我们上节学习了顺序表的实现.
顺序表的缺点：
- 任意位置插入或者删除元素的效率低：每次插入或者删除需要搬移元素；
- 考虑空间的大小是否需要开辟空间
以下为顺序表与链表的不同点
链表
链表的概念及其结构
概念：链表是一种物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的 指针链 接次序实现的 。
链表的分类
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然链表的类型很多，但是我们实际中最常用还是两种结构：
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
链表的实现
#pragma once //定义节点的结构 //数据 + 指向下一个节点的指针 typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; void SLTPrint(SLTNode* phead); //尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x); //头插 void SLTPushFront(SLTNode** pphead, SLTDataType x); //尾删 void SLTPopBack(SLTNode** pphead); //头删 void SLTPopFront(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos);
链表形式：
//定义节点的结构 //数据 + 指向下一个节点的指针 typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
节点的创建:
链表是一个个节点连接起来的，所以我们的第一步应该动态申请节点
//开辟新结点 SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL)//判断开辟是否成功 { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; return newnode; }
链表的增删：
尾插
我们先要创建一个存放x的新节点，然后找到节点的尾，在将为节点的next指向新节点
//尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x);//创建一个新节点 if (*pphead==NULL) { *pphead = newnode; } else { //创建一个尾节点，找尾 SLTNode* ptail = *pphead; while (ptail->next) { ptail = ptail->next;//找链表下一个为NULL的地址 } //下一个为NULL，出循环 ptail->next = newnode; } }
头插
头插对于尾插简单不少，先创建新节点，将新节点的next指向头节点，然后将地址赋给头节点
//头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x);//创建一个新节点 if (*pphead == NULL) { *pphead = newnode; } else { newnode->next = *pphead; *pphead = newnode;//头节点为新的节点 } }
尾删
//尾删 void SLTPopBack(SLTNode** pphead) { assert(pphead && *pphead); if ((*pphead)->next == NULL) {//->的优先级高于(); //只存在一个节点 free(*pphead); *pphead = NULL; } else { //找尾节点 SLTNode* pcur = *pphead;//保存尾节点的上一个节点 SLTNode* ptail = *pphead; while (ptail->next) { pcur = ptail; ptail = ptail->next; } free(ptail); ptail = NULL; pcur->next = NULL; } }
头删
//头删 void SLTPopFront(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* pcur = (*pphead)->next; free(*pphead); *pphead = NULL; *pphead = pcur; }
查找
//查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur = phead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } //没有查找到 return NULL; }
打印
void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead; while (pcur) {//pcur!=NULL printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL\n"); }
链表的重点
这是一串链表，在链表中的增删查改，其实是需要关注其节点；
1、尾删：则是需要找到尾节点，进行删除
如果我们将为释放掉，那尾节点的上一个节点，指向哪里，将会沦为野指针，是非常危险的，所以我们得创建一个指针，用来找到这个节点，这就是尾删的重点
2、头删：找到头节点的下一个节点，在删除头节点
与尾删类似，我们需要考虑如果将phead删除，我们如何找到新的头节点
综上所述：链表的难度常常发生在其释放时，指针的丢失或者成为野指针，如果注意其，我们将事半功倍，减少bug的产生；
//在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos); //销毁链表 void SListDesTroy(SLTNode** pphead);
在指定位置之前插入数据
//在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead && *pphead); assert(pos); SLTNode* newnode = SLTBuyNode(x);//创建一个新节点 if (pos == *pphead) { //头插 SLTPushFront(*pphead, x); } else{ SLTNode* prev = *pphead; //找到pos的上个节点 while (prev->next != pos) { prev = prev->next; } newnode->next = pos; prev->next = newnode; } }
在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = SLTBuyNode(x); SLTNode* pcur = pos->next; //保存pos下一个节点，以防节点丢失 pos->next = newnode; newnode->next = pcur; }
删除pos之后的节点
//删除pos之后的节点 void SLTEraseAfter(SLTNode* pos) { assert(pos && pos->next); SLTNode* del = pos->next; pos->next = del->next; free(del); del = NULL; }
链表的摧毁
//销毁链表 void SListDesTroy(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* pcur = *pphead; while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }
总体展示：
#define _CRT_SECURE_NO_WARNINGS #include"slist.h" #include<assert.h> void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead; while (pcur) {//pcur!=NULL printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL\n"); } //开辟新结点 SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; return newnode; } //尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x);//创建一个新节点 if (*pphead==NULL) { *pphead = newnode; } else { //创建一个尾节点，找尾 SLTNode* ptail = *pphead; while (ptail->next) { ptail = ptail->next;//找链表下一个为NULL的地址 } //下一个为NULL，出循环 ptail->next = newnode; } } //头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x);//创建一个新节点 if (*pphead == NULL) { *pphead = newnode; } else { newnode->next = *pphead; *pphead = newnode;//头节点为新的节点 } } //尾删 void SLTPopBack(SLTNode** pphead) { assert(*pphead && pphead); //只有一个节点，直接释放掉 if ((*pphead)->next == NULL) //-> 优先级高于* { free(*pphead); *pphead = NULL; } else { //链表有多个节点 SLTNode* prev = *pphead; SLTNode* ptail = *pphead; while (ptail->next) { prev = ptail; ptail = ptail->next; } free(ptail); ptail = NULL; prev->next = NULL; } } //头删 void SLTPopFront(SLTNode** pphead) { //链表不能为空 assert(pphead && *pphead); SLTNode* next = (*pphead)->next; //-> 优先级高于* free(*pphead); *pphead = NULL; *pphead = next; } //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur = phead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } //没有查找到 return NULL; } //在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead&&*pphead); assert(pos); SLTNode* newnode = SLTBuyNode(x);//创建一个新节点 //如果为头插 if (pos == *pphead) { SLTPushFront(pphead,x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //找到pos的上一个节点 prev->next = newnode; newnode->next = pos; } } //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = SLTBuyNode(x); SLTNode* pcur = pos->next; pos->next = newnode; newnode->next = pcur; } //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead && *pphead); assert(pos); //pos是头结点/pos不是头结点 if (pos == *pphead) { //头删 SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; //减少创建一个节点保存pos->next的节点 free(pos); pos = NULL; } } //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos) { assert(pos && pos->next); SLTNode* del = pos->next; pos->next = del->next; free(del); del = NULL; } //销毁链表 void SListDesTroy(SLTNode** pphead) { assert(pphead&&*pphead); SLTNode* pcur = *pphead; while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }
