Применение линейных списков
Линейные списки находят широкое применение в приложениях, где непредсказуемы требования на размер памяти, необходимой для хранения данных; большое число сложных операций над данными, особенно включений и исключений. На базе линейных списков могут строиться стеки, очереди и деки. Представление очереди с помощью линейного списка позволяет достаточно просто обеспечить любые желаемые дисциплины обслуживания очереди. Особенно это удобно, когда число элементов в очереди трудно предсказуемо.
В программном примере 2.1 показана организация стека на односвязном линейном списке. Это - пример функционально аналогичен примеру 1.4 с той существенной разницей, что размер стека здесь практически неограничен. Он ограничен только свободной оперативной памятью.
Стек представляется как линейный список, в котором включение элементов всегда производится в начало списка, а исключение - также из начала. Для представления его нам достаточно иметь один указатель - top, который всегда указывает на последний записанный в стек элемент. В исходном состоянии (при пустом стеке) указатель top - пустой. Процедуры StackPush и StackPop сводятся к включению и исключению элемента в начало списка. Обратите внимание, что при включении элемента для него выделяется память, а при исключении - освобождается. Перед включением элемента проверяется доступный объем памяти, и если он не позволяет выделить память для нового элемента, стек считается заполненным. При очистке стека последовательно просматривается весь список и уничтожаются его элементы.
При списковом представлении стека оказывается непросто определить размер стека. Эта операция могла бы потребовать перебора всего списка с подсчета числа элементов. Чтобы избежать последовательного перебора всего списка мы, ввели дополнительную переменную stsize, которая отражает текущее число элементов в стеке и корректируется при каждом включении/исключении.
{==== Программный пример 2.1 ====}
// Стек на 1-связном линейном списке
typedef ... data; // эл-ты могут иметь любой тип
typedef struct Node* link; // указатель на эл-т списка
struct Node // элемент списка
{
data inf; // данные
link next; // указатель на следующий эл-т
};
link top; // указатель на вершину стека
long stSize; // размер стека
// *** инициализация - список пустой
void StackInit()
{
top = NULL;
stSize = 0;
}
// *** очистка - освобождение всей памяти
void StackClr()
{
link buf;
while( top ) // перебор эл-тов до конца списка и их уничтожение
{
buf = top;
top = top->next;
delete buf;
}
stSize = 0;
}
// *** занесение в стек
bool StackPush( data d )
{
link curr = new Node; // если нет больше свободной памяти, то - отказ
if( curr == NULL ) return false;
else // выделение памяти для эл-та и заполнение инф.части
{
curr->inf = d;
curr->next = top; // новый эл-т помещается в голову списка
top = curr;
stSize++; // коррекция размера
return true;
}
}
// *** выборка из стека
bool StackPop( data& d )
{
if( top == NULL ) return false; // список пуст - стек пуст
else
{
d = top->inf; // выборка информации из 1-го эл-та списка
// 1-й эл-т исключается из списка, освобождается память
link curr = top;
top = top->next;
delete curr;
stSize--; // коррекция размера
return true;
}
}
// *** определение размера стека
long GetSize()
{
return stSize;
}
Программный пример для организация на односвязном линейном списке очереди FIFO можно разработать самостоятельно. Для линейного списка, представляющего очередь, необходимо будет сохранять: top - указатель на первый элемент списка, и bottom - на последний элемент.
Линейные связные списки иногда используются также для представления таблиц - в тех случаях, когда размер таблицы может существенно изменяться в процессе ее существования. Однако то обстоятельство, что доступ к элементам связного линейного списка может быть только последовательным, не позволяет применить к такой таблице эффективный двоичный поиск, что существенно ограничивает их применимость. Поскольку упорядоченность такой таблицы не может помочь в организации поиска, задачи сортировки таблиц, представленных линейными связными списками, возникают значительно реже, чем для таблиц в векторном представлении. Однако, в некоторых случаях для таблицы, хотя и не требуется частое выполнение поиска, но задача генерации отчетов требует расположения записей таблицы в некотором порядке. Для упорядочения записей такой таблицы применимы любые алгоритмы из описанных нами в лекции 6.
Некоторые алгоритмы, возможно, потребуют каких-либо усложнений структуры, например, быструю сортировку Хоара целесообразно проводить только на двухсвязном списке, в цифровой сортировке удобно создавать промежуточные списки для цифровых групп и т.д. Мы приведем два простейших примера сортировки односвязного линейного списка. В обоих случаях мы предполагаем, что определены типы данных:
typedef struct Node* link; // указатель на элемент списка
struct Node // элемент списка
{
int key; // ключ
data inf; // данные
link next; // указатель на элемент списка
};
В обоих случаях сортировка ведется по возрастанию ключем и параметром функции сортировки является указатель на начало неотсортированного списка, функция возвращает указатель на начало отсортированного списка. Прежний, неотсортированный список перестает существовать.
Пример 2.2 демонстрирует сортировку выборкой. Указатель newh является указателем на начало выходного списка, исходно - пустого. Во входном списке ищется максимальный элемент. Найденный элемент исключается из входного списка и включается в начало выходного списка. Работа алгоритма заканчивается, когда входной список станет пустым. Обратим внимание читателя на несколько особенностей алгоритма. Во-первых, во входном списке ищется всякий раз не минимальный, а максимальный элемент. Поскольку элемент включается в начало выходного списка (а не в конец выходного множества, как было в программном примере 1.7), элементы с большими ключами оттесняются к концу выходного списка и последний, таким образом, оказывается отсортированным по возрастанию ключей. Во-вторых, при поиске во входном списке сохраняется не только адрес найденного элемента в списке, но и адрес предшествующего ему в списке элемента - это впоследствии облегчает исключение элемента из списка (вспомните пример 1.4). В-третьих, обратите внимание на то, что у нас не возникает никаких проблем с пропуском во входном списке тех элементов, которые уже выбраны - они просто исключены из входной структуры данных.
{==== Программный пример 2.2 ====}
// Сортировка выборкой на 1-связном списке
link Sort( link& head )
{
link newh = NULL; // выходной список - пустой
link max, prev, pmax, curr;
while( head ) // цикл, пока не опустеет входной список
{
max = head; // нач.максимум - 1-й эл-т
prev = head;
curr = head->next; // поиск максимума во входном списке
while( curr )
{
if( curr->key > max->key )
{// запоминается адрес максимума и адрес предыдущего эл-та
max = curr;
pmax = prev;
}
prev = curr; // движение по списку
curr = curr->next;
}
// исключение максимума из входного списка
if( max == head )head = head->next;
else pmax->next = max->next;
max->next = newh; // вставка в начало выходного списка
newh = max;
}
return newh;
}
В программном примере 1.11 (ленкция 6) - иллюстрации сортировки вставками - из входного списка выбирается (и исключается) первый элемент и вставляется в выходной список "на свое место" в соответствии со значениями ключей. Сортировка включением на векторной структуре в примере 1.9 (лекция 6) требовала большого числа перемещений элементов в памяти. Обратите внимание на то, что в двух последних примерах пересылок данных не происходит, все записи таблиц остаются на своих местах в памяти, меняются только связи между ними - указатели.
{==== Программный пример 2.3 ====}
// Сортировка вставками на 1-связном списке
link SortI( link& head )
{
link newh = NULL; // выходной список - пустой
link curr, sel;
while( head ) // цикл, пока не опустеет входной список
{
sel = head; // эл-т, который переносится в выходной список
head = head->next; // продвижение во входном списке
if( newh == NULL || sel->key < newh->key )
{// выходной список пустой или элемент меньше 1-го- вставка в начало
sel->next = newh;
newh = sel;
}
else // вставка в середину или в конец
{
curr = newh;
// до конца выходного списка или пока ключ следующего
// эл-та не будет больше вставляемого
while( curr->next && curr->next->key < sel->key )
curr = curr->next;
// вставка в выходной список после эл-та cur
sel->next = curr->next;
curr->next = sel;
}
}
return newh;
}