数据结构【没头单链表】
目录
概念与结构
概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的 指针链接次序实现的。
这个单链表我们需要一个整行或其他类型的存放数据，还有一个结构体指针，结构体指针连接下一个节点。
结点
与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点”
结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。
图中指针变量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.带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头 双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实 现反⽽简单了，后⾯我们代码实现了就知道了。
原文地址：https://blog.csdn.net/qq_67578580/article/details/140579570
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！