数据结构实验-互联网域名查询实验报告.doc

精品文档实 验 报 告 实验课程：数 据 结 构 实验项目：实验三互联网域名查询 专 业：计算机科学与技术 班 级： 姓 名： 学 号： 指导教师： 目 录1、 问题定义及需求分析 （1）问题描述 （2）实验任务 （3）需求分析二、概要设计： (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系3、 详细设计 (1)数据类型及存储结构 (2)模块设计4、 调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会5、 使用说明 (1)程序使用说明6、 测试结果 (1)运行测试结果截图7、 附录 (1)源代码1、 问题定义及需求分析 （1）实验目的 互联网域名查询 互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如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(CSNode *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) /同样若孩子节点不空则入队列que.push(xx-firstchild);4、 调试分析 问题解决：在编写层次优先遍历算法的时候遍历结果总是不正确，原因是取完队首元素后没有将出队列，经过改正，在取队首元素后加上出队列函数将队首元素出队；这样便解决了问题；时空分析：经过孩子兄弟链表表示的树创建后便得到一棵二叉树；对于两个遍历函数，深度优先遍历是递归算法，在时间上，递归算法效率较低，尤其是运算次数较大的时候；层次优先遍历函数借助到队列，所以在内存占用上较多；而深度优先遍历算法的空间占用上更优于层次优先遍历；经验体会：孩子兄弟链表表示的树与二叉树可以相互转化；它的深度优先遍历递归算法虽较为简单但相比非递归算法而言效率不高。5、 使用说明第一步：输入域名第二步：完成创建第三步：输出层次优先遍历结果第四步：输出深度有限遍历结果6、 测试截屏7、 附录#include #include#include#define ElemType char#define QueueSize 50#define push Push#define empty Empty#define pop Pop#define front Fronttypedef struct 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-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 != 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 = 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;elseif (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-firstchild = B-nextsibling = NULL;X = X-firstchild;struct Queue int Top, Tail;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:Pop() Top+;return;/出队列CSNode *Queue:Front() return aTop;/取队首元素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(%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 = 0;char b30; /定义字符数组接