数据结构分解学习教案

1、会计学1数据结构数据结构(sh j ji u)分解分解第一页，共50页。2插入排序有多种具体实现插入排序有多种具体实现(shxin)算法：算法： 1) 直接插入排序直接插入排序 2) 折半插入排序折半插入排序 3）2-路插入排序路插入排序 4) 表插入排序表插入排序 5) 希尔排序希尔排序小改进小改进大改进大改进第1页/共50页第二页，共50页。3 以关键字序列（以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现）为例，

2、分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现(shxin)？ 直接插入排序直接插入排序 希尔排序（取希尔排序（取dk=5,3,1）答：显然，直接插入排序方法易于在链表上实现；但希尔排序方法因为是按增量答：显然，直接插入排序方法易于在链表上实现；但希尔排序方法因为是按增量(zn lin)选择记录，不易于在链表上实现。选择记录，不易于在链表上实现。 两种排序方法的中间状态分别描述如后：两种排序方法的中间状态分别描述如后：第2页/共50页第三页，共50页。4 256256，301301 ，751751，129129，9

3、37937，863863，742742，694694，076076，438438 256256，301301，751751 ，129129，937937，863863，742742，694694，076076，438438 129129，256256，301301，751751 ，937937，863863，742742，694694，076076，438438 129129，256256，301301，751751，937937 ，863863，742742，694694，076076，438438 129129，256256，301301，751751，863863，937937 ，742

4、742，694694，076076，438438 129129，256256，301301，742742，751751，863863，937937 ，694694，076076，438438 129129，256256，301301，694694，742742，751751，863863，937937 ，076076，438438 076076，129129，256256，301301，694694，742742，751751，863863，937937 ，438438 076076，129129，256256，301301，438438，694694，742742，751751，863863

5、，937937 第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第第6趟趟第第7趟趟第第8趟趟第第9趟趟第3页/共50页第四页，共50页。5256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，937937，863863，742742，751751，076076，438438256256，301301，694694，0

6、76076，937937，863863，742742，751751，129129，438438256256，301301，694694，076076，438438，863863，742742，751751，129129，937937第第1趟趟dk=5dk=5第第2趟趟dk=3dk=3第第3趟趟dk=1dk=1256256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，694694，076076，438438，863863，742742，751751，129129，937937076076，

7、301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438

8、438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，129129，256256，301301，438438，694694，742742，751751，863863，937937第4页/共50页第五页，共50页。6void ShellSort(SqList &L，int dlta ，int t) /按增量序列按增量序列dlta0t-1对顺序对顺序(shnx)表表L作作Shell排序排序 for(k=0；kt；+k)

9、 ShellSort(L，dltak)； / ShellSort空间效率：空间效率：O O（1 1）因为仅占用因为仅占用1 1个缓冲单元个缓冲单元(dnyun)(dnyun)(与算法有关）与算法有关）算法的稳定性：不稳定算法的稳定性：不稳定因为因为4949* *排序后却到了排序后却到了4949的前面的前面参见教材参见教材P272P272由经验公式得到由经验公式得到dkdk值依次装在值依次装在dltadltat t 中中/增量为增量为dltak的一趟插入排序的一趟插入排序第5页/共50页第六页，共50页。7理解难点理解难点(ndin)(ndin)：整理动作是二：整理动作是二合一的，合一的， r0

10、 r0 仍是每个仍是每个dkdk子集的哨兵，子集的哨兵，用于子集的彻底排序！用于子集的彻底排序！ for(i=dk+1；i=L.length； + i) if(ri.key 0&(r0.key0&(r0.keyrj.key); j-=dk) rj+dk=rj；rj+dk=r0； 5 7 45 7 4 i=1 i+dk=6 i+2dk=11 i=1 i+dk=6 i+2dk=11 如果如果(rgu)(rgu)不用不用forfor循环，比较的结果是循环，比较的结果是 5 5，4 4，7 7 只有执行只有执行forfor循环后，比较结果才会是循环后，比较结果才会是 4 4，5 5，7

11、 7for(i=dk+1；i=L.length； + i) if(ri.key ri-dk.key) r0=ri；大者后移大者后移空间效率与算法设计有关空间效率与算法设计有关第7页/共50页第八页，共50页。9交换排序的主要交换排序的主要(zhyo)算法算法有：有： 1) 冒泡排序冒泡排序 2) 快速排序快速排序第8页/共50页第九页，共50页。10基本思路：每趟不断将记录两两比较，并按基本思路：每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。）规则交换。优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生优

12、点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生(fshng)(fshng)，还可以提前结束排序。，还可以提前结束排序。前提：顺序存储结构前提：顺序存储结构 例：关键字序列例：关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排序的具体），请写出冒泡排序的具体(jt)实现过程。实现过程。21，25，49， 25*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，

13、49初态初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第9页/共50页第十页，共50页。11最好情况：初始最好情况：初始(ch sh)排列已经有序，只执行一趟起泡，做排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。次关键码比较，不移动对象。最坏情形：初始最坏情形：初始(ch sh)排列逆序，算法要执行排列逆序，算法要执行n-1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n- i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换。此时的比较总次数次对象交换。此时的比较总次数KCN和记录移动次数和记录移动次数RMN为：为：11111233121nini

14、nninRMNnninKCN)()()()(第10页/共50页第十一页，共50页。12第11页/共50页第十二页，共50页。13第12页/共50页第十三页，共50页。14( )，设以首元素设以首元素(yun s)为枢为枢轴中心轴中心21， 25， 49， 25*，16， 08初态：初态：第第1趟：趟：第第2趟：趟：第第3趟：趟：08，16，21，25， 25*，(49)2116，08，( )25，25*，49(08)，16，21，25，(25*，49)第13页/共50页第十四页，共50页。15pivotkey=21pivotkey=21( 08 ，16 ） 21 （ 25* ， 49， 25

15、）ri0123456初态初态21254925*1608第第1趟趟highhighlowlow2125*32108251649设计技巧：设计技巧：交替交替/振荡式逼近振荡式逼近第14页/共50页第十五页，共50页。16原始原始(yunsh)序列：序列： 256，301，751，129，937，863，742，694，076，438第第1趟趟第第2趟趟第第3趟趟第第4趟趟256256，301301，751751，129129，937937，863863，742742，694694，076076，438438，129129，937937，863863，742742，694694，301301，438

16、438意即模拟算法实现步骤意即模拟算法实现步骤076076301301129129751751，129129，438438，301301，694694，742742，694694，863863，937937，301301，694694，742742，937937，301301，301301，694694，742742，937937，742742，( (存每层存每层lowlow，highhigh和和pivot)pivot)第15页/共50页第十六页，共50页。17讨论讨论1 1：如何编程实现？：如何编程实现？分析：分析：每一趟子表的形成是采用从两头向中间交替式逼近法；每一趟子表的形成是采用从两头

17、向中间交替式逼近法；由于由于(yuy)(yuy)每趟中对各子表的操作都相似，主程序可采每趟中对各子表的操作都相似，主程序可采用递归算法。用递归算法。见教材见教材(jioci)P275int Partition(SqList &L,int low,int high) /int Partition(SqList &L,int low,int high) /一趟快排一趟快排/交换子表交换子表 rlowhigh rlowhigh的记录，使支点（枢轴）记录到位，并返回其位置的记录，使支点（枢轴）记录到位，并返回其位置(wi zhi)(wi zhi)。返回时，在支点之前的记录均不大于它，支

18、点之后的记录均不小于它。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。 r0=rlow; /r0=rlow; /以子表的首记录作为支点记录，放入以子表的首记录作为支点记录，放入r0r0单元单元（续下页）（续下页）一趟快速排序算法一趟快速排序算法（针对一个子表的操作）（针对一个子表的操作）第16页/共50页第十七页，共50页。18pivotkey=rlow.key; /pivotkey=rlow.key; /取支点取支点(zhdin)(zhdin)的关键码存入的关键码存入pivotkeypivotkey变量变量while(low high) while(low high) /从表

19、的两端交替地向中间扫描从表的两端交替地向中间扫描(somio)(somio)while(low=pivotkey ) - -high;while(low=pivotkey ) - -high; rlow=rhigh; / rlow=rhigh; /比支点小的记录交换到低端；比支点小的记录交换到低端；while(lowhigh & rlow.key=pivotkey) + +low;while(lowhigh & rlow.key=pivotkey) + +low; rhigh=rlow; / rhigh=rlow; /比支点大的记录交换到高端；比支点大的记录交换到高端； rlo

20、w=r0; /rlow=r0; /支点记录支点记录(jl)(jl)到位；到位；return low; /return low; /返回支点记录返回支点记录(jl)(jl)所在位置。所在位置。/Partition/Partition第17页/共50页第十八页，共50页。19从高端扫描从高端扫描(somio)寻找小于寻找小于pivot的元的元素素从低端扫描从低端扫描寻找寻找(xnzho)大于大于pivot的的元素元素r0=rlow; pivot=rlow.key;low highlow =pivot- high;rlow = rhigh;low high &rlow.key=pivot-

21、low;rhigh = rlow;rlow = r0;return low;第18页/共50页第十九页，共50页。20if ( low 1/对顺序表对顺序表L中的子序列中的子序列r lowhigh 作快速排序作快速排序/一趟快排，将一趟快排，将r 一分为二一分为二/在左子区间进行递归快排，直到长度为在左子区间进行递归快排，直到长度为1/在右子区间进行递归快排，直到长度为在右子区间进行递归快排，直到长度为1是局部变量是局部变量 1, L.length 第19页/共50页第二十页，共50页。21设每个子表的支点都在中间设每个子表的支点都在中间(zhngjin)(zhngjin)（比较均衡），则：（

22、比较均衡），则：第第1 1趟比较，可以确定趟比较，可以确定1 1个元素的位置；个元素的位置；第第2 2趟比较（趟比较（2 2个子表），可以再确定个子表），可以再确定2 2个元素的位置；个元素的位置；第第3 3趟比较（趟比较（4 4个子表），可以再确定个子表），可以再确定4 4个元素的位置；个元素的位置；第第4 4趟比较（趟比较（8 8个子表），可以再确定个子表），可以再确定8 8个元素的位置；个元素的位置； 只需只需log2nlog2n 1 1趟便可排好序。趟便可排好序。而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。而且，每趟

23、需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。教材教材P276P276有证明：快速排序的平均排序效率为有证明：快速排序的平均排序效率为O(nlogO(nlog2 2n)n)；但最坏情况下但最坏情况下( (例如天然有序例如天然有序) )仍为仍为O(nO(n2 2),),改进措施见改进措施见P277P277。第20页/共50页第二十一页，共50页。22选择排序有多种具体实现选择排序有多种具体实现(shxin)算算法：法： 1) 简单选择排序简单选择排序 2) 锦标赛排序锦标赛排序 3) 堆排序堆排序第21页/共50页第二十二页，共50页。2

24、3第22页/共50页第二十三页，共50页。24原始原始(yunsh)序列：序列： 21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25，49，25*，16，2108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，49时间效率：时间效率： 虽移动次数较少，但比较次数仍多。虽移动次数较少，但比较次数仍多。 空间效率：空间效率：没有附加单元（仅用到没有附加单元（仅用到1 1个个temp)temp)算法的稳定性：算法的稳定性：因为排序时，因为排序时，2525* *

25、到了到了2525的前面。的前面。最小值最小值 0808 与与r1r1交换位置交换位置第23页/共50页第二十四页，共50页。25Void SelectSort(SqList &L ) for (i=1; i0; - - i ) /把把r1length建建成大根堆成大根堆 HeapAdjust(r, i, length ); /使使rilength成为成为大根堆大根堆 / HeapSortHeapAdjust是针对结点是针对结点 i 的堆调整函数，其含义是的堆调整函数，其含义是：从结点：从结点i开始开始(kish)到堆尾为止，自上向下比较，到堆尾为止，自上向下比较，如果子女的值大于双亲结

26、点的值，则互相交换，即如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。把局部调整为大根堆。参见教材参见教材P281-282第37页/共50页第三十八页，共50页。39while(child=m) /检查是否到达当前堆尾，未到尾则整理检查是否到达当前堆尾，未到尾则整理 if ( childm & rchild.key=rchild.key ) breack; /根大则不必调整，函数结束根大则不必调整，函数结束 else rcurrent=rchild; /否则子女中的大者上移否则子女中的大者上移 current= child; child=2* child; /将根下降到

27、子女位置并继续向下整理！将根下降到子女位置并继续向下整理！ / while rcurrent=temp; /直到自下而上都满足直到自下而上都满足(mnz)堆定义，再安置入口结点堆定义，再安置入口结点 / HeapAdjustHeapAdjust(r, i, m )current=i; temp=ri; child=2*i; /temp暂存暂存ri值，值，child是其左孩子是其左孩子(hi zi) 从结点从结点i i开始到开始到当前堆尾当前堆尾m m为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，

28、即把局部调整为大根堆。第38页/共50页第三十九页，共50页。40第39页/共50页第四十页，共50页。41第40页/共50页第四十一页，共50页。42123456136542第41页/共50页第四十二页，共50页。43123456136542第42页/共50页第四十三页，共50页。44123456136542第43页/共50页第四十四页，共50页。45123456136542第44页/共50页第四十五页，共50页。46123456136542第45页/共50页第四十六页，共50页。47void HeapSort (HeapType &H ) /对顺序表对顺序表H进行堆排序进行堆排序 for ( i = H.length / 2; i 0; - - i ) HeapAdjust(H,i, H.length ); /for,建立初始堆建立初始堆 for ( i = H.length