5

私は現在、C で arraylist (または動的配列) を実装するプログラムを書いています。うーん... 70 ～ 80% は完了したと思いますが、いくつかのテストでコードに深刻な問題が見つかりました。マシンの。

簡単に言うと、文字列のグループ ( char* ) を配列リストに挿入し、いくつかの操作を行った後にそれらを取得して表示しようとしました。しかし、これは私が得たものです：

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

残念ながら、コードを 2 回見直したにもかかわらず、コードのどこに問題があるのか​​ まだわかりません。

配列リスト.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

4 に答える 4

7

他の人が指摘したように、問題は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:

実装をより効率的にするには、配列を毎回 1 エントリずつ拡張するのではなく、割り当てられたブロックの数をエントリの数とは別に追跡します。

于 2010-09-17T05:50:17.077 に答える
2

メソッドではarraylist_add、ローカル変数のアドレスをnew_dataリストに格納しています。この変数は、コントロールが関数から出るとすぐに破棄されます。したがって、逆参照時に未定義の動作を呼び出す無効なポインターがあります。この問題を解決するには、を使用してヒープから文字列にメモリを割り当てる必要があります。mallocつまり、次のようなことを行う必要がありますvalue_type* new_data = (value_type*)malloc( (size + 1) * sizeof(value_type));。また、 を使用して自分でこのメモリの割り当てを解除する必要があることも覚えておいてくださいfree。

于 2010-09-17T05:39:14.250 に答える
1

あなたの問題の根本はここにあります：

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たとえば、データ用のスペースを割り当てる必要があります

于 2010-09-17T05:43:04.767 に答える
1

一見すると、arraylist_add では、new_data をローカル変数として宣言します。それをarraylist_set_data_collectionに渡すと、このデータへのポインターが渡されます。ただし、arraylist_add が main に戻ると、new_data は範囲外になり、有効ではなくなります。

ディープ コピーを実行し、malloc と free を使用してメモリを手動で処理することを検討してください。

于 2010-09-17T05:40:40.980 に答える