42028

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

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

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

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

Русский

2015-01-18

56.5 KB

138 чел.

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


 

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

75543. Літні канікули. Повторення розділових запитань (Disjunctive Questions) 22.06 KB
  Повторення розділових запитань Disjunctive Questions. Обладнання: підручник тематична картина Літні канікули граматична таблиця Disjunctive Questions 37 Reference Grmmr; українськоанглійські словники речення і розділові питання для гри Find your prtner НО1. We hve to review the grmmr the building of the disjunctive questions to use them in our speech mking it more nturl. By the end of the lesson you should be ble: to use the tgquestions in your dilogues; to use your imgintion describing pictures.
75544. Україна. Географічне положення. Загальна характеристика. Нові ЛО 24.58 KB
  Ввести нові ЛО та відпрацювати їх вживання в мові. Практикувати учнів у читанні тексту з метою отримання загального уявлення (skimming) та з метою максимально повного й точного розуміння всієї інформації, що в ньому міститься (scanning)
75545. Географічне положення та державний устрій України 24.82 KB
  Т: We re going to tlk bout the politicl structure of Ukrine nd its geogrphicl position. By the end of the lesson you should be ble: to recognize nd understnd new words nd word combintions from the topic: The politicl structure of Ukrine in the text; to listen for the min ide nd specific informtion; to tlk bout the politicl structure of Ukrine in brief. One student from the clss is selected who thinks of geogrphicl plce in Ukrine tht must be guessed by the rest of the clss. Exmple: Is it river Is it mountin Is it one of the lrgest cities...
75546. Україна. Життя молоді, План-конспект уроку з англійської мови для учнів 9-х класів 23.9 KB
  People Підтема: Україна. re ll young people like Of course not. Thts why teengers esily come under the influence of other people. Young people re crzy bout music.
75547. Культура та наука в Україні, План-конспект уроку з англійської мови для учнів 9-х класів 22.03 KB
  Обладнання: підручник текст Culture nd Science in Ukrine HO1 Who is who H02. Т: We continue our work on the topic Ukrine. We re going to tlk bout culture nd science in Ukrine. By the end of the lesson you should be ble: to prticipte in common converstionl exchnges nd tell bout this topic using tl text nd wordcombintions s pln; to operte fcts bout Ukrine in new situtions.
75548. Київ - столиця України. Повторення ЛО теми Town Features 25.32 KB
  Обладнання: підручник слайди фотографії комплект учбових картин з видами міста Києва роздавальний матеріал round Kyiv НО1 картки з коротким описанням визначних місць Києва Н02 Mtch the English words nd word combintions with their Ukrinin equivlents H03 Which sentences do not fit to the text bout Kyiv HO4. Т: The topic of our...
75549. Київ - столиця України, План-конспект уроку з англійської мови для учнів 9-х класів 24.87 KB
  Активізація лексичного матеріалу теми Town Fetures. Активізація лексичного матеріалу теми Town Fetures. Т: There re mny ncient towns in Ukrine. Wht other ncient towns do you know Is your town villge old or new re there ny interesting fcts in the history of your town villge Why re people interested in the histories of cities towns nd villges Cn you explin the choice of nmes for some cities towns or villges Is the plce for town or villge chosen by chnce or for purpose Cn you give n exmple of it 2 WhileReding ctivities.