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

學無先后，達者為師

網站首頁 編程語言 正文

C語言帶頭雙向循環鏈表的示例代碼_C 語言

作者：南猿北者 ? 更新時間： 2022-12-08 編程語言

前言

對于鏈表來說，不只有單鏈表這一個品種；

鏈表有很多種形態

按方向分：單向、雙向

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

按循環：循環、不循環

1、單向或則雙向：

2、帶頭或者不帶頭：

3、循環或者不循環：

組合排列一下的話，鏈表一共有8種形態！！！

今天我們就來學習一下結構最復雜的帶頭雙向循環鏈表！！！；

雖然名字聽上去比較復雜，但是實現起來比單鏈表（全名：不帶頭、不循環、單向鏈表）更加簡單，也不需要過多考慮特殊情況；
?

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

結構分析

首先鏈表的頭節點是不存儲有效數據的（該節點被稱為哨兵位），其次我們只需要知道改頭節點的指針就能找到整個鏈表，并且便于對整個鏈表進行維護；

當然既然是雙向的嘛，那節點一定有個指針域指向前一個節點，另一個指針域指向后一個節點；

那么我們的單個節點的數據結構就是：

現在我們定義了一個plist指針用來維護整個鏈表，根據上面說的plist就應該用來存儲哨兵位的頭節點的指針，那么如何表示鏈表為NULL的情況？

鏈表為空：

就是:

head->next=head;

head->prev=head;

鏈表的基本操作實現

創建節點

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

鏈表銷毀

// 雙向鏈表銷毀
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;
}

鏈表尾刪

由于是循環的，哨兵位的前一個節點就是尾節點，同時尾節點的前一個節點我們也不用遍歷，可以很輕松的拿到：

// 雙向鏈表尾刪
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了，就沒辦法找了
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}

鏈表pos位置前面去插入

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

刪除pos位置

// 雙向鏈表刪除pos位置的節點
void ListErase(ListNode* pos)
{
	assert(pos);//由于參數限制，我們無法判斷表是否為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;
}

代碼復用

我們上面既然實現了在pos位置之前插入和刪除pos位置的數據；

那么：

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

那么實際上我們只要實現ListInsert、ListErase這兩個接口就能快速實現出帶頭雙向循環鏈表了；

總代碼及頭文件

頭文件的包含：

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

// 創建返回鏈表的頭結點.
ListNode* ListCreate(LTDataType x);
//初始化哨兵位的頭節點;
void InitDummyHead(ListNode* pHead);
// 雙向鏈表銷毀
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的前面進行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節點
void ListErase(ListNode* pos);
//判斷鏈表是否為NULL
bool is_Empty(ListNode* pHead);

功能代碼實現：

#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;
}
// 雙向鏈表銷毀
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);//函數復用
}
// 雙向鏈表尾刪
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);//函數復用
}
// 雙向鏈表頭插
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);//函數復用
}
// 雙向鏈表頭刪
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);//函數復用
}
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	assert(!is_Empty(pHead));//表都為NULL了，就沒辦法找了
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//pos不能為NULL,由于參數限制我們無法對pos判斷是否為哨兵位頭節點，因此我們假設pos傳的都是合法指針和NULL
	ListNode* NewNode = ListCreate(x);
	ListNode* prev = pos->prev;
	NewNode->next = pos;
	pos->prev = NewNode;
	prev->next = NewNode;
	NewNode->prev = prev;
}
// 雙向鏈表刪除pos位置的節點
void ListErase(ListNode* pos)
{
	assert(pos);//由于參數限制，我們無法判斷表是否為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;
}

原文鏈接：https://blog.csdn.net/qq_62106937/article/details/127741856

欄目分類
最近更新