《資料結構》
第八次實驗報告
1、實驗內容
1) 有序表的二分查詢
?建立有序表，然後進行二分查詢
2) 二叉排序樹的查詢
?建立二叉排序樹，然後查詢
2、需求分析
二分查詢的基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,演算法中止；如果xa[n/2],則只要在陣列a的右半部搜尋x.
時間複雜度無非就是while迴圈的次數！
總共有n個元素，
漸漸跟下去就是n,n/2,n/4,....n/2^k（接下來操作元素的剩餘個數），其中k就是迴圈的次數
由於你n/2^k取整後》=1
即令n/2^k=1
可得k=log2n,（是以2為底，n的對數）
所以時間複雜度可以表示o()=o(logn)
下面提供一段二分查詢實現的偽**:
binarysearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
return mid
elseif mid >des then
max=mid-1
else
min=mid+1
return max
折半查詢法也稱為二分查詢法，它充分利用了元素間的次序關係，採用分治策略，可在最壞的情況下用o(log n)完成搜尋任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查詢的x作比較，如果x=a[n/2]則找到x，演算法終止。如果xa[n/2]，則我們只要在陣列a的右半部繼續搜尋x。
3、概要設計
1、順序查詢，在順序表r[0..n-1]中查詢關鍵字為k的記錄，成功時返回找到的記錄位置，失敗時返回-1，具體的演算法如下所示：
int seqsearch(seqlist r,int n,keytype k)
if(i>=n)
return -1;
else
}2、二分查詢，在有序表r[0..n-1]中進行二分查詢，成功時返回記錄的位置，失敗時返回-1，具體的演算法如下：
int binsearch(seqlist r,int n,keytype k)
return -1;
}四、詳細設計
源**：
#include
#include
static int a[1024],count=0;
void find1(int low,int high,int x)
else printf("\n查é找ò失骸?敗悒?，?查é找ò次?數簓為a%d。￡",count);
} void find2(int low,int high,int x)
else printf("\n查é找ò失骸?敗悒?，?查é找ò次?數簓為a%d。￡",count);
} int main()
五、心得體會
通過這次在實現順序和二分查詢演算法的過程中，讓我對順序和二分查詢演算法有了更多的了解。查詢根據給定的某個值，在查詢表中確定乙個其關鍵字等於給定值的資料元素或（記錄）的操作，應用十分廣泛。順序查詢是一種最簡單的查詢方法。
它的基本思路是：從表的一端開始,順序掃瞄線性表,依次將掃瞄到的關鍵字和給定值k相比較,若當前掃瞄到的關鍵字與k相等,則查詢成功；若掃瞄結束後,仍未找到關鍵字等於k的記錄,則查詢失敗。二分查詢也稱為折半查詢要求線性表中的結點必須己按關鍵字值的遞增或遞減順序排列。
它首先用要查詢的關鍵字k與中間位置的結點的關鍵字相比較,這個中間結點把線性表分成了兩個子表,若比較結果相等則查詢完成;若不相等,再根據k與該中間結點關鍵字的比較大小確定下一步查詢哪個子表,這樣遞迴進行下去,直到找到滿足條件的結點或者該線性表中沒有這樣的結點。在學習過程中，善於發現，會找到更多的捷徑。
演算法與資料結構實驗報告
學生實驗報告冊 課程名稱 演算法與資料結構 實驗專案名稱 順序表實驗學時 2 同組學生姓名實驗地點 工科樓a205 實驗日期 2013年10月16日實驗成績 批改教師批改時間 實驗1 順序表 一 實驗目的和要求 掌握順序表的定位 插入 刪除等操作。二 實驗儀器和裝置 turbo c 2.0 三 實驗...
資料結構與演算法實驗報告
實驗名稱 線性表的應用指導教師 余文春 實驗日期 2014年月日實驗地點 北503 成績 實驗目的 1 掌握線性表及其順序儲存與鏈式儲存結構的概念。2 掌握兩種儲存方式的基本運算 實現方法和技術。3 靈活應用線性表進行程式設計，解決實際問題。實驗內容 約瑟夫 joseph 問題的一種描述是 編號為1...
資料結構與演算法專題實驗報告
資料結構 建立乙個具有n n 1 個頂點的無向圖的鄰接矩陣，並對其按照 深度優先搜尋 和 廣度優先搜尋 方法進行遍歷。1.編寫c程式予以實現。2.程式要求能輸入圖的頂點數 邊數以及邊的關係，並自動生成鄰接矩陣。3.結果輸出鄰接矩陣和遍歷的路徑。4.熟悉無向圖的兩種遍歷演算法。考慮用乙個n維陣列來存放...