投稿
  1. 首页
  2. 随笔

数据结构-双向链表(c++)超全超详细

太原理工大学怎么样 • 2022-12-16 • 随笔 • 阅读 818

数据结构-双向链表(c++)超全超详细,第1张

数据结构-双向链表(c++)超全超详细

文章目录
  • 前言
  • 一、双向链表是什么？
  • 二、双向链表上的基本 *** 作
    • 1.定义双向链表
    • 2.初始化双链表
    • 3.前插法创建双链表
    • 4.尾插法创建双链表
    • 5.双向链表的遍历输出
    • 6.双链表的指定位置插入
    • 7.双链表的按位取值
    • 8.双链表的任意位置删除
    • 9.双链表的销毁
  • 三、全部代码(主函数部分比较凌乱）
  • 总结

前言

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点（插入，删除 *** 作时），只能从头开始遍历，访问后继结点的时间复杂度为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
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;
}
总结 以上就是今天要讲的内容，本文仅仅简单介绍了双向链表的基本 *** 作，如有错误，欢迎大家指针，看完记得点个赞。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5635953.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
太原理工大学怎么样 太原理工大学怎么样 一级用户组
0 0
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表（0条）

保存