Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Списки в программировании

Список

Связный список (англ. List) — структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.

Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.

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

XOR-связный список [ править ]

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

Первый элемент является следующим для последнего элемента списка.

Рассмотрим базовые операции на примере односвязного списка.

Вставка [ править ]

Очевиден случай, когда необходимо добавить элемент ( [math]newHead[/math] ) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

Поиск [ править ]

Для того, чтобы найти элемент по значению ( [math]value[/math] ), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем [math]NULL[/math] .

Удаление [ править ]

Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.

Удаление элемента после заданного ( [math]thisElement[/math] ) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.

Для начала необходимо уметь определять — список циклический или нет. Воспользуемся алгоритмом Флойда «Черепаха и заяц». Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.

Если цикла не существует, то заяц первым дойдет до конца и функция возвратит [math]false[/math] . В другом случае, в тот момент, когда и черепаха и заяц находятся в цикле, расстояние между ними будет сокращаться на [math]1[/math] , что гарантирует их встречу за конечное время.

Так как для поиска хвоста мы должны знать, что цикл существует, воспользуемся предыдущей функцией и при выходе из неё запомним «момент встречи» зайца и черепахи. Назовем её [math]pointMeeting[/math] .

Наивные реализации [ править ]

Реализация за [math]O(n^2)[/math] [ править ]

Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от [math]pointMeeting[/math] вперёд указатель. Если он окажется в текущем элементе, прежде чем посетит [math]pointMeeting[/math] снова, то точку окончания (начала) хвоста нашли.

Реализация за [math]O(n log n)[/math] [ править ]

Реализацию, приведенную выше можно улучшить. Для этого воспользуемся бинарным поиском. Сначала проверим голову списка, потом сделаем [math] 2 [/math] шага вперёд, потом [math] 4 [/math] , потом [math] 8 [/math] и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции — на левой границе, где мы в хвосте, и на правой — в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за [math]O(n log n)[/math] .

Эффективная реализация [ править ]

Возможны два варианта цикла в списке. Первый вариант — сам список циклический (указатель [math]next[/math] последнего элемента равен первому), а второй вариант — цикл внутри списка (указатель [math]next[/math] последнего элемента равен любому другому (не первому)). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Достаточно запустить один указатель из [math]pointMeeting[/math] , а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла. Сложность алгоритма — [math]O(n)[/math] . Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.

Доказательство корректности алгоритма [ править ]

Рассмотрим цикл длиной [math]N[/math] с хвостом длины [math]L[/math] . Напишем функции для обоих указателей в зависимости от шага [math]n[/math] . Очевидно, что встреча не может произойти при [math]n leqslant L[/math] , так как в этом случае [math]2ngt n[/math] для любого [math]ngt 0[/math] . Тогда положения указателей зададутся следующими функциями (при [math]ngt L[/math] ):

[math]f_1(n) = L + (n-L) bmod N[/math]

[math]f_2(n) = L + (2n-L) bmod N[/math]

Приравнивая, получим [math]n bmod N = 0[/math] , или [math]n = k N, n gt L[/math] . Пусть [math]H[/math] — голова списка, [math]X[/math] — точка встречи, [math]A[/math] — первый элемент цикла, [math]Q[/math] — расстояние от [math]X[/math] до [math]A[/math] . Тогда в точку [math]A[/math] можно прийти двумя путями: из [math]H[/math] в [math]A[/math] длиной [math]L[/math] и из [math]H[/math] через [math]X[/math] в [math]A[/math] длиной [math]L + N = X + Q[/math] , то есть:

[math]Q = L + N — X[/math] , но так как [math]X = kN[/math]

[math]Q = L + (1-k) N[/math]

Пусть [math]L = p N + M, 0 leqslant M lt N[/math]

[math]L lt k N leqslant L + N[/math]

[math]pN + M lt kN leqslant (p+1)N + M[/math] откуда [math]k = p + 1[/math]

Подставив полученные значения, получим: [math]Q = pN + M + (1 — p — 1)N = M = L bmod N[/math] , откуда следует, что если запустить указатели с одной скоростью из [math]H[/math] и [math]X[/math] , то они встретятся через [math]L[/math] шагов в точке [math]A[/math] . К этому времени вышедший из [math]H[/math] пройдёт ровно [math]L[/math] шагов и остановится в [math]A[/math] , вышедший из [math]X[/math] накрутит по циклу [math][L/N][/math] шагов и пройдёт ещё [math]Q = L bmod N[/math] шагов. Поскольку [math]L = [L/N] + L bmod N[/math] , то они встретятся как раз в точке [math]A[/math] .

Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий. Эта рекурсивная функция принимает указатель на голову списка и предыдущий элемент (при запуске указывать [math]NULL[/math] ), а возвращает указатель на новую голову списка.

Алгоритм корректен, поскольку значения элементов в списке не изменяются, а все указатели [math]next[/math] изменят свое направление, не нарушив связности самого списка.

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

Введение. Основные операции

О дносвязный список – структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL.

Для нас односвязный список полезен тем, что

  • 1) Он очень просто устроен и все алгоритмы интуитивно понятны
  • 2) Односвязный список – хорошее упражнение для работы с указателями
  • 3) Его очень просто визаулизировать, это позволяет «в картинках» объяснить алгоритм
  • 4) Несмотря на свою простоту, односвязные списки часто используются в программировании, так что это не пустое упражнение.
  • 5) Эта структуру данных можно определить рекурсивно, и она часто используется в рекурсивных алгоритмах.
Читать еще:  Операторы программирования паскаль

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

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

Чтобы не писать каждый раз struct мы определили новый тип.
Теперь наша задача написать функцию, которая бы собирала список из значений, которые мы ей передаём. Стандартное имя функции – push, она должна получать в качестве аргумента значение, которое вставит в список. Новое значение будет вставляться в начало списка. Каждый новый элемент списка мы должны создавать на куче. Следовательно, нам будет удобно иметь один указатель на первый элемент списка.

Вначале списка нет и указатель ссылается на NULL.
Для добавления нового узла необходимо

  • 1) Выделить под него память.
  • 2) Задать ему значение
  • 3) Сделать так, чтобы он ссылался на предыдущий элемент (или на NULL, если его не было)
  • 4) Перекинуть указатель head на новый узел.

1) Создаём новый узел

2) Присваиваем ему значение

3) Присваиваем указателю tmp адрес предыдущего узла

4) Присваиваем указателю head адрес нового узла

5) После выхода из функции переменная tmp будет уничтожена. Получим список, в который будет вставлен новый элемент.

Так как указатель head изменяется, то необходимо передавать указатель на указатель.

Теперь напишем функцию pop: она удаляет элемент, на который указывает head и возвращает его значение.

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

Уже после этого можно удалить первый элемент и вернуть его значение

Не забываем, что необходимо проверить на NULL голову.

Таким образом, мы реализовали две операции push и pop, которые позволяют теперь использовать односвязный список как стек. Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.

Для дальнейшего разговора необходимо реализовать функции getLast, которая возвращает указатель на последний элемент списка, и nth, которая возвращает указатель на n-й элемент списка.

Так как мы знаем адрес только первого элемента, то единственным способом добраться до n-го будет последовательный перебор всех элементов списка. Для того, чтобы получить следующий элемент, нужно перейти к нему через указатель next текущего узла

Переходя на следующий элемент не забываем проверять, существует ли он. Вполне возможно, что был указан номер, который больше размера списка. Функция вернёт в таком случае NULL. Сложность операции O(n), и это одна из проблем односвязного списка.

Для нахождение последнего элемента будем передирать друг за другом элементы до тех пор, пока указатель next одного из элементов не станет равным NULL

Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.

Для вставки нового элемента в конец сначала получаем указатель на последний элемент, затем создаём новый элемент, присваиваем ему значение и перекидываем указатель next старого элемента на новый

Односвязный список хранит адрес только следующего элемента. Если мы хотим удалить последний элемент, то необходимо изменить указатель next предпоследнего элемента. Для этого нам понадобится функция getLastButOne, возвращающая указатель на предпоследний элемент.

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

Удаление последнего элемента и вставка в конец имеют сложность O(n).

Можно написать алгоритм проще. Будем использовать два указателя. Один – текущий узел, второй – предыдущий. Тогда можно обойтись без вызова функции getLastButOne:

Теперь напишем функцию insert, которая вставляет на n-е место новое значение. Для вставки, сначала нужно будет пройти до нужного узла, потом создать новый элемент и поменять указатели. Если мы вставляем в конец, то указатель next нового узла будет указывать на NULL, иначе на следующий элемент

Покажем на рисунке последовательность действий

После этого делаем так, чтобы новый элемент ссылался на следующий после n-го

Программирование линейных списков

технические науки

  • Хусаинов Исмагильян Гарифьянович , доктор наук, доцент, профессор
  • Башкирский государственный университет, Стерлитамакский филиал
  • Похожие материалы

    С++ — один из самых распространенных языков программирования [1, 2]. Он широко используется студентами при выполнении выпускных квалификационных и курсовых работ. С++ с успехом применяется при выполнении численных расчетов по научным задачам [3, 4].

    Любая программа для компьютера предназначена для обработки данных. Данные бывают статические и динамические. В статье рассматривает создание односвязного списка, добавление, удаление, поиск элемента по ключу. Приведенные в работе программы протестированы в среде Borland C++ 5.02. Программы предназначены для начинающих программистов студентов и школьников. Они могут быть использованы при выполнении лабораторных, контрольных и курсовых работ.

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

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

    Независимо от вида элемент динамической структуры данных должен иметь минимум два поля: одно поле для хранения данных, а другое для хранения указателя. Как полей для данных, так и полей для указателей может быть несколько. Поле данных может иметь любой основной или составной тип, а также может быть указателем. Рассмотрим описание типа простого элемента динамической структуры данных. Общий вид:

    Первое поле структуры — поле данных, а второе поле — указатель.

    Пример описания элемента динамической структуры данных, хранящей фамилию, имя, отчество и год рождения.

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

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

    Над односвязнымb списками можно выполнять следующие операции:

    • начальное формирование списка (создание первого элемента);
    • добавление элемента в конец списка;
    • чтение элемента с заданным ключом;
    • вставка элемента в заданное место списка (до или после элемента с заданным ключом);
    • удаление элемента с заданным ключом;
    • упорядочивание списка по ключу.

    Рассмотрим каждую операцию отдельно на примере создания динамической структуры данных для хранения списка группы студентов (ф.и.о., дата рождения (день, месяц, год)).

    Начальное формирование списка.

    Добавление элемента в конец списка.

    Чтение элемента с заданным ключом.

    Пусть ключом является год рождения.

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

    Сортировка связанного списка по ключу заключается только в изменении связей между элементами.

    Список литературы

    1. Подбельский В.В. Язык С++: Учебное пособие – 5 изд. – М: Финансы и статистика, 2004. – 560 c.
    2. Шилдт Г. С++: базовый курс. 3-е издание. – М.: Издательский дом «Вильямс». 2010. – 624 с.
    3. Хусаинов И.Г. Тепловые процессы при акустическом воздействии на насыщенную жидкостью пористую среду // Вестник Башкирского университета. 2013. Т. 18. № 2. С. 350-353.
    4. Хусаинова Г.Я. Нестационарная фильтрация вязкопластичной жидкости в пласте // Автоматизация. Современные технологии. 2018. Т. 72. № 4. – С. 147-149.

    Электронное периодическое издание зарегистрировано в Федеральной службе по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор), свидетельство о регистрации СМИ — ЭЛ № ФС77-41429 от 23.07.2010 г.

    Соучредители СМИ: Долганов А.А., Майоров Е.В.

    Реализация связных списков на С++

    Более подробно про структуры данных и алгоритмы, используемые статье можно прочитать тут:

    Однонаправленный связанный список. Очередь

    В данной своей статье я хотел бы рассмотреть такую интересную структуру данных, как связанный список или как его еще называют динамический список. Связный список — это динамическая структура данных, состоящая из узлов, которые содержат в себе в классическом варианте два значения: первое — это какое-либо данное (этим данным может быть что угодно: обычная переменная, объект класса и так далее), а второе — это указатель на следующий узел в списке (не зря же список является связанным).

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

    На рисунке мы видим узлы, содержащие в себе два значения — данное и указатель. Указатель всегда указывает (содержит в себе адрес памяти) на следующий узел связанного списка. И самое важное — это то, что указатель последнего узла должен всегда выставляться в нуль (NULL, nullptr или просто 0). Этим он сообщает что является последним узлом связанного списка и что дальше указывать не на что. Если нужно будет добавить новый узел в динамический список, то это значение NULL заменяется на адрес нахождения в памяти нового узла (как это делается мы рассмотрим ниже), а сам же указатель нового узла опять выставляется в NULL. По ходу работы программы мы можем сколь угодно создавать таких узлов нашего связанного списка, единственное ограничение накладывает размер свободной оперативной памяти компьютера (ее конечно же должно хватать). Логически мы видим, что все узлы расположены как бы по порядку, хотя на самом деле в памяти компьютера они могут располагаться где угодно. И найти его не составит никакого труда, т.к. у нас есть в узле поле-указатель, указывающий на нужную ячейку памяти.

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

    А теперь нужно создать сам объект «связанный список», который и будет хранить эти самоссылающиеся узлы (Node — с англ. узел). Вот как мы это сделаем

    Итак, если с первой структурой Node все понятно, то со структурой List , представляющей «связанный список» нам нужно сейчас разобраться. Мы выяснили, что динамический список состоит из узлов, значит класс List должен манипулировать этими узлами: создавать их, удалять, выводить на печать и так далее. Пока что остановимся только на таких моментах как создавать и выводить на печать, удаление оставим на потом. Как видите, в нашем классе List имеются два метода: addNode() — создает новый узел в динамическом списке, printList() — выводит содержание списка (всех узлов поочереди) на печать. Также у нас есть закрытое поле класса head типа Node — это так называемая «голова» связанного списка и судя из названия должна всегда указывать на начало списка в памяти компьютера, т.е. на его первый узел (этот момент мы не обсуждали выше, но он логически понятен — должен же быть указатель, указывающий просто на начало динамического списка и не содержащий никаких данных). Зная, где начинается связанный список, на него нам указывает «голова» head , и где заканчивается, об этом нам сообщает указатель последнего узла, выставленный в NULL , мы можем путешествовать по всему динамическому списку и произодить с них необходимые операции.

    Изначально в конструкторе класса List переменной head выставляется значение в NULL , т.к. при создании объекта класса List связанный список еще пуст и узлов в нем нет, соответственно и указывать не на что. Складываем все вышеупомянутое и получаем рабочую программу, реализующую динамический список.

    Результат работы программы будет выглядеть так:

    Думаю, что метод, добавляющий новый узел в список ( addNode ) нужно рассмотреть подробнее — не всем и все здесь будет понятно сразу же:

    Итак, первая строка кода

    Node *nd = new Node;

    динамически (new) создает новый объект типа Node , т.е. новый узел. Как вы знаете, после отработки данной строки, в указатель nd , при успешном создании объекта, записывается адрес созданного объекта в памяти (в неудачном случае будет записано NULL , т.е. объект не создан). Идем дальше…

    В этих двух строках кода мы уже обращаемся к полям созданного узла и присваиваем им необходимые значения: задаем данное — это данное метод addNode() принимает в качестве аргумента, выставляем указатель в NULL , т.к. вновь созданный узел всегда у нас будет последним (в данном варианте программы узлы добавляются в конец связанного списка — классический вариант). Далее…

    Следующая конструкция выбора служит для определения: создается первый узел в списке или он уже не первый. В случае, если создается только первый узел, то head будет в NULL и выполнится условие после if , т.е. head присвоится адрес первого узла в памяти. В последующих случаях, когда создаются 2, 3, 4, 5, . узлы будет срабатывать блок после else . Его рассмотрим подробнее…

    Создаем вспомагательную переменную типа Node и присваиваем ей указатель на начало списка. Далее в цикле мы последовательно проходимся по нашему связанному списку, пока не дойдем до узла, который был создан последним прошлый раз и присваиваем его указателю адрес нашего вновь созданного узла. Описанный процесс показан на рисунке:

    Однонаправленный связнный список. Стек

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

    Рассмотрев код программы, видим, что изменился метод добавления нового узла в список. Теперь новый узел как бы вклинивается между «головой» списка и следующим после нее узлом. Соответственно, в результатах работы мы видим в какой последовательности выводятся значения, находящиеся в узлах. Если вам подходит такой вариант обратного вывода, то можете использовать этот код.

    Двунаправленный связанный список. Дек

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

    Связные списки

    Связный список является простейшим типом данных динамической структуры, состоящей из элементов ( узлов ). Каждый узел включает в себя в классическом варианте два поля:

    • данные (в качестве данных может выступать переменная, объект класса или структуры и т. д.)
    • указатель на следующий узел в списке.

    Элементы связанного списка можно помещать и исключать произвольным образом.

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

    Классификация списков

    По количеству полей указателей различают однонаправленный (односвязный) и двунаправленный (двусвязный) списки.

    Связный список, содержащий только один указатель на следующий элемент, называется односвязным .
    Связный список, содержащий два поля указателя – на следующий элемент и на предыдущий, называется двусвязным .

    По способу связи элементов различают линейные и циклические списки.

    Связный список, в котором, последний элемент указывает на NULL , называется линейным .
    Связный список, в котором последний элемент связан с первым, называется циклическим .

    Виды списков

    Таким образом, различают 4 основных вида списков.

      Односвязный линейный список (ОЛС).
      Каждый узел ОЛС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).

  • Односвязный циклический список (ОЦС).
    Каждый узел ОЦС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит адрес первого узла (корня списка).
  • Двусвязный линейный список (ДЛС).
    Каждый узел ДЛС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит нулевое значение (указывает на NULL). Поле указателя на предыдущий узел первого узла (корня списка) также содержит нулевое значение (указывает на NULL).
  • Двусвязный циклический список (ДЦС).
    Каждый узел ДЦС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит адрес первого узла (корня списка). Поле указателя на предыдущий узел первого узла (корня списка) содержит адрес последнего узла.
Ссылка на основную публикацию
Adblock
detector