2008级本科数据结构理论教案1章.doc

数据结构 教案 黄石理工学院 计算机学院 1 第一章第一章 绪论绪论 一 教学目标一 教学目标 了解数据结构讨论的范畴 掌握数据与数据结构 数据类型 抽象数据类型的基本概念 二 教学要求二 教学要求 1 了解数据结构的研究目的和研究内容 2 掌握数据结构中的重要概念和术语 3 掌握算法设计的基本要求以及算法复杂度的分析和计算方法 三 教学内容提要三 教学内容提要 1 基本概念 理解什么是数据 数据对象 数据元素 数据结构 数据的逻辑结构与物理结 构 逻辑结构与物理结构间的关系 2 面向对象概念 理解什么是数据类型 抽象数据类型 数据抽象和信息隐蔽原则 了解什 么是面向对象 由于目前关于这个问题有许多说法 我们采用了一种最流行的说法 即 Coad 与 Yourdon 给出的定义 面向对象 对象 类 继承 通信 3 数据结构的抽象层次 理解用对象类表示的各种数据结构 4 算法与算法分析 理解算法的定义 算法的特性 算法的时间代价 算法的空间代价 四 教学重点 难点及解决方法四 教学重点 难点及解决方法 1 教学重点及难点 本章讨论的都是一些基本概念 重点在于了解有关数据结构的各个名词 和术语的含义 以及语句频度和时间复杂度 空间复杂度的估算 2 解决方法 通过例一 例二及例三归纳总结三种主要的数据结构 讨论可变聚合类型与多 形数据类型的区别 五 课时安排五 课时安排 4 学时 六 教学内容六 教学内容 1 1 概念和术语 概念和术语 数据 是能输入到计算机中并能被计算机程序处理的符号的总称 数据元素 是数据的基本单位 它在计算机处理和程序设计中通常作为一个整体进行考虑和 处理 一个数据元素可由若干数据项组成 数据对象 是具有相同特征的数据元素的集合 是数据的一个子集 数据结构 是数据元素的组织形式 或数据元素相互之间存在一种或多种特定关系的集合 数据的逻辑结构 是指数据结构中数据元素之间的逻辑关系 数据的存储结构 是数据的逻辑结构在计算机内存中的存储方式 又称物理结构 数据类型 是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合 抽象数据类型 是指一个数学模型以及在该模型上定义的一套运算规则的集合 数据结构 教案 黄石理工学院 计算机学院 2 算法 建立在数据结构基础上的 为解决问题而采取的步骤和方法 2 2 逻辑结构的四种基本形态 逻辑结构的四种基本形态 根据数据元素之间关系的不同特征 通常有下列四类基本结构 1 集合 结构中的数据元素间除了 同属于一个集合 的关系外 别无其它关系 2 线性结构 结构中的数据元素之间存在一个对一个的关系 3 树型结构 结构中的数据元素之间存在一个对多个的关系 4 图型结构或网状结构 结构中的数据元素之间存在多个对多个的关系 3 3 数据存储结构的基本组织方式 数据存储结构的基本组织方式 数据存储结构有顺序和链式两种方式 1 顺序存储结构的特点 要借助数据元素在存储器中的相应位置来体现数据元素相互间的 逻辑关系 常用高级编程语言中的 一维数组 来描述或实现 2 链式存储结构的特点 通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关 系 通常用链表来实现 在顺序存储结构的基础上 又可延伸变化出另外两种存储结构 即索引存储和散列存储 1 索引存储就是在数据文件的基础上增加了一个索引表文件 通过索引表建立索引 可以 把一个顺序表分成几个顺序子表 其目的是在查询时提高查找效率 避免盲目查找 2 散列存储就是通过数据元素与存储地址之间建立起某种映射关系 使每个数据元素与每 一个存储地址之间尽量达到一一对应的目的 这样 查找时同样可大大提高效率 4 4 数据结构的研究内容 数据结构的研究内容 数据结构的核心研究内容包括三个方面 数据的逻辑结构 存储结构以及相应的基本操作运 算的定义和实现 5 5 算法的五个重要特征 算法的五个重要特征 1 有穷性 一个算法必须保证在执行有限步骤之后结束 而不是无限的 2 确定性 算法中每一条指令必须有明确的含义 而不能是模棱两可的 3 可行性 每一个操作步骤都必须在有限的时间内完成 4 输入 一个算法可以有一个或多个输入 也可以没有输入 5 输出 一个算法可以有一个或多个输出 没有输出的算法是没有实际意义的 6 6 算法的评价标准 算法的评价标准 1 正确性 2 易读性 3 高效性 4 可维护性 7 7 算法分析的目的 算法分析的目的 算法分析主要是指分析算法的效率 算法效率的度量主要从两个方面 算法的运行时间和算 法所需的存储空间 分析的目的是通过考察算法的时间和空间效率 以求改进算法或对不同的算法 数据结构 教案 黄石理工学院 计算机学院 3 进行比较 一般情况下 鉴于运算空间 内存 较为充足 所以把算法的时间复杂度分析作为重点 8 8 算法的时间复杂度分析 算法的时间复杂度分析 1 算法运算时间的度量的两种方法 事后统计的方法和事前分析估算的方法 2 算法运行时间的分析规则 通常把一个程序的运行时间定义为一个 T n 其中 n 是该程序输入数据的规模 而不是某 一个具体的输入 T n 的单位是不确定的 一般把它看成在一个特定计算机上执行的指令条数 通 常记作 T n O f n 其中 f n 表示数据输入规模 常见的算法时间复杂度的形式按性能降序的排列如下 O 1 O n 2 log O n O n n 2 log O 2 n O 3 n O n 2 例 1 1 分析以下程序段的时间复杂度 for i 0 i n i for j 0 j m j A i j 0 解 该程序段的时间复杂度为 O m n 例 1 2 分析以下程序段的时间复杂度 i s 0 while s n i s i 解 语句 为赋值语句 其执行次数为 1 次 所以其时间复杂度为 O 1 语句 和语句 构 成 while 循环语句的循环体 它们的执行次数由循环控制条件中 s 与 n 的值确定 假定循环重复执 行 x 次后结束 则语句 和语句 各重复执行了 x 次 其时间复杂度按线性累加规则为 O x 此 时 s 与 n 满足关系式 s n 而 s 1 2 3 x 所以有 1 2 3 x n 可以推出 x n n 2 4 1 2 1 2 811 x 与 n 之间满足 x f n 所以循环体的时间复杂度为 O n 语句 与循环体由线性累加 规则得到该程序段的时间复杂度为 O n 例 1 3 分析以下程序段的时间复杂度 i 1 while i n i 2 i 解 其中语句 的执行次数是 1 设语句 的执行次数为 f n 则有 n nf 2 数据结构 教案 黄石理工学院 计算机学院 4 得 T n O n 2 log 例 1 4 有如下递归函数 fact n 分析其时间复杂度 fact int n if nmaxlen 1 printf overflow exit 0 i 0 j 0 i 和 j 分别作为扫描顺序表 A 和 B 的指针 k 0 k 指示顺序表 C 中当前位置 while i m i k else C elem k B elem j j k while i m 表 B 已结束 表 A 没有结束 链入表 A 的剩余部分 C elem k A elem i i k while jnext q next head head q 图 2 1 单链表逆置示意图 示示 图 head head qp head 有 序 有 序 子 序 列 R l m 有 序 子 序 列 R m 1 n q a 单链表初始状态 示示 图 b 第三个结点逆置 示示 图 数据结构与算法 教案 黄石理工学院 计算机学院 8 例 2 3 假设有一个循环链表的长度大于 1 且表中既无头结点也无头指针 已知 p 为指向链表中某结 点的指针 设计在链表中删除 p 所指结点的前趋结点的算法 解 解 可引入一个指针 q 当 q next p 时 说明此时 q 所指的结点为 p 所指结点的前趋结点 从而可 得算法如下 void delete LinkList p 在链表中删除 p 所指结点的前趋结点 LinkList q t q p while q next next p q next 不是 p 的前趋结点 q q next t q next t 指向要删除结点 q next p 删除 t 结点 free t 例 2 4 试设计实现删除单链表中值相同的多余结点的算法 解 解 该例可以这样考虑 先取开始结点的值 将它与其后的所有结点值一一比较 发现相同的就删 除掉 然后再取第二结点的值 重复上述过程直到最后一个结点 设单链表 其类型为 LinkList 的头指针 head 指向头结点 则可按下列步骤执行 首先 用一个指针 p 指向单链表中第一个表结点 然后用另一个指针 q 查找链表中其余结点元素 由于是单链表 故结束条件为 p NULL 同时让指针 s 指向 q 所指结点的前趋结点 当查找到结点具有 q data p data 时删除 q 所指的结点 然后再修改 q 直到 q 为空 然后使 p 指针后移 即 p p next 重复进行 直到 p 为空时为止 算法描述如下 del LinkList head 删除单链表中值相同的多余结点 LinkList p s q p head next while p NULL s 指向要删除结点的前趋 q p next while q NULL if q data p data 查找值相同的结点并删除 s next q next free q q s next else s q q q next 数据结构与算法 教案 黄石理工学院 计算机学院 9 p p next 七 本章小结七 本章小结 在这一章我们向大家介绍了线性表的抽象数据类型的定义以及它的两种存储结构的实现 顺序表是线性表的顺序存储结构的一种别称 它的特点是以 存储位置相邻 表示两个元素之间的前驱 后继关系 因此 顺序表的优点是可以随机存取表中任意一个元素 其缺点是每作一次插入或删除操作 时 平均来说必须移动表中一半元素 常应用于主要是为查询而很少作插入和删除操作 表长变化不大 的线性表 链表是线性表的链式存储结构的别称 它的特点是以 指针 指示后继元素 因此线性表的元素可以存 储在存储器中任意一组存储单元中 它的优点是便于进行插入和删除操作 但不能进行随机存取 每个 元素的存储位置都存放在其前驱元素的指针域中 为取得表中任意一个数据元素都必须从第一个数据元 素起查询 由于它是一种动态分配的结构 结点的存储空间可以随用随取 并在删除结点时随时释放 以便系统资源更有效地被利用 这对编制大型软件非常重要 作为一个程序员在编制程序时必须养成这 种习惯 由于线性表是一种应用很广的数据结构 链表的操作又很灵活 在自己实现链表类时 正如课程中所 述 应该为链表结构设置合适的数据成员和恰当的操作接口 以便使每个基本操作的时间复杂度在尽可 能低的级别上 八 作业八 作业 复习第二章 预习第三章 作业题 2 11 2 21 2 19 2 22 2 24 2 27 2 28 2 38 数据结构与算法 教案 黄石理工学院 计算机学院 10 第三章第三章 栈与队列栈与队列 一 教学目标一 教学目标 对栈 队列 优先级队列等限制存取点的表的掌握程度和应用它们解决应用问题的能力 二 教学要求二 教学要求 掌握栈的定义 特性和栈的抽象数据类型 栈的顺序表示 链表表示以及相应操作的实现 特 别注意栈空和栈满的条件 了解在表达式计算时栈是如何使用的 重点了解用后缀表示计算表达式及中缀表示改后缀表示 的方法和算法思路 掌握队列的定义 特性和队列的抽象数据类型 队列的顺序表示 链表表示以及相应操作的实 现 特别是循环队列中队头与队尾指针的变化情况 三 教学内容提要三 教学内容提要 1 栈 栈的特性 栈的基本运算 2 栈的应用 用后缀表示计算表达式 中缀表示改后缀表示 3 队列 队列的特性 队列的基本运算 循环队列的概念 循环队列队空 队满的条件及队 列长度的公式 循环队列的相关算法 4 双向队列 双向队列的插入与删除算法 5 优先级队列 优先级队列的插入与删除算法 四 教学重点 难点及解决方法四 教学重点 难点及解决方法 1 教学重点及难点 栈和队列是在程序设计中被广泛使用的两种线性数据结构 因此本章的 学习重点在于掌握这两种结构的特点 以便能在应用问题中正确使用 2 解决方法 讨论队列与栈的相同点及不同点 五 课时安排五 课时安排 4 学时 六 教学内容六 教学内容 从数据结构数据结构的角度看 它们和线性表相同 从数据类型数据类型的角度看 它们和线性表不同 线性表线性表 栈栈 队列队列 Insert L i i x Insert S n 1n 1 x Insert Q n 1n 1 x 1 1 i i n 1 n 1 Delete L i i Delete S n n Delete Q 1 1 1 1 i i n n 1 1 栈栈 栈 Stack 是限定仅在表的一端进行插入或删除操作的线性表 通常把允许插入和删除操作 的一端称为栈顶 Top 而另一端称为栈底 Bottom 表为空时称为空栈 在栈上的主要运算是 数据结构与算法 教案 黄石理工学院 计算机学院 11 入栈和出栈 栈中元素如果按 a1 a2 an的顺序进栈 则出栈顺序为 an an 1 a1 因此 栈又称为 后进先出 Last In First Out 的线性表 简称 LIFO 表 同线性表相似 栈也有顺序栈和链栈两种存储结构 顺序栈易产生 上溢 现象 而链栈不容 易产生 另外 注意对栈的操作只能在栈顶进行 2 2 队列 队列 队列 Queue 是限定只能在表的一端进行插入 在表的另一端进行删除的线性表 通常把允 许插入的一端称为队尾 rear 允许删除的一端称为队头 front 队列中元素如果按 a1 a2 an的顺序进队 则出队的顺序仍为 a1 a2 an 因此 队列又称为 先进先出 First In First Out 的线性表 简称 FIFO 表 队列也有顺序队列和链队列两种存储结构 在顺序队列中 为避免 假满 现象 一般采用循 环队列 即首尾相接 链队列会因为队满而产生 上溢 现象 例一 例一 数制转换数制转换 十进制数 N 和其他 d 进制数的转换是计算机实现计算的基本问题 其解决方法很多 其中一个 简单算法基于下列原理 N N N N divdiv d dd d N N modmod d d 其中 div 为整除运算 mod 为求余运算 例如 例如 1348 10 2504 8 其运算过程如下 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 假设现要编制一个满足下列要求的程序 对于输入的任意一个非负十进制整数 打印输出与其 等值的八进制数 由于上述计算过程是从低位到高位顺序产生八进制数的各个数位 而打印输出 一般来说应从高位到低位进行 恰好和计算过程相反 因此 若将计算过程中得到的八进制数的各 位顺序进栈 则按出栈序列打印输出的即为与输入对应的八进制数 voidvoid conversion 对于输入的任意一个非负十进制整数 打印输出 数据结构与算法 教案 黄石理工学院 计算机学院 12 与其等值的八进制数 InitStack S 构造空栈 scanfscanf d N whilewhile N Push S N 8 N N 8 whilewhile StackEmpty S Pop S e printfprintf d e conversion 这是利用栈的后进先出特性的最简单的例子 在这个例子中 栈操作的序列是直线式的 即先 一味地入栈 然后一味地出栈 也许 有的读者会提出疑问 用数组直接实现不也很简单吗 仔细 分析上述算法不难看出 栈的引入简化了程序设计的问题 划分了不同的关注层次 使思考范围缩 小了 而用数组不仅掩盖了问题的本质 还要分散精力去考虑数组下标增减等细节问题 例二 例二 括号匹配的检验括号匹配的检验 假设表达式中允许包含两种括号 圆括号和方括号 其嵌套的顺序随意 即 或 等为正确的格式 或 或 均为不正确的格式 检验括号 是否匹配的方法可用 期待的急迫程度 这个概念来描述 例如考虑下列括号序列 1 2 3 4 5 6 7 8 分析可能出现的不匹配的情况 1 到来的右括弧非是所 期待 的 2 到来的是 不速之客 3 直到结束 也没有到来所 期待 的 status matching string 数据结构与算法 教案 黄石理工学院 计算机学院 13 whilewhile i length exp i break break casecase ifif NOTNOT StackEmpty S i elseelse state 0 break break ifif state 例三 行编辑程序问题例三 行编辑程序问题 一个简单的行编辑程序的功能是 一个简单的行编辑程序的功能是 接受用户从终端输入的程序或数据 并存入用户的数据区 每接受一个字符即存入用户数据区每接受一个字符即存入用户数据区 不恰当 较好的做法是 设立一个输入缓冲区 用以接受用户输入的一行字符 然后逐行存入用户数设立一个输入缓冲区 用以接受用户输入的一行字符 然后逐行存入用户数 据区 允许用户输入出差错 并在发现有误时可以及时更正 据区 允许用户输入出差错 并在发现有误时可以及时更正 例如 可用一个退格符 表示前一个字符无效 可用一个退行符 表示当前行中的字 符均无效 例如 假设从终端接受了这样两行字符 whwhli ililr e e s s outcha putcharputchar s 则实际有效的是下列两行 whilewhile s putcharputchar s voidvoid LineEdit 利用字符栈 S 从终端接收一行并传送至调用过程 的数据区 InitStack S 构造空栈 S 数据结构与算法 教案 黄石理工学院 计算机学院 14 ch getchar 从终端接收第一个字符 whilewhile ch EOFEOF EOF 为全文结束符 whilewhile ch EOFEOF breakbreak 仅当栈非空时退栈 casecase ClearStack S breakbreak 重置 S 为空栈 defaultdefault Push S ch breakbreak 有效字符进栈 未考虑栈满情形 ch getchar 从终端接收下一个字符 将从栈底到栈顶的字符传送至调用过程的数据区 ClearStack S 重置 S 为空栈 ifif ch EOFEOF ch getchar DestroyStack S 例四 例四 迷宫求解迷宫求解 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题 由于计算机解迷宫时 通常 用的是 穷举求解穷举求解 的方法 即从入口出发 顺某一方向向前探索 若能走通 则继续往前走 否 则沿原路退回 换一个方向再继续探索 直至所有可能的通路都探索到为止 为了保证在任何位置 上都能沿原路退回 显然需要用一个后进先出的结构来保存从入口到当前位置的路径需要用一个后进先出的结构来保存从入口到当前位置的路径 因此 在求 迷宫通路的算法中应用 栈 也就是自然而然的事了 假设迷宫如下图所示 数据结构与算法 教案 黄石理工学院 计算机学院 15 假设 当前位置当前位置 指的是 在搜索过程中某一时刻所在图中某个方块位置在搜索过程中某一时刻所在图中某个方块位置 则求迷宫中一条 路径的算法的基本思想基本思想是 若当前位置若当前位置 可通可通 则纳入 则纳入 当前路径当前路径 并继续朝 并继续朝 下一位置下一位置 探索 探索 即切换即切换 下一位置下一位置 为为 当前位置当前位置 如此重复直至到达出口 若当前位置若当前位置 不可通不可通 则应顺着 则应顺着 来向来向 退回到退回到 前一通道块前一通道块 然后朝着除 然后朝着除 来向来向 之外的其他方向继续探索 若该通道块的四之外的其他方向继续探索 若该通道块的四 周四个方块均周四个方块均 不可通不可通 则应从 则应从 当前路径当前路径 上删除该通道块上删除该通道块 所谓 下一位置下一位置 指的是 当前当前 位置位置 四周四个方向 东 南 西 北 上相邻的方块四周四个方向 东 南 西 北 上相邻的方块 假设以栈栈 S S 记录记录 当前路径当前路径 则栈顶栈顶中 存放的是存放的是 当前路径上最后一个通道块当前路径上最后一个通道块 由此 纳入路径纳入路径 的操作即为的操作即为 当前位置入栈当前位置入栈 从从 当前路径上删除前一通道块当前路径上删除前一通道块 的操作即为的操作即为 出栈出栈 求迷宫中一条从入口到出口的路径的算法可简单描述如下 设定当前位置的初值为入口位置 dodo 若若当前位置可通 则 则 将当前位置插入栈顶 纳入路径 若若该位置是出口位置 则则结束 求得路径存放在栈中 否则否则切换当前位置的东邻方块为新的当前位置 否则否则 若若栈不空且栈顶位置尚有其他方向未被探索 则则设定新的当前位置为 沿顺时针方向旋转 找到的栈顶位置的下一相邻块 若若栈不空但栈顶位置的四周均不可通 则 则 删去栈顶位置 从路径中删去该通道块 若若栈不空 则则重新测试新的栈顶位置 直至直至找到一个可通的相邻块或出栈至栈空 whilewhile 栈不空 栈不空 在此 尚需说明一点的是 所谓当前位置可通可通 指的是未曾走到过的通道块未曾走到过的通道块 即要求该方块位 置不仅是通道块 而且既不在当前路径上 否则所求路径就不是简单路径 也不是曾经纳入过路 径后又从路径上删除的通道块 否则只能在死胡同内转圈 数据结构与算法 教案 黄石理工学院 计算机学院 16 typedeftypedef structstruct intint ord 通道块在路径上的 序号 PosType seat 通道块在迷宫中的 坐标位置 intint di 从此通道块走向下一通道块的 方向 SElemType 栈的元素类型 StatusStatus MazePath MazeType maze PosType start PosType end 若迷宫 maze 中从入口 start 到出口 end 的通道 则求得一条存放在栈中 从栈底到栈顶 并返回 TRUETRUE 否则返回 FALSEFALSE InitStack S curpos start 设定 当前位置 为 入口位置 curstep 1 探索第一步 dodo ifif Pass curpos 当前位置可以通过 即是未曾走到过的通道块 FootPrint curpos 留下足迹 e curstep curpos 1 Push S e 加入路径 ifif curpos end returnreturn TRUETRUE 到达终点 出口 curpos NextPos curpos 1 下一位置是当前位置的东邻 curstep 探索下一步 elseelse 当前位置不能通过 ifif StackEmpty S Pop S e whilewhile e di 4 Pop S e 留下不能通过的标记 并退回一步 while ifif e di 4 数据结构与算法 教案 黄石理工学院 计算机学院 17 e di Push S e 换下一个方向探索 curpos NextPos curpos e di 设定当前位置是该新方向上的相邻块 if if else whilewhile StackEmpty S returnreturn FALSEFALSE MazePath 例五 例五 表达式求值表达式求值 限于二元运算符的表达式定义 表达式 操作数 运算符 操作数 操作数 简单变量 表达式 简单变量 标识符 无符号整数 在计算机中 表达式可以有三种不同的标识方法 设 Exp S1 OPOP S2 则称 OPOP S1 S2 为表达式的前缀表示法前缀表示法 称 S1 OPOP S2 为表达式的中缀表示法中缀表示法 称 S1 S2 OPOP 为表达式的后缀表示法后缀表示法 可见 它以运算符所在不同位置命名的 例如 ExpExp a b c d e f 前缀式 a b c d e f 中缀式 a b c d e f 后缀式 a b c d e f 结论结论 1 1 操作数之间的相对次序不变操作数之间的相对次序不变 2 2 运算符的相对次序不同运算符的相对次序不同 3 3 中缀式丢失了括弧信息 致使运算的次序不确定 4 4 前缀式的运算规则前缀式的运算规则为 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表 数据结构与算法 教案 黄石理工学院 计算机学院 18 达式达式 5 5 后缀式的运算规则后缀式的运算规则为 运算符在式中出现的顺序恰为表达式的运算顺序运算符在式中出现的顺序恰为表达式的运算顺序 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式 如何从后缀式求值 如何从后缀式求值 先找运算符 后找操作数先找运算符 后找操作数 如何从原表达式求得后缀式 如何从原表达式求得后缀式 分析 原表达式 和 后缀式 中的运算符 原表达式 a a b b c c d d e e f f 后缀式 a a b b c c d d e e f f 运算符 优先数 1 0 1 1 2 2 3 每个运算符的运算次序要由它之后的一个运算符来定 若当前运算符的优先数小 则暂不进行 否 则立即进行 表达式求值的规则 1 设立运算符栈栈和操作数栈栈 2 设表达式的结束符为 予设运算符栈的栈底为 3 若当前字符是操作数 则进操作数栈 4 若当前运算符的优先数高于栈顶运算符 则进栈 5 否则 退出栈顶运算符作相应运算 6 对它之前后的运算符起隔离作用 可视为自相应左括弧开始的表达式的结束符 算法描述如下 OperandType EvaluateExpression 算术表达式求值的算符优先算法 设 OPTR 和 OPND 分别为运算符栈和运算数栈 OP 为运算符集合 InitStack OPTR Push OPTR initStack OPND c getchar whilewhile c GetTop OPTR ifif In c OP Push OPND c c getchar 不是运算符则进栈 数据结构与算法 教案 黄石理工学院 计算机学院 19 elseelse switchswitch precede GetTop OPTR c casecase 退栈并将运算结果入栈 Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b breakbreak switch while returnreturn GetTop OPND EvaluateExpression 例六 实现递归例六 实现递归 在高级语言编制的程序中 调用函数与被调用函数之间的链接和信息交换必须通过栈例进行 当在一个函数的运行期间调用另一个函数时 在运行该被调用函数之前 需先完成三件事 1 将所有的实在参数 返回地址等信息传递给被调用函数保存 2 为被调用函数的局部变量分配存储区 3 将控制转移到被调用函数的入口 从被调用函数返回调用函数之前 应该完成 1 保存被调函数的计算结果 2 释放被调函数的数据区 3 依照被调函数保存的返回地址将控制转移到调用函数 多个函数嵌套调用的规则是 后调用先返回 此时的内存管理实行 栈式管理栈式管理 递归过程指向过程中占用的数据区 称之为递归工作栈递归工作栈 每一层的递归参数合成一个记录 称之为递归工作记录递归工作记录 数据结构与算法 教案 黄石理工学院 计算机学院 20 栈顶记录指示当前层的执行情况 称之为当前活动记录 栈顶指针 称之为当前环境指针 例如 voidvoid hanoi intint n charchar x charchar y charchar z 将塔座 x 上按直径由小到大且至上而下编号为 1 至 n 的 n 个圆盘按规则搬到塔座 z 上 y 可用作辅助塔座 1 1 2 2 ifif n 1 3 3 move x 1 z 将编号为 的圆盘从 x 移到 z 4 4 elseelse 5 5 hanoi n 1 x z y 将 x 上编号为 至 n 1 的圆 盘移到 y z 作辅助塔 6 6 move x n z 将编号为 n 的圆盘从 x 移到 z 7 7 hanoi n 1 y x z 将 y 上编号为 至 n 1 的圆盘 移到 z x 作辅助塔 8 8 9 9 七 本章小结七 本章小结 在这一章我们学习了栈和队列这两种抽象数据类型 在学习过程中大家已经了解到 栈和 队列都属线性结构 因此他们的存储结构和线性表非常类似 同时由于他们的基本操作要比线 性表简单得多 因此它们在相应的存储结构中实现的算法都比较简单 相信对大家来说都不是 难点 这一章的重点则在于栈和队列的应用 通过本章所举的例子学习分析应用问题的特点 在 算法中适时应用栈和队列 八 作业八 作业 复习第三章 预习第四章 作业题 3 15 3 18 3 28 3 29 3 31 数据结构与算法 教案 黄石理工学院 计算机学院 21 第四章第四章 串串 一 教学目标一 教学目标 了解串的定义 存储方式和常用的串运算 二 教学要求二 教学要求 掌握串类型的定义 串类型的基本概念 理解串定长顺序存储表示及各种算法 掌握堆分配存储的类型定义 理解堆分配存储串的算法 掌握串的块链存储表示定义 理解串的块链存储表示的算法 三 教学内容提要三 教学内容提要 1 串类型的定义及相关概念 长度 定串 子串 位置 相等 空格串等概念 2 串的抽象数据类型及串定位函数的实现 3 串定长顺序存储表示 串定长顺序存储表示的串连接运算算法 串定长顺序存储表示的求 子串运算算法 4 堆分配存储的类型定义 堆分配存储的类型的插入算法 5 串的块链存储表示定义 求子串位置的定位函数 四 教学重点 难点及解决方法四 教学重点 难点及解决方法 1 教学重点及难点 本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法 并学会利用这些基本操作来实现串的其它操作 本章的难点是理解实现串匹配的 KMP 算法的思想 但它不属本章学习的基本要求 更不是重点学习内容 2 解决方法 讨论实现串的堆分配存储表示的串各种操作 五 课时安排五 课时安排 2 学时 六 教学内容六 教学内容 串的逻辑结构和线性表极为相似 区别仅在于串的数据对象约束为字符集 然而 串的基本操 作和线性表有很大差别 在线性表的基本操作中 大多以 单个元素 作为操作对象 如 在线性 表中查找某个元素 求取某个元素 在某个位置上插入一个元素和删除一个元素等 而在串的基本 操作中 通常以 串的整体 作为操作对象 如 在串中查找某个子串 求取一个子串 在串的某 个位置上插入一个子串以及删除一个子串等 数据结构与算法 教案 黄石理工学院 计算机学院 22 1 1 概念和术语 概念和术语 串 String 或字符串 是由零个或多个字符组成的有限序列 一般记为 s a1a2 an n 0 其中 s 是串的名 用双引号括起来的字符序列是串的值 串的长度 串中字符的个数 n 子串和主串 串中任意个连续的字符组成的子序列称为该串的子串 包含子串的串相应地称 为主串 空串 不包含任何字符的串 表示为 空格串 由一个或多个空格字符组成的串 例如 2 串的基本操作 1 用串变量赋值 assign s t 和用串常量赋值 create s ss 2 判等函数equal s t 3 求长函数length s 4 连接函数concat s t 5 求子串函数substring s pos len 6 定位函数index s t 7 置换函数replace s t v 8 插入子串insert s pos t 9 删除子串delete s pos k 10 串的复制copy s t 例 3 1 已知字符串 a an apple b other hero c her 求 1 concat substr a 1 2 b 2 replace a substr a 5 1 c 3 index a c 和 index b c 解 1 返回值为 another hero 其中 substr a 1 2 的返回值为 an 2 返回值为 an aherherle 其中 sub a 5 1 的返回值为 p 3 返回值分别为 0 和 3 3 串的顺序存储结构 顺序串 串的顺序存储方式类似于线性表的顺序存储方式 其存储结构用 C 语言描述为 typedef struct strnode char data maxlen int len SeqString 定义顺序串类型 例 3 2 设定串采用顺序存储结构 写出对串 s1 和串 s2 比较大小的算法 串值大小按字典排序 升序 方式 返回值等于 1 0 和 1 分别表示 s1s2 数据结构与算法 教案 黄石理工学院 计算机学院 23 解 算法思想 1 比较 s1 和 s2 共同长度范围内的对应字符 若 s1 的字符 s2 的字符 返回 若 s1 的字符后者时 返回 1 前者 后者时 返回 1 算法描述如下 define MAXLEN 256 struct strnode char data MAXLEN int len SeqString 定义顺序串类型 int strcmp SeqString s1 SeqString s2 比较串 s1 和串 s2 的大小 int comlen if s1 len s2 len comlen s1 len 求出串 s1 和串 s2 的共同长度 else comlen s2 len for i 0 i comlen i 在共同长度内逐个字符比较 if s1 ch i s2 ch i return 1 s1s2 ch i return 1 s1 s2 if s1 ch i s2 ch i return 0 s1 s2 else if s1 ch i s2 ch i return 1 s1s2 4 串的链式存储结构 即链串或块链结构 使用链式存储结构的字符串 只要存储空间足够大 其长度没有任何限制 但逻辑上的连续性 不体现为物理上的邻接性 每个字符和一个指针域形成一个结点 结点间的关系由链指针实现 即 字符逻辑上的连续性由链指针描述 其存储结构用 C 语言描述为 typedef struct strnode 定义字符串的结点类型 char data struct strnode next LinkString 数据结构与算法 教案 黄石理工学院 计算机学院 24 5 串的模式匹配算法 这是串的一种重要操作 很多软件 若有 编辑编辑 菜单项的话 则其中必有 查找查找 子菜单 项 首先 回忆一下串匹配 查找 的定义 INDEXINDEX S S T T pos pos 初始条件 串 S 和 T 存在 T 是非空串 1 pos StrLength S 操作结果 若主串 S 中存在和串 T 值相同的子串 则返回它在主串 S 中第 pos 个字符之后第一次 出现的位置 否则函数值为 0 下面讨论以定长顺序结构表示串时的几种算法 一 一 简单算法简单算法 intint Index SString S SString T int pos 返回子串 T 在主串 S 中第 pos 个字符之后的位置 若不存在 则函数值为 0 其中 T 非空 1 pos StrLength S i pos j 1 whilewhile i S 0 elseelse returnreturn 0 Index 二 二 首尾匹配算法首尾匹配算法 先比较模式串的第一个字符 再比较模式串的最后一个字符 最后比较模式串中从第二个到 第 n 1 个字符 主串 a a b b a a b b c c a a b b c c a a a a a a b b c c b b a a a a b b c c 模式串 a a a a 2 次 a a a a a a 1 2 次 a a a a a a b b c c b b a a 2 5 次 a a a a a a a a 2 2 次 a a a a 2 次 a a b b c c b b a a 5 次 数据结构与算法 教案 黄石理工学院 计算机学院 25 intint Index FL SString S SString T int pos 返回子串 T 在主串 S 中第 pos 个字符之后的位置 若不存在 则函数值为 0 其中 T 非空 1 pos StrLength S sLength S 0 tLength T 0 i pos patStartChar T 1 patEndChar T tLength whilewhile i sLength tLength 1 ifif S i patStartChar i 重新查找匹配起始点 elseelse ifif S i tLength 1 patEndChar i 模式串的 尾字符 不匹配 重新查找匹配起始点 elseelse 检查中间字符的匹配情况 k 1 j 2 whilewhile j tLength j ifif j tLength returnreturn i elseelse i 重新开始下一次的匹配检测 returnreturn 0 三 三 KMP KMP D E Knuth V R Pratt J H Morris 算法算法 上述两种算法的时间复杂度为 O m n KMP 算法的时间复杂度可以达到 O m n 当 S i T j 时 已经得到的结果 S i j 1 i 1 T 1 j 1 若已知 T j k 1 j 1 T 1 k 1 则有 S i k 1 i 1 T 1 k 1 i s1 si j 1 si k 1 si 1 s si i 数据结构与算法 教案 黄石理工学院 计算机学院 26 t1 tj k 1 tj 1 t tj j t1 tk 1 t tk k 定义 定义 模式串的nextnext函数 intint Index KMP SString S SString T intint pos 利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后的位置的 KMP 算法 其中 T 非空 1 pos StrLength S i pos j 1 whilewhile i S 0 匹配成功 elseelse returnreturn 0 Index KMP 求next函数值的过程是一个递推过程 分析如下 已知 next 1 0 假设 next j k 又 T j T k 则 next j 1 k 1 若 T j T k 则需往前回朔 检查 T j T 这实际上也是一个匹配的过程 不同在于 主串和模式串是同一个串 voidvoid get next SString next 1 0 j 0 whilewhile i T 0 ifif j 0 T i T j i j next i j elseelse j next j 其它情况 且 时当 1 pp ppp jk1 Max k 1j 0 j 1 j1k j1 k21 next 数据结构与算法 教案 黄石理工学院 计算机学院 27 get next 还有一种特殊情况需要考虑 例如 S aaabaaabaaabaaabaaabaaabaaabaaabaaabaaab T aaaabaaaab next j 01234 nextval j 00004 voidvoid get nextval SString nextval 1 0 j 0 whilewhile i T 0 ifif j 0 T i T j i j ifif T i T j next i j elseelse nextval i nextval j elseelse j nextval j get nextval 七 本章小结七 本章小结 在这一章向读者介绍了串类型的定义及其实现方法 并重点讨论了串操作中最常用的 串定位 操作 又称模式匹配 的两个算法 串的两个显著特点是 其一 它的数据元素都是字符 因此它的存储结构和线性表有很大不同 其二 串的基本操作通常以 串的整体 作为操作对象 而不像线性表是以 数据元素 作为操作对象 串匹配 的简单算法 算法 4 6 其算法思想直截了当 简单易懂 适用于在一般的文档编辑 中应用 但在某些特殊情况 例如只有 0 和 1 两种字符构成的文本串中应用时效率就很低 KMP 算 法是它的一种改进方法 其特点是利用匹配过程中已经得到的主串和模式串对应字符之间 等与不 等 的信息以及 T 串本身具有的特性来决定之后进行的匹配过程 从而减少了简单算法中进行的 本 不必要再进行的 字符比较 八 作业八 作业 复习第四章 预习第五章 作业题 4 10 4 12 4 17 4 25 数据结构与算法 教案 黄石理工学院 计算机学院 28 第五章第五章 数组与广义表数组与广义表 一 教学目标一 教学目标 多维数组的结构特点和在内存中的两种顺序存储方式 矩阵和三角矩阵元素的存储 递归问题 求解方法的掌握以及对广义表的递归解法的掌握 及应用递归方法求解应用问题的能力 二 教学要求二 教学要求 理解数组类型的特点及其在高级编程语言中的存储表示和实现方法 并掌握数组在 以行为主 的存储表示中的地址计算方法 掌握特殊矩阵的存储压缩表示方法 理解稀疏矩阵的两类存储压缩方法的特点及其适用范围 领会以三元组表示稀疏矩阵时进行矩 阵运算所采用的处理方法 三 教学内容提要三 教学内容提要 数组的定义 数组的顺序表示与实现 n 维数组的数据元素存储位置的计算公式 特殊矩阵的压缩存储 稀疏矩阵的三元组顺序表 稀疏矩阵的三元组顺序表的求转置矩阵算法 实现 广义表的定义 广义表的存储结构 广义表长度 广义表深度 广义表表头 广义表表尾 递归 递归的定义 递归的数据结构 递归问题用递归过程求解 递归实现时栈的应用 四 教学重点 难点及解决方法四 教学重点 难点及解决方法 1 教学重点及难点 本章重点是学习数组类型的定义及其存储表示 如何对递归定义的数据 结构设计实现其操作的递归算法 2 解决方法 主要是了解数组类型的特点以及在高级编程语言中的实现方法 广义表本属线 性类型的数据结构 但由于广义表比数组更为复杂 它兼有 多层次 的特点 特别是它的存储表示 和操作的实现和树的操作极为类似 因此在本章的学习中应善于和第六章的内容相对照 反之通过 本章的学习恰好是对实现树操作的递归算法的复习和巩固 五 课时安排五 课时安排 4 学时 六 教学内容六 教学内容 1 1 多维数组的顺序存储结构 多维数组的顺序存储结构 对于多维数组 有两种存储方式 一是以行为主序 或先行后列 的顺序存放 如 BASIC PASCAL C 等程序设计语言中用的是 数据结构与算法 教案 黄石理工学院 计算机学院 2