42028

Динамические структуры данных (списки, очереди, стеки, двоичные деревья)

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

Информатика, кибернетика и программирование

Программа должна обеспечивать: начальное формирование данных о всех автобусах в парке в виде двусвязного циклического списка; при выезде каждого автобуса из парка вводится номер автобуса и программа удаляет данные об этом автобусе из списка автобусов находящихся в парке и записывает эти данные в список автобусов находящихся на маршруте; при въезде каждого автобуса в парк вводится номер автобуса и программа удаляет данные об этом автобусе из списка автобусов находящихся на маршруте и записывает эти данные в список автобусов...

Русский

2015-01-18

56.5 KB

130 чел.

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

Тема: Динамические структуры данных.

Цель работы: приобрести практические навыки использования динамических структур данных при работе со списками, стеками, очередями.

Порядок выполнения работы

  1.  Изучить теоретические основы работы с динамическими структурами данных – списками, очередями, стеками, двоичными деревьями.
  2.  Разработать алгоритм решения задачи и программу.

Требования

  1.  Определить заданные в варианте задания составные типы данных с помощью ключевого слова typedef.
  2.  Исходную загрузку данных в динамические структуры производить из ASCII файла. Размер динамической структуры считывать из ASCII файла. Память под динамическую структуру выделять с помощью операторов работы c динамической памятью.
  3.  Предусмотреть диалоговый ввод-вывод данных (редактирование) через консоль.
  4.  Предусмотреть форматированный вывод результатов работы программы на экран.
  5.  Разработанные структуры, обеспечивающие в соответствии с заданием работу со списком, стеком, двоичным деревом или очередью должны реализовывать следующие функции (в дополнение к перечисленным в задании): а) возвращение количества элементов; б) добавление элемента; в) поиск элемента по значению (возвратить номер); г) удаление элемента по номеру; д) набор методов для организации последовательного доступа к элементам; е) вывод списка на экран.

Варианты заданий

  1.  Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе содержат: номер автобуса; фамилию и инициалы водителя; номер маршрута. Программа должна обеспечивать: 1) начальное формирование данных о всех автобусах в парке в виде двусвязного циклического списка; 2) при выезде каждого автобуса из парка вводится номер автобуса, и программа удаляет данные об этом автобусе из списка автобусов, находящихся в парке, и записывает эти данные в список автобусов, находящихся на маршруте; 3) при въезде каждого автобуса в парк вводится номер автобуса, и программа удаляет данные об этом автобусе из списка автобусов, находящихся на маршруте, и записывает эти данные в список автобусов, находящихся в парке; 4) по запросу выдаются сведения об автобусах, находящихся в парке, или об автобусах, находящихся на маршруте.
  2.  Предметный указатель организован как массив. Каждая компонента указателя содержит слово и номера страниц, на которых это слово встречается (прикрепление номеров к каждой компоненте организовано в виде линейного односвязного списка). Количество номеров страниц, относящихся к одному слову, не ограничивается. Составить программу, которая обеспечивает: 1) чтение предметного указателя из файла, в котором указывается количество слов (в дальнейшем количество изменяться не будет); 2) вывод предметного указателя; 3) вывод номеров страниц для заданного слова; 4) добавление номера страницы для имеющегося слова; 5) удаление номера страницы для заданного слова. Список слов не изменяется в программе. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
  3.  Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержит: пункт назначения; номер рейса; фамилию и инициалы пассажира; желаемую дату вылета. Программа должна обеспечивать: 1) хранение всех заявок в виде линейного двусвязного списка; 2) добавление заявок в список; 3) удаление заявок; 4) вывод заявок по заданному номеру рейса и дате вылета; 5) вывод всех заявок.
  4.  Англо-русский словарь построен как циклический односвязный список. Каждая компонента содержит английское слово, соответствующее ему русское слово и счетчик количества обращений к данной компоненте. В процессе эксплуатации словаря при каждом обращении к компоненте в счетчик обращений добавляется единица. Составить программу, которая: 1) обеспечивает начальный ввод словаря с конкретными значениями счетчиков обращений; 2) добавление новой компоненты в словарь с переводом; 3) удаление существующей компоненты из словаря; 4) вывод словаря на экран полностью (без увеличения счетчика обращений); 5) вывод перевода введенного английского слова, с увеличением  счетчика обращений. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
  5.  Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержат: пункт назначения; номер рейса; фамилию и инициалы пассажира; желаемую дату вылета. Программа должна обеспечивать: 1) хранение всех заявок в виде линейного односвязного списка; 2) добавление и удаление заявок; 3) по заданному номеру рейса и дате вылета вывод заявок с их последующим удалением; 4) вывод всех заявок.
  6.  На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована как двоичное дерева. Составить программу, которая: 1) обеспечивает начальное формирование картотеки в виде циклического двусвязного списка; 2) производит вывод всей картотеки; 3) вводит номер телефона и время разговора; 4) выводит извещение на оплату телефонного разговора. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
  7.  Составить программу, которая содержит динамическую информацию об автобусах и водителях. Сведения о каждом автобусе содержат его номер и номер маршрута, признак того, где находится автобус – на маршруте или в парке. Сведения о каждом водителе содержат его фамилию и инициалы и признак того, свободен ли водитель или нет. Программа должна обеспечивать: 1) начальное формирование данных о всех водителях и автобусах в парке в виде массивов (количество элементов изменяться не будт); 2) при постановке автобуса на маршрут (выезде из парка) из списка свободных на данный момент автобусов выбирается номер автобуса (аналогично с водителем), и программа устанавливает значение признака «автобус на маршруте» и «водитель на маршруте», а также соответствие водитель-автобус, формируя при этом линейный односвязный список; 3) при въезде каждого автобуса в парк вводится номер автобуса или ФИО водителя, и программа устанавливает значение признака «автобус в парке» и «автобус свободен»; 4) по запросу выдаются сведения об автобусах, находящихся в парке, свободных водителях, об автобусах и их водителях, находящихся на маршруте.
  8.  Составить программу, отыскивающую проход по лабиринту. Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице. Программа находит выход из лабиринта, двигаясь от заданного квадрата. После отыскания прохода программа выводит найденный путь от начального квадрата до выхода в виде координат квадратов. Для хранения пути использовать односторонний стек, реализованный в виде двусвязного списка.
  9.  Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается: номер поезда; станции отправления и назначения; время отправления. Данные в информационной системе организованы в виде линейного списка. Составить программу, которая: 1) обеспечивает первоначальный ввод данных в информационную систему и формирование линейного односвязного списка; 2) производит вывод всего списка; 3) вводит номер поезда и выводит все данные об этом поезде; 4) вводит название станции и выводит данные обо всех поездах, следующих с этой станции, а затем данные обо всех поездах, следующих до этой станции. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
  10.  Гаражная стоянка имеет одну стояночную полосу, причем въезд и выезд находятся в одном конце полосы. Если владелец автомашины приходит забрать свой автомобиль, который не является ближайшим к выходу, то все автомашины, загораживающие проезд, удаляются, машина данного владельца выводится со стоянки («перегон»), а другие машины возвращаются на стоянку в исходном порядке. Написать программу, которая моделирует процесс прибытия и отъезда машин. Прибытие или отъезд автомашины задается командной строкой, которая содержит признак прибытия или отъезда и номер машины. Программа должна выводить сообщение при прибытии или выезде любой машины. При выезде автомашины со стоянки сообщение должно содержать число раз, которое машина удалялась со стоянки для обеспечения выезда других автомобилей. Реализовать с помощью основного (стоянка) и временного (перегон) односторонних стеков, реализованный в виде односвязного списка.
  11.  В файловой системе каталог файлов организован как циклический двусвязный список. Для каждого файла в каталоге содержатся следующие сведения: имя файла; дата создания; количество обращений к файлу. Составить программу, которая обеспечивает: 1) начальное формирование каталога файлов; 2) вывод каталога файлов; 3) удаление файлов, дата создания которых меньше заданной; 4) выборку файла с наибольшим количеством обращений. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
  12.  Предметный указатель организован как циклический односвязный список. Каждая компонента указателя содержит слово и номера страниц, на которых это слово встречается. Количество номеров страниц, относящихся к одному слову, не более десяти. Составить программу, которая обеспечивает: 1) добавление слов к предметному указателю; 2) вывод предметного указателя с номерами страниц для каждого слова; 3) вывод номеров страниц для заданного слова; 4) удаление слова из списка. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
  13.  Словарь терминов организован как циклический двусвязный список. Каждый термин содержит определение – текст, длиной не более 255 символов. Составить программу, которая обеспечивает: 1) чтение словаря из файла; 2) вывод всех терминов словаря; 3) вывод определения для заданного термина; 4) добавление термина с определением; 5) удаление термина; 6) замена определения для заданного термина. Программа должна обеспечивать диалог с помощью меню и вывод сообщений об ошибке, если термин не найден.
  14.  Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: номер УДК; фамилию и инициалы автора; название; год издания; количество экземпляров данной книги в библиотеке, количество экземпляров данной книги на руках. Программа должна обеспечивать: 1) начальное формирование данных о всех книгах в библиотеке в виде линейного двусвязного списка; 2) при взятии каждой книги вводится номер УДК, и программа уменьшает значение количества книг на единицу или выдает сообщение о том, что требуемой книги в каталоге нет, или все экземпляры требуемой книги находятся на руках; 3) при возвращении каждой книги вводится номер УДК, и программа увеличивает значение количества книг на единицу (либо выдает сообщение о том, что в каталоге данной книги нет); 4) по запросу выдаются сведения о наличии книг в библиотеке.
  15.  Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: номер УДК; фамилию и инициалы автора; название; год издания; количество экземпляров данной книги в библиотеке. Программа должна обеспечивать: 1) начальное формирование данных о всех книгах в библиотеке в односвязном циклическом списке; 2) добавление данных о книгах, вновь поступающих в библиотеку; 3) удаление данных о списываемых книгах; 4) по запросу выдаются сведения о наличии книг в библиотеке, упорядоченные по выбранному полю.
  16.  Картотека в бюро обмена квартир организована как линейный двусвязный список. Сведения о каждой квартире содержат: количество комнат; этаж; площадь; адрес. Составить программу, которая обеспечивает: 1) начальное формирование картотеки; 2) ввод заявки на обмен; 3) поиск в картотеке подходящего варианта: при равенстве количества комнат и этажа и различии площадей в пределах 10% выводится соответствующая карточка. Если подходящих карточек более одной, то предлагается выбрать из списка либо отказаться от обмена; если найдена только одна подходящая карточка, то предлагается подтверждение обмена. Подтвержденная карточка удаляется из списка, в противном случае поступившая заявка включается в список; 4) вывод всего списка.
  17.  Анкета для опроса населения содержит сведения о респонденте: ФИО; возраст; пол; образование (начальное, среднее, неоконченное высшее, высшее); и ответ на вопрос анкеты либо «ДА», либо «НЕТ». Составить программу, которая: 1) обеспечивает чтение анкет и ответов на них из файла и формирует линейный односвязный список; 2) обеспечивает поиск анкет по сформированному запросу, содержащему: а) начальные буквы фамилии (или фамилию целиком); б) возраст в виде диапазона; в) пол – мужской/женский/оба; г) образование в виде любых комбинаций указанных в задании вариантов; 3) производит вывод всех анкет и ответов на вопросы. Если в результате поиска не найдено ни одной анкеты, то выводится соответствующее сообщение. Программа должна обеспечивать диалог с помощью меню.
  18.  Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: номер УДК; фамилию и инициалы автора; название; год издания; количество экземпляров данной книги в библиотеке. Программа должна обеспечивать: 1) начальное формирование данных о всех книгах в библиотеке в виде циклического односвязного списка; 2) добавление данных о книгах, вновь поступающих в библиотеку; 3) удаление данных о списываемых книгах; 4) по запросу выдаются сведения о наличии книг в библиотеке, упорядоченные по годам издания.
  19.  На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована как линейный список. Составить программу, которая обеспечивает: 1) начальное формирование картотеки в виде линейного двусвязного списка; 2) вывод всей картотеки; 3) ввод номера телефона и время разговора; 4) вывод извещения на оплату телефонного разговора. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.


 

А также другие работы, которые могут Вас заинтересовать

18342. Выявление уязвимостей компьютерных сетей 140 KB
  Выявление уязвимостей компьютерных сетей Системы обнаружения атак Существует три этапа осуществления атаки. Первый подготовительный этап заключается в поиске предпосылок для осуществления той или иной атаки. На этом этапе ищутся уязвимости использование которых
18343. Экранирование и межсетевые экраны 141.5 KB
  Экранирование и межсетевые экраны Основные понятия По материалам руководящего документа Государственной технической комиссии России межсетевой экран МЭ представляет собой локальное однокомпонентное или функциональнораспределенное средство комплекс реализу
18344. Протоколы безопасности 1.86 MB
  Протоколы безопасности Протоколами безопасности на транспортном уровне являются Secure Socket Layer SSL и Secure Shell Protocol SSH которые обеспечивают безопасную передачу данных между клиентом и сервером. Оба протокола разработаны рабочей группой IETF по безопасности транспортног
18345. Сутність, призначення і роль бюджету держави 18.48 KB
  Тема 1. Сутність призначення і роль бюджету держави Хронологічна таблиця історії виникнення та розвитку бюджету Дата Подія 1215 р. Прийнято Велику хартію вольностей[3 C.33] 1302 p. ...
18346. Бюджет як основний фінансовий план держави 68.14 KB
  Тема 2. Бюджет як основний фінансовий план держави Таблиця2.1. Трактування сутності понять Джерело Визначення Казначейська система: Підручник / Юрій С.І. Стоян В.І. Мац М.Й. Тернопіль 2002. БЮДЖЕТНЕ ПЛАНУВАНН
18347. Бюджетний дефіцит і джерела його фінансування 90 KB
  Тема 4. Бюджетний устрій та побудова бюджетної системи Порівняльна характеристика складу структури бюджетної системи України та Чехії. 1. Бюджетна система Існує три варіанти виокремлення видів бюджетів: створення єдиного для всієї країни бюджету на загальноде
18348. Бюджетний процес 30.32 KB
  Тема 5. Бюджетний процес Таблиця 5.1. Аналіз бюджетного процесу на державному та місцевому рівнях Стадії бюджетного процесу Учасники бюджетного процесу Функції учасників бюджетного процесу Тер...
18349. Міжбюджетнівідносини і система бюджетноговирівнювання 26.3 KB
  Тема 6. Міжбюджетнівідносини і система бюджетноговирівнювання Частина 1 Таблиця 6.1. Трактування вітчизняними та зарубіжними науковцями сутності поняття бюджетне регулювання Джерело Визначення Бюджетна си...
18350. Система доходів бюджету 33.25 KB
  Тема 7. Система доходів бюджету Частина 1 Таблиця 7.1 Джерела Визначення Бюджетна система. Вишкіл студії: Навчальний посібник / За ред. С. І. Юрія О. П. Кириленко. – Тернопіль: Економічна думка 2010. – 424 с. – С. 84. ...