C++帶頭雙向循環(huán)鏈表怎么實(shí)現(xiàn)

這篇文章主要介紹“C++帶頭雙向循環(huán)鏈表怎么實(shí)現(xiàn)”，在日常操作中，相信很多人在C++帶頭雙向循環(huán)鏈表怎么實(shí)現(xiàn)問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”C++帶頭雙向循環(huán)鏈表怎么實(shí)現(xiàn)”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

與單鏈表的區(qū)別

單向/雙向

單向：只有一個(gè)ｎｅｘｔ指針，只指向下一位元素

雙向：有兩個(gè)指針，指向上一位和下一位元素，尋找前一節(jié)點(diǎn)和后一節(jié)點(diǎn)很便利

帶頭/不帶頭

帶頭：在本來(lái)的頭結(jié)點(diǎn)之前還有一個(gè)哨兵衛(wèi)節(jié)點(diǎn)作為頭節(jié)點(diǎn)，它的址域指針指向頭節(jié)點(diǎn)，值域不做使用
不帶頭：沒(méi)有哨兵衛(wèi)頭節(jié)點(diǎn)，在尾刪尾插等問(wèn)題中要考慮頭結(jié)點(diǎn)的情況（局限）

循環(huán)/非循環(huán)

循環(huán)：頭結(jié)點(diǎn)會(huì)與尾節(jié)點(diǎn)相連

非循環(huán)：頭結(jié)點(diǎn)不與尾節(jié)點(diǎn)相連

代碼的實(shí)現(xiàn)

接口

// 創(chuàng)建鏈表（鏈表初始化）
ListNode* ListCreate();
//創(chuàng)建節(jié)點(diǎn)
ListNode* BuyListNode(ListNode* pHead);
// 雙向鏈表銷(xiāo)毀
void ListDestory(ListNode* pHead);
// 雙向鏈表打印
void ListPrint(ListNode* pHead);
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead);
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead);
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(ListNode* pos);

節(jié)點(diǎn)的構(gòu)造

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

初始化鏈表

// 創(chuàng)建鏈表（初始化）
ListNode* ListCreate()
{
	//開(kāi)辟哨兵衛(wèi)頭結(jié)點(diǎn)
	ListNode* plist = (ListNode*)malloc(sizeof(ListNode));
	if (plist == NULL)//失敗打印錯(cuò)誤信息并結(jié)束進(jìn)程
	{
		perror("ListCreat fail:");
		exit(-1);
	}
	plist->next = plist;
	plist->prev = plist;
	return plist;
}

開(kāi)辟節(jié)點(diǎn)

//創(chuàng)建節(jié)點(diǎn)
ListNode* BuyListNode(LTDataType x)
{
	//創(chuàng)建節(jié)點(diǎn)
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)//失敗打印錯(cuò)誤信息并結(jié)束進(jìn)程
	{
		perror("creatnode fail:");
		exit(-1);
	}
	newnode->data = x;
	//初始化結(jié)點(diǎn)
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

銷(xiāo)毀鏈表

注：動(dòng)態(tài)開(kāi)辟的鏈表空間，在不使用后需要將之釋放，避免造成內(nèi)存泄漏

// 雙向鏈表銷(xiāo)毀
void ListDestory(ListNode* pHead)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	ListNode* cur = pHead;
	pHead->prev->next = NULL;
	while (cur!=NULL)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	return;
}

打印鏈表

// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//創(chuàng)建尋址指針
	ListNode* cur = pHead->next;
	//循環(huán)遍歷鏈表
	while (cur != pHead)
	{
		//打印數(shù)據(jù)
		printf("%d->", cur->data);
		//找到下一個(gè)節(jié)點(diǎn)
		cur = cur->next;
	}printf("NULL\n");
	return;
}

尾插鏈表

// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//創(chuàng)建節(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);
	//找到尾節(jié)點(diǎn)
	ListNode* tail=pHead->prev;
	tail->next = newnode;
	newnode->prev = tail;
 
	pHead->prev = newnode;
	newnode->next = pHead;
}

尾刪鏈表

尾刪前記錄前一節(jié)點(diǎn)的地址

// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//只剩哨兵衛(wèi)頭結(jié)點(diǎn)的情況
	if (pHead->prev == pHead)
		return;
	//記錄尾節(jié)點(diǎn)及其前一節(jié)點(diǎn)
	ListNode* tail = pHead->prev;
	ListNode* tailprev = tail->prev;
	//釋放尾節(jié)點(diǎn)
	free(tail);
	//構(gòu)建尾節(jié)點(diǎn)前一節(jié)點(diǎn)與哨兵衛(wèi)頭結(jié)點(diǎn)的關(guān)系
	tailprev->next = pHead;
	pHead->prev = tailprev;
	return;
}

頭插鏈表

頭插前記錄哨兵衛(wèi)頭節(jié)點(diǎn)的下一節(jié)點(diǎn)

// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//創(chuàng)建節(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);
	//記錄哨兵衛(wèi)頭結(jié)點(diǎn)的下一節(jié)點(diǎn)
	ListNode* next = pHead->next;
	//構(gòu)建各節(jié)點(diǎn)之間的關(guān)系
	pHead->next = newnode;
	newnode->prev = pHead;
 
	newnode->next = next;
	next->prev = newnode;
	return;
}

頭刪鏈表

// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//只剩哨兵衛(wèi)頭結(jié)點(diǎn)的情況
	if (pHead->next == pHead)
		return;
	//記錄哨兵衛(wèi)頭結(jié)點(diǎn)下一節(jié)點(diǎn)及其的下一節(jié)點(diǎn)
	ListNode* next = pHead->next;
	ListNode* nextNext = next->next;
	//釋放節(jié)點(diǎn)
	free(next);
	pHead->next = nextNext;
	nextNext->prev = pHead;
	return;
}

查找鏈表

// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//創(chuàng)建尋址指針
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		//比較數(shù)據(jù)
		if (cur->data == x)
			return cur;
		//找到下一個(gè)節(jié)點(diǎn)
		cur = cur->next;
	}
	//沒(méi)找到則返回NULL
	return NULL;
}

鏈表pos位置的刪除

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
	return;
}

到此，關(guān)于“C++帶頭雙向循環(huán)鏈表怎么實(shí)現(xiàn)”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！