常用数据结构 & 算法分析

数据结构自 1968 年以来被设置为一门独立课程，是关于结构化编程（以模块功能和处理过程为主的编程范式）的一门方法学，主要研究的是数据的逻辑结构与物理结构以及它们之间的相互关系，并定义与这些结构相适应的算法。这里的算法描述的是一种确定并且有效的，适合用于计算机程序来实现和解决问题的方法。某种意义上，数据结构和算法是计算机科学与技术领域研究和应用的核心。

编写程应用序解决问题，首先需要从实际问题域当中抽象出一个模型，然后设计出求解该模型的算法。模型抽象的过程，实质是分析问题并从中找出操作对象，然后寻找出这些操作对象之间的关系，最终用程序语言加以描述的过程。本文采用 Linux C 语言进行描述，主要讲解了线性表、栈与队列、串、图共 5 种主要的数据结构，以及查找和排序这 2 种常用算法。

数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，可以将其定义为一个二元组的形式：

\[DataStructure = (D, S)\]

其中D是数据元素的有限集，S是D里关系的一个有限集合。

逻辑分布结构

逻辑结构是数据元素之间相互的逻辑关系。

• 集合结构：数据元素只是同属于一个集合，并不存在其它关系，类似于数学中的集合概念。
• 线性结构：数据元素之间存在一对一的关系。
• 树形结构：数据元素之间存在一对多的层次关系。
• 图状结构：数据元素之间存在多对多的关系。

物理存储结构

物理存储反映了数据元素在计算机存储器内的分布结构。

• 顺序存储结构：数据元素存放在连续的存储地址单元。
• 链式存储结构：数据元素存放在任意存储单元，通过存放数据元素地址的指针来建立关系。

抽象数据类型

抽象数据类型（ADT，Abstract Data Type）是指一个编程模型及定义在该模型上的一系列操作，其标准格式定义如下：

ADT 抽象数据类型名称 {
    数据对象 Data：......
    数据关系 Relation：......
    基本操作 Operation：......
        操作名称(参数)
            条件：......
            结果：......
}

算法分析

算法的复杂度通常使用大 O 符号进行描述，因而也被称为大 O 表示法。

时间复杂度

算法中基本操作重复执行的次数是问题规模n的某个函数\(f(n)\)，即随着问题规模n的增大，算法执行时间的增长率等于\(f(n)\)的增长率，这称为算法的渐近时间复杂度（asymptotic time complexity），简称为时间复杂度，记作：

\[T(n) = O(f(n))\]

频度（frequency count）是指程序的基本语句被计算机重复执行的次数，对于下面三段 C 语言代码：

++x, y=0;

for(i=1; i<=n; ++i){
    ++x;
    y += x;
}

for(j=1; j<=n; ++j){
    for(k=1; k<=n; ++k) {
        ++x;
        y += x;
    }
}

上述代码都包含了让x自增1的基本操作语句++x，该语句被执行的频度分别为1、n、n²，那么三段程序的时间复杂度分别为常量阶O(1)、线性阶O(n)、平方阶O(n²)。对于更加复杂的算法，还可能存在对数阶O(log n)、指数阶O(2ⁿ)等数量级的复杂度。

名称	阶	字符
常数阶	O(1)	12
线性阶	O(n)	2n+3
平方阶	O(n²)	3n²+2n+1
对数阶	O(logn)	5log₂n+20
nlogn 阶	O(nlogn)	2n+3nlog₂n+19
立方阶	O(n³)	6n³+2n²+3n+4
指数阶	O(2ⁿ)	2ⁿ

空间复杂度

类似于算法的时间复杂度，空间复杂度（space complexity）是算法所需计算机存储资源空间的量度，记作：

\[S(n) = O(f(n))\]

其中n为问题的规模大小，计算机程序除了需要存储空间存放所使用的指令、常数、变量、输入数据之外，还需要存放一些计算相关的辅助存储单元。如果输入数据占用的空间只取决于问题本身而与算法无关，则只需要分析输入和程序之外的存储空间，否则应该同时考虑输入本身所占用的空间。如果额外空间相对于输入数据而言是常数，则称此算法为原地工作；如果占用存储空间依赖于特定输入，则除特别指出以外，均按最坏情况分析。

线性表

线性表（linear list）是 n 个数据元素的有限序列，记为\((a_1,..., a_{i-1},a_i,a_{i+1},...,a_n)\)。其中，\(a_{i+1}\)是\(a_i\)的直接前驱元素，\(a_{i-1}\)是\(a_i\)的直接后继元素；线性表中元素的个数n称为线性表长度，下标i称为数据元素在线性表中的位置顺序。线性表是一种非常灵活的数据结构，可以按需进行增长或者缩短，或者访问任意的线性表元素，以及执行插入删除等操作。线性表的抽象数据类型定义如下：

ADT List {
    数据对象：D = {a | aᵢ∈ElemSet, i = 1,2,...,n, n>=0}
    数据关系：Rl = {<aᵢ₋₁, aᵢ> | aᵢ₋₁, aᵢ∈D, i=2,...,n}
    基本操作：
        InitList(&L)
            结果：构造一个空的线性表L。
        DestroyList(&L)
            条件：线性表L已经存在。
            结果：销毁线性表L。
        ClearList(&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, coompare())
            条件：线性表L已经存在，compare()是数据元素判定函数。
            结果：返回L中第一个与e满足关系compare()的数据元素的位序。如果这样的数据元素不存在，则返回值为0。
        PriorElem(L, cur_e, &pre_e)
            条件：线性表 L 已经存在。
            结果：如果cur_e是L的数据元素，并且不是第一个，则通过pre_e返回其前驱，否则操作失败，pre_e无定义。
        NextElem(L, cur_e, &next_e)
            条件：线性表 L 已经存在。
            结果：如果cur_e是L的数据元素，并且不是第一个，则通过pre_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：线性表 LA 和 LB 分别代表两个数据集合 A 与 B，现在需要求这两个集合的并集并将结果赋值给 A，即\(A=A{\bigcap}B\)。

解决该问题，需要首先扩大线性表 LA 的长度，然后将线性表 LB 中存在而线性表 LA 中不存在的数据元素插入至 LA。然后从线性表 LB 依次获取每个数据元素，并依次在线性表 LA 中进行查询，如果该数据元素不存在则执行插入至 LA 的操作：

void Union(List &La, List Lb) {

    ElemType e;             // 声明指定类型的数据元素
    int La_len, Lb_len, i;  // 声明线性表长度

    // 获取线性表长度
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);

    for (i = 1; i <= Lb_len; i++) {
        GetElem(Lb, i, e);                // 获取线性表Lb中的第i个数据元素并赋值给e
        if (!LocateElem(La, e, equal))    // 如果线性表La中不存在和e相同的数据元素
            ListInsert(La, ++La_len, e);  // 那么执行插入操作
    }
}

示例 2：线性表 LA 和 LB 中的数据元素按照递增排列，现在要求将 LA 和 LB 归并为一个新的线性表 LC，并且 LC 中的数据元素仍然按照递增排列。例如：LA=(1,2,3)、LB=(4,5,6)，那么期望得到的结果为：LC=(1,2,3,4,5,6)。

解决此问题，首先需要设置 LC 为空表，然后将 LA 或 LB 中的元素逐个插入 LC。为了让 LC 中的元素递增排列，可以设置分别指向 LA 和 LB 中元素的i和j指针，如果设置i指向的元素为a，j指向的元素为b，那么插入至 LC 中的元素c应同时满足如下条件：

\[c=\begin{cases}a& 当{a ≤ b}时\\\\b& 当{a > b}时\end{cases}\]

由于指针i和j的初始值均为1，因此在其所指向的元素插入至 LC 之后，LA 或者 LB 中的其它数据元素顺序后移。

void MergeList(List La, List Lb, List &Lc) {
    int La_len, Lb_len;
    ElemType ai, bj;
    int i = 1, j = 1, k = 0;

    InitList(Lc); // 使用参数传递过来的Lc指针，初始化一个空线性表

    La_len = ListLength(La); // 获取参数传递过来的线性表La的长度
    Lb_len = ListLength(Lb); // 获取参数传递过来的线性表Lb的长度

    while ((i <= La_len) && (j <= Lb_len)) {
        GetElem(La, i, ai); // 获取线性表LA位置i的元素ai
        GetElem(Lb, j, bj); // 获取线性表LB位置j的元素bj
        // 如果aj小于或等于bj
        if (ai <= bj) {
            ListInsert(Lc, ++k, ai); // 将ai插入LC的k+1位置
            ++i;
        } else {
            ListInsert(Lc, ++k, bj); // 将bj插入LC的k+1位置
            ++j;
        }
    }

    while (i <= La_len) {
        GetElem(La, i++, ai);    // 获取线性表LA在i+1位置的元素ai
        ListInsert(Lc, ++k, ai); // 将ai插入LC的k+1位置
    }

    while (j <= Lb_len) {
        GetElem(Lb, j++, bj);    // 获取线性表LB在j+1位置的元素bj
        ListInsert(Lc, ++k, bj); // 将bj插入LC的k+1位置
    }
}

上面这两个算法的时间复杂度取决于抽象数据类型 List 中定义的基本操作的执行时间，如果GetElem()与ListInsert()的执行时间与线性表长度无关，LocateElem()的执行时间与表长成正比，则上面例子中Union()的时间复杂度为\(O(ListLength(LA) × ListLength(LB))\)，MergeList()的时间复杂度为\(O(ListLength(LA) + ListLength(LB))\)；虽然MergeList()包含三个while循环语句，但是仅当i和j均指向线性表中实际存在的元素时才会取值比较。而且如果其中一个线性表的元素已经插入至线性表 LC，那么只需要将另一个线性表的剩余元素依次插入即可。因而对于传入的每一组具体参数 LA 和 LB，后面两个while循环语句只会执行到一个循环体。

线性表顺序实现（顺序表）

线性表的顺序实现是指使用一组地址连续的存储单元依次存储线性表中的各个数据元素，通常使用高级语言中的数组来进行实现（C 语言中数组的每个元素都是相同数据类型），其中第 1 个数据元素的位置就是线性表的起始位置和基地址。只要确定了线性表的起始位置，线性表中的任意数据元素就可以进行随机存取。笔者使用了 MinGW 内置的 GCC 作为 C 语言程序编译器，其整型数据类型int所占用的存储空间为 4 个字节，因此整型数组int a[10]的存储空间分布如下：

顺序表的存储结构：

#define LIST_INIT_SIZE 100 // 顺序表存储空间初始大小
#define LISTINCREMENT 10   // 顺序表存储空间分配的步进增量

typedef struct{
  ElemType *elem; // 存储空间的基地址
  int length;     // 顺序表当前长度
  int listsize;   // 当前分配的存储空间大小，以sizeof(ElemType)作为单位
}SqList

上述顺序表定义中，数组指针elem指向线性表的基地址，length等于线性表当前的长度，listsize表示顺序表当前分配的存储空间大小。顺序表初始化时，会首先分配一个预定义大小的数组存储空间，并将线性表当前长度设置为0；当存储空间不足时，会为顺序表增加LISTINCREMENT个数据元素空间。

Status InitList_Sq(SqList &L) {
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); // 构造一个空线性表L
    if (!L.elem)
        exit(OVERFLOW);          // 存储分配失败
    L.length = 0;                // 初始化一个长度为0的空顺序表
    L.listsize = LIST_INIT_SIZE; // 将宏定义中声明的LIST_INIT_SIZE作为初始的存储大小
    return OK;
}

顺序表的这种存储结构非常容易实现随机的存取操作，接下来重点讨论一下顺序表的插入和删除操作。

插入

插入操作是指在顺序表的两个元素之间插入一个新的元素，插入位置之后的元素会顺序向后移动一个位置，操作完成之后整个顺序表的长度也会相应的增加一个位置。

/** 向顺序线性表L的第i个元素之前插入新的元素e，其中i的取值范围为1≤i≤ListLength_Sq(L)+1 */
Status ListInsert_Sq(SqList &L, int i, ElemType e) {
    ElemType *p;

    /* 判断i值是否合法 */
    if (i < 1 || i > L.length + 1)
        return ERROR;

    /* 如果当前顺序表长度已满，则增加容量 */
    if (L.length >= L.listsize) {
        ElemType *newbase = (ElemType *)realloc( L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType) );
        if (!newbase)
            return ERROR;            // 如果存储分配失败
        L.elem = newbase;            // 新的顺序表基地址
        L.listsize += LISTINCREMENT; // 增加顺序表存储容量
    }

    ElemType *q = &(L.elem[i - 1]); // q为新元素的插入位置
    for (p = &(L.elem[L.length - 1]); p >= q; --p){
        *(p + 1) = *p;
    }

    /* 插入位置及之后的元素右移 */
    *q = e;     // 插入数据元素e
    ++L.length; // 顺序表长度增加1位
    return OK;
}

删除

删除顺序表中的某个元素，会导致删除位置之后的元素顺序向前移动一个位置，操作完成之后顺序表长度会相应的减少一个位置。

/** 删除顺序线性表L的第i个元素，并使用e返回该元素的值，其中i的取值范围为1≤i≤ListLength_Sq(L) */
Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
    ElemType *p, *q;

    /* 判断i值是否合法 */
    if (i < 1 || i > L.length)
        return ERROR;

    p = &(L.elem[i - 1]);      // 被删除元素的位置
    e = *p;                    // 将被删除元素的值赋给e
    q = L.elem + L.length - 1; // 表尾元素的位置

    for (++p; p <= q; ++p) {
        *(p - 1) = *p;  // 被删除元素之后的元素向左移动
    }

    --L.length;         // 顺序表的长度减去1
    return OK;
}

向顺序表中某个位置插入或删除一个元素，时间主要耗费在移动数组的元素上，而移动元素的个数取决于插入或删除元素在数组中的位置。从操作概率上分析，顺序表插入或删除元素平均需要移动数组中约一半数量的元素。因此，如果顺序表长度为n，那么算法ListInsert_Sq()和ListDelete_Sq()的时间复杂度为\(O(n)\)。

查找

顺序表L中查询是否存在与e相同数据元素的最简便办法是让e与L中的数据元素逐个进行比较，如果存在与e相同的元素则返回该元素在L中的位置，否则返回0。

/** 在顺序线性表L中查找首个与e满足compare()关系的数据元素的位置序号，如果没有查找到就返回0 */
int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType))
    int i;
    ElemType *p;

    i = 1;      // i的初值为第1个元素的位置序号
    p = L.elem; // p的初值为第1个元素的存储位置

    while (i <= L.length && !(*compare)(*p++, e)){
        ++i;
    }

    if (i <= L.length)
        return i;
    else
        return 0;
}

线性表链式实现（线性表）

栈与队列

串

数组与广义表

树与二叉树

图

动态存储管理

查找

内部排序

外部排序

文件

\[ \]