C - 动态数组处理建议

Question

我目前正在学习 C，作为一个在更高级语言方面有相当多经验的人。

After considering some of your comments and doing a bit more testing and fidelling, I came up with a better solution (scroll down).

Advice and comments are still very welcome though.

就是说，我在 C 中的动态数组处理方面遇到了一些困难。我把它归结为一个我非常喜欢的点，只需用 NULL 终止每个数组并使用 realloc 必要时。

基本上我是在寻求建议:除了显而易见的(不能使用 NULL 值作为数据值)之外，这样做有什么缺点吗(请参阅下面的示例代码)？

#include "stdlib.h"

int array_length(void* array)
{
    int i;
    for (i = 0; ((void**)array)[i]; i++);
    return i;
}

void array_add(void* array, void* item)
{
    int size = array_length(array);
    realloc(array, sizeof(item) * (size + 2));

    ((void**)array)[size] = item;
    ((void**)array)[size + 1] = NULL;
}

void* array_new(){
    void** array = malloc(sizeof(NULL));
    array[0] = NULL;
    return array;
}

#include "stdio.h"

void print_items(char** array){
    printf("%i - [", array_length(array));
    for (int i = 0; array[i]; i++){
        printf("\"%s\"", array[i]);
        if (array[i+1])
            printf(", ");
    }
    printf("]\n");
}

int main(){
    char** str_list = array_new();

    print_items(str_list);
    array_add(str_list, "Something!");
    print_items(str_list);
    array_add(str_list, "Another Thing.");
    print_items(str_list);
}

更好的版本(更新!)

在阅读了您的答案并自己进行了更多调试之后，我想出了一个新版本，它主要基于下面提到的 struct 方法。

看看，然后告诉我，我现在做错了什么。 :)

#include "stdlib.h"
#include "assert.h"

typedef void* Any;

typedef struct {
    Any* items;
    int count;
} List;

List* list_new(){
    List* list = malloc(sizeof(List));
    list->items = NULL;
    list->count = 0;
    return list;
}

void list_add(List* list, Any element){
    int count = list->count + 1;
    list->items = realloc(list->items, count * sizeof(element));
    list->items[count-1] = element;
    list->count = count;
}

void list_free(List* list){
    if (list){
        if (list->items) free(list->items);
        free(list);
    }
}

void list_each(List* list, void (*callback)(List*, Any, int)){
    for (int i = 0; i < list->count; i++){
        callback(list, list->items[i], i);
    }
}

// Sample usage

#include "stdio.h"

void debug_item(List* list, Any item, int index){
    if(index > 0) printf(", ");
    printf("\"%s\"", item);
}

void debug(List* list){
    printf("%i : [", list->count);
    list_each(list, debug_item);
    printf("]\n");
}

int main(){
    List* cats = list_new();
    debug(cats);
    list_add(cats, "Baltazar");
    list_add(cats, "Scar");
    list_add(cats, "Garfield");
    debug(cats);
    list_free(cats);
}

Answer 1

您的 array_length 是 O(N)。如果您在数组中添加大量项目，这将导致二次运行时间，这可能会非常慢。

你可以做的是使用一个结构来存储数组的大小

struct dyn_array {
    size_t array_size; // how many elements fit in the array?
    size_t nelems;     // how much array space are we using now? 
    int *elems; //or void*, you know the drill...
}

这种方法的好处之一是您不再需要使用 NULL 终止符。它还允许您使用 int 数组(或其他任何内容)而不仅仅是指针数组。