C - 图中的AddEdge函数

问题描述 投票：-1回答：3

我正在尝试创建具有讲座名称的顶点。我的目标是连接讲座，如果讲座属于同一个学生。但是开始我做一个原型来创建图形和顶点。但我不能用边连接它们。我连接它们但没有给出输出。程序说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;
    }
c graph
3个回答
0
投票

虽然您可能有正在运行的程序，但您的数据结构设计已被破坏。如何从给定顶点添加多个边？

图的邻接列表表示有两部分：

  • 一组顶点。
  • 地图：顶点 - >顶点列表。 //这些是邻接

在C中，将顶点放在数组中很方便。然后，您可以将顶点数组中的索引用作顶点信息本身的“句柄”。这允许map也是一个数组：一个列表数组。

有了这个，生活变得更加简单：

// A vertex in this simple graph contains only its name.
#define NAME_SIZE 10
typedef struct vertex_s {
  char name[NAME_SIZE];
} VERTEX;

// An adjacency is just a vertex ID and a next pointer.
typedef struct adjacency_s {
  struct adjacency_s *next;
  int vertex_id;
} ADJACENCY;

// A graph is a set of vertices and a map from vertex IDs to adjacency lists.
typedef struct graph_s {
  VERTEX vertex[MAX_VERTEX_COUNT];
  ADJACENCY *adjacency_list[MAX_VERTEXT_COUNT];
  int vertex_count;
} GRAPH;

现在您可以初始化图形：

// Make a newly declared graph empty;
void init_graph(GRAPH *graph) {
  graph->vertex_count = 0;
}

添加顶点只是将其数据复制到顶点数组中的新位置。我们将其手柄退回以备将来使用。

int add_vertex(GRAPH *graph, char *name) {
  // Allocate a fresh vertex and empty adjacency list.
  memcpy(graph->vertex[graph->vertex_count].name, name, NAME_SIZE);
  graph->adjacency[graph->vertex_count] = NULL;
  return graph->vertex_count++;
}

现在我们可以通过将新的邻接推到“from”顶点的邻接列表的头部，从任何顶点向其他任何顶点添加边。该节点包含“to”顶点的ID。

void add_edge(GRAPH *graph, int from_id, int to_id) {
  ADJACENCY *a = malloc(sizeof *a); // Don't typecast malloc in C!
  a->vertex_id = to_id;
  a->next = graph->adjacency_list[from_id];
  graph->adjacency_list[from_id] = a;
}

您可能需要的另一个功能是按名称查找顶点。

2
投票

程序说test.exe停止工作

我想指出你有一个严重的记忆问题。你使用全局

 struct Graph *graph;

和初始化的主要的本地*graph;。

 struct Graph* graph = createGraph(V);

然而，在功能

struct AdjListNode* newAdjListNode(char name[10])

你有全球*graph尚未初始化！因此，您的程序将无法正常工作。

您有两种方法可以解决问题。快但不是我推荐的

1）删除本地* graph,to newAdjListNode（char name [10]）的声明

struct Graph* graph = createGraph(V);

并使用全局*图表;

graph = createGraph(V);

2）删除全局struct Graph *graph;的声明并将local * 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;正在使用。清理你对全局变量的使用。全局变量是糟糕的编程习惯。

程序逻辑仍然需要改进，但至少你有适当的内存分配。

1
投票

我只是无法理解你为什么使用数组，因为使用该指针是没有意义的。如果你不想摆脱那个数组指针，你可以使用类似的东西。

 #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 it;
    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;


    return newNode;
}

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

    // 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);
    struct AdjListNode * temp=graph->array[0].head;
    //i try to connect them 
    graph->array[0].head=source;
    graph->array[0].head->next=desti;
    ++(graph->it);

    if(temp)
    desti->next=temp->next;
}

void printGraph(struct Graph* graph)
{
    int v;
    struct AdjListNode* pCrawl = graph->array[0].head;
    for (v = 0; v <= graph->it; ++v)
    {

        printf("name: %s   ", pCrawl->name);
        pCrawl=pCrawl->next;
}
        printf("\n");
}
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;
}`.
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.