链表类的实现

定义链表的类的声明时采用模版机制，这样虽然繁琐一些，但为将来对链表的复用提供了很大的方便。同时在链表中增加头结点，统一了空表和非空表操作的实现，降低了程序结构的复杂性，减少了出错的概率。

头文件

#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;
}