Методические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "




НазваниеМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
страница1/19
Дата публикации28.09.2013
Размер1.39 Mb.
ТипМетодические указания
vbibl.ru > Информатика > Методические указания
  1   2   3   4   5   6   7   8   9   ...   19


ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра прикладной математики и информатики

МЕТОДИЧЕСКИЕ УКАЗАНИЯ И ЗАДАНИЯ

К ЛАБОРАТОРНЫМ РАБОТАМ ПО КУРСУ

"АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ "
( направление подготовки 6.050103 ”Программная инженерия”)


Донецк 2009

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра прикладной математики и информатики


МЕТОДИЧЕСКИЕ УКАЗАНИЯ И ЗАДАНИЯ

К ЛАБОРАТОРНЫМ РАБОТАМ ПО КУРСУ

^ "АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ "
( направление подготовки 6.050103 ”Программная инженерия”)
Рассмотрено на заседании кафедры

Прикладной математики и информатики

Протокол № от
Утверждено на заседании

учебно- издательского совета ДонНТУ

протокол № от

Донецк 2009

УДК 518.551071
Методические указания и задания к лабораторным работам по курсу "Алгоритмы и структуры данных" (направление подготовки 6.050103 ”Программная инженерия”). Сост. Г.Г.Шалдырван, Н.С.Костюкова. – Донецк, 2009. – 114 с.
Излагаются вопросы, связанные с теоретическими основами структур данных, способами представления данных в оперативной памяти компьютера, методами обработки различных структур данных. Приведены описания алгоритмов и процедур обработки таблиц, списковых структур, деревьев.

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

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

Составители: доц. Г.Г. Шалдырван

доц. Н.С. Костюкова
ВВЕДЕНИЕ
Люди издавна обрабатывали данные о своей деятельности. Использовались различные способы отображения реального мира: рисунки, эскизы, фотографии, математические законы, формулы, числовые представления и другие. Первые исследователи окружающего мира не задумывались над понятием ''данные'' и над их общими структурами. С появлением компьютеров, с момента использования их для решения задач возникла необходимость структурировать данные с тем, чтобы компьютер мог их обрабатывать.
На ранних этапах развития вычислительной техники компьютеры использовались для решения научно-технических задач, в которых обрабатывались небольшие объемы информации. Структурами таких данных были простые (одиночные) переменные и прямоугольные массивы. С усложнением логики задач этих структур было уже недостаточно: появились структурированные данные, такие, как строки, стеки, очереди, списки, деревья, графы.

Решение экономических задач и задач управления, требующих обработки больших объемов информации, привело к организации данных в виде файлов. Первоначально использовались самые простые файлы – последовательные. Организацию доступа к файлу и программы ведения файла разрабатывал сам программист. Каждый программист составлял свой файл данных, даже если над одной проблемой работало несколько человек.
Создание эффективных внешних запоминающих устройств с прямым доступом (магнитные диски) привело к разработке более удобных структур файлов: индексно-последовательных и с прямым доступом. Были разработаны средства управления файлами, реализованные в операционных системах.

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

Простые

данные

Структурирован-ные данные

Файлы простые

Файлы сложные

БД


^


КЛАССИФИКАЦИЯ СТРУКТУР ДАННЫХ



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

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

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

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

Исходной проблемой при решении конкретной задачи является выбор наиболее подходящей структуры данных и способа ее отображения в памяти. В научно – технических задачах широко используются прямоугольные структуры; при разработке компиляторов и операционных систем используются таблицы, очереди, стеки, деревья. Обработка экономических и статистических данных с помощью компьютера обусловила применение таблиц и списковых структур. Решение информационно-поисковых задач повлекло использование таблиц, деревьев, графов.
Таким образом, при решении задачи в первую очередь нужно выполнить следующие действия:

  • определить структуры данных (входных, промежуточных, выходных);

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

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



^

Структура оперативной памяти



Различные абстрактные структуры данных отображаются в памяти компьютера на разные структуры хранения. Набор структур хранения (структур памяти) весьма ограничен. Базовой структурой оперативной памяти (ОП) является упорядоченная последовательность байт (байт – это наименьший адресуемый элемент памяти). Более сложные структуры памяти надстраиваются над базовой. Основными среди них являются векторы и списки.
Вектор – это множество элементов ОП, которые физически расположены рядом (например, последовательность подряд идущих байт). Адрес первого элемента является базовым адресом вектора. Адрес k-го элемента вектора может быть определен по формуле:



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

Связная память (динамически распределяемая область памяти) поддерживается современными системами программирования Паскаль и Си.

^

ЛАБОРАТОРНАЯ РАБОТА 1

МЕТОДЫ СОРТИРОВКИ ПОСТОЯННЫХ ТАБЛИЦ И ПОИСКА В ТАБЛИЦАХ


Цель работы: ознакомление с различными методами сортировки таблиц и методами поиска в упорядоченных таблицах.
^ МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ

Классификация таблиц

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

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

На логическом уровне таблица представляется, например, так:

Name

Capital

Area

Population

Россия

Москва

225110

2400000

Украина

Киев

15630

400000

. . .

. . .

. . .

. . .


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



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

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

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

Среднее количество операций сравнения и перестановок зависит от метода сортировки и связано с n – размером таблицы (размер таблицы – это количество содержащихся в ней записей).
^ Методы сортировки таблиц

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

С точки зрения экономичности использования памяти методы внутренней сортировки можно разделить на две группы:

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

  • методы, требующие для проведения сортировки дополнительного объема памяти (двухпутевая вставка, методы слияния).

В зависимости от характерных особенностей процесса сортировки методы можно разбить на три категории:

- с помощью выбора (линейный выбор, выбор с подсчетом, сортировка слиянием),

- с помощью включения (прямое включение, бинарное включение, двухпутевая вставка, метод Шелла),

- с помощью обменов (”пузырек”, шейкер-сортировка, ”быстрая”).

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

R[j] – j я запись таблицы;

K[j] – значение ключевого поля (ключа) j й записи.

В иллюстрационных примерах для простоты рассматриваются только значения ключевого поля таблицы.
^ Линейный выбор (сортировка выбором)

Согласно методу сортировки линейным выбором, начиная с первой записи таблицы (i=1), осуществляется поиск записи, имеющей наименьшее значение ключа (j=i, i+1, …n). После того, как эта запись найдена, она меняется местами с первой записью таблицы. В результате такой перестановки запись с наименьшим значением ключа помещается в первую позицию и в дальнейшем не рассматривается. Если же наименьшее значение ключа, имеет первая запись, то перестановка не нужна. Затем, начиная со второй записи таблицы (i=2), осуществляется поиск второго наименьшего ключа. Найденная запись меняется местами со второй записью. Этот процесс заканчивается поиском места для предпоследней записи таблицы (i=n-1). После этого все записи будут расположены в порядке возрастания кодов ключа.

Число сравнений в данном методе равно (в среднем порядка ). Максимальное количество перестановок – (n-1), причем эти величины не зависят от исходного состояния ключей.

В качестве примера рассмотрим сортировку таблицы со следующими значениями ключей: 23 11 4 56 9 35 7

Ниже показаны этапы сортировки (перемещаемые элементы подчеркнуты):

1: 23 11 4 56 9 35 7

2: 4 11 23 56 9 35 7

3: 4 7 23 56 9 35 11

4: 4 7 9 56 23 35 11

5: 4 7 9 11 23 35 56

6: 4 7 9 11 23 35 56
Программа сортировки таблицы методом линейного выбора приведена в приложении А.
^ Модифицированный метод линейного выбора: за первый проход таблицы определяются запись с минимальным значением ключа и запись с максимальным значением ключа, которые меняются местами с первой и последней записями соответственно:

23 11 4 56 9 35 7

4 11 23 7 9 35 56

Записи с ключами 4 и 56 стали на свои места и из дальнейшего процесса сортировки исключаются. Операция сортировки модифицированным методом выполняется за [n/2] проходов таблицы:

4 11 23 7 9 35 56

4 7 23 11 9 35 56

4 7 9 11 23 35 56


^

Линейный выбор с подсчетом



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

Просмотр таблицы начинается с первой записи (i=1,2, …n-1). Ее ключ сравнивается с ключами последующих записей (j=i+1, i+2,…n). При этом счетчик большего из сравниваемых ключей увеличивается на 1. При втором просмотре таблицы первый ключ уже не рассматривается, второй ключ сравнивается со всеми последующими. Результаты сравнений фиксируются в счетчиках.

Для таблицы, содержащей n записей, этот процесс повторяется (n-1) раз. После выполнения всех просмотров счетчик каждого элемента указывает, какое количество ключей таблицы меньше ключа этого элемента. Эти счетчики используются затем в качестве индексов элементов результирующей таблицы. Поместив записи в результирующую таблицу в соответствии со значениями их счетчиков, получим упорядоченную таблицу. В процессе сортировки выполняется (n-1) просмотров таблицы с n/2 сравнениями в среднем при каждом просмотре. Значения счетчиков изменяются столько раз, сколько выполняется сравнений. Рассмотрим пример использования этого метода. Ключи записей и массив счетчиков имеют вид:

Индексы

Ключи

Счетчики


0

9

0

1

5

0

2

10

0

3

2

0


Изменение массива счетчиков в результате просмотров:


1-й

просмотр

2-й

просмотр

3-й

просмотр

Результирующая таблица (ключи)

2

2

2

2

0

1

1

5

1

2

3

9

0

0

0

10
  1   2   3   4   5   6   7   8   9   ...   19

Добавить документ в свой блог или на сайт

Похожие:

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по курсу “
В прологе предусматриваются основные арифметические операции +, -, /, ×, mod, div. Чтобы заставить систему выполнить присваивание...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница