算法-抽象数据型.pptVIP

数据结构与算法 主讲老师 刘斌Email nj liubin QQ 1263447339 课程简介 结构 实体 关系 把某些成份按一定的规律或方式组织在一起的实体或某些成分组织在一起的方式在这里 我们把实体看作数据算法是对特定问题求解方法和步骤的一种描述 大公因数的求解算法元二次方程的求解周长 圆面积方体的表面积和边长排序治 贪心 动态规划 数据结构 算法 程序 程序 为计算机解决问题编制的指令集 是按照事先设计的功能和性能要求执行的指令序列从程序设计的观点来看 信息的表示 数据结构 研究的问题信息的处理 算法 研究的问题了解计算机原理 掌握程序设计的必由之路 课程目标 学会怎样组织信息 以便支持高效的数据处理掌握常用的数据结构及其应用学会合理组织数据 有效地处理数据基本掌握算法的设计与分析方法提高程序设计能力学会分析和研究计算机处理的数据对象的特性 掌握常用数据结构内在的逻辑关系 在机内的存储表示 掌握常用数据结构上的运算操作的动态性质和执行算法 能够为实际应用选择适当的数据结构 存储结构和相应算法 初步掌握算法性能的分析方法 与计算机专业其他课程的关系 建议的学习方案 听课 思考 提问 讨论三人行 必我我师焉学而不思则罔 思而不学则殆不耻下问独学而无友则孤陋而寡闻上机纸上得来终觉浅 绝知此事要躬行听懂很容易 学会才是真 教材和参考书 教材 廖明宏等 数据结构与算法 第4版 高等教育 2007年11月 参考书 算法与数据结构 C语言描述 第2版 张乃孝主编 高等教育出版社 2006 1数据结构 C语言版 有配套习题集与习题解答 严蔚敏等 清华大学出版社数据结构算法与应用 C 语言描述 大量的习题 网上PDF格式 翻译教材 课程资源 北大计算机系课程资源 包含课程的视频 C 语言 成绩考核 总成绩 平时成绩 40 期末考试成绩 60 上机作业 一定要按时交 20 平时成绩40 随堂提问 考勤15 上机考勤5 期末考试成绩60 注重综合能力的考评 平时表现突出 上机能力较强的 如完成附加题 可以得到奖励加分 不超过5分 作业要求 上机作业程序编写程序调试运行结果网上提交 上机要求 上机环境VC 6 0要求认真准备 有备而来 严禁玩游戏 及时向老师反映问题 培养独立解决问题的能力 第一章绪论 1 1数据结构的研究对象1 2数据结构的发展概况1 3抽象数据型 ADT 1 4算法及其复杂性1 5逐步求精的程序设计方法1 6关于描述语言 1 1数据结构的研究对象 1 1 1基本概念和术语1 1 2四种基本的数据结构1 1 3数据结构的研究对象 1 1 1基本概念和术语 1 数据 数据是用于描述客观事物的数值 字符 以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合 其范围随着计算机技术的发展而不断发展 2 数据元素数据的基本单位是数据元素 在计算机程序中通常作为一个整体进行考虑和处理 3 数据项是数据的不可分割的最小单位 一个数据元素可由若干个数据项组成 4 数据对象性质相同的元素的集合叫做数据对象 1 1 1基本概念和术语 5 结点数据元素在机内的位串表示 即数据元素在计算机内的映象 6 域 字段当数据元素由若干个数据项组成时 位串中对应于各个数据项的子串称为域 字段 是数据元素中数据项在计算机中的映象 7 信息表计算机程序所作用的一组数据通常称为信息表 是数据对象在计算机中的映象 1 1 1基本概念和术语 8 数据结构数据结构指的是数据元素之间的相互关系 这种关系是抽象的 即并不涉及数据元素的具体内容 是数据元素及其相互间的关系的数学描述 9 逻辑结构和存储结构 1 逻辑结构数据结构中描述的是数据元素之间的抽象关系 逻辑关系 称为逻辑结构 2 存储结构 物理结构数据结构在计算机中的表示 映象 称为存储结构 物理结构 1 1 1基本概念和术语 3 数据元素之间的关系 逻辑结构 在计算机中有两种表示方法 顺序映象 表示 和非顺序映象 表示 从而导致两种不同的存储结构 顺序结构和链式结构 顺序映象 表示 的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系 非顺序映象 表示 的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系 1 1 2四种基本的逻辑结构 1 集合结构结构中的数据元素之间除了属于同一个集合的关系之外 别无其他关系 关系比较松散 可用其他结构来表示 2 线性结构结构中的数据元素之间存在一个对一个的关系 即线性关系 每个元素至多有一个直接前导和后继 3 树型结构结构中的数据元素之间存在一个对多个的关系 即层次关系 即每一层上的元素可能与下层的多个元素相关 而至多与上层的一个元素相关 1 1 2四种基本的逻辑结构 4 网状 图型结构结构中的数据元素之间存在多个对多个的关系 即任意关系 任何元素之间都可能有关系 一般将逻辑结构分为线性结构 2 和非线性结构 1 3 4 两种 结构中的数据元素之间存在多个对多个的关系 即任意关系 任何元素之间都可能有关系 1 1 3数据结构的研究对象 1 数据对象的结构形式 各种数据结构的性质 逻辑结构 2 数据对象和关系在计算机中的表示 物理结构 存储结构 3 数据结构上定义的基本操作 算法 4 算法的效率 5 数据结构的应用 如数据分类 检索 1 2数据结构的发展概况 1 程序设计方法学的发展极大地促进了数据结构的发展 1 计算机科学及其应用的发展使数据结构成为独立学科 2 以数据为中心的程序设计方法推动了数据结构的发展 面向过程的程序设计的特点是以程序为中心 侧重于建立程序 程序在简单的数据结构上进行复杂的运算 软件设计的主要工作就是设计求解问题的过程 注重于程序设计技巧 适合于数值计算 结构化特别是面向对象的程序设计以数据 结构 为中心 系统采用复杂的数据结构来描述系统状态 程序围绕数据结构进行加工 这种编程语言更适合于非数值计算 2 数据结构在计算机科学中的地位 1 是计算机科学的一门专业基础和核心课程 2 是学习 设计和实现操作系统 编译系统 数据库系统和其它应用系统的重要基础 1 3抽象数据型 ADT 1 3 1抽象数据型的定义1 3 2数据型 数据结构和ADT1 3 3抽象数据型的实现1 3 4多层次抽象技术1 3 5抽象数据型的优点 1 3 1抽象数据型的定义 一 抽象数据型的定义1 定义 是一个数学模型和在该模型上定义的操作集合的总称 注 ADT是程序设计语言中数据类型概念的进一步推广和进一步抽象 ADTint x x Z 2 ADT的优点使用者只要知道这些操作的用途就可以编程序了 至于这些操作是怎样实现的 以及整型数在内存中是如何表示的 并不影响使用者所编程序的编码形式 1 3 1抽象数据型的定义 二 抽象数据型的实现1 抽象型实现的含义就是将ADT转换成程序设计语言的说明语句 加上对应于该ADT中的每个操作的函数 换句话说 就是用适当的数据结构来表示ADT中的数学模型 并用一组函数来实现该模型上的各种操作 2 注意事项 1 同一数学模型上定义不同的操作集 则它们代表不同的ADT 2 把ADT的描述与用某种程序设计语言实现ADT加以区别 这是大型程序设计中当前的发展趋势 1 3 2数据型 数据结构和ADT 1 三个概念的各自含义及相互关系 1 各自含义数据型是该类型变量的存储格式和所有可能取值的集合 数据结构则是抽象数据型中数学模型的表示 抽象数据型是一个数学模型及在该模型上定义的操作集的总称 2 相互关系数据型是根据数据结构分类的 同类型的数据元素的数据结构相同 数据结构是ADT中数学模型的表示 ADT是数据类型的进一步推广和进一步抽象 2 信息聚集的三种方式数组 结构 体 和文件 1 3 3抽象数据型的实现 一 ADT的实现原则 1 应符合规格描述的定义 2 应有尽可能好的通用性 3 应尽可能具有良好的独立性 在结构上应成为独立的模块 将内部细节屏蔽起来 二 ADT的实现举例 ADT栈的带头结点的链式实现 1 数据结构描述enumboolean FALSE TRUE structnode elementtypeval node next 结点的类型typedefnode stack 栈的类型 1 3 3抽象数据型的实现 2 基本操作的实现stackNEWSTACK stacks s newnode s node malloc sizeof node s next NULL returns 1 3 3抽象数据型的实现 voidPUSH elementtypeelm stackstk stacks s newnode s val elm s next stk next stk next s 1 3 3抽象数据型的实现 voidPOP stackstk stacks if stk next stk next NULL s stk next stk next s next deletes free s 1 3 3抽象数据型的实现 elementtypeTOP stackstk if stk next return stk next val elsereturnNULLELE 1 3 3抽象数据型的实现 booleanEMPTY stackstk if stk next returnFALSE elsereturnTRUE 1 3 4多层次抽象技术 1 逐层抽象方法对于较复杂的数据类型 先将较简单 较基本的数据类型抽象出来 给出定义 再用已定义的数据类型去定义更复杂的数据类型 完成对后者的抽象 就是说 用已定义的类型来表述正要定义的类型的定义域 并用前者的操作来表述后者的操作这就是所谓逐层抽象的方法 逐层抽象实质是用已知的简单数据类型定义更复杂的数据类型 1 3 4多层次抽象技术 2 优点 1 由于在定义高层数据类型时不必考虑低层数据类型及其操作的内部细节 因而对复杂数据类型进行抽象可以简化许多琐事 2 多层次抽象化通常可以采用自底向上的方式进行 先抽象出最基本的数据类型 然后利用它们定义上一层数据类型 如此逐层向上 直至到达最高层的数据类型为止 这样可以防止低层次倒过来引用高层数据类型 保证整个系统的有序层次结构 3 缺点多层次抽象化的最终目的是建立最高层的数据类型 因此低层应该服从高层的要求 自底向上方式是底层的抽象带有一定的盲目性 在抽象过程中 可能从高层返回低层作修正 也就是不得不穿插一些自顶向下的过程 1 3 5抽象数据型的优点 采用抽象数据型的方法进行软件 特别是大型软件 系统的设计 具有许多明显的优点 首先 它降低了软件设计的复杂性 其次 抽象数据型可提高程序的可读性和可维护性 第三 由于抽象数据型的使用降低了程序的复杂度 使程序的各部分相对分离 因而程序的正确性容易得到保证 第四 有利于软件重用 1 4算法及其复杂性 1 4 1算法及其性能评价准则1 4 2算法时间复杂性分析方法 1 4 1算法及其性能评价准则 一 算法 算法的特征和算法描述算法 Algorithm 是对特定问题求解步骤的一种描述 它是指令 规则 的有限序列 其中每一条指令表示一个或多个操作 算法的特征 有穷性 确定性 能行性 输入 输出算法描述 自然语言 程序设计语言 类语言 1 4 1算法及其性能评价准则 一 算法 算法的特征和算法描述算法 Algorithm 是对特定问题求解步骤的一种描述 它是指令 规则 的有限序列 其中每一条指令表示一个或多个操作 算法的特征 有穷性 确定性 能行性 输入 输出算法描述 自然语言 程序设计语言 类语言 常用的算法设计方法 递归法 Recursion 分治法 Divide andConquer 贪心法 Greedy 动态规划 DynamicProgramming 搜索与遍历 回溯 Backtracking 解空间局部搜索 近似算法 Approximation 在线算法 On Line 等 1 4 1算法及其性能评价准则 二 好的算法的标准1 正确性 Correctness 正确性的含义 是指对于一切合法的输入数据经有限时间或有限步后均可得到正确 满足规格说明要求 的结果 算法包括两方面的内容 解决问题的方法 实现这一方法的一系列指令 语句 步骤 算法的正确性证明 需要一组相关的引理和定理 确认一个算法所使用的方法和公式的正确性 在证明一系列的语句确实做了符合规定的动作 算法的正确性的严格的形式化证明还未取得突破 还是一项令人生畏的工作 只有那些比较简单的算法 其正确性才能被形式化证明 1 4 1算法及其性能评价准则 二 好的算法的标准2 时间复杂性 TimeComplexity 如何计算和比较算法的执行时间 实验测量法 实际执行时间 执行指令的条数 优点 精确缺点 必须先运行根据算法编制的的程序 所得的时间统计量依赖于计算机的硬件 软件等环境因素 容易掩盖算法本身的优劣 1 4 1算法及其性能评价准则 二 好的算法的标准 事前分析 估计 法高级语言编写的程序在计算机上运行时间取决于下列因素 依据的算法本身选择何种策略 问题的规模 输入的规模 输入的大小 如求素数问题 程序设计语言 算法的实现语言级别越高 执行效率越低 编译程序产生的机器代码的质量 及其执行指令的速度 表明用绝对的时间单位衡量一个算法的效率是不适合的 1 4 1算法及其性能评价准则 二 好的算法的标准算法的时间复杂性 认为一个特定的算法执行时间 运行工作量的大小 只依赖于问题的规模 即算法执行时间是问题规模的函数 由于算法的执行时间由组成算法的控制结构 顺序 分支和循环 和基本操作的综合效果 因此从算法中选择对于研究问题来说是基本的操作 基本运算 把算法的基本操作的重复执行的次数作为算法的时间度量 通常 我们并不关心T n 的具体值 而是关心它的增长率 即T n 随问题规模n 是一个整数 的增大的变化趋势 界限 算法的复杂性定义算法中基本操作重复执行的次数是问题规模n的某个函数f n 算法的时间度量记作T n O f n 它表示随问题规模n的增大 算法执行时间的增长率不会超过f n 称为算法的渐进时间复杂性 简称时间复杂性 1 4 1算法及其性能评价准则 二 好的算法的标准3 空间复杂性 SpaceComplexity 算法的空间复杂性是指算法在执行过程中的存储量需求一个算法的存储量需求除了存放算法本身所有的指令 常数 变量和输入数据外 还包括对数据进行操作的工作单元和存储实现计算所需信息的辅助空间算法的存储量需求与输入的规模 表示方式 算法采用的数据结构 算法的设计以及输入数据的性质有关算法的执行的不同时刻 其空间需求可能是不同的算法的空间复杂性是指算法在执行过程中的最大存储量需求空间复杂性的渐进表示 空间复杂度T n O f n 其中 n为问题的输入规模 1 4 1算法及其性能评价准则 二 好的算法的标准4 可读性 Readability 可读性好的算法有助于设计者和和他人阅读 理解 修改和重用晦涩难懂的算法不仅容易隐藏错误 而且还增加了阅读难度可读性好的算法 常常也具有简单性5 健壮性 Robustness 当输入数据非法时 能作出适当的反应 如对输入数据进行语法检查 提出修改输入建议并提供重新输入的机会 避免异常出错6 一个好的算法还应该具有灵活性 Flexibility 可重用性 Reuseabale 和自适应性 Adaptability 等 1 4 2算法时间复杂性分析方法 一 算法的时间复杂性定义1 1设一个领域问题的输入的规模为n Dn是该领域问题的所有输入集合 任意一个输入I Dn是P I 是I出现的概率 I DnP I 1 T I 是 解决该领域问题的 算法在输入I下所执行的基本运算的次数 称E n I Dn P I T I 为该算法的期望复杂性 平均时间复杂性 称W n maxI Dn T I 为该算法的最坏时间复杂性 1 4 2算法时间复杂性分析方法 一 算法的时间复杂性例1 1A是一个由n个不同元素的实数数组 给出求其最大和最小元素的算法和时间复杂性voidSM doubleA intn double 容易看出 算法SM对大小为n的数组需要2 n 1 比较 算法SM的基本运算是元素比较 则复杂性为2 n 1 1 4 2算法时间复杂性分析方法 一 算法的时间复杂性例1 2A是一个由n个不同元素的实数数组 给出确定给定实数K是否在A中的算法及其时间复杂性intSK doubleA intn doubleK intj 0 while j n if A j K break elsej returnj 若j n 则K在A中 否则 j n K不在A中 1 4 2算法时间复杂性分析方法 一 算法的时间复杂性算法SK的基本运算是元素与K的比较假定q表示K在A中的概率 有假设K等于A的每个元素有相同的概率 令Dn I0 I1 In 1 In 其中Ij 0 j n 表示K A j 的任意输入 In表示K不是A中元素的任意一个输入 由上述说明有 当0 j n时 P Ij q n T Ij j 1 P In 1 q T In n算法SK的期望复杂性和最坏复杂性为E n j Dn P Ij T Ij j 0 n 1 q n j 1 1 q n 1 2 n 1 q 1 q n 1 2 n 1 K在A中 q 1 W n max T Ij 0 j n n 1 4 2算法时间复杂性分析方法 二 函数阶的比较定义1 2设f n T n 是整数集到实数集上的函数 称函数f n 是T n 增长率的上界 当且仅当存在一个正常数C和整数n0 使得对任意的n n0时 有T n Cf n 记作 T n O f n 此时也称T n 的阶至多为f n 一个算法的时间复杂性为O f n 表明它的基本操作次数至多是f n 的某个常数倍例1 3设函数T n 3n5 4n2 1 证明 T n n5 证明 f n n5 取n0 0 C 8 则当n n0时有T n 3n5 4n2 1 8n5 Cf n 证毕 1 4 2算法时间复杂性分析方法 二 函数阶的比较定义1 3设f n T n 是整数集到实数集上的函数 称函数f n 是T n 增长率的下界 当且仅当存在一个正常数C和整数n0 使得对任意的n n0时 有T n Cf n 记作 T n f n 此时也称T n 的阶至少为f n 一个算法的时间复杂性为 f n 表明它的基本操作次数至少是f n 的某个常数倍例1 4设函数T n 3n5 4n2 1 证明 T n n5 证明 f n n5 取n0 0 C 1 则当n n0时有T n 3n5 4n2 1 1 n5 Cf n 证毕 1 4 2算法时间复杂性分析方法 定理2 1若A n amnm a1n a0是关于n的m次多项式 则A n nm 此定理说明 时间复杂性仅取决于多项式的最高次幂 而与最高次幂的系数和其他低次项无关 1 表示时间复杂性为常数常见的时间复杂性及其比较 1 n n n n n n2 n3 2n 1 4 2算法时间复杂性分析方法 1 4 2算法时间复杂性分析方法 三 时间复杂性的运算法则设T1 n O f n T2 n O g n 则加法规则 T1 n T2 n O max f n g n 乘法规则 T1 n T2 n O f n g n 1 4 2算法时间复杂性分析方法 例1 5 s 0 f n 1 T2 n O f n O 1 常量阶 for i 1 i n i x s x f n 3n 1 T1 n O f n O n 线性阶 for i 1 i n i for j 1 j n j x s x f n 3n2 2n 1 T3 n O f n O n2 平方阶 for i 1 i n i for j 1 j n j c i j 0 for k 1 k n k c i j a i k b k j f n 2n3 3n2 2n 1 T4 n O f n O n3 立方阶 1 4 2算法时间复杂性分析方法 例1 6 Longfact intn C当n 0 n 1 if n 0 n 1 T n return 1 G T n 1 当n 1elsereturn n fact n 1 T n G f n 1 T n 1 G f n 2 T n 2 G f n 3 T 2 G f 1 T 1 CT n G n 1 C 1 5逐步求精的程序设计方法 1 5 1如何求解一个问题一 算法的定义1 计算能由一个给定的计算模型机械地执行的规则 或步骤 序列称为该计算模型的一个计算 注 一个计算机程序是一个计算 计算模型是计算机 计算可能永远不停止 不是算法 2 算法是一个满足下列条件的一个计算 1 有穷性 终止性 总是在执行有穷步后停止 2 确定性 每一步必须有严格的定义和确定的动作 3 能行性 每个动作都能被精确地机械执行 4 输入 有0个和多个满足约束条件的输入 5 输出 有一个或多个满足约束条件的结果 1 5逐步求精的程序设计方法 1 5 1如何求解一个问题一 算法的定义1 计算能由一个给定的计算模型机械地执行的规则 或步骤 序列称为该计算模型的一个计算 注 一个计算机程序是一个计算 计算模型是计算机 计算可能永远不停止 不是算法 2 算法是一个满足下列条件的一个计算 1 有穷性 终止性 总是在执行有穷步后停止 2 确定性 每一步必须有严格的定义和确定的动作 3 能行性 每个动作都能被精确地机械执行 4 输入 有0个和多个满足约束条件的输入 5 输出 有一个或多个满足约束条件的结果 1 5逐步求精的程序设计方法 1 5 1如何求解一个问题一 算法的定义3 算法的逐步求精就是对用自然语言等描述的算法逐步细致化 精确化和形式化 追求的目标是把算法变成可以执行的程序 1 5逐步求精的程序设计方法 1 5 1如何求解一个问题二 求解问题的一般过程1 模型化 对实际问题进行分析 选择适当的数学模型来描述问题 即模型化 2 确定算法 根据模型 找出解决问题的方法 算法 3 逐步求精 就是对用自然语言等描述的算法逐步细致化 精确化和形式化 这一阶段可能包括多步求精 当逐步求精到某一步时 根据程序中所使用的数据形式 定义若干ADT 并且用ADT中的操作代替对应的非形式语句 4 ADT的实现 对每个ADT 选择适当的数据结构表示数学模型 并用相应的函数实现每个操作 1 5逐步求精的程序设计方法 1 5 2算法逐步求精例1 7交叉路口的交通安全管理问题问题描述 一个具有多条通路的交叉路口 当允许某些通路上的车辆在交叉路口拐弯时 必须对其他一些通路上的车辆加以限制 不允许同时在交叉路口拐弯 以免发生碰撞 所有这些可能的拐弯组成一个集合 有5条组成的交叉路口 其中有2条路是单行道 把从一条路到另一条路的通路称为拐弯 有的拐弯可以同时通过 有些拐弯不能同时通过 共有13个拐弯 要求 1 设置一组交通灯 实现安全管理 2 使交通灯的数目最少 基本要求 把这个集合分成尽可能少的组 使得每组中所有的拐弯都能同时进行而不发生碰撞 这样 每组对应一个指挥灯 因而实现了用尽可能少的指非灯完成交叉路口的管理 1 5逐步求精的程序设计方法 1 5 2算法逐步求精模型化 1 用图作为交叉路口的数学模型 2 每个拐弯对应图中的一个顶点 3 若两个拐弯不能同时进行 则用用一条边把这两个拐弯所对应的两个结点连接起来 并且说这两个顶点是相邻的 1 5逐步求精的程序设计方法 1 5 2算法逐步求精确定算法 1 穷举法 2 试探法 3 贪心法贪心算法的思想是首先用第一种颜色对图中尽可能多的顶点着色 尽可能多表现出贪心 然后用第二种颜色对余下的顶点中尽可能多的顶点着色如此等等 直至所有的顶点都着完色 当用一种新颜色对余下的顶点着色时我们采取下列步骤 1 选取某个未着色的顶点 并且用新颜色对它着色 2 扫描所有未着色的顶点集 对其中的每个顶点 确定它是否与已着新颜色的任何顶点相邻 若不相邻 则用新颜色对它着色 1 5逐步求精的程序设计方法 1 5 2算法逐步求精用C 语言描述的 贫心 算法如下 voidgreedy GRAPHG SETnewclr 类型GRAPH和SET有待具体说明 本程序把G中可以着同一色的顶点放入newclr 1 newclr F 2 while G中有未着色的顶点v 3 if v不与newclr中的任何顶点相邻 4 对v着色 5 将v放入newclr 其中 G是被着色的图 newclr的初值为空 算法执行的结果形成可以着相同颜色的顶点的集合newclr 只要重复调用greedy算法 直到图中的所有顶点都被着色为止 即可求出问题的解 1 5逐步求精的程序设计方法 1 5 2算法逐步求精逐步求精 第一步求精 voidgreedy GRAPHG SETnewclr 类型GRAPH和SET有待具体说明 intfound 1 newclr F 2 whi