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

План занятия

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

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

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

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

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

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

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

Объявление переменных в 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
}

Математические функции объявлены в заголовочном файле <math.h>.

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

Основные типы: 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 мы можем взаимодействовать с пользователем.

Функции ввода-вывода объявлены в заголовочном файле <stdio.h>.

printf принимает в качестве аргументов строку, которую он и печатает. В этой строке могут встречаться специальные последовательности символов, которые printf заменяет на свои последующие аргументы. Чтобы подставить int, используется %d, чтобы float - %f. Если напутать с аргументами и их типами, то программа свалится во время исполнения, так что внимательнее с этим.

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

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.

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

В языке 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-ти точек и записывает их в статический массив (аналогично предыдущей задаче). Надо отсортировать точки по возрастанию удалённости от начала координат, причем запрещается менять массив с точками. Вместо этого предлагается создать массив из указателей на точки и сортировать этот массив любым известным способом сортировки. При этом сделайте функцию, принимающую указатель на точку и возвращающую расстояние до начала координат. При сортировке пользуйтесь этой функцией.

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, задающие отрезки. Выход программы: для каждого отобранного отрезка строка с его началом и концом. Если возникли сложности с решением, ознакомьтесь со статьёй, содержащей решение и обсуждение этих задач в общем виде.

5. Как я помню, кое-кто из слушателей любит сложные задачи, при решении которых нужно не столько "кодить", сколько придумывать элегантный алгоритм. Такие студенты приглашаются к решению задачек с сайта codeforces.com, там как раз такие задачи и есть система сдачи и оценки решений. Приятного решения!

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

Конспекты с http://info.fenster.name:

• Введение в C

• Лекция про типы данных

• Посимвольный ввод/вывод, массивы

• Указатели, функция scanf, передача массивов в функцию

• Указатель

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

Как писать модули на современном Lua (англ.)