Алгоритм формирования первых 2-х элементов
Начало алгоритма
1. Описать структуру переменной (рекомендуется шаблон структуры описывать глобально):
Алгоритм формирования первых 2-х элементов
Начало алгоритма
1. Описать структуру переменной (рекомендуется шаблон структуры описывать глобально):
struct Stack {
int info;
Stack *Next;
} ;
2. Объявить два указателя на структуру:
Stack *begin (вершина стека), *t (текущий элемент);
3. Стек пуст, поэтому вершина в NULL: begin = NULL; (такое значение необходимо для первого вталкиваемого в стек элемента); графически это можно изобразить так:
4. Захват памяти под первый (текущий) элемент:
t = new Stack;
формируется конкретный адрес (А1) для первого элемента, т.е. t равен А1.
5. Считываем информацию (i1);
а) формируем информационную часть:
t -> info = i1;
б) значение вершины - в адресную часть (там был NULL)
t -> Next = begin;
6. Вершину стека переносим на созданный (1-ый) элемент:
begin = t;
7. Опять захватываем память (под второй элемент):
t = new Stack;
имеем конкретный адрес (A2) для второго элемента, т.е. по шагам
8. Считываем для него информацию (i2);
а) формируем информационную часть:
t -> info = i2;
б) в адресную часть - значение вершины, т.е. адрес предыдущего (первого) элемента (А1):
t -> Next = begin;
9. Вершину стека снимаем с первого и устанавливаем на новый элемент (A2):
begin = t;
Конец алгоритма
Алгоритм добавления текущего элемента
Начало алгоритма
1. Захват памяти под текущий элемент (формирование конкретного адреса).
2. Формирование информационной части.
3. Формирование адресной части:
- в адресную часть значение вершины;
- в вершину значение адреса нового элемента.
Конец алгоритма
Алгоритм извлечения элемента из стека (обработка и уничтожение)
Начало алгоритма
1. Используя вершину стека, выдавливаем последний занесенный элемент:
t = begin;
2. Обрабатываем информационную часть (t ->i nfo) (выводим на экран).
3. Вершине стека присваиваем значение адресной части, т.е. вершину переставляем на следующий элемент: begin = t->Next;
4. Уничтожаем обработанный элемент, т.е. освобождаем занятую под него память: delete t;
Для первых двух элементов рассмотрим подробно:
1) t = begin;
2) t -> info; например, печать i
3) begin = t -> Next; , т.е. begin равен A1
4) delete t;
Конец алгоритма
А теперь давайте рассмотрим алгоритмы решения конкретного примера.
Задача. Сформировать стек, для простоты состоящий из целых положительных чисел (признаком окончания может быть отрицательное число, его в стек не заносим). Просмотреть стек, не изменяя вершины. Найти в стеке максимальный элемент и его порядковый номер, одновременно освобождая память, занятую просмотренным элементом.
Программа должна получить следующую структуру данных:
|
begin |
ik |
p |
ik-1 |
... |
i1 |
NULL |
Декларируем структурный тип данных глобально:
struct Stack {
int info;
Stack *Next;
} ;
Формирование стека из k элементов
Начало алгоритма
1. Декларируем объекты int i, kol = 0; где i – дополнительная переменная, kol - счетчик элементов;
Stack *begin = NULL, (стек пуст) *t;
2. Начало бесконечного цикла, например while(1)
а) считывание информации для текущего элемента (ввод i);
б) если i<0 выход из цикла - break;
в) захват памяти под текущий элемент: t = new Stаck;
г) формирование информационной части
t -> info = i;
д) значение вершины стека заносим в адресную часть текущего элемента (для первого элемента NULL):
t -> Next = begin;
е) вершину стека переставляем на начало только что созданного элемента: begin = t;
ж) счетчик элементов увеличиваем на единицу: kol++;
3. Конец цикла.
4. Вывод сообщения: «Kol elementov =… ».
Конец алгоритма
Просмотр стека
Начало алгоритма
1. Устанавливаем текущий указатель на вершину. Проверяем, не пуст ли стек. Если begin=NULL, то стек пуст (выдаем сообщение, и либо завершаем работу, либо переходим на его формирование).
2. Если стек не пуст начинаем цикл, выполняя до тех пор, пока t != NULL, т.е. не дошли до последнего.
а) выводим на печать информационную часть:
printf(“ Элемент: %d”, t -> info);
б) переставляем текущий указатель на следующий элемент:
t = t -> Next;
3. Конец цикла.
Конец алгоритма
Поиск максимального элемента
Начало алгоритма
1. Устанавливаем указатель текущего элемента на вершину:
t = begin;
(можно проверить, не пустой ли стек).
2. Положим, что максимальный - это элемент вершины:
int max = t -> info;
int nom_max = k; - номер элемента вершины, т.е. последнего.
3. Начало цикла, используем конструкцию do-while: do (выполнять)
а) begin = t -> Next; - переставляем вершину стека на следующий элемент, а указатель t остался на k-ом;
б) проверяем, если (t->info > max), заменяем max=t->info; и nom_max=k;
в) освобождаем память просмотренного элемента t : delete t;
г) t = begin; теперь и вспомогательный указатель устанавливаем на следующий элемент и уменьшаем номер текущего элемента: k--;
4. Конец цикла, выполняющегося до тех пор пока t != NULL.
5. Вывод на экран найденных значений max и nom_max.
Конец алгоритма
Варианты заданий
Написать программу, создающую стек из случайных целых чисел и вычислить среднее арифметическое. (Использование датчика случайных чисел рассмотрено в работе «Сортировка и поиск»)
1. Создать стек из случайных целых чисел, лежащих в диапазоне –50 до +50 и преобразовать его в два стека. Первый должен содержать только положительные числа, а второй – только отрицательные. Порядок следования чисел должен быть сохранен.
2. Создать стек из случайных целых чисел и удалить из него записи с четными числами.
3. Создать стек из случайных целых чисел, лежащих в диапазоне от –10 до 10 и удалить из него записи с отрицательными числами.
4. Создать стек из случайных целых чисел и поменять местами крайние элементы.
5. Создать стек из случайных целых чисел и удалить элементы стека, заканчивающиеся на цифру 5.
6. Создать стек из случайных целых чисел и поменять местами элементы, содержащие максимальное и минимальное значения.
7. Создать стек из случайных целых чисел. Перенести в другой стек все элементы, находящиеся между вершиной и элементом с максимальным значением.
8. Создать стек из случайных целых чисел. Перенести в другой стек все элементы находящиеся между вершиной и элементом с минимальным значением.
9. Создать стек из случайных чисел и определить сколько элементов стека находится между минимальным и максимальным элементами, удалить их.
10. Создать стек из случайных чисел и определить, сколько элементов стека имеют значения меньше среднего значения от всех элементов стека и удалить эти элементы.
11. Создать стек из случайных чисел и поменять местами минимальный и максимальный элементы.
12. Создать стек из случайных целых чисел и из него сделать еще два стека. В первый поместить все четные, а во второй - нечетные числа.
13. Создать стек из случайных целых чисел в диапазоне от 1 до 10, определить наиболее часто встречающееся число и удалить все элементы стека, содержащие это число.
14. Создать стек из случайных целых чисел и удалить из него каждый второй элемент.
15. Создать стек из случайных целых чисел и удалить из него каждый нечетный элемент.
Контрольные вопросы
1. Что представляет из себя динамическая структура данных «стек»?
2. Как сформировать стек из к элементов?
3. Как просмотреть непустой стек?
4. Как решить задачу не извлекая элементы из стека?
5. Какими способами формируется стек?