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

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

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

3、visit();初始條件：動態(tài)查找表dt存在，visit是對結(jié)點操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)t的每個結(jié)點調(diào)用函數(shù)visit()一次且至多一次，一旦visit()失敗，則操作失敗。adt dynamicsearchtable二. 存儲結(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ù)元素個數(shù) */typedef int status; /* status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如ok等 *

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

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

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

7、child,key);elsereturn searchbst(t-rchild,key); /* 在右子樹中繼續(xù)查找*/* 在根指針t所指二叉排序樹中遞歸地查找其關(guān)鍵字等于key的數(shù)據(jù)元素，若查找*/* 成功，則指針p指向該數(shù)據(jù)元素結(jié)點，并返回true，否則指針p指向查找路徑上*/* 訪問的最后一個結(jié)點并返回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); /* 在左子樹中繼續(xù)查找*/elsesearchbst1(&(*t)-rchild,key,*t,p,flag); /* 在右子樹中繼續(xù)查找*/* 當(dāng)二叉排序樹t中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時，插入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é)點*s為新的根結(jié)點*/else if lt(e.key,p-data.key)p-lchild=s; /* 被插結(jié)點*s為左孩子*/elsep-rchild=s; /* 被插結(jié)點*s為右孩子*/return true;elsereturn false; /* 樹中已有關(guān)鍵字相同的結(jié)點，不再插入*/* 從

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

11、ata=s-data; /* s指向被刪結(jié)點的前驅(qū)（將被刪結(jié)點前驅(qū)的值取代被刪結(jié)點的值）*/if(q!=*p)q-rchild=s-lchild; /* 重接*q的右子樹*/elseq-lchild=s-lchild; /* 重接*q的左子樹*/free(s);/* 若二叉排序樹t中存在關(guān)鍵字等于key的數(shù)據(jù)元素時，則刪除該數(shù)據(jù)元素結(jié)點，*/* 并返回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;/* 初始條件: 動態(tài)查找表dt存在，visit是對結(jié)點操作的應(yīng)用函數(shù)*/* 操作結(jié)果: 按關(guān)鍵字的順序?qū)t的每個結(jié)點調(diào)用函數(shù)visit()一次且至多一次*/void traversedstable(bitree dt,void(*visit)(elemtype1)if(dt)traversedstable(dt-lchil

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

14、s);void main() /*用于測試二叉排序樹的查找*/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; /* 測試數(shù)據(jù)*/ initdstable(&dt); /* 構(gòu)造空表*/for(i=0;iinsertbst(&dt,ri); /* 依次插入數(shù)據(jù)元素*/h1: printf(=動態(tài)查找表演示系統(tǒng)=);printf(n);printf(1、遍歷原有表n);printf(2、查找表內(nèi)值n);print

15、f(3、刪除表內(nèi)值n);printf(4、插入一個值n);printf(5、銷毀表n);printf(6、退出系統(tǒng));printf(n);printf(請選擇你需要的操作（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請輸入你要查找的值：);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(查找失敗，表中無此值，是否繼續(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請輸入你要刪除的值：);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(刪除失敗，表中無此值，請按任意鍵返回繼續(xù).);printf(n);getchar();getchar();goto h4;h5: case 4:printf(原有的表遍歷如下：n);traversedstable(dt,print);printf(n);printf(請輸入你要插入的值：);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