数据结构严蔚敏版第十章答案

{

int b[MAXSIZE]; //设立辅助存储数组b for(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++) {

if(a[i]

while(i<=e1) b[k++]=a[i++];

while(j<=e2) b[k++]=a[j++]; //归并到b中 for(i=s1;i<=e2;i++) //复制回去 a[i]=b[i]; }//Merge 10.37

void LinkedList_Merge_Sort1(LinkedList &L)//链表结构上的归并排序非递归算法 {

for(l=1;lnext,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; //求出两个待归并子序列的尾指针

if(e1!=e2) LinkedList_Merge(L,p,e1,e2); //归并 }

}//LinkedList_Merge_Sort1

void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2 {

q=p->next;r=e1->next; //q和r为两个子序列的起始位置 while(q!=e1->next&&r!=e2->next) {

if(q->datadata) //选择关键字较小的那个结点接在p的后面 {

p->next=q;p=q; q=q->next; } else {

p->next=r;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.38

void LinkedList_Merge_Sort2(LinkedList &L)//初始归并段为最大有序子序列的归并排序,采用链表存储结构 {

LNode *end[MAXSIZE]; //设立一个数组来存储各有序子序列的尾指针 for(p=L->next->next,i=0;p;p=p->next) //求各有序子序列的尾指针 if(!p->next||p->data>p->next->data) end[i++]=p;

while(end[0]->next) //当不止一个子序列时进行两两归并 {

j=0;k=0; //j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置 for(p=L->next,e2=p;p->next;p=e2) //两两归并所有子序列 {

e1=end[j];e2=end[j+1]; //确定两个子序列

if(e1->next) LinkedList_Merge(L,p,e1,e2); //归并

end[k++]=e2; //用新序列的尾指针取代原来的尾指针 j+=2; //转到后面两个子序列 }

}//while

}//LinkedList_Merge_Sort2

void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从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;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)//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列 {

start1=0;start2=l1; //分别表示序列1和序列2的剩余未归并部分的起始位置 for(i=0;i

for(j=start2;j

RSh(a,start1,j-1,k);//将a[start1]到a[j-1]之间的子序列循环右移k位 start1+=k+1;

start2=j; //修改两序列尚未归并部分的起始位置 }

}//SL_Merge

void RSh(int a[ ],int start,int end,int k)//将a[start]到a[end]之间的子序列循环右移k位,算法原理参见5.18 {

len=end-start+1; for(i=1;i<=k;i++)

if(len%i==0&&k%i==0) p=i; //求len和k的最大公约数p for(i=0;i

j=start+i;l=start+(i+k)%len;temp=a[j]; while(l!=start+i) {

a[j]=temp;

temp=a[l]; a[l]=a[j];

j=l;l=start+(j-start+k)%len; //依次向右移 }

a[start+i]=temp; }//for }//RSh 10.40

书后给出的解题思路在表述上存在问题,无法理解.比如说,\把第一个序列划分为两个子序列,使其中的第一个子序列含有s1个记录,0<=s1

void Hash_Sort(int a[ ])//对1000个关键字为四位整数的记录进行排序 {

int b[10000];

for(i=0;i<1000;i++) //直接按关键字散列 {

for(j=a[i];b[j];j=(j+1)000); b[j]=a[i]; }

for(i=0,j=0;i<1000;j++) //将散列收回a中 if(b[j]) {

for(x=b[j],k=j;b[k];k=(k+1)000) if(b[k]==x) {

a[i++]=x; b[k]=0; } }//if

}//Hash_Sort 10.42

typedef struct {

int gt; //大于该记录的个数 int lt; //小于该记录的个数

} place; //整个序列中比某个关键字大或小的记录个数 int Get_Mid(int a[ ],int n)//求一个序列的中值记录的位置 {