C 动态增长数组

Question

我有一个程序可以读取游戏中实体的“原始”列表，并且我打算创建一个数组来保存不确定数量的实体的索引号（int），以处理各种事物。我想避免使用太多的内存或 CPU 来保存此类索引...

到目前为止，我使用的一个快速而肮脏的解决方案是在主处理函数（本地焦点）中声明具有最大游戏实体大小的数组，以及另一个整数来跟踪已添加到列表中的数量。 这并不令人满意，因为每个列表都包含 3000 多个数组，虽然不算多，但感觉有点浪费，因为我可能会使用 6-7 个列表的解决方案来实现不同的功能。

我还没有找到任何 C（不是 C++ 或 C#）特定的解决方案来实现此目的。我可以使用指针，但我有点害怕使用它们（除非这是唯一可能的方法）。

数组不会离开本地函数作用域（它们将被传递给函数，然后被丢弃），以防发生变化。

如果指针是唯一的解决方案，我如何跟踪它们以避免泄漏？

Answer 1

我可以使用指针，但我有点害怕使用它们。

如果您需要动态数组，则无法转义指针。你为什么害怕呢？它们不会咬人（只要你小心）。 C 中没有内置的动态数组，您只需自己编写一个。在 C++ 中，您可以使用内置的 std::vector 类。 C# 和几乎所有其他高级语言也有一些类似的类来为您管理动态数组。

如果您确实打算编写自己的数组，可以从这里开始：大多数动态数组实现都是从某个（小）默认大小的数组开始工作的，然后每当添加新元素时空间不足时，将数组的大小。正如您在下面的示例中看到的，这根本不是很困难：（为了简洁起见，我省略了安全检查）

typedef struct {
  int *array;
  size_t used;
  size_t size;
} Array;

void initArray(Array *a, size_t initialSize) {
  a->array = malloc(initialSize * sizeof(int));
  a->used = 0;
  a->size = initialSize;
}

void insertArray(Array *a, int element) {
  // a->used is the number of used entries, because a->array[a->used++] updates a->used only *after* the array has been accessed.
  // Therefore a->used can go up to a->size 
  if (a->used == a->size) {
    a->size *= 2;
    a->array = realloc(a->array, a->size * sizeof(int));
  }
  a->array[a->used++] = element;
}

void freeArray(Array *a) {
  free(a->array);
  a->array = NULL;
  a->used = a->size = 0;
}

使用它也很简单：

Array a;
int i;

initArray(&a, 5);  // initially 5 elements
for (i = 0; i < 100; i++)
  insertArray(&a, i);  // automatically resizes as necessary
printf("%d\n", a.array[9]);  // print 10th element
printf("%d\n", a.used);  // print number of elements
freeArray(&a);

Answer 2

一种简单的解决方案涉及 mmap。如果您可以容忍 POSIX 解决方案，那么这非常棒。只需映射整个页面并防止溢出，因为 realloc 对于此类值无论如何都会失败。现代操作系统不会承诺全部，直到您使用它，并且您可以根据需要截断文件。

或者，还有realloc。就像所有一开始看起来比后来更可怕的事情一样，克服最初的恐惧的最好方法就是让自己沉浸在未知的不适中！毕竟，有时候我们学到的东西最多。

不幸的是，存在局限性。例如，当您仍在学习使用函数时，您不应该扮演老师的角色。我经常阅读那些看似不知道如何使用realloc（即当前接受的答案！）的人的答案，告诉其他人如何错误地使用它，有时是在幌子下他们忽略了错误处理，尽管这是一个需要提及的常见陷阱。 这是一个解释如何正确使用 realloc 的答案。 请注意，答案是将返回值存储到不同的变量中，以便执行错误检查。

每次调用函数以及每次使用数组时，你正在使用一个指针。这些转换是隐式发生的，如果有的话应该更可怕，因为我们看不到的东西往往会导致最多的问题。例如，内存泄漏...

数组运算符是指针运算符。 array[x] 实际上是 *(array + x) 的缩写，它可以分解为：* 和 (数组+x）。很可能 * 令您感到困惑。我们可以通过假设 x 为 0 来进一步消除问题中的加法，因此，array[0] 变为 *array< /code> 因为添加 0 不会改变值......

因此我们可以看到 *array 相当于 array[0]。您可以在想要使用另一个的地方使用一个，反之亦然。数组运算符是指针运算符。

malloc、realloc 和朋友们并没有发明您一直在使用的指针概念；他们只是使用它来实现一些其他功能，这是一种不同形式的存储持续时间，最适合当您希望大小发生剧烈的动态变化时。

遗憾的是，目前接受的答案也违背了StackOverflow 上的其他一些非常有根据的建议，同时，错过了介绍一个鲜为人知的功能的机会，该功能正是针对此用例而闪耀的：灵活的数组成员！这实际上是一个相当糟糕的答案...:(

当您定义结构时，请在结构的末尾声明您的数组，而不需要任何例如：

struct int_list {
    size_t size;
    int value[];
};

这将允许您将 int 数组合并到与 count 相同的分配中，并且像这样绑定它们可能非常方便！

sizeof (struct int_list) 的作用就好像 value 的大小为 0，因此它会告诉您结构的大小对于空列表，您仍然需要添加传递给 realloc 的大小来指定列表的大小。

另一个方便的提示是记住 realloc(NULL, x)。 ) 相当于 malloc(x)，我们可以用它来简化我们的代码，例如：

int push_back(struct int_list **fubar, int value) {
    size_t x = *fubar ? fubar[0]->size : 0
         , y = x + 1;

    if ((x & y) == 0) {
        void *temp = realloc(*fubar, sizeof **fubar
                                   + (x + y) * sizeof fubar[0]->value[0]);
        if (!temp) { return 1; }
        *fubar = temp; // or, if you like, `fubar[0] = temp;`
    }

    fubar[0]->value[x] = value;
    fubar[0]->size = y;
    return 0;
}

struct int_list *array = NULL;

我选择使用 struct int_list ** 的原因。因为第一个参数可能看起来并不明显，但如果您考虑第二个参数，那么在 push_back 中对 value 所做的任何更改对于我们的函数来说都是不可见的是从哪里打来的，对吗？第一个参数也是如此，我们需要能够修改我们的数组，不仅仅是这里，而且也可能在我们传递的任何其他函数中它到...

array开始时什么都没有指向；这是一个空列表。 初始化与添加它相同。例如：

struct int_list *array = NULL;
if (!push_back(&array, 42)) {
    // success!
}

PS 完成后记得free(array);！

Answer 3

我能想到几个选择。

1. 链接列表。您可以使用链表来制作动态增长的数组之类的东西。但是，如果不先遍历 1-99，就无法执行 array[100]。而且您使用起来可能不太方便。
2. 大阵。只需创建一个具有足够空间的数组来容纳所有
3. 调整数组大小的内容。一旦知道大小，就重新创建数组，和/或每次用完空间并留出一些余量时，创建一个新数组，并将所有数据复制到新数组。
4. 链表数组组合。只需使用固定大小的数组，一旦空间不足，创建一个新数组并链接到该数组（明智的做法是跟踪该数组以及指向结构中下一个数组的链接）。

很难说哪种选择最适合您的情况。简单地创建一个大数组当然是最简单的解决方案之一，并且不会给您带来太多问题，除非它真的很大。

Answer 4

基于 Matteo Furlans 设计，当他说“大多数动态数组实现都是从某个（小）默认大小的数组开始工作的，然后每当添加新数组时空间不足时元素，数组大小的两倍”。下面的“正在进行的工作”的不同之处在于它的大小不会加倍，它的目标是仅使用所需的内容。为了简单起见，我还省略了安全检查...同样基于 brimboriums 想法，我尝试向代码添加删除功能...

看起来像这样...

#ifndef STORAGE_H
#define STORAGE_H

#ifdef __cplusplus
extern "C" {
#endif

    typedef struct 
    {
        int *array;
        size_t size;
    } Array;

    void Array_Init(Array *array);
    void Array_Add(Array *array, int item);
    void Array_Delete(Array *array, int index);
    void Array_Free(Array *array);

#ifdef __cplusplus
}
#endif

#endif /* STORAGE_H */

storage.h文件 storage.c 文件看起来像这样...

#include <stdio.h>
#include <stdlib.h>
#include "storage.h"

/* Initialise an empty array */
void Array_Init(Array *array) 
{
    int *int_pointer;

    int_pointer = (int *)malloc(sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to allocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer; 
        array->size = 0;
    }
}

/* Dynamically add to end of an array */
void Array_Add(Array *array, int item) 
{
    int *int_pointer;

    array->size += 1;

    int_pointer = (int *)realloc(array->array, array->size * sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to reallocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer;
        array->array[array->size-1] = item;
    }
}

/* Delete from a dynamic array */
void Array_Delete(Array *array, int index) 
{
    int i;
    Array temp;
    int *int_pointer;

    Array_Init(&temp);

    for(i=index; i<array->size; i++)
    {
        array->array[i] = array->array[i + 1];
    }

    array->size -= 1;

    for (i = 0; i < array->size; i++)
    {
        Array_Add(&temp, array->array[i]);
    }

    int_pointer = (int *)realloc(temp.array, temp.size * sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to reallocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer; 
    } 
}

/* Free an array */
void Array_Free(Array *array) 
{
  free(array->array);
  array->array = NULL;
  array->size = 0;  
}

main.c 看起来像这样...

#include <stdio.h>
#include <stdlib.h>
#include "storage.h"

int main(int argc, char** argv) 
{
    Array pointers;
    int i;

    Array_Init(&pointers);

    for (i = 0; i < 60; i++)
    {
        Array_Add(&pointers, i);        
    }

    Array_Delete(&pointers, 3);

    Array_Delete(&pointers, 6);

    Array_Delete(&pointers, 30);

    for (i = 0; i < pointers.size; i++)
    {        
        printf("Value: %d Size:%d \n", pointers.array[i], pointers.size);
    }

    Array_Free(&pointers);

    return (EXIT_SUCCESS);
}

期待接下来的建设性批评...

Answer 5

当你说

创建一个数组，保存不确定数量的实体的索引号（int）

，您基本上是在说您正在使用“指针”，但它是数组范围的本地指针而不是内存范围的指针。既然你在概念上已经在使用“指针”（即引用数组中元素的id号），为什么不只使用常规指针（即引用最大数组中元素的id号：整个内存） ）。

您可以让对象存储指针，而不是存储资源 ID 号。基本上是同样的事情，但效率更高，因为我们避免将“数组+索引”变成“指针”。

如果您将指针视为整个内存的数组索引（这就是它们的实际情况），那么指针并不可怕

Answer 6

创建任何类型的无限项目的数组：

typedef struct STRUCT_SS_VECTOR {
    size_t size;
    void** items;
} ss_vector;


ss_vector* ss_init_vector(size_t item_size) {
    ss_vector* vector;
    vector = malloc(sizeof(ss_vector));
    vector->size = 0;
    vector->items = calloc(0, item_size);

    return vector;
}

void ss_vector_append(ss_vector* vec, void* item) {
    vec->size++;
    vec->items = realloc(vec->items, vec->size * sizeof(item));
    vec->items[vec->size - 1] = item;
};

void ss_vector_free(ss_vector* vec) {
    for (int i = 0; i < vec->size; i++)
        free(vec->items[i]);

    free(vec->items);
    free(vec);
}

以及如何使用它：

// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT {
    int id;
} apple;

apple* init_apple(int id) {
    apple* a;
    a = malloc(sizeof(apple));
    a-> id = id;
    return a;
};


int main(int argc, char* argv[]) {
    ss_vector* vector = ss_init_vector(sizeof(apple));

    // inserting some items
    for (int i = 0; i < 10; i++)
        ss_vector_append(vector, init_apple(i));


    // dont forget to free it
    ss_vector_free(vector);

    return 0;
}

此向量/数组可以容纳任何类型的项目，并且大小完全动态。

Answer 7

好吧，我想如果您需要删除一个元素，您将复制一个数组，忽略要排除的元素。

// inserting some items
void* element_2_remove = getElement2BRemove();

for (int i = 0; i < vector->size; i++){
       if(vector[i]!=element_2_remove) copy2TempVector(vector[i]);
       }

free(vector->items);
free(vector);
fillFromTempVector(vector);
//

假设 getElement2BRemove()、copy2TempVector( void* ...) 和 fillFromTempVector(...) 是处理临时向量的辅助方法。

Answer 8

这些帖子的顺序显然是错误的！这是系列 3 篇文章中的第 1 篇。对不起。

在尝试使用 Lie Ryan 的代码时，我在检索存储的信息时遇到了问题。向量的元素不是连续存储的，正如您通过“作弊”一点并将指针存储到每个元素的地址（这当然违背了动态数组概念的目的）并检查它们所看到的那样。

通过一些修补，via：

ss_vector* vector; // pull this out to be a global vector

// Then add the following to attempt to recover stored values.

int return_id_value(int i,apple* aa) // given ptr to component,return data item
{   printf("showing apple[%i].id = %i and  other_id=%i\n",i,aa->id,aa->other_id);
    return(aa->id);
}

int Test(void)  // Used to be "main" in the example
{   apple* aa[10]; // stored array element addresses
    vector = ss_init_vector(sizeof(apple));
    // inserting some items
    for (int i = 0; i < 10; i++)
    {   aa[i]=init_apple(i);
        printf("apple id=%i and  other_id=%i\n",aa[i]->id,aa[i]->other_id);
        ss_vector_append(vector, aa[i]);
     }   
 // report the number of components
 printf("nmbr of components in vector = %i\n",(int)vector->size);
 printf(".*.*array access.*.component[5] = %i\n",return_id_value(5,aa[5]));
 printf("components of size %i\n",(int)sizeof(apple));
 printf("\n....pointer initial access...component[0] = %i\n",return_id_value(0,(apple *)&vector[0]));
 //.............etc..., followed by
 for (int i = 0; i < 10; i++)
 {   printf("apple[%i].id = %i at address %i, delta=%i\n",i,    return_id_value(i,aa[i]) ,(int)aa[i],(int)(aa[i]-aa[i+1]));
 }   
// don't forget to free it
ss_vector_free(vector);
return 0;
}

只要您知道每个数组元素的地址，就可以毫无问题地访问每个数组元素，所以我想我会尝试添加一个“下一个”元素并将其用作链接列表。当然还有更好的选择。请指教。

Answer 9

这些帖子的顺序显然是错误的！这是 3 篇文章系列中的第 3 篇文章。对不起。

我对 Lie Ryan 的代码“采取了更多的自由”。诚然，访问单个链接列表非常耗时
由于搜索开销而导致的元素，即沿着列表查找直到找到正确的元素。我现在已经治愈了这个问题
维护一个包含下标 0 到与内存地址配对的地址向量。这有效
因为地址向量是一次性分配的，因此在内存中是连续的。由于不再需要链表，
我已经撕掉了它的相关代码和结构。

这种方法不如简单的静态数组那么有效，但至少您不必“遍历列表”
寻找合适的物品。您现在可以使用下标访问元素。为了实现这一点，我已经
添加代码来处理元素被删除并且“实际”下标不会反映在
指针向量的下标。这对于用户来说可能重要也可能不重要。对我来说，这很重要，所以
我已经将下标的重新编号设置为可选。如果不使用重新编号，程序流程将进入虚拟流程
“missing”元素返回一个错误代码，用户可以选择忽略该错误代码或根据需要采取行动。

从这里开始，我建议用户对“元素”部分进行编码以满足他们的需求并确保其正确运行。如果你的
添加的元素是数组，仔细编写子例程来访问它们，看看如何有额外的数组结构
静态数组不需要这样做。享受！

#include <glib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>


// Code from https://stackoverflow.com/questions/3536153/c-dynamically-growing-array
// For pointer-to-pointer info see:
// https://stackoverflow.com/questions/897366/how-do-pointer-to-pointers-work-in-c-and-when-might-you-use-them
typedef struct STRUCT_SS_VECTOR
{   size_t size; // # of vector elements
    void** items; // makes up one vector element's component contents
    int subscript; // this element's subscript nmbr, 0 thru whatever
 //   struct STRUCT_SS_VECTOR* this_element; // linked list via this ptr
 //   struct STRUCT_SS_VECTOR* next_element; // and next ptr
} ss_vector;

ss_vector* vector; // ptr to vector of components
ss_vector* missing_element(int subscript) // intercepts missing elements
{   printf("missing element at subscript %i\n",subscript);
    return NULL;
}

typedef struct TRACKER_VECTOR
{   int subscript;
    ss_vector* vector_ptr;
} tracker_vector;  // up to 20 or so, max suggested

tracker_vector* tracker;
int max_tracker=0; // max allowable # of elements in "tracker_vector"
int tracker_count=0; // current # of elements in "tracker_vector"
int tracker_increment=5; // # of elements to add at each expansion

void bump_tracker_vector(int new_tracker_count)
{   //init or lengthen tracker vector
    if(max_tracker==0) // not yet initialized
    { tracker=calloc(tracker_increment, sizeof(tracker_vector));
        max_tracker=tracker_increment;
printf("initialized %i-element tracker vector of size %lu at %lu\n",max_tracker,sizeof(tracker_vector),(size_t)tracker);
        tracker_count++;
        return;
    }
    else if (max_tracker<=tracker_count) // append to existing tracker vector by writing a new one, copying old one
    {   tracker_vector* temp_tracker=calloc(max_tracker+tracker_increment,sizeof(tracker_vector));  
        for(int i=0;(i<max_tracker);i++){   temp_tracker[i]=tracker[i];} // copy old tracker to new
        max_tracker=max_tracker+tracker_increment;
        free(tracker);
        tracker=temp_tracker;
printf("  re-initialized %i-element tracker vector of size %lu at %lu\n",max_tracker,sizeof(tracker_vector),(size_t)tracker);
        tracker_count++;
        return;
    } // else if
    // fall through for most "bumps"
    tracker_count++;
    return;
}  // bump_tracker_vector()

ss_vector* ss_init_vector(size_t item_size) // item_size is size of one array member
{   ss_vector* vector= malloc(sizeof(ss_vector)); 
    vector->size = 0; // initialize count of vector component elements
    vector->items = calloc(1, item_size); // allocate & zero out memory for one linked list element
    vector->subscript=0;
    bump_tracker_vector(0); // init/store the tracker vector
    tracker[0].subscript=0;
    tracker[0].vector_ptr=vector; 
    return vector; //->this_element;
} // ss_init_vector()

ss_vector* ss_vector_append( int i) // ptr to this element, element nmbr
{   ss_vector* local_vec_element=0;
    local_vec_element= calloc(1,sizeof(ss_vector)); // memory for one component
    local_vec_element->subscript=i; //vec_element->size; 
    local_vec_element->size=i; // increment # of vector components
    bump_tracker_vector(i);  // increment/store tracker vector
    tracker[i].subscript=i;
    tracker[i].vector_ptr=local_vec_element; //->this_element;
    return local_vec_element;
}  // ss_vector_append()

void bubble_sort(void)
{   //  bubble sort
    struct TRACKER_VECTOR local_tracker;
    int i=0;
    while(i<tracker_count-1)
    {   if(tracker[i].subscript>tracker[i+1].subscript)
        {   local_tracker.subscript=tracker[i].subscript; // swap tracker elements
            local_tracker.vector_ptr=tracker[i].vector_ptr;
            tracker[i].subscript=tracker[i+1].subscript;
            tracker[i].vector_ptr=tracker[i+1].vector_ptr;
            tracker[i+1].subscript=local_tracker.subscript;
            tracker[i+1].vector_ptr=local_tracker.vector_ptr;
            if(i>0) i--; // step back and go again
        }
        else 
        {   if(i<tracker_count-1) i++;
        }
    } // while()
} // void bubble_sort()

void move_toward_zero(int target_subscript) // toward zero
{   struct TRACKER_VECTOR local_tracker;
    // Target to be moved must range from 1 to max_tracker
    if((target_subscript<1)||(target_subscript>tracker_count)) return; // outside range
    // swap target_subscript ptr and target_subscript-1 ptr
    local_tracker.vector_ptr=tracker[target_subscript].vector_ptr;
    tracker[target_subscript].vector_ptr=tracker[target_subscript-1].vector_ptr;
    tracker[target_subscript-1].vector_ptr=local_tracker.vector_ptr;
}

void renumber_all_subscripts(gboolean arbitrary)
{   // assumes tracker_count has been fixed and tracker[tracker_count+1]has been zeroed out
    if(arbitrary)  // arbitrary renumber, ignoring "true" subscripts
    {   for(int i=0;i<tracker_count;i++) 
        {   tracker[i].subscript=i;}
    }
    else // use "true" subscripts, holes and all
    {   for(int i=0;i<tracker_count;i++) 
        {   if ((size_t)tracker[i].vector_ptr!=0) // renumbering "true" subscript tracker & vector_element
            {   tracker[i].subscript=tracker[i].vector_ptr->subscript;}
            else // renumbering "true" subscript tracker & NULL vector_element
            {   tracker[i].subscript=-1;}
        } // for()
        bubble_sort(); 
    } // if(arbitrary) ELSE
} // renumber_all_subscripts()

void collapse_tracker_higher_elements(int target_subscript)
{   // Fix tracker vector by collapsing higher subscripts toward 0.
    //  Assumes last tracker element entry is discarded.
    int j;
    for(j=target_subscript;(j<tracker_count-1);j++)
    {   tracker[j].subscript=tracker[j+1].subscript;
        tracker[j].vector_ptr=tracker[j+1].vector_ptr;
    }
    // Discard last tracker element and adjust count
    tracker_count--;
    tracker[tracker_count].subscript=0;
    tracker[tracker_count].vector_ptr=(size_t)0;
} // void collapse_tracker_higher_elements()

void ss_vector_free_one_element(int target_subscript, gboolean Keep_subscripts) 
{   // Free requested element contents.
    //      Adjust subscripts if desired; otherwise, mark NULL.
    // ----special case: vector[0]
    if(target_subscript==0) // knock out zeroth element no matter what
    {   free(tracker[0].vector_ptr);} 
    // ----if not zeroth, start looking at other elements
    else if(tracker_count<target_subscript-1)
    {   printf("vector element not found\n");return;}
    // Requested subscript okay. Freeit. 
    else
    {   free(tracker[target_subscript].vector_ptr);} // free element ptr
    // done with removal.
    if(Keep_subscripts) // adjust subscripts if required.
    {   tracker[target_subscript].vector_ptr=missing_element(target_subscript);} // point to "0" vector
    else // NOT keeping subscripts intact, i.e. collapsing/renumbering all subscripts toward zero
    {   collapse_tracker_higher_elements(target_subscript);
        renumber_all_subscripts(TRUE); // gboolean arbitrary means as-is, FALSE means by "true" subscripts
    } // if (target_subscript==0) else
// show the new list
// for(int i=0;i<tracker_count;i++){printf("   remaining element[%i] at %lu\n",tracker[i].subscript,(size_t)tracker[i].vector_ptr);}
} // void ss_vector_free_one_element()

void ss_vector_free_all_elements(void) 
{   // Start at "tracker[0]". Walk the entire list, free each element's contents, 
    //      then free that element, then move to the next one.
    //      Then free the "tracker" vector.
    for(int i=tracker_count;i>=0;i--) 
    {   // Modify your code to free vector element "items" here
        if(tracker[i].subscript>=0) free(tracker[i].vector_ptr);
    }
    free(tracker);
    tracker_count=0;
} // void ss_vector_free_all_elements()

// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT
{   int id; // one of the data in the component
    int other_id; // etc
    struct APPLE_STRUCT* next_element;
} apple; // description of component

apple* init_apple(int id) // make a single component
{   apple* a; // ptr to component
    a = malloc(sizeof(apple)); // memory for one component
    a->id = id; // populate with data
    a->other_id=id+10;
    a->next_element=NULL;
    // don't mess with aa->last_rec here
    return a; // return pointer to component
}

int return_id_value(int i,apple* aa) // given ptr to component, return single data item
{   printf("was inserted as apple[%i].id = %i     ",i,aa->id);
    return(aa->id);
}

ss_vector* return_address_given_subscript(int i) 
{   return tracker[i].vector_ptr;} 

int Test(void)  // was "main" in the example
{   int i;
    ss_vector* local_vector;
    local_vector=ss_init_vector(sizeof(apple)); // element "0"
    for (i = 1; i < 10; i++) // inserting items "1" thru whatever
    {local_vector=ss_vector_append(i);}   // finished ss_vector_append()
    // list all tracker vector entries
    for(i=0;(i<tracker_count);i++) {printf("tracker element [%i] has address %lu\n",tracker[i].subscript, (size_t)tracker[i].vector_ptr);}
    // ---test search function
    printf("\n NEXT, test search for address given subscript\n");
    local_vector=return_address_given_subscript(5);
printf("finished return_address_given_subscript(5) with vector at %lu\n",(size_t)local_vector);
    local_vector=return_address_given_subscript(0);
printf("finished return_address_given_subscript(0) with vector at %lu\n",(size_t)local_vector);
    local_vector=return_address_given_subscript(9);
printf("finished return_address_given_subscript(9) with vector at %lu\n",(size_t)local_vector);
    // ---test single-element removal
    printf("\nNEXT, test single element removal\n");
    ss_vector_free_one_element(5,TRUE); // keep subscripts; install dummy error element
printf("finished ss_vector_free_one_element(5)\n");
    ss_vector_free_one_element(3,FALSE);
printf("finished ss_vector_free_one_element(3)\n");
    ss_vector_free_one_element(0,FALSE);
    // ---test moving elements
printf("\n Test moving a few elements up\n");
    move_toward_zero(5);
    move_toward_zero(4);
    move_toward_zero(3);
    // show the new list
    printf("New list:\n");
    for(int i=0;i<tracker_count;i++){printf("   %i:element[%i] at %lu\n",i,tracker[i].subscript,(size_t)tracker[i].vector_ptr);}
    // ---plant some bogus subscripts for the next subscript test
    tracker[3].vector_ptr->subscript=7;
    tracker[3].subscript=5;
    tracker[7].vector_ptr->subscript=17;
    tracker[3].subscript=55;
printf("\n RENUMBER to use \"actual\" subscripts\n");   
    renumber_all_subscripts(FALSE);
    printf("Sorted list:\n");
    for(int i=0;i<tracker_count;i++)
    {   if ((size_t)tracker[i].vector_ptr!=0)
        {   printf("   %i:element[%i] or [%i]at %lu\n",i,tracker[i].subscript,tracker[i].vector_ptr->subscript,(size_t)tracker[i].vector_ptr);
        }
        else 
        {   printf("   %i:element[%i] at 0\n",i,tracker[i].subscript);
        }
    }
printf("\nBubble sort to get TRUE order back\n");
    bubble_sort();
    printf("Sorted list:\n");
    for(int i=0;i<tracker_count;i++)
    {   if ((size_t)tracker[i].vector_ptr!=0)
        {printf("   %i:element[%i] or [%i]at %lu\n",i,tracker[i].subscript,tracker[i].vector_ptr->subscript,(size_t)tracker[i].vector_ptr);}
        else {printf("   %i:element[%i] at 0\n",i,tracker[i].subscript);}
    }
    // END TEST SECTION
    // don't forget to free everything
    ss_vector_free_all_elements(); 
    return 0;
}

int main(int argc, char *argv[])
{   char cmd[5],main_buffer[50]; // Intentionally big for "other" I/O purposes
    cmd[0]=32; // blank = ASCII 32
    //  while(cmd!="R"&&cmd!="W"  &&cmd!="E"        &&cmd!=" ") 
    while(cmd[0]!=82&&cmd[0]!=87&&cmd[0]!=69)//&&cmd[0]!=32) 
    {   memset(cmd, '\0', sizeof(cmd));
        memset(main_buffer, '\0', sizeof(main_buffer));
        // default back to the cmd loop
        cmd[0]=32; // blank = ASCII 32
        printf("REad, TEst, WRITe, EDIt, or EXIt? ");
        fscanf(stdin, "%s", main_buffer);
        strncpy(cmd,main_buffer,4);
        for(int i=0;i<4;i++)cmd[i]=toupper(cmd[i]);
        cmd[4]='\0';
        printf("%s received\n ",cmd);
        // process top level commands
        if(cmd[0]==82) {printf("READ accepted\n");} //Read
        else if(cmd[0]==87) {printf("WRITe accepted\n");} // Write
        else if(cmd[0]==84) 
        {   printf("TESt accepted\n");// TESt
            Test();
        }
        else if(cmd[0]==69) // "E"
        {   if(cmd[1]==68) {printf("EDITing\n");} // eDit
            else if(cmd[1]==88) {printf("EXITing\n");exit(0);} // eXit
            else    printf("  unknown E command %c%c\n",cmd[0],cmd[1]);
        }
        else    printf("  unknown command\n");
        cmd[0]=32; // blank = ASCII 32
    } // while()
    // default back to the cmd loop
}   // main()

Answer 10

这些帖子的顺序可能有误！这是系列 3 篇文章中的第 2 篇文章。对不起。

我对 Lie Ryan 的代码进行了“一些自由”，实现了一个链表，以便可以通过链表访问他的向量的各个元素。这允许访问，但不可否认的是，由于搜索开销，访问单个元素非常耗时，即沿着列表走下去直到找到正确的元素。我将通过维护一个包含下标 0 到与内存地址配对的地址向量来解决这个问题。这仍然不如简单数组那么有效，但至少您不必“遍历列表”来搜索正确的项目。

    // Based on code from https://stackoverflow.com/questions/3536153/c-dynamically-growing-array
typedef struct STRUCT_SS_VECTOR
{   size_t size; // # of vector elements
    void** items; // makes up one vector element's component contents
    int subscript; // this element's subscript nmbr, 0 thru whatever
    struct STRUCT_SS_VECTOR* this_element; // linked list via this ptr
    struct STRUCT_SS_VECTOR* next_element; // and next ptr
} ss_vector;

ss_vector* vector; // ptr to vector of components

ss_vector* ss_init_vector(size_t item_size) // item_size is size of one array member
{   vector= malloc(sizeof(ss_vector)); 
    vector->this_element = vector; 
    vector->size = 0; // initialize count of vector component elements
    vector->items = calloc(1, item_size); // allocate & zero out memory for one linked list element
    vector->subscript=0;
    vector->next_element=NULL;
    //      If there's an array of element addresses/subscripts, install it now.
    return vector->this_element;
}

ss_vector* ss_vector_append(ss_vector* vec_element,                 int i) 
//                                                                          ^--ptr to this element  ^--element nmbr
{   ss_vector* local_vec_element=0;
    // If there is already a next element, recurse to end-of-linked-list
    if(vec_element->next_element!=(size_t)0) 
    {   local_vec_element= ss_vector_append(vec_element->next_element,i); // recurse to end of list
        return local_vec_element;
    }
    // vec_element is NULL, so make a new element and add at end of list
    local_vec_element= calloc(1,sizeof(ss_vector)); // memory for one component
    local_vec_element->this_element=local_vec_element; // save the address
    local_vec_element->next_element=0;
    vec_element->next_element=local_vec_element->this_element;
    local_vec_element->subscript=i; //vec_element->size; 
    local_vec_element->size=i; // increment # of vector components
    //      If there's an array of element addresses/subscripts, update it now.
    return local_vec_element;
}

void ss_vector_free_one_element(int i,gboolean Update_subscripts) 
{   // Walk the entire linked list to the specified element, patch up 
    //      the element ptrs before/next, then free its contents, then free it.
    //      Walk the rest of the list, updating subscripts, if requested.
    //      If there's an array of element addresses/subscripts, shift it along the way.
    ss_vector* vec_element;
    struct STRUCT_SS_VECTOR* this_one;
    struct STRUCT_SS_VECTOR* next_one;
    vec_element=vector;
    while((vec_element->this_element->subscript!=i)&&(vec_element->next_element!=(size_t) 0)) // skip
    {   this_one=vec_element->this_element; // trailing ptr
        next_one=vec_element->next_element; // will become current ptr
        vec_element=next_one;
    } 
    // now at either target element or end-of-list
    if(vec_element->this_element->subscript!=i)
    {   printf("vector element not found\n");return;}
    // free this one
    this_one->next_element=next_one->next_element;// previous element points to element after current one
    printf("freeing element[%i] at %lu",next_one->subscript,(size_t)next_one);
    printf(" between %lu and %lu\n",(size_t)this_one,(size_t)next_one->next_element);
    vec_element=next_one->next_element; 
    free(next_one); // free the current element
    // renumber if requested
    if(Update_subscripts)
    {   i=0;
        vec_element=vector;
        while(vec_element!=(size_t) 0)
        {   vec_element->subscript=i;
            i++;
            vec_element=vec_element->next_element; 
        }
    }
    //      If there's an array of element addresses/subscripts, update it now.
/*  // Check: temporarily show the new list
    vec_element=vector;
    while(vec_element!=(size_t) 0)
    {   printf("   remaining element[%i] at %lu\n",vec_element->subscript,(size_t)vec_element->this_element);
        vec_element=vec_element->next_element;
    } */
    return;
} // void ss_vector_free_one_element()

void ss_vector_insert_one_element(ss_vector* vec_element,int place) 
{   // Walk the entire linked list to specified element "place", patch up 
    //      the element ptrs before/next, then calloc an element and store its contents at "place".
    //      Increment all the following subscripts.
    //      If there's an array of element addresses/subscripts, make a bigger one, 
    //      copy the old one, then shift appropriate members.
    // ***Not yet implemented***
} // void ss_vector_insert_one_element()

void ss_vector_free_all_elements(void) 
{   // Start at "vector".Walk the entire linked list, free each element's contents, 
    //      free that element, then move to the next one.
    //      If there's an array of element addresses/subscripts, free it.
    ss_vector* vec_element;
    struct STRUCT_SS_VECTOR* next_one;
    vec_element=vector;
    while(vec_element->next_element!=(size_t) 0)
    {   next_one=vec_element->next_element;
        // free(vec_element->items) // don't forget to free these
        free(vec_element->this_element);
        vec_element=next_one;
        next_one=vec_element->this_element;
    }
    // get rid of the last one.
    // free(vec_element->items)
    free(vec_element);
    vector=NULL;
    //      If there's an array of element addresses/subscripts, free it now.
printf("\nall vector elements & contents freed\n");
} // void ss_vector_free_all_elements()

// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT
{   int id; // one of the data in the component
    int other_id; // etc
    struct APPLE_STRUCT* next_element;
} apple; // description of component

apple* init_apple(int id) // make a single component
{   apple* a; // ptr to component
    a = malloc(sizeof(apple)); // memory for one component
    a->id = id; // populate with data
    a->other_id=id+10;
    a->next_element=NULL;
    // don't mess with aa->last_rec here
    return a; // return pointer to component
};

int return_id_value(int i,apple* aa) // given ptr to component, return single data item
{   printf("was inserted as apple[%i].id = %i     ",i,aa->id);
    return(aa->id);
}

ss_vector* return_address_given_subscript(ss_vector* vec_element,int i) 
// always make the first call to this subroutine with global vbl "vector"
{   ss_vector* local_vec_element=0;
    // If there is a next element, recurse toward end-of-linked-list
    if(vec_element->next_element!=(size_t)0)
    {   if((vec_element->this_element->subscript==i))
        {   return vec_element->this_element;}
        local_vec_element= return_address_given_subscript(vec_element->next_element,i); // recurse to end of list
        return local_vec_element;
    }
    else
    {   if((vec_element->this_element->subscript==i)) // last element
        {   return vec_element->this_element;}
        // otherwise, none match
        printf("reached end of list without match\n");
        return (size_t) 0;
    }
} // return_address_given_subscript()

int Test(void)  // was "main" in the original example
{   ss_vector* local_vector;
    local_vector=ss_init_vector(sizeof(apple)); // element "0"
    for (int i = 1; i < 10; i++) // inserting items "1" thru whatever
    {   local_vector=ss_vector_append(vector,i);}   
    // test search function
    printf("\n NEXT, test search for address given subscript\n");
    local_vector=return_address_given_subscript(vector,5);
    printf("finished return_address_given_subscript(5) with vector at %lu\n",(size_t)local_vector);
    local_vector=return_address_given_subscript(vector,0);
    printf("finished return_address_given_subscript(0) with vector at %lu\n",(size_t)local_vector);
    local_vector=return_address_given_subscript(vector,9);
    printf("finished return_address_given_subscript(9) with vector at %lu\n",(size_t)local_vector);
    // test single-element removal
    printf("\nNEXT, test single element removal\n");
    ss_vector_free_one_element(5,FALSE); // without renumbering subscripts
    ss_vector_free_one_element(3,TRUE);// WITH renumbering subscripts
    // ---end of program---
    // don't forget to free everything
    ss_vector_free_all_elements(); 
    return 0;
}