数据结构 第9章 校园十大 实验报告

数据结构

实验报告 第九章

实验名称：校园十大优秀青年评比 实验类型：综合性实验 班级： 学号： 姓名：

实验日期：2014年6月28日

1.问题描述

新一届校园十大优秀青年评比开始了！每一位在校学生可通过网上评比系统，为自己认为优秀的学生提名与投票。请开发一个可用于该需求的系统，满足下列基本功能。

? 提名优秀学生和投票。

? 查看提名学生的基本信息。 ? 显示各提名学生的票数。 ? 显示排行榜

设计要求

? 采用散列存储，存放提名学生的相关信息。 ? 设计哈希函数和冲突解决方法。

? 提名学生至少包括以下信息：姓名、票数、个人基本信息（如班级、专

业、年级、突出事迹等）。

? 设计输入提名学生信息的界面。 ? 设计足够多的测试用例。 ? 查看指定学生的票数。 ? 按序显示各提名学生票数

2.数据结构设计

因为一个学生结点要包含很多信息，所以使用结构体把学生的信息汇总在一起。

struct student {

char name[20];//姓名 int studentnum;//学号 int number;//票数 int Class;//班级

char major[30];//专业 char grade[10];//年级

char achievement[200];//事迹 };

3.算法设计

整个程序要包括学生信息的输入，投票，排序，显示。

其中程序要求使用哈希表，我们这里使用的哈希函数是根据姓名拼音的ASCII码来设计，例：h(key)=key%HashLength，其中k为姓名所有拼音的ASCII码值的累加和，HashLength为表长。冲突解决办法是线性探测法。

排序使用的是插入排序法，关键程序具体如下 学生信息输入：

void votesystem::inserthash(char*name)//插入 { int s; char a[2]; hashfind(name,s); cout<<\输入学生信息：\\n\ strcpy(st[s].name,name); cout<<\学号：\ cout<<\班级：\ cout<<\专业：\ cout<<\年级：\ cout<<\事迹：\ st[s].number=1;//提名即为投一票 count++;//当前人数加1 }

哈希函数：

int votesystem::Hash(char*name)//哈希函数 进行转换 { char*p=name; int key=0; while(*p) { key+=int(*p); p++; } return key%hashlength; }

处理冲突：

int votesystem::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))return 1;//找到 else return 0; }

显示所有信息：

void votesystem::display()//显示哈希表 { for(int i=0;i

显示指定选手票数：

void votesystem::showvote(int k)//按哈希表下标显示票数 { cout<<\现得票数：\}

显示前十名：

void votesystem::showrank()//显示排行榜 { int a[11];//定义一个数组存放前十名在哈希表中的下标 for(int i=0;i<10;i++)a[i]=-1; for(int i=0;i=0;k--)//利用插入法进行排序 { if(a[k]>-1) { if(st[a[k]].number

} }

}

a[k+1]=i;

cout<<\学号\姓名\得票数\for(int i=0;i<10&&a[i]>-1;i++)//输出前十名 cout<

4.运行、测试与分析 1）程序运行，开始投票

2）给11个人投票后，显示选手信息（略去中间投票过程）

3）给p选手累计投票

4）显示p选手票数

5）显示前10名选手

6）退出

5.实验收获及思考 遇到的问题：

1.无法编译。

2.局部测试时，结果不对。

3.运行时程序出现未知错误，程序无法正常运行。

解决办法：

1.大多是变量书写错误或者忘记定义变量，检查后修改就解决了。

2.按照算法核对代码，并按照例子，一步步脑子里运算，对比结果，检查出错

误之处并改正。

3.一步步检查发现是指针不对导致程序问题发生。

实验的收获：

通过亲自使用构造哈希函数、解决冲突的办法，更深刻的记忆了有关知识， 也做出一个小的投票系统，使用了结构体和类，进一步增强了其使用熟练程度，同时在指针使用方面也有了一定的认识和提高，进一步减少了程序中出现的错误。通过实验不仅培养了独立思考和操作的能力，在各种其它能力上也都有了提高，比如，我们在查找大量资料的过程中渐渐地培养了搜索信息的能力。更重要的是，在设计中，我们学会了很多学习方法。这个程序还有不完善的地方，让我清楚地认识到了自己能力的欠缺。我还需要继续努力学习。 附录：

#include #include #include\#include%using namespace std; struct student {

char name[20];//姓名 int studentnum;//学号 int number;//票数 int Class;//班级

char major[30];//专业 char grade[10];//年级

char achievement[200];//事迹 };

class votesystem {

private:

student *st;

int count;//当前元素个数 int hashlength;//哈希表长 public:

votesystem(){st=NULL;count=0;hashlength=0;} //构造函数 ~votesystem(){delete[]st;count=0;} //析构函数 void HashTable(int n);//初始化哈希表 int Hash(char*name);//哈希函数

void collision(int&s){s=s++;}//开放定址线性探测法处理冲突 int hashfind(char*name,int&k);//查找

void inserthash(char*name);//插入 int vote(char*name);//投票 void display();//显示哈希表

void showvote(int k);//按哈希表下标显示票数 void showrank();//显示排行榜 };

void votesystem::HashTable(int n)//初始化哈希表 {

hashlength=n;

st=new student[hashlength]; for(int i=0;i

int votesystem::Hash(char*name)//哈希函数 进行转换 {

char*p=name; int key=0; while(*p) {

key+=int(*p); p++; }

return key%hashlength; }

int votesystem::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))return 1;//找到 else return 0; }

void votesystem::inserthash(char*name)//插入 {

int s; char a[2];

hashfind(name,s);

cout<<\输入学生信息：\\n\ strcpy(st[s].name,name);

cout<<\学号：\

cout<<\班级：\

cout<<\专业：\ cout<<\年级：\

cout<<\事迹：\ st[s].number=1;//提名即为投一票 count++;//当前人数加1 } int votesystem::vote(char*name)//记录已存在时调用hashfind函数投票 {

int s; int f;

f=hashfind(name,s);//定位

if(f){st[s].number++;return 1;}//投票成功 else return 0;//投票失败 }

void votesystem::display()//显示哈希表 {

for(int i=0;i

cout<<\学号：\ <<\姓名：\

<<\票数：\票\ <<\专业：\ <<\年级：\

<<\班级: \班\ <<\事迹：\ <

void votesystem::showvote(int k)//按哈希表下标显示票数 {

cout<<\现得票数：\}

void votesystem::showrank()//显示排行榜 {

int a[11];//定义一个数组存放前十名在哈希表中的下标 for(int i=0;i<10;i++)a[i]=-1;

for(int i=0;i

if(st[i].name[0]!='\\0') { int k=9;

for(;k>=0;k--)//利用插入法进行排序 {

if(a[k]>-1) {

if(st[a[k]].number

a[k+1]=i; } }

cout<<\学号\姓名\得票数\ for(int i=0;i<10&&a[i]>-1;i++)//输出前十名 cout<

int main(void) {

int choice=-1;int m=0,p=0,i; votesystem L; L.HashTable(50); int choose=-1,k=-1; char name[20];

while(choose!=5)//不是选择5的情况下继续运行，否则退出 {

cout<

<<\、提名选手信息\\n\ <<\、查询选手得票\\n\ <<\、给选手投票\\n\ <<\、前十排行榜单\\n\ <<\、退出投票系统\\n\ <>choose; switch(choose) {

char a[2]; case 1:

L.display();break; case 2:

cout<<\请输入选手姓名：\ cin.getline(a,2); cin.getline(name,20); int f;

f=L.hashfind(name,k);

if(f)L.showvote(k),cout<

cout<<\请输入选手姓名：\ cin.getline(a,2); cin.getline(name,20); f=L.hashfind(name,k);

if(f){L.vote(name);cout<<\投票成功！\ else {

L.inserthash(name); cout<<\投票成功！\\n\ }

break; case 4:

L.showrank(); break; case 5:

cout<<\已退出，谢谢使用。\ break; default:

cout<<\输入错误，请重新选择!\\n\ break; }

}//end while return 0; }

本文来源：https://www.bwwdw.com/article/l2eo.html