Одним из способов организации обработки данных является стек. <...> Говорят, что стек работает по принципу LIFO (Last In – First Out) (последним пришел – первым ушел). <...> Стек – это структура с единственной точкой входа-выхода, которая называется вершиной стека (рис. <...> Укажем типичные операции при работе со стеком: • инициализация стека; • добавление элемента в стек; • исключение элемента из стека; • проверка стека на наличие в нем элементов. <...> Способы реализации Структура стека может быть реализована двумя способами [3,5]: • с использованием массивов; • с использованием динамических структур (линейных списков). <...> Отметим, что кроме непосредственно элементов хранящихся в стеке (для этого используется необходимое количество первых элементов массива), необходимо иметь указатель на вершину стека. <...> В этом случае описание стека имеет вид: struct stek { int d; stek *next;//указатель на следующий элемент списка // (стека) }; Схематичное представление стека на основе линейного списка приведено на рис. <...> Рассмотрим подпрограммы работы со стеком на основе линейных списков. void init(stek* &st) { st=NULL; } bool empty (stek* st) { return (st==NULL); } void push(stek* &st, int d) { stek *pv = new stek; // объявляем новую динамиче//скую переменную типа stek pv->d = d; // записываем значение, которое помеща//ется в стек pv->next = st; // связываем новый элемент стека с // предыдущим st = pv; // новый элемент стека становится его //вершиной } int pop(stek* &st) 8 { int temp = st->d; // извлекаем в переменную temp // значение в вершине стека stek *pv = st; // запоминаем указатель на вершину //стека, чтобы затем // освободить выделенную под него память st = st->next; // вершиной становится предшествую //щий top элемент delete pv; // освобождаем память, тем самым удали //ли вершину return temp; // возвращаем значение, которое было //в вершине } 1.3. <...> При этом в каждой группе изменить взаимный порядок следования. <...> Основные операции над очередью аналогичны операциям над стеком: • инициализация очереди; • добавление элемента в очередь; • исключение элемента из очереди <...>
Основы_алгоритмизации_и_программирования._Деревья.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
ОСНОВЫ АЛГОРИТМИЗАЦИИ
И ПРОГРАММИРОВАНИЯ.
ДЕРЕВЬЯ
Методические указания
Воронеж
Издательский дом ВГУ
2015
Стр.1
СОДЕРЖАНИЕ
ВВЕДЕНИЕ ............................................................................................................................ 4
1. СТЕКИ ................................................................................................................................ 5
1.1. Основные понятия ......................................................................................................... 5
1.2. Способы реализации ..................................................................................................... 5
1.3. Задачи для самостоятельного решения ....................................................................... 9
2. ОЧЕРЕДИ ........................................................................................................................... 9
2.1. Основные понятия ......................................................................................................... 9
2.2. Способы реализации ................................................................................................... 10
2.3. Задачи для самостоятельного решения ..................................................................... 15
3. . Структура программы С++ ......................................................................................... 15
4. ДЕРЕВЬЯ .......................................................................................................................... 17
4.1. Основные понятия и определения ............................................................................. 17
4.2. Способы представления деревьев .............................................................................. 22
4.3. Способы обхода деревьев ........................................................................................... 26
4.4. Рекурсивные алгоритмы работы с деревьями ........................................................... 27
4.4.1. Построение .................................................................................................................. 27
4.4.2. Поиск по дереву .......................................................................................................... 32
4.4.3. Удаление вершины из дерева .................................................................................... 35
4.4.4. Обработка значений в вершинах деревьев ............................................................... 38
4.4.5. Работа с деревьями-формулами ................................................................................ 40
4.4.5.1. Построение дерева-формулы, соответствующего выражению ........................... 41
4.4.5.2. Вывод дерева-формулы, соответствующего выражению .................................... 47
4.4.5.3. Вычисление значения выражения по дереву-формуле ........................................ 48
4.5. Нерекурсивные алгоритмы работы с деревьями ...................................................... 50
4.6. Программа работы с деревьями ................................................................................. 54
4.7. Задачи для самостоятельного решения ..................................................................... 55
Заключение ..................................................................................................................................................... 58
Литература ....................................................................................................................................................... 59
3
Стр.3
Рассмотрим реализацию стека на основе массива. Отметим, что кроме
непосредственно элементов хранящихся в стеке (для этого используется необходимое
количество первых элементов массива), необходимо иметь указатель
на вершину стека. Поэтому целесообразно объединить эти данные в
один класс. Таким образом, описание стека имеет вид:
class Stack
{
private:
enum {max = 10};
int st[max];
int top;
public:
Stack ( ) //конструктор
{
this->top = 0;
}
….
}
Отметим, что поле TOP хранит индекс верхнего элемента стека, а одновременно
с этим и количество элементов в стеке. Поэтому если TOP==0,
то стек пуст.
Схематичное изображение такого представления приведено на рис.
1.2. Вершина стека TOP содержит значение 3, т.е. стек состоит из 3 элементов:
7, 2 и 13. Если из этого стека будет считан элемент, то считается значение
13, а значение TOP сократится до 2. Если же необходимо добавить элемент
в стек, то сначала будет увеличено значение TOP, а затем на соответствующее
место в массиве будет записан новый элемент.
STEK
EL
TOP
3
7 2 13
1 2 3 4
...
...
MAXN
Рис. 1.2. Представление стека с помощью массива
Приведем методы, реализующие основные и дополнительные операции
работы со стеком на основе массива.
6
Стр.6
void push ( int var ) //добавить элемент в стек
{
st [ ++top ] = var;
}
int pop ( ) //извлечь элемент из стека
{
return st [ top-- ];
}
bool empty() //проверка стека на пустоту
{
return top==0;
}
void clear ( ) //очистить стек
{
top=0;
}
void print () //печать содержимого стека
{
int s2;
s2=this->top;
if (this->empty()==true){
cout << "Stack is empty.." << endl;
}
else{
cout << "Stack.." << endl;
while (this->empty()!=true)
{
cout << this->pop ( ) << endl;
}
this->top=s2;
}
}
Рассмотрим реализацию стека на основе динамических структур. В
этом случае описание стека имеет вид:
struct stek
{
int d;
stek *next;//указатель на следующий элемент списка
// (стека)
};
Схематичное представление стека на основе линейного списка приведено
на рис. 1.3.
7
Стр.7
TOP
13
2
7
Рис. 1.3. Представление стека с помощью списка
При извлечении элемента из списка, представленного на рис. 1.3, будет
получено число 13; указатель TOP будет перенастроен на следующий
элемент стека (2); а память, отведенная под хранение элемента 13, будет освобождена.
Если же к списку необходимо добавить элемент, то будет создано
новое звено списка, в которое будет помещен добавляемый элемент.
Затем будет организована ссылка с нового элемента списка на текущую
вершину стека, а сам указатель TOP будет перенастроен на новый элемент.
Сравнивая рис. 1.2 и рис. 1.3 видно, что в случае реализации стека на основе
динамических структур память расходуется существенно эффективнее,
т.к. выделяется и освобождается по мере необходимости. Поэтому при решении
практических задач обычно используется реализация стека на основе
списка [3].
Рассмотрим подпрограммы работы со стеком на основе линейных
списков.
void init(stek* &st)
{
st=NULL;
}
bool empty (stek* st)
{
return (st==NULL);
}
void push(stek* &st, int d)
{
stek *pv = new stek; // объявляем новую динамиче//скую
переменную типа stek
pv->d = d; // записываем значение, которое помеща//ется
в стек
pv->next = st; // связываем новый элемент стека с
// предыдущим
st = pv; // новый элемент стека становится его
//вершиной
}
int pop(stek* &st)
8
Стр.8