第一讲数据结构与算法.ppt

数据结构与算法 第一讲 计算机编程解决问题的基本步骤 1 分析具体问题 抽象数学模型 2 设计数据结构 选择有效算法 3 编写程序 实现算法 4 设计测试数据 反复调试直至得到最终解答 数据结构 算法 程序设计 运用数据结构的知识更好地进行算法设计与算法分析 掌握计算机进行数据处理的基本原理 基本方法和技巧 进一步提高程序设计的水平和能力 一 数据结构的基本概念数据 是对客观事物的符号表示 在计算机系统中指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素 是数据的基本单位 是数据这个集合中的一个一个的元素 构成数据元素的不可分割的数据单位称为数据项 例如 对于学生花名册 其中每个学生记录就是一个数据元素 而学生的姓名 年龄等项目为数据项 数据元素是讨论数据结构时涉及的最小数据单位 数据对象 是性质相同的数据元素的集合 是数据的一个子集 例如 整数数据对象是集合N 0 1 2 数据结构 在任何问题中 数据元素都不是孤立存在的 而是在它们之间存在存在着某种关系 数据元素相互之间的关系称为结构 把相互之间存在着一定关系的数据元素的集合及定义在其上的基本操作 运算 称为数据结构 如果不考虑定义在数据结构上的操作 则数据结构也可借助集合论术语定义为 数据结构是一个二元组 D S 其中D是数据元素的有限集 S是D上的关系的有限集 二 数据结构的分类集合结构中的数据元素之间除了 同属于一个集合 的关系外 别无其它关系 则称这种结构为集合 在集合中 各元素是 平等 的 它们的共同关系是都属于同一个集合 线性结构结构中的数据元素之间存在一个对一个的关系 在线性结构中 第一个元素可以没有前驱 最后一个可以没有后继 其余的每个元素都有唯一的前驱和后继 树形结构结构中的数据元素之间存在一个对多个的关系 在树形结构中 除第一个特殊元素没有前驱外 其它每个元素都有唯一的前驱 图状结构结构中的数据元素之间存在多个对多个的关系 三 数据的逻辑结构与物理结构 数据结构定义中描述的 关系 是数据元素之间的逻辑关系 称为数据的逻辑结构 数据结构在计算机中的表示 又称映象 称为数据的物理结构 又称存储结构 它包括数据元素的表示和关系的表示 数据元素之间的关系在计算机中有两种不同的表示方法 顺序映象和非顺序映象 并由此得出两种不同的存储结构 顺序存储结构和链式存储结构 1 顺序存储结构 用一组地址连续的存储单元依次存放数据元素 数据元素之间的逻辑关系通过元素的地址直接反映 用一组地址任意的存储单元依次存放数据元素 数据元素之间的逻辑关系通过指针间接地反映 2 链式存储结构 a1a2a3 a30 线性结构 线性表 1 顺序存储结构 2 链式存储结构 四 数据结构课程研究的主要内容 1 研究数据元素之间的客观联系 2 研究具有某种逻辑关系的数据在计算机存储器内的存储方式 3 研究如何在数据的各种关系 逻辑的和物理的 的基础上对数据实施一系列有效的基本操作 五 算法的概念 算法是对特定问题求解步骤的一种描述 它是指令的有限序列 其中每一条指令表示一个或多个操作 一个算法具有下列五个重要特性 1 有穷性一个算法必须总是 对任何合法的输入值 在执行有穷步之后结束 且每一步都可在有穷时间内完成 2 确定性算法中的每一条指令必须有确切的含义 在任何条件下 算法只有唯一的一条执行路径 即对于相同的输入只能得出相同的输出 3 可行性算法中描述的操作都是可以通过已经实现的基本操作运算执行有限次来实现的 4 输入算法有零个或多个输入 5 输出算法有一个或多个输出 算法设计的要求 一个 好 的算法应考虑达到以下目标 1 正确性指算法能满足具体问题的要求 对任何合法的输入 算法都会得出正确的结果 2 可读性算法主要是为了人的阅读和交流 其次才是机器执行 可读性好有助于人对算法的理解 并且晦涩难懂的程序易于隐藏较多错误难以调试和修改 3 健壮性当输入数据非法时 算法也能适当地做出反应或进行处理 而不会产生莫名其妙的输出结果 4 效率与低存储量要求效率指的是算法的执行时间 对于同一个问题如果有多个算法可以解决 执行时间短的算法效率高 存储量需求指算法执行过程中所需要的最大存储空间 这两者都与问题的规模有关 算法效率的度量 算法执行时间需要通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量 抛开与计算机硬件 软件相关的因素 一个用高级程序设计语言编写的程序在计算机上运行时所消耗的时间取决于两个因素 算法选用的策略和问题的规模 一个算法是由控制结构 顺序 分支和循环三种 和原操作 固有数据类型的操作 构成的 则算法时间取决于两者的综合效果 为了便于比较同一问题的不同算法 通常的做法是 从算法中选取一种对于所研究的问题来说是基本运算的原操作 以该基本操作重复执行的次数作为算法的时间量度 n n n n2 n2 n n3 例 一般情况下 对循环语句只考虑循环体语句的执行次数 而忽略该语句中步长加一 终值判别 循环转移等成份 因此 当有若干个循环语句时 算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的 在一个算法中 有些语句可能很少被执行 且与程序规模无关 在估算时间复杂度时 可以不考虑它们 一般只考虑与程序规模有关的语句的语句频度 某些语句的频度是随机量 它可能依赖于具体输入值或应用方式 在这种情况下 一般要分别讨论时间复杂度在最好情况下 最差情况下及一般情况下的值 由于算法的时间复杂度考虑的只是对于问题规模n的增长率 则在难以精确计算基本操作执行次数的情况下 只需求出它关于n的增长率即可 下面给出几种常见函数的比较关系 即当n充分大时 下列关系成立 O a O logn O n O nlogn O n2 O nm O an O n O nn 其中 n为自变量 a和m为常数 课堂练习 分析以下程序段的时间复杂度 其中n为为正整数 表示输入数据的规模 1 a n n 2 fori 1tondoj j n 3 for