绪论信息技术算法和程序福建教师招考.ppt

数据结构 力为运动商城整理 参考书目 数据结构 高等教育出版社刘大有 唐海鹰 孙舒杨 虞强源 杨鲲编著 数据结构C 语言描述 清华大学出版社WilliamFord WilliamTopp著刘卫东 沈官林译严蔚敏审 数据结构程序设计题典 清华大学出版社李春葆 曾惠 张植民编著 力为运动商城整理 目录 第一章绪论 第二章线性表 第三章栈和队列 第四章串 第五章数组和广义表 力为运动商城整理 第七章图 第八章查找 第九章排序 期末复习 第六章树 第一章绪论 知识点数据结构中常用的基本概念和术语算法描述和分析方法难点算法复杂度的分析方法要求了解数据的逻辑结构和存储结构 算法的基本概念 它们对于程序设计的重要性以及相互关系掌握算法时间复杂度的概念及分析方法 力为运动商城整理 02080 3班号0595 2918327办公室电话号码362000泉州邮编35010219830607748身份证号码 例1 02080 33501021983060774805952918327362000 结论1 杂乱的数据不能表达和交流信息 什么是数据结构 力为运动商城整理 例2 电话号码簿 a1 b1 a2 b2 an bn 其中 ai为某人姓名 bi为该人的电话号码 要求 设计一个算法 给定一个姓名时 能查出此人的电话号码 如果姓名和电话号码的排列次序无规律 则只能逐一比较姓名进行查找如果姓名按字典顺序组织 则查找就快捷多了 结论2 数据之间是有联系的这些联系常常影响算法的选择和效率 DS 就是要研究数据之间的联系 力为运动商城整理 例3 大学学生管理机构学校一系 八系 一年级二年级三年级四年级 班 班张三 李四 结论 数据之间是有结构的例 中数据之间呈分层结构 树状结构 DS 就是要研究数据之间的各类结构 力为运动商城整理 例 图书目录管理设每个书目含 书名 作者 登录号 分类 出版年月对图书目录常有如下操作 查找 某书在书库中是否存在 插入 购进新书时的登录 删除 报废或丢失的书 需从目录中去掉 结论 在某种数据结构上可定义一组运算 DS 就是要研究各类数据结构上的各种运算 力为运动商城整理 综上所述 DS 主要研究内容 数据的组织形式 数据的各种逻辑结构和存储结构 以及它们之间的相应关系 定义相应的操作 算法 实现操作 设计算法 评估算法 分析算法的效率 常见的数据结构有 数组 栈 队列 表 串 树 图和文件等 数据结构讨论描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现 力为运动商城整理 1 线性表示例 常见数据结构示例 力为运动商城整理 2 树形结构示例 一层 二层 三层 四层 力为运动商城整理 3 图形结构示例 力为运动商城整理 基本概念和术语 数据 Data 一切能够由计算机接受和处理的对象 数据元素 Dataelement 数据的基本单位 是组成数据的 事实 数值 或 符号 在程序中作为一个整体加以考虑和处理 数据项 Dataitem 数据的不可分割的最小单位 在有些场合下 数据项又称为字段或域 数据对象 Dataobject 性质相同的数据元素组成的集合 是数据的一个子集 力为运动商城整理 数据及数据元素 例1 学生花名册 数据元素 数据 学生名字 学号的集合 每个学生的名字 例2 学生成绩表 数据 数据元素 数据项 学生成绩的集合 每个学生的成绩 名字 成绩 数据对象 学生名字的集合 力为运动商城整理 数据结构 Datastructure 是相互之间存在一种和多种特定关系的数据元素的集合讨论计算机系统中数据的组织形式及其相互关系数据结构的研究 主要指数据的逻辑结构和物理结构的研究数据的逻辑结构 数据元素之间的相互关系数据的物理结构 数据结构在计算机的表示 又称数据的存储结构 包括数据元素的表示和关系的表示 力为运动商城整理 逻辑结构 数据之间的相互关系称为逻辑结构 通常分为4类基本结构 集合 结构中的数据元素除了同属于一种类型外 别无其它关系 线性结构 结构中的数据元素之间存在一对一的关系 树型结构 结构中的数据元素之间存在一对多的关系 图状结构或网状结构 结构中的数据元素之间存在多对多的关系 力为运动商城整理 数据 逻辑 结构的形式定义为 一个二元组 Data Structure D S 其中 D是数据元素的有限集 S是D上关系的有限集 例复数的数据结构定义 Complex C R 其中 C是含两个实数的集合 C1 C2 分别表示复数的实部和虚部 R P P是定义在集合上的一种关系 C1 C2 力为运动商城整理 存储结构 顺序存储结构连续顺序地存放数据元素若数据的逻辑结构也是顺序 线性 的 则逻辑结构和物理结构就完全统一连续存放的数据元素可以在内存中容易找到链式存储结构元素在内存中不一定连续存放在元素中附加指针项 通过指针可以找到关系元素 元素 指针 结点 元素 指针 力为运动商城整理 0300 0301 0302 0303 0304 0305 0306 0307 0308 0309 K1 K2 K3 K4 K1 K2 K3 K4 顺序存储结构 逻辑结构 物理结构 力为运动商城整理 0300 0301 0302 0303 0304 0305 0306 0307 0308 0309 K1 K2 K3 K4 K5 K6 K1 K2 K3 K4 K5 K6 逻辑结构 物理结构 力为运动商城整理 0300 0310 0320 0330 0340 0350 0370 0380 K1 K2 K3 K4 K5 K6 K1 K2 K3 K4 K5 K6 通过指针 可以方便地找到关系结点 指向后继结点的指针 逻辑结构 物理结构 链式存储结构 力为运动商城整理 索引存储方法为放在内存中的元素建立索引表元素可以离散存放通过查索引表找到需要的元素 0300 0301 0302 0303 0304 0305 0306 0307 0308 0309 K1 K2 K3 K4 1 2 3 4 索引表 索引号 力为运动商城整理 例 班级的逻辑关系与课堂上的座次 一个树形关系结构用索引方式存储 1 2 3 4 5 6 0300 0301 0302 0303 0304 0305 0306 0307 0308 0309 K1 K2 K3 K4 K5 K6 力为运动商城整理 数据类型 datatype 是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称 抽象数据类型 abstractdatatype 简称ADT 是指一个数学模型以及定义在该模型上的一组操作 抽象数据类型实际上就是对该数据结构的定义 用三元组描述如下 D 数据对象S D上的关系集P 对D的基本操作 力为运动商城整理 描述一种抽象数据类型可采用如下书写格式 ADT抽象数据类型名 数据对象 伪代码描述数据关系 伪代码描述基本操作 ADT抽象数据类型名 基本操作名 参数表 初始条件 操作结果 力为运动商城整理 小结 数据结构包括数据的逻辑结构 数据在计算机系统中的存储结构和数据操作的集合把数据以一定的逻辑结构组织起来 以适当的方式存储在计算机系统的存储器里 其最终目的是为了有效处理数据 提高数据处理运算速度 逻辑结构 存储结构 算法 要素 目标 三个要素都与我们所要实现的目标相关 有效处理数据 提高数据处理运算速度 力为运动商城整理 算法的概念及特点算法是为解决某一特定类型问题规定的运算规则的有穷集合有穷性确定性有效性输入输出 特点 非无限执行 必须在有限步骤内结束 非二义 下一步必须是明确的 每一步是可执行的 外部输入零个或多个 至少一个 算法 Algorithm 力为运动商城整理 相似 都是解决问题的方法和步骤 是指令的集合区别 有穷性描述方法联系 程序用某种程序设计语言来实现算法 程序使用程序设计语言 算法可以使用框图及其他语言 算法与程序 类似 While 1 的语句段 在程序中允许但在算法中不允许 力为运动商城整理 算法的设计要求 正确性 算法应能正确地实现处理要求 可读性 有助于对算法的理解 便于纠正和扩充 健壮性 使证明其正确性比较容易 对算法进行修改也比较方便 效率与低存储 达到所需的时 空性能 力为运动商城整理 算法效率的度量 算法的复杂性包括时间复杂性 所需运算时间 和空间复杂性 所占存储空间 重点是时间复杂性 事后验证 事先估计 一个算法所需的运算时间通常与所解决问题的规模大小有关 用n表示问题规模的量 把算法运行所需的时间T表示为n的函数 记为T n 定义 如果存在两个正常数c和n0 对于所有的n n0 有 f n c g n 则记作f n O g n 一般情况下 算法中基本操作重复执行的次数是问题规模n的某个函数 算法的时间量记作T n O f n 称作算法的渐近时间复杂度 它描述了当n逐渐增大时T n 的极限情况频度 指该语句重复执行的次数 一个算法所需的执行时间就是该算法中所有语句执行次数之和 力为运动商城整理 例1 x s 0 将x自增看成是基本操作 则语句频度为 即时间复杂度为 1 如果将s 0也看成是基本操作 则语句频度为 其时间复杂度仍为 1 即常量阶 例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 即时间复杂度为平方阶 力为运动商城整理 定理 若A n amnm am 1nm 1 a1n a0是一个m次多项式 则A n O nm 证略 例4for i 2 i n I for j 2 j i 1 j x a i j x 语句频度为 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 的算法则由一个二次多项式来限界 最常用的计算算法时间复杂度的多项式的关系为 O 1 O logn O n O nlogn O n2 O n3 指数时间的关系为 O 2n O n O nn O 的运算规则 1 T1 n O f n T2 n O g n 则 T n T1 n T2 n O max f n g n 2 T1 m O f m T2 n O g n 则 T m n T1 m T2 n O f n g n 力为运动商城整理 计算下面交换i和j内容程序段的时间复杂性 temp i i j j temp 解 以上三条单个语句均执行1次 该程序段的执行时间是一个与问题n无关的常数 因此 算法的时间复杂度为常数阶 记作T n O 1 力为运动商城整理 计算下面求累加和程序段的时间复杂性 1 sum 0 1次 2 for i 1 i n i n次 3 for j 1 j n j n2次 4 sum n2次 解 T n 2n2 n 1 O n2 力为运动商城整理 算法的运行时间往往还与具体输入的数据有关 通常用以下两种方法来确定一个算法的运算时间 1 平均时间复杂性 研究同样的n值时各种可能的输入 取它们运算时间的平均值 2 最坏时间复杂性 研究各种输入中运算最慢的一种情况下的运算时间 力为运动商城整理 Voidbubble sort inta intn for I n 1 change TURE I 1change TURE 最好情况 0次最坏情况 1 2 3 n 1 n n 1 2平均时间复杂度为 O n2 力为运动商城整理 算法的存储空间需求 算法的空间复杂度S n O g