軟考軟件設(shè)計師專題講義九：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

　　表插入排序算法分析：

　　直接插入排序、折半插入排序均要大量移動記錄，時間開銷大。若要不移動記錄完成排序，需要改變存儲結(jié)構(gòu)，進(jìn)行表插入排序。所謂表插入排序，就是通過鏈接指針，按關(guān)鍵碼的大小，實現(xiàn)從小到大的鏈接過程，為此需增設(shè)一個指針項。操作方法與直接插入排序類似，所不同的是直接插入排序要移動記錄，而表插入排序是修改鏈接指針。用靜態(tài)鏈表來說明。

　　#define SIZE 200

　　typedef struct{

　　ElemType elem; /*元素類型*/

　　int next; /*指針項*/

　　}NodeType; /*表結(jié)點類型*/

　　typedef struct{

　　NodeType r[SIZE]; /*靜態(tài)鏈表*/

　　int length; /*表長度*/

　　}L_TBL; /*靜態(tài)鏈表類型*/

　　假設(shè)數(shù)據(jù)元素已存儲在鏈表中，且0號單元作為頭結(jié)點，不移動記錄而只是改變鏈指針域，將記錄按關(guān)鍵碼建為一個有序鏈表。首先，設(shè)置空的循環(huán)鏈表，即頭結(jié)點指針域置0，并在頭結(jié)點數(shù)據(jù)域中存放比所有記錄關(guān)鍵碼都大的整數(shù)。接下來，逐個結(jié)點向鏈表中插入即可。

　　表插入排序得到一個有序的鏈表，查找則只能進(jìn)行順序查找，而不能進(jìn)行隨機查找，如折半查找。為此，還需要對記錄進(jìn)行重排。

　　重排記錄方法：按鏈表順序掃描各結(jié)點，將第i個結(jié)點中的數(shù)據(jù)元素調(diào)整到數(shù)組的第i個分量數(shù)據(jù)域。因為第i個結(jié)點可能是數(shù)組的第j個分量，數(shù)據(jù)元素調(diào)整僅需將兩個數(shù)組分量中數(shù)據(jù)元素交換即可，但為了能對所有數(shù)據(jù)元素進(jìn)行正常調(diào)整，指針域也需處理。

　　【算法10.3】

　　1. j=l->r[0].next;i=1; //指向第一個記錄位置，從第一個記錄開始調(diào)整

　　2. 若i=l->length時，調(diào)整結(jié)束;否則，

　　a. 若i=j，j=l->r[j].next;i++;轉(zhuǎn)(2) //數(shù)據(jù)元素應(yīng)在這分量中，不用調(diào)整，處理下一個結(jié)點

　　b. 若j>i，l->r[i].elem<-->l->r[j].elem; //交換數(shù)據(jù)元素

　　p=l->r[j].next; // 保存下一個結(jié)點地址

　　l->r[j].next=l->[i].next;l->[i].next=j; // 保持后續(xù)鏈表不被中斷

　　j=p;i++;轉(zhuǎn)(2) // 指向下一個處理的結(jié)點

　　c. 若jr[j].next;//j分量中原記錄已移走，沿j的指針域找尋原記錄的位置

　　轉(zhuǎn)到(a)

　　【時效分析】

　　表插入排序的基本操作是將一個記錄插入到已排好序的有序鏈表中，設(shè)有序表長度為i，則需要比較至多i+1次，修改指針兩次。因此，總比較次數(shù)與直接插入排序相同，修改指針總次數(shù)為2n次。所以，時間復(fù)雜度仍為O(n2)

　　　　　　　計算機軟考軟件設(shè)計師練習(xí)試題及答案解析匯總