42028

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

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

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

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

Русский

2015-01-18

56.5 KB

126 чел.

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


 

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

47025. Формы первичного туберкулеза. Особенности течения туберкулезного процесса 45.5 KB
  Характеризуется поражением лимфатических узлов лимфогематогенной диссеминацией возбудителя и высокой реактивностью организма к возбудителю заболевания. Безболезненное увеличение периферических лимфатических узлов окружённых более мелкими лимфатическими узлами. Различают следующие клинические формы первичного туберкулёза: туберкулёзная интоксикация у детей и подростков; туберкулёз внутригрудных лимфатических узлов; первичный туберкулёзный комплекс; хронически текущий первичный туберкулёз. Характерно...
47028. Вина, пересыщенные диоксидом углерода, их классификация, свойства, особенности технологии. Сорта, разрешенные в РФ для производства шампанского. Технологические требования к сортам винограда 45.83 KB
  Вина пересыщенные диоксидом углерода их классификация свойства особенности технологии. Вина пересыщенные диоксидом углерода составляют особую группу отличаются по своему внешнему виду букету и вкусовому сложению. Вина пересыщенные диоксидом углерода делятся на два основных типа: игристые и газированные шипучие. Игристые вина получают пересыщением диоксидом углерода образующимся при вторичном брожении.
47029. Теории игры (К.Гроос, Ф.Бойтендайк). Проблемы детской игры в теориях: В.Штерна, 3.Фрейда, Ж.Пиаже, К.Коффки, К.Левина, Л.С. Выготского) 46 KB
  Теории игры К. Проблемы детской игры в теориях: В. период развития и роста когда оно не может самостоятельно поддерживать свою жизнь г это время детства имеет целью сделать возможным приобретение приспособлений необходимых для жизни но не развивающихся непосредственно из прирожденных реакций д унаследованные реакции в связи с импульсивной потребностью в деятельности сами стремятся к проявлению и таким образом сами дают повод к новоприобретениям так что над прирожденной основой образуются приобретенные навыки е выработка...
47030. РЕАЛИЗАЦИЯ БИОЛОГИЧЕСКОЙ ИНФОРМАЦИИ В КЛЕТКЕ 46 KB
  Функция рибосом заключается в узнавании трехнуклеотидных кодонов мРНК сопоставлении им соответствующих антикодонов тРНК несущих аминокислоты и присоединении этих аминокислот к растущей белковой цепи. Для узнавания аминокислот в клетке имеются специальные молекулы тРНК. Присоединение аминокислот к тРНК осуществляется в энергозависимой реакции ферментами аминоацилтРНКсинтетазами а получившаяся молекула называется аминоацилтРНК. Таким образом специфичность трансляции определяется взаимодействием между кодоном мРНК и антикодоном тРНК а...