c - 检查链表中的下一个节点时出错

Question

我正在尝试创建一个在图中创建 bfs 的程序。我创建了邻接矩阵和 bfs 函数。如果我输入一个小输入(例如 4 个节点)，该程序就可以工作，但如果我输入更大的输入，我就会开始出现段错误。

问题是，我并不总是把它放在同一个地方。每次我运行它时，它可能会在不同的迭代中崩溃，但肯定是在同一个循环中。这是我的代码:(我只是发布我认为与问题相关的函数，但如果您认为需要更多代码，请询问)。

void matrixBfs(int n, int matrix[n][n], Node nodeLocker[n], int source)
{
    int aux;
    Box* head =(Box*) malloc(sizeof(Box*));
    if (head == NULL)
    {
        printf("Memory failure\n");
    }
    head->next = NULL;

    add(head, source);
    nodeLocker[source].checked = 1;

    while (len(head) > 0)
    {
        aux = pop(head);

        for(int i=0; i<n; i++)
        {
            if ((matrix[aux][i]) && !(nodeLocker[i].checked))
            {
                add(head, i);
                nodeLocker[i].checked = 1;
            }
        }
    }
    head = NULL;
    free(head);
}

这是崩溃的函数，通过打印我已经确定崩溃在

while (len(head) > 0)

和

add(head, i);

声明。

这些功能是:

// Returns the length of the list.
int len(Box* head)
{
  int i = 0;
  Box* current = head;

  for(i; current->next != NULL; i++)
  {
    current = current-> next;
  }
  return i;
}

// Adds an element at the end of the list
void add(Box* head, int value)
{
  Box* current = head;

  while((current->next) != NULL)
  {
    current = (current->next);
  }

  Box* auxNode = (Box*) malloc(sizeof(Box*));

  if (auxNode == NULL)
  {
    printf("Memory failure\n");
  }
  auxNode->id = value;
  auxNode->next = NULL;

  current->next = auxNode;

}

再次，通过打印，我确定它们在检查链表的下一个节点时都会崩溃。也就是说，在

for(i; current->next != NULL; i++)

和

while((current->next) != NULL)

我很抱歉延长了我的问题，并且非常感谢您对此事的任何帮助。所以提前致谢。

编辑:这是完整的代码，以防需要:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Lists.c"


typedef struct Nodo
{
    int id;         // Representative value
    int checked;        // 0 if the node wasn't visited; and 1 if it was.
} Node;

void initializeLocker(int n, Node nodeLocker[n])
{
    for (int i=0; i < n; i++)
    {
        nodeLocker[i].id = i;
        nodeLocker[i].checked = 0;
    }
}

void matrixBfs(int n, int matrix[n][n], Node nodeLocker[n], int source)
{
    int aux;
    Box* head =(Box*) malloc(sizeof(Box*));
    if (head == NULL)
    {
        printf("Memory failure\n");
    }
    head->next = NULL;

    add(head, source);
    nodeLocker[source].checked = 1;

    while (len(head) > 0)
    {
        aux = pop(head);

        for(int i=0; i<n; i++)
        {
            if ((matrix[aux][i]) && !(nodeLocker[i].checked))
            {
                add(head, i);
                nodeLocker[i].checked = 1;
            }
        }
    }
    head = NULL;
    free(head);
}

int main()
{
  FILE* file = fopen("Input.in","r");
  char c[5];
  char* pch;
  int n;
  int num;
  int num2;

  fgets(c, 5, file);

  n = atoi(c);  // Number of nodes.

  if (n < 0)
  {
    printf("Must input at least one node");
    exit(1);
  }

  int matrix[n][n];

  // Initialization loop
  for (int i=0; i<n; i++)
  {
    for(int j=0; j<n; j++)
    {
        matrix[i][j] = 0;
    }
  }


  // Insertion loop.
  while(fgets(c, 5, file))
  {
    pch = strtok(c, " ");
    num = atoi(pch) - 1;
    pch = strtok(NULL, " ");
    num2 = atoi(pch) - 1;
    matrix[num][num2] = 1;
    matrix[num2][num] = 1;
  }

  fclose(file);             // No further use of the file.
  pch = NULL;
  free(pch);

  Node nodeLocker[n];

  initializeLocker(n, nodeLocker);

  matrixBfs(n, matrix, nodeLocker, 0);

  for (int i=0; i<n; i++)
  {
    if(nodeLocker[i].checked == 0)
    {
        printf("The entered graph has at least 1 node aislated. Please enter 
a new graph.");
        exit(1);
    }
  }

  initializeLocker(n, nodeLocker);
  nodeLocker[0].checked = 1;
  matrixBfs(n, matrix, nodeLocker, 1);

  for (int i=1; i<n; i++)
  {
    if (nodeLocker[i].checked == 0)
    {
        printf("%d is a linker agent.\n", 1);
        break;
    }
  }

  for (int i=1; i<n; i++)
  {
    initializeLocker(n, nodeLocker);
    nodeLocker[i].checked = 1;
    matrixBfs(n, matrix, nodeLocker, 0);

    for (int j=0; j<n; j++)
    {
        if (nodeLocker[j].checked == 0)
        {
            printf("%d is a linker agent.\n", i+1);
            break;
        }
    }
  }

  return 0;
}

“Box”结构在此文件中定义:

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

typedef struct Box
{
  int id;
  struct Box* next;
} Box;

// Adds an element at the end of the list.
void add(Box* head, int value)
{
  Box* current = head;
  Box* next = NULL;

  if (current != NULL)
  {
     next = current->next;
  }

  while(next != NULL)
  {
    current = next;
    next = current->next;
  }

  Box* auxNode = (Box*) malloc(sizeof(Box*));

  if (auxNode == NULL)
  {
    printf("Memory failure\n");
  }
  auxNode->id = value;
  auxNode->next = NULL;

  current->next = auxNode;

}

// Returns the length of the list
int len(Box* head)
{
 int i = 0;
 Box* current = head;
 Box* next = NULL;

 if (current != NULL)
 {
     next = current->next;
 }

 for(i; next != NULL; i++)
 {
    current = next;
    next = current-> next;
  }
  return i;
}

// Prints the entire list
void printLine(Box* head)
{
  if (head->next == NULL)
  {
    printf("The list is empty\n");
    return;
  }

  Box* current = head;

  current = current->next;
  printf("[%d", (current->id) + 1);

  while (current->next != NULL)
  {
    current = current->next;
    printf(", %d", (current->id) + 1);
  }

  printf("]\n");
}

// Deletes and returns the last element of the list
int pop(Box* head)
{
  Box* auxNode;
  int value;

  if (len(head) == 1)
  {
    auxNode = head->next;
    head->next = NULL;
    value = auxNode->id;
    auxNode = NULL;
    free(auxNode);
    return value;
  }

  Box* current = head;

  while (current->next->next != NULL)
  {
    current = current->next;
  }

  auxNode = current->next;
  value = current->next->id;
  current->next = NULL;
  auxNode = NULL;
  free(auxNode);
  return value;
}

最后，使用“Input.txt”文件输入输入内容。这里，第一行显示图的节点数，其余行显示它们之间的连接:

9
1 2
1 3
1 5
2 3
2 5
3 5
4 7
5 6
5 7
5 9
6 7
6 9
7 8
7 9
8 9

Answer 1

在导致段错误的两个语句中，您没有检查 current 是否为 NULL。相反，在 len 和 add 函数中使用类似的东西:

int len(Box* head)
{
  int i = 0;
  Box* current = head;
  Box* next = NULL;

  if (current != NULL) {
      next = current->next;
  }

  for(i; next != NULL; i++)
  {
    current = next;
    next = current-> next;
  }
  return i;
}


// Adds an element at the end of the list
void add(Box* head, int value)
{
  Box* current = head;
  Box* next = NULL;

  if (current != NULL) {
      next = current->next;
  }

  while(next != NULL)
  {
    current = next;
    next = current->next;
  }

  Box* auxNode = (Box*) malloc(sizeof(Box*));

  if (auxNode == NULL)
  {
    printf("Memory failure\n");
  }
  auxNode->id = value;
  auxNode->next = NULL;

  current->next = auxNode;

}