Связный список

Структура данных, представляющая собой конечное множество упорядоченных элементов (узлов), связанных друг с другом посредством указателей, называется связным списком. Каждый элемент связного списка содержит поле с данными, а также указатель (ссылку) на следующий и/или предыдущий элемент. Эта структура позволяет эффективно выполнять операции добавления и удаления элементов для любой позиции в последовательности. Причем это не потребует реорганизации структуры, которая бы потребовалась в массиве. Минусом связного списка, как и других структур типа «список», в сравнении его с массивом является отсутствие возможности работать с данными в режиме произвольного доступа, т. е. список – структура последовательно доступа, в то время как массив – произвольного. Последний недостаток снижает эффективность ряда операций.

Каждый узел односвязного (однонаправленного связного) списка содержит указатель на следующий узел (рис. 2.7). Из одной точки можно попасть лишь в следующую точку, двигаясь тем самым в конец. Так получается своеобразный поток, текущий в одном направлении.

Рисунок 2.7 – Односвязный список

Повторим уже ранее сказанное. На изображении каждый из блоков представляет элемент (узел) списка. Head list – заголовочный элемент списка (для него предполагается поле next). Он не содержит данные, а только ссылку на следующий элемент. На наличие данных указывает поле info, а ссылки – поле next (далее за ссылки будет отвечать и поле prev). Признаком отсутствия указателя является поле nil.

Односвязный список не самый удобный тип связного списка, т. к. из одной точки можно попасть лишь в следующую точку, двигаясь тем самым в конец. Когда кроме указателя на следующий элемент есть указатель на предыдущий, то такой список называется двусвязным.

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

Рисунок 2.8 – Двусвязный список

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

Когда количество памяти, по каким-либо причинам, ограничено, тогда альтернативой двусвязному списку может послужить XOR-связный список (рис. 2.9). Последний использует логическую операцию XOR (исключающее «ИЛИ», строгая дизъюнкция), которая для двух переменных возвращает истину лишь при условии, что истинно только одно из них, а второе, соответственно, ложно. Таблица истинности операции:

a	b	a ⊕ b

В качестве переменных a и b у нас выступают адреса (на следующий и предыдущий элемент), над которыми выполняется операция XOR, возвращающая реальный адрес следующего элемента.

Рисунок 2.9 – XOR-связный список

Еще один вид связного списка – кольцевой список. В кольцевом односвязном списке последний элемент ссылается на первый. В случае двусвязного кольцевого списка, плюс к этому, первый элемент ссылается на последний (рис. 2.10). Таким образом, получается зацикленная структура.

Рисунок 2.10 – Кольцевой связный список

Рассмотрим основные операции над связными списками.

На примере двусвязного списка, разберем принцип работы этой структуры данных. При реализации списка удобно использовать структуры (в Pascal – записи).

Общая форма описания узла двунаправленного связного списка и указателя на первый элемент списка:

struct имя_списка

{

информационное поле 1;

информационное поле 2;

…

информационное поле n;

указатель на следующий элемент;

указатель на предыдущий элемент;

};

имя_списка *указатель_на_голову_списка

Пример:

struct DoubleList //описание узла списка

{

int data; //информационное поле

DoubleList *next; //указатель на следующий элемент

DoubleList *prev; //указатель на предыдущий элемент

};

DoubleList *head; //указатель на первый элемент списка

Теперь, предполагая, что описан узел и указатель на голову списка (см. пример выше), напишем функции обработки списка.

Опишем функцию AddList, которая в качестве параметров принимает значение будущего узла и его адрес, после чего создает в списке заданный узел:

void AddList(int value, int position)

{

DoubleList *node=new DoubleList; //создание нового элемента

node->data=value; //присвоение элементу значения

if (head==NULL) //если список пуст

{

node->next=node; //установка указателя next

node->prev=node; //установка указателя prev

head=node; //определяется голова списка

}

else

{

DoubleList *p=head;

for(int i=position; i>1; i--) p=p->next;

p->prev->next=node;

node->prev=p->prev;

node->next=p; //добавление элемента

p->prev=node;

}

cout<<"\nЭлемент добавлен...\n\n";

}

Функция DeleteList для удаления элемента использует его адрес:

int DeleteList(int position)

{

if (head==NULL) { cout<<"\nСписок пуст\n\n"; return 0; }

if (head==head->next) //если это последний элемент в списке

{

delete head; //удаление элемента

head=NULL;

}

else

{

DoubleList *a=head;

for (int i=position; i>1; i--) a=a->next;

if (a==head) head=a->next;

a->prev->next=a->next; //удаление элемента

a->next->prev=a->prev;

delete a;

}

cout<<"\nЭлемент удален...\n\n";

}

Если список пуст, то выводится сообщение, извещающее об этом, и функция возвращается в место вызова.

Функция PrintList выводит на экран все элементы списка:

void PrintList()

{

if (head==NULL) cout<<"Список пуст\n";

else

{

DoubleList *a=head;

cout<<"\nЭлементы списка: ";

do

{

cout<<a->data<<" ";

a=a->next;

} while(a!=head); cout<<"\n\n";

}

}

Вывести список можно и посредством цикла, то есть итеративно. Теперь соединим эти три функции в одной программе, а также напишем главную функцию, отвечающую за вызов подпрограмм:

struct DoubleList //описание узла списка

{

int data; //информационное поле

DoubleList *next; //указатель на следующий элемент

DoubleList *prev; //указатель на предыдущий элемент

};

DoubleList *head; //указатель на первый элемент списка

void AddList(int value, int position) //добавление элемента

{

DoubleList *node=new DoubleList; //создание нового элемента

node->data=value; //присвоение элементу значения

if (head==NULL) //если список пуст

{

node->next=node; //установка указателя next

node->prev=node; //установка указателя prev

head=node; //определяется голова списка

}

else

{

DoubleList *p=head;

for(int i=position; i>1; i--) p=p->next;

p->prev->next=node;

node->prev=p->prev;

node->next=p; //добавление элемента

p->prev=node;

}

cout<<"\nЭлемент добавлен...\n\n";

}

int DeleteList(int position) //удаление элемента

{

if (head==NULL) { cout<<"\nСписок пуст\n\n"; return 0; }

if (head==head->next) //если это последний элемент в списке

{

delete head; //удаление элемента

head=NULL;

}

else

{

DoubleList *a=head;

for (int i=position; i>1; i--) a=a->next;

if (a==head) head=a->next;

a->prev->next=a->next; //удаление элемента

a->next->prev=a->prev;

delete a;

}

cout<<"\nЭлемент удален...\n\n";

}

void PrintList() //вывод списка

{

if (head==NULL) cout<<"Список пуст\n";

else

{

DoubleList *a=head;

cout<<"\nЭлементы списка: ";

do

{

cout<<a->data<<" ";

a=a->next;

} while(a!=head); cout<<"\n\n";

}

}

void main() //главная функция

{

int value, position, x;

do

{

cout<<"1. Добавить элемент"<<endl;

cout<<"2. Удалить элемент"<<endl;

cout<<"3. Вывести список"<<endl;

cout<<"0. Выйти"<<endl;

cin>>x;

switch (x)

{

case 1:

cout<<"Значение > "; cin>>value;

cout<<"Позиция > "; cin>>position;

AddList(value, position); break;

case 2:

cout<<"Позиция > "; cin>>position;

DeleteList(position); break;

case 3: PrintList(); break;

}

} while (x!=0);

}

От программы требуется, чтобы она выполнялась до тех пор, пока не выполнен выход из цикла do функции main (для выхода из него пользователь должен ввести 0). По этой причине в конце функции main не был описан оператор, тормозящий программу.

Стек

Стек характерен тем, что получить доступ к его элементам можно лишь с одного конца, называемого вершиной стека; иначе говоря: стек – структура данных типа "список", функционирующая по принципу LIFO (last in — first out, «последним пришёл — первым вышел»). Графически его удобно изобразить в виде вертикального списка (рис. 2.11), например, стопки книг, где чтобы воспользоваться одной из них, и не нарушить установленный порядок, нужно поднять все те книги, что лежат выше нее, а положить книгу можно лишь поверх всех остальных.

Рисунок 2.11 – Стек

Впервые стек был предложен в 1946 году Аланом Тьюрингом, как средство возвращения из подпрограмм. В 1955 году немцы Клаус Самельсон и Фридрих Бауэр из Технического университета Мюнхена использовали стек для перевода языков программирования и запатентовали идею в 1957 году. Но международное признание пришло к ним лишь в 1988 году.

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

Стек, чаще всего, реализуется на основе обычных массивов, односвязных и двусвязных списков. В зависимости от конкретных условий, выбирается одна из этих структур данных.

Основными операциями над стеками являются:

· добавление элемента;

· удаление элемента;

· чтение верхнего элемента.

В языках программирования эти три операции, обычно дополняются и некоторыми другими. Вот, например, список функций C++ для работы со стеком:

· push() – добавить элемент;

· pop() – удалить элемент;

· top() – получить верхний элемент;

· size() – размер стека;

· empty() – проверить стек на наличие элементов.

Данные функции входят в стандартную библиотеку шаблонов C++ – STL, а именно в контейнер stack. Далее будет рассмотрен пример работы с контейнером stack, а пока разберем стек, реализованный на основе массива.

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

· Creation () – создание пустого стека;

· Full () – проверка стека на пустоту;

· Add () – добавление элемента;

· Delete () – удаление элемента;

· Top () – вывод верхнего элемента;

· Size () – вывод размера стека.

Как таковых пользовательских операций тут всего четыре: Add, Delete, Top, Size. Они доступны из консоли. Функция Creation – создает пустой стек сразу после запуска программы, а Full проверяет возможность выполнения пользовательских операций.

const int n=3;

struct Stack

{

int A[n];

int count;

};

void Creation(Stack *p) //создание стека

{ p->count=0; }

int Full(Stack *p) //проверка стека на пустоту

{

if (p->count==0) return 1;

else if (p->count==n) return -1;

else return 0;

}

void Add(Stack *p) //добавление элемента

{

int value;

cout<<"Введите элемент > "; cin>>value;

p->A[p->count]=value;

p->count++;

}

void Delete(Stack *p) //удаление элемента

{ p->count--; }

int Top(Stack *p) //вывод элементов

{ return p->A[p->count-1]; }

int Size(Stack *p) //размер стека

{ return p->count; }

void main() //главная функция

{

Stack s;

Creation(&s);

char number;

do

{

cout<<"1. Добавить элемент"<<endl;

cout<<"2. Удалить элемент"<<endl;

cout<<"3. Вывести верхний элемент"<<endl;

cout<<"4. Узнать размер стека"<<endl;

cout<<"0. Выйти"<<endl;

cout<<"Номер команды > "; cin>>number;

switch (number)

{

case '1':

if (Full(&s)==-1) cout<<endl<<"Стек заполнен\n\n";

else

{

Add(&s);

cout<<endl<<"Элемент добавлен в стек\n\n";

}

break;

case '2':

if (Full(&s)==1) cout<<endl<<"Стек пуст\n\n";

else

{

Delete(&s);

cout<<endl<<"Элемент удален из стека\n\n";

}

break;

case '3':

if (Full(&s)==1) cout<<endl<<"Стек пуст\n\n";

else cout<<"\nЭлементы стека: "<<Top(&s)<<"\n\n";

break;

case '4':

if (Full(&s)==1) cout<<endl<<"Стек пуст\n\n";

else cout<<"\nРазмер стека: "<<Size(&s)<<"\n\n";

break;

case '0': break;

default: cout<<endl<<" Команда не определена\n\n";

break;

}

} while(number!='0');

}

Как видно, часто встречающимся элементом программы является поле count структуры stack. Оно исполняет роль указателя на «голову» стека. Например, для удаления элемента достаточно сдвинуть указатель на одну ячейку назад. Основная часть программы зациклена, и чтобы выйти из нее, а, следовательно, и из приложения вообще, нужно указать 0 в качестве номера команды.

Многие языки программирования располагают встроенными средствами организации и обработки стеков. Одним из них, как подчеркивалось ранее, является C++. Разберем принципы функционирования контейнера stack стандартной библиотеки шаблонов STL. Во-первых, stack – контейнер, в котором добавление и удаление элементов осуществляется с одного конца, что свойственно непосредственно стеку. Использование стековых операций не требует их описания в программе, т. е. stack здесь предоставляет набор стандартных функций. Для начала работы со стеком, в программе необходимо подключить библиотеку stack:

#include <stack>

и в функции описать его самого:

stack < тип данных > имя стека;

Обратите внимание, что скобки, обособляющие тип данных, указываются здесь не как подчеркивающие общую форму записи, а как обязательные при описании стека.

Теперь в программе можно использовать методы контейнера. Следующая программа является аналогом предыдущей, но вместо пользовательских функций в ней используются функции контейнера stack.

#include <stack>

void main() //главная функция

{

stack <int> S; //создание стека S типа int

char number; int value;

do

{

cout<<"1. Добавить элемент"<<endl;

cout<<"2. Удалить элемент"<<endl;

cout<<"3. Получить верхний элемент"<<endl;

cout<<"4. Узнать размер стека"<<endl;

cout<<"0. Выйти"<<endl;

cout<<"Номер команды > "; cin>>number;

switch (number)

{

case '1': //добавление элемента

cout<<"Значение > "; cin>>value;

S.push(value);

cout<<endl<<"Элемент добавлен в стек\n\n";

break;

case '2': //удаление элемента

if (S.empty()==true) cout<<"\nСтек пуст\n\n";

else

{

S.pop();

cout<<endl<<"Элемент удален из стека\n\n";

}

break;

case '3': //вывод верхнего элемента

if (S.empty()==true) cout<<"\nСтек пуст\n\n";

else cout<<"\nВерхний элемент стека: "<<S.top()<<"\n\n";

break;

case '4': //вывод размера стека

if (S.empty()==true) cout<<"\nСтек пуст\n\n";

else cout<<"\nРазмер стека: "<<S.size()<<"\n\n";

break;

case '0': break; //выход

default: cout<<endl<<"Команда не определенная\n\n";

break;

}

} while(number!='0');

}

Использование стандартных средств C++ позволило заметно сократить общий объем программы, и тем самым упростить листинг. По своему функционалу данная программа полностью аналогична предыдущей.