《数据结构习题课7学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构习题课7学习教案.pptx（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1数据结构数据结构(sh j ji u)习题课习题课7第一页，共37页。第第7章作业章作业(zuy)n n247页：每组的第1题是必交的，即7-2、7-5、7-18、7-24、7-49n n7-2、7-3、n n7-5、7-8、7-10、n n7-18、n n7-24、7-26、7-30、7-31、7-35、7-36n n7-49、7-50第1页/共37页第二页，共37页。7-2n n若对序列（若对序列（7，3，1，8，6，2，4，5）按从）按从小到大排序小到大排序(pi x)，请写出冒泡排序，请写出冒泡排序(pi x)的第一趟结果。的第一趟结果。第2页/共37页第三页，共37页。n n
2、参考答案 3，1，7，6，2，4，5，8第3页/共37页第四页，共37页。7-3n n设文件（R1，R2，Rn）以单链表方式表示，指针(zhzhn)变量FIRST指向表头结点，且表中的结点结构为：n n其中KEY为该结点的关键词域，LINK为链接域。请给出这种线性表的直接插入排序算法，并要求算法的时间复杂度为O(n2)，且算法是稳定的。KEYLINK第4页/共37页第五页，共37页。n n算法算法(sun f(sun f)InsertSort(FIRST.FIRST)InsertSort(FIRST.FIRST)n n /*/*对单链表直接插入排序对单链表直接插入排序,FIRST,FIRST指
3、向表头结点指向表头结点*/*/n nIS1IS1边界边界 n n IF(LINK(FIRST)=NULL OR LINK(LINK(FIRST)=NULL)THEN IF(LINK(FIRST)=NULL OR LINK(LINK(FIRST)=NULL)THEN RETRUN.RETRUN.n nIS2IS2插入排序插入排序 n n q LINK(FIRST).q0 LINK(q).q LINK(FIRST).q0 LINK(q).n n WHILE(qNULL)(WHILE(qNULL)(n n p LINK(FIRST).p0 FIRST.p LINK(FIRST).p0 FIRST.n
4、 n WHILE(KEY(p)=KEY(q)AND LINK(p)q)DO WHILE(KEY(p)=KEY(q)AND LINK(p)q)DO n n (p0p.pLINK(p).).(p0p.pLINK(p).).n n IF(KEY(p)KEY(q)THEN(IF(KEY(p)KEY(q)THEN(n n LINK(q0)LINK(q).LINK(p0)q.LINK(q)p.LINK(q0)LINK(q).LINK(p0)q.LINK(q)p.n n q LINK(q0).).q LINK(q0).).n n ESLE(q0 q.q LINK(q0).).ESLE(q0 q.q LINK
5、(q0).).n n )第5页/共37页第六页，共37页。7-5n n设计一算法，在尽可能少的时间内重排数组，使所有取负设计一算法，在尽可能少的时间内重排数组，使所有取负设计一算法，在尽可能少的时间内重排数组，使所有取负设计一算法，在尽可能少的时间内重排数组，使所有取负值的关键词放在所有取非负值的关键词之前值的关键词放在所有取非负值的关键词之前值的关键词放在所有取非负值的关键词之前值的关键词放在所有取非负值的关键词之前(zhqin)(zhqin)，并分析算法的时间复杂度。并分析算法的时间复杂度。并分析算法的时间复杂度。并分析算法的时间复杂度。第6页/共37页第七页，共37页。n n基本思想：以
6、0为基准记录，使用快速排序(pi x)的一次分划过程即可，时间复杂度为O(n).第7页/共37页第八页，共37页。算法算法Part(A,n.A)Part(A,n.A)/*/*以以0 0为基准为基准(jzh(jzh n)n)元素一次分划元素一次分划*/*/P1 P1 初始化初始化 i1.jn.i1.jn.P2P2以以0 0分划分划 WHILE ij DO WHILE ij DO (WHILE Ki0 AND ij DO ii+1.WHILE Ki0 AND i0 AND i0 AND iRj+1)时才会发生交换，关键词相同的记录不会(b hu)发生交换，即相同位置不变，因此是冒泡排序算法是稳定的
7、。第10页/共37页第十一页，共37页。7-10n n类似于冒泡过程（从下到上），与之对应的是下沉过程（从上到下）。如果排序是冒泡和下沉的交替过程，证明如果经过一趟冒泡和一次下沉后发现Rj和Rj+1（1jn1）没有交换，则它们已经进入(jnr)最终排序位置。第11页/共37页第十二页，共37页。参考答案参考答案n n证明：n n如果经过一趟冒泡和一次下沉后发现Rj和Rj+1（1jn1）没有交换，那么(n me)有n n R1=R2=R3=Xi+1.key)if(Xi.keyXi+1.key)n n (Xi (Xi Xi+1.Xi+1.n n change 1.)change 1.)n n fo
8、r i 2 for i 2 toto n-1 step 2 /n-1 step 2 /偶交换偶交换偶交换偶交换n n if(Xi.keyXi+1.key)if(Xi.keyXi+1.key)n n (Xi (Xi Xi+1.Xi+1.n n change 1.)change 1.)n n )第15页/共37页第十六页，共37页。n n(1)(1)最好情况下，比较最好情况下，比较最好情况下，比较最好情况下，比较(b(b jio)jio)一趟每趟中奇交换偶交换比较一趟每趟中奇交换偶交换比较一趟每趟中奇交换偶交换比较一趟每趟中奇交换偶交换比较(b(b jio)jio)次次次次数共数共数共数共(n-1
9、)(n-1)次，无记录交换次，无记录交换次，无记录交换次，无记录交换 /正序正序正序正序n n(2)(2)最坏情况下比较最坏情况下比较最坏情况下比较最坏情况下比较(b(b jio)(n/2)+1jio)(n/2)+1趟，总比较趟，总比较趟，总比较趟，总比较(b(b jio)jio)次数为次数为次数为次数为(n-(n-1)*(n/2+11)*(n/2+1）次每次比较）次每次比较）次每次比较）次每次比较(b(b jio)jio)都交换，总交换次数为都交换，总交换次数为都交换，总交换次数为都交换，总交换次数为(n-1)*n/2(n-1)*n/2 或或或或 (n-1)*3n/2(n-1)*3n/2 /
10、逆序逆序逆序逆序n n(3)(3)最好时间最好时间最好时间最好时间O(n)O(n)n n最坏时间最坏时间最坏时间最坏时间O(n2)O(n2)n n平均时间平均时间平均时间平均时间O(n2)(O(n2)(书上书上书上书上P201P201反序对的平均数反序对的平均数反序对的平均数反序对的平均数)第16页/共37页第十七页，共37页。正确性证明正确性证明(zhngmng)：数学：数学归纳法归纳法n n对元素个数n进行归纳n n当n=1是，算法正确n n假设当n=k时，算法能对n个元素的数组进行排序，则当n=k+1时，进行一趟分划后,轴心元素Rs进入了最终(zu zhn)排序应在的位置Ri，即Ri之前
11、的元素RsRi-1都小于等于Ri，Ri之后的元素Ri+1Re都大于等于Ri。由于RsRi-1,Ri+1Re任意一部分最多为k个，按照假设，都能正确排序。因此，该算法能对全部k+1个元素正确排序。第17页/共37页第十八页，共37页。7-24n n填充如下排序算法中的方框，并证明填充如下排序算法中的方框，并证明(zhngmng)该算法的正确性该算法的正确性.(实质是一趟实质是一趟快速排序算法快速排序算法)n n算法算法PartA(R,s,e)n n/分划文件分划文件(Rs,Rs+1,Re),且且Ks-1=-,Ke+1=+n nPA1初始化初始化n n i s.j .n n K Ks.R Rs.e
12、+1第18页/共37页第十九页，共37页。n nPA2分划分划(fn hu)过程过程n n while ij don n (jj-1.n n while do jj-1.n n if (ij)then ji.n n else (Ri Rj.n n i=i+1.n n while KiK do i i+1.n n if then Rj Ri.).n nPA3 KjKi=M n/2 =M，才会在辅助堆栈中压入第，才会在辅助堆栈中压入第1 1个元素个元素n n当当n/(22)=Mn/(22)=M，才会在辅助堆栈中压入第，才会在辅助堆栈中压入第2 2个元素个元素n n，依此类推，依此类推(y c(y
13、c li tu)li tu)，n n当当n/(2k)=Mn/(2k)=M，才会在辅助堆栈中压入第，才会在辅助堆栈中压入第k k个元素个元素n n则则 2k=n/M.k=log2(n/M)2k=n/M.k=log2(n/M)n n因此最多为因此最多为 floor(log2(n/M)floor(log2(n/M)个个第21页/共37页第二十二页，共37页。7-30n n证明：用淘汰赛找n个元素的最大元素正好(zhngho)需要n1次元素比较。第22页/共37页第二十三页，共37页。参考答案参考答案n n证明(zhngmng)：在淘汰赛中，每进行一场比赛，即进行依次比较，都恰淘汰1个元素，找到最大元
14、素需要淘汰n-1个元素，因此需要n-1比较。第23页/共37页第二十四页，共37页。7-31n n证明(zhngmng)：用淘汰赛找 n个元素的最大元素所形成的树高为log2n.第24页/共37页第二十五页，共37页。参考答案参考答案n n证明：证明：n n 当当n=2Kn=2K时，第时，第1 1轮后剩下轮后剩下n/2=2K-1 n/2=2K-1，第二轮后剩下，第二轮后剩下n/4=2K-2,n/4=2K-2,依次类推依次类推,第第k k轮淘汰赛后就剩下轮淘汰赛后就剩下1 1个选手个选手(xu(xu nshnsh u)u)，就是最大元素。每一轮淘汰赛都对，就是最大元素。每一轮淘汰赛都对应比赛树中
15、的一层，因此当应比赛树中的一层，因此当n=2Kn=2K时，比赛树的最大层数是时，比赛树的最大层数是k k，比赛树的高度是，比赛树的高度是log2nlog2nn n 当当n n为任意数时，总可以找到一个为任意数时，总可以找到一个k k，使得，使得2K-1n=2k2K-1n=2k，只需要，只需要k k轮淘汰赛轮淘汰赛就可以最大元素，对应的比赛树高为就可以最大元素，对应的比赛树高为k k。由。由2K-1n=2k 2K-1n=2k，得，得log2n=klog2n+1log2n=k1 AND Ri/21 AND Ri/21;j=1)/上浮(shn f)if(aj aj1)swap(aj,aj1);第28
16、页/共37页第二十九页，共37页。7-36n n文件(R1，R2，Rn)是一个堆，1in，请给出一个算法，该算法从(R1，R2，Rn)中删除 Ri，并使删除后的文件仍然是堆，要求(yoqi)算法的时间复杂度为O(log2n).第29页/共37页第三十页，共37页。参考答案参考答案n n算法算法Delete(R,n,i.R,n)Delete(R,n,i.R,n)n n/*/*在堆中删除元素在堆中删除元素RiRi，从上往下调整堆，从上往下调整堆*/*/n nD1 RiD1 Ri与与RnRn交换交换(jiohun)(jiohun)n n Ri Rn.n n-1.Ri Rn.n n-1.n nD2 D
17、2 从上往下调整，称下沉从上往下调整，称下沉 n n ji.ji.n n WHILE(2*jRj OR WHILE(2*jRj ORn n 2*j+1Rj)DO(2*j+1Rj)DO(n n y 2*j.y 2*j.n n IF(2*j+1R2*j)THEN y y+1.IF(2*j+1R2*j)THEN y y+1.n n Rj Ry.j y.Rj Ry.j y.n n )第30页/共37页第三十一页，共37页。C+int hMAXN;int hMAXN;int n=0;int n=0;void delete(int i)void delete(int i)hi=hn-;hi=hn-;whi
18、le(2*i hi|2*i+1hi)while(2*i hi|2*i+1hi)int y=2*i;int y=2*i;if(y+1hy)y+;if(y+1hy)y+;swap(hi,hy);swap(hi,hy);i=y;i=y;第31页/共37页第三十二页，共37页。7-49n n填充如下排序填充如下排序(pi x)算法中的方框，并讨算法中的方框，并讨论该算法的稳定性论该算法的稳定性.n n算法算法C(R，n)n n/*比较计数，本算法按关键词比较计数，本算法按关键词K1，K2，Kn排序排序(pi x)记录记录R1，R2，Rn.一维数组一维数组COUNT1:n用来记录各个记录用来记录各个记录
19、的排序的排序(pi x)位置位置*/第32页/共37页第三十三页，共37页。C1 FOR i=1 TO n DO .C2 FOR i=n TO 2 DO FOR j=i1 TO 1 STEP 1 DO FOR j=i1 TO 1 STEP 1 DO IFIF THEN THEN COUNTj COUNTj+1COUNTj COUNTj+1 ELSEELSE STEP 1STEP 1K Kj jKKi icounti counti+1counti counti+1counti 1counti 1第33页/共37页第三十四页，共37页。稳定性讨论稳定性讨论(toln)该算法该算法(sun f)是稳
20、定的是稳定的第34页/共37页第三十五页，共37页。7-50n n有一种简单的排序算法，叫做计数排序有一种简单的排序算法，叫做计数排序(Count Sorting).(Count Sorting).这种排序算法这种排序算法对一个待排序的表对一个待排序的表(用数组表示用数组表示)进行排序，并将排序结果存放到另一进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键词互不相同，计个新的表中。必须注意的是，表中所有待排序的关键词互不相同，计数排序算法针对数排序算法针对(zhndu)(zhndu)表中的每个记录，扫描待排序的表一趟，表中的每个记录，扫描待排序的表一趟，统计表中有
21、多少个记录的关键词比该记录的关键词小，假设针对统计表中有多少个记录的关键词比该记录的关键词小，假设针对(zhndu)(zhndu)某一个记录，统计出的计数值为某一个记录，统计出的计数值为c c，那么，这个记录在新的，那么，这个记录在新的有序表中的合适的存放位置即为有序表中的合适的存放位置即为c.c.n n(1)(1)给出适用于计数排序的数据表定义。给出适用于计数排序的数据表定义。n n(2)(2)对于有对于有n n个记录的表，关键词比较次数是多少？个记录的表，关键词比较次数是多少？n n(3)(3)与简单选择排序相比较，这种方法是否更好？为什么？与简单选择排序相比较，这种方法是否更好？为什么？第35页/共37页第三十六页，共37页。参考答案参考答案n n(1)数据表放在数组R中，元素个数为n，下标从0开始（因为小于关键词的个数为c,就放在c的位置）。n n(2)对于每个记录，扫描待排序的表一趟，即比较n次。一共n个记录，共需比较n2次。n n(3)与简单选择排序相比(xin b)，比较次数增加，移动次数减少。整体上时间效率要低于简单选择排序，辅助空间要高于简单选择排序。第36页/共37页第三十七页，共37页。