Динамические структуры данных

Материал из ПИЭ.Wiki

Перейти к: навигация, поиск
Файл:Wiki_letter_w.png

Это незавершённая статья. Вы можете помочь проекту, исправив и дополнив её.


Содержание

Типы рекурсивных данных

Ссылки

Линейные списки

Линейный список представляет собой последовательность n≥0 узлов Х[1], X[2], … , X[n], важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии. Иначе говоря, в такой структуре должно соблюдаться следующее условие: если n>0 и X[1] является первым узлом, а X[n] – последним, то k –й узел следует за X[k-1] и предшествует узлу X[k+1] для всех 1< k <n. Элемент списка состоит из двух частей: информационной, содержащей данные, и адресной, где хранятся указатели на следующие элементы.

В зависимости от количества полей в адресной части и порядка связывания элементов различают:

Линейные односвязные списки – единственное адресное поле содержит адрес следующего элемента. Если следующий элемент отсутствует, то в адресное поле заносят константу nil;

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

Tape pe = ^element; {тип указателя}

element = record

name: string[16]; {информационное поле 1}

telefon: string[7]; {информационное поле 2}

p: pe; {адресное поле}

end;

Элемент двусвязного списка описывается с двумя адресными полями, например:

Tape pe = ^element; {тип указателя}

element = record

name: string[16]; {информационное поле 1}

telefon: string[7]; {информационное поле 2}

prev: pe; {адресное поле «предыдущий»}

next: pe; {адресное поле «следующий»}

end;


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

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

2) Вставка нового узла сразу после или до k-го узла.

3) Удаление k-го узла.

4) Объединение в одном списке двух или более линейных списков.

5) Разбиение линейного списка на два или более списка.

6) Создание копии линейного списка.

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

8) Сортировка узлов в порядке возрастания значений в определенных полях этих узлов.

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

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

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

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

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

Файл:линейные_списки.png

Рис.1. Три наиболее важных класса линейных списков

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

Исходные установки.

В начале программы необходимо описать элемент и его тип:

Type tpel=^element; {тип «указатель на элемент»}

element=record

num: integer; {число}

p:tpel; {указатель на следующий элемент}

end;

В статистической памяти описываем переменную-указатель списка и несколько пе-ременных-указателей, используемых при выполнении операций со списком:

Var first, {указатель списка – адрес первого элемента списка}

n,f,q:tpel; {вспомогательные указатели}

исходное состояние «список пуст»:

first:=nil;

Добавление нового элемента к списку. Добавление элемента к списку включает запрос памяти для размещения элемента и заполнение его информационной части. По-строенный таким образом элемент добавляется к уже существующей части списка.

В общем случае при добавлении элемента к списку возможны следующие варианты:

• Список пуст, добавляемый элемент станет единственным элементом списка.

• Элемент необходимо вставить перед первым элементом списка.

• Элемент необходимо вставить перед заданным элементом списка.

• Элемент необходимо дописать в конец списка.

Добавление к пустому списку состоит из записи адреса элемента в указатель списка, причем в поле «адрес следующего» добавляемого элемента необходимо поместить nil;

new(first); {запрашиваем память под элемент}

first^.num:=5; {заносим число в информационное поле}

first^.p:=nil; {записываем nil в поле «адрес следующего»}


Добавление элемента перед первым элементом списка. При выполнении этой операции необходимо в поле «адрес следующего» переписать адрес первого элемента списка, а в указатель списка занести адрес добавляемого элемента:

new(q); {запрашиваем память под элемент}

q^.num:=4; {заносим число в информационное поле}

q^.p:=first; {в поле «адрес следующего» переписываем адрес первого элемента}

first:=q; … {в указатель списка заносим адрес нового элемента}


Добавление элемента перед заданным. Для выполнения операции необходимо знать адреса элементов, между которыми вставляется элемент, так как адресные части этих элементов при выполнении операции будут корректироваться. Пусть f – адрес предыдущего элемента, а n – адрес следующего элемента, тогда:

new(q); {запрашиваем память под элемент}

q^.num:=3; {заносим число в информационное поле}

q^.p:=n; {в поле «адрес следующего» нового элемента переписываем адрес следующего элемента}

f^.p:=q; …{в поле «адрес следующего» предыдущего элемента заносим адрес ново-го элемента}

Минимально для вставки элемента в линейный односвязный список необходимо знать только адрес предыдущего элемента, так как тогда адрес следующего элемента известен – n f^.p;

new(q); {запрашиваем память под элемент}

q^.num:=3; {заносим число в информационное поле}

q^.p:=f^.p; {в поле «адрес следующего» нового элемента переписываем адрес следующего элемента}

f^.p:=q; … {в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}

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

new(q); {запрашиваем память под элемент}

q^.num:=7; {заносим число в информационное поле}

q^.p:=nil; {в поле «адрес следующего» нового элемента записываем nil}

f^.p:=q; …{в поле «адрес следующего» предыдущего элемента заносим адрес ново-го элемента}

Просмотр и обработка элементов списка. Просмотр и обработка элементов списка выполняется последовательно с использованием дополнительного указателя:

f:=first;

while f<>nil do

begin

<обработка элемента по адресу f>

f:=f^.p;

end;…

В качестве примера рассмотрим вывод на экран элементов списка:

f:=first;

while f<>nil do

begin

writeln (f^.num,’ ‘);

f:=f^.p;

end;…

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

f:=first;

flag:=false;

while (f<>nil) and (not flag) do

begin

if f^.num=k then flag:=not flag

else f:=f^.p;

end;

if flag then <элемент найден>

else<элемент не найден>; …

Удаление элемента из списка. При выполнении операции удаления также возможны четыре случая:

• Удаление единственного элемента.

• Удаление первого (не единственного) элемента списка.

• Удаление элемента, следующего за данным.

• Удаление последнего элемента.

Удаление единственного элемента.После удаления единственного элемента спи-сок становиться пустым, следовательно при выполнении этой операции необходимо не только освободить память, выделенную для размещения элемента, но и занести nil в указатель списка first:

Dispose(first);

first:=nil; …

Удаление первого (неединственного) элемента списка. Удаление первого элемента состоит из сохранения адреса следующего в рабочей переменной f, освобождения памяти элемента и записи в указатель списка сохраненного адреса следующего элемента:

f:=first^.p; {сохраняем адрес следующего элемента}

dispose(first); {освобождаем память}

first:=f; … {заносим в указатель списка адрес следующего элемента}

Удаление элемента, следующего за данным (не последнего). Удаление элемента, следующего за данным, требует запоминания адреса удаляемого элемента, изменения адресной части данного элемента и освобождения памяти.

n:=f^.p; {сохраняем адрес удаляемого элемента}

f^.p:=n^.p; {заносим в адресное поле предыдущего элемента адрес следующего}

dispose(n); … {освобождаем память}

Удаление последнего элемента. Удаление последнего элемента отличается только тем, что в поле «адрес следующего» заданного элемента записывается константа nil:

n:=f^.p;

f^.p:=nil;

dispose(n); …

Удаление последнего элемента можно свести к удалению элемента, следующего за данным, так как адресная часть удаляемого элемента равна nil. Комбинируя приемы удаления, мы можем организовать любую дисциплину удаления.

Деревья

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

Формально дерево ( tree ) определяется как конечное множество T одного или более узлов со следующими свойствами: а)Существует один выделенный узел, а именно – корень ( root ) данного дерева; А б)Остальные узлы (за исключением корня) распределены среди m>=0 непересекающихся множеств T 1 , T 2 , …, T m , и каждое из этих множеств, в свою очередь, является деревом; деревья T 1 , T 2 , ..., T m называются поддеревьями данного корня.

Это определение является рекурсивным: дерево определено на основе понятия дерево. Рекурсивный характер деревьев можно наблюдать и в природе, например, почки молодых деревьев растут и со временем превращаются в ветви (поддеревья), на которых снова появляются почки, которые также растут и со временем превращаются в ветви (поддеревья) и т.д. Можно привести еще одно формальное определение дерева: Один узел является деревом. Этот же узел также является корнем этого дерева. Пусть n – это узел, а T 1 , T 2 , ... T m – деревья с корнями n 1 , n 2 , … n m соответственно. Можно построить новое дерево, сделав n родителем узлов n 1 , n 2 , … n m . В этом дереве n будет корнем, а T 1 , T 2 , ... T m – поддеревьями этого корня. Узлы n 1 , n 2 , … ,n m называются сыновьями узла n .

Из приведенных выше определений следует, что каждый узел дерева является корнем некоторого поддерева данного дерева. Количество поддеревьев узла называется степенью(degree) этого узла. Узел с нулевой степенью называется концевым узлом(terminal node) или листом(leaf). Неконцевой узел называется узлом ветвления( branch node). Каждый узел имеет уровень( level), который определяется следующим образом: уровень корня дерева равен нулю, а уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева, содержащего данный узел. Рассмотрим эти понятия на примере дерева с семью узлами (см. рисунок). Узлы часто изображаются буквами, они так же, как и элементы списков могут быть элементами любого типа.

Файл:Деревья_с_семью_узлами.png

Узел A является корнем, который имеет два поддерева { B } и { C , D , E , F , G }. Корнем дерева{ C , D , E , F , G } является узел C . Уровень узла C равен 1 по отношению ко всему дереву. Он имеет три поддерева { D }, { E }и { F , G }, поэтому степень узла C равна 3. Концевыми узлами (листьями) являются узлы B , D , E , G .

Если в п.б) данного выше определения имеет значение относительнгый порядок поддеревьев T 1 , T 2 , ... T m, то дерево является упорядоченным ( ordered tree).Если в упорядоченном дереве m>=2, то имеет смысл назвать поддерево Т2 вторым поддеревом данного корня и т.д. Упорядоченные деревья иногда также называются плоскими деревьями (plane treeы), поскольку при их упорядочении имеет значение способ размещения дерева на плоскости. Если не считать различными два дерева, которые отличаются только относительным порядком поддеревьев узлов, то дерево называется ориентированным ( oriented), поскольку при этом имеет значение только относительная ориентация узлов, а не их порядок. Сама природа представления данных в компьютере определяет неявный порядок любого дерева, поэтому в большинстве случаев упорядоченные деревья представляют наибольший интерес.

Лес( forest) – это множество (обычно упорядоченное), содержащее несколько непересекающихся деревьев. Узлы дерева при условии исключения корня образуют лес. Между абстрактными понятиями леса и деревьев существует не очень заметная разница. При удалении корня дерева получим лес, и наоборот: при добавлении одного узла в лес, все деревья которого рассматриваются как поддеревья нового узла, получим дерево.Поэтому понятия лес и дерево часто используются как равнозначные при работе со структурами данных.

Путем из узла n 1 в узел n k называется последовательность узлов n 1 , n 2 , … n k , где для всех i , 1< i <k , узел n i является родителем узла n i +1 . Длиной пути называется число, на единицу меньшее числа узлов, составляющего этот путь. Таким образом, путем нулевой длины будет путь из любого узла к самому себе. Например, на рисунке путем длины 2 будет путь от узла A к узлу F или от узла C к узлу G . Для рассмотрения деревьев необходимо создать описательную терминологию. Вместо двусмысленных формулировок лучше использовать общепринятые термины, которые применяются при работе с генеалогическими деревьями.Наиболее распространенные типы генеалогических деревьев- это родословная( показаны предки конкретного человека) и родовая схема( показаны наследники). Если существует путь из узла a в узел b , то в этом случае узел a называется предком узла b , а узел b – потомком узла a . Отметим, что любой узел одновременно является предком и потомком самого себя. Например, на рисунке предками узла G будут сам узел G и узлы F , C и A . Потомками узла C будут являться сам узел C и узлы D , T , F , G . В дереве только корень не имеет предков, а листья не имеют потомков.

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

Высотой узла дерева называется длина самого длинного пути от этого узла до какого-либо листа. Глубина узла определяется как длина пути от корня до этого узла.

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

Файл:Нов.png


а)- вложенные множества б)вложенные скобки в)список с отступами


Еще одно изображение дерева, соответствующего арифметическому выражению а-b(c/d+e/f):


Файл:А.png В свою очередь, лес можно рассматривать как особую структуру списка. Слово "Список" здесь применяется в очень специфическом смысле, и, чтобы подчеркнуть это, его пишут с прописной буквы. Рекурсивно Список определяется как конечная последовательность атомов или Списков, число которых может быть больше или равно нулю. здесь под словом "атом" подразумевается неопределенное понятие, которое может относиться к элементам любой совокупности объектов и которое можно отличить от Списка.С помощью обычной системы обозначений на основе запятых и скобок можно различать атомы и списки, а так же быстро и просто указывать упорядочение в пределах Списка. Рассмотрим список с 5 элементами L=(a,(b,a,b),(),c,(((2)))), в котором, сначала следует атом a, затем список (b,a,b), после, пустой Список (), атом с, и , наконец, Список(2). Последний Список состоит из списка ((2)), который включает список (2), который , в свою очередь, включает атом 2. Этому списку соответствует древовидная структура:


Файл:Список.png


Звездочки используются для обозначения Списков, чтобы их можно было отличить от атомов. Индексные обозначения могут применяться для Списков точно так , как и для леса, например L[2]=(b,a,b) и L[2,2]=a. Узлы-Списки на схеме не несут никакой другой полезной информации, помимо того , что они являются Списками. Для устранения этого недостатка их можно пометить символами, как было сделано выше для деревьев и других структур. Важное отличие между Списками и деревьями заключается в том, что Списки могут перекрываться( подсписки могут пересекаться) и даже быть рекурсивными(содержать самих себя)

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


Обход бинарных деревьев Существует достаточно много алгоритмов работы с древовидными структурами, в которых наиболее часто встречается понятие "обхода"(traversing) дерева или прохода по дереву. При таком методе исследования дерева каждый узел посещается в точности один раз, а полный обход дерева задает линейное упорядочение узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие "следующий" узел, т.е.узел, который располагается перед данным узлом в таком упорядочении или после него. Для обхода бинарного дерева можно применить один из трех принципиально разных способов: в прямом порядке(preorder); в центрированном порядке(inorder); в обратном порядке(postorder); Эти три метода определяются рекурсивно.Если бинарное дерево пусто, то для его "обхода" ничего делать не потребуется , в противном случае обход выполняется в три этапа.

Прямой порядок обхода Попасть в корень Пройти левое поддерево Пройти правое поддерево

Центрированный порядок обхода Пройти левое поддерево Попасть в корень Пройти правое поддерево

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

Сбалансированные деревья

Деревья оптимального поиска

Б-деревья

Деревья приоритетного поиска

Литература

1. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. - М.: Мир, 1989. - 360 с., ил. ISBN 5-03-001045-9

2. Кнут Д.Э. Искусство программирования

3. Иванова Г.С. Технология программирования

Просмотры
Инструменты

Besucherzahler russian mail order brides
счетчик посещений
Rambler's Top100
Лингафонные кабинеты  Интерактивные доски  Интерактивная приставка Mimio Teach