• Инструменты для разработчика

    • Самые удобные инстременты для разработчика, которые облегчат жизнь любого как начинающего так и продвинутого разработчика.
    • Украшатели, уменьшители, конвертеры кодов.
    • Доменные инструменты.
    • Всё в одном комплекте.
  • Использование BB кодов. Тут указаны существующие BB коды на форуме.

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

Deimos#

Модератор #2
Регистрация
17.02.2016
Сообщения
116
Репутация
41
Баллы
28
Награды
0
Возраст
27
Адрес
Россия
Лучшие ответы
0
Линейные структуры данных

Линейные списки
Наиболее общей структурой является линейный список (АТД - Абстракный Тип Данных): последовательность элементов 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#:
Пожалуйста, Войти или Регистрация для просмотра содержания кодов!
Основное соглашение которое должно быть учтено это то что последний узел должен ссылаться
либо на нулевой указатель - null
либо на первый элемент списка - что сделает список циклическим.

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

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

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

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

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

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

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


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



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

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

 
Последнее редактирование:
Сверху Снизу