42028

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

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

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

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

Русский

2015-01-18

56.5 KB

127 чел.

Лабораторная работа № 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) вывод извещения на оплату телефонного разговора. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.


 

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

37272. Сучасні методи активізації навчальної діяльності військовослужбовців 178 KB
  Оголосити тему заняття, її актуальність та звязок з іншими темами, мету та навчальні питання, які будуть розглянуті. Особливу увагу на занятті необхідно звернути на те, що існує обєктивна потреба в оволодінні всім офіцерським складом загальними поняттями про психологію спілкування у військовому колективі, а також розкрити сутність
37273. Правоохранительные органы 175 KB
  Проработка включенных в программу тем дает отправные знания о понятии правоохранительной деятельности и её значении в российской правовой системе основных направлениях функциях и органах осуществляющих её о судебной власти правосудии и судах их построении и основных полномочиях об организационном обеспечении деятельности судов и органах его осуществляющих о прокурорском надзоре и прокуратуре о выявлении и расследовании преступлений и занимающихся этим учреждениях об адвокатской деятельности и адвокатуре иных формах оказания...
37274. Применение языка PHP, СУБД MySQL и фреймворка CodeIgniter для разработки динамических веб-сайтов 959 KB
  Курсовая работа посвящена возможностям применения языка PHP, системы управления базами данных (СУБД) MySQL, фреймворка CodeIgniter для разработки динамических веб-сайтов. Апробация данных технологий проводится на примере создания фронт-части (front-end) веб-сайта для сети мебельных магазинов «Комфорт+»
37275. Розрахунок і конструювання монолітного ребристого залізобетонного перекриття з балочними плитами 2.33 MB
  0184 Визначення кількості стержнів армування Розрахунок і конструювання другорядної балки Розрахункова схема балки Статичний розрахунок балки Уточнення розмірів перерізу балки Розрахунок міцності балки в нормальних перерізах Розрахунок міцності балки в похилих перерізах Розрахунок на дію поперечної сили Розрахунок на дію згинального моменту Побудова обгинаючої епюри моментів Побудова епюри матеріалів Конструювання перерізу 11 Конструювання перерізу 22 Конструювання перерізу 33 Розрахункові перерізи для епюри...
37276. Исследование методов и алгоритмов работы трансляторов предметно-ориентированных языков 889.5 KB
  Для описания семантических функций синтаксической диаграммы расстановки ссылок использованы следующие обозначения: Tb_Lexems[.Code массив кодов лексем; Tb_Lexems[.Vlue массив значений лексем; Number_Lexem номер очередной рассматриваемой лексемы в массиве лексем; Stek_do стек для циклов WHILE; Stek_if стек для развилок IF; Stek_cse – стек для операторовпереключателей SWITCH; Stek_to – стек для циклов FOR. Рисунок 3 Рсхема расстановки ссылок Семантические функции к Рсхеме расстановки ссылок на рисунке 3: y0:...
37277. Багатоповерхова каркасна будівля 525.5 KB
  Розрахунок та конструювання другорядної балки. Розрахункова схема балки. Статичний розрахунок балки. Конструктивний розрахунок допоміжної балки.
37278. Теория государства и права, учебник 4.32 MB
  Садовничий ректор Московского университета академик РАН профессор Введение Вопросам теории государства и права в отечественной и зарубежной юридической литературе традиционно уделяется большое внимание. Определение и основное разделение права М. Лекции по общей теории права СПб.
37279. ПРИМЕНЕНИЕ ТЕХНОЛОГИЙ JAVA И JAVAFX ДЛЯ РАЗРАБОТКИ ВИРТУАЛЬНЫХ ЛАБОРАТОРИЙ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ 912.5 KB
  Методы моделирования в настоящее время внедрились практически во все сферы человеческой деятельности: технические, социально-экономические, сложные экономические, общественные, сферы международных отношений и др. Это связано с необходимостью расширения и углубления знаний реального мира. Существует множество реальных объектов и процессов, информацию о которых мы не можем получить из-за малости или масштабности размеров (объекты микро- и макрокосмоса); высоких или криогенных температур.