网络101第四组课程设计报告.doc

陕西科技大学电信学院数据结构课程设计报告名 称: “校园之星”投票系统 班 级: 网络101 组 别: 第四组 成 员: 李昀隆 霍杏 吕佳骏 赵晨 胡波 杨康宁 指导教师: 赵晓 学年学期: 2011 2012 学年 第 一 学期 2011 年 12 月 28 日摘 要本课程设计题目为校园之星投票系统，这个系统可以为你心中的校园之星投票及进行评价，并可以查看学生的得票数和评价情况。另外，系统还可以生成截止某一时刻的投票情况统计清单。我们主要运用了数据结构的两块知识：一个是哈希表的相关内容，其中具体包括哈希表的创建、查找、插入、冲突处理。输入的学生拼音名字的ASCII码值之和对哈希表长取余，获得哈希地址。投票时，进行哈希查找，若查找成功，则票数加一，若查找失败，则将其姓名插入到哈希表中。另一个是有关文件的创建、读写的相关内容。系统运行时会自动生成一个.txt的文件，将学生姓名及票数都记录在内，以便随时调出查看。主函数中用switch语句实现多分枝选择，来实现不同的功能。本程序的优点在于用哈希表来进行查找文件中的内容，这样调用的时候很方便，而且当面对群体较广，上榜学生较多时，查找速度会比较快。关键字：哈希表；文件；投票；查看；目 录1 需求分析42 概要设计43 详细设计44 调试分析45 测试结果46 课设总结57 参考文献5数据结构课程设计报告一 需求分析1、程序的功能 校园之星投票系统主要实现了四个功能：1给您心中的校园之星投票和评价 2.查看某位学生的票数 3.查看某位学生获得的评价 4.截止目前投票情况 给您心中的校园之星投票和评价功能中，实现投票和评价功能，我们运用了投票函数vote，在此函数中包括了哈希表的查找HashSearch(ht,x), 在哈希表查找中地址为正，则找到这个人，投一票，地址为负时则把地址转正，增加此人，并把新的投票信息付给此人，加入到哈希表中。在投票函数中还调用了写文件函数WriteBoard(filename,x,addr)，将学生的投票信息写入到txt格式的文件中。查看某位学生的票数的功能中，运用的是Dispvote函数。此函数中主要调用的是哈希查找HashSearch(ht,x)，实现对某位同学票数的查看。查看某位学生的评价功能中，运用的是Dispevaluate函数，其原理同DispVote函数相同。截止目前投票情况功能中，运用了函数Dissituation，其主要是通过一个循环来遍历哈希地址将所有学生的得票情况打印出来。2、输出形式 给您心中的校园之星投票和评价功能中，投票人输入学生姓名和评价，即可，输出，恭喜投票成功。查看某位学生的票数和评价两个功能中，投票人输入学生的名字查找该同学，查找成功则显示该同学的相关信息，否则输出对不起，没有您要查找的学生，请检查输入是否正确,返回主菜单重新输入，若输入无误，则该生还没有上榜，您可以返回主菜单为其投票哦。 截止目前投票情况中会输出目前为止所有的投票信息 声明中会输出程序相关的声明。3、初步测试计划 小组内每个人对自己所编写的函数进行测试，成功后合并到一起进行调试。对所出现的问题集体进行讨论，然后修改再运行，直至整个程序运行成功。 修改时我们主要用了printf打印法，缩小范围，查找出错地方。程序中投票人只需输入数字（1,2,3,4,5,）便可选择想要实现的功能。在case 1中投票者需输入所喜欢学生的拼音名字，以及对他的评价；在case2，case3中投票人输入学生的拼音名字即可查看其得票数和他人的评价。初步测试成功。二、概要设计一、子函数功能介绍1、 建立文件CreateBoard：初始化所有学生的得票信息 2、 读取文件内容ReadBoard：生成的文件为二进制随机存取文件，文件内容为上榜学生的信息，即DataType类型的数据。文件中的记录按照哈希地址来存放。3、 写文件WriteBoard：把修改后的学生信息或新上榜的学生信息写入文件中的指定位置。4、 哈希表的创建CreateHash：首先将表中各节点的关键字清空，使其地址为开放的；然后调用插入的算法将给定的数据元素序列items一次插入哈希表中。5、 哈希表的插入HashInsert：首先调用查找算法在哈希表中待插入的数据元素，若在表中找到待插入的数据元素，则不必插入；若在表中没找到待插入的数据元素，此时查找算法给出一个单元空闲的哈希地址，则将待插入的数据元素插入到该哈希地址对应的空闲单元中。6、哈希表的查找HashSearch：哈希表的查找过程与创建哈希表过程类似7、哈希函数HashFunc：采用除留余数法构造哈希函数8、冲突处理函数Collision：在开放定址法中，选用线性探查法处理冲突9、投票函数Vote：为学生投票分为两种情况：一是学生已经在榜上，那么给学生的票数加一；二是学生不在榜上，那么把学生插入哈希表中，并保存在文件中。10、查看学生得票情况DispVote：根据学生的名字在哈希表中查找学生，并显示学生的得票数。11、查看学生的评价Dispevaluate：根据学生的名字在哈希表中查找学生，并显示他人对该生的评价。12、截至目前投票情况查询函数Dissituation13、声明函数claim II、函数的调用关系 三， 小组分工情况 起初我们在一起讨论了课设题目，需要用到的数据结构知识，算法，列出了整体框架，流程 按照框架分好了每个人的任务，下页所示。分头去查阅资料，完成各自的任务，随时在讨论 在一起合程序，运行调试。一起努力，看到了黎明的曙光。李昀隆 Main函数调试及后期美化处理 霍杏 哈希表创建相关函数 吕佳骏 文件的读写函数 赵晨 票数，评价查询函数 胡波 创建榜单函数，投票情况显示 杨康宁 声明，花边函数 3 详细设计、函数流程图开始输入choice输入x.pinyin输入x.pingjiax.pinyin输入x.pinyin声明函数结束投票函数显示评价函数显示票数函数输入 k结 束K=0K为任意数字显示投票情况函数123450二，用到的数据结构的知识及相关数据结构的描述形式1、哈希表 在线性表、树等结构中，记录在结构中的相对位置是随机的，和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。理想的情况是不经过任何比较，一次存取便能得到所查记录，那就必须在存储的记录位置和它的关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应，这个对应关系即为哈希函数，按这个思想建立的表称为哈希表。2、哈希函数的构造除留余数法构造哈希函数：取关键字被某个不大与哈希表表长m的数p除后所得余数为哈希地址。即 H（key）=key MOD p, pm3、哈希表的插入首先调用查找算法在哈希表中待插入的数据元素，若在表中找到待插入的数据元素，则不必插入；若在表中没找到待插入的数据元素，此时查找算法给出一个单元空闲的哈希地址，则将待插入的数据元素插入到该哈希地址对应的空闲单元中。4、哈希表的查找根据待查找的数据元素x和建表时的哈希函数计算哈希地址；若该地址所对应的单元为空，则查找失败；若不为空，则将该单元中节点的关键字与x的关键字比较：若相等查找成功，若不相等则按建表时设定的处理冲突的方法找下一个地址。5、处理冲突的方法在开放定址法中，选用线性探查法处理冲突6、文件的读写文件一般指存储在外部介质上的数据的集合。用fopen函数打开文件：fopen(“al”,”r”)；用fclose关闭文件：fclose(fp);用二进制方式向文件读写一组数据：fread(buffer,size,count,fp),fwrite(buffer,size,count,fp);用fseek改变文件位置标记：fseek(文件类型指针，位移量，起始点)。写入的数据存储在生成的txt文件中。程序如下#include stdio.h #include malloc.h#include string.h#include stdlib.h#include / 清屏函数所在头文件/#define HASHSIZE 41#define NULLKEY 0typedef int KeyType;typedef struct KeyType key; char pinyin20; char pingjia50;DataType;typedef struct Node DataType data; struct Node *left,*right;BSTNode,*BSTree;typedef structDataType data;int times;HashItem,HashTableHASHSIZE; /*获得哈希地址*/根据以拼音表示的学生姓名计算哈希地址 int HashFunc(char key) /实参为x.pinyin /* key为学生的姓名*/ int addr=0,i=0; while(keyi!=0)addr+=(int)keyi;i+;/key为拼音的ASCII码值 return addr % HASHSIZE; /*冲突处理*/int Collision(int d) return(d+1)%HASHSIZE;/*哈希查找*/int HashSearch(HashTable ht,DataType x) int addr; addr=HashFunc(x.pinyin); if (strcmp(htaddr.data.pinyin,NULLKEY) & strcmp (htaddr.data.pinyin,x.pinyin) /第一个比较说明输入不为空，不等于0，为真，说明不为空 /第二个比较说明不存在，为真。则说明没找到，用冲突处理看能否找到 addr=Collision(addr); /看看冲突处理能不能找到 if(!strcmp(htaddr.data.pinyin ,x.pinyin) return addr; /找到了返回地址 else return -addr; /返回负地址/*哈希插入*/int HashInsert(HashTable ht,DataType x)int addr;addr=HashSearch(ht,x);if(addr0) return 0;elseht-addr.data=x;ht-addr.times=1;return 1;/*哈希创建*/void CreateHash(HashTable ht,DataType items,int n)/*利用所给关键序列items创建哈希表，N为关键字个数*/int i;for(i=0;iHASHSIZE;i+) /*初始化哈希表*/hti.data.key=NULL;hti.times=0;for(i=0;i0) /哈希查找中地址为正，则找到这个人了，投一票 htaddr.data.key+; x=htaddr.data; else addr=-addr; /把地址转正了，增加此人 htaddr.data=x; /把新的投票信息付给此人，加入到哈希表 WriteBoard(filename,x,addr); printf(n - - - - -亲! 恭喜! 投票成功- - - - - -nn);/CASE2/*查询学生的评价*/ void Dispevaluate(HashTable ht,DataType x) /*ht 为哈希表，x为要查找的学生信息*/ int addr; addr=HashSearch(ht,x); if(addr=0) printf(nn学生 %s 的同学评价为- %s -nn,htaddr.data.pinyin,htaddr.data.pingjia); else printf(nn对不起，没有您要查找的学生，请检查输入是否正确，返回主菜单重新输入nn); printf(若输入无误，则该生还没有上榜，您可以返回主菜单为其投票哦n); /CASE3/*查询学生得票情况*/ void DispVote(HashTable ht,DataType x) /*ht为哈希表，x为要查找的学生信息*/ int addr; addr=HashSearch(ht,x); if(addr=0) printf(nn学生 %s 的票数为 %d nn,htaddr.data.pinyin,htaddr.data.key); else printf(nn对不起，没有您要查找的学生，请检查输入是否正确,返回主菜单重新输入); printf(nn若输入无误，则该生还没有上榜，您可以返回主菜单为其投票哦n); /CASE4/*截止目前投票情况查询*/void Dissituation(HashTable ht,int addr)printf(n* 投票情况 *);for(addr=0;addr41;addr+) if(htaddr.data.key!=0) printf(nn 学生 %9s 的票数为-* %d *- 恭喜恭喜nn,htaddr.data.pinyin,htaddr.data.key); /case5/*声明函数*/void claim()printf(nn);printf(); printf( 亲，感谢使用本投票系统 nn);printf( 本系统由陕西科技大学电气与信息工程学院网络101班设计nn);printf( 设计者：李昀隆，霍杏，吕佳骏，赵晨，胡波，杨康宁nn);printf( 指导老师：赵晓nn);printf( 本程序最终解释权归陕西科技大学电气与信息工程学院网络101班所有nn);printf( 欢迎您对本系统提出意见或建议。邮箱：nn);printf(n);printf();/*花边函数*/void printfbian()int w=23,i; for (i=1;i=80;i+) printf(%c,w);/*主函数*/int main ()HashTable ht;int k,addr;int choice = 0;DataType x;char filename=sjjg.txt;CreateBoard(ht,filename);B:printfbian() ; printf( n); printf( 2011-1012学年度陕西科技大学校园之星评比活动开始啦！nn); printf( * 校园之星投票系统 *n); printf( -n); printf( * 1.给您心中的校园之星投票 *nn); printf( * 2.查看上榜同学获得的评价 *nn); printf( * 3.查看某位学生的票数 *nn); printf( * 4.截止目前投票情况 *nn); printf( * 5.相关声明 *nn); printf( * 0.退出 *nn);A:printf(nn 请选择1，2，3，4，5, 0nn); scanf(%d,&choice); if(choice5) printf(输入有误，请重新选择); goto A; switch (choice) case 1: flushall(); system (cls); printfbian(); printf(n -欢迎投票-); printf(nn 请输入您心中校园之星的拼音名字:); gets(x.pinyin); printf(n 请输入您对该同学的评价:); gets(x.pingjia); x.key=1; Vote(ht,filename,x); printf (nnnnnnnnnnnnt退出本菜单请按0，返回主菜单请按任意数字。nn); scanf (%d,&k); if(k=0) exit; else system (cls); goto B; break; case 2: system (cls); flushall(); printfbian(); printf(n 请输入您要查询评价的学生拼音名字:); gets(x.pinyin); Dispevaluate(ht,x); printf (nnnnnnnnnnnnt退出本菜单请按0，返回主菜单请按任意数字。nn); scanf (%d,&k); if(k=0) exit; else system (cls); goto B; break; case 3: system (cls); f