C语言链表实现栈式DFS遍历未完整输出，请求排查问题

问题描述 #

用C语言实现基于链表栈的深度优先搜索（DFS），构建包含两个互连顶点a、b的图后，执行DFS遍历仅输出顶点a，预期输出为a b，需排查代码错误。

原代码 #

#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; // 顶点数量
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;

    // 读取顶点
    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;
            }

            // 为当前顶点添加邻接边
            struct edge *new = malloc(sizeof(struct edge));
            new->data = input;
            new->next = ptr->enext;
            ptr->enext = new;
        }
        ptr = ptr->next;
    }
    // 打印图结构
    printGraph(v);

    // DFS初始化
    for (int i = 0; i < n; i++) 
    {
        status[1][i] = '1'; // 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);
    status[1][0] = '2'; // 2表示已入栈

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

        // 更新弹出顶点的状态为已访问（3）
        for (int i = 0; i < n; i++)
        {
            if (status[0][i] == temp)
            {
                status[1][i] = '3';
                break;
            }
        }

        // 查找当前顶点的所有邻居
        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)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = item;
    newNode->next = head;
    head = newNode;
    printf("Item inserted.\n");
}

char pop()
{
    if(head == NULL)
        printf("UNDERFLOW: Stack is Empty\n");
    else
    {
        char deletedItem = head->data;
        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)
{
    return head == NULL;
}

运行输出 #

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 

错误分析与修复 #

1. 邻接边遍历循环条件错误 #

DFS模块中，查找当前顶点邻居时，错误地使用while (ptr != NULL)作为循环条件（ptr是当前顶点节点，不会为空），实际应遍历邻接边链表，使用ptr1作为循环指针，正确条件为while (ptr1 != NULL)。

2. 邻居顶点匹配错误 #

循环内部错误地用当前顶点的ptr->data匹配状态数组，实际应使用边节点的ptr1->data（邻居顶点的标识）来判断是否未访问。

3. Pop函数空栈返回值缺失 #

当栈为空时，pop()函数未返回有效数据，会导致未定义行为，需添加默认返回值。

修复后的核心代码片段 #

修改DFS中的邻居遍历逻辑：

// 查找当前顶点的所有邻居
struct vertex *ptr = v;
for (int j = 0; j < n; j++)
{
    if (temp == ptr->data)
    {
        struct edge *ptr1 = ptr->enext;
        // 修复：遍历邻接边链表
        while (ptr1 != NULL) 
        {
            for(int i = 0; i < n; i++) 
            {
                // 修复：匹配邻居顶点的标识
                if(ptr1->data == status[0][i])
                {
                    if (status[1][i] == '1')
                    {
                        d = status[0][i];
                        push(d);
                        status[1][i] = '2';
                        break;
                    }
                }
            }
            ptr1 = ptr1->next;
        }
        // 找到当前顶点后退出循环，无需继续遍历
        break;
    }
    ptr = ptr->next;
}

修改pop()函数添加空栈返回值：

char pop()
{
    if(head == NULL)
    {
        printf("UNDERFLOW: Stack is Empty\n");
        return '\0'; // 添加默认返回值
    }
    else
    {
        char deletedItem = head->data;
        head = head->next;
        return deletedItem;
    }
}

修复后的运行输出 #

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 Item inserted.
b 

内容的提问来源于stack exchange，提问作者ss511