《2023年数据结构邻接矩阵邻接表图实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构邻接矩阵邻接表图实验报告.pdf（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验名称：数据结构实验五实 验 内 容:1 .使用邻接矩阵速立一个图，深度遍历。2.使用邻接表建立一个图，广度遍历。3.建立一个图，存储结构自己拟定，并进行拓扑排序。实 验 代 码：1 .#in c 1 u de stdio.h”#d e f in e I n finit y 10 0#d e fine Max Vert e xN u m 20t ypedef e num DGDN,UDG,UDN Graph Kind;typed e f i nt V RT y pe;ty p e def c h ar V er t e x T y p e;bool Vis i tMa x V e rtexN
2、um;ty p e d e f st r u c t ArcCell(VRType a dj;ArcC e 1 1 ,AdjMatrix Max VertexN um MaxVe r texNum;t y p edef str u ct(Vert e xT y p e v e xsMaxVerte x Num ;AdjMatrix a res；/邻接矩阵in t vex n um,arcn u m;/图的当前顶点数和弧数。G r a p hKind kind;)MGr a ph;int LocateVe x(M Graph G,V e rtex T ype v)f or(i n t i=0;i
3、 G.ve x n um;+i)wif(v=G.v ex s E i)0 r e turn i;)i f(i=Gvexn u m)oprin t f(输入的顶点不合法n”)；r e t urn 0;)V e r t e x Type vl,v2;VRTy p e w;voi d Cre a teUDG(MGraph&G)(o i n t i,j,k;printf(请输入顶点数:n )；s c a n f(d”,&G.v e xnum);叩r i n t f(请输入弧数:n”);scanf(%d ,&G.ar c num);。i=0;owh i le(iGvexn u m)prin t f（请输
4、入第 d 个顶点n，i）;getchar();s canf(n%cn,&Gv e xs i);。+i;。for(i=0;i G.vexnum;+i)for(j=0：j G.v e x n um;+j)Garcs ij.adj=0;0)o f o r(k=0;k G.a rcn u m；+k)“print f(请输入一条边依附的顶点及权值(vl v2 w)n );e g etchar()；osc a nf(%c%c%d ,&vl,&v 2,&w);Q i=LocateVe x(G,v 1);何 =Lo c ate Vex(G,v2);G.a rcsi j.a d j=w;G.arcsj i =G
5、.arcsi j；)6return;)v o id DFST r av e r s e(MGraph&Qi n t i)pri n t f(*%c n,G.vexsi);Vis i ti=t r ue;fo r(int j=0;jGve x num;j+)时 f(Ga r c sij.adj=l&!Vi s i tjl)(DFST r a v e r s e(G,j);00)void D FS(MG r aph&G)(int i;for(i=0;iG.v e xnum;i+)Visili=f a Ise;for(i=0；iG.v exnum；i+)(。i f(!Visiti)0(。DFS Tr
6、ave r s e(G,i)；)v o id main()MGr a ph gra p h；*C r e a teUDG(g r aph);中 r in t f(顶点集合为：)；fbr(i n t i=0;iprintf(n%c,g r aph.v e xs L i);pr i ntf(n 深度遍历结果是:)；eDFS(g ra p h);叩rintf(”n”)；return;)2.#inclu d e std i o.h1#include std l i b.h#def i ne Max Vert e xNum 20typ e d ef in t I n fbType;ty p e d ef
7、 c ha r V e rt e xType;t y p edef V e rte x Type QElemType;bo o 1 v i s i tedMaxVe r t e x Num;t ypede f s t r u c t ArcN o de(int a d j vex;/该弧指向的顶点位置struct A r cNo d e*nextarc；/指向下一条弧的指针InfoTy p e*info;ArcN o d e;ty p edef s truct VNodeaVert e x T ype d a t a;/顶点信息Ar c N o de*f i r s ta r e;/指向第一条
8、依附该顶点的弧的指针VN o de,AdjLi s tM a xVertexNumJ；t y pe d ef s truct!Adj List v ert i ces；“n t vexnum,a renum；/图的当前顶点数和弧数)ALGrap h;t y pedef struc t QN o de(Q E lemTyp e d ata;st r uct QN o de*nex t;QNo d e,*Queueptr;typ e d e f s t rue t(Q u euep t r fro n t;Queu e ptr re a r;LinkQ u eue;void I nitQueue(
9、L ink Q u e ue&Q)(Q.front=Q.rear=(Q u e u e ptr)ma 1 loc(si z eof(QN o de);i f(!Q.f r ont)r etu r n;Q.f r o n tnex tNULL;return;void E n Q ueue(L inkQ u e u e&Q,Q E l e mT y p e e)(oQ u e ue p tr p=N U L L；p=(Q ueue p t r)malloc(sizeof(Q N o d e);i f(!p)r e turn;p-d a t a=e;p-n ext=N U L L；Q.rear n
10、e xt=p;Q.r ea r=p；return;)Q E 1 em T y p e D eQ ueue(L i n kQ u e u e&Q,Q E lemT y p e&e)(Q ueue p t r p;“f(Q.fron t=Q .rea r)return;p=Q.fro n t-n ext；笛=p-data;oQ.f r o n t n e xt=p-ne x t;“f(Q.re a r=p)Q.r ear=Q.front;ofree(p);or e tur n e;)int QueueEmpty(L i n kQue u e Q)i f(Q.f r ont=Q.r e ar)re
11、t urn 1；oelse。r e t u r n 0;)i n t Loca t e(A LG r a p h G,VertexType v)(of o r(i n t k=0;kG.v exnum;+k)(if(v=G v er t ice s k.dat a)r etur n k;)if(k=Gvexnum)P rin t f(输入的顶点不合法n)；6return 0;)v o id Cre a teALG r ap h(ALGrap h&G)(Vertex Type vl,v2;int i,j,k；ArcN o d e*p,*r;pr i ntf（请输入顶点数和弧数（以空格分开）：”）
12、；s c a nf(%d%(!,&G,ve x num,&G.ar c n um);o f or(i=0;i G.v exnum；+i)(ge t char();p r 血f(”请输入第d 个 结 点：”，i);。scanf(H%cn,&G,verti c es Li,da t a)；o G.verticesi.f irstar c=NULL；。for(i=0;iadjv e x=j;。叩 info=N ULL;r-ad j vex=k;o r i n f o=NULL;p-n e xtarc=G.vert i c esk.firs t a rc;G v erticesk.f i r s t
13、ar c=p；or-n e x t a r c=G.ve r ticesj.fi r st a rc;G.v e r t i ce s j.f irst a rc=r；r et u rn;)void B F S T raverse(ALGr a p h G,Q E l e m T y pe x)(A n t i,v;oA rc N o d e *p;oQ E l e m T y pe v 1;f or(v=0；vG.vexnum;+v)visited v =false；L inkQ ueue Q;n i t Que u e(Q);aE nQ ueue(Q,x);A =L o e a te(G,
14、x);visited i =true;for(v=0;v adjvex)0000vi s i t ed padjvex=t r uo E nQ u e u e(Q,G.v ert i c e sp-adjvex.data);000。p=p-n e xtarc；000 j 00)if(!visi t ed v)(g v is i t e d v =t r ue;“oEnQ u e u e(Q,G.v e rti c e s v.d a t a);void main()(och a r f 1 a gl;AL Graph gra p h2;oQEl e mType x;aCreateALGr a
15、p h(g r aph 2);flag 1 =*；wh i le(flag 1=Y I Iflagl=y，)p r i n t f（”请输入遍历的起点：”）;gget c h ar();scanf(u%cn,&x);gprintf(广度遍历结果是:n)；“B F STrav e r s e(graph2,x);sprint f(n n 继续遍历(Y/N):)；getch a r();os c anf(%c&flagl);0)return；)3.#include”st d io.hu#inclu d e st d lib.h#defi n e Sta c k I n i tS i z e 20#
16、d efine Stackin c rement 5#def i ne Ma x V e rtexN u m 20typed e f i n t Inf o Type；typed e f c h ar Vert e xType;type d e f Ver t exType S E 1 emT y pe;typede f s t r uct(oSElem T y p e*base;SE 1 emT y pe*top；in t stacksize;SqStack;ty p e d e f s truct Ar c Nodei n t adj vex；/该弧指向的顶点位置s true t Ar c
17、 Node*n e x t a rc;/指向下一条弧的指针Inf o T ype*info;ArcNo d e;t y pedef s truct V Node(in t indegr e e;W ertexT ype d a ta;顶点信息A rc Node*fi r stare；/指向第一条依附该顶点的弧的指针VNo d e,AdjL i stMaxV e rtexN u m;ty p ed e f s tr u c t(Adj L i s t vertice s；in t v exnum,aren u m；/图的当前顶点数和弧数AL Gr a p h;b o o 1 In i tS t
18、ack(SqSta c k&s)(s.base=(SElemType*)ma 1 lo c(Sta c klnitSize*s i z eo f(SEI e mT y p e);i f(Js.base)retur n false;as.t o p=s.base;os.st a ck s iz e=Stac k Init S ize;r e tur n true；)bo o 1 P op(SqS t ac k&s,int&e)(if(s.top=s.bas e)s r eturn false;e=*-s.to p;oret u rn t r ue;)b ool Pus h(S q Sta c k
19、&s,int e)(oi f(s.to p -s.b a se=s.stacksize)(s.b a se=(SE 1 e mTyp e*)rea 1 1 oc(s.base,(s.stacksize+Sta c kin e rem en。*sizeof(S E lem T y pe);i f(!s.b a se)re t urn fals e;s.top=s.b a se+s.stacksize;8s.s t ac k s i z e+=S t ac k I n creme n t;)*s.t o p+=e;oret u r n true；)b ool StackEmpty(SqS t a
20、ck s)if(s.t op=s,b a s e)8r e tu r n tr u e；else。re t ur n fals e；)int Loca t e(A L Gra p h G,VertexT y pe v)(ofor(i n t k=0;kG.v exnum；+k)(i f(v=G.ve r ti c esk.d ata)。re t urn k;。i f(k=G.v e x n um)。pri n tf(输入的顶点不合法n”)；retur n 0;)vo i d Cre a teALG r ap h(A L Graph&G)/邻接表存储(VertexTy p e v 1,v2;“n
21、t i,j,k;A reNode*p;叩r int f(”请输入顶点数和弧数(以空格分 开)：”)；sea n f(%d%d,&G.ve x n u m,&G a r c num);f or(i=0;iG.ve x num；+i)(。getcha r();-p r i nt f(请输入第 d 个 结 点:”,i)；。s c a n f(c”，&G.v erticesi.d ata)；。G.v e rtic e s i.fir s tare=NULL;oG.v erti c es i.i n degre e=0;)ofor(i=0;i a djvex=j；p-info=NUL L;p-nex t
22、 arc=G.ve r t ices k.f i rsta r c;G.ve r t i ce s k.firstar c=p;re t ur n;)void Fi n d I nDe g re e(A L G r a ph G,int aMaxVerte x N u m)i n t i,k：A r c No d e*p;ofo r(i=0;in e x t a rc)0 0|oak=p-a djvex;。a k =+G,verti c es k.i n d e g ree;0 0 ret u r n；)voi d T o pologicalS o r t(A L G rap h G)/拓扑排
23、序算法(int i,j,coun t;o A r c N o d e*p;S q S tack s;int indeg r ee M a xV ertexN um;6 for(i=0 ；i Ma x V ert e x Nu m；+i)in d e gree i =0 ;F in d i n D egree(G,inde g ree)；I nitS tack(s);f o r (i=0;i n exta r c)00 I。j=p-ad j ve x；i f(!(-i n de g r e ej)Pus h(s,j);00 I o i f(c o u n tGv e xn u m)。p rint
24、f(错误！该有向图有回路！nn);eels e return;)vo i d m a i n()(A L Graph g r a ph3;CreateALGr a p h(g ra p h3);叩rintf(拓扑排序的结果是：n”)；To p o lo g icalSo r t(g raph3)；pr i ntf(H nn)；retu r n;3 D:VC+6.旭天中文精简黑色版(DVC6MyProjectsGraphDebugGraph.exe*1_ 一 一，1请输入顶点数:8请输入弧数：:青输入第。个顶点,输入第1个顶点福输入第2个顶点:青输入第3个顶点;青输入第4个顶点:青输入第5个顶点
25、:青输入第6个顶点箱输入第7个顶点请输入一条边依附的顶点及权值（v i v2 w）请输入一条边依附的顶点及权值（2 w）a c 1睛输入一条边依附的顶点及权值目3D:VC+6.0 创天中文精简景&l)VC6MyProjectsGraphDebugGraph.exe请输入一条边依附的顶点及权值（以b d 1请输入一条边依附的顶点及权值（Ub e 1请输入一条边依附的顶点及权值（皿e h 1请输入一条边依附的顶点及权值（以Id h 1情输入一条边依附的顶点及权值（Mlc f 1请输入一条边依附的顶点及权值（”p g 1请输入一条边依附的顶点及权值（U1f g 1顶点集合为：a b c d e f
26、g h深度遍历结果是：a b d h e c f gPress any key to co n tin u e.W）)W）W）M）)I-，D:VC+6.0s|天中文精简螟色版VC6MyProjectsGraph3DebugGr叩 h3.exe，1215)开开开开开开开开开开尉尉耐尉耐鬲鬲鬲鬲鬲鬲鬲鬲鬲鬲怅据陆标标空空空空空空空空案走癌癌以以以以以以以以以以占我点点占i点点点点占菰超超微顶顶顶顶顶顶顶顶顶顶rrrrr.、-7、r7、-7:7、-7弋弋弋弋弋弋弋弋弋弋HTaH寸Hz(y(/yx(明点点点点点点点点点点nR_方结结结结结结结结结结甚有有有有有有有有有有.ffxf/lZ(Nz(x z(/kGABCDEFGHIJKLn瓜瓜瓜瓜瓜瓜瓜m弧弧弧弧弧E占向向向向曾7EH:卜一曲同向向南响响响响而有有有有有以cHoty结Bke0123 012345678911012345678911114向1.BAy顶第第第第第第第第第第第第第第第第第第第第第第第第第第wtFan