2022年实验三互联网域名查询实验报告 .pdf

《2022年实验三互联网域名查询实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年实验三互联网域名查询实验报告 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、. word 范文实验报告实验课程：数据 结 构实验项目：实验三互联网域名查询专业：计算机科学与技术班级：姓名：学号：指导教师：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - . word 范文目录一、问题定义及需求分析（1）问题描述（2）实验任务（3）需求分析二、概要设计： (1) 抽象数据类型定义 (2)主程序流程 (3) 模块关系三、详细设计(1) 数据类型及存储结构 (2)模块设计四、调试分析 (1)调试分析 (2)算

2、法时空分析 (3)经验体会五、使用说明(1) 程序使用说明六、测试结果(1) 运行测试结果截图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - . word 范文七、附录 (1)源代码一、问题定义及需求分析（1）实验目的互联网域名查询互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如 cn、com等，最底层 （第四层）是叶子结点，如www 等。因此，域名搜索可以看成是树的遍名师资料总结 - - -精品资料欢

3、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - . word 范文历问题。（2）实验任务设计搜索互联网域名的程序。（3）需求分析： 1)采用树的孩子兄弟链表等存储结构。 2)创建树形结构。 3)通过深度优先遍历搜索。4) 通过层次优先遍历搜索。二、概要设计：采用孩子兄弟链表存储结构完成二叉树的创建；主程序流程：创建根节点域名输入域名拆分根据孩子兄弟链表表示的树进行插入调用层次优先遍历输出遍历结果调用深度优先遍历输出遍历结果结束程序模块关系：输入域名创建孩子兄弟

4、树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - . word 范文层次优先遍历输出结果深度优先遍历输出结果结束三、详细设计孩子兄弟链表结构：typedef struct CSNode ElemType data10; struct CSNode *firstchild, *nextsibling; *CSTree; 模块一深度优先遍历算法如下void DFS(CSNode *root) if (!root) return;/

5、递归结束条件printf(%sn, root-data); DFS(root-firstchild);/递归遍历孩子节点DFS(root-nextsibling);/递归遍历兄弟节点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - . word 范文 模块二层次优先遍历算法如下void BFS(CSNode *root) printf(层次优先搜索遍历结果为：n); Queue que; que.Clear(); que.pus

6、h(root);/根节点入队列while (!que.empty() /队列不空的时候执行循环CSNode *xx = que.front(); /取队首元素 que.pop();/出队列printf(%sn, xx-data); if (xx-nextsibling) /出队节点的孩子节点若不空则入队列que.push(xx-nextsibling); if (xx-firstchild) /同样若孩子节点不空则入队列que.push(xx-firstchild); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

7、 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - . word 范文四、调试分析问题解决：在编写层次优先遍历算法的时候遍历结果总是不正确，原因是取完队首元素后没有将出队列，经过改正，在取队首元素后加上出队列函数将队首元素出队；这样便解决了问题；时空分析：经过孩子兄弟链表表示的树创建后便得到一棵二叉树；对于两个遍历函数，深度优先遍历是递归算法，在时间上， 递归算法效率较低， 尤其是运算次数较大的时候；层次优先遍历函数借助到队列，所以在内存占用上较多；而深度优先遍历算法的空间占用上更优于层次优先遍历；经验体会：孩子兄弟链表表示的树与二叉树可以相互转化；它的

8、深度优先遍历递归算法虽较为简单但相比非递归算法而言效率不高。五、使用说明第一步：输入域名第二步：完成创建第三步：输出层次优先遍历结果第四步：输出深度有限遍历结果六、测试截屏名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - . word 范文七、附录#include #include #include #define ElemType char #define QueueSize 50 #define push Push #def

9、ine empty Empty #define pop Pop #define front Front typedef struct CSNode ElemType data10; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - . word 范文struct CSNode *firstchild, *nextsibling; *CSTree;/节点结构void InitTree(CSNode *A) /构造一个空树A = (

10、CSTree)malloc(sizeof(CSNode); A-firstchild = A-nextsibling = NULL; int Search_(CSNode *X, char *a) /查找待插入的节点在树中是否存在CSNode *B; B = X;/B指向根节点while (B-data) if (strcmp(B-data, a) = 0) X = B; /若存在相等的则返回1 return 1; else B = B-nextsibling; /否则 B 指向它的兄弟节点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

11、 - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - . word 范文 return 0; void hanshu1(CSNode *A, ElemType *s) /将节点插入到树中CSNode *B, *X; char *str; int i; X = A; /X指向根节点B = (CSTree)malloc(sizeof(CSNode); B-firstchild = B-nextsibling = NULL; char ZhongZhuan15; /中转数组for (; s != 0;) /zhongzhuan接 受s中xx

12、x. 部 分 或 取 完 翻 转zhongzhuan str = strchr(s, .);/返回字符串s 中第一次出现点的位置if (str) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - . word 范文 i = str - s; ZhongZhuani + 1 = 0; for (; i = 0; i-, s+) ZhongZhuani = s0;/将拆分后的节点传入中转数组中 else /字符串中不含点符号_st

13、rrev(s); i = strlen(s); ZhongZhuani + 1 = 0; for (; i = 0; i-) ZhongZhuani = si;/将字符串存入中转数组里 s = 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - . word 范文if (Search_(X, ZhongZhuan) /若要插入的字符串已存在该层面上X = X-firstchild;/x指向孩子节点continue; if

14、(X-data0 = 0) strcpy(X-data, ZhongZhuan);/将中转数组的信息复制给待插入节点B = (CSTree)malloc(sizeof(CSNode); B-firstchild = B-nextsibling = NULL; else if (X-firstchild) strcpy(B-data, ZhongZhuan); X-nextsibling = B;/将作为的兄弟节点B = (CSTree)malloc(sizeof(CSNode); B-firstchild = B-nextsibling = NULL; X = X-nextsibling; /

15、x指向它的兄弟节点 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - . word 范文else strcpy(B-data, ZhongZhuan); X-firstchild = B; B = (CSTree)malloc(sizeof(CSNode); B-firstchild = B-nextsibling = NULL; X = X-firstchild; struct Queue int Top, Tail; CS

16、Node *a1000; void Clear(); void Push(CSNode *e); void Pop(); CSNode *Front(); bool Empty(); ;/队列封装为结构体void Queue:Clear() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - . word 范文Top = Tail = 0; return; /清空队列void Queue:Push(CSNode *e) aTai

17、l+ = e; return; /入队列void Queue:Pop() Top+; return; /出队列CSNode *Queue:Front() return aTop; /取队首元素bool Queue:Empty() return Top = Tail; /判空名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 17 页 - - - - - - - - - . word 范文void BFS(CSNode *root) printf(层次优先搜索遍历结果为：n)

18、; Queue que; que.Clear(); que.push(root);/根节点入队列while (!que.empty() /队列不空的时候执行循环CSNode *xx = que.front(); /取队首元素 que.pop();/出队列printf(%sn, xx-data); if (xx-nextsibling) /出队节点的孩子节点若不空则入队列que.push(xx-nextsibling); if (xx-firstchild) /同样若孩子节点不空则入队列que.push(xx-firstchild); void DFS(CSNode *root) if (!ro

19、ot) return;/递归结束条件名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - . word 范文printf(%sn, root-data); DFS(root-firstchild);/递归遍历孩子节点DFS(root-nextsibling);/递归遍历兄弟节点 int main() int j; CSNode *A; A = (CSNode*)malloc(sizeof(CSNode);/根节点创建A-first

20、child = A-nextsibling = NULL; A-data0 = 0; char b30; /定义字符数组接收域名char *s; for (j = 0; j3; j+) printf(请输入网址： ); gets(b); s = b;/s指向数组 b _strrev(s); hanshu1(A, s);/字符串 s 存入 A中 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - . word 范文BFS(A);/层次优先遍历printf(深度优先遍历结果为:n); DFS(A);/深度优先遍历 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -