实验九-图的邻接表存储表示和实现

《实验九-图的邻接表存储表示和实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、C语言版图的邻接表存储表示和实现#include//图的邻接表存储表示#defineMAX_NAME3//顶点字符串的最大长度+1#defineMAX_VERTEX_NUM20typedefintInfoType;//存放网的权值typedefcharVertexType[MAX_NAME];//字符串类型typedefenum{DG,DN,AG,AN}GraphKind;//{有向图,有向网,无向图,无向网}typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指

2、向下一条弧的指针InfoType*info;//网的权值指针）}ArcNode;//表结点typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//第一个表结点的地址,指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;typedefintQElemType;//队列类型//单链队列－－队列

3、的链式存储结构typedefstructQNode{QElemTypedata;//数据域structQNode*next;//指针域}QNode,*QueuePtr;typedefstruct{QueuePtrfront,//队头指针，指针域指向队头元素rear;//队尾指针，指向队尾元素}LinkQueue;//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。intLocateVex(ALGraphG,VertexTypeu){inti;for(i=0;i

4、returni;return-1;}//采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。intCreateGraph(ALGraph*G){inti,j,k;intw;//权值VertexTypeva,vb;ArcNode*p;printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3):");scanf("%d",&(*G).kind);printf("请输入图的顶点数和边数:（空格）");scanf("%d%d",&(*G).vexnum,&(*G).arcnum);printf("请输入%d个顶点的值(<%d个字符

5、):",(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;++i)//构造顶点向量{scanf("%s",(*G).vertices[i].data);(*G).vertices[i].firstarc=NULL;}if((*G).kind==1

6、

7、(*G).kind==3)//网printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):");else//图printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):");for(k=0;k<(*G).arcnum;++k)//构造表结点

8、链表{if((*G).kind==1

9、

10、(*G).kind==3)//网scanf("%d%s%s",&w,va,vb);else//图scanf("%s%s",va,vb);i=LocateVex(*G,va);//弧尾j=LocateVex(*G,vb);//弧头p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;if((*G).kind==1

11、

12、(*G).kind==3)//网{p->info=(int*)malloc(sizeof(int));*(p->info)=w;}elsep->info=NULL;//图p

13、->nextarc=(*G).vertices[i].firstarc;//插在表头(*G).vertices[i].firstarc=p;if((*G).kind>=2)//无向图或网,产生第二个表结点{p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=i;if((*G).kind==3)//无向网{p->info=(int*)malloc(sizeof(int));*(p->info)=w;}elsep->info=NULL;//无向图p->nextarc=(*G).vertices[j].firstarc;//插在表

14、头(*G)