模版类实现线性表链式储存

同上一篇文章，我们一样是把以前使用C语言实现的单向链表用模版实现了一次，进一步让我们对模版和C++的封装特性有了了解。对于链表的操作我们不过多介绍了，如果有还不清楚操作的，请看以前介绍链表的文章。

#pragma once

// 链表储存数据的结构体
template<typename T>
struct LinkListNode
{
	T data;
	LinkListNode* next;
};

template<typename T>
class LinkList
{
public:
	LinkList();
	~LinkList();

	void clear();					// 清空
	T get(int pos);					// 获取某位置的元素
	int insert(int pos, T& data);	// 插入一个元素
	T remove(int pos);				// 删除一个元素
	int length();					// 获取链表长度

private:
	LinkListNode < T >* m_header;	// 链表头节点
	int m_length;					// 链表长度
};

template<typename T>
int LinkList<T>::length()
{
	return m_length;
}

template<typename T>
T LinkList<T>::remove(int pos)
{
	// 备份头节点指针
	LinkListNode < T >* pCur = m_header;
	// 循环找到pos位置的前一个节点
	for (int i = 0; i < pos; i++)
	{
		if (pCur->next != nullptr)
			pCur = pCur->next;
	}
	// 定义一个指针记录pos位置的节点
	LinkListNode < T >* pDel = pCur->next;
	// 备份节点的数据
	T tData = pDel->data;
	// 改变指针指向，让链表跳过pos位置的节点重新连接
	pCur->next = pDel->next;
	
	// 删除节点并长度--
	delete pDel;
	m_length--;

	// 返回被删除的数据
	return tData;
}

template<typename T>
int LinkList<T>::insert(int pos, T& data)
{
	// 记录头节点位置
	LinkListNode < T >* pCur = m_header;
	// 生成新节点
	LinkListNode < T >* node = new LinkListNode < T > ;

	// 给新节点数据域赋值
	node->data = data;

	// 循环找到 pos 位置的前一个节点的位置
	for (int i = 0; i < pos; i++)
	{
		if (pCur->next != nullptr)
			pCur = pCur->next;
	}

	// 把新节点插入到 pos 的前一个位置并对长度++
	node->next = pCur->next;
	pCur->next = node;
	m_length++;

	return 0;
}

template<typename T>
T LinkList<T>::get(int pos)
{
	// 记录头节点位置
	LinkListNode < T >* pCur = m_header;

	// 循环找到 pos 位置的节点
	for (int i = 0; i <= pos; i++)
	{
		// 如果后面没有节点了，就指向最后一个节点
		if (pCur->next != nullptr)
			pCur = pCur->next;
	}
	// 返回节点数据
	return pCur->data;
}

template<typename T>
void LinkList<T>::clear()
{
	while (length())
	{
		remove(0);
	}
}

template<typename T>
LinkList<T>::~LinkList()
{
	clear();
	// 释放头节点
	delete m_header;
}

template<typename T>
LinkList<T>::LinkList()
{
	// 初始化头节点和长度
	m_header = new LinkListNode < T > ;
	m_header->next = nullptr;
	m_length = 0;
}

测试代码

#include <iostream>
#include "seqlist.hpp"
#include "LinkList.hpp"

using namespace std;

void LinkListTest()
{
	//创建链表
	LinkList<int> list;
	int array[5] = { 0 };
	//初始化
	for (int i = 0; i < sizeof(array) / sizeof(int); ++i)
	{
		array[i] = i;
		//插入数据
		list.insert(array[i], i);
	}

	//遍历链表
	for (int i = 0; i < list.length(); ++i)
	{
		cout << "list emement " << i << " value = " << list.get(i) << endl;
	}

	//删除所有节点
	while (list.length() > 0)
	{
		cout << "Delete element " << list.remove(0) << endl;
	}
}

int main(int argc, char* argv[])
{
	LinkListTest();

	return 0;
}