データ構造の線形表(シングルチェーン表)復習問題

復習問題を通して、シングルチェーンの表をよく知って、固めます.まずその問題を見てください.
1.シングルチェーンテーブルL 2をシングルチェーンテーブルL 1の後ろに接続するアルゴリズムを設計する.2.ヘッドノードがないシングルチェーン表の削除アルゴリズムを設計する.3.無頭結点のシングルチェーン表の挿入アルゴリズムを設計する.5.ヘッドノードがないシングルチェーン表の逆置アルゴリズムを設計する.6.シングルチェーン表の逆置アルゴリズムを設計する.
これらの問題をする前に、私達はシングルチェーン表を作成しなければなりません.私達はそれぞれ頭の結点があるシングルチェーン表と頭の結点がないシングルチェーン表を作成します.コードは下記の通りです.
シングルチェーンの結点の種類を指定します.

/*       */
typedef struct Node{
	int data;		//    
	struct Node * next;	//    
}Node,*PNode;

頭の結点があるものを作成します.

//          
PNode Create(int * a,int Length){
	PNode head,p,q;
	head = (PNode)malloc(sizeof(Node));
	head->next = NULL;
	p = head;
	for(int i = 0;i < Length;i++){
		q = (PNode)malloc(sizeof(Node));
		q->data = a[i];
		q->next = NULL;
		p->next = q;
		p = q;
	}
	return head; 
}

ヘッダなしのノードを作成:

//           
PNode nCreate(int * b,int Length){
	PNode node,p,q;
	if(Length > 0){
		node = (PNode)malloc(sizeof(Node));
		node->data = b[0];
		node->next = NULL;
		p = node;
		for(int i = 1;i < Length;i++){
			q = (PNode)malloc(sizeof(Node));
			q->data = b[i];
			q->next = NULL;
			p->next = q;
			p = q;
		}
		return node;
	}
}

チェーンを作成しました.復習問題を始めましょう.
1.シングルチェーンテーブルL 2をシングルチェーンテーブルL 1の後ろに接続するアルゴリズムを設計する.
考え方:題意は二つのチェーンをつなぎ合わせることです.これは簡単です.生活の中で2つの線を1つの線につなぎたいなら、1つの線の末尾と1つの線の頭をつなぎます.このような考えは私達のこの問題でも役に立ちます.コードを見る:

//1.      L2      L1     
void ConnectList(PNode L1,PNode L2){
	PNode p;
	p = L1;
	while(p->next != NULL){ //     L1     
		p = p->next;
	}
	p->next = L2->next;     //        
}

2.ヘッドノードがないシングルチェーン表の削除アルゴリズムを設計する.
考え方:チェーンの一つの要素を削除して、最初の思考は削除された点の前の接合点を探してから、削除された点の前の接合点のポインタ領域を削除して、削除された点のポインタ領域に設定します.しかし、このように一つの困難があります.最初の一つは削除しても実現できません.頭通りのポイントがあるシングルチェーン表に適しています.後で考え方を変えて、削除要素を変えて理解しますと、あなたはシングルチェーンの表の中であなたの削除したその値が探し出せません.どうやって彼に見つけられませんか?簡単なのは、後のノードのデータ領域を削除されたデータ領域に上書きし、削除されたポイントのポインタ領域を後のノードのポインタ領域に設定することです.完全に削除操作が完了しました.もう一つの問題があります.最後の結点に会ったらどうすればいいですか?また、前の結点を記録する仮変数が必要です.最後の結点と判断したら、そのまま削除してもいいです.コードは以下の通りです

//2.               ；
bool nDelete(PNode node,int i,int *ptr){
	PNode p,q,m;
	int count = 0;
	p = node;
	while(p!=NULL && count < i-1){ //     i     
		m = p;						//m       i-1     
		p = p->next;
		count++;
	}
	if(p == NULL){
		return false;
	}else if(p->next == NULL){     //         。 
		*ptr = p->data;
		q = p;
		m->next = NULL;
	}else{
		*ptr = p->data;
		q = p->next;
		p->data = q->data;
		p->next = q->next;
	}
	free(q);
	return true;
}

3.無頭結点のシングルチェーン表の挿入アルゴリズムを設計する.
頭の結点がない挿入アルゴリズムは、最初の位置に要素を挿入してください.ここでは上の削除要素と同じ考えを採用しています.ここでは、私達はこう考えられます.私達は最初の位置に元素を挿入するのは面倒です.第二の位置に元素を挿入して、二つのノードのデータ領域を交換してもいいです.表に要素を挿入することもできますか?コードは以下の通りです

//3.               ；
bool nInsert(PNode node,int i,int ndata){
	PNode p = node,q;
	int count =0;
	while(p!=NULL&&count next;
		count++;
	}
	if(p == NULL){
		return false;
	}else{
		q = (PNode)malloc(sizeof(Node));
		q->data = p->data;		//      
		q->next = p->next;
		p->data = ndata;		//     
		p->next = q;
		return true;
	}
}

5.ヘッドノードがないシングルチェーン表の逆置アルゴリズムを設計する.
考え方:逆置アルゴリズムとは、位置を入れ替えて、最初と最後の交換位置、二つ目と最後から二つ目の交換位置をこれと類推することです.しかし、シングルチェーン表には毎回最初から始めなければならない欠点があります.配列は下付きで相応の元素を見つけることができません.相対的にいくつかの元素を探すのは難しい時があります.ここでは、チェーンを作る時に使うヘッド挿入法を使って逆置を実現できます.最初から遍歴して、各ノードを取り出して、新しい結点を作って、新しいチェーンを形成します.これは私達の逆置チェーンです.コードは以下の通りです

//5.               
PNode nInverse(PNode node){
	PNode p = NULL,q = NULL,m = NULL;
	p = q = node;
	while(q!=NULL){
		q = q->next;   //            
		p->next = m;  //      
		m = p;
		p = q;
	//	printf("fsf  ");
	}
	return m;
}

6.シングルチェーン表の逆置アルゴリズムを設計する.
考え方:これは無頭結点逆置の基本と同じです.自慢話ではなく、直接コードを見ます.

//6.          
void Inverse(PNode head){
	PNode p = NULL,q = NULL, m = NULL;
	p = q = head->next;  //      
	while(q!=NULL){
		q = q->next;
		p->next = m;
		m = p;
		p = q;
	}
	head->next = m;
}

はい、このいくつかの復習問題は大体終わって、自分でパソコンで練習します.分からないところはペンを持って紙に書いてください.絵を描いたら、構想があります.頑張って!
ソースをクリックしてリソースをダウンロードします.