「データ構造とアルゴリズム」第2章線形表——練習問題

1.逆さま順序表のアルゴリズムを作成してください.アルゴリズムの時間複雑性はO(n)で、空間複雑性はO(1)です.nはシーケンステーブルの長さである.

#include 
#define MAXN 100	
void turn(int List[],int *p_len)
{
	if (*p_len<0||*p_len>MAXN)
		printf("    ");
	else{ 
		for (int i=0;i<=*p_len/2;i++)
		{
			int tmp = List[i];
			List[i] = List[*p_len-i-1];
			List[*p_len-i-1] = tmp;
		}
	}	
}

int main()
{
	int st[MAXN] = {1,2,3,4,5,6,7,8,9,0};
	int n = 10;
	turn(st,&n);
	int i=0;
	while (i<10)  {
		printf("%d",st[i]);
		i++;
	}
	
	return 1;
}

2.リニアテーブルの長さを求めるアルゴリズムを作成してください.リニアテーブルがシングルチェーンテーブルとして記憶されていると仮定します.

#include 
#include 

typedef struct node {
	char data;
	struct node *next;
}NODE;
					
int LinkLen(NODE *L)
{
	int k = 0;
	while (L) {
		k++;
		L = L->next;
	}
	return k;
}		

int main()
{
	NODE *a,*b,*c;
	a = (NODE*)malloc(sizeof(NODE));	
	b = (NODE*)malloc(sizeof(NODE));	
	c = (NODE*)malloc(sizeof(NODE));	
	a->next = b;
	b->next = c;
	c->next = NULL;
	int k = LinkLen(a);
	printf("%d",k);
}			

3.シングルチェーン表の練習問題をやり直します.
表面なし:

#include 
#include 

typedef struct node {
	int data;
	struct node *next;
}NODE;

NODE* TurnLink(NODE *head)
{
	NODE *HEAD = NULL;
    NODE *p;
    while(head){
         p = head;
         head = head->next;
         p->next = HEAD;
         HEAD = p;     
    }
    return HEAD;   
}

int main()
{
	NODE *a,*b,*c;
	a = (NODE*)malloc(sizeof(NODE));	
	b = (NODE*)malloc(sizeof(NODE));	
	c = (NODE*)malloc(sizeof(NODE));
	a->data = 1;	
	a->next = b;
	b->data = 2;
	b->next = c;
	c->data = 3;
	c->next = NULL;
	NODE* k = TurnLink(a);
	printf("%d",k->data);
}

4.整数の線形表でも辞書の順序を定義することができます.任意の2つの線形表A=(a 0,a 1,...am)、B=(b 1,b 2,...,bn)に対して、データ要素は整数である.(1)m=nでai=bi(i=0,1,…m-1)であれば、A=Bと定義する.(2)m(3)AとBが上記の2つに該当しない場合、必ずjが存在し、jBが存在する.二つの順序表の大きさを判定するアルゴリズムを作成してください.ABなら、1を返します.

typedef struct LIST {
	int list[MAXN];
	int k;
}List;

int test (List a,List b)
{
	if (a->k == b->k) {
		int time;
		for (int i = 0;i<a->k;i++) 
			if (a->list[i] == b->list[i] ) 
				time++;
		if (time == a->k) return 0;		
	}
	if (a->k < b->k) {
		int time;
		for (int i = 0;i<a->k;i++) 
			if (a->list[i] == b->list[i] ) 
				time++;
		if (time == a->k) return -1;
	}
	for (int j=0;j<m&&j<n;j++) {
		if (a->list[j]<b->list[j]) return -1;
		if (a->list[j]>b->list[j]) return 1;
	}
}

5、シングルチェーン表の練習問題をやり直します.

  int test (NODE *a,NODE *b)
{
	int alin = 0,blin = 0;
	NODE *pa = a;
	NODE *pb = b;
	while (pa) {
		pa = pa->next;
		alin++;
	}
	pa = a;
	while (pb) {
		pb = pb->next;
		blin++;
	}
	pb = b;
 	if (alin == blin) {
 		int time;
 		while ((pa->data == pb->data)&&(!pa && !pb)){
 			pa = pa->next;
 			pb = pb->next;
 			time++;
 		}
 	if (time == alin) return 0;
	}
	pa =a,pb =b;
	if (alin < blin) {
		while ((pa->data == pb->data)&&(!pa && !pb)){
 			pa = pa->next;
 			pb = pb->next;
 			time++;
 		}
 	if (time == alin) return -1;
	}
	pa =a,pb =b;
	while (pa->data == pb->data) {
		pa = pa->next;
		pb = pb->next;	
	}
	if (pa->data<pb->data) return -1;
	else return 1;
}

typedef struct node {
	int data;
	struct node *next;
}NODE;

6.手順表の重複要素を削除するアルゴリズムを作成してください.あなたのアルゴリズムの時間複雑性を分析します.時間複雑性:O(n^2)

int SqListDelete(int[] list,int *p_len,int i)
{
	int j;
	if(i<0||i>=*p_len)
		return 0;
	for (j=i+1;j<*p_len;j++)
		list[j-1]=list[j];
	(*p_len)--;	
} 
void Delete (int[] list,int k) {
	for (int i=0;i<k;i++) {
		for (int j=i+1;j<k;j++) {
			if (list[i]==list[j]) {
				SqListDelete(list,&k,j);
			}
		}
	}
}

7.アルゴリズムを作成してください.シングルチェーン表では、値がaの結点をbの結点の前に挿入します.チェーンの中にbという値の結点がない場合、aという値の結点をチェーンの尾部に挿入します.

typedef struct node{
	int data;
	struct node *next;
}NODE;

void test7(NODE *head,int a,int b)
{
	NODE *p1 = head,p2 = head->next,q1,q2;
	if (p1) {
		while (p2) {
			if (p2->data==a){
				break;
			}
			p1 = p2;
			p2 = p2->next;
		}
		if (!p2) return 0;
		q1 = head;
		q2 = q->next;
		while (q2) {
			if (q2->data==b){
				p1->next = p2->next;
				q1->next = p2;
				p2->next = q2;
				return 0;
			}
			q1 = q2;
			q2 = q2->next;
		}
	}
	return 0;
}

8.一つのバンドヘッドのシングルチェーンテーブルAを二つの同じ構造のチェーンテーブルBとCに分解するアルゴリズムを作成してください.Bの結点はAの中の値がゼロ以下の結点であり、Cの結点はAの中の値がゼロより大きい結点である.Aに保存されているのは整数値であると仮定する.

typedef struct node{
	int data;
	struct node *next;
}NODE;

NODE* test8(NODE *A)
{
	NODE *B,*C,a,b,c;
	B = (NODE*)malloc(sizeof(NODE));
	C = (NODE*)malloc(sizeof(NODE));
	B->next = NULL;
	C->next = NULL;
	a = A;
	b = B;
	c = C;
	while (a->next) {
		if (a->next->data<0) {
			b->next = a;
			b = b->next;
			a->next = b->next;
			b->next = NULL;
		}
		else if (a->next->data>0) {
			c->next = a;
			c = c->next;
			a->next = c->next;
			c->next = NULL;
		}
		a = a->next;
	}
	return B,C;
}

9.一方向循環チェーンテーブルが設けられており、各ノードは3つのドメイン:pror、data、nextを含み、dataはデータドメインであり、nextは後継ノードを指すポインタであり、prorもポインタであるが、その値は空である.アルゴリズムを作成してみて、この一方向循環チェーン表を双方向循環チェーンに変換し、prorが前駆ノードを指すようにします.

typedef struct node{
	int data;
	struct node *next;
	struct node *prior;
}NODE;

NODE* test9(NODE *head)
{
	NODE *p = head;
	NODE *q = head->next;
	while (q->prior) {
		q->prior = p;
		p = q;
		q = q->next;
	}
}

10.一つのアルゴリズムを作成してください.二つのバンドヘッドの規則的な循環チェーン表を一つのバンドヘッドの規則的な循環チェーン表にまとめてください.問題を出すSBは、書かないで何順に保存しますか?ここは子供の時から大人になるまでのところです.

typedef struct node{
	int data;
	struct node *next;
}NODE;

NODE* test10(NODE *a,NODE *b)
{
	NODE *boos = (NODE*)malloc(sizeof(NODE));
	boos->next = NULL:
	NODE *boos1 = boss;
	NODE *p1 = a->next;
	NODE *q1 = b->next;
	while(!p1 && !p2) {
		if (p1->data>q1->data){
			boos1->next = p1;
			boos1 = boos1->next;
			p1 = p1->next;
		}
		else {
			boos1->next = q1;
			boos1 = boos1->next;
			q1 = q1->next;
		}
	if (!p1){
		boos1->next = q1;
		while(q1){
			boos1 = q1;
			q1 = q1->next;
		}
		boos1->next = boos->next;
	}	
	else{
		boos1->next = p1;
		while(p1){
			boos1 = p1;
			p1 = p1->next;
		}
		boos1->next = boos->next;
	}
	return boos;
	
}

11.多項式F(x)はバンドヘッドの規則的なシングルチェーンとして表していると仮定します.F(x 0)の値を求めるアルゴリズムを作成してください.x 0は任意の与えられた浮動小数点です.