Алгоритм и структура данных. 1 Базовый процедурноориентированный алгоритмический язык
 Скачать 1.16 Mb.
|
Линейные структуры данныхВ программировании со структурами данных мы встречаемся постоянно. Вокруг них чаще всего весь процесс и строится. В каких-то языках программирования мы работаем с памятью напрямую, и структурированием данных приходится заниматься самостоятельно. В других уже есть готовые классы и функции для работы с данными. Но базовые паттерны одни и те же во всех случаях. Рассмотрим общие принципы без привязки к какому-либо языку программирования. Предполагается, что вы понимаете по какой логике работает память компьютера (что это просто длинная лента с ячейками для байтов). В заголовке было сказано о линейных структурах. Линейные структуры данных — это когда все элементы расположены в форме последовательности. То есть массив — это линейная структура данных, граф — нет. Массивы Массив — структура данных, хранящая набор значений (элементов массива), идентифицируемых по индексу или набору индексов, принимающих целые (или приводимые к целым) значения из некоторого заданного непрерывного диапазона. Одномерный массив можно рассматривать как реализацию абстрактного типа данных — вектор. В некоторых языках программирования массив может называться также таблица, ряд, вектор, матрица. Стеки Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. lastin — firstout, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Очередь О́чередь — абстрактный тип данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, англ. first in, first out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется. Списки Список - довольно широко используемая структура данных в области числового программирования. Список -это упорядоченная последовательность элементов, которая может иметь произвольную длину. Признак упорядоченный указывает на то, что порядок элементов в последовательности является существенным. Элементами списка могут быть любые термы – константы, переменные, структуры, которые включают, конечно, и другие списки. В информатике, спи́сок (англ. list) — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности. Экземпляры значений, находящихся в списке, называются элементами списка (англ. item, entry либо element); если значение встречается несколько раз, каждое вхождение считается отдельным элементом.  Структура односвязного списка из трёх элементов Термином список также называется несколько конкретных структур данных, применяющихся при реализации абстрактных списков, особенно связных списков. Связные и двусвязные списки Связный список является простейшим типом данных динамической структуры, состоящей из элементов (узлов). Каждый узел включает в себя в классическом варианте два поля: данные (в качестве данных может выступать переменная, объект класса или структуры и т. д.) указатель на следующий узел в списке. Элементы связанного списка можно помещать и исключать произвольным образом. Доступ к списку осуществляется через указатель, который содержит адрес первого элемента списка, называемый корнем списка.  |