Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

9.Какова структура записи?
10.К каким структурам данных относятся очереди и стеки ?
11.Каково правило выборки элемента из стека ?
12.Какая операция  читает верхний элемент стека без его удаления ?
13.Какую дисциплину обслуживания принято называть FIFO, а какую — LIFO ?
14.Признак заполнения кольцевой очереди ?
15.Признак пустой очереди ?
16.Что называется списком?
17.Перечислите виды списков.
18.Назовите элементы очереди.
19.Как организуется кольцевая очередь?
20.Какова особенность деков?

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

До сих пор мы рассматривали только статические программные объекты. Однако использование при программировании только статических объектов может вызвать определенные трудности, особенно с точки зрения получения эффективной машинной программы. Дело в том, что иногда мы заранее не знаем не только размера значения того или иного программного объекта, но также и того, будет ли существовать этот объект или нет. Такого рода программные объекты, которые возникают уже в процессе выполнения программы или размер значений которых определяется при выполнении программы, называются динамическими объектами.
Динамические структуры данных имеют 2 особенности:
1) Заранее не определено количество элементов в структуре.
2) Элементы динамических структур не имеют жесткой линейной упорядоченности. Они могут быть разбросаны по памяти.
Чтобы связать элементы динамических структур между собой в состав элементов помимо информационных полей входят поля указателей (рис. 3.1) (связок с другими элементами структуры).

P1 и P2 это указатели, содержащие адреса элементов, с которыми они связаны. Указатели содержат номер слота.

3.1  Связные  списки

Наиболее распространенными динамическими структурами являются связанные списки. С точки зрения логического представления различают линейные и нелинейные списки.
В линейных списках связи строго упорядочены: указатель предыдущего элемента содержит адрес последующего элемента или наоборот.
К линейным спискам относятся односвязные и двусвязные списки. К нелинейным — многосвязные.
Элемент списка в общем случае представляет собой поле записи и одного или нескольких указателей.

3.1.1  Односвязные  списки
Элемент односвязного списка содержит два поля (рис. 3.2): информационное поле (INFO) и поле указателя (PTR).

Особенностью указателя является то, что он дает только адрес последующего элемента списка. Поле указателя последнего элемента в списке является пустым (NIL). LST — указатель на начало списка. Список может быть пустым, тогда LST будет равен NIL.
Доступ к элементу списка осуществляется только от его начала, то есть обратной связи в этом списке нет.

3.1.2  Кольцевой  односвязный  список

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

Простейшие операции, производимые над односвязными списками

1) Вставка в начало односвязного списка.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники