网站建设图片如何加载,济南网站建设培训班,保定网站建设方法,建网站都有什么语言#x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前学习C和算法 ✈️专栏#xff1a;数据结构 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章对你有帮助的话 欢迎 评论#x1f4ac; 点赞… 个人主页Weraphael ✍作者简介目前学习C和算法 ✈️专栏数据结构 希望大家多多支持咱一起进步 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注 前景回顾 上期讲解了顺序表虽然它的尾插和尾删的时间复杂度都是O(1)但还是存在一些缺陷的比如中间和头部插入数据效率低下还会存在一定的空间浪费等。现在我们来看看链表是否能解决顺序表的缺陷。 目录前景回顾一、概念二、链表的结构三、链表的分类四、链表的实现4.1 准备工作4.2 接口4.3 单链表之动态申请一个节点4.4 单链表之打印4.5 单链表之尾插4.6 单链表之头插4.7 单链表之尾删4.8 单链表之头删4.9 单链表之查找4.10 单链表之在pos之前插入x4.11 单链表之删除指定pos结点4.12 单链表之在pos位置之后插入x4.13 单链表之删除pos位置之后的结点4.14 单链表之结点释放五、总结一、概念 链表是一种物理存储结构上非连续的存储结构数据元素的逻辑顺序是通过链表中的指针链接来实现的 二、链表的结构
物理结构 物理结构就是数据在内存中实实在在的变化。我们通常把一小块的内存空间称为结点而显示中的结点一般都是从堆上申请的。链表之所以能链接起来主要是因为上一个结点存储着下一个结点的地址。然而在平时做题的时候不可能把图画的这么详细因此引入了逻辑结构。 逻辑结构 逻辑结构是为了方便理解形象画出来的。(一般分析都画逻辑结构) 三、链表的分类 实际中的链表的结构非常多样以下情况组合起来就有8种结构 1. 单向或者双向 2. 带头哨兵位或者不带头 带哨兵位的头结点是不存储有意义数据的 3. 循环或者非循环 总结 虽然有这么多的链表结构但是最常用是以下这两种 不带头单向非循环链表 带头双向循环链表 四、链表的实现
4.1 准备工作 为了方便管理我们可以创建多个文件来实现 test.c - 测试代码逻辑 源文件SList.c - 动态的实现 源文件SList.h - 存放函数的声明 头文件 4.2 接口
【SList.h】
typedef int SLTDateType;//定义结构体
typedef struct SListNode
{SLTDateType data; struct SListNode* next;//存储下一个结点的地址
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
//单链表在pos之前插入x
void SListInsert(SListNode** plist,SListNode* pos,SLTDateType x);
//单链表删除指定pos结点
void SListErase(SListNode** plist,SListNode* pos);
//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
//结点释放
void SListDestroy(SListNode** plist);4.3 单链表之动态申请一个节点
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(newnode :: malloc);return NULL;}newnode-next NULL;newnode-data x;return newnode;
}其实这个接口可以不用写写出来是因为后面的尾插、头插等需要向内存申请空间然而为了减少代码量因此就多了这个接口。 4.4 单链表之打印
// 单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur plist;while (cur) //cur ! NULL{printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}【笔记总结】 为什么不断言plist结点 因为空链表是可以打印的。为什么不直接拿plist遍历 首先拿plist遍历肯定是没有问题的但是为了保存头结点最好还是新建一个结点遍历。cur cur-next 千万不能写成 cur 原因是链表在内存空间上是不连续的。 4.5 单链表之尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);//向内存申请空间SListNode* newnode BuySListNode(x);//当空链表为空 -- 赋值if (*pplist NULL){*pplist newnode;}//不为空 -- 找到尾节点再链接else{SListNode* tail *pplist;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}【笔记总结】 为什么要二级指针 首先pplist一开始是指向头结点的当pplist指向NULL时尾插时就要改变头结点如果不是二级指针即使修改了头结点尾插后pplist还是指向NULL不变为什么断言pplist而不断言*pplist 不断言*pplist是因为空链表可以尾插 断言pplist是因为pplist其实存储的是*pplist的地址即使*pplist NULL但pplist绝对不可能为NULL。 4.6 单链表之头插
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pplist);//向内存申请空间SListNode* newnode BuySListNode(x);//头插newnode-next *pplist;*pplist newnode;}【常见错误】 头插过程特别容易出错少部分人可能会写成 *pplist newnode newnode-next *pplist 如果这么写就大错特错了原因是如果这么写就找不到原来的头结点了 4.7 单链表之尾删
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist); //空链表不能尾删//如果链表中只有一个结点直接释放if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else{//尾插过程SListNode* prev NULL;SListNode* tail *pplist;//找尾结点while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}【笔记总结】 要断言*pplist因为空链表是不能尾删。为什么还要定义prev 首先即使找到了尾结点并把尾结点释放掉但在尾结点释放之前并没有把尾结点的前一个结点的next掷为NULL。所以定义prev是为了找到原尾结点的前一个结点。 4.8 单链表之头删
// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);//空链表不能头删SListNode* first *pplist;*pplist first-next;free(first);
}【动图展示】 4.9 单链表之查找
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur plist;while (cur){if (cur-data x){return cur;}}//遍历完还是没找到return NULL;
}4.10 单链表之在pos之前插入x
//单链表在pos之前插入x
void SListInsert(SListNode** plist, SListNode* pos, SLTDateType x)
{assert(plist);assert(pos);//开个新节点SListNode* newnode BuySListNode(x);//如果pos指向头结点相当于头插if (pos *plist){SListPushFront(plist, x);}else{//找到pos前一个位置SListNode* prev *plist;while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;}
}【动图展示】 4.11 单链表之删除指定pos结点
//单链表删除指定pos结点
void SListErase(SListNode** plist, SListNode* pos)
{assert(plist);assert(pos);//pos指向头结点相当于头删if (*plist pos){SListPopFront(plist);}else{//找到pos前一个结点SListNode* prev *plist;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}
}【动图展示】 4.12 单链表之在pos位置之后插入x
//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}注意链接顺序不要和头插犯同样的错误 【动图展示】
4.13 单链表之删除pos位置之后的结点
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos-next);//之后的结点不能为NULL//记录pos后一个结点SListNode* del pos-next;//链接pos-next del-next;//删除释放free(del);
}【动图展示】 4.14 单链表之结点释放
//结点释放
void SListDestroy(SListNode** plist)
{SListNode* cur *plist;while (cur){//在释放前记录下一个结点SListNode* next cur-next;free(cur);cur next;}*plist NULL;
}【动图展示】 五、总结
不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插入动态顺序表空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低
