查找 - 查找的基本概念

　　本章簡介

　　由於查找運算的使用頻率很高幾乎在任何一個計算機系統軟件和應用軟件中都會涉及到所以當問題所涉及的數據量相當大時

　　查找方法的效率就顯得格外重要在一些實時查詢系統中尤其如此因此本章將系統地討論各種查找方法並通過對它們的效率

　　分析來比較各種查找方法的優劣

　　查找的基本概念

　　查找表和查找

　　一般假定被查找的對象是由一組結點組成的表(Table)或文件而每個結點則由若干個數據項組成並假設每個結點都有一個

　　能惟一標識該結點的關鍵字

　　查找(Searching)的定義是給定一個值K在含有n個結點的表中找出關鍵字等於給定值K的結點若找到則查找成功返回該

　　結點的信息或該結點在表中的位置;否則查找失敗返回相關的指示信息

　　查找表的數據結構表示

　　()動態查找表和靜態查找表

　　若在查找的同時對表做修改操作(如插入和刪除)則相應的表稱之為動態查找表否則稱之為靜態查找表

　　()內查找和外查找

　　和排序類似查找也有內查找和外查找之分若整個查找過程都在內存進行則稱之為內查找;反之若查找過程中需要訪問外

　　存則稱之為外查找

　　平均查找長度ASL

　　查找運算的主要操作是關鍵字的比較所以通常把查找過程中對關鍵字需要執行的 平均比較次數(也稱為平均查找長度)作為衡量

　　一個查找算法效率優劣的標准

　　平均查找長度 ASL(Average Search Length)定義為

　　

　　其中

　　①n是結點的個數;

　　②P i 是查找第i個結點的概率若不特別聲明認為每個結點的查找概率相等即

　　p l =p …=p n =/n

　　③c i 是找到第i個結點所需進行的比較次數

　　注意

　　為了簡單起見假定表中關鍵字的類型為整數

　　typedef int KeyType; //KeyType應由用戶定義

From:http://tw.wingwit.com/Article/program/sjjg/201311/23606.html