Добро пожаловать в Forum.iCoder.Uz

Присоединяйтесь к нам сейчас, чтобы получить доступ ко всем нашим функциям. После регистрации и входа в систему вы сможете создавать темы, публиковать ответы на существующие темы, повышать репутацию других участников, получать собственный личный мессенджер и многое другое. Это также быстро и совершенно бесплатно, так чего же вы ждете?

C# Односвязные списки

Информация о теме

О теме Здравствуйте, вы читаете тему Односвязные списки созданную в в разделе Обучение C# пользователем Deimos#. Эта тема была просмотрена 1 598 раз(а), получила 1 комментариев и 2 очки реакции...
Название категории Обучение C#
Название темы Односвязные списки
Автор темы Deimos#
Дата начала
Ответы
Просмотры
Количество реакций к первому сообщению
Последнее сообщение Рома_Python_c#

Deimos#

Модератор #2
Регистрация
17.02.2016
Сообщения
116
Реакции
41
Баллы
35
Возраст
29
Линейные структуры данных

Линейные списки
Наиболее общей структурой является линейный список (АТД - Абстракный Тип Данных): последовательность элементов a[SUB]1[/SUB], a[SUB]2[/SUB], a[SUB]3[/SUB], ..., a[SUB]n[/SUB] где N >= 0.
Все элементы которой имеют один базовый тип. Количество элементов N называется длинной списка.
a[SUB]1[/SUB] - первый элемент списка, a[SUB]n[/SUB] - последний элемент списка.

Для формирования АТД нужно задать множество операций которые могут быть следующие:
  1. Создание пустого списка
  2. Вставка нового элемента в или после позиции P
  3. Удаление элемента в или после позиции P
  4. Получение доступа к элементу в позиции P для проверки или изменения.
  5. Переход к следующему или предыдущему элементу.



Это самые наиболее часто используемые операции но может потребоваться и другие операции со списком например как​
поиск элемента с заданным значением, либо операцию сортировки и так далее.
В линейный список будет трудно задать быстрый доступ к определенному элементу если нужно еще и вставить элемент в
произвольной позиции.

Для этого различаю разные типы линейных списков в зависимости от поставленной задачи.​
Достаточно простая реализация составляется из массива данных.

В этом случае используется последовательное распределение памяти, и все элементы списка хранятся в смежных ячейках​
к которым осуществляется эффективный прямой доступ (direct access).Но так же есть и недостатки этого способа.
Важно отметить что практическая реализация операций требует обязательной программной обработки возможных ошибок.

Например при вставке L.N = MaxLength следует предусмотреть ошибку переполнения памяти, при удалении​
элемента когда список пустой L.N = 0 - ошибку отсутствия элементов.
Легко заметить что реализация списка посредством массива позволяется легко организовать доступ к элементам,
но операции вставки и удаления выполняются крайне неэффективно, так как требуют большого числа сдвигов элементов,
за исключением случая когда обрабатывается последний элемент.

Вместо того что бы хранить элементы списка в ячейках лучше использовать более гибкую структуру - Связный список.
Который кроме элемента содержит так же указатель на следующий элемент списка. Такая реализация использует
связное распределение памяти, при котором к элементам списков позволяет эффективно организовать операции
вставки и удаления, пожертвовав для этого удобства дополнительной памятью для хранения указателей.

Для начала определим структуру нашего связного списка как элемент узла и указатель на следующий узел​
Так как мы будем делать уникальный список данных то я буду использовать абстрактный тип данных <T>
C#:
Пожалуйста, Вход или Регистрация to view codes content!
Основное соглашение которое должно быть учтено это то что последний узел должен ссылаться
либо на нулевой указатель - null
либо на первый элемент списка - что сделает список циклическим.

Жестких рекомендаций по реализации списка нету и в зависимости от задачи он может отличаться.

Использования фиктивных узлов позволяет легко решить задачу вставки и удаления элемента списка.
Циклический список необходим во многих прикладных приложениях.

Давайте реализуем список с нулевым указателем на последний элемент.
Структура будет следующей:
Создаем абстрактный класс списка и назовем его AbstractList<T>
fgvudgx7236336.png

И так же в нем реализуем все часто используемые методы
  • Поиск элемента по индексу
  • Поиск элемента по условию
  • Очистка списка
  • Вывод списка на экран пользователя
  • Поле возвращающее кол-во элементов в списке
idiiyrz2818037.png

Будем наследовать этот класс для всех типов связных списков так будет удобнее и меньше нужно будет
реализовывать повторяющегося кода для остальных наследуемых линейных списокв.
Что бы не возникло путаницы создайте в проекте новую папку и назовите ее Abstract
Там создадим наш класс AbstractList<T>
C#:
Пожалуйста, Вход или Регистрация to view codes content!
После того как мы создали наш абстракный класс.
Можно приступить к реализации односвязного списка.

В новом классе LinkedList<T> который будем наследовать от базового типа.
Добавим конструктор и 2 метода добавления и удаления узла а так же вывод всего списка на экран.
Конструктор нашего класса
C#:
Пожалуйста, Вход или Регистрация to view codes content!


Пожалуйста, Вход или Регистрация to view spoiler content!

Теперь определим метод удаления узла из списка

Пожалуйста, Вход или Регистрация to view spoiler content!


Пример использование списка
C#:
Пожалуйста, Вход или Регистрация to view codes content!

yirbpex8080387.png



На этом основные функции односвязного списка реализованы.
Полный листин списка можно посмотреть ниже


Пожалуйста, Вход или Регистрация to view spoiler content!

Пожалуйста, Вход или Регистрация to view spoiler content!

Пожалуйста, Вход или Регистрация to view spoiler content!

 
Последнее редактирование:

Рома_Python_c#

Пользователь
Регистрация
06.11.2020
Сообщения
1
Реакции
0
Баллы
1
Возраст
19
Можете пожалуйста кинуть уже полностью готовый , если не сложно
 
shape1
shape2
shape3
shape4
shape7
shape8
Сверху Снизу