C語言怎么實現帶頭雙向循環鏈表

本篇內容主要講解“C語言怎么實現帶頭雙向循環鏈表”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“C語言怎么實現帶頭雙向循環鏈表”吧!

創建鏈表存儲結構

我們需要創建一個結構體來存儲一個鏈表結點的相關信息。

typedef int ListDataType;//將ListDataType先定義為int類型，根據需要可以改為不同的類型
//創建一個鏈表的結構體
typedef struct ListNode
{
	ListDataType data;//存儲數據
	struct ListNode* next;//存儲下一個結點的地址的指針
	struct ListNode* prev;//存儲上一個結點的地址的指針
}ListNode;

創建結點

我們每次增加數據都要創建一個新的結點，但每次都創建就會非常的麻煩。所以我們考慮把創建一個結點這個功能封裝成一個函數，每次要使用只要調用一下就可以了。

ListNode* BuyListNode(ListDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//向內存申請一個新的結點
	if (newnode == NULL)
	{
		printf("BuyListNode::%s\n", strerror(errno));//打印結點空間申請失敗的原因
		exit(-1);//終止程序
	}
	newnode->data = x;//將x放入申請的結點數據區
	newnode->next = NULL;//讓新結點的next指向空
	newnode->prev = NULL;//讓新結點的prev指向空
	return newnode;//返回新結點的地址
}

鏈表的初始化

帶頭雙向循環鏈表我們對其初始化就是申請一個帶哨兵位的頭結點。接下來我們看初始化的兩種方法。

void ListInit(ListNode** pphead)//這里我們需要對頭結點進行改變，所以傳二級指針
{
	assert(pphead);//檢測傳過來的pphead的地址是否為空
	*pphead = BuyListNode(0);//創建一個新的哨兵位頭結點
	(*pphead)->next = *pphead;//讓這個結點指向自己
	(*pphead)->prev = *pphead;
}

ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);//創建一個新的哨兵位頭結點
	phead->next = phead;//讓這個結點的next指向自己
	phead->prev = phead;//讓prev指向自己
	return phead;//返回哨兵位頭結點的地址
}

雙向鏈表的打印

我們才用遍歷鏈表的方式來打印鏈表中的數據。

void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;//讓cur指向哨兵位的下一個結點
	while (cur != phead)//鏈表打印是否結束的條件判斷
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

雙向鏈表尾插

雙向循環鏈表結構比較優，所以很方便找到尾結點。尾結點就是哨兵位結點prev指向的結點。

void ListPushBack(ListNode* phead, ListDataType x)
{
	assert(phead);//檢查傳過來的頭結點是否為空
	ListNode* tail = phead->prev;//找到鏈表的尾結點
	ListNode* newnode = BuyListNode(x);//創建一個新的結點

	tail->next = newnode;//讓尾結點的next指向新的結點
	newnode->prev = tail;//讓新結點的prev指向之前的尾結點
	newnode->next = phead;//讓新的結點的next指向頭結點
	phead->prev = newnode;//讓頭結點指向新的尾結點
}

雙向鏈表尾刪

void ListPopBack(ListNode* phead)
{
	assert(phead);
	if (phead->next == phead)//如果鏈表只有哨兵位結點的情況，就不能繼續刪除了
		return;

	ListNode* tail = phead->prev;//找到尾結點
	ListNode* tailPrev = tail->prev;//定義尾結點的前一個結點
	free(tail);//釋放要刪除的結點
	tailPrev->next = phead;//讓前一個結點指向哨兵位結點
	phead->prev = tailPrev;//讓哨兵位結點指向新的尾結點
}

雙向鏈表頭插

雙向鏈表的頭插就是在哨兵位結點的下一個位置插入一個新的數據。

注意：這一種方法種的指向關系不能隨意顛倒，否則就會出錯。

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);//創建一個新結點
	newnode->next = phead->next;//新結點的next指向頭結點的下一個結點
	phead->next->prev = newnode;//頭結點的下一個結點指向新結點
	phead->next = newnode;//頭結點指向新結點
	newnode->prev = phead;//新結點prev指向頭結點
}

我們可以對上一種情況進行優化，定義一個next記錄頭結點的下一個結點的地址。這樣我們就可以不用在意指向順序的問題，可以減少出錯的概率。

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);//創建一個新結點
	ListNode* next = phead->next;//定義next記錄頭節點的下一個結點的位置
	phead->next = newnode;//頭結點next指向新結點
	newnode->prev = phead;//新結點的prev指向頭結點
	next->prev = newnode;//頭結點的下一個結點的prev指向新階段
	newnode->next = next;//新結點的next指向原頭結點的下一個結點
}

雙向鏈表頭刪

我們先找到頭結點的下一個結點，然后在把它釋放掉。這里需要注意的是如果鏈表為空，只有哨兵位頭結點的情況，我們需要對其進行特殊的處理。

void ListPopFront(ListNode* phead)
{
	assert(phead);
	if (phead->next == NULL)//只有哨兵位頭結點的情況
		return;
	ListNode* next = phead->next->next;//定義next指向要刪除結點的下一個結點
	free(phead->next);//釋放要刪除的結點
	phead->next = next;//讓哨兵位頭結點指向要刪除的下一個結點
	next->prev = phead;//讓要刪除的下一個結點的prev指向toujied
}

雙向鏈表查找

若我們想要對指定的位置的結點進行相應的改變就得先找到對應的結點，所以我們將查找指定數據封裝成一個函數。方便后續調用。

ListNode* ListFind(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;//讓cur指向哨兵位頭結點的下一個結點
	while (cur != phead)//鏈表循環是否結束的判斷條件
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;//找不到對于的結點
}

雙向鏈表pos前插入結點

推薦使用第二種方法，不容易出錯。

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);//創建一個新的結點
	pos->prev->next = newnode;//pos的前一個結點的next指向新結點
	newnode->prev = pos->prev;//新結點的prev指向pos的前一個結點
	newnode->next = pos;//新結點的next指向pos結點
	pos->prev = newnode;//pos的prev指向新結點
}

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);//創建一個新的結點
	ListNode* posPrev = pos->prev;//定義pos的前一個結點
	posPrev->next = newnode;//讓pos的pos前一個結點的next指向新結點
	newnode->prev = posPrev;//新結點的prev指向pos的前一個結點
	newnode->next = pos;//新結點的next指向pos
	pos->prev = newnode;//pos的prev指向新結點
}

雙向鏈表刪除pos位置的結點

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;//prev為pos的前一個結點
	ListNode* next = pos->next;//next為pos的后一個結點
	free(pos);//釋放posjied
	prev->next = next;
	next->prev = prev;
}

雙向鏈表的銷毀

void ListDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;//指向哨兵位結點的下一個結點
	while (cur != phead)//依次循環找鏈表的每一個結點
	{
		ListNode* next = cur->next;//記錄cur的下一個結點位置
		free(cur);//釋放cur位置的結點
		cur = next;//指向下一個結點
	}
	free(phead);//釋放哨兵位頭結點
}

注意：在寫雙向鏈表的頭插，頭刪，尾插，尾刪時我們可以復用雙向鏈表的任意位置插入和任意位置刪除那兩個函數。那兩個函數就可以完成頭插，頭刪，尾插，尾刪這幾個功能。

順序表和鏈表的區別

順序表優點：

1.物理空間是連續的，方便用下標隨機訪問。

2.CPU高速緩存命中率會更高。

順序表缺點：

1.由于需要物理空間連續，空間不夠需要擴容。擴容本身有一定消耗。其次擴容機制還存在一定的空間浪費。

2.頭部或者中部插入刪除，挪動數據，效率低。O（N)

鏈表優點：

1.任意位置插入刪除數據效率高。O(1)

2.按需申請和釋放空間

鏈表缺點：

不支持下標的隨機訪問。有些算法不適合在它上面運行。如：二分查找、排序等。

到此，相信大家對“C語言怎么實現帶頭雙向循環鏈表”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！