C - 图中的 AddEdge 函数

Question

我正在尝试创建具有讲座名称的顶点。我的目标是在讲座属于同一学生的情况下连接讲座。但首先我制作了一个原型(prototype)来创建图形和顶点。但我无法将它们与边连接。我连接它们，但没有给出输出。程序说 test.exe 停止工作这是我的代码

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

    int count = 0;//count for adjlist place for vertices

    struct AdjListNode
    {
        char name[10];//lecture name
        struct AdjListNode* next;
        int id;//id for place of vertex in array of graph
    };
    struct AdjListNode *desti, *source, *newNode, *temp, *pCrawl; 

    struct AdjList
    {
        struct AdjListNode *head;  // pointer to head node of list
    };
    struct AdjList *array;

    struct Graph
    {
        int V;
        struct AdjList* array;
    };
    struct Graph *graph;

    struct AdjListNode* newAdjListNode(char name[10])
    {
        struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
        memcpy(newNode->name, name, sizeof newNode->name);
        newNode->id = count;
        newNode->next = NULL;
        graph->array[count].head = newNode;
        count++;

        return newNode;
    }

    struct Graph* createGraph(int V)
    {
        struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
        graph->V = V;

        // Create an array of adjacency lists.  Size of array will be V
        graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

        // Initialize each adjacency list as empty by making head as NULL
        int i;
        for (i = 0; i < V; ++i)
            graph->array[i].head = NULL;

        return graph;
    }

    void addEdge(struct Graph* graph, char src[10], char dest[10])
    {
   //i create destination vertex and source vertex
        struct AdjListNode* desti = newAdjListNode(dest);//
        struct AdjListNode* source = newAdjListNode(src);

        //i try to connect them 
        desti->next = graph->array[source->id].head;
        source->next = graph->array[desti->id].head;
    }

    void printGraph(struct Graph* graph)
    {
        int v;
        for (v = 0; v < graph->V; ++v)
        {
            struct AdjListNode* pCrawl = graph->array[v].head;
            printf("name: %s -  ", pCrawl->name);
            printf("%s",pCrawl->next->name);  
    }
    }
    int main()
    {
        // create the graph given in above fugure
        int V = 5;
        struct Graph* graph = createGraph(V);
        newAdjListNode("BS11");
        newAdjListNode("CS10");
        newAdjListNode("MATH10"); 
        addEdge(graph, "CS10", "MATH10");
        addEdge(graph, "BS11", "CS10");
        printGraph(graph);
        return 0;
    }

Answer 1

Program says test.exe stop working

我想指出您有严重的内存问题。您使用全局

 struct Graph *graph;

和本地*graph;在您初始化的main中。

 struct Graph* graph = createGraph(V);

然而，在函数中

struct AdjListNode* newAdjListNode(char name[10])

您有尚未初始化的全局*graph!因此你的程序将无法正常运行。

您有两种方法可以解决该问题。速度很快，但我不推荐

1) 将本地 *graph, 的声明删除到 newAdjListNode(char name[10])

struct Graph* graph = createGraph(V); 

并使用全局*图；

graph = createGraph(V); 

2) 删除全局struct Graph *graph;的声明并将本地 *graph 传递给您的 newAdjListNode(char *name, struct Graph* graph);

该版本的程序如下所示:

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

    int count = 0;//count for adjlist place for vertices global!!??

    struct AdjListNode
    {
        char name[10];//lecture name
        struct AdjListNode* next;
        int id;//id for place of vertex in array of graph
    };

    struct AdjListNode *desti, *source, *temp, *pCrawl; // *newNode, // globals!?

    struct AdjList
    {
        struct AdjListNode *head;  // pointer to head node of list
    };

   //struct AdjList *array; //used where???
   //---------------------

    struct Graph
    {
        int V;
        struct AdjList* array; // 
    };

   // struct Graph *graph; - do not use globals, they create problems and colide with local variables of the same name.
    //--------------------------

    struct AdjListNode* newAdjListNode(char name[10], struct Graph* graph)
    {
        struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));

        memcpy(newNode->name, name, sizeof newNode->name); 

        newNode->id = count;
        newNode->next = NULL;

        graph->array[count].head  = newNode;
        count++;

        return newNode;
    }

    struct Graph* createGraph(int V)
    {
        struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
        graph->V = V;

        // Create an array of adjacency lists.  Size of array will be V
        graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

        // Initialize each adjacency list as empty by making head as NULL
        int i;
        for (i = 0; i < V; ++i)
            graph->array[i].head = NULL;

        return graph;
    }

    void addEdge(struct Graph* graph, char src[10], char dest[10])
    {
   //i create destination vertex and source vertex
        //struct AdjListNode* 
        desti = newAdjListNode(dest,graph);//
        //struct AdjListNode* 
        source = newAdjListNode(src,graph);

        //i try to connect them 
        desti->next = graph->array[source->id].head;
        source->next = graph->array[desti->id].head;
    }

    void printGraph(struct Graph* graph)
    {
        int v;
        for (v = 0; v < graph->V; ++v)
        {
            //struct AdjListNode* 
            pCrawl = graph->array[v].head;
            printf("name: %s -  ", pCrawl->name);
            printf("%s",pCrawl->next->name);  
        }
    }


    int main()
    {
        // create the graph given in above fugure
        int V = 5;
        struct Graph* graph = createGraph(V);

        newAdjListNode("BS11",graph);
        newAdjListNode("CS10",graph);
        newAdjListNode("MATH10",graph); 

        addEdge(graph, "CS10", "MATH10");
        addEdge(graph, "BS11", "CS10");
        printGraph(graph);
        return 0;
    }

您还可以在

中隐藏全局变量 *desti、*source、*temp、*pCrawl;

void addEdge(struct Graph* graph, char src[10], char dest[10])

和全局 struct AdjList *array; 未使用。清理你对全局变量的使用。全局变量是不好的编程习惯。

程序逻辑还有待改进，但至少你有合适的内存分配。