数据结构期末复习知识点兼容版

1、数据结构期末复习复习要点：第一章1 .相关基本概念：数据、数据元素（基本单位）、数据项（最小单位）、算法及其特征等； 数据：所有能输入到计算机中并被计算机程序处理的符号总称。 数据元素：基本单位。 数据项：最小单位。 算法特征（5点）：有穷性；确定性；可行性；输入；输出。2 .逻辑结构、存储结构（物理结构）及其类型；逻辑结构有四种基本类型：集合、线性结构、树形结构和网状结构。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。注：期中考题目数据结构分为两大类，即为逻辑结构和存储结构。其中逻辑结果又分为线性结构和非线性结构，存储

2、结构一共有四种（顺序、链接、索引、散列）。3 .算法分析：语句频度（执行次数）计算、时间和空间复杂度分析。表示方法 语句频度：直接写次数。 时间复杂度：0（执行次数），如：O（n）o 空间复杂度：0（所需空间）第二章1213212428304277123456781.顺序表（数组）插入、删除、有序表合并算法及其移动次数计算；序号12345678表示L.elem01234567顺序表插入算法思想：如果要在序号5前插入元素e,需要将序号58向后移动一个位置。移动次数为4次，公式n-i+1StatusListInsert_Sq(SqList&L.inti,ElenTypeej在第i个元素前插

3、入新元素3当前i为5if(i<111i>L-length+1)returnERROR;/i值不合丫去if(L.length>=L.listsize)当前存储空间已满，增加分配<ElemType*newbace=(ElemType*)realloc(L.elenij(L-listsize+LISTIHCREMENT)*sizeof(ElemType);if(fnewbace)returnERROR;L.elea=neibace;L-listsize+=LISTIHCREMENT；ElemType*p;ElemType*q=&(L.elen»i-1);/序

4、号5对应L.elEmgfor(p=&(L.elemL.length-1);p>=q;p)表长L.length值为8,P揖向序号也对应L®pc7*(P+D=*P；"元素后移*1=序号5对应L.elgm叼赋值为e*+L.length;returnOK;顺序表删除算法思想：如果要删除序号5元素，需要将68依次向前移动一位移动次数为3次，公式n-istatusListDeiete_Sq(SqList&L.inti,ElenTupete)删除第i个元素，并用。返回其值，当前i为5<if(1<1|i>L.length)returnERROR;/i

5、值不合法ELcmType*p=&(!_.£电mi-1);"P为被删除元素检置-*P；被删除元素的值赋值给eElenTt|pe*q=L.elem+L.length-1;表尾元素位置Llem叼+7,为L-Uem7for(+p；p<=q；+p)P先移到序号叫判断是查公于q*(p-1)=*p；元素前移-L.length;表长减1returnOK;有序表合并LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)则LC=(2,3,5,6,8,8,9,11,11,15,20)算法思想(以非递减为例)：La和Lb非递减排列，La与Lb中元素逐个比较，较小的先插入

6、Lc中。注：非递减是指递增排序，但元素有可能相等，与之相对的有非递增排序。移动次数为(La.length+Lb.length)voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)/需爵线性表呼Lb的元素按值非递减排列.归并门和Lb得到新的顺序线性表L*Lc的元素也按值非递减排列。Elemlype*pa,*pbf*pcf*pa_last,*pb_last;pa=La.elem;pb=Lb.elem：Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElenType*)malloc(Lc,lis

7、tsize*sizeoF(EleinT|fpe);"p嗡向if(*Lc.elem)exitCOUERFLOW);/存储分配失败_pa_last=La.elem+La.length-1;“paj4只指向La最后一个元素pblast=Lb.el&mLb.length-1;/pb指向Lh最后一个元素iihile(pa<-palast&&pb<=pblast)</归并if(*pa<=*pb)*pc+=*pa+;如第PH当前宿不于pb当前值，pc当前位置的值赋值为pc当前值else*pc+=*pt)+;>_while(pa<=pa_l

8、ast)«pc+*-*p3*+;/每入La的剩余元塞while(pb<=pb_last)*pc+*=*pb+；/插入LD的剩余元素这两个岫i12语句只会执行其中一个/MergeList2.链表（有无头节点、单双、循环）插入（前、后）、删除（前、本身、后）的指针挂接、建立（不带头节点）算法。单链表每个节点有数据域和指针域datanextm头ala2a3a4a5a6带头节点L-JinJZELEDJZELEELLHPTala2a3a4a5a6不带头节点L-匚一匚匚I一匚口一匚口一匚口一133PT团一口口口口口m单循环链表在P(a3)节点前插入S节点(1)Q=P;先让Q指向a3(2)P

9、=L;/P指向第一个节点(带头结点指向头结点，不带头结点指向al)(3)while(P->next!=Q)P=P->next;/找至Ua3的前驱a2,P指向a2(4)S->next=P->next;/P->next为a3,让S->next等于a3(5)P->next=S;/a2指针域指向节点S 在P(a3)节点后插入S节点(1)S-next=P->next;(2)P->next=S; 删除P(a3)前一个节点(1)Q=P;(2)P=L;(3)while(P->next->next!=Q)P=P->next;/找至Ua1(4

10、)P->next=P->next->next;让a1指针域指向a3,从而删除a2 删除P(a3)节点(1)Q=P;(2)P=L;(3)while(P->next!=Q)P=P->next;/找至Ua2(4)P->next=P->next->next;/让a2指针域指向a4,从而删除a3 删除P(a3)后一个节点(1)P->next=P->next->next;让a3指针域指向a5,从而删除a4双链表每个节点有前驱指针、数据域、后继指针priordatanext双循环链表头a1a2a3a4 在P(a2)节点前插入S节点技巧：先让S

11、->prior和S->next与链表建立关系注：步骤(4)必须在步骤后面(1)S->next=P;/先让S->next指向a2(2)S->prior=P->prior;/S->prior指向a1(3)P->prior->next=S;/再把a1->next指向S(4)P->prior=S;/a2->prior指向S 在P(a2)节点后插入S节点注：步骤(4)必须在步骤(3)后面(1)S->prior=P;(2)S->next=P->next;(3)P->next->prior=S;/a3-&g

12、t;prior指向S(4)P->next=S; 删除P(a2)前一个节点a1(1)Q=P->prior;Q指向要被删除的a1;(2)P->prior=P->prior->prior;/P->priro指向头(3)P->prior->next=P;/头->next指向P(4)free(Q);/释放a1的存储空间 删除P(a2)节点(1)P->next->prior=p->prior;(2)P->prior->next=p->next;(3)free(P); 删除P(a2)后一个节点a3(1)Q=P->

13、next;(2)P->next=P->next->next;/a2->next指向a4(3)P->next->prior=P;/a4->prior=P(4)free(Q);/释放a3存储空间建立(不带头节点)单链表voidCreateList_l(LinkLi.st&l,intn)/建立不带头结点链表LinkListp,q;for(inti=Q;i<n;*+i)p=(LinkList)malloc(sizeoF(LHode);cin»p->(lata；输入数据速p->next=NULL;p当前为最后一个节点IfCl=

14、0)第一个节点continue;不执行后面的语句<|->next=p;让前一个节点next指针指向pq=p;"q指向p读程序：设n为2（i取0,1）dat4i=0时，pTLTqTdata八datai=1时，LTqTpTqTpT第三章1 .栈的进出序列、栈、队列、循环队列的满/空条件；由于栈的插入、删除操作是限制在栈顶进行的，因而后进栈的元素必然是先出栈，0.所以栈是“后进先出”表。由于队列的输入、输出操作分别在队的两端进行，因此先入队的元素必然先输出，故队列又称为“先进先出”表栈的进出序列例题：进栈序列为123,可能得到的出栈序列是什么？答：共五种123/132/213/

15、231/321进出栈情况（以132序列为例）：1进栈一1出栈，输出1-2进栈一3进栈一3出栈一2出栈输出32栈、队列、循环队列的满/空条件栈空条件：s.top=s.base;栈满条件：s.top-s.base=stacksize;队空条件：Q.front=Q.rear;队满条件：q->rear-q->front=MAXSIZE循环队列空条件：Q.front=Q.rear循环队列满条件：为避免在队满是队头指针和队尾指针也是重合的情况，规定队列中还有一个空的存储单元时为队满，即为Q.front=（Q.rear+1）MODmaxsize（MOD为取余运算符）。因而，这种循环队列不适合用动

16、态数组作为存储结构。2.栈、队列的存储结构、基本操作算法（双向栈）；栈存储结构 顺序栈typedefstructSElemType*base;SElemType*top;intstacksize;SqStack; 链式栈,dam.产型_匚1槿底 队列存储结构顺序存储结构出队列入队列3%4.-BS3.8队列的示意图链式存储结构队头队尾Q-itOTtQA-*T*Ta尸rrnH-hAQzrp5:"一双向栈UIIUV栈i底栈i顶性口顶栈口底存储结构：typedefstructElemtype*base2;Elemtype*top2;BDStacktype;/双向栈类型初始化：StatusIn

17、it_Stack(BDStacktype&tws,intm)初始化一个大小为m的双向栈twstws.base0=(Elemtype*)malloc(sizeof(Elemtype)*m);tws.base1=tws.base0+m;tws.top0=tws.base0;tws.top1=tws.base1;returnOK;/Init_Stack入栈：Statuspush(BDStacktype&tws,inti,Elemtypex)/x入栈,i=0表示低端栈,i=1表示高端栈if(tws.top0>tws.top1)returnOVERFLOW;/注意此时的栈满条件if

18、(i=0)*tws.top0+=x;elseif(i=1)*tws.top1卜-=x;elsereturnERROR;returnOK;/push出栈:Statuspop(BDStacktype&tws,inti,Elemtype&x)/x出栈,i=0表示低端栈,i=1表示高端栈if(i=0)if(tws.top0=tws.base0)returnOVERFLOW;x=*-tws.top0;elseif(i=1)if(tws.top1=tws.base1)returnOVERFLOW;x=*+tws.top1;elsereturnERROR;returnOK;/pop第四章1.

19、字符串模式匹配的简单算法；intIndex(SStringS,SStringT,intpos)/算法4.5/返回子串T在主串S中第pos个字符之后的位置。/若不存在，则函数值为0。/其中，T非空，1WposWStrLength(S)。inti=pos;intj=1;while(i<=S0&&j<=T0)if(Si=Tj)/继续比较后继字符+i;+j;else/指针后退重新开始匹配i=i-j+2;/此时i为上次开始比较位置的下一位j=1;if(j>T0)returni-T0;elsereturn0;/Index2.计算NEXTnextj:0111232技巧：第一

20、二个肯定是0,1!如果要计算next4,找的字符串必须是以第3个字符c为结尾，第1个字符a为开头的。以第6个为例，a前一个字母是b,以第5个字符b为结尾的ab刚好和以第1个字符为开头的ab匹配，所以next6=2+1=3。第五章1.二维数组的地址(下标)换算;习题5.1假设有二维数组A6*8,每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置(基地址)为1000,计算：(1)数组A的体积(即存储量)6*8*6=288字节(3)按行存储是，元素a14的第一个字节的地址1000+(8*1+4)*6=1072基址+(每行的元素个数*行数+当前列序)*每个元素所占存储单元(4)按列存

21、储时，元素a47的第一个字节的地址1000+(6*7+4)*6=6276基址+(每列的元素个数*列数+当前彳T序)*每个元素所占存储单元习题5.2假设按低下标优先存储整数组A9*3*5*8时，第一个元素的字节地址是100,每个整数占四个字节。问下列元素的存储地址是什么？(2) a1111地址：100+(3*5*8*1+5*8*1+8*1+1)*4=776(3) a3125地址：100+(3*5*8*3+5*8*1+8*2+5)*4=1784(4) a8247地址：100+(3*5*8*8+5*8*2+8*4+7)*4=44162 .特殊矩阵(三角、其他有规律)压缩为一维的下标计算；下三角矩阵压

22、缩为一维数组(记忆公式)技巧：推荐把公式(2)背下来(i,j,R范围都是从0开始)，其他根据范围变化公式(1)若1<=j,j<=n,0<=R<=n(n+1)/2-1当i>=j时，k=i(i-1)/2+j-1;当i<j时，k=j(j-1)/2+i-1.(2)若0<=i,j<=n-1,0<=R<=n(n+1)/2-1/注意i,j是0到n-1,下面的公式相当于把(1)中i变成i+1,j变成j+1当i>=j时，k=(i+1)i/2+j;当j<j时，k=(j+1)j/2+i.(3)若1<=j,j<=n,1<=R&l

23、t;=n(n+1)/2/注意R是1到n(n+1)/2,下面公式相当于把(1)中k变成k-1当i>=j时，k=i(i-1)/2+j;当i<j时，k=j(j-1)/2+i;(4)若0<=j,j<=n-1,1<=R<=n(n+1)/2当i>=j时，k=(i+1)i/2+j+1;当i<j时，k=(j+1)j/2+i+1;3 .稀疏矩阵的三元组表示。4.稀疏矩阵应用的算法。(略)£)5.10T的三元组装bxLsta第六章1 .二叉树的性质；性质1：在二叉秋i的第i层上至多有2个结点(i/)。性质2：深度为k的二叉树至多有2k-1个结点(k>

24、1)o性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。性质4：具有n个结点的完全二叉树的深度为og2n+1。性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1日中)，有：(1)如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其双亲是j/2(2)如果2i>n,则结点i无左孩子；如果2i4,则其左孩子是2i。(3)如果2i+1>n,则结点i无右孩子;如果2i+1刍，则其右孩子是2i+1。2 .二叉树的先序、中序、后序、层次遍历过程；树的先序、后序、层次遍历过程;光不遍历：-+ab-c<l/ef中序

25、;遍历：a+b*c-d-e/f后序;遍历：abcd*+ef/-整次遍历：-+/a*efb-cd3.二叉树遍历过程：先（根）序遍历：根一左子树一右子树中（根）序遍历：左子树一根一右子树后（根）序遍历：左子树一右子树一根层次遍历：从上到下，从左往右，逐个遍历树的遍历过程：先根（次序）遍历：先访问根结点，然后依次先根遍历根的每棵子树（根一子树）后跟（次序）遍历：先依次后根遍历每棵子树，然后访问根结点（子树一根）层次遍历：从上到下，从左往右，逐个遍历注：树与二叉树相互转化后树的先根遍历相当于二叉树的先序遍历树的后根遍历相当于二叉树的中序遍历给出两个遍历序列，画出树（二叉树、树）习题6.23画出和下列已

26、知序列对应的树T:（1）树的先根次序访问序列为GFKDAIEBCHJ;（2）树的后根次序访问序列为DIAEKFCJHBGo注：树的后根遍历相当于二叉树的中序遍历EJ由（1）知G为根；G为根，联系（2）知G无右子树；观察（1）,F为G左子树；根据，观察（2）知DIAEK在F左边,在F右边；观察（1）,K为F左子树；根据，观察（2）知K无右子树；观察（1）,D为K左子树；根据，观察（2）知D无左子树；观察（1）,A为D右子树；观察（2）,IE分别为A左右子树；的右子树自行观察判断。4 .二叉树与树相互转换；树转化成二叉树：规则：树的最左孩子变成二叉树左子树，该左孩子的兄弟变成二叉树左子树的右子树向

27、仁）注：原树中B为A最左孩子，C,D为B兄弟，变成二叉树后C成为B右子树，D成为C右子树。二叉树转化成树5 .求哈夫曼树和给出编码、带权路径长度计算。习题6.26假设用于通信的电文仅由0.07,0.19,0.02,0.06,0.32,0.21,0.10路径长度8个字母组成，字母在电文中出现的频率分别为。试为这8个字母设计哈夫曼编码，并求带权7、19、2、6、32、3、21、10。当前未用权：7、19、2、6、32、3、21、10,选出2、3构造出5。当前未用权：7、19、6、32、21、10、5,选出5、6构造出11。当前未用权：7、19、32、21、10、11,选出7、10构造出17。当前未

28、用权：19、32、21、11、17,选出11、17构造出28。当前未用权：19、32、21、28,选出19、21构造出40。当前未用权：32、28、40,选出32、28构造出60。剩下权：40、60,构造出100编码：树的左分支为0,右分支为1。得到哈夫曼编码为A:1101B:01C:11111D:1110E:10F:11110G:00H:1100带权路径长度：(7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4)/100=2.61注：该公式为：A路径长*A权+B路径长*B权+H路径长*H权，因为设的权值是原来的100倍，所以结果除以100。第七章1.邻接矩阵、邻接表存储结

29、构及其特征;图7.1图的示例(«)有向图Gr(b)无向图G图7.8图的部接矩阵注以后向图G1为例01(T(有'路径用1,v1v2否则0)v3v4101v10110011v20000100v3000110ojv41000的邻接表:的邻接表.G】的逆邻接表收012300110100002000131000注：以有向图G1为例第0行值为1的是1、2,所以有V1一2一1。第1行值全为0,所以有V2。第2行值为1的是3,所以有V3-3。第3行值为1的是0,所以有V4-0。2.求最小生成树（Prim、Kruskal）;（a）普里姆（Prim）：以点为基础从V1开始，找到最小边（V1,V3

30、）;寻找与VI、V3相关联的最小边，找到（V3,V6）;寻找与VI、V3、V6相关联的最小边，找到（V6,V4）;寻找与VI、V3、V6V4相关联的最小边，此时有（V4,V1）和（V3,V2）,因为（V4,V1）与原来的边构成圈，所以选择（V3,V2）。（如果（V4,V1）不与原来的边构成圈，则二条边任选一条）；寻找与V1、V3、V6V4、V2相关联，并且不与原来边构成圈的最小边，找到（V2,V5）;克鲁斯卡尔（Kruskal）（避圈法）：以边为基础方法介绍：依次寻找权最小边，避免生成一个圈，所有点联通时生成最小树。3 .拓扑排序；步骤：（1）在有向图中选一个没有前驱的顶点且输出之。（2）从图

31、中删除该顶点和所有以它为尾的弧。注：拓扑排序不唯一。、Floyd)。算法求题7.11图中从顶点a到其他各顶点间的最短路径，写4 .求最短路径过程(Dijkstra迪杰斯特拉(Dijkstra)习题7.11试利用Dijkstra出执行算法过程中各步状态。10求解过程:终点bcdef£s【终点集)K=1152(atc)12K-2156b)p1210(aeQ6(a.c/)®jfK=3153)11(a丁七，f.d)10(口便通)16(a,cTfkg)加aC.f)K=415(B.b)11(siCtfid)16(fliCJig)iCtf»e)K=5*1&14(0ii&

32、#163;1(f.d1g)a-cJte.d值K=615K=1时，找a能直接到达的点，有b,c,d,(a,c)权最小，(a,c)为a到c最短路径，将c放如终点集S;K=2时，找a能直接到达的点，或通过(a,c)能到达的点，(a,c,f)权最小，(a,c,f)为a到f的最短路径，将f放入终点集S;K=3时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，(a,c,e)权最小，(a,c,e)为a到e最短路径，将e放入终点集S;K=4时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，或通过(a,c,e)能到达的点，(a,c,f,d)为a

33、到d最短路径，将d放入终点集S;K=5时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，或通过(a,c,e)能到达的点，或通过(a,c,f,d)能到达的点，(a,c,f,d,g)权最小，为a到g最短路径，将g放入终点集S;K=6时，只剩下(a,b),(a,b)为a到b最短路径，将b放入终点集S。弗洛伊德(Floyd)b-041厂602,3oo0.(b)图7,36带权有向图(Q有向网Gt(b)邻接矩阵DDta>Dfl)012012012012004110411Q46Q461602602602502231803703703?0Pp(-1)p(l)p<S

34、3012012012Q1Z0ABACABACABABCABABC1BAECBABCBABCBCABC2CACACABCACABCACAB图7.37图7.36中有向图的各对顶点间的最爆路径及其路径长度注：D(1)ij是从Vi到Vj的中间顶点的序号不大于1的最短路径的长度；D(k)ij是从Vi到Vj的中间顶点的序号不大于k的最短路径的长度；D(n-1)ij就是从Vi到Vj的最短路径的长度。D(-1)栏中，Vi-Vj不允许有转折点。直接填邻接矩阵。D(0)栏中，Vi-Vj只允许通过V0转折，或者不转折。通过V0转折权值小于原权值，就把原权值替换掉。D(1)栏中，Vi-Vj只允许通过V0、V1转折，或

35、者不转折。如果转折后权值小于原权值，替换。D(2)栏中，Vj-Vj允许通过V0、V1、V2转折，或者不转折，如果转折后权值小于原权值，替换。此时p(2)中就是各点间的最短路径。如果要找的值大于如果要找的值小于平均查找长度等概率条件下,ASL=一呼夫mid=(low+high)/2,继续比较；,继续比较。第九章1 .以下所有查找成功平均查找长度2 .顺序查找；折半查找；顺序查找：从表中最后一个记录开始，逐个进行比较。平均查找长度等概率时，平均查找长度ASL=(n+1)/2不等概率时，ASL=nP1+(n-1)P2+2Pn-1+Pn折半查找：指针low和high分别指示待查元素所在范围的下界和上界

36、，Smid,则让mid=(mid+1+high)/2Smid,则让mid=(low+mid-1)/2当n>50时，有近似结果ASL=Og：(n+1)-13.二叉排序树的插入二叉排序树建立(建立)、删除、平衡过程;(1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3)它的左、右子树也分别为二叉排序树。习胰9.哨已知如下所示长度为12的表(Jan*Feb»Mar*Apr,May.June,July.Aug.Sep.Oct,Nov,Dec)<1)试按表中元素的顺序依次插入一棵初始为空的二叉排

37、序将,画出插入完成之后的二叉排序树并求其在等概率的情况下杳找成功的平均查找长度。<1)求得的二叉排序树如下图所示，在等概率情况下查找成功的平均查找长度为ASLt=-(1X1+2X注：中序遍历二叉排序树，得到从小到大序列根据字母的先后确定大小插入Jan;F小于J,Feb成为Jan左子树；M大于J,Mar成为Jan右子树；Apr小于Jan,且Apr小于Feb,Apr成为Feb左子树；May大于Jan,且May大于Mar,May成为Mar右子树；June大于Jan,且June小于Mar,June成为Mar左子树。剩下的略。二叉排序树删除()3种情况：(1)*p为叶子节点，直接删除。(2) *p

38、只有一个孩子*child只需将*child和*p的双亲直接连接后，即可删去*p。(3)*p有两个孩子用*p的直接前驱或直接后继代替*p,然后删除它的直接前驱或直接后继。平衡二叉树：树上任何节点的左右子树深度差都不超过1插入节点P后不平衡，找到离P最近的不平衡点，根据二叉排序树的建立进行调整。序列:Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec(i)(1)插入Aug时，Feb左右子树深度差超过1不平衡(50XE变化后的2(72)变化后(】)>)(2)插入Oct时，最近不平衡点为May)因为Sep>Oct>May,所以Oct作为

39、双亲变化后的(3)插入Nov时，Jan不平衡。把Jan左转，Mar的左子树变成Jan右子树。4.最终平衡树哈希表构造、冲突解决方法；除留余数法、线性探测或链地址法。构造：除留余数法：H(key)=keyMODp,p<=m冲突解决：，k(k<=m-1)线性探测法：Hi=(H(key)+曲Modmi=1,2,链地址法：将所有关键字为同义词的记录存储在同一线性链表中。例题：已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A0.6中，采用线性探测方法解决冲突。38:38%7=3,查找次数为1。25:25%7=4,

40、查找次数为1。74:74%7=4,与25冲突,(4+1)%7=5,查找次数为2。63:63%7=0,查找次数为1.52:52%7=3,与38冲突,(3+1)%7=4,与25冲突，(4+1)%7=(5+1)%7=5,与74冲突，(1+3+1+1+2+4)76=26,杳找次数为4。48:48%7=6,与52冲突，(6+1)%7=0,与63冲突，(0+1)%7=1,查找次数为3等概率成功查找的平均查找长度为:地址：0123456634838257452次数：131124例9-3已知一组关键字为U9J4.23.01.68,20,84,27.55,11,10,79)则按哈希函数H(key)=keyMOD

41、13和链地址法处理冲突构造所得的哈希表如图9.26所示,125520A3456789101112图9.建链地址法处理神突时的哈爵衰第十章1 .简单排序(直接插入、选择、冒泡)的过程； 直接插入(略) 选择排序基本思想：依次在序列中选出最小的记录Rk,将它与第1个记录R1交换。模式：for(i=0;i<10;i+)for(j=i;j<10;j+); 冒泡排序：基本思想：依次比较相邻的两个数，将小数放在前面，大数放在后面。模式：for(i=0;i<n;i+)for(j=0;j<n-i-1;j+);2 .先进排序(希尔、快速、堆、归并、基数)过程；希尔排序：基本思想：先取一个

42、小于n的整数d1作为第一个增量，所有距离为dl的倍数的记录放在同一个组中，先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量di=1。【初始关键字:一越排序结果:493865977613274955044913t3827-I|6549i9755I7604二趟排序结果：三趟排序结果:13274955044938659776图10.5希尔排序示例初始关9字快速排序：基本思想：选第一个记录为支点，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录关键字比支点小，另一个部分记录的关键字比支点大。再可分别找两个支点，对这两部分记录继续进行快速排序。p

43、ivorkcy进行I次交换之后迸行2次交换之后进行3次交换之后进行4次交换之后273813769765丽完成一趟排序76976549初始状态一次划分之后分别进行快速排序有序序列493865972738131491132738结束结束1327384976132749><76976549)由6576(97)49(65结束结束49657697堆排序：n个关键字序列Kl,K2,，Kn称为堆，必须所有根大于（或小于）其子树。例题：无序序列49,38,65,97,76,13,27,49），进行堆排序思路：将次序列写出完全二叉树形式，然后从最有一个非终端结点开始筛选。归并排序：析始关字一18归并

44、之后二通旧井之后三前归并之后图10.132路归并排序示例基数排序：先将个位数值与fi中的i值相等的放入相应位置将十位数值与fi中的i值相等的放入相应位置将百位数值与fi中的i值相等的放入相应位置()930f£5f£6f7(WJfE»图10.14链式基数排序示例C»)初始状态1(b)第一君分配之后*(C)第一通收集之后，d)第二母分配之后.(G第二收集之后fU)第三也分配之后(G第三船收出之后的有序文杵甲甲fflf5(b)3.各种排序的特点、稳定性、时间复杂度（包括平均、最好、最坏）排序方法平均时阊地坏情况辅助存储简单排序CXrt()|'OGi，)

45、CKD快速排序O(nloflit)tXn1)0(1。5)堆播序OCnJogn)CXulofn)0(1)归并排序O(nlogn)。（制。）CKn)基数排序0(点打+rd)CXref)希尔排序O(nlogn)0(nr)排序方法稳定性插入排序稳定选择排序不稳定冒泡排序稳定希尔排序不稳定快速排序不稳定堆排序不稳定归并排序稳定基数排序稳定数据结构复习数据结构：带有结构和操作的数据元素集合结构：数据元素之间的关系；操作：对数据的加工处理；数据结构研究的问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。(字符字符用文字图形图象声音)对每种数据结构，主要讨论如下三方面的问题：数据的逻辑结构；逻辑

46、结构它属于用户的视图，是面向问题的数据结构从逻辑上分为四类：集合：”属于同一个集合”；线性结构：一对一的线性关系；树结构：一对多的层次关系；图结构：多对多的任意关系。数据的存储结构；数据的存储结构是逻辑结构的物理存储方式，属于具体实现的视图，是面向计算机的通常有两种存储结构：1 .顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。2 .链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。一种数据的逻辑结构可以用多种存储结构来存储数据结构的抽象层次线性结构直接存取类数组，文件顺序存取类表，栈，队列，优先队列广义索引类

47、线性索引，搜索树非线性结构层次结构类树，二叉树，堆群结构类集合，图3)数据的运算，即对数据施加的操作算法分析：时间复杂度算法的概念：算法是求解问题的操作序列(或操作步骤)。时间复杂度T(n):以求解问题的基本操作(原操作)的执行次数作为算法时间的度量for(i=1;i<=n;i+)for(j=1;j<=n;j+)x+;单条语句O(1)一条循环O(n)两条循环0(门八2).一、线性表1线性表的逻辑结构：在线性表中，除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。2顺序表存储特点：1）元素存储在一组连续的内存单元中2）通过元素的存储顺序反映线性表中数

48、据元素之间的逻辑顺序；3 顺序表操作特点：1）可随机存取顺序表的元素；2）顺序表的插入删除操作要通过移动元素实现4 线性链表存储特点：1）用任意一组的存储单元存储线性表中的数据元素；2）通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；5 线性链表操作特点1）不能随机存取元素；2）插入、删除操作通过修改结点的指针实现；6顺序表的插入平均要移动表的一半元素n/2、删除操作平均要移动（n-1）/27顺序表能随机存取元素的原因是：顺序表能通过L.elemi-1或L.elem+（i-1）直接定位元素的存储地址。8线性链表不能随机存取元素的原因是：需从线性链表的头指针开始，顺着链指针定位元素的

49、存储地址9对于经常要存取元素的应用，线性表应采用顺序存储结构10对于经常要插入删除元素的应用，线性表应采用链式存储结构二、栈和队列栈：1栈是限定仅能在表尾一端进行插入、删除操作的线性表；后进先出2表尾称为栈顶，表头称为栈底；3栈的满空判断4栈顶元素的位置由一个栈顶指针指示；5进栈、出栈操作要修改栈顶指针；6一个栈的输入序列为a,b,c,则所有可能的出栈序列为：abc,acb,bac,bca,cba7栈的顺序存储结构1 ）用一组连续的内存单元依次存放自栈底到栈顶的数据元素；2 ）栈顶元素的位置由栈顶指针指示；8栈的链式存储和实现栈的链式存储与线性表的链式存储类似，可用带头结点的线性链表存储。注意

50、：栈顶指针就是带头结点的线性链表的头指针队列：1队列是限定仅能在表尾一端插入，表头一端删除操作的线性表；先进先出2表尾称为队头，表头称为队尾3队头、队尾元素的位置分别由队头指针和队尾指针指示；4队列的满空判断5入队操作要修改队尾指针，出队操作要修改队头指针；6循环队列一一队列的顺序存贮结构三、数和二叉树1树的逻辑结构树：是一种一对多的结构关系或称为分枝结构关系，除了根之外，每个元素只有一个直接前趋；，但每个元素可以有零个或多个直接后继；2树的基本术语：树的结点孩子结点双亲结点兄弟结点结点层（根为1）树的高度（层数）结点的度（结点子树的个数）树的度（树中最大的结点度）叶子结点（度为0的结点）分枝

51、结点（度不为0的结点）森林（互不相交的树集合）3二叉树的定义：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。4二叉树的五种基本形态5二叉树性质性质1在二叉机t的第i层上最多有2A（i-1）个结点性质2深度为k的二叉树最多有2Ak-1个结点，最少有k个结点性质3设二叉树叶子结点数为n0,度为2的结点数为n2,则n0=n2+1性质4具有n个结点的完全二叉树的深度为log2（n+1）性质5在完全二叉权寸中编号为i的结点，1）若有左孩子，则左孩编号为2i;2）若有右孩子，则有孩子结点编号为2i+1;3）若有双亲，则双亲结点编号为i/2;4）结点所在层次为10g2i+15）若i为奇数，且i!=1,它处于右兄弟位置，则它的左兄弟为