作者:來源: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]。
}