原创力文档- 1、本文档共10页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
实验八查找概要
实验八 查找
【实验目的】
1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。
2、掌握线性表中顺序查找和折半查找的方法。
3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。
4、掌握二叉排序树的构造方法和查找过程；
【实验学时】
2学时
【实验预习】
回答以下问题：
1、顺序查找。顺序查找的平均查找长度和查找不成功时的比较次数。
2、折半查找。折半查找的平均查找长度。
3、二叉排序树和平衡二叉树。
4、哈希表和哈希查找
5、处理冲突的方法有哪几种？
【实验内容和要求】
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参考程序如下：
#includestdio.h
#define MAX 100
#define KeyType int
/*静态查找表的顺序存储结构*/
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(\n***************MENU******************\n);
printf( 1. 输入顺序查找表\n);
printf( 2. 顺序查找\n);
printf( 3. 输入折半查找表\n);
printf( 4. 折半查找\n);
printf( 0. EXIT);
printf(\n***************MENU******************\n);
printf(\ninput choice:);
scanf(%d,select);
getchar();
switch(select)
{
case 1:
printf(\n1-输入顺序查找表\n);
n=inputSeqData(R);
printf(\n顺序查找表元素:);
for(i=0; in; i++)
printf(%d ,R[i].key);
printf(\n);
getchar();
break;
case 2:
printf(\n2-顺序查找\n);
printf(\n输入查找关键字：);
scanf(%d,k);
i=SeqSearch(R,n,k);
if(i==-1)
printf(\n未找到key=%d！\n,k);
else
printf(\n查找成功！k=%d位置序号：%d\n,k,i);
getchar();
break;
case 3:
printf(\n3-输入折半查找表\n);
文档评论（0）