2024年動態(tài)查找表實驗報告

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

ADTDynamicSearchTable{

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

標識數(shù)據(jù)元素。

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

基本操作P：

InitDSTable(&DT);

操作成果：結構一個空的動態(tài)查找表DT。

DestroyDSTable(&DT);

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

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

SearchDSTable(DT,key);

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

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

則為“空”。

InsertDSTable(&DT,e);

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

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

DeleteDSTable(&T,key);

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

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

TraverseDSTable(DT,Visit());

初始條件：動態(tài)查找表DT存在，Visit是對結點操作的應用函數(shù)；

操作成果：按某種次序對DT的每個結點調用函數(shù)visit()一次且至多一次。一旦visit()失敗，則

操作失敗。

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