数据描述2--单向链表

继续是《数据结构算法与应用：C++语言描述》第3章数据描述的笔记。本小节主要介绍链表，以及单向链表和单向循环链表，双向链表的介绍。

链表描述

类ChainNode和Node

链表描述中，数据对象实例的每个元素都放在单元或节点中进行描述，不过每个节点不必是一个数组元素，但都包含了与该节点相关的其他节点的位置信息，这种关于其他节点的位置信息被称为链(link)或指针(pointer)。

令$L=(e_1,e_2,\ldots,e_n)$是一个线性表，其链表描述如下图所示，每个节点都包含一个链接域，用以指向表中的下一个元素。所以节点$e_i$的指针将指向$e_{i+1}$，其中$1\le i \lt n$。节点$e_n$没有下一个节点，所以它的链接域是NULL(或0)。指针变量first指向描述中的第一个节点。

上图中每个节点都正好有一个链接域，所以该图的链表结构被称之为单向链表，此外，这种结构由于是每个节点的指针都指向下一个节点，然后最后一个节点的链接域是NULL，故也称为链(chain)。这里定义的Chain<T>是ChainNode<T>的一个友类，即Chain<T>可以访问ChainNode<T>的所有成员(尤其是私有成员)。其类定义如下：

#include<iostream>

// 必须先声明，否则友元模板类之间无法直接访问，会出现未定义的错误。
template<class T>
class Chain;


template<class T>
class ChainNode{
    friend Chain<T>;
private:
    T data;
    ChainNode<T> * link;
};

template<class T>
class Chain{
private:
    // 指向第一个节点的指针
    ChainNode<T> *first;
public:
    Chain(){ first = 0; }
    ~Chain();
    bool isEmpty() const{ return first == 0; }
    int Length() const;
    bool Find(int k, T& x)const;
    int Search(const T& x)const;
    Chain<T>& Delete(int k, T& x);
    Chain<T>& Insert(int k, const T&x);
    void Output(std::ostream& out)const;
};

操作

下面给出析构函数，Length,Find,Search,Output函数的代码实现，其中析构函数的复杂性是$\theta(n)$,n是链表的长度，而Length的复杂性是$\theta(n)$,Find的复杂性$O(k)$,函数Search的复杂性是$O(n)$,Output的复杂性是$\theta(n)$。

template<class T>
Chain<T>::~Chain(){
    // 删除链表中的所有节点
    ChainNode<T> *next;
    while (first){
        next = first->link;
        delete first;
        first = next;
    }
}

template<class T>
int Chain<T>::Length() const{
    // 返回链表中的元素总数
    ChainNode<T> *current = first;
    int len = 0;
    while (current){
        len++;
        current = current->link;
    }
    return len;
}

template<class T>
bool Chain<T>::Find(int k, T&x)const{
    // 寻找链表中的第k个元素，并将其传送者x
    if (k < 1)
        return false;
    ChainNode<T> *current = first;
    // current的索引
    int index = 1;  
    while (index < k && current){
        current = current->link;
        index++;
    }
    if (current){
        x = current->data;
        return true;
    }
    // 不存在第k个元素
    return false;
}

template<class T>
int Chain<T>::Search(const T& x)const{
    // 寻找x，如果发现x，则返回x的位置
    ChainNode<T> *current = first;
    // current的索引
    int index = 1;
    while (current && current->data != x){
        index++;
        current = current->link;
    }
    if (current)
        return index;
    return 0;
}

template<class T>
void Chain<T>::Output(std::ostream& out)const{
    //  将链表元素送至输出流
    ChainNode<T> *current;
    for (current = first; current; current = current->link){
        out << current->data << " ";
    }
}
// 重载 <<
template<class T>
std::ostream& operator<<(std::ostream& out, const Chain<T>& x){
    x.Output(out);
    return out;
}

删除操作

假如要从下图中删除第四个元素，需要进行如下操作：

1. 找到第三和第四个节点；
2. 使第三个节点指向第五个节点；
3. 释放第四个节点所占空间，以便于重用。
   
   代码实现如下：

   template<class T>
   Chain<T>& Chain<T>::Delete(int k, T&x){
       // 把第k个元素取至x，然后删除第k个元素
       if (k < 1 || !first)
           // 不存在第k个元素
           throw OutOfBounds();
       // p最终指向第k个节点
       ChainNode<T> *p = first;
       if (k == 1)
           // p已经指向第k个元素
           first = first->link;
       else{
           // q用于移动到第k-1个节点
           ChainNode<T>*q = first;
           for (int index = 1; index < k - 1 && q; index++)
               q = q->link;
           if (!q || !q->link)
               // 不存在第k个元素
               throw OutOfBounds();
           // 存在第k个元素
           p = q->link;
           // 让上一个节点指向待删除节点后面的节点
           q->link = p->link;
       }
       // 保存第k个元素的值，然后释放节点
       x = p->data;
       delete p;
       return *this;
   }

这里有三种情形要考虑，分别如下：

• k小于1或链表为空；
• 第一个元素将被删除且链表不为空；
• 从一个非空的链表中删除非首元素的元素。

程序中首先就处理第一种情形，即引发OutOfBounds异常。然后声明一个指针变量p用于最终指向第k个元素，对于第二种情形，语句first = first->link;就可以用来删除第一个元素；对于第三种情形，首先是定义了新的指针变量q，然后通过一个for循环让q定位到第k-1个元素，此时如果链表的节点数少于k-1，则q为0，也是引发OutOfBounds异常，否则就让p指向第k个元素，并保存其值，然后释放该节点。

插入操作

插入操作和删除操作很相似，要在链表第k个元素之后插入一个新的元素，需要首先找到第k个元素，然后在该节点后面插入新的节点。程序实现如下所示，其时间复杂性是$O(k)$。

template<class T>
Chain<T>& Chain<T>::Insert(int k, const T& x){
    // 在第k个元素后面插入x
    if (k < 0)
        throw OutOfBounds();
    ChainNode<T> *p = first;
    for (int index = 1; index < k && p; index++)
        p = p->link;
    if (k>0 && !p)
        // 不存在第k个元素
        throw OutOfBounds();
    ChainNode<T> *newNode = new ChainNode<T>;
    newNode->data = x;
    if (k){
        newNode->link = p->link;
        p->link = newNode;
    }
    else{
        // k=0,即作为第一个元素插入
        newNode->link = first;
        first = newNode;
    }
    return *this;
}

同样在插入操作中需要注意的是$k=0$和$k \neq 0$两种情形下的插入操作，前者是作为第一个元素插入，需要使用到指向第一个节点的指针first。

扩充类Chain

这里会在之前的抽象数据类型LinearList中的操作上增加一些新的方法，比如Erase（删除链表中的所有节点)、Zero(将first指针置为0，但并不删除任何节点)、Append(在链表的尾部添加一个元素)。
对于函数Erase，其等价于类的析构函数，实现如下所示：

// 删除链表中的所有节点
template<class T>
void Chain<T>::Erase(){
    ChainNode<T> *next;
    while (first){
        next = first->link;
        delete first;
        first = next;
    }
}

而函数Zero则可以定义为如下的内联函数：

void Zero() { first = 0; }

对于函数Append，为了在$\theta(1)$的时间内添加一个元素，需要在类中添加一个新的类型是ChainNode<T> *的私有成员last来跟踪链表的最后一个元素。同时需要在插入和删除操作中各自添加一条语句，即在Delete函数中的语句

// 存在第k个元素
p = q->link;

后面增加下列语句

// 如果刚好是第k个节点是最后一个节点
if (p == last)
    last = q;

在Insert操作中的语句

return *this;

前面添加下面的语句

// 如果新插入的节点是最后一个节点
if (!newNode->link)
    last = y;

最后，Append函数的代码实现如下：

// 在链表末尾右端添加一个元素
template<class T>
Chain<T>& Chain<T>::Append(const T&x){
    ChainNode<T> *newNode;
    newNode = new ChainNode<T>;
    newNode->data = x;
    newNode->link = 0;
    if (first){
        // 链表非空
        last->link = newNode;
        last = newNode;
    }
    else{
        first = last = newNode;
    }
    return *this;
}

这里需要判断链表是否为空的问题，如果是空，则令first = last = newNode;

链表遍历器类

这里使用一个链表遍历器，遍历器的功能是记录当前位置并每次向前移动一个位置。在如下实现的遍历器程序中，有两个共享成员Initialize和Next。
Initialize返回一个指针，其指向第一个链表节点中包含的数据，同时把私有变量location设置为指向链表的第一个节点，该变量用来跟踪我们在链表中所处的位置。而成员Next用来调整location，使其指向链表中的下一个节点，并返回指向该节点数据域的指针。由于遍历器类访问了Chain类的私有成员，所以应把它定义为Chain的友类(实际上应该还需要定义为ChainNode的友类，因为也是访问了其私有成员data)。

// 链表遍历器类
template<class T>
class ChainIterator{
private:
    ChainNode<T> *location;
public:
    T* Initialize(const Chain<T>& c){
        location = c.first;
        if (location)
            return &location->data;
        return 0;
    }
    T* Next(){
        if (!location)
            // 链表为空
            return 0;
        location = location->link;
        if (location)
            return &location->data;
        return 0;

    }
};

其使用例子如下,此时Output函数不是Chain类的成员函数。

template<class T>
void Output(const Chain<T>& X){
    int *x;
    ChainIterator<T> c;
    x = c.Initialize(X);
    while (x){
        cout << *x << ' ';
        x = c.Next();
    }
    cout << endl;
}

使用遍历器可以实现在线性时间内输出链表，如上述程序所示。

更完整的例子可以查看ChainList。

循环链表

我们可以采纳下面一条或两条措施使得链表的应用代码可以更加简洁和高效：

1. 把线性表描述成一个单向循环链表，或简称循环链表；
2. 在链表的前部增加一个附加的节点，称之为头节点。

通过把单向链表最后一个节点的链接指针改为指向第一个节点，就可以把一个单向链表改造成循环链表，如下图(a)所示，而图(b)给出了一个带有头指针的非空的循环链表，图(c)给出了一个带有头指针的空的循环链表。

CircularList类的定义与Chain类定义相似。尽管链表搜索的复杂性仍然保持为$O(n)$，但代码本身要稍微简单一些，如下所示，程序在for循环的每次循环中执行的比较次数较少，因此会比Chain类中的搜索运行得更快一些。

template<class T>
int CircularList<T>::Search(const T& x)const{
    // 在带有头节点的循环链表中查找x
    ChainNode<T>* current = first->link;
    int index = 1;
    first->data = x;    // 把x放入头节点
    while (current->data != x){
        current = current->link;
        index++;
    }
    // 判断是否是链表头节点
    return ((current == first) ? 0 : index);
}

更完整的CircularList可以查看我的github

与公式化描述方法的比较

使用公式化描述方法的线性表仅需要能够保持所有元素的空间以及保存表长的空间，而链表和循环链表描述还需要额外的空间，用来保存链接指针。采用链表描述所实现的插入和删除操作要比公式化描述时执行得更快，当每个元素都很长时(字节数多)，尤其如此。

还可以使用链接模式来描述很多表，这样做不会降低空间利用率，也不会降低执行效率；而对于公式化描述，为了提高空间利用率，不得不把所有的表都放在一个数组中，并使用了另外两个数组来对这个数组进行索引，更有甚者，与一个表对应一个数组的情形相比，插入和删除操作变得更加复杂，而且存在一个很显著的最坏运行时间。
采用公式化描述，可以在$\theta(1)$的时间内访问第k个元素，而这种操作在链表中是需要$O(k)$。

双向链表

双向链表就是每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针。

下图是一个双向链表表示。

双向链表的类定义如下所示：

template<class T>
class DoubleNode{
    T data;
    DoubleNode<T>*left, *right;
};

template<class T>
class DoubleChainList{
private:
    DoubleNode<T>* LeftEnd, *RightEnd;
public:
    DoubleChainList(){ LeftEnd = RightEnd = 0 };
    ~DoubleChainList();
    int Length() const;
    bool Find(int k, T& x)const;
    int Search(const T& x)const;
    DoubleChainList<T>& Delete(int k, T& x);
    DoubleChainList<T>& Insert(int k, const T& x);
    void Output(std::ostream & out)const;
};

此外在双向链表的左部和/或右部添加头节点，并且把链表变成循环的链表，可以提高双向链表的性能。在一个非空的双向链表中，LeftEnd->left是一个指向最右边结点的指针(即RightEnd),RightEnd->right是一个指向最左边节点的指针，这样可以省去RightEnd，只需要简单地使用变量LeftEnd来跟踪链表。