数据结构实验上机指导(6)

数据结构与算法实验指导书

p->next = HTC[j]; p->key = i; HTC[j] = p; }

main()

{ CHAINHASH *HTC[MAXSIZE]; int i, k;

printf(\建立开散列表\\n\\n\ for (i = 0; i

printf(\请输入开散列表元素关键字值,关键字为正整型量，用空格分开，

-99为结束标志 : \

creat_chain_hash(HTC);

printf(\显示建立的开散列表 : \\n\\n\ print_chain_hash(HTC);

printf(\输入待插入元素关键字 : \ scanf(\

k = search_chain_hash(HTC, i);

if (k == 0) { printf(\表中待插入元素不存在,可插入散列表中\\n\\n\ insert_chain_hash(HTC, i);

printf(\显示插入后的开散列表 : \\n\\n\ print_chain_hash(HTC);}

else printf(\表中待插入元素存在，不可插入散列表中\\n\\n\}

实验八 排序

一、实验目的

1、掌握常用的排序方法，并能用高级语言实现排序算法。

2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。

3、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度

的分析方法。

二、实验内容

1、排序综合练习

#include

#define KEYTYPE int #define MAXSIZE 100

int createList(RECNODE *r) { int j, k;

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

while(j != 0) { k++; r[k].key = j; scanf(\ return k; }

frontdisplayList(RECNODE *r, int n)

- 26 -

数据结构与算法实验指导书

{int i;

printf(\排序前 : \

for (i = 0; i < n; i++) printf(\ 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*/

- 27 -

数据结构与算法实验指导书

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);} }

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); /*将无序序列建成大堆*/

- 28 -

数据结构与算法实验指导书

}

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;} /*有序子序列长度加倍*/ }

for(i = n; i >= 2; i--)

{temp = r[1]; /*堆顶及堆尾元素交换*/ r[1] = r[i]; r[i] = temp;

sift(r,1,i - 1);

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

- 29 -

数据结构与算法实验指导书

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

- 30 -

数据结构与算法实验指导书

printf(\排序前 : \

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

printf(\排序后 : \

for (j = 0; j < len; j++) printf(\ printf(\ break; } printf(\结束此练习吗? (0 -- 结束 1 -- 继续) : \ scanf(\ printf(\ } }

- 31 -