数据结构课件.ppt

1 数据结构 2 课程简介 核心基础课程计算机及相关专业的升学必考课程52课堂 12实验C C 编程能力 抽象思维 时间 2X 考核 笔试 其中 期末 70 实验 平时30 3 教学目标 讲授各种常用的数据结构 各种排序 查找算法等 为软件设计 数据的组织与处理和解决各种实际应用问题打下理论基础 也为学习后续课程创造条件初步拥有分析研究计算机加工数据结构特性的能力 以便为日后应用开发所涉及的数据选择适当的逻辑结构 存储结构并设计相应的算法 4 参考书目 数据结构 C语言版 严蔚敏清华大学出版社教材配套习题集清华大学出版社数据结构习题与解析 C语言篇 李春保清华大学出版社数据结构辅导与提高徐孝凯著清华大学出版社数据结构 用面向对象方法与C 描述 殷人昆等清华大学出版社数据结构习题解析 殷人昆等清华大学出版社数据结构 C 版 美 D S Mailk著清华大学出版社C 编程 数据结构与程序设计方法 美 D S Malik著电子工业出版社 5 课前的话 计算机系列课程之间的联系 6 数据结构课程的地位 是介于数学 计算机硬件和计算机软件三者之间的一门核心课程 7 基础 坚实的数学 逻辑基础复习C C 重点是结构 类型定义 指针的运用 递归 8 第一章绪论 1 1什么是数据结构建立数学模型是分析具体问题的过程 包括 分析具体问题中操作对象找出这些对象间的关系 并用数学语言描述数学模型分两类 1 数值计算类 例 根据三条边 求三角形面积 假定 三条边依次为a b c三个实型数 满足 a 0 b 0 c 0 a b c b c a c a b 则s area 9 2 非数值计算类 例1 5个整数组成的集合 D 20 5 66 15 44 其中 20 5 66等称为数据元素 元素 元素与元素之间关系是它们同属于集合D D 20 5 66 15 44 是一个数据对象例2 一列整数 线性结构 L 20 5 66 15 44 其中 元素与元素之间在L中是前后关系或线性关系 L 20 5 66 15 44 是一个线性表 10 例3一张登记表DL序号姓名性别年龄1李刚男25记录12王霞女29记录23刘大海男40记录34李爱林男44记录4其中 姓名 性别 年龄是数据项 item 数据域 field 姓名 性别 年龄 是记录 record C语言将 记录 record 定义为 结构 struct 登记表也是一个线性表 11 例4树状结构 其中 A B C等是结点 node A与B B与E A与C之间是层次关系或父子关系 12 例5图状结构 A B D C E F G 其中 A B C等是顶点 vertex 图中任意两个顶点之间都可能有关系 13 例6田径赛的时间安排问题 无向图的着色问题 设有六个比赛项目 规定每个选手至多可参加三个项目 有五人报名参加比赛 如下表所示 设计比赛日程表 使得在尽可能短的时间内完成比赛 14 用如下六个不同的代号代表不同的项目 跳高跳远标枪铅球100米200米ABCDEF用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边 某选手比赛的项目必定有边相连 不能同时比赛 对图上的每个顶点染一种颜色 并且要求有线相连的两个顶点不能具有相同颜色 而总的颜色种类应尽可能地少 同色可以同时比赛 15 A E B F D C 只需安排四个单位时间进行比赛 16 教材P2 3例1 例2 例3综上几个例子可见 描述这类非数值问题的数学模型不再是数学方程 而是诸如表 树和图之类的数据结构 因此简单说来 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科 17 计算机内的数值运算依靠方程式 而非数值运算 如表 树 图等 则要依靠数据结构同样的数据对象 用不同的数据结构来表示 运算效率可能有明显的差异 程序设计的实质是对实际问题选择一个好的数据结构 加之设计一个好的算法 而好的算法在很大程度上取决于描述实际问题的数据结构 算法 数据结构 程序1976年 瑞士N Wirth教授 18 1 2基本概念和术语 数据 Data 是对信息的一种符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素 DataElement 是数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 一个数据元素可由若干个数据项组成 数据项是数据的不可分割的最小单位 数据对象 DataObject 是性质相同的数据元素的集合 是数据的一个子集 19 数据结构数据结构定义1 在任何问题中 数据元素都不是孤立存在的 而是在它们之间存在着某种关系 这种数据元素相互之间的关系称为结构 Structure 数据结构的形式定义为 数据结构是一个二元组Data Structure D S 1 1 其中 D是数据元素的有限集 S是D上关系的有限集 数据结构主要指逻辑结构和物理结构 20 数据之间的相互关系称为逻辑结构 即从逻辑关系上描述数据 与数据的存储无关 是独立于计算机的 通常分为四类基本结构 集合结构中的数据元素除了同属于一种类型外 别无其它关系 线性结构结构中的数据元素之间存在一对一的关系 树形结构结构中的数据元素之间存在一对多的关系 图状结构或网状结构结构中的数据元素之间存在多对多的关系 21 物理结构亦称存储结构 是数据的逻辑结构在计算机存储器内的表示 或映像 依赖于计算机 存储结构可分为4大类 顺序 链式 索引 哈希例 见教材P6 复数3 0 2 3i的两种存储方式 法1 地址内容 法2 地址内容 22 同一种逻辑结构可采用不同的存储方法 以上四种之一或组合 这主要考虑的是运算方便及算法的时空要求数据结构基本操作的实现 基本操作在计算机上的实现 方法 23 24 如何描述存储结构可以借用高级程序语言中提供的 数据类型 来描述它 例如 可以用 一维数组 类型来描述顺序存储结构 以C语言提供的 指针 来描述链式存储结构假如把C语言看成是一个执行C指令和C数据类型的虚拟处理器 那么讨论的存储结构是数据结构在C虚拟处理器中的表示 不妨称它为虚拟存储结构 25 数据类型 datatype 是一个值的集合和定义在这个值上的一组操作的总称原子类型 如 int char float等 结构类型 如 数组 结构 联合体等 抽象数据类型 AbstractDataType 与计算机实现无关的数据类型形式定义 ADT抽象数据类型名 1 数据对象 2 数据关系 一个或多个关系 3 一组基本操作 运算 ADT抽象数据类型名 26 数据对象和数据关系的定义用伪码描述 基本操作的定义格式为基本操作名 参数表 初始条件 操作结果 基本操作有两种参数 传值参数 引用参数 以 符号打头 例1 6 P9 27 1 3抽象数据类型的表示与实现 采用类C语言描述数据结构 类C语言精选了C语言的一个核心子集 同时作了若干扩充修改 增强了语言的描述功能类C语言简要说明 参见书10 11页 为了便于算法描述 使算法易于理解 类C中函数的形参 除了允许值参外 增添了C 语言的引用参数 在函数的形参表中 以引用参数是实参的别名 28 交换两个整数变量 voidswap intn intm 参数为值参inttemp temp n n m m temp main inta 10 b 20 swap a b 传值 结果 a 10 b 20 voidswapx int 传引用 结果 a 20 b 10 原因 调用swap a b 时 实参a b的值被传递给swap intn intm 的形参n m 调用swap a b 的结果n和m的值交换 而变量a b的值并没有交换 调用swapx c d 时 形参n m作为实参c d别名 n和c对应同一个变量 m和d对应 调用swapx c d 的结果n和m的值交换 即变量c d的值交换 29 在本课程中 数据的存储结构是用C语言的数据类型描述 定义 的 主要用到下列数据类型 数组 结构 指针1数组数组类型变量 数组变量 由一组类型相同的数据元素组成数组的类型定义和变量定义typedef数组元素类型名数组类型名 常量表达式 数组类型名数组变量名 例某班30个学生的数学成绩 可以用有30个分量的整型数组变量存储 TypedefintScores 30 Scoresclass051 30 该数组在内存中的存储示意图 class051 0 xFF000 xFF040 xFF080 xFF9C 85776882 31 2结构结构类型变量 结构变量 由一组类型可以不同的数据元素组成结构的类型定义和变量定义typedef结构定义结构类型名 结构类型名结构变量名 例一本书可以用有2个成员 数据域 的结构变量存储 Typedefstruct intno chartitle 40 BookType BookTypebook1 32 该结构变量在内存中的存储示意图 0 xFF000 xFF040 xFF050 xFF2B 154685 0 x00025C3D D A T A S T book1 notitle 3D5C0200 33 3指针指针类型变量 指针变量 用于存储变量地址 或称指向该变量 指针的类型定义和变量定义 只介绍本课程用到的指向结构变量指针类型 typedef结构定义 指针的类型名 指针的类型名指针变量名例typedefstruct intno chartitle BookPtr BookPtrpbook 34 该变量在内存中的存储示意图 0 xAF000 xAF040 xAF050 xAF2B 154685 D A T A S T 0 xAF00 notitle 0 xEF20 pbook book1 35 1 4算法和算法分析 1 4 1算法 algorithm 是对特定问题求解步骤的一种描述 算法是指令的有限序列 其中每一条指令表示一个或多个操作算法特性有穷性 确定性 可行性 输入 输出算法的含义与程序十分相似 但二者是有区别的 一个程序不一定满足有穷性 死循环 另外 程序中的指令必须是机器可执行的 而算法中的指令则无此限制 一个算法若用计算机语言来书写 则它就可以是一个程序 36 1 4 2算法设计的要求评价一个好的算法有以下几个标准 正确性 Correctness 算法应满足具体问题的需求 可读性 Readability 算法应该好读 以有利于阅读者对程序的理解 健壮性 Robustness 算法应具有容错处理 当输入非法数据时 算法应对其作出反应 而不是产年莫名其妙的输出结果效率与存储量需求效率指的是算法执行的时间 存储量需求指算法执行过程中所需要的最大存储空间 这两者与问题的规模有关 37 1 4 3算法效率的度量 事先分析求出该算法的时间界限函数事后测试收集此算法的执行时间和实际占用空间的统计资料将一个算法转换成程序并在计算机上执行时 其运行所需要的时间取决于下列因素 硬件的速度 书写程序的语言 编译程序所生成目标代码的质量 问题的规模 在各种因素都不能确定的情况下 很难比较出算法的执行时间 也就是说 使用执行算法的绝对时间来衡量算法的效率是不合适的 为此 将上述各种与计算机相关的软 硬件因素都确定下来 这样一个特定算法的运行工作量的大小就只依赖于问题的规模 通常用正整数n表示 或者说它是问题规模的函数 38 一个算法的评价主要从时间复杂度和空间复杂度来考虑时间复杂度1 时间频度 一个算法中的原操作执行次数称为语句频度或时间频度 记为T n 2 时间复杂度想知道T n 变化规律若有某个辅助函数f n 使得当n趋近于无穷大时 T n f n 的极限值为不等于零的常数 则称f n 是T n 的同数量级函数 记作T n f n 称O f n 为算法的渐近时间复杂度 简称时间复杂度例如 若T n n n 1 2 则有1 4 T n n2 1 故它的时间复杂度为 n2 即 n 与n2数量级相同 39 算法效率的度量 采用时间复杂度 例1 11分析以下程序段的时间复杂度for i 1 i n i y y 1 for j 0 j 2 n j x n 1 该程序段的时间复杂度 T n 40 例1 12分析以下程序段的时间复杂度i 1 while i n i i 2语句1的频度是 1设语句2的频度是f n 则有 即 取最大值则该程序段的时间复杂度为 1 2 41 例1 13x 1 for i 1 i n i for j 1 j i j for k 1 k j k x 由于内循环的执行次数虽与规模n无直接关系 但与外循环的变量取值有关 因此从内层向外层循环分析执行次数 42 f n O n 43 常见函数的时间复杂度按数量递增排列及增长率P16图1 7 时间复杂度T n 按数量级递增顺序为 复杂度高 复杂度低 44 加法规则针对并列程序段T n m T1 n T2 m O max f n g m 乘法规则针对嵌套程序段 n m T1 n T2 m O f n g m 45 voidexam floatx intm intn floatsum for inti 0 i m i x中各行数据累加sum i 0 0 for intj 0 j n j sum i x i j for i 0 i m i 打印各行数据之和cout i sum i endl 渐进时间复杂度为O max m n m 46 空间复杂度与时间复杂度类似 空间复杂度是指算法在计算机内执行时所需存储空间的度量 记作 S n O f n 一般所讨论的是除正常占用内存开销外的辅助存储单元规模 讨论方法与时间复杂度类似 不再赘述 47 本章小结 数据 数据结构等基本概念数据结构的三个方面的内容抽象数据类型的概念线性和非线性结构的逻辑特征数据存储的四种基本方法算法 算法的时间复杂度及其分析的简易方法 48 HOMEWORK1 复习C语言 重点是基本语句 结构类型 指针和递归复习本章预习下一章C C 程序内存的格局 1 全局数据区2 代码区3 栈区4 堆区 49 第二章线性表 线性结构的特点熟练掌握两种存储结构的描述方法 链表是本章的重点和难点熟练掌握顺序表的定义与实现 包括查找 插入 删除算法的实现熟练掌握在各种链表结构中实现线性表操作的基本方法 能在实际应用中选用适当的链表结构 50 2 1线性表的类型定义 a1 a2 ai 1 ai ai 1 an 1 线性表的定义 是n个数据元素的有限序列 n 0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标 是元素的序号 表示元素在表中的位置 n为元素总个数 即表长 空表 线性终点 51 例分析26个英文字母组成的英文表 A B C D Z 例分析学生情况登记表 数据元素都是记录 元素间关系是线性 数据元素都是字母 元素间关系是线性 同一线性表中的元素必定具有相同特性 52 线性表的抽象数据类型 ADT P19其中只是一些基本操作 另外可以更复杂 如 将两个线性表合并等 复杂的操作可用基本操作实现 例2 1利用两个线性表LA和LB分别表示两个集合A和B 现要求一个新的集合A A B voidunion Listif LocateElem La e equal ListInsert La La len e 53 例2 2有线性表LA和LB 其元素均按非递减有序排列 编写一个算法将它们合并成一个线性表LC 且LC的元素也是按非递减有序排列 算法思路 依次扫描通过LA和LB的元素 比较当前的元素的值 将较小值的元素赋给LC 如此直到一个线性表扫描完毕 然后将未完的那个顺序表中余下部分赋给LC即可 LC的容量要能够容纳LA LB两个线性表相加的长度P21 54 2 2线性表的顺序表示和实现 线性表的顺序表示又称为顺序存储结构或顺序映像逻辑上相邻 物理上也相邻用一组地址连续的存储单元依次存储线性表的元素 可通过数组来实现若已知表中首元素在存储器中的位置 则其他元素存放位置亦可求出 利用数组下标 55 线性表 a1 a1 a2 an 顺序存储结构的一般形式序号存储状态存储地址1b2b pib i 1 pnb n 1 p自由区maxlengb maxleng 1 p其中 b 表的首地址 基地址 元素a1的地址 p 1个数据元素所占存储单元的数目 maxleng 最大长度 为某个常数 56 线性表顺序结构在C语言中的定义其中 SqList 结构类型名La 结构类型变量名La length 表长La elem 0 a1La elem La length 1 an definemaxleng100structSqList ElemTypeelem maxleng 下标 0 1 maxleng 1intlength 表长 SqListLa 57 线性表的顺序存储结构定义 动态 defineList Init size100 defineListincrement10structSqList ElemType elem intlength intlistsize 58 顺序存储结构的寻址公式i 12in地址 bb 1b i 1 pb n 1 p假设 线性表的首地址为b 每个数据元素占p个存储单元 则表中任意元素ai 1 i n 的存储地址是 LOC i LOC 1 i 1 p b i 1 p 1 i n 例 假设b 1024 p 4 i 35LOC i b i 1 p 1024 35 1 4 1024 34 4 1160 59 插入算法实现举例设L elem 0 maxleng 1 中有legth个元素 在L elem i 1 之插入新元素e 1 i length例 i 3 e 6 length 6插入6之前 258203035 01234567835 30 20 8依次后移一个位置插入6之后 2568203035 012345678 60 算法2 4 p 24 插入操作移动元素次数的分析在 a1 a2 ai an 中ai之前插入新元素e 1 i n 1 当i 123jnn 1移动元素次数个数 nn 1n 2n i 110假定在各位置插入元素的概率相同 则插入一个元素时移动元素的平均值是n 2删除操作移动元素次数的分析当i 123 i n移动元素次数个数 n 1n 2 n i 0假定在各位置插入元素的概率相同 则删除一个元素时移动元素的平均值是 n 1 2算法2 7 p 26 61 顺序存储结构的评价优点 1 是一种随机存取结构 存取任何元素的时间是一个常数 速度快 2 结构简单 逻辑上相邻的元素在物理上也是相邻的 3 不使用指针 节省存储空间 缺点 1 插入和删除元素要移动大量元素 消耗大量时间 2 需要一个连续的存储空间 3 插入元素可能发生 溢出 4 自由区中的存储空间不能被其它数据共享 62 2 3线性表的链式存储结构 顺序表 随机存取链表 逻辑相邻 物理不一定相邻特点每个元素 表项 由结点 Node 构成 线性结构结点可以不连续存储表可扩充适用于存储空间需求不定 插入或删除频繁的情形 datanext a0 a1 a2 a3 a4 first 63 free a 可利用存储空间 a0 a2 a1 a3 free first b 经过一段运行后的单链表结构 单链表的存储映像 64 2 3 1线性链表 用一组任意的存储单元存储线性表的数据元素 可以是零散分布在内存中的任意位置上的 链表中结点的逻辑次序和物理次序不一定相同 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai 除存储本身信息外 还需存储其直接后继的地址 或位置 信息 这个信息称为指针 pointer 或链 link 结点数据域 元素本身信息指针域 指示直接后继的存储位置 65 31 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG H 例线性表 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 43 13 1 NULL 37 7 19 25 31 H 头指针 66 结点 数据元素的存储映像 由数据域和指针域两部分组成 链表 n个结点由指针链组成一个链表 它是线性表的链式存储映像 称为线性表的链式存储结构 单链表 双链表 多链表 循环链表 结点只有一个指针域的链表 称为单链表或线性链表 有两个指针域的链表 称为双链表 有多个指针域的链表 称为多链表 首尾相接的链表称为循环链表 67 头指针 头结点和首元结点头指针是指向链表中第一个结点 或为头结点或为首元结点 的指针 单链表可由一个头指针唯一确定 头结点是在链表的首元结点之前附设的一个结点 数据域内只放空表标志和表长等信息 首元结点是指链表中存储线性表第一个数据元素a1的结点 68 一个线性表的逻辑结构为 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 其存储结构用单链表表示如下 请问其头指针的值是多少 例 答 头指针是指向链表中第一个结点的指针 因此关键是要寻找第一个结点的地址 31 头指针的值是31 69 上例链表的逻辑结构示意图有以下两种形式 区别 无头结点 有头结点 70 单链表的C定义 或 typedefstructnode LPointer structnode intdata LPointernext typedefstructnode intdata node next LinkList 71 单链表的插入 在第一个结点前插入newnode next first first newnode 72 data next q data next data next data null first data next data next data null first data next q 73 在链表中间插入newnode next current next current next newnode 74 data next data next data null data next q p data next data next data null data next q 75 在链表末尾插入newnode next current next current next newnode 76 在链表中设置头结点在链表的首元结点之前附设的一个头结点 该结点的数据域中不存储线性表的数据元素 其作用是为了对链表进行操作时 可以对空表 非空表的情况以及对首元结点进行统一处理 编程更方便无头结点时 当头指针的值为空时表示空表 有头结点时 当头结点的指针域为空时表示空表 77 带头结点的单链表第一个结点前插入新结点 first newnode first newnode 插入 first newnode first newnode 插入 p p p p newnode next p next p next newnode 78 从带头结点的单链表中删除第一个结点 q p next p next q next deleteq first first 非空表 first first 空表 p q p q 79 P30 31算法2 9 2 10 2 11 2 12就地逆置一个带头结点的链表静态链表 自学 LNode p head newLNode LPointer malloc sizeof LNode 创建新头结点while h NULL p h h h next 摘下h链头结点p next head next head next p 插入head链前端 h head next deletehead 重置h 删去head头结点 80 2 3 2循环链表 CircularList 循环链表是单链表的变形 循环链表最后一个结点的next指针不为NULL 而是指向了表的前端 为简化操作 在循环链表中往往加入表头结点 循环链表的特点是 只要知道表中某一结点的地址 就可搜寻到所有其他结点的地址 81 循环链表的示例 带表头结点的循环链表 82 循环链表的运算与单链表类似 只是在涉及到链头与链尾的处理时稍有不同表尾插入 83 用循环链表求解约瑟夫问题 约瑟夫问题的提法n个人围成一个圆圈 首先第s个人从1开始逐个顺时针报数 报到第m个人 令其出列 然后再从下一个人开始 从1顺时针报数 报到第m个人 再令其出列 如此下去 直到圆圈中只剩一个人为止 此人即为优胜者 LabI 84 voidCreaList NodeType constint 创建单向循环链表 voidCreaList NodeType 出队情况打印 85 2 3 3双向链表 DoublyLinkedList 逆向扫描单链表困难双向链表是指在前驱和后继方向都能遍历的线性链表双向链表结点结构 86 带表头结点的双向循环链表 结点指向p p lLink rLink p rLink lLink 87 双向循环链表的插入算法 非空表 newnode lLink current newnode rLink current rLink current rLink newnode current current rLink current rLink lLink current 88 双向循环链表的插入算法 空表 newnode lLink current newnode rLink current rLink first current rLink newnode current current rLink current rLink lLink current first lLink current 89 P37 38带头节点的链表类型定义 typedefstructLNode intdata LNode next Position typedefstruct LNode Head Tail intlen LinkList 90 第3章栈和队列 栈和队列也是线性表 只是其基本操作有一定的限制栈 Stack 只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶 top 另一端称为栈底 bottom 后进先出 LIFO 91 列车调度若进站的六辆列车顺序如上所述 那么是否能够得到4312 3241 1423和1342的出站序列 92 ADTStack p45 栈的基本操作1 初始化操作InitStack 93 3 1 2栈的表示和实现 顺序栈 top 空栈 top top top top top a进栈 b进栈 a a b a b c d e e进栈 a b c d e f进栈溢出 a b d e e退栈 c base base base base base base 94 顺序栈的类型定义 defineSTACK INIT SIZE100 栈存储空间的初始分配量 defineSTACKINCREMENT10 栈存储空间的分配增量typedefstruct SElemType base 栈空间基址SElemType top 栈顶指针intstacksize 当前分配的栈空间大小 以sizeof SElemType 为单位 SqStack SqStacks 95 0 xAF000 xAF040 xAF080 xEF000 xEF040 xEF08 0 xEF000 xEF0C0 x0064a1a2a3 Sbasetopstacksize 96 顺序栈基本操作的算法 StatusInitStack Sq SqStack 97 0 xAF000 xAF040 xAF080 xEF000 xEF040 xEF08 0 xEF000 xEF000 x0064 Sbasetopstacksize 98 StatusDetroyStack Sq SqStack 99 StatusClearStack Sq SqStack 100 StatusPush SqStack 101 StatusPop SqStack 102 双栈共享一个栈空间 base0top0top1base1 0maxSize 1 V 103 栈的链式存储和实现 栈的链式存储结构称为链栈 它的运算是受限的单链表 插入和删除操作仅限制在表头位置上进行 无栈满问题 空间可扩充 typedefstructnode ElemTypedata node next LinkStack 104 3 2栈的应用举例 例1数制转换 十进制数到八进制数转换求解方法N Ndiv8 10 8 Nmod8N 十进制数 div 整除运算 mod 求余运算 1348 10 2 83 5 82 0 8 4 2504 8NNdiv8Nmod8134816841682102125202由低位到高位顺序产生八进制数的各个数位 但按从高位到低位的顺序输出 105 voidconversion InitStack S scanf d N 输入一个非负十进制整数while N N不等于零循环Push S N 8 N 8第一个余数进栈N N 8 整除运算 while StackEmpty S 输出栈中的八进制数位Pop S e Printf d e 106 例2括号匹配的检验 表达式中 或 等为正确的格式 或 或 均为不正确的格式算法读入表达式1 凡出现左括弧 则进栈 2 凡出现右括弧 首先检查栈是否空若栈空 则表明该 右括弧 多余 否则和栈顶元素比较 若相匹配 则 左括弧出栈 否则表明不匹配3 表达式检验结束时 若栈空 则表明表达式中匹配正确 否则表明 左括弧 有余 107 Statusmatching charexp while i length exp switchexp i case Push S exp i i break case if StackEmpty S 108 练习 设计一个算法 用栈的基本运算 判定一个字符串是否为对称字符串 abccba 若是 则返回1 否则返回0 109 例5表达式求值 表达式求值是程序设计语言编译的一个最基本的问题表达式的构成 操作数 运算符 分界符表达式的求值 5 6 1 2 4按照四则运算法则 上述表达式的计算过程为 5 6 1 2 4 5 6 3 4 5 18 4 23 4 19表达式中运算符的运算顺序为 如何确定运算符的运算顺序 110 运算符优先关系表 1 2 表明可以进行 1的运算 1退栈 运算 运算结果入栈 1 2 脱括号 读下一字符或表达式结束 111 算法思想 设定两栈 操作符栈OPTR 操作数栈OPND栈初始化 设操作数栈OPND为空 操作符栈OPTR的栈底元素为表达式起始符 依次读入字符 是操作数则入OPND栈 是操作符则要判断 if操作符栈顶元素 压入OPTR栈 112 相同运算符 先出现的比后出现的优先级高 先出现的运算符优先级低于 高于 后出现的运算符优先级高于 低于 优先权相等的仅有 和 作为表达式结束符 通常在表达式之前加一 使之成对 当出现 时 表明表达式求值结束 的优先级最低 113 表达式求值示意图 5 6 1 2 4 5 6 1 2 3 18 23 4 19 5 读入表达式过程 6 1 2 4 19 1 2 3 6 3 18 5 18 23 23 4 19 114 3 3递归 以下三种情况常常用到递归方法 定义是递归的数据结构是递归的二叉树 广义表 单链表一个结点 它的指针域为NULL 是一个单链表 一个结点 它的指针域指向单链表 仍是一个单链表问题的解法是递归的汉诺塔 八皇后 115 递归思想 分治法 递归算法的设计1 将问题用递归的方式描述 定义 2 根据问题的递归描述 定义 编写递归算法问题的递归定义递归定义包括两项基本项 终止项 描述递归过程的终结状态 直接求解 递归项 将问题分解为与原问题性质相同 但规模较小的问题 问题原始状态到终结状态的转化 116 递归实质复杂问题分解为相对简单且解法相同或类似的子问题 解决这些子问题 原问题即终获解决递归函数设计注意事项 函数说明 严格定义函数的功能和接口 使得原问题和子问题接口一致对每次递归调用都简而视之 切忌想得太深太远 117 链表中寻找给定值的结点并打印 voidPrint ListNode f int 118 汉诺塔 TowerofHanoi 问题 解法 如果n 1 则将这一个盘子直接从A柱移到C柱上 否则 执行以下三步 用C柱做过渡 将A柱上的 n 1 个盘子移到B柱上 将A柱上最后一个盘子直接移到C柱上 用A柱做过渡 将B柱上的 n 1 个盘子移到C柱上 119 voidHanoi intn charS charM charD 解决汉诺塔问题的算法if n 1 cout move S to D endl else Hanoi n 1 S D M cout move S to D endl Hanoi n 1 M S D 120 递归过程与递归工作栈 递归过程在实现时 需要自己调用自己 层层向下递归 退出时的次序正好相反 递归调用n n 1 n 2 1 0 1返回次序主程序第一次调用递归过程为外部调用 递归过程每次递归调用自己为内部调用 它们返回调用它的过程的地址不同 121 递归工作栈 每一次递归调用时 需要为过程中使用的参数 局部变量等另外分配存储空间 每层递归调用需分配的空间形成递归工作记录 按后进先出的栈组织 局部变量返回地址参数 活动记录框架 递归工作记录 122 函数递归时的活动记录 y fx intfx returnx 调用块 函数块 123 longFactorial longn inttemp if n 0 return1 elsetemp n Factorial n 1 RetLoc2returntemp voidmain intn n Factorial 4 RetLoc1 124 求解阶乘n 的过程 主程序main fact 4 参数4计算4 fact 3 返回24 参数3计算3 fact 2 返回6 参数2计算2 fact 1 返回2 参数1计算1 fact 0 返回1 参数0直接定值 1返回1 参数传递 结果返回 递归调用 回归求值 125 递归过程简洁 易编 易懂递归过程效率低 重复计算多改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程 126 计算斐波那契数列的函数Fib n 如F0 0 F1 1 F2 1 F3 2 F4 3 F5 5 求解斐波那契数列的递归算法longFib longn if n 1 returnn elsereturnFib n 1 Fib n 2 127 斐波那契数列的递归调用树 调用次数NumCall k 2 Fib k 1 1 Fib 1 Fib 0 Fib 1 Fib 2 Fib 3 Fib 4 Fib 1 Fib 0 Fib 2 Fib 1 Fib 0 Fib 1 Fib 2 Fib 3 Fib 5 128 单向递归用迭代法实现 longFibIter longn if n 1 returnn longtwoback 0 oneback 1 Current for inti 2 i n i Current twoback oneback twoback oneback oneback Current returnCurrent 129 递归与回溯 迷宫问题P51非递归算法 略 小型迷宫 小型迷宫的数据intsec 常用于搜索过程 130 迷宫问题 include include includestructIntersection 交通路口结构定义intleft intforward intright intMazeSize intEXIT Intersection intsec 地图 交通路口结构数组 voidmain Maze MazeMap dat TraverseMaze 1 131 voidMaze char filename 从文件filename中读取各路口和出口的数据 生成地图 ifstreamfin fin open filename ios in ios nocreate ios binary if fin cout MazeSize 输入迷宫路口数intsec newIntersection MazeSize 1 for inti 1 i intsec i left intsec i forward intsec i right fin EXIT 输入迷宫出口fin close 132 迷宫漫游与求解算法 intTraverseMaze intCurrentPos if CurrentPos 0 路口从1开始if CurrentPos EXIT 出口处理 cout CurrentPos return1 else 递归向左搜寻可行途径if TraverseMaze intsec CurrentPos left cout CurrentPos return1 else 递归向前搜寻可行途径if TraverseMaze intsec CurrentPos forward cout CurrentPos return1 else 递归向右搜寻可行途径if TraverseMaze intsec CurrentPos right cout CurrentPos return1 return0 133 练习 A n 为整数数组 写出下列递归算法 1 求数组A中的最大整数 2 求n个整数的和 3 求n个整数的平均值 intMaxKey intn if n 1 returnA 0 inttemp MaxKey n 1 if A n 1 temp returnA n 1 elsereturntemp intSum intn if n 1 returnA 0 elsereturnA n 1 Sum n 1 floatAverage intn if n 1 return float A 0 elsereturn float A n 1 n 1 Average n 1 n 134 n皇后问题 在n行n列的国际象棋棋盘上 若两个皇后位于同一行 同一列 同一对角线上 则称为它们为互相攻击 n皇后问题是指找到这n个皇后的互不攻击的布局 135 1 主对角线3 主对角线5 主对角线 0 次对角线2 次对角线4 次对角线6 次对角线 1 次对角线3 次对角线5 次对角线 0 主对角线2 主对角线4 主对角线6 主对角线 0123 0123 k i j k n i j 1 136 皇后问题解题思路 安放第i行皇后时 需要在列的方向从0到n 1试探 j 0 n 1 在第j列安放一个皇后 如果在列 主对角线 次对角线方向有其它皇后 则出现攻击 撤消在第j列安放的皇后 如果没有出现攻击 在第j列安放的皇后不动 递归安放第i 1行皇后 137 设置4个数组col n col j 标识第j列是否安放了皇后md 2n 1 md k 标识第k条主对角线是否安放了皇后sd 2n 1 sd k 标识第k条次对角线是否安放了皇后q n q i 记录第i行皇后在第几列 138 voidQueen inti for intj 0 j n j if 第i行第j列没有攻击 在第i行第j列安放皇后 if i n 1 输出一个布局 elseQueen i 1 撤消第i行第j列的皇后 139 皇后算法求精 voidQueen inti for intj 0 j n j if col j 撤消第i行第j列的皇后 140 3 4队列 Queue 定义队列是只允许在一端删除 在另一端插入的线性表允许删除的一端叫做队头 front 允许插入的一端叫做队尾 rear 特性先进先出 FIFO FirstInFirstOut 141 ADTQueue p61 1 初始化操作InitQueue Q 功能 构造一个空队列Q 2 销毁操作DestroyQueue Q 功能 销毁已存在队列Q 3 置空操作ClearQueue Q 功能 将队列Q置为空队列 4 判空操作QueueEmpty Q 功能 若队列Q为空 则返回True 否则返回False 5 取队头元素操作GetHead Q e 功能 取队头元素 并用e返回 6 入队操作EnQueue Q e 功能 将元素e插入Q的队尾 7 出队操作DeQueue Q e 功能 若队列不空 则删除Q的队头元素 用e返回其值 并返回OK 否则返回ERROR 142 队列的链接表示 链式队列 typedefstructQNode QElemTypedata QNode next QueuePtr typedefstruct QueuePtrfront QueuePtrrear LinkQueue 143 队列的顺序表示 循环队列 用一组地址连续的存储单元依次存放从队列头到队列尾的元素 附设两个指针front和rear初始化建空队列时 令front rear 0插入新的队列尾元素时 尾指针增1 删除队列头元素时 头指针增1 头指针始终指向队头元素 而尾指针始终指向队尾元素之后 144 假溢出 现象将队列元素存放数组首尾相接 形成循环队列 145 队头 队尾指针加1时从maxSize 1直接进到0 可用语言的取模 余数 运算实现队头指针进1 front front 1 maxSize 队尾指针进1 rear rear 1 maxSize 队列初始化 front rear 0 队空条件 front rear 队满条件 rear 1 maxSize front 146 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front rear A A B C rear rear 空队列 A进队 B C进队 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 A退队 B退队 0 1 2 3 4 5 6 7 D E F G H I进队 front B C rear A front B C rear C rear D E F G H front I 147 循环队列的顺序存储结构 defineMAXQSIZE100 最大队列长度typedefstruct QElemType base 初始化的动态分配存储空间intfront 头指针 若队列不空 指向队列头元素intrear 尾指针 若队列不空 指向队列尾元素的下一个位置 SqQueue 148 第4章串 串是一种特殊的线性表 它是由零个或多个字符组成的有限序列 一般记作s a1 a2 a3 an 其中s 串名 a1 a2 a3 an 串值串的应用非常广泛 许多高级语言中都把串的作为基本数据类型 在事务处理程序中 姓名 地址 名称等可作为字符串处理 文本文件中的每一行字符也作为字符串处理 149 串的有关术语子串子串的位置串相等ADTString p71 150 4 2串的表示和实现 定长顺序存储结构以一组地址连续的存储单元存放串值字符序列 其类型说明如下 PASCAL串C串定长顺序存储结构下的串操作 p73 75 defineMAXSTRLEN255typedefunsignedcharSString MAXSTRLEN 1 151 堆分配存储表示以一组地址连续的存储单元存放串值字符序列 其存储空间是在程序执行过程中动态申请