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

- 26 -

数据结构实验指导书

main() {

BTree *B;

B=creatree();

printf(\按先序遍历次序生成的二叉树\preorder(B);

printf(\二叉树深度:%d\\n\ printf(\总结点个数:%d\\n\ printf(\叶子结点个数:%d\\n\

printf(\非叶子结点个数:%d\\n\ printf(\具有双孩子结点个数:%d\\n\ printf(\具有单孩子结点个数:%d\\n\ }

三、注意事项

1、 遍历的思想。 思考题

1、用非遍历算法如何实现？

实验七 查找与排序

一、实验目的

1、掌握查找的不同方法，并能用高级语言实现查找算法。

2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造方法和查找算法。

3、掌握二叉排序树的生成、插入、删除、输出运算。 4、掌握常用的排序方法，并能用高级语言实现排序算法。

5、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。 6、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

二、实验内容

1、顺序表的顺序查找

#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) {/*顺序表上查找元素*/

- 27 -

数据结构实验指导书

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

2、有序顺序表的二分查找的递归算法

#include

#define KEYTYPE int #define MAXSIZE 100 typedef struct { KEYTYPE key; }SSELEMENT;

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); /*二分法递归查找*/

- 28 -

数据结构实验指导书

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

3、排序综合练习

#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) {int i;

printf(\排序前 : \

for (i = 0; i < n; i++) printf(\ printf(\}

reardisplayList(RECNODE *r, int n) {int i;

printf(\排序后 : \

- 29 -

数据结构实验指导书

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,产生了两个独立的待排子序列*/

- 30 -