數據結構作業(yè)——分塊查找算法.doc

《數據結構作業(yè)——分塊查找算法.doc》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、數據結構實驗報告三題目：試編寫利用折半查找確定記錄所在塊的分塊查找算法。提示：1)讀入各記錄建立主表；2)按L個記錄/塊建立索引表；3)對給定關鍵字k進行查找；測試實例：設主表關鍵字序列：{12221382833384287765063991019796}，L=4，依次查找K=13，K=86，K=88算法思路題意要求對輸入的關鍵字序列先進行分塊，得到分塊序列。由于序列不一定有序，故對分塊序列進行折半查找，找到關鍵字所在的塊，然后對關鍵字所在的塊進行順序查找，從而找到關鍵字的位置。故需要折半查找和順序查找兩個函數，考慮用C++中的類函數實現。因為序列一般是用數組進行存儲的，這樣可以調用

2、不同類型的數組，程序的可適用性更大一些。折半查找函數：ints,d,ss,dd;//聲明一些全局變量，方便函數與主函數之間的變量調用。templateintBinSearch(TA[],intlow,inthigh,Tkey)//遞歸實現折半查找{intmid;//初始化中間值的位置Tmidvalue;//初始化中間值if(low>high){s=A[high];d=A[low];ss=high;dd=low;return-1;}//如果low的值大于high的值，輸出-1，并且將此時的low與high的值存儲。else{mid=(low+high)/2;//中間位置

3、為低位與高位和的一半取整。midvalue=A[mid];if(midvalue==key)returnmid;elseif(midvalueintshuxuSearch(TA[],

4、inthigh,Tkey)//順序查找{inti=0;A[high]=key;//初始化i，使A的最高位為key值while(A[i]!=key)i++;returni;//如果A中有key值，則在i不到n+1時就會輸出，否則，返回high值，說明搜索失敗。}主函數中，首先對所需要的參數變量進行初始化，由鍵盤輸入關鍵字，分塊的多少，每一塊有多少個關鍵字。為了用戶的人性化考慮，這里由用戶自己決定分塊的多少和數目。為了實現這一功能，引入了一個動態(tài)存儲的二維數組：int**p2;p2=newint*[row];//聲明一個二維數組for(i=0;i

5、[col];for(i=0;i=M[i])M[i]=p2[i][j];}cout<

6、保證可以多次查找并輸出結果。在關鍵字等信息輸入完畢后，進行查找，可以得到該關鍵字所在塊的序號，以及該關鍵字在整個關鍵字序列中的位置。程序結構源代碼：#includeusingnamespacestd;ints,d,ss,dd;//聲明一些全局變量，方便函數與主函數之間的變量調用。templateintBinSearch(TA[],intlow,inthigh,Tkey)//遞歸實現折半查找{intmid;//初始化中間值的位置Tmidvalue;//初始化中間值if(low>high){s=A[high];d=A[low];ss=high;dd=l

7、ow;return-1;}//如果low的值大于high的值，輸出-1，并且將此時的low與high的值存儲。else{mid=(low+high)/2;//中間位置為低位與高位和的一半取整。midvalue=A[mid];if(midvalue==key)returnmid;elseif(midvalue