《按照大纲的知识点整理----数据结构.docx》由会员分享，可在线阅读，更多相关《按照大纲的知识点整理----数据结构.docx（18页珍藏版）》请在课桌文档上搜索。
1、一、线性表（一）线性表的定义和根本操作（二）线性表的实现1 .顺序存储结构2 .链式存储结构3 .线性表的应用二、栈、队列和数组（一）栈和队列的根本概念循环队列:为了克服假溢出时移动元素的缺点.循环队列的入队操作：先输入,后加尾指针.循环队列的出队操作：先取数据,后加头指针.队列中元素个数（如同补码原理）rear-front,rear-front0（rear-front+maxsize）%maxsize,rear-front0判断队列的空与满：另设置一个标志位以区别队列是空还是满少用一个元素的空间，约定以“队列头指针在队列尾指针的下一位置上”作为队列呈满状态的标志Qfgt=Qg空.小Q.fro
2、nt=（Q.rear+1）%maxsize,?两因此循环队列中少用一个位置.实际大小为maxsize1（线性存储的情况）（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储对称矩阵:%a=ajide特殊矩阵三角矩阵:0bf00c一a0O-对角矩阵:0b000C如果是上三角矩阵,那么的位置k=i*（i+l）2+j如果是下三角矩阵,那么力的位置k=j*（j+l）2+j,下三角与上三角互相对称的原理.行优先存储：将数组元素按行向量排列开始地址为:loc(0,00)列优先存储：三、树与二叉树/*树有且只有一个根结点，二叉树有0个或1个根结点(一)树的概念
3、(二)二叉树1.二叉树的定义及其主要特征空二叉树(2)只有根节点的二叉树二叉树的五种类型(3)没有左子树的二叉树(4)没有右子树的二叉树(5)同时有左右子树的二叉树2 .二叉树的顺序存储结构和链式存储结构3 .二叉树的遍历(1)二叉树的递归遍历A.前序B.中序C.后续(2)二叉树的非递归遍历A.前序B.中序C.后序i. 双栈ii. 栈中存标志位的方法iii. 除了栈只用一个指针变量的方法uoidpostorder(bitreebt)bitree*p=null,lastUiSit=null;/*IaStUiSit指向最后访问节点，用于判别右子树是否已经访问WStackst;InitStack(S
4、t);push(st,bt);Mhile(tStackempty(st)lchild?=null)push(st,p-lchild);p=p-lchild;/*此时P指向最左节点*/while(p-rchild=nullp-rchild=lastuisit)&p?=null)lastuisit=pop(st);printf(,%d,lastuisit-data);p-getStack(st);if(p-rchildfnull)push(st,p);*while*postorder*/(3)二叉树的层次遍历4 .线索二叉树的根本概念和构造5 .二叉排序树空树定义(2)1）若左子树不空，则左子树上
5、结点的值均小于根节点的值2）若它的右子树不空，则右子树上结点的值均大于根结点的值3）它的左右子树分别为二叉排序树6.平衡二叉树空树（2）它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1（三）树、森林1.树的存储结构(1)双亲表示法以一组连续空间存储树的结构，同时在每个结点中附设一个指示器指示其双亲结点在链表中位置。孩子表示法顺序与链式相结合的方式datafirstciIdBCDI23（3）孩子兄弟表示法（也即，二叉链表表示法）.占.名吉才句;贵工-LcliAldclgIAn仪trypeder-ctCySTcdcfRIoI-TlClata;SJ-UCfUSZQdeM长
6、lrstChIle1,矢me:XtSibIiKk皂二USlSrOCIGsfcOSTioo;2.森林与二叉树的转换由森林车争换成二文树的转-按规则为：若F=力，WdB=否则由KOO(T1)又才应彳导至UNUe(rct):由(*11，七2tlll)采上应彳导组JLBT二由(T2,T3,.Tn)走十应彳导至URBTO由二又柑专学演为乐和KMT左拳按ML贝U为：若B=e_刎F=cr1吉贝”，r7No.1由LBT.又十应彳寻3JLr.,tLm)i1.7RHTr又十应彳寻壬UT2,T3,.,T.Jo17止匕、才对开D.而和卜合勺餐手中才柒彳乍上勺f-与二攵韦寸合勺多科格彳乍才白乂寸庐应5主意自W是、于7枳
7、寸又寸应臼勺歹一机匕-兵左、右子彳对白勺柢C会已吱变为二左是拔子，后是亢羊将一棵树转换为一叉树的思路,主要根据树的孩子兄弟存储方式而求的,方法是：（Ij树中所方相邻兄弟之间加一条连线J（2）对树中的每个结点，只保K/其与第一介孩子结点之间的连线.删去其与其它孩子结点之间的连线J（3以树的根结心为铀心，杓监探树顺时针除转一方的fl?度，使Z结构层次分明U切以证明，树做武样的转换所构成的叉树是唯一的。2 .森林转换为二义树森林是若十棵树的集合.招可以转换为二叉树，森林同样也可以转换为一叉树。因此，森林也可以力便地用孩子兄弟登去去示,森林转换为二叉树的方法如下：（1）将森林中的每棵树转换成相应的_叉
8、树.（2）第一棵二叉利不动，从第二棵二叉树开始，依次把后一棵叉树的根结点作为前一棵叉树根结点的石孩子当所有二叉树连在一起后，所得到的二叉树就是由森林转换;得到的一叉树.3 .树和森林的遍历比才艮（次存）遍历：若树不空，则先访问才艮结点，然后代次先?艮遍_历各择于枳to后才艮（次序）通历:若木对不空，则先住次后才艮边历备择子树,然后访问才艮结忐一4屋历：若树不空，则奉上而下自主至右访问树中多个结，点、C森林可以分解成三部分:1o森4z卡中第棵树的方艮结点；2。森林中第一根树的子树森林；3。赤林中其它树构成的森X木C树先根遍历后根遍历森林二叉树先手遍历先号遍历中序遍历中声遍历(四)树的应用1 .等
9、价类问题2 .哈夫曼(Huffman)树和哈夫曼编码(1)每次合并权值最小的和次小的.(2)排列时权值左小右大四、图(一)图的概念图中的数据元素为顶点(VerteX),V是顶点的有穷非空集合;VR是两个顶点之间的关系的集合.假设u,w属于VR,那么u,w表示从U到w的一条弧(ArC),且称为弧尾或初始点,w为弧头或终端点,此时的图称为有向图.无向图:以(U,w)表示,w之间的一条边.用G=(V,E)表示图.用n表示图中顶点数目,用e表示边或弧的数目.对于无向图,叫边.对有向图,叫弧对于无向图：0e(一1)1z八-nn-)无向完全图：有2条边对于有向图Oen(n-1)有向完全图:有ST）边的有向
10、图.稀疏图:有很少条边或弧的图.反之称为稠密图.边上的权:表示从一个顶点到另一个顶点的距离或消耗.网：带权的图如果两个顶点之间直接有边相连那么这两个顶点互为临接点.度:和顶点相关联的顶点的数目.入度：以某顶点为头的弧的数目称为该顶点的入度.出度：以某顶点为尾的弧的数目称为该顶点的出度.度=入度+出度路径：从某顶点到另一个顶点的顶点序列.路径的长度:路径上边或弧的数目.回路或环:第个顶点和最后一个顶点相同的路径.简单路径:序列中顶点不重复出现在无向图中：如果从顶点V到顶点W之间有路径,称V和W是连通的.如果图中任意两点都是连通（即任意两点之间都有路径相通）的,那么称G是连通图.连通分量：无向图中
11、的极大连通子图极大连通子图:在原来图的根底上（即包括原来图的所有顶点和边（弧）拥有最多的边数和最多的顶点数的图.一个连通图的生成树是一个极小连通子图.它含有图中全部顶点,但只有足以构成一颗树的n-1条边.如果在一个生成树上添加一条边必定构成i个环.非连通图：有n个顶点和小于n-1条边有n个顶点和大于n-1条边的图肯定有环.但是有n-1条边的图不一定是生成树.在有向图中：如果对任意两个顶点之间都存在一条有向路径,那么称G是强连通图.极大连通子图称为强连通分量.如果一个有向图恰有一个顶点的入度为0,其余定点的入度均为1,那么是一颗有向树.一个有向图的生成森林由假设千颗有向树组成.含有全部顶点,但只
12、有足以构成假设千颗不相交的有向树的弧.（二）图的存储及根本操作1 .邻接矩阵法2 .邻接表法对图中每个顶点建立一个单链表,第i个单链表中的节点表示依附于顶点V的边（对有向图是以定点V为尾的弧）.每个节点由三个域构成.Adjvex与顶点V邻接的点在图中的位置Nextarc下一条边或弧的节点Info权值等每个链表上附设一个表头结点.DataFirstarc指向链域这些表头节点通常以顺序结构的形式存储.为了便于确定有向图中定点的入度.建立有向图的逆链接表.在建立邻接表或逆邻接表时,假设输入的定点信息即为顶点的编号,那么建立临界表的时间复杂度为O（n+e）,否那么需要通过查找才能得到顶点在图中的位置,
13、那么时间复杂度为O(n*e).优点：找任意顶点第一个邻接点和下一个邻接点容易缺点：判定两个顶点是否有边或狐不比邻接矩阵方便(三)图的遍历为了防止同一-顶点被访问屡次,设个辅助数组ViSited0.n-l,初始值为0.以下两种搜索对无向图和有向图都适合.1.深度优先搜索类似于树的先根遍历算法描述：初始状态是图中所有顶点都未被访问从图中某个顶点V出发,访问此定点,然后依次从V的未被访问的邻接点出发深度优先遍历图,直至图中所有和V有路径相通的顶点都被访问到；如此时图中尚有顶点未被访问,那么另选图中一个未曾被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问到为止.BleanvisitedMax
14、;voidDFSTraverse(GraphG,Status(*Visit)(intv)VisitFunc=Visit;for(v=o;vGvexnum;+v)visitedv=FALSE;for(v=o;v=0;W=NeXtAdjVeX(GV,w)其中FirstAdjVex函数作用是获得第V个节点的第一个边if(!visitedw)DFS(G,w);Status(*VisitFunc)(intv);函数变量是一个静态分配的指针Vis计FUrIC,指向一个函数，该函数带一个int型的参数。ViS计FUnC=Visit;使用全局变量VisitFunc,使DFS不必设函数指针参数。使之前定义的函数
15、指针指向ViSit函数，ViS计FUnC是全局变量，故在深度优先搜索DFS中不必再定义函数指针参数，直接调用ViSitFUrIC函数即可，也就是ViSit函数。当用二维数组表示临界矩阵作图的存储结构时,查找每个顶点的邻接点所需时间为.其中n为图中顶点数.而当以邻接表作图的存储结构时,找邻接点所需时间为O(e).其中e为无向图中边的数或有向图中弧的数.因此,当以邻接表作存储结构时,深度优先搜索遍历图的时间复杂度为O(n+e).2 .广度优先搜索类此于树的按层次遍历的过程.算法描述：从图中某顶点V出发,在访问了V之后依次访问V的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问他们的邻接点,
16、并使“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有以被访问的顶点的邻接点都被访问到.假设此时图中尚有顶点未被访问,那么另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止.为了顺次访问路径长度为2、3、的顶点,需附设队列以存储以被访问的路径长度为1、2、.的顶点.(四)图的根本应用及其复杂度分析1 .最小(代价)生成树(极小连通子图)最小生成树MST性质：假设N=(V,E)是一个连通网,U是顶点集V的一个非空子集.假设(u,v)是一条具有最小权值(代价)的边,其中U属于U,V属于V-U,那么必存在一颗包含边(u,v)的最小生成树.Prim算
17、法和Kruskal算法是两个利用MST性质构造最小生成树的算法.Prim算法:假设N=(V,E)是连通网,TE是N上最小生成树中边的集合.算法从U=uo)(uo属于V),TE=卜开始，y重复执行下述操作:在所有U属于U,v属于V-U的边(u,v)属于E中找一代价最小的边(uo,vo)并入集合TE,同时U0并入U,直至U=V为止.此时TE中必有n-1条边,那么T=(V,TE)为N的最小生成树.2 .最短路径1)从某个源点到其余各顶点的最短路径2)每一对顶点之间的最短路径3 .拓扑排序顶点表示活动AOV网.4 .关键路径边表示活动网一AOE网(ACtiVityOnEdge)的概念：AOE网是一个带
18、权的有向无环图.定点表示事件,弧表示活动,权表示活动持续的时间.AOE网用来估算工程的完成时间.AOE网(边表示活动网)：最早开始时间e(a。=+选大者最迟开始时间1出)二选小者/*最迟开始时间：不推迟整个工程完成的前提下,活动比最迟必需开始进行的时间*/*关键活动不是顶点:答题时应注意*/产关键路径为最早开始时间=最迟开始时间的顶点之间的活动构成*/*关键路径是通过事件求活动.*/*关键路径有多个：如：a2a3a4a5aa2a6a7a5其中aa2a5的工期减少会使整个工程缩短工期*/*完成工程的最短时间是从开始点到完成点的最长路径长度*/*开始点为Vi从Vi的最长路径为Vi最早发生时间*/五
19、、查找(一)查找的根本概念(二)顺序查找法无序表和有序表的顺序查找(1)无序表“，+1ASL=2查找失败时和给定值进行比拟的关键字个数为n+1个2_如果查找成功与不成功的可能性相同,那么/*乘5的原理*/13AS七SS=y(+l)+(+l)=(+l)2(=124(2)有序表查找成功时“，+1ASL=2查找不成功时ASIl=-2(三)折半查找法折半查找性能分析(1)(2)平均查找长度为ASLbs=-D-I折半查找只适用于有序表且限于顺序存储结构有序表上折半查找时判定树的高度为|_噫_|+1(因这跟完全二叉树深度一样|_隰1+1)(四)B-树:平衡的多路查找树空树树中每个节点至多有m棵子树(2)若
20、根节点不是叶子节点，则至少有两棵子树除根之外的所有非终端结点至少有-棵子树一颗m阶的B树.2(4)所有非终端结点中包含:(n,o,K1,i,K2,A2.,K,An)勺为关键字。勺Ai所指关键字均大于却均小于山川WZ)为关键字个数(5)所有叶子节点在同一层次上，并且不带信息B+树.与B树的差异：(1)有n棵子树的结点有n个关键字(2)所有的叶子节点中包含了全部关键字信息.及指向这些关键字记录的指针.并且,叶子结点本身依关键字的大小自小而大顺序链接.(3)所有非终端结点可看成索引局部,节点中仅含其子树中的最大关键字.(五)散列(Hash)表及其查找哈西函数标准:映像到地址集合中任何一个地址的概率是
21、相等的./*聚集:冲突发生以后相同位置的记录聚集到一块*/*二次聚集:由非同义词冲突产生*/*发生聚集原因:哈西函数选择不当*/*在哈西法能有效防止冲突装填因子二表中填入的记录个数哈西表长度(六)查找算法的分析及应用六、内部排序(一)排序的根本概念(二)插入排序1 .直接插入排序2 .折半插入排序(三)气泡排序(bubblesort)如果一趟排序中未发生交换,那么说明已结束(四)简单项选择择排序(五)希尔排序(shellsort)(六)快速排序(七)堆排序假设在输出堆顶的最小值之后,使得剩余n-1个元素的序列又重建成一个堆,那么得到n个元素中的次小值.如此反复执行,便能得到一个有序序列.把待排
22、序列假设成完全二叉树（1）建堆从无序序列建堆的过程为反复筛选的过程.从最后一个非终端节点即l112-j开始”筛选”.（2）输出堆顶元素后调整堆1）输出堆顶元素后,以堆中最后一个元素替代.2）自上至下进行调整.此过程称为“筛选二（八）二路归并排序（mergesort）（九）基数排序（十）各种内部排序算法的比拟（十一）内部排序算法的应用根本概念和术语数据:是对客观事物的符号表示,在计算机科学中表示所有能输入到计算机中并被计算机程序处理的符号总称.数据元素:是数据的根本单位,在计算机程序中作为一个整体考虑.数据元素由假设十数据项组成数据对象:是性质相同的数据元素的集合.是数据的个子集.数据结构:相互
23、之间存在一种或多种特定关系的数据元素的集合.结构包括:集合、线性结构、树形结构、图状结构.数据结构描述元素间逻辑关系.在计算机中bit是信息的最小单位.位串表示数据元素.（8位二进制表示一个字节）抽象数据结构E数据项计算机 存储结构数据机构今算法设计存储结构今算法实现数据类型:是一个值的集合和定义在这个值集上的一组操作的总称.抽象数据类型:原子类型、固定聚合类型、可变聚合类型（值的成分数目不确定）抽象数据类型表示与实现类C语言（预定义#definetrue1(2)数据结构的表示(typedef)(3)根本操作的算法函数类型函数名(函数参数表)算法说明语句序列)函数名算法(控制结构+原操作)定义
24、：(algorithm)是对特定问题求解步骤地种描述。它是指令的有限序列。特点：(1)有穷性(2)确定性(3)可行性(4)输入(5)输出根本要求：(1)正确性(2)可读性健壮性(4)较高效率与低存储需求算法效率度量(1) 事后统计的方法(2) 事前分析估算算法时间复杂度的表示：f(n)：n为问题规模n的某个函数T(n)=0(f(n)算法执行时间T(n)的增长率和f(n)增长率相同渐进时间复杂度一一时间复杂度频度：语句重复执行的次数0(1),0(n000(2)算法原地工作：算法所需的辅助空间不依赖问题的规模n。算法执行效率：时间复杂度：空间复杂度：_n(n+l)y2n=o(4n)-2一相当于。(
25、1)排序排序算法与待排序列初始状态1 .排序趟数与数列原始状态有关的算法：交换排序(起泡、快速)起泡排序结束的条件为在一趟排序中没有进行过交换记录的操作.2 .二路归并排序和简单项选择择排序的比拟次数与序列初态无关一、插入排序：待排记录分两组,一组有序,一组无序,每次从无序组中取出一个记录插入到有序组,使有序组依然有序.直接插入排序算法思想：(1)将待排记录分为rl,il,ri,n.前一子区间已排好序,后一区间为初始未排序状态.(2)依次将后一子区间的第一个元素插入到前一子区间,每次插入完毕后i+1直到in(3)分类过程从i=2开始,初始rl只有一个元素,可认为是有序的.(4)第i趟直接插入排
26、序操作为:自i-1起往前搜索,(可同时后移记录),当rk-lrirk时停止(5)可设置监视哨(防止每次验是否出界)voidInsertSort(Sqlist&L)for(inti=2;iL.length;i+)1.listO=L.listi;1.listi=L.listi-l;for(intj=i-1;LT(L.listO,L.listj)!=Oy)/LT(a,b)当ab时返回true1.listj+l=L.listj;1.listj+l=L.listO;I)endInsertSort希尔排序(缩小增量排序)算法思想：先将整个待排记录序列分割成为假设干子序列分别进行直接插入排序,待整个序列根本
27、有序时,再对全体记录进行一次直接插入排序,待整个序列根本有序时在对全体序列进行一次直接插入排序.(这样在最后一趟排序时只需作记录的少量比拟和移动即可完成排序).算法实现：/shellinsertvoidShellInsertCSqlist&L,intdk)前后记录位置的增量为dk,而不是1r0只是暂存单元，不是哨兵。当j=0时插入位置已经找到for(inti=dk+1;iO<(L.listO,L.list|j);j-=dk)1.listj+dk=L.listj;1.listj+dk=L.listO;)endShellInsertvoidShellSort(Sqlist&L,intdlta,
28、intt)for(intk=O;kt;k+)ShellInsert(L,dltak);)endShellSort其中C语言知识for(i=0;i10;i+)中最后一个语句i+每次在循环中的语句结束后执行.特点:子序列的构成不是简单的“逐段分割”,而是相隔某个增量的记录组成一个序列,并在子序列内进行直接插入排序.时间复杂度(平均和最坏)空间复杂度。),稳定性：不稳定增量:应使增量序列中的值没有除一致外的公因子，并且最后一个增量值必须1.分成了很多子序列,但不能试图并行处理这些子列,因只适合串行.每一个字序列的元素或许是别的子序列的元素.二、选择排序每一趟在n-i+1个记录中选取关键字最小的记录作
29、为有序序列中第i个记录简单项选择择排序一趟简单项选择择排序的操作：通过n-i次关键字间比拟，从n-i+1个记录中选出关键字最小的记录，并和第i(l=i=n)个记录交换。/SelectSortvoidSelectSort(Sqlist&L)for(inti=l;iL.length;+i)j=SelectMinKey(L,i);if(i!=j)L.listi与L.lisj交换)endSeIectSort时间复杂度OS)(最坏好)空间复杂性记录移动次数较少0=x=3(n-l).特点：无论记录初始排列如何，所需关键字间比拟次数都相同。加：kjb化&V堆排序：定义:n个元素序列化%或上/那根本思想：1、
30、如何在输出堆顶元素之后，调整剩余元素成为一个新堆(1)假设输出堆顶元素之后，以堆中最后一个元素替代之。(2)自上之下调整，根与其左右孩子大者(小者，由小到大排列时)进行交换在被破坏“堆”中进行与相同的调整，直到叶子节点2、如何从无序序列建成一个堆L2个元素开始“筛选”。时间复杂度最坏O(nlogn)(最好，坏，平均)空间复杂度O(1)适应性：对n较大的文件有效，时间主要消耗在建初始堆和调整建新堆时进行的反复“筛选”上。比拟次数之多为4n,其中n为堆中所含元素。稳定性：不稳定特点：每个待排记录尽占一个存储空间选择排序移动次数为O(n)同大(小)顶堆中关键字最小(大)的在叶子节点上，故必须在L2大
31、的位置上。三、归并排序：四、交换排序：五、各种排序法适用性基数排序：适用于n值很大而关键字较小的序列直接插入排序假设待排记录序列为按关键字根本有序时时间复杂度可提高至0(n);堆排序属于选择排序,故每次从待排序列中迭出最大或最小的元素.如果想得到最大k个或最小k个元素,那么用之.而对记录数小的序列不适用.快速排序在关键字根本有序时最不利于发挥长处.(课p276)移动次数与比拟次数.而比拟次数最多简单项选择择排序无论初始排列如何,比拟次数均n(n-l)2,即0().交换:堆排序时间复杂度O(lg),比拟次数不超过2R)g1n2直接插入排序的比拟和移动次数均为4折半插入排序比直接插入排序,关键字间
32、比拟次数减少了.因每趟进行n个比拟,一共1g趟.两个各有n个数据的有序表归并成一个有序表最少比拟次数为n次直接插入排序中被排序列初始根本有序时可减少比拟和移动次数.排序算法平均时间复杂度空间复杂度稳定性移动次数比拟次数选择排序最少，根本上O(n)归并排序OSlog,)好,坏,平均O(n)稳定归并的趟数g入树的深度)各种排序算法稳定性分析：稳定的有：1 .直接插入.因每次从未排队列中按顺序选取插入,故值相同,元素前后顺序不变.2 .起泡排序：因每次选取未排局部的最大(最小)元素,且这是按顺序取得3 .折半插入4 .归并排序5 .基数排序各种算法的时间复杂性：0(1):直接插入排序、起泡、折半插入
33、、直接选择.希尔、快速排序、堆排序、归并.(注意：其中堆排序中删除一个元素时间复杂度为也即一次调整堆的时间)O(d(n+r):基数排序其中,直接插入最好情况O(n),起泡排序最好O(n)快速排序最坏情况0().各种算法空间复杂性：0(1):插入排序均是,选择排序O(n)归并排序O(n+r):基数0(lg,)快速排序,需要个栈的存储空间,最坏情况下0(n),此时,枢轴位置偏向一侧,如,想防止最坏情况那么必须先对长度短的子序列进行排序.查找哈希表(从关键字找到存储位置)哈希函数的构造方法：1 .直接定址法H(key)=key或H(key)=akey+b2 .数字分析法3 .平方取中法4 .折叠法5
34、 .除留余数法6 .随机数法处理冲突的方法取关键字的假设十数位组成哈希地址。(尽量防止冲突)关键字进行平方运算后取中间几位为哈希地址。将关键字分割成位数不同的几局部(最后一局部位数可以不同)然后取这几局部叠加和(舍去进位)H(key)=keyMODP,P=mP为小于等于表长的最大素数开放定值法Hi=(Zey)+diModtn其中4的取值为：(1) 线性探测再散列4=1,2,3,k(2)二次探测再散列4=匕T22,-22,3?,.r,(-2)(3)4=伪随机数列2.Hj=RHj(key)日,.kA”，均为不同的哈希函数,同义词产生地址冲突时计算另一个哈希函数地址.直到冲突不再发生.益:不宜产生“
35、聚集”缺：计算时间增加了3.链地址法：将关键字为同义词的记录存储在同一线性链表中。4.建立一个公共溢出区一旦有冲突那么填入溢出表。堆排序小根堆中,关键字最大的纪录有可能在大于周的位置上,也即二路归并排序的辅助存储空间为O(n).比拟次数051g快速排序的辅助空间为O(log211)比拟次数为O(Dlog2。)快速排序算法在待排纪录根本有序时最不利于发挥作用,甚至有时会出现相反现象(效率下降)快速排序中要注意找界限区分选择排序和起泡排序时要进一步排序,从实际得出结论二路归并和简单项选择择排序的比拟次数与待排序列初态无关起泡排序结束的条件为一趟排序中没有进行过交换记录的操作.比拟趟数与数列原始状态有关的算法：交换排序(起泡、快速)
