自組織線性表.doc

題目：自組織線性表 背景自組織線性表根據(jù)估算的訪問(wèn)頻率排列記錄，先放置請(qǐng)求頻率最高的記錄，接下來(lái)是請(qǐng)求頻率次高的記錄，依此類推。自組織線性表根據(jù)實(shí)際的記錄訪問(wèn)模式在線性表中修改記錄順序。自組織線性表使用啟發(fā)式規(guī)則決定如何重新排列線性表。轉(zhuǎn)置方法的基本原理是，在一次查找過(guò)程中，一旦找到一個(gè)記錄，則將它與前一個(gè)位置的記錄交換位置。這樣，隨著時(shí)間的推移，經(jīng)常訪問(wèn)的記錄將移動(dòng)到線性表的前端，而曾經(jīng)頻繁使用但以后不再訪問(wèn)的記錄將逐漸退至線性表的后面。盡管一般情況下自組織線性表的效率可能沒有查找數(shù)和已排序的線性表那么好，但它也有自身的優(yōu)勢(shì)。它可以不必對(duì)線性表進(jìn)行排序，新記錄的插入代價(jià)很??；同時(shí)也比查找樹更容易實(shí)現(xiàn)，且無(wú)需額外的存儲(chǔ)空間。問(wèn)題描述 用轉(zhuǎn)置法實(shí)現(xiàn)一個(gè)自組織線性表，保存一組漢字用于查詢?；疽?（1） 從文件中讀入一組漢字集合，用自組織線性表保存。（2） 在查詢時(shí)，采用轉(zhuǎn)置法調(diào)整自組織線性表的內(nèi)容。（3） 從文件中依次讀入需查詢的漢字，把查詢結(jié)果保存在文件中（如找到，返回比較的次數(shù)，如果沒有找到，返回比較的次數(shù)） 實(shí)驗(yàn)分析：題目要求用轉(zhuǎn)置方法實(shí)現(xiàn)自組織線性表，也就是把找到的記錄與它在線性表中的前一條記錄交換位置，隨著時(shí)間的推移把最常用的記錄移動(dòng)到線性表的前面。函數(shù)void transpose(char a2,int i,int j)實(shí)現(xiàn)字符串的交換位置。int search(char a2,int size,char c2)函數(shù)用于查找是否有相應(yīng)的字符，在自組織線性表中。實(shí)驗(yàn)代碼：#includeusing namespace std;bool flag;void transpose(char a2,int i,int j); /轉(zhuǎn)置函數(shù)的聲明int search(char a2,int size,char c2);/search函數(shù)的聲明int main() int i,m,n,num; static char a2002,b2002,c2; cina0;for(i=0;i+)if(ai0=0)break; m=i; cinb0;for(i=0;i+) if(bi0=0)break; n=i; for(i=0;in;i+) num=search(a,m,bi); c0=bi0; c1=bi1; if(flag) cout查找c成功,查找次數(shù)為：numendl; else cout查找c失敗,查找次數(shù)為：numendl; system(pause); return 0; void transpose(char a2,int i,int j) /轉(zhuǎn)置函數(shù)的定義 char temp=ai0; ai0=aj0; aj0=temp; temp=ai1; ai1=aj1; aj1=temp; int search(char a2,int size,char c2) /查找字符串函數(shù) flag=0; int i; for(