作者:來源:2006年9月4日
13.將哨兵放在R[n]中，將排序後的記錄放在R[0..n-1]，並重寫直接插入排序算法。
解決方案:
重寫的算法如下:
void InsertSort(SeqList R)
{//插入並排序記錄r [0...n-1]按升序排列。
int i，j；
for(I = n-2；我& gt=0;I-)//Insert R[n-2]..R[0]依次在有序區域中。
if(R[i]。key & gtR[i+1]。key) //如果不是，R[i]保持不變。
{
R[n]= R[I]；j = I+1；//R[n]是哨兵
Do{ //從左到右查找有序區域中的插入位置。
R[j-1]= R[j]；//移動關鍵字小於R[i]的記錄。鑰匙在右邊。
j++；
}while(R[j].key & ltR[n]。key])；
R[j-1]= R[n]；//將R[i]插入正確的位置。
}//endif
}//InsertSort。
14.用單鏈表作為存儲結構實現直接插入排序算法。
解決方案:
#define int KeyType //將KeyType定義為int類型。
typedef結構節點{
KeyType鍵；//關鍵字字段
其他信息類型信息；//其他信息字段，
結構節點* next//鏈表中的指針字段
} RecNode//記錄節點類型
typedef RecNode * LinkList//單個鏈表由LinkList表示。
void InsertSort(鏈表頭)
{//鏈式存儲結構的直接插入排序算法，其中head是以前導節點為單位的單鏈表。
RecNode *p，*q，* s；
如果((head-& gt；接下來)& amp& amp(頭-& gt；下壹個-& gt；next))///當表中的節點數大於1時。
{
p = head-& gt；下壹個-& gt；接下來；//p指向第二個節點。
head->；next = NULL
q =頭；//指向插入位置的前置節點。
while(p)& amp；& amp(問->；接下來)& amp& amp(p->；key & ltq->；下壹個-& gt；關鍵)
q = q-& gt；接下來；
如果(p)
{ s = p；p = p-& gt；接下來；//移除要插入的節點。
s-& gt；next = q-& gt；接下來；//在Q節點後插入適當的位置
q->；next = s；
}
}
}
15.設計壹個算法，在盡可能短的時間內重新排列數組，把所有否定關鍵字放在所有非否定關鍵字之前。請分析算法的時間復雜度。
解決方案:
因為只有否定的關鍵詞需要排在第壹位，沒有精確的排序順序，所以這個算法采用了兩端掃描的方法，就像快速排序中使用的方法壹樣。當左側掃描到正數時，停止向右側掃描，遇到負數時，與左側的當前記錄進行交換，這樣壹次行程即可完成排序。
無效度假村(SeqList R)
{//重新排列數組，使negative關鍵字排在前面。
int i=1，j = n；//數組存儲在r [1...n]
while(我& ltj)//I & lt；j表示掃描尚未完成。
{ while(I & lt；強生公司。& ampR[i]。key & lt0) //如果遇到負數，繼續掃描。
i++；
R[0]= R[I]；//R[0]是輔助空格。
while(我& lt強生公司。& ampR[j]。key & gt=0)//如果遇到正數，繼續向左掃描。
j-；
R[i++]= R[j]；R[j-]= R[0]；//交換當前兩個元素並移動指針。
}//結束時間
}//度假村
在任何情況下，該算法中的比較次數為n(每個元素為0)，交換次數小於n/2。壹般來說，時間復雜度為O(n)。
*16.寫壹個雙向冒泡排序算法，就是在排序過程中交替改變掃描方向。
解決方案:
算法如下:
void冒泡排序(SeqList R)
{//r [1...n]是要排序的文件，采用雙向掃描冒泡排序。
int i，j，k；
布爾交換；//交換標簽
I = n；j = 1；
交換=真；
while(I & gt；j)& amp；& amp(交換)
{ k = I-1；交換=假；
while(k & gt；=j)//從下到上掃描
{ if(r[k]& gt；r[k+1])
{ r[0]= r[k]；r[k]= r[k+1]；r[k+1]= r[k]；交換=真；//交換
}//endif
k-；
}//結束時間
如果(交換)
{ exchange = FALSE
j++；k = j+1；
while(k & lt；=i)//從上到下掃描
{ if(r[k]& lt；r[k-1])
{ r[0]= r[k]；r[k]= r[k-1]；r[k-1]= r[k]；交換=真；//交換
}//endif
k++；
}結束時間
I-；
}//endif
}結束時間
}//endsort
17.下面是壹個自上而下冒泡排序的偽代碼算法，使用lastExchange記錄每次掃描中交換的最後壹個元素的位置，並以此作為下壹個排序循環終止的控制值。請寫壹個自下而上掃描的冒泡排序算法。
void BubbleSort(int A[]，int n)
//讓A[0..n-1]是整數向量。
int lastExchange，j，I = n-1；
while(I & gt；0)
last exchange = 0；
for(j = 0；j & lt我；J++)//掃描A[0..i]從上到下。
if(A[j+1]& lt；A[j]){
交換A[j]和A[j+1]；
last exchange = j；
}
i = lastExchange//將I設置為最後壹個交換位置。
}//結束時間
}//BubbleSort
解決方案:算法如下:
void BubbleSort(int A[]，int n)
//讓A[0..n-1]是整數向量。
int lastExchange，j，I = 0；
while(我& ltN) //這個很重要。如果不改為這個，算法會無限循環。
last exchange = n；
for(j = n-1；j & gt我；j-)//掃描A[0..i]從下到上。
if(A[j-1]& lt；A[j]){
交換A[j]和A[j-1]；
last exchange = j；
}
i = lastExchange//將I設置為最後壹個交換位置。
}//結束時間
}//BubbleSort
18.要重寫快速排序，需要通過選擇三個來選擇劃分的基準記錄；如果當前排序的區間長度小於或等於3，則直接插入排序，不進行分割。
解決方案:
重寫後的算法如下:
void快速排序(SeqList R，int low，int high)
{//Sort R [low...高]迅速
int pivotpos
if(高-低& lt=2)//如果當前區域中的元素少於3個，
{//執行直接插入排序。
InsertSort(R，low，high)；
}
其他
{
pivot pos = mid partition(R，low，high)；
QuickSort(R，low，pivot pos-1)；
QuickSort(R，pivotpos+1，高)；
}
}//快速排序
int mid partition(seq list R，int i，int j)
{//以三者之法則為基準。
if(R[(i+j)/2]。key & gtR[i]。關鍵)
{交換R[(i+j)/2]和R[I]；}
if(R[i]。key & gtR[j]。關鍵)
{交換R[i]和R[j]；}
if(R[i]。鍵)& ltR[(i+j)/2]。關鍵)
{交換R[i]和R[(I+j)/2]；}
//上面的三個if語句使區間中第壹條記錄的鍵值成為三個鍵的中間值。
返回部分(R，I，j)；//所以我們還是可以用原來的劃分算法。
}
19.對於給定的j(1≤j≤n)，要求在無序記錄區R[1中根據關鍵字從小到大找到第j個位置的記錄..n](即尋找無序集合中的第j個最小元素)，並嘗試利用快速排序的除法思想編寫算法實現上述搜索操作。
答:
int快速排序(SeqList R，int j，int low，int high)
{//Sort R [low...高]迅速
int pivotpos//被分割的基準記錄的位置
if(低& ltHigh){//僅當間隔長度大於1時排序。
pivotpos=Partition(R，low，high)；//分頻R[低...高]
if (pivotpos==j)返回r[j]；
else if(pivot pos & gt；j) return(R，j，low，pivot pos-1)；
else返回quicksort(R，j，pivotpos+1，高)；
}
}//快速排序
20.寫壹個以單鏈表為存儲結構的直接選擇排序算法。
答:
#define int KeyType //將KeyType定義為int類型。
typedef結構節點{
KeyType鍵；//關鍵字字段
其他信息類型信息；//其他信息字段，
結構節點* next//鏈表中的指針字段
} RecNode//記錄節點類型
typedef RecNode * LinkList//單個鏈表由LinkList表示。
void selectsort(鏈表頭)
{RecNode *p，*q，* s；
if(head-& gt；接下來)& amp& amp(頭-& gt；下壹個-& gt；下壹個)
p = head-& gt；接下來；//p指向當前排序順序中最大元素的前任。
while(p->；下壹個)
{ q = p-& gt；接下來；s = p；
while(q)
{ if(q-& gt；key & lts-& gt；key)s = q；
q = q-& gt；接下來；
}//結束時間
交換S節點和P節點的數據；
p = p-& gt；接下來；
}//結束時間
}//endif
}//endsort
21.寫壹個heapInsert(R，key)算法，在堆R中插入關鍵字，保證插入R後還是堆..提示:應該在heap R中增加壹個length屬性描述(即應該重寫本章定義的SeqList的類型描述，以包含length字段)；將鍵插入R中現有元素的尾部(即原堆的長度加上位置1，插入堆的長度加上1)，然後自下而上調整，使插入的關鍵字滿足屬性。請分析壹下算法的時間。
答:
#define n 100//假設文件的長度盡可能長。
typedef int KeyType//將KeyType定義為int類型。
typedef結構節點{
KeyType鍵；//關鍵字字段
其他信息類型信息；//其他信息字段，
} Rectype//記錄節點類型
typedef結構{
Rectype數據[n]；//存儲記錄的空間
int長度；//文件長度
} seqlist
void heapInsert(seqlist *R，KeyType key)
{//原堆元素在r->；data[1]~ R-& gt；數據[R-& gt；長度]，
//將新的關鍵字key插入R-& gt；數據[R-& gt；長度+1]位置，
//帶R-& gt；Data[0]是輔助空間，調整為堆(這裏設為大根堆)。
int large//large指向調整節點左右子節點中關鍵字較大的壹個。
int低，高；//low和high分別指向要調整的堆的第壹條和最後壹條記錄。
int I；
r-& gt；長度++；r-& gt；數據[R-& gt；長度】。key = key//插入新記錄
for(I = R-& gt；長度/2；我& gt0;I-)//構建壹個堆
{
低= I；高= R-& gt；長度；
r-& gt；數據[0]。key = R-& gt；數據[低]。關鍵；//R-& gt；Data[low]是當前調整的節點。
for(大= 2 *低；大號& lt=高；large*=2){
//如果大& gt高表示R-& gt；數據【低】是壹片葉子，調整結束；
//否則將大指針指向R-& gt；數據的左子[低]
if(large & lt；高& amp& ampr-& gt；數據[大]。key & ltr-& gt；數據[大+1]。關鍵)
大++的；//如果R-& gt；數據[低]的右子存在。
//並且關鍵字大於左兄弟，make large指向它。
if(R-& gt；數據[0]。key & ltr-& gt；數據[大]。關鍵)
{ R-& gt；數據[低]。key = R-& gt；數據[大]。關鍵；
低=大；//使低點指向新的調整節點。
}
else break//當前調整節點不小於其子節點的關鍵字，調整完成。
}//結束
r-& gt；數據[低]。key = R-& gt；數據[0]。關鍵；//將調整後的節點放在最後的位置。
}//的結尾
} heap insert結束
算法分析:
如果文件長度為n，算法需要調整n/2遍，總時間復雜度和初始堆差不多，最差時間復雜度為O(nlgn)，輔助空間為O(1)。
22.寫壹個堆構建算法:從壹個空堆開始，依次讀入元素，調用上面問題中的堆插入算法，將元素插入堆中。
答:
void BuildHeap(seqlist *R)
{
KeyType鍵；
r-& gt；長度= 0；//生成壹個空堆
scanf("%d "，& amp關鍵)；//將MAXINT設置為不可能的關鍵字。
而(鍵！=MAXINT)
{
heapInsert(R，key)；
scanf("%d "，& amp關鍵)；
}
}
23.寫壹個堆刪除算法:HeapDelete(R，I)，從堆中刪除R[i]，分析算法時間。建議:首先將R[i]與堆中的最後壹個元素交換，將堆長減少1，然後從位置I向下調整，滿足堆性質。
答:
void HeapDelete(seqlist *R，int i)
{//原堆元素在r->；data[1]~ R-& gt；數據[R-& gt；長度]，
//put R-& gt；數據[i]被刪除，即R->；數據[R-& gt；長度]放入R-& gt；在數據[i]之後，
//put R-& gt；長度減去1，然後調整堆。
//帶R-& gt；Data[0]是輔助空間，調整為堆(這裏設為大根堆)。
int large//large指向調整節點左右子節點中關鍵字較大的壹個。
int低，高；//low和high分別指向要調整的堆的第壹條和最後壹條記錄。
int j；
如果(i & gtr-& gt；長度)
錯誤(“沒有這樣的節點”)；
r-& gt；數據[i]。key = R-& gt；數據[R-& gt；長度】。關鍵；
r-& gt；長度-；r-& gt；數據[R-& gt；長度】。key = key//插入新記錄
for(j = I/2；j & gt0;j-)//構建壹個堆
{
低= j；高= R-& gt；長度；
r-& gt；數據[0]。key = R-& gt；數據[低]。關鍵；//R-& gt；Data[low]是當前調整的節點。
for(大= 2 *低；大號& lt=高；large*=2){
//如果大& gt高表示R-& gt；數據【低】是壹片葉子，調整結束；
//否則將大指針指向R-& gt；數據的左子[低]
if(large & lt；高& amp& ampr-& gt；數據[大]。key & ltr-& gt；數據[大+1]。關鍵)
大++的；//如果R-& gt；數據[低]的右子存在。
//並且關鍵字大於左兄弟，make large指向它。
if(R-& gt；數據[0]。key & ltr-& gt；數據[大]。關鍵)
{ R-& gt；數據[低]。key = R-& gt；數據[大]。關鍵；
低=大；//使低點指向新的調整節點。
}
else break//當前調整節點不小於其子節點的關鍵字，調整完成。
}//結束
r-& gt；數據[低]。key = R-& gt；數據[0]。關鍵；//將調整後的節點放在最後的位置。
}//的結尾
} heap delete結束
24.假設兩個單鏈表中的元素都是升序排列的，試著寫壹個算法，把這兩個有序鏈表合並成壹個升序排列的單鏈表。該算法應該使用原始的鏈表節點空間。
答:
typedef結構節點{
KeyType鍵；//關鍵字字段
其他信息類型信息；//其他信息字段，
結構節點* next//鏈表中的指針字段
} RecNode//記錄節點類型
typedef RecNode * LinkList//單個鏈表由LinkList表示。
無效合並排序(鏈表la，鏈表lb，鏈表lc)
{RecNode *p，*q，*s，* r；
lc = la
p = la//p是la表的掃描指針，指向要比較的節點的前壹個位置。
q=lb->接下來；//q是lb表的掃描指針，指向比較的節點。
while(p->；接下來)& amp& amp(問)
如果(p->；下壹個-& gt；key & lt= q->；關鍵)
p = p-& gt；接下來；
else { s = q；q = q-& gt；接下來；
s-& gt；next = p-& gt；接下來；p->；next = s；//將S節點插入P節點後，
p = s；}
如果(！p->；下壹個)p-& gt；next = q；
免費(磅)；
}
25.設向量A[0..n-1]包含n個不同的整數，每個元素的值在0到n-1之間。試寫壹個時間為O(n)的算法對向量A排序，結果可以輸出到另壹個向量B[0..n-1]。
答:
sort(int *A，int *B)
{//對向量A進行排序，並發送給向量b。
int I；
for(I = 0；我& lt= n-1；i++)
b[A[I]]= A[I]；
}
*26.為壹組按字典順序排列的英語單詞寫壹個基數排序算法。讓所有單詞都由大寫字母組成，最長的單詞有d個字母。提示:所有長度小於d個字母的單詞末尾都要用空格填充，排序時要設置27個方框，分別對應空格，a，B...z分別為。
答:
#define KeySize 10 //設置關鍵字位數d=10。
#定義基數27 //基數rd是27。
typedef RecType數據類型；//將隊列中節點的數據類型更改為RecType類型。
typedef結構節點{
char key[KeySize]；//關鍵字字段
其他信息類型信息；//其他信息字段，
} RecType//記錄節點類型
typedef RecType seqlist[n+1]；
void半徑排序
{
link queue B[基數]；
int I；
for(I = 0；我& lt基數；I++)//框是空的
init queue(& amp；b[I])；
for(I = KeySize-1；我& gt=0;I-){//從低到高做D-trip框排序。
Distribute(R，B，I)；//第壹個KeySize-i傳遞分配
Collect(R，B)；//第壹個KeySize-i集合
}
}
void Distribute(seqlist R，LinkQueue B[]，int j)
{//根據關鍵字的第j個分量分配，開頭的框為空。
int I；
j = KeySize-j；//從低位開始確定關鍵字的位置。
for(I = 0；我& ltn；I++) //依次掃描R[i]並裝箱。
if (R[i]。鍵[j]-' A ' & gt；26)
排隊(& ampB[0]，R[I])；//將第j個關鍵字空格記錄到第0個隊列中。
否則排隊(& ampB[0]，R[R[i]。key[j]-' A '+1])；
}
void Collect(seqlist R，LinkQueue B[])
{
//依次收集每個非空盒子裏的記錄，這個過程結束後所有盒子都是空的。
int i，j；
for(j = 0；j & lt基數；j++)
而(！隊列清空(& ampB[j])
r[i++]=出列(& ampb[j])；//將出列記錄依次輸出到R[i]。
}