БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра программного обеспечения информационных технологий
Факультет ФКСиС
Специальность ПОИТ
Индивидуальная практическая работа №2
по дисциплине «Языки программирования. Часть 2»
Вариант 5
Выполнил студент: Бордон Е.С.
группа 991051
Зачетная книжка № 99105004
Минск 2021
Задание:
5. Разработать программу слияния двух стеков, содержащих
возрастающую последовательность целых положительных чисел, в третий
стек так, чтобы его элементы располагались также в порядке возрастания.
Пояснения к работе программы:
Программа реализована на языке программирования Си в программной среде разработки Visual Studio 2019. Программы выполнена в консольном режиме.
Стек – это структура данных, в которой элементы поддерживают принцип LIFO (“Last in – first out”): последним зашёл – первым вышел. Или первым зашёл – последним вышел. Это значит, что каждый добавляемый элемент будет идти в начало очереди. Всего в программе будет 3 стека по условию задания ‘a’, ‘b’ и ‘c’.
Структура будет представлять из себя указатель на вершину и значение стека. Функции добавления, удаления элемента будут вынесены в отдельные процедуры:
typedef struct STACK {
int value;
struct STACK* next;
} Stack;
Stack* stack_push(Stack* stack, int value) { // Добавление элемента
Stack* node = malloc(sizeof(Stack));
assert(node); //Проверка верности функционирования программы
node->value = value;
node->next = stack;
return node;
}
int stack_is_empty(Stack* stack) { // проверка на пустоту
return (!stack);
}
int stack_top(Stack* stack) { // возвращаем последний элемент
assert(stack); //Проверка верности функционирования программы
return stack->value;
}
Stack* stack_pop(Stack* stack, int* valptr) { // убираем элемент
Stack* next;
assert(stack); //Проверка верности функционирования программы
if (valptr)
*valptr = stack->value;
next = stack->next;
free(stack);
return next;
}
Stack* a = NULL, * b = NULL, * c = NULL;
В начале работы программы мы будем указывать размер стека ‘a’ и ‘b’. Данные для них будут браться рандомно для простоты работы программы. Для этого создаем вспомогательные динамические массивы, добавляем в них рандомные значения и сортируем по возрастанию.
do { // проверка ввода
printf("Введите число элементов стэка 'а': ");
fseek(stdin, 0, SEEK_END); // очистка потока
} while (scanf_s("%d", &size_a) != 1 || size_a < 1);
do { // проверка ввода
printf("Введите число элементов стэка 'b': ");
fseek(stdin, 0, SEEK_END); // очистка потока
} while (scanf_s("%d", &size_b) != 1 || size_b < 1);
printf("\nЧисла подобраные рандомным образом от 1-99,\nи отсортированы по возростанию согласно заданию.\n");
srand(time(NULL)); // для разных значений рандома
printf("\nДаные для стэка 'a': ");
int* arr_a;
arr_a = (int*)malloc(size_a * sizeof(int));
for (i = 0; i < size_a; i++)
arr_a[i] = 1 + rand() % (99);
sortarr(arr_a, size_a); // сортируем по условию задания по возрастанию
for (i = 0; i < size_a; i++)
printf("%d ", arr_a[i]);
printf("\nДаные для стэка 'b': ");
int* arr_b;
arr_b = (int*)malloc(size_b * sizeof(int));
for (i = 0; i < size_b; i++)
arr_b[i] = 1 + rand() % (99);
sortarr(arr_b, size_b); // сортируем по условию задания по возрастанию
for (i = 0; i < size_b; i++)
printf("%d ", arr_b[i]);
Далее необходимо заполнить сами стеки ‘a’ и ‘b’. Тк каждый новый элемент идет в начало очереди заполняем в обратном порядке:
for (i = (size_a-1); i >= 0; i--) // Заполняем стэк 1
a = stack_push(a, arr_a[i]); // заполняем в обратном порядке чтобы в топе был самый маленький элемент
for (i = (size_b-1); i >= 0; i--) // тк каждый новый идет наверх
b = stack_push(b, arr_b[i]); // Заполняем стэк 2
free(arr_a); // освобождаем память
free(arr_b);
В результате мы получаем два стека с отсортированными значениями по возрастанию, согласно условию задания. Дальше мы начинаем сравнивать вершины стека ‘a’ и ‘b’, при удовлетворении условия кладем элемент в стек ‘c’.
В начале мы сравниваем каждый ‘a’ топ элемент с каждым ‘b’ топ элементов в результате если ‘a’ меньше добавляем в ‘c’ и убираем его из ‘a’, если больше или равно делаем тоже с ‘b’.
while (!stack_is_empty(a) && !stack_is_empty(b)) { // пока не закончатся а и b
if (stack_top(a) < stack_top(b)) { // сравниваем последний элементы а и b
c = stack_push(c, stack_top(a)); // добавляем элемент в с
a = stack_pop(a, NULL); // убираем элемент а
}
else {
c = stack_push(c, stack_top(b)); // добавляем элемент в с
b = stack_pop(b, NULL); // убираем элемент b
}
}
В результате самые крупные элементы в начале стека ‘a’ или ‘b’ не попали в стек ‘c’. Тк данные отсортированы, мы просто проверим наличие элементов в каждом из стеков (в одном из) и добавим в стек ‘c’:
while (!stack_is_empty(a)) {
c = stack_push(c, stack_top(a));
a = stack_pop(a, NULL);
}
while (!stack_is_empty(b)) {
c = stack_push(c, stack_top(b));
b = stack_pop(b, NULL);
}
Теперь стек ‘c’ содержит исходные элементы и упорядочен по убыванию. Для того чтобы сделать по возрастанию, согласно заданию, мы перенесем сначала в уже пустой стек ‘a’ сделав его в стеке ‘a’ по возрастанию. Затем в стек ‘b’ сделав его там по убыванию. И затем вернем данные из ‘b’ в ‘c’ где числа будут уже по возрастанию, согласно заданию работы.
while (!stack_is_empty(c)) {
c = stack_pop(c, &i);
a = stack_push(a, i);
}
while (!stack_is_empty(a)) {
a = stack_pop(a, &i);
b = stack_push(b, i);
}
while (!stack_is_empty(b)) {
b = stack_pop(b, &i);
c = stack_push(c, i);
}
При завершении работы выводим конечный результат.
Все функции программы вынесены в отдельный заголовочный файл.
В ходе тестирования программы ошибок не обнаружено.
Результат работы программы:
Рис. 1 Результат работы программы.
Листинг программы: файл “functions.h”:
#pragma once
typedef struct STACK {
int value;
struct STACK* next;
} Stack;
Stack* stack_push(Stack* stack, int value) { // Добавление элемента
Stack* node = malloc(sizeof(Stack));
assert(node); //Проверка верности функционирования программы
node->value = value;
node->next = stack;
return node;
}
int stack_is_empty(Stack* stack) { // проверка на пустоту
return (!stack);
}
int stack_top(Stack* stack) { // возвращаем последний элемент
assert(stack); //Проверка верности функционирования программы
return stack->value;
}
Stack* stack_pop(Stack* stack, int* valptr) { // убираем элемент
Stack* next;
assert(stack); //Проверка верности функционирования программы
if (valptr)
*valptr = stack->value;
next = stack->next;
free(stack);
return next;
}
void sortarr(int* arr, int count) {
int ss;
for (int i = 1; i < count; i++) {
for (int j = 0; j < (count - i); j++) {
if (arr[j] > arr[j + 1]) {
ss = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = ss;
}
}
}
}
Листинг программы: файл “project.c ”:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h> //проверяет значение аргумента arg и если аргумент равен нулю, то выводится диагностическое сообщение
#include <locale.h>
#include "functions.h"
int main() {
setlocale(LC_ALL, "RU");
Stack* a = NULL, * b = NULL, * c = NULL;
int i, size_a=0, size_b=0;
// вводим числа для стэка a and b
do { // проверка ввода
printf("Введите число элементов стэка 'а': ");
fseek(stdin, 0, SEEK_END); // очистка потока
} while (scanf_s("%d", &size_a) != 1 || size_a < 1);
do { // проверка ввода
printf("Введите число элементов стэка 'b': ");
fseek(stdin, 0, SEEK_END); // очистка потока
} while (scanf_s("%d", &size_b) != 1 || size_b < 1);
printf("\nЧисла подобраные рандомным образом от 1-99,\nи отсортированы по возростанию согласно заданию.\n");
srand(time(NULL)); // для разных значений рандома
printf("\nДаные для стэка 'a': ");
int* arr_a;
arr_a = (int*)malloc(size_a * sizeof(int));
for (i = 0; i < size_a; i++)
arr_a[i] = 1 + rand() % (99);
sortarr(arr_a, size_a); // сортируем по условию задания по возрастанию
for (i = 0; i < size_a; i++)
printf("%d ", arr_a[i]);
printf("\nДаные для стэка 'b': ");
int* arr_b;
arr_b = (int*)malloc(size_b * sizeof(int));
for (i = 0; i < size_b; i++)
arr_b[i] = 1 + rand() % (99);
sortarr(arr_b, size_b); // сортируем по условию задания по возрастанию
for (i = 0; i < size_b; i++)
printf("%d ", arr_b[i]);
for (i = (size_a-1); i >= 0; i--) // Заполняем стэк 1
a = stack_push(a, arr_a[i]); // заполняем в обратном порядке чтобы в топе был самый маленький элемент
for (i = (size_b-1); i >= 0; i--) // тк каждый новый идет наверх
b = stack_push(b, arr_b[i]); // Заполняем стэк 2
free(arr_a); // освобождаем память
free(arr_b);
while (!stack_is_empty(a) && !stack_is_empty(b)) { // пока не законтатся а и b
if (stack_top(a) < stack_top(b)) { // сравниваем последний элементы а и b
c = stack_push(c, stack_top(a)); // добавляем элемент в с
a = stack_pop(a, NULL); // убираем элемент а
}
else {
c = stack_push(c, stack_top(b)); // добавляем элемент в с
b = stack_pop(b, NULL); // убираем элемент b
}
}
// проверяем последний элемент тк последовательность упорядочина он самый крупный
while (!stack_is_empty(a)) {
c = stack_push(c, stack_top(a));
a = stack_pop(a, NULL);
}
// проверяем последний элемент тк последовательность упорядочина он самый крупный
while (!stack_is_empty(b)) {
c = stack_push(c, stack_top(b));
b = stack_pop(b, NULL);
}
// Сейчас стэк с расположен по !убыванию! его нужно отзеркалить
// Копируем стэк "с" в "а" - в "а" он уже по !возрастанию!
// его можно выводить, но по заданию нужно слить все в третий стэк "c"
while (!stack_is_empty(c)) {
c = stack_pop(c, &i);
a = stack_push(a, i);
}
// Копируем стэк "а" в "b" - в "b" он по убыванию
while (!stack_is_empty(a)) {
a = stack_pop(a, &i);
b = stack_push(b, i);
}
// Копируем стэк "b" в "c" - в "с" он опять по возрастанию!
// На этом задание выполнено
while (!stack_is_empty(b)) {
b = stack_pop(b, &i);
c = stack_push(c, i);
}
// Выводим стэк "c"
printf("\n\nРезультат слияния стэка 'a' и 'b' \n");
printf("Стэк 'c': \n");
while (!stack_is_empty(c)) {
printf("%d ", stack_top(c));
c = stack_pop(c, NULL);
}
printf("\n");
printf("\n");
system("pause");
return 0;
}