数据结构实验_互联网域名查询实验报告

1、.实验报告实验课程：数据结构实验项目 ：实验三互联网域名查询专业：计算机科学与技术班级：姓名：学号：指导教师 ：.专业学习资料.目录一、问题定义及需求分析（ 1）问题描述（ 2）实验任务（ 3）需求分析二、概要设计 ：(1) 抽象数据类型定义(2)主程序流程(3) 模块关系三、详细设计(1)数据类型及存储结构(2)模块设计四、调试分析(1)调试分析(2)算法时空分析(3)经验体会五、使用说明(1)程序使用说明六、测试结果(1)运行测试结果截图.专业学习资料.七、附录(1)源代码一、问题定义及需求分析（1）实验目的互联网域名查询互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域

2、，如 cn、 com 等，最底层（第四层）是叶子结点 ，如 www 等。因此，域名搜索可以看成是树的遍历问题。.专业学习资料.（2 ）实验任务设计搜索互联网域名的程序。（ 3 ）需求分析 ：1) 采用树的孩子兄弟链表等存储结构。2) 创建树形结构 。3) 通过深度优先遍历搜索 。4) 通过层次优先遍历搜索 。二、概要设计 ：采用孩子兄弟链表存储结构完成二叉树的创建；主程序流程 ：创建根节点域名输入域名拆分根据孩子兄弟链表表示的树进行插入调用层次优先遍历输出遍历结果调用深度优先遍历输出遍历结果结束程序模块关系 ：输入域名创建孩子兄弟树层次优先遍历输出结果.专业学习资料.深度优先遍历输出结果结束三

3、、详细设计孩子兄弟链表结构 ：typedef struct CSNodeElemType data10;struct CSNode *firstchild, *nextsibling;*CSTree;模块一深度优先遍历算法如下void DFS(CSNode *root) if (!root) return;/递归结束条件printf("%sn", root->data);DFS(root->firstchild);/递归遍历孩子节点DFS(root->nextsibling);/递归遍历兄弟节点模块二层次优先遍历.专业学习资料.算法如下void BFS(C

4、SNode *root) printf(" 层次优先搜索遍历结果为：n");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)

5、/同样若孩子节点不空则入队列que.push(xx->firstchild);四、调试分析问题解决 ：在编写层次优先遍历算法的时候遍历结果总是不正确，原因是取完队首元素后没有将出队列 ，经过改正 ，在取队首元素后加上出队列函数将队首元素出队；这样便解.专业学习资料.决了问题 ；时空分析 ：经过孩子兄弟链表表示的树创建后便得到一棵二叉树；对于两个遍历函数，深度优先遍历是递归算法，在时间上 ，递归算法效率较低，尤其是运算次数较大的时候 ；层次优先遍历函数借助到队列，所以在内存占用上较多；而深度优先遍历算法的空间占用上更优于层次优先遍历；经验体会 ：孩子兄弟链表表示的树与二叉树可以相互转化；它

6、的深度优先遍历递归算法虽较为简单但相比非递归算法而言效率不高。五、使用说明第一步 ：输入域名第二步 ：完成创建第三步 ：输出层次优先遍历结果第四步 ：输出深度有限遍历结果六、测试截屏.专业学习资料.七、附录#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;.专业学习资料.struct CSNode *firstchild, *nextsibling;*CSTree;/ 节点结构void InitTree(CSNode *A) / 构造一个空树A = (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-&g

8、t;data, a) = 0)X = B;/ 若存在相等的则返回1return 1;elseB = B->nextsibling;/ 否则 B 指向它的兄弟节点.专业学习资料.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

9、 != '0')/zhongzhuan接受 s 中 xxx.部分或取完翻转zhongzhuanstr = strchr(s, '.');/返回字符串s 中第一次出现点的位置if (str)i = str - s;.专业学习资料.ZhongZhuani + 1 = '0'for (; i >= 0; i-, s+)ZhongZhuani = s0;/将拆分后的节点传入中转数组中else/ 字符串中不含点符号_strrev(s);i = strlen(s);ZhongZhuani + 1 = '0'for (; i >=

10、0; i-)ZhongZhuani = si;/将字符串存入中转数组里s = '0'if (Search_(X, ZhongZhuan)/ 若要插入的字符串已存在该层面上X = X->firstchild;/x指向孩子节点continue;.专业学习资料.if (X->data0 = '0')strcpy(X->data, ZhongZhuan);/将中转数组的信息复制给待插入节点B = (CSTree)malloc(sizeof(CSNode);B->firstchild = B->nextsibling = NULL;elsei

11、f (X->firstchild)strcpy(B->data, ZhongZhuan);X->nextsibling = B;/将作为的兄弟节点B = (CSTree)malloc(sizeof(CSNode);B->firstchild = B->nextsibling = NULL;X = X->nextsibling;/x 指向它的兄弟节点elsestrcpy(B->data, ZhongZhuan);X->firstchild = B;B = (CSTree)malloc(sizeof(CSNode);.专业学习资料.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();/ 队列封装为结构体void Queue:Clear() Top = Tail = 0;return;/ 清空队列void Queue:Push(CSNode *e) .专业学习资料.aTail+ = e;return;/ 入队列void Queue:Po

13、p() Top+;return;/ 出队列CSNode *Queue:Front() return aT op;/ 取队首元素bool Queue:Empty() return Top = Tail;/ 判空void BFS(CSNode *root) printf(" 层次优先搜索遍历结果为：n");Queue que;que.Clear();que.push(root);/根节点入队列.专业学习资料.while (!que.empty() /队列不空的时候执行循环CSNode *xx = que.front(); /取队首元素que.pop();/出队列printf(&

14、quot;%sn", xx->data);if (xx->nextsibling) /出队节点的孩子节点若不空则入队列que.push(xx->nextsibling);if (xx->firstchild) /同样若孩子节点不空则入队列que.push(xx->firstchild);void DFS(CSNode *root) if (!root) return;/递归结束条件printf("%sn", root->data);DFS(root->firstchild);/递归遍历孩子节点DFS(root->nextsibling);/递归遍历兄弟节点int main().专业学习资料.int j;CSNode *A;A = (CSNode*)malloc(sizeof(CSNode);/根节点创建A->firstchild = A->nextsibling = NULL;A->data0