雙向連結清單

引言：

        單連結清單存在一個問題，當我們想要訪問某個結點的前一個結點時。要從頭結點開始訪問。顯然這種操作是令人煩躁的。為此，雙向連結清單出現，它比單連結清單多出了一個指針域。指向前一個結點。

這樣，對于雙向連結清單。就能夠友善的從後向前周遊連結清單了。但多出的問題是對于插入和删除結點的開銷要添加一倍。

分析描寫叙述：

        雙向連結清單存儲結構圖為：

，用結構體表示範樣例如以下：

typedef	int	ElemType;
typedef struct LNode{
	ElemType	data;
	struct LNode *prior;
	struct LNode *next;
}LNode, *PLNode;
      

        雙向連結清單的初始化。

雙向連結清單的初始化，即配置設定一個LNode結構體大小的記憶體。使它的prior指針和next指針都指向結點本身。

PLNode InitDList(void)
{
	PLNode HeadLNode = (PLNode)malloc(sizeof(LNode));
	if(HeadLNode == NULL){
		printf("malloc memory fail.\n");	
		return NULL;
	}

	HeadLNode->prior = HeadLNode->next = HeadLNode;

	return HeadLNode;
}
      

        雙向連結清單建立連結清單。

向已經初始化的雙向連結清單的頭部插入結點元素。

PLNode CreateDList(PLNode PHeadNode)
{
	PLNode TmpLNode = (PLNode)malloc(sizeof(LNode));
	if(TmpLNode == NULL){
		printf("malloc memory fail.\n");	
		return PHeadNode;
	}
	TmpLNode->next = NULL;

	while(scanf("%d", &TmpLNode->data) != 0){
		TmpLNode->next        = PHeadNode->next;
		TmpLNode->prior       = PHeadNode;
		PHeadNode->next       = TmpLNode;
		if(TmpLNode->next != NULL)//此處的推斷是針對空連結清單的操作，假設是空連結清單，以下的語句就不做。
			TmpLNode->next->prior = TmpLNode;	

		TmpLNode = (PLNode)malloc(sizeof(LNode));
		if(TmpLNode == NULL){
			return PHeadNode;
		}
	}
	free(TmpLNode);

	return PHeadNode;
}
      

          雙向連結清單的周遊。

此處的連結清單的周遊與前面提到的單連結清單的周遊沒有什麼不同。須要注意的地方還是對參數的保護。

void TraverseDList(PLNode PHeadNode)
{
	PLNode TmpLNode = PHeadNode;

	if(PHeadNode == NULL) {
		printf("input element faulse.\n");
		return ;
	}

	while(TmpLNode->next != NULL){
		printf("%d ", TmpLNode->next->data);	
		TmpLNode = TmpLNode->next;
	}
	putchar('\n');
}
      

         雙向連結清單的長度。

跟求單連結清單長度一樣。          

int ListLength(PLNode PHeadNode)
{
	int count = 0;
	while(PHeadNode->next != NULL){
		count++;
		PHeadNode = PHeadNode->next;	
	}

	return count;
}
      

         雙向連結清單中插入節點元素。給定一個雙向連結清單和插入位置，給定一個結點元素，向給定的連結清單中插入該結點。

PLNode InsertDList(PLNode PHeadNode, ElemType data, int Index)
{
	int index = 0;
	PLNode TmpLNode = PHeadNode;

	if(PHeadNode == NULL || Index < 0 || Index > ListLength(PHeadNode) + 1){
		printf("input element faulse.\n");	
		return NULL;
	}

	for(index = 1; index < Index; index++){
		TmpLNode = TmpLNode->next;	
	}

	PLNode Tmp = (PLNode)malloc(sizeof(LNode));
	if(Tmp == NULL){
		printf("malloc memory faluse.\n");	
		return PHeadNode;
	}
	Tmp->data = data;

	Tmp->next = TmpLNode->next;
	Tmp->prior = TmpLNode->prior;
	TmpLNode->next = Tmp;
	TmpLNode->prior = Tmp;

	return PHeadNode;
}
      

          雙向連結清單中删除結點。

PLNode DeleteList(PLNode PHeadNode,  int Index)
{
	int index;
	PLNode TmpNode = PHeadNode;

	if(PHeadNode == NULL || Index < 0 || Index > ListLength(PHeadNode)){
		printf("input element faulse.\n");	
		return NULL;
	}
	

	for(index = 0; index < Index; index++){
		TmpNode = TmpNode->next;	
	}
	TmpNode->prior->next = TmpNode->next;
	if(TmpNode->next != NULL)
		TmpNode->next->prior = TmpNode->prior;
	free(TmpNode);

	return PHeadNode;
}
      

        雙向連結清單中删除結點。

PLNode DeleteList(PLNode PHeadNode,  int Index)
{
	int index;
	PLNode TmpNode = PHeadNode;

	if(PHeadNode == NULL || Index <= 0 || Index > ListLength(PHeadNode)){
		printf("input element faulse.\n");	
		return NULL;
	}
	
	for(index = 0; index < Index; index++){
		TmpNode = TmpNode->next;	
	}

	TmpNode->prior->next = TmpNode->next;
	TmpNode->next->prior = TmpNode->prior;

	free(TmpNode);

	return PHeadNode;
}