实验报告 实验课名称：数据结构实验 实验名称：校园十大优秀青年评比 班级：20130613 学号：16 姓名：施洋 时间：2015-5-25
一、问题描述 新一届校园十大青年评比开始了！每一位在校学生可通过网上评比系统，为自己认为优秀的学生提名与投票。请开发一个用于该需求的系统，满足下列基本功能：
(1)提名优秀学生与投票。
(2)查看提名学生的基本信息。
(3)显示各提名学生的票数。
(4)显示排行榜。
基本要求：
(1)采用散列存储，存放提名学生的相关信息。
(2)设计哈希函数和冲突解决方法。
(3)提名学生至少包括以下信息：姓名、票数、个人基本信息（如：班级、专业、年级、突出事迹等）。
(4)设计输入提名学生信息的界面。
(5)完成基本功能。
(6)界面友好，操作简单。
(7)设计足够多的测试用例。
(8)查看指定学生的票数。
二、数据结构设计 1）用哈希表存储提名学生相关信息。
每位选手即学生的基本信息含有多个属性，为此可根据学生信息建立结构体，如下：
struct student{ char name[40];//姓名的拼音+学号 int number;//票数 int Class;//班级 char Major[50];//专业 char Grade[10];//年级 char Honour[100];//突出事迹 };
（2）设计哈希函数，并用开放定址线性探测法处理冲突。
（3）设计一个投票系统类：votesystem class votesystem{ private:
student *stu;
int count;//当前元素个数
int sizeindex;//哈希表长 public:
votesystem() {stu=NULL;count=0;sizeindex=0;}
~votesystem() {delete []stu;count=0;}
void InitHashTable(int n);//初始化哈希表
int Hash(char *name);//哈希函数
void collision(int &s){s=s++;}//开放定址线性探测法处理冲突
int search(char *name,int&k);//查找
void insert(char*name);//插入
int vote(char*name);//投票
void display();//显示哈希表
void showvote(int k); //按哈希表下标显示票数
void showrank();//显示排行榜 }; 三、算法设计 votesystem 成员函数详细设计：
（1）哈希函数 Hash 根据实现要点提示设计哈希函数 int votesystem::Hash(char *name)//哈希函数 {
char *p=name;
int key=0;
while(*p)
{
key+=int(*p);
p++;
}
return key%sizeindex; }
（2）查找函数 search
Step1：对指定的选手调用哈希函数求值
Step2：用开放定址线性探测法处理冲突，在哈希表中查找 k=Hash(name);//哈希函数定位 while(stu[k].name[0]!="\0"&&strcmp(stu[k].name,name))
collision(k);//处理冲突
Step3：若找到返回 1；否则返回 0 if(!strcmp(stu[k].name,name)) return 1;//找到
else return 0;
（3）插入函数 insert
Step1：调用查找函数 search，找到插入信息的位置
Step2：按照提名学生信息示例格式输入学生的信息 void votesystem::insert(char *name) { int s;char a[2]; search(name,s); cout<<"提名学生信息格式如下：\n"
<<"\t 班级：2\n"
<<"\t 专业：软件工程\n"
<<"\t 年级：二\n"
<<"\t 突出事迹：全国三好学生\n"; strcpy(stu[s].name,name); cout<<"班级：\t";cin>>stu[s].Class; cout<<"专业：\t";cin.getline(a,2);cin.getline(stu[s].Major,50); cout<<"年级：\t";cin.getline(stu[s].Grade,10); cout<<"突出事迹：\t";cin.getline(stu[s].Honour,100);
Step3：提名即为投一票，同时当前元素个数加 1
stu[s].number=1;//提名即为投一票
count++;//当前人数加 1 }
（4）投票函数 vote Step1：
记录已存在时调用 search 函数 int votesystem::vote(char*name)
{
int s;
int f;
f=search(name,s);//定位
if(f) {stu[s].number++;return 1;}//投票成功
else return 0;//投票失败 } Step2：
记录不存在时，转到提名或返回
cout<<"无此记录!\n";
cout<<"
1、提名该学生\n"
<<"
2、返回\n"
<<"请选择操作：";
int t;
cin>>t;
if(t==1)
{
L.insert(name);
cout<<"提名成功\n";
} （5）
显示哈希表函数 display
从表头开始，若表中记录已存在，则输出该学生的基本信息：姓名，票数，专业，年级，班级，突出事迹；否则转到下一个。
void votesystem::display() {
for(int i=0;i<sizeindex;i++)
if(stu[i].name[0]!="\0")
cout<<stu[i].name<<" "
<<stu[i].number<<"票"<<" "
<<stu[i].Major<<" "
<<stu[i].Grade
<<stu[i].Class<<"班"<<" "
<<stu[i].Honour<<"\t"
<<endl; }
(6)显示排行榜函数 showrank
Step1：定义一个数组 a[11]，存储前十名在哈希表中的下标，并初始化数组
Step2：从哈希表表头开始依次访问，记录存在时即转到 Step3
Step3：利用 插入法对进行记录进行排序
Step4：将哈希表下标保存到数组 a 中 int a[11];//定义一个数组存放前十名在哈希表中的下标
for(int i=0;i<10;i++) a[i]=-1;
for( i=0;i<sizeindex;i++)//遍历哈希表
{
if(stu[i].name[0]!="\0")
{
for(int k=9;k>=0;k--)//利用插入法进行排序
{
if(a[k]>-1)
{
if(stu[a[k]].number<stu[i].number)
a[k+1]=a[k];
else break;
}
}
a[k+1]=i;
}
} Step5：根据数组 a 中排序结果，顺序输出前十名选手的姓名，票数 for(i=0;i<10&&a[i]>-1;i++)//对前十名输出
cout<<stu[a[i]].name<<"\t"
<<stu[a[i]].number
<<endl;
四、界面设计 ***************
1、选手信息
2、选手得票数
3、投票
4、排行榜
5、退出系统
***************
五、 运行测试与分析 （1）对记录不存在的学生进行投票，即提名过程
依此模式对记录不存在的学生进行提名，具体信息如图（3）所示
（2）对记录已存在的选手进行投票
（3）显示选手信息
（4）显示排行榜
（5）显示指定选手得票数
（6）显示记录不存在选手的得票数
（7）选择无效操作
六、实验收获与思考 通过此次课程设计，我又一次复习了数据结构的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一点又一点的纠正终于实现了投票系统的基本功能,对哈希函数有了更深入的学习与运用。
教师评分：
教师签字：
相关热词搜索： 十大 评比 优秀青年