算法设计与分析导论

《算法设计与分析导论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析导论学号：3120107218专业：过程装备与控制工程122姓名：宋梓瑜日期：2013年11月6日（1）.问题描述：1.输入一些整数，采用哈希表结构存储；2.实现对哈希表的查找；3.程序采用子程序结构，结构清晰；4.友好清晰的用户界面，能识别输入错误并控制错误的修改。(2).概要设计：⒈ 为实现上述算法，需要顺序表的抽象数据类型： ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P: Creathash(&h) 操作结果：构造一个

2、具有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存在。     操作结果：查找

3、表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表的模块：主要建立一个哈希表； ⑶解决冲突模块：利用开放地址的二次探测再散列解决

4、冲突； (4)输出哈希表模块：显示已创建哈希表。（3）.详细设计：⒈元素类型，结点类型 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) {  

5、   return  k%h->size; } /*二次探测再散列解决冲突*/ int hash2(int i,int t) {  if(i%2==0)      t=t+pow(++a,2);    elset=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;i<

6、h->size;i++)    h->elem[i].key=-1;    printf("input data:");    for(j=0;jlength;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!=-1&&h->

7、elem[p].key!=key&&isize/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;    p=hash(h,key);    t=p;    while(

8、h->elem[p].k