《徐镜春数据结构习题10》由会员分享，可在线阅读，更多相关《徐镜春数据结构习题10（35页珍藏版）》请在金锄头文库上搜索。
1、10.7(1)假设初始序列为：k01,k02,k03,k04,k05,k06,k07最好情况下，经过第一趟快速排序后得到序列：k11,k12,k13,k14,k15,k16,k17其中，k14=k01，k11,k12,k13=k14比较次数为 6 次。经过第二趟快速排序后得到序列：k21,k22，k23,k24,k25,k26,k27其中，k24=k14=k01; k22=k11,k21=k22; k26=k15,k25=k26比较次数为 4 次，合计 10 次比较。（2）4，1，3，7，6，5，210.16将每一个关键字 ki0,nk)看作 ki=kk-1,ink-1+kk-2,ink-2+
2、.+k1,in+k0,i其中，kj,i0,n) j=k-1,k-2,.,1,0即，将 ki 看作是 k 为 n 进制数（kk-1,ikk-2,i.k1,ik0,i）利用基数排序所需时间为 O(k(n+rd)=O(k(n+n)=O(2kn)=O(kn)10.25void SLL-Insert(SLinkListType SL.r0.next=0;for (i=1; i=1 while (p-next)while (p-next-data=p-next) p=p-next;EnQueue(Q,p); p=p-next;/将指向各有序子序列的头结点的指针入循环队列while (!QueueEmpty
3、(Q)DeQueue(Q,p1);if (!QueueEmpty(Q)DeQueue(Q,q1);if (p1-next-datanext-data)EnQueue(Q,p1); p1=p1-next; r1=p1;else EnQueue(Q,q1); q1=q1-next; r1=q1;while (p1-next-data=p1-data p=p-next; r1=r1-next;else r1-next=q1-next; q=q-next; r1=r1-next;if (p1-next-datap-data)r1-next=p1-next;else r1-next=p1-next;/i
4、f/while/MergeSort(以下内容来自 http:/)第十章 内部排序10.23void Insert_Sort1(SqList for(i=k-1;i;-i) /从后向前逐个插入排序if(L.ri.keyL.ri+1.key)L.rk+1.key=L.ri.key; /监视哨for(j=i+1;L.rj.keyL.ri.key;+j)L.rj-1.key=L.rj.key; /前移L.rj-1.key=L.rk+1.key; /插入/Insert_Sort110.24void BiInsert_Sort(SqList /辅助存储x=L.r.key;d=x;first=1;final
5、=1;for(i=2;i=x) /插入前部for(j=final;djL.ri.key;j-)dj+1=dj;dj+1=L.ri.key;final+;else /插入后部for(j=first;djL.ri;L.ri.next=p;p=q;/for/SLInsert_Sort10.26void Bubble_Sort1(int a ,int n)/对包含 n 个元素的数组 a 进行改进的冒泡排序change=n-1; /change 指示上一趟冒泡中最后发生交换的元素while(change)for(c=0,i=0;iai+1)aiai+1;c=i+1; /c 指示这一趟冒泡中发生交换的元素
6、change=c;/while/Bubble_Sort110.27void Bubble_Sort2(int a ,int n)/相邻两趟是反方向起泡的冒泡排序算法low=0;high=n-1; /冒泡的上下界change=1;while(lowai+1)aiai+1;change=1;high-; /修改上界for(i=high;ilow;i-) /从下向上起泡if(aiai-1;change=1;low+; /修改下界/while/Bubble_Sort210.28void Bubble_Sort3(int a ,int n)/对上一题的算法进行化简,循环体中只包含一次冒泡int b 3
7、; /b 0 为冒泡的下界,b 2 为上界,b 1 无用d=1;b 0 =0;b 2 =n-1; /d 为冒泡方向的标识,1 为向上,-1 为向下change=1;while(b 0 0) /注意这个交换条件aiai+d;change=1;b1+d-=d; /修改边界d*=-1; /换个方向/while/Bubble_Sort310.29void OE_Sort(int a ,int n)/奇偶交换排序的算法change=1;while(change) /本算法的结束条件是连续两趟无交换发生change=0;for(i=1;iai+1)aiai+1;change=1;for(i=0;iai+1
8、)aiai+1;change=1;/while/OE_Sort10.30typedef struct int low;int high; boundary; /子序列的上下界类型void QSort_NotRecurve(int SQList high=L.length;InitStack(S); /S 的元素为 boundary 类型while(low2) /如果当前子序列长度大于 3 且尚未排好序pivot=Partition(L,low,high); /进行一趟划分if(high-pivotpivot-low)Push(S,pivot+1,high); /把长的子序列边界入栈high=p
9、ivot-1; /短的子序列留待下次排序elsePush(S,low,pivot-1);low=pivot+1;/ifelse if(low=pivotkey)high-;L.rlow=L.rhigh;while(lowL.rhigh.key) L.rlowL.rhigh;else /子序列含有三个元素if(L.rlow.keyL.rlow+1.key) L.rlowL.rlow+1;if(L.rlow+1.keyL.rhigh.key) L.rlow+1L.rhigh;if(L.rlow.keyL.rlow+1.key) L.rlowL.rlow+1;/Easy_Sort10.31void
10、Divide(int a ,int n)/把数组 a 中所有值为负的记录调到非负的记录之前low=0;high=n-1;while(low=0) high-; /以 0 作为虚拟的枢轴记录alowahigh;while(lowahigh;/Divide10.32typedef enum RED,WHITE,BLUE color; /三种颜色void Flag_Arrange(color a ,int n)/把由三种颜色组成的序列重排为按照红,白,蓝的顺序排列i=0;j=0;k=n-1;while(jaj;i+;j+;break;case WHITE:j+;break;case BLUE:aja
11、k;k-; /这里没有 j+;语句是为了防止交换后 aj仍为蓝色的情况/Flag_Arrange分析:这个算法中设立了三个指针.其中,j 表示当前元素;i 以前的元素全部为红色;k 以后的元素全部为蓝色.这样,就可以根据 j 的颜色,把其交换到序列的前部或者后部.10.33void LinkedList_Select_Sort(LinkedList p-next-next;p=p-next)q=p-next;x=q-data;for(r=q,s=q;r-next;r=r-next) /在 q 后面寻找元素值最小的结点if(r-next-datanext-data;s=r;if(s!=q) /找
12、到了值比 q-data 更小的最小结点 s-nextp-next=s-next;s-next=q;t=q-next;q-next=p-next-next;p-next-next=t; /交换 q 和 s-next 两个结点/for/LinkedList_Select_Sort10.34void Build_Heap(Heap iH.rk.key)H.rjH.rk;j=k;/for/Build_Heap10.35void TriHeap_Sort(Heap i0;i-)Heap_Adjust(H,i,H.length);for(i=H.length;i1;i-)H.r 1 H.ri;Heap_A
13、djust(H,1,i-1);/TriHeap_Sortvoid Heap_Adjust(Heap for(j=3*s-1;j(n-1)?(n-1):(start2+l-1);/注意 end2可能超出边界Merge(a,start1,end1,start2,end2); /归并/Merge_Sortvoid Merge(int a ,int s1,int e1,int s2,int e2)/将有序子序列 as1到 ae1和 as2到 ae2归并为有序序列 as1到 ae2int bMAXSIZE; /设立辅助存储数组 bfor(i=s1,j=s2,k=s1;inext,e2=p;p-next;
14、p=e2)for(i=1,q=p;inext;i+,q=q-next);e1=q;for(i=1;inext;i+,q=q-next);e2=q; /求出两个待归并子序列的尾指针if(e1!=e2) LinkedList_Merge(L,p,e1,e2); /归并/LinkedList_Merge_Sort1void LinkedList_Merge(LinkedList r=e1-next; /q 和 r 为两个子序列的起始位置while(q!=e1-nextp=q;q=q-next;elsep-next=r;p=r;r=r-next;/whilewhile(q!=e1-next) /接上剩余部分p-next=q;p=q;q=q-next;while(r!=e2-next)p-next=r;p=r;r=r-next;/LinkedList_Merge10.38void LinkedList_Merge_Sort2(LinkedList /设立一个数组来存储各有序子序列的尾指针for(p=L-next-next,i=0;p;p=p-next) /求各有序子序列的尾指针if(!p-next|p-datap-next-data) endi+=p;while(end 0 -next) /当不止一个子序列时进行两两归并j=0;k=0; /j:当前子序列尾指针
