Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Ответы на ГОС экзамены по дисциплине Структуры и алгоритмы обработки данных - файл 1.doc


Ответы на ГОС экзамены по дисциплине Структуры и алгоритмы обработки данных
скачать (161.5 kb.)

Доступные файлы (1):

1.doc162kb.16.11.2011 04:35скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
  1. Структуры и алгоритмы обработки данных


  1. Полустатические структуры данных. Реализация основных операций работы со стеками и очередями.


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


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


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


Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришел - первым исключается"). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.


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


Полезными могут быть также вспомогательные операции:

  • определение текущего числа элементов в стеке;

  • очистка стека;

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


x:=pop(stack); push(stack,x).


Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению.


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

а). пустого;

б-г). после последовательного включения в него элементов с именами 'A', 'B', 'C';

д, е). после последовательного удаления из стека элементов 'C' и 'B';

ж). после включения в стек элемента 'D'.



Рис 1. Включение и исключение элементов из стека.


Как видно из рис. 1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D... Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.


Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается"). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO.


Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение.


Дек – двусторонняя очередь, т.е. и добавление и удаление осуществляется с обеих сторон.


Представление на файле этих АТД имеет такой же характер и «преимущества» как и у стека, т.е. переписывание файла происходит во всех случаях кроме добавления компоненты в его конец.


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


Реализация на динамической структуре использует ту же особенность (цикличность) и лучше всего представляется в виде кольцевого двунаправленного списка.



  1. Динамические структуры данных. Односвязные и двусвязные списки: операции над ними. Мультисписки.


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

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

    • поле связок, в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры;


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


Достоинства связного представления данных - в возможности обеспечения значительной изменчивости структур;

  • размер структуры ограничивается только доступным объемом машинной памяти;

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


Вместе с тем связное представление не лишено и недостатков, основные из которых:

  • работа с указателями требует, как правило, более высокой квалификации от программиста;

  • на поля связок расходуется дополнительная память;

  • доступ к элементам связной структуры может быть менее эффективным по времени.


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


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

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


На рис. 2 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.



^ Рис.2. Структура односвязного списка


Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рис. 3, где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil, как и показано на рис. 3.


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



Рис. 3. Структура двухсвязного списка


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


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



^ Рис. 4. Структура кольцевого двухсвязного списка


Операции над списками.

Перебор элементов списка.


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

Из текущего эл-та выбирается указатель на следующий эл-т и для следующей итерации следующий эл-т становится текущим; если текущий эл-т был последний, то его поле next содержит пустой указатель и, т.обр. в cur запишется nil, что приведет к выходу из цикла.

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

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


^ Вставка элемента в список.


Вставка элемента в середину односвязного списка показана на рис.5



Рис. 5. Вставка элемента в середину 1-связного списка


Рисунок 6 представляет вставку в двухсвязный список.



Рис. 6 Вставка элемента в середину 2-связного списка


Удаление элемента из списка.


Удаление элемента из односвязного списка показано на рис. 7.



Рис. 7. Удаление элемента из 1-связного списка


Удаление элемента из двухсвязного списка требует коррекции большего числа указателей, как показано на рис. 8.



^ Рис. 8. Удаление элемента из 2-связного списка


Перестановка элементов списка.

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



Рис. 9. Перестановка соседних элементов 1-связного списка



  1. Структура данных «дерево». Виды деревьев. Реализация основных операций над бинарными деревьями.


Дерево - это граф, который характеризуется следующими свойствами:

1. Существует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется КОРНЕМ (рис. 6.8, 6.9 - A,G,M - корни).

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

3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

Название "дерево" проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется обычно ВЕТВЬЮ. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются ЛИСТЬЯМИ (или терминальными вершинами)(рис. 6.8, 6.9 - b,k,l,h - листья). Узел, не являющийся листом или корнем, считается промежуточным или узлом ветвления (нетерминальной или внутренней вершиной).

рис. 6.8. Дерево рис. 6.9.


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


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


Эти подмножества называются левым и правым поддеревьями исходного дерева.


Каждый элемент бинарного дерева называется узлом дерева.



Два узла являются братьями, если они сыновья одного и того же отца.

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

Свойство 1. Строго бинарное дерево с n листами всегда содержит 2n-1 узлов.


Над бинарным деревом есть операция - его прохождение, т.е. нужно обойти все дерево, отметив каждый узел один раз.


^ Над деревьями определены следующие основные операции:

1) Поиск узла с заданным ключом

2) Добавление нового узла

3) Удаление узла ( поддерева )

4) Обход дерева в определенном порядке.


Существует 3 способа обхода бинарного дерева.

  • в прямом порядке

  • в симметричном порядке

  • в обратном порядке


В прямом порядке:

  • Попасть в корень

  • Пройти в прямом порядке левое поддерево

  • Пройти в прямом порядке правое поддерево


В симметричном порядке:

  • Пройти в симметричном порядке левое поддерево

  • Попасть в корень

  • Пройти в симметричном порядке правое поддерево


В обратном порядке:

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

  • Пройти в обратном порядке правое поддерево

  • Попасть в корень




  1. Бинарные деревья выражений. Алгоритм вычисления значения выражения в обратной польской записи.


Дано выражение а*(-b)+с/d

Операции выполняются над выражениями, представленными в виде бинарных деревьев. Такие выражения можно символьно складывать,



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

(-) - операция унарного минуса;

() - операция возведения в степень;

(+) - операция сложения;

(*) - операция умножения;

(/) - операция деления.

(Е) - указательная переменная, адресующая корень дерева, каждая вершина которого состоит из левого указателя (LPТR), правого указателя (RPTR) и информационного поля TYPE.




Рис.6.33 Таблица символов


Последовательность напечатанных символов, +АВ называется префиксной формой арифметического выражения; знак операции (+) предшествует операндам А и В.

Более привычная форма арифметического выражения (А+В) называется инфиксной формой; она получается при прохождении дерева в обратном порядке , обозначаемом LTR.

Постфиксная форма арифметического выражения — в которой знак операции следует за операндами, например АВ+, получается при концевом порядке (LRT) прохождения дерева.


^ Обратная польская запись (постфиксная форма)форма записи математических выражений, в которой операнды расположены перед знаками операций.




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

  • Запись набора операций состоит из последовательности операндов и знаков операций. Операнды в выражении при письменной записи разделяются пробелами.

  • Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу.

  • Результатом вычисления выражения становится результат последней вычисленной операции.


Например, рассмотрим вычисление выражения 7 2 3 * - (эквивалентное выражение в инфиксной нотации: 7-2*3).

    1. Первый по порядку знак операции - «*», поэтому первой выполняется операция умножения над операндами 2 и 3 (они стоят последними перед знаком). Выражение при этом преобразуется к виду 7 6 - (результат умножения — 6, — заменяет тройку «2 3 *»).

    2. Второй знак операции — «-». Выполняется операция вычитания над операндами 7 и 6.

    3. Вычисление закончено. Результат последней операции равен 1, это и есть результат вычисления выражения.


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


Особенности обратной польской записи следующие:

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

  • В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций. Так, в инфиксной записи выражение 5 * (-3 + 8) использует знак «минус» как символ унарной операции (изменение знака числа), а выражение (10 - 15) * 3 применяет этот же знак для обозначения бинарной операции (вычитание). Конкретная операция определяется тем, в какой позиции находится знак. Обратная польская запись не позволяет этого: запись 5 3 - 8 + * (условный аналог первого выражения) будет интерпретирована как ошибочная, поскольку невозможно определить, что «минус» после 5 и 3 обозначает не вычитание; в результате будет сделана попытка вычислить сначала 5 - 3, затем 2 + 8, после чего выяснится, что для операции умножения не хватает операндов. Чтобы всё же записать это выражение, придётся либо переформулировать его, либо ввести для операции изменения знака отдельное обозначение, например, «±»: 5 3 ± 8 + *.

  • Так же, как и в инфиксной нотации, в ОПН одно и то же вычисление может быть записано в нескольких разных вариантах. Например, выражение (10 - 15) * 3 в ОПН можно записать как 10 15 - 3 *, а можно — как 3 10 15 - *

  • Из-за отсутствия скобок обратная польская запись короче инфиксной. За этот счёт при вычислениях на калькуляторах повышается скорость работы оператора (уменьшается количество нажимаемых клавиш), а в программируемых устройствах сокращается объём тех частей программы, которые описывают вычисления. Последнее может быть немаловажно для портативных и встроенных вычислительных устройств, имеющих жёсткие ограничения на объём памяти.




  1. Применение бинарных деревьев для кодирования информации: алгоритм Хаффмана.




  1. Сущность и сравнительные характеристики основных алгоритмов поиска данных.




  1. Понятие хеширования данных. Методы разрешения коллизий при хешировании.




  1. Общее понятие эффективности алгоритма. О-сложность алгоритмов.




  1. Сортировка данных. Строгие и улучшенные методы сортировки: сущность и сравнительные характеристики.




  1. Структура данных «граф». Алгоритмы на графах: обходы графа, поиск кратчайших путей, нахождение каркасов.



Скачать файл (161.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации