Лабораторные работы по "Информатике"
Автор: Prostpony • Ноябрь 10, 2018 • Лабораторная работа • 14,853 Слов (60 Страниц) • 407 Просмотры
Оглавление
Лабораторная работа №1 2
Тема: Обработка стека 2
Лабораторная работа №2 9
Тема: Обработка списков. 9
Лабораторная работа №3 24
Тема: Обработка очереди. 24
Лабораторная работа №4 36
Тема: Двоичные деревья. 36
Лабораторная работа №5 47
Тема: Обработка исключительных ситуаций 47
Лабораторная работа №1
Тема: Обработка стека
Цель: формировать практические умения и навыки описания структуры данных таких, как стек, решения задач его обработки.
Задание 1.
Отладить и откомпилировать следующую программу, включающую основные операции над стеком.
Пример 1. Программная реализация стека
Рассмотрим, как представлять стек с помощью односвязного списка и как в этом случае реализуются операции со стеком. Операция записи в стек означает создание нового элемента списка, присоединение его к списку в качестве первого его элемента и занесение в него заданного значения. Операция чтения из стека реализуется как чтение значения первого элемента списка с удалением этого элемента из списка, при этом обязателен контроль состояния стека. Состояние стека определяется значением его указателя: стек пуст, если указатель имеет значение NULL, в противном случае - стек не пуст.
#include
#include
#include
using namespace std;
class Stack
{
enum {EMPTY = -1, FULL = 20};
char st[FULL + 1];
int top;
public:
Stack();
void Push(char c);
char Pop();
void Clear();
bool IsEmpty();
bool IsFull();
int GetCount();
};
Stack::Stack()
{
top = EMPTY;
}
void Stack::Clear()
{
top = EMPTY;
}
bool Stack::IsEmpty()
{
return top == EMPTY;
}
bool Stack::IsFull()
{
return top == FULL;
}
int Stack::GetCount()
{
return top + 1;
}
void Stack::Push(char c)
{
if(!IsFull())
st[++top] = c;
}
char Stack::Pop()
{
if(!IsEmpty())
return st[top--];
else
return 0;
}
void main()
{
srand(time(0));
Stack ST;
char c;
// пока стек не заполнится
while(!ST.IsFull()){
c=rand()%4+2;
ST.Push(c);
}
while(c=ST.Pop()){
cout<
}
cout<<"\n\n";
}
[pic 1]
Рисунок 1.1
Пример 2. Программная реализация очереди
Операции записи в очередь и чтения из очереди реализуются аналогично операциям со стеком. Здесь отличие состоит в том, что добавление и удаление элемента производятся в разные концы очереди, при этом состояние очереди должны контролировать обе операции: если очередь была пуста, то операция записи корректирует и указатель на конец очереди, а если очередь состоит из одного элемента, то операция чтения должна корректировать и указатель на начало очереди (задавать значение NULL при списочном представлении очереди).
...