Основные алгоритмические конструкции

Структура данных. Классификация структур данных.

Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

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

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

1) По сложности: простые и интегрированные.

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

Интегрированные структуры данных конструируются программистом.

2). По способу представления: физическая и логическая

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

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

3). По наличию связей между элементами данных: несвязные и связные.

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

Связные структуры характеризуются наличием связи.

Примерами несвязных структур есть векторы, массивы, строки, стеки, очереди; примеры связных структур - связные списки.

4). По изменчивости: статические, полустатические, динамические. Изменчивость, то есть изменение числа элементов и (ли) связей между элементами структуры.

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

Полустатические - это стеки, очереди, деки, дерева.

Динамические - линейные и разветвленные связные списки, графы, дерева.

5). По характеру упорядоченности элементов в структуре: линейные и нелинейные.

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

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

6). По виду памяти, используемой для сохранности данных: структуры данных для оперативной и для внешней памяти. Структуры данных для оперативной памяти - это данные, размещенные в статической и динамической памяти компьютера. Все вышеприведенные структуры данных - это структуры для оперативной памяти.

Структуры данных для внешней памяти называют файловыми структурами или файлами. Примерами файловых структур есть последовательные файлы, файлы, организованные разделами, В- деревья.

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

Алгоритмический язык	Блок-схема
действие 1 действие 2 ... действие n

Пример. Определить значение переменной c после выполнения фрагмента алгоритма.

Алгоритмический язык	Блок-схема
a:=3 c:=4 c:=a+c/2

Ответ: 5

2. Структура ветвление. В зависимости от результата проверки условия («да» или «нет») осуществляет выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведёт к общему выходу, поэтому работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура «ветвление» бывает четырёх видов: «если-то»; «если-то-иначе»; «выбор»; «выбор-иначе».

Структура «если-то».

Алгоритмический язык	Блок-схема
еслиусловие то действия всё

Пример 1. Определить значение переменной a после выполнения фрагмента алгоритма при a=5 и a=10.

Алгоритмический язык	Блок-схема
Ввода еслиa>5 то a:=a+20 всё

Ответ: 5 и 30.

Структура «если-то-иначе».

Алгоритмический язык	Блок-схема
еслиусловие тодействия 1 иначедействия 2 всё

Пример 2. Определить значение переменной a после выполнения фрагмента алгоритма при a=5 и a=10.

Алгоритмический язык	Блок-схема
Ввода еслиa>5 то a:=a+20 иначеa:=a*10 всё

Ответ: 50 и 30.

Структура «выбор».

Алгоритмический язык	Блок-схема
выбор приусловие 1: действия 1 приусловие 2: действия 2 … приусловие n: действия n всё

Пример 3. Дано целое число в диапазоне 1–7. Составить строку — название дня недели, соответствующее данному числу (1 — «понедельник», 2 — «вторник» и т. д.).

Алгоритмический язык	Блок-схема
выбор приn=1: c:=«понедельник» приn=2: c:=«вторник» приn=3: c:=«среда» приn=4: c:=«четверг» приn=5: c:=«пятница» приn=6: c:=«суббота» приn=7: c:=«воскресенье» всё

Структура «выбор-иначе».

Алгоритмический язык	Блок-схема
выбор приусловие 1: действия 1 приусловие 2: действия 2 … приусловие n: действия n иначедействия n + 1 всё

Пример 4. Дано целое число n. Составить строку-описание оценки, соответствующей числу n (1 — «плохо», 2 — «двойка», 3 — «тройка», 4 — «хорошо», 5 — «отлично»). Если n не лежит в диапазоне 1–5, то вывести строку «ошибка»

Алгоритмический язык	Блок-схема
выбор приn=1: c:=«плохо» приn=2: c:=«двойка» приn=3: c:=«тройка» приn=4: c:=«хорошо» приn=5: c:=«отлично» иначеc:=«ошибка» всё

3. Структура цикл. Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Циклы бывают трёх видов: с предусловием «пока-делай», с постусловием «делай-пока», со счётчиком «для».

Цикл с предусловием («пока-делай»). Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.

Алгоритмический язык	Блок-схема
нц покаусловие тело цикла кц

Дата добавления: 2015-04-30