Вопрос 3-4. Понятие подпрограммы, функции, возвращающие значения в C/C++, описание и использование.

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

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

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

Достоинства использования подпрограмм

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

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

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

• Позволяет повторно использовать ранее разработанные программы.

Функции, возвращающие значение: любого типа, кроме void, в концеreturn.

bool palindrom(string s)

{

int i=0, j=s.length()-1;

for (; i<j; i++, j--) if (s[i]!=s[j])

return false;

return true;

}

Функции, не возвращающие значение. Типа void.

Вопрос 5. Передача параметров в подпрограмму, параметры входные и выходные, параметры, передаваемые по значению и по адресу.

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

Передача параметров – подстановка фактических параметров вместо формальных при обращении к подпрограмме.

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

Существует 2 способа передачи параметров – по значению и по адресу.

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

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

В С/С++ параметры по адресу могут передаваться с помощью указателей и с помощью ссылок.

Формальные параметры делятся на входные и выходные.

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

Выходные параметры могут передаваться только по адресу.

Вопрос 6.Использование подпрограмм, параметры формальные, локальные, глобальные, обращения к подпрограммам, фактические параметры.

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

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

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

Если значение какого-то локального параметра необходимо сохранить между вызовами, то этот параметр нужно описать статически (static int n=0). Такая статическая переменная сохраняется не в стеке, а в сегменте данных и инициализируется один раз при первом обращении к подпрограмме.

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

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

. Стек – это настолько популярная структура данных, что во многих ЭВМ она реализуется аппаратно

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

LIFO (Last In – First Out). Описание стека помощью массива:

const int stacksize = 100;

int stack[stacksize], x, sp;

• Компонентами стека могут быть величины различного типа, здесь int. Для работы со стеком нужно уметь обратиться к вершине стека, для этой цели вводится специальная переменная, называемая указателем стека, здесьsp (stack pointer).Чаще всего она указывает на первый свободный элемент стека, т.е. ее значением является номер элемента массива, не занятого информацией. Поэтому вначале работы, когда стек пуст, указатель стекаspуказывает на первый элемент массива.Оператор присваивания

• sp = 0;- инициализирует стек, делает его пустым.

Кроме инициализации над стеком производятся две операции:

• Положить в стек и

• Взять из стека.

• На С++ эти операции реализуются так:

1. stack[sp] = x;// положитьxна вершину стека,

sp = sp + 1;// указатель стека переместить на след-ую комп-ту

2. sp = sp - 1;

x = stack[sp];

• т.к. spуказывает на первый свободный элемент стека, вначале указатель уменьшаем на единицу, а затем переменнойxприсваиваем значение последнего элемента в стеке.

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

• Положить в стек:

if (sp = = stacksize) cout << “стек полон \n”;

else { stack[sp] = x; sp = sp + 1; };

• Взять из стека:

if ( sp < 1) cout << “стек пуст \n”;

else {sp = sp - 1; x = stack[sp]; };

Указатель стека spможет указывать на первый занятый элемент в стеке, на его вершину, тогда операции положить в стек и взять из стека преобразуются так:

1. sp = sp + 1; stack[sp] = x;

2. x = stack[sp]; sp = sp – 1;

Пример использования стека:

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

Существуют три формы записи выражений: 1) инфиксная, 2) префиксная и 3) постфиксная.

• Инфиксная запись – это привычная нам запись выражения, когда знаки операций стоят между операндами, например,

x + y * z – a/(b + c)‏

• В префиксной записи знаки операций выносятся вперед

- + * x y z / + a b c

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

x y z * + a b c + / -В ОПЗ отсутствуют скобки, а знаки операций выполняются в порядке их написания, таким образом выражение в виде ОПЗ может быть вычислено за один проход слева направо. Для преобразования инфиксной формы в постфиксную существуют различные алгоритмы, приведем алгоритм стека с приоритетами, предложенный голландским ученым Дейкстра. Пусть входная строка это выражение в обычной, инфиксной форме, а выходная строка – выражение в форме ОПЗ.

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

всем знакам операций и скобкам присваивается приоритет

знак приоритет

( 0

) 1

+ - 2

* / 3

Если очередной символ входной строки это знак операции и его приоритет равен нулю или

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

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

+

(

/

-

*

+

x y z * + a b c + / -x+y*-a(b+c)

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

x y z * + a b c + / -