1、HUNANUNIVERSIT Y題目 學(xué)生 學(xué)生學(xué)號 專業(yè)班級 指導(dǎo)老師 完成日期曉鴻2 0僅12月31日課程實驗報告告自組織線性表'需求分析1程序功能本程序可輸入漢語句子和要查找的漢字，并用需查找的漢 字與漢字句子中的漢字進(jìn)行查找比較，把查找到的漢字在順序 表中用轉(zhuǎn)置法排序，輸出查找結(jié)果與比較次數(shù)。2輸入形式用戶輸入句子，可以輸入空格，不對非法輸入做處理， 假定輸入的數(shù)據(jù)都合法漢字。用戶輸入要查找的字，用空格隔開。3. 輸出形式輸出要查找的漢字和查找結(jié)果及比較次數(shù)，并將輸出保存 到文件中。要查找的漢字為：“漢字A”查找成功，比較次數(shù)為?！皾h字B”查找失敗，比較次數(shù)為。4測試數(shù)據(jù)數(shù)據(jù)1

2、：請輸入文字（文字間可輸入空格）：我愛你中國請輸入查找的字們（中間用空格隔開）：你你你你中國輸出:你查找成功！查找次數(shù)為：3你查找失敗!查找次數(shù)為：2你查找成功！查找次數(shù)為：1你查找成功！查找次數(shù)為：1中查找成功！查找次數(shù)為：4國查找成功！查找次數(shù)為：5數(shù)據(jù)2：請輸入文字（文字間可輸入空格）：隔壁老王買了個瓜很甜請輸入查找的字們（中間用空格隔開）：瓜很甜老王輸出：瓜查找成功！查找次數(shù)為：3很查找失??！查找次數(shù)為：2甜查找成功！查找次數(shù)為：1老查找成功！查找次數(shù)為：4王查找成功！查找次數(shù)為：5數(shù)據(jù)3：請輸入文字（文字間可輸入空格）：一二三四五六七八請輸入查找的字們（中間用空格隔開）：、 、 -

3、-八八一一輸出：六查找成功！查找次數(shù)為：6六查找成功！查找次數(shù)為：5二查找成功！查找次數(shù)為：2二查找成功！查找次數(shù)為：1數(shù)據(jù)4：請輸入文字（文字間可輸入空格）：君不見黃河之水天上來奔流到海請輸入查找的字們（中間用空格隔開）：不見君輸出：不查找成功！查找次數(shù)為：2見查找失?。〔檎掖螖?shù)為：3君查找成功！查找次數(shù)為：3輸入：請輸入文字（文字間可輸入空格）：小明我真不知道該輸入什么了請輸入查找的字們（中間用空格隔開）：你是小鴻嗎輸出：你查找成功！查找次數(shù)為：2是查找失敗！查找次數(shù)為：3小查找成功！查找次數(shù)為：3鴻查找失敗！查找次數(shù)為：3嗎查找成功！查找次數(shù)為：3概要設(shè)計1抽象數(shù)據(jù)類型將每一個元素儲存在

4、一個有序并且有限的序列中，每一個元素 都有一個自己的位置，也都有一個數(shù)據(jù)類型，所以使用 線性表來儲 存每一個文字。2. 線性表ADT數(shù)據(jù)對象：定義線性表的最大儲存元素maxsize;當(dāng)前儲存元素數(shù)listsize;數(shù)據(jù)關(guān)系：若listsize二0,則線性表沒有元素，為空；基本操作：alist(i nt n)構(gòu)造函數(shù)alist()析構(gòu)函數(shù)bool appe nd(i nt a)/增加元素bool getValue(i nt& it) con st / 獲得 it 位置線性表的值bool insert(int a)/插入元素3. 算法基本思想自組織線性表根據(jù)估算的訪問頻率排列記錄，先放置請

5、求頻率最 高的記錄，接下來是請求頻率次高的記錄，依此類推。自組織線性 表根據(jù)實際的記錄訪問模式在線性表中修改記錄順序。自組織線性 表使用啟發(fā)式規(guī)則決定如何重新排列線性表。轉(zhuǎn)置方法的基本原理是，在一次查找過程中，一旦找到一個記錄， 則將它與前一個位置的記錄交換位置。這樣，隨著時間的推移，經(jīng)常訪問的記錄將移動到線性表的前端，而曾經(jīng)頻繁使用但以后不再 訪問的記錄將逐漸退至線性表的后面4. 程序基本流程該程序主要分為輸入模塊，轉(zhuǎn)置查找模塊和輸出模塊（1）讀入模塊：從文件中讀入一組漢字集合，并保存在自組織 線性表中，讀入要查找的漢字。（2）轉(zhuǎn)置查找模塊：依次根據(jù)需查找的漢字對漢字線性表遍歷 一次進(jìn)行查找

6、，若查找到該漢字，調(diào)用轉(zhuǎn)置函數(shù)，將該漢 字與前一個位置的漢字轉(zhuǎn)置，然后繼續(xù)查找下一個漢字。（3）輸出模塊：若查找到漢字，則輸出到屏幕和文件中查找成 功并顯示查找次數(shù)；若沒有查找到該漢字，輸出到屏幕和 文件中查找不成功并顯示查找的次數(shù)。三詳細(xì)設(shè)計1物理數(shù)據(jù)類型本題中需要元素的交換，由于每個中文占用兩個字節(jié)的函數(shù), 使用數(shù)組交換只需要交換數(shù)組的兩個元素，較為便利，所以使用 序表來實現(xiàn)線性表。順序表的偽代碼class AListprivate:int listsize;int maxsize;int fen ce;Elem* listArray;public:AList（i nt size）maxs

7、ize = size;fence = listsize = 0;listArray = new Elemsize;AList() delete listArray; void setStart() fence = 0; void setE nd() fence = listsize; void prev() if (fence != 0) fen ce-; void n ext() if (fence <= listsize)fen ce+;bool getValue(Elem & it) const it = listArrayfe nee;return true;bool i

8、n sert(Elem item) if (listsize = maxsize) return false; for (int i = listsize; i > fen ce; i-) listArrayi = listArrayi - 1;listArrayfe nee = item;listsize+;return true;bool appe nd(Elem& item)if (listsize = maxsize)retur n false; listArraylistsize+ = item;return true;2算法的具體步驟順序表的構(gòu)建一一查找元素一一轉(zhuǎn)置順

9、序表的構(gòu)建：先將文字輸入到一個string類的字符串中，再將字 符串中每一個元素逐個賦值給順序表，值得注意的是中文每個字占 兩個字符串，在賦值時需要跳過空格，即線性表中值存儲文字。stri ng a;getline(cin, a);可輸入空格for (i nt i = 0; i < a.len gth(); i+)if (ai='')con ti nue;listArraylistsize = ai;listsize+;maxsize = listsize;return true;查找元素：輸入一組漢字，在順序表中比較查找，若為數(shù)組中的第 一個即是要找的漢字，則不處理(在

10、 swap函數(shù)里進(jìn)行判斷)，若不 是第一個，則將該漢字與前一個漢字在數(shù)組中的位置進(jìn)行交換，并輸出查找成功和比較的次數(shù)；若沒找到這個漢字，則輸出查找不成功 和查找的次數(shù)。并且注意跳過空格。void fin d()cout << "請輸入查找的字們(每個字間輸入空格)："<<e ndl;stri ng b;getl in e(c in, b);int i;int size = 0;for (i nt j = 0; j < b.le ngth(); j += 2)if (bj='')j-; con ti nue;int judge =

11、 0;for (i = 0; i <=listsize; i += 2)if (listArrayi = bj && listArrayi + 1 = bj + 1)judge = 1;swap(i);break;if (judge)cout«" “" <<bjvvbj+1vv" ” "<< "查找成功" << "查找 次數(shù)為："<< i/2+1 <<e ndl;elsecout << " “"

12、; << bj << bj + 1 << " ” " << "查找失敗"<< "查找次數(shù)為："<< i / 2 << endl;轉(zhuǎn)置：若果查找成功，則進(jìn)行轉(zhuǎn)置，因為中文占兩個字符，所以需 要將兩個字符轉(zhuǎn)置。如果需要轉(zhuǎn)置的中午是開頭，就不需要轉(zhuǎn)置直 接返回true。bool swap (nt n)if (n <= 1)return true;Elem temp;temp = listArray n;listArray n = listArray n

13、 - 2;listArray n - 2 = temp;temp = listArray n+1;listArray n + 1 = listArray n - 1;listArray n -1 = temp;return 0;3.算法時空分析n個漢字，查找n次，時間復(fù)雜度為O （n）4. 輸入輸出格式.輸入請輸入文字（文字間可輸入空格）：cout << "請輸入文字（文字間可輸入空格）："<< endl;stri ng a;getli ne（cin, a）;可輸入空格請輸入查找的字們（中間用空格隔開）：cout << "請輸入

14、查找的字們(每個字間輸入空格)："<<e ndl;stri ng b;getl in e(ci n, b);.輸出查找成功，顯示查找次數(shù):if (judge)cout«" “" <<bjvvbj+1vv" ” "<< "查找成功"<< 次數(shù)為："<< i/2+1 <<e ndl;查找查找失敗，顯示查找次數(shù):elsecout << " “" << bj << bj + 1 <

15、< "” "<< "查找失敗 "查找次數(shù)為："<< i / 2 << endl;"<<四.測試結(jié)果.測試1彥找;熾為: 査我戊數(shù)為: 吉找軸為:査找左數(shù)為: 直找軸為:32114測試2測試3測試4測試5EAmy c»A救學(xué)揭祁J自迥織級性表DEbug、自組妃線性表吏尬諸愉入文字（文字間可輸入空格）:査找次數(shù)為：14 査找次針加14 查找劉為：1 查找軸為：14 査找次費(fèi)為:14卜明我耳不韌通蒯J+么了 請隔入査我的字們每個字間輸入空格， 你罡小鴻嗎-早"敘川|嚴(yán)

16、ja奩找失敗査找失敗 查找成功 藝找失敗 查找失敗請按任童鍵繼續(xù)，五實驗心得書上順序表定義完整，題目難度不大，較前幾次試驗，比較簡單六附錄#in elude <fstream>#in cludevstri ng>#i nclude"iostream"using n amespace std;#defi ne Elem charclass AListprivate:int listsize;int maxsize;int fen ce;Elem* listArray;public:AList(i nt size)maxsize = size;fence =

17、listsize = 0;listArray = new Elemsize;AList() delete listArray; void setStart() fence = 0; void setE nd() fence = listsize; void prev() if (fence != 0) fen ce-; void n ext() if (fence <= listsize)fen ce+;bool getValue(Elem & it) const it = listArrayfe nee;return true;bool in sert(Elem item) i

18、f (listsize = maxsize) return false;for (int i = listsize; i > fen ce; i-)listArrayi = listArrayi - 1;listArrayfe nee = item;listsize+;return true;bool appe nd(Elem& item)if (listsize = maxsize)retur n false; listArraylistsize+ = item;return true;bool star()"<< endl;eout << &

19、quot;請輸入文字(文字間可輸入空格)：stri ng a;getline(ein, a);可輸入空格for (i nt i = 0; i < a.len gth(); i+)if (ai='')con ti nue;listArraylistsize = ai;listsize+;maxsize = listsize;return true; void fin d()cout << "請輸入查找的字們(每個字間輸入空格)："<<e ndl;stri ng b;getl in e(c in, b);int i;int size = 0;for (i nt j = 0; j < b.le ngth(); j += 2)if (bj='')j-; con ti nue;int judge = 0;for (i = 0; i <=listsize; i += 2)if (listArrayi = bj &&