c - while循环链表中的段错误？

Question

我正在尝试在 C 中设置一个图表。我尝试了用户输入的图表，它工作得很好。但是，我正在尝试实现从文件读取。最后一个 else 语句是错误的来源，因为当我将其注释掉时，它编译时没有任何问题。我已经对我认为有问题的 block 添加了评论。如果此问题还需要任何其他信息，请告诉我。

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

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

//int counter and mainVertex would be used to determine if graph is connected.

// void graphConnection(){
// 
// 
// 
// 
// 
// 
// }


char* deblank(char* input)
{
    int i,j;
    char *output=input;
    for (i = 0, j = 0; i<strlen(input); i++,j++)
    {
        if (input[i]!=' ')
            output[j]=input[i];
        else
            j--;
    }
    output[j]=0;
    return output;
}


struct node *G[1000];
int counter = 0;
char *mainVertex;

void readingEachLine(){

  FILE * fp;
  char * line = NULL;
  size_t len = 0;
  ssize_t read;

  //Read file and exit if fail
  fp = fopen("test.txt", "r");
  if (fp == NULL)
      exit(EXIT_FAILURE);

  while ((read = getline(&line, &len, fp)) != -1) {
    line = deblank(line);
    int i = 0;
    struct node* cursor = malloc(sizeof(struct node));
    struct node* secondcursor = malloc(sizeof(struct node));
    struct node* tempitem;
    while(line[i] != '\n'){

      //If its the first of the line look into the array and set struct cursor to the corresponding
      //array position

      if (i == 0){
        mainVertex[counter] = line[0];
        int convertor = line[i] - '0';
        cursor = G[convertor];
        counter++;
      }
      //if its not the first, then set a struct with that number as data

      else{
        tempitem = malloc(sizeof(struct node));
        int convertor = line[i] - '0';
        tempitem->data = convertor;
        tempitem->next = NULL;
      }
      //if there is no element connected to the struct in array, connect the tempitem

      if (cursor->next == NULL){
        cursor->next = tempitem;
      }
      //If there are already connected elements, loop until the end of the linked list
      //and append the tempitem
      //ERROR: I GET SEGMENTATION FAULT FROM HERE. TRIED AFTER COMMENTING IT OUT

      else{
        secondcursor = cursor;
        while(secondcursor->next != NULL){
          secondcursor = secondcursor->next;
        }
        secondcursor->next = tempitem;
      }
      i++;
    }
    printf("\n");
  }
}

int main(void){
  for (int i = 1; i < 1000; i++)
  {
      G[i]= malloc(sizeof(struct node));
      G[i]->data = i;
      G[i]->next = NULL;
  }
  readingEachLine();
}

编辑:文本文件如下所示:

1 3 4
2 4
3 1 4
4 2 1 3

Answer 1

您的代码有几个错误选项:

• 显然，您最多可以有 1,000 个节点。您有一个包含 1,000 个指向链表的头指针的数组 G。不要一开始就为所有 1,000 个节点分配内存。一开始，所有链表都是空的，空链表是没有节点且头为NULL的链表。

• 在您的示例中，cursor 用于迭代现有的指针，因此不要为其分配内存。如果您有这样的代码:

  struct node *p = malloc(...);
  
  // next use of p:
  p = other_node;
  

  你不应该分配。您将覆盖 p 并丢失已分配内存的句柄。并非所有指针都必须使用 malloc 初始化；仅当您创建节点时才分配。

• 如果节点数量超过 9 个，那么从一行中去除所有空格然后解析单个数字的想法将会失败。 (但是您可以满足 1,000 个节点的需求。)不要尝试自己解析这些数字。有一些库函数可以实现这一点，例如 strtol。
• 尚不清楚 mainVertex 应该是什么。当您分配给它时，您只使用它一次。您将它视为一个数组，但它是一个全局指针，初始化为NULL。当您取消引用它时，您会得到未定义的行为，这可能是您的段错误的来源。

这是一个可以完成您想做的事情的程序。 (为了简单起见，它总是在头部插入节点，并且应该有更多的分配检查。)

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

enum {
    maxNodes = 1000
};

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

struct node *G[maxNodes];
size_t nnode = 0;

int read_graph(const char *fn)
{
    FILE * fp;
    char * line = NULL;
    size_t len = 0;

    fp = fopen(fn, "r");
    if (fp == NULL) return -1;

    while (getline(&line, &len, fp) != -1) {
        char *p;
        char *end;
        int id;
        int n;

        id = strtol(line, &end, 10);
        if (end == line) continue;

        if (id < 1 || id > maxNodes) break;

        if (id > nnode) nnode = id;
        id--;

        p = end;
        n = strtol(p, &end, 10);

        while (p != end) {
            struct node *nnew = malloc(sizeof(*nnew));

            nnew->data = n - 1;
            nnew->next = G[id];
            G[id] = nnew;

            p = end;
            n = strtol(p, &end, 10);
        }
    }

    fclose(fp);
    free(line);

    return 0;
}

int main(void)
{
    if (read_graph("test.txt") < 0) {
        fprintf(stderr, "Couldn't gread raph.\n");
        exit(1);
    }

    for (int i = 0; i < nnode; i++) {
        struct node *p = G[i];

        if (p) {
            printf("%d:", i + 1);

            for (; p; p = p->next) {
                printf(" %d", p->data + 1);
            }

            puts("");
        }
    }

    for (int i = 0; i < nnode; i++) {
        struct node *p = G[i];

        while (p) {
            struct node *old = p;

            p = p->next;
            free(old);
        }
    }

    return 0;
}