关于链表的入门，单向链表及其简单的功能的实现（c语言环境）

一.链表的概念

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

二.单向链表的结构

链表是逻辑上连续的，物理结构上非连续，非顺序的储存结构，那么我们就得使它的结构可以满足该条件，这时候就需要指针，用指针来联系起不同的单元结构，形成一条像链子的数据结构。也就是上图的结构。

当然我们也需要一个指向第一个数据结构的指针，可以将其命名为\"SList\"，并在我们未开始在链表中添加数据时，将其置为NULL（空指针）。

这时候就需要定义一个结构体变量，其中包含两种元素，第一种“我们需要储存的元素”；第二种“用来联系不同单元结构的元素（指针）”，这边就以最简单的包含一个int类型和一个指针的结构体来作为基础的例子（对于将SListDataType定义成int，这一步可以使我们在后面想储存别的类型数据的时候可以直接对SListDataType进行修改）

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

三.单向链表的部分功能的实现

现在我们得到一个结构体单元“SLTNode（链表结点）”，那么有了基础的结构体单元后，我们还要尝试着实现一些链表的基本功能

//链表尾部插入void SListPushBack(SLTNode** pphead, SListDataType x);//链表的打印void SListPrint(SLTNode* phead);//链表尾部删除void SListPopback(SLTNode** pphead);//链表头部插入void SListPushFront(SLTNode** phead, SListDataType x);//链表头部删除void SListPopFront(SLTNode** phead);//链表在pos位置的插入xvoid SListInsert(SLTNode** phead, SListDataType pos, SListDataType x);//链表在pos位置的删除void SListErase(SLTNode** phead, SListDataType pos);

三（1）.代码的文件分类

我们在实现这种代码时最好可以将不同用途的代码放置在不同的文件中，如将需要包含的头文件，宏，定义，结构体的创建，函数的声明放在自己创建的头文件中，我这边将其放在“SList.h”中。而具体的函数的实现我将其放在以“SList.c”命名的源文件中，而具体的测试我将其放在“test.c”源文件中。（可以避免代码过于混乱，头文件反复包含等情况）

三（2）.链表尾部插入和删除，及打印的功能实现

三（2）1.指针的衔接和新空间的创建，以及找到我们需要的加入位置（链表的尾插）

#include\"SList.h\"int main(){SLTNode* SList = NULL;SLTNode*(* pSL) = &SList;SListPushBack(pSL, 1);SListPushBack(pSL, 2);return 0;}

关键：为什么使用二级指针

因为假如我们都链表为空链表，那么我们创建新数据时要将最初始的指向链表头的指针和新数据的地址相连，如果只是传入SList，那么函数内接收到的也只是一个值，将其和新空间相连并不能改变函数外的SList指针的指向，所以要能对SList进行修改，就需要我们传入SList的地址，再对其解引用，才可以修改SList

a.空间的创建

//链表内存申请SLTNode* BuyNewSListNode(SListDataType x){SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (newNode == NULL){printf(\"申请内存失败\\n\");exit(-1);}newNode->data = x;newNode->next = NULL;return newNode;}

我们malloc了一个大小足够的空间，并将其强制转换成SLTNode（我们前面定义的结构体）的指针类型，并设置了一个同一类型的指针变量“newNode”来接收它，对其解引用可以将我们要放的新数放置进去，另一个指针变量我们可以置空（防止野指针的出现），当然我们也要考虑到开辟空间失败的情况（一般不会出现），写一个if语句包含一下这种情况，最后我们就创建了一个新的结构体单元

现在我们要做的事情就是将它和其他数据联系起来，这边先实现的是尾插，所以我们只需将我们的newNode传给上一级结构体单元中的指针变量来即可

因为我们后面会用到很多次的空间创建，我们可以将创建空间的功能封装成一个函数，而我们所需要的newNode（新结构体的地址）可以用返回值的形式传回，我们接收后可以进行下一步的连接

b.链表的找尾（和找到其他我们想要的位置）

如果是空链表，既直接可以将newNode赋给SList，，如果链表有内容，我们则需要找到链表的尾部

链表不可以像数组一样可以用单纯的+1来进行寻找下一个结构体，我们则需要通过每个结构体的指针来访问下一个结构体，那么我们到底要访问几次呢？

答案是，访问到直到结构体中的指针为空时

我们可以将pList赋值给一个新的结构体指针变量cur（表示现在的指针指向）（不去轻易的改变最初始的指针位置，因为我们可能还会用到它），并写一个while循环，循环条件是（cur->next !=NULL），每次成功时，将cur->next赋值给cur，以此实现一步一步的向后寻找，当循环结束时，cur就是最后一个结构体的位置

while (tail->next != NULL){tail =tail ->next;}

当然我们也可以将这种方法推广出更多找位置的方式

如找到第i个结构体的位置，已经记录下前后两个结构体的位置

找到第i个结构体，就需要我们循环 i-1 次

int time = 0；for (time = 0;time next;}

要找到前后两个结构体的位置，我们就可以在对cur进行修改前，先将其赋值给另一个指针变量，同理，在它修改后，再由它找到下一个结构体的位置，并赋给另一个指针变量

int time = 0;SLTNode* prev = NULL;SLTNode* aft = NULL;for (time = 0;time next;aft = cur->next;}

c.链表的尾插

到此我们已经创建完新的空间和找到链表的尾部，只要进行连接即可

//链表尾插void SListPushBack(SLTNode** pphead, SListDataType x){if (*pphead == NULL){SLTNode*newNode=BuyNewSListNode(x);*pphead = newNode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail =tail ->next;}SLTNode* newNode = BuyNewSListNode(x);tail->next = newNode;}}

一种情况是链表为空，将newNode赋值给*pphead（传入的SList的地址，解引用，将SList的内容修改，指向新数据空间）

另一种用找尾的方法，找到尾后将两者连接即可

三（2）2.链表的打印

有了链表找尾的知识，解决链表的打印只需要在每次向后的过程中，将结构体中的数据内容打印出来即可

void SListPrint(SLTNode* phead){assert(phead);SLTNode* cur = phead;while (cur != NULL){printf(\"%d->\", cur->data);cur = cur->next;}printf(\"NULL\\n\");}

为了美观，我们可以加上“->”和最后的“NULL”

注意注意，这边我们只需要打印，对内容和指向链表头的指针不进行修改，所以用一级指针找到对应数据即可（二级也可，只是多一步解引用的操作），当然我们还要考虑到链表为空的情况，所以也进行一次断言

三（2）3.链表的尾删

关键点：找到尾部前一个结构体的位置（前面找到我们需要的位置中有对应内容），malloc的空间都释放，前一个结构体中的指针置空

//链表的尾删void SListPopback(SLTNode** pphead){//1.为空//2.只有一个元素//3.有多个元素if (*pphead == NULL){return;}else if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* prev = NULL;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}}

其中有三种情况，分别是没有内容，有一个内容，有许多内容，只需注意一下特殊的没有内容，其他都正常的找位，释放，置空即可

三（3）链表的头部插入和删除

1.链表的头部插入

关键点：创建新的结构体，将新结构体作为第一个和指向链表的指针相连，将新结构体中的指针和原本第一个的结构体的位置相连

用我们前面创建变量的函数，利用其将要插入的值放入，和用其返回值（新结构体的地址），将pList和新结构体相连，并用其地址解引用，找到新结构体的指针变量，将原本第一个结构体的地址赋给它，完成链接

（这边也正是上面保留原本第一个结构体的地址使我们可以完成链接，如果改变了*pphead（传入的二级指针解引用得到的首结构体的地址），再想找回去就难了）

//链表头插void SListPushFront(SLTNode** pphead, SListDataType x){SLTNode* head = *pphead;SLTNode* newNode = BuyNewSListNode(x);*pphead = newNode;newNode->data = x;newNode->next = head;}

2.函数的头删

关键点：第一个结构体的空间的释放和指针置空（不置空也行，因为后面也拿不到这个指针了），pList和第二个结构体的连接

void SListPopFront(SLTNode** pphead){if (*pphead == NULL){return;}SLTNode* head = *pphead;*pphead = (*pphead)->next;free(head);}

这边如果直接释放，就拿不到第二个结构体的地址了，所以还是需要存一下的

三（4）.链表第pos位置的插入和删除

1.第pos位置的插入

关键点：拿到pos前后两个结构体的地址，这两个结构体和新结构体的连接

注意：可能存在的pos=0（头插）或pos=全部个数+1（尾插），和pos全部个数+1（不合规输入）等情况

要想要判断合不合规，首先要计数一下全部都元素个数，这边可以用到我们找尾的那个循环

SLTNode* count = *pphead;int i = 0;while (count != NULL){count = count->next;i++;}

在其中添加一个计数的整形即可

这边判断的条件是（count ！= NULL），这样可以循环满，如果和上面一样是（count->next！=NULL）就会少循环一次，那样 i 初始化为1即可

正常情况 if (pos > 0 && pos <= i + 1)

SLTNode* cur = *pphead;if (pos > 0 && pos <= i + 1){int time = 0;SLTNode* prev = NULL;for (time = 0;time next;}SLTNode* newNode = BuyNewSListNode(x);prev->next = newNode;newNode->next = cur;}

通过循环pos-1次可以定位到pos的位置

而正好如果是i+1的情况，循环结束后的prev指向最后一个结构体的位置，cur指向NULL，正好在下面的链接中也可以使用，所以i+1也是正常的情况

特殊情况 else if (pos == 0)

直接用上面的头插到函数即可（不一定是最优解）

else if (pos == 0){SListPushFront(pphead, x);}

最终结果

//链表在pos位置的插入xvoid SListInsert(SLTNode** pphead, SListDataType pos, SListDataType x){SLTNode* count = *pphead;int i = 0;while (count != NULL){count = count->next;i++;}SLTNode* cur = *pphead;if (pos > 0 && pos <= i + 1){int time = 0;SLTNode* prev = NULL;for (time = 0;time next;}SLTNode* newNode = BuyNewSListNode(x);prev->next = newNode;newNode->next = cur;}else if (pos == 0){SListPushFront(pphead, x);}else{printf(\"输入位置不合法\\n\");}}

2.第pos位置的删除

和第pos位置的插入类似，考虑一下特殊的情况，其他也是上面的知识点拼接，这边就直接给出结果

关键点：特殊情况，结构体的连接

//链表pos的位置删除一个元素void SListErase(SLTNode** pphead, SListDataType pos){SLTNode* count = *pphead;int i = 0;while (count != NULL){count = count->next;i++;}SLTNode* cur = *pphead;if (pos > 0 && pos <= i){int time = 0;SLTNode* prev = NULL;SLTNode* aft = NULL;for (time = 0;time next;aft = cur->next;}free(cur);prev->next = aft;}else if (pos == 0){SListPopFront(pphead);}else{printf(\"输入位置不合法\\n\");}}

四.结果

SList.h

#include#include#includetypedef int SListDataType;typedef struct SListNode{SListDataType data;struct SListNode* next;}SLTNode;//链表尾部插入void SListPushBack(SLTNode** pphead, SListDataType x);//链表的打印void SListPrint(SLTNode* phead);//链表尾部删除void SListPopback(SLTNode** pphead);//链表头部插入void SListPushFront(SLTNode** phead, SListDataType x);//链表头部删除void SListPopFront(SLTNode** phead);//链表在pos位置的插入xvoid SListInsert(SLTNode** phead, SListDataType pos, SListDataType x);//链表在pos位置的删除void SListErase(SLTNode** phead, SListDataType pos);

SList.c

#include\"SList.h\"//链表内存申请SLTNode* BuyNewSListNode(SListDataType x){SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (newNode == NULL){printf(\"申请内存失败\\n\");exit(-1);}newNode->data = x;newNode->next = NULL;return newNode;}//链表的打印void SListPrint(SLTNode* phead){assert(phead);SLTNode* cur = phead;while (cur != NULL){printf(\"%d->\", cur->data);cur = cur->next;}printf(\"NULL\\n\");}//链表尾插void SListPushBack(SLTNode** pphead, SListDataType x){if (*pphead == NULL){SLTNode*newNode=BuyNewSListNode(x);*pphead = newNode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail =tail ->next;}SLTNode* newNode = BuyNewSListNode(x);tail->next = newNode;}}//链表的尾删void SListPopback(SLTNode** pphead){//1.为空//2.只有一个元素//3.有多个元素if (*pphead == NULL){return;}else if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* prev = NULL;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}}//链表头插void SListPushFront(SLTNode** pphead, SListDataType x){SLTNode* head = *pphead;SLTNode* newNode = BuyNewSListNode(x);*pphead = newNode;newNode->data = x;newNode->next = head;}//链表头删void SListPopFront(SLTNode** pphead){if (*pphead == NULL){return;}SLTNode* head = *pphead;*pphead = (*pphead)->next;free(head);}//链表在pos位置的插入xvoid SListInsert(SLTNode** pphead, SListDataType pos, SListDataType x){SLTNode* count = *pphead;int i = 0;while (count != NULL){count = count->next;i++;}SLTNode* cur = *pphead;if (pos > 0 && pos <= i + 1){int time = 0;SLTNode* prev = NULL;for (time = 0;time next;}SLTNode* newNode = BuyNewSListNode(x);prev->next = newNode;newNode->next = cur;}else if (pos == 0){SListPushFront(pphead, x);}else{printf(\"输入位置不合法\\n\");}}//链表pos的位置删除一个元素void SListErase(SLTNode** pphead, SListDataType pos){SLTNode* count = *pphead;int i = 0;while (count != NULL){count = count->next;i++;}SLTNode* cur = *pphead;if (pos > 0 && pos <= i){int time = 0;SLTNode* prev = NULL;SLTNode* aft = NULL;for (time = 0;time next;aft = cur->next;}free(cur);prev->next = aft;}else if (pos == 0){SListPopFront(pphead);}else{printf(\"输入位置不合法\\n\");}}

test.c

#include\"SList.h\"int main(){SLTNode* SList = NULL;SLTNode*(* pSL) = &SList;//SListPushBack(pSL, 1);//SListPushBack(pSL, 2);//这边可以用前面的函数来进行测试return 0;}