实用数据结构第一章绪论.ppt

1 数据结构DataStructure主讲 龚梦2012年9月 2 学时数 68h 教材 陈元春等 实用数据结构基础 中国铁道出版社 2011参考书 1 严蔚敏等 数据结构 C语言版 清华大学出版社 2007年4月 22 2 朱战立 数据结构 JAVA语言描述 清华大学出版社 2005年12月 25 3 丁宝康等 数据结构自学考试指导 清华大学出版社 2001年5月 23 内容安排 4 数据结构课程的地位 是介于数学 计算机硬件和计算机软件三者之间的一门核心课程 关系 对象关系操作 对象关系操作 5 第1章数据结构的基本概念 1 1何谓数据结构1 2算法与伪码 简 1 3程序结构化与设计风格 略 1 4程序分析的方法1 5时间复杂度分析1 6渐近式表示法 只讲大O表示法 1 7递归式的复杂度计算 略 重点 6 1 1数据结构基本概念 Q1什么是数据结构 Q2学习数据结构有什么用 Q3数据结构涵盖的主要内容 讨论 7 Q1 什么是数据结构 答 是相互之间存在一种或多种特定关系的数据元素的集合 表示为 数值或非数值 Data Structure D S 或 是指同一数据元素类 数据实体 中各元素之间存在的关系 亦可表示为 S D R 元素有限集 关系有限集 8 术语 数据 数据元素和数据项 数据 data 所有能被计算机识别 存储和处理的符号的集合 包括数字 字符 声音 图像等信息 数据元素 dataelement 是数据的基本单位 具有完整确定的实际意义 又称元素 结点 顶点 记录等 数据项 Dataitem 构成数据元素的项目 是具有独立含义的最小标识单位 又称字段 域 属性等 三者之间的关系 数据 数据元素 数据项 例 班级通讯录 个人记录 姓名 年龄 9 Q2 学习数据结构有什么用 答 计算机内的数值运算依靠方程式 而非数值运算 如表 树 图等 则要依靠数据结构 这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科 程序设计实质 好算法 好结构 同样的数据对象 用不同的数据结构来表示 运算效率可能有明显的差异 Q3 数据结构涵盖的内容 解释1 什么叫数据的逻辑结构 答 指数据元素之间的逻辑关系 即从逻辑关系上描述数据 它与数据的存储无关 是独立于计算机的 逻辑结构可细分为4类 集合结构 仅同属一个集合线性结构 一对一 1 1 树结构 一对多 1 n 图结构 多对多 m n 非线性 线性 12 例 用图形表示下列数据结构 并指出它们是属于线性结构还是非线性结构 1 S D R D a b c d e f R a e b c c a e f f d 解 上述表达式可用图形表示为 bcaefd 此结构为线性的 2 S D R D di 1 i 5 R di dj i j d1d5d2d4d3 该结构是非线性的 解 上述表达式可用图形表示为 14 解释2 什么叫数据的物理结构 答 物理结构亦称存储结构 是数据的逻辑结构在计算机存储器内的表示 或映像 它依赖于计算机 存储结构可分为4大类 例 复数3 0 2 3i的两种存储方式 顺序 链式 索引 散列 法1 地址内容 法2 地址内容 2字节 15 解释3 什么是数据的运算 答 在数据的逻辑结构上定义的操作算法 它在数据的存储结构上实现 最常用的数据运算有5种 插入 删除 修改 查找 排序 16 1 2算法与伪码 Q1 什么是算法 Q2 算法的表示方式有哪些 讨论 程序设计实质 好算法 好结构 答 算法是解决某一特定类型问题的有限运算序列 是一系列输入转换为输出的计算步骤 常用时间复杂度来衡量 1 什么是算法 算法有5个基本特性 算法评价有4个指标 有穷性 确定性 可行性 输入和输出 运行时间 占用空间 正确性和简单性 常用空间复杂度来衡量 18 算法的特性 有穷性 按照算法所描述的步骤执行 在有限的步骤内 一定会结束 确定性 每一个步骤的语句必须很明确 可行性 算法中的每一个步骤必须是可执行的基本指令 即使是用纸笔也能完成的计算 输入 一个算法有零个或多个输入数据 输出 一个算法有一个或多个输出数据 19 1条列式的步骤2流程图3伪码4程序语句 2 算法的表示方式有哪些 20 条列式 以条列式的步骤来描述解决问题的方法 流程图 以图形符号来描述问题的解决方法 伪码 以夹杂程序语法和自然语言来描述解决问题的方法 程序语句 直接以程序语法来描述解决问题的方法 21 1 4程序分析的方法 算法效率的分析 用依据该算法编制的程序在计算机上执行所消耗的时间来度量 程序的执行效率的分析也就是 22 利用计算机内记时功能 不同算法的程序可以用一组或多组相同的统计数据区分缺点 必须先运行依据算法编制的程序 所得时间统计量依赖于硬件 软件等环境因素 掩盖算法本身的优劣 1 事后统计 23 一个高级语言程序在计算机上运行所消耗的时间取决于 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度同一个算法用不同的语言 不同的编译程序 在不同的计算机上运行 效率均不同 所以使用绝对时间单位衡量算法效率不合适 2 事前分析估计 24 讨论 那如何进行事前分析 为了能以相同的标准来进行程序效率分析 我们常常以执行次数来作为程序效率分析的方式 例1 n n矩阵相乘for i 1 i n i for j 1 j n j c i j 0 执行了n n次for k 1 k n k c i j c i j a i k b k j 执行了n n n次 一共执行了 n n n n n 次 25 1 5时间复杂度分析 一个特定算法的 运行工作量 的大小 只依赖于问题的规模 通常用整数量n表示 或者说 它是问题规模的函数 假如 随着问题规模n的增长 算法执行时间的增长率和f n 的增长率相同 则可记作 T n O f n 称T n 为算法的 渐近 时间复杂度 如何估算算法的时间复杂度 算法的执行时间 原操作 i 的执行次数 原操作 i 执行时间算法的执行时间与原操作执行次数之和成正比从算法中选取一种基本操作 以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则 频度 FrequencyCount 指该语句重复执行的次数例如 s 0 x s 0 将x自增看成是基本操作 则语句频度为 即时间复杂度为 1 如果将s 0也看成是基本操作 则语句频度为 其时间复杂度仍为O 1 即常量阶 例如 for i 1 i n i x s x 语句频度为 2n其时间复杂度为 O n 即时间复杂度为线性阶 算法的时间复杂度是指算法中所有语句的频度之和 记为f n 求O的数学定义 则称函数f n 与g n 同阶 或者说 f n 与g n 为同一个数量级 记作 f n O g n 渐进符号 O 的定义 当且仅当存在一个正的常数C 使得对所有的n n0 有f n Cg n 则f n O g n 3n 2 O n 3n 2 4n当n 2 3n 3 O n 3n 3 4n当n 3 100n 6 O n 100n 6 101n当n 10 10n2 4n 2 O n2 10n2 4n 2 11n2当n 5 6 2n n2 O 2n 6 2n n2 7 2n当n 4 例 时间复杂度T n 按数量级递增顺序为 注1O 为渐近符号 复杂度高 复杂度低 例如 for I 1 I n I for j 1 j n j x s x 语句频度为 2n2其时间复杂度为 O n2 即时间复杂度为平方阶 定理 若A n amnm am 1nm 1 a1n a0是一个m次多项式 则A n O nm 证略 语句频度为 1 2 3 n 2 1 n 2 n 2 2 n 1 n 2 2 n2 3n 2 时间复杂度为O n2 例 for i 2 i n i for j 2 j i 1 j x a i j x 例 分析以下程序段的时间复杂度 i 1 while i n i i 2 该算法的运行时间由程序中所有语句的频度 即该语句重复执行的次数 之和构成 解 分析 显然 语句 的频度是1 设语句 的频度是f n 则有 即f n log2n 取最大值f n log2n 所以该程序段的时间复杂度T n 1 f n 1 log2n O log2n 例 两个n阶矩阵的乘法C A B 算法如下 defineMAX100voidmatrixmult intn floata MAX MAX floatb MAX MAX floatc MAX MAX inti j k floatx for i 1 i n i for j 1 j n j x 0 for k 1 k n k x a i k b k j c i j x n 1 n n 1 n2 n2 n 1 n3 n2 该算法中主要语句的频度分别是 n 1 n n 1 n2 n2 n 1 n3 n2则时间复杂度为所有语句的频度之和f n 2n3 4n2 2n 1 O n3 可见 算法的时间复杂度是由嵌套最深层语句的频度决定的 学会分析方法 for i 1 i n i for j 1 j i j for k 1 k j k 语句频度 X 91 y 100 while y 0 if x 100 x 10 y elsex 语句 实质是 while x 100 x x 10 y 内循环次数为10 外循环次数为100 语句 的频度应为1100