考研计机数据结构思维导图一图了解知识脉络和考点.pdf

1.1数据结构的基本概念数据 数据是信息的载体， 是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合数据元素 数据元素是数据的基本单位， 通常作为一个整体进行考虑和处理数据对象数据对象是具有相同性质的数据元素的集合， 是数据的一个子集数据类型是一个值的集合和定义在此集合上的一组操作的总称基本概念和术语数据类型原 子 类 型 ： 其值不可再分的数据类型分类结 构 类 型 ： 其值可以再分解为若干成分（ 分量） 的数据类型抽象数据类型： 抽象数据组织及与之相关的操作数据结构是相互之间存在一种或多种特定关系的数据元素的集合数据结构逻辑结构数据结构包括三方面 存储结构数据的运算逻辑结构是指数据元素之间的逻辑关系， 即从逻辑关系上描述数据数据的逻辑结构分类与数据的存今线性结构旨无关，是独立于计算机的线性表笆队列数组非线性结构存储结构是推概述集合树图号数据结构在计算机中的表示（ 又称映像） ， 也称物理结构数据元素的表示和关系的表示数据的存储结构存储结构是用计算机语言实现的逻辑结构， 它依赖于计算机语言把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中， 元素之间的关系由存储单元的邻接关系来体现顺序存储优 点 ： 可以实现随机存取， 每个元素占用最少的存储空间分类缺 点 ： 只能使用相邻的一整块存储单元， 因此可能产生较多的外部碎片数据结构三要素要求逻辑上相邻的元素在物理位置上也相邻， 借助指示元素存储地址的指针来表示元素之间的逻辑关系链式存储优 点 ： 不会出现碎片现象， 能充分利用所有存储单元缺 点 ： 每个元素因存储指针而占用额外的存储空间， 且只能实现顺序存取在存储元素信息的同时， 还建立附加的索引表索引存储散列存储优 点 ： 检索速度快" 一 附加的索引表额外占用存储空间缺 点j! 增加和删除数据时也要修改索引表， 会花费较多的时间根据元素的关键字直接计算出该元素的存储地址， 又 称哈希（Hash ）存储优 点 ： 检索、增加和删除结点的操作都很快缺 点 ： 若散列函数不好， 则可能出现元素存储单元的冲突， 而解决冲突会增加时间和空间开销数据的运算施加在数据上的运算包括运算的定义和实现。

运算的定义是针对逻辑结构的， 指出运算的功能运算的实现是针对存储结构的， 指出运算的具体操作步骤1.2算法和算法评价算法的基本概念-算法是对特定问题求解步骤的一种描述， 它是指令的有限序列， 其中的第条指令表示一个或多个操作有穷性： 一个算法必须执行有穷步之后结束，且街一步都可在有穷时间内完成重要特性确定性： 算法中每条指令必须有确切的含义， 对于相同的输入只能得出相同的输出可行性 : 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现输入 ： 一个苜法有零个或多个输入， 这些输入取自于某个特定的对象的集合输 出 ： 一个算法有一个或多个输出， 这些输出是与输入有着某种特定关系的埴优秀算法的标准正确性： 算法应能够正确地解决求解问题.可读性： 算法应具有良好的可读性， 以帮助人们理解健壮性： 输入非法数据时， 算法能适当地做出反应或进行处理， 而不会产生莫名其妙的输出结果效率与低存储量需求： 效率是指算法执行的时间， 存储量需求是指算法执行过程中所需要的最大存储空间， 这两者都与问题的规模有关算法效率的度量是通过时间复杂度和空间复杂度来描述的一个语句的频度是指该语句在算法中被重匏执行的次数时 间 复 杂 度 - . . . . - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -一 —・ 常见的渐近时间复杂度为} 一般情况下, 嵌套的循环次数是时间复杂度指数( 存在特殊情况)算法效率的度量空间复杂度计算规则算法的空间复杂度S ( n )定义为该算法所耗费的存储空间, 它是问题规模n的函数.一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变员和输入数据外， 还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间算法原地工作是指算法所需的辅助空间为常由， 即0 ( 1 )加法规则： 0 ( f ( n ) ) + 0 ( g ( n ) ) = 0 ( m a x ( f ( n ) , g ( n ) )乘法规则： O ( f ( n ) ) x O ( g ( n ) ) = 0 ( f ( n ) x g ( n ) )线性表是具有相同数据类型的n个数据元素的有限序列， 其中n为表长， 当n=0时线性表是一个空表2.1线性表的定义和基本操作表中元素的个数有限线性表的特点表中元素具有逻辑上的顺序性， 表中元素有其先后次序■线性表的定义-表中元素都是数据元素， 每个元素都是单个元素每个元索占有相同大小的存储空间注意 线性表是一种逻辑结构， 表示元素之间一对一的相邻关系1顺序表和链表是指存储结构InitList(&L):初始化表， 构造一个空的线性表Length (L):求表长, 返回线性表L的长度， 即L中数据元素的个数LocateElem(L,e): 按值查找操作， 在表L中查找具有给定关键字值的元素Get日em(L,i):按位查找操作， 获取表L中第i个位置的元素的值口线性表的基本操作-Listinsert (&L,i.e):插入操作. 在表L中的第i个位置上插入指定元素ListDelete(&Lf i, &e):删除操作, 删除表L中第i个位置的元素, 并用e返回删除元素的值PrintList (L):输出操作， 按前后顺序输出线性表L的所有元素值Empty (L):判空操作， 若L为空表， 则返回true,否则返回falseDestroyList(&L):销毁操作， 销毁线性表， 并释放线性表L所占用的内存空间考试尽量使用这些函数名称, 方便老师阅卷「顺序表的定义线性表的顺序存储又称顺序表 gH：人_ 至 尸 一 加 一 美m汩附*r s me国- 彷* 五牌降枇本山《1丑-安r逻辑上相邻的两个兀素在物理位置上也相邻用一组地址连续的存储单兀依次存储线性表中的数据兀素I静态分配 数组的大小和空间已经固定， 一旦空间占满， 再加入新的数据将会产生溢出， 程序就会崩溃—维数组空间分配 存储数组的空间是在程序执行过程中通过动态存储分配语句分配一的动 态 分 配r-------------------------------------——— — —~4一 ~ | 一旦数据空间占满， 就另外开辟一块更大的存储空间， 用以替换原来的存储空间注意 动态分配仍然是顺序存储结构， 物理结构没有变化， 依然是随机存取方式， 只是分配的空间大小可以在运行时决定随机访问， 即通过首地址和元素序号可在时间0(1)内找到指定的元素特点 存储密度高， 每个结点只存储数据元素 与链表形成对比逻辑上相邻的元素物理上也相邻，当执行播入和删除操作时，需要移动大量元素2.2线性表的顺序表示,插入操作由于顺序表的中元素的物理位置是相邻的， 所以当插入新元素的时候就需要对表中的元素进行整体移动最好情况： 在表尾插入(i = n+1),元素后移语句将不执行, 时间复杂度为。

1)最坏情况： 在表头插入(i=D,元素后移语句将执行n次 ， 时间复杂度为0(n )实现情况( 长度为n )假设pi ( pi = l/(n+ l))是在第i个位置上插入一个结点的概率平均情况则在长度为n的线性表中插入一个结点时， 移动节点的平均次数为 沙屋为" T " W' +D*第或时间复杂度为0 (2即为移动元素， 对想要删除的元素进行覆盖顺序表上基本操作的实现 删除操作最好情况： 删除表尾元素(i = n ) ,无须移动元素， 时间复杂度为0(1)最坏情况： 删除表头元素(i=l),需移动除第一个元素外的所有元素， 时间复杂度为0(n)假设pi ( pi = 1/n)是在第i个位置上删除一个结点的概率平均情况理生长度为n的线性表中删强一个色点时， 删除节点的巴羽逍啰 2 上I 〃 〃，“时间宜杂度为0(n)I n-(-〃- --- 1-) - - -n---l- -n 22最好情况: 查找的元索就在表头， 仅需比较一次, 时间复杂度为0(1)最坏情况: 查找的元素在表尾( 或不存在) 时， 在要比较n次, 时间复杂度为0(n )按 值 查 找 鲤 弊 整L 假设pi(pi=l/n )是查找的元素在第i ( l<=i<=L.length )个位置上的概率平均情况h + 1则在长度为n的线性表中查找值为e的元素所需比较的平均次数为M n 2时间复杂度为0(n)2.3线性表的链式表示( 上)优 点 ： 可以随时存取表中的任意一个元素缺 点 ： 插入和删除操作需要移动大量元素背景 3a士 优 点 ： 不需要使用地址连续的存储单元， 插入和删除操作不需要移动元素， 而只需修改指针一 _—J 链 式 存 储 线 性 表 (---------------------- 1缺 点 ： 失去顺序表可随机存取的优点带头结点 空表判断：L= = NULL。

代码书写不便- 实 现 方 式 T不带头结点 空表判断：L・>next= = NULL.写代码更方便单链表的定义线性表的链式存储又称单链表， 它是指通过一组任意的存储单元来存储线性表中的数据元素对每个链表结点， 除存放元素自身的信息外， 还需要存放一个指向其后继的指针data :数据域， 存放数据元素---------r next :指针域， 存放其后继结点的地址优点 解决顺序表需要大量连续存储单元的缺点单链表附加指针域， 浪费存储空间- - - - - - - ： 查找某个特定的结点时， 需要从表头开始遍历， 依次直找从一个空表开始， 生成新结点， 并将读取到的数据存放到新结点的数据域中， 然后将新结点插入到当前链表的表头, 即头结点之后采用头插法建立单链表। ।与 次a3所 指 《 | 刈・左,/next=p->next;p->next=s;若在给定的节点下进行插入， 则时间复杂度为9(D本算法主要的时间开销在于查找第i-1个元素， 时间复杂度为0(n)对某一结点进行前插操作即寻找到要插入结点的前一个结点， 然后按照正常插入方法执行即可时间复杂度为O(n )单链表上基本操作的实现删除结点操作是将单链表的第1个结点删除。

先检查删除位置的合法性, 后直找表中第1-1个结点， 即被删结点的前驱结点， 再将其删除删除结点操作 - - - - - - -1 ； । t_. ; । । - c । t—示意图该算法£ . 一 . . . . . . . . . . . L:_ 要删除某个给定结点*P,通常的做法是先从链表的头结点开始顺序找到其前驱结点, 然后再执行删除操作“… --------- 1算法的时间复杂度为o(n )删除结点*p- - - - - - - - - - - - - 删除结点*p的操作可用删除*p的后继结点操作来实现， 实质就是将其后继结点的债赋予其自身， 然后删除后继结点---------------1时间复杂度为0 (1 ).一, 从第一个结点开始顺序依次访问表中的每个结点，为此需要设置一个计数器变量， 每访问一个结点， 计数器加L直到访问到空结点为止求 表 长 操 作 ,- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - -算法的时间复杂度为0(n )单链表只能从头结点依次顺序地向后遍历23线性表的链式表示( 中)■ 双链表------------------------1不能够快速的对其前驱结点进行操作概念 双链表结点中有两个指针pri。

市Inext,分别指向其前驱结点和后继结点pN 1 ] — 匕 I ] 4示意图 .一妾双链表的插入操作;- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -一 原则就是在进行双链表插入的时候要保证不会造成断链,J;.①一, ；一4 1 ・ 1 ।_口1」 _口 ： 1 4 =双链表的删除操作.平二图- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ---------- 1原则仍然是在进行操作的时候一定要考虑是否会造成断链操作的时候一定要考虑, 本操作顺序是否会造成后继结点的丢失循环单腿表和单链表的区别在于， 表中最后一个结点的指针不是NULL,而改为指向头结点， 形成了一个环循环单链表判空条件： 头结点的指针是否等于头指针循环链表循环双链表小 山… 如果是要在链首之前插入结点，此时效率明显更高时间复杂度0 (1 )在循环双链表中， 头结点的prior指针还要指向表尾结点在循环双链表1中， 某结点*p为尾结点时,p->next= = L当循环双链表为空表时， 其头结点的prior域和next域都等于L. 静 态 链 表 借 助 数 组 来 描 述 线 性 表 的 链 式 存 储 结 构 静态链表也要预先分配一块连续的内存空间基 本 结 构r--------- - - - - - - - - - - 结点也有数据域data和指针域next 这里的指针是结点的相对地址( 数组下标) ， 又称游标特点 静态链表以ne xt= E作为其结束的标志静态链表的插入、删除操作与动态链表的相同， 只需要修改指针， 而不需要移动元素优 点 ： 增、删 操作不需要大量移动元素缺 点 ： 不能随机存取， 只能从头结点开始依次往后直找； 容量固定不可变适用场景： ①不支持指针的低级语言； ②数据元素数量固定不变的场景( 如操作系统的文件分配表FAT )2.3线性表的链式表示( 下)基于存储的考虑土 Q 顺序表可以顺序存取， 也可以随机存取存取( 读写) 方式| - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ------------1链表只能从表头顺序存取元素顺序存储： 逻辑上相邻的元素， 对应的物理存储位置也相邻链式存储： 逻辑上相邻的元素， 物理存储位置则不一定相邻， 对应的逻辑关系是通过指针链接来表示的顺序表有序： 可采用折半查找, 此时的时间复杂度为O(log2n )直找、插入和删除操作顺序表无序时： 两者的时间复杂度均为。

n )r顺序表和链表的比较对于按序号杳找顺序表支持随机访问， 时间复杂度仅为0(1)链表的平均时间复杂度为O ( n )顺序表： 平均需要移动半个表长的元素链 表 : 只需修改相关结点的指针域者空间满则无法进行扩充会出现内存溢出n插入、删除操作静态分配 存6T 动态分配 对空间进行扩充的时候需要进行数据移动， 效率低下空间分配连式存储空间分配非常灵活J选取存储结构基于运算的考虑基于环境的考虑难以估计线性表的长度或存储规模时， 不宜采用顺序表链表不用事先估计存储规模， 但链表的存储密度较低按序号访问数据元素 顺序表优于链表进行插入、删除等操作 链表优于顺序表顺序表基于数组更容易实理链表基于指针， 在某些编程语言中不适合实现只允许在一端进行插入或删除操作的线性表 先进后出栈 顶 (Top ): 线性表允许进行插入删除的那一端结构 (--------- 1我 底 (Bottom ) :固定的， 不允许进行插入和删除的另一端栈的基本概念卡特兰数 n个不同元素进栈, 出栈元素不同排列的个数为栈的基本操作InitStack (&S):初始化一个空栈SStackEmpty (S):判断一个栈是否为空， 若栈S为空则返回true.否则返回false。

Push (&S x):进栈， 若栈S未满， 则将x加入使之成为新栈顶Pop (&S , &x):出栈， 若栈S非空则弹出栈顶元素， 并用x返回GetTop(S , & x):读栈顶元素, 若栈S非 空 , 则用x返回栈顶元素在解答算法题时, 若题干未做出限制, 则可直接使用这些基本的操作函数DestroyStack (&S):销毁栈， 并释放栈S占用的存储空间( " & ” 表示引用调用)采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素， 同时附设一个指针(top)指示当前栈顶元素的位置顺序栈的实现基本结构与操作栈顶指针:S.top,初始时设置S.top=-1栈顶元素:S.data[S.top]进栈操作: 栈不满时， 栈顶指针先加L再送值到栈顶元素出栈操作: 栈非空时， 先取栈顶元素值， 再将松顶指针减1栈空条件:S.top==-1栈满条件:S.top==MaxSize-l;栈长:S.top+1初始化void InitStack(SqStack 4S ){S .t o p - 1; 〃初始化栈顶指针3.1栈判栈空bool StackErapty(SqStack S)(if (S .to p --1)return true;«lsoretucn false;〃栈空〃不空bool Puah(SqSt4ck fcS,EleniType x) {栈的顺序存储结构顺序栈的基本操作进栈i£ (S.top-MaxSixe-l>return false；S.data(**S.top]-x;return true;〃枝濡.〃指计先加1 .再入校bool PoptSqStack &S,ElemType &x))出栈if return false;xaS.data(S.top);return true;〃枝空，报播Z /x记录枝JI元素让两个顺序栈共享一个一维数组空间， 将两个栈的栈底分别设置在共享空间的两端， 两个栈顶向共享空间的中间延伸共享栈基本原则两个栈的栈顶指针都指向栈顶元素,topO=-l时。

号栈为空,topl = MaxSize时1号栈为空当两个栈顶指针相邻(topl-topO=l)时， 判断为栈;1当 号栈进栈时topO先加1再赋值,1号栈进栈时topi先减1再赋值; 出栈时则刚好相反存取数据的时间复杂度均为0(1)采用单链表实现， 并规定所有操作都是在单链表的表头进行栈的链式存储结构优点便于多个栈共享存储空间和提高其效率且不存在栈满上溢的情况是一种操作受限的线性表， 只允许在表的一端进行插入 产在表的另一端进行删除向队列中插入元素称为入队或进队； 删除元素称为出队或离队3 . 2队列( 上 )队列的定义 先进先出队头(Front) :允许删除的一端， 又称队首结构队尾(Rear):允许插入的一端空队列： 不含任何元素的空表厂队列的基本概念InitQueue (&Q)初始化队列， 构造一个空队列Q队列基本操作QueueEmpty (Q):判队列空， 若队列Q为空返回true.否则返回falseEnQueue (&Q , x):入 队 ， 若队列Q未 满 ， 将x加 入 ， 使之成为新的队尾DeQueue (&Q , & x):出 队 ， 若队列Q非 空 , 删除队头元素， 并用x返回GetHead(Q z & x):读队头元素，若队列Q非 空，则将队头元素赋值给X分配一块连续的存储单元存放队列中的元素， 并附设两个指针队列的顺序存储队头指针front指向队头元素， 队尾指针rear指向队尾元素的下一个位置( 具体问题具体分析)初始状态( 队空条件)：Q.front==Q.rear==0基本操作 进队操作: 队不满时， 先送值到队尾元素， 再将队尾指针加1出队操作: 队不空时， 先取队头元素值， 再将队头指针加1假溢出 这种溢出并不是真正的溢出， 在data数组中依然存在可以存放元素的空位置J队列的顺序存储结构把存储队列元素的表从逻辑上视为一个环， 称为循环队列初始时:Qfront=Q.rear=0循环队列基本操作队首指针进l：Q.front= ( Q.front+1) %MaxSize队尾指针进 l：Q.rear=(Q.rear+l)%MaxSize队列长度(Qrear+MaxSize-Q.front)%MaxSize.队 空：Q.front==Q.rear判断条件牺牲一个单元来区分队空和队满， 即" 队头指针在队尾指针的下一位置作为队满的标志"队满条件：(Q.rear+l)%MaxSize= =Q.front队空条件:Q.front= =Q.rear队列中元素的个数： (Q.rear-Q.front+ MaxSize ) %MaxSize队满队 空 ： 为Q.size==0类型中增设表示元素个数的数据成员。

——- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 队 满 ：Q.size= = MaxSize类型中增设tag数据成员， 以区分是队满还是队空tag等于0时, 若因删除导致Q.front==Q.rear,则为队空tag等于1时, 若因插入导致Q.front==Q.rear■， 则为队满队列的链式表示称为链队列， 是一个同时带有队头指针和队尾指针的单链表队列的链式存储r-队列的链式存储结构头指针指向队头结点尾指针指向队尾结点当Qfront= = N U LL且Q.rear= = NU LL时, 链式队列为空3.2队列（ 下 ）适合于数据元素变动比较大的情形不存在队列满且产生溢出的问题双端队列双端队列是指允许两端都可以进行入队和出队操作的队列概述 逻辑结构仍是线性结构一将队列的两端分别称为前端和后端， 两端都可以入队和出队八 * 输出受限的双端队列： 允许在一端进行插入和删除， 但在另一端只允许插入的双端队列7 3类- - - - - - - 输入受限的双端队列： 允许在一端进行插入和删除， 但在另一端只允许删除的双端队列括号匹配①碑定中级表达式中各个运算符的运算顺序表达式求值中级衷达式转后缀裳达式（ 手 算 ）后缀表达式的计算栈的应用3.3~4矩阵的压缩存储（ 上 ）递归旦选择下一个运算符， 按 照 「 左操作数右瘵作数运算符」的方式组合成一个新的撵作数③如果还有运算符没被处理， 就继续②从左往右扫描，每遇至IJ一个运舞符，就让运算符前面最近的两个手算 操作数执行对应运算， 合体为一个操作数机算①从左往右扫描下一个元素， 直到处理完所有元素②若扫描到操作数则压入栈， 并回到①； 否则执行③③若扫描到运算符， 则弹出两个栈顶元素， 执行相应运算, 运监结果压回栈顶， 回到①①确定中缀表达式中各个运算符的运算顺序中缀表达式转前缀表达式（ 手 算 ）前度表达式的计璋②选择下一个运算符， 按 照f运算符左操作数右操作数J的方式组合成一个新的操作数③如果还有运算符没被处理， 就继续②? 从右往左扫描下一个元素, 直到处理完所有元素②若扫描到操作数则压入栈， 并回到①； 否则执行③③若扫描到运算符，则弹出两个钱顶元素， 执行相应运算, 运算结果压回饯顶， 回到①中缀表达式转后缀表达式手算机算中塘表达式的计算（ 用栈实现）计算正整数的阶乘n !①确定中掇表达式中各个运箕符的运箕顺序②选择下一个运算符， 按 照 「 左操作数右操作数运算符」的方式组合成一个新的操作数③如果还有运算符没被处理， 就继续②" 左 优 先 " 原 则 ： 只要左边的运算符能先计算， 就优先算左边的从左到右处理各个元索, 直到末尾。

可能谓到三种情况:⑥遇到操作数. 直接加入后缀表达式.旦 遇到界限符遇 到3二直接入栈； 遇 到T则依次弹出栈内运算符并加入后墩裳达式， 直 到 弹 出 " （ "为止注意: 二二不加入后缀裳达式.③遇到运算符依次弹出栈中优先级高于或等于当前运算符的所有运算符， 并加入后缀表达式， 若 碰 到 或 栈 空 则 停 止 之后再把当前运算符入栈初始化两个栈， 操作数栈和运算符栈若扫描到操作数， 压入操作数栈若扫描到运算符或界限符， 则按照" 中缝转后缀" 相同的逻辑压入运算符栈（ 期间也会弹出运, 符， 每当弹出一个运算符时， 就需要再弹出两个操作数栈的栈顶元素并执行相应运算， 运算结果再压回操作数栈）递归调用时，函数调用栈可称为" 递归工作钱"每迸入一层递归， 就将递归调用所需信息压入栈顶每退出一层递归， 就从栈顶弹出相应信息缺 点 ： 太多层递归可能会导致栈溢出求斐波那契数列队列在计算机系统中的应用解决主机与外部设备之间速度不匹配的问题 利用队列先进先出的性质， 实现对打印机与主机速度不匹配的协调功能解决由多用户引起的资源竞争问题 将多个用户排成一个队列， 然后利用先进先出的性质分别将C P U分配给不同的用户使用图的广度优先遍历数组的定义概述数组是由n个相同类型的数据元素构成的有限序列每个数据元素称为一个数组元素每 个元素在n个线性关系中的序号称为该元素的下标， 下标的取值范围称为数组的维界 下标从0开始计数特殊矩阵的压缩存储数组是线性表的推广数 组 与 线 性 表 的 关 系 | - - - - - - - - - - - - - - - - - - - - - - - ---------------1 一 维 数 组 可 视 为 一 个 线 性 表 ； 二维数组可视为其元素也是定长线性表的线性表特点 数 组 一 旦 被 定 义 ， 其维数和维界就不再改变一个数组的所有元素在内存中占用一段连续的存储空间数组的存储结构按行优先按照一行一行的存储多维数组 映射方法二维数组公式 L O C (% )= LOC(%o) + p x g + 1 )+小 心按列优先按照一列一列的存储考试的时候可以根据具体问题现场推演二维数组公式 L O C(«u)eLOC(^><1)+ [/x (^ + l) + f]x£3.3~4矩阵的压缩存储（ 下 ）—2 指 为 多 个 值 相 同 的 元 素 只 分 配 一 个 存 悌 空 间，对零元素不分配存储空间压 缩 存 储•- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - —— - - - - - - - - -- - - - - - - - - - - -1目的是为了节省存储空间指 具 有 许 多 相 同 矩 阵 元 素 或 零 元 素 ， 并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵概述特殊矩阵对称矩阵常见的特殊矩阵上 （ 下 ）三角矩阵对角矩阵特 殊 矩 阵 的 压 缩 存 储 方 法 ： 找出特殊矩阵中值相同 的 矩 阵 元 素 的 分 布 规 律 ， 把 那 些 呈 现 规 律 性 分 布 的 、值相同的多个矩阵元素压缩存情到一个存储空间中概念关于左对角线对称的矩阵上 三 角 区 ： 位于对角线上方的区域下 三 角 区 ： 位于对角线下方的区域对称矩阵7-1. / 之/ （ 下三角区和主对角线元素）记不住公式的话记住推导过程, 考试的时候可以直接带入试试矩阵的压缩存储计算公式上三角区的所有元素均为同一常量♦ i-i, / 区元的〃 =*存储完下三角区和主对角线上的元素之后， 紧接着存储对角线上方的常量一次下三角矩阵元素下标之间的对应关系« ” +1)三 角矩阵下三角矩阵在内存中的压缩存储形式下三角区的所有元素均为同一常量,2 ）（ 下三角区和主对角畿元素）上三角区元素）%] [明I | "A "U I "A J …(心1 I /■> I iI G第I行 事2行 第3行特殊矩阵只需存储主对角线、上三角区上的元素和下三角区的常量一次（ i-»X2w-M2）4 a_，K 上三角区和主对角段元素）上三角矩阵元索下标之间的对应关系下三角区元素）" [ … | 也 [ 也 ] 卬 ！… [ 七 ]… [ Oy ] C I上三角矩阵在内存中的压缩存储形式 后行 姮打 一 而 奇 高 》三对角矩阵又 称 为 带 状 矩 阵 ， 以角线为中心的3条 对 角 线 的 区 域 ， 其他区域的元素都为零三对角矩阵A也可以采用压缩存储， 将3条对角线上的元素按行优先方式存放在一维数组B中， 且a,存 放 于BQ]中在一维数组B中存放的下标为k=2i+j-3矩阵中非零元素的个数t,相对定阵元素的个数S来说非常少， 即S>>t的矩阵称为稀疏矩阵存储方式 三元组 将非零元索及其相应的行和列构成一个三元组（ 行 标 ， 列 标 ， 值 ）稀疏矩阵注 意 ： 稀疏矩阵压缩存储后便失去了随机存取特性稀疏矩阵的三元组既可以采用数组存储， 也可以采用十字链表法存储串是由零个或多个字符组成的有限序列串中任意个连续的字符组成的子序列称为该串的子串， 包含子串的串相应地称为主串基本概述子串在主串中的位置以子串的第一个字符在主串中的位置来表示当两个串的长度相等且每个对应位置的字符都相等时， 称这两个串是相等的由一个或多个空格( 空格是特殊字符) 组成的串称为空格串 其长度为串中空格字符的个数4.1串的定义和实现类似于线性表的顺序存储结构， 用一组地址连续的存储单元存储串值的字符序列截 断 ： 串的实际长度只能小于等于MAXLEN,超过预定义长度的串值会被舍去定长顺序存储表示»士 一、4 L用一个额外的变量来存放串的长度串 表 示 方 法।- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -弊端「2. 串 值后 甄 个不计入串长的结束标记字符" 、 入， 此时的串长为隐含值串值序列的长度超过上界， 约定用截断法处理解决方法 用不限定串长的最大长度， 即采用动态分配的方式一 串的存储结构堆分配存储表示 堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列， 但它们的存储空间是在程序执行过程中动态分配得到的每个结点既可以存放一个字符， 也可以存放多个字符。

每个结点称为块， 整个链表称为块链结构块链存储表示headTA|B|C|D| ZE|F|G|H|<•) M点大小为， 的情表head_H4! c 1 - H T “ ♦H意图 _________________________________ T厕返回值>0;若s=T,则返回值:0;若s

将S清为空串DestroyString(&S ): 销毁串将串S销毁英 文 字 符 一ASCII字符集字符集编码 中英文- - - -Unicode字符集4.2串的模式匹配子串的定位操作通常称为串的模式匹配， 它求的是子串( 常称模式串) 在主串中的位置实 现 思 想 「将主串中与模式串长度相同的子串搞出来， 挨个与模式串对比当子串与模式串某个对应字符不匹配时， 就立即放弃当前子串， 转而检索下一个子串简单的模式匹配算法缺 点 ： 主串指针会出现回溯现象导致时间开销增加最坏时间复杂度：O(mm ) ， 其中n和m分别为主串和彳英式串的长度字符串的前缀、后缀和部分匹配值next数 组 ： 当模式串的第j个字符匹配失败时， 令模式串跳到next(j]再继续匹配获取串的匹配值 ‘ababa'为例'a'的前缀和后缀都为空集， 最长相等前后缀长度为0'ab'的前缀为｛ a),后缀为(b｝ ,(a｝ n ( b｝ =0,最长相等前后缀长度为0'aba'的前缀为｛ a,ab｝后缀为｛ a,ba), ( a,ab ) n(a,ba ) =｛ a )， 最长相等前后缀长度为1’abab的刖缀｛ a,ab,aba ) n后缀｛ b,ab,bab)-(ab )， 最长相等刖后缀长度为2改进的模式匹配算法一 KMP算法当子串和模式串不匹配时， 主串指针'ababa'的前缀｛ a,ab,aba,abab)门后缀｛ a,ba,aba,baba｝ =｛ a,aba｝ ,公共元素有两个， 最长相等前后缀长度为3故字符串'ababa'的部分匹配值为00123i不回溯， 模式串指针j=next[j]时间复杂度： 。

m+n )优 点 ： 主串不会进行回溯KM P算法的进一步优化KMP算法优化： 当子串和模式串不匹配时j = nextval[j] 通过构造nextval函数树是n （ n之0 ） 个节点的有限集当n=0时， 称为空树树的定义有且仅有一个特定的称为根的结点在任意一棵非空树中应满足f-------------------------------------------------------------------------------------------- 1 当n＞l时， 其余节点可分为m （ m＞ 0 ） 个互不相交的有限集T1,T2….Tm,其中每个集合本身又是一棵树， 并且称为根的子树树是一种逻辑结构， 也是一种分层结构树的根结点没有前驱， 除根结点外的所有结点有且只有一个前驱树中所有结点可以有零个或多个后继示意图5」树的基本概念K的祖先: 根A到结点K的唯一路径上的任意结点q人 . 子 孙 ： 结点B是结点K的祖先， 而结点K是结点B的子孙考虑件点K _____________________________________________S”双亲与孩子： 路径上最接近结点K的结点E称为K的双亲, 而K为结点E的孩子兄 弟 ： 有相同双亲的结点称为兄弟， 如结点K和结点L有相同的双亲E,即K和L为兄弟结点的度： 何中一个结点的孩子个数， 树中结点的最大度数称为树的度分支结点： 度大于0的结点基本术语叶子结点（ 又称终端结点）: 度为0 （ 没有子女结点） 的结点结点的层次： 从何根开始定义， 根结点为第1层 ， 它的子结点为第2层 , 以此类推结点的深度： 从根结点开始自顶向下逐层累加的结点的高度： 从叶结点开始自底向上逐层累加的树的高度（ 或深度）： 树中结点的最大层数有序树和无序树： 树中结点的各子树从左到右是有次序的， 不能互换， 称该树为有序树， 否则称为无序树路径和路径长度： 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的， 而路径长度是路径上所经过的边的个数森 林 ： 森林是n棵互不相交的树的集合只要把树的根结点删去就成了森林给农棵独立的树加上一个结点， 并把这m棵树作为该结点的子树， 则森林就变成了树树中的结点数等于所有结点的度婺”度为m的树中第i层上至多有 /T 个结点（i大于等于1）高度为h的m叉树至少有h 个结点.高度为h的m叉树至多有 （ 机“ - 1） /（ 加 - 1） 个结点高度为h、度为m的树至少有h+m -1个结点树的性质-具有n个结点的m叉树的最小高度为 '「 1 。

6n（ " 5 7） +1） ］任意结点的度＜ m （ 最多m个孩子）m叉树——每个结点最多只能有m个孩子的树允许所有结点的度都＜ m可以是空树任意结点的度＜ m （ 最多m个孩子）度为m的树至少有一个结点度=m （ 有m个孩子）一定是非空树， 至少有m + 1个结点5.2二叉树的概念二叉树的定义： 二叉树是另一种树形结构， 其特点是每个结点至多只有两棵子树， 并且二叉树的子树有左右之分， 其次序不能任意颠倒度为2的树至少有3个结点， 而二叉树可以为空二叉树与度为2的有序的的区别孩子结点度为2的有序树的孩子的左右次序是相对于另一孩子而言的， 若某个结点只有一个孩子, 则这个孩子就无须区分其左右次序二叉树无论其孩子数是否为Z均需确定其左右次序一棵高度为h,且含有 2A- 1 个结点的二叉树称为满二叉树满二叉树特殊的二叉树完全二叉树二叉排序树「 _ 叉树的定义及其主要特性双 亲 为1诅 」对于编号为i的结点 若有左孩子， 则左孩子为2i若有右孩子， 则右孩子为2i + l高度为h、有n个结点的二叉树， 当且仅当其每个结点都与高度为h的满二叉树中编号为1 ~ n的结点一对应时， 称为完全二叉树i - L〃/2」 则结点为分支结点， 否则为叶子结点叶子结点只可能在层次最大的两层上出现. 对于最大层次中的叶子结点， 都依次排列在该层最左边的位置上_上 若有度为1的结点， 则只可能有一个， 且该结点只有左孩子而无右孩子（ 重要特征）- - - -J 按层序编号后， 一旦出现某结点（ 编号为i）为叶子结点或只有左孩子， 则编号大于i的结点均为叶子结点若n为奇数， 则每个分支结点都有左孩子和右孩子若n为偶数， 则编号最大的分支结点（编号为n/2 ）只有左孩子， 没有右孩子， 其余分支结点左、右孩子都有左子树上所有结点的关键字均小于根结点的关键字; 右子树上的所有结点的关键字均大于根结点的关键字; 左子树和右子树又各是一棵二叉排序树二叉树的性质平衡二叉树： 树上任一结点的左子树和右子树的深度之差不超过1非空二叉树上的叶子结点数等于度为2的结点数加1非空二叉树上第k层上至多 2" 个结点高度为h的二叉树至多有 2人- 1 个结点对完全二叉树按从上到下、从左到右的顺序依次编号L2， … , n,则有以下关系当i>l时， 结点i的双亲的编号为 L办 」 即当i为偶数时， 其双亲的编号为i/2它是双亲的左孩子; 当i为奇数时， 其双亲的编号为（ i-l） /2,它是双亲的右孩子2小结点i的左孩子编号为2i,否则无左孩子_ 2 i + l < n 结点i的右孩子编号为2i+ 1,否则无右孩子结点7所在层次（ 深度） 为Uog2〃+ 1具有n个 （n>0 ）结点的完全二叉树的高度为「1。

改S + 1 ） 1或Uog2〃 」 + 1用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素， 即将完全二叉树上编号为i的结点元素存储在一维数组下标为i - 1的分量中顺序存储结构 完全二叉树和满二叉树采用顺序存储比较合适一一般的二叉树， 为了能反映二叉树中结点之间的逻辑关系， 只能添加并不存在的空结点， 让其每个结点与完全二叉树上的结点相对照， 再存储到一维数组的相应分量中I 二叉树的存储结构由于顺序存储的空间利用率较低， 因此二叉树一般都采用链式存储结构， 用链表结点来存储二叉树中的每个结点链式存储结构typedef struct BlTNodetElenType data;struct BITNode *lch lld , •rchlld; / / 左. 右篌子18升结 构 描 述｝ BlTNod», ,BlTree;在含有n个结点的二叉链表中， 含有n + 1个空链域5.3二叉树的遍历和线索二叉树访问根结点先序遍历访问t眸 点先序遍历左子树先序遍历右子树中序遍历左子捕二叉树的遍历中序遍历访问根结点 - 时 间 复 杂 度 （n ）中序遍历右子树后序遍历后序遍历左子树后序遍历右子树递归算法和非递归算法的转换： 利用栈进行实现利用队列实现层次遍历先将二叉棚板结点入队， 然 后 出 队 ， 访问出队结点若它有左子树， 则将左子树根结点入队若它有右子树， 则暨右子树根结点入队然后出队， 访问出队结点……如此反复， 直至队列为空二叉树的先序（ 后 序 ） 序列和中序序列可以唯一地确定一棵二叉- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 树由遍历序列构造二叉树1层序遍历与中序（ 后 序 ） 可以确定一颗二叉树" "基本概念“上 +则人 遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列， 从而得到几种遍历序列线索二叉树的基本概念| - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -----------------------------1使得该序列中的每个结点（ 第一个和最后一个结点除外） 都有一个直接前驱和直接后继若无左子树， 令Ichild指向其前驱结点规 定i----------------------------------------------------------------1若无右子树， 令rchild指向其后继结点件点件构 | 1chlId | lug | das | - 9 | eh£Ld |标志域的含义I 0 Jchild域指示结点的左孩子wT 1 Ichild域指示结点的前驱侬9 ， rchild域指示结点的右孩子----------[1 rchild域指示结点的后继一线索二叉树中序线索二叉树的构造皿入 二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索椒令 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _而前驱或后继的信息只有在遍历时才能得到， 因此线索化的实质就是遍历一次二叉树附设指针pre指向刚刚访问过的结点， 指针p指向正在访问的结点， 即pre指向p的前驱史? 竺三四期楚工检查p的左指针是否为空若为空就将它指向pre在中序遍历的过程中।- - - - - - - - - - - - - - - - - - -------------------------------1检查pre的右指针是否为空， 若为空就将它指向p中序线索二叉树的遍历 若其右标志为T ,则右键为线索， 指示其后继， 否则遍历右子树中第一个访问的结点（ 右子树中最左下的结点） 为其后继先序序列为ABCDF,然后依次判断每个结点的左右链域， 如果为空则将其改造为线索一 人 工 ， 结点A“ B均有左右孩子; 结点C无左孩子， 将左链域指向前驱B,无右孩子， 将右链域指向后继D先序线索二叉树 - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - -结点D无左孩子， 将左链域指向前驱C,无右孩子， 将右链域指向后继F结点F无左孩子， 将左链域指向前驱D,无右孩子, 也无后继故右空后序序列为CDBFA,结点C无左孩子， 也无前驱故皆空， 无右孩子， 将右键域指向后继D后序线索二叉树 结点D无左孩子， 将左链域指向前驱G无右孩子， 将右链域指向后继——B结点F无左孩子， 将左链域指向前驱B,无右孩子， 将右链域指向后继A5滴采用一组连续空间来存储每个结点， 同时在每个结点中增设一个伪指针，瘠示我双亲结点在数组中的位置双亲表示法根结点下标为0 ,其伪指针域为-1优点 利用了 每 个 结 点 ( 根 结 点 除 外 ) 只有唯一双亲的性质， 可以很快得到每个结点的双亲结点缺点 但求结点的孩子时需要遍历整个结构树的存储结构将每个结点的孩子给点都用单链表链接起来形成一个线性结构， 此时n个结点就此n个 孩 子 链 表 ( 叶子结点的孩子链表为空表)孩子表示法 优点 寻找于女的操作非常直落~ ~缺点 寻找双亲的操作需要遍历n个结点中孩于链表指针域所指向的n个孩子链表以二叉链表作为树的存储结构, 孩子兄弟表示法使每个结点包括三部分内容站点值、指向结点第一个孩子结点的指呼指向结点下一个兄弟结点的指针孩子兄弟表示法 优点 这种存储表示法比较灵活, 其一大的优点是可以方便地实现树转换为二叉树的操作， 易 于 直 找 结 点 的 孩 子 等" I 一 心 Q 人 任qgvx 入 4 八 占 上 片 上 △ 八£上-----------r---—— 卜若为每个结点增设一个p aren t域指向其父结点， 则查找结点的父结点也很方便缺点 从当前结点查找其双亲结点比较麻烦 J树、森林与二叉树的转换5.4树、森林树转换为二叉树的规则 每个结点左指针指向它的第一个孩子， 右指针指向它在闲中的相邻右兄弟在兄弟结点之间加一连线树转换成二叉树的画法 对 每 个 结 点 ， 只保留它与第一个孩子的连线, 而与其他孩子的连线全部抹掉以树根为轴心， 顺时针旋转4 5度格森林中的每棵树转换成相应的二叉树森林转换成二叉树的画法 每棵树的根也可视为兄弟关系， 在每棵树的根之间加一根连线以第一棵树的根为轴心顺时针旋转4 5 °若二叉树非空， 则二叉♦的根及其左子柳为第一棵树的二叉树形式， 故将根的右链断开二叉树转换为森林的规则 二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树一应用同样的方法. 直到最后只剩一棵没有右子树的二叉树为止展后再将每棵二叉树依次转换成树， 就得到了原森林森林与二叉树的对应关系树和森林的遍历若捌非空, 先访问根结点， 再依次遍历根结点的每棵子树， 遍历子树时仍遵循先根后子树的规则先 根 遍 历f- - - - - - - - - - -- - - - - - - - - - - - 其遍历序列”即 阚 二 叉 研 理 生 到 哽-ge 若捌非空. 先依次遍历根结点的每棵子树, 再访问根结点， 遍历子树时仍遵循先子树后根的规则后 根 遍 历f- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - 其遍历序列与这曝树相应二叉树的中序序列里同访问森林中第一棵树的根结点先序遍历森林 先序遍历第一裸树中根结点的子树森林先序遍历除去第一棵用之后剌余的树构成的. 森林中序遍历森林中第一棵树的根结点的子何森林中序遍历森林 访问第一裸树的根结点中序遍历除去第一裸树之后剩余的树构成的森林树和森林的遍历与二叉树遍历的对应关系树森林二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历1 ) U n i on ( S , R oot L R oot 2 )把 集 合S中的子集合R oot 2并入子集合R。

”,要求R oot l和R oot 2互不相交， 否则不执行合并支持操作 2 ) F i n d ( S , x ) :百找集合S中单元索x所在的子集合， 并返回该子里合的名字3 ) I n i t i a l ： ) :将集合S中的每个元素都初始化为只有一个元素的子中合树的应用——并查集 用树( 森林) 的双亲表示作为并一集的存储结构， 每个子集合以一棵树表示具体实现 所有表示子集合的树， 构成表示全集合的森林， 存放在双亲表示数组内通常用数组元素的下标代表元素名， 用根结点的下标代表子集合名， 根结点的双亲结点为负数5滴1） 若左子树非空， 则左子树上所有结点的值均小于根结点的值二叉排序树的定义 特性 [ 2 ）若右子树非空， 则右子树上所有结点的值均大于根结点的值 - 左子树结点值C根结点值＜ 右子树结点值- 3） 左、右子树也分别是一棵二叉排序树二叉排序树的查找是从根结点开始， 沿某个分支逐层向下比较的过 至 坦 蛰 蟹 走 眄二叉排序树的查找 程 ， 若二叉排序树非空, 先将给定值与根结点的关键字比较 若不等， 如果小于根结点的关犍字, 则在根结点的左子树上查找 -递归否则在根结点的右子树上查找5.5树与二叉树的应用（ 上 ）二叉排停树的插入二叉排序树（ BST ）.插入结点的过程若原二叉排序树为空， 则直接插入结点若关键字k小于根结点值， 则插入到左子树若关键字k大于根结点值， 则插入到右子树插入的结点一定是一个新添加的叶结点, 且是查找失败时的查找路径上访问的最后一介结点的左孩子或右孩子设查找的关键字再列为{45,24,53,45,12,24},则生成的二叉排序树若被删除结点z是叶结包啰皂接删除， 不会破坏三》排序飒的性质二 叉 排 序 树 的 删 除 「 若结点z只有一棵左子树或茄树， 则让z的子树成为z父结点的子树， 替代z的位置若结点z有左、右两棵子树， 则令z的直接后继（ 或直接前驱） 替代乙然后从二叉排序树中删去这个直接后继（ 或直接前驱） ， 这样就转换成了第一或第二种情况二叉排序树的查找效率分析 平均执行时间为T心 在 插 入 和 删 除 二 叉 树 结 点 时 ， 要保证任意结点的左、右子树高度差的绝对值不超过L将这样的二叉树称为平衡二叉树平糊二叉树的定义 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - : 平衡因子: 左子树与右子树的高度差为该结点的平衡因子 平衡因子的值只可能是- L。

或1首先检gf具插入路径上的结点是否因为此次操作而导致了不平衡当在二叉排序树中插入（ 或删除） 一个结点时若源致了不平街二J先找到运人路包上高注入结点展近的空衡因子的度对值大于1的结点A， 再对以A为根的子树，在保持二叉排序例特性的前提下， 调整各结点的位置关系， 使之重新达到平衡平衡二叉树的插入5.5树与二叉树的应用（ 中 ）平衡二叉树R L平衡旋转（ 先右后左双旋转）由于在A的右孩子（ R ）的左子树（ L ） 上届入新结点孑A的平衡因子由-1激至-2,导致以A为根的子硝失去平衡， 需要进行两次旋转操作， 先右旋转后左旋转}M H-1< > > ・入 taaat 2 ・入 串H平衡二叉树的直找 平均直找长度5滴哈夫曼树的定义称为哈夫灵树, 也称最优二叉树： 在含有n个带权叶结点的二叉树中， 其中带权路径长度（W P L ）最小的二叉树结点的带权路径长度： 从树的根到任谶结点的路径长度（ 经过的边数） 与该结点上权值的乘积基本概念WPL = XwZ/= !树中所有叶结点的带权路径长度之和称为该树的带权路径长度每次从合成后存在的结点中选出两个最小的进行构造二叉树是第i个叶结点所带的权值是该叶结点至懈结点的路径长度5 . 5树与二叉树的应用（ 下）哈夫曼树的构造哈夫曼树和哈夫曼编码示意图固定长度编码： 在数据通信中， 若对每个字符用相等长度的二迸制位表示基本概念可变长度编码允许对不同字符用不等长的二进制位表示特点 对频率高的字符赋以短编码， 而对频率较低的字符则赋以较长一些的编码-H 可以使字符的平均编码长度减短， 起到压缩数据的效果可变长度编码比固定长度编码要好前缀编码没有一个编码是另一个编码的前皴哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码哈夫曼编码将每个出现的字符当作一个独立的结点, 当权值为它出现的点度： 或次数—老电座町哈夫曼物构造哈夫曼编码 将字符的编码解释为从根至该字符的路径上边标记的序列其中边标记为。

表示. 转向左孩子” ， 标记为1表示“ 转向右孩子’各字 甲B码 为2b:IOIcioodrille.HOIf JIMc:l2b:l3c:96.1图的基本概念图的定义图G由顶点集V和边集E组成， 记为G =(V,E )， 其 中V(G )表示图G中顶点的有限非空集;E ( G ) 表示图G中顶点之间的关系( 边) 集合/N{ M ， V2/一， ％}则用M表示图G中顶点的个数也称图G的阶 £ ・{( " / ) | “ €匕丫€” 用旧表示图G中边的条数注意: 线性表可以是空表, 树可以是空树， 但图不可以是空图图的一些基本概念及术语若E是有向边( 也称弧) 的有限集合时， 则图G为有向图.-------- 1弧是顶点的有序对， 记为,其中v,w是顶点,v称为弧尾,w称为弧头,称为从顶点v到顶点w的弧， 也称v邻接到w,或w邻接自v若E是无向边( 简舜理2的有限集合时， 则图G为走向图无 向 图 ［边是顶点的无序对， 记为(v,,w)或(w,v )， 因为(％w ) =(w,v )， 其中v,w是顶点可以说顶点W和顶点v互为邻接点边(v,w )依附于顶点w和％或者说边(v,w)和顶点y,w相关联e ke 不存在重复边简 单 图 ,- - - - - - - - - - - - - - -—不存在顶点到自身的边， 则称图G为简单图多重图 若图G中某两个结点之间的边数多于一条, 又允许顶点通过同一条边和自己关联， 则G为多重图人 一… 一人 对于无向图, 旧的取值范围是0到n(n-l)/2,有n ( n-l)2条边的无向图称为完全图， 在完全图中任意两个顶点之间都存在边1对于有向图, 旧的取值范围是。

到n(n-l)， 有n(n-l)条弧的有向图称为有向完全图， 在有向完全图中任意两个顶点之间都存在方向相反的两条弧子图 设有两个图G = (V,E )和G '=(V;E '),若V. 是V的子集， 且E. 是E的子集， 则称G. 是G的子图. 若有满足V(G ')=V(G )的子图G ：则称其为G的生成子图在无向图中， 若从顶点v到顶点w有路径存在， 则称v W w是连通的* 、 ” 、e *八= 若图G中任意两个顶点都是连通的， 则称图G为连通图， 否则称为非连通图连通、连通图和连通分量 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - -无向图中的极大连通子图称为连通分量若一个图有n个顶点， 并且边数小于n-L则此图必是非连通图- … 八0 强连通图： 在有向图中， 若从顶点v到顶点w和从顶点w到顶点v之间都有路径， 则称这两个顶点是强连通的若图中任何一对顶点都是强连通的， 则称此图为强连通强连通图、强 连 通 分 量 ；- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -----------------------1有向图中的极大强连通子图称为有向图的强连通分垣连通图的生成树是包含图中全部顶点的一个极小连通子图…一 若图中顶点数为n,则 它 的 生 成 树 含 有 条 边- - - - - - - - - - - - - - - - - - - 对生成树而言， 若砍去它的一条边， 则会变成非连通图， 若加上一条边则会形成一个回路在非连通图中， 连通分量的生成树构成了非连通图的生成森林度 ： 定义为以该顶点为一个端点的边的数目顶点的度，入度和出度 「 无向图： 顶点v的度是指依附于该顶点的边的条数 无向图的全部顶点的度的和等于边数的2倍有向图： 全部顶点的入度之和与出度之和相等, 并且等于边数边的权和网 每条边都可以标上具有某种含义的数值， 该数值称为该边的权值. 这种边上带有权值的图称为带权图， 也称网稠密图、稀疏图边数很少的图称为稀疏图， 反之称为稠密图般当图G满 足|E |v|Hk)g|H可以将G视为稀疏图路径、路径长度和回路路 径 ： 两个顶点之间相连的边路 径 长 度 : 路 弛 邈 婺 目 里回路或环： 第一个顶点和最后一个顶点相同的路径若一个图有n个顶点， 并且有大于n-1条边， 则此图一定有环简单路径、简 单 回 路 匚蚪 般 径 : 顶点不事匏出现的路径简单回路： 除第一个顶点和最后一个顶点外, 其余顶点不重复出现的回路丁一 从顶点u出发到顶点v的最短路径若存在， 则此路径的长度称为从u到v的距离距离 - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ------- 1若从U到V根本不存在路径， 则记该距离为无穷有向树 一个顶点的入度为0、其余顶点的入度均为1的有向图， 称为有向树是指用一个一维数组存储图中顶点的信息， 用一个二维数组存储图中边的信息（ 即各顶点之间的邻接关系）存储顶点之间邻接关系的二维数组称为邻接矩阵邻接矩阵存储4财 =结构示意1,若 际 ,） 或＜„ ＞ 是顼G冲的边0,若（4 0 ）或＜»中＞不是£（6件的边带权图示意小 叨 =［ 吗, 若（ 3,） 或＞ 是£（ G舛的边|0或8 , 若际V/）或不是E（ G冲的边邻接矩阵法邻接矩阵表示法的空间复杂度为0 （ M） ,其中n为图的顶点数恒|无向图的邻接矩阵一定是一个对称矩阵（ 并且唯一） . 因此, 在实际存储邻接矩阵时只需存储上（ 或 下 ） 三角矩阵的元素特点对于无向图, 邻接矩阵的第i行 （ 或第i列 ） 非零元素（ 或非。

元 素 ） 的个数正好是第i个顶点的度TD（ 同对于有向图, 邻接矩阵的第许亍（或第i列 ） 非零元素（ 或非 元 素）的个数正好是第i个顶点的出度 0D（ V）用邻接矩阵法存储图彳艮容易确定图中任意两个顶点之间是否有边相连. 但是要确定图中有多少条边， 则必须按行、按列对每个元素进行检测， 所花费的时间代价很大稠密图适合使用邻接矩阵的存储八小当一个图为稀跪图时， 使用邻接矩阵法要浪费大量的存储空间， 而图的邻接表法结合了顺序存储和链式存储方法， 减少了不必要的浪赛一 对 图G中的街个顶点建立一个单链表， 第i个单链表中的结点表示依附于顶点vi的边， 这个单链表就称为顶点vi的边表（ 对于有向图则称为出边表）结构 r---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- - - - - - 边表的头指针和顶点的数据信息采用顺序存储（ 称为顶点表） ， 所以在邻接表中存在两种结点: 顶点表结点和边表结点邻接表法示意图三号 更 斗E口4 Z口5 - - 4 4 -1 -4- 2 /若G为无向图, 则所需的存储空间为0 （ |V| + 2|E|） ;若G为有向图, 则所需的存储空间为O|V|+|E|）对于稀筑图， 采用邻接表表示将极大地节省存懂空间特点6.2图的存储及基本操作在邻接表中， 给定一顶点， 能很容易地找出它的所有邻边, 因为只需要读取它的邻接表在有向图的邻接表表示中, 求一个给定顶点的出度只需计算其邻接表中的结点个数但求其顶点的入度则需要遍历全部的邻接表图的邻接衷表示并不唯一十字链表是有向图的一种链式存储结构. 在十字链表中， 对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点时间宦杂度0 （ |V| + |E|）尾 域 （tailvex ）弧尾头 域 （headvex ）: 弧头弧结点域结构链 域 （hlink ）: 指向弧头相同的下一条弧位结点十字链表链 域（tlink）: 指向弧尾相同的下一条弧inf。

域 ： 指向该弧的相关信息tailvex headvex hlink tlink info顶 点-结 点-域 结. 构 「 data域存-放- -顶- -点 相关的数据佶息卜firstin和firstout两个域分别指向以该顶点为建头或建昆的第一个弧结点」顶点站点data firstin firstout只能存有向图邻接多至表是无向图的另一种链式存储结构时间且杂度0 （ |V| + |E|）mark为标志域， 可用以标记该条边是否被搜索过ivex和jvex为该边依附的两个顶点在图中的位置边结构I邻接多重表上ilink指向下一条依附于顶点ivex的边；0 n k指向下一条依附于顶点jyvex的边inf 为指向和边相关的各种信息的指针域顶点结构data域存睹该顶点的相关信息firstedge域指示第一条依附于该顶点的边datafiratedgo类似于二叉树的层序遍历算法广度优先搜索首先访问起始顶点v,接着由V出发， 依次访问v的各个未访问过的邻接顶点Wl,w2… ,wi广度优先搜索(BFS) 算法思想 然后依次访问wLw2“wi的所有未被访问过的邻接顶点再从这些访问过的顶点出发， 访问它们所有未被访问过的邻接顶点, 亶至图中所有顶点都被访问过为止利用队列实现搜索在最坏的情况下, 空间复杂度为0(|V|)BFS算法的性能分析 邻接表存储方式： 顶 点 : O (|V |)边 ： 0 (旧 ) 总 时 间 复 杂 度 ： O(|V| + |E|)时间复杂度- - - - - - - - - - 邻接矩阵存储方式：总时间复杂度：BFS算法可以解决最短路径问题在广度遍历的过程中， 我们可以得到一棵遍历树， 称为广度优先生成树匚度优先生成树 心一 邻接矩阵存储表示是唯一的， 故其广度优先生成树也是唯一的由于邻接表存储表示不唯一， 故其广度优先生成树也是不唯一的深度优先搜索( DFS )类似于树的先序遍历。

搜索策略是尽可能“ 深" 地搜索一个图一 首先访问图中某一起始顶点V,然后由V出发, 访问与v邻接且未被访问的任一顶点w l,再访问与w l邻接且未被访问的任一顶点w2…重复上述过程算 法 思 想f - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- .- - - - - - - - - - - — — .当不能再继续向下访问时， 依次退回到最近被访问的顶点， 若它还有邻接顶点未被访问过， 则从该点开始继续上述搜索过程， 直至图中所有顶点均被访问过为止6.3图的遍历T 深度优先搜索DFS算法的性能分析燮 重 法 _ 需要借助一个递归工作栈空间复杂度为0(|V|)邻接矩阵 时间复杂度时间复杂度邻 接 链 表找所有顶点的邻接点所需的时间为 旧 ) ] r / / / / / »I------------------------------------------------------ -卜总时间复杂度： 。

V + e )1访问顶点所需的时间为0(|V|) J 11 11深度优先的生成树和生成森林对连通图调用DFS才能产生深度优先生成树非连通图产生的是深度优先生成森林} 基于邻接表存储的深度优先生成树是不唯一的基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的注意,基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的图的遍历与图的连通性图的遍历算落可以用来判断图的连通性」 若无向图是连通的， 则从任一结点出发， 仅需一次遍历就能够访问图中的所有顶点对 于 无向 图| - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - --------- 1若无向图是非连通的， 则从某一个顶点出发， 一次遍历只能访问到该顶点所在连通分量的所有顶点， 而对于图中其他连通分量的顶点， 则无法通过这次遍历访问_ 若无向图是连通的， 从初始点到图中的每个顶点都有路径， 则能够访问到图中的所有顶点对于有向图若无向图是非连通的， 不能访问到所有顶点最小生成树人一 一人37_人 心 - - 乂 入 “ I - 若砍去它的一条边， 则会使生成树变成非连通图一个连通图的生成树包含图的所有顶点， 并且只含尽可能少的边।- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -最小生成树： 权值之和最小的刃隈生成树, 则称为最小生成树最小生成树性质最小生成树算法若给它增加一条边， 则会形成图中的一条回路最小生成树不是唯一的， 即最小生成树的树形不唯一其对应的边的权值之和总是唯一的， 而且是最小的最小生成树的边数为顶点数减1P r i m算法概述始时从图中任取一顶点加入何T ,此时树中只含有一个顶点之后选择一个与当前T中顶点集合距离最近的顶点， 并将该顶点和相应的边加入T ,每次操作后T中的顶点数和边数都增1以此类推, 直至图中所有的顶点都并入L得到的T就是最小生成树。

此时T中必然有n - 1条边时 间 复 杂 度 5 因 与适用于求解边稠蜜的图的最小生成树初始时为只有n个顶点而无边的非连通图T ={ V , { } } ,每个顶点自成一个连通分量然后按照边的权值由小到大的顺序， 不断选取当前未被选取过且权值最小的边,概述若该边依附的顶点落在T中不同的连通分量上， 则将此边加入T否则舍弃此边而选择下一条权值最小的边6.4图的应用（ 上）K r u s k a l 算法以此类推， 直至T中所有顶点都在一个连通分量上时 间 复 杂 度5 1 o g | E | ）适合于边稀疏而顶点较多的图辅助数组D i j k s t r a算法求单源最短路径问题实现过程d i s t止记录从源点v O到其他各顶点当前的最短路径长度， 它的初态为:若从v O到v i有弧， 则d i s t [ i ]为弧上的权值;否则置d i s t [ i ]为无穷大p a t h [ ] :p a t h [ i ]表示从源点到顶点i之间的最短路径的前驱结点1） 初始化:集合S初始为{ 0 } , d i s t口的初始值d i s t [ i ] =a r c s ⑼ [ i ] , i =l, 2 ， … , n - 12 ）从顶点集合V - S中选出v j ,满 足"st㈠卜%w V - S ） y j就是当前求得的一条从v O出发的最短路径的终点， 令S =3）修改从V O出发到集合V - S上任一顶点v k可达的最短路径长度:若d i s t U ] + a r c s 3 k ]

因3 ）允许图中有带负权值的边, 但不允许有包含带负权值的边组成的回路适用于带权无向图有 向 无 环 图 ： 若一个有向图中不存在环， 则称为有向无环图， 简称DAG图有 向 无 环 图 描 述 表 达 式 |有向无环图是描述含有公共子式的表达式的有效工具6.4图的应用( 下)若用DAG图表示一个工程， 其顶点表示活动， 用有向边＜ Vi,Vj＞表示活动Vi必须先于活动进行的这样一种关系， 则将这种有向图称为顶点表示活动的网络， 记为AOV网AOV网概述活动Vi是活动Vj的直接前驱， 活动Vj是活动Vi的直接后继这种前驱和后继关系具有传递性, 且任何活动不能以它自己作为自己的前驱或后继拓扑排序定义每个顶点出现且只出现二业| 若顶点A在序列中排在顶点B的刖面， 则在图中不存在从顶点B到顶点A的路径① 从AOV网中选择一个没有前驱的顶点并输出拓扑排序实现方法②从网中删除该顶点和所有以它为起点的有向边— Ha于P徘 序③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止. 后一种情况说明有向图中必然存在环入度为零的顶点, 即没有前驱活动的或前驱活动都已经完成的顶点， 工程可以从这个顶点所代表的活动开始或继续若一个顶点有多个直接后继， 则拓扑排序的结果通常不唯一若各个顶点已经排在一个线性有序的序列中， 每个顶点有唯一的前驱后继关系， 则拓扑排序的结果是唯一的注意生成AOV网的新的邻接存储矩阵， 可以是三角矩阵对于一般的图来说， 若其邻接矩阵是三角矩阵， 则存在拓扑序列; 反之则不一定成立拓扑排序、若图中有环逆拓扑排序序列可能不唯一, 则不存在拓扑排序序列/ 逆拓扑排序序列具体实现 DFS算法逆拓扑排序①从AOV网中选择一个没有后继( 出度为0 )的顶点并输出思想②从网中删除该顶点和所有以它为终点的有向边③重复①和②直到当前的AOV网为空AOE网概述 在带权有向图中，以顶点表示事件， 以有向边表示活动， 以边上的权值表示完成该活动的开销( 如完成活动所需的时间)，称之为用边表示活动的网络关键路径AQE与 AOV ,-------------］ 不同点相同点 AOE网和AOV网都是有向无环图AOE网中的边有权值； 而AOV网中的边无权值. 只有在某顶点所代表的事件发生后, 从该顶点出发的各有向边所代表的活动才能开始AO E网性质 ,- - - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - -只有在进入某顶点的各有向边所代表的活动都已结束时， 该顶点所代表的事件才能发生4 关 键 路 径 ： 从源点到汇点的所有路径中， 具有最大路径长度的路径关 键 路 径 与 关 犍 活 动 | - - - - - -； - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -关 键 活 动 ： 关键路径上的活动事件vk的最早发生事件ve(k)ve( 源点)=0ve(k) = Max{ve(j)+Weight(vj,vk)) },vk为vj的任意后继,Weight (yj,vk)表 示＜ vj,vk＞上的权值变量含义事件vk的最迟发生事件vl(k)vl()DS)= ve ( JDS)vl(k)=Min{vl(j)-Weight(vk，W)},vk 为 0 的任意前驱活动ai的最早开始时间e(i) 该活动弧的起点所表示的事件的最早发生时间. 若边＜ vk,vj＞表示活动ai,则有e ( i ) =ve(k)活动ai的最迟开始时间l(i) 该活动加的终点所表示事件的最迟发生时间与该活动所需时间之差. 若边＜ vk,vj＞表示活动ai,则有l(i)=vl(j)-Weight(vk,vj)一个活动ai的最迟开始时间l(i)和其展早开始时间e(i)的差额d(i)=l ( i)-e(i)关键路径的算法步骤从源点出发， 令ve( 源点)=0,按拓扑有序求其余顶点的最早发生时间ve()从汇点出发， 令vl( 汇点)=ve ( 汇 点 ) ， 按逆拓扑有序求其余顶点的最迟发生时间vl()坐据角顶点的ve()值求所有弧的最早开始时间e ()根据各顶点的vl()值求 ^ 开始时间10求AOE网中所有活动的差额d(),找出所有d()=0的活动构成关键路径关盛路径上的所有活动都是关健活动， 是决定整个工程的关键因素, 因此可通过加快关键活动来缩短整个工程的工期不能任意缩短关槽活动, 因为一旦缩短到一定的程度， 该关犍活动就可能会变成^ 关健活动注意网中的关健路径并不唯一, 只有加快那些包括在所有关犍路径上的关犍活动才能达到缩短工期的目的J M用 加 ， 望整个工程的工期将增长缩短关键活动的时间， 可以缩短整个工程的工期. 关键活动可能会变成非关键活动查 找 ： 在数据集合中寻找满足某种条件的数据元索的过程称为查找7.1查找的基本概念基本概念查 找 表 （ 宜找结构）： 用于查找的数据集合称为查找表， 它由同一类型的数据元素（ 或记录） 组 成 ， 可以是一个数组或链表等数据类型查询某个特定的数据元素是否在妊找表中…士》 检索满足条件的某个特定的数据元素的各种属性查找表操作 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - 在查找表中插入一个数据元索从一找表中删除某个数据元素静态查找表 查找后不会对表进行任何修改动态查找表 直找后对表进行修改关 键 字 ： 数据元素中唯一标识该元素的某个数据项的值， 使用基于关健字的直找， 直找结果应该是唯一的在查找过程中， 一次查找的长度是指需要比较的关键字次数, 而平均查找长度则是所有查找过程中进行"关键字的比较次数的平均值平均查找长度数 学 表 达 式 ASL = £[C ,参数含义n是查找表的长度P是查找第i个数据元素的概率， 一般认为每个数据元素的查找概率相等， 即P=l/nQ是找到第i个数据元素所需进行的比较次数平均查找长度是衡量直找算法效率的最主要的指标又称线性查找， 主要用于性表中进行查找。

顺序蛰找通常分为对一般的无序线性表的顺序查找和对按关键字有序的顺序表的顺序直找基本思想从线性表的一端开始， 逐个检查关键字是否满足给定的条件.若查找到某个元素的关键字满足给定条件， 则直找成功， 返回该元素性表中的位置若已经杳找到表的另一端， 但还没有查找到符合给定条件的元素， 则返回查找失败的信息一股线性表的顺序直找飒平 均 查 找 长 度 ’失败 A S L不成功=«+ 1顺序查找缺点 当n较大时， 平均查找长度较大， 效率低心上 对数据元素的存储没有要求， 顺序存储或链式存储皆可优点 (基本思想对表中记录的有序性也没有要求, 无论记录是否按关键字有序， 均可应用假设表L是按关键字从小到大排列的， 直找的顺序是从前往后, 待查找急的关键字为key当萱找到第i个元素时, 发现第i个元素对应的关键字小于key,但第i+1个元素对应的关键字大于key,这时就可返回查找失败的信息因为第i个元素之后的元素的关犍字均大于key,所以表中不存在关键字为key的元素有序表的顺序查找成功g L 成 功 = £ e(〃- i + l) = ^y^平均直找长度ASL不 成功-1)=失败 / -1 + 2+ - + n + n------------- = —H --------« + 1 ----------2 〃 + 1折半直找又称二分直找，它仅适用于有序的顺序表7.2顺序查找和折半直找基本思想首先将给定值key与表中中间位置的元素比较， 若相等, 则查找成功, 返回该元素的存储位置声不等， 则所需查找的元素只能在中间元素以外的前半部空后半部分然后在缩小的范围内继续进行同样的查找， 如此重复, 直到找到为止或确定表中没有所需要宜我的元素， 则有找不成功, 返回有找失败的信息查找过程中可以生成判定树( 平衡二叉树)折半查找树中每个圆形结点表示一个记录， 结点中的值为该记录的关键字值树中最下面的叶结点都是方形的， 它表示查找不成功的情况平均查找长度成功- i( lx | + 2x2+ -+/ix2*',) = ^ lo 8J(fi+l)-l«logJ(" + l)-l[ h是树的高度， 并且元素个数为哩树高吃 h =Flog2(n + 1)1失败时间复杂度为 0(10g2〃 )仅适合于顺序存储结构， 不适合于链式存储结构， 且要求元素按关健字有序排列又称索引顺序查找， 它吸取了顺序查找和折半查找各自的优点， 既有动态结构， 又适于快速直找基本思想分块查找将有找表分为若干子块块内的元素可以无序， 但块之间是有序的, 第一个块中的最大关键字小于第二个块中的所有记录的关键字， 以此类推再建立一个索引表， 索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址， 索引表按关键字有序排列将长度为n的查找表均匀地分为b块, 每块有s个记录， 在等概率情况下索引查找 L]块内查找的平均查找长度Ls直找成功长度. b + 1 s + 1 s2 + 2s + nASL j + & = -----+-------= --------------在块内和索引表中均采用顺序查找， 则 平 均 查 找 长 度 ( ―若$ = > / 丘则平均查找长度取最小值Vn +1ASL = £ .+ /,= f log2(/> + 1)l +-----W采用折半查找时， 则平均查找长度 2B树及其基本操作7.3B树和B+树概 述 ： 又称多路平衡直找区,B阅中所有结点的孩子个数的最大值称为B树的阶， 通常用m表示树中每个结点至多有m棵子树， 即至多含褥m - 1个关健字若根结点不是终端结点， 则至少有两棵子树 「 ［特点 除根结点外的所有非叶结点至少有 「 加21棵子树， 即 至 少 含 有।加2 I — 1个关键字所有的叶结点都出现在同一层次上， 并且不带信息B树是所有结点的平衡因子均等于。

的多路平衡直找树结点的孩子个数等于该结点中关域字个数加1-H 如果根结点没有关犍字就没有子树， 此 时B树为空推^ 1 4质如果根结点有关键字， 则其子树必然大于等于两棵， 因为子树个数等于关: ：结点中关键字从左到右递增有序， 关键字两快1均有指向子树的指针， 左边指针所指子树的所有关键字均小于该关键字, 右边指针所指子树的所有关键字均大于该关键字年 意 一 棵 更 受n个关键字、高度为h、幽为m的B树B树的高度（ 碳盘存取次数） +点中的关键字个数达到最少， 则容纳同样多关键字的B树的高度达到最大在B一上查找到某个结点后， 先在有序表中进行杳找B的的套找 若找到则查找成功， 否则按照对应的指针信息到所指的于树中去直找直找到叶结点时（ 对应指针为空指针）， 则说明树中没有对应的关键字, 直找失败定 位 . 利用前述的B捌查找算法， 找出插入该关假字的原低层中的某个非叶结点（ 注意: 插入位省一定是嵌低层中的某个非叶结点）B树的插入 插 入 ： 在B♦中， 个非失败结点的关键字个数都在区间［ 「 中7 2］一 1，町 一 】J捕入后的结点关键字个数小于m ,可以直接插入; 插入后检空被插入结点内关冠字的个就当插入后的结点关键字个数大于m - 1时, 必须对结点进行分裂直按删除关键字： 若偶删除关健字所在结点的关键字个数 > r m / 21 ， 表明删除该关停字后仍满足B树的定义, 则直接删去该关犍字g皿sr八1二~ r 则需要调整该结点、右（ 或左） 兄弟结点及其双亲结点（ 父子换位B闵 的 删 除 ［ 兄弟够借: 若被恻除关键字所在结点删除前的关键字个数= , 而2 1 1 1且与此结点相邻的右（ 或 左 ） 兄弟结点的关犍字个数 二I ।法 ） ， 以达到新的平衡 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _兄弟不够借: 若被免不关借字所在结点删除前的关屣字个数= 「 用/2'1 一1 目此时与该结点相邻的左、右兄弟结点的关键字个数均=「m / 21 - 1 ， 则将关题字删除后与左（ 或 右 ） 兄弟结点及双亲结点中的关键字进行合并B +树的基本概念每个分支结点最多有m棵 子 树 （ 孩子结点）非叶根结点至少有两梯子树， 其他每个分支结点至少有「 血2~1 探子树结点的子树个数与关键字个数相等.所有叶结点包含全部关键字及指向相应记录的指针, 叶结点中将关键字按大小献序排列, 并且相邻叶结点按大小峡序相互链接起来所有分支结点（ 可视为索引的索引） 中仅包含它的各个子结点（ 即下一级的索引块） 中关键字的最大值及指向月子结点的指针在B +树中， 具有n个关键字的结点只含有n操子树， 即每个关键字对应一梯子树; 而在B树中， 具有n个关键字的结点含有n + 1棵子树M阶的B+树与M阶的B树的主要差异在B ,树 g , 每 个 * 点 （ 非根内部结点； 的关逛字个数0的范围是标结点: 1 9内 山 广 在8匆0每个洁点，： 非限内部培点） 的 关 犍 字 个 数 门 的 范 匡 是< H < m 1，:根总点在B ，倒中， 叶结点包含信息,所有非叶结点仅起索引作用， 非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针， 不含有该关键字对应记录的存储地址在B +树中， 叶结点包含了全部关键字， 即在非叶结点中出现的关键字也会出现在叶结点中; 而在B树中， 叶结点包含的关犍字和其他结点包含的关键字是不重经的7.4散列表( 上 )散列函数: 一个把查找表中的关键字映射成该关键字对应的地址的函数， 记 为Hash(key ) =Addr冲 突 ： 散列函数可能会把两个或两个以上的不同关键字映射到同一地址散列表的基本概念-散列表: 根据关键字而直接进行访问的数据结构对散列表进行查找的时间复杂度为。

1)散列函数的定义域必须包含全部需要存储的关键字， 而值域的范围则依赖于散列表的大小或地址范围注意 散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中， 从而减少冲突的发生散列函数应尽量简单， 能够在较短的时间内计算出任一关键字对应的散列地址直接取关键字的某个线性函数值为散列地址士散列函数为 H(key)=key或 H(key)=a*key + b a 和 b是常数直接定址法 - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -散列函数的构造方法散列函数平方取中法■ 特点计算最简单， 且不会产生冲突特点 适合关键字的分布基本连续的情况若关键字分布不连续， 空位较多， 则会造成存储空间的浪费假定散列表表长为m,取一个不大于m但最接近或等于m的质数p,利用以下公式把关键字转换成散列地址散列函数为 H(key):key%p最简单、最常用的方法—关键是选好P，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址， 从而尽可能减少冲突的可能性设关键字是r进制数， 而।•个数码在各位上出现的频率不一定相同， 可能在某些位上分布均匀一些， 每种数码出现的机会均等而在某些位上分布不均匀， 只有某几种数码经常出现， 此时应选取数码分布较为均匀的若干位作为散列地址适合于已知的关键字集合， 若更换了关键字----------1则需要重新构造新的散列函数取 关 键 字 的 平 方 值 的 码 拽 步 散 列 地 址散列地址分布比较均匀适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数Hi = (//(key) + d0 % m数学递推公式H ( key )为散列函数m表示散列表表长;di为增量序列4 = 0, 1,2,…， 6 - 1开放定址法增量的取值方法线性探测法当出现冲突时， 就会顺序的向下一个单元探测， 直到单元没有发生冲突优 点 ： 简单容易实现缺 点 ： 会出现聚集现象， 降低查找效率平方探测法优 点 ： 可以避免出现“ 堆积” 问题，缺 点 ： 不能探测到敞列表上的所有单元， 但至少能探测到一半单元处理冲突的方法7.4散列表( 下 )4 = Hashz(key)再散列法 当通过第一个散列函数H(key )得到的地址发生冲突时厕利用第二个散列函数Hash列ey)计算该关键字的地址增量计 算公式公式乩=("(key) + ZxHash2(key)) % m伪随机序列法 d,=伪随机数序列时， 称为伪随机序列法拉链法把所有的同义词存储在一个线性链表中， 这个线性链表由其散列地址唯一标识所有同义词就像被拉链串在一起一样散列查找及性能分析+、 、 ①检测查找表中地址为Addr的位置上是否有记录， 若无记录， 返回直找失败； 若有记录， 比较它与key的 值 ， 若 相 等 ， 则返回查找成功标志， 否则执行步骤②兰人上王T②用给定的处理冲突方法计算•下一个散列地址" ， 并把Add道为此地址， 转入步骤①平均一找长度作为衡量敬列表的查找效率的度量散列表的查找效率取决于三个因素:散列函数、处理冲突的方法和装填因子特表中记录数〃散列表长度m装 填 因 子।- - - - - - - ——- 装填因子越大越容易发生冲突排 序 ： 就是重新排列表中的元素， 使表中的元素满足按关键字有序的过程8.1排序的基本概念算法的稳定性:若待排序表中有两个元素Ri和Rj其对应的关键字相同即keyi=keyj,且在排序前Ri在Rj的前面， 若使用某一排序算法排序后,Ri仍然在Rj的前面， 则排序算法是稳定的排序的定义 根据数据是否在内存中进行分类分类 插入排序交换排序基本类型 选择排序归并排序基数排序内部排序： 在排序期间元素全部存放在内存中的排序外部排序： 在排序期间元素无法全部同时存放在内存中， 必须在排序的过程中根据要求不断地在内、外存之间移动的排序基本思想 每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中， 直到全部记录插入完成概述直接插入排序引申出的算法折半插入排序希尔排序空间效率:空间复杂度为0Q )实现过程有序序列将整个序列分为两部分1 ------------------------- ——1无序序列每次从无序序列中取出一个元素， 然后在有序序列中遍历， 寻找合适的位置将该元素插入有序序列中自插入的位置开始有序序列向后移动一个元素位置L 直接插入排序8.2插入排序稳定算法性能分析表中元素已经有序, 此时每插入一个元素， 都只需比较一次而不用移动元素取灯1月/兀时间复杂度为0(n)表中元素顺序刚好与排序结果中的元素顺序相反( 逆 序 )时间效率最坏情况总的比较次数达到最大 P总的移动次数也达到最大平均情况时间复杂度 城 )时间复杂度为 脸适用于顺序存储和链式存储首先确定折半插入排序的范围实现过程然后对其进行类似于二分法定界的方式， 不断缩小其范围最后对数据进行移动， 对待排序算法进行插入空间效率： 空间复杂度为0Q )折半插入排序性能分析。

(4 0g2")时间效率 比较次数为」- 一该算法比较次数仅与表中元素个数有关稳定算法适用于顺序存储J希尔排序先将待排序表分割成若干形如L [ i , i + d, i + 2d， … ,i + kd]的 " 特 殊 " 子 表，对各个子表分别进行直接插入排序缩小增量d ,重复上述过程， 直到d=l为止实现过程 每次排序去一定的步长， 然后在选定的元素中进行直接插入排序步长逐渐减小， 最后为1空间效率:空间复杂度为1)性能分析 - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - 时间复杂度为 方冷不稳定算注适用于顺序存储根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置r -基本概述考试涉及范围冒泡排序快速排序基本思想从后往前( 或从前往后) 两两比较相邻元素的值， 若为逆序( 即) ， 则交换它们， 直到序列比较完将最小的元素交换到待排序列的第一个位置( 或将最大的元素交换到待排序列的最后一个位置)进行下一趟冒泡时， 前一趟确定的最小元素不再参与比较， 每趟冒泡的结果是把序列中的最小元素( 或最大元素) 放到了序列的最终位置如果某一趟排序过程中未发生" 交换" ， 则算法可提前结束空间复杂度：0(1)8 3交换排序冒泡排序性能分析时间效率最好情况最坏情况时间复杂度为O (n)时间复杂度5 / )平均情况冒泡排序时间复杂度为oW)稳定算法适用于顺序存储快速排序被认为是目前基于比较的内部排序方法中最好的方法J快速排序_ 首先选取一个元素作为枢纽， 然后以此枢轴为界分为两个部分， 左面小于该枢轴值， 右面大于该枢轴值基本思想- - - - - - - - - - - 然后再对这两个部分分别递归的进行上述步骤最 好 情 况0(10g2〃)空间复杂度 最坏情况 0(n)平均情况。

log2〃)性能分析 - …十 快速排序的运行时间与划分是否对称有关- - - - - - - - - - - 时间效率 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -对应于初始排序表基本有序或基本逆序时， 就 得 到 最 坏 情 况 下 的 时 间 复 杂 度 为 )快速排序的时间复杂度为5/)不稳定算法适用于顺序存储基本思想每一趟( 如第i趟 ) 在后面n-i+1 (i=L2. . … n-1) 个待排序元素中选取关键字最小的元素, 作为有序子序列的第i个元素， 直到第n-1趟做完， 待排序元素只剩下1个, 就不用再选8.4选择排序基本思想将表分为两部分， 有序部分和无序部分每次从无序部分中选取最小的兀素， 然后将其放入有序部分中空间效率: 0(1)性能分析— 元素间比较的次数与序列的初始状态无关简单选择排序—一—时 向 效 率 | 而同鲁九自% a , 8时间复杂度为5 〃)不稳定的排序算法适合顺序存储3 大 根堆： 父节点的值大于相对应的孩子结点值基 本 概 述 「 一- - - - - - - - - - - -小 跟堆： 父节点的值小于相对应的孩子结点值建 堆 ： 按照大根堆或者小根堆的规则建立起相应的二叉树， 那么根节点一定是最大值或者最小值- “' 5 调 整堆： 当根节点输出后， 整颗二叉树可能被破坏， 这是要根据相应的建堆规则， 自底向上， 自左向右， 进行父节点与子节点交换以满足相应的建堆规则堆排序空间效率: 空间复杂度为0(1)- - - - - - - - - 性能分析 时间效率 建堆时间为o(n ) 调整的时间复杂度为0(h) h为二叉树的高度时 间 复 杂 度5〃log2〃)不稳定排序算法L归并排序稳定 排序 算法2路归并——二合一每 次 选 定 相 应 的 元 素 分 别 合 成 一 个 新 的 有 序 表r - - - - - - - - -基本思想初 妫 制 f 149] [M| (6S1 (971 (76) [13] (27) R t t g _ 7 d ix 口"-T-1 hr1 hr " 1(M L429] [65 97] [13 76] (27JT!_1 .二•外 弁 后 (3S 49 6S (13 27 76)_ I示意图(13 27 M 49 65 76 97]性能分析空 间 复 杂 度 为0 ( n )时 间 复 杂 度 为O ( / i l o g2„ )适 用于 顺序 表最 高 位 优 先 (M S D )法 ： 按 关 键 字 位 权 重 递 减 依 次 逐 层 划 分 成 若 干 更 小 的 子 序 列 ， 最 后 将 所 有 子 序 列依次连接成一个有序序列排 序 思 想I--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- - - - - - - - - - - - - 最 低 位 优 先(L S D )法 ： 按 关 键 字 权 重 递 增 依 次 进 行 排 序 ， 最后形成一个有序序列8.5归并排序和基数排序一 趟 排 序 需 要 的 辅 助 存 储 空 间 为r( 「 个队列:r个 队 头 指 针 和 「 个 队 尾 指 针 )基 数 排 序 的 空 间 复 杂 度 为0”基 数 排 序 需 要 进 行d趟 分 配 和 收 集 ， 一 趟 分 配 需 要0 ( n )， 一 趟 收 集 需 要0 ( r )一 基数排序性 能分 析时间效率基 数 排 序 的 时 间 复 杂 度 为 。

d ( n + r ) ) 与 序 列 的 初始状态无关稳定排序算法埠 法 肿 类时 间 复 杂 度空 网 复 杂 度是 否 稳 定最 好 情 况平 均 情 况最 坏 情 况宜 接 播 入 蚌 序8 0代小0(1)覆 泡 排 序城)0(1)是简 编 选 建 持 序a / )0(1)否前 尔 排 序0(1)否快i t捧 序O(nlog：/i)a/)O(logj«)S堆 排 序□("log：”)B )否2 s H l卅1序0(”!叫" )a ”iog2”)N O是基 数 持 序 ( 和+ ， ) )a m+ r»“)是8.6各种内部排序算法的比较及应用j排序算法小结若n较 小 ， 可 采 用 直 接 插 入 排 序 或 简 单 选 择 排 序当记录本身信息量较大时, 用简单选择排序较好若 文 件 的 初 始 状 态 已 按 关 键 字 基 本 有 序 ， 则 选用 直接 插 入 或 冒 泡 排 序 为 宜快 速 排 序 被 认 为 是 目 前 基 于 比 较 的 内 部 排 序 方 法 中 最 好 的 方 法 待 排 序 的 关 键 字 随 机 分 布 时 ， 快速排序 的 平 均 时 间 最 短若n较大很! ) 应 采 用 时 间 复 杂 度 为0 (〃 10g2〃 ) 的 排 序 方 法 快 速 排 序 、堆排序或 归并排序要 求 排 序 稳 定 且 时 间 复 杂 度 为0("10g2% )则可选用 归并排序若n很大 ， 记 录 的 关 键 字 位 数 较 少 且 可 以 分 解 时 ， 采用基 数排序较好当记 录本 身 信 息 量 较 大 时 ， 为 避 免 耗 费 大 量 时 间 移 动 记 录 ， 可 用链表作为 存储结构8.7外部排序（ 上）进行^ 序, 目些把的记录很多、 j g 息量庞大， 殛将整个文件复制进内存中进行排也r 外部排序的基本概念一需要将待排序的记录存储在外存上， 排序时再把数据一部分一部分地调入内存进行排序， 在排序过程中需要多次进行内存和外存之间的交换外部排序的方法i-g入 文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的---------- 1 外部排序过程中的时间代价主要考虑访问磁盘的次数， 即 I/O 次数据内存缓冲区大小， 将外存上的文件分成若干长度为f的子文件， 依次读入内存并利用内部排序方法对它们进行排序, 并将排序后得到的有序子文件重新写回外存 （ 归并段或顺串）外部排序通常采用归并排序法 算法实现的两个阶段I -------------------------------------------------------------------------------------------------------------------------- 1 对这些归并段进行逐趟归并， 使归并段（ 有序子文件） 逐渐由小到大， 直至得到整个有序文件为止耗费时间 外部排序的总时间=内部排序所需的时间+ 外存信息读写的时间+内部归并所需的时间典吟蔡初始归并段个数」都能减少归并趟数， 进而减少读写磁盘的次数， 达到提高外部排序速度的目的引入败者树的背景 为了使内部归并不受k （ 归并路数） 的增大的影响基本思想败者树是树形选择排序的一种变体, 可视为一棵完全二叉树k个叶结点分别存放k个归并段在归并过程中当前参加比较的记录， 内部结点用来记忆左右子树中的" 失败者" ， 而让胜者往上继续进行比较, 一直到根结点若比较两个数， 大的为失败者、小的为胜利者, 则根结点指向的数为最小数多路平衡归并与败者树k 路归并的败者树深度riog2Ai性 能 分 析 I - --------------------------- :I 总的比较次数 S （ n ~ O flogiArl = 「 log4r1 （ 〃 - 1） 「 log2Al = （ 〃 T） 「 log?/]归并路数k并不是越大越好. 归并路数k增大时， 相应地需要增加输入缓冲区的个数注®1 I ------------ ；- - -；- - - - -;- - - - - - - ;- - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - -优化当k值过大时， 虽然归并趟数会减少, 但读写外存的次数仍会增加皿人। 乂 * “ , 、 ―*/公, 乂 代价1 ： 需要增加相应的输入缓冲区增加归并路数k ,进行多路平衡归并।- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - --- - - - - - - - - - - - - - - - - - 代价2 : 每次从k个归并段中选一个最小元素需要（ k-1） 次关键字对比减少初始归并段数量rr置换- 选择排序（ 生成初始归并段）设初始待排文件为FL初始归并段输出文件为F0,内存工作区为WA,F。

和WA的初始状态为空,WA可容纳w个记录1） 从FI输入w个记录到工作区WA2 ）从WA中选出其中关键字取最小值的记录， 记为MINIMAX记录3 ）将MINIMAX记录输出到F中去4 ） 若FI不空， 则从FI输入下一个记录到WA中5）从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录， 作为新的MINIMAX记录6 ）重复3 ） ~ 5 ） ， 直至在WA中选不出新的MINIMAX记录为止， 由此得到一个初始归并段， 输出一个归并段的结束标志到F0中去7 ）重复2 ） ~ 6 ）， 直至WA为空由此得到全部初始归并段8.7外部排序（ 下 ）结构概述各叶结点表示一个初始归并段， 上面的权值表示该归并段的长度叶结点到根的路径长度表示其参加归并的趟数各非叶结点代表归并成的新归并段根结点表示最终生成的归并段树的带权路径长度WPL为归并过程中的总读记录数引入哈夫曼树的思想在归并树中, 让记录数少的初始归并段最先归并， 记录数多的初始归并段最晚归并， 就可以建立总的I/O次数最少的最佳归并树算法优化最佳归并树示意图若初始归并段不足以构成一棵严格k叉树时， 需添加长度为。

的"虚段-按照哈夫曼树的原则， 权为0的叶子应离树根最远算法修正K意图卜设度为0的 结 点 有 （ = 〃 ） 个， 度为k的结点有 M 个需要修正的条件严格k叉树有〃 （ ） = «：- 1） 4 + 1变形可得 为 = （ 如 一 1） / （ 4一 1）（ % - 1） %（ A - 1） = 0 说明正好可以构造k叉归并树- !） %（ * -1 ） = «* 0再加上k-u-l个空归并段， 就可以建立归并树。