数据结构——线性表

线性表

线性结构的特点是：在数据元素的非空有限集中，(1)存在唯一的一个被称做“第一个”的数据元素；(2)存在唯一的一个被称做“最后一个”的数据元素；(3)除第一个之外，集合中的每个数据元素均只有一个前驱；(4)除最后一个之外，集合中每个数据元素均只有一个后继。

一、线性表的基本概念

（一）线性表的定义

线性表是由n个具有相同数据类型的数据元素组成的有限序列。其中n>=0，n为表长，当n为0时线性表是一个空表，若用L命名线性表，则其一般表示为：

L=(a₁, a₂, a₃, …, a_i, …, a_n)

式中，a₁是唯一的“第一个”数据元素，又称表头元素；a_n是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外,每个元素有且仅有一个直接后继（“直接前驱”和“前驱”、“直接后继”和“后继”通常被视为同义词）。

在稍复杂的线性表中，一个数据元素可以由若干个数据项(item)组成。在这种情况下，常把数据元素称为记录(record)，含有大量记录的线性表又称文件(file)。

以上就是线性表的逻辑特性,这种线性有序的逻辑结构正是线性表名字的由来。

由此,我们得出线性表的特点如下:

• 表中元素的个数有限。
• 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
• 表中元素都是数据元素，每个元素都是单个元素。
• 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
• 表中元素具有抽象性，即仅讨论元素间的逻辑关系,而不考虑元素究竟表示什么内容。

（二）线性表的基本操作

抽象数据类型线性表的定义如下：

ADT List {
    数据对象：D = { a<sub>i</sub> | a<sub>i</sub> ∈ ElemSet, i = 1,2,…,n, n>=0 }
    数据关系：R1 = ( <a<sub>i-1</sub>, a<sub>i</sub>> | a<sub>i-1</sub>,a<sub>i</sub> ∈ D, i = 2,…,n)
    基本操作：
    InitList( &L )
        操作结果：构造一个空的线性表L。
    DestroyList( &L )
        初始条件：线性表L已存在。
        操作结果：销毁线性表L。
    ClearList( &L )
        初始条件：线性表L已存在。
        操作结果：将L重置为空表。
    PrintList( L )
        初始条件：线性表L已存在。
        操作结果：按前后顺序输出线性表L的所有元素。
    ListEmpty( L )
        初始条件：线性表L已存在。
        操作结果：若L为空表，则返回True，否则返回False。
    Listlength( L )
        初始条件：线性表L已存在。
        操作结果：返回L中数据元素个数。
    GetElem( L, i, &e )
        初始条件：线性表L已存在，1<=i<=ListLength(L)。
        操作结果：用e返回L中第i个数据元素的值。
    LocateElem( L, e, compare() )
        初始条件：线性表L已存在，compare()是数据元素判定函数。
        操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。
    PriorElem( L, cur_e, &pre_e )
        初始条件：线性表L已存在。
        操作结果：若cur_e是L的数据元素，且不是第一个，则用则用pre_e来返回他的前驱，否则操作失败，pre_e无定义。
    NextElem( L, cur_e, &pre_e )
        初始条件：线性表L已存在。
        操作结果：若cur_e是L的数据元素，且不是最后一个，则用则用next_e来返回他的后继，否则操作失败，next_e无定义。
    ListInsert( &L, i, e )
        初始条件：线性表L已存在，1<=i<=ListLength(L)+1。
        操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
    ListDelete( &L, i, &e )
        初始条件：线性表L已存在且非空，1<=i<=ListLength(L)。
        操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
    ListTraverse( L, visit() )
        初始条件：线性表L已存在。
        操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
} ADT List

除了以上操作，还可以有一些更复杂的操作，例如拆分、合成与复制线性表。

二、线性表的实现

（一）顺序存储

1.顺序表的定义

线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素，又称为顺序表，因此表中逻辑上相邻的两个元素在物理位置上也连续，正因为这一点，而且线性表中各元素属于同一类型，因此，顺序表中的任意一个数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的数据结构。通常用高级程序设计语言的数组来描述线性表的顺序存储结构。

2.顺序表的实现

在C++语言中，我们可以使用一维数组作为顺序表的存储结构，但是同样是数组我们也有两种不同的实现方式，分别是静态分配与动态分配。对数组进行静态分配时，由于数组的大小和空间已经固定，所以空间一旦被占满，再加入新数据就会发生溢出，进而导致程序崩溃。而进行动态分配则可以避免这一问题，存储数组的空间大小是在程序执行过程中可以自由调整的，通过内存分配语句来进行控制，因此一旦空间占满，就另外开辟一块更大的存储空间，将原表中的元素全部拷贝到新空间，从而达到扩充数组存储空间的目的，而不需要一次性地为数组划分所有空间。

后续所有代码均采用C++实现，并为了保持跟课本上定义的抽象数据类型的基本操作一致，仅仅会使用部分C++特性。比如这一节我使用类来定义顺序表的数据结构，却将数据操作方法定义在类外，完全可以定义在类内进行，且更推荐将所有相关操作定义在同一类内而不是使用引用的方式。

(1)静态分配

完整代码

数据结构

首先来看一下静态分配顺序表的数据结构：

#define MaxSize 10 // 顺序表的最大长度
class SqList {
public:
    int data[MaxSize]; // 实际的存储结构，采用数组存储
    int length; // 记录顺序表的当前长度

    SqList() {
        length = 0;
        for (int i = 0; i < MaxSize; ++i) {
            data[i] = 0; // 将数组内的每个数值初始化为0,否则访问时为随机值，即脏数据
        }
    }
};

可见，在创建SqList这个数据结构时已经完成了内存分配，顺序表长度不可改变，并且由于数组可以通过数组下标来访问每个位置的元素，实现了顺序表随机存取的特性。但需要注意C++数组下标从0开始。

函数声明

下面是函数声明部分，定义了顺序表各个函数，这里不多做解释。

// 函数声明
void InitList(SqList &L);                           // 初始化
void DestroyList(SqList &L);                        // 销毁
void ClearList(SqList &L);                          // 重置为空表
void PrintList(const SqList &L);                    // 打印
bool ListEmpty(const SqList &L);                    // 判空
int ListLength(const SqList &L);                    // 获取长度
bool GetElem(const SqList &L, int i, int &e);       // 按位查找
int LocateElem(const SqList &L, int e);             // 按值查找
bool PriorElem(const SqList &L, int cur_e, int &pre_e); // 查找前驱
bool NextElem(const SqList &L, int cur_e, int &next_e); // 查找后继
bool ListInsert(SqList &L, int i, int e);           // 插入
bool ListDelete(SqList &L, int i, int &e);          // 删除
void ListTraverse(const SqList &L, void (*visit)(int)); // 遍历
bool LocateChangeElem(SqList &L, int e, int em);    // 先按值查找后改值
bool GetChangeElem(SqList &L, int i, int em);       // 先按位序查找后改值

初始化，销毁与清空

下面是顺序表的初始化，销毁与清空。初始化在新建SqList时其实已经发生，而销毁操作会自动进行，因此无需手动销毁，清空操作是将长度置0然后将数组元素全部清空。

// 实现模块
void InitList(SqList &L) {
    L.length = 0;
}

void DestroyList(SqList &L) {
    // 静态分配，无需显式销毁
}

void ClearList(SqList &L) {
    L.length = 0;
    for (int i = 0; i < MaxSize; ++i) {
        L.data[i] = 0;
    }
}

顺序表的打印

下面是顺序表的打印，即数据表的元素存储在数组的前length位置上，只需循环访问即可。

void PrintList(const SqList &L) {
    std::cout << "开始打印顺序表\n";
    for (int i = 0; i < L.length; ++i) {
        std::cout << "Data[" << i << "]==" << L.data[i] << "\n";
    }
    std::cout << "打印结束！\n";
}

判空与获取长度

下面是判空与获取长度函数，只需要获取顺序表length变量的值即可。

bool ListEmpty(const SqList &L) {
    return L.length == 0;
}

int ListLength(const SqList &L) {
    return L.length;
}

按序号获取元素

GetElem函数获取顺序表中第i个元素，这里的i是从1开始的，因此需要首先检测要求获取的值是否在范围内，小于1以及大于顺序表长度的值都是不允许的。如果查找失败则返回false，查找成功则返回true并且将查找到的值用e返回。

bool GetElem(const SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i - 1];
    return true;
}

查找元素位置

LocateList函数获取表中第一次出现e元素的位置，返回值为元素e在表中的位序，如果没找到则返回0。

int LocateElem(const SqList &L, int e) {
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] == e)
            return i + 1; // 返回位序
    }
    return 0; // 未找到返回0
}

获取某元素相邻元素

PriorElem和NextElem函数在顺序表中查找元素e，若找到元素e且它有前一个或后一个元素，则用pre_e或next_e返回其相邻的上一个元素或下一个元素并且返回值为true，否则返回值为false并且pre_e和next_e不代表任何值。

bool PriorElem(const SqList &L, int cur_e, int &pre_e) {
    for (int i = 1; i < L.length; ++i) {
        if (L.data[i] == cur_e) {
            pre_e = L.data[i - 1];
            return true;
        }
    }
    return false;
}

bool NextElem(const SqList &L, int cur_e, int &next_e) {
    for (int i = 0; i < L.length - 1; ++i) {
        if (L.data[i] == cur_e) {
            next_e = L.data[i + 1];
            return true;
        }
    }
    return false;
}

插入和删除元素

ListInsert与ListDelete分别用于向顺序表插入元素和删除元素，需要注意的是，由于顺序表中元素的逻辑顺序和物理顺序保持一致，因此在进行插入操作时，需要将被插入位置后面的所有元素全部后移；在进行删除操作时，需要将被删除元素后面的的全部元素向前移动一位。移动操作的时间复杂度为$O(n)$。

bool ListInsert(SqList &L, int i, int e) {
    if (i < 1 || i > L.length + 1 || L.length >= MaxSize)
        return false;
    
    for (int j = L.length; j >= i; --j) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

bool ListDelete(SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i - 1];
    for (int j = i; j < L.length; ++j) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

遍历顺序表

ListTraverse函数用于使用指定的函数访问顺序表的各元素。

void ListTraverse(const SqList &L, void (*visit)(int)) {
    for (int i = 0; i < L.length; ++i) {
        visit(L.data[i]);
    }
}

例如有个简单的函数visit

void visit(int a){
    std::cout<<a<<std::endl;
}

可通过下面的方式调用visit函数

ListTraverse(L,visit);

修改元素值

LocateChangeElem与GetChangeElem分别是两种改元素值的方式，代码比较简单，先定位后修改，代码如下。

bool LocateChangeElem(SqList &L, int e, int em) {
    int bitOrder = LocateElem(L, e);
    if (bitOrder != 0) {
        L.data[bitOrder - 1] = em;
        return true;
    }
    return false;
}

bool GetChangeElem(SqList &L, int i, int em) {
    if (i < 0 || i >= L.length) return false;
    L.data[i] = em;
    return true;
}

(2)动态分配

完整代码

数据结构

相较于静态分配，动态分配顺序表的实现要稍显复杂，顺序表的数据结构如下：

#define InitSize 10
class SeqList {
public:
    int *data; // 指示动态分配数组的指针
    int MaxSize; // 顺序表的最大容量
    int length; // 顺序表当前的长度

    SeqList() : data(new int[InitSize]), MaxSiz	e(InitSize), length(0) {}
    ~SeqList() {
        delete[] data;
    }
};

函数声明

函数声明如下，由于LocateChangeElem与GetChangeElem实现方法没有什么不同，这里不再赘述。其中IncreaseSize函数起到扩展动态分配顺序表的空间的作用，下面我仅介绍与上述实现不同的地方。

// 函数声明
bool InitList(SeqList &L);                         // 初始化
bool Empty(const SeqList &L);                      // 判空
bool Full(const SeqList &L);                       // 判满
void IncreaseSize(SeqList &L, int len);            // 动态扩展空间
bool ListInsert(SeqList &L, int i, int e);         // 插入
int GetElem(const SeqList &L, int i);              // 按位查找
int LocateElem(const SeqList &L, int e);           // 按值查找
bool ListDelete(SeqList &L, int i, int &e);        // 删除
void DestroySqList(SeqList &L);                    // 销毁
void ClearList(SeqList &L);                        // 清空
int ListLength(const SeqList &L);                  // 获取长度
bool PriorElem(const SeqList &L, int cur_e, int &pre_e); // 查找前驱
bool NextElem(const SeqList &L, int cur_e, int &next_e); // 查找后继
void ListTraverse(const SeqList &L, void (*visit)(int)); // 遍历
void PrintSqList(const SeqList &L);                // 打印顺序表

初始化

初始化函数如下，由于采用动态分配内存的方式，顺序表必须手动销毁。在这里我采用的C++类的方式编写的数据结构，因此使用析构函数~SeqList()进行顺序表的销毁。当然，按照前文方法定义，如果非要进行自行销毁的话也是可以的。

// 初始化
bool InitList(SeqList &L) {
    L.data = new int[InitSize]; 
    if (L.data == nullptr) return false;
    L.length = 0;
    L.MaxSize = InitSize;
    return true;
}
// 销毁
void DestroySqList(SeqList &L) {
    delete[] L.data;
    L.data = nullptr;
    L.length = 0;
    L.MaxSize = 0;
}

扩大顺序表内存

IncreaseSize是动态分配顺序表的核心函数，首先分配一个指针p指向原先顺序表的内存数据，其次分配增加之后的存储空间，然后将原内存数据复制进新空间，最后回收原先分配的内存，即完成了扩展空间操作。

// 扩展空间
void IncreaseSize(SeqList &L, int len) {
    std::cout << "开始扩展表存储空间..." << std::endl;
    int *p = L.data;
    L.data = new int[L.MaxSize + len];
    for (int i = 0; i < L.length; ++i) { // 复制数据
        L.data[i] = p[i];
    }
    L.MaxSize += len;
    delete[] p;
    std::cout << "扩展完成，当前最大容量: " << L.MaxSize << std::endl;
}

插入元素

ListInsert与静态分配的最大区别在于，当顺序表空间不足时会自动完成内存扩展，再进行插入操作。

// 插入
bool ListInsert(SeqList &L, int i, int e) {
    if (i < 1 || i > L.length + 1) return false;
    if (Full(L)) IncreaseSize(L, InitSize);
    for (int j = L.length; j >= i; --j) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

其余代码与上述静态分配顺序表相同，不进行列举。

（二）链式存储

顺序表中元素的物理地址相邻且连续，并且每个元素的长度和大小完全一致，因此可以随机存取存储表中的任意元素。但是这种顺序存储结构也具有一个严重的问题，那就是在插入或删除中间元素时需要移动大量的元素，这在顺序表很长时需要消耗大量的时间。链式存储线性表不需要使用的地址连续的物理单元，不要求元素间物理地址上相邻，而是通过指针的形式指向该元素的上一个或下一个结点，因此链式存储线性表在插入和删除内部元素时无需移动其他元素，但这也导致无法随机存取内部元素。

1.线性链表的定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素$a_i$，与其直接后继数据元素$a_{i+1}$之间的逻辑关系，对数据元素$a_i$来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素$a_i$的存储映像，称为结点(node)。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n个结点（$a_i$(1≤i≤n)的存储映像）链结成一个链表，即为线性表

$$(a_1,a_2,…,a_n)$$

的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

用线性链表表示线性表时，数据元素间的逻辑关系是由结点中的指针指示的，逻辑间相邻的元素不要求物理位置相邻，因此这种存储结构为非顺序映像或链式映像。

单链表的结点定义如下：

struct LNode {
    int data; //数据域
    LNode *next; //指针域
};

结点中的data用于存储数据，*next指向下个相邻节点，因此两个结点之间无需相邻，但是对于每个结点需要额外消耗内存来存储下个位置的指针。由于单链表的元素离散分布在内存中，因此不能进行随机存取，在查找某个元素时需要从表头开始遍历，依次查找。

通常用头指针L（或head）来标识一个单链表，指出链表的起始地址，头指针为空时表示单链表为空表。此外，为了操作上的方便，可以在单链表的第一个数据结点之前附加一个头结点，头结点可以不记录信息，也可以记录表长等信息。单链表带头结点时，头指针指向头结点，否则指向第一个数据结点。

引入头结点的优点：

1. 由于第一个数据结点的位置被存储在头结点的指针域中，因此在链表的第一个位置的操作跟在表的其他位置的操作一致，无须进行特殊处理。即修改第一个数据结点时不用修改头指针。
2. 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也得到了统一。

2.线性链表（单链表）的基本操作的实现

根据单链表是否带头结点，部分实现代码会有所不同，不同的代码会单独标注出来，相同的省略。完整代码

(1)带头结点的单链表

初始化

单链表的初始化如下，新建一个结点，数据域不赋值，由于初始化的单链表为空表，因此指针域为nullptr。

LinkList::LinkList() {
    head = new LNode;
    head->next = nullptr;
}

求表长

求表长操作，设置一个计数变量，从头结点开始，若该节点的指针域不为空则计数变量+1，直到当前结点指针域为空，返回计数变量。

int LinkList::length() const {
    int len=0;
    LNode *L = head;
    while(L->next!=nullptr){
        L=L->next;
        len++;
    }
    return len;
}

按序号查找结点

从单链表的第一个结点开始，沿着指针域依次向后搜索，直到找到第i个元素为止。如果给定序号不在链表范围内则查找失败。

三、线性表的应用