背景

折腾

邻接矩阵 VS 邻接表

邻接矩阵

数据结构图

代码实现

int array[10][10] = {0};

void cteate_array() {
    char x;
    char y;
    for (int k = 0; k < edge; k++) {
        fflush(stdin);
        scanf("%c %c", &x, &y);
        array[x - 'a'][y - 'a'] = 1;
    }
}

传统创建邻接表

数据结构图

代码实现

#include <iostream>
#include "stdio.h"
#include "string.h"
#include "stdlib.h"

using namespace std;
typedef char vertex_type[20];


int num;
int edge;
int kind;
// kind = 0 : 有向图
// kind = 1 ： 无向图
typedef struct arcnode {
    int cur;
    struct arcnode *next;
} arcnode, *arcnode_p;

typedef struct vnode {
    vertex_type data;
    struct arcnode *first;
} vnode, *nodelist;


// 输入data，返回邻接表的cur
int getnode(vnode *G, char *data) {
    int i;
    for (i = 0; i < num; i++)
        if (strcmp(data, G[i].data) == 0)
            return i;
    return -1;
}


void create(vnode *G, int kind) {
    for (int i = 0; i < num; i++) {
        scanf("%s", G[i].data);
        G[i].first = NULL;
    }
    int po;
    int nex;
    for (int i = 0; i < edge; i++) {
        char a[20] = {'\0'};
        char b[20] = {'\0'};
        scanf("%s%s", a, b);
        if ((po = getnode(G, a)) >= 0 && (nex = getnode(G, b)) >= 0) {
            arcnode_p new_node;
            // 新建结点
            new_node = new arcnode;
            new_node->cur = nex;
            new_node->next = NULL;
            // 如果头为空，直接链到first
            if (G[po].first == NULL)
                G[po].first = new_node;
            else {
                arcnode_p p;
                p = G[po].first;
                while (p->next != NULL) {
                    p = p->next;
                }
                p->next = new_node;
            }
            // 如果是无序图
            if (kind == 1) {
                // 新建结点
                new_node = new arcnode;
                new_node->cur = po;
                new_node->next = NULL;
                // 如果头为空，直接链到first
                if (G[nex].first == NULL)
                    G[nex].first = new_node;
                else {
                    arcnode_p p;
                    p = G[nex].first;
                    while (p->next != NULL) {
                        p = p->next;
                    }
                    p->next = new_node;
                }
            }
        }
    }
}
int main() {
    nodelist G;
    scanf("%d", &kind);
    scanf("%d%d", &num, &edge);
    G = new vnode[num];
    create(G, kind);
    arcnode_p p;
    for (int i = 0; i < num; i++) {
        printf("%s:   ", G[i].data);
        p = G[i].first;
        while (p != NULL) {
            printf("%s ", G[p->cur].data);
            p = p->next;
        }
    }
}