數(shù) 據(jù) 結(jié) 構(gòu) 實(shí)習(xí)報(bào)告題 目： 班 級(jí)： 姓 名： 完成日期： 目 錄一、問(wèn)題描述：文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫(xiě)一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒ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ì)匹配的詞集非空。文件名和詞集均用戶從鍵盤(pán)輸入；2、 “單詞”定義：由字母構(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ù)：將實(shí)驗(yàn)的源程序作為測(cè)試文件,從中任意選取“單詞”作為測(cè)試的詞集。三、概要設(shè)計(jì)：采用截取字符串、比較字符串的模式來(lái)完成“單詞匹配比較”，從而統(tǒng)計(jì)出其出現(xiàn)的位置和次數(shù)。1、數(shù)據(jù)結(jié)構(gòu)定義：程序?qū)⑸婕暗饺缦聝蓚€(gè)線性表結(jié)構(gòu)的數(shù)據(jù)類型，用類C語(yǔ)言描述如下：（1） 定義從文本讀取的“單詞串”類型：ADT FileString數(shù)據(jù)對(duì)象：D=Si | Si 標(biāo)準(zhǔn)c+ 字符串集合,i = 1,2,3,.,n,n 0；數(shù)據(jù)關(guān)系：R1= | Si-1,Si D,i = 1,2,3,.,n基本操作：createFileString (FSList & FSL);初始條件：已知一個(gè)空的“文本單詞串表頭”；操作結(jié)果：生成一個(gè)空的“文本單詞串序列”；insertFileString (FSList & FSL,string str,int row);初始條件：FSL為文本字符串序列的表頭str為一個(gè)標(biāo)準(zhǔn)的c+字符串，row代表了字符串出現(xiàn)的行數(shù)；操作結(jié)果：將str插入到文本字符串序列中，不需要排序；若FSL為空表頭，則創(chuàng)建一個(gè)字符串序列；否則插在字符串序列尾部；getFSLength (FSList FSL);初始條件：FSL為文本字符串序列的表頭；操作結(jié)果：獲取以FSL為表頭的文本字符串的長(zhǎng)度printFileString (FSList FSL);初始條件：FSL為文本字符串序列的表頭;操作結(jié)果：打印以FSL為表頭的文本字符串中的所有字符串；readFile (FSList & FSL);初始條件：FSL為文本字符串序列的表頭；操作結(jié)果：從文件中讀取字符串序列，并將其保留在以FSL為表頭的字符串序列中；clearFileString (FSList & FSL);初始條件：FSL為文本字符串序列的表頭；操作結(jié)果：以FSL為表頭的文本字符串序列被清空；ADT FileString（2） 定義從鍵盤(pán)讀取的“單詞串”類型：ADT KeyString數(shù)據(jù)對(duì)象：D=Si | Si 標(biāo)準(zhǔn)c+ 字符串集合,i = 1,2,3,.,n,n 0；數(shù)據(jù)關(guān)系：R1= | Si-1,Si D,i = 1,2,3,.,n基本操作：createKeyString (KSList & KSL);初始條件：已知一個(gè)空的“鍵盤(pán)單詞串表頭”；操作結(jié)果：生成一個(gè)空的“鍵盤(pán)單詞串序列”；insertKeyString (KSList & KSL,string str,int row);初始條件：KSL為鍵盤(pán)字符串序列的表頭str為一個(gè)標(biāo)準(zhǔn)的c+字符串，row代表了字符串出現(xiàn)的行數(shù)；操作結(jié)果：將str插入到鍵盤(pán)字符串序列中，不需要排序；若KSL為空表頭，則創(chuàng)建一個(gè)字符串序列；否則插在字符串序列尾部；getKSLength (KSList KSL);初始條件：KSL為鍵盤(pán)字符串序列的表頭；操作結(jié)果：獲取以KSL為表頭的鍵盤(pán)字符串的長(zhǎng)度printKeyString (KSList KSL);初始條件：KSL為鍵盤(pán)字符串序列的表頭;操作結(jié)果：打印以KSL為表頭的鍵盤(pán)字符串中的所有字符串；readKey (KSList & KSL);初始條件：KSL為文本字符串序列的表頭；操作結(jié)果：從鍵盤(pán)中讀取字符串序列，并將其保留在以KSL為表頭的字符串序列中；clearKeyString (KSList & KSL);初始條件：KSL為文本字符串序列的表頭；操作結(jié)果：以KSL為表頭的文本字符串序列被清空；ADT KeyString2、模塊設(shè)計(jì)：1） 主程序模塊：主函數(shù)設(shè)計(jì)如下int main ( ) 登陸界面和使用提示；構(gòu)建文本字符串序列；構(gòu)建鍵盤(pán)字符串序列；構(gòu)建模式匹配排除符集合；字符串模式匹配，統(tǒng)計(jì)單詞；結(jié)束一輪工作，提示是否繼續(xù)操作；2） 文本字符串模塊-構(gòu)建文本字符串序列；3） 鍵盤(pán)字符串模塊-實(shí)現(xiàn)鍵盤(pán)字符串?dāng)?shù)據(jù)類型；4） 模式匹配模塊-實(shí)現(xiàn)文本字符串和鍵盤(pán)字符串的匹配統(tǒng)計(jì)；5） 登陸界面模塊-提示用戶程序使用方法3、各模塊間的調(diào)用關(guān)系： 四、詳細(xì)設(shè)計(jì)1、主程序用到的宏定義：#define MAX_WORD_LENGTH 1000/最大字符串長(zhǎng)度#define MAX_MODELEXCEPTION_LENGTH 50#define FILE_NAME_LENGTH 100/文件名長(zhǎng)度2、存儲(chǔ)結(jié)構(gòu)設(shè)/*從文件讀取的字符串集合*/typedef struct FileStringstring name;/字符串名稱int row;/字符串所在的行FileString * next;/鄰接字符串FileString,*FSList;/*從鍵盤(pán)讀取的字符串集合*/typedef struct KeyStringstring name;/字符串名稱int * rows;/字符串所在行向量int count;/字符串出現(xiàn)的次數(shù)KeyString * next;/鄰接字符串KeyString,*KSList;/*匹配文本字符串和鍵盤(pán)字符串的模式匹配排除符集合*/typedef char * Model;3、主要算法設(shè)計(jì)：/*在文件字符串集合中插入新的字符串*/int insertFileString(FSList & FSL,string str,int row)if(!FSL)/如果是空表，則創(chuàng)建集合createFileString(FSL);FSList sp ,tp;sp = tp = FSL;while(sp = sp -next)tp = sp;FSList s = new FileString;/插在既有的集合中if(!s)coutname = str;s-row = row;s-next = NULL;tp-next = s;/順序插入return 1;/*從文件中讀取串*/int readFile(FSList & FSL)char urlFILE_NAME_LENGTH;/指向文件路徑的const指針coutEnter the file to read:;gets(url);while(url0 = 0)/保證文件名不為空coutThe files name can not be null!endl;gets(url);ifstream fs = ifstream(url);/打開(kāi)文件讀取字符串if(!fs)coutFile reads wrong!n;return 0;int rowLine = 1;string s;while(fs.peek()!=EOF)/遇到文件尾符，結(jié)束讀取getline(fs,s,n);/依行讀取sinsertFileString(FSL,s,rowLine+);/將獲取的字符串插入文件字符串集合return 1;/*統(tǒng)計(jì)模式匹配排除字符*/int getModelException(Model & model)model = new charMAX_MODELEXCEPTION_LENGTH;/集合model能統(tǒng)計(jì)除了默認(rèn)匹配字符外的所有客戶指定的排除字符char match;coutmatch;cin.ignore();/避免其他方法的流操作帶來(lái)負(fù)面影響int i = 0;while(match = y)if(!i)coutBegin to receive:;if(cin.peek()=n)if(!i)coutNo character receivedendl;coutEnd receivingendl;break;cin.get(modeli+);/默認(rèn)的模式匹配排除符modeli = ;modeli+1 = ,;modeli+2 = .;modeli+3 = ;modeli+4 = ;modeli+5 = ;modeli+6 = *;modeli+7 = #;modeli+8 = !;modeli+9 = $;modeli+10 = %;modeli+11 = ;modeli+12 = &;modeli+13 = (;modeli+14 = );modeli+15 = -;modeli+16 = +;modeli+17 = _;modeli+18 = |;modeli+19 = ;modeli+20 = ;modeli+21 = ;modeli+22 = ;modeli+23 = ;modeli+24 = :;modeli+25 = ;modeli+26 = ;modeli+28 = ?;modeli+29 = /;modeli+30 = ;modeli+31 = t;modeli+32 = 0;/串尾標(biāo)志return 1;/*模式匹配方法*/bool modelMatch(string s,Model model,int pos)for(int i = strlen(model) -1 ;i=0;i-)if(spos = modeli)return true;return false;/*查找模式串T在主串S中出現(xiàn)的次數(shù)*/int count(string S,const string T,Model model)int count = 0;const char * tc = T.c_str();int i = 0;while(i S.length()/定義模式匹配規(guī)則-掃描排除字符if(modelMatch(S,model,i)/遇到模式匹配規(guī)則所定義的字符，則忽略讀取i+;continue;else/至此，Si肯定不是模式匹配的排除字符char * sc = new charMAX_WORD_LENGTH;char * sp = sc;/此處的while循環(huán)保證了在讀取過(guò)程中始終保證不遇到模式匹配的排除字符while(Si!=0&!modelMatch(S,model,i)/未至行尾并且沒(méi)有遇到/模式匹配規(guī)則所定義/的排除字符，則讀取*sp = Si;/讀取子串sp+,i+;*sp = 0;/結(jié)束子串讀取if(!strcmp(sc,tc)/比較模式串和子串count+;/相等則增加計(jì)數(shù)delete sc;return count;/*定位KSL中字符串在FSL中的位置*/void locate(FSList & FSL,KSList & KSL,Model model)if(!FSL&!KSL)coutnext)FSList fp = FSL;/sp是SL的副本操作int * row = new intgetFSLength(FSL)+1;/對(duì)于鍵盤(pán)字符串集合中的每個(gè)字符串，/row都會(huì)重新申請(qǐng)空間int * r = row;kp-rows = row;while(fp = fp-next)int c = count(fp-name,kp-name,model);if(c) /kp-name在fp-name出現(xiàn)了，則統(tǒng)計(jì)其位置kp-count += c;*r = fp-row;r+;*r = 0;/堆棧指針指向空間最后單元的下個(gè)單元賦NULL值五、調(diào)試報(bào)告：1、 程序在設(shè)計(jì)過(guò)程中主要遇到了如下幾個(gè)主要的問(wèn)題：1）從文本中讀取文件時(shí)的錯(cuò)誤。最典型的錯(cuò)誤就是當(dāng)鍵入的文件名為空時(shí)，程序會(huì)拋擲異常，且給出嚴(yán)重的警告。該問(wèn)題的發(fā)現(xiàn)，是在我對(duì)主程序模塊作了添加一個(gè)dowhile（）循環(huán)后發(fā)現(xiàn)的。經(jīng)過(guò)調(diào)試分析，我發(fā)現(xiàn)問(wèn)題在于readFile(FSList & FSL)模塊中的語(yǔ)句：gets（url）；當(dāng)?shù)谝惠喲h(huán)結(jié)束后，欲再繼續(xù)二輪循環(huán)時(shí)，會(huì)執(zhí)行指令：cinon；該語(yǔ)句只接受了on的賦值，卻將enter鍵傳給了下一輪的gets（url）；從而導(dǎo)致錯(cuò)誤。我初步的修改是取一個(gè)折中的方法，在readFile（FSList & FSL）模塊中添加語(yǔ)句：cin.ignore（）；這樣自然會(huì)忽略enter鍵的鍵入，但使得初次循環(huán)在輸入文件名時(shí)，要先回車，后輸入文件回車。給用戶很不好理解的困惑。于是，我又再次修改：將cin.ignotrz（）添加到主程序模塊中cinon；語(yǔ)句之后；這樣就可以忽略enter，同時(shí)又保證程序模塊可以復(fù)用，不會(huì)產(chǎn)生讀取錯(cuò)誤，如當(dāng)前版本所示。2）在統(tǒng)計(jì)單詞匹配時(shí)發(fā)生的錯(cuò)誤。這里的主要問(wèn)題是關(guān)于模式匹配排除符的把握問(wèn)題，具體體現(xiàn)在算法count（string S,const string T,Model model）中。模式匹配排除是我自己在設(shè)計(jì)程序的過(guò)程中提出的一個(gè)術(shù)語(yǔ)。我起初并沒(méi)有想過(guò)提出這么一個(gè)概念，而是想以一個(gè)condition的bool 變量來(lái)表示。后來(lái)，我看到若手工指定排除符，則condition的內(nèi)容就是變化的，而且隨著定義的排除符的數(shù)目的不同，每次對(duì)condition 的修改都會(huì)引起程序大規(guī)模的改動(dòng)。特別是在我想到將condition區(qū)分為用戶特別指定和程序初始化時(shí)的默認(rèn)分配情況時(shí)，這種由condition控制的表示就越來(lái)越有問(wèn)題，這迫使我想到用一種數(shù)據(jù)結(jié)構(gòu)來(lái)封裝和模式匹配的相關(guān)操作。于是，我提出了模式匹配排除符的概念，并且對(duì)其作了相應(yīng)的處理。其中，仿照windows程序的消息機(jī)制，我也對(duì)排除符做了相應(yīng)的規(guī)劃，區(qū)分為特別的排除符和默認(rèn)的排除符，具體的實(shí)現(xiàn)機(jī)制在getModelException (Model & model) 算法中。3)程序設(shè)計(jì)中對(duì)動(dòng)態(tài)內(nèi)存分配的妥善處理。由于文本字符串序列和鍵盤(pán)字符串序列長(zhǎng)度的不確定性，而且又用到了鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，故對(duì)內(nèi)存分配的處理是很關(guān)鍵的。本程序中new 操作多達(dá)7次（在不考慮是否處于循環(huán)體中的情況下）。其中算法locate(FSList & FSL,KSList & KSL,Model model)在動(dòng)態(tài)分配了內(nèi)存給rows變量后，并沒(méi)有回收內(nèi)存，這就考慮到跨模塊去回收內(nèi)存的問(wèn)題。我定義了一個(gè)clear*()函數(shù)，用來(lái)清理由FSList和KSList所申請(qǐng)到的內(nèi)存。clear*（）要求對(duì)字符串序列的統(tǒng)計(jì)操作后，立即調(diào)用它來(lái)釋放內(nèi)存，保證不會(huì)產(chǎn)生內(nèi)存泄露。2、程序的時(shí)空復(fù)雜度分析：設(shè)從文本中依行讀取的字符串平均長(zhǎng)度為L(zhǎng)，其行數(shù)為m，待統(tǒng)計(jì)單詞平均長(zhǎng)度為S，其個(gè)數(shù)為n，則程序的時(shí)間消耗主要用于統(tǒng)計(jì)定位操作上。對(duì)于modelMatch（）算法，其時(shí)間復(fù)雜度為：O（L）;對(duì)于count（）算法，其時(shí)間復(fù)雜度為：O（L*L）,這是因?yàn)閏ount（）中調(diào)用了modelMatch（）；對(duì)于locate（）算法，其時(shí)間復(fù)雜度為：O（L*L*n*m）；這是因?yàn)檎{(diào)用了count（）。從空間角度來(lái)看，輔存空間依然消耗在統(tǒng)計(jì)和定位上，還包括在構(gòu)建單詞穿序列上。對(duì)于count（）算法，其空間復(fù)雜度為O（L）;對(duì)于locate（）算法，其空間復(fù)雜度為O（m*n）；這是因?yàn)橐獮镵SL的rows動(dòng)態(tài)分配內(nèi)存；構(gòu)建單詞串的時(shí)間復(fù)雜度為O（m+n）；從時(shí)空復(fù)雜度來(lái)看，這個(gè)程序?qū)嶋H上效率其實(shí)并不是很高。我統(tǒng)計(jì)過(guò)，當(dāng)統(tǒng)計(jì)單詞數(shù)在5個(gè)以上時(shí)，就會(huì)有延時(shí)傾向；當(dāng)統(tǒng)計(jì)的單詞數(shù)控制在12個(gè)以上時(shí)，查找延時(shí)相當(dāng)明顯，約有0.5秒的間隔出現(xiàn)。當(dāng)統(tǒng)計(jì)單詞數(shù)為15個(gè)時(shí)，有1秒延遲，當(dāng)統(tǒng)計(jì)超過(guò)17個(gè)單詞時(shí)有1.5-2秒的延遲。此外，輸入的單詞的特征也對(duì)統(tǒng)計(jì)延時(shí)有影響，當(dāng)待統(tǒng)計(jì)的單詞與文本串中讀取的單詞長(zhǎng)度相當(dāng)時(shí)，統(tǒng)計(jì)延時(shí)最大；而待統(tǒng)計(jì)單詞過(guò)長(zhǎng)或過(guò)短，都不會(huì)有太大的影響。由此可見(jiàn)，單詞長(zhǎng)度對(duì)統(tǒng)計(jì)的影響，無(wú)論時(shí)時(shí)間復(fù)雜度還是空間復(fù)雜度，都是很突出的。3、程序的擴(kuò)展方向：程序還不能完全處理漢字串的情況，可以向著類似offic和一般的文本編輯工具所提供的全字匹配查找與一般查找方向拓展，真正做到“一查即得，一查即準(zhǔn)”。同時(shí)，針對(duì)統(tǒng)計(jì)延時(shí)，可以在參考KMP算法的同時(shí)，加以優(yōu)化改良。六、經(jīng)驗(yàn)體會(huì)：1)理解分析問(wèn)題的能力得到提高。設(shè)計(jì)一個(gè)應(yīng)用程序關(guān)鍵是對(duì)要求做最準(zhǔn)確的把握，也就是說(shuō)弄清楚需求分析是很重要的。本程序要求我從文件中讀取單詞的位置，就是在文件中檢索字符串，這樣一抽象，問(wèn)題的脈絡(luò)就清晰了。接下來(lái)，如何讀取，讀取后如何映射，映射的字符串又怎么和待查字符串關(guān)聯(lián)，這就構(gòu)成了解決問(wèn)題的幾大關(guān)鍵模塊。逐個(gè)解析，整個(gè)程序的框架就了然于胸了。特別要指出的是，對(duì)整個(gè)程序的把握，隨著編程工作的深入，是越來(lái)越深刻，而且新的思路也是層出不窮。2） 創(chuàng)新意