（C語言版）連結清單（四）——實作雙向循環連結清單建立、插入、删除、釋放記憶體等簡單操作

雙向循環連結清單是基于雙向連結清單的基礎上實作的，和雙向連結清單的操作差不多，唯一的差別就是它是個循環的連結清單，通過每個節點的兩個指針把它們扣在一起組成一個環狀。是以呢，每個節點都有前驅節點和後繼節點（包括頭節點和尾節點）這是和雙向連結清單不同的地方。我們看下雙向循環連結清單的示意圖（我在網上找了張圖檔，自己畫的實在難看，有時間真的要去學下怎麼畫圖了，然後可以寫出更好的部落格）：

在程式的編寫方面呢，雙向循環連結清單有點向前面知識的組合，雙向循環連結清單在“雙向”方面和雙向連結清單一樣，在“循環方面”和單向循環連結清單一樣。以前的知識消化了呢，這個雙向循環連結清單也就簡單了。上面這個圖比較形象的展現出了雙向循環連結清單的含義：簡單說呢，就是目前節點的一個指針指向前置節點一個指針指向後繼節點，每個節點都重複這樣，就形成了一個環了。

DbCcLinkList.h 頭檔案——包含了節點結構的定義和連結清單相關操作函數的聲明

#ifndef DOUBLE_CIRCULAR_LINKED_LIST_H
#define DOUBLE_CIRCULAR_LINKED_LIST_H

typedef struct Node
{
	int data;
	struct Node *pNext;
	struct Node *pPre;
}NODE, *pNODE;

//建立雙向循環連結清單
pNODE CreateDbCcLinkList(void);

//列印連結清單
void TraverseDbCcLinkList(pNODE pHead);

//判斷連結清單是否為空
int IsEmptyDbCcLinkList(pNODE pHead);

//計算連結清單的長度
int GetLengthDbCcLinkList(pNODE pHead);

//向連結清單中插入節點
int InsertEleDbCcLinkList(pNODE pHead, int pos, int data);

//從連結清單中删除節點
int DeleteEleDbCcLinkList(pNODE pHead, int pos);

//删除整個連結清單，釋放記憶體
void FreeMemory(pNODE *ppHead);

#endif

DbCcLinkList.cpp 雙向循環連結清單的源檔案——包含了連結清單相關操作函數的定義

（1）這部分是用來建立連結清單的，雙向循環連結清單每插入一個節點就要控制4個指針，第一，插入位置的上一個節點有一個指針，它要指向插入節點；第二，插入的節點有兩個指針，一個指向上一個節點，一個指向下一個節點；第三，插入位置的下一個節點有一個指針，它是指着插入節點的。寫程式的關鍵也就是控制好這四個指針，不要弄錯了，要不然會有奇怪的結果（程式出不來結果，無線循環等）

#include <stdio.h>
#include <stdlib.h>
#include "DbCcLinkList.h"

//建立雙向循環連結清單
pNODE CreateDbCcLinkList(void)
{
	int i, length = 0, data = 0;
	pNODE p_new = NULL, pTail = NULL;
	pNODE pHead = (pNODE)malloc(sizeof(NODE));

	if (NULL == pHead)
	{
		printf("記憶體配置設定失敗！\n");
		exit(EXIT_FAILURE);
	}
	pHead->data = 0;
	pHead->pNext = pHead;
	pHead->pPre = pHead;
	pTail = pHead;

	printf("請輸入想要建立連結清單的長度：");
	scanf("%d", &length);

	for (i=1; i<length+1; i++)
	{
		p_new = (pNODE)malloc(sizeof(NODE));

		if (NULL == p_new)
		{
			printf("記憶體配置設定失敗！\n");
			exit(EXIT_FAILURE);
		}

		printf("請輸入第%d個節點元素值：", i);
		scanf("%d", &data);

		p_new->data = data;
		p_new->pPre = pTail;
		p_new->pNext = pHead;
		pTail->pNext = p_new;
		pHead->pPre = p_new;
		pTail = p_new;
	}
	return pHead;
}

（2）這部分是獲得雙向連結清單的資訊，和單向循環連結清單一樣，連結清單結束的限制條件是判斷是否等于頭結點。意思就是從頭節點的下一個節點開始如果又到了頭節點說明已經周遊一圈了。

//列印連結清單
void TraverseDbCcLinkList(pNODE pHead)
{
	pNODE pt = pHead->pNext;

	printf("連結清單列印如：");
	while (pt != pHead)
	{
		printf("%d ", pt->data);
		pt = pt->pNext;
	}
	putchar('\n');
}

//判斷連結清單是否為空
int IsEmptyDbCcLinkList(pNODE pHead)
{
	pNODE pt = pHead->pNext;

	if (pt == pHead)
		return 1;
	else
		return 0;
}

//計算連結清單的長度
int GetLengthDbCcLinkList(pNODE pHead)
{
	int length = 0;
	pNODE pt = pHead->pNext;

	while (pt != pHead)
	{
		length++;
		pt = pt->pNext;
	}
	return length;
}

（3）這部分是雙向連結清單的插入、删除節點操作，但是它不需要和雙向連結清單一樣判斷最後一個節點是否為空（因為此時要用到節點的指針），雙向循環連結清單不存在這樣的情況，這是由于它不光是雙向的，而且是循環的，是以每個節點都不可能為空。

//向連結清單中插入節點
int InsertEleDbCcLinkList(pNODE pHead, int pos, int data)
{
	pNODE p_new = NULL, pt = NULL;
	if (pos > 0 && pos < GetLengthDbCcLinkList(pHead) + 2)
	{
		p_new = (pNODE)malloc(sizeof(NODE));

		if (NULL == p_new)
		{
			printf("記憶體配置設定失敗！\n");
			exit(EXIT_FAILURE);
		}

		while (1)
		{
			pos--;
			if (0 == pos)
				break;
			pHead = pHead->pNext;
		}
		
		p_new->data = data;
		pt = pHead->pNext;
		p_new->pNext = pt;
		p_new->pPre = pHead;
		pHead->pNext = p_new;
		pt->pPre = p_new;
		
		return 1;
	}
	else
		return 0;
}

//從連結清單中删除節點
int	DeleteEleDbCcLinkList(pNODE pHead, int pos)
{
	pNODE pt = NULL;
	if (pos > 0 && pos < GetLengthDbCcLinkList(pHead) + 1)
	{
		while (1)
		{
			pos--;
			if (0 == pos)
				break;
			pHead = pHead->pNext;
		}
		pt = pHead->pNext->pNext;
		free(pHead->pNext);
		pHead->pNext = pt;
		pt->pPre = pHead;

		return 1;
	}
	else
		return 0;	
}

（4）這是釋放記憶體操作，和上面講的一樣，不需要判斷最後一個節點是否為空，每次釋放一個節點的記憶體的以後它還是保持環狀的結構，是以沒有節點為空。

//删除整個連結清單，釋放記憶體空間
void FreeMemory(pNODE *ppHead)
{
	pNODE pt = NULL;
	while (*ppHead != NULL)
	{
		pt = (*ppHead)->pNext->pNext;


		if ((*ppHead)->pNext == *ppHead)
		{
			free(*ppHead);
			*ppHead = NULL;
		}
		else
		{
			free((*ppHead)->pNext);
			(*ppHead)->pNext = pt;
			pt->pPre = *ppHead;
		}
	}
}

maincpp 測試程式——通過簡單的互動界面判斷函數的功能是否正确

#include <stdio.h>
#include <stdlib.h>
#include "DbCcLinkList.h"

int main(void)
{
	int flag = 0, length = 0;
	int position = 0, value = 0;
	pNODE head = NULL;

	head = CreateDbCcLinkList();
	
	flag = IsEmptyDbCcLinkList(head);
	if (flag)
		printf("雙向循環連結清單為空！\n");
	else
	{
		length = GetLengthDbCcLinkList(head);
		printf("雙向循環連結清單的長度為：%d\n", length);
		TraverseDbCcLinkList(head);
	}
	
	printf("請輸入要插入節點的位置和元素值(兩個數用空格隔開)：");
	scanf("%d %d", &position, &value);
	flag = InsertEleDbCcLinkList(head, position, value);
	if (flag)
	{
		printf("插入節點成功！\n");
		TraverseDbCcLinkList(head);
	}	
	else
		printf("插入節點失敗！\n");
	
	flag = IsEmptyDbCcLinkList(head);
	if (flag)
		printf("雙向循環連結清單為空，不能進行删除操作！\n");
	else
	{
		printf("請輸入要删除節點的位置：");
		scanf("%d", &position);
		flag = DeleteEleDbCcLinkList(head, position);
		if (flag)
		{
			printf("删除節點成功！\n");
			TraverseDbCcLinkList(head);
		}	
		else
			printf("删除節點失敗！\n");
	}
		
	FreeMemory(&head);
	if (NULL == head)
		printf("已成功删除雙向循環連結清單，釋放記憶體完成！\n");
	else
		printf("删除雙向循環連結清單失敗，釋放記憶體未完成！\n");

	return 0;
}

PS：到這裡為止，連結清單的知識就寫到這裡了，後面開始就是隊列和棧了。其實線性表方面的知識都大同小異，隻要原理清楚之後，它的形式的變化可以是多鐘多樣的，當然本人水準有限，希望能和同道之人繼續深入探讨，共同進步。

（C語言版）連結清單（四）——實作雙向循環連結清單建立、插入、删除、釋放記憶體等簡單操作

繼續閱讀

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

CRC32和CRC8校驗代碼，C語言版

241 Different Ways to Add Parentheses（C代碼版）

[轉]ISUP信令的IAM消息詳細内容

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

結構體：typedef與struct的差別

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希