文本文件單詞的檢索與計數(shù)

1、 程序設計課程設計 報 告 學 院：軟件學院 專業(yè)班級：軟件 班 學 號： 姓 名： 指導教師： 時 間： 2012年 6月29日文本文件單詞的檢索與計數(shù)專業(yè)：軟件工程 班級： 1.1【問題描述】串是非數(shù)值處理中的主要對象，如在信息檢索、文本編輯、符號處理等許多領域，得到越來越廣泛的應用。在高級語言中也引入了串數(shù)據類型概念，并且串變量與其他變量（如整型、實型等）一樣，可以進行各種運算。然而，在各種不同類型的應用中，所處理的串有不同的特點，要想有效地實現(xiàn)串的處理，就必須熟悉串的存儲結構及其基本運算。本課程設計的目的就是熟悉串類型的實現(xiàn)方法和文本模式匹配方法，熟悉如何利用模式匹配算法實現(xiàn)一般的文本

2、處理技術。本課程設計分兩步：首先，設計出串定位算法（即模式匹配算法）及其實現(xiàn)；然后，再利用串定位算法設計文本文件的檢索及單詞的計數(shù)等操作。1.2【設計需求及分析】1.2.1 串模式匹配算法的設計要求在串的基本操作中，在主串中查找模式串的模式匹配算法即求子串位置的函數(shù)Index(S,T)，是文本處理中最常用、最重要的操作之一。所謂子串的定位就是求子串在主串中首次出現(xiàn)的位置，又稱為模式匹配或串匹配。模式匹配的算法很多，在這里只要求用最簡單的樸素模式匹配算法。該算法的基本思路是將給定子串與主串從第一個字符開始比較，找到首次與子串完全匹配的子串為止，并記住該位置。但為了實現(xiàn)統(tǒng)計子串出現(xiàn)的個數(shù)，不僅需要

3、從主串的第一個字符位置開始比較，而且需要從主串的任一給定位置檢索匹配字符串，所以，首先要給出兩個算法：1標準的樸素模式匹配算法2給定位置的匹配算法1.2.2 文本文件單詞的檢索與計數(shù)的設計要求要求編程建立一個文本文件，每個單詞不包含空格且不跨行，單詞由字符序列構成且區(qū)分大小寫；統(tǒng)計給定單詞在文本文件中出現(xiàn)的總次數(shù)；檢索輸出某個單詞出現(xiàn)在文本中的行號、在該行中出現(xiàn)的次數(shù)以及位置。該設計要求可分為三個部分實現(xiàn)：其一，建立文本文件，文件名由用戶用鍵盤輸入；其二，給定單詞的計數(shù)，輸入一個不含空格的單詞，統(tǒng)計輸出該單詞在文本中的出現(xiàn)次數(shù)；其三，檢索給定單詞，輸入一個單詞，檢索并輸出該單詞所在的行號、該行

4、中出現(xiàn)的次數(shù)以及在該行中的相應位置。1建立文本文件2給定單詞的計數(shù)3檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置4主控菜單程序的結構3【設計功能的實現(xiàn)】（用C或C+語言描述）詳細設計樸素模式匹配算法該算法的基本思想是：設有三個指針i,j,k，用i指示主串S每次開始比較的位置；指針j,k分別指示主串S和模式串T中當前正在等待比較的字符位置；一開始從主串S的第一個字符（i=0;j=1）和模式T的第一個字符（k=0）比較，若相等，則繼續(xù)逐個比較后續(xù)字符（j+,k+）。否則從主串的下一個字符（i+）起再重新和模式串（j=0）的字符開始比較。依此類推，直到模式T中的所有字符都比較完，而且一直相等，則稱匹

5、配成功，并返回位置i；否則返回-1，表示匹配失敗。順序串的模式匹配算法如下：int index(SString S, SString T) /求子串T在主串S中首次出現(xiàn)的位置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+; /繼續(xù)下一個字符的比較 if (j=m) /若相等，則說明找到匹配的子串，返回匹配位置i，/否則從下一個位置重新開始比較 re

6、turn i; /endforreturn -1; /endIndex給定位置的串匹配算法該算法要求從串S1（為順序存儲結構）中第k個字符起，求出首次與字符串S2相同的子串的起始位置。該算法與上面介紹的模式匹配算法類似，只不過上述算法的要求是從主串的第一個字符開始，該算法是上述算法的另一種思路：從第k個元素開始掃描S1，當其元素值與S2的第一個元素的值相同時，判定它們之后的元素值是否依次相同，直到S2結束為止。若都相同，則返回當前位置值；否則繼續(xù)上述過程，直至S1掃描完為止，其實現(xiàn)算法如下：Int PartPosition(SString S1, SString S2, int k)int i

7、, j;i=k-1; /掃描s1的下標，因為c中數(shù)組下標是從0開始，串中序號相差1j=0; /掃描s2的開始下標while (i<s1.length && j<s2.length)if (s1.chi=s2.chj) i+; j+; /繼續(xù)使下標移向下一個字符位置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 /函數(shù)結束

8、說明：以上兩個算法可統(tǒng)一為一個算法，即在子串定位算法Index(S,T)的參數(shù)中增加一個起始位置參數(shù)即可。建立文本文件建立文件的實現(xiàn)思路是：（1）定義一個串變量；（2）定義文本文件；（3）輸入文件名，打開該文件；（4）循環(huán)讀入文本行，寫入文本文件，其過程如下： While ( 不是文件輸入結束) 讀入一文本行至串變量；串變量寫入文件；輸入是否結束輸入標志；（5）關閉文件。給定單詞的計數(shù)該功能需要用到前一節(jié)中設計的模式匹配算法，逐行掃描文本文件。匹配一個，計數(shù)器加1，直到整個文件掃描結束；然后輸出單詞出現(xiàn)的次數(shù)。其實現(xiàn)過程如下：（1）輸入要檢索的文本文件名，打開相應的文件；（2）輸入要

9、檢索統(tǒng)計的單詞；（3）循環(huán)讀文本文件，讀入一行，將其送入定義好的串中，并求該串的實際長度，調用串匹配函數(shù)進行計數(shù)。具體描述如下：While (不是文件結束) 讀入一行并到串中； 求出串長度； 模式匹配函數(shù)計數(shù)；（4）關閉文件，輸出統(tǒng)計結果。 檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置這個設計要求與上一個類似，但要相對復雜一些。其實現(xiàn)過程描述如下：（1）輸入要檢索的文本文件名，打開相應的文件；（2）輸入要檢索統(tǒng)計的單詞；（3）行計數(shù)器置初值0；（4）while (不是文件結束) 讀入一行到指定串中； 求出串長度； 行單詞計數(shù)器置0； 調用模式匹配函數(shù)匹配單詞定位、該行匹配單詞計數(shù)； 行號計數(shù)器

10、加1； If (行單詞計數(shù)器!=0) 輸出行號、該行有匹配單詞的個數(shù)以及相應的位置；運行主控程序主控菜單程序的結構要求內容如下：（1）頭文件包含；（2）菜單選項包括： 1建立文件 2單詞計數(shù) 3單詞定位 4退出程序（3）選擇14執(zhí)行相應的操作，其他字符為非法。程序代碼：#include <stdio.h>#include <stdlib.h>#include <string.h>#define LIST_INIT_SIZE 500 /*線性表存儲空間的初始分配量*/#define LISTINCREMENT 10 /*線性表存儲空間的分配增量*/#defin

11、e FILE_NAME_LEN 20 /*文件名長度*/#define WORD_LEN 20 /*單詞長度*/#define MaxStrSize 256#define llength 110 /*規(guī)定一行有110個字節(jié)*/typedef struct char chMaxStr; /* ch是一個可容納256個字符的字符數(shù)組 */ int length; string;/* 定義順序串類型 */typedef struct char wordWORD; /*存儲單詞，不超過20個字符*/ int count; /*單詞出現(xiàn)的次數(shù)*/ elem_type;typedef struct ele

12、m_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+) /*當前單詞與加入的單詞相同，直接統(tǒng)計，不做插入 */ if (

13、strcmp(eti.word, word) = 0) eti.count+; return ; if (strcmp(eti.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(eti.word, word); eti.c

14、ount = 1;int sqlist_count(sqlist *sq, elem_type *et) int i; int j=0; for(i=0;i<sq->length;i+) j=j+eti.count; return j;void creat_text_file() elem_type w; sqlist s; char file_nameFILE_NAME_LEN + 1,yn; FILE *fp; printf("輸入要建立的文件名："); scanf("%s",file_name); fp=fopen(file_name,

15、"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);/*

16、關閉文件 */ printf("建立文件結束!n"); void substrsum() char file_nameFILE_NAME_LEN + 1; char wordWORD_LEN+1; FILE *fp; int i; int j,q=0; int w,x,y=0; elem_type etLIST_INIT_SIZE; sqlist sq; sqlist_init(&sq, et); printf("請輸入文件名："); scanf("%s", file_name); fp = fopen(file_name,

17、"r"); if (fp = NULL) printf("打開文件失敗!n"); return; while (fscanf(fp, "%s", word) != EOF) sqlist_add(&sq, et, word); fclose(fp); printf(">>>>>>>>>>>>>>>>單詞<<<>>>>個數(shù)<<<<<<<<

18、;<<<n"); for (i = 0; i < sq.length; i+) x=strlen(eti.word); for(w=x-1;w>=0;w-) if(eti.wordw<65|(eti.wordw>90&&eti.wordw<97)|eti.wordw>122) eti.wordw=' ' for(w=0;w<x;w+) if (eti.wordw=' ') y+; if(y=x) eti.count=0; y=0; else y=0; if(eti.count!

19、=0) printf("%20s%10dn", eti.word, eti.count); else q+; j=sqlist_count(&sq, et); printf("n>>>>>>>>>>>>>>>>>>%s的單詞總數(shù)為%d個n",file_name,j); printf("n>>>>>>>>>>>>>>>>>>%

20、s的非單詞個數(shù)為%d種n",file_name,q); printf("n"); int partposition (string s1,string s2,int k) int i,j; i=k-1; /* 掃描s1的下標，因為c中數(shù)組下標是從0開始，串中序號相差1 */ j=0;/* 掃描s2的開始下標 */ while(i<s1.length && j<s2.length) if(s1.chi=s2.chj) i+;j+; /* 繼續(xù)使下標移向下一個字符位置 */ else i=i-j+1; j=0; if (j>=s2.l

21、ength) return i-s2.length; else return -1;/* 表示s1中不存在s2，返回-1 */ /* 表示s1中存在s2，返回其起始位置 */ /* 函數(shù)結束 */ void substrcount() FILE *fp; string s,t;/* 定義兩個串變量 */ char fname10; int i=0,j,k; printf("輸入文本文件名："); scanf("%s",fname); fp=fopen(fname,"r"); printf("輸入要統(tǒng)計計數(shù)的單詞："

22、); scanf("%s",t.ch); t.length=strlen(t.ch); while(!feof(fp) memset(s.ch,'0',110); fgets(s.ch,110,fp); s.length=strlen(s.ch); k=0; /* 初始化開始檢索位置 */ while(k<s.length-1) /* 檢索整個主串S */ j=partposition(s,t,k);/* 調用串匹配函數(shù) */ if(j<0 ) break; else i+;/* 單詞計數(shù)器加1 */ k=j+t.length;/* 繼續(xù)下一字串

23、的檢索 */ printf("n單詞%s在文本文件%s中共出現(xiàn)%d次n",t.ch,fname,i); /* 統(tǒng)計單詞出現(xiàn)的個數(shù) */ void substrint() FILE *fp; string s,t; /* 定義兩個串變量 */ char fname10; int i,j,k,l,m; int wz20; /* 存放一行中字串匹配的多個位置 */ printf("輸入文本文件名："); scanf("%s",fname); fp=fopen(fname,"r"); printf("輸入要檢索的

24、單詞："); scanf("%s",t.ch); t.length=strlen(t.ch); l=0; /* 行計數(shù)器置0 */ while(!feof(fp) /* 掃描整個文本文件 */ memset(s.ch,'0',110); fgets(s.ch,110,fp); s.length=strlen(s.ch); l+; /* 行計數(shù)器自增1 */ k=0;/* 初始化開始檢索位置 */ i=0; /* 初始化單詞計數(shù)器 */ while(k<s.length-1) /* 檢索整個主串S */ j=partposition(s,t,k

25、); /* 調用串匹配函數(shù) */ if(j<0) break; else i+;/* 單詞計數(shù)器加1 */ wzi=j;/* 記錄匹配單詞位置 */ k=j+t.length;/* 繼續(xù)下一字串檢索 */ if(i>0) printf("行號：%d,次數(shù)：%d,位置分別為：",l,i); for(m=1;m<=i;m+) printf("第%4d個字符",wzm+1); printf("n"); printf("n本軟件自定義110個字節(jié)為一行nn");/* 檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置 */void substrio() void substrcount(),substrint(); char t; while(1) printf("=n"); printf("|文本文件單詞字串的定位統(tǒng)計及定位|n"); printf("|=|n"); printf("| a. 單詞出現(xiàn)次數(shù) |n"); printf("|