数据结构与算法PPT.ppt

数据结构与算法 乔海燕电话 020 31981361Email qiaohy 1 课程安排 讲授3学时 周 实验2学时 周 分组 总成绩 平时 听课 作业 期中 期末教学用书 RobertL KruseandAlexanderJ Ryba DataStructuresandProgramDesigninC 高教出版社 2001年参考书 1 数据结构 许卓群 张乃孝 杨冬青 唐世渭 高等教育出版社 1987年2 数据结构 C 与面向对象的途径 张乃孝 裘宗燕 高等教育出版社 1998年3 数据结构 C语言版 严蔚敏 吴伟民 清华大学出版社 1997年4 数据结构与算法 王若梅等著 中山大学出版社 2000年 2 为什么学习数据结构 计算机科学是 一种关于信息结构转换的科学 Wegnor InputOutput 算法的学问 算法是精确定义的一系列规则 指出怎样从给定的输入信息经过有限步骤产生所求的输出信息 Knuth 信息结构 数据结构 和算法是计算机科学的核心课题 两者之间有着本质的联系 数据结构 算法 程序 Computersystem 3 程序 算法 数据结构 数据结构 一种程序构件 programmingconstruct 工具 编程中常用的数据组织形式及其操作的抽象 编程 数据结构的选择 算法的设计与度量 4 教学目的 掌握常用的数据结构及其应用学会合理地组织数据 有效地表示数据和处理数据掌握算法设计技术和分析技术提高程序设计质量 5 第一章概论 什么是数据结构抽象数据类型算法的概念算法的度量 数据结构示例数据结构的概念数据的逻辑结构数据的存储结构 6 什么是数据结构 示例1 例1图书馆的书目自动检索系统 所处理的基本数据 数据元素 每本书由 登录号 书名 作者 出版社 分类号 组成 数据元素间的关系 逻辑结构 一个按登录号顺序排列的书目表和按书名 作者和分类号顺序排列的索引表 所需的操作 一组作用在这些表上的运算 查询 插入 修改等 怎样存储这些数据及其关系使得上述操作容易实现 存储结构 7 什么是数据结构 示例2 例2人机对弈问题 三子棋 数据元素 格局 某时刻的棋盘布局 格局之间的关系 一个格局可以派生出几个下一个格局 树状结构 博弈树 操作 由某个格局出发 借助于以上的格局树 显式地或非显式地 找出计算机赢的步骤 存储结构 如何存储格局及其格局间的关系 8 什么是数据结构 示例3 例3多岔路口的交通灯管理系统 B A C D E 数据元素 通路 如 A B 通路间的关系 图 通路为结点 两节点相邻 如果两通路不能同时通行 操作 上图的着色问题 用最少的颜色 对每个节点着色 相邻节点着不同的颜色 存储 如何存储通路间的关系 9 第一章概论 什么是数据结构抽象数据类型算法的概念算法的度量 数据结构示例数据结构的概念数据的逻辑结构数据的存储结构 10 数据结构的概念 数据是客观事物的符号表示 是信息的载体数据元素是数据的基本单位数据结构是相互间具有某些关系的数据元素的集合 它包括下面三方面的内容 1 数据的逻辑结构 表示数据元素间的关系 2 数据的运算 是数据元素集上所允许的操作 3 数据的存储结构 指如何在计算机上数据元素及其关系 11 第一章概论 什么是数据结构抽象数据类型算法的概念算法的度量 数据结构示例数据结构的概念数据的逻辑结构数据的存储结构 12 数据的逻辑结构 数据的逻辑结构是一个二元组 D R D是数据元素的有限集 R是D上关系的有限集 例如 在示例3中 D AB AC AD BA BC BD DA DB DC DA EB DC ED R R1 R1 AB EA AB BD AB DA AB BC 13 逻辑结构的类型 我们将讨论R含有一个关系的情况 即R R1 根据R1的特性 数据结构 D R1 可分为下列几种 D d1 d2 dn 1 集合 数据元素同 属于一个集合 R1 2 线性结构 R1 d1 d2 d2 d3 d n 1 dn 即除开始和终结节点d1 dn外 每个节点有一个前驱和一个后继3 树状结构 D R1 构成树 即每个元素最多有一个前驱 可以有多个后继4 图状结构 D R1 构成一个图 14 第一章概论 什么是数据结构抽象数据类型算法的概念算法的度量 数据结构示例数据结构的概念数据的逻辑结构数据的存储结构 15 数据的存储结构 数据 逻辑 结构的存储包含数据元素的存储及其逻辑关系的存储设M为内存的一片存储区域 将数据结构存储到计算机内 我们需要建立一个映射 存储映像 S D M即对于D中的每个数据元素d S d M 并且这个映射具有明显地或者隐含地体现R的能力 根据存储映像的特点 存储结构可分为 顺序存储结构 链式存储结构 索引和散列等 16 存储结构的分类 顺序结构 顺序的方法 将逻辑上相邻的元素存储到物理上相邻的存储位置 常用于线性的数据结构 例如 D d1 d2 d3 d4 d5 R d1 d2 d2 d3 d3 d4 d4 d5 假定一个结点占一个单元 d1存放于200号单元 d1 d2 d3 d4 d5 200 201 202 203 204 17 存储结构的分类 链式结构 这种结构是给结点附加一个指针字段 指出其后继节点的位置 即存放结点的存储单元分为两部分 数据项 指针项 指针项可以有多个 以指示多个后继 例如 R d1 d2 d1 d3 d2 d4 d2 d5 d3 d6 d1 d2 d3 d6 d5 d4 d1 d2 d3 d4 d5 d6 空指针 18 索引 Indexing 的方法 在线性结构中 将每个节点的序号作为其索引号 索引的存储结构就是用节点的索引号来确定节点的存储地址 数据存储区 1 2 3 4 5 索引表存储索引号及地址 M 存储映像 Z M 19 假设每个节点占用p个单元且顺序存储 q为开时节点的存储位置 那么第i个节点的存储位置为 i 1 p q存储映像可以是非线性的 20 散列 hashing 的方法 散列的方法是用结点的值来确定其地址 假设每个数据元素都有一个关键字 K是关键字的集合 函数 称为散列函数 最好的散列函数应满足不同的关键字具有不同的地址 如果不同的关键字对应的地址相同 则称为 碰撞 冲突 h K M 21 以上四种方法可以组合使用 例如 先用散列的方法存储表 发生碰撞时 用一个链表存储所有的同义词 逻辑结构相同 但存储结构不同 则认为是不同的数据结构 如顺序表和链表具有相同的逻辑结构 但存储结构分别为顺序结构和链表结构 22 第一章概论 什么是数据结构抽象数据类型算法的概念算法的度量 23 数据类型 DataType 一般的高级语言都提供了一些数据类型 如整数型 字符型等 数据类型是一个值的集合和定义在此集合上的一组操作的总称 用户还可以定义自己的数据类型 数据类型可分为原子类型 不可分解的 如int bool char等 和结构类型 由其他类型构成 数据类型为程序员提供了极大的方便 它将数据集合及其上的操作与其实现细节分离开来 或者说将数据的逻辑表示和运算与它们的实现相分离 程序员只需要了解此集合由哪些值构成 可以进行那些运算 24 抽象数据类型 ADT 我们把数据元素集合 或者一个数据模型 及其上的一组操作的数学说明称为抽象数据类型 AbstractDataTypes 常用ADT表示 例如 表示圆的ADT 数据模型 表示圆的半径和圆心的三个实数 操作 构造一个给定圆心和半径的圆 求圆的面积等一个数据结构是一个ADT的实现 现代程序设计使用信息隐蔽和数据封装 使得ADT的使用和实现相分离 ADT的使用和ADT的实现可以同时进行 ADT实现的修改不影响ADT的使用 本课程介绍的数据结构将由抽象数据结构描述 25 ADT在OO语言中的实现 在C 中 一个ADT与其实现构成一个class 或者说抽象数据类型可以由C 的类来描述 ADT的每个运算对应一个成员函数 例如 表示圆的classclassCircle private floatr x y public Circle floatv1 floatv2 floatv3 floatarea returnpi r r 一个抽象数据类型中的数据元素集可以是任意时 即多态ADT 这样的ADT可用template来描述 26 第一章概论 什么是数据结构抽象数据类型算法的概念算法的度量 27 算法的概念 一个算法是对特定问题求解步骤的一种描述 它是指令的有穷序列 算法具有以下特性 1 有穷性 一个算法总是在执行有穷步后结束2 确定性 算法的每一步都必须是明确地定义的 3 可行性 算法中的每一步都是可以通过已经实现的操作来完成的4 输入 一个算法有零个或者多个输入 这些输入取自于特定的对象集合5 输出 一个算法有一个或者多个输出 它们是与输入有特定关系的量 28 算法的描述 算法的描述可以用下列语言描述 自然语言程序设计语言介于自然语言和程序设计语言的伪代码框图 29 算法的设计要求 算法的设计应满足 1 正确性 对于合法的输入产生符合要求的输出 2 可读性 算法应该易读 便于交流 这也是保证算法正确性的前提 添加注释也是一种增加可读性的办法 3 健壮性 当输入非法时 算法还能做出适当的反应而不会崩溃 如输出错误信息 算法中应该考虑适当的错误处理 4 效率高且内存消耗小 效率高指运行时间短 存储指算法执行过程中所需的最大存储空间 30 算法设计 例假设有n 1 个整数a1 a2 an 要求对此数列由小到大进行排序 显然这个数列构成一个线性结构 我们选择顺序存储结构 即用一个数组A存储此数列及排序后的数列 思路 1从未排好序的数列中选出最小的元素 将其放到排好序的数列后2重复这个过程 直至排序结束 31 a1 a2 a3 an 找出最小元素aj a1 a2 a3 an aj 交换a1和aj a1 a2 a3 an aj 找出最小元素aj a1 a2 a3 an aj 交换a2和aj 32 进一步细化 假设n个数存放在一个数组A 0 n 1 中1 循环i以1步长 从0到n 2 执行 1 ji A i 存储从A i 到A n 1 的最小整数 2 循环k以1为步长 从i 1到n 1 执行若A k A j 则jk 从A i 到A n 中选出最小整数 3 tA i A i A j A j t 交换A i A j 2 算法结束 33 voidselectSort inta constintn 将整数列a 0 a n 1 按非递减序排列for inti 0 i n 1 i intj i 找出a i 到a n 1 的最小数a j for intk i 1 k n k if a k a j j k j指示当前的最小数 交换a i 和a j inttempt a i a i a j a j t 34 模板 Template 前一程序只适用于整数列的排序 事实上 此算法适用于任何 定义了比较运算 类型的序列 我们可以用C 提供的模板机制来设计一个更通用的排序算法 一个模板函数是适用于很多类型的函数 在这些类型上运算遵从相同的模式 它带有类型参数的函数 当类型参数用特定的参数代换时 编译器生成针对此类型的特定函数 同样 一个模板类是带有类型参数的类 它适用于多种类型 通过简单的类型代换 编译器便可生成代换类型的类 35 templateclassdataList1 private T element intarraySize voidswap constintm1 constintm2 intminKey constintlow constinthigh public dataList intsize 10 arraySize size element newT size dataList delete element voidsort 36 templatevoiddataList swap constintm1 constintm2 Ttemp element m1 element m1 element m2 element m2 temp templateintdataList minKey constintlow constinthigh intmin low for intk low 1 k high k if element k element min min k returnmin 37 templatevoiddataList sort for inti 0 i arraySize 1 i intj minKey i arraySize 1 if j i swap j i 38 第一章概论 什么是数据结构抽象数据类型算法的概念算法的度量 39 算法分析 解决同一问题的算法可以有多种 我们希望从中选出最优的算法 效率高或者存储空间小 为此 我们需要对算法进行评估 分析 通常有两种方法 事后统计 不同算法的程序运行在同一组输入上 根据时间和空间的统计来比较优劣 缺陷 事先编写程序 依赖于程序运行的软硬件环境 习题 试统计函数sort 在不同大小输入上的运行时间 40 算法分析 事前估计 一种不考虑算法的程序运行软硬件环境的分析方法 一个算法的运行工作量的大小只依赖于问题的规模 通常考虑两个度量 时间复杂度 算法执行的操作的总数作为问题规模的函数 空间复杂度 算法执行时所占用的存储空间作为问题规模的函数 41 时间复杂度 对于给定规模的问题 计算算法运行的总 步数 在算法中选取一种基本操作作为 程序步 多种不同的操作可视为一个程序步 或者不同的操作具有不同的权 统计算法从开始到运行终止时所需总程序步数T 并将其视为问题规模n的函数T n T n 称为算法的时间复杂度 42 例迭代累加求和floatsum inta constintn floats 0 0 计一步for inti 0 i n i s a i 每次循环计 步 赋值returns 总计步数 n 问题的规模即数组的规模n 43 包含函数调用的赋值语句的程序步数 x sum A n 总步数 调用的步数 1即 n 1 基本运算的完成时间不应该依赖于所涉及参数值 44 求总程序步数 数组的大小n为问题的规模 voidselectSort inta constintn for inti 0 i n 1 i intj i 计一次for intk i 1 k n k if a k a j j k if语句最多计 步 此循环总步数 2 n i 1 inttempt a i a i a j a j t 计3步 n 1次循环 每次1 n i 1 3 总计T n n 2i 0 1 n i 1 3 n 4 n 1 T n 与输入有关系 45 时间复杂度T n 可能依赖于输入 即不同的输入 相同的规模 其复杂度不同 譬如排序算法 此时可以计算平均复杂度或者最坏情况复杂度 平均复杂度 TheAverageCase 所有可能输入数据集的期望值 最坏情况复杂度 TheWorstCase 估算最坏情况下时间复杂度的一个上界 这也是通常所指的复杂度 46 复杂度的度量通常计算到数量级 如果f n 是一个函数 并且存在一个常数c 当n充分大时 则记为T n O f n 如T n 3n2 12n 则T n O n2 累加求和的例子 T n O n 排序的例子 T n O n2 注意 我们不写T n O 3n2 或者T n O n3 应该取最小的上界 常见的复杂度 O 1 O log2n O n O nlog2n O n2 O 2n O n T n cf n 47 n T n 200log2n 100n 5n2 2n 20 10 2000 1000 48 T1 n 100nlogn T2 n n2 假设问题规模为n 28 49 更快的机器还是更快的算法 换一个快10倍的机器能否解决更大的问题呢 n 原机器一小时解决问题规模 n 新机器一小时解决问题规模 50 大O表示法 加法法则 n T1 n T2 n O f1 n O f2 n O max f1 n f2 n 即 如果两个程序段的复杂度分别为O f1 n 和O f2 n 则将这两个程序段顺序连接的程序的复杂度为O max f1 n f2 n 例如 考虑以下的程序段 action1 action1的时间复杂度为O f1 n actions action2的时间复杂度为O f2 n 此程序段的时间复杂度为O max f1 n f2 n 51 乘法法则 n T1 n T2 n O f1 n O f2 n O f1 n f2 n 例如 下面的程序段 for i 1 i n i action 这里 如果以action的时间代价为单位 则for循环的代价为T1 n O n 假设action的时间复杂度为O f n 按乘法法则 此程序段的时间法杂度为O nf n 如果一个程序的执行代价为O f1 n 但其单位是另一个程序的执行代价 而后一个程序的执行代价为