主题：用邻接表存储无向图
yybb
[专家分：0] 发布于 2006-08-19 08:49:00
//*****************以下是邻接表存储图的信息(方法二)****************************
#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef char vextype; //顶点的数据类型
typedef float adjtype; //权值类型
typedef struct node
{
int adjvex; //邻接点域
adjtype arctex; //权值信息
struct node *next; //链域
}edgenode; //边表结点
typedef struct
{
vextype vertex; //顶点信息
edgenode *link;
}vexnode;
createDjList(vexnode ga[],int n,int e); //建立无向图的邻接表
print(vexnode ga[],int n); //无向图的输出
main()
{
vexnode ga[100];
int n,e;
printf("请输的顶点数和边数:");
scanf("%d %d",&n,&e);
createDjList(ga,n,e);
printf("无向图形成后的情况:\n");
print(ga,n); //无向图的输出
}
回复列表 （共6个回复）
沙发
yybb [专家分：0] 发布于 2006-08-19 08:45:00
createDjList(vexnode ga[],int n,int e) //建立无向图的邻接表
{
int i,j,k;
float w;
edgenode *s,*p,*q;
//printf("请按顺序输入%d个顶点(按下标顺序输入):",n);
//getchar();
for(i=1;i<=n;i++) //读入顶点信息
{
ga[i].vertex=char(i);
s=(edgenode *)malloc(sizeof(edgenode)); //申请一个节点作为头结点
s->adjvex=0;
s->next=NULL;
ga[i].link=s; //边表头指针初始化
}
printf("请输入%d边的信息:\n",e);
for(k=0;k<e;k++)
{
printf("请输入第%d条的起点、终点和权:",k+1);
scanf("%d %d %f",&i,&j,&w); //读入边(vi,vj)上的权w
if(i<=n&&j<=n&&i!=j&&i>0&&j>0)//添加条件,为了不超过下标
{
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=j;
s->arctex=w;
s->next=NULL;
p=ga[i].link;
while(ga[i].link->next!=NULL&&p->next!=NULL&&(p->adjvex)<(s->adjvex)) //将s插入顶点vj的边表合适位置
{
q=p; //p的前驱,为了能让序号从大到小排序
p=p->next;
}
if(p->adjvex!=s->adjvex)
{
if(ga[i].link->next==NULL) //邻接表还没有结点时
p->next=s;
else if(ga[i].link->next==p&&(p->adjvex)>(s->adjvex)) //当插在首位置时
{
s->next=p;
ga[i].link->next=s;
}
else if(p->adjvex>s->adjvex) //插在两个结点之间
{
q->next=s;
s->next=p;
}
else if(p->adjvex<s->adjvex) //插到末尾
{
s->next=p->next;
p->next=s;
}
}
板凳
yybb [专家分：0] 发布于 2006-08-19 08:46:00
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=i;
s->arctex=w;
s->next=NULL;
p=ga[j].link;
while(ga[j].link->next!=NULL&&p->next!=NULL&&(p->adjvex)<(s->adjvex)) //将s插入顶点vj的边表合适位置
{
q=p; //p的前驱,为了能让序号从大到小排序
p=p->next;
}
if(p->adjvex!=s->adjvex) //添加条件，为了不链接相同的邻接结点
{
if(ga[j].link->next==NULL)
p->next=s;
else if(ga[j].link->next==p&&(p->adjvex)>(s->adjvex))
{
s->next=p;
ga[j].link->next=s;
}
else if(p->adjvex>s->adjvex)
{
q->next=s;
s->next=p;
}
else if(p->adjvex<s->adjvex)
{
s->next=p->next;
p->next=s;
}
}
}
}
}
3 楼
yybb [专家分：0] 发布于 2006-08-19 08:47:00
print(vexnode ga[],int n)//无向图的输出
{
int i,j,k=0,t=0; //设置k,是为了整齐输出0;t是为了路径有没有存在
edgenode *p;
for(i=1;i<=n;i++)
{
p=ga[i].link->next;
for(j=1;j<=n;j++)
{
if(p!=NULL)
if(p->adjvex==((char)j))
{
printf("V%d->V%d路径:%-3.0f",i,j,p->arctex);
p=p->next;
t=1;
}
if(t!=1)
printf("V%d->V%d路径:%-3d",i,j,k);
t=0;
}
printf("\n");
}
}
//*****************以上是邻接表存储图的信息****************************
[em3][em3][em3][em3][em3][em3][em13][em13][em13][em13][em19][em19][em20][em20][em20][em20][em5][em5][em5][em2][em2][em13][em13][em13]
4 楼
tgbtgb [专家分：490] 发布于 2006-08-19 12:26:00
你瞅瞅，就你？？？？？？？？？？／
5 楼
未成名的柯南 [专家分：10] 发布于 2006-08-20 07:06:00
呵呵！
收下了哦！
我们这些初学者就是要交流嘛！
6 楼
yybb [专家分：0] 发布于 2006-09-02 09:32:00
你等着瞧，我会成为编程高手的，你要是那么强，那就编几个试试啊，操。。。。。。。
[em12][em12][em12][em12]
我来回复
您所在位置：