《数据结构实训》doc版.doc

实验序号5实验名称查找运算实现实验地点SC-1310实验日期2013年 12月 17日 实验内容1.用折半查找法实现对10个整数的查找。2用哈希查找实现对10个字符串的查找。（假设字符串互不相同，M取13）实验过程及步骤第一题程序：#include #include #define LIST_SIZE 20 typedef char KeyType;typedef int OtherType;typedef structKeyType key;OtherType other_data;RecordType;typedef structRecordType rLIST_SIZE+1; /* r0为工作单元 */int length;RecordList;void createlist(RecordList *l)int i;int len;KeyType ch;printf(请输入线性表的长度:);scanf(%d,&len);l-length = len;for(i=1; iri.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.rmid. key) return (mid);/*找到待查元素*/else if (kl.rmid. 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);elseprintf(该元素在表中的位置为%dn,locate);第二题程序：#include #include #include #define m 30#define NULLKEY NULLtypedef structchar *key;RecordType;typedef RecordType HashTablem;int hash(char *k)int h;char k0;k0 = k0;h=k0-96;return h;void createhash(HashTable *ht)int i,j;int n;char p10;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%dn,j);if (*ht)j.key = NULLKEY)(*ht)j.key=(char*)malloc(10*sizeof(char);strcpy(*ht)j.key,p);/printf(okn);else for (i=1; i=m-1; i+)hj=(j+i) % m;if (*ht)hj.key=NULLKEY) (*ht)hj.key=(char*)malloc(10*sizeof(char);strcpy(*ht)hj.key,p);i = m;int HashSearch( HashTable ht, char *K)int h0;int i;int hi;int result;h0=hash(K);if (hth0.key=NULLKEY) return (-1);else result = strcmp(hth0.key,K);if (result = 0) return (h0);else /* 用线性探测再散列解决冲突 */ for (i=1; i=m-1; i+)hi=(h0+i) % m;if (hthi.key=NULLKEY) return (-1);elseresult = strcmp(hthi.key,K);if (result = 0) return (hi);return (-1);void printword(HashTable ht)/*按第一个字母的顺序输出ht哈希表中的标识符，处理冲突的方法为线性探测开放定址法*/int i,j;for(i=1; i=26; i+)j = i;while(htj.key != NULLKEY)if(hash(htj.key) = i)printf(%sn,htj.key);j = (j+1)%m;void main()/int i,j;char *k;int result;HashTable ht;float uasLength;createhash(&ht);k = (char *)malloc(10*sizeof(char);printf(请输入要查找的元素:);fflush(stdin);gets(k);result = HashSearch(ht,k);if(result = -1)printf(未找到!n);elseprintf(元素位置为%dn,result);实验结果及分析第一题结果字符整数分析：程序能够正常运行，没有错误，输入长度为10的线性表，并且