Arraylist в C не работает - PullRequest
Новая
       36

Arraylist в C не работает

5 голосов
/ 17 сентября 2010

В настоящее время я пишу программу для реализации массива (или динамического массива) на языке C. Хмм ... Я думаю, что с этим покончено на 70 - 80%, однако я обнаружил серьезную проблему с моим кодом при тестировании ихна нескольких машинах.

Вкратце, я вставил группу строк (char *) в свой массив и попытался получить и отобразить их после нескольких операций.Тем не менее, вот что я получил: 

CHECK: 1
CHECK: 2
CHECK: ܗ¿èۗ¿
CHECK: EàEàHAÿE؉Ⱥ
CHECK: 5
CHECK: 6

К сожалению, я до сих пор не могу понять, где проблема в моих кодах, хотя я дважды просмотрел свои коды.

arraylist.h 

#ifndef _ARRAYLIST_H
#define _ARRAYLIST_H

#include <stdio.h>

typedef char* value_type;

struct arraylist {
  int size;
  value_type* data;
};

extern void arraylist_initial(struct arraylist *list);
extern int arraylist_get_size(const struct arraylist list);
extern value_type* arraylist_get_data_collection(const struct arraylist list);
extern void arraylist_set_data_collection(struct arraylist *list, value_type* data);
extern void arraylist_add(struct arraylist *list, value_type value);
extern value_type arraylist_get(const struct arraylist list, int index);
extern int arraylist_indexof(const struct arraylist list, value_type value);

#endif

arraylist.c 

#include "arraylist.h"

void arraylist_initial(struct arraylist *list) {
  list->size = 0;
  list->data = NULL;
}

int arraylist_get_size(const struct arraylist list) {
  return list.size;
}

value_type* arraylist_get_data_collection(const struct arraylist list) {
  return list.data;
}

void arraylist_set_data_collection(struct arraylist *list, value_type* data) {
  list->data = data;
}

void arraylist_add(struct arraylist *list, value_type value) {
  int size = arraylist_get_size(*list);
  value_type new_data[size + 1];

  int index = 0;
  for(; index != size; ++index) {
    new_data[index] = arraylist_get(*list, index);
  }
  new_data[index] = value;

  arraylist_set_data_collection(list, new_data);

  ++list->size;
}

value_type arraylist_get(const struct arraylist list, int index) {
  if(index < arraylist_get_size(list)) {
    return list.data[index];
  }
  else {
    return NULL;
  }
}

int arraylist_indexof(const struct arraylist list, value_type value) {
  int index = 0;
  for(; index != arraylist_get_size(list); ++index) {
    if(strcmp(list.data[index], value) == 0) {
      return index;
    }
  }

  return -1;
}

int main(void){
  struct arraylist list;

  arraylist_initial(&list);

  arraylist_add(&list, "1");
  arraylist_add(&list, "2");
  arraylist_add(&list, "3");
  arraylist_add(&list, "4");
  arraylist_add(&list, "5");
  arraylist_add(&list, "6");

  int index = 0;
  for(; index != 6; ++index) {
    printf("CHECK: %s\n", arraylist_get(list, index));
  }

  return 0;
}

Ответы [ 4 ]

7 голосов
/ 17 сентября 2010

Как уже отмечали другие, проблема заключается в функции arraylist_add(), которая должна динамически распределять память.Эта проблема на самом деле идеально подходит для realloc(), который расширяет динамически размещенный массив (то есть вам не нужно делать цикл копирования): 

void arraylist_add(struct arraylist *list, value_type value) {
  int size = arraylist_get_size(*list);
  value_type *new_data;

  new_data = realloc(list->data, (size + 1) * sizeof new_data[0]);

  if (new_data)
  {
      new_data[size] = value;
      arraylist_set_data_collection(list, new_data);
      ++list->size;
  }
}

Это будет работать даже при первом выделении,поскольку realloc() работает как malloc(), если вы передаете ему NULL.

PS:

Чтобы сделать реализацию более эффективной, расширять ее не следуетмассив по одной записи каждый раз - вместо этого отслеживайте количество выделенных блоков отдельно от количества записей.

2 голосов
/ 17 сентября 2010

В методе arraylist_add вы сохраняете адрес локальной переменной new_data в списке. Эта переменная будет уничтожена, как только элемент управления выйдет из функции. Следовательно, у вас есть недействительные указатели, которые при разыменовании вызывают неопределенное поведение. Чтобы решить эту проблему, вам нужно выделить память для строки из кучи, используя malloc, т.е. вам нужно сделать что-то вроде value_type* new_data = (value_type*)malloc( (size + 1) * sizeof(value_type));. Также помните, что вы должны освободить эту память самостоятельно, используя free.

1 голос
/ 17 сентября 2010

Корень вашей проблемы здесь: 

void arraylist_add(struct arraylist *list, value_type value) {
  int size = arraylist_get_size(*list);
  value_type new_data[size + 1];
  ...
  arraylist_set_data_collection(list, new_data);
  ...
  ++list->size;
}

new_data объявлено в стеке. Больше не безопасно использовать эту память после возврата вызова. Вам необходимо выделить место для данных с помощью malloc, например

1 голос
/ 17 сентября 2010

На первый взгляд: в arraylist_add вы объявляете new_data как локальную переменную.Когда вы передаёте это в arraylist_set_data_collection, он передает указатель на эти данные.Однако, как только arraylist_add вернется в main, new_data выйдет из области видимости и, следовательно, больше не будет действительным.

Рассмотрите возможность создания глубокой копии и обработки памяти вручную с помощью malloc и free.

...