42028

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

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

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

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

Русский

2015-01-18

56.5 KB

150 чел.

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


 

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

45907. Методы организации производства. Факторы, влияющие на выбор методов организации производства 12.36 KB
  Методы организации производства это совокупность приемов и операций изготовления продукции выполняемых при определенном сочетание элементов производственного процесса. номенклатура выпускаемой продукции 2. периодичность выпуска продукции 4. трудоемкость изготовления продукции 5.
45908. Организация непоточного производства: признаки и способы организации 27 KB
  Признаки непоточного производства А обработка на рабочих местах различных по конструкции структуре и технологии изготовления предметов труда; Б незначительный выпуск однородных предметов труда; В рабочие места размещаются по однотипным группам оборудования без определенной связи с последовательностью выполнения операций; Г предметы труда перемещаются в процессе изготовления продукции сложными маршрутами в связи с чем возникают значительные перерывы в обработке и требуются промежуточный склады для хранения незавершенного производства в...
45909. Характеристики партионного производства 14.14 KB
  Партионный способ организации производственных процессов ПП имеет следующие особенности: А предметы труда и изделия изготавливаются периодически повторяющимися партиями определенного размера; Б размер партии предметов труда определяется с учетом конкретных производственных условий; В разрабатывается специальный порядок запуска предметов труда в производство; Г имеется незавершенное производство; Д используется в условиях среднесерийного производства. Партионное производство характеризуется следующими параметрами: 1 размер партии...
45910. Организация гибкого автоматизированного производства. ГАП 14.11 KB
  ГАП. ГАП автоматизированное производство линия участок цех функционирующее как единое целое на основе безлюдной или при минимальном участии человека. ГАП включает технологическое оборудование а так же складские транспортные контролирующие системы и другие компоненты на базе ЧПУ и использованием средств вычислительной техники. Работа всех компонентов ГАП координируется как единого целого при помощи многоуровневых распределенных микропроцессорных систем управления.
45911. Организация гибких производственных систем 14.94 KB
  ГПС совокупность оборудования с ЧПУ в различных сочетаниях гибких производственных модулей ГПМ робототизированных технологических комплексов РТК отдельных единиц технологического оборудования с ЧПУ систем транспортных и складских операций средств контроля и систем обеспечения их функционирования в автоматическом режиме в течении определенного периода времени от половины смены и более . ГПС организационнотехнологическая производственная система позволяющая в условиях мелко средне и в отдельных случаях крупносерийного...
45912. Сущность и признаки поточного производства 12.83 KB
  Наиболее прогрессивным методом организации производства является поточным. Для внедрения поточного производства создаются поточные линии представляемые собой совокупность рабочих мест расположенных в последовательности соответственной очередности операций ТП. Признаки поточного производства: на каждой поточной линии изготавливаются однотипные детали; на каждом рабочем месте а иногда и на нескольких предусмотрено выполнение определенных операций; рабочие места располагаются в соответствии с последовательность операций ТП; передача...
45913. Организация поточного производства. Характеристики и условия перехода к поточной форме организации производства 13.21 KB
  Значительный объем выпуска однотипных изделий для чего стремятся максимально унифицировать конструкцию выпускаемых изделий; 2.отработка конструкций изделий с точки зрения групповых поточных технологий. Поточные линии могут быть ограничены пределами участка а могут распространятся и на несколько участков например: сборочные конвейеры носят характер общезаводского сквозного потока когда все производственные операции начинают с поступления материала и сырья в обработку до сдачи готовых изделий на склад выполняются в рамках...
45914. Организация инструментального хозяйства. Задачи и состав инструментального хозяйства 13.85 KB
  Задачи и состав инструментального хозяйства. Основная задача инструментального хозяйства обеспечение рабочих позиций высококачественными инструментами и оснасткой. Содержание деятельности инструментального хозяйства: 1определение потребности и планирование обеспечения подразделений предприятия инструментом и оснасткой.
45915. Методы планирования потребности в инструменте и технологической оснастке 14.69 KB
  Планирование инструмента оснастки потребного для изготовления производственной программы т. расходного фонда инструмента может быть осуществлено несколькими способами: 1укрупненным методом или статическим: на основе отчетных документов содержащих данные о расходе инструмента за предыдущий период составляются расходные нормативы по которым определяется потребность на следующий период. Определение потребности по каждому виду оснастки инструмента производится путем расчета. для режущего инструмента NH объем выпуска изделий...