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

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

1、实验报告实验课程:数据结构实验项目:实验三互联网域名查询专业:计算机科学与技术班经姓 枚学 指导教师:。s t r cpy(X-data, Z hongZ hu a n);/将中转数组的信息复制给待插入节B = (CSTr e e)mallo c (si z eoffCSNod e );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 o o |3strep y (B- d a t a, ZhongZh u an);。 X-next sibling = B; 将B作为X的兄弟节点。B

2、= (CSTree) mallocf s i z e o f (CSNo de);。B-f i rstchi 1 d = B- n exts i bl i ng = NULL;s X= X ne x ts i blin g; /x指向它的兄弟节点。 )el s e0 o 。 str c p y (B- d a taz ZhongZh u a n );。 oXfi r stch i 1 d = B； B = (CSTre e )malloc( s izeo f (C S No d e);o。B-firstc h ild = B-ne x t s ibling = NULL;。X = X fi r

3、stchi 1 d；0 o o jsos t r u ct Queue 3 int Top, Tail;-CSNode*a 1 000;v oid C lear()；voi d Push(C S Node *e); void Pop()；C S Node * Fro nt ();bool Em p ty();/队列封装为结构体v oi d Qu e u e :CI e ar() 0 Top =Tai 1 = 0;are turn;/清空队列void Qu e u e ： :Push (CSNode *e)a a(Tail+ = e；3 return; 入队列v o id Qu e ue:Pop

4、() 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 Top = T a il;) 判空void BFSfCSNod e *ro o t) printf (层次优先搜索遍历结果为：n”)；Q u e ue qu e ；q u e . Clear ();3 q u e. p ushfroo t ) ； / /根节点入队列w hile(!que. empty() )/队列不空的时候执行循环。CS Nod e * x x = q u e.f

5、ro nt()；/取队首元素que.pop(); / / 出队列， printf(%sn, xx d a t a );。if (xx-nextsibling) /出队节点的孩子节点若不空则入队列。q ue.push(xx-nexts i bling);if (xx-f i rstch i Id) /同样若孩子节点不空则入队列3 oque. p u s h(xx f irst c hil d )；o)vo i d DFS(CS Node * roo t ) 8 if (koot)retum； 递归结束条件。pr i ntf( %sn , r oot-da t a);。D F S( r oot-f

6、ir s tchild);/ / 递归遍历孩子节点DFS(ro o t-ne x t s ib 1 in g ) ;/ / 递归遍历兄弟节点int main()(nt j ;CSNod e *A;A = (C SNod e *) mallo c (sizeof(CSNod e )； / /根节点创建A-fir s tchild = A-nextsibli n g = NULL;A-da t a0 = O;c h ar b30; /定义字符数组接受域名。char *s;for (j = 0; j 域名拆分 根据孩子兄弟链表表达的树进 行插入 调用层次优先遍历输出遍历结果调用深度优先遍历输出遍历结

7、果结束程序模块关系：输I:域名创建孩子兄弟树层次优I先遍历输出结果深厚优先遍历输出结果结束三、具体设计孩子兄弟链表结构：typ e d e f struct CSNodeE 1 e mT y pe data 10；st r u c t CSNod e *fi r s tchi 1 d, * nextsi b I i ng;*CSTree;模块一深度优先遍历算法如下void DF S (CSNode *root) iff! root) r e turn； 递归结束条件prin t f (sn，roo t -d a ta);DFS (roo t -f i rstchild); /递归遍历孩子节点o

8、 D F S(roo t n e x t s i b ling);递归遍历兄弟节点模块二层次优先遍历算法如下vo i d B FS (CSNode * roo t )叩in t f (层次优先搜索遍历结果为:n);。Qu e u e que;3 q ue.Clear ();que.push(root); 根节点入队列 wh i 1 e (!que. e mpty()/队列不空的时候执行循环。CSNode *xx = q u e.f r ont(); 取队首元素que. p o p()； /出队列。p ri n tf(%sn, xx-data);。i f (xx-nextsibli ng) /出

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

10、次优先遍历函数借助到队列，所以在内存占用上较多;而深度优先遍历算法的空间占 用上更优于层次优先遍历；经验体会：孩子兄弟链表表达的树与二叉树可以互相转化：它的深度优先遍历递归算法虽较为 简朴但相比非递归算法而言效率不高。五、使用说明第一步:输入域名第二步:完毕创建第三步:输出层次优先遍历结果第四步:输出深度有限遍历结果六、测试截屏 F:CodeBlocksX数据结构实装一互联网域名查询test.exe- X请输入网址： www. baidu. tao. com人清输入网址：www. neu. edu. cn 请输入网址：www. bb. ff. com 层次优先搜索遍历结果为： ,com ,cn

11、 ,tao ,edu .ff , baidu ,neu .bb ：-V WWW WWW 深度优先遍历结果为： .com .tao .baidu WWW .ff .bbWWW .cn .edu .neu WWWProcess returned 0 (0x0) execution time ： 40. 883 s Press 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 hardefi n e QueueSi z e 5 0# d e fin e push Pushit

12、 d e fin e empt y Em p ty# defin e p op Pop#d e fi n e front F r onttypedef str u ct CSNodes E 1 emType data 10; struct CSN o de * first child, * n e x t sib 1 in g ; *CSTree； 节点结构v oi d I nitTree(C S N o d e * A) 构造一个空树A = (CST r eejmall o c (s i z e offCSNode)；A-fi r s t c h ild = A nex t sib 1 i

13、ng = NULL;)i nt Searc h _(CS N ode *X, char *a)杳找待插入的节点在树中是否存在CSNod e *B;B = X;/B指向根节点while (B-data)i f (st r c mp ( B-dat a , a ) = 0)，X= B; 若存在相等的则返回1 。retu r n 1;。 else0 o 。 B = B n e x t sibling; /否则B指向它的兄弟节点。)r e tur n 0;)v o id hans h u 1 (C S Nod e *A, E 1 em T ype *s)将节点插入到树中CSNo de*B, *X;ch

14、ar * s tr;inti;oX = A; /X指向根节点o B = (CST r e e) ma I loc(sizeof (CSN o de);a B-firstch i 1 d = B-nex t sibling = NULL ；c ha r Zhong Z hu a n 15;中转数组ofor (; s !=0；)(/zhong z h u a n接受s中x xx.部分或取完翻转z h ongzhu a n。st r = st r chr(s,返回字符串s中第一次出现点的位置。if (str)。 Zhong Z hu a n i + 1 = 0;s f o r (; i = 0； s

15、+)(oo00ZhongZ h uan i = s 0 ;将拆分后的节点传入中转数组中00 。else。/ /字符串中不含点符号s t rr e v(s)：。i = st r I e n(s); ZhongZh u an i +1= 0;。f or (: i = 0； i -) oooZh o n g Zhuan i = s i ;/ /将字符串存入中转数组里。s = 0; 。if (S e arch_( X,Zh o n gZ h ua n )。若要插入的字符串已存在该层面上 X = X-f i rs t c h i 1 d ; / /x 指向孩子节点。 a c o ntinue;0 o if (Xdat a 00)