C++语言实现双向链表

这篇文章是关于利用C++模板的方式实现的双向链表以及双向链表的基本操作,在之前的博文C语言实现双向链表中,已经给大家分析了双向链表的结构,并以图示的方式给大家解释了双向链表的基本操作。本篇文章利用C++实现了双向链表的基本操作,其中包括:

双向链表的基本操作C++语言实现

双向链表 实现的功能
头部插入结点建立链表 尾部插入结点建立链表
实现指定位置插入结点 查找给定数值是否存在
删除指定位置的结点 修改指定位置的结点
双向链表的长度 打印双向链表

定义双向链表的结点

因为双向链表的结点由三部分构成,用于指向当前节点的直接前驱节点指针域,用于存储数据元素数据域 ,以及用于指向当前节点的直接后继节点指针域

因此,首先我们需要封装一个结点类,定义了结点的三个要素,并利用构造函数实现初始化,另外,考虑到在双向链表中要用到结点类,所以将双向链表类定义为结点的友元类。

class doubleLinkedListNode
{
	private:
		doubleLinkedListNode<T> *prior;//双向结点前驱指针指向该结点的前驱结点
		T data;//储存结点数据
		doubleLinkedListNode<T> *next;//双向结点的后驱指针指向该结点的后继结点
		//将双向链表类定义为结点的友元类
		friend  class doubleLinkedList<T>;
	public:
		//结点的无参构造函数,将结点指针域初始化为NULL
		doubleLinkedListNode()
		{
			prior = NULL;
			next = NULL;
		}
		//结点的有参构造函数,初始化指针域和数据域
		doubleLinkedListNode(T _data,doubleLinkedListNode<T> *_prior = NULL,doubleLinkedListNode<T> *_next = NULL)
		{
			prior = _prior;//初始化前驱指针
			data = _data;//初始化数据域
			next = _next;//初始化后继指针
		}
		~doubleLinkedListNode()
		{
			prior = NULL;
			next = NULL;
		}
};

双向链表的基本操作

实现了双向链表头部插入结点, 尾部插入结点,指定位置插入结点建立链表, 查找给定数值的指定位置,删除指定位置的结点,修改指定位置的结点,双向链表的长度,打印双向链表,接下来逐一进行讲解实现:

头部插入结点建立链表

带头结点实现的双向链表,实现头部插入结点可分为两种情况,一种是只有一个头结点的时候,只需要使headnewNode的两个指针关联上即可,另外的两个指针依旧是NULL状态。另一种情况便是有结点的情况,这个时候跟在中间结点插入相似,需要调整四个指针,首先是让newNode与后继结点关联,最后让newNodehead结点关联。
因此,头部插入结点实现如下:

template<class T>
bool doubleLinkedList<T>::insertNodeByhead(T item)
{
	//创建一个新的结点
	doubleLinkedListNode<T>* newNode = new doubleLinkedListNode<T>(item);
	if (newNode == NULL){
		cout << "内存分配失败,新结点无法创建" << endl;
		return false;
	}
	//分两种情况,head的next是否为NULL,然后处理四个指针
	if(head->next == NULL)
	{
		head->next = newNode;
		newNode->prior = head;
		return true;
	}
	else{
		newNode->next = head->next;
		head->next->prior = newNode;
		newNode->prior = head;
		head->next = newNode;
		return true;
	}
}

尾部插入结点建立链表

在尾部插入结点,当然第一步需要找到最后一个结点,然后在其后进行插入,双向链表因为两端的指针都是指向NULL的,所以在尾部插入也只需要调整两个指针就ok.

template<class T>
bool doubleLinkedList<T>::insertNodeBytail(T item)
{
	//创建一个新的结点
	doubleLinkedListNode<T>* newNode = new doubleLinkedListNode<T>(item);
	if (newNode == NULL){
		cout << "内存分配失败,新结点无法创建" << endl;
		return false;
	}
	//首先找到最后一个结点
	doubleLinkedListNode<T>* lastNode = head;
	while(lastNode->next != NULL)
	{
		lastNode = lastNode->next;//没找到就一直循环
	}
	//找到调整指针
	lastNode->next = newNode;
	newNode->prior = lastNode;
	return true;
}

实现指定位置插入结点

在指定位置插入只需要两步走,首先也是找到指定的位置,然后就是插入新结点的指针的调整,中间插入是最复杂的,都逃不过调整四个指针,但是首先依旧是让新结点和后继结点建立上相关性,最后让新结点与前继结点建立关系,实现新结点的插入。

bool doubleLinkedList<T>::insertNode(T item,int n)
{
	if(n<1){
		cout<<"输入的非有效位置!"<<endl;
		return false;
	}
	doubleLinkedListNode<T>* pMove = head;//创建一个新的指针,设置为游标指针
	//首先找到插入位置
	for(int i=1;i<n;i++)
	{
		pMove = pMove->next;
		if(pMove == NULL&& i<=n)
		{
			cout<<"插入位置无效!"<<endl;
			return false;
		}
	}
	//创建一个新的结点
	doubleLinkedListNode<T>* newNode = new doubleLinkedListNode<T>(item);
	if (newNode == NULL){
		cout << "内存分配失败,新结点无法创建" << endl;
		return false;
	}
	//插入新的结点
	newNode->next = pMove->next;   
	if (pMove->next != NULL)
	{
		pMove->next->prior = newNode;
	}
	newNode->prior = pMove;
	pMove->next = newNode;
	return true;
}

查找给定数值是否存在

查找给定元素,也就是一个遍历链表的过程,从头结点的下一个结点开始遍历,毕竟第一个头结点是没有储存数据项的。

template<class T>
bool doubleLinkedList<T>::findData(T item)
{
	doubleLinkedListNode<T> *pMove = head->next;  //设置游标指针
	if(pMove == NULL)//链表为空
	{
		return false;
	}
	while(pMove)//遍历链表
	{
		if(pMove->data == item){
			return true;
		}
		pMove = pMove->next;
	}
	return false;
}

删除指定位置的结点

删除指定的结点,第一步查找到删除的结点,需要定义一个删除指针临时指向将要删除的结点,最后指针处理删除之后别忘了释放该结点空间。

template<class T>
bool doubleLinkedList<T>::deleteData(int n)
{
	if (n<1||n>getLength())
	{
		cout << "输入非有效位置" << endl;
		return false;
	}
	doubleLinkedListNode<T> * pMove = head;//设置游标指针
	doubleLinkedListNode<T> * pDelete;             
	//查找删除结点的位置
	for (int i = 1; i <= n; i++)
	{
		pMove = pMove->next;                                         //游标指针后移
	}
	//删除结点
	pDelete = pMove;      
	pMove->prior->next = pDelete->next;
	pMove->next->prior = pDelete->prior;
	delete pDelete;//释放空间
	return true;
}

修改指定位置的结点

修改指定位置的结点数据,当然还是得找到指定位置,然后对其进行修改,修改之后将原来的数据以引用的形式返回,具体的用法在测试函数中写到了的,不会的可以作为参考。

template<class T>
bool doubleLinkedList<T>::changeListElements(int n,T item,T &x)
{
	if (n<1||n>getLength())
	{
		cout << "输入非有效位置" << endl;
		return false;
	}
	doubleLinkedListNode<T> *pMove = head->next;  //设置游标指针
	for(int i=1;i<n;i++)//找到指定位置1
	{
		pMove = pMove->next;
	}
	x = pMove->data;
	pMove->data = item;
	return true;
}

双向链表的长度

计算双向链表的长度的函数,在双向链表的私有成员封装了一个变量length,以此来记录双向链表的长度,遍历双向链表,逐一进行计算结点数就是双向链表的长度。

template<class T>
int doubleLinkedList<T>::getLength()
{
	doubleLinkedListNode<T> *pMove = head->next;  //设置游标指针
	int length=0;
	//遍历链表,计算结点数
	while(pMove!=NULL)
	{
		pMove = pMove->next;  //游标指针后移
		length++;       //计算length
	}
	return length;
}

打印双向链表

打印双向链表,从第二个结点开始遍历链表,因为第一个为头结点是不含数据的,打印的过程也就是一个遍历的过程。

template<class T>
void doubleLinkedList<T>::printLinkedlist()
{
	//从第二个结点开始打印,表头不含数据
	doubleLinkedListNode<T>* pMove = head->next;
	while(pMove)
	{
		cout<<pMove->data<<" ";
		pMove = pMove->next;//移动指针
	}
	cout<<endl;
}

以上就是本次博文与大家分享的利用C++语言实现双向链表,在用C语言写了之后,感觉写起来就比较轻松,唯一不同的就是要利用类来进行封装。完整的代码,以及测试代码我已经Push到Github,喜欢的小伙伴欢迎Star! C++语言实现双向链表Github地址,如果还想要了解其他的数据结构实现的小伙伴也可以来我的Myblog,我们一起讨论,如果有写的不好的地方还请多多担待,也欢迎大家在评论区留言,我加以改正,共同进步!

原文地址:https://www.cnblogs.com/xiangjunhong/p/12482457.html