![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Виды списков.
Оглавление I. Введение………………………………………………………………………………… 3 II. Виды списков…………………………………………………………………………... 4 III. Заключение …………………………………………………………………...……….11 IV. Список литературы………………………………………………………………….. 11
Введение Современному человеку из информационного общества очень важно научиться работать и информацией и применять различные инструменты для упрощения этой работы. Одним из таких инструментов является компьютер, который стал универсальным помощником человеку в различных сферах деятельности. Компьютерные программы обычно оперируют с таблицами информации. В большинстве случаев это не просто аморфные массы числовых величин: в таблицах присутствуют важные структурные отношения между элементами данных. Поэтому важно добиться хорошего понимания структурных отношений, существующих между данными, способов представления таковых в машине и методов работы с ними. В простейшей форме таблица может быть линейным списком элементов. Тогда присущие ей структурные свойства содержат в себе ответы на такие вопросы, как: " Какой элемент является первым в списке? какой — последним? какой элемент предшествует данному или следует за данным? " Можно много говорить о структуре даже в этом совершенно очевидном случае. В некоторых ситуациях таблица может быть двумерным массивом (т. е. матрицей, иногда называемой сеткой, имеющей структуру строк и столбцов), либо может быть n-мерным массивом при весьма больших значениях n, либо она может иметь структуру дерева, представляющего отношения иерархии или ветвления, либо это может быть сложная многосвязанная структура с огромным множеством взаимных соединений, такая, например, которую можно найти в человеческом мозгу. Системы обработки списков полезны в очень многих случаях, однако при их использовании программист нередко сталкивается с излишними ограничениями. Целью данной работы был сбор и предоставление информации о существующих видах списков.
Виды списков. Список (list) – набор элементов, расположенных в определенном порядке. Таким набором быть может ряд знаков в слове, слов в предложений в книге. Этот термин может также относиться к набору элементов на диске. Использование при обработке информации списков в качестве типов данных привело к появлению в языках программирования средств обработки списков. Список очередности (pushup list) – список, в котором последний поступающий элемент добавляется к нижней части списка. Список с использованием указателей (linked list) – список, в котором каждый элемент содержит указатель на следующий элемент списка. Линейный список (linear list) — это множество, состоящее из Операции, которые мы имеем право выполнять с линейными списками, включают, например, следующие: 1. Получить доступ к k-му узлу списка, чтобы проанализировать и/или изменить содержимое его полей. 2. Включить новый узел непосредственно перед k-ым узлом. 3. Исключить k-й узел. 4. Объединить два (или более) линейных списка в один список. 5. Разбить линейный список на два (или более) списка. 6. Сделать копию линейного списка. 7. Определить количество узлов в списке. 8. Выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах. 9. Найти в списке узел с заданным значением в некотором поле. Специальные случаи k=1 и k=n в операциях (1), (2) и (3) особо выделяются, поскольку в линейном списке проще получить доступ к первому и последнему элементам, чем к произвольному элементу. В машинных приложениях редко требуются все девять из перечисленных выше операций в самом общем виде. Мы увидим, что имеется много способов представления линейных списков в зависимости от класса операций, которые необходимо выполнять наиболее часто. По-видимому, трудно спроектировать единственный метод представления для линейных списков, при котором все эти операции выполняются эффективно; например, сравнительно трудно эффективно реализовать доступ к k-му узлу в длинном списке для произвольного k, если в то же время мы включаем и исключаем элементы в середине списка. Следовательно, мы будем различать типы линейных списков по главным операциям, которые с ними выполняются. Однонаправленный и двунаправленный список – линейные списки, в которых все исключения и добавления происходят в любом месте списка. Однонаправленный список отличается от двунаправленного списка только связью. То есть в однонаправленном списке можно перемещаться только в одном направлении (из начала в конец), а двунаправленном – в любом. Из рисунка это видно: сверху однонаправленный список, а снизу двунаправленный
На рисунке видно как добавляется и удаляется элемент из двунаправленного списка. При добавлении нового элемента (обозначен N) между элементами 2 и 3. Связь от 3 идет к N, а от N к 4, а связь между 3 и 4 удаляется. В однонаправленном списке структура добавления и удаления такая же только связь между элементами односторонняя. Очередь (queue) — линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце. Очередь — тип данных, при котором новые данные располагаются следом за существующими в порядке поступления; поступившие первыми данные при этом обрабатываются первыми.
В некоторых разделах математики слово " очередь" используют в более широком смысле, обозначая любой сорт списка, в котором производятся включения и исключения; указанные выше специальные случаи называются тогда " очередями с различными дисциплинами". Однако здесь термин " очередь" используется лишь в узком смысле, аналогичном упорядоченным очередям людей, ожидающим обслуживания. У очереди есть голова (head) и хвост (tail). Элемент, добавляемый в очередь, оказывается в её хвосте, как только что подошедший покупатель; элемент, удаляемый из очереди, находится в её голове, как тот покупатель, что отстоял дольше всех.
В очереди новый элемент добавляется только с одного конца. Удаление элемента происходит на другом конце. В данном случае это может быть только 4 элемент. Очередь по сути однонаправленный список, только добавление и исключение элементов происходит на концах списка. Стек (stack) — линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка. Стек — часть памяти ОЗУ компьютера, которая предназначается для временного хранения байтов, используемых микропроцессором; при этом используется порядок запоминания байтов “последним вошел – первым вышел”, поскольку такие ввод и вывод организовывать проще всего, также операции осуществляются очень быстро. Действия со стеком производится при помощи регистра указателя стека. Любое повреждение этой части памяти приводит к фатальному сбою. Стек в виде списка (pushdown list) – стек, организованный таким образом, что последний вводимый в область памяти элемент размещается на вершине списка. Из стека мы всегда исключаем " младший" элемент из имеющихся в списке, т. е. тот, который был включен позже других. Для очереди справедливо в точности противоположное правило: исключается всегда самый " старший" элемент; узлы покидают список в том порядке, в котором они в него вошли. Стеки очень часто встречаются в практике. Простым примером может служить ситуация, когда мы просматриваем множество данных и составляем список особых состояний или объектов, которые должны обрабатываться позднее; когда первоначальное множество обработано, мы возвращаемся к этому списку и выполняем последующую обработку, удаляя элементы из списка, пока список не станет пустым. Для этой цели пригодны как стек, так и очередь, но стек, как правило, удобнее. При решении задач наш мозг ведет себя как " стек": одна проблема приводит к другой, а та в свою очередь к следующей; мы накапливаем в стеке эти задачи и подзадачи и удаляем их по мере того, как они решаются. Аналогично процесс входов в подпрограммы и выходов из них при выполнении машинной программы подобен процессу функционирования стека. Стеки особенно полезны при обработке языков, имеющих структуру вложений. К ним относятся языки программирования, арифметические выражения и немецкие " Schachtelsatze" /буквально " вложенные предложения" /. Стек можно представить себе как коробку, в которую складывают какие-нибудь предметы, чтобы достать самый нижний нужно предварительно вытащить остальные. Стек можно уподобить стопке тарелок, из которой можно взять верхнюю и на которую можно положить новую тарелку. Другое название стека в русской литературе — “магазин” — понятно всякому, кто разбирал автомат Калашникова].
Дек (deck) (стек с двумя концами) — линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются на обоих концах списка. Иногда аналогия с переключением железнодорожных путей, предложенная Э. Дейкстрой, помогает понять механизм стека. На рис. 2. Изображен дек в виде железнодорожного разъезда.
В связанном списке (linked list) элементы линейно упорядочены, но порядок определяется не номерами, как в массиве, а указателями, входящими в состав элементов списка. Списки являются удобным способом хранения динамических множеств, позволяющим реализовать все операции, (хотя и не всегда эффективно). Если каждый стоящий в очереди запомнит, кто за ним стоит, после чего все в беспорядке рассядутся на лавочке, получится односторонне связанный список; если он запомнит ещё и впереди стоящего, будет двусторонне связанный список. Элемент двусторонне связанного списка (doubly linked list) — это запись, содержащая три поля: key (ключ) и два указателя — next (следующий) и prev (от previous—предыдущий). Помимо этого, элементы списка могут содержать дополнительные данные. Если х —элемент списка, то next указывает на следующий элемент списка, а prev — на предшествующий. Если prev{х}=nil, то у элемента х нет предшествующего: этоголова (head) списка. Если next{х}= nil, то х — последний элемент списка или, как говорят, егохвост (tail).
Вместо того чтобы хранить список в последовательных ячейках памяти, можно использовать значительно более гибкую схему, в которой каждый узел содержит связь со следующим узлом списка.
Здесь А, В, С, D и Е— произвольные ячейки в памяти, а Л — пустая связь. Программа, в которой используется такая таблица, имела бы, в случае последовательного распределения, дополнительную переменную или константу, значение которой показывает, что таблица состоит из пяти элементов; эту же информацию можно задать с помощью признака конца (" пограничника"), снабдив им элемент 5 или следующую ячейку, В случае связанного распределения в программе имеется переменная связи или константа, которая указывает на А, а отправляясь от А, можно найти все другие элементы списка. Использование связанного распределения, как правило, предполагает существование некоторого механизма поиска пустого пространства для нового узла, когда мы хотим включить в список некоторую вновь образованную информацию. Для этой цели обычно существует специальный список, называемый списком свободного пространства.
Он обладает той особенностью, что связь его последнего узла не равна Л, а идет назад к первому узлу списка. В этом случае можно получить доступ к любому элементу, находящемуся в списке, отправляясь от любой заданной точки; одновременно мы достигаем также полной симметрии, и теперь нам уже не приходится различать в списке " последний" или " первый" узел. Типичная ситуация выглядит следующим образом: Предположим, в узлах имеется два поля: INFO и LINK. Переменная связи PTR указывает на самый правый узел списка, a LINK (PTR) является адресом самого левого узла. Разного рода расщепления одного циклического списка на два, соответствуют операциям конкатенации (объединения) и деконкатенации (разъединения) цепочек. Циклические списки можно использовать не только для представления структур, которым свойственна цикличность, но также для представления линейных структур; циклический список с одним указателем на последний узел, по существу, эквивалентен простому линейному списку с двумя указателями на начало и конец. Заключение В данном УСРС были рассмотрены разнообразные виды списков. Для каждого списка можно привести жизненные примеры для простоты восприятия. Я думаю, что изучив более конкретно и полно каждый список в отдельности, студент сможет предусматривать целесообразность их использования в тех или иных случаях.
Список литературы: 1. Айен Синклер “Большой толковый словарь компьютерных терминов”, М.: 1998 г. 2. Вирт Н. “Алгоритмы и структуры данных”, Москва Изд. Мир, 1989 г. 3. Зубов В. С. “Справочник программиста”, М.: 1999 г.
|