数据结构(C语言)笔记

绪论

>笔记部分

一、 数据结构的定义

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

二、 基本概念和数据：

1. 数据

数据（ data ） 是对客观事物的符号表示， 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称， 它是计算机程序加工的 “ 原料 ” 。

2 ． 数据元素

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

3 ． 数据对象

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

4 ． 数据结构

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

（ 1 ） 数据结构的基本结构

根据数据元素之间关系的不同特性， 通常有下列四类基本结构：

①集合。 数据元素之间除了 “ 同属于一个集合 ” 的关系外， 别无其它关系。

②线性结构。 数据元素之间存在一个对一个的关系。

③树形结构。 数据元素之间存在一个对多个的关系。

④图状结构或网状结构。 数据元素之间存在多个对多个的关系。

（ 2 ） 数据结构的形式定义

数据结构的形式定义为： 数据结构是一个二元组 Data_Structure== （ D ， S ）

其中： D 表示数据元素的有限集， S 表示 D 上关系的有限集。

（ 3 ） 数据结构在计算机中的表示

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

①元素的表示。 计算机数据元素用一个由若干位组合起来形成的一个位串表示。

②关系的表示。 计算机中数据元素之间的关系有两种不同的表示方法： 顺序映象和非顺序映象。 并由这两种不同的表示方法得到两种不同的存储

结构： 顺序存储结构和链式存储结构。

• 顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
• 非顺序映象的特点是借助指示元素存储地址的指针（ pointer ） 表示数据元素之间的逻辑关系。

5 ． 数据类型

数据类型（ Data type ） 是一个值的集合和定义在这个值集上的一组操作的总称。 按 “ 值 ” 的不同特性， 高级程序语言中的数据类型可分为两类：

• 一类是非结构的原子类型， 值是不可分解的；
• 另一类是结构类型， 值是由若干成分按某种结构组成的， 可以分解， 并且它的成分可以是非结构的， 也可以是结构的。

6 ． 抽象数据类型

抽象数据类型（ Abstract Data Type 简称 ADT ） 由一个值域和定义在该值域上的一组操作组成。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 “ 抽象 ” 的意义在于数据类型的数学抽象特性。

若按其值的不同特性， 抽象数据类型可细分为下列三种型： 原子类型， 固定聚合类型和可变聚合类型。

7 ． 多形数据类型

多形数据类型（ polymorphic data type ） 是指其值的成分不确定的数据类型。

三、 抽象数据类型的表示和实现

抽象数据类型可通过固有数据类型来表示和实现， 即利用处理器中已存在的数据类型来说明新的结构， 用已经实现的操作来组合新的操作。

1 ． 抽象数据类型的 C 语言描述 （ 1 ） 预定义常量和类型

#define TRUE 1
#define FALSE 0
#define OK
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

（ 2 ） 数据结构的表示和数据元素类型

typedef // 数据结构的表示（存储结构） 用类型定义（ typedef ） 描述
ElemType // 数据元素类型约定为 ElemType

（ 3 ） 算法的函数描述

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

（ 4 ） 赋值语句

简单赋值 变量名 = 表达式；
串联赋值 变量名 1= 变量名 2=…= 变量名 k= 表达式；
成组赋值 （变量名 1 ， 变量名 2 ， … ， 变量名 k ） = （表达式 1 ， 表达式 2 ， … ， 表达式 k ）；
结构名 = 结构名
结构名 = （值 1 ， … ， 值 k ） ；
变量名 []= 表达式；
变量名 [ 起始下标 .. 终止下标 ]= 变量名 [ 起始下标 .. 终止下标 ] ；
交换赋值 变量名 变量名
条件赋值 变量名 = 
条件表达式 ？表达式 T ： 表达式 F ；

（ 5 ） 选择语句

条件语句 1 if （表达式） 语句；

条件语句 2 if （表达式） 语句；
else 语句；

开关语句 1 switch （表达式） {
case 值 1 ： 语句序列 1 ； break ；
…
case 值 n ： 语句序列 n ； break ；
default ： 语句序列 n+1 ；
}

开关语句 2 switch{
case 条件 1 ： 语句序列 1 ； break ；
…
case 条件 n ： 语句序列 n ； break ；
default ：
语句序列 n+1 ；
}

（ 6 ） 循环语句

for 语句 for （赋初值表达式序列； 条件； 修改表达式序列）语句；
while 语句 while （条件） 语句；
do-while 语句 do{
语句序列；
}while （语句） ；

（ 7 ） 结束语句

函数结束语句 return 表达式；
return ；
case 结束语句 break ；
异常结束语句 exit （异常代码） ；

（ 8 ） 输入和输出语句

输入语句 scanf （ [ 格式串 ] ， 变量 1 ， … ， 变量 n ） ；
输出语句 printf （ [ 格式串 ] ， 表达式 1 ， … ， 表达式 n ） ；

（ 9 ） 基本函数

求最大值 max （表达式 1 ， … ， 表达式 n ）
求最小值 min （表达式 1 ， … ， 表达式 n ）
求绝对值 abs （表达式）
求不足整数值 floor （表达式）
求进位整数值 ceil （表达式）
判定文件结束 eof （文件变量）或 eof
判定行结束 eoln （文件变量）或 eoln

（ 10 ） 逻辑运算

与运算 && ： 对于 A&&B ， 当 A 的值为 0 时， 不在对 B 求值。
或运算 || ： 对于 A||B ， 当 A 的值为非 0 时， 不在对 B 求值。

四、 算法和算法分析

（ 1 ） 算法的定义

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

（ 2 ） 算法的 5 个重要特性

①有穷性；

②确定性；

③可行性；

④输入；

⑤输出。

2 ． 算法设计的要求

（ 1 ） 正确性（ correctness ）

正确性是指设计或选择的算法应当能正确地反映某种需求， 否则， 算法正确与否的衡量准则就不存在了。 “ 正确 ” 一词的含义大体可分为以下四个

层次：

①程序不含语法错误。

②程序对于几组输入数据能够得出满足规格说明要求的结果。

③程序对于精心选择的、 典型、 苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。

④程序对于一切合法的输入数据都能产生满足规格说明要求的结果。

（ 2 ） 可读性（ readability ）

可读性算法首先是方便人的阅读与交流， 其次才是机器执行。 可读性好有助于人对算法的理解， 因为晦涩难懂的程序易于隐藏较多错误从而难以调试和修改。

（ 3 ） 健壮性（ robustness ）

健壮性是指当输入数据非法时， 算法也能适当地作出反应或进行处理， 而不会产生莫明其妙的输出结果。

（ 4 ） 效率与低存储量需求

效率指的是算法执行时间。 对于同一个问题如果有多个算法可以解决， 执行时间短的算法效率高； 存储量需求指算法执行过程中所需要的最大存储空间， 这两者都与问题的规模有关。

3 ． 算法效率的度量

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量， 度量一个程序的执行时间通常有两种方法：

（ 1 ） 事后统计

很多计算机内部都有计时功能， 有的甚至可精确到毫秒级， 因此采用不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。

但这种方法有两个缺陷： 一是必须先运行依据算法编制的程序； 二是所得时间的统计量依赖于计算机的硬件、 软件等环境因素， 有时容易掩盖算法本身的优劣。

（ 2 ） 事前分析估算

①消耗时间的因素

一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

a ． 程序依据的算法选用的策略。

b ． 问题的规模。

c ． 书写程序的语言。

d ． 编译程序所产生的机器代码的质量。

e ． 机器执行指令的速度。

显然， 同一个算法用不同的语言实现， 或者用不同的编译程序进行编译， 或者在不同的计算机上运行时， 效率均不相同， 这表明使用绝对的时间

单位衡量算法的效率是不合适的。

②时间复杂度

为了便于比较同一问题的不同算法的执行时间， 通常的做法是从算法中选取一种对于所研究的问题（或算法类型） 来说是基本运算的原操作， 以该基本操作重复执行的次数作为算法的时间量度。 一般情况下， 算法中基本操作重复执行的次数是问题规模 n 的某个函数 f （ n ） ， 算法的时间量度记作

T （ n ） —O （ f （ n ） ）

它表示随问题规模 n 的增大算法执行时间的增长率和 f （ n ） 的增长率相同， 称作算法的渐近时间复杂度（ asymptotic time complexity ） ， 简称时间复杂度。 由于算法的时间复杂度考虑的只是对于问题规模 n 的增长率， 因此在难以精确计算基本操作执行次数（或语句频度） 的情况下， 只需求出它关于n 的增长率或阶即可。

4 ． 算法的存储空间需求

类似于算法的时间复杂度， 以空间复杂度（ space complexity ） 作为算法所需存储空间的量度， 记作

S （ n ） =O （ f （ n ） ）

其中 n 为问题的规模。

线性表

笔记部分

一、 线性表的类型定义

1 线性表的定义

线性表（ linear_list ） 是最常用且最简单的一种数据结构。 一个线性表是 n 个数据元素的有限序列。 在稍复杂的线性表中， 一个数据元素可以由若干个数据项（ item ） 组成。 在这种情况下， 常把数据元素称为记录（ record ） ， 含有大量记录的线性表又称文件（ file ） 。

2 ． 抽象数据类型线性表的定义

ADT List{

数据对象：

数据关系：

基本操作：

InitList （ &L ）

操作结果： 构造一个空的线性表 L 。

DestroyList （ &L ）

初始条件： 线性表 L 已存在。

操作结果： 销毁线性表 L 。

ClearList （ &L ）

初始条件： 线性表 L 已存在。

操作结果： 将 L 重置为空表。

ListEmpty （ L ）

初始条件： 线性表 L 已存在

操作结果： 若 L 为空表， 则返回 TRUE ， 否则返回 FALSE 。

ListLength （ L ）

初始条件： 线性表 L 已存在。

操作结果： 返回 L 中数据元素的个数。

GetElem （ L ， i ， &e ）

初始条件： 线性表 L 已存在， 1≤i≤ListLength （ L ） 。

操作结果： 用 e 返回 L 中的第 i 个数据元素的值。

LocateElem （ L ， e ， compare （） ）

初始条件： 线性表 L 已存在， compare （） 是数据元素判定函数。

操作结果： 返回 L 中第 1 个与 e 满足关系 compare （） 的数据元素的位序。 若这样的数据元素不存在， 则返回值为 0 。

PriorElem （ L ， cur_e ， &pre_e ）

初始条件： 线性表 L 已存在

操作结果： 若 cur_e 是 L 的数据元素， 且不是第一个， 则用 pre_e 返回它的前驱， 否则操纵结果失败， next_e 无定义。

NextElem （ L ， cur_e ， &next_e ）

初始条件： 线性表 L 已存在

操作结果： 若 cur_e 是 L 的数据元素， 且不是最后一个， 则用 next_e 返回它的后继， 否则操作失败， next_e 无定义。

ListInsert （ &L ， i ， e ）

初始条件： 线性表 L 已存在， 1≤i≤ListLength （ L ） +1 。

操作结果： 在 L 中第 i 个位置之前插入新的数据元素 e ， L 的长度加 1.

ListDelete （ &L ， i ， &e ）

初始条件： 线性表 L 已存在且非空， 1≤i≤ListLength （ L ） 。

操作结果： 删除 L 的第 i 个数据元素， 并用 e 返回其值， L 的长度减 1 。

ListTraverse （ L ， visit （） ）

初始条件： 线性表 L 已存在。

操作结果： 依次对 L 的每个数据元素调用函数 visit （） 。 一旦 visit （） 失败， 则操作失败。

}ADT list

二、 线性表的顺序表示和实现

1 顺序存储的特点方法

（ 1 ） 顺序存储中， 逻辑关系上相邻的两个元素在物理位置上也相邻， 因此对表中相邻的元素 和 赋以相邻的存储位置 LOC （ ） 和 LOC （） . 所以只要确定了存储线性表的起始位置， 线性表中任一数据元素都可随机存取， 所以线性表的顺序存储结构是一种随机存取的存储结构；

（ 2 ） 线性表的顺序存储结构是一个记录型 的结构。 数据元素的存储位置可用数组的下标值（即相对于线性表的起始位置的值） 来表示；

（ 3 ） 在顺序存储结构中， 线性表的某些操作容易实现， 如求表长的操作， 线性表的长度即为 last 域的值。

3 ． 线性存储的缺点

（ 1 ） 在做插入或删除操作时， 需移动大量元素；

（ 2 ） 在给长度变化较大的线性表预先分配空间时， 必须按最大空间分配， 使存储空间不能得到充分利用， 造成了空间的浪费；

（ 3 ） 表的容量难以扩充。

三、 线性表的链式表示和实现

链式存储结构， 由于它不要求逻辑上相邻的元素在物理位置上也相邻， 因此它没有顺序存储结构所具有的缺点。

1 ． 定义

为了表示每个数据元素 a i 与其直接后继元素 a i+1 之间的逻辑关系， 对数据元素 a i 来说， 除了存储其本身的信息之外， 还需存储一个指示其直接后继元素的信息（即直接后继元素的存储位置） ， 这两部分信息组成数据元素 a i 的存储映象， 称为结点（ Node ） 。 它包括两个域： 数据域和指针域， 其中，数据域存储该数据元素信息； 指针域存储直接后继元素的存储位置。 指针域中存储的信息称做指针或链， n 个结点（ a i （ 1≤i≤n ） 的存储映象） 链结成一个链表， 即为线性表（ a 1 ， a 2 ， … ， a n ） 的链式存储结构， 又由于此链表的每个结点中只包含一个指针域， 又称线性链表或单链表。

2 ． 线性链表特点

（ 1 ） 它不要求逻辑上相邻的元素在物理位置上也相邻， 因此可以用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的， 也可以是不连续的） ；

（ 2 ） 用线性链表表示线性表时， 数据元素之间的逻辑关系是由结点中的指针指示的；

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

通常把链表画成用箭头相链接的结点的序列， 结点之间的箭头表示链域中的指针。 因为在使用链表时， 关心的只是它所表示的线性表中数据元素之间的逻辑顺序， 而不是每个数据元素在存储器中的实际存储的物理位置，

3 ． 线性链表的操作

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

4 ． 静态链表

（ 1 ） 这种存储结构需要预先分配一个较大的空间， 但在做线性表的插入和删除操作时不需移动元素， 仅需修改指针， 故仍具有链式存储结构的主要优点。

（ 2 ） 实现静态链表的插入和删除操作。 首先将所有未被使用过以及被删除的分量用游标链成一个备用的链表， 每当进行插入时便可从备用链表上取得第一个结点作为待插入的新结点； 反之， 在删除时将从链表中删除下来的结点链接到备用链表上。

5 ． 循环链表

循环链表（ circular linked list ） 是另一种形式的链式存储结构。 它的特点是表中最后一个结点的指针域指向头结点， 整个链表形成一个环。 由此，从表中任一结点出发均可找到表中其它结点。

6 ． 双向链表

在单链表中， NextElem 的执行时间为 O （ 1 ） ， 而 PriorElem 的执行时间为为 O （ n ） ， 为克服单链表这种单向性的缺点， 可利用双向链表（ double

linked list ） 。

顾名思义， 在双向链表的结点中有两个指针域， 一个指向直接后继， 另一个指向直接前驱。

双向链表也可以有循环链表， 如图 2-6 （ c ） 所示， 链表中存有两个环， 图 2-6 （ b ） 所示为只有一个表头结点的空表。

在双向链表中， 有些操作如： ListLength 、 GetElem 、 LocateElem 等仅需涉及一个方向的指针， 则它们的算法描述和线性链表的操作相同， 但在插

入、 删除时有很大的不同， 在双向链表中需同时修改两个方向上的指针， 图 2-7 和图 2-8 分别显示了删除和插入结点时指针修改的情况。

四、 一元多项式的表示及相加

1 一元多项式的表示

（ 1 ） 一元多项式 P x （ x ） 按升幂表示

P n （ x ） =p 0 +p 1 x+p 2 x 2 +…+p n X n

（ 2 ） 用线性表 P 表示

P= （ p 0 ， p 1 ， p 2 ， … ， p n ）

2 ． 一元多项式的相加

已知 Q m （ x ） 是一元 m 次多项式， 同样可用线性表 Q 来表示：

Q= （ q 0 ， q 1 ， q 2 ， … ， q m ）

不失一般性， 设 m<n ， 则两个多项式相加的结果 R n （ x ） =P n （ x ） +R n （ x ）

可用线性表 R 表示：

R= （ p 0 +q 0 ， p 1 +q 1 ， p 2 +q 2 ， … ， p m +q m ， p m+1 ， … ， p n ）

栈和队列

笔记部分（栈）

一、抽象数据类型栈的定义

栈（ Stack ） 是被限定仅在表尾进行插入或删除操作的线性表。 表尾端称为栈顶（ top ） ， 表头端称为栈底（ bottom ） 不含元素的空表称为空栈。 栈的修改是按后进先出的原则进行的， 因此， 栈又称为后进先出（ Last In First Out ） 的线性表（简称 LIFO 结构） 。

（ 2 ） 栈的抽象数据类型定义

ADT Stack{

数据对象：

数据关系：

约定 a n 端为栈顶， a 1 端为栈底。

基本操作：

InitStack （ &S ）

操作结果： 构造一个空栈 S 。

DestroyStack （ &S ）

初始条件： 栈 S 已存在。

操作结果： 栈 S 被销毁。

ClearStack （ &S ）

初始条件： 栈 S 已存在。

操作结果： 将 S 清为空栈。

StackEmpty （ S ）

初始条件： 栈 S 已存在。

操作结果： 若栈 S 为空栈， 则返回 TRUE ， 否则返回 FALSE 。

StackLength （ S ）

初始条件： 栈 S 已存在。

操作结果： 返回 S 的元素个数， 即栈的长度。

GetTop （ S ， &e ）

初始条件： 栈 S 已存在且非空。

操作结果： 用 e 返回 S 的栈顶元素。

Push （ &S ， e ）

初始条件： 栈 S 已存在。

操作结果： 插入元素 e 为新的栈顶元素。

Pop （ &S ， &e ）

初始条件： 栈 S 已存在且非空。

操作结果： 删除 S 的栈顶元素， 并用 e 返回其值。

StackTraverse （ S ， visit （） ）

初始条件： 栈 S 已存在且非空。

操作结果： 从栈底到栈顶依次对 S 的每个数据元素调用 visit （） 。 一旦 visit （） 失败， 则操作失败。

}ADT Stack

2 栈的表示和实现

（ 1 ） 顺序栈

顺序栈即栈的顺序存储结构， 是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素， 同时设指针 top 指示栈顶元素的当前位置。 通常的习惯做法是以 top=0 表示空栈， 鉴于 C 语言中数组的下标约定从 0 开始， 则以 C 作描述语言时， 如此设定会带来很大不便； 另一方面， 由于栈在使用过程中所需最大空间的大小难以估计， 因此， 一般来说， 在初始化设空栈时不应限定栈的最大容量。 一个合理的做法是： 先为栈分配一个基本容量， 然后在使用过程中， 当栈的空间不够使用时再逐步扩大。

栈的初始化操作为： 按设定的初始分配量进行一次存储分配， base 可称为栈底指针， 在顺序栈中， 它始终指向栈底的位置， 若 base 的值为 NULL ，则称栈结构不存在。 称 top 为栈顶指针， 其初值指向栈底， 即 top=base 可作为栈空的标记， 每当插入新的栈顶元素时， 指针 top 增 1 ； 删除栈顶元素时， 指针 top 减 1 ， 因此， 非空栈的栈顶指针始终在栈顶元素的下一个位置上。

（ 2 ） 链栈

由于栈的操作是线性表操作的特例， 则链栈的操作易于实现。

二、 栈的应用举例

1 数制转换

十进制 N 和其他 d 进制数的转换是计算机实现计算的基本问题， 其解决方法很多， 其中一个简单算法基于下列原理：

N= （ N div d ） ×d+N mod d （其中： div 为整除计算， mod 为求余计算）

实现对于输入的任意一个非负十进制整数， 打印输出与其等值的八进制数代码如下：

void conversion （） {

// 对于输入的任意一个非负十进制整数， 打印输出与其等值的八进制数

InitStack （） ；

scanf （ “%d” ， N ） ；

while （ N ） {

Push （ S ， N%8 ） ；

N=N%8 ；

}

while （！ StackEmpty （ S ） ） {

Pop （ S ， e ） ；

printf （ “%d” ， e ） ；

}

2 ． 括号匹配的检验

假设表达式中允许包括两种括号： 圆括号和方括号， 其嵌套的顺序随意， 即（ [] （） ） 或 [ （ [][] ） ] 等为正确的格式， [ （ ] ） 或（ [ （） ] 或（（） ] ）

均为不正确的格式。 检验括号是否匹配的方法可用 “ 期待的急迫程度 ” 这个概念来描述。

3 ． 表达式求值

（ 1 ） 算符优先法

算符优先法是根据算术四则运算优先关系的规定来实现对表达式的编译或解释执行的。

（ 2 ） 算符间的优先关系。

将运算符和界限符统称为算符， 它们构成的集合命名为 0P 。

（ 3 ） 算法的实现

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

想是：

①首先置操作数栈为空栈， 表达式起始符 “#” 为运算符栈的栈底元素。

②依次读入表达式中每个字符， 该字符若是操作数则进 0PND 栈， 若是运算符， 则和 0PTR 栈的栈顶运算符比较优先权后作相应操作， 直至整个表达式求值完毕（即 OPTR 栈的栈顶元素和当前读入的字符均为 “#” ） 。

三、 栈与递归的实现

1 递归的定义

一个直接调用自身或通过一系列过程调用语句间接地调用自身的过程， 称做递归过程。递归是程序设计过程中一个强有力的工具。 其一， 有许多数学函数是递归定义的， 如大家熟悉的阶乘函数2 阶 Fibonacci 数列和 Ackerman 函数等； 其二， 有的数据结构， 如二叉树、 广义表等， 由于结构本身固有的递归特性， 则它们的操作可递归地描述； 其三， 还有一类问题， 虽然问题

本身没有明显的递归结构， 单用递归求解比迭代求解更简单， 如八皇后问题、 Hanoi 塔问题等。

2 ． 递归函数的执行过程

与汇编程序设计中主程序和子程序之间的链接及信息交换相类似， 在高级语言编制的过程中， 调用函数和被调用函数之间的链接及信息交换需通过栈来进行。

一个递归函数的运行过程类似于多个函数的嵌套调用， 只是调用函数和被调用函数是同一个函数， 因此， 和每次调用相关的一个重要的概念是递归函数运行的 “ 层次 ” 。 假设调用该递归函数的主函数为第 0 层， 则从主函数调用递归函数为进入的第 1 层； 从第 i 层递归调用本函数为进入的 “ 下一层 ” ，即第 i+1 层。 反之， 退出第 i 层递归应返回至 “ 上一层 ” ， 即第 i-1 层。 为了保证递归函数的正确执行， 系统需设立一个 “ 递归工作栈 ” 作为整个递归函数运行期间使用的数据存储区。 每一层递归所需信息构成一个 “ 工作记录 ” ， 其中包括所有的实在参数、 所有的局部变量以及上一层的返回地址。 每进入一层递归， 就产生一个新的工作记录压入栈顶。 每退出一层递归， 就从栈顶弹出一个工作记录， 则当前执行层的工作记录必是递归工作栈栈顶的工作记录， 称这个记录为 “ 活动记录 ” ， 并称指示活动记录的栈顶指针为 “ 当前环境指针 ” 。

笔记部分（队列）

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

（ 1 ） 队列的特点

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

（ 2 ） 队列的抽象数据类型定义

ADT Queue{

数据对象：

数据关系：

基本操作：

InitQueue （ &Q ）

操作结果： 构造一个空队列 Q 。

DestroyQueue （ &Q ）

初始条件： 队列 Q 已存在。

操作结果： 队列 Q 被销毁， 不再存在。

ClearQueue （ &Q ）

初始条件： 队列 Q 已存在。

操作结果： 将 Q 清为空队列。

QueueEmpty （ Q ）

初始条件： 队列 Q 已存在。

操作结果： 若 Q 为空队列， 则返回 TRUE ， 否则 FALSE 。

QueueLength （ Q ）

初始条件： 队列 Q 已存在。

操作结果： 返回 Q 的元素个数， 即队列的长度。

GetHead （ Q ， &e ）

初始条件： Q 为非空队列。

操作结果： 插入元素 e 为 Q 的新的队头元素。

EnQueue （ &Q ， e ）

初始条件： 队列 Q 已存在。

操作结果： 插入元素 e 为 Q 的新的队尾元素。

DeQueue （ &Q ， &e ）

初始条件： Q 为非空队列。

操作结果： 删除 Q 的对头元素， 并用 e 返回其值。

QueueTraverse （ Q ， visit （） ）

初始条件： Q 已存在且非空。

操作结果： 从队头到队尾， 依次对 Q 的每个元素调用函数 visit （） 。 一旦

visit （） 失败， 则操作失败。

}ADT Queue

（ 3 ） 双端队列

双端队列（ Deque ） 是限定插入和删除操作在表的两端进行的线性表。 这两端分别称作端点 1 和端点 2 。 在实际使用中， 还有输出受限的双端队列（即一个端点允许插入和删除， 另一个端点只允许插入） 和输入受限的双端队列（即一个端点允许插入和删除， 另一个端点只允许删除） 。

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

对于在使用中数据元素变动较大的数据结构， 用链式存储结构比顺序存储结构更有利。 队列也是一种链式存储结构。

（ 1 ） 定义

用链表表示的队列简称为链队列， 一个链队列需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针） 才能唯一确定。 为了操作方便起见， 通常给链队列添加一个头结点， 并令头指针指向头结点。

（ 2 ） 特点

空的链队列的判决条件为头指针和尾指针均指向头结点。 链队列的操作即为单链表的插入和删除操作的特殊情况， 只是尚需要修改尾指针和头指针。

3 ． 循环队列 – 队列的顺序存储结构

队列的顺序存储结构中， 除了用一个能容纳最大容量元素的向量以外， 还需要两个指针分别指示队头元素和队尾元素， 并约定尾指针指向队尾元素在队列中的当前位置。 为了在 C 语言中描述方便起见， 在此我们约定： 初始化建空队列时， 令 front==rear=0 ， 每当插入新的队列尾元素时， “ 尾指针

增 1” ； 每当删除队列头元素时， “ 头指针增 1” 。 因此， 在非空队列中， 头指针始终指向队列头元素， 而尾指针始终指向队列尾元素的下一个位置。

串

笔记部分

一、 串类型的定义

1 串的逻辑结构定义

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

S=′ … ′（ n≥0 ）

其中， S 是串的名， 用单引号括起来的字符序列是串的值； a i （ 1≤i≤n ） 可以是字母、 数字或其它字符； 串中字符的数目 n 称为串的长度， 零个字符的串称为空串（ null string ） ， 它的长度为零。串中任意个连续的字符组成的子序列称为该串的子串。 包含子串的串相应地称为主串。 通常称字符在序列中的序号为该字符在串中的位置。 子串在主串中的位置则以子串的第一个字符在主串中的位置表示。当且仅当这两个串的长度相等并且对应位置的字符全部相同， 才能称两个串是相等的。

串必须用一对单引号括起来， 单引号本身不属于串， 它的作用只是为了避免与变量名或数值常量混淆而已。

2 ． 串的抽象数据类型的定义

ADT String{

数据对象：

数据关系：

基本操作： StrAssign （ &T ， chars ）

初始条件： chars 是字符串常量。

操作结果： 生成一个其值等于 chars 的串 T 。

StrCopy （ &T ， S ）

初始条件： 串 S 存在。

操作结果： 由串 S 复制得串 T 。

StrEmpty （ S ）

初始条件： 串 S 存在。

操作结果： 若 S 为空串， 则返回 TRUE ， 否则返回 FALSE 。

StrCompare （ S ， T ）

初始条件： 串 S 和 T 存在。

操作结果： 若 S>T ， 则返回值 >0 ； 若 S=T ， 则返回值 =0 ； 若 S<T ， 则返回值 <0 。

StrLength （ S ）

初始条件： 串 S 存在。

操作结果： 返回 S 的元素个数， 称为串的长度。

ClearString （ &S ）

初始条件： 串 S 存在。

操作结果： 将 S 清为空串。

Concat （ &T ， S1 ， S2 ）

初始条件： 串 S1 和 S2 存在。

操作结果： 用 T 返回由 S1 和 S2 联接而成的新串。

SubString （ &Sub ， S ， pos ， len ）

初始条件： 串 S 存在， 1≤pos≤StrLength （ S ） 且 0≤len≤StrLength （ S ） -pos+1 。

操作结果： 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。

Index （ S ， T ， pos ）

初始条件： 串 S 和 T 存在， T 是非空串， 1≤pos≤StrLength （ S ） 。

操作结果： 若主串 S 中存在和串 T 值相同的子串， 则返回它在主串 S 中第 pos 个字符之后第一次出现的位置； 否则函数值为 0 。

Replace （ &S ， T ， V ）

初始条件： 串 S ， T 和 V 存在， T 是非空串。

操作结果： 用 V 替换主串 S 中出现的所有与 T 相等的不重叠的子串。

StrInsert （ &S ， pos ， T ）

初始条件： 串 S 和 T 存在， 1≤pos≤StrLength （ S ） +1 。

操作结果： 在串 S 的第 pos 个字符之前插入串 T 。

StrDelete （ &S ， pos ， len ）

初始条件： 串 S 存在， 1≤pos≤StrLength （ S ） -len+1 。

操作结果： 从串 S 中删除第 pos 个字符起长度为 len 的子串。

DestroyStrig （ &S ）

初始条件： 串 S 存在。

操作结果： 串 S 被撤销。

}ADT String

二、 串的表示和实现

如果在程序设计语言中， 串只是作为输入或输出的常量出现， 则只需存储此串的串值， 即字符序列即可串有三种机内表示方法： 定长顺序存储表示、 堆分配存储表示、 串的块链存储表示。

1 ． 定长顺序存储表示

（ 1 ） 定长数组的描述

类似于线性表的顺序存储表示， 用一组连续的存储单元存储串值的字符序列。 在串的定长顺序存储结构中， 按照预定义的大小， 为每个定义的串变量分配一个固定长度的存储区。

（ 2 ） 串长度的表示方法

①如上述定义描述的那样， 以下标为 0 的数组分量存放串的实际长度， 如 PASCAL 语言中的串类型采用这种表示方法。

②在串值后面加一个不计入串长的结束标记字符， 如在有的 C 语言中以 “\0” 表示串值的终结。

2 ． 堆分配存储表示

这种存储表示的特点是， 仍以一组地址连续的存储单元存放串值字符序列， 但它们的存储空间是在程序执行过程中动态分配所得。 在 C 语言中， 存在一个称之为 “ 堆 ” 的自由存储区。 并由 C 语言的动态分配函数 malloc （） 和 free （） 来管理。 利用 malloc （） 为每个新产生的串分配一块实际串长所需的

存储空间， 若分配成功， 则返回一个指向起始地址的指针， 作为串的基址。

3 ． 块的串链存储表示

和线性表的链式存储结构相类似， 也可采用链表方式存储串值。 由于串结构的特殊性 — 结构中的每个数据元素是一个字符， 则用链表存储串值时， 存在一个 “ 结点大小 ” 的问题， 即每个结点可以存放一个字符， 也可以存放多个字符。 当结点大于 1 时， 由于串长不一定是结点大小的整倍数， 则链表中的最后一个结点不一定全被串值占满， 此时通常补上 “#” 或其它的非串值字符（通常 “#” 不属于串的字符集， 是一个特殊符号） 。

尾指针是为了便于进行连接操作， 但应注意连接时需处理第一个串尾的无效字符。在链式存储方式中， 结点大小的选择和顺序存储方式的格式选择一样都很重要， 它直接影响着串处理的效率。 链式存储的存储密度小（如结点大小为 l 时） ， 运算处理方便， 然而， 存储空间占用量大。 如果在串处理过程中需进行内、 外存数据交换的话， 则会因为内外存交换操作过多而影响处理的总效率。

三、 串的模式匹配算法

1 求子串位置的定位函数 Index （ S ， T ， pos ）

子串的定位操作通常称作串的模式匹配（其中 T 称为模式串） ， 是各种串处理系统中最重要的操作之一。 根据定长顺序存储结构， 写出的不依赖于

其他串操作的匹配算法如下。

int Index （ SString S ， SString T ， int pos ） {

// 返回子串 T 在主串 S 中第 pos 个字符之后的位置。 若不存在， 则函数值为 0.

// 其中， T 非空， 1 pos StrLength （ S ） 。

i=pos ； 　 j=1 ；

while （ i<=S[0]&&j<=T[0] ） {

if （ S[i]==T[j] ） {++i ； ++j ； }

else （ j>T[0] ） return i-T[0] ；

}

if （ j>T[0] ） 　 return i-T[0] ；

else return

0 ；

}

算法的基本思想是： 从主串 S 的第 pos 个字符起和模式的第一个字符比较之。 若相等， 则继续逐个比较后续字符； 否则从主串的下一个字符起再重新和模式的字符比较之。 以此类推， 直至模式 T 中的每个字符依次和主串 S 中的一个连续的字符序列相等， 则称匹配成功， 函数值为和模式 T 中第一个字符相等的字符在主串 S 中的序号， 否则称匹配不成功， 函数值为零。

2 ． 模式匹配的一种改进算法

这种改进算法是 D.E.Knuth 与 V.R.Pratt 和 J.H.Morris 同时发现的， 因此称之为克努特一莫里斯一普拉特算法（简称为 KMP 算法） ， 此算法可以在O （ n+m ） 的时间数量级上完成串的模式匹配操作。

改进之处在于： 每当一趟匹配过程中出现字符比较不等时， 不需回溯指示主串的指针 i ， 而是利用已经得到的 “ 部分匹配 ” 的结果将模式向右 “ 滑动 ” 尽可能远的一段距离后， 继续进行比较。

KMP 算法的最大特点是指示主串的指针不需回溯， 整个匹配过程中， 对主串仅需从头至尾扫描一遍。 这对处理从外设输入的庞大文件很有效， 可以边读入边匹配， 而无需回头重读。

四、 串操作应用举例

1 文本索引

文本编辑程序是一个面向用户的系统服务程序， 广泛用于源程序的输入和修改， 甚至用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色。 文本编辑的实质是修改字符数据的形式和格式。

2 ． 建立词索引表

信息检索是计算机应用的重要领域之一。 由于信息检索的主要操作是在大量的存放在磁盘上的信息中查询一个特定的信息， 为了提高查询效率，一个重要的问题是建立一个好的索引系统。 在实际系统中， 按书名检索并不方便， 因为很多内容相似的书籍其书名不一定相同。 因此较好的办法是建立 “ 书名关键词索引 ”。

数组和广义表

笔记部分（数组）

一、 数组的定义

1 抽象数据类型数组定义

ADT Array{

数据对象： j i =0,…,b i -1 ， i=1,2 ， … ， n ，

D={ |n （ >0 ） 称为数组的维数， b i 是数组第 i 维的长度， j i 是数组元素的第 i 维下标， ElemSet}

数据关系： R={R1 ， R2 ， … ， Rn}

Ri={< , >|0≤j k ≤b k -1,1≤k≤n 且 k≠i ， 0≤j i ≤b i -2 ， , D ， i=2 ， … ， n}

基本操作：

InitArray （ &A ， n ， bound1 ， … ， boundn ）

操作结果： 若数组 n 和各维长度合法， 则构造相应的数组 A ， 并返回 OK 。

DestroyArray （ &A ）

操作结果： 销毁数组 A 。

Value （ A ， &e ， index1 ， … ， indexn ）

初始条件： A 是 n 维数组， e 为元素变量， 随后是 n 个下标值。

操作结果： 若个下标不超界， 则 e 复制为所指定的 A 的元素值， 并返回 OK 。

Assign （ &A ， e ， index1 ， … ， indexn ）

初始条件： A 是 n 维数组， e 为元素变量， 随后是 n 个下标值。

操作结果： 若下标不越界， 则将 e 的值赋给所指定的 A 的元素， 并返回 OK 。

} ADT array

2 ． 数组和线性表的关系

可以把二维数组看成是这样一个定长线性表： 它的每个数据元素也是一个定长线性表。 以 m 行 n 列的矩阵形式表示。 它可以看成是一个线性表。A= （ α 0 ， α 1 ， … ， α p ） （ p=m-1 或 n-1 ）其中每一个数据元素 α j 是一个列向量的线性表α j = （ a 0j ,a 2j ， … ， a m-1 ，j ）1≤j≤n-1或者 α i 是一个行向量的线性表α i = （ a i1 ， a i2 ， … ， a i ，n-1 ）1≤i≤m-1。 在 C 语言中， 一个二维数组可以用其分量类型为一维数组的数组来定义

数组一旦被定义， 它的维数和维界就不再改变。 因此， 除了结构的初始化和销毁之外， 数组只有存取元素和修改元素值的操作。

二、 数组的顺序表示和实现

1 二维数组的两种存储方式

建立了数组， 则结构中的数据元素个数和元素之间的关系就不再发生变动， 因此采用顺序存储结构。 二维数组可有两种存储方式： 一种以列序为主序（ column-major-order ） 的存储方式；另一种是以行序为主序（ row-major-order ） 的存储方式。

2 ． 数组元素的存储位置

（ 1 ） 数组元素存储位置的计算

以行序为主序的存储结构为例， n 维数组中的数据元素存储位置的计算公式为：$loc(a_ij)=loc(a_11)+[(i-1)n+(j-1)m]*l$

可缩写成$loc(a_ij)=loc(a_11)+l(in+jm-n-m)$

（ 2 ） 随机存储结构

数组元素的存储位置是其下标的线性函数， 一旦确定了数组的各维的长度， c i 就是常数。 由于计算各个元素存储位置的时间相等， 所以存取数组中任一元素的时间相等。 我们称具有这一特点的存储结构为随机存储结构。

三、 矩阵的压缩存储

在数值分析中经常出现一些阶数很高的矩阵， 同时在矩阵中有许多值相同的元素或者是零元素。 为了节省存储空间， 可以对这类矩阵进行压缩存储。 即为多个值相同的元只分配一个存储空间， 对零元不分配空间。

假若值相同的元素或者零元素在矩阵中的分布有一定的规律， 则我们称此类矩阵为特殊矩阵； 反之， 称为稀疏矩阵。

1 ． 特殊矩阵

（ 1 ） 对称矩阵

若一个 n 阶矩阵 A 中的元满足下述性质 $a_ij = a_ji$ ， 则称其为 n 阶对称矩阵。

（ 2 ） 对称矩阵的存储

若将每一对对称元分配一个存储空间， 则可将 个元压缩存储到 $n(nn+1)/2$个元的空间中。

因此，我们可以按从上到下、从左到右将这些元素存放在一个向量 sa[0…n(n+1)/2-1] 中。为了便于访问对称矩阵A中的元素，我们必须在 aij 和sa[k] 之间找一个对应关系。

若 i >= j，则aij在下三角形中。 aij 之前的 i 行（从第0行到第 i-1行）一共有 1+2+…+i=i(i+1)/2 个元素，在第 i 行上， aij 之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：

$k = i ∗ ( i + 1 ) / 2 + j k\=i*(i+1)/2+jk\=i∗(i+1)/2+j0 < = k < n ( n + 1 ) / 2 0<=k<n(n+1)/20<=k<n(n+1)/2$若 i<j ，则aij是在上三角矩阵中。因为 aij=aji，所以只要交换上述对应关系式中的i和j即可得到：k = j ∗ ( j + 1 ) / 2 + i k=j*(j+1)/2+ik=j∗(j+1)/2+i0 ≦ k < n ( n + 1 ) / 2 0≦ k<n(n+1)/20≦k<n(n+1)/2

(3)三角矩阵

以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。

三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有 n(n+1)/2个，因此，三角矩阵可压缩存储到向量 sa[0…n(n+1)/2] 中，其中c存放在向量的最后一个分量中，上三角矩阵中,主对角线之上的第i行(0<=i<n)恰有 n-i 个元素，按行优先顺序存放上三角矩阵中的元素 aij时，aij之前的i行一共有i(2n-i+1)/2 个元素，

在第 i 行上，aij前恰好有 j-i 个元素：aii, aii+1, … aij-1。因此，sa[k] 和 aij的对应关系是：

当 i < = j : k = i ( 2 n − i + 1 ) / 2 + j − i

当 i > j : k = n ( n + 1 ) / 2

下三角矩阵的存储和对称矩阵类似，sa[k]和aij对应关系是：

当 i>=j,k=i(i+1)/2+j

当 i < j , k = n ( n + 1 ) / 2 。

上述对称矩阵的存储方式也适用于三角矩阵和对角矩阵。 一般统称的特殊矩阵中， 非零元的分布都有一个明显的规律， 从而可将其压缩存储到一维数组中， 并找到每个非零元在一维数组中的对应关系。

2 ． 稀疏矩阵

（ 1 ） 稀疏矩阵的定义

稀疏矩阵的概念只能凭人们的直觉来了解。 假设在 m×n 的矩阵中， 有 t 个元素不为零。 令 ， 称e=$\s/(m*n)\$为矩阵的稀疏因子。 通常认为 e≤0.05 时称为稀疏矩阵。

（ 2 ） 三元组顺序表

①三元组顺序表的定义

假设以顺序存储结构来表示三元组表， 则可得稀疏矩阵的一种压缩存储方式 —— 我们称之为三元组顺序表。一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元.

下列三元组表

( (1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7) )加上(6,7,8)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。

#define maxsize 10000
typedef int datatype;
typedef struct
{
	int i,j;
	datatype v;
}triplet;
typedef struct
{
	triplet data[maxsize];
	int  m,n,t;
}tripletable;

Untitled

②三元组顺序表的运算

压缩存储结构下矩阵的两种运算：

a ． 转置；

b ． 相乘。

（ 3 ） 十字链表

①十字链表的定义

同一行的非零元听过 right 域链接成一个线性链表， 同一列的非零元通过 down 域链接成一个线性链表， 每一个非零元既是某个行链表中的一个结点， 又是某个列链表中的一个结点， 整个矩阵构成了一个十字交叉的链表， 故称这样的存储结构为十字链表。

②采用十字链表的原因

当矩阵非零元的位置或个数经常变动 时， 三元组就不适合于作稀疏矩阵的存储结构。

③十字链表的特点

链表中， 每个非零元用一个结点表示， 结点中除了表示非零元的三元组外（ row ， col ， val ） 还有两个链域： 向下域（ down ） 和向右域（ right ）

四、 广义表

1 广义表的定义

广义表是线性表的推广 。 也有人称其为列表（ 1ists ， 用复数形式以示与统称的表 list 的区别） 。 广义表一般记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。 在线性表的定义中， 只限于是单个元素。 而在广义表中， 可以是单个元素， 也可以是广义表， 分别称为广义表 LS 的原子和子表。

Untitled

2 ． 广义表的举例

广义表的定义是一个递归的定义。

3 ． 列表的三个重要结论：

（ 1 ） 列表的元素可以是子表， 而子表的元素还可以是子表 …… 。 由此， 列表是一个多层次的结构， 可以用图形象地表示。

（ 2 ） 列表可为其它列表所共享。

（ 3 ） 列表可以是一个递归的表， 即列表也可以是其本身的一个子表。

五、 广义表的存储结构

广义表中的数据元素可以具有不同的结构（或是单元素， 或是列表） ， 因此难以用顺序存储结构表示， 通常采用链式存储结构， 每个数据元素可

用一个结点表示。

1 ． 设定结点的结构

若列表不空， 则可分解成表头和表尾； 反之， 一对确定的表头和表尾可唯一确定列表。 由此， 一个表结点可由三个域组成： 标志域、 指示表头的

指针域和指示表尾的指针域， 而元素结点只需两个域： 标志域和值域。 结点的结构说明如图 5-5 所示。

图 5-5 结点的结构

2 ． 广义表的存储结构

广义表的存储结构如图 5-6 所示。

图 5-6 广义表的存储结构示例

3 ． 其他存储结构

广义表的另一种结点结构的链表示列表， 如图 5-7 和图 5-8 所示。

图 5-7 另一种存储结构的结点

5-8 广义表的另一种存储结构

六、 m 元多项式的表示

广义表中的数组元素可以是另外一个广义表， 一个 m 元多项式的表示是广义表的典型应用。

对任何一个 m 元多项式都可进行如此操作： 先分解出一个主变元， 随后再分解出第二个变元， 等等。 由此， 一个 m 元的多项式首先是它的主变元的

多项式， 而其系数又是第二变元的多项式， 由此可用广义表来表示 m 元多项式。

七、 广义表的递归算法

1 求广义表的深度

广义表的深度定义为广义表中括弧的重数， 是广义表的一种度量。 求广义表深度的递归函数如下所示。

int GListDepth （ GList L ） {

// 采用头尾链表存储结构， 求广义表 L 的深度

if （ !L ） return 1 ；

if （ L->tag==ATOM ） retrun 0 ；

for （ max=0 ， pp=L ； pp ； pp=pp->ptr.tp ） {

dep=GListDepth （ pp->ptr->hp ） ；

if （ dep>max ） max=dep ；

}

return max+1 ；

}

2 ． 复制广义表

复制广义表只需复制其表头和表尾， 然后合成即可。 复制广义表的递归算法如下所示。

Status CopyGList （ GList &T ， GList L ） {

if （ !L ） T=NULL ；

else{

if （ !T= （ GList ） malloc （ sizeof （ GLNode ） ） ） exit （ OVERFLOW ） ；

T->tag=L->tag ；

if （ L->tag==ATOM ） T->atom=L->atom ；

else{

CopyGList （ T->ptr.hp ， L->ptr.hp ） ；

CopyGList （ T->ptr.tp ， L->ptr.tp ） ；

}

}

return OK ；

}

3 ． 建立广义表的存储结构

建广义表存储结构的递归过程如图 5-11 所示。

Status CreateGList （ GList &L ， SString S ） {

if （ StrCompare （ S,emp ） ） L=NULL ；

else{

if （ !L= （ GList ） malloc （ sizeof （ GLNode ） ） ） exit （ OVERFLOW ） ；

if （ StrLength （ S ） ==1 ） {L->tag=ATOM ； L->atom=S ； }

else{

L->tag=LIST ； p=L ；

SubString （ sub ， S ， 2 ， StrLength （ S ） -2 ） ；

do{

sever （ sub ， sub ） ；

CreateGList （ p->ptr.hp ， hsub ） ； q=p ；

if （ !StrEmpty （ sub ） ） {

if （ ! （ p= （ GLNode * ） malloc （ sizeof （ GLNode ） ） ） ）

exit （ OVERFLOW ） ；

p->tag=LIST ； q->ptr.tp=p ；

}

}while （！ StrEmpty （ sub ） ） ；

q->ptr.tp=NULL ；

}else

}

return OK ；

}

Status sever （ SString &str ， SString &hstr ） {

n=StrLength （ str ） ； i=0 ； k=0 ；

do{

++i ；

SubString （ ch ， str ， i ， 1 ） ；

if （ ch==’ （ ’ ） ++k ；

else if （ ch==’ ） ’ ） --k ；

}while （ i<n&& （ ch!=’ ， ’||k!=0 ） ） ；

if （ i<n ） {

SubString （ hstr ， str ， 1 ， i-1 ） ； SubString （ str ， str ， i+1 ， n-i ） ；

else{StrCopy （ hstr ， str ） ； ClearString （ str ） ； }

}

：

树和二叉树

1.树的定义及基本术语

定义

树（ tree ） 是 n （ n≥0 ） 个结点的有限集。

在一棵非空树中：

有且仅有一个特定的称为根（ root ） 的结点；

当 n>1 时， 其余结点可分为 m （ m>0 ） 个互不相交的有限集 ， ， … ， ， 其中每一个集合本身又是一棵树， 并且称为根的子树。

例如， 在图 6-1 中， （ a ） 是只有一个根结点的树； （ b ） 是有 l3 个结点的树， 其中 A 是根， 其余结点分成三个互不相交的子集：={B ， E ， F ， K ， L} ， ={C ， G} ， = （ D ， H ， I ， J ， M} ； T l 、 T 2 和 T 3 都是根 A 的子树， 且本身也是一棵树。 对树的定义可用图 6-1 表示：

树的形式化定义

树是一种数据结构 Tree= （ D ， R ） 其中： D 是具有相同特性的数据元素的集合； 若 D 只含一个数据元素， 则 R 为空集， 否则 R 是 D 上某个二元关系 H 的集合， 即 R={H} 。 H 为如下描述的二元关系： （ 1 ） 在 D 中存在唯一的称为根的数据元素 root ， 它在关系 H 下无前驱； （ 2 ） 若 D={root}≠空， 则存在 D={root} 的一个划分 ， ， … ， （ m>0 ） ， 对任意一对 j≠k （ 1≤j ， k≤m ） 有 = ， 且对任意的 i （ 1≤i≤m ） ，存在唯一数据元素 ∈ ， 有（ root ， ） ∈ H ； （ 3 ） 对应于 D={root} 的划分， H={ （ root ， ） ， … ， （ root ， ） ） 有唯一的一个划分 ， ， … ， （ m>0 ） ， 对任意 j≠k （ 1≤j ， k≤m ） 有， 且对任意的 i （ 1≤i≤m ） ， 是 上的二元关系， （ ， { } ） 是一棵符合本定义的树， 称为根 root 的子树。

树的表示形式

如图 6-2 所示为图 6-1 （ b ） 中树的各种表示形式。 其中： （ a ） 是以嵌套集合（即一些集合的集体， 对于其中任何两个集合， 或者不相交， 或者一个包含另一个） 的形式表示的； （ b ） 是以广义表的形式表示的， 根作为由子树森林组成的表的名字写在表的左边； （ c ） 用的是凹入表示法（类似书的编目） 。

（1 ） 结点： 树的结点包含一个数据元素及若干指向其子树的分支。 （ 2 ） 结点的度（ degree ） ： 结点拥有的子树个数称为结点的度。 （ 3 ） 树的度（ degree ） ： 树的度是树内各结点的度的最大值。 （ 4 ） 叶子（或终端结点） ： 度为 0 的结点称为叶子（ 1eaf ） 或终端结点。 度不为 0 的结点称为非终端结点或分支结点。 除根结点之外， 分支结点也称为内部结点。 （ 5 ） 结点的孩子、 双亲： 结点的子树的根称为该结点的孩子（ child ） ， 相应地， 该结点称为孩子的双亲（ parent ） 。 （ 6 ） 结点的兄弟（ sibing ） ： 同一双亲的孩子之间互称为兄弟。 （ 7 ） 树的深度（ depth ） ： 树中结点的最大层次称为树的深度（ depth ） 或高度。 （ 8 ） 结点的祖先： 从根到该节点所经分支上的所有节点。 （ 9 ） 结点的子孙： 以该节点为根的子树中的任一结点。 （ 10 ） 结点的层次： 从根开始定义， 根为第一层， 根的孩子为第二层。 （ 11 ） 结点的堂兄弟： 其双亲在同一层的结点互为堂兄弟。 （ 12 ） 森林（ forest ） ： m （ m≥0 ） 棵互不相交的树的集合。 对树中每个结点而言， 其子树的集合即为森林。 （ 13 ） 有序数与无序树： 如果将树中结点的各子树看成从左至右是有次序的（即不能互换） ， 则称该树为有序数， 否则称为无序树。 有序数中最左边的子树称为第一个孩子， 最右边的称为最后一个孩子。

任何一棵树是一个二元组 Tree= （ root ， F ） ， 其中： root 是数据元素， 称做树的根结点； F 是 m （ m≥0 ） 棵树的森林， F= （ ， ， … ， ） ， 其中= （ ， ） 称做根 root 的第 i 棵子树； 当 i≠0 时， 在根结点和其子树森林之间存在下列关系：

2.二叉树

二叉树的定义

二叉树（ binary tree ） 是另一种树型结构， 它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于 2 的结点） ， 并且二叉树的子树有左右之分， 其次序不能任意颠倒。 形式化定义 二叉树是一种数据结构：

BinaryTree= （ D ， R ）
其中： D 是具有相同特性的数据元素的集合； 若 D= ， 则 R= ， 称 BinaryTree 为空的二叉树； 若 D≠ ， 则 R 是 D 上某个二元关系 H 的集合， 即
R={H} ， 且
① D 中存在唯一的称为根的元素 r ， 它在关系 H 下无前驱；
②若 D-{r}≠ ， 则 D-{r}={D ι ， D r } ， = ；
③若 ≠ ， 则在 n 中存在唯一的元素 ， <r ， > ∈ H ， 且存在 上的关系 ∈ H ； 若 ≠ ， 则在 中存在唯一的元素 ， （ r ， ） ∈ H ， 且存
在 上的关系 ∈ H ； H={ （ r ， ） ， （ r ， ） ， ， } ；
④（ D ι ， H ι ） 是一棵符合本定义的二叉树， 称为根 r 的左子树， （ D r ， H r ） 是一棵符合本定义的二叉树， 称为根 r 的右子树。

二叉树可以有五种基本形态， 如图所示。

二叉树的性质

性质 l ： 在二叉树的第 i 层上至多有 $2_m$个结点（ i≥1 ） 。 性质 2 ： 深度为 k 的二叉树至多有 -l 个结点， （ k≥1 ） 。 性质 3 ： 对任何一棵二叉树 T ， 如果其终端结点数为 n 0 ， 度为 2 的结点数为 n 2 ， 则 n 0 =n 2 +1 。