數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-動(dòng)態(tài)查找表實(shí)驗(yàn)報(bào)告1

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-動(dòng)態(tài)查找表實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告題目：動(dòng)態(tài)查找表學(xué)院計(jì)算機(jī)專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)年級(jí)班別2009級(jí) 2 班學(xué)號(hào)3109005935學(xué)生姓名黃麗敏指導(dǎo)教師吳偉民成績(jī)_2011年6月 一. 動(dòng)態(tài)查找表： 抽象數(shù)據(jù)類型動(dòng)態(tài)查找表的定義如下：adt dynamicsearchtable數(shù)據(jù)對(duì)象d：d是具有相同特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字?jǐn)?shù)據(jù)關(guān)系r：數(shù)據(jù)元素同屬一個(gè)集合?；静僮鱬：initdstable(&dt);操作結(jié)果：構(gòu)造一個(gè)空的動(dòng)態(tài)查找表dt。destroydstable(&dt)初始條件：動(dòng)態(tài)查找表dt存在。操作結(jié)果：銷毀動(dòng)態(tài)

2、查找表dt。searchdstable(dt,key);初始條件：動(dòng)態(tài)查找表dt存在，key為和關(guān)鍵字類型相同的給定值。操作結(jié)果：若dt中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。insertdstable(&dt,e);初始條件：動(dòng)態(tài)查找表dt存在，e為待插入的數(shù)據(jù)元素。操作結(jié)果：若dt中不存在其關(guān)鍵字等于e.key的數(shù)據(jù)元素，則插入e到dt。deletedstable(&dt,key);初始條件：動(dòng)態(tài)查找表dt存在，key為和關(guān)鍵字類型相同的給定值。操作結(jié)果：若dt中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之。traversedstable(dt,

3、visit();初始條件：動(dòng)態(tài)查找表dt存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)t的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次，一旦visit()失敗，則操作失敗。adt dynamicsearchtable二. 存儲(chǔ)結(jié)構(gòu)定義：公用頭文件ds0.h和宏定義:#include /* eof(=z或f6),null */#include#define true 1#define false 0#define ok 1#define n 10 /* 數(shù)據(jù)元素個(gè)數(shù) */typedef int status; /* status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如ok等 *

4、/typedef int keytype; /* 設(shè)關(guān)鍵字域?yàn)檎?*/#define eq(a,b) (a)=(b)#define lt(a,b) (a) 二叉排序樹(shù)存儲(chǔ)結(jié)構(gòu)： 二叉排序樹(shù)的類型bitree定義如下：typedef int keytype; /* 設(shè)關(guān)鍵字域?yàn)檎?/typedef structkeytype key;int others; elemtype; /* 數(shù)據(jù)元素類型*/typedef elemtype telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild; /*

5、 左右孩子指針*/bitnode,*bitree;三、算法設(shè)計(jì)：/* 操作結(jié)果: 構(gòu)造一個(gè)空的動(dòng)態(tài)查找表dt */status initdstable(bitree *dt)*dt=null;return ok;/* 初始條件: 動(dòng)態(tài)查找表dt存在。操作結(jié)果: 銷毀動(dòng)態(tài)查找表dt */void destroydstable(bitree *dt) /* 同bo6-2.c */if(*dt) /* 非空樹(shù)*/if(*dt)-lchild) /* 有左孩子*/destroydstable(&(*dt)-lchild); /* 銷毀左孩子子樹(shù)*/if(*dt)-rchild) /* 有右孩子*/de

6、stroydstable(&(*dt)-rchild); /* 銷毀右孩子子樹(shù)*/free(*dt); /* 釋放根結(jié)點(diǎn)*/*dt=null; /* 空指針賦0 */* 在根指針t所指二叉排序樹(shù)中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素，*/* 若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針,否則返回空指針。*/ bitree searchbst(bitree t,keytype1 key) if(!t)|eq(key,t-data.key)return t; /* 查找結(jié)束*/else if lt(key,t-data.key) /* 在左子樹(shù)中繼續(xù)查找*/return searchbst(t-l

7、child,key);elsereturn searchbst(t-rchild,key); /* 在右子樹(shù)中繼續(xù)查找*/* 在根指針t所指二叉排序樹(shù)中遞歸地查找其關(guān)鍵字等于key的數(shù)據(jù)元素，若查找*/* 成功，則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)，并返回true，否則指針p指向查找路徑上*/* 訪問(wèn)的最后一個(gè)結(jié)點(diǎn)并返回false,指針f指向t的雙親，其初始調(diào)用值為null */void searchbst1(bitree *t,keytype1 key,bitree f,bitree *p,status *flag)if(!*t) /* 查找不成功*/*p=f;*flag=false;else if

8、eq(key,(*t)-data.key) /* 查找成功*/*p=*t;*flag=true;else if lt(key,(*t)-data.key)searchbst1(&(*t)-lchild,key,*t,p,flag); /* 在左子樹(shù)中繼續(xù)查找*/elsesearchbst1(&(*t)-rchild,key,*t,p,flag); /* 在右子樹(shù)中繼續(xù)查找*/* 當(dāng)二叉排序樹(shù)t中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時(shí)，插入e并返回true，*/* 否則返回false。*/status insertbst(bitree *t, elemtype1 e)bitree p,s;sta

9、tus flag; searchbst1(t,e.key,null,&p,&flag); if(!flag) /* 查找不成功*/s=(bitree)malloc(sizeof(bitnode);s-data=e;s-lchild=s-rchild=null;if(!p)*t=s; /* 被插結(jié)點(diǎn)*s為新的根結(jié)點(diǎn)*/else if lt(e.key,p-data.key)p-lchild=s; /* 被插結(jié)點(diǎn)*s為左孩子*/elsep-rchild=s; /* 被插結(jié)點(diǎn)*s為右孩子*/return true;elsereturn false; /* 樹(shù)中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入*/* 從

10、二叉排序樹(shù)中刪除結(jié)點(diǎn)p，并重接它的左或右子樹(shù)。*/void delete(bitree *p)bitree q,s;if(!(*p)-rchild) /* 右子樹(shù)空則只需重接它的左子樹(shù)（待刪結(jié)點(diǎn)是葉子也走此分支）*/q=*p;*p=(*p)-lchild;free(q);else if(!(*p)-lchild) /* 只需重接它的右子樹(shù)*/q=*p;*p=(*p)-rchild;free(q);else /* 左右子樹(shù)均不空*/q=*p;s=(*p)-lchild;while(s-rchild) /* 轉(zhuǎn)左，然后向右到盡頭（找待刪結(jié)點(diǎn)的前驅(qū)）*/q=s; s=s-rchild; (*p)-d

11、ata=s-data; /* s指向被刪結(jié)點(diǎn)的前驅(qū)（將被刪結(jié)點(diǎn)前驅(qū)的值取代被刪結(jié)點(diǎn)的值）*/if(q!=*p)q-rchild=s-lchild; /* 重接*q的右子樹(shù)*/elseq-lchild=s-lchild; /* 重接*q的左子樹(shù)*/free(s);/* 若二叉排序樹(shù)t中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，*/* 并返回true；否則返回false。*/status deletebst(bitree *t,keytype1 key)if(!*t) /* 不存在關(guān)鍵字等于key的數(shù)據(jù)元素*/return false;elseif eq(key,(*t)-data.

12、key) /* 找到關(guān)鍵字等于key的數(shù)據(jù)元素*/delete(t);else if lt(key,(*t)-data.key)deletebst(&(*t)-lchild,key);elsedeletebst(&(*t)-rchild,key);return true;/* 初始條件: 動(dòng)態(tài)查找表dt存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)*/* 操作結(jié)果: 按關(guān)鍵字的順序?qū)t的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次*/void traversedstable(bitree dt,void(*visit)(elemtype1)if(dt)traversedstable(dt-lchil

13、d,visit); /* 先中序遍歷左子樹(shù)*/visit(dt-data); /* 再訪問(wèn)根結(jié)點(diǎn)*/ traversedstable(dt-rchild,visit); /* 最后中序遍歷右子樹(shù)*/ 四、編譯：1.初次編譯會(huì)出現(xiàn)很多錯(cuò)誤，這主要是寫程序時(shí)的粗心大意還有一些潛在的定于或邏輯錯(cuò)誤，第一次運(yùn)行如下：2.錯(cuò)誤很多，經(jīng)過(guò)一番調(diào)試才發(fā)現(xiàn)定義結(jié)構(gòu)體時(shí)出了問(wèn)題，有些沒(méi)用到，有些重定義了，調(diào)試后如下：3.此時(shí)只剩下很少錯(cuò)誤，很明顯是i未定義，經(jīng)過(guò)修改調(diào)試后編譯通過(guò)。五、測(cè)試void print(elemtype c) /*以下主函數(shù)調(diào)用*/printf(%d,%d) ,c.key,c.other

14、s);void main() /*用于測(cè)試二叉排序樹(shù)的查找*/char q;bitree dt,p;int i,select;keytype j;elemtype k;elemtype r10=45,1,12,2,53,3,3,4,37,5,24,6,100,7,61,8,90,9,70,10; /* 測(cè)試數(shù)據(jù)*/ initdstable(&dt); /* 構(gòu)造空表*/for(i=0;iinsertbst(&dt,ri); /* 依次插入數(shù)據(jù)元素*/h1: printf(=動(dòng)態(tài)查找表演示系統(tǒng)=);printf(n);printf(1、遍歷原有表n);printf(2、查找表內(nèi)值n);print

15、f(3、刪除表內(nèi)值n);printf(4、插入一個(gè)值n);printf(5、銷毀表n);printf(6、退出系統(tǒng));printf(n);printf(請(qǐng)選擇你需要的操作（16）：);scanf(%d,&select);switch(select)h2: case 1:printf(原有的表遍歷如下：n);traversedstable(dt,print);printf(n);printf(按任意鍵返回.);getchar();getchar();system(cls);goto h1;h3: case 2:printf(原有的表遍歷如下：n);traversedstable(dt,print

16、);printf(n);printf(n請(qǐng)輸入你要查找的值：);scanf(%d,&j);p=searchbst(dt,j);if(p)printf(n查找成功：);printf(%d,%d),p-data.key,p-data.others);/getchar();getchar();printf(n是否繼續(xù)查找？(y/n):);q=getchar();getchar();if(q=y|q=y) else system(cls);goto h1;elseprintf(查找失敗，表中無(wú)此值，是否繼續(xù)查找？(y/n):);getchar();q=getchar();if(q=y|q=y)goto

17、 h2;elsesystem(cls);goto h1;h4: case 3:printf(原有的表遍歷如下：n);traversedstable(dt,print);printf(n);printf(n請(qǐng)輸入你要?jiǎng)h除的值：);scanf(%d,&j);/getchar();/q=getchar();p=searchbst(dt,j);if(p)printf(刪除此值后：n);deletebst(&dt,j);traversedstable(dt,print);printf(n是否繼續(xù)刪除？(y/n):);getchar();q=getchar();if(q=y|q=y)goto h4;els

18、esystem(cls);goto h1; elseprintf(刪除失敗，表中無(wú)此值，請(qǐng)按任意鍵返回繼續(xù).);printf(n);getchar();getchar();goto h4;h5: case 4:printf(原有的表遍歷如下：n);traversedstable(dt,print);printf(n);printf(請(qǐng)輸入你要插入的值：);scanf(%d,&k.key);p=searchbst(dt,k.key);if(!p)printf(插入此值后：n);k.others=k.others+(n+1);insertbst(&dt,k);traversedstable(dt,print);printf(n);printf(是否繼續(xù)插入新值？(y|n):);getchar();q=getchar();if(q=y|q=y)goto h5;elsesyste