c - 地址在大小块之后为 0 字节，adrees 未被堆栈、malloc 或释放

Question

所以我正在尝试运行以下程序，但是当我尝试在跳过列表中插入一个值时，出现了段错误。我的目标是将所有值插入排序的跳过列表中。

 int main(int argc, char const *argv[]) {
  int x;
  record *ptrs[5];
  int i;

  for ( i = 0; i < 5; i++) {
    ptrs[i] = malloc(sizeof(record));
  }
  node_ptr skip_list = creat_skip_list();

  for ( i = 0; i < 5; i++) {
    ptrs[i] = malloc(sizeof(record));
    scanf("%d", &x);
    ptrs[i] -> x = x;
    insert_skip_list(skip_list, x, ptrs[i]);

  }

我的跳过列表代码如下。

    #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "skip_list.h"
#include "test_strc.h"  

typedef struct node {
  int key;
  record *ptr;
  node_ptr forward[MaxLevel];
} node;


node_ptr creat_skip_list() {
  node_ptr head;
  node_ptr last;
  int i;

  head=malloc(sizeof(node));
  last=malloc(sizeof(node));

  for ( i = 0; i < MaxLevel; i++) {
    head->forward[i]=last;
    last->forward[i]=NULL;
  }
  head->ptr = malloc(sizeof(record));
  last->ptr = malloc(sizeof(record));
  last->key=MaxValue+1;
  return head;
};


int randomLevel() {
  srand(time(NULL));
  return rand()%(MaxLevel-1);
}

node_ptr makeNode (int lvl, int searchKey, record* newValue) {
  node_ptr temp = malloc(sizeof(node));
  temp->key = searchKey;
  temp -> ptr = newValue;
  return temp;
}


void insert_skip_list(node_ptr head,int searchKey, record* newValue) {
  printf("asdasd\n" );
  node_ptr update[MaxLevel];
  node_ptr temp=head;
  int i;
  for ( i = MaxLevel; i >= 0; i--) {
    while (temp->forward[i]->key < searchKey) {
      temp=temp->forward[i];
    }
    update[i]=temp;
  }
  temp=temp->forward[0];
  if (temp->key==searchKey)
    temp->ptr = newValue;  
  else {
    int lvl=randomLevel();
    printf("lvl is %d\n", lvl);
    temp=makeNode(lvl,searchKey,newValue); //creates node
    for ( i = 0; i < lvl; i++) {
      temp->forward[i] = update[i]->forward[i];
      update[i]->forward[i] = temp;
    }
  }
}

recored 结构只包含一个名为 x 的 int 字段。 Valgrind 给我以下消息

 ==5124== Invalid read of size 8
==5124==    at 0x400A25: insert_skip_list (skip_list.c:55)
==5124==    by 0x4007E0: main (test_skip.c:23)
==5124==  Address 0x51e02d0 is 0 bytes after a block of size 176 alloc'd
==5124==    at 0x4C28C20: malloc (vg_replace_malloc.c:296)
==5124==    by 0x400898: creat_skip_list (skip_list.c:20)
==5124==    by 0x400766: main (test_skip.c:16)
==5124== 
==5124== Invalid read of size 4
==5124==    at 0x400A29: insert_skip_list (skip_list.c:55)
==5124==    by 0x4007E0: main (test_skip.c:23)
==5124==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==5124== 
==5124== 
==5124== Process terminating with default action of signal 11 (SIGSEGV)
==5124==  Access not within mapped region at address 0x0
==5124==    at 0x400A29: insert_skip_list (skip_list.c:55)
==5124==    by 0x4007E0: main (test_skip.c:23)

什么会导致这种情况？因为看起来我已经分配了我要访问的每个 block 。 MaxValue 为 200，MaxLevel 为 20。

Answer 1

这是你的错误:

for ( i = MaxLevel; i >= 0; i--) {
    while (temp->forward[i]->key < searchKey) {

如果我想倒退，我通常这样做:

for (i = MaxLevel; i--; ) {

这样做的好处是，array[i] 的第一次访问不会超出数组范围。这就是 valgrind 在这里检测到的。另外，这样 i 可以是未签名的 - 在您的代码中，它必须被签名，否则 i >= 0 将始终为真。