数据结构实验
实验一静态查找表中的查找
一、实验目的：
1、理解静态查找表的概念
2、掌握顺序查找和折半查找算法及其实现方法
3、理解顺序查找和折半查找的特点，学会分析算法的性能
二、实验内容：
1、按关键字从小到大顺序输入一组记录构造查找表，并且输出该查找表；
2、给定一个关键字值，对所构造的查找表分别进行顺序查找和折半查找，输出查找的结果以及查找过程中“比较”操作的执行次数。
三、实验要求：
1、查找表的长度、查找表中的记录和待查找的关键字值要从终端输入；
2、具体的输入和输出格式不限；
3、算法要具有较好的健壮性，对错误操作要做适当处理；
4、输出信息中要标明所采用的查找方法类型。
实验二基于二叉排序树的查找
一、实验目的：
1、理解动态查找表和二叉排序树的概念
2、掌握二叉排序树的构造算法及其实现方法
3、掌握二叉排序树的查找算法及其实现方法
二、实验内容：
1、输入一组记录构造一颗二叉排序树，并且输出这棵二叉排序树的中序序列；
2、给定一个关键字值，对所构造的二叉排序树进行查找，并输出查找的结果。
三、实验要求：
1、二叉排序树中的记录和待查找的关键字值要从终端输入；
2、输入的记录格式为(整数，序号)，例如(3, 2)表示关键字值为3，输入序号为2的记录；
3、算法要具有较好的健壮性，对错误操作要做适当处理。
四、程序实现：
(1)实现顺序查找表和折半查找表：
#include<stdio.h>
#define MAX_LENGTH 100
typedef struct
{
int key[MAX_LENGTH];
int length;
}stable;
int seqserch(stable ST,int key,int &count)
{
int i;
for(i=ST.length;i>0;i--)
{
count++;
if(ST.key[i]==key)
return i;
}
return 0;
}
int binserch(stable ST,int key,int &count)
{
int low=1,high=ST.length,mid;
while(low<=high)
{
count++;
mid=(low+high)/2;
if(ST.key[mid]==key)
return mid;
else if(key<ST.key[mid])
high=mid-1;
else
low=mid+1;
}
return 0;
} main()
{
stable ST1;
int
a,b,k,x,count1=0,count2=0,temp=0;
ST1.length=0;
printf("请按从小到大的顺序输入查找表数据：(-1代表结束！)\n");
for(a=0;a<MAX_LENGTH;a++)
{
scanf("%d",&temp);
if(temp!=-1)
{
ST1.key[a]=temp;
ST1.length++;
}
else
break;
}
printf("输入数据为：\n");
for(b=0;b<ST1.length;b++)
{
printf("%d ",ST1.key[b]);
}
printf("\n请输入要查找的数据：");
scanf("%d",&k);
a=seqserch(ST1,k,count1)+1;
printf("\n顺序查找：该数据的位置在第：%d个\n",a);
printf("查找次数为：%d\n\n",count1-1);
a=binserch(ST1,k,count2)+1;
printf("折半查找：该数据的位置在第：%d个\n",a);
printf("查找次数为：%d\n",count2-1);
}
（2）二叉排序树的查找：
#include<stdio.h> #include<malloc.h> typedef struct node {
int data;
int key;
struct node *left,*right;
}bitnode,*bittree;
void serchbst(bittree T,bittree *F,bittree *C,int data)
{
while(T!=NULL)
{
if(T->data==data)
{
*C=T;
break;
}
else if(data<T->data)
{
*F=T;
T=T->left;
}
else
{
*F=T;
T=T->right;
}
}
return 0;
}
int insertbst(bittree *T,int key,int data) {
bittree F=NULL,C=NULL,s;
serchbst(*T,&F,&C,data);
if(C!=NULL) return 0;
s=(bittree)malloc(sizeof(bitnode));
s->data=data;
s->key=key;
s->left=s->right=NULL;
if(F==NULL) *T=s;
else if(data<F->data)
F->left=s;
else
F->right=s;
return 1; }
void creatbst(bittree *T)
{
int key,data;*T=NULL;
printf("请输入数据以构造二叉排序树：(数据格式为:m n (-1000,-1000)代表结束)\n");
scanf("%d%d",&key,&data);
while(key!=-1000 || data!=-1000)
{
insertbst(T,key,data);
scanf("%d%d",&key,&data);
}
}
void midTraverse(bittree T)
{
if(T!=NULL)
{
midTraverse(T->left);
printf("(%d,%d)
",T->key,T->data);
midTraverse(T->right);
}
}
main()
{
bittree
T=NULL,C=NULL,F=NULL;
int key,data,temp;
creatbst(&T);
printf("此二叉树的中序序列为：");
midTraverse(T);
printf("\n请输入要查找的关键字：");
scanf("%d",&data);
serchbst(T,&F,&C,data);
printf("此关键字的数据为：%d\n",C->key);
}
五、实现结果：
(1)顺序查找和折半查找：
(2)二叉树排序树查找：
六、实验之心得体会：
（1）在这次实验中，我基本上掌握了顺序查找、折半查找和二叉排序树查找的基本思想和实现方法，让我体会到了写程序时，不仅要考虑是否能够调试出结果，还要考虑程序实现的效率，这是一个编程人员必须要具备的一项总要的素质。
（2）通过这次实验，让我体会到同样的数据在不同的查询方法下有着不同的查询效率，就拿实验一来说，用顺序查找法在12个数据中查找一个关键字需要的查找的次数为8次，但是，如果折半查找法却只要两次，由此可以看出，我们在查找时不仅要考虑查找的实现，还要考虑查找的效率和查找所用的时间。
（3）用二叉排序树查找效率也比较高，只要你输入相应的关键字，就可已找到所需要的数据，就我个人看来，用二叉排序树的效率要比顺序查找和折半查找的效率更高，查询的速度更快。