问题 B: 邻接表存储的图转化为邻接矩阵存储的图-附加代码模式

题目描述

邻接表和邻接矩阵，是两种最重要的，也是最基础的图的存储方式。同学们需要熟练掌握这两种方式的程序编写。

以上图为例，其对应的邻接表和邻接矩阵存储方式可以分别表示为：
（1）邻接表法
节点个数：7
节点信息：a b c d e f g
a-g-f
b-c
c-e
d
e-d
f-g-e
g-d
（2）邻接矩阵法
节点个数：7
节点信息：a b c d e f g
0 0 0 0 0 1 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 1
0 1 0 1 0 0 0
请编写程序将邻接表法存储的图，转化为邻接矩阵法存储的图，并输出

// please comment the following code when you submit to OJ
int main(){
    // freopen("/config/workspace/answer/test.in","r",stdin);
    linkGraph LG;
    Graph G;
    InputlinkGraph(LG);
    PrintlinkGraph(LG);
    linkGraph2Graph(LG,G);
    printGraph(G);
    DestroylinkGraph(LG);
    return 0;
}
 
 

 本题为附加代码模式，以上代码为自动附加在同学们提交的代码后面。在本题的提示中有代码框架，请同学们拷贝后，修改，再注释掉部分代码，最后提交。

输入格式

输入第一行为正整数n(n<100)，表示图的节点个数。
接下来n行，表示每个节点的信息，还有以该节点为起点可以到达的其他点的边信息
约定：每个节点信息为小写字母a开始的连续n个字母

输出格式

首先输出邻接表
再输出由0，1组成的邻接矩阵

输入样例

7
a-g-f
b-c
c-e
d
e-d
f-g-e
g-d

输出样例  

a --> g --> f 
b --> c 
c --> e 
d 
e --> d 
f --> g --> e 
g --> d 
0 0 0 0 0 1 1 
0 0 1 0 0 0 0 
0 0 0 0 1 0 0 
0 0 0 0 0 0 0 
0 0 0 1 0 0 0 
0 0 0 0 1 0 1 
0 0 0 1 0 0 0 

数据范围与提示

代码框架如下（注意里面有一些小错误需要修复）：

#include 
#include 
#include 
#include 
using namespace std;
 
#define MAX_SIZE 100
 
// 邻接矩阵存储的图
struct Graph
{
    int vexNumber;
    string vexInfo[MAX_SIZE];
    int adjMatrix[MAX_SIZE][MAX_SIZE];
};
 
// 弧结点定义
struct ArcNode
{
    int weight;       // 弧上的信息部分
    int adj;          // 邻接点的序号
    ArcNode *nextarc; // 下一条边
};
 
// 顶点结点定义
struct VexNode
{
    string Info;       // 顶点上的信息部分
    ArcNode *firstarc; // 弧链头指针
};
 
// 邻接表结构的图的定义
struct linkGraph
{
    VexNode *vexes; //  每个节点的邻接表
    int vexnumber;  //  节点数量
};
 
// 邻接表存储的图的初始化
int InitGraph(linkGraph &G, int vexnumber)
{
    G.vexes = new VexNode[vexnumber];
    G.vexnumber = vexnumber;
    for (int i = 0; i < vexnumber; i++)
        G.vexes[i].firstarc = NULL;
    return 0;
}
// 构造边节点指针
ArcNode* getArcNode(int adj){
    ArcNode* node = new ArcNode();
    node->adj = adj;
    node->nextarc = nullptr;
    return node;
}
// 根据输入构造邻接表存储的图
void InputlinkGraph(linkGraph& LG){
    
}
// 将邻接表存储的图转化为邻接矩阵存储的图
void linkGraph2Graph(const linkGraph& LG, Graph& G){
    
}
 
// 输出邻接矩阵
void printGraph(const Graph& G){
   
}
 
 
// 邻接表存储的图的销毁
int DestroylinkGraph(linkGraph &G)
{
    for (int i = 0; i < G.vexnumber; i++)
    {
        while (G.vexes[i].firstarc != NULL)
        {
            ArcNode *p = G.vexes[i].firstarc;
            G.vexes[i].firstarc = p->nextarc;
            delete p;
        }
    }
    delete[] G.vexes;
    G.vexes = NULL;
    G.vexnumber = 0;
    return 0;
}
// please comment the following code when you submit to OJ
int main(){
    // freopen("/config/workspace/answer/test.in","r",stdin);
    linkGraph LG;
    Graph G;
    InputlinkGraph(LG);
    PrintlinkGraph(LG);
    linkGraph2Graph(LG,G);
    printGraph(G);
    DestroylinkGraph(LG);
    return 0;
}

代码展示 

#include
#include
#include
#include
using namespace std;
 
#define MAX_SIZE 100
 //领接矩阵存储的图
struct Graph{
    int vexNumber;
    string info[MAX_SIZE];
    int adjMatrix[MAX_SIZE][MAX_SIZE];
};
 //弧结点定义
struct ArcNode{
    int weight;//弧上的信息部分
    int adj;//邻接点的序号
    ArcNode *nextarc;
};
 //顶点结点定义
struct VexNode{
    char Info;
    ArcNode *firstarc;
};
 //领接表结构的图的定义
struct linkGraph{
    VexNode *vexes;
    int vexnumber;
};
  
int preInitGraph(linkGraph &G){
    G.vexes=new VexNode[G.vexnumber];
    for(int i=0;i
        G.vexes[i].firstarc=NULL;
        G.vexes[i].Info=(char)('a'+i);
    }
    return 0;
}
//构造边结点指针
ArcNode * getArcNode(int adj){
    ArcNode* node=new ArcNode();
    node->adj=adj;
    node->nextarc=nullptr;
    return node;
}
//根据输入构造领接表存储的图
void InputlinkGraph(linkGraph &LG){
    cin>>LG.vexnumber;
    preInitGraph(LG);
    string temp;
    for(int i=0;i
        cin>>temp;
        for(int j=2;jlength();j++){
            if(temp[j]>='a'&&temp[j]<='z'){
                int k;
                for(k=0;k
                    if(LG.vexes[k].Info==temp[j]){
                        break;
                    }
                }
                ArcNode *p=getArcNode(k);
                ArcNode *q=LG.vexes[i].firstarc;
                if(LG.vexes[i].firstarc==NULL)
                    LG.vexes[i].firstarc=p;
                else{
                    while(q->nextarc!=NULL){
                        q=q->nextarc;
                    }
                    q->nextarc=p;
                }
            }
        }
    }
}
//将领接表存储的图转化为领接矩阵存储的图
void linkGraph2Graph(const linkGraph &LG,Graph &G){
    G.vexNumber=LG.vexnumber;
    G.adjMatrix[MAX_SIZE][MAX_SIZE]={0};
    for(int i=0;i
        ArcNode *p=LG.vexes[i].firstarc;
        while(p!=NULL){
            G.adjMatrix[i][p->adj]=1;
            p=p->nextarc;
        }
    }
}
//输出领接矩阵
void printGraph(const Graph &G){
    for(int i=0;i
        for(int j=0;j
            cout<" ";
        }
        cout<
    }
}
 
int DestroylinkGraph(linkGraph &G){
    for(int i=0;i
        while(G.vexes[i].firstarc!=NULL){
            ArcNode *p=G.vexes[i].firstarc;
            G.vexes[i].firstarc=p->nextarc;
            delete p;
        }
    }
    delete[]G.vexes;
    G.vexes=NULL;
    G.vexnumber=0;
    return 0;
}
 
//输出领接表存储的图
void PrintlinkGraph(const linkGraph &G){
    for(int i=0;i
        cout<
        ArcNode *p=G.vexes[i].firstarc;
        while(p!=NULL){
            cout<<" --> "<adj].Info;
            p=p->nextarc;
        }
        cout<
    }
}
 
//comment
/*
int main(){
    freopen("/config/workspace/test/test","r",stdin);
    linkGraph LG;
    Graph G;
    InputlinkGraph(LG);
    PrintlinkGraph(LG);
    linkGraph2Graph(LG,G);
    printGraph(G);
    DestroylinkGraph(LG);
 
    return 0;
}
*/