singlylinkedlist.h

回顾基础

//单链表类
#include <iostream.h>
#include "Node.h"                                //单链表结点类

template <class T>
class SinglyLinkedList                           //单链表类
{
  public:
    Node<T> *head;                               //单链表的头指针

    SinglyLinkedList();                          //构造空单链表
    SinglyLinkedList(T value[], int n);          //构造由指定数组提供元素的单链表
    ~SinglyLinkedList();                         //析构
 
    bool isEmpty();                              //判断单链表是否为空
    int length();                                //返回单链表长度 
    Node<T>* getNode(int i);                     //返回第i（i≥0）个结点指针
    T get(int i);                                //返回第i个元素
    bool set(int i, T x);                        //设置第i个元素为x
    friend ostream& operator<<(ostream& out, SinglyLinkedList<T> &list);    //输出单链表所有元素
    Node<T>* insert(int i, T x);                 //插入x作为第i个结点，返回新插入结点指针
    bool remove(int i, T& old);                  //删除第i个结点，被删除元素存放在old变量中
    void clear();                                //清空单链表

    void insert(T x);                            //在单链表最后插入x元素
    void concat(SinglyLinkedList<T> &list);      //将list链接在当前单链表之后

    //第2章习题
    SinglyLinkedList(SinglyLinkedList<T> &list); //以单链表list构造新的单链表，复制单链表
    bool equals(SinglyLinkedList<T> &list);      //比较两条单链表是否相等

    //第8章 8.2.1 顺序查找
    Node<T>* search(T value, Node<T>* start);    //从单链表start结点开始顺序查找指定元素
    Node<T>* search(T value);                    //顺序查找指定元素
    bool contain(T value);                       //判断单链表是否包含指定元素
    bool remove(T value);                        //移去指定元素首次出现结点

  private:
    int lengthFrom(Node<T>*p);                   //返回从p结点开始的单链表长度
    void printFrom(Node<T>*p);                   //输出从p结点开始的单链表
    Node<T>* create(T value[], int n, int i);    //由指定数组构造单链表
    Node<T>* copy(Node<T> *p);                   //复制单链表
    bool equals(Node<T> *p, Node<T> *q);         //比较两条单链表是否相等

};

template <class T>
SinglyLinkedList<T>::SinglyLinkedList()          //构造空单链表
{
    this->head = NULL;
}

template <class T>
SinglyLinkedList<T>::SinglyLinkedList(T value[], int n)    //构造由指定数组提供元素的单链表
{
    head = NULL;                                           //n=0时，构造空链表
    if (n>0)                                               //构造非空链表    
    {
        head = new Node<T>(value[0]);
        Node<T> *rear = head;                              //rear指向单链表最后一个结点
        int i=1;
        while (i<n)  
        {
            rear->next = new Node<T>(value[i++]);          //创建结点链入rear结点之后
            rear = rear->next;                             //rear指向新的链尾结点
        }
    }
}

template <class T>
SinglyLinkedList<T>::~SinglyLinkedList()         //析构函数
{
//    cout<<"析构~SinglyLinkedList\n";
    clear();                                     //清空单链表
}

template <class T>
bool SinglyLinkedList<T>::isEmpty()              //判断单链表是否为空
{
    return head==NULL;
}

template <class T>
int SinglyLinkedList<T>::length()                //返回单链表长度
{                                                //单链表遍历算法，O(n)
    int i=0;
    Node<T> *p=head;                             //p从head指向的结点开始
    while (p!=NULL)                              //若单链表未结束
    {
        i++;
        p = p->next;                             //p到达后继结点
    }
    return i;
}

template <class T>
Node<T>* SinglyLinkedList<T>::getNode(int i)     //返回第i（i≥0）个结点指针
{                                                //若单链表空或序号错误返回NULL，O(n)
    if (i<0)
        return NULL;

    int j=0;
    Node<T> *p=head;
    while (p!=NULL && j<i)
    {
        j++;
        p = p->next;
    }
    return p;                                    //p指向第i个结点，若head==NULL，则p==NULL
}

template <class T>
T SinglyLinkedList<T>::get(int i)                //返回第i个元素
{                                                //若单链表空或i指定元素序号无效则抛出异常
    Node<T>* p = getNode(i);                     //p指向第i个结点
    if (p!=NULL)
        return p->data;
    throw "单链表空或参数i指定元素序号无效";
}

template <class T>
bool SinglyLinkedList<T>::set(int i, T x)        //设置第i个元素为x，O(n)
{
    Node<T>* p=getNode(i);                       //p指向第i个结点
    if (p!=NULL)
    {
        p->data = x;
        return true;
    }
    return false;
}

template <class T>
ostream& operator<<(ostream& out, SinglyLinkedList<T> &list)    //输出单链表所有元素
{
    Node<T> *p = list.head;                      //p从head指向的结点开始
    out<<"(";
    while (p!=NULL)                              //若单链表未结束
    {
        out<<p->data;                            //访问p结点
        p = p->next;                             //p到达后继结点
        if (p!=NULL)
            out<<", ";
    }
    out<<")\n";
    return out;
}

template <class T>
Node<T>* SinglyLinkedList<T>::insert(int i, T x) //插入x作为第i个结点，返回新插入结点指针
{
    Node<T> *q=NULL;
    if (head==NULL || i<=0)                      //头插入
    {
        q = new Node<T>(x, head);
        head = q;
    }
    else                                         //单链表不空且i>=1
    {
        int j=0; 
        Node<T> *p=head;
        while (p->next!=NULL && j<i-1)           //寻找插入位置
        {
            j++;
            p = p->next;
        }                                        //循环停止时，p指向第i-1个结点或链表最后一个结点
        q = new Node<T>(x, p->next);             //插入x作为p结点的后继结点
        p->next = q;
    }
    return q;
}

template <class T>
bool SinglyLinkedList<T>::remove(int i, T& old)  //删除第i个结点，被删除元素存放在old变量中
{
    if (head!=NULL && i>=0)
        if (i==0)                                //头删除
        {
            Node<T> *q=head;
            old = q->data;
            head = head->next;
            delete q;                            //释放结点占用的存储单元
            return true;
        }
        else                                     //中间/尾删除
        {
            Node<T>* p=getNode(i-1);             //p指向待删除结点的前驱结点
            if (p!=NULL && p->next!=NULL)
            {
                Node<T> *q=p->next;              //q结点为p结点的后继结点
                old = q->data;
                p->next = q->next;               //删除p的后继结点q
                delete q;
                return true;
            }
        }
    return false;
}

template <class T>
void SinglyLinkedList<T>::clear()                //清空单链表，O(n)
{
    Node<T> *p=head;
    while (p!=NULL)
    {
        Node<T> *q = p;
        p = p->next;                             //到达p的后继结点
        delete q;                                //释放q结点所占用的存储单元
    }
    head = NULL;                                 //设置单链表为空，否则运行错
}
//以上是第2章SinglyLinkedList类内容

//可行，效率较低，不必要
template <class T>
void SinglyLinkedList<T>::insert(T x)            //在单链表最后插入x元素
{
    insert(this->length(), x);                   //需两次遍历单链表，效率较低
}

//【例2.3】  将两条单链表首尾相接合并成一条单链表。
template <class T>
void SinglyLinkedList<T>::concat(SinglyLinkedList<T> &list)   //将list链接在当前单链表之后
{
    if (this->head==NULL)
        this->head = list.head;
    else
    {
        Node<T> *p=head;
        while (p->next!=NULL)                    //找到最后一个结点
            p = p->next;
        p->next = list.head;                     //连接两条单链表
    }
    list.head = NULL;                            //设置单链表为空，否则运行错
}
/*
不能，相当于两条链表合并，有问题
template <class T>
SinglyLinkedList<T>::SinglyLinkedList(Node<T> *head)       //构造指定头指针的单链表
{
    this->head = head;
}
*/

//以下是第2章习题

template <class T>
SinglyLinkedList<T>::SinglyLinkedList(SinglyLinkedList<T> &list)   //以单链表list构造新的单链表，复制单链表
{
    this->head = NULL;
    if (list.head!=NULL)                         //构造非空链表    
    {
        this->head = new Node<T>(list.head->data);
        Node<T> *p=list.head->next;
        Node<T> *rear = this->head;              //rear指向单链表最后一个结点