一、前言
前面我们学习了数据结构中的顺序表，知道了顺序表的空间是连续存储的，这与数组非常类似，为我们随机访问数据提供了便利的条件，但顺序表也有着一些不足之处：
- 尾部插入删除效率还不错，中部或者头部插入删除需要挪动数据，效率低下。
- 顺序表满了以后需要扩容，扩容本身也有一定的消耗。
- 扩容存在空间浪费：一次扩的多了容易造成浪费，一次扩的少了可能要频繁扩容。
这些大大增加我们的时间与空间成本。为了解决这个问题，就要学习我们今天要讲解的链表。
二、什么是链表
2.1 链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。与顺序表不同，链表的存储数据在内存是随机分布的。
链表是由一个个结点组成的，结点如下图所示：
注意：链表中的最后一个结点的next指向空，next=NULL，一个个结点串成了链表：
2.2 链表的分类
链表的种类多种多样，它们大致可以分为三类：
2.2.1 单向或双向
2.2.2 带不带头结点
2.2.3 循环不循环
三、单链表的基本操作
单链表的基本操作包括单链表的初始化、判断空链表、销毁、清空以及求表长这些较为简单的操作，还有更为重要的单链表的取值、按值查找返回元素所在地址、按值查找返回元素所对应序号、结点插入和删除以及头插法和尾插法建立单链表。目前只实现了这些操作，并进行的测试。
3.1 单链表的初始化
单链表的结点定义方式与我们以往定义的方式都不同，它是一个结构体中包含两个成员。一个是存储数值，一个存放下一个结点的地址。
typedef int SLTDataType; typedef struct SList { SLTDataType val; struct SList* next;//下一个结点的地址 }SLT;
3.2 创建一个新结点
后面我们要在单链表中进行头插和尾插，此时插入的不再是像顺序表一样简单的SLDateType数据了，而是一个结点，这个结点是包括SLTDateType数据以及SLTDateType*的指针，因此，为了方便和减少代码的重复度，我们另写一个函数用来专门创建新结点。
SLT* CreateNode(SLTDataType x) { SLT* newnode = (SLT*)malloc(sizeof(SLT)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; //原本指向下一个结点的指针放在插入的结点的里面 //尾插是newnode->next = NULL //尾插中经过while循环，tail->next == NULL newnode->next = NULL; return newnode; }
3.3 打印单链表
注意：链表和顺序不同的是，顺序表传过来的指针是肯定不会为空的，而链表传过来的指针是可能为空的，比如说当链表中没有元素时，头指针所指向的就是NULL，如果在第一行写上断言就会有问题。
void SLTPrint(SLT* phead)//初位置的指针 { SLT* tail = phead;//指向链表的第一个结点（结构体） //遍历链表 while (tail != NULL)//尾结点的next为空，tail指向尾结点 { printf("%d->", tail->val); tail = tail->next; } printf("NULL\n"); }
3.4 单链表尾插
注意：在创建结点时，已经让 结点.next=NULL，所以不需要在插入完结点后，再让新结点的next指针为NULL。
有人可能会有疑问，为什么之前打印链表的时候不用断言指针，而在尾插时就要断言指针，以及为什么函数的形参是二级指针，而不使用一级指针。
因为，尾插分为两种情况:
- 当链表为空时，头指针phead指向NULL，尾插相当于头插，此时要改变phead的指向，让phead指向这个新结点，此时就需要二级指针来改变一级指针的值（如果我们用一级指针做形参，形参的改变不会影响实参，那么一级指针phead就不会被改变）。
- 至于这个什么时候要断言指针，什么时候不用断言指针：
- 一级指针也就是phead，当链表为空的时候，phead就是为NULL，phead存在为空的可能。
- 而二级指针永远指向phead，phead的地址是永远存在的，那么pphead就一定不可能为空，所以需要断言pphead。
void SLTpushback(SLT** pphead, SLTDataType x) { assert(pphead); SLT* newnode = CreateNode(x);//新结点的地址 if (*pphead == NULL)//改变结构体的指针（二级指针） { *pphead = newnode; } else { SLT* tail = *pphead; while (tail->next != NULL)//tail->next,当链表为空会解引用空指针 { tail = tail->next; } //下一个结构体的指针被存放在结构体成员里面 //可以使用一级指针访问结构体的成员来间接访问下一个结构体的指针 //第一个结点的结构体的指针没有存放，所以要用二级指针 tail->next = newnode;//修改结构体的内容（一级指针） } }
3.5 单链表头插
头插没什么好说的，记住要断言*pphead，保证链表内容不为空，头删也同理。
void SLTpushfront(SLT** pphead, SLTDataType x) { assert(pphead); SLT* newnode = CreateNode(x); newnode->next = *pphead; *pphead = newnode; }
3.6 单链表尾删
要想删除链表中的元素，就必须保证原链表就有元素，因此要断言assert(*pphead)。
尾删需要分情况去讨论：
void SLTpopback(SLT** pphead) { assert(pphead); assert(*pphead); SLT* tail = *pphead; if (tail->next == NULL)//只有一个结点 { free(*pphead); *pphead = NULL; } else { while (tail->next->next != NULL)//tail指向的结点后面第二个不为空 { tail = tail->next; } free(tail->next); tail->next = NULL; } }
3.7 单链表头删
void SLTpopfront(SLT** pphead) { assert(pphead); assert(*pphead); SLT* tail= *pphead; *pphead = tail->next; free(tail); tail = NULL; }
3.8 单链表的查找
这个函数返回值不再是void，而是SListNode*，把找到的结点的地址返回去，这个函数一般会跟结点插入删除之类的函数一起使用。
SLT* SLTfind(SLT* phead, SLTDataType x) { SLT* cur = phead; while (cur) { if (cur->val == x) { return cur; } else { cur = cur->next; } } return NULL; }
3.9 单链表任意位置插入
void SLTInsert(SLT** pphead, SLT* pos, SLTDataType x) { assert(pphead); //pphead 是二级指针，不会为空 //*pphead == NULL 链表为空 //要么都为空，要么都不为空 assert((pos && *pphead)||(!pos && !(*pphead))); if (*pphead == NULL) { SLTpushfront(pphead, x); } else { SLT* prve = *pphead; while (prve->next != pos) { prve = prve->next; } SLT* newnode = CreateNode(x); prve->next = newnode; newnode->next = pos; } }
3.10 单链表任意位置删除
这里我要提醒一下，千万不要忘记判断pos是否正确，不要只单单断言pos是否为NULL，还要判断能不能在链表中找到pos这个地址。
void SLTErase(SLT** pphead, SLT* pos) { assert(pphead); assert(*pphead); assert(pos); if (*pphead == pos) { SLTpopfront(pphead); } else { SLT* prve = *pphead; while (prve->next != pos) { prve = prve->next; } prve->next = pos->next; free(pos); } }
3.11 单链表的销毁
销毁链表这一块，咱可不敢直接free(phead)，因为链表在物理结构上是不连续存储的，销毁链表必须要一个结点一个结点去销毁！！！！最后不要忘记把phead置为NULL。
void SLTDestory(SLT** pphead) { assert(pphead); SLT* cur = *pphead; while (cur) { //方法一： //cur = cur->next; //free(*pphead);//释放掉了phead的空间 //*pphead = cur; SLT* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
四、完整代码
4.1 SLT.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDataType; typedef struct SList { int val; struct SList* next;//下一个结点的地址 }SLT; void SLTPrint(SLT* phead);//打印链表 SLT* CreateNode(SLTDataType x, SLT* tail);//创建一个新结点 void SLTpushback(SLT** pphead, SLTDataType x);//尾插 void SLTpushfront(SLT** pphead, SLTDataType x);//头插 void SLTpopback(SLT** pphead); void SLTpopfront(SLT** phead); SLT* SLTfind(SLT* phead, SLTDataType x); //与find函数结合使用 //在pos前面插入 void SLTInsert(SLT** pphead, SLT* pos, SLTDataType x); //删除pos位置 void SLTErase(SLT** pphead, SLT* pos); void SLTDestory(SLT** pphead);//销毁
4.2 SLT.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include"SList.h" SLT* CreateNode(SLTDataType x) { SLT* newnode = (SLT*)malloc(sizeof(SLT)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; //原本指向下一个结点的指针放在插入的结点的里面 //尾插是newnode->next = NULL //尾插中经过while循环，tail->next == NULL newnode->next = NULL; return newnode; } void SLTPrint(SLT* phead)//初位置的指针 { SLT* tail = phead;//指向链表的第一个结点（结构体） //遍历链表 while (tail != NULL)//尾结点的next为空，tail指向尾结点 { printf("%d->", tail->val); tail = tail->next; } printf("NULL\n"); } void SLTpushback(SLT** pphead, SLTDataType x) { assert(pphead); SLT* newnode = CreateNode(x);//新结点的地址 if (*pphead == NULL)//改变结构体的指针（二级指针） { *pphead = newnode; } else { SLT* tail = *pphead; while (tail->next != NULL)//tail->next,当链表为空会解引用空指针 { tail = tail->next; } //下一个结构体的指针被存放在结构体成员里面 //可以使用一级指针访问结构体的成员来间接访问下一个结构体的指针 //第一个结点的结构体的指针没有存放，所以要用二级指针 tail->next = newnode;//修改结构体的内容（一级指针） } } void SLTpushfront(SLT** pphead, SLTDataType x) { assert(pphead); SLT* newnode = CreateNode(x); newnode->next = *pphead; *pphead = newnode; } void SLTpopback(SLT** pphead) { assert(pphead); assert(*pphead); SLT* tail = *pphead; if (tail->next == NULL)//只有一个结点 { free(*pphead); *pphead = NULL; } else { while (tail->next->next != NULL)//tail指向的结点后面第二个不为空 { tail = tail->next; } free(tail->next); tail->next = NULL; } } void SLTpopfront(SLT** pphead) { assert(pphead); assert(*pphead); SLT* tail= *pphead; *pphead = tail->next; free(tail); tail = NULL; } SLT* SLTfind(SLT* phead, SLTDataType x) { SLT* cur = phead; while (cur) { if (cur->val == x) { return cur; } else { cur = cur->next; } } return NULL; } void SLTInsert(SLT** pphead, SLT* pos, SLTDataType x) { assert(pphead); //pphead 是二级指针，不会为空 //*pphead == NULL 链表为空 //要么都为空，要么都不为空 assert((pos && *pphead)||(!pos && !(*pphead))); if (*pphead == NULL) { SLTpushfront(pphead, x); } else { SLT* prve = *pphead; while (prve->next != pos) { prve = prve->next; } SLT* newnode = CreateNode(x); prve->next = newnode; newnode->next = pos; } } void SLTErase(SLT** pphead, SLT* pos) { assert(pphead); assert(*pphead); assert(pos); if (*pphead == pos) { SLTpopfront(pphead); } else { SLT* prve = *pphead; while (prve->next != pos) { prve = prve->next; } prve->next = pos->next; free(pos); } } void SLTDestory(SLT** pphead) { assert(pphead); SLT* cur = *pphead; while (cur) { //方法一： //cur = cur->next; //free(*pphead);//释放掉了phead的空间 //*pphead = cur; SLT* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
