太原理工大学软件工程课程设计实验.pdf

文本文件单词的检索与计数文本文件单词的检索与计数 专业：软件工程班级： 1227 班姓名： 王晓春学号： 2012005774 同组人：王晓春 闫瑞娟 张泽磊组长：王晓春完成日期： 2014.6.25 一一 【问题描述】【问题描述】 串是非数值处理中的主要对象，如在信息检索、文本编辑、符号处理等许多 领域，得到越来越广泛的应用。在高级语言中也引入了串数据类型概念，并且串 变量与其他变量（如整型、实型等）一样，可以进行各种运算。 然而，在各种不同类型的应用中，所处理的串有不同的特点，要想有效地实 现串的处理，就必须熟悉串的存储结构及其基本运算。本课程设计的目的就是熟 悉串类型的实现方法和文本模式匹配方法， 熟悉如何利用模式匹配算法实现一般 的文本处理技术。 本课程设计分两步：首先，设计出串定位算法（即模式匹配算法）及其实现； 然后，再利用串定位算法设计文本文件的检索及单词的计数等操作。 二二 【设计需求及分析】【设计需求及分析】 1.1.设计要求设计要求 1.1 串模式匹配算法的设计要求串模式匹配算法的设计要求 在串的基本操作中，在主串中查找模式串的模式匹配算法即求子串位置 的函数 Index(S,T)，是文本处理中最常用、最重要的操作之一。 所谓子串的定位就是求子串在主串中首次出现的位置，又称为模式匹配或串 匹配。模式匹配的算法很多，在这里只要求用最简单的朴素模式匹配算法。该算 法的基本思路是将给定子串与主串从第一个字符开始比较， 找到首次与子串完全 匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从 主串的第一个字符位置开始比较， 而且需要从主串的任一给定位置检索匹配字符 串，所以，首先要给出两个算法： 1标准的朴素模式匹配算法 2给定位置的匹配算法 1.21.2 文本文件单词的检索与计数的设计要求文本文件单词的检索与计数的设计要求 要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序 列构成且区分大小写；统计给定单词在文本文件中出现的总次数；检索输出某个 单词出现在文本中的行号、在该行中出现的次数以及位置。 该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键 盘输入；其二，给定单词的计数，输入一个不含空格的单词，统计输出该单词在 文本中的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所 在的行号、该行中出现的次数以及在该行中的相应位置。 1建立文本文件 2给定单词的计数 3检索单词出现在文本文件中的行号、次数及其位置 4主控菜单程序的结构 2.2.概要设计示例如下：概要设计示例如下： 2.62.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;/模式串长度赋 m n=S.length;/目标串长度赋 n for (i=0; i=n-m;i+) j=0; k=i;/ 目标串起始位置 i 送入 k while (j=mj+;/继续下一个字符的比较 if (j=m)/若相等，则说明找到匹配的子串，返回匹配位置 i， /否则从下一个位置重新开始比较 return i; /endfor return -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 开始，串中序号相差 1 j=0;/扫描 s2 的开始下标 while (is1.length/表示 s1 中存在 s2，返回其起始位置 else return -1;/表示 s1 中不存在 s2， 返回-1 /函数结束 说明： 以上两个算法可统一为一个算法， 即在子串定位算法 Index(S,T)的参 数中增加一个起始位置参数即可。 2.72.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.82.8 函数调用关系函数调用关系 主程序 CreatTextFile() SubStrCount()SubStrInd() PartPosition() 三三 【设计功能的实现】【设计功能的实现】 #include stdafx.h #include #include #define MaxStrSize 256/根据用户需要自己定义大小 typedef struct char chMaxStrSize; /ch 是一个可容纳 256 个字符的字符数组 int length; SString; /定义顺序串类型 int PartPosition(SString s1, SString s2, int k) /检索单词出现在文本文件中的位置 int i, j; i=k-1;/扫描 s1 的下标，因为 c 中数组下标是从 0 开始，串中序号相差 1 j=0;/扫描 s2 的开始下标 while (is1.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( 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(/读入一行文本 memset(S.ch,0, 256); fgets(S.ch,100,fp); S.length=strlen(S.ch); k=0;/初始化开始检索位置 while(kS.length-1)/检索整个主串 S j=PartPosition(S,T,k); if(j0) break; else i+;/单词计数器加 1 k=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(/读入一行文本 memset(S.ch,0, 256); fgets(S.ch,256,fp); S.length=strlen(S.ch); l+; k=0;/从串 T 的扫描初始位置默认为数组第一位，可根据用户要求 改变 k 值，成为给定位置的串匹配算法 i=0; while(kS.length-1) j=PartPosition(S,T,k); if(j0) printf(行号：%d , 次数：%d, 位置分别为：,l, i); for(m=1;m=i;m+) printf(%4d, wzm+1); printf(n); int main() void CreatTextFlie(), SubStrInd(); int xz;/操作号 do printf(*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, switch(xz) case 1:CreatTextFile(); break; case 2:SubStrCount(); break; case 3:SubStrInd(); break; case 4:return 0; default: printf(选择错误，重新选n); while(1); 四四 【实例测试及运行结果】【实例测试及运行结果】 运行实例一： 未输入文件前的页面 输入文本文件，计数单词出现的次数 检索某单词的行号，出现次数，以及位置 运行实例二： 未输入文件前的页面 输入文本文件，计数单词出现的次数 检索某单词的行号，出现次数，以及位置 5 5课程总结课程总结 在此次的实验过程中，我对结构化的编程思想有了更深刻的理解。在实验中，遇 到过很多问题，比如对抽象数据结构线性表的实现方法不熟悉，对数组定义模糊 等，后来经过思考并查阅资料解决了问题，使自己养成了独立思考、独立解决问 题的能力。通过这次设计，我学会了和别人配合工作，因为一个人所学的知识不 可能面面俱到的，只有通过合作，发挥自己的优点，体现团队精神，才能使工作 做得更为出色。 通过这次设计，我学到了许多书本上学不到的知识，增强了自己的动手能 力。计算机技术的高速发展，使我深深地认识到只有不断的加强学习，才能在计 算机技术方面不至于被淘汰，今后，我还要加强学习，努力使自己成为一位专业 的计算机人员，为我自己所从事的工作服务。 二交通咨询系统设计 专业：软件工程班级： 1227 班姓名： 闫瑞娟学号： 2012005779 同组人：张泽磊 王晓春 闫瑞娟组长：张泽磊完成日期： 2014.6.25 一、一、问题描述问题描述 在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他 出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一 个人们关心的问题， 可用一个图结构来表示交通网络系统， 利用计算机建立一个交通咨询系 统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提 出的各种路径选择问题。例如，问题之一：“一位旅客要从 A 城到 B 城，他希望选择一条途 中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找 一条从顶点 A 到顶点 B 的所含边数目最少的路径。我们只需要从顶点 A 出发对图作广度优 先搜索，一旦遇到顶点 B 就终止。由此所得广度优先生成树上，从根顶点 A 到顶点 B 的路 径就是中转次数最少的路径。路径上 A 与 B 之间的顶点就是路径的中转站，但这只是一类 最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。 设计一个交通咨询系统， 为出差、 旅游或做其他出行的客人提供各种路径选择信息查询 服务。 二、二、设计需求及分析设计需求及分析 设计一个交通咨询系统， 能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路 径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所 需时间或所需费用。 本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三 是实现任两个城市顶点之间的最短路径问题。 3.2.1 建立图的存储结构建立图的存储结构 邻接矩阵是表示图形中顶点之间相邻关系的矩阵。 图的邻接矩阵是定义如下的 n 阶方阵： 设 G=（V，E）是一个图，结点集为 n vvvV, 21 。 G 的邻接矩阵, E,0 E,)( ,)( jiji jijinnji ijnnij vvvv vvvvw aaA ）或当（，或 ）或当（， 当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。 图的邻接矩阵表示， 除了需用一个二维数组存储顶点之间的相邻关系