Jump to content

Список (абстрактный тип данных)

(Перенаправлено из типа списка )

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

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

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

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

Многие языки программирования обеспечивают поддержку типов данных списков и имеют специальный синтаксис и семантику для списков и операций со списками. Список часто можно составить, записывая элементы последовательно, разделяя их запятыми , точками с запятой и/или пробелами , внутри пары разделителей, таких как круглые скобки «()», квадратные скобки «[]», фигурные скобки «{}» или угловые скобки '<>'. Некоторые языки могут позволять индексировать или нарезать типы списков, как типы массивов , и в этом случае тип данных более точно описывается как массив.

В теории типов и функциональном программировании абстрактные списки обычно определяются индуктивно с помощью двух операций: nil , которая создает пустой список, и cons , которая добавляет элемент в начало списка. [1]

Поток это потенциально бесконечный аналог списка. [2] : §3.5 

Операции

[ редактировать ]

Реализация структуры данных списка может обеспечивать некоторые из следующих операций :

  • создавать
  • тест на пустой
  • добавить элемент в начало или конец
  • доступ к первому или последнему элементу
  • доступ к элементу по индексу

Реализации

[ редактировать ]

Списки обычно реализуются либо как связанные списки (одно- или двусвязные), либо как массивы , обычно переменной длины или динамические массивы .

Стандартный способ реализации списков, берущий свое начало в языке программирования Lisp , заключается в том, чтобы каждый элемент списка содержал как свое значение, так и указатель, указывающий расположение следующего элемента в списке. В результате получается связанный список или дерево , в зависимости от того, есть ли в списке вложенные подсписки. Некоторые старые реализации Lisp (например, реализация Lisp символики 3600 ) также поддерживали «сжатые списки» (с использованием кодирования CDR ), которые имели специальное внутреннее представление (невидимое для пользователя). Списками можно манипулировать с помощью итерации или рекурсии . Первое часто предпочтительнее в императивных языках программирования , тогда как второе является нормой в функциональных языках .

Списки могут быть реализованы как самобалансирующиеся двоичные деревья поиска , содержащие пары индекс-значение, обеспечивающие равновременный доступ к любому элементу (например, всем, находящимся на периферии, и внутренним узлам, хранящим индекс самого правого дочернего элемента, используемый для управления поиском). , принимая время логарифмическим по размеру списка, но до тех пор, пока оно не сильно изменится, это создаст иллюзию произвольного доступа и позволит выполнять операции замены, префикса и добавления также в логарифмическом времени. [3]

Поддержка языков программирования

[ редактировать ]

Некоторые языки не предлагают структуру данных списка , но предлагают использование ассоциативных массивов или каких-либо таблиц для эмуляции списков. Например, Lua предоставляет таблицы. Хотя Lua хранит внутри себя списки с числовыми индексами в виде массивов, они по-прежнему выглядят как словари. [4]

В Lisp списки являются основным типом данных и могут представлять как программный код, так и данные. В большинстве диалектов список первых трех простых чисел можно записать как (list 2 3 5). В нескольких диалектах Lisp, включая Scheme , список представляет собой набор пар, состоящий из значения и указателя на следующую пару (или нулевое значение), образующий односвязный список. [5]

Приложения

[ редактировать ]

В отличие от массива , список может расширяться и сжиматься.

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

Списки также составляют основу для других абстрактных типов данных, включая очередь , стек и их варианты.

Абстрактное определение

[ редактировать ]

Тип абстрактного списка L с элементами некоторого типа E ( мономорфный список) определяется следующими функциями:

ноль: () → L
минусы: E × L L
сначала: Л Е
остальное: Л Л

с аксиомами

первый (cons ( e , l )) = e
отдых (cons( e , l )) = l

для любого элемента e и любого списка l . Подразумевается, что

минусы ( е , л ) ≠ л
минусы ( е , л ) ≠ е
минусы ( е 1 , л 1 ) = минусы ( е 2 , л 2 ), если е 1 знак равно е 2 и л 1 = л 2

Обратите внимание, что first (nil())) и rest (nil()) не определены.

Эти аксиомы эквивалентны аксиомам абстрактного типа данных стека .

В теории типов приведенное выше определение проще рассматривать как индуктивный тип, определенный в терминах конструкторов: nil и cons . можно представить как преобразование 1 + E × L L. В алгебраических терминах это first и rest затем получаются путем сопоставления с образцом в конструкторе cons и отдельной обработки нулевого случая.

Монада списка

[ редактировать ]

Тип списка образует монаду со следующими функциями (с использованием E * вместо L для представления мономорфных списков с элементами типа E ):

где добавление определяется как:

Альтернативно, монада может быть определена с помощью операций return , fmap и join , с помощью:

что fmap , join , append иbind Обратите внимание , четко определены, поскольку они применяются к все более глубоким аргументам при каждом рекурсивном вызове.

Тип списка — аддитивная монада, где nil — монадический ноль, а add — монадическая сумма.

Списки образуют моноид при операции добавления . Идентификационным элементом моноида является пустой список nil . По сути, это свободный моноид над множеством элементов списка.

См. также

[ редактировать ]
  • Тип данных массива — тип данных, представляющий упорядоченный набор элементов (значений или переменных).
  • Очередь – абстрактный тип данных
  • Set — абстрактный тип данных для хранения уникальных значений.
  • Стек — абстрактный тип данных.
  • Поток — последовательность элементов данных, доступных с течением времени.
  1. ^ Рейнгольд, Эдвард; Нивергельт, Юрг; Нарсингх, Део (1977). Комбинаторные алгоритмы: теория и практика . Энглвуд Клиффс, Нью-Джерси: Прентис Холл. стр. 38–41. ISBN  0-13-152447-Х .
  2. ^ Абельсон, Гарольд; Сассман, Джеральд Джей (1996). Структура и интерпретация компьютерных программ . МТИ Пресс.
  3. ^ Барнетт, Гранвилл; Дель Тонга, Лука (2008). «Структуры данных и алгоритмы» (PDF) . mta.ca. ​Проверено 12 ноября 2014 г.
  4. ^ Лерусалимский, Роберто (декабрь 2003 г.). Программирование на Lua (первое издание) (Первое изд.). Луа.орг. ISBN  8590379817 . Проверено 12 ноября 2014 г.
  5. ^ Стил, Гай (1990). Common Lisp (Второе изд.). Цифровая пресса. стр. 29–31. ISBN  1-55558-041-6 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 7df5eafd9476e5d50dd5f030a4c5ddef__1722677700
URL1:https://arc.ask3.ru/arc/aa/7d/ef/7df5eafd9476e5d50dd5f030a4c5ddef.html
Заголовок, (Title) документа по адресу, URL1:
List (abstract data type) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)