原发布于7月21日，因期末考试影响这篇没有学完，现开始继续更新
代码部分一些内容进行了省略，

数据结构 C语言版

绪论

基本概念

数据 Data：客观事物，所有能输入到计算机中并被计算机程序处理的符号的总称
数据元素 Data Element：数据基本单位，整体
数据项 Data Item：有独立含义，不可分割
数据对象 Data Object：性质相同的数据元素集合，数据的子集

数据结构

逻辑结构

集合
线性
树
图、网状

线性结构：线性表、栈和队列、字符串、数组、广义表（线性表的推广
非线性结构：树、二叉树、有向图、无向图

存储结构

也称物理结构

顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，数组
链式存储结构：给每个结点附加指针字段，用于存储后继元素的存储地址，指针

数据类型和抽象数据类型

数据类型 Data Type：一个值的集合和定义在这个值集上的一组操作的总称
抽象数据类型 Abstract Data Type，ADT：用户定义，包括：数据对象、数据对象上关系的集合、对数据对象的基本操作的集合

ADT 抽象数据类型名
{
    数据对象：<数据对象的定义>
    数据关系：<数据关系的定义>
    基本操作：<基本操作的定义>
} ADT 抽象数据类型名

其中，基本操作的定义格式为

1
2
3

基本操作名(参数表)
    初始条件：<初始条件描述>
    操作结构：<操作结果描述>

e.g. 复数

定义部分

ADT Complex
{
 数据对象：D = {e1, e2 | e1, e2 ∈ R}
 数据关系：S = {(e1, e2) | e1 是复数实部，e2 是复数虚部}
 基本操作：
   Create(&C, x, y)
     操作结果：构造复数C，其实部和虚部分别赋以参数x, y
   GetReal(C)
     初始条件：C已存在
     操作结果：返回C的实部值
   GetImage(C)
     初始条件：C已存在
     操作结果：返回C的虚部值
   Add(C1, C2)
     初始条件：C1, C2是复数
     操作结果：返回C1和C2的和
   Sub(C1, C2)
     初始条件：C1, C2是复数
     操作结果：返回C1和C2的差
} ADT Complex

表示部分

typedef struct
{
    float Realpart;
    float Imagepart;
} Complex;

实现部分

void Create(&Complex C, float x, float y)
{    // 构造一个复数
    C.Realpart = x;
    C.Imagepart = y;
}
float GetReal(Complex C)
{    // 取C的实部
    return C.Realpart;
}
float GetImag(Complex C)
{    // 取C的虚部
    return C.Imagepart;
}
Complex Add(Complex C1, Complex C2)
{    // 求两个复数的和
    Complex sum;
    sum.Realpart = C1.Realpart + C2.Realpart;
    sum.Imagepart = C1.Imagepart + C2.Imagepart;
    return sum;
}
Complex Sub(Complex C1, Complex C2)
{    // 求两个复数的差
    Complex difference;
    difference.Realpart = C1.Realpart - C2.Realpart;
    difference.Imagepart = C1.Imagepart - C2.Imagepart;
    return difference;
}

算法和算法分析

算法的特性

有穷性
确定性
可行性
输入
输出

评价优劣的基本标准

正确性
可读性
健壮性（对输入非法数据的处理反应
高效性

时间复杂度

问题规模：问题的输入量，问题大小的本质表示，一般用整数n
语句频度 Frequency Count：一条语句的重复执行次数

数量级 Order of Magnitude 为 O

渐进时间复杂度，简称时间复杂度 Time Complexity
T(n) = O(f(n))
旧博客：Time O

最好、最坏和平均时间复杂度

平均时间复杂度：在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值

空间复杂度

渐进空间复杂度 Space Complexity
S(n) = O(f(n))

线性表

定义和特点

定义

由 n 个数据特性相同的元素构成的有限序列
n = 0 时为空表

非空线性表的特点

存在唯一一个被称作“第一个”的数据元素
存在唯一一个被称作“最后一个”的数据元素
除第一个之外，结构中的每个数据元素均只有一个前驱
除最后一个之外，结构中的每个数据元素均只有一个后驱

类型定义

ADT List
{
    数据对象：D = {a_i | a_i∈ElemSet, i=1, 2, …, n, n ≥ 0}
    数据关系：R = {(a_i-1, a_i) | a_i-1, a_i∈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)
        初始条件：线性表 L 已存在
        操作结果：返回 L 中第1个值与 e 相同的元素在 L 中的位置，若数据不存在，返回值为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 的数据元素，且不是最后一个，则用 next_e 返回其后继，否则操作失败，next_e 无定义
      ListInsert(&L, i, e)
        初始条件：线性表 L 已存在，且 1 ≤ i ≤ ListLength(L) + 1
        操作结果：在 L 中第 i 个位置之前插入新的数据元素 e, L 的长度加1
      ListDelete(&L, i)
        初始条件：线性表 L 已存在且非空，且 1 ≤ i ≤ ListLength(L)
        操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L的长度都加1
      TraverseList(L)
        初始条件：线性表 L 已存在
        操作结果：对线性表 L 进行遍历，在遍历的过程中
} ADT List

顺序表示

每个存储元素占 l 个存储单元
LOC(a_i) = LOC(a₁) + (i - 1) * l

只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存储，所以线性表的顺序存储结构是一种随机存储的存储结构

#define MAXSIZE 100        // 顺序表可能达到的最大长度
typedef struct
{
    ElemType *elem;        // 存储空间的基地址
    int length;            // 当前长度
} SqList                // 顺序表的结构类型为 SqList

初始化

Status InitList(SqList &L)
{
    L.elem = new ElemType[MAXSIZE];
    if (!L.elem) exit(OVERFLOW);
    L.length = 0;
    return OK;
}

取值

Status GetElem(SqList L, int i, ElemType &e)
{
    if (i < 1 || i > L.length) return ERROR;
    e = L.elem(i - 1);
    return OK;
}

查找

int LocateElem(SqList L, ElemType e)
{
    for (i = 0; i < L.length; i++)
        if (L.elem[i] == e) return i + 1;
    return 0;
}

O(n)

插入

Status ListInsert(SqList &L, int i, ElemType e)
{
    if ((i < 1) || (i > L.length + 1)) return ERROR;
    if (L.length == MAXSIZE) return ERROR;
    for (int j = L.length - 1; j >. i - 1; j--)
        L.elem[j + 1] = L.elem[j];
    L.elem[i - 1] = e;
    ++L.length;
    return OK;
}

O(n)

删除

Status ListDelete(SqList &L, int i)
{
    if ((i < 1) || (i > L.length)) return ERROR;
    for (int j = i; j <= L.length - 1; j++)
        L.elem[j - 1] = L.elem[j];
    --L.length;
    return OK;
}

O(n)

链式表示

用一组任意的存储单元存储线性表的数据元素（可以不连续）

结点包括数据域和指针域，指针域中存储的信息称作指针或链

根据链表结点所含指针个数、指针指向和指针连接方式，将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等，其中除单链表、循环链表、双向链表，其他用于树和图等结构

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

通常习惯上用 LinkList 定义单链表，强调定义的是某个单链表的头指针
用 LNode * 定义指向单链表任意结点的指针变量

通常增加一个多余的头结点

便于首元结点的处理，对首元结点的操作与其他数据元素相同，无需特殊处理
便于空表和非空表的统一处理：无需判断头指针是否为 nullptr

首元结点：链表中存储第一个数据元素 a_i 的结点
头结点：首元结点之前附设的一个结点，其指针域指向首元结点，数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息
头指针：指向链表的第一个结点

单链表是非随机存取的存储结构，要取得第 i 个数据元素必须从头指针出发顺链进行寻找，也称为顺序存取的存取结构

初始化

Status InitList(LinkList &L)
{
    L = new LNode;
    L->next = NULL;
    return OK;
}

取值

Status GetElem(LinkList L, int i, ElemType &e)
{
    p = L->next;
    int j = 1;
    while (p && j < i)
    {
        p = p->next;
        ++j;
    }
    if (!p || j > i) return ERROR;
    e = p->data;
    return OK;
}

O(n)

查找

LNode *LocateElem(LinkList L, ElemType e)
{
    p = L->next;
    while (p && p->data != e)
        p = p->next;
    return p;
}

O(n)

插入

Status ListInsert(LinkList &L, int i, ElemType e)
{
    p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        ++j;
    }
    if (!p || j > i - 1) return ERROR;
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

O(n)

删除

Status ListDelete(LinkList &L, int i)
{
    p = L;
    int j = 0;
    while ((p->next) && (j < i - 1))
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || (j > i - 1)) return ERROR;
    q = p->next;
    p->next = q->next;
    delete q;
    return OK;
}

O(n)

创建

前插法

创建一个只有头结点的空链表
根据待创建的元素个数 n 循环 n 次执行
- 生成一个新结点 *p
- 输入元素值赋给新结点 *p 的数据域
- 将新结点 *p 插入到头结点之后

逆位序输入数据

void CreateList_H(LinkList &L, int n)
{
    L = new LNode;
    L->next = NULL;
    for (i = 0; i < n; ++i)
    {
        p = new LNode;
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
}

O(n)

后插法

创建一个只有头结点的空链表
尾指针 r 初始化，指向头结点
根据创建链表包括的元素个数 n 循环 n 次执行
- 生成一个新结点 *p
- 输入元素值赋给新结点 *p 的数据域
- 将新结点 *p 插入到尾结点 *r 之后
- 尾指针 r 指向新的尾结点 *p

void CreateList_R(LinkList &L, int n)
{
    L = new LNode;
    L->next = NULL;
    r = L;
    for (i = 0; i < n; ++i)
    {
        p = new LNode;
        cin >> p->date;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

循环链表

Circular Linked List
表中最后一个结点的指针域指向头结点

终止条件

1	p != L \|\| p->next != L

合并两个表时

1
2
3

p = B->next->next;
B->next = A->next;
A->next = p;

O(1)

双向链表

typedef struct DuLNode
{
    ElemType date;
    struct DuLNode *prior;
    struct DeLNode *next;
} DuLNode, *DuLinkList;

插入

Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)
{
    if (!(p = GetElem_DuL(L, i))) return ERROR;
    s = new DuLNode;
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
}

删除

Status ListDelete_DuL(DuLinkList &L, int i)
{
    if (!(p = GetElem_DuL(L, i))) return ERROR;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    delete p;
    return OK;
}

顺序表和链表的比较

空间性能

存储空间分配
存储密度大小

存储密度 = 数据元素本身占用的存储量 / 结点结构占用的存储量

时间性能

存取元素的效率
插入和删除操作的效率

线性表的应用

合并（去重）

分别获取 LA 表长 m 和 LB 表长 n
从 LB 中第1个数据元素开始，循环 n 次执行、
- 从 LB 中查找第 i (1 ≤ i ≤ n)个数据元素赋给 e
- 在 LA 中查找元素 e，如果不存在，则将 e 插在表 LA 的最后

void MergeList(List &LA, List LB)
{
    m = ListLength(LA);
    n = ListLength(LB);
    for (i = 1; i <= n; ++i)
    {
        GetElem(LB, i, e);
        if (!LocateElem(LA, e))
            ListInsert(LA, ++m, e);
    }
}

O(m * n)

合并（有序表不去重）

顺序有序表

创建一个表长为 m+n 的空表 LC
指针 pc 初始化，指向 LC 的第一个元素
指针 pa 和 pb 初始化，分别指向 LA 和 LB 的第一个元素
当指针 pa 和 pb 均未达到相应表尾时，则依次比较 pa 和 pb 所指向的元素值，从 LA 或 LB 中拿较小的结点插入到 LC 的最后
如果 pb 已到达 LB 的表尾，依次将 LA 的剩余元素插入 LC 的最后
如果 pa 已到达 LA 的表尾，依次将 LB 的剩余元素插入 LC 的最后

void MergeList_Sq(SqList LA, SqList LB, SqList &LC)
{
    LC.length = LA.length + LB.length;
    LC.elem = new ElemType(LC.length);
    pc = LC.elem;
    pa = LA.elem;
    pb = LB.elem;
    pa_last = LA.elem + LA.length - 1;
    pb_last = LB.elem + LB.length - 1;
    while ((pa <= pa_last) && (pb <= pb_last))
    {
        if (*pa <= *pb) *pc++ = *pa++;
        else *pc++ = *pb++;
    }
    while (pa <= pa_last) *pc++ = *pa++;
    while (pb <= pb_last) *pc++ = *pb++;
}

O(m + n)
O(m + n)

链式有序表

指针 pa 和 pb 初始化，分别指向 LA 和 LB 的第一个结点
LC 的结点取值为 LA 的头结点
指针 pc 初始化，指向 LC 的头结点
当指针 pa 和 pb 均未到达相应的表尾时，则依次比较 pa 和 pb 所指向的元素值，从 LA 或 LB 中拿较小的结点插入到 LC 的最后
将非空表的剩余段插入到 pc 所指结点之后
释放 LB 的头结点

void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC)
{
    pa = LA->next;
    pb = LB->next;
    LC = LA;
    pc = LC;
    while (pa && pb)
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    delete LB;
}

O(m + n)
O(1)

栈和队列

定义和特点

栈 stack 仅在表尾进行插入或删除操作的线性表
表尾称为 栈顶 top，表头称为 栈底 bottom，不含元素的空表称为空栈
后进先出 First In First Out (LIFO)

队列

队列 queue 是 先进先出 First In First Out (FIFO) 的线性表
队列中，允许插入的一端称为 队尾 rear，允许删除的一段称为 队头 front

栈的表示和操作

ADT Stack
{
    数据对象：D = {a_i | a_i∈ElemSet, i = 1, 2, …, n, n ≥ 0}
    数据关系：R = {i - 1, a_i> | a_{i - 1}, a_i∈D, i = 2, …, n}
        a_n为栈顶，a_i为栈底
    基本操作：
        InitStack(&S)
            操作结果：构造一个空栈 S
        DestroyStack(&S)
            初始条件：栈 S 已存在
            操作结果：栈 S 被销毁
        ClearStack(&S)
            初始条件：栈 S 已存在
            操作结果：栈 S 清为空栈
        StackEmpty(S)
            初始条件：栈 S 已存在
            操作结果：若 S 为空栈，返回 true，否则返回 false
        StackLength(S)
            初始条件：栈 S 已存在
            操作结果：返回 S 的元素个数，即栈的长度
        GetTop(S)
            初始条件：栈 S 已存在且非空
            操作结果：返回 S 的栈顶元素，不修改栈顶指针
        Push(&S, e)
            初始条件：栈 S 已存在
            操作结果：插入 e 为新的栈顶元素
        Pop(&S, &e)
            初始条件：栈 S 已存在且非空
            操作结果：删除 S 的栈顶元素，并用 e 返回其值
        StackTraverse(S)
            初始条件：栈 S 已存在且非空
            操作结果：从栈底到栈顶依次对 S 的每个数据元素进行访问
} ADT Stack

顺序栈

#define MAXSIZE 100
typedef struct
{
    SElemType *base;    // 栈底指针
    SelemType *top;
    int stacksize;
} SqStack;

初始化

为栈动态分配一个最大容量为 MAXSIZE 的数组空间，使 base 指向栈底
栈顶指针 top 初始为 base，即为空栈
stacksize 置为 MAXSIZE

Status InitStack(SqStack &S)
{
    S.base - enw SElemType[MAXSIZE];
    if (!S.bash) exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

入栈

判断是否已满，若满返回 ERROR
将新元素压入栈顶，栈顶指针加1

Status Push(SqStack &S, SElemType e)
{
    if (S.top - S.base == S.stacksize) return ERROR;
    *S.top++ = e;
    return OK;
}

出栈

判断栈是否空，若空返回 ERROR
栈顶指针减1，栈顶元素出栈

Status Pop(SqStack &S, SElemType &e)
{
    if (S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}

取栈顶元素

当栈非空时，返回栈顶元素的值

SelemType GetTop(SqStack S)
{
    if (S.top != S.base)
        return *(S.top - 1);
}

链栈

typedef struct StackNode
{
    ElemType data;
    struct StackNode *next;
} StackNode, *LinkStack;

初始化

没必要设头结点，直接将栈顶指针置空

Status InitStack(LinkStack &S)
{
    S = NULL;
    return OK;
}

入栈

不需要判断是否满

为入栈元素 e 分配空间，用指针 p 指向
将新结点数据域置为 e
将新结点插入栈顶
修改栈顶指针为 p

Status Push(LinkStack &S, SElemType e)
{
    p = new StackNode;
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}

出栈

判断栈是否为空，若空返回 ERROR
将栈顶元素赋给 e
临时保存栈顶元素的空间，以备释放
修改栈顶指针，指向新的栈顶元素
释放原栈顶元素的空间

Status Pop(LinkStack &S, SElemType &e)
{
    if (S = NULL) return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    delete p;
    return OK;
}

取栈顶元素

SElemType GetTop(LinkStack S)
{
    if (S != NULL)
        return S->data;
}

栈与递归

分治法

能将一个问题转变成一个新问题，解法相同或类同，不同的仅是处理的对象，并且这些处理对象更小且变化有规律
可以通过转化而使问题简化
必须有一个明确的递归出口，或称为递归的边界

void p(参数表)
{
    if (递归结束条件成立) 可直接求解;
    else p(较小的参数);
}

如果当递归结束条件成立，只执行 return 操作时，分治法可以化简为

void p(参数表)
{
    if (递归结束条件不成立)
        p(较小的参数);
}

e.g. 遍历输出链表

void TraverseList(LinkList p)
{
    if (p)
    {
        cout << p->data << endl;
        TraverseList(p->next);
    }
}

e.g. 汉诺塔问题

问题描述
1. 每次只能移动一个圆盘
2. 圆盘可以插在 A、B、C 中任一塔座上
3. 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上
问题分析
设 A 柱上最初的盘子总数为 n，则当 n=1 时，只要将编号为 1 的圆盘从塔座 A 直接移至 C 上即可；否则，执行以下
1. 用 C 柱做过渡，将 A 柱上的 (n-1) 个盘子移到 B 柱上
2. 将 A 柱上最后一个盘子直接移到 C 柱上
3. 用 A 柱做过渡，将 B 柱上的 (n-1) 个盘子移到 C 柱上
算法步骤
1. 如果 n=1，则直接将编号为 1 的圆盘从 A 移到 C，递归结束
2. 否则
  - 递归，将 A 上编号为 1 至 n-1 的圆盘移到 B，C 做辅助塔
  - 直接将编号为 n 的圆盘从 A 移到 C
  - 递归，将 B 上编号为 1 至 n-1 的圆盘移到 C，A 做辅助塔
算法描述

int m = 0;

void move(char A, int n, char C)
{
    cout << ++m << ", " << n << ", " << A << ", " C << endl;
}

void Hanoi(int n, char A, char B, char C)
{
    if (n == 1) move(A, 1, C);
    else
    {
        Hanoi(n-1, A, C, B);
        move(A, n, C);
        Hanoi(n-1, B, A, C);
    }
}

O(2ⁿ)

队列的表示和操作

ADT Queue
{
    数据对象：D = {a_i | a_i∈ElemSet, i = 1, 2, …, n, n ≥ 0}
    数据关系：R = {i-1, a_i> | a_i-1, a_i∈D, i = 2, …, n}
            约定其中 a_i 端为队列头，a_n 为队列尾
    基本操作：
        InitQueue(&Q)
            操作结果：构造一个空队列 Q
        DestroyQueue(&Q)
            初始条件：队列 Q 已存在
            操作结果：队列 Q 被销毁
        ClearQueue(&Q)
            初始条件：队列 Q 已存在
            操作结果：将 Q 清为空队列
        QueueEmety(Q)
            初始条件：队列 Q 已存在
            操作结果：若 Q 为空队列，则返回 true，否则返回 false
        QueueLength(Q)
            初始条件：队列 Q 已存在
            操作结果：返回 Q 的元素个数，即队列的长度
        GetHead(Q)
            初始条件：Q 为非空队列
            操作结果：返回 Q 的队头元素
        EnQueue(&Q, e)
            初始条件：队列 Q 已存在
            操作结果：插入元素 e 为 Q 的新队尾元素
        DeQueue(&Q, &e)
            初始条件：Q 为非空队列
            操作结果：删除 Q 的队头元素，并用 e 返回其值
        QueueTraverse(Q)
            初始条件：Q 已存在且非空
            操作结果：从队头到队尾，依次对 Q 的每个数据元素访问
} ADT Queue

循环队列——队列的顺序表示和实现

#define MAXQSIZE 100
typedef struct
{
    QElemType *base;    // 存储空间的基地址
    int front;            // 头指针
    int rear;            // 尾指针
} SqQueue

初始化时，令 front = rear = 0；每当有新的队尾元素时，尾指针 rear 加一；每当删除队列队头元素时，头指针 front 加一

假溢出：溢出 base
解决方案：通过取模实现头尾指针的循环
同时带来的问题：循环队列不能以头、尾指针的值是否相同来判别队列是否为空
处理方法

少用一个元素空间，即队列空间大小为 m 时，有 m-1 个元素就认为是队满。这样判断队空的条件不变，即当头、尾指针的值相同时，则认为队空；而当尾指针在循环意义上加 1
后是等于头指针，则认为队满

队空的条件：Q.front == Q.rear
队满的条件：(Q.rear + 1) % MAXQSIZE == Q.front

设一个标志位以区别队列是空还是满

初始化

为队列分配一个最大容量为 MAXQSIZE 的数组空间，base 指向数据空间的首地址
头指针和尾指针置为零，表示队列为空

Status InitQueue(SqQueue &Q)
{
    Q.base = new QElemType[MAXQSIZE];
    if (!Q.base) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

求队列长度

int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

入队

判断队列是否满，若满返回 ERROR
将新元素插入队尾
队尾指针加 1

Status EnQueue(SqQueue &Q, QElemType e)
{
    if ((Q.rear + 1) % MAXQSIZE == Q.front)
        return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}

出队

判断队列是否为空，若空返回 ERROR
保存队头元素
队头指针加 1

Status DeQueue(SqQueue &Q, QElemType &e)
{
    if (Q.front == Q.rear) return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}

取队头元素

QElemType GetHead(SqQueue Q)
{
    if (Q.front != Q.rear)
        return Q.base[Q.front];
}

链队——队列的链式表示和实现

typedef struct QNode
{
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;
type struct
{
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;

初始化

生成新结点作为头结点，队头和队尾指针指向此结点
头结点的指针域置空

Status InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;
    return OK;
}

入队

为入队元素分配结点空间，用指针 p 指向
将新结点数据域置为 e
将新结点插入到队尾
修改队尾指针为 p

Status EnQue(LinkQueue &Q, QElemType e)
{
    p = new QNode;
    p->data = e;
    p->next = NULL;
    Q.rear ->next = p;
    Q.rear = p;
    return OK;
}

出队

判断队列是否为空，若空返回 ERROR
临时保存队头元素的空间，以备释放
修改头结点的指针域，指向下一个结点
判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点
释放原队头元素的空间

Status DeQueue(LinkQueue &Q, QElemType &e)
{
    if (Q.front == Q.rear) return ERROR;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) Q.rear = Q.front;
    delete p;
    return OK;
}

取队头元素

QElemType GetHead(LinkQueue Q)
{
    if (Q.front != Q.rear)
        return Q.front->next->data;
}

串、数组和广义表

串

串 string （或字符串）由零个或多个字符组成的有限序列，一般记为

s = “a_ia₂ … a_n“ (n ≥ 0)

串中字符的数目 n 称为串的长度
零个字符的串称为空串 null string ø

串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串
通常称字符在序列中的序号为该字符在串中的位置
两串相等，当且仅当两个串的值相等

由一个或多个空格组成的串 " " 称为 空格串 blank string

抽象类型定义

ADT String
{
    数据对象：D = {a_i | a_i∈CharacterSet, i = 1, 2, …, n, n≥0}
    数据关系：R1 = {(a_i-1, a_i) | a_i-1, a_i∈D, i = 2, …, n}
    基本操作：
        StrAssign(&T, chars)
            初始条件：chars 是字符串常量
            操作结果：生成一个其值等于 chars 的串 T
        StrCopy(&T, S)
            初始条件：串 S 已存在
            操作结果：由串 S 复制得串 T
        StrEmpty(S)
            初始条件：串 S 已存在
            操作结果：若 S 为空串，则返回 true，否则返回 false
        StrCompare(S, T)
            初始条件：串 S 和串 T 已存在
            操作结果：若 S > T，则返回值 > 0；若 S = T，则返回值 = 0；若 S < T，则返回值 < 0
        StrLength(S)
            初始条件：串 S 已存在
            操作结果：返回 S 的元素个数，称为串的长度
        ClearString(&S)
            初始条件：串 S 已存在
            操作结果：将 S 清为空串
        Concat(&T, S1, S2)
            初始条件：串 S1 和 S2 已存在
            操作结果：用 T 返回由 S1 和 S2 联接而成的新串
        SubString(&Sub, S, pos, len)
            初始条件：串 S 已存在，1 ≤ pos ≤ StrLength(S) 且 0 ≤ len ≤ StrLength(S) - pos + 1
            操作结果：用 Sub 返回串 S 的第 pos 个字符起长度为 len 的字串
        Index(S, T. pos)
            初始条件：串 S 和 T 已存在，T 是非空串，1 ≤ pos ≤ StrLength(S)
            操作结果：若主串 S 中存在和串 T 值相同的子串，则返回它在主串中 S 中第 pos 个字符之后第一次出现的位置；否则函数值为 0
        Replace(&S, T, V)
            初始条件：串 S T V 已存在，T 是非空串
            操作结果：用 V 替换主串 S 中出现的所有与 T 相等的不重叠的子串
        StrInsert(&S, pos, T)
            初始条件：串 S 和 T 已存在，1 ≤ pos ≤ StrLength(S) + 1
            操作结果：在串 S 的第 pos 个字符之前插入串 T
        StrDelete(&S, pos, len)
            初始条件：串 S 已存在，1 ≤ pos ≤ StrLength(S) - len + 1
            操作结果：从串 S 中删除第 pos 个字符起长度为 len 的子串
        DestroyString(&S)
            初始条件：串 S 已存在
            操作结果：串 S 被销毁
} ADT String

存储结构

顺序存储

// 定长
#define MAXLEN 255
typedef struct
{
    char ch[MACLEN + 1];
    int lenth;
} SString;

// 堆
typedef struct
{
    char *ch;
    int length;
} HString;

链式存储

#define CHUNKSIZE 80
typedef struct Chunk
{
    char ch[CHUNKSIZE];
    struct Chunk *next;
} Chunk;
typedef struct
{
    Chunk *head, *tail;
    int length;
} LString;

模式匹配算法

子串的定位运算通常称为串的 模式匹配 或 串匹配

BF 算法

分别利用计数指针 i 和 j 指示主串 S 和模式 T 中当前正待比较的字符位置，i 初始值为 pos，j 初始值为 1
如果两个串均未比较到串尾，即 i 和 j 均分别小于等于 S 和 T 的长度时，循环之行
- S.ch[i] 和 T.ch[j] 比较，若相等，则 i 和 j 分别指示串中下个位置，继续比较后续字符
- 若不等，指针后退重新开始匹配，从主串的下一个字符 (i = i - j + 2) 起再重新和模式的第一个字符 (j = 1) 比较
如果 j > T.length，说明模式 T 中第一个字符相等的字符在主串 S 中的序号 (i - T.length)；否则称匹配不成功，返回 0

int Index_BF(SString S, SString T, int pos)
{
    i = pos; j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (S.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > T.length) return i - T.length;
    else return 0;
}

最好情况 O(m + n)
最坏情况 O(m * n)

KMP 算法

Knuth, Morris, Pratt 共同设计实现的
改进在于，每当一趟匹配过程中出现字符比较不等时，不需回溯 i 指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较

O(m + n)

数组

类型定义

类型相同
可以通过下标访问数据元素
当每个元素处于 n (n ≥ 1) 个关系中，称为 n 维数组

ADT Array
{
    数据对象: j_i = 0, ..., b_i - 1, i = 1, 2, ..., n, D = {a_{j₁j₂...j_n} | n (> 0) 称为数组的维数，b_i 是数组第 i 维的长度，j_i 是数组元素第 i 维的下标，a_{j₁j₂...j_n} ∈ Elemset}
    数据关系: R = {R1, R2, ..., Rn}
    基本操作:
        InitArray(&A, n, boundi, ..., doundn)
            操作结果：若维数 n 和各维长度合法，则构造相应的数组 A，并返回 OK
        DestroyArray(&A)
            操作结果：销毁数组 A
        Value(A, &e, indexl, ..., indexn)
            初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值
            操作结果：若各下标不超界，则 e 赋值为所指定的 A 的元素值，并返回 OK
        Assign(&A, e, indexl, ..., indexn)
            初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值
            操作结果：若下标不越界，则将 e 的值赋给所指定的 A 的元素，并返回 OK
} ADT Array

顺序存储

一旦建立了数组，结构中的数据元素个数和元素之间的关系就不再发生变动
在大部分语言中，都是以行序为主序的存储结构，而在如 FORTRAN 语言中，以列序为主序

LOC(i, j) = LOC(0, 0) + (n x i + j)L

特殊矩阵的压缩存储

对称矩阵
三角矩阵
对角矩阵
稀疏矩阵（较复杂

广义表

定义

线性表的推广，也称为列表
LS = (a₁, a₂, …, a_n)，其中 a_i可以是单个元素，也可以是广义表，分别称为广义表 LS 的原子和子表
习惯上，用大写字母表示广义表的名称，用小写字母表示原子

定义是一个递归的过程
重要结论：

广义表的元素可以是子表，子表的元素还可以是子表
广义表可以为其他广义表所共享（指可以不必列出子表的值，而是通过子表的名称来引用
广义表可以是一个递归的表，即可以是本身的一个子表

最重要的两个运算：

取表头 GetHead(LS): 取出的表头为非空广义表的第一个元素，可以是单原子，也可以是一个子表
取表尾 GetTail(LS): 取出的表尾为除去表头之外，由其余元素构成的表，即一定是一个广义表

() 和 (()) 不同

存储结构

通常采用链式存储结构

头尾链表的存储结构

表结点：标志域、指示表头的指针域、指示表尾的指针域
原子结点标志域、值域

typedef enum{ATOM, LIST} ElemTag;    // ATOM == 0: 原子, LIST == 1: 子表
typedef struct GLNode
{
    ElemTag tag;
    union
    {
        AtomType atom;
        struct
        {
            struct GLNode *hp, *tp;
        } ptr;
    }
} *GList;

除空表的表头指针为空外，对任何非空广义表，其表头指针均指向一个表结点，且该结点中的 hp 域指示广义表表头（或为原子结点，或为表结点），tp 域指向广义表表尾（除非表尾为空，则指针为空，否则必为表结点
容易分清列表中原子和子表所在层次
最高层的表结点个数即为广义表的长度

扩展线性链表的存储结构

无论是原子结点还是表结点均由三个域组成，原子结点增加一个 tp

树和二叉树

定义

树

树 Tree 是 n (n ≥ 0) 个结点的有限集，或为空树 (n = 0)，或为非空树
对于非空树 T：

有且仅有一个称之为根的结点
除根结点外的其余结点可分为 m (m > 0) 个互不相交的有限集 T₁, T₂, …, T_m，其中每个集合本身又是一棵树，并称为根的子树 SubTree

基本术语

结点：树中的一个独立单元，包含一个数据元素及若干指向其子树的分支
结点的度：结点拥有的子树数
树的度：树内各结点度的最大值
叶子：度为 0 的结点（或称为终端结点
非终端结点：度不为 0 的结点（或称为分支结点，除根结点外，非终端结点也称为内部结点
双亲和孩子：结点的子树的根称为该结点的孩子，相应的，该结点称为孩子的双亲
兄弟：同一个双亲的孩子之间互称兄弟
祖先：从根到该结点所经分支上的所有节点
子孙：以某结点为根的子树中的任一结点
层次：结点的层次从根开始定义起，根为第一层
堂兄弟：双亲在同一层的结点互为堂兄弟
树的深度：树中结点的从最大层次（或称为树的高度
有序树和无序树：从左到右是有次序的（不能交换），称为有序树，最左边的子树的根称为第一个孩子
森林：m (m ≥ 0) 棵互不相交的树的集合。对树中的每个结点而言，其子树的集合即为森林

就逻辑结构而言，任何一棵树都是一个二元组 Tree = (root, F)

二叉树

二叉树 Binary Tree 是 n (n ≥ 0) 个结点所构成的集合
对于非空树 T：

有且仅有一个称之为根的结点
除根结点之外的其余结点分为两个互不相交的子集 T₁ 和 T₂，分别称为 T 的左子树和右子树，且 T₁ 和 T₂ 本身又都是二叉树

与树的区别：

二叉树每个结点至多只有两颗子树（即不存在度大于 2 的结点
二叉树的子树有左右之分，其次序不能任意颠倒

抽象数据类型定义

ADT Tree
{
    数据对象：D 是具有相同特性的数据元素的集合
    基本操作：
        InitTree(&T)
            操作结果：构造空树 T
        DestroyTree(&T)
            初始条件：树 T 存在
            操作结果：销毁树 T
        CreateTree(&T, definition)
            初始条件：definition 给出树 T 的定义
            操作结果：按 definition 构造树 T
        Cleartree(&T)
            初始条件：树 T 存在
            操作结果：将树 T 清为空树
        TreeEmpty(T)
            初始条件：树 T 存在
            操作结果：若 T 为空树，则返回 true，否则 false
        TreeDepth(T)
            初始条件：树 T 存在
            操作结果：返回 T 的深度
        Root(T)
            初始条件：树 T 存在
            操作结果：返回 T 的根
        Value(T, cur_e)
            初始条件：树 T 存在，cur_e 是 T 中某个结点
            操作结果：返回 cur_e 的值
        Assign(T, cur_e, value)
            初始条件：树 T 存在，cur_e 是 T 中某个结点
            操作结果：结点 cur_e 赋值为 value
        Parent(T, cur_e)
            初始条件：树 T 存在，cur_e 是 T 中某个结点
            操作结果：若 cur_e 是 T 的非根结点，则返回它的双亲，否则函数值为空
        LeftChild(T, cur_e)
            初始条件：树 T 存在，cur_e 是 T 中的某个结点
            操作结果：若 cur_e 是 T 的非叶子结点，则返回它的最左孩子，否则返回空
        RightSibling(T, cur_e)
            初始条件：树 T 存在，cur_e 是 T 中某个结点
            操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则函数值为空
        InsertChild(&T, p, i, c)
            初始条件：树 T 存在，p 指向 T 中某个结点，1 ≤ i ≤ p 所指结点的度 +1，非空树 c 与 T 不相交
            操作结果：插入 c 为 T 中 p 所指结点的第 i 棵子树
        DeleteChild(&T, p, i)
            初始条件：树 T 存在，p 指向 T 中某个结点，1 ≤ i ≤ p 所指结点的度
            操作结果：删除 T 中 p 所指结点的第 i 棵子树
        TraverseTree(T)
            初始条件：树 T 存在
            操作结果：按某种次序对 T 的每个结点访问一次
} ADT Tree

ADT BinaryTree
{
    数据对象：D 是具有相同特性的数据元素的集合
    基本操作：
        InitBiTree(&T)
            操作结果：构造空二叉树 T
        DestroyBiTree(&T)
            初始条件：二叉树 T 存在
            操作结果：销毁二叉树 T
        CreateBiTree(&T, definition)
            初始条件：definition 出二叉树 T 的定义
            操作结果：按 definition 构造二叉树 T
        ClearBiTree(&T)
            初始条件：二叉树存在
            操作结果：将二叉树 T 清为空树
        BiTreeEmpty(T)
            初始条件：二叉树 T 存在
            操作结果：若 T 为空二叉树，则返回 true，否则 false
        BiTreeDepth(T)
            初始条件：二叉树 T 存在
            操作结果：返回 T 的深度
        Root(T)
            初始条件：二叉树 T 存在
            操作结果：返回 T 的根
        Value(T, e)
            初始条件：二叉树 T 存在，e 是 T 中某个结点
            操作结果：返回 e 的值
        Assign(T, &e, value)
            初始条件：二叉树 T 存在，e 是 T 中某个节点
            操作结果：结点 e 赋值为 value
        Parent(T, e)
            初始条件：二叉树 T 存在，e 是 T 中某个结点
            操作结果：若 e 是 T 的非根结点，则返回它的双亲，否则返回空
        LeftChild(T, e)
            初始条件：二叉树 T 存在，e 是 T 中某个结点
            操作结果：返回 e 的左孩子，若 e 无左孩子，则返回空
        RightChild(T, e)
            初始条件：二叉树 T 存在，e 是 T 中某个结点
            操作结果：返回 e 的右孩子，若 e 无右孩子，则返回空
        LeftSibling(T, e)
            初始条件：二叉树 T 存在，e 是 T 中某个结点
            操作结果：返回 e 的左兄弟，若 e 是 T 的左孩子或无左兄弟，则返回空
        RightSibling(T, e)
            初始条件：二叉树 T 存在，e 是 T 中某个结点
            操作结果：返回 e 的右兄弟，若 e 是 T 的右孩子或无右兄弟，则返回空
        InsertChild(&T, p, LR, c)
            初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树为空
            操作结果：根据 LR 为 0 或 1，插入 c 为 T 中 p 所指结点的左或右子树，p 所指结点的原有左或右子树则成为 c 的右子树
        DeleteChild(&T, p, LR)
            初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1
            操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树
        PreOrderTraverse(T)
            初始条件：二叉树 T 存在
            操作结果：先序遍历 T，对每个结点访问一次
        InOrderTraverse(T)
            初始条件：二叉树 T 存在
            操作结果：中序遍历 T，对每个结点访问一次
        PostOrderTraverse(T)
            初始条件：二叉树 T 存在
            操作结果：后序遍历 T，对每个结点访问一次
        LevelOrderTraverse(T)
            初始条件：二叉树 T 存在
            操作结果：层序遍历 T，对每个结点访问一次
} ADT BinaryTree

二叉树性质

在二叉树的第 i 层上至多有 2^{i - 1} 个结点 (i ≥ 1)
深度为 k 的二叉树至多有 w^k - 1 个结点 (i ≥ 1)
对任何一棵二叉树 T，如果其终端结点数 n₀，度为 2 的结点数为 n₂，则 n₀ = n₂ + 1

满二叉树：深度为 k 且含有 2^k - 1 个结点的二叉树
- 特点：
  - 每一层上的结点数都是最大结点数，即每一层 i 的结点数都具有最大值 2^{i - 1}
完全二叉树：深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应
- 特点：
  1. 叶子结点只可能在层次最大的两层上出现
  2. 对任一结点，若其右分支下的子孙的最大层次为 l，则其左分支下的子孙的最大层次必为 l 或 l + 1

具有 n 个结点的完全二叉树的深度为 ⌊log₂n⌋ + 1
如果对一棵有 n 个结点的完全二叉树的结点按层序编号，则对任一结点 i (1 ≤ i ≤ n) 有
1. 如果 i = 1，则结点 i 是二叉树的根，无双亲；如果 i > 1，则其双亲 PARENT(i) 是结点 ⌊i / 2⌋
2. 如果 2i > n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子 LCHILD(i) 是结点 2i
3. 如果 2i + 1 > n，则结点 i 无右孩子；否则其右孩子 RCHILD(i) 是结点 2i + 1

二叉树存储结构

顺序存储结构

1
2
3

#define MAXTSIZE 100
typedef TElemType SqBiTree[MAXTSIZE];        // 0 号单元存储根结点
SqBiTree bt;

仅适用于完全二叉树，因为在最坏的情况下，一个深度为 k 且只有 k 个结点的单支树（树中不存在度为 2 的结点）却需要长度为 2^k - 1 的一维数组

链式存储结构

二叉链表包含：

数据域
左右指针域

三叉链表增加一个指向双亲结点的指针域
在含有 n 个结点的二叉链表中有 n + 1 个空链域，可以利用这些空链域存储其他有用信息，从而得到线索链表

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

二叉树遍历和线索二叉树

遍历

traversing binary tree

先序遍历

若二叉树为空，则空操作；否则

访问根结点
先序遍历左子树
先序遍历右子树

中序遍历

若二叉树为空，则空操作；否则

中序遍历左子树
访问根结点
中序遍历右子树

后序遍历

若二叉树为空，则空操作；否则

后序遍历左子树
后序遍历右子树
访问根结点

中序遍历

递归算法

void InOrderTraverse(BiTree T)
{
    if (T)
    {
        InOrderTraverse(T->lchild);
        cout << T->data;
        InOrderTraverse(T->rchild);
    }
}

非递归算法

初始化一个空栈 S，指针 p 指向根结点
申请一个结点空间 q，用来存放栈顶弹出的元素
当 p 非空或者栈 S 非空时，循环执行以下操作：
- 如果 p 非空，则将 p 进栈，p 指向该结点的左孩子
- 如果 p 为空，则弹出栈顶元素并访问，将 p 指向该结点的右孩子

void InOrderTraverse(BiTree T)
{
    InitStack(S); p = T;
    q = new BiTNode;
    while (p || !StackEmpty(S))
    {
        if (p)
        {
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            Pop(S, q);
            cout << q->data;
            p = q->rchild;
        }
    }
}

时间空间都为 O(n)

先序遍历的顺序创建二叉链表

扫描字符序列，读入字符 ch
如果 ch 是一个 ‘#’ 字符，则表明该二叉树为空，即 T 为 NULL；否则执行以下操作
- 申请一个结点空间 T
- 将 ch 赋给 T->data
- 递归创建 T 的左子树
- 递归创建 T 的右子树

void CreateBiTree(BiTree &T)
{
    cin >> ch;
    if (ch == '#')
        T = NULL;
    else
    {
        T = new BiTNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

复制二叉树

如果是空树，递归结束，否则执行以下操作：

申请一个新结点空间，复制根结点
递归复制左子树
递归复制右子树

void Copy(BiTree T, BiTree &NewT)
{
    if (T == NULL)
    {
        NewT = NULL;
        return;
    }
    else
    {
        NewT = new BiTNode;
        NewT->data = T->data;
        Copy(T->lchild, NewT->lchild);
        Copy(T->rchild, NewT->rchild);
    }
}

计算二叉树深度

如果是空树，递归结束，深度为 0，否则执行以下操作：

递归计算左子树的深度记为 m
递归计算右子树的深度记为 n
如果 m 大于 n，二叉树的深度为 m + 1，否则为 n + 1

int Depth(BiTree T)
{
    if (T == NULL)
        return 0;
    else
    {
        m = Depth(T->lchild);
        n = Depth(T->rchild);
        if (m > n)
            return (m + 1);
        else
            return (n + 1);
    }
}

统计二叉树中结点的个数

int NodeCount(BiTree T)
{
    if (T == NULL)
        return 0;
    else
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

线索二叉树

如果有 n 个结点的二叉链表中必定存在 n + 1 个空链域，因此可以充分利用这些空链域来存放结点的前驱和后继信息

试做如下规定：
若结点有左子树，则其 lchild 域指示其左孩子，否则令 lchild 域指示其前驱
若结点有右子树，则其 rchild 域指示其右孩子，否则令 rchild 域指示其后继
为了避免混淆，需要改变结点结构，增加两个标志域，

lchild	LTag	data	RTag	rchild

其中

LTag =

0 lchild 域表示结点的左孩子
1 lchild 域表示结点的前驱

RTag 同理

typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild, *rchild;
    int LTag, RTag;
} BiThrNode, *BiThrNode;

线索链表：以这种结点结构构成的二叉链表
线索：其中指向结点前驱和后继的指针
线索二叉树 (Threaded Binary Tree)：加上线索的二叉树
线索化：对二叉树以某种次序遍历使其次序遍历使其变为线索二叉树的过程

树和森林

树的存储结构

双亲表示法

以一组连续的存储单元存储树的结点，每个结点除了数据域 data 外，还附设一个 parent 域用以指示其双亲结点的位置

孩子表示法

由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域

若不存储 degree，则多重链表中的结点是同构的。会有很多空链域，空间较浪费。一棵有 n 个结点度为 k 的树中必有 n(k - 1) + 1 个空链域
若存储 degree，则多重链表中的结点是不同构的。虽然节约存储空间，但操作不方便

另一种办法是，把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表做存储结构，则 n 个结点有 n 个孩子链表（叶子的孩子链表为空表）。而 n 个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构

数据结构 C语言版

绪论

基本概念

数据结构

逻辑结构

存储结构

数据类型和抽象数据类型

算法和算法分析

算法的特性

评价优劣的基本标准

时间复杂度

最好、最坏和平均时间复杂度

空间复杂度

线性表

定义和特点

类型定义

顺序表示

初始化

取值

查找

插入

删除

链式表示

初始化

取值

查找

插入

删除

创建

前插法

后插法

循环链表

双向链表

插入

删除

顺序表和链表的比较

空间性能

时间性能

线性表的应用

合并（去重）

合并（有序表 不去重）

顺序有序表

链式有序表

栈和队列

定义和特点

栈的表示和操作

顺序栈

初始化

入栈

出栈

取栈顶元素

链栈

初始化

入栈

出栈

取栈顶元素

栈与递归

队列的表示和操作

循环队列——队列的顺序表示和实现

初始化

求队列长度

入队

出队

取队头元素

链队——队列的链式表示和实现

初始化

入队

出队

取队头元素

串、数组和广义表

串

抽象类型定义

存储结构

顺序存储

链式存储

模式匹配算法

BF 算法

KMP 算法

数组

类型定义

合并（有序表不去重）