实验六 查找算法

软件学院 数据结构 实验报告

2016 ～2017 学年 第 一 学期 2014 级 软件工程 专业

班级： 191 学号： 201419118 姓名： 孟国元

实验六 查找算法实验

一、实验目的

1、掌握静态查找表的查找算法 2、掌握二叉排序树的查找算法 3、掌握哈希函数的构造和哈希表的查找 4、了解查找表的广泛应用 二、实验内容 1、有序表的查找 1.1 数据结构的设计

有序表的存储结构（数组表示)

#define Max 20

int a[Max] = {05,13,19,21,37,56,64,75,80,88,92}

1.2 基本思想： 折半查找算法

在有序表中，取中间的记录作为比较对象，如果要查找记录的关键字等于中间记录的关键字，则查找成功；若要查找记录的关键字小于中间记录的关键字，则在中间记录的左半区继续查找；若要查

1

找记录的关键字大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述查找过程，直到查找成功，或有序表中没有所要查找的记录，查找失败。例：

输入：查找记录的关键字 k = 13，k =37，k =99

输出：k=13，查找成功；k=37，查找成功；k=99，查找不成功

1.3 实验步骤： 源程序：

#include

#define MAX 20;

int Search_Bin(int ST[],int key,int length)

{

int low = 0,mid;

int high = length-1;

while(low<=high)

{

mid = (low+high)/2;

2

if(key==ST[mid])

{

printf(\"key=%d\\n位置：%d\\n\

return key;

}

else if (key{

high = mid-1;

}

else

low = mid+1;

}

return 0;

}

3

void main()

{

int a[]={5,13,19,21,37,56,64,75,80,88,92};

int length;

int key,result=0;

length=sizeof(a)/sizeof(a[0]);

printf(\"请输入要查找的值：\");

scanf(\"%d\

result = Search_Bin(a,key,length);

if(result==0)

{

printf(\"查找不成功！\

}

else

4

{

printf(\"查找成功！\

}

}

1.4 运行结果：

2、二叉排序树的查找 2.1 数据结构的设计 二叉链表的存储结构表示：

typedef int datatype;

struct bi_search_tree

{

datatype key;

struct bi_search_tree *left, *right;

5

};

typedef struct bi_search_tree bst_tree

2.2 基本思路

先将输入的数据记录序列通过二叉排序树的插入算法建立一个二叉排序树，然后在二叉排序树中查找某个给定的关键字，返回查找成功或者不成功的结果

输入：（1）数据记录序列{37,56,05,13,19,21, 64, 88, 75,80,92}建立二叉排序树，（2）查找记录的关键字 k = 13，k =37，k =99

输出：k=13，查找成功；k=37，查找成功；k=99，查找不成功

2.3 实验步骤： 主要函数声明：

#include

#include

typedef struct BiTNode

{

int data;

6

struct BiTNode *left,*right;

}BiTNode,*BiTree;

BiTree initializer_BiTree(BiTree T,int key)

{

T = (BiTree)malloc(sizeof(BiTNode));

T->data=key;

T->left=T->right=NULL;

printf(\"初始化成功！\\n\");

return T;

}

BiTree InsertBST(BiTree T,int key)

{

if(T==NULL){

T=(BiTree)malloc(sizeof(BiTNode));

7

T->data=key;

T->left=T->right=NULL;

return T;

}

else if(key == T->data)

{

}

else if(keydata)

T->left = InsertBST(T->left,key);

else

T->right = InsertBST(T->right,key);

}

int SearchBST(BiTree T,int key)

{

8

if(!T)

return 0;//查找不成功

else if(key == T->data)//查找成功

return 1;

else if(key < T->data)//左子树

return SearchBST(T->left,key);

else //右子树

return SearchBST(T->right,key);

}

void print(BiTree t){//打印树中的数据if(t)

printf(\"%d\\n\

if(t->left)

print(t->left);

9

if(t->right)

print(t->right);

}

主函数代码：

void main()

{

BiTree T,root;

int key,length,i;

int data[] = {37,56,05,13,19,21, 64, 88, 75,80,92};

length=sizeof(data)/sizeof(data[0]);

T = initializer_BiTree(T,37);//初始化

root=T;//根结点

for(i=1;i{

10

T=root;

InsertBST(T,data[i]);//依次插入结点

}

printf(\"请输入需要查找的值：\");

scanf(\"%d\

i=SearchBST(T,key);//进行查找

if(i==0)

printf(\"key=%d 查找不成功！\

else

printf(\"key=%d 查找成功！\

}

2.4 运行结果：

11

三、问题讨论

1、折半查找有哪些特点？

优点是比较次数少，查找速度快，平均性能好；

缺点是要求待查表为有序表，且插入删除困难。

2、二叉排序树有那些特点？

（1）二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)

于x的关键字。

（2） 二叉排序树中，各结点关键字是惟一的。

（3） 按中序遍历该树所得到的中序序列是一个递增有序序列。

四、实验心得

二叉排序树不能存储相同的值，书上写的二叉排序树构造方法好麻烦啊！做完实验后发现java取消指针是多么的正确。

12