Бинарный поиск, для отсортированных массивов

Допустим элементов 2¹⁰= 1024, будет деление 1024, 512, максимум 10 шагов, вычислительная эффективность log₂n. Бинарный поиск является быстрым поиском, на практике разрабатывают алгоритмы, которые должны приближаться к близкому поиску.

 

6.Функции

Функция – это последовательность объявлений и операторов, которой дано имя.

В Си++ для функции должно быть:

1. Объявление или прототип

2. Определение

3. Вызов

В СИ++ правильность вызова контролируется по прототипу.

 

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

 

● Объявление функции или прототип

[класс] тип имя ([список параметров]);

 

Бывает 2 класса:

1. Extern (внешний) – по умолчанию, функция будет видна во всех модулях программы.

2. Static – функция видна только в том модуле, где она объявлена.

Тип: может быть любой, кроме массива и функции, но может быть указатель на массив и на функцию.

Параметры: параметры связывают эту функцию с вызывающей функцией, вызов функции осуществляется следующий образом:

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

F(5)

F(арифм.выраж.)

2. В стеке выделяется память в объеме соответствующем типам формальных параметров.

3. В эти участки памяти копируются значения аргументов, здесь же проверяется соответствие типов, при несовпадении - ошибка.

4. По выходу из функции стек очищается, т.е. все значения аргументов, переданные в стек, теряются.

 

Существует 2 способа передачи параметров функции:

1. По значению

2. По адресу

 

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

 

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

 

Примечание:

1. Из функции нельзя возвращать указатель или ссылку на локальную переменную

2. Если все же необходимо возвратить ссылку, то поступают так:

Int &fun (int c)

{static int b;

Cin >> b;

b+=c;

return b;                             

}

 

● Указатели на функции

Void f(int a) { … }                    // определение

Void (*pf) (int);                           // объявление указателя на функцию

 

Чтобы более определено объявить указатель на функцию используют определение или переопределение типов.

Typedef void (*pf) (int);

 

Указателю можно присвоить адрес функции

pf=&f;                                              // pf=f;

 

Можно вызвать функцию по указателю

Pf(10);

(*pf)(10);

 

 

● Объявление и инициализация массива указателей на функции

Pf menu[] = {&new, &open, &save};

 

Вызов функции:

Menu [2] (5);                                                // вызов save

 

Передача в функцию указателя на функцию:

#include <iostream.h>

Typedef void (*pf) (int);                                          // определение типа указателя на функцию, тип указателя

Void f1 (pf ptr)                                             // функция f1 имеет в качестве параметра указатель на функцию, имя этого параметра ptr, а тип – выше определен

           {ptr(5);}

Void f(int i) {cout << i;}                             // определение функции, тип функции

Void main ()

{

f1(f);                                                                 // вывод числа 5

}

 

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

● Указатель на функцию как возвращаемое функцией значение

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

 

 

● Некоторые виды функций

1. Встроенные функции

Такими функциями объявляют достаточно короткие функции, чтобы можно было в точку вызова поместить ее код

Inline float cube (const float s) {return s*s*s;}

Inline – рекомендация компилятору сделать функцию встроенной

 

2. Функции с параметрами со значениями по умолчанию

Такие функции используются для повышения надежности вызова

 

● Рекурсивные функции

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

Требования к рекурсивным функциям:

1. Должна содержать как минимум 2 ветви – нерекурсивную и рекурсивную, нерекурсивная завершается возвратом, рекурсивная – уменьшает объем задачи и содержит рекурсивный вызов.

Достоинства:

1. Краткая запись

Недостатки:

1. Большие накладные расходы – на рекурсивные вызовы требуется много машинного времени и большие затраты оперативной памяти

2. Основной недостаток, что ограничивает применение рекурсивных функций, - это переполнение стека

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

● Перегрузка функций

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

 

● Шаблоны функций

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

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

Примечание:

1. В угловых скобках может находиться более широкий список параметров

Template <class A, class B, int I, char ch>

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

 

7.Динамические структуры данных

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

К динамическим структурам данных относятся:

1. Стеки

2. Очереди

3. Списки

4. Деревья

5. Графы

6. Сети

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

1. Поле данных

2. Поле указателя на такой же элемент

 

Struct Node

{Data d;                           // поле данных

Node *p;                        //поле указателей

};

 

Стек

Last in – first out

LIFO

 

15 вершина стека

-40

37

25

 

Используются в:

1. Системном ПО

2. Компиляторах

3. При реализации рекурсивных алгоритмов

 

 

Top – указатель на вершину стека

NULL – 0

 

Для работы со стеком определены 2 функции:

1. Функция push – вталкивать (помещать в стек)

2. Pop – выталкивать (делать выборку) из стека

3. Top – указатель на вершину стека

 

Очереди

First in

First out FIFO

Используются:

1. В буферизованном вводе-выводе

2. В моделировании

3. В диспетчеризации задач операционной системы

 

● Очередь приоритетов

В рассмотренной очереди все элементы имеют одинаковый приоритет. На практике обычно элементы с разными приоритетами.

Линейные списки

⇐ Предыдущая123456789Следующая ⇒

Поделиться: