数据结构专业课程设计方案报告书.doc

数据结构课程设计汇报书

课内设计任务一：

1. 设计题目：运动会分数统计

2.任务：参与运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1～m，女子m+1～m+w。不一样项目取前五名或前三名积分；取前五名积分分别为：7、5、3、2、1，前三名积分分别为：5、3、2；哪些项目取前五名或前三名由学生自己设定。（m<=20,n<=20）

3. 功效要求：
1) 能够输入各个项目标前三名或前五名成绩；
2) 能统计各学校总分；
3) 能够按学校编号、学校总分、男女团体总分排序输出；
4) 能够按学校编号查询学校某个项目标情况；
5) 能够按项目编号查询取得前三或前五名学校。

需求分析：
本程序需要建立两个个线性表，一个计运动项目，一个计学校，项目信息中统计了前几名，经过遍历项目表能够统计出每个学校成绩，统计出成绩统计在学校数组中，最终算出男子，女子和总体总分，并以此排序。

概要设计：
typedef struct school
{
char name[60];
int id;
int male_score;
int female_score;
}School, * School_List;
typedef struct sport
{
char name[60];
int id;
int category;
int winner[5];
}Sport, * Sport_List;

School_List scl;
Sport_List spl;

具体设计：
# include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
typedef struct school
{
char name[60];
int id;
int male_score;
int female_score;
}School, * School_List;

typedef struct sport
{
char name[60];
int id;
//类别（积分类型1:75321；0:532）
int category;
int winner[5];
}Sport, * Sport_List;

//统计每个学校分数
void count_score(int m, int n, int w, School_List scl,Sport_List spl)
{
int i = 0;
//初始化分数为0
for(i;i<n;i++)
{
scl[i].male_score = 0;
scl[i].female_score = 0;
}
//统计男子项目
for(i=0;i<m;i++)
{
if(spl[i].category == 1)
{
scl[spl[i].winner[0]-1].male_score += 7;
scl[spl[i].winner[1]-1].male_score += 5;
scl[spl[i].winner[2]-1].male_score += 3;
scl[spl[i].winner[3]-1].male_score += 2;
scl[spl[i].winner[4]-1].male_score += 1;
}
else
{
scl[spl[i].winner[0]-1].male_score += 5;
scl[spl[i].winner[1]-1].male_score += 3;
scl[spl[i].winner[2]-1].male_score += 2;
}
}
//女子项目
for(i=m;i<m+w;i++)
{
if(spl[i].category == 1)
{
scl[spl[i].winner[0]-1].female_score += 7;
scl[spl[i].winner[1]-1].female_score += 5;
scl[spl[i].winner[2]-1].female_score += 3;
scl[spl[i].winner[3]-1].female_score += 2;
scl[spl[i].winner[4]-1].female_score += 1;
}
else
{
scl[spl[i].winner[0]-1].female_score += 5;
scl[spl[i].winner[1]-1].female_score += 3;
scl[spl[i].winner[2]-1].female_score += 2;
}
}
}
//初始化全部数据
void init(int *m, int *n, int *w,School_List *scl,Sport_List *spl)
{
*m = *n = *w = 0;
//初始化数量
int M,N,W;
M = N = W = 0;
printf("课题1：运动会分数统计") ;
printf("请分别输入学校数目，男子项目和女子项目数：\n");
while(N < 1 || N >20)
{
printf("学校数目（1-20）：");
fflush(stdin);
scanf("%d",&N);
}
while(M < 1 || M >20)
{
printf("男子项目数（1-20）：");
fflush(stdin);
scanf("%d",&M);
}
while(W < 1 || W >20)
{
printf("女子项目数（1-20）：");
fflush(stdin);
scanf("%d",&W);
}
*m = M;
*n = N;
*w = W;
//分配空间
*scl = (School*)malloc(N * sizeof(School));
*spl = (Sport*)malloc((M+W) * sizeof(Sport));
//初始化项目学校基础信息
School_List sh_l = *scl;
Sport_List sp_l = *spl;
int i = 0;
printf("请依次输入%d个学校名称:\n",N);
for(i;i<N;i++)
{
fflush(stdin);
scanf("%s",sh_l[i].name);
sh_l[i].id = i+1;
}
printf("请依次输入%d个男子项目:\n",M);
for(i=0;i<M;i++)
{
fflush(stdin);
scanf("%s",sp_l[i].name);
sp_l[i].id = i+1;
}
printf("请依次输入%d个女子项目:\n",W);
for(i=M;i<M+W;i++)
{
fflush(stdin);
scanf("%s",sp_l[i].name);
sp_l[i].id = i+1;
}
//初始化项目成绩
printf("请依次输入%d个项目标积分类型和成绩:\n",W+M);
for(i=0;i<M+W;i++)
{
sp_l[i].category = -1;
while(sp_l[i].category != 1 && sp_l[i].category != 0)
{
printf("选择%s积分类型(1.统计前5名;0.统计前3名):",sp_l[i].name);
fflush(stdin);
scanf("%d",&sp_l[i].category);
}
if(sp_l[i].category == 1)
{
printf("请次序输入%s前五名所属学校(1-%d)：",sp_l[i].name,N);
fflush(stdin);
scanf("%d%d%d%d%d",&(sp_l[i].winner[0]),&(sp_l[i].winner[1]),&(sp_l[i].winner[2]),&(sp_l[i].winner[3]),&(sp_l[i].winner[4]));
int j = 0;
for(j;j<5;j++)
{
if(sp_l[i].winner[j] > N || sp_l[i].winner[j] < 1)
{
//不正当输入强制设为1
sp_l[i].winner[j] = 1;
}
}
}
else
{
printf("请次序输入%s前三名所属学校(1-%d)：",sp_l[i].name,N);
fflush(stdin);
scanf("%d%d%d",&(sp_l[i].winner[0]),&(sp_l[i].winner[1]),&(sp_l[i].winner[2]));
sp_l[i].winner[3] = sp_l[i].winner[4] = 0;
int j = 0;
for(j;j<3;j++)
{
if(sp_l[i].winner[j] > *n || sp_l[i].winner[j] < 1)
{
//不正当输入强制设为1
sp_l[i].winner[j] = 1;
}
}
}
}
count_score(M,N,W,sh_l,sp_l);
}
//按学校编号查询全部项目标成绩
void getshool_mark(int s_id, int m, int w, School_List scl, Sport_List spl)
{
printf("学校%s在此次运动会成绩：\n",scl[s_id-1].name);
int i = 0;
for(i;i<m+w;i++)
{
int j = 0;
if(spl[i].category == 1)
{

for(j;j<5;j++)
{
if(s_id == spl[i].winner[j])
{
printf("在%s中取得第%d名！\n",spl[i].name,1+j);
}
}
}
else
{
for(j;j<3;j++)
{
if(s_id == spl[i].winner[j])
{
printf("在%s中取得第%d名！\n",spl[i].name,1+j);
}
}
}
}
}
//按项目编号查询前几名学校
void getsport_inf(int s_id, School_List scl, Sport_List spl)
{
if(spl[s_id-1].category == 1)
{
printf("%s前五名分别为：\n",scl[s_id-1].name);
int j=0;
for(j;j<5;j++)
{
printf("第%d名：%d%s\n",1+j,spl[s_id-1].winner[j],scl[spl[s_id-1].winner[j]-1].name);
}
}
else
{
printf("%s前三名分别为：\n,",scl[s_id-1].name);
int j=0;
for(j;j<3;j++)
{
printf("第%d名：%d%s\n",1+j,spl[s_id-1].winner[j],scl[spl[s_id-1].winner[j]-1].name);
}
}
}
//全部学校按某种次序输出
void printschool(int n, School_List scl)
{

int choose = -1;
while(choose > 5 || choose < 0)
{
printf("0.返回\n");
printf("1.按学校编号输出\n");
printf("2.按成绩排名输出\n");
printf("3.按男子成绩输出\n");
printf("4.按女子成绩输出\n");
fflush(stdin);
scanf("%d",&choose);
}
int i = 0;
switch(choose)
{
case 0:
return;
case 1:
{
for(i=0;i<n;i++)
{
printf("%d:%s总分为%d\n",1+i,scl[i].name,scl[i].male_score+scl[i].female_score);
}
break;
}
case 2:
{
int *max=new int[n];
for(i=0;i<n;i++)
{
max[i] = i;
}
//排序，max[i]统计第i大项位置
for(i=0;i<n-1;i++)
{
int j = 1+i;
for(j;j<n;j++)
if(scl[max[i]].male_score + scl[max[i]].female_score < scl[max[j]].male_score + scl[max[j]].female_score)
{
max[i] = max[j] + max[i];
max[j] = max[i] - max[j];
max[i] = max[i] - max[j];
}
}
//输出
for(i=0;i<n;i++)
{
printf("%d:%s总分为%d\n",1+max[i], scl[max[i]].name, scl[max[i]].male_score+scl[max[i]].female_score);
}
break;
}
case 3:
{
int *max=new int[n];
for(i=0;i<n;i++)
{
max[i] = i;
}
//排序，max[i]统计第i大项位置
for(i=0;i<n-1;i++)
{
int j = 1+i;
for(j;j<n;j++)
if(scl[max[i]].male_score < scl[max[j]].male_score)
{
max[i] = max[j] + max[i];
max[j] = max[i] - max[j];
max[i] = max[i] - max[j];
}
}
//输出
for(i=0;i<n;i++)
{
printf("%d:%s男子项目总分为%d\n",1+max[i], scl[max[i]].name, scl[max[i]].male_score);
}
break;
}
case 4:
{
int *max=new int[n];
for(i=0;i<n;i++)
{
max[i] = i;
}
//排序，max[i]统计第i大项位置
for(i=0;i<n-1;i++)
{
int j = 1+i;
for(j;j<n;j++)
if(scl[max[i]].female_score < scl[max[j]].female_score)
{
max[i] = max[j] + max[i];
max[j] = max[i] - max[j];
max[i] = max[i] - max[j];
}
}
//输出
for(i=0;i<n;i++)
{
printf("%d:%s女子项目总分为%d\n",1+max[i], scl[max[i]].name, scl[max[i]].female_score);
}
break;
}
}

}
int main()
{
int m,n,w;
School_List scl;
Sport_List spl;
init(&m,&n,&w,&scl,&spl);
int choose = -1;
while(choose != 0)
{
printf("0.退出\n");
printf("1.按次序输出学校信息\n");
printf("2.查询学校在各项目标成绩\n");
printf("3.打印全部项目\n");
printf("4.查询项目标前几名\n\n");
fflush(stdin);
scanf("%d",&choose);
switch(choose)
{
case 0:
return 0;
case 1:
{
printschool(n,scl);
break;
}
case 2:
{
int sid = 0;
while(sid > n || sid < 1)
{
printf("请输入需查询学校编号(1-%d)：\n",n);
scanf("%d",&sid);
}
getshool_mark(sid, m, w, scl, spl);
break;
}
case 3:
{
int i = 0;
for(i;i<m+w;i++)
{
printf("%d:%s\n",spl[i].id,spl[i].name);
}
break;
}
case 4:
{
int sid = 0;
while(sid > m+w || sid < 1)
{
printf("请输入需查询项目编号(1-%d)：\n",m+w);
fflush(stdin);
scanf("%d",&sid);
}
getsport_inf(sid, scl, spl);
break;
}
}

}
return 0;
}

调试分析：
a）因为\n忘记添加造成界面混乱。
b）有值在循环时，程序自动判定有时不正当，所以需要循环前进行判定。或强制讲不正当内容默认为1.
c.) max没有要求

用户手册：
演示程序运行环境为 Windows8系统，C-free 5 中C-free5.0中运行。实施文件为：sports_meet.exe
（1） 进入演示程序后即显示 DOS 形式界面：
（2） 输入各个项目和名次，系统计算排名。
（3） 接收其它命令后即实施对应运算和显示对应结果。

测试结果：

课内设计任务二：
1.哈希表查找设计
问题描述：
设哈希表长为20，用除留余数法结构一个哈希函数，以开放定址法中线性探测再散列法作为处理冲突方法，编程实现哈希表查找、插入和建立算法。
测试数据
关键字组为｛19,01,23,14,55,20,84,27,68,11,10,77｝，哈希函数为H(key)=key%13

2.需求分析：
1. 用户能够依据自己需求输入一个次序表（哈希表）
2. 经过用除留余数法结构哈希函数，并用开放地址二次探测再散列处理冲突。
3. 在经过排序后显示该哈希表。
4. 程序实施命令包含：
创建哈希表 输出哈希表 二次探测再散列处理冲突

3.概要设计：
#include<malloc.h>
#include<iostream.h>
#include<iomanip.h>
#include<process.h>
#include<ctype.h>
#define TableSize 20
#define SUCCESS 1
#define UNSUCCESS 0
typedef int Status;
typedef struct
{
int key;
}Elemtype;

typedef struct
{
Elemtype elem;
int tag;
}HashItem;
typedef struct
{
HashItem table[TableSize];
int currentSize;
}HashTable;
Status Initiate(HashTable *h)
{
int i;
for(i=0; i<TableSize; i++)
{
(*h).table[i].tag=0;
(*h).table[i].elem.key=NULL;
}
(*h).currentSize=0;
return SUCCESS;
}
int SearchHash(HashTable h, Elemtype x, int p)
{
int i=x.key%p;
int j=i;
while(h.table[j].tag==1 && h.table[j].elem.key!=x.key)
{
j=(j+1)%TableSize;
if(j==i)
{
cout<<"哈希表中未查找到"<<x.key<<endl;
return TableSize;
}
}
if(h.table[j].tag==1)
{cout<<"该元素在哈希表第"<<j<<"位"<<endl; return -j;}
else
{cout<<"哈希表中未查找到"<<x.key<<endl; return j;}
}
Status Insert(HashTable *h, Elemtype x, int p)
{
int i=SearchHash(*h, x, p);
if(i<0)
{cout<<x.key<<"元素已存在,无法再录入,操作失败！"<<endl<<endl;
return UNSUCCESS;}
else
{
if(i!=TableSize && (*h).table[i].tag!=1)
{
(*h).table[i].elem.key=x.key;
(*h).table[i].tag=1;
(*h).currentSize++;
cout<<"录入成功！"<<endl<<endl;
return SUCCESS;
}
else
if(i==TableSize)
{cout<<"哈希表已满,无法再插入"<<x.key<<"，操作失败！"<<endl<<endl;
return UNSUCCESS;}
}
}
Status Print(HashTable h)
{
cout<<endl<<"哈希表序数 存放情况 存放元素"<<endl;
for(int i=0;i<TableSize;i++)
{cout<<setw(4)<<i<<setw(10)<<h.table[i].tag<<setw(10)<<h.table[i].elem.key<<endl;}
cout<<endl<<"表中非空元素个数："<<h.currentSize<<endl<<endl;
return SUCCESS;
}
int main( )
{
cout<<endl<<"******** 哈希表设计********"<<endl<<endl;
HashTable h;
Initiate(&h);
int prime;
cout<<"请输入除数：";
cin>>prime;
char choice;
while(1)
{
cout<<"————————————————————————"<<endl;
cout<<"按 a 输出哈希表"<<endl;
cout<<"按 b 查找指定元素在表中位置"<<endl;
cout<<"按 c输入，插入元素"<<endl;
cout<<"按 其它键 退出"<<endl<<endl<<"请选择：";
cin>>choice;
cout<<"————————————————————————"<<endl;
switch(choice)
{
case'a':
{ Print(h); break;}
case'b':
{ cout<<"请输入需要查找元素值：";
Elemtype a;
cin>>a.key;
SearchHash(h,a,prime);
break;}
case'c':
{ cout<<"请输入需要输入元素个数(1~20)：";
int n,i;
cin>>n;
Elemtype *pi=0;
pi=(Elemtype*)malloc(n*sizeof(Elemtype));
cout<<"请依次输入"<<n<<"个元素值："<<endl;
for(i=0;i<n;i++)
{ cin>>pi[i].key; Insert(&h,pi[i],prime);}
break;}
default:
{return 0;}
}
}
}

用户手册：演示程序运行环境为 Windows8系统，C-free 5 中C-free5.0中运行
（4） 进入演示程序后即显示 DOS 形式界面：
（5） 输入除数.
（6） 接收其它命令后即实施对应运算和显示对应结果。

测试结果：