链表的基础

��

目录

顺序表

链表

需要注意的 

链表的优势 

 单链表的实现

1.单链表的准备

2.单链表的结构体的创建

 3.单链表的准备

 4.前插

5.后插

 6.后删

7.前删

8.任意位置前插

9.任意位置后插

 10.删除

11.修改

12.打印

13.释放链表

---

 总说链表难，但我感觉只要认真听讲，再加上自己敲敲代码，也不是很难，毕竟后面还有更难的算法  哈哈

顺序表

想要了解什么是链表，我们要先知道什么是顺序表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储

 这一点在通讯录的实现给出了充足的运用，然后向更深的探索，也就慢慢产生了链表

链表

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

这就好比火车一样，每个车间都装着东西，然而车间与车间之间并不是向顺序表一样直接加加向后，而是每个车间是通过中间车钩连接起来的，

 在数据结构上的链表也是同样道理，在一个结构体内，有一部分装着必要的信息，而另一部分又有指针，该指针存放着下一个结构体的地址，使得两个结构体如果火车一样连接在一起；

文字表示固然不清楚，我们展示图形：

此处只展示单链表，单链表会的话，双链表也是同样道理，可以自己实现 

需要注意的 

我们的链表最后一个节点的指针部分，必须存放的是NULL这里我们需要自己写代码让其为NULL要不然没有这一步，我们不知道结束的判断是什么 

链表的优势 

这里是摘自别人的博客 

 链表基础知识详解（非常详细简单易懂）-CSDN博客

人家写的比我写的详细多了，还讲解了双链表，值得学习 

 

   链表是通过节点把离散的数据链接成一个表，通过对节点的插入和删除操作从而实现 对数据的存取。而数组是通过开辟一段连续的内存来存储数据，这是数组和链表最大的区 别。数组的每个成员对应链表的节点，成员和节点的数据类型可以是标准的 C 类型或者是 用户自定义的结构体。数组有起始地址和结束地址，而链表是一个圈，没有头和尾之分， 但是为了方便节点的插入和删除操作会人为的规定一个根节点。

————————————————

                            版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

                        

原文链接：https://blog.csdn.net/qq_61672347/article/details/125701955

 单链表的实现

1.单链表的准备

我们先写出需要用到的头文件 

#include #include #include#include#include#includetypedef int SLDataType;

这里的重命名是为了方便以后修改

2.单链表的结构体的创建

一部分存放需要存的信息，一部分为指针存放下一个结构体的地址

typedef int SLDataType;typedef struct SLList{    SLDataType x;    struct SLList* next;}SL;

 3.单链表的准备

int main(){SL* SLList=NULL;return 0;}

 4.前插

前插需要考虑的就是如果单链表本来就没有节点 

大致图：

需要注意的是我们传的是指针的地址，我们需要用二级指针接收，才可以改变一级指针指向的内容

SLPushFront(&SLList, 5);    void SLPushFront(SL** pphead, SLDataType x){assert(pphead);SL* newcode = (SL*)malloc(sizeof(SL));if (newcode == NULL){perror("malloc fail");return;}newcode->next = *pphead;newcode->x = x;*pphead = newcode;}

5.后插

 后插跟前插同样的道理

 同样需要考虑的是没有节点的问题与只有一个节点

void SLPushback(SL** pphead,SLDataType x){assert(pphead);SL* newcode = (SL*)malloc(sizeof(SL));if (*pphead == NULL){*pphead = newcode;(*pphead)->x = x;(*pphead)->next = NULL;return;}SL* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newcode;tail = tail->next;tail->x = x;tail->next = NULL;}

 6.后删

 

后删同样需要考虑没有节点，没有节点当然删不了啊，还有只有一个节点，我们需要直接将这个节点直接释放，然后等于NULL

void SLPopBack(SL** pphead){assert(pphead);assert(*pphead);SL* tail = *pphead;//一个也没有assert(*pphead);//一个节点if ((*pphead)->next==NULL){free(*pphead);*pphead = NULL;return;}//多个节点while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}

7.前删

void SLPopFront(SL** pphead){assert(pphead);assert(*pphead);SL* tail = *pphead;*pphead = (*pphead)->next;free(tail);//tail是SL* tail=&SLList;}

8.任意位置前插

 我们需要先找到该位置，然后在与前面前插后插同样方法进行插入

SL* pos = SLFind(SLList,2);SLInsert(&SLList,pos,20);//前插SLPrint(SLList);

SL* SLFind(SL* pphead, SLDataType x){assert(pphead);SL* tail = pphead;while (tail->x != x){tail = tail->next;}return tail;}void SLInsert(SL** pphead, SL* pos, SLDataType x){assert(pphead);assert(pos);SL* tail = *pphead;SL* newcode = (SL*)malloc(sizeof(SL));if (newcode == NULL){perror("SLInsert fail");}while (tail->next != pos){tail = tail->next;}newcode->next = tail->next;newcode->x = x;tail->next = newcode;}

9.任意位置后插

SL* pos = SLFind(SLList,2);    SLInsertBack(&SLList, pos, 30);//后插SLPrint(SLList);

void SLInsertBack(SL** pphead, SL* pos, SLDataType x){assert(pphead);assert(pos);SL* tail = *pphead;SL* newcode = (SL*)malloc(sizeof(SL));if (newcode == NULL){perror("SLInsertBack fail");}while (tail != pos){tail = tail->next;}newcode->next = tail->next;newcode->x = x;tail->next = newcode;}

 10.删除

SL* pos = SLFind(SLList,2)；SLErase(&SLList, pos);SLPrint(SLList);

void SLErase(SL** pphead, SL* pos){assert(pphead);assert(pos);SL* tail = *pphead;if (pos == *pphead){SLPopFront(pphead);return;}while (tail->next != pos){tail = tail->next;}tail->next = pos->next;free(pos);}

11.修改

pos= SLFind(SLList, 3);SLModify(&SLList, pos, 50);SLPrint(SLList);

void SLModify(SL** pphead, SL* pos, SLDataType x){assert(pphead);assert(pos);SL* tail = *pphead;while (tail != pos){tail = tail->next;}tail->x = x;}

12.打印

void SLPrint(SL* pphead){SL* tail = pphead;while (tail != NULL){printf("%d->", tail->x);tail = tail->next;}printf("NULL\n");}

13.释放链表

void SLList_free(SL** pphead){//定义一个指针变量保存头结点的地址SL* pb = *pphead;while (*pphead != NULL){//先保存p_head指向的结点的地址pb = *pphead;//p_head保存下一个结点地址*pphead = (*pphead)->next;free(pb);pb = NULL;}}