算法設計學習：單連結清單算法

（1）題目：單連結清單A 和 B （帶表頭結點），元素遞增有序。設計算法将A 和 B歸并成一個按照元素值依然遞增有序的連結清單C，C由A和B的結點組成。

分析：A，B有序，可以從A，B中挑出最小的元素插入C的尾部。若是一個插入完畢，另一個則隻要連結到C的尾部。

代碼：

typedef struct LNode
{
	int data;
	struct LNode *next;  //指向後繼結點的指針
}LNode;

void mergeLinkedList( LNode *&A, LNode *&B, LNode *&C)  //要改變的變量使用引用型
{
	LNode *p = A->next;	 //p 跟蹤A的最小值結點
	LNode *q = B->next;	 //q 跟蹤B的最小值結點
	LNode *r;			 //r 指向C的終端結點

	C = A;				  //使用A頭結點作為C的頭結點
	C->next = NULL;
	free(B);			 // B的頭結點無用，釋放掉
	r = C;				  //頭結點

	while( NULL != p && NULL != q )
	{
		if ( p->data <= q->data )
		{
			r->next = p;
			p = p->next; // A移動元素
			r = r->next; // C尾結點向後移動
		}
		else
		{
			r->next = q;
			q = q->next; // B移動元素
			r = r->next; // C尾結點向後移動
		}
	}

	r->next = NULL;		//此句話可以去掉，下面兩個if語句必須有一個要執行

	if ( NULL != p )	   //還有剩餘結點的連結清單連結在尾部
	{
		r->next = p;
	}
	if ( NULL != q )
	{
		r->next = q;
	}
}
           

總結：1）尾插法建立單連結清單；2）單連結清單歸并操作

引申：歸并稱為  遞減的連結清單C。  （将插入過程改為頭插入法即可）

代碼：

void mergeLinkedListDescend( LNode *&A, LNode *&B, LNode *&C)
{
	LNode *p = A->next;	 //p 跟蹤A的最小值結點
	LNode *q = B->next;	 //q 跟蹤B的最小值結點
	LNode *s;			 //用 S來接受新的結點插傳入連結表C的前端

	C = A;				  //使用A頭結點作為C的頭結點
	C->next = NULL;
	free(B);			 // B的頭結點無用，釋放掉

	while( NULL != p && NULL != q )
	{
		if ( p->data <= q->data )	//連結清單的頭插入法
		{
			s = p;		 //将 p 指派給 接受新結點的 s
			p = p->next; // A移動元素

			s->next = C->next;	// s 所指向新結點的指針域next 指向C中的開始結點
			C->next = s;        // 頭結點的指針域next指向 s結點，使得s稱為新的開始結點
		}
		else
		{
			s = q;  	//将 q 指派給 接受新結點的 s
			q = q->next; // B移動元素

			s->next = C->next;	// s 所指向新結點的指針域next 指向C中的開始結點
			C->next = s;        // 頭結點的指針域next指向 s結點，使得s稱為新的開始結點
		}
	}

	while ( NULL != p )	   //還有剩餘結點的連結清單逐個插入到C的頭部
	{
		s = p;		 
		p = p->next; 
		s->next = C->next;	   //  這兩句插入順序不能颠倒。	 後繼結點先寫
		C->next = s;  			// 這兩句插入順序不能颠倒。
	}
	while ( NULL != q )
	{
		s = q;  
		q = q->next; 
		s->next = C->next;	
		C->next = s;     
	}
}
           

（2）題目：查找連結清單C（帶頭結點）中是否存在一個值為 x 的結點，若存在，則删除該結點并傳回1，否則傳回0.

代碼：

int SearchAndDelete(LNode *&C, int x)
{
	LNode *p;
	LNode *q;
	p = C;
	//查找部分 開始
	while( NULL != p)
	{
		if ( x == p->next->data )
		{	 
			break;
		}
		p = p->next;
	}
	 //查找部分結束
	if ( NULL == p->next )
	{
		return 0;
	}
	else
	{
		//删除部分開始
		q = p->next;
		p->next = p->next->next;   //将p的指針域next指向原來p的下一個結點的下一個結點，即可删除  或者寫成  p->next = q->next;
           

free(q);	//釋放q所指結點的記憶體空間
		//删除部分結束
		return 1;
	}
}
           

附錄：假設有n個元素已經儲存在數組a中，下面分别是尾插法與頭插法建立連結清單C

//尾插法
void CreateListR(LNode *&C, int a[], int n)
{
	LNode *s;  //s用來指向新申請的結點
	LNode *r;  //r指向C的終端結點
	int i;
	C = (LNode*) malloc( sizeof(LNode));	  //  申請C的頭結點空間
	C->next = NULL;
	r = C;
	for ( i = 1; i <= n; ++ i )
	{
		s = (LNode*) malloc( sizeof(LNode));   //s指向新申請的結點
		s->data = a[i];    //新申請的結點接收a的一個元素
		r->next = s;		//r來接納新結點
		r = r->next;		//r指向終端結點，以便接納下一個到來的結點
	}
	r->next = NULL;	  //a中的元素全部裝傳入連結表C中，C的終端指針為NULL
}

//頭插法
void CreateListF(LNode *&C, int a[], int n)
{
	LNode *s;
	int i;
	C = (LNode*) malloc( sizeof(LNode));	  //  申請C的頭結點空間
	C->next = NULL;
	for ( i = 1; i <= n; ++ i )
	{
		s = (LNode*) malloc( sizeof(LNode));   //s指向新申請的結點
		s->data = a[i];    //新申請的結點接收a的一個元素
		 /*  下面兩句為 頭插法 的關鍵步驟*/
		s->next = C->next;			//s所指新結點的指針域next指向C中的開始結點
		C->next = s;			   //頭結點的指針域next指向s結點，使得s成為了新的開始結點
	}
}
           

<pre name="code" class="cpp">//整表删除
int ClearList(LNode *&C)
{
	LNode *p;
	LNode *q;
	p = C->next;

	while(p)
	{
		q = p->next;
	    free(p);
		p = q;
	}
	C->next = NULL;
	return 1;
}