Указатели в С. Динамические массивы. Строки. Указатель на функцию

План занятия

разбор домашнего задания
повторение базовых типов, в том числе указателей
создание динамических массивов, malloc, free, sizeof
typedef
realloc
const
C-строки
sprintf, sscanf
указатель на функцию
обсуждение прогресса по учебным проектам

Разбор домашнего задания

1. Задача про площадь треугольника. Решили на занятии через векторное произведение.

#include <math.h>
#include <stdio.h>

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

Point triangle[3];

float dAbs(float number) {
    if (number >= 0) {
                return number;
    } else {
                return -number;
        }
}

int main() {
    int i;
    for (i = 0; i < 3; i++) {
        scanf("%f %f", &triangle[i].x, &triangle[i].y);
    }
        Point v1, v2;
        v1.x = triangle[0].x - triangle[1].x;
        v1.y = triangle[0].y - triangle[1].y;
        v2.x = triangle[2].x - triangle[1].x;
        v2.y = triangle[2].y - triangle[1].y;
        float vect = v1.x * v2.y - v1.y * v2.x;
        //printf("%f", triangle[1].y);
        //printf("%f %f %f %f", v1.x, v1.y, v2.x, v2.y);
        float square = dAbs(vect) / 2.;
        printf("%f\n", square);
}

2. Задача отсортировать N чисел по возрастанию. N было зафиксировано как константа ARRAY_SIZE = 5.

#include <stdio.h>

const int ARRAY_SIZE = 5; 

int main() {
  int array[ARRAY_SIZE];
  int i;
  for (i = 0; i < ARRAY_SIZE; i ++) {
        scanf("%d", &array[i]);  
    }
  int j;
  for (j = 0; j < ARRAY_SIZE; j ++) {
          int k;
          for (k = j; k < ARRAY_SIZE; k ++) {
                        if (array[k] < array[j]) {
                                int temp;
                                temp = array[k];
                                array[k] = array[j];
                                array[j] = temp;
                        }
          }
  } 
        for ( j = 0; j < ARRAY_SIZE; j ++) {
        printf("%d \n", array[j]);
        
        }

}

Последующий материал на занятии не разбирался - разбор переносится на 10 апреля. К 10 апреля надо доделать ДЗ с прошлого раза.

Динамические массивы, malloc, free, sizeof, typedef

Сначала разберем две полезные функции: malloc, free. Эти функции нужны для работы с динамической памятью. Функция malloc принимает число байт, которое требуется выделить на динамической памяти, и возвращает указатель на начало выделенного куска памяти (тип этого указателя: void*). Функция free принимает указатель на кусок памяти и "удаляет" его (возвращает операционной системе).

Нельзя пользоваться удаленной памятью или удалять память несколько раз - от этого программа падает! Если программа взяла память при помощи malloc и так и не вернула её при помощи free, то говорят об утечках памяти.

Если вызвать free с нулевым указателем, то ничего не произойдёт.

malloc и free расположены в заголовочном файле <stdlib.h>.

Указатель типа void* неявно преобразуется в указатели на другие типы.

Ещё одна полезная операция: sizeof. Она принимает тип и возвращает его размер в байтах. Она нам нужна, чтобы знать, что подавать в malloc.

Пример. Размещаем число в динамической памяти. Создаем ещё один указатель (pointer_copy) на это число. Копируем значение числа в переменную value_copy. После этого изменяем число через первый указатель. Убеждаемся, что значение, на которое укзаывает pointer_copy, изменилось, а значение value_copy - не изменилось. Удаляем память, в которой живёт число, с помощью free. После этого нельзя пользоваться указателями на эту память, а вот копией числа (value_copy) - можно.

#include <stdlib.h>
#include <stdio.h>

int main() {
  int* pointer = malloc(sizeof(int));
  *pointer = 42;
  printf("%d\n", *pointer); // prints 42
  int* pointer_copy = pointer;
  int value_copy = *pointer;
  *pointer = 100;
  printf("%d\n", *pointer_copy); // prints 100
  printf("%d\n", value_copy); // prints 42
  free(pointer);
  // using pointer_copy here would break the program
  printf("%d\n", value_copy); // prints 42
}

Этот пример искусственный: в данном случае число было куда проще разместить на стеке. Однако этот пример раскрывает, как пользоваться malloc и free. Идём дальше.

Чтобы двигаться дальше, нам надо уяснить одну вещь: в C переменная, отвечающая за массив, представляет собой указатель на первый элемент массива. Именно так о ней и надо думать, чтобы понять следующую тему.

Динамический массив - это массив, размер которого определяется во время исполнения программы. (Сравнить: размер статического массива определяется во время компиляции программы.) Динамический массив размещается в динамической памяти.

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

Пример. Спрашиваем у пользователя число N и создаем массив из N чисел, заполняем их вводом от пользователя. Потом печатаем числа в виде текста.

#include <stdlib.h>
#include <stdio.h>

int main() {
  int N;
  scanf("%d", &N);
  int* array = malloc(sizeof(int) * N);
  int i;
  for (i = 0; i < N; i++) {
    scanf("%d", &(array[i]));
  }
  for (i = 0; i < N; i++) {
    printf("Element %d is equal to %d\n", i, array[i]);
  }
  free(array);
}

Пример работы программы:

3
6
7
8
Element 0 is equal to 6
Element 1 is equal to 7
Element 2 is equal to 8

typedef

typedef - это оператор языка C, который создает синонимичное название для типа.

Примеры:

typedef int* IntPointer;
typedef int IntArray[10];

Так мы объявили тип IntPointer как синоним int*, то есть указатель на число. Тип IntArray - массив из 10 чисел.

typedef удобно использовать при работе со сложными типами. (Ниже см. пример работы с указателями на функции - там без typedef вообще печаль.)

Используем typedef для создания динамического массива из статических массивов. По сути это двумерный массив, у которого "высота" может меняться, а "ширина" - фиксирован.

#include <stdlib.h>
#include <stdio.h>

int main() {
        int N;
        scanf("%d", &N);
        typedef int Array5[5];
        Array5* array = malloc(sizeof(Array5) * N);
        int i;
        for (i = 0; i < N; i++) {
                int j;
                for (j = 0; j < 5; j++) {
                        scanf("%d", &(array[i][j]));
                }
        }
}
free(array);

realloc

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

Пример.

#include <stdlib.h>
#include <stdio.h>

int main() {
        int N;
        printf("Array size: ");
        scanf("%d", &N);
        int* array = malloc(sizeof(int) * N);
        int i;
        for (i = 0; i < N; i++) {
                printf("Element %d: ", i);
                scanf("%d", &(array[i]));
        }
        int new_size = 2 * N;
        int* new_array = malloc(sizeof(int) * new_size);
        for (i = 0; i < N; i++) {
                new_array[i] = array[i];
        }
        free(array);
        for (i = N; i < new_size; i++) {
                new_array[i] = new_array[i - N];
        }
        for (i = 0; i < new_size; i++) {
                printf("Element %d is equal to %d\n", i, new_array[i]);
        }
        free(new_array);
}

Пример работы программы:

Array size: 3
Element 0: 5
Element 1: 6
Element 2: 7
Element 0 is equal to 5
Element 1 is equal to 6
Element 2 is equal to 7
Element 3 is equal to 5
Element 4 is equal to 6
Element 5 is equal to 7

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

Перепишем тот же код с использованием realloc.

#include <stdlib.h>
#include <stdio.h>

int main() {
        int N;
        printf("Array size: ");
        scanf("%d", &N);
        int* array = malloc(sizeof(int) * N);
        int i;
        for (i = 0; i < N; i++) {
                printf("Element %d: ", i);
                scanf("%d", &(array[i]));
        }
        int new_size = 2 * N;
        int* new_array = realloc(array, sizeof(int) * new_size);
        for (i = N; i < new_size; i++) {
                new_array[i] = new_array[i - N];
        }
        for (i = 0; i < new_size; i++) {
                printf("Element %d is equal to %d\n", i, new_array[i]);
        }
        free(new_array);
}

Этот код работает так же, как предыдущий. Обратите внимание, что теперь нет цикла, в котором мы копировали значения из старого массива в новый. free(array) теперь тоже не вызывается - если надо, это сделает сам realloc.

const

Модификатор типа const помечает тип как неизменяемый (константный). Переменные такого типа получают значение при создании и впоследствии его не меняют.

Пример:

const int x = 5;

В случае с указателями const может писаться:

до звезды - тогда через такой указатель нельзя изменять то, на что он указывает
после звезды - тогда нельзя изменять значение указателя (то есть, переставлять его на другой адрес)
и до и после - тогда получаем сочетаний вышеописанных свойств

Примеры:

const char* x = "aaa"; // запрещает писать x[0] = 'b';
char* const y = "aaa"; // запрещает писать y = x;

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

Иллюстрация запрета:

const int* x = ...;
int* y = ...;
x = y; // ok
y = x; // error

C-строки

Строка - это массив символов. Символ - это однобайтное число, тип char.

В первом приближении символ = байт.

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

Стоит помнить, что это не единственный способ представляния строки. В других языках, например в C++ очень популярны т.н. P-строки (P-в честь языка Pascal), в которых хранится длина строки как число, а потом само содержимое строки, после которого может не быть нулевого байта.

Когда мы пишем строку в двойных кавычках, то C создает в статической неизменяемой памяти массив символов, которые мы написали в двойных кавычках, после которых нулевой байт. А значением такого выражения является указатель на первый байт строки. Такая память является неизменяемой. Чтобы изменять строку, надо иметь её изменяемоую копию, например, в динамической памяти.

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

Пример:

const char long_string = "Hello, "
                         "world";
printf(long_string);
// prints "Hello, world"

Пример. Создаем строку, которую и печатаем.

#include <stdio.h>

int main() {
        const char* str = "Hello";
        printf(str);
        printf("\n");
        printf("%s\n", str);
}

Разберем этот код построчно.

Переменная str хранит указатель на начало строки, то есть на 'H'. После этой буквы идут и другие буквы строки, а именно 'e', 'l', 'l', 'o'. А потом идёт нулевой байт: '\0'. Длина строки 5, а памяти она занимает 6 байт благодаря завершающему нулевому байту.

Потом мы печатаем строку двумя способами. Сначала просто подаем её в printf в качестве форматной строки, после чего отдельно печатаем переход на новую строку, так как в исходную строку он не входит. Потом печатаем её более правильным способом - через подстановку %s форматной строки. Второй способ предпочтительнее, так как сама строка может содержать части, похожие на подстановочные последовательности (например, %d), что, без сомнения, смутит printf. Он будет пытаться взять несуществующий аргумент, из-за чего программа, скорее всего, упадёт.

Так как строки - указатели и массивы одновременно, то мы можем работать с нами в обоих качествах. К примеру, запись str[index] дает нам доступ к символам строки.

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

char buffer[100];
strcpy(buffer, "Hello");
printf("The value of buffer is %s.", buffer);
// prints "The value of buffer is Hello."

(см. ниже про функцию strcpy, она копирует строку.)

Нулевой символ в конце маркирует конец строки. А начало строки нигде не обозначено. Это значит, что никто не мешает нам переместить указатель вглубь строки, "откусив" её начало.

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

#include <stdio.h>

int main() {
        const char* str = "ABCDEFGHIJKLMNOPQRSTUVWQRSTUVWXYZ";
        int start;
        scanf("%d", &start);
        char* suffix = str + start;
        printf("%s\n", suffix);
}

Обратите внимание, как мы сложили указатель с числом. Эта запись синонамична следующей записи: &(str[start]). То есть, представив строку как массив, выбрать в нем элемент с индексом start и взять на него указатель (вернувшись к типу "строка"). Для указателей на другие типы это тоже работает. Если размер элемента массива больше 1, то прибавление к указателю числа приводит к перемещению на целое число элементов массива, а не на байты!

Пример работы с программой:

10
KLMNOPQRSTUVWQRSTUVWXYZ

Модуль <string.h>

В <string.h> есть много полезных функций для работы со строками.

strlen: принимает строку, возвращает её длину
memset: принимает указатель, значение value и число байт num и "забивает" num байт, начиная с байта, на который указывает указатель, значением value
strcmp: принимает две C-строки и сравнивает их. Если строки равны, то возвращает 0, если первая строка лексиграфически меньше второй, то результат меньше 0, если вторая меньше первой, то результат больше 0. Если одна из строк является префиксом другой, то этот префик считается меньше, так как в одном из символов у него будет стоять нулевой байт (конец строки), а в другой строке будет не ноль, а содержательный символ, который имеет номер больше 0.
memcmp: принимает два указателя типа void* и размер num. Сравнивает куски памяти размера num. Возвращаемые значения аналогично strcmp
strcpy: принимает два указателя: destination и source. Воспринимает source как С-строку и копирует её, включая нулевой байт, в destination. Возвращает destination.
memcpy: принимает два указателя destination и source и размер num. Копирует num байт из source в destination.
strcat: принимает две С-строки: destination и source. Дописывает source в конец destination. Конец destination определяется по нулевому байту, начиная с которого начинается копирование из source. Нулевой байт из source тоже копируется в самый конец, после чего копирование прерывается. Эта функция удобна для объединения двух строк, так же известной как конкатенация.

sprintf, sscanf

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

Функция sprintf устроена так же, как printf, но имеет в начале списка аргументов ещё один аргумент - указатель char*, в который она печатает свой результат вместо вывода его на экран.

char buffer[100];
sprintf(buffer, "Hello, %s!", "Vasya");

Функция sscanf устроена так же, как scanf, но имеет в начале списка аргументов ещё один аргумент - указатель const char*, из которого она берет входной материал вместо ввода его с клавиатуры.

int x;
sprintf("x = 42", "x = %d", &x);

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

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

Записывается это так:

int addInt(int n, int m) {
    return n+m;
}

int main() {
    int (*functionPtr)(int,int);
    functionPtr = &addInt;
    int sum = (*functionPtr)(2, 3); // sum == 5
}

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

Выполните все предыдущие задания, которые вы не выполнили.
Выучите теорию за это и предыдущие занятия. Нового теста на дом не задаю.
Уделите время учебному проекту.
Решите следующие задачи.

Обязательные задачи

Определите нашу любимую структуру Point с полями x и y типа int. Создайте экземпляры этой структуры на стеке, в статической памяти и в динамической памяти. Последнюю не забудьте удалить с помощью free.
Сортировка. Напишите программу, которая спрашивает у пользователя число N, после чего спрашивает N чисел. Эти числа программа заносит в динамический массив, в котором она их сортирует любым известным способом сортировки и выводит на экран.
Напишите функцию repeatString, которая будет объявлена следующим образом: char* repeatString(const char* text, int n, const char* separator). Эта функция выделяет память с помощью malloc, в которую кладёт строку, образованную повторением n раз строки text, с использованием separator в качестве соединительной строки. После этого возвращает эту строку. Итоговая длина строки будет strlen(text) * n + strlen(separator) * (n - 1). В malloc подаётся значение, на 1 большее чем длина строки. (Почему?) Вызовите функцию repeatString из функции main и распечатайте результат. Не забудьте после этого удалить то, что вернула функция repeatString, с помощью функции free, чтобы избежать утечек памяти.
Перепишите задачу Спираль из предыдущего занятия так, чтобы размер стороны квадрата задавался пользователем во время работы программы. Подсказка: многомерный массив можно всегда "свернуть" в одномерный. А одномерные массивы любого размера можно создать с помощью malloc.

Дополнительное задание (задание с одной вакансии)

An input file contains integers, both positive and negative (there might be some duplicates). Each line on the file has one integer.

Compute the number of distinct y values within the range -10000 ≤ y ≤ 10000 such that there are distinct numbers a, b in the file where a + b = y.

You can download the file (57MB). There are two test cases there for you to verify your program. Check the README file for the answers.

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

Kodomo

Пользователь