logo资料库

文本文件单词的检索与计数.doc

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.22M 资料格式：doc 举报 版权申诉
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
资料共12页，剩余部分请下载后查看
    1.1【问题描述】
    1.2【设计需求及分析】
    1.2.1 串模式匹配算法的设计要求
    1.2.2 文本文件单词的检索与计数的设计要求
    给定位置的串匹配算法
    程序设计课程设计 报 告 学 院：软件学院 专业班级：软件 班 学 姓 号： 名： 指导教师： 时 间： 2012 年 6 月 29 日 文本文件单词的检索与计数 专业：软件工程 班级： 1015 班 姓名： 李超 学号：2010004812 完成日期：2012/6/22
    1.1【问题描述】 串是非数值处理中的主要对象，如在信息检索、文本编辑、符号处理等许多领域，得到 越来越广泛的应用。在高级语言中也引入了串数据类型概念，并且串变量与其他变量（如整 型、实型等）一样，可以进行各种运算。 然而，在各种不同类型的应用中，所处理的串有不同的特点，要想有效地实现串的处理， 就必须熟悉串的存储结构及其基本运算。本课程设计的目的就是熟悉串类型的实现方法和文 本模式匹配方法，熟悉如何利用模式匹配算法实现一般的文本处理技术。 本课程设计分两步：首先，设计出串定位算法（即模式匹配算法）及其实现；然后，再 利用串定位算法设计文本文件的检索及单词的计数等操作。 1.2【设计需求及分析】 1.2.1 串模式匹配算法的设计要求 在串的基本操作中，在主串中查找模式串的模式匹配算法——即求子串位置的函数 Index(S,T)，是文本处理中最常用、最重要的操作之一。 所谓子串的定位就是求子串在主串中首次出现的位置，又称为模式匹配或串匹配。模 式匹配的算法很多，在这里只要求用最简单的朴素模式匹配算法。该算法的基本思路是将给 定子串与主串从第一个字符开始比较，找到首次与子串完全匹配的子串为止，并记住该位置。 但为了实现统计子串出现的个数，不仅需要从主串的第一个字符位置开始比较，而且需要从 主串的任一给定位置检索匹配字符串，所以，首先要给出两个算法： 1．标准的朴素模式匹配算法 2．给定位置的匹配算法 1.2.2 文本文件单词的检索与计数的设计要求 要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区 分大小写；统计给定单词在文本文件中出现的总次数；检索输出某个单词出现在文本中的行 号、在该行中出现的次数以及位置。 该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其 二，给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其 三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及 在该行中的相应位置。 1．建立文本文件 2．给定单词的计数 3．检索单词出现在文本文件中的行号、次数及其位置 4．主控菜单程序的结构 3【设计功能的实现】（用 C 或 C++语言描述） 详细设计 朴素模式匹配算法 该算法的基本思想是：设有三个指针——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; n=S.length; for (i=0; i<=n-m; //模式串长度赋 m //目标串长度赋 n i++) { j=0; k=i; while (j<=m && s.ch[k]==t.ch[j]) // 目标串起始位置 i 送入 k {k++; if (j==m) return i; //继续下一个字符的比较 j++;} //若相等，则说明找到匹配的子串，返回匹配位置 i， //否则从下一个位置重新开始比较 } //endfor return -1; } //endIndex 给定位置的串匹配算法 该算法要求从串 S1（为顺序存储结构）中第 k 个字符起，求出首次与字符串 S2 相同的 子串的起始位置。 该算法与上面介绍的模式匹配算法类似，只不过上述算法的要求是从主串的第一个字 符开始，该算法是上述算法的另一种思路：从第 k 个元素开始扫描 S1，当其元素值与 S2 的 第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到 S2 结束为止。若都相 同，则返回当前位置值；否则继续上述过程，直至 S1 扫描完为止，其实现算法如下： Int PartPosition(SString S1, SString S2, int k) { //扫描 s1 的下标，因为 c 中数组下标是从 0 开始，串中序号相差 1 //扫描 s2 的开始下标 int i, j; i=k-1; j=0; while (i=s2.length) return i- s2.length; //表示 s1 中存在 s2，返回其起始位置
    else return -1; //表示 s1 中不存在 s2， 返回-1 } //函数结束 说明：以上两个算法可统一为一个算法，即在子串定位算法 Index(S,T)的参数中增加一 个起始位置参数即可。 建立文本文件 建立文件的实现思路是： （1）定义一个串变量； （2）定义文本文件； （3）输入文件名，打开该文件； （4）循环读入文本行，写入文本文件，其过程如下： While ( 不是文件输入结束) { 读入一文本行至串变量； 串变量写入文件； 输入是否结束输入标志； } （5）关闭文件。 给定单词的计数 该功能需要用到前一节中设计的模式匹配算法，逐行扫描文本文件。匹配一个，计数器 加 1，直到整个文件扫描结束；然后输出单词出现的次数。 其实现过程如下： （1）输入要检索的文本文件名，打开相应的文件； （2）输入要检索统计的单词； （3）循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实际长度，调 用串匹配函数进行计数。具体描述如下： While (不是文件结束) { 读入一行并到串中； 求出串长度； 模式匹配函数计数； } （4）关闭文件，输出统计结果。 检索单词出现在文本文件中的行号、次数及其位置 这个设计要求与上一个类似，但要相对复杂一些。其实现过程描述如下： （1）输入要检索的文本文件名，打开相应的文件； （2）输入要检索统计的单词； （3）行计数器置初值 0； （4）while (不是文件结束) { 读入一行到指定串中；
    求出串长度； 行单词计数器置 0； 调用模式匹配函数匹配单词定位、该行匹配单词计数； 行号计数器加 1； If (行单词计数器!=0) 输出行号、该行有匹配单词的个数以及相应的位置； } 运行主控程序 主控菜单程序的结构要求内容如下： （1）头文件包含； （2）菜单选项包括： 1．建立文件 2．单词计数 3．单词定位 4．退出程序 （3）选择 1——4 执行相应的操作，其他字符为非法。 程序代码： #include #include #include #define LIST_INIT_SIZE 500 /*线性表存储空间的初始分配量*/ #define LISTINCREMENT 10 /*线性表存储空间的分配增量*/ #define FILE_NAME_LEN 20 #define WORD_LEN 20 #define MaxStrSize #define llength 110 /*文件名长度*/ /*单词长度*/ 256 /*规定一行有 110 个字节*/ typedef struct { char ch[MaxStr]; /* ch 是一个可容纳 256 个字符的字符数组 */ int length; } string;/* 定义顺序串类型 */ typedef struct { char word[WORD]; int count; /*存储单词，不超过 20 个字符*/ /*单词出现的次数*/ } elem_type; typedef struct{ elem_type *elem; int length; int listsize; /*存储空间基址*/ /*当前长度*/ /*当前分配的存储容量*/
    } sqlist; void sqlist_init(sqlist *sq, elem_type *et){ sq->elem = et; sq->length = 0; } void sqlist_add(sqlist *sq, elem_type *et, char *word) { int i; int j; for (i = 0; i < sq->length; i++) { /*当前单词与加入的单词相同，直接统计，不做插入 */ if (strcmp(et[i].word, word) == 0) { et[i].count++; return ; } if (strcmp(et[i].word, word) > 0) { break; } } if (sq->length == LIST_INIT_SIZE) { printf("空间不足，单词[%s]插入失败\n", word); return; } for (j = sq->length; j > i; j--) { memcpy(et+j, et+j-1, sizeof(elem_type)); } sq->length++; strcpy(et[i].word, word); et[i].count = 1; } int sqlist_count(sqlist *sq, elem_type *et) { int i; int j=0; for(i=0;ilength;i++)
    j=j+et[i].count; return j; } void creat_text_file() { elem_type w; sqlist s; char file_name[FILE_NAME_LEN + 1],yn; FILE *fp; printf("输入要建立的文件名："); scanf("%s",file_name); fp=fopen(file_name,"w"); yn='n';/* 输入结束标志初值 */ while(yn=='n'||yn=='N') { printf("请输入一行文本："); gets(w.word); gets(w.word); s.length=strlen(w.word); fwrite(&w,s.length,1,fp); fprintf(fp,"%c",10);/* 是输入换行 */ printf("结束输入吗？y or n ：");yn=getchar(); } fclose(fp);/* 关闭文件 */ printf("建立文件结束!\n"); } void substrsum() { char file_name[FILE_NAME_LEN + 1]; char word[WORD_LEN+1]; FILE *fp; int i; int j,q=0; int w,x,y=0; elem_type et[LIST_INIT_SIZE]; sqlist sq; sqlist_init(&sq, et); printf("请输入文件名："); scanf("%s", file_name);
    fp = fopen(file_name, "r"); if (fp == NULL){ printf("打开文件失败!\n"); return; } while (fscanf(fp, "%s", word) != EOF){ sqlist_add(&sq, et, word); } fclose(fp); printf(">>>>>>>>>>>>>>>>单词<<<>>>>个数<<<<<<<<<<<\n"); for (i = 0; i < sq.length; i++) { x=strlen(et[i].word); for(w=x-1;w>=0;w--) if(et[i].word[w]<65||(et[i].word[w]>90&&et[i].word[w]<97)||et[i].word[w]>122) { et[i].word[w]=' '; } for(w=0;w>>>>>>>>>>>>>>>>>%s 的单词总数为%d 个\n",file_name,j); printf("\n>>>>>>>>>>>>>>>>>>%s 的非单词个数为%d 种\n",file_name,q); printf("\n"); } int partposition (string s1,string s2,int k) { int i,j; i=k-1; /* 扫描 s1 的下标，因为 c 中数组下标是从 0 开始，串中序号相差 1 */ j=0;/* 扫描 s2 的开始下标 */
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料