已阅读5页,还剩56页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构与算法B 课程编号 CST 0 502学时 课堂教学 教学实验 周学分 任课教师 赵海燕软件研究所zhhy 助教 2 3人 2005 2 24 2005SpringDataStructureandAlgorithms 2 教材 张乃孝主编 陈光 刘 韩玉真编 算法与数据结构 C语言描述 高等教育出版社 2002 2005 2 24 2005SpringDataStructureandAlgorithms 3 参考书 张乃孝 裘宗燕 数据结构 C 与面向对象的途径 高等教育出版社 2000年张乃孝 数据结构基础 北京大学出版社许卓群等著 数据结构 高等教育出版社 1987年张铭 刘晓丹译 数据结构与算法分析 C 第二版 电子工业出版社 2002年 2005 2 24 2005SpringDataStructureandAlgorithms 4 参考书 ThomasH Cormen CharlesE Leiserson RonaldL Rivest CliffordStein IntroductiontoAlgorithms MITPress 高等教育出版社影印 RobertSedgewick AlgorithminC Addison WesleyPress 1990 2005 2 24 2005SpringDataStructureandAlgorithms 5 考核内容 平时40 其中书面作业10 上机 报告 25 考勤 课堂表现5 考试 期末 60 要求 端正学习态度 严禁抄袭提倡适度讨论 但必须独立完成作业按时 限定期限内 提交作业根据延期长短相应扣分 2005 2 24 2005SpringDataStructureandAlgorithms 6 书面作业提交要求 写学号 名字每次作业 都在作业本或电子稿的word文档中写上 我保证没有抄袭他人作业 的诚实保证 否则 计零分或根据抄袭情况倒扣分 写算法分析 注释算法中直接使用的函数 过程要说明函数功能 入口参数 出口参数注意算法格式 层次嵌套 不同功能块之间留空 2005 2 24 2005SpringDataStructureandAlgorithms 7 上机题提交要求 上机作业打一个zip包后提交 学号 姓名 作业次数 e g 00308096张宁1 zip 包中含有 1 readme txt文件 把你的程序运行环境 编译运行步骤 程序功能等等简单说明一下2 附加了足够注释的源程序以及相关的项目和资源文件 3 上机实习总结报告 2005 2 24 2005SpringDataStructureandAlgorithms 8 上机安排 从第三周开始时间 周二9 10节地点 计算中心6 96人 号机房帐号 hx29 10 密码hx2004 2005 2 24 2005SpringDataStructureandAlgorithms 9 课程目标 学会怎样组织信息 以便支持高效的数据处理掌握常用的数据结构及其应用学会合理组织数据 有效地处理数据基本掌握算法的设计与分析方法提高程序设计能力 2005 2 24 2005SpringDataStructureandAlgorithms 10 基本要求 从每个数据结构的逻辑结构 相应的一组基本运算实现三个方面去掌握线性表 包括栈 队列 树 图和字典等常用的数据结构掌握在顺序存储结构上实现的几种重要的排序算法对算法的时间和空间复杂性有一定的分析能力针对简单的应用问题 应能选择合适的数据结构及设计有效的算法来解决 2005 2 24 2005SpringDataStructureandAlgorithms 11 学习数据结构的目的 求解问题计算机科学就是 一种关于信息结构转换的科学 Wegnor 数据结构也称 信息结构 计算机科学是 算法的学问 算法是精确定义的一系列规则 指出怎样从给定的输入信息经过有限步骤产生所求的输出信息 Knuth 其实 数据结构与算法两者互为存在 数据结构离不开施于其上的操作 同时算法也必然离不开作为其处理对象和结果的数据 2005 2 24 2005SpringDataStructureandAlgorithms 12 学习数据结构的目的 例子 已知一组人的身高 从中找出最高 最矮的 再找出身材最适中的 诸如101个人中 找出高度第51位的那个 TowerofHanio 给出3个柱子和n个圆盘 起初所有盘子均放在最左边的柱子上 按大盘在下的顺序堆放 如何把所有盘子移到最右的柱子上 要求任何盘子都不能放到比它小的圆盘上面 2005 2 24 2005SpringDataStructureandAlgorithms 13 第一章绪论 2005 2 24 2005SpringDataStructureandAlgorithms 14 内容 1 1问题求解1 2数据结构1 3算法1 4算法分析1 5抽象数据类型 2005 2 24 2005SpringDataStructureandAlgorithms 15 1 1问题求解 建立求解问题的模型 把描述实际对象的数据及其相互关系映射到计算机的存储器上 编程序模拟对象领域中的求解过程 2005 2 24 2005SpringDataStructureandAlgorithms 16 用计算机解决问题的步骤 问题分析 弄清所要解的问题是什么 并且把它用一种语言 自然语言 说明语言或数学语言 清楚地描述出来设计 建立程序系统的结构 重点是数据结构的设计和算法的设计程序编码 实现 采用适当的程序设计语言 编写出可执行的程序程序测试和维护 发现和排除在前几个阶段中产生的错误 在使用中不断维护和完善 2005 2 24 2005SpringDataStructureandAlgorithms 17 问题分析示例 为一个多叉路口设计一个交通信号灯的管理系统 首先需要分析一下所有车辆的行驶路线的冲突问题 这个问题可以归结为对车辆的可能行驶方向作某种分组 对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞 2005 2 24 2005SpringDataStructureandAlgorithms 18 问题分析示例 可通行方向A BA CA DB AB CB DD AD BD CE AE BE CE D 2005 2 24 2005SpringDataStructureandAlgorithms 19 交叉路口的图示模型 有些通行方向显然不能同时进行 相应的结点间画一条连线 问题分析示例 2005 2 24 2005SpringDataStructureandAlgorithms 20 问题分析示例 把图中的结点进行分组 使得有结点相连的结点不在同一个组里地图着色问题 如果把图中的一个结点理解为一个国家 结点之间的连线看作两国有共同边界 上述问题就变成著名的 着色问题 即求出最少要几种颜色可将图中所有国家着色 使得任意两个相邻的国家颜色都不相同通过上面的分析可以得到该交通管系统的数学模型 2005 2 24 2005SpringDataStructureandAlgorithms 21 程序设计示例 算法设计1 对n个结点 逐个测试其所有组合 2 贪心法 while有结点未着色 选择一种新颜色 在未着色的结点中 给尽可能多的彼此之间没有边的连接结点着色 2005 2 24 2005SpringDataStructureandAlgorithms 22 有些通行方向显然不能同时进行 相应的结点间画一条连线 AB AC AD BA BC BD DA DB DC EA EB EC ED 2005 2 24 2005SpringDataStructureandAlgorithms 23 程序设计示例 把前述方法应用于交叉路口的模型图 得到下面的分组 绿色 AB AC AD BA DC ED蓝色 BC BD EA红色 DA DB白色 EB EC 2005 2 24 2005SpringDataStructureandAlgorithms 24 程序设计示例 若有一种高级程序语言可以直结描述和处理抽象的集合和图 假设需要着色的图是G 集合V1包括图中所有未被着色的结点 着色开始时V1是G所有结点集合 NEW表示已确定可以用新颜色着色的结点集合 则下面的程序可从G中找出可用新颜色着色的结点集 NEW for每个v V1doifv与NEW中所有结点间都没有边 从V1中去掉v NEW NEW v 2005 2 24 2005SpringDataStructureandAlgorithms 25 程序设计示例 对集合和图的操作包括 判断一个集合是否为空 issetempty V1 置一个集合为空 emptyset NEW 从集合中去掉一个元素 removefromset V1 v 向集合里增加一个元素 addtoset NEW v 检查结点v与结点集合中各结点之间在图G中是否有边连接 notadjacentwithset NEW v G 有了图 集合这样的结构和基于其上的操作 程序的实现将会非常简单 但 现在没有 2005 2 24 2005SpringDataStructureandAlgorithms 26 程序设计示例 算法 intcolorup graphG intcolor 0 V1 G V while issetempty V1 emptyset NEW while v V1 2005 2 24 2005SpringDataStructureandAlgorithms 27 1 2数据结构 数据 Data 在计算机科学中是所有能输入到计算机中并能被计算机程序处理的符号的总称数据元素 DataElement 数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 有时称作点 结点或顶点 数据结构 DataStructures 由若干数据元素 点 按照一定方式构成的复合数据以及作用于其上的函数或运算 2005 2 24 2005SpringDataStructureandAlgorithms 28 数据结构 按照逻辑关系组织起来的一批数据 按一定的存储方法把它存储在计算机中 并在这些数据上定义了一个运算的集合数据之间的逻辑关系 逻辑结构 数据在计算机中的存储方式 存储结构 数据的运算简言之 一类数据的表示及其相关操作 2005 2 24 2005SpringDataStructureandAlgorithms 29 数据结构 1 逻辑结构 表示数据元素之间的逻辑关系B K R 2 物理结构 数据结构在计算机存储器中的映射 或表示 又称存储结构 也称存储表示 3 运算 结构的行为特征 作用于数据结构上的运算 例如 检索 插入 删除等常见的基本数据结构 线性表 字符串 堆栈与队列 树与二叉树 字典 图本书将要讨论的主要数据结构 2005 2 24 2005SpringDataStructureandAlgorithms 30 线性结构 关系r是一种线性关系 或称为 前后关系 有时也称为 大小关系 关系r是有向的 且满足全序性和单索性等约束条件全序性是指 线性结构的全部结点两两皆可以比较前后 关系r 单索性是指 每一个结点x都存在唯一的一个直接后继结点y 如果其他结点z在y之前 则这个z也一定在x之前 不会在x y之间 在程序设计中应用最多 2005 2 24 2005SpringDataStructureandAlgorithms 31 树型结构 树型结构简称树结构 或称为层次结构 其关系r称为层次关系 或称 父子关系 上下级关系 等每一个结点可以有多于一个的 直接下级 但是它只能有唯一的 直接上级 树型结构的最高层次的结点称为根 root 结点 只有它没有父结点从数学上看 树型结构和图结构的基本区别就是 每个结点是否仅仅从属一个直接上级 而线性结构和树型结构的基本区别是 每个结点是否仅仅有一个直接后继 树型结构存在着很多变种 如二叉树结构 堆结构等 它们都有着各自独特的有效应用 2005 2 24 2005SpringDataStructureandAlgorithms 32 图结构 图结构有时称为结点互联的网络结构 因特网的网页链接关系就是一个非常复杂的图结构对于图结构的关系r没有加任何约束 这样也就无法象线性结构及树结构那样 利用关系r的约束来设计图结构的存储结构在日常应用中图结构往往只是层次结构的一种扩展 允许结点具有多个 直接上级结点 关系r表现为树型结构约束的放松 2005 2 24 2005SpringDataStructureandAlgorithms 33 问题 数学模型 实现 数据结构的主要内容 不同结构的比较及算法分析 2005 2 24 2005SpringDataStructureandAlgorithms 34 问题 算法和程序 问题需要完成的任务 比如TowerofHanio可看成数学中的函数 输入到输出的一种映射算法解决问题的一种方法或一个过程一个问题可有多种算法来解决程序使用某种程序设计语言对一种算法的具体实现 2005 2 24 2005SpringDataStructureandAlgorithms 35 1 3算法 Algorithm 解题过程的精确描述 由有限条可完全机械执行的 有确切含义的指令 或命令 语句 所构成用计算装置能够理解的语言描述的解题过程 具有如下性质 将它作用于所求解的问题的给定输入集上 或作用于问题自身的描述上 将产生唯一确定的动作序列 此序列是有限的 此序列或终止于给出问题的解 或终止于指出问题对此输入无解有穷性 确定性 可行性 输入 输出 2005 2 24 2005SpringDataStructureandAlgorithms 36 算法的特性 1 正确性必须完成所期望的功能 2 确定性 无二义性 下一步应执行的步骤必须明确 3 0至多个输入 1至多个输出 4 具体步骤由一系列具体步骤组成 5 有穷性有限步骤组成 6 可终止性 2005 2 24 2005SpringDataStructureandAlgorithms 37 算法分类 穷举法 百钱买百鸡 贪心法 Huffman树 递归法 分治法 二分法检索 回溯法 八皇后 动态规划法 最佳二叉排序树 宽度优先和深度优先搜索 裁剪和分枝界限法并行算法 2005 2 24 2005SpringDataStructureandAlgorithms 38 1 4算法分析 算法设计的两个目标 易读 易编码和调试 软件工程 充分利用计算机资源 算法和数据结构 评估方法 实验 运行程序 渐进分析 关键资源 影响运行时间的因素 往往与问题的输入规模有关 2005 2 24 2005SpringDataStructureandAlgorithms 39 算法分析 评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源 程序所用算法运行时所要花费的时间代价程序中使用的数据结构占有的空间代价 2005 2 24 2005SpringDataStructureandAlgorithms 40 时间代价 空间代价 算法的空间代价 或称空间复杂性 当被解决问题的规模 以某种单位计算 由1增至n时 解该问题的算法所需占用的空间也以某种单位由f 1 增至f n 这时我们称该算法的空间代价是f n 算法的时间代价 或称时间复杂性 当问题规模以某种单位由1增至n时 对应算法所耗费的时间也以某种单位由g 1 增至g n 这时我们称算法的时间代价是g n 2005 2 24 2005SpringDataStructureandAlgorithms 41 时空复杂性 问题规模空间单位 一般规定为一个简单变量 如整型 实型等 所占存储空间的大小时间单位 一般规定为执行一个简单语句 如赋值语句 判断语句等 所用时间主要运算例如 直接选择排序主要运算 比较运算空间单位 一个元素占存储空间s时间单位 一次比较所用时间t n 1 n 2 2 1 n n 1 2 2005 2 24 2005SpringDataStructureandAlgorithms 42 大O 表示法 说某个算法的时间代价 或者空间代价 为O f n 则表示如果存在正的常数c和n0 当问题的规模n n0后 该算法的时间 或空间 代价T n c f n 这时也称该算法的时间 或空间 代价的增长率为f n 算法增长率的上限 当n充分大时 该算法的复杂性不大于f n 的一个常数倍 2005 2 24 2005SpringDataStructureandAlgorithms 43 大O 常用的计算规则 1 加法规则 顺序结构 If结构 switch结构T n T1 n T2 n O f1 n O f2 n O max f1 n f2 n 2 乘法规则 for while do while结构T n T1 n T2 n O f1 n O f2 n O f1 n f2 n 2005 2 24 2005SpringDataStructureandAlgorithms 44 大O 表示法 采用 大O表示法 简化了时间和空间代价的度量 其基本思想是主要关注复杂性的量级 最坏情况下的代价 对同样规模的问题所花费的最大代价 最好情况下的代价和平均情况下的代价等 关心当n充分大时 函数T n c logn n n2 n3 2n常数 对数 线性 二次 指数 增长率 2005 2 24 2005SpringDataStructureandAlgorithms 45 复杂度图示 2005 2 24 2005SpringDataStructureandAlgorithms 46 10 20 30 40 50 200 400 600 800 1000 1200 1400 10n 20n 5nlogn 2n2 2n 2005 2 24 2005SpringDataStructureandAlgorithms 47 复杂性计算示例 Cn n An n Bn nfor i 0 i n i for j 0 j n j c i j 0 for k 0 k n k c i j c i j a i k b k j T n O f1 n f2 n 1 n O n2 n3 O n3 2005 2 24 2005SpringDataStructureandAlgorithms 48 OrdersofMagnitudeinSpeed 2005 2 24 2005SpringDataStructureandAlgorithms 49 运行时间估算 例 假设CPU每秒处理106个指令 对于输入规模为108的问题 时间代价为2n2的算法要运行多长时间 操作次数为T n T 108 2 108 2 2 1016运行时间为2 1016 106 2 1010秒每天有86 400秒 因此需要231 480天 634年 2005 2 24 2005SpringDataStructureandAlgorithms 50 运行时间估算 例 假设CPU每秒处理106个指令 对于输入规模为108的问题 时间代价为nlogn的算法要运行多长时间 操作次数为T n T 108 108 log108 2 66 109运行时间为2 66 109 106 2 66 103秒 即44 33分钟 2005 2 24 2005SpringDataStructureandAlgorithms 51 规定时间内处理问题的规模 设CPU每秒处理106个指令 则每小时能够解决的最大问题规模T n 106 3600对T n 2n2 即2n2 3600 106n 42 426T n nlogn即nlogn 3600 106n 133 000 000 2005 2 24 2005SpringDataStructureandAlgorithms 52 加快硬件速度 CPU每秒处理108个指令 快100倍 处理时间降为原来的1 100 解决问题的规模 对2n2 规模增加10倍 对nlogn 规模增加75倍 2005 2 24 2005SpringDataStructureandAlgorithms 53 数据结构和算法的选择 如何求解问题的关键在于数据结构和算法的选择分析问题 以确定任何算法均会遇到的资源限制确定必须支持的基本操作 插入 删除和查找 并度量每种操作所受的资源限制选择最接近这些开销的数据结构和相应的算法 2005 2 24 2005SpringDataStructureandAlgorithms 54 时间与空间的权衡 数据结构一定的空间来存储它的每一个数据项一定的时间来执行单个基本操作代价和效益空间和时间的限制程序设计工作量 2005 2 24 2005SpringDataStructureandAlgorithms 55 1 5抽象数据类型 模块化的思想的发展 它为模块的划分提供了理论依据 简称ADT可以看作是定义了一组操作的一个抽象模型例如 集合与集合的并 交 差运算就可义为一个的抽象数据类型 一个抽象数据类型要包括哪些操作 这一点由设计者根据需要确定例如 对于集合 如果需要 也可以把判别一个集合是否空集或两个集合是否相等作为集合上的操作 2005 2 24 2005SpringDataStructureandAlgorithms 56 抽象数据类型 用数学方法定义对象集合和运算集合 仅通过运算的性质
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年安全管理人员安全教育培训试题及答案
- 2023年煤矿井下电气备考押题二卷合一带答案41
- (2025)0-6岁儿童健康管理服务规范培训试题及参考答案
- (新)保密知识竞赛试题(附答案)
- (中级社工师)综合能力试题及答案
- 2025 年食安员管理员考试题库及答案
- (2025年)辅警考试真题及答案
- (完整版)船员安全培训试题(含答案)
- 26年初级注册安全工程师《建筑施工安全》真题及答案解析
- 20261029-052016-人教版三年级体育下册单元测试卷全套(含答案)
- 北京市朝阳区2026-2027学年度第一学期期中质量检测高三英语试卷(含答案)
- 2026山东省防疫安全协管员招聘考试(畜牧兽医)历年参考题库含答案详解
- 2026健康管理师考试理论知识真题及答案
- 2025 含聚谷氨酸有机水溶肥料在马铃薯种植中的应用技术规程
- 2026-2027学年清华附中九年级上册化学期中真题卷
- 2026年四川省成都市技能人才评价考评员考试题库(附答案)
- 正大集团人才评估行测题目
- 离散数学 (第七版) 课件 第二部分 集合论
- FMEA风险评估分析表实战培训
- 2025年进出口银行人员招聘笔试考试试题及答案详解
- 光伏组件拆除方案
评论
0/150
提交评论