#yyds干货盘点#
7-1 邻接表创建无向图 (20分)
输入格式: 输入第一行中给出2个整数i(0<i≤10)，j(j≥0)，分别为图G的顶点数和边数。 输入第二行为顶点的信息，每个顶点只能用一个字符表示。 依次输入j行，每行输入一条边依附的顶点。 输出格式: 依次输出各顶点的度，行末没有最后的空格。
输入样例: 5 7 ABCDE AB AD BC BE CD CE DE
输出样例: 2 3 3 3 3
#include<bits/stdc++.h>
using namespace std;
typedef struct ArcNode{//边
int adjvex;//邻接点域
struct ArcNode *nextarc;//链域，指向下一个邻接点
}ArcNode;
typedef struct VNode//顶点
{
char data;//顶点域，储存该顶点信息
ArcNode *firstarc;
}VNode,AdjList[11];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;//顶点数和边数
}ALGraph;//图
int locate(ALGraph &g,char c){
//定位函数
for(int i=0;i<g.vexnum;i++){
if(g.vertices[i].data==c){
return i;
}
}
return -1;
}
int Creat(ALGraph &g){
int adr1,adr2;
char c[11];
char c2[3];
ArcNode *a1,*a2;
scanf("%d %d",&g.vexnum,&g.arcnum);
scanf("%s",c);//顶点的信息
for(int i=0;i<g.vexnum;i++){
g.vertices[i].data=c[i];
g.vertices[i].firstarc=NULL;
}
getchar();
for(int i=0;i<g.arcnum;i++){
scanf("%s",c2);
getchar();//输入每一个边依附的两个顶点
adr1 = locate(g,c2[0]);
adr2=locate(g,c2[1]);
a1 = new ArcNode;
a1->adjvex=adr2;//临界序号为adr2
a1->nextarc=g.vertices[adr1].firstarc;//将e指针指向当前顶点上指向的结点
g.vertices[adr1].firstarc=a1;//互相指向
a2 = new ArcNode;
a2->adjvex = adr1;
a2->nextarc=g.vertices[adr2].firstarc;
g.vertices[adr2].firstarc=a2;
}
}
void print(ALGraph &g){
int cut;
int sum[11]={0};
ArcNode *p=NULL;
for(int i=0;i<g.vexnum;i++){
cut=0;
p=g.vertices[i].firstarc;
while(p){
cut++;
p=p->nextarc;
}
sum[i]=cut;
}
for(int i=0;i<g.vexnum;i++){
if(i==0)
cout<<sum[0];
else
cout<<" "<<sum[i];
}
}
int main(){
ALGraph g;
Creat(g);//创建图
print(g);//输出各顶点的度
}