Очередь
Из динамических элементов формируется цепочка. Динамический элемент хранит адрес следующего динамического элемента.
Очередь работает по тому же принципу, что и очередь в магазине: "первым пришел, первым ушел". Элементы добавляются в конец очереди, а берутся из начала. Для работы необходимо знать начало и конец очереди.
Указатель у последнего элемента в очереди хранит нулевое значение
Рисунок 1.10.2.
Стек
Стек работает по принципу "первым пришел, последним ушел". Элементы добавляются и берутся с одного конца, который называется вершина стека.
Рисунок 1.10.3.
Список
Список порядок работы с элементами списка не определен. Можно, например, вставить или убрать элемент из любой части списка.
Рисунок 1.10.4.
Может использоваться кольцевой список, в котором соединены начало и конец.
Двунаправленный список
Формируется из динамических элементов с двумя указателями.
Рисунок 1.10.5.
Рисунок 1.10.6.
Может использоваться кольцевой список, в котором начало и конец соединены.
Дерево
Дерево состоит из элементов, которые называются узлами или вершинами.
Рисунок 1.10.7.
Узлы соединены направленными дугами X->Y. X называется предшественником (родителем) Y. Y - называется потомком. Дерево имеет одну вершину, которая не имеет предшественников. Она называется корнем дерева. Вершины, которые не имеют потомков, называются листьями.
Дерево может формироваться из динамических элементов с двумя указателями.
Рисунок 1.10.8.
Программа для организации очереди.
Будет создана очередь из произвольного количества целых положительных чисел. Признак окончания ввода - отрицательное число.
#include < iostream.h>
#include < conio.h>
/* Описание структурного элемента, info - информационное поле, next -указатель на следующий элемент. */
struct ELEM
{
int info;
ELEM *next;
};
void main()
{
// Указатели на элементы очереди: первый, последний, текущий, старый, новый
ELEM *nach, *tek, *old, *kon, *new_n;
int i=1;
nach=0;
kon=0;
cout << "\n Введите произвольное кол-во целых чисел";
cout << "\n признак окончания ввода - отрицательное число";
// Создается очередь из целых чисел
do
{
// Ввод числа
cout << "\n Введите целое число";
cin >> i;
if (i<=0) break; // Прекращение цикла
// Создание очередного элемента
new_n=new ELEM; /* Выделяется память под новый элемент, адрес выделенной памяти записывается в new_n */
new_n-> info=i; /* Присваивается значение информационному полю нового элемента*/
new_n-> next=0; /* Присваивается значение указателю нового элемента */
if (nach)
{ // Если очередь не пуста, очередной элемент добавляется в конец очереди
kon-> next=new_n;
kon=new_n;
}
else
{
/* Если очередь пуста, начало и конец очереди будут указывать на один и тот же элемент */
nach=new_n;
kon=new_n;
}
}
while (i> 0);
// Пример обработки элементов
// Элементы отображаются на экране и удаляются из очереди
while (nach)
{
old=nach;
cout << "\n элемент "<< nach-> info; // Выводим элемент на экран
nach=nach-> next; // Переходим к следующему элементу очереди
delete old; // Очищаем память, которую занимал первый элемент
}
getch();
}
Фрагмент программы для реализации стека
Создание стека из элементов 9, 10,... 16.
nach=0; // nach - вершина стека
for (i=9; i<=16; i++)
{
// Создание очередного элемента
new_n=new ELEM;
new_n-> info=i;
if (nach)
{ // Если стек не пуст, очередной элемент добавляется в вершину стека
new_n-> next=nach;
nach=new_n;
}
else
{ // иначе стек будет состоять из одного элемента
new_n-> next=0;
nach=new_n;
}