Списки. Очередь. Стек. Дек

Другими словами, элемент двусторонне связанного списка (doubly linked list) — это запись, содержащая три поля: key (ключ) и два указателя — next (следующий) и prev (от previous—предыдущий). Помимо этого, элементы списка могут содержать дополнительные данные. Если х — элемент списка, то next указывает на следующий элемент списка, а prev — на предшествующий. Если prev{х}=nil, то у элемента х нет предшествующего: это голова (head) списка. Если next{х}= nil, то х — последний элемент списка или, как говорят, его хвост (tail).

Прежде  чем двигаться по указателям, надо знать хотя бы один элемент списка. В различных ситуациях используются разные виды списков. В односторонне связанном (singly linked) списке отсутствуют поля prev. В упорядоченном (sorted) списке элементы расположены в порядке возрастания ключей, так что у головы списка ключ наименьший, а у хвоста списка — наибольший, в отличие от неупорядоченного (unsorted) списка. В кольцевом списке (circular list) поле prev головы списка указывает на хвост списка, а поле next хвоста списка указывает на голову списка.

Если иное не оговорено особо, под списком мы будем понимать неупорядоченный двусторонне связанный список.

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

 

Здесь А, В, С, D и Е— произвольные ячейки в памяти, а Л — пустая связь. Программа, в которой используется такая таблица, имела бы, в случае последовательного распределения, дополнительную переменную или константу, значение которой показывает, что таблица состоит из пяти элементов; эту же информацию можно задать с помощью признака конца ("пограничника"), снабдив им элемент 5 или следующую ячейку, В случае связанного распределения в программе имеется переменная связи или константа, которая указывает на А, а отправляясь от А, можно найти все другие элементы списка.

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

Здесь FIRST — переменная связи, указывающая на первый узел в списке.

Теперь мы можем сопоставить  эти две основные формы хранения информации:

1) Связанное распределение требует дополнительного пространства в памяти для связей. В некоторых ситуациях этот фактор может быть доминирующим. Однако мы часто встречаемся с таким положением, когда информация в узле не занимает все слово целиком, и поэтому место для поля связи уже существует. Кроме того, во многих применениях несколько элементов можно объединять в один узел, и, следовательно, потребуется лишь одна связь ни несколько элементов информации. Но гораздо важнее тот факт, что при использовании связанной памяти часто возникает неявный выигрыш в памяти, поскольку можно совмещать общие части таблиц; и во многих Случаях последовательное распределение не будет столь эффективным, как связанное, если так или иначе не остается пустым довольно большое количество ячеек памяти.

2) Легко исключить элемент, находящийся внутри связанного списка. Например, чтобы исключить элемент 3, нам необходимо только изменить связь в элементе 2. При последовательном же распределении такое исключение обычно потребует перемещения значительной части списка вверх на другие места памяти.

3) Если используется связанная схема, то легко включить элемент в список. Например, чтобы включить элемент в (1), необходимо изменить лишь две связи:

Такая операция заняла бы значительное время при работе с длинной  последовательной таблицей.

4) При последовательном распределении значительно быстрее выполняются обращения к произвольным частям списка. Доступ к k-му элементу списка, если k — переменная, для последовательного распределения занимает фиксированное время, а для связанного — необходимо k итераций, чтобы добраться до требуемого места. Таким образом, полезность связанной памяти основывается на том факте, что в огромном большинстве приложений мы будем продвигаться по списку последовательно, а не произвольным образом; если нам необходимы элементы в середине или в нижней части списка, то постараемся завести дополнительную переменную связи или список переменных связи, которые указывают на соответствующие места в списке.

5) При использовании схемы со связями упрощается задача объединения двух списков или разбиения списка на части.

6) Схема со связями годится для структур более сложных, чем простые линейные списки. У нас может быть переменное количество списков, размер которых непостоянен; любой узел одного списка может быть началом другого списка; в одно и то же время узлы могут быть связаны в несколько последовательностей, соответствующих различным спискам, и т.д.

7) На многих машинах простые операции, такие, как последовательное продвижение по списку, выполняются несколько быстрее для последовательных списков.

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

В следующих нескольких примерах мы будем ради удобства предполагать, что узел — это одно слово и что оно разделено на два поля INFO и LINK:

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

Циклическое кольцо или  список (circular list или ring) – файл, у которого нет определенного начала и конца; каждый элемент файла содержит указатель на начало следующего элемента; при этом «последний» элемент указывает на «первый», так что к списку можно обратиться с любого элемента.

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

Предположим, в узлах имеется  два поля: INFO и LINK. Переменная связи PTR указывает на самый правый узел списка, a LINK (PTR) является адресом самого левого узла.

Разного рода расщепления одного циклического списка на два, соответствуют операциям  конкатенации (объединения) и деконкатенации (разъединения) цепочек.

Таким образом, мы видим, что циклические  списки можно использовать не только для представления структур, которым  свойственна цикличность, но также  для представления линейных структур; циклический список с одним указателем на последний узел, по существу, эквивалентен простому линейному списку с двумя указателями на начало и конец. В связи с этим наблюдением возникает естественный вопрос: Как найти конец списка, имея в виду круговую симметрию? Пустой связи Л, которая отмечает конец, не существует. Проблема решается так: если мы выполняем некоторые операции, двигаясь по списку от одного узла к следующему, то мы должны остановиться, когда мы вернулись к исходному месту (предполагая, конечно, что исходное место все еще присутствует в списке).

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

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

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

1.2 Динамические информационные  структуры

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

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

В языке C++ предусмотрена возможность использования динамических величин. Для них выделение и очистка памяти происходит не на этапе трансляции, а в ходе выполнения самой программы. Для работы с динамическими величинами в C++ предусмотрен специальный тип значений - ссылочный. Этот тип не относится ни к простым, ни к составным. Переменные ссылочного типа, или указатели, являются статическими переменными. Значением переменной ссылочного типа является адрес ячейки - места в памяти соответствующей динамической величины. Свое значение ссылочная переменная получает в процессе выполнения программы, в момент появления соответствующей динамической величины.

Значением указателя является адрес  ячейки, начиная с которой будет размещена в памяти соответствующая динамическая величина.

На этой схеме р. - имя указателя; звездочкой изображено значение указателя, а стрелка отражает тот факт, что значением указателя является адрес объекта (ссылка на объект), посредством которого объект и доступен в программе.

В некоторых случаях возникает  необходимость в качестве значения указателя принять «пустую» ссылку, которая не связывает с указателем никакого объекта. Такое значение в C++ задается служебным словом null и принадлежит любому ссылочному типу. Результаты выполнения оператора p=null можно изобразить следующим образом:

Функция <тип> i = new <тип>, где i – это имя переменной, выполняет две функции:

1) резервирует место в памяти для размещения динамического объекта соответствующего типа с именем i;

2) указателю i присваивает адрес динамического объекта i.

Динамические объекты размещаются  по типу стека в специальной области памяти — так называемой «куче» свободной от программ и статических переменных. Символ -> после имени указателя означает, что речь идет не о значении ссылочной переменной, а о значении того динамического объекта, на который указывает эта ссылочная переменная.

Если в процессе выполнения программы  некоторый динамический объект р, созданный в результате выполнения оператора new, становится ненужным, то его можно уничтожить (очистить выделенное ему место в памяти) с помощью стандартной процедуры delete. В результате выполнения оператора вида      delete p динамический объект, на который указывает ссылочная переменная р, прекращает свое существование, занимаемое им место в памяти становится свободным, а значение указателя р становится неопределенным.

Значение одного указателя можно  присвоить другому указателю того же типа. Можно также указатели одинакового типа сравнивать друг с другом.

Стандартные процедуры new и delete позволяют динамически порождать программные объекты и уничтожать их, что дает возможность использовать память машины более эффективно.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include "stdafx.h"

#include "iostream"

//односвязный список

struct list_one

{

int info;

list_one*next;

};

 

//двусвязный список

struct list_two

{

int info;

list_two *next,*back;

};

 

//стек

struct stack

{

int info;

stack *p;

};

 

//создание односвязного  списка со сторожем

void push_list_one(list_one*&head)

{

head=new list_one;//сторож

list_one *q,*p;

q=head;

std::cout<<"\nвведите  элементы списка. 0 - конец ввода\n";

do

{

p=new list_one;

std::cin>>p->info;

q->next=p;

q=q->next;

}while(q->info!=0);

q->next=NULL;

}

 

//вывод односвязного  списка на экран

void vivod_list_one(const list_one*head)

{

head=head->next;

while(head)

{

std::cout<<head->info<<" ";

head=head->next;

}

std::cout<<"\n";

}

 

//создание двусвязного  циклического списка со сторожем

void push_list_two(list_two*&head)

{

head=new list_two;//сторож

list_two *q,*p;

q=head;

std::cout<<"\nвведите  элементы списка. 0 - конец ввода\n";

do

{

p=new list_two;

std::cin>>p->info;

q->next=p;

p->back=q;

q=q->next;

}while(q->info!=0);

q->next=head;

head->back=q;

}

 

//вывод односвязного  списка на экран

void vivod_list_two(list_two*head)

{

list_two *p=head;

head=head->next;

while(p!=head)

{

std::cout<<head->info<<" ";

head=head->next;

}

std::cout<<"\n";

}

 

//добавление элемента в стэк

bool push_stack(stack *&top)

{

stack *q=new stack;

std::cin>>q->info;

q->p=top;

bool b=true;

if (q->info==0) b=false;

top=q;

return b;

}

 

//взятие элемента из  стека

int pop_stack(stack *&top)

{

int info = top->info;

stack *q=top;

top=top->p;

delete q;

return info;

}

 

void create_stack(stack*&Stack)

{

Stack=new stack;

std::cout<<"\nвведите элементы стэка. 0 - конец ввода\n";

int len=0;

while(push_stack(Stack))len++;

std::cout<<"\nСтек:\n";

for(int i=0; i<=len;++i)

std::cout<<pop_stack(Stack)<<" ";

}

 

 

 

void main()

{

system("chcp 1251 > nul");