数据结构复习要点.doc

数据结构考试大纲第一章 绪论 1、数据结构的基本概念和术语 2、算法的描述 第二章 线性表 1、线性表的逻辑结构 2、线性表的存储结构及基本操作 3、线性表的应用 第三章 栈和队列 1、栈和队列的逻辑结构定义 2、栈和队列的存储结构及基本操作 3、栈和队列的应用 第四章 串 1、串的逻辑结构定义 2、串的存储结构及基本操作 3、串的应用 第五章 数组和广义表 1、数组和广义表的定义、存储结构 2、数组的运算 3、矩阵的压缩存储 4、数组的应用 第六章 树和二叉树 1、树的结构定义和基本操作 2、二叉树的定义、性质和存储结构 3、遍历二叉树和线索二叉树 4、树和森林（存储结构、互相转换、遍历） 5、树的应用 第七章 图 1、图的定义和术语 2、图的存储结构 3、图的遍历 4、图的应用 第八章 查找 1、线性表、有序表的查找及其分析 2、二叉排序树和平衡二叉树 3、散列（Hash）表的定义，Hash叉数的构造方式、冲突处理和Hash表的查找及其分析 第九章 内部排序 1、排序的基本概念 2、各种排序方法及其分析 第十章 外部排序 1、外存信息存取的基本概念 2、磁盘、磁带归并排序 第十一章 文件 1、有关文件的基本概念 2、顺序文件、索引文件、索引顺序文件、直接存取文件、多重链表文件、倒排文件等的存取方法。 第一章 绪论 1、数据结构的基本概念和术语 数据：是描述客观事物的数、字符以及所有能输入到计算机中被计算机程序加工处理的信息的集合。数据元素：数据的基本单位。（一个数据项或多个数据项（域）。数据项是数据的最小单位。结点、顶点、记录。数据对象：是性质相同的数据元素的集合。数据结构：相互之间存在着某种逻辑关系的数据元素的集合。数据之间的相互关系，即数据的组织形式。四类基本结构：集合、线性结构、树形结构、图状结构或网状结构。1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。数据的逻辑结构，简称为数据结构，有：1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前驱和后继。2）非线性结构，一个结点可能有多个直接前驱和后继。数据的存储结构有：1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。2）链接存储，结点间的逻辑关系由附加指针字段表示。3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。4）散列存储，按结点的关键字直接计算出存储地址。 数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。抽象数据类型ADT：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。抽象数据类型的表示：三元组（数据对象D，D上关系集S，对D的基本操作集P）。 2、算法的描述 算法：是执行特定计算的有穷过程。算法特性：有穷性 确定性 可行性 有输入 有输出。算法设计要求：正确性、可读性、健壮性、效率与低存储量需求评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。 算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为O(n)。时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数。算法衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度。第二章 线性表 1、线性表的逻辑结构 线性表：是由n(n0)个数据元素组成的有限序列。 2、线性表的存储结构及基本操作 线性表的基本运算有：建表、插入、删除、查找、定位、遍历（P19）1）InitList(L),构造空表，即表的初始化；2）ListLength(L),求表的结点个数，即表长；3）GetNode(L,i),取表中第i个结点，要求1iListLength(L)；4）LocateNode(L,x)查找L中值为x的结点并返回结点在L中的位置，有多个x则返回首个，没有则返回特殊值表示查找失败。5）InsertList(L,x,i)在表的第i个位置插入值为x的新结点，要求1iListLength(L)+1；6）DeleteList(L,i)删除表的第i个位置的结点，要求1iListLength(L)；顺序存贮结构：地址计算（数组：以行为主、以列为主）。链式存贮结构：单链表、循环链表、双向链表。数据结构改变了，解决问题的策略也相应要改变。顺序表和链表的比较1）基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。2）基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量）存储密度：顺序表=1，链表1。 3、线性表的应用 一元多项式表示与运算。第三章 栈和队列 1、栈和队列的逻辑结构定义 栈：限制仅在表的一端进行插入和删除运算的线性表，又称为后进先出表（LIFO表）。插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。队列：限制仅在表的一端进行插入操作，在另一端进行删除操作的线性表，又称为先进先出线性表（FIFO表）。允许删除的一端称队首，允许插入的一端称队尾。双端队列： 2、栈和队列的存储结构及基本操作 栈的基本运算有：1）initstack(s)，构造一个空栈；2）stackempty(s)，判栈空；3）stackfull(s)，判栈满；4）push(s,x)，进栈；5）pop (s)，退栈；6）stacktop(s)，取栈顶元素。顺序栈：栈的顺序存储结构称顺序栈。链栈当栈满时，做进栈运算必定产生空间溢出，称“上溢”。当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。队列的基本运算：1）initqueue(q)，置空队；2）queueempty(q)，判队空；3）queuefull(q)，判队满；4）enqueue(q,x)，入队；5）dequeue(q)，出队；6）queuefront(q)，返回队头元素。顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。链队列顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize循环队列的边界条件处理：由于无法用front=rear来判断队列的“空”和“满”。解决的方法有：1）另设一个布尔变量以区别队列的空和满；2）少用一个元素，在入队前测试rear在循环意义下加1是否等于front；3）使用一个记数器记录元素总数。 3、栈和队列的应用 栈与递归表达式的三种标识方法：前缀表示、中缀表示、后缀表示。第四章 串 1、串的逻辑结构定义 串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；空串：长度为零的串称空串；空白串：由一个或多个空格组成的串称空白串；子串：串中任意个连续字符组成的子序列称该串的子串；主串：包含子串的串称主串；子串的首字符在主串中首次出现的位置定义为子串在主串中的位置；空串是任意串的子串；任意串是自身的子串；串常量在程序中只能引用但不能改变其值；串变量取值可以改变； 2、串的存储结构及基本操作 串的基本运算1） int strlen(char *s);求串长。2） char *strcpy(char * to,char * from);串复制。3） char *strcat(char * to,char * from);串联接。4） int strcmp(char *s1,char *s2);串比较。5） char *strchr(char *s,char c);字符定位。串的存储结构：1）串的顺序存储：串的顺序存储结构称顺序串。按存储分配不同分为：a）静态存储分配的顺序串：直接用定长的字符数组定义，以“0”表示串值终结。#define maxstrsize 256typedef char seqstringmaxstrsize;seqstring s;不设终结符，用串长表示。Typedef struct Char chmaxstrsize; Int length;seqstring;以上方式的缺点是：串值空间大小是静态的，难以适应插入、链接等操作。b）动态存储分配的顺序串：简单定义：typedef char * string;复杂定义：typedef struct char *ch; int length; hstring;2）串的链式存储：串的链式存储结构称链串。链串由头指针唯一确定。类型定义：typedef struct node char data; struct node *next;linkstrnode;typedef linkstrnode *linkstring;linkstring s;将结点数据域存放的字符个数定义为结点的大小。结点大小不为1的链串类型定义：#define nodesize 80typedef struct node char datanodesize; struct node * next;linkstrnode;6.串运算的实现（1）顺序串上的子串定位运算。1）子串定位运算又称串的模式匹配或串匹配。主串称目标串；子串称模式串。2）朴素的串匹配算法。时间复杂度为O(n2)。比较的字符总次数为（n-m+1）m。Int naivestrmatch(seqstring t,seqstring p) int i,j,k; int m=p.length; int n=t.length; for(i=0;i=n-m;i+) j=0;k=i; while(jdata=p-data)t=t-next; p=p-next; else shift=shift-next; t=shift; p=P; if(p=NULL) return shift; else return NULL; 3、串的应用 文本编辑、建立词索引表第五章 数组和广义表 1、数组和广义表的定义、存储结构 多维数组：一般用顺序存储的方式表示数组。常用存储方式有：1）行优先顺序，将数组元素按行向量排列；2）列优先顺序，将数组元素按列向量排列。广义表：是线性表的推广，广义表是n个元素的有限序列，元素可以是原子或一个广义表，记为LS。若元素是广义表称它为LS的子表。若广义表非空，则第一个元素称表头，其余元素称表尾。表的深度是指表展开后所含括号的层数。把与树对应的广义表称为纯表，它限制了表中成分的共享和递归；允许结点共享的表称为再入表；允许递归的表称为递归表；相互关系：线性表纯表再入表递归表；广义表的特殊运算：1）取表头head(LS)；2）取表尾tail(LS); 2、数组的运算 计算地址的函数：LOC(Aij)=LOC(Ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d对Ac1:d1, c2:d2*d 3、矩阵的压缩存储 矩阵的压缩存储：为多个非零元素分配一个存储空间；对零元素不分配存储空间。1） 对称矩阵：在一个n阶的方阵A中，元素满足Aij=Aji 0=i,j(k-1)/2以行优先顺序存放的Aij与SAk的关系：k=2i+j;稀疏矩阵：当矩阵A中有非零元素S个，且S远小于元素总数时，称为稀疏矩阵。对其压缩的方法有顺序存储和链式存储。1）三元组表：将表示稀疏矩阵的非零元素的三元组（行号、列号、值）按行或列优先的顺序排列得到的一个结点均是三元组的线性表，将该表的线性存储结构称为三元组表。2）行逻辑链接的顺序表：在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三元组表中的起始位置。3）十字链表： 4、数组的应用 第六章 树和二叉树 1、树的结构定义和基本操作 树：是n个结点的有限集T，T为空时称空树，否则满足：1）有且仅有一个特定的称为根的结点；2）其余结点可分为m个互不相交的子集，每个子集本身是一棵树，并称为根的子树。树的表示方法：1）树形表示法；2）嵌套集合表示法；3）凹入表表示法；4）广义表表示法；一个结点拥有的子树数称为该结点的度；一棵树的度是指树中结点最大的度数。度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点根结点称开始结点，根结点外的分支结点称内部结点；树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲；树中存在一个结点序列K1，K2，Kn，使Ki为Ki+1的双亲，则称该结点序列为K1到Kn的路径或道路；树中结点K到Ks间存在一条路径，则称K是Ks的祖先，Ks是K的子孙；结点的层数从根算起，若根的层数为1，则其余结点层数是其双亲结点层数加1；双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度；树中每个结点的各个子树从左到右有次序的称有序树，否则称无序树；树的存贮表示：1）双亲数组表示：记录型一维数组：data,parent2）孩子链表表示法：多重链表表示法: data,degree,link1,link2单链表表示法:data,likn3）左孩子右兄弟链表示法：lchild,data,rsibling 2、二叉树的定义、性质和存储结构 二叉树：是n个结点的有限集，它或为空集，或由一个根结点及两棵互不相交的、分别称为该根的左子树和右子树的二叉树组成。二叉树不是树的特殊情况，这是两种不同的数据结构；它与无序树和度为2的有序树不同。二叉树的性质：1）二叉树第i层上的结点数最多为2(i-1)；2）深度为k的二叉树至多有2k-1个结点；3）在任意二叉树中，叶子数为n0，度为2的结点数为n2，则n0=n2+1；满二叉树是一棵深度为k的且有2k-1个结点的二叉树；完全二叉树是至多在最下两层上结点的度数可以小于2，并且最下层的结点集中在该层最左的位置的二叉树；具有N个结点的完全二叉树的深度为log2N取整加1；二叉树的存储结构顺序存储结构：把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然后依次存储在一个向量b0n中，b1n存放结点，b0存放结点总数。各个结点编号间的关系：1）i=1是根结点；i1则双亲结点是i/2取整；2）左孩子是2i, 右孩子是2i+1；（要小于n）3）i（n/2取整）的结点是叶子；4）奇数没有右兄弟，左兄弟是i-1；5）偶数没有左兄弟，右兄弟是i+1；链式存储结构在二叉树中所有类型为bintnode的结点和一个指向开始结点的bintree类型的头指针构成二叉树的链式存储结构称二叉链表：lchild,data,rchlid。二叉链表由根指针唯一确定。在n个结点的二叉链表中有2n个指针域，其中n+1个为空。三叉链表：parent,lchild,data,rchlid双亲链表：data,parent,LRTag线索链表：lchild,ltag,data,rtag,rchild 3、遍历二叉树和线索二叉树 二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为O(n)。前序：根左右中序：左根右后序：左右根线索二叉树：利用二叉链表中的n+1个空指针域存放指向某种遍历次序下的前趋和后继结点的指针，这种指针称线索。加线索的二叉链表称线索链表。相应二叉树称线索二叉树。线索链表结点结构：lchild,ltag,data,rtag,rchild；ltag=0, lchild是指向左孩子的指针；ltag=1, lchild是指向前趋的线索；rtag=0,rchild是指向右孩子的指针；rtag=1,rchild是指向后继的线索；查找*p在指定次序下的前驱和后继结点。算法的时间复杂度为O(h)。线索对查找前序前驱和后序后继帮助不大。遍历线索二叉树。时间复杂度为O(n)。 4、树和森林（存储结构、互相转换、遍历） 森林是m棵互不相交的树的集合。树、森林与二叉树的转换1）树与二叉树的转换：1所有兄弟间连线；2保留与长子的连线，去除其它连线。该二叉树的根结点的右子树必为空。2）森林与二叉树的转换：1将所有树转换成二叉树；2将所有树根连线。二叉树与树、森林的转换。是以上的逆过程。树的存储结构1）双亲链表表示法：为每个结点设置一个parent指针，就可唯一表示任何一棵树。Data|parent2）孩子链表表示法：为每个结点设置一个firstchild指针，指向孩子链表头指针，链表中存放孩子结点序号。Data|firstchild。3）双亲孩子链表表示法：将以上方法结合。Data|parent|firstchild4）孩子兄弟链表表示法：附加两个指向左孩子和右兄弟的指针。Leftmostchild|data|rightsibling树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历对应二叉树。 5、树的应用 树的路径长度是从树根到每一结点的路径长度之和。将树中的结点赋予实数称为结点的权。结点的带权路径是该结点的路径长度与权的乘积。树的带权路径长度（WPL）又称树的代价，是所有叶子的带权路径长度之和。带权路径长度最小的二叉树称最优二叉树（哈夫曼树）。具有2n-1个结点其中有n个叶子，并且没有度为1的分支结点的树称为严格二叉树。哈夫曼编码 对字符集编码时，要求字符集中任一字符的编码都不是其它字符的编码前缀，这种编码称前缀码。字符出现频度与码长乘积之和称文件总长；字符出现概率与码长乘积之和称平均码长；使文件总长或平均码长最小的前缀码称最优前缀码利用哈夫曼树求最优前缀码，左为0，右为1。编码平均码长最小；没有叶子是其它叶子的祖先，不可能出现重复前缀。第七章 图 1、图的定义和术语 图：图G是由顶点集V和边集E组成，顶点集是有穷非空集，边集是有穷集；G中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G中每条边都没有方向的称无向图。顶点n与边数e的关系：无向图的边数e介于0n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于0n(n-1)之间，有n(n-1)条边的称有向完全图；无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和。所有图均满足：所有顶点的度数和的一半为边数。图G（V，E），如V是V的子集，E是E的子集，且E中关联的顶点均在V中，则G(V,E)是G的子图。路径，简单路径：序列中顶点不重复出现的路径。回路，简单回路：序列中第一个顶点和最后一个顶点相同的路径。在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；极小连通子图为此连通图的生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。树图：其本质特征是连通性和无圈性，把不含圈的无向连通图称为树图。将图中每条边赋上权，则称带权图为网络。 2、图的存储结构 1）邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。无向图是对称矩阵；有向图行是出度，列是入度。2）邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstedge,并顺序存储在一个向量中；vertex保存顶点信息，firstedge保存邻接表头指针。邻接矩阵表示法与邻接表表示法的比较：1）邻接矩阵是唯一的，邻接表不唯一；2）存储稀疏图用邻接表，存储稠密图用邻接矩阵；3）求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；4）判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)；5）求边数e，邻接矩阵耗时为O(n2)，与e无关，邻接表的耗时为O(e+n)； 3、图的遍历 1）图的深度优先遍历：类似与树的前序遍历。按访问顶点次序得到的序列称DFS序列。对邻接表表示的图深度遍历称DFS，时间复杂度为O(n+e); 对邻接矩阵表示的图深度遍历称DFSM，时间复杂度为O(n2);2）图的广度优先遍历：类似与树的层次遍历。按访问顶点次序得到的序列称BFS序列。对邻接表表示的图广度遍历称BFS，时间复杂度为O(n+e); 对邻接矩阵表示的图广度遍历称BFSM，时间复杂度为O(n2); 4、图的应用 生成树：连通图G的一个子图若是一棵包含G中所有顶点的树，该子图称生成树。有DFS生成树和BFS生成树，BFS生成树的高度最小。非连通图生成的是森林。最小生成树：将权最小的生成树称最小生成树。（是无向图的算法）普里姆算法：1）确定顶点S、初始化候选边集T0n-2；formvex|tovex|lenght2）选权值最小的Ti与第1条记录交换；3）从T1中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；4）选权值最小的Ti与第2条记录交换；5）从T2中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；6）重复n-1次。初始化时间是O(n),选轻边的循环执行n-1-k次，调整轻边的循环执行n-2-k；算法的时间复杂度为O(n2)，适合于稠密图。克鲁斯卡尔算法：1）初始化确定顶点集和空边集；对原边集按权值递增顺序排序；2）取第1条边，判断边的2个顶点是不同的树，加入空边集，否则删除；3）重复e次。对边的排序时间是O(elog2e)；初始化时间为O(n)；执行时间是O(log2e)；算法的时间复杂度为O(elog2e)，适合于稀疏图。路径的开始顶点称源点，路径的最后一个顶点称终点；单源最短路径问题：已知有向带权图，求从某个源点出发到其余各个顶点的最短路径；单目标最短路径问题：将图中每条边反向，转换为单源最短路径问题；单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；所有顶点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；求最短路径：1）从某个源点到其余各点的最短路径；2）每一对顶点之间的最短路径。求从某个源点到其余各点的最短路径的迪杰斯特拉算法：1）初始化顶点集Si,路径权集Di,前趋集Pi；2）设置Ss为真，Ds为0；3）选取Di最小的顶点加入顶点集；4）计算非顶点集中顶点的路径权集；5）重复3）n-1次。算法的时间复杂度为O(n2)。每一对顶点之间的最短路径弗洛伊德算法的基本思想是：从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。若存在，则存在路径vi,vj / 路径中不含其它顶点若,存在，则存在路径vi,v1,vj / 路径中所含顶点序号不大于1若vi,v2, v2,vj存在，则存在一条路径vi, , v2, vj / 路径中所含顶点序号不大于2 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。拓扑排序：对一个有向无环图进行拓扑排序，是将图中所有顶点排成一个线性序列，满足弧尾在弧头之前。这样的线性序列称拓扑序列。1）无前驱顶点优先：总是选择入度为0的结点输出并删除该顶点的所有边。设置各个顶点入度时间是O(n+e)，设置栈或队列的时间是O(n)，算法时间复杂度为O(n+e)。2）无后继的顶点优先：总是选择出度为0的结点输出并删除该顶点的所有边。设置各个顶点出度时间是O(n+e)，设置栈或队列的时间是O(n)，算法时间复杂度为O(n+e)。求得的是逆拓扑序列。关键路径，如何求？整个工程完成的时间为：从有向图的源点到汇点的最长路径。关键活动：该弧上的权值增加将使有向图上的最长路径的长度增加。第八章 查找 1、线性表、有序表的查找及其分析 查找：就是确定一个已给的数据是否出现在某个数据表中。域（字段）：组成记录的每个数据项。关键字：通常记录中总存在某个或某组数据项，它们的值能唯一标识一个记录，这个（组）数据项称为关键字。查找方法：顺序、二分、线性插值、分区，取决于查找表的结构。静态查找表，在等概率查找的情况下；在不等概率查找的情况下，ASLss在 PnPn-1P2P1时取极小值。有序查找表：折半静态查找树表：最优二叉树、次优二叉树。索引顺序表：平均查找长度=查找索引的平均查找长度+查找顺序表的平均查找长度查找插入删除无序顺序表 O(n)O(1)O(n)无序线性链表 O(n)O(1)O(1)有序顺序表 O(logn)O(n)O(n)有序线性链表 O(n)O(1)O(1)静态查找树表 O(logn)O(nlogn)O(nlogn) 2、二叉排序树和平衡二叉树 二叉排序树：如果将记录的键码按二叉树的结构来组织，并且假定树中任意非叶子结点的键码大于其左子树所有结点的键码（若左子树存在的话），而小于其右子树所有结点的键码（如右子树存在的话），这样的二叉树叫二叉排序树（二叉查找树）。查找、插入、删除算法。平衡二叉树：树中每个结点的左、右子树深度之差的绝对值不大于1。构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。B-树：B-树是一种平衡的多路查找树。在含N个关键字的B-树上进行一次查找，需访问的结点个数不超过logm/2 (N+1)/2)+1B+树：B+树是B-树的一种变种。 每个叶子结点中含有n个关键字和n个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点； 每个非叶结点中的关键字Ki即为其相应指针Ai所指子树中关键字的最大值； 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 和m之间。查找过程：在B+树上，既可以进行缩小范围的查找，也可以进行顺序查找；在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；若在结点内查找时，给定值Ki，则应继续在Ai所指子树中进行查找。哈希查找： 3、散列（Hash）表的定义，Hash函数的构造方式、冲突处理和Hash表的查找及其分析 哈希函数：能把关键字映射成记录存贮地址的函数。哈希表：假定数组HT0m-1为存贮记录的地址空间，哈希函数H以每个记录的关键字值K作为输入，产生一个落在0m-1内的整数H（K），并以它作为K所标识的记录在表HT中的地址或索引号，这样产生的记录表H（K）叫做 构造哈希函数的方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。冲突处理：开放定址法：线性探测再散列、二次探测再散列、伪随机探测再散列再哈希法链地址法建立一个公共溢出区第九章 内部排序 1、排序的基本概念 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。排序文件中有相同的关键字时，若排序后相对次序保持不变的称稳定排序，否则称不稳定排序；排序算法的基本操作：1）比较关键字的大小；2）改变指向记录的指针或移动记录本身。评价排序方法的标准：1）执行时间；2）所需辅助空间，辅助空间为O(1)称就地排序；另要注意算法的复杂程度。2、各种排序方法及其分析 插入类：将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。1）直接插入排序（基于顺序查找）算法中引入监视哨R0的作用是：1）保存Ri的副本；2）简化边界条件，防止循环下标越界。关键字比较次数最大为(n+2)(n-1)/2；记录移动次数最大为(n+4)(n-1)/2；算法的最好时间是O(n)；最坏时间是O(n2)；平均时间是O(n2)；是一种就地的稳定的排序；2）折半插入排序（基于折半查找）3）表插入排序（基于链表存储）4）希尔排序（基于逐趟缩小增量）实现过程：是将直接插入排序的间隔变为d。d的取值要注意：1）最后一次必为1；2）避免d值互为倍数；关键字比较次数最大为n1.25；记录移动次数最大为1.6n1.25；算法的平均时间是O(n1.25)；是一种就地的不稳定的排序；交换类：通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。1）冒泡排序实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。关键字比较次数最小为n-1、最大为n(n-1)/2；记录移动次数最小为0，最大为3n(n-1)/2；算法的最好时间是O(n)；最坏时间是O(n2)；平均时间是O(n2)；是一种就地的稳定的排序；2）快速排序实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较，有交换后,交换j，i。i=j时确定基准，并以其为界限将序列分为两段。重复以上步骤。关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2；算法的最好时间是O(nlog2n)；最坏时间是O(n2)；平均时间是O(nlog2n)；辅助空间为O(log2n)；是一种不稳定排序；选择类：从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。1）简单选择排序实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。关键字比较次数为n(n-1)/2；记录移动次数最小为0，最大为3(n-1)；算法的最好时间是O(n2)；最坏时间是O(n2)；平均时间是O(n2)；是一种就地的不稳定的排序；2）树形选择排序锦标赛排序3）堆排序实现过程：把序列按层次填入完全二叉树，调整位置使双亲大于或小于孩子，建立初始大根或小根堆，调整树根与最后一个叶子的位置，排除该叶子重新调整位置。算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；是一种就地的不稳定排序；归并类：通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。1）归并排序实现过程：将初始序列分为2个一组，最后单数轮空，对每一组排序后作为一个单元，对2个单元排序，直到结束。算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；辅助空间为O(n)；是一种稳定排序；基数排序：多关键字的排序、链式基数排序。实现过程：按基数设置箱子，对关键字从低位到高位依次进行箱排序。算法的最好时间是O(d*n+d*rd)；最坏时间是O(d*n+d*rd)；平均时间是O(d*n+d*rd)；辅助空间O(n+rd)；是一种稳定排序；各种内部排序方法的比较和选择：按平均时间复杂度分为：1) 平方阶排序：直接插入、直接选择、冒泡排序；2) 线性对数阶：快速排序、堆排序、归并排序；3) 指数阶：希尔排序；4) 线性阶：基数排序。平均时间最坏情况辅助存储简单排序O(n2)O(n2)O(1)快速排序O(nlogn)O(n2)O(logn)堆排序O(nlogn)O(nlogn)O(1)归并排序O(nlogn)O(nlogn)O(n)基数排序O(d(n+rd)O(d(n+rd)O(rd)选择合适排序方法的因素：1)待排序的记录数；2)记录的大小；3)关键字的结构和初始状态；4)对稳定性的要求；5)语言工具的条件；6)存储结构； 7)时间和辅助空间复杂度。结论：1) 若规模较小可采用直接插入或直接选择排序；2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序；3) 若规模较大可采用快速排序、堆排序或归并排序；4) 任何借助于比较的排序，至少需要O(nlog2n)的时间，基数排序只适用于有明显结构特征的关键字；5) 有的语言没有提供指针及递归，使归并、快速、基数排序算法复杂；6) 记录规模较大时为避免大量移动记录可用链表作为存储结构，如插入、归并、基数排序，但快速、堆排序在链表上难以实现，可提取关键字建立索引表，然后对索引表排序。第十章 外部排序 1、外存信息存取的基本概念 外部排序由相对独立的两个步骤组成：1）按可用内存大小，利用内部排序方法，构造若干( 记录的) 有序子序列，通常称外存中这些记录有序子序列为