Программа для организации очереди.
Для работы с динамическими структурами
Дерево может формироваться из динамических элементов с двумя указателями.
Дерево состоит из элементов, которые называются узлами или вершинами.
Дерево
Двунаправленный список формируется из динамических элементов с двумя указателями.
Двунаправленный список
Список
Стек
Указатель у последнего элемента в очереди хранит нулевое значение.
Очередь
Из динамических элементов формируется цепочка. Динамический элемент хранит адрес следующего динамического элемента.
Существует 5 основных видов динамических структур:
· очередь
· стек
· список
· двунаправленный список
· дерево
Очередь работает по тому же принципу, что и очередь в магазине: "первым пришел, первым ушел". Элементы добавляются в конец очереди, а берутся из начала. Для работы необходимо знать начало и конец очереди.
Стек работает по принципу "первым пришел, последним ушел". Элементы добавляются и берутся с одного конца, который называется вершина стека.
Порядок работы с элементами списка не определен. Можно, например, вставить или убрать элемент из любой части списка.
Может использоваться кольцевой список, в котором соединены начало и конец.
Может использоваться кольцевой список, в котором начало и конец соединены.
Узлы соединены направленными дугами X->Y(от Х к Y). X называется предшественником (родителем) Y. Y - называется потомком.
Дерево имеет одну вершину, которая не имеет предшественников. Она называется корнем дерева. Вершины, которые не имеют потомков, называются листьями.
Примеры программ (фрагментов программ)
Задача. Создание очереди из произвольного количества целых положительных чисел. Признак окончания ввода - отрицательное число.
#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();}