文章目錄
- 資料結構 查找
- 順序查找
- 折半查找
- 分塊查找
資料結構 查找
1.查找表：由同一型別的資料元素（或記錄）構成的集合，
2.關鍵字：資料元素（或記錄）中某個資料項的值，用以標識一個資料元素（或記錄），
3.查找：在查找表中確定一個其關鍵字等于給定值的記錄或資料元素，
4.動態查找表：在查找的同時對表做修改操作（插入和洗掉），否則為靜態查找表，
5.平均查找長度：ASL=求和Pi*Ci（Pi為查找表中第i個記錄的概率，Ci為和給定值進行過的關鍵字個數）
順序查找
又稱線性查找，主要用于在線性表中進行查找，
從表的一端開始，依次將記錄的關鍵字和給定值進行比較，若某個記錄的關鍵字和給定值相等，則查找成功；反之則查找失敗，
對無序線性表進行順序查找，查找失敗時要遍歷整個線性表；對有序線性表進行順序查找，查找失敗時不一定要遍歷整個線性表，
ASL成功=（n+1）/2
O（n）
折半查找
又稱線性查找，主要用于在線性表中進行查找，
從表的一端開始，依次將記錄的關鍵字和給定值進行比較，若某個記錄的關鍵字和給定值相等，則查找成功；反之則查找失敗，
對無序線性表進行順序查找，查找失敗時要遍歷整個線性表；對有序線性表進行順序查找，查找失敗時不一定要遍歷整個線性表，
ASL成功=（n+1）/2
O（n）
分塊查找
又稱索引順序查找，
分塊，子塊內元素可以無序，但塊間是有序的，即對于所有塊有第i塊的最大關鍵字小于第i+1塊的所有記錄的關鍵字，
ASL=Lb+Lw（Lb所在塊的平均查找長度；Lw塊中的平均查找長度）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255179.html
標籤：其他
上一篇：對kubernetes的認識
下一篇：C語言編程＞第二十二周 ② 請補充fun函式，該函式的功能是：回傳字符陣列中指定字符的個數，指定字符從鍵盤輸入。