數據結構毫無疑問是計算機科學既經典又核心的課程之一，不管是從事計算機軟件還是硬件的開發工作，如果沒有系統地學習數據結構或者是沒有專心自學過，很容易被人打上“非專業”的標簽。對于任何在信息技術行業工作的專業人員或者想進入此行業的人來說，什么時候開始學數據結構都不會晚，更不會過時。
從“數據結構”的名字看，它不僅僅只是講授數據的結構以及在計算機內如何存儲和組織數據的方式，這些只是它的表面現象。數據結構背后真正蘊含的是與之息息相關的算法，精心選擇的數據結構配合恰如其分的算法就意味著數據或者信息在計算機內被高效率地存儲和高效率地處理。算法其實就是數據結構的靈魂，它既神秘又神奇“好玩”，當然對初學者也比較難，算法可以說是“聰明人在計算機上的游戲”。
本書是一本綜合而且全面講述數據結構及其算法分析的教科書，為了便于高校的教學或者讀者自學，作者在描述數據結構原理和算法時文字清晰并且嚴謹，為每個算法及其數據結構提供了演算的詳細圖解。另外，為了適合在教學中讓學生上機實踐或者自學者上機“操練”，本書為每個經典的算法都提供了C語言編寫的完整范例程序的源代碼，每個范例程序都不需要經過修改，直接通過編譯就可以運行，目的就是讓本書的學習者以這些范例程序作為參照迅速掌握數據結構和算法的要點。
全書的所有范例程序都可以在標準的C語言編程環境中編譯通過并且成功運行，我們在改編本書的過程中選用了免費的Dev C++ 5.11集成開發環境，對原書的所有范例程序進行編譯、修改、調試和測試，并確保它們都可以準確無誤地運行。附錄A包含了“C/C++編譯程序的介紹與安裝”，其中重點就介紹了Dev C++。附錄B則包含了“C語言快速入門”。
第8章 查找
在數據處理過程中，是否能在最短時間內查找到所需要的數據，是一個相當值得信息從業人員關心的問題。所謂查找（search，或搜索）指的是從數據文件中找出滿足某些條件的記錄。用以查找的條件稱為“鍵值”（key），就如同排序所用的鍵值一樣。
例如聯系人中找某人的電話號碼，那么這個人的姓名就成為在聯系人中查找電話號碼的鍵值。通常影響查找時間長短的主要因素包括算法的選擇、數據存儲的方式和結構。
8-1 常見的查找方法
如果根據數據量的大小，可將查找分為：
1. 內部查找：數據量較小的文件，可以一次性全部加載到內存中進行查找。
2. 外部查找：數據量大的文件，無法一次加載到內存中處理，而需使用輔助存儲器來分次處理。
如果從另一個角度來看，查找的技巧又可分為“靜態查找”和“動態查找”兩種。定義如下所示。
1. 靜態查找：指的是在查找過程中，查找的表格或文件的內容不會被改動。例如符號表的查找就是一種靜態查找。
2. 動態查找：指的是在查找過程中，查找的表格或文件的內容可能會被改動，例如在樹狀結構中所談的B-tree查找就屬于一種動態查找。
至于查找技巧中比較常見的方法有順序法、二分查找法、斐波那契法、插值法、哈希法、m路查找樹、B-tree等。為了讓大家能確實掌握各種查找的技巧和基本原理，以便應用于日后的各種領域，現將幾個主要的查找方法分述于后。
8-1-1 順序查找法
順序查找通常用于未經組織化的文件，又稱為線性查找。查找的過程從文件第一項數據開始，按序比較每個鍵值。由于順序查找法是逐項對比，因此只要一找到數據就可以結束數據的查找。以n項數據為例，使用順序查找法來查找數據時，有可能在第1項就找到了，在這種情形下僅需執行一次比較操作。如果數據在第2項、第3項…第n項，則其需要的比較次數分別為2、3、4、…、n次。因此，在平均情況下，順序查找法，查找一項數據需要的平均比較次數為 (n+1)/2。
現在以一個例子來說明，假設已有數列74、53、61、28、99、46、88，若要查找28，則需要比較4次；要查找74僅需比較1次；要查找88則需查找7次，這表示當查找的數列長度n很大時，利用順序查找是不太適合的，它是一種適用于小數據文件的查找方法。
另外，在最差的情況下，逐一對比后沒有找到數據，則必須花費n次，其最壞情況下（Worst Case）的時間復雜度為O(n)。也就是說，除非可以預知要查找的數據大概位于文件的前端，否則當文件的數據項數過大時，順序查找法在查找的效率上顯然不如其他的查找法。
線性查找法的優點是文件或數據事前不需要經過任何的處理與排序，也由于它未考慮到數據的特征對于查找的影響，所以在應用上適合于各種情況，其缺點則是查找的速度較慢。
順序查找法的C語言算法如下所示。
while (val!=-1)
{
find=0;
printf("請輸入查找鍵值(1-150)，輸入-1離開：");
scanf("%d",&val);
for (i=0;i<80;i++)
{
if(data[i]==val)
{
printf("在第 %3d個位置找到鍵值 [%3d]\n",i+1,data[i]);
find++;
}
}
if(find==0 && val !=-1)
printf("######沒有找到 [%3d]######\n",val);
}
8.1.1
請設計一個C程序，以隨機數生成1~150之間的80個整數，然后實現順序查找法的過程。
請參考程序CH08_01.c，本范例程序的運行結果如圖8-1所示。
圖8-1 實現順序查找法的范例程序的運行結果
8-1-2 二分查找法
如果要查找的數據已經事先排好序了，則可使用二分查找法來進行查找。二分查找法是將數據平均分割成兩份，再比較鍵值與中間值的大小，如果鍵值小于中間值，可確定要查找的數據在前半段，否則在后半部。如此分割數次直到找到或確定不存在為止。例如，以下已排序的數列 2、3、5、8、9、11、12、16、18 ，而所要查找值為11時：
首先跟第5個數值 9 比較，如圖8-2所示。
圖8-2 先和中值比較
因為11＞9，所以和后半部的中間值 12 比較，如圖8-3所示：
圖8-3 再和后半部的中值比較
因為 11＜12，所以和前半部的中間值 11比較，如圖8-4所示：
圖8-4 再和后半部的前半部中值比較
因為 11=11，表示查找到了即查找完成，如果不相等則表示沒有找到。
二分查找法的C語言算法如下所示。
int bin_search(int data[50],int val)
{
int low,mid,high;
low=0;
high=49;
printf("查找過程中......\n");
while(low <= high && val !=-1)
{
mid=(low+high)/2;
if(val
{
printf("%d 介于位置 %d[%3d]和中間值 %d[%3d]，找左半邊\n",val,low+1, data[low],mid+1,data[mid]);
high=mid-1;
}
else if(val>data[mid])
{
printf("%d 介于中間值位置 %d[%3d] 和 %d[%3d]，找右半邊\n",val,mid+1, data[mid],high+1,data[high]);
low=mid+1;
}
else
return mid;
}
return -1;
……
新書資訊