网页设计与网站制作,网站宣传费用,搭建什么网站好,网站备案 上一级服务商名称上一章中#xff0c;我们学习了链表中的单链表#xff0c;那今天我们来学习另一种比较常见的链表--双向链表#xff01;#xff01; 目录
一、双向链表的结构
二、 双向链表的实现
1. 双向链表的初始化和销毁
2. 双向链表的打印
3. 双向链表的头插/尾插
4. 双向链表的… 上一章中我们学习了链表中的单链表那今天我们来学习另一种比较常见的链表--双向链表 目录
一、双向链表的结构
二、 双向链表的实现
1. 双向链表的初始化和销毁
2. 双向链表的打印
3. 双向链表的头插/尾插
4. 双向链表的头删/尾删
5. 查找数据是否存在
6. 在指定位置之后插入数据
7. 删除指定位置的数据
8. 判断双向链表是否为空
三、顺序表和双向链表的优缺点分析 一、双向链表的结构 “哨兵位”存在的意义遍历循环链表避免死循环。 注意带头链表里的头节点实际为“哨兵位”不存储任何有效数据。
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;//存储的数据struct ListNode* prev; //指针保存前一个节点的地址struct ListNode* next; //指针保存下一个节点的地址
}LTNode;
二、 双向链表的实现 我们先在头文件中定义需要实现的相关接口。
//List.h
#includestdio.h
#include stdbool.h//引用bool类型
#includestdlib.h
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;//存储的数据struct ListNode* prev; //指针保存前一个节点的地址struct ListNode* next; //指针保存下一个节点的地址
}LTNode;
//创建节点
LTNode* LTBuyNode(LTDataType x);
//双向链表有哨兵位插入数据之前链表中必须初始化一个哨兵位
//需要修改哨兵位就要传二级指针
//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
//头插/尾插
//不需要修改哨兵位就不需要传二级指针
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
//头删/尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
//查找数据是否存在
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的数据
void LTErase(LTNode* pos);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
1. 双向链表的初始化和销毁
//双向链表初始化
void LTInit(LTNode** pphead)
{*pphead (LTNode*)malloc(sizeof(LTNode));if (*pphead NULL){perror(malloc fail);exit(1);}(*pphead)-data -1;//给哨兵位一个无效的数据是多少都可以//带头双向循环链表在刚初始化一个哨兵位时next和prev都指向自己(*pphead)-next (*pphead)-prev *pphead;return phead;
} 这种写法要涉及到二级指针非常麻烦那我们尝试简化一下代码。
LTNode* LTInit()
{LTNode*phead (LTNode*)malloc(sizeof(LTNode));if (phead NULL){perror(malloc fail);exit(1);}phead-data -1;phead-next phead-prev phead;return phead;
} 实际上这段代码还可以进行简化。因为双向链表为空时仍然有一个哨兵位那我们在初始化时就可以直接申请一个哨兵位。
//将申请节点的功能进行封装
LTNode* LTBuyNode(LTDataType x) {LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL) {perror(malloc);exit(1);}newnode-data x;newnode-next newnode-prev newnode;return newnode;
}
//双向链表初始化
LTNode* LTInit()
{LTNode* phead LTBuyNode(-1);//申请哨兵位return phead;
}
//双向链表销毁
void LTDestroy(LTNode* phead)
{assert(phead);//遍历链表把每一个节点都释放LTNode* pcur phead-next;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}//链表中哨兵位也要释放free(phead);phead NULL;
}
2. 双向链表的打印
//双向链表打印
void LTPrint(LTNode* phead)
{assert(phead);//phead不能为空LTNode* pcur phead-next;while (pcur ! phead){//从第一个节点开始走走到哨兵位结束printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}
3. 双向链表的头插/尾插
void LTPushBack(LTNode* phead, LTDataType x)
{LTNode* newnode LTBuyNode(x);//ptail-nextphead;//尾节点的next指向哨兵位//phead-prevptail//哨兵位的prev指向尾节点//新尾节点的next要指向哨兵位newnode-next phead;//新尾节点的prev要指向原来的尾节点newnode-prev phead-prev;//原来尾节点的next指向新的尾节点phead-prev-next newnode;//哨兵位的prev连接新的尾节点phead-prev newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//新的头节点的next指向原来的头节点newnode-next phead-next;//新的头节点的prev指向哨兵位newnode-prev phead;//原来头节点的prev指向新的头节点phead-next-prev newnode;//哨兵位的next指向新的头节点phead-next newnode;
}
4. 双向链表的头删/尾删
void LTPopBack(LTNode* phead)
{assert(phead);//链表不能为空(只有一个哨兵位)assert(phead-next ! phead);LTNode* del phead-prev;LTNode* prev del-prev;//原来尾节点的前一个节点的next指向哨兵位prev-next phead;//哨兵位的prev变成原来尾节点的前一个节点phead-prev prev;//释放原来的尾节点free(del);del NULL;
}
void LTPopFront(LTNode* phead)
{assert(phead);//链表不能为空(只有一个哨兵位)assert(phead-next ! phead);LTNode* del phead-next;LTNode* next del-next;//原来头节点的后一个节点的prev指向哨兵位next-prev phead;//哨兵位的next变成原来头节点的后一个节点phead-next next;//释放原来的尾节点free(del);del NULL;
}
5. 查找数据是否存在
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x) {return pcur;}pcur pcur-next;}return NULL;
}
6. 在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//新节点的next指向pos后面原来的节点newnode-next pos-next;//新节点的prev指向pos节点newnode-prev pos;//pos节点后面原来的节点的prev换成新节点pos-next-prev newnode;//pos节点的next换成新节点pos-next newnode;
}
7. 删除指定位置的数据
void LTErase(LTNode* pos)
{assert(pos);//pos前面节点的next指向pos后面的节点pos-prev-next pos-next;//pos后面节点的prev指向pos前面的节点pos-next-prev pos-prev;free(pos);pos NULL;
}
8. 判断双向链表是否为空
bool LTEmpty(LTNode* phead)
{return phead-next phead;
}
三、顺序表和双向链表的优缺点分析 顺序表 带头双向循环链表 优点 下标随机访问实现二分查找、排序、堆算法等 Cache命中率高存储空间连续 任意位置插入删除数据效率高 按需申请、释放不存在空间浪费 缺点 前面部分的插入删除效率低下 扩容会有效率损失还可能会存在空间浪费 不支持下标随机访问 Cache命中率低存储空间不连续
