Введение
Я решительно полагаю на вашу проблему, и это разреженность (большинство элементов в вашем массиве останутся равными нулю).При этом предположении я бы построил массив как список .Я включил пример кода, который не является полным и не предназначен для этого - вы должны сделать свою домашнюю работу:)
Основной объект - это структура с указателем на begin element и размер:
typedef struct vector {
size_t size;
vector_element_t * begin;
} vector_t;
каждый элемент вектора имеет свой собственный индекс и значение и указатель на следующий элемент в списке:
typedef struct vector_element vector_element_t;
struct vector_element {
int value;
size_t index;
vector_element_t *next;
};
на этом основании мыможно построить динамический вектор в виде списка, сняв ограничение на порядок (это не нужно, вы можете изменить этот код, чтобы сохранить порядок), используя несколько простых пользовательских методов:
vector_t * vector_init(); // Initialize an empty array
void vector_destroy(vector_t* v); // Destroy the content and the array itself
int vector_get(vector_t *v, size_t index); // Get an element from the array, by searching the index
size_t vector_set(vector_t *v, size_t index, int value); // Set an element at the index
void vector_delete(vector_t *v, size_t index); // Delete an element from the vector
void vector_each(vector_t *v, int(*f)(size_t index, int value)); // Executes a callback for each element of the list
// This last function may be the response to your question
Проверьте это онлайн
Основной пример
Это основной, который использует все эти методы и печатает в консоли:
int callback(size_t index, int value) {
printf("Vector[%lu] = %d\n", index, value);
return value;
}
int main() {
vector_t * vec = vector_init();
vector_set(vec, 10, 5);
vector_set(vec, 23, 9);
vector_set(vec, 1000, 3);
printf("vector_get(vec, %d) = %d\n", 1000, vector_get(vec, 1000)); // This should print 3
printf("vector_get(vec, %d) = %d\n", 1, vector_get(vec, 1)); // this should print 0
printf("size(vec) = %lu\n", vec->size); // this should print 3 (the size of initialized elements)
vector_each(vec, callback); // Calling the callback on each element of the
// array that is initialized, as you asked.
vector_delete(vec, 23);
printf("size(vec) = %lu\n", vec->size);
vector_each(vec, callback); // Calling the callback on each element of the array
vector_destroy(vec);
return 0;
}
И вывод:
vector_get(vec, 1000) = 3
vector_get(vec, 1) = 0
size(vec) = 3
Vector[10] = 5
Vector[23] = 9
Vector[1000] = 3
size(vec) = 3
Vector[10] = 5
Vector[1000] = 3
callback с функцией vector_each - это то, на что вы действительно должны смотреть.
Реализации
Я даю вамнекоторые тривиальные реализации для функций во введении.Они не полны, и некоторые проверки указателей должны быть введены.Я оставляю это тебе.Как таковой, этот код не предназначен для производства и при некоторых обстоятельствах может также переполниться .
Особой частью является поиск определенного элемента в векторе.Каждый раз, когда вы перемещаетесь по списку, это удобно только и только если у вас есть разреженность (большая часть вашего индекса всегда будет возвращать ноль).В этой реализации, если вы обращаетесь к индексу, который не зачислен в список, вы получите результат 0. Если вы не хотите этого, вам следует определить обратный вызов ошибки.
Инициализация и уничтожение
Когда мы инициализируем, мы выделяем память для нашего вектора, но без элементов внутри, таким образом, begin указывает на NULL.Когда мы уничтожаем вектор, мы должны не только освободить вектор, но и каждый содержащийся в нем элемент.
vector_t * vector_init() {
vector_t * v = (vector_t*)malloc(sizeof(vector_t));
if (v) {
v->begin = NULL;
v->size = 0;
return v;
}
return NULL;
}
void vector_destroy(vector_t *v) {
if (v) {
vector_element_t * curr = v->begin;
if (curr) {
vector_element_t * next = curr->next;
while (next) {
curr = curr->next;
next = next->next;
if (curr)
free(curr);
}
if (next)
free(next);
}
free(v);
}
}
Методы get и set
В get вы можете увидеть, как работает список (и та же самая концепция используется также в set и delete): мы начинаем с начала и пересекаем список, пока не достигнем элемента с индексом, равным запрошенному.Если мы не можем найти его, мы просто возвращаем 0. Если нам нужно «поднять какой-то сигнал», когда значение не найдено, легко реализовать «обратный вызов ошибки».
Пока sparsness верно, поиск индекса во всем массиве является хорошим компромиссом с точки зрения требований к памяти, и эффективность может быть не проблемой.
int vector_get(vector_t *v, size_t index) {
vector_element_t * el = v->begin;
while (el != NULL) {
if (el->index == index)
return el->value;
el = el->next;
}
return 0;
}
// Gosh, this set function is really a mess... I hope you can understand it...
// -.-'
size_t vector_set(vector_t *v, size_t index, int value) {
vector_element_t * el = v->begin;
// Case 1: Initialize the first element of the array
if (el == NULL) {
el = (vector_element_t *)malloc(sizeof(vector_element_t));
if (el != NULL) {
v->begin = el;
v->size += 1;
el->index = index;
el->value = value;
el->next = NULL;
return v->size;
} else {
return 0;
}
}
// Case 2: Search for the element in the array
while (el != NULL) {
if (el->index == index) {
el->value = value;
return v->size;
}
// Case 3: if there is no element with that index creates a new element
if (el->next == NULL) {
el->next = (vector_element_t *)malloc(sizeof(vector_element_t));
if (el->next != NULL) {
v->size += 1;
el->next->index = index;
el->next->value = value;
el->next->next = NULL;
return v->size;
}
return 0;
}
el = el->next;
}
}
Удаление элемента
При таком подходе можно довольно легко удалить элемент, подключив curr->next к curr->next->next.Хотя мы должны освободить предыдущую curr->next ...
void vector_delete(vector_t * v, size_t index) {
vector_element_t *curr = v->begin;
vector_element_t *next = curr->next;
while (next != NULL) {
if (next->index == index) {
curr->next = next->next;
free(next);
return;
} else {
curr = next;
next = next->next;
}
}
}
Итерационную функцию
Я думаю, что это ответ на последнюю часть вашего вопроса, вместо этого передавая последовательность индексов, вы передаете обратный вызов в вектор.Обратный вызов получает и устанавливает значение в определенном индексе.Если вы хотите работать только с некоторыми конкретными индексами, вы можете включить проверку в сам обратный вызов.Если вам нужно передать больше данных в обратный вызов, проверьте самый последний раздел.
void vector_each(vector_t * v, int (*f)(size_t index, int value)) {
vector_element_t *el = v->begin;
while (el) {
el->value = f(el->index, el->value);
el = el->next;
}
}
Ошибка обратного вызова
Возможно, вы захотите поднять вне границ ошибкаили что-то другое.Одно из решений состоит в том, чтобы обогатить ваш список указателем на функцию, представляющим обратный вызов, который должен вызываться, когда ваш пользователь ищет неопределенный элемент:
typedef struct vector {
size_t size;
vector_element_t *begin;
void (*error_undefined)(vector *v, size_t index);
} vector_t
и, возможно, в конце вашей функции vector_get, которую вы можете захотетьсделать что-то вроде:
int vector_get(vector_t *v, size_t index) {
// [ . . .]
// you know at index the element is undefined:
if (v->error_undefined)
v->error_undefined(v, index);
else {
// Do something to clean up the user mess... or simply
return 0;
}
}
обычно неплохо добавить также вспомогательную функцию для установки обратного вызова ...
Передача пользовательских данных для "каждого" обратного вызова
Если вы хотите передать больше данных обратному вызову пользователя, вы можете добавить void* в качестве последнего аргумента:
void vector_each(vector_t * v, void * user_data, int (*f)(size_t index, int value, void * user_data));
void vector_each(vector_t * v, void * user_data, int (*f)(size_t index, int value, void * user_data)) {
[...]
el->value = f(el->index, el->value, user_data);
[...]
}
если пользователю это не нужно, он может передать замечательный NULL.