自組織線性表

背景自組織線性表根據(jù)估算的訪問頻率排列記錄，先放置請求頻率最高的記錄，接下來是請求頻率次高的記錄，依此類推。自組織線性表根據(jù)實際的記錄訪問模式在線性表中修改記錄順序。自組織線性表使用啟發(fā)式規(guī)則決定如何重新排列線性表。轉(zhuǎn)置方法的基本原理是，在一次查找過程中，一旦找到一個記錄，則將它與前一個位置的記錄交換位置。這樣，隨著時間的推移，經(jīng)常訪問的記錄將移動到線性表的前端，而曾經(jīng)頻繁使用但以后不再訪問的記錄將逐漸退至線性表的后面。盡管一般情況下自組織線性表的效率可能沒有查找數(shù)和已排序的線性表那么好,但它也有自身的優(yōu)勢。它可以不必對線性表進行排序，新記錄的插入代價很??；同時也比查找樹更容易實現(xiàn)，且無需額外的存儲空間。問題描述用轉(zhuǎn)置法實現(xiàn)一個自組織線性表，保存一組漢字用于查詢?；疽髲奈募凶x入一組漢字集合，用自組織線性表保存。在查詢時，采用轉(zhuǎn)置法調(diào)整自組織線性表的內(nèi)容。從文件中依次讀入需查詢的漢字，把查詢結(jié)果保存在文件中(如找到，返回比較的次數(shù)，如果沒有找到，返回比較的次數(shù))需求分析輸入的形式：輸入漢字的個數(shù)n,n為大于0的正整數(shù)，并輸入一組漢字；輸出的形式：輸出是否找到(查詢成功\\查找不成功)和比較的次數(shù)；程序所達到的功能：本程序可以通過用戶從鍵盤中輸入漢字個數(shù)n和n個漢字進行保存，然后用戶通過輸入漢字對儲存的漢字進行訪問，對n個漢字根據(jù)估算的訪問頻率進行排序，并輸出查詢的漢字是否查找成功和查詢的次數(shù)的信息；但是該程序不處理有相同字的一組漢字：測試數(shù)據(jù)：輸入：5〃漢字的個數(shù)請輸入一組漢字：我是中國人請輸入查找的漢字：中國輸出：中查詢成功3〃比較的次數(shù)輸出：國查詢成功4〃比較的次數(shù)概要設(shè)計：抽象數(shù)據(jù)類型的定義：因為數(shù)據(jù)對象和數(shù)據(jù)關(guān)系符合線性表的數(shù)據(jù)結(jié)構(gòu)，可以采用線性表數(shù)據(jù)結(jié)構(gòu)。線性表的ADT：數(shù)據(jù)對象：D={aiIaiUElemSet,i=1,2,...,n,n三0}{稱n為線性表的表長；稱n=0時的線性表為空表。}數(shù)據(jù)關(guān)系：R1={vai-1,ai>lai-1,aiUD,i=2,...,n}基本操作：voidCreat(link*1)//創(chuàng)建新的線性表voidswap(1ink*1,inti,intj)//交換兩個元素boolfind(1ink*1,char*s)〃查找基本算法思想：自組織線性表根據(jù)估算的訪問頻率排列記錄，先放置請求頻率最高的記錄，接下來是請求頻率次高的記錄，依此類推。自組織線性表根據(jù)實際的記錄訪問模式在線性表中修改記錄順序。自組織線性表使用啟發(fā)式規(guī)則決定如何重新排列線性表。轉(zhuǎn)置方法的基本原理是，在一次查找過程中，一旦找到一個記錄，則將它與前一個位置的記錄交換位置。這樣，隨著時間的推移，經(jīng)常訪問的記錄將移動到線性表的前端，而曾經(jīng)頻繁使用但以后不再訪問的記錄將逐漸退至線性表的后面程序的流程：程序由三個模塊組成：1?輸入模塊：漢字個數(shù)的輸入及需保存的漢字序列的輸入2?排序模塊：輸入查詢的漢字，查詢時進行自組織線性表排序3?輸出模塊：輸出查詢是否成功和查詢的次數(shù)三?詳細(xì)設(shè)計：(1)物理數(shù)據(jù)類型：由于自組織線性表中元素的位置與元素的訪問頻率有關(guān)，可以采用專制的方法來實現(xiàn)自組織線性表，也就是把找到的記錄與它在線性表中的前一條記錄交換位置，隨著時間的推移把最常用的記錄移動到線性表的定義數(shù)組：typedefstructNode//保存漢字{chardata[3];}Node;typedefstructlink//線性表{Node*node;intlength;}1ink;voidCreat(1ink*1)//創(chuàng)建新的線性表的偽代碼：voidCreat(1ink*1){coutvv"請輸入漢字的個數(shù)：";cin>>1->1ength;1->node=(Node*)ma11oc(1->1ength*sizeof(Node));coutvv"請輸入”vv1->1ength<<”漢字"；getchar();for(inti=0;i<1->1ength;i++)gets(l->node[i].data);}voidswap(link*l,inti,intj)//交換兩個元素的偽代碼：voidswap(link*l,inti,intj){chars[3];strcpy(s,l->node[i].data);strcpy(l->node[i].data,l->node[j].data);strcpy(l->node[j].data,s);}boolfind(link*l,char*s)〃查找的偽代碼：boolfind(link*l,char*s){for(inti=O;ivl->length;i++){if(!strcmp(s,l->node[i].data)){if(i!=0)swap(l,i,i-1);coutvv”查找成功”；coutvvi+lvvendl;〃比較的次數(shù)returntrue;}}returnfalse;cout<v”查找不成功”；coutvvi+1vvendl;〃比較的次數(shù)}算法的具體步驟：第一步獲取漢字個數(shù)n及n個漢字，建立n為長度的漢字?jǐn)?shù)組第二步輸入一個漢字，在數(shù)組中比較查找，若為數(shù)組中的第一個即是要找的漢字，則不處理，若不是第一個，則將該漢字與前一個漢字在數(shù)組中的位置進行交換，并輸出查找成功和比較的次數(shù)；若沒找到這個漢字，則輸出查找不成功和查找的次數(shù)；第三步重復(fù)執(zhí)行第二步操作或者結(jié)束查找算法的時間分析：由于該算法主要用于漢字的查找，故時間代價為(