带头双向循环链表

发布于：2023-01-04 ⋅ 阅读:(199) ⋅ 点赞:(0)

一、头文件

Link.h这个头文件中包含了顺序表的定义和对顺序表进行操作的所有函数，所有的函数只传递结构体指针以加快程序运行速度。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>//需要的头文件


#define TYPE int
typedef struct DoubleList
{
	TYPE data;//数据
	struct DoubleList* prev;//指向前面节点的指针，头节点指向尾节点
	struct DoubleList* next;//指向后面节点的指针，尾节点指向头节点
}DList;


//初始化双向链表
DList* InitDList(DList* p);
//初始化节点
DList* Buylistnode(TYPE x);
//头插
void DListfrontpush(DList* p, TYPE x);
//尾插
void DListbackpush(DList* p, TYPE x);
//头删
void DListfrontpop(DList* p);
//尾删
void DListbackpop(DList* p);
//判读链表是否为空
bool ListEmpty(DList* p);
//计算大小
size_t ListSize(DList* p);
//寻找元素
DList* ListFind(DList* p, TYPE x);
// 在pos之前插入
void ListInsert(DList* pos, TYPE x);
// 删除pos位置
void ListErase(DList* pos);
//考虑用一级指针，让调用ListDestory的人置空（保持接口一致性）
void ListDestory(DList* p);
//打印链表
void print(DList* p);

二、函数

这些函数储存在一个function.c 文件中

1.初始化链表

DList* InitDList(DList* p);

先申请一个哨兵卫，让哨兵卫的prev和next都指向自己

//初始化双向链表
DList* InitDList(DList* p)
{
	DList* guard = (DList*)malloc(sizeof(DList));
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	guard->next = guard;
	guard->prev = guard;
}

2.申请一个节点

DList* InitDList(DList* p);

从堆区申请一个节点的空间，让哨兵卫的prev和next都置空，等待后面的操作

DList* Buylistnode(TYPE x)
{
	DList* newcode = (DList*)malloc(sizeof(DList));
	if (newcode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newcode->data = x;
	newcode->next = NULL;
	newcode->prev = NULL;
	return newcode;
}

3.头插

void DListfrontpush(DList* p, TYPE x);

定义newcode指针指向新开辟的节点，然后因为p解引用后拿到的是哨兵卫的地址，我们新建一个first指针储存哨兵卫的next同时也是有效数据储存的头一个节点。

由于双向链表可以前后寻找，所以只需要改变哨兵卫的next，新节点的prev和next，还有原来的有效数据的头的prev三个节点的数据就能将新的节点连接到里面

//头插
void DListfrontpush(DList* p, TYPE x)
{
	DList* newcode = Buylistnode(x);
	DList* first = p->next;
	first->prev = newcode;
	p->next = newcode;
	newcode->next = first;
	newcode->prev = p;
}

4.尾插

void DListbackpush(DList* p, TYPE x);

定义newcode指针指向新开辟的节点，然后因为p解引用后拿到的是哨兵卫的地址同时我们新建一个prevcode指针。由于链表是循环的，所以哨兵卫的prev就是尾节点，prevcode指针赋值为这个尾节点

我们首先将新的尾节点的next指向哨兵卫，然后哨兵卫的prev改成新节点的地址，我们此时的prevcode指针指向的节点就可以与newcode链接形成新链表

//尾插
void DListbackpush(DList* p, TYPE x)
{
	DList* newcode = Buylistnode(x);
	DList* prevcode = p->prev;
	newcode->next = p;
	p->prev = newcode;
	prevcode->next = newcode;
	newcode->prev = prevcode;
}

5.判断链表是否为空

bool ListEmpty(DList* p);

很简单，看看哨兵卫next是否指向它自己

bool ListEmpty(DList* p)
{
	assert(p);
	return p->next == p;
}

6.头删

void DListfrontpop(DList* p);

定义两个指针，first指向有效数据头节点，second指向第二个节点，将哨兵卫的next改为指向second，second节点的prev指向哨兵卫。这里不需要担心只有一个有效节点的情况，如果只有一个节点，second就指向哨兵卫，代码跑完后还是哨兵卫自己指向自己

//头删
void DListfrontpop(DList* p)
{
	assert(!ListEmpty(p));//保证链表不为空
	DList* first = p->next;
	DList* second = first->next;
	p->next = second;
	second->prev = p;
	free(first);
	first = NULL;
}

6.尾删

void DListfrontpop(DList* p);

定义两个指针，tail指向有效数据尾节点，near指向倒数第二个节点，将near的next指向哨兵卫的prev改为指向near，释放空间即可。

//尾删
void DListbackpop(DList* p)
{
	assert(!ListEmpty(p));
	DList* tail = p->prev;
	DList* near = tail->prev;
	near->next = p;
	p->prev = near;
	free(tail);
	tail = NULL;
}

7.打印链表

void print(DList* p);

以数据有效的头节点尾起点，直到遇到哨兵卫停止打印。

//打印链表
void print(DList* p)
{
	assert(p);
	DList* cur = p->next;
	printf("head<=>");
	for (cur = p->next; cur != p; cur = cur->next)
	{
		printf("%d<=>",cur->data);
	}
	printf("head\n");
}

8.链表中有效数据的个数

size_t ListSize(DList* p);

以数据有效的头节点尾起点，直到遇到哨兵卫停止计数。

size_t ListSize(DList* p)
{
	assert(p);
	size_t n = 0;
	DList* cur = p->next;
	for (cur = p->next; cur != p;cur = cur->next)
	{
		n++;
	}
	return n;
}

9.链表中寻找存储相应数据的节点

DList* ListFind(DList* p, TYPE x);

以数据有效的头节点尾起点，直到遇到对应节点停止，又循环回到了哨兵卫就返回NULL

DList* ListFind(DList* p, TYPE x)
{
	assert(p);
	size_t n = 0;
	DList* cur = p->next;
	while (cur != p)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

10.链表在pos节点之前插入数据

void ListInsert(DList* pos, TYPE x);

首先，不破坏原链表的链接情况，将newcode的prev和next连接前后。

然后，pos的prev依旧是原链表的前一个，此时需要改原链表前一个节点的next为新节点的地址，最后pos的prev链接newcode就完成了

// 在pos之前插入
void ListInsert(DList* pos, TYPE x)
{
	assert(pos);
	DList* newcode = Buylistnode(x);
	newcode->prev = pos->prev;
	newcode->next = pos;
	pos->prev->next = newcode;
	pos->prev = newcode;
}

11.链表删除pos节点

void ListErase(DList* pos);

建立两个指针，prev指向pos前的节点，first指向后节点，直接将prev和first连接起来并释放pos

// 删除pos位置
void ListErase(DList* pos)
{
	assert(pos);
	DList* prev = pos->prev;
	DList* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}

12.链表销毁

void ListDestory(DList* p);

从数据的有效数据头节点逐个向后释放直到回到哨兵卫，然后释放哨兵卫。

然而此时虽然所有的堆区空间已经释放，但是用于传参的原指针p依旧指向那块空间，这时我们就需要手动在测试函数中置空

//考虑用一级指针，让调用ListDestory的人置空（保持接口一致性）
void ListDestory(DList* p)
{
	assert(p);
	DList* cur = p->next;
	while (cur != p)
	{
		DList* next = cur->next;
		free(cur);
		cur = next;
	}
	free(p);
	p = NULL;
}



//配合使用
int main()
{
	DList s;
	DList* plist = &s;
	plist = InitDList(plist);
	DListfrontpush(plist, 4);
	DListfrontpush(plist, 3);
	DListfrontpush(plist, 2);
	DListfrontpush(plist, 1);
	ListDestory(plist);
	plist = NULL;//注意这里
	return 0;
}

三、调试

通过test.c来进行操作

void test1()
{
	DList s;
	DList* plist = &s;
	plist = InitDList(plist);
	DListfrontpush(plist, 4);
	DListfrontpush(plist, 3);
	DListfrontpush(plist, 2);
	DListfrontpush(plist, 1);
	print(plist);

	DListbackpush(plist, 10);
	print(plist);

	DListfrontpop(plist);
	print(plist);

	DListbackpop(plist);
	print(plist);

	ListInsert(ListFind(plist, 3) , 12);
	print(plist);

	ListErase(ListFind(plist, 2));
	print(plist);

	printf("%d", ListSize(plist));

	ListDestory(plist);
	plist = NULL;
}



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

 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布