云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □学期：2010秋季学期任课教师:实验题目: 查找算法设计与实现姓名: 王辉学号: 20091120154电子邮件:完成提交时间： 2010 年 12 月 27 日云南大学软件学院2010学年秋季学期《数据结构实验》成绩考核表学号：姓名：本人承担角色：综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。

）（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。

难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)1 哈希表查找。

根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。

熟悉各种查找算法的思想。

2、掌握查找的实现过程。

3、学会在不同情况下运用不同结构和算法求解问题。

4 把每个学生的信息放在结构体中：typedef struct //记录{NA name;NA tel;NA add;}Record;5 void getin(Record* a)函数依次输入学生信息6 人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。

并采用二次探测再散列法解决冲突。

7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。

完成按姓名查询的操作。

将初始班级的通讯录信息存入文件。

二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）1抽象数据类型的功能规格说明和结构体：#include<stdio.h>#include<stdlib.h>#include<string>#include <windows.h>#define MAXSIZE 20 //电话薄记录数量#define MAX_SIZE 20 //人名的最大长度#define HASHSIZE 53 //定义表长#define SUCCESS 1#define UNSUCCESS -1#define LEN sizeof(HashTable)typedef int Status;typedef char NA[MAX_SIZE];typedef struct //记录{NA name;NA tel;NA add;}Record;typedef struct //哈希表{Record *elem[HASHSIZE]; //数据元素存储基址int count; //当前数据元素个数int size; //当前容量}HashTable;2 主函数与各子函数的调用关系：（通过switch(num)函数按不同功能要求分别调用相关函数）int main(int argc, char* argv[]){system("color 61");int c,flag=1;HashTable *H;H=(HashTable*)malloc(LEN);for(int i=0;i<HASHSIZE;i++)H->elem[i]=NULL;H->size=HASHSIZE;H->count=0;Record a[MAXSIZE];while (1){printf("\n ★☆★☆★☆★☆★☆wang hui★☆★☆★☆★☆★☆★☆");printf("\n ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★");printf("\n ★☆★☆我的未来不是梦★☆★☆");printf("\n ★☆★☆无聊中郁闷死★☆★☆");printf("\n ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★");printf("\n ┏━━━━━━━━━━━━━┓");printf("\n ★┃欢迎欢迎欢迎欢迎欢迎欢迎┃★");printf("\n 〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒"); printf("\n ★★★★★★★哈希表的设计与实现★★★★★★");printf("\n 【】. 添加用户信息");printf("\n 【】. 读取所有用户信息");printf("\n 【】. 以姓名建立哈希表(再哈希法解决冲突) ");printf("\n 【】. 以电话号码建立哈希表(再哈希法解决冲突) ");printf("\n 【】. 查找并显示给定用户名的记录");printf("\n 【】. 查找并显示给定电话号码的记录");printf("\n 【】. 清屏");printf("\n 【】. 保存");printf("\n 【】. 退出程序");printf("\n 温馨提示：");printf("\n Ⅰ.进行操作前请先输出");printf("\n Ⅱ.进行操作前请先输出");printf("\n ★★★★★★★〒〒〒〒〒〒〒〒〒★★★★★★");printf("\n");printf("请输入一个任务选项>>>");printf("\n");int num;scanf("%d",&num);switch(num){case 1:getin(a);break;case 2:ShowInformation(a);break;case 3:CreateHash1(H,a); /* 以姓名建立哈希表*/break;case 4:CreateHash2(H,a); /* 以电话号码建立哈希表*/break;case 5:c=0;SearchHash1(H,c);break;case 6:c=0;SearchHash2(H,c);break;case 7:Cls(a);break;case 8:Save();break;case 9:return 0;break;default:printf("你输错了，请重新输入!");printf("\n");}}system("pause");return 0;}三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。

）1 主函数打印和主子函数调用：int main(int argc, char* argv[]){system("color 61");int c,flag=1;HashTable *H;H=(HashTable*)malloc(LEN);for(int i=0;i<HASHSIZE;i++)H->elem[i]=NULL;H->size=HASHSIZE;H->count=0;Record a[MAXSIZE];while (1){printf("\n ★☆★☆★☆★☆★☆申平★☆★☆★☆★☆★☆★☆");printf("\n ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★");printf("\n ★☆★☆我的未来不是梦★☆★☆");printf("\n ★☆★☆无聊中郁闷死★☆★☆");printf("\n ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★");printf("\n ┏━━━━━━━━━━━━━┓");printf("\n ★┃欢迎欢迎欢迎欢迎欢迎欢迎┃★");printf("\n 〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒");printf("\n ★★★★★★★哈希表的设计与实现★★★★★★");printf("\n 【】. 添加用户信息");printf("\n 【】. 读取所有用户信息");printf("\n 【】. 以姓名建立哈希表(再哈希法解决冲突) ");printf("\n 【】. 以电话号码建立哈希表(再哈希法解决冲突) ");printf("\n 【】. 查找并显示给定用户名的记录");printf("\n 【】. 查找并显示给定电话号码的记录");printf("\n 【】. 清屏");printf("\n 【】. 保存");printf("\n 【】. 退出程序");printf("\n 温馨提示：");printf("\n Ⅰ.进行操作前请先输出");printf("\n Ⅱ.进行操作前请先输出");printf("\n ★★★★★★★〒〒〒〒〒〒〒〒〒★★★★★★");printf("\n");printf("请输入一个任务选项>>>");printf("\n");int num;scanf("%d",&num);switch(num){case 1:getin(a);break;case 2:ShowInformation(a);break;case 3:CreateHash1(H,a); /* 以姓名建立哈希表*/break;case 4:CreateHash2(H,a); /* 以电话号码建立哈希表*/break;case 5:c=0;SearchHash1(H,c);break;case 6:c=0;SearchHash2(H,c);break;case 7:Cls(a);break;case 8:Save();break;case 9:return 0;break;default:printf("你输错了，请重新输入!");printf("\n");}}system("pause");return 0;}2键盘输入各人的信息:void getin(Record* a) //键盘输入各人的信息{system("cls");printf("输入要添加的个数：\n");scanf("%d",&NUM_BER);int i;for(i=0;i<NUM_BER;i++){printf("请输入第%d个记录的用户名:\n",i+1);scanf("%s",a[i].name);printf("请输入%d个记录的电话号码:\n",i+1);scanf("%s",a[i].tel);printf("请输入第%d个记录的地址:\n",i+1);scanf("%s",a[i].add); //gets(str2);??????}}3显示输入的用户信息和人名的折叠处理:void ShowInformation(Record* a) //显示输入的用户信息{system("cls");int i;for( i=0;i<NUM_BER;i++)printf("\n第%d个用户信息:\n 姓名：%s\n 电话号码：%s\n 联系地址：%s\n",i+1,a[i].name,a[i].tel,a[i].add);}void Cls(Record* a){printf("*");system("cls");}long fold(NA s) //人名的折叠处理{char *p;long sum=0;NA ss;strcpy(ss,s); //复制字符串，不改变原字符串的大小写strupr(ss); //将字符串ss转换为大写形式p=ss;while(*p!='\0')sum+=*p++;printf("\nsum====================%d",sum);return sum;}5哈希函数, 先将用户名进行折叠处理, 折叠处理后的数，用除留余数法构造哈希函数并返回模值; 把字符串转换成整型数,用除留余数法构造哈希函数并返回模值:int Hash1(NA str) //哈希函数{long n;int m;n=fold(str); //先将用户名进行折叠处理m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数return m; //并返回模值}int Hash2(NA str) //哈希函数{long n;int m;n = atoi(str); //把字符串转换成整型数.m=n%HASHSIZE; //用除留余数法构造哈希函数return m; //并返回模值}6冲突处理函数，采用二次探测再散列法解决冲突:Status collision(int p,int &c) //冲突处理函数，采用二次探测再散列法解决冲突{int i,q;i=c/2+1;while(i<HASHSIZE){if(c%2==0){c++;q=(p+i*i)%HASHSIZE;if(q>=0) return q;else i=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0) return q;else i=c/2+1;}}return UNSUCCESS;}void benGetTime();void CreateHash1(HashTable* H,Record* a) //建表，以人的姓名为关键字，建立相应的散列表{system("cls"); //若哈希地址冲突，进行冲突处理benGetTime();int i,p=-1,c,pp;for(i=0;i<NUM_BER;i++){c=0;p=Hash1(a[i].name);pp=p;while(H->elem[pp]!=NULL) {pp=collision(p,c);if(pp<0){printf("第%d记录无法解决冲突",i+1); //需要显示冲突次数时输出continue;} //无法解决冲突，跳入下一循环}H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入H->count++;printf("第%d个记录冲突次数为%d。