2024年動(dòng)態(tài)查找表實(shí)驗(yàn)報(bào)告

動(dòng)態(tài)查找表試驗(yàn)報(bào)告一.1、試驗(yàn)概要試驗(yàn)項(xiàng)目名稱:抽象數(shù)據(jù)類型的實(shí)現(xiàn)試驗(yàn)項(xiàng)目性質(zhì):設(shè)計(jì)性試驗(yàn)所屬課程名稱:數(shù)據(jù)結(jié)構(gòu)試驗(yàn)計(jì)劃學(xué)時(shí):62、試驗(yàn)?zāi)繕?biāo)對(duì)某個(gè)詳細(xì)的抽象數(shù)據(jù)類型，利用課程所學(xué)的知識(shí)和措施，設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上實(shí)現(xiàn)該抽象數(shù)據(jù)類型的所有基本操作。通過(guò)本設(shè)計(jì)性試驗(yàn)，檢查所學(xué)知識(shí)和能力，發(fā)覺(jué)學(xué)習(xí)中存在的問(wèn)題。進(jìn)而達(dá)成純熟地利用本課程中的基礎(chǔ)知識(shí)及技術(shù)的目標(biāo)。試驗(yàn)要求如下：1．參加試驗(yàn)的學(xué)生應(yīng)首先了解設(shè)計(jì)的任務(wù)，然后依照自己的基礎(chǔ)和能力從中選擇一題。一般來(lái)說(shuō)，選擇題目應(yīng)以在要求的時(shí)間內(nèi)能完成，并能得到應(yīng)有的鍛煉為標(biāo)準(zhǔn)。若學(xué)生對(duì)教材以外的有關(guān)題目較感興趣，希望選作試驗(yàn)的題目時(shí)，應(yīng)征得指引教師的認(rèn)可，并寫出明確的抽象數(shù)據(jù)類型定義及闡明。2.試驗(yàn)前要作好充足準(zhǔn)備，包括：了解試驗(yàn)要求，掌握輔助工具的使用，了解該抽象數(shù)據(jù)類型的定義及意義，以及其基本操作的算法并設(shè)計(jì)合理的存儲(chǔ)結(jié)構(gòu)。3.試驗(yàn)時(shí)嚴(yán)肅仔細(xì)，要嚴(yán)格按照要求獨(dú)立進(jìn)行設(shè)計(jì)，不能隨意更改。注意觀測(cè)并統(tǒng)計(jì)各種錯(cuò)誤現(xiàn)象，糾正錯(cuò)誤，使程序滿足預(yù)定的要求，試驗(yàn)統(tǒng)計(jì)應(yīng)作為試驗(yàn)報(bào)告的一部分。4.試驗(yàn)后要及時(shí)總結(jié)，寫出試驗(yàn)報(bào)告，并附所打印的問(wèn)題解答、程序清單，所輸入的數(shù)據(jù)及對(duì)應(yīng)的運(yùn)行成果。所用軟件環(huán)境或工具：DEV-C++5可視化編程環(huán)境.3.動(dòng)態(tài)查找表的抽象數(shù)據(jù)類型

ADTDynamicSearchTable{

數(shù)據(jù)對(duì)象D：D是具備相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素含有類型相同的核心字，可唯一

標(biāo)識(shí)數(shù)據(jù)元素。

數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)集合。

基本操作P：

InitDSTable(&DT);

操作成果：結(jié)構(gòu)一個(gè)空的動(dòng)態(tài)查找表DT。

DestroyDSTable(&DT);

初始條件：動(dòng)態(tài)查找表DT存在；

操作成果：銷毀動(dòng)態(tài)查找表DT。

SearchDSTable(DT,key);

初始條件：動(dòng)態(tài)查找表DT存在，key為和核心字類型相同的給定值；

操作成果：若DT中存在其核心字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否

則為“空”。

InsertDSTable(&DT,e);

初始條件：動(dòng)態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素；

操作成果：若DT中不存在其核心字等于e.key的數(shù)據(jù)元素，則插入e到DT。

DeleteDSTable(&T,key);

初始條件：動(dòng)態(tài)查找表DT存在，key為和核心字類型相同的給定值；

操作成果：若DT中存在其核心字等于key的數(shù)據(jù)元素，則刪除之。

TraverseDSTable(DT,Visit());

初始條件：動(dòng)態(tài)查找表DT存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；

操作成果：按某種次序?qū)T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則

操作失敗。

}ADTDynamicSearchTable動(dòng)態(tài)查找表的特點(diǎn)二叉排序樹(shù)是一個(gè)動(dòng)態(tài)樹(shù)表，其特點(diǎn)是，樹(shù)的結(jié)構(gòu)一般不是一資生成的，面是在查找過(guò)程中，當(dāng)樹(shù)中不存在核心字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找途徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。算法設(shè)計(jì)#include<stdio.h>#include<malloc.h>#include<conio.h>#include<cstdlib>#include<iostream>typedefstructElemType{ intkey;}ElemType;typedefstructbitnode{//二叉樹(shù)的二叉鏈表存儲(chǔ)表示 ElemTypedata; structbitnode*lchild,*rchild;//左右孩子指針 intlength;}bitnode,*bitree;bitreeSearch(bitreeT,ElemTypee,bitreef,bitree&p)//在二叉排序樹(shù)中查找數(shù)據(jù){ if(!T) { p=f; returnNULL; }//查找不成功 elseif(T->data.key==e.key) { p=T;returnT; }//查找成功 elseif(T->data.key>e.key) returnSearch(T->lchild,e,T,p); else returnSearch(T->rchild,e,T,p);}//在二叉排序樹(shù)中查找數(shù)據(jù)voidInsert(bitree&T,ElemTypee)//在二叉排序樹(shù)中插入數(shù)據(jù){ bitreep,s; if(!Search(T,e,NULL,p))//查找不成功 { s=(bitree)malloc(sizeof(bitnode)); s->data=e; s->lchild=s->rchild=NULL; if(!p)T=s;//被插入結(jié)點(diǎn)*s為新的根結(jié)點(diǎn) elseif(e.key<p->data.key)p->lchild=s;//被插結(jié)點(diǎn)*s為左孩子 elsep->rchild=s;//被插結(jié)點(diǎn)*s為右孩子 return; } elsereturn;}voidInit(bitree&T)//結(jié)構(gòu)一個(gè)動(dòng)態(tài)查找表T{intx;inti;intn;ElemTypee; printf("請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù):"); scanf("%d",&x); for(i=1;i<=x;i++) { printf("第%d個(gè)結(jié)點(diǎn)數(shù)據(jù)值:",i); scanf("%d",&n); e.key=n; Insert(T,e); }printf("二叉排序樹(shù)已經(jīng)建立!\n");}voidDestory(bitreeT)//后序遍歷二叉樹(shù)，銷毀動(dòng)態(tài)查找表T{ if(T) {if(T->lchild) DestoryTree(T->lchild);if(T->rchild) DestoryTree(T->rchild); free(T); T=NULL; }}voidDelete(bitree&p)//從二叉排序樹(shù)中刪除結(jié)點(diǎn)p，并重接它的左或右子樹(shù){ bitreeq,s; if(!p->rchild)//右子樹(shù)空，只需重接它的左子樹(shù) { q=p; p=p->lchild; free(q); q=NULL; } elseif(!p->lchild)//左子樹(shù)空，只需重接它的右子樹(shù) { q=p; p=p->rchild; free(q); q=NULL; } else{//左右子樹(shù)均不空 q=p; s=p->lchild; while(s->rchild)//向右走到盡頭 { q=s; s=s->rchild; } p->data=s->data;//將被刪結(jié)點(diǎn)的前驅(qū)s的內(nèi)容直接替代該結(jié)點(diǎn)的內(nèi)容 if(q!=p)//若被刪除結(jié)點(diǎn)的左子樹(shù)的右子樹(shù)不為空 q->rchild=s->lchild;//重接*q的右子樹(shù) else q->lchild=s->lchild;//重接*q的左子樹(shù) free(s); s=NULL; }}//刪除結(jié)點(diǎn)voidDeletebit(bitree&T,intn)//刪除二叉排序樹(shù)中的數(shù)據(jù){ if(!T) return;//不存在核心字等于n的數(shù)據(jù)元素 else{ if(T->data.key==n) return(Delete(T));//找到核心字等于n的數(shù)據(jù)元素并刪除它 elseif(T->data.key>n) Deletebit(T->lchild,n);//繼續(xù)在左子樹(shù)中刪除 else Deletebit(T->rchild,n);//繼續(xù)在右子樹(shù)中刪除 return; }}voidXianxu(bitreeT)//先序遍歷{ if(T!=NULL) { printf("%d\t",T->data.key); Xianxu(T->lchild); Xianxu(T->rchild); }}voidZhongxu(bitreeT)//中序遍歷{ if(T!=NULL) { Zhongxu(T->lchild); printf("%d\t",T->data.key); Zhongxu(T->rchild); }}voidHouxu(bitreeT)//后序遍歷{ if(T!=NULL) { Houxu(T->lchild); Houxu(T->rchild); printf("%d\t",T->data.key); }}intmain(){ bitreeT=NULL,p; ElemTypee; intn; inth; charc;do{printf("***********************************************************\n");printf("**\n");printf("*動(dòng)態(tài)查找表*\n");printf("*1.建立二叉排序樹(shù)*\n");printf("*2.二叉排序樹(shù)查找元素*\n");printf("*3.二叉排序樹(shù)插入元素*\n");printf("*4.二叉排序樹(shù)刪除元素*\n");printf("*5.遍歷二叉排序樹(shù)*\n");printf("*6.銷毀二叉排序樹(shù)*\n");printf("*7.退出*\n");printf("**\n");printf("***********************************************************\n"); printf("請(qǐng)輸入你的選擇:\n"); scanf("%d",&h); switch(h) { case1: Init(T); break; case2:chara; printf("請(qǐng)輸入要查找的數(shù)據(jù):\n"); scanf("%d",&n); e.key=n; if(Search(T,e,NULL,p)) printf("數(shù)據(jù)已經(jīng)存在!\n"); else { printf("數(shù)據(jù)不存在!\n"); } break; case3: printf("請(qǐng)輸入要插入的數(shù)據(jù):\n"); scanf("%d",&n); e.key=n; if(Search(T,e,NULL,p)) printf("已經(jīng)存在!\n"); else { Insert(T,e); printf("成功插入!\n"); } break; case4: printf("請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù):\n"); scanf("%d",&n); e.key=n; if(Search(T,e,NULL,p)) { Deletebit(T,n); printf("已經(jīng)成功刪除!\n"); } elseprintf("數(shù)據(jù)不存在!\n"); break; case5:intz;do {printf("********************************************************************\n");printf("**\n");printf("*遍歷二叉排序樹(shù)*\n");printf("*1.先序遍歷二叉排序樹(shù)*\n");printf("*2.中序遍歷二叉排序樹(shù)*\n");printf("*3.后序遍歷二叉排序樹(shù)*\n");printf("*4.退出*\n");printf("**\n");printf("********************************************************************\n");printf("請(qǐng)輸入你的選擇:\n");scanf("%d",&z);switch(z) {case1: printf("先序遍歷二叉排序樹(shù):"); Xianxu(T); printf("\n"); break; case2: printf("中序遍歷二叉排序樹(shù):"); Zhongxu(T); printf("\n"); break; case3: printf("后序遍歷二叉排序樹(shù):"); Houxu(T); printf("\n"); break;case4: printf("退出!返回上級(jí)菜單！\n"); break; default:printf("選擇錯(cuò)誤，重新開(kāi)始!\n");}}while(z!=4);break;case6: printf("確定是否要銷毀二叉排序樹(shù)?(y/n)\n");scanf("\n%c",&c); getch(); if(c=='y') { Destory(T); printf("所選數(shù)據(jù)已成功銷毀!\n"); getch(); T=NULL;} else printf("所選數(shù)據(jù)銷毀失敗!\n"); break;case7: printf("退出！\n"); break; default:printf("選擇錯(cuò)誤，重新開(kāi)始!\n"); }}while(h!=7);}調(diào)試主頁(yè)面建立二叉排序樹(shù)輸入十個(gè)數(shù)據(jù)：10,15,26,96,82,37,46,50,61,03,99查找元素:26存在則輸出插入元素：刪除元素：56（不存在）99（存在）遍歷：跳入二級(jí)子菜單，里邊分別有三種遍歷方式可供選擇，分別為先序，中序，后序6.在子菜單中選擇4退出則返回到上級(jí)菜單，即主頁(yè)面7銷毀二叉樹(shù)：先問(wèn)詢是否確認(rèn)要銷毀，輸入y則銷毀