Блог

Итак, я пытаюсь запустить следующую программу, но когда я пытаюсь вставить значение в список пропусков, я получаю ошибку сегментации. Моя цель — вставить все значения в отсортированном списке пропусков.

  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", amp;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("asdasdn" );
  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 %dn", 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;
    }
  }
}
  

Записанная структура содержит только поле int с именем x. 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)
  

Что может вызвать это? Потому что, как кажется, я выделил каждый блок, к которому я собираюсь получить доступ. Максимальное значение равно 200, а максимальный уровень равен 20.

Это ваша ошибка:

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

Если я хочу вернуться назад, я обычно делаю это таким образом:

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

преимущество этого заключается в том, что первый доступ к массиву [i] не выходит за пределы массива. Это то, что обнаруживает здесь valgrind. Кроме того, таким образом, i может быть беззнаковым — в вашем коде он должен быть подписан, потому что в противном случае i >= 0 всегда будет true .