C语言数据结构基础-单链表

1.链表概念

在前面的学习中，我们知道了线性表，其中逻辑结构与物理结构都连续的叫顺序表，那么：

链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表

中的指针链接次序实现的。

2.链表组成

单链表元素（节点）由保存的数据和下个单元的地址组成

//结点结构体的定义
struct SListNode{int data;struct SListNode* next;
};

（node就是结点的意思）

国际惯例，我们进行typdef

typedef struct SListNode{int data;struct SListNode* next;
}SLTNode;

那么此时我们可不可以在其中定义next的时候也用SLTNode呢？

SLTNode* next;

当然是不可以的，此时使用的SLTNode还未被定义，编译器还未能识别，使用了就会报错

为什么要用malloc开辟空间？

为了之后删除（使用free函数释放指针指向的空间）的时候方便，进行初始化时用malloc给每一个节点开辟空间

3.单链表各功能的实现

为了便于链表结点的创建和初始化，我们将其初始功能进行封装

SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->next = NULL;newnode->data = x;return newnode;
}

1.尾差

基于顺序表的经验，大概分为两种情况，一种是链表为空，另一种是链表不为空

我们首先传入该链表的头节点，通过直接链接或者先遍历再链接。

传一个指针进函数，对指针进行操作（每一个结点都有元素与其指针等级），那么以上函数就算传值调用，并不能让phead真正等于newnode

此处的传指针就是传值调用，指针作为变量来修改，就应该传指针的地址，才能达到传址调用的目的。

传递一个指针，可以在函数内部直接修改该指针指向空间的内容，但是想修改、操作传递来的指针，就必须传该指针的指针，才能通过该指针的指针来修改指针的内容。

先让创建的新结构体的next找到现在的phead(也就是*pphead,因为函数中不再存在phead这个变量)

再把现在处于第一个的结构体（我们刚刚自己创建的newnode）的地址给到phead

形参是实参的拷贝。

void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL) {*pphead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail就是尾节点ptail->next = newnode;
}

为了便于主函数的调用和检验，我们写出能打印其数据的函数

void SLTPrint(SLTNode* phead) {assert(phead);SLTNode* pos = phead;while (pos) {printf("%d->",pos->data);pos = pos->next;}printf("NULL");
}

这样就能检验我们的尾插功能了。

2.头插

此处同理，我们任然需要传一个二级指针，通过二级指针对链表进行修改。

依然是分两种情况，实现如下：

void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//若为空if (*pphead == NULL) {*pphead = newnode;return;}//链接newnode 和 *ppheadnewnode->next = *pphead;*pphead = newnode;
}

能否调换以下两句的顺序？

当然不行，否则新节点将自己的地址赋给了自己的next。

由此可见，链表的实现，重在理清个节点之间的链接顺序。

3.尾删

释放空间，让原本倒数第二个结点的next指向NULL（先free，再置NULL）

多个节点时，我们需要先遍历链表找到最后一个节点的前驱节点ptail（原来的倒数第二个节点），删除最后一个节点的同时改变前驱节点的next的值

但如果只有一个节点呢？

if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;return;
}

所以直接先free再置NULL即可 ,但请注意->和*的优先级不同，箭头是最高优先级，所以需要使用括号

void SLTPopBack(SLTNode** pphead) {assert(pphead);//没有节点时assert(*pphead);//只有一个节点时if ((*pphead)->next) {free(*pphead);*pphead = NULL;return;}//多个节点时SLTNode* ptail = *pphead;while (ptail->next->next) {//很明显，只有一个节点的时候过不了，那么我们就需要在多个节点之前写出只有一个节点的情况ptail = ptail->next;}free(ptail->next);ptail->next = NULL;
}

尽管看上去是先写的一个节点，再写的多个节点，但正常逻辑应该是先写多个（通常情况）再考虑一个（特殊情况）

tips：

遍历链表与找链表尾结点是不一样的

（补充一下遍历链表的方法）

SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{prev = ptail;ptail = ptail->next;
}

4.头删

如果链表已经为空的话应该直接退出，所以依然分三种情况考虑

void SLTPopFront(SLTNode** pphead) {assert(pphead);//没有节点 一个节点 多个节点assert(*pphead);SLTNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);tmp = NULL;//发现此时一个节点和多个节点都能通过这段代码
}

依然是处理pphead和pphead->next的关系，此处又有一个小技巧，如过发现不能很好的直接通过等式调整各个指针所指向的位置，可以通过建立新的变量拷贝需要处理的数据。

5.指定位置前后的插入

为了能找到指定的位置，我们先写出一个查找函数

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {assert(phead);while (phead->next) {if (phead->data == x) {return phead;}phead = phead->next;}//没有找到return NULL;
}

为什么要断言链表不为空？因为如果链表为空，传进来的pos也必须为空，矛盾。

pos应当是已知链表（首节点地址为*pphead的）一个具体特定结点，而非NULL

当然，此处也可以不传二级指针只传一级指针，因为我们也可以不需要对传入的指针进行操作，但是为了接口的一致性，也可以都使用二级指针接口

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next=newnode;
}void SLTInsertBefore(SLTNode* phead, SLTNode* pos, SLTDataType x) {assert(pos);assert(phead);if (pos == phead) {SLTPushFront(&phead, x);return;}SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = phead;while (prev->next != pos) {prev = prev->next;}newnode->next = pos;prev->next = newnode;}

为什么在指定位置前插入数据需要头结点的位置，而指定位置后的不需要呢（指定位置之前插入需要三个参数，指定位置之后插入需要两个参数）？

因为根据单链表的特性，除了最后一个节点，所有节点都能通过自己找到下一个节点，但是找不到上一个节点，所以当我们需要再指定位置之前插入数据时，就需要遍历链表来找到指定位置。

6.删除指定位置之后的节点

此处的条件为pos->next不为空，具体操作就是链接pos,pos->next,pos->next->next之间的关系

void SLTEraseAfter(SLTNode* pos) {assert(pos);if (pos->next == NULL) {return;}//pos pos->next pos->next->nextSLTNode* tmp = pos->next;pos->next = pos->next->next;free(pos->next);pos->next == NULL;
}

7.删除指定位置的节点

同理

void SLTErase(SLTNode* phead, SLTNode* pos) {assert(phead);assert(pos);//刚好是头则执行头删if (phead == pos) {SLTPopFront(&phead);return;}while (phead->next != pos) {phead = phead->next;}phead->next = pos->next;free(pos);pos = NULL;
}

6,7检测如下