内容发布更新时间 : 2024/12/22 17:19:22星期一 下面是文章的全部内容请认真阅读。
typedef struct {
int data; int bf;
int lsize; //lsize 域表示该结点的左子树的结点总数加 1 BlcNode *lchild,*rchild;
} BlcNode,*BlcTree; //含lsize 域的平衡二叉排序树类型
BTNode *Locate_BlcTree(BlcTree T,int k)//在含lsize 域的平衡二叉排序树T 中确 定第k 小的结点指针 {
if(!T) return NULL; //k 小于 1 或大于树结点总数 if(T->lsize==k) return T; //就是这个结点 else if(T->lsize>k)
return Locate_BlcTree(T->lchild,k); //在左子树中寻找
else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k 的值
}//Locate_BlcTree
第 9 章 内部排序
9．6 编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。 void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法 {
low=0;high=n-1; // 冒泡的上下界 change=1;
while(low change=0; for(i=low;i 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 9．7 编写算法，对 n 个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记 录排在关键字为非负值的记录之前，要求： 采取顺序存储结构，至多使用一个记录的辅助存储空间； 算法的时间复杂度 O(n)； 讨论算法中记录的最大移动次数。 void Divide(int a[ ],int n)//把数组a 中所有值为负的记录调到非负的记录之前 { low=0;high=n-1; while(low while(low while(low }//Divide 9．8 试以单链表为存储结构实现简单选择排序的算法 void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法 { for(p=L;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->data x=r->next->data; s=r; } if(s!=q) //找到了值比q->data 更小的最小结点s->next { p->next=s->next;s->next=q; t=q->next;q->next=p->next->next; p->next->next=t; } //交换q 和 s->next 两个结点 }//for }//LinkedList_Select_Sort 9．9 假设含n个记录的序列中，其所有关键字为值介于v和w 之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数，之后按number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。 void Enum_Sort(int a[ ],int n)//对关键字只能取v 到w 之间任意整数的序列进行排序 { int number[w+1],pos[w+1]; for(i=0;i pos[i]=pos[i-1]+num[i]; //pos 数组可以把关键字的值映射为元素在排好的序列 中的位置 for(i=0;i 分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos 数组和那里的cpot 数组起的是相类似的作用. 9．10 已知两个有序序列(a1, a 2,..., a m)和(a m+1 , a m+2 ,..., a n ),并且其中一个序列的记录个数少于s,且s=?√n?. 试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。 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 9．12 设计一个用链表表示的直接选择排序算法。 void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法 { for(p=L;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->data x=r->next->data; s=r; } if(s!=q) //找到了值比q->data 更小的最小结点s->next { p->next=s->next;s->next=q; t=q->next;q->next=p->next->next; p->next->next=t; } //交换q 和 s->next 两个结点 }//for }//LinkedList_Select_Sort 9．16 已知（k1,k2,?k n）是堆，写一个算法将（k1,k2,?，k n，k n+1）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。 void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法 { for(i=2;i { //此时从H.r[1]到H.r[i-1] 已经是大顶堆 j=i; while(j!=1) //把H.r[i]插入 { k=j/2; if(H.r[j].key>H.r[k].key) H.r[j]<->H.r[k]; j=k; } }//for }//Build_Heap/