《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)參考答案第十章》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)參考答案第十章（15頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、真誠(chéng)為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請(qǐng)指正。
第十章 內(nèi)部排序
10.23
void Insert_Sort1(SqList &L)//監(jiān)視哨設(shè)在高下標(biāo)端的插入排序算法
{
k=L.length;
for(i=k-1;i;--i) //從后向前逐個(gè)插入排序
if(L.r[i].key>L.r[i+1].key)
{
L.r[k+1].key=L.r[i].key; //監(jiān)視哨
for(j=i+1;L.r[j].key>L.r[i].key;++j)
L.r[j-1].key=L.r[j].key; //前移
L.r[j-1].key=L.r[k+1].key
2、; //插入
}
}//Insert_Sort1
10.24
void BiInsert_Sort(SqList &L)//二路插入排序的算法
{
int d[MAXSIZE]; //輔助存儲(chǔ)
x=L.r.key;d=x;
first=1;final=1;
for(i=2;i<=L.length;i++)
{
if(L.r[i].key>=x) //插入前部
{
for(j=final;d[j]>L.r[i].key;j--)
d[j+1]=d[j];
d[j+1]=L.r[i].key;
final++;
}
else //插入后部
{
for(j
3、=first;d[j]
4、].next=1;
L.r[1].next=0; //建初始循環(huán)鏈表
for(i=2;i<=L.length;i++) //逐個(gè)插入
{
p=0;x=L.r[i].key;
while(L.r[L.r[p].next].key
5、xt;
if(p!=i)
{
L.r[p]<->L.r[i];
L.r[i].next=p;
}
p=q;
}//for
}//SLInsert_Sort
10.26
void Bubble_Sort1(int a[ ],int n)//對(duì)包含n個(gè)元素的數(shù)組a進(jìn)行改進(jìn)的冒泡排序
{
change=n-1; //change指示上一趟冒泡中最后發(fā)生交換的元素
while(change)
{
for(c=0,i=0;ia[i+1])
{
a[i]<->a[i+1];
c=i+1; //c指示這一趟冒泡中發(fā)生交換的元
6、素
}
change=c;
}//while
}//Bubble_Sort1
10.27
void Bubble_Sort2(int a[ ],int n)//相鄰兩趟是反方向起泡的冒泡排序算法
{
low=0;high=n-1; //冒泡的上下界
change=1;
while(lowa[i+1])
{
a[i]<->a[i+1];
change=1;
}
high--; //修改上界
for(i=high;i>low
7、;i--) //從下向上起泡
if(a[i]a[i-1];
change=1;
}
low++; //修改下界
}//while
}//Bubble_Sort2
10.28
void Bubble_Sort3(int a[ ],int n)//對(duì)上一題的算法進(jìn)行化簡(jiǎn),循環(huán)體中只包含一次冒泡
{
int b[ 3 ]; //b[0]為冒泡的下界,b[ 2 ]為上界,b[1]無(wú)用
d=1;b[0]=0;b[ 2 ]=n-1; //d為冒泡方向的標(biāo)識(shí),1為向上,-1為向下
change=1;
while(b[0]
8、change)
{
change=0;
for(i=b[1-d];i!=b[1+d];i+=d) //統(tǒng)一的冒泡算法
if((a[i]-a[i+d])*d>0) //注意這個(gè)交換條件
{
a[i]<->a[i+d];
change=1;
}
b[1+d]-=d; //修改邊界
d*=-1; //換個(gè)方向
}//while
}//Bubble_Sort3
10.29
void OE_Sort(int a[ ],int n)//奇偶交換排序的算法
{
change=1;
while(change)
{
change=0;
for(i=1;i
9、+=2) //對(duì)所有奇數(shù)進(jìn)行一趟比較
if(a[i]>a[i+1])
{
a[i]<->a[i+1];
change=1;
}
for(i=0;ia[i+1])
{
a[i]<->a[i+1];
change=1;
}
}//while
}//OE_Sort
分析:本算法的結(jié)束條件是連續(xù)兩趟比較無(wú)交換發(fā)生
10.30
typedef struct {
int low;
int high;
} boundary; //子序列的上下界類(lèi)型
void QSor
10、t_NotRecurve(int SQList &L)//快速排序的非遞歸算法
{
low=1;high=L.length;
InitStack(S); //S的元素為boundary類(lèi)型
while(low2) //如果當(dāng)前子序列長(zhǎng)度大于3且尚未排好序
{
pivot=Partition(L,low,high); //進(jìn)行一趟劃分
if(high-pivot>pivot-low)
{
Push(S,{pivot+1,high}); //把長(zhǎng)的子序列邊界入棧
high=pi
11、vot-1; //短的子序列留待下次排序
}
else
{
Push(S,{low,pivot-1});
low=pivot+1;
}
}//if
else if(low
12、/QSort_NotRecurve
int Partition(SQList &L,int low,int high)//一趟劃分的算法,與書(shū)上相同
{
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(low=pivotkey)
high--;
L.r[low]=L.r[high];
while(low
13、ow]=L.r[0];
return low;
}//Partition
void Easy_Sort(SQList &L,int low,int high)//對(duì)長(zhǎng)度小于3的子序列進(jìn)行比較排序
{
if(high-low==1) //子序列只含兩個(gè)元素
if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high];
else //子序列含有三個(gè)元素
{
if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
if(L.r[low+1].key>L.r[high].key) L
14、.r[low+1]<->L.r[high];
if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
}
}//Easy_Sort
10.31
void Divide(int a[ ],int n)//把數(shù)組a中所有值為負(fù)的記錄調(diào)到非負(fù)的記錄之前
{
low=0;high=n-1;
while(low=0) high--; //以0作為虛擬的樞軸記錄
a[low]<->a[high];
while(low
15、;
a[low]<->a[high];
}
}//Divide
10.32
typedef enum {RED,WHITE,BLUE} color; //三種顏色
void Flag_Arrange(color a[ ],int n)//把由三種顏色組成的序列重排為按照紅,白,藍(lán)的順序排列
{
i=0;j=0;k=n-1;
while(j<=k)
switch(a[j])
{
case RED:
a[i]<->a[j];
i++;
j++;
break;
case WHITE:
j++;
break;
case BLUE:
a[j]<->a[k]
16、;
k--; //這里沒(méi)有j++;語(yǔ)句是為了防止交換后a[j]仍為藍(lán)色的情況
}
}//Flag_Arrange
分析:這個(gè)算法中設(shè)立了三個(gè)指針.其中,j表示當(dāng)前元素;i以前的元素全部為紅色;k以后的元素全部為藍(lán)色.這樣,就可以根據(jù)j的顏色,把其交換到序列的前部或者后部.
10.33
void LinkedList_Select_Sort(LinkedList &L)//單鏈表上的簡(jiǎn)單選擇排序算法
{
for(p=L;p->next->next;p=p->next)
{
q=p->next;x=q->data;
for(r=q,s=q;r->next;r=r->nex
17、t) //在q后面尋找元素值最小的結(jié)點(diǎn)
if(r->next->datanext->data;
s=r;
}
if(s!=q) //找到了值比q->data更小的最小結(jié)點(diǎn)s->next
{
p->next=s->next;s->next=q;
t=q->next;q->next=p->next->next;
p->next->next=t;
} //交換q和s->next兩個(gè)結(jié)點(diǎn)
}//for
}//LinkedList_Select_Sort
10.34
void Build_Heap(Heap &H,int n)//從低下標(biāo)到高下標(biāo)逐
18、個(gè)插入建堆的算法
{
for(i=2;iH.r[k].key)
H.r[j]<->H.r[k];
j=k;
}
}//for
}//Build_Heap
10.35
void TriHeap_Sort(Heap &H)//利用三叉樹(shù)形式的堆進(jìn)行排序的算法
{
for(i=H.length/3;i>0;i--)
Heap_Adjust(H,i,H.length);
for(i=H
19、.length;i>1;i--)
{
H.r[1]<->H.r[i];
Heap_Adjust(H,1,i-1);
}
}//TriHeap_Sort
void Heap_Adjust(Heap &H,int s,int m)//順序表H中,H.r[s+1]到H.r[m]已經(jīng)是堆,把H.r[s]插入并調(diào)整成堆
{
rc=H.r[s];
for(j=3*s-1;j<=m;j=3*j-1)
{
if(j
20、;
s=j;
}
H.r[s]=rc;
}//Heap_Adjust
分析:本算法與課本上的堆排序算法相比,只有兩處改動(dòng):1.建初始堆時(shí),i的上限從H.length/3開(kāi)始(為什么?) 2.調(diào)整堆的時(shí)候,要從結(jié)點(diǎn)的三個(gè)孩子結(jié)點(diǎn)中選擇最大的那一個(gè),最左邊的孩子的序號(hào)的計(jì)算公式為j=3*s-1(為什么?)
10.36
void Merge_Sort(int a[ ],int n)//歸并排序的非遞歸算法
{
for(l=1;l
21、i; //求出待歸并的兩段的上下界
end1=start1+l-1;
start2=end1+1;
end2=(start2+l-1)>(n-1)?(n-1):(start2+l-1);//注意end2可能超出邊界
Merge(a,start1,end1,start2,end2); //歸并
}
}//Merge_Sort
void Merge(int a[ ],int s1,int e1,int s2,int e2)//將有序子序列a[s1]到a[e1]和a[s2]到a[e2]歸并為有序序列a[s1]到a[e2]
{
int b[MAXSIZE]; //設(shè)立輔助存儲(chǔ)數(shù)組b
22、
for(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++)
{
if(a[i]
23、;l*=2) //l為一趟歸并段的段長(zhǎng)
for(p=L->next,e2=p;p->next;p=e2)
{
for(i=1,q=p;i<=l&&q->next;i++,q=q->next);
e1=q;
for(i=1;i<=l&&q->next;i++,q=q->next);
e2=q; //求出兩個(gè)待歸并子序列的尾指針
if(e1!=e2) LinkedList_Merge(L,p,e1,e2); //歸并
}
}//LinkedList_Merge_Sort1
void LinkedList_Merge(LinkedList &L,LNode *p,LNode *
24、e1,LNode *e2)//對(duì)鏈表上的子序列進(jìn)行歸并,第一個(gè)子序列是從p->next到e1,第二個(gè)是從e1->next到e2
{
q=p->next;r=e1->next; //q和r為兩個(gè)子序列的起始位置
while(q!=e1->next&&r!=e2->next)
{
if(q->datadata) //選擇關(guān)鍵字較小的那個(gè)結(jié)點(diǎn)接在p的后面
{
p->next=q;p=q;
q=q->next;
}
else
{
p->next=r;p=r;
r=r->next;
}
}//while
while(q!=e1->next) //接上剩余部分
{
25、
p->next=q;p=q;
q=q->next;
}
while(r!=e2->next)
{
p->next=r;p=r;
r=r->next;
}
}//LinkedList_Merge
10.38
void LinkedList_Merge_Sort2(LinkedList &L)//初始?xì)w并段為最大有序子序列的歸并排序,采用鏈表存儲(chǔ)結(jié)構(gòu)
{
LNode *end[MAXSIZE]; //設(shè)立一個(gè)數(shù)組來(lái)存儲(chǔ)各有序子序列的尾指針
for(p=L->next->next,i=0;p;p=p->next) //求各有序子序列的尾指針
if(!p->next
26、||p->data>p->next->data) end[i++]=p;
while(end[0]->next) //當(dāng)不止一個(gè)子序列時(shí)進(jìn)行兩兩歸并
{
j=0;k=0; //j:當(dāng)前子序列尾指針存儲(chǔ)位置;k:歸并后的子序列尾指針存儲(chǔ)位置
for(p=L->next,e2=p;p->next;p=e2) //兩兩歸并所有子序列
{
e1=end[j];e2=end[j+1]; //確定兩個(gè)子序列
if(e1->next) LinkedList_Merge(L,p,e1,e2); //歸并
end[k++]=e2; //用新序列的尾指針取代原來(lái)的尾指針
j+=2; //轉(zhuǎn)到后面
27、兩個(gè)子序列
}
}//while
}//LinkedList_Merge_Sort2
void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//對(duì)鏈表上的子序列進(jìn)行歸并,第一個(gè)子序列是從p->next到e1,第二個(gè)是從e1->next到e2
{
q=p->next;r=e1->next;
while(q!=e1->next&&r!=e2->next)
{
if(q->datadata)
{
p->next=q;p=q;
q=q->next;
}
else
{
p->next=r
28、;p=r;
r=r->next;
}
}//while
while(q!=e1->next)
{
p->next=q;p=q;
q=q->next;
}
while(r!=e2->next)
{
p->next=r;p=r;
r=r->next;
}
}//LinkedList_Merge,與上一題完全相同
10.39
void SL_Merge(int a[ ],int l1,int l2)//把長(zhǎng)度分別為l1,l2且l1^2<(l1+l2)的兩個(gè)有序子序列歸并為有序序列
{
start1=0;start2=l1; //分別表示序列1和序列2的剩余未歸
29、并部分的起始位置
for(i=0;i
30、間的子序列循環(huán)右移k位,算法原理參見(jiàn)5.18
{
len=end-start+1;
for(i=1;i<=k;i++)
if(len%i==0&&k%i==0) p=i; //求len和k的最大公約數(shù)p
for(i=0;i
31、}//for
}//RSh
10.40
書(shū)后給出的解題思路在表述上存在問(wèn)題,無(wú)法理解.比如說(shuō),"把第一個(gè)序列劃分為兩個(gè)子序列,使其中的第一個(gè)子序列含有s1個(gè)記錄,0<=s1
32、
for(i=0,j=0;i<1000;j++) //將散列收回a中
if(b[j])
{
for(x=b[j],k=j;b[k];k=(k+1)%10000)
if(b[k]==x)
{
a[i++]=x;
b[k]=0;
}
}//if
}//Hash_Sort
10.42
typedef struct {
int gt; //大于該記錄的個(gè)數(shù)
int lt; //小于該記錄的個(gè)數(shù)
} place; //整個(gè)序列中比某個(gè)關(guān)鍵字大或小的記錄個(gè)數(shù)
int Get_Mid(int a[ ],int n)//求一個(gè)序列的中值記錄
33、的位置
{
place b[MAXSIZE];
for(i=0;ia[i]) b[i].gt++;
else if(a[j]
34、
10.43
void Count_Sort(int a[ ],int n)//計(jì)數(shù)排序算法
{
int c[MAXSIZE];
for(i=0;i
35、<->a[min]; //與第i個(gè)記錄交換
c[min]=INFINITY; //修改該記錄的c值為無(wú)窮大以便下一次選取
}
}//Count_Sort
10.44
void Enum_Sort(int a[ ],int n)//對(duì)關(guān)鍵字只能取v到w之間任意整數(shù)的序列進(jìn)行排序
{
int number[w+1],pos[w+1];
for(i=0;i
36、or(i=0;i
37、//利用計(jì)數(shù)實(shí)現(xiàn)基數(shù)排序,其中關(guān)鍵字為3位自然數(shù),共有n個(gè)自然數(shù)
{
int number ,pos ;
num c[MAXSIZE];
for(j=0;j<3;j++) //依次對(duì)個(gè)位,十位和百位排序
{
for(i=0;i
38、[i]=c[i];
}//for
}//Enum_Radix_Sort
分析:計(jì)數(shù)排序是一種穩(wěn)定的排序方法.正因?yàn)槿绱?它才能夠被用來(lái)實(shí)現(xiàn)基數(shù)排序.
10.46
typedef struct {
int key;
int pos;
} Shadow; //影子序列的記錄類(lèi)型
void Shadow_Sort(Rectype b[ ],Rectype &a[ ],int n)//對(duì)元素很大的記錄序列b進(jìn)行排序,結(jié)果放入a中,不移動(dòng)元素
{
Shadow d[MAXSIZE];
for(i=0;i1&&change;i--) //對(duì)影子序列執(zhí)行冒泡排序
{
change=0;
for(j=0;jd[j+1].key)
{
d[j]<->d[j+1];
change=1;
}
}//for
for(i=0;i
嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)參考答案第十章
