C++模板实现泛型链表

ゞ浴缸里的玫瑰 2022-08-04 05:15 242阅读 0赞

链表是一个比较基础的数据结构，也是理解其他数据结构和算法和基础。传统C实现的链表其代码复用性比较差，其在C++中，list是对链表的一个通用实现。本文作者也尝试了用模板来实现一个通用型的链表，下面给出代码，以供参考，如有错误，请联系笔者改正。

首先利用C++模板实现一个链表的结点数据结构，其实现如下：

在头文件node.h中：

#pragma once
 #ifndef __UNIT
 #define __UNIT
 template<typename T>
 class node
 {
 public:
 	node();
 	node(T d);
 	~node();
 public:
 	T data;
 	node<T> *pre;
 	node<T> *next;
 };
 #endif

在CPP文件node.cpp中：

#include "node.h"
 template<typename T>
 node<T>::node()
 {
 	pre = nullptr;
 	next = nullptr;
 }
 
 template<typename T>
 node<T>::node(T d)
 {
 	pre = nullptr;
 	next = nullptr;
 	data = d;
 }
 
 template<typename T>
 node<T>::~node()
 {
 }

然后是实现链表数据结构头文件(BaseList.h)：

#pragma once
 #include "node.h"
 #include "node.cpp"
 #ifndef __BASELIST
 #define __BASELIST
 template<typename T>
 class BaseList
 {
 public:
 	BaseList();
 	BaseList(T d);
 	~BaseList();
 	//在链表尾插入数据
 	node<T> *push_back(T data);
 	//在链表第pos位尾插入数据
 	node<T> *push_back(T data,size_t pos);
 	在链表尾结点node后插入数据
 	node<T> *push_back(node<T> *nod);
 	//删除链表表尾
 	node<T> *pop();
 	//删除链表相应结点，如果存在多个，则一同删除
 	node<T> *pop(node<T> *nod);
 	//删除相应位置结点
 	node<T> *pop(size_t pos);
 	//返回链表首元素
 	node<T> *top();
 	//清空链表
 	void empty();
 	//逆置链表
 	void reverse();
 	//求链表长度
 	size_t length();
 private:
 	node<T> *head;//表头，头结点不存储元素
 	node<T> *curr;//当前结点，也就是尾结点
 	size_t size;
 };
 #endif

</pre><pre name="code" class="cpp">可以从头文件中看到链表提供的功能。

</pre>最后是链表的实现CPP文件（BaseList.cpp）<pre name="code" class="cpp">#include "BaseList.h"
 template<typename T>
 BaseList<T>::BaseList()
 {
 	head = new node < T >() ;//关结点总是存在的，它不是有效的结点，只是用于标识表头
 	head->data = 0;
 	curr = head;
 	size = 0;
 }
 
 template<typename T>
 BaseList<T>::BaseList(T d)//通过一个特殊的值来标识表头
 {
 	head = new node < T >();//关结点总是存在的，它不是有效的结点，只是用于标识表头
 	head->data = d;
 	curr = head;
 	size = 0;
 }
 
 template<typename T>
 BaseList<T>::~BaseList()
 {
 	if (size == 0)
 		return;
 	node<T> *nod = head;
 	node<T> *temp;
 	while (nod)
 	{
 		temp = nod;
 		nod = nod->next;
 		delete temp;
 	}
 }
 
 //在链表尾插入数据
 template<typename T>
 node<T>* BaseList<T>::push_back(T data)
 {
 	node<T> *nod = new node<T>();//新建节点
 	nod->data = data;
 	curr->next = nod;//将节点加入到链表中
 	curr = nod;//更新当前节点
 	size++;
 	return nod;
 }
 
 //在链表第pos位(从0开始)尾插入数据
 template<typename T>
 node<T>* BaseList<T>::push_back(T data, size_t pos)
 {
 	node<T> *nod = nullptr;
 	if (pos == size+1)//插入的位置与长度加1相等，则相等于在链表尾进行插入
 	{
 		push_back(data);
 	}
 	else if ((size&&pos) && (pos <= size))//如果 (0<size && 0<pos<=size)
 	{
 		node<T> *tempfrom=head,*temp = head->next;
 		while (pos--)
 		{
 			tempfrom = temp;
 			temp = temp->next;
 		}
 		nod = new node<T>();//新建节点
 		nod->next = temp;
 		nod->data = data;
 		tempfrom->next = nod;
 		size++;
 	}
 	else
 	{
 		return nullptr;
 	}
 	return nod;
 }
 
 //在链表尾结点node后插入数据
 template<typename T>
 node<T>* BaseList<T>::push_back(node<T> *nod)
 {
 	if (nod != nullptr)
 	{
 		curr->next = nod;
 		curr = nod;
 		size++;
 	}
 	return nod;
 }
 
 //删除链表表尾
 template<typename T>
 node<T>* BaseList<T>::pop()
 {
 	if (size == 0)
 		return nullptr;
 	node<T> *temp = head;
 	size_t n = 1;
 	while (n != size)//找到最后一个结点的前一个结点
 	{
 		temp = temp->next;
 		n++;
 	}
 	curr = temp;
 	delete temp->next;
 	temp->next = nullptr;
 	size--;
 	return temp;
 }
 
 //删除相应位置结点,返回删除结点的前一个结点
 template<typename T>
 node<T>* BaseList<T>::pop(size_t pos)
 {
 	if (size == 0||pos+1>size)
 		return nullptr;
 	node<T> *temp = head;
 	size_t n = 1;
 	pos = pos + 1;
 	while (n!=pos)//找到特定结点的前一个结点
 	{
 		temp = temp->next;
 		n++;
 	}
 	node<T> *del = temp->next;//这个del指向要删除的结点
 	temp->next=temp->next->next;
 	if (temp->next == nullptr)//如果删除的是最后一个结点
 		curr = temp;
 	delete del;
 	size--;
 	return temp;
 }
 
 //删除链表相应结点，如果存在多个，则一同删除
 template<typename T>
 node<T>* BaseList<T>::pop(node<T> *nod)
 {
 	node<T> *del=head->next;
 	size_t pos = 0;
 	while (del)
 	{
 		if (del->data == nod->data)//如果找到了相同的数据，则删除
 			del=pop(pos);
 		del = del->next;
 		pos++;
 
 	}
 	return curr;
 }
 
 //返回链表首元素
 template<typename T>
 node<T>* BaseList<T>::top()
 {
 	return head->next;
 }
 //清空链表
 template<typename T>
 void BaseList<T>::empty()
 {
 	if (size == 0)
 		return;
 	node<T> *nod = head->next;
 	node<T> *temp;
 	while (nod)
 	{
 		temp = nod;
 		nod = nod->next;
 		delete temp;
 	}
 	size = 0;
 }
 
 //逆置链表
 template<typename T>
 void BaseList<T>::reverse()
 {
 	node<T> *p1, *p2, *p3;
 	if (head->next != nullptr&&head->next->next!=nullptr)
 	{
 		p1 = head->next;//首先指向第一个节点
 		p2 = head->next->next;//指向第二个节点
 		while (p2)
 		{
 			p3 = p2->next;
 			p2->next = p1;
 			p1 = p2;
 			p2 = p3;
 		}
 		head->next->next = nullptr;
 		curr = head->next;
 		head->next = p1;
 		
 	}
 }
 
 //求链表长度
 template<typename T>
 size_t BaseList<T>::length()
 {
 	return size;
 }

最后是用于测试的代码，记得一定要将cpp文件和h文件include进来

#include<iostream>
 #include "BaseList.h"
 #include "BaseList.cpp"
 
 using namespace std;
 int main()
 {
 	BaseList<int> mylist;
 	mylist.push_back(1);
 	mylist.push_back(2);
 	mylist.push_back(3);
 	
 
 	node<int> unit(10);
 	mylist.push_back(&unit);
 	mylist.reverse();
 	mylist.pop();
 	mylist.pop(2);
 	return 0;
 }