使用c的stack push函数，使用双向链表实现

Question

我正在尝试使用 C 实现 Hierholzer 算法。我已经为使用双向链表实现的简单堆栈创建了一个 push 函数，但指针总是移动到 else 条件，即使起始节点为空。

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<stddef.h>

typedef struct node
{
    int source;
    int num;
    struct node *l, *r;
    int done;
}node;

void push(int source, int num, struct node *head)
{
    node *n = malloc(sizeof(node));
    n->num = num;
    n->l = NULL;
    n->done = 0;
    n->source = source;

    if (*head == NULL)
    {
        head = n;
        head -> r = NULL;
    }
    else
    {
        n -> r = head;
        head->l = n;
        head = n;
    }
}

int pop(node *head)
{
    if(head == NULL)
    {
        return -1;
    }
    else
    {
        node *temp = head;
        head = head->r;
        int num = temp->num;
        free(temp);
        return num;
    }
}

void append(node *extra, node *head)
{
    node *temp = extra;
    while(temp->r != NULL)
    {
        temp = temp->r;
    }
    temp->r = head;
    head->l = temp;
    head = extra;
}

node** read(int num)
{
    char a[2000] = "Assignment1.txt" ,c[1000];


    FILE *f = fopen(a,"r");
    printf("Got file\n");

    node *adj[num];

    int i=0;
    node *l;
    printf("l: %d\n", l);

    while(fscanf(f,"%s",c))
    {

        char *p = strtok(c, ",");
        while(p!=NULL)
        {
            push(i, atoi(p), l);
            p = strtok (NULL, ",");
        }
        adj[i++] = l;
    }
    printf("Adjacency list created\n");

    return adj;
}

node* euler(node *adj[],int n, int i)
{
    node *cpath = NULL;
    node *fin = NULL;
    node *extra;
    node *temp = adj[i];
    node *tempi;

    while(temp!=NULL)
    {
        if(temp->r->r == NULL)
        {
            tempi = temp;
        }

        if(temp->done == 0)
        {
            temp->done = 1;
            push(i, temp->num, cpath);
            extra = euler(adj, n, temp->num);
            append(extra, cpath);
        }
        else
        {
            temp = temp->r;
        }
    }

    while(tempi->l != NULL)
    {
        push(i,tempi->num, fin);
        extra = euler(adj, n, tempi->num);
        append(tempi, fin);
        tempi = tempi->l;
    }
    if(tempi != NULL)
    {
        push(i,tempi->num, fin);
        extra = euler(adj, n, tempi->num);
        append(tempi, fin);
    }

    return fin;
}

int main()
{
    int n;
    printf("Enter the number of vertices: ");
    scanf("%d", &n);
    node **adj = read(n);
    node *fin = euler(adj, n, 0);
    node *temp = fin;

    while(temp!=NULL)
    {
        printf("%d ", temp->num);
        temp = temp->r;
    }

    return 0;
}

我还没有调试整个代码，但我卡在了 read() 函数，其中输入是一个 Assignment1.txt，其中包括：

2,3
3,1
1,2

我无法理解为什么会出现分段错误。

Answer 1

在读取函数中，您将返回 adj。但是，它是一个局部变量。您没有使用 malloc 类型的函数。因此，局部变量在函数返回后销毁。因此，当您尝试访问 main 中的 adj 时，您正在尝试访问一个随机位置。估计是这个原因导致的问题

Answer 2

该函数处理传递给它的指向头节点的指针值的副本。所以原来的指针本身在函数中并没有改变。它是函数内更改的传递指针值的副本。

您需要通过引用传递指针，即间接通过指针指向指针。

函数可以通过以下方式声明和定义。

int push( struct node **head, int source, int num )
{
    node *n = malloc(sizeof(node));
    int success = n != NULL;

    if ( success )
    {
        n->source = source;
        n->num    = num;
        n->done   = 0;
        
        n->l = NULL;
        n->r = *head;
        if ( *head != NULL ) ( *head )->l = n;

        *head = n;
    }

    return success;
}

使用c的stack push函数，使用双向链表实现

Stack push function using c, implemented using doubly linked list

c

stack

pointers

graph-theory

doubly-linked-list