算法設计与分析导论.docVIP

算法设计与分析导论 学号：3120107218 专业：过程装备与控制工程122 姓名：宋梓瑜 日期：2013年11月6日 .问题描述： 1.输入一些整数，采用哈希表结构存储； 2.实现对哈希表的查找； 3.程序采用子程序结构，结构清晰； 4.友好清晰的用户界面，能识别输入错误并控制错误的修改。 .概要设计： ⒈?为实现上述算法，需要顺序表的抽象数据类型：? ADT?Hash?{? 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可 唯一标识数据元素的关键字。? 数据关系R：数据元素同属一个集合。?基本操作P:? Creathash(h)? 操作结果：构造一个具有n个数据元素的哈希查找表h。??destroyhash(h)? ????初始条件：哈希查找表h存在。?????操作结果：销毁哈希查找表h。??displayhash（h）? ????初始条件：哈希查找表h存在。?????操作结果：显示哈希查找表h。?hash(h，k)? 初始条件：哈希查找表h存在。? 操作结果：通过除留余数法得到地址用k返回。?hash2?(i，k)? 初始条件：哈希查找表h存在存在，i是除留余数法得到的地址。?操作结果：返回二次探测再散列解决冲突得到的地址k。?search?(h，key)? 初始条件：哈希查找表h存在。? ????操作结果：查找表h中的key，若查找成功，返回其地址，否则返回 -1? insert?(h，key)? 初始条件：哈希查找表h存在。? 操作结果：若表h中没有key，则在h中插入key。? ????????????????search1(h,?key,p)? 初始条件：哈希查找表h存在。? 操作结果：在表h中查找key，若没有，则返回p的插入的地址，否 则返回-1。? ?}ADT?Hash? 2.?本程序有三个模块：? ⑴?主程序模块? ?main(){?初始化；?{? 接受命令；?显示结果；?｝?｝? ⑵?创建hash表的模块：主要建立一个哈希表；? ⑶解决冲突模块：利用开放地址的二次探测再散列解决冲突；? 输出哈希表模块：显示已创建哈希表。 .详细设计： ⒈元素类型，结点类型?typedef?struct?{? ????int?key;?}keytype;? typedef?struct?{? ????keytype?elem[100];? int?length;???/*当前的长度*/?????int?size;??/*哈希表的总长*/?}hashtable;?/*全局变量*/?int?a=0,b=0;?/*哈希函数*/? 2.对抽象数据类型中的部分基本操作的伪码算法如下：?/*哈希函数*/? int?hash(hashtable?*h,int?k)?{? ????return??k%h-size;?}? /*二次探测再散列解决冲突*/?int?hash2(int?i,int?t)?{??if(i%2==0)??????t=t+pow(++a,2);???? else t=t-pow(++b,2);????return?t;?}? /*创建哈希表*/? void?creat(hashtable?*h)?{??int?i,j,key,t,p;? ???printf(input?hash?size?and?length:);????scanf(%d%d,h-size,h-length);????for(i=0;ih-size;i++)????h-elem[i].key=-1;????printf(input?data:\n);????for(j=0;jh-length;j++)?????{??scanf(%d,key);????????p=hash(h,key);????????if(h-elem[p].key==-1)??????????h-elem[p].key=key;????????else??????????{??i=0;?????????????t=p;? ????????????while(h-elem[p].key!=-1h-elem[p].key!=keyih-size/2)???????????????{??p=hash2(i,t);??????????????????i++;???????????????}?????????????a=b=0;? ????????????h-elem[p].key=key;??????????}??????}?}? /*查找哈希表中的元素，返回元素的地址，否则返回-1*/?int?search(hashtable?*h,int?key)?{??int?p,t,i=0;??