sem05 (Мини-учебник с ejudge = Чернокнижка)

1Занятие №51.1 УказателиРассмотрим важнейший производный тип — указательный. Если base — это некоторый базовый тип, то тип указателя на тип base имеет своим множеством значений всевозможные адреса памяти, по которым на данной машине могут храниться значения типа base,плюс специальное значение 0, которое не соответсвует никакому допустимому адресу объекта.Другими словами в переменных указательного типа хранятся адреса объектов, то естьпеременных или функций.

Аналогом указательных типов в языке Паскаль являются ссылочные типы.Простейшее определение переменной указательного типа имеет вид:<тип> *<переменная>;Знак ’*’ («звёздочка») относится к имени переменной, а не к типу, поэтому определениеint *p, c;определяет переменную p указательного на int типа и переменную c целого типа. Функция,возвращающая указатель, определяется похожим образомchar *strdup(char *ptr);Аналогично массив указателейint *aptr[20];Указательный тип может иметь в качестве своего базового типа любой тип, в частности указательный, структурный, массивовый и т.

д. Синтаксис таких сложных описаний (деклараторов) будет рассмотрен нами позднее.Переменные указательного типа могут хранить адрес любого объекта в программе, приусловии, что типы объекта и указателя согласованы. На самом деле, поскольку адрес объекта, как правило, имеет размер, не зависящий от размера объекта, возможно практическинеограниченное явное приведение значений одних указательных типов к другим. Язык Си,хотя и не поощеряет такие приведения типов, не запрещает их.Для взятия адреса существующего объекта используется операция &. Например, выражениеp = &c;присваивает переменной указательного типа p адрес переменной c.

Точно так же могутбраться адреса элементов массива, полей структур, локальных и глобальных переменныхи пр.Для разыменования указательного значения (взятия значения по адресу) применяетсяунарная операция *. Например, printf("%d\n", *p);.Даже если указатель p содержит 0 или недопустимое значение, выражение &(*p) всегдатождественно равно p. То же верно и для всякого выражения указательного типа. Обратноевыражение *&E, очевидно, не всегда равно E.Указатели одного типа можно сравнивать друг с другом на равенство и неравенство. Любой указательный тип может сравниваться на равенство или неравенство с целой константой0 (точнее, с константным выраженим, равным 0 какого-либо целого типа).

Любому указателю может присваиваться целая константа 0, что означает, что данный указатель не указывает1ни на какую область памяти. Стандартная библиотека определяет константу NULL, которуюможно использовать для символической (возможно более наглядной) записи нулевого указателя. Попытки записи или чтения по нулевому указателю обычно вызывают исключениеоперационной системы. Если же указатель не инициализирован, то он указывает на некоторую случайную область памяти. Выражение указательного типа может использоваться вусловиях циклов, оператора if и т. д. Это обозначает неявное сравнение значения выражения с нулевым указателем 0. Например циклfor (p = head; p; p = p->next)будет работать до тех пор, пока p не обратиться в нуль.В языке Си существует специальный тип обобщённого указателя, который записываетсякакvoid *ptr;то есть как указатель на «тип» void.

Такому указателю можно присваивать значения указателей любого типа, и такой указатель можно присваивать указателю любого типа (тольков Си, но не в Си++). Указатель обобщённого типа нельзя разыменовывать и с нимнельзя проводить арифметические операции (но с нулём сравнивать можно).1.1.1 Массивы и указателиВ языке Си массивы и указатели тесно связаны друг с другом.Во-первых, выражение, состоящее из имени массива, имеет тип константного указателяна первый элемент массива. То есть имя массива можно рассматривать как константныйуказатель на его первый элемент.И наоборот, любое указательное значение можно рассматривать как адрес первого элемента некоторого массива, и соответственно, любое указательное значение можно индексировать.Например, если есть определение переменнойint arr[32], *p;то выражения &arr[0] и arr полностью эквивалентны друг другу.

Например, после выполнения инструкцииp = arr;указатель p будет содержать адрес нулевого элемента массива, и имя указателя p можетвезде использоваться для обращения к массиву arr. Например,p[0] = 2;c = p[3] + p[4];Существует два отличия между переменной, объявленной как массив и переменной, объявленной как указатель: во-первых, имени массива нельзя присвоить никакого значения, тоесть выражение видаarr = &p[3];/* неправильно! */во-вторых, при определении переменной типа массива под эту переменную отводится память, достаточная для хранения заявленного в определении переменной числа элементовмассива, а при определении указателя отводится память, достаточная для хранения указателя. Так, для массива arr будет отведено 128 байт (в предположении, что int занимает 4байта), а для указателя p — только 4 байта (если указатель занимает 4 байта памяти).21.1.2 Арифметика указателейНа связи указателей и массивов построена арифметика указательных значений.

Пустьпеременная p указательного типа указывает на i-й элемент некоторого массива arr, то естьp = &arr[i], а переменная q — на j-й элемент того же массива arr.Значение указательного типа можно складывать со значением целого типа, и из значенияуказательного типа можно вычитать значение целого типа. Тип результата этих операцийсовпадает с указательным типом, а результат — это указательное значение, указывающее наэлемент массива, отстоящий от исходного элемента массива на указанное число элементов.Например, если int arr[10], *p = &arr[5];, тогдаp + 3 == &arr[8];p - 4 == &arr[1];Таким образом устанавливается тождественная связь между операцией индексированияи сложением указателя и целого значения:arr[ind] == *(arr + ind)&arr[ind] == arr + indТакие тождества рассматриваются в Си как определение операции индексирования.Соответственно, для указателей определены операции -, +=, -=, ++, --.Два указателя можно вычитать друг из друга.

Эти два указателя должны указывать наэлементы одного и того же массива (должны, естественно, иметь один и тот же тип). Результатом вычитания является целое число — разность между указателями, выраженная в числеэлементов массива данного типа. Пусть p и q определены как указано выше.p - q == i - jЕсли p и q не указывают на элементы одного и того же массива, результат операции p - qне определён.Если p — указатель, то(p + 1) - p == 1для любого типа на который указывает переменная p.В качестве примера рассмотрим возможную реализацию функции strcpy.char *strcpy(char *str1, char *str2){char *d = str1;while ((*d++ = *str2++));return str1;}1.2 Работа с динамической памятьюВ языке Си помимо области памяти, выделяемой во время компиляции программы дляглобальных переменных, и области памяти в стеке, выделяемой для локальных переменныхдинамически при каждом вызове функции, существует область памяти (традиционно называемая «кучей»), представляющая собой нечто среднее между этими двумя типами памяти.Куча существует все время выполнения программы, но память в ней выделяется и освобождается динамически, по требованию программиста.

По сути, памятью, выделяемой в куче,3нужно пользоваться, когда размер входных данных программы заранее неизвестен, то естьпрактически всегда.Средства работы с динамической памятью не встроены в язык, а предоставляются стандартной библиотекой. Чтобы использовать функции работы с динамической памятью, необходимо подключить заголовочный файл#include <stdlib.h>Определены следующие стандартные функцииvoid *malloc(size_t size);выделяет в куче область памяти размера size и возвращает указатель на начало этой области памяти.

Здесь size_t — это тип, определённый стандартом для представления величин,задающих размер объектов. Операция sizeof вырабатывает значение именно этого типа.Обычно тип size_t определяется эквивалентным типу unsigned long int. Если sizeравно нулю, результат работы функции неопределён.void *calloc(size_t nitems, size_t nsize);выделяет в куче область памяти для размещения массива из nitems элементов, каждый изкоторых имеет размер nsize, и возвращает указатель на выделенную область памяти. Выделенная область памяти инициализируется нулями. Если функции calloc или malloc немогут выделить область памяти достаточного размера, они возвращают нулевой указатель (0или NULL). Программист должен проверять результат, возвращаемый этими функциями и предпринимать действия по обработке ошибок, если был возвращён нулевойуказатель.void free(void *ptr);освобождает ранее выделенный в куче блок памяти и делает его доступным для повторного использования.

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