word/media/image1.gif
（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）
实验难度： A □ B □ C □
学 期： 2013秋季学期
任课教师: 张德海
实验题目: 学生信息管理系统
小 组 长:
联系电话:
电子邮件:
完成提交时间：2013年 12月17日
《数据结构实验》成绩考核表
综合得分：（满分100分）
指导教师： 年 月 日
综合得分：（满分100分）
指导教师： 年 月 日
综合得分：（满分100分）
指导教师： 年 月 日
一、【实验构思（Conceive）】(10%)
设计主要要求分别以电话号码和用户名为关键字建立哈希表，并实现查找功能。所以本设计的核心问题是如何解决散列的问题，由于结点的个数无法确认，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，使用链表结构把同义词链接在一起。 首先，解决的是定义链表结点，在链接地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成。name[8] 、num[11]和address[20]都是char浮点型采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。
二、【实验设计(Design)】(20%)
设计哈希表实现学生信息管理系统完成以下要求：
（1）设每个记录有下列数据项：电话号码、用户名、地址；
（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；
（3）采用再哈希法解决冲突；
（4）查找并显示给定电话号码的记录；
（5）查找并显示给定用户的记录。
具体思路为：
（1）对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。
得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值相加，然后对20求余。
（2）要添加用户信息，即要有实现添加结点的功能函数，所以要设计一个必须包括
一个输入结点信息、添加结点的函数；
（3）要实现查找函数，则必须包括一个查找结点的函数；
另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数
（4）最后，程序完成后要对程序进行编译调试，执行后要选择数据进行测试，
三、【实现描述（Implement）】(30%)
1 建立节点
struct node
{
char name[8],address[20];
char num[11];
node * next;
};
typedef node* pnode; //可以为一个已有的数据类型声明多个别名
typedef node* mingzi;
node **phone;
node **nam;
node *a;
2 哈希函数的定义 本程序要设计两个
hash（）函数，分别对应电话号码和用户名。对关键字进行模运算，
将运算结果所得的余数作为关键字（或结点）的存储地址，方法如下：以电话号码为关键字建立哈希函数hash(char num[11])。以用户名为关键字建立哈希函数hash2(char name[8])。利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数。将计算出来的数作为该结点的地址赋给key2。
void hash(char num[11]); //以电话号码为关键字建立哈希函数
//哈希函数的主旨是将电话号码的十一位数字全部加起来
{
int i = 3;
key=(int)num[2];
while(num[i]!=NULL)
{
key+=(int)num[i];
i++;
}
key=key%20; } //利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除
以20后的余数
void hash2(char name[8]); //哈希函数 以用户名为关键字建立哈希函数
{
int i = 1;
key2=(int)name[0];
while(name[i]!=NULL)
{
key2+=(int)name[i];
i++;
}
key2=key2%20;
}
3 哈希查找
想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码为关键字，首先，都需要利用hash函数来计算出地址。再通过比对，如果是以电话号码为关键字，比较其电话号码是否相同，如果相同则输出该结点的所有信息，如果以用户名为关键字，则比较用户名是否相同，如果相同则输出该结点的所有信息。如果找不到与之对应相同的，则输出“无此记录”。 void find(char num[11]) ; //
在以电话号码为关键字的哈希表中查找用户信息
4 流程图
以学号为关键字的hash函数流程图
以姓名为关键字的hash函数流程图
四、【测试结果（Testing）】(10%)
1、添加记录
2、查找记录
3、姓名散列
4、学号散列
5、清空记录
五、【实验总结】(10%)
卢晨阳 20121120205：
主要负责：程序算法的设计和程序实现，实验报告的部分撰写
经验总结：1、我们定义了两个哈希函数，一个以学号为关键字，另一个以姓名ASCII之和求模之后的值为关键字。第一种是将学号从第二位开始逐一累加并将所得结果对30求模得哈希地址。第二种则是将姓名字符进行强制类型转换之后得ASCII码相加对30求模得哈希地址。
2、哈希表问题，在存储位置和关键字之间建立对应关系f，根据对应关系f找到定值K。若结构中存在关键字和定值K相等的记录，必定在f（K）的存储位置上，由此可以省去比较过程，直接找到所查记录。
3、。由于长度无法确定，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题，所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，可以使用链表结构把同义词链接在一起 即同义词的存储地址不是散列表中其他的空地址。
毛钰源 20121120036：
主要负责：程序算法的部分改进和界面设计，部分接口的实现
经验总结：1、哈希表的实现，其主要的精妙之处在于，重载了[]这个运算符，然后在判断哈希表是否为空时，初始化。
2、在实验中虽然使用得仍然是倒插入指针头的方法，但其始终保持着在散列的地址第一位。且在此次实验中，主要是要分清nHash与key二者的区别，前者是由后者通过HashKey()函数算出来的，但还是有一定的区别的。。
3、哈希表其实不难，考验的是我们的学习态度，独立思考问题，和解决问题的能力。把握这次机会大有收获。
刘羽 20121120274：
主要负责：程序部分算法的实现，数据测试和部分实验报告的撰写
经验总结：1、在程序的重载的[]函数里，通过GetAssocAt()函数来判断KEY是滞相等，如果不等，则新关联一个到当前的哈希表内。否则，返回当前值。
2、我们定义有3个域的节点，这三个域分别为学号char num[30]，姓名char name[30]，地址char address[30]。这种类型的每个节点对应链表中的每个节点，其中电话号码和姓名可分别作关键字实现哈希表的创建。
3、“哈希表问题”基本算法老师在课堂上有涉及过，但具体的还要靠自己去钻研。通过本次课程设计对哈希表问题有了一个比较全面的认识和了解。
六、【项目运作描述（Operate）】(10%)
在运作部分没有图形界面，只能在DOS下面运行，虽然成本很低，但推广的价值意义不是很大。且此次程序仍然能够满足一些要求，比如哈希表的建立以及解决冲突问题，程序中查找也可以正常实现，是基本达到了实验的要求。
七、【代码】(10%)
#include
#include
#define NULL 0
unsignedint key;
unsignedint key2;
int *p;
struct node
{
char name[8],address[20];
char num[11];
node * next;
};
typedef node* pnode;
typedef node* mingzi;
node **phone;
node **nam;
node *a;
void hash(char num[11])
{
int i = 3;
key=(int)num[2];
while(num[i]!=NULL)
{
key+=(int)num[i];
i++;
}
key=key%20;
}
void hash2(char name[8])
{
int i = 1;
key2=(int)name[0];
while(name[i]!=NULL)
{
key2+=(int)name[i];
i++;
}
key2=key2%20;
printf("\ndz====================%d\n",key2);
}
node* input()
{
node *temp;
temp = new node;
temp->next=NULL;
printf("请输入姓名:");
scanf("%s",temp->name);
printf("输入地址：");
scanf("%s",temp->address);
printf("输入学号：");
scanf("%s",temp->num);
return temp;
}
int apend()
{
node *newphone;
node *newname;
newphone=input();
newname=newphone;
newphone->next=NULL;
newname->next=NULL;
hash(newphone->num);
hash2(newname->name);
newphone->next = phone[key]->next;
phone[key]->next=newphone;
newname->next = nam[key2]->next;
nam[key2]->next=newname;
return 0;
}
void create()
{
int i;
phone=new pnode[20];
for(i=0;i<20;i++)
{
phone[i]=new node;
phone[i]->next=NULL;
}
}
void create2()
{
int i;
nam=new mingzi[20];
for(i=0;i<20;i++)
{
nam[i]=new node;
nam[i]->next=NULL;
}
}
void list()
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=phone[i]->next;
while(p)
{
printf("%s_%s_%s\n",p->name,p->address,p->num);
p=p->next;
}
}
}
void list2()
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=nam[i]->next;
while(p)
{
printf("%s_%s_%s\n",p->name,p->address,p->num);
p=p->next;
}
}
}
void find(char num[11])
{
hash(num);
node *q=phone[key]->next;
while(q!= NULL)
{
if(strcmp(num,q->num)==0)
break;
q=q->next;
}
if(q)
printf("%s_%s_%s\n",q->name,q->address,q->num);
else printf("无此记录\n");
}
void find2(char name[8])
{
hash2(name);
node *q=nam[key2]->next;
while(q!= NULL)
{
if(strcmp(name,q->name)==0)
break;
q=q->next;
}
if(q)
printf("%s_%s_%s\n",q->name,q->address,q->num);
else printf("无此记录\n");
}
void menu() //菜单
{
printf("\t\t\t $$$$哈希表实验$$$$\n");
printf("\t\t\t 1.添加记录\n");
printf("\t\t\t 2.查找记录\n");
printf("\t\t\t 3.姓名散列\n");
printf("\t\t\t 4.学号散列\n");
printf("\t\t\t 5.清空记录\n");
printf("\t\t\t 6.退出系统\n");
}
int main()
{
char num[11];
char name[8];
create();
create2() ;
int sel;
while(1)
{
menu();
scanf("%d",&sel);
if(sel==2)
{
printf("7学号查询，8姓名查询\n");
int b;
scanf("%d",&b);
if(b==7)
{
printf("请输入学号\n");
scanf("%s",num);
printf("输出查找的信息\n");
find(num);
}
else
{
printf("请输入姓名\n");
scanf("%s",name);
printf("输出查找的信息\n");
find2(name);
}
}
if(sel==3)
{
printf("姓名散列结果\n");
list2();
}
if(sel==1)
{
apend();
}
if(sel==4)
{
printf("学号散列结果\n");
list();
}
if(sel==5)
{
printf("列表已清空\n");
create();create2();
}
if(sel==6)
return 0;
}
return 0;
}
本文来源：https://www.2haoxitong.net/k/doc/d6c29b89f11dc281e53a580216fc700abb6852a2.html
文档为doc格式