Начнем с того, что отсортировать список тривиальным вызовом qsort не удастся, поскольку она рассчитывает, что следующий сортируемый элемент расположен непосредственно за концом предыдущего. При обработке массивов все так и происходит, но списки ведут себя иначе. Малого того, что элементы списка могут размещаться в памяти в каком угодно порядке: нет никаких гарантий, что за концом какого-то элемента находится действительный элемент!
Рассмотрим следующий пример:
struct LIST *last_record = 0;
strict LIST *list = (struct LIST*) malloc(sizeof(struct LIST));
Допустим, нам необходимо отсортировать список так, чтобы последующий элемент имел большее или такое же значение val. Как это сделать? Алгоритм сортировки прост как косяк: перегоняем списки в массив, сортируем его как обычно, затем либо уничтожаем несортированный список и создаем новый, либо «натягиваем» отсортированный массив на уже существующий «скелет», то есть используем уже выделенные блоки памяти. Естественно, последний способ работает намного быстрее! Демонстрационная программа для сортировки прилагается. Двухмаршрутные списки
В тех случаях, когда требуется осуществить ту или иную выборку элементов из списка для их последующей обработки (проще говоря, фильтрацию), можно пойти двумя путями:
1. Вернуть отфильтрованные элементы в отдельном списке (что имеет тот недостаток, что понапрасну расходует память, а при «многокаскадной» фильтрации мы рискуем окончательно запутаться в куче списков). 2. Помимо поля struct list *next_record добавить еще одно поле «struct list *next_filtred__record». В таком случае мы будем иметь дело всего лишь с одним списком, содержащим как оригинальные, так и отфильтрованные данные.
Естественно, еще потребуется поле «struct LIST* first_filtred_record», содержащее указатель на первый отфильтрованный элемент списка. Оно необходимо затем, что первый элемент оригинального списка не обязательно будет совпадать с первым отфильтрованным элементом. К тому же «двухмаршрутные» списки естественным образом поддерживают «каскадную» фильтрацию. В самом деле, мы сканируем список, перескакивая по полям «next_filtred_record», и, если следующий элемент не проходит через фильтр, то предыдущая ссылка перескакивает вперед. Так же очевидно, что нам потребуется два набора функций для работы с двумя маршрутами. Обработка ошибки выделения памяти
Постоянная проверка успешности выполнения интенсивно используемых функций во-первых, слишком утомительна, во-вторых, загромождает исходный текст, и, в-третьих, приводит к неоправданному увеличению объема откомпилированного кода программы.
char *p;
p = malloc(BLOCK_SIZE);
if (p==0)
{
fprintf(stderr,"-ERR: недостаточно памяти для продолжения операци\n");
_exit();
}
Кстати говоря, следующий код «p = malloc(x); if (!p) return 0;» даже хуже, чем отсутствие проверки вообще, так как при обращении к нулевому указателю Windows хоть выругается, указав на место сбоя, а такая кривая проверка просто тихо кончит программу...
Решение заключается в создании «оберток» для интенсивно используемых функций, проверяющих успешность завершения вызываемой ими функции и при необходимости рапортующих об ошибке с завершением программы или передающих управление соответствующему обработчику данной аварийной ситуации.
void* my_malloc(int x)
{
int *z;
z=malloc(x);
if (!z) GlobalError_and_save
}
Между прочим, виртуальная память не безгранична и иногда она неожиданно кончается. Попытка выделения нового блока посредством malloc дает ошибку. В этой ситуации очень важно корректно сохранить все несохраненные данные и выйти. А как быть, если для сохранения требуется определенное количество памяти? Да очень просто! При старте программы выделяем malloc'ом столько памяти, сколько ее может потребоваться для аварийного сохранения. Если нас обломают на память, то просто не запускаемся, а с ругательством сваливаем. Затем, при нехватке памяти просто сохраняемся (необходимая память у нас есть) и все!!!
