使用c的堆栈推送功能，使用双向链表实现

debugcn 发表于 Dev

亚历克斯·阿布罗伊

我正在尝试使用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

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

来自莫斯科的弗拉德

该函数处理传递给它的指向头节点的指针的值的副本。因此，原始指针本身不会在函数中更改。它是在函数中更改的传递的指针的值的副本。

您需要按引用传递指针，该引用是间接通过指针传递给指针的。

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

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;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。