《数据结构与算法》实验指导V2015 实验八 查找
【实验目的】
1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。
3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。 4、掌握二叉排序树的构造方法和查找过程；
【实验学时】
2学时
【实验预习】
回答以下问题：
1、顺序查找。顺序查找的平均查找长度和查找不成功时的比较次数。
2、折半查找。折半查找的平均查找长度。
3、二叉排序树和平衡二叉树。
4、哈希表和哈希查找
5、处理冲突的方法有哪几种？
常熟理工学院计算机科学与工程学院
1
《数据结构与算法》实验指导V2015 【实验内容和要求】
1、编写程序exp8_1.c，实现顺序查找和折半查找。 补充完整程序，调试运行测试数据：
（1）顺序查找表{ 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 } 查找key = 41 查找成功比较次数：________ 查找key = 100 查找不成功比较次数：______
（2）折半查找表{ 12 ，15 ，20，29 ，33 ，33，48 ，65 ，89 } 查找key = 29 查找成功比较次数：________ 查找key = 99 查找不成功比较次数：______
exp8_1.c参考程序如下： #include
/*静态查找表的顺序存储结构*/ typedef struct {
KeyType key; /*关键字值项*/ } table;
int inputSeqData(table R[]); /*创建顺序查找表*/ int SeqSearch (table R[], int n, KeyType k ); /*顺序查找算法*/
int inputBinData(table R[]); /*创建折半查找表，按照增序*/ int BinSearch(table R[],int n, KeyType k); /*折半查找算法*/
int main() {
table R[MAX]; int select,n,i; KeyType k; do {
printf(\ printf(\输入顺序查找表\\n\ printf(\顺序查找\\n\
printf(\输入折半查找表\\n\ printf(\折半查找\\n\ printf(\
printf(\ printf(\ scanf(\ getchar(); switch(select)
常熟理工学院计算机科学与工程学院
2
《数据结构与算法》实验指导V2015 {
case 1:
printf(\输入顺序查找表\\n\ n=inputSeqData(R);
printf(\顺序查找表元素:\ for(i=0; i printf(\ printf(\ getchar(); break; case 2: printf(\顺序查找\\n\ printf(\输入查找关键字：\ scanf(\ i=SeqSearch(R,n,k); if(i==-1) printf(\未找到key=%d！\\n\ else printf(\查找成功！k=%d位置序号：%d\\n\ getchar(); break; case 3: printf(\输入折半查找表\\n\ n=inputBinData(R); printf(\折半查找表元素:\ for(i=0; i printf(\ printf(\ getchar(); break; case 4: printf(\折半查找\\n\ printf(\输入查找关键字：\ scanf(\ i=BinSearch(R,n,k); if(i==-1) printf(\未找到key=%d！\\n\ else printf(\查找成功！k=%d位置序号：%d\\n\ getchar(); break; case 0: break; default: 常熟理工学院计算机科学与工程学院 3