循环链表中的分段错误

Question

我正在编写插入循环链表的代码，但在第 110 行出现分段错误。我已经检查了代码，但无法找到分段错误的原因，该代码使用循环队列检查链表。如果匹配则打印正确，否则基于给定案例的输出

插入的代码是我有疑问的代码。

//-------------------- head of the code ------------------------

#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#define in(x) scanf(" %d", &x);
#define LinkedListNode LinkedListNode
typedef struct LinkedListNode LinkedListNode;
struct LinkedListNode {
  int val;
  struct LinkedListNode* next;
};


//-------------------- body of the code ------------------------

LinkedListNode* insertAtBeginning(LinkedListNode* tail, int val) {
  if(tail==NULL){
    tail->val = val;
    tail->next = tail;
  }
  else{
    LinkedListNode* p = (LinkedListNode*)malloc(sizeof(LinkedListNode));

    p->val = val;
    p->next = tail->next;
    tail->next = p;
  }

  return tail;
}

LinkedListNode* insertAtEnd(LinkedListNode* tail, int val) {
  if(tail==NULL){
    tail->val = val;
    tail->next = tail;
    return tail;
  }
  else{

    LinkedListNode* p = (LinkedListNode*)malloc(sizeof(LinkedListNode));

    p->val = val;
    p->next = tail->next;
    tail->next = p;
    tail = p;
    return tail;
  }

}


//-------------------- tail of the code ------------------------

int rng(int lim) {
  if (lim == 0) return 0;
  return rand()%lim;
}

int a[1005], sz = 0;
void insertt(int val, int pos) {
  if (pos < 0) return;
  if (pos > sz + 1) return;
  sz += 1;
  for (int i = sz; i > pos; i--)
  a[i] = a[i - 1];
  a[pos] = val;
}

void erasee(int pos) {
  if (pos > sz) return;
  if (pos < 1) return;
  sz--;
  for (int i = pos; i <= sz; i++)
  a[i] = a[i + 1];
}

int check(LinkedListNode* tail) {
  if (tail == NULL && sz == 0) return 1;
  if (tail == NULL || sz == 0) return 0;
  if (tail->val != a[sz]) return 0;
  LinkedListNode* ii = tail->next;
  for (int i = 1; i < sz; i++) {
    if (ii == NULL) return 0;
    if (a[i] != ii->val) return 0;
    ii = ii->next;
  }
  return 1;
}

int main() {
  srand(time(NULL));
  int t, n; in(t); in(n);
  while (t--) {
    LinkedListNode* head = NULL;
    sz = 0;
    for (int i = 0; i < n; i++) {
      int type = rng(4);
      if (type == 0) {
        int val = rng(1000);
        head = insertAtBeginning(head, val);
        insertt(val, 1);
        if (!check(head)) {
          printf("incorrect insertAtBeginning");
          return 0;
        }
      }

      if (type == 1) {
        int val = rng(1000);
        head = insertAtEnd(head, val);
        insertt(val, sz + 1);
        if (!check(head)) {
          printf("incorrect insertAtEnd");
          return 0;
        }
      }

    }
  }
  printf("correct");
}

我收到以下错误

Reading symbols from Solution...done.
[New LWP 83892]
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Core was generated by `./Solution'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0  insertAtEnd (val=<optimized out>, tail=0x0) at Solution.c:110

Answer 1

问题就在这里

if(tail==NULL){
    tail->val = val;
    tail->next = tail;
    return tail;
}

如果 tail 是一个空指针，你直接解引用这个空指针。这会导致 未定义的行为- 您仍然需要分配一个新节点。

insertAtEnd 和 insertAtBeginning 函数都有同样的问题。在 insertAtBeginning 函数中，出于某种原因，你有一个错误命名的 tail 变量（应该是 head 指针）。

另一个问题：

head = insertAtEnd(head, val);

您应该在此处传递（并分配给）tail 指针。但是你没有这样的指针。

Answer 2

if (tail == NULL)
    tail->val = val;

这不会有好下场。您正在取消引用空指针。

循环链表中的分段错误

Segmentation Fault in Circular Linked List

c

circular-list