从0到1学习数据结构与算法（更新中）

第一章

0.数据结构的研究内容

研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。

实践中即设计出合适的数据结构及相应的算法即：首先要考虑对相关的各种信息如何表示、组织和存储？

1.基本概念和术语

1.数据（data）：
所有能输入到计算机中去的描述客观事物的符号。

数值性数据（实数、整数）
非数值性数据（多媒体信息处理：字符串、图形、图像、声音）

2.数据元素（data element）：
数据的基本单位，也
称结点（node）或
记录（record）

3.数据项（data item）：
组成数据元素的、有独立含义的、不可分割的数据最小单位，也称域/字段(field)

4、数据对象(Data Object)：
相同特性数据元素的集合，是数据的一个子集

5、数据结构（Data Structure）
是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构的两个层次：

• 逻辑结构:数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型

• 存储结构（物理结构）:数据元素及其关系在计算机存储器中的存储方式。

一、逻辑结构

分法1：

• 线性结构—-
  有且仅有一个开始和一个终端结点
  ，并且所有结点都最多只有一个直
  接前趋和一个后继。
  例如：线性表、栈、队列、串
• 非线性结构—-
  一个结点可能有多个直接前趋和直
  接后继。
  例如：树、图

分法2：

二、存储结构

存储结构分为：

• 顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。（需要一片连续存储空间，一般借助数组来描述）
• 链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑系。（无需占用一整块存储空间）

数据的运算

逻辑结构和存储结构都相同, 但运算不同, 则数据结构不同. 例如, 栈与队列

对于一种数据结构, 常见的运算:
插入 删除 修改 查找 排序

数据类型：在一种程序设计语言中，变量所具有的数据种类

FORTRAN语言：整型、实型、和复数型
C语言：基本数据类型： char int float double void
       构造数据类型：数组、结构体、共用体、文件

抽象数据类型

• 更高层次的数据抽象。
• 由用户定义，用以表示应用问题的数据
  模型。
• 由基本的数据类型组成, 并包括一组相关
  的操作。

抽象数据类型可以用以下三元组表示：

ADT=(D,S,P)
D是数据对象
S是D上的关系集
P是D上的操作集

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

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

（1）预定义常量及类型

//预定义常量：函数结果状态代码
#define OK 1
#define ERROR 0
#define OVERFLOW 2
//预定义类型status是函数返回值类型，其值是函数结果状态代码。
typedef int Status; //给类型定义新名字

（2）数据元素被约定为ElemType类型，用户需要根据具体情况，自行定义该数据类型。

（3）算法去描述为以下的函数形式：

函数类型 函数名（函数参数表）
{
  语句序列;
}

（4）内存的动态分配与释放
使用new和delete动态分配和释放内存空间

分配空间 指针变量=new数据类型；

释放空间 delete指针变量；

（5）赋值语句

（6）选择语句

（7）循环语句

（8）使用的结束语句形式有

• 函数结束语句retum
• 循环结束语句break;
• 异常结束语句exit（异常代码）

（9）输入输出语句形式有

• 输入语句cin(scanf())
• 输出语句cout(printf())

（10）扩展函数有

• 求最大值max
• 求最小值mm

3.算法与算法分析

3.1一些定义与理解

算法：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列

算法的描述：

自然语言
流程图
程序设计语言
伪码

算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量

• 问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示
• 算法的执行时间大致等于所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积，一条语句的重复执行次数被称为语句频度
• 算法分析并非统计精确执行时间
• 若每条语句执行一次所需时间均是单位时间，则一个算法的
  执行时间可用算法的所有语句（通常只考虑“基本语句”）频度之和度量。
• 基本语句：指算法中重复执行次数和算法的执行时间成正比
  的语句

3.2时间复杂度的渐进表示法

通常，算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：T(n)=O(f(n))

  n越大算法的执行时间越长
  ·排序：n为记录数
  ·矩阵：n为矩阵的阶数
  ·多项式：n为多项式的项数
  ·集合：n为元素个数
  ·树：n为树的结点个数
  ·图：n为图的顶点数或边数

3.3分析时间复杂度的基本方法

• 找出语句频度最大的那条语句作为基本语句
• 计算基本语句的频度得到问题规模月的某个函数／(n)
• 取其数量级用符号“0“表示

3.4渐进空间复杂度

空间复杂度：算法所需存储空间的度量，记作： S(n)=O(f(n))
其中n为问题规模（或大小）

第二章

线性结构：
线性结构表达式：（a1 , a2 , ……, an）

线性结构的特点：

① 只有一个首结点和尾结点；
② 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。

简言之，线性结构反映结点间的逻辑关系是 一对一 的
线性结构包括线性表、堆栈、队列、字符串、数组等等，
其中，最典型、最常用的是线性表

1线性表的定义和特点

线性表的定义：用数据元素的有限序列表示

数据元素都是字母; 元素间关系是线性

同一线性表中的元素必定具有相同特性

2案例引入

总结：

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

3线性表的类型定义

线性表的重要基本操作

初始化,取值，查找，插入，删除

ADT List{
数据关系：R={<a i-1 ,ai>lai-1 pai ED,i=2,…,n}
基本操作：
Init List{&L}
操作结果：构造一个空的线性表L。
Destroy List(&L)
初始条件：线性表L已存在.
操作结果：销毁线性表L。
Clear List I EL
初始条件：线性表L已存在。
操作结果：将L重置为空表。
List Empty(L)
初始条件：线性表L已存在。
操作结果：若L为空表，则返回true，否则返回 false o
List Length(L)
初始条件：线性表L已存在
操作结果：返回中数据元素个数。
Get El em（L，i,&e）
初始条件：线性表L已存在，且１≤i≤List Length(L)。
操作结果：用e返回中第1个数据元素的值，
Locate El em(L,e)
初始条件：线性表L已存在，
操作结果：返回L中第1个值与e相同的元素在L中的位置。若这样的数据元素不存在，则返回值为0。
Prior El em(I,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无定义。
List Insert(&L,ive)
初始条件：线性表L已存在，且1≤i≤List Length(L)+1 o
操作结果：在L中第i个位置之前插人新的数据元索e，L的长度加1。
List Delete l&L i
初始条件：线性表L已存在且非空，且1≤i≤List Length（L）。
操作结果：删除L的第i个数据元素，L的长度减1。
初始条件：线性表L已存在。
操作结果：对线性表工进行遍历，在遍历过程中对工的每个结点访问一次。
}ADT List

• 抽象数据类型仅为模型
  定义，不涉及具体实现
• 该抽象数据类型给出的
  操作是基本操作，基于
  此可以构成其他更复杂
  操作
• 对于不同应用，基本操
  作的接口可能不同
• 抽象数据类型定义的线
  性表可根据实际所采用
  的存储结构形式进行具
  体的表示和实现

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

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

顺序存储
把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。简言之，逻辑上相邻，物理上也相邻

顺序存储
用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现

4.1顺序表的类型定义

#define MAXSIZE 100 //最大长度
typedef struct //定义顺序表结构体
{
ElemType *elem; //指向数据元素的基地址， ElemType为统一描述而定义，实际使用用基本类型或者结构体替换
int length; //线性表的当前长度（注意：C语言中数组的下标是从0开始，元素位置序号是从1开始） 
}SqList； //顺序表的结构类型为SqList，结构体别名

一元多项式

#define MAXSIZE 100 //多项式可能达到的最大长度
typedef struct //多项式非零项的定义
{ 
float coef; //系数
int expn; //指数
}Polynomial; 
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; //存储空间的基地址（ElemType 为Book结构体）
int length; //图书表中当前图书个数
}SqList; //图书表的顺序存储结构类型为SqList

补充：C语言的动态分配函数（ <stdlib.h> ）

malloc(m)
//开辟m字节长度的地址空间，并返回这段空间的首地址
sizeof(x)
//计算变量x的长度。
free(p)
// 释放指针p所指变量的存储空间，即彻底删除一个变量

4.2线性表的重要基本操作

初始化

参数用引用的情况:

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

参数用指针的情况:

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

补充：几个简单基本操作的算法实现

销毁线性表L:
void DestroyList(SqList &L)
{
if (L.elem) delete[]L.elem;
//释放存储空间（如果存在元
素） 
}

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

求线性表L的长度:
int GetLength(SqList L)
{
return (L.length); 
}

判断线性表L是否为空:
int IsEmpty(SqList L)
{
if (L.length==0) return 1; 
else return 0;
}

取值

随机存取

获取线性表L中的某个数据元素的内容:

int GetElem(SqList L, int i, ElemType &e) {
if (i<1||i>L.length) return ERROR;
//判断i值是否合理，若不合理，返回ERROR
e=L.elem[i-1]; //第i-1的单元存储着第i个数据
return OK;
}

查找

在线性表L中查找值为e的数据元素:

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

平均查找长度（ASL）：在执行查找时，为确定元素在顺序表中的位置，须和给定值进行比较的数据元素个数的期望值成为查找算法在查找成功时的平均查找长度（ASL）。

最好的情况：需比较1次
最坏的情况：需比较n次
如果每个元素的查找概率相等，即p=1/n,

则平均查找长度为 (n+1)/2

平均时间复杂度O(n)

插入

• 插第 4 个结点之前，移动 6-4+1 次
• 插在n个元素的第 i 个结点之前，移动 n-i+1 次

【算法步骤】

1.判断插入位置i 是否合法。

2.判断顺序表的存储空间是否已满。

3.将第n至第i 位的元素依次向后移
动一个位置，空出第i个位置。

4.将要插入的新元素e放入第i个位置

5.表长加1，插入成功返
回OK。

【算法描述】

Status ListInsert_Sq (SqList &L, int i, ElemType e)
{
if (i<1 || i>L.length+1) return ERROR; //i值不合法
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; //将新元素e放入第i个位置
++L.length; //表长增1
return OK;
}

【算法分析】

算法时间主要耗费在移动元素的操作上

• 若插入在尾结点之后，则根本无需移动（特别快）；
• 若插入在首节点之前，若元素全部后移（特别慢）；
• 若要考虑在各种位置插入（n个元素，共n+1种插入可能）的平均移动次数

平均移动次数（AMN）n/2

平均时间复杂度O(n)

删除

【算法步骤】

（1）判断删除位置 i 是否合法（合法值为1≤i≤n）。

（2）将第i+1至第n 位的元素依次向前移动一个位置。

（3）表长减1，删除成功返回OK。

【算法描述】

将线性表L中第i个数据元素删除

 Status ListDelete_Sq(SqList &L,int i) {
if((i<1)||(i>L.length)) return ERROR; //i值不合法
for (j=i; j<=L.length-1; j++) 
L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
--L.length; //表长减1
return OK;
}

【算法分析】

算法时间主要耗费在移动元素的操作上

• 若删除尾结点，则根本无需移动（特别快）；
• 若删除首结点，则表中n-1个元素全部前移（特别慢）；
• 若要考虑在各种位置删除（n个元素，共n种可能）的平均移动次数，该如何计算？

平均移动次数 (n-1)/2

平均时间复杂度O(n)

4.3顺序表的特点

• 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即 线性表的逻辑结构与存储结构一致

• 在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等

这种存取元素的方法被称为随机存取法!

优点:
存储密度大（结点本身所占存储量/结点结构所占存储量）
可以随机存取表中任一元素

缺点:
在插入、删除某一元素时，需要移动大量元素
初始分配固定空间，浪费存储空间
属于静态存储形式，数据元素的个数不能自由扩充

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

链式存储结构
结点在存储器中的位置是任意
的，即逻辑上相邻的数据元素
在物理上不一定相邻

线性表的链式表示又称为非顺序映像或链式映像。

通过指针来实现

5.1与链式存储有关的术语

1、结点：数据元素的存储映像。由数据域和指针域两部分组成

2、链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构

3、单链表、双链表、循环链表：

• 结点只有一个指针域的链表，称为单链表或线性链表
• 有两个指针域的链表，称为双链表
• 首尾相接的链表称为循环链表

4、头指针、头结点和首元结点:

• 头指针是指向链表中第一个结点的指针
• 头结点是在链表的首元结点之前附设的一个结点 （不是第一个元素节点！！）；数据域内只放空表标志和表长等信息
• 首元结点是指链表中存储第一个数据元素a1的结点

5.2链表（链式存储结构）的特点

• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
• 访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等!!!

  这种存取元素的方法被称为 顺序存取法

链表的优缺点:

优点

• 数据元素的个数可以自由扩充
• 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高

缺点

• 存储密度小
• 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）

5.3单链表的定义和实现

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名

若头指针名是L，则把链表称为表L

单链表的存储结构定义

typedef struct LNode
{
ElemType data; //节点的数据域
struct LNode *next; //节点的指针域
}LNode,*LinkList;
// *LinkList为Lnode类型的指针

• LinkList与LNode *本质是等价的，Linklist定义单链表强调链表的头指针p，LNode定义指向单链表中任意节点的指针p

• 注意区分指针变量和结点变量两个不同的概念

    指针变量 p ：表示结点地址
  
    结点变量*p：表示一个结点
  

• 若p->data=ai, //p是指向第i个元素的ai的指针，

  则p->next是指向第i+1个元素的指针

  则p->next->data=ai+1

单链表基本操作的实现

初始化; 取值; 查找; 插入; 删除.

初始化

【算法步骤】

（1）生成新结点作头结点，用头指针L指向头结点。

（2）头结点的指针域置空

【算法描述】

Status InitList_L(LinkList &L)
{ 
L=new LNode; //头指针L指向头结点
L->next=NULL; //头结点的指针域置空（头结点的指针域指
向第一个节点）
return OK; 
}

补充：几个简单基本操作的算法实现

销毁:

Status DestroyList_L(LinkList &L)
{
LinkList p;
while (L) //只要链表头指针不为空
{
p=L; //链表的头指针赋值给p（用于辅助操作指针变量）
L=L->next; //链表头结点的指针赋值给头指针（头指针指
向下一个节点）
delete p; //删除指针p指向的节点
}
return OK;
}

清空:
Status ClearList(LinkList & L){// 将L重置为空表
LinkList p,q;
p=L->next; //p指向第一个元素结点
while(p) //没到表尾（当最后一个节点被删除后，p指针
将变为空指针）
{ 
q=p->next; //指针q指向下一个节点
delete p; //删除p指向的当前节点
p=q; //指针p指向下一个节点
}L->next=NULL; //头结点指针域为空
return OK;
}

求表的长度:
int ListLength_L(LinkList L){
//返回L中数据元素个数
LinkList p;
p=L->next; //p指向第一个结点
i=0; 
while(p){//遍历单链表,统计结点数
i++;
p=p->next; }
return i; 
}

判断表是否为空:
int ListEmpty(LinkList L)
{ 
//若L为空表，则返回1，否则返回0
if(L->next) //非空
return 0;
else
return 1;
}

取值

链表不是随机存取结构

【算法步骤】

• 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next。
• j做计数器，累计当前扫描过的结点数，j初值为1。当p指向扫描到的下一结点时，计数器j加1。
• 当j = i时，p所指的结点就是要找的第i个结点。

【算法描述】

int LocateELem_L (LinkList L，Elemtype e) 
{
//返回L中值为e的数据元素的位置序号，查找失败返回0
p=L->next; j=1;
while(p &&p->data!=e) 
{p=p->next; j++;} 
if(p) return j; 
else return 0;
}

查找

【算法步骤】

• 从第一个结点起，依次和e相比较。
• 如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址（第几个元素，注意j的初始值为1）；
• 如果查遍整个链表都没有找到其值和e相等的元素，则返回0 或“NULL”。

【算法描述】

int LocateELem_L (LinkList L，Elemtype e) 
{
//返回L中值为e的数据元素的位置序号，查找失败返回0
p=L->next; j=1;
while(p &&p->data!=e) 
{p=p->next; j++;} 
if(p) return j; 
else return 0;
}

插入

【算法步骤】

• 找到ai-1存储位置p
• 生成一个新结点*s
• 将新结点*s的数据域置为x
• 新结点*s的指针域指向结点ai
• 令结点 *p 的指针域指向新结点 *s

【算法描述】

int LocateELem_L (LinkList L，Elemtype e) 
{
//在L中第i个元素之前插入数据元素e 
Status ListInsert_L(LinkList &L, int i, ElemType e){ 
p=L; j=0; 
while(p&&j<i−1){p=p->next;++j;} //寻找第i−1个结点
if(!p || j>i−1) return ERROR; //i大于表长 + 1或者小于1 
s=new LNode; //生成新结点s 
s->data=e; //将结点s的数据域置为e 
s->next=p->next; //将结点s插入L中 p->next=s; 
return OK; 
}//ListInsert_L
}

删除

【算法步骤】

• （1）找到ai-1存储位置p
• （2）临时保存结点ai的地址在q中，以备释放
• （3）令p-＞next指向ai的直接后继结点
• （4）将ai的值保留在e中
• （5）释放结点ai的空间

【算法描述】

int LocateELem_L (LinkList L，Elemtype e) 
{
//将线性表L中第i个数据元素删除
Status ListDelete_L(LinkList &L,int i,ElemType &e){
p=L;j=0; 
while(p->next &&j<i-1){ //寻找第i个结点，并令p指向其前驱ai-1
p=p->next; ++j; 
} 
if(!(p->next)||j>i-1) return ERROR; //删除位置不合理(i>n或i<1)
q=p->next; //临时保存被删结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
e=q->data; //保存删除结点的数据域
delete q; //释放删除结点的空间
return OK; 
}//ListDelete_L
}

【算法分析】

-p->next = p->next->next 可以吗???

不行！节点ai无法释放空间

5.4链表的运算时间效率分析

1. 查找: 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。

2. 插入和删除: 因线性链表不需要移动元素，只要修改指针，在确定插入和删除位置后，时间复杂度为O(1)。

但是，如果要在单链表中进行前插或删除操作，由于要
从头查找前驱结点，所耗时间复杂度为 O(n) 。

5.5单链表的建立（前插法）

【算法步骤】

• 建立线性表的链式存储过程即是动态生成链表的过程
• 从一个空表开始，重复读入数据
  • 生成新结点*p
  • 将读入数据存放到新结点*p的数据域中
  • 将该新结点*p插入到链表的前端

【算法描述】

void CreateList_F(LinkList &L,int n){
//逆位序输入n个元素的值，建立带表头结点的单链表L 
L=new LNode; 
L->next=NULL; //先建立一个带头结点的单链表
for(i=n; i>0; --i){ 
p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=L->next;L->next=p; //插入到表头
} 
}//CreateList_F

5.6单链表的建立（尾插法）

【算法步骤】

• 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
• 初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点

【算法描述】

void CreateList_L(LinkList &L,int n){ 
//正位序输入n个元素的值，建立带表头结点的单链表L 
L=new LNode; 
L->next=NULL; //先建立一个带头结点的单链表
r=L; //尾指针r指向头结点
for(i=0;i<n;++i){ 
p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=NULL; r->next=p; //插入到表尾
r=p; //r指向新的尾结点
} 
}//CreateList_L

5.7循环链表

循环链表：表中最后一个节点的指针域指向头结点，整个链表形成一个环。

从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不到；

对循环链表，有时不给出头指针，而给出尾指针
可以更方便的找到第一个和最后一个结点

如何查找开始结点和终端结点？

开始结点：rear->next->next
终端结点：rear

循环链表的合并（Ta表尾连接Tb表头，Tb表尾连接Ta表头，去除Tb的表头）

示例：

LinkList Connect(LinkList Ta, LinkList Tb)
{//假设Ta、Tb都是非空的单循环链表
p=Ta->next;//①p存表头结点
Ta->next=Tb->next->next;//②Tb表头(Tb->next->next，即Tb第一个元素节点)连结Ta表尾(Ta->next)，注意不包括Tb的头结点！
deleteTb->next;//③释放Tb表头结点
Tb->next=p;//④Tb的表尾连接到Ta的头结点
return Tb;
}

约瑟夫问题

在罗马人占领乔塔帕特后39 个犹太人与约瑟夫及他的朋友躲到一个洞中39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式：

41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
然而约瑟夫和他的朋友并不想遵从，要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏

约瑟夫问题的解法

void Josephus ( int n, int m ) {
Firster ( ); //检验指针指向第一个结点
for ( int i = 0; i < n-1; i++ ) { //执行n-1次
for ( int j = 0; j < m-1; j++ ) Next ( );
//循环m次使current指向被删除结点
cout << “出列的人是” << GetElem_L ( ) << endl; //出列人员的数据
ListDelete ( ); //删去每一趟的第m结点
    }
}

5.8双向链表

单链表只能先后寻查其他节点，如要寻查节点的直接前驱则只能从表头指针出发，而双向链表可解决这个问题。

5.9双向链表的删除

对比单链表为什么用两个指针？

1. 节点a的后继指针域指向节点c
   p->prior->next=p->next;

2. 节点c的前驱指针域指向节点a
   p->next->prior=p->prior;

Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e)
{
if(!(p=GetElemP_DuL(L,i))) return ERROR; //在L中确定第i
个位置元素的位置指针p，p为空时元素不存在
e=p->data; //保存被删除节点的值
p->prior->next=p->next; //节点a的后继指针域指向节点c p->next->prior=p->prior; //节点c的前驱指针域指向节点a
delete p; //释放被删除节点空间
return OK; }

6顺序表和链表的比较

7线性表的应用

7.1线性表的合并

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

    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)) //La中不存在和e相同的元素
ListInsert(&La,++La_len,e); //将e插在La的最后并长度加1 
    }
}

7.2有序表的合并

已知线性表La 和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。

【算法步骤】－有序的顺序表合并

• 创建一个空表Lc，长度为La和Lb的长度之和
• 依次从 La 或 Lb中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止
• 继续将 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表的最后一个元素
pb_last=LB.elem+LB.length-1; //指针pb_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

【算法步骤】－有序的链表合并

• Lc指向La
• 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止。
• 继续将 La 或 Lb 其中一个表的剩余结点插入在Lc 表的最后。
• 释放 Lb 表的表头结点

【算法描述】－有序的链表合并

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;} //释放Lb的头结点
}

8总结

第三章

1 栈和队列的定义和特点

栈

01 定 义： 只能在表的一端（栈顶）进行插入和删除运算的线性表（受限）

02 逻辑结构：与线性表相同，仍为一对一关系

03 存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见       

04 运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则

05 实现方式：关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同
基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等

队列

01 定 义： 只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表

02 逻辑结构：与线性表相同，仍为一对一关系

03 存储结构：用顺序队列或链队存储均可

04 运算规则：先进先出（FIFO）

05 实现方式：关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同

2 案例引入

案例3.1 ：一元多项式的运算

案例3.2：号匹配的检验

案例3.3 ：表达式求值

案例3.4 ：舞伴问题

3 栈的表示和操作的实现

顺序栈的表示

#define MAXSIZE 100
typedef struct
{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈可用的最大容量
}SqStack;

顺序栈初始化

步骤：

(1)分配空间并检查空间是否分配失败，若失败则返回错误

(2)设置栈底和栈顶指针S.top = S.base;

(3)设置栈大小

Status InitStack( SqStack &S )
{
S.base =new SElemType[MAXSIZE]；//动态分配数组
空间给顺序栈
if( !S.base ) return OVERFLOW; //存储分配失败
S.top = S.base; //top初始为base，空栈
S.stackSize = MAXSIZE; //栈最大容量为MAXSIZE
return OK;
}

求顺序栈的长度

//初始为0，添加n个元素为n
int StackLength( SqStack S )
{
return S.top – S.base; }

清空顺序栈

//注意判断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; //base所指的内存被释放，但 是base所指的地址仍然不变
S.stacksize = 0; 
S.base = S.top = NULL; //必须要置空 }
return OK;
  }
}

顺序栈入栈

(1)判断是否栈满，若满则出错

(2)元素e压入栈顶

(3)栈顶指针加1

Status Push( SqStack &S, SElemType e) 
{
if( S.top - S.base== S.stacksize ) // 是否栈满
return ERROR; 
*S.top++=e; //元素e压入栈顶，栈顶指针加1（注意顺序！）
return OK;
}

顺序栈出栈

(1)判断是否栈空，若空则出错

(2)获取栈顶元素e

(3)栈顶指针减1

Status Pop( SqStack &S, SElemType &e) 
{
if( S.top == S.base ) // 栈空
return ERROR; 
e＝ *--S.top; //栈顶指针减1，栈顶元素赋值给e（注意顺序！）
return OK;
}

取顺序栈栈顶元素

(1)判断是否空栈，若空则返回错误

(2)否则通过栈顶指针获取栈顶元素

Status GetTop( SqStack S, SElemType &e) //此处是S而不是&S
{
if( S.top == S.base ) return ERROR; // 栈空
e = *( S.top – 1 ); 
return OK;
}

链栈的表示

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

链栈的初始化

void InitStack(LinkStack &S )
{
S=NULL; //构建一个空栈，栈顶指针置空
return OK;
}

判断链栈是否为空

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

链栈进栈

Status Push(LinkStack &S , SElemType e)
{
p=new StackNode; //生成新结点p 
if (!p) exit(OVERFLOW);
p->data=e; //新节点数据域置为e 
p->next=S; //将新节点插入栈顶
S=p; //让指针S指向栈顶
return OK; 
}

链栈进栈

Status Pop (LinkStack &S,SElemType &e)
{
if (S==NULL) return ERROR; //栈空返回错误
e = S-> data; //将栈顶元素赋值给e
p = S; //用p临时保存栈顶元素空间，以便释放
S = S-> next; //修改栈顶指针，指向下个元素
delete p; //释放原栈顶元素空间
return OK;
}

取链栈栈顶元素

SElemType GetTop(LinkStack S)
{
if (S==NULL) exit(1)；//栈非空
else return S–>data; //返回栈顶元素的
值，栈顶指针不变
}

4 栈与递归

以下三种情况常常用到递归方法：

• 递归定义的数学函数
• 可递归求解的问题
• 具有递归特性的数据结构

1. 递归定义的数学函数:
   

2. 具有递归特性的数据结构:
   •树:Root, Lchild, Rchild
   • 广义表 A=(a, A)

3. 可递归求解的问题:
   迷宫问题、汉诺塔（ Hanoi, 又称河内塔）问题、八皇后问题

4.1用分治法求解递归问题

分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解

必备的三个条件:

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

  分治法求解递归问题算法的一般形式：
  void X(参数表) {
  if （递归结束条件）可直接求解步骤；-----基本项
  else X（较小的参数）；------归纳项
  } 
  long Fact ( long n ) 
  {
  if ( n == 0) return 1; //基本项
  else return n * Fact (n-1); //归纳项
  }

  

任意函数之间调用过程

调用前, 系统完成:

(1) 将实参, 返回地址等传递给被调用函数

(2) 为被调用函数的局部变量分配存储区

(3) 将控制转移到被调用函数的入口

调用后, 系统完成:

(1) 保存被调用函数的计算结果

(2) 释放被调用函数的数据区

(3) 依照被调用函数保存的返回地址将控制转移到调用函数

尾递归 循环结构

long Fact ( long n ) 
{
if ( n == 0) 
return 1;
else 
return n * Fact (n-1);
}
long Fact ( long n ) {
t=1;
for(i=1; i<=n; i++)
t=t*i;
return t; 
}

单向递归 循环结构

虽然有一处以上的递归调用语句，但各次递归调用语句的
参数只和主调函数有关，相互之间参数无关，并且这些递
归调用语句处于算法的最后。
long Fib ( long n ) {// Fibonacci数列
if(n==1 || n==2) return 1; 
else return Fib (n-1)+ Fib (n-2);}

尾递归、单向递归->循环结构

long Fib ( long n ) {
if(n==1 || n==2) return 1;
else{
t1=1; t2=1;
for(i=3; i<=n; i++)
{
t3=t1+t2; 
t1=t2; 
t2=t3;
} 
return t3; }}

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

5.1队列的抽象数据类型

ADT Queue{

    数据对象:...
    数据关系:...
    基本操作：
    (1) InitQueue (&Q) //构造空队列
    (2) DestroyQueue (&Q) //销毁队列
    (3) ClearQueue (&S) //清空队列
    (4) QueueEmpty(S) //判空. --TRUE,
    (5) QueueLength(Q) //取队列长度
    (6) GetHead (Q,&e) //取队头元素
    (7) EnQueue (&Q,e) //入队列
    (8) DeQueue (&Q,&e) //出队列
    (9) QueueTraverse(Q,visit()) //遍历
}ADT Queue

5.2队列的抽象数据类型队列的顺序表示－－用一维数组base[M]

初始化定义

#define M 100 //最大队列长度
Typedef struct {
QElemType *base; //初始化的动态分配存储空间（表示
存储空间的基地址：对比顺序栈，队列的两个指针均
需要移动，栈的base指针不需要移动）
int front; //头指针
int rear; //尾指针
}SqQueue;

5.3循环队列

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


//构造一个空的队列
Status InitQueue (SqQueue &Q)
{
Q.base =new QElemType[MAXQSIZE] //为队列分配
一个数组空间
if(!Q.base) exit(OVERFLOW); //存储分配失败
Q.front=Q.rear=0; //头指针和尾指针置为0，队列为空
return OK;
}

求循环队列的长度

//返回Q的元素个数，即队列的长度
int QueueLength (SqQueue Q)
{
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

注意：非循环队列尾和头指针的差值就是队列长度，循环队列差值可能为负，故加上MAXQSIZE再与MAXQSIZE求余

循环队列入队

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; //队尾指针加1
return OK;
}

循环队列出队

Status DeQueue (LinkQueue &Q,QElemType &e)
{
//如果队列为空，返回错误
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front]; //保存队头元素
Q.front=(Q.front+1)%MAXQSIZE; //队头指针加1
return OK;
}

取循环队列的队头元素

//返回队头元素，不修改队头指针
SElemType GetHead (SqQueue Q)
{
if (Q.front != Q.rear) //队列非空
return Q.base[Q.front]; //返回队头元素的值，队头
指针不变
}

6 链队列

链队，链式存储结构实现的队列，通常用单链表表示。为便于操作，链队包含头结点，队头指针指向头结点。

//定义
typedef struct QNode{
QElemType data;
struct Qnode *next; }Qnode, *QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;

//初始化
Status InitQueue (LinkQueue &Q){
Q.front=Q.rear=new Qnode; //生成一个新节点作为头结
点，队头和队尾指针指向此节点
if (!Q.front) exit(OVERFLOW); //失败
Q.front->next=NULL; //头结点的指针域置空
return OK;
}

销毁链队列

Status DestroyQueue (LinkQueue &Q){
//从头节点开始，依次释放第1个元素（销毁操作开始前的队头节点）
，第2个元素，直到最后一个元素（销毁操作开始前的队尾节点）
while(Q.front){ //队头指针不为空
Q.rear=Q.front->next; //队尾指针指向对头指针指向的下 一个
节点
free (Q.front); //释放当前节点(第一次是头结点)
Q.front=Q.rear; //队头指针指向下一个节点（与队尾指针 指向同
一个节点） ，只要有节点未销毁，指针将不为空
} 
return OK;
}

判断链队列是否为空

Status QueueEmpty (LinkQueue Q)
{
return (Q.front==Q.rear); //链头是否等于链尾
}

取链队列的队头元素

Status GetHead (LinkQueue Q, QElemType &e){
if (Q.front==Q.rear) return ERROR; //空队列返回错误
e=Q.front->next->data; //返回队头元素的值，指针不变
return OK;
}

链队列入队

Status EnQueue(LinkQueue &Q,QElemType e){
p=new QNode; //为入队元素分配节点空间，用指针p指向
if(!p) exit(OVERFLOW);
p->data=e; //将新节点数据域置为e p->next=NULL; //将新节点指针域置为空（队尾）
Q.rear->next=p; //将队尾节点的指针域指向新节点
Q.rear=p; //移动队尾指针，指向新节点
return OK;
}

链队列入队

Status DeQueue (LinkQueue &Q,QElemType &e){
if(Q.front==Q.rear) return ERROR; //队列为空返回错误
p=Q.front->next; //p指向队头元素节点
e=p->data; //保存队头元素节点值
Q.front->next=p->next; //修改队头指针指向出队节点的下一个
if(Q.rear==p) Q.rear=Q.front; //若队尾节点出队，队尾指针指
向头节点
delete p; //释放原队头节点空间
return OK;
}

第四章

补充：C语言中常用的串运算

调用标准库函数 #include<string.h>
串比较，strcmp(char s1,char s2) 
串复制，strcpy(char to,char from)
串连接，strcat(char to,char from) 
求串长，strlen(char s)

4.1串

• 串(String)：零个或多个字符组成的有限序列
• 子串：串中任意个连续的字符组成的子序列称为该串的子串；
• 位置：字符在序列中的序号；
• 子串位置：子串的第一个字符在主串中的位置；
• 串相等：两个串的长度相等，且各个对应位置的字符都相等；
• 空格串：一个或多个空格组成的串
• 空串：零个字符的串，长度为零

4.2案例引入

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

然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染。

例如，假设病毒的DNA序列为baa，患者1的DNA序列为aaabbba，则感染，患者2的DNA序列为babbba，则未感染。

（注意，人的DNA序列是线性的，而病毒的DNA序列是环状的）

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

4.3.1类型定义

ADT String {
数据对象:…
数据关系:…
基本操作:
(1) StrAssign (&T,chars) //串赋值
(2) StrCompare (S,T) //串比较
(3) StrLength (S) //求串长
(4) Concat(&T,S1,S2) //串联
(5) SubString(&Sub,S,pos,len) //求子串
(6) StrCopy(&T,S) //串拷贝
(7) StrEmpty(S) //串判空
(8) ClearString (&S) //清空串
(9) Index(S,T,pos) //子串的位置
(11) Replace(&S,T,V) //串替换
(12) StrInsert(&S,pos,T) //子串插入
(12) StrDelete(&S,pos,len) //子串删除
(13) DestroyString(&S) //串销毁
}ADT String

4.3.2串的存储结构

顺序存储,链式存储

串的定长顺序存储结构

#define MAXLEN 255
typedef struct{
char ch[MAXLEN+1]; //存储串的一维数组
int length; //串的当前长度
}SString;

串的堆式顺序存储结构

设定固定串空间不尽合理，无法根据需要动态分配和释放字符数组空间，C语言中存在称为“堆”的自由存储区

typedef struct{
char *ch; //若串非空,则按串长分配存储区,
//否则ch为NULL
int length; //串长度
}HString;

串的链式存储结构

链表存储串值时可能存在：每个节点存放一个字符或多个字
符的情况

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

4.3.3 串的模式匹配算法

BF算法(重点)

Index(S, T, pos)

将主串S的第pos个字符和模式T的第1字符（j=1）比较，若相等，继续逐个比较后续字符；若出现某个字符等，从主串的下一字符（i=i-j+2）起，重新与模式的第一个字符（j=1）比较。

直到主串的一个连续子串字符序列与模式相等 。
返回值为S中与T匹配的子序列第一个字符的序号， 即匹配成功。

否则，匹配失败，返回值 0

BF算法描述

int Index(Sstring S, Sstring T, int pos){
i=pos; j=1; //初始化
while (i<=S.length && j <=T.length) //两个串均未比较到串尾
{
if ( S[ i ]=T[ j ]) {++i; ++j; } //继续比较后续字符
else{ i=i-j+2; j=1; } //指针后退重新开始匹配
}
if ( j>T.length) return i－T.length; //匹配成功，返回位置
else return 0; //匹配失败
}

核心：理解匹配失败后主串下一个位置

最好情况: 算法复杂度O(n+m)

最坏情况:总次数为：(n-m)*m+m＝(n-m+1)m; 若m<<n，则算法复杂度O(nm)

KMP算法

4.4数组

4.4.1类型定义

ADT Array {
数据对象:…
数据关系:…
基本操作:
(1) InitArray (&A,n,bound1, boundn) //构造数组A
(2) DestroyArray (&A) // 销毁数组A
(3) Value(A,&e,index1,…,indexn) //取数组元素值
(4) Assign (A,&e,index1,…,indexn) //给数组元素赋值
}ADT Array

二维数组常用：
LOC ( i, j ) = a + (i * n + j)L

4.4.2特殊矩阵的压缩存储

什么是压缩存储？

若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。

什么样的矩阵能够压缩？

一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。

什么叫稀疏矩阵？

矩阵中非零元素的个数较少（一般小于5%）

1. 对称矩阵
   [特点]:在n×n的矩阵A中，满足如下性质：aij=aji (1 ≤ i, j ≤ n)
   
   
   [存储方法]: 只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。
   
   

2. 三角矩阵
   [特点]:对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。
   
   
   存储方法: 重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间: sa[0.. n(n+1)/2]
   

3. 对角矩阵（带状矩阵）
   [ 特点]:在n×n的方阵中，非零元素集中在主对角线及其两侧共L(奇数)条对角线的带状区域内 — L对角矩阵。

4. 稀疏矩阵
   [ 特点]:大多数元素为零。

存储方法: 只记录每一非零元素(i, j, aij ) 节省空间，但丧失随机存取功能

4.5广义表

广义表（线性表的推广，也称为列表）： n ( 0 )个表元素组成的有限序列，记作LS = (a0, a1, a2, …, an-1)

LS是表名。
ai是表元素，它可以是表 (称为子表)，可以是数据元素(称为原子)。
n为表的长度。n = 0 的广义表为空表。

广义表与线性表的区别？

1. 线性表的成分都是结构上不可分的单元素
2. 广义表的成分可以是单元素，也可以是有结构的表
3. 线性表是一种特殊的广义表
4. 广义表不一定是线性表，也不一定是线性结构！

广义表的基本运算

1. 求表头GetHead(L):非空广义表的第一个元素，可以是一个单元素，也可以是一个子表求表尾
2. 求表尾GetTail(L):非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表

广义表的特点

1. 有次序性 一个直接前驱和一个直接后继
2. 有长度 ＝表中元素个数
3. 有深度 ＝表中括号的重数
4. 可递归 自己可以作为自己的子表
5. 可共享 可以为其他广义表所共享

4.6案例分析与实现

略QWQ

第五章

5.1树和二叉树的定义

5.1.1树的定义

树（Tree）是n（n≥0）个结点的有限集，它或为空树（n = 0）；或为非空树，对于非空树 T：

    有且仅有一个称之为根的结点；

    除根结点以外的其余结点可分为m（m＞0） 个互不相交的有限集T1, T2, …, Tm, 其中每一
    个集合本身又是一棵树，并且称为根的子树（SubTree）。

5.1.2基本术语

根 ——即根结点(没有前驱)

叶子 ——即终端结点(没有后继)

森林 ——指m棵不相交的树的集合(例如删除A后的子树个数)

有序树 ——结点各子树从左至右有序，不能互换（左为第一）

无序树 ——结点各子树可互换位置。

双亲 ——即上层的那个结点(直接前驱)

孩子 ——即下层结点的子树的根(直接后继)

兄弟 ——同一双亲下的同层结点（孩子之间互称兄弟）

堂兄弟 ——即双亲位于同一层的结点（但并非同一双亲）

祖先 ——即从根到该结点所经分支的所有结点

子孙 ——即该结点下层子树中的任一结点

结点 ——即树的数据元素

结点的度 ——结点拥有的子树数

结点的层次 ——从根到该结点的层数（根结点算第一层）

终端结点 ——即度为0的结点，即叶子

分支结点 ——即度不为0的结点（也称为内部结点）

树的度 ——树内各结点度的最大值

树的深度(或高度)——树中节点的最大层次数结

5.1.3二叉树的定义

二叉树（Binary Tree）是n（n≥0）个结点所构成的集合，它或为空树（n = 0）；或为非空树，对于非空树T：

1. 有且仅有一个称之为根的结点；
2. 除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。

二叉树基本特点： • 结点的度小于等于2 • 有序树（子树有序，不能颠倒）

5.2案例引入

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

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

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

5.5.1 遍历规则：

限定先左后右，则只有前3种情况，分别称之为先（根） 序遍历、中（根） 序遍历和后（根）序遍历

先序遍历算法

Status PreOrderTraverse(BiTree T){
if(T==NULL) return OK; //空二叉树
else{ 
cout<<T->data; //访问根结点
PreOrderTraverse(T->lchild); //递归遍历左子树
PreOrderTraverse(T->rchild); //递归遍历右子树
}
}

中序遍历算法

Status InOrderTraverse(BiTree T){
if(T==NULL) return OK; //空二叉树
else{ 
InOrderTraverse(T->lchild); //递归遍历左子树
cout<<T->data; //访问根结点
InOrderTraverse(T->rchild); //递归遍历右子树
}
}

后序遍历算法

Status PostOrderTraverse(BiTree T){
if(T==NULL) return OK; //空二叉树
else{ 
PostOrderTraverse(T->lchild); //递归遍历左子树
PostOrderTraverse(T->rchild); //递归遍历右子树
cout<<T->data; //访问根结点
}
}

• 如果去掉输出语句，从递归的角度看，三种算法是完全
  相同的，或说这三种算法的访问路径是相同的，只是访
  问结点的时机不同。
• 时间效率:O(n)//每个结点只访问一次
• 空间效率:O(n)//栈占用的最大辅助空间（树的深度，最坏情况为n）

5.5.2二叉树的建立：

递归算法

void CreateBiTree （BiTree &T）{
cin>>ch; //接受输入
if (ch==’#’) T=NULL; //递归结束，建空树
else{
T=new BiTNode; 
T-＞data=ch; //生成根结点
CreateBiTree(T-＞lchild); //递归创建左子树
CreateBiTree(T-＞rchild); //递归创建右子树
}
}

计算二叉树结点总数

• 如果是空树，则结点个数为0；
• 否则，结点个数为左子树的结点个数+右子树的结点个数再+1。

int NodeCount(BiTree T){
if (T == NULL ) return 0; //如果空树，则节点个数为0，
递归结束
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
//否则节点个数为左子树的节点个数+右子树的节点个数
+1
}

计算二叉树深度

• 如果是空树，则深度为0；
• 否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者加1。

int Depth(BiTree T){
//树的深度
if(T==NULL) 
return 0; //如果空树，深度为0
else 
{ 
int m=Depth(T->lchild); //递归计算左子树深度为m
int n=Depth(T->rchild); //递归计算右子树深度为n
if(m>n) 
return (m+1); //m和n较大者+1
else 
return (n+1); 
}
}

重要结论:
若二叉树中各结点的值均不相同，则：
由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，
但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。

5.5.3 线索化二叉树：

普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得
若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树

线索二叉树构造的实质是将二叉链表中的空指针改为前驱或后继的线索，线索化的过程即是遍历过程中修改空指针
的过程！

• 线索二叉树：构造的实质是在二叉树（图形式样）上加上线索信息（一般用虚线来表示）
• 线索链表：将二叉链表中的空指针改为前驱或后继的线索，
  线索化的过程即是遍历过程中修改空指针的过程！

5.6树和森林

以一组连续的存储单元存储树的结点，每个结点除了数据域data外，还附设一个parent域用以指示其双亲结点的位置
优缺点：
求结点的双亲和树的根十分方便， 但求结点的孩子时需要遍历整个结构

5.7哈夫曼树及其应用

5.7.1 哈夫曼树的构造：

基本思想：使权大的结点靠近根
操作要点：对权值的合并、删除与替换，总是合并当前值最小的两个

哈夫曼树的构造过程：

• 第一步：根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树。
• 第二步：在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。
• 第三步：在森林中删除这两棵树，同时将新得到的二叉树加入森林中。重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。

哈夫曼树构造算法的实现：

结点类型定义

typedef struct
{ 
int weght; //结点的权值
int parent, lch, rch; //结点的双亲、左孩子、右孩子
的下标
}*HuffmanTree; //动态分配数组存储哈夫曼树

数组[0…2n-1]的0号单元不使用，从1号单元开始使用，叶子
结点集中存储在前面部分l~n 个位置，而后面的n-1 个位置存
储其余非叶子结点

初始化

void CreatHuffmanTree (HuffmanTree HT, int n)
{
if (n<=1) return;
m=2*n-1;
HT=new HTNode[m+1]; //0号单元未用，HT[m]表示根结点
for(i=1; i<=m; ++i)
{ //l~m号单元中的双亲、左孩子，右孩子的下标都初始化为0
HT[i].lch=0; HT[i].rch=0; HT[i].parent=0;
}
for(i=1;i<=n;++i) //输人前n 个单元中叶子结点的权值
    cin>>HT[i].weight;

//构造 Huffman树
for (i=n+1; i<=m; ++i) 
{ Select (HT,i-1, s1, s2);
    //在HT[k](1≤k≤i-1)中选择两个其双亲域为0,
    // 且权值最小的结点,
    // 并返回它们在HT中的序号s1和s2
    HT[s1].parent=i; HT[s2] .parent=i; 
    //表示从F中删除s1,s2
    HT[i].lch=s1; HT[i].rch=s2 ; 
    //s1,s2分别作为i的左右孩子
    HT[i].weight=HT[s1].weight + HT[s2] .weight;
    //i 的权值为左右孩子权值之和
}
}

5.7.2 哈夫曼编码

基本思想：为出现次数较多的字符编以较短的编码。为确保对数据文件进行 有效的压缩和对压缩文件进行正确的解码，可以利用哈夫曼树来设计二进制编码。

哈夫曼树中，约定左分支标记为0，右分支标记为l，则根结点到每个叶子结点路径上的0、l序列即为相应字符的编码。

前缀编码：一个编码方案中，任一个编码都不是其他任
何编码的前缀（最左子串），则称编码是前缀编码，可
以保证对压缩文件进行解码时不产生二义性， 确保正确
解码。

哈夫曼树中，约定左分支标记为0, 右分支标记为l,则根结
点到每个叶子结点路径上的0、l序列即为相应字符的编码。

哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中
的每个左分支赋予0, 右分支赋予1，则从根到每个叶子的
路径上，各分支的赋值分别构成一个二进制串， 该二进
制串就称为哈夫曼编码

哈夫曼编码构造算法的实现

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n){
//从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中
HC=new 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; //释放临时空间
} // CreatHuffanCode

哈夫曼编码的几点结论：

• 哈夫曼编码是不等长编码。
• 哈夫曼编码是前缀编码，即任一字符的编码都不是另一字符编码的前缀。
• 哈夫曼编码树中没有度为1的结点。若叶子结点的个数为n，则哈夫曼编码树的结点总数为 2n-1。
• 发送过程：根据由哈夫曼树得到的编码表送出字符数据
• 接收过程：按左0、右1的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束

第六章

6.1图的定义和基本术语

图：Graph=(V, E)

V：顶点(数据元素)的有穷非空集合；
E：边的有穷集合。

• 无向图：每条边都是无方向的

• 有向图：每条边都是有方向的

• 完全图：任意两个点都有一条边相连
  

• 稀疏图：有很少边或弧的图

• 稠密图：有较多边或弧的图

• 网：边/弧带权的图

• 邻接：有边/弧相连的两个顶点之间的关系。

• 无序：存在边(vi, vj)，则称vi和vj互为邻接点

• 有序：存在弧<vi, vj>，则称vi邻接到vj， vj邻接于vi

• 顶点的度：与该顶点相关联的边的数目，记为TD(v)

  • 在有向图中, 顶点的度等于该顶点的入度与出度之和。
  • 顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v)
  • 顶点 v 的出度是以 v 为始点的有向边的条数, 记作OD(v)

• 路径：连续的边构成的顶点序列。

• 路径长度：路径上边或弧的数目/权值之和。

• 简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。（序列中顶点不重复出现的路径）

• 回路(环)：第一个顶点和最后一个顶点相同的路径。

• 简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路
  径。

• 在无（有）向图G=( V, {E} )中，若对任何两个顶点 v、u 都存在从
  v 到 u 的路径，则称G是连通图（无向）/强连通图（有向）。

• 权与网：图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。

• 子图：设有两个图G=(V，E)、G1=( V1，{E1})，若V1V，E1 CE，则称 G1是G的子图例:(b)(c)是(a)的子图
  

极大连通子图：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。(图G中并不被其他连通子图包含的连通子图)

性质：1）连通图只有一个极大连通子图，就是它本身；2）非连通图有多个极大连通子图（非连通图的极大连通子图叫做连通分量，每个分量都是一个连通图）

无向图 G 的极大连通子图称为G的连通分量。

有向图 G 的极大强连通子图称为G的强连通分量。

极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。

生成树：包含无向图G 所有顶点的极小连通子图。
性质：

1）同一个连通图可以有不同的生成树，所以生成树不是唯一的；
2）极小连通子图只存在于连通图中；
3）如果在生成树上添加一条边，一定会构成一个环

6.2案例引入

六度空间理论：
你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。

6.3图的类型定义

CreateGraph(&G,V,VR)
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。

DFSTraverse(G)
初始条件：图G存在。
操作结果：对图进行深度优先遍历。

BFSTraverse(G)
初始条件：图G存在。
操作结果：对图进行广度优先遍历。

6.4图的存储结构

6.5图的遍历

遍历定义：从已给的连通图一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。
遍历实质

遍历实质：找每个顶点的邻接点的过程

图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

6.6图的应用