數(shù)據(jù)結構實驗互聯(lián)網(wǎng)域名查詢實驗報告記錄

1、數(shù)據(jù)結構實驗互聯(lián)網(wǎng)域名查詢 實驗報告記錄作者:日期:實驗報告實驗課程：實驗項目：實驗三互聯(lián)網(wǎng)域名查詢專 業(yè)：班 級：姓 名:學 號:指導教師:目錄一、問題定義及需求分析(1) 問題描述(2) 實驗任務(3) 需求分析二、概要設計：(1) 抽象數(shù)據(jù)類型定義(2) 主程序流程(3) 模塊關系三、詳細設計(1) 數(shù)據(jù)類型及存儲結構(2) 模塊設計四、調(diào)試分析(1) 調(diào)試分析(2) 算法時空分析(3) 經(jīng)驗體會五、使用說明(1)程序使用說明六、測試結果(1)運行測試結果截圖七、附錄(1)源代碼一、問題定義及需求分析（1）實驗目的互聯(lián)網(wǎng)域名查詢互聯(lián)網(wǎng)域名系統(tǒng)是一個典型的樹形層次結構。從根節(jié)點往下的第一層

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

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

4、();que.push(root);/根節(jié)點入隊列while (!que.empty() /隊列不空的時候執(zhí)行循環(huán)CSNode *xx = que.front(); / 取隊首元素que.pop();/ 出隊列 printf(%sn, xx-data);if (xx-nextsibling) /出隊節(jié)點的孩子節(jié)點若不空則入隊列 que.push(xx-n extsibli ng);if (xx-firstchild) /同樣若孩子節(jié)點不空則入隊列 que.push(xx-firstchild);四、調(diào)試分析問題解決：在編寫層次優(yōu)先遍歷算法的時候遍歷結果總是不正確，原因是取完隊首元素后沒有將出隊

5、列，經(jīng)過改正，在取隊首元素后加上出隊列函數(shù)將隊首元素出隊；這樣便解決了 問題；時空分析：經(jīng)過孩子兄弟鏈表表示的樹創(chuàng)建后便得到一棵二叉樹；對于兩個遍歷函 數(shù)，深度優(yōu)先遍歷是遞歸算法，在時間上，遞歸算法效率較低，尤其是運算次數(shù)較大的 時候；層次優(yōu)先遍歷函數(shù)借助到隊列，所以在內(nèi)存占用上較多；而深度優(yōu)先遍歷算法的 空間占用上更優(yōu)于層次優(yōu)先遍歷；經(jīng)驗體會：孩子兄弟鏈表表示的樹與二叉樹可以相互轉化；它的深度優(yōu)先遍歷遞歸算法雖較為簡單但相比非遞歸算法而言效率不高。五、使用說明第一步：輸入域名 第二步：完成創(chuàng)建第三步：輸出層次優(yōu)先遍歷結果第四步：輸出深度有限遍歷結果六、測試截屏七、附錄#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é)點結構 void In itTree(CSNode *A) /構造一個空樹A = (CSTree)malloc(sizeof(CSNode

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

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

9、串中不含點符號_strrev(s);i = strle n(s);Zho ngZhua ni + 1 = 0：for (; i = 0; i-)ZhongZhuani = si;將字符串存入中轉數(shù)組里s = 0;if (Search_(X, ZhongZhuan)/若要插入的字符串已存在該層面上X = X-firstchild;/x 指向孩子節(jié)點con ti nue;if (X-data0 = 0)strcpy(X-data, Zhon gZhua n);將中轉數(shù)組的信息復制給待插入節(jié)點 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é)點B = (CSTree)malloc(sizeof(CSNode);B-firstchild = B- nextsibli ng = NULL;X = X-nextsibling; /x指向它的兄弟節(jié)點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();/隊列封裝為結構體void Queue:Clear() Top = Tail = 0; return;/清空隊列void Queue:Push(CSNode *e) aTail+ = e;return;/入隊列 void Queue:Pop() Top+; return;/出隊列CS

12、Node *Queue:Front() return aTop;/取隊首元素bool Queue:Empty() return Top = Tail;/判空 void BFS(CSNode *root) printf(層次優(yōu)先搜索遍歷結果為：n);Queue que;que.Clear();que.push(root);/根節(jié)點入隊列while (!que.empty() /隊列不空的時候執(zhí)行循環(huán)CSNode *xx = que.front(); / 取隊首元素que.pop();/ 出隊列printf(%sn, xx-data);if (xx-nextsibling) /出隊節(jié)點的孩子節(jié)點若

13、不空則入隊列que.push(xx-n extsibli ng);if (xx-firstchild) /同樣若孩子節(jié)點不空則入隊列 que.push(xx-firstchild);void DFS(CSNode *root) if (!root) return;/遞歸結束條件printf(%sn, root-data);DFS(root-firstchild);/遞歸遍歷孩子節(jié)點 DFS(root- nextsibli ng);/ 遞歸遍歷兄弟節(jié)點int mai n()int j;CSNode *A;A = (CSNode*)malloc(sizeof(CSNode);/根節(jié)點創(chuàng)建 A-firstchild