ex.2.2. Напишите цикл, эквивалентный приведенному выше for-циклу, не пользуясь операторами && и ||.
#include <stdio.h>
int lim = 10;
int main()
{
int i, c;
char s[lim];
i = 0;
while (i < lim-1) {
c = getchar();
if (c == EOF)
break;
if (c == '\n')
break;
s[i++] = c;
}
s[i] = '\0';
printf("%s", s);
return 0;
}
ex.2.3. Напишите функцию htoi(s), которая преобразует последовательность шестнадцатеричных цифр, начинающуюся с 0x или 0X, в соответствующее целое. Шестнадцатеричными цифрами являются символы 0...9, a...f, А...F.
#include <stdio.h>
int htoi(char m[]);
int lower(int c);
int hex_a_f_to_int(int c);
int main()
{
int n;
char s[] = "0xb1A\0";
n = htoi(s);
printf("%x", n);
return 0;
}
/* htoi: преобразование hex в целое */
int htoi(char s[])
{
int i = 0;
int answer = 0;
int valid = 1;
int hex_a_f;
/* squeeze: удаляет все символы s2 из s1*/
void squeeze(char s1[], char s2[])
{
int i, j, k;
for (i = j = 0; s1[i] != '\0'; i++) {
for (k = 0; s2[k] != s1[i] && s2[k] != '\0'; k++);
if (k == len)
s1[j++] = s1[i];
}
s1[j] = '\0';
}
/* strlen: возвращает длину строки s */
int strlen(char s[])
{
int i;
i = 0;
while (s[i] != '\0')
++i;
return i;
}
ex.2.5. Напишите функцию any(s1,s2), которая возвращает либо ту позицию в s1, где стоит первый символ, совпавший с любым из символов в s2, либо -1 (если ни один символ из s1 не совпадает с символами из s2). (Стандартная библиотечная функция strpbrk делает то же самое, но выдает не номер позиции символа, а указатель на символ.)
#include <stdio.h>
int any(char s1[], char s2[]);
int strlen(char s[]);
int main()
{
char s1[] = "test string\0";
printf("s1 = %s\n\n", s1);
char s2[] = "ring\0";
printf("s2 = %s\n", s2);
printf("position of first occurrence = %d\n", any(s1, s2));
return 0;
}
/* any: возвращает индекс первого вхождения символа из s2 в s1*/
int any(char s1[], char s2[])
{
int i, j, k;
int len = strlen(s1);
int first = len;
for (i = j = 0; s1[i] != '\0'; i++)
for (k = 0; s2[k] != '\0'; k++)
if (s2[k] == s1[i] && i < first)
first = i;
if (first == len)
first = -1;
return first;
}
ex.2.6. Напишите функцию setbits(x, p, n, y), возвращающую значение x, в котором n битов, начиная с p-й позиции, заменены на n правых разрядов из y (остальные биты не изменяются).
#include <stdio.h>
unsigned setbits(unsigned x, int p, int n, unsigned y);
void printfbit(unsigned n);
int main()
{
printf("76543210\n\n");
unsigned c1 = 'f';
printfbit(c1);
unsigned c2 = 'z';
printfbit(c2);
printfbit(setbits(c1, 5, 3, c2));
return 0;
}
/* setbits: x получает n правых бит из y, начиная с p-й позиции */
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
return ( (~0 << (p+1)) & x ) | ( ~(~0 << (p+1-n)) & x ) | \\
(~(~0 << n) & y) << (p+1-n);
}
ex.2.7. Напишите функцию invert(x, p, n), возвращающую значение x с инвертированными n битами, начиная с позиции p (остальные биты не изменяются).
#include <stdio.h>
unsigned invert(unsigned x, int p, int n);
void printfbit(unsigned n);
int main()
{
printf("76543210\n\n");
unsigned c = 'f';
printfbit(c);
printfbit(invert(c, 5, 3));
return 0;
}
/* invert: инвертирует n бит из x, начиная с p-й позиции */
unsigned invert(unsigned x, int p, int n)
{
return ( ((~x >> (p+1-n)) & ~(~0 << n)) << (p+1-n) ) | \\
(~( ((~0 >> (p+1-n)) & ~(~0 << n)) << (p+1-n) ) & x);
}
ex.2.8. Напишите функцию rightrot (x, n), которая циклически сдвигает x вправо на n разрядов.
#include <stdio.h>
unsigned rightrot(unsigned x, int n);
void printfbit(unsigned n);
int main()
{
printf("76543210\n\n");
unsigned c = 'f';
printfbit(c);
printfbit(rightrot(c, 3));
return 0;
}
/* rightrot: сдвиг x на n вправо */
unsigned rightrot(unsigned x, int n)
{
return ((~(~0 << n) & x) << (8-n)) | x >> n;
}
ex.2.9. Применительно к числам, в представлении которых использован дополнительный код, выражение x &= (x-1) уничтожает самую правую единицу в x. Объясните, почему. Используйте это наблюдение при написании более быстрого варианта функции bitcount.
Объяснение. Если х нечетно, то (х-1) имеет такое же битовое представление как и х, за исключением того, что крайний правый бит в нем равен 0. В этом случае (х & (х-1)) == (х-1). Если же х четно, то в представлении (х-1) нули, стоявшие в х справа становятся единицами, а крайняя правая единица -- нулем. Конъюнкция х & (х-1) очищает эти позиции вплоть до того места, когда встретит единицы в представлениях обоих чисел (т.е. единицу, бывшую в x до этого шага второй справа).
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x &= (x-1))
b++;
return b;
}
Упражнение 3.2. Напишите функцию escape(s,t), которая при копировании текста из t в s преобразует такие символы, как новая строка и табуляция в "видимые последовательности символов" (вроде \n и \t). Используйте инструкцию switch. Напишите функцию, выполняющую обратное преобразование эскейп-последовательностей в настоящие символы.
Упражнение 3.3. Напишите функцию expand(s1,s2), заменяющую сокращенную запись наподобие a-z в строке s1 эквивалентной полной записью аbс...хуz в s2. В s1 допускаются буквы (прописные и строчные) и цифры. Следует уметь справляться с такими случаями, как a-b-c, a-z0-9 и -a-b. Считайте знак '-' в начале или в конце s1 обычным символом минус.
#include <stdio.h>
#include <ctype.h>
#define MAXLEN 30
void expand(char s1[], char s2[]);
int main()
{
char in[MAXLEN] = "-1-67-9-\0";
char out[MAXLEN];
Упражнение 3.5. Напишите функцию itob(n,s,b), которая переводит целое n в строку s, представляющую число по основанию b. В частности, itob(n, s, 16) помещает в s текст числа n в шестнадцатеричном виде.
/* itob: преобразование n в строку s, представляющую
* число по основанию b (2 <= b <= 16) */
void itob(int n, char s[], int b) {
int i, sign;
char digits[] = "0123456789ABCDEF";
sign = n; /* сохраняем знак */
i = 0;
do { /* генерируем цифры в обратном порядке */
s[i++] = digits[n % b]; /* следующая цифра */
} while ( n /= b ); /* исключить ее */
if (sign < 0)
s[i++] = '-';
/* getl: читает строку в s, возвращает длину */
int getl(char s[], int lim)
{
int c, i;
i = 0;
while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
s[i++] = c;
if (c == '\n')
s[i++] = c;
s[i] = '\0';
return i;
}
/* strrindex: вычисляет выдает позицию самого правого вхождения t в s
* или выдает -1, если t нет в s */
int strrindex (char s[], char t[])
{
int i, j, k;
int tmp = -1;
for (i = 0; s[i] != '\0'; i++) {
for (j = i, k = 0; t[k] != '\0' && s[j] == t[k]; j++, k++);
if (k > 0 && t[k] == '\0' && i > tmp)
tmp = i;
}
return tmp;
}
Упражнение 4.2. Дополните функцию atof таким образом, чтобы она справлялась с числами вида: 123.45e-6, в которых после мантиссы может стоять e (или E) с последующим порядком (быть может, со знаком).
Упражнение 4.7. Напишите программу ungets(s), возвращающую строку s во входной поток. Должна ли ungets "знать" что-либо о переменных buf и bufp, или ей достаточно пользоваться только функцией ungetch?
Упражнение 4.10. В основу программы калькулятора можно положить применение функции getline, которая читает целиком строку; при этом отпадает необходимость в getch и ungetch. Напишите программу, реализующую этот подход.
#include <stdio.h>
#include <stdlib.h> /* для atof() */
#define MAXOP 100 /* макс. размер операнда или оператора */
#define NUMBER '0' /* признак числа */
#define MAXLINE 500 /* макс. размер строки ввода */
int getop (char []);
int getl(char [], int);
void push (double);
double pop (void);
char line[MAXLINE];
int line_i;
/* калькулятор с обратной польской записью */
int main()
{
int type;
double op2;
char s[MAXOP];
while (getl(line, MAXLINE) != 0)
{
line_i = 0;
while ((type = getop(s)) != '\0')
{
switch (type)
{
case NUMBER:
push (atof(s));
break;
case '+':
push (pop() + pop());
break;
case '*':
push (pop() * pop());
break;
case '-':
op2 = pop();
push (pop() - op2);
break;
case '/':
op2 = pop();
if (op2 != 0.0)
push (pop() / op2);
else
printf("ошибка: деление на нуль\n");
break;
case '\n':
printf("\t%.8g\n", pop());
break;
default:
printf("ошибка: неизвестная операция %s\n", s);
break;
}
}
}
return 0;
}
#include <ctype.h>
/* getop: получает следующий оператор или операнд */
int getop(char s[])
{
int i, c;
while ((s[0] = c = line[line_i++]) == ' ' || c == '\t');
s[1] = '\0';
if (!isdigit(c) && c != '.')
return c; /* не число */
i = 0;
if (isdigit(c)) /* накапливаем целую часть */
while (isdigit(si] = c = line[line_i));
if (c =='.') /* накапливаем дробную часть */
while (isdigit(si] = line[line_i));
s[i] = '\0';
line_i--;
return NUMBER;
}
/* getline: читает строку в s, возвращает длину */
int getl(char s[], int lim)
{
int c, i;
i = 0;
while (--lim > 0 && (c = getchar()) != EOF && c != '\n')
s[i++] = c;
if (c == '\n')
s[i++] = c;
s[i] = '\0';
return i;
}
Упражнение 4.11. Модифицируйте функцию getop так, чтобы отпала необходимость в функции ungetch. Подсказка: используйте внутреннюю статическую переменную.
int getop(char s[])
{
int i;
static int c;
while ((s[0] = c = getch()) == ' ' || c == '\t');
s[1] = '\0';
if (!isdigit(c) && c != '.')
return c; /* не число */
i = 0;
if (isdigit(c)) /* накапливаем целую часть */
while (isdigit(s[++i] = c = getch()));
if (c =='.') /* накапливаем дробную часть */
while (isdigit(s[++i] = c = getch()));
s[i] = '\0';
Упражнение 4.12. Примените идеи, которые мы использовали в printd, для написания рекурсивной версии функции itoa; иначе говоря, преобразуйте целое число в строку цифр с помощью рекурсивной программы.
#include <stdio.h>
void itoa(int n, char s[]);
void reverse(char s[]);
Упражнение 4.14. Определите swap(t,x,y) в виде макроса, который осуществляет обмен значениями указанного типа t между аргументами x и y. (Примените блочную структуру.)
#include <stdio.h>
#define swap(t,x,y) {t temp = x; x = y; y = temp;}
int main(void) {
int ai=1, bi=2;
printf("Initial: ai=d\n", ai, bi);
swap(int, ai, bi);
printf("Swapped: ai=d\n", ai, bi);
float af=1.0, bf=2.0;
printf("Initial: af=f\n", af, bf);
swap(float, af, bf);
printf("Swapped: af=f\n", af, bf);
Упражнение 5.1. Функция getint написана так, что знаки - или +, за которыми не следует цифра, она понимает как "правильное" представление нуля. Скорректируйте программу таким образом, чтобы в подобных случаях она возвращала прочитанный знак назад во ввод.
#include <stdio.h>
#include <ctype.h>
#define SIZE 20 /* макс. размер строки ввода */
int main(void)
{
int i, type, array[SIZE], getint(int *);
for (i = 0; i < SIZE && (type = getint(&array[i])) != EOF; i++)
printf("array[%d] = s\n", i, type ? array[i] : type,
type ? "" : "is not a number");
return 0;
}
int getch (void);
void ungetch (int);
/* getint: читает следующее целое из ввода в *pn */
int getint(int *pn)
{
int c, sign;
while (isspace(c = getch())); /* пропуск символов-разделителей */
if (!isdigit(c) && c != EOF && c != '+' && c != '-') {
return 0;
}
sign = (c =='-') ? -1 : 1;
if (c == '+' || c == '-')
if(!isdigit(c = getch())){
return 0;
}
for (*pn = 0; isdigit(c); c = getch())
*pn = 10 * *pn + (c - '0');
*pn *= sign;
if (c != EOF)
ungetch(c);
return c;
}
char buf[SIZE]; /* буфер для ungetch */
int bufp = 0; /* след. свободная позиция в буфере */
int getch(void) /* взять (возможно возвращенный) символ */
{
return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c) /* вернуть символ на ввод */
{
if (bufp >= SIZE)
printf("ungetch: слишком много символов\n");
else
buf[bufp++] = c;
}
Упражнение 5.2. Напишите функцию getfloat -- аналог getint для чисел с плавающей точкой. Какой тип будет иметь результирующее значение, задаваемое функцией getfloat?
#include <stdio.h>
#include <ctype.h>
#define SIZE 20 /* макс. размер строки ввода */
int main(void)
{
int i, type, getfloat(double *);
double array[SIZE];
for (i = 0; i < SIZE && (type = getfloat(&array[i])) != EOF; i++)
printf("array[%d] = s\n", i, type ? array[i] : type,
type ? "" : "is not a number");
return 0;
}
int getch (void);
void ungetch (int);
/* getfloat: читает следующее целое из ввода в *pn */
int getfloat(double *pn)
{
int c, sign;
float power;
while (isspace(c = getch())); /* пропуск символов-разделителей */
if (!isdigit(c) && c != EOF && c != '+' && c != '-') {
return 0;
}
sign = (c =='-') ? -1 : 1;
if (c == '+' || c == '-')
if(!isdigit(c = getch())){
return 0;
}
for (*pn = 0.0; isdigit(c); c = getch())
*pn = 10.0 * *pn + (c - '0');
if (c == '.')
c = getch();
for (power = 1.0; isdigit(c); c = getch()) {
*pn = 10.0 * *pn + (c - '0');
power *= 10.0;
}
*pn *= sign / power;
if (c != EOF)
ungetch(c);
return c;
}
Упражнение 5.3. Используя указатели, напишите функцию strcat, которую мы рассматривали в главе 2 (функция strcat(s,t) копирует строку t в конец строки s).
#include <stdio.h>
#include <string.h>
#define SIZE 15
void new_strcat(char *, char *);
int main()
{
char s[SIZE] = "Hello,";
char t[SIZE] = " world!";
int i;
for (i = 0; i < SIZE; i++)
printf("s+t[%d] = %c\n", i, s[i]);
return 0;
}
/* new_strcat: помещает t в конец s; s достаточно велика */
void new_strcat(char *ps, char *pt)
{
while (*ps++); /* находим конец s */
while ((*ps++ = *pt++)); /* копируем t */
}
Упражнение 5.4. Напишите функцию strend(s,t), которая выдает 1, если строка t расположена в конце строки s, и нуль в противном случае.
#include <stdio.h>
#include <string.h>
Упражнение 5.5. Напишите варианты библиотечных функций strncpy, strncat и strncmp, которые оперируют с первыми символами своих аргументов, число которых не превышает n. Например, strncpy(t,s,n) копирует не более n символов t в s. Полные описания этих функций содержатся в приложении B.
/* strncpy: копирует n символов из t в s */
void strncpy(char *s, char *t, int n)
{
int i = 0;
while (i++ < n && (*s++ = *t++));
}
/* strncat: помещает n символов из t в конец s */
void strncat(char *ps, char *pt, int n)
{
int i = 0;
while (*++ps); /* находим конец s */
while (i++ < n && (*ps++ = *pt++)); /* копируем t */
}
/* strncmp: выдает < 0 при s < t, 0 при s == t, > 0 при s > t */
int strncmp(char *s, char *t, int n)
{
int i = 0;
while (i++ < n && *s++ == *t++)
if (*(s-1) == '\0')
return 0;
Упражнение 5.6. Отберите подходящие программы из предыдущих глав и упражнений и перепишите их, используя вместо индексирования указатели. Подойдут, в частности, программы getline (главы 1 и 4), atoi, itoa и их варианты (главы 2, 3 и 4), reverse (глава 3), а также strindex и getop (глава 4).
getline() (у на-- getl()):
#include <stdio.h>
#define MAXLINE 50 /* максимальная длина строки ввода */
int getl(char *, int);
int main()
{
char line[MAXLINE]; /* текущая строка */
int len = 0;
while ((len = getl(line, MAXLINE)) > 0) {
printf("len = %d; line = %s\n", len, line);
}
return 0;
}
/* getl: читает строку в s, возвращает длину */
int getl(char *ps, int lim)
{
int c;
char *start = ps;
/* getl: читает строку в s, возвращает длину */
int getl(char *s, int lim)
{
int c;
char *ps = s;
while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
*s++ = c;
if (c == '\n')
*s++ = c;
*s = '\0';
return s-- - ps;
}
/* strrindex: вычисляет выдает позицию самого правого вхождения t в s
* или выдает -1, если t нет в s */
int strrindex (char *s, char *t)
{
int i, tmp = -1;
char *ps, *pt, *pstrbeg;
pstrbeg = s;
while (*s++) {
for (ps = s, pt = t; *pt && *ps++ == *pt++;);
i = &(*--ps) - pstrbeg;
if (!*pt && i > tmp)
tmp = i;
}
return tmp;
}
getop() (остальные функции, включая main(), есть в решениях упражнений 4.2--4.10.):
#include <ctype.h>
/* getop: получает следующий оператор или операнд */
int getop(char *s)
{
int c;
while ((*s = c = getch()) == ' ' || c == '\t');
*(s+1) = '\0';
if (!isdigit(c) && c != '.')
return c; /* не число */
if (isdigit(c)) /* накапливаем целую часть */
while (isdigit(*++s = c = getch()));
if (c =='.') /* накапливаем дробную часть */
while (isdigit(*++s = c = getch()));
*s = '\0';
if (c != EOF)
ungetch(c);
return NUMBER;
}
Упражнение 5.7. Напишите новую версию readlines, которая запоминала бы строки в массиве, определенном в main, а не запрашивала память посредством программы alloc. Насколько быстрее эта программа?
#include <stdio.h>
#include <string.h>
#define MAXLINES 5000 /* максимальное число строк */
#define ALLOCSIZE 10000 /* размер доступного пространства */
char *lineptr[MAXLINES]; /* указатели на строки */
int readlines(char *lineptr[], int nlines, char *linestore);
void writelines(char *lineptr[], int nlines);
/* сортировка строк */
int main()
{
char allocbuf[ALLOCSIZE]; /* массив для хранения строк */
int nlines; /* количество прочитанных строк */
if ((nlines = readlines(lineptr, MAXLINES, allocbuf)) >= 0) {
printf("nlines=%d\n", nlines);
writelines(lineptr, nlines);
return 0;
} else {
printf("ошибка: слишком много строк\n");
return 1;
}
}
#define MAXLEN 1000 /* максимальная длина строки */
int getl(char *, int);
/* readlines: чтение строк */
int readlines(char *lineptr[], int maxlines, char *linestore)
{
int len, nlines;
char *p, line[MAXLEN];
nlines = 0;
p = linestore + strlen(linestore);
while ((len = getl(line, MAXLEN)) > 0)
if (nlines >= maxlines || (len + strlen(linestore)) >= ALLOCSIZE)
return -1;
else {
line[len-1] = '\0'; /* убираем символ \n */
strcpy(p, line);
lineptr[nlines++] = p;
p += len;
}
return nlines;
}