В нашей программе бинарного поиска внутри цикла осуществляются две проверки, хотя могла быть только одна (при увеличении числа проверок вне цикла). Напишите программу, предусмотрев в ней одну проверку внутри цикла. Оцените разницу во времени выполнения.
пятница, 28 ноября 2014 г.
среда, 26 ноября 2014 г.
Конструкция else-if
Последовательность инструкций
Основное действие, выполняемое на каждом шаге поиска, — сравнение значения x (меньше, больше или равно) с элементом v[mid]; это сравнение естественно поручить конструкции else-if.
if (выражение)
инструкция
else if (выражение)
инструкция
else if (выражение)
инструкция
else if (выражение)
инструкция
else
инструкция
самый общий способ описания многоступенчатого принятия решения. Выражения вычисляются по порядку; как только встречается выражение со значением "истина", выполняется соответствующая ему инструкция; на этом последовательность проверок завершается. Здесь под словом инструкция имеется в виду либо одна инструкция, либо группа инструкций в фигурных скобках.
Последняя else-часть срабатывает, если не выполняются все предыдущие условия. Иногда в последней части не требуется производить никаких действий, в этом случае фрагмент
else
инструкция
можно опустить или использовать для фиксации ошибочной ("невозможной") ситуации.
В качестве иллюстрации трехпутевого ветвления авторы книги предлагают рассмотреть функцию бинарного поиска значения x в массиве v. Предполагается, что элементы v упорядочены по возрастанию. Функция выдает положение x в v (число в пределах от 0 до n-1 ), если x там встречается, и -1 , если его нет.
При бинарном поиске значение x сначала сравнивается с элементом, занимающим серединное положение в массиве v. Если x меньше, чем это значение, то областью поиска становится "верхняя" половина массива v, в противном случае — "нижняя". В любом случае следующий шаг — это сравнение с серединным элементом отобранной половины. Процесс "уполовинивания" диапазона продолжается до тех пор, пока либо не будет найдено значение, либо не станет пустым диапазон поиска.
int binsearch(int x, int v[], int n);
int main(void)
{
int index = 10;
int arr[10] = { 1, 3, 4, 7, 15, 18, 33, 34, 67, 88 }; /* упорядоченный по возрастанию массив из 10 элементов */
int pos; /* позиция искомого значения в массиве */
int el = 7; /* искомое значение */
pos = binsearch(el, arr, index);
printf("Значение %d имеет индекс %d\n", el, pos);
return 0;
}
/* binsearch: найти x в v[0] <= v[1] <= ... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (x < v[mid])
high = mid - 1;
else if (x > v[mid])
low = mid + 1;
else /* совпадение найдено */
return mid;
}
return -1; /* совпадения нет */
}
$ vim binsearch.c#include <stdio.h>
int binsearch(int x, int v[], int n);
int main(void)
{
int index = 10;
int arr[10] = { 1, 3, 4, 7, 15, 18, 33, 34, 67, 88 }; /* упорядоченный по возрастанию массив из 10 элементов */
int pos; /* позиция искомого значения в массиве */
int el = 7; /* искомое значение */
pos = binsearch(el, arr, index);
printf("Значение %d имеет индекс %d\n", el, pos);
return 0;
}
/* binsearch: найти x в v[0] <= v[1] <= ... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (x < v[mid])
high = mid - 1;
else if (x > v[mid])
low = mid + 1;
else /* совпадение найдено */
return mid;
}
return -1; /* совпадения нет */
}
$ cc -g -O0 -Wall -o a.out binsearch.c
$ ./a.out
Значение 7 имеет индекс 3
Основное действие, выполняемое на каждом шаге поиска, — сравнение значения x (меньше, больше или равно) с элементом v[mid]; это сравнение естественно поручить конструкции else-if.
понедельник, 24 ноября 2014 г.
Конструкция if-else
Инструкция if-else используется для принятия решения. Формально ее синтаксисом является:
if (выражение)
инструкция1
else
инструкция2
причем else-часть может и отсутствовать. Сначала вычисляется выражение, и, если оно истинно (т. е. отлично от нуля), выполняется инструкция1. Если выражение ложно (т. е. его значение равно нулю) и существует else-часть, то выполняется инструкция2.
if (выражение)
короче, чем
if (выражение != 0)
Отсутствие else-части в одной из вложенных друг в друга if-конструкций может привести к неоднозначному толкованию записи. Эту неоднозначность разрешают тем, что else связывают с ближайшим if, у которого нет своего else. Например, в
if (а > Ь)
z = а;
else
z = b;
else относится к внутреннему if, что и показано с помощью отступов.
Если требуется иная интерпретация, необходимо должным образом расставить фигурные скобки:
if (n > 0) {
if (a > b)
z = а;
}
else
z = b;
if (a > b)
z = а;
}
else
z = b;
Инструкции и блоки
Порядок, в котором выполняются вычисления, определяется инструкциями управления.
Выражения, х = 0, или i++, или printf (...) , становятся инструкциями, если в конце них поставить точку с запятой, например:
х = 0;
i++;
printf (...);
В Си точка с запятой является заключающим символом инструкции.
Фигурные скобки, обрамляющие группу инструкций, образующих тело функции, — это один пример; второй пример — это скобки, объединяющие инструкции, помещенные после if, else, while или for.
пятница, 21 ноября 2014 г.
Приоритет и очередность вычислений
Таблица 1. Приоритеты и очередность вычислений операторов
| Операторы | Выполняются | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| () | [] | -> | . | слева направо | |||||||
| ! | ~ | ++ | -- | + | - | * | & | (type) | sizeof | справа налево | |
| * | / | % | слева направо | ||||||||
| + | - | слева направо | |||||||||
| << | >> | слева направо | |||||||||
| < | <= | > | >= | слева направо | |||||||
| == | != | слева направо | |||||||||
| & | слева направо | ||||||||||
| ^ | слева направо | ||||||||||
| | | слева направо | ||||||||||
| && | слева направо | ||||||||||
| || | слева направо | ||||||||||
| ?: | справа налево | ||||||||||
| = | += | -= | *= | /= | %= | &= | ^= | |= | <<= | >>= | справа налево |
| , | слева направо | ||||||||||
Примечание. Унарные операторы +, -, * и & имеют более высокий приоритет, чем те же бинарные операторы.
Приоритеты побитовых операторов &, ^ и | ниже, чем приоритет == и !=, из-за чего в побитовых проверках, таких как
if ((х & MASK) == 0) ...
чтобы получить правильный результат, необходимо использовать скобки.
чтобы получить правильный результат, необходимо использовать скобки.
В языке Си очередность вычисления операндов оператора не фиксируется. В инструкции
х = f() + g();
f может быть вычислена раньше g или наоборот. Из этого следует, что если одна из функций изменяет значение переменной, от которой зависит другая функция, то помещаемый в x результат может зависеть от очередности вычислений. Чтобы обеспечить нужную последовательность вычислений, промежуточные результаты можно запоминать во временных переменных.
printf("%d %d\n", ++n, power(2, n)); /* НЕВЕРНО */
может давать несовпадающие результаты. Результат вызова функции зависит от того, когда компилятор сгенерирует команды увеличения n — до или после обращения к power. Чтобы обезопасить себя от возможного побочного эффекта, достаточно написать
++n;
printf("%d %d\n", n, power(2, n));
printf("%d %d\n", n, power(2, n));
Обращения к функциям, вложенные присвоения, инкрементные и декрементные операторы дают "побочный эффект", проявляющийся в том, что при вычислении выражения значения некоторых переменных изменяются. В любом выражении с побочным эффектом может быть скрыта трудно просматриваемая зависимость результата выражения от очередности изменения значений переменных, входящих в выражение. В такой, например, типично неприятной ситуации
a[i] = i++;
возникает вопрос: массив a индексируется старым или измененным значением i?
Авторы книги рекомендуют не писать программы, зависящие от очередности вычислений, так как компиляторы могут по-разному их генерировать в зависимости от архитектуры машины.
Упражнение 2.10.
Напишите функцию lower, которая переводит большие буквы в малые, используя условное выражение (а не конструкцию if-else).
Условные выражения
Инструкции
if (а > b)
z = a;
else
z = b;
пересылают в z большее из двух значений a и b. Условное выражение, написанное с помощью тернарного (т.е. имеющего три операнда) оператора ?:, представляет собой другой способ записи этой и подобных ей конструкций:
z = (a > b) ? а : b; /* z = max(a, b) */
выр1 ? выр2 : выр3
первым вычисляется выражение выр1. Если его значение не нуль (истина), то вычисляется выражение выр2 и значение этого выражения становится значением всего условного выражения. В противном случае вычисляется выражение выр3 и его значение становится значением условного выражения. Следует отметить, что из выражений выр2 и выр3 вычисляется только одно из них.
Условное выражение и в самом деле является выражением, и его можно использовать в любом месте, где допускается выражение.
Если выр2 и выр3 принадлежат разным типам, то тип результата определяется правилами преобразования, о которых шла речь ранее. Например, если f имеет тип float, a n — тип int, то типом выражения
(n > 0) ? f : n
будет float вне зависимости от того, положительно значение n или нет.
Заключать в скобки первое выражение в условном выражении не обязательно, так как приоритет ?: очень низкий (более низкий приоритет имеет только присваивание), но авторы книги рекомендуют всегда это делать, для лучшего восприятия.
В качестве примера приведится цикл, обеспечивающий печать n элементов массива по 10 на каждой строке с одним пробелом между колонками; каждая строка цикла, включая последнюю, заканчивается символом новой строки:
В качестве примера приведится цикл, обеспечивающий печать n элементов массива по 10 на каждой строке с одним пробелом между колонками; каждая строка цикла, включая последнюю, заканчивается символом новой строки:
#include <stdio.h>
int main(void)
{
int i, n;
char a[] = "C is a general-purpose programming language initially developed by Dennis Ritchie.";
n = sizeof(a);
for (i = 0; i < n; i++)
printf("%6d%c", a[i], (i % 10 == 9 || i == n - 1) ? '\n' : ' ');
return 0;
}
Символ новой строки посылается после каждого десятого и после n-го элемента. За всеми другими элементами следует пробел.
Еще один пример:
#include <stdio.h>
int main(void)
{
Символ новой строки посылается после каждого десятого и после n-го элемента. За всеми другими элементами следует пробел.
Еще один пример:
#include <stdio.h>
int main(void)
{
int n;
char a[] = "Привет, мир!";
n = sizeof(a);
printf("Вы имеете %d элемент%s.\n", n, (n % 10 == 1 && n % 100 != 11) ?
" " : ((n % 100 < 10 || n % 100 > 20) && n % 10 >= 2 && n % 10 <= 4) ?
"а" : "ов");
return 0;
}
Упражнение 2.9.
Применительно к числам, в представлении которых использован дополнительный код, выражение х &= (х-1) уничтожает самую правую 1 в х. Объясните, почему. Используйте это наблюдение при написании более быстрого варианта функции bitcount.
Операторы и выражения присваивания
Выражение
i = i + 2
в котором стоящая слева переменная повторяется и справа, можно написать в сжатом виде:
i += 2
Оператор +=, как и =, называется оператором присваивания.
Большинству бинарных операторов (аналогичных + и имеющих левый и правый операнды) соответствуют операторы присваивания ор=, где ор — один из операторов
+ * / % << >> & ^ |
Если выр1 и выр2 — выражения, то
выр1 ор= выр2
эквивалентно
выр1 = (выр1) ор (выр2)
с той лишь разницей, что выр1 вычисляется только один раз. Обратите внимание на скобки вокруг выр2:
x *= y + 1
эквивалентно
x = x * (y + 1)
но не
x = x * y + 1
В качестве примера авторы книги приводят функцию bitcount, подсчитывающую число единичных битов в своем аргументе целочисленного типа:
#include <stdio.h>
int bitcount(unsigned x);
int main(void)
{
printf("%u\n", bitcount(100));
return 0;
}
/* bitcount: подсчет единиц в х */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
Кроме того, в сложных выражениях вроде
yyval[yypv[p3 + p4] + yypv[p1 + p2]] += 2
благодаря оператору присваивания += запись становится более легкой для понимания, так как читателю при такой записи не потребуется старательно сравнивать два длинных выражения.
Присваивание вырабатывает значение и может применяться внутри выражения:
Типом и значением любого выражения присваивания являются тип и значение его левого операнда после завершения присваивания.
i = i + 2
в котором стоящая слева переменная повторяется и справа, можно написать в сжатом виде:
i += 2
Оператор +=, как и =, называется оператором присваивания.
Большинству бинарных операторов (аналогичных + и имеющих левый и правый операнды) соответствуют операторы присваивания ор=, где ор — один из операторов
+ * / % << >> & ^ |
Если выр1 и выр2 — выражения, то
выр1 ор= выр2
эквивалентно
выр1 = (выр1) ор (выр2)
с той лишь разницей, что выр1 вычисляется только один раз. Обратите внимание на скобки вокруг выр2:
x *= y + 1
эквивалентно
x = x * (y + 1)
но не
x = x * y + 1
#include <stdio.h>
int bitcount(unsigned x);
int main(void)
{
printf("%u\n", bitcount(100));
return 0;
}
/* bitcount: подсчет единиц в х */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
Независимо от машины, на которой будет работать эта программа, объявление аргумента x как unsigned гарантирует, что при правом сдвиге освобождающиеся биты будут заполняться нулями, а не знаковым битом.
yyval[yypv[p3 + p4] + yypv[p1 + p2]] += 2
благодаря оператору присваивания += запись становится более легкой для понимания, так как читателю при такой записи не потребуется старательно сравнивать два длинных выражения.
while ((с = getchar()) != EOF)
...
...
В выражениях встречаются и другие операторы присваивания (+=, -= и т.д.), хотя и реже.
Типом и значением любого выражения присваивания являются тип и значение его левого операнда после завершения присваивания.
среда, 19 ноября 2014 г.
Упражнение 2.8.
Напишите функцию rightrot(х, n), которая циклически сдвигает x вправо на n разрядов.
Упражнение 2.7.
Напишите функцию invert(х, р, n), возвращающую значение x с инвертированными n битами, начиная с позиции p (остальные биты не изменяются).
Упражнение 2.6.
Напишите функцию setbits(x, p, n, y), возвращающую значение x, в котором n битов, начиная с p-й позиции, заменены на n правых разрядов из y (остальные биты не изменяются).
четверг, 13 ноября 2014 г.
Побитовые операторы
В Си имеются шесть операторов для манипулирования с битами. Их можно применять только к целочисленным операндам, т. е. к операндам типов char, short, int и long, знаковым и беззнаковым.
& — побитовое И.
| — побитовое ИЛИ.
^ — побитовое исключающее ИЛИ.
<< — сдвиг влево.
>> — сдвиг вправо.
~ — побитовое отрицание (унарный).
Оператор & (побитовое И) часто используется для обнуления некоторой группы разрядов.
х = х | SET_ON;
устанавливает единицы в тех разрядах х, которым соответствуют единицы в SET_ON.
unsigned getbits(unsigned х, int p, int n);
int main(void)
& — побитовое И.
| — побитовое ИЛИ.
^ — побитовое исключающее ИЛИ.
<< — сдвиг влево.
>> — сдвиг вправо.
~ — побитовое отрицание (унарный).
Оператор & (побитовое И) часто используется для обнуления некоторой группы разрядов.
Например
n = n & 0177;
обнуляет в n все разряды, кроме младших семи.
n = n & 0177;
обнуляет в n все разряды, кроме младших семи.
Число 0177 записано в восьмеричной системе. В двоичной системе это число равно
0000 0000 0000 0000 0000 0000 0111 1111, размер целого на моей машине 4 байта.
Пусть целая переменная n = 65535
(0000 0000 0000 0000 1111 1111 1111 1111 в двоичном виде)
0000 0000 0000 0000 1111 1111 1111 1111
&
0000 0000 0000 0000 0000 0000 0111 1111
---------------------------------------
0000 0000 0000 0000 0000 0000 0111 1111
#include <stdio.h>
int main(void)
{
int n = 65535;
n = n & 0177;
int main(void)
{
int n = 65535;
n = n & 0177;
printf("%d\n", n);
}
Восьмеричные числа используются из-за удобства при работе с двоичной системой счисления. Каждая цифра восьмеричного числа может быть заменена тремя цифрами двоичного.
Таблица соответствия цифр восьмеричной системы счисления числам двоичной системы:
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
Оператор | (побитовое ИЛИ) применяют для установки разрядов; так,
}
Восьмеричные числа используются из-за удобства при работе с двоичной системой счисления. Каждая цифра восьмеричного числа может быть заменена тремя цифрами двоичного.
0 000
2 010
3 011
4 100
5 101
6 110
7 111
х = х | SET_ON;
устанавливает единицы в тех разрядах х, которым соответствуют единицы в SET_ON.
#include <stdio.h>
#define SET_ON 07 /* 0000 0000 0000 0000 0000 0000 0000 0111 */
int main(void)
{
int n = 120; /* 0000 0000 0000 0000 0000 0000 0111 1000 */
n = n | SET_ON;
printf("%d\n", n);
}
0000 0000 0000 0000 0000 0000 0000 0111
|
0000 0000 0000 0000 0000 0000 0111 1000
---------------------------------------
0000 0000 0000 0000 0000 0000 0111 1111
Оператор ^ (побитовое исключающее ИЛИ) в каждом разряде установит 1, если соответствующие разряды операндов имеют различные значения, и 0, когда они совпадают.
#include <stdio.h>
int main(void)
{
int a = 017; /* 0000 0000 0000 0000 0000 0000 0000 1111 */
int b = 036; /* 0000 0000 0000 0000 0000 0000 0001 1110 */
int c = 0;
c = a ^ b;
printf("%o ^ %o = %o\n", a, b, c);
printf("%x ^ %x = %x\n", a, b, c);
}
17 ^ 36 = 21
f ^ 1e = 11
0000 0000 0000 0000 0000 0000 0000 1111
^
0000 0000 0000 0000 0000 0000 0001 1110
---------------------------------------
0000 0000 0000 0000 0000 0000 0001 0001
Операторы << и >> сдвигают влево или вправо свой левый операнд на число битовых позиций, задаваемое правым операндом, который должен быть неотрицательным. Так, х << 2 сдвигает значение х влево на 2 позиции, заполняя освобождающиеся биты нулями, что эквивалентно умножению х на 4. Сдвиг вправо беззнаковой величины всегда сопровождается заполнением освобождающихся разрядов нулями.
#include <stdio.h>
int main(void)
{
unsigned char a = 11; /* 0000 1011 */
a = a << 2;
printf("The result is %d\n", a);
}
0000 1011 11
<< 2 *4
0010 1100 44
Как видно из примера, освободившиеся биты справа заполнились нулями.
#include <stdio.h>
int main(void)
{
unsigned char a = 11; /* 0000 1011 */
a = a >> 2;
printf("The result is %d\n", a);
}
0000 1011 11
>> 2 /4
0000 0010 11 2
Сдвиг числа на 2 разряда вправо равносилен его делению на 4. Выдвигаемые наружу разряды содержат остаток от деления (11 в двоичной системе = 3 в десятичной; 11 % 4 = 3).
Сдвиг вправо знаковой величины на одних машинах происходит с распространением знака ("арифметический сдвиг"), на других — с заполнением освобождающихся разрядов нулями ("логический сдвиг").
#include <stdio.h>
int main(void)
{
signed char a = -16; /* 1111 0000 */
a = a >> 2;
printf("The result is %d\n", a);
}
1111 0000 -16
>> 2 /4
1111 1100 -4
На моей машине сдвиг арифметический, освободившиеся разряды нулями не заполняются.
Унарный оператор ~ поразрядно "обращает" целое т. е. превращает каждый единичный бит в нулевой и наоборот. Например
#include <stdio.h>
int main(void)
{
unsigned char a = 11; /* 0000 1011 */
a = a << 2;
printf("The result is %d\n", a);
}
The result is 44
0000 1011 11
<< 2 *4
0010 1100 44
Как видно из примера, освободившиеся биты справа заполнились нулями.
#include <stdio.h>
int main(void)
{
unsigned char a = 11; /* 0000 1011 */
a = a >> 2;
printf("The result is %d\n", a);
}
The result is 2
0000 1011 11
>> 2 /4
0000 0010 11 2
Сдвиг числа на 2 разряда вправо равносилен его делению на 4. Выдвигаемые наружу разряды содержат остаток от деления (11 в двоичной системе = 3 в десятичной; 11 % 4 = 3).
Сдвиг вправо знаковой величины на одних машинах происходит с распространением знака ("арифметический сдвиг"), на других — с заполнением освобождающихся разрядов нулями ("логический сдвиг").
#include <stdio.h>
int main(void)
{
signed char a = -16; /* 1111 0000 */
a = a >> 2;
printf("The result is %d\n", a);
}
The result is -4
1111 0000 -16
>> 2 /4
1111 1100 -4
На моей машине сдвиг арифметический, освободившиеся разряды нулями не заполняются.
Унарный оператор ~ поразрядно "обращает" целое т. е. превращает каждый единичный бит в нулевой и наоборот. Например
х = х & ~077
обнуляет в х последние 6 разрядов. Заметим, что запись х & ~077 не зависит от длины слова, и, следовательно, она лучше, чем х & 0177700, поскольку последняя подразумевает, что х занимает 16 битов. Не зависимая от машины форма записи ~077 не потребует дополнительных затрат при счете, так как ~077 — константное выражение, которое будет вычислено во время компиляции.
077 - 0000 0000 0011 1111
~077 - 1111 1111 1100 0000 - 177700 (2 байта)
1111 1111 1111 1111 1111 1111 1100 0000 - 37777777700 (4 байта)
Для иллюстрации некоторых побитовых операций авторы книги предлагают рассмотреть функцию getbits(x, p, n), которая формирует поле в n битов, вырезанных из х, начиная с позиции p, прижимая его к правому краю. Предполагается, что 0-й бит — крайний правый бит, а n и p — осмысленные положительные числа. Например, getbits(x, 4, 3) вернет в качестве результата 4, 3 и 2-й биты значения х, прижимая их к правому краю:
#include <stdio.h>
unsigned getbits(unsigned х, int p, int n);
int main(void)
{
printf("%u\n", getbits(126, 4, 3));
return 0;
}
/* getbits: получает n бит, начиная с р-й позиции */
unsigned getbits(unsigned х, int p, int n)
{
return (х >> (p + 1 - n)) & ~(~0 << n);
}
Выражение х >> (p+1-n) сдвигает нужное нам поле к правому краю. Константа ~0 состоит из одних единиц, и ее сдвиг влево на n бит (~0 << n) приведет к тому, что правый край этой константы займут n нулевых разрядов. Еще одна операция побитовой инверсии ~ позволяет получить справа n единиц.
Упражнение 2.5.
Напишите функцию any(s1, s2), которая возвращает либо ту позицию в s1, где стоит первый символ, совпавший с любым из символов в s2, либо -1 (если ни один символ из s1 не совпадает с символами из s2).
(Стандартная библиотечная функция strpbrk делает то же самое, но выдает не номер позиции символа, а указатель на символ.)
(Стандартная библиотечная функция strpbrk делает то же самое, но выдает не номер позиции символа, а указатель на символ.)
Упражнение 2.4.
Напишите версию функции squeeze(s1, s2), которая удаляет из s1 все символы, встречающиеся в строке s2.
Операторы инкремента и декремента
В Си есть два оператора, предназначенных для увеличения и уменьшения переменных. Оператор инкремента ++ добавляет 1 к своему операнду, а оператор декремента -- вычитает 1.
Необычность операторов ++ и -- в том, что их можно использовать и как префиксные (помещая перед переменной: ++n), и как постфиксные (помещая после переменной: n++) операторы. В обоих случаях значение n увеличивается на 1, но выражение ++n увеличивает n до того, как его значение будет использовано,
а n++ — после того.
а n++ — после того.
Предположим, что n содержит 5, тогда
x = n++;
установит x в значение 5, а
x = ++n;
установит х в значение 6. И в том и другом случае n станет равным 6.
if (c == '\n')
nl++;
nl++;
то безразлично, какой оператор выбрать — префиксный или постфиксный.
Но существуют ситуации, когда требуется оператор вполне определенного типа. В качестве примера, авторы книги предлагают рассмотреть функцию
squeeze(s, с), которая удаляет из строки s все символы, совпадающие с c:
#include <stdio.h>
#define MAXLINE 1000 /* максимальный размер вводимой строки */
int getstr(char line[], int maxline);
void squeeze(char s[], int с);
int c = 65; /* Символ 'A' */
int main(void)
{
int len = 0;
char line[MAXLINE]; /* текущая строка */
while ((len = getstr(line, MAXLINE)) > 0)
{
squeeze(line, c);
printf("%s", line);
}
return 0;
}
/* getline: читает строку в s, возвращает длину */
int getstr(char s[], int lim)
{
int c, i;
for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; ++i)
s[i] = c;
if (c == '\n')
{
s[i] = c;
++i;
}
s[i] = '\0'; /* в конец строки дописывам "0" */
return i; /* функция возвращает длину строки */
}
/* squeeze: удаляет все с из s */
void squeeze(char s[], int с)
{
int i, j;
for (i = j = 0; s[i] != '\0'; i++)
if (s[i] != c)
s[j++] = s[i];
s[i] = '\0';
}
#include <stdio.h>
#define MAXLINE 1000 /* максимальный размер вводимой строки */
int getstr(char line[], int maxline);
void squeeze(char line[], int symbol);
int main(void)
{
int len = 0;
char line[MAXLINE]; /* текущая строка */
int c = 65; /* Символ 'A' */
while ((len = getstr(line, MAXLINE)) > 0)
{
squeeze(line, c);
printf("%s", line);
}
return 0;
}
/* getline: читает строку в s, возвращает длину */
int getstr(char s[], int lim)
{
int c, i;
for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; ++i)
s[i] = c;
if (c == '\n')
{
s[i] = c;
++i;
}
s[i] = '\0'; /* в конец строки дописывам "0" */
return i; /* функция возвращает длину строки */
}
/* squeeze: удаляет все с из s */
void squeeze(char s[], int symb)
{
int i, j;
for (i = j = 0; s[i] != '\0'; i++)
if (s[i] != symb)
s[j++] = s[i];
s[i] = '\0';
}
if (s[i] != с) {
s[j] = s[i];
j++;
}
squeeze(s, с), которая удаляет из строки s все символы, совпадающие с c:
#include <stdio.h>
#define MAXLINE 1000 /* максимальный размер вводимой строки */
int getstr(char line[], int maxline);
void squeeze(char s[], int с);
int c = 65; /* Символ 'A' */
int main(void)
{
int len = 0;
char line[MAXLINE]; /* текущая строка */
while ((len = getstr(line, MAXLINE)) > 0)
{
squeeze(line, c);
printf("%s", line);
}
return 0;
}
/* getline: читает строку в s, возвращает длину */
int getstr(char s[], int lim)
{
int c, i;
for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; ++i)
s[i] = c;
if (c == '\n')
{
s[i] = c;
++i;
}
s[i] = '\0'; /* в конец строки дописывам "0" */
return i; /* функция возвращает длину строки */
}
/* squeeze: удаляет все с из s */
void squeeze(char s[], int с)
{
int i, j;
for (i = j = 0; s[i] != '\0'; i++)
if (s[i] != c)
s[j++] = s[i];
s[i] = '\0';
}
#include <stdio.h>
#define MAXLINE 1000 /* максимальный размер вводимой строки */
int getstr(char line[], int maxline);
void squeeze(char line[], int symbol);
int main(void)
{
int len = 0;
char line[MAXLINE]; /* текущая строка */
int c = 65; /* Символ 'A' */
while ((len = getstr(line, MAXLINE)) > 0)
{
squeeze(line, c);
printf("%s", line);
}
return 0;
}
/* getline: читает строку в s, возвращает длину */
int getstr(char s[], int lim)
{
int c, i;
for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; ++i)
s[i] = c;
if (c == '\n')
{
s[i] = c;
++i;
}
s[i] = '\0'; /* в конец строки дописывам "0" */
return i; /* функция возвращает длину строки */
}
/* squeeze: удаляет все с из s */
void squeeze(char s[], int symb)
{
int i, j;
for (i = j = 0; s[i] != '\0'; i++)
if (s[i] != symb)
s[j++] = s[i];
s[i] = '\0';
}
Каждый раз, когда встречается символ, отличный от с, он копируется в текущую j-ю позицию, и только после этого переменная j увеличивается на 1, подготавливаясь таким образом к приему следующего символа. Это в точности совпадает со следующими действиями:
if (s[i] != с) {
s[j] = s[i];
j++;
}
if (с == '\n' ) {
s[i] = с;
++i;
}
s[i] = с;
++i;
}
можно переписать более компактно:
if (с == '\n' )
s[i++] = с;
s[i++] = с;
В качестве третьего примера рассматривается функция strcut(s, t), которая строку t помещает в конец строки s. Предполагается, что в s достаточно места, чтобы разместить там суммарную строку. strcut написана так, что она не возвращает никакого результата. На самом деле библиотечная strcat возвращает указатель на результирующую строку.
#include <stdio.h>
#define MAXLINE 1000 /* максимальный размер вводимой строки */
int getstr(char line[], int maxline);
void strcut(char line[], char new_line[]);
int main(void)
{
int len = 0;
char line[MAXLINE]; /* текущая строка */
char new_line[] = "This is the end!";
while ((len = getstr(line, MAXLINE)) > 0)
{
strcut(line, new_line);
printf("%s", line);
}
return 0;
}
/* getline: читает строку в s, возвращает длину */
int getstr(char s[], int lim)
{
int c, i;
for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; ++i)
s[i] = c;
if (c == '\n')
s[i++] = c;
s[i] = '\0'; /* в конец строки дописывам "0" */
return i; /* функция возвращает длину строки */
}
/* strcut: помещает t в конец s; s достаточно велика */
void strcut(char s[], char t[])
{
int i, j;
i = j = 0;
while (s[i] != '\0') /* находим конец s */
i++;
while ((s[i++] = t[j++]) != '\0') /* копируем t */
;
}
При копировании очередного символа из t в s постфиксный оператор ++ применяется и к i, и к j, чтобы на каждом шаге цикла переменные i и j правильно отслеживали позиции перемещаемого символа.
Подписаться на:
Сообщения (Atom)