前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >【链表】还不会用C++实现链表？一文教会你各种链表的实现

【链表】还不会用C++实现链表？一文教会你各种链表的实现

作者头像
用户10923276
发布于 2024-03-28 18:19:16
2020
发布于 2024-03-28 18:19:16
举报
文章被收录于专栏：北飞的山羊知识库北飞的山羊知识库

本文将用C++语言来实现数据结构中的无头单链表，带头循环链表，以及带头循环双向链表等链表结构（带头单链表与后两种链表的结构相似，实现起来比后两种更简单，读者阅读完本文即可自行实现）

一、无头单链表的实现

无头单链表在头插时需要改变头指针的位置，具体代码实现如下：

代码语言：javascript
复制
//无头单链表

#include <iostream>
#include <assert.h>

using namespace std;

template <class T>

//先定义链表中的节点
struct SListNode
{
	T data;
	SListNode* next;

	SListNode(T x)
	{
		this->data = x;
		this->next = nullptr;
	}
};

template <class T>
class SList
{
private:
	//链表初始化后链表中就有一个节点
	SListNode<T>* head;
	
public:
	SList(T x)
	{
		this->head = new SListNode<T>(x);
	}

	~SList()
	{
		SListNode<T>* cur = head;
		while (cur)
		{
			SListNode<T>* next = cur->next;
			delete cur;
			cur = next;
		}
	}


	// 动态申请一个节点
	SListNode<T>* BuySListNode(T x);

	// 单链表打印
	void SListPrint();

	// 单链表尾插
	void SListPushBack(T x);

	// 单链表的头插
	void SListPushFront(T x);

	// 单链表的尾删
	void SListPopBack();

	// 单链表头删
	void SListPopFront();

	// 单链表查找
	SListNode<T>* SListFind(T x);

	// 单链表在pos位置之后插入x
	void SListInsertAfter(SListNode<T>* pos, T x);

	// 单链表删除pos位置之后的值
	void SListEraseAfter(SListNode<T>* pos);

};


template <class T>
SListNode<T>* SList<T>:: BuySListNode(T x)
{
	SListNode<T>* tmp = new SListNode<T>(x);
	tmp->next = nullptr;
	return tmp;
}

template <class T>
void SList<T>::SListPrint()
{
	SListNode<T>* cur =head;
	while (cur)
	{
		cout << cur->data << "->";
		cur = cur->next;
	}
	cout << "NULL" << endl;
}

template <class T>
void SList<T>::SListPushBack(T x)
{
	SListNode<T>* cur = head;

	while (cur->next)
	{
		cur = cur->next;
	}
	SListNode<T>* newnode = BuySListNode(x);
	cur->next = newnode;//连接
}
template <class T>
void SList<T>::SListPushFront(T x)
{
	SListNode<T>* newnode = BuySListNode(x);
	newnode->next = head;
	head = newnode;
}

template <class T>
void SList<T>::SListPopBack()
{
	assert(head);//头结点为空就不能继续删除了
	SListNode<T>* tail = head;
	//链表中只有一个节点就只能删除头结点
	if (tail->next == nullptr)
	{
		delete head;
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		delete tail->next;
		tail->next = nullptr;
	}

}

template <class T>
void SList<T>::SListPopFront()
{
	assert(head);
	SListNode<T>* cur = head->next;
	delete head;
	head = cur;
}

template <class T>
SListNode<T>* SList<T>::SListFind(T x)
{
	assert(head);
	SListNode<T>* cur = head;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return nullptr;
}

template <class T>
void SList<T>::SListInsertAfter(SListNode<T>* pos, T x)
{
	assert(pos);
	SListNode<T>* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


template <class T>
void SList<T>::SListEraseAfter(SListNode<T>* pos)
{
	assert(pos->next && pos);
	SListNode<T>* cur = pos->next;
	pos->next = pos->next->next;
	delete cur;
}


int main()
{

	SList<int> cur(1);

	cur.SListPushBack(2);
	cur.SListPushBack(3);
	cur.SListPushBack(4);
	cur.SListPushBack(5);
	cur.SListPushBack(6);
	cur.SListPrint();

	cur.SListPopFront();
	cur.SListPrint();

	cur.SListPopBack();
	cur.SListPrint();

	SListNode<int>* p1 = cur.SListFind(2);
	cur.SListInsertAfter(p1, 20);
	cur.SListPrint();

	cur.SListEraseAfter(p1);
	cur.SListPrint();


	
	return 0;
}

二、带头循环链表的实现

带头意味着链表中会一直存在着一个头结点，无论链表的插入还是删除都是对头结点后面的节点进行的操作。头插的节点也是直接连接在头结点的下一个结点，不会改变头结点。循环意味着尾节点的next指针指向头节点，就像是形成了一个环一样。

具体实现代码如下：

代码语言：javascript
复制
#include <iostream>
#include <assert.h>

using namespace std;

template <class T>
struct Node
{
	T data;
	struct Node* next;
	Node()
	{
		this->data = 0;
		this->next = nullptr;
	}
	Node(T data)
	{
		this->data = data;
		this->next = nullptr;
	}
};

template <class T>
class SList
{
private:
	Node<T>* head;
	Node<T>* tail;
public:
	SList()
	{
		this->head = new Node<T>();
		this->tail = head;
	}

	~SList()
	{
		Node<T>* p = head;
		Node<T>* q = head;
		while (p != tail)
		{
			q = p->next;
			delete p;
			p = q;
		}
		delete tail;
	}

	
	// 动态申请一个节点
	Node<T>* BuySListNode(T x);

	// 单链表打印
	void SListPrint();

	// 单链表尾插
	void SListPushBack(T x);

	// 单链表的头插
	void SListPushFront(T x);

	// 单链表的尾删
	void SListPopBack();

	// 单链表头删
	void SListPopFront();

	// 单链表查找
	Node<T>* SListFind( T x);

	// 单链表在pos位置之后插入x
	void SListInsertAfter(Node<T>* pos, T x);

	// 单链表删除pos位置之后的值
	void SListEraseAfter(Node<T>* pos);

};

template <class T>
Node<T>* SList<T>::BuySListNode(T x)
{
	Node<T>* tmp = new Node<T>;
	tmp->data = x;
	tmp->next = nullptr;
	return tmp;
}

template <class T>
void SList<T>::SListPrint()
{
	assert(head->next);//保证头节点后还有结点才打印，不然报错
	Node<T>* cur = head->next;
	while (cur != head)
	{
		cout << cur->data << "->";
		cur = cur->next;
	}
	cout << "NULL" << endl;
}

template <class T>
void SList<T>::SListPushBack(T x)
{
	Node<T>* newnode = BuySListNode(x);
	tail->next = newnode;
	tail = newnode;
	tail->next = head;//尾节点的next指向头节点
}

template <class T>
void SList<T>::SListPushFront(T x)
{
	Node<T>* newnode = BuySListNode(x);
	if (head == tail)
	{
		head->next = newnode;
		tail = newnode;
		tail->next = head;
	}
	else
	{
		newnode->next = head->next;
		head->next = newnode;
	}
}

template <class T>
void SList<T>::SListPopBack()
{
	assert(head->next);
	Node<T>* cur = head;
	while (cur->next != tail)
	{
		cur = cur->next;
	}
	delete tail;
	tail = cur;
	tail->next = head;

}

template <class T>
void SList<T>::SListPopFront()
{
	assert(head->next);
	Node<T>* cur = head->next;

	if (head->next == tail)
	{
		delete tail;
		tail = head;
	}
	else
	{
		head->next = cur->next;
		delete cur;
	}
}

template <class T>
Node<T>* SList<T>::SListFind(T x)
{
	assert(head->next);
	Node<T>* cur = head->next;
	while (cur != head)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return nullptr;
}

template <class T>
void SList<T>::SListInsertAfter(Node<T>* pos, T x)
{
	assert(pos);
	if (pos->next == head)
	{
		SListPushBack(x);
	}
	else if(pos == head)
	{
		SListPushFront(x);
	}
	else
	{
		Node<T>* newnode = BuySListNode(x);
		newnode->next = pos->next;
		pos->next = newnode;
	}
}
template <class T>
void SList<T>::SListEraseAfter(Node<T>* pos)
{
	assert(pos);
	//尾节点后的头节点不能删
	if (pos->next == head)
	{
		exit(-1);
	}
	else if (pos == head)
	{
		SListPopFront();
	}
	else
	{
		Node<T>* cur = pos->next;
		pos->next = pos->next->next;
		delete cur;
	}
}


int main()
{

	SList<int> SL1;
	SL1.SListPushBack(1);
	SL1.SListPushBack(2);
	SL1.SListPushBack(3);
	SL1.SListPushBack(4);
	SL1.SListPushBack(5);
	SL1.SListPrint();

	SL1.SListPushFront(10);
	SL1.SListPrint();

	SL1.SListPopFront();
	SL1.SListPrint();

	SL1.SListPopBack();
	SL1.SListPrint();

	Node<int>* cur = SL1.SListFind(2);
	SL1.SListInsertAfter(cur, 20);
	SL1.SListPrint();

	SL1.SListEraseAfter(cur);
	SL1.SListPrint();

	return 0;
}

三、带头双向循环链表的实现

具体实现思路与带头循环链表大同小异，只是在节点中需要增加一个指向前一个节点的指针。

具体实现代码如下：

代码语言：javascript
复制
#include <iostream>
#include <assert.h>

using namespace std;

template <class T>
struct Node
{
	T data;
	struct Node* prev;//指向前一个节点的指针
	struct Node* next;
	Node()
	{
		this->data = 0;
		this->prev = nullptr;
		this->next = nullptr;
	}
	Node(T data)
	{
		this->data = data;
		this->prev = nullptr;
		this->next = nullptr;
	}
};

template <class T>
class SList
{
private:
	Node<T>* head;//头节点
	Node<T>* tail;//尾节点
public:
	SList()
	{
		this->head = new Node<T>();
		head->next = nullptr;
		head->prev = nullptr;
		this->tail = head;
	}

	~SList()
	{
		Node<T>* p = head;
		Node<T>* q = head;
		while (p != tail)
		{
			q = p->next;
			delete p;
			p = q;
		}
		delete tail;
	}

	Node<T>* getHead()
	{
		return this->head;
	}

	// 动态申请一个节点
	Node<T>* BuySListNode(T x);

	// 单链表打印
	void SListPrint();

	// 单链表尾插
	void SListPushBack(T x);

	// 单链表的头插
	void SListPushFront(T x);

	// 单链表的尾删
	void SListPopBack();

	// 单链表头删
	void SListPopFront();

	// 单链表查找
	Node<T>* SListFind(T x);

	// 单链表在pos位置之后插入x
	void SListInsertAfter(Node<T>* pos, T x);

	// 单链表删除pos位置之后的值
	void SListEraseAfter(Node<T>* pos);

};

template <class T>
Node<T>* SList<T>::BuySListNode(T x)
{
	Node<T>* tmp = new Node<T>;
	tmp->data = x;
	tmp->prev = nullptr;
	tmp->next = nullptr;
	return tmp;
}

template <class T>
void SList<T>::SListPrint()
{
	assert(head->next);
	Node<T>* cur = head->next;
	while (cur != head)
	{
		cout << cur->data << "<->";
		cur = cur->next;
	}
	cout << endl;
}

template <class T>
void SList<T>::SListPushBack(T x)
{
	Node<T>* newnode = BuySListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	tail = newnode;
	tail->next = head;
	head->prev = tail;
}

template <class T>
void SList<T>::SListPushFront(T x)
{
	Node<T>* newnode = BuySListNode(x);
	if (head == tail)//头节点后没有节点
	{
		head->next = newnode;
		newnode->prev = head;
		tail = newnode;
		tail->next = head;
		head->prev = tail;
	}
	else
	{
		newnode->next = head->next;
		newnode->prev = head;
		head->next = newnode;
	}
}

template <class T>
void SList<T>::SListPopBack()
{
	assert(head->next);

	Node<T>* cur = tail->prev;
	head->prev = tail->prev;
	delete tail;
	tail = cur;
	tail->next = head;
	
}


template <class T>
void SList<T>::SListPopFront()
{
	assert(head->next);//只剩头节点不删
	Node<T>* cur = head->next;

	if (head->next == tail)//头节点后只有一个节点
	{
		delete tail;
		tail = head;
		head->next = head;
		head->prev = head;
	}
	else
	{
		head->next = cur->next;
		cur->next->prev = head;
		delete cur;
	}
}

template <class T>
Node<T>* SList<T>::SListFind(T x)
{
	assert(head->next);
	Node<T>* cur = head->next;
	while (cur != head)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return nullptr;
}

template <class T>
void SList<T>::SListInsertAfter(Node<T>* pos, T x)
{
	assert(pos);
	if (pos->next == head)
	{
		SListPushBack(x);
	}
	else if (pos == head)
	{
		SListPushFront(x);
	}
	else
	{
		Node<T>* newnode = BuySListNode(x);
		newnode->next = pos->next;
		newnode->prev = pos;
		pos->next = newnode;
	}
}


template <class T>
void SList<T>::SListEraseAfter(Node<T>* pos)
{
	assert(pos);
	if (pos->next == head)//尾节点后的头节点不删
	{
		exit(-1);
	}
	else if (pos == head)
	{
		SListPopFront();
	}
	else
	{
		Node<T>* cur = pos->next;
		pos->next = pos->next->next;
		pos->next->prev = pos;
		delete cur;
	}
}


int main()
{
	//SListNode<int>* head = new SListNode<int>;

	SList<int> SL1;
	SL1.SListPushBack(1);
	SL1.SListPushBack(2);
	SL1.SListPushBack(3);
	SL1.SListPushBack(4);
	SL1.SListPushBack(5);
	SL1.SListPrint();

	SL1.SListPushFront(10);
	SL1.SListPrint();

	SL1.SListPopFront();
	SL1.SListPrint();

	SL1.SListPopBack();
	SL1.SListPrint();

	Node<int>* cur = SL1.SListFind(2);
	SL1.SListInsertAfter(cur, 20);
	SL1.SListPrint();

	SL1.SListEraseAfter(cur);
	SL1.SListPrint();

	return 0;
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-03-28，如有侵权请联系 cloudcommunity@tencent.com 删除
class
tail
void
链表
c++

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

class
tail
void
链表
c++
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 一、无头单链表的实现
  • 二、带头循环链表的实现
  • 三、带头双向循环链表的实现
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2024 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论