期末复习讲义.ppt

DCSofSUSE 第1章绪论 复习要点 1 数据结构基本概念2 数据元素 数据项 逻辑结构 物理结构3 时间复杂度 空间复杂度 语句频度等计算 DCSofSUSE 基本概念 1 数据 所有能被计算机识别 存储和处理的符号的集合 包括数字 字符 声音 图像等信息 2 数据元素 是数据的基本单位 具有完整确定的实际意义 在计算机程序中通常作为一个整体进行考虑和处理 一个数据元素可由若干个数据项组成 3 数据项 构成数据元素的项目 它是数据不可分割的最小单位 4 数据类型 指一个类型和定义在这个类型上的操作集合 例 C语言 基本类型 整型 浮点型 字符型等构造类型 数组 结构 联合 指针 枚举等 5 抽象数据元素 抽象定义的 没有实际含义的数据元素 6 抽象数据类型 用户自己定义的数据类型 DCSofSUSE 数据结构 DCSofSUSE 集合结构 仅同属一个集合线性结构 一对一 1 1 树结构 一对多 1 n 图结构 多对多 m n 线性 逻辑结构可细分为4类 数据的逻辑结构 指数据元素之间的逻辑关系 即从逻辑关系上描述数据 它与数据的存储无关 是独立于计算机的 DCSofSUSE 1 R D S D a b c d e f S 解 上述表达式可用图形表示为 bcaefd 此结构为线性的 例 用图形表示下列数据结构 并指出它们是属于线性结构还是非线性结构 DCSofSUSE 物理结构亦称存储结构 是数据的逻辑结构在计算机存储器内的表示 或映像 它依赖于计算机 存储结构可分为4大类 例 复数3 0 2 3i的两种存储方式 顺序 链式 索引 散列 法1 地址内容 法2 地址内容 2字节 数据的物理结构 DCSofSUSE 时间复杂度和空间复杂度如何表示 DCSofSUSE 特别说明 如果无论算法规模怎样变化 其执行时间为一常数 则该算法的时间复杂度为O 1 DCSofSUSE DCSofSUSE 第2章线性表 复习要点 1 基本概念线性结构 线性表 位序 长度 空表等2 线性表的基本操作主要掌握插入 删除等运算及特性3 顺序存储 链式存储特点 组织方式顺序表 单链表 双链表的查找 插入和删除等操作 DCSofSUSE 一 线性表 linear list 线性表是n个数据元素的有限序列 记为 L a1 a2 an 数据元素之间的关系是 ai 1领先于ai ai领先于ai 1 称ai 1是ai的直接前驱元素 ai 1是ai的直接后继元素 除a1外 每个元素有且仅有一个直接前驱元素 除an外 每个元素有且仅有一个直接后继元素 线性表中数据元素的个数n n 0 称为线性表的长度 当n 0时 称为空表 DCSofSUSE 线性表的顺序存储结构 一 顺序存储结构用一组地址连续的存储单元依次存储线性表的元素 设线性表的每个元素占用k个存储单元 则第i个元素ai的存储位置为 Loc ai Loc a1 i 1 k其中 Loc ai 为线性表的起址 特点 存储单元地址连续 需要一段连续空间 逻辑上相邻的数据元素其物理位置也相邻存储密度大 100 随机存取元素序号与存储位置存在如下关系 Loc ai Loc a1 i 1 d 1 i n 线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素 这称为顺序表 DCSofSUSE 二 插入和删除操作1 插入运算INSERT L i b 插入前 L a1 ai 1 ai an 插入后 L a1 ai 1 b ai an 算法思想 进行合法性检查 1 i n 1 判断线性表是否已满 将第n个至第i个元素逐一后移一个单元 在第i个位置处插入新元素 将表的长度加1 DCSofSUSE 线性表上的基本运算插入运算含义 将元素e插入到线性表 a1 a2 ai 1 ai an 中 构成新的线性表 a1 a2 ai 1 e ai an 满足ai 1 e ai 其中 为比较关系 即不破坏原线性关系 表的长度为n 1将元素e插入到元素ai 1之后 ai 1的直接后继和ai的直接前驱就改变了 需要在顺序表的存储结构上反映出来 DCSofSUSE 2 删除运算DELETE L i 删除前 L a1 ai 1 ai ai 1 an 删除后 L a1 ai 1 ai 1 an 算法思想 进行合法性检查 i是否满足1 i n 判线性表是否已空 L length 0 将第i 1至第n个元素逐一向前移一个位置 将表的长度减1 思考 如果要删除指定位置开始的m个元素 如何实现 DCSofSUSE 线性表顺序存储结构的特点 1 逻辑上相邻的元素 其物理位置也相邻 2 可随机存取表中任一元素 3 必须按最大可能长度预分存储空间 存储空间利用率低 表的容量难以扩充 是一种静态存储结构 4 插入删除时 需移动大量元素 平均移动元素为n 2 顺序表的基本运算的复杂度插入T n O n S n O 1 删除T n O n S n O 1 DCSofSUSE 线性表的链式表示和实现 链表 线性表的链式存储内涵 线性表的链式存储指用任意的存储单元存放线性表中的元素 每个元素与其直接前驱和 或 直接后继之间的关系用指针来存储 这称为链表 术语结点 数据元素及与其有直接关系的元素的地址构成的存储单位 数据域 指针域 DCSofSUSE 单链表的表示和实现 单链表上的查找运算在单链表中 必须从头指针出发进行查找 查找第i个元素查找指定的元素是否在表中 若找到 则返回该元素的值 否则返回ERROR 在单链表上查找第i个元素的示意图 p k 1 找到 返回P指向的结点的数据 问题 in呢 特别说明 指针的移动 不会删除结点 DCSofSUSE 单链表上的插入运算 第i个位置上插入新的结点 逻辑运算 a1 a2 ai 1 ai ai 1 an a1 a2 ai 1 e ai ai 1 an 单链表上的实现示意图 基本步骤 找到第i 1个元素所在结点 申请一个新结点s并填入e值 修改s的指针域指向p的下一结点 思考 第 步是否可交换 DCSofSUSE 链表的优缺点优点 插入 删除时无须移动元素 只需修改指针根据需要申请存储空间 且不要求连续的存储空间缺点 对表中的元素只能进行顺序访问用指针指示元素之间的逻辑关系 直接前驱 后继 存储空间利用率低 DCSofSUSE 双向链表 双向链表上的插入操作 将元素e插入到链表的第i个结点前 基本步骤 1 定位指针p指向结点ai 1 p 2 建立新结点s并赋e 3 修改s的next指针域指向p下一结点 s next p next 5 修改p的next指针域指向s结点 p next s 6 修改s下一结点的prior指针域指向s s next prior s 4 修改s的prior指针域指向p结点 s prior p 问题 修改指针的步骤是否可随意 不带头结点 DCSofSUSE 双向链表上的删除操作 删除第i个结点 基本步骤 1 定位指针p指向结点ai p 2 修改p的前一结点的next指针域指向p下一结点 p prior next p next 3 修改p的下一结点的prior指针域指向p前一结点 p next prior p prior 4 释放结点p DCSofSUSE 第3章栈和队列 一 栈的概念栈 stack 是插入和删除操作限定在表尾进行的线性表 栈的逻辑表示为 S a1 a2 an 表尾元素an称为栈顶 top 表头元素a1称为栈底 bottom 不含元素的空表称为空栈栈的运算特性是后进先出 LastInFirstOut LIFO 或先进后出 FirstInLastOut FILO DCSofSUSE 二 队列的概念队列 Queue 是限定仅在一端插入 另一端删除的线性表 允许插入的一端叫队尾 rear 允许删除的一端叫队头 front 不含元素的空表称为空队列队列的运算特性是先进先出 FirstInFirstOut FIFO DCSofSUSE 插入 删除操作 栈 Push S x Pop S e GetTop S e StackEmpty S 队列 QueueEmpty Q EnQueue Q e DeQueue Q e GetHead Q e DCSofSUSE 第4章串 要点 基本概念和朴素模式匹配算法 模式匹配算法朴素的串匹配算法intIndex sstringS sstringT intpos 返回子串T在主串S中从第pos个字符开始的位置 要求T非空 1 pos Strlength S i pos j 1 while iStrlength T return i Strlength T return0 Index 算法时间复杂度 O n m 其中n m分别为主串和子串长度 DCSofSUSE 第5章数组和广义表 要点 数组基本概念和特殊矩阵的压缩存贮 LOC aij LOC a11 i 1 n j 1 d 对称矩阵 数组B ai j an n k m 下标 k m DCSofSUSE 第6章树与二叉树 要点 1 二叉树的性质 推论及应用性质1 性质2 性质3 性质4 性质5 2 完全二叉树的概念及特点 3 二叉树的遍历 4 线索二叉树的基本概念和数据结构 5 树 森林与二叉树的转换 及相关特点 6 Huffman树及Huffman编码 DCSofSUSE 树的基本术语1 树的结点 包含一个DE和指向其子树的所有分支 2 结点的度 一个结点拥有的子树的个数 度为零的结点称为叶结点 3 树的度 树中所有结点的度的最大值Max D I 含义 树中最大分支数为树的度 4 结点的层次及树的深度 根为第一层 根的孩子为第二层 若某结点为第k层 则其孩子为k 1层 树中结点的最大层次称为树的深度或高度5 森林 是m m 0 棵互不相的树的集合森林与树概念相近 相互很容易转换 结论 一棵树的各结点的度之和 等于该树的分支数目 DCSofSUSE 二叉树性质 扩展要求掌握各性质的推论 性质1 在二叉树的第i层上至多有2i 1个结点 i 1 性质2 深度为k的二叉树至多有2k 1个结点 k 1 深度一定 二叉树的最大结点数也确定 性质3 二叉树中 终端结点数n0与度为2的结点数n2有如下关系 n0 n2 1性质4 结点数为n的完全二叉树 其深度为 log2n 1 DCSofSUSE 性质5 在按层序编号的n个结点的完全二叉树中 任意一结点i 1 i n 有 i 1时 结点i是树的根 否则 i 1 结点i的双亲为结点 i 2 2i n时 结点i无左孩子 为叶结点 否则 结点i的左孩子为结点2i 2i 1 n时 结点i无右孩子 否则 结点i的右孩子为结点2i 1 性质6 含有n个结点的二叉链表中 有n 1个空链域 重点说明 对于前4个性质 要求能推广到多叉树 DCSofSUSE 二叉树的遍历 遍历顺序 DLR LDR LRD 层序遍历 D L R 根结点 根的左子树 根的右子树 DCSofSUSE 线索二叉树 结点结构在二叉链表中增加ltag和rtag两个标志域 若结点有左子树 则左链域lchild指示其左孩子 ltag 0 否则 令左链域指示其前驱 ltag 1 若结点有右子树 则右链域rchild指示其右孩子 rtag 0 否则 令右链域指示其后继 rtag 1 DCSofSUSE 树与二叉树的转换 借助于 孩子兄弟表示法 实现树与二叉树之间的转化 DCSofSUSE 森林转化为二叉树 B D F C K L M E G H I 结论 从根开始 沿右指针前进 结点个数对应原森林中树的数目 DCSofSUSE 赫夫曼编码 已知某系统在通信联络中只可能出现8种字符 其概率如下表所示 a g c d h e f b 最优二叉树 0 1 0 0 0 0 0 0 1 1 1 1 1 1 a 0010 b 11 c 1010 d 1011 e 100 f 01 g 0011 h 000 a b c d e f g h DCSofSUSE 第7章图 要点 1 图的邻接矩阵和邻接表表示特点及关系 2 最小生成树及算法 3 完全图基本概念 拓扑排序的基本概念和特点 DCSofSUSE 一 数组表示法 邻接矩阵 设图G V E 有n个顶点 则G的邻接矩阵定义为n阶方阵A 其中 A i j 1若 vi vj 或 E i j0其它 无向图的邻接矩阵为对称矩阵 DCSofSUSE 特点 判定两个顶点Vi与Vj是否关联 只需判A i j 是否为1顶点的度容易求得 DCSofSUSE 二 邻接表 adjacencylist 如图G2的邻接表为 特点 设无向图中顶点数为n 边数为e 则它的邻接表需要n个头结点和2e个表结点 顶点Vi的度TD Vi 链表i中的表结点数 DCSofSUSE 二 邻接表 adjacencylist 2 有向图邻接表 与无向图的邻接表结构一样 只是在第i条链表上的结点是以Vi为弧尾的各个弧头顶点 特点 1 n个顶点 e条弧的有向图 需n个表头结点 e个表结点2 第i条链表上的结点数 为Vi的出度 求顶点的出度易 求入度难 如图G1的邻接表为 DCSofSUSE 图的遍历 一 深度优先搜索 depth first search 如图G4 二 广度优先搜索 breadth first search 首先访问指定顶点v0 将v0作为当前顶点 访问当前顶点的所有未访问过的邻接点 并依次将访问的这些邻接点作为当前顶点 重复2 直到所有顶点被访问为止 DCSofSUSE 最小生成树概念1 设无向连通图G V E 其子图G V T 满足 V G V G n个顶点 G 是连通的 G 中无回路则G 是G的生成树 DCSofSUSE 普里姆 Prim 最小生成树算法 1 TE U u0 2 当U V 重复下列步骤 1 选取 u0 v0 min cost u v u U v V U 保证不形成回路 2 TE TE u0 v0 边 u0 v0 并入TE 3 U U V0 顶点V0并入U 特点 以连通为主选代价最小的邻接边 顶点加入序列 V1 V3 V6 V4 V2 V5 顶点逐个加入 DCSofSUSE 克鲁斯卡尔 Kruskal 最小生成树算法 步骤 v u ET 1 1 3 0 1 3 2 5 2 4 6 5 1 4 4 3 6 6 2 3 边数 n 1 5代价 1 2 3 4 5 15 DCSofSUSE 拓扑排序 topologicalsort 拓扑排序是一种对非线性结构的有向图进行线性化的重要手段 AOV网可解决如下两个问题 1 判定工程的可行性 显然 有回路 整个工程就无法结束 2 确定各项活动在整个工程执行中的先后顺序 称这种先后顺序为拓扑有序序列 如图有如下拓扑有序序列 a1a2a3a4a6a5a7a8a9a2a6a1a3a4a5a7a9a8 DCSofSUSE 第9章查找 要点 1 基本概念 2 有序表查找 二分查找 或折半查找 思想 算法 3 哈希查找基本概念及冲突解决方法 链地址法 公共溢出区法 4 二叉排序树的特点 DCSofSUSE 查找 在查找表中确定与给定值相等的DE的过程 查找结果 查找成功 table中存在给定值的记录 查找不成功 table中不存在给定值的记录 查找表分为 静态查找表 对查找表中的数据元素不进行插入和删除操作 动态查找表 对查找表中的数据元素可进行插入和删除操作 DCSofSUSE 有序表的查找有序表 查找表中记录按关键字有序排列的表 即 ST elem i key ST elem i 1 keyi 1 2 n 1折半查找 要求 查找表为有序表 查找过程 先确定待查记录范围 然后逐步缩小范围 直到 查找成功或不成功 DCSofSUSE 折半查找算法intSearch Bin SSTableST KeyTypekey low 1 high ST length while low high mid low high 2 if EQ key ST elem mid key returnmid elseif LT key ST elem mid key high mid 1 elselow mid 1 return0 Search Bin 折半查找算法 递归实现 intSearch Bin SSTableST intlow inthigh KeyTypekey if low high mid low high 2 if EQ key ST elem mid key returnmid elseif LT key ST elem mid key returnSearch Bin ST low mid 1 key elsereturnSearch Bin ST mid 1 high key elsereturn0 Search