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

1、武漢理工大學(xué)課程設(shè)計(jì)報(bào)告計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題目文學(xué)研究助手班 級(jí) 計(jì)算機(jī)1101班學(xué) 號(hào) 0姓 名 王衛(wèi)華指導(dǎo)教師杜海濤2013年6月21日課程設(shè)計(jì)任務(wù)書(shū)學(xué)生姓名：王衛(wèi)華專(zhuān)業(yè)班級(jí)： 1101班指導(dǎo)教師：杜海濤工作單位：計(jì)算機(jī)科學(xué)系題目：文學(xué)研究助手初始條件：文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試 寫(xiě)一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱(chēng)為''文學(xué)研究助手”。英文小說(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng) 計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出 現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。

2、測(cè)試用例見(jiàn)題集P116o要求完成的主要任務(wù)：（包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）課程設(shè)計(jì)報(bào)告按學(xué)校規(guī)定格式用A4紙打印（書(shū)寫(xiě)），并應(yīng)包含如下內(nèi)容：1、問(wèn)題描述簡(jiǎn)述題目要解決的問(wèn)題是什么。2、設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì).主要算法設(shè)計(jì)（用類(lèi)C語(yǔ)言或用框圖描述）、測(cè)試用例 設(shè)計(jì)；3、調(diào)試報(bào)告調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的；對(duì)設(shè)計(jì)和編碼的討論和分析。4、經(jīng)驗(yàn)和體會(huì)（包括對(duì)算法改進(jìn)的設(shè)想）5、附源程序清單和運(yùn)行結(jié)果。源程序要加注釋。如果題目規(guī)定了測(cè)試數(shù) 據(jù)，則運(yùn)行結(jié)果要包含這些測(cè)試數(shù)據(jù)和運(yùn)行輸出，6、設(shè)計(jì)報(bào)告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績(jī) 均為0分。時(shí)間安排：1、第

3、17周（6月17日至6月21日）完成。2、6月21日14： 00到計(jì)算中心檢查程序、交課程設(shè)計(jì)報(bào)告、源程序（CD盤(pán)）。指導(dǎo)教師簽名:系主任（或責(zé)任教師）簽名：年 月 日文學(xué)研究助手一、問(wèn)題描述：文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫(xiě) 一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱(chēng)為“文學(xué)研究助手”。英文小說(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì) 工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次 數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。二、需求分析：1、文本串非空且以文件形式存放，統(tǒng)計(jì)匹配的詞集非空。文件名和詞集均由用 戶(hù)從鍵盤(pán)輸入；2、

4、"單詞”定義：由字母構(gòu)成的字符序列，中間不含空格字符且區(qū)分大小寫(xiě)；3、待統(tǒng)計(jì)的“單詞”在文本串中不跨行出現(xiàn)，它或者從行首開(kāi)始，或者前置若 干空格字符；4、在計(jì)算機(jī)終端輸出的結(jié)果是：?jiǎn)卧~，出現(xiàn)的次數(shù)，出現(xiàn)的位置所在行的行號(hào), 同一行出現(xiàn)兩次的只輸出一個(gè)行號(hào)；5、測(cè)試數(shù)據(jù)以你的C源程序模擬英文小說(shuō)，C語(yǔ)言保留字集作為待統(tǒng)計(jì)的詞匯集： if else for while return void int char typedef struct definesizeof delete include三. 概要設(shè)計(jì)1、存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)define SIZE 20typedef FILE *PFILE

5、； typedef char StringSIZE；typedef struct/單詞類(lèi)型String data； int len； WordType；/單詞串單詞的長(zhǎng)度typedef struct WordNode/ /單詞結(jié)點(diǎn)類(lèi)型WordType data； WordNode *next； WordNodet*pWordNode；typedef struct RowLink表示文本每一行的鏈表WordNode *head,*tail；)RowLink,*RLink；typedef struct RowNumNode/行號(hào)結(jié)點(diǎn)類(lèi)型int elem；/行號(hào)RowNumNode *next；Ro

6、wNumNode,*RowNumL ink；typedef struct SearchWordNode待搜索的單詞結(jié)點(diǎn)類(lèi)型WordType data；int count；RowNumLink RNhead,RNta訂; 表SearchWordNode *next；SearchWordNode,*SWLink；待搜索單詞待搜索單詞出現(xiàn)的次數(shù)存放文本中岀現(xiàn)待搜索單詞行號(hào)的鏈struct SWLinkList 結(jié)果/待搜索的單詞集合的鏈表并用來(lái)存儲(chǔ)統(tǒng)計(jì)SWLink head,tail；;2.主要算法設(shè)計(jì)描述下列函數(shù)中較容易實(shí)現(xiàn)的未給岀步驟(1) void CopyWord(WordType &

7、;wt String ch)把字符串ch復(fù)制到單詞元素v(2) int MatchWord(WordType wl,WordType w2) 單詞的匹配,若相等則返回1,否則返回非0(3) void MakeWordNode(PWordNode &PN) 生成一個(gè)單詞結(jié)點(diǎn)(4) void InsertAfter(RowLink &L,WordType w)<用后插法把單詞結(jié)點(diǎn)w插入鏈表LMakeWordNode>next)；>next->data=w；=>next；(5) void DestroyWordLink(RowLink &L)銷(xiāo)毀

8、鏈表L(6) void CreateWordLink(RowLink &LtFILE *f) 創(chuàng)建存放f指向文本每中一行單詞的鏈表該函數(shù)的主要步驟：String ch；char c=getc(f):WordType w；char c=getc(f):/從文件中讀取一個(gè)字符MakeWordNode;/調(diào)用該函數(shù)生成文件行單詞鏈表的頭結(jié)點(diǎn)二while(c! =，nr&&! feof (f)/c不是換行,文件也未結(jié)束 while(! (c>=rAF&&c<=rZr I |c>=rar&&c<=rzr)&&

9、c! =，nr&&!feof (f)/濾去非法 字符c=getc(f)；for (int i=0；c>=lAF&&c<=：lZ, | | c>=lar&&c<=1 zr; i+) /取單詞，ch|.i=c；c=getc(f)；chi = fOr ；CopyWord (w, ch)；/將獲取的字符串復(fù)制到單詞型的變量中InsertAfter (L, w) ； /將獲取的該單詞插入到鏈表中)(7) void MakeRowNumNode(RowNumLink &p)生成一個(gè)行結(jié)點(diǎn)(8) void MakeSWNode(

10、SWLink &p)生成一個(gè)待搜索的單詞結(jié)點(diǎn)(9) void CreateSWLinkList(SWLinkList &S)建立一個(gè)待搜索的單詞鏈表(10) void OutputSWLinkList(SWLinkList S)輸出待搜索的單詞鏈表的在文本中出現(xiàn)的次數(shù)和行號(hào)(11) void OpenFile(PFILE &f,String ch)打開(kāi)文件，ch表示文件的路徑及名稱(chēng)(12) 中心函數(shù)描述void MatchSWLinkList(SWLinkList &S,FILE *f)查找文本中出現(xiàn)待搜索的單詞的次數(shù)和行號(hào))該函數(shù)是求解該問(wèn)題的主演函數(shù)，其主要

11、步驟為：i=0 記錄行號(hào)while(! (feof (f)/文件未結(jié)束i+;CreateWordLink (RL, f):/創(chuàng)建文本的該行單詞鏈表Sps=>next； /ps指向此時(shí)被搜索的單詞while(ps) 當(dāng)ps所指單詞不為空，在本行中查找其出現(xiàn)的次 數(shù)pr=>next ；/該指針指向文件該行的鏈表int label=l； 用于標(biāo)志待搜索單詞在本行中是否是第一次 出現(xiàn)，若是須創(chuàng)建一行結(jié)點(diǎn)，若不是，直接count+1while(pr)/本文中一行單詞鏈表的每個(gè)結(jié)點(diǎn)依次與被搜索的單詞比較if(MatchWord(pr->data,ps-data)ps->count+

12、；if(label=l)是該正在搜索指針?biāo)傅膭?chuàng)建統(tǒng)計(jì)被搜索單詞行號(hào)的鏈表，記錄此時(shí)的行號(hào) label=O；pr=pr->next；/指向本行中下一個(gè)單詞并進(jìn)行比較ps=pS->next； 對(duì)待搜索的下一個(gè)單詞進(jìn)行統(tǒng)計(jì)DestroyWordLink(RL)；/銷(xiāo)毀已被搜索過(guò)的文件中該行單詞的鏈表四、調(diào)試報(bào)告調(diào)試過(guò)程中遇到的問(wèn)題及解決方案：(1) 對(duì)單詞類(lèi)型WordType進(jìn)行定義時(shí)，原本想采用字符數(shù)組對(duì)data進(jìn)行定義， 但是對(duì)字符數(shù)組的操作不如對(duì)字符串操作方便，故改用字符串。(2) 在創(chuàng)建文件中每一行單詞的鏈表以及待測(cè)試的單詞的鏈表，及創(chuàng)建待測(cè)試的 單詞的鏈表時(shí)，原本按照生成頭結(jié)

13、點(diǎn)，然后再生成結(jié)點(diǎn)依次插入，但發(fā)現(xiàn)在其它 函數(shù)中也用到生成結(jié)點(diǎn)，這導(dǎo)致程序冗雜，故把生成結(jié)點(diǎn)寫(xiě)成一個(gè)獨(dú)立的函數(shù)， 供其它函數(shù)調(diào)用。(3) 在統(tǒng)計(jì)被測(cè)試單詞在每一行中出現(xiàn)的次數(shù)時(shí)，若該單詞在一行中出現(xiàn)了兩 次，統(tǒng)計(jì)時(shí)發(fā)生了錯(cuò)誤。后經(jīng)修改，設(shè)置了一個(gè)label標(biāo)志，用于標(biāo)志待搜所單詞 在本行中是否是第一次出現(xiàn)，若是，須創(chuàng)建一行結(jié)點(diǎn)，記錄行號(hào)，若不是，克接count自增 I 而開(kāi)需再比成一個(gè)行結(jié)占(4) 在從文件中獲取字符時(shí)茲初未考慮所獲取的字符是否是英文字母，且未過(guò) 濾非英文字母的字符。對(duì)設(shè)計(jì)和編碼的分析：該設(shè)計(jì)的主要思想為：(1).存儲(chǔ)結(jié)構(gòu)思想如下：用結(jié)點(diǎn)為單詞類(lèi)型的鏈表存儲(chǔ)文件中某一行的單詞，

14、用結(jié)點(diǎn)為待搜索單詞 類(lèi)型(該節(jié) 點(diǎn)中包括count用來(lái)記錄文件中單詞出現(xiàn)的總數(shù)，還帶有指向行的 指針等)的鏈表來(lái)表示待搜索的單詞，并對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)O(2)在統(tǒng)計(jì)被測(cè)單詞集在文件中出現(xiàn)的總次數(shù)及行號(hào)時(shí)，思想如下：首先，生成文件某一行的單詞錐表，取待搜索的第一個(gè)單詞與本行每一個(gè) 單詞比較，若相等則count自增1,然后取待搜索的下一個(gè)單詞，亦與本行的每一個(gè)單詞比較，直至完成所有要搜索的單詞。然后，生成下一行的單詞鏈表，重復(fù)上一步驟，直至文件結(jié)束。五、經(jīng)驗(yàn)和體會(huì)以及對(duì)算法改進(jìn)的設(shè)想經(jīng)驗(yàn)和體會(huì)：(1)理解分析問(wèn)題的能力及解決問(wèn)題的能力得到提髙這次課程設(shè)計(jì)從解決問(wèn)題的思想到實(shí)際編寫(xiě)代碼及調(diào)試、分析代碼的

15、優(yōu)劣, 都需要自己再三斟酌，耐心的編寫(xiě)與解決編程中的問(wèn)題，對(duì)于編程中一些不熟悉 的用法還需要查找一些資料。經(jīng)過(guò)此次課程設(shè)計(jì)，我認(rèn)識(shí)到設(shè)計(jì)一個(gè)應(yīng)用程序的 關(guān)鍵是對(duì)要求做最準(zhǔn)確的把握，也就是說(shuō)弄清楚需求分析是很重要的。本程序要 求我從文件中找到所要查找的單詞岀現(xiàn)的次數(shù)及位置，也就是在文件中檢索字符 串。這樣想來(lái)，思路就清晰了。如何在文件中讀取單詞，讀取后如何映射，映射 的字符串有如何和帶查找的單詞關(guān)聯(lián)、查找的結(jié)果如何存儲(chǔ)，是解決該問(wèn)題的幾 大關(guān)鍵模塊。逐個(gè)解析，整個(gè)程序的框架就了然于胸了。且隨著編程的進(jìn)行，思 路越來(lái)越清晰。(2)對(duì)程序設(shè)計(jì)語(yǔ)言的細(xì)微之處又有了更深刻的理解。由于字符串的操作是很 原

16、始的基于原子的操作，所以更能看清楚我們所用的字符串操作函數(shù)在底層的實(shí) 現(xiàn)機(jī)制，盡管再次程序中實(shí)現(xiàn)時(shí)與標(biāo)準(zhǔn)字符串的實(shí)現(xiàn)原理和實(shí)施手段有所不同， 但根本認(rèn)識(shí)差的并不遠(yuǎn)。次算法存在的不足之處及對(duì)算法改進(jìn)的設(shè)想：該思想的主要缺陷是在統(tǒng)計(jì)待搜索單詞在每一行中出現(xiàn)的次數(shù)時(shí)，時(shí)間復(fù) 雜度太髙，每一個(gè)待搜索的單詞都要與一行中的所有單詞比較。若待搜索的單詞 有m個(gè)，文件中每行單詞平均有n個(gè)，則統(tǒng)計(jì)一行中所有待搜索的單詞出現(xiàn)的次 數(shù)的時(shí)間復(fù)雜度就為0 改進(jìn)：可以通過(guò)KMP模式匹配進(jìn)行修改。此外還 可以在行結(jié)點(diǎn)中增加一計(jì)數(shù)量來(lái)統(tǒng)計(jì)每一行中被檢測(cè)單詞出現(xiàn)的次數(shù)。六. 附源程序清單和運(yùn)行結(jié)果。ttincludeO tt

17、includeOttincludeOv#include<>#include<>define SIZE 20typedef FILE *PFILE；typedef char StringSIZE:String data；/單詞串int len；單詞的長(zhǎng)度WordType；typedef struct WordNode /單詞結(jié)點(diǎn)類(lèi)型IWordType data；WordNode *next；WordNode,*PWordNode；typedef struct RowLink/表示文本每一行的鏈表WordNode *head,*tail；RowLink,*RLink；Ity

18、pedef struct RowNumNode/行號(hào)結(jié)點(diǎn)類(lèi)型int elem；行號(hào)RowNumNode *next；RowNumNode,*RowNumLink；typedef struct SearchWordNode/待搜索的單詞結(jié)點(diǎn)類(lèi)型WordType data；/待搜索單詞int count；待搜索單詞出現(xiàn)的次數(shù)RowNumLink RNhead, RNta訂；/存放文本中出現(xiàn)待搜索單詞行號(hào)的鏈表SearchWordNode *next；SearchWordNode,*SWLink；struct SWLinkList/待搜索的單詞集合的鏈表SWLink head,tail；;void

19、CopyWord(WordType &w,String ch)/把字符串 ch 復(fù)制到單詞元素 wint j=strlen(ch)； for(int i=0；i<=j;i+)i=chi；=j;int MatchWord(WordType wl.WordType w2)/單詞的匹配，若相等則返回 1,否則 返回非0if!二return 0；elsefor(int i=0；i<；i+)ifi! = i)break；if(i=return 1；elsereturn 0；void MakeWordNode(PWordNode &PN) 生成一個(gè)單詞結(jié)點(diǎn)if(!(PN=(PW

20、ordNode)malloc(sizeof(WordNode)cout«,r為新單詞分配存儲(chǔ)空間失敗，r«endl；exit (0)；PN->next二NULL；void InsertAfter(RowLink &L,WordType w) /用后插法把單詞結(jié)點(diǎn) w 插入鏈 表LMakeWordNode>next)； >next->data=w； =>next；void DestroyWordLink(RowLink &L)/銷(xiāo)毀鏈表 Lwhile=>next；delete；=;void CreateWordLink(Ro

21、wLink &L.FILE *f)/創(chuàng)建存放 f 指向文本每中一行單 詞的鏈表String ch；char c二getc(f)；WordType w；MakeWordNode；二while(c! = rnr&&!feof (f)wh訂e(!(c>=,A,&&c<=tZ,|c>=,a,&&c<=,z,)&&c! = ,n,&&!feof (f)/濾去非法字符c=getc(f)；for (int i=0；c>=, A，&&c<=,Z' | | c>

22、;=,a,&&c<=, z' i+)/取單詞chi=c；c=getc(f)；chi = ' 0'；CopyWord(wtch)；InsertAfter(Ltw)； void MakeRowNumNode(RowNumLink &p)/生成一個(gè)行結(jié)點(diǎn)if (! (p=(RowNumLink)malloc(sizeof(RowNumNode) cout«，r分配行號(hào)結(jié)點(diǎn)失敗，r«endl； exit (0); p->next=NULL；void MakeSWNode(SWLink &p)/生成一個(gè)待搜索的單詞結(jié)

23、點(diǎn) if(!(p=(SWLink)malloc(sizeof(SearchWordNode) cout«w分配待搜索的單詞結(jié)點(diǎn)失敗"<<endl； exit (0)；p->next=NULL；p->count二0；p->RNhead二NULL；p->RNta ilhlULL；void CreateSWLinkList(SWLinkList &S)/建立一個(gè)待搜索的單詞鏈表)MakeSWNode；String st=H#M；WordType w,label；CopyWord(label,st)；cout«H請(qǐng)輸入要搜索的英

24、文單詞，如果是則表示輸入結(jié)束K«endl； cin»st；CopyWord(w,st)；¥whi 1 e (!MatchWord (w, 1 abe 1)/w 不是MakeSWNode>next)；>next->data=w；二>next；cin>>st；CopyWord(wt st)；void MatchSWLinkList(SWLinkList &S,FILE *f) /查找文本中出現(xiàn)待搜索的單 詞的次數(shù)和行號(hào)RowLink RL；用于保存文件中一行單詞的鏈表PWordNode pr二NULL ；/指向文件單次鏈表中

25、的每一個(gè)單詞SWLink ps=NULL； 指向被搜索的單詞int i=0；while(! (feof(f)/讀取文本的每一行單詞i卄；/行號(hào)CreateWordLink(RL, f);/創(chuàng)建文本的一行單詞鏈表ps=>next；while (ps)/遍歷待搜索的單詞鏈表的每個(gè)結(jié)點(diǎn)pr=>next；int label"； 用于標(biāo)志待搜索單詞在本行中是否是第一次出現(xiàn), 若是須創(chuàng)建一行結(jié)點(diǎn)，若不是，直接count+1>while(pr) /本文中一行單詞鏈表的每個(gè)結(jié)點(diǎn)依次與被搜索的 單詞比較if (MatchWord(pr->data,ps->data)ps-

26、>count+；if(label=l)if (ps->RNhead=NULL)/判斷是否是第一個(gè)結(jié)點(diǎn)，MakeRowNumNode (ps->RNhead) ；/ 創(chuàng)建統(tǒng)計(jì)被搜索單詞出現(xiàn)次數(shù)及行號(hào)的鏈表ps->RNhead->elem=i ；ps->RNtail=ps->RNhead；elseMakeRowNumNode(ps->RNtail->next)；ps->RNtai l->next->elemzzi ；ps->RNtai1二ps->RNtai1-next ；label=0；pr=pr->next

27、；ps二ps->next；)DestroyWordLink (RL);/銷(xiāo)毀已被搜索過(guò)的文件中該行單詞的鏈表void OutputSWLinkList(SWLinkList S)/輸出待搜索的單詞鏈表的在文本中出 現(xiàn)的次數(shù)和行號(hào)SWLink p；/指向待輸出的單詞RowNumLink pr；/指向待輸出單詞的某一行cout« "搜索結(jié)果："«end 1;p=>next；while(p)printf (，r%-8s：cout«M出現(xiàn)的次數(shù)M«p->count«M "<<"所在行為："if(p->count)pr=p->RNhead；while(pr)cout«pr->elem«,r, ”；pr=pr->next；cout<<endl；?p=p->next；void OpenFile(PFILE &ftString ch