太原理工大学数据结构课程设计.docx

程序设计课程设计 专业班级： 计科1402 学号： 2014006935 学生姓名： 陈志棚 指导教师： 李丹丹、孟亮、王华 2016年 1月 10日1.谁拿了最多奖学金【问题描述】某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：1) 院士奖学金，每人8000元，期末平均成绩高于80分（80），并且在本学期内发表1篇或1篇以上论文的学生均可获得；2) 五四奖学金，每人4000元，期末平均成绩高于85分（85），并且班级评议成绩高于80分（80）的学生均可获得；3) 成绩优秀奖，每人2000元，期末平均成绩高于90分（90）的学生均可获得；4) 西部奖学金，每人1000元，期末平均成绩高于85分（85）的西部省份学生均可获得；5) 班级贡献奖，每人850元，班级评议成绩高于80分（80）的学生干部均可获得；只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。【设计需求及分析】现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。输入数据格式格式：输入的第一行是一个整数N（1 = N 80&ST1.article=1) money1=8000; else money1=0; return money1;int wusi(Student ST2)/五四奖学金 int money2; if(ST2.averscore85&ST2.banjiscore80) money2=4000; else money2=0; return money2;int Chengjiyouxiu(Student ST3)/成绩优秀奖 int money3; if(ST3.averscore90) money3=2000; else money3=0; return money3;int xibu(Student ST4)/西部奖学金 int money4; if(ST4.averscore85&ST4.ch2=Y) money4=1000; else money4=0; return money4;int banjigongxian(Student ST5)/班级贡献奖学金 int money5; if(ST5.banjiscore80&ST5.ch1=Y) money5=850; else money5=0; return money5;3. 主函数：int main() int N,i,j,k; int sum=0;/存储奖学金总数 printf(请输入学生总数N：n); scanf(%d,&N); Student ArryN;/存储学生信息 int MonN;/储存学生的奖学金; printf(请输入学生姓名、期末平均成绩、班级评议成绩、是否学生干部、是否西部省份、论文发表数:n); for(i=0;iN;i+) scanf(%s %d %d %c %c %d,&(A),&(Arryi.averscore),&(Arryi.banjiscore),&(Arryi.ch1),&(Arryi.ch2),&(Arryi.article); Moni=yuanshi(Arryi)+wusi(Arryi)+Chengjiyouxiu(Arryi)+xibu(Arryi)+banjigongxian(Arryi); k=0; for(j=1;jMonk) k=j;printf(奖学金最多的是:n%sn%dn,A,Monk);for(i=0;iN;i+) sum=sum+Moni; printf(奖学金总数为:%dn,sum); return 0;【实例测试及运行结果】【使用说明】1、 运行程序后输入学生总数；2、 输完总人数后分别输入各学生的姓名、期末平均成绩、班级评议成绩、是否学生干部、是否西部省份、论文发表数，每输完一个学生，以回车表示该学生信息录入完毕；3、 所以学生信息输完后回车，程序会自动得到结果！【心得体会】1、 程序设计思路不难，主要是定义两个数组，一个结构体数组用于存储学生信息，一个数组用于存储学生所得的奖学金，两个数组的下标相互对应，即一个数组学生信息对应着另一个数组中该学生所得奖学金，之后找出数组中奖学金最多的学生并输出学生信息和奖学金总数，最后输出所以学生所得的奖学金总数！2、 通过该程序，能够让我更好的掌握结构数组的使用。3、 程序可以加以改进，将判断是否能拿到奖学金的5个函数写成一个函数，这样能够使程序更加简洁！2、统计数字【问题描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。【设计需求及分析】原始数据保存在文件count.in中，文件包含n+1行。第1行是整数n(1=n=200000)，表示自然数的个数；第2n+1行每行一个自然数。结果保存在文件count.out中，文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开【设计功能的实现】（用C或C+描述）#includestdio.h#includestdlib.h1、 定义一个顺序查找函数，用于每次在文件中读取数据时判断存储的数组中是否有该数据，如果已存在，则返回该数据在数组中对应的下标，不存在，则返回0；int Locate(int r,int e,int length)/顺序查找函数 int i=0; while(i=length)&(ri!=e) i+; if(i=length) return i; else return 0;2、 定义一个直接插入排序函数，用于将已存完数据的数组将里面数据从小到大排序；void InsSort(int r,int c,int length)/直接插入排序 int i,j; for(i=2;ir0) rj+1=rj;cj+1=cj; j-; rj+1=r0;cj+1=c0; 3、 主函数：int main() FILE *fp,*out; int str10,cou10,temp;/str用来储存来自文件的数据，cou用来储存相同数据的个数，str和cou下标互相对应。temp为临时储存 int i=1,j=1,k,t; fp=fopen(C:UsersOxygenDesktop课程设计程序程序2count.in.txt,r); out=fopen(C:UsersOxygenDesktop课程设计程序程序2count.out.txt,w); if(fp=NULL) printf(无法打开输入文件); exit(0); if(out=NULL) printf(无法打开输出文件); exit(0); fscanf(fp,%d,&t); printf(共有%d个自然数n,t); for(i;i=t;i+) fscanf(fp,%d,&temp); printf(%dn,temp); k=Locate(str,temp,j-1);/查找函数，若查找成功，返回temp在数组str中的数组下标，否则返回0 if(k) couk+;/数组str中有temp该自然数，则对应计数数组cou加1； else strj=temp;/查找不成功，则将temp插入到str中 couj=1; j+; /结束后j为str数组长度 InsSort(str,cou,j);/将str数组中的自然数按从小到大排序，cou数组对应下标也跟着变化 printf(统计的结果为:n); for(i=1;ij;i+) printf(%d %dn,stri,coui);/屏幕输出统计结果 fprintf(out,%d %dn,stri,coui);/将结果输出到count.out中 fclose(fp); fclose(out);【实例测试及运行结果】待读取的文件程序运行结果：输出文件：【使用说明】1、 将需要统计的数字保存到文本文件中，文件名为“count.in”，并将文件放到程序对应的路劲下（C:UsersOxygenDesktop课程设计程序程序2count.in.txt）；2、 运行程序，则会在程序对应的输出路径（C:UsersOxygenDesktop课程设计程序程序2count.out.txt）中输出一个统计结果的count.out文件文件。3、 打开coun.out文件文本便可查看结果。【心得体会】1、 本道题的思路是：定义两个数组str和cou，数组str用于存储来自文本“count.in”中的自然数，数组cou用于存储自然数出现的个数。两个数组下标相互对应（同一个下标在两个数组中分别表示自然数和该自然数出现的次数）。通过fscanf函数每次向文件中读取一个自然数时，判断该读取的自然数在数组str中是否存在，如果存在，则在cou数组中对应的将改自然数出现的次数加1，如果不存在，则将该自然数插入到数组str中。最后将数组str中的自然数通过排序按从小到大排序，cou数组中的数按str数组相对应的发生变化。最后将str和cou数组中的数据输出到“count.out”文件文本中。2、 通过该程序，让我加深对文件文本的操作，以及对查找和排序的使用。3、 该程序可以加以改进，将str和cou这两个数组定义到一个结构体中，这样能够使程序更加精悍。3文件文本单词的计数【问题描述】假设有如下的英文文本文档：(此处为太原理工大学学校简介英文版)Taiyuan University of Technology (TUT) has its history traced all the way back to the Western Learning School of Shanxi Grand Academy (1902), which was one of the three earliest national universities in China. With the tradition and development of over 100 years, TUT is now a general university with engineering as the major, sciences and technology integrated and coordinate development of multiple disciplines. It is a university that is included in the “Project 211” - the national higher education promotion program for 100 top universities in China.设计C或C+程序，统计在这样的英文文本文件中，出现了多少个单词，每个单词出现了几次。连续的英文字符都认为单词(不包括数字)，单词之间用空格或标点符号分隔。【设计需求及分析】要统计英文文本文件中出现了哪些单词，就要从文件中读取字符，读取出来的连续英文字符认为是一个单词，遇空格或标点符号单词结束。使用线性表记录单词以及每个单词出现的次数。线性表中的单词按字典顺序存储。【设计功能的实现】（用C或C+描述）#include stdio.h#include stdlib.h#include string.h1、 定义一个线性表用于存储文件文本中读取的单词和记录单词出现的次数：typedef struct char word21; /存储单词，不超过20个字符 int count; /单词出现的次数 ElemType;typedef struct ElemType elem; /存储空间基址 Seqlist;2、 定义一个字符串顺序查找函数，用于每次在文件中读取数据时判断存储的数组中是否有该数据，如果已存在，则返回该数据在数组中对应的下标，不存在，则返回0；int LocateElem(Seqlist r,char e,int length)/字符串顺序查找函数 int i=0; while(i=length)&(strcmp(ri.elem.word,e)!=0)/strcmp为字符串比较函数，相等则返回0 i+; if(i=length) return i; else return 0;3、 定义一个字符串直接插入排序函数，用于将已存完数据的数组将里面数据从小到大排序；void InsertList(Seqlist r,int length)/字符串直接插入排序 int i,j; for(i=2;i0)/若字符串rj.elem.word大于字符串r0.elem.word，则返回值大于0 rj+1=rj; j-; rj+1=r0; 4、 主函数：int main() FILE *fp,*out; int i=1,j,n; int length=0;/储存数组str的长度 Seqlist str100; char temp21;/临时储存变量 fp=fopen(C:UsersOxygenDesktop课程设计程序程序3tyut.txt,r); out=fopen(C:UsersOxygenDesktop课程设计程序程序3counttyut.txt,w); if(fp=NULL) printf(无法打开输入文件!); exit(0); if(out=NULL) printf(无法打开输出文件!); exit(0); while(fscanf(fp,%s,temp)!=EOF) j=LocateElem(str,temp,length); if(j=0)/数组str中不存在temp，将temp插入到数组str中 strcpy(stri.elem.word,temp);/strcpy字符串赋值函数，将temp中的字符串赋值给stri.elem.word stri.elem.count=1; length+;/数组str长度加1 i+; else strj.elem.count+;/若数组str中存在temp，则该字符串的计数count加1 InsertList(str,length);/调用字符串直接插入排序 printf(统计结果为:n); for(n=1;nlength;n+) printf(%10s %dn,strn.elem.word,strn.elem.count);/屏幕输出统计结果 fprintf(out,%10s %dn,strn.elem.word,strn.elem.count);/将结果输出到counttyut.txt中 fclose(fp); return 0;【实例测试及运行结果】1、程序运行结果： 2、输入文件文本：4、 输出文本文件： 【心得体会】1、 本道题设计思路是：定义一个结构体数组str用于存储从文本本件中读取到的单词和各单词出现的次数，通过fscanf函数每次从文件文本中读取一个单词时，判断该单词在数组str.elem.word中是否存在，如果存在，则在str.elem.count中将该单词出现的次数加1，如果不存在，则将该单词插入到str.elem.word中。最后将数组str中的单词按字典顺序从小到大排序，并将str.elem.word和str.elem.count数据输出到“counttyut.txt”文件文本中。2、通过该程序，让我更加熟练的掌握如何从一个文件文本中读取一个字符串，以及更深度的掌握字符串大小的比较。5、交通咨询系统（最短路径问题）【问题描述】在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到顶点B的所含边数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。设计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询服务。【设计需求及分析】设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵：设G=（V，E）是一个图，结点集为。G的邻接矩阵当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 50 /最大顶点数typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型 Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int型MGraph;单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点SV到G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，cost是表示G的邻接矩阵，costij表示有向边的权。若不存在有向边，则costij的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为disti=costv1i,i=1,2,n。从S之外的顶点集合V-S中选出一个顶点w，使distw的值最小。于是从源点到达w只通过S中顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的distv和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到V-S为空。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化S和D，置空最短路径终点集，置初始的最短路径值；Sv1=TRUE; Dv1=0； /S集初始时只有源点，源点到源点的距离为0；While (S集中顶点数n)开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中；Sv=TRUE；更新当前最短路径及距离；任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要对G中任意一对顶点有序对“v,w(vw)”,找出v到w的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点 vi到vj的最短路径。如果从vi到vj存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径和是否存在。如果存在，则比较和的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么可分解为和,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。【设计功能的实现】（用C或C+描述）#include#include#define MVNum 100 /最大顶点数#define Maxint 32767enum boolean FALSE,TRUE ;typedef char VertexType;typedef int Adjmatrix;typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int型MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;void CreateMGraph(MGraph *G,int n,int e) /采用邻接矩阵表示法构造有向图G，n,e表示图的当前顶点数和边数int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint; /初始化邻接矩阵printf(输入%d条边的i,j以及w:n,e);for(k=1;karcsij=w;printf(有向图的存储结构建立完毕!n);void Dijkstra(MGraph *G,int v1,int n) /用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径Pv及其权Dv /设G是有向图的邻接矩阵，若边不存在，则Gij=Maxint /Sv为真当且仅当v属于s,即已求得从v1到v得最短路径int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v; /置初始的最短路径值if(D2vMaxint)P2v=v1; /v1是v的前驱（双亲）elseP2v=0; /v无前驱 /end forD2v1=0;Sv1=TRUE;for(i=2;in;i+) min=Maxint;for(w=1;w=n;w+)if(!Sw & D2wmin)v=w;min=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw;P2w=v;printf(路径长度 路径n);for(i=1;i=n;i+) printf(%5d,D2i);printf(%5d,i);v=P2i;while(v!=0) printf(-%d,v);v=P2v;printf(n);void Floyd(MGraph *G,int n)int i,j,k,v,w;for(i=1;i=n;i+)for(j=1;jarcsij!=Maxint)Pij=j;elsePij=0;Dij=G-arcsij;for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+) if(Dik+Dkj%d,k);k=Pkw; printf(-%d,w);printf(路径长度: %d