Реклама


Онлайн редактор HTML/CSS/JS кода- (КЛИК). Подробно - (Тут) | Онлайн COLOR PICKER - (КЛИК).
Инструменты для программиста - (КЛИК). | Pastebin - (КЛИК). | Лента - (КЛИК). | BB-коды - (КЛИК).
iCoder.Uz  iCoder.Uz

Общая репутация темы

+1
Показано с 1 по 1 из 1

Тема: Односвязные списки

  1. ID сообщения 20295 #1
    Профи
    Оффлайн

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

    Линейные структуры данных

    Линейные списки
    Наиболее общей структурой является линейный список (АТД - Абстракный Тип Данных): последовательность элементов a1, a2, a3, ..., an где N >= 0.
    Все элементы которой имеют один базовый тип. Количество элементов N называется длинной списка.
    a1 - первый элемент списка, an - последний элемент списка.

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




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

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

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

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

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

    Для начала определим структуру нашего связного списка как элемент узла и указатель на следующий узел
    Так как мы будем делать уникальный список данных то я буду использовать абстрактный тип данных
    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "XCODE" BBкода...

    Основное соглашение которое должно быть учтено это то что последний узел должен ссылаться
    либо на нулевой указатель - null
    либо на первый элемент списка - что сделает список циклическим.

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

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

    Давайте реализуем список с нулевым указателем на последний элемент.
    Структура будет следующей:
    Создаем абстрактный класс списка и назовем его AbstractList
    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "IMG" BBкода...

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

    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "IMG" BBкода...

    Будем наследовать этот класс для всех типов связных списков так будет удобнее и меньше нужно будет
    реализовывать повторяющегося кода для остальных наследуемых линейных списокв.
    Что бы не возникло путаницы создайте в проекте новую папку и назовите ее Abstract
    Там создадим наш класс AbstractList
    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "XCODE" BBкода...

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

    В новом классе LinkedList который будем наследовать от базового типа.
    Добавим конструктор и 2 метода добавления и удаления узла а так же вывод всего списка на экран.
    Конструктор нашего класса
    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "XCODE" BBкода...



    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "XCODE" BBкода...

    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "IMG" BBкода...



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

    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "XCODE" BBкода...

    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "IMG" BBкода...




    Пример использование списка
    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "XCODE" BBкода...


    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "IMG" BBкода...



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


    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "XCODE" BBкода...



    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "XCODE" BBкода...



    Пожалуйста, войдите или пройдите Регистрацию чтобы увидеть содержимое "XCODE" BBкода...


    Поблагодарили:

    Последний раз редактировалось Deimos#; 22.07.19 в 12:23.

Метки этой темы

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •  
12+