数据描述1--线性表

《数据结构算法与应用：C++语言描述》第3章数据描述的笔记。

本章的重点是介绍线性表，但一个主要目标是让大家明白—数据可以用不同的形式进行描述或存储在计算机存储器中。最常见的数据描述方法有：公式化描述、链接描述、间接寻址和模拟指针。

公式化描述

公式化描述借助数学公式来确定元素表中的每个元素分别存储在何处(如存储器地址)。最简单的情形就是把所有元素依次连续存储在一片连续的存储空间中，这就是通常 所说的连续线性表。

链接描述

链接描述中，元素表中的每个元素可以存储在存储器的不同区域汇总，每个元素都包含指向下一个元素的指针。

间接寻址

间接寻址中，元素表的每个元素也是可以存储在存储器的不同区域中，但与链接描述不同的是，此时必须保存一张表，该表的第i项指向元素表中的第i个元素，所以这张表是一个用来保存元素地址的表。

模拟指针

模拟指针非常类似于链接描述，区别在于它用整数代替了C++指针，整数所扮演的角色与指针所扮演的角色完全相同。

数据对象是一组实例或值，比如布尔值，整数，浮点数，字符串等。数据结构包括数据对象和实例以及构成实例的每个元素之间所存在的各种关系，这些关系可由相关的函数来实现。

线性表简介

定义：线性表示这样的数据对象，其实例形式为：$(e_1,e_2,\ldots,e_n)$,其中n是有穷自然数。

当n=0时，表为空；当$n\gt 0$,$e_1$是第一个元素，$e_n$是最后一个元素，可以认为$e_1$优先于$e_2$,$e_2$优先于$e_3$,如此等等。除了这种优先关系外，在线性表中不再有其他的结构。我们可用s来表示每个元素$e_i$所需要的字节数，即s是一个元素的大小。

以下是一些线性表的例子：

• 一个班级学生姓名按字母顺序排列的列表；
• 按递增次序排列的考试分数表；
• 按字母依次排列的会议列表。

根据这些例子可以知道对于线性表有必要执行下列操作：

• 创建一个线性表；
• 确定线性表是否为空；
• 确定线性表的长度；
• 查找第k个元素；
• 查找指定的元素；
• 删除第k个元素；
• 在第k个元素之后插入一个新的元素。

下面用一个抽象数据类型(abstract data type, ADT)来说明线性表，它给出了实例以及相关操作的描述。

抽象数据类型 LinearList {
实例
	0或多个元素的有序集合
操作
	Create(): 创建一个空线性表
	Destroy(): 删除表
	IsEmpty(): 如果表为空则返回true，否则返回false
	Length(): 返回表的大小 (即表中元素个数)
	Find(k,x): 寻找表中第k 个元素，并把它保存到 x 中；如果不存在，则返回false
	Search(x): 返回元素x在表中的位置；如果x 不在表中，则返回0
	Delete(k,x): 删除表中第k个元素，并把它保存到 x 中；函数返回修改后的线性表
	Insert(k,x): 在第k个元素之后插入x；函数返回修改后的线性表
	Output(out): 把线性表放入输出流 out 之中
}

公式化描述

基本描述

公式化描述采用数组来表示一个对象的实例，数组中的每个位置被称之为单元(cell)或节点(node)，每个数组单元应该足够大，以便能够容纳数据对象实例中的任意一个元素。

实例中每个元素在数组中的位置可以用一个数学公式来指明，一个简单的映射公式如下：

location(i) = i - 1

上述公式指明表中第i个元素(如果存在)位于数组中i-1位置处。

下面的程序给出了相应的C++类定义。由于表元素的数据类型随着应用的变化而变化，所以定义了一个模板类，在该模板类中，用户指定元素的数据类型是T。

#ifndef LINEARLIST_H_
#define LINEARLIST_H_
#include<iostream>

template<class T>
class LinearList
{
private:
    int MaxSize;
    T *element;
    int length;     // 当前线性表的长度
public:
    LinearList(int MaxListSize = 10);
    ~LinearList(){ delete[] element; }
    bool isEmpty() const{ return length == 0; }
    int Length() const { return length; }
    // 返回第k个元素至x中
    bool Find(int k, T&x)const;
    // 返回x所在的位置
    int Search(const T& x) const;
    // 删除第k个元素并将它返回至x中
    LinearList<T>& Delete(int k, T&x);
    // 在第k个元素之后插入x
    LinearList<T>& Insert(int k, const T& x);
    void Output(std::ostream &out) const;
};

#endif

异常类NoMem

如果分配内存失败，那么我们希望可以引发一个异常，有时，异常可能由new引起，有时则需要我们自己来引发。而我们希望在所有情形下都能引发同一个异常，因此，定义了一个异常类NoMem,如下面程序所示。

#include<iostream>

// 内存不足
class NoMem{
public:
    NoMem(){}
};

// 使new引发NoMem异常而不是xalloc异常
void my_new_handler(){
    throw NoMem();
}

new_handler Old_Handler_ = std::set_new_handler(my_new_handler);

在上述程序中，函数my_new_handler简单地引发了一个类型为NoMem的异常，然后在程序最后一行调用了C++函数set_new_handler，每当分配内存失败时，该函数就让操作符new调用函数my_new_handler，所以new引发的异常是NoMem而不是xalloc。每当分配内存失败时，set_new_handler将返回一个指针，指向由new此前所调用的那个函数，该指针保存在变量Old_Handler_中。为了恢复new的元素行为，可以如此调用:set_new_handler(Old_Handler_);

操作

在抽象数据类型中的操作Create和Destroy分别被作为类的构造函数和析构函数加以实现。基本操作实现的程序如下所示：

#include"LinearList.h"

template<class T>
LinearList<T>::LinearList(int MaxListSize){
    MaxSize = MaxListSize;
    element = new T[MaxSize];
    length = 0;
}

// 返回第k个元素至x中
template<class T>
bool LinearList<T>::Find(int k, T&x)const{
    if (k <1 || k>length)
        return false;
    x = element[k - 1];
    return true;
}

// 返回x所在的位置
template<class T>
int LinearList<T>::Search(const T& x)const{
    for (int i = 0; i < length; i++){
        if (element[i] == x)
            return ++i;
    }
    return 0;
}

由上述程序可知，函数IsEmpty,Length,Find三个函数的复杂性是$\theta(1)$,而Search的复杂性是$O(length)$。

删除元素

程序如下所示

// 删除第k个元素并将它返回至x中
template<class T>
LinearList<T>& LinearList<T>::Delete(int k, T&x){
    // 如果不存在第k个元素，则引发异常OutOfBounds
    if (Find(k, x)){
        // 将第k个元素后的元素向前移动一个位置
        for (int i = k; i < length; i++)
            element[i - 1] = element[i];
        length--;
        return *this;
    }
    else
        throw OutOfBounds();
}

该函数首先要判断表中是否存在第k个元素，然后再删除元素。如果不存在，则出现一个异常，这里是引发一个类型为OutOfBounds的异常。每当正在执行的函数中任一参数超出所期望的范围时，就引发这种类型的异常。
如果存在第k个元素，则可以将元素$k+1，k+2，…,length$依次向前移动一个位置，并将length减一，从而删除第k个元素。
Delete函数在不存在第k个元素时，所需要的时间是$\theta(1)$;如果存在，则需要移动length-k个元素，需要耗时$\theta((length-k)s)$,其中s是每个元素的大小。此外，被删除的元素被移动至x，因此，总的时间复杂性是$O((length-k)s)$。

插入操作

程序如下：

 // 在第k个元素之后插入x
template<class T>
LinearList<T>& LinearList<T>::Insert(int k, const T&x){
    // 如果不存在第k个元素，则引发异常OutOfBounds
    if (k<0 || k>lenth)
        throw OutOfBounds();
    // 如果表已满，则引发异常NoMem
    if (length == MaxSize)
        throw NoMem();
    // 向后移动一个位置
    for (int i = length - 1; i >= k; i--)
        element[i + 1] = element[i];
    element[k] = x;
    length++;
    return *this;
}

为了在第k个元素之后插入一个元素，首先需要把第k+1至length元素向后移动一个位置，然后将新元素插入到k+1位置处。

Insert函数的时间复杂性是$O((length-k)s)$。

测试

下面程序是用来测试类LinearList的例子，其中头文件llist.h包含了类声明以及定义，xcept.h则是异常类的定义。

#include<iostream>
#include"llist.h"
#include"xcept.h"


int main(){
    using std::cout;
    using std::endl;
    using std::cin;

    try{
        LinearList<int> L(5);
        cout << "Length = " << L.Length() << endl;
        cout << "IsEmpty = " << L.isEmpty() << endl;
        L.Insert(0, 2).Insert(1, 6);
        cout << "List is " << L << endl;
        int z;
        L.Find(1, z);
        cout << "First element is " << z << endl;
        cout << "Length = " << L.Length() << endl;
        L.Delete(1, z);
        cout << "Deleted element is " << z << endl;
        cout << "List is " << L << endl;
    }
    catch (...){
        std::cerr << "An exception has occured" << endl;
    }

    system("pause");
    return 0;
}

输出结果如下所示：

完整的例子放在了我的Github中—LinearList

小结

​ 对这种公式化描述方法，首先是分析这种方法的优缺点，首先这种方法的确是可以用非常简单的C++函数来实现各种操作，执行查找、删除和插入的函数都有一个最差的、与表大小呈线性关系的时间复杂性。但一个缺点是空间的低效利用。

​ 因此其实可以对原来的类LinearList做出一点修改，增加一个可以调整数组大小的函数Resize，在初始创建线性表时，置MaxSize =1;然后，执行插入操作期间，当线性表的元素个数等于MaxSize,就调用Resize函数，增加两倍的容量；在删除操作期间，当元素个数减少到容量的1/4时，就调用Resize函数，将容量减少到当前的1/2。
具体实现的操作如下所示:

template<class T>
bool ResizeLinearList<T>::Resize(int resizeCount){
    // 新数组的大小必须大于现有的数组元素个数
    if (resizeCount <= length){
        std::cerr << "should give a larger numbers than current array numbers\n";
        return false;
    }
    // 更新数组的容量
    MaxSize = resizeCount;
    T * newElement = new T[resizeCount];
    for (int i = 0; i < length; i++)
        newElement[i] = element[i];
    delete[] element;
    element = newElement;
    return true;
}
// 删除第k个元素并将它返回至x中
template<class T>
ResizeLinearList<T>& ResizeLinearList<T>::Delete(int k, T&x){
    // 如果不存在第k个元素，则引发异常OutOfBounds
    if (Find(k, x)){
        // 将第k个元素后的元素向前移动一个位置
        for (int i = k; i < length; i++)
            element[i - 1] = element[i];
        length--;
        // 如果当前元素数量等于1/4的容量，则将最大容量缩小一半
        if (length == (int)MaxSize * 0.25)
            Resize((int)0.5 * MaxSize);
        return *this;
    }
    else
        throw OutOfBounds();
}

// 在第k个元素之后插入x
template<class T>
ResizeLinearList<T>& ResizeLinearList<T>::Insert(int k, const T&x){
    // 如果不存在第k个元素，则引发异常OutOfBounds
    if (k<0 || k>length)
        throw OutOfBounds();
    // 如果表已满，则增加2倍容量
    if (length == MaxSize)
        Resize(2*MaxSize);
    // 向后移动一个位置
    for (int i = length - 1; i >= k; i--)
        element[i + 1] = element[i];
    element[k] = x;
    length++;
    return *this;
}

完整的例子在ResizeLinearList