C/C++数据结构之双向链表详细写法以及使用场合（对比单链表）

2021-10-27 19:44:00

文章目录

前言

双向链表，顾名思义，即对比于单链表的只能向后一个方向延伸，双向链表可以向前和向后两个方向延伸，提高了访问元素的灵活性。

一、双向链表基础框架

既然要做到双向，那么我们只需要在单链表的基础上再加上一个指向上一个元素的指针即可，那么依照构建单链表的方法我们可以得到双链表所需要的结构体设计为：

#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）
C/C++数据结构之双向链表详细写法以及使用场合（对比单链表）
C/C++数据结构之双向链表详细写法以及使用场合（对比单链表）

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;
}

三：双向链表的元素插入

C/C++数据结构之双向链表详细写法以及使用场合（对比单链表）
C/C++数据结构之双向链表详细写法以及使用场合（对比单链表）
C/C++数据结构之双向链表详细写法以及使用场合（对比单链表）

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;
}

四：双向链表的元素删除

C/C++数据结构之双向链表详细写法以及使用场合（对比单链表）

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;
}
上一篇：ORACLE 父子关系查询


下一篇：双链表