數據結構第八章(排序)習題參考答案(下)

　　二算法設計題

　　 將哨兵放在R[n]中被排序的記錄放在R[n]中重寫直接插入排序算法

　　解重寫的算法如下因為哨兵換了位置所以一切都反向了有序區是從右邊長出來的;

　　void InsertSort(SeqList R)

　　{ file://對 順序表中記錄R[n]按遞增序進行插入排序

　　int ij;

　　for(i=n;i>=;i) file://依 次插入R[n]R[]

　　if(R[i]key>R[i+]key) file://若 不是這樣則R[i]原位不動

　　{

　　R[n]=R[i];j=i+; file://R [n]是哨兵

　　do{ file://從 左向右在有序區中查找插入位置

　　R[j]=R[j]; file://將 關鍵字小於R[i]key的記錄向右移

　　j++;

　　}while(R[j]key

　　R[j]=R[n]; file://將 R[i]插入到正確位置上

　　}//endif

　　}//InsertSort

　　以單鏈表作為存儲結構實現直接插入排序算法

　　解單鏈表?My God! 你還記得那是什麼東東麼? 先定義一個單鏈表結構吧

　　#define int KeyType file://且 定義KeyType 為int型的吧

　　typedef struct node{

　　KeyType key; file://關 鍵字域

　　OtherInfoType info; file://其 它信息域只是意思意思

　　struct node * next; file://鏈 表中指針域

　　}RecNode; file://記 錄結點類型

　　typedef RecNode * RecList ; file://單 鏈表用RecList表示

　　file://下 面就是排序算法

　　void InsertSort(RecList R)

　　{ file://鏈 式存儲結構的直接插入排序算法

　　file://R 是帶頭結點的單鏈表

　　RecNode *p*q*s*t; file://這 四個指針用於保存排序時的結點位置

　　s=R>next; file://s 指向第一個結點

　　t=R; file://t 指向頭結點

　　p=R>next; file://前 一個記錄

　　q=P>next; file://下 一個記錄

　　while( q ) file://當 q為空時表示已經訪問完畢所有結點排序結束

　　{

　　if(p>key>q>key)//此時前一關鍵字大於後一關鍵字因此要進行插入操作

　　{

　　while (s>key<=q>key&&s!=p)

　　{ file://從 頭向右逐個比較直到p結點

　　t=s; file://記 下s結點位置

　　s=s>next; file://指 針向右移

　　}//比較結束找到比q>key大的第一個結點(記錄)

　　t>next=q; file://摘 下q所指結點插入到相應位置

　　P>next=q>next;

　　q>next=s;

　　q=p>next; file://恢 復指針順序

　　S=R>next;

　　t=R;

　　}//endif

　　else file://此 時沒有插入操作指針按序右移

　　{p=p>next; q=q>next;}

　　}//endwhile

　　}//InsertSort

　　設計一算法使得在盡可能少的時間內重排數組將所有取負值的關鍵字放在所有取非負值的關鍵字之前請分析算法的時間復雜度

　　解因為只需將負數關鍵字排在前面而無需進行精確排列順序因此本算法采用兩端掃描的方法就象快速排序采用的方法一樣左邊掃描到正數時停止開始掃描右邊遇到負數時與左邊的當前記錄交換如此交替進行一趟下來就可以完成排序

　　void ReSort(SeqList R)

　　{

　　file://重 排數組使負值關鍵字在前

　　int i=j=n; file://數 組存放在R[n]中

　　while (i file://i

　　{ while(i<) href=file://遇 file://遇 到負數則繼續掃描

　　i++;

　　R[]=R[i]; file://R []為輔助空間

　　while(i=)// 遇到正數則繼續向左掃描

　　j;

　　R[i++]=R[j];R[j]=R[];//交換當前兩個元素並移動指針

　　}//endwhile

　　}//ReSort

　　本算法在任何情況下的比較次數均為n(每個元素和)相比交換次數少於n/總的來說時間復雜度為O(n)

　　*寫一個雙向冒泡排序的算法即在排序過程中交替改變掃描方向

　　解這個算法如下

　　void BubbleSort(SeqList R)

　　{ file://R [n]是待排序文件雙向掃描冒泡排序

　　int ijk;

　　Boolean exchange; file://交 換標記

　　for(i=;i file://最 多只需(n/)趟排序

　　{

　　exchange=FLASE;

　　for(j=ni; j>=i;j) file://對 當前無序區R[ini+]進行自下而上掃描

　　{

　　if(R[j+]key file://輕 的泡泡上升

　　{

　　R[]=R[j+];

　　R[j+]=R[j];

　　R[j]=R[];

　　exchange=TURE; file://交 換後標記為真

　　}

　　if (!exchange) return; file://本 趟排序未發生交換提前結束

　　}//endfor

　　exchange=FLASE; file://重 新設置標記

　　for(k=i+; k<=ni;k++) file://對 當前無序區R[ini+]進行自上而下掃描

　　{

　　if(R[k+]key>R[k]key) file://重 的泡泡下沉

　　{

　　R[]=R[k+];

　　R[k+]=R[k];

　　R[k]=R[];

　　exchange=TURE; file://交 換後標記為真

　　}

　　if(!exchange) return; file://本 趟未發生交換提前結束

　　}//endfor

　　}//endfor

　　}//BubbleSort

　　下面是一個自上往下掃描的冒泡排序的偽代碼算法它采用lastExchange 來記錄每趟掃描中進行交換的最後一個元素的位置並以它作為下一趟排序循環終止的控制值請仿照它寫一個自下往上掃描的冒泡排序算法

　　void BubbleSort(int A[]int n)

　　//不妨設A[n]是整型向量

　　int lastExchangeji=n;

　　while (i>)

　　lastExchange=;

　　for(j=;j

　　if([j+]

　　交換A[j]和A[j+];

　　lastExchange=j;

　　}

　　i=lastExchange;//將i置為最後交換的位置

　　}//endwhile

　　}//BubbleSort

　　解算法如下這種方向性的改變一般是一些加號要變為減號大於變成小於頭一個結點變成最後一個結點如此這般

　　void BubbleSort(int A[]int n)

　　file://不 妨設A[n]是整型向量

　　int lastExchangeji=;

　　while (i file://這 一條很重要如不改為這樣算法將無限循環下去

　　lastExchange=n;

　　for(j=n;j>i;j)//從下往上掃描A[i]

　　if([j]

　　交換A[j]和A[j];

　　lastExchange=j;

　　}

　　i=lastExchange;//將i置為最後交換的位置

　　}//endwhile

　　}//BubbleSort

　　改寫快速排序算法要求采用三者取中的方式選擇劃分的基准記錄;若當前被排序的區間長度小於等於時無須劃分而是直接采用直接插入方式對其排序

　　解改寫後的算法如下

　　void QuickSort(SeqList Rint low int high)

　　{ file://對 R[lowhigh]快速排序

　　int pivotpos;

　　if(highlow<=) file://若 當前區內元素少於個

　　{ file://則 進行直接插入排序

　　InsertSort(Rlowhigh);//此函數就不寫了

　　}

　　else

　　{

　　pivotpos=midPartion(Rlowhigh);

　　QuickSort(Rlowpivotpos);

　　QuickSort(Rpivotpos+high);

　　}

　　}//QuickSort

　　int midPartion(SeqList Rint i int j)

　　{ file://三 者取中規則定基准

　　if(R[(i+j)/]key>R[i]key)

　　{ 交換R[(i+j)/]和R[i];}

　　if(R[i]key>R[j]key)

　　{ 交換R[i]和R[j];}

　　if(R[i]key)

　　{ 交換R[i]和R[(i+j)/];}

　　file://以 上三個if語句就使區間的第一個記錄的key值為三個key的中間值

　　return Partion(Rij);//這樣我們就可以仍使用原來的劃分算法了

　　}

　　順便提一下課本中又有幾處筆誤如第頁的算法中A[i]A[k]應為R[i]R[k]以及下面的算法中遞歸調用的應是RandomizedQuickSort函數而不是QuickSort函數

　　另外這些算法並不能直接用於驗證因為算法中用的都不是指針參數而算法又要對實參進行修改才能達到所需結果所以我們主要是要理解算法的整個思想和實現真正編程的話要上機多試才行

　　對給定的j( ≤ j ≤ n )要求在無序的記錄區R[n]中找到按關鍵字自小到大排在第j個位置上的記錄(即在無序集合中找到第j個最小元)試利用快速排序的劃分思想編寫算法實現上述的查找操作

　　(答案及點評) 以單鏈表為存儲結構寫一個直接選擇排序算法

　　(答案及點評) 寫一個heapInsert(Rkey)算法將關鍵字插入到堆R中去並保證插入R後仍是堆提示應為堆R增加一個長度屬性描述(即改寫本章定義的SeqList類型描述使其含有長度域);將key先插入R中已有元素的尾部(即原堆的長度加的位置插入後堆的長度加)然後從下
From:http://tw.wingwit.com/Article/program/sjjg/201311/23626.html