當前位置:成語大全網 - 漢語詞典 - 算法:刪除單鏈表和順序表。刪除序列表中具有相同值的冗余節點。

算法:刪除單鏈表和順序表。刪除序列表中具有相同值的冗余節點。

第八章排序(算法設計)練習答案

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

}