数据结构使用C语言朱战立.ppt

教材 朱战立编著 数据结构 使用C语言 第3版 西安交通大学出版社 2003年 数据结构 2 学时数 70 50学时授课 20学时上机 教材 朱战立编著 数据结构 使用C语言 第3版 西安交通大学出版社 2003年参考书 1 严蔚敏等 数据结构 C语言版 清华大学出版社 2 数据结构学习指导与典型题解 朱战立等编著 西安交通大学出版社 2002年 3 内容安排 4 1 上课认真听讲 适当做好笔记 2 考试成绩分两部分 平时成绩 包括出勤和上机实验 占20 期末成绩占80 3 课后需要多读课文和参考书 上网查看相关内容 在理解基本内容的基础上 多看 多做习题 4 上机实验十分重要 一定要在上机前做好充分准备 多采用不同的数据存储结构和不同的实现算法解决一个问题 对学生的几点要求 5 第1章绪论 讨论5个问题 1 1数据结构的基本概念1 2抽象数据类型和软件构造方法1 4算法和算法的时间复杂度1 5算法书写规范 6 1 1数据结构的基本概念 1 举例建立一个学生档案系统 学生表包括学号 姓名 性别 籍贯 要求 查找 王红 是否存在 解决的方法步骤 如何记录所有学生记录 及选择何种逻辑数据结构 选择何种存储结构 若把所有记录依次存储在一个数组中 采用顺序存储结构若采用指针链表 采用链式存储结构 7 为什么要学习数据结构 什么是程序 软件 N 沃思 NiklausWirth 教授提出 程序 算法 数据结构以上公式说明了如下两个问题 1 数据上的算法决定如何构造和组织数据 算法 数据结构 2 算法的选择依赖于作为基础的数据结构 数据结构 算法 软件 程序 文档 软件工程的观点 8 电子计算机的主要用途 早期 主要用于数值计算 后来 处理逐渐扩大到非数值计算领域 能处理多种复杂的具有一定结构关系的数据 数值计算解决问题的一般步骤 数学模型 选择计算机语言 编出程序 测试 最终解答 数值计算的关键是 如何得出数学模型 方程 程序设计人员比较关注程序设计的技巧 非数值计算问题 数据元素之间的相互关系一般无法用数学方程加以描述 10 例1 1电话号码查询问题 1 按顺序存储方式 须遍历表 2 按姓氏索引方式 索引要写出好的查找算法 取决于这张表的结构及存储方式 电话号码表的结构和存储方式决定了查找 算法 的效率 非数值计算问题 11 例1 2田径赛的时间安排问题 无向图的着色问题 设有六个比赛项目 规定每个选手至多可参加三个项目 有五人报名参加比赛 如下表所示 设计比赛日程表 使得在尽可能短的时间内完成比赛 非数值计算问题 12 1 设用如下六个不同的代号代表不同的项目 跳高跳远标枪铅球100米200米ABCDEF 2 用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边 3 某选手比赛的项目必定有边相连 不能同时比赛 非数值计算问题 田径赛的时间安排问题解法 13 只需安排四个单位时间进行比赛 14 非数值计算问题 主要考虑的是设计出合适的数据结构及相应的算法 即 首先要考虑对相关的各种信息如何表示 组织和存储 因此 可以认为 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科 15 数据结构课程的形成和发展 形成阶段 60年代初期 数据结构 有关的内容散见于操作系统 编译原理和表处理语言等课程 1968年 数据结构 被列入美国一些大学计算机科学系的教学计划 发展阶段 数据结构的概念不断扩充 包括了网络 集合代数论 关系等 离散数学结构 的内容 70年代后期 我国高校陆续开设该课程 16 17 数据结构课程的地位 它是计算机专业及相关专业的核心课程之一 是计算机及相关专业的重要骨干基础课程 它针对非数值计算的程序设计问题 研究计算机的操作对象以及它们之间的关系和操作 即其研究目的是研究有效地组织和处理非数值类型数据的理论 技术和方法 18 数据结构课程 所处的地位 19 数据结构的核心研究内容 数据的逻辑结构 存储结构及它们之间的关系和相应的基本操作运算的定义和实现 本书围绕数据结构的三种基本结构 线性结构 第2 5章 树形结构 第7章 和图形结构 第8章 展开讨论 研究解决如下问题 一个具体问题的逻辑数据结构是什么 适宜选用什么样的存储结构 采用什么样的操作实现算法效率更高 20 2 基本术语 1 数据 所有能被计算机识别 存储和处理的符号的集合 包括数字 字符 声音 图像等信息 2 数据元素 是数据的基本单位 具有完整确定的实际意义 在计算机程序中通常作为一个整体进行考虑和处理 一个数据元素可由若干个数据项组成 3 数据项 构成数据元素的项目 它是数据不可分割的最小单位 4 数据类型 指一个类型和定义在这个类型上的操作集合 例 C语言 基本类型 整型 浮点型 字符型等构造类型 数组 结构 联合 指针 枚举等 5 抽象数据类型 AbstructDataType 简称ADT 是指一个数学模型以及定义在该模型上的一组操作 抽象数据类型的定义取决于它的一组逻辑特性 而与其在计算机内部如何表示和实现无关 即不论其内部结构如何变化 只要它的数学特性不变 都不影响其外部的使用 6 抽象数据元素 抽象定义的 没有实际含义的数据元素 21 22 2 基本术语 续 7 数据结构 是相互之间存在一种或多种特定关系的数据元素的集合 或按照一定逻辑关系组织 并按一定存储方法存储的数据的集合 且需要定义一系列运算 逻辑结构 存储结构和运算合称为三要素 表示为 Data Structure D R 其中 D 元素有限集 R 关系有限集 23 数据结构涵盖的内容 24 集合结构 仅同属一个集合线性结构 一对一 1 1 树结构 一对多 1 n 图结构 多对多 m n 非线性 线性 逻辑结构可细分为4类 答 指数据元素之间的逻辑关系 即从逻辑关系上描述数据 它与数据的存储无关 是独立于计算机的 解释1 什么叫数据的逻辑结构 25 1 S D R D a b c d e f R a e b c c a e f f d 解 上述表达式可用图形表示为 bcaefd 此结构为线性的 例 用图形表示下列数据结构 并指出它们是属于线性结构还是非线性结构 26 d1d5d2d4d3 该结构是非线性的 解 上述表达式可用图形表示为 2 S D R D di 1 i 5 R di dj i j 27 答 物理结构亦称存储结构 是数据的逻辑结构在计算机存储器内的表示 或映像 它依赖于计算机 存储结构可分为4大类 例 复数3 0 2 3i的两种存储方式 顺序 链式 索引 散列 法1 地址内容 法2 地址内容 2字节 解释2 什么叫数据的物理结构 28 答 在数据的逻辑结构上定义的操作算法 它在数据的存储结构上实现 最常用的数据运算有5种 插入 删除 修改 查找 排序 解释3 什么是数据的运算 练习1 设有数据逻辑结构为 line D R 其中D 01 02 03 04 05 06 R r r 试分析该数据结构属于哪种逻辑结构 01 02 05 04 06 03线性结构 29 2 设有数据逻辑结构为tree D R 其中D 01 02 03 04 05 06 07 08 R r r 试分析该数据结构属于哪种逻辑结构 树型 30 作业 什么是逻辑结构与存储结构 他们之间的关系如何 31 设有数据逻辑结构为 line D R 其中D a b c d e f g R r r 试画出对应的图形并说明属于哪种逻辑结构 32 将上述关系改为r 试画出对应的图形并说明属于哪种逻辑结构 33 34 1 4什么是抽象数据类型 1数据类型与抽象数据类型的区别 2抽象数据类型如何定义 3抽象数据类型如何表示和实现 讨论 35 1数据类型与抽象数据类型的区别 数据类型 是一个值的集合和定义在该值上的一组操作的总称 抽象数据类型 由用户定义 用以表示应用问题的数据模型 它由基本的数据类型构成 并包括一组相关的服务 或称操作 它与数据类型实质上是一个概念 但其特征是使用与实现分离 实行封装和信息隐蔽 独立于计算机 36 2抽象数据类型如何定义 抽象数据类型可以用以下的三元组来表示 ADT D R P ADT抽象数据类型名 数据对象 数据关系 基本操作 ADT抽象数据类型名 ADT常用定义格式 数据对象 D上的关系集 D上的操作集 37 1 4 3抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型 如整型 实型 字符型等 来表示和实现 参看课本P28 线性表的抽象数据类型 思考用具体C语言如何实现 注意 上机时要必须用具体语言实现 如C或C 等 队列的抽象数据类型定义ADTQueue 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 1 2 n 约定a1为队列头 an为队列尾 基本操作 InitQueue Q 操作结果 构造一个空队列Q DestroyQueue Q 初始条件 队列Q已存在 操作结果 销毁队列Q QueueLength Q 初始条件 队列Q已存在 操作结果 返回Q的数据元素个数 即队列的长度 38 39 1 5算法效率的度量 1什么是算法 如何评判算法的好坏 2时间复杂度和空间复杂度如何表示 3计算举例 讨论 40 1什么是算法 如何评判一个算法的好坏 常用时间复杂度来衡量 算法的基本特性 算法评价指标 有穷性 确定性 可行性 必有输出 正确性 可读性 健壮性 高效率与低存储量需求 见课本P20 常用空间复杂度来衡量 好的程序设计 好算法 好结构 算法 是对特定问题求解步骤的一种描述 它是指令的有限序列 是一系列输入转换为输出的计算步骤 有穷性 一个算法必须总是 对任何合法的输入值 在执行有穷步之后结束 且每一步都可在有穷时间内完成 确定性 每条指令必须有确切的含义可行性 算法是能行得通的必有输出 41 正确性 算法应当满足具体问题的需求可读性 算法的可读性有利于人们对算法的理解健壮性 当输入数据非法时 算法也能适当地做出反应或进行处理 而不会产生莫名其妙的结果 效率与低存储需求 时间短 存储空间少 两者不能兼得 42 1 3 3算法效率的度量 求解同一个问题 可以有许多不同的算法 究竟如何评价这些算法的好坏呢 显然 选用的算法首先应该是 正确的 此外 主要考虑如下三点 1 执行算法所消耗的时间 2 执行算法所消耗的存储空间 其中主要考虑辅助存储空间 3 算法应该易于理解 易于编码 易于调试等 43 时间复杂度 timecomplexity 语句频度 FrequencyCount 语句重复执行的次数语句的执行时间语句频度 执行一次所需时间算法的执行时间所有语句执行时间的总和算法的渐近时间复杂度 asymptotictimecomplexity 简称时间复杂度因为语句的执行时间取决于机器的硬件速度 指令类型 以及编译所产生的代码质量 所以将算法中基本操作的最大语句频度作为算法执行时间的量度 它是问题规模n的某个函数f n 44 时间复杂度表示法记作T n O f n 称为大O表示法 表示随问题规模n的增大 算法执行时间的增长率和f n 的增长率相同 时间复杂度往往不是精确的执行次数 而是估算的数量级 它着重体现的是随着问题规模n的增大 算法执行时间的变化趋势时间复杂度的数量级O 1 O log2n O n O nlog2n O n2 O n3 O 2n O 3n O n 例如在下列三个程序段中 a x x 1 b for i 1 i n i x x 1 c for j 1 j n j for k 1 k n k x x 1 基本语句均为x x 1 程序段 a 中频度为1 则T n O 1 程序段 b 中频度为n 则T n O n 程序段 c 中频度为n2 则T n O n2 时间复杂度的求解 算法1 1的时间复杂度voidsort ElemTypeS MAXSIZE intn 对数组S中的n个数据按由大到小的顺序排序并输出 n MAXSIZE for i 1 i n i for j i j n j if S i score S j score t S i S i S j S j t for i 1 i n i printf 8d 8d 8d n i S i no S i score sort 算法中if语句的执行频度为 n n 1 n 2 3 2 1 n n 1 2 T n O n2 加法规则 针对并列程序段 T n m T1 n T2 m O max f n g m 乘法规则 针对嵌套程序段 T n m T1 n T2 m O f n g m 算法1 1中既有并列程序段又有嵌套程序段并列程序段 T n O max n2 n O n2 嵌套程序段 T n O f n g n O n2 有的情况下 算法中基本操作重复执行的次数还随问题的输入数据集不同而不同 例如 Voidbubble sort inta intn for i 1 ia j 1 flag 1 a j a j 1 分析算法复杂度 最好情况 0次最坏情况 1 2 3 n 1 n n 1 2平均时间复杂度为 O n2 50 空间复杂度度量 SpaceComplexity 空间是指执行算法所需用的存储空间存储空间的固定部分程序指令代码的空间 常数 简单变量 定长成分 如数组元素 结构成员等 变量所