2009级数据结构实验指导书(10)

数据结构实验指导书

}

void selesort(RECNODE *r, int n) {/*简单选择排序*/ int i,j,k; RECNODE temp; for(i = 1; i < n; i++) { k = i; /*k:最小关键字的初始位置*/ for(j = i + 1; j <= n; j++) if(r[j].key < r[k].key) k = j; /*k:跟踪记录当前最小关键字的位置*/ if(k != i) /*最小关键字元素和待排序列的第一个元素交换*/ {temp = r[i]; r[i] = r[k]; r[k] = temp;} } }

void sift(RECNODE *r, int i, int m)

{/*i是根结点编号,m是以i结点为根的子树中最后一个结点的编号*/ int j; RECNODE temp; temp = r[i]; j = 2 * i; /*j为i根结点的左孩子*/ while(j <= m) {if(j < m && (r[j].key < r[j + 1].key)) j++; /*当i结点有左右孩子时,j取关键字大的孩子结点编号*/ if(temp.key < r[j].key) /*按堆定义调整,并向下一层筛选调整 */ { r[i] = r[j]; i = j; j = 2 * i;} else break; /*筛选调整完成,跳出循环 */ } r[i] = temp; }

void heapsort(RECNODE *r, int n)

{/*堆排序: n为r表中记录数,从r[1]开始放起*/ int i; RECNODE temp; for(i = n/2; i >= 1; i--) sift(r, i, n); /*将无序序列建成大堆*/ for(i = n; i >= 2; i--) {temp = r[1]; /*堆顶及堆尾元素交换*/ r[1] = r[i]; r[i] = temp; sift(r,1,i - 1);

/*交换后,从第一个元素开始调整为大堆,每次记录个数少一个*/

} }

quicksort(r, start, i - 1);

/*对两个独立的待排子序列分别递归调用快速排序算法*/

quicksort(r, i + 1,end);}

- 31 -

数据结构实验指导书

void merge(RECNODE *r, int low, int m, int high)

{ /*两相邻的有序表(一个从low到m;另一个从m+1到high)*/

/*合并为一个有序表(从low到high)*/

RECNODE r1[MAXSIZE]; /*合并时用的缓冲向量*/ int i, j, k; i = low; j = m + 1; k = 0; while(i <= m && j <= high) /*两相邻的有序表合并*/ if(r[i].key <= r[j].key) {r1[k] = r[i]; i++; k++;} else {r1[k] = r[j]; j++; k++;} while(i <= m) /*有序表剩余部分处理*/ {r1[k] = r[i]; i++; k++;} while(j <= high) //有序表剩余部分处理 {r1[k] = r[j]; j++; k++;} for(i = low, k = 0; i <= high; i++, k++)/*缓冲向量r1复制到原来的r中*/ r[i] = r1[k]; }

void merge_one(RECNODE *r, int lenth, int n) {/*二路归并中的\一趟归并\算法*/ int i = 0; while(i + 2 * lenth - 1 < n) {merge(r, i, i + lenth - 1, i + 2 * lenth - 1);/*两子序列长度相等的*/ i = i + 2 * lenth;} /*情况下调用merge*/ if(i + lenth - 1 < n - 1) merge(r, i, i + lenth - 1, n - 1); /*序列中的余留部分处理*/ }

void mergesort(RECNODE *r, int n) {/*二路归并排序算法*/ int lenth = 1; /*有序子序列长度初始值 = 1*/ while(lenth < n) {merge_one(r, lenth, n); /*调用\一趟归并\的算法*/ lenth = 2 * lenth;} /*有序子序列长度加倍*/ }

void main() { RECNODE a[MAXSIZE]; int len, b, j, k; int loop = 1; while (loop) { printf(\排序综合练习\\n\\n\ printf(\退出\\n\ printf(\直接插入排序\\n\ printf(\简单交换(冒泡)排序\\n\

- 32 -

数据结构实验指导书

printf(\快速排序\\n\printf(\简单选择排序\\n\printf(\堆排序\\n\

printf(\二路归并排序\\n\printf(\请选择项号 ： \scanf(\printf(\

if(b >= 0 && b <= 6) switch(b) { case 0: loop = 0; break; case 1: len = createList(a); frontdisplayList(a,len); insertsort(a,len); reardisplayList(a,len); break; case 2: len = createList(a); frontdisplayList(a,len); bublesort(a, len); reardisplayList(a,len); break; case 3: len = createList(a); frontdisplayList(a,len); quicksort(a, 1, len); reardisplayList(a,len); break; case 4: len = createList(a); frontdisplayList(a,len); selesort(a, len); reardisplayList(a,len); break; case 5: len = createList(a); frontdisplayList(a,len); heapsort(a, len); reardisplayList(a,len); break; case 6:

printf(\输入待排序数据(整数，以空格隔开，0 结束) : \k = 0; scanf(\

while(j != 0) { k++; a[k-1].key = j; scanf(\ len = k;

printf(\排序前 : \

for (j = 0; j < len; j++) printf(\ printf(\ mergesort(a, len);

printf(\排序后 : \

for (j = 0; j < len; j++) printf(\ printf(\ break; }

- 33 -

数据结构实验指导书

printf(\结束此练习吗? (0 -- 结束 1 -- 继续) : \ scanf(\ printf(\ }

}

三、注意事项

1、查找时mid的变化。