Курсовая работа
на тему
«Динамические двусвязные списки»
Выполнил студент
I курса
144 группы
очного отделения
Трошин А.И.
Проверил(а):
Колхидашвили М.Р.
Сотемская М.И.
Гатчина
Оглавление
I. Введение. 3
II. Теоретическая часть. 4
III. Задание на курсовую работу. 6
IV. Описание программы.. 7
1. Главное окно. 7
1.1. Кнопка «Добавить». 8
1.2. Кнопка «Редактирование». 9
1.3. Кнопка «Удалить». 10
1.4. Диалог сохранения файла. 10
1.5. Диалог открытия файла. 11
1.6. Кнопка «Поиск по». 12
V. Заключение. 15
VI. Список используемой литературы.. 16
Приложение 1. 16
I. Введение
Связные списки представляют собой динамические (линейные) структуры данных (динамические цепочки звеньев), в которых однотипные элементы (звенья) каким-либо образом связаны между собой, обычно на физическом уровне. Классификация связных списков. По числу связей (и одновременно, направлению) списки бывают односвязными (однонаправленными), двусвязными (двунаправленными) и многосвязными.
Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент списка. Двунаправленный список отличается двумя основными преимуществами.
Во-первых, список может просматриваться в обоих направлениях. Это не только упрощает сортировку списка, но также позволяет пользователям базы данных просматривать данные в обоих направлениях.
Во-вторых, список при нарушении одной из связей может быть восстановлен по другой связи. Это свойство имеет смысл использовать при отказах оборудования, приводящих к нарушению списка.
Целью данной курсовой работы является получение практических навыков в работе с двунаправленными списками.
II. Теоретическая часть
Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным.
Структура, элементами которой служат записи с одним и тем же форматом, связанные друг с другом с помощью указателей, хранящихся в самих элементах, называют связанным списком. В связанном списке элементы линейно упорядочены, но порядок определяется не номерами, как в массиве, а указателями, входящими в состав элементов списка. Каждый список имеет особый элемент, называемый указателем начала списка (головой списка), который обычно по содержанию отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак NULL, свидетельствующий о конце списка.
Линейные связные списки являются простейшими динамическими структурами данных. Из всего многообразия связанных списков можно выделить следующие основные:
· однонаправленные (односвязные) списки;
· двунаправленные (двусвязные) списки;
· циклические (кольцевые) списки..
Для ускорения многих операций целесообразно применять переходы между элементами списка в обоих направлениях. Это реализуется с помощью двунаправленных списков, которые являются сложной динамической структурой.
Двунаправленный (двусвязный) список – это структура данных, состоящая из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы. При этом два соседних элемента должны содержать взаимные ссылки друг на друга.
Итак, каждый элемент двунаправленного списка состоит из трех полей:
1) информационного поля или поля данных;
2) ссылки на следующий элемент списка;
3) ссылки на предыдущий элемент списка.
Рис. 1. Структура двунаправленного списка.
В таком списке каждый элемент (кроме первого и последнего) связан с предыдущим и следующим за ним элементами. Каждый элемент двунаправленного списка имеет два поля с указателями: одно поле содержит ссылку на следующий элемент, другое поле – ссылку на предыдущий элемент и третье поле – информационное. Наличие ссылок на следующее звено и на предыдущее позволяет двигаться по списку от каждого звена в любом направлении: от звена к концу списка или от звена к началу списка, поэтому такой список называют двунаправленным.
Основными операциями, осуществляемыми с двунаправленными списками, являются:
· создание списка;
· печать (просмотр) списка;
· вставка элемента в список;
· удаление элемента из списка;
· поиск элемента в списке
· проверка пустоты списка;
· удаление списка.
Особое внимание следует обратить на то, что в отличие от однонаправленного списка здесь нет необходимости обеспечивать позиционирование какого-либо указателя именно на первый элемент списка, так как благодаря двум указателям в элементах можно получить доступ к любому элементу списка из любого другого элемента, осуществляя переходы в прямом или обратном направлении.
III. Задание на курсовую работу
Разработать программу, реализующую работу с динамическим двусвязным списком.
Элементом списка является любой объект, количество характеристик описывающих объектов должно быть не менее 4.
Программа должна предоставлять следующие функциональные возможности:
- добавлять в список новые элементы;
- редактировать элементы;
- удалять указанный элемент;
- определение наличия элемента в списке (поиск по признаку);
- вывод всех элементов в списке;
- сохранять список в типизированном файле
- загружать список из файла.
Программа разрабатывается в среде разработки приложений Lazarus (официальный сайт https://lazarus.freepascal.org/).
Lazarus — свободная среда разработки программного обеспечения на языке Object Pascal для компилятора Free Pascal (часто используется сокращение FPC — Free Pascal Compiler, свободно распространяемый компилятор языка программирования Pascal). Интегрированная среда разработки предоставляет возможность кроссплатформенной разработки приложений в Delphi-подобном окружении.
IV. Описание программы
Программа разработана для работы с клиентами туристического агенства. Элементами списка являются клиенты. В программе осуществляются:
ü добавление нового элемента в список;
ü изменение выделенного в списке элемента;
ü удаление выделенного в списке элемента;
ü поиск элементов в списке по ключевым словам и критериям;
ü сохранение списка в файл;
ü загрузка списка из ранее сохраненного файла.
Главное окно
Главное меню представляет собой 3 вкладки: «Файл», «Правка», «Поиск». Во вкладке «Файл» мы имеем 3 функциональные кнопки, а именно - «Открыть», «Сохранить как», «Выход». Во вкладке «Правка» мы имеем 2 функциональные кнопки, а именно - «Добавить», «Удалить». Во вкладке «Поиск» мы имеем 1 функциональную кнопку, а именно - «Поиск по». Так же у нас есть прямоугольная область, в которой располагаются элементы списка.
Главное окно программы изображено на Рис. 2.
Рис.2. Главное окно
Кнопка «Добавить»
Кнопка «Добавить» отвечает за добавление нового элемента в список. При нажатии открывается окно добавления/изменения элемента (Рис.3.)
Рис.3. Кнопка «Добавить»
Важно: необходимо заполнить все поля в окне добавления/изменения элемента, иначе появится системное сообщение «Поле пусто» (Рис.4.)
Рис.4. Системное сообщение «Поле пусто»
После процедуры заполнения полей необходимо нажать кнопку «ОК», после чего окно добавления/изменения элемента закроется, и в главном окне программы в прямоугольной области списка появится новый элемент (элементы в списке отображаются только по параметру «ФИО», все остальные данные элемента хранятся в памяти). (Рис.5.)
Рис.5. Добавленные элементы
Чтобы закрыть окно добавления/изменения элемента, не добавляя новый элемент, необходимо нажать кнопку «Отмена».
Кнопка «Редактирование»
Двойной клик по нужному объекту в списке отвечает за изменение выделенного в списке элемента. При двойном нажатии открывается окно добавления/изменения элемента, в поля которого загружаются все данные этого элемента, записанные ранее. (Рис.6.)
В появившемся окне можно изменить данные в полях, далее следует нажать кнопку «ОК», после чего окно добавления/изменения элемента закроется, а все внесенные изменения сохранятся.
Чтобы закрыть окно добавления/изменения элемента, не изменяя данных элемента, необходимо нажать кнопку «Отмена».
Рис. 6. Кнопка «Изменить»
Кнопка «Удалить»
Кнопка «Удалить» отвечает за удаление выделенного в списке элемента. При нажатии выделенный элемент удаляется из списка. При этом стоящий за ним элемент перемещается на его место и получает его адрес. Таким образом, смещаются все последующие элементы списка.
Диалог сохранения файла
Диалог сохранения (Файл-Сохранить как) позволяет сохранить созданный список в файл. Процедура сохранения стандартная (Рис.7.)
Рис.7. Диалог сохранения файла
Важно: имя и путь сохранения файла должны быть исключительно на латинице.
Диалог открытия файла
Диалог открытия позволяет загрузить список из файла. Процедура загрузки файла стандартна (Рис.8.). Загруженный список из файла изображен на Рис.9.
Рис. 8. Диалог открытия файла
Рис. 9. Загруженный список
Кнопка «Поиск по»
Кнопка «Поиск по» отвечает за поиск элементов в списке. При нажатии открывается окно поиска элемента (Рис.10.)
Рис. 10. Окно поиска элемента
В появившемся окне нужно ввести в соответствующее поле ключевое слово или часть слова, выбрать критерий поиска в выпадающем списке (или выбрать в нем «Показать всё»).
Или, если необходим поиск по критериям “Транспорт”, ”Отели” выбрать нужное в списке.
Важно: необходимо сначала ввести ключевое слово или часть слова и только после этого задавать критерий. Для отображения всего списка вводить ключевое слово или его часть не нужно.
Следует заметить, что в окне поиска отображаются все данные, закрепленные за одним элементом, а не только «Наименование», как в главном окне.
Примеры результатов поиска по разным ключевым словам и параметрам изображены на Рис.11, 12 и 13.
Рис. 11. Результат поиска «Показать все»
Рис. 12. Результат поиска по ключевому слову «Ти» и параметру «ФИО»
Рис. 13. Результат поиска по ключевому слову «Россия» и параметру «Изготовитель»
V. Заключение
Двусвязный список состоит из элементов данных, каждый из которых содержит ссылки как на следующий, так и на предыдущий элементы.
Наличие двух ссылок вместо одной предоставляет несколько преимуществ. Вероятно, наиболее важное из них состоит в том, что перемещение по списку возможно в обоих направлениях. Это упрощает работу со списком, в частности, вставку и удаление. Помимо этого, пользователь может просматривать список в любом направлении. Еще одно преимущество имеет значение только при некоторых сбоях. Поскольку весь список можно пройти не только по прямым, но и по обратным ссылкам, то в случае, если какая-то из ссылок станет неверной, целостность списка можно восстановить по другой ссылке.
Целью выполнения лабораторной работы являлось получение практических навыков в работе с двунаправленными списками.
При выполнении работы была разработана программа, реализующая работу с динамическим двусвязным списком в среде разработки приложений Lazarus.
VI. Список используемой литературы
1. https://it.kgsu.ru/PasDin/dnpas035.html
2. https://saod.narod.ru/saod3/List003.html
3. https://programm.ws/page.php?id=600
4. https://lazarus.freepascal.org/
Приложение 1.
Unit 1.