Внешняя память компьютера

     Массив  лучше всего вообразить как гусеницу или поезд с лапками-запятыми вместо колёс. Ползёт он всегда влево, на левом же конце его локомотив  — первый элемент. Первый потому, что  элементы упорядочены. Если знаете порядковый номер элемента, то легко получить его значение:

     array[1] #=> "Як-цуп-цоп, парви каридулла"

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

     array[0] #=> "Этот массив пойдёт в переменную array"

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

     [править]Строки

     Стро́ки — это ряды букв и других символов. В Ruby стро́ки используют наработки языка Perl. Вот небольшой список их возможностей:

     Нет ограничений. Длина строки́ может  достигать поистине фантастических размеров.

     Динамичность. Стро́ки можно расширять или уменьшать (для этого есть методы + и []).

     Любой объект преобразуется в строку (методы .inspect и .to_s есть у любого объекта).

     Строка  обладает обширной библиотекой методов, которые работают с правилами (это  методы .gsub, .match, .scan, .split). Можно вставлять произвольный код на языке Ruby в строку. После выполнения код заместится результатом.

     Стро́ки начинаются и заканчиваются " (программистскими кавычками) или ' (машинописным апострофом). Пример:

     "мама  мыла раму" # строка в кавычках

     'рама  сопротивлялась' # строка в апострофах

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

     [править]Ассоциативные массивы

     Ассоциативные массивы подобны массивам упорядоченных  пар. Работают они подобно словарям: фигурная скобка символизирует боковой  вид на открытую книгу, а стрелка => покажет читателю связь каждой сущности с какой-то другой. Вторая фигурная скобка говорит, что пора закрывать книгу.

     array = {"мама"=>"мыла раму", 807=>"Это число улыбается!"}

     Но  можно и без фигурных скобок, одной  стрелкой:

     "Превед"=>"Медвед"

     Например:

     puts array["мама"] #=> мыла раму

     puts array["807"] #=> nil

     puts array[807] #=> Это число улыбается!

     puts array[1] #=> nil

     puts array["Превед"] #=> Медвед

     Ассоциативные массивы оставляют возможность  хранения данных разного типа только в ассоциативном виде.

     [править]Диапазоны значений

     Чтобы было удобней получать подмассив или подстроку, был введён простенький тип данных — диапазон (класс Range). Диапазон формируется тремя элементами: начало, конец и тип протяжённости (символ .. или ...). Начало и конец должны быть одного типа данных (одного класса) и быть перечислимыми, что значит, иметь метод .succ. Пример диапазонов:

     "a".."z"

     "a"..."z" # то же, что и "a".."y"

     1..100

     1...100 # то же, что и 1..99

     Диапазон-мотоцикл (..) проезжает от первого указанного объекта к его .succ (succedent — «последующему»), и до последнего включительно. Три точки — то же, но мотоцикл остановился прямо перед последним элементом. Ещё раз:

     1..99 ≣ 1...100

     Объекты, имеющие .succ называют последовательными: этим методом можно по текущему элементу достоверно определить следующий.

     [править]Классы и объекты

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

     str = "Я - строка"

     str.class #=> String

     str.class.superclass #=> Object

     Классы  можно определять и создавать  по ним объекты. Внутри класса может  быть много всего интересного, и  у него может быть фамильное дерево, то есть классы Ruby поддерживают наследование. Однако заметим, что множественное наследование в Ruby не разрешается. И ещё много всего интересного можно сделать с классами и объектами. Но об этом позже.

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

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

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

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

     В информатике, спи́сок (англ. list) — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности — кортежа. Экземпляры значений, находящихся в списке, называютсяэлементами списка (англ. item, entry либо element); если значение встречается несколько раз, каждое вхождение считается отдельным элементом.

     

     

     Структура односвязного списка из трёх элементов

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

 

     prefix = constructor List(A)

     head,tail = selectors List(A)

     null,nonnull = predicates List(A)

     NIL,nonNIL = parts List(A)

     Первая  строка данного определения обозначает, что список элементов типа A (говорят: «список над A») представляет собой  размеченное объединение пустого  списка и декартова произведения атома типа A со списком над A. Для  создания списков используются два  конструктора (вторая строка определения), первый из которых создаёт пустой список, а второй — непустой соответственно. Вполне понятно, что второй конструктор  получает на вход в качестве параметров некоторый атом и список, а возвращает список, первым элементом которого является исходный атом, а остальными — элементы исходного списка. То есть получается префиксация атома  к списку, с чем и связано  такое наименование конструктора. Здесь  необходимо отметить, что пустой список [] не является атомом, а потому не может префиксироваться. С другой стороны, пустой список является как бы нулевым элементом для конструирования списков, поэтому любой список содержит в самом своём конце именно пустой список — с него начинается конструирование.

     Третья  строка определяет селекторы для  списка, то есть операции для доступа  к элементам внутри списка. Селектор head получает на вход список и возвращает первый элемент этого списка, то есть типом результата является тип A. Этот селектор не может получить на вход пустой список — в этом случае результат операции неопределён. Селектор tail возвращает список, полученный из входного в результате отсечения его головы (первого элемента). Этот селектор также не может принимать на вход пустой список, так как в этом случае результат операции неопределён. При помощи этих двух операций можно достать из списка любой элемент. Например, чтобы получить третий элемент списка (если он имеется), необходимо последовательно два раза применить селектор tail, после чего применить селектор head. Другими словами, для получения элемента списка, который находится на позиции n (начиная с 0 для первого элемента, как это принято в программировании), необходимо n раз применить селектор tail, после чего применить селектор head.

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

     [править]Свойства

 

     У определённой таким образом структуры данных имеются некоторые свойства:

     Размер  списка — количество элементов в  нём, исключая последний «нулевой»  элемент, являющийся по определению  пустым списком.

     Тип элементов — тот самый тип A, над которым строится список; все  элементы в списке должны быть этого  типа.

     Отсортированность — список может быть отсортирован в соответствии с некоторыми критериями сортировки (например, по возрастанию целочисленных значений, если список состоит из целых чисел).

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

     Сравниваемость — списки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения списков может использовать разные технологии.

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

     [править]Списки в языках программирования

 

     [править]Функциональные языки

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

     [править]Язык Haskell

     [править]Язык Lispактных списков, особенносвязных списков.

     Стек (англ. stack — стопка) — структура данных, в которой доступ к элементам организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.