數(shù)據(jù)結(jié)構(gòu)作業(yè)系統(tǒng)答案

1、試以k+1作為監(jiān)視哨改寫教材節(jié)中給出的直接插入排序算法。其中，為待排序記錄且k<MAXSIZEo實(shí)現(xiàn)下列函數(shù)：voidlnsertSort(SqList&L);順序表的類型SqList定義如下：typedefstructKeyTypekey;RedType;typedefstructRedTyperMAXSIZE+1;.RedType;typedefstructRedTyperMAXSIZE+1;.,kp是堆，則可以寫一個(gè)時(shí)間復(fù)雜度為O(log(n)的算法將(法,k2,kp,kp+1)調(diào)整為堆。試編寫”從p=1起，逐個(gè)插入建堆”的算法，并討論由此方法建堆的時(shí)間復(fù)雜度。實(shí)現(xiàn)下列函數(shù)

2、：voidCreateHeap(HeapType&h,char*s);堆(順序表)的類型HeapType定義如下：typedefcharKeyType;typedefstructKeyTypekey;RedType;typedefstructRedTyperMAXSIZE+1;intlength;SqList,HeapType;voidCreateHeap(HeapType&h,char*s)(inti,j,locate,k;KeyTypee;=0；for(i=0;si!=,0,;i+)+;.key=si;e=.key;locate=;k=2;for(j=;k>0;j=j

3、/2,k=j/2)(if(e<k.key)(j.key=k.key;locate=k;)locate.key=e;假設(shè)定義堆為滿足如下性質(zhì)的完全三叉樹：空樹為堆；根結(jié)點(diǎn)的值不小于所有子樹根的值，且所有子樹均為堆。編寫利用上述定義的堆進(jìn)行排序的算法，并分析推導(dǎo)算法的時(shí)間復(fù)雜度。實(shí)現(xiàn)下列函數(shù)：voidHeapSort(HeapType&h);堆(順序表)的類型HeapType定義如下：typedefcharKeyType;typedefstructKeyTypekey;RedType;typedefstructRedTyperMAXSIZE+1;intlength;SqList,He

4、apType;比較函數(shù)和交換函數(shù)：StatusLT(RedTypea,RedTypeb)return<TRUE:FALSE;StatusGT(RedTypea,RedTypeb)return>TRUE:FALSE;voidSwap(RedType&a,RedType&b)RedTypec;c=a;a=b;b=c;voidHeapAdjust(HeapType&H,intsjntm)intj,flag;RedTyperc;rc=s;for(j=3*s-1;j<=m;j=3*j-1)(flag=O;printf(nDo%dnHJ);if(j<m&am

5、p;&LTj,j+1)j+；flag=1;printf(巧;if(flag)if(j<m&&LTj，D+1)j+;elseif0+1<m&&LTO，O+2)j=j+2;if(!LT(rc，O)break;s=0；s=j；s=rc;|voidHeapSort(HeapType&h)/*元素比較和交換必須調(diào)用以下比較函數(shù)和交換函數(shù)：*/*StatusLT(RedTypea,RedTypeb);比較："<"*/*StatusGT(RedTypea,RedTypeb);比較：*/*voidSwap(RedType&a

6、mp;a,RedType&b);交換*/(inti;RedType;typedefstructRedTyperMAXSIZE+1;ey)(temp=j;k=j；temp=i;i=M；k=temp;if%2=0)n=2;elsen=2+1;returnn.key;已知記錄序列a1.n中的關(guān)鍵字各不相同，可按如下所述實(shí)現(xiàn)計(jì)數(shù)排序：另設(shè)數(shù)組c1.n,對(duì)每個(gè)記錄ai,統(tǒng)計(jì)序列中關(guān)鍵字比它小的記錄個(gè)數(shù)存于ci,則ci=O的記錄必為關(guān)鍵字最小的記錄，然后依ci值的大小對(duì)a中記錄進(jìn)行重新排列，試編寫算法實(shí)現(xiàn)上述排序方法。實(shí)現(xiàn)下列函數(shù)：voidCountSort(SqList&L);/*采用順序表存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)序列a,為n*/*在函數(shù)內(nèi)自行定義計(jì)數(shù)數(shù)組c7順序表的類型SqList定義如下：typedefstructKeyTypekey;RedType;typedefs