定义链表的类的声明时采用模版机制，这样虽然繁琐一些，但为将来对链表的复用提供了很大的方便。同时在链表中增加头结点，统一了空表和非空表操作的实现，降低了程序结构的复杂性，减少了出错的概率。
头文件
#ifndef LINKLIST_H
#define LINKLIST_H
#include <cstddef>
#include <iostream>
/* 单链表的结点定义 */
template<class T>
struct LinkNode
{
T data;
LinkNode<T> *next;
LinkNode(LinkNode<T> *ptr = NULL){next = ptr;}
LinkNode(const T &item, LinkNode<T> *ptr = NULL)
//函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
{
next = ptr;
data = item;
}
};
/* 带头结点的单链表定义 */
template<class T>
class LinkList
{
public:
//无参数的构造函数
LinkList(){head = new LinkNode<T>;}
//带参数的构造函数
LinkList(const T &item){head = new LinkNode<T>(item);}
//拷贝构造函数
LinkList(LinkList<T> &List);
//析构函数
~LinkList(){Clear();}
//重载函数:赋值
LinkList<T>& operator=(LinkList<T> &List);
//链表清空
void Clear();
//获取链表长度
int Length() const;
//获取链表头结点
LinkNode<T>* GetHead() const {return head;}
//查找数据的位置，返回第一个找到的满足该数值的结点指针
LinkNode<T>* Find(T &item);
//定位指定的位置，返回该位置上的结点指针
LinkNode<T>* Locate(int pos);
//在指定位置pos插入值为item的结点，失败返回false
bool Insert(T &item, int pos);
//删除指定位置pos上的结点，item就是该结点的值，失败返回false
bool Remove(int pos, T &item);
//获取指定位置pos的结点的值，失败返回false
bool GetData(int pos, T &item);
//设置指定位置pos的结点的值，失败返回false
bool SetData(int pos, T &item);
//判断链表是否为空
bool IsEmpty() const;
//打印链表
void Print() const;
//链表排序
void Sort();
//链表逆置
void Reverse();
private:
LinkNode<T> *head;
};
#endif
源文件
#include "LinkList.h"
//复制构造函数
template<class T>
LinkList<T>::LinkList(LinkList<T>& L)
{
T value;
LinkNode<T>* srcptr = L.GetHead();
LinkNode<T>* destptr = head = new LinkNode<T>;
while(srcptr->next != NULL){
value = srcptr->next->data;
destptr->next = new LinkNode<T>(value);
srcptr = srcptr->next;
destptr = destptr->next;
}
destptr->next = NULL;
}
//将链表置为空表
template<class T>
void LinkList<T>::Clear()
{
LinkNode<T>* temp = NULL;
while(head->next != NULL){
temp = head->next;
head->next = temp->next;
delete temp;
}
}
//计算待附加头结点的单链表长度
template<class T>
int LinkList<T>::Length() const
{
int count = 0;
LinkNode<T>* temp = head->next;
while(temp != NULL){
temp = temp->next;
++count;
}
return count;
}
//在表中搜索数据item的节点,搜索成功则返回该结点地址，否则返回NULL
template<class T>
LinkNode<T>* LinkList<T>::Find(T &item)
{
LinkNode<T>* temp = head->next;
while(temp != NULL){
if(temp->data == item) break;
else temp = temp->next;
}
return temp;
}
// 返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL
template<class T>
LinkNode<T>* LinkList<T>::Locate(int pos)
{
int i = 0;
LinkNode<T> *p = head;
if (pos < 0)
return NULL;
while (NULL != p && i < pos)
{
p = p->next;
i++;
}
return p;
}
//取出链表中第i个元素的值
template<class T>
bool LinkList<T>::GetData(int pos,T &item)
{
if(pos<=0) return false;
LinkNode<T>* temp = Locate(pos);
if(temp == NULL) return false;
else{
item = temp->data;
return true;
}
}
//给链表中第i个元素的赋值
template<class T>
bool LinkList<T>::SetData(int pos,T &item)
{
if(pos<=0) return false;
LinkNode<T>* temp = Locate(pos);
if(temp == NULL) return false;
else{
temp->data = item;
return true;
}
}
//判断链表是否为空
template<class T>
bool LinkList<T>::IsEmpty() const
{
return (head->next == NULL)?true:false;
}
template<class T>
bool LinkList<T>::Insert(T &item, int pos)
{
LinkNode<T> *p = Locate(pos);
if (NULL == p)
return false;
LinkNode<T> *node = new LinkNode<T>(item);
if (NULL == node)
{
std::cerr << "分配内存失败!" << std::endl;
exit(1);
}
node->next = p->next;
p->next = node;
return true;
}
template<class T>
bool LinkList<T>::Remove(int pos, T &item)
{
LinkNode<T> *p = Locate(pos);
if (NULL == p || NULL == p->next)
return false;
LinkNode<T> *del = p->next;
p->next = del->next;
item = del->data;
delete del;
return true;
}
template<class T>
void LinkList<T>::Print() const
{
int count = 0;
LinkNode<T> *p = head;
while (NULL != p->next)
{
p = p->next;
std::cout << p->data <<std::endl;
}
}
template<class T>
void LinkList<T>::Reverse()
{
LinkNode<T> *pre = head->next;
LinkNode<T> *curr = pre->next;
LinkNode<T> *next = NULL;
head->next->next = NULL;
while (curr)
{
next = curr->next;
curr->next = pre;
pre = curr;
curr = next;
}
head->next = pre;
}
