Programms from Kernighan and Ritchie

[KBacHuK]

Упражнение 5.8. В функциях day_of_year и month_day нет никаких проверок правильности вводимых дат. Устраните этот недостаток.
#include <stdio.h>

int day_of_year(int, int, int);
int month_day(int, int, int *, int *);

int main()
{
int year = 2012, date = 60, month = 2, day = 29;
int m, d;

month_day(year, date, &m, &d);
printf("d -> month=d\n",
date, year, m, d);
printf("month=d -> d\n",
month, day, day_of_year(year, month, day), year);

year = 1917;
if (month_day(year, date, &m, &d) !=-1) {
printf("d -> month=d\n",
date, year, m, d);
}
else {
printf("error in month_day\n");
}
if (day_of_year(year, 2, 29) !=-1) {
printf("month=d -> d\n",
month, day, day_of_year(year, month, day), year);
}
else {
printf("error in day_of_year\n");
}


return 0;
}

static char daytab[2][13] = {
{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
};

/* day_of_year: определяет день года по месяцу и дню */
int day_of_year(int year, int month, int day)
{
int i, leap;

// Отсчет начнем с 1918 -- года перехода на грегорианский календарь
if (year < 1918 || month < 1 || month > 12 || day < 1)
return -1;

leap = (year % 4 == 0 && year % 100 !=0) || (year % 400 == 0);
for (i = 1; i < month; i++)
day += daytab[leap][i];
return day;
}

/* month_day: определяет месяц и день по дню года */
int month_day(int year, int yearday, int *pmonth, int *pday)
{
int i, leap;

if (year < 1918 || yearday < 1 || yearday > 366)
return -1;

leap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
for (i = 1; yearday > daytab[leap][i]; i++)
yearday -= daytab[leap][i];
*pmonth = i;
*pday = yearday;

return 0;
}

[KBacHuK]

Упражнение 5.9. Перепишите программы day_of_year и month_day, используя вместо индексов указатели.
/* day_of_year: определяет день года по месяцу и дню */
int day_of_year(int year, int month, int day)
{
int i, leap;
char *tmp;

// Отсчет начнем с 1918 -- года перехода на грегорианский календарь
if (year < 1918 || month < 1 || month > 12 || day < 1)
return -1;

leap = (year % 4 == 0 && year % 100 !=0) || (year % 400 == 0);
tmp = &daytab[leap][1];
for (i = 1; i < month; i++)
day += *tmp;
return day;
}

/* month_day: определяет месяц и день по дню года */
int month_day(int year, int yearday, int *pmonth, int *pday)
{
int i, leap;
char *tmp;

if (year < 1918 || yearday < 1 || yearday > 366)
return -1;

leap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
tmp = &daytab[leap][1];
for (i = 1; yearday > *tmp; i++)
yearday -= *tmp;
*pmonth = i;
*pday = yearday;

return 0;
}

[KBacHuK]

Упражнение 5.10. Напишите программу expr, интерпретирующую обратную польскую запись выражения, задаваемого командной строкой, в которой каждый оператор и операнд представлены отдельным аргументом.
#include <stdio.h>
#include <stdlib.h>

#define MAXOP 100 /* макс. размер операнда или оператора */
#define NUMBER '0' /* признак числа */

int getop (char *);
void push (int);
int pop (void);


/* калькулятор с обратной польской записью */
int main(int argc, char *argv[])
{
int c;
int op2;
int err=0;
char s[MAXOP];

while (--argc > 0 && (c = getop(*++argv))) {
switch (c) {
case NUMBER:
push (atoi(*argv));
break;
case '+':
push (pop() + pop());
break;
case '*':
push (pop() * pop());
break;
case '-':
op2 = pop();
push (pop() - op2);
break;
case '/':
op2 = pop();
if (op2 != 0)
push (pop() / op2);
else
printf("ошибка: деление на нуль\n");
break;
default:
err = 1;
printf("ошибка: неизвестная операция %s\n", s);
break;
}
}
if (!err)
printf("\t%d\n", pop());

return 0;
}


#define MAXVAL 10 /* максимальная глубина стека */

int sp = 0; /* следующая свободная позиция в стеке */
int val[MAXVAL]; /* стек */

/* push: положить значение i в стек */
void push(int i)
{
if (sp < MAXVAL){
val[sp++] = i;
}
else
printf("ошибка: стек полон, %d не помещается\n", i);
}

/* pop: взять с вершины стека и выдать в качестве результата */
int pop(void)
{
if (sp > 0) {
return val[--sp];
}
else {
printf ("ошибка: стек пуст\n");
return 0;
}
}

#include <ctype.h>
#include <string.h>

/* getop: получает следующий оператор или операнд */
int getop(char *s)
{
int c = strlen(s);
int p = 0;
char *tmp = s;

while (isdigit(*tmp++))
p++;
if (p != c){
return *s; /* не число */
}
else {
return NUMBER;
}
}

[KBacHuK]

Упражнение 5.12. Расширьте возможности entab и detab таким образом, чтобы при обращении вида
/* инициализация массива стопов табуляции tabstops */
void settabs(int argc, char *argv[], int tabstops[])
{
int i, c;
int tabstart = 0, tabsize = TABSIZE;

while (--argc > 0 && (**++argv == '-' || **argv == '+')) {
switch (**argv)
{
case '-':
if ((c = atoi(*argv + 1)) > 0)
tabstart = c;
break;
case '+':
if ((c = atoi(*argv + 1)) > 0)
tabsize = c;
break;
}
}

for (i=0; i < tabstart; i++)
tabstops[i] = 0;

for (i=tabstart; i < MAXLINE; i++)
tabstops[i] = ((i - tabstart) % tabsize == 0);
}

[KBacHuK]

Упражнение 5.13. Напишите программу tail, печатающую n последних введенных строк. По умолчанию значение n равно 10, но при желании n можно задать с помощью аргумента.

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

#define MAXLINES 50 /* максимальное число строк */
#define NDEF 10 /* колчичество возвращаемых по умолчанию строк */

char *lineptr[MAXLINES]; /* указатели на строки */

int setnumlines(int, char *[]);
int readlines(char *lineptr[], int nlines);
void tail(char *lineptr[], int nlines, int n);


int main(int argc, char *argv[])
{
int nlines; /* количество прочитанных строк */
int n; /* количество строк, которые нужно распечатать */

n = setnumlines(argc, argv);

if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
tail(lineptr, nlines, n);
return 0;
} else {
printf("ошибка: слишком много строк\n");
return 1;
}
}

/* setnumlines: инициализация количества выводимых строк */
int setnumlines(int argc, char *argv[])
{
int n;

while (--argc > 0 && **++argv == '-') {
if ((n = atoi(*argv + 1)) > 0)
return n;
else
return 0;
}
return NDEF;
}

/* tail: печать n строк с конца */
void tail(char *lineptr[], int nlines, int n)
{
int i;

if (n > nlines)
n = nlines;
for (i=1; i <= n; i++)
printf("%s\n", lineptr[nlines-i]);
}

[KBacHuK]

Упражнение 5.14. Модифицируйте программу сортировки, чтобы она реагировала на параметр -r, указывающий, что объекты нужно сортировать в обратном порядке, т. е. в порядке убывания. Обеспечьте, чтобы -r работал и вместе с -n.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXLINES 5000 /* максимальное число строк */

char *lineptr[MAXLINES]; /* указатели на строки текста */

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines, int reverse);
void quicksort(void *lineptr[], int left, int right,
int (*comp)(void *, void *));
int numcmp(char *, char *);

/* сортировка строк */
int main(int argc, char *argv[])
{
int nlines; /* количество прочитанных строк */
int numeric = 0; /* 1, если сорт. по числ. знач. */
int reverse = 0; /* 1, если выводить по убыванию */
int c;

while (--argc > 0 && (*++argv)[0] == '-')
while ((c = *++argv[0]))
switch (c) {
case 'n':
numeric = 1;
break;
case 'r':
reverse = 1;
break;
default:
printf("sort: неверный параметр %c\n", c);
argc = 0;
break;
}

if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
quicksort((void **) lineptr, 0, nlines-1,
(int (*)(void*,void*))(numeric ? numcmp : strcmp));
printf("SORTED:\n");
writelines(lineptr, nlines, reverse);
return 0;
} else {
printf("Bведено слишком много строк\n");
return 1;
}
}

/* writelines: печать строк */
void writelines(char *lineptr[], int nlines, int reverse)
{
int i;

if (reverse)
for (i=1; i <= nlines; i++)
printf("%s\n", lineptr[nlines-i]);
else
while (nlines-- > 0)
printf("%s\n", *lineptr++);
}

[KBacHuK]

Упражнение 5.15. Введите в программу необязательный параметр -f, задание которого делало бы неразличимыми символы нижнего и верхнего регистров (например, a и A должны оказаться при сравнении равными).
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#define MAXLINES 5000 /* максимальное число строк */

char *lineptr[MAXLINES]; /* указатели на строки текста */

int readlines(char *lineptr[], int nlines);
void setlower(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines, int reverse);
void quicksort(void *lineptr[], int left, int right,
int (*comp)(void *, void *));
int numcmp(char *, char *);

/* сортировка строк */
int main(int argc, char *argv[])
{
int nlines; /* количество прочитанных строк */
int numeric = 0; /* 1, если сорт. по числ. знач. */
int reverse = 0; /* 1, если выводить по убыванию */
int case_insensetive = 0; /* 1, если сорт. нечувств. к регистру */
int c;

while (--argc > 0 && (*++argv)[0] == '-')
while ((c = *++argv[0]))
switch (c) {
case 'n':
numeric = 1;
break;
case 'r':
reverse = 1;
break;
case 'f':
case_insensetive = 1;
break;
default:
printf("sort: неверный параметр %c\n", c);
argc = 0;
break;
}

if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
if (case_insensetive)
setlower(lineptr, nlines);
quicksort((void **) lineptr, 0, nlines-1,
(int (*)(void*,void*))(numeric ? numcmp : strcmp));
printf("SORTED:\n");
writelines(lineptr, nlines, reverse);
return 0;
} else {
printf("Bведено слишком много строк\n");
return 1;
}
}

/* setlower: преобразование символов к нижнему регистру */
void setlower(char *lineptr[], int nlines)
{
int i, j;

for (i=0; i < nlines; i++) {
j = 0;
while(lineptr[i][j]) {
lineptr[i][j] = tolower(lineptr[i][j]);
j++;
}
}
}

[KBacHuK]

Упражнение 5.16. Предусмотрите в программе необязательный параметр -d, который заставит программу при сравнении учитывать только буквы, цифры и пробелы. Организуйте программу таким образом, чтобы этот параметр мог работать вместе с параметром -f.
Теперь при сравнении нам предлагается не замечать некоторых символов, например, пунктуации. Переработаем chcmp() из упражнения 5.15 в таком ключе:
Пропустим нежелательные символы в начале строки
Сравним строки, пропуская нежелательные символы
Изменения:
- строки
int directory = 0; /* 1, если сорт. игнорирует пунктуацию */
int case_insensetive = 0; /* 1, если сорт. нечувств. к регистру */
вынесены из основной функции, чтобы эти переменные были видимы из chcmp.
- в оператор switch основной функции добавлен блок:
case 'd':
directory = 1;
break;
- переработана функция chcmp(). Теперь она обрабатывает все лексикографические сравнения, а strcmp() не используется:
/* chcmp: сравнивает s1 и s2, игнорируя разницу в регистре и/или
* символы пунктуации */
int chcmp(char *s1, char *s2)
{
if(directory) {
while(!isdigit(*s1) && !isalpha(*s1) && !isspace(*s1) && *s1)
++s1;
while(!isdigit(*s2) && !isalpha(*s2) && !isspace(*s2) && *s2)
++s2;
}
while(case_insensetive ? (tolower(*s1) == tolower(*s2)) : (*s1 == *s2)) {
if(*s1 == '\0')
return 0;
++s1;
++s2;
if(directory) {
while(!isdigit(*s1) && !isalpha(*s1) && !isspace(*s1) && *s1)
++s1;
while(!isdigit(*s2) && !isalpha(*s2) && !isspace(*s2) && *s2)
++s2;
}
}
return case_insensetive ? (tolower(*s1) - tolower(*s2)) : (*s1 - *s2);
}
В этом случае игнорируются все символы, кроме букв, цифр и пробелов. Если не игнорировать также непечатаемые символы, код будет короче, т. к. можно использовать не три функции is..., а одну -- ispunct().

[KBacHuK]

Упражнение 5.17. Реализуйте в программе возможность работы с полями: возможность сортировки по полям внутри строк. Для каждого поля предусмотрите свой набор параметров. Предметный указатель этой книги (Имеется в виду оригинал книги на английским языке. – Примеч. пер.) упорядочивался с параметрами: -df для терминов и -n для номеров страниц.
main()
include <stdio.h>
include <string.h>
include <ctype.h>
include <stdlib.h>
define MAXLINES 5000 /* максимальное число строк */
char *lineptr[MAXLINES]; /* указатели на строки текста */
int readlines(char *lineptr[], int nlines); void writelines(char *lineptr[], int nlines, int reverse); void quicksort(void *lineptr[], int left, int right,
int (*comp)(void *, void *));
int numcmp(char *, char *); int chcmp(char *, char *);
int directory = 0; /* 1, если сорт. игнорирует пунктуацию */ int case_insensitive = 0; /* 1, если сорт. нечувств. к регистру */ int fs = 0, ff = 0; /* начальная и конечная позиции поля */
/* сортировка строк */
int main(int argc, char *argv[])
{
int nlines; /* количество прочитанных строк */
int numeric = 0; /* 1, если сорт. по числ. знач. */
int reverse = 0; /* 1, если выводить по убыванию */
int field = 0; /* 1, если определена начальная позиция поля */
int c;

while (--argc > 0 && ((c = (*++argv)[0]) == '-' || c == '+'))
if (c == '-')
while ((c = *++argv[0]))
switch (c) {
case 'n':
numeric = 1;
break;
case 'r':
reverse = 1;
break;
case 'f':
case_insensitive = 1;
break;
case 'd':
directory = 1;
break;
default:
printf("sort: неверный параметр %c\n", c);
argc = 0;
break;
}
else if (c == '+') {
if (!fs && !field) {
fs = atoi(++argv[0]);
field = 1;
if (fs < 0) {
printf("sort: значение позиции должно быть неотрицательным\n");
fs = 0;
}
}
else if (!ff) {
ff = atoi(++argv[0]);
if (ff < fs) {
printf("sort: конечная позиция поля должна быть больше начальной\n");
ff = 0;
}
}
}
else
printf("вызов: sort -nrfd +field_start +field_finish\n");

if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
if (numeric)
quicksort((void **) lineptr, 0, nlines-1,
(int (*)(void *, void *)) numcmp);
else
quicksort((void **) lineptr, 0, nlines-1,
(int (*)(void *, void *)) chcmp);
printf("SORTED:\n");
writelines(lineptr, nlines, reverse);
return 0;
} else {
printf("Bведено слишком много строк\n");
return 1;
}
}

[KBacHuK]

Упражнение 5.18. Видоизмените dcl таким образом, чтобы она обрабатывала ошибки во входной информации.
Какие именно ошибки? Дадим слово авторам: "Лишние пробелы для нее опасны. Она не предпринимает никаких мер по выходу из ошибочной ситуации, и поэтому неправильные описания также ей противопоказаны".
Действительно, если поставить пробел внутри поля аргументов функции, получим ошибку исправить которую без перезапуска невозможно:

Заметьте, что вторая попытка синтаксически корректна, но также воспринимается как ошибка.
Необходимо научиться убирать лишние пробелы:
int gettoken(void) /* возвращает следующую лексему */
{
int c;
void ungetch(int);
char *p = token;

if ((c = getter()) == '(') {
if ((c = getter()) == ')') {
strcpy(token, "()");
return tokentype = PARENS;
} else {
ungetch(c);
return tokentype = '(';
}
} else if (c == '['){
for (*p++ = c; (*p++ = getter()) != ']'; );
*p = '\0';
return tokentype = BRACKETS;
} else if (isalpha(c)) {
for (*p++ = c; isalnum(c = getch()); )
*p++ = c;
*p = '\0';
ungetch(c);
return tokentype = NAME;
} else
return tokentype = c;
}

int getter(void)
{
int c;
while ((c = getch()) == ' ' || c == '\t');
return c;
}
getter() -- широко используемая в книге операция предварительного удаления пробелов и табуляций. Вынесена в функцию, потому что необходимо применить несколько раз.
Теперь -- борьба с повторением ошибок. В такой простой программе логично выглядит такой подход: сообщить пользователю об ошибке и выйти из программы, давая ему шанс ее исправить.
Поэтому исходную функцию dirdcl() я дополнил сообщения об ошибках вызовом функций exit() из stdlib.h со статусом -1:
/* dirdcl: разбор собственно объявителя */
void dirdcl(void)
{
int type;

if (tokentype == '(') {
dcl();
if (tokentype != ')') {
printf("oшибкa: пропущена )\n");
exit(-1);
}
} else if (tokentype == NAME) /* имя переменной */
strcpy(name, token);
else {
printf("ошибка: должно быть name или (dcl)\n");
exit(-1);
}

while((type = gettoken()) == PARENS || type == BRACKETS)
if (type == PARENS)
strcat(out, "функц. возвр.");
else {
strcat(out, " массив ");
strcat(out, token);
strcat(out, " из ");
}
}

[KBacHuK]

Упражнение 5.19. Модифицируйте undcl так, чтобы она не генерировала лишних скобок.
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAXTOKEN 100

enum {NAME, PARENS, BRACKETS};

int gettoken(void);
int nexttoken(void);
int getter(void);
int tokentype; /* тип последней лексемы */
char token[MAXTOKEN]; /* текст последней лексемы */
char name[MAXTOKEN]; /* имя */
char datatype[MAXTOKEN]; /* тип = char, int и т.д. */
char out[1000]; /* выдаваемый текст */

/* undcl: преобразует словесное описание в объявление */
int main(void)
{
int type;
char temp[MAXTOKEN];

while (gettoken() != EOF) {
strcpy(out, token);
while ((type = gettoken()) != '\n')
if (type == PARENS || type == BRACKETS)
strcat(out, token);
else if (type == '*' ) {
if ((type = nexttoken()) == PARENS || type == BRACKETS)
sprintf(temp, "(*%s)", out);
else
sprintf(temp, "*%s", out);
strcpy(out, temp);
} else if (type == NAME) {
sprintf(temp, "s", token, out);
strcpy(out, temp);
} else
printf("неверный элемент %s во фразе\n", token);
printf("%s\n", out);
}
return 0;
}

enum {NO, YES};
int prevtoken = NO;

int nexttoken(void)
{
int type;
type = gettoken();
prevtoken = YES;
return type;
}

int getch(void);

int gettoken(void) /* возвращает следующую лексему */
{
int c;
void ungetch(int);
char *p = token;

if (prevtoken == YES) {
prevtoken = NO;
return tokentype;
}

if ((c = getter()) == '(') {
if ((c = getter()) == ')') {
strcpy(token, "()");
return tokentype = PARENS;
} else {
ungetch(c);
return tokentype = '(';
}
} else if (c == '['){
for (*p++ = c; (*p++ = getter()) != ']'; );
*p = '\0';
return tokentype = BRACKETS;
} else if (isalpha(c)) {
for (*p++ = c; isalnum(c = getch()); )
*p++ = c;
*p = '\0';
ungetch(c);
return tokentype = NAME;
} else
return tokentype = c;
}

[KBacHuK]

Упражнение 5.20. Расширьте возможности dcl, чтобы dcl обрабатывала объявления с типами аргументов функции, квалификаторами вроде const и т. п.
void params_dcl(void)
{
void type_dcl(void);

do {
type_dcl();
} while (tokentype == ',');
if (tokentype != ')') {
printf("oшибкa: пропущена ) в объявлении параметров\n");
prevtoken = YES;
}
}

void type_dcl(void)
{
char t[MAXTOKEN];
int istypename(char []);
int istypequal(char []);

t[0] = '\0';
gettoken();

do {
if (tokentype != NAME) {
prevtoken = YES;
dcl();
}
else if (istypename(token)) {
strcat(t, token);
gettoken();
}
else if (istypequal(token)) {
strcat(t, token);
gettoken();
}
else {
printf("ошибка: неизвестный параметр %s\n", token);
prevtoken = YES;
}
} while (tokentype == ',' && tokentype == ')');
strcat(out, t);
if (tokentype == ',')
strcat(out, ", ");
}

int istypename(char name[])
{
int i=0;
char *types[] = {"char", "int", "float"};
int ntypes = 3;

while (ntypes--)
if (strcmp(name, types[i++]) == 0)
return 1;

return 0;
}

int istypequal(char qual[])
{
int i=0;
char *quals[] = {"const", "volatile"};
int nquals = 2;

while (nquals--)
if (strcmp(qual, quals[i++]) == 0)
return 1;

return 0;
}

[SomeStrangeGuy]

Упражнение 6.1. Haшa вepcия getword не обрабатывает должным образом знак подчеркивания, строковые константы, комментарии и управляющие строки препроцессора. Напишите более совершенный вариант программы.

struct key {
char *word;
int count;
} keytab[] = {
{"_asm", 0},
{"as_m", 0},
{"asm", 0},
{"break", 0},
{"case", 0},
{"char", 0}
};
Фигурные скобки вокруг элементов отдельных структур пришлось поставить, т. к. в отличие от того, что было у K&R, мой gcc ругается из-за отсутствия этих скобок.
Переделанная getword():
/* getword: принимает следующее слово или символ из ввода */
int getword (char *word, int lim)
{
int c, getch(void);
void ungetch(int);
char *w = word;

while (isspace(c = getch()));
if (c != EOF)
*w++ = c;
if (isalpha(c) || c == '_')
for ( ; --lim > 0; w++)
if (!isalnum(*w = getch()) && *w != '_') {
ungetch(*w);
break;
}
*w = '\0';
return c;
}
Даже стала короче.
Про директивы препроцессора я не понял задания. getword(), в ее нынешнем виде, игнорирует собственно директивы, но извлекает ключевые слова, стоящие за ними. Сами же директивы не являются ключевыми словами. Может я должен, вместо препроцессора, выполнить подстановку из директив? Короче говоря, оставил как есть.
Пропуск ключевых слов, находящихся внутри строковых констант осуществляется добавлением условия
else if (c == '"') {
while ((t = getch()) != c && t != EOF);
}
Заметим, что это решение не застраховано от ложных срабатываний на экранированных двойных кавычках.
Удаление многострочных комментариев осуществляется условием:
else if (c == '/') {
if ((t = getch()) == '*') {
while ((t = getch()) != EOF )
if (t == '*') {
if ((t = getch()) == '/')
break;
else
ungetch(t);
}
}
else
ungetch(t);
}
Однострочные комментарии мы обрабатывать не будем, но идея здесь та же, только начало комментария -- "//", а конец -- "\n".
Сходная задача по "уборке" комментариев решалась также в упражнении 1.24.
getword() полностью:
int getword (char *word, int lim)
{
int c, t, getch(void);
void ungetch(int);
char *w = word;

while (isspace(c = getch()));
if (c != EOF)
*w++ = c;
if (isalpha(c) || c == '_') {
for ( ; --lim > 0; w++)
if (!isalnum(*w = getch()) && *w != '_') {
ungetch(*w);
break;
}
}
else if (c == '"') {
while ((t = getch()) != c && t != EOF);
}
else if (c == '/') {
if ((t = getch()) == '*') {
while ((t = getch()) != EOF )
if (t == '*') {
if ((t = getch()) == '/')
break;
else
ungetch(t);
}
}
else
ungetch(t);
}
*w = '\0';
return c;
}

[SomeStrangeGuy]

Упражнение 6.2. Напишите программу, которая читает текст Си-программы и печатает в алфавитном порядке все группы имен переменных, в которых совпадают первые 6 символов, но последующие в чем-то различаются. Не обрабатывайте внутренности закавыченных строк и комментариев. Число 6 сделайте параметром, задаваемым в командной строке.

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

#define MAXWORD 100

struct tnode { /* узел дерева */
char *word; /* указатель на текст */
int count; /* число вхождений */
struct tnode *left; /* левый дочерний узел */
struct tnode *right; /* правый дочерний узел */
};

struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);

int num;

int main(int argc, char *argv[])
{
struct tnode *root;
char word[MAXWORD];

if (argc == 2)
num = atoi(argv[1]);
else if (argc < 2)
num = 3; /* Значение длины сравнения по умолчанию */
else {
printf("usage: tree <number>\n");
exit(-1);
}

root = NULL;
while (getword (word, MAXWORD) != EOF)
if (isalpha(word[0]))
root = addtree(root, word);
treeprint(root);
return 0;
}

struct tnode *talloc(void);
char *mystrdup(char *);

/* addtree: добавляет узел со словом w в р или ниже него */
struct tnode *addtree(struct tnode *p, char *w)
{
int cond;

if (p == NULL) { /* слово встречается впервые */
p = talloc(); /* создается новый узел */
p->word = strdup(w);
p->count = 1;
p->left = p->right = NULL;
} else if ((cond = strncmp(w, p->word, num)) == 0)
p->count++; /* это слово уже встречалось */
else if (cond < 0) /* меньше корня левого поддерева */
p->left = addtree(p->left, w);
else /* больше корня правого поддерева */
p->right = addtree(p->right, w);
return p;
}
addtree() подверглась, как видно, минимальной переработке. strdup() переименована в mystrdup(), чтобы не конфликтовать с библиотечной функцией.
Вот тестовая программа:
#include <stdio.h>

int main(void)
{
char test1[] = "This is a test";
int test = 2;
/* test for ex. 6.2 */
printf("d\n", test1, test);
return 0;
}

[SomeStrangeGuy]

Упражнение 6.3. Напишите программу печати таблицы "перекрестных ссылок", которая будет печатать все слова документа и указывать для каждого из них номера строк, где оно встретилось. Программа должна игнорировать "шумовые" слова, такие как "и", "или" и пр.

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

#define MAXWORD 100
#define MAXLINK 5

struct tnode { /* узел дерева */
char *word; /* указатель на текст */
int nline[MAXLINK]; /* массив номеров строк */
int count; /* индекс в nline[] */
struct tnode *left; /* левый дочерний узел */
struct tnode *right; /* правый дочерний узел */
};

struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);

int num; /* Максимальная длина "шумового" слова */
int lnum = 0; /* Инициализация счетчика строк */

int main(int argc, char *argv[])
{
struct tnode *root;
char word[MAXWORD];

if (argc == 2)
num = atoi(argv[1]);
else if (argc < 2)
num = 2;
else {
printf("usage: linktree <number>\n");
exit(-1);
}

root = NULL;
while (getword (word, MAXWORD) != EOF)
if (isalpha(word[0]) && strlen(word) > num)
root = addtree(root, word);
treeprint(root);
return 0;
}

struct tnode *talloc(void);
char *mystrdup(char *);

/* addtree: добавляет узел со словом w в р или ниже него */
struct tnode *addtree(struct tnode *p, char *w)
{
int cond;

if (p == NULL) { /* слово встречается впервые */
p = talloc(); /* создается новый узел */
p->word = strdup(w);
p->nline[p->count] = lnum;
p->count = 1;
p->left = p->right = NULL;
} else if ((cond = strcmp(w, p->word)) == 0) {
p->nline[p->count++] = lnum; /* это слово уже встречалось */
}
else if (cond < 0) /* меньше корня левого поддерева */
p->left = addtree(p->left, w);
else /* больше корня правого поддерева */
p->right = addtree(p->right, w);
return p;
}

/* treeprint: упорядоченная печать дерева р */
void treeprint(struct tnode *p)
{
int i;

if (p != NULL) {
treeprint (p->left);
printf("\n%s ", p->word);
for (i = 0; i < MAXLINK; i++)
printf("%2d ",p->nline[i]);
treeprint(p->right);
}
}

/* getword: принимает следующее слово или символ из ввода */
int getword (char *word, int lim)
{
int c, t, getch(void);
void ungetch(int);
char *w = word;

while (isspace(c = getch()) && c != '\n');
if (c != EOF)
*w++ = c;
if (isalpha(c) || c == '_') {
for ( ; --lim > 0; w++) {
if (!isalnum(*w = getch()) && *w != '_') {
ungetch(*w);
break;
}
else if (*w == '\n') {
lnum++;
ungetch(*w);
break;
}
}
}
else if (c == '"') {
while ((t = getch()) != c && t != EOF);
}
else if (c == '/') {
if ((t = getch()) == '*') {
while ((t = getch()) != EOF )
if (t == '*') {
if ((t = getch()) == '/')
break;
else
ungetch(t);
}
}
else
ungetch(t);
}
else if (c == '\n')
lnum++;
*w = '\0';
return c;
}

[SomeStrangeGuy]

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

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

#define MAXWORD 100
#define MAXWORDS 20

struct tnode { /* узел дерева */
char *word; /* указатель на текст */
int count; /* число вхождений */
struct tnode *left; /* левый дочерний узел */
struct tnode *right; /* правый дочерний узел */
};

struct tnode *addtree(struct tnode *, char *);
void tree2array(struct tnode *);
void bubble_sort(struct tnode *[], int);
void arrayprint(struct tnode *[]);
int getword(char *, int);

struct tnode *words[MAXWORDS];
int nword = 0;

int main(void)
{
struct tnode *root;
char word[MAXWORD];

root = NULL;
while (getword (word, MAXWORD) != EOF)
if (isalpha(word[0]))
root = addtree(root, word);
tree2array(root);
printf("number of words = %d\n\n", nword);
bubble_sort(words, nword);
arrayprint(words);
return 0;
}

/* tree2array: сохранение упорядоченного по алфавиту дерева в массиве */
void tree2array(struct tnode *p)
{
if (p != NULL) {
tree2array (p->left);
if (nword < MAXWORDS)
words[nword++] = p;
tree2array(p->right);
}
}

void swap(struct tnode *[], int, int);

/* bubble_sort: сортировка *w[] пузырьком */
void bubble_sort(struct tnode *w[], int n) {
int j, t = 1;

while (n-- && t)
for (j = t = 0; j < n; j++) {
if (w[j]->count >= w[j+1]->count) continue;
swap(w, j, j+1);
t = 1;
}
}

/* swap: поменять местами w[i] и w[j] */
void swap(struct tnode *w[], int i, int j)
{
struct tnode *temp;

temp = w[i];
w[i] = w[j];
w[j] = temp;
}

/* arrayprint: печать массива структур */
void arrayprint(struct tnode *w[])
{
int i;

for (i = 0; i < nword; i++)
printf("%4d %s\n", w[i]->count, w[i]->word);
}

[SomeStrangeGuy]

Упражнение 6.6. Реализуйте простую версию #define-npoцeccopa (без аргументов), которая использовала бы программы этого параграфа и годилась бы для Си-программ. Вам могут помочь программы getch и ungetch.

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

#define MAXWORD 100
#define HASHSIZE 101

struct nlist { /* элемент таблицы */
struct nlist *next; /* указатель на следующий элемент */
char *name; /* определенное имя */
char *defn; /* замещающий текст */
};

static struct nlist *hashtab[HASHSIZE]; /* таблица указателей */

struct nlist *install(char *, char *);
int getword(char *, int);


int main(void)
{
char word[MAXWORD];

while (getword (word, MAXWORD) != EOF)
printf("[%s]", word);

return 0;
}

struct nlist *lookup(char *);
char *mystrdup(char *);
unsigned hash(char *);

/* install: заносит имя и текст (name, defn) в таблицу */
struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;

if ((np = lookup(name)) == NULL) { /* не найден */
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else /* уже имеется */
free((void *) np->defn); /* освобождаем прежний defn */
if ((np->defn = mystrdup(defn)) == NULL)
return NULL;
return np;
}

/* lookup: ищет s */
struct nlist *lookup(char *s)
{
struct nlist *np;

for (np = hashtab[hash(s)]; np != NULL; np = np->next)
if (strcmp(s, np->name) == 0)
return np; /* нашли */
return NULL; /* не нашли */
}

/* hash: получает хэш-код для строки s */
unsigned hash(char *s)
{
unsigned hashval;

for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
В коде присутствуют install(), lookup() и hash() из п. 6.6, но пока не используются. Здесь не зватает getword() и пары getch/ungetch -- их можно взять из прошлых упражнений этой главы.
Вводим тестовую программу:
#include <stdio.h>

#define TWO 2

int main(void)
{
char test1[] = "This is a test";
int test = TWO;
/* test for ex. 6.2 */
printf("d\n", test1, test);
#undef TWO

return 0;
}

Добавим обработку undef в основную программу:
int main(void)
{
char word[MAXWORD], tword[MAXWORD];
struct nlist *np;

while (getword (word, MAXWORD) != EOF) {
if (strcmp(word, "#") == 0) {
printf("<directive?>");
printf("[%s]", word);
getword (word, MAXWORD);
if (strcmp(word, "define") == 0) {
printf("<define>");
if (isupper(getword (word, MAXWORD))) {
printf("<NAME>");
strcpy(tword, word);
if (isalnum(getword (word, MAXWORD))) {
printf("<<defn>>");
np = install(tword, word);
}
else
printf("error: incorrect definition.\n");
}
else {
printf("error: must be only UPPER LETTERS in directive.\n");
}
}
else if (strcmp(word, "undef") == 0) {
printf("<undef>");
if (isupper(getword (word, MAXWORD))) {
printf("<NAME>");
undef(word);
}
}
else {
printf("<not>");
}
}
else if ((np = lookup(word)) != NULL) {
printf("<in table>");
strcpy(word, np->defn);
}
printf("[%s]", word);
}
printf("\n");
tableprint();

return 0;
}
Функция undef() (т. е. решение упражнения 6.5) имеет вид:
/* undef: удаление записи из хэш-таблицы hashtab */
void undef(char *s)
{
int i;
struct nlist *np, *prev;

prev = NULL;
i = hash(s);
for (np = hashtab[i]; np != NULL; np = np->next) {
if (strcmp(s, np->name) == 0)
break;
prev = np;
}
if (np != NULL) {
if (prev == NULL)
hashtab[i] = np->next;
else
prev->next = np->next;
free((void *) np->name);
free((void *) np->defn);
free((void *) np);
}
}

[KBacHuK]

Упражнение 7.1. Напишите программу, осуществляющую перевод ввода с верхнего регистра на нижний или с нижнего на верхний в зависимости от имени, по которому она вызывается и текст которого находится в arg[0].
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

/* upper/lower: переводит ввод в верхний/нижний регистр */
int main(int argc, char *argv[])
{
int c;

if (argc != 1) {
printf("usage: /.{upper|lower}\n");
exit(1);
}

printf("%s\n", argv[0]);

if (strcmp(argv[0], "./upper") == 0)
while ((c = getchar()) != EOF)
putchar(toupper(c));
else
while ((c = getchar()) != EOF)
putchar(tolower(c));

return 0;
}

[KBacHuK]

Упражнение 7.2. Напишите программу, которая будет печатать разумным способом любой ввод. Как минимум она должна уметь печатать неграфические символы в восьмеричном или шестнадцатеричном виде (в форме, принятой на вашей машине), обрывая длинные текстовые строки.
#include <stdio.h>
#include <ctype.h>


#define MAXLEN 30

/* печатает неграфические символы ввода как 16-ричные числа,
* разрывает длинные строки */
int main(void)
{
int n = 0;
char c;

while ((c = getchar()) != EOF) {
if (c == '\n') {
n = 0;
putchar(c);
}
else if (!isprint(c) && c != '\n') {
if (n > MAXLEN) {
putchar('\n');
n = 0;
}
printf("\\%x", c);
n++;
}
else {
if (n > MAXLEN) {
putchar('\n');
n = 0;
}
putchar(c);
n++;
}
}

return 0;
}

[KBacHuK]

Упражнение 7.3. Дополните minprintf другими возможностями printf.
#include <stdio.h>
#include <stdarg.h>


void minprintf(char *, ...);

int main(void)
{
int i = 12;
double f = 12.0;
minprintf("o, f, e, c \n",
i, i, i, f, f, f, "string", 'c');
return 0;
}

/* minprintf: минимальный printf с переменным числом аргументов */
void minprintf(char *fmt, ...)
{
va_list ap; /* указатель на очередной безымянный аргумент */
char *p, *sval;
int ival;
double dval;
unsigned int uval;

va_start(ap, fmt); /* устанавливает ap на 1-й безымянный аргумент */
for (p=fmt; *p; p++) {
if (*p !='%') {
putchar(*p);
continue;
}
switch (*++p) {
case 'd': case 'i':
ival = va_arg(ap, int);
printf ("%d", ival);
break;
case 'o':
uval = va_arg(ap, unsigned int);
printf ("%o", uval);
break;
case 'x':
uval = va_arg(ap, unsigned int);
printf ("%x", uval);
break;
case 'f':
dval = va_arg(ap, double);
printf("%f", dval);
break;
case 'g':
dval = va_arg(ap, double);
printf("%g", dval);
break;
case 'e':
dval = va_arg(ap, double);
printf("%e", dval);
break;
case 'c':
ival = va_arg(ap, int);
putchar(ival);
break;
case 's':
for (sval = va_arg(ap, char *); *sval; sval++)
putchar(*sval);
break;
default:
putchar(*p);
break;
}
}
va_end(ap); /* очистка, когда все сделано */
}