Файл: Основы программирования на языке Pascal ( ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПАСКАЛЬ).pdf

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

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

Все элементы списка хранят:

1. Хранит информацию любого вида.
2. Указывает следующий элемент списка.

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

Рис.2.Данные динамической структуры

Однонаправленный и двунаправленный список

Этот метод заключается в том, что его изменение может проходит на любом промежутке списка. [20, с.27]

Направление однонаправленного списка отличает от двунаправленного в том, их различие только в связи. Получается, что в однонаправленном изменения в списке можно производить только в одном направлении, а уже в двунаправленном в любом порядке. [15, с.27]

Первый рисунок является однонаправленным, а второй двунаправленным (см. рис 3-4).

5

4

2

1

3

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

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

5

3

1

2

4

В двунаправленном списке, как ниже показано на рисунке, осуществляется удаление и добавление элемента. Когда добавляется новый элемент между 2 и 3 , связь которая была теряется в участке 3 и 4 (см. рис 5).

4

N

5

3

1

2

Рис.5.Связь между 3 и 4

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

Очередь

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

---

Рис.6.Очередеь

Начало

Второй

Третий

Конец

Исключить

Включить

Само правило этого списка, подобно живой очереди, первым стоял, первым будешь обслужен, а уже при добавлении будет увеличиться число в списке. У любой очереди имеется как голова, так и хвост. Те элементы, которые добавляются в список оказываются в хвосте, а объект удаляемый из этой очереди находится в голове списка. [18, с.27]

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

Рис.7.Новый элемент очереди

Начало

Второй

Третий

Конец

Новый

Эти 4 элемента показаны на рисунке выше. Очередь – это так называемый односторонний список, где добавление или исключение из него происходит в конце.

Стек

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

Стек – временная память, которая занимает часть ОЗУ, памяти компьютера, то что использует микропроцессор. При таком режиме работы, работает функция «запоминания байтов». Принцип этого списка, последним войдя, первым уйдёшь. Данные списки проще всего организовать, и быстрота операций на много лучше. Эти функции включаются при помощи «Регистра», если же на любой части этого стека, будет повреждение то это приведёт к неработоспособности списка (см. рис 8).

Возможно и такое что, элемент введённый в список элемент окажется на вершине списка. Исключается всегда элемент, который оказался младшим в его частности, или тот что включился позже всех.

Для такой очереди имеется абсолютно противоположное правило, где может быть исключён из списка только старший, узлы которого покидают его в том же порядке в котором были в него добавлены (см. рис 9).

Второй сверху

Включить или исключить

Верх

Низ

Третий сверху

Рис.8. Регистра

Сами стеки очень часто могут встречаться на практике, например когда мы стоим какой либо список состоящий из каких либо событий, и выстраиваем порядок их обработки, после обработки мы возвращаемся к следующей обработке данных. [8, с.27]

---

Тем самым мы подчищаем список, где уже видно нужные и не нужные объекты. Но это можно делать как в «стеке» так в «очереди». Допустим стек работает как мозг, в нём удобнее производить анализ, то есть когда решается какая либо проблема, мы просто её удаляем, то же самое и выполняет «стек».

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

Дек

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

Рис.9. Стек, представленный в виде железнодорожного разъезда

Дек похож на колоду карт, чем стек, он имеет больше возможностей. Дек бывает с «ограниченным входом» или «ограниченным выходом», но в этих случаях исключения происходят только на одном конце(см. рис. 10).

Рис.10.Дек с «ограниченным входом»

Дек это так называемый двунаправленный список.

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

1

2

3

4

N

N

Если система обнаруживает беспорядок, то она выполнит операцию по установлению порядка. [16, с.27]

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

Если же имеются элементы которые не были оговорены, то это уже будет двусторонний связной список (см. рис. 11).

Элемент 5

Элемент 4

Элемент 3

Элемент 2

Элемент 1

L₀ + 5c:

L₀ + 4c:

L₀ + 3c:

L₀ + 2c:

L₀ + c:

Элемент 5

Элемент 4

Элемент 3

Элемент 2

Элемент 1

Л

E

D

C

B

Л:

E:

D:

C:

B:

Последовательное распределение

Адрес

---

Содержимое

Связанное распределение

Адрес

Содержимое

Рис.11. Двусторонний связной список

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

Какую либо связь можно указать стрелкам, так как без разницы какую клетку наймёт клиент (см. рис. 12).

Рис.12. Элементы

Элемент 1

Элемент 2

Элемент 3

Элемент 4

Элемент 5

FIRST

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

Операции над списочными структурами

В машинной памяти списки представляются в виде комбинации каким

либо образом связанных между собой или с полями в которых есть два поля (см рис 13).

…

Рис.13.Комбинации

Количество элементов может ссылаться на другой какой либо элемент или произвольное. Имя может иметь значение как и списочный элемент. Все имена которые хранит программа, находятся в постоянной работе, которые строены в таблицу программы. Так же они могут и не иметь имён, но в этом случае они будут работать на ограниченном промежутке. [21, с.27]

Структуры памяти

Списки – это такая совокупность атомов, что позволяет связывать специальные элементы, то есть в информационной науке это называется cons-ячейки или списочные ячейки. [4, с.27]

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

Рис.14.Ячейки указывают на атомы

Бывает, что обе ячейки указывают на атомы, это записывается как (см. рис 14).

Представления списков через списочные ячейки

Содержание одного атома, записывается следующим образом (см.рис 15):

Рис.15. Содержание одного атома

На конце списка указывается NIL

Вместо nil пишут - \.

Список получается как операция (cons 'a nil)

---

Список из двух элементов (b a)

Правое поле указывается на cdr хвост списка.

Левое должно поле, на саr голову списка.

Соответствием списка занимается списочная ячейка.

Если в списке нет ни одного уровня (a (b c) d), тогда каждому элементу списка должна соответствовать списочная ячейка. Причем саr это поле второй списочной ячейки может указывать на вложенный список.

Представления списков через точечную пару

Абсолютно любой список возможно записать в точечной нотации.

(a) <=> (a.nil)

(a b c) <=> (a.(b.(c.nil)))

Выражение которое представленно в точечной нотации нужно привести к списочной в том случае, если cdr поле является списком.

(a.(b c)) <=> (a b c)

(a.(b.c)) <=> (a b.c)

Списочная ячейка и базовые функции

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

* (сar '(a (b c) d)

a

Результатом любого действия функции cdr будет значение либо правого поля либо первой списочной ячейки.

* (сdr '(a (b c) d)

((b c) d)

CONS создает новые списочные ячейки, car поле которых указывает на первый элемент, а уже cdr на второй (cons 'x '(a b c))

или

LIST * (list 'a '(b c)) (a (b c))

Такие списки представляются в этом виде.

Это всё получается следующим образом:

1. Создается списочная ячейка где для каждого аргумента функции.

2. В car поле должен ставится указатель на соответствующий элемент.

3. В cdr поле должен ставится указатель на следующую списочную ячейку.

Переменные и списки

Рассмотрим данное выражение:

(setq y '(a b c))

Где переменная Y должна иметь значение '(a b c)

Использование данной переменной , в функции обеспечивает доступ к структуре.

(setq x (cons 'd y))

CONS не может изменять структуры, и увеличивает список.

Если в функции идёт присвоение списков задается явно, то под него должны отводится новые списочные ячейки т.е.

(setq z '(a b c))

Допустим переменная z будет иметь значение '(a b c).

Использование разрушающих функций

Разрушающую функцию необходимо использовать при работе с очень большими списками, чтобы не увеличивать расход памяти к примеру использовать nconc вместо append. [11, с.27]

Однако такое использование разрушающих функций приводит к побочным эффектам.

---