записки хакера

КРИС КАСПЕРСКИ

Спецвыпуск: Хакер, номер #071, стр. 071-112-1

[сортировка списков.]

Списки — популярные и во многом интересные структуры данных. Они естественным образом поддерживают быструю вставку и удаление элементов, но ни в одном известном мне руководстве не затрагиваются вопросы их сортировки. Ну да, конечно, в библиотеке STL есть класс list с готовым методом stort. Пользуйся – не хочу! Но универсальное решение по определению не есть хорошее. Это раз. Не все программисты пользуются STL — это два. Наконец, в Си ничего подобного и в помине нет – это три. К тому же было бы полным непрофессионализмом вызвывать list::sort, не задумываясь о том, как он работает. А, правда, как? Давайте, не подглядывая в исходный код STL, попытаемся реализовать сортировку списка самостоятельно.

Начнем с того, что отсортировать список тривиальным вызовом qsort не удастся, поскольку она рассчитывает, что следующий сортируемый элемент расположен непосредственно за концом предыдущего. При обработке массивов все так и происходит, но списки ведут себя иначе. Малого того, что элементы списка могут размещаться в памяти в каком угодно порядке: нет никаких гарантий, что за концом какого-то элемента находится действительный элемент!

Рассмотрим следующий пример:

struct LIST *last_record = 0;

strict LIST *list = (struct LIST*) malloc(sizeof(struct LIST));

for(a=0;a<N; a++)

{

list->val = a;

list->next_record = (struct LIST*) malloc(sizeof(struct LIST));

list = list->next_record;

} list->val=a; list->next_record = 0;

Допустим, нам необходимо отсортировать список так, чтобы последующий элемент имел большее или такое же значение val. Как это сделать? Алгоритм сортировки прост как косяк: перегоняем списки в массив, сортируем его как обычно, затем либо уничтожаем несортированный список и создаем новый, либо «натягиваем» отсортированный массив на уже существующий «скелет», то есть используем уже выделенные блоки памяти. Естественно, последний способ работает намного быстрее! Демонстрационная программа для сортировки прилагается.

[двухмаршрутные списки.]

В тех случаях, когда требуется осуществить ту или иную выборку элементов из списка для их последующей обработки (проще говоря, фильтрацию), можно пойти двумя путями:

1 Вернуть отфильтрованные элементы в отдельном списке (что имеет тот недостаток, что понапрасну расходует память, а при «многокаскадной» фильтрации мы рискуем окончательно запутаться в куче списков).

2 Помимо поля struct list *next_record добавить еще одно поле «struct list *next_filtred__record». В таком случае мы будем иметь дело всего лишь с одним списком, содержащим как оригинальные, так и отфильтрованные данные.

Естественно, еще потребуется поле «struct LIST* first_filtred_record», содержащее указатель на первый отфильтрованный элемент списка. Оно необходимо затем, что первый элемент оригинального списка не обязательно будет совпадать с первым отфильтрованным элементом. К тому же «двухмаршрутные» списки естественным образом поддерживают «каскадную» фильтрацию. В самом деле, мы сканируем список, перескакивая по полям «next_filtred_record», и, если следующий элемент не проходит через фильтр, то предыдущая ссылка перескакивает вперед. Так же очевидно, что нам потребуется два набора функций для работы с двумя маршрутами.