数据结构c语言版 图的邻接表存储表示和实现

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

1、数据结构C语言版图的邻接表存储表示和实现.txt如果青春的时光在闲散中度过，那么回忆岁月将是一场凄凉的悲剧。杂草多的地方庄稼少，空话多的地方智慧少。即使路上没有花朵，我仍可以欣赏荒芜。/*数据结构C语言版图的邻接表存储表示和实现P163编译环境：Dev-C++4.9.9.2日期：2011年2月15日*/#include//图的邻接表存储表示#defineMAX_NAME3//顶点字符串的最大长度+1#defineMAX_VERTEX_NUM20typedefintInfoType;//存放网的权值typedefcharVe

2、rtexType[MAX_NAME];//字符串类型typedefenum{DG,DN,AG,AN}GraphKind;//{有向图,有向网,无向图,无向网}typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//网的权值指针）}ArcNode;//表结点typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//第一个表结点的地址,指向第一条依附该顶点的

3、弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;typedefintQElemType;//队列类型//单链队列－－队列的链式存储结构typedefstructQNode{QElemTypedata;//数据域structQNode*next;//指针域}QNode,*QueuePtr;typedefstruct{QueuePtrfront,/

4、/队头指针，指针域指向队头元素rear;//队尾指针，指向队尾元素}LinkQueue;//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。intLocateVex(ALGraphG,VertexTypeu){inti;for(i=0;i

5、texTypeva,vb;ArcNode*p;printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3):");scanf("%d",&(*G).kind);printf("请输入图的顶点数和边数:（空格）");scanf("%d%d",&(*G).vexnum,&(*G).arcnum);printf("请输入%d个顶点的值(<%d个字符):",(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;++i)//构造顶点向量{scanf("%s",(*G).vertices[i

6、].data);(*G).vertices[i].firstarc=NULL;}if((*G).kind==1

7、

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

9、

10、(*G).kind==3)//网scanf("%d%s%s",&w,va,vb);else//图scanf("%s

11、%s",va,vb);i=LocateVex(*G,va);//弧尾j=LocateVex(*G,vb);//弧头p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;if((*G).kind==1

12、

13、(*G).kind==3)//网{p->info=(int*)malloc(sizeof(int));*(p->info)=w;}elsep->info=NULL;//图p->nextarc=(*G).vertices[i].firstarc;//插在表头(*G).vertices[i].firsta

14、rc=p;if((*G).kind>=2)//无向图或网,产生第二个表结点{p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=i;if(