2015-05-10
1235
Тема. Линейные двунаправленные связанные списки
Цель.
· Получить практические навыки по созданию и по управлению двунаправленными списками
Задание
Создать многомодульное приложение, демонстрирующее выполнение операций над двунаправленным списком. В заголовочном файле определить структуру узла и функции, реализующие операции над списком.
Требования к разработке.
Во всех вариантах для основного списка реализовать операции:
1 вывод списка от первого элемента к последнему;
2 вывод списка от последнего элемента к первому;
3 создание списка из n элементов, вставляя новый элемент перед первым элементом;
а так же дополнительные операции, определенные заданием варианта.
ВАРИАНТЫ
| Вариант | Вид списка | Тип информационной части узла списка | Дополнительные Операции |
| 1. | Список с двумя указателями | Номер абонемента, Название книги, дата выдачи, дата возврата, дата фактического возврата. | 1. Вставить новый узел в список после последнего узла с таким же номером абонента(дата фактического возврата еще не заполнена). 2. Изменить значение поля фактической даты возврата по указанной книге, указанного абонемента. 3. Удалить узлы, в которых дата возврата и дата фактического возврата совпадают. 4. Определить количество книг, заданного абонемента. |
| 2. | Список с головным элементом | Номер мед. полиса, Дата обращения, Код диагноза (число). | 5. Вставка нового узла перед первым узлом с заданным значением Мед. полиса, если такого нет, то узел вставить в конец списка. 6. Удаление из списка всех узлов с заданным значением Кода диагноза. 7. Переместить все узлы с одинаковым мед. полисом в новый список. 8. Определить количество обращений в одну и туже дату с одним и тем же диагнозом. |
| 3. | Циклический список с указателем на вершину | Номер счета в банке, дата,вид операции (приход или расход), сумма вклада. Примечание: По одному счету может быть несколько узлов. | 9. Вставка нового узла перед первым узлом. 10. Удаление сведений по счету (всех узлов), у которого общая сумма вклада равна нулю (сумма по приходу, минус сумма по расходу). 11. Создать новый список из исходного, которого будет содержать остаток по всем видам операций одного счета, указав вид операции – приход, и текущую дату. 12. Определить количество узлов по одному номеру счета. |
| 4. | Циклический список с головным элементом | Номер автобусного маршрута, время отправления (целое число), номер автобуса, стоимость одной поездки, дата отправления. Примечание: По одному номеру автобуса может быть несколько узлов. | 13. Вставить новый узел после последнего узла с заданным номером автобуса. 14. Удалить все узлы заданного автобуса. 15. Подсчитать, сколько раз автобус выходил на маршрут в течении заданного дня. 16. Сколько рейсов в течении указанного дня сделал каждый автобус. |
| 5. | Список с двумя указателями | Код товара, дата продажи, цена, отметка о возврате. | 17. Отсортировать список, располагая элементы в хронологическом порядке. 18. Удалить все узлы по заданному товару, проданному в указанную дату. 19. Сформировать новый список, из узлов исходного, по тем товарам, по которым имеется возврат. 20. Определить, какой вид товара чаще возвращают. |
| 6. | Список с головным элементом | Номер железнодорожного билета, станция назначения, номер поезда, номер вагона, номер места, стоимость проезда, дата продажи, дата отправления поезда, время в пути. | 21. Вставить новый узел в список, упорядоченный по номеру вагона. 22. Удалить сведения о билетах, пассажиры которых добрались уже до места (оценка по текущей дате). 23. Сформировать новый список из узлов исходного, включив в него сведения о тех проданных билетах, по которым пассажиры поедут в указанную дату. 24. Определить номер вагона в который продано больше всего билетов. |
| 7. | Циклический список с указателем на вершину | Марка автомобиля, страна изготовитель, год выпуска | 25. Вставить новый узел по автомобилю так, чтобы он разместился в списке своего модельного ряда, перед узлом, год выпуска которого меньше. 26. Сформировать новый список, узел которого содержит данные: марка автомобиля, указатель на начало модельного ряда этой марки в исходном списке. 27. Удалить информацию обо всех автомобилях заданной марки из исходного списка, поиск первого узла модельного ряда, осуществить с помощью нового списка. 28. Определить, каких автомобилей меньше всего. Если таких автомобилей несколько, то указать марку первого встреченного. |
| 8. | Циклический список с головным элементом | Марка автомобиля, страна изготовитель, год выпуска, цена. Дата продажи (заполняется не сразу). | 29. Упорядочить созданный список из n узлов так, чтобы узлы были упорядочены по стране изготовителю (будут сформированы подсписки по стране). 30. Вставить новый узел со сведениями об автомобиле какой-то страны в начало своего подсписка. 31. Установить дату продажи проданному автомобилю. 32. Удалить все узлы по проданным автомобилям. |
| 9. | Список с двумя указателями | Инвентарный номер книги, указатель на список областей знаний (к которым относится книга, при создании списка указатель равен NULL), Автор, Название, Год издания. Примечание. Список областей знаний это тоже линейный список, информационная часть которого содержит название области. | 33. Вставить новый узел со сведениями о книге после последнего узла. 34. Сформировать новый список из значений списков по областям знаний, включив название области только один раз. 35. Удалить узлы со сведениями по книгам определенного автора и изданные после указанного года. 36. Часть списка, начиная с узла с заданным номером и до конца списка, перенести в начало списка |
| 10. | Список с головным элементом | Код товара, дата продажи, цена, отметка о возврате, дата возврата. | 37. Упорядочить список по правилу: сначала проданные, но не возвращенные, а затем возвращенные. 38. Переформировать список следующим образом: часть списка, содержащая возвращенный товар перенести в начало исходного списка. 39. Удалить товар, который продан до указанной даты. 40. Определить количество проданного в указанную дату товара. |
| 11. | Циклический список с указателем на вершину | Номер мед. полиса, указатель на линейный список (узлы которого содержат: Код заболевания и Дата регистрации заболевания зарегистрировано), фамилия больного. | 41. Вставить в начало списка заболеваний пациента новый узел. 42. Сформировать новый список, включив в него информацию о пациентах, у которых зарегистрировано более 5 заболеваний. 43. Удалить из списка кодов заболеваний указанного пациента, узел с указанным кодом. 44. Определить количество заболеваний у заданного пациента. |
| 12. | Циклический список с головным элементом | Номер зач. книжки, Номер группы, Фамилия студента, Указатель на линейный список сведений по результатам сессии (узел этого списка содержит: Название дисциплины, Оценка, Номер семестра). | 45. Упорядочить исходный список по номеру группы. 46. Вставить сведения о новом студенте, об успеваемости которого еще нет сведений, перед узлом, номер зачетной книжки в котором меньше номера зач. книжки нового студента. 47. Удалить все сведения о студентах заданной группы. 48. Определить количество групп, в которых сдавали заданный экзамен. |
| 13. | Список с двумя указателями | Номер зач. книжки, Номер группы, Оценка. | 49. Вставить новый узел перед первым узлом с таким же ключом, если такого узла еще нет, то вставить перед первым узлом, у которого ключ больше. 50. Удалить узлы с указанным номером зачетной книжки. 51. Сформировать новый список из исходного, включив в него узлы с оценкой неуд, исключив их при этом из исходного списка. 52. Определить средний балл студента с указанной зачетной книжкой. |
| 14. | Список с головным элементом | Номер телефона (из 7 цифр), время разговора (целое число), номер телефона вызываемого абонента. | 53. Добавить новый узел в список, упорядочивая узлы по первым четырем цифрам телефона. 54. Удалить последний узел с заданным значением телефона. 55. Подсчитать суммарное время разговора с заданного телефона. 56. Сформировать новый двунаправленный список из узлов исходного списка, начинающихся с заданных четырех цифр, но в котором первым узлом будет последний узел в подсписке узлов с заданными четырьмя цифрами. Этот подсписок удалить из исходного. |
|
|
|
|
|
|
|
|
|
