Сортировка методом прямого включения

Такой метод широко используется при игре в карты. Элементы мысленно делятся на уже «готовую» последовательность а₁…а_i-1 и исходную последовательность а_i…а_n. При каждом шаге, начиная с i=1 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется в нужное место.

Ход сортировки массива {44, 55, 12, 42, 94, 18, 6, 67} методом прямого включения: 

Метод сортировки
for(i=1; i<N; i++) { vsp = a[i]; for(j=i-1; vsp<a[j]&&j>=0; j--) a[j+1] = a[j]; a[j+1] = vsp; }

Cортировка методом прямого выбора

Этот прием основан на следующих принципах:

1. выбирается элемент с наименьшим значением;

2. он меняется местами с первым элементом а1;

3. затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.

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

Метод сортировки
for(i=0; i<N; i++) { vsp = a[i]; m = i; for(j=i+1; j<N; j++) if(a[j]<vsp) { m = j; vsp = a[j]; } a[m] = a[i]; a[i] = vsp; }

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

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

Метод сортировки
for(i=0; i<N; i++) { for(j=N-1; j>i; j--) if(a[j-1]>a[j]) { vsp = a[j]; a[j] = a[j-1]; a[j-1] = vsp; } }

Такой метод широко известен под именем пузырьковая сортировка.

22) Двухмерный массив.

Двумерный массив - это одномерный массив, элементами которого являются одномерные массивы. Другими словами, это набор однотипных данных, имеющий общее имя, доступ к элементам которого осуществляется по двум индексам. Наглядно двумерный массив удобно представлять в виде таблицы, в которой n строк и m столбцов, а под ячейкой таблицы, стоящей в i-й строке и j-м столбце понимают некоторый элемент массива a[i][j].

23) Функция в языке си. Описание, прототип, параметры функции.

Функция - это самостоятельная единица программы, созданная для решения конкретной задачи. Функция в языке С играет ту же роль, что и подпрограммы или процедуры в других языках. Функциями удобно пользоваться, например, если необходимо обработать один и тот же код программы. Как и переменные, функции надо объявлять (declare). Функцию необходимо объявить до её использования. Запомните это простое правило - сначала объяви, а потом используй.  Каждая функция языка С имеет имя и список аргументов (формальных параметров). Функции могут возвращать значение. Это значение может быть использовано далее в программе. Так как  функция может вернуть какое-нибудь значение, то обязательно нужно указать тип данных возвращаемого значения. Если тип не указан, то по умолчанию предполагается, что функция возвращает целое значение (типа int). После имени функции принято ставить круглые скобки (это касается вызова функции её объявления и описания). В этих скобках перечисляются параметры функции, если они есть. Если у функции нет параметров, то при объявлении и при описании функции вместо <список параметров> надо поставить void - пусто.

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

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

Список параметров не может быть опущен. Функция, которая не требует параметров, должна иметь пустой список либо список, состоящий из одного ключевого слова void. Например, следующие объявления эквивалентны: int fork(); int fork( void ); Такой список состоит из названий типов, разделенных запятыми. После имени типа может находиться имя параметра, хотя это и необязательно. В списке параметров не разрешается использовать сокращенную запись, соотнося одно имя типа с несколькими параметрами: int manip( int vl, v2 ); // ошибка int manip( int vl, int v2 ); // правильно Имена параметров не могут повторяться. Имена, фигурирующие в определении функции, можно и даже нужно использовать в ее теле. В объявлении же функции они не обязательны и служат средством документирования ее интерфейса. Например: void print( int *array, int size ); Имена параметров в объявлении и в определении одной и той же функции не обязаны совпадать. Однако употребление разных имен может запутать пользователя. С++ допускает сосуществование двух или более функций, имеющих одно и то же имя, но разные списки параметров. Такие функции называются перегруженными. О списке параметров в этом случае говорят как о сигнатуре функции, поскольку именно он используется различения разных версий одноименных функций. Имя и сигнатура однозначно идентифицируют версию.

24) Механизм передачи параметров. Формальные и фактические параметры.

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

Передача параметров по значению предусматривает следующие моменты:

Компилятолр выделяет специальную память для формальных параметров. При этом для параметров типа float выделяется память как для величины типа double, а для параметров типа char и short int выделяется место как для параметра типа int. Если же параметром является массив, то формируется указатель на начало массива и он служти для представления массива параметров в теле функции.

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

Значения фактических параметров заносятся в память, выделенную для фактических параметров. При этом, как было уже сказано выше, тип float преобразуется в double, а char и short int - в тип int.

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

Функция не оказывает никакого влияния на свои фактические параметры. Не меняет их значения.

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

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

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

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

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

Формальные параметры - это параметры которые мы объявляем в заголовке функции при описании.

Фактические параметры - это параметры которые мы подставляем при вызове функции.

Про фактические параметры больше не нашел, ну я думаю и так понятно, что это ;)

25) Функция. Параметры передаваемые по значению.

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

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

Передача параметра

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

Передача параметра по значению

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

Пример на С++:

#include <iostream>

using namespace std; // для использования cout

void f(int x)

{

// передача параметра по значению

cout << x;

x = 1;

cout << x;

}

26) Функции. Параметры передаваемые по адресу.

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

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

Передача параметра по адресу

Если необходимо именно изменить переменную из внешней, по отношению к вызываемой функции, области видимости, можно копировать адрес переменной, подлежащей изменению. Соответственно при вызове функции g(&x) приходится использовать операцию взятия адреса. Эта техническая деталь отвлекает внимание программиста от логики прикладной программы, однако в случаях невозможности передачи по ссылке может оказаться единственным решением.

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

Пример на С++:

#include <iostream>

using namespace std; // для использования cout

void g(int* x)

{

// передача параметра по адресу

cout << *x;

*x = 2;

cout << *x;

}

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

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

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

Как известно, в Си фактические параметры, передаваемые функции, ставятся в соответствие формальным параметрам, определенным в заголовке функции. Если в функции объявлено три параметра, то при ее вызове должно быть передано также три значения. При знакомстве сфункциями, такими как рriпtf или scanf, можно обратить внимание на то, что эти функции поддерживают переменное число параметров. Например, все следующие вызовы функции printf являются корректными:

printf("1001 совет по C/C++");

printf("%d %s", 1001, "совет по C/C++");

printf("%d %d %d %d %d, 1, 2, 3, 4, 5);

printf("%f %s %s %d %х", salary, name, state, age, id);

Как будет разъяснено в С272, используя макрокоманды va_arg, va_end и va_start, которые определены в заголовочном файле stdarg.h, можно создать свои собственные функции, поддерживающие переменное число параметров. С помощью макрокоманд параметры по существу извлекаются из стека, по одному за каждое обращение к макрокоманде, пока не будет получен последний параметр. При получении параметров с использованием этих макрокоманд следует знать тип каждого из параметров. В случае printf для отслеживания типа параметров используются спецификаторы формата, такие как %d, %s и %f.

28) Указатель на функцию

В языке "с" сами функции не являются переменными, но

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

можно обрабатывать, передавать другим функциям, помещать в

массивы и т.д. Мы проиллюстрируем это, проведя модификацию

написанной ранее программы сортировки так, чтобы при задании

необязательного аргумента -N она бы сортировала строки ввода

численно, а не лексикографически.

Сортировка часто состоит из трех частей - сравнения, ко-

торое определяет упорядочивание любой пары объектов, перес-

тановки, изменяющей их порядок, и алгоритма сортировки, осу-

ществляющего сравнения и перестановки до тех пор, пока

объекты не расположатся в нужном порядке. Алгоритм сортиров-

ки не зависит от операций сравнения и перестановки, так что,

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

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

Именно такой подход используется в нашей новой программе

сортировки.

Как и прежде, лексикографическое сравнение двух строк

осуществляется функцией STRCMP, а перестановка функцией

SWAP; нам нужна еще функция NUMCMP, сравнивающая две строки

на основе численного значения и возвращающая условное указа-

ние того же вида, что и STRCMP. Эти три функции описываются

в MAIN и указатели на них передаются в SORT. В свою очередь

функция SORT обращается к этим функциям через их указатели.

мы урезали обработку ошибок в аргументах с тем, чтобы сосре-

доточиться на главных вопросах.

29) Вызов функции. Оператор return

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

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

30) Функция main() и ее параметры.

Функция main () — это, конечно, частный случай функции вообще. Функции являются основными “строительными блоками” программы, или подпрограммами. Они, в свою очередь, строятся из операторов, составляющих тело функции. Каждый оператор оканчивается точкой с запятой (;). В общем виде функция определяется таким образом:

Возвращаемый_ тип_ имя функции(список_ параметров)

{

// В фигурных скобках заключено тело функции,

// составленное из отдельных операторов.

тело_функции

}

строки, т. е. имен файлов, ключей, опций и вообще всего, что вы вводите с клавиатуры после подсказки DOS, запуская программу. Конечно, программа не обязана воспринимать какие-либо команды, указываемые в строке запуска, однако в любом случае функции main () передаются два параметра — число аргументов/включая имя, под которым запущена программа (argc), и массив указателей (argv) на отдельные аргументы (выделенные элементы командной строки). Забегая вперед, приведем пример, который распечатывает по отдельности все “аргументы” строки, введенной пользователем при запуске:

#include <stdio.h>

int main(int argc, char *argv[])

{

int i;

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

printf ( "%s\n", argv[i]);

return 0;

}

31) Рекурсивные функции.

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

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

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

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

32) Локальные и глобальные переменные.

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

Чаще всего блоком программы, в котором объявлены локальные переменные, является функция. Рассмотрим, например, следующие две функции:

void func1(void)

{

int x;

x = 10;

}

void func2(void)

{

int x;

x = -199;

}

Целая переменная х объявлена дважды: один раз в func1() и второй — в func2(). При этом переменная х в одной функции никак не связана и никак не влияет на переменную с тем же именем в другой функции. Это происходит потому, что локальная переменная видима только внутри блока, в котором она объявлена, за пределами этого блока она невидима.По умолчанию локальные переменные хранятся в стеке. Стек — динамически изменяющаяся область памяти. Вот почему в общем случае локальные переменные не сохраняют свое значение в период между вызовами функций. Локальные переменные можно инициализировать каким-либо заранее заданным значением. Это значение будет присвоено переменной каждый раз при входе в тот блок программы, в котором она объявлена.

Глобальные переменные

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

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

33) Символьные переменные и константы. Объявление, инициализация, операции.

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

Константа	Формат	Примеры
Символьная	Один или два символа заключенные в апострофы	'A', 'ю', '*', '\0', '\n'

Для символьных переменных введен базовый тип char. Описание символьных переменных имеет вид:

char список_имен_переменных;

Для ввода и вывода символьных значений в форматных строках библиотечных функций printf() и scanf() используется спецификация преобразования %c – для работы с одним символом и %s – для работы с массивом символов.

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

34) Массив символов. Объявление, инициализации, операции.

В языке Си нет отдельного типа для строк. Работа со строками реализована через массивы. Хотя в других языках програмимирования имеется такой тип данных как string - строки. В Си символьная строка - это одномерный массив типа char, заканчивающийся нулем - нулевым байтом. Символьная константа '\0' определена для нулевого байта. Поэтому, если в массиве должно содержаться N символав, то нужно опеределять массив как массив для N+1 элемента. Например, когда мы говорим, что массив содержит 100 элементов: a[1], a[2], ..., a[99], то это значит, что элемент a[100] содержит ноль. Обычный одномерный массив можно трактовать как строку символов. Язык С допускает строковые константы, хотя в языке и нет специального типа для таких констант. Делается это через массив. Строковая константа - это набор литер. В конце строковой константы не нужно ставить символ '\0'. Это сделает сам компилятор при обработке массива. Например, константа "Borland C++" будет выглядеть в памяти как массив символов:

B o r l a n d C + + \0

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

char stroka[ ] = "привет";

Инициализируется массив символов из 7 элементов, последним элементом (седьмым) будет символ '\0', которым завершаются все строковые литералы.

В том случае, если задается размер массива, а строковый литерал длиннее, чем размер массива, то лишние символы отбрасываются.

Следующее объявление инициализирует переменную stroka как массив, состоящий из семи элементов.

char stroka[5] = "привет";

В переменную stroka попадают первые пять элементов литерала, а символы 'Т' и '\0' отбрасываются.

Если строка короче, чем размер массива, то оставшиеся элементы массива заполняются нулями.

Отметим, что инициализация переменной типа tab может иметь следующий вид:

union tab pers1 = "Антон";

и, таким образом, в символьный массив попадут символы:

'А','Н','Т','О','Н','\0',

а остальные элементы будут инициализированы нулем.