数据结构课程设计(奥运会奖牌管理程序).doc

哈尔滨工业大学（威海）数据结构课程设计报告1. 选题背景与意义背景： 奥运会历来是一场国际性质的全球体育盛会，2008北京奥运俨然已经成为中国的骄傲，中国运动健儿历来在奥运会上有突出的运动成绩，为国家带来很多荣誉。08奥运已经远去，12伦敦将要来临，届时，奥运会将会又成为全球人瞩目的焦点。主办国毫无例外将成为主角，它也成为显示综合国力的舞台。虽然外人在看那一幕幕的精彩冲刺，那些漂亮的烟花和惊喜的圣火点燃，但是奥运管理者却要为大赛的任何情况，任何时刻做好相应的准备。其中，奥运的金牌、奖牌管理必将是重中之重，在开赛之前其有关程序必须准确无误的运行，才能保证奥运畅通无阻的进行。在这种很受欢迎的情况下，我们选择编写跟奥运有关的奖牌管理程序，必将受到有关管理者的欢迎，虽然我们不是专业的编程人员，但是可以为他们提供一些参考。意义： 编写与奖牌管理有关的程序后，管理者不用再为某一次的运动员获奖或者某一个国家的获奖而分散注意力，只需要在特定时刻、特定的项目、特定的运动员获奖时，将信息输入电脑中，此时计算机已经将数据记录，从而避免了靠人来记忆的局限性，保证了结果的准确，也是一种公平的体现。当然，编写完的程序会有很强大的功能，比如，当一个项目的决赛比完以后，需要进行颁奖典礼，此时只需要在电脑中输入此项目，立刻便有相应的获奖运动员及信息输出，再将此信息传送到后勤处，颁奖典礼便能顺利进行。另外，在每一天的比赛完成或者每一场比赛完成，都会有奖牌榜、金牌榜的更新，此时，此程序便起了很大作用，不需要刻意编写，系统会在存储完成后自动的生成奖牌榜和金牌榜。这只是列举了此程序的部分作用，具体的很多实用性的价值会在程序中体现。需求分析1.目的要求： 要实现快速的存储，方便的查找，精确地排序过程。2.具体过程：（1）存储操作。存储奖牌有关的信息，此时要存储国家、金牌数、奖牌数。 （2）排序操作。对存储的金牌数和奖牌数运用两种不同的排序方式，分别把它们排序后输出，也就是金牌榜和奖牌榜。 （3）查找操作。按照输入的国家，可以运用一种查找方式找到对应国家的金牌数、奖牌数以及在榜单上的排名；按照输入的金牌数可以按照另一种查找方式找到对应的国家以及此国家的奖牌数；按照一种查找方式根据奖牌数找到对应的国家以及此国家的金牌数。（1）存储操作。与上不同，此部分存储获得金牌的运动员、获奖时间、项目和国籍。（2）查找操作。输入获得金牌运动员的名字，能查找到他的国籍，所参加的项目以及获奖时间；输入国家，所有获得金牌的运动员及其获奖时间和所参加的项目全部可以输出；输入时间，当天的获得金牌的运动员及其国籍和所参加的运动项目均可以输出；输入运动项目，所有在该项上获得金牌的运动员及其国籍和获奖时间均可以找到。3.分析结果：此程序能准确无误的实现以上操作，所以实用性很高，它不仅可以应用到奥运会，在大小型的运动会等都可以用的到，而且方便快捷，是很多大赛组织者希望看到和采用的，可以带来方便。 概要设计国家金牌（顺序查找）金牌国家（二分查找）奖牌国家（顺序查找）金牌运动员、国籍、获奖时间、项目之间相互查找（多种方式）运动员、国籍、项目、获奖时间国家、金牌数、奖牌数查找操作金牌榜（直接插入排序）奖牌榜（折半插入排序） 排序过程存储结构输入数据详细设计#include#include#include#define OK 1#define ERROR 0 #define OVERFLOW -2#define EQ(a,b) (a)=(b)#define LT(a,b) (a)next=NULL; printf(1).存储(国家、金牌数、奖牌数)nn); printf(请输入要存储的国家个数nn); scanf(%d,&n); printf(请依次输入%d个国家的名字n,n); for(i=0;idata1.countryi); printf(请依次输入%d个国家的金牌数n,n); for(i=0;idata1.goldeni); Mi+1=L1-data1.goldeni; printf(请依次输入%d个国家的奖牌数n,n); for(i=0;in;i+) /*用一个循环,依次存储奖牌数,同时将 medal0n-1中的数存入N1n中*/ scanf(%d,&Qi); while(Qidata1.medali=Qi; printf(nn(2).排序(金牌榜)nn); /*直接插入排序*/ for(i=2;i=n;+i) /*在数组M中按照插入排序从小到大排列金牌数*/if(MiMi-1) /*若,则需要把Mi插入到有序子表中*/ M0=Mi; /*Mi中的值放到M0中作为监视哨*/ Mi=Mi-1; for(j=i-2;M0Mj;-j) /*除后两个外依次与监视哨比较,若, Mj+1=Mj; 则记录后移*/Mj+1=M0; /*插入到正确位置*/ printf(nn下面是金牌排序显示:nn);for(i=1;i=n;i+)printf(%d ,Mi); for(i=0;i=1;i-)/*用两个for循环找到金牌数由多到少的国家在原来存储中 for(j=0;jdata1.goldenj) printf(t%s t%dt %dn,L1-data1.countryj,L1-data1.goldenj,L1-data1.medalj); Gj=j; /*j值放于数组G中相应的位置,使j在 下一次循环时不能等于以前找过的值*/ printf(nn排序(奖牌榜)nn); /*折半插入排序*/ for(i=2;i=n;+i) N0=Ni; /*放于N0中起监视作用*/ low=1; high=i-1; while(low=high+1;-j) /*记录后移*/ Nj+1=Nj; Nhigh+1=N0; /*插入*/ printf(nn下面是奖牌排序显示:nn); for(i=1;i=1;i-) /*用两个for循环找到奖牌数由多到少的国家在原来存储中 for(j=0;jdata1.medalj) printf(t%s t%dt %dn,L1-data1.countryj,L1-data1.goldenj,L1-data1.medalj); Hj=j; /*j值放于数组H中相应的位置,使j在 下一次循环时不能等于以前找过的值*/ printf(nn(3).查找(国家金牌数)nn); printf(请输入要查找的国家个数kn); scanf(%d,&k); while(kn) /*此部分为判断要查找的国家数目是否 超出范围,若超出,需要重新输入*/ printf(您要查找的国家个数大于存储个数,请重新输入n); scanf(%d,&k); printf(请依次输入这个%d国家的名字n,k); for(i=0;ik;i+) l=0; scanf(%s,Wi); for(j=0;jdata1.countryj) 较，找到国家对应的位置*/ printf(n此国家的金牌数为%d,奖牌数为%dnn,L1-data1.goldenj,L1-data1.medalj); l=1; while(l=0) /*若j循环一趟没有找到与Wi相同的 值，则运行while*/ printf(n没有查找到您要找的这个国家,请重新输入nn); scanf(%s,Wi); for(j=0;jdata1.countryj) printf(n此国家的金牌数为%d,奖牌数为%dnn,L1-data1.goldenj,L1-data1.medalj); l=1; /*给l赋值1,保证只要输错就一直进行 while循环*/ printf(nn查找(金牌数国家)nn);/*有序数组M中二分法查找金牌的过 printf(请输入您要查找的次数n); 程*/scanf(%d,&m);printf(请连续%d次输入金牌数n,m);for(i=0;im;i+) l=0; scanf(%d,&Fi); low=1; high=n; while(low=high) mid=(low+high)/2; if(EQ(Fi,Mmid) for(j=0;jdata1.goldenj)/*由有序组中的金牌找到其在原来存储中的位置*/printf(n此金牌数对应的国家为%s,奖牌数为%dnn,L1-data1.countryj,L1-data1.medalj); l=1; break; /*若在M中找到了相应的金牌数，在输 出后要跳出if，不然为死循环*/else if(LT(Fi,Mmid) high=mid-1; else low=mid+1; while(l=0) printf(n没有找到该奖牌数所对应的国家,请重新输入nn); scanf(%d,&Fi); low=1; high=n; while(low=high) mid=(low+high)/2;if(EQ(Fi,Mmid) for(j=0;jdata1.goldenj)printf(n此金牌数对应的国家为%s,奖牌数为%dnn,L1-data1.countryj,L1-data1.medalj); l=1; break;else if(LT(Fi,Mmid) high=mid-1;else low=mid+1; printf(nn查找(奖牌国家)nn);/*直接查找过程*/ printf(请输入您要查找的次数n); scanf(%d,&z); printf(请连续%d次输入奖牌数n,z); for(i=0;iz;i+) l=0; scanf(%d,&Zi); for(j=0;jdata1.medalj) 数值比较，找到奖牌对应的位置*/ printf(n此奖牌数对应的国家为%s,金牌数为%dnn,L1-data1.countryj,L1-data1.goldenj); l=1; while(l=0) printf(n没有存储你输入的奖牌数,请重新输入nn); scanf(%d,&Zi); for(j=0;jdata1.medalj) printf(n此奖牌数对应的国家为%s,金牌数为%dnn,L1-data1.countryj,L1-data1.goldenj); l=1; typedef struct LNode2 /*存储获得金牌的运动员姓名、国籍、获奖时间*/ struct data2 /*数据域*/ char athlete5050; /*存储运动员的二维数组*/ char country5050; /*存储国籍的二维数组*/ char time5050; /*存储时间的二维数组*/ char project5050; /*存储项目的二维数组*/data2; struct LNode2 *next; LNode2,*LinkList2;Status Storage_Search(LinkList2 L2) /*存储(Storage),查找(Search)*/ int i,j,m,k,l; char F5050; char G5050; char H5050; char K5050; L2=(LNode2 *)malloc(sizeof(LNode2); L2-next=NULL; printf(nn(1).存储(获金牌的运动员及其国籍、获奖时间、所参加的项目)nn); printf(请输入要存储的获金牌的运动员的人数mn); scanf(%d,&m); printf(请依次输入这%d个运动员的姓名n,m); for(i=0;idata2.athletei); printf(请依次输入这%d个运动员的国籍n,m); for(i=0;idata2.countryi); printf(请依次输入这%d个运动员的获奖时间n,m); for(i=0;idata2.timei); printf(请依次输入这%d个运动员所参加的项目n,m); for(i=0;jecti); printf(nn(2).查找(运动员项目+国籍+时间)nn); printf(请输入你要查找的运动员的人数kn); scanf(%d,&k); printf(请依次输入这%d个运动员的姓名n,k); for(i=0;ik;i+) l=0; scanf(%s,Fi); for(j=0;jdata2.athletej) 比较，找到对应的位置*/ printf(n这名运动员国籍是%s,获金牌时间是%s,所参加的项目是%snn,L2-data2.countryj,L2-data2.timej,L2-jectj); l=1; while(l=0) printf(n没有查找到您要找的这个运动员,请重新输入nn); scanf(%s,Fi); for(j=0;jdata2.athletej) printf(n这名运动员国籍是%s,获金牌时间是%s,所参加项目是%snn,L2-data2.countryj,L2-data2.timej,L2-jectj); l=1; printf(nn查找(国家获金牌运动员+时间+项目)nn); printf(请输入您要查找的次数n); scanf(%d,&k); printf(请连续%d次输入国家的名字n,k); for(i=0;ik;i+) l=0; scanf(%s,Gi); for(j=0;jdata2.countryj) 比较，找到对应的位置*/ printf(n此国家获得金牌的运动员有%s,所参加的项目间是%snn,L2-data2.athletej,L2-jectj,L2-data2.timej); l=1; while(l=0) printf(n没有存储您要查找的国家,请重新输入nn); scanf(%s,Gi); for(j=0;jdata2.countryj) printf(n此国家获得金牌的运动员有%s,所参加的项目是%s,获奖时间是%snn,L2-data2.athletej,L2-jectj,L2-data2.timej); l=1; printf(nn查找(时间获金牌的运动员+国籍+项目)nn); printf(请输入您要查找的次数n); scanf(%d,&k); printf(请连续%d次输入获奖时间n,k); for(i=0;ik;i+) l=0; scanf(%s,Hi); for(j=0;jdata2.timej) 比较，找到时间对应的位置*/ printf(n这天获金牌的运动员有%s,国籍为%s,所参加的项目是%snn,L2-data2.athletej,L2-data2.countryj,L2-jectj); l=1; while(l=0) printf(n没有存储您输入的时间,请重新输入nn); scanf(%s,Hi); for(j=0;jdata2.timej) printf(n这天获金牌的运动员有%s,国籍为%s,所参加的项目%snn,L2-data2.athletej,L2-data2.countryj,L2-jectj); l=1; printf(nn查找(项目获金牌的运动员+国籍+时间)nn); printf(请输入您要查找的次数n); scanf(%d,&k); printf(请连续%d次输入项目名称n,k); for(i=0;ik;i+) l=0; scanf(%s,Ki); for(j=0;jectj) 较，找到项目对应的位置*/ printf(n此项目获金牌的运动员有%s,国籍为%s,获奖时间是%snn,L2-data2.athletej,L2-data2.countryj,L2-data2.ti mej); l=1; while(l=0) printf(n没有存储您输入的时间,请重新输入nn); scanf(%s,Ki); for(j=0;jectj) printf(n此项目获金牌的运动员有%s,国籍为%s,获奖时间是%snn,L2-data2.athletej,L2-data2.countryj,L2-data2.timej); l=1; printf(nn 本次运行结束,谢谢您的使用!nn); main() LinkList1 L1; LinkList2 L2; Storage_Sort_Search(L1); /*调用Storage_Sort_Search*/ Storage_Search(L2); /*调用Storage_Search*/2. 算法设计与分析for(i=0;in;i+) scanf(%d,&Qi); while(Qidata1.medali=Qi; 此部分为查错改进，一个国家所获得的奖牌数显然要大于或者等于其获得的金牌数，此时若输入一个奖牌数值比原来的金牌数值要小，就会有错误，此时采用while循环，只要输入的有错误，就提示您重新输入。另外，为了排序方便，把奖牌数值存于N中，这也是经过考虑后做的改进。for(i=0;i=1;i-) for(j=0;jdata1.goldenj) printf(t%s t%dt %dn,L1-data1.countryj,L1-data1.goldenj,L1-data1.medalj); Gj=j; 此部分程序是在M数组存储的金牌数从小到大排完序的基础上运行。主要问题是，能把金牌排序输出，但是对应的国家不好找，需要在原来的对应存储位置寻找，采用两个for循环，时间复杂度O(n*n)，但是只需要找寻n个值，也就是在n*n 次中找n个值，有点浪费。若只有Mi=L1-data1.goldenj来判断，而存储的国家有重复，比如有3个国家的金牌数都是30枚，则会打印3*3=9次，就会有错。经过思考，我们加入了Gj!=j的条件，当找寻过一趟后就把j值存储下来，下一趟循环不允许j值等于以前找过的值，就能把问题解决。（注意：这时候并不是一一对应输出的，但不会有错误）for(i=2;i=n;+i) /*折半插入排序*/ N0=Ni; /*放于N0中起监视作用*/ low=1; high=i-1; while(low=high+1;-j) /*记录后移*/ Nj+1=Nj; Nhigh+1=N0; /*插入*/ 此部分为折半插入排序奖牌榜的算法，主要排序过程都在每句后面给了相应的介绍，主要是在原来存储时的N数组起了作用，使在排序中变得方便。for(i=0;im;i+) l=0; scanf(%d,&Fi); low=1; high=n; while(low=high) mid=(low+high)/2; if(EQ(Fi,Mmid) for(j=0;jdata1.goldenj) printf(n此金牌数对应的国家为%s,奖牌数为%dnn,L1-data1.countryj,L1-data1.medalj); l=1;break; else if(LT(Fi,Mmid) high=mid-1;else low=mid+1; while(l=0) printf(n没有找到该奖牌数所对应的国家,请重新输入nn); scanf(%d,&Fi); low=1; high=n; while(low=high) mid=(low+high)/2;if(EQ(Fi,Mmid) for(j=0;jdata1.goldenj) printf(n此金牌数对应的国家为%s,奖牌数为%dnn,L1-data1.countryj,L1-data1.medalj); l=1; break;else if(LT(Fi,Mmid) high=mid-1;else low=mid+1; 这一段程序是二分查找，由金牌数找到其对应的国家，但是里面出现很多问题，我们一一进行了修改或改进。首先，在找到输入的金牌数的情况下，就又要面临根据国家找金牌或奖牌相类似的难题，这个解决方法上面已经给了介绍。而当输入的金牌数未存储时，这个提示错误并且重新输入的过程比较麻烦。我们先给字母l一个赋值0，当能找到时，令l=1，此时就不会执行下面的while(l=0)过程。如果找不到，就不会有l=1，此时就会执行while(l=0)过程，再在while循环中加入原来的二分过程，把提示和修改过程加入到这一个while循环中，就能把正确数据输出。另外if判别中需要加入break,这样才不会使if变成死循环。调试分析1. 存储部分：我们是把与获得金牌的运动员有关的数据和与金牌榜奖牌榜有关的数据分开存储，在调试的时出现的主要问题有：存储牌数的整型数组与存储字符串的数组没有区分开，只要输入便会有错。考虑到要输入的值太多，改用for循环依次输入简便不少。另外，我们在调试过程中发现如果用二维数组存储字符串，会在查找中有关顺序的部分变简单不少。2. 排序部分：此部分主要涉及两个，根据金牌数和奖牌数找到对应的国家，里面涉及这两个排序。我们采用两种不同的排序方式，当把金牌数用堆排序时，调试过很多次，总有部分问题难以修改，只好对此部分运用了插入排序，前面的MN 数组也是根据此时的调试而加入的，从而对程序得出正确的结果。对奖牌的排序运用折半插入排序后，有时候会出现部分的乱序和不认识的字符出现，经调试以后，发现会有mid的类型定义以及对于高半区和低半区的位置的错误，多次修改调试后，这个折半过程可以顺利运行了。3. 查找部分：此部分查找的很多，相应的调试也较前两部分多。在由国家找其金牌数的最简单问题时，程序调试就显示有大问题，而不是括号或者字符这种小问题，由此引出了我们对于前面两个while循环的使用，对前面的程序的修改起了关键作用。在运行中偶然输入了一个没有存储的国家，此时，程序继续运行但是没有输出任何数据，因此我想到应该有一个改错结构，即使输错也应该给出提醒，并且重新输入，由此引出一部分新的程序改进。对于金牌找国家，运用了二分查找，此部分调试唯一的缺点就是忘记给EQ和LT宏定义，以至于最后差点放弃。奖牌找国家调试过程中只出现了一部分小小的错误，可以很快改正。获得金牌的运动员及其信息的相互查找，此部分调试过程中会显示比较的问题，发现是对应的比较类型不对，显示的查找也应该是换做另一类数组，同时应该加入前面改正的纠错结构，最终能够顺利调试运行。3. 运行结果与分析 依次存储十个国家金牌数和奖牌数，在奖牌数输入小于金牌数时，会提示有错误。 金牌榜和奖牌榜的排序有显示，只是截图未全面。只是采用的北京奥运会金牌榜的前十名作为测试数据。 输入错误会有提示，可以重新输入。 根据金牌数找国家的过程。 第二部分存储。由运动员出发进行查找 由国家出发进行查找。输入的国家没有存储会有提示错误，可以重新输入。由时间查找获奖运动员及其国籍和项目。由项目出发查找获得金牌的运动员以及其国籍和获奖时间。输入的项目没有存储的时候会有提示错误。问题及难点1. 存储中开始以为以一种类型的数组存储到结束，发现类型不仅仅是一种，而且维数最后要有一维和二维的，并且长度也要根据国家总个数进行设定。2. 输入金牌数后，紧接着要输入奖牌数，此时金牌数要比奖牌数少或者相等，这一部分的改正后来才想到。3. 金牌排序过程中，为了方便，需要在一开始放到一个一维数组中，在排完序后，怎样不出差错的由金牌把对应的国家找出，最后设计了一个存储j值的数组，使问题得到解决。只是堆排序过程始终没能正确运行下来，只好改掉。4. 奖牌是按照折半插入排序来的，只是按照从小到大放到里面后，最终的显示和查找，需要有时候从大到小，亦从后往前来用，有时候需要从小到大亦从前往后来用。5. 每次查找过程中，都要输入一个查找的次数，给for循环的使用带来了方便。每次也都要有相应的纠错结构，在这个地方编写过程中耗费了不少时间。主要是两次运用while循环，若查找到则把相应的第二个while的条件变化掉，如果没有查找到，则运行第二个while，此时还需要把if循环用break跳出，仅仅这一点也会导致错误。6. 进过分析，我们发现其实我们的问题可以化成两部分存储，其中一部分存储金牌榜、奖牌榜的数据，另一部分存储获得金牌的运动员的信息，这样不仅使相应的分析变得简便，而且更加容易操作，这也是一部分改进。7. 在第二部分查找中，既然运动员、国籍、获奖时间、项目是相互联系的，在编写完成一部分程序后，可以相应的运用到另外的几部分。4. 总结（收获与体会）卢栋：课程设计总共两周的时间，两周过得很快，也有很多的收获。首先，课程设计是以团队为单位的，两个人一组，需要两个人合作、分工。合作在前，分工在后，分工的目的是提高效率，但必须建立在合作的基础上。在这一点上，我做的显然不够，我主要负责编写查找的部分，程序主要分为存储、排序、查找，查找在最后一部分，所以在前面我就清闲了很多，但理想