自組織線性表

1、背景自組織線性表根據(jù)估算的訪問頻率排列記錄，先放置請求頻率最高的記錄，接下來是請 求頻率次高的記錄，依此類推。自組織線性表根據(jù)實(shí)際的記錄訪問模式在線性表中修改記錄 順序。自組織線性表使用啟發(fā)式規(guī)則決定如何重新排列線性表。轉(zhuǎn)置方法的基本原理是，在 一次查找過程中，一旦找到一個(gè)記錄，則將它與前一個(gè)位置的記錄交換位置。這樣，隨著時(shí) 間的推移，經(jīng)常訪問的記錄將移動(dòng)到線性表的前端，而曾經(jīng)頻繁使用但以后不再訪問的記錄 將逐漸退至線性表的后面。盡管一般情況下自組織線性表的效率可能沒有查找數(shù)和已排序的線性表那么好，但它也 有自身的優(yōu)勢。它可以不必對線性表進(jìn)行排序，新記錄的插入代價(jià)很??；同時(shí)也比查找樹更 容易實(shí)

2、現(xiàn)，且無需額外的存儲(chǔ)空間。問題描述用轉(zhuǎn)置法實(shí)現(xiàn)一個(gè)自組織線性表，保存一組漢字用于查詢。基本要求（1）從文件中讀入一組漢字集合，用自組織線性表保存。（2）在查詢時(shí)，采用轉(zhuǎn)置法調(diào)整自組織線性表的內(nèi)容。（3）從文件中依次讀入需查詢的漢字，把查詢結(jié)果保存在文件中（如找到，返回比 較的次數(shù)，如果沒有找到，返回比較的次數(shù)）需求分析（1）輸入的形式：輸入漢字的個(gè)數(shù)n,n為大于0的正整數(shù)，并輸入一組漢字；（2） 輸出的形式：輸出是否找到（查詢成功查找不成功）和比較的次數(shù)；（3）程序所達(dá)到的功能：本程序可以通過用戶從鍵盤中輸入漢字個(gè)數(shù)n和n個(gè)漢字進(jìn)行 保存，然后用戶通過輸入漢字對儲(chǔ)存的漢字進(jìn)行訪問，對n個(gè)漢字根

3、據(jù)估算的訪問 頻率進(jìn)行排序，并輸出查詢的漢字是否查找成功和查詢的次數(shù)的信息；但是該程序 不處理有相同字的一組漢字：（4）測試數(shù)據(jù)：輸入：5漢字的個(gè)數(shù)請輸入一組漢字：我是中國人請輸入查找的漢字：中國輸出：中查詢成功3/比較的次數(shù)輸出：國查詢成功4/比較的次數(shù)概要設(shè)計(jì)：抽象數(shù)據(jù)類型的定義：因?yàn)閿?shù)據(jù)對象和數(shù)據(jù)關(guān)系符合線性表的數(shù)據(jù)結(jié)構(gòu)，可以 采用線性表數(shù)據(jù)結(jié)構(gòu)。線性表的ADT：數(shù)據(jù)對象：D= ai I ai EElemSet, i=1,2,.,n, n30 （ 稱n為線性表的表長；稱n=0時(shí)的線性表為空表。數(shù)據(jù)關(guān)系：R1 = |ai-1 ,aiED, i=2,.,n 基本操作：void Creat(l

4、ink *l)創(chuàng)建新的線性表void swap(link *l,int i,int j)/交換兩個(gè)元素bool find(link *l,char *s)/查找基本算法思想：自組織線性表根據(jù)估算的訪問頻率排列記錄，先放置請求頻率最 高的記錄，接下來是請求頻率次高的記錄，依此類推。自組織線性表根據(jù)實(shí)際的 記錄訪問模式在線性表中修改記錄順序。自組織線性表使用啟發(fā)式規(guī)則決定如何 重新排列線性表。轉(zhuǎn)置方法的基本原理是，在一次查找過程中，一旦找到一個(gè)記錄，則將它與前一 個(gè)位置的記錄交換位置。這樣，隨著時(shí)間的推移，經(jīng)常訪問的記錄將移動(dòng)到線性 表的前端，而曾經(jīng)頻繁使用但以后不再訪問的記錄將逐漸退至線性表的后

5、面程序的流程：程序由三個(gè)模塊組成：輸入模塊：漢字個(gè)數(shù)的輸入及需保存的漢字序列的輸入排序模塊：輸入查詢的漢字，查詢時(shí)進(jìn)行自組織線性表排序輸出模塊：輸出查詢是否成功和查詢的次數(shù)詳細(xì)設(shè)計(jì)：(1)物理數(shù)據(jù)類型：由于自組織線性表中元素的位置與元素的訪問頻率有關(guān)，可 以采用專制的方法來實(shí)現(xiàn)自組織線性表，也就是把找到的記錄與它在線性表 中的前一條記錄交換位置，隨著時(shí)間的推移把最常用的記錄移動(dòng)到線性表的 前面。定義數(shù)組：typedef struct Node/保 存漢字char data3;Node;typedef struct link/線性表Node *node;int length;link;void

6、Creat(link *l)創(chuàng)建新的線性表的偽代碼：void Creat(link *l)coutl-length;l-node=(Node *)malloc(l-length*sizeof(Node);coutlength”漢字”； getchar();for(int i=0;ilength;i+)gets(l-nodei.data);void swap(link *l,int i,int j)/交換兩個(gè)元素的偽代碼：void swap(link *l,int i,int j)char s3;strcpy(s,l-nodei.data);strcpy(l-nodei.data,l-nodej

7、.data);strcpy(l-nodej.data,s);bool find(link *l,char *s)/查找的偽代碼：bool find(link *l,char *s)for(int i=0;ilength;i+)if(!strcmp(s,l-nodei.data)if(i!=0)swap(l,i,i-1);cout”查找成功”；couti+1endl;比較的次數(shù)return true;return false;cout ”查找不成功”；couti+1endl;/ 比較的次數(shù)算法的具體步驟：第一步 獲取漢字個(gè)數(shù)n及n個(gè)漢字，建立n為長度的漢字?jǐn)?shù)組第二步輸入一個(gè)漢字，在數(shù)組中比較查找，若為數(shù)組中的第一個(gè)即是要 找的漢字，則不處理，若不是第一個(gè)，則將該漢字與前一個(gè)漢字在數(shù)組中 的位置進(jìn)行交換，并輸出查找成功和比較的次數(shù)；若沒找到這個(gè)漢字，則 輸出查找不成功和查找的次數(shù)；第三步重復(fù)執(zhí)行第二步操作或者結(jié)束查找算法的時(shí)間分析