太原理工大学软件学院课程设计实验报告相邻数对ISBN识别码文本文件单词统计送货.pdf

课程设计课程名称：程序设计课程设计设计名称：相邻数对、ISBN 识别码文本文件单词统计、构造最小生成树送货、学生信息管理系统专业班级：学号：学生姓名：指导教师：2017 年 06 月 21 日太原理工大学课程设计任务书学生姓名专业班级课程名称程序设计课程设计（程序设计课程设计（Programming Curriculum Design）设计名称相邻数对,ISBN 识别码,文本文件单词统计等设计周数2设计任务主要设计参数1.1.基本要求基本要求掌握 C 或 C+语言、结构化程序和面向对象程序设计方法、数据结构和离散数学理论知识，熟悉 C 或 C+程序的开发环境及调试过程，巩固和加深对理论课中知识的理解，提高学生对所学知识的综合运用能力。2.2.培养学生以下技能培养学生以下技能培养学生查阅参考资料、 手册的自学能力， 通过独立思考深入钻研问题，学会自己分析、解决问题。通过对所选题目分析， 找出解决方法，设计算法，编制程序与调试程序。能熟练调试程序，在教师的指导下，完成课题任务。按课程设计报告的要求撰写设计报告。设计内容设计要求1.1.设计内容设计内容相邻数对；ISBN 识别码；文本文件单词统计；构造可以使 n 个城市连接的最小生成树；送货；学生信息管理系统2.2.设计要求设计要求至少完成上述设计内容中的 4 个设计题目；对每个题目要给出设计方案、功能模块划分、算法思想；选择使用的数据结构；给出题目的程序实现；按要求撰写设计报告。主要参考资料1.程序设计课程设计指导书；2.程序设计技术、数据结构等课程教材；3. 其他自选的相关资料。学生提交归档文件课程设计报告封面应给出专业、班级、姓名、学号、指导教师和完成日期。每个设计题目的内容包括以下几项：设计题目、问题描述、问题分析、功能实现、测试实例及运行结果、源程序清单。注：1.课程设计完成后，学生提交的归档文件应按照：封面任务书说明书图纸的顺序进行装订上交（大张图纸不必装订）。2.可根据实际内容需要续表，但应保持原格式不变。指导教师签名指导教师签名：日期日期：2017.6.3I目目 录录1. 相邻数对.22. ISBN 识别码.43. 文本文件单词统计.74. 构造可以使 n 个城市连接的最小生成树.135. 送货.186. 学生信息管理系统.232题目一题目一 相邻数对相邻数对1.11.1【问题描述】【问题描述】给定 n 个不同的整数，问这些数中有多少对整数，它们的值正好相差 1。输入格式输入格式输入的第一行包含一个整数 n，表示给定整数的个数。第二行包含所给定的 n 个整数。输出格式输出格式输出一个整数，表示值正好相差 1 的数对的个数。1 1.2.2【设计及分析】【设计及分析】先设定一个全局数组 a，数组的大小尽量大，数组的下标对应的是输入的整数范围。数组内 0 表示没有对应于该下标的整数，1 表示有对应于该下标的整数。将数组全部初始化为0，表示没有进行输入。然后输入整数个数和相应的整数对数组进行修改，然后进行相邻数对筛选得出数对及数对的个数。数据流图如图 1-1。1 1.3.3【设计功能的实现】【设计功能的实现】#includeint a1005;void inita(int *a)/初始化数组int n=0;for(;n1004;n+)an=0;void main()int n,i,m,count=0;inita(a);printf(请输入整数的个数：n);scanf(%d,&n);printf(请输入整数：n);for(i=0;in;i+)/修改数组内容scanf(%d,&m);am=1;printf(输入的整数中的相邻数对如下：n);for(i=0;i1005;i+)/相邻数对的筛选图 1-13if(ai=1)&(ai+1=1)printf(%d,%d),i,i+1);count+=1;printf(n 输入的整数中共有%d 个相邻数对n,count);1 1.4.4【测试及运行结果】【测试及运行结果】1 1.5.5【总结】【总结】1.该题目比较简单，在经过老师的指导，有了大概的设计思想并进行代码的编写。2.在写代码的过程中，用了全局数组 a，在初始化数组后对其进行调整，但是在编写过程中，没有考虑好各变量的关系， 调整数组时发生了数据与输入数据不一致的情况， 此时虽然没有语法错误，但经过检查后发现了逻辑错误，然后增加了一个变量进行修改。3.该程序比较简单，但是觉得数组大部分的空间没有利用，有一定的资源浪费，在运算速度上也是比较慢的。4题目二题目二 ISBNISBN 识别码识别码2 2.1.1【问题描述】【问题描述】每一本正式出版的图书都有一个 ISBN 号码与之对应，ISBN 码包括 9 位数字、1 位识别码和 3 位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如 0-670-82162-4 就是一个标准的 ISBN 码。ISBN 码的首位数字表示书籍的出版语言，例如 0 代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如 670 代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。识别码的计算方法如下：首位数字乘以 1 加上次位数字乘以 2以此类推，用所得的结果 mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN 号码0-670-82162-4 中的识别码 4 是这样得到的：对 067082162 这 9 个数字，从左至右，分别乘以 1，2，9，再求和，即 01+62+29=158，然后取 158 mod 11 的结果 4作为识别码。编写程序判断输入的 ISBN 号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出是正确的 ISBN 号码。输入格式输入格式输入只有一行，是一个字符序列，表示一本书的 ISBN 号码（保证输入符合 ISBN 号码的格式要求）。输出格式输出格式输出一行，假如输入的 ISBN 号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的 ISBN 号码（包括分隔符“-”）。2 2.2.2【设计及分析】【设计及分析】用一个函数来计算正确的 ISBN 码。在主函数中，先输入一个字符串存放于全局数组 a中，然后用对字符串中特定符号-进行删除，并保存与数组 a1 中，原数组不变。处理数组 a1，用 judge 函数来计算正确的 ISBN 码，然后对数组 a1 中的 ISBN 码与计算的值是否相等，相等则输出 RIGHT，反之将计算出的 ISBN 码赋值给数组 a 中的 ISBN 码，并输出数组a。数据流图如图 2-1。图 2-152 2.3.3【设计功能的实现】【设计功能的实现】#include#include#includechar a100,a1100;int judge(char *a)/计算正确的 ISBN 码int i=0,l,s=0,m;for(;i9;i+)ai-=48;l=ai*(i+1);s=s+l;m=s%11;return m;void main()int i,m,j=0,l;printf(请输入 ISBN 码：);gets(a);l=strlen(a);for(i=0;ai!=0;i+)/将-删除掉便于计算if(ai!=-)a1j+=ai;elsea1j=ai;m=judge(a1);/计算 ISBN 码/printf(%d,m);if(m=(a19-48)/判断 ISBN 码是否正确printf(RIGHT);/正确输出 RIGHTelseal-1=(m+48);/错误则修改 ISBN 码并输出正确的 ISBN 码printf(%s,a);2 2.4.4【测试及运行结果】【测试及运行结果】62 2.5.5【总结】【总结】1、在编写程序框架时，我准备先实现 ISBN 码的正确计算与修改，所以先使用的是整数进行计算，在整数计算成功后修改为题目中所要求的字符串输入。2、在对字符串进行处理时，要考虑字符-在字符串中的位置，最初打算用三个数组来控制计算，但在计算过程中出现了错误。然后采取将字符串中的-删除并存储于新的数组a1 中，原始数组不变。3、在初始框架中，计算是针对整数进行的，在对字符串进行处理时，要考虑其与整数的关系，才能得到正确的计算值。在修改数组 a 时也需要考虑计算值之间的转换。7题目三题目三 文本文件单词统计文本文件单词统计3 3.1.1【问题描述】【问题描述】要统计英文文本文件中出现了哪些单词， 就要从文件中读取字符， 读取出来的连续英文字符认为是一个单词，遇空格或标点符号单词结束。3 3.2.2【设计及分析】【设计及分析】先构建一个结构体用于存放单词及对应的数目， 然后用一个函数来对所获取的单词进行处理，单词相同的则对应数目加 1，总单词数目加 1；单词不同的总单词加 1，对应单词数目加 1。主程序中通过文件进行读取单词，并将大写的字母转换为小写的字母。然后进行单词的排序，先按照单词出现的频率排序，然后按照首字母进行排序，最后对首字母相同的单词进行排序。数据流图如图 3-1。3 3.3.3【设计功能的实现】【设计功能的实现】#include#include#include struct word/结构体，用于存放单词及对应的个数char str30;int num;A1000;int sum;/记录总的单词数void chuli(char s)/处理获取的单词int i,j;int flag=0;图 3-18for(i=0;i=sum;i+)if(strcmp(Ai.str,s)=0)/相同的单词，单词总数加 1，对应单词数量加 1，标志 flag变成 1Ai.num+;flag=1;sum+;if(flag=0)/单词不同，则加入单词，并将对应的单词数和单词总数量加 1for(j=0;j30;j+)Asum.strj=sj;Asum.num+;sum+;int main()char ch,s30;int i,flag=0,l;int ii,jj;struct word a;FILE *fp;fp=fopen(tyut.txt,r);if(fp=NULL)printf(文件为空!);sum=0;ch=NULL;for(i=0;i1000;i+)Ai.num=0;/将所有单词对应的数目设置为 0while(ch!=-1)for(i=0;i=65&ch=97&ch=65&ch=65&ch=97&ch=122)continue;else break;chuli(s);/处理所获取的单词 s9/将单词按照出现的频率排序，便于后面的按字母顺序排序，由于之前初始化 A 的 sum=0，/所以去掉这一步按字母排序顺序会打乱for(ii=0;iisum;ii+)for(jj=ii+1;jjsum;jj+)if(Aii.numAjj.str0)a=Ajj;Ajj=Aii;Aii=a;/然后首字母相同的单词再进行排序for(ii=0;Aii.num!=0;ii+)for(jj=ii+1;Ajj.num!=0;jj+)l=0;while(Aii.strl=Ajj.strl)l+;if(Aii.strlAjj.strl)a=Ajj;Ajj=Aii;Aii=a;for(i=0;Ai.num !=0;i+)printf(%s 单词个数有：%dn,Ai.str,Ai.num);printf(nn);return 0;103 3.4.4【测试及运行结果】【测试及运行结果】11123 3.5.5【总结】【总结】1、设置了全局数组 A 和全局变量 s 用于存放单词和单词总数，用全局变量可以在使用对应函数时直接进行修改。2、在获取单词时，如果不进行大小写转换的话，相同的单词会因为大小写的不同而出现两次甚至多次，与题意不符，所以在获取单词的同时可以将大小写进行统一，便于最后统计的正确性。在本次实验我选择的是将大小写字母统一为小写字母，然后进行统计排序。3、在对所获取的单词进行排序时，先按单词出现的频率排序，将数组 A 中 sum 值为 0 的一律排到最后，便于进行下一步统计。第二步按照首字母进行排序，大致将单词进行了分段。第三步按照首字母相同的单词组进行排序，最终完成题目的要求。在排序的部分中，感觉程序过于繁琐，可以进行一些优化。13题目四题目四 构造可以使构造可以使 n 个城市连接的最小生成树个城市连接的最小生成树4 4.1.1【问题描述】【问题描述】给定一个地区的 n 个城市间的距离网，用 Prim 算法或 Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。2、要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。3、表示城市间距离网的邻接矩阵（要求至少 6 个城市，10 条边）。4 4.2.2【设计及分析】【设计及分析】在考虑使用 Prim 算法还是 Kruskal 算法时，我选择使用 prim 算法。虽然 kruskal 算法算法思想简单，但是在算法实现上需要判断新加入的边是否会构成回路，而 prim 算法不需要进行判断，构成的就是最小生成树。prim 算法中需要判断所选择的点是否已在点集中，若存在，则选择次小边所对应的点。在实现 prim 算法时，先建立了一个全局数组用于构建邻接矩阵，然后使用了两个函数，一个用于选择顶点 v 所对应最短边的点， 另一个用于选择在已有点集中选择最短边所对应的点。主函数中先初始化两个点集，规定一个起点，然后进行最小生成树的构造。数据流图如图 4-1。4 4.3.3【设计功能的实现】【设计功能的实现】#include PRIM算法图4-114#define m1 999;int mm20,l;int nodelist2020,n,d20,p20;void readgraph()/初始化邻接矩阵int i,j;printf(请输入图的顶点个数 n:);scanf(%d,&n);printf(请输入图所对应的邻接矩阵:n);for(i=1;i=n;i+)for(j=1;j=n;j+)scanf(%d,&nodelistij);printf(n);printf(已成功建立邻接矩阵n);for(i=1;i=n;i+)for(j=1;j=n;j+)printf(%5d,nodelistij);printf(n);int mine(int v)/求顶点 V 所连接的点的最短路径所对应的顶点int min1,i,ii;min1=nodelistv1;ii=1;for(i=1;i=n;i+)if(nodelistvimin1)min1=nodelistvi;ii=i;else continue;return ii;int mme()/求已有顶点的最短路径所对应的顶点int ei,ej,i;ei=mine(1);l=1;for(i=2;i=nodelistiej)ei=ej;l=i;15return ei;void main()int min,m20,v,i,ei,j;char ding7=A,B,C,D,E,F,G;min=0;readgraph();v=1;for(i=0;i=n;i+)/初始化两个顶点集mi=1;mmi=0;m1=0;mm1=1;printf(所构造的最小生成树的边及对应权值为：n);for(;vn;v+)ei=mme();if(mmei=1)/判断所找到的顶点是否已经加入顶点集nodelistlei=1000;nodelisteil=1000;v-=1;else mmei=1;mei=0;printf(%c 到%c 权值为%d,dingl-1,dingei-1,nodelistlei);min+=nodelistlei;/计算最短路径长度nodelistlei=1000;nodelisteil=1000;printf(n);printf(最小生成树的权值即最短路径长度为:%dn,min);164 4.4.4【测试及运行结果】【测试及运行结果】174 4.5.5【总结】【总结】1、在最初编写程序时，没有使用两个算法，直到最后构建生成树需要判断是否构成回路时才发现没有使用算法思想。2、在编写算法的过程中，发现判断是否构成回路的函数比较复杂一点，虽然 kruskal 算法思想简单，但是在实现方面觉得 prim 算法更容易一点。在选出最短边所对应的顶点后，只需要判断该顶点是否已经包含在点集，若包含，则选次短边所对的顶点并继续判断，反之则将该顶点加入到点集中，逐步构造出最短路径并计算出最短路径长度。3、在初始化邻接矩阵时需要自己手动输入，当矩阵比较大时，输入矩阵比较麻烦而且可能出现出入错误的情况，这一点需要改进，初步的想法是可以用文件的读取方式进行初始化。18题目五题目五 送货送货5 5.1.1【问题描述】【问题描述】为了增加公司收入，F公司新开设了物流业务。由于F公司在业界的良好口碑，物流业务一开通即受到了消费者的欢迎，物流业务马上遍及了城市的每条街道。然而，F公司现在只安排了小明一个人负责所有街道的服务。任务虽然繁重，但是小明有足够的信心，他拿到了城市的地图，准备研究最好的方案。城市中有n个交叉路口，m条街道连接在这些交叉路口之间，每条街道的首尾都正好连接着一个交叉路口。除开街道的首尾端点，街道不会在其他位置与其他街道相交。 每个交叉路口都至少连接着一条街道， 有的交叉路口可能只连接着一条或两条街道。基本需求：小明希望设计一个方案， 从编号为 1 的交叉路口出发， 每次必须沿街道去往街道另一端的路口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。输入数据格式： 输入的第一行包含两个整数n,m(1n10,n-1m20)， 表示交叉路口的数量和街道的数量，交叉路口从1到n标号。接下来 m 行，每行两个整数 a,b，表示和标号为 a 的交叉路口和标号为 b 的交叉路口之间有一条街道， 街道是双向的， 小明可以从任意一端走向另一端。 两个路口之间最多有一条街道。输出输出格式：如果小明可以经过每条街道正好一次，则输出一行包含 m+1 个整数p1,p2,p3,.,pm+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证 p1 最小，p1 最小的前提下再保证 p2 最小，依此类推。如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1。5 5.2.2【设计及分析】【设计及分析】经过查阅资料， 发现解决该问题需要使用欧拉回路的算法。 在图构建完成后，需要先判断图中顶点度数为奇数的个数 l， l 为 0 或 2 时存在回路， 反之不存在回路。 首先用函数初始化和设置邻接矩阵，然后用函数计算图中顶点度数是奇数的个数。在主函数中进行判断，若满足存在回路的条件，则用选择顶点的函数构建路径。选择顶点的函数中，要判断被选则的顶点 i 是否已经包含在点集 b，若不包含则选出顶点 i,若包含，如果只存在这一条边的情况下选择 i，反之选择满足条件的其他顶点 j。数据流图如图 5-1。195 5.3.3【设计功能的实现】【设计功能的实现】#include int a100100,b100;void chushihua(int l)/初始化邻接矩阵 a 和已选点集 bint i,j;for(i=1;i=100;i+)for(j=1;j=100;j+)aij=0;for(i=1;i=100;i+)bi=0;int shezhi(int m)/设置邻接矩阵int a1,b1,i;for(i=1;i=m;i+)scanf(%d,%d,&a1,&b1);aa1b1=1;ab1a1=1;return 0;int odd(int n)/计算顶点度数为奇数的个数int l=0,i,j,m,s;图5-120for(i=1;i=n;i+)m=0;s=0;for(j=1;j=n;j+)if (aij=1)m+;s=m%2;if(s=1)l+;return l;int xuanze(int v,int n)/选择路径int i,j;for(i=1;i=n;i+)if(avi=1)&bi!=1)/若边存在且点 i 未被选择时，则选择该点avi=0;aiv=0;bi=1;return i;else if(avi=1)&bi=1)/若边存在但点 i 已被选择，则判断 v 点是否存在其他边存在且点 j 未被选择的情况， 若存在，则返回 j;反之返回 ifor(j=i+1;j=n;j+)if(avj=1)&bj!=1)avj=0;ajv=0;bj=1;return j;else return i;return i;else continue;return 0;void main()int m,i,j,end1000,a1=0,l,n;printf(请输入交叉路口的数量和街道的数量:n);scanf(%d,&n);scanf(%d,&m);chushihua(n);/printf(%d,n);21printf(请输入%d 条街道：,m);shezhi(m);/*for(i=1;i=n;i+)for(j=1;j=n;j+)printf(%d,aij);printf(n);*/l=odd(n);printf(奇数度的结点有%d 个n,l);if(l!=0&l!=2)printf(-1n);printf(不存在路径！);elseprintf(存在路径n);j=1;b1=1;end1=1;for(i=1;i=(m+1);i+)/调用选择函数a1=xuanze(j,n);endi+1=a1;j=a1;printf(构成的路径为：n);for(i=1;i=(m+1);i+)/输出生成的路径printf(%d,endi);5 5.4.4【测试及运行结果】【测试及运行结果】225 5.5.5【总结】【总结】1、看过题目后要先去查阅资料，在知道处理的算法后要仔细阅读算法，了解算法的核心思想。在掌握算法后才可以进行编程，不然会做很多的无用功，浪费了时间和精力。2、在初始化矩阵时，发现最初设置的全局变量 n 没有被赋值，经过修改后把变量 n 设置在了主函数内。3、在编写选择函数时，对情况的判断掌握的不太好，最初是没有返回所有的情况， 导致函数不完整。 经过不断的调试后返回情况完整但是返回结果出现了错误。通过对代码的进一步修改，改正了函数中的逻辑错误，选择出了正确的路径。