顺序表遗留下来的问题
- 中间/头部的插⼊删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容⼀般是呈2倍的增长，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到
200，我们再继续插入了5个数据，后⾯没有数据插入了，那么就浪费了95个数据空间。
那么如何解决以上问题呢？
那这个时候我们就要开始我们的链表专题了~~
链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。
- 链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。
- 车厢是独立存在的，且每节车厢都有车门。想象一下这样的场景，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾？
最简单的做法：每节车厢里都放一把下一节车厢的钥匙。
在链表里，每节“车厢”是什么样的呢？我们来看下面：
- 与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”
- 节点的组成主要有两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。
- 图中指针变量 plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希望plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFA0。
- 为什么还需要指针变量来保存下一个节点的位置？
- 链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。
- 结合前面学到的结构体知识，我们可以给出每个节点对应的结构体代码：
假设当前保存的节点为整型：
struct SListNode { int val; struct SListNode* next; }
- 当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个节点的地址（当下一个节点为空时保存的地址为空）。
- 当我们想要从第一个节点走到最后一个节点时，只需要在前一个节点拿上下一个节点的地址（下一个节点的钥匙）就可以了。
给定的链表结构中，如何实现节点从头到尾的打印？
思考：当我们想保存的数据类型为字符型、浮点型或者其他自定义的类型时，该如何修改？
补充说明：
1、链式机构在逻辑上是连续的，在物理结构上不一定连续
2、节点一般是从堆上申请的
3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续
单链表的实现
我们老样子，先来定义结构体，要用的头文件引入~~
头文件
SList
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int SLNDataType; typedef struct SListNode { SLNDataType val; struct SListNode* next; }SLNode;
我们要实现哪些功能呢？
//打印 void SLTPrint(SLNode* phead); //尾插 void SLTPushBack(SLNode** pphead, SLNDataType x); //头插 void SLTPushFront(SLNode** pphead, SLNDataType x); //尾删 void SLTPopBack(SLNode** pphead); //头删 void SLTPopFront(SLNode** pphead); //查找 SLNode* SListFind(SLNode** phead, SLNDataType x); //在指定位置之前插入数据 void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x); //删除pos节点 void SLTErase(SLNode** pphead, SLNode* pos); //在指定位置之后插入数据 void SLTInsertAfter(SLNode* pos, SLNDataType x); //删除pos之后的节点 void SLTEraseAfter(SLNode* pos); //销毁链表 void SListDesTroy(SLNode** pphead);
好接下来我们开始实现~~
SList.c
打印
- 这个很好实现
void SLTPrint(SLNode* phead) { //将头节点的地址保存到cur中 SLNode* cur = phead; while (cur != NULL) { printf("%d-> ", cur->val); //cur是保存下一个节点的地址 cur = cur->next; } printf("NULL\n"); }
- 我们来测试一下，这里链表中什么都没有，我们可以自己手动创造几个数据
slttest1() { //测试打印 SLNode* node1 = (SLNode*)malloc(sizeof(SLNode)); node1->val = 1; SLNode* node2 = (SLNode*)malloc(sizeof(SLNode)); node2->val = 2; SLNode* node3 = (SLNode*)malloc(sizeof(SLNode)); node3->val = 3; SLNode* node4 = (SLNode*)malloc(sizeof(SLNode)); node4->val = 4; node1->next = node2; node2->next = node3; node3->next = node4; node4->next = NULL; SLNode* plist = node1; SLTPrint(plist); }
- 可以看到是可以打印出来的~~
尾插
- 这里的尾插是不是需要先申请空间，然后再将申请出来的空间赋值
- 还需要先判断链表为不为，如果是空，就将新开辟的空间赋给头
- 下面是代码：
- 扩容我们后面可能还要用，所以我们就给他分装成一个函数
//开辟空间 SLNode* CreateNode(SLNDataType x) { //malloc一个新的空间 SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } //申请出来的空间直接赋值 newnode->val = x; //下一个next赋值为空 newnode->next = NULL; //返回一个新的空间 return newnode; }
void SLTPushBack(SLNode** pphead, SLNDataType x) { assert(pphead); //这里申请空间 SLNode* newnode = CreateNode(x); //判断头是否为空，如果为空，就将新开辟的空间赋给头 if (*pphead == NULL) { *pphead = newnode; } else { //将头指向变量尾 SLNode* tail = *pphead; //找尾 while (tail->next != NULL) { //找到了尾然后继续 tail = tail->next; } //把那个返回的空间赋值给尾的next tail->next = newnode; } }
头插
- 这里先申请节点，然后让新的节点和头节点连接起来，最后再让新的节点成为头节点
- 这里如果链表为空也是可以完成任务的~~
void SLTPushFront(SLNode** pphead, SLNDataType x) { //申请节点 SLNode* newnode = CreateNode(x); //让新节点跟头节点连接起来 newnode->next = *pphead; //让新的节点成为头节点 *pphead = newnode; }
- 可以看到，头插~~
尾删
- 首先找尾，然而找尾就要找到前一个节点，掷为空，然后再进行
free - 链表为空的时候不能尾删
void SLTPopBack(SLNode** pphead) { assert(pphead); assert(*pphead); //当前链表只有一个节点的时候 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { //定义一个快慢指针 SLNode* ptail = *pphead; SLNode* prev = NULL; //ptail的next不等于NULL就一直找 while (ptail->next != NULL) { //将ptail的地址赋给慢指针prev prev = ptail; //ptail继续往下找 ptail = ptail->next; } free(ptail); prev->next = NULL; } }
头删
- 使用临时节点指向头节点
- 然后将头节点指向新的头
- 把临时指针指向的节点释放掉
void SLTPopFront(SLNode** pphead) { assert(pphead); assert(*pphead); //定义一个临时指针，将第二个节点赋值给临时指针 SLNode* next = (*pphead)->next; //释放头节点 free(*pphead); //将临时节点变成头节点 *pphead = next; }
查找
- 这里我们传地址就是要保持接口的一致性
- 所以我们这里写二级指针
- 这里很简单，不再介绍
SLNode* SListFind(SLNode** pphead, SLNDataType x) { assert(phead); SLNode* pcur = *phead; while (pcur != NULL) { if (pcur->val == x) { return pcur; } pcur = pcur->next; } return NULL; }
在指定位置之前插入数据
- 在插入前，我们要向申请一块空间
- 先找到要插入的地方前一个节点
- 处理前一个和后一个的连接关系~~
- 链表不能为空，pos也不能为空
- 还要处理只有一个节点和只有一个节点的情况下，直接将新申请下来的节点赋给头
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x) { assert(pphead); //链表不能为空，pos也不能为空 assert(pos); assert(*pphead); SLNode* node = CreateNode(x); //处理只有一个节点和只有一个节点的情况下，直接将新申请下来的节点赋给头 if ((*pphead)->next == NULL || pos == *pphead) { node->next = *pphead; *pphead = node; return; } SLNode* prev = *pphead; //找pos的前一个节点 while (prev->next != pos) { prev = prev->next; } //连接 node->next = pos; prev->next = node; }
在指定位置之后插入数据
- 这里可以直接申请空间后赋值，然后直接连接~~
void SLTInsertAfter(SLNode* pos, SLNDataType x) { assert(pos); SLNode* node = CreateNode(x); //连接 node->next = pos->next; pos->next = node; }
删除pos节点
- 首先找到前一个节点，将next的指针指向下一个，再把pos的节点删除~~
- 当也要判断pos是不是头
void SLTErase(SLNode** pphead, SLNode* pos) { assert(pphead); assert(*pphead); assert(pos); //判断pos是不是头 if (pos == *pphead) { *pphead = (*pphead)->next; free(pos); return; } //找pos的前一个节点 SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; }
删除pos之后的节点
- 首先要将pos的节点保存下来，然后改变pos的指向，最后释放
void SLTEraseAfter(SLNode* pos) { assert(pos && pos->next); SLNode* del = pos->next; pos->next = del->next; free(del); del = NULL; }
销毁链表
- 销毁节点之前，要把下一个节点保存起来，然后找下一个free，句许循环
void SListDesTroy(SLNode** pphead) { assert(pphead); SLNode* pcur = *pphead; while (pcur != NULL) { SLNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }
源码
//打印 void SLTPrint(SLNode* phead) { assert(phead); SLNode* end = phead; while (end != NULL) { printf("%d->", end->val); end = end->next; } printf("NULL\n"); } SLNode* CreateNode(SLNDataType x) { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { perror("malloc fail\n"); return -1; } newnode->next = NULL; newnode->val = x; return newnode; } //尾插 void SLTPushBack(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* newnode = CreateNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } //头插 void SLTPushFront(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* newnode = CreateNode(x); if (*pphead == NULL) { *pphead = newnode; } else { newnode->next = *pphead; *pphead = newnode; } } //尾删 void SLTPopBack(SLNode** pphead) { assert(pphead); assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { //定义一个快慢指针 SLNode* ptail = *pphead; SLNode* prev = NULL; //ptail的next不等于NULL就一直找 while (ptail->next != NULL) { //将ptail的地址赋给慢指针prev prev = ptail; //ptail继续往下找 ptail = ptail->next; } free(ptail); prev->next = NULL; } } //头删 void SLTPopFront(SLNode** pphead) { assert(pphead); assert(*pphead); SLNode* cur = (*pphead)->next;; free(*pphead); *pphead = cur; } //查找 SLNode* SListFind(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* cur = *pphead; while (cur != NULL) { if (cur->val == x) { return cur; } cur = cur->next; } return NULL; } //在指定位置之前插入数据 void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x) { assert(pphead); assert(pos); SLNode* newnode = CreateNode(x); if (*pphead == NULL || pos == *pphead) { newnode->next = *pphead; *pphead = newnode; return; } SLNode* next = pos; SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = next; } //删除pos节点 void SLTErase(SLNode** pphead, SLNode* pos) { assert(pphead); assert(*pphead); assert(pos); if (*pphead == pos) { free(*pphead); pphead = NULL; return; } SLNode* next = pos->next; SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } free(pos); pos = NULL; prev->next = next; } //在指定位置之后插入数据 void SLTInsertAfter(SLNode* pos, SLNDataType x) { assert(pos && pos->next); SLNode* newnode = CreateNode(x); SLNode* cur = pos->next; pos->next = newnode; newnode->next = cur; } //删除pos之后的节点 void SLTEraseAfter(SLNode* pos) { assert(pos); SLNode* del = pos->next; SLNode* cur = del->next; pos->next = cur; free(del); del = NULL; } //销毁链表 void SListDesTroy(SLNode** pphead) { assert(pphead); assert(*pphead); SLNode* pcur = *pphead; if (pcur == NULL) { SLNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }
