數(shù)據(jù)結(jié)構(gòu)之查找課件-wenkub
2022-08-20 09:41:47 本頁面
【正文】 在的塊，然后在塊內(nèi)查找待查的數(shù)據(jù)。 斐波那契查找方法 插值查找法 分塊查找 ?分塊查找又稱為索引順序查找，是順序查找方法的另一種改進，其性能介于順序查找和二分查找之間。 else if (r[mid].keyk) low=mid+1。 ?重復(fù)上述過程，查找范圍每次縮小 1/2，當(dāng)范圍不斷縮小，出現(xiàn)查找范圍的下界大于上界時，則查找失敗，確定關(guān)鍵字為 key的記錄不存在。 缺點是平均查找長度較大 ， 特別是當(dāng) n較大時 ， 查找效率較低 ，不宜采用 。 while (r[i].key!=k) i。 ?順序查找的線性表定義如下： Typedef struct rectype { keytype key。 ?查找算法中的基本運算是記錄的關(guān)鍵字與給定值所進行的比較，其執(zhí)行時間通常取決于比較的次數(shù)。 ?在計算機中，被查找的數(shù)據(jù)對象是由同一類型的記錄構(gòu)成的集合，可稱之為查找表（ search table）。 ?在實際應(yīng)用問題中，每個記錄一般包含有多個數(shù)據(jù)域，查找是根據(jù)其中某一個指定的域進行的，這個作為查找依據(jù)的域稱為關(guān)鍵字（ key）。因此，通常以關(guān)鍵字與給定值進行比較的記錄個數(shù)的平均值，作為衡量查找算法好壞的依據(jù)。 itemtype item1 …… }rectype。 return(i)。 ?折半查找又稱二分查找 (Birary search)。 ?比較結(jié)果有三種可能： ⑴ 如果 r[m].keyk， 說明如果存在欲查找的元素 ，該元素一定在數(shù)組的前半部分 ， 查找范圍縮小了一半 ， 修改查找范圍的的上界 high=m1， 繼續(xù)對數(shù)組的前半部分進行二分查找； ⑵ 如果 r[m].keyk， 說明如果存在欲查找的元素 ，該元素一定在數(shù)組的后半部分 ， 查找范圍縮小了一半 ， 修改查找范圍的的下界 low=m+1， 繼續(xù)對數(shù)組的后半部分進行二分查找； ⑶ 如果 r[m].key=k，查找成功， m所指的記錄就是查找到的數(shù)據(jù)。 if (r[mid].key==k) return(mid)。 } 折半查找的分析 ?折半查找的判定樹 ?平均查找長度 ASL= log2(n+1)1 ?查找成功時的最大查找長度為折半查找判定樹的深度 ?log2n? +1， ?查找不成功時的最大查找長度也為折半查找判定樹的深度 ?log2n? +1。索引表按關(guān)鍵字值的遞增順序排列。 ?例如線性表中關(guān)鍵字為 :9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82其索引如圖 。 typedef struct indexterm index[MAXITEM]。amp。 else find=1。 j=idx[low].high。 if (ij) i=0。 2. 若右子樹非空 , 則右子樹上的所有結(jié)點都大于其根結(jié)點的值 。 }BSTree 二叉排序樹查找 基本思想：查找過程從根結(jié)點開始，首先將它的關(guān)鍵字與給定值 k進行比較，如果相等，則查找成功，輸出有關(guān)的信息；如果不等，若根結(jié)點關(guān)鍵字大于給定值 k，向左子樹繼續(xù)查找，否則向右子樹繼續(xù)查找。 if(kbdata) return (search (bleft, k))。 while(p!=NULL)。 } return (NULL)。 If (tptr==null) { tptr=s。 /*無需插入 q=p。 /*要插入結(jié)點 s的父 else qrchild=s。 Flchild=plchild 或 Flchild=prchild 3. P有兩個兒子時，有兩種方法。 /*r為臨時變量 S=flchild。 設(shè) Q為 S的父親。 S=srchild。 /*當(dāng) Q=P時， S即為 P的左兒子，此時把 S的左兒子作為 P的左兒子 平衡樹 ?平衡樹 (Balanced tree)也稱為 AVL樹，是由阿德爾森 — 維爾斯基和蘭迪斯 (Adelsonvelskii and landis)于 1962年首先提出的。 平衡樹 ?平衡二叉樹 1 1 1 1 0 0 0 1 2 0 0 1 0 ?不平衡二叉樹 ?假設(shè)給平衡樹某個結(jié)點的左子樹插入一個新結(jié)點，且此新結(jié)點使左子樹的高度加 1，我們可能會遇到以下三種情況： (1) 如果原來其左子樹高度 hl與右子樹高度 hr相等 ，即原來此結(jié)點的平衡因子等于 0,插入新結(jié)點后將使平衡因子變成 +1， 但仍符合平衡樹的條件 ， 不必對其加以調(diào)整； ⑵ 如果原來 hlhr， 即原來此結(jié)點的平衡因子等于+1,插入新結(jié)點后將使平衡因子變成 +2， 破壞了平衡樹的限制條件 ， 需對其加以調(diào)整； ⑶ 如果原來 hlhr，即原來此結(jié)點的平衡因子等于1，插入新結(jié)點后將使平衡因子變成 0，平衡更加改善，不必加以調(diào)整。 ?圖中矩形表示子樹，矩形的高度表示子樹的高度，帶陰影線的方形則表示插入新結(jié)點后造成的子樹高度加 1，各結(jié)點旁所標(biāo)數(shù)字為該
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1