IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【数据结构】带头双向循环链表的实现 -> 正文阅读

[数据结构与算法]【数据结构】带头双向循环链表的实现

带头双向循环链表

1、带头双向循环链表的结构

在这里插入图片描述

  1. 双向循环链表有一个头节点，这个头节点不存储数据，只起到标记头部的位置。
  2. 链表中某一节点的指针域分为两部分，一部分储存下一节点的地址，另一部分储存上一节点的地址。
  3. 通过指针域，链表的头节点与尾节点相连，形成循环。

带头双向循环链表因其结构优势，在实现增删查改不用进行遍历，时间复杂度为O(1)。

利用结构体将带头双向循环链表定义出来

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
  1. 如代码所示，结构体中有两个成员为指针域，一个成员为数据域。
  2. 将结构体类型与结构体中的成员数据域类型都用 typedef重新定义，便于代码维护。

2、链表的初始化

在这里插入图片描述

LTNode* ListInit()
{
	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc");
		exit(-1);  //将整个程序结束掉
	}

	guard->next = guard;  //带头双向链表为空的时候，头节点的next与prev要指向自己
	guard->prev = guard;

	return guard;
}
  1. exit()，是将整个程序终止，退出当前运行的程序。exit(0);表示程序正常退出，exit(其他值);表示程序异常退出。
    return，是将该段函数运行中止，回到调用的函数或者回到主函数中。
  2. 为什么用 exit ？
    当动态内存申请失败是，除了申请的内存实在过大，一般是自己的电脑硬件内存不够用了，所以直接将程序结束，去检查一下自己的电脑内存吧。
  3. 带头双向循环链表为空时，指针域next与指针域prev都指向自己，即自己指向自己。

3、链表的打印

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;

	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
  1. 从第一个存储有效的数据的节点开始打印（头节点的下一个节点），直到再次打印到头节点，链表中的所有数据打印完毕。

4、链表判空

bool ListEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;  //相等说明是空，且相等为真，所以空时返回值为真，非空时，返回值为假
}

1、链表中的返回值：相等说明是空，且相等为真，所以空时返回值为真，非空时，返回值为假

5、链表申请一个节点

LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	node->next = NULL;
	node->prev = NULL;
	node->data = x;

	return node;
}
  1. 当链表中需要插入数据时，即需要开辟一个新的节点，利用动态内存开辟函数为其开辟一块空间。
  2. 将新开辟空间指针域的两个部分全部置空，数据域赋值为要插入的数据。

6、链表尾插

在这里插入图片描述

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);  //因为当头双向链表为空时，头节点也不为空，所以要断言，避免为空
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;  //尾插先找到尾，头节点的上一个就是尾节点

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

}
  1. 尾插先找到尾，尾节点就是头节点的上一个节点
  2. 再将新开辟的节点(即要插入的节点)与头节点还有之前的尾节点联系起来。

链表尾插并打印

void TestList1()
{
	/*LTNode* plist = NULL;
	listInit(&plist);*/

	LTNode* plist = ListInit();

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListPrint(plist);
}

int main()
{
	TestList1();
	return 0;
}

打印结果
在这里插入图片描述

  1. 数据1 2 3 4依次往后插入。

7、链表头插

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* first = phead->next;   //先将第一个存放有效数据的节点标记出来

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}
  1. 链表头插首先要标记第一个有效存储数据的节点，便于新节点插入后能够找到并产生联系。

链表头插并打印

void TestList2()
{
	/*LTNode* plist = NULL;
	listInit(&plist);*/


	LTNode* plist = ListInit();

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListPushFront(plist, 100);
	ListPushFront(plist, 200);
	ListPushFront(plist, 300);

	ListPrint(plist);
}

int main()
{
	TestList2();
	return 0;
}

打印结果
在这里插入图片描述

  1. 数据 300 200 100依次在链表头上插入。

8、链表尾删

void ListPopBack(LTNode* phead)
{
	assert(phead);
	//if (phead->next == phead)
	//{
	//	return 0; //没得删，直接返回
	//}

	assert(!ListEmpty(phead)); //为空，没得删

	LTNode* tail = phead->prev; //尾删先找尾
	LTNode* prev = tail->prev;  //找到尾的前一个

	prev->next = phead;
	phead->prev = prev;

	free(tail);
	tail = NULL;
}
  1. 删节点之前要先判断链表是否为空，为空即没得删，用断言函数断言。
  2. 头节点 phead 为空也没得删，同样用断言函数断言。
  3. 删尾部之前要先找到尾部，尾节点就是头节点的上一个节点
  4. 将尾节点的上一个节点找到并标记起来，便于后续与头节点产生联系。

链表尾删并打印

void TestList3()
{
	LTNode* plist = ListInit();

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	
	ListPrint(plist);
}

int main()
{
	TestList3();
	return 0;
}

打印结果
在这里插入图片描述

  1. 调用4次尾删函数，之前插入的四个数据1 2 3 4 全被删除了。

9、链表头删

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead)); //为空，没得删
	
	LTNode* first = phead->next;  //先将第一个存放有效数据的节点标记出来
	LTNode* second = first->next; //先将第二个存放有效数据的节点标记出来
	
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;

}
  1. 删除前判空，即判断是否有节点可删。
  2. 判断传过来的头节点 phead 是否为空，用断言函数。
  3. 带头双向循环链表的头删即删除第一个有效存储数据的节点。
  4. 将第一个有效存储数据的节点标记出来，便于后续能够找到并free掉。
  5. 将第二个有效存储数据的节点标记出来，便于后续能够找到并与头节点产生联系。

链表头删并打印

void TestList4()
{
	
	LTNode* plist = ListInit();

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListPrint(plist);

	ListPopFront(plist);
	ListPopFront(plist);

	ListPrint(plist);
}

int main()
{
	TestList4();
	return 0;
}

打印结果
在这里插入图片描述

  1. 调用两次头删函数，数据 1 2 被删除了。

10、求链表的长度

size_t ListSize(LTNode* phead)
{
	assert(phead);

	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		n++;
		cur = cur->next;
	}
	
	return n;
}
  1. 遍历一遍链表就能求出链表长度。
  2. 遍历链表结束标志是再次遇到头节点。

调用求链表长度函数

void TestList5()
{

	LTNode* plist = ListInit();

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	size_t len = ListSize(plist);
	printf("%zd\n", len);

	ListPopFront(plist);
	ListPopFront(plist);

	size_t n = ListSize(plist);
	len = ListSize(plist);
	printf("%zd\n", len);

}

int main()
{
	TestList5();
	return 0;
}

打印结果
在这里插入图片描述

  1. 插入四个数据，链表长度是4。
  2. 再头删两个数据，链表长度变成2。

11、查找位置

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL; //遍历完了还没找到，返回空
}
  1. 遍历链表，找到给定的数据后，返回该数据的位置。
  2. 遍历完后还没找到，说明链表中没有要找的数据，返回空指针。

调用查找函数并打印

void TestList6()
{

	LTNode* plist = ListInit();

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	LTNode* pos = ListFind(plist,2);

	printf("%p\n", pos);

}

int main()
{
	TestList6();
	return 0;
}

打印结果
在这里插入图片描述

  1. 查找数据 2 的位置，如代码所示，找到了。

12、在给定位置pos处插入数据

在给定pos位置插入数据，带头双向循环链表默认是在pos位置之前插入的

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;

	LTNode* newnode = BuyListNode(x);

	newnode->next = pos;
	pos->prev = newnode;

	prev->next = newnode;
	newnode->prev = prev;
}
  1. 插入数据，需要开辟一个新的节点。
  2. 找到给定pos位置的上一个节点并标记出来，便于后续找到并与新节点产生联系。

插入数据

void TestList7()
{

	LTNode* plist = ListInit();

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListPrint(plist);

	LTNode* pos = ListFind(plist, 2);

	if (pos != NULL)
	{
		ListInsert(pos, 300);
	}

	ListPrint(plist);
}

int main()
{
	TestList7();
	return 0;
}

打印结果
在这里插入图片描述

  1. 如结果所示，在2前面插入了一个300。

13、删除给定位置pos处的数据

void LiseErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}
  1. 将pos位置的上一个节点prev与下一个节点next找到并标记出来。
  2. 将上一个节点prev与下一个节点next通过指针域联系起来。
  3. 将pos位置free掉，及时置空。

删除数据

void TestList8()
{

	LTNode* plist = ListInit();

	ListPushBack1(plist, 1);
	ListPushBack1(plist, 2);
	ListPushBack1(plist, 3);
	ListPushBack1(plist, 4);

	ListPrint(plist);

	LTNode* pos = ListFind(plist, 2);

	if (pos != NULL)
	{
		LiseErase(pos);
	}
	
	ListPrint(plist);
}

int main()
{
	TestList8();
	return 0;
}

打印结果
在这里插入图片描述

  1. 数据 2 被删除了。

14、尾插写法2

void ListPushBack1(LTNode* phead, LTDataType x)
{
	assert(phead);  //因为当头双向链表为空时，头节点也不为空，所以要断言，避免为空

	ListInsert(phead, x); //在phead前面插入就是尾插
}
  1. 在头节点前面插入就是尾插。直接调用 ListInsert(LTNode* pos, LTDataType x);函数。

15、头插写法2

void ListPushFront1(LTNode* phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead->next, x); //在phead下一个节点插入就是头插
}
  1. 在第一个有效存储数据的节点前插入就是头插，直接调用 ListInsert(LTNode* pos, LTDataType x);函数。

16、尾删写法2

void ListPopBack1(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead)); //为空，没得删

	LiseErase(phead->prev);

}
  1. 直接调用 LiseErase(LTNode* pos);函数，将尾部删除即可。

17、头删写法2

void ListPopFront1(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead)); //为空，没得删

	LiseErase(phead->next);

}
  1. 直接调用 LiseErase(LTNode* pos);函数，将第一个有效存储数据的节点删除即可。

18、链表销毁

void ListDestory(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead); //头节点也需要销毁
	//phead = NULL;一级指针，在这里phead改变不了，除非传过来的是phead的地址，所以需要使用的人在函数外面自行销毁
}
  1. 遍历链表，将链表的每一个节点都free掉。
  2. 最后再将头节点也free掉。
  3. free掉头节点后需要将头节点置空，但是因为这里是一级指针，即头节点phead本身，在函数中将其置空，不能改变---->形参是实参的临时拷贝，对形参的改变，改变不了实参。所以需要使用者在函数外部主动置空。

链表销毁展示

void TestList9()
{

	LTNode* plist = ListInit();

	ListPushBack1(plist, 1);
	ListPushBack1(plist, 2);
	ListPushBack1(plist, 3);
	ListPushBack1(plist, 4);

	ListPrint(plist);

	ListDestory(plist);
	plist = NULL; //使用完后自行置空

	ListPrint(plist);
}

int main()
{
	TestList9();
	return 0;
}

打印结果
在这里插入图片描述

  1. 我们可以看到，在链表销毁后再次打印，之前打印函数中写的断言函数起作用了，说明链表已经销毁完毕。

19、带头双向循环链表的所有代码

List.h文件：写函数的声明，函数的头文件，其他 .c文件只要包含List.h文件—>#include “List.h”，就相当于写了函数的声明与头文件。如下：

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

//带头双向循环链表

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

//初始化
//void ListInit(LTNode** pphead);
LTNode* ListInit();

//打印
void ListPrint(LTNode* phead);

//判断是否为空
bool ListEmpty(LTNode* phead);

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

//头插
void ListPushFront(LTNode* phead, LTDataType x);

//尾删
void ListPopBack(LTNode* phead);

//头删
void ListPopFront(LTNode* phead);

//求链表长度
size_t ListSize(LTNode* phead);

//查找位置
LTNode* ListFind(LTNode* phead, LTDataType x);

//在pos位置插入，默认在前插入
void ListInsert(LTNode* pos, LTDataType x);

//删除pos位置
void LiseErase(LTNode* pos);

//尾插写法2
void ListPushBack1(LTNode* phead, LTDataType x);

//头插写法2
void ListPushFront1(LTNode* phead, LTDataType x);

//尾删写法2
void ListPopBack1(LTNode* phead);

//头删写法2
void ListPopFront1(LTNode* phead);

//销毁链表
void ListDestory(LTNode* phead);

List.c文件：用来实现链表的各种功能接口函数。如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

//初始化
LTNode* ListInit()
{
	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc");
		exit(-1);  //将整个程序结束掉
	}

	guard->next = guard;  //带头双向链表为空的时候，头节点的next与prev要指向自己
	guard->prev = guard;

	return guard;
}


//打印
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;

	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}


//判断是否为空，为空返回真，非空返回假
bool ListEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;  //相等说明是空，且相等为真，所以空时返回值为真，非空时，返回值为假
}


//申请一个节点
LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	node->next = NULL;
	node->prev = NULL;
	node->data = x;

	return node;
}


//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);  //因为当头双向链表为空时，头节点也不为空，所以要断言，避免为空
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;  //尾插先找到尾，头节点的上一个就是尾节点

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

}


//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* first = phead->next;   //先将第一个存放有效数据的节点标记出来

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}


//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	//if (phead->next == phead)
	//{
	//	return 0; //没得删，直接返回
	//}

	assert(!ListEmpty(phead)); //为空，没得删

	LTNode* tail = phead->prev; //尾删先找尾
	LTNode* prev = tail->prev;  //找到尾的前一个

	prev->next = phead;
	phead->prev = prev;

	free(tail);
	tail = NULL;
}


//头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead)); //为空，没得删
	
	LTNode* first = phead->next;  //先将第一个存放有效数据的节点标记出来
	LTNode* second = first->next; //先将第二个存放有效数据的节点标记出来
	
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;

}


//求链表长度
size_t ListSize(LTNode* phead)
{
	assert(phead);

	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		n++;
		cur = cur->next;
	}
	
	return n;
}


//查找位置
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL; //遍历完了还没找到，返回空
}


//在pos位置插入，默认在前插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;

	LTNode* newnode = BuyListNode(x);

	newnode->next = pos;
	pos->prev = newnode;

	prev->next = newnode;
	newnode->prev = prev;
}


//删除pos位置
void LiseErase(LTNode* pos)
{
    assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}


//尾插写法2
void ListPushBack1(LTNode* phead, LTDataType x)
{
	assert(phead);  //因为当头双向链表为空时，头节点也不为空，所以要断言，避免为空

	ListInsert(phead, x); //在phead前面插入就是尾插
}


//头插写法2
void ListPushFront1(LTNode* phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead->next, x); //在phead下一个节点插入就是头插
}


//尾删写法2
void ListPopBack1(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead)); //为空，没得删

	LiseErase(phead->prev);

}


//头删写法2
void ListPopFront1(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead)); //为空，没得删

	LiseErase(phead->next);

}


//销毁函数
//可以传二级指针，内部置空头节点
//建议：也可以考虑使用一级指针作为形参，让调用ListDestory的人置空（这样是为了保持接口的一致性）
void ListDestory(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead); //头节点也需要销毁
	//phead = NULL;一级指针，在这里phead改变不了，除非传过来的是phead的地址，所以需要使用的人在函数外面自行销毁
}

test.c文件：主函数写在这，在主函数中可以调用 List.c文件中实现的各种接口。如下：

int main()
{
	return 0;
}

以上就是无头单向非循环链表链表的所有代码，在SList.c文件中实现的函数接口有以下注意：

  1. 函数对指定的地址要进行断言，避免传过来的是空指针。
  2. 形参传过来的不是头节点的地址，如果需要改变头节点本身，需要使用者在使用完函数后，在主函数中自己更改。

内容创作不易😁😁
你的关注与支持就是我的创作动力🧡💛
动动你的发财手给个一键三连吧😉
非常感谢！🌹🌹🌹
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-08-19 19:31:09  更:2022-08-19 19:33:13 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年5日历 -2024/5/7 1:15:04-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码