这是我关于数据结构课程的笔记。

1 绪论

1.1 基本概念和术语

1.1.1 数据

数据(data)：对客观事物的符号表示，在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素（data element）：数据的基本单位。在计算机中通常作为一个整体进行考虑喝处理。

数据项（data item）：是组成数据元素、有独立含义的、不可分割的最小单位。

数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集。

1.1.2 数据结构

数据结构（data structure）：相互之间存在一种或多种特定关系的数据元素的集合。

结构（structure）：数据元素相互之间的关系。

• 逻辑结构

  数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

  因此，数据的逻辑结构 可以看作是 从具体问题抽象出来的数学模型。

  四类基本结构：

  1. 集合 set：数据元素之间就是“属于同一个集合”
  2. 线性结构 list：数据元素之间存在着一对一的线性关系
  3. 树形结构 tree：数据元素之间存在者一对多的层次关系
  4. 图状结构 或 网状结构 graph：数据元素之间存在着多对多的任意关系

  

  

• 存储结构

  存储结构：数据结构在计算机中的表示（又称映像），数据的物理结构。包括数据元素的表示和关系的表示。

  在计算机中，表示信息的最小单位是二进制数的一位，叫做 位（bit）。计算机中，用一个由若干位组合起来形成的一个位串表示一个数据元素。通常称这个位串为元素（element）或结点（node）。当数据元素由若干个数据项组成时，位串中对应于各个数据项的子位串称为数据域（data field）。

  元素 或 结点 可以看成是数据元素在计算机中的映像。

  数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像 和 非顺序映像，并由此得到两种不同的存储结构：顺序存储结构 和 链式存储结构。（其实还有两种存储方式：索引存储（索引项：关键词、地址）、散列存储（结点地址 = F(关键字) ））

  • 顺序映像 的特点是：借助元素在存储器中的相对关系来表示数据元素之间的逻辑关系

  • 非顺序映像 的特点是：借助指示元素存储地址的 指针（pointer）来表示 数据元素之间的逻辑关系

数据存储原则：

• 不仅要存储数据本身的值，还要保存数据间的关系。
• 存储数据的目的是为了对它们进行处理。

• 数据的 逻辑结构 属于用户视图，是面向问题的，反映了数据内部的构成方式，数据的逻辑结构独立于计算机

• 数据的 物理存储结构 的实现要用计算机语言中的 数据类型 来描述，因而是依赖于具体的计算机语言而言的，是面向计算机的。

一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据存储的效率往往是不同的

1.1.3 数据的运算

数据的运算有两方面的含义：运算的定义与算法的实现

运算的定义：取决于数据的逻辑结构。根据问题中的数据及数据间的关系，设计相应的数据处理方法。

常见的运算操作：

• 初始化：对存储结构设置初始值，或者申请存储空间。
• 判空：判断存储空间是否为未存放有效值的状态
• 查找：判断是否包含指定元素
• 遍历：按某种次序访问所有元素，每个元素只被访问一次
• 插入：增加指定元素
• 删除：移去指定元素
• ……

1.1.3 数据类型和抽象数据类型

1. 数据类型

数据类型（data type）是 一个值的集合和定义在这个值集上的一组操作的总称。

2. 抽象数据类型

抽象数据类型（Abstract Data Type，简称 ADT）是指一个数学模型以及定义在该模型上的一组操作。

• 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

• 抽象数据类型，不仅包括各处理器已经定义及实现的数据类型，还包括用户自己定义的数据类型。

抽象数据类型具体包括三部分：数据对象、数据对象上关系的集合以及对抽象对象的基本操作

抽象数据类型的定义格式：

1
2
3
4
5

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

基本操作的定义格式：

1
2
3

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

1.2 算法和算法分析

1.2.1 算法

算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

算法的 5 个重要特性：

1. 有穷性：一个算法总是在执行有穷步之后结束，且每一步都可在 有穷时间 内完成。
2. 确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。而且，在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得到相同的输出。
3. 可行性：算法中所描述的操作都是可以通过已经实现的基本运算执行有限次来实现。
4. 输入：一个算法有零个或多个输入，这些输入来自某个特定的对象的集合
5. 输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量

1.2.2 算法设计的要求

• 正确性：指算法至少应该具有输入、输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案。
• 可读性：算法设计的另一个目的是为了方便阅读、理解和交流
• 健壮性：有成鲁棒性或容错性，是指算法对不合理输入的反应能力和处理能力。一个好的算法，应该能够识别出错误的输入数据并进行适当的处理和反应，而不是产生异常或莫名其妙的结果。
• 效率：具有 时间效率高 和 存储空间少 的要求。

1.2.3 算法的描述

• 自然语言描述 —— Pipeline Chart

  • 优点：容易理解
  • 限制：冗余、含糊
  • 用途：粗略地描述算法的目的

• 流程图 —— Pipeline Chart

  • 优点：步骤直观
  • 限制：缺乏严谨性和灵活性
  • 用途：描述简单的算法

• 编程语言 —— Programming Language

  • 优点：电脑可以运行
  • 显示：抽象性差，编程要求高
  • 用途：需要调试算法

• 伪代码 —— Pseudo Code

  介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。

  优点：表达能力强，抽象性强，容易理解

2 线性表

2.1 线性表的类型定义

线性结构的特点：

在数据元素的非空有限集中，

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

线性表是最常用且最简单的一种数据结构。一个线性表是 个数据元素的有限序列。

1
2
3

// 例子
(A,B,C,...,Z)  // 26 个英文字母的字母表，表中数据元素是单个字母字符
(6,17,28,50,92,188)  // 某校几年内拥有计算机数量变化，表中的数据元素是整数

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

例如，一个学校的学生健康情况登记表如图所示，表中每个学生的情况为一个记录，它由姓名、学号、性别、年龄、班级和健康状况等 6 个数据项组成。

【注】线性表的元素可以是各种各样的，但是在同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在序偶关系。

线性表是具有相同特性的数据元素的一个有限序列，例如：

有限序列的第一个元素叫做线性起点，每个元素的前面一个元素叫做 它的直接前趋，后一个元素叫做它的直接后继，序列的最后一个元素叫做线性终点。

线性表（Linear List）：由 个数据元素（结点） 组成的有限序列。

• 数据元素个数 定义为 线性表的长度
• 当 时称为空表
• 是第一个数据元素， 是最后一个数据元素， 是第 个数据元素，称 为数据元素 在线性表中的位序
• 将非空的线性表 记作：
• 这里的数据元素 只是一个抽象的符号，其具体含义在不同的情况下可以不同。

同一线性表中的元素必定具有相同的特性，数据元素间的关系是线性关系。

线性表的逻辑特征

非空的线性表中：

• 有且仅有一个开始结点 ，它没有直接前趋，而仅有一个直接后继
• 有且仅有一个终端结点 ，它没有直接后继，而仅有一个直接前驱
• 其余内部结点 都有且仅有一个直接前趋 和一个直接后继 。

线性表是一个相当灵活的数据结构，它的长度可以根据需要增加或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除。

顺序存储结构存在问题：

• 存储空间分配不灵活
• 运算的空间复杂度高

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

ADT List{
    数据对象:D = {ai | ai ∈ ElemSet, i = 1,2,..., m, n≥0}
    数据关系:R1 = {<a(i-1), ai | a(i-1), ai ∈ 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, compare())
        	初始条件：线性表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的数据元素，且不是最后一个，则用 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

例：合并两个线性表 LA 和 LB，从线性表 LB 中依次取每个数据元素，并依值在线性表 LA 中进行查访，若不存在，则插入之。

1
2
3
4
5
6
7
8
9
10
11

void union(List& La, List Lb)
{
    // 将所有在线性表 Lb 中但不在 La 中的数据元素插入到 Lb 中
    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);
    }
}  // union

时间复杂度：O(ListLength(LA)*ListLength(LB))

例：合并两个递增有序序列 LA 和 LB：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

void MergeList(List La, List Lb, List& Lc){
    // 已知线性表 La 和 Lb 中的数据元素按值非递减排列
    // 归并 La 和 Lb 得到新的线性表 Lc, Lc 的数据也按值非递减排列
    InitList(Lc);
    i = j = 1; k = 0;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    
    while((i<=La_len) && (i<=Lb_len)){
        GetElem(La, i, ai);
        GetElem(Lb, j, bj);
        if(ai <= bj){
            ListInsert(Lc, ++k, ai);
            ++i;
        }else{
            ListInsert(Lc, ++k, bj);
            ++j;
        }
    }
    
    while(i <= La_len){
        GetElem(La, i++, ai);
        ListInsert(Lc, ++k, ai);
    }
	while(j <= Lb_len){
        GetElem(Lb, j++, bj);
        ListInsert(Lc, ++k, bj);
	}
}  // MergeList

时间复杂度：O(ListLength(LA)+ListLength(LB))

2.2 线性表的顺序表示和实现

在计算机中，线性表有两种基本的存储结构：顺序存储结构 和 链式存储结构

线性表的顺序表示 指的是用 一组地址连续单元 依次存储 线性表的数据元素。

2.2.1 线性表的线性存储表示

线性表的顺序表示又称为顺序存储结构或顺序映像。

顺序存储定义：把逻辑上相邻的数据元素存储在物理相邻的存储单元中的存储结构。

• 依次存储，地址连续，中间没有空出存储单元。

• 线性表顺序存储结构占用一片连续的存储空间，知道某个元素的存储位置就可以计算其他元素的存储位置。

  假设线性表的每个元素需占 个存储单元，则第 个数据元素的存储位置和第 个数据元素的存储位置之间满足关系： 。

  由此所有数据元素的存储位置均可由第一个数据元素的存储位置得到： ，第一个元素的地址是基地址。

  每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。

• 线性表的顺序存储结构 是一种 随机存取的存储结构

2.2.2 线性表的实现

高级程序设计语言中的数组类型也有随机存取的特性，因此通常用数组来描述数据结构中的顺序存储结构。

顺序表的特点：以物理位置相邻表示逻辑关系。任一元素均可随机存取。（优点）

顺序表（元素）：地址连续、依次存放、随意存取、类型相同。

=> 可以用高级语言的 一维数组表示顺序表示。

线性表的表长可变（删除），数组长度不可动态定义。=> 用一个变量表示顺序表的长度属性

通用代码：

1
2
3
4
5
6
7

#define LIST_INIT_SIZE 100  // 线性表存储空间的初始分配量
#define LISTINCREMENT 10    // 线性表存储空间的分配增量
typedef struct{
    ElemType elem[LIST_INIT_SIZE];  // 存储空间的基地址
    int length;    // 当前长度 
    int listsize;  // 当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;

注意：上面代码的数组是静态分配的

数组动态分配：

1
2
3
4
5

typedef struct{
    ElemType* data; // 可以用内存动态分配来动态分配内存
    int length;
    int listsize;  
}SqList;   // 顺序表类型

1
2
3
4

SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);
// 释放指针 free(p)
//或者借助 C++ 语法： L.data = new ElemType[MaxSize]，释放地址：delete p 或 delete[] p

• 多项式的顺序存储结构类型定义

  ：

  => 线性表：P = ((p1,e1), (p2, e2), ..., (pm, em))

  1 2 3 4 5 6 7 8 9 10

  #define MAXSIZE 1000 // 多项式可能达到的最大长度 typedef struct{ // 多项式非零项的定义 float p; // 系数 int e; // 指数 }Polynomial; typedef struct{ Polynomial* elem; // 存储空间的基地址 int length; }SqList;

2.2.3 顺序表基本操作的实现

预定义常量和类型

1
2
3
4
5
6
7
8
9
10

// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
// Statue 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;

• 线性表的初始化

  1 2 3 4 5 6 7 8 9

  Status InitList_Sq(SqList& L) { // 构造一个空的线性表 L L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); // 存储分配失败 L.length = 0; // 空表长度为 0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq

• 元素的插入

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  Status ListInsert_Sq(SqList &L, int i, ElemType e){ // 在顺序线性表 L 中 第 i 个位置之前插入新的元素 e // i 的合法值为 1<= i <= ListLength_Sq(L)+1 if(i<1 || i>L.length+1) return ERROR; if(L.length >= L.listsize){ newbase = (ElemType*) malloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); // 分配地址失败 L.elem = newbase; // 新基址 L.listsize = LISTINCREMENT; // 增加存储容量 } 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; }// ListInsert_Sq

• 元素的删除

  1 2 3 4 5 6 7 8 9 10 11 12

  Status ListDelete_Sq(SqList &L, int i, ElemType &e){ // 在顺序线性表L中删除第 i 个元素，并用 e 返回其值 // i 的合法值为 1<= i <= ListLength_Sq(L) if((i<1) || (i>L.length)) return ERROR; // i 值不合法 p = &(L.elem[i-1]); // p 为被删除元素的位置 e = *p; // 被删除元素的值赋给 e q = L.elem + L.length - 1; // 表尾元素的位置 for(++p; p<=q; ++p) // 被删除元素之后元素左移 *(p-1) = *p; --L.length; // 表长减 1 return OK; } // ListDelete_Sq

若表长为 ，则算法 ListInsert_Sq 和 ListDelete_Sq 的时间复杂度为

• 找到满足 compare 关系的第一个元素

  1 2 3 4 5 6 7 8 9 10

  int LocateElem_Sq(SqList L, ElemType e, Status(* compare)(ElemType, ElemType)){ // 在顺序线性表 L 中查找第 1 个值与 e 满足 compare() 关系的位序 // 若找到，则返回其在 L 的位序，否则返回 0 i = 1; p = L.elem; while(i<=L.length && !(*compare)(*p++, e)) ++i; if(i <= L.length) return i; else return 0; } // LocateElem_Sq

• 合并递增有序顺序线性表

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  void MergeList_Sq(SqList La, SqList Lb, SqList &Lc){ // 已知顺序线性表 La 和 Lb 的元素按值非递减排序 // 归并 La 和 Lb 得到新的顺序线性表 Lc，Lc 的元素也按值非递减排列 pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length + Lb.length; pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType)); if(!Lc.elem) exit(OVERFLOW); // 存储分配失败 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++; // 插入 La 的剩余元素 while(pb <= pb.last) *pc++ = *pb++; // 插入 Lb 的剩余元素 } // MergeList_Sq

2.3 顺序表的链式表示和实现

链式存储结构，不要求逻辑上相邻的元素在物理位置也相邻，因此它没有顺序存储结构所具有的弱点（在插入或删除操作时，需移动大量元素），同时也失去了顺序表 随机存取 的优点。

2.3.1 线性链表

线性表的链式存储结构

• 特点：用一组 任意的存储单元 存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）
• 对于数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素 的 存储映像，称为 结点 (node)。它包括两个域：
  • 数据域：存储数据元素信息
  • 指针域：存储直接后继存储位置，指针域存储的信息称做 指针 或 链。
• 个结点( 的存储映像)链结成一个链表，即线性表 的链式存储结构。
• 此链表的每个结点只包含一个指针域，故又称 线性链表 或 单链表

整个链表必须从 头指针 开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为 “空” ()

• 用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像。
• 这种存储结构称为 非顺序映像 或 链式映像

2.3.2 线性链表的实现

单链表的描述：

1
2
3
4

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

• 设 L 是 LinkList 型变量，则 L 为单链表的头指针，它指向表中第一个结点。若 L 为 “空” (L = NULL) ，则所表示的线性表为 “空” 表，其长度 为 “零” 。

• 有时，在单链表的第一个结点之前附设一个结点，称之为头结点，头结点的数据域可以不存储任何信息，也可以存储诸如 线性表的长度等类的附加信息。头结点的指针域指向第一个结点的指针（即第一个元素结点的存储位置）。

  

  若线性表为空表，则头结点的指针域为 “空”

单链表是非随机存取的存储结构。

2.3.3 线性链表基本操作的实现

• 获取链表中的元素

  1 2 3 4 5 6 7 8 9 10 11 12 13

  Status GetElem_L(LinkList L, int i, ElemType & e){ // L 为带头结点的单链表的头指针 // 当第 i 个元素存在时,其值赋给 e 并返回 OK,否则返回 ERROR p = L->next; j = 1; // 初始化, p 指向第一个结点, j 为计数器 while(p && j<i){ // 顺指针向后查找, 知道 p 指向第 i 个元素或 p 为空 p = p->next; ++j; } if(!p || j>i) return ERROR; // 第 i 个元素不存在 e = p->data; // 取 第 i 个元素 return OK; } // GetElem_L

• 插入元素

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  Status ListInsert_L(LinkList & L, int i, ElemType e){ // 在带头结点的单链表线性表 L 中第 i 个位置之前插入元素 e p = L; j = 0; while(p->next && j<i-1){ // 寻找第 i-1 个结点 p = p->next; ++j; } if(!p || j > i-1) return ERROR; // i 小于 1 或者大于表长加 1 s = (LinkList)malloc(sizeof(LNode)); // 生成新结点 s->data = e; s->next = p->next; p->next = s; return OK; } // ListInsert_L

• 删除结点

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  Status ListDelete_L(LinkList &L, int i, ElemType & e){ // 在带头结点的单链线性表L中,删除第 i 个元素,并用 e 返回其值 p = L; j = 0; while(p && j<i-1){ // 寻找第 i-1 个结点 p = p->next; ++j; } if(!p || j>i-1) return ERROR; // i 小于 1 或者大于表长加1 q = p->next; p->next = p->next->next; e = q->data; free(q); return OK; } // ListDelete_L

• 插入和删除操作，复杂度均为 ，因为查找第 i-1 个结点的复杂度为

• 逆向建立链表

  1 2 3 4 5 6 7 8 9 10 11

  void CreateList_L(LinkList &L, int n){ // 逆位序输入 n 个元素的值，建立带表头结点的单链线性表 L L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; for(i = n; i>0; --i){ p = (LinkList)malloc(sizeof(LNode)); // 生成新的结点 scanf(& p->data); p->next = L->next; L->next = p; } } // CreateList_L

• 合并两个有序链表（非递减序列）

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  void MergeList_L(LinkList & La, LinkList & Lb, LinkList & Lc){ // 已知单恋线性表 La 和 Lb 的元素按值非递减排列 // 归并 La 和 Lb 得到新单链线性表 Lc, Lc 的元素也按值非递减排列 pa = La->next; pb = Lb->next; Lc = pc = La; // 用 La 的头结点组为 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; // 插入剩余段 free(Lb); // 释放 Lb 的头结点 }

2.3.4 静态链表

1
2
3
4
5
6

// 线性表的静态单链表存储结构
#define MAXSIZE 1000
typedef struct{
    ElemType data;
    int cur;  // 游标,代替指针指示结点在数组中的相对位置
}component, SLinkList[MAXSIZE];

这种存储结构需要预先分配一个较大的空间，但在线性表的插入和删除操作时不需要移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。下面展示 插入元素 "SHI" 和 删除元素 "ZHENG" 之后的状况。

假设 S 为 SLinkList 变量，则 S[0].cur 指示第一个结点在数组中的位置，若设 i = S[0].cur ，则 S[i].data 存储线性表的第一个数据元素。若第 i 个分量表示链表的第 k 个结点，则 S[i].cur 指示第 k+1 个结点的位置。因此在静态链表中，以整型游标 i 代替动态指针 p。i = S[i].cur 实为指针后移（类似 p=p->next）

需要自己实现 malloc 和 free 这两个函数。为了辨明数组中哪些分量未被使用，解决办法是将所有未被使用过以及被删除的分量用游标链成一个备用链表，每当插入时，便可从备用链表取第一个结点作为待插入的新结点。反之，在删除时将从链表中删除下来的结点链接到备用链表上。

• 初始化静态链表

  1 2 3 4 5 6

  void InitSpace_SL(SLinkList &space){ // 将一维数组 space 中各分量链成一个备用链表，space[0].cur 为头指针 // “0” 表示空指针 for(i = 0; i<MAXSIZE-1; ++i) space[i].cur = i+1; space[MAXSIZE-1].cur = 0; } // InitSpace_SL

• 自定义 malloc 函数

  1 2 3 4 5 6 7 8

  int Malloc_SL(SLinkList & space){ // 将一维数组 space 中各分量链成一个备用链表, space[0].cur 为头指针 // '0' 表示空指针 i = space[0].cur; if(space[0].cur) space[0].cur = space[i].cur; // 将备用链表的头指针指向备用链表中第一个节点的下一个节点。这样，备用链表中的第一个节点被分配出去，不再是备用节点。 return i; } // Malloc_SL

• 自定义 free 函数

  1 2 3 4 5

  void Free_SL(SLinkList &space, int k){ // 将下标为 k 的空闲结点回收到备用链表 space[k].cur = space[0].cur; // 回收结点的指针域指向现在链表第一个结点 space[0].cur = k; // 头结点指针域指向回收结点 } // Free_SL

• 建立结合 (A_B)⋃(B-A) ：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

  void difference_SL(SLinkList &space, int& S){ //依次输入集合 A 和 B 的元素,在一维数组 space 中建立表示集合(A_B)⋃(B-A) // 的静态链表,S 为其头指针。假设备用空间足够大,space[0].cur 为其头指针 InitSpace_SL(space); // 初始化备用空间 S = Malloc_SL(space); // 生成 S 的头结点 r = S; // r 指向 S 的当前最后结点 scanf(m, n); // 输入 A 和 B 的元素个数 for(j = 1; j<=m ;++j){ // 建立集合 A 的链表 i = Malloc_SL(space); // 分配结点 scanf(space[i].data); // 输入 A 的元素值 space[r].cur = i; // 插入到表尾 r = i; } // 尾结点的指针为空 space[r].cur = 0; // 尾结点的指针为空 for(j = 1; j<=n; ++j){ // 依次输入 B 的元素，若不在当前表中，则插入，否则删除 scanf(b); p = S; k = space[S].cur; // k指向集合 A 中的第一个结点 while(k != space[r].cur && space[k].data != b){ // 在当前表中查找 p = k; k = space[k].cur; } if(k == space[r].cur){ // 当前表中不存在该元素，插入在 r 所指结点之后 //且 r 的位置不变 i = Malloc_SL(space); space[i].data = b; space[i].cur = space[r].cur; space[r].cur = i; } else{ // 该元素在表中，删除之 space[p].cur = space[k].cur; Free_SL(space, k); if(r == k) r = p; // 若删除的是 r 所指结点，则需修改尾指针 } } }

  时间复杂度：

2.3.5 循环链表

循环链表（circular linked list） 是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针指向头结点，整个链表形成一个环。

因此，从表中任一结点出发均可找到表中其他结点。

在这种结构中，链表操作中的循环条件是 p->next 是否等于头指针。

有时候，在循环链表中设立尾指针而不设头指针，可以使得某些操作化简。例如两个线性表合并成一个表时，仅需将一个表的表尾和另一个表的表头相接。运算时间

2.3.6 双向链表

双向链表的结点有两个指针域，其一指向直接后继，另一指向直接前驱。C 语言中可描述如下：

1
2
3
4
5

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

双向链表中存在两个环，有 d->next->prior = d->prior->next = d

在双向链表中，有些操作：ListLength, GetElem 和 LocateElem 等仅需涉及一个方向的指针，则它们的算法描述和线性链表的操作相同。但在 插入、删除 时有很大的不同，在双向链表中需 同时修改两个方向上的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){
    // 在带头结点的双链循环线性表L中第i个位置之前插入元素 e
    // i 的合法值为 1≤i≤表长+1
    if(!(p = GetElemP_DuL(L,i)))  // 在 L 中确定插入位置
        return ERROR;              // p == NULL, 即插入位置不合法
    
    if(!(s = (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
    
    s->data = e;
    s->prior = p->prior; p->prior->next = s;
    s->next = p; p->prior = s;
    
    return OK
}  // ListInsert_DuL

1
2
3
4
5
6
7
8
9
10
11

Status ListDelete_DuL(DuLinkList &L, int i, ELemType &e){
    // 删除带头结点的双链循环线性表 L 的第 i 个元素，i的合法值 1≤i≤表长
    if(!(p = GetElemP_DuL(L, i)))  // 在 L 中确定第 i 个元素的位置指针 p
        return ERROR;   // p = NULL, 即第 i 个元素
    
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}  // ListDelete_Dul

链表有空间的合理利用上和插入、删除时不需要移动等优点。但，它也存在着实现某些基本操作，如求线性表的长度时不如顺序存储结构的缺点。另一个方面，由于在链表中，结点之间的关系用指针表示，则数据元素在线性表中的 “位序” 的概念已淡化，而被数据元素在线性链表中的 “位置” 所代替。

2.4 一元多项式的表示和相加

一元多项式 可按升幂写成： ，它由 个系数唯一确定。因此，在计算机里，它可用一个线性表 来表示： 每一项的指数 隐含在其系数 的序号里。

在处理多项式的次数可能很高且变化很大，例如 的多项式时，就要用长度为 20001 的线性表表示，浪费大量空间。

可以用一个长度为 每个元素有两个数据项（系数项和指数项）的线性表： 这样将到达节省空间。

利用 线性链表 可以更好地实现 改变多项式的系数和指数的运算。

抽象数据类型一元多项式的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

ADT Polynomial{
    数据对象: D = {ai|ai∈TermSet, i = 1,2,...,m,  m≥0
              TermSet 中每个元素都包含一个表示系数的实数和表示指数的整数}
    
    数据关系：R1 = {<a(i-1), ai>|a(i-1), ai ∈ D,且 a(i-1) 中的指数值 <ai 
        						  中指数值,i = 2,...,n}
    基本操作：
        CreatePolyn(&P, m)
        操作结果: 输入 m 项的系数和指数,建立一元多项式 P
        DestroyPolyn(&P)
        初始条件: 一元多项式 P 已存在
        操作结果: 销毁一元多项式 P
        PrintPolyn(P)
        初始条件: 一元多项式 P 已存在
        操作结果: 打印输出一元多项式 P
        PolynLength(P)
        初始条件: 一元多项式 P 已存在
        操作结果: 返回一元多项式 P中的项数
        AddPolyn(&Pa, &Pb)
        初始条件: 一元多项式 Pa 和 Pb 已存在
        操作结果: 完成多项式相加运算, 即 Pa = Pa+Pb,并销毁一元多项式 Pb
        SubtractPolyn(& Pa, & Pb)
        初始条件: 一元多项式 Pa 和 Pb 已存在
        操作结果: 完成多项式相减运算, 即 Pa = Pa-Pb,并销毁一元多项式 Pb
        MultiplyPolyn(&Pa, &Pb)
        初始条件: 一元多项式 Pa 和 Pb 已存在
        操作结果: 完成多项式相乘运算, 即 Pa = Pa×Pb,并销毁一元多项式 Pb
} ADT Polynomial

实现上述定义的一元多项式，显然应该采用链式存储结构。例如：表示多项式

利用有序链表实现 一元多项式。有序链表的基本操作定义 与 线性链表 有两处不同，一是 LocateElem 的职能不同，二是需要增加有序关系进行插入操作 OrderInsert：

1
2
3
4
5
6

Status LocateElem(LinkList L, ElemType e, Position &q,
                 int(*compare) (ElemType, ElemType));
// 若有序链表 L 中存在与 e 满足判定函数 compare() 取值为 0 的元素，则 q 指示 L中第一个值为 e 的结点的位置，并返回 TRUE，否则 q 指示第一个与 e 满足判定函数 compare() 取值 >0 的元素的前驱的位置，并返回 FALSE

Status OrderInsert(LinkList & L, ElemType e, int(* compare)(ElemType, ElemType));
// 按有序判定函数 compare() 的约定，将值为 e 的结点插入到有序链表 L 的适当位置

抽象数据类型 Polynomial 的实现：

1
2
3
4

typedef struct{
    float coef;  // 系数
    int expn;    // 指数
}term, ElemType;  //两个类型名: term 用于本 ADT, ElemType 为 LinkList 的数据对象名

基本操作算法描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int cmp(term a, term b)
    // 依 a 的指数值 < (或 = )(或 > ) b 的指数值，返回 -1,0,+1
    
void CreatePolyn(polynomial & P, int m){
    // 输入 m 项的系数和指数，建立一元多项式的有序链表 P
    InitList(P);
    h = GetHead(P);
    e.coef = 0.0; ex.expn = -1; SetCurElem(h, e);  // 设置头结点的数据元素
    for(i = 1; i<=m; ++i){  //依次输入 m 个非零项
        scanf(e.coef, e.expn);
        if(!LocateElem(P,e,q,(*cmp)())){       //当前链表中不存在该指数项
            if(MakeNode(s,e)) InsFirst(q, s);  // 生成结点并插入链表
        }
    }
} // CreatePolyn

多项式相加：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

void AddPolyn(polynomial & Pa, polynomial & Pb){
    // 多项式加法: Pa = Pa + Pb, 利用两个多项式的结点构成 "和多项式"
    ha = GetHead(Pa); hb = GetHead(Pb); // ha 和 hb 指向Pa 和 Pb 的头结点
    qa = NextPos(Pa, ha); qb = NextPos(Pb, hb);  // qa 和 qb 分别指向 Pa 和 Pb 中的当前结点
    while(qa && qb){
        a = GetCurElem(qa); b = GetCurElem(qb);  // a 和 b 为两表中当前比较元素
        switch( *cmp(a, b) ){
            case -1:   // 多项式 PA 中当前结点的指数值小
                ha = qa; qa = NExtPos(Pa, qa); 
                break;
            case 0:    // 两者的指数相等
                sum = a.coef + b.coef;
                if(sum != 0.0){  // 修改多项式 PA 当前的系数值
                    SetCurElem(qa, sum);  ha = qa;
                }else{  // 删除多项式 PA 中的当前结点
                    DelFirst(ha, qa);  FreeNode(qa);
                }
                DelFirst(hb, qa);  FreeNode(qb); 
                qb = NextPos(Pb, hb); qa = NextPos(Pa, ha); 
                break;
            case 1:   // 多项式 PB 中当前结点的指数值小
                DelFirst(hb, qb);  InsFirst(ha, qb);
                qb = NextPos(Pb, hb); ha = NextPos(Pa, ha);
                break;
        }
    }
    if(!ListEmpty(Pb)) Append(Pa, qb);  // 链表 Pb 中剩余结点
    FreeNode(hb); // 释放 Pb 的头结点
}

3 栈和队列

• 从 数据结构 角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是 操作受限的线性表 。因此，可称为限定性的数据结构。
• 从 数据类型 角度看，它们是和线性表大不相同的抽象数据类型。

3.1 栈

3.1.1 抽象数据类型栈的定义

栈 (stack) 是限定 仅在表尾进行插入或删除 的线性表。

• 表尾段称为 栈顶(top)，表头段称为栈底(bottom)。不含元素的空表称为空栈。
• 栈 是 后进先出 (last in first out) 的线性表 (简称 LIFO 结构)

栈的数据结构的抽象定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

ADT Stack{
    数据对象: D = {ai|ai∈TermSet, i = 1,2,...,n,  n≥0
              TermSet 中每个元素都包含一个表示系数的实数和表示指数的整数}
    
    数据关系：R1 = {<a(i-1), ai>|a(i-1), ai ∈ D,i = 2,...,n}
    		约定 an 为栈顶，a1 为栈底
    基本操作：
        InitStack(&S)
        操作结果：构造一个空栈S.
        DestroyStack(&S)
            初始条件：栈S已存在.
            操作结果：栈S被销毁.
        ClearStack(&S)
            初始条件：栈S已存在.
            操作结果：栈S清为空栈.
        StackEmpty(&S)
            初始条件：栈S已存在.
            操作结果：若栈S为空栈，则返回 TRUE，否则返回 FALSE.
        StackLength(&S)
            初始条件：栈S已存在.
            操作结果：返回S的元素个数，即栈的长度.
        GetTop(S, &e)
            初始条件：栈S已存在且非空.
            操作结果：用 e 返回 S的栈顶元素.
        Push(&S, e)
            初始条件：栈S已存在.
            操作结果：插入元素 e 为新的栈顶元素.
        Pop(&S, &e)
            初始条件：栈S已存在且非空.
            操作结果：删除S的栈顶元素，并用 e 返回其值.
        StackTraverse(S.visit())
            初始条件：栈S已存在且非空.
            操作结果：从栈底到栈顶依次对 S 的每个数据元素调用函数 visit().一旦visit()失败，则操作失败
            
}ADT Stack

3.1.2 栈的表示和实现

栈的两种存储表示方式：顺序栈 和 链栈 。

顺序栈，栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈的位置。通常以 top = 0 表示空栈。

设定两个常量STACK_INIT_SIZE(存储空间初始分配量)和 STACKINCREMENT (存储空间分配增量)，并以下述类型说明作为顺序栈的定义。

1
2
3
4
5

typedef struct{
    SElemType * base;
    SElemType * top;
    int stacksize;
}SqStack;

stacksize 指示栈的当前可使用的最大容量。

顺序栈的模块说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// ADT Stack 的表示和实现
// 栈的顺序存储表示
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
    SElemType * base;
    SElemType * top;
    int stacksize;
}SqStack;
// 基本操作的函数原型说明
Status InitStack(SqStack &S);
Status DestroyStack(SqStack &S);
Status ClearStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S, SElemType &e);
Status Push(SqStack &S, SElemType e);
Status Pop(SqStack &S, SElemType &e);
Status StackTraverse(SqStack S, Status(*visit)());

基本操作的算法描述（部分）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

Status InitStack(SqStack &S){
    // 构造一个空栈
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base) exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
} // InitStack

Status GetTop(SqStack S, SElemType &e){
    // 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK，否则返回 ERROR
    if(S.top == S.base) return ERROR;
    e = *(S.top - 1);
    return OK;
}  // GetTop

Status Push(SqStack &S, SElemType e){
    // 插入元素 e 为新的栈顶元素
    if(S.top - S.base >= S.stacksize){  // 栈满，追加存储空间
        S.base = (SElemType *)realloc(S.base, 
                 (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
        if(!S.base) exit(OVERFLOW); //存储分配失败
        S.top = S.base+S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
} // Push

Status Pop(SqStack &S,SElemType &e){
    // 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR
    if(S.top == S.base) return ERROR;
    e = * --S.top;
} //Pop

链栈：

共享栈：

3.2 栈的应用

3.2.1 数制转换

十进制数 N 和其他 d 进制数的转换。基本原理：

上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出一般是从高位到地位进行，伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

void conversion(){
    // 对于输入的任一个非负十进制整数，打印输出与其等值的八进制数
    InitStack(S);
    scanf("%d", N);
    while(N){
        Push(S, N%8);
        N /= 8;
    }
    while(!StackEmpty(s)){
        Pop(S,e);
        printf("%d",e);
    }
} // conversion

c++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

void conversion(){
    stack<int> stk;
    int N;
    cin >> N;
    while(N){
        stk.push(N%8);
        N /= 8;
    }
    while(!stk.empty()){
        cout << stk.top();
        stk.pop();
    }
}

3.2.2 表达式求值

四则运算求值 规则：（1）先乘除，后加减；（2）从左算到右；（3）先括号内，后括号外

设定任意两个相继出现的运算符 和 之间的优先关系，最多有以下三种关系： ， 的优先权低于 ；， 的优先权等于 ； ， 的优先权高于 。

为了实现算符优先算法，可以使用两个工作栈。一个称作 OPTR，用以寄存 运算符；另一个叫做 OPND，用于 寄存操作数或运算结果。算法基本思想：

（ 1 ）首先置操作数栈为空栈，表达式起始符 "#" 为运算符栈的栈底元素

（ 2 ）依次读入表达式中每个字符，若是操作数则进入 OPND 栈，若是运算符则和 OPTR 栈的栈顶运算符进行优先权 比较后进行相应运算操作。

（ 3 ）如此，直至整个表达式求值完毕 （即 OPTR 栈的栈顶元素和读入的字符均为 "#" ）

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

OperandType EvaluateExpression(){
    // 算术表达式求值的算符优先算法，设 OPTR 和 OPND 分别为运算符栈和运算数栈
    // OP 为运算符集合
    InitStack(OPTR);  Push(OPTR, '#');
    InitStack(OPND);  c = getchar();
    while(c! = '#' || GetTop(OPTR) != '#'){
        if(!In(c, OP)){ Push(OPND, c); c = getchar(); } // 不是运算符则进栈
        else
            switch(Precede(GetTop(OPTR), c)){
                case '<':  // 栈顶元素优先权低
                    Push(OPTR, c); c = getchar();
                    break;
                case '=':  // 脱括号并接受下一个字符
                    Pop(OPTR, x); c = getchar();
                    break;
                case '>':  // 退栈，将运算符结果入栈
                    Pop(OPTR, theta);
                    Pop(OPND, b);  Pop(OPND, a);
                    Push(OPND, Operate(a, theta, b));
                    break;       
            } // switch
    } // while
    return GetTop(OPND);
} // EvaluateExpression

3.3 栈与递归的实现

一个直接调用自己，或通过一系列调用语句间接地调用自己的函数，称做递归函数。

递归的应用

阶乘函数： 2 阶 数列：

3.3.1 n 阶汉诺塔问题

假设有 3 个分别命名为 X、Y 和 Z 的塔座，在塔座 X 上插有 个直径大小各不相同、依小到大编号为 1,2,···,n 的圆盘。要求将 X 轴上的 个圆盘移至塔座 Z 上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则： （ 1 ）每次只能移动一个圆盘；（ 2 ）圆盘可以插在 X、Y 和 Z 中的任一塔座上；（ 3 ）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。

如何实现移动圆盘操作：

• n = 1 时，只要将编号为 1 的圆盘从 塔座X 直接移动到 塔座 Z
• ，n > 1 时，需利用塔座 Y 作辅助塔座，若能设法将压在编号为 n 的圆盘之上的 n-1 圆盘从塔座 X 移动到 塔座 Y 上，则可先将 编号为 n 的圆盘从塔座 X 移至 塔座 Z，然后再将塔座 Y 上的 n-1 个圆盘（依照上述法则）移至塔座 Z 上。 而如何将 n-1 个圆盘从一个塔座移至另一个塔座是一个和原问题具有相同的特征属性的问题，指示问题规模小 1，因此可以用相同的方法求解。

算法实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void hanoi(int n, char x, char y, char z)
    // 将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘规则搬到
    // 塔座z上，y可用作辅助塔座
    // 搬动操作 move(x,n,z) 可定义为(c是初值为0的全局变量，对搬动计数)
    // printf("%i, Move disk %i from %c to %c\n", ++c, n, x, z);
{
    if(n == 1)
        move(x, 1, z);     // 将编号为 1 的圆盘从 x 移动到 z
    else{
        hanoi(n-1,x,z,y);  // 将 x 上编号为 1 到 n-1 的圆盘移到 y,z 作辅助塔
        move(x,n,z);       // 将编号为 n 的圆盘从 x 移到 z
        hanoi(n-1,y,x,z);  // 将 y 上编号为 1 至 n-1 的圆盘移到 z,x 作辅助塔
    }
}

3.3.2 递归函数运行实质

当在一个函数的运行期间调用另一个函数，在运行被调用函数之前，系统需先完成 3 件事：

• 将 所有的实在参数、返回地址 等信息传递 给被调用函数保存
• 为 被调用函数的局部变量 分配存储区
• 将 控制转移到被调函数的入口

从被调用函数返回调用函数之前，系统也应完成 3 件工作：

• 保存 被调函数的计算结果
• 释放 被调函数的数据区
• 依照 被调函数保存的返回地址 将控制转移到 调用函数

一个递归函数的运行过程 类似于 多个函数的嵌套调用，只是 调用函数 和 被调用函数 是同一个函数，因此，和每次调用相关的一个重要的概念是递归函数运行的 “层次” 。 假设调用该递归函数的主函数为 第 0 层，则从主函数调用递归函数为进入 第 1 层；从第 i 层递归调用本函数为 进入 “下一层”，即 i+1 层。反之，退出第 i 层递归则返回 i-1 层。

为保证 递归函数 正确执行，系统需设立一个 “递归工作栈” 作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括 所有的实在参数、所有的局部变量以及上一层的返回地址。 每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必定是递归工作栈栈顶的工作记录，称这个记录 “活动记录”，并称指示活动记录的栈顶指针为 “当前环境指针”。

3.4 队列

3.4.1 抽象数据类型队列的定义

队列（queue）是一种 先进先出（first in first out，缩写为 FIFO）的线性表。只允许在表的一端进行插入，而在另一端删除元素。允许插入的一端叫做 队尾（rear），允许删除的一端则称为 队头（front）。

队列的应用：操作系统中的作业排队。

队列的抽象数据类型定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

ADT Queue{
    数据对象: D = {ai|ai∈TermSet, i = 1,2,...,n,  n≥0}
    数据关系：R1 = {<a(i-1), ai>|a(i-1), ai ∈ D,i = 2,...,n}
    		约定 a1 段为队列头，an 段为队列尾
    基本操作：
        InitQueue(&Q)
            操作结果：构造一个空队列Q.
        DestroyQueue(&Q)
            初始条件：队列Q已存在.
            操作结果：队列Q被销毁，不再存在.
        ClearQueue(&Q)
            初始条件：队列Q已存在.
            操作结果：将Q清为空队列.
        QueueEmpty(Q)
            初始条件：队列Q已存在.
            操作结果：若Q为空队列，则返回TRUE,否则返回FALSE.
        QueueLength(Q)
            初始条件：队列Q已存在.
            操作结果：返回Q的元素个数，即队列的长度.
        GetHead(Q, &e)
            初始条件：队列Q已存在且非空.
            操作结果：用 e 返回 Q的队头元素.
        EnQueue(&Q, e)
            初始条件：队列Q已存在.
            操作结果：插入元素 e 为新的队尾元素.
        DeQueue(&Q, &e)
            初始条件：队列Q已存在且非空.
            操作结果：删除Q的队头元素，并用 e 返回其值.
        QueueTraverse(Q.visit())
            初始条件：队列Q已存在且非空.
            操作结果：从队头到队尾依次对 Q 的每个数据元素调用函数 visit().一旦visit()失败，则操作失败
}ADT Queue

双端队列是限定插入和删除操作在表的两端进行的线性表。这两段分别称为端点1和端点2。

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

队列有两种存储表示：链式存储和线性存储。

链队列，需要两个分别指示队头和队尾的指针（分别称为 头指针 和 尾指针）。为操作方便，给队列添加一个头结点，并令头指针指向头结点。

单链队列的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

typedef struct QNode{
    QElemType data;
    struct QNode * next;
}QNode, * QueuePtr;

typedef struct{
    QueuePtr front;  // 队头指针
    QueuePtr rear;   // 队尾指针
}ListQueue;

// 基本操作
Status InitQueue(LinkQueue &Q);
Status DestroyQueue(LinkQueue &Q);
Status ClearQueue(LinkQueue &Q);
Status QueueEmpty(LinkQueue Q);
int QueueLength(LinkQueue Q);
Status GetHead(LinkQueue Q, QElemType &e);
Status EnQueue(LinkQueue &Q, QElemType e);
Status DeQueue(LinkQueue &Q, QElemType &e);
Status QueueTraverse(LinkQueue Q, visit());

基本操作的算法描述（部分）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

Status InitQueue(LinkQueue &Q){
    // 构造一个空队列 Q
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

Status DestroyQueue(LinkQueue &Q){
    // 销毁队列 Q
    while(Q.front){
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    return Ok;
}

Status EnQueue(LinkQueue &Q, QElemType Q){
    // 插入元素 e 为 Q 的新的队尾元素
    p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data = e; p->next = NULL;
    Q.rear -> next = p;
    Q.reat = p;
    return OK;
}

Status DeQueue(LinkQueue &Q, QElemType &e){
    // 若队列不空，则删除 Q 的队头元素，用 e 返回其值，并返回 OK
    // 否则返回 ERROR
    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;  // 特殊情况，队列只有一个数据元素
    free(p);
    return OK;
}

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

• 在非空队列中，队首指针始终指向队头元素，而队尾指针始终指向队尾元素的下一个位置。

• 在顺序队列中存在 “假溢出” 现象。因为在入队和出队操作中，头、尾指针只增加不减少，导致删除元素的空间永远无法重新利用。

• 因此，尽管队列中实际元素个数可能远远小于数组大小，但可能由尾指针已超出数组空间的上界而不能做入队操作。这种现象称为假溢出。

  

为充分利用数组空间，克服上述“假溢出”现象的方法：将队列分配的数组空间看成一个首位相接的圆环，并称这种队列为 循环队列。

• 在循环队列中 进行出队、入队操作时，队首、队尾指针仍要加 1，朝前移动。只不过当队首、队尾指针指向数组上界（MAX_QUEUE_SIZE-1）时，其加 1 操作的结果是指向数组的下界 0：

  1 2	if(i+1 == MAX_QUEUE_SIZE) i = 0; else i++;

  其中 i 代表 队首指针或队尾指针

  可以用 模运算简化为 ：i = (i+1)%MAX_QUEUE_SIZE

• 入队时尾指针向前追赶头指针，出队时，头指针向前追赶尾指针，故队空和队满尾指针均相等。
• 因此无法通过 front = rear 来判断队列 “空” 还是 “满”。 解决方法：约定入队前，测试尾指针在循环意义下加 1 是否等于头指针，若相等则认为队满。即：
  • rear 所指的单元始终为空
  • 循环队列为空：front = rear
  • 循环队列满：(rear+1)%MAX_QUEUE_SIZE = front

循环队列 vs. 非循环队列

• 队列主要用于保存中间数据，而且保存的数据满足先产生先处理的特点。非循环队列可能存在数据假溢出，即队列中还有空间，可是队满的条件却成立了。为此，改为循环队列，这样克服了假溢出。
• 但并不能说循环队列一定优于非循环队列，因为循环队列中出队元素的空间可能被后来进队的元素占用，如果算法要求 队列操作结束后利用进队的所有元素实现某种功能，这样循环队列就不适合了，这种情况下就需要使用非循环队列。

3.4.4 优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，从队列头删除。

在优先队列中，每个元素都有一个优先级。具有最高优先级的元素最先出队。优先队列具有 最高级先出 的行为特征。优先队列执行的操作有 查找、插入一个新元素 和 删除 三种。

• 优先队列和普通队列都适用在处理或服务对象需要按序逐个进行操作的场合，不过 优先队列关心对象的优先级，将队列按 优先级顺序 作 出队 处理。

• 例子：

  • 操作系统的任务调度

    对操作系统而言，当有多个任务需要处理的时候，一般而言，解决这个问题的简单策略就是把任务放在一个队列中，先来者先服务，这是公平的，虽然对每个任务本身来说，都期望是能够被立即执行而不仅仅是被执行。 实际中会出现提交一个执行时间很短的任务可能要等很长的时间才能被执行的情形，因为在它之前已经有许多执行时间很长的任务，在队列中等待执行，这样会导致用户的使用感受不好。 解决此问题的一个策略是利用优先队列，按照“任务需要执行的时间越短，它的优先权越高”的原则，按任务的轻重顺序执行，可以使用户的平均等待时间最短。

  • 多媒体通讯网络中的数据包调度

  • 集合中的元素搜索

3.4.5 队列的应用

• 只要满足 先来先服务 特性的应用均可采用队列作为其数据组织方式或中间数据结构。
• 调度或缓冲：消息缓冲器、邮件缓冲器、计算机的硬件设备之间的通信也需要队列作为数据缓冲、操作系统的资源管理
• 广度优先搜索

回文串的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

bool Palindrome_Test(char * str)
    //判断输入的字符串是否回文序列，是则返回 true，否则返回 false
{
    InitStack(S);
    InitQueue(Q);
    for(char *c = str; *c != '\0'; c++){
        Push(S, *c);
        EnQueue(Q, *c);  // 同时使用栈和队列两种结构
    }
    while(!StackEmpty(S)){
        Pop(S, a);
        DeQueue(Q, b);
        if(a != b) return false;
    }
    return true;
}

用两个栈 S1 和 S2 模拟一个队列，写出入队和出队的算法（可用栈的基本操作）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Status EnQueue(DualStack &Q, QElemType e){
    if(!Q.StackFull(S1)) Q.push(S1, e);
    else if(Q.StackEmpty(S2)){
        while(!Q.StackEmpty(S1)) Q.Push(S2, Q.Pop(S1));
        Q.Push(S1, e);
	}
    else exit(OVERFLOW);
    return OK;
}

Status DeQueue(DualStack &Q, QElemType &e){
    if(!Q.StackEmpty(S1) || !Q.StackEmpty(S2)){
        if(!Q.StackEmpty(S2)) a = Q.Pop(S2);
        else{
            while(!Q.StackEmpty(S1)) Q.Push(S2, Q.Pop(S1));
            a = Q.Pop(S2);
        }
        return OK;
    }
    else exit(OVERFLOW);
}

4 串

4.1 串类型的定义

串 (string)(或字符串) 是由零个或多个字符组成的有限序列

• 一般记为 。其中， 是串的名，用双引号括起来的字符序列是串的值； 可以是 字母、数字或其他字符；
• 串中字符的数目 称为串的 长度。
• 零个字符的串称为 空串 (null string)，它的长度为零。用 表示 “空串”。
• 通常将仅由一个或多个空格组成的串称为 空白串（Blank String），注意 空串和空白串的不同。 "" 和 " " 分别表示长度为0的空串和长度为 1 的空白串。
• 串中 任意个 连续的字符 组成的子序列称为串的子串。包含子串的串相应地称为 主串。
• 通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
• 只有当两个串的长度相等，并且各个对应位置的字符都相等时两个串才相等
• 串值必须用一对双引号括起来。

字符串常数："\n"

字符串变量：a = "program"

串的逻辑结构和线性表极为相似，区别在于 串的数据对象约束为字符集。在串的基本操作中，通常以 “串的整体” 作为操作对象，例如在串中查找某个子串，求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。

串的抽象数据类型定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

ADT Queue{
    数据对象: D = {ai|ai∈TermSet, i = 1,2,...,n,  n≥0}
    数据关系：R1 = {<a(i-1), ai>|a(i-1), ai ∈ 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 返回串的第 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

串类型的 最小操作子集：

• 串赋值（StrAssign）
• 串比较（StrCompare）
• 求串长（StrLength）
• 串联结（Concat）
• 求子串（SubString）

字符（char）：组成字符串的基本单元，在C和C++中，字符占单个字节（8 bits），采用 ASCII码 对 128个符号（字符集 charset）进行编码。

标准字符串：将 C++ 的 <string.h> 函数库作为字符串数据类型的方案。例如char S[M] 字符串的结束标记：'\0' ，'\0' 是 ASCII 码中 8位全0码，又称 NULL符

函数库的字符串操作函数：

1
2
3
4
5
6
7
8
9
10
11
12

// 字符串长函数
int strlen(char* s);
// 字符串复制
char* strcpy(char* s1, char* s2);
// 字符串拼接
char* strcat(char* s1, char* s2);
// 字符串比较
int strcmp(char* s1, char* s2);
// 定位函数
char* strchr(char* s, char c);
// 逆定位函数
char* strrchr(char* s, char c);

4.2 串的表示和实现

串是一种特殊的线性表，存储方式取决于对字符串所进行的操作。字符串在计算机中有 3 种表示方式：

• 定长顺序存储表示：将字符串定义成字符数组，利用字符串名可以直接访问字符串值。用这种表示方式，字符串的存储空间在编译时确定，其大不能改变。
• 堆分配存储方式：仍然用一组地址连续的存储单元来依次存储字符串中的字符序列，但字符串的存储空间是在程序运行时根据字符串的实际长度动态分配的。
• 块链存储方式：是一种链式存储结构表示

4.2.1 定长顺序存储表示

用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组如下描述：

1
2
3
4
5
6
7

// 串的定长顺序存储表示
#define MAXSTRLEN 256   // 用户可在 255 以内定义最大串长
typedef struct
{
    char str[MAX_STRLEN];
    int length;
}StringType;

串的实际长度可以在这预定义长度范围内，超过预定义长度的串值则被舍弃，称之为 “截断”。

字符串的联结操作

1
2
3
4
5
6
7
8
9
10
11

Status StrConcat(StringType &s, StringType t)
{
    // 将字符串 t 联结到字符串s之后，结果仍然保存在s中
    if(s.length+t.length > MAX_STRLEN)
        return ERROR;  //联结长度超出范围
    for(i=0; i<t.length; i++){
        s.str[s.length+i] = t.str[i];  // 将字符串 t 联结到字符串之后
    }
    s.length = s.length+t.length;  // 修改联结后的字符串长度
    return OK;
}

求子串操作（已知位置）

1
2
3
4
5
6
7
8
9

Status SubString(StringType s, int pos, int len, StringType* sub){
    if(pos < 0 || pos > s.length || len < 0 || len > (s.length-pos+1))
        return ERROR;  // 参数非法
    
    sub->length = len-pos+1;  // 求得子串长度
    
    for(j = 0, k = pos; k<len; k++, j++)
        sub->str[j] = s.str[k];
}

4.2.2 堆分配存储表示

这种存储表示的特点，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。

实现方式：在 C 语言中，存在一个称之为 “堆” 的自由存储区，并由 C 语言的动态分配函数 malloc() 和 free() 来管理。利用函数 malloc() 为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向初始地址的指针，作为串的基址。

1
2
3
4
5

// 串的堆分配存储表示
typedef struct{
    char* ch;    // 若是非空串，则按串长分配
    int length;  // 字符串的长度
}HString;

字符串的联结操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Status StrConcat(HString &T, HString S1, HString S2){
    // 用 T 返回由 s1 和 s2 联结而成的串
   	if(T.ch) free(T.ch);
    t_len = S1.length+S2.length;
    if(!(T.ch = (char*)malloc(sizeof(char)*t_len))) exit(OVERFLOW);
    int pos = 0;
    for(i = 0; i<S1.length; i++){
        T.ch[pos++] = S1[i];
    }
    for(i = 0; i<S2.length; i++){
        T.ch[pos++] = S2[i];
	}
    return OK;
}

指定位置的字符串插入

1
2
3
4
5
6
7
8
9
10
11
12
13

Status StrInsert(HString &S, int pos, HString T){
    // 1<= pos <= StrLength(S)+1, 在串S的第pos个字符之前插入串T
    if(pos < 1 || pos > S.length+1) return ERROR;
    if(T.length){
        if(!(S.ch=(char* )realloc(S.ch, (S.length+T.length)*sizeof(char))))
            exit(OVERFLOW);
        for(i = S.length-1; i>=pos-1; --i)  // 为插入 T 而腾出位置
            S.ch[i+T.length] = S.ch[i];
        S.ch[pos-1 ... pos+T.length-2] = T.ch[0 ... T.length-1];   // 插入 T
        S.length+=T.length;
    }
    return OK;
}

ADT String 的表示和实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

// 串的堆分配存储表示
typedef struct{
    char * ch;
    int length;
}HString;

// 基本操作函数原型
Status StrAssign(HString &T, char* chars);
int StrLength(HString S);
int StrCompare(HString S, HString T);
Status ClearString(HString &S);
Status Concat(HString &T, HString S1, HString S2);
HString SubString(HString S, int pos, int len);

// 基础操作算法描述
Status StrAssign(HString &T, char* chars){
    // 生成一个其值等于串常量chars的串T
    if(T.ch) free(T.ch);  // 释放 T 原有空间
    for(i = 0, c = chars; c; ++i, ++c);  // 求chars的长度 i
    if(!i){T.ch = NULL; T.length = 0;}
    else{
        if(!(T.ch = (char*)malloc(i*sizeof(char)))) exit(OVERFLOW);
        T.ch[0 ... i-1] = chars[0 ... i-1];
        T.length = i;
    }
    return OK;
} // StrAssign

int StrLength(HString S){
    // 返回S的元素个数，称为串的长度
    return S.length;
}  // StrLength

int ClearString(HString &S){
    // 将 S 清为空串
    if(S.ch){free(S.ch);  S.ch = NULL;}
    S.length = 0;
    return OK;
} // ClearString

Status Concat(HString &T, HString S1, HString S2){
    // 用 T 返回由S1和S2联结而成的新串
    if(T.ch) free(T.ch);
    if(!(T.ch = (char*)malloc((S1.length + S2.length)*sizeof(char))))
        exit(OVERFLOW);
    T.ch[0 ... S1.length-1] = S1.ch[0 ... S1.length-1];
    T.length = S1.length + S2.length;
    T.ch[S1.length ... T.length-1] = S2.ch[0 ... S2.length-1];
    return OK;
} // Concat

Status SubString(HString &Sub, HString S, int pos, int len){
    // 用 Sub 返回串 S 的第pos个字符起长度为 len 的子串
    // 其中, 1<=pos<=StrLength(S) 且 0<=len<=StrLength(S)-pos+1
    if(pos < 1 || pos > S.length || len<0 || len.S.length-pos+1)
        return ERROR;
    if(Sub.ch) free(Sub.ch);
    if(!len){Sub.ch = NULL; Sub.length = 0;}
    else{
        Sub.ch = (char*)malloc(len*sizeof(char));
        Sub.ch[0 ... len-1] = S.ch[pos-1 ... pos+len-2];
        Sub.length = len;
    }
    return OK;
}

4.2.3 串的块链存储表示

可以采用 链表方式 存串值。结构中的每个数据元素是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。

串的块链存储表示：

1
2
3
4
5
6
7
8
9
10

#define CHUNKSIZE 80  // 可由用于定义的块大小
typedef struct Chunk{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;

typedef struct{
    Chunk * head, * tail;   // 串的头和尾指针
    int curlen;             // 串的当前长度
}LString;

串的存储密度： 存储密度小（如结点大小为1时），运算处理方便，然而，存储占用量大。如果在串处理过程中需要进行行内外存交换时，会因为内外存交换操作过多而影响处理的总效率。

4.3 串的模式匹配算法

4.3.1 求子串位置的定位函数 Index(S, T, pos)

子串的定位操作 通常称为 串的模式匹配（其中 T 称为 模式串），是各种串处理系统中最重要的操作之一。最朴素的模式匹配算法：

1
2
3
4
5
6
7
8
9
10
11

int Index(SString S, SString T, int pos){
    // 返回子串T在主串中第pos个字符之后的位置。若不存在，则函数值为0
    // 其中,T非空,1<=pos<=StrLength(S)
    i = pos-1; j = 0;
    while(i<S.length && j<T.length){
        if(S[i] == T[j]){++i; ++j; }  // 继续比较后继字符
        else{ i = i-j+2; j = 0;}  // 指针后退重新开始匹配
	}
    if(j > T[0]) return i-T.length;
    else return 0;
}

4.3.2 KMP算法

算法流程

假设现在文本串匹配到 i 位置，模式串 P 匹配到 j 位置

• 如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++, j++ ，继续匹配下一个字符
• 如果 j != -1 且当前字符匹配失败（即 S[i] != P[i]），则令 i 不变，j = next[j] ，这意味着模式串 P 相对于文本串 S 向右移动了 j-next[j] 位。

算法关键

• 寻找前缀和后最最长公共元素长度
• 求 next 数组
• 匹配失配的处理

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int KmpSearch(char* s, char* p)
{
    int i = 0, j = 0;
    int slen = strlen(s)， plen = strlen(p);
    while(i < slen && j < slen){
        if(j == -1 || s[i] == s[j]){
            i++, j++;
        }else{
            j = next[j];
        }
    }
    
    if(j == plen)
        return i-j;
    else 
        return -1;
}

求解 next 数组：

1
2
3
4
5
6
7
8
9
10
11
12
13

void GetNext(char* p, int next[]){
    int plen = strlen(p);
    int i = 0; j = -1;
    next[0] = -1;
    while(i<plen){
        if(j == -1 || p[i] == p[j]){
            i++, j++;
            next[i] = j;
        }else{
            j = next[j];
		}
    }
}