数据结构期末复习笔记.pdf

数据结构期末复习-笔记第一节：高等数据结构(上)数组、字符串/Array&String 链表/Linke d-list 栈/Stack 队列/Que ue 双端队列/De que 树/Tre e数组、字符串力扣242优 点：根据下标随机访问某个元素缺 点：查询某个元素是否存在时需遍历整个数组；删除/添加元素时，需0(n)时间链表力扣25结题技巧利用快慢指针(有时要三个)构建T虚假的链表头栈力扣20、739可以用一个单链表来实现算法基本思想只关心上一次的操作处理完上一次的操作后，能在0(1)时间内查找到更前一次的操作队歹u力扣239用 在：需要一定的顺序处理数据，且处理的数据在不断变化基本实现可以用f双链表来实现Null 在社交网络里，每个人可以用图的顶点表示，人与人直接的关系可以用图的边表示，在地图上，要求解从起始点到目的地，如何行驶会更快捷，需要运用图论里的最短路径算法前维树：出现在面试的难题中，要求能熟练地书写它的实现以及运用线段树和树状数组应用场合比较明确如果要求在一幅图片当中修改像素的颜色,求解任意矩形区间的灰度平均值,则需要采用二维的线段恻优先队列力扣347与普通队列的区别保证每次取出的元素是队列中优先级最高的优先级别可自定义（比如指小的优先级高）最常用的场景从杂乱无章的数据中按照一定的II质序(或者优先级)筛选数据(取出前k大的数)本质0 1 2 3 4 5二叉堆的结构，堆在英文里叫Binary he ap利用一个数组结构来实现完全二叉树特性数组里的第一个元素array 0 拥有最高的优先级给 定 一 下 标i,那么对于元素array【i】而言 父节点对应的元素下标是(i-1)/2 左侧子节点对应的元素下标是2*i+l 右侧子节点对应的元素下标是2*i+2数组中每个元素的优先级都必须要高于它两侧子节点其基本操作为以下两个(都需O(log k)向上筛选(sift up/bubble up)加入新节点时，将节点添加到数的底部(数组最后一个元素)，然后根据节点的优先级，顺着树爬上去，直到树稳定向下筛选(sift d own/bubble d own)删除根节点时，用树的最后一个节点代替根节点的位置，然后根据节点的优先级，顺着树向下比较，直到树稳定另一个最重要的时间复杂度：优先队列的初始化看似时间复杂度是O(n*log k),实际上是O(n)图必需熟练掌握的知识点图的存储和表达方式：邻接矩阵、邻接链表图的遍历：深度优先、广度优先二部图的检测(B ip a rtite)、树的检测、环的检测：有向图、无向图拓扑排序联合-查找算法(Union-Find)最短路径：Dijkstra、Be llman-Ford力扣785力扣212也称字典树这种数据结构被广泛地运用在空醺我当中什么是字典杳找？例如:给定一系列构成字典的字符串，要求在字典当中找出所有以ABC 开头的字符串方法一:暴力搜索法时间复杂度：0 (MN)方法二:前缀树时间复杂度：0 (M)重要性质每个节点至少包含两个基本属性child re n:数组或者集合,罗列出每个分支当中包含的所有字符isEnd:布尔值，表示该节点是否为某字符串的结尾根节点是空的除了根节点，其他所有节点都可能是单词的结尾，叶子节点一定都是单词的结尾最基本的操作创建 遍历一遍输入的字符串,对每个字符串的字符进行遍历 从前缀树的根节点开始，将每个字符加入到节点的child re n字符集当中 如果字符集已经包含了这个字符，跳过 如果当前字符是字符串的最后一个，把当前节点的isEnd 标记为真搜索 从前缀树的根节点出发，逐个匹配输入的前缀字符 如果遇到了，继续往下一层搜索 如果没遇到，立即返回线段树力扣315一种按照二叉树的形式存储数据的结构，每个节点保存的都是数组里某一段的总和例如要求一段大区间，则对应是各个小区间的和(不相交)先从一个例题出发假设我们有一个数组array(O.n-1,里面有n 个元素，现在我们要经常对这个数组做两件事：1,更新数组元素的数值 2,求数组任意一段区间里元素的总和(或者平均值)方法一：遍历一遍数组 时间复杂度：0 (n)方法二：线段树 时间复杂度：0 (log n)方法三：树状数组树状数组力扣308 重要的基本特征 利用数组来表示多叉树的结构，和优先队列有些类似 优先队列是用数组来表示完全二叉树，而树状数组是多叉树 树状数组的第一个元素是空节点 如果节点tre e y是 tre e 冈的父节点，那么需要满足y=x-(x&(-x)第三节：排序算法基 本 的 排 序 算 法【简单直接助你迅速写出没有bug的代码】冒泡排序/Bubble Sort 插入排序 Inse rtion Sort常 考 的 排 序 算 法【解决绝大部分涉及排序问题的关键】归并 排 序/Me rge Sort 快速排序/Quick Sort 拓扑排序/Topological Sort其 他 排 序 算 法【掌握好它的解题思想能开阔解题思路】堆排序/He ap Sort 桶排序/Bucke t Sort冒泡算法两两比较void s o rt(in t nums)boole an hasChange =tru e;fo r(in t i =;i num s.le ngth-&hasChange;i+)hasChange =fa ls e;fo r(in t j =;j numsj+)swap(nums,j,j +i);hasChange =tru e;)复杂度空间复杂度：0(1)假设数组的元素个数是 整个排序的过程中,直接在给定的数组里进行元素的两两交换。时间复杂度：0(”2),情 景 一 给定的数组按照顺序已经排好只 需 要 进 行 次 的 比 较，两两交换次数为0,时间复杂度是0(n),这是最好的情况。，情 景 二 给定的数组按照逆序排列需要进行n(n-1)/2次比较,时间复杂度是0(标2),这是最坏的情况。，情 景 三 给定的数组杂乱无章在这种情况下，平均时间复杂度是0(口 人2)。插入排序力扣147待排数据与有序区最外围数据进行比较void sort(int nums)for(int i=,j,current;i=&numsj current;j-)numsj+=numsjnumsj+=current;复杂度空间复杂度：0(1)假设数组的元素个数是m整个排序的过程中，直接在给定的散组里进行元素的两两交换。时间复杂度：0(2 2)情景一：给定的数组按照顺序已经排好只 需 要 进 行 次 的 比 较，两两交换次数为0,时间复杂度是0(n),这是最好的情况。，情景二：给定的数组按照逆序排列需要进行n(n-1)/2次比较，时间复杂度是0(2),这是最坏的情况。，情 景 三 给定的数组杂乱无章在这种情况下,平均时间复杂度是0(M 2).归并排序分治的思想归并排序的核心思想是分治，把一个复杂问题拆分成若干个子问题来求解。归并排序的算法思想/把数组从中间划分成两个子数组；递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素；依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。主体函数/*归并排序的主体函数7void sort(int A,int lo,int hi)if(lo=hi)return;int mid=lo+(hi-lo)/2;sort(A,lo,mid);sort(A,mid+,hi);merge(A,lo,mid,hi);void merge(int nums,int lo,int mid,int hi)int copy=nums.clone();int k=lo,i=lo,j=mid+;while(k mid)numsk+=copyj+;else if(j hi)numsk+=copyi+;else if(copyj=hi)return;int p=partition(nums,lo,hi);sort(nums,lo,p-1);sort(nums,p+,hi);int partition(int nums,int lo,int hi)swap(numsj randRange(10j hi),hi);int i,j;for(i=lo,j=lo;j hi;j+)if(numsj=numshi)swap(nums,i+,j);swap(nums,i,j);return i;复杂度最优情况下的时间复杂度T(n)=2*T(n/2)+0(n)0(n)是怎么得出来的呢？把规模大小为n的问题分解成n/2的两个子问题；和基准值进行n-1次比较，n-1次比较的复杂度就是0(n)；快速排序的复杂度也是O(nlogn)。最复杂的情况每次在选择基准值的时候；都不幸选择了子数组里的最大或最小值；其中一个子数组长度为1；另一个长度只比父数组少1。空间复杂度：O(logn)和归并排序不同，快速排序在每次递归的过程中；只需要开辟0(1)的存储空间来完成交换操作实现直接对数组的修改；而递归次数为lo g n,所以它的整体空间复杂度完全取决于压堆栈的次数。拓扑排序应用场合拓扑排序就是要将图论里的顶点按照相连的性质进行排序前提必须是有向图图里没有环先计算入度，删除节点后更新入度代码void sort()Queue q=new LinkedList();for(int v=0；v V;v+)if(indegreev=)q.add(v);while(!q.isEmpty()int v=q.poll();print(v);for(int u=;u adjv.length;u+)if(-indegreeu=)q.add(u);)广度优先搜索队列q保存入度为0的顶点复杂度时间复杂度：O(n)统计顶点的入度需要0(n)的时间；接下来每个顶点被遍历一次，同样需要0(n)的时间。数据结构时间复杂度线性表顺序表插 入，删 除：0(n)直接插入排序、简单选择排序、快速排序的算法以及时间复杂度直接插入排序、简单选择排序的平均时间复杂度：T(n)=O(n 2)快速排序时间复杂度平均情况(每次总是选到中间值作枢轴)T(n)=O(n l o g 2 n)最坏情况(每次总是选到最小或最大元素作枢轴)T(n)=O(M)排序 1.数据结构和算法的基本概念(1)数据、数据元素、数据逻辑结构、数据存储结构、数据类型、抽象数据类型等数 据：集合存储数据时，不仅要存储各元素的值，而且要存储数据元素之间的关系数据元素：数据的基本单位数据项：构成数据元素的最小单位一个学生就是个数据元素，数据项包含学号、姓名等数据结构定义了一组按某些关系组合起来的数据元素三要素数据逻辑结构指数据元素间的逻辑关系，与存储结构无关数据存储结构指数据结构在计算机中的映像（存储方式）顺序存储逻辑上相连的元素存储在物理位置上也连续的单元中链式存储利用地址链接各元素，不要求物理位置连续散列存储（哈希存储）根据元素关键字计算出元素的存储地址索引存储 建立索引表 索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）其优点是检索速度快，缺点是索引表额外耗费空间运算集扩展 数据的逻辑结构抽象于（独立于）存储结构 如III好 表、哈希表、单链表，即表示逻辑结构，又表示存储结构 而有序表只表示逻辑结构栈是一种抽象数据类型，可采用顺序存储戳链式存储，只表示逻辑结构而循环队列是用II同序表表示的队列数据类型不仅定义了一组带结构的数据元素，还在其上定义了一组操作扩展 1)原子类型。其值不可再分的数据类型 2)结构类型。其值可以再分解为若干成分(分量)的数据类型。3)抽象数据类型。抽象数据组织及与之相关的操作抽象数据类型(ADT)描述了数据的逻辑结构和抽象运算仅仅是一组逻辑特性的描述与其在计算机内的实现无关用三元组(数据对象,数据关系，基本操作集)来表示，从而构成一个完整的数据结构定义(2)算法、算法设计的要求、算法效率的度量、算法存储空间的需求等算法概念算法是对特定问题的求解步骤算法的计算量大小称为计算的：复杂性算法设计的要求正确性：每一个步骤有确定的含义健壮性：对非法数据能进行处理算法效率的度量 用 f(n)计算时间复杂度，T(n)为频度之和，0(n)是 T(n)的数量级(n 为问题的规模)时间复杂度为。(标2),说明算法的执行时间与M 2 成正比 最内层语句被执行的次数常见的渐近时间复杂度为0(1)O(log2n)O(n)O(nlog2n)0(n2)O(n3)0(2)O(n!)next=head判断是否尾节点:p-next=head双向链表插入过程PP1 Fbciau-ru-.s s T|口 e|I Il图2 9 双向链表的插入 _先右后左 s-next=p-next p-next-prior=s p-next=s s-prior=p循环链表和双向链表从任意节点出发都可访问任意节点栈顺序栈结构 top:指向栈顶 bottom:指向栈底操作判断空栈：top=bottom top指向位置有兀涝动态J I同学栈可以根据需要增大栈的空间 botte m指向位置有元素 top指向位置不放元素共享栈 利用了栈底位置不变，栈顶位置动态变化的特性 栈底在两端（0和M-1）top0和to p l是两个栈顶指示器链栈top-Atop空栈链栈存储形式非空栈多栈运算队列顺序队列 插 入：rear位置插入元素，后+1 删 除：front位置删除，后+1 初始化：front=rear=0队 空：rear=front 队 满:rear=MAX_QUEUE_SIZE-1循环队列 队满：front=(rear+1)%MAX_QUEUE_SIZE链队列 rear指向元素的后一链队列结点示意图 结构 front:队头指针，在此删除元素 rear:队尾指针，在此添加元素操作队空：front=rear添加/删除元素（a空从药(b)xAfk（c）y再入队同 x出队队雉作及指针变化（2）栈、队列和线性表的实现，包括顺序和链式存储结构（3）栈、队列和线性表的应用线性表已知元素个数时，使用III页序存储更节省时间，因为链式存储需要存储额外的指针删除单链表中值相同的节点48 删除单链表中值相同的节点49 void Delete_Node_value(LNode*L)50 LNode*p=L-next,*q,*ptr;51(p!=NULL)5253545556575859606162636465)66)q=p;ptr=p-next;(ptr!=NULL)(ptr-data=p-data)q-next=ptr-next;free(ptr);ptr=q-next;elseq=ptr；ptr=ptr-next;p=p-next;串串；字符的有限序列空 串：长度为0的串空串所任意串的子串 空白串（空格串）：所有字符都是空格的串 串长：所含字符长度 串的存储方式 定长存储：字符数组 堆分配：长度动态变化的字符数组 块链存储：链式存储，一个块包含若干个字符在串未填上不属于串值的特殊字符，表示串的总结串的模式匹配算法 模式匹配：指子串值主串中的定位，匹配成功表在主串S中能找到模式串T BF*求串的next函数值I 0123456789 10 11abcaabbabcabnext|4 00011201234rmtvalU-1 0 0-1 1 0 2-1 0 0-1 I 4|next数组首字符从-1开始若从答案从0开 始，则整体数组+1得结果匹配第i个字符，看0 i-1的字符间（头和尾）是否有相同子串有：写上子串长度无：写0 nextval数组 辅助步骤：先根据next数组值，写下对应的字符 首字符从-1开始 比对第i位字符和辅助字符是否相同不 同：nextval的值即为next的值相 同:看next的值为多少,为k则取nextvalk.数组定义的下标从1开始数组的存储两种类型：按行存储/按列存储三角矩阵分上三角、下三角带状矩阵以对角线为中心，三条元素稀疏矩阵三元组表示法十字链表 3.排序基础（1）排序的概念与分类内部排序插入排序直接插入排序直接插入排序1typedef int D a t a T y p e;2直接插3void I n s e r t S o r t(D a t a T y p e L ,int l e n)4inti，3；5D a t a T y p e t e m p;6f o r(i=l;i =0;j-)9i f(t e m p L j )L j+1 =L j ;1 0e l s e b r e a k;数据移位1 11 2L j+1 =t e m p;1 31 4思 想：数据分为两个区一有序区和无序区；每次都取最靠近有序区的数插入到有序区中（没有选择的过程！）插入排序过程30。5。40 2520i=l203050I402550i=2203015040i2540i=32030I-405025_ i25i=42025304050初始时，有序区元素个数为1直插是稳定排序直接插入排序、简单选择排序的平均时间复杂度：T(n)=O(n2)折半插入排序希尔排序思想序列增量作为分组间隔，分为若干组，组内进行直接插入排序一般第一次取的增量为n/2不断缩小增量，直到为1步骤楙而而第轮组耦*了仙讨郴布时”和精魄段T为推而楙tH tiifft 播耀2 ttfttitfi交换排序冒泡排序冒泡排序/冒泡排序：对n个数，要排n-1趟，第j趟要交换向次vo id b u b b le _ s o rt(in t a ,in t n)in t te mp=0;fo r(in t i=0;i n;i+)fo r(in t j=0;j a j+l)交换te mp=a j;a j =a j+1;a j+1 =te m p;?快速排序快速排序1 typedef int DataType;2/快速排序3 void Quicksort(DataType R,int s,int e)4 int low=s,high=e;DataType x=Rs;6?.hile(low high)(low=x)high-;Rlow=Rhigh;(lowhigh&Rlowx)low+;10 Rhigh=Rlow;彳大数放在右恻大数序列中11 循环结束时low、h i g h 合12 Rlow=x;13 if(s high-1)14 QuickSort(R,s,high-1);15 if(high+1 e)16 Quicksort(R,high+1,e);对右例大数序列进行递归划分”1 思 想：每次取第一个数为枢轴，从另一边开始取数进行比较，若大于枢轴贝怀变，小于则将那个数放到枢轴的位置。high和low的指针重合的地方就是枢轴该呆的地方，枢轴一旦确立后其位置不变 练习】写出序列 31,68,45,90,23,39,54,12,87,76 以“31”为枢轴的一次划分结果。12,231,90,45,39,54,68,87,76 快速排序是不稳定的！快速排序时间复杂度平均情况(每次总是选到中间值作枢轴)T(n)=O(n l o g 2 n)最坏情况(每次总是选到最小或最大元素作枢轴)T(n)=O(n2)选择排序简单选择排序直接选择排序1234567891011121314151617typedef int DataType;直接选择排序void SelectSort(DataType L,int len)int i,j,min;DataType temp)(i=0;ilen-l;i+)min=i;for(j=i+l;jlen;j+)求i后的第1个数到末尾的min(Lj Lmin)min=j;)(min!=i)temp=Li;Li=Lmin;Lmin=temp;思 想：数据分为两个区一有序区和无序区；每次都在无序区中取一个最小的数送到有序区中(比较+交换)选择排序过程30 20 50 40 25t _T第i=l趟结果：20 30 50 40 25t _第i=2趟结果：20 25 50 4 0 独1 _T第i=3趟结果：20 25 30 40 50第i二 4趟结果：20 25 30 40 50初始时，有序区为空直选是不稳定的！直接插入排序、简单选择排序的平均时间复杂度：T(n)=O(n2)堆排序归并排序过程初始关键字：23 38 22 45L _rJ Ln_ J一趟归并后：23 38 22 45I II二趟归并后：22 23 38 45I_ _ _ _ _ _ _.I三趟归并后：15 22 23 23四趟归并后：15 22 23 23图1 5 1 1归并排序过程代码基数排序外部排序多路归并排序 (2)直接插入排序、希尔排序与基数排序 4.哈希表 (1)哈希表的构造设计哈希函数：y=h（k）y 为求得的哈希地址，h 为求地址使用的函数，k 是自变量（或称关键字，即一个个数据）直接定值法 定 义：y=k+b（b 为偏移量）适用场合：k 值连续 缺 点：易于浪费空间除留余数法 定 义：y=k%n（n 为存储空间个数）适用场合：大部分 Ps:n 值一般取小于或等于存储空间的素数设计哈希函数方法拓展直接定值法 定 义：y=k+b（b 为偏移量）适用场合：k 值连续 缺 点：易于浪费空间 数字分析法定 义：杳看数字的各位，取其值相差较大的某几位作为关键字k平方取中法定 义：将一个数平方后取其中间几位作为k原 理：平方后中间的数值一般相差较大折叠移位法移位叠加法定 义：将一个数拆为位数相同的若干块，并将这些块相加，舍弃进位，结果作为k间界叠加法定 义：与移位叠加法类似，但其取其中的一位前后颠倒（如 5 8 4 变 成 485）后相加，舍进位，结果为k解决冲突方法冲 突：对不同的关键字取到同一个地址,即引起冲突开放定址法定 义：y=（k%n）+d i）%n（以除留余数法为例）di取值的不同可分为以下几类线性探索法(最常用！)di取2 1 的正整数并递增(1,2,3,4,.)平方探查法 di为线性探索法的平方冲突解决方法拓展开放定址法定 义：y=(k%n)+d i)%n(以除留余数法为例)di取值的不同可分为以下几类线性探索法(最常用！)di取2 1 的正整数并递增(123,4,.)平方探查法di为线性探索法的平方链地址法h(2 0)=2 0%l l=9；散列表：。h(3 0)=3 0%l l=8；1h(70)=70%l l=4；2h(1 5)=1 5%l l=；Jh(8)=8%l l=；5h(1 2)=1 2%l l=l；6h(1 8)=1 8%l l=7；7h(6 3)=6 3%U=；:h(1 9)=1 9%l l=；i oAA-AAA AAA-A A-AT 1 2 1 A l-OITOQ-OJSE-o|2 S P 定 义：以链表洞诸存数据，将冲突了的关键字连接在同一地址的上一个关键字后构造哈希表已知散列表地址区间为0 10,给定关键字序列(20,3 0,7 0 ,15,8,12,18,63,19)。哈希函数为h(k)=k%ll,分别采用线性探查法和链地址法处理冲突，构造散列表。要求写出各自的计算过程并画出对应的散列表线性探查法h（20）=20%ll=9；h（30）=30%ll=8；h（70）=70%ll=4；h（15）=15%ll=4,冲突;h（）=4%=（4+1）%1 1=5；h（8）=8%ll=8,冲 突；h0=8%=（8+1）%1 1=9,冲突；h2=（8+2）%1 1=1 0；h（12）=12%ll=l；h（18）=18%ll=7；0散 列 表：应h（63）=63%H=f,冲突;%d儿=（8+1）%1 1=9,冲突；h2=（8+2）%l l=1 0,冲突;h3=（8+3）%1 1=0；h（19）=19%U=：,冲突;%=8hj =（8+1）%1 1=9,冲突；h2=（8+2）%l l=1 0,冲突;h3=（8+3）%1 1=0,冲突；%=（8+4）%1 1=1,冲突；%=（8+5）%1 1=2。1 2 3 4 5 6 7 8 9112|19|70115|118|30|20|链地址法h（20）=20%ll=9；散 列 表。A_h（30）=30%ll=8；1-HukJh（70）=70%ll=4；2Ah（15）=15%ll=；34A-170|THl51A|h（8）=8%ll=；5Ah（12）=12%U=l；6Ah（18）=18%ll=7；77 i 8|7h（63）=63%U=；89-MM3h（19）=19%ll=；10A定 义：以链表来储存数据，将冲突了的关键字连接在同一地址的上一个关键字后（2）哈希表的实现散列表应用拓展：初始化：为每个空间都设为空标志，表长为0查找步 骤：L将要查找的数作为关键字，计算其哈希地址 2、将原表中相应哈希地址的数与要查找的数作比较，若相同则查找到 3、若不相同则按照冲突解决方法，对照下一空间的数是否相等 查找失败的情况：计算出来的地址对应的值为空标志查找次数与散列表的容量相同删除步 骤：L第一步与查找的第一步相同 2、比较，若相同则删除 3、同查找的第三步 4、表长减1插入步 骤：1、先查找，若查找到与插入的数相同的关键字，则关键字已存在，插入失败2、若没找到相同的关键字，则按照冲突解决方法继续往下找、若下一地址为删除标志，则记录该位置d e le te d _ pos、若下一地址为空标志，则插入关键字 重复，直至探查次数与散列表的容量相同或插入成功/失败 3、若探查次数与散列表容量相同，则将关键字插入到d e le te d _ pos位 置,表长加15.递归(1)递归函数的执行过程(2)折半查找、归并排序和快速排序折半查找要求每次都取中间值，通过中间值是大于或小于要查的数,从而来确定查找区间操作 初 始:mid =(low+high)/2,low=最低,high=表长 若关键字大于mid low=mid +1 mid =(low+high)/2 若关键字小于mid high=mid -1 mid =(low+high)/2若high low:查找失败要 求：查找表必须有序分块查找法将列表组织成索引顺序结构先通过索引表确定要查找的子表在子表中检索（III褥 查 找 法）归并并E序步骤初始关键字：23 38 河 怦 一一趟归并后：23 38 22 451r 1二趋归并后：22 23 38 45II三趟归并后：15 22 23 23四趟归并后：口5 22 23 2323 67 31 15 41 L-rJ|23 67 15 31 41图1 0 4 1归并排序过程1234567891 01 11 21 31 41 51 61 7typedef int D a t a T y p e;快速排序void Q u i c k so rt(D a t a T y p e R ,int s,int e)int l o w =s,h i g h =e;D a t a T y p e x =R s;h i L (l o w h i g h)(l o w =x)h i g h-;R l o w =R h i g h ;(l o w h i g h&R l o w x)l o w+;R h i g h =R l o w ;R l o w =x;f(s h i g h-1)Q u i c k so rt/,s,h i g h-1);/，f(h i g h+l e)Q u i c k so rt、，h i g h+1,e);思 想：每次取第一个数为枢轴，从另一边开始取数进行比较，若大于枢轴则不变，小于则将那个数放到枢轴的位置。high和low的指针重合的地方就是枢轴该呆的地方，枢轴一旦确立后其位置不变【练习 1 写出序列 31,68,45,90,23,39,54,12,87,76）以“31”为枢轴的一次划分结果。12,231,90,45,39,54,68,87,76快速排序是不稳定的！（3）广义表的定义、存储与实现定 义：由 n个元素构成的序列，元素可以是原子，也可是子表广 义 表表长n表深hA=()01B=(e)1C=(a,(b,c,d)2D=(A,B,C)33W=(a，E)2F=()7 1-l)性质2:深度为k的二叉树至多有2人匕1个结点(k2l)性质3:包含n个结点的二叉树的高度至少为Iog2(n+1)性质4:在任意一棵二叉树中，若终端结点的个数为nO,度为2 的结点数为n2,则n0=n2+l定 义：所有结点的度均为2,且所有叶子结点均在最后一层完全二叉树定 义：前 n 个结点与满二叉树相同二叉树的五种基本形态：5款翦冬形套(1)空二叉树 鬟 整 的 (3)锻和左子树(4)根和右千M(5)程和左右子材 A、空二叉树 B、只有一个根结点的二叉树 C、右子树为空的二叉树 D、左子树为空的二叉树 E、左、右子树都为空的二叉树(2)二叉树的实现，包括顺序和链式存储结构顺序存储必须按照完全二叉树的形式来存链式存储一个节点有三个域 数据域 左孩子指针 右孩子指针结论若一棵树有n 个节点，需要2 n 个指针域。分支数目B=n-l0则浪费2n-B=n+1个存储空间（3）二叉树的遍历中序遍历非递归算法步骤 初始化一个空栈S，指针p 指向根结点 申请一个结点空间q,用来存放栈顶弹出的元素 当p 非空或者栈s 非空时，循环执行以下操作：如果p 非空，则将p 进栈，p 指向该结点的左孩子如果p 为空，则弹出栈顶元素并访问，将 p 指向该结点的右孩子中序遍历：a*二叉树的遍历 前序遍历（根左右）中序遍历（左根右）后序遍历（左右根）由中序+前序或后序遍历画出二叉树确定方法：由前序（或后序）序列确定根再由中序序列确定左、右 树的范围后序遍历序列：E-D C A （左右）中序遍历序列：|E A D C（左 右）由前序遍历（空树以#表示）画出二叉树练习：请画出通过前序遍历CrcatcBTrcjPrc按下列次序输入字符时ABC#DE#G#F#创而 J :叉树。（4）堆和堆排序（5）二叉排序树已知关键字序列，构造二叉排序树，并列出查找某个关键字的过程以及比较次数二叉排序树特点【例】已知关键字序列 10,18,3,8,12,2,7,4）,请给出构造一颗二叉排序树的过程。较小的数在左，较大的数在右中序序列恰好为递增的有序序列查找某个关键字的过程删除二叉排序树的某个数删除叶子结点或单支结点删除双分支结点（用该结点中序遍历的前驱结点或后继结点来代替）二叉排序树的查找性能分支越均衡，树的深度越浅，平均查找长度ASL越小(6)二叉平衡树左子树与右子树的高度差 2的二叉排序树平衡因子：左子树深度-右子树深度平衡化操作找不平衡的子树，圈出临近的3个节点，把其中中间值作为根节点二叉树的操作线索二叉树给出二叉树，建立相应的中序线索二叉树线索二叉树的意义：解决二叉树空指针过多(空指针数目=2 n-(n-l)=n+l)的浪费利用空指针域时，为了避免混淆，给结点增加两个标志域，如下图所示：Itagleftdatarightrtag约定:左标志I t a g J 表 可 eft 指向左孩子结点I 1 表小l eft 指向前驱结点右标书r t a g 表示r i ght 指向右孩子结点心,a g 1 1 表示r i ght 指向后继结点普通线索二叉树对前序、后 序：线索化后有一个指针域指向NULL对中序：两个指针域指向NULL按中序遍历得到的线索二叉树称为中序线索二叉树双向线索链表在二叉树的线索链表上添加一个头节点G)(J H)M二叉树/Thrt(C)中序线索二叉链表(b)中序线索树的逻辑形式中序线案二叉树及其存保结构左孩子：指向根节点右孩子：指向中序最后一个节点哈夫曼数给出叶子结点的权值，建立相应的哈夫曼树，并求带权路径长度WPL和哈夫曼编码二叉树的带全路径长度WPL=每个叶子节点的权值与对应路径长度的乘积之和 图中 WPL=(3+5+7+8)*4+(11+14)*3+(23+29)*2 哈夫曼编码的特点：权值越大的字符编码越短，反之越长 给出叶子结点的权值，建立相应的哈夫曼树，并求带权路径长度WPL和哈夫曼编码已知某系统在通信联络中只可能出现八种字符，其概率分别为0.05,0.29,0.07.0.08.0.14.0.23.0.03.0.11.试设计哈夫曼编码（在构造哈夫曼树时要求左子树的根结点权值W右子树权值）。辟钎“-*-1八八I 3用匀2A 八 、?Il n 19 0 3人一 八3 9 7 8 4-提示：苜先画出此哈夫曼树.设权=（5,29,7,8,14,23,3,11）,f i n 伊叶/结点的哈夫曼树共有_ 2 n-l _ 个结点。P s；当遇到有相同结点或权值接近时，一般用高度小的结点结合（例如此题的5+3=8与原题的8）。二叉树的带全路径长度WPL=每个叶子节点的权值与对应路径长度的乘积之和图中 W PL=(3+5+7+8)*4+(11+14)*3+(23+29)*2哈夫曼编码的特点：权值越大的字符编码越短，反之越长写出电文“ATTSTATADT中各字符的哈夫曼编码字符集合T,A,D,S构造哈夫曼树（左权为0,右权为1）T A IXD S 哈夫曼编码：T:0 A:11D：100 S：101操作算法统计二叉树的结点总数1 typedef int DataType;2 struct BTNodeDataType data;4 BTNode*lchild;BTNode*rchild;6；一个二叉镀表由根指针root唯一确定，若二叉树为空，则r8t=NULL78 统计二叉树中结点总数=左子树结点数+右子树结点数+1(根节点)9 int BTreeCount(BTNode*root)10(root=NULL)0;11 else1213BTreeCount(root-lchild)+BTreeCount(root-rchild)+1;左子树结点数+右子树结点数+1(根结点)统计二叉树叶子结点总数7 int Leafs(BTNode*root)8(root=NULL)return 0;(root-lchild=NULL&root-rchild=NULL)1;Leafs(root-lchild)+Leafs(root-rchild);11 1 1计算二叉树的深度1 typedef int DataType;2 struct BTNode3 DataType data;4 BTNode*lchild;BTNode*rchild;6；78 左、右子树中深度较大的子树深度”I9 int BTreeDepth(BTNode*root)10 i(root=NULL)ret 0;11 else12 int depl=BTreeDepth(root-lchild);13 int depr=BTreeDepth(root-rchild);14(depldepr)return depl+1;15 else return depr+1;16)17 左、右子树中深度较大的子树深度+1查找二叉树中值为item的结点1 typedef int DataType;2 struct BTNodeDataType data;4 BTNode*lchild;5 BTNode*rchild;6；78 查找二叉树中值为item的结点9 BTNode*FindBTree(BTNode*root,DataType item)10 if(root=NULL)return NULL;11(root-data=item)return root;12 BTNode*p=FindBTree(root-lchild,item);13 if(p!=NULL)return p;14 else15 return FindBTree(root-rchild,item);16 7.树和森林(i)树的定义以及树的存储结构，包括双亲、双亲孩子和孩子兄弟表示法定义有关树的概念度结点的度：某一个结点的拥有的孩子结点的个数（有多少条分支）树的度：取树中结点的度的最大值存储结构双亲表示法（顺序）利用了任一个节点只有一个父节点的特性。可以直接找到任一节点的父节点，当求子节点时需扫描整个数组咸 凌:树的双亲存储结构*双亲孩子表示法每个节点有多个指针域，每个指针域指向子树的根节点孩子兄弟表示法(二叉树表示法)(2)树和森林与二叉树的转换原理二叉树转