Реализация структуры списков
Автор: andrewLpL • Декабрь 5, 2021 • Практическая работа • 5,305 Слов (22 Страниц) • 232 Просмотры
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования
«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)
Кафедра комплексной информационной безопасности электронно-вычислительных систем (КИБЭВС)
СПИСКИ
Отчет по практической работе №3 по дисциплине «Структуры данных»
Томск 2021
Оглавление
1 Введение 3
2 Ход работы 4
2.1 Реализация узла 4
2.2 Описание списка 4
2.3 Реализация списка 5
2.4 Тестирование 12
3 Заключение 16
Приложение А 17
1 Введение
Целью данной практической работы является получение навыков реализации структуры списков. Для данной работы будет использоваться язык программирования C#.
Задание: Реализовать динамический список при помощи двух классов. Реализовать интерфейсную часть - методы:
- инициализация пустого списка;
- добавление элементов списка в конец;
- удаление заданного элемента из списка;
- очистка списка;
- поиск элемента списка.
Реализуемый список должен быть циклическим. Два упорядоченных динамических списка объединить в один упорядоченный - реализовать в виде метода. Реализовать сортировку элементов списка в виде метода.
2 Ход работы
2.1 Реализация узла
Для реализации структуры списка создается вспомогательный класс узла – Node. В качестве атрибутов класса используется переменная типа int – data, которая хранит значение узла, и объект класса Node – next, который хранит объект следующего узла. Реализация класса Node на языке C# представлена на рисунке 1.
[pic 1]
Рисунок 1 - Реализация класса Node
2.2 Описание списка
Структура список реализуется с помощью класса List. Класс List включает в себя следующие атрибуты:
- начальный узел – begin типа Node;
- размер массива – size типа int.
Также класс List имеет ряд методов. Их описание представлено в таблице 1.
Таблица 1 - Описание методов.
Название метода | Описание |
List() | Конструктор класса, создающий пустой список |
List(int value) | Конструктор, создающий один узел со значением value |
bool add(int value) | Метод добавляющий в конец списка новый узел со значением value. В случае успешного добавления возвращает true, иначе false |
bool remove_elem(int value) | Удаление всех узлов, которые хранят значение равное value В случае успешного удаления возвращает true, иначе false |
int get_index(int value) | Возвращает индекс первого элемента, который совпал со значением value |
Node index(int index) | Возвращает значение узла, находящегося на i-ом месте |
void BubbleSort() | Сортировка списка по возрастанию |
void connect(List list) | Соединение списка с другим списком list |
void clear() | Очистка всего списка |
2.3 Реализация списка
В циклическом списке каждый узел знает местонахождения следующего, причем следующем элементом конечного узла является первый узел.
Класс List предусматривает два случая создания списка, создание пустого списка, создание списка с одним узлом – begin, значением котороего будет передано в конструктор, при инициализации.
В первом случае размер списка будет равен нулю, т.е. size = 0 и узел begin = null, так как список пустой. Реализация конструктора, создающего пустой список, представлена на рисунке 2.
[pic 2]
Рисунок 2 - Реализация конструктора без входных параметров
Во втором случае размер списка равен одному, и так как список циклический, то первый узел begin будет указывать на себя, как на следующего. Реализация конструктора, создающего список с одним узлом, представлена на рисунке 3.
...