C++实现链表

包括了添加删除访问查找反转（递归和非递归）等一系列操作。

#include<iostream>
using namespace std;

template<class Type> class List;

template<class Type> class ListNode{
friend class List<Type>;
    Type data;  //结点数据
    ListNode<Type> *link;   //结点链接指针
public:
    ListNode(); //链表结点构造函数
    ListNode(const Type &item);
    //给出当前结点的下一结点地址
    ListNode<Type> *NextNode(){
        return link;
    }
    //在当前结点后插入结点p
    void InsertAfter(ListNode<Type> *p);
    //摘下当前结点的下一结点
    ListNode<Type> *RemoveAfter();

};

template<class Type> class List{
    ListNode<Type> *first, *last;
public:
    //创建数据为item，指针为next的新结点
    ListNode<Type> *GetNode(const Type &item, ListNode<Type> *next);
    //构造函数
    List(){
        last = first = new ListNode<Type>();
    }
    List(const Type &value){
        last = first = new ListNode<Type>(value);
    }
    ~List();    //析构函数
    void MakeEmpty();   //链表置空
    int Length() const;     //求链表长度
    ListNode<Type> *Find(Type value);
    ListNode<Type> *Find(int i);
    int Insert(Type value, int i);
    bool Remove(int i);
    Type *Get(int i);
    Type Get_Min();
    void Reverse();
    void Reverse(ListNode<Type> *head);
};

template<class Type>
ListNode<Type>:: ListNode(): link(NULL){}

template<class Type>
ListNode<Type>:: ListNode(const Type &item): data(item), link(NULL){}

template<class Type>
void ListNode<Type>:: InsertAfter(ListNode<Type> *p){
    p->link = link;
    link = p;
}

//摘下当前结点的下一结点
template<class Type>
ListNode<Type> *ListNode<Type>:: RemoveAfter(){
    ListNode<Type> *tempptr = link;
    if(link == NULL) return NULL;   //没有下一结点则返回空指针
    link = tempptr->link;   //重新链接
    return tempptr;     //返回下一结点地址
}

template<class Type>
ListNode<Type> *List<Type>:: GetNode(const Type &item, ListNode<Type> *next = NULL){
    ListNode<Type> *newnode = new ListNode<Type>(item);
    newnode->link = next;
    return newnode;
}

//析构函数 (链表的公共操作)
template<class Type>
List<Type>:: ~List(){
    //链表置空，再删去表头结点
    MakeEmpty();
    delete first;
}

//删去链表中除表头结点外的所有其他结点
template<class Type>
void List<Type>:: MakeEmpty(){
    ListNode<Type> *q;
    while(first->link != NULL){
        //将表头结点后第一个结点从链中摘下
        q = first->link;
        first->link = q->link;
        delete q;   //释放它
    }
    last = first;   //修改表尾指针
}

//求单链表的长度
template<class Type>
int List<Type>:: Length()const{
    ListNode<Type> *p = first->link;    //检测指针p指示第一个结点
    int count = 0;
    while(p != NULL){
        p = p->link;
        count++;
    }
    return count;
}

//在链表中从头搜索其数据值为value的结点
template<class Type>
ListNode<Type> *List<Type>:: Find(Type value){
    ListNode<Type> *p = first->link;
    while(p != NULL && p->data != value)
        p = p->link;
    return p;
}

//在链表中从头搜索第 i 个结点，不计头结点
template<class Type>
ListNode<Type> *List<Type>:: Find(int i){
    if(i < -1) return NULL;
    if(i == -1) return first;
    ListNode<Type> *p = first->link;
    int j = 0;
    while(p!=NULL && j<i){
        p = p->link;
        j++;
    }
    return p;
}

//将含value的新元素插入到链表第 i 个位置
template<class Type>
int List<Type>:: Insert(Type value, int i){
    // p 指向链表第 i-1个结点
    ListNode<Type> *p = Find(i-1);
    if(p == NULL) return 0;
    ListNode<Type> *newnode = GetNode(value, p->link);//创建结点
    if(p->link == NULL) last = newnode;
    p->link = newnode;  //重新链接
    return 1;
}

//从链表中删去第 i 个结点，返回能否成功删除
template<class Type>
bool List<Type>:: Remove(int i){
    ListNode<Type> *p = Find(i-1), *q;
    if(p==NULL || p->link==NULL)
        return 0;
    q = p->link;
    p->link = q->link;
    if(q == last) last = p;
    delete q;
    return 1;
}

//提取第 i 个结点的数据
template<class Type>
Type *List<Type>:: Get(int i){
    // p 指向链表第 i 个结点
    ListNode<Type> *p = Find(i);
    if(p==NULL || p==first)
        return NULL;
    else return &(p->data);
}

//返回链表中最小的元素
template<class Type>
Type List<Type>:: Get_Min(){
    ListNode<Type> *p = first->link;
    Type ans = p->data;
    while(p->link != NULL){
        p = p->link;
        ans = min(ans, p->data);
    }
    return ans;
}

//反转链表（非递归）
template<class Type>
void List<Type>:: Reverse(){
    ListNode<Type> *current = first->link;
    ListNode<Type> *next = current->link;
    ListNode<Type> *previous = NULL;

    while(current!=NULL){
        next = current->link;
        current->link = previous;
        previous = current;
        current = next;
        if(next != NULL)
            next = next->link;
    }
    first->link = previous;
}

//反转链表（递归）
template<class Type>
void List<Type>:: Reverse(ListNode<Type> *p){
    if(p->link == NULL){
        first->link = p;
        return;
    }
    Reverse(p->link);
    p->link->link = p;
    p->link = NULL;
}


int main(){
    List<double> a;
    double d = 20.0;
    a.Insert(2, 0);
    a.Insert(d, 0);
    a.Insert(d+1, 1);
    a.Insert(d+2, 2);
    a.Insert(d+3, 3);
    for(int i = 0; i < a.Length(); i++)
        cout << *a.Get(i) << endl;
    a.Reverse(); //非递归
    cout << "After reverse:" << endl;
    for(int i = 0; i < a.Length(); i++)
        cout << *a.Get(i) << endl;

    cout << "After reverse(Recursion):" << endl;
    a.Reverse(a.Find(0));  //递归
    for(int i = 0; i < a.Length(); i++)
        cout << *a.Get(i) << endl;



    cout << "min: " << a.Get_Min() << endl;
    cout << a.Length() << endl;
    a.Remove(1);
    cout << a.Length() << endl;
    return 0;
}