数据结构初阶--双向循环链表（讲解+类模板实现）

转载作者：我是一只小鸟更新时间：2022-11-26 22:37:48

25

4

带头双向链表的结构

看下面的图，就是我今天要给大家分享有结构——带头双向循环链表。这里的头是不存放任何数据的，就是一个哨兵卫的头结点.

用代码来表示每一个节点就是这样的:

数据域和指针域
两个指针，一个指向前驱结点，一个指向后继结点
给定两个构造函数，有参和无参，分别对结点的指针域和数据域进行初始化

                        
                          template <class DateType>
struct LinkNode
{
      //数据域
      DateType data;
      //两个指针
      LinkNode<DateType>* prev;
      LinkNode<DateType>* next;
      LinkNode(DateType _data, LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :data(_data), prev(_prev), next(_next){}
      LinkNode(LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :prev(_prev), next(_next){}
};

带头双向链表的接口实现

要实现的接口

                        
                          LinkList();//构造函数，初始化头节点
LinkList(const LinkList<DateType>& list2);//拷贝构造，进行两个链表的拷贝
~LinkList();//析构函数，用来清除链表，释放结点空间
int Length();//求双向循环链表的长度
void CreateList(int n);//常见n个结点的双向循环链表
bool GetElem(int pos,DateType& data);//得到pos位置结点的元素值
LinkNode<DateType>* Locate(int i ,int back_pos);//定位元素，当back_pos=0的时候，从头节点向前查询第i个元素，back_pos！=0的时候，从头节点后查询第i个元素
bool Insert(int pos, const DateType& data, int back_pos);//在pos的位置插入元素，当back_pos！=0的时候，在pos位置后插入元素，当back_pos=0的时候，在pos位置前插入元素
void PrintList(int sign);//输出双向循环链表所有结点的元素值，当sign！=0时，正序打印元素值，当sign=0时，逆序打印
bool Delete(int pos, DateType& data,int back_pos);//删除pos位置的结点

双向链表的小框架

                        
                          template<class DateType>
class LinkList
{
public:
private:
	LinkNode<DateType>* head;//头节点
};

初始化双向链表

在初始化双链表的过程中，我们要开好一个头节点，作为哨兵卫的头节点，然后返回这个节点的指针，接口外面只要用一个节点指针接受这个返回值就好了，具体实现如下:

                        
                          //构造函数,初始化一个循环双链表
	LinkList()
	{
		head = new LinkNode<DateType>;
		if (head == NULL)
		{
			cout << "内存分配失败" << endl;
			exit(-1);
		}
		head->data = 0;
		head->next = head;
		head->prev = head;
	}

拷贝构造

在拷贝构造中，要注意一件事情，就是最后一个结点的next需要指向头节点，头节点的prev需要指向最后一个结点，形成双向循环链表。

                        
                          //拷贝构造
	LinkList(const LinkList<DateType>& list2)
	{
		LinkNode<DateType>* p = list2.head->next;
		if (p == NULL)
		{
			cout << "内存分配失败" << endl;
			exit(-1);
		}
		head = new LinkNode<DateType>;
		LinkNode<DateType>* h = head;
		while (p!=list2.head)
		{
			LinkNode<DateType>* t = new LinkNode<DateType>;
			h->next = t;
			t->prev = h;
			t->data = p->data;
			p = p->next;
			h = h->next;
		}
		h->next = this->head;
		this->head->prev = h;
	}

定位结点

因为后面的在指定插入删除元素，需要定位pos位置结点的地址，所以这里旧封装一个函数，直接获取pos位置结点的地址。

                        
                          //定位元素，back_pos=0时从头节点向前查第i个元素，d!=0时，从头节点向后找第i个元素
	LinkNode<DateType>* Locate(int i ,int back_pos)
	{
		if (head->next == head || i == 0) {
			return head;
		}
		int j = 0;
		LinkNode<DateType>* p = head;
		//从头节点往后找第i个元素
		if (back_pos)
		{
			while (p->next != head && j != i)
			{
				p = p->next;
				++j;
			}
			if (p->next == head && j != i)
			{
				return NULL;
			}
			else
			{
				return p;
			}

		}//向前找
		else
		{
			while (p->prev != head && j != i)
			{
				p = p->prev;
				++j;
			}
			if (p->prev == head && j != i)
				return NULL;
			else
				return p;
		}
	}

创建双向链表

                        
                          //创建双循环链表
	void CreateList(int n)
	{
		DateType* nodetemp = new DateType[n];
		for (rsize_t i = 0; i < n; i++)
		{
			cout << "Enter the element:  " << endl;
			cin >> nodetemp[i];
			Insert(i, nodetemp[i], 1);
		}
		delete[] nodetemp;
		
	}

打印双向循环链表

因为是双向循环链表，可以很简单的实现正序打印和逆序打印，所以这里用一个标志sign，来指定正序还是逆序打印链表元素。

                        
                          //输出双循环链表所有结点的元素值,分为正序打印和逆序打印
	void PrintList(int sign)
	{
		//正序打印
		if (sign)
		{
			cout << "head " ;
			LinkNode<DateType>* p = head;
			while (p->next != head)
			{
				p = p->next;
				cout << "-> " << p->data;
			}
			cout << "->over" << endl;
		}//逆序打印
		else
		{
			cout << "head " << endl;
			LinkNode<DateType>* p = head;
			while (p->prev != head)
			{
				p = p->prev;
				cout << "-> " << p->data;
			}
			cout << "->over" << endl;
		}
	}

指定位置插入结点

任意位置插入首先要开辟一个节点，然后就是按照所个位置，改变指针的指向来把这个节点连接上去，看具体代码实现如下:

                        
                          //在pos的位置插入元素
	bool Insert(int pos, const DateType& data, int back_pos)
	{
		LinkNode<DateType>* p = Locate(pos, back_pos);
		if (!p)
			return false;
		LinkNode<DateType>* new_node = new LinkNode<DateType>(data);
		if (NULL == new_node)
		{
			cout << "内存分配失败" << endl;
			exit(-1);
		}
		//p结点后插入
		if (back_pos)
		{
			p->next->prev = new_node;
			new_node->prev = p;
			new_node->next = p->next;
			p->next = new_node;
		}//p结点前插入
		else
		{
			p->prev->next = new_node;
			new_node->next = p;
			new_node->prev = p->prev;
			p->prev = new_node;
		}return true;
	}

指定位置删除结点

删除就要考虑链表是否为空，防止删除头节点。

                        
                          //删除pos位置的结点
	bool Delete(int pos, DateType& data,int back_pos)
	{
		LinkNode<DateType>* p = Locate(pos, back_pos);
		if (!p)
		{
			return false;
		}
		if (p == head )
		{
			cout << "请不要删除头节点" << endl;
			return false;
		}
		data = p->data;
		p->prev->next = p->next;
		p->next->prev = p->prev;
		delete p;
		return true;
	}

获取链表长度

                        
                          int Length()
	{
		LinkNode<DateType>* p = head;
		int i = 0;
		while (p->next != head)
		{
			++i;
			p = p->next;
		}
		return i;

	}

销毁链表

在析构函数中实现链表的销毁。

                        
                          //析构函数
	~LinkList()
	{
		LinkNode<DateType>* p, * q = head->next;
		while (q != head)
		{
			p = q;
			q = q->next;
			delete p;
		}
	}

整体代码以及测试

                        
                          #define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<string>//C++中的字符串
using namespace std; //标准命名空间
/*
双向循环链表
*/
template <class DateType>
struct LinkNode
{
	//数据域
	DateType data;
	//两个指针
	LinkNode<DateType>* prev;
	LinkNode<DateType>* next;
	LinkNode(DateType _data, LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :data(_data), prev(_prev), next(_next)
	{}
	LinkNode(LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :prev(_prev), next(_next)
	{}
};
template<class DateType>
class LinkList
{
public:
	//构造函数,初始化一个循环双链表
	LinkList()
	{
		head = new LinkNode<DateType>;
		if (head == NULL)
		{
			cout << "内存分配失败" << endl;
			exit(-1);
		}
		head->data = 0;
		head->next = head;
		head->prev = head;
	}
	//拷贝构造
	LinkList(const LinkList<DateType>& list2)
	{
		LinkNode<DateType>* p = list2.head->next;
		if (p == NULL)
		{
			cout << "内存分配失败" << endl;
			exit(-1);
		}
		head = new LinkNode<DateType>;
		LinkNode<DateType>* h = head;
		while (p!=list2.head)
		{
			LinkNode<DateType>* t = new LinkNode<DateType>;
			h->next = t;
			t->prev = h;
			t->data = p->data;
			p = p->next;
			h = h->next;
		}
		h->next = this->head;
		this->head->prev = h;
	}
	//析构函数
	~LinkList()
	{
		LinkNode<DateType>* p, * q = head->next;
		while (q != head)
		{
			p = q;
			q = q->next;
			delete p;
		}
	}
	//求双循环链表的长度
	int Length()
	{
		LinkNode<DateType>* p = head;
		int i = 0;
		while (p->next != head)
		{
			++i;
			p = p->next;
		}
		return i;

	}
	//创建双循环链表
	void CreateList(int n)
	{
		DateType* nodetemp = new DateType[n];
		for (rsize_t i = 0; i < n; i++)
		{
			cout << "Enter the element:  " << endl;
			cin >> nodetemp[i];
			Insert(i, nodetemp[i], 1);
		}
		delete[] nodetemp;
		
	}
	//得到位置为pos的结点元素值
	bool GetElem(int pos,DateType& data)
	{
		LinkNode<DateType>* p = head;
		if (pos<0 || pos>Length())
		{
			cout << "输入的位置不合法" << endl;
			return false;
		}
		else {
			p = Locate(pos, 1);
			data = p->data;
		}
		return true;
	}
	//定位元素，back_pos=0时从头节点向前查第i个元素，d!=0时，从头节点向后找第i个元素
	LinkNode<DateType>* Locate(int i ,int back_pos)
	{
		if (head->next == head || i == 0) {
			return head;
		}
		int j = 0;
		LinkNode<DateType>* p = head;
		//从头节点往后找第i个元素
		if (back_pos)
		{
			while (p->next != head && j != i)
			{
				p = p->next;
				++j;
			}
			if (p->next == head && j != i)
			{
				return NULL;
			}
			else
			{
				return p;
			}

		}//向前找
		else
		{
			while (p->prev != head && j != i)
			{
				p = p->prev;
				++j;
			}
			if (p->prev == head && j != i)
				return NULL;
			else
				return p;
		}
	}
	//在pos的位置插入元素
	bool Insert(int pos, const DateType& data, int back_pos)
	{
		LinkNode<DateType>* p = Locate(pos, back_pos);
		if (!p)
			return false;
		LinkNode<DateType>* new_node = new LinkNode<DateType>(data);
		if (NULL == new_node)
		{
			cout << "内存分配失败" << endl;
			exit(-1);
		}
		//p结点后插入
		if (back_pos)
		{
			p->next->prev = new_node;
			new_node->prev = p;
			new_node->next = p->next;
			p->next = new_node;
		}//p结点前插入
		else
		{
			p->prev->next = new_node;
			new_node->next = p;
			new_node->prev = p->prev;
			p->prev = new_node;
		}return true;
	}
	//输出双循环链表所有结点的元素值,分为正序打印和逆序打印
	void PrintList(int sign)
	{
		//正序打印
		if (sign)
		{
			cout << "head " ;
			LinkNode<DateType>* p = head;
			while (p->next != head)
			{
				p = p->next;
				cout << "-> " << p->data;
			}
			cout << "->over" << endl;
		}//逆序打印
		else
		{
			cout << "head " << endl;
			LinkNode<DateType>* p = head;
			while (p->prev != head)
			{
				p = p->prev;
				cout << "-> " << p->data;
			}
			cout << "->over" << endl;
		}
	}
	//删除pos位置的结点
	bool Delete(int pos, DateType& data,int back_pos)
	{
		LinkNode<DateType>* p = Locate(pos, back_pos);
		if (!p)
		{
			return false;
		}
		if (p == head )
		{
			cout << "请不要删除头节点" << endl;
			return false;
		}
		data = p->data;
		p->prev->next = p->next;
		p->next->prev = p->prev;
		delete p;
		return true;
	}
private:
	LinkNode<DateType>* head;//头节点
};
int main()
{
	LinkList<int> list;
	list.CreateList(5);
	list.PrintList(1);
	cout << "-----------------------" << endl;
	LinkList<int> list2(list);
	list2.PrintList(1);
	cout << "-----------------------" << endl;
	list.Insert(0, 10, 1);
	list.PrintList(1);
	cout << list.Length() << endl;
	cout << "-----------------------" << endl;
	int b = 0;
	list.Delete(0, b, 1);
	cout << b << endl;
	list.PrintList(1);
	cout << list.Length() << endl;
	cout << "-----------------------" << endl;
	list.GetElem(3, b);
	cout << b << endl;
	cout <<"---------------------------" << endl;
	system("pause");
	return EXIT_SUCCESS;
}

链表和顺序表的对比

参考下表:

不同点	顺序表	链表
存储空间上	物理上连续	逻辑上连续
随机访问	支持	不支持
任意位置插入删除	要移动元素，O(N)	只要改变指针指向
插入数据	要考虑扩容，会带来一定的空间消耗	没有容量这个概念，可以按需申请和释放
缓存利用率	高	低

最后此篇关于数据结构初阶--双向循环链表（讲解+类模板实现）的文章就讲到这里了,如果你想了解更多关于数据结构初阶--双向循环链表（讲解+类模板实现）的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

25

4

0

文章推荐：基于桶的排序之计数排序

文章推荐： Selenium4+Python3系列（九）-上传文件及滚动条操作

文章推荐：学习ASP.NETCoreBlazor编程系列十三——路由（完）

php - for 循环 vs while 循环 vs foreach 循环 PHP
我是 PHP 新手。我一直在脚本中使用 for 循环、while 循环、foreach 循环。我想知道哪个性能更好？选择循环的标准是什么？当我们在另一个循环中循环时应该使用哪个？我一直想知道要
java - 编写 for 循环/while 循环？
我在高中的编程课上，我的作业是制作一个基本的小计和顶级计算器，但我在一家餐馆工作，所以制作一个只能让你在一种食物中读到。因此，我尝试让它能够接收多种食品并将它们添加到一个价格变量中。抱歉，如果某些代码
javascript - 为成分编写 while 循环/for 循环。
这是我正在学习的一本教科书。 var ingredients = ["eggs", "milk", "flour", "sugar", "baking soda", "baking powder",
Javascript 添加前导零适用于 while 循环，但不适用于 for 循环
我正在从字符串中提取数字并将其传递给函数。我想给它加 1，然后返回字符串，同时保留前导零。我可以使用 while 循环来完成此操作，但不能使用 for 循环。 for 循环只是跳过零。 var add
java - 程序适用于 for 循环，但不适用于 while 循环？
编辑:我已经在程序的输出中进行了编辑。该程序要求估计给定值 mu。用户给出一个值 mu，同时还提供了四个不等于 1 的不同数字(称为 w、x、y、z)。然后，程序尝试使用 de Jaeger 公式找
Java For 循环 vs While 循环，奇怪的行为和时间性能
我正在编写一个算法，该算法对一个整数数组从末尾到开头执行一个大循环，其中包含一个 if 条件。第一次条件为假时，循环可以终止。因此，对于 for 循环，如果条件为假，它会继续迭代并进行简单的变量更改
java - While 循环 vs For 循环，哪个更节省内存!
现在我已经习惯了在内存非常有限的情况下进行编程，但我没有答案的一个问题是:哪个内存效率更高；- for(;;) 或 while() ？还是它们可以平等互换？如果有的话，还要对效率问题发表评论! 最佳答
java - 一个 while 循环，其中包含一个 if 语句和一个 for 循环
这个问题已经有答案了: How do I compare strings in Java? (23 个回答) 已关闭 8 年前。我正在尝试创建一个小程序，我可以在其中读取该程序的单词。如果单词有 6
python - 弹出索引超出范围 - 作业(列表，for 循环，while 循环)
这个问题在这里已经有了答案: python : list index out of range error while iteratively popping elements (12 个答案) 关
java - JOptionPane.showInputDialog 循环(使用 do while 循环)
我正在尝试向用户请求 4 到 10 之间的整数。如果他们回答超出该范围，它将进入循环。当用户第一次正确输入数字时，它不会中断并继续执行 else 语句。如果用户在 else 语句中正确输入数字，它将正
php - 嵌套的 foreach 循环，break inside 循环
我尝试创建一个带有嵌套 foreach 循环的列表。第一个循环是循环一些数字，第二个循环是循环日期。我想给一个日期写一个数字。所以还有另一个功能来检查它。但结果是数字多次写入日期。 Out 是这样的:
java - 在 while 循环(或 for 循环)内创建一个数组，然后在外部使用该数组
我想要做的事情是使用循环创建一个数组，然后在另一个类中调用该数组，这不会做，也可能永远不会做。解决这个问题最好的方法是什么？我已经寻找了所有解决方案，但它们无法编译。感谢您的帮助。 import ja
php - 嵌套的 foreach 循环，break inside 循环
我尝试创建一个带有嵌套 foreach 循环的列表。第一个循环是循环一些数字，第二个循环是循环日期。我想给一个日期写一个数字。所以还有另一个功能来检查它。但结果是数字多次写入日期。 Out 是这样的:
c - 如何将 'convert' 两个(for 循环)转为一个(while 循环)？
我正在模拟一家快餐店三个多小时。这三个小时分为 18 个间隔，每个间隔 600 秒。每个间隔都会输出有关这 600 秒内发生的情况的统计信息。我原来的结构是这样的: int i; for (i=0;
javascript - ie javascript for in 循环 vs chrome for in 循环
这个问题已经有答案了: IE8 for...in enumerator (3 个回答) How do I check if an object has a specific property in J
java - 编程语言中的 for 循环 VS while 循环，c++/java？
哪个对性能更好？这可能与其他编程语言不一致，所以如果它们不同，或者如果你能用你对特定语言的知识回答我的问题，请解释。我将使用 c++ 作为示例，但我想知道它在 java、c 或任何其他主流语言中的工
c++ - C++11 段错误中基于范围的 for 循环，但不是常规 for 循环
这个问题不太可能帮助任何 future 的访问者；它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况有关，这些情况并不普遍适用于互联网的全局受众。为了帮助使这个问题更广泛地适用，visit
c - while 循环(和 for 循环)上的 scanf 错误，永远扫描
我是 C 编程和编写代码的新手，以确定 M 测试用例的质因数分解。如果我一次只扫描一次，该功能本身就可以工作，但是当我尝试执行 M 次时却惨遭失败。我不知道为什么 scanf() 循环有问题。 in
javascript - 进行修改时应出现 'for-of' 循环，而不是 'for' 循环
这个问题已经有答案了: JavaScript by reference vs. by value [duplicate] (4 个回答) 已关闭 3 年前。我在使用 TSlint 时遇到问题，并且理
javascript - 为 Charts.js 添加 for 循环/foreach 循环
我尝试在下面的代码中添加 foreach 或 for 循环，以便为 Charts.js 创建多个数据集。这将允许我在此折线图上创建多条线。我有一个 PHP 对象，我可以对其进行编码以稍后填充变量，但

首页

博学

6Ren·AI

商城