求一个将无向带权图的邻接矩阵转化为边集数组的C程序

发布网友 发布时间：2022-04-20 04:43

我来回答

共3个回答

热心网友 时间：2023-08-31 16:58

typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;

typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode;

typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;

void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ])

{

int i,j; glinklistnode *p;

for(i=0;i<=n-1;i++) g2[i].firstarc=0;

for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++)

if (g1.edge[i][j]==1)

{

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j;

p->nextarc=g[i].firstarc; g[i].firstarc=p;

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i;

p->nextarc=g[j].firstarc; g[j].firstarc=p;

扩展资料：

数据结构算法注意事项。

算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的存储结构实质上是它的逻辑结构在计算机存储器中的实现，为了全面的反映一个数据的逻辑结构，它在存储器中的映象包括两方面内容，即数据元素之间的信息和数据元素之间的关系。

不同数据结构有其相应的若干运算。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新和排序等。

数据的运算是数据结构的一个重要方面，讨论任一种数据结构时都离不开对该结构上的数据运算及其实现算法的讨论。

数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

热心网友 时间：2023-08-31 16:58

#include<stdio.h>
#include<stdlib.h>
#define max 20
#define digit 1
define zero 0
typedef struct{
int num;
char data;
}Vertex;
typedef struct{
intn; //顶点数
inte; //弧数
Vertex vexs[max];
int edges[max][max];
}MGraph;
typedef struct node{
int adjvex;
node *nextarc;
char info;
}ARCNODE; //邻接表的结点结构
typedef struct{
char vexdata;
ARCNODE *firstarc;
}VEXNODE; //邻接表的表头结点
typedef struct{
int vexnum,arcnum; //顶点数、弧数
VEXNODE ve[max];
}ALGraph; //邻接表类型

ALGraph *Creat_alg(){ //创建邻接表
ALGraph *alg;
int i,n,e,b,a;
char ch;
ARCNODE *AR;
alg=(ALGraph*)malloc(sizeof(ALGraph));
printf("输入顶点数:");
scanf("%d",&n);
printf("输入弧数:");
scanf("%d",&e);
alg->vexnum=n;
alg->arcnum=e;
printf("输入顶点信息:\n");
for(i=0;i<n;i++){
scanf("%s",&ch);
alg->ve[i].vexdata=ch;
alg->ve[i].firstarc=NULL;
}
printf("输入弧的信息(弧的两端点):\n");
for(i=0;i<e;i++){
scanf("%d%d",&a,&b);
AR=(ARCNODE*)malloc(sizeof(ARCNODE));
AR->adjvex=b;
AR->info=alg->ve[b].vexdata;
AR->nextarc=alg->ve[a].firstarc;
alg->ve[a].firstarc=AR;
AR=(ARCNODE*)malloc(sizeof(ARCNODE));
AR->adjvex=a;
AR->info=alg->ve[a].vexdata;
AR->nextarc=alg->ve[b].firstarc;
alg->ve[b].firstarc=AR;
}
return alg;
}

void ALGout(ALGraph *alg){ //邻接表输出
int i,n1;
ARCNODE *p;
VEXNODE *q;
n1=alg->vexnum;
for(i=0;i<n1;i++){
q=&alg->ve[i];
printf("%c",q->vexdata);
p=q->firstarc;
while(p!=NULL){
printf("─→");
printf("%c",p->info);
p=p->nextarc;
}
printf("\n");
}
}

MGraph *ALG_change_MG(ALGraph *alg){ //将邻接表转换为邻接矩阵
MGraph *mg;
int i,n1;
mg=(MGraph*)malloc(sizeof(MGraph));
mg->n=alg->vexnum;
mg->e=alg->arcnum;
n1=mg->n;
for(i=0;i<n1;i++){
mg->vexs[i].num=i;
mg->vexs[i].data=alg->ve[i].vexdata;
}
ARCNODE *p;
for(i=0;i<n1;i++){
p=alg->ve[i].firstarc;
while(p!=NULL){
mg->edges[i][p->adjvex]=1;
mg->edges[p->adjvex][i]=1;
p=p->nextarc;
}
}
return mg;
}

void MGout(MGraph *mg){ //输出邻接矩阵
int i,j,k;
k=mg->n;
for(i=0;i<k;i++){
for(j=0;j<k;j++){
if(mg->edges[i][j]==1)
printf("%-5d",digit);
else
printf("%-5d",zero);
}
printf("\n");
}
}

void main(){
MGraph *mg;
ALGraph *alg;
printf("建立无向图的邻接表:\n");
alg=Creat_alg();
printf("邻接表输出:\n");
ALGout(alg);
mg=ALG_change_MG(alg);
printf("邻接矩阵输出:\n");
MGout(mg);
}

热心网友 时间：2023-08-31 16:59

算法有问题