C++类模板方式实现单链表

时间:2022-06-27 17:40:30

链表通过在构造函数中创建头结点,来建立一个空链表,通过插入(Insert方式)添加元素,可以使用Reverse对单链表翻转,利用“标尺-距离”方法,一次遍历,找到中间节点病返回,在拷贝构造函数中进行深度复制,创建链表,防止浅复制的析构导致的内存泄露。代码有不足,希望指正。

代码以类模板的方式实现,因此需要将类的定义文件设置为.h文件,而类的实现设置为.hpp文件,这样可以防止以.cpp文件包含类实现时第一次编译语法检查不出错,但是再运行时展开失败,报错。

LinkList.h文件:

#ifndef __LinkList_H_
#define __LinkList_H_

template <class T>
struct LinkListNode{
LinkListNode* next;
T item;
};

template <class T>
class LinkList
{
private:
LinkListNode<T>* _header;
int _length;
public:
//the constructor 1:create a list;
LinkList();
//copy constructor 2:copy a new list from a source list
LinkList(const LinkList<T>& list);
//the destructor:destroy a lsit;
~LinkList();
//get the size of the list;
int LinkList_Length();
//insert a element in the list at the (pos)th position;
bool LinkList_Insert(T item, int pos);
//get the element in the list at the (pos)th position;
T LinkList_Get(int pos);
//Delete the (pos)th position
T LinkList_Delete(int pos);

//Reverse the list
void LinkList_Reverse();

//Get the middle element in the list
T LinkList_Middle();
};
#endif

LinkList.hpp文件:

#ifndef __LinkList_DEF_HPP_
#define __LinkList_DEF_HPP_

#include <iostream>
#include "LinkList.h"

using namespace std;

//the constructor:create a list;
template <class T>
LinkList<T>::LinkList()
{
_header = new LinkListNode < T > ;
if (_header != NULL)
{
_length = 0;
_header->next = NULL;
_header->item = _length;
}
else
{
delete _header;
_header = NULL;
}
}


//copy constructor 2:copy a new list from a source list
template <class T>
LinkList<T>::LinkList(const LinkList<T>& list)//深度拷贝
{
if (list._header == NULL)
return;

LinkListNode<T>* src_current = list._header->next;
LinkListNode<T>* node = new LinkListNode < T > ;
this->_header = node;//创建头指针
node->item = src_current->item;//拷贝头指针的数据

while (src_current != NULL)
{
LinkListNode<T>*current = new LinkListNode < T > ;//为下一个节点申请空间
current->item = src_current->item;
current->next = NULL;
node->next = current;
node = current;
src_current = src_current->next;
this->_length++;
}
}


//the destructor:destroy a lsit;
template <class T>
LinkList<T>::~LinkList()
{
LinkListNode<T>* temp = _header->next;
LinkListNode<T>* buf;
while (temp != NULL)
{
buf = temp;
temp = temp->next;
cout << "delete: " << buf->item << endl;
delete buf;
}
delete _header;//删除单链表头指针
cin.get();
}
//get the size of the list;
template <class T>
int LinkList<T>::LinkList_Length(){
return _length;
}


//insert a element in the list at the (pos)th position;
template <class T>
bool LinkList<T>::LinkList_Insert(T item, int pos)
{
LinkListNode<T>* node = new LinkListNode < T > ;
if ((node == NULL) || (pos < 0))
{
delete node;
node = NULL;
return false;
}
else
{
LinkListNode<T>* current = _header;
for (int i = 0; (i < pos) && (current->next != NULL); ++i)
{
current = current->next;
}

node->item = item;
node->next = current->next;
current->next = node;

_length++;

return true;
}
}


//get the element in the list at the (pos)th position;
template <class T>
T LinkList<T>::LinkList_Get(int pos)
{
int ret = -1;
if ((pos >= 0) && (pos < _length))
{
LinkListNode<T>* current = _header;
for (int i = 0; (i < pos) && (current->next != NULL); ++i)
{
current = current->next;
}
ret = current->next->item;
}
return ret;
}


//Delete the (pos)th position
template <class T>
T LinkList<T>::LinkList_Delete(int pos)
{
T ret = -1;
LinkListNode<T>* temp = NULL;
if ((pos >= 0) && (pos < _length))
{
LinkListNode<T>* current = _header;
for (int i = 0; (i < pos) && (current->next != NULL); ++i)
{
current = current->next;
}
temp = current->next;
current->next = temp->next;
_length--;
ret = temp->item;
delete temp;
temp = NULL;
}
return ret;
}


//Reverse the list
template <class T>
void LinkList<T>::LinkList_Reverse()
{
LinkListNode<T>* current = _header->next;
LinkListNode<T>* pnext = NULL;
while (current->next != NULL)
{
pnext = current->next;
current->next = pnext->next;
pnext->next = _header->next;
_header->next = pnext;
}
}

//Get the middle element in the list
template <class T>
T LinkList<T>::LinkList_Middle()
{
LinkListNode<T>* listnode = _header;
LinkListNode<T>* l_listnode = _header;
while (l_listnode->next != NULL )
{
if (l_listnode->next->next != NULL)
{
listnode = listnode->next;
l_listnode = l_listnode->next->next;
}
else
{
listnode = listnode->next;
l_listnode = l_listnode->next;
}
}

return listnode->item;
}
#endif