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

2、敗，比較次數(shù)為。4.測試數(shù)據(jù)數(shù)據(jù)1：請輸入文字（文字間可輸入空格）：我愛你 中國請輸入查找的字們（中間用空格隔開）：你 你 你 你 中 國輸出： 你 查找成功！查找次數(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

4、小 查找成功！查找次數(shù)為：3鴻 查找失敗！查找次數(shù)為：3嗎 查找成功！查找次數(shù)為：3二概要設(shè)計 1.抽象數(shù)據(jù)類型將每一個元素儲存在一個有序并且有限的序列中，每一個元素都有一個自己的位置，也都有一個數(shù)據(jù)類型，所以使用線性表來儲存每一個文字。 2.線性表ADT數(shù)據(jù)對象：定義線性表的最大儲存元素maxsize; 當前儲存元素數(shù)listsize;數(shù)據(jù)關(guān)系：若listsize=0,則線性表沒有元素，為空;基本操作：alist(int n)/構(gòu)造函數(shù) alist()/析構(gòu)函數(shù) bool append(int a)/增加元素 bool getValue(int& it) const /獲得it位置線性表的值

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

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

7、t fence;Elem* listArray;public:AList(int size)maxsize = size;fence = listsize = 0;listArray = new Elemsize;AList() delete listArray; void setStart() fence = 0; void setEnd() fence = listsize; void prev() if (fence != 0) fence-; void next() if (fence fence; i-)listArrayi = listArrayi - 1;listArrayfen

8、ce = item; listsize+;return true;bool append(Elem& item)if (listsize = maxsize)return false;listArraylistsize+ = item;return true;2.算法的具體步驟順序表的構(gòu)建查找元素轉(zhuǎn)置順序表的構(gòu)建：先將文字輸入到一個string類的字符串中，再將字符串中每一個元素逐個賦值給順序表，值得注意的是中文每個字占兩個字符串，在賦值時需要跳過空格，即線性表中值存儲文字。string a;getline(cin, a);/可輸入空格for (int i = 0; i a.length();

9、 i+)if (ai = )continue;listArraylistsize = ai;listsize+;maxsize = listsize;return true;查找元素：輸入一組漢字，在順序表中比較查找，若為數(shù)組中的第一個即是要找的漢字，則不處理（在swap函數(shù)里進行判斷），若不是第一個，則將該漢字與前一個漢字在數(shù)組中的位置進行交換,并輸出查找成功和比較的次數(shù)；若沒找到這個漢字，則輸出查找不成功和查找的次數(shù)。并且注意跳過空格。void find()cout 請輸入查找的字們（每個字間輸入空格）：endl;string b;getline(cin, b);int i;int siz

10、e = 0;for (int j = 0; j b.length(); j += 2)if (bj = )j-; continue;int judge = 0;for (i = 0; i =listsize; i += 2)if (listArrayi = bj & listArrayi + 1 = bj + 1)judge = 1;swap(i);break;if (judge)cout“ bjbj+1” 查找成功 查找次數(shù)為： i/2+1 endl;elsecout “ bj bj + 1 ” 查找失敗 查找次數(shù)為： i / 2 endl;轉(zhuǎn)置：若果查找成功，則進行轉(zhuǎn)置，因為中文占兩個字符

11、，所以需要將兩個字符轉(zhuǎn)置。如果需要轉(zhuǎn)置的中午是開頭，就不需要轉(zhuǎn)置直接返回true。bool swap(int n)if (n = 1)return true;Elem temp;temp = listArrayn;listArrayn = listArrayn - 2;listArrayn - 2 = temp;temp = listArrayn+1;listArrayn + 1 = listArrayn - 1;listArrayn - 1 = temp;return 0; 3.算法時空分析 n個漢字，查找n次，時間復(fù)雜度為O（n）。4. 輸入輸出格式輸入 請輸入文字（文字間可輸入空格）：c

12、out 請輸入文字（文字間可輸入空格）： endl;string a;getline(cin, a);/可輸入空格請輸入查找的字們（中間用空格隔開）：cout 請輸入查找的字們（每個字間輸入空格）：endl;string b;getline(cin, b);輸出查找成功，顯示查找次數(shù)：if (judge)cout“ bjbj+1” 查找成功 查找次數(shù)為： i/2+1 endl;查找失敗，顯示查找次數(shù)：elsecout “ bj bj + 1 ” 查找失敗 查找次數(shù)為： i / 2 endl;4 測試結(jié)果測試1測試2測試3測試4測試55 實驗心得書上順序表定義完整，題目難度不大，較前幾次試驗，比

13、較簡單。六附錄#include #include#includeiostreamusing namespace std;#define Elem charclass AListprivate:int listsize;int maxsize;int fence;Elem* listArray;public:AList(int size)maxsize = size;fence = listsize = 0;listArray = new Elemsize;AList() delete listArray; void setStart() fence = 0; void setEnd() fen

14、ce = listsize; void prev() if (fence != 0) fence-; void next() if (fence fence; i-)listArrayi = listArrayi - 1;listArrayfence = item; listsize+;return true;bool append(Elem& item)if (listsize = maxsize)return false;listArraylistsize+ = item;return true;bool star()cout 請輸入文字（文字間可輸入空格）： endl;string a;

15、getline(cin, a);/可輸入空格for (int i = 0; i a.length(); i+)if (ai = )continue;listArraylistsize = ai;listsize+;maxsize = listsize;return true;void find()cout 請輸入查找的字們（每個字間輸入空格）：endl;string b;getline(cin, b);int i;int size = 0;for (int j = 0; j b.length(); j += 2)if (bj = )j-; continue;int judge = 0;for (i = 0; i =listsize; i += 2)if (listArrayi = bj & listArrayi + 1 = bj + 1)judge = 1;swap(i);break;if (judge)cout“ bjbj+1” 查找成功 查找次數(shù)為： i/2+1 endl;elsecout “ bj bj + 1 ” 查找失敗 查找次數(shù)為： i / 2 endl;bool swap(int n)