云南大学软件学院数据结构实验7学生信息管理系统

1、云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）序号学号姓名成绩123指导教师（签名）实验难度： A B C 学 期：2013秋季学期任课教师：张德海实验题目：学生信息管理系统小组长：联系电话：电子邮件：完成提交时间：2013年12月17日数据结构实验成绩考核表评分项目评分指标分值得分实验构思 （10%）1.实验目的明确52.实验内容理解透彻、对实验所涉 及到的知识点分析到位5实验设计 （15%）1.有对基本数据结构的抽象数据类 型定义52.实验方案设计完整，数据结构、 算法选择合理53.算法结构和程序功能模块之间逻 辑清晰、有相

2、应的流程图5实验实现 （25%）1.代码编写规范、风格统、注释 清楚易读52.程序运行正常，测试结果正确153.界面友好、易于操作、有较强的 容错性5实验报告撰写（10%）1.内容详实无缺漏，文字流畅、图 表清楚52.实验结果分析客观、详细，实验 体会真实可信，对原实验方案的改 进和对实验内容的发散性思考5个人工作量（30%）1.个人完成工作量152.个人技术水平103.团队合作精神5实验运作 （10%）1.有一定用户群52.应用前景分析5综合得分： （满分100分）指导教师：评分项目评分指标分值得分实验构思 （10%）1.实验目的明确52.实验内容理解透彻、对实验所涉 及到的知识点分析到位5

3、实验设计 （15%）1.有对基本数据结构的抽象数据类 型定义52.实验方案设计完整，数据结构、 算法选择合理53.算法结构和程序功能模块之间逻 辑清晰、有相应的流程图5实验实现 （25%）1.代码编写规范、风格统、注释 清楚易读52.程序运行正常，测试结果正确153.界面友好、易于操作、有较强的 容错性5实验报告撰写（10%）1.内容详实无缺漏，文字流畅、图 表清楚52.实验结果分析客观、详细，实验 体会真实可信，对原实验方案的改 进和对实验内容的发散性思考5个人工作量（30%）1.个人完成工作量152.个人技术水平103.团队合作精神5实验运作 （10%）1.有一定用户群52.应用前景分析5

4、综合得分：（满分100分）指导教师：评分项目评分指标分值得分实验构思 (10%)1.实验目的明确52.实验内容理解透彻、对实验所涉 及到的知识点分析到位5实验设计 (15%)1.有对基本数据结构的抽象数据类 型定义52.实验方案设计完整，数据结构、 算法选择合理53.算法结构和程序功能模块之间逻 辑清晰、有相应的流程图5实验实现 (25%)1.代码编写规范、风格统、注释 清楚易读52.程序运行正常，测试结果正确153.界面友好、易于操作、有较强的 容错性5实验报告撰写(10%)1.内容详实无缺漏，文字流畅、图 表清楚52.实验结果分析客观、详细，实验 体会真实可信，对原实验方案的改 进和对实验

5、内容的发散性思考5个人工作量(30%)1.个人完成工作量152.个人技术水平103.团队合作精神5实验运作 (10%)1.有一定用户群52.应用前景分析5综合得分：(满分100分)指导教师：一、【实验构思（Conceive）】 （10%）设计主要要求分别以电话号码和用户名为关键字建立哈希表，并实现查找功能。 所以本设计的核心问题是如何解决散列的问题，由于结点的个数无法确认，并且如果 采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以采用链地址法 散列算法。采用链地址法，当出现同义词冲突时，使用链表结构把同义词链接在一起。 首先，解决的是定义链表结点，在链接地址法中，每个结点对应一个

6、链表结点，它由 三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以 该链表结点它是由四个域组成。name8、num11和address20都是char浮点型 采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链 表的第一个结点。这些表头结点组成一个一维数组，即哈希表。二、【实验设计（Design）】 （20%）设计哈希表实现学生信息管理系统完成以下要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）采用再哈希法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显

7、示给定用户的记录。具体思路为：（1）对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。 得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码 值相加，然后对20求余。（2）要添加用户信息，即要有实现添加结点的功能函数，所以要设计一个必须包括 一个输入结点信息、添加结点的函数；（3）要实现查找函数，则必须包括一个查找结点的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数（4）最后，程序完成后要对程序进行编译调试，执行后要选择数据进行测试，三、【实现描述(Implement)】 (30%)1建立节点struct nodechar

8、 name8,address20;char num11;node * next;typedef node* pnode; /可以为一个已有的数据类型声明多个别名typedef node* mingzi;node *phone;node *nam;node *a;2哈希函数的定义本程序要设计两个hash()函数，分别对应电话号码和用户名。对关键字进行模运算，将运算结果所得的余数作为关键字(或结点)的存储地址，方法如下：以电话号码为 关键字建立哈希函数hash(char num11)。以用户名为关键字建立哈希函数 hash2(char name8)。利用强制类型转换，将用户名的每一个字母的ASCL

9、L码值相 加并且除以20后的余数。将计算出来的数作为该结点的地址赋给key2。void hash(char num11); /以电话号码为关键字建立哈希函数/哈希函数的主旨是将电话号码的十一位数字全部加起来int i = 3;key=(int)num2;while(numi!二NULL)key+=(int)numi;i+；key二key%20; /利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且 除以20后的余数void hash2(char name8); 哈希函数 以用户名为关键字建立哈希函数int i = 1;key2=(int)name0;while(namei!二NUL

10、L)key2+=(int)namei;i+;key2二key2%20;3哈希查找想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码为关 键字，首先，都需要利用hash函数来计算出地址。再通过比对，如果是以电话号码 为关键字，比较其电话号码是否相同，如果相同则输出该结点的所有信息，如果以用 户名为关键字，则比较用户名是否相同，如果相同则输出该结点的所有信息。如果找 不到与之对应相同的，则输出“无此记录”。void find(char num11) ; / 在以电话号码为关键字的哈希表中查找用户信息4流程图以学号为关键字的hash函数流程图Ki：y24-snaniL|i|四、【测试

11、结果(Testing)】 (10%)1、添加记录ESW 选定 C;V/i n d owssyst em 3 2cm d. e-xe验录录翊录统实记记瞽记系哀加找名号空出希H2 _ 345 _A-20121120205tiw：SSS录录刻录茨 实记记蕙记系 养找套辛出 SS姓X追 哈,3_4_b-G_微软拼音-简捷2010半=$毁录录到录统 穿记记翳记系 养找名号击 希添查姓学 哈2.3-4-5_6_ $1请额入姓名；毛饪源撤乂地址，楸一输入学号：20121120036姑= = = = = = = = = = = = = = = = = = = =!_ 4SSSS哈布表实验亭岩亭1 -堡如记录2

12、-置程记录2、查找记录验录录列列录统 实记记幕诡系 霏技名号空出 希馨姓学董 哈1.2.3.4.5.6.7学号查询&姓名登询?清输八兰号20121120205输3登找地信息验录录录统 实记记费正系 专K名号空出 #馨一姓学住豪 哈1.2.3.4.5.6.户辰 P3-tH_20121120205:学号查询，8姓名查询8请输入姓名输出查找的信息Jh=1i$蛛录录录 实近记蕾记 靠扶言空 希曹一姓学清 哈1.2.3.4.5.-20121120274ill13、姓名散列$验录录录统 实记记记系 寄找名号空出 希 101 哈2.3.4.E.J $S$剥视 -20121120274i：lF28121120

13、205 一_201211200364、学号散列哈 12 356$验录录录统 实记记翳记系 需找名号空出 希警一姓学住隅芋首散列绡果卢辱阳_楸二_2史用洞海-20121120036刘羽楸一-201211202745、清空记录列表已清空$以录录:录统 实记记暮记系寿找名号空出 希警姓学注 1 -1 2 3 4 5 6$ $五、【实验总结】(10%)卢晨阳 20121120205:主要负责：程序算法的设计和程序实现，实验报告的部分撰写经验总结：1、我们定义了两个哈希函数，一个以学号为关键字，另一个以姓名ASCII 之和求模之后的值为关键字。第一种是将学号从第二位开始逐一累加 并将所得结果对30求模得

14、哈希地址。第二种则是将姓名字符进行强制 类型转换之后得ASCII码相加对30求模得哈希地址。2、哈希表问题，在存储位置和关键字之间建立对应关系f，根据对应关系 f找到定值K。若结构中存在关键字和定值K相等的记录，必定在f(K) 的存储位置上，由此可以省去比较过程，直接找到所查记录。3、。由于长度无法确定，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题，所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，可以使用链表结构把同义词链接在一起 即同义词的存储地址不是散列表中其他的空地址。毛钰源 20121120036：主要负责：程序算法的部分改进和界面设计，部分接口的实现经

15、验总结：1、哈希表的实现，其主要的精妙之处在于，重载了 口这个运算符，然后 在判断哈希表是否为空时，初始化。2、在实验中虽然使用得仍然是倒插入指针头的方法，但其始终保持着在 散列的地址第一位。且在此次实验中，主要是要分清nHash与key二 者的区别，前者是由后者通过HashKey ()函数算出来的，但还是有一 定的区别的。3、哈希表其实不难，考验的是我们的学习态度，独立思考问题，和解决 问题的能力。把握这次机会大有收获。刘羽 20121120274：主要负责：程序部分算法的实现，数据测试和部分实验报告的撰写经验总结：1、在程序的重载的口函数里，通过GetAssocAt ()函数来判断KEY是

16、滞相 等，如果不等，则新关联一个到当前的哈希表内。否则，返回当前值。2、我们定义有3个域的节点，这三个域分别为学号char num30，姓名 char name30，地址char address30。这种类型的每个节点对应链 表中的每个节点，其中电话号码和姓名可分别作关键字实现哈希表的 创建。3、“哈希表问题”基本算法老师在课堂上有涉及过，但具体的还要靠自己去钻研。通过本次课程设计对哈希表问题有了一个比较全面的认识和 了解。六、【项目运作描述(Operate)】 (10%)在运作部分没有图形界面，只能在DOS下面运行，虽然成本很低，但推广的价值 意义不是很大。且此次程序仍然能够满足一些要求，比

17、如哈希表的建立以及解决冲突 问题，程序中查找也可以正常实现，是基本达到了实验的要求。七、【代码】(10%)#include#include#define NULL 0unsigned int key;unsigned int key2;int *p;struct nodechar name8,address20;char num11;node * next;typedef node* pnode;typedef node* mingzi;node *phone;node *nam;node *a;void hash(char num11)int i = 3;key=(int)num2;whil

18、e(numi!=NULL) key+=(int)numi;i+；key=key%20;void hash2(char name8)int i = 1;key2=(int)name0;while (namei!=NULL)key2+=(int)namei;i+;key2=key2%20;printf(ndz=%dn,key2);node* input()node *temp;temp = new node;temp-next=NULL;printf(请输入姓名：)；scanf(%s”,temp-name);printf(输入地址：)；scanf(%s”,temp-address);printf(

19、输入学号：)；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 = phonekey-next;phonekey-next=newphone;newname-next = namkey2-next;namkey2-next=newname;return 0;

20、void create() int i;phone=new pnode20;for(i=0;inext=NULL;void create2()int i;nam=new mingzi20;for (i=0;inext=NULL;void list()int i;node *p;for(i=0;inext;printf(%s_%s_%sn”,p-name,p-address,p-num);p=p-next;void list2()int i;node *p;for (i=0;inext;while (p)printf(%s_%s_%sn”,p-name,p-address,p-num);p=p-next;void find(char num11)hash(num);node *q=phonekey-next;while (q!= NULL)if (strcmp(num,q-num)=0)break;q=q-next;if (q)printf(%s_%s_%sn”,q-name,q-address,q-num);else printf(无此记录 n);void find2(char name8)hash2(name);node