实验七 查找
一、实验目的
1. 掌握查找的不同方法，并能用高级语言实现查找算法； 2. 熟练掌握二叉排序树的构造和查找方法。 3. 熟练掌握静态查找表及哈希表查找方法。 二、实验内容
设计一个读入一串整数，然后构造二叉排序树，进行查找。 三、实验步骤
1. 从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。
2. 在二叉排序树中查找某一结点。
3.用其它查找算法进行排序（课后自己做）。 四、实现提示
1. 定义结构
typedef struct node { int key; int other;
struct node *lchild, *rchild;
} bstnode;
void inorder ( t ) { if (t!=Null) { inorder(t→lchild); printf(“M”, t→key); inorder(t→rchild); } }
bstnode *insertbst(t, s)
bstnode *s, *t; { bstnode *f, *p; p=t;
while(p!=Null)
{ f=p;
if (s→key= =p→key) return t; if (s→key p=p→rchild; } if(t= =Null) return s; if (s→key f→rchild=s; return t; } bstnode *creatord( ) { bstnode *t, * s; int key; t=Null; scanf(“%d”,&key); while (key!=0) { s=malloc(sizeof (bitree)); s→key=key; s→lchild=Null; s→rchild=Null; scanf(“%d”, &data); s→other=data; t=insertbst(t, s); scanf(“%d”,&key); } return t; } 五、思考与提高 1. 用其它的查找方法完成该算法。 2.比较各种算法的时间及空间复杂度。 六、完整参考程序 1.折半查找 #include #define MAX 30 //定义有序查找表的最大长度 typedef struct{ char elem[MAX]; //有序查找表 int length; //length指示当前有序查找表的长度 }SSTable; void initial(SSTable &); //初始化有序查找表 int search(SSTable,int); //在有序查找表中查找元素 void print(SSTable); //显示有序查找表中所有元素 void main() {SSTable ST; //ST为一有序查找表 int ch,loc,flag=1; char j; initial(ST); //初始化有序查找表 while(flag) { printf(\请选择：\\n\ printf(\显示所有元素\\n\ printf(\查找一个元素\\n\ printf(\退出\\n\ scanf(\ switch(j) 置 else printf(\不存在!\\n\当前元素不存在 break; } {case '1':print(ST); break; //显示所有元素 case '2':{printf(\请输入要查找的元素：\ scanf(\ //输入要查找的元素的关键字 loc=search(ST,ch); //查找 if(loc!=0) printf(\该元素所在位置是：%d\\n\显示该元素位 default:flag=0; } } printf(\程序运行结束!按任意键退出!\\n\} void initial(SSTable &v) {//初始化有序查找表 int i; printf(\请输入静态表的元素个数：\输入有序查找表初始化时的长度 scanf(\ printf(\请从小到大输入%d个元素（整形数）：\\n\ getchar(); for(i=1;i<=v.length;i++) scanf(\从小到大输入有序查找表的各元素 } int search(SSTable v,int ch) {//在有序查找表中查找ch的位置，成功返回其位置，失败返回0 int low,high,mid; low=1;high=v.length; //置区间初值