欧美vvv,亚洲第一成人在线,亚洲成人欧美日韩在线观看,日本猛少妇猛色XXXXX猛叫

寫在前面

這個新的類別主要是將平時學的數據結構的知識概念與數據結構引發的各種算法進行一個整理總結。這一個類別參考的資料是《大話數據結構》。由于PDF是掃描版，所以主要內容都是手打，比較麻煩，會耗費一些時間。所以主要是要提綱挈領，將要點整理出來，以便在做題的時候，能將這些知識融會貫通一下。畢竟不能當個只會復制粘貼的碼農，還是要花費時間與精力來提升一下自己的知識水平。

數據結構算法的學習我不會按照資料的順序，照本宣科的講，只會按照做題的順序來一步步學習。由于做題剛剛做完了Hash Table的簡單題目。所以就先來學習一下“查找”這一部分的知識。

查找概論

查找表( Table)： 是由同一類型的數據元素（或記錄）構成的集合。說白了，就是一張表，要查找的數據都在這里面。

關鍵字(Key)： 是數據元素中某個數據項的值，又稱為鍵值，可以用它來表示一個數據元素。也可以表示一個記錄的某個數據項（字段），稱之為關鍵碼。如果關鍵字可以唯一標識一個記錄，則稱之為主關鍵字( Key)。可以表示多個數據元素（或記錄）的關鍵字，稱之為次關鍵字( Key)。

查找()： 根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素（或記錄）。

查找表根據操作方式可以分為兩大類：靜態查找表與動態查找表。

靜態查找表( Table)： 只作查找操作的查找表。其主要操作有：

動態查找表( Table)： 在查找過程中同時插入查找表中不存在的數據元素，或者從查找表中刪除已經存在的某個數據元素。其主要操作有：

查找所基于的數據結構是集合，集合中的記錄之間沒有本質關系。所以要想獲得較高的查找性能，我們需要將查找集合組織成表、樹等結構。對于靜態查找表來說，可以使用線性表結構來組織數據；對于動態查找表來說，可以考慮二叉排序樹的查找技術。最后還可以使用散列表結構來解決一些查找問題，這就是哈希表。

順序表查找

順序查找( )： 就是線性查找，也是最基本的查找技術，其查找過程是：從表中第一個（或最后一個）記錄開始，逐個進行記錄的關鍵字和給定值比較，若某個記錄的關鍵字與給定值相等，則查找成功。如果直到最后一個（或第一個）記錄，關鍵字與給定值比較都不等，則表中沒有所查的記錄，查找不成功。

順序表查找算法 ：順序查找的算法實現如下：

int Sequentital_Search(int *a,int n, int key){
    for(int i=0;iif(a[i]==key)
            return i;
    }
    return 0;
}

這段代碼就很基礎，也是很常用的普遍遍歷算法。但是，這個算法也還有改進的地方，就是因為每一次要做兩次比較：一次是i與n比較，檢查i是否越界；一次是a[i]與key比較，檢查是否查找成功。那么能不能簡化這樣的比較呢？可以設置一個哨兵，減少i與n的比較。優化算法如下：

int Sequentital_Search(int *a,int n, int key){
    int i=n;
    a[0]=sentinel;
    while(a[i]!=sentinel){
        i--;
    }
    return i;       //這里返回0說明查找失敗
}

這段優化的代碼不僅減少了i與n的比較，還通過反轉遍歷順序，將優化前的算法需要返回兩種不同的情況，簡化成一種。代碼更加簡介美觀了。

順序查找算法的平均查找次數是：(n+1)/2；時間復雜度為：O(n)。

有序表查找

折半查找( )，二分查找： 前提設定線性表中記錄必須是關鍵碼有序（常為從小到大），線性表采用順序存儲。二分查找基本思想是：在有序表中，取中間記錄作為比較對象，若給定值與中間記錄的關鍵字相等，則查找成功；若小于順序查找平均時間復雜度，則在中間記錄的左半區繼續查找；若大于，則在中間記錄的右半區繼續查找。不管重復上述過程直到查找成功順序查找平均時間復雜度，或所有查找區域無記錄，即查找失敗。

算法實現代碼如下：

int Binary_Search(int *a, int n, int key){
    int low = 1,high = n,mid;
    while(low <= high){
        mid=(low + high) / 2;
        if(key < a[mid]) 
            high=mid - 1;
        else if(key > a[mid]) 
            low=mid + 1;
        else 
            return mid;
    }
    return 0;
}

二分查找等于是把靜態有序查找表分成了兩顆子樹，即查找結果只需要找其中一半數據記錄即可，相等于工作量少了一半，而后不斷重復，從而提升了查找效率，降低了算法復雜度。二分查找的最壞情況查詢次數是：log2n+1。時間復雜度是：O(logn)。

插值查找

雖然二分查找與順序查找相比提高了提高了效率，但是，二分查找太具有一般性，比如0~，查找5，如果還是二分查找，那么首先還是會查找50000。而如果能直接從下標較小的情況開始查找，比如找100，那么效率可能會進一步提高。將二分查找的mid的公式變換有：

插值查找就是對公式進行改進。

插值查找( )是根據要查找的關鍵字key與查找表中最大最小記錄的關鍵字比較后的查找方法，其核心就在于插值的計算公式：

從時間復雜度來看也是：O(logn)。對于關鍵字分布比較均勻的查找表來說，插值查找算法的平均性能比二分查找要好多。但如果數組中關鍵字分布不均勻，或者說數組存在很多極端大或小的樹，就不合適了。

斐波那契查找

斐波那契查找( )： 是利用了黃金分割原理來實現的。

int Fibonacci_Search(int ^a, int n, int key){
    int low=1 ,high=n ,mid,i, k=0;     //定義最低下標與最高下標為記錄首位與記錄末位
    while(n>F[k]-1)                    //計算n位于斐波那契數列的位置
        k++;
    for(i=m;i1;i++)              //將不滿的數字補全
        a[i]=a[n];
    while(low<=high){
        mid=low+F[k-1]-1;              //計算當前分隔的下標
        if(key//若查找記錄小于當前分隔記錄
            high=mid-1;                //最高下標調整到分隔下標mid-1處
            k=k-1;                     //斐波那契數列下標減一位,此時1位
        }
        else if(key>a[mid]){           //若查找記錄大于當前分隔記錄
            low=mid+1;                 //最低下標調整到分隔下標mid+1處
            k=k-2;                     //斐波那契數列下標減兩位，此時2位
        }
        else{
            if(mid<=n)
                return mid;            //若相等說明mid即為查找結果
            else
                return n;              //若mid>n說明是補全數值，返回n
        }
    }
}