计算机软件技术基础3-1 数据结构及算法(概述+线性表).ppt

1 常用数据结构及其运算 第三章 2 3 1概述 3 2线性表 3 3栈与队 3 4树与二叉树 3 5图 3 6查找与排序 目录 3 3 1概述 3 1 1数据结构的概念3 1 2数据的逻辑结构和物理结构3 1 3算法与算法分析3 1 4算法分析技术初步3 1 5小结 4 3 1 1数据结构的概念 数值型与非数值型数据数值型 整型 实型 布尔型等非数值型 文献检索 金融管理 商业系统等数据处理 数据结构研究非数值运算的程序设计问题 数据结构就是相互之间存在一种或多种特定关系的数据元素的集合 如线性关系 层次关系 网状关系等 5 数据 data 是信息的载体 指所有能输入到计算机中并被计算机程序处理的符号的总称 如数 字符 符号等的集合 分为数值型和非数值型数据两类 数据元素 dataelement 是数据的基本单位 如数据集合N 1 2 3 4 5 中整数1至5均为数据元素 数据元素不一定是单个的数字或字符 也可能是若干个数据项的组合 如学生信息 数据元素有时也称结点或记录 3 基本概念和术语 3 1 1数据结构的概念 6 数据类型 程序设计语言中允许的变量类型 基本数据类型 原子类型 变量值不可分 如整型 实型 字符型等 结构类型 变量值可分 如数组 结构体等 数据对象 dataobject 性质相同的数据元素的集合 如大写字母字符的数据对象是集合 C A B Z 3 1 1数据结构的概念 7 数据结构 datastructure 是指同一数据对象中各数据元素间存在的关系 数据结构与算法 程序 算法 数据结构算法指解决特定问题的有限运算序列 3 1 1数据结构的概念 8 1 逻辑结构 研究数据元素及其关系的数学特性 即数据元素间的逻辑关系 二元组S D R D 数据元素的非空有限集合R D上关系的非空有限集合 3 1 2数据的逻辑结构和物理结构 9 四类基本结构 举例 3 1 2数据的逻辑结构和物理结构 10 例1 linearity D R 其中D 1 2 3 4 5 6 7 8 9 10 R r r 例2 Tree D R 其中D 1 2 3 4 5 6 7 8 9 10 R r r 3 1 2数据的逻辑结构和物理结构 11 例4 S D R 其中D 1 2 3 4 5 6 R r1 r2 r1 r2 例3 Graph D R 其中D 1 2 3 4 5 R r r 3 1 2数据的逻辑结构和物理结构 12 2 物理结构 存储结构 是逻辑结构在计算机中的映象 即具体实现 四种基本存储结构 顺序存储结构链式存储结构索引存储结构散列存储结构3 逻辑结构与存储结构的关系 算法的设计取决于选定的逻辑结构 而算法的实现依赖于采用的存储结构 同一种逻辑结构可采用不同的存储结构 3 1 2数据的逻辑结构和物理结构 13 一 什么是算法 算法是对特定问题求解步骤的一种描述 是指令的有限序列 其中每条指令表示一个或多个操作 算法的五个特征 有穷性 确定性 可行性 输入 输出 算法描述 采用类C语言的形式 有时也用自然语言 注释部分用 或 表示 3 1 3算法与算法分析 14 二 算法设计的要求 正确性 健壮性 效率与低存储三 算法评价标准 时间复杂度 空间复杂度一般时间复杂度考虑的较多 一个可执行的算法不一定是一个好算法 算法的分析通常用计算机执行时在时间和空间两方面的消耗多少作为评价该算法优劣的标准 度量一个程序的执行时间通常有两种方法 事后统计和事前分析估算着重介绍第二种方法 算法 问题规模 语言 机器代码质量 机器执行指令的速度 3 1 3算法与算法分析 15 一 时间复杂度1 频度 指一条语句重复执行的次数 记作 F n 2 算法的时间度量 T n O F n 是问题规模n的某个函数F n 称为算法的渐进时间复杂度或时间复杂度 例 T n 3n2 2n 则T n O n2 T n 3n 2n 则T n O 3n 3 1 4算法与分析技术初步 16 x 的语句频度及三段程序的时间复杂度 a b c F n 1nn2T n O 1 O n O n2 例 a x s 0 b for i 1 i n i x s x c for j 1 j n j for k 1 k n k x s x 3 1 4算法与分析技术初步 17 问题 有A B两段程序同时运行 在某时刻A的运行速度是B的2倍 因此 A的算法复杂度比B低 即效率高 3 1 4算法与分析技术初步 18 常见的时间复杂度1 O 1 常量型2 O n O n2 O nk 多项式型3 O log2n O 2log2n 对数型4 O 2n O en 指数型按增长率排序 一般有 1 3 2 4 3 1 4算法与分析技术初步 19 当难以精确计算基本操作执行次数 或语句频度 情况下 只需求出关于n的增长率或阶即可 当难以确定各种输入数据集出现的概率时 平均时间复杂度也难以确定时 可用最坏的情况作为分析依据 3 1 4算法与分析技术初步 20 例 求下列程序段的时间复杂度1 for i 0 i n i 2 for j 0 j n j 3 b i j 0 4 for k 0 k n k 5 b i j b i j a i k a k j 6 以执行次数最多的语句 第5句 进行计算 语句频度为 F n n3时间复杂度 T n O F n O n3 3 1 4算法与分析技术初步 21 3 程序运行时间计算方法 1 两条法则 加法法则若T1 n O F n T2 n O G n 则 T1 n T2 n max O F n O G n 乘法法则 若T1 n O F n T2 n O G n 则 T1 n T2 n O F n G n 3 1 4算法与分析技术初步 22 例 三个程序段执行时间分别为O n O n3 O nlogn 则T n max O n O n3 O nlogn O n3 加法法则特例 某两步的运行时间分别为O F n O G n 其中F n n4 n为偶数 G n n2 n为偶数 n2 n为奇数 G n n3 n为奇数 则总运行时间 T n O n4 当n为偶数时 O n3 当n为奇数时 3 1 4算法与分析技术初步 23 2 常用的六条分析规则 1 每个赋值语句或读 写语句的运行时间通常是O 1 例外情况 赋值语句的右部表达式出现函数调用 此时要考虑计算函数值所耗费的时间2 一个序列语句的运行时间由加法法则确定 即为该序列中耗时最多的语句的运行时间 3 1 4算法与分析技术初步 24 3 if S语句 执行时间为条件测试时间 O 1 分支语句S的执行时间 if S1条件测试 O 1 S1和S2中运行时elseS2间较大者 4 循环语句的运行时间 是n次重复执行循环体所耗时间的总和 应用乘法法则 即 执行一次循环体时间的最大值 循环次数每次执行循环体的时间 循环体本身运行时间 计算循环参数及测试时间 通常为O 1 多层循环 由内层 外层逐层分析 3 1 4算法与分析技术初步 25 5 过程调用语句 a 非递归过程 根据过程调用的层次 由内而外分析程序的运行时间 b 递归调用 可先对递归过程设一特定的运行时间函数T n 根据过程递归调用的情况 得到T n 的一个递推关系 6 goto语句 可以最坏情况进行计算 即在遇到向下转移的goto语句时 可认为goto语句所引起的控制转移根本没有发生 当遇到向上转移的goto语句时 则必须考虑它对程序运行时间的影响 3 1 4算法与分析技术初步 26 4 时间复杂度计算举例 例1 1 for i 1 i i 1 j 3 if A j 1 A j 4 temp A j 1 5 A j 1 A j 6 A j temp 分析 4 6 O 1 3 6 O 1 2 6 O 1 n i O n i 1 6 T n O n2 3 1 4算法与分析技术初步 27 例2 for i 2 i i j S 求 S 语句的频度及整个程序段的算法复杂度 分析 i 2 执行n 1次i 3 执行n 2次 i n 2 执行3次则 F n 3 4 5 n 1 n 3 n 2 2T n O n2 3 1 4算法与分析技术初步 28 例3 i 1 While i n i i 3 求 语句的频度及整个程序段的算法复杂度 分析 设 句的频度为F n 则 T n O log3n 3 1 4算法与分析技术初步 29 例4 prime intn n为一正整数 inti 2 while n i 0 求算法的复杂度 分析 设嵌套最深层语句 i 的频度为F n 有 F n 1 0 sqrt n 则 3 1 4算法与分析技术初步 30 例5 x n y 0 while x y 1 y 1 do y y 1 求 语句的频度和整个程序段的算法复杂度 分析 F n F n n 3 1 4算法与分析技术初步 31 例6 w 11 k 21 while k 10 do ifw 20then w w 10 k elsew w 10 求 语句的频度 分析 对每一合法k值 句执行2次则 句频度F n 21 10 2 22 3 1 4算法与分析技术初步 32 例7 x 87 y 10 while y 0 if x 100 x 10 y elsex 求 语句的频度和整个算法的复杂度 分析 句频度F n 15 11 9 114T n O 1 3 1 4算法与分析技术初步 33 例8 intfact intn 计算n 1 if n 1 2 fact 1 else 3 fact n fact n 1 计算程序段的时间复杂度 3 1 4算法与分析技术初步 34 例9 floatp n intn 1 if n 1 return n 2 elsereturn p n 1 p n 2 计算程序段的时间复杂度 3 1 4算法与分析技术初步 35 二 空间复杂度 空间复杂度是指在算法中所需的辅助空间单元而不包括问题的原始数据占用的空间 因为这些单元与算法无关 记作 S n 时间与空间是一对矛盾 要节约空间往往就要消耗较多时间 反之亦然 而目前由于计算机硬件的发展 一般都有足够的内存空间 因此在分析中着重考虑时间的因素 3 1 4算法与分析技术初步 36 理解数据 数据元素 数据对象 逻辑结构和物理结构 数据类型 数据结构 算法等基本概念 掌握频度 时间复杂度的计算 了解空间复杂度 3 1 5小结 37 3 2线性表 3 2 1线性表的定义和运算3 2 2顺序存储线性表3 2 3线性链表3 2 4向量和链表的比较3 2 5小结3 2 6作业 38 3 2 1线性表的定义和运算 线性表的概念线性表的逻辑结构是n个数据元素的有限序列 L a1 a2 an L为线性表 ai i 1 n 是属于某数据对象的元素 n为线性表的长度 n 0 n 0的表称为空表 2 线性表的定义L D R 39 3 线性表的结构特点表中的数据元素为同一数据类型数据元素之间是线性关系每个元素有且只有一个前趋元素 第一个元素除外 每个元素有且只有一个后继元素 最后一个元素除外 3 2 1线性表的定义和运算 40 有序表与无序表的概念若线性表中的数据元素相互之间可以比较 且ai ai 1 i 2 3 n 或ai ai 1 i 1 2 n 1 则称该线性表为有序表 否则称为无序表 线性表的基本运算插入 删除 查找 排序等 按位置 按值 3 2 1线性表的定义和运算 41 3 2 2顺序存储线性表 顺序表 一 顺序存储结构 用一组地址连续的存储单元存放线性表的数据元素 也称为向量式存储结构 该结构用高级语言中的一维数组类型表示 例如 可用一维数组A n 来存储线性表 a1 a2 an 地址计算 addr ai addr a1 i 1 L 特点 随机存储结构 查找方便 42 例 addr a4 addr a1 i 1 L 2000H 4 1 1 2003H 3 2 2顺序存储线性表 43 二 顺序存储结构的插入与删除1 插入1 概念 有线性表 a1 a2 an 长度为n 要在第i 1与第i个元素之间插入一个新元素 使得线性表变为 a1 a2 ai 1 x ai an 长度为n 1 2 插入过程 将ai至an依次后移一个位置 共移动n i 1个元素 然后将新元素插入在第i个位置上 合法位置 1 i n 1 请参见教材27页图2 3所示 3 2 2顺序存储线性表 44 3 算法描述intInsertList L m n i x 形式参数 if in 1 return 0 位置非法for j n j i j L j 1 L j 移动元素L i x 插入元素n 长度加1return 1 执行成功 返回 3 2 2顺序存储线性表 45 2 删除1 概念 删除第i个位置上的元素 使线性表的长度由n变为n 1 2 删除过程 ai 1 an依次前移一个位置 共移动n i个元素 合法位置 1 i n 参见教材27页图2 4所示 3 2 2顺序存储线性表 46 3 算法描述intDeleteList L m n i if in return 0 参数不合法for j i j n 1 j L j L j 1 前移n 表长减1return 1 3 2 2顺序存储线性表 47 运算的时间分析 在插入和删除运算中 时间主要消耗在移动元素上 设pi 在第i个元素前插入一个元素的概率 则在长度为n的线性表中插入一个元素所需的平均移动次数为 3 2 2顺序存储线性表 48 在等概率情况下 pi 1 n 1 则有 同理 删除时有 在等概率情况下 qi 1 n 则有 问题 顺序表插入 删除的时间复杂度 O n 3 2 2顺序存储线性表 49 4 顺序表特点 优点 存储效率高 查找方便 缺点 1 插入删除代价高 插入或删除一个元素 平均需要移动表中一半的元素 仅适用于不经常进行插入和删除运算以及表中元素相对稳定的场合 2 要求连续存储区 管理不灵活 元素删除后不能释放空间 3 2 2顺序存储线性表 50 三 顺序存储结构的应用举例2 顺序表合并 将两个有序顺序表A 有m个元素 和B 有n个元素 合并为一个有序线性表C 3 2 2顺序存储线性表 51 解 LINK A m B n C i 0 j 0 t 0 k 0 while iB j C k B j else C k B j 相等者只保存一个i if i m B未完 将B余下的元素赋给Cfor t j t n t C k B t if j n A未完 将A余下的元素赋给Cfor t i t m t C k A t returnk 3 2 2顺序存储线性表 52 3 2 3线性链表 一 问题的提出 顺序存储结构的缺点1 插入和删除时需移动大量的元素 2 要求存放元素的存储单元连续 3 有时会造成空间浪费或溢出 4 表的容量不易扩充 个数固定 53 二 线性链表的逻辑结构1 逻辑结构 每个结点有两个字段 data 数据域 存放结点值next 指针域 存放后继结点的地址 头指针 head 指向链表的第一个结点 链表可以为空 headNULL字段值的获取 data a1 next a1 C语言 a1 data a1 next 3 2 3线性链表 54 二 线性链表的逻辑结构2 线性链表的特点 存储单元不要求连续 插入和删除方便 要求较多的存储空间 存放指针域 3 2 3线性链表 55 三 单链表1 基本概念 每个结点只有一个指针域的链表 结点定义 typedefstructnode chardata structnode next NODE 3 2 3线性链表 56 三 单链表2 线性链表的基本运算 1 基本操作 3 2 3线性链表 1 指针赋值 s p q p next 2 指针移动 p p next 3 后插 s next p next p next s 4 前插 q head while q next p q q next q next s s next p 57 1 指针赋值 s p q p next 2 指针移动 p p next 3 后插 s next p next p next s 4 前插 q head while q next p q q next q next s s next p 58 2 结点的动态生成及回收 动态生成 GETNODE P data P data b C语言中的实现 包含头文件 alloc h intGet NODE P P NODE malloc sizeof NODE if P return 0 elsereturn 1 回收 RET P C语言中的实现 free P 3 2 3线性链表 59 NODE CreateList intn 建立有n个结点的单链表 NODE h NULL pre NULL s 定义变量for i 0 idata s next NULL 生成结点并赋值if h NULL h s elsepre next s pre s 结点指针链接 return h 返回链表头指针 三 单链表3 线性链表的建立 补充 3 2 3线性链表 60 1 问题描述 在值为a的结点前插入一个值为x的结点 若链表为空 则x成为其头结点 若表中无a元素 则将x插入表尾 三 单链表4 插入运算 3 2 3线性链表 61 2 算法描述InsertList head a x GETNODE p p data x 取得一个新结点pif head NULL then 空表head p p next NULL return if head data a then a为头结点p next head head p return q head while q next NULL 完成插入 3 2 3线性链表 62 1 问题描述 将值为a的结点删除 三 单链表5 删除运算 3 2 3线性链表 63 2 算法描述DeleteList head a if head NULL return 空表if head data a then a为头结点p head head head next free p return LOOKFOR head a q if q next NULL then return p q next q next p next free p 完成删除return 3 2 3线性链表 64 三 单链表5 算法运算时间分析在单链表中插入或删除一个结点时 仅需改变一个或两个指针 而无需移动元素 3 2 3线性链表 65 1 在链表的第一个结点之前附加一个头结点 四 线性链表的其他形式1 带头结点的线性链表 头结点 数据域 不用 或用于存放其它信息 如表长 指针域 指向链表的第一个结点 3 2 3线性链表 66 2 头结点的用处 可简化算法的形式 例如在插入运算中 当表空时尚有头结点存在 因此头指针非空 当a为表中第一个元素时 因有头结点存在 则在a结点之前插入一元素时不必修改头指针 3 2 3线性链表 67 表中最后一个结点指向表的第一个结点 整个链表形成一个环 只要给定循环链表中任一结点的地址 就可以查遍表中所有的结点 而不必从头指针开始 四 线性链表的其他形式2 循环链表 3 2 3线性链表 68 优点 提高查找效率 思考 如何判断循环链表的表尾 单链表 判断指针域为空 四 线性链表的其他形式2 循环链表 3 2 3线性链表 69 逻辑结构 四 线性链表的其他形式3 双向链表 3 2 3线性链表 70 四 线性链表的其他形式3 双向链表 特点 一个结点有两个指针域 容易找到前驱 双向链表的插入 在P结点之后插入值为y的结点 GETNODE q q data y q next p next p next q q next prior q q prior p 3 2 3线性链表 71 四 线性链表的其他形式3 双向链表 双向链表的删除 删除结点P p prior next p next p next prior p prior free p 3 2 3线性链表 72 五 链表应用举例1 一元多项式相加 结点结构 每一个非零项构成链表中的一个结点 结点由两个数据域和一个指针域构成 3 2 3线性链表 73 A x 3x14 2x8 1B x 8x14 3x10 10 x6C x A x B x 设pa pb指针 1 若指数相等 则系数相加 c x 中建项 系数为0 不建 2 若pa exp pb exp复抄pa所指项 反之 复抄pb所指项 74 structnode1 addpoly structnode1 ah structnode1 bh structnode1 pa pb pc ch pp int