【王道数据结构】【强化练习】【图的应用】【4.2.1-4.2.2】

4.2.1

定义一个顺序存储的图（邻接矩阵实现）

#include <iostream>
typedef struct maxtrix{
    int ** matrix;
    int rows;
    int cols;
}matrix,*pm;

void init(pm m,int row ,int col)
{
    m->matrix=(int **) malloc(sizeof (int*)*row);
    m->cols=col;
    m->rows=row;
    for(int i=0;i<row;i++)
        m->matrix[i]=(int*) malloc(sizeof (int)*col);
    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
            m->matrix[i][j]=0;
}
void print(pm p)
{
    for(int i=0;i<p->rows;i++) {
        for (int j = 0; j < p->cols; j++)
            printf("%3d", p->matrix[i][j]);
        puts("");
    }
}
void test()
{
    maxtrix m;
    init(&m,10,10);
    print(&m);
}
int main() {
    test();
    return 0;
}

4.2.2

定义一个链式存储的图（邻接表实现）

#include <iostream>
typedef struct node{
    int data;
    node* next;
};
typedef struct headnode{
    int number;
    node* node;
}headnode;

typedef struct graph{
    headnode* head;
    int dots;
}graph;

void init(graph*g,int dots)
{
    g->dots=dots;
    g->head=(headnode*) malloc(sizeof (headnode)*dots);
    for(int i=0;i<dots;i++) g->head[i].number=i,g->head[i].node= nullptr;
}
void print(graph* g)
{
    for(int i=0;i<g->dots;i++)
    {
        printf("%3d",g->head[i].number);
        node* tmp=g->head[i].node;
        while(tmp){
            printf("%3d",tmp->data);
            tmp=tmp->next;
        }
        puts("");
    }
}
void test()
{
    graph g;
    init(&g,10);
    print(&g);
}
int main() {
    test();
    return 0;
}