СТЕК И ФУНКЦИИ

 

 

Будем рассматривать каждый ВЫЗОВ функции как помещение в специальный стек

большого "блока информации", включающего в частности

АРГУМЕНТЫ И ЛОКАЛЬНЫЕ ПЕРЕМЕННЫЕ вызываемой функции.

 

Оператор return из вызванной функции выталкивает со стека ВЕСЬ такой блок.

 

В качестве примера рассмотрим такую программу:

 

int x = 7; /* глобальная */

int v = 333; /* глобальная */

 

int factorial(int n){

int w; /* лишняя переменная, только для демонстрационных целей */

 

w = n;

 

if(n == 1) return 1; /* #a */

else return n * factorial(n-1); /* #b */

}

void func(){

int x; /* func::x */

 

x = 777; /* #c */

printf("Вызвана функция func()\n");

}

void main(){

int y = 12; /* main::y */

int z;

 

/* A */

z = factorial(3); /* B */

printf("z=%d\n", z);

 

func(); /* C */

}

 

Выполнение программы начнется с вызова функции main().

В точке /* A */

 

| в з г л я д |

V V

 

--------+ +--------

|=======================|

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

 

В каждый данный момент видимы переменные, которые находятся

a) на вершине (и только) стека вызовов функций.

b) и незаслоненные ими глобальные переменные.

В данном случае мы смотрим "сверху" и видим:

 

main::z, main::y,::x,::v

 

 

В точке /* B */ мы вызываем factorial(3).

 

 

--------+ +--------

|=======================|

| w = мусор |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

При новом взгляде видимы:

factorial(3)::w, factorial(3)::n,::x,::v

 

Стали невидимы:

main::z, main::y

 

Строка "текущий оператор..." указывает место, с которого надо возобновить

выполнение функции, когда мы вернемся в нее.

 

Когда выполнение программы в функции factorial(3) дойдет до точки

/* #b */ будет выполняться return 3 * factorial(2).

В итоге будет вызвана функция factorial(2).

 

--------+ +--------

|=======================|

| w = мусор |

| n = 2 |

|factorial(2) |

|=======================|

| +-|---> текущий оператор return 3 * factorial(2);

| w = 3 |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

 

 

Когда выполнение программы в функции factorial(2) дойдет до точки

/* #b */ будет выполняться return 2 * factorial(1).

В итоге будет вызвана функция factorial(1).

 

--------+ +--------

|=======================|

| w = мусор |

| n = 1 |

|factorial(1) |

|=======================|

| +-|---> текущий оператор return 2 * factorial(1);

| w = 2 |

| n = 2 |

|factorial(2) |

|=======================|

| +-|---> текущий оператор return 3 * factorial(2);

| w = 3 |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

 

Затем в factorial(1) выполнение программы дойдет до точки /* #a */

и будет производиться return 1.

 

При return вычеркивается ОДИН блок информации со стека вызовов функций,

и возобновляется выполнение "текущего оператора" в функции,

ставшей НОВОЙ вершиной стека вызовов.

Заметьте, что в данной ситуации вызванные функции factorial(m) еще не завершились.

В них еще ЕСТЬ что сделать: вычислить выражение в return,

и собственно выполнить сам return. Вычисления будут продолжены.

 

--------+ +--------

|=======================|

| +-|---> текущий оператор return 1;

| w = 1 |

| n = 1 |

|factorial(1) |

|=======================|

| +-|---> текущий оператор return 2 * factorial(1);

| w = 2 |

| n = 2 |

|factorial(2) |

|=======================|

| +-|---> текущий оператор return 3 * factorial(2);

| w = 3 |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

 

Начинается выталкивание функций со стека и выполнение операторов return;

 

--------+ +--------

|=======================|

| +-|---> текущий оператор return 2 * 1;

| w = 2 |

| n = 2 |

|factorial(2) |

|=======================|

| +-|---> текущий оператор return 3 * factorial(2);

| w = 3 |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

 

--------+ +--------

|=======================|

| +-|---> текущий оператор return 3 * 2;

| w = 3 |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

 

--------+ +--------

|=======================|

| +-|---> текущий оператор z = 6;

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

 

--------+ +--------

|=======================|

| z = 6 |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

 

Наконец, в точке /* C */ будет вызвана функция func().

Рассмотрим точку /* #c */ в ней.

 

--------+ +--------

|=======================|

| x = 777; |

|func(); |

|=======================|

| +-|---> текущий оператор func();

| z = 6 |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

 

В данном месте нас интересует - какие переменные видимы?

Видимы:

func::x = 777

::v = 333

 

И все.

::x заслонен локальной переменной.

main::y, main::z невидимы, так как находятся

не на вершине стека вызовов функций

 

Многие функции более естественно выражаются через рекурсию.

Хотя, часто это приводит к излишним вычислениям по сравнению с итерациями

(то есть циклами). Вот пример - числа Фибоначчи.

 

int fibonacci(int n){

if(n==1 || n==2) return 1;

 

/* else */

 

return fibonacci(n-1) + fibonacci(n-2);

}

void main(){

printf("20ое число Фибоначчи равно %d\n", fibonacci(20));

}

 

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

результатов, то этот массив на самом деле неявно моделируется

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

Однако этот способ плох - в нем слишком много повторяющихся

действий. Добавим оператор печати - и посчитаем, сколько раз

была вызвана fibonacci(1)?

 

int called = 0;

 

int fibonacci(int n){

if(n==1){

called++;

return 1;

 

} else if(n==2)

return 1;

 

return fibonacci(n-1) + fibonacci(n-2);

}

void main(){

printf("20ое число Фибоначчи равно %d\n", fibonacci(20));

printf("fibonacci(1) была вызвана %d раз\n", called);

}

 

Она была вызвана... 2584 раза!

C

 

/* Рисуем хитрую геометрическую фигуру */

#include

 

const int LINES = 15;

 

void draw(int nspaces, int nstars, char symbol){

int i;

 

for(i=0; i < nspaces; i++)

putchar(' ');

for(i=0; i < nstars; i++)

putchar(symbol);

}

 

void main(){

int nline, nsym;

char symbols[3]; /* Массив из трех букв */

 

symbols[0] = '\\';

symbols[1] = 'o';

symbols[2] = '*';

 

for(nline=0; nline < LINES; nline++){

for(nsym = 0; nsym < 3; nsym++)

draw(nline, nline, symbols[nsym]);

 

/* Переход на новую строку вынесен

из функции в главный цикл */

putchar('\n');

}

}

C

 

/* Задача:

нарисовать таблицу вида

 

кот кот кот кошка кошка кот

кот кот кошка кошка кот...

 

Где идет последовательность

кот, кот, кот, кошка, кошка...

повторяющаяся много раз и располагаемая по 6 зверей в строку.

*/

 

#include /* магическая строка */

 

/* Объявление глобальных переменных.

В данном случае - констант.

*/

 

int TOMCATS = 3; /* три кота */

int CATS = 2; /* две кошки */

int ANIMALS_PER_LINE = 6; /* шесть зверей в каждой строке */

int LINES = 25; /* число выводимых строк */

 

/* и нам понадобится еще одна переменная - общее число зверей.

Ее мы вычислим через уже заданные, поэтому тут мы ее объявим...

но вычислить что-либо можно только внутри функции.

В нашем случае - в функции main().

*/

int ANIMALS; /* общее число зверей */

 

int nth_in_line = 0; /* номер зверя в текущей строке */

/* Эта переменная не может быть локальной в функции, так как

* тогда она уничтожится при выходе из функции. Нам же необходимо,

* чтобы ее значение сохранялось. Поэтому переменная - глобальная.

*/

 

/* Функция, которая считает число зверей в одной строке

и либо переводит строку, либо переводит печать в

следующую колонку (табуляцией).

*/

void checkIfWeHaveToBreakLine(){

nth_in_line++; /* текущий номер зверя в строке (с единицы) */

 

if(nth_in_line == ANIMALS_PER_LINE){

/* Если строка заполнена зверьми... */

putchar('\n'); /* новая строка */

nth_in_line = 0; /* в новой строке нет зверей */

} else {

putchar('\t'); /* в следующую колонку */

}

}

 

void main(){

int nanimal; /* номер зверя */

int i; /* счетчик */

 

ANIMALS = ANIMALS_PER_LINE * LINES;

nanimal = 0;

 

while(nanimal < ANIMALS){

 

for(i=0; i < TOMCATS; i++){

/* Оператор printf() выводит СТРОКУ СИМВОЛОВ.

СТРОКА заключается в двойные кавычки

(не путать с одиночными для putchar().

*/

printf("кот");

nanimal++; /* посчитать еще одного зверя */

 

/* и проверить - не надо ли перейти на новую строку? */

checkIfWeHaveToBreakLine();

}

for(i=0; i < CATS; i++){

printf("кошка");

nanimal++; /* посчитать еще одного зверя */

 

/* и проверить - не надо ли перейти на новую строку? */

checkIfWeHaveToBreakLine();

}

}

/* putchar('\n'); */

}

C

 

/*

Та же задача, но еще надо печатать номер каждого зверя.

Ограничимся пятью строками.

*/

 

#include /* магическая строка */

 

int TOMCATS = 3; /* три кота */

int CATS = 2; /* две кошки */

int ANIMALS_PER_LINE = 6; /* шесть зверей в каждой строке */

int LINES = 5; /* число выводимых строк */

int ANIMALS; /* общее число зверей */

 

int nth_in_line = 0; /* номер зверя в текущей строке */

 

void checkIfWeHaveToBreakLine(){

nth_in_line++;

 

if(nth_in_line == ANIMALS_PER_LINE){

putchar('\n');

nth_in_line = 0;

} else

printf("\t\t"); /* @ */

 

/* Одинокий оператор может обойтись без {...} вокруг него */

}

 

void main(){

int nanimal;

int i;

 

ANIMALS = ANIMALS_PER_LINE * LINES;

nanimal = 0;

 

while(nanimal < ANIMALS){

 

for(i=0; i < TOMCATS; i++){

/* Формат %d выводит значение переменной типа int

в виде текстовой строки.

Сама переменная должна быть в списке после формата

(список - это перечисление переменных через запятую).

Переменных ИЛИ выражений (формул).

 

Давайте выводить по ДВЕ табуляции --

это место отмечено в функции checkIfWeHaveToBreakLine()

как @.

 

Еще раз внимание - один символ мы выводим как

putchar('a');

Несколько символов - как

printf("abcdef");

 

Одиночные кавычки - для одной буквы.

Двойные кавычки - для нескольких.

*/

 

printf("кот%d", nanimal);

nanimal++;

 

checkIfWeHaveToBreakLine();

}

for(i=0; i < CATS; i++){

printf("кошка%d", nanimal);

nanimal++;

 

checkIfWeHaveToBreakLine();

}

}

}

C

 

/* Задача: напечатать корни из чисел от 1 до 100.

 

Новая информация:

Нам понадобится новый тип данных - ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА.

Это числа, имеющие дробную часть (после точки).

Как мы уже знаем, целые - это int.

буква - это char.

действительное число - это double.

(есть еще слово float, но им пользоваться не рекомендуется).

 

Для вычисления корня используется итерационный алгоритм Герона.

 

q = корень из x;

 

q[0]:= x;

q[n+1]:= 1/2 * (q[n] + x/q[n]);

 

Главное тут не впасть в ошибку, не клюнуть на q[n] и не

завести массив. Нам не нужны результаты каждой итерации,

нам нужен только конечный ответ. Поэтому нам будет вполне

достаточно ОДНОЙ, но изменяющейся в цикле, ячейки q.

*/

 

#include

 

/* Еще одно новое ключевое слово - const. Обозначает константы.

В отличие от переменных, такие имена нельзя изменять.

То есть, если где-то потом попробовать написать epsilon =...;

то это будет ошибкой.

*/

const double epsilon = 0.0000001; /* точность вычислений */

 

/* Функция вычисления модуля числа */

double doubleabs(double x){

if(x < 0) return -x;

else return x;

}

 

/* Функция вычисления квадратного корня */

double sqrt(double x){

 

double sq = x;

 

/* Такая конструкция есть просто склейка двух строк:

double sq;

sq = x;

Называется это "объявление переменной с инициализацией".

*/

 

while(doubleabs(sq*sq - x) >= epsilon){

sq = 0.5 * (sq + x/sq);

}

return sq;

}

 

void main() {

int n;

 

for(n=1; n <= 100; n++)

printf("sqrt(%d)=%lf\n",

n, sqrt((double) n)

);

 

}

 

/*

Здесь в операторе printf() мы печатаем ДВА выражения.

ФОРМАТ ЗНАЧЕНИЕ

------ --------

%d -- n

%lf -- sqrt((double) n)

 

По формату %d печатаются значения типа int.

По формату %c печатаются значения типа char.

По формату %lf (или %g) печатаются значения типа double.

 

Что значит "напечатать значение выражения sqrt(xxx)"?

Это значит:

- вызвать функцию sqrt() с аргументом, равным xxx;

- вычислить ее;

- возвращенное ею значение напечатать по формату %lf,

то есть как действительное число.

 

Заметьте, что тут возвращаемое значение НЕ присваивается

никакой переменной, мы не собираемся его хранить.

 

Точно так же, как в операторе x = 12 + 34;

12 и 34 не хранятся ни в каких переменных,

а оператор

 

printf("%d\n", 12);

 

печатает ЧИСЛО 12, а не переменную.

 

Точно так же, как можно писать

 

double z;

 

z = sqrt(12) + sqrt(23);

 

где значение, вычисленное каждой функцией, НЕ хранится

в своей собственной переменной (такая переменная на самом

деле существует в компьютере, но программисту она не

нужна и недоступна).

Или

 

z = sqrt(sqrt(81));

 

(корень из корня из 81 --> даст 3)

 

Далее, что означает конструкция (double) n?

Функция sqrt() требует аргумента типа double.

Мы же предлагаем ей целый аргумент

 

int n;

 

Целые и действительные числа представлены в памяти

машины ПО-РАЗНОМУ,

поэтому числа

 

12 и 12.0 хранятся в памяти ПО-РАЗНОМУ.

 

Машина умеет преобразовывать целые числа в действительные

и наоборот, надо только сказать ей об этом.

Оператор (double) x

называется "приведение типа к double".

 

Заметим, что часто преобразование типа

выполняется автоматически.

 

Так, например, при сложении int и double

int автоматически приводится к double, и результат

имеет тип double.

 

int var1;

double var2, var3;

 

var1 = 2;

var2 = 2.0;

var3 = var1 + var2;

 

что означает на самом деле

 

var3 = (double) var1 + var2;

 

var3 станет равно 4.0

 

Более того, к примеру тип char - это тоже ЦЕЛЫЕ ЧИСЛА из интервала

0...255. Каждая буква имеет код от 0 до 255.

 

*/

* 18_POINTERS.txt *

 

УКАЗАТЕЛИ

=========

void f(int x){

x = 7;

}

 

main(){

int y = 17;

f(y);

printf("y=%d\n", y); /* печатает: y=17 */

}

 

В аргументе x передаётся КОПИЯ значения y,

поэтому x=7; не изменяет значения у.

Как все же сделать, чтобы вызываемая функция

могла изменять значение переменной?

 

Отбросим два способа:

 

- объявление y как глобальной

(много глобальных переменных - плохой стиль),

 

- y=f(y);

(а что если надо изменить МНОГО переменных?

return, к несчастью, может вернуть лишь одно значение).

 

Используется новая для нас конструкция: УКАЗАТЕЛЬ.

 

Пример (@)

 

void f(int *ptr){ /* #2 */

*ptr = 7; /* #3 */

}

 

main (){

int y=17;

 

f(&y); /* #1 */

printf("y=%d\n", y); /* печатает: y=7 */

}

 

Ну как, нашли три отличия от исходного текста?

 

Мы вводим две новые конструкции:

 

&y "указатель на переменную y" или

"адрес переменной y"

 

*ptr означает "разыменование указателя ptr"

(подробнее - позже)

 

int *ptr; означает объявление переменной ptr,

которая может содержать в себе

указатель на переменную,

хранящую int-число.

 

 

Для начала определим, что такое указатель.

 

int var1, var2, z; /* целочисленные переменные */

int *pointer; /* указатель на целочисленную переменную */

 

var1 = 12;

var2 = 43;

pointer = &var1;

 

Мы будем изображать указатель в виде СТРЕЛКИ;

это хороший прием и при практическом программировании.

________

/pointer/

_/_______/_

| значение| Переменная, хранящая указатель

| есть | (адрес другой переменной)

| |

| &var1 |

| |

|_______|_|

|

|&var1 - сам указатель на var1 -

| "стрелка, указывающая на переменную var1".

V Она обозначается &var1

________

/ var1 /

_/_______/_

| значение|

| есть |

| 12 |

|_________|

 

Таким образом, УКАЗАТЕЛЬ - это "стрелка, указывающая на некий ящик-переменную".

Начало этой стрелки можно (в свою очередь) хранить в какой-нибудь переменной.

 

При этом, если стрелка указывает на переменную типа int,

то тип переменной, хранящей начало стрелки, есть int *

 

Если типа char, то тип - char *

 

АДРЕС (указатель на) можно взять только от переменной или элемента массива,

но не от выражения.

 

int x;

int arr[5];

 

Законно &x стрелка на ящик "x"

& arr[3] стрелка на ящик "arr[3]"

 

Незаконно &(2+2) тут нет именованного "ящика",

на который указывает стрелка,

да и вообще ящика нет.