2023年数据结构实验五实验报告.pdf

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

1、少运城学优数据结构实验报告实验五图子系统实验题目:图的遍历问题_ _ _ _ _ _ _ _ _ _ _ _ _ _ _专业班级：网络工程 10 02班组 长：王星（）_ _ _ _ _ _ _ _ _ _ _ _ _ _ _组 员：郭坤铭（）张磊（）2023年5月 1 8日赎验报告实 验 类 型 综合 实验室软件实验室二一一、实验题目图的遍历问题二、实验目的和规定1、掌握图的存储思想及其存储实现2、掌握图的深度、广度优先遍历算法思想及其程序实现3、掌握图的常见应用算法的思想及其程序实现三、需求分析本演示程序用c+6.0 编写，完毕用户用键盘输入以下结点数据:太原、成都、北京、上海、天津、大连

2、、河北。（1）建立一个有向图或无向图（自定）的邻接表并输出该邻接表。（2）在图的邻接表的基础上计算各顶点的度，并输出。（3）以有向图的邻接表为基础实现输出它的拓扑排序序列。（4）采用邻接表存储实现无向图的深度优先遍历。（5）采用邻接表存储实现无向图的广度优先遍历。（6）采用邻接矩阵存储实现无向图的最小生成树的P R I M 算法。最后，在主函数中设计一个简朴的菜单，分别调试上述算法。四、概要设计为了实现上述程序功能，需要定义如下内容基本数据类型定义如下：t y p e d e f s t r u c t n o d e /边表结点。i n t a d j ;o s t r u c t n o

3、d e *n e x t;n o d e ；t y p e d e f s t r u c t v n o d e c h a r n a m e 2 0;n o d e *f n e x t;v n o d e,A L i s t 2 0 ;t y p e d e f s t r u c t A Li s t Li s t;i n t v,e ;*G r a p h;G r a p h C r e a t D G ()G r a p h C r e a t A G O /边表结点数据域/顶点表结点/邻接表/顶点树和边数/建立无向邻接表有向邻接图v o i d P r i n t (G r a

4、 p h G)输出图的邻接表v o i d C r e a t e A N (A G r a p h *G 1)/构造邻接矩阵结构的图Gv o i d D u (G r a p h G)输出各顶点的度数v o i d D FST r a v e l (G r a p h G)深度优先遍历v o i d B F S T r a v e l (G r a p h G)/广度优先遍历五、具体设计#i n c l u d e f t i n c l u d e#i n c 1 u d e t y p e d e f s t r u c t n o d e 边表结点i n t a d j;边表结点数据域

5、 s t r u c t n o d e *n e x t;I n o d e；t y p e d e f s t r u c t v n o d e /顶点表结点c h a r n a m e 2 0;n o d e *f n e x t ;v n o d e,A Li s t 2 0;t y p e d e f s t r u c t A L i s t Li s t；/邻接表i n t v ,e ；/顶点树和边数*G r a p h ;/建立无向邻接表G r a p h C r e a t D G ()G r a p h G；i n t i,j,k;n o d e *s；G=m a l

6、l o c (2 0*s i z e o f (v n o d e)；p r i n t f C 请输入图的顶点数和边数(空格隔开)：);s c a n f (%d%d ,&G -v,&G e)；读入顶点数和边数f o r (i=0 ;i v;i+)P r i n t f (”请输入图中第%d元素：，i +1 );8 s c a n f (%s ”,G-L i s t i .n a m e);/读入顶点信息o G-L i s t i .f ne x t=N U LL；/边表置为空表)of o r(k=0;k e;k +)P r i ntf (请请输入第%d条边的两顶点序号(空格隔开)：，k +

7、1);。s canf(%d%d,&i,&j )；读入边(V i,Vj)的顶点对序号；s =(no d e *)m al l oc(s i ze o f (node)；生成边表结点8 S a dj=j ;s-ne x t=G-L i s t i .f n e xt;G-L i s t i .f n e xt=s;将新结点*s插入顶点V i的边表头部 s=(node *)m al l oc(s i z e o f (n o de);s-ad j=i；/邻接点序号为io s -n e x t=G-L i s t j .f ne xt;6G-L i s t j .f ne x t=s;/将新结点*s插

8、入顶点V j的边表头部)or e t u r n G;)/有向邻接图G r a p h C r e a tA G ()G ra p h G；i nt i,j ,k;n o de *q;oG=m al l oc(20*s i z e of (v no d e);叩ri ntf(请输入图的顶点数和边数【空格隔开】：)；s canf r%d%d，,&G-v,&G-e)；of or(i=0;i v;i +)叩r i n t f (”请输入图中第(1元素：“，i +1)；MS c an f (%s”,&G-List i .nam e);/读入顶点信息G L i s t i .f ne x t=N U L

9、 L;f or(k=0；k e;k +)。P ri ntf (请请输入第%d边的两顶点序号【空格隔开】：，k+1);g s can f (%d%d”,&i,&j);。q=(n o d e *)m a l l o c(s i z e of (no de);/生成新边表结点sq-adj=j；邻接点序号为jq-ne xt=G L i s t i .f ne xt;。G L i s t i .f ne xt=q;r e turn G;/输出图的邻接表voi d P ri nt(G r ap h G)i n t i ；n o de *p；P r i n t f (t=令 B 接表=n )；f or(i=

10、0;i v;i+4-)。p=G-L i s t i .f ne xt;。p ri ntf (?，%d|%3 s”,i,G-L i s t i .nam e);awh i l e(p)叩 ri ntf (-%3 s”,G L i s t p adj .n a m e)；g p ri n tf p a d j);p=p-ne xt;0)op ri ntf (n )；)ty p e de f s t r uc t 2ch a r v e x 20；L i s ts 20;t y p e de f s truct L i s t s 1 ;，i nt e dg e 2 0 2 0 ;/令 B 接矩阵i

11、n t vl,e 1;/顶点数和弧数 A G r ap h ;typ e d e f s tru c t i n t d a ta;/*某顶点与已构造好的部分生成树的顶点之间权值最小的顶点*/i n t l owcos t;/*某顶点与已构造好的部分生成树的顶点之间的最小权值*/C l os E d g e 20；/*用普里姆算法求最小生成树时的辅助数组*/voi d C re at e A N(A G r a p h *G 1)/*构造邻接矩阵结构的图G */i nt i,j,k,w;叩 ri ntf(请输入图的顶点数和边数(空格隔开)：)；s canf C%d%d&G l-v l,&G l

12、-e l);/读入顶点数和边数f or(i =1;i vl;i+)%ri ntf (请输入图d号元素：，i);s canf (%s，z,&G 1 1 i .ve x);读入顶点信息寸of or(i=l;i vl；i+)/初始化邻接矩阵f or(j=l;j vl;j +)G l-e dg e i j =9 ;。f or(k=l;k e l;k +)p ri ntf （请输入两顶点及边的权值（空格隔开）:;。s canf (%d%d%d,&i,&j ,&w)；G 1-e d g e i j =w;。G l e d g e j i =w;)voi d P r i n tA N(A G r ap h

13、*G 1)i nt i,j;op ri n t f (t=令口接矩阵=n );f or(i=1;i v 1;i +)f or(j =1；j vl;j+)p ri nt f (%3 d”,G 1 e dg e i j );8 P r i nt f (n );)输出各顶点的度数voi d D u(G r a p h G)i n t i,j；n ode *p；p r i n t f (nn);f or(1=0;i v;i +)g p=G-L i s t i .f n e x t；(p ri n t f (顶点2s 的度为：，G-L i s t i .n a m e);。j =0；awh i l e(

14、p)j+;。P=P -n ex t；s p ri nt f (%d n,j)；)/栈typ e de f s truct s t ack oi nt x;s t r uct s t ack *ne xt;s t ack;i nt p u s h (s t a c k *s,i n t i)st a c k*p;%=(s t a c k *)m a 1 l oc(s i ze of (s t a c k)；p-x=i ;叩 一 ne x t=s n e x t;s-n e xt=p;re t u r n 1;i n t p o p (s t a c k*s,i n t j )。s ta c k

15、*p =s n e x t;/保存栈顶指针j=p-x;s ne xt=p-ne xt;将栈顶元素摘下f re e (p);释放栈顶空间re t u r n j;)拓扑排序voi d T op o(G r ap h G,s tack *s)i nt i ,k,co u nt;i nt j=0;i n t i nde g re e 20 =0;nod e *p;f o r(i =0;i v；i+)p=G-L i s t i .f ne xt；;wh i 1 e(p!=N UL L)i nd e g r e e p ad j +;p=p-ne xt;)f or(i=0;i v；i+)i f (i n

16、de g r e e i =0)p us h (s,i);8 col m t=0;w h i l e (s-ne xt!=NUL L)i=p op (s,j)；p ri ntf (，z%2 s ”,G-L i s t i .nam e);+c ou n t;f or(p =G-L i s t i .f ne x t;p!=NUL L ；p=p -n ext)g k=p adj;i f (!(i n de g re e k )p us h (s,k);)i f (co unt v)p ri ntf (有回路！);)voi d DFS (G r ap h G,i nt i,i n t f l a

17、g口)o n ode *p;p ri n t f (%2 s ”,G-L i s t i .n a m e)；f l ag i =l；p=G-L i s t i .f n e x t;owh i l e(p)i f (!f l ag p-a d j)。DFS (G,p-a dj,f l a g);p=p-ne xt;)/深度优先遍历vo i d DFS T ra v e l (G r a p h G)i nt i ;i nt f 1 a g 2 0 ;/标志数组of o r(i=0;i v；i+)8 f 1 a g i 0;of or(i=0;i v;i +)oi f(!f l ag i )o

18、DFS (G,i ,f l a g);)/建立队列typ e de f s truct oi n t*e l e m;。i nt f ront,re a r;*Q ue ue；队列初始化voi d I ni tQ ue ue(Q u e ue Q)Q-e l e m=(i nt*)m al l oc(20*s i ze of (i n t);i f (!Q e 1 e m)e x i t(0);Q f r o n t=Q-re a r=0;)/入队v o i d Ent e r(Q ue ue Q,i nt e)i f (Q-re ar+l)%20!=Q-f r o nt)oQ-e l e m

19、 Q-re a r =e;oe l s e p r i nt f (队列满!n );Q-re ar=(Q r e ar+l)%20;)/出队vo i d L e a v e (Q u e ue Q,i nt e)oi f(Q re ar!=Q-f ro nt)e=Q-e l e m Q-f ro n t；oe l s ep r i n t f (队列空!n )；Q f r o nt=(Q f r o n t+l)%20;)广度优先遍历vo i d B FS T r ave l (G r a p h G)Q u e u e Q ;anode *p；i n t i ,j=0;i nt f l ag

20、 20;标志数组Q=m a 1 1 o c(s i z e o f (20);In i tQ ue u e (Q);f or(i=0;i v;i +)f 1 ag i =0;of or(i=0；iG-v;i +)i f (f l a g i =0)g f l ag i =1;p r i nt f (%2s”,G-L i s t i .n a m e)；Ente r(Q,i );。3V h i l e (Q -f ront!=Q-r e ar)。，L e ave(Q,j);/队头元素出队并置为j。o p=G-L i s t j .f n e xt；ow h i 1 e (p !=NUL L)i

21、f (f 1 a g p-ad j =0)。p r i ntf (%2 s ”,G L i s t p-a d j .n am e);8 of l a g p-a dj =1；o o o o o E n t e r(Q,p-adj);p=p-ne xt;。)6)i nt m i ni m um (C l os E d g e cl,i nt vnum)i nt i;i nt w,p;w=10 0 0;e f or(i =1;i =v n u m ;i+)i f (cl i .1 o wc o s t!=0&c 1 i .l owcos t w)o w=cl i .l owcos t;p=i;O

22、Oj-or e t u rn p;)voi d P r i m (A G ra p h *G 1,i nt u)C l o s Edg e cl os e dg e;i nt i,j ,k；of or(j =l；j vl；j+)/*辅助数组初始化*/i f (j !=u)必c 1 o s e dg e j .d a ta=u;c l o s e dg e j .l ow c o s t=G l-e d g e u j ；8 cl os e d g e u .1 o w c os t=0;/*初始,U=u */f or(i=l;i vl;i+)k =m i ni m u m (c 1 o s e

23、 d g e,G 1 v 1)；/*求出生成树的下一个顶点*/op r i ntf (%d-%d n”,cl o s e dg e k .data,k)；/*输出生成树的边火/cl os e dg e k .1 owcos t =0;/*第 k 顶点并入 U 集*/of o r(j=l;j vl;j +)/*新顶点并入U 后，修改辅助数组*/i f (G 1-e d g e k j e dg e k j ；0 0 )菜单列表voi d m e nu()op r i ntf (t*图的遍历问题*火*n);p r i n t f （t t-1.建立无向邻接图-n）;op ri n tf -2.建立

24、有向邻接图 一-n）；p ri nt f（t t-3.建立无向邻接矩阵-n ）;op r i ntf C t t-4.输出各顶点的度-n ）;p ri n t f （，z t t-5.拓扑排序-n ）;p ri ntf （t t-6.深度优先遍历-n）;o p ri n t f -7 .广度优先遍历-n ）；p r i ntf（t t-8.p ri m算法生成最小生成树-n ）；p ri ntf （z，t t-9 一退出 一-n ）;叩 ri ntf （t*n）;）/主函数v o id m ai n()G ra p h G;oA G r ap h G 1;i n t c h oi ce,u;s

25、 ta c k *s=(s tac k *)m al l oc(s i z e o f (s tac k );s-n e xt=NUL L;w h i l e (1)e m e nu();p ri ntf(”请输入选择：)；s e an f (,z%d ,&ch o i c e)；s wi tch (ch oi c e)cas e l:G=C re atDG ();P r i nt(G)；p ri ntf (n n)；b re ak;c a s e 2:G=C re atA G();P r i n t(G);p r i ntf (n n);b r e ak ;o c a s e 3:C re

26、a t e A N(&G 1)；P ri nt A N(&G 1);p ri ntf n n);bre ak;cas e 4:Du(G);p ri ntf (n n );bre a k ;c as e 5:p ri n t f (拓扑排序：);T op o(G ,s)；p r i ntf(n n);bre ak;cas e 6 ：p ri ntf (深度优先遍历：)；D F S T ra v e l (G);p ri n tf (n n );b re a k;c a s e 7:p ri ntf (广度优先遍历：”)；B F S T rave l (G);p ri ntf (n n )；br

27、e ak;ocas e 8：。p r i n tf (请输入起点序号:;s canf&u);。aop r i n t f (P ri m 算法：n );。P ri m(&G l,u);p ri ntf(n);百br e ak;c a s e 9:e xi t(0)；d e f au 1 t:p ri n t f (输入错误，请重新输入：n n );)六、使用说明1、程序名为实验5.e xe,运营坏境为D OS.程序执行后显示如图所示：*-M-*-M-的向向向先法图无有无I立立立出簧度im出F建建建暮深广pr退*-*123456789*一一一一一一一一一题阵问图度一力至燧球的邻点4MJ叔成性，、

28、最历*情输入选择:2、建立无向邻接图题阵、可B E矩度舞邻邻点历招H的向向向先法图无有无舁f立立立出瞿度im出f建建建翦深广河曲知123456789331 22001 开开开鬲鬲鬲t-JV-J S空空空-微元元元的的的一一221超勤勒救边边边匚匚匚1 2 3选图图图第第入入入入入A-A-入-jybt3、输出各顶点的度I5S1E矩度最历黑邻邻点遍里的向向向先法图无有无4|舁立立立出畲度im出共建建建篝深广pr退二-二工2 3 4 5 6 7 8 9请输入选择：4顶点b说度为;2顶点打的度为：2顶点sh的度为：24、进行深度优先遍历邙阵向图 度f历报一向向向先法一无有无4 3 舁立立立出差度in出

29、建建建寓深广琏退1 2 3 4 5 6 7 8 9遭输入港接:6深度优先遍历：bj sb ty5、进行广度优先遍历问图甯度最历第甯邻邻点si的向向向先法图无有无:立立立出震度im出工建建建鬻深广相退二-.-1 2 3 4 5 6 7 8 9道输入选提：7广度优先遍历：bjsh ty6、建立有向邻接图|51经型矩度最历接接妾的历悬骂邻邻点H的向向向先法图无有无:2:立立立出普度in出力建建建籍深广W退二-1 2 3 4 5 6 7 8 931 1 1空空空m号号号1bjtysh点点点表y-顶顶顶接tfl:2 第第.边边边1 23n rrr g.ng.hg-h=匚匚口佯佯J=选图图图图入入入J-y

30、-hAJ入入入入b tse l l l l瞿星d e青45r44Vm!青青青青青青青青7、拓扑排序题阵I5B1国矩度历接接奏的邻点dj权成性最历摞的向向向先法图无有无1舁T7 H立出普度in出建建建寓深广M退一-一1 2 3 4 5 6 7 8 9hty S-5-J择:b选序入排青团8、建立无向邻接矩阵题阵小问图思度最I WOS历盘需邻邻点B1的向向向先法图无有无昇T立立立出簧度iln出建建建鬻深广掳4-*1 2 3 4 5 6 7 8 9*（至咯隔开）（至喀隔开）（空崔隔开）（空格隔开）数值胞”又又又知“J y/毛超妾口b t S打勺边边边支及及及一一:3顶OT点点_ _蕃顶顶顶选图酎图西两

31、两两入入入入入入入入A趣趣趣趣趣趣趣刖生宿主Q E主月主月主星P E主P E主收9 9 99 5 99、prim算法生成最小生成树题阵问图僵度_力接接强的f-,在2一历热的向向向K先法图无有无导T立立立出差度in出建建建寓深广.退*-*1 2 3 4 5 6 7 8 9*-一一一-一*1号8于岑选2 3 算醯in主目主R十l、l P 1工七、实验总结本次实验对我们来说有不小的难度,花费了很长的时间，在大家的商议讨论和共同努力下，最终完毕了实验的内容，组长在此过程中很认真负责，使成员一步一步前进。同时,这使我们在图这方面的知识更加全面，通过实验进一步增强了我们的实际运用知识的能力，对我们很有帮助。