数据结构.ppt

2020 1 3 1 数据结构 数据结构 2020 1 3 2 要求实现如下功能 录入学生信息 学号 姓名 选修 实验课 必修课成绩 查找功能 删除功能 修改功能 插入功能 排序功能 统计学生人数等功能 实例 学生管理系统 2020 1 3 3 数据结构 是计算机相关专业的一门重要的专业基础课 它主要研究计算机加工对象的逻辑结构 在计算机中的表示形式以及实现各种基本操作的算法 它是学习操作系统 编译原理 数据库原理等计算机专业核心课程的基础 掌握好这门课程的内容 是学习计算机其他相关课程的必备条件 开设背景 2020 1 3 4 课程讲述的主要内容本课程将分别讲述数据结构的基本概念 线性表 栈和队列 串和数组 树形结构 图结构 查找 排序和文件等内容 学习本课程的注意事项l上课认真听讲 l仔细阅读教材中的大量例题 从而体会并最终掌握数据结构中的基本概念 充分利用网络资源下载相关的算法 课件 代码 l独立完成上机作业 每次上机前均要独自编写代码 l独立完成每个章节后面的练习题 l要善于把书本上的伪代码写成真正的C语言代码 2020 1 3 5 关于习题与实验题 在每周都应该完成与上课内容相应的习题习题包括理论习题和上机实验题实验题要求用C语言编写 并在计算机上调试通过实验报告至少应包括题目算法步骤源程序 不太多时写在实验报告上 运算结果及分析调试过程与体会 2020 1 3 6 参考资料 1 数据结构 C语言版 清华大学出版社黄国瑜叶乃菁著2 数据结构 C语言篇 习题与解析清华大学出版社李春葆著3 数据结构教程上机实验指导清华大学出版社李春葆著4 数据结构 C 或JAVA语言版 清华大学出版社5 C语言程序开发范例宝典明日科技王娣等编 2020 1 3 7 网络资源 1 2020 1 3 8 联系方式 E Mail chunlin he QQ 93401318Phone2020 1 3 9 第1章绪论 本章主题 数据结构的基本概念和术语教学目的 了解数据结构的基本概念 理解常用术语教学重点 熟悉数据结构常用术语 掌握基本概念 了解算法时间复杂度和空间复杂度的分析与评价教学难点 数据元素间的4种结构关系 主要内容 1 1什么是数据结构1 2基本概念和术语1 3抽象数据类型的表示和实现1 4算法和算法分析 2020 1 3 10 1 1什么是数据结构 计算机解决问题的步骤实际问题 数学模型 算法 程序 结果工程师数学家程序员计算机的用途科学计算 数值运算 解方程 组 函数求值 概率统计等非数值运算 字符 表格 图象 声音等 2020 1 3 11 计算机的用途 数值运算 水库大坝的应力计算预报人口增长天气预报 2020 1 3 12 计算机的用途 非数值运算 书目检索系统 2020 1 3 13 多叉路口的交通灯管理问题 有连线的节点用不同的颜色标记 表示不能同时通行 要求使用的颜色数尽可能少 以使减少等待时间 2020 1 3 14 多叉路口的交通灯管理问题 不能同时通行的通路用连线把它们连起来 它们有 A B通路 CA BD BCA D通路 CB BCB C通路 AB ADB D通路 AB CBC A通路 ABC B通路 BD AD 2020 1 3 15 计算机的用途 非数值运算 计算机与人对奕问题 2020 1 3 16 1 1 1数据结构示例 例1 1 图书目录表由于表中每条记录 表示每一本书 的登录号各不相同 所以可用登录号来唯一地标识每条记录 一本图书 在计算机的数据管理中 能唯一地标识一条记录的数据项被称为关键字 因为每本图书的登录排列位置有先后次序 所以在表中会按登录号形成一种次序关系 即整个二维表就是图书数据的一个线性序列 这种关系被称为线性结构 2020 1 3 17 返回 返回 2020 1 3 18 描述磁盘目录和文件结构时 假设每个磁盘包括一个根目录 root 和若干个一级子目录 每个一级子目录中又包含若干个二级子目录 这种关系很像自然界中的树 所以称为目录树 如左图所示 例1 2 磁盘目录结构和文件管理系统 在这种结构中 目录和目录以及目录和文件之间呈现出一对多的非线性关系 即根root有多个下属 也称为后代 每一后代又有属于自己的后代 而任一个子目录或文件都只有一个唯一的上级 也称为双亲 称这种数学模型为树型数据结构 2020 1 3 19 例1 3 教学计划编排问题 假如一个教学计划中包含许多课程 在课程之间 有些必须按规定的先后次序排课 如 学C6课程必须先学C3课 学C3课程必须先学C1课 这些课程之间存在先修和后续的关系 在这种结构中 表示课程的数据之间呈现多对多的非线性关系 称这类数学模型为图形结构 2020 1 3 20 图结构还有 多岔路口交通灯的控制和管理 煤气管道的铺设造价等 通过以上几例可以认为 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系 并对这种结构定义相应的运算 而且确保经过这些运算后所得到的新结构仍然是原来的结构类型 2020 1 3 21 学科 数据结构 在计算机科学中所处的地位 综合性的专业基础课 2020 1 3 22 1 2基本概念和术语1 数据 Data 数据 Data 是对客观事物的符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 包括整型 实型 布尔型 字符 声音 文字 表格 图象等 例如 一个图书管理程序所要处理的数据可能是一张表格 如表1 1所示 2 数据元素 DataElement 数据元素 DataElement 是数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 一个数据元素可由若干个数据项组成 数据项是数据的不可分割的最小单位 2020 1 3 23 例如 在表1 1所示的图书目录表中 为了便于处理 把其中的每一行 代表一本书 作为一个基本单位来考虑 故该数据由7个数据项组成 一般情况下 一个结点中含有若干个字段 也叫数据项 字段是构成数据的最小单位 3 数据对象 DataObject 数据对象 DataObject 是性质相同的数据元素的集合 是数据的一个子集 例 整数集合 N 0 1 2 无限集 字符集合 C A B C Z 有限集 2020 1 3 24 4 数据类型 DataType 数据类型 DataType 是一个值的集合和定义在这个值集上的一组操作的总称 例如 整型 字符型 浮点型 双精度型等数据类型 分别是一组相同结构的值以及在这些值上允许进行操作的总称 如 在高级语言中 整数类型的取值范围为 32768 32767 运算符集合为加 减 乘 除 取模等 数据结构 DataTYPE 是相互之间存在一种或多种特定关系的数据元素的集合 2020 1 3 25 数据结构 DataStructure 数据结构是研究数据元素 DataElement 之间抽象化的相互关系 逻辑结构 和这种关系在计算机中的存储表示 物理结构 并对这种结构定义相适应的运算 设计出相应的算法 2020 1 3 26 数据结构主要指逻辑结构和物理结构 1 逻辑结构 数据之间的相互关系称为逻辑结构 通常分为4类基本结构 集合 结构中的数据元素除了同属于一种类型外 别无其它关系 见图 线性结构 结构中的数据元素之间存在一对一的关系 见图 树型结构 结构中的数据元素之间存在一对多的关系 见图 图状结构或网状结构 结构中的数据元素之间存在多对多的关系 见图 2020 1 3 27 四类数据基本结构的示意图 a 集合结构 b 线性结构 c 树型结构 d 图形结构 由以上例子可见 描述这类非数值计算问题的数学模型和方法不再是数学方程 而是诸如线性表 树和图之类的数据结构 2020 1 3 28 数据结构的形式定义为 数据结构是一个二元组 Data Structure D S 其中 D是数据元素的有限集 S是D上关系的有限集 例复数的数据结构定义如下 Complex C R 其中 C是含两个实数的集合 C1 C2 分别表示复数的实部和虚部 R P P是定义在集合上的一种关系 C1 C2 2020 1 3 29 2 存储结构 数据结构在计算机中的存储表示称为数据的存储结构 它包括数据元素的表示和关系的表示 表1 1所示的表格数据在计算机中可以有多种存储表示 数据既可以存放在一块连续的内存单元中 通过元素在存储器中的位置来表示它们之间的逻辑关系 顺序 也可以随机分布在内存中的不同位置 通过指针元素表示数据元素之间的逻辑关系 链式 这两种不同的表示方法对应有四种不同的存储结构 亦称方式 顺序存储结构 链式存储结构 索引存储结构和散列存储结构 2020 1 3 30 1 顺序存储结构是把逻辑上相邻的结点存储在物理上相邻的存储单元里 结点之间的逻辑关系由存储单元位置的邻接关系来体现 优点 占用较少的存储空间 缺点 由于只能使用相邻的一整块存储单元 因此可能产生较多的碎片现象 顺序存储结构通常借助程序语言中的数组来描述 顺序存储结构主要应用于线性的数据结构 2020 1 3 31 2 链式存储结构将结点所占的存储单元分为两部分 一部分存放结点本身的信息 另一部分存放结点的后继结点地址 结点间的逻辑关系由附加的指针字段表示 链式存储结构常借助于程序语言的指针类型描述 优点 不会出现碎片现象 充分利用所有的存储单元 缺点 每个结点占用较多的存储空间 3 索引存储方式是用结点的索引号来确定结点的存储地址 在储存结点信息的同时 要建立附加的索引表 优点 检索速度快 缺点 增加了附加的索引表 占用较多的存储空间 在增加和删除数据时需要修改索引表而花费较多时间 2020 1 3 32 4 散列存储方式是根据结点的关键字值直接计算出该结点的存储地址 通过散列函数把结点间的逻辑关系对应到不同的物理空间 优点 检索 增加和删除结点的操作都很快 缺点 当采用不好的散列函数时可能出现结点存储单元的冲突 为解决冲突需要附加时间和空间的开销 2020 1 3 33 数据类型 在一种程序设计语言中 变量所具有的数据种类 例1 在FORTRAN语言中 变量的数据类型有整型 实型 和复数型例2 在C语言中数据类型 基本类型和构造类型基本类型 整型 浮点型 字符型构造类型 数组 结构 联合 指针 枚举型 自定义数据对象 某种数据类型元素的集合 例3 整数的数据对象是 3 2 1 0 1 2 3 英文字符类型的数据对象是 A B C D E F 2020 1 3 34 5 抽象数据类型 AbstructDataType 简称ADT ADT是指一个数学模型以及定义在该模型上的一组的操作 可以看作是数据的逻辑结构及其在逻辑结构上定义的操作 抽象数据类型的定义仅取决于它的一组逻辑特性 而与其在计算机内部如何表示和实现无关 按其值不同特性 可细分为下列三种类型 原子类型 原子类型变量的值是不可再分解的 固定聚合类型 该类型的变量 其值由确定数目的成分按某种结构组成 可变聚合类型 该类型的变量 其 值 的成分的数目不明确 2020 1 3 35 抽象数据类型 AbstractDataType简称ADT 是指一个数学模型以及定义在该模型上的一组操作 一个含抽象数据类型的软件模块常含定义 表示和实现3个部分 抽象数据类型实际上就是对该数据结构的定义 因为它定义了一个数据的逻辑结构以及在此结构上的一组算法 用三元组描述如下 其中D是数据对象 S是D上的关系集 P是对D的基本操作 见P8 2020 1 3 36 1 3抽象数据类型的表示和实现预定义常量和类型 数据结构的表示用类型定义 typedef 描述 数据元素类型约定为ElemType 基本操作的算法用函数描述 赋值语句 选择语句 循环语句 结束语句 输入 输出语句 注释 基本函数 逻辑运算 2020 1 3 37 1 4算法和算法分析 1 算法的定义算法是对特定问题求解步骤的一种描述 是指令的有限序列 其中每一条指令表示一个或多个操作 2020 1 3 38 2 算法的特性算法是执行特定计算的有穷过程 这个过程有5个特点 1 有穷性 一个算法必须总是在执行有穷步之后结束 且每一步都在有穷时间内完成 也就是说当执行一个算法时 不论是何种情况 在经过了有限步骤后 这个算法一定要终止 2 确定性 算法中的每条指令都必须是清楚的 指令无二义性 且算法只有一个入口和一个出口 3 输入 具有0个或多个由外界提供的量 输入 这些输入取自于某个特定的对象集合 4 输出 产生1个或多个结果 这些输出是同输入有着某些特定关系的量 5 可行性 每条指令都充分基本 即 序列中的每个操作都是可以简单完成的 都可以通过已经实现的基本操作运算的有限次来实现 2020 1 3 39 1 4 2算法设计的要求评价一个好的算法有以下几个标准 1 正确性 Correctness 算法应满足具体问题的需求 2 可读性 Readability 算法应该好读 以有利于阅读者对程序的理解 3 健壮性 Robustness 算法应具有容错处理 当输入非法数据时 算法应对其作出反应 而不是产生莫名其妙的输出结果 2020 1 3 40 4 效率与存储量需求效率指的是算法执行的时间 存储量需求指算法执行过程中所需要的最大存储空间 一般 这两者与问题的规模有关 1 4 3算法效率的度量对一个算法要作出全面的分析可分成两个种方法 即事前分析和事后统计事前分析求出该算法的一个时间界限函数事后统计收集此算法的执行时间和实际占用空间的统计资料 O函数形式的定义 如果f n 是正常数n的一个函数 则xn O f n 表示存在一个正的常数M 使提当n n0 有 xn M f n 则时间量度记作T n O f n 2020 1 3 41 一般情况下 算法中基本操作重复执行的次数是问题规模n的某个函数 算法的时间量度记作T n O f n 称作算法的渐近时间复杂度 一般指简单算法中包含简单操作的次数 不必精确计算出算法的时间复杂度 只要大致计算出相应的数量级 如 O 1 O n O n2 O logn 等 定义 语句频度 是指该语句重复执行的次数 例 for I 1 I n I 频度为nfor j 1 j n j 频度为n c I j 0 for k 1 k n k 频度为nc I j a I k b k j 2020 1 3 42 由于是一个三重循环 每个循环从1到n 则总次数为 n n n n3时间复杂度为T n O n3 例 x s 0 将x自增看成是基本操作 则语句频度为 即时间复杂度为 1 如果将s 0也看成是基本操作 则语句频度为 其时间复杂度仍为 1 即常量阶 例 for I 1 I n I x s x 语句频度为 2n其时间复杂度为 O n 即时间复杂度为线性阶 2020 1 3 43 例 for I 1 I n I for j 1 j n j x s x 语句频度为 2n2其时间复杂度为 O n2 即时间复杂度为平方阶 例 for i 2 i n I for j 2 j i 1 j x a i j x 2020 1 3 44 语句频度为 1 2 3 n 2 1 n 2 n 2 2 n 1 n 2 2 n2 3n 2 时间复杂度为O n2 即此算法的时间复杂度为平方阶 一个算法时间为O 1 的算法 它的基本运算执行的次数是固定的 因此 总的时间由一个常数 即零次多项式 来限界 而一个时间为O n2 的算法则由一个二次多项式来限界 2020 1 3 45 作业 分析以下程序段的时间复杂度 for I 1 I n I y y 1 频度为n 1for j 0 j 2 n j x 频度为 n 1 2n 1 例 分析以下程序段的时间复杂度 I 1 频度为1while I n I I 2 若频度为f n 则有2f n n则f n log2n 2020 1 3 46 有如下递归函数fact n 分析其时间复杂度 Fact n If n 1 return 1 频度为1elsereturn n fact n 1 频度为T n 1 O 1 设fact n 的运行时间函数是T n 则构成一个递归函数 T n O 1 T n 1 n 1 O 1 T 1 n O 1 O n 2020 1 3 47 以下六种计算算法时间的多项式是最常用的 其关系为 O 1 O logn O n O nlogn O n2 O n3 指数时间的关系为 O 2n O n O nn 当n取得很大时 指数时间算法和多项式时间算法在所需时间上非常悬殊 因此 只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法 那就取得了一个伟大的成就 2020 1 3 48 有的情况下 算法中基本操作重复执行的次数还随问题的输入数据集不同而不同 例如 Voidbubble sort inta intn for I n 1 change TURE I 1change TURE 最好情况 0次 2020 1 3 49 最坏情况 1 2 3 n 1 n n 1 2平均时间复杂度为 O n2 1 4 4算法的存储空间需求空间复杂度 算法所需存储空间的度量 记作 S n O f n 其中n为问题的规模 或大小 2020 1 3 50 一个算法的空间复杂度是指算法运行从开始到结束所需的存储量 算法的存储量指的是算法执行过程中所需的最大存储空间 算法执行期间所需要的存储量应该包括以下三部分 1 输入数据所占空间 2 程序本身所占空间 3 辅助变量所占空间 类似于算法的时间复杂度 通常以算法的空间复杂度作为算法所需存储空间的量度 定义 S n O g n 称S n 为算法的空间复杂度 2020 1 3 51 1 4 4算法描述一个算法可以用自然语言 数字语言或流程图等来描述 也可以用计算机高级程序语言来描述 如Pascal语言 C语言或伪代码等 本书选用C语言作为描述算法的工具 1 用自然语言描述算法用日常的自然语言来描述算法 可以是英文 也可以是其它文字语言 优点 简单 便于人们对算法的阅读 缺点 不够严谨 2020 1 3 52 2 用流程图描述算法使用程序流程图 N S图等描述算法 特点是描述过程简洁 明了 目前在一些高级语言程序设计中仍然被采用 但用这两种方法描述的算法不能直接在计算机上执行 必须通过编程将它转换成可执行程序 3 用程序设计 C或C 语言描述算法可以直接使用程序设计语言 如C或C 描述算法 但直接使用程序设计语言不太容易且不直观 且需要借助于注释才能看明白 2020 1 3 53 为解决理解与执行的矛盾 常使用一种称为伪码 类 语言的描述方法来进行算法描述 类语言介于高级程序设计语言和自然语言之间 它忽略高级程序设计语言中一些严格的语法规则与描述细节 因此它比程序设计语言更容易描述和被人理解 而且比自然语言更接近程序设计语言 它虽然不能直接执行但很容易被转换成高级语言