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

2、現，且無需額外的存儲空間。問題描述用轉置法實現一個自組織線性表，保存一組漢字用于查詢?；疽螅?）從文件中讀入一組漢字集合，用自組織線性表保存。（2）在查詢時，采用轉置法調整自組織線性表的內容。（3）從文件中依次讀入需查詢的漢字，把查詢結果保存在文件中（如找到，返回比 較的次數，如果沒有找到，返回比較的次數）需求分析（1）輸入的形式：輸入漢字的個數n,n為大于0的正整數，并輸入一組漢字；（2） 輸出的形式：輸出是否找到（查詢成功查找不成功）和比較的次數；（3）程序所達到的功能：本程序可以通過用戶從鍵盤中輸入漢字個數n和n個漢字進行 保存，然后用戶通過輸入漢字對儲存的漢字進行訪問，對n個漢字根

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

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

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

6、Creat(link *l)創建新的線性表的偽代碼：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)/交換兩個元素的偽代碼：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;比較的次數return true;return false;cout ”查找不成功”；couti+1endl;/ 比較的次數算法的具體步驟：第一步 獲取漢字個數n及n個漢字，建立n為長度的漢字數組第二步輸入一個漢字，在數組中比較查找，若為數組中的第一個即是要 找的漢字，則不處理，若不是第一個，則將該漢字與前一個漢字在數組中 的位置進行交換，并輸出查找成功和比較的次數；若沒找到這個漢字，則 輸出查找不成功和查找的次數；第三步重復執行第二步操作或者結束查找算法的時間分析