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

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

#pragma once

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

template
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
int LinkList::length()
{
return m_length;
}

template
T LinkList::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
int LinkList::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
T LinkList::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
void LinkList::clear()
{
while (length())
{
remove(0);
}
}

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

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

测试代码

#include
#include “seqlist.hpp”
#include “LinkList.hpp”

using namespace std;

void LinkListTest()
{
//创建链表
LinkList 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;
}