数据结构课程设计报告书.doc

数据结构课程设计报告书 课内设计任务一：1. 设计题目：运动会分数统计2.任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些项目取前五名或前三名由学生自己设定。（m=20,n=20）3. 功能要求：1) 可以输入各个项目的前三名或前五名的成绩；2) 能统计各学校总分；3) 可以按学校编号、学校总分、男女团体总分排序输出；4) 可以按学校编号查询学校某个项目的情况；5) 可以按项目编号查询取得前三或前五名的学校。需求分析： 本程序需要建立两个个线性表，一个计运动项目，一个计学校，项目信息中记录了前几名，通过遍历项目表可以统计出每个学校的成绩，统计出成绩记录在学校数组中，最后算出男子，女子和总体的总分，并以此排序。概要设计：typedef struct school char name60; int id; int male_score; int female_score;School, * School_List;typedef struct sport char name60; int id; int category; int winner5;Sport, * Sport_List; School_List scl; Sport_List spl;详细设计：# include#include#include#includetypedef struct school char name60; int id; int male_score; int female_score;School, * School_List;typedef struct sport char name60; int id; /类别（积分类型1:75321；0:532） int category; int winner5;Sport, * Sport_List;/统计每个学校的分数void count_score(int m, int n, int w, School_List scl,Sport_List spl) int i = 0; /初始化分数为0 for(i;in;i+) scli.male_score = 0; scli.female_score = 0; /统计男子项目 for(i=0;im;i+) if(spli.category = 1) sclspli.winner0-1.male_score += 7; sclspli.winner1-1.male_score += 5; sclspli.winner2-1.male_score += 3; sclspli.winner3-1.male_score += 2; sclspli.winner4-1.male_score += 1; else sclspli.winner0-1.male_score += 5; sclspli.winner1-1.male_score += 3; sclspli.winner2-1.male_score += 2; /女子项目 for(i=m;im+w;i+) if(spli.category = 1) sclspli.winner0-1.female_score += 7; sclspli.winner1-1.female_score += 5; sclspli.winner2-1.female_score += 3; sclspli.winner3-1.female_score += 2; sclspli.winner4-1.female_score += 1; else sclspli.winner0-1.female_score += 5; sclspli.winner1-1.female_score += 3; sclspli.winner2-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 20) printf(学校数目（1-20）：); fflush(stdin); scanf(%d,&N); while(M 20) printf(男子项目数（1-20）：); fflush(stdin); scanf(%d,&M); while(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;iN;i+) fflush(stdin); scanf(%s,sh_); sh_li.id = i+1; printf(请依次输入%d个男子项目:n,M); for(i=0;iM;i+) fflush(stdin); scanf(%s,sp_); sp_li.id = i+1; printf(请依次输入%d个女子项目:n,W); for(i=M;iM+W;i+) fflush(stdin); scanf(%s,sp_); sp_li.id = i+1; /初始化项目成绩 printf(请依次输入%d个项目的积分类型与成绩:n,W+M); for(i=0;iM+W;i+) sp_li.category = -1; while(sp_li.category != 1 & sp_li.category != 0) printf(选择%s的积分类型(1.记录前5名;0.记录前3名):,sp_); fflush(stdin); scanf(%d,&sp_li.category); if(sp_li.category = 1) printf(请顺序输入%s的前五名所属学校(1-%d)：,sp_,N); fflush(stdin); scanf(%d%d%d%d%d,&(sp_li.winner0),&(sp_li.winner1),&(sp_li.winner2),&(sp_li.winner3),&(sp_li.winner4); int j = 0; for(j;j N | sp_li.winnerj 1) /不合法输入强制设为1 sp_li.winnerj = 1; else printf(请顺序输入%s的前三名所属学校(1-%d)：,sp_,N); fflush(stdin); scanf(%d%d%d,&(sp_li.winner0),&(sp_li.winner1),&(sp_li.winner2); sp_li.winner3 = sp_li.winner4 = 0; int j = 0; for(j;j *n | sp_li.winnerj 1) /不合法输入强制设为1 sp_li.winnerj = 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,scls_); int i = 0; for(i;im+w;i+) int j = 0; if(spli.category = 1) for(j;j5;j+) if(s_id = spli.winnerj) printf(在%s中获得第%d名！n,,1+j); else for(j;j3;j+) if(s_id = spli.winnerj) printf(在%s中获得第%d名！n,,1+j); /按项目编号查询前几名的学校void getsport_inf(int s_id, School_List scl, Sport_List spl) if(spls_id-1.category = 1) printf(%s的前五名分别为：n,scls_); int j=0; for(j;j5;j+) printf(第%d名：%d%sn,1+j,spls_id-1.winnerj,sclspls_); else printf(%s的前三名分别为：n,scls_); int j=0; for(j;j 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;in;i+) printf(%d:%s总分为%dn,1+i,,scli.male_score+scli.female_score); break; case 2: int *max=new intn; for(i=0;in;i+) maxi = i; /排序，maxi记录第i大的项位置 for(i=0;in-1;i+) int j = 1+i; for(j;jn;j+) if(sclmaxi.male_score + sclmaxi.female_score sclmaxj.male_score + sclmaxj.female_score) maxi = maxj + maxi; maxj = maxi - maxj; maxi = maxi - maxj; /输出 for(i=0;in;i+) printf(%d:%s总分为%dn,1+maxi, , sclmaxi.male_score+sclmaxi.female_score); break; case 3: int *max=new intn; for(i=0;in;i+) maxi = i; /排序，maxi记录第i大的项位置 for(i=0;in-1;i+) int j = 1+i; for(j;jn;j+) if(sclmaxi.male_score sclmaxj.male_score) maxi = maxj + maxi; maxj = maxi - maxj; maxi = maxi - maxj; /输出 for(i=0;in;i+) printf(%d:%s男子项目总分为%dn,1+maxi, , sclmaxi.male_score); break; case 4: int *max=new intn; for(i=0;in;i+) maxi = i; /排序，maxi记录第i大的项位置 for(i=0;in-1;i+) int j = 1+i; for(j;jn;j+) if(sclmaxi.female_score sclmaxj.female_score) maxi = maxj + maxi; maxj = maxi - maxj; maxi = maxi - maxj; /输出 for(i=0;i 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 | 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%132.需求分析：1. 用户可以根据自己的需求输入一个顺序表（哈希表）2. 通过用除留余数法构造哈希函数，并用开放地址的二次探测再散列解决冲突。3. 在经过排序后显示该哈希表。4. 程序执行的命令包括：创建哈希表 输出哈希表 二次探测再散列解决冲突3.概要设计： #include #include #include #include #include #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 tableTableSize; int currentSize; HashTable;Status Initiate(HashTable *h) int i; for(i=0; iTableSize; i+) (*h).tablei.tag=0; (*h).tablei.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.tablej.tag=1 & h.tablej.elem.key!=x.key) j=(j+1)%TableSize; if(j=i) cout哈希表中未查找到x.keyendl;return TableSize; if(h.tablej.tag=1) cout该元素在哈希表的第j位endl; return -j; else cout哈希表中未查找到x.keyendl; return j; Status Insert(HashTable *h, Elemtype x, int p) int i=SearchHash(*h, x, p); if(i0) coutx.key元素已存在,无法再录入,操作失败！endlendl; return UNSUCCESS; else if(i!=TableSize & (*h).tablei.tag!=1) (*h).tablei.elem.key=x.key; (*h).tablei.tag=1; (*h).currentSize+; cout录入成功！endlendl; return SUCCESS; else if(i=TableSize) cout哈希表已满,无法再插入x.key，操作失败！endlendl; return UNSUCCESS; Statu