數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告書題 目： 文本文件單詞的檢索與計數(shù) 專 業(yè)：網(wǎng)絡(luò)工程學(xué) 號：7學(xué)生姓名：張欽昆指導(dǎo)教師：王初陽完成日期：2014/6/7目錄1 設(shè)計任務(wù)書錯誤!未定義書簽題目與要求錯誤!未定義書簽知識點(diǎn) 2輸入輸出分析 2.測試數(shù)據(jù)分析 2.2 概要設(shè)計錯誤!未定義書簽結(jié)構(gòu)體類型及函數(shù)聲明錯誤!未定義書簽主程序流程 3模塊流程說明 4.3 詳細(xì)設(shè)計 8數(shù)據(jù)類型實(shí)現(xiàn) 8.程序代碼 1 04 調(diào)試分析 1 7問題分析與回顧 1 7算法時空分析錯 誤!未定義書簽算法改進(jìn)錯誤!未定義書簽經(jīng)驗(yàn)和體會錯誤!未定義書簽。5 測試結(jié)果參考文獻(xiàn) 評分標(biāo)準(zhǔn) 錯誤!未定義書簽。.2 5241 設(shè)計任務(wù)書題目與

2、要求題目：文本文件單詞的檢索與計數(shù)。要求：編程建立一個文本文件， 每個單詞不包含空格且不跨行， 單詞由字符序列構(gòu) 成且區(qū)分大小寫； 統(tǒng)計給定單詞在文本文件中出現(xiàn)的總次數(shù)； 檢索輸出某個單詞出現(xiàn)在 文本中的行號、 在該行中出現(xiàn)的次數(shù)以及位置。 建立文本文件， 文件名由用戶用鍵盤輸 入；給定單詞的計數(shù)， 輸入一個不含空格的單詞， 統(tǒng)計輸出該單詞在文本中的出現(xiàn)次數(shù)； 檢索給定單詞， 輸入一個單詞， 檢索并輸出該單詞所在的行號、 該行中出現(xiàn)的次數(shù)以及 在該行中的相應(yīng)位置。知識點(diǎn)串的應(yīng)用、文件、結(jié)構(gòu)體、指針、數(shù)組、函數(shù)、函數(shù)的調(diào)用、循環(huán)語句、選擇語 句、輸入輸出控制、自定義類型等。輸入輸出分析（1）普通

3、輸入在文本文件的建立中， 需要先定義串變量和文本文件， 從而建立文本文件； 根據(jù)實(shí) 際情況，將單詞的長度定義為 20，規(guī)定每行最多輸入 110 個字符。（2）對話式輸入為便于轉(zhuǎn)換及比較，對話式輸入采用字符數(shù)組進(jìn)行存儲 .為保障程序的健壯性，同 時限制對話式輸入的格式，對于非法的會話式輸入則提示用戶操作失敗的原因。（3）程序輸出 為了能讓程序輸出時更加美觀，程序輸出主要以整齊為主，使得輸出的程序結(jié)果 均整齊輸出。測試數(shù)據(jù)分析在建立文本文件名時， 要求鍵盤輸入所建立的文本文件的名稱， 如果所輸入的文本 文件名稱超過所給定的字符，將提示輸入錯誤，請重新輸入。在第二次輸入文本文件名稱以供在此文本文件中

4、查找所給定的單詞， 如果用戶輸入 的文本文件名稱與第一次不符或輸入為空，系統(tǒng)將提示輸入錯誤，請重新輸入。在主控程序中，要求輸入執(zhí)行指令 14，如果輸入非 14 字符，系統(tǒng)將提示 輸入錯誤，請重新選擇2 概要設(shè)計結(jié)構(gòu)體類型及函數(shù)聲明(1) 結(jié)構(gòu)體1. typedef struct/* 定義順序串類型 */char chMaxStrSize;int length; string;2. typedef struct /* 統(tǒng)計單詞出現(xiàn)的次數(shù) */char wordWORD_LEN;int count; elem_type;/* 存儲空間基址 */* 當(dāng)前長度 */* 當(dāng)前分配的存儲容量 */3. t

5、ypedef struct elem_type *elem; int length; int listsize; sqlist;函數(shù)：1. 建立文件： void creat_text_file()2. 單詞統(tǒng)計： void sqlist_add(sqlist *sq, elem_type *et, char *word)3. 文本文件中單詞的總匯： void substrsum()4. 單詞的定位： void substrcount()5. 主函數(shù)： int main()主程序流程1)主程序調(diào)用模塊圖主程序利用 switch()語句實(shí)現(xiàn)各個模塊的調(diào)用，主函數(shù)調(diào)用如圖 1 所示主程序根據(jù)不同數(shù)值

6、調(diào)用函數(shù)圖 1 主程序調(diào)用模塊圖模塊流程說明主函數(shù)對各主要模塊進(jìn)行調(diào)用， 各個主要模塊又分別調(diào)用其他子模塊。 下面用簡要 流程圖對各主要模塊進(jìn)行說明。(1) 建立文本文件主模塊如圖 2 所示，建立文本文件模塊。首先定義一個串變量，然后調(diào)用 void creat_text_file()函數(shù)，定義文本文件，鍵盤輸入文件名，打開該文件，循環(huán)讀入文本行， 寫入文本文件，最后關(guān)閉文件。打開文件，循環(huán)讀入文本行，寫入文本文件關(guān)閉文件圖2 建立文本文件模塊（2）給定單詞的計數(shù)主模塊如圖 3 所示為給定單詞計數(shù)程圖。 其實(shí)現(xiàn)過程如下；首先輸入要檢索的文本文件 名，打開相應(yīng)的文件，然后輸入要檢索統(tǒng)計的單詞，循環(huán)

7、讀文本文件，讀入一行，將其 送入定義好的串中， 并求該串的實(shí)際長度， 調(diào)用串匹配函數(shù)進(jìn)行計數(shù)。 數(shù)最后關(guān)閉文件， 輸出統(tǒng)計結(jié)果圖 3 單詞計數(shù)模塊3）主控程序模塊如圖 4 為中控程序流程圖。過程如下： 輸入頭文件使用循環(huán)語句輸出一下 4 個執(zhí)行指令：1. 建立文本文檔2. 文本單詞匯總3. 給定單詞定位4. 退出如輸入非 14 的指令，系統(tǒng)將提示，輸入錯誤請重新輸入 結(jié)束。圖 4 主控程序模塊3 詳細(xì)設(shè)計數(shù)據(jù)類型實(shí)現(xiàn)結(jié)構(gòu)體：1. typedef struct/* 定義順序串類型 */char chMaxStrSize;int length; string;2. typedef struct /

8、* 統(tǒng)計單詞出現(xiàn)的次數(shù) */char wordWORD_LEN; int count; elem_type;/* 存儲空間基址 */* 當(dāng)前長度 */* 當(dāng)前分配的存儲容量 */3. typedef struct elem_type *elem; int length; int listsize; sqlist;函數(shù)：1.建立文件： void creat_text_file()2.單詞統(tǒng)計： void sqlist_add(sqlist *sq, elem_type *et, char *word)3.文本文件中單詞的總匯： void substrsum()4.單詞的定位： void subs

9、trcount()5.主函數(shù)： int main()程序代碼#include #include #include #define LIST_INIT_SIZE 500 /* 線性表存儲空間的初始分配量 */ /* 線性表存儲空間的分配增量 */ /* 文件名長度 */ /* 單詞長度 */#define LISTINCREMENT 10#define FILE_NAME_LEN 20#define WORD_LEN#define MaxStrSize20256/* 規(guī)定一行有 110 個字節(jié) */#define llength 110 typedef struct char chMaxStrS

10、ize; /* ch 是一個可容納 256 個字符的字符數(shù)組 */ int length;/* 存儲單詞，不超過 20 個字符 */ /* 單詞出現(xiàn)的次數(shù) */ string;/* 定義順序串類型 */ typedef struct char wordWORD_LEN;int count; elem_type; typedef struct/* 存儲空間基址 */* 當(dāng)前長度 */* 當(dāng)前分配的存儲容量 */elem_type *elem;int length;int listsize; sqlist;void sqlist_init(sqlist *sq, elem_type *et)sq-

11、elem = et;sq-length = 0;void sqlist_add(sqlist *sq, elem_type *et, char *word) int i;int j;for (i = 0; i length; i+)/* 當(dāng)前單詞與加入的單詞相同，直接統(tǒng)計，不做插入 */ if (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;f

12、or (j = sq-length; j i; j-) memcpy(et+j, et+j-1, sizeof(elem_type); sq-length+;strcpy(eti.word, word); eti.count = 1;int sqlist_count(sqlist *sq, elem_type *et)int i;int j=0; for(i=0;ilength;i+)j=j+eti.count;return j;void creat_text_file()elem_type w;sqlist s;char file_nameFILE_NAME_LEN + 1,yn;FILE

13、*fp;printf( 輸入要建立的文件名： ); scanf(%s,file_name);fp=fopen(file_name,w);yn=n; /* 輸入結(jié)束標(biāo)志初值 */ while(yn=n|yn=N) printf( 請輸入一行文本： ); gets; gets;=strlen; fwrite(&w,1,fp);fprintf(fp,%c,10); /* 是輸入換行 */ printf( 結(jié)束輸入嗎 y or n ： );yn=getchar();fclose(fp); /* 關(guān)閉文件 */ printf( 建立文件結(jié)束 !n);void substrsum()char file_n

14、ameFILE_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, r);if (fp = NULL)printf( 打開文件失敗 !n);return;while (fscanf(fp, %s, word) != EOF)sqlist_add(&sq, et, wo

15、rd);fclose(fp);printf( 單詞 個數(shù) n);for (i = 0; i =0;w-)if(eti.wordw90&eti.wordw122) eti.wordw= ;for(w=0;wx;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);else q+;j=sqlist_count(&sq, et);printf(n%s 的單詞總數(shù)為 %d 個n,file_name,j);printf(n%s 的非單詞個數(shù)

16、為 %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)?c 中數(shù)組下標(biāo)是從 0 開始，串中序號相差 1 */ j=0; /* 掃描 s2 的開始下標(biāo) */while(i & j=return ; /* 表示 s1 中存在 s2，返回其起始位置 */elsereturn -1; /* 表示 s1中不存在 s2，返回-1 */* 函數(shù)結(jié)束 */void substrcount()FILE *fp;string s,t;/* 定義兩個串變量 */

17、char fname10;int i=0,j,k;printf( 輸入文本文件名： );scanf(%s,fname);fp=fopen(fname,r);printf( 輸入要統(tǒng)計計數(shù)的單詞： scanf(%s,;=strlen;while(!feof(fp) memset,0,110); fgets,110,fp);=strlen;k=0;while(k);/* 初始化開始檢索位置 */ /* 檢索整個主串 S */j=partposition(s,t,k);if(j0 ) break; elsei+;k=j+;/* 調(diào)用串匹配函數(shù)/* 單詞計數(shù)器加/* 繼續(xù)下一字串的檢索*/1 */*/

18、printf（n 單詞%s在文本文件 %s中共出現(xiàn) %d 次n,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( 輸入要檢索的單詞： );scanf(%s,;memset,0,110);fgets,110,fp);=strlen;l+;k=0;i=0;while(k/

19、*/* 行計數(shù)器自增 1 */* 初始化開始檢索位置 /* 初始化單詞計數(shù)器 */ 檢索整個主串 S */*/j=partposition(s,t,k);if(j0)printf( 行號： %d,次數(shù)： for(m=1;m=i;m+)%d,位置分別為： ,l,i);printf( 第%4d個字符 ,wzm+1); printf(n);printf(n 本軟件自定義 110 個字節(jié)為一行 nn); /* 檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置 */ void substrio()void substrcount(),substrint();=strlen;l=0;/* 行計數(shù)器置 0 */

20、while(!feof(fp)/* 掃描整個文本文件 */char t;while(1)printf(=n); printf( 請輸入 :);printf(| 文本文件單詞字串的定位統(tǒng)計及定位 |n); printf(|=|n);printf(| a. 單詞出現(xiàn)次數(shù) |n);printf(|n);printf(|n);printf(| b. 單詞出現(xiàn)位置 |n); printf(|n);printf(=n);scanf(%c,&t);switch(t) case a: substrcount(); break; case b: substrint(); break; default: retu

21、rn;int main()void creat_text_file(),substrsum(),substrio();int xz;while(1)printf(=n); printf(| 文本文件的檢索、字串的統(tǒng)計及定位 |n); printf(|=|n); printf(|1.建立文本文件|n);printf(|2.單詞字串的計數(shù)|n);printf(|3.單詞字串的定位|n);printf(| 4. 退出整個程序 |n); printf(=n); printf(請選擇 (1-4)n);scanf(%d,&xz);switch(xz)case 1: creat_text_file();br

22、eak;case 2: substrsum();break;case 3: substrio();break;case 4: return 0;default:printf( 選擇錯誤，重新選 n);return 0;4 調(diào)試分析問題分析與回顧問題 1：在語句“請輸入一行文本”后邊，只寫一句接受語句，結(jié)果運(yùn)行時，請輸 入文本和結(jié)束輸入嗎演示在一起，并且不能接受文本輸入。解決：和同學(xué)討論后，加入了文本接受語句，成功運(yùn)行。問題 2：當(dāng)要檢索文本時，輸入為空，或輸入非建立的文本文件名，系統(tǒng)不能正常 運(yùn)行。分析：缺少判斷語句。 解決：當(dāng)出現(xiàn)這種情況時，系統(tǒng)提示輸入錯誤，請重新輸入。算法時空分析確定給定

23、單詞出現(xiàn)的個數(shù)，需要統(tǒng)計文本文件中全部的單詞，因此時間復(fù)雜度為 O(n);確定給定單詞出現(xiàn)的位置，需要顯示其所在的行和列，時間復(fù)雜度為 O(i*l);算法改進(jìn)此算法雖然基本實(shí)現(xiàn)了功能， 但卻仍存在許多不足， 例如當(dāng)當(dāng)前建立的文件名與之 前相同時，沒有錯誤提示， 另如在對單詞的檢索方面， 時間復(fù)雜度及空間復(fù)雜度仍不盡 如人意。仍需要改進(jìn)代碼，達(dá)到算法的高效性。經(jīng)驗(yàn)和體會通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計， 讓我對數(shù)據(jù)結(jié)構(gòu)這門課有了更加深刻的認(rèn)識。 數(shù)據(jù) 結(jié)構(gòu)這門課程的理論性只是較強(qiáng)，要學(xué)好這門課程，就必要在掌握好理論知識的同時， 加強(qiáng)上機(jī)操作，遇到問題，解決問題，這樣才會有更大的進(jìn)步。我課程設(shè)計的題目是

24、文件文本的檢索與計數(shù)，由于這個課題要用到串的知識。而 我對之前對串的定義卻不是很明確， 于是我有詳細(xì)的學(xué)習(xí)了課本上的知識并查閱了很多 文獻(xiàn)。在著手作程序的過程中，經(jīng)常遇到程序運(yùn)行不出來，運(yùn)行達(dá)不到效果等問題，尤 其是接收文本， 搜索時如何定位等方面遇到了很多問題。 但我通過請教老師和同學(xué)， 查 閱文獻(xiàn)， 然后基本上解決了這些問題。 在這個過程中我學(xué)到了很多， 我認(rèn)識到了堅持不 懈的重要性，在我一遍一遍的調(diào)試下，終于成功的寫出了程序。在編寫此次程序時，我 學(xué)會了先用流程圖對進(jìn)行算法分析， 這樣是自己的思路更加清晰， 而不是像之前那樣對 整個函數(shù)沒有整體的認(rèn)知，而導(dǎo)致常常無從下手。之前我對數(shù)據(jù)結(jié)構(gòu)的各種算法都感到畏懼， 感覺很抽象， 而這次通過自己幾周的努 力，在老師和同學(xué)們的幫助下， 終于完成了此次課程設(shè)計， 這對我來說無疑是極大的鼓 舞，極大的增強(qiáng)了我學(xué)數(shù)據(jù)結(jié)構(gòu)的自信心。 而且我也充分認(rèn)識到數(shù)據(jù)結(jié)構(gòu)本身就是一門 實(shí)踐性很強(qiáng)的課程，只有加強(qiáng)實(shí)踐，才能學(xué)得更好！5 測試結(jié)果（1） 輸入建立文件名 如圖 5 所示為輸入建立文件測試圖 5 輸入建立文件測試2) 輸入一行文本測試如圖 6 所示建立一行文本，建立文件結(jié)束界面圖 6 建立文件結(jié)束測試（3）單詞字串的計數(shù)測試 如圖 7，單詞字串的計數(shù)測試界面圖7 單