数据结构【没头单链表】

逆向-落叶

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

840

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

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

概念与结构

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

这个单链表我们需要一个整行或其他类型的存放数据，还有一个结构体指针，结构体指针连接下一个节点。

结点

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点”

结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。

图中指针变量plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望 plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012FFA0。链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

链表的性质

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续 2、结点⼀般是从堆上申请的 3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

结合前⾯学到的结构体知识，我们可以给出每个结点对应的结构体代码：

假设当前保存的结点为整型：

struct SListNode
{
 int data; //节点数据
 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在当前节点拿上下⼀个结点的地址就可以了。

链表的打印分析

给定的链表结构中，如何实现结点从头到尾的打印？

思考：当我们想保存的数据类型为字符型、浮点型或者其他⾃定义的类型时，该如何修改？

实现单链表：

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

创建单链表数据

arr用来存放数据，p指向下一个节点

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int data;
typedef struct slist
{
	//存放数据
	data* arr;
	//指向下一个节点
	struct slist* p;
}SL;

在测试文件创建链表为NULL

申请空间

接收的是数值，返回的是空间，把arr赋值x，p给空返回add

//申请空间
SL* koj(data x)
{
	//申请空间
	SL* add = (SL*)malloc(sizeof(SL));
	//判断是不是空
	if (add == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//把数据赋值给add
	add->arr = x;
	add->p = NULL;
	//然后返回
	return add;
}

尾插数据

头文件

使用二级指针接收，直接修改实参。用一级的话还要赋值。

声明尾插的函数，为什么要声明，因为如果我们有很多个函数的话要一个一个找很麻烦，所以声明在头文件，就像我们看书的目录一样方便我们查看有哪些函数。

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

add接收的新申请的空间

思路：先判断当前r是不是空，是就直接把申请的空间给过去就行了

有空间，把地址给tab循环走到最后一个节点，然后让最后一个节点的指针指向add空间

//尾插
void weic(SL** r, data x)
{
	assert(r);
	//申请空间
	SL* add = koj(x);
	//判断单链表是不是空
	if (*r == NULL)
	{
		//是空就直接赋值
		*r = add;
	}
	//不是空就循环走到tab->p 的null位置，进行连接
	else
	{
		//把r地址给tab
		SL* tab = *r;
		while (tab->p)
		{
			//循环走到tab->p 的null位置，进行连接
			tab = tab->p;
		}
		//把申请的空间和tab->p连接
		tab->p = add;
	}
}

打印

打印用一级就行了，我们只是打印数据。

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

打印

循环往后打印，最后一个打印NULL

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

    SL* add = NULL;
	//尾插
	weic(&add, 1);
	weic(&add, 2);
	weic(&add, 3);
	weic(&add, 4);

头插数据

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

思路：申请add空间，add的指针指向头节点*r，把add给*r这样新申请的空间就是头节点了。

//头插
void toc(SL** r, data x)
{
	assert(r);
	//申请空间
	SL* add = koj(x);
	//把申请空间的add->p指向r的当前地址
	add->p = *r;
	//把add的地址给r
	*r = add;
}

    SL* add = NULL;
	//头插
	toc(&add, 1);
	toc(&add, 2);
	toc(&add, 3);
	toc(&add, 4);

尾删

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

思路：判断当前节点的下一个节点是不是空，是就说明只有一个节点，直接释放。

循环往后走到最后一个节点，每走一步前保存到tab，就能拿到前一个节点了。

把tab->p赋值为空，释放add空间就可以了。

//尾删除
void weisc(SL** r)
{
	assert(r && *r);
	//判断第一个节点的p是不是null，是就直接释放
	if ((*r)->p == NULL)
	{
		free(*r);
		*r = NULL;
	}
	else
	{
		//这个找后面的节点
		SL* add = *r;
		//这个是后面的前一个节点
		SL* tab = NULL;
		//循环到后面的节点
		while (add->p)
		{
			//把当前节点给tab
			tab = add;
			//然后指向下一个节点
			add = add->p;
		}
		//把tab赋值为null
		tab->p = NULL;
		//然后释放add的空间
		free(add);
		add = NULL;
	}
}

我们可以看到尾插1,2,3,4删除了4这个节点

    SL* add = NULL;
	//尾插
	weic(&add, 1);
	weic(&add, 2);
	weic(&add, 3);
	weic(&add, 4);
	//尾删
	weisc(&add);
	day(add);

头删

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

思路：创建add保存头节点，r往后走一步，释放add空间

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

	SL* add = *r;
	*r = (*r)->p;
	free(add);
	add = NULL;
}

可以看到我们删了1和2。

	SL* add = NULL;
	//尾插
	weic(&add, 1);
	weic(&add, 2);
	weic(&add, 3);
	weic(&add, 4);
	//头删
	tosc(&add);
	tosc(&add);
	day(add);

查询数据

//查询
SL* cx(SL* r,data x);

思路：把r给add,让add循环判断每个节点的arr数据等不等于x，等于直接返回当前节点，不等于返回NULL。

//查询
SL* cx(SL* r, data x)
{
	SL* add = r;
	//循环查询
	while (add)
	{
		//判断是不是等于x
		if (add->arr == x)
		{
			//是就返回当前节点
			return add;
		}
		//指向下一个节点
		add = add->p;
	}
	//没有返回空
	return NULL;
}

pos接收当前节点，等于空打印没找到，不等于打印找到了。

	SL* add = NULL;
	//尾插
	weic(&add, 1);
	weic(&add, 2);
	weic(&add, 3);
	weic(&add, 4);
	day(add);
	//查询
	SL* pos = cx(add, 4);
	if (pos == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	}

指定位置前插入数据

//在指定位置前插入数据
void zhidqcr(SL** r, SL* pos, data x);

思路：判断pos等于r就说明在第一个节点或只有一个节点，直接调用头插的函数就行了。

add循环到pos后面，tab->p连接pos，add->p连接tab。

//在指定位置前插入数据
void zhidqcr(SL** r,SL* pos, data x)
{
	assert(r);
	assert(pos);
	//判断是不是在第一个节点
	if (pos == *r)
	{
		//是就调用头插
		toc(r,x);
	}
	else
	{
		//申请的空间
		SL* tab = koj(x);
		SL* add = *r;
		//循环到节点前面停下
		while (add->p != pos)
		{
			add = add->p;
		}
		//进行
		tab->p = pos;
		add->p = tab;

	}
}

在3的前面插入了一个数据为99的节点

	SL* add = NULL;
	//尾插
	weic(&add, 1);
	weic(&add, 2);
	weic(&add, 3);
	weic(&add, 4);
	//查询
	SL* pos = cx(add, 3);
	//if (pos == NULL)
	//{
	//	printf("没找到\n");
	//}
	//else
	//{
	//	printf("找到了\n");
	//}
	zhidqcr(&add, pos, 99);

	day(add);

指定位置后插入数据

//在指定位置后插入数据
void zhidhcr(SL* pos, data x);

思路：add是新申请的空间，add->p连接pos下一个节点，pos->p连接add。

//指定位置后插入数据
void zhidhcr(SL* pos, data x)
{
	assert(pos);
	//申请空间
	SL* add = koj(x);
	//把r后面那个节点的地址给新的节点
	add->p = pos->p;
	//把新的节点给r
	pos->p = add;
}

我们可以看到在3后面插入了一个99的节点。

	SL* add = NULL;
	//尾插
	weic(&add, 1);
	weic(&add, 2);
	weic(&add, 3);
	weic(&add, 4);
	//查询
	SL* pos = cx(add, 3);
	//if (pos == NULL)
	//{
	//	printf("没找到\n");
	//}
	//else
	//{
	//	printf("找到了\n");
	//}
	zhidhcr(pos, 99);

删除pos节点

//删除pos节点
void scpos(SL** r, SL* pos);

思路：判断只有一个节点或等于当前节点，直接释放。

把r给add,让add循环到pos前一个节点，add->p指向pos下一个节点，然后释放pos空间。

//删除pos节点
void scpos(SL** r, SL* pos)
{
	//我们需要pos前一个节点，和后一个节点连接
	assert(r && *r);
	assert(pos);
	//判断如果（第一个节点等于要删除的节点）直接释放
	if (*r == pos)
	{
		free(*r);
		*r = NULL;
	}
	else
	{
		SL* add = *r;
		//循环走到pos节点的后面
		while (add->p != pos)
		{
			add = add->p;
		}
		//把pos指向的节点，给pos前面的节点（把pos后面的节点和pos前面的节点进行连接）
		add->p = pos->p;
		//释放pos空间
		free(pos);
		pos = NULL;
	}
}

我们可以看到3被删除了

    SL* add = NULL;
	//尾插
	weic(&add, 1);
	weic(&add, 2);
	weic(&add, 3);
	weic(&add, 4);
	//查询
	SL* pos = cx(add, 3);
	//if (pos == NULL)
	//{
	//	printf("没找到\n");
	//}
	//else
	//{
	//	printf("找到了\n");
	//}
	scpos(&add,pos);

删除pos后面的节点

//删除pos后面的节点
void schpos(SL* pos);

思路：把pos下一个节点给add, pos->p指向add下一个节点。释放add空间。

//删除pos后面的节点
void schpos(SL* pos)
{
	assert(pos&&pos->p);
	//把pos下一个节点给add
	SL* add = pos->p;
	//把add下个节点给pos
	pos->p = add->p;
	//释放add
	free(add);
	add = NULL;
}

	SL* add = NULL;
	//尾插
	weic(&add, 1);
	weic(&add, 2);
	weic(&add, 3);
	weic(&add, 4);
	//查询
	SL* pos = cx(add, 3);
	//if (pos == NULL)
	//{
	//	printf("没找到\n");
	//}
	//else
	//{
	//	printf("找到了\n");
	//}
	scpos(&add,pos);
	day(add);

销毁

//链表销毁
void xiaoh(SL** r);

思路：add循环释放，tab保存add下一个节点，释放add，在把tab给add,

最后还剩下*r赋值为NULL。

//链表销毁
void xiaoh(SL** r)
{
	assert(r && *r);
	//把r节点给add
	SL* add = *r;
	SL* tab = NULL;
	//循环走全部节点
	while (add)
	{
		//把add下一个节点给tab
		tab = add->p;
		//释放add节点
		free(add);
		//把tab给add
		add = tab;
	}
	//把一开始的*r赋值为NULL
	*r = NULL;

}

释放完后还剩下*r的空间需要赋值为NULL