2023年数据结构实验互联网域名查询实验报告.pdf

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

1、实 验 报 告实验课 程:数 据 结 构 _ _ _ _ _ _ _ _ _ _实验项目:实验三互联网域名查询专 业:计算机科学与技术班 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _姓 名2 _学_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _指导教师:目 录一、问题定义及需求分析(1 )问题描述(2)实验任务(3)需求分析二、概要设计：(1)抽象数据类型定义(2 )主程序流程(3)模块关系三、具体设计(1 )数据类型及存储结构(2)模块设计四、调试分析(1 )调试分析(2)算法时空分析(3)经验体会五、使用说明(1)程序

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

3、节点 域名输入 域名拆分.根据孩子兄弟链表表达的树进-行 插 入-调用层次优先遍历 输出遍历结果 调用深度优先遍历输出遍历结果结束程序模块关系:输入域名创建孩子兄弟树层次:遍历输出结果深牛优先遍历输出结果结束三、具体设计孩 子 兄 弟 链 表 结 构：typ e d e f struct CSNodeE 1 e mT y pe data 10；o st r u c t CSNod e*fi r s tchi 1 d,*nextsi b I i ng;*CS T ree;模块一深度优先遍历算法如下void DF S(CSNode*root)i f(1 ro o t)r e turn；递归结束条件

4、prin t f roo t d a ta);DFS(roo t-f i rstchild);/递归遍历孩子节点o DFS(roo t n e x t s i b ling);递归遍历兄弟节点)模块二层次优先遍历算法如下vo i d B FS (CSNode*roo t)p r in t f(层次优先搜索遍历结果为：n );o Qu e u e que;。q ue.Clear();que.push(root)；根节点入队列6wh i 1 e(!que.e mpty()/队列不空的时候执行循环Q CSNode 火xx 二 q u e.f r ont();取队首元素que.p o p()；/出队列

5、。p ri n tf(%snz xx-data);J i f(xx-nextsibli ng)/出队节点的孩子节点若不空则入队列qu e.pu s h(xx-next s ibling);6)6 if(x x-first c hi 1 d)/同样若孩子节点不空则入队列。q ue.p u s h(xxf i r s t chi 1 d);o 0。)四、调试分析问题解决：在编写层次优先遍历算法的时候遍历结果总是不对的,因素是取完队首元素后没有将出队列，通过改正，在取队首元素后加上出队列函数将队首元素出队;这样便解决了问题；时空分析：通过孩子兄弟链表表达的树创建后便得到一棵二叉树;对于两个遍历函数，

6、深度优先遍历是递归算法，在时间上，递归算法效率较低，特别是运算次数较大的时候;层次优先遍历函数借助到队列，所以在内存占用上较多;而深度优先遍历算法的空间占用上更优于层次优先遍历；经验体会：孩子兄弟链表表达的树与二叉树可以互相转化；它的深度优先遍历递归算法虽较为简朴但相比非递归算法而言效率不高。五、使用说明第一步:输入域名第二步:完毕创建第三步:输出层次优先遍历结果第四步:输出深度有限遍历结果六、测试截屏 ：(：。k81。:1*据 结 构 实 验 一 互 联 网 域 名 葺 询$160-X靖输入网址： 人请输入网址 请输入网址 www.bb.ff.coin层次优先搜索遍历结果为：.comcn,t

7、ao.edu.ff.baidu.neu.bbW W WW W WW W W深度优先遍历结果为：.com.tao.baiduW W W.ff.bbW W W.cn.edu.neuW W WProcess returned 0(0 x0)execution time：40.883 sPress any key to continue.七、附录#in c lu d e#i n c 1 u d e#i nclu d e#d ef i ne ElemTy p e c har#defi n e QueueSi z e 5 0#d e fin e push P u s h#d e fin e empt y

8、Em p ty#defin e p op Pop#d e fi n e front F r onttypedef str u ct CS N ode。E 1 emType data 1 0 ;os t ruct CSN o de*f i r s t c h ild,*n e x t sib 1 in g;*CSTree；节点结构v oi d I nitTree(C S No d e*A)构造一个空树0 A=(CST r ee)mall o c(s i z e of(CSNode)；A-fi r s t c h ild=A nex t sib 1 i ng=N U LL;i nt Searc h

9、 _(CSNode*X,char*a)查找待插入的节点在树中是否存在CSNod e*B;B=X;/B指向根节点while(B-data)7 i f(st r c mp(B-dat a,a)=0)x=B;若存在相等的则返回1。retu r n 1;6 o e l s eO O I。B=B n e x t sibling;/否则B指向它的兄弟节点6)r e tur n 0;v o id hans h u 1 (CS Nod e*A,E 1 em Type*s)将节点插入到树中CSNo d e*B,*X;c h a r *s tr;inti；oX=A;/X指向根节点oB=(CST r e e)ma

10、1 loc(sizeof(CSN o d e);o B-firstch i 1 d=B-nex t sibling=NULL；c ha r Zhong Z hu a n 15;中转数组for(;s!=*0*；)/zhong z h u a n接受s中x xx.部分或取完翻转z h ongzhu a n3 s tr=st r chr(s,?);返回字符串s中第一次出现点的位置3 if(str)0 3 i=s tr-s；。Zhong Z hu a n i+1=0;3 f o r(;i=0；i-,s+)(oroZhongZh u an i=s 0;将拆分后的节点传入中转数组中0 0 j0)else。

11、/字符串中不含点符号。s t rr e v(s)；。4=s t r I e n(s);6ZhongZh u an i+1=0;o。f or(；i=0；i-)0(o Z h o n g Zhuan i=s i;/将字符串存入中转数组里0 0。s=0；6)3 if(S e arch_(X,Z h o n gZ h ua n)。若要插入的字符串已存在该层面上;X-f i rs t c h i 1 d;/x 指向孩子节点o 0co ntinue;0 0 if(Xdat a 00)6 s t r cpy(X-dataz Z hongZ hu a n);/将中转数组的信息复制给待插入节点B=(CSTr e

12、 e)mallo c(si z eof(CSNod e);o o B-f i r s t c h i 1 d=B-nex t s i bling=NULL;。el s e(if(X-firstchild)0 0 0 1。strep y(B-d a t a,ZhongZh u an);。X next s ibling=B；将B作为X的兄弟节点3 B=(CSTree)malloc(s i z e o f(CSNo de)；o B-f i rstchi 1 d=B-n exts i bl i n g =NULL;。ooX=X n e xts i blin g;/x指向它的兄弟节点。)os el s

13、eO 0 o o str c p y(B-d a ta,ZhongZh u a n)；。o X fi r stch i 1 d=B；ooo。B=(CSTre e)malloc(s izeo f (CS No d e);B-firstc h ild=B-ne x t s ibling=N U L L;。X=X fi r s t c h i 1 d；0 0 0 10 0 )s t r u ct Queue、int Top,Tail;o CSNo de*a 1 000;v oid C lear()；voi d Push(C S Node*e);o void Pop()；C S Node*Fro n

14、t();bool Em p ty();/队列封装为结构体v oi d Qu e u e：:CI e ar()o Top=Tai 1 =0;re turn;/清空队列void Qu e u e：:Pus h(CSNode*e)aTail+=e；。return;入队列v o id Qu e ue:Pop()T o p+;。return;/出队列CSNode*Q u eue:F ront()o r e tur n a Top;/取队首元素b ool Queue：:Em p ty()r e t u rn T o p =T a il;)判空vo id BFS(CSNod e*ro o t)p rintf

15、(”层次优先搜索遍历结果为：n”)；Q u e ue qu e；q u e.Clear();。q u e.p ush(roo t)；/根节点入队列w h ile(!que.empty()/队列不空的时候执行循环。CS Nod e*x x=q u e.fro n t()；/取队首元素que.pop();/出队列。printf(%sn,xx d a t a);6 if(xx-nextsibling)/出队节点的孩子节点若不空则入队列。q ue.push(xx-nexts i bling);。if(xx-f i rstch i Id)/同样若孩子节点不空则入队列。qu e.p u s h(xx f

16、irst c hil d)；)vo i d DFS(C S N 0 d e*roo t)6 if(!r o ot)return；递归结束条件。pr i ntf(H%sn u,r oot-da t a);6 D F S(r oot-fir s tchild);/递归遍历孩子节点DFS(ro o t-ne x t s ib 1 in g);/递归遍历兄弟节点)int main()(in t j;CSNod e*A;A=(CSNod e*)mallo c(sizeof(CSNod e)；/根节点创建A-fir s tchild=A-nextsibli n g=NULL;A-d a t a0=0;c h ar b30;/定义字符数组接受域名。char*s;for(j=0;j3;j+)。叩r i ntf(请输入网址：);。3 g e t s(b);s=比 5指向数组bo_st r rev(s)；。hans h u 1(A,s)；/字符串 s 存入 A 中。BFS(A);层次优先遍历print f(1,深度优先遍历结果为：n);。DFS(A);深度优先遍历)