《太原理工大学数据结构课程设计》由会员分享，可在线阅读，更多相关《太原理工大学数据结构课程设计（24页珍藏版）》请在金锄头文库上搜索。
1、1程序设计课程设计专业班级： 计科 1402 学号： 2014006935 学生姓名： 陈志棚 指导教师： 李丹丹、孟亮、王华 2016 年 1 月 10 日1.谁拿了最多奖学金2【问题描述】某校的惯例是在每学期的期末考试之后发放奖学金。 发放的 奖学金共有五种， 获取的条件各自不同：1) 院士奖学金，每人 8000 元，期末平均成 绩高于 80 分（ 80），并且在本学期内发表1 篇或 1 篇以上论文的学生均可获得；2) 五四奖学金，每人 4000 元，期末平均成 绩高于 85 分（ 85），并且班级评议成绩高于 80 分（80）的学生均可获得；3) 成绩优秀奖，每人 2000 元，期末平均
2、成绩高于 90 分（90）的学生均可获得；4) 西部奖学金，每人 1000 元，期末平均成绩高于 85 分（85）的西部省份学生均可获得；5) 班级贡献奖，每人 850 元，班级评议成绩高于 80 分（80）的学生干部均可获得；只要符合条件就可以得奖，每 项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是 87 分，班 级评议 成绩 82 分，同时他还是一位学生干部，那么他可以同时获 得五四奖学金和班级贡献奖 ，奖金总数是 4850 元。【设计需求及分析】现在给出若干学生的相关数据， 请计算哪些同学获得的奖 金总数最高（假设总有同学能满足获得奖学金的条件）。
3、输入数据格式格式：输入的第一行是一个整数 N（1 80&ST1.article=1)money1=8000;elsemoney1=0;return money1;int wusi(Student ST2)/五四奖 学金int money2;if(ST2.averscore85&ST2.banjiscore80)money2=4000;elsemoney2=0;return money2;int Chengjiyouxiu(Student ST3)/成绩优秀奖int money3;if(ST3.averscore90)money3=2000;elsemoney3=0;return money3;
4、int xibu(Student ST4)/西部奖学金int money4;if(ST4.averscore85&ST4.ch2=Y)money4=1000;elsemoney4=0;return money4;int banjigongxian(Student ST5)/班级贡献奖学金int money5;if(ST5.banjiscore80&ST5.ch1=Y)money5=850;elsemoney5=0;4return money5;3. 主函数：int main()int N,i,j,k;int sum=0;/存储奖学金总数printf(请输入学生总数 N：n);scanf(%d,
5、Student ArryN;/存储学生信息int MonN;/储存学生的奖学金;printf(请输入学生姓名、期末平均成 绩、班级评议成绩、是否学生干部、是否西部省份、论文发表数:n);for(i=0;iMonk)k=j;printf(奖学金最多的是:n%sn%dn,Arryk.name,Monk);for(i=0;ir0)rj+1=rj;cj+1=cj;j-;rj+1=r0;cj+1=c0;73、 主函数：int main()FILE *fp,*out;int str10,cou10,temp;/str用来储存来自文件的数据，cou 用来储存相同数据的个数，str 和 cou下标互相对应。t
6、emp 为临时储存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,printf(共有%d 个自然数n,t);for(i;i0)/若字符串 rj.elem.word 大于字符串r0.elem.word，则返回值大于 0rj+1
7、=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
8、);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.wordstri.elem.count=1;length+;/数组 str 长度加 1i+;elsestrj.elem.count+;/若数组 str 中存在 temp，则该字符串的计数 count 加 1InsertList(str,length)
9、;/调用字符串直接插入排序13printf(统计结果为:n);for(n=1;n的权。若v,Vn21不存在有向边，则 costij的权为无穷大（这里取 值为 32767）。设 S 是一个集合，其中的每个元素表示一个顶点，从源点到 这些顶点的最短距离已 经求出。 设顶点 v1为源点，集合 S 的初态只包含一个元素，即顶点 v1。数组 dist记录从源点到其他顶点当前的最短距离，其初值为 disti=costv1i,i=1,2,n。从 S 之外的顶点集合 V-S 中选出一个顶点 w，使 distw的值 最小。于是从源点到达 w 只通 过 S 中顶点，把 w 加入集合S 中，调整 dist 中记录的
10、从源点到 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 集中顶点数和是
11、否存在。如果存在，则比较和的路径长度，取长度较短者为 当前所求得的最短路径。 该 路径是中间顶点序号不大于 1的最短路径。其次，考虑从 vi到 vj是否包含有顶点 v2为中间顶点的路径，若没有，则说 明从 vi到 vj的当前最短路径就是前一步求出的；若有，那么可分解为和,而这两条路径是前一次找到的中间顶点序号不大于 1 的最短路径，将 这两条路径长度相加就得到路径 的18长度。将该长度与前一次中求出的从 vi到 vj的中间顶点序号不大于 1 的最短路径比较，取其长度较短者作为当前求得的从 vi到 vj的中间顶点序号不大于 2 的最短路径。依此类推，直到顶点 vn加入当前从 vi到 vj的最短路
12、径后， 选出从 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 vex
13、sMVNum; /顶点数组， 类型假定为 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;iarcsij=Maxint; /初始化邻接矩阵printf(输入%d 条边的 i,j 以及 w:n,e);for(k
14、=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(D2varcsvwarcsvw;P2w=v;printf(路径长度 路径n);for(i=1;iarcsij!=Maxint)Pij=j;elsePij=0;Dij=G-arcsij;for(k=1;k%d,k);k=Pkw;printf(-%d,w);printf(路径长度: %dn,Dvw);else21if(xz=1) printf(求单源路径,输入源点 v:);scanf(%d,Dijkstra(G,v,n);printf(结束求最短路径,再见!n);【实例测试及运行结果】1、 有向图：2、 运行
