自組織線性表.doc

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