上机实验：
1. 参考下列邻接表的程序，思考对于无权无向图、无权有向图、带权无向图、带权有向图四种情况，邻接表程序应该如何处理？
程序6-2
#include<malloc.h>
#include<stdio.h>
#define MAX_VEX 50
typedef structarcnode /*定义表结点*/
{
int vextex;
struct arcnode*next;
}ARCNODE;
typedef structvexnode /*定义头结点*/
{
int data;
ARCNODE *firstarc;
}VEXNODE;
VEXNODEadjlist[MAX_VEX]; /*定义表头向量adjlist*/
intcreatadjlist() /*建立邻接表*/
{
ARCNODE *ptr;
int arcnum,vexnum,k,v1,v2;
printf("input vexnum，arcnum:\n");
scanf("%d,%d",&vexnum,&arcnum); /*输入图的顶点数和边数（弧数）*/
for(k=0;k<vexnum;k++)
adjlist[k].firstarc=NULL; /*为邻接表的adjlist数组各元素的链域赋初值*/
for(k=0;k<arcnum;k++) /*为adjlist数组的各元素分别建立各自的链表*/
{
printf("v1,v2=");
scanf("%d,%d",&v1,&v2);
ptr=(ARCNODE*)malloc(sizeof(ARCNODE));
/*给结点V1 的相邻结点V2 分配内存空间*/
ptr->vextex=v2;
ptr->next=adjlist[v1].firstarc;
adjlist[v1].firstarc=ptr; /*将相邻结点V2 插入表头结点V1 之后*/
ptr=(ARCNODE*)malloc(sizeof(ARCNODE));
/*对于有向图此后的四行语句要删除*/
ptr->vextex=v1; /*给结点V2 的相邻结点V1 分配内存空间*/
ptr->next=adjlist[v2].firstarc;
adjlist[v2].firstarc=ptr; /*将相邻结点V1 插入表头结点V2 之后*/
}
return(vexnum);
}
main()
{
int i,n;
ARCNODE *p;
n=creatadjlist(); /*建立邻接表并返回顶点的个数*/
printf("Output AdjList of graph:\n");
for(i=0;i<n;i++) /*输出邻接表中各个链表的信息*/
{
printf("%d==>",i);
p=adjlist[i].firstarc;
while(p!=NULL)
{
printf("--->%d",p->vextex);
p=p->next;
}
printf("\n");
}
2. 读懂边集数组程序。
/*程序6-3：*/
#include<malloc.h>
#include<stdio.h>
#define MAX_ARC 50
typedef structedges
{
int bv,ev,w;
}EDGES;
EDGESedgeset[MAX_ARC];
intcreatedgeset() /*建立带权图的边集数组*/
{
int arcnum,i;
printf("input arcnum:\n"); /*提示输入边数*/
scanf("%d",&arcnum); /*输入边数*/
for(i=0;i<arcnum;i++)
{
printf("bv,ev,w=");
scanf("%d,%d,%d",&edgeset[i].bv,&edgeset[i].ev,&edgeset[i].w);
/*输入每条边的起、止顶点及边的权值*/
}
return(arcnum);
}
main()
{
int i,arcnum;
arcnum=createdgeset(); /*建立带权图的边集数组并返回其边数*/
printf("bv ev w\n");
for(i=0;i<arcnum;i++) /*输出边集数组中每一条边的信息*/
printf("%d %d%d\n",edgeset[i].bv,edgeset[i].ev,edgeset[i].w);
}
