Лабораторные работы / отчёт 14 (с 14_2_2)
.docxФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
“ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ”
Кафедра “Информатика и вычислительная техника”
ОТЧЕТ
по лабораторной работе №14
“ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СПИСКИ”
Выполнил:
Студент группы ИВТ-234 Бектимиров А.Е.
_____________________________________________________
(дата, подпись)
Проверил:
ст. пр. доцент Дорошенко М.С.
_____________________________________________________
(дата, подпись)
Омск 2024
Лабораторная работа №14
Тема: Динамические структуры данных. Списки
Вариант 2
Задание 1
Условие задачи:
Используя динамические структуры двусвязный список и стек, проверить, является ли он упорядоченным набором чисел.
Схема
алгоритма:
Текст программы:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
struct LinkedList {
Node* head;
Node* tail;
};
struct Stack {
Node* top;
};
LinkedList* createList() {
LinkedList* list = new LinkedList();
list->head = nullptr;
list->tail = nullptr;
return list;
}
void insertNode(LinkedList* list, int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->prev = nullptr;
newNode->next = nullptr;
if (list->head == nullptr) {
list->head = newNode;
list->tail = newNode;
}
else {
list->tail->next = newNode;
newNode->prev = list->tail;
list->tail = newNode;
}
}
Stack* createStack() {
Stack* stack = new Stack();
stack->top = nullptr;
return stack;
}
void push(Stack* stack, Node* node) {
node->next = stack->top;
stack->top = node;
}
Node* pop(Stack* stack) {
if (stack->top == nullptr) {
return nullptr;
}
Node* topNode = stack->top;
stack->top = stack->top->next;
return topNode;
}
bool isOrdered(LinkedList* list) {
Stack* stack = createStack();
Node* current = list->head;
while (current != nullptr) {
if (stack->top == nullptr || current->data >= stack->top->data) {
push(stack, current);
current = current->next;
}
else {
return false;
}
}
return true;
}
int main() {
setlocale(LC_ALL, "RUS");
LinkedList* list = createList();
int num;
char choice;
do {
cout << "Введите число: ";
cin >> num;
insertNode(list, num);
cout << "Вы хотите добавить ещё числа в список? (y/n): ";
cin >> choice;
} while (choice == 'y');
if (isOrdered(list)) {
cout << "Заданный список является упорядоченным набором чисел." << endl;
}
else {
cout << "Заданный список не является упорядоченным набором чисел." << endl;
}
return 0;
}
Результаты выполнения программы:
Задание 2
Условие задачи:
Используя динамическую структуру стек, распечатать элементы в обратном порядке.
Схема алгоритма:
Текст программы:
#include <iostream>
#include <stack>
void printReverse(std::stack<int>& s) {
std::stack<int> tempStack = s;
while (!tempStack.empty()) {
std::cout << tempStack.top() << " ";
tempStack.pop();
}
}
int main() {
std::stack<int> myStack;
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
printReverse(myStack);
return 0;
}
Результаты выполнения программы:
