首页 / 算法 / 20201016数据结构和算法之 双向链表

20201016数据结构和算法之 双向链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了20201016数据结构和算法之 双向链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6406字，纯文字阅读大概需要10分钟。

内容图文

** 双向链表的结构如下:**

typedef struct _dbLinkList{
 type data;
 _dbLinkList* pre;
 _dbLinkList* next; 
}dbLinkList,dbLinkNode;

**双向链表的特性：**由结构可以看出，双向链表继承了单向链表的特性同时，其构成相对于单向链表，多了一个指向前一个元素的pre指针,具有了逆向追溯性。
**函数调用接口：**其结构函数初始化、尾部插入、查询元素、增加元素、销毁链表同单向链表，
但是前插法、删除元素接口函数有些不一样。
具体的详见接口函数代码注释。

bool dbLinkListInsertFront(dbLinkList*& link, dbLinkList* &node) {
	if (!link || !node) return false;
	if (!link->next) {//链表为空的情况
		node->next = NULL;
		node->pre = link;
		link->next = node;
	}
	else {//第二个结点靠头结点来外推，所以必须得先将第二个结点关联的指针赋值，才不会改变原有的值
		node->next = link->next;//将新结点指向第二个结点
		link->next->pre = node;	//先将第二个结点指向新结点	  
	    
		link->next = node;//将首结点指向新结点 
		node->pre = link;	//将新结点指向首结点				
	}
	return true;
}

以上是前插法的调用函数区分为空链表插入和非空链表插入，同时在非空链表插入时，连接前后指针的顺序非常重要，必须将外推的结点先赋值。
以下是删除元素函数，和前插法函数有些类似，分为删除的结点是尾结点和非尾结点两种情况。

bool dbLinkListDeleteEle(dbLinkList* &link, int i) {
	if (!link) return false;
	dbLinkList* p = link;
	int pos = 0;
	while (p && pos < i) {
		p = p->next;
		pos++;
	}
	if (!p || pos > i) return false;
	if (!p->next) {//删除的是尾结点
		p->pre->next = NULL;
	}
	else {//删除的是非尾结点
		p->next->pre = p->pre;
		p->pre->next = p->next;
	}
	
	delete p;
	return true;
}

其他通用的函数和调试代码如下（含前面的接口程序，亲测可用）

#include<Windows.h>
#include<iostream>
using namespace std;

typedef struct _dbLinkList {
	int data;
	_dbLinkList* pre;
	_dbLinkList* next;
}dbLinkListNode,dbLinkList;
//函数实现
bool initdbLinkList(dbLinkList* &link);//双向链表初始化
bool dbLinkListInsertFront(dbLinkList*& link, dbLinkList* &node);//链表前插法
bool dbLinkListPrint(dbLinkList*& link);//打印链表
bool dbLinkListInsertBack(dbLinkList* &link,dbLinkList* &node);//链表尾插法
bool dbLinkListInsert(dbLinkList* &link,int i,dbLinkList* &node);//任意位置插入
bool dbLinkListGetEle(dbLinkList*& link, int i, dbLinkList*& node);//获取第i个位置的元素
//根据需要更改要查询的数据类型
bool dbLinkListFindEle(dbLinkList*& link, int e);//查询是否有元素e
bool dbLinkListDeleteEle(dbLinkList*& link, int i);//删除第i个位置的数据
void dbLinkListDestroy(dbLinkList*& link);//销毁链表
int main() {
	dbLinkList* link;
	dbLinkListNode* node;
	initdbLinkList(link);
	int cout;
	std::cout << "采用前插法插入数据，请输入要插入的个数：" << std::endl;
	cin >> cout;
	for (int i = 0; i < cout; i++) {
		node = new dbLinkListNode;
		cin >> node->data;
		dbLinkListInsertFront(link, node);
	}
	dbLinkListPrint(link);

	std::cout << "**************采用尾插法插入数据，请输入要插入的个数：***********" << std::endl;
	cin >> cout;
	for (int i = 0; i < cout; i++) {
		node = new dbLinkListNode;
		cin >> node->data;
		dbLinkListInsertBack(link, node);
	}
	dbLinkListPrint(link);

	std::cout << "**************任意位置插入数据，请输入要插入的位置和数据：***********" << std::endl;
	cin >> cout;	
	node = new dbLinkListNode;
	cin >> node->data;
	if (dbLinkListInsert(link, cout, node)) {
		std::cout << "插入成功！" << std::endl;
		dbLinkListPrint(link);
	}
	else {
		std::cout << "插入失败！" << std::endl;
	}

	std::cout <<endl<< "**************获取指定位置的数据，请输入要获取的位置：***********" << std::endl;
	cin >> cout;
	node = new dbLinkListNode;
	if (dbLinkListGetEle(link, cout, node)) {
		std::cout << "获取成功！第"<<cout<<"位的数据是:"<<node->data << std::endl;	
	}
	else {
		std::cout << "获取失败！" << std::endl;
	}
	std::cout << endl << "**************查询是否有指定的数据***********" << std::endl;
	cout = 4;
	if (dbLinkListFindEle(link,cout)) {
		std::cout << "查询成功！" << std::endl;
	}
	else {
		std::cout << "查询失败！" << std::endl;
	}

	std::cout << endl << "**************删除指定位置的数据,请输入位置***********" << std::endl;
	cin>>cout;
	if (dbLinkListDeleteEle(link, cout)) {
		std::cout << "删除成功！" << std::endl;
		dbLinkListPrint(link);
	}
	else {
		std::cout << "删除失败！" << std::endl;
	}

	
	dbLinkListDestroy(link);
	system("pause");
	return 0;
}
bool initdbLinkList(dbLinkList* &link) {
	link = new dbLinkList;
	if (!link) return false;
	link->pre = NULL;
	link->next = NULL;
	link->data = -1;
	return true;
}
bool dbLinkListInsertFront(dbLinkList*& link, dbLinkList* &node) {
	if (!link || !node) return false;
	if (!link->next) {//链表为空的情况
		node->next = NULL;
		node->pre = link;
		link->next = node;
	}
	else {//第二个结点靠头结点来外推，所以必须得先将第二个结点关联的指针赋值，才不会改变原有的值
		node->next = link->next;//将新结点指向第二个结点
		link->next->pre = node;	//先将第二个结点指向新结点	  
	    
		link->next = node;//将首结点指向新结点 
		node->pre = link;	//将新结点指向首结点				
	}
	return true;
}
bool dbLinkListPrint(dbLinkList*& link) {
	if (!link) return false;
	dbLinkList* p = link;
	while (p->next) {
		p = p->next;
		cout << p->data << " ";
	}
	cout << endl;
	cout << "逆向打印双向链表！" << endl;
	while (p!=link) {
		cout << p->data << " ";
		p = p->pre;
	}
	return true;
}
bool dbLinkListInsertBack(dbLinkList*& link, dbLinkList*& node) {
	if (!link || !node) return false;
	dbLinkList* p = link;
	while (p->next != NULL) {
		p = p->next;
	}
	p->next = node;
	node->pre = p;
	node->next = NULL;
	return true;
}
bool dbLinkListInsert(dbLinkList*& link, int i, dbLinkList*& node) {
	if (!link || !node) return false;
	dbLinkList* p = link;
	int pos = 0;
	while (p && pos < i - 1) {//找到第i-1个结点
		p = p->next;
		pos++;
	}
	if (pos > i - 1 || !p) return false;
	
	p->next->pre = node;
	node->next = p->next;
	p->next = node;
	node->pre = p;
	
	return true;	
}
bool dbLinkListGetEle(dbLinkList*& link, int i, dbLinkList*& node) {
	if (!link || !node) return false;
	dbLinkList* p = link;
	int pos = 0;
	while (p && pos < i) {
		p = p->next;
		pos++;
	}
	if (!p || pos > i) return false;
	node = p;
	node->next = p->next;
	node->pre = p->pre;
	return true;
}
bool dbLinkListFindEle(dbLinkList*& link, int e) {
	if (!link) return false;
	dbLinkList* p = link;
	while (p && p->data != e) {
		p = p->next;
	}
	if (!p || p==link)  return false;
	else  return true;
}
bool dbLinkListDeleteEle(dbLinkList* &link, int i) {
	if (!link) return false;
	dbLinkList* p = link;
	int pos = 0;
	while (p && pos < i) {
		p = p->next;
		pos++;
	}
	if (!p || pos > i) return false;
	if (!p->next) {//删除的是尾结点
		p->pre->next = NULL;
	}
	else {//删除的是非尾结点
		p->next->pre = p->pre;
		p->pre->next = p->next;
	}
	
	delete p;
	return true;
}
void dbLinkListDestroy(dbLinkList*& link) {
	if (!link) return;
	dbLinkList* p = link;
	while (p->next) {
		link = p->next;
		delete p;
		p = link;
	}
	delete p;
}
lee李家军 发布了48 篇原创文章 · 获赞 0 · 访问量 365 私信 关注

内容总结

以上是互联网集市为您收集整理的20201016数据结构和算法之 双向链表全部内容，希望文章能够帮你解决20201016数据结构和算法之 双向链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/645798.html

来源：【匿名】