6

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

 1 year ago
source link: https://www.cnblogs.com/yzsn12138/p/16928086.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

带头双向链表的结构

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

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

  • 数据域和指针域
  • 两个指针，一个指向前驱结点，一个指向后继结点
  • 给定两个构造函数，有参和无参，分别对结点的指针域和数据域进行初始化
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){}
};
2976263-20221126190631040-647395676.png

带头双向链表的接口实现

要实现的接口

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;//头节点
};

初始化双向链表

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

2976263-20221126190645097-1044536896.png
//构造函数,初始化一个循环双链表
	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) 只要改变指针指向
插入数据 要考虑扩容，会带来一定的空间消耗 没有容量这个概念，可以按需申请和释放
缓存利用率 高 低

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK