实验4图的遍历及应用.docVIP

实验4 图的遍历及应用 实验目的 1) 掌握图的邻接矩阵存储； 2) 利用邻接矩阵存储图； 3) 掌握图的邻接表存储； 4) 利用邻接表存储图并实现图的遍历； 实验环境 1) 硬件：每个学生需配备计算机一台，操作系统：Windows2000/XP。 2) 软件：visual c++6.0。 实验学时 3学时 实验内容 已知图1，分别用邻接矩阵，邻接表表示两种表示法创建g1,g2. 实验代码： (1 )邻接矩阵： /* Note:Your choice is C IDE */ #include stdio.h #include stdlib.h int jds,i,j,v=0; char cc; typedef struct{ char g[20],cc[20][20]; }ST,*st; void jjj(st tt){ for(i=1;i=jds;i++) { printf(与编号%d的邻接点编号是：,i); for(j=1;j=jds;j++) { if(tt-cc[i][j]==1) printf(%d ,j);} printf(\n);} } void main() { ST yy; printf(请输入结点数：\n); scanf(%d,jds); cc=getchar();/*吃掉回车字符*/ printf(请输入邻接矩阵的所有值：\n); for(i=1;i=jds;i++){ for(j=1;j=jds;j++) { scanf(%c,yy.cc[i][j]);}} for(i=1;i=jds;i++){ for(j=1;j=jds;j++) { printf(%c,yy.cc[i][j]);}} printf(\n请按编号（1~..）输入对应的结点的值：\n); for(j=1;j=jds;j++) { scanf(%c,yy.g[j]);} for(i=1;i=jds;i++){ for(j=1;j=jds;j++) { if(yy.cc[i][j]==1) {++v;} }} printf(图的边数是：%d\n,v/2); printf(图的邻接关系图如下：\n); jjj(yy); } 结果： 邻接表： /* Note:Your choice is C IDE */ #include stdio.h #include stdlib.h typedef struct snode{ int no; char node; struct snode *next; }sn,*zn; typedef struct ssize{ int head; struct ssize *size; int tail; }ss,*zs; int i,j,a,a1,a2; char cd,ck; zn createnode(){ zn pp1,pp2,pp; printf(请输入总结点数：); scanf(%d,a); cd=getchar(); printf(请输入各结点的信息(字符)：\n); pp=(sn *)malloc(sizeof(sn)); pp1=pp; for(i=1;i=a;i++) { pp-no=i; printf(结点%d：,i); pp-node=getchar(); pp2=(sn *)malloc(sizeof(sn)); if(i==a) { pp-next=NULL;} else { pp-next=pp2; pp=pp2;} cd=getchar(); } return (pp1); } void outputnode(zn p){ zn p1; printf(现在输出所有结点信息：\n); p1=p; while(p1!=NULL) {printf(结点%d:,p1-no); printf( %c,p1-node); printf(\n); p1=p1-next;} } zs createsize(zn p){ zs h1,h2,h3; j=1; h1=(ss*)malloc(sizeof(ss));