数据结构【没头单链表】

目录

​

概念与结构

结点

链表的性质

链表的打印分析

实现单链表：

创建单链表数据

申请空间

尾插数据

打印

头插数据

尾删

头删

查询数据

指定位置前插入数据

指定位置后插入数据

删除pos节点

删除pos后面的节点

销毁

链表的分类

链表说明：

---

概念与结构

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

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

结点

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

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

图中指针变量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

---

链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2x2x2）链表结构：

链表说明：

虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表

1.⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦ 结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。 

2.带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头 双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实 现反⽽简单了，后⾯我们代码实现了就知道了。