快捷導(dǎo)航

C語言類的雙向鏈表詳解

更新時(shí)間：2022年01月18日 10:08:02 作者：weixin_52079669

大家好，本篇文章主要講的是C語言類的雙向鏈表詳解，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下

前言

鏈表（linked list)是一種這樣的數(shù)據(jù)結(jié)構(gòu)，其中的各對象按線性排列。數(shù)組的線性順序是由數(shù)組下標(biāo)決定的，然而于數(shù)組不同的是，鏈表的各順序是由鏈表中的指針決定的。

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。

雙向鏈表的定義

雙鏈表（doubly linked list)的每一個(gè)元素都是一個(gè)對象，每一個(gè)對象都有一個(gè)數(shù)據(jù)域和兩個(gè)指針front和tail。對象中還可以包含其他輔助數(shù)據(jù)。設(shè)L為鏈表的一個(gè)元素，L.front指向他在鏈表中的后繼元素，L.tail指向他的前繼元素。

我們可以定義一個(gè)結(jié)構(gòu)體封裝這些數(shù)據(jù)

typedef struct Node
{
	int data;
	struct Node* front;
	struct Node* tail;
}NODE, * LPNODE;

雙向鏈表的創(chuàng)建

在C++中，我們以類的形式封裝了雙向鏈表。在類中，我們定義了兩個(gè)指針，一個(gè)是指向鏈表的頭部 frontNode，一個(gè)是指向了鏈表的尾部 tailNode，另外我們還加入了 curSize屬性，記錄節(jié)點(diǎn)的個(gè)數(shù)。在對象創(chuàng)建的過程就是鏈表創(chuàng)建的過程，我們只需要在類的構(gòu)造函數(shù)中初始化參數(shù)即可。

class duplexHead {
public:
	duplexHead() {
		frontNode = NULL;
		tailNode = NULL;
		curSize = 0;
	}
 
	LPNODE createNode(int data);
	LPNODE seachNode(int data);
	void push_front(int data);
	void push_back(int data);
	void push_appoin(int posData, int data);
	void pop_front();
	void pop_back();
	void pop_appoin(int posData);
	void printByFront();
	void printByTail();
 
protected:
 
	LPNODE frontNode;
	LPNODE tailNode;
	int curSize;
 
};

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

在上面，我們已經(jīng)知道雙向鏈表的單體長啥樣了，我們只需要給他的單體分配空間然后初始化他的參數(shù)即可。

LPNODE duplexHead::createNode(int data)
{
	LPNODE newNode = new NODE;
	assert(newNode);
	newNode->front = nullptr;
	newNode->tail = nullptr;
	newNode->data = data;
	return newNode;
}

雙向鏈表節(jié)點(diǎn)查找

鏈表的查找我們可以定義一個(gè)函數(shù)LPNODE seachNode（int data)，當(dāng)滿足查找條件時(shí)，我們就返回當(dāng)前節(jié)點(diǎn)的鏈表。在實(shí)際操作過程中，鏈表的數(shù)據(jù)域可能會(huì)有多個(gè)數(shù)據(jù)，可能要比較int 類型，可能要比較string類型等多種變化，這是我們可以在參數(shù)列表預(yù)留一個(gè)函數(shù)指針 (int) (*comparData)(LPNODE data),以應(yīng)對多種需求。當(dāng)然，在這里為了演示方便，我們就用一個(gè)int 類型的數(shù)據(jù)代替了。

 
LPNODE duplexHead::seachNode(int data)
{
	if (!curSize)
	{
		printf("鏈表為空，無法查找");
		return;
	}
	LPNODE preNode = frontNode;
	LPNODE curNode = frontNode;
	while (curNode != NULL && curNode->data != data)
	{
		preNode = curNode;
		curNode = preNode->tail;
	}
	if (curNode == nullptr)
	{
		printf("鏈表中沒有該數(shù)據(jù)");
		return nullptr;
	}
 
	return curNode;
 
}

雙向鏈表的插入

插入節(jié)點(diǎn)，我們分為頭部插入和尾部插入以及指定位置插入。而這三種插入，都可分為3步。

（1）創(chuàng)建新節(jié)點(diǎn)

（2）找到插入位置

（3）插入

我們就以制定位置插入為例，如圖所示，我們只需把原來相連的兩個(gè)節(jié)點(diǎn)斷開，然后再分別用指針拼接起來，當(dāng)然我們也可以調(diào)用我們的seachNode來查找位置，這樣就更方便一些了。

void duplexHead::push_appoin(int posData, int data)
{
 
	if (curSize == 0)
		return;
	if (frontNode->data == posData)
	{
		push_front(data);
	}
	else
	{
		LPNODE preNode = frontNode;
		LPNODE curNode = frontNode;
		while (curNode != NULL && curNode->data != posData)
		{
			preNode = curNode;
			curNode = preNode->tail;
		}
		if (curNode == NULL)
		{
			printf("未找到指定位置，無法插入！\n");
		}
		else
		{
			LPNODE newNode = createNode(data);
			preNode->tail = newNode;
			newNode->tail = curNode;
			curNode->front = newNode;
			newNode->front = preNode;
			curSize++;
		}
	}
}

雙向鏈表的節(jié)點(diǎn)刪除

刪除節(jié)點(diǎn)我們也可以分為頭部刪除，尾部刪除，指定數(shù)據(jù)刪除。他與插入節(jié)點(diǎn)幾乎是一樣的

（1）找到刪除位置

（2）刪除

我們就以指定數(shù)據(jù)刪除為例，我們通過while或者seachNode來查找到要?jiǎng)h除的節(jié)點(diǎn)，然后把他的front 指向的位置和tail指向的位置記住，就可以直接刪除節(jié)點(diǎn)了。刪除完了節(jié)點(diǎn)要記得把前后段的鏈表連接上即可。

 
void duplexHead::pop_appoin(int posData)
{
	if (frontNode == NULL || curSize == 0)
	{
		printf("鏈表為空無法刪除！");
		return;
	}
	if (frontNode->data == posData)
	{
		pop_front();
		return;
	}
	LPNODE preNode = frontNode;
	LPNODE curNode = frontNode;
	while (curNode != NULL && curNode->data != posData)
	{
		preNode = curNode;
		curNode = preNode->tail;
	}
	if (curNode == NULL)
	{
		printf("未找到指定位置無法刪除！\n");
	}
	else
	{
		if (tailNode == curNode)
		{
			pop_back();
		}
		else
		{
			preNode->tail = curNode->tail;
			//curNode->tail是不是不空
			//當(dāng)刪除的表尾時(shí)候，curNode->tail等于空
			curNode->tail->front = preNode;
			free(curNode);
			curNode = NULL;
			curSize--;
		}
	}
}

雙向鏈表的刪除

于雙向鏈表的創(chuàng)建一樣，我們可以把雙向鏈表的刪除放在析構(gòu)函數(shù)中，實(shí)現(xiàn)創(chuàng)建和刪除自動(dòng)化，當(dāng)對象被創(chuàng)建，雙向鏈表就被創(chuàng)建，當(dāng)對象消亡，雙向鏈表就刪除了。

duplexHead::~duplexHead()
{
	if (!frontNode)return;
	LPNODE pmove ;
	
 
	while (!pmove)
	{
		pmove = frontNode->tail;
		delete frontNode->tail;
		frontNode = pmove;
	}
 
}