Способы описания алгоритмов и программ (сп-бы, правила построения). Типы данных и их структуры

Понятие алгоритм является основным при составлении любых программ.

Программа для ЭВМ – алг, оформленный спец.образом, конечная послед-сть предписаний, определяющих процесс переработки вх. данных в вых.

Алгоритм – формальное предписание однозначно определяющее сод-е и послед-сть операций и перевод совок-сти исх данных в искомый рез-т.

Свойства алгоритма:

1. Алгоритм должен заканчиваться после конечного числа шагов (св-во конечности)

2. Каждый шаг алгоритма должен быть точно и однозначно определен (св-во определенности)

3. Должен иметь некоторое число входных данных, т.е. величин, заданных до начала работы

4. Результатом работы алгоритма должна быть одна или несколько вых вел-н, зависящих от исх данных (св-во результативности).

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

Для задания структур данных и алг-в их обработки требуется иметь систему формальных предписаний (язык описаний). Средства описаний:

1. Словесный – описание послед-сти обработки элементов данных. Задается в произвольном изложении на естественном языке.

2. Структурно-стилизованный – основан на формализованном представлении предписаний, задаваемых путем использования ограниченного набора типовых синтаксических конструкций. Такие средства описаний – псевдокоды. 3. Программный

4. Графический – при вып-нии схем отд функции алг-мов и прогр отображают в виде условно-графических символов. Порядок номера символа проставляют слева в разрыве его контура. Символы соединяются линиями линии потока данных. Размер выбирают из ряда 10,15 и т.д. мм. b=1,5*а;

(Процесс операции присваивания, арифметика, действия; Решение (условие) - выбирается направление; Модификация (счетчик типа for); Предопределенный процесс; Ввод / вывод данных; Пуск / остановка (начало); Межстраничный соединитель; Комментарии)

Типы данных

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

Элемент структ: константа ( пост знач-е и пост имя ) и переменная ( перем знач-е и пост имя ).

Массив – конечная последовательность (множество) переменных 1го фиксированного типа, объединенных единым фиксированным именем. Массив состоит из компонент. Все 1типа – базового, поэтому структ массива однородна. Массивы относятся к структурам со случайным доступом.

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

Матрица – массив в массиве.

Запись – структура данных, позволяющая группировать данные различных типов. Элементы записи могут быть составными. Мощность составного типа равна произведению мощностей составляющих типов. Как и массив, запись – структура со случайным доступом.

Таблица – объединение структур типа запись (по строке – записи, по столбцам – массивы).

Фрейм – структ дан для предст-я знаний в конкретных предм обл. Поля фрейма связ-ся м/у собой отнош-ми, реализуемыми в виде отд процедур.

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

Стек – хар-ся послед-ной орг-цией и возм-тью доступа только с 1 края цепочки записей – вершины стека. В стеке реализуется следующий принцип: «последний пришел – первый ушел». Стековая организация широко используется при трансляции входных языков и при управлении ОП.

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

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

Файл – последовательность элементов одного и того же типа, число которых заранее не определено. В отличии от массивов, файлы имеют следующие особенности: а) длина файла может меняться; б) невозможно сразу обратиться к произвольному элементу файла. Элементы просматриваются подряд от начала до конца, при этом доступен только один элемент. С каждым файлом связана буферная переменная. Этот тип переменной совпадает с базовым типом файла. В буфере может размещаться только 1 элемент файла, значение кот будет явл-ся значением буфера.

Статическая переменная – описанная где-либо в программе.

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

Ссылочный тип – простой тип (как вещественные, целые, булевые).