資源描述：
《多種查找算法實現(xiàn)及其比較》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、廣西工學院計算機學院《數(shù)據(jù)結構》課程實驗報告書實驗八多種查找算法實現(xiàn)及其比較學生姓名：學號：班級：計指導老師專業(yè)：計算機學院軟件學院提交日期：2013年6月28日-22-1．實驗目的1）掌握常見的靜態(tài)查找表和動態(tài)查找表的表示和操作方法。2）能根據(jù)具體的查找方法設計合理的查找表的數(shù)據(jù)結構。2.實驗內(nèi)容1）用靜態(tài)查找結構實現(xiàn)靜態(tài)查找算法，包括順序查找—用順序表、鏈表（流程圖）折半查找—用有序順序表（流程圖）基本操作：Create(&ST,n);//構造含有n個元素的靜態(tài)查找表STDestroy(&ST);//銷毀表Search(ST
2、,key);//查找關鍵字為key的數(shù)據(jù)元素Traverse(ST,visit());//遍歷查找表數(shù)據(jù)結構定義：typedefstruct{intkey;}Eletype;typedefstruct{Elemtype*elem;intlength;}SSTable;#defineBLOCK_NUM32）用動態(tài)查找結構實現(xiàn)動態(tài)查找算法，包括二叉排序樹—無重復關鍵字AVL樹—平衡二叉排序樹動態(tài)查找：表結構本身是在查找過程中動態(tài)生成的?；静僮鳎篒nitDSTable(&DT);//構造一個空的動態(tài)查找表DTDestroyDSTab
3、le(&DT);//銷毀表SearchDSTable(DT,key);//查找關鍵字為key的數(shù)據(jù)元素-22-InsertDSTable(&DT,e);DeleteDSTable(&DT,key);TraverseDSTable(DT,visit());//遍歷查找表二叉排序樹的數(shù)據(jù)類型描述：typedefstruct{intkey;}ElemType;typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;3）．用以上方法中
4、的一種，編程實現(xiàn)在n個數(shù)據(jù)（n>=10）中查找某個數(shù)3．實驗要求（1）上機前交實驗源程序（紙質(zhì)版），由學習委員統(tǒng)一收好交老師（附上不交同學名單）。（2）用一切你能想到的辦法解決遇到的問題，培養(yǎng)解決問題的能力。（3）實驗課上進行答辯。（4）實驗報告當場交。報告內(nèi)容包括：實驗目的、實驗內(nèi)容、實驗代碼、實驗運行結果以及實驗體會供五部分。3．主要算法3.1順序存儲結構（1）結構定義：#include#include#include#include//各頭文件#d
5、efineN10#defineOK1#defineERROR0#defineOVERFLOW-2typedefintkeyType;//設關鍵字域為長整型-22-typedefintTElemType;//定義宏參//定義靜態(tài)表存儲結構typedefstruct{TElemType*elem;//定義數(shù)據(jù)類型intlength;//記錄當前長度}SSTable;//定義動態(tài)表存儲結構typedefstruct{intkey;//關鍵字}ElemType;//定義動態(tài)表指針typedefstructBiTNode{ElemType
6、data;//定義數(shù)據(jù)類型structBiTNode*lchild;//左孩子指針structBiTNode*rchild;//右孩子指針}BiTNode,*BiTree;voidInsert_BST(BiTree&T,BiTreeS);intDelete(BiTree&p);//建立靜態(tài)表voidCreat_seq(SSTable&ST,TElemTyper[],intn){//操作結果:建立一個靜態(tài)表-22-inti;ST.elem=(TElemType*)calloc(n+1,sizeof(TElemType));//分配
7、存儲空間if(!ST.elem)//分配存儲空間失敗exit(0);for(i=1;i<=n;i++)//把r中的數(shù)據(jù)元素復制給STST.elem[i]=r[i];ST.length=n;////記錄當前長度}//靜態(tài)表清空voidClear(SSTable&ST){//初始條件:靜態(tài)表已存在//操作結果:清空靜態(tài)表inti=ST.length;for(i=1;i<=ST.length;i++)//把ST當前長度賦值為0ST.elem[i]=0;return;}//靜態(tài)順序查找intsearch_seq(SSTableST,ke
8、yTypekey){//初始條件:靜態(tài)表已存在//操作結果:在順序表中順序查找其關鍵字等于key的數(shù)據(jù)元素，//若存在，則返回該元素，否則返回0inti=ST.length;ST.elem[0]=key;while(ST.elem[i]!=key)--i;-22
