1686: 图-建立无向图的邻接表
金币值：2
定数：10
时间限制：1.000 s
内存限制：128 M
正确：46
提交：83
正确率：55.42% 命题人：
题目描述
从键盘输入顶点信息和边信息建立一个无向图的邻接表。阅读程序，编写CreateALGraph函数代码，要求在邻接表中插入结点时采用头部插入法。
测试代码 复制
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100 // 最大顶点数,应由用户定义
typedef char VertexType; // 顶点类型应由用户定义
typedef int EdgeType; // 边上的权值类型应由用户定义
typedef struct EdgeNode { // 边表结点
int adjvex; // 邻接点域,存储该顶点对应的下标
EdgeType info; // 用于存储权值,对于非加权图可以不需要
struct EdgeNode *next; // 链域,指向下一个邻接点
}EdgeNode;
typedef struct VertexNode { // 顶点表结点
VertexType data; // 顶点域,存储顶点信息
EdgeNode *firstEdge; // 边表头指针
}VertexNode, AdjList[MAXVEX];
typedef struct {
AdjList adjList;
int numNodes,numEdges; // 图中当前顶点数和边数
}GraphAdjList;
void PrintALGraph(GraphAdjList &G) {//打印图的邻接表
int i;
EdgeNode *e;
for(i = 0; i < G.numNodes; i++) {
printf("%c|",G.adjList[i].data);
e = G.adjList[i].firstEdge;
while(e!=NULL) {
printf("(%d,%d)",i,e->adjvex);
e=e->next;
}
printf("\n");
}
}
void CreateALGraph(GraphAdjList &G);
int main(void) {
GraphAdjList G;
CreateALGraph(G);
PrintALGraph(G);
return 0;
}
/*提交以下代码*/
void CreateALGraph(GraphAdjList &G) {// 建立图的邻接表
}输入格式
第1行输入2个整数，分别表示图中的顶点数n和边数m
第2行输入n个字符，分别表示图中n个顶点信息
第3-m+2行每行输入两个整数u和v，分别表示图中一条边的两个顶点
第2行输入n个字符，分别表示图中n个顶点信息
第3-m+2行每行输入两个整数u和v，分别表示图中一条边的两个顶点
输出格式
共有n行，每行中的信息分别表示一个顶点信息以及与该顶点相邻的每条边的信息，具体输出格式见样例。
输入样例 复制
4 4
ABCD
0 1
0 2
1 2
1 3输出样例 复制
A|(0,2)(0,1)
B|(1,3)(1,2)(1,0)
C|(2,1)(2,0)
D|(3,1)提示
根据题目要求，第1行输入两个整数，第2行输入三个字符，此时需要注意正确处理第1行的结束符，否则会造成输入数据有误。具体处理方法如下：
scanf("%d %d\n",&G.numNodes,&G.numEdges);
或
scanf("%d %d",&G.numNodes,&G.numEdges); getchar();
scanf("%d %d\n",&G.numNodes,&G.numEdges);
或
scanf("%d %d",&G.numNodes,&G.numEdges); getchar();