《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-二叉排序樹(shù)應(yīng)用實(shí)驗(yàn)報(bào)告(共15頁(yè)).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-二叉排序樹(shù)應(yīng)用實(shí)驗(yàn)報(bào)告(共15頁(yè)).doc（15頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí) 驗(yàn) 報(bào) 告 實(shí)驗(yàn)課程：數(shù) 據(jù) 結(jié) 構(gòu) 實(shí)驗(yàn)項(xiàng)目：實(shí)驗(yàn)四二叉排序樹(shù)應(yīng)用 專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)： 姓 名： 學(xué) 號(hào)： 指導(dǎo)教師： 目 錄1、 問(wèn)題定義及需求分析 （1）問(wèn)題描述 （2）實(shí)驗(yàn)任務(wù) （3）需求分析二、概要設(shè)計(jì)： (1)抽象數(shù)據(jù)類(lèi)型定義 (2)主程序流程 (3) 模塊關(guān)系3、 詳細(xì)設(shè)計(jì) (1)數(shù)據(jù)類(lèi)型及存儲(chǔ)結(jié)構(gòu) (2)模塊設(shè)計(jì)4、 調(diào)試分析 (1)調(diào)試分析 (2)算法時(shí)空分析 (3)經(jīng)驗(yàn)體會(huì)5、 使用說(shuō)明 (1)程序使用說(shuō)明6、 測(cè)試結(jié)果 (1)運(yùn)行測(cè)試結(jié)果截圖7、 附錄 (1)源代碼1、 問(wèn)題定義及需求分析（1）實(shí)驗(yàn)?zāi)康?二叉排序樹(shù)應(yīng)用 問(wèn)題描

2、述 互聯(lián)網(wǎng)域名系統(tǒng)是一個(gè)典型的樹(shù)形層次結(jié)構(gòu)。從根節(jié)點(diǎn)往下的第一層是頂層域，如cn、com等，最底層（第四層）是葉子結(jié)點(diǎn)，如www等。因此，域名搜索可以構(gòu)造樹(shù)的結(jié)構(gòu)完成；（2）實(shí)驗(yàn)任務(wù) 設(shè)計(jì)基于二叉排序樹(shù)的搜索互聯(lián)網(wǎng)域名的程序。（3）需求分析： 1）采用二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)。 2）完成二叉排序樹(shù)的創(chuàng)建、插入、刪除、查詢(xún)操作。 3）可以考慮兩棵二叉排序樹(shù)的合并。2、 概要設(shè)計(jì)：(1)抽象數(shù)據(jù)類(lèi)型定義： 程序中定義了二叉排序樹(shù)的節(jié)點(diǎn)類(lèi)型；由數(shù)據(jù)域和左右孩子指針構(gòu)成；指針類(lèi)型為該節(jié)點(diǎn)類(lèi)型，指向該類(lèi)型的節(jié)點(diǎn)形成二叉排序樹(shù)；數(shù)據(jù)域是由字符數(shù)組構(gòu)成，用于存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)信息。(2) 主程序流程： 輸入域名

3、拆分域名并完成二叉排序樹(shù)的創(chuàng)建 調(diào)用功能函數(shù)進(jìn)入功能菜單 選擇執(zhí)行不同的操作(查找、插入、刪除) 操作完畢后可選擇返回功能函數(shù)繼續(xù)執(zhí)行操作或者結(jié)束程序 (3) 模塊間的調(diào)用關(guān)系: 創(chuàng)建二叉排序樹(shù) 功能函數(shù) 查找 插入 刪除 選擇 結(jié)束 三、詳細(xì)設(shè)計(jì) 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)的二叉排序樹(shù)的定義如下： typedef struct BiTNodeElemType data30; /定義數(shù)據(jù)域類(lèi)型為字符數(shù)組 struct BiTNode *lchild, *rchild; /定義左右孩子節(jié)點(diǎn)指針BiTNode, *BiTree;模塊1-查找樹(shù)中是否有待插入節(jié)點(diǎn)算法如下：int SearchBST(BiT

4、ree T, char *key, BiTree f, BiTree *p) if (!T) /* 查找不成功 */ *p = f; return 0; else if(strcmp(key,T->data)=0) /* 查找成功 */ *p = T; return 1; else if (strcmp(key,T->data)<0) return SearchBST(T->lchild, key, T, p); /* 若該節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)，則在左子樹(shù)中繼續(xù)查找 */ else return SearchBST(T->rchild, key, T, p); /*

5、否則在右子樹(shù)中繼續(xù)查找 */模塊2-插入節(jié)點(diǎn)算法如下：int InsertBST(BiTree *T, char *key) BiTree p,s; if (!SearchBST(*T, key, NULL, &p) /* 查找不成功 */ s = (BiTNode*)malloc(sizeof(BiTNode);strcpy(s->data, key); s->lchild = s->rchild = NULL; if (!p) *T = s; /* 插入s為新的根結(jié)點(diǎn) */ else if (strcmp(key,p->data)<0) p->l

6、child = s; /* 插入s為左孩子 */ else p->rchild = s; /* 插入s為右孩子 */ return 1; else return 0; /* 樹(shù)中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入 */模塊3-刪除節(jié)點(diǎn)算法如下：int Delete(BiTree *p) BiTree q,s; if(*p)->rchild=NULL) /* 右子樹(shù)空則只需重接它的左子樹(shù)（待刪結(jié)點(diǎn)是葉子也走此分支) */ q=*p;*p=(*p)->lchild;free(q); else if(*p)->lchild=NULL) /* 只需重接它的右子樹(shù) */ q=*p;

7、*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; strcpy(*p)->data,s->data); /* s指向被刪結(jié)點(diǎn)的直接前驅(qū)（將被刪結(jié)點(diǎn)前驅(qū)的值取代被刪結(jié)點(diǎn)的值） */ if(q!=*p) q->rchild=s->lchild; /* 重接q的右子樹(shù) */ else q->lchild=s->lchild; /* 重接

8、q的左子樹(shù) */ free(s); return 1;模塊4-查找待刪除節(jié)點(diǎn)的位置算法如下：int DeleteBST(BiTree *T,char *key) if(!*T) /* 不存在關(guān)鍵字等于key的數(shù)據(jù)元素 */ return 0; else if (strcmp(key,(*T)->data)=0) /* 找到關(guān)鍵字等于key的數(shù)據(jù)元素 */ return Delete(T); else if (strcmp(key,(*T)->data)<0) return DeleteBST(&(*T)->lchild,key);/* 若待刪除節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)，

9、則遞歸訪問(wèn)其左子樹(shù) */ else return DeleteBST(&(*T)->rchild,key);/* 否則訪問(wèn)右子樹(shù) */ 模塊5-功能函數(shù)包括查找、插入和刪除算法如下:void Gongneng(BiTNode *A)/ 執(zhí)行操作需將此樹(shù)的根節(jié)點(diǎn)傳入到此函數(shù)里面int k;char a30,c30,d30;printf("請(qǐng)選擇你的操作：n");printf("1-查找n");printf("2-刪除n");printf("3-插入n");printf("輸入：");

10、scanf("%d",&k);switch(k)/通過(guò)switch語(yǔ)句執(zhí)行不同的操作case 1 :system("cls");printf("請(qǐng)輸入你要查找的節(jié)點(diǎn)：");scanf("%s",c); Search(A, c); /調(diào)用查找函數(shù) break;case 2:system("cls");printf("請(qǐng)輸入你要?jiǎng)h除的節(jié)點(diǎn)：");scanf("%s",a);if(!DeleteBST(&A,a)printf("n不存在

11、此節(jié)點(diǎn)！n");elseprintf("n刪除節(jié)點(diǎn)成功！nn刪除后樹(shù)的中序遍歷結(jié)果如下：n");InOrder(A); break;case 3:system("cls");printf("請(qǐng)輸入要插入的節(jié)點(diǎn)：");scanf("%s",d);if(!InsertBST(&A,d)printf("插入失敗!要插入的節(jié)點(diǎn)已存在!n");elseprintf("n插入成功!nn插入后樹(shù)的中序遍歷結(jié)果如下：n"); InOrder(A);break; default : printf("輸入數(shù)值錯(cuò)誤!n");四、調(diào)試分析 問(wèn)題及解決方法： 在編寫(xiě)功能函數(shù)時(shí)，在參數(shù)的傳遞上出現(xiàn)了問(wèn)題；無(wú)法正確的將根節(jié)點(diǎn)傳入到功能函數(shù)里，導(dǎo)致功能函數(shù)無(wú)法正常運(yùn)行；解決方法為：void Gongneng(BiTNode *A)； 時(shí)空分析： 由于采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，所以在插入和刪除算法的時(shí)間復(fù)雜度較低；而對(duì)于較多的數(shù)據(jù)元素形成的樹(shù)時(shí)，查找算法在時(shí)間復(fù)雜度上不算簡(jiǎn)便；而存儲(chǔ)方面，二叉鏈表構(gòu)成的二叉排序樹(shù)存儲(chǔ)較為方便且空間利用率高； 經(jīng)驗(yàn)體會(huì): 二叉鏈