數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)互聯(lián)網(wǎng)域名查詢實(shí)驗(yàn)報(bào)告記錄

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)互聯(lián)網(wǎng)域名查詢 實(shí)驗(yàn)報(bào)告記錄作者:日期:實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課程：實(shí)驗(yàn)項(xiàng)目：實(shí)驗(yàn)三互聯(lián)網(wǎng)域名查詢專 業(yè)：班 級：姓 名:學(xué) 號:指導(dǎo)教師:目錄一、問題定義及需求分析(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)程序使用說明六、測試結(jié)果(1)運(yùn)行測試結(jié)果截圖七、附錄(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等。因此，域名 搜索可以看成是樹的遍歷問題。（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ōu)先遍歷輸出結(jié)果結(jié)束三、詳細(xì)設(shè)計(jì)孩子兄弟鏈表結(jié)構(gòu)：typedef stru

3、ct CSNodeElemType data1O;struct CSNode *firstchild, * nextsibli ng;*CSTree;模塊一深度優(yōu)先遍歷算法如下void DFS(CSNode *root) if (!root) return;/遞歸結(jié)束條件printf(%sn, root-data);DFS(root-firstchild);遞歸遍歷孩子節(jié)點(diǎn)DFS(root- nextsibli ng);/ 遞歸遍歷兄弟節(jié)點(diǎn) 模塊二層次優(yōu)先遍歷算法如下void BFS(CSNode *root) printf(層次優(yōu)先搜索遍歷結(jié)果為：n);Queue que;que.Clear

4、();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-n extsibli ng);if (xx-firstchild) /同樣若孩子節(jié)點(diǎn)不空則入隊(duì)列 que.push(xx-firstchild);四、調(diào)試分析問題解決：在編寫層次優(yōu)先遍歷算法的時(shí)候遍歷結(jié)果總是不正確，原因是取完隊(duì)首元素后沒有將出隊(duì)

5、列，經(jīng)過改正，在取隊(duì)首元素后加上出隊(duì)列函數(shù)將隊(duì)首元素出隊(duì)；這樣便解決了 問題；時(shí)空分析：經(jīng)過孩子兄弟鏈表表示的樹創(chuàng)建后便得到一棵二叉樹；對于兩個(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)化；它的深度優(yōu)先遍歷遞歸算法雖較為簡單但相比非遞歸算法而言效率不高。五、使用說明第一步：輸入域名 第二步：完成創(chuàng)建第三步：輸出層次優(yōu)先遍歷結(jié)果第四步：輸出深度有限遍歷結(jié)果六、測試截屏七、附錄#in elude #i

6、n cludevstri ng.h#in clude#defi ne ElemType char#defi ne QueueSize 50#defi ne push Push#defi ne empty Empty#defi ne pop Pop#defi ne front Fronttypedef struct CSNodeElemType data10;struct CSNode *firstchild, * nextsibli ng;*CSTree;節(jié)點(diǎn)結(jié)構(gòu) void In itTree(CSNode *A) /構(gòu)造一個(gè)空樹A = (CSTree)malloc(sizeof(CSNode

7、);A-firstchild = A- nextsibli ng = NULL;int Search_(CSNode *X, char *a)/查找待插入的節(jié)點(diǎn)在樹中是否存在CSNode *B;B = X;/B指向根節(jié)點(diǎn)while (B-data)if (strcmp(B-data, a) = 0)X = B; /若存在相等的則返回1return 1;elseB = B-nextsibling; /否則B指向它的兄弟節(jié)點(diǎn)return 0;void ha nshu1(CSNode *A, ElemType *s)/將節(jié)點(diǎn)插入到樹中CSNode *B, *X;char *str;int i;X =

8、代/X指向根節(jié)點(diǎn)B = (CSTree)malloc(sizeof(CSNode);B-firstchild = B- nextsibli ng = NULL;char ZhongZhuan 15;/ 中轉(zhuǎn)數(shù)組for (; s != 0;)/zhongzhuan 接受 s中 xxx.部分或取完翻轉(zhuǎn) zhongzhuan str = strchr(s, .);/返回字符串s中第一次出現(xiàn)點(diǎn)的位置 if (str)i = str - s;Zho ngZhua ni + 1 = 0;for (; i = 0; i-, s+)ZhongZhuani = s0;/將拆分后的節(jié)點(diǎn)傳入中轉(zhuǎn)數(shù)組中 else字符

9、串中不含點(diǎn)符號_strrev(s);i = strle n(s);Zho ngZhua ni + 1 = 0：for (; i = 0; i-)ZhongZhuani = si;將字符串存入中轉(zhuǎn)數(shù)組里s = 0;if (Search_(X, ZhongZhuan)/若要插入的字符串已存在該層面上X = X-firstchild;/x 指向孩子節(jié)點(diǎn)con ti nue;if (X-data0 = 0)strcpy(X-data, Zhon gZhua n);將中轉(zhuǎn)數(shù)組的信息復(fù)制給待插入節(jié)點(diǎn) B = (CSTree)malloc(sizeof(CSNode);B-firstchild = B- n

10、extsibli ng = NULL;elseif (X-firstchild)strcpy(B-data, Zhon gZhua n);X- nextsibl ing = B;/將E作為X的兄弟節(jié)點(diǎn)B = (CSTree)malloc(sizeof(CSNode);B-firstchild = B- nextsibli ng = NULL;X = X-nextsibling; /x指向它的兄弟節(jié)點(diǎn)elsestrcpy(B-data, Zhon gZhua n);X-firstchild = B;B = (CSTree)malloc(sizeof(CSNode);B-firstchild =

11、B- nextsibli ng = NULL;X = X-firstchild;struct Queue int Top, Tail;CSNode *a1000;void Clear();void Push(CSNode *e); void Pop();CSNode *Fro nt(); bool Empty();/隊(duì)列封裝為結(jié)構(gòu)體void Queue:Clear() Top = Tail = 0; return;/清空隊(duì)列void Queue:Push(CSNode *e) aTail+ = e;return;/入隊(duì)列 void Queue:Pop() Top+; return;/出隊(duì)列CS

12、Node *Queue:Front() return aTop;/取隊(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ì)列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)若

13、不空則入隊(duì)列que.push(xx-n extsibli ng);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- nextsibli ng);/ 遞歸遍歷兄弟節(jié)點(diǎn)int mai n()int j;CSNode *A;A = (CSNode*)malloc(sizeof(CSNode);/根節(jié)點(diǎn)創(chuàng)建 A-firstchild