Занятие 6 (двунаправленный список). Отчет по разработке программы в соответствии с требованиями задания по однонаправленному списку
 Скачать 141.1 Kb.
|
|
1 Занятие 6. Двунаправленные динамические списки Цель: получение знаний и практических навыков управления двунаправленным списком в программах на языке С++. 1 Задание. Разработать многомодульную программу, которая демонстрирует выполнение всех операций, определенных вариантом, над линейным двунаправленным динамическим списком. Требования к разработке. 1. Разработать структуру узла списка, структура информационной части узла определена вариантом. Для определения структуры узла списка, используйте тип struct или class. Сохраните определение структуры узла и прототипы функций в заголовочном файле. 2. Разработайте функции для выполнения операции над линейным двунаправленным динамическим списком: • создание списка; • вставку узла; • удаление узла; • вывод списка в двух направлениях (слева направо и справа налево); • поиск узла с заданным значением (операция должна возвращать указатель на узел с заданным значением). 3. Дополнительные операции над списком, указанные вариантом, оформите в виде функций и включите в отдельный файл с расширением cpp. Подключите к этому файлу заголовочный файл с определением структуры узла. 4. Разработайте программу, управляемую текстовым меню, и включите в меню демонстрацию выполнения всех операций задания и варианта. 5. Проведите тестирование операций. • Оцените сложность алгоритма первой дополнительной операции. 6. Оформите отчет по разработке программы в соответствии с требованиями задания по однонаправленному списку. Примечание: в определении информационной части узла варианта, подчеркнутое поле считать полем ключа. 2 Варианты Вариант Тип информационной части узла списка Дополнительные Операции 1 Номер зач. книжки (буквенно-цифровой), Номер группы, Оценка. Вставить новый узел перед первым узлом с таким же ключом, если такого узла еще нет, то вставить 2 перед первым узлом, у которого ключ больше. Удалить узлы с указанным номером группы. Сформировать Oновый список из исходного, включив в него узлы с оценкой неуд, исключив их при этом из исходного списка. 2 Номер телефона (из 7 цифр), время разговора (целое число), номер телефона вызываемого абонента. Добавить новый узел в список, упорядочивая узлы по первым четырем цифрам телефона в порядке возрастания. Удалить последний узел с заданным значением телефона. Подсчитать суммарное время разговора с заданного телефона. 3 Номер абонемента (буквенно-цифровой), Название книги, дата выдачи, дата возврата, дата фактического возврата. Вставить новый узел в список после последнего узла с таким же номером абонента(дата фактического возврата еще не заполнена). Изменить значение поля фактической даты возврата по указанной книге, указанного абонемента. Удалить узлы, в которых дата возврата и дата фактического возврата совпадают. Определить количество книг, заданного абонемента. 4 Номер мед. полиса (буквенно-цифровой), Дата обращения, Код диагноза (число). Вставка нового узла перед первым узлом с заданным значением Мед. полиса, если такого нет, то узел вставить в конец списка. Удаление из списка всех узлов с заданным значением Кода диагноза. Переместить все узлы с одинаковым мед. полисом в новый список. 3 Определить количество обращений в одну и туже дату с одним и тем же диагнозом. 5 Номер счета в банке (20- значное число), дата, вид операции (приход или расход), сумма вклада. Вставка нового узла перед первым узлом. Удаление сведений по счету (всех узлов), у которого общая сумма вклада равна нулю ( сумма по приходу, минус сумма по расходу). Создать новый список из исходного, которого будет содержать остаток по всем видам операций одного счета, указав вид операции – приход, и текущую дату. 6 Номер автобусного маршрута, время отправления (целое число), номер автобуса (формат госномера автотранспорта в России), стоимость одной поездки, дата отправления. Вставить новый узел после последнего узла с заданным номером автобуса. Удалить все узлы заданного автобуса. Подсчитать, сколько раз автобус выходил на маршрут в течении заданного дня. 7 Код товара (буквенно- цифровой), дата продажи, цена, отметка о возврате. Отсортировать список, располагая элементы в хронологическом порядке. Удалить все узлы по заданному товару, проданному в указанную дату. Сформировать новый список, из узлов исходного, по тем товарам, по которым имеется возврат. 8 Номер железнодорожного билета (буквенно- цифровой), станция назначения, номер поезда, номер вагона, номер места, стоимость проезда, дата Вставить новый узел в список, упорядоченный по номеру вагона. Удалить сведения о билетах, пассажиры которых добрались уже до места (оценка по текущей дате). Сформировать новый список из узлов исходного, включив в него сведения о тех проданных билетах, 4 продажи, дата отправления поезда, время в пути. по которым пассажиры поедут в указанную дату. 9 Марка автомобиля, страна изготовитель, год выпуска Вставить новый узел по автомобилю так, чтобы он разместился в списке своего модельного ряда, перед узлом, год выпуска которого меньше. Сформировать новый список, узел которого содержит данные: марка автомобиля, указатель на начало модельного ряда этой марки в исходном списке. Удалить информацию обо всех автомобилях заданной марки из исходного списка, поиск первого узла модельного ряда, осуществить с помощью нового списка. 10 Марка автомобиля, страна изготовитель, год выпуска, цена. Дата продажи (заполняется не сразу). Упорядочить созданный список из n узлов так, чтобы узлы были упорядочены по стране изготовителю (будут сформированы подсписки по стране). Вставить новый узел со сведениями об автомобиле какой- то страны в начало своего подсписка. Установить дату продажи проданному автомобилю. Удалить все узлы по проданным автомобилям. 11 Инвентарный номер книги (буквенно-цифровой), указатель на список областей знаний (к которым относится книга, при создании списка указатель Вставить новый узел со сведениями о книге после последнего узла. Сформировать новый список из значений списков по областям 5 равен NULL), Автор, Название, Год издания. Примечание: список областей знаний – это тоже линейный список, информационная часть которого содержит название области. знаний, включив название области только один раз. Удалить узлы со сведениями по книгам определенного автора и изданные после указанного года. Часть списка, начиная с узла с заданным номером и до конца списка, перенести в начало списка 12 Код товара (буквенно- цифровой), дата продажи, цена, отметка о возврате, дата возврата. Упорядочить список по правилу: сначала проданные, но не возвращенные, а затем возвращенные. Переформировать список следующим образом: часть списка, содержащая возвращенный товар перенести в начало исходного списка. Удалить товар, который продан до указанной даты. 13 Номер мед. полиса (буквенно-цифровой), указатель на линейный список (узлы которого содержат: Код заболевания и Дата регистрации заболевания зарегистрировано), фамилия больного. Вставить в начало списка заболеваний пациента новый узел. Сформировать новый список, включив в него информацию о пациентах, у которых зарегистрировано более 5 заболеваний. Удалить из списка кодов заболеваний указанного пациента, узел с указанным кодом. 14 Номер зач. книжки (буквенно-цифровой), Номер группы, Фамилия студента, Указатель на линейный список сведений по результатам сессии (узел этого списка содержит: Название дисциплины, Оценка, Номер семестра). Упорядочить исходный список по номеру группы. Вставить сведения о новом студенте, об успеваемости которого еще нет сведений, перед узлом, номер зачетной книжки в котором меньше номера зач. книжки нового студента. Удалить все сведения о студентах заданной группы. 6 15 Номер читателя библиотеки, указатель на сведения о взятых читателем книгах. Сведения о взятой книге: инвентарный номер (число), дата выдачи, дата возврата Добавить сведения о взятой читателем книге Оформить возврат определенной книги Сформировать список книг, которые не вернул читатель в срок. 16 Номер кассы в магазине. указатель на список проведенных кассой операций. Сведения по проведенной операции: код товара, количество, единица измерения (например, кг или штуки), цена за единицу измерения, сумма к оплате за товар, дата операции Добавить сведения о проведенной операции Определить приход по кассе в указанную дату Отменить (удалить) проведенную операцию 17 Номер класса в школьном журнале, указатель на список тем уроков. О каждой теме должны храниться сведения: код дисциплины, название темы, дата изучения темы. Примечание. Для расшифровки названия дисциплины по ее коду создать массив для нескольких дисциплин, элемент массива должен хранить: код и название дисциплины. с кодом Вставить сведения по теме урока по определенной дисциплине в список тем, в конец списка тем данной дисциплины. Сформировать массив (или список) указателей на начало списка тем по определенной дисциплине. Удалить темы по заданной дисциплине. 3 Форма отчета по разработанной программе 1. Постановка задачи – условие задания, требования в соответствии с вариантом. 2. Определение списка операций над списком, которые выявлены в процессе исследования задач: 7 2.1 Определить структуру узла двунаправленного списка в соответствии с вариантом. 2.2 Изобразить (рисунок) для каждой базовой операции полученного списка процесс выполнения операции на существующем списке. 2.3 Изобразите структуру данных, которая будет использоваться в операциях. 2.4 Привести словесное описание алгоритма выполнения операции. 2.5 Привести таблицу тестов для каждой операции. 3. Представить код программы на языке С++. 4. Представить результат тестирования программы: скриншоты выполнения каждой операции. 5. Привести выводы по полученным знания и умениям. |