C語(yǔ)言帶頭雙向循環(huán)鏈表的示例代碼

更新時(shí)間：2022年11月08日 08:40:12 作者：南猿北者

這篇文章主要介紹了如何利用C語(yǔ)言實(shí)現(xiàn)帶頭雙向循環(huán)鏈表，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

前言

對(duì)于鏈表來(lái)說(shuō)，不只有單鏈表這一個(gè)品種；

鏈表有很多種形態(tài)

按方向分：?jiǎn)蜗颉㈦p向

按帶不帶頭：帶頭、不帶頭

按循環(huán)：循環(huán)、不循環(huán)

1、單向或則雙向：

2、帶頭或者不帶頭：

3、循環(huán)或者不循環(huán)：

組合排列一下的話，鏈表一共有8種形態(tài)?。。?/p>

今天我們就來(lái)學(xué)習(xí)一下結(jié)構(gòu)最復(fù)雜的帶頭雙向循環(huán)鏈表?。。?；

雖然名字聽(tīng)上去比較復(fù)雜，但是實(shí)現(xiàn)起來(lái)比單鏈表（全名：不帶頭、不循環(huán)、單向鏈表）更加簡(jiǎn)單，也不需要過(guò)多考慮特殊情況；

兩種鏈表的比較：（上面是單鏈表，下面是帶頭雙向循環(huán)鏈表）

結(jié)構(gòu)分析

首先鏈表的頭節(jié)點(diǎn)是不存儲(chǔ)有效數(shù)據(jù)的（該節(jié)點(diǎn)被稱(chēng)為哨兵位），其次我們只需要知道改頭節(jié)點(diǎn)的指針就能找到整個(gè)鏈表，并且便于對(duì)整個(gè)鏈表進(jìn)行維護(hù)；

當(dāng)然既然是雙向的嘛，那節(jié)點(diǎn)一定有個(gè)指針域指向前一個(gè)節(jié)點(diǎn)，另一個(gè)指針域指向后一個(gè)節(jié)點(diǎn)；

那么我們的單個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)就是：

現(xiàn)在我們定義了一個(gè)plist指針用來(lái)維護(hù)整個(gè)鏈表，根據(jù)上面說(shuō)的plist就應(yīng)該用來(lái)存儲(chǔ)哨兵位的頭節(jié)點(diǎn)的指針，那么如何表示鏈表為NULL的情況？

鏈表為空：

就是:

head->next=head;

head->prev=head;

鏈表的基本操作實(shí)現(xiàn)

創(chuàng)建節(jié)點(diǎn)

ListNode* ListCreate(LTDataType x)
{
	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
	if (!NewNode)
		exit(-1);
	NewNode->val = x;
	NewNode->prev = NULL;
	NewNode->next = NULL;
	return NewNode;
}

我們?cè)趧?chuàng)建節(jié)點(diǎn)的時(shí)候就一起將數(shù)據(jù)域初始化，方標(biāo)后續(xù)操作；

初始化鏈表

void InitDummyHead(ListNode* pHead)
{
	assert(pHead);
	pHead->prev = pHead;
	pHead->next = pHead;
}

鏈表銷(xiāo)毀

// 雙向鏈表銷(xiāo)毀
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	ListNode* next = NULL;
	while (cur!=pHead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	free(cur);
}

實(shí)現(xiàn)思路：

打印鏈表

除了哨兵位的節(jié)點(diǎn)存到是無(wú)效數(shù)據(jù)不打印外，其他節(jié)點(diǎn)的數(shù)據(jù)都要打?。?/p>

// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		printf("%d->",cur->val);
		cur = next;
	}
	printf("NULL\n");
}

鏈表尾插

該鏈表的尾插，比單鏈表的尾插簡(jiǎn)單太多了，不用遍歷找尾：

// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
    ListNode* NewNode = ListCreate(x);
	ListNode* tail = pHead->prev;
	tail->next = NewNode;
	NewNode->prev = tail;
	pHead->prev = NewNode;
	NewNode->next = pHead;
}

鏈表尾刪

由于是循環(huán)的，哨兵位的前一個(gè)節(jié)點(diǎn)就是尾節(jié)點(diǎn)，同時(shí)尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)我們也不用遍歷，可以很輕松的拿到：

// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	ListNode* tail = pHead->prev;
	ListNode* prev = tail->prev;
	ListNode* next = pHead;
	free(tail);
	prev->next = next;
	next->prev = prev;
}

鏈表頭插

// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* NewNode = ListCreate(x);
	prev->next = NewNode;
	NewNode->prev = prev;
	NewNode->next = cur;
	cur->prev = NewNode;
}

鏈表頭刪

// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* next = cur->next;
	free(cur);
	prev->next = next;
	next->prev = prev;
}

鏈表查找

// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	assert(!is_Empty(pHead));//表都為NULL了，就沒(méi)辦法找了
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}

鏈表pos位置前面去插入

// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//pos不能為NULL,由于參數(shù)限制我們無(wú)法對(duì)pos判斷是否為哨兵位頭節(jié)點(diǎn)，因此我們假設(shè)pos傳的都是合法指針和NULL
	ListNode* NewNode = ListCreate(x);
	ListNode* prev = pos->prev;
	NewNode->next = pos;
	pos->prev = NewNode;
	prev->next = NewNode;
	NewNode->prev = prev;
}

刪除pos位置

// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(ListNode* pos)
{
	assert(pos);//由于參數(shù)限制，我們無(wú)法判斷表是否為NULL；
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}

鏈表判空

//判斷鏈表是否為NULL
bool is_Empty(ListNode* pHead)
{
	assert(pHead);
	return pHead == pHead->prev;
}

代碼復(fù)用

我們上面既然實(shí)現(xiàn)了在pos位置之前插入和刪除pos位置的數(shù)據(jù)；

那么：

ListInsert(plist,x);//相當(dāng)于尾插
ListInsert(plist->next, x);//相當(dāng)于頭插
ListErase(plist->next);//相當(dāng)于頭刪
ListErase(plist->prev);//相當(dāng)于尾刪;

那么實(shí)際上我們只要實(shí)現(xiàn)ListInsert、ListErase這兩個(gè)接口就能快速實(shí)現(xiàn)出帶頭雙向循環(huán)鏈表了；

總代碼及頭文件

頭文件的包含：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 帶頭+雙向+循環(huán)鏈表增刪查改實(shí)現(xiàn)
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType val;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 創(chuàng)建返回鏈表的頭結(jié)點(diǎn).
ListNode* ListCreate(LTDataType x);
//初始化哨兵位的頭節(jié)點(diǎn);
void InitDummyHead(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);
//判斷鏈表是否為NULL
bool is_Empty(ListNode* pHead);

功能代碼實(shí)現(xiàn)：

#include"DList.h"
ListNode* ListCreate(LTDataType x)
{
	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
	if (!NewNode)
		exit(-1);
	NewNode->val = x;
	NewNode->prev = NULL;
	NewNode->next = NULL;
	return NewNode;
}
void InitDummyHead(ListNode* pHead)
{
	assert(pHead);
	pHead->prev = pHead;
	pHead->next = pHead;
}
// 雙向鏈表銷(xiāo)毀
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	ListNode* next = NULL;
	while (cur!=pHead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	free(cur);
}
// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		printf("%d->",cur->val);
		cur = next;
	}
	printf("NULL\n");
}
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	/*ListNode* NewNode = ListCreate(x);
	ListNode* tail = pHead->prev;
	tail->next = NewNode;
	NewNode->prev = tail;
	pHead->prev = NewNode;
	NewNode->next = pHead;*/
	ListInsert(pHead,x);//函數(shù)復(fù)用
}
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	/*ListNode* tail = pHead->prev;
	ListNode* prev = tail->prev;
	ListNode* next = pHead;
	free(tail);
	prev->next = next;
	next->prev = prev;*/
	ListErase(pHead->prev);//函數(shù)復(fù)用
}
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	/*ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* NewNode = ListCreate(x);
	prev->next = NewNode;
	NewNode->prev = prev;
	NewNode->next = cur;
	cur->prev = NewNode;*/
	ListInsert(pHead->next,x);//函數(shù)復(fù)用
}
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	/*ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* next = cur->next;
	free(cur);
	prev->next = next;
	next->prev = prev;*/
	ListErase(pHead->next);//函數(shù)復(fù)用
}
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	assert(!is_Empty(pHead));//表都為NULL了，就沒(méi)辦法找了
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//pos不能為NULL,由于參數(shù)限制我們無(wú)法對(duì)pos判斷是否為哨兵位頭節(jié)點(diǎn)，因此我們假設(shè)pos傳的都是合法指針和NULL
	ListNode* NewNode = ListCreate(x);
	ListNode* prev = pos->prev;
	NewNode->next = pos;
	pos->prev = NewNode;
	prev->next = NewNode;
	NewNode->prev = prev;
}
// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(ListNode* pos)
{
	assert(pos);//由于參數(shù)限制，我們無(wú)法判斷表是否為NULL；
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}
//判斷鏈表是否為NULL
bool is_Empty(ListNode* pHead)
{
	assert(pHead);
	return pHead == pHead->prev;
}

以上就是C語(yǔ)言帶頭雙向循環(huán)鏈表的示例代碼的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言帶頭雙向循環(huán)鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: