數(shù)據(jù)結(jié)構(gòu)C語言實現(xiàn)順序查找,折半查找,二叉排序樹,哈希表實驗原理(實驗原理+程序代碼+程序截圖+實驗小結(jié)

1、實驗日期:2010-6-12教師簽字:成績學(xué)號：E30814013專業(yè)：網(wǎng)絡(luò)工程姓名：張蕓學(xué)號：E30814013專業(yè)：網(wǎng)絡(luò)工程姓名：張蕓實驗報告實驗?zāi)康模簩崿F(xiàn)順序查找，折半查找，二叉排序樹，哈希表實驗原理:順序查找iiitSearch_Seq(SSTableST,KeyTypekey)/算法9.1/在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0。mt1=0;ST.elemO.key=key;/”哨兵”for(i=ST.lengtli;ST.elemi.key!=key;-i);/從后往前找returni;/找不到時，i為0/Search_S

2、eq二叉排序樹(BinarySortTree)乂稱二叉查找(搜索)樹(BinarySearchTree)o其定義為：二叉排序樹或者是空樹，或者是滿足如下性質(zhì)的二叉樹：若它的左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若它的右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；左、右子樹本身又各是一棵二叉排序樹。哈希表StatusSearcliHasli(HashTableH,HKeyTvpeK,int&p、mt&c)/算法9.17/在開放定址哈希表H中查找關(guān)鍵碼為K的元素，/若查找成功，以p指示待查數(shù)據(jù)元素在表中位置，并返回SUCCESS；/否則，以p指示插入位置，并返回UNSUCCES

3、S,c用以計沖突次數(shù)，其初值置零，供建表插入時參考p=Hash(K);/求得哈希地址while(H.elemp.key!=NULLKEY)&/該位置中填有記錄!equal(K,(H.elemp.key)/并且關(guān)鍵字不相等collision(p,-h-c);/求得下一探查地址pif(equal(K,(H.elemp.key)retuinSUCCESS;/查找成功，p返回待查數(shù)據(jù)元素位置elsel-euunUNSUCCESS;/查找不成功(H.elemp.kev=NULLKEY),p返回的是插入位置/SeaicliHash順序查找#includevoidmain()inta10=1,2,34567

4、,8,90;inti,x,y;printf(“輸入你要査找的數(shù):n”);scanf(%d,&x);y=o；for(i=0;i10;i+)if(x=ai)y=i;printf(”你要查找的數(shù)(1在第個(1位置n”,x,i+1);break;if(y=O)printf(”無法找到你要査找的數(shù)n“);折半查找#include#defineN21voidmain(void)intaN;mtiaijium;mttop.bottomaiiid;mtflag=l;/如果在表列中找到數(shù)字，則值為1,否則為0mtloc=-l;/要查找的數(shù)在表列中的位置，如果loca-1表示表列中沒有這個數(shù);如果有這個數(shù)，則它的

5、值為所在的位置pimtfC你想在多少個數(shù)中進行折半查找，請輸入(120)：”)；scanf(”d,&n);wlule(n20)prmtf(”你輸入的數(shù)不正確，請重新輸入。5”)；pmitf(“你想在多少個數(shù)中進行折半查找，請輸入(1-20)：”)；scanf(%d&n);prmtf(請你輸入一個整數(shù)al:”)；scanf(”d,&al);1=2;while(iai-l)i+;elsepnntf(“你輸入的數(shù)不滿足要求，請重新輸入。輸出表列pimtf(ii輸出表列n”)；fbr(i=l;iatop)|(numatop或者numnum)若amidnimi,則num定在afbottom和amid范韋

6、I之內(nèi)top=nud-l;nud=(top+bottom)/2;elseif(anndnum)/若anudnum,則num定在anud+l和atop范|制之內(nèi)bottom=nud+l;nud=(top+bottom)/2;if(loc=-l)pnntf(M%d這個數(shù)在表列中沒有找到。irnum);HE:Debugzheban.exe你想在多少個數(shù)中進行折半查找，請輸入(1-20):10請你輸入一個整數(shù)aLl：l請你豹入一個整數(shù)aL2：2請你豹入一個整數(shù)aL3：3請你豹入一個整數(shù)aL4：4請你豹入一個整數(shù)aL5：5請你豹入一個整數(shù)aL6：6請你鞠入一個整數(shù)aL7：7請你豹入一個整數(shù)aL8：8請你

7、鞠入一個整數(shù)aL9：9請你輸入一個整數(shù)aL10：10輸岀表列12345678910請你輸入要查找的數(shù)：5botton=l,nid=5,aL5=5找到數(shù)5的位置5Pressanykeytocontinue.搜狗拼音半:nlI二叉排序樹#include#include#include#defineINFMT”d”#defineOUTFMTM%d”/*#defiiieNULLOL*/#defineBOOLint#defineTRUE1#defineFALSE0#defineLEN10000tvpedefintElemType;tvpedefstmctBSTNodeElemTypedata;stmct

8、BSTNode*lcluld,*rcluld;BSTNode,*BSTree;/*插入新節(jié)點/voidInseit(BSTiee*tree,ElemTypeitem)BSTieenode=(BSTree)malloc(sizeof(BSTNode);node-data=item;node-lchild=node-rcliild=NULL;if(!*tiee)*tree=node;elseBSTreecursor=*tree;wliile(1)if(itemdata)if(NULL=cuisor-lchild)cuisor-lchild=node;break;cursor=cursor-lcli

9、ild;elseif(NULL=cuisor-icluld)cuisor-rchild=node;break;cursor=cursor-rcluld;return:/*查找指定值*/BSTreeSearch(BSTreetree,ElemTypeitem)BSTreecursor=tree;while(cursor)if(item=cursor-data)returncursor;elseif(itemdata)cursor=cursor-lchild;elsecursor=cursor-rchild;returnNULL;/*中綴遍歷*/voidInorder(BSTieetree)BST

10、reecursor=tree;if(cursor)Iiioidei(cuisof-ichild);pnntf(OUTFMT.cuisor-data);Iiioidei(cuisof-ichild);/*回收資源*/voidCleaiiup(BSTreetiee)BSTreecursor=tree,temp=NULL;if(cursor)Cleanup(cursor-lchild);Cleanup(cuisor-rcluld);fiee(cuisor);voidmain()ElemTypeitem;chaichoice;BSTreeroot=NULL,let;/*必須賦予NULL值，否則出錯*/

11、BOOLfiiush=FALSE;dopnntfC請輸入數(shù)據(jù)（-10000結(jié)束）：n”）;wlule(1)scanf(INFMT.&item);if(-10000!=item)Insert(&root,item);elsebreak;pimtf(iiii創(chuàng)建完成n);Inorder(root);/*二叉排序樹的查找測試*/do請輸入查找數(shù)據(jù)：”);scanf(H%d,&item);getchai();printf(MSearching.iin);ret=Seaich(root,item);if(NULL=ret)prmtf(查找失敗！”);elsepnntfC查找成功！J;pnntf(-n繼續(xù)

12、測試按y,退出按其它鍵。iT);choice=getchai();while(choice=y|choice=,Y,);Cleanup(root);#iiicludevoidmain()inta10;mtbaj,c;J=l;fbr(i=0;i9;i+)a】=0；printf(iW輸入5個數(shù)(非零)n”);for(i=0;i5;i+)sc3nfC%d”,&b);c=b%7;A:if(ac=O)ac=b;elsec=(c+1)%7j+；gotoA;pnntf(”d在哈希表的第d位，第d次放入哈希表n,b,c,j);J=l；,E:Debughaxi.exeM請輸入5個數(shù)非零7?在哈希表的笫0位笫1次放入哈希表1414在哈希表的笫1位，笫2次放入哈希表33在哈希表的笫3位，笫1次放入哈希表55