实 验 报 告 实验课程：数 据 结 构 实验项目：实验三互联网域名查询 专 业：计算机科学与技术 班 级： 姓 名： 学 号： 指导教师： 目 录 一、问题定义及需求分析 （1）问题描述 （2）实验任务 （3）需求分析

二、概要设计： (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系

三、详细设计 (1)数据类型及存储结构 (2)模块设计

四、调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会

五、使用说明 (1)程序使用说明 六、测试结果 (1)运行测试结果截图 七、附录 (1)源代码 一、问题定义及需求分析 （1）实验目的 互联网域名查询 互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如www等。因此，域名搜索可以看成是树的遍历问题。 （2）实验任务 设计搜索互联网域名的程序。 （3）需求分析： 1)采用树的孩子兄弟链表等存储结构。 2)创建树形结构。 3)通过深度优先遍历搜索。 4)通过层次优先遍历搜索。

二、概要设计： 采用孩子兄弟链表存储结构完成二叉树的创建； 主程序流程： 创建根节点 域名输入 域名拆分 根据孩子兄弟链表表示的树进行插入 调用层次优先遍历 输出遍历结果 调用深度优先遍历 输出遍历结果 结束程序 模块关系： 输入域名

创建孩子兄弟树 层次优先遍历输出结果 深度优先遍历输出结果 结束 三、详细设计 孩子兄弟链表结构： typedef struct CSNode{ ElemType data[10]; struct CSNode *firstchild, *nextsibling; }*CSTree; 模块一深度优先遍历 算法如下 void DFS(CSNode *root) { if (!root) return;//递归结束条件 printf("%s\n", 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("%s\n", xx->data); if (xx->nextsibling) {//出队节点的孩子节点若不空则入队列 que.push(xx->nextsibling); } if (xx->firstchild) {//同样若孩子节点不空则入队列 que.push(xx->firstchild); } } }

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

五、使用说明 第一步：输入域名 第二步：完成创建 第三步：输出层次优先遍历结果 第四步：输出深度有限遍历结果

六、测试截屏

七、附录 #include #include #include #define ElemType char #define QueueSize 50 #define push Push #define empty Empty #define pop Pop #define front Front typedef struct CSNode{ ElemType data[10]; 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; //若存在相等的则返回1 return 1; } else { B = 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 ZhongZhuan[15]; //中转数组

for (; s != '\0';) { //zhongzhuan接受s中xxx.部分或取完翻转zhongzhuan str = strchr(s, '.');//返回字符串s中第一次出现点的位置 if (str) { i = str - s; ZhongZhuan[i + 1] = '\0'; for (; i >= 0; i--, s++) { ZhongZhuan[i] = s[0];//将拆分后的节点传入中转数组中 } } else {//字符串中不含点符号 _strrev(s); i = strlen(s); ZhongZhuan[i + 1] = '\0'; for (; i >= 0; i--) { ZhongZhuan[i] = s[i];//将字符串存入中转数组里 } s = '\0'; }

if (Search_(X, ZhongZhuan)) {//若要插入的字符串已存在该层面上 X = X->firstchild;//x指向孩子节点 continue; } if (X->data[0] == '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; //x指向它的兄弟节点 } 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; CSNode *a[1000]; void Clear(); void Push(CSNode *e); void Pop(); CSNode *Front(); bool Empty(); };//队列封装为结构体

void Queue::Clear() { Top = Tail = 0; return; }//清空队列

void Queue::Push(CSNode *e) { a[Tail++] = e; return; }//入队列

void Queue::Pop() { Top++; return; }//出队列

CSNode *Queue::Front() { return a[Top]; }//取队首元素

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("%s\n", xx->data); if (xx->nextsibling) {//出队节点的孩子节点若不空则入队列 que.push(xx->nextsibling);