Способы описания алгоритмов основные алгоритмические структуры

Способы описания алгоритмов.

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

Словесное описание– структура алгоритма на естественном языке. Например, инструкции по эксплуатации электроприборов. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном языке. Данный способ описания алгоритмов не нашел широкого распространения.

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

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

Программа– описание структуры алгоритма на понятном языке алгоритмического программирования.

Основные конструкции, использующиеся для построения блок-схем:

Графическое изображение блока

Блок, характеризующий начало/конец алгоритма (для подпрограмм – вызов/возврат):

Блок – процесс, предназначенный для описания отдельных действий:

Блок – предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам):

Блок – ввода/вывода с неопределенного носителя:

Блок – ввод с клавиатуры:

Блок – вывод на монитор:

Блок – вывод на печатающее устройство:

Блок – решение (проверка условия или условный блок):

Блок, описывающий цикл с параметром:

Блок – границы цикла, описывающий циклические процессы типа «цикл с предусловием», «цикл с постусловием»:

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

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

1.Линейная структура:

Линейной называется алгоритмическая конструкция, реализованная в виде последовательности действий (шагов), в которой каждое действие алгоритма выполняется ровно 1 раз, причем после каждого i-ого действия выполняется (i+1)-ое действие, еслиi-ое действие не конец алгоритма.

2.Разветвляющеяся структура:

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

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

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

Источник

Способы описания алгоритмов основные алгоритмические структуры

Различают следующие виды алгоритмов :

линейный – список команд (указаний), выполняемых последовательно друг за другом;

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

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

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

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

1. определить температуру воздуха

2. если температура ниже 0, то надеть шубу, иначе надеть куртку

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

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

Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем они настолько достаточны, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования .

Источник

Понятие алгоритма, свойства алгоритмов, способы записи алгоритма, основные алгоритмические структуры.

Понятие алгоритма, свойства алгоритмов, способы записи алгоритма, основные алгоритмические структуры.

Алгоритм – последовательность инструкций, правильное выполнение которых ведет к решению поставленной задачи.

Основными свойствами алгоритма являются:

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

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

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

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

5. Конечность(каждое действие и алгоритм в целом должны иметь возможность завершения).

Алгоритм может быть сформулирован тремя различными способами:

1) Словесная формулировка алгоритма;

2) Формулировка в виде графической схемы (блок-схема);

3) Запись алгоритма в виде программы, записанной на одном из языков программирования.

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

1) Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке, в котором они следуют.

2) Цикличный алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.

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

· Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз (используют, когда заранее известно какое число повторений тела цикла необходимо выполнить);

· Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.

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

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

Языки программирования, классификация языков программирования. Понятие о системе программирования.

Язык программирования – это фиксированная система обозначений для описания алгоритмов и структур данных.

Языки программирования – искусственные языки. От естественных они отличаются ограниченным числом «слов», значение которых понятно транслятору, и очень строгими правилами записи команд (операторов).

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

Транслятор программ может производиться двумя различными способами:

Интерпретатор (каждая инструкция, вводимая в ПК, сразу же преобразуется в машинный код и выполняется);

Компилятор (в машинный код переводится только вся программа в целом).

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

Язык машинных кодов и язык Ассемблера относятся к языкам низкого уровня, т.е. уровня приближенного к машинной логике.

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

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

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

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

Пример.

WriteLn(‘Введите через пробел два числа ‘);

WriteLn(‘Сумма чисел равна ‘,s);

Оператор присваивания. Выражение, приоритеты в выражениях.

Оператор присваивания – основной оператор любого языка программирования. Общая форма записи оператора:

имя величины := выражение

Например, V:=A; или V:=A+1;

переменная := выражение;

левая_часть := правая_часть;

Оператор работает справа налево, то есть сначала вычисляется то, что записано в правой части, а затем результат записывается «в левую часть».

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

Как только в программе встречается переменная, для неё в памяти отводится место. Оператор присваивания помещает значение переменной или значение выражения в отведённое место.

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

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

Тип переменной в левой части оператора присваивания обычно должен совпадать с типом значения выражения в правой части. Выражения являются составной частью операторов.

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

— операция NOT;

— операции типа умножения;

— операции типа сложения;

— операции сравнения (отношения).

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

Например, если в выражении … (X > 5) AND (Y > 10) … не поставить скобки, то будет синтаксическая ошибка, так как приоритет операции AND выше приоритета операций сравнения >.

операции типа умножения – это *, /, div, mod, and

операции типа сложения – это +, -, or, xor

операции сравнения – это <>, , =, in

Сравнение строк символов выполняется слева направо посимвольно. Более короткие строки дополняются пробелами справа.

Оператор цикла с заранее известным количеством повторений

Инструкция for используется в том случае, если некоторую последовательность действий (инструкций программы) надо выполнить несколько раз, причем число повторений известно.

В общем виде инструкция for записывается следующим образом:

for счетчик := нач_знач to кон_знач do

// здесь инструкции, которые надо выполнить несколько раз

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

Если в инструкции for вместо слова to записать downto, то поле очередного выполнения инструкций тела цикла значение счетчика будет не увеличиваться, а уменьшаться.

Текстовые.

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

var Имя_переменной: text;

Имя_переменной – имя переменной, которая впоследствии будет связана с файлом;

text — соответствующий тип переменной.

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

Типизированные.

Типизированным называется файл, который состоит из однородных элементов, относящихся к одному и тому же типу. Такими элементами могут

быть переменные различных типов и массивы. Каждый элемент такого файла

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

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

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

его нельзя просматривать и редактировать с помощью обычного текстового редактора.

Для того, чтобы в типизированный файл можно было производить

запись или считывать из него информацию, его следует связать с помощью

процедуры assign с файловой переменной подобно тому, как мы это уже

делали с текстовыми файлами. Например, так:

В общем виде описание файловой переменной для типизированного файла выглядит следующим образом:

var Имя_переменной: file of Тип;

Имя_переменной – имя переменной, связанной с типизированным

file – служебное слово;

Тип – тип элементов, из которых состоит данный файл.

Подобно текстовым файлам, типизированные файлы открываются для чтения процедурой resetи для записи процедурой rewrite, а закрываются процедурой close.

Непосредственное чтение данных из файла производится с помощью следующего оператора:

read (Имя_переменной1, Имя_переменной2);

Имя_переменной1 –имя файловой переменной;

Имя_переменной2 – имя обычной переменной, относящейся к тому же типу, что и элементы типизированного файла.

Запись в файл производится оператором:

write (Имя_переменной1, Имя_переменной2);

Операторы writeln и readln для записи и чтения в типизированном файле использовать нельзя, так как данный тип не содержит строк.

Процедура seek (Имя_переменной, п);

seek – служебное слово, которое в переводе с англ. «искать»;

Имя_переменной – имя файловой переменной;

n – порядковый номер элемента в файле (нумерация начинается с нуля).

Если в ходе работы программы необходимо установить, какой элемент

файла является текущим, то для этого используется функция filepos.

Общий вид описания данной функции:

Аргументом данной функции является имя файловой переменной, а

значением – порядковый номер текущего элемента в файле.

Нетипизированные.

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

Описание нетипизированной файловой переменной имеет следующий общий вид:

var Имя_переменной: file;

Имя_переменной – имя связываемой с нетипизированным файлом файловой переменной.

Связывание файловой переменной с файлом производится так же, как и

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

rewrite. Формат этих процедур также аналогичен формату других видов

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

Для непосредственной записи информации в нетипизированный файл используется оператор blockwrite.

Общий вид данного оператора следующий:

blockwrite (Имя_переменной1, Имя_переменной,n);

Имя_переменной1 – имя файловой переменной;

Имя_переменной2 – имя вспомогательной переменной, из которой данные передаются в файл;

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

Чтение информации из файла производится оператором blockread.

Общий вид данного оператора:

blockread (Имя_переменной1, Имя_переменной2,n);

Имя_переменной1 – имя файловой переменной;

Имя_переменной2 – имя вспомогательной переменной, в которую передаются данные из файла;

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

Стандартные модули Паскаля.

В Турбо Паскале имеется 8 стандартных модулей, в которых содержится множество различных типов, констант, процедур и функций. Этими модулями являются SYSTEM, DOS, CRT, GRAPH, OVERLAY, TURBO3, GRAPH3. Модули Паскаля GRAPH, TURBO 3, GRAPH 3 выделены в отдельные TPU -файлы, а остальные входят в состав библиотечного файла TURBO.TPL. Лишь один модуль Паскаля SYSTEM подключается к любой программе автоматически, все остальные становятся доступны только после указания их имен в списке подключаемых модулей.

Модуль Паскаля SYSTEM. В него входят все процедуры и функции стандартного Паскаля, а также встроенные процедуры и функции, которые не вошли в другие стандартные модули (например, INC , DEC , GETDIR и т.п.). Модуль Паскаля SYSTEM подключается к любой программе независимо от того, объявлен ли он в предложении USES или нет, поэтому его глобальные константы, переменные, процедуры и функции считаются встроенными в Турбо Паскаль.

Модуль Паскаля PRINTER делает доступным вывод текстов на матричный принтер. В нем определяется файловая переменная LST типа TEXT , которая связывается с логическим устройством PRN.

Модуль Паскаля CRT.В нем сосредоточены процедуры и функции, обеспечивающие управление текстовым режимом работы экрана. С его помощью можно перемещать курсор в любую точку экрана, менять цвет выводимых символов и фона, создавать окна. Кроме того, в данный модуль включены также процедуры «слепого» чтения клавиатуры и управления звуком.

Модуль Паскаля GRAPH. Содержит набор типов, констант, процедур и функций для управления графическим режимом работы экрана. Этот модуль позволяет создавать различные графические изображения и выводить на экран надписи стандартными или созданными программистом шрифтами.

Модуль Паскаля DOS. В модуле собраны процедуры и функции, открывающие доступ к средствам дисковой операционной системы MS — DOS .

Модуль Паскаля OVERLAY. Данный модуль необходим при разработке громоздких программ с перекрытиями. Турбо Паскаль обеспечивает создание программ, длина которых ограничивается лишь основной оперативной памятью. Операционная система MS — DOS оставляет программе около 580 Кбайт основной памяти. Память такого размера достаточна для большинства исполняемых программ, тем не менее, использование программ с перекрытиями снимает это ограничение.

Модули Паскаля TURBO 3 и GRAPH 3 введены для обеспечения совместимости с ранней версией системы Турбо Паскаль.

Структура модулей Паскаля:

Unit ;
interface ;
implementation ;
begin
;
end.

Здесь UNIT – зарезервированное слово (единица); начинает заголовок модуля;

· — имя модуля (правильный идентификатор);

· INTERFACE – зарезервированное слово (интерфейс); начинает интерфейсную часть модуля;

· IMPLEMENTATION – зарезервированное слово (выполнение); начинает исполняемую часть модуля;

· BEGIN – зарезервированное слово; начинает инициирующую часть модуля; причем конструкция begin необязательна;

· END – зарезервированное слово – признак конца модуля.

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

Компиляция модулей Паскаля.

В среде Турбо Паскаль имеются средства, управляющие способом компиляции модулей и облегчающие разработку больших программ. Определены три режима компиляции: COMPILE ,MAKE , BUILD. Режимы отличаются способом связи компилируемого модуля или основной программы с другими модулями, объявленными в предложении USES.

При компиляции модуля или основной программы в режиме COMPILE все, упоминаемые в предложении USES модули, должны быть предварительно откомпилированы, и результаты компиляции должны быть помещены в одноименные файлы с расширением TPU (от англ. Turbo Pascal Unit). Файл с расширением TPU создается автоматически при компиляции модуля Паскаля.

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

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

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

Метод бинарного поиска

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

Метод (алгоритм) бинарного поиска реализуется следующим образом:

1. Сначала образец сравнивается со средним (по номеру) элементом массива;

· Если образец равен среднему элементу, то задача решена.

· Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz) и за новое значение verh принимается sred+1, а значение niz не меняется.

· Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1) и за новое значение niz принимается sred-1, а значение verh не меняется.

2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (niz – verh)/2+verh вычисляется новое значение sred и поиск продолжается.

Алгоритм бинарного поиска заканчивает свою работу, если искомый элемент найден, или если перед выполнением очередного цикла поиска обнаруживается, что значение verh больше, чем niz.

Сортировка массива

Под сортировкой массива подразумевается процесс перестановки элементов массива, целью которого является размещение элементов массива в определенном порядке.

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

Сортировка методом обмена

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

Типизированные указатели

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

Указатель, как и любая другая переменная программы, должен быть объявлен в разделе объявления переменных.

В общем виде объявление типизированного указателя выглядит след образом:

Имя_указателя: ^Тип;

Имя_указателя – имя переменноц-указателя;

Тип – тип переменной, на которую указывает переменная-указатель;

Значок ^ показывает, что объявляемая переменная является указателем.

Нетипизированные указатели

Чтобы хранить указатели, вам требуется переменная-указатель, а для создания переменной-указателя вам необходим ссылочный тип (или тип «указатель»). Простейшим ссылочным типом является стандартный тип с именем Pointer. Переменная типа Pointer — это общий (нетипизированный) указатель, то есть, просто адрес. Он не содержит информации о том, на что он указывает.

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

Списки

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

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

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

Упорядоченный список

Как правило, списки упорядочены. Порядок следования элементов в списке определяется содержимым одного из полей.

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

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

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

Очереди.

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

Например, пусть у нас есть очередь из трех элементов А,В,С, в которую первым был помещен элемент А, затем — элемент В, а последним — элемент С. После удаления элемента А первым элементом очереди будет элемент В. При этом элемент А остался в массиве на своем месте, но его уже нет в очереди, так как указатель начала очереди указывает на элемент В, т. е. следующий элемент массива. Если мы добавим в очередь новый элемент D, то он будет помещен в конец очереди, определяемый указателем конца. Очередь, в которой нет ни одного элемента, называется пустой. В этом случае оба указателя показывают на одно и то же место. Операции над очередями: Init — создает пустую очередь; Empty — возвращает значение true, если очередь пуста, и false в противном случае; Insert — добавляет элемент в конец очереди; Remove — удаляет элемент из начала очереди.

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

Бинарное дерево должно реализовывать следующие операции:

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

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

Получение значения текущего элемента

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

Удаление узла из дерева

Уничтожение бинарного дерева

Основные понятия объектно-ориентированного программирования: наследование, полиморфизм, инкапсуляция.

Объектно-ориентированное программирование (ООП) – это методика разработки программ, в основе которой лежит понятие объекта, как некоторой структуры, описывающей объект реального мира, его поведение.

Язык Object Pascal, поддерживая концепцию объектно-ориентированного программирования, дает возможность определять классы.

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

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

Под инкапсуляцией понимается скрытие полей объекта с целью обеспечения доступа к ним только посредством методов класса.

В Object Pascal ограничение доступа к полям объекта реализуется при помощи свойств объекта. Свойство объекта характеризуется полем, сохраняющим значение свойства, и двумя методами, обеспечивающими доступ к полю свойства. Метод установки значения свойства называется методом записи свойства (write), а метод получения значения свойства – методом чтения свойства (read).

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

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

Понятие алгоритма, свойства алгоритмов, способы записи алгоритма, основные алгоритмические структуры.

Алгоритм – последовательность инструкций, правильное выполнение которых ведет к решению поставленной задачи.

Основными свойствами алгоритма являются:

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

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

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

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

5. Конечность(каждое действие и алгоритм в целом должны иметь возможность завершения).

Алгоритм может быть сформулирован тремя различными способами:

1) Словесная формулировка алгоритма;

2) Формулировка в виде графической схемы (блок-схема);

3) Запись алгоритма в виде программы, записанной на одном из языков программирования.

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

1) Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке, в котором они следуют.

2) Цикличный алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.

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

· Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз (используют, когда заранее известно какое число повторений тела цикла необходимо выполнить);

· Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.

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

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

Источник