線性表的查找

查找，也可稱檢索，是在大量的資料元素中找到某個特定的資料元素而進行的工作。

在查找表中，線性表查找是最簡單的一種，主要的操作為順序查找和折半查找。

順序查找：從表的一端開始，依次将查找的關鍵字與給定資料庫進行批對，若關鍵字在給定資料庫中存在，則查找成功，否則當資料庫從頭到尾沒有批對到，則查找失敗。

作用範圍：即使用線性表的順序存儲又适合于線性表的鍊式存儲結構。

資料元素類型定義

順序表的定義：

我們假設st.r[1]開始存儲資料，把st.r[0]放置不用，這樣傳回的i值就是目前資料的位置。

将僞代碼簡單實作下

可以看到“我被列印一次”這句話被列印了50次，說明每次都要循環變量是否滿足條件i>=1進行檢測。算法是世界在于根據具體的情況進行不斷的優化。我們完全可以改進算法，免去這個檢測過程。改進的辦法是查找之前先對st.r[0]的關鍵字指派key,這時候st.r[0]起到了監視哨的作用。

改進後的僞代碼

将改良後僞代碼簡單實作下

可以清晰的看到改良前的代碼列印了50次，改良後的代碼隻列印了1次，這其中的差距就是選擇算法的重要性

算法簡單，對表結構無任何要求（順序和鍊式），無論記錄是否按關鍵字有序均可應用。

n很大時查找效率較低，不易采取順序查找。

說起了折半查找，讓我想起了我的高中數學老師，曾經老師在課堂講折半查找的時候說等到大學有接觸計算機的童鞋就會在資料結構中會重新學到折半查找，沒想到那個人就是我。~~(>_<)~~

總的來說可以描述為：