1、.實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課程：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)項(xiàng)目 ：實(shí)驗(yàn)三互聯(lián)網(wǎng)域名查詢專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：姓名：學(xué)號(hào)：指導(dǎo)教師 ：.專業(yè)學(xué)習(xí)資料.目錄一、問題定義及需求分析（ 1）問題描述（ 2）實(shí)驗(yàn)任務(wù)（ 3）需求分析二、概要設(shè)計(jì) ：(1) 抽象數(shù)據(jù)類型定義(2)主程序流程(3) 模塊關(guān)系三、詳細(xì)設(shè)計(jì)(1)數(shù)據(jù)類型及存儲(chǔ)結(jié)構(gòu)(2)模塊設(shè)計(jì)四、調(diào)試分析(1)調(diào)試分析(2)算法時(shí)空分析(3)經(jīng)驗(yàn)體會(huì)五、使用說明(1)程序使用說明六、測(cè)試結(jié)果(1)運(yùn)行測(cè)試結(jié)果截圖.專業(yè)學(xué)習(xí)資料.七、附錄(1)源代碼一、問題定義及需求分析（1）實(shí)驗(yàn)?zāi)康幕ヂ?lián)網(wǎng)域名查詢互聯(lián)網(wǎng)域名系統(tǒng)是一個(gè)典型的樹形層次結(jié)構(gòu)。從根節(jié)點(diǎn)往下的第一層是頂層域

2、，如 cn、 com 等，最底層（第四層）是葉子結(jié)點(diǎn) ，如 www 等。因此，域名搜索可以看成是樹的遍歷問題。.專業(yè)學(xué)習(xí)資料.（2 ）實(shí)驗(yàn)任務(wù)設(shè)計(jì)搜索互聯(lián)網(wǎng)域名的程序。（ 3 ）需求分析 ：1) 采用樹的孩子兄弟鏈表等存儲(chǔ)結(jié)構(gòu)。2) 創(chuàng)建樹形結(jié)構(gòu) 。3) 通過深度優(yōu)先遍歷搜索 。4) 通過層次優(yōu)先遍歷搜索 。二、概要設(shè)計(jì) ：采用孩子兄弟鏈表存儲(chǔ)結(jié)構(gòu)完成二叉樹的創(chuàng)建；主程序流程 ：創(chuàng)建根節(jié)點(diǎn)域名輸入域名拆分根據(jù)孩子兄弟鏈表表示的樹進(jìn)行插入調(diào)用層次優(yōu)先遍歷輸出遍歷結(jié)果調(diào)用深度優(yōu)先遍歷輸出遍歷結(jié)果結(jié)束程序模塊關(guān)系 ：輸入域名創(chuàng)建孩子兄弟樹層次優(yōu)先遍歷輸出結(jié)果.專業(yè)學(xué)習(xí)資料.深度優(yōu)先遍歷輸出結(jié)果結(jié)束三

3、、詳細(xì)設(shè)計(jì)孩子兄弟鏈表結(jié)構(gòu) ：typedef struct CSNodeElemType data10;struct CSNode *firstchild, *nextsibling;*CSTree;模塊一深度優(yōu)先遍歷算法如下void DFS(CSNode *root) if (!root) return;/遞歸結(jié)束條件printf("%sn", root->data);DFS(root->firstchild);/遞歸遍歷孩子節(jié)點(diǎn)DFS(root->nextsibling);/遞歸遍歷兄弟節(jié)點(diǎn)模塊二層次優(yōu)先遍歷.專業(yè)學(xué)習(xí)資料.算法如下void BFS(C

4、SNode *root) printf(" 層次優(yōu)先搜索遍歷結(jié)果為：n");Queue que;que.Clear();que.push(root);/根節(jié)點(diǎn)入隊(duì)列while (!que.empty() /隊(duì)列不空的時(shí)候執(zhí)行循環(huán)CSNode *xx = que.front(); /取隊(duì)首元素que.pop();/出隊(duì)列printf("%sn", xx->data);if (xx->nextsibling) /出隊(duì)節(jié)點(diǎn)的孩子節(jié)點(diǎn)若不空則入隊(duì)列que.push(xx->nextsibling);if (xx->firstchild)

5、/同樣若孩子節(jié)點(diǎn)不空則入隊(duì)列que.push(xx->firstchild);四、調(diào)試分析問題解決 ：在編寫層次優(yōu)先遍歷算法的時(shí)候遍歷結(jié)果總是不正確，原因是取完隊(duì)首元素后沒有將出隊(duì)列 ，經(jīng)過改正 ，在取隊(duì)首元素后加上出隊(duì)列函數(shù)將隊(duì)首元素出隊(duì)；這樣便解.專業(yè)學(xué)習(xí)資料.決了問題 ；時(shí)空分析 ：經(jīng)過孩子兄弟鏈表表示的樹創(chuàng)建后便得到一棵二叉樹；對(duì)于兩個(gè)遍歷函數(shù)，深度優(yōu)先遍歷是遞歸算法，在時(shí)間上 ，遞歸算法效率較低，尤其是運(yùn)算次數(shù)較大的時(shí)候 ；層次優(yōu)先遍歷函數(shù)借助到隊(duì)列，所以在內(nèi)存占用上較多；而深度優(yōu)先遍歷算法的空間占用上更優(yōu)于層次優(yōu)先遍歷；經(jīng)驗(yàn)體會(huì) ：孩子兄弟鏈表表示的樹與二叉樹可以相互轉(zhuǎn)化；它

6、的深度優(yōu)先遍歷遞歸算法雖較為簡(jiǎn)單但相比非遞歸算法而言效率不高。五、使用說明第一步 ：輸入域名第二步 ：完成創(chuàng)建第三步 ：輸出層次優(yōu)先遍歷結(jié)果第四步 ：輸出深度有限遍歷結(jié)果六、測(cè)試截屏.專業(yè)學(xué)習(xí)資料.七、附錄#include <stdio.h>#include<string.h>#include<stdlib.h>#define ElemType char#define QueueSize 50#define push Push#define empty Empty#define pop Pop#define front Fronttypedef struct

7、 CSNodeElemType data10;.專業(yè)學(xué)習(xí)資料.struct CSNode *firstchild, *nextsibling;*CSTree;/ 節(jié)點(diǎn)結(jié)構(gòu)void InitTree(CSNode *A) / 構(gòu)造一個(gè)空樹A = (CSTree)malloc(sizeof(CSNode);A->firstchild = A->nextsibling = NULL;int Search_(CSNode *X, char *a)/ 查找待插入的節(jié)點(diǎn)在樹中是否存在CSNode *B;B = X;/B指向根節(jié)點(diǎn)while (B->data)if (strcmp(B-&g

8、t;data, a) = 0)X = B;/ 若存在相等的則返回1return 1;elseB = B->nextsibling;/ 否則 B 指向它的兄弟節(jié)點(diǎn).專業(yè)學(xué)習(xí)資料.return 0;void hanshu1(CSNode *A, ElemType *s)/ 將節(jié)點(diǎn)插入到樹中CSNode *B, *X;char *str;int i;X = A;/X 指向根節(jié)點(diǎn)B = (CSTree)malloc(sizeof(CSNode);B->firstchild = B->nextsibling = NULL;char ZhongZhuan15;/ 中轉(zhuǎn)數(shù)組for (; s

9、 != '0')/zhongzhuan接受 s 中 xxx.部分或取完翻轉(zhuǎn)zhongzhuanstr = strchr(s, '.');/返回字符串s 中第一次出現(xiàn)點(diǎn)的位置if (str)i = str - s;.專業(yè)學(xué)習(xí)資料.ZhongZhuani + 1 = '0'for (; i >= 0; i-, s+)ZhongZhuani = s0;/將拆分后的節(jié)點(diǎn)傳入中轉(zhuǎn)數(shù)組中else/ 字符串中不含點(diǎn)符號(hào)_strrev(s);i = strlen(s);ZhongZhuani + 1 = '0'for (; i >=

10、0; i-)ZhongZhuani = si;/將字符串存入中轉(zhuǎn)數(shù)組里s = '0'if (Search_(X, ZhongZhuan)/ 若要插入的字符串已存在該層面上X = X->firstchild;/x指向孩子節(jié)點(diǎn)continue;.專業(yè)學(xué)習(xí)資料.if (X->data0 = '0')strcpy(X->data, ZhongZhuan);/將中轉(zhuǎn)數(shù)組的信息復(fù)制給待插入節(jié)點(diǎn)B = (CSTree)malloc(sizeof(CSNode);B->firstchild = B->nextsibling = NULL;elsei

11、f (X->firstchild)strcpy(B->data, ZhongZhuan);X->nextsibling = B;/將作為的兄弟節(jié)點(diǎn)B = (CSTree)malloc(sizeof(CSNode);B->firstchild = B->nextsibling = NULL;X = X->nextsibling;/x 指向它的兄弟節(jié)點(diǎn)elsestrcpy(B->data, ZhongZhuan);X->firstchild = B;B = (CSTree)malloc(sizeof(CSNode);.專業(yè)學(xué)習(xí)資料.B->fir

12、stchild = B->nextsibling = NULL;X = X->firstchild;struct Queue int Top, T ail;CSNode *a1000;void Clear();void Push(CSNode *e);void Pop();CSNode *Front();bool Empty();/ 隊(duì)列封裝為結(jié)構(gòu)體void Queue:Clear() Top = Tail = 0;return;/ 清空隊(duì)列void Queue:Push(CSNode *e) .專業(yè)學(xué)習(xí)資料.aTail+ = e;return;/ 入隊(duì)列void Queue:Po

13、p() Top+;return;/ 出隊(duì)列CSNode *Queue:Front() return aT op;/ 取隊(duì)首元素bool Queue:Empty() return Top = Tail;/ 判空void BFS(CSNode *root) printf(" 層次優(yōu)先搜索遍歷結(jié)果為：n");Queue que;que.Clear();que.push(root);/根節(jié)點(diǎn)入隊(duì)列.專業(yè)學(xué)習(xí)資料.while (!que.empty() /隊(duì)列不空的時(shí)候執(zhí)行循環(huán)CSNode *xx = que.front(); /取隊(duì)首元素que.pop();/出隊(duì)列printf(&

14、quot;%sn", xx->data);if (xx->nextsibling) /出隊(duì)節(jié)點(diǎn)的孩子節(jié)點(diǎn)若不空則入隊(duì)列que.push(xx->nextsibling);if (xx->firstchild) /同樣若孩子節(jié)點(diǎn)不空則入隊(duì)列que.push(xx->firstchild);void DFS(CSNode *root) if (!root) return;/遞歸結(jié)束條件printf("%sn", root->data);DFS(root->firstchild);/遞歸遍歷孩子節(jié)點(diǎn)DFS(root->nextsibling);/遞歸遍歷兄弟節(jié)點(diǎn)int main().專業(yè)學(xué)習(xí)資料.int j;CSNode *A;A = (CSNode*)malloc(sizeof(CSNode);/根節(jié)點(diǎn)創(chuàng)建A->firstchild = A->nextsibling = NULL;A->data0