1、 內(nèi)江師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告課題名稱： 文本文件單詞的檢索與計(jì)數(shù) 姓 名： 學(xué) 號(hào)： 專業(yè)班級(jí)： 軟 件 工 程 系 （院）： 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 設(shè)計(jì)時(shí)間： 20XX 年 X 月 X日 設(shè)計(jì)地點(diǎn)： 成 績(jī)： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 1 課程設(shè)計(jì)目的(1).訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識(shí)，編寫程序求解指定問題。 (2).初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；(3).提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；(4).訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，鞏固、深化學(xué)生

2、的理論知識(shí)，提高編程水平，并在此過程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。2 課程設(shè)計(jì)任務(wù)與要求：文本文件單詞的檢索與計(jì)數(shù)軟件任務(wù)：編寫一個(gè)文本文件單詞的檢索與計(jì)數(shù)軟件, 程序設(shè)計(jì)要求：1）建立文本文件，文件名由用戶鍵盤輸入2）給定單詞的計(jì)數(shù)，輸入一個(gè)不含空格的單詞，統(tǒng)計(jì)輸出該單詞在文本中的出現(xiàn)次數(shù)要求：(1)、在處理每個(gè)題目時(shí)，要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)類型、構(gòu)思算法、通過設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型、編制上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫出完整的分析報(bào)告。前期準(zhǔn)備工作完備與否直接影響到后序上機(jī)調(diào)試工作的效率。在程序設(shè)計(jì)階段應(yīng)盡量利用已有的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率。 (

3、2)、設(shè)計(jì)的題目要求達(dá)到一定工作量（300行以上代碼），并具有一定的深度和難度。(3)、程序設(shè)計(jì)語言推薦使用C/C+，程序書寫規(guī)范，源程序需加必要的注釋;(4)、每位同學(xué)需提交可獨(dú)立運(yùn)行的程序；(5)、每位同學(xué)需獨(dú)立提交設(shè)計(jì)報(bào)告書（每人一份），要求編排格式統(tǒng)一、規(guī)范、內(nèi)容充實(shí)，不少于8頁（代碼不算）； (6)、課程設(shè)計(jì)實(shí)踐作為培養(yǎng)學(xué)生動(dòng)手能力的一種手段，單獨(dú)考核。3 課程設(shè)計(jì)說明書一 需求分析3.1 串模式匹配算法的設(shè)計(jì)要求在串的基本操作中，在主串中查找模式串的模式匹配算法即求子串位置的函數(shù)Index(S,T)，是文本處理中最常用、最重要的操作之一。所謂子串的定位就是求子串在主串中首次出現(xiàn)的位

4、置，又稱為模式匹配或串匹配。模式匹配的算法很多，在這里只要求用最簡(jiǎn)單的樸素模式匹配算法。該算法的基本思路是將給定子串與主串從第一個(gè)字符開始比較，找到首次與子串完全匹配的子串為止，并記住該位置。但為了實(shí)現(xiàn)統(tǒng)計(jì)子串出現(xiàn)的個(gè)數(shù)，不僅需要從主串的第一個(gè)字符位置開始比較，而且需要從主串的任一給定位置檢索匹配字符串，所以，首先要給出兩個(gè)算法：1標(biāo)準(zhǔn)的樸素模式匹配算法2給定位置的匹配算法3.2 文本文件單詞的檢索與計(jì)數(shù)的設(shè)計(jì)要求要求編程建立一個(gè)文本文件，每個(gè)單詞不包含空格且不跨行，單詞由字符序列構(gòu)成且區(qū)分大小寫；統(tǒng)計(jì)給定單詞在文本文件中出現(xiàn)的總次數(shù)；檢索輸出某個(gè)單詞出現(xiàn)在文本中的行號(hào)、在該行中出現(xiàn)的次數(shù)以及

5、位置。該設(shè)計(jì)要求可分為三個(gè)部分實(shí)現(xiàn)：其一，建立文本文件，文件名由用戶用鍵盤輸入；其二，給定單詞的計(jì)數(shù)，輸入一個(gè)不含空格的單詞，統(tǒng)計(jì)輸出該單詞在文本中的出現(xiàn)次數(shù)；其三，檢索給定單詞，輸入一個(gè)單詞，檢索并輸出該單詞所在的行號(hào)、該行中出現(xiàn)的次數(shù)以及在該行中的相應(yīng)位置。1建立文本文件2給定單詞的計(jì)數(shù)3檢索單詞出現(xiàn)在文本文件中的行號(hào)、次數(shù)及其位置4主控菜單程序的結(jié)構(gòu)二 概要設(shè)計(jì)21建立文本文件 定義一個(gè)串變量 ，定義文本文件， 輸入文件名，打開該文件 ， 循環(huán)讀入文本行，寫入文本文件， 關(guān)閉文件 。22給定單詞的計(jì)數(shù) 逐行掃

6、描文本文件。匹配一個(gè)，計(jì)數(shù)器加1，直到整個(gè)文件掃描結(jié)束；然后輸出單詞的次數(shù) 23檢索單詞出現(xiàn)在文本文件中的行號(hào)、次數(shù)及其位置  逐行掃描文本文件。掃描一個(gè)單詞，單詞數(shù)加1，匹配一個(gè)，計(jì)數(shù)器加1，輸出該單詞數(shù)，行數(shù)到底 ，以此，行數(shù)加1，單詞數(shù)清零，直到整個(gè)文件掃描結(jié)束；然后輸出單詞的次數(shù)，行號(hào)，第幾個(gè)單詞。三 詳細(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）比較，若

7、相等，則繼續(xù)逐個(gè)比較后續(xù)字符（j+,k+）。否則從主串的下一個(gè)字符（i+）起再重新和模式串（j=0）的字符開始比較。依此類推，直到模式T中的所有字符都比較完，而且一直相等，則稱匹配成功，并返回位置i；否則返回-1，表示匹配失敗。順序串的模式匹配算法如下：int index(SString S, SString T) /求子串T在主串S中首次出現(xiàn)的位置int i,j,k,m,n;m=T.length; /模式串長(zhǎng)度賦mn=S.length; /目標(biāo)串長(zhǎng)度賦nfor (i=0; i<=n-m; i+) j=0; k=i; / 目標(biāo)串起始位置i送入k while (j<=m &&

8、amp; s.chk=t.chj) k+; j+; /繼續(xù)下一個(gè)字符的比較 if (j=m) /若相等，則說明找到匹配的子串，返回匹配位置i，/否則從下一個(gè)位置重新開始比較 return i; /endforreturn -1; /endIndex給定位置的串匹配算法該算法要求從串S1（為順序存儲(chǔ)結(jié)構(gòu)）中第k個(gè)字符起，求出首次與字符串S2相同的子串的起始位置。該算法與上面介紹的模式匹配算法類似，只不過上述算法的要求是從主串的第一個(gè)字符開始，該算法是上述算法的另一種思路：從第k個(gè)元素開始掃描S1，當(dāng)其元素值與S2的第一個(gè)元素的值相同時(shí)，判定它們之后的元素值是否依次相同，直到S2結(jié)束為止。若都相同

9、，則返回當(dāng)前位置值；否則繼續(xù)上述過程，直至S1掃描完為止，其實(shí)現(xiàn)算法如下：Int PartPosition(SString S1, SString S2, int k)int i, j;i=k-1; /掃描s1的下標(biāo)，因?yàn)閏中數(shù)組下標(biāo)是從0開始，串中序號(hào)相差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>=

10、s2.length) return i- s2.length; /表示s1中存在s2，返回其起始位置else return -1; /表示s1中不存在s2， 返回-1 /函數(shù)結(jié)束說明：以上兩個(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è)

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

12、；（3）行計(jì)數(shù)器置初值0；（4）while (不是文件結(jié)束) 讀入一行到指定串中； 求出串長(zhǎng)度； 行單詞計(jì)數(shù)器置0； 調(diào)用模式匹配函數(shù)匹配單詞定位、該行匹配單詞計(jì)數(shù)； 行號(hào)計(jì)數(shù)器加1； If (行單詞計(jì)數(shù)器!=0) 輸出行號(hào)、該行有匹配單詞的個(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)的操作，其他字符為非法。四 調(diào)試分析與測(cè)試結(jié)果4.1未輸入文件前的頁面4.2輸入文本文件 4.3文本單詞匯總4.4 單詞定位五 用戶手冊(cè)該軟件界面簡(jiǎn)潔，操作簡(jiǎn)單，運(yùn)行程序后根據(jù)提示就可完

13、成相關(guān)操作。六 附錄（源程序清單）#include <stdio.h>#include <stdlib.h>#include <string.h>#define LIST_INIT_SIZE 500 /*線性表存儲(chǔ)空間的初始分配量*/#define LISTINCREMENT 10 /*線性表存儲(chǔ)空間的分配增量*/#define FILE_NAME_LEN 20 /*文件名長(zhǎng)度*/#define WORD_LEN 20 /*單詞長(zhǎng)度*/#define MaxStrSize 256#define llength 110 /*規(guī)定一行有110個(gè)字節(jié)*/#defi

14、ne MaxStr 258#define WORD 21typedef struct char chMaxStr;/* ch是一個(gè)可容納256個(gè)字符的字符數(shù)組 */ int length; string;/* 定義順序串類型 */typedef struct char wordWORD; /*存儲(chǔ)單詞，不超過20個(gè)字符*/ int count; /*單詞出現(xiàn)的次數(shù)*/ elem_type;typedef struct elem_type *elem; /*存儲(chǔ)空間基址*/ int length; /*當(dāng)前長(zhǎng)度*/ int listsize; /*當(dāng)前分配的存儲(chǔ)容量*/ sqlist;int s

15、qlist_init(sqlist *sq, elem_type *et) sq->elem = et; sq->length = 0; return 0;int 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 (strcmp(eti.word, word) = 0) eti.count+; return 0; if (strcmp(eti.word, word) &

16、gt; 0) break; if (sq->length = LIST_INIT_SIZE) printf("空間不足，單詞%s插入失敗n", word); return 0; for (j = sq->length; j > i; j-) memcpy(et+j, et+j-1, sizeof(elem_type); sq->length+; strcpy(eti.word, word); eti.count = 1; return 0;int sqlist_count(sqlist *sq, elem_type *et) int i, j = 0

17、; for(i=0;i<sq->length;i+) j=j+eti.count; return j;int 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,"w"); yn='n'/* 輸入結(jié)束標(biāo)志初值 */ while(yn='n'|yn

18、='N') printf("請(qǐng)輸入一行文本："); 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);/* 關(guān)閉文件 */ printf("建立文件結(jié)束!n"); return 0;int substrsum() char

19、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("請(qǐng)輸入文件名："); scanf("%s", file_name); fp = fopen(file_name, "r"); if (fp = NULL) printf("打開文件失敗!n");

20、 return 0; while (fscanf(fp, "%s", word) != EOF) sqlist_add(&sq, et, word); fclose(fp); printf(">>>>>>>>>>>>>>>>單詞<<<>>>>個(gè)數(shù)<<<<<<<<<<<n"); for (i = 0; i < sq.length; i+) x

21、=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!=0) printf("%20s%10dn", eti.word, eti.count); el

22、se q+; j=sqlist_count(&sq, et); printf("n>>>>>>>>>>>>>>>>>>%s的單詞總數(shù)為%d個(gè)n",file_name,j); printf("n>>>>>>>>>>>>>>>>>>%s的非單詞個(gè)數(shù)為%d種n",file_name,q); printf("n"); re

23、turn 0;int partposition (string s1,string s2,int k) int i,j; i=k-1; /* 掃描s1的下標(biāo)，因?yàn)閏中數(shù)組下標(biāo)是從0開始，串中序號(hào)相差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.length) return i-s2.length; else return -1;/* 表示s1

24、中不存在s2，返回-1 */ /* 表示s1中存在s2，返回其起始位置 */ /* 函數(shù)結(jié)束 */ int 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ù)的單詞："); scanf("%s",t.ch); t.length=strlen(t.c

25、h); 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ù)下一字串的檢索 */ printf("n單詞%s在文本文件%s中共出現(xiàn)%d次n",t.c

26、h,fname,i);return 0;/* 統(tǒng)計(jì)單詞出現(xiàn)的個(gè)數(shù) */int 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("輸入要檢索的單詞："); scanf("%s",t.ch); t.le

27、ngth=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); /* 調(diào)用串匹配函數(shù) */ if(j<0) break; else i+;/*

28、 單詞計(jì)數(shù)器加1 */ wzi=j;/* 記錄匹配單詞位置 */ k=j+t.length;/* 繼續(xù)下一字串檢索 */ if(i>0) printf("行號(hào)：%d,次數(shù)：%d,起始位置分別為：",l,i); for(m=1;m<=i;m+) printf("第%4d個(gè)字符",wzm+1); printf("n"); printf("n本軟件自定義110個(gè)字節(jié)為一行nn"); return 0;/* 檢索單詞出現(xiàn)在文本文件中的行號(hào)、次數(shù)及其位置 */int substrio() int substrco

29、unt(),substrint(); char t; /while(1) / printf("=n"); printf("|文本文件單詞字串的定位統(tǒng)計(jì)及定位|n"); printf("|=|n"); printf("| a. 單詞出現(xiàn)次數(shù) |n"); printf("| |n"); printf("| |n"); printf("| b. 單詞出現(xiàn)位置 |n"); printf("| |n"); printf("=n"); printf("請(qǐng)輸入a或b:"); scanf("%c%*c",&t); switch(t) case 'a': substrcount();break; case 'b': substrint();break; default: return 0; / return 0;int main(void) int creat_text_file(),substrsum(),substr