前言
作
名言：我可以接收失败，但我不能接收放弃
在前面我们学习了，顺序表(一个连续存储的物理单元，是用数组实现)实现了对数据的增删查改，我们本期将来学习单链表（也实现对数据的增删查改），既然都是对数据增删查改，为什么我们不用顺序表而要弄出个个单链表呢？这就不得不提顺序表的缺陷。
一 顺序表的不足之处
对于顺序表的不足，我们主要从时间复杂度和内存的浪费上考虑。
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
二 链表
概念：
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
1 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向或者双向
带头或者不带头
循环或者非循环
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
下面我们主要研究无头单向非循环链表。
2 单链表 
单链表结构简单，但是又是非常重要的，从图中我们可以看出。
1 从逻辑是单链表是连续的，但是在物理层面是非连续的
2 链表的节点，一般都是从堆区申请的
为了更好的理解单链表，我们将他的功能一一实现。
三 单链表的实现
1 创建三个文件
1 SList.h
在该文件中我们完成，单表的类型定义，接口函数的声明，引用的头文件。
2 SList.c
完成单链表表接口函数的实现
3 Test.c
主函数，测试顺序表各接口的功能
2 SList.h
#pragma once//防止重复头文件被包含 #include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int SLTDataType;//定义节点中数据类型 typedef struct SListNode { SLTDataType data;//指向节点中的数据 struct SListNode* next;//指向下个节点的指针 }SListNode;//注意这里重命名不能在结构体中中生效 //打印单链表 void SListPrint(SListNode* phead); //申请新节点 SListNode* BuySLTNode(SLTDataType x); //单链表销毁 void SListDestory(SListNode** pphead); //单链表头插 void SListPushFort(SListNode** pphead, SLTDataType x); //单链表头删 void SListPopFort(SListNode** pphead); //单链表尾插 void SListPushBack(SListNode** pphead, SLTDataType x); //单链表尾删除 void SListPopBack(SListNode** pphead); //单链表查找 SListNode* SListFind(SListNode* phead, SLTDataType x); //在pos之前插入 void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x); //在pos后插入 void SListInsertAfter(SListNode* pos, SLTDataType x);
这里和顺序表一样就是要定义函数实现单链表的功能。
这里我们重点关注，结构体的定义
typedef int SLTDataType;//定义节点中数据类型 typedef struct SListNode { SLTDataType data;//指向节点中的数据 struct SListNode* next;//指向下个节点的指针 }SListNode;//注意这里重命名不能在结构体中中生效
一个节点中主要包括存储的数据和指向下个节点的指针
3 SList.c
#define _CRT_SECURE_NO_WARNINGS #include"SList.h" //打印单链表 void SListPrint(SListNode* phead) { SListNode* cur = phead;//保存单链表头的地址 while (cur) { printf("%d->", cur->data);//打印链表数据 cur = cur->next;//保存指向下个节点的地址 } printf("NULL\n");//链表最后指向空 } //申请新节点 SListNode* BuySLTNode(SLTDataType x) { SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));//为新节点的数据申请空间 if (NewNode==NULL) { perror("malloc fail");//申请失败报错 exit(-1); } NewNode->data = x;//将为新节点插入数据 NewNode->next = NULL;//将节点指向下个位置的地址置空 return NewNode; } //链表销毁 void SListDestory(SListNode** pphead) { assert(pphead);//断言(plist地址肯定不为空) SListNode* cur = *pphead;//保存好链表头的地址 while (cur) { SListNode* next = cur->next;//将指向一个链的地址记录下来 free(cur);//释放头的空间 cur = next;//指向一个链 } *pphead = NULL;//销毁完毕，单链表内容为空 } //单链表头插 void SListPushFort(SListNode** pphead,SLTDataType x) { assert(pphead);//断言(plist地址肯定不为空) SListNode* NewNode = BuySLTNode(x);//申请一个节点 NewNode->next = *pphead; *pphead = NewNode; } //单链表头删 void SListPopFort(SListNode** pphead) { assert(pphead);//断言(plist地址肯定不为空) //温柔的检测 if (*pphead == NULL)//链表为空就不删除 { return; } //暴力检测 //assert(*pphead!=NULL); SListNode* del = *pphead;//将要删除地址给del *pphead = (*pphead)->next;//plist指向下个链表的头 free(del);//释放要删除的空间 del = NULL; } //单链表尾插 void SListPushBack(SListNode** pphead, SLTDataType x) { assert(pphead);//断言 SListNode* NewNode = BuySLTNode(x);//申请一个节点 //1链表为空 //2联邦不为空 if (*pphead == NULL) { *pphead = NewNode; } else { SListNode* tail = *pphead;//记录链表头的地址 //找尾 while (tail->next != NULL) { tail = tail->next;//不断的指向下个链 } tail->next = NewNode;//尾插入数据 } } //单链表尾删除 void SListPopBack(SListNode** pphead) { assert(pphead);//断言(plist地址肯定不为空) //温柔的检测 if (*pphead == NULL)//链表为空就不删除 { return; } if ((*pphead)->next == NULL)//一个节点 { free(*pphead); *pphead = NULL; } else//多个节点 { SListNode* tail = *pphead;//记录链表头的地址 SListNode* prev = NULL;//置空 //找尾 while (tail->next != NULL) { prev = tail;//保存上个节点的地址 tail = tail->next;//不断的指向下个节点 } prev->next = NULL;//将上个节点的位置置空 free(tail);//释放 tail = NULL; } } //单链表查找 SListNode* SListFind(SListNode* phead, SLTDataType x) { SListNode* cur = phead;//标记头节点 //遍历链表 while (cur) { if (cur->data == x) { return cur;//找到返回标记点 } cur = cur->next; } return NULL;//没找到返回NULL } //在pos之前插入 void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x) { assert(pphead);//断言 assert(pos); if (pos == *pphead)//第一个节点就是pos { SListPushFort(pphead, x);//直接头插 } else//第一个节点不为pos { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next;//不断指向下个节点 // 暴力检查，pos不在链表中.prev为空，还没有找到pos，说明pos传错了 assert(prev); } SListNode* NewNode = BuySLTNode(x);//申请新的节点 prev->next = NewNode;//上个节点的next指向新节点 NewNode->next = pos;//新节点指向pos; } } //在pos后插入 void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos);//断言 //直接插入就行了 SListNode* NewNode = BuySLTNode(x);//申请新的节点 NewNode->next = pos->next;//指向pos后的节点 pos->next = NewNode;//节点pos指向新节点 }
在这里我们主要完成对单链表增删查改函数接口的实现。
我们考虑到要观察储存在单链表中的数据，所以我们首先要实现一个打印单链表的函数。
打印单链表
//打印单链表 void SListPrint(SListNode* phead) { SListNode* cur = phead;//保存单链表头的地址 while (cur) { printf("%d->", cur->data);//打印链表数据 cur = cur->next;//保存指向下个节点的地址 } printf("NULL\n");//链表最后指向空 }
这里我们只要不断的通过cur找到的节点下个数据即可，还要注意中单链表打印完毕后，不要忘记在最后一行打印NULL表示链表到此为止。
在实现单链表的其他功能的前提是我们需要有一个节点。
申请节点
//申请新节点 SListNode* BuySLTNode(SLTDataType x) { SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));//为新节点的数据申请空间 if (NewNode==NULL) { perror("malloc fail");//申请失败报错 exit(-1); } NewNode->data = x;//将为新节点插入数据 NewNode->next = NULL;//将节点指向下个位置的地址置空 return NewNode; }
在这个节点中就一个数据和一个空指针。
有时候当我们不要这个单链表时，我们可以写函数接口来销毁他。
链表销毁
//链表销毁 void SListDestory(SListNode** pphead) { assert(pphead);//断言(plist地址肯定不为空) SListNode* cur = *pphead;//保存好链表头的地址 while (cur) { SListNode* next = cur->next;//将指向一个链的地址记录下来 free(cur);//释放头的空间 cur = next;//指向一个链 } *pphead = NULL;//销毁完毕，单链表内容为空 }
在这里我们只要注意通过free不断释放节点申请的空间即可，顺便提一句，当我们要修改一级指针的值，通常我们要用到二级指针。在测试中我们给SListDestory传的是&plist(plist是一个一级指针)，所以要用二级指针来接收。
下面我们来实现一个简单的头插
单链表的头插
//单链表头插 void SListPushFort(SListNode** pphead,SLTDataType x) { assert(pphead);//断言(plist地址肯定不为空) SListNode* NewNode = BuySLTNode(x);//申请一个节点 NewNode->next = *pphead; *pphead = NewNode; }
这里我们注意节点之间的链接。
有了头插我们中来个头删除吧。
单链表的头删除
//单链表头删 void SListPopFort(SListNode** pphead) { assert(pphead);//断言(plist地址肯定不为空) //温柔的检测 if (*pphead == NULL)//链表为空就不删除 { return; } //暴力检测 //assert(*pphead!=NULL); SListNode* del = *pphead;//将要删除地址给del *pphead = (*pphead)->next;//plist指向下个链表的头 free(del);//释放要删除的空间 del = NULL; }
这里我们要判断链表是否为空，为空就不删除，不为空直接释放头节点就可以，但这里我们注意重新指向下个节点。
写道这里我们还没有测试我们之前写的功能，下面我们测试一下。 
测试很重要(不要全部写完在来测试)
单链表的尾插
//单链表尾插 void SListPushBack(SListNode** pphead, SLTDataType x) { assert(pphead);//断言 SListNode* NewNode = BuySLTNode(x);//申请一个节点 //1链表为空 //2联邦不为空 if (*pphead == NULL) { *pphead = NewNode; } else { SListNode* tail = *pphead;//记录链表头的地址 //找尾 while (tail->next != NULL) { tail = tail->next;//不断的指向下个链 } tail->next = NewNode;//尾插入数据 } }
对于单链表的尾插，我们要分为二种情况：
1 链表为空
为空的直接把新节点赋值给*pphead（plist）即可
2 链表不为空
首先我们要找链表的尾，其次才是插入数据
单链表的尾删
/单链表尾删除 void SListPopBack(SListNode** pphead) { assert(pphead);//断言(plist地址肯定不为空) //温柔的检测 if (*pphead == NULL)//链表为空就不删除 { return; } if ((*pphead)->next == NULL)//一个节点 { free(*pphead); *pphead = NULL; } else//多个节点 { SListNode* tail = *pphead;//记录链表头的地址 SListNode* prev = NULL;//置空 //找尾 while (tail->next != NULL) { prev = tail;//保存上个节点的地址 tail = tail->next;//不断的指向下个节点 } prev->next = NULL;//将上个节点的位置置空 free(tail);//释放 tail = NULL; } }
单链表的尾删的话条件更加复杂一点，我们要考虑链表为空就不删除，链表中为一个节点(不要尾)和链表中多个节点(要找尾)。
下面我们继续测试函数的功能
有了增删，那么我们还要写查和改。
单链表查找
//单链表查找 SListNode* SListFind(SListNode* phead, SLTDataType x) { SListNode* cur = phead;//标记头节点 //遍历链表 while (cur) { if (cur->data == x) { return cur;//找到返回标记点 } cur = cur->next; } return NULL;//没找到返回NULL }
单链表的查的话主要是，遍历链表，找我们查找数据，返回指向该数据的指针就可。
其实查找的功能主要是方便我们能找道pos的地址从而实现对他的前插和后插。
在pos之前插入
//在pos之前插入 void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x) { assert(pphead);//断言 assert(pos); if (pos == *pphead)//第一个节点就是pos { SListPushFort(pphead, x);//直接头插 } else//第一个节点不为pos { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next;//不断指向下个节点 // 暴力检查，pos不在链表中.prev为空，还没有找到pos，说明pos传错了 assert(prev); } SListNode* NewNode = BuySLTNode(x);//申请新的节点 prev->next = NewNode;//上个节点的next指向新节点 NewNode->next = pos;//新节点指向pos; } }
在对pos之前插入我们要考虑许多，首先pos是不能为空的，其实当第一个节点就是pos时,我们直接头插入就可以了，最后当第一个节点不为pos时，就要在判断链表中是pos是否存在。
在pos后插入
//在pos后插入 void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos);//断言 //直接插入就行了 SListNode* NewNode = BuySLTNode(x);//申请新的节点 NewNode->next = pos->next;//指向pos后的节点 pos->next = NewNode;//节点pos指向新节点 }
对于pos后插就简单了，我们直接插入就好。
继续测试
对于修改pos值就不多说了，我们有pos的指针直接改就是了。
单链表就基本功能就都实现了，大家一定要动手多多尝试。
