数据结构与算法

§1 绪论

1.1 算法和算法分析

算法效率以下两个方面来考虑：

1. 时间效率：指的是算法所耗费的时间；
2. 空间效率：指的是算法执行过程中所耗费的存储空间。

时间效率和空间效率有时候是矛盾的。

Ⅰ 算法时间效率的度量

算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。主要有两种度量方法。

(1) 事后统计

将算法用编程软件进行实现，然后统计其在计算机上运行时间和空间开销。

缺点：① 编写程序实现算花费较多的时间和精力；② 所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣。

(2) 事前分析（常用）

对算法所消耗资源的一种估算方法。

一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需的时间与算法中进行的简单操作次数乘积：

$$算法运行时间 = 一个简单操作所需的时间 \times 简单操作次数$$

也即算法中每条语句的执行时间之和：

$$算法运行时间 = \sum_{语句条数} 每条语句的执行次数 \times 该语句执行一次所需的时间$$

每条语句执行一次所需的时间，一般是随机器而异的。取决于机器的指令性能、速度以及编译的代码质量。是由机器本身软硬件环境决定的它与算法无关。

所以，我们可假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即频度之和了：

$$算法运行时间 = \sum_{语句条数} 每条语句的执行次数 \times 单位时间 = \sum_{语句条数} 每条语句的执行次数$$

例如：两个$n \times n$矩阵相乘的算法

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

我们把算法所耗费的时间定义为该算法中每条语句的频度之和，则上述算法的时间消耗$T(n)$为：

$$T(n) = (n+1) + [n*(n+1)] + (n*n) + [(n*n)*(n+1)] + [(n*n)*n] = 2n^3 + 3n^2 + 1$$

为了便于比较不同算法的时间效率，我们仅比较它们的数量级。例如：两个不同的算法，时间消耗分别是 ① $T_1(n) = 10n^2$和 ② $T_2(n) = 5n^3$，$T_2$的数量级大，一般认为复杂度高。

• 算法时间复杂度的渐进表示

若有某个辅助函数$f(n)$，使得当$n$趋近于无穷大时，$T(n)/f(n)$的极限值为不等于零的常数，则称$f(n)$是$T(n)$的同数量级函数。记作$T(n)=O(f(n))$，称$O(f(n))$为算法的渐进时间复杂度($O$是数量级的符号)，简称时间复杂度。

因此，对于上述示例中求解矩阵相乘问题，算法耗费时间复杂度为：

$$T(n) = O(n^3)$$

一般情况下，不必计算所有操作的执行次数，而只考虑算法中基本操作执行的次数，它是问题规模$n$的某个函数，用$T(n)$表示。

算法中基本语句（执行次数最多的语句）重复执行的次数是问题规模$n$的某个函数$f(n)$，算法的时间量度记作：$T(n)=O(f(n))$。它表示随着$n$的增大，算法执行的时间的增长率和$f(n)$的增长率相同，称渐近时间复杂度。

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

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

Ⅱ 算法空间效率的度量

• 渐进空间复杂度

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

算法要占据的空间：① 变量等算法本身要占据的空间，输入/输出，指令，常数，变量等；② 算法要使用的辅助空间。

§ 2 线性表：顺序表和链表

2.1 线性表的定义和特点

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

$$(a_1, a_2, \cdots, a_{i-1}, a_i, a_{i+1}, \cdots, a_{n-1}, a_n)$$

线性表的第一个数据元素$a_1$被称为起始节点，最后一个数据元素$a_n$被称为终端节点，中间的数据元素为普通的节点。

线性表(Linear List)的定义：

由$n(n \geq 0)$个数据元素(结点)$a_1，a_2，…，a_n$组成的有限序列。

• 其中数据元素的个数$n$定义为表的长度；
• 当$n=0$时称为空表；
• 将非空的线性表($n>0$)记作：$(a_1，a_2，…，a_n)$；
• 这里的数据元素$a_i$只是一个抽象的符号，其具体含义在不同的情况下不同。

有两点需要注意：

• 线性表中每个节点的数据元素类型是相同的；
• 之所以称为线性，是因为每一个元素只有一个直接前趋，并且也只有一个直接后继(除起始节点、终端节点)。

小结

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

2.2 案例引入

2.3 线性表的类型定义

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

ADT List{
	数据对象:D={ai|ai属于Elemset,(i=1,2...,n, n≥0)}
	数据关系:R={<a{i-1}, ai|a{i-1},ai属于D,(i=2,3,...,n)}
	基本操作:
		// 初始化线性表
		// 操作结果：构造一个空的线性表L
		InitList(&L);	
    
		// 销毁线性表
		// 初始条件：线性表L已经存在
		// 操作结果: 销毁线性表L
		DestroyList(&L);
    
		// 清楚表中数据
		// 初始条件：线性表L已经存在
		// 操作结果：将线性表L重置为空表
		ClearList(&L);
    
		// 判断表中数据是否为空
		// 初始条件: 线性表L已经存在
		// 操作结果: 若L为空则返回TURE; 否则返回FALSE
		ListEmpty(L);

		// 求线性表长度
		// 初始条件: 线性表L已经存在
		// 操作结果: 返回线性表L中的数据元素个数
		ListLength(L);
    
		// 求线性表第i个位置的元素
		// 初始条件: 线性表L已经存在
		// 操作结果: 用e返回线性表L中第i个数据元素的值
		GetElem(L,i, &e);
		// 查找搜索元素
		// 初始条件: 线性表L已经存在，compare()是数据元素判定函数
		// 操作结果: 返回L中第1个与e满足compare()的元素位序。若不存在则返回值为0
		LocateElemL(L,e,compare());
    
		// 求一个元素的前趋
		// 初始条件: 线性表L已经存
		// 操作结果: 若cur_e是L的数据元素且不是第一个,则用pre_e返回其前趋，否则操作失败
		PriorElem(L, cur_e, &pre_e);
		// 求一个元素的后继
		NextElem(L, cur_e, &next_e);
    
		// 插入一个元素 
		// 初始条件: 线性表L已经存在，1<=i<=ListLength(L)+1
		// 操作结果: 在L的第i个位置之前插入新的数据元素e，L的长度加一
		ListInsert(&L,i,e);

		// 删除一个元素
		// 初始条件: 线性表L已经存在，1<=i<=ListLength(L)+1
		// 操作结果: 删除L的第i个数据元素，并用e返回其值，L的长度减一。
		ListDelete(&L,i,&e);
    
		// 遍历
		// 初始条件: 线性表L已经存在
 		// 操作结果: 依次对线性表中每个元素调用visited()操作
		ListTraverse(&L, visited());
} ADT List

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

Ⅰ 线性表的存储结构

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

Ⅱ 线性表的顺序存储表示

(1) 基本概念

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

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

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

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

(2) 顺序表中元素存储位置的计算

如果每个元素占用8个存储单元，$a_i$存储位置是2000单元，则$a_{i+1}$存储位置是2008。

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

$$\begin{aligned} & \text{LOC}(a_{i+1}) = \text{LOC}(a_i) + \ell \\ & \text{LOC}(a_{i}) = \text{LOC}(a_1) + (i-1) \ell \end{aligned}$$

式中，$\text{LOC}(a_1)$为基地址。

根据顺序表的性质，我们发现与C语言中的数组十分相似，但是仍然存在几个问题：

• 数据长度是否可变
  • 线性表长可变(添加、插入、删除等)
  • C语言中数组长度不可动态定义

C语言中一维数组的定义方式：

类型说明符 数组名[常量表达式]

说明：常量表达式中可以包含常量和符号常量，不能包含变量。即C语言中不允许对数组的大小作动态定义。

如何解决这个问题呢？一种方式是首先定义足够大的数组，然后额外用一个变量表示顺序表的长度属性。

//线性表存储空间的初始分配量
#define LIST_INIT_SIZE 100 
typedef struct {
    ElemType elem[LIST_INIT_SIZE]; 	// ElemType可以是int、char或其他类型数据
    int length; // 当前长度
} SqList;

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

$$P_n(x) = p_1 x^{e_1} + p_2 x^{e_2} + \cdots + p_m x^{e_m}$$

线性表$P=((p1, e1), (p2, e2), \cdots, (pm,em))$，代码为

#define MAXSIZE 1000 //多项式可能达到的最大长度

typedef struct {	// 多项式非零项的定义
    float p;	// 系数
    int e;		// 指数
}Polynomial;

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

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

(3) 顺序表的定义示意图

Ⅲ 内部基础算法实现

(1) 线性表的初始化（参数引用法）

% 初始化函数
int InitList_Sq(SqList& L)
{
	L.elem = new ElemType[MAXSIZE];
    // 异常处理
    if(!L.elem) 
    {
		exit(-2);
    }
    L.length = 0;
    return 1;
}

(2) 销毁线性表

% 销毁函数
void DestroyList(SqList& L)
{
    if(L.elem)
    {
		delete L.elem;	// 释放空间
    }
}

(3) 清空线性表

void ClearList(SqList& L)
{
	L.length = 0;	// 线性表还占用空间没有释放，只是长度置为0
}

(4) 求线性表的长度

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

(5) 判断线性表是否为空

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

(6) 顺序表的取值(根据位置i获取相应位置的数据内容)

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

(7) 顺序表的查找(按值查找)

在线性表L中查找与指定值e相同的数据元素的位置。从表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号，未找到，返回0。

int LocateELem(SqList L, ElemType e)
{
    // 在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)
    for (int i=0; i < L.length; i++)
    {
        if(L.elem[i] == e)
            return i+1;		//查找成功，返回序号
        return 0; 		//查找失败，返回0
    }
}

(8) 插入算法

算法思想：
① 判断插入位置i是否合法；
② 判断顺序表的存储空间是否已满，若已满返回ERROR；
③ 将第n至第ì 位的元素依次向后移动一个位置，空出第i个位置；
④ 将要插入的新元素e放入第i个位置；
⑤ 表长加1，插入成功返回OK。

int Listlnsert_Sq(SqList& L, int i, ElemType e)
{
    if( i<1 || i>L.length+1) // 插入位置i不合法
        return ERROR;
	if( L.length==MAXSIZE ) // 当前存储空间已满，无法插入
        return ERROR;
    for( int j=L.length-1; j>=i-1;j--)
    {
        L.elem[j+1]=L.elem[j];
    }
	// 插入元素
    L.elem[i-1]=e;
    // 表长+1
    L.length = L.length+1;
}

(9) 删除元素

算法思想:
① 判断删除位置i 是否合法(合法值为1≤i≤n)；
② 欲删除的元素保留在e中；
③ 将第i+1至第n 位的元素依次向前移动一个位置；
④ 表长减1，删除成功返回OK.

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

Ⅳ 线性表的顺序存储结构实现小结

① 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致；
② 在访问线性表时，可以快速地计算出任何一个数据元素的存储地址，因此可以粗略地认为，访问每个元素所花时间相等；
③ 这种存取元素的方法被称为随机存取法。

• 顺序表优缺点
  • 优点
    • 存储密度大(结点本身所占存储量/结点结构所占存储量)；
    • 可以随机存取表中任一元素；
  • 缺点
    • 在插入、删除某一元素时，需要移动大量元素；
    • 浪费存储空间；
    • 属于静态存储形式，数据元素的个数不能自由扩充。

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

Ⅰ 链式表的基本概念

(1) 链式存储结构

• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻；
  • 用一组物理位置任意的存储单元来存放线性表的数据元素。
    这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
• 线性表的链式表示又称为非顺序映像或链式映像。

(2) 与链式表相关的概念

• 结点：数据元素的存储映像。由数据域和指针域两部分组成；
• 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。

• 单链表：结点只有一个指针域的链表，称为单链表或线性链表；

• 双链表：结点有两个指针域的链表，称为双链表；

• 循环链表：首尾相接的链表称为循环链表。

• 头指针：是指向链表中第一个结点的指针；
• 首元结点：是指链表中存储第一个数据元素a1的结点；
• 头结点：是在链表的首元结点之前人为附加的一个结点；

根据是否带头节点，可将链表划分为2中类型：

(3) 几点讨论

• 讨论1：如何表示空表？
  • 无头结点时：头指针为空时表示空表；
  • 有头结点时：头节点的指针域为空时表示空表；
• 讨论2：额外添加头节点的优势？
  • 便于首元结点的处理
    首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理；
  • 便于空表和非空表的统一处理
    无论链表是否为空，头指针都是指向头结点的非空指针因此空表和非空表的处理也就统一了。
• 讨论3：头结点的数据域内装的是什么?
  • 头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。
• 讨论4：链表(链式存储结构)的特点？
  • (1) 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
  • (2) 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。

Ⅱ 单链表的定义和表示

(1) 带头结点的单链表

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。若头指针名是L，则把链表称为表L。

typedef struct Lnode // 声明结点的类型和指向结点的指针类型，该结构体的名字为Lnode
{
    ElemType data;	// 结点的数据域
    struct Lnode* next;	// 结点的指针域  struct可加可不加
}LNode, *LinkList;	// 根据typedef的作用：LNode是别名，LinkList为指向结构体Lnode的指针类型

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

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; //数据域
    struct Lnode *next; //指针域
}LNode, *LinkList;

(2) 单链表的初始化

算法思想：
① 生成新结点作头结点，用头指针L指向头结点；
② 将头结点的指针域置空。

int InitList(LinkList& L)
{
    L = new Lnode;
    L->next = NULL;
    return 1;	// 初始化成功
}

(3) 判断链表是否为空

注意：链表为空指的是：链表中无元素，称为空链表(头指针和头结点仍然在)。

int ListEmpty(LinkList& L) //若L为空表，则返回1，否则返回0
{
    if(L->next != NULL)
        return 0;
    else
        return 1;
}

(4) 单链表的销毁

注意：链表销毁后不再存在，不仅所有的元素没有了，头指针、头节点也没有了。

算法思想：从头指针开始，依次释放所有结点。

int DestoryList_L(LinkList& L)
{
    LNods* p;	// 或者 LinkList p;
    while(L != NULL)
    {
        p = L;
        L = L->next;
        deltet p;
	}
}

(5) 单链表的清空

注意：链表清空后仍然存在，但链表中元素没有了，头指针、头节点仍然存在。

算法思想：依次释放所有结点，并将头结点指针域设置为空。

Status ClearList(LinkList& L){	// 将L重置为空表
    Lnode *p,*q;	// 或 Linklist p,q;
    p = L->next;
    while(p != NULL) 	// 没到表尾
    {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;
    return Ok;
}

(6) 求链表的长度

int ListLength_L(LinkList& L)
{
    LinkList p;
    p = L-next;
    len = 0;
    while(p)
    {
		len++;
		p = p->next;
	}
	return len;
}

(7) 取第i个元素

从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。

算法思想：
① 从第1个结点(L->next)顺链扫描，用指针p指向当前扫描到的结点，p初值p =L->next；
② j做计数器，累计当前扫描过的结点数，j初值为1；
③ 当 p指向扫描到的下一结点时，计数器j加1；
④ 当j==i时，p所指的结点就是要找的第i个结点。

// 获取线性表L中的某个数据元素的内容，通过变量e返回
Status GetElem_L(LinkList& L, int i, ElemType &e)
{ 
    p = L->next;	// 初始化
    j = 1;
    while( p && j<i )	// 向后扫描，直到p指向第i个元素或p为空
    {
        p = p->next;
        ++j;
    }
	if( !p || j>i )
        return ERROR; // 第i个元素不存在
    e = p->data;	// 取第i个元素
return Ok;
}

(8) 查找算法(按值查找)

算法思想：
① 从第一个结点起，依次和e相比较；
② 如果找到一个其值与e相等的数据元素，则返回其在链表中的位置或地址；
③ 如果査遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。

// 在线性表L中查找值为e的数据元素
// 找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
Lnode* LocateELem_L(LinkList& L, Elemtype e)
{
	p = L->next;
	while( p && p->data!=e)
		p = p->next;
	return p;
}

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

(9) 插入操作

算法思想：
① 首先找到$a_{i-1}$的存储位置 p；
② 生成一个数据域为 e的新结点s；
③ 插入新结点：新结点的指针域指向结点$a_i \Longrightarrow$结点 $a_{i-1}$的指针域指向新结点。

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

(10) 删除操作

算法思想：
① 首先找到$a_{i-1}$的存储位置 p，保存要删除的a的值；
② 令 p -> next 指向$a_{i+1}$；
③ 释放结点$a_{i}$的空间。

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

(11) 构建单链表：头插法

算法思想：
① 从一个空表开始，重复读入数据；
② 生成新结点，将读入数据存放到新结点的数据域中；
③ 从最后一个结点开始，依次将各结点插入到链表的前端。

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

(12) 构建单链表：尾插法

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

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

Ⅲ 循环链表

循环链表：是一种头尾相接的链表(即：表中最后一个结点的指针指向头结点，整个链表形成一个环)。

注意:
由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next 是否为空，而是判断它们是否等于头指针L。

例子：两个循环链表合并。

LinkList Connect(LinkList Ta, LinkList Tb) 	// 假设Ta、Tb都是非空的单循环链表
{
    LinkList p;
    p=Ta->next;	// p存表头结点
    Ta->next=Tb->next->next;	// Tb表头连结Ta表尾
    delete Tb->next;	// 释放Tb表头结点
    Tb->next=p;	// 修改指针
    return Tb;
}

Ⅳ 双向链表

单链表的结点 → 有指示后继的指针域 → 找后继结点方便；
即：查找某结点的后继结点的执行时间为$O(1)$。

无指示前驱的指针域 → 找前驱结点难：从表头出发查找。
即：查找某结点的前驱结点的执行时间为$O(n)$。

可用双向链表来克服单链表的这种缺点。

双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指域 prior ，这样链表中就形成了有两个方向不同的链，故称为双向链表。

(1) 双向链表结构定义

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

(2) 双向循环链表

和单链的循环表类似，双向链表也可以有循环表：让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点。

双向链表的对称性：设指针p指向某一结点，则：

p->prior->next = p = p->next->prior

在双向链表中有些操作(如：ListLength、GetElem等)，因仅涉及一个方向的指针，故它们的算法与线性链表的相同。但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为$O(n)$。

(2) 双向链表插入结点

Status Listinsert_DuL(DuLinkList& L, int i, ElemType e)
{
    //在带头结点的双向循环链表L中第i个位置之前插入元素 e
    if(!(p=GetElemP DuL(L,i))) 
        return ERROR;
    DuLinkList s=new DuLNode;
    s->date = e;
    // 四部曲
    p->prior->next = s;
    s->prior = p->prior;
    p->prior = s;
    s ->next = p;
    return OK;
}

(3) 双向链表删除结点

Status ListDelete_DuL(DuLink& L, int i, ElemType& e)
{
    // 删除带头结点的双向循环链表L的第i个元素，并用 e返回.
    if(!(p=GetElemP DuL(L,i)))
        return ERROR;
    e = p-> data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return Ok;
}

2.6 线性表的应用

Ⅰ 线性表的合并

问题描述：假设利用两个线性表La和Lb分别表示两个集合A和B，现要求一个新的集合A=AUB，注意，存在重复元素合并后只出现一次。

$$La = (7, 5, 3, 11) \quad Lb=(2,6,3) \quad \Longrightarrow \quad La=(7, 5, 3, 11, 2, 6)$$

算法步骤：依次取出Lb中的每个元素，执行以下操作：
① 在La中查找该元素；
② 如果找不到，则将其插入La的最后。

// 链表实现
void union(List& La, List Lb)
{
    La_len=ListLength(La);	// 求链表长度
    Lb_len=ListLength(Lb);	// 求链表长度
    for(int i=1; i<=Lb_len; i++)
    {
        GetElem(Lb,i,e);	// 取出第i个元素e
        if(!LocateElem(La, e))	// 判断La中是否存在e
            Listinsert(&La, ++La_len, e);	// 不存在则插入
    }
}

Ⅱ 有序表的合并

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

$$La = (1, 7, 8) \quad Lb=(2, 4, 6, 8, 10, 11) \quad \Longrightarrow \quad Lc=(1, 2, 4, 6, 7, 8, 8, 10, 11)$$

算法步骤：
① 创建一个空表Lc；
② 依次从 La 或 Lb 中”摘取“元素值较小的结点插入到Lc表的最后，直至其中一个表变空为止；
③ 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后。

• 用顺序表实现

void MergeList_Sq(SqList LA, SqList LB, SqList& LC)
{
    ElemType* pa = LA.elem;
    ElemType* pb = LB.elem;	// 指针pa和pb的初值分别指向两个表的第一个元素
    LC.length = LA.length+LB.length;	// 新表长度为待合并两表的长度之和
    LC.elem = new ElemType[Lc.length];	// 为合并后的新表分配一个数组空间
    ElemType* pc = LC.elem;	// 指针pc指向新表的第一个元素
    ElemType* pa_last = LA.elem+LA.length-1;	// 指针pa_last指向LA表的最后一个元素
    ElemType* 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
}

• 用链表实现

void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc)	// La、Lb是带头结点的单链表
{
    LinkList pa=La->next;
    LinkList pb=Lb->next;
    LinkList pc=La;
    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的头结点
}

Ⅲ 实际案例1：稀疏多项式的运算

容易发现顺序存储结构存在问题：存储空间分配不灵活；运算的空间复杂度高。

因此这种稀疏多项式的运算比较适合于链表实现。

链式存储结构：

typedef struct Pnode
{
    float coef;	// 系数
    int expn;	// 指数
    struct Pnode* next;	// 指针域
}PNode, *Polynomial;

【多项式的创建】算法步骤：
① 创建一个只有头结点的空链表；
② 根据多项式的项的个数n，循环n次执行以下操作：
a. 生成一个新结点s；
b. 输入多项式当前项的系数和指数赋给新结点s的数据域；
c. 设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre初值指向头结点；
d. 指针q初始化，指向首元结点；
e. 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q；
f. 将输入项结点s插入到结点q之前。

void CreatePolyn(Polynomial& P, int n)
{
	// 输入m项的系数和指数，建立表示多项式的有序链表P
    P = new PNode;
    P->next = NULL;	// 先建立一个带头结点的单链表
    for( int i=1; i<=n; ++i)	// 依次输入n个非零项
    {
        s = new PNode;	// 生成新结点
        cin >> s->coef >> s->expn;	// 输入系数和指数
        pre=P;	// pre用于保存q的前驱，初值为头结点
        q=P->next;	// q初始化，指向首元结点
        while(q && q->expn < s->expn)	// 找到第一个大于输入项指数的项*q
        {
            pre=q;
            q=q->next;
        }
        s->next=q;	// 将输入项s插入到q和其前驱结点pre之间
        pre->next=s;
    }
}

【多项式的相加】算法步骤：

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

§ 3 线性表：栈和队列

3.1 栈和队列的定义和特点

Ⅰ 概念概述

栈和队列是两种常用的、重要的数据结构。栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

栈——后进先出：生活举例：电梯进出。

队列——先进先出：生活举例：排队买票。

• 由于栈的操作具有后进先出的固有特性，使得栈成为程序设计中的有用工具。另外，如果问题求解的过程具有”后进先出”的天然特性的话，则求解的算法中也必然需要利用”栈”。

例如：数制转换、括号匹配的检验、行编辑程序、迷宫求解、表达式求值、八皇后问题、函数调用、递归调用的实现等都与栈这种数据结构有关。

• 由于队列的操作具有先进先出的特性，使得队列成为程序设计中解决类似排队问题的有用工具。

例如：脱机打印输出：按申请的先后顺序依次输出；
例如：多用户系统中，多个用户排成队，分时地循环使用CPU和主存；
例如：按用户的优先级排成多个队，每个优先级一个队列；
例如：实时控制系统中，信号按接收的先后顺序依次处理；
例如：网络电文传输，按到达的时间先后顺序依次进行。

Ⅱ 栈(stack)的概念

(1) 栈的定义

栈(stack)是一个特殊的线性表，是限仅在一端(通常是表尾)进行插入和删除操作的线性表。又称为后进先出(Last In First Out)的线性表，简称LIFO结构。

表尾(即$a_n$端)被称为栈顶Top，表头(即$a_1$端)被称为栈底Base。例如：

$$栈： S=(a_1, a_2, \cdots, a_n)$$

入栈：插入元素到栈顶(表尾)的操作；出栈：从栈顶(表尾)删除最后一个元素的操作。

(2) 栈的示意图

(3) 栈概念和特点小结

相关概念	释义
定义	限定只能在表的一端进行插入、删除运算的线性表(只能在栈顶操作)
逻辑结构	与线性表相同，仍为一对一关系
存储结构	用顺序栈或链栈存储均可，但以顺序栈更常见
运算规则	只能在栈顶运算，且访问结点时依照店进先出(LIFO)的原则
实现方式	关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同

Ⅲ 队列(queue)的概念

(1) 队列的定义

队列(queue)是一种先进先出(Frist In Frist Out ——FIFO)的线性表。在表一端插入(表尾)，在另一端(表头)删除。

$$队列：Q=(a_1, a_2, \cdots, a_n)$$

(2) 队列示意图

(3) 队列概念和特点小结

相关概念	释义
定义	只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表(头删尾插)
逻辑结构	与线性表相同，仍为一对一关系
存储结构	顺序队或链队，以循环顺序队列更常见
运算规则	只能在队首和队尾运算，且访问结点时依照先进先出(FIFO)的原则
实现方式	关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同

3.2 案例引入

Ⅰ 进制转换

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

转换法则：

$$n = (n \text{ div }d)*d + n \text{ mod }d$$

其中，div为取商运算，mod为取余运算。

Ⅱ LeetCode 20有效的括号

Ⅲ 表达式求值

表达式求值是程序设计语言编译中一个最基本的问题，它的实现也需要运用栈。

这里介绍的算法是由运算符优先级确定运算顺序的对表达式求值算法——算符优先算法。

• 表达式的组成
  • 操作数(operand)：常数、变量；
  • 运算符(operator)：算术运算符、关系运算符和逻辑运算符；
  • 界限符(delimiter)：左右括弧和表达式结束符。

任何一个算术表达式都由操作数(常数、变量)、算术运算符(+、-、*、/)和界限符(括号、表达式结束符#、虚设的表达式起始符#)组成。后两者统称为算符。

例如：# 3*(7-2) #

• 为了实现表达式求值，需要设置两个栈：
  • 一个是算符栈OPTR，用于寄存运算符；
  • 另一个称为操作数栈(OPND)，用于寄存运算数和运算结果。
• 求值的处理过程是自左至右扫描表达式的每一个字符：
  • 当扫描到的是运算数，则将其压入栈OPND；
  • 当扫描到的是运算符时：
    • 若这个运算符比OPTR栈顶运算符的优先级高，则入栈OPTR，继续向后处理；
    • 若这个运算符比OPTR栈顶运算符优先级低，则从OPND中弹出两个运算数，从OPTR中弹出栈顶运算符进行运算，并将运算结果压入栈OPND。
  • 继续处理当前字符，直到遇到结束符为止。

3.3 栈的表示和操作

Ⅰ 常见的栈操作

InitStack(&S)：初始化操作；操作结果：构造一个空栈S。

DestroyStack(&S)：销毁栈操作；初始条件：栈S已存在；操作结果：栈S被销毁。

StackEmpty(S)：判定S是否为空；初始条件：栈S已存在；操作结果：若栈S为空则返回true，否则false。

StackLength(S)：求栈的长度；初始条件：栈S已存在；操作结果：返回S的元素个数，即栈的长度。

GetTop(S, &e)：取栈顶元素；初始条件：栈S已存在且非空；操作结果：用e返回S的栈顶元素。

ClearStack(&S)：栈置空操作；初始条件：栈S已存在；操作结果：将 S 清为空栈。

Push(&S, e)：入栈操作；初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。

Pop(&S, &e)：出栈操作；初始条件：栈S已存在且非空；操作结果：删除S的栈顶元素an，并用e返回
其值。

Ⅱ 顺序栈的表示和实现

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

栈底一般在低地址端。① 附设top指针，指示栈顶元素在顺序栈中的位置。② 附设base指针，指示栈底元素在顺序栈中的位置。③ 用stacksize表示栈可使用的最大容量。

从上图可以看到，为了方便操作，通常top指示真正的栈顶元素之上的下标地址。

空栈标志：base=top

栈满标志：top-base=stacksize

栈满时的处理：1、报错，返回操作系统。2、分配更大空间，作为栈的存储空间，将原栈的内容移入新栈。

• 使用数组作为顺序栈存储方式的特点：简单，方便、但易产生溢出(数组大小固定)
  • 上溢(overflow)：栈已经满，又要压入元素；
  • 下溢(underflow)：栈已经空，还要弹出元素

注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束。

(1) 顺序栈的数据类型定义

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

(2) 顺序栈的初始化

Status InitStack(SqStack& S)
{
    S.base = new SElemType[MAXSIZE];	// base指针指向数组首元素地址
    if(!S.base)	// 判断空间是否分配成功
        exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

(3) 顺序栈判断是否为空

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

(4) 顺序栈求长度

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

(5) 顺序栈的清空(不销毁内存，只清空数据)

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

(6) 顺序栈的销毁(销毁内存，清空数据)

Status DestroyStack( SqStack& S )
{
    if( S.base )
    {
        delete[] S.base ;	// 注意： ① []是否要加？；② delet是释放空间，指针还存在
        S.stacksize =0;
        S.base = S.top = NULL;	// 防止野指针？
    }
	return Ok;
}

(7) 顺序栈的入栈操作

算法思想：
① 判断是否栈满，若满则出错(上溢)；
② 元素e压入栈顶；
③ 栈顶指针加1。

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

(8) 顺序栈的出栈操作

算法思想：
① 判断是否栈空，若空则出错(下溢)；
② 获取栈顶元素e；
③ 栈顶指针减1。

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

Ⅲ 链栈的表示和实现

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

看上图，链栈有点类似于用头插法构造链表。

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

(1) 链栈的数据类型定义

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

LinkStack S;	// 创建一个指向链栈结点的指针

(2) 链栈的初始化

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

(3) 链栈判断是否为空

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

(4) 链栈的入栈操作

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

(5) 链栈的出栈操作

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

(6) 取栈顶元素

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

3.4 栈与递归

Ⅰ 递归的定义

若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；

若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。例如：递归求n的阶乘

long Fact ( long n ) 
{
    if(n == 0) 
        return 1;
    else 
        return n * Fact(n-1);
}

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

① 递归定义的数学函数

• 阶乘函数：

$$\text{Fact}(n) = \begin{align} \begin{cases} 1 & n = 1 \\ n \cdot \text{Fact}(n) & n \neq 1 \end{cases} \end{align}$$

• 2阶Fibonaci数列：

$$\text{Fib}(n) = \begin{align} \begin{cases} 1 & n = 1 \text{ OR }n=2\\ \text{Fib}(n) + \text{Fib}(n) & \text{others} \end{cases} \end{align}$$

② 具有递归特性的数据结构

• 二叉树
• 广义表

③ 可递归求解的问题

• 迷宫问题
• Hanoi塔问题

Ⅱ 递归的本质解析

(1) 思想：用分治法求解问题

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

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

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

void p(参数表)
{
    if(递归结束条件)
        可直接求解步骤;	// -----基本项
    else 
        p(较小的参数);	// ------归纳项
}

(2) 函数调用过程

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

当多个函数构成嵌套调用时，简单分析可知，最后调用的函数先返回结果，也就是遵循：后调用先返回——栈的特征。

(3) 递归的优缺点

优点：结构清晰，程序易读。

缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈恢复状态信息。时间开销大。

当对时间效率要求比较高的时候，就要想办法把递归变成非递归，通用的方法有2种：

① 尾递归、单向递归→循环结构；

尾递归：

单向递归：虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调函数有关，相互之间参数无关，并且这些递归调用语句处于算法的最后。

② 自用栈模拟系统的运行时栈。

借助栈改写递归：

—— 递归程序在执行时需要系统提供栈来实现；

—— 仿照递归算法执行过程中递归工作栈的状态变化可写出相应的非递归程序；

—— 改写后的非递归算法与原来的递归算法相比，结构不够清晰，可读性较差有的还需要经过一系列优化。

详细步骤：

Step 1：设置一个工作栈存放递归工作记录(包括实参、返回地址及局部变量等)；
Step 2：进入非递归调用入口(即被调用程序开始处)将调用程序传来的实在参数和返回地址入栈(递归程序不可以作为主程序，因而可认为初始是被某个调用程序调用)；
Step 3：进入递归调用入口:当不满足递归结束条件时，逐层递归，将实参、返回地址及局部变量入栈，这一过程可用循环语句来实现一模拟递归分解的过程；
Step 4：递归结束条件满足，将到达递归出口的给定常数作为当前的函数值；
Step 5：返回处理：在栈不空的情况下，反复退出栈顶记录，根据记录中的返回地址进行题意规定的操作，即逐层计算当前函数值，直至栈空为止一模拟递归求值过程。

3.5 队列的表示和操作

Ⅰ 常见的队列操作

InitQueue(&Q)：初始化操作；操作结果：构造一个空队列Q。

DestroyQueue(&Q)：销毁队列操作；初始条件：队列Q已存在；操作结果：队列Q被销毁。

ClearQueue(&Q)：判定Q是否为空；初始条件：队列Q已存在；操作结果：若队列Q为空则返回true，否则false。

QueueLength(Q)：求队列Q的长度；初始条件：队列Q已存在；操作结果：返回队列Q的元素个数。

GetHead(Q, &e)：求队头元素；初始条件：队列Q已存在且非空；操作结果：用e返回队头元素。

EnQueue(&Q, e)：插入操作；操作结果：插入元素e为Q的队尾元素。

DeQueue(&Q, &e)：删除操作；条件：Q为非空队列；操作结果：:删除Q的队头元素，用e返回值。

还有将队列置空、遍历队列等操作….

Ⅱ 队列的顺序表示和实现

队列的物理存储可以用顺序存储结构，也可用链式存储结构。相应地，队列的存储方式也分为两种，即顺序队列和链式队列。

队列的顺序表示 —— 用一维数组base[MAXQSIZE]。

(1) 顺序队的数据类型定义

#define MAXQSIZE 100 // 最大队列长度

typedef struct 
{
    QElemType *base;// 初始化的动态分配存储空间，用数组存储数据
    int front;	// 头指针：称作指针，但实际不是指针类型变量，作用是指示队头位置
    int reary;	// 尾指针
}sqQueue;

(2) 队列的假溢出

• 解决方法：
  • 方法1：将队中元素依次向队头方向移动。
    缺点：时间消耗大，每移动一次，队中元素都要移动。
  • 方法2：将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为maxgsize时，若向量的开始端空着，又可从头使用空着的空间。当front为maxqsize时，也是一样。

综上，基本使用方法2的循环队列法：

base[0]接在base[MAXQSIZE-1]之后，若rear+1==M，则令rear=0。实现方法：利用<font color=re’d>模(mod，C语言中%)运算</font>。

// 插入元素
Q.base[Q.rear] = x;
Q.rear = (Q.rear+1)%MAXQSIZE; 	// 对MAXQSIZE取模

// 删除元素
x = Q.base[s.front]
Q.front = (Q.front+1)%MAXQSIZE;

但是，采用了循环队列之后，要考虑队空和队满的情况，因为不做处理的时候，队空和队满情况是一样的，如下图所示。

(3) 循环队列解决队空/满的方法——这里介绍少用一个元素法

注意，队空的判定仍然是使用front==rear，而队满采用：(rear+1)%MAXQSIXZE==front。

(4) 循环顺序队列的初始化

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

(5) 循环顺序队列求长度

int QueueLength(SqQueue Q)
{
    return ( (Q.rear-Q.front + MAXQSIZE)%MAXQSIZE ) 	// 注意此处算法
}

(6) 循环顺序队列的入队

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

(7) 循环顺序队列的出队

Status DeQueue(SqQueue& Q, QElemType& e)
{
    if(Q.front==Q.rear)	// 队空
        return ERROR;
    
    e = Q.base[Q.front];	// 保存队头元素
    Q.front=(Q.front+1)%MAXQSIZE;	// 队头指针+1

return Ok;

(8) 取队首元素

SElemType GetHead(SqQuere Q)
{
    if(Q.front!=Q.rear)	// 队列不为空
        return Q.base[Q.front];	// 返回队头指针元素的值，队头指针不变
    else
        return NULL;	// 看具体的数据
}

Ⅲ 链队的表示和实现

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

(1) 链队的数据类型定义

// 链队的数据类型定义
typedef struct Qnode
{
	QElemType data;
	stuct Qnode *next;
}QNode, *QuenePtr;

// 头尾指针单独封装起来
typedef struct 
{
	QuenePtr front;	// 队头指针
	QuenePtr rear;	// 队尾指针
} LinkQueue;

(2) 链队的初始化

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

(3) 链队的销毁

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

(4) 链队的入队操作

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

(5) 链队的出队操作

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

(6) 链队求队头操作

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

§ 4 串、数组和广义表

4.1 串

Ⅰ 串的概念

这里的串，特指“字符串(String)”：零个或多个任意字符组成的有限序列。

$$\text{String } S="a_1 a_2 \cdots a_n"$$

(1) 几个相关概念

• 字串：串中任意个连续字符组成的子序列称为该串的子串。

• 主串：包含子串的串相应地称为主串。

• 字符位置：字符在序列中的序号为该字符在串中的位置。

• 子串位置：子串第一个字符在主串中的位置。

• 空格串：由一个或多个空格组成的串，与空串不同。

• 串相等：当且仅当两个串的长度相等，并且各个对应位置上的字符都相同时，这两个串才是相等的。

  • 所有的空串都是相等的。

Ⅱ 案例引入

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

案例： 病毒感染检测

研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列。然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染。

例如：假设病毒的DNA序列为baa(aab、aba)，患者1的DNA序列为aaabbba，则感染，患者2的DNA序列为babbba，则未感染。(注意，人的DNA序列是线性的，而病毒的DNA序列是环状的)

Ⅲ 串的表示和实现

(1) 串的类型定义

串中元素逻辑关系与线性表的相同，串可以采用与线性表相同的存储结构。

涉及串的相关操作：

StrAssign(&T, chars)：串赋值。

StrCompare(S, T)：串比较。

StrLength(S)：求串长。

Concat(&T,S1,S2)：串连结。

SubString(&sub, S, pos, len)：求子串。

StrCopy(&T, S)：串拷贝。

StrEmpty(S)：串判空。

ClearString (&S)：清空串。

index(S, T, pos)：子串的位置。

Replace(&S,T, V)：串替换。

Strlnsert(&S, pos, T)：子串插入。

StrDelete(&S, pos, len)：子串删除。

DestroyString(&S)：串销毁。

Ⅳ 顺序串的表示和实现

(1) 顺序串的存储结构

顺序串在实际中比链串更常用。

#define MAXLEN 255

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

(2) 顺序串的模式匹配算法

• 概念：确定主串中所含子串(模式串)第一次出现的位置(定位)。
• 算法应用：搜索引擎、拼写检查、语言翻译、数据压缩算法。
• 算法种类：
  • BF算法(Brute-Force，又称古典的、经典的、朴素的、穷举的、暴力算法)
  • KMP算法(特点：速度快)

BF算法：穷举法思想

简单来说：算法的思路是从S的第一个字符开始依次与T的字符进行匹配。

算法流程：

将主串的第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;	// 返回匹配的第一个字符的下标
    else 
        return 0;	// 模式匹配不成功
}

KMP算法

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

int Index_KMP(SString S,sString T, int pos) 
{
    i = pos;
    j = 1;
    while ( i<s.length && j<Tlength ) 
    {
        if ( j==0 || S.ch[i]==Tch[j] )
        { 
            i++;
            j++;
        }
        else
            j = next[j];	// i不变j后退
    }
    if ( j>T.length )
        return i-T.length; 	// 匹配成功
    else return 0;	// 返回不匹配标志
}

其中，next[j]的求法：

void get_next(SString T, int& next[])
{
    i = 1; 
    next[1]= 0;
    j = 0;
    while( i<Tlength )
    {
        if( j==0 || T.ch[i] == T.ch[j] )
        {
            ++i; 
            ++j;
            next[i] =j;
        }
        else
            j= next[j];
    }
}

关于KMP算法中模式串的移动不会产生漏解的证明 - 博客园

反证法证明：为什么KMP算法不会跳过（漏掉）正确的答案 - CSDN

Ⅴ 链串的表示和实现

(1) 链串的存储结构

为例改善存储密度低的问题，一般采用下面这种方式，又被称为块链串。

#define CHUNKSIZE 80	// 块的大小可由用户定义

typedef struct Chunk
{
    char ch[CHUNKSIZE];
    struct Chunk* next;
}Chunk;

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

4.2 数组

Ⅰ 数组的概念

数组：按一定格式排列起来的、具有相同类型的数据元素的集合。

(1) 一维数组

一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组。
一维数组的逻辑结构：线性结构，定长的线性表。
声明格式：数据类型 变量名称[长度]，e.g. int a[5] = {0, 1, 2, 3, 4}。

(2) 二维数组

二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组。

• 二维数组的逻辑结构可分为2种：
  • 非线性结构：每一个数据元素既在一个行表中，又在一个列表中。
  • 线性结构(定长的线性表)：该线性表的每个数据元素也是一个定长的线性表。

声明格式：数据类型 变量名称[行数][列数]，e.g. int num[5][8]。

(3) 高维数组

三维数组：若二维数组中的元素又是一个一维数组，则称作三维数组。
n维数组：若n-1维数组中的元素又是一个一维数组结构则称作n维数组。

(4) 结论

线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。

数组特点：结构固定——定义后，维数和维界不再改变。

数组基本操作：除了结构的初始化和销毁之外只有取元素和修改元素值的操作。

Ⅱ 数组的表示和操作

数组很少会采用链式存储结构，因为一般数组特点：结构固定。

(1) 数组的顺序存储结构和基本操作

数组可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。

例1：一个一维数组定义为：int a[5]，每个元素占用4字节，假设a[0]存储在2000单元，a[3]地址是多少?

答1：占据2012-2015存储单元。

二维数组的存储顺序可以按行、按列分为2种情况：

• 以行序为主序时：
  • 设数组开始存储位置 LOC(0,0)，存储每个元素需要L个存储单元数组元素a[i][j]的存储位置是：LOC(i,j)= LOC(0,0)+(n*i+j)*L。

(2) 特殊矩阵的压缩存储

矩阵：可以看作是一个由$m \times n$个元素排成的$m$行$n$列的表。

矩阵的常规存储：将矩阵描述为一个二维数组。矩阵的常规存储的特点：① 可以对其元素进行随机存取；② 矩阵运算非常简单；③存储的密度为 1。

这里考察某些比较特殊的矩阵的存储，这类矩阵不适宜常规存储的矩阵 —— 值相同的元素很多且呈某种规律分布，零元素多。

矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

压缩存储的定义：若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等都适合采用压缩存储。

• 对称矩阵
  • [存储方法] 只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。
• 三角矩阵：对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c
  • [存储方法] 重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间。
• 对角矩阵(带状矩阵)：在$n \times n$的方阵中，所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等
  • [存储方法] 如下图所示，但是这种方法只有当次对角线数量小于某一值时才可行。

• 稀疏矩阵：一般认为矩阵中非零元素占总元素的5%以下时是稀疏的。
  • [存储方法1] 三元组法 —— 存各非零元的值和非零元的行列位置。为更可靠描述，通常再加一个“总体”信息：即总行数、总列数、非零元素总个数。
  • [存储方法2] 十字链表法 —— 在十字链表中，矩阵的每一个非零元素用一个结点表示该结点除了(row，col，value)以外，还要有两个域：
    • right：用于链接同一行中的下一个非零元素；
    • down：用以链接同一列中的下一个非零元素。
    • 

(3) 基本操作

InitArray(&A, n, bound1, ..., bound n)：构造数组A；

DestroyArray(&A)：销毁数组A；

Value(A, &e, index1, ..., index n)：取数组元素值；

Assign (A, &e, index1, ..., index n)：给数组元素赋值。

4.5 广义表

Ⅰ 广义表的概念

广义表(又称列表 Lists)是 $n\geq 0$个元素 $a_0, a_1, … , a_{n-1}$ 的有限序列，其中每一个 $a_i$ 或者是原子，或者是一个广义表。

广义表通常记作：$LS = (a_1, a_2, \cdots, a_n)$，其中，$LS$为表名，$n$为长度，每一个$a_i$为表的元素。

表头：若广义表$LS$非空，则其第一个元素$a_1$就是表头，记作：$\text{head}(LS) = a_1$，表头既可以是原子也可以是子表。

表尾：除表头之外的其它元素组成的子表，记作：$\text{tail}(LS) = (a_2, \cdots, a_n)$，注：表尾不是最后一个元素，而是一个子表；此外，若$LS$中只有一个元素，则只有表头，表尾是一个空的子表。

• 广义表的特性：

  • ① 广义表中的数据元素有相对次序；一个直接前驱和一个直接后继。
  • ② 广义表的长度定义为最外层所包含元素的个数；
  • ③ 广义表的深度定义为该广义表展开后所含括号的重数；
  • ④ 广义表可以为其他广义表共享；如：广义表B就共享表A。在B中不必列出A的值，而是通过名称来引用：B=(A)。
  • ⑤ 广义表可以是一个递归的表。如：F=(a, F) = (a,(a,(a, ... )))。注意：递归表的深度是无穷值，长度是有限值。
  • ⑥ 广义表是多层次结构，广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表。

  

• 广义表的基本操作

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

Ⅱ 广义表 VS 线性表

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

广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。

—— 当二维数组的每行(或每列)作为子表处理时，二维数组即为一个广义表。

—— 另外，树和有向图也可以用广义表来表示。

由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。

§ 5 树、二叉树

5.1 树形结构

Ⅰ 树的概念

(1) 树的定义

树(Tree) 是 $n(n≥0)$ 个结点的有限集：

• 若$n=0$，称为空树；
• 若$n>0$，则它满足如下两个条件：
  ① 有且仅有一个特定的称为根 (Root)的结点；
  ② 其余结点可分为 $m(m≥0)$ 个互不相交的有限集T1,T2,T3,…,Tm，其中每一个集合本身又是一棵树，并称为根的子树(SubTree)。

显然，树的定义是一个</font color=red>递归</font>的定义。

(2) 树的表示形式

(3) 树的相关术语

有序树：树中结点的各子树从左至右有次序(最左边的为第一个孩子)，换了顺序就是另一棵树了。

无序树：树中结点的各子树无次序。

森林：是 $m(m≥0)$ 棵互不相交的树的集合。把根结点删除树就变成了森林。一棵树可以看成是一个特殊的森林。给森林中的各子树加上一个双亲结点，森林就变成了树。树一定是森林，但森林不一定是树。

Ⅱ 二叉树

普通树(多又树)若不转化为二又树，则分支太多且不固定，运算很难实现。

• 为何要重点研究每结点最多只有两个“叉”的树？
  • 二叉树的结构最简单，规律性最强；
  • 可以证明，所有树都能转为唯一对应的二叉树不失一般性。

(1) 二叉树的定义

二叉树是 $n(n≥0)$ 个结点的有限集，它或者是空集($n= 0$)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

特点1：每个结点最多有俩孩子(二叉树中不存在度大于 2 的结点)。
特点2：子树有左右之分，其次序不能颠倒。
特点3：二叉树可以是空集合，根可以有空的左子树或空的右子树。

注意：二叉树不是树的特殊情况，它们是两个概念。

二叉树结点的子树必须区分左子树和右子树，即使只有一棵子树也进行区分，说明它是左子树，还是右子树。

树当结点只有一个孩子时，就无须区分它是左还是右的次序。因此二者是不同的。这是二又树与树的最主要的差别。

简单来说：也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了)。

二叉树有且只有这五种基本形态。

Ⅲ 案例引入

(1) 数据压缩问题

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

(2) 利用二又树求解表达式的值

以二叉树表示表达式的递归定义如下：

(1) 若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；

(2) 若表达式为第一操作数 运算符 第二操作数的形式，则相应的二cha树中以左子树表示第一操作数右子树表示第二操作数，根结点的数据域存放运算符(若为一元运算符，则左子树为空)，其中，操作数本身又为表达式。

Ⅳ 树、二叉树的表示

(1) 二叉树的抽象数据类型定义

ADT BinaryTree
{
    数据对象D: D是具有相同特性的数据元素的集合。
    数据关系R: 若D=Φ，则R=Φ;
    		  若D≠Ф，则R={H}; H是如下二元关系：
                  ① root 唯一    //关于根的说明
                  ② Dj ∩ Dk = Ф  //关于子树不相交的说明
                  ③ ...          //关于数据元素的说明
                  ④ ...          //关于左子树和右子树的说明

	基本操作 P:
	// 初始条件: definition给出二叉树T的定义。
	// 操作结果: 按definition构造二叉树T。
	CreateBiTree(&T, definition);
	
	// 初始条件: 二叉树T存在。
	// 操作结果: 先序遍历T，对每个结点访问一次。
	PreOrderTraverse(T);
	
	// 初始条件: 二叉树T存在。
	// 操作结果: 中序遍历T，对每个结点访问一次。
	InOrderTraverse(T);
	
	// 初始条件: 二叉树T存在。
	// 操作结果: 后序遍历T，对每个结点访问一次。
	PostOrderTraverse(T);

}ADT BinaryTree

(2) 二叉树的性质与存储结构

满二叉树：一棵深度为 $k$且有$2^k-1$个结点的二叉树称为满二叉树。也就是说每一层上的结点数都是最大结点数(即每层都满)；叶子节点全部在最底层。

对满二叉树结点位置进行编号编号规则：从根结点开始，自上而下，自左而右。每一结点位置都有元素。如下图所示。

完全二叉树：深度为$k$的具有$n$个结点的二叉树，当且仅当其每一 个结点都与深度为$k$的满二叉树中编号为$1 \sim n$的结点一一对应时，称之为完全二叉树。如下图所示。

完全二叉树的特点：1.叶子只可能分布在层次最大的两层上。2.对任一结点，如果其右子树的最大层次为$i$，则其左子树的最大层次必为$i$或$i+1$。

• 性质

  • ① 在二叉树的第$i$层上至多有$2^{i-1}$个结点。
  • ② 深度为$k$的二叉树至多有$2^k-1$个结点。
  • ③ 对任何一棵二叉树T，如果其叶子数为$n_0$，度为$2$的结点数为$n_2$，则$n_0 = n_2+1$。
  • ④ 具有$n$个结点的完全二叉树的深度为$\lfloor \log_2 n \rfloor +1$。
  • ⑤ 如果对一棵有$n$个结点的完全二叉树按层序编号(从第1层到第$\lfloor \log_2 n \rfloor +1$层，每层从左到右)，则对任结点$i(1≤i≤n)$，有:
    • 如果$i=1$，则结点$i$是二叉树的根，无双亲；如果$i>1$，则其双亲是结点 $\lfloor i/2 \rfloor$。
    • 如果$2i>n$，则结点$i$为叶子结点，无左孩子；否则其左孩子是结点$2i$。
    • 如果$2i+1>n$，则结点$i$无右孩子；否则，其右孩子是结点$2i + 1$。
• 树、二叉树的顺序存储结构

按满二叉树的结点层次编号，依次存放二叉树中的数据元素。

//二叉树顺序存储表示
#define MAXTSIZE 100

typedef TElemType SqBiTree[MAXSTIZE];
SqBiTree bt;

当不是满二叉树、完全二叉树的时候：不满的地方用0值填充。

由此看来，二叉树的顺序存储结构的存储密度会很低，一般只适用于满二叉树和完全二叉树。

• 树、二叉树的链式存储结构

// 二叉链表存储结构
typedef struct Binode
{
    TElemType data;
    struct Binode *lchild,*rchild;	// 左右孩子指针
}BiNode,*BiTree;

二叉树的三叉链表存储：

typedef struct TriTNode
{
    TelemType data;
    struct TriTNode *lchild,*parent,*rchild;	// 左右孩子指针+双亲指针
}TriTNode, *TriTree;

5.2 遍历二叉树

Ⅰ 遍历的概念

遍历定义 —— 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次(又称周游)。

“访问”的含义很广，可以是对结点作各种处理，如：输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构。

遍历目的 —— 得到树中所有结点的一个线性排列。

遍历用途 —— 它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

Ⅱ 遍历二叉树算法描述

假设：L遍历左子树，D访问根结点，R遍历右子树则遍历整个二叉树方案共有6种，分别是：

$$DLR、LDR、LRD、DRL、RDL、RLD$$

其中，主要看前三种：先(根)序遍历DLR、中(根)序遍历LDR、后(根)序遍历LRD。

先序遍历二叉树	中序遍历二叉树	后序遍历二叉树
若二叉树为空，则空操作； 否则 (1) 访问根结点； (2) 先序遍历左子树； (3) 先序遍历右子树。	若二叉树为空，则空操作； 否则 (1) 中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树。	若二叉树为空，则空操作； 否则 (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点。

由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二又树一样“递归”进行。

• 根据遍历序列确定二叉树

  • 若二叉树中各结点的值均不相同，则二叉树结点的先序序列、中序序列和后序列都是唯一的。
  • 由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一棵二叉树。==只知道某一种序是不能唯一确定一棵二叉树的==。

Ⅲ 先序遍历二叉树(递归方法)

明显，利用递归的算法进行。

// 先(根)序遍历
Status PreOrderTraverse(BiTree T)	// 指针T指向二叉树的根节点
{
    if(T==NULL)
        return OK; // 空二叉树
    else
    {
        visit(T); // 访问根结点，根据实际需要进行操作
        PreOrderTraverse(T->lchild);	// 递归遍历左子树
        PreOrderTraverse(T->rchild);	// 递归遍历右子树
    }
}

void visit(BiTree T)
{
    // 打印输出当前节点数据
    cout << T->data << endl;
}

Ⅳ 中序、后序遍历二叉树(递归方法)

// 中(根)序遍历
Status InOrderTraverse(BiTree T)	// 指针T指向二叉树的根节点
{
    if(T==NULL) 
        return OK; // 空二叉树
    else
    {
        InOrderTraverse(T->lchild);	// 递归遍历左子树
        visit(T);	// 访问根结点
        InOrderTraverse(T->rchild);	// 递归遍历右子树
    }
}

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

Ⅴ 中序遍历二叉树(非递归方法)

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

• 基本思想
  • ① 建立一个栈；
  • ② 根结点进栈，遍历左子树；
  • ③ 根结点出栈，输出根结点，遍历右子树。

// 中序遍历非递归算法
Status InOrderTraverse (BiTree T) 
{
    BiTree p; 
    InitStack(S);
    p=T;
    while(p || !StackEmpty(S))
    {
        if(p)
        {
            Push(S,p);	// 入栈
            p=p->lchild;
        }
        else 
        { 
            Pop(s,q);	// 弹出栈顶元素，用q接收
            cout << q->data << endl;
            p=q->rchild;
        }
	}//while
	return OK;
}

Ⅵ 二叉树的层次遍历

对于一颗二叉树，从根结点开始，按从上到下、从左到右的顺序访问每一个结点。每一个结点仅仅访问一次。

• 算法设计思路：使用一个队列。
  • ① 将根结点进队；
  • ② 队不空时循环：从队列中出列一个结点*p，访问它;
    • 若它有左孩子结点，将左孩子结点进队；
    • 若它有右孩子结点，将右孩子结点进队。

// 使用循环顺序队列，其数据类型定义为
typedef struct
{
    BTNode data[MaxSize];	// 存放队中元素
    int front;	// 队头“指针”
    int rear;	// 队尾“指针”
}SqQueue;

// 二叉树层次遍历算法
void LevelOrder(BTNode *b) 
{
    BTNode *p;
    SqQueue *qu;	
    InitQueue(qu);	// 初始化队列
    enQueue(qu,b);	// 根结点指针进入队列
    while (!QueueEmpty(qu))	// 队不为空，则循环
    {
        deQueue(qu, p);	// 出队结点，用指针p接收
        cout << p->data << endl;	// 访问结点p
        if (p->lchild!=NULL) 
            enQueue(qu, p->lchild);	// 有左孩子时将其进队
        if (p->rchild!=NULL) 
            enQueue(qu, p->rchild);	// 有右孩子时将其进队
    }
}

Ⅶ 遍历二叉树算法的应用

(1) 构建一颗二叉树

按先序遍历序列建立二叉树的二叉链表。

例：已知先序序列为：ABCDEGF

① 从键盘输入二叉树的结点信息，建立二叉树的存储结构；
② 在建立二叉树的过程中按照二叉树先序方式建立。

注意，只知道先序序列是无法得到唯一的一个二叉树的，那怎么办呢，一种方法是补充空结点，如下图所示。

根据补充的空结点的位置不一样，所得的树就不一样，这样就可确定一颗二叉树了。可以用一个特殊的字符表示空节点(例如：#)。

// 递归算法
Status CreateBiTree(BiTree& T)
{
    char ch;
    cin>>ch;
    if(ch == '#')
        T= NULL;
    else 
    {
        if ( !(T=new BiTNode) )
            exit(OVERFLOW); 
        T->data = ch;	// 生成根结点
        CreateBiTree(T->lchild);	// 构造左子树
        CreateBiTree(T->rchild);	// 构造右子树
    }
    return OK;
} // CreateBiTree

(2) 复制一颗二叉树

• ① 如果是空树，递归结束；
• ② 否则，申请新结点空间，复制根结点
  • 递归复制左子树
  • 递归复制右子树

int Copy(BiTree T, BiTree& NewT)
{
    if(T==NULL)
    { //如果是空树返回0
        NewT = NULL; 
        return 0;
    }
    else 
    {
        NewT = new BiTNode;
        NewT->data=T->data;
        // 递归复制
        Copy(T->lChild, NewT->lchild);
        Copy(T->rChild, NewT->rchild);
    }
}

(3) 计算二叉树的深度

• ① 如果是空树，则深度为0
• ② 否则，递归计算左子树的深度记为$m$，递归计算右子树的深度记为$n$
  • 二叉树的深度计算方法为：$\max(m, n) + 1$。

int Depth( BiTree T)
{
    if(T==NULL)
        return 0;	// 如果是空树返回0
    else
    {
        m = Depth(T->lChild);
        n = Depth(T->rChild);
        if(m>n)
            return (m+1);
        else 
            return(n+1);
    }
}

(4) 计算结点总数

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

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

(5) 计算二叉树叶子结点数(补充)

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

int LeafCount(BiTree T)
{
    if(T==NULL)	// 如果是空树返回0
        return O;
    if(T->lchild == NULL && T->rchild == NULL)
        return 1;	// 如果是叶子结点返回1
    else
        return LeafCount(T->lchild)+LeafCount(T->rchild);
}

5.3 线索二叉树

Ⅰ 线索二叉树概念

当用二叉链表作为二叉树的存储结构时可以很方便地找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点。

• 提出的问题：如何寻找特定遍历序列中二叉树结点的前驱和后继？？？

• 解决的方法

  • 方法1：通过遍历寻找——费时间；

  • 方法2：再增设前驱、后继指针域——增加了存储负担；

  • 方法3：利用二叉链表中的空指针域。

    回顾：二叉树链表中空指针域的数量：

    具有$n$个结点的二叉链表中，一共有$2n$个指针域；因为$n$个结点中有$n-1$个孩子，即$2n$个指针域中，有$n-1$个用来指示结点的左右孩子，其余$n+1$个指针域为空！

利用二叉链表中的空指针域：如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱，如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继。——这种改变指向的指针称为“线索”。

加上了线索的二叉树称为线索二叉树(Threaded Binary Tree)，对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。

为区分lchild和rchild指针到底是指向孩子的指针，还是指问前趋或有后继的指针，对二叉链表中每个结点增设两个标志域ltag 和 rtag ，并约定：
—— ltag=0， lchild 指向该结点的左孩子；
—— ltag =1，lchild 指向该结点的前驱；
—— rtag=0，rchild 指向该结点的右孩子；
—— rtag =1，rchild 指向该结点的后继。

这样，线索二叉树中的结点构成如下：

typdef struct BiThrnode
{
    int data;
    bool ltag;
    bool rtag;
    struct BiThrnode* lchild;
    struct BiThrnode* rchild;
}BiThrNode, *BiThrTree;

Ⅱ 先序线索二叉树

5.4 树和森林

注意，树是不分左右顺序的。

Ⅰ 树的存储结构

(1) 双亲表示法

实现：定义结构数组，存放树的结点，每个结点含两个域：① 数据域：存放结点本身信息。② 双亲域：指示本结点的双亲结点在数组中的位置。如下图所示。

这种方法有比较明显的优缺点：优点：找双亲容易；缺点：找孩子麻烦。

// 树的单个结点的数据存储类型定义
typedef struct PTnode
{
    TElemType data;
    int parent;
}PTNode;

//=====================================================

// 树的数据存储类型定义
# define MAX_TREE_SIZE 100

typedef struct
{
    PTNode nodes[MAX_TREE_SIZE];
    int r;	// 根节点的位置
    int n;	// 节点个数
}PTree;

(2) 孩子链表

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则$n$个结点有$n$个孩子链表(叶子的孩子链表为空表)。而 $n$ 个头指针又组成一个线性表，用顺序表(含$n$个元素的结构数组)存储。

// 孩子结点结构
typedef struct CTnode
{
    int child;
    struct CTnode* next;
}* ChildePtr;

// 双亲结点结构
typedef struct
{
    TElemType data;
    ChildePtr firstchild;
}CTBox;

//=====================================================

// 树的数据存储类型定义
# define MAX_TREE_SIZE 100

typedef struct
{
    CTBox nodes[MAX_TREE_SIZE];
    int r;	// 根节点的位置
    int n;	// 结点个数
}PTree;

这种方法有比较明显的优缺点：优点：找孩子容易；缺点：找双亲麻烦。

(3) 带双亲的孩子链表

结合上述2种方法的优点。

(4) 孩子兄弟表示法 / 二叉树表示法 / 二叉链表表示法 （常用）

实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。

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

Ⅱ 树与二叉树的转换

将树转化为二叉树进行处理，利用二叉树的算法来实现对树的操作。

由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系。

给定一棵树，可以找到唯一的一棵二叉树与之对应。

• 树转换为二叉树：容易发现规律，右兄弟转换为右孩子，具体步骤如下：

  • ① 加线：在兄弟之间加一连线
  • ② 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系；
  • ③ 旋转：以树的根结点为轴心，将整树顺时针转45°。

• 二叉树转换为树：

  • ① 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子….沿分支找到的所有右孩子，都与p的双亲用线连起来；
  • ② 抹线：抹掉原二叉树中双亲与右孩子之间的连线；
  • ③ 调整：将结点按层次排列，形成树结构。

Ⅲ 森林与二叉树的转换

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

Ⅳ 树和森林的遍历

(1) 树的遍历(三种方法)

• 先(根)序遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。
• 后(根)序遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。
• 按层次遍历：若树不空，则自上而下自左至右访问树中每个结点。

(2) 森林的遍历

为了遍历森林，我们以下面这种视角重新审视森林的结构：

将森林看作由三部分构成：Part 1：森林中第一棵树的根结点；Part 2：森林中第一棵树的子树森林；Part 3：森林中其它树构成的森林。

• 先序遍历：若森林不空，则
  • ① 访问森林中第一棵树的根结点；
  • ② 先序遍历森林中第一棵树的子树森林；
  • ③ 先序遍历森林中(除第一棵树之外)其余树构成的森林。
  • 本质：依次从左至右对森林中的每一棵树进行先(根)序遍历。
• 中序遍历：若森林不空，则
  • ① 中序遍历森林中第一棵树的子树森林；
  • ② 访问森林中第一棵树的根结点；
  • ③ 中序遍历森林中(除第一棵树之外)其余树构成的森林。
  • 本质：依次从左至右对森林中的每一棵树进行后(根)序遍历。

5.5 哈夫曼树(最优二叉树)

Ⅰ 哈夫曼树的概念

首先来看个例子：

//【例】编程:将学生的百分制成绩转换为五分制成绩
// <60:E  60-69:D  70-79:C  80-89:B  90-100:A

if(score<60)
    grade == 'E';
else if(score<70)
    grade ==`'D';
else if(score<80)
    grade =='C';
else if(score<90)
    grade ==`'B';
else
    grade =='A';

判断树：用于描述分类过程的二叉树。

如果每次的输入量很大，则应考虑程序的操作时间。

若学生的成绩数据共10000个：E、D、C、B、A分别占总数据的5%、15%、40%、30%、10%。则5%的数据需1次比较，15%的数据需2次比较，40%的数据需3次比较，40%的数据需4次比较，因此10000个数据比较的次数为：

$$10000×(1×5\%+2×15\%+3×40\%+4×10\%)=31500次$$

考虑如何减少一些数据量：

(1) 相关概念

路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

结点的路径长度：两结点间路径上的分支数。

树的路径长度：从树根到每一个结点的路径长度之和，记作：TL。

$$树(a)的路径长度：TL(a) = 0+1+1+2+2+3+3+4+4=20 \\ 树(b)的路径长度：TL(b) = 0+1+1+2+2+2+2+3+3=16$$

一个小结论：结点数目相同的二叉树中，完全二叉树是路径长度最短的 一种(不唯一) 二叉树。

权重(weight)：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作WPL。

$$WPL = \sum_{k=1}^n w_k l_k$$

哈夫曼树：带权路径长度(WPL)最短的树。

注意：

“带权路径长度最短”是在“度相同”的树中比较而得的结果，因此有最优二叉树、最优三又树之称等等。

结点的度：是结点拥有子树的的个数；树的度：是所有结点的度的最大值。

Ⅱ 哈夫曼树的构造

上面我开门观察得到一个结论：哈夫曼树具有“位高权重”的特点，也即离根近的叶子权重高，离根远的叶子权重低。根据这个特点，有如下的构造思想：

• 贪心算法：构造哈夫曼树时首先选择权值小的叶子结点。
  • ① 构造森林全是根
    根据$n$个给定的权值$(w_1, w_2, \cdots, w_n)$构成$n$棵二叉树的森林$F=(T_1, T_2, \cdots, T_n)$，其中$T_i$只有一个带权为$w_i$的根结点。
  • ② 选用两小造新树
    在$F$中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
  • ③ 删除两小添新人
    在$F$中删除这两棵树，同时将新得到的二叉树加入森林中。
  • ④ 重复②和③
    直到森林中只有一棵树为止，这棵树即为哈夫曼树。

这种算法得到的哈夫曼树：其结点的度数为0或2，没有度为1的结点。此外，包含$n$个叶子结点的哈夫曼树中共有$2n-1$个结点。

Ⅲ 哈夫曼树的实现

(1) 哈夫曼树的存储结构

既可采用顺序存储结构，又可采用链式存储结构，一般而言采用顺序存储结构比较简单：一维结构数组。

typedef struct 
{
    int weight;	// 权重值
    int parent;	// 双亲
    int lch;	// 左孩子
    int rch;	// 右孩子
}HTNode,*HuffmanTree;

(2) 实现：分2步

• 初始化
  • HT [1, 2, ..., 2n-1]:lch=rch=parent=0；
  • 输入初始n个叶子结点：设置HT[1,...,n]的weight值；
• 构造过程
  • 进行以下n-1次合并，依次产生n-1个结点HT[n+1, ..., 2n-1]
  • a. 在HT[1, ..., i-1]中选两个未被选过(从parent ==0 的结点中选)的weight最小的两个结点HT[s1]和HT[s2]，s1、s2为两个最小结点下标；
  • b. 修改HT[s1]和HT[s2]的parent值：HT[s1].parent=i, HT[s2].parent=i；
  • c. 修改新产生的HT[i]：
    HT[i].weight=HT[s1].weight + HT[s2].weight
HT[i]. lch=s1; HT[i].rch=s2

void CreatHuffmanTree (HuffmanTree HT, int n)	// 构造哈夫曼树--哈夫曼算法
{
    // 初始化
    if(n <= 1)
        return;
    int m = 2*n-1;	// 数组共2n-1个元素
    HT = new HTNode[m+1];	// 0号单元未用，HT[m]表示根结点
    for(int i=1; i<=m; ++i)	// 将2n-1个元素的lch、rch、parent置为0
    {
        HT[i].lch=0; 
        HT[i].rch=0; 
        HT[i].parent=0;
    }
    for(int i=1; i<=n; ++i)
        cin >> HT[i].weight;	// 输入前n个元素的weight值
    // =================初始化结束，下面开始建立哈夫曼树===========
    
    for(int i=n+1; i<=m; i++)	// 合并产生n-1个结点, 构造Huffman树
    {
        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的权值为左右孩子权值之和
    }
}

Ⅳ 哈夫曼数的应用——哈夫曼编码

• 两个问题
  • 1、为什么哈夫曼编码能够保证是前缀编码？
    因为没有一片树叶是另一片树叶的祖先，所以每个叶结点的编码就不可能是其它叶结点编码的前缀。
  • 2、为什么哈夫曼编码能够保证字符编码总长最短？
    因为哈夫曼树的带权路径长度最短，故字符编码的总长最短。
• 性质
  • ① 哈夫曼编码是前缀码；
  • ② 哈夫曼编码是最优前缀码；

哈夫曼树的实现

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

§ 6 图

6.1 图的定义和术语

Ⅰ 图的基本概念

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

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

稀疏图：有很少边或弧(有向图的边)的图($e<n \log n$)。

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

网：边/弧带权的图。

邻接： 有边/弧相连的两个顶点之间的关系。存在$(v_i, v_j)$，则称$v_i$和$v_j$互为邻接点；存在$$，则称$v_i$邻接到$v_j$，$v_j$邻接于$v_i$。

注意：

在离散数学中，$(\cdot, \cdot)$表示的无序偶对，$<\cdot, \cdot>$表示有序偶对。

关联(依附)：边/弧与顶点之间的关系。

顶点的度：与该顶点相关联的边的数目，记为$TD(V)$。在有向图中，顶点的度等于该顶点的入度与出度之和。

注意：

入度：顶点$v$的入度是以$v$为终点的有向边的条数，记作$ID(v)$；

出度：顶点$v$的出度是以$v$为始点的有向边的条数，记作$OD(v)$。

问：当有向图中仅1个顶点的入度为0，其余顶点的入度均为1，此时是何形状?
答：是树！而且是一棵有向树！

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

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

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

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

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

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

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

子图：设有两个图G=(V，{E})、G1=(V1，{E1})，若$V1 \subseteq V$，$E1 \subseteq E$，则称 G1是G的子图。

连通分量(强连通分量)：

无向图G的极大连通子图称为G的连通分量。极大连通子图意思是：该子图是G连通子图，将G的任何不在该子
图中的顶点加入，子图不再连通。

有向图G的极大强连通子图称为G的强连通分量。极大强连通子图意思是:该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。

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

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

生成森林：对非连通图，由各个连通分量的生成树的集合。

Ⅱ 案例引入

案例6.1 六度空间理论

“六度空间”理论又称作六度分隔(SixDegrees of Separation )理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。”该理论产生于20世纪60年代，由美国心理学家米尔格伦提出。

把六度空间理论中的人际关系网络抽象成一个无向图G。用图G中的一个顶点表示一个人，两个人认识与否用代表这两个人的顶点之间是否有一条边来表示。从任一顶点出发用广度优先方法对图进行遍历，统计所有路径长度不超过7的顶点

Ⅲ 图的类型定义

// 图的抽象数据类型定义如下
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>的信息(权)

	// 图的基本操作P
	// 图的创建操作。
		// 初始条件:无。
		// 操作结果:生成一个没有顶点的空图G。
    Create_Graph() 

    // 求图中的顶点v的值。
        // 初始条件:图G存在，v是图中的一个顶点。
        // 操作结果:求v的值
    GetVex(G,v);

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

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

} ADT Graph

6.2 图的存储结构

前面已经介绍了图的逻辑结构：多对多。

图没有顺序存储结构，但可以借助二维数组来表示元素间的关系——数组表示法(邻接矩阵)。

图有链式存储结构，具体有3种形式：① 多重链表；② 邻接表邻接多重表；③ 十字链表。

Ⅰ 数组表示法(邻接矩阵)

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

设图$A=(V, E)$，有$n$个顶点，则可构建一个一维数组，称为顶点表$\text{Vexs}[n]$：

i	0	1	2	…	n-1
vexs[i]	v~1~	v~2~	v~3~	…	v~n-1~

图的邻接矩阵是一个二维数组 $\text{A. arcs}[n][n]$，定义为:

$$\text{A. arcs}[i][i] = \begin{cases} &1, & <i, j> \in E ~ 或 ~ (i, j) \in E \\ & 0,& \text{others} \end{cases}$$

分析1：无向图的邻接矩阵是对称的；

分析2：无向图顶点$v_i$的度=第$i$行(列) 中1的个数；

分析3：完全图的邻接矩阵中，对角元素为0，其余1。

分析1：有向图的邻接矩阵可能是不对称的；

分析2：顶点的出度=第$i$行元素之和，顶点的入度=第$i$列元素之和，顶点的度=第$i$行元素之和+第$i$列元素之和。

网(即有权图)的邻接矩阵表示法：

$$\text{A. arcs}[i][i] = \begin{cases} &w_{ij}, & <i, j>~ 或 ~ (i, j) \in VR \\ & \infty,& \text{others} \end{cases}$$

Ⅱ 邻接矩阵的存储表示

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

#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; // Adjacency Matrix Graph

采用邻接矩阵表示法创建无向网(无向图、有向图、有向网)

• 【算法思想】
  • (1) 输入总顶点数和总边数。
  • (2) 依次输入点的信息存入顶点表中。
  • (3) 初始化邻接矩阵，使每个权值初始化为极大值。
  • (4) 构造邻接矩阵。

// 图G中查找顶点u，存在则返回顶点表中的下标; 否则返回-1
int LocateVex(AMGraph G, VertexType u)
{
    int i;
    for( i=0; i<G.vexnum; ++i)
        if(u==G.vexs[i])
            return i;
    return -1;
}

// 采用邻接矩阵表示法，创建无向网
Status CreateUDN(AMGraph& G)
{
    Gcin >> G.vexnum >> G.arcnum;	// 输入总顶点数，总边数
    for( int i = 0; i<G.vexnum; ++i)// 依次输入点的信息
        cin >> G.vexs[i];
    for( int i = 0; i<G.vexnum; ++i) // 初始化邻接矩阵
        for( int j = 0; j<G.vexnum; ++j)
            G.arcs[i][j] = MaxInt;	// 边的权值均置为极大值(无穷)
    for( int k = 0; k<G.arcnum; ++k){	// 构造邻接矩阵
        cin >> v1 >> v2 >> w;	// 输入一条边所依附的顶点及边的权值
        i = LocateVex(G, v1);
        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;
}//CreateUDN

邻接矩阵存储方式有什么不好？

① 不便于增加和删除顶点；② 浪费空间——存稀疏图(点很多而边很少)有大量无效元素，对稠密图(特别是完全图)还是很合算的；③ 浪费时间——例如统计稀疏图中一共有多少条边。

Ⅲ 邻接表表示法(链式)

(1) 无向图/网的邻接表

• 顶点：按编号顺序将顶点数据存储在一维数组中；
  • 头节点data：存放结点数据；
  • 头节点firstarc：存放邻接结点的数组下标索引。
• 关联同一顶点的边(以顶点为尾的弧)：用线性链表存储。
  • 表结点adjvex：
  • 表结点nextarc：链域，指示下一条边或弧；
  • 附加：表结点weight：若有权值，则添加weight表示。

特点

① 邻接表不唯一；

② 若无向图中有$n$个顶点、$e$条边，则其邻接表需$n$个头结点和$2e$个表结点(空间复杂度$O(n+2e)$)。适宜存储稀疏图。

③ 无向图中顶点$v_i$的度为第$i$个单链表中的结点数。

(2) 有向图/网的邻接表

若是带有权值的网，则在表结点上可以再添加一个单元存储info。

(3) 图的邻接表实现

#define MVNum 100	// 最大顶点数

// 表结点定义(边、弧结点)
typedef struct Arcnode
{
    int adjvex;	// 该边所指向的顶点的位置
    struct Arcnode* nextarc;	// 指向下一条边的指针
    OtherInfo info;	// 和边相关的信息
}ArcNode;

// 头节点定义
typedef struct VNode
{
    VerTexType data;	// 顶点信息
    ArcNode* firstarc;	// 指向第一条依附该顶点的边的指针 
}VNode, AdjList[MVNum];	// AdjList表示邻接表类型
// 这里 AdjList v; 等价于 VNode v[MVNum];

// 邻接表图定义
typedef struct 
{
    AdjList vertices;	// vertices--vertex的复数
    int vexnum, arcnum;	// 图的当前顶点数和弧数
}ALGraph;

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

• 【算法思想】
  • (1) 输入总顶点数和总边数；
  • (2) 建立顶点表
    依次输入点的信息存入顶点表中，并使每个表头结点的指针域初始化为NULL创建邻接表；
  • (3) 创建邻接表
    依次输入每条边依附的两个顶点，确定两个顶点的序号$i$和$j$，建立边结点将此边结点分别插入到$v_i$和$v_j$对应的两个边链表的头部。

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

• 邻接表特点
  • 方便找任一顶点的所有“邻接点“
  • 节约稀疏图的空间：需要N个头指针+2E个结点(每个结点至少2个域)
  • 方便计算任一顶点的“度”?
    • 对无向图：是的
    • 对有向图：只能计算“出度”，需要构造“逆邻接表”(存指向自己的边)来方便计算”入度“
    • 不方便检查任意一对顶点间是否存在边。

Ⅳ 图的其他改进表示法

(1) 十字链表——用于有向图

十字链表(Orthogonal List)是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。

有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。

(2) 邻接多重表——用于无向图

第一个格子是标记域，搜索时用的，用来标记是否被查找过；

0后边指针的找相同相同位置带0的，1后边招相同位置带1的，推广到任意数。

6.3 图的遍历

Ⅰ 遍历的基本概念

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

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

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

• 所以问题来了，怎样避免重复访问？
  • 解决思路：设置辅助数组 visited[n]，用来标记每个被访问过的顶点。
  • 初始状态visited [i]设为0；顶点$i$被访问，改 visited [i]为1，防止被多次访问。
• ==图常用的遍历算法==：
  • ① 深度优先搜索(Depth First Search—DFS )，思想：一条道走到黑，然后再回退。
  • ② 广度优先搜索(Breadth Frist Search—BFS)，

Ⅱ 深度优先搜索(DFS)

(1) DFS的基本步骤

• 【算法思想】
  • 在访问图中某一起始顶点$v$后，由$v$出发，访问它的任一邻接顶点$w_1$；
  • 再从$w_1$出发，访问与$w_1$邻接但还未被访问过的顶点$w_2$；
  • 然后再从$w_2$出发，进行类似的访问 … …
  • 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点$u$为止。
  • 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。
    • 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；
    • 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

(2) 基于邻接矩阵表示的无向图DFS

• 连通图的遍历

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

• 非连通图的遍历

(3) 基于邻接表表示的无向图DFS

Ⅲ 广度优先搜索(BFS)

(1) BFS的基本步骤

• 【算法思想】
  • 从图的某一结点出发，首先依次访问该结点的所有邻接点$v_{i1}, v_{i2}, …, v_{in}$，再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点；
  • 重复此过程，直至所有顶点均被访问为止。

(2) 基于邻接表表示的无向图BFS

// 按广度优先非递归遍历连通图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进队
            }//if
        }//for
    }//while
}//BFS

6.4 图的应用

Ⅰ 最小生成树

(1) 最小生成树的概念

生成树：(所有顶点)均由边连接在一起，但不存在回路的图。

• 所有生成树具有以下共同特点：

  • 生成树的顶点个数与图的顶点个数相同；
  • 生成树是图的极小连通子图。去掉一条边则非连通；
  • 一个有$n$个顶点的连通图的生成树有$n-1$条边；
  • 在生成树中再加一条边必然形回路；
  • 生成树中任意两个顶点间的路径是唯一的。

  注意：含$n$个顶点$n-1$条边的图不一定是生成树。

设图 G=(V,E)是个连通图，当从图任一顶点出发遍历图G 时，将边集 E(G)分成两个集合 T(G)和 B(G)。其中 T(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1(V, T)是图的极小连通子图。即子图G1 是连通图 G 的生成树。

(2) 最小生成树的应用

• 最小代价生成树

给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。

(3) 构造最小生成树MST

构造最小生成树的算法很多，其中多数算法都利用了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$中顶点的边中选取权值最小的边。

==构造最小生成树方法一：普里姆(Prim)算法==

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

==构造最小生成树方法二：克鲁斯卡尔(Kruskal) 算法==

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

Ⅱ 最短路径

典型用途：交通网络的问题 —— 从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？

交通网络用有向网来表示：顶点 —— 表示地点，弧 —— 表示两个地点有路连通，弧上的权值 —— 表示两地点之间的距离、交通费或途中所花费的时间等。

问题抽象：在有向网中 A点(源点)到达B点(终点)的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

最短路径与最小生成树不同，路径上不一定包含$n$个顶点，也不一定包含 $n-1$ 条边。

最短路径的2类问题：

• 单源最短路径：用Dijkstra(迪杰斯特拉)算法
• 所有顶点间的最短路径：用Floyd(弗洛伊德)算法

(1) Dijkstra(迪杰斯特拉)算法

• 【思想概述】
  • 初始化：先找出从源点$v_0$到各终点$v_k$的直达路径$(v_0, v_k)$，即通过一条弧到达的路径；
  • 选择：从这些路径中找出一条长度最短的路径$(v_0, u)$；
  • 更新：然后对其余各条路径进行适当调整：
    • 若在图中存在弧$(u, v_k)$，且$(v_0, u) + (u, v_k) < (v_0, v_k)$，则以路径$(v_0, u , v_k)$代替$(v_0, v_k)$；
  • 在调整后的各条路径中，再找长度最短的路径，依此类推。
• 【迪杰斯特拉(Dijkstra)算法】按路径长度递增次序产生最短路径
  • 把$V$分成两组：
    • (1) $S$：已求出最短路径的顶点的集合；
    • (2) $T=V-S$：尚未确定最短路径的顶点集合。
  • 将$T$中顶点按最短路径递增的次序加入到$S$中，保证：
    • (1) 从源点$v_0$到$S$中各顶点的最短路径长度都不大于从$v_0$到$T$中任何顶点的最短路径长度；
    • (2) 每个顶点对应一个距离值：
      • $S$ 中顶点：从$v_0$到此顶点的最短路径长度。
      • $T$ 中顶点：从$v_0$到此顶点的只包括$S$中顶点作中间顶点的最短路径长度。

(2) Floyd(弗洛伊德)算法

• 所有顶点间的最短路径
  • 方法一：每次以一个顶点为源点，重复执行 Dijkstra 算法 n次。
  • 方法二：弗洛伊德(Floyd)算法
• 【算法思想】
  • 逐个顶点试探
  • 从$v_i$到$v_j$的所有可能存在的路径中选出一条长度最短的路径

Ⅲ 有向无环图：拓扑排序

有向无环图：无环的有向图，简称 DAG图(Directed Acycline Graph)。

有向无环图常用来描述一个工程或系统的进行过程（通常把计划、施工、生产、程序流程等当成是一个工程）。一个工程可以分为若干个子工程，只要完成了这些子工程（活动）就可以导致整个工程的完成。

• AOV 网：拓扑排序问题
  • 用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称 AOV网(Activity On Vertex network)。
• AOE 网：关键路径问题
  • 用一个有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网(Activity On Edge)。

AOV 网的特点：
① 若从$i$到$j$有一条有向路径，则$i$是$j$的前驱，$j$是$i$的后继。
② 若$$是网中有向边，则$i$是$j$的直接前驱，$j$是$i$的直接后继。
③ AOV 网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。

问题：如何判别 AOV 网中是否存在回路？

拓扑排序：在 AOV 网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若 AOV 网中有弧$$存在，则在这个序列中，$i$一定排在$j$的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。

拓扑排序的一个重要应用：检测 AOV 网中是否存在环方法

对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该 AOV 网必定不存在环。

Ⅳ 有向无环图：关键路径

关键路径问题引入：

设一个工程有 11项活动，9个事件：

事件$v_1$—表示整个工程开始(源点:入度为0的顶点)

事件$v_9$—表示整个工程结束(汇点:出度为0的顶点)

对于AOE网，我们关心两个问题：① 完成整项工程至少需要多少时间？② 哪些活动是影响工程进度的关键？

这两个问题涉及关键路径算法——求路径最长(路径上各活动持续时间之和)。

• 如何确定关键路径，需要定义4个描述量：
  • ve(vj)： 表示事件vj 的最早发生时间，例：ve(v1)=0, ve(v2)= 30；
  • vl(vj) ：表示事件vj的最迟发生时间，例：vl(v4)=165；
  • e(i)：表示活动 ai 的最早开始时间，例：e(a3)= 30；
  • l(i)表示活动 ai的最迟开始时间，例：l(a3)=120。
• l(i)-e(i)表示完成活动ai的时间余量。例：l(3)-e(3)= 90；
• 关键活动：关键路径上的活动，l(i)==e(i)(即l(i) - e(i) == 0的活动。

如何找l(i)==e(i)的关键活动？

设活动ai用弧$$表示，其持续时间记为：$w_{j,k}$，则有：

关系	图示
$\begin{cases} e(i) = ve(j) \\ l(i) = vl(k) - w_{j,k} \end{cases}$

如何求ve(j) 和 v(j)？

(1) 从 ve(1)=0 开始向前递推，$ve(j) = \max_i \{ ve(i) + w_{i,j}\}, \in T, 2\leq j \leq n$，其中$T$是所有以$j$为开头的弧的集合。

(2) 从 v(n)= ve(n)开始向后递推，$vl(i) = \min_j \{ vl(j) - w_{i,j}\}, \in S, 1\leq i \leq n-1$，其中 $S$ 是所有以$i$为尾的弧的集合。

1. 若网中有几条关键路径，则需加快同时在几条关键路径上的关键活动。如：a11、a10、a8、a7；
2. 若一个活动处于所有的关键路径上，那么提高该活动的速度，就能缩短工程的完成时间。如：a1、a4；
3. 处于所有的关键路径上的活动完成时间不能缩短太多，否则会使原来的关键路径变成不是关键路径。这时，必须重新寻找关键路径。如：a1由6 天变成 3天，就会改变关键路径。

§ 7 查找操作

7.1 查找的基本概念

本章讲解的查找操作，既不是在线性表上找，也不是在树或图上进行查找，而是在一个新的数据结构——查找表上进行查找。

查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系(没有前趋、后继、邻接等关系)，因此查找表是一种应用灵便的结构。

查找操作：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录。

• 关键字：用来标识一个数据元素(或记录)的某个数据项的值。
  • 主关键字：可唯一地标识一个记录的关键字是主关键字；
  • 次关键字：反之，用以识别若干记录的关键字是次关键字。
• 查找表可分为两类
  • 静态查找表：仅作“查询”(检索)操作的查找表。
  • 动态查找表：作“插入”和“删除”操作的查找表。
    有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为’在查找表中”的数据元素，此类表为动态查找表。

查找的方法取决于查找表的结构，即表中数据元素是依何种关系组织在一起的。

由于对查找表来说，在集合中查询或检索一个“特定的”数据元素时若无规律可循，只能对集合中的元素一一加以辨认直至找到为止。而这样的“查询”或“检索”是任何计算机应用系统中使用频度都很高的操作，因此设法提高查找表的查找效率，是本章讨论问题的出发点。

为提高查找效率，一个办法就是在构造查找表时，在集合中的数据元素之间人为地加上某种确定的约束关系。

7.2 线性表上的查找

Ⅰ 顺序查找(线性查找)

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

数据元素类型定义：

typedef struct
{
    KeyType key;	// 关键字域
    ...	// 其他域
}ElemType;

typedef struct
{
    ElemType* R;	// 表基地址
    int length;	// 表长
}SSTable;

int Search_Seq( SsTable ST , KeyType key )
{
    //若成功返回其位置信息，否则返回0
    for(int i=ST.length; i>=1; --i)
        if( ST.R[i].key==key )
            return i;
    return 0;
}

容易发现：每执行一次循环都要进行两次比较，是否能改进？

改进：把待查关键字key存入表头（“硝兵“、监视哨”），从后往前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。

// 设置监视哨的顺序查找
int Search_Seq( SsTable ST , KeyType key )
{
    //若成功返回其位置信息，否则返回0
    ST.R[0].key = key
    for(int i=ST.length; ST.R[i].key!=key; --i);
    
    return i;
}

当 ST.length 较大时，此改进能使进行一次查找所需的平均时间几乎减少一半。

• 顺序查找的特点
  • 优点：算法简单，逻辑次序无要求，且不同存储结构均适用。
  • 缺点：ASL太长，时间效率太低。

Ⅱ 折半查找(二分查找)

有序表表示静态查找表 → 折半查找：每次将待查记录所在区间缩小一半。

• 【折半查找算法(非递归算法)】
  • 设表长为$n$，$\text{low}$、$\text{high}$和$\text{mid}$分别指向待查元素所在区间的上界、下界和中点，key为给定的要查找的值；
  • 初始时，令$\text{low}=1$，$\text{high}=n$，$\text{mid} = \lfloor (\text{low} + \text{high})/2 \rfloor$；
  • 让k与mid指向的记录比较
    • 若key==R[mid].key，查找成功；
    • 若key<R[mid].key，则high=mid-1；
    • 若key>R[mid].key，则low=mid+1；
  • 重复上述操作，直至low>high时，查找失败。

int Search_Bin( SSTable ST, KeyType key )
{
    // 置区间初值
    int low=1;
    int high= STlength ;
    
    while (low <= high) 
    {
        int 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;	// 顺序表中不存在待查元素
}// Search_Bin

补充【算法7.3】折半查找—递归算法

int Search_Bin (ssTable ST, keyType key, int low, int high) 
{
    if(low>high)
        return 0;	// 查找不到时返回0
    mid=(low+high)/2;
    if(key==ST.elem[mid].key)
        return mid;
    else if(key<sTelem[mid].key)
        return Search_Bin(ST, key, low, mid-1);
    else
        return Search_Bin(ST, key, mid-1, high);
}

• 折半查找的特点
  • 折半查找优点：效率比顺序查找高。
  • 折半查找缺点：只适用于有序表且限于顺序存储结构（对线性链表无效）；此外，只适合查找操作，若查找完后还有插入、删除等操作，则需要移动大量元素。

Ⅲ 分块查找

条件1：将表分成几块，且表或者有序，或者分块有序。若$i<j$，则第$j$块中所有记录的关键字均大于第$i$块中的最大关键字。
条件2：建立“索引表”(每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序)。

查找过程：先确定待查记录所在块(顺序或折半查找)再在块内查找(顺序查找)。

7.3 树表上的查找

对于前面讲的线性表查找，当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录。相当复杂。

一种方法是：改用动态查找表——几种特殊的树，表结构在查找过程中动态生成。对于给定值key，若表中存在，则成功返回，否则，插入关键字等于key的记录。

特殊的树：二叉排序树、平衡二叉树、红黑树、B-树、B+树、键树。

Ⅰ 二叉排序树(Binary Sort Tree)

(1) 定义

二叉排序树或是空树，或是满足如下性质的二叉树：

(1) 若其左子树非空，则左子树上所有结点的值均小于根结点的值；
(2) 若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；
(3) 其左右子树本身又各是一棵二叉排序树。

二叉排序树的性质：中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

(2) 查找操作

【算法步骤】

• 若查找的关键字等于根结点，成功；
• 否则：
  • 若小于根结点，查其左子树
  • 若大于根结点，查其右子树
  • 在左右子树上的操作类似

【二叉排序树的递归查找】

• 若二叉排序树为空，则查找失败，返回空指针。
• 若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较：
  • ① 若key == T->data.key，则査找成功，返回根结点地址；
  • ② 若key < T->data.key，则进一步查找左子树；
  • ③ 若key > T->data.key，则进一步査找右子树。

【存储结构】

typedef struct
{
    KerType key;	// 关键字项
    InfoType otherinfo;	// 其他数据域
}ElemType;

typedef struct BSTnode
{
    ElemType data;	// 数据域
    struct BSTnode* lchild, * rchild;	// 左右孩子指针
}BSTNode, *BSTree;

// 递归查找
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); 	// 在右子树中继续査找
} // SearchBST

分析易知：含有$n$个结点的二叉排序树的平均查找长度和树的形态有关。

问题：如何提高形态不均衡的二又排序树的查找效率？

解决办法：做“平衡化”处理，即尽量让二叉树的形状均衡！

【补充：二叉排序树的插入操作】

• 若二叉排序树为空，则插入结点作为根结点插入到空树中；
• 否则，继续在其左、右子树上查找
  • 树中已有，不再插入；
  • 树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子

【补充：二叉排序树的生成操作】

从空树出发，经过一系列的查找、插入操作之后，可生成一颗二叉排序树。

一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。

插入的结点均为叶子结点，故无需移动其他结点。相当于在有序序列上插入记录而无需移动其他记录。

但是：关键字的输入顺序不同，建立的二叉排序树不同。如下图所示。

【补充：二叉排序树的删除操作】

从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。

由于中序遍历二叉排序树可以得到一个递增有序的序列。那么，在叉排序树中删去一个结点相当于删去有序序列中的一个结点。

• 将因删除结点而断开的二又链表重新链接起来；
• 防止重新链接后树的高度增加；

第一种情况：被删除的结点是叶子结点

操作方法：直接删去该结点。

第二种情况：被删除的结点只有左子树或者只有右子树

操作方法：用其左子树或者右子树替换它(结点替换)，也即其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树“。

第三种情况：被删除的结点既有左子树，也有右子树。

操作方法：可以以其中序前趋值替换之(值替换)，然后再删除该前趋结点。前趋是左子树中最大的结点。也可以用其后继替换之，然后再删除该后继结点，后继是右子树中最小的结点。

Ⅱ 平衡二叉树AVL

问题：如何提高形态不均衡的二又排序树的查找效率？

解决办法：做“平衡化”处理，即尽量让二又树的形态均衡！$\Longrightarrow$ 平衡二叉树。

(1) 定义

平衡二叉树(balanced binary tree)又称AVL树(Adelson-Velskii and Landis)。

一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：① 左子树与右子树的高度之差的绝对值小于等于1；② 左子树和右子树也是平衡二叉排序树。

为了方便起见，给每个结点附加一个数字，给出该结点左子树一右子树的高度差。这个数字称为结点的平衡因子BF)：

$$平衡因子\text{BF} = 结点左子树的高度-结点右子树的高度$$

根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是：$0$、$1$或$-1$。

对于一棵有$n$个结点的AVL树，其高度保持在$O(\log_2 n)$量级，ASL也保持在$O(\log_2 n)$数量级。

(2) 失衡二叉树的平衡调整

调整原则：1) 降低高度； 2）保持二叉排序树性质。

• LL型调整

• RR型调整

这里就不贴全图了，RR型的思想本质和LL一样，只是位置正好相反而已。

① B结点带右子树β一起上升；② A结点成为B的左孩子；③ 原来B结点的左子树α作为A的右子树。

• LR型调整

• RL型调整

这里就不贴全图了，RL型的思想本质和LR一样，只是位置正好相反而已。

7.4 哈希表/散列表

Ⅰ 散列表的概念

(1) 基本概念

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

对应关系——hash函数H(·)。

$$Loc(i)=H(key_i)$$

例如，构造下图所示的hash函数，其映射关系为：学号后两位 → 索引地址。

优点：查找效率高；缺点：空间效率低。

(2) 相关术语

散列方法(杂凑法)：选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放，查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。

散列函数(杂凑函数)：散列方法中使用的转换函数——hash函数H(·)。

散列表(杂凑表)：按上述思想构造的表。

冲突：不同的关键码映射到同一个散列地址，即$key_1 \neq key_2$，但是$H(key_1)=H(key_2)$。

同义词：具有相同函数值的多个关键字。

(3) 注意事项

使用散列表要解决好两个问题：

1) 构造好的散列函数$H(·)$：(a) 所选函数尽可能简单，以便提高转换速度；(b) 所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，以减少空间浪费。
2) 制定一个好的解决冲突的方案：查找时，如果从散列函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

Ⅱ 散列函数的构造方法

(1) 构造散列函数考虑的因素

① 执行速度(即计算散列函数所需时间)；
② 关键字的长度；
③ 散列表的大小；
④ 关键字的分布情况；
⑤ 查找频率。

• 根据元素集合的特性构造
  • 要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。
  • 要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。
• 常用的方法：1.直接定址法；2.数字分析法；3.平方取中法；4.折叠法；5.除留余数法；6.随机数法。

(2) 直接定址法

$$H(key) = a*key+b（a、b为常数）$$

优点：以关键码key的某个线性函数值为散列地址，不会产生冲突。

缺点：要占用连续地址空间，空间效率低。

(3) 除留余数法

$$H(key) = key ~\text{ mod } ~ p（p是整数）$$

$p$选取的一个技巧：设表长为$m$，取 $p≤m$ 且为质数。

Ⅲ 处理冲突的方法

• 常见的方法
  • 开放定址法(开地址法)
  • 链地址法(拉链法)
  • 再散列法(双散列函数法)
  • 建立一个公共溢出区

(1) 开放定址法

基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。

• 线性探测法

$$H_i = [H(key) + d_i ] ~ \text{ mod }~ m$$

其中，$m$为散列表长度，$d_i$为线性增量序列。该方法一旦冲突，就找下一个地址，直到找到空地址存入。

• 二次探测法

$$H_i = [H(key) + d_i ] ~ \text{ mod }~ m$$

其中，$m$为散列表长度，m要求是某个$4k+3$的质数，$d_i = 1^2, -1^2, 2^2, -2^2, \cdots, q^2, -q^2$。

(2) 链地址法(拉链法)

基本思想：相同散列地址的记录链成一单链表。

m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

• 链地址法建立散列表步骤
  • Step1：取数据元素的关键字key，计算其散列函数值(地址)。若该地址对应的链表为空，则将该元素插入此链表；否则执行Step2解决冲突。
  • Step2：根据选择的冲突处理方法，计算关键字key的下一一个存储地址。若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表。

Ⅳ 散列表的查找

• 几点结论
  • 散列表技术具有很好的平均性能，优于一些传统的技术；
  • 链地址法优于开地址法；
  • 除留余数法作散列函数优于其它类型函数。

§ 8 排序操作

Ⅰ 排序算法的基本介绍

排序：将一组杂乱无章的数据按一定规律顺次排列起来。即，将无序序列排成一个有序序列(由小到大或由大到小)的运算。

如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言。

• 排序方法的分类

  • 按数据存储介质：内部排序和外部排序
  • 按比较器个数：串行排序和并行排序
  • 按主要操作：比较排序和基数排序
  • 按辅助空间：原地排序和非原地排序
  • 按稳定性：稳定排序和非稳定排序
  • 按自然性：自然排序和非自然排序

  (1) 按存储介质

内部排序：数据量不大、数据在内存，无需内外存交换数据；

外部排序：数据量较大、数据在外存(文件排序)。

外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。

(2) 按比较器个数

串行排序：单处理机(同一时刻比较一对元素)；

并行排序：多处理机(同一时刻比较多对元素)。

(3) 按主要操作

比较排序：用比较的方法，例如：插入排序、交换排序、选择排序、归并排序；

基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置。

(4) 按辅助空间

原地排序：辅助空间用量为$O(1)$的排序方法。(所占的辅助存储空间与参加排序的数据量大小无关)

非原地排序：辅助空间用量超过$O(1)$的排序方法。

(5) 按稳定性

稳定排序：能够使任何数值相等的元素，排序以后相对次序不变；

非稳定性排序：不是稳定排序的方法。

排序的稳定性只对结构类型数据排序有意义。例如下面这种情况：

n个学生信息(学号、姓名、语文、数学、英语、总分)

1、按数学成绩从高到低排序
2、按照总分从高到低排序,
3、总分相同的情况下，数学成绩高的排在前面

(6) 按自然性

自然排序：输入数据越有序，排序的速度越快的排序方法。

非自然排序：不是自然排序的方法。

• 顺序表存储结构

#define MAXSIZE 20	// 设记录不超过20个
typedef int KeyType;	// 设关键字为整型量(int型)

// 定义每个记录(数据元素)的结构======================================
typedef struct 
{
    KeyType key ;	// 关键字
    InfoTypeother info;	// 其它数据项
}RedType;	//Record Type

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

Ⅱ 插入排序概述

【基本思想】每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

即边插入边排序，保证子序列中随时都是排好序的。

【基本操作】有序插入

在有序序列中插入一个元素，保持序列有序，有序长度不断增加。

1. 起初，a[0]是长度为1的子序列。然后，逐一将a[1]至a[n-1]插入到有序子序列中。
2. 在插入a[i]前，数组a的前半段(a[0]—a[i-1])是有序段，后半段(a[i]—a[n-1])是停留于输入次序的“无序段”；
3. 插入a[i]使a[0]—a[i-1]有序，也就是要为a[i]找到有序位置$j(0≤j≤i)$，将a[i]插入在a[j]的位置上。

【插入排序的分类】

Ⅲ 插入排序——直接插入排序

直接插入排序——采用顺序查找法查找插入位置。

// 直接插入排序为减少一次比较，采用了“哨兵”，存在开头
void InsertSort( SqList& L )
{
    int i, j;
    for ( i=2; i<=L.length; ++i)
    {
        if (L.r[i].key < L.r[i-1].key)	// 若"<",需将L.r[i]插入有序子表
        { 
            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];	// 记录后移
            }
            L.r[j+1]=L.r[0];	// 插入到正确位置
        }
    }
}

【时间复杂度结论】

1. 原始数据越接近有序，排序速度越快
   a. 最坏情况下(输入数据是逆有序的)：$Tw(n)=O(n^2)$
   b. 平均情况下，耗时差不多是最坏情况的一半：$Te(n)=O(n^2)$
2. 要提高查找速度：① 减少元素的比较次数；② 减少元素的移动次数。

Ⅳ 插入排序——折半插入排序

其本质思想来自：第7章节的折半查找。

void BInsertSort(SqList& L)
{
    for( int i=2; i<=L.length; ++i)	// 依次插入第2~第n个元素
    { 
        L.r[0]= L.r[i];	// 当前插入元素存到“哨兵”位置
        int low=1;
        int high=i-1;	// 采用二分查找法查找插入位置
        while ( low <= high )
        {
            mid = (low + high)/2;
            if( L.r[0].key < L.r[mid].key )
                high = mid - 1;
            else 
                low = mid + 1;
        } //循环结束，high+1则为插入位置
        for (int j=i-1; j>=high+1; --j)
            L.r[j+1] = L.r[j];	// 移动元素
        L.r[high+1] = L.r[0];	// 插入到正确位置
} // BInsertSort

【复杂度简要结论】

1. 折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的们排列；
2. 减少了比较次数，但没有减少移动次数；
3. 平均性能优于直接插入排序。

Ⅴ 插入排序——希尔排序

【基本思想】

先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

【希尔排序思路】

1. 定义增量序列$D_k$：$D_M>D_{M-1}>…>D_1=1$；
   刚才的例子中：$D_3=5，D_2=3，D_1=1$
2. 对每个$D_k$进行“Dκ-间隔”插入排序($k=M, M-1, …, 1$)。

【希尔排序特点】

1. 一次移动，移动位置较大，跳跃式地接近排序后的最终位置；
2. 最后一次只需要少量移动；
3. 增量序列必须是递减的，最后一个必须是1；
4. 增量序列应该是互质的。

// 对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子
void ShellInsert(SqList& L, int dk)
{
    for(int i=dk+1; i<=L.length; ++i)
    {
        if(L.r[i].key < L.r[i-dk].key) 
        {
            L.r[0]=L.r[i];
            for(int j=i-dk; j>0 &&(L.r[0].key<L.r[j].key); j=j-dk)
                L.r[j+dk]=L.r[j];
            L.r[j+dk]=L.r[0];
        }
    }
}


void ShellSort(Sqlist& L, int dltal[], int t)
{
    // 按增量序列dlta[0...t-1]对顺序表L作希尔排序
    for(int k=0; k<t; ++k)
        ShellInsert(L，dlta[k]);	// 一趟增量为dlta[k]的插入排序
}

【希尔排序算法分析】

1. 希尔排序算法效率与增量序列的取值有关
   1. 一种常用的增量序列：Hibbard增量序列：$D_k=2^{k-1}$—相邻元素互质，其最坏情况：$T_{worst}=O(n^{3/2})$，猜想平均情况：$T_{avg}=O(n^{5/4})$。
   2. 另一种常用增量序列：Sedgewick增量序列。
2. 希尔排序法是一种不稳定的排序算法。
3. 空间复杂度：$O(1)$。
4. 不宜在链式存储结构上实现。

Ⅵ 交换排序——冒泡排序

【基本思想】两两比较，如果发生逆序则交换，直到所有记录都排好序为止。

【冒泡排序基本思想】基于简单交换思想，每趟不断将记录两两比较，并按“前小后大”规则交换。

// 冒泡排序算法
void bubble_sort(SqList& L)
{
    int m, j;
    int n = L.length;
    RedType x;	// 交换时临时存储
    for(m=1; m<=n-1; m++)	// 总共需m趟
    {
        for(j=1; j<=n-m; j++)
            if(L.r[j].key>L.r[j+1].key)	// 发生逆序
            {
                x=L.r[j]; 
                L.r[j]=L.r[j+1];
                L.r[j+1]=x; //交换
            } //endif
    } //for
}

Ⅶ 交换排序——快速排序

• 【基本思想】：递归思想
  • 任取一个元素 (如：第一个)为中心；
  • 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；
  • 对各子表重新选择中心元素并依此规则调整；
  • 直到每个子表的元素只剩一个。

• 【快速排序的特点】
  • ① 每一趟的子表的形成是采用从两头向中间交替式逼近法，
  • ② 由于每趟中对各子表的操作都相似，可采用递归算法。

int Partition ( SqList& L, int low, int high )
{
    L.r[0]= L.r[low];
    pivotkey = L.r[low].key;
    while (low < high )
    {
        while ( low < high && L.r[high].key >= pivotkey)
            --high;
        L.r[low] = L.r[high];
        while ( low < high && L.r[low].key <= pivotkey )
            ++low;
        L.r[high]= L.r[low];
    }
    L.r[low]=L.r[0];
    return low;
}

// 对顺序表L快速排序
void QSort(SqList& L, int low, int high)
{ 
    if (low < high)	// 长度大于1
    { 
        pivotloc = Partition(L, low, high);	// 将L.r[low, high]一分为二，pivotloc为枢轴元素排好序的位置
        QSort(L, low, pivotloc-1);	// 对低子表递归排序
        QSort(L, pivotloc+1, high);	// 对高子表递归排序
    }
} // QSort
    
void main()
{
    Qsort(L, 1, L.length);
}

【快速排序复杂度分析】

时间复杂度：可以证明，平均计算时间是$O(n \log_2 n)$。

实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序分法中最好的一个。

空间复杂度：快速排序不是原地排序
由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。(即使不用递归，也需要用用户栈)。在平均情况下：需要$O(\log n)$的栈空间；最坏情况下：栈空间可达$O(n)$。

稳定性：快速排序是一种不稳定的排序方法。

自然性：输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法。

Ⅷ 选择排序——简单选择排序

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

• 【基本操作】
  • 首先，通过$n-1$次关键字比较，从$n$个记录中找出关键字最小的记录，将它与第1个记录交换；
  • 其次，通过$n-2$次比较，从剩余的$n-1$个记录中找出关键字次小的记录，将它与第2个记录交换；
  • 重复上述操作，共进行$n-1$趟排序后，排序结束。

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

【简单选择排序复杂度分析】

时间复杂度：

1. 记录移动次数
   最好情况为0，最坏情况为$3(n-1)$
2. 比较次数
   无论待排序列处于什么状态，选择排序所需进行的”比较”次数都相同
3. 算法稳定性
   简单选择排序是不稳定排序，但是可以稳定化。

Ⅸ 选择排序——堆排序

(1) 堆的定义

若$n$个元素的序列$(a_1, a_2, \cdots, a_n)$满足：

$$\begin{cases} a_i \leq a_{2i} \\ a_i \leq a_{2i+1} \end{cases} \quad \text{OR} \quad \begin{cases} a_i \geq a_{2i} \\ a_i \geq a_{2i+1} \end{cases}$$

则称该序列为小根堆$\text{ OR }$大根堆。

从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于(大于)它的孩子结点。

(2) 堆排序

若在输出堆顶的最小值(最大值)后，使得剩余$n-1$个元素的序列重又建成一个堆，则得到$n$个元素的次小值(次大值)…如此反复，便能得到一个有序序列，这个过程称之为堆排序。

实现堆排序需解决两个问题：1、如何由一个无序序列建成一个堆；2、如何在输出堆顶元素后，调整剩余元素为一个新的堆?

(3) 问题2：如何在输出堆顶元素后，调整剩余元素为一个新的堆?

• 对于小根堆：
  • 1. 输出堆顶元素之后，以堆中最后一个元素替代之；
    2. 然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；
    3. 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。
• 对于大根堆：与小根堆相反。

【筛选过程】

/*
已知R[s..m]中记录的关键字除R[S]之外均满足堆的定义，
本函数调整R[S]的关键字，使R[s..m]成为一个大根堆
*/
void HeapAdjust (elem R[], int s, int m)
{
    rc = R[s];
    for(int 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];	// rc应插入在位置s上
        s = j;
    }//for
    R[s]= rc;	// 插入
}// HeapAdjust

(4) 问题1：如何由一个无序序列建成一个堆？

显然：单结点的二叉树是堆；在完全二叉树中所有以叶子结点(序号i>n/2)为根的子树是堆。

这样，我们只需依次将以序号为$n/2, n/2-1, …, 1$的结点为根的子树均调整为堆即可。即：对应由$n$个元素组成的无序序列，“筛选”只需从第$n/2$个元素开始。

由于堆实质上是一个线形表，那么我们可以顺序存储一个堆。

下面以一个实例介绍建一个小根堆的过程。例：有关键字为49，38，65，97，76，13，27，49的一组记录，将其按关键字调整为一个小根堆。

由以上分析知：

若对一个无序序列建堆，然后输出根；重复该过程就可以由一个无需序列输出有序序列。
实质上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。

【堆排序算法如下】

// 对R[1]到R[n]进行堆排序
void HeapSort(elem R[])
{
    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]重新建堆
    }
}
//HeapSort

【堆排序算法复杂度】

Ⅹ 归并排序

【基本思想】将两个或两个以上的有序子序列，“归并/合并”为一个有序序列。

在内部排序中，通常采用的是2-路归并排序，即：将两个位置相邻的有序子序列$R[1 \sim m]$和$R[m+1 \sim n]$归并为一个有序序列$R[1 \sim n]$。

关键问题：如何将两个有序序列合成一个有序序列?

这个问题其实在第2章线性表的时候已经学过了，过程可用下图示例。

Ⅺ 基数(桶/箱)排序

【基本思想】分配+收集

也叫桶排序或箱排序：设置若干个箱子，将关键字为$k$的记录放入第$k$个箱然后在按序号将非空的连接。

【前提条件】数字是有范围的

均由0-9这十个数字组成，则只需设置十个箱子，相继按个、十、百….进行排序。

一副扑克牌，有4种花色，每种花色有13张牌，利用桶排序可以：Step 1先准备4个桶，将牌分成4种花色；Step 2再准备13个桶，将13张牌排序。也即：桶排序适合多关键字排序。

• 各种排序方法比较

补充1（不系统）：动态规划

首先我们来看一个经典的动态规划问题：

给你一个无序的数组nums = [1，5，2，4，3]，要求我们找出其中最长的递增的子序列（比如这里的 1,2,4 就是其中的一个，1,2,3 是另外一个答案）。这里我们再对这个问题做一些简化，我们要求这个算法只返回最长序列的“长度”就好了（也即3）

解决这道题，最容易想到的办法是暴力枚举/或者叫暴力搜索