IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构-双向链表(c++)超全超详细 -> 正文阅读

[数据结构与算法]数据结构-双向链表(c++)超全超详细

文章目录

前言

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点（插入，删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。

提示：以下是本篇文章正文内容，下面案例可供参考

一、双向链表是什么？

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prev和next，分别指向其前驱结点和后继结点。
在这里插入图片描述

二、双向链表上的基本操作

1.定义双向链表

代码如下（示例）：

typedef struct DoubleLinkList {

	int data;		//结点的数据域

	DoubleLinkList* next;	//下一个结点的指针域

	DoubleLinkList* prev;	//上一个结点的指针域

}DoubleLinkList,DoubleLinkNode;

2.初始化双链表

代码如下（示例）：

bool DoubleLinkListInit(DoubleLinkList* &L) {	//构造一个空的双向链表

	L = new DoubleLinkNode;	//生成新结点作为头结点，用头指针L指向新结点
	if (!L)return true;		//生成结点失败

	L->next = NULL;		//头结点的next指针域指空
	L->prev = NULL;		//头结点的prev指针域指空
	L->data = -1;

	return true;
}

3.前插法创建双链表

代码如下（示例）：

bool DoubleLinkListInsertFront(DoubleLinkList*& L, DoubleLinkNode* node) {

	if (!L || !node) return false;

	
	if (L->next == NULL) {//只有头结点
		node->next = NULL;
		node->prev = L;		//新结点的prev指针指向头结点
		L->next = node;		//头结点的next指针指向新结点
	}
	else {
		L->next->prev = node;	//第二个结点的prev指向新结点
		node->next = L->next;	//新结点的next指向第二个结点
		node->prev = L;			//新结点的prev指向第一个结点
		L->next = node;			//第一个结点的next指向新结点
	}
	return true;
}

4.尾插法创建双链表

代码如下（示例）：

bool DoubleLinkListInsertBack(DoubleLinkList*& L, DoubleLinkNode* node) {

	DoubleLinkNode* last = NULL;

	if (!L || !node) return false;

	last = L;

	while (last->next) last = last->next;

	node->next = NULL;
	node->prev = last;
	last->next = node;

	return true;
}

5.双向链表的遍历输出

代码如下（示例）：

void DoubleLinkListPrint(DoubleLinkList* &L) {

	DoubleLinkNode* p=L;

	if (!L) {
		cout << "链表为空" << endl;
		return;
	}

	while (p->next) {
		cout << p->next->data << "  ";
		p = p->next;
	}

	//逆向打印
	cout << endl << "逆向打印" << endl;
	while (p) {
		cout << p->data << " ";
		p = p->prev;
	}
	cout << endl;

	return;
}

6.双链表的指定位置插入

代码如下（示例）：

bool DoubleLinkListInsert(DoubleLinkList* L,int i,int e) {

	if (!L || !L->next) return false;
	if (i < 1)return false;

	int j = 0;
	DoubleLinkList* p, * s;
	p = L;

	while (p && j < i) {//查找位置为i的结点，p指向该结点
		p = p->next;
		j++;
	}

	if (!p || j != i) {
		cout << "结点不存在" << i << endl;
		return false;
	}

	s = new DoubleLinkNode;
	s->data = e;

	s->next = p;
	s->prev = p->prev;

	p->prev->next = s;
	p->prev = s;

	return true;
}

7.双链表的按位取值

代码如下（示例）：

bool DoubleLinkListGetElem(DoubleLinkList* &L,int i,int& e) {

	int index;
	DoubleLinkList* p;

	if (!L || !L->next) return false;

	p = L->next;
	index = 1;

	while (p || index < i) { //链表向后扫描，直到p指向第i个元素或者p为空
		p = p->next;		//p指向下一个结点
		index++;				//计数器index加1
	}

	if (!p || index > i) {
		return false;   //i值不合法，i>n或i<=0
	}

	e = p->data;

	return true;
}

8.双链表的任意位置删除

代码如下（示例）：

bool DoubleLinkListDelete(DoubleLinkList*& L, int i) {

	DoubleLinkList* p;
	int index = 0;

	if (!L || !L->next) {
		cout << "双向链表为空！" << endl;
		return false;
	}
	if (i < 1) {
		cout << "不能删除头结点!" << endl;
		return false;
	}
	p = L;

	while (p && index < i) {
		p = p->next;
		index++;
	}
	if (!p)return false; //当结点不存在时，返回失败

	p->prev->next = p->next;
	p->next->prev = p->prev;

	delete p;

	return true;
}

9.双链表的销毁

代码如下（示例）：

void DoubleLinklistDestroy(DoubleLinkList*  &L) {

	DoubleLinkList* p = L;
	cout << "销毁链表" << endl;

	while (p) {
		L = L->next; //L指向下一个结点
		delete p;   //删除当前结点
		p = L;     //p移向下一个结点
	}

}

三、全部代码(主函数部分比较凌乱）

#include<iostream>
using namespace std;

typedef struct DoubleLinkList {

	int data;		//结点的数据域

	DoubleLinkList* next;	//下一个结点的指针域

	DoubleLinkList* prev;	//上一个结点的指针域

}DoubleLinkList,DoubleLinkNode;


bool DoubleLinkListInit(DoubleLinkList* &L) {	//构造一个空的双向链表

	L = new DoubleLinkNode;	//生成新结点作为头结点，用头指针L指向新结点
	if (!L)return true;		//生成结点失败

	L->next = NULL;		//头结点的next指针域指空
	L->prev = NULL;		//头结点的prev指针域指空
	L->data = -1;

	return true;
}


//前插法
bool DoubleLinkListInsertFront(DoubleLinkList*& L, DoubleLinkNode* node) {

	if (!L || !node) return false;

	
	if (L->next == NULL) {//只有头结点
		node->next = NULL;
		node->prev = L;		//新结点的prev指针指向头结点
		L->next = node;		//头结点的next指针指向新结点
	}
	else {
		L->next->prev = node;	//第二个结点的prev指向新结点
		node->next = L->next;	//新结点的next指向第二个结点
		node->prev = L;			//新结点的prev指向第一个结点
		L->next = node;			//第一个结点的next指向新结点
	}
	return true;
}


//尾插法
bool DoubleLinkListInsertBack(DoubleLinkList*& L, DoubleLinkNode* node) {

	DoubleLinkNode* last = NULL;

	if (!L || !node) return false;

	last = L;

	while (last->next) last = last->next;

	node->next = NULL;
	node->prev = last;
	last->next = node;

	return true;
}


//双向链表的遍历输出
void DoubleLinkListPrint(DoubleLinkList* &L) {

	DoubleLinkNode* p=L;

	if (!L) {
		cout << "链表为空" << endl;
		return;
	}

	while (p->next) {
		cout << p->next->data << "  ";
		p = p->next;
	}

	//逆向打印
	cout << endl << "逆向打印" << endl;
	while (p) {
		cout << p->data << " ";
		p = p->prev;
	}
	cout << endl;

	return;
}


//指定位置插入
bool DoubleLinkListInsert(DoubleLinkList* L,int i,int e) {

	if (!L || !L->next) return false;
	if (i < 1)return false;

	int j = 0;
	DoubleLinkList* p, * s;
	p = L;

	while (p && j < i) {//查找位置为i的结点，p指向该结点
		p = p->next;
		j++;
	}

	if (!p || j != i) {
		cout << "结点不存在" << i << endl;
		return false;
	}

	s = new DoubleLinkNode;
	s->data = e;

	s->next = p;
	s->prev = p->prev;

	p->prev->next = s;
	p->prev = s;

	return true;
}


//双向链表按位取值
bool DoubleLinkListGetElem(DoubleLinkList* &L,int i,int& e) {

	int index;
	DoubleLinkList* p;

	if (!L || !L->next) return false;

	p = L->next;
	index = 1;

	while (p || index < i) { //链表向后扫描，直到p指向第i个元素或者p为空
		p = p->next;		//p指向下一个结点
		index++;				//计数器index加1
	}

	if (!p || index > i) {
		return false;   //i值不合法，i>n或i<=0
	}

	e = p->data;

	return true;
}


//任意位置删除
bool DoubleLinkListDelete(DoubleLinkList*& L, int i) {

	DoubleLinkList* p;
	int index = 0;

	if (!L || !L->next) {
		cout << "双向链表为空！" << endl;
		return false;
	}
	if (i < 1) {
		cout << "不能删除头结点!" << endl;
		return false;
	}
	p = L;

	while (p && index < i) {
		p = p->next;
		index++;
	}
	if (!p)return false; //当结点不存在时，返回失败

	p->prev->next = p->next;
	p->next->prev = p->prev;

	delete p;

	return true;
}


//销毁双向链表
void DoubleLinklistDestroy(DoubleLinkList*  &L) {

	DoubleLinkList* p = L;
	cout << "销毁链表" << endl;

	while (p) {
		L = L->next; //L指向下一个结点
		delete p;   //删除当前结点
		p = L;     //p移向下一个结点
	}

}








int main() {
	
	DoubleLinkList* L;
	DoubleLinkList* s;

	//1.初始化一个空的双向链表
	if (DoubleLinkListInit(L)) {
		cout << "初始化链表成功!" << endl;
	}
	else {
		cout << "初始化链表失败！" << endl;
	}

	//2.使用前插法插入数据
	int n;

	cout << "使用前插法创建双向链表" << endl;
	cout << "请输入元素个数：";
	cin >> n;
	cout << endl << "依次输入" << n << "个元素: ";

	while (n > 0) {
		s = new DoubleLinkNode;
		cin >> s->data;
		DoubleLinkListInsertFront(L, s);
		n--;
	}

	DoubleLinkListPrint(L);

	//3.使用尾插法插入数据
	
	cout << "使用尾插法创建双向链表" << endl;
	cout << "请输入元素个数：";
	cin >> n;
	cout << endl << "依次输入" << n << "个元素: ";

	while (n > 0) {
		s = new DoubleLinkNode;
		cin >> s->data;
		DoubleLinkListInsertBack(L, s);
		n--;
	}


	DoubleLinkListPrint(L);

	//4.任意位置插入元素
	for (int j = 0; j < 3; j++) {
		int i, x;
		cout << "请输入要插入的位置和元素(用空格隔开):";
		cin >> i >> x;

		if (DoubleLinkListInsert(L, i, x)) {
			cout << "插入成功！" << endl;
		}
		else {
			cout << "插入失败！" << endl;
		}
		DoubleLinkListPrint(L);
	}

	//5.双向链表删除元素
	if (DoubleLinkListDelete(L, 2)) {
		cout << "删除链表第2个元素成功" << endl;
	}
	else
		cout << "删除链表第2个元素失败！" << endl;


	DoubleLinkListPrint(L);

	//6.销毁链表
	DoubleLinklistDestroy(L);


	return 0;
}

总结

以上就是今天要讲的内容，本文仅仅简单介绍了双向链表的基本操作，如有错误，欢迎大家指针，看完记得点个赞。
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-12-02 17:01:12  更:2021-12-02 17:03:07 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 14:28:59-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码