1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 12
Текст из файла (страница 12)
Списки можно сделать проходимыми в обоих направлениях, если добавить еще один массив, называемый ПРЕДЫДУШАЯ. Значение ПРЕДЫДУ(ДАЯИ равно ячейке, в которой помещается тот элемент списка, который стоит непосредственно перед элементом из ячейки А Список такого рода называется дважды связанным. Из дважды связанного списка можно удалить элемент нли вставить в него элемент, не зная ячейку, где находится предыдущий элемент, Со списком часто работают очень ограниченными приемами. Например, элементы добавляются нли удаляются только на конце списка. Иными словами, элементы вставляются и удаляются по принципу "последний вошел — первый вышел". В этом случае список называют стеком или магазином.
Часто стек реализуется в виде одного массива. Например, список Элем 1, Элем 2, Элем 3 можно было бы хранить в массиве ИМЯ, как показано на рис. 2 4, Переменная ВЕРШИНА является указателем последнего элемента, добавленного к стеку. Чтобы добавить (ЗАТОЛКНУТЬ) новый элемент в стек, значение ВЕРШИНА увеличивают на 1, а затем помещают новый элемент в ИМЯ!ВЕРШИНА). (Поскольку массив ИМЯ имеет конечную длину 1, перед попыткой вставить новый элемент следует проверить, что ВЕРШИНА ( ! — !.) Чтобы удалить (ВЫТОЛКНУТЬ) элемент из вершины стека, надо просто уменьшить значение ВЕРШИНА на!.
Заметим, что не обязательно физически стирать элемент, удаляемый из стека. Чтобы узнать, пуст ли стек, достаточно проверить, не имеет ли ВЕРШИНА значение, меньшее нуля. Понятно, что время выполнения операций ЗАТОЛКНУТЬ и 64 ГЛ. Б РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ имя ЗАДИий ПЕРЕДНИЙ- Рнс. 2.5. Реалнаадии очереди в виде одного массива. ВЫТОЛКНУТЬ и проверка пустоты не зависят от числа элементов в стеке. Другой специальный вид списка — очередь, т. е.
список, в который элементы всегда добавляются с одного (переднего) конца, а удаляются с другого. Как и стек, очередь можно реализовать одним массивом, как показано на рис. 2.5, где приведена очередь, содержащая список из элементов Р, Я, )с, 5, Т. Два указателя обозначают ячейки текущего переднего и заднего концов очереди. Чтобы добавить (ВПИСАТЬ) новый элемент к очереди, как и в случае стека, полагают ПЕРЕДНИЙ = ПЕРЕДНИЙ +1 и помещают новый элемент в ИМЯ(ПЕРЕДНИЙ). Чтобы удалить (ВЫПИСАТЬ) элемент нз очереди, заменяют ЗАДНИЙ на ЗАДНИЙ +1.
Заметьте, что эта техника с точки зрения доступа к элементам основана на принципе "первый вошел — первый вышел". Поскольку массив ИМЯ имеет конечную длину, скажем 1, указатели ПЕРЕДНИЙ и ЗАДНИЙ рано или поздно доберутся до его конца. Если длина списка, представленного этой очередью, никогда не превосходит 1, то можно трактовать ИМЯ[0] как элемент, следующий за элементом ИМЯ(1 — П.
Элементы, расположенные в виде списка, сами могут быть сложными структурами. Работая, например, со списком массивов, мы на самом деле не добавляем и не удаляем массивы, ибо каждое добавление или удаление потребовало бы времени„пропорционального раз- 2.2. ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ меру массива. Вместо этого мы добавляем или удаляем указатели массивов. Таким образом, сложную структуру можно добавить или удалить за фиксированное время, не зависящее от ее размера.
2.2. ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ Обычно списки применяются для представления множеств. При этом объем памяти, необходимый для представления множества, пропорционален числу его элементов. Время, требуемое для выполнения операции над множествами, зависит от природы операции. Например, пусть А и  — два множества. Операция А П В требует времени, по крайней мере пропорционального сумме размеров этих множеств, поскольку как список, представляющий А, так и список, представляющий В, надо просмотреть хотя бы один раз '). Подобным же образом операция А (1 В требует времени, пропорционального сумме размеров множеств, поскольку надо выделить элементы, входящие в оба множества, и вычеркнуть один экземпляр каждого такого элемента. Если же А и В не пересекаются, можно найти А () В за время, не зависящее от размера А и В.
Для этого достаточно сделать конкатенацию списков, представляющих А и В. Задача объединения двух непересекающихся множеств усложняется, если необходимо быстро определять, входит ли данный элемент в данное множество. Этот вопрос подробно обсуждается в разд. 4.6 и 4.7. Другой способ представления множества, отличный от представления его в виде списка,— представление в виде двоичного (битового) вектора. Пусть У вЂ” универсальное множество (т.
е. все рассматриваемые множества являются его подмножествами), состоящее из л элементов. Линейно упорядочим его. Подмножество Ве='У представляется в виде вектора ез из п битов, такого, что у-й разряд в ча равен 1 тогда н только тогда, когда у-й элемент множества У принадлежит 3. Будем называть чз характеристическши вектором для 3. Представление в виде двоичного вектора удобнее тем, что можно определять принадлежность 1-го элемента множества У данному множеству за время, не зависящее от размера данного множества. Более того, основные операции над множествами, такие, как объединение и пересечение, можно осуществить как операции ~/ и Д над двоичными векторами. Если мы не хотим считать операции над двоичными векторами первичными (т. е.
выполняемыми за единицу времени), то можно с таким же успехом вместо характеристического вектора определить массив А, для которого АИ=1 тогда и только тогда, когда 1-й эле- ') Если оба спнсна упорядочены, то дая нахождения ях пересечения суше. етяует линейный алгоритм. йз ГЛ. 2. РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ мент множества () принадлежит 5. При таком представлении все еще легко выяснять, принадлежит ли данный элемент данному мно. жеству.
Недостаток этого представления заключается в том, что объединение и пересечение занимают время, пропорциональное 11Ц1 '), а не размерам рассматриваемых множеств. Подобно этому память, требуемая для хранения множества 5, пропорциональна 11Ц1, а не 1Щ. 2.2. ГРАФЫ Сейчас мы введем математическое понятие графа и те структуры данных, которые обычно применяются для его представления. Определение. Граф б=(У, Е) состоит из конечного непустого множества узлов У и множества ребер Е. Если ребра представлены в виде упорядоченных пар (о, гс) узлов, то граф называется Ориенти. рованным; О называется началом, а гс — концом ребра (п, гс). Если ребра — неупорядоченные пары (множества) различных вершин, также обозначаемые (п, гс), то граф называют неориентирсванным *).
Если в ориентированном графе б=(У, Е) пара (и, гс) принадлежит множеству ребер Е, то узел гс называется смежным с узлом о. Говорят, что ребро (о, гв) идет из о в гс. Число узлов, смежных с узлом о, называется нолустеленью еео исхода, Если (п, гс) — ребро неориентированного графа б=(У, Е), то мы считаем, что (и, гн)=(гс, о), так что (гс, о) — то же самое ребро. Узел гн называется смежным с узлом о, если (о, гн) (а значит, и (гн, О)) принадлежит Е. Степень узла — это число узлов, смежных с ним.
Путем в ориентированном или неориентированном графе называют последовательность ребер вида (онпз) (омо,), ..., (о -ыов). Говорят, что этот путь идет из и, во„и имеет длину н — ). Часто такой путь представляют последовательностью о„о„..., о„узлов, лежащих на нем. В вырожденном случае один узел обозначает путь длины О, идущий из этого узла в него же. Путь называется простым, если все ребра и все узлы иа нем, кроме, быть может, первого и последнего, различны.
Цикл — это простой путь длины не менее 1, который начинается и кончается в одном и том же узле. Заметим, что в неориентированном графе длина цикла должна быть не менее 3. Известно несколько представлений графа б=(У, Е). Один из них — матрица смежностей, т. е. матрица А размера 11У11х11У11, состоящая из О и 1, в которой А(г', )1= ) тогда и только тогда, когда есть ребро из узла ) в узел /. Представление в виде матрицы смеж- ') зХ)! обозначает здесь число злементов (рззмер, нлн мощносгнь) множе.
ствз Х. 2) Заметим, что в ориентированном графе может быть ребро (о, о), з в неорнентнроввнном — нет. КОНЕИ СЛОЮ Улел ЯД т г /7уллгпгу плаатат з ~а ) 2~ )-м~ З) О~ а 7 8 Э Рнс. 2.6. Ориентированный граф н его представления: а — ориентированный граф; б — матрица смежностей; а — спнскн смежностей; г — табличное представление списков смежностей. 3 А. Аао, дж. Хопкробт, дж. улькин ностей удобно для тех алгоритмов на графах, которым часто нужно знать, есть ли в графе данное ребро, ибо время, необходимое для определения наличия ребра, фиксировано и не зависит от ЕЩ и 1!Ей.
Основной недостаток применения матрицы смежностей заключается в том, что она занимает память объема ~1)г!~е даже тогда„когда граф содержит только 0(й)гй) ребер. Уже начальное заполнение матрицы смежностей посредством "естественной" процедуры требует времени 0(Я~а), что сводит на нет алгоритмы сложности 0(Й)гй) при работе с графами, содержащими лишь 0(й)гй) ребер. Хотя разработаны методы для преодоления этой трудности (см. упр. 2.12), почти неизбежно возникают другие проблемы, которые приводят к тому, что алгоритмы сложности 0(й)гй), основанные на работе с матрицей смежностей, встречаются редко.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
