5.2. Указатели и ссылки

Объект, указатель и ссылка

Указатели совместно с адресной арифметикой играют в Си особую роль. Можно сказать, что они определяют лицо языка. Благодаря им Си может считаться одновременно языком высокого и низкого уровня по отношению к памяти.

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

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

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

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

• терминология ссылка, значение касается фундаментальных свойств переменных в языках программирования. Имя переменной в различных контекстах может восприниматься как ее значение (содержимое памяти), так и ссылка на нее (адрес памяти, указатель)(см. 1.3). Например, при присваивании левая часть рассматривается как ссылка, а правая – как значение (см. 1.4);

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

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

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

Указатель в Си

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

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

• передавать информацию о том, где в памяти расположены данные. Такая информация, естественно, является более компактной, чем сами данные, и ее условно можно назвать указателем. Получаем «дилетантское» определение указателя: указатель - переменная, содержащая информацию о расположении в памяти другой переменной.

Наряду с указателем в программировании также используется термин ссылка. Ссылка – содержанием ссылки также является адресная информация об объекте (переменной), но внешне она выглядит как переменная (синоним оригинала).

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

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

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

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

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

• указатель, который содержит адрес переменной, ссылается на эту переменную или назначен на нее;

• переменная, адрес которой содержится в указателе, называется указуемой переменной.

Последовательность действий при работе с указателем включает 3 шага:

1. Определение указуемых переменных и переменной-указателя. Для переменной-указателя это делается особым образом.

int a,x; // Обычные целые переменнные
int *p;  // Переменная - указатель на другую  целую переменную

В определении указателя присутствует та же самая операция косвенного обращения по указателю. В соответствии с принципами контекстного определения типа переменной (см. 5.5) эту фразу следует понимать так: переменная p при косвенном обращении к ней дает переменную типа int. То есть свойство ее – быть указателем, определяется в контексте возможного применения к ней операции *. Обратите внимание, что в определении присутствует указуемый тип данных. Это значит, что указатель может ссылаться не на любые переменные, а только на переменные заданного типа, то есть указатель в Си типизирован.

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

p = &a; // Указатель содержит адрес переменной a

Операция & понимается буквально как адрес переменной, стоящей справа от нее. В более широкой интерпретации она «превращает» объект в указатель на него (или производит переход от объекта к указателю на него) и является в этом смысле прямой противоположностью операции *, которая «превращает» указатель в указуемый объект. То же самое касается типов данных. Если переменная a имеет тип int, то выражение &a имеет тип – указатель на int или int*.

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

*p=100;     // Эквивалентно a=100
x = x + *p; // Эквивалентно x=x+a
(*p)++;     // Эквивалентно a++

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

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

Адресная арифметика и управление памятью

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

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

Такие свойства указателя обеспечиваются адресной арифметикой, которая базируется на нестандартной интерпретации операции указатель+целое и других, производных от нее операциях:

• любой указатель потенциально ссылается на неограниченную в обе стороны область памяти, заполненную переменными указуемого типа;

• переменные в области нумеруются от текущей указуемой переменной, которая получает относительный номер 0. Переменные в направлении возрастания адресов памяти нумеруются положительными значениями 1,2,3..., убывания - отрицательными - -1,-2..;

• результатом операции указатель+i является адрес i-ой переменной (значение указателя на i-ую переменную) в этой области относительно текущего положения указателя.

В операциях адресной арифметики транслятором автоматически учитывается размер указуемых переменных, то есть +i понимается не как смещение на i байтов или слов, а как смещение на i указуемых переменных. Другая важная особенность: при перемещении указателя нумерация переменных в памяти остается относительной и всегда производится от текущей указуемой переменной.

Указатели и массивы. Нетрудно заметить, что указатель в Си имеет много общего с массивом. Наоборот, труднее сформулировать, чем они отличаются друг от друга. Действительно, разница лежит не в принципе работы с указуемыми переменными, а в способе назначения указателя и массива на ту память, с которой они работают. Образно говоря, указателю соответствует массив, «не привязанный» к конкретной памяти, а массиву соответствует указатель, постоянно назначенный на выделенную транслятором область памяти. Это положение вещей поддерживается еще одним правилом: имя массива во всех выражениях воспринимается как указатель на его начало, то есть имя массива A эквивалентно выражению &A[0] и имеет тип «указатель на тип данных элементов массива». Таким образом, различие между указателем и массивом аналогично различию между переменной и константой: указатель - это ссылочная переменная, а имя массива - ссылочная константа, привязанная к конкретному адресу памяти.

Если МАССИВ=ПАМЯТЬ+УКАЗАТЕЛЬ (начальный адрес), то УКАЗАТЕЛЬ=МАССИВ-ПАМЯТЬ, т.е. указатель это «массив без памяти», «свободно перемещающийся по памяти» массив.

Указатели и многомерные массивы. Двумерный массив реализован как «массив массивов» - одномерный массив с количеством элементов, соответствующих первому индексу, причем каждый элемент представляет собой массив элементов базового типа с количеством, соответствующим второму индексу. Например, char A[20][80] определяет массив из 20 массивов по 80 символов в каждом и никак иначе.

Идентификатор массива без скобок интерпретируется как адрес нулевого элемента нулевой строки, или указатель на базовый тип данных. В нашем примере идентификатору A будет соответствовать выражение &A[0][0] с типом char*.

Имя двумерного массива с единственным индексом интерпретируется как начальный адрес соответствующего внутреннего одномерного массива. A[i] понимается как &A[i][0], то есть начальный адрес i-го массива символов.

От такого многообразия возможностей работы с указателями нетрудно прийти в замешательство: как вообще с ними работать, кто за что отвечает? Действительно, при работе с указателями легко выйти «за рамки дозволенного», т.е. определенных самим же программистом структур данных. Поэтому попробуем еще раз обсудить принципиальные моменты адресной арифметики.

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

На что ссылается указатель? Cинтаксис языка в операциях с указателями не позволяет различить в конкретной точке программы, что подразумевается под этим указателем - указатель на отдельную переменную, массив (начало, середину конец...), какова размерность массива и т.д.. Все эти вопросы целиком находятся в ведении работающей программы. Все же даже поверхностный взгляд на программу позволяет сказать, с чем же работает указатель – с отдельной переменной или массивом.

• наличие операции инкремента или индексации говорит о работе указателя с памятью (массивом);

• использование исключительно операции косвенного обращения по указателю свидетельствует о работе с отдельной переменной.

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

• неинициализированный указатель. После определения указатель ссылается «в никуда», тем не менее программист работает через него с переменной или массивом, записывая данные по случайным адресам;

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

• выход указателя за границы памяти. Например, конец строки отмечается символов ‘\0’, начало же формально соответствует начальному положению указателя. Если в процессе работы со строкой требуется возвращение на ее начало, то начальный указатель необходимо запоминать, либо дополнительно отсчитывать символы.

Другие операции над указателями

В процессе определения указателей мы рассмотрели основные операции над ними:

• операция присваивания указателей одного типа. Назначение указателю адреса переменной p=&a есть одни из вариантов такой операции;

• операция косвенного обращения по указателю (разыменования указателя);

• операция адресной арифметики «указатель+целое» и все производные от нее.

Кроме того, имеется еще ряд операций, понимание которых не выходит за рамки уже имеющейся интерпретации указателя.

Сравнение указателей на равенство. Равенство указателей однозначно понимается как совпадение адресов, то есть назначение их на одну и ту же область памяти (переменную).

Пустой указатель (NULL-указатель). Среди множества адресов выделяется такой, который не может быть использован в правильно работающей программе для размещения данных. Это значение адреса называется NULL-указателем или «пустым» указателем. Считается, что указатель с таким значением не является корректным (указывает «в никуда»). Обычно такое значение определяется в стандартной библиотеке ввода-вывода в виде #define NULL 0.

Значение NULL может быть присвоено любому указателю. Если указатель по логике работы программы может иметь такое значение, то перед косвенным обращением по нему его нужно проверять на достоверность:

int *p,a;
if (…) p=NULL; else p=&a; ...
if (p !=NULL) *p = 5;    ...

Сравнение указателей на «больше-меньше»: при сравнении указателей производится сравнение соответствующих адресов как беззнаковых переменных. Если оба указателя ссылаются на элементы одного и того же массива, тогда соотношение «больше-меньше» следует понимать как «ближе-дальше» к началу массива:

//--- Симметричная перестановка символов строки
void F(char *p) {
  for (char *q=p; *q!=0; q++);     // Указатель q до конца строки
  for (q--; q>p; p++, q--)         // Пока p левее q
    { char c; c=*p; *p=*q; *q=c; } // 3 стакана над переменными под указателями
}

Разность значений указателей. В случае, когда указатели ссылаются на один и тот же массив, их разность понимается как «расстояние между ними», выраженную в количестве указуемых переменных.

Преобразование типа указателя. Отдельная операция преобразования, связанная с изменением типа указуемых элементов при сохранении значения указателя (адреса), используется при работе с память на низком (архитектурном) уровне (см. 9.2). Отдельный разговор о преобразовании типов указателей при наследовании (см. 11.3, 11.4). Сюда же относится преобразование вида «целое-указатель».

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

extern int fread(void *, int, int, FILE *);
int A[20];
fread(A, sizeof(int), 20, fd);

Функция fread выполняет чтение из двоичного файла n записей длиной по m байтов, при этом структура записи для функции неизвестна. Поэтому начальный адрес области памяти передается формальным параметром типа void*. При подстановке фактического параметра A типа int* производится неявное преобразование его к типу void*.

extern void *malloc(int);
int *p = (int*)malloc(sizeof(int)*20); // Явное преобразование void* к int*

Функция malloc возвращает адрес зарезервированной области динамической памяти в виде указателя void*. Это означает, что функцией выделяется память как таковая, безотносительно к размещаемым в ней переменным. Вызывающая функция явно преобразует тип указателя void* в требуемый тип int* для работы с этой областью как с массивом целых переменных.

Вывод: преобразование указателя void* к любому другому типу указателя соответствует «смене точки зрения» программы на адресуемую память от «данные вообще» к «конкретные данные» и наоборот (см. 9.2) и должно быть сделано явно. Преобразование указателя к типу void* не требует явного подтверждения.

Указатель как формальный параметр и результат функции

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

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

void inc(int *p) { 
  (*pi)++; // аналог вызова:  pi = &a
}  

void main() { 
  int a;                                
  inc(&a);      // *(pi)++ эквивалентно a++ 
} 

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

int sum(int A[],int n) {  // Исходная программа            
  int s,i;                                           
  for (i=s=0; i<n; i++) s+= A[i];                             
  return s;
}                                    
int sum(int *p, int n) {  // Эквивалент с указателем
  int s,i;
  for (i=s=0; i<n; i++) s+= p[i];
  return s; 
}

int x, B[10] = {1,4,3,6,3,7,2,5,23,6};

void main() { 
  x = sum(B,10);  // аналог вызова: p = B, n = 10 
}

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

Указатель - результат функции. Функция в качестве результата может возвращать указатель. Формальная схема функции обязательно включает в себя:

• определение типа результата в заголовке функции как указателя. Это обеспечивается добавлением пресловутой перед именем функции - **int F(...**;

• оператор return возвращает объект (переменную или выражение), являющееся по своей природе (типу данных) указателем. Для этого можно использовать локальную переменную - указатель.

Содержательная сторона проблемы состоит в том, что функция либо выбирает один из известных ей объектов (переменных), либо создает их в процессе своего выполнения (динамические переменные), возвращая в том и другом случае указатель на нее. Для выбора у нее не так уж много возможностей. Это могут быть:

• глобальные переменные программы;

• формальные параметры, если они являются массивами, указателями или ссылками, то есть «за ними стоят» другие переменные.

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

char *F1() { char cc=’A’; return &cc; }

Пример: функция возвращает указатель на минимальный элемент массива. Массив передается как формальный параметр.

//------------------------------------------------------52-01.cpp
//----- Результат функции - указатель на минимальный элемент
int *min(int A[], int n) {
  int *pmin, i;  // Рабочий указатель, содержащий результат
  for (i=1, pmin=A; i<n; i++)
    if (A[i] < *pmin) pmin = &A[i];
  return(pmin);  // В операторе return - значение указателя 
}

void main() {
  int B[5]={3,6,1,7,2};
  printf("min=%d\n",*min(B,5)); 
}

Прежде всего, обратим внимание на синтаксис. Заголовок функции написан таким образом, как будто имя функции является указателем на int. Этим способом и обозначается, что ее результат - указатель. Оператор return возвращает значение переменной-указателя pmin, то есть адрес. Вообще в нем может стоять любое выражение, значение которого является указателем, например:

return &A[k];
return pmin+i;
return A+k; 

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

Ссылка как неявный указатель

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

Ссылка – неявный указатель, имеющий синтаксис указуемого объекта (синоним). В Си имеется возможность определения такого синонима с использованием символа &:

int a=5;  // Переменная – прототип
int &b=a; // Переменная b – ссылка на переменную a
b++;      // Операция над b есть операция над прототипом a

Наиболее употребительным в Си, а в других языках – единственно возможным является использование ссылки как формального параметра функции. Это означает, что при вызове функции формальный параметр создается как переменная-ссылка, который отображается на соответствующий фактический параметр. Формальный параметр –ссылка аналогично отмечается в списке параметров значком & перед именем. В остальном синтаксис работы с параметром-ссылкой и параметром-значением идентичны. Различие заключается в способе взаимодействия с фактически параметром:

• при передаче по значению формальный параметр является копией фактического, он может быть изменен независимо от значения оригинала – фактического параметра. Такой параметр является исключительно входным;

• при передаче по ссылке формальный параметр отображается на фактический, и его изменение сопровождается изменением фактического параметра-прототипа. Такой параметр может быть как входным, так и выходным.

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

//-----------------------------------------------------------------
// Формальный параметр - значение
void inc(int vv) { vv++; } // Передается значение - копия nn

void main() { int nn=5; inc(nn); } // nn=5

//-----------------------------------------------------------------
// Формальный параметр - указатель
void inc(int *pv) { (*pv)++; } // Передается указатель - адрес nn

void main() { int nn=5; inc(&nn); }  // nn=6

//-----------------------------------------------------------------
// Формальный параметр - ссылка
void inc (int &vv) { vv++; }  // Передается указатель - синоним nn

void main() { int nn=5; inc(nn); } // nn=6

В Си возможна также и передача ссылки в качестве результата функции. Ее следует понимать как отображение (синоним) на переменную, которая возвращается оператором return. Требования к объекту – источнику ссылки, на который она отображается, еще более строгие – это либо глобальная переменная, либо формальный параметр функции, передаваемый в нее по ссылке или по указателю. При обращении к результату функции – ссылке производится действие с переменной-прототипом. Более подробно все нюансы и примеры будут рассмотрены в 10.2.

//------------------------------------------------------52-02.cpp
//----- Функция возвращает ссылку на минимальный элемент массива
int &ref_min(int A[], int n) {
  for (int i=0,k=0; i<n; i++)
    if (A[i]<A[k]) k=i;
  return A[k];
}

void main() {
  int B[5] = {4,8,2,6,4};
  ref_min(B,5)++;
  for (int i=0; i<5; i++) printf("%d ",B[i]); 
}

Здесь «ссылка на ссылке ссылкой погоняет». Формальный параметр A – массив, который передается по ссылке и при вызове отображается на B. Функция, возвращает ссылку на минимальный элемент A[k], тем самым отображает свой результат на минимальный элемент массива. Кому надоело «играть в прятки» с транслятором, может посмотреть программный эквивалент с использованием обычных указателей.

//------------------------------------------------------52-03.cpp
//----- Функция возвращает указатель на минимальный элемент массива
int *ptr_min(int *p, int n) {
  int *pmin;
  for (pmin=p; n>0; p++,n--)
    if (*p < *pmin) pmin=p;
  return pmin;
}

void main() {
  int B[5]={4,8,2,6,4};
  (*ptr_min(B,5))++;
  for (int i=0; i<5; i++) printf("%d ",B[i]); 
}

Строки, массивы символов и указатель char*

Среди возможных интерпретаций указателя char* (указатель на отдельный символ, на байт, массив байтов, массив целых (размерности байт)), можно выделить указатель на строку: массив, содержащий последовательность символов, ограниченную символом ‘\0’. Цикл работы со строкой с использованием указателя обычно включает линейное перемещение указателя с проверкой на символ конца строки под указателем.

int strlen(char *p) { // Возвращает длину строки, заданной
  int n; // указателем на на строку char*
  for (n=0; *p != '\0'; p++, n++);
  return n;
}

void strcat(char *p, char *q) { // Объединяет строки,
  while (*p !='\0') p++; // заданные указателями
  while(*q !='\0') *p++ = *q++);
  *p = '\0';
}

При просмотре массива операции индексирования с линейно изменяющимся индексом (p[i] и i++) заменены аналогичным линейным перемещением указателя - *p++, или *p, p++.

Строковая константа в любом контексте интерпретируется как указатель на создаваемый транслятором массив символов, инициализированный этой строкой. Трансляция строковой константы включает в себя:

• создание массива символов с размерностью, достаточной для размещения строки;

• инициализацию (заполнение) массива символами строки, дополненной символом '\0';

• включение в контекст программы, где присутствует строковая константа, указателя на созданный массив символов. В программе ей соответствует тип char* - указатель на строку.

char *q = "ABCD"; // Программа                           
char *q; // Эквивалент
char A[5] = {'A','B','C','D','\0'};
q = A;  

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

char c1 = "ABCD"[3];
char c2 = ("12345" + 2)[1];
for (char *q = "12345"; *q !='\0'; q++);
char c3=*(--q);

Указатель на строку, массив символов, строковая константа. Имя массива символов, строковая константа и указатель на строку имеют в языке один и тот же тип char*, поэтому могут использоваться в одном и том же контексте, например, в качестве фактических параметров функций:

extern int strcmp(char *, char*);
char *p,A[20];
strcmp(A,"1234");
strcmp(p,A+2);

Результат функции - указатель на строку. Функция, возвращающая указатель, может «отметить» им место в строке с интересующими вызывающую программу свойствами. При отсутствии найденного элемента возвращается NULL.

Индексация или перемещение указателя. При работе с массивом через указатель всегда существует альтернатива: использовать индексацию при «неподвижном» указателе, либо перемещать указатель с помощью операций p++ или присваивания указателя. Рекомендации – соображения удобства. Единственный случай, если перемещение по массиву складывается из двух составляющих, то избежать суммирования индексов, а также периодических присваиваний указателей можно сочетанием перемещения указателя и индексации.

Посмотрим, как все вышесказанное выглядит на практике.

Поиск всех вхождений подстроки в строке. Для начала разработаем функцию поиска подстроки в строке. Функция получает указатель на начало строки, продвигает его к началу обнаруженного фрагмента и возвращает в качестве результата. Внешний цикл, таким образом, предполагает простое перемещение указателя p по строке. В его теле для каждого текущего положения указателя p производится проверка на обнаружение подстроки. Для этого используется индексация относительно текущего положения указателя p[i], тем более, что аналогичная индексация используется и во второй строке для попарного сравнения символов.

//------------------------------------------------------52-04.cpp
//---- Поиск в строке заданного фрагмента
char *find (char *p,char *q) { // Попарное сравнение
  for (; *p!='\0'; p++) { // до обнаружения расхождения
    for ( int i=0 ; q[i]!='\0' && q[i]==p[i]; i++);
    if ( q[i] == '\0') return p; // Конец подстроки - успех
  } // иначе продолжить поиск
  return NULL;
}

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

//------------------------------------------------------52-05.cpp
//----- Поиск всех вхождений фрагмента в строке
void main() { 
  char c[80]="find first abc and next abc and last abc",*q="abc", *s;
  for (s=find(c,q); s!=NULL; s=find(s+strlen(q),q)) puts(s);
}

Получается итерационный цикл, в котором найденное значение на текущем шаге становится началом поиска на следующем. В первый раз функция вызывается с указателем на начало строки, а при повторении цикла - с указателем на первый символ за фрагментом, найденном на текущем шаге - s+strlen(q).

Сортировка слов в строке (выбором). Рассмотрим еще одни пример, использующий ту же технику перемещения указателей по строке.

//------------------------------------------------------52-06.cpp
//---- Поиск слова максимальной длины посимвольная обработка
// Функция возвращает указатель начала слова или NULL, если нет слов
char *find(char *s) {
  int n,lmax; char *pmax;
  for (n=0,lmax=0,pmax=NULL; *s!=0;s++){
    if ( *s!=' ') n++; // символ слова увеличить счетчик
    else { // перед сбросом счетчика
      if (n > lmax) { lmax=n; pmax=s-n; }
      n=0;                           // фиксация максимального значения
    }
  }                              
  if (n > lmax) pmax=s-n; // то же самое для последнего слова
  return pmax; 
}

Для получения указателя на начало очередного слова используется указатель текущего символа s. В момент запоминания он ссылается на первый символ после слова, поэтому по правилам адресной арифметики он смещается назад на число символов n, равное длине слова.

//------------------------------------------------------52-07.cpp
//---- Сортировка слов в строке в порядке убывания (выбором)
void sort(char *in, char *out) { 
  char * q;
  while((q=find(in))!= NULL) { // Получить индекс очередного слова
    for (; *q!=' ' && *q!=0; ) {
      *out ++= *q; *q ++=' ';  // Переписать с затиранием
    }
    *out++=' ';  // После слова добавить пробел
  }
  *out=0;
}

Лабораторный практикум

Вариант задания реализовать в виде функции, использующей для работы со строкой только указатели и операции над ним вида *p++, p++, p[i] и т.д. Если функция возвращает строку или ее фрагмент, то это также необходимо сделать через указатель.

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

2. Шейкер-сортировка с использованием указателей на правую и левую границы отсортированного массива и сравнения указателей.

3. Функция находит в строке пары одинаковых фрагментов и возвращает указатель на первый. С помощью функции найти все пары одинаковых фрагментов.

4. Функция находит в строке пары инвертированных фрагментов (например "123apr" и "rpa321") и возвращает указатель на первый. С помощью функции найти все пары.

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

6. Функция находит в строке десятичные константы и заменяет их на шестнадцатеричные с тем же значением, например "aaaaa258xxx" на "aaaaa0x102xxx".

7. Функция находит в строке символьные константы и заменяет их на десятичные коды, например "aaa'6'xxx" на "aaa54xxx".

8. Функция находит в строке самое длинное слово и возвращает указатель на него. С ее помощью реализовать размещение слов в выходной строке в порядке убывания их длины.

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

10. Функция находит в строке симметричный фрагмент вида "abcdcba" длиной 7 и более символов (не содержащий пробелов) и возвращает указатель на его начало и длину. С использованием функции «вычеркнуть» все симметричные фрагменты из строки.

11. «Быстрая» сортировка (разделением) с использованием указателей на правую и левую границы массива, текущих указателей на правый и левый элемент и операции сравнения указателей (см. 7.2).

12. Найти в строке последовательности, состоящие из одного повторяющегося символа и заменить его на число символов и один символ (например "aaaaaa" - "5a").

13. Функция создает копию строки и "переворачивает" в строке все слова. (Например: "Жили были дед и баба" - "илиЖ илиб дед и абаб").

Вопросы без ответов

Определите, используется ли указатель для доступа к отдельной переменной или к массиву. Напишите вызов функции с соответствующими фактическими параметрами – адресами переменных или именами массивов.

Пример оформления тестового задания.

//------------------------------------------------------52-08.cpp
//-------------------------------------------------------
void F(int *p, int *q, int n) {
  for (*q = 0; n > 0; n--)
      * q = *q + *p++; 
}

void main() {
  int x,A[5]={1,3,7,1,2};
  F(A,&x,5); printf("x=%d\n",x); // Выведет 13 
}

Формальный параметр p используется в контексте *p++, что означает работу с последовательностью переменных, то есть с массивом. Число повторений цикла определяется параметром n, соответствующим размерности массива. Указатель q используется для косвенного обращения через него к отдельной переменной. Поэтому при вызове функции фактическими параметрами являются: имя массива – указатель на начало, адрес переменной – указатель на нее и константа – размерность массива, передаваемая по значению.

//-----------------------------------------------------------52-09
//-----------------------------------------------------------1
int F1(char *c) {
  for (int nc=0;*c!=0;c++)
    if (*c!=' ' && (c[1]==' ' || c[1]==0)) nc++;
  return nc;
}
//-----------------------------------------------------------2
int F2(char *c) {
  int nc; char *p;
  for (nc=0,p=c; *c!=0;c++)
            if (*c!=' ' && (p==c || c[-1]==' ')) nc++;
  return nc;}
//-----------------------------------------------------------3
void F3(char *c) {
  while (*c!=0) c++;
  *c++='*'; *c=0; }
//----------------------------------- -----------------------4
void F4(char *c) {
  for (;*c!=0;c++)
            if (*c==' ' && c[1]==' '){
                        for (char *p=c;*p!=0;p++) *p=p[1];
                        c--;
}}
//-----------------------------------------------------------5
void F5(char *c, char *out) {
  for (; *c!=0; c++)
            if (*c!=' '){
                        *out++=*c;
                        if (c[1]==' ') *out++=' ';
                        }
  *out=' ';}
//-----------------------------------------------------------6
void F6(char *c, char *out) {
  for (;*c!=0;c++)
            if (!(*c==' ' && c[1]==' ')) *out++=*c;
  *out=0 ;}
  //-----------------------------------------------------------7
  int F7(char *c) {
  for (int nc=0; *c!=0;c++)
            if (*c>='0' && *c<='9')
                        nc=nc+*c-'0';
  return nc;}
//-----------------------------------------------------------8
void F8(char *p,int B[]) {
  int nc; char *c;
  for ( nc=0,c=p;*c!=0;c++)
            if (*c!=' ' && (c==p || c[-1]==' '))
                        B[nc++]=c-p; }
//-----------------------------------------------------------9
void F9(char *c, char *out) {
  for (char *p=c; *c!=0;c++)
            if (*c!=' ' && (c[1]==' ' || c[1]==0)){
                        for (char *q=c; q>=p && *q!=' '; q-- )
                                    *out++=*q;
                        *out++=' ';
                        }
  *out=0; }
//-----------------------------------------------------------10
int F10(char *c) {
  for (;*c!=0;c++)
            if (*c>='0' && *c<='9 ') break;
  for (int s=0;*c>='0' && *c<='9';c++)
            s=s*10+*c-'0';
  return s; }
//-----------------------------------------------------------11
char *F11(char *c, int &m) {
  char *b=NULL;
  for (m=0;*c!=0;c++)
            if (*c==c[1]){
                        for (int k=2;*c==c[k];k++);
                        if (k>m) m=k,b=c;
            }
  return b; }
//----------- ------------------------------------------------12
char *F12(char *c, int &m) {
  char *b=NULL;
  int k=0;
  for (;*c!=0;c++)
            if (*c!=' ') k++;
            else{
                        if (k!=0 && k>m) m=k,b=c-k;
                        k=0;
                        }
  return b; }
//------------------------------------------------------------13
char *F13(char *c, int &m) {
  char *b=NULL;
  for (int k=0;*c!=0;c++)
            if (*c!=' '){
                        for (k=1;c[k]!=' ' && c[k]!=0;k++);
                        if (k>m) m=k,b=c;
                        c+=k-1;
            }
  return b;
}
//---------------------- -------------------------------------14
int F14(char *c) {
  int s;
  for (;*c!=0;c++)
            if (*c>='0' && *c<='9' || *c>='A' && *c<='F') break;
  for (s=0;*c>='0' && *c<='9' || *c>='A' && *c<='F';c++)
            if (*c>='0' && *c<='9')
                        s=s*16+*c-'0';
            else
                        s=s*16+*c-'A'+10;
  return s;}
//------------------------------------------------------------15
void F15(char *c) {
  for (char *p=c; *p !='\0'; p++);
  for (p--; p>c; p--,c++)
            { char s; s=*p; *p=*c; *c=s; }
}
//------------------------------------------------- ----------16
int F16(char *c) {
  for (int old=0, nw=0; *c !='\0'; c++){
            if (*c==' ') old = 0;
            else { if (old==0) nw++; old=1; }
            }
  return nw; }
//------------------------------------------------------------17
void F17(int a,char *c) {
  for (int mm=a; mm !=0; mm /=10 ,c++);
  for (mm=a, *c--='\0'; mm!=0; c--,mm=mm/10)
            *c= mm % 10 + '0';
}
//------------------------------------------------------ -----18
void F18(int a,char *c) {
  for (int mm=a; mm !=0; mm /=16 ,c++);
  for (mm=a, *c--='\0'; mm!=0; c--,mm=mm /16)
            {
            int v=mm % 16;
            if (v <=9) *c = v + '0';
            else *c = v - 10 + 'A';
}}
//------------------------------------------------------------19
int F19(char *p) {
  char *c; int ns;
  for (c=p,ns=0; *c !='\0'; c++) {
            for (int k=0; c-k >=p && c[k] !='\0'; k++)
                        if (c[-k] != c[k]) break;
            if (k >=3) ns++;
            }
  return ns; }
//------------------------------------------------------------20
char *F20(char *c1, char *c2) {
  for (; *c1 !='\0'; c1++) {
            for (int j=0; c1[j]==c2 [j]; j++);
            if (c2[j]=='\0') return c1;
            }
  return NULL;}
//------------------------------------------------------------21
char *F21(char *c, int &s) {
  int n; char *z,*p;
  for (; *c!=0; c++){
            for (p=c,n=0; *p !='\0'; p++)
                        if (*p==*c) n++;
            if (n > s) { z=c ; s=n; }
            }
  return z;
}
//------------------------------------------------------------22
void F22(double x, char *c) {
  x-=(int)x;
  int i;
  for (*c++='.', i=1; i< 6; i++) {
            x *= 10.; *c++=(int)x + '0'; x -= (int)x;
            }
  *c='\0';}
//------------------------------------------------------------23
void F23(char *c) {
  int cm=0;
  for (char *p=c; *c !='\0'; c++) {
            if (c[0]=='*' && c[1]=='/') { cm--, c++; continue; }
            if (c[0]=='/' && c[1]=='*') { cm++, c++; continue; }
            if (cm==0) *p++ = *c;
            }
  *p=0; }
//------------------------------------------------------------24
int *F24(int *p, int *q) { return *p > *q ? p : q; }
//------------------------------------------------------------25
void F25(int *p1, int *p2) { 
  int c; 
  c = *p1; 
  *p1 = *p2; 
  *p2 = c; 
}
//------------------------------------------------------------26
void F26(int *p, int *q, int n) {
  for (*q = *p; n > 0; n--, p++)
    if (*p > *q) *q = *p;
}
//------------------------------------------------------------27
int *F27(int *p, int n) { 
  int *q;
  for (q = p; n > 0; n--, p++)
  if (*p > *q) q = p;
  return q; 
}

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

//------------------------------------------------------------28
int inc1( int vv) { vv++; return vv; }
void main1(){ int a,b=5; a=inc1(b); }
//------------------ ---------------------------------------- 29
int inc2( int &vv) { vv++; return vv; }
void main2(){ int a,b=5; a=inc2(b); }
//----------------------------------------------------------- 30
int inc3( int &vv) { vv++; return vv; }
void main3(){ int a,b=5; a=inc3(+ +b); }
//----------------------------------------------------------- 31
int &inc4( int &vv) { vv++; return vv; }
void main4(){ int a,b=5; a=inc4(b); }
//----------------------------------------------------------- 32
int inc5(int &x) { x++; return x+1; }
void main5 ()
{ int x,y,z; x = 5; y = inc5(x); z=inc5(x); z=inc5(z); }
//----------------------------------------------------------- 33
int &inc6(int &x){ x++; return x; }
void main6 ()
{ int x,y,z; x = 5; y = inc6(x); z = inc6(inc6(x)); }
//---------------------------- -------------------------------34
int inc7(int x) { x++; return x+1; }
void main7 () { int x,y,z; x = 5; y=inc7(x);
z = inc7(inc7(x)); }
//------------------------------------------------------------ 35
int &F38(int &n1, int &n2){
return n1 > n2 ? n1 : n2; }
void main8(){ int x=5,y=6,z; z=F38(x,y); F38(x,y)++; }
//------------------------------------------------------------ 36
int &F39(int &n1, int &n2){
return n1 > n2 ? n1 : n2; }
void main10(){ int x=5,y=6,z; F39(x,y)=0; F39(x,y)++; }