當前位置:成語大全網 - 新華字典 - 用算法實現:單鏈表和順序表刪除。刪除順序表中值相同的多余結點

用算法實現:單鏈表和順序表刪除。刪除順序表中值相同的多余結點

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

作者: 來源: 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;i>=0;i--) //在有序區中依次插入R[n-2]..R[0]

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

{

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

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

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

j++;

}while(R[j].key<R[n].key]);

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

}//endif

}//InsertSort.

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

解:

#define int KeyType //定義KeyType 為int型

typedef struct node{

KeyType key; //關鍵字域

OtherInfoType info; //其它信息域,

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

}RecNode; //記錄結點類型

typedef RecNode * LinkList ; //單鏈表用LinkList表示

void InsertSort(LinkList head)

{//鏈式存儲結構的直接插入排序算法,head是帶頭結點的單鏈表

RecNode *p,*q,*s;

if ((head->next)&&(head->next->next))//當表中含有結點數大於1

{

p=head->next->next;//p指向第二個節點

head->next=NULL;

q=head;//指向插入位置的前驅節點

while(p)&&(q->next)&&(p->key<q->next->key)

q=q->next;

if (p)

{s=p;p=p->next;// 將要插入結點摘下

s->next=q->next;//插入合適位置:q結點後

q->next=s;

}

}

}

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

解:

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

void ReSort(SeqList R)

{//重排數組,使負值關鍵字在前

int i=1,j=n; //數組存放在R[1..n]中

while (i<j) //i<j表示尚未掃描完畢

{ while(i<j&&R[i].key<0) //遇到負數則繼續掃描

i++;

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

while(i<j&&R[j].key>=0)// 遇到正數則繼續向左掃描

j--;

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

}//endwhile

}//ReSort

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

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

解:

算法如下:

void BubbleSort(SeqList R)

{//R[1..n]是待排序文件,雙向掃描冒泡排序

int i,j,k;

Boolean exchange; //交換標記

i=n;j=1;

exchange=TRUE;

while (i>j)&&(exchange)

{k=i-1;exchange=FALSE;

while (k>=j)//由下往上掃描

{if (r[k]>r[k+1])

{r[0]=r[k];r[k]=r[k+1];r[k+1]=r[k];exchange=TRUE;//交換

}//endif

k--;

}//endwhile

if (exchange)

{exchange=FALSE;

j++;k=j+1;

while(k<=i)//由上往下掃描

{if (r[k]<r[k-1])

{r[0]=r[k];r[k]=r[k-1];r[k-1]=r[k];exchange=TRUE;//交換

}//endif

k++;

}endwhile

i--;

}//endif

}endwhile

}//endsort

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

void BubbleSort(int A[],int n)

//不妨設A[0..n-1]是整型向量

int lastExchange,j,i=n-1;

while (i>0)

lastExchange=0;

for(j=0;j<i;j++)//從上往下掃描A[0..i]

if(A[j+1]<A[j]){

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

lastExchange=j;

}

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

}//endwhile

}//BubbleSort

解:算法如下:

void BubbleSort(int A[],int n)

//不妨設A[0..n-1]是整型向量

int lastExchange,j,i=0;

while (i<n) //這壹條很重要,如不改為這樣,算法將無限循環下去

lastExchange=n;

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

if(A[j-1]<A[j]){

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

lastExchange=j;

}

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

}//endwhile

}//BubbleSort

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

解:

改寫後的算法如下:

void QuickSort(SeqList R,int low ,int high)

{//對R[low..high]快速排序

int pivotpos;

if(high-low<=2)//若當前區內元素少於3個

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

InsertSort(R,low,high);

}

else

{

pivotpos=midPartion(R,low,high);

QuickSort(R,low,pivotpos-1);

QuickSort(R,pivotpos+1,high);

}

}//QuickSort

int midPartion(SeqList R,int i, int j)

{//三者取中規則定基準

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

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

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

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

if(R[i].key)<R[(i+j)/2].key)

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

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

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

}

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

答:

int QuickSort(SeqList R,int j,int low,int high)

{ //對R[low..high]快速排序

int pivotpos; //劃分後的基準記錄的位置

if(low<high){//僅當區間長度大於1時才須排序

pivotpos=Partition(R,low,high); //對R[low..high]做劃分

if (pivotpos==j) return r[j];

else if (pivotpos>j) return(R,j,low,pivotpos-1);

else return quicksort(R,j,pivotpos+1,high);

}

} //QuickSort

20.以單鏈表為存儲結構,寫壹個直接選擇排序算法。

答:

#define int KeyType //定義KeyType 為int型

typedef struct node{

KeyType key; //關鍵字域

OtherInfoType info; //其它信息域,

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

}RecNode; //記錄結點類型

typedef RecNode * LinkList ; //單鏈表用LinkList表示

void selectsort(linklist head)

{RecNode *p,*q,*s;

if(head->next)&&(head->next->next)

{p=head->next;//p指向當前已排好序最大元素的前趨

while (p->next)

{q=p->next;s=p;

while(q)

{if (q->key<s->key) s=q;

q=q->next;

}//endwhile

交換s結點和p結點的數據;

p=p->next;

}//endwhile

}//endif

}//endsort

21.寫壹個heapInsert(R,key)算法,將關鍵字插入到堆R中去,並保證插入R後仍是堆。提示:應為堆R增加壹個長度屬性描述(即改寫本章定義的SeqList類型描述,使其含有長度域);將key先插入R中已有元素的尾部(即原堆的長度加1的位置,插入後堆的長度加1),然後從下往上調整,使插入的關鍵字滿足性質。請分析算法的時間。

答:

#define n 100//假設文件的最長可能長度

typedef int KeyType; //定義KeyType 為int型

typedef struct node{

KeyType key; //關鍵字域

OtherInfoType info; //其它信息域,

}Rectype; //記錄結點類型

typedef struct{

Rectype data[n] ; //存放記錄的空間

int length;//文件長度

}seqlist;

void heapInsert(seqlist *R,KeyType key)

{//原有堆元素在R->data[1]~R->data[R->length],

//將新的關鍵字key插入到R->data[R->length+1]位置後,

//以R->data[0]為輔助空間,調整為堆(此處設為大根堆)

int large;//large指向調整結點的左右孩子中關鍵字較大者

int low,high;//low和high分別指向待調整堆的第壹個和最後壹個記錄

int i;

R->length++;R->data[R->length].key=key;//插入新的記錄

for(i=R->length/2;i>0;i--)//建堆

{

low=i;high=R->length;

R->data[0].key=R->data[low].key;//R->data[low]是當前調整的結點

for(large=2*low;large<=high;large*=2){

//若large>high,則表示R->data[low]是葉子,調整結束;

//否則令large指向R->data[low]的左孩子

if(large<high&&R->data[large].key<R->data[large+1].key)

large++;//若R->data[low]的右孩子存在

//且關鍵字大於左兄弟,則令large指向它

if (R->data[0].key<R->data[large].key)

{ R->data[low].key= R->data[large].key;

low=large;//令low指向新的調整結點

}

else break;//當前調整結點不小於其孩子結點的關鍵字,結束調整

}//endfor

R->data[low].key=R->data[0].key;//將被調整結點放入最終的位置上

}//end of for

}end of heapinsert

算法分析:

設文件長度為n,則該算法需進行n/2趟調整,總的時間復雜度與初建堆類似,最壞時間復雜度為O(nlgn),輔助空間為O(1).

22.寫壹個建堆算法:從空堆開始,依次讀入元素調用上題中堆插入算法將其插入堆中。

答:

void BuildHeap(seqlist *R)

{

KeyType key;

R->length=0;//建壹個空堆

scanf("%d",&key);//設MAXINT為不可能的關鍵字

while(key!=MAXINT)

{

heapInsert(R,key);

scanf("%d",&key);

}

}

23.寫壹個堆刪除算法:HeapDelete(R,i),將R[i]從堆中刪去,並分析算法時間,提示:先將R[i]和堆中最後壹個元素交換,並將堆長度減1,然後從位置i開始向下調整,使其滿足堆性質。

答:

void HeapDelete(seqlist *R,int i)

{//原有堆元素在R->data[1]~R->data[R->length],

//將R->data[i]刪除,即將R->data[R->length]放入R->data[i]中後,

//將R->length減1,再進行堆的調整,

//以R->data[0]為輔助空間,調整為堆(此處設為大根堆)

int large;//large指向調整結點的左右孩子中關鍵字較大者

int low,high;//low和high分別指向待調整堆的第壹個和最後壹個記錄

int j;

if (i>R->length)

Error("have no such node");

R->data[i].key=R->data[R->length].key;

R->length--;R->data[R->length].key=key;//插入新的記錄

for(j=i/2;j>0;j--)//建堆

{

low=j;high=R->length;

R->data[0].key=R->data[low].key;//R->data[low]是當前調整的結點

for(large=2*low;large<=high;large*=2){

//若large>high,則表示R->data[low]是葉子,調整結束;

//否則令large指向R->data[low]的左孩子

if(large<high&&R->data[large].key<R->data[large+1].key)

large++;//若R->data[low]的右孩子存在

//且關鍵字大於左兄弟,則令large指向它

if (R->data[0].key<R->data[large].key)

{ R->data[low].key= R->data[large].key;

low=large;//令low指向新的調整結點

}

else break;//當前調整結點不小於其孩子結點的關鍵字,結束調整

}//endfor

R->data[low].key=R->data[0].key;//將被調整結點放入最終的位置上

}//end of for

}end of HeapDelete

24.已知兩個單鏈表中的元素遞增有序,試寫壹算法將這兩個有序表歸並成壹個遞增有序的單鏈表。算法應利用原有的鏈表結點空間。

答:

typedef struct node{

KeyType key; //關鍵字域

OtherInfoType info; //其它信息域,

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

}RecNode; //記錄結點類型

typedef RecNode * LinkList ; //單鏈表用LinkList表示

void mergesort(LinkList la,LinkList lb,LinkList lc)

{RecNode *p,*q,*s,*r;

lc=la;

p=la;//p是la表掃描指針,指向待比較結點的前壹位置

q=lb->next;//q是lb表掃描指針,指向比較的結點

while(p->next)&&(q)

if (p->next->key<=q->key)

p=p->next;

else {s=q;q=q->next;

s->next=p->next;p->next=s;//將s結點插入到p結點後

p=s;}

if (!p->next) p->next=q;

free(lb);

}

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;i<=n-1;i++)

B[A[i]]=A[i];

}

*26.寫壹組英文單詞按字典序排列的基數排序算法。設單詞均由大寫字母構成,最長的單詞有d個字母。提示:所有長度不足d個字母的單詞都在尾處補足空格,排序時設置27個箱子,分別與空格,A,B...Z對應。

答:

#define KeySize 10 //設關鍵字位數d=10

#define Radix 27 //基數rd為27

typedef RecType DataType;//將隊列中結點數據類型改為RecType類型

typedef struct node{

char key[KeySize]; //關鍵字域

OtherInfoType info; //其它信息域,

}RecType; //記錄結點類型

typedef RecType seqlist[n+1];

void RadixSort(seqlist R)

{

LinkQueue B[Radix];

int i;

for(i=0;i<Radix;i++)//箱子置空

InitQueue(&B[i]);

for(i=KeySize-1;i>=0;i--){//從低位到高位做d趟箱排序

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;i<n;i++) //依次掃描R[i],將其裝箱

if (R[i].key[j]-'A'>26)

EnQueue(&B[0],R[i]);//將第j位關鍵字位空格的記錄入第0個隊列

else EnQueue(&B[0],R[R[i].key[j]-'A'+1]);

}

void Collect(seqlist R,LinkQueue B[])

{

//依次將各非空箱子中的記錄收集起來,本過程結束,各箱子都變空

int i,j;

for (j=0;j<Radix;j++)

while(!QueueEmpty(&B[j]))

R[i++]=DeQueue(&B[j]);//將出隊記錄依次輸出到R[i]中

}