为什么遍历没有被打印？

Question

我用C语言编写了一个使用链表进行深度优先搜索的代码。我已经使用其中使用链表的堆栈实现。

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

struct node
{
    char data;
    struct node *next;
};

struct node *head = NULL;

struct edge {
    char data;
    struct edge *next;
};

struct vertex {
    char data;
    struct vertex *next;
    struct edge *enext;
};

void push(char item);
char pop();
bool isEmpty(struct node *head);
void printGraph(struct vertex *v);

int n; //no of vertices
char d; 

int main(void) 
{
    struct vertex *v = NULL;
    printf("Enter the no. of vertices: ");
    scanf("%d", &n);
    char status[2][n];
    printf("Enter the vertices of the graph: \n");
    char c;

    //getting the vertices
    for (int i = 0; i < n; i++) 
    {
        scanf(" %c", &c);
        struct vertex *new = malloc(sizeof(struct vertex));
        new->data = c;
        new->next = v;
        v = new;
    }

    printf("Press $ to stop for the particular vertex\n");
    struct vertex *ptr = v;
    for (int i = 0; i < n; i++)
    {
        printf("Enter the vertices with which the vertex %c forms an edge: \n", ptr->data);
        ptr->enext = NULL;
        char input;

        while(1) 
        {
            scanf(" %c", &input);

            if (input == '$') 
            {
                break;
            }

            //adding vertices to the edge list of the particular vertex
            struct edge *new = malloc(sizeof(struct edge));
            new->data = input;
            new->next = ptr->enext;
            ptr->enext = new;
        }
        ptr = ptr->next;
    }
    //graph made
    printGraph(v);

    //dfs
    for (int i = 0; i < n; i++) 
    {
        status[1][i] = '1';
    }

    struct vertex *pointer = v;

    for(int i = 0; i < n; i++) 
    {
        status[0][i] = pointer->data;
        pointer = pointer->next;
    }

    d = v->data;
    // push(d);
    push(d);
    status[1][0] = '2';

    while(!isEmpty(head))
    {
        char temp = pop();
        printf("%c ", temp);

        // updating status of popped element
        for (int i = 0; i < n; i++)
        {
            if (status[0][i] == temp)
            {
                status[1][i] = '3';
                break;
            }
        }

        //to find the popped elements' neighbours
        struct vertex *ptr = v;
        for (int j = 0; j < n; j++)
        {
            if (temp == ptr->data)
            {
                struct edge *ptr1 = ptr->enext;
                while (ptr != NULL) 
                {
                    for(int i = 0; i < n; i++) 
                    {
                        if(ptr->data == status[0][i])
                        {
                            if (status[1][i] == '1')
                            {
                                d = status[0][i];
                                push(d);
                                status[1][i] = '2';
                                break;
                            }
                        }
                    }
                    ptr1 = ptr1->next;
                }
            }
            ptr = ptr->next;
        }
    }
}

void push(char item)
{
    //create new node
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = item;

    //make the new node point to the head node
    newNode->next = head;

    //make the new node as head node
    //so that head will always point the last inserted data
    head = newNode;
    printf("Item inserted.\n");
}

char pop()
{
    //temp is used to free the head node
    //struct node *temp;

    if(head == NULL)
        printf("UNDERFLOW: Stack is Empty\n");
    else
    {
        
        char deletedItem = head->data;

        //make the head node point to the next node.
        //logically removing the node
        head = head->next;
        return deletedItem;
    }
}

void printGraph(struct vertex *v)
{
    struct vertex *ptr = v;
    for (int i = 0; i < n; i++)
    {
        printf("%c ------> ", ptr->data);
        struct edge *ptr1 = ptr->enext;
        while (ptr1 != NULL)
        {
            printf("%c", ptr1->data);
            printf("-->");
            ptr1 = ptr1->next;
        }
        printf("NULL\n");
        ptr = ptr->next;
    }
}

bool isEmpty(struct node *head)
{
    if (head == NULL)
    {
        return true;
    }
    return false;
}

输出：

Enter the no. of vertices: 2
Enter the vertices of the graph: 
b
a
Press $ to stop for the particular vertex
Enter the vertices with which the vertex a forms an edge:
b
$
Enter the vertices with which the vertex b forms an edge:
a
$
a ------> b-->NULL
b ------> a-->NULL
Item inserted.
a

为什么整个遍历没有被打印出来？我期望输出是这样的：

a b

，但它只是“a”。 我更新第一个元素的状态后是否有任何错误？ 帮助

Answer 1

说实话，我发现你用于找出弹出元素的邻居的图形 DFS 代码非常令人困惑。您是否已经使用您已经尝试过的输入来使用此代码遇到分段错误。

您可以尝试这个更简单的代码，它将适用于您给出的输入情况：

//to find the popped elements' neighbours
        struct vertex *ptr = v;

        while (ptr) {
            if (temp == ptr->data) break;
             ptr = ptr->next;
        }
        struct edge* edge_ptr = ptr->enext;

        while (edge_ptr) {
                for (int i = 0; i < n; i++)
                {
                    if (edge_ptr->data == status[0][i])
                    {
                        if (status[1][i] == '1') // not visited?
                        {
                            d = status[0][i];
                            push(d);
                            status[1][i] = '2'; //mark vertex pushed on stack?
                            break;
                        }
                    }
                }
                edge_ptr = edge_ptr->next;
        }