动态增长的数组

我能想到几个选择。

1. 相连名单。你可以使用一个链表来创建一个动态增长的数组。但是，如果不首先遍历 1-99，那么就不能进行 array[100]。而且可能对你来说也没那么方便。
2. 只需要创建一个空间足够大的数组
3. 调整数组大小。一旦知道了数组的大小，就重新创建该数组，并且/或者每次空间用完时创建一个新数组，并留出一些空白，然后将所有数据复制到新数组中。
4. 链表数组组合。简单地使用一个固定大小的数组，一旦空间用完，创建一个新的数组并链接到该数组(明智的做法是在结构中跟踪该数组并链接到下一个数组)。

很难说在你的情况下什么选择是最好的。简单地创建一个大的数组当然是最简单的解决方案之一，除非它非常大，否则不会给您带来太多问题。

当你说

创建一个包含不确定数量实体的索引数(int)的数组

你基本上是说你在使用“指针”，但它是一个数组范围的本地指针，而不是内存范围的指针。既然你在概念上已经使用了“指针”(即指向数组中元素的 id 号) ，为什么不使用常规指针(即指向最大数组中元素的 id 号: 整个内存)呢。

您可以让对象存储指针，而不是存储资源 ID 号。基本上是一样的，但是效率更高，因为我们避免了把“ array + index”变成“指针”。

如果你认为指针是整个内存的数组索引(它们实际上就是数组索引) ，那么它们并不可怕

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

如果需要动态数组，则无法转义指针。你为什么害怕？它们不会咬人(只要你小心)。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);

一个简单的解决方案涉及 mmap。如果您能够容忍 POSIX 解决方案，那么这非常好。只需映射整个页面并防止溢出，因为 realloc无论如何都会失败。现代操作系统只有在你使用它的时候才会提交整个系统，如果你愿意，你可以截断文件。

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

不幸的是，还是有局限性的。例如，当你还在学习使用函数时，你不应该扮演老师的角色。我经常从那些似乎不知道如何使用 realloc(即 目前可接受的答案！)的人那里读到答案，告诉别人如何不正确地使用它，偶尔假装他们已经使用了 遗漏的错误处理，尽管这是一个需要提及的常见陷阱。下面是一个解释如何正确使用 realloc的答案.请注意，答案是将返回值存储到一个 < em > different 变量中，以执行错误检查。

每次调用函数，每次使用数组，都是在使用指针。这种转换是隐性发生的，如果说有什么事情应该更可怕的话，那就是那些我们看不到的东西往往会导致最多的问题。例如，内存泄漏..。

数组运算符是指针运算符。array[x]实际上是 *(array + x)的一条捷径，它可以分为: *和 (array + x)。最有可能的是 *使你感到困惑。我们可以通过假设 x是 0来进一步消除这个问题，因此，array[0]变成了 *array，因为增加 0不会改变值..。

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

malloc，realloc和朋友们并不是你一直使用的 发明指针的概念; 他们只是 使用这个来实现一些其他的功能，这是一种不同形式的存储持续时间，最适合当你想要 大小的剧烈的、动态的变化。

令人遗憾的是，目前已被接受的答案 还有与 关于 StackOverflow 的其他一些非常有根据的建议背道而驰，同时错过了引入一个鲜为人知的特性的机会，这个特性正好适用于这个用例: 灵活的数组成员！这实际上是一个 非常破碎的答案... : (

定义 struct时，声明结构的数组 最后，不要有任何上界。例如:

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，不仅仅是 给你，还有 也可能在我们传递给它的任何其他函数中..。

array开始时什么都不指向; 它是一个空列表。启动中等于向它加法。例如:

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

附注 记住 free(array);当你完成它！

创建一个由任何类型的无限项组成的数组:

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;
}

这个向量/数组可以容纳任何类型的项目，它的大小是完全动态的。

好吧，我想如果你需要删除一个元素，你会做一个数组的副本，尽管被排除的元素。

// 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(...)是处理临时矢量的辅助方法。

建立在 Matteo Furlans的设计上，当他说“ 大多数动态数组实现都是从一个默认大小的数组开始，然后当添加新元素时空间不足时，将数组的大小增加一倍”的时候。下面的“ 正在进行中的工作”的不同之处在于，它的大小不会增加一倍，它的目标是只使用所需要的东西。我也省略了简单的安全检查... 也建立在 荆棘的想法，我试图添加一个删除函数的代码..。

H 文件看起来像这样..。

#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 */

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;
}

主电路看起来像这样..。

#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);
}

期待 建设性的批评的到来。

这些帖子的顺序显然是错误的! 这是一系列3个帖子中的第一个。对不起。

在尝试使用李 · 瑞安的代码时，我在检索存储的信息时遇到了问题。向量的元素并不是连续存储的，您可以通过“欺骗”一下并存储指向每个元素地址的指针(这当然违背了动态数组概念的目的)并检查它们来看到这一点。

稍作修补，来自:

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;
}

只要您知道每个数组元素的地址，就可以毫无问题地访问它们，所以我想我将尝试添加一个“ next”元素，并将其用作一个链表。不过，肯定还有更好的选择。请指示。

这些帖子可能排错了顺序! 这是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;
}

这些帖子显然是错误的顺序! 这是在一系列的3个帖子 # 3。对不起。

我已经“采取了一些更多的自由”与李瑞安的代码。链接列表是公认的时间访问个人 元素，也就是说，沿着列表一直走，直到找到正确的元素。我现在已经治好了 维护一个包含下标0的地址向量，通过任何与内存地址配对的方式 因为地址向量是一次性分配的，因此在内存中是连续的, 我已经撕掉了它的相关代码和结构。

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

从这里开始，我建议用户编写适合自己需要的“元素”部分，并确保其正确运行。如果你 添加的元素是数组，仔细编写访问它们的子程序，看看有多少额外的数组结构 静态数组不需要这些，好好享受吧！

#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()