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

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

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

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

4、中出現(xiàn)的次數(shù)以及在該行中的相應(yīng)位置。1建立文本文件2給定單詞的計(jì)數(shù)3檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置4主控菜單程序的結(jié)構(gòu)3【設(shè)計(jì)功能的實(shí)現(xiàn)】（用C或C+語言描述）詳細(xì)設(shè)計(jì)樸素模式匹配算法該算法的基本思想是：設(shè)有三個(gè)指針i,j,k，用i指示主串S每次開始比較的位置；指針j,k分別指示主串S和模式串T中當(dāng)前正在等待比較的字符位置；一開始從主串S的第一個(gè)字符（i=0;j=1）和模式T的第一個(gè)字符（k=0）比較，若相等，則繼續(xù)逐個(gè)比較后續(xù)字符（j+,k+）。否則從主串的下一個(gè)字符（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; /目標(biāo)串長度賦nfor (i=0; i<=n-m; i+) j=0; k=i; / 目標(biāo)串起始位置i送入k while (j<=m && s.chk=t.chj) k+; j+; /繼續(xù)下一個(gè)字符的比較 if (j=m) /若相等，則說明找到匹配的子串，返回匹配位置i，/否則從下一個(gè)位置重新開始比較 re

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

7、, j;i=k-1; /掃描s1的下標(biāo)，因?yàn)閏中數(shù)組下標(biāo)是從0開始，串中序號相差1j=0; /掃描s2的開始下標(biāo)while (i<s1.length && j<s2.length)if (s1.chi=s2.chj) i+; j+; /繼續(xù)使下標(biāo)移向下一個(gè)字符位置else i=i-j+1; j=0; /使i下標(biāo)回溯到原位置的下一個(gè)位置，使j指向s2的第一個(gè)字符，再重新比較if (j>=s2.length) return i- s2.length; /表示s1中存在s2，返回其起始位置else return -1; /表示s1中不存在s2， 返回-1 /函數(shù)結(jié)束

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

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

10、加1； If (行單詞計(jì)數(shù)器!=0) 輸出行號、該行有匹配單詞的個(gè)數(shù)以及相應(yīng)的位置；運(yùn)行主控程序主控菜單程序的結(jié)構(gòu)要求內(nèi)容如下：（1）頭文件包含；（2）菜單選項(xiàng)包括： 1建立文件 2單詞計(jì)數(shù) 3單詞定位 4退出程序（3）選擇14執(zhí)行相應(yīng)的操作，其他字符為非法。程序代碼：#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個(gè)字節(jié)*/typedef struct char chMaxStr; /* ch是一個(gè)可容納256個(gè)字符的字符數(shù)組 */ int length; string;/* 定義順序串類型 */typedef struct char wordWORD; /*存儲單詞，不超過20個(gè)字符*/ int count; /*單詞出現(xiàn)的次數(shù)*/ elem_type;typedef struct ele

12、m_type *elem; /*存儲空間基址*/ int length; /*當(dāng)前長度*/ int listsize; /*當(dāng)前分配的存儲容量*/ 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+) /*當(dāng)前單詞與加入的單詞相同，直接統(tǒng)計(jì)，不做插入 */ 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'/* 輸入結(jié)束標(biāo)志初值 */ 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("結(jié)束輸入嗎？y or n ：");yn=getchar(); fclose(fp);/*

16、關(guān)閉文件 */ printf("建立文件結(jié)束!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(">>>>>>>>>>>>>>>>單詞<<<>>>>個(gè)數(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個(gè)n",file_name,j); printf("n>>>>>>>>>>>>>>>>>>%

20、s的非單詞個(gè)數(shù)為%d種n",file_name,q); printf("n"); int partposition (string s1,string s2,int k) int i,j; i=k-1; /* 掃描s1的下標(biāo)，因?yàn)閏中數(shù)組下標(biāo)是從0開始，串中序號相差1 */ j=0;/* 掃描s2的開始下標(biāo) */ while(i<s1.length && j<s2.length) if(s1.chi=s2.chj) i+;j+; /* 繼續(xù)使下標(biāo)移向下一個(gè)字符位置 */ 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ù)結(jié)束 */ void substrcount() FILE *fp; string s,t;/* 定義兩個(gè)串變量 */ char fname10; int i=0,j,k; printf("輸入文本文件名："); scanf("%s",fname); fp=fopen(fname,"r"); printf("輸入要統(tǒng)計(jì)計(jì)數(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) /* 檢索整個(gè)主串S */ j=partposition(s,t,k);/* 調(diào)用串匹配函數(shù) */ if(j<0 ) break; else i+;/* 單詞計(jì)數(shù)器加1 */ k=j+t.length;/* 繼續(xù)下一字串

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

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

25、); /* 調(diào)用串匹配函數(shù) */ if(j<0) break; else i+;/* 單詞計(jì)數(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個(gè)字符",wzm+1); printf("n"); printf("n本軟件自定義110個(gè)字節(jié)為一行nn");/* 檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置 */void substrio() void substrcount(),substrint(); char t; while(1) printf("=n"); printf("|文本文件單詞字串的定位統(tǒng)計(jì)及定位|n"); printf("|=|n"); printf("| a. 單詞出現(xiàn)次數(shù) |n"); printf("|