數(shù)據(jù)結(jié)構(gòu)實驗報告七

1、云南大學(xué)軟件學(xué)院 數(shù)據(jù)結(jié)構(gòu)實驗報告 （本實驗項目方案受“教育部人才培養(yǎng)模式創(chuàng)新實驗區(qū)（X3108005）”項目資助） 實驗難度： A B C 序號學(xué)號姓名成績120111120181董呢喃220111120143羅淑靜3指導(dǎo)教師 （簽名）學(xué)期：2010秋季學(xué)期 任課教師: 秦江龍 實驗題目: 哈希表查找 小 組 長: 聯(lián)系電話: 電子郵件: 完成提交時間:2012年12月16日云南大學(xué)軟件學(xué)院2010學(xué)年 秋季 學(xué)期數(shù)據(jù)結(jié)構(gòu)實驗成績考核表學(xué)號： 20111120143 姓名： 羅淑靜 本人承擔(dān)角色： 程序設(shè)計、算法分析 評分項目評分指標(biāo)分值得分實驗構(gòu)思（10%）1. 實驗?zāi)康拿鞔_52. 實驗內(nèi)

2、容理解透徹、對實驗所涉及到的知識點分析到位5實驗設(shè)計（15%）1. 有對基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型定義52. 實驗方案設(shè)計完整，數(shù)據(jù)結(jié)構(gòu)、算法選擇合理 53.算法結(jié)構(gòu)和程序功能模塊之間邏輯清晰、有相應(yīng)的流程圖5實驗實現(xiàn)（25%）1. 代碼編寫規(guī)范、風(fēng)格統(tǒng)一、注釋清楚易讀 52. 程序運行正常，測試結(jié)果正確153. 界面友好、易于操作、有較強(qiáng)的容錯性5實驗報告撰寫（10%）1. 內(nèi)容詳實無缺漏，文字流暢、圖表清楚52. 實驗結(jié)果分析客觀、詳細(xì)，實驗體會真實可信，對原實驗方案的改進(jìn)和對實驗內(nèi)容的發(fā)散性思考5個人工作量（30%）1. 個人完成工作量152. 個人技術(shù)水平103. 團(tuán)隊合作精神5實驗運

3、作（10%）1. 有一定用戶群52. 應(yīng)用前景分析5綜合得分： （滿分100分）指導(dǎo)教師： 年 月 日（注：此表在難度為C時使用，每個成員一份。）云南大學(xué)軟件學(xué)院2010學(xué)年 秋季 學(xué)期數(shù)據(jù)結(jié)構(gòu)實驗成績考核表學(xué)號： 20111120181 姓名： 董呢喃 本人承擔(dān)角色： 算法分析、后期調(diào)試 評分項目評分指標(biāo)分值得分實驗構(gòu)思（10%）1. 實驗?zāi)康拿鞔_52. 實驗內(nèi)容理解透徹、對實驗所涉及到的知識點分析到位5實驗設(shè)計（15%）1. 有對基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型定義52. 實驗方案設(shè)計完整，數(shù)據(jù)結(jié)構(gòu)、算法選擇合理 53.算法結(jié)構(gòu)和程序功能模塊之間邏輯清晰、有相應(yīng)的流程圖5實驗實現(xiàn)（25%）1.

4、代碼編寫規(guī)范、風(fēng)格統(tǒng)一、注釋清楚易讀 52. 程序運行正常，測試結(jié)果正確153. 界面友好、易于操作、有較強(qiáng)的容錯性5實驗報告撰寫（10%）1. 內(nèi)容詳實無缺漏，文字流暢、圖表清楚52. 實驗結(jié)果分析客觀、詳細(xì)，實驗體會真實可信，對原實驗方案的改進(jìn)和對實驗內(nèi)容的發(fā)散性思考5個人工作量（30%）1. 個人完成工作量152. 個人技術(shù)水平103. 團(tuán)隊合作精神5實驗運作（10%）1. 有一定用戶群52. 應(yīng)用前景分析5綜合得分： （滿分100分）指導(dǎo)教師： 年 月 日（注：此表在難度為C時使用，每個成員一份。）一、【實驗構(gòu)思（Conceive）】(10%)實現(xiàn)下列操作:構(gòu)造空表、銷毀表、搜索指定關(guān)

5、鍵字的元素、插入新元素、刪除指定關(guān)鍵字的元素、遍歷表中所有元素。二、【實驗設(shè)計(Design)】(20%)ADT DynamicSearchTable數(shù)據(jù)對象：D是具有相同特性的數(shù)據(jù)元素的集合，各個數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系：數(shù)據(jù)元素同屬一個集合?；静僮鳎築SP InitBST(BiTree &T)操作結(jié)果：構(gòu)造一棵空樹BSP createBst(key)操作結(jié)果：建立一個二叉樹結(jié)點void traverseBST(BSP T)操作結(jié)果：中序遍歷（遞歸）動態(tài)查找表（二叉鏈表），并打印結(jié)點值BSP FindMin(BSP T)操作結(jié)果：找到關(guān)鍵字最小的

6、結(jié)點，即最左邊的節(jié)點int SearchBST(BiTree T,int key,BiTree f,BiTree &p)操作結(jié)果：在根指針T所指的二叉樹中遞歸地查找其關(guān)鍵字等于key的元素，查找成功：指針p指向該結(jié)點，并返回TRUE，否則：p指向查找路徑上訪問的最后一個結(jié)點，即插入位置，并返回FALSEint InsertBST(BiTree &T,TElemType e) 當(dāng)二叉樹T中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素事，插入e并返回TRUE，否則返回FLASEint DeleteBST(BiTree &T,int key) 操作結(jié)果：查找樹T中是否存在關(guān)鍵字等于k

7、ey的數(shù)據(jù)元素，存在：刪除，并返回TRUE，不存在：返回FALSEvoid DestoryBST(BiTree &T) 操作結(jié)果：銷毀二叉樹ADT DynamicSearchTable三、【實現(xiàn)描述（Implement）】(30%)1.抽象數(shù)據(jù)類型具體實現(xiàn)的函數(shù)原型說明:typedef int keytype; /定義關(guān)鍵字類型typedef struct Bnodekeytype data;struct Bnode *lchild,*rchild;BST,*BSP; / 定義樹節(jié)點類型2.函數(shù)的調(diào)用關(guān)系：（在main函數(shù)中）int select=0,flag=1,a; /操作選擇字符

8、，循環(huán)控制字符，查找函數(shù)返回值接受符 T=NULL; while(flag) /操作選擇 printf("1-創(chuàng)建2叉查找樹n"); printf("2-插入元素n"); printf("3-查找元素n"); printf("4-刪除元素n"); printf("5-刪除表n"); printf("6-退出n"); printf("請選擇操做n"); scanf("%d",&select); switch(select) cas

9、e 1: /創(chuàng)建二叉查找表 printf("請輸入關(guān)鍵字,0結(jié)束n"); scanf("%d",&key); while(key!=0) S=createBst(key); T=InsertBST(T,S); printf("請繼續(xù)輸入："); scanf("%d",&key); printf("查找表為n"); traverseBST(T); printf("nn"); break; case 2: /插入元素 printf("請輸入要插入的元素；

10、n"); scanf("%d",&key); S=createBst(key); T=InsertBST(T,S); printf("n插入成功n"); printf("插入的元素為：n"); traverseBST(S); printf("nn"); break; case 3: /查找元素 printf("請輸入要查找的元素：n"); scanf("%d",&key); a=Search(T,key); printf("nn"

11、); break; case 4: /刪除元素 printf("請輸入要刪除的元素：n"); scanf("%d",&key); DeleteBST(T,key); printf("nn"); break; case 5:/銷毀二叉查找表 DestroyBST(T); printf("刪除成功"); case 6: /退出 flag=0; break; 3、其中部分操作的偽碼算法如下：1)BSP InitBST() BSP T; T->data=0; T->lchild=T->rchild

12、=NULL; return T;2)void DestroyBST(BSP T) if(T) /中序刪除各結(jié)點 DestroyBST(T->lchild); T->data=NULL; free(T); DestroyBST(T->rchild); 3)BSP createBst(keytype key) /建立一個二叉樹結(jié)點 BSP s; s=(BSP)malloc(sizeof(BST); s->data=key; s->lchild=s->rchild=NULL; return s;4)BSP InsertBST(BSP T,BSP S) BSP p,

13、q; if(T=NULL) return S; else p=T; q=NULL; while(p) /樹不空時，依次查看 q=p; if(S->data=p->data) /找到與關(guān)鍵字相同的結(jié)點，返回 printf("該元素已在表中"); return T; if(S->data<p->data) /關(guān)鍵字小于當(dāng)前結(jié)點關(guān)鍵字，查看左孩子 p=p->lchild; else /否則查看右孩子 p=p->rchild; if(S->data<q->data) /關(guān)鍵字小于當(dāng)前結(jié)點，插入做左孩子 q->lchi

14、ld=S; else /否則插入做右孩子 q->rchild=S; return T; 5)int Search(BSP T,keytype x) BSP p; if(T=NULL) printf("error"); else p=T; while(p) /樹不空時，依次查找 if(p->data=x) printf("查找成功"); return 0; else if(x<p->data) p=p->lchild; else p=p->rchild; if(!p) /樹空表示沒找到 printf("所找元素

15、不存在"); return 0;6)void traverseBST(BSP T) if(T) /中序遍歷，打印關(guān)鍵字 traverseBST(T->lchild); printf("%d",T->data); traverseBST(T->rchild); 7)BSP FindMin(BSP T) /找到關(guān)鍵字最小的結(jié)點，即最左邊的節(jié)點 if(T=NULL) return NULL; else if(T->lchild=NULL) return T; else return FindMin(T->lchild);8)BSP Dele

16、teBST(BSP T,keytype x) keytype y; BSP p; if(T=NULL) printf("錯誤"); else if(x<T->data) /關(guān)鍵字小于當(dāng)前節(jié)點，則看左孩子 T->lchild=DeleteBST(T->lchild,x); else if(x>T->data) /關(guān)鍵字大于當(dāng)前節(jié)點，則看又孩子 T->rchild=DeleteBST(T->rchild,x); else if(T->lchild!=NULL&&T->rchild!=NULL) /左右孩子都不空，則找到最小節(jié)點代替 p=FindMin(T->rchild); T->data=p->data; T->rchild=DeleteBST(T->rchild,T->data); else p=T; if(T->lchild=NULL) /左孩子空，則用右孩子代替 T=T->rchild; else if(T->rchild=NULL)/右孩子空，則用左孩子代替 T=