笔记六：单链表链表介绍与模拟实现

在他一生中，从来没有人能够像你们这样，以他的视角看待这个世界。

                                                                                                             ---------《寻找天堂》    

目录

文章目录

一、什么是链表？

二、为什么要使用链表？

三、 单链表介绍与使用

        3.1 单链表

         3.1.1 创建单链表节点

        3.1.2 单链表的头插、尾插

         单链表的尾插

         单链表的头插

3.1.3  单链表的头删、尾删

         单链表的尾删​编辑

         单链表的头删

 3.1.4 链表节点的查找

3.1.5 在指定位置插入数据

        在指定位置前插入数据

         在指定位置之后插入数据

 3.1.6 删除pos之后的节点

3.1.7 销毁链表

 四、完整代码

SList.h

SList.c

---

一、什么是链表？

        链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成 （malloc），每个节点包括两个部分：

•      一个是存储数据元素的数据域
•      另一个是存储下一个节点地址的指针域

二、为什么要使用链表？

         使用链表用于解决动态数量的数据存储。比如说，我们要管理一堆票据，可能有一张，但也可能有一亿张。怎么办呢？申请一个几十G的大数组存储着吗？万一用户只有一百张票据要处理呢？内存较小拒绝运行？可申请少了又不够用啊……

        而且，用数组的话，删除然后添加票据，是每次删除让后面五百万张往前移一格呢、还是每次添加从头搜索空闲格子？如何区分空闲格子和值为0的数据？要进行区分的话是多占用空间呢还是占用数据值域？占用了值域会不会使得数据处理变得格外复杂？会不会一不小心就和正常数据混淆？万一拿来区分的字段在某个版本后废弃不用、或者扩充值域了呢？

        那么，链表这种东西就是个很有效的数据结构，可以很有效的管理这类不定量的数据。

三、 单链表介绍与使用

        3.1 单链表

        单链表的每个节点除了存放数据元素外，还要存储指向下一个节点的指针。与顺序表进行对比：

	优点	缺点
顺序表	可随机存储，存储密度较高	要求大片连续空间，改变容量不方便
单链表	不要求大片连续空间，改变容量方便	不可随机存取，要耗费一定空间存放指针

         3.1.1 创建单链表节点

typedef int SLTDataType;
//链表是由节点构成
//逻辑结构：一定连续；物理结构：不一定连续
//不会造成空间的浪费，由独立的节点构成
typedef struct SListNode {  //SList : single linked list 单链表SLTDataType data;  //  一个是存储数据元素的数据域struct SListNode* next;  //   另一个是存储下一个节点地址的指针域
}SLTNode;

        上面的结构体仅是单链表节点的定义，要创建一新的节点需要对里面的数据进行初始化：插入数值，节点指向的下一个节点为空

//创建一个节点
struct SListNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (struct SListNode*)malloc(sizeof(struct SListNode));newnode->data = x;newnode->next = NULL;return newnode;
}

        3.1.2 单链表的头插、尾插

         单链表的尾插

        这里传递的链表节点的参数，为什么是二级指针呢？

        在初始化过程中，需要修改头指针，因此要用到二级指针传递头指针的地址，这样才能修改头指针。这与普通变量类似，当需要修改普通变量的值，需传递其地址。使用二级指针，很方便就修改了传入的结点一级指针的值。 如果用一级指针，则只能通过指针修改指针所指内容，却无法修改指针的值，也就是指针所指的内存块。

//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) { //一级指针传递的为结构体变量地址的值，二级指针接收的是指向结构体变量的指针的地址assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为ppheadif (*pphead == NULL) {*pphead = newnode;return;}//链表不为空，链表的尾指向新节点SLTNode* ptail = *pphead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;
}

         单链表的头插

void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);//链表为空，新节点指向pphead，pphead再指向新节点；链表不为空，新节点指向pphead，pphead再指向新节点SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

         插入完数据后，想要打印以一下链表的数据，通过从头开始一个一个节点地访问数据，并打印，便实现了链表数据的打印。然后看看插入的情况；

//打印链表
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur) {printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

         尾插部分数据，观察打印的结果是否符合预期结果；发现运行结果与预期相符，所以链表的插入操作是没什么大问题的

3.1.3  单链表的头删、尾删

        如果链表为空，不需要删除；如果删除的是第一个结点，则需要将保存链表首地址的指针保存第一个结点的下一个结点的 地址 如果删除的是中间结点，则找到中间结点的前一个结点，让前一个结点的指针域保存这个结 点的后一个结点的地址即可 

         单链表的尾删

void SLTPopBack(SLTNode** pphead) {assert(pphead);//链表为空，不删除assert(*pphead); //指向第一个节点的地址//链表不为空，只有一个节点if ((*pphead)->next = NULL) {free(*pphead);*pphead = NULL;return;}//多个节点，释放最后一个节点，其前驱节点指向空SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next) {prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;
}

         单链表的头删

void SLTPopFront(SLTNode** pphead) {assert(pphead);//链表为空，不删除assert(*pphead);//链表不为空，释放最后一个节点，其前驱节点指向空SLTNode* pcur = *pphead;*pphead = pcur->next;pcur->next = NULL;free(pcur);pcur = NULL;
}

 3.1.4 链表节点的查找

         先对比第一个结点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下 一个结点，如果到达最后一个结点的时候都没有匹配的数据，说明要查找数据不存在

//查找
SLTNode* STLFind(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* pcur = *pphead;while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}

3.1.5 在指定位置插入数据

        在指定位置前插入数据

//在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//头节点不能为空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//当pos节点指向 头节点时,进行头插if (*pphead == pos) {SLTPushFront(pphead, x);return;}//pos pphead不指向同一节点SLTNode* prev = *pphead;while (prev->next != pos) { //找到pos节点的前驱prev = prev->next;}newnode->next = pos;prev->next = newnode;
}

         在指定位置之后插入数据

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

 3.1.6 删除pos之后的节点

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos);assert(pos->next);//pos后不为空SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

3.1.7 销毁链表

        重新定义一个指针next，保存pcur指向节点的地址，然后next后移保存下一个节点的地址，然后释放pcur对应的节点，以此类推，直到pcur为NULL为止 

//销毁链表,由独立的节点构成，需要一个个销毁
void SListDestroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

 四、完整代码

SList.h

 

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//顺序表存在的一定的问题：
//1.顺序表的中间/头部的插入需要挪动数据
//2.扩容存在性能的消耗
//3.会有空间的浪费typedef int SLTDataType;
//链表是由节点构成
//逻辑结构：一定连续；物理结构：不一定连续
//不会造成空间的浪费，由独立的节点构成
typedef struct SListNode {  //SList : single linked list 单链表SLTDataType data;struct SListNode* next;
}SLTNode;//链表的头插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(struct SListNode** pphead, SLTDataType x);//链表的头删、尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//打印链表
void SLTPrint(SLTNode* phead);//查找
SLTNode* STLFind(SLTNode** phead, SLTDataType x);//在指定位置前插入数据
void SLTInsert(SLTNode** phead, SLTNode* pos,SLTDataType x);//删除pos节点
void SLTErase(SLTNode** phead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** phead);

SList.c

#include"SList.h"//创建一个节点
struct SListNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (struct SListNode*)malloc(sizeof(struct SListNode));newnode->data = x;newnode->next = NULL;return newnode;
}//打印链表
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur) {printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//链表的头插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) { //一级指针传递的为结构体变量地址的值，二级指针接收的是指向结构体变量的指针的地址assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为ppheadif (*pphead == NULL) {*pphead = newnode;return;}//链表不为空，链表的尾指向新节点SLTNode* ptail = *pphead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;
}void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);//链表为空，新节点指向pphead，pphead再指向新节点；链表不为空，新节点指向pphead，pphead再指向新节点SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}//链表的头删、尾删
void SLTPopBack(SLTNode** pphead) {assert(pphead);//链表为空，不删除assert(*pphead); //指向第一个节点的地址//链表不为空，只有一个节点if ((*pphead)->next = NULL) {free(*pphead);*pphead = NULL;return;}//多个节点，释放最后一个节点，其前驱节点指向空SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next) {prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;
}
void SLTPopFront(SLTNode** pphead) {assert(pphead);//链表为空，不删除assert(*pphead);//链表不为空，释放最后一个节点，其前驱节点指向空SLTNode* pcur = *pphead;*pphead = pcur->next;pcur->next = NULL;free(pcur);pcur = NULL;
}//查找
SLTNode* STLFind(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* pcur = *pphead;while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}//在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//头节点不能为空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//当pos节点指向 头节点时,进行头插if (*pphead == pos) {SLTPushFront(pphead, x);return;}//pos pphead不指向同一节点SLTNode* prev = *pphead;while (prev->next != pos) { //找到pos节点的前驱prev = prev->next;}newnode->next = pos;prev->next = newnode;
}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(pos);//当pos节点指向 头节点时,进行头删if (*pphead == pos) {SLTPopFront(pphead);return;}//pos pphead不指向同一节点SLTNode* prev = *pphead;while (prev->next != pos) { //找到pos节点的前驱prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos);assert(pos->next);//pos后不为空SLTNode* del = pos->next;pos->next = pos->next->next;//pos->next = del->next;free(del);del = NULL;
}//销毁链表,由独立的节点构成，需要一个个销毁
void SListDestroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}