真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告1/2真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)第四章：實(shí)驗(yàn):簡單查找算法需求和規(guī)格說明：查找算法這里主要使用了順序查找，折半查找，二叉排序樹查找和哈希表查找四種方法。由于自己能力有限，本想實(shí)現(xiàn)其他算法，但沒有實(shí)現(xiàn)。其中順序查找相對比較簡單，折半查找參考了書上的算法，二叉排序樹查找由于有之前做二叉樹的經(jīng)驗(yàn)，因此實(shí)現(xiàn)的較為順利，哈希表感覺做的并不成功，感覺還是應(yīng)該可以進(jìn)一步完善，應(yīng)該說還有很大的改進(jìn)余地。設(shè)計(jì)思想：開始的時(shí)候提示輸入一組數(shù)據(jù)。并存入一維數(shù)組中，接下來調(diào)用一系列查找算法對其進(jìn)行處理。順序查找只是從頭到尾進(jìn)行遍歷。二分查找則是先對數(shù)據(jù)進(jìn)行排序，然后利用三個(gè)標(biāo)志，分別指向最大，中間和最小數(shù)據(jù)，接下來根據(jù)待查找數(shù)據(jù)和中間數(shù)據(jù)的比較不斷移動標(biāo)志，直至找到。二叉排序樹則是先構(gòu)造，構(gòu)造部分花費(fèi)最多的精力，比根節(jié)點(diǎn)數(shù)據(jù)大的結(jié)點(diǎn)放入根節(jié)點(diǎn)的右子樹，比根節(jié)點(diǎn)數(shù)據(jù)小的放入根節(jié)點(diǎn)的左子樹，其實(shí)完全可以利用遞歸實(shí)現(xiàn)，這里使用的循環(huán)來實(shí)現(xiàn)的，感覺這里可以嘗試用遞歸。當(dāng)二叉樹建好后，中序遍歷序列即為由小到大的有序序列，查找次數(shù)不會超過二叉樹的深度。這里還使用了廣義表輸出二叉樹，以使得更直觀。哈希表則是利用給定的函數(shù)式建立索引，方便查找。設(shè)計(jì)表示：實(shí)現(xiàn)注釋：其實(shí)查找排序這部分和前面的一些知識聯(lián)系的比較緊密，例如順序表的建立和實(shí)現(xiàn)，順序表節(jié)點(diǎn)的排序，二叉樹的生成和遍歷，這里主要是中序遍歷。應(yīng)該說有些知識點(diǎn)較為熟悉，但在實(shí)現(xiàn)的時(shí)候并不是那么順利。在查找到數(shù)據(jù)的時(shí)候要想辦法輸出查找過程的相關(guān)信息，并統(tǒng)計(jì)。這里順序查找和折半查找均使用了數(shù)組存儲的順序表，而二叉樹則是采用了鏈表存儲的樹形結(jié)構(gòu)。為了直觀起見，在用戶輸入了數(shù)據(jù)后，分別輸出已經(jīng)生成的數(shù)組和樹。折半查找由于只能查找有序表，因此在查找前先調(diào)用函數(shù)對數(shù)據(jù)進(jìn)行了排序。在查找后對查找數(shù)據(jù)進(jìn)行了統(tǒng)計(jì)。二叉排序樹應(yīng)該說由于有了之前二叉樹的基礎(chǔ)，并沒有費(fèi)太大力氣，主要是在構(gòu)造二叉樹的時(shí)候，要對新加入的節(jié)點(diǎn)數(shù)據(jù)和跟數(shù)據(jù)進(jìn)行比較，如果比根節(jié)點(diǎn)數(shù)據(jù)大則放在右子樹里，如果比根節(jié)點(diǎn)數(shù)據(jù)小則放入左子樹。建立了二叉樹后，遍歷和查找就很簡單了。而哈希表，應(yīng)該說自我感覺掌握的很不好，程序主要借鑒了書上和ppt上的代碼，但感覺輸出還是有問題，接下來應(yīng)該進(jìn)一步學(xué)習(xí)哈希表的相關(guān)知識。其實(shí)原本還設(shè)計(jì)了其他幾個(gè)查找和排序算法，但做到哈希表就感覺很困難了，因此沒有繼續(xù)往下做，而且程序還非常簡陋，二叉樹和哈希表的統(tǒng)計(jì)部分也比較薄弱，這也是接下來我要改進(jìn)的地方。具體代碼見源代碼部分。5.詳細(xì)設(shè)計(jì)表示：6.用戶手冊：程序運(yùn)行后，用戶首先要輸入數(shù)據(jù)的個(gè)數(shù)。接下來輸入一組數(shù)據(jù)并根據(jù)提示進(jìn)行順序查找，二分查找，二叉排序樹查找和哈希表查找等操作，由于操作直接簡單這里不再詳述。數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第1頁。7.調(diào)試報(bào)告：應(yīng)該說在調(diào)試這個(gè)程序的過程中自己發(fā)現(xiàn)了很多不足，這次實(shí)驗(yàn)讓我學(xué)到了不少東西，但應(yīng)該說這個(gè)程序可實(shí)現(xiàn)的功能還是偏少，不太實(shí)用，接下來有待改進(jìn)。8.源代碼清單和結(jié)果：#include<stdio.h>#defineLENGTH100#include<stdlib.h>#include<time.h>#defineINFMT"%d"#defineOUTFMT"%d"/*#defineNULL0L*/#defineBOOLint#defineTRUE1#defineFALSE0#defineLEN10000typedefintElemType;typedefstructBSTNode{ElemTypedata;structBSTNode*lchild,*rchild;}BSTNode,*BSTree;typedefBSTreeBiTree;/*插入新節(jié)點(diǎn)*/voidInsert(BSTree*tree,ElemTypeitem){BSTreenode=(BSTree)malloc(sizeof(BSTNode));node->data=item;node->lchild=node->rchild=NULL;if(!*tree)*tree=node;else{BSTreecursor=*tree;while(1){if(item<cursor->data){if(NULL==cursor->lchild)數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第2頁。數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第2頁。cursor->lchild=node;break;}cursor=cursor->lchild;}else{if(NULL==cursor->rchild){cursor->rchild=node;break;}cursor=cursor->rchild;}}}return;} void showbitree(BiTreeT)//遞歸顯示二叉樹的廣義表形式{ if(!T) {printf("空");return;} printf("%d",T->data); //打印根節(jié)點(diǎn) if(T->lchild||T->rchild) { putchar('('); showbitree(T->lchild); //遞歸顯示左子樹 putchar(','); showbitree(T->rchild); //遞歸顯示右子樹 putchar(')'); }}/*查找指定值*/BSTreeSearch(BSTreetree,ElemTypeitem){BSTreecursor=tree;數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第3頁。{if(item==cursor->data)returncursor;elseif(item<cursor->data)cursor=cursor->lchild;elsecursor=cursor->rchild;}returnNULL;}/*中綴遍歷*/voidInorder(BSTreetree){BSTreecursor=tree;if(cursor){Inorder(cursor->lchild);printf(OUTFMT,cursor->data);Inorder(cursor->rchild);}}/*回收資源*/voidCleanup(BSTreetree){BSTreecursor=tree,temp=NULL;if(cursor){Cleanup(cursor->lchild);Cleanup(cursor->rchild);free(cursor);}}voidsearchtree(BSTreeroot){charchoice;printf("中序遍歷的結(jié)果為:\n");Inorder(root);數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第4頁。printf("\n\n");數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第4頁。ElemTypeitem;BSTreeret;/*二叉排序樹的查找測試*/do{printf("\n請輸入查找數(shù)據(jù)：");scanf("%d",&item);getchar();printf("Searching...\n");ret=Search(root,item);if(NULL==ret)printf("查找失?。?);elseprintf("查找成功！");printf("\n繼續(xù)測試按y，退出按其它鍵。\n");choice=getchar();}while(choice=='y'||choice=='Y');Cleanup(root);}searchhash(int*arr,intn){ inta[10]; intb,i,j,c; j=1; for(i=0;i<9;i++) a[i]=0; printf("以下為哈希表輸出\n"); for(i=0;i<n;i++) { c=arr[i]%7;A: if(a[c]==0)a[c]=arr[i]; else{c=(c+1)%7;j++;a[c]++;gotoA;} printf("\n%d在哈希表的第%d位,第%d次放入哈希表\n",arr[i],c,j); j=1;}}voidSequenceSearch(int*fp,intLength);數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第5頁。voidSearch(int*fp,intleng數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第5頁。voidSort(int*fp,intlength);voidSequenceSearch(int*fp,intLength){intdata;printf("開始使用順序查詢.\n請輸入你想要查找的數(shù)據(jù).\n");scanf("%d",&data);for(inti=0;i<Length;i++)if(fp[i]==data){printf("經(jīng)過%d次查找，查找到數(shù)據(jù)%d.\n",i+1,data);return;}printf("經(jīng)過%d次查找，未能查找到數(shù)據(jù)%d.\n",i,data);}voidSearch(int*fp,intlength){intdata;printf("開始使用順序查詢.\n請輸入你想要查找的數(shù)據(jù).\n");scanf("%d",&data);printf("由于二分查找法要求數(shù)據(jù)是有序的，現(xiàn)在開始為數(shù)組排序.\n");Sort(fp,length);printf("數(shù)組現(xiàn)在已經(jīng)是從小到大排列,下面將開始查找.\n");intbottom,top,middle;bottom=0;top=length;inti=0;while(bottom<=top){middle=(bottom+top)/2;i++;if(fp[middle]<data){bottom=middle+1;}elseif(fp[middle]>data)數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第6頁。top=middle-1;}else{printf("經(jīng)過%d次查找，查找到數(shù)據(jù)%d.\n",i,data);return;}}printf("經(jīng)過%d次查找，未能查找到數(shù)據(jù)%d.\n",i,data);}voidSort(int*fp,intlength){printf("現(xiàn)在開始為數(shù)組排序，排列結(jié)果將是從小到大.\n");inttemp;for(inti=0;i<length;i++)for(intj=0;j<length-i-1;j++)if(fp[j]>fp[j+1]){temp=fp[j];fp[j]=fp[j+1];fp[j+1]=temp;}printf("排序完成!\n下面輸出排序后的數(shù)組:\n");for(intk=0;k<length;k++){printf("%5d",fp[k]);}printf("\n");}structhash{intkey;intsi;};structhashhlist[11];inti,adr,sum,d;數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第7頁。floataverage;voidchash(int*arr,intn){for(i=0;i<11;i++){hlist[i].key=0;hlist[i].si=0;}for(i=0;i<n;i++){sum=0;adr=(3*arr[i])%11;d=adr;if(hlist[adr].key==0){hlist[adr].key=arr[i];hlist[adr].si=1;}else{do{d=(d+(arr[i]*7)%10+1)%11;sum=sum+1;}while(hlist[d].key!=0);hlist[d].key=arr[i];hlist[d].si=sum+1;數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第8頁。}}}voiddhash(int*arr,intn){printf("哈希表顯示為:");for(i=0;i<11;i++)printf("%4d",i);printf("\n");printf("哈希表關(guān)鍵字:");for(i=0;i<11;i++)printf("%4d",hlist[i].key);printf("\n");printf("查找長度是:");for(i=0;i<11;i++)printf("%4d",hlist[i].si);printf("\n");average=0.0;for(i=0;i<11;i++)average=average+hlist[i].si;average=average/n;printf("平均長度:asl(%d)=%f\n",n,average);}voidmain()數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第9頁。數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告全文共13頁，當(dāng)前為第9頁。intcount;intarr[LENGTH];ElemTypeitem;charchoice;BSTreeroot=NULL,ret;/*必須賦予NULL值，否則出錯(cuò)*/BOOLfinish=FALSE;printf("請輸入你的數(shù)據(jù)的個(gè)數(shù):\n");scanf("%d",&count);printf("請輸入%d個(gè)數(shù)據(jù)\n",count);for(inti=0;i<count;i++){scanf("%d",&arr[i]);item=arr[i];if(-10000!=item)Insert(&root,item);}printf("當(dāng)前已經(jīng)生成的數(shù)列：\n");for(i=0;i<count;i++){printf("%d",arr[i]);}printf("\n當(dāng)前已經(jīng)生成的二叉樹：\n");showbitree(root);