日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言類的雙向鏈表詳解_C 語言

作者：weixin_52079669 ? 更新時間： 2022-03-31 編程語言

前言

鏈表（linked list)是一種這樣的數據結構，其中的各對象按線性排列。數組的線性順序是由數組下標決定的，然而于數組不同的是，鏈表的各順序是由鏈表中的指針決定的。

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環鏈表。

雙向鏈表的定義

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

我們可以定義一個結構體封裝這些數據

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

雙向鏈表的創建

在C++中，我們以類的形式封裝了雙向鏈表。在類中，我們定義了兩個指針，一個是指向鏈表的頭部?frontNode，一個是指向了鏈表的尾部?tailNode，另外我們還加入了?curSize屬性，記錄節點的個數。在對象創建的過程就是鏈表創建的過程，我們只需要在類的構造函數中初始化參數即可。

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;
 
};

節點的創建

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

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

雙向鏈表節點查找

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

 
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("鏈表中沒有該數據");
		return nullptr;
	}
 
	return curNode;
 
}

雙向鏈表的插入

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

（1）創建新節點

（2）找到插入位置

（3）插入

我們就以制定位置插入為例，如圖所示，我們只需把原來相連的兩個節點斷開，然后再分別用指針拼接起來，當然我們也可以調用我們的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++;
		}
	}
}

雙向鏈表的節點刪除

刪除節點我們也可以分為頭部刪除，尾部刪除，指定數據刪除。他與插入節點幾乎是一樣的

（1）找到刪除位置

（2）刪除

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

 
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是不是不空
			//當刪除的表尾時候，curNode->tail等于空
			curNode->tail->front = preNode;
			free(curNode);
			curNode = NULL;
			curSize--;
		}
	}
}

雙向鏈表的刪除

于雙向鏈表的創建一樣，我們可以把雙向鏈表的刪除放在析構函數中，實現創建和刪除自動化，當對象被創建，雙向鏈表就被創建，當對象消亡，雙向鏈表就刪除了。

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

總結

原文鏈接：https://blog.csdn.net/weixin_52079669/article/details/122525114

欄目分類
最近更新