北京邮电大学计算机学院数据结构第一章课件

张成文sfds bupt 北京邮电大学计算机学院 算法与数据结构 平时 作业 实验 期中 40 期末考试 闭卷 60 成绩评定标准 作业 概念 作业本实验 编程 电子版 两个要素 关于实验报告 电子版形式统一实验报告格式每次实验每人写一个实验报告每次实验报告在下次上课前提交 实验报告文档命名 个人word文档命名方式例子 实验1 班级 学号 名字 doc 按班级统一压缩文档命名方式例子 实验1 班级 rar 按班级统一发到指定邮箱 邮件标题例子 实验1 班级 每次实验登记 学习登记表 并一同发送到指定邮箱 实验报告内容要求 问题描述 算法描述 附加了足够注释的程序代码算法中使用的函数 过程 参数 变量的命名要能表示含义注意算法格式 层次嵌套 不同功能块之间留空 实验报告评分标准 文档命名报告内容是否齐全报告内容是否正确 数据结构 第1章绪论 8 第1章绪论 数据结构 第1章绪论 9 1 1学习数据结构的作用和意义 是为研究和解决如何有效地组织和处理非数值数据而产生的理论 技术和方法 数据结构 问题的数学模型算法 处理问题的策略程序设计 为计算机处理问题编制的一组指令集 数据结构 第1章绪论 10 例 查找某人的社会关系 计算机中如何表示 存储和操作 张三 李四 王五 陈六 赵七 数据结构 第1章绪论 11 1 2基本概念和术语 数据被计算机加工处理的对象 数据元素数据的基本单位 是数据集合中的一个个体 一个数据元素可由若干个数据项组成 数据项数据结构中讨论的数据的最小单位 原子项 数据结构 第1章绪论 12 数据对象性质相同的数据元素的集合 是数据的一个子集 学号姓名班号性别出生日期入学成绩001刘影01女19840417623002李恒01男19831211679003陈诚02男19840910638 数据结构具有结构的数据元素的集合 它包括数据对象的逻辑结构 存储结构和相适应的运算 结构的行为特征 数据元素 数据结构 第1章绪论 14 四种基本的逻辑结构 1 集合结构数据元素除了 属于同一集合 的联系之外 没有其它的关系 2 线性结构数据元素之间存在一对一的关系 3 树型结构数据元素之间存在一对多的关系 4 图状结构或网状结构数据元素之间存在多对多的关系 成员关系 长幼关系 管理关系 朋友关系 逻辑结构数据元素之间的逻辑关系 与计算机无关 数据结构 第1章绪论 15 存储结构 物理结构 指数据的逻辑结构在计算机存储器中的映象表示 数据元素的映象关系的映象 数据结构 第1章绪论 16 数据存储方式 数据元素关系的存储 的四种常用结构 1 顺序存储 数据元素依次放在连续的存储单元中 a1a2 ai an 2 链式存储 在存储结点中增加若干指针域 记录后继或者相关结点的地址 指针 a11220 a31342 a21072 10001004 100010041072107612201224 指针 结点 结点 数据结构 第1章绪论 17 3 索引存储 将数据元素分为若干子表 子表的开始位置存放在索引表中 索引表班级addr主表01102310354 4 散列存储 根据数据元素的关键字值 由散列函数计算出存储地址 LOC ai H key 432 713 王小二李一凡 1a12a2 31a31 数据结构 第1章绪论 18 运算 操作 在数据逻辑结构上定义的一组数据被使用的方式 其具体实现要在存储结构上进行 数据结构 第1章绪论 19 数据的逻辑结构 运算的定义 面向用户 抽象数据类型 概念层数据的存储结构 运算的实现 面向计算机实现层按照面向对象程序设计的观点 一种数据结构就是一个抽象数据类型的体现 在面向对象程序设计语言中 一种数据结构通常使用一个类 Class 进行封装 在非面向对象程序设计语言中 通常用结构 Structure 封装数据的存储结构 用函数 Function 封装一个运算的实现 分层模型 数据类型 datatype 一组值的集合以及定义在这个值集上的一组操作的总称 在高级语言中 数据类型通常又分为原子类型 atomicdatatype 和结构类型 structuraldatatype 原子类型 atomicdatatype 不可进一步分解的数据类型 结构类型 structuraldatatype 可进一步分解为原子类型或其它结构类型的数据类型 根据数据元素数目的不同又可分为固定聚合类型 fixed aggregatedatatype 和可变聚合类型 variable aggregatedatatype 抽象数据类型 AbstractDataType ADT 定义在一个抽象的数学模型上的数据类型及相应操作 它只取决于数据类型的逻辑特性 而与数据类型在计算机内的表示和实现无关 数据结构 第1章绪论 22 抽象数据类型的描述方法 其中基本操作的定义格式为 ADT抽象数据类型名 数据对象 数据对象的定义 数据关系 数据关系的定义 基本操作 基本操作的定义 ADT抽象数据类型名 基本操作名 参数表 初始条件 初始条件描述 操作结果 操作结果描述 数据结构 第1章绪论 23 例 抽象数据类型 复数 的定义 ADTComplex 数据对象 D e1 e2 e1 e2 RealSet 数据关系 R1 e1是复数的实数部分 e2是复数的虚数部分 基本操作 AssignComplex Z v1 v2 操作结果 构造复数Z 其实部和虚部分别被赋以参数v1和v2的值 DestroyComplex Z 操作结果 复数Z被销毁 GetReal Z realPart 初始条件 复数Z已存在 操作结果 用realPart返回复数Z的实部值 ADTComplex 数据结构 第1章绪论 24 1 3算法的描述和分析 1 3 1算法的概念建立在数据结构基础上的 求解问题的一系列确切的步骤 一个算法必须满足以下五个重要特性有穷性 对任何合法输入执行有穷步后能结束 确定性 每条指令必须有确切的含义 可行性 算法的每一条指令均能执行 输入 有零个或多个输入 输出 有一个或多个输出 数据结构 第1章绪论 25 评价算法优劣的基本标准正确性可读性健壮性高效性 高效率与低存储量 算法效率的度量时间复杂度空间复杂度 数据结构 第1章绪论 26 1 3 2算法的描述 数据结构是算法处理的对象 也是实现算法的基础 选择描述工具的原则不依赖于具体计算机与具体程序设计语言的一种形式化语言 可用于描述或表达算法思想 本课程采用类C语言或伪码语言特点它描述的算法自然易懂 具有较好的可移植性 算法格式void函数名 参数表 返回值的类型函数名 参数表 算法说明 算法说明 语句序列 语句序列 函数名 函数名 包括顺序 判定和重复三种基本控制结构和自然语言成分 数据结构 第1章绪论 27 赋值语句 变量名 表达式 变量名1 变量名2 变量名n 表达式 变量名1 变量名2 变量名n 表达式1 表达式2 表达式n 结构变量名 成员1值 成员2值 成员n值 数组变量名1 下标1 下标2 数组变量名2 下标3 下标4 变量名1 变量名2 变量名 条件表达式 表达式T 表达式F 条件语句 if 条件表达式 语句 else语句 if 条件表达式 语句 数据结构 第1章绪论 28 分情况语句 分支语句 switch 表达式 case值1 语句序列1 break case值2 语句序列2 break case值n 语句序列n break default 语句n 1 switch case条件1 语句序列1 break case条件2 语句序列2 break case条件n 语句序列n break default 语句n 1 数据结构 第1章绪论 29 循环语句 while 条件表达式 语句 do 语句序列 while 条件表达式 break 强制循环结束 continue 强制循环继续 for 赋初值表达式 条件 修改表达式 语句 数据结构 第1章绪论 30 输入输出语句 scanf 变量表 printf 变量表 转移语句 goto语句标号 引用语句 函数名 参量表 变量名 函数名 参量表 返回语句 return Return表达式 exit 异常代码 注释语句 注释内容 注释内容 数据结构 第1章绪论 31 1 3 3算法分析 算法效率的度量 一个具体问题的数据对象往往可以采用多种存储方式的一种 一个问题的解决又常常有多种可用的算法 数据结构 第1章绪论 32 通常有两种衡量算法效率的方法 事后统计法利用计算机内记时功能 不同算法的程序可以用一组或多组相同的统计数据区分 事前分析估算法时间复杂度 渐进时间复杂度 空间复杂度 缺点 必须执行程序其它因素掩盖算法本质 如何估算算法的时间复杂度 从算法中选取一种对所研究的问题来说执行最频繁的基本操作为原操作 当问题规模n相当大时 该原操作执行时间占算法总执行时间的绝大部分 所以 把该原操作在算法中重复执行的次数 频度 作为算法运行时间的衡量准则 可近似认为 算法的执行时间与原操作的频度成正比估算时间复杂度时取频度的阶次 时间复杂度 n问题规模 一般为数据的输入量算法的时间复杂度算法中各语句的频度之和T n T n O f n 大O表示法 时间复杂度 O的含义存在正的常数c和n0 使得当n n0时 0 T n c f n 表示随着问题规模n的增长 算法执行时间的增长率和f n 的增长率相同 称f n 为算法的渐近时间复杂度 简称时间复杂度 即 当n 时T n f n 常数 数据结构 第1章绪论 36 例1 交换i和j的内容 1 temp i 2 i j 3 j temp 解 T n 3记作T n O 1 常用的时间复杂度频率计数 算法中常用的时间复杂度频率计数有7种 O 1 常数型O n 线性型O n2 平方型O n3 立方型O 2n 指数型O log2n 对数型O nlog2n 二维型 按时间复杂度由小到大排列的频率表为 时间复杂度曲线 O 1 O log2n O n O nlog2n n2 O n3 O 2n 1 计算T n 2 从T n 中推断f n 时间复杂度计算步骤 数据结构 第1章绪论 40 例2 n n矩阵相乘的算法语句for i 1 i n i n 1for j 1 j n j n n 1 c i j 0 n2for k 1 k n k n2 n 1 c i j c i j a i k b k j n3 解 语句频度T n 2n3 3n2 2n 1当n n0 1时 有T n 8n3 即c 8 由此取f n n3则T n O n3 算法中存在循环时 通常由嵌套层数最深的循环语句的最内层语句决定 1 问题的规模2 输入实例的初态 影响算法时间复杂度的因素 最坏时间复杂度 定义 算法在最坏情况下的时间复杂度 即为分析估计算法在最坏情况下执行时间的上界 数据结构 第1章绪论 43 例3 在数组A 1 n 查找给定值K 1 i n 2 while i 1 解 最好情况的时间复杂度T n O 1 最坏情况的时间复杂度T n O n 平均时间复杂度 所有可能的输入实例以等概率出现的情况T n 1 2 n n O n 算法与数据状态有关时 需讨论不同情况 1 n 数据结构 第1章绪论 44 2 空间复杂度算法的存储空间输入数据所占空间程序本身所占空间辅助变量所占空间空间复杂度S n O f n 表示随着问题规模n的增大 算法运行所需存储量的增长率与f n 的增长率相同 存储密度d 数据本