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

學無先后，達者為師

網站首頁 編程語言 正文

C語言超詳細講解雙向帶頭循環鏈表_C 語言

作者：[Pokemon]大貓貓 ? 更新時間： 2023-05-08 編程語言

在上一篇所講述的單鏈表中，存在一些缺陷：

1、在進行尾插和尾刪時，需要遍歷鏈表找到尾結點

2、在進行中間插入和刪除時，也需要先遍歷鏈表找到前一個結點

對于這些缺陷，可以采用一種結構更為復雜的鏈表 雙向帶頭循環鏈表

雙向帶頭循環鏈表結構雖然復雜，但在鏈表的操作上帶來了很大的優勢

一、雙向帶頭循環鏈表的結構

//存儲數據的類型，這里以 int 來舉例
typedef int LTDataType;
//結點的類型
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

二、雙向帶頭循環鏈表的函數接口

1. 申請結點

在插入等操作時需要申請結點，為了避免麻煩重復的操作，這里將申請結點封裝為一個函數

申請結點函數如下：

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		//開辟空間失敗，打印錯誤信息
		perror("malloc");

		//結束程序
		exit(-1);
	}
	newnode->data = x;
	newnode->prev = newnode->next = NULL;
	return newnode;
}

2. 初識化

在雙向帶頭循環鏈表中，即使沒有存儲數據也 至少會包含一個哨兵位的頭結點

初始化函數如下：

LTNode* InitLT()
{
	//申請頭結點，頭結點的數據存什么無關緊要
	LTNode* phead = BuyLTNode(-1);
	//改變指針指向，構成循環
	phead->prev = phead->next = phead;
	return phead;
}

3. 打印

為了驗證插入、刪除等得到的結果是否正確，提供打印函數，這里數據類型以 int 為例，當讀者采用的類型不同時，自行更改函數即可

打印函數如下：

void LTPrint(LTNode* phead)
{
	//鏈表不能為空
	assert(phead);
	LTNode* cur = phead->next;
	printf("head->");
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("head\n");
}

4. 尾插尾刪

尾插：在鏈表的最后一個結點之后插入結點

尾插函數如下：

void LTPushBack(LTNode* phead, LTDataType x)
{
	//鏈表不能為空
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	//找到尾結點
	LTNode* tail = phead->prev;
	//改變指針指向
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

尾刪：刪除鏈表最后一個結點

尾刪函數如下：

void LTPopBack(LTNode* phead)
{
	assert(phead);	//鏈表不能為空
	assert(phead->next != phead);	//空鏈表不能刪
	//找尾結點及尾結點的前一個結點
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//改變指針指向
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
}

5. 頭插頭刪

頭插： 在第一個結點之前插入新結點

頭插函數如下：

void LTPushFront(LTNode* phead, LTDataType x)
{
	//鏈表不能為空
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	//找到頭結點后的第一個結點
	LTNode* first = phead->next;
	//改變指針指向
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

頭刪：刪除鏈表的第一個結點

頭刪函數如下：

void LTPopFront(LTNode* phead)
{
	assert(phead);	//鏈表不能為空
	assert(phead->next != phead);	//空鏈表不能刪
	//找到頭結點后的第一個和第二個結點
	LTNode* first = phead->next;
	LTNode* second = first->next;
	//改變指針指向
	phead->next = second;
	second->prev = phead;
	free(first);
}

6. 查找

查找：如果數據存在，返回該數據結點的指針，不存在返回 NULL

查找函數如下：

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	//鏈表不能為空
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x) return cur;
		cur = cur->next;
	}
	return NULL;
}

7. 中間插入和刪除

中間插入：通過查找函數 LTFind 獲得指向結點的指針 pos，在 pos 指向的 結點之前 插入結點

在 pos 之前插入結點函數如下：

void LTInsert(LTNode* pos, LTDataType x)
{
	//pos 不能為空
	assert(pos);
	LTNode* newnode = BuyLTNode(x);
	//找到 pos 的前一個結點
	LTNode* posPrev = pos->prev;
	//改變指針指向
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

在調用中間插入函數 LTInsert 時

  • 如果在鏈表頭結點之前插入數據，便和尾插函數的功能一樣
  • 如果在鏈表頭結點之后插入數據，便和頭插函數的功能一樣

因此在尾插和頭插函數的實現中可以直接調用中間插入函數 LTInsert

尾插和頭插函數更改如下：

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	//鏈表不能為空
	assert(phead);
	LTInsert(phead, x);
}
//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{
	//鏈表不能為空
	assert(phead);
	LTInsert(phead->next, x);
}

中間刪除：通過查找函數 LTFind 獲得指向結點的指針 pos，刪除 pos 指向的結點

刪除 pos 指向的結點函數如下：

void LTErase(LTNode* pos)
{
	//pos 不能為空
	assert(pos);
	//找到 pos 的前一個和后一個結點
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	//改變指針指向
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

在調用中間刪除函數 LTErase 時

  • 如果刪除鏈表頭結點的前一個結點，便和尾刪函數的功能一樣
  • 如果刪除鏈表頭結點的后一個結點，便和頭刪函數的功能一樣

因此在尾刪和頭刪函數的實現中可以直接調用中間刪除函數 LTErase

尾刪和頭刪函數更改如下：

//尾刪
void LTPopBack(LTNode* phead)
{
	assert(phead);	//鏈表不能為空
	assert(phead->next != phead);	//空鏈表不能刪
	LTErase(phead->prev);
}
//頭刪
void LTPopFront(LTNode* phead)
{
	assert(phead);	//鏈表不能為空
	assert(phead->next != phead);	//空鏈表不能刪
	LTErase(phead->next);
}

8. 判空及求鏈表長度

判空：判斷鏈表是否為空

判空函數如下：

bool LTEmpty(LTNode* phead)
{
	//鏈表不能為空
	assert(phead);
	return phead->next == phead;
}

鏈表長度：鏈表有效數據個數

鏈表長度函數如下：

size_t LTSize(LTNode* phead)
{
	//鏈表不能為空
	assert(phead);
	size_t size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

9. 銷毀單鏈表

在鏈表中，存儲數據的結點是由自己開辟的，當不使用鏈表時，應將其銷毀

銷毀鏈表函數如下：

void LTDestroy(LTNode* phead)
{
	//鏈表不能為空
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* curNext = cur->next;
		free(cur);
		cur = curNext;
	}
	free(phead);
}

原文鏈接：https://blog.csdn.net/qq_70793373/article/details/128361715

欄目分類
最近更新