Какой использовать связанный список или статические массивы?

Проблема с 'select count (*)' заключается в том, что значение может меняться между вызовами, поэтому ваш «настоящий» выбор будет иметь количество элементов, отличное от ожидаемого количества.

Думаю, лучшее решение - ваша «2». Вместо связанного списка я бы лично выделил массив (при необходимости перераспределив). Это проще в языках, поддерживающих растущие массивы (например, std::vector<myrecord> в C++ и List<myrecord> в C#).

Вы забыли вариант 3, он немного сложнее, но может быть лучше всего для вашего конкретного случая. Так обычно делается в C++ std :: vector.

Выделяйте массив любого удобного размера. Когда этот массив будет заполнен, выделите новый массив большего размера от 1,5x до 2x размера заполненного, затем скопируйте заполненный массив в этот. Освободите исходный массив и замените его новым. Вспенить, промыть, повторить.

И забыл вариант №4. Выделите массив фиксированного размера. Когда этот массив заполнится, выделите другой. Вы можете отслеживать массивы, связывая их в связанный список или имея массив более высокого уровня, в котором хранятся указатели на массивы данных. Эта двухуровневая схема отлично подходит, когда вам нужен произвольный доступ, вам просто нужно разбить ваш индекс на две части.

Есть много возможных критических замечаний, которые следует сделать.

1. Вы вообще не говорите о статическом массиве - статический массив будет иметь заранее определенный размер, фиксированный во время компиляции, и либо локальный для исходного файла, либо локальный для функции. Вы говорите о динамически выделяемом массиве.

2. Вы не даете никаких указаний ни о размере записи, ни о количестве записей, ни о том, насколько динамична находящаяся под ней база данных (то есть может ли какой-либо другой процесс изменить какие-либо данные во время работы вашего). Информация о размерах не очень важна, но есть другой фактор. Если вы составляете какой-то отчет, тогда можно загрузить данные в память; вы не собираетесь изменять базу данных, и данные представляют собой точный снимок. Однако, если другие люди могут изменять записи, в то время как вы изменяете записи, ваше общее решение является основным примером того, как потерять чужие обновления. Это вещь ПЛОХО!

3. Зачем вам сразу все данные в памяти? Игнорирование ограничений размера, в чем именно преимущество этого по сравнению с обработкой каждой соответствующей записи один раз в правильной последовательности? Видите ли, СУБД прилагает много усилий, чтобы иметь возможность выбирать соответствующие записи (предложения WHERE) и соответствующие данные (списки SELECT) и позволять вам указывать последовательность (предложения ORDER BY), и у них есть лучшие системы сортировки, которые они могут позволить себе (лучше, чем те, которые вы или я, вероятно, произведем).

4. Остерегайтесь квадратичного поведения, если вы распределяете массив по частям. Каждый раз, когда вы перераспределяете, есть большая вероятность, что старую память придется скопировать в новое место. Это фрагментирует вашу память (старое местоположение будет доступно для повторного использования, но по определению будет слишком маленьким для повторного использования). Марк Рэнсом указывает разумную альтернативу - не самую простую схему в мире в целом (но она избегает квадратичного поведения, о котором я упоминал). Конечно, вы можете (и будете) абстрагироваться от этого с помощью набора подходящих функций.

5. Массовая загрузка (также упомянутая Марком Рэнсомом) также полезна. Вы можете предварительно выделить массив, в который выполняется массовая выборка, чтобы вам не приходилось выполнять дополнительное копирование. Однако это просто линейное поведение, поэтому оно менее серьезно.

Создайте структуру данных для представления вашего массива или списка. Представьте, что вы используете объектно-ориентированный язык, и создайте аксессоры и конструкторы для всего, что вам нужно. Внутри этой структуры данных сохраните массив и, как говорили другие, когда массив заполнится до предела, выделите новый массив в 2 раза больше и скопируйте в него. Доступ к структуре только через определенные вами процедуры для доступа к ней.

Именно так это делают Java и другие языки. Внутри это даже то, как Perl реализован в C.

Я собирался сказать, что ваш лучший вариант - это поискать библиотеку, которая уже делает это ... может быть, вы можете позаимствовать Perl-реализацию C такой структуры данных. Я уверен, что это проверено лучше, чем все, что вы или я могли бы скатать с нуля. :)

while(record = get_record()) {
  records++;
  records_array = (record_struct *) realloc(records_array, (sizeof record_struct)*records);
  *records_array[records - 1] = record;
}

Это строго пример - пожалуйста, не используйте realloc () в производстве.

Связанный список - удобный и простой вариант. Я бы с этим согласился. Если вы предпочитаете растущий массив, вы можете найти реализацию как часть Интерфейсы C и реализации Дэйва Хэнсона, который в качестве бонуса также предоставляет связанные списки.

Мне это кажется дизайнерским решением, которое может измениться по мере развития вашего приложения, поэтому вам обязательно стоит скрыть представление за подходящим API. Если вы еще не знаете, как это сделать, код Hanson предоставит вам несколько хороших примеров.