数据结构与算法基础

“程序=数据结构+算法”

——图灵奖获得者、Pascal语言之父Nicklaus Wirth

课程内容：

[TOC]

1 绪论

1.1 数据结构研究内容

“计算机主要用于数值计算时，一般要经过如下几个步骤：首先从具体问题抽象出数学模型，然后设计一个解此数学模型的算法，最后编写程序，进行测试、调试，直到解决问题。”

实例1.线性表
- 操作==对象==：每位学生的信息（姓名，性别……）。
  
  操作==算法==：查询，插入，修改，删除等。
实例2.树结构
- 操作==对象==：各种棋局状态，即描述棋盘的格局信息。
  
  操作==算法==：走棋，使棋局状态发生变化。
实例3.图结构
- 操作==对象==：各地点及路的信息。
  
  操作==算法==：设置信号灯，求出各个可同时通行的路的集合。

“ 从上面三个实例可以看出，非数值计算问题的数学模型不再是数学方程，而是诸如==线性表、树和图的数据结构==。因此，简单地说，数据结构是一门研究==非数值计算==程序设计中的操作对象，以及这些对象之间的==关系==和==操作==的学科。“

1.2 基本概念和术语

1.2.1 数据、数据元素、数据项和数据对象

数据：各种符号的集合
- 数值型的数据：整数、实数等
- 非数值型的数据：文字、图像、图形、声音等
数据元素^a ：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理

学号姓名性别出生日期政治面貌

0001 陆宇男 1986/09/02 团员

0002 李明男 1985/12/25 党员

0003 汤晓影女 1986/03/26 团员

其中第二行整体为一个数据元素^a ,其中包含了五个数据项
数据项：构成数据元素的不可分割的最小单位
- 数据>数据元素>数据项
  - 例：学生表>个人记录>学号
数据对象：是性质相同的数据元素的集合，是数据的一个子集^b
- 例：字母字符数据对象是集合C= {‘A’,‘B’, …，‘Z’,‘a’,‘b’, …，‘z’}
数据元素和数据对象
- 数据元素与数据的关系：集合的个体
- 数据对象和数据的关系：集合的子集

学号	姓名	性别	出生日期	政治面貌
0001	陆宇	男	1986/09/02	团员
0002	李明	男	1985/12/25	党员
0003	汤晓影	女	1986/03/26	团员

1.2.2 数据结构

数据结构
1. 数据元素之间的逻辑关系，也称为逻辑结构
2. 数据元素及其关系在计算机存储器中的表示（又称为映像），称为数据的物理结构或数据的存储结构
3. 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现
- 逻辑结构
  - 描述数据元素之间的逻辑关系
  - 与数据的存储无关，独立于计算机
  - 是从具体问题抽象出来的数学模型
- 物理结构（存储结构）
  - 数据元素及其关系在计算机存储器中的结构（存储方式）
  - 是数据结构在计算机中的表示
- 逻辑结构与存储结构的关系
  - 存储结构是逻辑关系的映象与元素本身的映象
  - 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
  - 两者综合起来建立了数据元素之间的结构关系
- 逻辑结构的种类
  - 划分方法一——两类结构
    - （1）==线性结构== ：有且仅有一个开始和一个终端节点，并且所有结点都最多只有一个直接前趋和一个直接后继
      
      例如：线性表、栈、队列、串
    - （2）==非线性结构==：一个节点可能有多个直接前驱和直接后继
      
      例如：树、图
  - 划分方法二——四类基本逻辑结构
    - （1）==集合结构==：数据元素之间除了 属于同一集合的关系外，别无任何其他关系。
      
      例如：确定一名学生是否为班级成员，只需将班级看做一个集合结构。
    - （2）==线性结构===结构中的数据元素之间存在着一对一的线性关系。
      
      例如：将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构
    - （3）==树形结构==：结构中的数据元素之间存在着一对多的层次**关系。
      
      例如：在班级的管理体系中，班长管理多个组长，每位组
      
      长管理多名组员，从而构成树形结构。
    - （4）==图状结构或网状结构==：结构中的数据元素之间存在着多对多的任意关系。
      
      例如：多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图状结构或网状结构。
- 存储结构的种类
  - 四种基本的存储结构：
    - 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
      
      在C语言中用数组来实现。
    - 链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。
      
      在C语言中用指针来实现。~~关于“指针”的痛苦回忆浮现出来力~~。:cry:
    - 索引存储结构：存储结点信息的同时，还建立附加的索引表
      
      例如：通讯录
    - 散列存储结构：根据结点的关键字直接计算出该结点的存储地址

1.2.3 数据类型和抽象数据类型

数据类型：在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量.常量或表达式，明确说明它们所属的数据类型^c。
- 例如C语言中：
  - 提供int，char, float, double等基本数据类型
  - 数组、结构、共用体、枚举等构造数据类型
  - 还有指针、空(void)类型
  - 用户也可用typedef 自己定义数据类型
- 一些最基本数据结构可以用数据类型来实现，如数组、字符串等;
- 而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。
- 数值类型的作用
  - 约束变量或常量的取值范围
  - 约束变量或常量的操作

抽象数据类型:是指一个数学模型以及定义在此数学模型上的一组操作。

由用户定义，从问题抽象出数据模型（逻辑结构）
还包括定义在数据模型上的一组抽象运算（相关操作）
不考虑计算机内的具体存储结构与运算的具体实现算法

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

ADT抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

}ADT 抽象数据类型名

其中：

数据对象、数据关系的定义用伪代码描述
基本操作的定义格式为：

基本操作名（参数表）

初始条件：<初始条件描述>

操作结果：<操作结果描述>

基本操作定义格式说明：

参数表：
1. 赋值参数只为操作提供输入值
2. 引用参数以&打头，除可提供输入值外，还将返回操作结果
初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足则操作失败，并返回相应出错信息。若初始条件为空，则省略之

操作结果：说明操作正常完成后，数据结构的变化情况和应返回的结果。

ADT大致结构：

ADT 抽象数据名{
    Data
        数据对象的定义
        数据元素之间的逻辑关系的定义
    Operation
        操作1
           初始条件
           操作结果描述
        操作2
            ……
        操作n
}ADT 抽象数据类型名

Circle的定义

ADT Circle{
  数据对象：D={r,x,y|rxy均为实数}
  数据关系：R={<r,x,y>|r是半径，<x,y>是圆心坐标}
  基本操作：
  Circle(&C,r,x,y)
         操作结果：构造一个圆
  double Area(C)
         初始条件：圆已存在
         操作结果：计算面积
  double Circumference(C)
         初始条件：圆已存在
         操作结果：计算周长
   ……
}ADT Cicle

复数的定义

ADT Complex{
    数据对象：D = {r1,r2|r1,r2都是实数}
    数据关系：S = { <r1,r2>|r1是实部，r2是虚部}
    基本操作：
        assign (&C,v1,v2)
        操作结果：构造复数Z，其实部和虚部，分别赋以参数V1,V2值
    destroy(&C)
        操作结果：复数Z被销毁
    getreal(C,&realPart)
        初始条件：复数已存在
        操作结果：用realpart返回复数Z的实部值。
    getlmag(C,&lmagPart)
        初始条件：复数已存在
        操作结果：用magPart返回复数Z的虚部值。
    add(C1,C2,&sum)
        初始条件：Z1,Z2是复数
        操作结果：sum返回两个复数Z1，Z2的和
}ADT Circle

以上代码均为类C语言作为描述工具

1.3 抽象数据类型的表示与实现

以下给出一个具体的实现过程

#include<stdio.h>
typedef struct complex{					//typedef起别名的，定义一个结构体变量struct[结构体名]结构体变量名：用[struct[结构体名]等价于int
    float realpart;						//实部
    float imagepart;					//虚部
}complex;								//typedef关键字把struct complex 起了个名字叫complex]
complex assign(float real,float image){	//构造复数
    complex c;
    c.realpart=real;
    c.imagepart=image;
    return c;
}
float getreal(complex c){				//取复数实部
    return c.realpart;
}
float getimage(complex c){				//取复数虚部
    return c.imagepart;
}
complex Add(complex c1,complex c2){		//求两复数c1与c2的和sum
    complex sum;
    sum.realpart=c1.realpart+c2.realpart;
    sum.imagepart=c1.imagepart+c2.imagepart;
    return sum;
}
int main(){								//主函数
    complex c1,c2,c3;
    c1=assign(1.0,2.0);
    c2=assign(3.0,4.0);
    c3=Add(c1,c2);
    printf("c1:%.2f+%.2fi\n",c1.realpart,c1.imagepart);
    printf("c1:%.2f+%.2fi\n",c2.realpart,c2.imagepart);
    printf("c1与c2的和为:%.2f+%.2fi\n",Add(c1,c2).realpart,Add(c1,c2).imagepart);
}

1.4 算法和算法分析

算法；对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。
算法的描述：
1. 自然语言：英语、中文
2. 流程图：传统流程图、NS流程图 // 软件工程没白学
3. 伪代码：类语言：类C语言
4. 程序代码：C语言程序，JAVA语言程序
算法与程序：
- 算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多个算法。
- 程序是用某种程序设计语言对算法的具体实现。
  
  程序=数据结构+算法

1.4.1 算法特性

有穷性：算法总在有穷步之后结束，且每一步在有穷时间内完成。
确定性：每个指令有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
输入：一个算法有零个或多个输入。
输出：一个算法有一个或多个输出。

1.4.2 算法设计的要求

正确性：
1. 程序中不含语法错误。
2. 程序对于几组输入数据能够得出满足要求的结果。
3. 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果。
4. 程序对于一切合法的输入数据都能得出满足要求的结。
可读性：主要为了人的阅读和交流，其次才是为计算机的执行，因此算法要易于人理解。
健壮性：指当输入非法数据时，算法算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。
高效性：花费尽量少的时间和尽量地的存储需求。

1.4.3 算法的时间复杂度

算法效率以下两个方面来考虑：
1. 时间效率：指的是算法所耗费的时间。
2. 空间效率，值算法执行过程中所耗费的存储空间。
  - 时间效率和空间效率有时是矛盾的。
时间效率的度量：
- 事后统计：将算法实现，测算其时间和空间开销。
  - 缺点：编写程序实现算法将花费较多时间与精力，所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣。
- 事前分析：对算法所消耗资源的一种估算方法。算法运行时间=一个简单操作*简单操作次数
  - 为了方便比较不同算法的时间效率，我们仅比较他们的数量级

for(i=1;i<=n;i++)							//n+1次
    for(j+1;j<=n;j++){						//n(n+1)次
        c[1][j]=0;							//n*n次
        for(k=0:k<n:k++)					//n*n*(n+1)次
            c[i][j]=c[i][j]+a[i][k]*b[k][j];//n*n*n次
    }

对于求解矩阵相乘问题，算法耗费时间：

$\large T(n)={2n^3}+{3n^2}+2n+1$

$n→∞$时，$T(n)/n3→2$,这表示n充分大时，$T(n)与n^3$是同阶或同数量级，引入大“O”记号，则T(n)可记作：
- $\large T(n)=O(n^3)$
- 原公式： $\large T(n)=O(f(n))$

分析算法时间复杂度的基本方法
1. 找出语句频度最大的那条语句作为基本语句
2. 计算基本语句的拼读得到问题规模$n$的某个函数$f(n)$
3. 取其数量级用符号“$O$”表示

x=0;y=0;
for(int k=0;k<n;k++)		//n+1次（这里是判断次数，所以要加一）
    x++;					//n次(这里是执行次数，所以不用加一)
for(int i=0;i<n:i++)		//n+1次
    for(int j=0;j<n;j++)	//n*(n+1)次
        y++;				//n*n次

$\large f(n)=n(n+1)$ $\large T(n)=O(n^2)$
- 可以直接看执行次数最多的语句，比如嵌套最深的语句

for(i=1:i<=n:i++)
    for(j+!;j<+i:j++)
        for(k=1;k<=j:k++)
            x=x+1

语句频度=$\large\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^n=\sum\limits_{i=1}^n\sum\limits_{j=1}^nj=\sum\limits_{i=1}^n\dfrac{i(i+1)}{2}=\dfrac{1}{2}(\sum\limits_{i=1}^ni^2+\sum\limits_{i=1}^ni)=v$
- 公式第一步是第三层嵌套，执行$\large j$次（$\large j$个1的和）
  - 公式第二步是求和公式$\large j$看做一个变量，从$\large j=1$到$\large i$一个等差数列求和直接套公式
    - 公式第三步一个平方和累加公式^d一个累加公式[^e]，轻易可得出结果
      - 直接抓大放小，可得$T(N)=O(n^3)$
分析以下程序段的时间复杂度
1
2
3
i=1;
while(i<=n)
i=i*2;
关键是找出来执行次数x与n的关系，并表示成n的函数

假设语句2执行x次，由循环条件$i<=n,所以2^x=n 所以x<=log_2n$

即$f(n)<=loglog_2n$,取最大值$f(n)=log_2n$

1.4.4 算法的空间复杂度

空间复杂度：算法所需存储空间的度量
- 记作:$\large S(n)=O(f(n))$

算法一：

for(i=0;i<=n/2;i++){
    t=a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=t;
}

算法二：

for(i=0;i<=n;i++)
    b[i]=a[n-i-1];
for(i=0;i<=n;i++)
    a[i]=b[i];

算法一：$\large S(n)=O(1)$ 原地工作

算法二：$\large S(n)=O(n)$

[^e]: $\large \sum\limits_{k=1}^nK=\dfrac{n(n+1)}{2}$

1.5 小结

数据结构是一门研究非数值计算程序设计中操作对象，以及这些对象之间的关系和操作。
数据结构包括两个方面的内容：数据的逻辑结构和存储结构。同一逻辑结构采用不同的存储方法可以得到不同的存储结构。
1. 逻辑结构是从具体问题抽象出来的数学模型，从逻辑关系上描述数据，它与数据的存储无关。根据数据元素之间关系的不同特性，通常有四类基本逻辑结构：集合结构、线性结构、树形结构和图状结构。
2. 存储结构是逻辑结构在计算机中的存储表示，有两类存储结构：顺序存储结构和链式存储结构。
抽象数据类型是指由用户定义的、表示应用问题的数学模型 ，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合，以及对数据对象的基本操作的集合。
算法是为了解决某类问题而规定的一个有限长的操作序列。算法具有五个特性：有穷性、确定性、可行性、输入和输出。一个算法的优劣应该从以下四方面来评价：正确性、可读性、健壮性和高效性。
算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度，以考察算法的时间和空间效率。一般情况下，鉴于运算空间较为充足，故将算法的时间复杂度作为分析的重点。算法执行时间的数量级称为算法的渐近时间复杂度，$T(n) = 0(f(n) )$, 它表示随着问题规模n的增大，算法执行时间的增长率和.f(n)的增长率相同，简称时间复杂度。

2 线性表

“以下四章为线性结构相关的知识，同时本章是整个课程的重点与核心内容，也是其他后续章节的重要基础。”

2.1 线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列
$\large (a1,a2,a3,……a_i,a_{i+1},……,a_n)$ ~~也就是说数组就是线性表咯~~

其中数据元素的个数n定义为表的长度。

当n=0时称为空表。
将非空的线性表记作(a1,a2……，an)

可以看出线性表的逻辑特征是：

有且仅有一个开始结点$a1$，他没有直接前驱，而仅有一个直接后继$a2$。
有且仅有一个终端结点$a_n$，他没有直接前驱，而仅有一个直接前驱$a{n-1}$。
其余内部结点都有且仅有一个直接前驱和一个直接后继。

2.2 案例引入

2.2.1 一元多项式的运算

$\large P_n(x)=p_0+p_1x+p_2x^{2}+……+p_nx^n$ $\large Q_n(x)=q_0+q_1x+q_2x^{2}+……+q_nx^n$

其中$\large p_x和\large q_x$是系数
- 那么两个多项式相加的结果$R_n(x)=P_n(x)+Q_m(x)$可用线性表R表示：
  - $\large R=(p_0+q_0,p1+q1,p2+q2+……+p_n+q_n)$

2.2.2 稀疏多项式的运算

$\large S(x)=1+3x^{10000}+2x^{20000}$

仅记录系数不为零的系数即可，这样可以大大节省空间。

线性表A：(7,0)、(3,1)、(9,8)、(5,7)

线性表B：(8,1)、(22,7)、(-9,8)

创建一个新数组C
分别从头比较A、B的每一项 PS：就是相当于走一遍一元多项式运算的步骤
- 指数相同：对应系数相加，若其和不为零，则在C中增加一个新项
- 指数不相同：则将指数较小的项复制到C中
- 一个线性表添加完后，将另一个线性表剩余项依次复制到C中即可

0	1	7	8	7
7	11	22	0	5

顺序结构存在的问题
1. 存储空间分配不灵活
2. 运算的空间复杂度高
由此引出了链式存储结构
- 不需要额外的操作空间

2.2.3 图书信息管理系统

将图书表抽象为线性表
表中每本图书抽象线性表中数据元素
具体实现，学完这一章就会了，暂时按下不表

总结：

线性表中数据元素的类型可以为简单类型，也可以为复杂类型。
许多实际应用问题所涉及的基本操作有很大相似性，不应为每个具体应用单独编写一个程序。
从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。

2.3 线性表的类型定义

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

PS: List是线性表的英文名

基本操作：
- InitList(&L) (Initialization List)
  操作结果：构造一个空的线性表L。
- DestroyList(&L)
  初始条件:线性表L已存在。
  操作结果：将L重置为空表。
- ListEmpty(L)
  初始条件：线性表L已存在。
  操作结果：若L为空表，则返回true, 否则返回false。
- ListLength(L)
  初始条件：线性表L已存在。
  操作结果：返回L中数据元素个数。
- GetElem(L,i,&e)
  初始条件：线性表L巳存在，且1:,s;i:os;ListLength(L)。
  操作结果：用e返回L中第1个数据元素的值。
- LocateElem(L,e)
  初始条件：线性表L已存在
  操作结果：返回L中第1个值与e相同的元素在 L中的位置。若这样的数据元素不存在，则返回值为0。
- PriorElem(r,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:,s;i:os;ListLength (L) +l。
  操作结果：在 L中第1个位置之前插入新的数据元素 e, L的长度加1。
- ListDelete(&L,i)
  初始条件：线性表L已存在且非空，且l:os;i:os;ListLength(L)。
  操作结果：删除L的第1个数据元素，L的长度减1。
- TraverseList(L)
  初始条件：线性表L已存在
  操作结果：对线性表L进行遍历，在遍历过程中对 L的每个结点访问一次。

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

2.4.1 线性表的顺序存储表示

线性表的顺序表示又称为顺序存储结构或顺序映像
- 顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构

线性表的第一个数据元素$a_1$的存储位置，称作线性表的起始位置或基地址

顺序表的特点：以物理位置相邻表示逻辑关系，任一元素均可随机存取。（优点）
- PS：必须是占用一片连续的存储空间，中间不存在空的存储单元
线性表类型定义的模版：

#define LIST_INIT_SIZE 100					//线性表存储空间的初始分配量
typedef struct{
    ElemType elem[LIST_INIT_SIZE];			//ElemType改成需要的元素类型，把他当做未知数x,根据题目需求而改变
    int length;								//当前长度
}SqList;

例一：多项式的顺序存储结构类型定义

#define MAXSIZE 1000		//多项式可能达到的最大长度
 typedef struct{			//多项式非零项的定义
     float p;				//系数
     int e;					//指数
 }Ploynomial;

typedef struct{
    polynomial *elem;		//存储空间的基地址
    int length;				//多项式中当前项的个数
}SqList;					//多项式的顺序存储结构类型为SqList

例二：图书表的顺序存储结构类型定义

#define MAXSIZE 10000
typedef struct{				//图书信息定义
    char no [20];			//图书的ISBN
    char name[50];
    float price;
}Book;

typedef struct{
    Book *elem;				//存储空间的基地址
    int length;				//图书表中当前图书个数
}SqList;					//图书表的顺序存储结构类型为SqList

补充：数组定义

数组静态分配

typedef struct{
    ElemType data[MaxSize];		
    int length;				
}SqList;					//顺序表类型

数组动态分配

typedef struct{
    ElemType *data;		
    int length;				
}SqList;					//顺序表类型

C语言的内存动态分配

SqList L；

L.data=(ElemType*^f)malloc(sizeof(ElemType)*MaxSize);

需要加载头文件：<stdlid.h>

传地址方式——指针变量做参数(c++)

#include<iostream.h>
void swap(float*m,float*n){
    float t:
    t=*m;
    *m=*n;
    *n=t;
}
void main(){
    float a,b,*p1,*p2;
    cin>>a>>b;						//cin>>输入的意思
    p1=&a; p2=&b;
    swap(p1,p2);	
    cout<<a<<endl<<b<<endl;			//endl换行的意思
}

传地址方式——数组名作参数

#include<iostream.h>
void sub(char b[]){
    b[]="world";
}
void main (void){
    char a[10]="hello";
    sub(a):
    cout<<a<<endl;			//结果为world
}

传地址方式——引用类型作参数

#include<iostream.h>
void main(){
    int i=5;
    int &j=i;					//i是本名；j是小名
    i=7;						//i值改变j值也会跟着改变
    cout<<"i="<<i<<"j="<<j;		//输出i=7 j=7
}

形参变化实参也发生变化
占有同一片区域

顺序表示意图

#define MAXSIZE 100
typedef struct{
    	ElemType *elem;
    int length;
}SqList;						//定义顺序表类型

$\large SqList$ $\large L$； //定义变量L，L是SqList这种类型的，L是个顺序表

2.4.2 顺序表的基本操作的实现

初始化线性表L

算法2.1 顺序表的初始化

elem指向这段空间的基地址
将表的当前长度设为0

Status lnitLIS_Sq(SqList &L){				//构造一个空的顺序表
	L.elem=new ElemType[MAXSIZE];			//为顺序表分配空间
	if(!L.elem)exit(OVERFLOW);				//存储分配失败
	L.length=0;								//空表长度为0
	retunrn OK;
}

销毁线性表L

1
2
3

void DestroyList(SqList &L){
    if(L.elem)delete L.elem:		//释放存储空间
}

清空线性表L

1
2
3

void ClearList(SqList &L){
    L.length=0;						//将线性表长度置为0
}

求线性表L的长度

1
2
3

int GetLength(SqList L){
    return(L.length);
}

判断线性表L是否为空

int IsEmpty(SqList L){
    if(L.length==0)return 1;
    else return 0;
}

取值

算法2.2 顺序表的取值
1. 根据指定的位置序号$\large i$，获取顺序表中第$\large i$个数据元素的值。
2. 若是$\large i$值合理，则将将第 $\large i $个数据元素 $\large L.elem[i-1]$赋给参数$\large e$, 通过$\large e$返回第 1 个数据元素的传值。
1
2
3
4
5
int GetElem(SqList L,int i,ElemType &e){
if(i<1||i>L.length)return ERROR: //i是序号，所以不能小于1
e=L.elem[i-1];
return OK
}
查找

算法2.3 顺序表的查找
1. 从第一个元素开始，往后找，查找成功返回该元素的序号i+1
2. 若找到最后还是没找到，则查找失败，返回0
1
2
3
4
5
int LocateELem(SqList L,ElemType e){
for(i=0;i<L.length;i++)
jif(L.elem[i]==e)return i+1; //查找成功返回i+1
return 0； //查找失败返回0
}
平均查找长度ASL ：在查找时，为确定元素在顺序表中的位置，需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度

$\large ASL=\sum\limits_{i=1}^nP_iC_i$ $P_i$是第i个记录被查找的概率 $C_i$是第i个记录需要比较的次数

$\large ASL=p_1+2p_2+3p_3+np_n=\dfrac{1}{n}(1+2+3+……+n)$ 每一个记录被查找的概率都相等是$\large p_i=\dfrac{1}{n}$

$ASL=\dfrac{1}{n}\dfrac{n(n+1)}{2}=\dfrac{n+1}{2}$

tips：这里和C语言的查找有着异曲同工之妙，还是要打好C语言的基础学这个就会轻松很多了

插入

算法2.4 顺序表的插入

看插入位置是否合法（1<=i<=n+1）,不合法则返回error
看顺序表存储空间是否已满，已满返回error
将第n干活到第i个位置元素一次后移一个位置
将e放入第i个位置
表长+1

status ListInsert(SqList &L,int i,ElemType e){
    if(i<=1||i>L.length+1)return ERROR;
    if(L.length==MAXSIZE)return ERROR;
    for(j=L.length-1;j>=i-1;j--)
        L,elem[j+1]=L.elem[j];				//元素后移
    L.elem[i-1]=e;							//赋值
    L.length++;								//表长加一
    return OK;
}

顺序表插入算法分析：$\large E_{ins}=\dfrac{1}{n+1}\sum\limits_{i=1}^{n+1}(n-i+1)=\dfrac{n}{2}$

i是第几个位置，x是移动次数，第1个移动n次，第2个移动n-1次最后一个移动0次，可发现$\large i+x=n+1$

所以顺序表插入算法的平均复杂度为$\large O(n)$ (前面最高次项的系数二分一是常数，删除了)

删除

算法2.5 顺序表的删除

判断位置i是否合法
将位置i后的元素一次前移
表长-1，删除成功返回OK、

status ListInsert(SqList &L,int i,ElemType e){
    if(i<=1||i>L.length+1)return ERROR;
    for(j=i.j<length-1;j++
         L,elem[j-1]=L.elem[j];				//元素前移
        L，length--;
        ruturn OK;
}

顺序表删除算法分析：$\large E_{del}=\dfrac{1}{n}\sum\limits_{i=1}^{n}(n-i)=\dfrac{n-1}{2}$

i是第一个移动n-1次，i是2移动n-2次,i是第n个移动0次，可发现$\large x=n-i$

2.5 线性表的链式表示和实现

通过上一小节的学习，我们不难发现顺序表的优点是任一元素均可随机存取。但他的缺点也很明显，在进行插入和删除操作时，需移动大量元素，存储空间不灵活

所有这些问题，都可以通过线性表的另一种表示方法——链式存储结构来解决。

再开始本章的学习之前，我们先了解一下什么是链表：
- 用一组物理位置任意的存储单元来存放线性表的数据元素。
- 这组存储单元既可以是连续的也可以是不连续的，甚至是零散分布在存储中任意位置上的。
- 链表中的元素的逻辑次序和物理次序不一定相同

其中姓名列为数据域，数据域是用来存储元素数值数据

后面的四位编码为指针域，用来存储直接后继结点的存储位置

我们可以通过头指针来命名单链表

与链式存储相关的术语
1. 结点：数据元素的存储映像。有数据域和指针域两部分组成
2. 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
单链表，双链表，循环链表
- 节点只有一个指针域的链表称为单链表或线性链表
- 结点有两个指针域的链表，称为双链表
- 首位相连的链表称为循环链表
头指针，头结点，首元结点（头指针>头结点>首元结点）
- 头指针：指向链表中第一个结点的指针
- 首元结点：存储第一个元素的结点
- 头结点：首元结点前附设的一个结点
  - 带头结点
  - 不带头结点

空表如何表示？

无头结点时，头指针为空

有头结点时，头结点指针域为空
多设置一个头结点有什么好处？
- 便于首元结点的处理
  
  结点是由结构体构造的，没有头结点的话，第一个数据元素的地址储存在头指针里，就没有储存在结构体里，操作上就和其他数据元素不同，而有了头结点，在链表里第一个位置的操作和其他位置一致，无须进行特殊处理
- 便于空表和非空表的统一处理
  
  结点是由结构体构造的，没有头结点的话，第一个数据元素的地址储存在头指针里，就没有储存在结构体里，操作上就和其他数据元素不同
- 头结点的数据域内装什么
  
  可以空着也可以存放线性表长度等附加信息，但该结点不能计入链表长度值
顺序表是随机存取法：找到要取的元素直接找他的位置就可以了

链表是顺序存取：只能从头指针进入链表，然后顺序扫描其余结点。

2.5.1 单链表的定义和表示

单链表的存储结构为：数据域|指针域 =》【data|next】
其中data什么类型取决于数据元素什么类型，如果处理的是学生表这种，比较复杂的数据类型，则通常定义为ElemType类型
next的类型取决于他存放的地址的数据元素是什么类型 比如存放的是int a=5,那么就是int *P

typedef struct Lnode{				//声明结点的类型和指向结点的指针类型
    ElemType data;					//结点的数据域
    struct Lnode *nmet;				//结点的指针域
}Lnode,*LinkList					//LinkList为指向结构体Lnode的指针类型

定义链表L：LinkList L；

定义结点指针P：LNode *P；

例如：有一个存储学生学号、姓名、成绩的单链表结点类型定义如下：

typedef Struct student{
    char num[8];
    char name[8];
    int score;						//以上三个数据域
    struct student *next;			//指针域
}Lnode,*LinkList;

这样写不常用，不方便不统一，通常用一下格式

typedef Struct{
    char num[8];
    char name[8];
    int score;
}ElemType;					//将存储的多个数据项定义为一个结构类型

typedef struct Lnode{
    ElemType data;			//用这个结构类型定义data
    struct 	Lnode *next;
}Lnode,*LinkList

2.5.2 单链表基本操作和实现（重点）

2.5.2.1 初始化

算法2.6 单链表的初始化

生成新结点作为头结点，用头指针L 指向头结点。
头结点的指针域置空。 =》【 |^】

Status lnitList_L(LinkList &L){
    L=new LNode；   //或L=(LinkList) malloc (sizeof (LNode))
    L->next=NULL;
    return OK;
}

补充单链表的几个常用简单算法：

判断链表是否为空

int ListEmpty(LinkList L){
    if(L->next)
        return 0;
    else
        return 1;
}

单链表的销毁

从头指针开始，依次释放所有结点

Status DestroyList_L(LinkList &L){		//销毁单链表P
    Lnode *p;							//或LinkLIst p
    while(L){							//L指向空停止循环
        p=L;							//把L的地址给p
        L=L->next;						//L指向下一个地址
        delete p;						//删除p所指的结点
    }
    return OK;
}

清空链表

依次释放所有结点，并将头结点的指针域设置为空

Status clearList_L(LinkList &L){			//将L重置为空表
    Lnode *p,*q;
    p=L->next;
    while(p){								//没到表尾
        g=p->next;
        delete p;
        p=q;
    }
    L->next=NULL; 							//头结点指针域为空
    return OK:
     
}

求链表表长

从首元结点开始，依次计数所有结点

int ListLength_L(LinkList L){			//LinkLIst定义的变量就是指针型的
    LinkList p:
    P=L->next;
    i=0;
    while(p){
        i++;
        p=p->next
    }
    return i;
}

重要知识点重温：

2.5.2.2 取值

算法2.7 取值 ——取链表中第i个元素的内容

从头开始，顺着链域往下搜索，指针后移且计数器x++直到x=i.

Status GetElem_L(LinkList L,int i, ElemType &e){
    p=L->next;i=1;					//初始化
    while(p&&j<i){					//向后扫，知道p指向第i个元素或p为空
        p=p->next;++j;
    }
    if(!p||j>i)return ERROR;		//第i个元素不存在
    e=p->data;
    return OK;
}//GetElem_L

2.5.2.3 查找

算法2.8 按值查找——根据指定数据获取改数据所在位置

从第一个结点开，依次和e比较
如果找到了与e值相等的数据元素，则返回其地址

没找到则返回0或NULL

Lnode *LocateELem_L (LinkList L, Elemtype e) {
    p=L->next;
    while(p&&p->data!=e)
        p=p->next;
    return p;
}

或者

int LocateELem_L(LinkList L, Elemtype e){
    p=L->next;i=1:
    while(p&&p->data!=e)
        {p=p->next;j++;}
    if(p)return j;				//没找到的话p指向空
    else return 0;
}

2.5.2.4 插入

算法2.9 插入——在第i个结点前插入值为e的新结点

找到结点i-1
建构新结点s

s->next=p->next；p->next=s；

Status Listlnsert_L(lLinkList &L,int i,ElemType e){
    p=L;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,数据域为e
    s->next=p->next;					//插入新结点
    p->next=s;
    return OK;
}//Listlnsert_L

2.5.2.5 删除

算法2.10 删除——删除第i个结点

找到结点i-1
p->next=p->next->next

释放结点i的空间

Status ListDelet_L(LinkList &L,int i,ElemType &e){
    p=L;j=0;q;i;
    while(p->next&&j<i-1){p=p-next;++j;}   	//找到i-1
    if(!(p->next)||j>i-1)return ERROR;		//删除位置不合理
    q=p->next;								//q指向要删除的结点
    p->next=q->next;						//是p指针next域指向删除域的下一个结点
    e=q->data;								//保存删除结点的数据域
    delete q;								//释放空间
    retun OK;
}

分析单链表查找，插入，删除算法的时间效率分析：

查找：应为只能顺序存取，即要从头指针开始找起，查找时间复杂度为$\large O(n)$
插入和删除：因为线性链表不需要移动元素，只用修改至臻，一般情况下的时间复杂度为$\large O(1)$

2.5.2.6 创建单链表

2.5.2.6.1 头插法——插到链表头部

L=new LNode;

L=（LinkList）malloc(sizeof(LNode));//C语言 //生成一个结点

p->data=$a_n$ //数据域赋值

p->next=L->next; L->next=p; //L指针域的空赋给p的指针域,L指针域指向p

void CreateList_H(LinkList &L,int n){
    L=new LNode;
    L->next=NULL;					//建立带头结点的单链表
    for(i=n;i>0;--i){
        p=（LNode*)malloc(sizeof（LNode));				//生成新结点
        scanf(&p->data);
        p->next=L->next;
        L->next=P:
    }
}

2.5.2.6.2 尾插法——插到链表尾部

从空表L开始，将新结点逐个插入到链表尾部，尾指针r指向链表的尾节点

初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。

void CreatList_R(LinkList &L,int n){
    L=new LNode;
    L->next=NULL;
    r=L;
    for(i=0;i<n;++i){
         p=（LNode*)malloc(sizeof（LNode));				//生成新结点
         scanf(&p->data);
        r->next=p;
        r=p;
    }
}

2.5.3 循环链表

循环链表：头尾相接的链表
- 优点：从表中任意结点出发均可找到表中其他结点
- 注意：终止条件为判断他们是否等于头指针
- 如果是头指针表示的单循环链表
  - 找$a_1$的时间复杂度：O(1)
  - 找$a_n$的时间复杂度：O(n)
- 若是尾指针表示的单循环链表
  - 找$a_1$的存储是：R->next->next 时间复杂度：O(1)
  - 找$a_n$的存储是：R 时间复杂度：O(1)

带尾指针循环链表的合并

p存表头结点将Tb表头连接到Ta表尾释放Tb表头结点修改指针
p=Ta->next ; Ta->next=Tb->next->next ; delete Tb->next ; Tb->next=p;

LinkList Connect(LinkList Ta,LinkList Tb){
    p=Ta->next;			//  an指向b1,没毛病，但是bn指向a头结点p就找不到了因为第一步你覆盖了an，所以an指向b1前，要利用an找到a头结点，bn指向bn的next
    Ta->next=Tb->next->next:
    delete Tb->next:
    Tb->next=p;
    return Tb;
}						//时间复杂度O(1)

2.5.4 双向链表

双向链表的结构可以定义如下：

typedef struct DuLNode{						//前面的Du是double双向的意思
    Elemtype         data;
    struct DuLNode   *prior,*next;          //一个指向前驱，一个指向后驱
}DuLNode,*DuLinkList;

双向循环列表
- 让头结点的前驱指针指向链表的最后一个结点
- 让最后一个结点的后继指针指向头结点
双向链表结构的对称性：
- $\large p->prior->next=p=p->next->prior$

算法2.13 双向链表的插入

void Listlnsert_DuL(DuLinkList &L, lnt i, ElemType e){
    //双向链表头结点指针L，第i个位置，值为e的元素
    if(!(p=GetElemP_DuL(L,i)))return ERROR;			//确定第i个元素的位置指针P
    S=new DuLNode;			s->date=e;
    s->prior=p->prior;		P->prior->next=s;
    s->next=p;				p->prior=s;
    return OK;
}//Listlnsert_DuL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

**算法2.14 双向链表的删除**

{% image https://pic.imgdb.cn/item/65364f0dc458853aef6a3b51.png %}

```c
void ListDelete_DuL(DuLinkList &L, lnt i, ElemType &e){
    //用e返回
    if(!(p=GetElemP_DuL(L,i)))return ERROR;			//确定第i个元素的位置指针P，顺着链表查找时间复杂度为O(n)
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    return OK;
}//ListDelete_DuL

单链表、循环链表和双向链表的时间效率比较

	查找表头结点（首元结点）	查找表尾结点	查找结点*p的前驱结点
带头结点的单链表L	L->next 时间复杂度O(1)	L->next依次向后遍历时间复杂度O(n)	通过p->next无法找到其前驱
带头结点仅设头指针L的循环单链表	L->next 时间复杂度O(1)	L->next依次向后遍历时间复杂度O(n)	通过p->next可以找到其前驱时间复杂度O(n)
带头结点仅设尾指针R的循环单链表	R->next 时间复杂度O(1)	R 时间复杂度O(1)	通过p->next可以找到其前驱时间复杂度O(n)
带头结点的双向循环链表L	L->next 时间复杂度O(1)	L-》prior 时间复杂度O(1)	p->prior 时间复杂度O(1)

2.6顺序表和链表的比较

链式存储结构的优点：
- 结点空间可以动态申请和释放
- 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素
链式存储结构的缺点：
- 存储密度小，每个结点的指针域需要额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
  - $\large 存储密度=\dfrac {结点数据本身占用的空间}{结点占用的空间总量}$
  - 链式存储结构是非随机存储结构。对任一结点的操作都要从头遍历，这增加了算法的复杂度

2.7 线性表的应用

2.7.1 线性表的合并

线性表的合并

问题描述：

假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=AUB

La=(7,5,3, 11) Lb=(2, 6, 3) ====》 La=(7, 5, 3, 11, 2, 6)
算法步骤：

从Lb中的每个元素,执行以下操作：
1. 在La中查找该元素
2. 如果找不到，则将其插入到La的最后

代码实现:

void union(List &La, List Lb){
    La_len=ListLength(La);
    Lb_len=ListLength(Lb);
    for(i=1;i<=Lb_len;i++){
        GetElem(Lb,i,e);
        if(!LocateElem(La,e))  Listlnsert(&La,++La_len,e);
    }
}

时间复杂度为La的长度乘以Lb的长度

2.7.2 有序表的合并

有序表的合并

问题描述：

已知线性表La 和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。
算法步骤：
1. 创建一个空表Lc
2. 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止
3. 继续将La或Lb其中一个表的剩余结点插入在Lc表的最后

用顺序表实现合并的代码实现：

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
    pa=LA.elem;		
    pb=LB.elem;										//指针pa和pb的初值分别指向两个表的第一个元素      
    LC.length=LA.length+LB.length;					//新表的长度等于两表长之和
    LC.elem=new ElemType[LC.length];				//为合并后的新表分配一个数组空间
    pc=LC.elem;										//指针pc指向新表第一个元素
    pa_last=LA.elem+LA.length-1;					//指针pa_last指向LA表的最后一个元素（基地址加上长度减一）
    pa_last=LB.elem+LB.length-1;					//指针pa_last指向LB表的最后一个元素（基地址加上长度减一）
	while(pa<pa_last&&pb<=pb_last){					//两个表都非空
    if(*pa<=*pb)*pc++=*pa++;						//依次“摘取”两表中值较小的结点
    else *pc++=*pb++;
	}
    while(pa<=pa_last) *pc++=*pa++;					//LB表已经到达表位，将LA中剩余元素加入LC
    while(pb<=pb_last) *pc++=*pb++;					//LA表已经到达表位，将LB中剩余元素加入LC
}//MergeList_Sq

用链表实现合并的代码实现：

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    pa=La->next; pb=Lb->next; 
    pc=Lc=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; //插入剩余段delete Lb;
    delete 	LB;
}

算法的时间复杂度是：O(ListLength(La)+ListLength(Lb)）

2.8案例分析与实现

案例2.1 一元多项式的运算：实现两个多项式加、减、乘、除运算 线性表

实现两个多项式相加运算

案例2.2：稀疏多项式的运算 链表

创建一个新数组C
分别从头遍历比较A和B的每一项
- 指数相同，系数相加，和若不为零，则在C中新加一项
- 指数不同，则将指数较小的项复制到C中
一个多项式已遍历完毕时，将另一个剩余项依次复制到C中即可

用顺序存储结构的话，存储空间分配不灵活，运算的空间复杂度高，所以我们常用链式存储结构

创建一个只有头结点的空链表。
根据多项式的项的个数n，循环n次执行以下操作:
1. 生成一个新结点*s;
2. 输入多项式当前项的系数和指数赋给新结点*s的数据域：
3. 设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱pre初值指向头结点;
4. 指针q初始化，指向首元结点;
5. 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q;
6. 将输入项结点s插入到结点q之前。

算法步骤：
1. 指针p1和p2初始化，分别指向Pa和Pb的首元结点
2. p3指向和多项式的当前结点，初值为Pa的头结点
3. 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值(p1->expn与p2->expn) 有下列3种情况:
  1. 当p1->expn==p2->expn时，则将两个结点中的系数相加
    1. 若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点
    2. 若和为零，则删除p1和p2所指结点;
  2. 当p1->expnexpn时，则应摘取p1所指结点插入到“和多项式”链表中去
  3. 当p1->expn>p2->expn时，则应摘取p2所指结点插入到“和多项式”链表中去
4. 将非空多项式的剩余段插入到p3所指结点之后
5. 释放Pb的头结点

案例2.3 图书信息管理系统 线性表或链表

3 栈和队列

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

3.1 栈和队列的定义和特点

栈和队列是两种常用的、重要的数据结构
栈和队列是限定插入和删除只能在表的端点进行的线性表
- 线性表可以删除任意位置
- 栈只能在表尾插入或删除（类似弹夹，后面对应名词压入弹出都能十分契合）
- 队列只能在表尾插入或表头删除（类似于排队，队头先走，人来了在队尾）
  - 特性：栈——后进先出
由于栈的操作具有后进先出的固有特性，使得栈成为程序设计中的有用工具
- 数制转换 表达式求值 括号匹配检验 八皇后问题
  
  行编辑程序 函数调用 迷宫求解 递归调用的实现
由于队列具有先进先出的特性，使得队列可以解决类似排位问题的有用工具
- 脱机打印输出：按申请的先后顺序依次输出
  
  多用户系统中，多个用户排成队，分时地循环使用CPU和主存，按用户的优先级排成多个队，每个优先级一个队列
  
  实时控制系统中，信号按接收的先后顺序依次处理
  
  网络电文传输，按到达的时间先后顺序依次进行

3.1.1 栈的定义和特点

栈的定义：是一种特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表
- 又称为后进先出的线性表，简称LIFO结构（Last in First Out）
- 表尾称为栈顶，表头称为栈底，插入元素到栈顶的操作，称为入栈（压入、进栈、压栈），从栈顶删除最后一个元素的操作，称为出栈（弹出、弹栈）
栈的逻辑结构：与线性表相同，仍为一对一关系。
栈的存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见
栈的运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则
栈的实现方式：关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同

3.1.2 队列的定义和特点

队列的定义：是一种先进先出的线性表，简称FIFO结构
- 只能插入到队尾，从队头删除
队列的逻辑结构：同线性表，仍为一对一关系。
队列的存储结构：顺序队或链队，以循环顺序队列更常见
队列的运算规则：只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则
队列的实现方式：关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同

3.2 案例引入

案例3.1：进制转换

十进制整数N向其他进制数d（二、八、十六）的转换是计算机实现计算的基本问题。

转换法则：除以d倒取余

该转换法则对应于一个简单算法原理：

*n=(n div d)d+n mod d

其中：div为整除运算，mod为求余运算
例：十进制把159转换成八进制

运用到栈的后进先出的特性

3.2.1：括号匹配的检验

假设表达式中允许包含两种括号：圆括号和方括号
检验（（）】）是否匹配

后进的括号与前面括号进行匹配，如果为相同括号的两边，则栈顶的左括号弹出，也符合后进先出的特性
- 若遇到一下集中情况之一，说明括号不匹配
  1. 遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；
  2. 当栈中弹出的左括号与当前检验的右括号类型不同，则说明出现了括号交叉情况；
  3. 表达式输入完毕后，但栈中还有没匹配的左括号，说明左括号多于右括号。

3.3.2：表达式求值

表达式求值是程序设计语言编译中一个最基本的问题，他的实现也需要运用栈
这里介绍的算法是由运算符优先级确定运算顺序的对表达式求值算法

——算符优先算法
- 表达式的组成
  - 操作数：常数、变量。
  - 运算符：算术运算符、关系运算符和逻辑运算符。
  - 界限符：左右括弧和表达式结束符。
- 任何一个算术表达式都由操作数、算术运算符和界限符组层。后两者统称为算符
  - 例如：#3*（7-2）#
    为了实现表达式求值。需要设置两个栈
    - 一个是算符栈OPTR，用于寄存运算符
    - 另一个称为操作数栈OPND，用于寄存运算数和运算结果
    求值的处理过程是自左至右扫描表达式的每一个字符
    - 当扫描到的是运算数，则将其压入栈OPND
    - 当扫描到的是运算符时
      - 若这个运算符比OPTR栈顶运算符的优先级高，则入栈OPTR，继续向后处理
      - 若这个运算符比OPTR栈顶运算符优先级低，则从OPND栈中弹出两个运算数，从栈OPTR中弹出栈顶运算符进行运算，并将运算结果压入栈OPND。
      - 继续处理当前字符，直到遇到结束符为止。

3.2.3：舞伴问题

舞会上男女各排一队，舞会开始从队头各出一人配成舞伴，如果两队初始人数不同，则较长那一队未配对者等待下一轮舞曲。
该问题具有典型的先进先出特性，可以用队列作为是算法的数据结构
- 首先构造两个队列
- 依次将队头元素出队配成舞伴
- 某队为空，则另外一队等待者为下一舞曲第一个可获得舞伴的人。

3.3 栈的表示和操作的实现

3.3.1 栈的抽象数据类型和类型的定义

基本操作：

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的每个数据元素进行访问。

3.3.2 顺序栈的表示和实现

有与栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现方式。
- 栈的顺序存储——顺序栈
- 栈的链式存储——链栈

存储方式：同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。

设top指针，指栈顶元素在顺序栈中的位置

另设base指针，指示栈底元素在顺序栈中的位置

但是为了方便操作，通常top指示真正的栈顶元素之上的下标地址

另外用stacksize表示栈可使用的最大容量

空栈：base==top是栈空的标志

栈满：top-base==stacksize

栈满时的处理方法：
1. 报错，返回操作系统。
2. 分配更大的空间
使用数组作为顺序栈存储方式的特点：
- 简单、方便、但容易产生溢出
  - 上溢：栈已满，又要压入元素
  - 下溢：栈已空，还要弹出元素
- 一般上溢是错误，下溢是一种结束条件，即问题处理已结束

顺序栈的表示

#define MAXSIZE 100
typeldef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

3.3.2.1 顺序栈的初始化

Status lnitStack(SqStack &S){				//构造空栈
	S.base=new SElemType[MAXSIZE]; 
    //或S.base=(SElemType*)malloc(MAXSIZE*sizeof（SElemType));
	if (!S.base)exit (OVERFLOW);			//存储分配失败
	S.top=S.base;							//栈顶指针等于栈底指针
	S.stacksize=MAXSIZE;
    return OK；
}

算法补充：顺序栈判断栈是否为空

Status StackEmpty（SqStack S){
    //若栈为空，返回TRUE否则返回FALSE
    if(S.top==S.base)
        return TRUE;
    else
        return FALSE;
}

算法补充：求顺序栈长度

1
2
3

int StackLength(SqStack S){
    return S.top-S.base;
}

算法补充：清空顺序栈

Status ClearStack(SqStack S){
    if (S.base)S.top=S.base;
    return OK;
}

算法补充：销毁顺序栈

Status DestroyStack(SqStack &S){
    if(S.base){
        delete S.base;
        S.stacksize=0:
        S.base=S.top=NULL;
    }
    return OK;,			
}

3.3.2.2 顺序栈的入栈

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

3.3.2.3 顺序栈的出栈

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

3.3.3 链栈的表示和实现

链栈是运算受限的单链表，只能在链表头部进行操作

typedef struct StackNode{
    SElemType data；
    struct StackNode *next；  
}StackNode,*LinkStack;
LinkStack S;

链表头结点就是栈顶
不需要头结点
基本不存在栈满的情况
空栈相当于头指针指向空
插入和删除仅在栈顶处执行

3.3.3.1 链栈的初始化

void lnit Stack(LinkStack &S){
    S=NuLL;
    return OK;
}

算法补充：判断链栈是否为空

Status StackEmptyl(LinkStack S){
    if(S==NULL)return TRUE;
	else return FALSE;
}

3.3.3.2 链栈的入栈

Status Push(LinkStack &S,SElemType e){
    p=new StackNode;	//生成新结点p
    p->data=e;			//将新结点数据域置为e
    p->nextg=S;			//将新结点插入栈顶
    S=p;				//修改栈顶指针
    return OK;
}

相当于头插法

3.3.3.3 链栈的出栈

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

3.3.3.4 取栈顶元素

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

3.4栈与递归

递归的定义
- 若一个对象部分地包含它自己，或用他自己给自己定义，则称这个对象是递归的
- 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。
  - 例如：递归求n的阶乘
    1
    2
    3
    4
    long Fact(long n){
    if(n==0)return 1;
    else return n*Fact(n-1);
    }
- 以下三种情况尝尝用到递归方法
  - 递归定义的数学函数
    - 阶乘函数
    - 二阶fibonaci数列
  - 具有递归特性的数据结构
    - 二叉树
    - 广义表
  - 可递归求解的问题
    - 迷宫问题
    - hanoi塔问题
- 递归问题——用分治法求解
  - 分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解
  - 必备的三个条件
    1. 能够将一个问题转变成一个新的问题，而新的问题与原问题解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
    2. 可以通过上述转化而使问题简化
    3. 必须有一个明确的递归出口或递归的边界

分治法求解递归问题算法的一般形式：

函数调用过程

调用前，系统完成：
1. 将实参，返回地址等传递给被调用函数
2. 为被调用函数的局部变量分配存储区
3. 将控制转移到被调用函数的入口
调用后，系统完成：
1. 保存被调用函数的计算结果
2. 释放被调用函数的数据区
3. 依照被调用函数保存的返回地址将控制转移到调用函数

递归的优缺点
- 优点：结构清晰，程序易读
- 缺点：每次调用都要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大
  
  递归->非递归
  1. 尾递归、单项递归->循环结构
  2. 自用栈模拟系统的运行时栈

3.5 队列的表示和操作的实现

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

3.5.2 队列的顺序表示和实现

队列的物理存储可以用顺序存储结构，也可以用链式存储结构。相应的队列的存储方式也分为两种，即顺序队列和链式队列
队列的顺序表示——用一维数组base[MAXQSIZE]

#define MAXQSIZE 100		//最大队列长度
Typedef struct{
    QElemType *base;		//初始化的动态分配存储空间
    int front;				//头指针
    int rear;				//尾指针
}SqQueue;

若front=0且rear=MAXQSIZE时，再入队——真溢出
若front不为0，rear=MAXQSIZE时，再入队——假溢出，此时队列中还有空间可以存放
- 解决假溢出可以吧队的空间想象成一个循环的表
  - 引入循环队列
    1. 实现方法：利用%运算
    2. 插入元素：Q.base[Q.rear]=x;
      
      Q.rear=（Q.rear+1)%MAXQSIZE;
    3. 删除元素：x=Q.base[s.front]
      
      Q.front=(Q.front+1)%MAXQSIZE
    4. 循环队列:循环使用为队列分配的存储空间。
因为队空队满都是：front==rear
- 所以我们常常另设一个标志来区别队空队满、另设一个变量，记录元素个数或者少用一个元素空间。
- 队满时——少用一个元素空间
  - 队空：front==rear
  - 队满：（rear+1)%MAXQSIZE

3.5.2.1 队列的初始化

Status InitQueue(SqQueue &Q){
    Q.base=(QElemType*)
    malloc(MAXQSIZE*sizeof（QElemType)）；
    if（!Q.base)exit(OVERFLOW);
    Q.fornt=Q.rear=0;
    return OK;
}

3.5.2.2 求队列的长度

1
2
3

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

3.5.2.3 循环队列入队

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;
}

3.5.2.4 循环队列出队

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

3.5.2.5 取队头元素

1
2
3

Status GetHead(SqQueue Q){
    if(Q.front!==Q.rear);
    return Q.base[Q.front];				//返回队头指针元素的值，队头指针不变

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

若用户无法估计所用队列长度，则宜采用链队列

链队的类型定义

#define MAXQSIZE 100 
typedef struct Qnode{
    QElemType data;
    stuct Qnode *next;
}QNode,*QueuePtr			//ptr是pointer的缩写
typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

3.5.3.1 链队的初始化

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

3.5.3.2 链队列的销毁

Status DestroyQueue(LinkQueue &Q){
    while(Q.front){
        p=Q.front->next;
        ferr(Q.front);
        Q.front=p;
    }
    return OK;
}

3.5.3.3 链队列的入队

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

3.5.3.4 链队列的出队

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;
}

3.5.3.5 链队列取队头

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

4 串、数组和广义表

4.1 串的定义——几个术语

串(String)——由零个或多个任意字符组成的有限序列

子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串
- 真子串，不包含自身的所有子串
字符位置：字符在序列中的序号为该字符在串中的位置
子串位置：子串第一个字符在主串中的位置
空格串：由一个或多个空格组成的串，与空串不同
- 计算他们的长度时，要包括空格
串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，两个串才是相等的。

4.2 案例引入

“串的应用非常广泛，计算机上的非数值处理的对象大部分是字符串数据，例如：文字编辑、符号处理、各种信息处理系统等等。”

4.2.1 病毒感染检测

研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列（字符串的匹配）

4.3 串的类型定义、存储结构及运算

4.3.1 串的抽象类型定义

4.3.2 串的存储结构

4.3.2.1 串的顺序存储结构

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN+1];
    int length;
}SString;

顺序存储结构用的更多一些

4.3.2.2 串的链式存储结构

如果是普通的链式存储的话，虽然方便操作，但是存储密度较低，所以在这里，我们将多个字符存放在一个结点中，以克服其缺点。

我们称之为——块链结构

#define CHUNKSIZE BO 					//可由用户定义的块大小
typedef struct Chunk{
    char ch [CHUNKSIZE];
	struct Chunk *next;
})Chunk;
typedef struct{ 
	Chunk *head,*tail; 					//串的头指针和尾指针
	int length; 						//串的当前长度	
) LString;								//字符串的块链结构

4.3.3 串的模式匹配算法

算法目的：
- 确定主串中所含子串（模式串）第一次出现的位置（定位）
算法应用：
- 搜索引擎、拼写检查、语言翻译、数据压缩
算法种类：
- BF算法（暴力破解，朴素的、穷举的）
- KMP算法（速度快）

4.3.3.1 BF算法

匹配失败：
- $\large i=(i-j+1)+1=i-j+2$(i和j走的路程是一样的，i-j表示退回原位，而模式串是从下标1开始计算的，则要+1，这个时候才是真正退回了原位，再+1，就是原位的下一位了)
- $\large j=i$
匹配成功：
- $\large i=7$
- $\large j=5$
- 返回$\large i-t.length=3$
index(S,P,pos)
- 将主串的第pos个字符和模式串的第一个字符比较。
- 若相等，继续这个比较后续字符
- 若不等，就从主串的下一字符起，重新逐个比较
- 直到发现一个连续子串序列与模式串相等，返回值为S中与T匹配的子序列第一个字符的序号即匹配成功
- 否则匹配失败，返回0

int Index_BF(SString S,SString T){
    int i=1,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			//返回匹配的第一个字符的下标
}

BF算法的时间复杂度：

4.3.3.2 KMP算法

这种改进算法是由 Knuth 、 Morris 和 Pratt 同时设计实现的，因此简称 KMP 算法。

利用已经部分匹配的结果而加快模式串的滑动速度
且主串S的指针i不必回溯！可提速到O(N+M)！

为此，定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置

第四个这里是1因为比较的时候不包括末尾元素但包括首元素

$\large k-1=最大公共前后缀的长度$

int Index_KMP(SString S,SString T,int pos){
    i=pos;j=l;
    while (i<S.length && j<T.length) {
        if 
            <j==o||s.ch[i]==T.ch[j]){ ++i;++j;}			//继续比较后继字符
        else 
            j=next[i]; 									//i不变，j后退
    }
	if 
        (j>T.length)return i-T.length;					//匹配成功
	else 
        return 0; 										//匹配失败
}

根据next值求nextval值的方法

4.4 数组

栈和队列是操作受限的线性表。串是内容受限的线性表。数组和广义表是对线性表的推广。

4.4.1 数组的类型定义

数组：按一定格式排列起来，具有相同类型的数据元素的集合
一维数组：若线性表中的数据元素为非结构的简单元素，一维数组
- 一维数组的逻辑结构：线性结构。定长的线性表。
- 声明格式：数据类型变量名称[长度]
  - 例：int num[5]={0,1,2,3,4};
二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组。
- 二维数组的逻辑结构：
  - 非线性结构：每一个数据元素即在一个行表中，又在一个行列中
  - 线性结构：该线性表的每个数据元素也是一个定长的线性表
- 声明格式：数据类型变量名称[行数][列数];
  - 例：int num[5] [8]
n维数组：若n-1维数组中的元素又是一个一维数组结构，则称作n维数组。
结论：线性表结构是数组结构的一个特例，二数组结构又是线性表结构的拓展
数组特点：结构固定——定义后，维数和维界不再改变。
数组基本操作：除了结构的初始化和销毁之外，只有取元素和修改元素值的操作。

4.4.2 数组的顺序存储

二维数组可有两种存储方式
- 以行序为主序
- 以列序为主序

4.4.3 特殊矩阵的压缩存储

矩阵：一个由M*N个元素排成的m行n列的表。

$\large \begin{pmatrix}a_{11}&a_{12}&a_{13}&……&a_{1n}\a_{21}&a_{22}&a_{23}&……&a_{2n}\……&……&……&……&……&\a_{m1}&a_{m2}&a_{m3}&……&a_{mn}\end{pmatrix}$

矩阵的常规存储：

将矩阵描述为一个二维数组。

矩阵的常规存储的特点：

可以对其元素进行随机存取；
矩阵运算非常简单；存储密度为1

不适宜常规存储的矩阵：

值相同的元素很多且呈某种规律分布；
零元素多

矩阵的压缩存储:

为多个相同的非零元素只分配一个存储空间；
对零元素不分配空间
一些特殊的矩阵可以压缩，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵(矩阵中非零元素的个数较少，不到百分之五)等。
1. 对称矩阵：在N*N的矩阵中满足**$\large a_{ij}=a_{ji}$,存储方法，只存储上（或下）三角的数据元素，共占用N(N+1)/2**个元素空间
  
  下标k的求法为$(i-1)+(j-1)$,其中$a_{n-1}$前面行前面有$n-1$个数求和之后得到$\dfrac {n(n-1)}{2}$，列前面没有
2. 三角矩阵：对角线一下或以上的数据元素全为常数C
  1. 存储方法：重复元素c共享一个元素存储空间，共占用n（n+1)/2+1个元素空间：sa[1…n（n+1)/2+1]
3. 对角矩阵（带状矩阵）
  1. 特点：在n*n的方阵中，所有的非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为零，则称为对角矩阵，常见的有三对角矩阵，五对角矩阵，起对角矩阵。（几条对角线有数值就是几对角矩阵）
  2. 存储方法：以对角线的顺序存储
4. 稀疏矩阵
  1. 特点：设在m*n的矩阵中又t个非零元素，且t所占总体百分比小于五时称为稀疏矩阵
  2. 压缩存储原则：存各非零元素的值，行列位置和矩阵的行列数
    1. 例： $\large （i,j,a_{ij}）$
    2. 三元组顺序表又称有序的双下标
      1. 优点：便于进行依行顺序处理的矩阵运算。
      2. 缺点：不能随机存取，若按行号存取需要从头开始进行查找

4.5 广义表

广义表：又称列表Lists是n>=0个元素$a_0,a_1,……，a_{n-1}$的有限序列，其中没一个$a_i$或者是原子，或者是一个广义表
广义表通常记作：LS=$a_0,a_1,……，a_{n}$
- 其中LS为表名，n为表长，$a_i$为表的元素
- 通常用大写字母表示广义表，小写字母表示原子
- 表头：若LS非空，则其第一个元素$a_1$就是表头
  - 记作 $head（LS）=a_1$
- 表尾，除了表头的其他元素组成的表
  - 记作$tail（LS）=（a_2,……，a_{n}）$

广义表中的数据元素有相对次序；一个直接前驱和一个直接后继
广义表的长度定义为最外层所包含元素的个数
广义表的深度定义为该广义表展开后所含括号的重数
广义表可以为其他广义表共享
广义表可以是一个递归的表
广义表是多层次结构，广义表的元素可以是单元素，也饿可以是子表，而子表的元素还可以是子表类似二叉树。

广义表可以看做线性表的推广，线性表是广义表的特例

函数本身带括号，所以最后的c应该外面加一个括号

5 树和二叉树

树形结构与线性结构的不同就是，线性结构的前驱和后继是一对一的，树状结构属于非线性结构，有多个后继。前驱与后继是一对n的

5.1 树和二叉树的定义

5.1.1 树的定义

树是个n个结点的有限集：
- 若n=0，称为空树；
- 若n>0，则他满足如下两个条件：
  1. 有且仅有一个特定的称为根的结点
  2. 其余结点可分为吗（m>=0）个互不相交的有限集T1,T2,T3。。

5.1.2 树的基本术语

根结点：非空树中无前驱结点的结点。
结点的度：结点拥有的子树数。
树的度：树内各结点的度的最大值。
结点的子树的根称为该结点的孩子，该结点称为该孩子的双亲，还有结点的祖先，结点的子孙就不展开描述了。
有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。
无序树：树中结点的各子树无次序。
森林：是m棵互不相交的树的集合
- 把根结点删除树就变成了森林
- 一棵树可以看成是一个特殊的森林，树一定是森林，森林不一定是树
- 给森林中各子树加上一个双亲节点，森林就变成了树

5.1.3 二叉树的定义

二叉树的结构最简单，规律性最强，可以证明所有树都能转化为唯一对应的二叉树，不失一般性。

二叉树：是n个结点的有限集，他或者是空集或者是由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成
- 特点：每个节点最多两个孩子
- 子树有左右之分(即使只有一棵子树也进行区分)，次序不能颠倒
- 二叉树可以是空集合，根可以有空的左子树或空的右子树。
- 具有三个结点的树可能有几种形态？

5.2 案例引入

5.2.1 数据压缩问题

将数据文件转换成由0、1组成的二进制串，称之为编码

具体的方法到哈夫曼树和哈弗曼编码那里学习，这里暂且按下不表

5.2.2 利用二叉树求解表达式的值

以二叉树表示表达式的递归定义如下：
1. 若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；
2. 若表达式为 “ 第一操作数运算符第二操作数” 的形式，则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点存放运算符，其中错作数本身又为表达式。

具体实现，我们会在[5.8 案例分析与实现](####5.8 案例分析与实现)进行讲解

5.3 树和二叉树的抽象数据类型定义

5.4 二叉树的性质和存储结构

在二叉树的第i层上之多有$\large 2^{i-1}$个结点
深度为k的二叉树至多有$\large 2^k-1$个结点
对任何一棵二叉树T，如果其叶子树为$\large n_0$,度为2的结点数为$\large n_2$，则$\large n_0=n_2+1$
- 总边数$\large B=n-1 = B=n_22+n_11$
- 总结点数为$\large n=n_22+n_11+1$ 又 $n=n_2+n_1+n_0$
- 推导出$\large n_0=n_2+1$
具有n个结点的完全二叉树的深度为[log_2n]（向下取整）+1

性质4表明了完全二叉树结点数n与完全二叉树深度k之间的关系
如果对一棵有 n个结点的完全二叉树，其结点按层序编号（从第 1 层到第[log2n]+ 1 层，每层从左到右），则对任一结点(n=>i>=1), 有如果i=1，无双亲，如果i>1.则其双亲是结点[$\large i/2$]。
1. 性质5表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系

两种特殊形式的二叉树
- 满二叉树：一颗深度为k且有$\large 2^k-1$个结点的二叉树称为满二叉树
- 特点：
  - 每一层上的结点数
  - 编号从上到下，从左到右
- 完全二叉树：深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
  - 在满二叉树中，从最后一个结点开始，连续去掉任意个结点，都是一棵完全二叉树
  - 叶子只能分布在最大的两层上
  - 对任意一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i-1

5.5 遍历二叉树和线索二叉树

5.5.1 遍历二叉树

遍历的定义——顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次
- “访问”可以看做对结点作各种处理
遍历的目的——得到树中所有结点的一个线性排列
遍历的用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心
遍历的算法
- DLR——先（根）序遍历
- LDR——中（根）序遍历【从最左边开始左根右】，可以吧空序都先画出来，然后再开始遍历
- LRD——后（根）序遍历
- 例题——已知中序序列和后续序列求二叉树
- 前后确定根，中序辨左右 重点

二叉树先序遍历算法

Status PreOrderTiraverse（BiTree T）{
    if(T==NULL)return OK;
    else{
        visit(T);								//访问根结点
        PreOrderTiraverse(T->lchild);			//递归遍历左子树，递归调用
        PreOrderTiraverse(T->rchild);			//递归遍历右子树
    }
}

其中涉及到了递归调用的逐层返回

如果去掉输出语句，从递归的角度看，三种三发事完全相同的，只是访问的十几不同

时间复杂度是3n，其中3是常数可以去掉，所以O(n)

5.5.1.1 遍历二叉树的非递归算法

二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树

基本思想

建立一个栈
根结点进栈，遍历左子树
根结点出栈，输出根结点，遍历右子树

Status InOrderTraverse(BiTree T){
    BiTree p;InitStack(S);P=T;
    while(p||!StackEmpty(S)){		//StackEmpty（S），S空返回true,非空返回false
        if(p){Push (S,p); p=p->lchild;}//push（S，p）是把p值入栈S
        else {Pop(S,q); printf("%c", q->data);//pop（S，q）是出栈值给q
             p=q->rchild;}
    }//while
}
1
2
3
4
5
6
7
8
9
10
11
12

     ***走到D时，左右子树都为空返回时，q会指向A应为栈内一开始就存放了A，然后再访问A的右子树***

##### 5.5.1.2 二叉树的层次遍历

- 队列类型定义

  ```c
  typedef struct{
      BTNode data[MaxSize];
      int front,rear;
  }SqQueue;

二叉树层次遍历算法：

void LevelOrder(BTNode*b){
    BTNode *p;   SqQueue *qu;
    InitQueue(qu);//初始化队列
    enQueue(qu, b);//根结点指针进入队列
    while(!QueueEmpty（qu)）{
        deQueue(qu,p);//出队结点p
        printf("%c",p->data);//访问结点p
        if(p->lchild!=NULL)enQueue(qu,p->lchild);//有左孩子时将其进队
        if(p->rchild!=NULL)enQueue(qu,p->rchild);//有右孩子时将其进队
    }
}

5.5.1.3 遍历算法的应用——二叉树的建立

算法描述：

Statys CreatBiTree(BiTree &T){
    scanf(&ch);
    if(ch=="#")T=NULL;
    else{
        if(!(BiTNode*)malloc(sizeof(BiTNode)))	//分配一块儿结点空间
            exit(OVERFLOW);	
        T->data=ch;								//生成根结点
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return OK;
}

5.5.1.4 复制二叉树

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

5.5.1.5 计算二叉树的深度

如果是空树，则深度为0

否则，递归计算左子树深度记为m，右子树深度为n，二叉树深度则为n和m的较大者加1

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

5.5.1.6 计算二叉树的结点总数

如果是空树，则结点个数为0

否则，结点个数为左子树的结点个数+右子树的结点个数再加1

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

5.5.1.7 计算二叉树叶子结点数

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

5.5.2 线索二叉树

利用二叉链表中的空指针域：

如果某个节点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果右孩子为空，则其指针域改为指向其后继————将改变指向的指针称为**“线索”，加上了线索的二叉树称为线索二叉树**
为了区分是指向孩子的指针还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域ltag和rtag，这样结点的结构就为【lchild | ltag | data | rtag | rchild 】并约定：
- ltag=0/rtag=0 指针指向孩子
- ltag=1/rtag=1 指针指向前驱/后继

5.6 树和森林

本节将讨论树的表示及其遍历操作，并建立森林与二叉树的对应关系。

5.6.1 树的存储结构

5,6,6,1 双亲表示法

实现：定义结构数组存放树的结点，每个结点含两个域；

数据域：存放结点本身信息
双亲域：指示本结点的双亲结点在数组中的位置

C语言的类型描述：

typedef struct PTNode{
    TElemType data;
    int parent;
}PTNode;

树结构：

#define MAX_TREE_SIZE 100
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int r,n;//根结点的位置和结点个数
}

5.6.1.2 孩子链表

把每个结点的孩子结点排列起来。看成一个线性表，用单链表存储

C语言描述：

typedef struct CTNode{
    int child;
    struct CTNode *next;
}*Childptr;

树结构

typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;
}CTree;

5.6.1.3 孩子兄弟表示法

C语言描述

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

5.6.2 树与二叉树的转换

将树转换为二叉树进行处理，利用二叉树的算法来实现对树的操作。
由于树和二叉树都可以用二叉链表做存储结构，则以二叉链表做媒介可以导出树与二叉树之间的一个对应关系。
给定一棵树可以找到唯一的一颗二叉树与之对应
- 加线：在兄弟之间加一条线，
- 抹线：对每个结点，除了其左孩子外，去除其余孩子之间的关系
- 旋转：以树根结点为轴心，将整树顺时针旋转45°
  
  树变二叉树：兄弟相连留长子。其中根结点的油茶树一定为空
反之可以把二叉树转换成树
- 加线：若p结点是双亲节点的左孩子，则将p的右孩子，右孩子的右孩子……沿分支找到所有右孩子，都与p的双亲用线连起来
- 抹线：抹掉原二叉树中双亲与右孩子之间的连线
- 调整：将结点按层次排列，形成树结构。
  
  二叉树变树：左孩右右连双亲，去掉原来右孩线

5.6.3 森林与二叉树的转换

森林转换成二叉树（二叉树与多棵树之间的关系）
- 将个棵树分别转换成二叉树
- 将每棵树的根结点用线相连
- 以第一课树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
  
  森林变二叉树：树变二叉根相连
二叉树转换成森林
- 抹线：将二叉树中根结点与其右孩子连线，及沿有分支搜索到的所有右孩子之间的连线抹掉，使之变成孤立的二叉树
- 还原：将孤立的二叉树还原成树
  
  二叉树变森林：去掉全部右孩线，孤立二叉再还原

5.6.4 树和森林的遍历

5.6.4.1树的遍历

先根遍历：若树不为空，则先访问根结点，然后一次先根遍历各棵子树。
后根遍历：若树不为空，则先依次后根遍历各棵子树，然后访问根结点。
层次遍历：若树不为空，则自上而下自左至右访问树种每个结点。

5.6.4.2 森林的遍历

将森林看作由三部分构成：
1. 森林中第一棵树的根结点；
2. 森林中第一棵树的子树森林；
3. 森林中其他树构成的森林。
先序遍历：若森林不为空，则依次从左至右对森林中的每一棵树进行先根遍历
中序遍历：若森林不为空，则
1. 中序遍历森林中第一棵树的子树森林；
2. 访问森林中第一棵树的根结点；
3. 中序遍历森林中（除第一棵树之外）其余树构成的森林。
  
  即：依次从左至右对森林中每一个棵树进行后根遍历

5.7哈夫曼树的基本概念

5.7.1 哈夫曼树的基本概念

效率最高的判别树，就是哈夫曼树（也称最优二叉树）

路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径
结点的路径长度：两结点间路径上的分支数。
树的路径长度：从树根到没一个结点的路径长度之和。记作：TL
- 结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树，但路径长度最短的不一定是完全二叉树
权(weight)：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作：$\large WPL=\sum\limits_{k=1}^nw_kl_K$(weighted path length)
哈夫曼树：最优树/最优二叉树（带权路径长度最短的树）
- 因为构造这种树的算法是由哈夫曼教授于1952年提出的，所以被称为哈夫曼树，相应的算法称为哈夫曼算法
- 满二叉树不一定是哈夫曼树
- 哈夫曼树中全越大的叶子离根越近
- 具有相同带权结点的哈夫曼树不唯一
贪心算法：构造哈夫曼树时首先选择权值小的叶子结点

5.7.2 哈夫曼树的构造算法

构造过程
1. 根据给定的n个权值{$w_1.w_2.w_3,……,w_n$}，构造n棵只有根结点的二叉树，这n棵二叉树构成一个森林F。
2. 在森林 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和
3. 在森林F中删除这两棵树，同时将新得到的二叉树加入森林中。
4. 重复2和3的步骤，直到森林中只有一棵树为止，这棵树即为哈夫曼树。
口诀
1. 构造森林全是根
2. 选用两小造新树
3. 删除两小添新人
4. 重复二三剩单根
总结
1. 在哈夫曼树算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树
2. 经过n_1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支节点
  
  可见：哈夫曼树中共有n+n-1=2n-1个结点，且其所有的分支结点的度均不为1.
哈夫曼树构造算法的实现
采用顺序存储结构——一维结构数组 HuffmanTree H;

结点类型定义

typedef struct{
    int weight;
    int parent,lch,rch;
}HTNode,*HuffmanTree;

哈夫曼树中结点下标i	weight	parent	lch	rch
1
2
3
4
……
2n_1

构造哈夫曼树

void CreateHuffmanTree(HuffmanTree &HT,int n){
    if(n<=l) return;
	m=2*n-l;//数组一共2n-1个元素
	HT=new HTNode[m+l);//0号单元未用，HT[m]表示根结点
    for(i=l;i<=m;++i){//将2n-1个元素的lch/rch/parent置为0
        HT[i].parent=O;HT[i].lchild=O;HT[i].rchild=O;
    }
    for(i=l;i<=n;++i}cin>>HT[i] .weight;//输入前n个元素weight的值，初始化结束
    for (i=n+l;i<=m;++i)
        Select (HT,i-1,sl,s2);
        HT[sl] .parent=i;HT[s2] .parent=i;
        HT[i] .lchild=sl;HT [i]. rchild=s2;
        HT[i] .weight=HT[sl] .weight+HT[s2] .weight;
}

例题：

巳知 w = (5,29,7,8,14,23,3,11), 利用算法 5.10 试构造一棵哈夫曼树，计算树的带权路径长度，并给出其构造过程中存储结构HT的初始状态和终结状态。

哈夫曼树中结点下标i	weight	parent	lch	rch
1	5	9	0	0
2	29	14	0	0
3	7	10	0	0
4	8	10	0	0
5	14	12	0	0
6	23	13	0	0
7	3	9	0	0
8	11	11	0	0
9	8	11	1	7
10	15	12	3	4
11	19	13	8	9
12	29	14	5	10
13	42	15	6	11
14	58	15	2	12
15	100	0	13	14

5.7.3 哈夫曼编码

void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
    HC=nuw char*[n+1];										//分配n个字符编码的头指针矢量
    cd=new char[n];											//分配临时存放编码的动态数组空间
    cd[n-1]='\0';											//编码结束符
    for(i=1;i<=n;++i){										//逐个字符求哈夫曼编码
        start=n-1;c=i;f=HT[i].parent;
        while(f!=0){										//从叶子结点开始向上回溯，直到根节点
            --start;										//回溯一次start向前指一个位置
            if
                (HT[f].lchild==c)cd[start]='0';				//结点c是f的左孩子，则生成代码0
            else				 cd[start]='1';				//结点c是f的右孩子，则生成代码1
                c=f;f=HT[f].parent;							//继续向上回溯
        }													//求出第i个字符的编码
        HC[i]=new char[n-start];							//为第i个字符串编码分配空间
        strcpy(HC[i],&cd[start]);							//将求得的编码从临时空间cd复制到HC的当前行中
    }
   delete cd;												//释放临时空间
}															//creatHuffmanCode

编码：
1. 输入各字符及其权值
2. 构造哈夫曼树——HT[i] n+n-1个
3. 进行哈夫曼编码——HC[i]
4. 查HC[i]，得到各字符的哈夫曼编码
解码：
1. 构造哈夫曼树
2. 依次读入二进制码
3. 读入0，则走向左孩子，读入1，则走向右孩子
4. 一旦到达某叶子时，即可译出字符
5. 然后再从根出发继续译码，直到结束

6 图

图是一种比线性表和树更为复杂的数据结构。

6.1 图的定义和基本术语

6.1.1 图的定义

图：G=（V.E）
- V：顶点（数据元素）的有穷非空集合；
- E：边的有穷集合
无向图：每条边都是无方向的
有向图：每条边都是有方向的
完全图：任意两个点都有一条边相连
稀疏图：有很少边或弧的图（$e<nlog_2n$）
稠密图：有较多边或弧的图

6.1.2 图的基本术语

网，边/弧带权的图
邻接：有边/弧相连的两个顶点之间的关系。
- 存在（$v_i,v_j$）,则称为$v_i和v_j$互为邻接点
- 存在<$v_i,v_j$>，则称$v_i$邻接到$v_j$,$v_j$邻接于$v_i$,
关联（依附）：边/弧与顶点之间的关系。
- 存在（$v_i,v_j$）/<$v_i,v_j$>，则称该边/弧关联于$v_i$和$v_j$
顶点的度：与该顶点相关联的边的数目，记为TD（v）
- 在有向图中，顶点的度等于该顶点的入度和出度之和。
- 顶点v的入度是以v为终点的有向边的条数，记作ID（v）
- 顶点v的出度是以v为始点的有向边的条数，记作OD（v）
路径：连续的边构成的顶点序列
路径长度：路径上边或弧的数目/权值之和
回路（环）：第一个顶点和最后一个顶点相同的路径
简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径
简单回路（环）：除路径起点和终点相同外，其余顶点均不相同的路径
连通图（强连通图）：在无（有）向图G=(V,{E})中，若对任意两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）
权与网：
- 图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费。
- 带权的图称为网
子图：设有两个图$G=（V，{E}）、G_1=(V_1,{E_1})$,若$V_1属于V，E_1属于E$则称$G_1是G$的子图
连通分量（强连通分量）
- 无向图G的极大联通子图称为G的连通分量
  - 极大连通子图意思是：该子图是G联通子图，将G的任何不在该子图汇总的顶点加入，子图不再连通
- 有向图G的极大连通子图称为G的强连通分量
  - 极大强连通子图意思是: 该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。
- 极小联通子图：该子图是G的连通子图，在该子图中删除任何一条边，联通子图不再连通
- 生成树:包含无向图G所有顶点的极小连通子图
- 生成森林:对非连通图，由各个连通分量的生成树的集合

6.2 案例引入

6.2.1 六度空间理论

理论又称作六度分隔论 (Six Degrees of Separation)。六度空间理论是20世纪60年代由美国的心理学家米格兰姆(Stanley Milgram)提出的，理论指出：“你和任何一个陌生人之间所间隔的人不会超过六个”

6.3 图的类型定义

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

ADT Graph{
    数据对象V：具有相同特性的数据元素的集合，称为顶点集。
    数据关系R：R{VR}
    	VR={<V,W>|<V,W>|V,W属于V^p(v,w)}， <v, w>表示从v到w的弧，P (v, w)定义了弧<v, w>的信息
}

基本操作：
- CreateGraph{&G,V,VR}
  
  初始条件：V是图的顶点集，VR是图中弧的集合。
  
  操作结果：按V和VR的定义构造图G。
- DFSTraverse(G)
  
  初始条件：图G存在。
  
  操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点访问一次。
- BFSTraverse(G)
  
  初始条件：图G存在。
  
  操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点访问一次.

6.4 图的存储结构

图的逻辑结构：多对多
- 图没有顺序存储结构，可以借助二维数组来表示元素间的关系
数组表示法（邻接矩阵）
链式存储结构：
- 多重链表
  - 邻接表
  - 邻接多重表
  - 十字链表
重点介绍：
- 邻接矩阵（数组）表示法
- 邻接表（链式）表示法

6.4.1 邻接矩阵

数组（邻接矩阵）表示法

建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。

设图A=（V，E)有n个顶点，则
顶点表Vexs[n]

i 1 2 3 …… n-1

Vexs[n] $V_1$ $V_2$ $V_3$ …… $V_n$
图的邻接矩阵是一个二维数组$A.arcs[n][n]$,定义为：

$A.arcs[i][j]=\quad\begin{cases}1,如果<v_i,v_j>或(v_i,v_j)\in E\0，反之\end{cases}$
无向图的邻接矩阵表示法：
1. 无向图的邻接矩阵是对称的
2. 顶点i的度=第i行（列）中1的个数；
3. 完全图的邻接矩阵中，对角元素为0，其余1.
有向图的邻接矩阵表示法：
1. 有向图的邻接矩阵可能是不对称的
2. 顶点的出度=第i行元素之和
3. 顶点的入度=第i列元素之和
4. 顶点的度=第i行和列的元素之和
网（即有权图）的邻接矩阵表示法

邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵

#define Maxint 32767							//表示极大值
#define MVNum 100 								//最大顶点数
typedef char VerTexType;						//设顶点的数据类型为字符型
typedef int ArcType;							//假设边的权值类型为整形
typedef struct｛ 
    VerTexType vexs [MVNum];					//顶点表
	ArcType arcs[MVNum) [MVNum];				//邻接矩阵
    int vexnum,arcnum;							//图的当前点数和边数
}AMGraph;

采用邻接矩阵表示法创建无向网

输入总顶点数和总边数。
依次输入点的信息存入顶点表中。
初始化邻接矩阵，使每个权值初始化为极大值。
构造邻接矩阵。

Status CreateUDN(AMGraph &G){//创建无向网G
    cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数
    for(i=O;i<G.vexnum;++i)
		cin>>G.vexs[i];//依次输入点的信息
	for(i=O;i<G.vexnum;++i)//初始化邻接矩阵呢
		for (j=0; j<G.vexnum;++j) 
			G.arcs[i][j]=Maxint;//变得权值均置为最大
	for(k=O;k<G.arcnum;++k){//构造邻接矩阵
        cin>>vl>>v2>>w;//输入一条边所依附的顶点及边的权值
        i=LocateVex(G,vl);j=LocateVex(G,v2);//确定V1和V2在G中的位置
        G.arcs[i][j]=w;//边<v1,v2>的权值置为w
        G.arcs[j][i]=G.arcs[i][j];//置<v1,v2>的对称边<v2,v1>的权值为w
    }
    return OK;
}

补充算法：在图中查找顶点：

int LocateVex(AMGraph G,VertexType u){
    int i;
    for(i=0;i<G.vexnum;++i)
        if(u==G.vexs[i]) return i;
    return -1;
}

邻接矩阵的优点
- 直观简单好理解
- 方便检查任意一对顶点间是否存在边
- 方便找任一顶点的所有“邻接点”
- 方便计算任一顶点的“度”
邻接矩阵的缺点
- 不便于增加和删除顶点
- 浪费空间——存稀疏图有大量无效元素
  - 对稠密图来说还是很合算的
- 浪费时间——统计稠密图中一共有多少条边

6.4.2 邻接表

无向图邻接表表示法（链式）
- 顶点：按编号顺序将顶点数据存储在一维数组中；
- 关联同一顶点的边（以顶点为尾的弧）：
  - 用线性链表存储
- 特点：
  - 邻接表不唯一
  - 若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图
  - 无向图中顶点$V_i$的度为第i个单链表中的结点数
有向图邻接表表示法
- 特点：
  - 顶点$V_i$的出度为第i个单链表中的结点个数
  - 顶点的入度为整个链表中领接点域值是i-1的结点个数

图的邻接表存储表示：

typedef struct VNode{
    VerTexType data;					//顶点信息
    ArcNode *firstarc;					//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum]					//AdjList表示邻接表类型

弧（边）的结点结构 adjvex | nextarc | info

#define MVNum 100						//最大顶点数
typedef struct ArcNode{					//边结点
    int adjvex;							//该边所指向的顶点的位置
    struct ArcNode * nextarc;			//指向下一条边的指针
    OtherInfo info;						//和边相关的信息
}ARcNode;

图的结构定义：

typedef struct{
    AdjList vertices;//vertices——vertex的复数
    int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;

邻接表操作举例说明：

无向图的邻接表表示 p118

Status CreateUDG(ALGraph &G) {				//采用邻接表表示法， 创建无向图 G
	cin>>G.vexnum>>G.arcnum;				//输入总顶点数，总边数
	for(i=O;i<G.vexnum;++i){				//输入各点，构造表头结点表
		cin»G.vertices[i) .data;			//输入顶点值
		G.vertices[i) .firstarc=NULL;}		//初始化表头结点的指针域
	for(k=O;k<G.arcnum;++k){				//输入各边，构造邻接表
        cin>>vl>>v2;						//输入一条边依附的两个顶点
        i=LocateVex(G,vl);
        j=LocateVex(G,v2);
        pl=new ArcNode;//生成一个新的边结点*p1
        pl->adjvex=j;//邻接点序号为j
        pl->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=pl;//将新结点*p1插入顶点vi的边表头部（头插法）
        p2=new ArcNode;//生成另一个对称的新的边结点*p2
        p2->adjvex=i;//邻接点序号为i
        p2->nextarc=G.vertices[j].firstarc;
        G.vertices[j].firstarc=p2;//将心结点*p2插入顶点vj的边表头部
    }
     return OK;
}

无向图邻接表特点：
1. 方便找任一顶点的所有“邻接点”
2. 节约稀疏图的空间
  1. 需要n个头指针和+2e个结点（每个结点至少2个域）
3. 方便计算任一顶点的“度”
  1. 对无向图：是的
  2. 对有向图：只能计算“出度”需要构造“逆邻接表”来方便计算“入度”
4. 不方便检查任意一对顶点间是否存在边
邻接矩阵与邻接表表示法的关系
1. 联系：邻接表中每个链表对应于接短阵中的一行，链表中结点个数等于一行中非零元素的个数。
2. 区别：
  1. 对于任一确定的无向图，邻接矩阵是唯一的 (行列号与顶点编号一致)，但邻接表不唯一 (链接次序与顶点编号无关)
  2. 邻接矩阵的空间复杂度为$O（n^2)$,而邻接表的空间复杂度为$O(n+e)$。(e是出于$0到n^2$之间的复杂变量)
3. 用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图

6.4.3 十字链表

有向图：

顶点结点：

data	firstin	firstout
存与顶点相关的信息	入度边	出度边

弧结点：

tailvex	headvex	hlink	tlink
弧尾位置	弧头位置	弧头相同的下一条弧	弧尾相同的下一条弧

弧头是箭头，弧尾是箭尾

6.4.4 邻接多重表

边结点：

mark	ivex	ilink	jvex	jlink	info
标志域，标记此边是否被搜索过	该边依附的两个顶点在表头数组中的位置	指向依附于ivex的下一条边	该边依附的两个顶点在表头数组中的位置	指向依附于jvex的下一条边

顶点节点

data	firstedge
存与顶点有关的信息	指向第一条依附于该顶点的边

6.5 图的遍历

遍历的实质：找每个顶点的邻接点的过程
图常用的遍历：
- 深度优先搜索(DFS)
- 广度优先搜索(BFS)

6.5.1 深度优先搜索

甚多有限搜索遍历过程：

从图中某个顶点v出发，访问v。
找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问过的顶点没有未被访问的邻接点为止。
返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。
重复步骤 (2)和(3), 直至图中所有顶点都被访问过，搜索结束。

6.5.1.1 采用邻接矩阵表示图的深度优先搜索遍历

void DFS(AMGraph G,int v){//图G为邻接矩阵类型
    cout<<v;visited[v]=true;//访问第v个顶点
    for(w=0;w<G.vexnum;w++)//依次检查邻接矩阵v所在行
        if((G.arcs[v][w]!=0)&&(!visited[w]))
            DFS(G,w);//w是v邻接点，如果w未访问，则递归调用DFS
}

DFS算法效率分析
- 用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为$O(n^2)$
- 用邻接表来表示图，虽然有2e个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为$O(n+e)$
结论
- 稠密图适合在邻接矩阵上进行深度遍历
- 稀疏图适合在邻接表上进行深度遍历

6.5.2 广度优先搜索

用队列实现广度优先遍历，累次层次遍历那样

6.5.2.1 按广度优先非递归遍历连通图G

void BFS (Graph G,int v){
    cout<<v;visited[v]=true;//访问第v个顶点
    initQueue(Q);//辅助队列Q初始化，置空
    EnQueue(Q,v);//v进队
    while(!QueueEmpty(Q)){//队列非空
        DeQueue(Q,u);//队头元素出队并置为u
        for(W=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
            if(!visited[w]){//w为u的尚未访问的邻接顶点
                cout<<w;visited[w]=true; EnQueue(Q,w);//w进队
            }
    }
}

BFS算法效率分析
- 如果邻接矩阵，则BFS对于每一个背访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为$O(n^2)$
- 用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为$O(n+e)$
DFS和BFS算法效率比较
- 空间复杂度相同，都是O(n)（借用了堆栈或队列）；
- 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。

6.6 图的应用

6.6.1 最小生成树

生成树：所有顶点均由边连接在一起，但不存在回路的图
- 一个图可以有许多棵不同的生成树
- 所有生成树具有以下共同特点
  - 生成树的顶点个数与图的顶点个数相同
  - 生成树是图的极小连通子图，去掉一条边则非连通
  - 一个有n个顶点的连通图的生成树有n-1条边
  - 在生成树中再加一条边必然形成回路
  - 生成树中任意两个顶点间的路径是唯一的
无向图的生成树：
- 设图G=(V,E)是个连通图，当从图任一顶点出发遍历图G时，将边集E(G)分成两个集合T(G) 和B(G)。其中 T(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1(V,T)是图G的极小连通子图。即子图G1 是连通图G的生成树
最小生成树
- 给定一个无向网络，在该网络的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。
- 最小生成树的典型用途
  - 要在n个城市间建立通信网，则n个城市应铺设n-1条路，每条路也有对应的经济成本
  - 建立数学模型：
    - 顶点代表城市有n个
    - 边代表线路有n-1条
    - 边的权值表示线路的经济代价
    - 连通网表示n个城市间的通信网
构造最小生成树
- 构造最小生成树的算法很多，其中多数算法都利用了MST的性质
- MST性质：设N=（V,E) 是一个连通网，U是顶点集V的一个非空子集。若边(u,v) 是一条具有最小权值的边，其中$u\in U，v \in V-U$则必存在一棵包含边(u,v)的最小生成树
- 在生成树的构造过程中，图中n个顶点分属两个集合：
  - 已落在生成树上的顶点集: U
  - 尚未落在生成树上的顶点集: V-U
- 接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边

6.6.1.1 普利姆(prim)算法

算法思想：
1. 设N=（V,E)是连通网，TE是N上最小生成树中边的集合
2. 初始令$U={u_0}，(u_0 \in V),TE=${}
3. 在所有$u\in U，v \in V-U$的边$（u,v）\in E$中找一条代价最小的边$(u_0,v_0)$.
4. 将$(u_0,v_0)$并入集合TE，同时$v_o$并入U
5. 重复上述操作直至U=V为止，则T=（V，TE）为N的最小生成树

6.6.1.2 克鲁斯卡尔(Kruskal)算法

算法思想：
1. 设连通网 N=(VE)，令最小生成树初始状态为只有 n个顶点而无边的非连通图T=（V，{}),每个顶点自成一个连通分量。
2. 在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上(即:不能形成环），则将此边加入到 T中;否则，舍去此边，选取下一条代价最小的边。
3. 依此类推，直至T中所有顶点都在同一连通分量上为止。
最小生成树可能不唯一

算法名	普里姆算法	克鲁斯卡尔算法
算法思想	选择点	选择边
时间复杂度	O（n^2)(n为顶点数)	O(eloge)（e为边数）
适应范围	稠密图	稀疏图

6.6.2 最短路径

两种最常见的最短路径问题：
1. 单源最短路径——用Dijkstra（迪杰斯特拉）算法
2. 所有顶点间的最短路径——用Floyd——（弗洛伊德）算法

6.6.2.1 迪杰斯特拉算法

初始化：从源点$v_0$到各终点$v_k$的直达路径 $（v_o,v_k）$，即通过一条弧到达的路径。
选择：从这些路径中找出一条长度最短的路径$（v_0,u）$.
更新：然后对其余各条路径进行适当调整：
1. 若在图中存在弧$(u，v_k)$,且$(v_0,u)+（u，v_k）<(v_0,v_k),则以路径（v_0,u,v_k）代替（v_0，v_k)$
在调整后的各条路径中，再找长度最短的路径，依此类推

时间复杂度为 $O(n^3)$

6.6.2.2 弗洛伊德算法

6.6.3 拓扑排序

有向无环图：无环的有向图，简称DAG图
- 有向无环图常用来描述一个工程或系统的进行过程。
- 一个工程可以分为若干个子工程，只要完成了这些子工程，就可以导致整个工程的完成
AOV网拓扑排序
- 用一个有向图表示一个工程的各子工程及其相只制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称 AOV网(Activity On Vertex network)。
AOE网关键路径
- 有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网 (Activity On Edge)
AOV网的特点：
1. 若从i到j有一条有向路径，则i是j的前驱j是i的后继
2. 若<i,j>是网中有向边，则i是j的直接前驱;j是i的直接后继
3. AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。
拓扑排序
- 在AOV 网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若 AOV 网中有弧 <i,j>存在，则在这个序列中，i一定排在的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序
拓扑排序方法：
1. 在有向图中选一个没有前驱的顶点且输出
2. 在图中删除该顶点和所有以他为尾的弧
3. 重复1和2直到全部顶点均已输出；当图中不存在无前驱的顶点位置
  - 一个AOV网的拓扑序列不是唯一的
拓扑排序的一个重要应用：
- 检测AOV网中是否存在环的方法：
  - 对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该 AOV 网必定不存在环。
关键路径
假设一个工程有11项活动，9个事件
- 事件V1——表示整个工程开始（源点：入度为0的顶点）
- 事件v9——表示整个工程结束（汇点：出度为0的顶点）

关键路径——路径长度最长的路径
路径长度——路径上各活动持续时间之和
- ve(vj)——表示事件vj的最早发生时间
- vl(vj)——表示事件vj的最迟发生时间
- e(i)——表示活动ai的最早开始时间
- l(i)——表示活动ai的最迟开始时间
- l(i)-e(i)——表示完成活动ai的时间余量
- 关键活动——关键路径上的活动，即l(i)==e(i)的活动（即没有时间余量的活动）

其中√的为关键活动，而包含关键活动的路径为关键路径
- 需要加快同时在几条关键路径上的关键活动
  - 如：a11,a10,a8,a7
- 如果一个活动处于所有关键路径上，那么提高这个活动的速度，就能缩短整个工程的完成时间
  - 如：a1,a4
- 处于所有关键路径上的活动完成时间不能缩短太多，否则会使原来的关键路径变成不是关键路径。这时必须重新寻找关键路径

7 查找

7.1 查找的基本概念

查找表：是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着某种松散的关系，因此查找表是一种应用灵便的结构
- 查找表分两类
  - 静态查找表：仅做“查询“{检索)操作的查找表
  - 动态查找表：做“插入”和“删除”操作的查找表
关键字：关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。
- 主关键字：此关键字可以唯一地标识一个记录，则称此关键字为主关键字
- 次关键字：用以识别若千记录的关键字为次关键字。
查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）
- 若查找表中存在这样一个记录，则称 查找成功
  - 查找结果给出整个记录的信息，或指示该记录在查找表中的位置；
- 否则称 查找不成功
  - 查找结果给出“空记录”或“空指针”
- 查找经常进行的操作
  - 查询某个**“特定的”**数据元素是否在查找表中；
  - 检索某个**“特定的”**数据元素的各种属性；
  - 在查找表中插入一个数据元素；
  - 删除查找表中的某个数据元素；
查找算法的评价指标：
- 关键字的平均比较次数，也称平均查找长度。
  
  $\LARGE ASL=\sum\limits_{i=1}^np_ic_i$ (关键字比较次数的期望值)
  - n：记录的个数
  - pi：查找第i个记录的概率（通常认为pi=1/n）
  - ci：找到第i个记录所需的比较次数

7.2 线性表的查找

7.2.1 顺序查找

应用范围：
- 顺序表或线性链表表示的静态查找表
- 表内元素之间无序

数据元素类型定义

typedef struct{
    KeyType key;
    ……
}ElemType;

顺序表的定义

typedef struct{					//顺序结构表结构类型定义
    ElemType *R;				//表基址
    int length;					//表长
}SSTable;
SSTable ST;						//定义顺序表ST

顺序查找
1
2
3
4
5
int Search_seq(SSTable st,keytype key){
for(i=ST.length;i>=1;--i)
if (ST.R[i].key==key)return i;
return 0;
}
- 改进：把待查关键字key存入表头（”哨兵“）从后往前挨个比较，可免去查找过程中每一步都要检查是否查找完毕，加快速度
  1
  2
  3
  4
  5
  int search_seq(SSTable ST,KeyType key){
  ST.R[0].key=key;
  for(i=ST.length;ST.R[i].key!=key;--i);
  return i;
  }
  - 比较次数与key位置有关：
    - 查找第i个元素，需要比较n-i+1次
    - 查找失败，需要比较n+1次
  - 时间复杂度O(n)
    - 查找成功时的平均查找长度，设表中各记录查找概率相等
      
      $ASL=（1+2+……+n）/n=\dfrac {n+1}{2}$
  - 空间复杂度：一个辅助空间——O(1)
顺序查找的特点
- 优点：算法简单，逻辑次序无要求，且不同存储结构均适用
- 缺点：ASL太长，时间效率太低

7.2.2 折半查找

算法步骤
1. 设表长为n，low、high和mid分别指向待查元素所在区闻的上界，下界和中点，key为给定的要查找的值；
2. 初始时，令low=1，high=n，
3. 让k与mid指向的记录比较
  1. 若key==R[mid].KEY,查找成功
  2. 若key<R[mid].key,则high=mid-1
  3. 若key>R[mid].key,则low=mid-1

折半查找

int search_bIN(SSTable ST,KeyType key){
    low=1;high=ST,length;
    while(low<=high){
        mid=(low+high)/2;
        if(ST.R[mid].key==KEY)return mid;
        else 
            if(key<ST.R[mid].key)
                high=mid-1;
            else low=mid+1;
    }
    return 0;
}

$\large ASL=1/11*(11+22+43+44)=33/11=3$
平均查找长度ASL（成功时）
- $设表长为n=2^h-1,则h=log_2(n+1)，且表中每个记录的查找概率相等：p_i=1/n$
  
  $则\begin{align}
  ASL_{bs}&=\dfrac {1}{n} \sum\limits ^{n}_{j=1}j*2^{j-1}\
  &=\dfrac{n+1}{n}log_2(n+1)-1\
  &≈log_2(n+1)-1(n>50)\end{align}$
- 折半查找的性能分析
  - 优点：效率比顺序查找高
  - 缺点：只适用于有序表，且限于顺序存储结构(对线性链表无效)

7.2.3 分块查找

分块查找 (Blocking Search) 又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法。
1. 将表分成几块,且表或者有序，或者分块有序
2. 建立“索引表”（每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序）。
查找过程：先确定待查记录所在块，再在块内查找
查找效率：$ASL=L_b+L_w$
$\large ALS_{bs}≈log_2(\dfrac{n}{s}+1)+\dfrac {s}{2}$ s为每块内部的记录个数，n/s即块内数目
分块查找的特点
- 优点：插入和删除比较容易
- 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算
- 适用情况：线性表既要快速查找又要经常动态变化

	顺序查找	折半查找	分块查找
ASL	最大	最小	中间
表结构	有序表、无序表	有序表	分块有序
存储结构	顺序表、线性链表	顺序表	顺序表、线性链表

7.3 树表的查找

当表插入、删除操作频繁时，为了维护表的有序性，需要移动表中很多记录
- 改用动态查找表——几种特殊的树
- 表结构在查找过程中动态生成
- 对于给定值key，若表中存在，则成功返回；否则，插入关键字等于key的记录
  - 二叉排序树
    平衡二叉树
    红黑树
    B-树
    B+树
    键树

7.3.1 二叉排序树

二叉排序树又称为二叉搜索树、二叉查找树
- 二叉排序树或是空树，或是满足如下性质的二叉树；
  1. 若其左子树非空，则左子树上所有结点的值均小于根结点的值；
  2. 若其右子树非空，则右子树上所有结点的值均大于根结点的值；
  3. 其左右子树本身又各是一棵二叉排序树
- 二叉排序树的性质
  - 中序遍历非空的二又排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。
二叉排列树的操作——查找
- 若查找的关键字等于根结点，成功
- 否则
  - 小于根结点，查左子树
  - 大于根结点，查右子树
- 在左右子树上的操作类似

算法描述

BSTree SearchBST (BSTree_T,KeyType key){
    if ((!T)||key==T->data.key) return T;
    else if (key<T->data.key)
        return SearchBST(T->lchild,key);
		 else return SearchBST (T->rchild,key);
}

二叉排序树的查找分析
- 含有n个结点的二叉排列树的平均查找长度和树的形态有关
  - 最好的情况：
    
    二叉排列树的形态和折半查找的判定树相似:
    
    $ASL=log_2(n+1)-1$
    $O(log_2n)$
  - 最坏情况
    
    二叉排序树的形态为单支树，树的深度为n，
    
    $ASL=\dfrac {n+1}{2}$
    
    $O(n)$
二叉排序树的操作——插入
- 若二叉排序树为空，则插入结点作为根结点插入到空树中
- 否则，继续在左右子树上查找
  - 树中已有，不再插入
  - 树中没有
    - 查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
- 插入的元素一定在叶子结点上
二叉排序树的操作——生成
- 一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。
- 插入的结点均为叶子结点，故无序移动其他结点。相当于在有序序列上插入记录儿无需移动其他记录
- 不同的插入次序的序列生成不同形态的二叉排序树
二叉排序树的操作——删除
- 被删除的结点是叶子结点：直接删去该结点
- 被删除的结点只有左子树或右子树，用其左子树或右子树替换它
- 被删除的既有左子树，也有右子树，以其中序前驱值替换之（前驱是左子树中最大的结点），然后再删除该前驱结点
  - 也可以用其后继替换之（后继是右子树中最小结点），然后再删除该后继结点

7.3.2 平衡二叉树

平衡二叉树的定义
- 又称AVL树
- 一棵平衡二叉树或者是空树，或者是具有以下性质的二叉排序树：
  - 左子树与右子树的高度之差的绝对值小于等于1；
  - 左子树和右子树也是平衡二叉排序树。
为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子
- 根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1，0，或1
- 对于一棵有n个结点的AVL树，其高度保持在$O(log_2n)$数量级，ASL也是保持在$O(log_2n)$量级
- 当我们在一个平衡二叉树上插入结点时，可能导致失衡
  - 平衡调整的四种类型：
    
    LR型和RL型左右要看B和A哪个大
    - 调整原则：1. 降低高度 2. 保持二叉排序树性质

7.4 哈希表的查找

7.4.1 散列表的基本概念

基本思想：记录的存储位置与关键字之间存在对应关系

对应关系——hash函数（hash:散列）

Loc(i)=H(keyi)

散列表的查找
- 根据散列函数H(key)=k
  - 查找key=9，直接访问H(9)=9号地址，若内容为9则成功
    若查不到，则返回一个特殊值，如空指针或空记录。
- 优点：查找效率高
  缺点：空间效率低
散列函数和散列地址：在记录的存储位置p和其关键字key 之间建立一个确定的对应关系H, 使 p=H(key ), 称这个对应关系H为散列函数，p为散列地址。
散列表：一个有线连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标
冲突：不同的关键码映射到同一个散列地址
- key1≠key2，但是H(key1)=H(key2)
- 冲突是不可避免的，但可以减少
同义词：具有相同函数值的多个关键字

7.4.2 散列函数的构造方法

构造散列函数的考虑因素：
- 散列表的长度
- 关键字的长度
- 关键字的分布情况
- 计算散列函数所需的时间
- 记录的查找频率
构造号的散列函数要遵循以下两条原则
- 函数计算要简单，每一个关键字只能有一个散列地址与之对应
- 函数的值域需在表长的范围内，计算出的散列地址的分布应均匀，尽可能减少冲突。
根据数据元素的集合特性构造
- 要求一: n个数据原仅占用n个地址虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小
- 要求二:无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。

7.4.2.1 直接定址法

Hash(key)=a.key+b
优点：以关键码key的某个线性函数值为散列地址，不会产生冲突
缺点：要占用连续的地址空间，空间效率低

7.4.2.2 除留余数法

Hash(key)=key mod p
- 技巧：设：表长为m，取p<=m且为质数
  - 例：{15,23,27,38,53,61,70}
    
    散列函数：Hash(key)=key mod 7
    
    0 1 2 3 4 5 6
    
    70 15 23 38 53 61 27

7.4.3 处理冲突的方法

7.4.3.1 开放地址法（开地址法）

基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入
- 列入：除留余数法：$H_i=(Hash(key)+d)mod \ m$
- 常用方法：
  - 线性探测法 $d_i为1,2,……，m-1线性序列$
  - 二次探测法 $d_i为1^2,-1^2,2^2,-2^2……，q^2二次序列$
  - 伪随机探测法 $d_i为伪随机数序列$
例：关键码集为：{47，7，29，11，16，92，22，8，3}，散列表长m=11，散列函数为$Hash(key)=key \ mod \ 11$,拟用线性探测法处理冲突

0 1 2 3 4 5 6 7 8 9 10

11 22 47 92 16 3 7 29 8
- 使用线性探测法解释：
1. 47、7均是由散列函数得到的没有冲突的散列地址;
2. Hash(29)=7，散列地址有冲突，需寻找下一个空的散列地址由$H=(Hash(29)+1) mod \ 11=8$，散列地址8为空，因此将29存入。
3. 11、16、92均是由散列函数得到的没有冲突的散列地址:
4. 另外，22、8、3同样在散列地址上有冲突，也是由H,找到空的散列地址的。
  - 平均查找长度ASL=(1+2 +1 +1 +1 +4 +1 +2 +2)/9=1.67
0 1 2 3 4 5 6 7 8 9 10

11 22 3 47 92 16 7 29 8
- 使用二次探测法解释：
  - Hash(3)=3散列地址有冲突，由于$H_1=(Hash(3)+1^2)mod \ 11=4$，仍然冲突；
  - $H_2=(Hash(3)-1^2)mod \ 11=2$找到空的散列地址，存入

7.4.3.2 链地址法（拉链法）

基本思想：相同散列地址的记录链成一单链表
m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态结构。
链地址法建立散列表的步骤
- step1：取数据元素的关键字key，计算其散列函数值 (地址)。若该地址对应的链表为空，则将该元素插入此链表；否则执行Step2解决冲突。
- step2：根据选择的冲突处理方法，计算关键字key的下一个存储地址若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表
链地址法的优点：
- 非同义词不会冲突，无“聚集”现象
  - 链表上的结点空间动态申请，更适合于表长不确定的情况

7.4.4 散列表的查找

给定值查找值k，查找过程：

graph TD
A[给定k值]==>B(计算H)
B==>C{此地址为空}
C-->|N|D{关键字==k}
C-->|Y|G[查找失败]
D-->|N|E[案处理冲突方法计算Hi]
D-->|Y|H[查找成功]
E-->C
F[竖向流程图]

$ASL=(16+2+33+4+9)/12=2.5$
用连地址法处理冲突：
$ASL=(16+24+3+4)/12=1.75$
使用平均查找长度ASL来衡量查找算法，ASL取决于
- 散列函数
- 处理冲突的方法
- 散列表的装填因子α
  - $\Large α=\dfrac {表中填入的记录数}{哈希表的长度}$
  - α越大，表中的记录数越多，表越满，发生冲突的可能性就越大，查找时比较次数就越多
- 无冲突时才能达到O(1)
- $\large ASL≈1+\dfrac {α}{2}$
- $\large ASL≈\dfrac {1}{2}(1+\dfrac{1}{1-α})$
- $\large ASL≈-\dfrac{1}{α}ln(1-α)$
结论
- 链地址法优于开地址法
- 散列表技术具有很好的平均性能，优于一些传统的技术
- 除留余数法作散列函数优于其它类型函数

8 排序

8.1 基本概念和排序方法概述

8.1.1 排序的基本概念

排序：将一组杂乱无章的数据按照一定规律顺次排列起来，即，将无需数列排成一个有序序列（由小到大或由大到小）的运算。
- 如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言
- 排序方法的分类：
  - 按数据存储介质：内部排序和外部排序
    - 内部排序：数据量不大，数据在外存，无需内外存交换数据
    - 外部排序：数据量较大，数据在外存（文件排序）
      - 外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多
  - 按比价器个数：串行排序和并行排序
    - 串行排序：单处理机（同一时刻比较一对元素）
    - 并行排序：多处理机（同一时刻比较多对元素）
  - 按主要操作：比较排序和基数排序
    - 比较排序：用比较的方法
      - 插入排序、交换排序、选择排序、归并排序
    - 基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置
  - 按辅助空间：原地排序和非原地排序
    - 原地排序：辅助空间用量为O(1)的排序方法（所占用的辅助存储空间与参与排序的数据量大小无关）
    - 非原地排序：辅助空间用量超过O(1)的排序方法
  - 按稳定性：稳定排序和非稳定排序
    - 稳定排序：能够使任何数值相等的元素，排序以后相对次序不变。
    - 非稳定排序：不是稳定排序的方法
  - 按自然性：自然排序和非自然排序
    - 自然排序：输入数据越有序，排序的速度越快的排序方法
    - 非自然排序：不是自然排序的方法
接下来的学习内容：
按排序依据原则：
- 插入排序：直接插入排序、折半插入排序、希尔排序
- 交换排序：冒泡排序、快速排序
- 选择排序：简单选择排序、堆排序
- 归并排序:：2-路归并排序
- 基数排序
按排序所需工作量
- 简单的排序方法：$ T(n)=O(n^2)$
- 基数排序：$ T(n)=O(d.n)$
- 先进的排序方法：$ T(n)=O(nlogn)$

存储结构——记录序列以顺序表存储

1 2	#define MAXSIZE 20 //设记录不超过20个 typedef int KeyType; //设关键字为int型

Typedef struct{
    KeyType key;					//关键字
    infoType otherinfo;				//其他数据项
}RedType;

Typedef struct{					//定义顺序表的结构
    RedType r[MAXSIZE +1];		//存储顺序表的向量
    							//r[0]一般作哨兵或缓冲区
    int length;					
}SqList;

8.2 插入排序

基本思想：
- 在有序序列中插入一个元素，保持序列有序，有序长度不断增加
插入排序的种类
- 顺序法定位插入位置——直接插入排序
- 二分法定位插入位置——二分插入排序
- 缩小增量多遍插入排序——希尔排序

8.2.1 直接插入排序

直接插入排序——采用顺序查找法查找插入位置
1. 复制插入元素
2. 记录后移，查找插入位置
  1
  2
  for(j=i-1;j>=0&&x<a[j]；j--)
  a[j+1]=a[j];
3. 插入到正确位置
直接插入排序，使用“哨兵”
1. 复制为哨兵 L.r[0]=L.r[i];
2. 记录后移，查找插入位置
3. 插入到正确位置

void InserSort(SqList &L){
    int i,j;
    for(i=2;i<=L.length;++i){
        if(L.r[i].key<L.r[i-1].key){
            L.r[0]=L.r[i];
            for(j=i-1;L.r[0].key<L.r[j].key;--j){
                L.r[j+1]=L.r[j];
            }
        }
        L.r[j+1]=L.r[0];
    }
}

平均的情况：
- 比较次数$\sum\limits^{n-1}_{i=1} \dfrac{i+1}{2}=\dfrac{1}{4}(n+2)(n-1) $
- 移动次数$\sum\limits^{n-1}_{i=1} （\dfrac{i+1}{2}+1）=\dfrac{1}{4}(n+6)(n-1) $
时间复杂度结论
- 原始数据越接近有序，排序速度越快
- 最坏情况下（输入数据是逆有序的） $Tw(n)=O(n^2)$
- 平均情况下，耗时差不多是最坏情况的一半 $Te(n)=O(n^2)$
- 要提高查找速度
  - 减少元素的比较次数
  - 减少元素的移动次数

8.2.2 折半插入排序

void BinsertSort(SqList &L)｛   						//对顺序表L做折半插入排序
for (i=2;i<=L.length;++i){
    L.r[O]=L.r[i];
	low=l;high=i-1;
	while(low<=high){
        m=(low+high)/2;
		if(L.r[O].key<L.r[mid].key) high=mid-1;		//插入点在前一子表
		else low=mid+1;								//插入点在后一子表
    }
    for (j=i一l;j>=high+l; --j) L.r[j+l]=L.r(j]; 	//记录后移
	L.r[high+l]=L.r[O]; 							//将r[O]即原r[i], 插入到正确位置
	}
}

算法特点：
- 稳定排序
- 应为要进行折半查找，所以只能用于顺序结构，不能用于链式结构
- 适合初始记录无序，n较大时的情况
算法分析：
- 时间复杂度为$O(n^2)$
- 空间复杂度为$O(1)$

8.2.3 希尔排序

基本思想：
- 先将整个待排记录序列分割成若干子序列，分别进行直接插入排序待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
算法特点：
- 一次移动，移动位置较大，跳跃式地接近排序后的最终位置
- 最后一次只需要少量移动
- 增量序列必须是递减的，最后一个必须是1
- 增量序列应该是互质的
算法举例：

算法代码：

void shellsort(Sqlist &L,int dlta[],int t){
    for(k=0;k<t;++k)
        shellinsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序
}

void shellinert（SqList &L，int dk)
    for(i=dk+1;i<=L.length;++i)
        if(r[i].key<r[i-dk].key){
            r[0]=r[i];
            for(j=i-dk;j>0 &&（r[0].key<r[j].key);j=j-dk)
                r[j+dk]=r[j];
            r[j+dk]=r[0]
        }

算法分析：
- 时间复杂度是n和d的函数：
  - $O(N^{1.25})到O(1.6n^{1.25})——经验公式 $
  - 时间复杂度为$O(1)$
  - 是一种不稳定的排序方法

8.3 交换排序

8.3.1 冒泡排序

基本思想：每趟不断将记录两两比较，并按“前小后大”规则交换

void bubble_sort(SqList &L){
    int m,j,i; RedType x;
    for(m=1;m<=n-1;m++){
        for(j=1j=n-m;j++)
            if(L.r[j].key>L.r[j+1].key){
                x=L.r[j];
                L.r[j]=L.r[j+1];
                r[j+1]=x
            }
    }
}

改进的冒泡排序算法

void bubble_sort(SqList &L){
    int m,j,i,flag=1; RedType x; 
    for(m=1;m<=n-1&&flag==1;m++){		//用flag作为是否有交换的标记
        flag=0；
        for(j=1j=n-m;j++)
            if(L.r[j].key>L.r[j+1].key){
           		flag=1 					//若发生交换，flag置为1
                x=L.r[j];
                L.r[j]=L.r[j+1];
                r[j+1]=x
            }
    }
}

冒泡排序算法评价
- 冒泡排序最好时间复杂度是$O(n)$
- 冒泡排序最坏时间复杂度为$(n^2)$
- 冒泡排序平均时间复杂度为$O(n^2)$
- 冒泡排序算法中增加一个辅助空间temp，辅助空间为$S(n)=O(1)$
- 冒泡排序是稳定的

8.3.2 快速排序

基本思想
- 任取一个元素为中心
- 所有比他小的元素一律前放，比他大的后放，形成左右两个子表
- 对各子表重新选择中心元素并依此规则调整
- 知道每个子表的元素只剩一个
快速排序演示
算法图解：

排序算法：

int partition(SqList &L,int low,int high){
    L.r[0]=L.r[low];									//用子表的第一个记录做枢轴记录
    pivotkey=L.r[low].key;								//枢轴记录关键字保存在pivotkey中
    while(low<high){									//从表的两端交替地向中间扫描
        while(low<high&&L.[high].key>=pivotkey)--high;
        L.r[low]=L.r[high];								//将比枢轴记录小的移动到低端
        while(low<high&&L.[low].key>=pivotkey)++low;
        L.r[high]=L.r[low];								//将比枢轴记录大的移动到高端
    }
    L.r[low]=L.r[0];									//枢轴记录到位
    return low;											//返回枢轴记录
}
void QSort(SqList &L,int low,int high){
    if(low<high){
        pivotloc=Partition(L,low,high);					//将L.r[low,high]一分为二。pivotloc是枢轴记录
        QSort(L,low,pivotloc-1);						//对左子表递归排序
        QSort(L,pivotloc+1,high);						//对右子表递归排序
    }
}
void QuickSort(SqList &L){
    QSort(L,1,L.length);								//对顺序表L做快速排序
}

快速排序算法分析：
- 时间复杂度
  - 平均计算时间是$O(nlog_2n)$
  - 实验表明快速排序是我们所讨论的所有内排序方法中最好的一个。
- 空间复杂度
  - 快速排序不是原地排序
  - 平均情况下：需要$O(logn)$的栈空间
  - 最坏情况下：栈空间可达$O(n)$
- 快速排序不适于队原本有序或基本有序的记录序列进行排序

8.4 选择排序

8.4.1 简单选择排序

基本思想：
- 在待排序的数据中选出最大(小)的元素放在其最终的位置。

算法代码

void SelectSort(SqList &K){
    for(i=1;i<L.length;++i){
        k=i;
        for(j=i+1;j<=L.length;j++)
            if(L.r[j].key<L.r[k].key)k=j;		//记录最小值位置
        if(k!=i){
            x=L.r[i];
            L.r[i]=L.r[k];
            L.r[k]=x;
        }
    }
}

算法分析
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
简单选择排序是不稳定排序

8.2.2 堆排序

若有n个元素${a_1,a_2,……,a_n}$满足
$$
\left{
\begin{array}{l}
a_i<=a_{2i}\
a_i<=a_{2i+1}\
\end{array}
\right.
\quad\text{或者}\quad
\begin{cases}
a_i>=a_{2i}\
a_i>=a_{2i+1}\
\end{cases}
$$
- 则分别称该序列为小根堆和大根堆。
- 从堆定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于(大于)它的孩子结点
若在输出堆顶的最小值 (最大值) 后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值 (次大值) …如此反复，便能得到一个有序序列，这个过程称之为堆排序。
堆的调整
- 小根堆
  1. 输出堆顶元素之后，以堆中最后一个元素替代之
  2. .然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换，
  3. 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选“

算法描述

void HeapAdjust(elem R[],int s, int m){
    rc=R[s];
    for(j=2*S;J<=M;J*=2){//沿key较大的孩子结点向下筛选
        if(j<m&&R[j]<R[j+1])++j;//j为key较大的记录的下标
        if(rc>=R[j])break;
        R[s]=R[j];
        s=j;//rc应插入在位置s上
    }
    R[s]=rc;//插入
}

堆的建立
- 单结点的二又树是堆;
- 在完全二叉树中所有以叶子结点 (序号i > n/2) 为根的子树是堆这样，我们只需依次将以序号为$n/2，n/2-1，…,1$的结点为根的子树均调整为堆即可。
  
  从最后一个非叶子结点开始，以此向前调整
  1. 调整从第$n/2$个元素开始，将以该元素为根的二叉树调整为堆
  2. 将以序号为$n/2 - 1$的结点为根的二叉树调整为堆
  3. 再将以序号为$n/2 - 2$的结点为根的二又树调整为堆
  4. 再将以序号为$n/2 - 3$的结点为根的二又树调整为堆
- 通过以上分析可知：
  - 若对一个无序序列建堆，然后输出根；重复该过程就可以由一个无序序列输出有序序列。
  - 实质上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的

堆排序算法

void HeapSort（elem R[]){			//对R[1]到R[n]进行堆排序
    int i;
    for(i=n/2;i>=1;i--)
        HeapAdjust(R,i,n);			//建立初始堆
    for(i=n;i>1;i--){				//进行n-1趟排序
        Swap(R[1],R[i]);			//根与最后一个元素交换
        HeapAdjust(R,1,i-1);		//对R[1]到R[i-1]重新建堆
    }
}

算法分析
- 初始化堆所需时间不超过O(n)
- 堆排序在最坏情况下，其时间复杂度也为$O(nlog_2 n)$，这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于"最好”或"最坏“的状态。

8.5 归并排序

基本思想：
- 将两个或两个以上的有序子序列“归并”为一个有序序列
- 在内部排序中，通常采用的是2-路归并排序。
排序示例：
- 整个归并排序仅需[$log_2 n $]趟
算法分析：
- 时间效率：$O(nlog_2n)$
- 空间效率：$O(n)$、
  - 因为需要一个与原始序列同样大小的辅助序列。这正是此算法的缺点
- 具有稳定性

8.6 基数排序

基本思想：
- 分配+收集
- 也叫桶排序或箱排序: 设置若干个箱子，将关键字为k的记录放入第k个箱子，然后在按序号将非空的连接。
算法示例：
- 将这组数据第一趟按照个位排，然后收集回来
- 接下来按照十位来排，接下来收集回来
- 最后按照百位来排，收集回来时，我们可以发现已经有序了
算法分析
- 时间效率：O(k*(n+m))
  - k：关键字个数
  - m：关键字取值范围位m个值
总结：

数据结构与算法基础

1 绪论

1.1 数据结构研究内容

1.2 基本概念和术语

1.2.1 数据、 数据元素、 数据项和数据对象

1.2.2 数据结构

1.2.3 数据类型和抽象数据类型

1.3 抽象数据类型的表示与实现

1.4 算法和算法分析

1.4.1 算法特性

1.4.2 算法设计的要求

1.4.3 算法的时间复杂度

1.4.4 算法的空间复杂度

1.5 小结

2 线性表

2.1 线性表的定义和特点

2.2 案例引入

2.2.1 一元多项式的运算

2.2.2 稀疏多项式的运算

2.2.3 图书信息管理系统

2.3 线性表的类型定义

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

2.4.1 线性表的顺序存储表示

2.4.2 顺序表的基本操作的实现

2.5 线性表的链式表示和实现

2.5.1 单链表的定义和表示

2.5.2 单链表基本操作和实现 （重点）

2.5.2.1 初始化

2.5.2.2 取值

2.5.2.3 查找

2.5.2.4 插入

2.5.2.5 删除

2.5.2.6 创建单链表

2.5.2.6.1 头插法——插到链表头部

2.5.2.6.2 尾插法——插到链表尾部

2.5.3 循环链表

2.5.4 双向链表

2.6顺序表和链表的比较

2.7 线性表的应用

2.7.1 线性表的合并

2.7.2 有序表的合并

2.8案例分析与实现

3 栈和队列

3.1 栈和队列的定义和特点

3.1.1 栈的定义和特点

3.1.2 队列的定义和特点

3.2 案例引入

3.2.1：括号匹配的检验

3.3.2：表达式求值

3.2.3：舞伴问题

3.3 栈的表示和操作的实现

3.3.1 栈的抽象数据类型和类型的定义

3.3.2 顺序栈的表示和实现

3.3.2.1 顺序栈的初始化

3.3.2.2 顺序栈的入栈

3.3.2.3 顺序栈的出栈

3.3.3 链栈的表示和实现

3.3.3.1 链栈的初始化

3.3.3.2 链栈的入栈

3.3.3.3 链栈的出栈

3.3.3.4 取栈顶元素

3.4栈与递归

3.5 队列的表示和操作的实现

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

3.5.2 队列的顺序表示和实现

4 串、数组和广义表

4.1 串的定义——几个术语

4.2 案例引入

4.2.1 病毒感染检测

4.3 串的类型定义、存储结构及运算

4.3.1 串的抽象类型定义

4.3.2 串的存储结构

4.3.2.1 串的顺序存储结构

4.3.2.2 串的链式存储结构

4.3.3 串的模式匹配算法

4.3.3.1 BF算法

4.3.3.2 KMP算法

4.4 数组

4.4.1 数组的类型定义

4.4.2 数组的顺序存储

1.2.1 数据、数据元素、数据项和数据对象

2.5.2 单链表基本操作和实现（重点）