太原理工大学软件工程课程设计实验(15页).doc

-文本文件单词的检索与计数专业：软件工程 班级： 1227班 姓名： 王晓春 学号： 2012005774 同组人：王晓春 闫瑞娟 张泽磊 组长：王晓春 完成日期： 2014.6.25 一【问题描述】串是非数值处理中的主要对象，如在信息检索、文本编辑、符号处理等许多领域，得到越来越广泛的应用。在高级语言中也引入了串数据类型概念，并且串变量与其他变量（如整型、实型等）一样，可以进行各种运算。然而，在各种不同类型的应用中，所处理的串有不同的特点，要想有效地实现串的处理，就必须熟悉串的存储结构及其基本运算。本课程设计的目的就是熟悉串类型的实现方法和文本模式匹配方法，熟悉如何利用模式匹配算法实现一般的文本处理技术。本课程设计分两步：首先，设计出串定位算法（即模式匹配算法）及其实现；然后，再利用串定位算法设计文本文件的检索及单词的计数等操作。二【设计需求及分析】1.设计要求 1.1串模式匹配算法的设计要求在串的基本操作中，在主串中查找模式串的模式匹配算法即求子串位置的函数Index(S,T)，是文本处理中最常用、最重要的操作之一。所谓子串的定位就是求子串在主串中首次出现的位置，又称为模式匹配或串匹配。模式匹配的算法很多，在这里只要求用最简单的朴素模式匹配算法。该算法的基本思路是将给定子串与主串从第一个字符开始比较，找到首次与子串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字符位置开始比较，而且需要从主串的任一给定位置检索匹配字符串，所以，首先要给出两个算法：1标准的朴素模式匹配算法2给定位置的匹配算法1.2文本文件单词的检索与计数的设计要求要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给定单词在文本文件中出现的总次数；检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。1建立文本文件2给定单词的计数3检索单词出现在文本文件中的行号、次数及其位置4主控菜单程序的结构2.概要设计示例如下：2.6算法设计 朴素模式匹配算法该算法的基本思想是：设有三个指针i,j,k，用i指示主串S每次开始比较的位置；指针j,k分别指示主串S和模式串T中当前正在等待比较的字符位置；一开始从主串S的第一个字符（i=0;j=1）和模式T的第一个字符（k=0）比较，若相等，则继续逐个比较后续字符（j+,k+）。否则从主串的下一个字符（i+）起再重新和模式串（j=0）的字符开始比较。依此类推，直到模式T中的所有字符都比较完，而且一直相等，则称匹配成功，并返回位置i；否则返回-1，表示匹配失败。顺序串的模式匹配算法如下：int index(SString S, SString T) /求子串T在主串S中首次出现的位置int i,j,k,m,n;m=T.length; /模式串长度赋mn=S.length; /目标串长度赋nfor (i=0; i<=n-m; i+) j=0; k=i; / 目标串起始位置i送入k while (j<=m && s.chk=t.chj) k+; j+; /继续下一个字符的比较 if (j=m) /若相等，则说明找到匹配的子串，返回匹配位置i，/否则从下一个位置重新开始比较 return i; /endforreturn -1; /endIndex 给定位置的串匹配算法该算法要求从串S1（为顺序存储结构）中第k个字符起，求出首次与字符串S2相同的子串的起始位置。该算法与上面介绍的模式匹配算法类似，只不过上述算法的要求是从主串的第一个字符开始，该算法是上述算法的另一种思路：从第k个元素开始扫描S1，当其元素值与S2的第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到S2结束为止。若都相同，则返回当前位置值；否则继续上述过程，直至S1扫描完为止，其实现算法如下：Int PartPosition(SString S1, SString S2, int k)int i, j;i=k-1; /扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1j=0; /扫描s2的开始下标while (i<s1.length && j<s2.length)if (s1.chi=s2.chj) i+; j+; /继续使下标移向下一个字符位置else i=i-j+1; j=0; /使i下标回溯到原位置的下一个位置，使j指向s2的第一个字符，再重新比较if (j>=s2.length) return i- s2.length; /表示s1中存在s2，返回其起始位置else return -1; /表示s1中不存在s2， 返回-1 /函数结束说明：以上两个算法可统一为一个算法，即在子串定位算法Index(S,T)的参数中增加一个起始位置参数即可。2.7各模块及其伪码：1.建立文本文件建立文件的实现思路是：（1）定义一个串变量；（2）定义文本文件；（3）输入文件名，打开该文件；（4）循环读入文本行，写入文本文件，其过程如下： While ( 不是文件输入结束) 读入一文本行至串变量；串变量写入文件；输入是否结束输入标志；（5）关闭文件。2给定单词的计数该功能需要用到前一节中设计的模式匹配算法，逐行扫描文本文件。匹配一个，计数器加1，直到整个文件扫描结束；然后输出单词出现的次数。其实现过程如下：（1）输入要检索的文本文件名，打开相应的文件；（2）输入要检索统计的单词；（3）循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数。具体描述如下：While (不是文件结束) 读入一行并到串中； 求出串长度； 模式匹配函数计数；（4）关闭文件，输出统计结果。3.检索单词出现在文本文件中的行号、次数及其位置这个设计要求与上一个类似，但要相对复杂一些。其实现过程描述如下：（1）输入要检索的文本文件名，打开相应的文件；（2）输入要检索统计的单词；（3）行计数器置初值0；（4）while (不是文件结束) 读入一行到指定串中； 求出串长度； 行单词计数器置0； 调用模式匹配函数匹配单词定位、该行匹配单词计数； 行号计数器加1； If (行单词计数器!=0) 输出行号、该行有匹配单词的个数以及相应的位置；2.8函数调用关系主程序CreatTextFile()SubStrCount() SubStrInd()PartPosition()三【设计功能的实现】#include "stdafx.h"#include<stdio.h>#include<string.h>#define MaxStrSize 256 /根据用户需要自己定义大小typedef structchar chMaxStrSize; /ch是一个可容纳256个字符的字符数组int length;SString; /定义顺序串类型int PartPosition(SString s1, SString s2, int k)/检索单词出现在文本文件中的位置int i, j;i=k-1; /扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1j=0; /扫描s2的开始下标while (i<s1.length&&j<s2.length)if(s1.chi=s2.chj)i+;j+; /继续使下标移向下一个字符位置elsei=i-j+1;j=0;if(j>=s2.length)return i-s2.length;else return -1; /表示s1中不存在s2，返回-1 /表示s1中不存在s2，返回其起始位置 /函数结束void CreatTextFile()SString S;char fname10, yn;FILE *fp;printf("输入要建立的文件名： ");scanf("%s", fname);fp=fopen(fname,"w");yn='n' /输入结束标志初值while(yn='n'|yn='N')printf("请输入一行文本：");gets(S.ch);gets(S.ch);S.length=strlen(S.ch);fwrite(&S, S.length, 1, fp);fprintf(fp,"%c", 10); /是输入换行printf("结束输入吗？y or n: ");yn=getchar();fclose(fp); /关闭文件printf("建立文件结束！");void SubStrCount()FILE *fp;SString S,T; /定义两个串变量char fname10;int i=1,j,k;printf("输入文本文件名： ");scanf("%s", fname);fp=fopen(fname ,"r");printf("输入要计数的单词或字符串：");scanf("%s", T.ch);T.length=strlen(T.ch);while(!feof(fp)/扫描整个文件文本/fread(&S.ch,1,sizeof(S),fp); /读入一行文本memset(S.ch,'0', 256);fgets(S.ch,100,fp);S.length=strlen(S.ch);k=0; /初始化开始检索位置while(k<S.length-1) /检索整个主串Sj=PartPosition(S,T,k);if(j<0)break;elsei+; /单词计数器加1k=j+T.length; /继续下一字串的检索printf("n单词%s在文本文件%s中共出现%d次n", T.ch, fname,i); /统计单词出现个数void SubStrInd()/单词或字符串的检索与计数FILE *fp;SString S,T; /定义两个串变量char fname10;int i,j,k,l,m;/int wz20;/?printf("输入文本文件名：");scanf("%s", fname);fp=fopen(fname,"r");printf("输入要检索的单词：");scanf("%s", T.ch);T.length=strlen(T.ch);l=0; while(!feof(fp)/fread(&S, sizeof(S), 1, fp);/读入一行文本memset(S.ch,'0', 256);fgets(S.ch,256,fp);S.length=strlen(S.ch);l+;k=0;/从串T的扫描初始位置默认为数组第一位，可根据用户要求改变k值，成为给定位置的串匹配算法i=0;while(k<S.length-1)j=PartPosition(S,T,k);if(j<0)break;elsei+;/i记录被检测单词的出现次数wzi=j;/用数组wz记录被检测单词在所在行的位置k=j+T.length;/k为检测目标单词的下一个起始位置if(i>0)printf("行号：%d , 次数：%d, 位置分别为：",l, i);for(m=1;m<=i;m+) printf("%4d", wzm+1); printf("n");int main()void CreatTextFlie(), SubStrInd();int xz;/操作号doprintf("*n");printf("*文本文件的检索、字符串的统计及定位*n");printf("*n");printf("* 1.建立文本文件 *n");printf("* 2.单词字符串的计数 *n");printf("* 3.单词字符串的定位 *n");printf("* 4.退出程序 *n");printf("*n");printf(" 请选择（1-4） n");scanf("%d", &xz);switch(xz)case 1:CreatTextFile(); break;case 2:SubStrCount(); break;case 3:SubStrInd(); break;case 4:return 0;default: printf("选择错误，重新选n");while(1);四【实例测试及运行结果】运行实例一：未输入文件前的页面输入文本文件，计数单词出现的次数 检索某单词的行号，出现次数，以及位置运行实例二：未输入文件前的页面输入文本文件，计数单词出现的次数检索某单词的行号，出现次数，以及位置5课程总结在此次的实验过程中，我对结构化的编程思想有了更深刻的理解。在实验中，遇到过很多问题，比如对抽象数据结构线性表的实现方法不熟悉，对数组定义模糊等，后来经过思考并查阅资料解决了问题，使自己养成了独立思考、独立解决问题的能力。通过这次设计，我学会了和别人配合工作，因为一个人所学的知识不可能面面俱到的，只有通过合作，发挥自己的优点，体现团队精神，才能使工作做得更为出色。通过这次设计，我学到了许多书本上学不到的知识，增强了自己的动手能力。计算机技术的高速发展，使我深深地认识到只有不断的加强学习，才能在计算机技术方面不至于被淘汰，今后，我还要加强学习，努力使自己成为一位专业的计算机人员，为我自己所从事的工作服务。 二交通咨询系统设计专业：软件工程 班级： 1227班 姓名： 闫瑞娟 学号： 2012005779 同组人：张泽磊 王晓春 闫瑞娟 组长：张泽磊 完成日期： 2014.6.25 一、问题描述在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到顶点B的所含边数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。设计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询服务。二、设计需求及分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。3.2.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵：设G=（V，E）是一个图，结点集为。G的邻接矩阵当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 50 /最大顶点数typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型 Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int型MGraph;三、设计功能的实现（本次课设使用C语言描述）3.3.1 建立有向图的存储结构#include <stdio.h>void CreateMGraph(MGraph *G,int n,int e)int i,j,k,w;for(i=1;i<=n;i+)G->vexsi=(char)i;for(i=1;i<=n;i+)for(j=1;j<=n;j+)G->arcsij=Maxint;printf("输入%d条边的i,j及w:n",e);for(k=1;k<=e;k+)scanf("%d,%d,%d",&i,&j,&w);G->arcsij=w;printf("有向图建立完毕n");三停车场管理专业：软件工程 班级： 1227班 姓名： 张泽磊 学号： 2012005779 同组人：张泽磊 王晓春 闫瑞娟 组长：张泽磊 完成日期： 2014.6.25 一【问题描述】设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端）,若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。二【设计需求及分析】以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 3.栈和队列的定义（部分代码） typedef struct carqueue / 链队 LPTCARNODE lpHead; / 头结点 LPTCARNODE lpRear; / 指向当前队尾的指针 int nEffectiveSize; / 当前队中元素个数 TCARQUEUE, *LPTCARQUEUE; 4.栈和队列的初始化（部分代码） void InitQueue( LPTCARQUEUE &lpCarQueue ) lpCarQueue = ( LPTCARQUEUE ) malloc( sizeof( TCARQUEUE ) ); lpCarQueue->lpHead = ( LPTCARNODE) malloc( sizeof( TCARNODE ) ); lpCarQueue->lpHead->lpNext = NULL; lpCarQueue->lpRear = lpCarQueue->lpHead; lpCarQueue->nEffectiveSize = 0;void InitStack( LPTCARSTACK &lpCarStack, int nSize ) lpCarStack = ( LPTCARSTACK ) malloc( sizeof ( TCARSTACK ) ); lpCarStack->lpCarInformation = ( LPTCARINFORMATION ) malloc( nSize * sizeof ( TCARINFORMATION ) ); lpCarStack->nTop = -1; lpCarStack->nStackSize = nSize;-第 15 页-