数据结构【有头双向链表】

逆向-落叶

发布于 2024-10-28 14:34:54

660

发布于 2024-10-28 14:34:54

文章被收录于专栏：C++

注意：这⾥的“带头”跟前⾯我们说的“头结点”是两个概念，实际前⾯的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头结点。

带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的”。

实现双向链表

创建3个文件，list.h头文件，list.c存放函数的文件，test.c测试文件

双向链表数据

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

typedef int data;
typedef struct list
{
	data arr;//存放的数据
	struct list* prev; //节点头（上一个）
	struct list* next; //节点尾（下一个）
}SL;

创建双向链表

双向链表是：带头，双向，循环。

tab->arr存放x数值，双向链表是带循环的，所以节点头和节点尾要指向自己，

tab->next节点尾和tab->prev节点头指向自己。

然后返回当前节点。

//创建双向链表
SL* cjsxlb(data x)
{
	SL* tab = (SL*)malloc(sizeof(SL));
	if (tab == NULL)
	{
		perror("malloc");
		exit(1);
	}
	tab->arr = x;
	tab->next = tab->prev = tab;
	return tab;
}

初始化双向链表创建（哨兵位）

双向链表要带头，所以我们需要创建一个哨兵位head这个哨兵位不能修改。

//初始化
void csh(SL** r);//二级指针的方法
//SL* csh();//一级指针方法

    SL* add = NULL;//二级指针
	csh(&add);

	//SL* add = csh();//一级指针

二级指针：传地址过来可以直接修改到实参。

一级指针：需要add接收创建的哨兵位，然后返回。

//初始化
void csh(SL** r)//二级指针
{
	//创建链表
	*r = cjsxlb(-1);

}

//初始化
//SL* csh()//一级指针
//{
//	//创建链表
//	SL*add = cjsxlb(-1);
//	return add;
//}

尾插

尾插用一级指针就行了，我们不用修改哨兵位。

//尾插
void weic(SL* r,data x);

tab是新的双向链表空间

第一步：tab节点头，指向前一个节点。

第二步：tab节点尾，指向哨兵位节点。

第三步：tab前一个节点的节点尾指向tab。

第四步：哨兵位节点头指向tab。

//尾插
void weic(SL* r, data x)
{
	assert(r);
	SL* tab = cjsxlb(x);
	//先让新节点的头连接前一个节点
	tab->prev = r->prev;
	//新节点的尾连接哨兵位
	tab->next = r;
	//在让新节点的前一个节点连接新的节点头
	r->prev->next = tab;
	//让哨兵位的头指向新的节点
	r->prev = tab;
}

尾插的1,2,3,4

//尾插
	weic(add, 1);
	weic(add, 2);
	weic(add, 3);
	weic(add, 4);
	day(add);

打印双向链表

//打印
void day(SL* r);

打印哨兵位没什么用，所以我们从哨兵位下一个节点开始打印

把下一个节点给add，循环不等于哨兵位，打印每个节点存放的数据。

//打印
void day(SL* r)
{
	SL* add = r->next;
	while (add != r)
	{
		printf("%d->", add->arr);
		add = add->next;
	}
	printf("\n");

}

头插

//头插
void toc(SL* r,data x);

第一步：tab的节点尾指向，哨兵位的下一个节点。

第二步：tab节点头指向哨兵位。

第三步：哨兵位下一个节点的节点头指向tab.

第四步：哨兵位的尾指向tab.

//头插
void toc(SL* r, data x)
{
	assert(r);
	SL* tab = cjsxlb(x);
	//让新节点的尾指向哨兵位下一个节点
	tab->next = r->next;
	//新节点头指向哨兵位
	tab->prev = r;

	//哨兵位下一个节点头指向新节点
	r->next->prev = tab;
	//哨兵位位指向新节点
	r->next = tab;

}

头插了99

	//头插
	toc(&add, 99);

布尔类型

C语⾔原来并没有为布尔值单独设置⼀个类型，⽽是使⽤整数 0 表⽰假，⾮零值表⽰真。在 C99 中也引⼊了布尔类型，是专⻔表⽰真假的。

_Bool

布尔类型的使⽤得包含头⽂件<stdbool.h> 布尔类型变量的取值是： true 或者 false

#define bool _Bool
#define false 0
#define true 1

尾删

我们不能删除哨兵位，所以我们需要布尔类型来判断，当前节点是不是只有一个哨兵位，只有哨兵位不能删除。

//bool
bool list(SL* r);
//尾删除
void weisc(SL* r);

布尔类型，判断哨兵位的尾指向的是自己就返回真。

//布尔类型
bool list(SL* r)
{
	assert(r);
	//哨兵位指向的下一个节点等于哨兵位返回真
	return r->next == r;
}

布尔类型判断接收，（！逻辑非）把真变假，把假变真。

第一步：把最后一个节点给add。

第二步：把add前一个节点给tab。

第三步：tab的尾指向哨兵位。

第四步：哨兵位的头指向tab。

第五步：释放add空间。

//尾删除
void weisc(SL* r)
{
	assert(r);
	//布尔类型判断
	assert(!list(r));
	//把最后一个节点给add
	SL* add = r->prev;
	//把最后一个节点的前一个节点给tab
	SL* tab = add->prev;
	//tab尾指向哨兵位
	tab->next = r;
	//哨兵位头指向tab
	r->prev = tab;
	//释放add
	free(add);
	add = NULL;
}

我们可以看到把4删除了。

//尾删除
	weisc(&add);

头删

头删不是删哨兵位，是删除哨兵位的下一个节点。

//头删除
void tosc(SL* r);

布尔类型判断接收，（！逻辑非）把真变假，把假变真。

第一步：把哨兵位下一个节点给add。

第二步：把add下一个节点的头指向哨兵位。

第三步：哨兵位的尾指向add下一个节点。

第四步：释放add空间。

//头删除
void tosc(SL* r)
{
	assert(r);
	//布尔类型判断
	assert(!list(r));
	//哨兵位的下一个节点
	SL* add = r->next;

	//add下一个节点的头指向哨兵位
	add->next->prev = r;
	//哨兵位的尾指向add的下一个节点
	r->next = add->next;
	free(add);
	add = NULL;

}

把1删除了

    //头删除
	tosc(&add);

查询

//查找
SL* cz(SL* r, data x);

从哨兵位下一个节点开始循环查找，找到了返回当前空间就好了。

//查找
SL* cz(SL* r, data x)
{
	assert(r);
	//从哨兵位下一个节点开始
	SL* add = r->next;
	while (add != r)
	{
		if (add->arr == x)
		{
			return add;
		}
		add = add->next;
	}
	return NULL;

}

SL* tab = cz(add, 1);
	/*if (tab == NULL)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("找到了\n");
	}*/

指定位置后插入

这原理和头插一样

//指定位置后插入
void zhidcr(SL* tab, data x);

第一步：add的节点尾指向，tab的下一个节点。

第二步：add节点头指向tab。

第三步：tab下一个节点的节点头指向add.

第四步：tab的尾指向add.

//指定位置后插入
void zhidcr(SL* tab, data x)
{
	SL* add = cjsxlb(x);
	//新节点的尾指向tab的下一个节点
	add->next = tab->next;
	//新节点的头指向tab
	add->prev = tab;
	//tab下一个节点的头指向add
	tab->next->prev = add;
	//tab节点的尾指向add
	tab->next = add;

}

我们可以看到在1后面插入了一个99。

//指定位置后插入
	zhidcr(tab, 99);

指定位置删除数据

这个的原理和头删除一样，把哨兵位当做tab的上一个节点就可以了。

//指定位置删除
void zhidsc(SL* tab);

先把tab给add

第一步：把add上一个节点的尾指向add的下一个节点。

第二步：把add的下一个节点的头指向add的上一个节点。

第三步：释放add或tab空间,都是指向一块空间的，然后置为NULL。

//指定位置删除
void zhidsc(SL* tab)
{
	assert(tab);
	SL* add = tab;
	//把add上一个节点的尾指向add的下一个节点
	add->prev->next = add->next;
	//把add的下一个节点的头指向add的上一个节点
	add->next->prev = add->prev;
	//释放add
	free(tab);
	tab = NULL;
}

我们可以看到把3删除了

//指定位置删除
	zhidsc(tab);

销毁

销毁我们需要把哨兵位后面的全部销毁完，再销毁哨兵位。

//销毁
//void ziaoh(SL** r);//二级指针

//销毁
void xiaoh(SL* r);//一级指针

第一步：先把哨兵位下一个节点给add。

第二步：循环销毁哨兵位后面的节点，

tab保存下一个节点，释放add空间，把tab空间给add。

第三步：释放哨兵位，把哨兵位置为NULL，在把add置为NULL。

//销毁
void xiaoh(SL* r)//一级指针
{
	//从哨兵位下一个节点开始销毁
	SL* add = r->next;
	while (add != r)
	{
		//tab保存下一个节点
		SL* tab = add->next;
		//释放
		free(add);
		//下一个节点赋值给add
		add = tab;
	}
	//释放哨兵位
	free(r);
	r = NULL;
	//把add置为空
	add = NULL;
}

//销毁
void xiaoh(SL** r)//二级指针
{
	//从哨兵位下一个节点开始销毁
	SL* add = (*r)->next;
	while (add != *r)
	{
		//tab保存下一个节点
		SL* tab = add->next;
		//释放
		free(add);
		//下一个节点赋值给add
		add = tab;
	}
	//释放哨兵位
	free(*r);
	r = NULL;
	//把add置为空
	add = NULL;
}

二级指针可以传地址过去可以修改到实参，销毁数据相当于销毁了实参。

一级指针不能修改到实参，所以我们销毁完，需要把实参置为NULL。

	//xiaoh(&add);//二级指针

	xiaoh(add);//一级指针
	add = NULL;

我们可以看到销毁成功了。

顺序表和链表的分析

不同点	顺序表	链表（单链表）
存储空间上	物理上⼀定连续	逻辑上连续，但物理上不⼀定连续
随机访问	⽀持O(1)	不⽀持：O(N)
任意位置插⼊或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插⼊	动态顺序表，空间不够时需要扩容和空间浪费	没有容量的概念，按需申请释放，不存在空间浪费
应⽤场景	元素⾼效存储+频繁访问	任意位置⾼效插⼊和删除

代码

list.h

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

typedef int data;
typedef struct list
{
	data arr;//存放的数据
	struct list* prev; //节点头（上一个）
	struct list* next; //节点尾（下一个）
}SL;
//初始化
void csh(SL** r);//二级指针的方法
//SL* csh();//一级指针方法
//尾插
void weic(SL* r,data x);
//打印
void day(SL* r);
//头插
void toc(SL* r,data x);
//bool
bool list(SL* r);
//尾删除
void weisc(SL* r);
//头删除
void tosc(SL* r);
//查找
SL* cz(SL* r, data x);
//指定位置后插入
void zhidcr(SL* tab, data x);
//指定位置删除
void zhidsc(SL* tab);
//销毁
//void ziaoh(SL** r);//二级指针
//销毁
void xiaoh(SL* r);//一级指针

list.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"

//创建双向链表
SL* cjsxlb(data x)
{
	SL* tab = (SL*)malloc(sizeof(SL));
	if (tab == NULL)
	{
		perror("malloc");
		exit(1);
	}
	tab->arr = x;
	tab->next = tab->prev = tab;
	return tab;
}


//初始化
void csh(SL** r)//二级指针
{
	//创建链表
	*r = cjsxlb(-1);

}

//初始化
//SL* csh()//一级指针
//{
//	//创建链表
//	SL*add = cjsxlb(-1);
//	return add;
//}



//打印
void day(SL* r)
{
	SL* add = r->next;
	while (add != r)
	{
		printf("%d->", add->arr);
		add = add->next;
	}
	printf("\n");

}


//尾插
void weic(SL* r, data x)
{
	assert(r);
	SL* tab = cjsxlb(x);
	//先让新节点的头连接前一个节点
	tab->prev = r->prev;
	//新节点的尾连接哨兵位
	tab->next = r;
	//在让新节点的前一个节点连接新的节点头
	r->prev->next = tab;
	//让哨兵位的头指向新的节点
	r->prev = tab;
}


//头插
void toc(SL* r, data x)
{
	assert(r);
	SL* tab = cjsxlb(x);
	//让新节点的尾指向哨兵位下一个节点
	tab->next = r->next;
	//新节点头指向哨兵位
	tab->prev = r;

	//哨兵位下一个节点头指向新节点
	r->next->prev = tab;
	//哨兵位位指向新节点
	r->next = tab;

}

//布尔类型
bool list(SL* r)
{
	assert(r);
	//哨兵位指向的下一个节点等于哨兵位返回真
	return r->next == r;
}

//尾删除
void weisc(SL* r)
{
	assert(r);
	//布尔类型判断
	assert(!list(r));
	//把最后一个节点给add
	SL* add = r->prev;
	//把最后一个节点的前一个节点给tab
	SL* tab = add->prev;
	//tab尾指向哨兵位
	tab->next = r;
	//哨兵位头指向tab
	r->prev = tab;
	//释放add
	free(add);
	add = NULL;
}


//头删除
void tosc(SL* r)
{
	assert(r);
	//布尔类型判断
	assert(!list(r));
	//哨兵位的下一个节点
	SL* add = r->next;

	//add下一个节点的头指向哨兵位
	add->next->prev = r;
	//哨兵位的尾指向add的下一个节点
	r->next = add->next;
	free(add);
	add = NULL;

}



//查找
SL* cz(SL* r, data x)
{
	assert(r);
	//从哨兵位下一个节点开始
	SL* add = r->next;
	while (add != r)
	{
		if (add->arr == x)
		{
			return add;
		}
		add = add->next;
	}
	return NULL;

}


//指定位置后插入
void zhidcr(SL* tab, data x)
{
	SL* add = cjsxlb(x);
	//新节点的尾指向tab的下一个节点
	add->next = tab->next;
	//新节点的头指向tab
	add->prev = tab;
	//tab下一个节点的头指向add
	tab->next->prev = add;
	//tab节点的尾指向add
	tab->next = add;

}

//指定位置删除
void zhidsc(SL* tab)
{
	assert(tab);
	SL* add = tab;
	//把add上一个节点的尾指向add的下一个节点
	add->prev->next = add->next;
	//把add的下一个节点的头指向add的上一个节点
	add->next->prev = add->prev;
	//释放add
	free(tab);
	tab = NULL;
}



销毁
//void xiaoh(SL** r)//二级指针
//{
//	//从哨兵位下一个节点开始销毁
//	SL* add = (*r)->next;
//	while (add != *r)
//	{
//		//tab保存下一个节点
//		SL* tab = add->next;
//		//释放
//		free(add);
//		//下一个节点赋值给add
//		add = tab;
//	}
//	//释放哨兵位
//	free(*r);
//	r = NULL;
//	//把add置为空
//	add = NULL;
//}

//销毁
void xiaoh(SL* r)//一级指针
{
	//从哨兵位下一个节点开始销毁
	SL* add = r->next;
	while (add != r)
	{
		//tab保存下一个节点
		SL* tab = add->next;
		//释放
		free(add);
		//下一个节点赋值给add
		add = tab;
	}
	//释放哨兵位
	free(r);
	r = NULL;
	//把add置为空
	add = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"

void p()
{
	SL* add = NULL;//二级指针
	csh(&add);

	//SL* add = csh();//一级指针
	
	//尾插
	weic(add, 1);
	weic(add, 2);
	weic(add, 3);
	weic(add, 4);
	day(add);

	头插
	//toc(&add, 99);
	尾删除
	//weisc(&add);
	头删除
	//tosc(&add);

	SL* tab = cz(add, 3);
	/*if (tab == NULL)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("找到了\n");
	}*/
	//指定位置后插入
	//zhidcr(tab, 99);
	//day(add);

	//指定位置删除
	zhidsc(tab);
	day(add);

	//xiaoh(&add);//二级指针

	xiaoh(add);//一级指针
	add = NULL;

}

int main()
{
	p();
	return 0;

}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-28，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构