实验五查找运算实现.doc

实验五 查找运算实现 （2课时） 一、实验目的 掌握各种查找方法的基本思想，根据实际问题实现简单应用； 二、实验要求 程序结构清晰、语句完整，包含有头文件和main函数； 格式正确，语句采用缩进格式； 设计子函数实现题目要求的功能； 三、实验设备、材料和工具 turboc2,win-tc.vc++ 四、实验内容和步骤 1.用折半查找法实现对10个整数的查找。 2．用哈希查找实现对10个字符的查找。（假设字符互不相同，M取13） 五、实验报告要求 根据实验内容初步设计好程序,并从理论上排除错误； 针对程序的健壮性准备好测试数据； 结果分析中如实填写运行后的结果，并记录调试过程中的重要问题和解决方法。 源程序以电子版的形式保存，不必写在报告上。 六、运行结果及分析 1．实验程序 #include stdio.h #include stdlib.h #define LIST_SIZE 20 typedef char KeyType; typedef int OtherType; typedef struct { KeyType key; OtherType other_data; }RecordType; typedef struct { RecordType r[LIST_SIZE+1]; /* r[0]为工作单元 */ int length; }RecordList; void createlist(RecordList *l) { int i; int len; KeyType ch; printf(请输入线性表的长度:); scanf(%d,len); l-length = len; for(i=1; i=len; i++) { printf(请输入线性表的第%d个元素:,i); fflush(stdin); scanf(%c,ch); l-r[i].key = ch; } } int BinSrch(RecordList l, KeyType k) /*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的 位置*/ { int low,high,mid; low=1; high=l.length;/*置区间初值*/ while( low = high) { mid=(low+high) / 2; if( k==l.r[mid]. key) return (mid);/*找到待查元素*/ else if (kl.r[mid]. key) high=mid-1;/*未找到，则继续在前半区间进行查找*/ else low=mid+1;/*继续在后半区间进行查找*/ } return (0); } void main() { RecordList l; int locate; KeyType k; createlist(l); printf(请输入要查找的元素:); fflush(stdin); scanf(%c,k); locate = BinSrch(l,k); if(locate == 0) printf(未找到!\n); else printf(该元素在表中的位置为%d\n,locate); } 运行结果： 2.实验程序 #include stdio.h #include stdlib.h #include string.h #define m 30 #define NULLKEY NULL typedef struct { char *key; }RecordType; typedef RecordType HashTable[m]; int hash(char *k) { int h; char k0; k0 = k[0]; h=k[0]-96; return h; } void createhash(HashTable *ht) { int i,j; int n; char p[10]; int hj; for(i=0; im; i++) (*ht)[i].key = NULLKEY; printf(请输入哈希表的元素个数:); scanf(%d,n); for(i=1; i=n; i++) { printf(请输入第%d个元素:,i); fflush(stdin); gets(p); j = hash(p); // printf(ok%d\n,j); if ((*ht)[j].key == NULLKEY