C/C++教程
C/C++数据结构之双向链表详细写法以及使用场合（对比单链表）
本文主要是介绍C/C++数据结构之双向链表详细写法以及使用场合（对比单链表），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
文章目录
- 前言
- 一、双向链表基础框架
- 二、创建双向链表
- 三：双向链表的元素插入
- 四：双向链表的元素删除
- 五：双向链表的元素查找
- 六：双向链表的元素替换
- 七：双向链表的元素显示
- 八：与单链表的优劣对比
- 九：完整代码
前言
双向链表，顾名思义，即对比于单链表的只能向后一个方向延伸，双向链表可以向前和向后两个方向延伸，提高了访问元素的灵活性。
一、双向链表基础框架
既然要做到双向，那么我们只需要在单链表的基础上再加上一个指向上一个元素的指针即可，那么依照构建单链表的方法我们可以得到双链表所需要的结构体设计为：
#pragma once
#include<iostream>
#include <cstdio>
#include<cstdlib>
typedef int Status;
typedef int ElemType;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
using namespace std;
typedef struct DouList
{
struct DouList* prior;
struct DouList* next;
ElemType data;
}DouList;
可以发现再结构体里出现了两个DouList类型的结构体指针，*prior指向上一个节点，*next指向下一个节点。
二、创建双向链表
要创建双向链表，我们就得先知道双向链表的大致结构，有如下结构：
1：头指针的prior指向NULL，尾指针的next指向NULL
2：节点的prior指向上一个节点（如temp1->prior=temp0)
3：节点的next指向下一个节点（如temp1->next=temp2）
DouList* InitList(DouList* head)
{
DouList* body; //创建局部变量
head = (DouList*)malloc(sizeof(DouList)); //创建头指针
head->prior = NULL; //由上图可知先将头指针指向NULL
head->next = NULL;
head->data = 1; //随便赋一个值
DouList* list = head; //保留最初头指针
//for (int i = 2; i <= 5; i++) //可以用for也可以用do while
do
{
//创建并初始化一个新结点
body = (DouList*)malloc(sizeof(DouList));
body->prior = NULL;
body->next = NULL;
cout << "输入data" << endl;//数据输入
cin >> body->data;
//body->data = i;
list->next = body;//直接前趋结点的next指针指向新结点
body->prior = list;//新结点指向直接前趋结点
list = list->next; //指针移到下一位
} while (body->data != 0);
return head;
}
三：双向链表的元素插入
DouList* Insert_DouList(DouList* head,ElemType e,int i)//在第i个处插入e
{
DouList *p, *temp; //初始化指针
//if (i < 1)
//{
// cout << "输入的位置不对！！" << endl;
// return ERROR;
//} //检测要在主函数进行，不然返回值调不了
p = head; //保留原有头指针
temp = (DouList*)malloc(sizeof(DouList)); //开辟临时空间
temp->next = NULL; temp->prior = NULL; temp->data = e;//初始化
if (i == 1) //插入开头
{
p->prior = temp; //这些步骤建议在纸张上演算一下
temp->next = p;
head = temp;
}
else //插在表尾或表中
{
for (int j = 1; j < i-1; j++) //找到数据对应位置p
{
p = p->next;
}
if(p->next==NULL)//插在链尾
{
temp->prior = p;
p->next = temp;
}
else//插在链中
{
p->next->prior = temp;
temp->next = p->next;
p->next = temp;
temp->prior = p;
}
}
return head;
}
四：双向链表的元素删除
DouList* Delete_DouList(DouList* head, ElemType e)//删除数据为e的遇到的第一个
{
DouList* p = head; //保留原有头指针防止头指针丢失
if (p->data == e) //找到数据且数据为头指针位置
{
p->next->prior = NULL; //原有头指针的下一个数据变为头指针，其prior初始化为NULL
head->next = head; //使下一个数据变为头指针位置
return head; //返回头指针
}
while (p->next!=NULL) //p非空
{
if (p->data == e) //判断是否找到
{
p->next->prior = p->prior; //找到后改变原有的链接路径
p->prior->next = p->next;
free(p); //释放要删除的位置，这就是为什么不能直接用头指针去遍历链表
return head; //返回原有头指针
}
p = p->next; //没找到那么继续遍历
}
cout << "没有找到！！" << endl;
return head;
}
五：双向链表的元素查找
Status GetLocation(DouList* head, ElemType e)
{
int j = 1; //初始化位置为1
DouList* p, * temp; //局部指针
p = head; //保留原有头指针，要是直接用头指针去遍历那么最后会丢失原有头指针位置
while (p)
{
if (p->data == e) //找到了数据
return j;
else //没有找到，位置加1
{
++j;
p = p->next;
}
}
cout << "元素" << e << "不存在于链表中" << endl;
return FALSE;
}
六：双向链表的元素替换
DouList* ChangeDouList(DouList* head, ElemType e, int i)//第i个位置数据改为e
{
DouList* p;
p = head;
if (i < 1)
cout << "位置不对！！" << endl;
for (int j = 1; j < i; j++)
{
p = p->next; //先遍历来找到对应位置数据
}
p->data = e;
return head;
}
七：双向链表的元素显示
void display(DouList* head)
{
DouList* temp = head;
while (temp) {
//如果该节点无后继节点，说明此节点是链表的最后一个节点
if (temp->next == NULL) {
printf("%d\n", temp->data); //下一个元素为空
}
else {
printf("%d <-> ", temp->data);
}
temp = temp->next;
}
}
八：与单链表的优劣对比
可以发现，由于双向链表能够前后遍历，那么由于这一特性，我们得多写出一个指针，因此在数据插入和删除时造成了一些麻烦，而单链表由于只有一个指针因此只需要一直指向下一节点即可，减少了一些麻烦。但是正是由于双向链表可以前后遍历，因此在需要反复“横跳“的时候双向链表的效率远高于单链表，而在不需要反复”横跳“的情况下单链表更省时间也更容易写出。
九：完整代码
#pragma once
#include<iostream>
#include <cstdio>
#include<cstdlib>
typedef int Status;
typedef int ElemType;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 30
#define make (struct student*)malloc(sizeof(struct student));
using namespace std;
int n = 0;
typedef struct DouList
{
struct DouList* prior;
struct DouList* next;
ElemType data;
}DouList;
DouList* InitList(DouList* head)
{
DouList* body; //创建局部变量
head = (DouList*)malloc(sizeof(DouList)); //创建头指针
head->prior = NULL; //由上图可知先将头指针指向NULL
head->next = NULL;
head->data = 1; //随便赋一个值
DouList* list = head; //保留最初头指针
//for (int i = 2; i <= 5; i++) //可以用for也可以用do while
do
{
//创建并初始化一个新结点
body = (DouList*)malloc(sizeof(DouList));
body->prior = NULL;
body->next = NULL;
cout << "输入data" << endl;//数据输入
cin >> body->data;
//body->data = i;
list->next = body;//直接前趋结点的next指针指向新结点
body->prior = list;//新结点指向直接前趋结点
list = list->next; //指针移到下一位
} while (body->data != 0);
return head;
}
DouList* Insert_DouList(DouList* head,ElemType e,int i)//在第i个处插入e
{
DouList *p, *temp; //初始化指针
//if (i < 1)
//{
// cout << "输入的位置不对！！" << endl;
// return ERROR;
//} //检测要在主函数进行，不然返回值调不了
p = head; //保留原有头指针
temp = (DouList*)malloc(sizeof(DouList)); //开辟临时空间
temp->next = NULL; temp->prior = NULL; temp->data = e;//初始化
if (i == 1) //插入开头
{
p->prior = temp; //这些步骤建议在纸张上演算一下
temp->next = p;
head = temp;
}
else //插在表尾或表中
{
for (int j = 1; j < i-1; j++) //找到数据对应位置p
{
p = p->next;
}
if(p->next==NULL)//插在链尾
{
temp->prior = p;
p->next = temp;
}
else//插在链中
{
p->next->prior = temp;
temp->next = p->next;
p->next = temp;
temp->prior = p;
}
}
return head;
}
DouList* Delete_DouList(DouList* head, ElemType e)//删除数据为e的遇到的第一个
{
DouList* p = head; //保留原有头指针防止头指针丢失
if (p->data == e) //找到数据且数据为头指针位置
{
p->next->prior = NULL; //原有头指针的下一个数据变为头指针，其prior初始化为NULL
head->next = head; //使下一个数据变为头指针位置
return head; //返回头指针
}
while (p->next!=NULL) //p非空
{
if (p->data == e) //判断是否找到
{
p->next->prior = p->prior; //找到后改变原有的链接路径
p->prior->next = p->next;
free(p); //释放要删除的位置，这就是为什么不能直接用头指针去遍历链表
return head; //返回原有头指针
}
p = p->next; //没找到那么继续遍历
}
cout << "没有找到！！" << endl;
return head;
}
Status GetLocation(DouList* head, ElemType e)
{
int j = 1; //初始化位置为1
DouList* p, * temp; //局部指针
p = head; //保留原有头指针，要是直接用头指针去遍历那么最后会丢失原有头指针位置
while (p)
{
if (p->data == e) //找到了数据
return j;
else //没有找到，位置加1
{
++j;
p = p->next;
}
}
cout << "元素" << e << "不存在于链表中" << endl;
return FALSE;
}
DouList* ChangeDouList(DouList* head, ElemType e, int i)//第i个位置数据改为e
{
DouList* p;
p = head;
if (i < 1)
cout << "位置不对！！" << endl;
for (int j = 1; j < i; j++)
{
p = p->next; //先遍历来找到对应位置数据
}
p->data = e;
return head;
}
void display(DouList* head)
{
DouList* temp = head;
while (temp) {
//如果该节点无后继节点，说明此节点是链表的最后一个节点
if (temp->next == NULL) {
printf("%d\n", temp->data); //下一个元素为空
}
else {
printf("%d <-> ", temp->data);
}
temp = temp->next;
}
}
int main() {
DouList* head = NULL;
//创建双链表
head = InitList(head);
display(head);
//在表中第 3 的位置插入元素 7
head = Insert_DouList(head, 7, 1);
display(head);
//表中删除元素 2
head = Delete_DouList(head, 1);
display(head);
printf("元素 3 的位置是：%d\n", GetLocation(head, 3));
//表中第 3 个节点中的数据改为存储 6
head = ChangeDouList(head, 6, 3);
display(head);
return 0;
}
这篇关于C/C++数据结构之双向链表详细写法以及使用场合（对比单链表）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
栏目导航
