С динамически растущим массивом
У меня есть программа, которая читает "сырой" список игровых сущностей, и я намереваюсь создать массив, содержащий индексное число (int) неопределенного числа сущностей, для обработки различных вещей. Я бы хотел не использовать слишком много памяти или процессора для хранения таких индексов...
Быстрое и грязное решение, которое я использую до сих пор, состоит в том, чтобы объявить в основной функции обработки (локальный фокус) массив с размером максимального количества игровых объектов и другое целое число, чтобы отслеживать, сколько было добавлено в список. Это неудовлетворительно, так как каждый список содержит более 3000 массивов, что не так уж много, но выглядит как пустая трата, так как я могу использовать решение для 6-7 списков для различных функций.
Я не нашел никаких конкретных решений для C (не C++ или C#) для достижения этой цели. Я могу использовать указатели, но я немного боюсь их использовать (если это не единственный возможный способ).
Массивы не покидают область действия локальной функции (они должны быть переданы в функцию, а затем отброшены), если это что-то меняет.
Если указатели являются единственным решением, как я могу отслеживать их, чтобы избежать утечек?
10 ответов
Я могу использовать указатели, но я немного боюсь их использовать.
Если вам нужен динамический массив, вы не можете избежать указателей. Почему ты боишься, хотя? Они не будут кусаться (пока вы осторожны). В 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 = (int *)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 = (int *)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);
Как и во всем, что поначалу кажется страшнее, чем было позже, лучший способ преодолеть первоначальный страх - погрузиться в дискомфорт неизвестного! Временами это то, чему мы учимся больше всего.
К сожалению, есть ограничения. Хотя вы все еще учитесь использовать функцию, вы не должны брать на себя роль учителя, например. Я часто читаю ответы от тех, кто, кажется, не знает, как использовать realloc (то есть, в настоящее время принятый ответ!), рассказывающий другим, как использовать его неправильно, иногда под предлогом того, что они опускают обработку ошибок, даже если это распространенная ошибка, о которой нужно упомянуть. Вот ответ, объясняющий, как использовать realloc правильно. Обратите внимание, что ответ сохраняет возвращаемое значение в другую переменную для проверки ошибок.
Каждый раз, когда вы вызываете функцию, и каждый раз, когда вы используете массив, вы используете указатель. Преобразования происходят неявно, что, если что-то должно быть еще страшнее, так как именно вещи, которые мы не видим, часто вызывают большинство проблем. Например, утечки памяти...
Операторы массива являются операторами указателя. array[x] действительно ярлык для *(array + x), который можно разбить на: * а также (array + x), Скорее всего, что * это то, что вас смущает. Мы можем еще больше устранить сложение из задачи, предполагая, x быть 0 таким образом, array[0] становится *array потому что добавление 0 не будет менять значение...
... и, таким образом, мы можем видеть, что *array эквивалентно array[0], Вы можете использовать один, где вы хотите использовать другой, и наоборот. Операторы массива являются операторами указателя.
malloc, realloc и друзья не изобретают концепцию указателя, которую вы использовали все это время; они просто используют это для реализации какой-то другой функции, которая представляет собой другую форму продолжительности хранения, наиболее подходящую, когда вы желаете радикальных, динамических изменений в размере.
Жаль, что принятый в настоящее время ответ также идет вразрез с некоторыми другими очень обоснованными рекомендациями по Stackru и в то же время упускает возможность представить малоизвестную функцию, которая подходит именно для этого варианта использования: гибкий массив Участники! Это на самом деле довольно неправильный ответ...:(
Когда вы определяете 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 ** первый аргумент может показаться не сразу очевидным, но если подумать о втором аргументе, любые изменения, внесенные в value изнутри push_back не будет виден функции, из которой мы вызываем, верно? То же самое касается первого аргумента, и мы должны иметь возможность изменить наш array не только здесь, но, возможно, также в любой другой функции / с, мы передаем это...
array начинает указывать ни на что; это пустой список. Инициализация это то же самое, что и добавление к нему. Например:
struct int_list *array = NULL;
if (!push_back(&array, 42)) {
// success!
}
PS Не забудьте free(array); когда вы закончите с этим!
Есть несколько вариантов, которые я могу придумать.
- Связанный список. Вы можете использовать связанный список, чтобы создать динамически растущий массив. Но вы не сможете сделать
array[100]без необходимости проходить через1-99первый. И это может быть не очень удобно для вас использовать. - Большой массив. Просто создайте массив с более чем достаточно места для всего
- Изменение размера массива. Создайте заново массив, как только вы узнаете размер, и / или создайте новый массив каждый раз, когда у вас заканчивается свободное пространство с некоторым запасом, и скопируйте все данные в новый массив.
- Комбинированный список Array List. Просто используйте массив с фиксированным размером и, как только вы исчерпаете пространство, создайте новый массив и создайте ссылку на него (было бы целесообразно отслеживать массив и ссылку на следующий массив в структуре).
Трудно сказать, какой вариант будет лучшим в вашей ситуации. Простое создание большого массива, безусловно, является одним из самых простых решений и не должно доставлять вам особых проблем, если только он не очень большой.
Основываясь на дизайне Matteo Furlans, он сказал, что "большинство реализаций динамических массивов работают, начиная с массива некоторого (небольшого) размера по умолчанию, а затем, когда у вас заканчивается свободное место при добавлении нового элемента, удваивают размер массива". Разница в "незавершенном производстве" ниже заключается в том, что он не удваивается по размеру, а направлен на использование только того, что требуется. Я также пропустил проверки безопасности для простоты... Кроме того, основываясь на идее brimboriums, я попытался добавить функцию удаления в код...
Файл storage.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 */
Файл 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);
}
С нетерпением ждем конструктивной критики, чтобы следовать...
Чтобы создать массив неограниченных элементов любого типа:
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;
}
Этот вектор / массив может содержать любой тип элемента, и он полностью динамический по размеру.
Когда ты говоришь
сделать массив, содержащий порядковый номер (int) неопределенного числа объектов
Вы в основном говорите, что используете "указатели", но тот, который является локальным указателем в массиве, а не указателем в памяти. Поскольку вы концептуально уже используете "указатели" (то есть числа id, которые относятся к элементу в массиве), почему бы вам просто не использовать обычные указатели (то есть числа id, которые относятся к элементу в самом большом массиве: всей памяти).
Вместо того, чтобы ваши объекты хранили номера идентификаторов ресурсов, вы можете заставить их хранить указатель. В основном то же самое, но гораздо более эффективно, поскольку мы избегаем превращения "массива + индекса" в "указатель".
Указатели не страшны, если вы думаете о них как о индексе массива для всей памяти (что на самом деле и есть)
Ну, я думаю, если вам нужно удалить элемент, вы сделаете копию массива, презирающего элемент, который будет исключен.
// 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(...) являются вспомогательными методами для обработки временного вектора.
Эти сообщения явно расположены в неправильном порядке! Это №1 в серии из 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;
}
Можно без проблем получить доступ к каждому элементу массива, если вы знаете его адрес, поэтому я думаю, я попробую добавить «следующий» элемент и использовать его как связанный список. Конечно, есть варианты получше. Пожалуйста, порекомендуйте.
Эти сообщения явно расположены в неправильном порядке! Это №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()
Эти сообщения могут быть в неправильном порядке! Это №2 в серии из 3 постов. Простите.
Я «взял на себя некоторые вольности» с кодом Ли Райана, реализовав связанный список, чтобы к отдельным элементам его вектора можно было получить доступ через связанный список. Это позволяет получить доступ, но, по общему признанию, доступ к отдельным элементам занимает много времени из-за накладных расходов на поиск, то есть перемещения по списку, пока не найдете нужный элемент. Я исправлю это, поддерживая адресный вектор, содержащий индексы от 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;
}