Однонаправленный список

Эта структура позволяет установить связи между составляющими ее элементами и осуществлять переходы от одного элемента к другому в соответствии с некоторым порядком. Элементы представляют собой структуры и могут образовывать массив либо располагаться в "куче". Например, с помощью списка можно выполнить сортировку элементов по значению одного из элементов структуры, не перемещая данные в памяти. Однако при этом требуется дополнительная память для размещения указателя на последующий (или предыдущий) элемент списка. Схематически список изобразить следующим способом.

Пример. Сортировка массива методом вставки в список.

typedef struct zap{ // Строение элемента списка

struct {...} dan; // Хранимая информация

short key; // Ключ сортировки

struct zap *p; // Указатель на следующий элемент списка

} Zap;

/* Процедура сортировки */

Zap* sort(Zap *set, // Указатель на голову списка

short n){ // Число элементов списка

Zap *head, // "Голова" списка

*current, // Текущий элемент

*insert, // Вставляемый элемент

*prev; // Предыдущий элемент

short i, k;

head = set; head->p = NULL;

for (i = 1; i < n; i++){

current = head; insert = set + i;

/* Поиск места вставки */

for (k = 0; k < i && insert->key >= current->key; k++){

prev = current; current = current->p;

}

/* Вставка */

if (k == 0){ /* 1-й элемент */

head = insert;

} else {

prev->p=insert;

}

if (k < i){ /* Не последний элемент */

insert->p = current;

} else { /* Последний элемент */

insert->p = NULL;

}

} // End i

return head;

} // End sort

/* Обработка списка в вызывающей процедуре */

tek = sort(s, n);

for (i = 0; i < n; i++){

/* Использование dan((tek->dan).<имя>) */

....................................................

tek = tek->p;

}