|
|
Структура и алгоритмы обработки данныхСодержание 1. Понятие алгоритма и структуры данных. 3 2. Анализ сложности и эффективности алгоритмов и структур данных. 3 3. Данные числовых типов. Данные целочисленного типа. Данные вещественного типа. 4 4. Данные числовых типов. Операции над данными числовых типов. Данные символьного типа. 5 5. Данные логического типа. Данные типа указатель. 6 6. Линейные структуры данных. Массив. 6 7. Линейные структуры данных. Строка. 7 8. Линейные структуры данных. Запись. 7 9. Линейные структуры данных. Множество. 8 10. Линейные структуры данных. Таблица. 8 11. Линейные структуры данных. Линейные списки. Циклические списки. 9 12. Линейные структуры данных. Разреженные матрицы. 9 13. Линейные структуры данных. Стек. 10 14. Линейные структуры данных. Очередь. 10 15. Линейные структуры данных. Дек. 11 16. Нелинейные структуры данных. Мультисписки. Слоенные списки. 11 17. Нелинейные структуры данных. Графы. Спецификация. 12 18. Нелинейные структуры данных. Графы. Реализация. 12 19. Нелинейные структуры данных. Деревья. Общие понятия. 12 20. Нелинейные структуры данных. Деревья. Обходы деревьев. 13 21. Нелинейные структуры данных. Деревья. Спецификация двоичных деревьев. Реализация. Основные операции. 13 22. Файлы. Организация. 14 23. Файлы. В-деревья. Представление файлов В-деревьями. 14 24. Файлы. В-деревья. Основные операции. 14 25. Файлы. В-деревья. Общая оценка В-деревьев. 15 26. NP-сложные и труднорешаемые задачи. 15 27. Методы разработки алгоритмов. Метод декомпозиции. Динамическое программирование. 16 28. Методы разработки алгоритмов. Поиск с возвратом. Методы ветвей и границ. 16 29. Алгоритмы поиска. Поиск в линейных структурах. 17 30. Алгоритмы поиска. Хеширование данных. 17 31. Алгоритмы поиска. Использование деревьев в задачах поиска. 18 32. Алгоритмы поиска. Поиск в тексте. 18 33. Алгоритмы кодирования (сжатия) данных. 19 34. Алгоритмы сортировки. Сортировка подсчетом. Сортировка простым включением. 20 35. Алгоритмы сортировки. Сортировка методом Шелла. Сортировка простым извлечением. 20 36. Алгоритмы сортировки. Древесная сортировка. Сортировка методом пузырька. 21 37. Алгоритмы сортировки. Быстрая сортировка (Хоара). Сортировка слиянием. 21 38. Алгоритмы сортировки. Сортировка распределением. Сравнение алгоритмов внутренней сортировки. 22 39. Алгоритмы обхода графа. Поиск в глубину. 23 40. Алгоритмы обхода графа. Поиск в ширину (волновой алгоритм). 23
1. Понятие алгоритма и структуры данных. Структуры данных и алгоритмы служат теми материалами, из которых строятся программы. Более того, сам компьютер состоит из структур данных и алгоритмов. Встроенные структуры данных представлены теми регистрами и словами памяти, где хранятся двоичные величины. Заложенные в конструкцию аппаратуры алгоритмы - это воплощенные в электронных логических цепях жесткие правила, по которым занесенные в память данные интерпретируются как команды, подлежащие исполнению. Поэтому в основе работы всякого компьютера лежит умение оперировать только с одним видом данных - с отдельными битами, или двоичными цифрами. Работает же с этими данными компьютер только в соответствии с неизменным набором алгоритмов, которые определяются системой команд центрального процессора. Задачи, которые решаются с помощью компьютера, редко выражаются на языке битов. Как правило, данные имеют форму чисел, литер, текстов, символов и более сложных структур типа последовательностей, списков и деревьев. Еще разнообразнее алгоритмы, применяемые для решения различных задач; фактически алгоритмов не меньше чем вычислительных задач. Для точного описания абстрактных структур данных и алгоритмов программ используются такие системы формальных обозначений, называемые языками программирования, в которых смысл всякого предложения определется точно и однозначно. Среди средств, представляемых почти всеми языками программирования, имеется возможность ссылаться на элемент данных, пользуясь присвоенным ему именем, или, иначе, идентификатором. Одни именованные величины являются константами, которые сохраняют постоянное значение в той части программы, где они определены, другие - переменными, которым с помощью оператора в программе может быть присвоено любое новое значение. Но до тех пор, пока программа не начала выполняться, их значение не определено. Первые алгоритмы были придуманы для решения численных задач типа умножения чисел, нахождения наибольшего общего делителя, вычисления тригонометрических функций и других. Сегодня в равной степени важны и нечисленные алгоритмы; они разработаны для таких задач, как, например, поиск в тексте заданного слова, планирование событий, сортировка данных в указанном порядке и т.п. Нечисленные алгоритмы оперируют с данными, которые не обязательно являются числами; более того, не нужны никакие глубокие математические понятия, чтобы их конструировать или понимать. Из этого, однако, вовсе не следует, что в изучении таких алгоритмов математике нет места; напротив, точные, математические методы необходимы при поиске наилучших решений нечисленных задач при доказательстве правильности этих решений. Структуры данных, применяемые в алгоритмах, могут быть чрезвычайно сложными. В результате выбор правильного представления данных часто служит ключом к удачному программированию и может в большей степени сказываться на производительности программы, чем детали используемого алгоритма. Вряд ли когда-нибудь появится общая теория выбора структур данных. Самое лучшее, что можно сделать,- это разобраться во всех базовых "кирпичиках" и в собранных из них структурах. Способность приложить эти знания к конструированию больших систем - это прежде всего дело инженерного мастерства и практики. 2. Анализ сложности и эффективности алгоритмов и структур данных. В процессе решения прикладных задач выбор подходящего алгоритма вызывает определенные трудности. Алгоритм должен удовлетворять следующим противоречащим друг другу требованиям: 1) быть простым для понимания, перевода в программный код и отладки; 2) эффективно использовать вычислительные ресурсы и выполняться по возможности быстро. Если разрабатываемая программа, реализующая некоторый алгоритм, должна выполняться только несколько раз, то первое требование наиболее важно. В этом случае стоимость программы оптимизируется по стоимости написания (а не выполнения) программы. Если решение задачи требует значительных вычислительных затрат, то стоимость выполнения программы может превысить стоимость написания программы, особенно если программа выполняется многократно. Поэтому более предпочтительным может стать сложный комплексный алгоритм (в надежде, что результирующая программа будет выполняться существенно быстрее). Таким образом, прежде чем принимать решение об использовании того или иного алгоритма, необходимо оценить сложность и эффективность этого алгоритма. Сложность алгоритма – это величина, отражающая порядок величины требуемого ресурса (времени или дополнительной памяти) в зависимости от размерности задачи. Самый простой способ оценки – экспериментальный, т. е. запрограммировать алгоритм и выполнить полученную программу на нескольких задачах, оценивая время выполнения программы. Однако этот способ имеет ряд недостатков. Во-первых, экспериментальное программирование – это, возможно, дорогостоящий процесс. Во-вторых, необходимо учитывать, что на время выполнения программ влияют следующие факторы: 1) временная сложность алгоритма программы; 2) качество скомпилированного кода исполняемой программы; 3) машинные инструкции, используемые для выполнения программы. Теоретическая оценка временной сложности алгоритма осуществляется с использованием следующих базовых принципов: 1) время выполнения операций присваивания, чтения, записи обычно имеют порядок O(1). Исключением являются операторы присваивания, в которых операнды представляют собой массивы или вызовы функций; 2) время выполнения последовательности операций совпадает с наибольшим временем выполнения операции в данной последовательности (правило сумм: если T1(n) имеет порядок O(f(n)), а T2(n) – порядок O(g(n)), то T1(n) + T2(n) имеет порядок O(max(f(n), g(n)) );
3) время выполнения конструкции ветвления (if-then-else) состоит из времени вычисления логического выражения (обычно имеет порядок O(1) ) и наибольшего из времени, необходимого для выполнения операций, исполняемых при истинном значении логического выражения и при ложном значении логического выражения; 4) время выполнения цикла состоит из времени вычисления условия прекращения цикла (обычно имеет порядок O(1) ) и произведения количества выполненных итераций цикла на наибольшее возможное время выполнения операций тела цикла. 5) время выполнения операции вызова процедур определяется как время выполнения вызываемой процедуры; 6) при наличии в алгоритме операции безусловного перехода, необходимо учитывать изменения последовательности операций, осуществляемых с использованием этих операции безусловного перехода. 3. Данные числовых типов. Данные целочисленного типа. Данные вещественного типа. С помощью целых чисел может быть представлено количество объектов, являющихся дискретными по своей природе (т. е. счетное число объектов). Диапазон возможных значений целых типов зависит от их внутреннего представления, которое может занимать 1, 2 или 4 байта. Перечень целых типов, размер памяти для их внутреннего представления в битах, диапазон возможных значений.
(Таблица) Тип /shortint/integer/longint/byte/word/comp/ Диапазон /-128...127/-32768...32767/-2147483648...2147483647/0...255/0...65535/-2^(63)+1...2^(63)-1/ Машинное представление /8 бит со знаком/16 бит со знаком/32 бита со знаком/8 бит без знака/16 бит без знака/64 бита со знаком/
В отличие от целочисленных типов, значения которых всегда представляются в памяти ЭВМ абсолютно точно, значение вещественных типов определяет число лишь с некоторой конечной точностью, зависящей от внутреннего формата вещественного числа. Суммарное количество байтов, диапазоны допустимых значений чисел вещественных типов, а также количество значащих цифр после запятой
(Таблица) Тип /real/single/double/extended/ Диапазон значений /2.9*10^(-39)...1.7-10^(38)/1.4*10^(-45)...3.4-10^(38)/4.9*10^(-324)...1.8-10^(308)/3.1*10^(-4944)...1.2*10^(4932) Значащие цифры /11-12/7-8/15-16/19-20/ Размер в байтах /6/4/8/10/ 4. Данные числовых типов. Операции над данными числовых типов. Данные символьного типа. Над числовыми типами, как и над всеми другими возможны прежде всего, четыре основных операции: создание, уничтожение, выбор, обновление. Специфическими операциями над числовыми типами являются арифметические операции: сложение, вычитание, умножение, деление. Операция возведения в степень в некоторых языках также является базовой и обозначается специальным символом или комбинацией символов, в других – выполняется встроенными функциями. Еще одна группа операций над числовыми типами – операции сравнения >, <, ≥, ≤, =, <>. Существенно, что хотя операндами этих операций являются данные числовых типов, результат их имеет логический тип – «истина» или «ложь». Говоря об операциях сравнения, следует обратить внимание на особенность выполнения сравнений на равенство/неравенство вещественных чисел. Поскольку эти числа представляются в памяти с некоторой (не абсолютной) точностью, сравнения их не всегда могут быть абсолютно достоверны. Поскольку одни и те же операции допустимы для разных числовых типов, возникает проблема арифметических выражений со смешением типов. В реальных задачах выражения со смешанными типами встречаются довольно часто. Поэтому большинство языков допускает выражения, операнды которых имеют разные числовые типы, но обрабатываются такие выражения в разных языках по-разному. В одних языках все операнды выражения приводятся к одному типу, а именно к типу той переменной, в которую будет записан результат, а затем уже выражение вычисляется. В других (например, язык Си) преобразование типов выполняется в процессе вычисления выражения, при выполнении каждой отдельной операции, без учета других операций; каждая операция вычисляется с точностью самого точного участвующего в ней операнда. Данные символьного типа Значением символьного типа char являются символы из некоторого предопределенного множества. В качестве примеров этих множеств можно назвать ASCII. Это множество состоит из 256 разных символов, упорядоченных определенным образом, и содержит символы заглавных и строчных букв, цифр и других символов, включая специальные управляющие символы. Значение символьного типа char занимает в памяти 1 байт. Код от 0 до 255 в этом байте задает один из 256 возможных символов ASCII таблицы. ASCII включает в себя буквенные символы только латинского алфавита. Символы национальных алфавитов занимают «свободные места» таблице кодов и, таким образом, одна таблица может поддерживать только один национальный алфавит. Специфические операции над символьными типами – только операции сравнения. При сравнении коды символов рассматриваются как целые числа без знака. Кодовые таблицы строятся так, что результаты сравнения подчиняются лексикографическим правилам: символы, занимающие в алфавите места с меньшими номерами, имеют меньшие коды, чем символы, занимающие места с большими номерами. 5. Данные логического типа. Данные типа указатель. Значениями логического типа может быть одна из предварительно объявленных констант false (ложь) или true (истина). Данные логического типа занимают один байт памяти. При этом значению false соответствует нулевое значение байта, а значению true любое ненулевое значение байта. Над логическими типами возможны операции булевой алгебры – НЕ (not), ИЛИ (or), И (and), ИСКЛЮЧАЮЩЕЕ ИЛИ (xor). Последняя операция реализована для логического типа не во всех языках. Кроме того, следует помнить, что результаты логического типа получаются при сравнении данных любых типов. Данные типа указатель Тип указателя представляет собой адрес ячейки памяти. Физическое представление адреса существенно зависит от аппаратной архитектуры вычислительной системы. В языках программирования высокого уровня определена специальная константа nil, которая означает пустой указатель или указатель, не содержащий какой-либо конкретный адрес. В языках высокого уровня указатели могут быть типизированными и нетипизированными. При объявлении т и п и з и р о в а н н о г о указателя определяется и тип данного в памяти, адресуемого этим указателем. Н е т и п и з и р о в а н н ы й указатель служит для представления адреса, по которому содержатся данные неизвестного типа. В Паскале это тип pointer. Работа с нетипизированными указателями существенно ограничена, они могут использоваться только для сохранения адреса, а обращение по адресу, задаваемому нетипизированным указателем, невозможно. Основными операциями, в которых участвуют указатели, являются присваивание, получение адреса, выборка. Присваивание является двухместной операцией, оба операнда которой указатели. Как и для других типов, операция присваивания копирует значение одного указателя в другой, в результате оба указателя будут содержать один и тот же адрес памяти. Если оба указателя, участвующие в операции присваивания типизированные, то оба они должны указывать на данные одного и того же типа. Операция получения адреса – одноместная, ее операнд может иметь любой тип. Результатом является типизированный указатель, содержащий адрес операнда. Операция выборки – одноместная, ее операндом является типизированный указатель. Результатом этой операции являются данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя. 6. Линейные структуры данных. Массив. Массив – это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющих положение элемента в массиве. Тип индекса, в общем случае, может быть любым порядковым, но некоторые языки программирования поддерживают в качестве индексов массивов только последовательности целых чисел. Количество используемых индексов определяет размерность массива. Массив может быть одномерным (вектор), двумерным (матрица), трехмерным (куб) и т. д.: var Vector: array [1..100] of integer; Matrix: array [1..100, 1..100] of integer; Cube: array [1..100, 1..100, 1..100] of integer; Можно также выполнять операции над отдельными элементами массива. Перечень таких операций определяется типом элементов. Доступ к отдельным элементам массива осуществляется через имя массива и индекс (индексы) элемента: Cube[0,0,10] := 25; Matrix[10,30] := Cube[0,0,10] + 1; В памяти ЭВМ элементы массива обычно располагаются непрерывно, в соседних ячейках. Размер памяти, занимаемой массивом, есть суммарный размер элементов массива. 7. Линейные структуры данных. Строка. Строка – это последовательность символов (элементов символьного типа).В Паскале количество символов в строке (длина строки) может динамически меняться от 0 до 255. Рассмотрим пример описания строк: var TTxt: string; TWrd: string[120]; Здесь описаны строка TTxt, максимальная длина которой 255 символов (по умолчанию) и строка TWrd, максимальная длина которой ограничена 120 символами. Каждый символ строки имеет свой индекс, принимающий значение от 1 до заданной длины строки. Следует обратить внимание, что существует элемент строки с индексом 0, который не доступен с использованием индекса, и содержит текущее количество символов в строке. Доступ к этому специфическому элементу можно получить только с помощью специальных функций языка. Благодаря индексам, строки очень похожи на одномерные массивы символов, и доступ к отдельным элементам строки можно получать с использованием этих индексов, выполняя операции, определенные для символьного типа данных. Так же как и для массивов, определена операция присвоения строк в целом. Однако есть ряд отличий. Операций сравнения строк больше, чем аналогичных операций для массивов: <, >, ≥, ≤, =, <>. Существует операция сцепления (конкатенации) строк «+». В памяти ЭВМ символы строки располагаются непрерывно, в соседних ячейках. Размер памяти, занимаемой строкой, есть суммарный размер элементов массива (включая элемент, содержащий длину строки). 8. Линейные структуры данных. Запись. Запись – это агрегат, составляющие которого (поля) имеют имя и могут быть различного типа. Пример простейшей записи: type TPerson = record Name: string; Address: string; Index: longint; end; var Person1: TPerson; Запись описанного типа объединяет три поля. Первые два из них символьного типа, а третье – целочисленного. Можно также выполнять операции над отдельным полем записи. Перечень таких операций определяется типом поля. Доступ к полям отдельной записи осуществляется через имя записи и имя поля: Person1.Index := 190000; Person1.Name := ‘Иванов’; Person1.Adress := ‘Альметьевск, ул. Чехова, д.3’; В памяти ЭВМ поля записи обычно располагаются непрерывно, в соседних ячейках. Размер памяти, занимаемой записью, есть суммарный размер полей, составляющих запись. 9. Линейные структуры данных. Множество. Существует еще один структурированный тип – множество. Этот тип используется не так часто. Множество – совокупность каких-либо однородных элементов, объединенных общим признаком и представляемых как единое целое. Тип множество соответствует математическому понятию множества в смысле операций, которые допускаются над структурами такого типа. Множество допускает операции объединения множеств «+», пересечения множеств «*», разности множеств «–» и проверки элемента на принадлежность к множеству «in». Множества, так же как и массивы, объединяют однотипные элементы. Поэтому в описании множества обязательно должен быть указан тип его элементов: var RGB, YIQ, CMY: set of char; Здесь приведено описание трех множеств, элементами которых являются символы. Кроме того, определены операции сравнения множеств: ≥, ≤, =, <>. В отличие от массивов и записей здесь отсутствует возможность обращения к отдельным элементам. Операции выполняются по отношению ко всей совокупности элементов множества: CMY := [‘M’, ’C’, ’Y’]; RGB := [‘R’, ’G’, ’B’]; YIQ := [‘Y’, ’Q’, ’I’]; Writeln(‘Пересечение цветовых систем RGB и CMY ’, RGB*CMY); Writeln(‘Пересечение цветовых систем YIQ и CMY ’, YIQ*CMY); В Паскале в качестве типов элементов множества могут использоваться типы, максимальное количество значений которых не превышает 256. В памяти ЭВМ элементы множества обычно располагаются непрерывно, в соседних ячейках. 10. Линейные структуры данных. Таблица. Таблица представляет собой одномерный массив (вектор), элементами которого являются записи. Отдельная запись массива называется строкой таблицы. Чаще всего используется простая запись, т. е. поля – элементарные данные. Совокупность одноименных полей всех строк называется столбцом, а конкретное поле отдельной строки – ячейкой. Характерной особенностью таблиц является то, что доступ к элементам таблицы производится не по индексу, а по ключу, т. е. по значению одного из полей записи. Ключ таблицы (основной, первичный) – поле, значение которого может быть использовано для однозначной идентификации каждой записи таблицы. Ключ таблицы может быть составным – образовываться не одним, а несколькими полями данной таблицы. Вторичный ключ – поле таблицы с несколькими ключами, не обеспечивающий (в отличие от первичного ключа) однозначной идентификации записей таблицы. В этот ключ могут входить все поля таблицы за исключением полей, составляющих первичный ключ. Если последовательность записей упорядочена относительно какого-либо столбца (поля), то такая таблица называется упорядоченной, иначе – таблица неупорядоченная. Основной операцией при работе с таблицами является операция доступа к записи по ключу. Она реализуется процедурой поиска. Получив доступ к конкретной записи (строке таблицы), с ней можно работать как с записью в целом, так и с отдельными полями (ячейками). В памяти ЭВМ ячейки таблицы обычно располагаются построчно, непрерывно, в соседних ячейках. Размер памяти, занимаемой таблицей, есть суммарный размер ячеек. 11. Линейные структуры данных. Линейные списки. Циклические списки. Список – это структура данных, представляющая собой логически связанную последовательность элементов списка. Наиболее простой способ организовать структуру данных, состоящее из некоторого множества элементов – это организовать линейный список. При такой организации элементы некоторого типа образуют цепочку. Для связывания элементов в списке используют систему указателей, и в зависимости от их количества в элементах различают однонаправленные и двунаправленные линейные списки. (РИСУНОК1) Циклические списки Линейные списки характерны тем, что в них можно выделить первый и последний элементы, причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент. Это приводило к тому, что алгоритмы вставки и удаления крайних и средних элементов списка отличались друг от друга, что, естественно, усложняло соответствующие операции. Основное отличие циклического списка состоит в том, что в этом списке нет элементов, содержащих пустые указатели, и, следовательно, нельзя выделить крайние элементы. Таким образом, все элементы являются «средними». Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными. (РИСУНОК2 и др) 12. Линейные структуры данных. Разреженные матрицы. Разреженная матрица – двухмерный массив, большинство элементов которого равны между собой, так что хранить в памяти достаточно лишь небольшое число значений, отличных от основного (фонового) значения остальных элементов. Различают два типа разреженных матриц: 1) матрицы, в которых местоположения элементов со значениями, отличными от фонового, могут быть математически описаны; 2) матрицы со случайным расположением элементов. 1. Матрицы с математическим описанием местоположения элементов К данному типу матриц относятся матрицы, у которых местоположение элементов со значениями, отличными от фонового, может быть математически описано, т. е. в их расположении есть какая-либо закономерность. Элементы, значения которых являются фоновыми, называют нулевыми, а элементы, значения которых отличны от фонового, называют ненулевыми. Но необходимо помнить, что фоновое значение не всегда равно нулю. 2. Матрицы со случайным расположением элементов К данному типу относятся матрицы, у которых местоположение элементов со значениями, отличными от фонового, не могут быть математически описано, т. е. в их расположении нет какой-либо закономерности. Один из основных способов хранения подобных разреженных матриц заключается в запоминании ненулевых элементов в одномерном массиве записей с идентификацией каждого элемента массива индексами строки и столбца матрицы Такой способ хранения называется последовательным представлением разреженных матриц. 13. Линейные структуры данных. Стек. Стек – это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала. Здесь используется принцип «последним пришел – первым вышел» (LIFO: Last Input – First Output). Стек можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде линейного списка. При реализации стека в виде статического массива необходимо резервировать массив, длина которого равна максимально возможной глубине стека, что приводит к неэффективному использованию памяти. Однако работать с такой реализацией проще и быстрее. Стек как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа всегда идет с заголовком стека, т. е. не требуется осуществлять просмотр элементов, удаление и вставку элементов в середину или конец списка, то достаточно использовать экономичный по памяти линейный однонаправленный список. Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует и указатель принимает значение nil. Поскольку стек, по своей сути, является структурой с изменяемым количеством элементов, то основное внимание уделим динамической реализации стека. Как уже говорилось выше, для такой реализации целесообразно использовать линейный однонаправленный список. Описание элементов стека аналогично описанию элементов линейного однонаправленного списка, где DataType является типом элементов стека. Поэтому здесь приводить его не будем. Основные операции, производимые со стеком: записать (положить в стек); прочитать (снять со стека); очистить стек; проверка пустоты стека. 14. Линейные структуры данных. Очередь. Очередь – это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Каждый новый элемент размещается в конце очереди; элемент, стоящий в начале очереди, выбирается из нее первым. Здесь используется принцип «первым пришел – первым вышел» (FIFO: First Input – First Output). Очередь можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде линейного списка. При реализации очереди в виде статического массива необходимо резервировать массив, длина которого равна максимально возможной длине очереди, что приводит к неэффективному использованию памяти. Элементы очереди располагаются в «круге» элементов массива в последовательных позициях, конец очереди находится по часовой стрелке на некотором расстоянии от начала. При этом необходимо отдельно хранить значение индекса элемента массива, являющегося началом очереди, и значение индекса элемента массива, являющегося концом очереди. Когда происходит добавление в конец или извлечение из начала очереди, осуществляется смещение значений этих двух индексов по часовой стрелке. Очередь как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа идет с обоими концами очереди, то предпочтительно будет использовать линейный двунаправленный список. Основные операции, производимые с очередью: – добавить элемент; – извлечь элемент; – очистить очередь; – проверка пустоты очереди. 15. Линейные структуры данных. Дек. Дек – это структура данных, представляющая собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с двух сторон. Первый и последний элементы дека соответствуют входу и выходу дека. Выделяют ограниченные деки: – дек с ограниченным входом – из конца дека можно только извлекать элементы; – дек с ограниченным выходом – в конец дека можно только добавлять элементы. Дек также можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде линейного списка Описание элементов дека аналогично описанию элементов линейного двунаправленного списка, где DataType является типом элементов дека. Основные операции, производимые с деком: – добавить элемент в начало; – добавить элемент в конец; – извлечь элемент из начала; – извлечь элемент из конца; – очистить дек; – проверка пустоты дека. 16. Нелинейные структуры данных. Мультисписки. Слоенные списки. Мультисписок – это структура данных, состоящая из элементов, содержащих такое число указателей, которое позволяет организовать их одновременно в виде нескольких различных списков. В элементах мультисписка важно различать поля указателей для разных списков, чтобы можно было проследить элементы одного списка, не вступая в противоречие с указателями другого списка. При использовании традиционных списков для представления повторяющихся данных происходит нерациональное использование памяти за счет дублирования динамических элементов, хранящих повторяющиеся данные. Использование мультисписков позволяет устранить этот недостаток. Поиск в мультисписке происходит аналогично поиску в линейном списке, но при этом используется только один указатель, соответствующий списку, в котором осуществляется поиск. Добавление элемента, принадлежащего только одному из списков, осуществляется аналогично добавлению в линейный список, за исключением того, что поля указателей, относящиеся к другим спискам, устанавливаются в nil. Алгоритм выполнения такой операции сильно зависит от количества списков и места вставки нового элемента. Слоеные списки Слоеные (skip), или разделенные, списки – это связные списки, которые позволяют перескакивать через некоторое количество элементов. Идея, лежащая в основе слоеных списков, очень напоминает метод, используемый при поиске имен в адресной книжке. Чтобы найти имя, ищут страницу, помеченную буквой, с которой начинается имя, а затем поиск осуществляют в пределах этой страницы. В отличие от элементов обычных линейных списков, элементы этих списков имеют дополнительный указатель. Все элементы списка группируются по определенному признаку, и первый элемент каждой группы содержит указатель на первый элемент следующей группы. Если следующая группа отсутствует или элемент не является первым в группе, то этот дополнительный указатель принимает значение nil. Эта простая идея может быть расширена – можно добавлять нужное число дополнительных указателей, группируя группы элементов и т. д. на нужном количестве уровней. 17. Нелинейные структуры данных. Графы. Спецификация. Граф G – это упорядоченная пара (V, E), где V – непустое множество вершин, E – множество парлементов множества V, называемое множеством ребер. Упорядоченная пара элементов из V называется дугой. Если все пары в Е упорядочены, то граф называется о р и е н т и р о в а н н ы м (орграфом). Если дуга e ведет от вершины v1 к вершине v2, то говорят, что дуга e инцидентна вершине v2, а вершина v2 являются смежной вершине v1. В случае неориентированного графа ребро e является инцидентной обеим вершинам v1 и v2, а сами вершины – взаимно смежными. Путь – это любая последовательность вершин орграфа такая, что в этой последовательности вершина b может следовать за вершиной a, только если существует дуга, следующая из a в b. Аналогично можно определить путь, состоящий из дуг. Путь, начинающийся и заканчивающийся в одной и той же вершине, называется циклом. Граф, в котором отсутствуют циклы, называется ациклическим. Петля – дуга, соединяющая некоторую вершину сама с собой. Теория графов является важной частью вычислительной математики. С помощью этой теории решаются большое количество задач из различных областей. Граф состоит из множества вершин и множества ребер, которые соединяют между собой вершины. Вершинами могут быть населенные пункты, а ребрами дороги, соединяющие их, или вершинами являться подпрограммы, а соединение вершин ребрами означает взаимодействие подпрограмм. Часто имеет значение направление дуги в графе. 18. Нелинейные структуры данных. Графы. Реализация. Выбор структуры данных для хранения графа в памяти имеет принципиальное значение при разработке эффективных алгоритмов. Существуют два матричных и три списочных представления графа: – Матрица смежности – это двумерный массив размером n×n. Пространственная сложность этого способа V(n)~O(n2). Способ очень хорош, когда надо часто проверять смежность или находить вес ребра по двум заданным вершинам. – Матрица инцидентности – это двумерный массив размером n×m. Пространственная сложность этого способа V(n, m)~O(n×m). Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x». – Списки смежных вершин – это одномерный массив размером n, содержащий для каждой вершины указатели на списки смежных с ней вершин. Пространственная сложность этого способа Vmax(n)~O(n2). Этот способ хранения лучше всех других подходит для операции «перечисление всех вершин, смежных с x». – Список ребер – это одномерный массив размером m, содержащий список пар вершин, инцидентных с одним ребром графа. Пространственная сложность этого способа V(m)~O(m). Этот способ хранения графа особенно удобен, если главная операция, которой чаще всего выполняется, это перечисление ребер или нахождение вершин и ребер, находящихся в отношениях инцидентности. – Списки вершин и ребер. Каждое ребро и каждая вершина имеют вес – целое положительное число. Если граф не является помеченным, то считается, что вес равен единице. 19. Нелинейные структуры данных. Деревья. Общие понятия. Деревом называется орграф, для которого: 1) существует узел, в который не входит ни одной дуги (корень); 2) в каждую вершину, кроме корня, входит одна дуга. Вершины дерева подразделяют на следующие три группы: – корень – вершина, в которую не входит ни одной дуги; – узлы – вершины, в которые входит одна дуга и выходит одна или более дуг; – листья – вершины, в которые входит одна дуга и не выходит ни одной дуги. Все вершины, в которые входят дуги, исходящей из одной вершины, называются потомками этой вершины, а сама вершина – предком. Корень не имеет предка, а листья не имеют потомков. Выделяют уровни дерева. На первом уровне дерева может быть только одна вершина – корень, на втором – потомки корня, на третьем – потомки потомков корня и т. д. Поддеревом называется вершина со всеми ее потомками. 
Не нашли, что искали? Воспользуйтесь поиском по сайту: ©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|