Учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика

жүктеу/скачать 3,71 Mb.

бет	6/8
Дата	14.10.2019
өлшемі	3,71 Mb.
	#49870
түрі	Учебно-методический комплекс

1 2 3 4 5 6 7 8

Байланысты:
УМКАлгор и стр данн Инеттен (1)

максимальное кол-во самолётов в очереди на посадку и взлёт;

интервал времени для моделирования;

предполагаемое (ожидаемое) число прилетающих и

взлетающих самолётов в единицу времени;

2. используя псевдослучайные числа, удовлетворяющие закону

распределения Пуассона, смоделировать кол-во запросов на взлёт

и посадку самолётов в каждый момент времени;

3. в случае, если очередь на посадку не пуста, то использовать

взлётную полосу для посадки самолёта, в противном случае

использовать её для взлёта;

4. если какая-либо очередь заполнена, «отправить» самолёт на

другой аэропорт (вывести сообщение в консоль) в случае посадки

или «попросить» подождать некоторое время в случае взлёта;

5. все события (запрос на взлёт/посадку, взлёт/посадка, отказ во

взлёте/посадке)сопровождаютсясоответствующими

сообщениями в консоли;

6. вести статистику:

сколько получено запросов на взлёт/посадку;

80

сколько принято запросов на взлёт/посадку;

сколько самолётов взлетело/приземлилось;

сколько было отказов на взлёт/посадку;

общее время ожидания взлетевших/приземлившихся

самолётов;

время простоя взлётной полосы (обе очереди пусты).

7. по окончании интервала моделирования (цикл for)вывести в

консоль (файл) отчёт, который содержит:

1. общее кол-во обработанных запросов;

2. кол-во запросов на взлёт/посадку;

3. кол-во принятых запросов на взлёт/посадку;

4. кол-во отклонённых запросов на взлёт/посадку;

5. кол-во взлетевших/приземлившихся самолётов;

6. кол-во самолётов, оставшихся в очереди на взлёт/посадку;

7. время простоя взлётной полосы в процентах;

8. среднее время ожидания для взлёта/приземления;

9. среднее кол-во поступивших запросов на взлёт/приземление.

Для реализации создать классы Runwayи Plane, которые описывают

аэропорт (взлётную полосу) и самолёт соответственно.

Для генерации псевдослучайного числа с законом распределения

Пуассона рекомендуется использовать

...

#include

...

intmain(){

...

std::random_device rd; //генератор случайныхчисел.

std::mt19937gen(rd()); //генератор псевдослучайных

чисел, который инициализируется случайным числом

rd().

std::poisson_distribution<>distr(mean); //создание

объекта для генерации случайных чисел с

распределением Пуассона при заданном среднем

(ожидаемом) значении mean.

distr(gen); //генерирование случайного числа с

распределением Пуассона с заданным параметром

mean.





81

Задание 2

Разработать консольное приложение, которое с помощью абстрактных

структур данных СТЭК и ОЧЕРЕДЬ проверяет введённую с клавиатуры

строку текста на палиндром. Приложение должно:

1. делать запрос на ввод строки текста;

2. выводить в консоль:

в случае палиндрома – сообщение об этом;

в противном случае – сообщение об этом и символ, для

которого не оказалось равного ему симметричного;

3. делать запрос на выход из приложения.

Лабораторная работа №4

Цель работы: Изучение принципов организации и работы с абстрактной

структурой данных ДВУСВЯЗНЫЙ ЛИНЕЙНЫЙ СПИСОК.

Двусвязный линейный список — структура данных, где каждый

элемент содержит указатель на следующий и предыдущий элементы.

NULL

first

11

23

38

47

last

NULL

Поддерживаемые операции

1.

7.

8.

9.

10.

11.

12.

13.

вставить элемент перед текущим элементом;

вставить элемент после текущего элемента;

получить указатель на первый элемент списка.

получить указатель на последний элемент списка.

получить данные первого элемента списка.

получить данные последнего элемента списка.

получить указатель на следующий, относительно данного, элемент

списка;

получить указатель на предыдущий, относительно данного, элемент

списка;

удалить выбранный элемент из списка;

найти элемент с указанной информационной частью и вернуть укзатель

на него;

очистить список;

копировать список;

вывести в консоль все элементы списка.

ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ В ДВУСВЯЗНЫЙ СПИСОК

Графическая иллюстрация:

Пусть список имеет следующий вид:

NULL

first

11

p

23

38

47

last

NULL

1. newNode = new Node;

NULL

first

11

p

23

38

47

last

NULL

newNode

2. newNode->data = 50;

//запись информационной части и указателей

NULL

newNode

50

NULL

3. newNode->prev = p;

4. newNode->next = p->next;

//инициализация указателей нового элемента

NULL

first

11

p

23

38

47

last

NULL

1

50

newNode

83

2

5. p->next->prev = newNode;

6. p->next = newNode;

// перенаправление указателей соседних элементов

списка

NULL

first

11

p

23

38

47

last

NULL

4

1

50

newNode

3

2

УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ ДВУСВЯЗНОГО СПИСКА

Графическая иллюстрация:

NULL

first

11

23

p

38

47

last

NULL

Нужно удалить из списка элемент, на который указывает p.Перенаправление

указателей и освобождение памяти:

1. p->prev->next = p->next;

2. p->next->prev = p->prev;

3. delete p;

Выглядит это так:

NULL

first

11

23

p

1

38

47

NULL

last

2

84

NULL

first

11

23

47

last

NULL

Важно! Как при добавлении, так и при удалении элементов необходимо:

1. Специально рассматривать случай когда элемент добавляется или

удаляется в качестве первого или последного элемента списка. В этом

случае перенаправляются указатели first и last.

2. Проверять, является ли список пустым или нет.

При создании двусвязного списка нужно помнить, что каждый элемент

списка имеет 2 (два) указателя, — на предыдущий и на следующий элементы.

Первый элемент списка имеет указатель на предыдущий элемент, равный

NULL (nullptr). Последний элемент списка имеет указатель на следующий

элемент, равный NULL (nullptr).

Контрольные вопросы

1. Что такое абстрактная структура данных?

2. Основное свойство структуры данных двусвязный линейный список?

3. Напишите алгоритм основных операций с двусвязным линейным

списком?

4. Перечислите операции двусвязного списка, которые «недоступны»

для стэка и очереди?

5. Перечислите операции двусвязного списка, которые также

«доступны» для стэка? Очереди?

ПРАКТИЧЕСКИЕ ЗАДАНИЯ

Задание 1

ИспользуяабстрактнуюструктуруданныхДВУСВЯЗНЫЙ

ЛИНЕЙНЫЙ СПИСОК, разработать консольное приложение в

соответствии со своим вариантом. Приложение должно обеспечивать

диалог с помощью меню и контроль ошибок при вводе.

Вариант 1

Динамическая информация о наличии автобусов в автобусном парке

и на маршрутах включают в себя следующие сведенияокаждом

автобусе:

номер автобуса;

фамилию и инициалы водителя;

85

номер маршрута.

Программа должна обеспечивать:

начальное формирование данных о всех автобусах в виде списка;

по номеру автобуса:

«переводить» автобус из парка на маршрут – удалять

данные об этом автобусе из списка автобусов, находящихся

в парке, и добавлять эти данные в список автобусов,

находящихся на маршруте;

«переводить» автобус с маршрута в парк – удалять данных

об этом автобусе из списка автобусов, находящихся на

маршруте, и добавлять эти данные в список автобусов,

находящихся в парке;

выдавать по запросу сведения об автобусах, находящихся в парке,

или об автобусах, находящихся на маршруте;

выдавать по запросу сведения о всех автобусах.

Вариант 2

Список содержит текущую информацию о заявках на авиабилеты.

Каждая заявка включает в себя:

пункт назначения;

номер рейса;

фамилию и инициалы пассажира;

желаемую дату вылета.

Программа должна обеспечивать:

хранение всех заявок в виде списка;

добавление заявок в список;

удаление заявок из списка;

вывод заявок по заданному номеру рейса и дате вылета;

вывод всех заявок.

Вариант 3

Список содержит текущую информацию о книгах в библиотеке.

Сведения о книгах включают в себя:

номер УДК;

фамилию и инициалы автора;

название;

год издания;

количество экземпляров данной книги в библиотеке.

Программа должна обеспечивать:

начальное формирование данных о всех книгах в библиотеке в

виде вписка;

возможность получить книгу при вводе номера УДК и в

зависимости от состояния списка:

выдавать книгу «на руки» и уменьшать кол-во экземпляров

данной книги в библиотеке на единицу;

86

выдавать сообщение о том, что требуемой книги в

библиотеке нет;

требуемая книга находится на руках.

возможность вернуть книгу при вводе номера УДК (кол-во

экземпляров книги увеличивается на единицу);

выдавать сведения о наличии книг в библиотеке по запросу.

Вариант 4

Для каждого файла в некотором каталоге содержатся следующие

сведения:

имя файла:

дата создания;

количество обращений к файлу.

Программа должна обеспечивать:

начальное формирование каталога файлов;

вывод каталога файлов;

удаление файлов, дата создания которых меньше заданной;

выборку файлов с наибольшим количеством обращений.

Вариант 5

Каждая компонента предметного указателя содержит слово и

номера страниц, на которых это слово встречается. Количество

номеров страниц, относящихся к одному слову, от одного до десяти.

Программа должна обеспечивать:

начальное формирование предметного указателя;

вывод предметного указателя;

вывод номера страниц для заданного слова.

Вариант 6

Каждая компонента текста помощи для программы содержит

термин (слово) и текст, содержащий пояснения к этому термину.

Количество строк текста, относящихся к одному термину, от одной

до пяти.

Программа должна обеспечивать:

начальное формирование текста помощи;

вывод текста помощи;

вывод поясняющего текста для заданного термина.

Вариант 7

Картотека в бюро обмена квартир содержат следующие сведения о

каждой квартире:

количество комнат;

этаж;

площадь;

адрес.

Программа должна обеспечивать:

87

начальное формирование картотеки;

ввод заявки на обмен;

поиск в картотеке подходящего варианта:

при равенстве кол-ва комнат и этажа и различии площадей

в пределах 10м2 выводится соответствующая карточка и

удаляется из списка;

в противном случае поступившая заявка включается в

список;

вывод всего списка.

Вариант 8

Анкета для опроса населения содержит две группы вопросов.

Первая группа содержит сведения о респонденте:

возраст;

пол;

образование (начальное, среднее, высшее).

Вторая группа содержит собственно вопрос анкеты, ответ на

который может быть ДА или НЕТ.

Программа должна обеспечивать:

начальный ввод анкет и формирование из них линейного списка;

ответы на следующие вопросы на основе анализа анкет:

а). сколько мужчин старше 40 лет, имеющих высшее

образование, ответили ДА на вопрос анкеты;

б). сколько женщин моложе 30 лет, имеющих среднее

образование, ответили НЕТ на вопрос анкеты;

в). сколько мужчин моложе 25 лет, имеющих начальное

образование, ответили ДА на вопрос анкеты;

г). вывод всех анкет и ответов на вопросы в консоль.

Вариант 9

На междугородной телефонной станции картотека абонентов,

содержит сведения о телефонах и их владельцах.

Программа должна обеспечивать:

начальное формирование картотеки в виде линейного списка;

вывод всей картотеки в консоль;

ввод номера телефона и вывод времени разговора;

ввод данных абонента и вывод извещения на оплату телефонного

разговора.

Вариант 10

Автоматизированнаяинформационнаясистемана

железнодорожном вокзале содержит сведения об отправлении

поездов дальнего следования. Для каждого поезда указывается:

номер поезда;

88

станция назначения;

время отправления.

Данные в информационной системе организованы в виде линейного

списка.

Программа должна обеспечивать:

первоначальный ввод данных в информационную систему и

формирование линейного списка:

вывод всего списка в консоль;

ввод номера поезда и вывод всех данных об этом поезде;

ввод названия станции назначения и вывод данных обо всех

поездах, следующих до этой станции.

Лабораторная работа №5

Цель работы: Изучение принципов организации и работы с абстрактной

структурой данных БИНАРНОЕ ДЕРЕВО.

Бинарное дерево — структура данных, состоящая из множества узлов,

объединённых связями типа родитель (parentchild).Эти связи

удовлетворяют следующим условиям:

1. Существует единственный элемент (узел), у которого нет

«родителя». Этот элемент называется корнем (всего) дерева.

2. Всякий элемент (узел), не являющийся корнем дерева, имеет ровно

одного родителя.

3. Всякий элемент (узел) может иметь одного, двух или ни одного

«ребёнка».

Свойство: Всякий элемент (узел) является корнем дерева, состоящего из

его левого и правого поддеревьев.

Кроме того,элементы дерева определённым образом упорядочены.

Отношения порядка определяются в зависимости от типа элементов,

составляющих дерево. Для чисел это отношения больше, меньше.

Графическая иллюстрация одного узла бинарного дерева:

Info

данные

указатель

left

right

указатель

Каждый элемент бинарного дерева содержит данные (Info) и два

указателя. Левый (left) указатель направлен на «левого» ребёнка (child),

89

правый (right) — на «правого». Если какого-то (или обоих) «детей» нет, то

соответствующие указатели равны NULL().

Упорядочивание элементов бинарного дерева осуществляется по

следующему правилу:

Слева — элемент, предшествующий текущему (в случае чисел –

меньшее), справа — следующий по порядку (в случае чисел –

большее). Отношение порядка устанавливается в зависимости от

природы самих элементов и (или) логики приложения.

В левом поддереве расположены только предшествующие

корневому элементы, в правом – следующие по порядку.

Графическая иллюстрация бинарных деревьев

root

23

1. Бинарное дерево, состоящее из единственного

элемента – корня дерева.

2. Бинарное дерево с левым и правым

поддеревом.

root

23

18

31

13

16

20

10

11

12

12

90

СОЗДАНИЕ БИНАРНОГО ДЕРЕВА И ДОБАВЛЕНИЕ

ЭЛЕМЕНТОВ

Графическая иллюстрация:

root

1. Создание бинарного дерева.

2. Добавление элементов (Insert)

Insert 4:

root

4

Insert 9(9>4):

root

4

9

Insert 7(7>4, 7<9):

root

4

Insert 2(2<4):

root

9

4

7

2

9

7

91

Insert 8(8>4, 8<9, 8>7):

root

4

Insert 10(10>4, 10>9):

root

4

2

9

2

9

7

7

10

8

8

Insert 5(5>4, 5<9, 5<7):

root

4

2

9

7

10

5

8

92

Правило добавления элементов в бинарное дерево:

Элемент добавляется на соответствующую ему в

бинарном дереве позицию в качестве ЛИСТА.

Новый элемент замещает какой-либо указатель

NULL в существующем (или пустом) дереве.

Листом называется элемент дерева, у которого нет «детей». Другими

словами, указатели left и right такого элемента рывны NULL.

Общий вид элемента типа «ЛИСТ»:

Лист дерева

ДЕРЕВО

INFO

Для добавления элементов в бинарное дерево может быть применена

рекурсия, так как каждый раз необходимо проделать одни и те же действия,

вплоть до основного случая (base case), когда нужное место для добавления

элемента найдено.

Каждый раз нужно:

1. «Сравнить» добавляемый элемент с текущим.

2. Если добавляемый элемент предшествует текущему (меньше), то

перейти к левому (указатель left) «ребёнку» текущего элемента.

3. Если добавляемый элемент следует за текущим (больше), то

перейти к правому (указатель right) «ребёнку» текущего элемента.

Основной случай (base case):

Если «ребёнок» (левый или правый) равен NULL, то

место для добавления нового элемента найдено.

Теперь

1. Создаётся новый элемент.

2. Записывается информационная часть.

3. Указатели left и right устанавливаются в NULL.

Графическая иллюстрация:

Для определённости рассмотрим случай Insert 5(5>4, 5<9, 5<7).

Исходное бинарное дерево:

tree

4

tree–>right

2

9

7

10

8

1. Указатель tree на текущий элемент, значение tree–>info == 4.

2. Поскольку 5>tree–>info (=4), переходим для сравнения к корню правого

поддерева (info=9):

tree=tree –>left;

tree

tree–>left

9

7

10

8

94

3. Текущее значение tree–>info == 9.

4. Поскольку 5info (=9), переходим для сравнения к корню левого

поддерева (info=7):

tree=tree –>left;

tree

tree–>left

7

8

5. Текущее значение tree–>info == 7.

6. Поскольку 5info (=7), переходим для сравнения к корню левого

поддерева, но указатель tree–>left == NULL:

tree=tree –>left (=NULL);

tree

7

…

7. Поэтому наступает основной случай (base case) – создание и добавление

в дерево нового элемента:

tree = new Node(5, nullptr, nullptr);

tree

7

5

8

95

Пример private-функции, реализующей

добавления элементов в бинарное дерево:

рекурсивный

алгоритм

template

void BinaryTree::insertNode(

const Type& data, Node*& tree)

{

if(tree == nullptr )// Основной случай

tree = new Node{item, nullptr, nullptr};

else if(data < tree->info )

insert(data, tree->left );

else

insert(data, tree->right );

}

Пример public-функции, члена класса BinaryTree:

template

void BinaryTree::insert(const Type& data)

жүктеу/скачать 3,71 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7 8