中的\一趟归并\算法。 四、实验重点、难点
1、设置一个监视哨。 2、mid的变化。 3、快速排序
4、二路归并中的\一趟归并\算法 五、操作要点
（一）顺序表的顺序查找
#include
#define KEYTYPE int #define MAXSIZE 100 typedef struct { KEYTYPE key; }SSELEMENT;
typedef struct
{ SSELEMENT r[MAXSIZE]; int len; }SSTABLE;
int seq_search(KEYTYPE k, SSTABLE *st) {/*顺序表上查找元素*/ int j;
j = st->len; /*顺序表元素个数*/
st->r[0].key = k; /*st->r[0]单元作为监视哨*/ while(st->r[j].key != k) j--; /*顺序表从后向前查找*/
return j; /*j=0, 找不到；j<>0 找到*/ }
main( )
{ SSTABLE a; int i, j, k;
printf(\请输入顺序表元素(整型量)，用空格分开，-99为结束标志 ：\j = 0; k = 1; i = 0; scanf(\while (i != -99)
{ j++; a.r[k].key = i; k++; scanf(\输入顺序表元素*/ a.len = j;
printf(\顺序表元素列表显示 ：\for (i = 1; i<=a.len; i++) printf(\printf(\
printf(\输入待查元素关键字 : \scanf(\
k = seq_search(i, &a);
if (k == 0) printf(\表中待查元素不存在\\n\\n\
else printf(\表中待查元素存在,为第%d个元素\\n\，k ); }
（二）有序顺序表的二分查找的递归算法
#include
#define KEYTYPE int #define MAXSIZE 100 typedef struct { KEYTYPE key; }SSELEMENT;
- 20 -
typedef struct
{ SSELEMENT r[MAXSIZE]; int len; }SSTABLE;
int search_bin(KEYTYPE k, int low, int high) { /*有序表上二分法查找,递归算法*/ int mid; mid = -1;
if(low <= high) /*low 表示当前表中第1个元素所在下标*/ /*high表示当前表中最后一个元素所在下标*/ {
mid = (low +high)/2; /*mid表示当前表中中间一个元素所在下标*/ if(a.r[mid].key < k)
mid = search_bin(k, mid + 1,high); /*二分法递归查找*/
else if(a.r[mid].key > k)
mid = search_bin(k,low,high - 1);
}
return mid; /*mid = -1 查找不成功；mid!=-1 查找成功*/ }
main( )
{ SSTABLE a; int i, j, k;
printf(\请输入有序表元素，元素为整型量（从小到大输入），用空格分开，-99为结束标
志 ：\
j = 0; k = 1; i = 0; scanf(\while (i != -99)
{ j++; a.r[k].key = i; k++; scanf(\输入有序表元素*/ a.len = j;
printf(\有序表元素列表显示 ：\for (i = 1; i<=a.len; i++) printf(\printf(\
printf(\输入待查元素关键字 : \scanf(\
k = search_bin(i, 1, a.len);
if (k == -1) printf(\表中待查元素不存在\\n\\n\
else printf(\表中待查元素存在,为第%d个元素\\n\，k); }
（三）排序综合练习
#include
#define KEYTYPE int #define MAXSIZE 100
int createList(RECNODE *r) { int j, k;
printf(\输入待排序数据(整数，以空格隔开，0 结束) : \ while(j != 0) { k++; r[k].key = j; scanf(\ return k; }
frontdisplayList(RECNODE *r, int n) {int i;
printf(\排序前 : \
for (i = 0; i < n; i++) printf(\
- 21 -
printf(\}
reardisplayList(RECNODE *r, int n) {int i;
printf(\排序后 : \
for (i = 0; i < n; i++) printf(\ printf(\}
void insertsort(RECNODE *r, int n) {/*直接插入排序*/ int i,j; for(i = 2; i <= n; i++) { r[0] = r[i];
j = i - 1; /*r[0]是监视哨，j表示当前已排好序列的长度*/
while(r[0].key < r[j].key) /*确定插入位置*/ {r[j + 1] = r[j]; j--;} r[j + 1] = r[0]; /*元素插入*/ } }
void bublesort(RECNODE *r, int n) {/*简单交换排序:冒泡排序*/ int i, j; RECNODE temp; for(i = 1; i < n; i++) for(j = n - 1; j >= i; j--) if(r[j + 1].key < r[j].key) {temp = r[j + 1]; r[j + 1] = r[j]; r[j] = temp;} }
int partition(RECNODE *r, int *low, int *high)
{/*一趟快速排序,返回i,产生了两个独立的待排子序列*/ int i, j; RECNODE temp; i = *low; j = *high; temp = r[i]; /*枢轴记录保存在temp变量中*/ do
{ while((r[j].key >= temp.key) && (i < j))
j--; /*j指针记录和枢轴记录比较*/
if(i < j) { r[i] = r[j]; i++;} while((r[i].key <= temp.key) && (i < j))
i++; /*i指针记录和枢轴记录比较*/
if(i < j) { r[j] = r[i]; j--;} } while(i != j); r[i] = temp; /*枢轴记录的排序位置确定在i*/ return i; }
void quicksort(RECNODE *r, int start, int end) {/*快速排序*/ int i; if(start < end) { i = partition(r, &start, &end);
/*一趟快速排序,返回i,产生了两个独立的待排子序列*/
quicksort(r, start, i - 1);
/*对两个独立的待排子序列分别递归调用快速排序算法*/
quicksort(r, i + 1,end);}
- 22 -
}
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);
/*交换后,从第一个元素开始调整为大堆,每次记录个数少一个*/
} }
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++;}
- 23 -