数据结构总复习及典型题讲解学习教案

1、会计学1数据结构总复习数据结构总复习(fx)及典型题讲解及典型题讲解第一页，共37页。例例1 1 分析下列算法程序段的时间分析下列算法程序段的时间(shjin)(shjin)复杂度复杂度 for (i=1;i=n;i+) for (i=1;i=n;i+) for(j=1;j=i;j+) for(j=1;j=i;j+) for(k=1;k=j;k+) for(k=1;k=j;k+) x+ x+； / /基本语句基本语句解：计算见下页解：计算见下页第1页/共37页第二页，共37页。分析算法规律可知分析算法规律可知(k zh)(k zh)语句频度语句频度f(n)=1+(1+2)+(1+2+3)+.+

2、(1+2+3+n)f(n)=1+(1+2)+(1+2+3)+.+(1+2+3+n) = = = = = + = + = + = + = n(n+1)(n+2)/6 = n(n+1)(n+2)/6显然有：显然有：T T（n)=(n3)n)=(n3)。nkk1).321 (nkkk12)1(nkk122nkk12216)12)(1(nnn2)1(nn第2页/共37页第三页，共37页。第3页/共37页第四页，共37页。第4页/共37页第五页，共37页。fdgibehjac第5页/共37页第六页，共37页。 第6页/共37页第七页，共37页。 第7页/共37页第八页，共37页。第8页/共37页第九页，

3、共37页。第9页/共37页第十页，共37页。【解】【解】对图进行先序中序和后序遍历时对图进行先序中序和后序遍历时(l sh)(l sh)得到的结点序列分别如下得到的结点序列分别如下: :先序遍历的结点序列为：先序遍历的结点序列为：ABDFGHIECABDFGHIEC中序遍历的结点序列为：中序遍历的结点序列为：FDHGIBEACFDHGIBEAC后序遍历的结点序列为：后序遍历的结点序列为：FHIGDEBCAFHIGDEBCAABCGDEHIF第10页/共37页第十一页，共37页。ABCGDEHIFNIL先序线索先序线索(xin su)二叉树二叉树ABCGDEHIF后序线索二叉树后序线索二叉树NI

4、L第11页/共37页第十二页，共37页。ABEDCGJIFH第12页/共37页第十三页，共37页。ABDCEGJIFH第13页/共37页第十四页，共37页。第14页/共37页第十五页，共37页。abcdefhgi601234578 bdefghi cdatafc 1 2 3 4 8 67 5 aCTree.r=0CTree.n=9例例6.9 用孩子链表结构用孩子链表结构(jigu)表示下图所示的树表示下图所示的树第15页/共37页第十六页，共37页。612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgiPCTree.r=

5、1PCTree.r=1PCTree.n=9PCTree.n=9例例6.10 用带双亲用带双亲(shungqn)的孩子链表表示下图所示的树的孩子链表表示下图所示的树第16页/共37页第十七页，共37页。abcdefhgib d a c e f g h i与树对应的二叉树表示与树对应的二叉树表示(biosh)其根结点无右子树。其根结点无右子树。第17页/共37页第十八页，共37页。ACBED树ABCDE二叉树 A B C D E A B C D E A B C D E 对应存储存储解释解释例6.12 森林(snln)、树与二叉树转换（以二叉链表为纽带）第18页/共37页第十九页，共37页。ABCD

6、EFGHIJ森林森林ABCDEFGHIJ对应二叉树对应二叉树第19页/共37页第二十页，共37页。ABCDEFGHIJABCDEFGHIJ连接连接(linji)跟跟结点结点旋转旋转(xunzhun)成成二叉树二叉树第20页/共37页第二十一页，共37页。例例6.13 6.13 二叉树转换成森林二叉树转换成森林(snln)(snln)抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树ABC

7、DEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第21页/共37页第二十二页，共37页。第22页/共37页第二十三页，共37页。1135819234229148715295810001000011100111 HC 1 01102 10 3 11104 11115 110 6 00 7 01118 011 HuffmanHuffman编码编码(bin m)(bin m)HuffmanHuffman树树第23页/共37页第二十四页，共37页。第24页/共37页第二十五页，共37页。 weightparentlchildrchild15000229000370004800

8、0514000623000730008110009000100001100012000130001400015000 weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152141510001314HTHT初始状态初始状态HTHT终止终止(zhngzh)(zhngzh)状态状态第25页/共37页第二十六页，共37页。1135819234229148715295810001000011100111 HC 1 01

9、102 10 3 11104 11115 110 6 00 7 01118 011 HuffmanHuffman编码编码(bin m)(bin m)HuffmanHuffman树树第26页/共37页第二十七页，共37页。第27页/共37页第二十八页，共37页。ABCDEFGHIJKLMNO先序遍历先序遍历(bin l)：后序后序(hu x)遍历：遍历：层次层次(cngc)遍历：遍历：ABEFI GCDHJKL N OMEIFGB CJKN OLMH D AABCDEFGH IJKLMNO例例6.16 树的遍历树的遍历第28页/共37页第二十九页，共37页。ABCDEFGHIJ例6.17 森林(

10、snln)遍历先序遍历先序遍历(bin l)(bin l)结果：结果：A B C D E F G H I JA B C D E F G H I J中序遍历中序遍历(bin l)(bin l)结果：结果：B C D A F E H J I GB C D A F E H J I G第29页/共37页第三十页，共37页。第30页/共37页第三十一页，共37页。v1v4v3v2v5第31页/共37页第三十二页，共37页。v1v2v3v4v5234135124135242）从v1出发深度优先搜索遍历的结果(ji gu)为：v1 v2 v3 v4 v53）图的广度优先搜索生成树如上右图v1v2v3v4v5

11、第32页/共37页第三十三页，共37页。 15 17 18 22 35 51 60 88 931趟趟 l m h 15 17 18 22 35 51 60 88 932趟趟 l m h 15 17 18 22 35 51 60 88 933趟趟 l m h第33页/共37页第三十四页，共37页。931760 151888512235第34页/共37页第三十五页，共37页。例例 已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：哈希函数为：H(key)=key MOD 13, 哈希表长为哈希表长为m=16， 设每个记录设每个记录(j

12、l)的查找概率相等的查找概率相等(1) 用线性探测再散列处理用线性探测再散列处理(chl)冲突，即冲突，即Hi=(H(key)+di) MOD mH(55)=3 冲突冲突(chngt)，H1=(3+1)MOD16=4 冲突冲突(chngt)，H2=(3+2)MOD16=5H(79)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4 冲突，冲突，H4=(1+4)MOD16=5 冲突，冲突，H5=(1+5)MOD16=6 冲突，冲突，H6=(1+6)MOD16=7 冲突，冲突，H7=(1+7)MOD16=8 冲突

13、，冲突，H8=(1+8)MOD16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2+3*3+4+9)/12=2.514 16827 55 19208479231110H(19)=6H(14)=1H(23)=10H(1)=1 冲突，冲突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 冲突，冲突，H1=(6+1)MOD16=7 冲突，冲突，H2=(6+2)MOD16=8H(27)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10 冲突，冲突，H1=(10+1)MOD16=11 冲突