数据结构课后习题答案第八章

《数据结构课后习题答案第八章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章排序（参考答案）本章所用数据结构#defineN待排序记录的个数typedefstruct{intkey;ElemTypeother;}rectype;rectyper[n+1];//r为结构体数组8.2稳定排序有：直接插入排序、起泡排序、归并排序、基数排序不稳定排序有：希尔排序、直接选择排序、堆排序希尔排序例：49，38，49，90，70，25直接选择排序例：2，2，1堆排序例：1，2，28.3voidStlinkedInsertSort(s,n);//对静态链表s[1..n]进行表插入排序，并调整结果，使表物理上排序{

2、#defineMAXINT机器最大整数typedefstruct{intkey;intnext;}rec;recs[n+1];//s为结构体数组s[0].key=maxint;s[1].next=0;//头结点和第一个记录组成循环链表i=2;//从第2个元素开始，依次插入有序链表中while(i<=n){q=0;p=s[0].next;//p指向当前最小元素，q是p的前驱while(p!=0&&s[p].key

3、//将第个元素链入i++；}//while(i<=n)静态链表的插入//以下是重排静态链表，使之物理有序i=1;p=s[0].next;while(i<=n){WHILE(p

4、le(exchange){exchange=0;//假定本趟无交换for(j=n-i+1j>=i+1;j--)//向前起泡，一趟有一最小冒出if(r[j]r[j-1];exchange=1;}//有交换for(j=i+1;j>=n-I;j++)//向后起泡，一趟有一最大沉底if(r[j]>r[j+1]){r[j]ß>r[j+1];exchange=1;}//有交换i++;}//endofWHILEexchange}//算法结束8.5（1）在n=7时，最好情况下进行10次比较。6次比较完成第一趟快速排

5、序，将序列分成相等程度的序列（各3个元素），再各进行2次比较，完成全部排序。（2）最好的初始排列：4，1，3，2，6，5，78.6voidQuickSort(rectyper[n+1];intn)//对r[1..n]进行快速排序的非递归算法{typedefstruct{intlow,high;}nodenodes[n+1]；inttop;intquickpass(rectyper[],int,int);//函数声明top=1;s[top].low=1;s[top].high=n;while(top>0){ss=s[top].lo

6、w;tt=s[top].high;top--;if(ss1){top++;s[top].low=ss;s[top].high=k-1;}if(tt-k>1){top++;s[top].low=k+1;s[top].high=tt;}}}//算法结束intquickpass(rectyper[];ints,t){i=s;j=t;rp=r[i];x=r[i].key;while（i

7、]=r[j];while(i=r[j].key)i++;if(i

8、high=n;ss=s[top].low;tt=s[top].high;top--;flag=true;while(flag

9、

10、top>0){k=quickpass(r,ss,tt);if(k-ss>tt-k)//一趟排序后分割成左右两部分{if(k-ss>1)