实用标准

实验七 查找

一、实验目的

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 #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;

文案大全