Adrress是一個塊大小和adrees不是堆棧，malloc'd或free'd後0字節

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; 
    } 
    } 
} 

被recoding的結構只包含一個名爲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) 

這是什麼原因造成的？因爲看起來我已經分配了我要訪問的每個區塊。 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> = 0將永遠是真的。