绪论数据结构教程PPT课件.ppt

开设本课程的背景 数据结构 是计算机相关专业的一门重要的专业基础课 它主要研究计算机加工对象的逻辑结构 在计算机中的表示形式以及实现各种基本操作的算法 学好这门课 可以加深对程序设计的理解 有助于进一步提高程序设计能力 为进行软件开发打下良好的基础 并为计算机专业后续课程 如数据库操作系统编译原理 软件工程等课程奠定良好的基础 本课程讲述的主要内容本课程将分别讲述数据结构的基本概念 线性表 栈和队列 串和数组 树形结构 图结构 查找 排序等内容 学习本课程的基本方法上课认真听讲 仔细阅读教材中的大量例题 从而体会并最终掌握数据结构中的基本概念 认真上机实习 独立完成每个章节后面的练习题 第1章绪论 教学目的了解数据结构基本概念的含义了解数据结构研究的主要内容理解数据逻辑结构及存储结构的定义及分类理解算法的概念 描述方法以及评价标准掌握时间复杂度与空间复杂度的计算 1 1数据结构的概念1 2算法描述1 3算法分析 第1章绪论 1 1数据结构的概念 当今计算机应用的特点 l所处理的数据量大且具有一定的关系 l对其操作不再是单纯的数值计算 而更多地是需要对其进行组织 管理和检索 应用举例1 学籍档案管理假设一个学籍档案管理系统应包含如下表1 1所示的学生信息 表1 1 特点 l每个学生的信息占据一行 所有学生的信息按学号顺序依次排列构成一张表格 l表中每个学生的信息依据学号的大小存在着一种前后关系 这就是我们所说的线性结构 l对它的操作通常是插入某个学生的信息 删除某个学生的信息 更新某个学生的信息 按条件检索某个学生的信息等等 应用举例2 输出n个对象的全排列输出n个对象的全排列可以使用下图1 1所示的形式描述 图1 13个对象的全排列过程 特点 l在求解过程中 所处理的数据之间具有层次关系 这是我们所说的树形结构 l对它的操作有 建立树形结构 输出最低层结点内容等等 应用举例3 制定教学计划在制定教学计划时 需要考虑各门课程的开设顺序 有些课程需要先导课程 有些课程则不需要 而有些课程又是其他课程的先导课程 比如 计算机专业课程的开设情况如下表1 2所示 表1 2 课程先后关系的图形描形式 图1 2计算机专业必修课程开设先后关系 特点l课程之间的先后关系用图结构描述 l通过实施创建图结构 按要求将图结构中的顶点进行线性排序 结论计算机的操作对象的关系更加复杂 操作形式不再是单纯的数值计算 而更多地是对这些具有一定关系的数据进行组织管理 我们将此称为非数值性处理 要使计算机能够更有效地进行这些非数值性处理 就必须弄清楚这些操作对象的特点 在计算机中的表示方式以及各个操作的具体实现手段 这些就是 数据结构 这门课程研究的主要内容 数据是对客观事物的符号表示 在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合 数据元素 DataElement 数据元素是组成数据的基本单位 是数据集合的个体 在计算机中通常作为一个整体进行考虑和处理 学籍表 数据项 记录 数据项 具有独立含义的最小数据标识单位 数据结构数据结构的内容可归纳为三个部分 逻辑结构 存储结构和运算集合 按某种逻辑关系组织起来的一批数据 按一定的映象方式把它存放在计算机的存储器中 并在这些数据上定义了一个运算的集合 就叫做数据结构 逻辑结构数据结构中所说的 关系 实际上是指数据元素之间的逻辑关系 又称此为逻辑结构 常见的逻辑结构有 线性结构 树形结构和图形结构 集合 四个基本逻辑结构集合线性结构树形结构图 逻辑结构可看作是从具体问题抽象出来的数学模型 存储结构 物理结构 是指数据结构在计算机存储器中的具体实现 与孤立的数据元素表示形式不同 数据结构中的数据元素不但要表示其本身的实际内容 还要表示清楚数据元素之间的逻辑结构 常见的存储结构顺序存储结构 逻辑上相邻的元素存储在物理位置相邻的存储单元中 通常借助于程序设计语言中的数组来实现 链式存储结构 逻辑上相邻的元素不要求其物理位置相邻 元素间的相邻关系借助于指示数据元素地址的指针来实现 数据结构 逻辑结构 存储结构 数据运算 算法 线性结构 树 图 集合 链式存储结构 顺序存储结构 1 2算法描述 1 2 1算法的概念算法是解决某个特定问题的一种方法或一个过程 计算机对数据的操作可以分为数值性和非数值性两种类型 在数值性操作中主要进行的是算术运算 而在非数值性操作中主要进行的是检索 排序 插入 删除等等 编写程序的基本过程l通过对问题进行详细地分析 抽象出相应的数学模型 l确定使用的数据结构 并在此基础上设计对此数据结构实施各种操作的算法 l选用某种语言将算法转换成程序 l调试并运行这些程序 算法应该具有下列五个特性 1 有穷性 一个算法必须在执行有穷步之后结束 2 确定性 算法中的每一步 必须有确切的含义 在他人理解时不会产生二义性 3 可行性 算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现 4 输入 一个算法应该有零个或多个输入 5 输出 一个算法应该有一个或多个输出 这里所说的输出是指与输入有某种特定关系的量 举例问题 按从小到大的顺序重新排列x y z三个数值的内容 算法 1 输入x y z三个数值 2 从三个数值中挑选出最小者并换到x中 3 从y z中挑选出较小者并换到y中 4 输出排序后的结果 1 2 2算法的描述算法描述分为以下4种 1 框图算法描述 程序流程图 N S流程图 2 非形式算法描述 3 伪语言算法描述 4 高级语言编写的程序或函数 算法的评价标准 1 正确性 要求算法能够正确地执行预先规定的功能 并达到所期望的性能要求 2 可读性 为了便于理解 测试和修改算法 算法应该具有良好的可读性 3 健壮性 算法中拥有对输入数据 打开文件 读取文件记录 分配内存空间等操作的结果检测 并通过与用户对话的形式做出相应的处理选择 4 时间与空间效率 算法的时间与空间效率是指将算法变换为程序后 该程序在计算机上运行时所花费的时间及所占据空间的度量 1 3算法分析 算法的时间效率算法的时间效率主要由两个因素决定 l所需处理问题的数据量大小 数据量大 所花费的时间就多 l在解决问题的过程中 基本操作的执行次数 时间特性的分析如果我们将一个算法所花费的时间设计成一个以数据量n为自变量的函数T n 这个函数在正整数定义域范围内一定是单调递增的 好的算法应该能够在数据量n增长的同时 函数T n 的增长速度比较缓慢 一般情况下 算法中基本操作重复执行的次数是问题规模n的某个函数 算法的时间量度记作T n O f n 称作算法的渐近时间复杂度 例1 x s 0 将x自增看成是基本操作 s 0也看成是基本操作 则时间复杂度为 2 即常量阶 例2 for i 1 i n i x s x 基本操作出现的次数 频度 为 2n其时间复杂度为 O n 即时间复杂度为线性阶 例3 for i 1 i n i for j 1 j n j x s x 基本操作执行的次数 语句频度 为 2n2其时间复杂度为 O n2 即时间复杂度为平方阶 例4 for i 2 i n i for j 1 j i 1 j x a i j x 语句频度为 2 1 2 3 n 1 2 1 n 1 n 1 2 2 n n 1 2 n2 n 时间复杂度为O n2 即此算法的时间复杂度为平方阶 总之 算法时间复杂度计算 算法中基本操作的重复执行的次数 它是问题规模n的某个函数f n 记作T n O f n 若无循环语句及过程调用 则为O 1 若有循环语句 则找出最内层语句的执行次数 求出其数量级即可 忽略所有的常数和低次项 以下六种计算算法时间的多项式是最常用的 其关系为 O 1 O log2n O n O nlog2n O n2 O n3 指数时间的关系为 O 2n O n O nn 空间效率的分析一个算法的空间效率是指在算法的执行过程中 所占据的辅助空间数量 辅助空间就是除算法代码本身和输入输出数据所占据的空间外 算法临时开辟的存储空间单元 在有些算法中 占据辅助空间的数量与所处理的数据量有关 而有些却无关 后一种是较理想的情况 在设计算法时 应该注意空间效率 课堂提问 简述逻辑结构 存储结构的定义 常见的逻辑结构和存储结构有哪些 一个算法的时间复杂度为 3n2 2nlog2n 4n 7 5n 其时间复杂度为 A O n B O nlog2