数据结构课程设计 - — - 通讯录的制作 - 图文

选择“0”， 显示通讯录信息并退出通讯录，则有下图： 然后按任意键退出程序。 4.4.2分析 调试过程中我认为比较复杂的是用哈希表的二次探测再散列法解决冲突的算法不是特别容易研究明白，故对整个哈希表的定义与执行都是个不小的挑战，于是我设法通过查询资料，对其算法进行了仔细的分析，只要将二次探测再散列法的数学关系式琢磨透了，对于算法的表达就容易多了。因为二次探测再散列法是对出现冲突后，进行的摆动数列的方法解决冲突，其中需要考虑数据的变化、符号的改变和位置的准确移动，所以数学关系式思考起来比较麻烦。 4.5 程序代码 #include #include #include #define MAXSIZE 20 //电话薄记录数量 #define MAX_SIZE 20 //人名的最大长度 #define HASHSIZE 31 //定义表长 #define SUCCESS 1 #define UNSUCCESS -1 #define LEN sizeof(HashTable) //hashTable的长度 typedef int Status; typedef char NA[MAX_SIZE]; typedef struct{ //每一条电话本记录 17

NA name; NA tel; NA add; }Record; typedef struct{ //哈希表 Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; Status eq(NA x,NA y) { //关键字比较，相等返回SUCCESS；否则返回UNSUCCESS if(strcmp(x,y)==0) return SUCCESS; else return UNSUCCESS; }Status NUM_BER; //记录的个数 long fold(NA s) { //人名的折叠处理,就是将名字转换成一个数值 char *p; long sum=0; NA ss; strcpy(ss,s); //复制字符串，不改变原字符串的大小写//strupr(ss);//将字符串ss转换为大写形式 p=ss; while(*p!='\\0') sum+=*p++; //将字符串转换成一个int型的值用于hash表的计算比较 printf(\的转换hashCode是%ld\\n\ return sum; } int Hash1(NA str) { //哈希函数 long n; int m; n=fold(str); //先将用户名进行折叠处理 m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数 return m; //并返回模值 } 18

int Hash2(NA str) { //哈希函数 long n; int m; n = atoi(str); //把字符串转换成整型数. m=n%HASHSIZE; //用除留余数法构造哈希函数 return m; //用除留余数法构造哈希函数 } Status collision(int p,int c) { //冲突处理函数，采用二次探测再散列法解决冲突 int i,q; i=c/2+1; while(i=0) { printf(\ return q; } else { i=c/2+1; printf(\ return UNSUCCESS; } } else { q=(p-i*i)%HASHSIZE; c++; if(q>=0) { return q; } else { i=c/2+1; printf(\ return UNSUCCESS; } } } return UNSUCCESS; } void CreateHash1(HashTable* H,Record* a) { //建表，以人的姓名为关键字，建立相应的散列表 //若哈希地址冲突，进行冲突处理 19

int i,p=-1,c,pp; for(i=0;ielem[pp]!=NULL) { pp=collision(p,c); if(pp<0) { printf(\第%d记录无法解决冲突\ //需要显示冲突次数时输出 continue; } //无法解决冲突，跳入下一循环 } H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入 H->count++; printf(\第%d个记录冲突次数为%d。\\n\ //需要显示冲突次数时输出 } printf(\建表完成!\\n此哈希表容量为%d,当前表内存储的记录个数为%d.\\n\} void SearchHash1(HashTable* H,int c) { //在通讯录里查找姓名关键字，若查找成功，显示信息 int p,pp; //c用来记录冲突次数,查找成功时显示冲突次数 NA str; printf(\请输入要查找记录的姓名：\\n\ scanf(\ p=Hash1(str); pp=p; while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1)) pp=collision(p,c); if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1) { printf(\查找成功！\\n查找过程冲突次数为%d．以下是您需要要查找的信息：\\n\\n\ printf(\姓名：%s\\n电话号码：%s\\n联系地址：%s\\n\ } 20