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

实 验 报 告实验课程数据结构

实验项目实验三互联网域名查询

专 业计算机科学与技术班 级

指导教师

目 录

一、 问题定义及需求分析

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 *f irstchild, *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() ; //取队首元素qu e.p op() ;//出队列printf("%s\n", xx->data) ;if (xx->nextsibling) {//出队节点的孩子节点若不空则入队列que.push(xx->nextsibling) ;

}if (xx->firstchild) {//同样若孩子节点不空则入队列que.push(xx->firstchild) ;

}

}

}

四、调试分析

问题解决

在编写层次优先遍历算法的时候遍历结果总是不正确原因是取完队首元素后没有将出队列经过改正在取队首元素后加上出队列函数将队首元素出队这样便解决了问题

时空分析经过孩子兄弟链表表示的树创建后便得到一棵二叉树对于两个遍历函数深度优先遍历是递归算法在时间上递归算法效率较低尤其是运算次数较大的时候层次优先遍历函数借助到队列所以在内存占用上较多而深度优先遍历算法的空间占用上更优于层次优先遍历

经验体会

孩子兄弟链表表示的树与二叉树可以相互转化它的深度优先遍历递归算法虽较为简单但相比非递归算法而言效率不高。

五、使用说明

第一步输入域名

第二步完成创建

可编辑第三步输出层次优先遍历结果

第四步输出深度有限遍历结果

六、测试截屏

七、附录

#include <stdio.h>

#include<string.h>

#include<stdlib.h>

#def ine ElemType char

#define QueueSize 50

#def ine push Push

#def ine empty Empty

#define pop Pop

#def ine front Front typedef struct CSNode{

ElemType data[10] ;struct CSNode *f irstchild, *nextsibling;}*CSTree;//节点结构void InitTree(CSNode *A)

{ //构造一个空树

A = (CSTree)malloc(sizeof(CSNode)) ;

A->f irstchild = A->nextsibling =NULL;

}int Search_(CSNode *X, char *a)

{ //查找待插入的节点在树中是否存在

CSNo de *B;

B = X;//B指向根节点while (B->data)

{if (strcmp(B->data, a) == 0)

{

X = B; //若存在相等的则返回1return 1;

}else

{

B = B->nextsibling; //否则B指向它的兄弟节点

}

}return 0;

}void hanshu1(CSNode *A, ElemType *s)

{//将节点插入到树中

CSNo de *B, *X;char *s tr;int i;

X = A; //X指向根节点

B = (CSTree)malloc(sizeof(CSNode)) ;

B->f irstchild = B->nextsibling =NULL;c har ZhongZhuan[15] ; //中转数组f or (; s != ' \0' ;)

{

//zhongzhuan接受s中xxx.部分或取完翻转zhongzhuan str = strchr(s, ' . ' ) ;//返回字符串s中第一次出现点的位置if (str)

{i = str - s;

ZhongZhuan[i + 1] = '\0' ;f or (; i >= 0; i--, s++)

{

ZhongZhuan[i] = s[0] ;//将拆分后的节点传入中转数组中}

}

可编辑else

{//字符串中不含点符号

_strrev(s) ;i = strlen(s) ;

ZhongZhuan[i + 1] = '\0' ;f or (; i >= 0; i--)

{

ZhongZhuan[i] = s[i] ;//将字符串存入中转数组里

}i f (Search_(X, ZhongZhuan))

{//若要插入的字符串已存在该层面上

X = X->firstchild;//x指向孩子节点cont inue;

}i f (X->data[0] == '0' )

{s trcpy(X->data, ZhongZhuan) ;//将中转数组的信息复制给待插入节点B = (CSTree)malloc(sizeof(CSNode)) ;

B->f irstchild = B->nextsibling =NULL;

}else

{if (X->firstchild)

{strcpy(B->data, ZhongZhuan) ;

X->nextsibling = B;//将作为的兄弟节点

B = (CSTree)malloc(sizeof(CSNode)) ;

B->f irstchild = B->nextsibling =NULL;

X = X->nextsibling; //x指向它的兄弟节点

}else

{strcpy(B->data, ZhongZhuan) ;

X->firstchild = B;

B = (CSTree)malloc(sizeof(CSNode)) ;

B->f irstchild = B->nextsibling =NULL;

X = X->firstchild;

}

}

}

}

可编辑struct Queue {int Top, Tail ;

CSNo de *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[Ta i l++] = 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() ; //取队首元素qu e.p op() ;//出队列printf("%s\n", xx->data) ;if (xx->nextsibling) {//出队节点的孩子节点若不空则入队列que.push(xx->nextsibling) ;

}if (xx->firstchild) {//同样若孩子节点不空则入队列que.push(xx->firstchild) ;

}

}

}void DFS(CSNode *root) {if ( !root) return;//递归结束条件printf("%s\n", root->data) ;

DFS(root->firstchild) ;//递归遍历孩子节点

DFS(root->nextsibling) ;//递归遍历兄弟节点

}int main()

{int j;

CSNode *A;

A = (CSNode*)mal loc(si zeof(CSNode) ) ;//根节点创建A->f irstchild = A->nextsibling =NULL;

A->data[0] = '0' ;char b[30] ; //定义字符数组接收域名c har *s;f or (j = 0; j<3; j++)

{printf("请输入网址 ") ;gets(b) ;s = b;//s指向数组b

_strrev(s) ;h an s hu 1 (A, s) ;//字符串s存入A中

}

BFS(A) ;//层次优先遍历printf("深度优先遍历结果为:\n") ;

DFS(A) ;//深度优先遍历

}

. .