Виды списков.

Оглавление

I. Введение………………………………………………………………………………… 3

II. Виды списков…………………………………………………………………………... 4

III. Заключение …………………………………………………………………...……….11

IV. Список литературы………………………………………………………………….. 11

Введение

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

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

В простейшей форме таблица может быть линейным списком элементов. Тогда присущие ей структурные свойства содержат в себе ответы на такие вопросы, как: " Какой элемент является первым в списке? какой — последним? какой элемент предшествует данному или следует за данным? " Можно много говорить о структуре даже в этом совершенно очевидном случае.

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

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

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

Виды списков.

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

Список очередности (pushup list) – список, в котором последний поступающий элемент добавляется к нижней части списка.

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

Линейный список (linear list) — это множество, состоящее из узлов , структурные свойства которого по сути ограничиваются лишь линейным (одномерным) относительным положением узлов, т. е. теми условиями, что если , то является первым узлом; если , то k-му узлу предшествует и за ним следует ; является последним узлом.

Операции, которые мы имеем право выполнять с линейными списками, включают, например, следующие:

1. Получить доступ к k-му узлу списка, чтобы проанализировать и/или изменить содержимое его полей.

2. Включить новый узел непосредственно перед k-ым узлом.

3. Исключить k-й узел.

4. Объединить два (или более) линейных списка в один список.

5. Разбить линейный список на два (или более) списка.

6. Сделать копию линейного списка.

7. Определить количество узлов в списке.

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

9. Найти в списке узел с заданным значением в некотором поле.

Специальные случаи k=1 и k=n в операциях (1), (2) и (3) особо выделяются, поскольку в линейном списке проще получить доступ к первому и последнему элементам, чем к произвольному элементу.

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

Однонаправленный и двунаправленный список – линейные списки, в которых все исключения и добавления происходят в любом месте списка.

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

Очередь — тип данных, при котором новые данные располагаются следом за существующими в порядке поступления; поступившие первыми данные при этом обрабатываются первыми.

В некоторых разделах математики слово " очередь" используют в более широком смысле, обозначая любой сорт списка, в котором производятся включения и исключения; указанные выше специальные случаи называются тогда " очередями с различными дисциплинами". Однако здесь термин " очередь" используется лишь в узком смысле, аналогичном упорядоченным очередям людей, ожидающим обслуживания. У очереди есть голова (head) и хвост (tail). Элемент, добавляемый в очередь, оказывается в её хвосте, как только что подошедший покупатель; элемент, удаляемый из очереди, находится в её голове, как тот покупатель, что отстоял дольше всех.

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

Стек — часть памяти ОЗУ компьютера, которая предназначается для временного хранения байтов, используемых микропроцессором; при этом используется порядок запоминания байтов “последним вошел – первым вышел”, поскольку такие ввод и вывод организовывать проще всего, также операции осуществляются очень быстро. Действия со стеком производится при помощи регистра указателя стека. Любое повреждение этой части памяти приводит к фатальному сбою.

Стек в виде списка (pushdown list) – стек, организованный таким образом, что последний вводимый в область памяти элемент размещается на вершине списка.

Из стека мы всегда исключаем " младший" элемент из имеющихся в списке, т. е. тот, который был включен позже других. Для очереди справедливо в точности противоположное правило: исключается всегда самый " старший" элемент; узлы покидают список в том порядке, в котором они в него вошли.

Стеки очень часто встречаются в практике. Простым примером может служить ситуация, когда мы просматриваем множество данных и составляем список особых состояний или объектов, которые должны обрабатываться позднее; когда первоначальное множество обработано, мы возвращаемся к этому списку и выполняем последующую обработку, удаляя элементы из списка, пока список не станет пустым. Для этой цели пригодны как стек, так и очередь, но стек, как правило, удобнее. При решении задач наш мозг ведет себя как " стек": одна проблема приводит к другой, а та в свою оче­редь к следующей; мы накапливаем в стеке эти задачи и подзадачи и удаляем их по мере того, как они решаются. Аналогично процесс входов в подпрограммы и выходов из них при выполнении машинной программы подобен процессу функционирования стека. Стеки особенно полезны при обработке языков, имеющих структуру вложений. К ним относятся языки программирования, арифметические выражения и немецкие " Schachtelsatze" /буквально " вложенные предложения" /.

Стек можно представить себе как коробку, в которую складывают какие-нибудь предметы, чтобы достать самый нижний нужно предварительно вытащить остальные. Стек можно уподобить стопке тарелок, из которой можно взять верхнюю и на которую можно положить новую тарелку. Другое название стека в русской литературе — “магазин” — понятно всякому, кто разбирал автомат Калашникова].

Иногда аналогия с переключением железнодорожных путей, предложенная Э. Дейкстрой, помогает понять механизм стека. На рис. 2. Изображен дек в виде железнодорожного разъезда.

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

Если каждый стоящий в очереди запомнит, кто за ним стоит, после чего все в беспорядке рассядутся на лавочке, получится односторонне связанный список; если он запомнит ещё и впереди стоящего, будет двусторонне связанный список. Элемент двусторонне связанного списка (doubly linked list) — это запись, содержащая три поля: key (ключ) и два указателя — next (следующий) и prev (от previous—предыдущий). Помимо этого, элементы списка могут содержать дополнительные данные. Если х —элемент списка, то next указывает на следующий элемент списка, а prev — на предшествующий. Если prev{х}=nil, то у элемента х нет предшествующего: этоголова (head) списка. Если next{х}= nil, то х — последний элемент списка или, как говорят, егохвост (tail).

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

Здесь А, В, С, D и Е— произвольные ячейки в памяти, а Л — пустая связь. Программа, в которой используется такая таблица, имела бы, в случае последовательного распределения, дополнительную переменную или константу, значение которой по­казывает, что таблица состоит из пяти элементов; эту же информа­цию можно задать с помощью признака конца (" пограничника"), снабдив им элемент 5 или следующую ячейку, В случае связанного распределения в программе имеется переменная связи или константа, которая указывает на А, а отправляясь от А, можно найти все другие элементы списка. Использование связанного распределения, как правило, предполагает существование некоторого механизма поиска пустого пространства для нового узла, когда мы хотим включить в список некоторую вновь образованную информацию. Для этой цели обычно существует специальный список, называемый списком свободного пространства.

Циклическое кольцо или список (circular list или ring) – файл, у которого нет определенного начала и конца; каждый элемент файла содержит указатель на начало следующего элемента; при этом “последний” элемент указывает на “первый”, так что к списку можно обратиться с любого элемента.

Предположим, в узлах имеется два поля: INFO и LINK. Переменная связи PTR указывает на самый правый узел списка, a LINK (PTR) является адресом самого левого узла.

Разного рода расщепления одного циклического списка на два, соответствуют операциям конкатенации (объединения) и деконкатенации (разъединения) цепочек.

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

Заключение

В данном УСРС были рассмотрены разнообразные виды списков. Для каждого списка можно привести жизненные примеры для простоты восприятия. Я думаю, что изучив более конкретно и полно каждый список в отдельности, студент сможет предусматривать целесообразность их использования в тех или иных случаях.

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

1. Айен Синклер “Большой толковый словарь компьютерных терминов”, М.: 1998 г.

2. Вирт Н. “Алгоритмы и структуры данных”, Москва Изд. Мир, 1989 г.

3. Зубов В. С. “Справочник программиста”, М.: 1999 г.