sd_3
.pdfМинистерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ(ТУСУР)
Кафедра безопасности информационных систем(БИС)
СПИСКИ
Отчет по практической работе №3 по дисциплине «Структура данных»
Выполнил
Студент гр. 730-2
Подойницын
К.В. 23.09.2021
Принял
Инженер кафедры КИБЭВС
Уразаев Д.Р.
23.09.2021
Томск 2021
2
|
|
Оглавление |
1 |
Введение ............................................................................................................ |
3 |
2 |
Основная часть .................................................................................................. |
4 |
Заключение .............................................................................................................. |
9 |
|
Приложение А........................................................................................................ |
10 |
3
1 Введение Цель работы: овладеть навыками реализации списка и разработки
алгоритмов взаимодействия с ним на языке программирования C#.
Задание:
Реализовать динамический список при помощи двух классов. Класс Node -отвечает за узел элемента списка, класс List - за работу со списком.
Реализовать интерфейсную часть - методы:
1.Инициализация пустого списка
2.Добавление элементов списка в конец
3.Удаление заданного элемента из списка
4.Очистка списка
5.Поиск элемента списка по образцу
Вариант 8. Реализуемый список должен быть циклическим. Два
упорядоченных динамических списка объединить в один упорядоченный -
реализовать в виде метода. Реализовать сортировку элементов списка в виде
метода.
4
2 Основная часть Связный список — базовая динамическая структура данных,
состоящая из узлов, каждый из которых содержит как данные, так и ссылку на следующий узел списка.
Листинг программы представлен в Приложении А.
При инициализации класса List задаются его свойства first и last равные null, а также счетчик количества элементов count=0.
При добавлении нового элемента в список выполняется проверка на наличие первого элемента, если его нет, выполняется присвоение первому элементу значения first и last, т.к. список циклический (Рисунок 2.1), счетчик count увеличивается на 1.
Рисунок 2.1 – Добавление нового элемента в список
5
При очистке списка элементы first и last приравниваются к null, а также счетчик элементов count становится равным нулю.
При удалении проверяется положение элемента в списке, а после ссылка на этот элемент переносится на следующий, счетчик count
уменьшается на 1. Если элемент был один, то происходит тоже что и при отчистке (Рисунок 2.2).
Рисунок 2.2 – Удаление элемента из списка
6
2.1 Метод слияния и сортировки двух списков
При слиянии двух списков на вход метода (Sum) подаются оба списка,
после чего ко второму добавляются элементы первого , после этого все элементы второго списка подаются в массив f. Далее применяется сортировка Шелла к массиву f. Затем происходит отчистка List_2, в итоге отсортированный массив последовательно добавляется в список.
Рисунок 2.3 – Метод Sum
Рисунок 2.4 – Метод Sort
7
2.2 Блок-схема метода Блок-схемы представлены на рисунках 2.5-2.6
Рисунок 2.5 –Блок-схема метода
Sum
8
Рисунок 2.6 –Блок-схема метода Sort
9
Заключение В результате практической работы был написан алгоритм реализации
циклического списка, написан метод по объединению и сортировке списка.
10
Приложение А (обязательное)
Листинг программы реализации списка
using System.Collections; using System;
using System.Collections.Generic; using sd3;
namespace sd3
{
public class Node<T>
{
public Node(T data)
{
Data = data;
}
public T Data { get; set; }
public Node<T> Next { get; set; }
}
public class LinkedList<T> : IEnumerable<T>
{
Node<T> first; Node<T> last; int count;
public void Add(T data)
{
Node<T> node = new Node<T>(data);
// если список пуст if (first == null)
{
first = node; last = node; last.Next = first;
}
else
{
node.Next = first; last.Next = node; last = node;
}
count++;
}
public bool Remove(T data)
{
Node<T> current = first; Node<T> previous = null;
if (IsEmpty) return false;
do
{
if (current.Data.Equals(data))
{