太原理工《程序设计课程设计》实验报告

程序设计课程设计姓 名：学 号：班 级：指导教师： 成 绩：2015年7月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 = 100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。输出数据格式：输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这N个学生获得的奖学金的总数。【设计需求及分析】定义结构体student，包含name20(名字),Qg(期末平均成绩),Cg(班级评议成绩),sg2(是否是学生干部),xb2(是否是西部学生),money(奖学金)。只有一个主函数，用结构体定义一个动态数组，先给定数组长度N，然后在for循环中循环N次输入N个学生的数据，每次输入完一组，就直接按要求得出其奖学金数，最后找出奖学金最多的人和他的名字，N个学生的奖学金总数直接相加即可。【设计功能的实现】（用C语言）设计如下：#include#include#include struct student char name20; int Qg; int Cg; char sg2; char xb2; int lw; int money;void main()struct student *array;array=NULL;int N,i,zs=0,max=0,j=-1;/zs为总奖学金数量，j为奖学金最多的人序号，max为最多奖学金char s2=Y;scanf(%d,&N);array=(struct student*)malloc(N*sizeof(struct student);if(array=0)printf(FAIL);exit(0); for (i = 0; i 80&arrayi.lw0)num+=8000;if(arrayi.Qg85&arrayi.Cg80)num+=4000;if(arrayi.Qg90) num+=2000;if(arrayi.Qg80&!strcmp(arrayi.xb,s)num+=1000;if(arrayi.Qg80&!strcmp(arrayi.sg,s)num+=850;arrayi.money=num;zs+=num; for(i = 0; i N; i+)if(maxarrayi.money) j=i; max=arrayi.money; if(j=-1) printf(无人得到奖学金);else printf(%sn%dn%dn,arrayj.name,arrayj.money,zs); free(array); /*释放由malloc函数申请的内存块*/【实例测试及运行结果】 4个学生，奖学金最多的是ChenRuiyi，金额为9000,奖学金总数为28700【使用说明】 注意一定要按照按要求输入，由于规定了输入输出格式，所以我并没有加上超出范围的提示说明，按要求输入才能得到正确的计算结果。【心得体会】 由于对结构体动态数组的使用还没有怎么熟悉，一开始花费了不少时间去查阅书籍，而一旦数组建立好，先其中添加和查询数据就是相当于对普通数组的操作，实现起来也简单易懂，只是按要求在结构体内加了限定条件，为了按照要求输出，超出限制时并不能给出提示，这一点有待提高。【问题描述】问题：某次科研调查时得到了n个自然数，每个数均不超过1500000000（*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。功能： 从文件中每读出一个数据，就在顺序表中查找，若存在，则该数出现次数增，否则将该数插入数组中，出现次数为，插入后使顺序表中的数据按自然数有序。输入数据格式格式：原始数据保存在文件中，文件包含n+1行。第1行是整数n(1=n=200000)，表示自然数的个数；第2n+1行每行一个自然数。输出数据格式格式：结果保存在文件中，文件包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。【测试数据】82424510021002 34 25 1100 2由于数据量可能很大，要注意程序的运行效率。【设计需求及分析】定义顺序表，元素类型为：Element，顺序表类型为：SeqList，用顺序表的数组data记录自然数和该数出现的次数。定义如下： typedef struct data long int number;/*数字*/ long int count;/*该数字出现的个数*/ Element;typedef struct listElement data10000; /*存储自然数和该数出现的次数*/int length; /*存储不同自然数的个数,即顺序表的长度*/ SeqList;只有一个函数主函数，首先打开文件，按格式读取文件内容到结构体数组中，先读取数字总数，然后设置循环读取数字，有重复则将该数字的数量加1，无重复则新建一个数字，其数量为1，长度加1，关文件。其后对保存进入数组的数据进行冒泡排序，最后将排好序的数组放入文件中，关文件。【设计功能的实现】（用C语言）设计如下：#include#includetypedef struct data long int number; long int count; Element;typedef struct list Element data10000; /*存储自然数和该数出现的次数*/ int length; /*存储不同自然数的个数,即顺序表的长度*/ SeqList;void main() Element El;SeqList Se;int i=0,j,k,n,p,t1,t2;FILE *fp;if(fp=fopen(G:count.in.txt,r)=NULL)printf(fail!n);exit(0);fscanf(fp,%d,&n);/一个数字都没有if(n=0)printf(文件无数字！);exit(1);/将文件内容读取并储存while(in)fscanf(fp,%d,&p);if(i=0)Se.datai.number=p;Se.datai.count=1;Se.length=1;elsefor(k=0;kSe.length&p!=Se.datak.number;k+);if(kSe.length) /有重复数字Se.datak.count+;else /无重复数字Se.datak.number=p;Se.datak.count=1;Se.length+;k+;i+;fclose(fp);/冒泡排序for(i=0;iSe.length-1;i+)for(j=0;jSe.dataj+1.number)t1=Se.dataj.number;Se.dataj.number=Se.dataj+1.number;Se.dataj+1.number=t1;t2=Se.dataj.count;Se.dataj.count=Se.dataj+1.count;Se.dataj+1.count=t2;/输入文件if(fp=fopen(G:count.out.txt,w)=NULL)printf(fail!n);exit(0);for(k=0;kSe.length;k+)fprintf(fp,%d %dn,Se.datak.number,Se.datak.count);fclose(fp);【实例测试及运行结果】【使用说明】 按照要求输入数字进入count.in文件即可。【心得体会】 花费了很多的时间去熟悉文件的输入输出，一开始并未按格式读取文件内容，计算结果全部是乱码，后来看书修改了代码才能正常读取和录取，对于排序算法，我个人比较熟悉冒泡排序，就直接用冒泡排序对其进行排序，实现起来也还可以。【问题描述】设计C或C+程序，统计一个英文文本文件中，出现了多少个单词，每个单词出现了几次。连续的英文字符都认为单词(不包括数字)，单词之间用空格或标点符号分隔。 【设计需求及分析】要统计英文文本文件中出现了哪些单词，就要从文件中读取字符，读取出来的连续英文字符认为是一个单词，遇空格或标点符号单词结束。使用线性表记录单词以及每个单词出现的次数。线性表中的单词按字典顺序存储。线性表的顺序存储结构如下：#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef struct char word21 /存储单词，不超过20个字符 int count; /单词出现的次数 ElemType;typedef struct ElemType *elem; /存储空间基址 int length; /当前长度int listsize; /当前分配的存储容量 Seqlist;顺序表的初始化：InitList(SqList &L)顺序表上查找指定的单词：LocateElem(SqList &L,char *s) 若找到，单词的出现次数增1，返回0，否则返回该单词的插入位置。在顺序表上插入新的单词：InsertList(SqList &L,int i，char *s) 要求按字典顺序有序。新单词的出现次数为1.输出顺序表上存储的单词统计信息：PrintList(SqList &L) 输出文件中每个单词出现的次数以及文件中总的单词数(可输出到文件中)。统计过程如下：（1）输入要统计单词的文本文件名，打开相应的文件；（2）初始化顺序表；（3）从文本文件中读取字符，直到文件结束。具体描述如下：while (读文件没有结束结束) 过滤单词前的非字母字符； 读取一个单词，以字符串形式存储在一个字符数组中； 在线性表中查找该单词，若找到，单词的出现次数加1，否则返回其插入位置； 上一步中，若没找到，则进行插入操作； 处理下一个单词。（4）关闭文件，输出统计结果。【设计功能的实现】（用C语言）设计如下：#include#include#include#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef struct char word21; /存储单词，不超过20个字符 int count; /单词出现的次数 ElemType;typedef struct ElemType *elem; /存储空间基址 int length; /当前长度 int listsize; /当前分配的存储容量 SqList;/构造空线性表int InitList(SqList &L) L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)return 0;L.length=0;L.listsize=LIST_INIT_SIZE;return 1;/顺序表上查找指定的单词(二分法)int LocateElem(SqList &L,char *word)int low,high,mid;low=0;high=L.length-1;while(low=high)mid=(low+high)/2;if(strcmp(word,L.elemmid.word)=0)L.elemmid.count+;return 0;else if(strcmp(word,L.elemmid.word)=L.listsize)base=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(base=NULL)return 0;L.listsize=L.listsize+LISTINCREMENT;L.elem=base;for(j=L.length;j=i;j-)L.elemj=L.elemj-1;strcpy(L.elemi-1.word,word);L.elemi-1.count=1;L.length+;return 1;/输出顺序表上存储的单词统计信息void PrintList(SqList &L,int num)FILE *fw;int i;int n=num;fw=fopen(G:单词计数.txt,w);fprintf(fw,文章共有%d个单词n出现次数(按字典排序)nn,n);fprintf(fw,单词 出现次数n,n);for(i=0;i=A&ch=a&ch=A&ch20)printf(文章中部分单词太长不予统计);num+; wordj=0; mark=0; j=0; i=LocateElem(L,word); if(i0)InsertList(L,i,word);ch=fgetc(fp);fclose(fp);printf(统计完成，单词计数.txt文件在G盘生成。);PrintList(L,num);【实例测试及运行结果】【使用说明】 文件要提前建立好才能用。【心得体会】 一开始没有头绪，后来看了提示新建了三个函数，写起来就方便许多了，最主要的一个函数是用二分法查找顺序表上的单词，找到了个数加一，没找到就返回，向顺序表中添加单词，其余的就是之前的文件输入输出，不同之前的是一开始的文件名是用户指定的，然后统计的信息放在另外一个文件中即可。【问题描述】在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从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语言）设计如下：#include#include#define MVNum 50#define Maxint 32767enum booleanFALSE,TRUE;/ 枚举类型typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum; /顶点数组，类型假定为char型Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int型MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum;void CreateMGraph(MGraph * G,int n,int 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)/迪杰斯特拉算法，最短路径int D2MVNum,p2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v;if(D2vMaxint)p2v=v1;elsep2v=0;D2v1=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;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+DkjDij) Dij=Dik+Dkj;pij=pik;void main() MGraph *G; int e,n,v,w,k; G=(MGraph *)malloc(sizeof(MGraph); printf(输入图中顶点个数和边数n,e:); scanf(%d,%d,&n,&e); CreateMGraph(G,n,e); printf(1.求一个城市到所有城市的最短路径n); printf(求单源路径，输入源点v :); scanf(%d,&v); Dijkstra(G,v,n); printf(2.求任意的两个城市之间的最短路径n); Floyd(G,n); printf(输入源点（或起点）和终点:v,w:); scanf(%d,%d,&v,&w); k=pvw; if (k=0) printf(顶点%d 到 %d 无路径!n,v,w); else printf(从顶点%d 到 %d 最短路径路径是:%d,v,w,v); while (k!=w) printf(-%d,k); k=pkw; printf(-%d,w); printf(径路长度:%dn,Dvw); 【实例测试及运行结果】实际图：【使用说明】 输入格式：个数，边数 i，j，k 其余按照要求即可使用。【心得体会】 这个程序是算法设计课程的内容，用到了迪杰斯特拉算法和费洛伊德算法，一开始则是用数据结构中图结构体建立。虽然之前已经学过了其算法如何实现，不过自己编写确实有难度，想起来也麻烦，更重要的是还是有向图，还有方向问题，总之虽然困难重重，但是通过不懈的努力终于解决了问题，写出代码。