广州大石附近做网站的公司哪家好,网站设计模板照片,企业整站推广,百度权重排名高的网站哈喽铁子们#xff0c;这里是博主鳄鱼皮坡。这篇文章将分享交流双向链表的相关知识#xff0c;下面正式开始。
1. 双向链表的结构 注意#xff1a;这里的“带头”跟前面我们说的“头节点”是两个概念#xff0c;实际前面的在单链表阶段称呼不严 谨#xff0c;但是为了老…哈喽铁子们这里是博主鳄鱼皮坡。这篇文章将分享交流双向链表的相关知识下面正式开始。
1. 双向链表的结构 注意这里的“带头”跟前面我们说的“头节点”是两个概念实际前面的在单链表阶段称呼不严 谨但是为了老铁们更好的理解就直接称为单链表的头节点。 带头链表里的头节点实际为“哨兵位”哨兵位节点不存储任何有效元素只是站在这⾥“放哨 的”。而“哨兵位”存在的意义 遍历循环链表避免死循环。 2. 双向链表的实现 以尾插为例
第一步assert(phead); 防止为空。
第二步创建新节点和单链表一样用LTBuyNode()函数即可。
第三步先将新节点指向原链表由双向链表的特性我们就不需要像单链表一样遍历去找。newnode-prev即为上图的d3。 1 newnode-prev phead-prev;先将新节点的头部指向原链表的最后一个节点即d3。 2 newnode-next phead;而后将新节点的尾部指向原链表的哨兵位。
第四步将原链表相应的位置指向新节点 1phead-prev-next newnode;原链表的最后节点尾部指向新节点 2phead-prev newnode;原链表的哨兵位头部指向新节点
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead phead-prev newnodenewnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;
}
只要理清楚双向链表节点的指向关系之后和单链表结构相似。
双链表的代码如下
//List.c
#includeList.hvoid LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(malloc fail!);exit(1);}node-data x;node-next node-prev node;return node;
}
//初始化
//void LTInit(LTNode** pphead)
//{
// //给双向链表创建一个哨兵位
// *pphead LTBuyNode(-1);
//}
LTNode* LTInit()
{LTNode* phead LTBuyNode(-1);return phead;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead phead-prev newnodenewnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead newnode phead-nextnewnode-next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
}//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空只有一个哨兵位assert(phead phead-next ! phead);LTNode* del phead-prev;//phead del-prev deldel-prev-next phead;phead-prev del-prev;//删除del节点free(del);del NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-next;//phead del del-nextphead-next del-next;del-next-prev phead;//删除del节点free(del);del NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}//没有找到return NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//pos newnode pos-nextnewnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}//删除pos节点
void LTErase(LTNode* pos)
{//pos理论上来说不能为phead但是没有参数phead无法增加校验assert(pos);//pos-prev pos pos-nextpos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;
}void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}//此时pcur指向phead而phead还没有被销毁free(phead);phead NULL;
}
//List.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h//定义节点的结构
//数据 指向下一个节点的指针
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);//销毁链表
void SListDesTroy(SLTNode** pphead);3. 顺序表和双向链表的优缺点分析 不同点 顺序表 链表单链表 存储空间上 物理上⼀定连续 逻辑上连续但物理上不⼀定连续 随机访问 ⽀持O(1) 不⽀持O(N) 任意位置插⼊或者删除元素 可能需要搬移元素效率低O(N) 只需修改指针指向 插⼊ 动态顺序表空间不够时需要扩容 没有容量的概念 应⽤场景 元素⾼效存储频繁访问 任意位置插⼊和删除频繁 在接下来我们将会学习利用实现贪吃蛇小游戏等有意思的东西如果本篇有不理解的地方欢迎私信我或在评论区指出期待与你们共同进步。创作不易望各位大佬一键三连
