книги / Технологии разработки объектно-ориентированных программ на язык C++. Основы структурного программирования на алгоритмическом языке C++
.pdfДобавление верхнего элемента:
Stack* push(Stack* &first, int val) {
// Функция добавления элемента в стек
Stack* p = new Stack; // |
Выделение памяти для нового |
|
|
|
элемента |
p->data = val; |
// |
Присваивание нового элемента |
p->prev = first; |
/* |
Новый элемент указывает на |
|
|
нижний элемент */ |
first = p; |
// |
Новый элемент стает первым |
|
|
элементом стека */ |
return first; |
|
|
}
Подробнее: параметром передается указатель на первый элемент стека и значение элемента, который нужно добавить. Выделяется память для нового элемента (строка 2), присваивается значение, переданное параметром (строка 3), указателю нового элемента присваивается указатель на первый элемент стека (строка 4), а указателю на первый элемент присваивается указатель на новый эле-
мент (строка 5).
Удаление первых трех добавленных элементов:
void del(Stack* &first, int &n) { |
// Удаление |
int* mas = new int[n – 3]; |
// Для хранения |
|
элементов стека |
for (int i = 0; i < n – 3; i++) /* Перенос всех |
|
|
элементов, кроме |
|
последних трех, из |
|
стека в массив */ |
mas[i] = pop(first); |
|
for (int i = 0; i < 3; i++) |
/* Удаление оставшихся |
|
трех элементов */ |
pop(first); |
|
for (int i = n – 4; i >= 0; i--) |
/* Перенос элементов |
|
обратно в стек */ |
push(first, mas[i]); |
|
n –= 3; |
/* Уменьшение |
151
количества элементов стека */
}
Подробнее: параметром передается указатель по ссылке на первый элемент стека и так же по ссылке количество элементов стека. Объявляется массив из n – 3 количества элементов, так как три числа удалится (строка 2). Все элементы стека переносятся в массив, кроме последних трех (строки 3–4), а затем оставшиеся три элемента удаляются (строки 5–6). Все элементы массива переносятся обратно в стек, но уже в обратном порядке, чтобы сохранить изначальный порядок, который был в стеке (строки 7–8). В строке 9 уменьшается общее количество элементов стека.
Добавление трех элементов перед верхним элементом:
void add(Stack* &first) { // Добавление
int h = pop(first); // Сохраняем верхний элемент в переменную
for (int i = 0; i < 3; i++)
// Добавляем три новых |
элемента |
|
push(first, rand() % 10 |
+ 1); |
|
push(first, h); |
// Возвращаем верхний элемент |
|
}
Подробнее: параметром передается указатель по ссылке на первый элемент стека. Сохраняется верхний элемент стека и затем удаляется (строка 2). Добавляются три случайных элемента (строки 3–4), и затем ранее удаленный элемент возвращается в стек (строка 5).
Главная функция:
int main() {
setlocale(LC_ALL, "Rus"); srand(time(0));
cout << "Введите кол-во элементов в стеке (больше 3):
";
int size; cin >> size;
Stack* st = make_stack(size); // Создание стека
152
print_stack(st); |
// |
Печать стека |
del(st, n); |
// Удаление первых трех |
|
|
|
элементов |
cout << "Стек после удаления: "; |
|
|
print_stack(st); |
// Печать стека |
|
add(st); |
/* Добавление трех |
|
|
|
элементов |
|
|
перед первым */ |
cout << "Стек после добавления: "; |
||
print_stack(st); |
// Печать стека |
|
return 0; |
|
|
}
Пример выполнения работы программы:
Введите кол-во элементов в стеке (больше 3): 7
8 10 9 2 4 9 7
Стек после удаления: 8 10 9 2 Стек после добавления: 8 10 3 9 10 9 2
14.9. Реализация стека через класс
Рассмотрим решение задачи в гл. 2, реализованное через класс. Первым шагом создается класс stack со всеми необходимыми
методами.
class Stack { |
|
private: |
|
int* arr; |
// Массив элементов стека |
int MAX; |
// Максимальное кол-во элементов |
стека |
|
int index; |
// Текущий элемент в стеке |
public: |
|
Stack(int); |
// Конструктор |
~Stack(); |
// Деструктор |
bool push(int); |
// Вставка элемента |
int pop(); |
// Удаление элемента |
void print(); |
// Печать стека |
}; |
|
153
Скрытые данные: указатель на массив элементов, максимальное количество элементов в стеке, номер текущего элемента в стеке (помогает определить, насколько стек заполнен). Публичные методы: конструктор, деструктор, добавление элемента, удаление элемента и печать стека.
Конструктор и деструктор:
Stack::Stack(int kol) { // Создание стека c кол-вом элементов = kol
MAX = 100; // Максимальное кол-во элементов стека
index = 0; // Начальное кол-во элементов if (kol <= MAX) { // Если не переполнен
arr = new int[kol]; MAX = kol;
}
else cout << "Переполнение стека\n";
}
Stack::~Stack() { delete[] arr;
}
Подробнее: параметром для конструктора передается максимальное количество элементов стека. Переменной MAX присваивается переданный параметр (строка 6), и выделяется память для массива элементов (строка 5). Если ввели количество элементов больше 100, то выводит ошибку о переполнении стека (строка 8). В деструкторе удаляется массив (строка 11).
Печать стека:
void Stack::print() {
for (int i = index – 1; i >= 0; i--) cout << arr[i] << " ";
cout << endl;
}
Подробнее: элементы массива печатаются в обратном порядке
(строки 2–3).
154
Добавление элемента в стек:
bool Stack::push(int n) {
if (index == MAX) |
// Если стек заполнен |
return 0; |
|
else { |
// Если есть еще место |
arr[index++] = n; return 1;
}
};
Подробнее: параметром передается значение элемента, который нужно добавить. Если элемент добавляется, но места для него уже нет, то возвращается 0 (строка 3), иначе индекс увеличивается на 1 и в следующую пустую ячейку массива записывается значение, переданное параметром (строки 4–7).
Удаление элемента из стека:
int Stack::pop() {
if (index <= 0) { // Если стек пуст cout << "Стек пуст\n";
return 0;
}
else return arr[--index]; /* Так как в push сдвинется на 1 лишний элемент */
}
Подробнее: если стек пустой, то это сообщается пользователю и возвращается 0 (строки 3–4), а если нет, то возвращается элемент, который был добален последним (строка 6).
Удаление первых трех добавленных элементов:
void del(Stack &first, int &n) { |
// Удаление |
int* mas = new int[n – 3]; |
// Для хранения |
элементов стека for (int i = 0; i < n – 3; i++) /* Перенос всех
элементов, кроме последних трех, из стека в массив */
155
mas[i] = first.pop(); for (int i = 0; i < 3; i++)
// Удаление оставшихся трех элементов first.pop();
for (int i = n – 4; i >= 0; i--)
// Перенос элементов обратно в стек first.push(mas[i]);
n –= 3;
// Уменьшение количества элементов стека
}
Подробнее: параметром передается указатель по ссылке на первый элемент стека и так же по ссылке количество элементов стека. Объявляется массив из n – 3 количества элементов, так как три числа удалится (строка 2). Все элементы стека переносятся в массив, кроме последних трех (строки 3–4), а затем оставшиеся три элемента удаляются (строки 5–6). Все элементы массива переносятся обратно в стек, но уже в обратном порядке, чтобы сохранить изначальный порядок, который был в стеке (строки 7–8). В строке 9 уменьшается общее количество элементов стека.
Добавление трех элементов перед верхним элементом:
void add(Stack &first) { |
// Добавление |
int h = first.pop(); |
/* Сохраняем верхний элемент |
|
в переменную */ |
for (int i = 0; i < 3; i++) // Добавляем три новых |
|
|
элемента |
first.push(rand()%10 + 1); |
|
first.push(h); |
// Возвращаем верхний |
|
элемент |
} |
|
Подробнее: параметром передается указатель по ссылке на первый элемент стека. Сохраняется верхний элемент стека и затем удаляется (строка 2). Добавляются три случайных элемента (строки 3–4), и затем ранее удаленный элемент возвращается в стек
(строка 5).
156
Главный файл:
#include <iostream> #include <time.h> #include "stack.h" using namespace std;
void del(Stack &first, int &n) {…} void add(Stack &first) {…}
int main() { setlocale(LC_ALL, "Rus"); srand(time(0));
cout << "Введите максимальное количество элементов
встеке (менее
100): "; int n;
//n – максимальное количество элементов в стеке cin >> n;
Stack st(n);
cout << "Введите количество элементов в стеке: "; int p;
//p – количество элементов в стеке
cin >> p; |
|
for (int i = 0; i < p; i++) |
|
st.push(rand() % 10 + 1); |
// Добавление элементов |
|
в стек |
st.print(); |
// Печать стека |
del(st, p); |
// Удаление первых трех чисел |
cout << "Стек после удаления: "; |
|
st.print(); |
// Печать стека |
add(st); |
/* Добавление трех чисел |
|
перед первым числом */ |
cout << "Стек после добавления: "; |
|
st.print(); |
// Печать стека |
return 0; |
|
}
Пример выполнения работы программы:
Введите максимальное количество элементов в стеке (менее
100): 70
157
Введите количество элементов в стеке: 5
9 1 5 7 6
Стек после удаления: 9 1 Стек после добавления: 9 9 9 7 1
Задание для самостоятельной работы:
Реализовать стек из 15 элементов тремя способами. Написать программу, которая удаляет все элементы стека, добавляет 10 новых элементов и сортирует их по возрастанию.
14.10. Очереди
Очередь – абстрактный тип данных, представляющий собой список элементов, организованных по принципу FIFO (англ. first in – first out – «первым пришел – первым вышел»). Очереди, как и стек, не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся и забираются с разных концов [20] (рис. 14.4).
Рис. 14.4. Структура очереди
Базовые операции с очередью:
инициализация очереди;
помещение элемента в очередь;
удаление элемента из очереди;
печать очереди;
определение первого и последнего элементов без их удаления;
удаление очереди;
определение количества элементов очереди.
14.11. Реализация очереди через библиотеку STL
Необходимо реализовать очередь, используя класс queue библиотеки STL. Программа должна создавать очередь из 10 элемен-
158
тов, удалять первые два (1 и 2) и последние два элемента (9 и 10), добавлять три элемента в середину очереди.
Подключение необходимых библиотек, русского языка и генератора случайных чисел:
#include <iostream>
#include <queue> // Заголовок очереди #include <time.h>
using namespace std; int main() {
setlocale(LC_ALL, "Rus"); srand(time(0));
return 0;
}
Создание очереди:
queue<int> |
qu; |
// Создали пустую очередь |
|
for (int i = 0; i < 10; i++) |
|
|
|
qu.push(rand() % 10 + 1); |
// |
Добавление элементов |
|
|
|
|
в очередь |
print(qu); |
|
// |
Печать очереди |
Подробнее: в строке 1 создается очередь типа int, затем в цикле от 0 до 10 методом push() в очередь добавляются случайные элементы от 1 до 10. В конце очередь печатается.
Печать очереди:
/* Сохранили размер стека в переменную */
for (int i = 0; i < p; i++) { // Печать элементов стека cout << qu.front() << " ";
qu.pop();
}
cout << endl;
}
Подробнее: параметром передается очередь. В переменную p сохраняется изначальный размер очереди (строка 2). В цикле (стро-
159
ки 3–6) от 0 до p по очереди выводятся элементы очереди, а потом удаляются, чтобы получить доступ к следующему элементу.
Удаление первых двух и последних двух элементов:
qu.pop(); |
// |
Удаление |
первого |
элемента |
qu.pop(); |
// |
Удаление |
второго |
элемента |
int mas[6];
for (int i = 0; i < 6; i++) { // Перенос элементов в массив
mas[i] = qu.front(); |
// Забирает первый элемент без |
|
удаления |
qu.pop(); |
// Удаление элемента из очереди |
} |
|
qu.pop(); |
// Удаление девятого элемента |
qu.pop(); |
// Удаление десятого элемента |
for (int i = 0; i < 6; i++) |
// Перенос элементов в массив |
qu.push(mas[i]);
cout << "Очередь после удаления: |
"; |
|
print(qu); |
// |
Печать очереди |
Подробнее: удаляются первые два элемента (строки 1–2) методом pop(). Затем создается массив из шести элементов для временного хранения всех элементов очереди, кроме последних двух. В цикле (строки 4–7) все элементы очереди, кроме двух, переносятся в массив. Удаляются последние два элемента (строки 8–9). Затем все элементы переносятся обратно в очередь (строки 10–11). Очередь печатается (строка 13).
Добавление трех элементов в середину очереди:
for (int i = 0; i < 6; i++) { // Перенос элементов в массив
mas[i] = qu.front(); |
|
qu.pop(); |
|
} |
|
for (int i = 0; i < 3; i++) |
// Добавление первой половины |
|
из массива |
qu.push(mas[i]); |
|
for (int i = 0; i < 3; i++) |
// Добавление новых элементов |
qu.push(rand()% 10 + 1); |
|
for (int i = 3; i < 6; i++) |
// Добавление второй половины |
160