= Числовые типы данных в С. Статические массивы. Структуры =

== План занятия ==

 * Контрольная по типизации и процессу сборки программ на C
 * Разбор домашнего задания
 * Типы памяти в C (стековая, статическая, динамическая)
 * Объявление переменных в C, простейшие вычисления, функции
 * Числовые типы данных в С
 * Статические массивы
 * Структуры
 * printf, scanf
 * if, for
 * Понятие Указатель
 * Обсуждение прогресса по учебным проектам (Github!)

== Типы памяти в C ==

Переменные языка C могут существовать в трёх типах памяти:

 * на стеке,
 * в статической памяти,
 * в динамической памяти.

Если проводить аналогии с Lua, то '''стековая''' переменная C - это локальная переменная Lua (живёт только пока активна область видимости, где её объявили). Все переменные, которые мы объявляли выше, относятся в стековым переменным.

'''Статическая''' переменная - существует всё время существования программы. Объявляются с ключевым словом static или просто объявляются снаружи от функций. Можно провести аналогию с глобальными переменными Lua. И их тоже надо избегать.

'''Динамическая''' память - это память, которую программа запрашивает и отдает, руководствуясь правилами, которые составил программист. Есть две функции (malloc, free), которые можно вызвать в любой момент, они соответственно выделяют память указанного размера и возвращают её. Более подробно мы обсудим этот тип памяти позже, когда будем изучать указатели.

{{{#!wiki note
За удалением стековых переменных следит компилятор, а за удалением динамических переменных следит программист!!!
}}}

== Объявление переменных в C, простейшие вычисления, функции ==

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

Для начала запомните всего один тип данных: int. В нем хранится целое число.

Объявим переменную типа int:
{{{
int foo;
}}}

Присвоим ей значение:
{{{
foo = 42;
}}}

Обратите внимание, что пока мы не присвоим значение переменной, её значение может быть произвольным. К примеру, если бы мы объявили переменную и сразу же распечатали её значение, то, скорее всего, мы увидели бы какое-то произвольное "мусорное" значение.

Как вы заметили, каждый оператор в C завершается точкой с запятой.

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

{{{
int x = 1;
int y = x * x + x - 2;
y = y - x;
}}}

В Lua мы использовали local для объявления новой локальной переменной. В C это делается похожим образом, только вместо local пишется тип переменной.

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

'''Функции''' объявляются вот так:

{{{
тип-возврата имя-функции(список аргументов) {
  тело функции (код)
}
}}}

Возврат из функции осуществляется с помощью '''return'''.

Пример функции, которая принимает числа x и y и возвращает их сумму, и кода, использующего эту функцию:

{{{
int sum(int x, int y) {
  return x + y;
}

int main() {
  int a = 5;
  int b = 7;
  int c = sum(a, b);
}
}}}

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

Весь код, который что-то делает, находится внутри функций.

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

{{{
void useless_func(int x) {
  x = x + 1;
}

int main() {
  int y = 0;
  useless_func(y);
  printf("%d\n", y); -- prints 0
}
}}}

'''Математические функции''' объявлены в заголовочном файле [[http://www.cplusplus.com/reference/cmath/|<math.h>]].

{{{#!wiki warning
Если функция, возвращающая не void, завершилась, так ничего не вернув (то есть, исполнение дошло до конца функции, так и не встретив return), то это приведёт к ошибке во время исполнения. Программа свалится. Ещё хуже, если не свалится, что тоже может иметь место. Нахождению таких ошибок способствует использование статических анализаторов кода (которые могут быть встроены в продвинутые компиляторы).

К функции main это не относится. Это единственная функция, которая имеет право ничего не вернуть. В таком случае считается, что она вернула 0.
}}}

== Числовые типы данных в С ==

Основные типы: '''int''' (целое число), '''float''' (число с плавающей точкой, нецелое).

Все типы могут иметь знак (положительное или отрицательное) или не иметь знак. По умолчанию все числовые типы имеют знак. Чтобы превратить тип в '''беззнаковый''', надо приписать к нему спереди слово "unsigned". Все значение, которые могут принимать переменные беззнаковых типов, больше или равны нулю.

Тип int и ему подобные представляет собой двоичную запись хранимого числа. В памяти на него отводится несколько байт (обычно 4), в которых и хранится двоичная запись числа. Если тип знаковый, то один бит отводится на хранение знака. Таким образом, тип int может принимать значения от {{{-2147483647 (-2^31+1)}}} до {{{2147483647 (2^31-1)}}} включительно.

Тип float хранит два числа (m, мантисса и e, экспонента) в двоичной записи. Значение всего числа составляет m * 16 ^ e. Обе составляющие имеют знак. Тем самым, тип float может принимать дробные значения и очень большие значение, однако чем больше его значение, тем менше его точность (если считать её в количестве знаков после запятой). Типичный размер типа float - 4 байта.

На практике тип float часто оказывается недостаточно точным, поэтому лучше использовать тип double, который устроен так же, как float, но в 2 раза больше. В частности, все числа в Lua хранятся в форме double. Его точности хватает, чтобы "покрыть" все возможные значения типа int.

Целые типы тоже не ограничиваются int'ом и могут иметь разные размеры: 1 байт (char), 2 байта (типичный размер для short), 8 байт (типичный размер для long long int). Обратите внимание, что '''размер char всегда ровно 1 байт'''. В char хранят символы, а несколько char подряд образуют строки, но об этом позже.

Чтобы получить символ в коде, используются одинарные кавычки: 'x'. Не путайте со строками, для них используются двойные кавычки: "xxxx".

== Статические массивы ==

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

При объявлении тип элемента пишется до переменной, а число элементов массива заключается в квадратные скобки и пишется после имени переменной.

Объявим статический массив из 10 чисел:

{{{
int array[10];
}}}

В данный момент элементы массива имеют произвольные значения. Запишем в них что-нибудь:

{{{
array[0] = 1;
array[1] = 2;
array[2] = array[0] + array[1];
int x = 5;
array[x] = x * array[0];
}}}

Выше показано, как получать доступ к элементам массива. Так мы можем читать и писать в массив. Если по ошибке подать в качестве индекса несуществующий индекс, то программа свалится во время исполнения. Это довольно неприятный момент при программировании на C, но так надо. Проверяйте индексы!

Двумерные массивы.

{{{
int array[10][10];
array[0][0] = 0;
}}}

Аналогично можно сделать трёхмерный массив и другие многомерные массивы.

== Структуры ==

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

Объявим структуру Point, в которой есть два числовых поля (x и y):

{{{
typedef struct {
  int x;
  int y;
} Point;
}}}

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

{{{
Point p1;
p1.x = 1;
p1.y = 10;
Point p2 = p1; // p2 is copy of p1, thay are not linked with each other
Point points_array[10];
points_array[0] = p1;
points_array[1] = p2;
points_array[1].x = 100;
}}}

Функция, принимающая две точки и считающая их скалярное произведение:

{{{
int scal_mul(Point p1, Point p2) {
  return p1.x * p2.x + p1.y * p1.y;
}
}}}

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

== printf, scanf ==

С помощью функций printf и scanf мы можем взаимодействовать с пользователем.

Функции ввода-вывода объявлены в заголовочном файле [[http://www.cplusplus.com/reference/cstdio/|<stdio.h>]].

[[http://www.cplusplus.com/reference/cstdio/printf/|printf]] принимает в качестве аргументов строку, которую он и печатает. В этой строке могут встречаться специальные последовательности символов, которые printf заменяет на свои последующие аргументы. Чтобы подставить int, используется %d, чтобы float - %f. Если напутать с аргументами и их типами, то программа свалится во время исполнения, так что внимательнее с этим.

{{{
int x = 5;
float y = 7.0;
printf("x is %d, y is %f", x, y);
}}}

[[http://www.cplusplus.com/reference/cstdio/scanf/|scanf]] "вытаскивает" значения из ввода пользователя. Он принимает такую же строку с подстановками, как и printf, после которой принимает указатели на переменные, в которые он пишет результат. Что такое указатель, мы рассмотрим позже. Нам пока важно, как вызывать scanf. Пример: мы хотим, чтобы пользовать ввёл "x = какое-то число" и достать из этого число.

{{{
int main() {
	int x;
	scanf("x = %d", &x);
	printf("%d\n", x);
}
// if a user enters "x = 123", the program prints "123"
}}}

Таким образом, мы подаем в scanf переменные, в которых хотим получить результат, а перед переменными пишем амперсанд (&), чтобы получить указатель на них. Подробнее об указателях - ниже и в других занятиях.

Чаще нам нужно просто взять от пользователя само значение, без "сопроводительного текста":

{{{
int x;
scanf("%d", &x);
}}}

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

== if, for ==

if ведёт себя также, как в других языках (Lua, Python).

{{{
int x;
scanf("%d", &x);
if (x == 1) {
  printf("You entered 1\n");
} else {
  printf("You entered not 1\n");
}
}}}

Блоки кода обрамляются фигурными скобками.

"else if" пишется в два слова, а не в одно, как было в Lua или в Python.

{{{
int x;
scanf("%d", &x);
if (x == 1) {
  printf("You entered 1\n");
} else if (x == 2) {
  printf("You entered 2\n");
} else {
  printf("You entered neither 1 nor 2\n");
}
}}}

'''Логические выражения''':
{{{
И         &&
ИЛИ       ||
НЕ        !
РАВНО     ==
НЕ РАВНО  !=
}}}

'''Оператор for''' служит для создания циклов. Форма записи следующая:

{{{
for (оператор А; операция Б; оператор В) {
  оператор Г;
}
}}}

(Напоминание: операция - это то, что что-то возвращает, к примеру x == 1. Оператор - это то, что совершает некоторые действия.)

Пояснения к записи: for сначала выполняет А, потом проверяет истинность Б. Если Б истинно, то выполняет Г, потом выполняет В. Потом снова проверяет Б и т.д.

Для выхода из цикла служит '''break''', а для перехода из середины Г сразу к В служит '''continue'''.

Пример:

{{{
int a[10];
int i;
for (i = 0; i < 10; i++) {
  a[i] = i * i;
}
}}}

Мы заполнили массив квадратами чисел от 0 до 9 включительно.

== Понятие Указатель ==

Выше мы говорили про память компьютера как про последовательность байт, в которой размещаются переменные. Пришло время узнать ещё одну вещь о памяти: '''каждый её элемент имеет свой порядковый номер''', который называют '''адресом'''. Адреса в свою очередь тоже можно хранить в памяти. Такой тип данных, в котором хранится адрес, называется указателем. Указатель можно себе представить как целое число, в котором хранится порядковый номер какого-то байта в памяти.

'''Указатель - очень важный тип'''. Говорят, что понимание указателя отличает программиста от обычного человека, которому довелось писать код. С помощью указателей строится очень много важных вещей, в том числе продвинутые типы данных, такие как деревья, связные списки и другое. Мы сейчас не будем все их обсуждать, а поговорим об указателях как таковых.

В указателе мы будем хранить не абы какой адрес, а адрес какой-то переменной. Имея указатель, можно получить значение, на которое он указывает ('''разыменование''', '''indirection'''). Ещё в таких случаях говорят "пройти по указателю". Имея переменную, можно узнать её адрес ('''взятие адреса''', '''Address-of Operator'''). Теперь вы знаете две основные операции, в которых участвуют указатели. Ниже мы разберем, как всё это делать в коде на языке C.

{{{#!wiki warning
При пользовании указателями важно следить, чтобы указатель указывал на "живую" переменную. Если мы сделаем указатель на переменную, а потом эта переменная умерла (к примеру, это была стековая переменная, которая вышла из области видимости), а потом мы будем пытаться обращаться со значением, на которое указывает указатель, то получим очень неприятную ошибку, происходящую во время исполнения программы.
}}}

Перейдём к практике.

В языке C в тип указателя входит то, на какой тип он указывает. Таким образом, к каждому типу "прилагается" соответствующий тип-указатель. Чтобы сделать из типа X тип "указатель на X", надо к X приписать звезду:

{{{
int* x;
}}}

Мы только что объявили переменную x как указатель на int.

Как и со всеми типами, в x на данный момент лежит "мусор". Если мы попытаемся пройти по ней, как по указателю (разыменование), то получится ошибка.

Теперь положим в наш указатель адрес какой-нибудь переменной:

{{{
int* x;
int y = 10;
x = &y;
}}}

Вот мы и узнали, как записывается операция взятия адреса в сях. Для этого просто припишите к переменной амперсанд (&).

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

{{{
int arr[2];
int* arr1 = &(arr[1]);
}}}

Теперь у нас есть указатель на один из элементов массива.

Нельзя брать адрес временной переменной, являющейся результатом выражения. Так нельзя: &(x + y).

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

{{{
int z = *x;
}}}

Итак, звезда отвечает за разыменование. Не путайте её с звездой, которую мы писали при объявлении типа указатель! Это две разные звезды. Просто так получилось, что используется один и тот же символ в двух разных случаях.

Изменим значение, на которое ссылается указатель, используя при этом указатель:

{{{
*x = *x + 1;
}}}

Мы увеличили значение y на 1.

'''Операция стрелочка'''. Часто требуется поработать с полями структуры через указатель на эту структуру. Можно было бы писать {{{(*var).xxx}}}, но для этого придумали более короткое обозначение: {{{var->xxx}}}.

== Домашнее задание ==

Прорешать тест c2 на http://kodomoquiz.tk

Все задания рассчитаны на написание программ на языке C. Если затрудняетесь, то напишите решение на Lua. Обратите внимание, что в Lua для массивов и для структур используется один и тот же тип данных: таблица.

 1. Напишите программу, печатающую площадь треугольника. В программу вводятся координаты трёх точек (всего 6 чисел). Объявите структуру "Точка". Данные внутри программы должны храниться в форме статического массива из таких структур. Для хранения координат используйте тип double.
 2. Сортировка точек. Напишите программу, которая запрашивает координаты 5-ти точек и записывает их в статический массив (аналогично предыдущей задаче). Надо отсортировать точки по возрастанию удалённости от начала координат, причем запрещается менять массив с точками. Вместо этого предлагается создать массив из указателей на точки и сортировать этот массив [[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8#.D0.A1.D0.BF.D0.B8.D1.81.D0.BE.D0.BA_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.BE.D0.B2_.D1.81.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B8|любым известным способом сортировки]]. При этом сделайте функцию, принимающую указатель на точку и возвращающую расстояние до начала координат. При сортировке пользуйтесь этой функцией.
 3. Напишите программу, которая обращается к несуществующему элементу массива. Что выдаёт программа? Когда проявится такая ошибка: на этапе компиляции или на этапе исполнения? Как её исправить? Запомните эти вещи, они вам пригодятся.
 4. Спираль. Напишите программу, создающую двумерный массив N на N и заполняющий его числами от 1 до N*N по спирали. Затем программа печатает эту спираль на экран:
  {{{
  1 2 3
  8 9 4
  7 6 5
  }}}
Значение N должно быть записано в программе ровно один раз! Чтобы изменить значение N, изменения в программе должны быть внесены ровно в одном месте.

=== Дополнительные задания ===

 1. Как выглядит функция, которая ничего не принимает, ничего не возвращает и нечего не делает?
 2. Почитайте самостоятельно материалы по C, пока не узнаете что-нибудь, чего не было в лекции.
 3. Разберитесь, что такое '''статический анализатор кода'''. Напишите неправильную функцию, которая должна возвращать int, но ничего не возвращает. Посмотрите, что произойдёт при компиляции и при запуске. Найдите инструмент (возможно, онлайн-сервис), который бы автоматически находил подобные ошибки. Как учащиеся, вы можете бесплатно пользоваться коммерческим анализатором кода PVS-Studio, разработанным нашими соотечественниками.
 4. Две задачи по алгоритмам. (1) Есть линейная молекула ДНК и набор отрезков на ней. Надо отобрать подмножество непересекающихся отрезков, максимальное по числу отрезков. (2) Та же задача, но молекула ДНК кольцевая. Вход программы: на первой строке число отрезков N и длина ДНК L, на последующих N строках пары чисел a b, задающие отрезки. Выход программы: для каждого отобранного отрезка строка с его началом и концом. Если возникли сложности с решением, ознакомьтесь со [[http://habrahabr.ru/company/spbau/blog/254093/|статьёй]], содержащей решение и обсуждение этих задач в общем виде.
 5. Как я помню, кое-кто из слушателей любит сложные задачи, при решении которых нужно не столько "кодить", сколько придумывать элегантный алгоритм. Такие студенты приглашаются к решению задачек с сайта codeforces.com, там как раз такие задачи и есть система сдачи и оценки решений. Приятного решения!

=== Дополнительный материал ===

Конспекты с http://info.fenster.name:
 * [[http://info.fenster.name/clessons/lesson01.pdf|Введение в C]]
 * [[http://info.fenster.name/clectures/lecture06.pdf|Лекция про типы данных]]
 * [[http://info.fenster.name/clessons/lesson02.pdf|Посимвольный ввод/вывод, массивы]]
 * [[http://info.fenster.name/clessons/lesson03.pdf|Указатели, функция scanf, передача массивов в функцию]]
 * [[http://info.fenster.name/clectures/lecture02.pdf|Указатель]]

[[http://habrahabr.ru/post/251091/|Статья про связь между указателями и массивами]] (C и C++). Статья мне нравится. Автор пишет в основном про сишную часть плюсов, однако может быть пока что не вполне понятно. Автор статьи: выпускник МГУ Аскар Сафин.

[[http://hisham.hm/2014/01/02/how-to-write-lua-modules-in-a-post-module-world/|Как писать модули на современном Lua]] (англ.)