数据结构知识点总结,有工大老师多年经验编写.ppt

计算机系列课程之间的联系 数据结构涵盖的内容 二 基本概念和术语 1 数据数据是用于描述客观事物的数值 字符 以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合 其范围随着计算机技术的发展而不断发展 2 数据元素数据的基本单位是数据元素 在计算机程序中通常作为一个整体进行考虑和处理 3 数据项是数据的不可分割的最小单位 一个数据元素可由若干个数据项组成 4 数据对象性质相同的元素的集合叫做数据对象 5 结点数据元素在机内的位串表示 即数据元素在计算机内的映象 6 域 字段当数据元素由若干个数据项组成时 位串中对应于各个数据项的子串称为域 字段 是数据元素中数据项在计算机中的映象 7 信息表计算机程序所作用的一组数据通常称为信息表 是数据对象在计算机中的映象 8 数据结构数据结构指的是数据元素之间的相互关系 这种关系是抽象的 即并不涉及数据元素的具体内容 是数据元素及其相互间的关系的数学描述 9 逻辑结构和存储结构 1 逻辑结构数据结构中描述的是数据元素之间的抽象关系 逻辑关系 称为逻辑结构 2 存储结构 物理结构数据结构在计算机中的表示 映象 称为存储结构 物理结构 1 1 1基本概念和术语 3 数据元素之间的关系 逻辑结构 在计算机中有两种表示方法 顺序映象 表示 和非顺序映象 表示 从而导致两种不同的存储结构 顺序结构和链式结构 顺序映象 表示 的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系 非顺序映象 表示 的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系 1 1 1基本概念和术语 返回 1 1 2四种基本的数据结构 1 集合结构 结构中的数据元素之间除了 属于同一个集合 的关系之外 别无其他关系 关系比较松散 可用其他结构来表示 结构中的数据元素之间存在一个对一个的关系 即线性关系 每个元素至多有一个直接前导和后继 2 线性结构 3 树型结构 结构中的数据元素之间存在一个对多个的关系 即层次关系 即每一层上的元素可能与下层的多个元素相关 而至多与上层的一个元素相关 结构中的数据元素之间存在多个对多个的关系 即任意关系 任何元素之间都可能有关系 4 网状 图型结构 返回 1 1 3数据结构的研究对象 数据结构的研究对象 研究内容 1 数据对象的结构形式 各种数据结构的性质 逻辑结构 2 数据对象和 关系 在计算机中的表示 物理结构 存储结构 3 数据结构上定义的基本操作 算法 4 算法的效率 5 数据结构的应用 如数据分类 检索 返回 数据结构的作用图 数据结构 数据关系 数据表示 数据类型 数学离散数学应用数学 硬件存储设备总体结构 软件系统软件应用软件 算法设计数据运算 编码理论数据组合 系统设计数据存取 2 1算法及其性能评价准则 算法 Algorithm 是对特定问题求解步骤的一种描述 它是指令 规则 的有限序列 其中每一条指令表示一个或多个操作 算法的特征 有穷性 确定性 能行性 输入 输出 算法描述 自然语言 程序设计语言 类语言 一 算法 算法的特征和算法描述 常用的算法设计方法 递归法 Recursion 分治法 Divide andConquer 贪心法 Greedy 动态规划 DynamicProgramming 搜索与遍历 回溯 Backtracking 解空间局部搜索 近似算法 Approximation 在线算法 On Line 等 2 2算法时间复杂性分析方法 定理2 1若A n amnm a1n a0是关于n的m次多项式 则A n nm 此定理说明 时间复杂性仅取决于多项式的最高次幂 而与最高次幂的系数和其他低次项无关 1 表示实践复杂性为常数常见的时间复杂性及其比较 1 n n n n n n2 n3 2n 设T1 n O f n T2 n O g n 则加法规则 T1 n T2 n O max f n g n 乘法规则 T1 n T2 n O f n g n 1 表达式和赋值语句 O 1 2 语句序列 用加法规则 取耗时最多语句 3 条件语句 O 1 4 FOR语句 O N M N为循环次数 M为体内时间最多的语句5 WHILE语句 找出与循环次数有关的变量 通过计算找出上下限 例 x n y 0 while x y 1 y 1 y y 1 时间复杂性为O s 0 f n 1 T2 n O f n O 1 常量阶 for i 1 i n i for j 1 j n j x s x f n 3n2 2n 1 T3 n O f n O n2 平方阶 for i 1 i n i for j 1 j n j c i j 0 for k 1 k n k c i j a i k b k j f n 2n3 3n2 2n 1 T4 n O f n O n3 立方阶 for i 1 i n i x s x f n 3n 1 T1 n O f n O n 线形阶 第三章线性表 LinerList 知识点 线性表的逻辑结构和各种存储表示方法定义在逻辑结构上的各种基本运算 操作 在各种存储结构上如何实现这些基本运算各种基本运算的时间复杂性 重点 熟练掌握顺序表和单链表上实现的各种算法及相关的时间复杂性分析 难点 使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题 3 1抽象数据型线性表 定义 线性表是由n n 0 个相同类型的元素组成的有序集合 记为 a1 a2 a3 ai 1 ai ai 1 an 其中 n为线性表中元素个数 称为线性表的长度 当n 0时 为空表 记为 ai为线性表中的元素 类型定义为elementtype a1为表中第1个元素 无前驱元素 an为表中最后一个元素 无后继元素 对于 ai 1 ai ai 1 1 i n 称ai 1为ai的直接前驱 ai 1为ai的直接后继 位置概念 线性表是有限的 也是有序的 3 1抽象数据型线性表 线性表LIST D R D ai ai Elementset i 1 2 n n 0 R H H ai 1 ai D i 2 n 操作 设L的型为LIST线性表实例 x的型为elementtype的元素实例 p为位置变量 所有操作描述为 Insert x p L Locate x L Retrieve p L Delete p L Previous p L Next p L MakeNull L First L End L 数学模型 3 1抽象数据型线性表 举例 设计函数Deleval LIST 3 2线性表的实现 问题 确定数据结构 存储结构 实现型LIST 并在此基础上实现各个基本操作 存储结构的三种方式 连续的存储空间 数组 静态存储 非连续存储空间 指针 链表 动态存储 游标 连续存储空间 动态管理思想 静态链表 3 2 1指针和游标 指针 地址量 其值为另一存储空间的地址 游标 整型指示量 其值为数组的下标 用以表示指定元素的 地址 或 位置 所在的数组下标 3 2 2线性表的数组实现 顺序表 把线性表的元素逻辑顺序依次存放在数组的连续单元内 再用一个整型量表示最后一个元素所在单元的下标 特点 元素之间的逻辑关系 相继 相邻关系 用物理上的相邻关系来表示 用物理上的连续性刻画逻辑上的相继性 是一种随机存储结构 也就是可以随机存取表中的任意元素 其存储位置可由一个简单直观的公式来表示 3 2 2线性表的数组实现 类型定义 definemaxlength100structLIST elementtypeelements maxlength intlast 位置类型 typedefintposition 线性表L LISTL 表示 L elements p L的第p个元素L lastL的长度 最后元素的位置 3 2 2线性表的数组实现 操作 voidInsert elementtypex positionp LIST 时间复杂性 O n positionLocate elementtypex LISTL positionq for q 1 q L last q if L elements q x return q return L last 1 时间复杂性 O n 3 2 2线性表的数组实现 elementtypeRetrieve positionp LISTL if p L last error 指定元素不存在 elsereturn L elements p 时间复杂性 O 1 voidDelete positionp LIST 时间复杂性 O n 3 2 2线性表的数组实现 positionPrevious positionp LISTL if pL last error 前驱元素不存在 elsereturn p 1 时间复杂性 O 1 positionEnd LISTL return L last 1 O 1 positionFirst LISTL return 1 复杂性 O 1 positionNext positionp LISTL if p L last error 前驱元素不存在 elsereturn p 1 时间复杂性 O 1 positionMakeNull LIST 时间复杂性 O 1 3 2 2线性表的数组实现 3 2 3线性表的指针实现 单链表 一个线性表由若干个结点组成 每个结点均含有两个域 存放元素的信息域和存放其后继结点的指针域 这样就形成一个单向链接式存储结构 简称单向链表或单向线性链表 结构特点 逻辑次序和物理次序不一定相同 元素之间的逻辑关系用指针表示 需要额外空间存储元素之间的关系 非随机存储结构 3 2 3线性表的指针实现 操作讨论 3 2 3线性表的指针实现 插入元素 p a 表头插入元素 b 中间插入元素 c 表尾插入元素 q newcelltype q element x q next p next p next q 或 temp p next p next newcelltype p next element x p next next temp 讨论表头结点的作用 操作讨论 3 2 3线性表的指针实现 删除元素 q p next p next q next deleteq 或 q p next p next p next next deleteq 讨论结点ai的位置p 操作 3 2 3线性表的指针实现 positionEnd LISTL positionq q L while q next NULL q q next return q 时间复杂性 O n voidInsert elementtypex positionp positionq q newcelltype q element x q next p next p next q 时间复杂性 O 1 操作 3 2 3线性表的指针实现 positionLocate elementtypex LISTL positionp p L while p next NULL if p next element x returnp elsep p next returnp 时间复杂性 O n elementtypeRetrieve positionp return p next element 时间复杂性 O 1 操作 3 2 3线性表的指针实现 voidDelete positionp positionq if p next NULL q p next p next q next deleteq 时间复杂性 O 1 positionPrevious positionp positionq if p L next error 不存在前驱元素 else q L while q next p q q next returnq 时间复杂性 O n 操作 3 2 3线性表的指针实现 positionNext positionp positionq if p next NULL error 不存在后继元素 else q p next returnq 时间复杂性 O 1 positionMakeNull LIST 时间复杂性 O 1 操作 3 2 3线性表的指针实现 positionFirst LISTL returnL 时间复杂性 O 1 静态链表与动态链表的比较 比较参数 表的容量 存取操作 时间 空间 链式存储灵活 易扩充顺序存取访问元素费时间实际长度 节省空间 顺序存储固定 不易扩充随机存取插入删除费时间估算表长度 浪费空间 举例 遍历线性链表 按照线性表中元素的顺序 依次访问表中的每一个元素 每个元素只能被访问一次 voidTravel LISTL positionp p L next while p NULL cout p element p p next 单链表逆置问题 方法一 设表头为L 算法如下 p L next next q p next L next next NULL while p null p next L next L next p p q q q next 方法二 线性表由q来表示p null w q while w null w w next q next p p q q w 3 2 5双向链表 双向连表 在单向链表中 对每个结点增加一个域 用一指向该结点的前驱结点 线性表的这种存储结构称为双向链表 优点 实现双向查找 单链表不易做到 表中的位置i可以用指示含有第i个结点的指针表示 缺点 空间开销大 3 2 5双向链表 操作 删除位置p的元素 voidDelete positionp DLIST voidInsert elementtypex positionp DLIST 3 2 6环形链表 对线性链表的改进 解决 单向操作 的问题 改进后的链表 能够从任意位置元素开始 访问表中的每一个元素 单向环形链表 在 不带表头结点 的单向链表中 使末尾结点的指针域指向头结点 得到一个环形结构 用指向末尾结点的指针标识这个表 存储结构 与单向链表相同 略 操作 在表左端插入结点Insert x FIRST R R LInsert x R voidLInsert elementtypex LIST 3 2 6环形链表 在表右端插入结点Insert x END R R RInsert x R voidRInsert elementtypex LISTR LInsert x R R R next 操作 从表左端删除结点Delete First R R LDelete R voidLDelete LIST 3 2 6环形链表 3 2 6环形链表 双向环形链表的结构与双向连表结构相同 只是将表头元素的空previous域指向表尾 同时将表尾的空next域指向表头结点 从而形成向前和向后的两个环形链表 对链表的操作变得更加灵活 举例 设计算法 将一个单向环形链表反向 头元素变成尾元素 尾元素变成新的头元素 依次类推 3 2 6环形链表 3 3栈 Stack 栈是线性表的一种特殊形式 是一种限定性数据结构 也就是在对线性表的操作加以限制后 形成的一种新的数据结构 定义 是限定只在表尾进行插入和删除操作的线性表 栈又称为后进先出 LastInFirstOut 的线性表 简称LIFO结构 栈举例 3 3栈 栈的基本 MakeNull S 操作 Top S Pop S Push x S Empty S 举例 利用栈实现行编辑处理 设定符号 为擦讫符 用以删除 前的字符 符号 为删行符 用以删除当前编辑行 原理 一般字符进栈 读字符擦讫符退栈 删行符则清栈 3 3 1栈的实现 3 3栈 1 顺序存储 顺序栈示意图 top 类型定义 enumBoolen TRUE FALSE typedefstruct elementtypeelements maxlength inttop STACK STACKS 栈的容量 maxlength 1 栈空 S top 0 栈满 S top maxlength 1 栈顶元素 S elements S top 3 3 1栈的实现 1 顺序存储 操作 voidMakeNull STACK BooleanEmpty STACKS if S top 1 returnTRUEelsereturnFALSE elementtypeTop STACKS ifEmpty S returnNULL elsereturn S elements S top 3 3 1栈的实现 1 顺序存储 操作 voidPop STACK voidPush elementtypex STACK 3 3 1栈的实现 2 链式存储 采用由指针形成的线性链表来实现栈的存储 要考虑链表的哪一端实现元素的插入和删除比较方便 实现的方式如右图所示 其操作与线性链表的表头插入和删除元素相同 structnode Elementtypeval node next typedefnode STACK voidMakeNull STACK voidPop STACK booleanEmpty STACKS if S next returnFALSE elsereturnTRUE 多个栈共用一个存储空间的讨论 3 4排队或队列 Queue 队列是对线性表的插入和删除操作加以限定的另一种限定性数据结构 定义 将线性表的插入和删除操作分别限制在表的两端进行 和栈相反 队列是一种先进先出 FirstInFirstOut 简称FIFO结构 的线性表 操作 MakeNull Q Front Q EnQueue x Q DeQueue Q Empty Q 3 4队列 Queue 3 4 1队列的指针实现 元素的 型 structcelltype elementtypeelement celltype next 队列的 型 structQUEUE celltype front celltype rear 3 4 1队列的指针实现 操作 voidMakeNull QUEUE BooleanEmpty Q QUEUE elementtypeFront Q QUEUEQ returnQ front next element 3 4 1队列的指针实现 voidEnQueue elementtypex QUEUE voidDelete QUEUE 3 4 2队列的数组实现 队列的 型 structQUEUE elementtypeelement maxlength intfront intrear 随着不断有元素出队和进队 插入和删除 队列的状态由1变成2 此时an占据队列的最后一个位置 第n 1个元素无法进队 但实际上 前面部分位置空闲 3 4 2队列的数组实现 解决假溢出的方法有多种 一是通过不断移动元素位置 每当有元素出队列时 后面的元素前移一个位置 使队头元素始终占据队列的第一个位置 第二种方法是采用循环队列 插入元素 Q rear Q rear 1 maxlength删除元素 Q front Q front 1 maxlength 队空 Q rear 1 maxlength Q front队满 Q rear 1 maxlength Q front 3 4 2队列的数组实现 问题 如何解决循环队列中队空与队满状态相同 方法一 约定队列头指针在队列尾指针的下一位置上 方法二 另设一个标志位用以区别队空与队满两种状态 结论 两种方法的代价是相同的 操作 intaddone inti return i 1 maxlength voidMakeNull QUEUE booleanEmpty Q QUEUEQ if addone Q rear Q front returnTRUE elsereturnFALSE 3 4 2队列的数组实现 操作 elementtypeFront QUEUEQ if Empty Q returnNULL elsereturn Q elements Q front voidEnQueue elementtypex QUEUEQ if addone addone Q rear Q front error 队列满 else Q rear addone Q rear Q elements Q rear x 3 4 2队列的数组实现 voidDeQueue QUEUEQ if Empty Q error 空队列 elseQ front addone Q front 3 6串 String 串是线性表的一种特殊形式 表中每个元素的类型为字符型 是一个有限的字符序列 串的基本形式可表示成 S a1a2a3 an 其中 charai 0 i n n 0 当n 0时 为空串 n为串的长度 C语言中串有两种实现方法 1 字符数组 如 charstr1 10 2 字符指针 如 char str2 3 6 1抽象数据型串 3 6 2串的实现 1 串的顺序存储采用连续的存储空间 数组 自第一个元素开始 依次存储字符串中的每一个字符 charstr 10 China 操作 NULL ISNULL IN LEN CONCAT SUBSTR INDEX 2 串的链式存储构造线性链表 element类型为char 自第一个元素开始 依次存储字符串中的每一个字符 3 7数组 ARRAY 3 7 1抽象数据型数组 数组是由下标 index 和值 value 组成的序对 index value 的集合 也可以定义为是由相同类型的数据元素组成有限序列 数组在内存中是采用一组连续的地址空间存储的 正是由于此种原因 才可以实现下标运算 所有数组都是一个一维向量 数组1 a1 a2 a3 ai an 数组2 a11 a1n a21 a2n aij am1 amn 1 i m 1 j n 数组3 a111 a11n a121 a12n aijk amn1 amnp 1 i m 1 j n 1 k p 3 7 2数组的实现 1 数组的顺序存储 数组的顺序表示 指的是在计算机中 用一组连续的存储单元来实现数组的存储 目前的高级程序设计语言都是这样实现的 两种存储方式 一是按行存储 C语言 PASCAL等 二是按列存储 FORTRAN等 elementtypeA 2 3 1 数组的顺序存储 对二维数组有 LOC A i j LOC A 0 0 n i j 0 i m 1 0 j n 1对三维数组有 LOC A i1 i2 i3 LOC A 0 0 0 d2 d3 i1 d3 i2 i3 0 i1 d1 1 0 i2 d2 1 0 i3 d3 1 2 数组的压缩存储 特殊矩阵若n阶矩阵A中的元素满足下述性质aij aji1 i j n则称n阶对称阵 对于对称矩阵 为实现节约存储空间 我们可以为每一对对称元素分配一个存储空间 这样 原来需要的n2个元素压缩存储到n n 1 2个元素空间 对称关系 设sa 0 n n 1 2 做为n阶对称阵A的存储结构 则Sa k 和aij的一一对应关系为 i i 1 2 j当i jk j j 1 2 i当i j 2 稀疏矩阵 稀疏矩阵中 零元素的个数远远多于非零元素的个数 为实现压缩存储 仍考虑只存储非零元素 第4章树 1 一个结点x组成的集 x 是一株树 这个结点x也是这株树的根 2 假设x是一个结点 T1 T2 Tk是k株互不相交的树 我们可以构造一株新树 令x为根 并有k条边由x指向树T1 T2 Tk 这些边也叫做分支 T1 T2 Tk称作根x的树之子树 SubTree 树的构造性递归定义 递归定义 但不会产生循环定义 一株树的每个结点都是这株树的某株子树的根 注意 树的逻辑结构特点 除根结点之外 每株子树的根结点有且仅有一个直接前驱 但可以有0个或多个直接后继 即一对多的关系 反映了结点之间的层次关系 结点的度 元结点的度 元 和树的度叶结点 终端结点 非终端结点 分支结点 子结点 儿子 子女 父结点 双亲 兄弟 结点 和树的高 路 径 长祖先 结点 后代 子孙 结点层 结点的高路 路径 有序树无序树森林 森林forest 是n 0株互不相交的树的集合 二叉树 一棵二叉树是结点的一个有限集合 该集合或者为空 或者是由一个根结点和两棵分别称为左子树和右子树的 互不相交的二叉树组成 结构特点 每个结点最多只有两个孩子结点 即结点的度不大于2 子树有左右之别 子树的次序 位置 不能颠倒 基本形态 4 2 1二叉树的定义及遍历 高度为K且有2K 1个结点的二叉树称为满二叉树 设二叉树高度为K 称满足下列性质的二叉树为完全二叉树 1 所有的叶都出现在K或K 1层 2 K 1层的所有叶都在非终结结点的右边 3 除了K 1层的最右非终结结点可能有一个 只能是左分支 或两个分支之外 其余非终结结点都有两个分支 二叉树的遍历 根据某种策略 按照一定的顺序访问二叉树中的每一个结点 使每个结点被访问一次且只被访问一次 结果得到二叉树结点的线性序列 根 D 左孩子 L 和右孩子 R 三个结点可能出现的顺序有 DLR LDR LRD DRL RDL RLD 要讨论的三种操作分别为 先根顺序DLR 中根顺序LDR 后根顺序LRD 策略 左孩子结点一定要在右孩子结点之前访问 先根顺序遍历二叉树 若二叉树非空则 访问根结点 先根顺序遍历左子树 先根顺序遍历右子树 中根顺序遍历二叉树 若二叉树非空则 中根顺序遍历左子树 访问根结点 中根顺序遍历右子树 后根顺序遍历二叉树 若二叉树非空则 后根顺序遍历左子树 后根顺序遍历右子树 访问根结点 所得到的线性序列分别称为先根 序 中根 序 和后根 序 序列 如图所示的二叉树 对其进行先序 中序和后序遍历都是从根结点A开始的 且在遍历过程中经过结点的路线是一样的 只是访问的时机不同而已 性质1二叉树的第i层最多有2i 1个结点 i 1 证明用数学归纳法 性质2高度为K的二叉树最多有2K 1个结点 K 1 证明用求等比级数前K项和的公式 20 21 22 2K 2K 1性质3对任何一棵二叉树 如果其叶结点有n0个 度为2的非叶结点有n2个 则有n0 n2 1证明 若设度为1的结点有n1个 结点总数为n 分支总数为B 则根据二叉树的定义 n n0 n1 n2B 2n2 n1 n 1因此 有2n2 n1 n0 n1 n2 1n2 n0 1n0 n2 1 4 2 2二叉树的性质 性质4具有n n 0 个结点的完全二叉树的高度为 log2 n 1 或 log2n 1证明 设完全二叉树的高度为K 则有2K 1 1 n 2K 1变形2K 1 n 1 2K2K 1 n 2K取对数K 1 log2 n 1 KK 1 log2n K因此有 log2 n 1 KK log2n 1 性质5完全 或满 二叉树的顺序存储结构及其性质如果将一棵有n个结点的完全二叉树自顶向下 同一层自左向右连续给结点编号 1 2 n 且使该编号对应于数组的下标 则有以下关系 若i 1 则i是根结点 无父结点若i 1 则i的父结点为 i 2 若2 i n 则i有左儿子且为2 i 否则 i无左儿子 若2 i 1 n 则i有右儿子且为2 i 1 否则 i无右儿子 若i为偶数 且i n 则有右兄弟 且为i 1 若i为奇数 且i n i 1 则其左兄弟 且为i 1 voidPreorder BT BTREEBT if IsEmpty BT visit DATA BT Preorder LCHILD BT Preorder RCHILD BT 例1 1 写一个递归函数 按先根顺序列出二叉树中每个结点的DATA域之值 例1 2 写一个递归函数 按中根顺序列出二叉树中每个结点的DATA域之值 voidInorder BT BTREEBT if IsEmpty BT Inorder LCHILD BT visit DATA BT Inorder RCHILD BT 例1 3 写一个递归函数 按后根顺序列出二叉树中每个结点的DATA域之值 voidPostorder BT BTREEBT if IsEmpty BT Postorder LCHILD BT Postorder RCHILD BT visit DATA BT 二元树的遍历的非递归过程 voidNInorder BT BTREEBT STACKS BTREET MakeNull S T BT while IsEmpty T Empty S if IsEmpty T Push T S T T LCHILD T else T Top S Pop S visit DATA T T T RCHILD T 进栈 左走一步 退栈 右走一步 一 顺序表示1 完全 或满 二叉树 根据性质5 如已知某结点的层序编号i 则可求得该结点的双亲结点 左孩子结点和右孩子结点 采用一维数组 按层序顺序依次存储二叉树的每一个结点 如下图所示 4 2 4二叉树的表示 二 左右链表示 structnode structnode lchild structnode rchild datatypedata typedefstructnode BTREE 三 二叉树的线索表示 线索二叉树 若结点p有左孩子 则p lchild指向其左孩子结点 否则令其指向其 先序 中序 后序 前驱 若结点p有右孩子 则p rchild指向其右孩子结点 否则令其指向其 先序 中序 后序 后继 同时在每个结点中增加两个标志位 以区分该结点的的两个链域是指向其左 右孩子还是指向某种遍历的前驱 后继 structnode datatypedata structnode lchild rchild enumboollchild rchild typdefstructnode THTREE p ltag TRUEp lchild指向左孩子FALSEp lchild指向 中序 前驱 算法 求 p 中序前驱 分析 1 当p ltag FALSE时 p lchild即为所求 线索 2 当p ltag TRUE时 p为p的左子树的最右结点 THTREEInPre THTREEp THTREEQ Q p lchild if p ltag TRUE while Q rtag TRUE Q Q rchild return Q voidPreOrder BTREET STACKS Makenull S 递归工作栈structnode p T while p NULL coutdatarchild NULL Push S p rchild if p lchild NULL p p lchild 进左子树else p Top S Pop S 左子树空 访问右子树 例先序遍历的非递归算法 栈顶保存当前结点的右子树 voidPreorder BTREEbt STACKS BTREEt t bt Makenull S while t null Empty S whlie t null visit t data push t S t t lc if Empty S t top S pop S t t rc 例先序遍历的非递归算法 栈顶保存当前结点的左子树 4 3 1树的三种遍历 先根顺序 访问根结点 先根顺序遍历T1 先根顺序遍历T2 先根顺序遍历Tk 中根顺序中根顺序遍历T1 访问根结点 中根顺序遍历T2 中根顺序遍历Tk 后根顺序后根顺序遍历T1 后根顺序遍历T2 后根顺序遍历Tk 访问根结点 先根遍历序列 RADEBCFGHK中根遍历序列 DAERBGFHKC后根遍历序列 DEABGHKFCR D A E R B C F G H K 4 3 2树的存储结构 1 树的数组表示法 双亲表示 父链表示 单链表示 首先 对树T的结点按下列规则依次编号 根结点编号为1 对于T中的每一个已编号的结点k 按从左到右的顺序对k的儿子结点编号 然后 令树T的结点编号与一个结构体数组的下标对应 结构体数组的每个单元包括两个域 parent和data域 且规定 A i data 结点i的数据域的值 父链表示 structnode intparent chardata typedefnodeTREE 11 TREET 存储结构 基本操作的实现 结构特点 每个结点均保存父结点所在的数组单元下标兄弟结点的编号连续 易求父结点 祖先结点 如i的父结点的父结点T T i parent parent易求结点数据域的值 T i data不便于CREATEk操作 2 树的邻接表表示法 孩子表示法 孩子链表表示法 typedefstructCTNode intchild structCTNode next ChildPtr typedefstruct Telementtypedata ChildPtrfirstchild CTBox typedefstruct CTBoxnodes MAX TREE SIZE intn r Ctree 1 结点结构 2 存贮示例 因每个结点有且仅有两个指针域 所以也称为二叉树表示方法 3 树的 左 孩子 右 兄弟表示法 二叉树表示法 类型 typedefstructCSNode 动态存储结构ElemTypedata structCSNode firstchild nextsibling typedefstructCSNode TREE 森林 树 转换为二元树 连线 把每株树的各兄弟结点连起来 把各株树的根结点连起来 视为兄弟 抹线 对于每个结点 只保留与其最左儿子的连线 抹去该结点与其它结点之间的连线旋转 按顺时针旋转45度角 左链竖画 右链横画 4 5树的应用 没有度数为1的结点外结点数 内结点数 1 为什么 有n个外结点的扩充二元树共有2n 1个结点 4 5 3哈夫曼 Huffman 树及其应用 在二叉树中 对于每个结点 若出现空 左 右 子树 则为其加上一个特殊的结点 称为外结点 由此得到的新二叉树称为原二叉树的扩充二叉树 而原二叉树的结点称为内结点 一 哈夫曼树的由来及其构造 内路径长I 2 1 3 2 1 3 11外路径长E 1 2 5 3 2 4 25 2 扩充二元树的外路径长 内路径长及相互关系 外路径长E 从根结点到每个外结点的路径长之和 E lj内路径长I 从根结点到每个内结点的路径长之和关系 E I 2 n n为内结点的个数 4 5 3哈夫曼 Huffman 树及其应用 设 wi 2 3 4 11 求 wj lj 加权路长 a 11 1 4 2 2 3 3 3 34 b 2 1 3 2 4 3 11 3 53 c 2 2 11 2 3 2 4 2 40 3 扩充二元树的加权路径长 外结点的加权路径长 设每个外结点j对应一个实数wj 称为外结点的权值 lj是从根到外结点j的路长 则wj lj个称为外结点j的加权路长 扩充二元树的加权路长 WPL wj lj称为扩充二元树的加权路长 4 5 3哈夫曼 Huffman 树及其应用 哈夫曼树定义 在给定权值为w1 w2 wn的n个叶结点所构成的所有扩充二叉树中 WPL wj lj最小的称为huffman树 在哈夫曼树中 权值越小 离根越远 权值大的结点离根最近 构造算法 1 由给定的n个权值 w0 w1 w2 wn 1 构造具有n棵扩充二叉树的森林F T0 T1 T2 Tn 1 其中每棵扩充二叉树Ti只有一个带权值wi的根结点 其左 右子树均为空 2 重复以下步骤 直到F中仅剩下一棵二叉树为止 在F中选取两棵根结点的权值最小的扩充二叉树 做为左 右子树构造一棵新的二叉树 且置新的二叉树的根结点的权值为其左 右子树上根结点的权值之和 在F中删去这两棵二叉树 把新的二叉树加入F 哈夫曼树 最优二叉树 F 7 5 2 4 F 7 5 6 7 5 2 4 0 初始 1 合并 2 4 F 7 11 7 5 2 4 7 5 2 4 6 6 11 2 合并 5 6 F 18 5 3 合并 7 11 2 7 4 6 11 18 举例 编码和译码 哈夫曼 Huffman 树及其应用 是指将文件 字符集 中的每个字符转换为一个唯一的二进制串 编码 解码 是指将二进制串转换为对应的字符 译码 对于给定的字符集 可能存在多种编码方案 但应选择最优的 3 编码的前缀性 对字符集进行编码时 如果任意一个字符的编码都不是其它任何字符编码的前缀 则称这种编码具有前缀性或前缀编码 前缀编码 注意 等长编码具有前缀性 变长编码可能使译码产生二义性 即不具有前缀性 如 E 00 T 01 W 0001 则译码时无法确定信息串是ET还是W 最优编码 Huffman编码 Huffman编码问题和编码算法 对于给定的字符集以及每个字符出现的概率 使用频度 求字符集的最优的前缀性编码 Huffman编码问题 用huffman算法求字符集最优编码的算法 使字符集中的每个字符对应一株只有叶结点的二叉树 叶的权值为对应字符的使用频率 利用huffman算法来构造一株huffman树 对huffman树上的每个结点 左支附以0 右支附以1 或者相反 则从根到叶的路上的0 1序列就是相应字符的编码 Huffman编码问题和编码算法 哈夫曼 Huffman 树及其应用 举例 第5章图及其相关算法 图是由顶点集合 vertex 及顶点间的关系集合组成的一种数据结构 Graph V E 其中V x x 某个数据对象 是顶点的有穷非空集合 E x y x y V 或E x y V 是顶点之间关系的有穷集合 也叫做边 edge 集合 有向图若图G的每条边都有方向 则称G为有向图 Digraph 在有向图中 有向边 也称弧 都是顶点的有序对 无向图若图G的每条边都是没有方向的 则称G为无向图 UnDigraph 在无向图中 每条边都是顶点的无序对 x y 定义图 5 1图的基本概念 无向图中顶点v的度 Degree 是关联于该顶点的边的数目 或与该顶点相邻的顶点数目 记为D v 若G是有向图 则把邻接到顶点v的顶点数目或边数目称为顶点v的入度 Indegree 记为ID v 把邻接于顶点v的顶点数目或边数目称为顶点v的出度 Outdegree 记为OD v 顶点v的度则定义为该顶点的入度和出度之和 即D v ID v OD v 无论是有向图还是无向图 顶点数n 边数e和度数之间的关系为 定义结点的度 在无向图G中 若存在一个顶点序列vp vi1 vi2 vim vq 使得 vp vi1 vi1 vi2 vim vq E G 则称顶点vp路到vq有一条路径 Path 在有向图G中 若存在一个顶点序列vp vi1 vi2 vim vq 使得有向边 E G 则称顶点vp路到vq有一条有向路径 Path 非带权图的路径长度是指此路径上边的条数 带权图的路径长度是指路径上各边的权之和 简单路径若路径上各顶点v1 v2 vm均不互相同 则称这样的路径为简单路径 简单回路若路径上第一个顶点v1与最后一个顶点vm重合 则称这样的简单路径为回路或环 定义路 径 路径长 简单路 简单环路 连通图与连通分量在无向图中 若从顶点vi到顶点vj有路径 则称顶点vi与vj是连通的 如果图中任意一对顶点都是连通的 则称此图是连通图 非连通图的极大连通子图叫做连通分量 强连通图与强连通分量在有向图中 若对于每一对顶点vi和vj 都存在一条从vi到vj和从vj到vi的路径 则称此图是强连通图 非强连通图的极大强连通子图叫做强连通分量 定义图的连通性 5 1图的基本概念 5 2 1邻接矩阵 AdjacencyMatrix 一 图的邻接矩阵表示 5 2图的存储表示 在图的邻接矩阵表示中 有一个记录各个顶点信息的顶点表 还有一个表示各个顶点之间关系的邻接矩阵 设图A V E 是一个有n个顶点的图 图的邻接矩阵是一个二维数组A edge n n 定义 4 1 0 无向图的邻接矩阵是对称的 有向图的邻接矩阵可能是不对称的 在有向图中 统计第i行1的个数可得顶点i的出度 统计第j列1的个数可得顶点j的入度 在无向图中 统计第i行 列 1的个数可得顶点i的度 二 网络的邻接矩阵 defineMaxValueInt Max 在中 defineNumEdges50 边条数 defineNumVertices10 顶点个数typedefcharVertexData 顶点数据类型typedefintEdgeData 边上权值类型typedefstruct VertexDatavexlist NumVertices 顶点表EdgeDataedge NumVertices NumVertices 邻接矩阵 边表 可视为边之间的关系intn e 图中当前的顶点个数与边数 MTGraph voidCreateMGragh MTGragh G 建立 无向 图的邻接矩阵 inti j k w scanf d d 空间复杂性 S O n n2 时间复杂性 T O n n2 e 当e n T O n2 5 2 2邻接表 AdjacencyList 一 图的邻接表表示 对于G中的每个顶点vi 把所有邻接 于 vi的顶点vj链成一个单链表 称为关于vi的邻接表 邻接表中每个表结点都有两个域 其一是邻接点域adjvex 用以存放与vi相邻顶点的序号 其二是链域next 用来将邻接表的所有表点链在一起 另外若要表示边上的信息如 权值 则在表结点中还应增加一个数据域cost 无向图G1邻接表 G2的逆邻接表 有向图G2邻接表 在无向图的邻接表中 一条边 Vi Vj 在邻接表中出现两次 一次在关于Vi的邻接表中 一次在关于Vj的邻接表中 关于顶点Vi的邻接表的结点数目为顶点Vi的度 在有向图的邻接表中 一条边在邻接表中出只现一次关于顶点Vi的邻接表中结点数目为顶点Vi的出度 在逆邻接表中关于顶点Vi的邻接表中结点数目为顶点Vi的入度 defineNumVertices10 顶点个数typedefcharVertexData 顶点数据类型typedefintEdgeData 边上权值类型typedefstructnode 边表结点intadjvex 邻接点域 下标 EdgeDatacost 边上的权值structnode next 下一边链接指针 EdgeNode typedefstruct 顶点表结点VertexDatavertex 顶点数据域EdgeNode firstedge 边链表头指针 VertexNode typedefstruct 图的邻接表VertexNodevexlist NumVertices intn e 图中当前的顶点个数与边数 AdjGraph 在邻接矩阵中求边的数目e 必须检查整个矩阵 所耗时间是O n2 与边的个数e无关 而在邻接表中求边的数目e 只要对每个边表的结点个数进行计数即可求得e 所耗时间是O e n 因此当e是否为图的一条边 只要判断矩阵中的第i行第j列是否为非零元素即可 但在邻接表中 须扫描第i个边表 最坏情况下消耗时间O n 空间复杂度 两种存储结构的比较 图的搜索 从图的某个顶点出发 访遍图中所有的顶点 且使每个顶点被访问一次且仅被访问一次 称为图的搜索 遍历 GraphTraversal 访问 有许多方法和策略 不同的 访问 方法和策略导致不同的搜索算法 因此图