算法與資料結構之雙向循環連結清單

雙向循環連結清單

雙向連結清單每結點有兩個指針，一個指向結點的前驅，另一個指向結點的後繼，是以從連結清單的每一個結點出發，都可到達任意一個結點，有利于連結清單的查找，單連結清單的找前驅函數，除了有指向目前結點的指針外，還有一個緊跟其，一直指向其前驅的指針。在雙向連結清單中。不需要這個指向前驅的指針。

雙向循環連結清單的實作

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//線性表的雙向連結清單存儲結構
typedef struct Node
{
	int data;	//資料域
	struct Node *prior,*next;	//一個指向前驅，一個指向後繼
}NODE,*PNODE;

//基本操作
PNODE Create1(); //建立雙向循環連結清單，在表尾插入資料
PNODE Create2(); //建立雙向循環連結清單，在表頭插入資料
void Init(PNODE pHead);	//構造空的雙向循環連結清單
void Destroy(PNODE pHead); //銷毀雙向循環連結清單
void Clear(PNODE pHead); //将雙向連結清單置空
bool Empty(PNODE pHead); //判斷雙向連結清單是否為空
int Length(PNODE pHead); //傳回連結清單元素個數
bool Get(PNODE pHead,int i,int *e);	//将第i個元素的值賦給e
bool Prior(PNODE pHead,int cur_e,int *pre_e);//用pre_e儲存cur_e元素的前驅元素
bool Next(PNODE pHead,int cur_e,int *next_e);	//用pre_e儲存cur_e元素的後繼元素
bool Insert(PNODE pHead,int i,int e); //在第i個位置前面插入元素e
bool Delete(PNODE pHead,int i,int *e);//删除第i個位置的元素，用e儲存
void Traverse1(PNODE pHead); //正向周遊雙向連結清單
void Traverse2(PNODE pHead); //逆向周遊雙向連結清單

int main()
{
	int val;
	PNODE pHead=NULL;
	pHead=Create1();
	Traverse1(pHead);
	printf("連結清單元素個數為：%d\n",Length(pHead));
/*	Clear(pHead);
	if(Empty(pHead))
		printf("連結清單為空！\n");
	else
		printf("連結清單不為空！\n");
*/
	if(Get(pHead,3,&val))
		printf("第三個元素的值為：%d\n",val);
	else
		printf("第三個元素無值！\n");
	if(Prior(pHead,3,&val))
		printf("元素3的前驅元素是：%d\n",val);
	else
		printf("元素3無前驅！\n");
	if(Next(pHead,3,&val))
		printf("元素3的後繼元素是：%d\n",val);
	else
		printf("元素3無後繼！\n");
	if(Insert(pHead,4,100))
		printf("插入成功！\n");
	else
		printf("插入失敗！\n");
	Traverse1(pHead);
	printf("連結清單元素個數為：%d\n",Length(pHead));
	if(Delete(pHead,3,&val))
		printf("删除的元素為：%d\n",val);
	else
		printf("删除失敗！\n");
	Destroy(pHead);
	printf("銷毀成功！\n");
	return 0;
}

PNODE Create1()
{
	int i,val;
	PNODE pHead,pNew,pTail;
	pHead=(PNODE)malloc(sizeof(NODE));
	if(pHead==NULL)
		exit(-1);
	pHead->next=pHead;
	pHead->prior=pHead;
	pTail=pHead;
	printf("請輸入申請的元素的個數：");
	scanf("%d",&val);
	if(val<1)
		exit(-1);
	for(i=0;i<val;i++)
	{
		pNew=(PNODE)malloc(sizeof(NODE));
		if(pNew==NULL)
			exit(-1);
		printf("輸入第%d個元素的值：",i+1);
		scanf("%d",&pNew->data);
		pTail->next=pNew;
		pNew->prior=pTail;
		pTail=pNew;
	}
	pHead->prior=pTail;
	pTail->next=pHead;
	return pHead;
}
PNODE Create2()
{
	int i,val;
	PNODE pHead,pNew;
	pHead=(PNODE)malloc(sizeof(NODE));
	if(pHead==NULL)
		exit(-1);
	pHead->next=pHead;
	pHead->prior=pHead;
	printf("請輸入申請的元素的個數：");
	scanf("%d",&val);
	if(val<1)
		exit(-1);
	pNew=(PNODE)malloc(sizeof(NODE));
	if(pNew==NULL)
		exit(-1);
	printf("輸入第1個元素的值：");
	scanf("%d",&pNew->data);
	pHead->next=pNew;
	pNew->next=pHead;
	pHead->prior=pNew;
	pNew->prior=pHead;
	for(i=0;i<val-1;i++)
	{
		pNew=(PNODE)malloc(sizeof(NODE));
		if(pNew==NULL)
			exit(-1);
		printf("輸入第%d個元素的值：",i+2);
		scanf("%d",&pNew->data);
		pNew->next=pHead->next;
		pHead->next=pNew;
		pNew->prior=pHead;
		pNew->next->prior=pNew;
	}
	return pHead;
}
void Init(PNODE pHead)
{
	pHead=(PNODE)malloc(sizeof(NODE));
	if(pHead==NULL)
		exit(-1);
	pHead->prior=pHead;
	pHead->next=pHead;
}
void Destroy(PNODE pHead)
{
	PNODE p=(pHead)->prior,q;
	while(pHead!=p)
	{
		q=(pHead)->next;
		free(pHead);
		pHead=q;
	}
	free(pHead);
	pHead=NULL;
}
void Clear(PNODE pHead)
{
	PNODE p=pHead->next,q;
	while(p!=pHead)
	{
		q=p->next;
		free(p);
		p=q;
	}
	pHead->prior=pHead;
	pHead->next=pHead;
}
bool Empty(PNODE pHead)
{
	if(pHead->next==pHead&&pHead->prior==pHead)
		return true;
	else
		return false;
}
int Length(PNODE pHead)
{
	int count=0;
	PNODE p=pHead->next;
	while(p!=pHead)
	{
		count++;
		p=p->next;
	}
	return count;
}
bool Get(PNODE pHead,int i,int *e)
{
	int j=1;
	PNODE p=pHead->next;
	while(j<i&&p!=pHead)
	{
		j++;
		p=p->next;
	}
	if(j>i||p==pHead)
		return false;
	*e=p->data;
	return true;
}
bool Prior(PNODE pHead,int cur_e,int *pre_e)
{
	PNODE p=pHead->next->next;
	while(p!=pHead)
	{
		if(p->data==cur_e)
		{
			*pre_e=p->prior->data;
			return true;
		}
		p=p->next;
	}
	return false;
}
bool Next(PNODE pHead,int cur_e,int *next_e)
{
	PNODE p=pHead->next;
	while(p!=pHead->prior)
	{
		if(p->data==cur_e)
		{
			*next_e=p->next->data;
			return true;
		}
		p=p->next;
	}
	return false;
}
bool Insert(PNODE pHead,int i,int e)
{
	int j=1;
	PNODE p=pHead,pNew;
	if(i<1||i>Length(pHead)+1)
		return false;
	while(j<i)
	{
		j++;
		p=p->next;
	}
	pNew=(PNODE)malloc(sizeof(NODE));
	if(pNew==NULL)
		exit(-1);
	pNew->data=e;
	pNew->next=p->next;
	p->next=pNew;
	pNew->prior=p;
	pNew->next->prior=pNew;
	return true;
}
bool Delete(PNODE pHead,int i,int *e)
{
	int j=1;
	PNODE p=pHead->next;
	if(i<1||i>Length(pHead))
		return false;
	while(j<i)
	{
		p=p->next;
		j++;
	}
	*e=p->data;
	p->prior->next=p->next;
	p->next->prior=p->prior;
	free(p);
	return true;
}
void Traverse1(PNODE pHead)
{
	PNODE p=pHead->next;
	while(p!=pHead)
	{
		printf("%d	",p->data);
		p=p->next;
	}
	printf("\n");
}
void Traverse2(PNODE pHead)
{
	PNODE p=pHead->prior;
	while(p!=pHead)
	{
		printf("%d	",p->data);
		p=p->prior;
	}
	printf("\n");
}