c - 链表与图

Question

我有两段代码，一段创建链表，另一段创建图形并在其中添加边。

链表的基本代码如下

void create_list(node * current,int data){
    node *head=(node*)malloc(sizeof(node*));
    head->data=data;
    head->next=NULL;
    current->next=head;

}

int main() {
    node *head=(node*)malloc(sizeof(node*));
    create_list(head,4);

    node* temp=head;
    while(temp->next!=NULL)
      {
          cout<<temp->data;
          temp=temp->next;
      }
return 0;
}

上述程序的输出是0。

现在，对于图表，基本代码将是这样的

// A utility function that creates a graph of V vertices
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;
}

// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{
    // Add an edge from src to dest.  A new node is added to the adjacency
    // list of src.  The node is added at the begining
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Since graph is undirected, add an edge from dest to src also
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Driver program to test above functions
int main()
{
    // create the graph given in above fugure
    int V = 5;
    struct Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    // print the adjacency list representation of the above graph
    printGraph(graph);

    return 0;
}

我知道链表返回零，因为我需要传递头指针的引用，但令我困惑的是，图形代码中发生了同样的事情，但更改是全局可见的，即在添加边缘时。

这可能是一个非常幼稚的问题，但可以帮助我理解代码吗？ 谢谢!

更新:

void addEdge(struct Graph* graph, int src, int dest)

这里图表作为参数传递以添加边缘，它仍然全局显示更改，但是当我对链接列表执行相同操作时，即

void create_list(node * current,int data)

它不显示全局更改，为什么？

Answer 1

您的 malloc 调用使用 sizeof(node *) 而不是 sizeof(node)。

您的 while 循环将显示太少的一个，并将显示 [空] head 节点(即您得到垃圾而不是 4) .

这是带有注释和修复的代码[请原谅无偿的样式清理]:

void
create_list(node * current, int data)
{
// NOTE/BUG: malloc is incorrect
#if 0
    node *head = (node *) malloc(sizeof(node *));
#else
    node *head = (node *) malloc(sizeof(node));
#endif

    head->data = data;
    head->next = NULL;
    current->next = head;
}

int
main()
{
// NOTE/BUG: malloc is incorrect
#if 0
    node *head = (node *) malloc(sizeof(node *));
#else
    node *head = (node *) malloc(sizeof(node));
#endif

// NOTE/BUG: to ensure list is well formed, do this:
    head->next = NULL;

    create_list(head,4);

// NOTE/BUG: this doesn't work because it always displays one _less_ than the
// number in the list, so with one element in the list, it displays nothing
#if 0
    node *temp = head;
    while (temp->next != NULL) {
        cout << temp->data;
        temp = temp->next;
    }
#else
    node *temp = head->next;
    while (temp != NULL) {
        cout << temp->data;
        temp = temp->next;
    }
#endif

    return 0;
}