发布时间 : 星期三 文章第十章排序参考答案更新完毕开始阅读f1d379da50e2524de5187ecb
直到满足小堆定义或到达根结点。
（4）void MinMaxHeapIns(RecType R[],int n)
{ //假设R[1..n-1]是最小最大堆，插入第n个元素，把R[1..n]调成最小最大堆 j=n; R[0]=R[j];
h=?log2n?+1; //求高度
if (h%2==0) //插入元素在偶数层，是最大层
{i=n/2;
if (R[0].key j=i/4; while (j>0 && R[j]>R[i]) //调小堆 {R[i]=R[j]; i=j; j=i/4; } R[i]=R[0]; } else //插入元素大于双亲，调大堆 {i=n; j=i/4; while (j>0 && R[j] } else //插入元素在奇数层，是最小层 {i=n/2; if (R[0].key>R[i].key) //插入元素大于双亲，先与双亲交换，然后调大堆 {R[j]=R[i]; j=i/4; while (j>0 && R[j] else //插入元素小于双亲，调小堆 {i=n; j=i/4; while (j>0 && R[j]>R[i]) {R[i]=R[j]; i=j; j=i/4; } R[i]=R[0]; } } }//MinMaxHeapIns 17.void BiInsertSort(RecType R[]，int n) {//二路插入排序的算法 int d[n+1]; //辅助存储 d[1]=R[1];first=1;final=1; for(i=2;i<=n;i++) { if(R[i].key>=d[1].key) //插入后部 { low=1;high=final; while (low<=high) //折半查找插入位置 { m=(low+high)/2; if(R[i].key< d[m].key) high=m-1; else low=m+1; }//while for (j=final;j>=high+1;j--) d[j+1] = d[j];//移动元素 d[high+1]=R[i]; final++; //插入有序位置 } else //插入前部 { if(first==1){ first=n; d[n]=R[i];} else{ low=first;high=n; while (low<=high) { m=(low+high)/2; if(R[i].key< d[m].key) high=m-1; else low=m+1; }//while for (j=first;j<=high;j++) d[j-1] = d[j]; //移动元素 d[high]=R[i]; first--; }//if }//if }//for R[1] =d[fisrt]; for(i=first%n+1,j=2;i!=fisrt;i=i%n+1,j++) R[j] =d[i]; //将序列复制回去 }//BiInsertSort 18. 手工模拟排序过程略。 #define n 待排序记录的个数 typedef struct { int key[d]; //关键字由d个分量组成 int next; //静态链域 AnyType other; //记录的其它数据域 } SLRecType; SLRecType R[n+1]; //R[1..n]存放n个记录 typedef struct { int f,e; //队列的头、尾指针 } SLQueue; SLQueue B[m] //用队列表示桶，共m个 int RadixSort(SLRecType R[], int n) { //对R[1..n]进行基数排序，返回收集用的链头指针 for(i=1;i R[n].next=-1; p=1; //将初始链表的终端结点指针置空, p指向链表的第一个结点 for(j=d-1;j>=0;j--) //进行d趟排序 {for(i=0;i if(B[k].f==-1) B[k].f=p; //将R[p]链到桶头 else R[B[k].e].next=p; //将R[p]链到桶尾 B[k].e=p; //修改桶的尾指针, p=R[p].next; //扫描下一个记录 }//while i=0; while(B[i].f==-1) i++; //找第一个非空的桶 t=B[i].e; p=B[i].f //p为收集链表的头指针，t为尾指针 while(i if(B[i].f!=-1){ R[t].next=B[i].f; t=B[i].e; } //连接非空桶 }//while R[t].next=-1; //本趟收集完毕，将链表的终端结点指针置空 }//for return p; }//RadixSort 19. [题目分析]本题是基数排序的特殊情况，关键字只含一位数字的整数。 typedef struct { int key; int next; } SLRecType; SLRecType R[N+1]; typedef struct { int,f,e; } SLQueue; SLQueue B[10]; int Radixsort(SLRecType R[],int n) //设各关键字已输入到R数组中 {for (i=1;i R[n].next=-1; p=1; //-1表示静态链表结束 for (i=0;i<=9;i++);{ B[i].f=-1; B[i].e=-1;} //设置队头队尾指针初值 while (p!=-1) //一趟分配 {k=R[p].key; //取关键字 if(B[k].f==-1)B[k].f=p; //修改队头指针 else R[B[k].e].next=p; B[k].e=p; p=R[p].next; //下一记录 } i=0; //一趟收集 while (B[i].f==-1) i++; t=B[i].e; p=B[i]f; while (i<9) {i++; if (B[i].f!=-1) { R[t].next=B[i].f;t=B[i].e;} } R[t].next=-1; return p; //返回第一个记录指针 } [算法讨论]若关键字含d位，则要进行d趟分配和d趟收集。关键字最好放入字符数组，以便取关键字的某位。 20. void Adjust(int T[],int s) { //选得最小关键字记录后，从叶到根调整败者树，选下一个最小关键字 //沿从叶子结点R[s]到根结点T[0]的路径调整败者树 t=(s+k)/2; //T[t]是R[s]的双亲结点 while(t>0) { if(R[s].key>R[T[t]].key) s<-->T[t]; //s指示新的胜者 t=t/2; }//while T[0]=s; }//Adjust void CreateLoserTree(int T[]) { //建立败者树，已知R[0]到R[k-1]为完全二叉树T的叶子结点，存有k个关键字，沿 //从叶子到根的k条路径将T调整为败者树 R[k].key=MINKEY; //MINKEY是最小关键字 for(i=0;i for(i=k-1;k>=0;i--) Adjust(T,i); }//CreateLoserTree 21、[题目分析]利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”，设3个指针i，j和k，分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始，从右向左搜索，若该元素是兰色，则元素不动，指针左移（即k-1）；若当前元素是红色砾石，分i>=j（这时尚没有白色砾石）和i 为方便处理，将三种砾石的颜色用整数1、2和3表示。 void QkSort(rectype r[],int n) // r为含有n个元素的线性表，元素是具有红、白和兰色的砾石，用顺序存储结构存储， //本算法对其排序，使所有红色砾石在前，白色居中，兰色在最后。 {int i=1,j=1,k=n,temp; while (k!=j) {while (r[k].key==3) k--;// 当前元素是兰色砾石，指针左移 if (r[k].key==1) // 当前元素是红色砾石