数据结构课程设计报告书

数据结构课程设计南通大学计算机学院《数据结构课程设计报告书》题目：校园十大优秀青年评比专业：计算机科学与技术班级:姓名:学号：指导教师:开始日期：2013.1.14完成日期：2013.1.161.问题的描述和分析1.1问题描述新一届校园十大青年评比开始了！每一位在校学生可通过网上评比系统，为自己认为优秀的学生提名与投票。请开发一个用于该需求的系统，满足下列基本功能：(1)提名优秀学生与投票。(2)查看提名学生的基本信息。(3)显示各提名学生的票数。(4)显示排行榜。一．基本要求：.(1)采用散列存储，存放提名学生的相关信息。(2)设计哈希函数和冲突解决方法。(3)提名学生至少包括以下信息：姓名、票数、个人基本信息（如：班级、专业、年级、突出事迹等）。(4)设计输入提名学生信息的界面。(5)完成基本功能。(6)界面友好，操作简单。(7)设计足够多的测试用例。(8)查看指定学生的票数。(9)按序显示各提名学生票数。二．较高要求(1)限制每人的投票次数。(2)按软件要求，扩充其他功能。(3)实现数据的后效验，即不接收非法数据。1.2问题分析（1）用哈希表存储提名学生相关信息。每位选手即学生的基本信息含有多个属性，为此可根据学生信息建立结构体，如下：structstudent{ charname[20];//姓名的拼音intstudentnum;//学号 intnumber;//票数 intClass;//班级 charmajor[30];//专业 chargrade[10];//年级 charachievement[200];//突出事迹};（2）设计哈希函数，并用开放定址线性探测法处理冲突。哈希函数根据姓名拼音的ascll码来设计，hash（key）=key%hashlength，其中k为姓名所有拼音的ascll码值的累加和，hashlength为表长。因此需储存学生姓名的拼音。（3）设计一个投票系统类：votesystemclassvotesystem{private: student*st; intcount;//当前元素个数 inthashlength;//哈希表长public: votesystem(){st=NULL;count=0;hashlength=0;} ~votesystem(){delete[]st;count=0;} voidHashTable(intn);//初始化哈希表 intHash(char*name);//哈希函数 voidcollision(int&s){s=s++;}//开放定址线性探测法处理冲突 inthashfind(char*name,int&k);//查找 voidinserthash(char*name);//插入 intvote(char*name);//投票 voiddisplay();//显示哈希表 voidshowvote(intk);//按哈希表下标显示票数 voidshowrank();//显示排行榜};（4）加入用户登录系统，所以同时构造用户user的结构体；结构体中需要有用户姓名和用户权限次数的数据。structuser{ charusername[20]; introot; user(){root=4;}};2.概要设计2.1系统模块划分选手信息模块选手信息模块评比系统界面模块用户登录模块查询得票模块投票模块前十排行模块退出系统模块图2-1系统模块图2.2ADT（抽象数据类型）描述1.为了满足程序功能的设计，定义了两个结构体；分别是学生选手student和登录用户user；2.定义了投票系统类classvotesystem；3.详细设计3.1ADT基本操作算法设计3.1.1structstudent{ charname[20];//姓名的拼音intstudentnum;//学号 intnumber;//票数 intClass;//班级 charmajor[30];//专业 chargrade[10];//年级 charachievement[200];//突出事迹};structuser{ charusername[20]; introot; user(){root=4;}};userstore[20];3.1.classvotesystem{private: student*st; intcount;//当前元素个数 inthashlength;//哈希表长public: votesystem(){st=NULL;count=0;hashlength=0;} ~votesystem(){delete[]st;count=0;} voidHashTable(intn);//初始化哈希表 intHash(char*name);//哈希函数 voidcollision(int&s){s=s++;}//开放定址线性探测法处理冲突 inthashfind(char*name,int&k);//查找 voidinserthash(char*name);//插入 intvote(char*name);//投票 voiddisplay();//显示哈希表 voidshowvote(intk);//按哈希表下标显示票数 voidshowrank();//显示排行榜};3.2功能模块设计3.2.1评比界面模块（1）界面设计（2）处理流程设计评比系统选择界面：由于选择结构比较单一，故在选择时没有选择使用switch语句，使用简单的if语句；while(choice!=2) {system("cls"); cout<<"***欢迎来到校园十大优秀青年评比系统***"<<endl; charusername[20]; cout<<"1.=============>投票<=============="<<endl<<"2.=============>退出<=============="<<endl; cin>>choice;if(choice==1) {……}elsecout<<"退出成功！";3.2.2用户登录（1）界面设计（2）处理流程设计while(choose!=5)//不是选择5的情况下继续运行，否则退出 { cout<<"****************************\n" <<"校园十大优秀青年评比系统\n" <<"1、提名选手信息\n" <<"2、查询选手得票\n" <<"3、=======>投票\n" <<"4、前十排行榜单\n" <<"5、退出投票系统\n" <<"****************************\n" <<"感谢使用本系统！O(∩_∩)O"<<endl<<"请选择操作："; cin>>choose;if(choose==3)//每次投票后限制次数减一 store[i].root--; switch(choose) { chara[2]; case1: L.display();break; case2: cout<<"请输入选手姓名的拼音(如：zhangjing)："<<endl; cin.getline(a,2); cin.getline(name,20); intf; f=L.hashfind(name,k); if(f)L.showvote(k),cout<<endl; elsecout<<"选手尚未提名！\n"; break; case3: if(store[i].root<=0)//当限制次数使用全部后，3操作不可继续操作 { cout<<"【每人限投3票，您的投票次数已经用完】。"<<endl; break; } else cout<<"请输入选手姓名的拼音(如：zhangjing)："<<endl; cin.getline(a,2); cin.getline(name,20); f=L.hashfind(name,k); if(f){L.vote(name);cout<<"投票成功！剩余投票次数为："<<(store[i].root-1)<<endl;} else { cout<<"无此记录!\n"; cout<<"1、提名该学生\n" <<"2、返回系统界面\n" <<"请选择操作："; intt; cin>>t; if(t==1) { L.inserthash(name); cout<<"选手提名成功\n"; cout<<"剩余投票次数为："<<(store[i].root-1)<<endl; } } break; case4: L.showrank(); break; case5: cout<<"已登出，感谢您的使用!"<<endl; break; default: cout<<"操作无效，请重新选择!\n"; break; }3.2.3（1）界面设计（2）处理流程设计此处利用了类votesystem中定义的函数display；显示哈希表保存的下标对应储存位置中的数据；voidvotesystem::display()//【显示哈希表】{ for(inti=0;i<hashlength;i++) if(st[i].name[0]!='\0') cout<<st[i].studentnum<<'' <<st[i].name<<'' <<st[i].number<<"票"<<'' <<st[i].major <<st[i].grade <<st[i].Class<<"班"<<'' <<st[i].achievement<<'\t' <<endl;}3.2.4查询得票（1）界面设计（2）处理流程设计利用类中定义的函数showvote，表现出选手得票数；得票数储存在用哈希表下表表示位置的student类型的数组中；voidvotesystem::showvote(intk)//【按哈希表下标显示票数】{ cout<<"现得票数："<<st[k].number;}3.2.5投票（1）界面设计（2）处理流程设计投票模块的功能是整个系统中最主要的，其中需要考虑的有进行姓名插入时调用的哈西函数，使其排序更合理；同时调用的collision。用以解决冲突。intvotesystem::Hash(char*name)//【哈希函数】{ char*p=name; intkey=0; while(*p) { key+=int(*p); p++; } returnkey%hashlength;}查找函数用以检验表中是否会产生冲突，并解决；intvotesystem::hashfind(char*name,int&k)//【查找】{ k=Hash(name);//哈希函数定位 while(st[k].name[0]!='\0'&&strcmp(st[k].name,name)) collision(k);//处理冲突 if(!strcmp(st[k].name,name))return1;//【找到】 elsereturn0;}投票函数同时调用了查找，哈西函数；intvotesystem::vote(char*name)//记录已存在时调用hashfind函数【投票】{ ints; intf; f=hashfind(name,s);//定位 if(f){st[s].number++;return1;}//投票成功 elsereturn0;//投票失败}3.2.6前十排行（1）界面设计（2）处理流程设计选择4选项后，调用的类中的showrank函数；利用循环去其前十名，并且其中使用的插入排序法使数据中的票数按降序排列；再输出。voidvotesystem::showrank()//【显示排行榜】{ inta[11];//定义一个数组存放前十名在哈希表中的下标 for(inti=0;i<10;i++)a[i]=-1;for(i=0;i<hashlength;i++)//遍历哈希表 { if(st[i].name[0]!='\0') { for(intk=9;k>=0;k--)//利用插入法进行排序 { if(a[k]>-1) { if(st[a[k]].number<st[i].number) a[k+1]=a[k]; elsebreak; } } a[k+1]=i; } } cout<<"学号"<<'\t'<<"姓名"<<'\t'<<"得票数"<<'\t'<<endl; for(i=0;i<10&&a[i]>-1;i++)//输出前十名 cout<<st[a[i]].studentnum<<'\t' <<st[a[i]].name<<'\t' <<st[a[i]].number<<'\t' <<endl;}3.2.7退出系统（1）界面设计（2）处理流程设计当在用户界面选择5退出后，此时会清除屏幕上的信息同时回到系统界面；等待新的用户使用。当在系统界面登出后，则程序运行结束；4.运行和调试4.1运行和测试通过不同的用户登录，输入下面的数据；测试数据：学号姓名拼音票数班级专业年级突出事迹11113042030luyu12软件二全国大学生广告艺术大赛一等奖1113042039caizhitong12软件二全国大学生街舞大赛一等奖1113042041wangyongxi12软件二全国多媒体课件设计大赛一等奖1113042042sunqianping12网络二全国大学生摄影比赛一等奖1113042045majingchao22计二全国三好学生1113042046xuyang12软外二中国名校大学生辩论赛一等奖1113042047guopeng12网络二中国大学生数学建模竞赛一等奖1113022053Zhangjing42计二全国优秀短篇小说奖1113042049lihong22计二全国物理竞赛一等奖1113042050liuhan22网络二国家一等奖学金1113042051wangjian12软件二全国软件设计大赛一等奖1113042059chenwan12网合二全国大学生创业大赛一等奖对不存在的记录提名，选择“1”，查询选手信息；（3）选择“2”，定位查询选手票数；（4）选择“3”，若选手已经提名；则直接记录；（5）选择“4”查询前十名榜单；（6）选择“5”，退出用户系统时，回到系统界面，同时清除之前信息，等待其他用户登录；4.2调试记录与收获通过一周的课程设计，我再一次复习了数据结构的知识，在设计过程中虽然遇到了不少问题，但经过一次又一次的思考，一点又一点的纠正终于实现了投票系统的基本功能并且完成了系统的功能的添加。我认为，在这学期的课程设计中，不仅培养了独立思考和操作的能力，在各种其它能力上也都有了提高，比如，我们在查找大量资料的过程中渐渐地培养了搜索信息的能力。更重要的是，在设计中，我们学会了很多学习方法。在此次课程设计中，在收获知识的同时，还收获了阅历，收获了成熟。然而，这个程序还有不完善的地方，让我清楚地认识到了自己能力的欠缺。我再次确信要更加努力，更加完善提高编程能力，为将来步入社会奠定基础。源代码：#include<iostream>#include<cstring>#include<iostream.h>#include"stdio.h"#include"windows.h"structstudent{ charname[20];//姓名的拼音intstudentnum;//学号 intnumber;//票数 intClass;//班级 charmajor[30];//专业 chargrade[10];//年级 charachievement[200];//突出事迹};structuser{ charusername[20]; introot; user(){root=4;}};userstore[20];classvotesystem{private: student*st; intcount;//当前元素个数 inthashlength;//哈希表长public: votesystem(){st=NULL;count=0;hashlength=0;} ~votesystem(){delete[]st;count=0;} voidHashTable(intn);//初始化哈希表 intHash(char*name);//哈希函数 voidcollision(int&s){s=s++;}//开放定址线性探测法处理冲突 inthashfind(char*name,int&k);//查找 voidinserthash(char*name);//插入 intvote(char*name);//投票 voiddisplay();//显示哈希表 voidshowvote(intk);//按哈希表下标显示票数 voidshowrank();//显示排行榜};voidvotesystem::HashTable(intn)//【初始化哈希表】{ hashlength=n; st=newstudent[hashlength]; for(inti=0;i<hashlength;i++) st[i].name[0]='\0';}intvotesystem::Hash(char*name)//【哈希函数】{ char*p=name; intkey=0; while(*p) { key+=int(*p); p++; } returnkey%hashlength;}intvotesystem::hashfind(char*name,int&k)//【查找】{ k=Hash(name);//哈希函数定位 while(st[k].name[0]!='\0'&&strcmp(st[k].name,name)) collision(k);//处理冲突 if(!strcmp(st[k].name,name))return1;//【找到】 elsereturn0;}voidvotesystem::inserthash(char*name)//【插入】{ ints;chara[2]; hashfind(name,s); cout<<"提名学生信息格式如下：\n" <<"\t学号:1113022053\n" <<"\t班级：2\n" <<"\t专业：计算机\n" <<"\t年级：二\n"<<"\t突出事迹：好好学习，天天向上！\n"; strcpy(st[s].name,name);cout<<"学号：\t";cin>>st[s].studentnum; cout<<"班级：\t";cin>>st[s].Class; cout<<"专业：\t";cin.getline(a,2);cin.getline(st[s].major,30); cout<<"年级：\t";cin.getline(st[s].grade,10);cout<<"突出事迹：\t";cin.getline(st[s].achievement,200); st[s].number=1;//提名即为投一票 count++;//当前人数加1}intvotesystem::vote(char*name)//记录已存在时调用hashfind函数【投票】{ ints; intf; f=hashfind(name,s);//定位 if(f){st[s].number++;return1;}//投票成功 elsereturn0;//投票失败}voidvotesystem::display()//【显示哈希表】{ for(inti=0;i<hashlength;i++) if(st[i].name[0]!='\0') cout<<st[i].studentnum<<'' <<st[i].name<<'' <<st[i].number<<"票"<<'' <<st[i].major <<st[i].grade <<st[i].Class<<"班"<<'' <<st[i].achievement<<'\t' <<endl;}voidvotesystem::showvote(intk)//【按哈希表下标显示票数】{ cout<<"现得票数："<<st[k].number;}voidvotesystem::showrank()//【显示排行榜】{ inta[11];//定义一个数组存放前十名在哈希表中的下标 for(inti=0;i<10;i++)a[i]=-1;for(i=0;i<hashlength;i++)//遍历哈希表 { if(st[i].name[0]!='\0') { for(intk=9;k>=0;k--)//利用插入法进行排序 { if(a[k]>-1) { if(st[a[k]].number<st[i].number) a[k+1]=a[k]; elsebreak; } } a[k+1]=i; } } cout<<"学号"<<'\t'<<"姓名"<<'\t'<<"得票数"<<'\t'<<endl; for(i=0;i<10&&a[i]>-1;i++)//输出前十名 cout<<st[a[i]].studentnum<<'\t' <<st[a[i]].name<<'\t' <<st[a[i]].number<<'\t' <<endl;}intmain(void)//main函数{ intchoice=-1;intm=0,p=0,i; votesystemL; L.HashTable(50); while(choice!=2) {system("cls");//清除屏幕信息 cout<<"***欢迎来到校园十大优秀青年评比系统***"<<endl; charusername[20]; cout<<"1.=============>投票<=============="<<endl<<"2.=============>退出<=============="<<endl; cin>>choice; if(choice==1) { p++; charb[2]; cout<<"请输入您的名字:"; cin.getline(b,2); cin.getline(username,20); for(i=0;i<p;i++) { if(strcmp(store[i].username,username)==0) break }if(i==p) { strcpy(store[p].username,username); } intchoose=-1,k=-1; charname[20]; while(choose!=5)//不是选择5的情况下继续运行，否则退出 { cout<<"****************************\n" <<"校园十大优秀青年评比系统\n" <<"1、提名选手信息\n" <<"2、查询选手得票\n" <<"3、=======>投票\n" <<"4、前十排行榜单\n" <<"5、退出投票系统\n" <<"****************************\n" <<"感谢使用本系统！O(∩_∩)O"<<endl<<"请选择操作："