2017太原理工大学软件课程设计.doc

课程设计 课程名称： 程序设计课程设计 设计名称： 相邻数对、ISBN识别码 文本文件单词统计、构造可以使n 个城市连接的最小生成树 专业班级：软件1502班 学号： 2015005509学生姓名： 冯旭超 指导教师： 吕进来 2017年06月23日14太原理工大学课程设计任务书学生姓名专业班级 软件 课程名称程序设计课程设计（Programming Curriculum Design）设计名称相邻数对,ISBN识别码,文本文件单词统计等设计周数2设计任务主要设计参数1.基本要求掌握C或C+语言、结构化程序和面向对象程序设计方法、数据结构和离散数学理论知识，熟悉C或C+程序的开发环境及调试过程，巩固和加深对理论课中知识的理解，提高学生对所学知识的综合运用能力。2.培养学生以下技能培养学生查阅参考资料、手册的自学能力，通过独立思考深入钻研问题，学会自己分析、解决问题。通过对所选题目分析，找出解决方法，设计算法，编制程序与调试程序。能熟练调试程序，在教师的指导下，完成课题任务。按课程设计报告的要求撰写设计报告。设计内容设计要求1.设计内容相邻数对；ISBN识别码；文本文件单词统计；构造可以使n个城市连接的最小生成树；送货；学生信息管理系统2.设计要求至少完成上述设计内容中的4个设计题目；对每个题目要给出设计方案、功能模块划分、算法思想；选择使用的数据结构；给出题目的程序实现；按要求撰写设计报告。主要参考资 料1.程序设计课程设计指导书；2.程序设计技术、数据结构等课程教材；3. 其他自选的相关资料。学生提交归档文件 课程设计报告封面应给出专业、班级、姓名、学号、指导教师和完成日期。每个设计题目的内容包括以下几项：设计题目、问题描述、问题分析、功能实现、测试实例及运行结果、源程序清单。注：1.课程设计完成后，学生提交的归档文件应按照：封面任务书说明书图纸的顺序进行装订上交（大张图纸不必装订）。2.可根据实际内容需要续表，但应保持原格式不变。指导教师签名： 日期：2017.6.3目 录1.相邻数对12.ISBN识别码33. 文本文件单词统计.54. 构造可以使n 个城市连接的最小生成树11 题目一 相邻数对1.1【问题描述】给定n 个不同的整数，问这些数中有多少对整数，它们的值正好相差1。输入格式输入的第一行包含一个整数n，表示给定整数的个数。第二行包含所给定的n 个整数。输出格式输出一个整数，表示值正好相差1 的数对的个数。1.2【设计及分析】输入输出610 2 6 3 7 83测试数据输出说明值正好相差1 的数对包括(2, 3), (6, 7), (7, 8)。所以输出:3数据约定1<=n<=1000，给定的整数为不超过10000 的非负整数。1.3【设计功能的实现】#include "stdafx.h"#include<iostream>using namespace std;int main()int n; int m = 0;cout << "请输入数字个数:"cin >> n;int A1000;cout << "分别为：n"for (int i = 0; i < n; i+)cin >> Ai;for (int i = 0; i < n; i+)for (int j = i + 1; j < n; j+)if (Ai - Aj) = 1) | (Aj - Ai) = 1)m+;cout << "相邻数对个数为：" << m << endl;return 0;1.4【测试及运行结果】1.5【总结】这个实验主要使用两个循环即可完成实验。题目二 ISBN识别码2.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，再求和，即0×1+6×2+2×9=158，然后取158 mod 11 的结果4 作为识别码。编写程序判断输入的ISBN 号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出是正确的ISBN 号码。输入格式输入只有一行，是一个字符序列，表示一本书的ISBN 号码（保证输入符合ISBN 号码的格式要求）。输出格式输出一行，假如输入的ISBN 号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN 号码（包括分隔符“-”）。2.2【设计及分析】输入1 输出10-670-82162-4 Right输入2 输出20-670-82162-0 0-670-82162-42.3【设计功能的实现】#include "stdafx.h"#include<iostream>using namespace std;char a13;int main()int i = 1, sum = 0; int x;cout << "请输入标准ISBN码（X-XXX-XXXXX-X）:"for (int i = 1; i <= 13; i+)cin >> ai;sum = a1 * 1 + a3 * 2 + a4 * 3 + a5 * 4 + a7 * 5 + a8 * 6 + a9 * 7 + a10 * 8 + a11 * 9;sum = sum - 45 * '0'x = sum % 11;if (x = 10 && a13 = 'X')cout << "Right" << endl;return 0;else if (x = a13-'0')cout << "Right" << endl;return 0;else for (int i = 1; i <= 12; i+) cout << ai; if (x = 10)cout << "X"<<endl; return 0;else cout << x << endl;return 0;2.4【测试及运行结果】2.5【总结】这个的关键点在于字符必须减去0才可以进行运算。题目三 文本文件单词统计3.1【问题描述】假设有如下的英文文本文档：(此处为太原理工大学学校简介英文版)TAIYUAN UNIVERSITY OF TECHNOLOGYTaiyuan University of Technology (TUT) has its history traced all the way back to the Western Learning School ofShanxi Grand Academy (1902), which was one of the three earliest national universities in China. With the tradition anddevelopment of over 100 years, TUT is now a general university with engineering as the major, sciences and technologyintegrated 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.Recollecting the centennial history, generations of TUT have created its mission and glory of a century with responsibilityand confidence; expecting the promising tomorrow, over 30,000 TUT students and faculty are producing splendor andperspectives by their wisdom and diligence. In the new era, Taiyuan University of Technology, following the Conceptionof Scientific Development, is determined to further the reformation on education, to reinforce the teaching management soas to upgrade its teaching and researching levels. Taiyuan University of Technology will be turning itself into aresearch-based university.设计C 或C+程序，统计在这样的英文文本文件中，出现了多少个单词，每个单词出现了几次。连续的英文字符都认为单词(不包括数字)，单词之间用空格或标点符号分隔。3.2【设计及分析】要统计英文文本文件中出现了哪些单词，就要从文件中读取字符，读取出来的连续英文字符认为是一个单词，遇空格或标点符号单词结束。使用线性表记录单词以及每个单词出现的次数。线性表中的单词按字典顺序存储。线性表的顺序存储结构如下：#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef structchar word21 /存储单词，不超过20 个字符int count; /单词出现的次数 ElemType;typedef structElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量- 4 - Seqlist;3.3【设计功能的实现】3.3.1 实现顺序表的基本操作顺序表的初始化：InitList(SqList &L)顺序表上查找指定的单词：LocateElem(SqList &L,char *s)若找到，单词的出现次数增1，返回0，否则返回该单词的插入位置。在顺序表上插入新的单词：InsertList(SqList &L,int i，char *s)要求按字典顺序有序。新单词的出现次数为1.输出顺序表上存储的单词统计信息：PrintList(SqList &L)输出文件中每个单词出现的次数以及文件中总的单词数(可输出到文件中)。3.3.2 统计单词数统计过程如下：（1）输入要统计单词的文本文件名，打开相应的文件；（2）初始化顺序表；（3）从文本文件中读取字符，直到文件结束。具体描述如下：while (读文件没有结束结束)过滤单词前的非字母字符；读取一个单词，以字符串形式存储在一个字符数组中；在线性表中查找该单词，若找到，单词的出现次数加1，否则返回其插入位置；上一步中，若没找到，则进行插入操作；处理下一个单词。（4）关闭文件，输出统计结果。#include "stdafx.h"#include<stdio.h>#include<string.h>#include<stdlib.h>#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef structchar word21; /存储单词，不超过 20 个字符int count; /单词出现的次数 ElemType;typedef structElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量- 4 - SqList;int lnitList(SqList *p) p->elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (p->elem = NULL)return 0;p->length = 0;p->listsize = LIST_INIT_SIZE; return 1;int LocateElem(SqList *p, char *word)int low, high, mid;low = 0; high = p->length - 1;while (low <= high)mid = (low + high) / 2;if (strcmp(word, p->elemmid.word) = 0)/表中进行二分查找p->elemmid.count+;return 0;else if (strcmp(word, p->elemmid.word) < 0)high = mid - 1;elselow = mid + 1;return low + 1;int lnsertList(SqList *p,int i,char *word)int j;ElemType *base;if (p->length >= p->listsize)base = (ElemType*)realloc(p->elem, (p->listsize + LISTINCREMENT)*sizeof(ElemType);if (base = NULL)return 0; p->listsize = p->listsize + LISTINCREMENT;/扩充表长p->elem = base;for (j = p->length; j >= i; j-)p->elemj = p->elemj - 1;strcpy(p->elemi - 1.word, word);p->elemi - 1.count = 1;p->length+;return 1;void PrintList(SqList *p, int num)FILE *fw;int i;int no = num;fw = fopen("D:单词计数.txt", "w");fprintf(fw, "该文章共有%d个单词n以下字母顺序来显示每个单词出现的个数n*n", no);fprintf(fw, "单词 出现次数n", no);for (i = 0; i < p->length; i+)fprintf(fw, "%-24s %-5dn", p->elemi.word, p->elemi.count);fprintf(fw, "*n");fclose(fw);/主函数void main()SqList L;char word21, ch, filename30, filename150; int num = 0, i, j = 0, mark = 0;FILE *fp;lnitList(&L);printf("请将要检索的文本文件放入D盘根目录，然后输入文件名（不用写后缀）：");scanf("%s", &filename);sprintf(filename1, "D:%s.txt", filename); getchar();if (fp = fopen(filename1, "r") = NULL)printf("打开文件失败，请输入文件名与文件路径n");getchar();exit(0);ch = fgetc(fp);while (ch != EOF)if (ch >= 'A'&&ch <= 'Z') | (ch >= 'a'&&ch <= 'z')ch = ch >= 'A'&&ch <= 'Z' ? ch + 32 : ch;wordj+ = ch;mark = 1;elseif (mark = 1)if (j > 20)printf("文章中部分单词太长不予统计");num+;wordj = '0'mark = 0;j = 0;i = LocateElem(&L, word);if (i > 0)lnsertList(&L, i, word);ch = fgetc(fp);fclose(fp);printf("统计结束￥请查看打开的 单词统计.txt里面便是检索结果。n");PrintList(&L, num);system("start""D:单词计数.txt");getchar();3.4【测试及运行结果】3.5【总结】这个实验要熟悉线性表的各个操作，才能做出来完整的程序。题目四 构造可以使n 个城市连接的最小生成树4.1【问题描述】给定一个地区的n 个城市间的距离网，用Prim 算法或Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价。4.2【设计及分析】1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。2、要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。3、表示城市间距离网的邻接矩阵（要求至少6 个城市，10 条边）。4.3【设计功能的实现】#include"stdafx.h"#include<stdlib.h>#include<stdio.h>#include<iostream>using namespace std;#define MaxVextexNum 30 /* 最大顶点数为30 */*#define INFINITY 1000 定义一个权值的最大值 */typedef structint vexsMaxVextexNum; /* 顶点表 */int arcsMaxVextexNumMaxVextexNum; /* 邻接矩阵，即边表 */int n; /* 顶点数和边数 */MGraph; /* MGragh是以邻接矩阵存储的图类型 */typedef structint adjvertex; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */int lowcost; /* 某顶点与已构造好的部分生成树的顶点之 间的最小权值 */ClosEdgeMaxVextexNum; /* 用prim算法求最小生成树时的辅助数组 */void CreatGraph(MGraph *G) /* 建立有向图G的邻接矩阵存储 */int i, j;printf("请输入顶点数n :");scanf("%d", &(G->n);/* 输入顶点数和边数 */printf("n请输顶点字符信息(共%d个)：", G->n);for (i = 0; i<G->n; i+)scanf("%d", &(G->vexsi); /* 输入顶点信息，建立顶点表 */printf("n请输入邻接矩阵，不存在则输入1000n");for (i = 0; i < G->n; i+)for (j = 0; j < G->n; j+)cin >> G->arcsij;printf("此连邻接矩阵为（1000为不存在）：n");for (i = 0; i<G->n; i+)for (j = 0; j<G->n; j+)printf("%8d", G->arcsij);printf("n");void PRIM(MGraph G, int u, ClosEdge closedge)/* 从第u个顶点出发构造图G的最小生成树，最小生成树顶点信息存放在数组closedge中*/int i, j, w, k, cost = 0;for (i = 0; i<G.n; i+) /* 辅助数组初始化 */if (i != u)closedgei.adjvertex = u;closedgei.lowcost = G.arcsui;closedgeu.lowcost = 0; /* 初始，U=u */for (i = 0; i<G.n - 1; i+) /* 选择其余的G.n-1个顶点 */w = 1000;for (j = 0; j<G.n; j+) /* 在辅助数组closedge中选择权值最小的顶点*/if (closedgej.lowcost != 0 && closedgej.lowcost<w)w = closedgej.lowcost;k = j; /* 求出生成树的下一个顶点k */closedgek.lowcost = 0; /* 第k顶点并入U集 */for (j = 0; j<G.n; j+) /* 新顶点并入U后，修改辅助数组*/if (G.arcskj<closedgej.lowcost)closedgej.adjvertex = k;closedgej.lowcost = G.arcskj;printf("n最小生成树中包括的城市间的道路:n");for (i = 0; i<G.n; i+) /*打印最小生成树的各条边*/if (i != u)printf("%d->%d,%dn", i, closedgei.adjvertex, G.arcsiclosedgei.adjvertex);cost = cost + G.arcsiclosedgei.adjvertex;printf("n最小生成树的代价为:%dnn", cost);int main()int t;MGraph G;ClosEdge closedge;CreatGraph(&G);printf("请输入起始点：");scanf("%d", &t);PRIM(G, t, closedge);return 1;4.4【测试及运行结果】4.5【总结】这个实验必须把普利姆算法搞懂，将思路理清晰，才能让程序完整的被写出来。