數(shù)據(jù)結(jié)構(gòu)——查找,順序查找,折半查找

1、實驗五查找的應(yīng)用一、實驗?zāi)康模?、掌握各種查找方法及適用場合，并能在解決實際問題時靈活應(yīng)用。2、增強(qiáng)上機(jī)編程調(diào)試能力。二、問題描述分別利用順序查找和折半查找方法完成查找。有序表（3,4,5,7,24,30,42,54,63,72,87,95）輸入示例：請輸入查找元素：52輸出示例：順序查找：第一次比較元素95第二次比較元素87查找成功，i=*/查找失敗折半查找：第一次比較元素30第二次比較元素63 .利用序列（12,7,17,11,16,2,13,9,21,4）建立二叉排序樹，并完成指定元素的查 詢。輸入輸出示例同題1的要求。二數(shù)據(jù)結(jié)構(gòu)設(shè)計（選用的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)實現(xiàn)形式說明）（1）邏輯

2、結(jié)構(gòu)設(shè)計.順序查找和折.半查找采用線性表的結(jié)構(gòu).，二叉排序樹的查找則是建立一棵二叉樹，采用.的韭線性邏輯結(jié)構(gòu)。（2）存儲結(jié)構(gòu)設(shè)計采用順序存儲的一結(jié)構(gòu)，開辟一一塊空間用于存放元素。typedef struct(int key;/關(guān)鍵字域 ElemType;typedef struct Elem( int key;Elem;typedef struct BSTNode(Elem data;/結(jié)點數(shù)據(jù)域BSTNode *lchild,*rchild; /左右孩子指針BSTNode,*BSTree;typedef struct( ElemType *R; int length;SSTable;(3)存

3、儲結(jié)構(gòu)形式說明分別建立查找關(guān)鍵字，順序表一數(shù)據(jù)和二叉樹一數(shù)據(jù)的結(jié)構(gòu)體進(jìn)行存儲數(shù)據(jù)四、算法設(shè)計(1)算法列表(說明各個函數(shù)的名稱，作用，完成什么操作)序號名稱函數(shù)表示符操作說明1順序查找Search_Seq在順序表中順序查找關(guān)鍵字的數(shù)據(jù)元素2折半查找Search_Bin在順序表中折半查找關(guān)鍵字的數(shù)據(jù)元素3初始化Init對順序表進(jìn)行初始化，并輸入元素4樹初始化CreateBST創(chuàng)建一棵二叉排序樹5插入InsertBST將輸入元素插入到二叉排序樹中6查找SearchBST在根指針?biāo)付媾判驑渲羞f歸查找關(guān)鍵字 數(shù)據(jù)元素各函數(shù)間調(diào)用關(guān)系(畫出函數(shù)之間調(diào)用關(guān)系)算法描述_.int Search_Seq(

4、SSTable ST, int key)在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為/該元素在表中的位置，否則為0int c=1,i;for (i=ST.length; i=0; -i)printf(第1 次比較元素 dn”,c+,ST.Ri-1.key);if (ST.Ri-1.key=key)/從后往前找return i;return 0;/ Search_Seq int Search_Bin(SSTable ST, int key)/在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為/該元素在表中的位置，否則為0int low=0,high=

5、ST.length,i=1;/置查找區(qū)間初值int mid; while(low=high) mid=(low+high) / 2; printf(第 %d 次比較元素 dn”,i+,ST.Rmid.key);if (key=ST.Rmid.key)return mid;/找到待查元素else if (keydata.key=e;T-lchild=NULL;T-rchild=NULL;else if (T-data.keye)InsertBST(T-lchild,e);elseInsertBST(T-rchild,e); /*二 叉排序樹的創(chuàng)建void CreateBST(BSTree &T

6、) /依次讀入一個關(guān)鍵字為key的結(jié)點，將此結(jié)點插入二叉排序樹T中 T=NULL;int e,i=1,max;printf(輸入的個數(shù)為：)； scanf(%d”,&max);while (idata.key);if(!T)| key=T-data.key)return T;/查找結(jié)束else if(keydata.key) return SearchBST(T-lchild,key);/在左子樹中繼續(xù)查找elsereturn SearchBST(T-rchild,key);/在右子樹中繼續(xù)查找 五、調(diào)試記錄(調(diào)試過程中遇到的主要問題，是如何解決的，對設(shè)計和編碼的回顧討論和分析；改進(jìn)設(shè)想 等)

7、調(diào)試中出現(xiàn)了幾次程序查找失敗的情況，究其原因，是奇數(shù)個元素的時候，二分查找六、運行說明未定一義好，在后續(xù)改一進(jìn)之后，程序能實現(xiàn)預(yù)期一的效果(列出測試結(jié)果，包括輸入和輸出。這里的測試數(shù)據(jù)應(yīng)該完整和嚴(yán)格，最好多于示例中所列數(shù)據(jù)）字零字字*牛宰字字* 在找 實 驗* *律律律* * *功能；.一順序、-X柱找2:分查找 1有序表3,4, 5.7. 24, 30,42, 54, 53. 72,87,96輸入順序表元素個數(shù)：12依次輸無眥序喪元素3 4 5 7 24 SD 42 54 63 72 S7 95wwww*章章琳琳* 志衣點11 p f Kj 幣才k* * * 吊輸入查找元底 52第1次比較無

8、泰95第2次比校兀素87第3次比校兀素龍第4次比較兀索做第5次比較元素54第啾比較元素42第T次比較無知0第8次比敏元素飄第9次比校兀素了第10次比較兀案5第】1次比較兀素4第12次比校元素3第13次比較元素-33686019G存在r樣林樹林*林粹科.育序表的：分查找村林村* * *林本林林第1挾比較元素42第忘次比較兀素巧第3次比較元玄Mwj|序列(12.7,17,11,21, 4)建立：義排序楠,并完崩指定兀素的查制www 輸入的卒塹為：10地人革1個坎：12地匕簞4墳I 7蛔匕第個致，1；蛔入弟4 1、缺I 1蝠入蘋51致：16輸入第St致：3輸入第T個數(shù)* 13箍入弟8個就：澈入第紋：

9、幻地人蘋1U個故：4輸入查詢元素匚14弟斗次占詢I 12Ij&fXftHil： 17常&枚世詢：血弟丁株在可：13隹詢矢敗種串小功徒：1-序、：公宣找2- ：Jk找以下附上源代碼：#include#include#includeint N;typedef struct(int key;/關(guān)鍵字域 ElemType;typedef struct Elem(int key;Elem;typedef struct BSTNode(Elem data;/結(jié)點數(shù)據(jù)域BSTNode *lchild,*rchild;/左右孩子指針BSTNode,*BSTree;typedef struct(ElemType

10、 *R;int length;SSTable;int Search_Seq(SSTable ST, int key)在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為/該元素在表中的位置，否則為0int c=1,i;for (i=ST.length; i=0; -i)printf(第1次比較元素 dn”,c+,ST.Ri-1.key);if (ST.Ri-1.key=key)/從后往前找return i;return 0;/ Search_Seqint Search_Bin(SSTable ST, int key) /在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找

11、到，則函數(shù)值為 /該元素在表中的位置，否則為0int low=0,high=ST.length,i=1;/置查找區(qū)間初值int mid; while(low=high) mid=(low+high) / 2; printf(第 %d 次比較元素 dn”,i+,ST.Rmid.key);if (key=ST.Rmid.key) return mid;/找到待查元素else if (keydata.key=e;T-lchild=NULL;T-rchild=NULL;else if (T-data.keye)InsertBST(T-lchild,e);elseInsertBST(T-rchild,e

12、);/ *二叉排序樹的創(chuàng)建void CreateBST(BSTree &T )/依次讀入一個關(guān)鍵字為key的結(jié)點，將此結(jié)點插入二叉排序樹T中T=NULL;int e,i=1,max;printf(輸入的個數(shù)為：)；scanf(%d”,&max);while (idata.key);if(!T)| key=T-data.key)return T;/查找結(jié)束else if(keydata.key)return SearchBST(T-lchild,key);/在左子樹中繼續(xù)查找else/在右子樹中繼續(xù)查找return SearchBST(T-rchild,key); void main()int

13、N=1;printf(* 查找實驗 *n);SSTable W; int t,i,a;while (1)printf(*功能：1-順序、二分查找2-二分查找n);scanf(%d”,&a);switch (a)case 1:Init(W);printf(* 有序表的順序查找 *n);printf(請輸入查找元素n);scanf(%d”,&t);if(i=Search_Seq(W, t)printf(位置在第 %dn”,i);elseprintf(不存在n);printf(* 有序表的二分查找 *n);if(i=Search_Bin(W,t)+1)printf(位置在第d位n,i);elsepr