資料結構-雙向鏈表的基本操作 詳解（c語言實作）

1.創造一個節點,函式實作

DListNode* BuyListNode(Datetype x)
{
	DListNode*node = (DListNode*)malloc(sizeof(DListNode));
	node->date = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

2. 初始化

DListNode* DListInit()
{
	DListNode*plist = BuyListNode(0);
	plist->date = 0;
	plist->next = plist;
	plist->prev = plist;
	return plist;
}
//既然是雙向回圈鏈表，初始化的時候，prev與next需要指向自己，

既然是雙向回圈鏈表，初始化的時候，prev與next需要指向自己，

3.判空

int DListIsEmpty(DListNode*plist)
{
	return plist->next == plist ? 1 : 0;
}

只有一個頭節點的時候，鏈表為空，

4.頭插

void DListPushFront(DListNode*plist,Datetype x)
{
	DListNode*first = plist->next;
	DListNode*newnode = BuyListNode(x);
	newnode->prev = plist;
	plist->next = newnode;
	newnode->next=first;
	first->prev = newnode;
}
//只有一個頭結點時，代碼也是正確的，

只有一個頭節點時，代碼也是正確的，

5.尾插

void DListPushBack(DListNode*plist,Datetype x)
{
	if (DListIsEmpty(plist))
	{
		return;
	}
//如果是空表的話，就與尾插這個定義矛盾了，
	DListNode*tail = plist->prev;
	DListNode*newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = plist;
	plist->prev = newnode;
}

尾插肯定需要找尾，

6.頭刪

void DListPopFront(DListNode*plist)
{
	if (DListIsEmpty(plist))
	{
		return;
	}
	DListNode*first = plist->next;
	DListNode*next = first->next;
	free(first);
	first = NULL;
	plist->next = next;
	next->prev = plist;
}

一個頭節點與一個節點和一個頭節點與多個節點代碼都是一樣的，

7.尾刪

void DListPopBack(DListNode*plist)
{
	if (DListIsEmpty(plist))
	{
		return;
	}
	DListNode*tail = plist->prev;
	DListNode*tailprev = tail->prev;
	free(tail);
	tail = tailprev;
	tail->next = plist;
	plist->prev = tail;
}

一個頭節點與一個節點和一個頭節點與多個節點代碼都是一樣的，

8.查找資料

DListNode* DListFind(DListNode*plist,Datetype x)
{
	DListNode*cur = plist->next;
	while (cur != plist)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;	
	}
	return NULL;
}

查找資料成功后 就回傳資料的地址 ，

9.在pos下一個位置插入資料

void DListInsertAfter(DListNode*pos, Datetype x)
{
	assert(pos);//保證傳過來的地址不能為空
	DListNode*next = pos->next;
	DListNode*newnode = BuyListNode(x);
	pos->next = newnode;
	newnode->prev = pos;
	newnode->next = next;
	next->prev = newnode;
}

需要注意的是 pos不能為空，

10.在pos的上一個位置插入資料

void DListInsertBefore(DListNode*pos, Datetype x)
{
	assert(pos);
	DListNode*prev = pos->prev;
	DListNode*newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

一個頭節點和一個有效節點時 代碼也正確，

11.修改pos位置的資料

void DListModify(DListNode*pos, Datetype x)
{
	assert(pos);
	pos->date = x;
}

12.洗掉pos位置的資料

void DListErase(DListNode*pos)
{
	assert(pos);
	DListNode*next = pos->next;
	DListNode*prev = pos->prev;
	free(pos);
	pos = next;
	prev->next = next;
	next->prev = prev;
}

13.鏈表的有效長度（不包括頭節點）

int DListSize(DListNode*plist)
{
	DListNode*cur = plist->next;
	int size = 0;
	while (cur != plist)
	{
		cur = cur->next;
		++size;
	}
	return size;
}

14.列印鏈表（測驗各個介面）

void Print(DListNode*plist)
{
	DListNode*cur = plist->next;
	while (cur != plist)
	{
		printf("%3d", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

15.銷毀鏈表

void Destory(DListNode*plist)
{
	DListNode*cur = plist->next;
	while (cur != plist)
	{
		DListNode*next = cur->next;
		free(cur);
		cur = next;
	}
	free(plist);
	plist = cur = NULL;
}
//因為這里傳的是一級指標，主函式定義的phead也需要置空，防止phead成為野指標，

因為這里傳的是一級指標，主函式定義的phead也需要置空，防止phead成為野指標，

16.測驗

test()
{
//頭插3個資料
	DListNode*phead = DListInit();
	DListPushFront(phead, 3);
	DListPushFront(phead, 2);
	DListPushFront(phead, 1);
	Print(phead);

//尾插3個資料
	DListPushBack(phead, 4);
	DListPushBack(phead, 5);
	DListPushBack(phead, 6);
	Print(phead);

//頭刪1個資料
	DListPopFront(phead);
	Print(phead);

//尾刪1個資料
	DListPopBack(phead);
	Print(phead);

//查找資料，如果查找資料成功了，就回傳資料的地址，失敗，就回傳空，
	DListNode* pos = DListFind(phead, 3);
	if (pos)
	{
		printf("  Date found");
		printf("\n");
	}

//在pos下一個位置插入1個資料
	DListInsertAfter(pos, 7);
	Print(phead);

//在pos的上一個位置插入1個資料
	DListInsertBefore(pos, 8);
	Print(phead);

//將pos位置的資料改變
	DListModify(pos, 9);
	Print(phead);

//消除pos位置的資料
	DListErase(pos);
	Print(phead);

//計算出鏈表中的有效數字
	printf("  %d\n",DListSize(phead));
	Destory(phead);
	phead = NULL;//防止phead成為野指標
}

雙向鏈表的基本操作就分享到這里了，謝謝你的瀏覽，如果這篇博文對你有幫助的話，可以點個贊，順手再來個關注，

下期將發布與字串函式的相關內容的文章，