hslinkedlist.h

回顾基础

//带头结点的单链表类

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

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

    HSLinkedList();                              //构造空单链表
    HSLinkedList(T value[], int n);              //构造由指定数组提供元素的单链表
    ~HSLinkedList();                             //析构
 
    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, HSLinkedList<T> &list);    //输出单链表所有元素

    friend ostream& operator<<(ostream& out, HSLinkedList<T> &list);    //输出单链表所有元素
    Node<T>* insert(int i, T x);                 //插入x作为第i个结点，返回新插入结点指针
    bool remove(int i, T& old);                  //删除第i个结点，被删除元素存放在old变量中
    void clear();                                //清空单链表

    //第9章 排序
    void selectSort();                           //单链表的直接选择排序

};

template <class T>
HSLinkedList<T>::HSLinkedList()                  //构造空单链表
{
    this->head = new Node<T>();                  //创建头结点，数据域未初始化
}

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

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

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

template <class T>
int HSLinkedList<T>::length()                    //返回单链表长度
{                                                //单链表遍历算法，O(n)
    int i=0;
    Node<T> *p=head->next;                       //p指向第一个结点
    while (p!=NULL)
    {
        i++;
        p = p->next;
    }
    return i;
}

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

    int j=0;
    Node<T> *p=head->next;
    while (p!=NULL && j<i)
    {
        j++;
        p = p->next;
    }
    return p;                                    //p指向第i个结点，若单链表空或序号错误，则p==NULL
}

template <class T>
T HSLinkedList<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 HSLinkedList<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, HSLinkedList<T> &list)    //输出单链表所有元素
{
    Node<T> *p = list.head->next;
    out<<"(";
    while (p!=NULL)
    {
        out<<p->data;
        p = p->next;
        if (p!=NULL)
            out<<", ";
    }
    out<<")\n";
    return out;
}

template <class T>
Node<T>* HSLinkedList<T>::insert(int i, T x)     //插入x作为第i个结点，返回新插入结点指针
{
    int j=0; 
    Node<T> *p=head;
    while (p->next!=NULL && j<i)                 //寻找插入位置
    {
        j++;
        p = p->next;
    }
    Node<T> *q = new Node<T>(x, p->next);        //插入x作为p结点的后继结点
    p->next = q;
    return q;
}

template <class T>
bool HSLinkedList<T>::remove(int i, T& old)      //删除第i个结点，被删除元素存放在old变量中
{
    int j=0;
    Node<T> *front=head;
    while (front->next!=NULL && j<i)             //定位到待删除结点的前驱结点
    {
        j++;
        front = front->next;
    }
    if (front->next!=NULL)
    {
        Node<T> *q=front->next;                  //q结点为front结点的后继结点
        old = q->data;
        front->next = q->next;                   //删除front的后继结点q
        delete q;
        return true;
    }
    return false;
}

template <class T>
void HSLinkedList<T>::clear()                    //清空单链表，O(n)
{
    Node<T> *p=head->next;                       //p指向第一个结点
    while (p!=NULL)
    {
        Node<T> *q = p;
        p = p->next;                             //到达p的后继结点
        delete q;                                //释放q结点所占用的存储单元
    }
    head->next = NULL;                           //设置单链表为空
}

//以上是第2章内容，实现线性表ADT

//【例9.2】  单链表的直接选择排序。

template <class T>
void HSLinkedList<T>::selectSort()               //单链表的直接选择排序
{
    Node<T> *shead=NULL, *srear=NULL;            //已排序单链表的头指针、尾指针
    while (head->next!=NULL)                     //非空单链表
    {
        Node<T> *min=head->next;                 //min指向最小值结点
        Node<T> *mfront=head;                    //mfront是min的前驱结点
        if (min->next!=NULL)
        {
            Node<T> *pfront=min, *p=min->next;   //pfront是p的前驱结点
            while (p!=NULL)
            {   
                if (p->data < min->data)
                {
                    mfront = pfront;
                    min = p;
                }
                pfront = p;
                p = p->next;
            }  
        }
        mfront->next = min->next;                //从head链表中删除min结点
        min->next=NULL;
        if (shead==NULL)                         //在已排序单链表中插入min结点
            shead = min;                         //头插入
        else
            srear->next = min;                   //尾插入
        srear = min;
    }
    head->next = shead;                          //头结点指向已排序单链表
}


/*
下列算法不完善。

template <class T>
void HSLinkedList<T>::insert(int i, T x)         //插入x作为第i个结点
{
    Node<T>* p=getNode(i-1);                     //p指向待删除结点的前驱结点
    if (p!=NULL)
        p->next = new Node<T>(x, p->next);       //插入x作为p结点的后继结点
}
    错误：不能插入为第一个结点。当i=0时，getNode(i-1)返回NULL，则无法插入。
    该算法没有序号容错功能，当i<0或i>length()+1时，getNode(i-1)返回NULL，则无法插入。


template <class T>
bool HSLinkedList<T>::remove(int i, T& old)      //删除第i个结点，被删除元素存放在old变量中
{
    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;
}
*/