严蔚敏《数据结构(c语言版)习题集》算法设计题第十章答案

严蔚敏《数据结构(c语言版)习题集》算法设计题第十章答案  

　　第九章 查找第十章 内部排序

　　void Insert_Sort (SqList &L)//监视哨设在高下标端的插入排序算法

　　{

　　k=L length;

　　for(i=k ;i; i) //从后向前逐个插入排序

　　if(L r[i] key>L r[i+ ] key)

　　{

　　L r[k+ ] key=L r[i] key; //监视哨

　　for(j=i+ ;L r[j] key>L r[i] key;++j)

　　L r[j ] key=L r[j] key; //前移

　　L r[j ] key=L r[k+ ] key; //插入

　　}

　　}//Insert_Sort

　　void BiInsert_Sort(SqList &L)//二路插入排序的算法

　　{

　　int d[MAXSIZE]; //辅助存储

　　x=L r key;d=x;

　　first= ;final= ;

　　for(i= ;i<=L length;i++)

　　{

　　if(L r[i] key>=x) //插入前部

　　{

　　for(j=final;d[j]>L r[i] key;j )

　　d[j+ ]=d[j];

　　d[j+ ]=L r[i] key;

　　final++;

　　}

　　else //插入后部

　　{

　　for(j=first;d[j] [i].key;j++)

　　d[j-1]=d[j];

　　d[(j-2)%MAXSIZE+1]=L.r[i].key;

　　first=(first-2)%MAXSIZE+1; //这种形式的表达式是为了兼顾first=1的情况

　　}

　　}//for

　　for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去

　　L.r[j].key=d[i];

　　}//BiInsert_Sort

　　10.25

　　void SLInsert_Sort(SLList &L)//静态链表的插入排序算法

　　{

　　L.r[0].key=0;L.r[0].next=1;

　　L.r[1].next=0; //建初始循环链表

　　for(i=2;i<=L.length;i++) //逐个插入

　　{

　　p=0;x=L.r[i].key;

　　while(L.r[L.r[p].next].key &&l.r[p].next)

　　p=L.r[p].next;

　　q=L.r[p].next;

　　L.r[p].next=i;

　　L.r[i].next=q;

　　}//for

　　p=L.r[0].next;

　　for(i=1;i ;i++)>

　　{

　　while(p )>

　　q=L.r[p].next;

　　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)//对包含n个元素的数组a进行改进的冒泡排序

　　{

　　change=n-1; //change指示上一趟冒泡中最后发生交换的元素

　　while(change)

　　{

　　for(c=0,i=0;i ;i++)

　　if(a[i]>a[i+1])

　　{

　　a[i]<->a[i+1];

　　c=i+1; //c指示这一趟冒泡中发生交换的元素

　　}

　　change=c;

　　}//while

　　}//Bubble_Sort1

　　10.27

　　void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法

　　{

　　low=0;high=n-1; //冒泡的上下界

　　change=1;

　　while(low &&change)

　　{

　　change=0;

　　for(i=low;i ;i++)>

　　if(a[i]>a[i+1])

　　{

　　a[i]<->a[i+1];

　　change=1;

　　}

　　high--; //修改上界

　　for(i=high;i>low;i--) //从下向上起泡

　　if(a[i]

　　{

　　a[i]<->a[i-1];

　　change=1;

　　}

　　low++; //修改下界

　　}//while

　　}//Bubble_Sort2

　　10.28

　　void Bubble_Sort3(int a[ ],int n)//对上一题的算法进行化简,循环体中只包含一次冒泡

　　{

　　int b[ 3 ]; //b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用

　　d=1;b[0]=0;b[ 2 ]=n-1; //d为冒泡方向的标识,1为向上,-1为向下

　　change=1;

　　while(b[0] [>

　　{

　　change=0;

　　for(i=b[1-d];i!=b[1+d];i+=d) //统一的冒泡算法

　　if((a[i]-a[i+d])*d>0) //注意这个交换条件

　　{

　　a[i]<->a[i+d];

　　change=1;

　　}

　　b[1+d]-=d; //修改边界

　　d*=-1; //换个方向

　　}//while

　　}//Bubble_Sort3

　　10.29

　　void OE_Sort(int a[ ],int n)//奇偶交换排序的算法

　　{

　　change=1;

　　while(change)

　　{

　　change=0;

　　for(i=1;i ;i+=2)>

　　if(a[i]>a[i+1])

　　{

　　a[i]<->a[i+1];

　　change=1;

　　}

　　for(i=0;i ;i+=2)>

　　if(a[i]>a[i+1])

　　{

　　a[i]<->a[i+1];

　　change=1;

　　}

　　}//while

　　}//OE_Sort

　　分析:本算法的结束条件是连续两趟比较无交换发生

　　10.30

　　typedef struct {

　　int low;

　　int high;

　　} boundary; //子序列的上下界类型

　　void QSort_NotRecurve(int SQList &L)//快速排序的非递归算法

　　{

　　low=1;high=L.length;

　　InitStack(S); //S的元素为boundary类型

　　while(low &&!stackempty(s))>

　　{

　　if(high-low>2) //如果当前子序列长度大于3且尚未排好序

　　{

　　pivot=Partition(L,low,high); //进行一趟划分

　　if(high-pivot>pivot-low)

　　{

　　Push(S,{pivot+1,high}); //把长的子序列边界入栈

　　high=pivot-1; //短的子序列留待下次排序

　　}

　　else

　　{

　　Push(S,{low,pivot-1});

　　low=pivot+1;

　　}

　　}//if

　　else if(low &&high-low

　　{

　　Easy_Sort(L,low,high); //直接进行比较排序

　　low=high; //当前子序列标志为已排好序

　　}

　　else //如果当前子序列已排好序但栈中还有未排序的子序列

　　{

　　Pop(S,a); //从栈中取出一个子序列

　　low=a.low;

　　high=a.high;

　　}

　　}//while

　　}//QSort_NotRecurve

　　int Partition(SQList &L,int low,int high)//一趟划分的算法,与书上相同

　　{

　　L.r[0]=L.r[low];

　　pivotkey=L.r[low].key;

　　while(low )

　　{

　　while(low =pivotkey) &&l.r[high].key>

　　high--;

　　L.r[low]=L.r[high];

　　while(low &&l.r[low].key

　　low++;

　　L.r[high]=L.r[low];

　　}//while

　　L.r[low]=L.r[0];

　　return low;

　　}//Partition

　　void Easy_Sort(SQList &L,int low,int high)//对长度小于3的子序列进行比较排序

　　{

　　if(high-low==1) //子序列只含两个元素

　　if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high];

　　else //子序列含有三个元素

　　{

　　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.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)//把数组a中所有值为负的记录调到非负的记录之前

　　{

　　low=0;high=n-1;

　　while(low )

　　{

　　while(low =0) high--; //以0作为虚拟的枢轴记录 &&a[high]>

　　a[low]<->a[high];

　　while(low &&a[low]

　　a[low]<->a[high];

　　}

　　}//Divide

　　10.32

　　typedef enum {RED,WHITE,BLUE} color; //三种颜色

　　void Flag_Arrange(color a[ ],int 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];

　　k--; //这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况

　　}

　　}//Flag_Arrange