c - 带有空指针的图表的奇怪输出

Question

我正在尝试构建一个可以使用邻接列表或矩阵处理图的程序，为了做到这一点，老师教我们将邻接声明为 void *，以便将其转换为列表或矩阵。

使用以下代码我得到以下输出:

正如你所看到的，B 节点中出现了一些奇怪的事情。

如果我尝试使用 CodeBlocks 进行调试，调试器会在 appendNodeList 的 if (L->target != target) {..

我认为 initGraphList 中的动态分配存在问题，但我不知道如何修复它。

您认为这里的问题是什么？是分配吗？如果是，我该如何修复它？预先感谢您的帮助!

代码:

main.c

#include <stdio.h>
#include <stdlib.h>
#include "Graph.h"

int main(int argc, const char * argv[]) {
    Graph G = NULL;
    G = initGraphList(3);
    addEdgeList(G, 0, 1, 1);
    addEdgeList(G, 0, 2, 2);
    addEdgeList(G, 1, 0, 3);
    addEdgeList(G, 1, 2, 4);
    addEdgeList(G, 2, 0, 5);
    addEdgeList(G, 2, 1, 6);
    printGraphList(G);
    return 0;
}

图.h

#include "List.h"

struct TGraph {
    void **adj;
    int nodes_count;
};

typedef struct TGraph *Graph;

typedef struct AdjList{
    List *nodes;
}AdjList;

Graph initGraphList(int);
void printGraphList(Graph G);
void addEdgeList(Graph G, int source, int target, float peso);

图.c

#include <stdio.h>
#include <stdlib.h>
#include "Graph.h"

Graph initGraphList(int nodes_count){
    Graph G = (Graph)malloc(sizeof(struct TGraph));
    G->adj = malloc(sizeof(AdjList));
    G->nodes_count = nodes_count;
    ((AdjList *)(G->adj))->nodes = malloc(nodes_count * sizeof(List));
    return G;
}

void printGraphList(Graph G) {
    if (G != NULL) {
        int i;
        for(i = 0; i < G->nodes_count; i++) {
            printf("%c -> ", i + 'A');  //I use this in order to print out the nodes as A,B,C,.. instead of 0,1,2,...
            printList(((AdjList *)(G->adj))->nodes[i]);
            puts("\n");
        }
    }
}

void addEdgeList(Graph G, int source, int target, float peso){
    if(G != NULL){
        if(source != target){
            if(source < G->nodes_count){
                if(target < G->nodes_count)
                    ((AdjList*)(G->adj))->nodes[source]= appendNodeList(((AdjList*)(G->adj))->nodes[source], target, peso);
                else
                    fprintf(stderr, "Il nodo %d non e' compreso nel grafo\n", target);
            }else
                fprintf(stderr, "Il nodo %d non e' compreso nel grafo\n", source);
        }else
            fprintf(stderr, "Non e' possibile inserire un arco che punta allo stesso nodo\n");
    }else
        fprintf(stderr, "Grafo invalido\n");
}

列表.h

struct TList {
    char target;
    float peso;
    struct TList* next;
};

List initNodeList(int info, float peso);
List appendNodeList(List L, int target, float peso);
void printList(List L);

列表.c

#include <stdio.h>
#include <stdlib.h>
#include "List.h"

List initNodeList(int info, float peso) {
    List L = malloc(sizeof(struct TList));
    L->target = info;
    L->peso = peso;
    L->next = NULL;
    return L;
}

List appendNodeList(List L, int target, float peso) {
    if (L != NULL) {
        if (L->target != target) {
            L->next = appendNodeList(L->next, target, peso);
        }
    } else {
        L = initNodeList(target, peso);
    }
    return L;
}

void printList(List L) {
    if (L != NULL) {
        printf(" %c(%f), ", L->target + 'A', L->peso);
        printList(L->next);
    }
}

Answer 1

首先，您忘记用 NULL 初始化指针数组。这是我在您的代码中发现的主要错误。

如果您使用 typedef 定义任何指针，请避免误导性名称(例如添加后缀'Ptr' 为类型名称)

typedef struct TList {
    char target;
    float peso;
    struct TList* next;
} *TListPtr;

typedef struct TAdjList{
    TListPtr *nodes;
} *TAdjListPtr;

不需要void **adj。 TAdjListPtr *adj 做你想要的事情

typedef struct TGraph {
    TAdjListPtr adj;
    int nodes_count;
} *TGraphPtr;

TListPtr initNodeList(int info, float peso) {
    TListPtr L = malloc(sizeof(struct TList));
    L->target = info;
    L->peso = peso;
    L->next = NULL;
    return L;
}

TListPtr appendNodeList(TListPtr L, int target, float peso) {
    if (L != NULL) {
        if (L->target != target) {
            L->next = appendNodeList(L->next, target, peso);
        }
    } else {
        L = initNodeList(target, peso);
    }
    return L;
}

void printList(TListPtr L) {
    if (L != NULL) {
        printf(" %c(%f), ", L->target + 'A', L->peso);
        printList(L->next);
    }
}

您必须用 NULL 初始化指针数组。为此，请使用 memset。

TGraphPtr initGraphList(int nodes_count){
    TGraphPtr G = malloc(sizeof(struct TGraph));
    G->adj = malloc(sizeof(TAdjList));
    G->nodes_count = nodes_count;
    G->adj->nodes = (TListPtr*)malloc(nodes_count * sizeof(TListPtr));
    memset( G->adj->nodes, 0, nodes_count * sizeof( TListPtr ) );
    return G;
}

void printGraphList(TGraphPtr G) {
    if (G != NULL) {
        int i;
        for(i = 0; i < G->nodes_count; i++) {
            printf("%c -> ", i + 'A');  //I use this in order to print out the nodes as A,B,C,.. instead of 0,1,2,...
            printList(G->adj->nodes[i] );
            puts("\n");
        }
    }
}

void addEdgeList(TGraphPtr G, int source, int target, float peso){
    if(G != NULL){
        if(source != target){
            if(source < G->nodes_count){
                if(target < G->nodes_count)
                    G->adj->nodes[source] = appendNodeList(G->adj->nodes[source], target, peso);
                else
                    fprintf(stderr, "Il nodo %d non e' compreso nel grafo\n", target);
            }else
                fprintf(stderr, "Il nodo %d non e' compreso nel grafo\n", source);
        }else
            fprintf(stderr, "Non e' possibile inserire un arco che punta allo stesso nodo\n");
    }else
        fprintf(stderr, "Grafo invalido\n");
}