Способы передачи параметров:

• по значению – копируются значения фактических параметров в формальные, при изменении формальных параметров значения соответствующих фактических параметров не изменятся;

• по адресу – в стеке копии адресов фактических параметров. Изменяются исходные значения в ячейках с этими адресами;

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

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

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

• Если список формальных параметров заканчивается многоточием, это означает, что при ее вызове на этом месте можно указать еще несколько параметров. Проверка соответствия типов для этих параметров не выполняется, charиshortпередаются какint, аfloat– какdouble. Например,int printf(const char*, …);

Функция main()

Текущее количество фактических параметров при вызове передается тремя способами:

1. С помощью отдельного параметра счетчика;

2. С помощью параметра ограничителя, значение которого отмечает конец списка параметров;

3. Форматный строй, в котором передается спецификации параметров.

4. В языке С заданы два встроенных аргумента функции main:

5. main(int argc, char* argv[ ]){…}

6. main(int argc, char* argv[ ], char* env[ ]){…}

7. Два первых параметра используются для передачи аргументов командной строки. Третий используется для доступа к параметрам среды операционной системы. Эти три аргумента доступны только в функции main.

8. argcсодержит количество аргументов командной строки. Значение всегда больше 1, т.к. имя вызываемой программы трактуется как первый аргумент.

9. argv– указатель на массив указателей. Каждый элемент массива содержит указатель на отдельный параметр командной строки.

10. env– это указатель на массив строк, который содержит установку среды.

11. Аргументы функции mainпозиционно зависимы, при этом третий аргумент можно не объявлять, но если он объявлен, то и первые два тоже должны быть объявлены.

Вопрос № 15. Рекурсивная функция, примеры.

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

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

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

1) в стеке резервируется место для формальных параметров, в которые записываются значения фактических параметров;

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

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

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

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

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

Вопрос №16. Структуры данных (СД): динамические и статические, с произвольным и с последовательным доступом. Абстрактный тип данных. Характерные особенности АТД (обобщение и инкапсуляция)

Тип данных - это «шаблон» по которому выделяется память при объявлении переменных.

Типы данных бывают базовыми и производными.

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

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

К АТД относятся:

• последовательность;

• стек;

• очередь;

• дек;

• однонаправленный линейный список;

• двунаправленный линейный список.

Реализация АТД возможна, используя: 1) непрерывную область памяти, как правило реализует стек, 2) динамическая реализация.

Вопрос №17. Стек. Описание, набор операций, реализация а) на основе массива; б) на основе односвязного списка

1. Стек. Доступны две операции: PUSH– добавить в стек,POP– изъять из стека. Операторы:

• Сделать стек пустым;

• Стек пуст/не пуст?

• Добавить элемент в стек (PUSH);

• Взять элемент из стека;

• Показать вершину;

• Удалить вершину стека (POP

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

Операторы:

• Сделать очередь пустой;

• Очередь пустая/непустая?

• Добавить элемент в очередь;

• Показать начало или конец очереди;

• Удалить элемент из начала очереди.

Вопрос №19. Дек. Описание, набор операций, реализации а) на основе массива; б) на основе двусвязного списка.

Операторы:

• Сделать дек пустым;

• Дек пуст/не пуст?

• Добавить элемент в начало/конец дека;

• Показать начало или конец дека;

• Удалить элемент из начала/конца дека.

Вопрос №20. L1-список. Описание, набор операций, реализация а) на основе массива; б) на основе односвязного списка; в) на основе односвязного списка с буферным элементом в начале или в конце; г) на основе кольцевого односвязного списка с буферным элементом.

Операторы:

• Сделать список пустым;

• Список пуст/не пуст?

• Установить указатель в начало списка;

• Указатель в конце списка?

• Передвинуть указатель на один элемент вправо;

• Добавить элемент по положению указателя;

• Показать элемент по положению указателя;

• Удалить элемент по положению указателя.

Однонаправленный список чаще всего реализуется динамически, так как это тот АТД, размеры которого могут меняться с течением времени. Для того чтобы однонаправленный список реализовать нужно завести структуру (struct), которая бы отображала элемент списка.

Как правило в этой структуре одно поле отводится для хранения значения элемента списка:

• Одно поле – однонаправленный;

• Два поля – двунаправленный;

• Более двух полей – мультинаправленный.

Хранят адреса других элементов списка.

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

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

Вопрос №21. L2-список. Описание, набор операций, реализация а) на основе массива; б) на основе двусвязного списка; в) на основе двусвязного списка с буферным элементом в начале или в конце, или с двумя буферными элементами; г) на основе кольцевого двусвязного списка с буферным элементом.

Указатель может двигаться как вправо, так и влево.

Операторы:

• Сделать список пустым;

• Список пуст/не пуст?

• Установить указатель в начало/конец списка;

• Указатель в начале/конце списка?

• Передвинуть указатель на один элемент;

• Добавить элемент по положению указателя;

• Показать элемент по положению указателя;

• Удалить элемент по положению указателя.

Вопрос №22. Определение дерева. Корень. Лист. Потомок. Предок. Обходы деревьев (прямой, обратный, симметричный). Деревья выражений.

Дерево- это совокупность элементов (узлов), и отношений образующих их структур.

Вверху находится корень, внизу - листья.

• Нулевое дерево- это дерево без узлов.

• Путь из узла n₁в узел n_k- это последовательность узлов n₁, n₂,… n_k, где для всех 1ik узел n_i является родителем узла n_i+1.

• Длина пути- это число, на 1 меньше числа узлов, составляющих путь.

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

• Высота узла- это длина самого длинного пути.

• Высота дереваравна высоте корня.

• Высота узларавна длине пути из корня до этого узла.