Упражнения из книги Кернигана и Ритчи

[8Observer8]

Спасибо вам, что подняли тему! Я уже забыл про неё. Пора бы разобрать все задачи до конца. Прошу всех активно выкладывать здесь свои решения. Мы их будем сравнивать друг с другом и с решениями из других источников, таких как:

http://clc-wiki.net/wiki/K%26R2_solutions

http://programmersforum.ru/showthrea...480#post996480

Вот html-книга К&R на английском:
http://programmersforum.ru/showpost....&postcount=144

tungsten, хорошие у вас вопросы. Я постараюсь до вечера предложить свой вариант решения. Давайте все упражнения книги подробно разбирать в этой теме! Не стойте на месте, решайте остальные и выкладывайте здесь. Чем больше вариантов решения и вопросов, тем лучше!

[tungsten]

Задание 1.20
"Напишите программу detab, которая бы заменяла символы табуляции во входном потоке соответствующим количеством пробелов до следующей границы табуляции. Предположим, что табуляция имеет фиксированную ширину n столбцов. Следует ли сделать n переменной или символическим параметром?

Мое решение не идеальное.

#include <stdio.h>
#define MAXLINE 1000
#define n 8     /* число пробелов в табуляторе */

int spacediv(int k);

main()
{
    char c;
    int i,j,k,m;
    for (i = 0; i<MAXLINE && (c=getchar()) != EOF; ++i)
    if (c != '\t') {
        ++k;              /* считаем количество символов в строке */
        if (c == '\n')  { /* если новая строка - обнуляем */
            k=0;
        }
        putchar(c);
        }
    else {
        if (k>n) {
                m=spacediv(k);
        } else {
                m=n;
                }
        for (j = 0; j < m; ++j)
            printf("-");
            ++k;
        }
}

int spacediv(int k) /* аналог div но мы же о нем не знаем ;) */
{
    int i,j;
    for (i=1; i<k+1; ++i)
            if( (i*n > k) && ((i-1)*n <= k) ) {
                j = i * n - k;  /* определяем остаток до следующей позиции TAB. Здесь я столкнулся с проблемой - внутри предложения последний символ "съедается" следующей за TAB буквой. */
                return j;
            }
}

алгоритм сожрал исходник на СИ, в нем я кое где в конце строки поставил несколько ТАБов, в одной строке таб я поставил между круглой и фигурной скобкой, как видно на рисунке в одном месте последний символ "-" не отображается, в исходнике между двумя скобками на самом деле место в два пробела, в результате работы программы один из пробелов куда то исчез, тобишь пропечаталось одно "-".

[tungsten]

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

        for (j = 0; j < m; ++j)
            printf("-");
            ++k;

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

        for (j = 0; j < m; ++j) {
            printf("-");
            ++k;
        }

[tungsten]

Упражнение 1.21
Напишите программу entab, которая бы заменяла пустые строки, состоящие из одних пробелов, строками, содержащими минимальное количество табуляций и дополнительных пробелов, - так, чтобы заполнять то же пространство. Используйте те же параметры табуляции, что и в программе detab. Если для заполнения места до следующей границы табуляции требуется один пробел или один символ табуляции, то что следует предпочесть?

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

#include <stdio.h>
#define MAXLINE 1000
#define n 8

void spacefill(int nbspaces);   /* процедура заполнения пробелами */
int tabplace(int symbolnumber); /* является ли текущее место границей табуляции? */

main()
{
char c;
int i,j,nbspaces;

i=j=nbspaces=0;
for ( i = 0; (i < MAXLINE) && ((c=getchar()) != EOF); ++i) {
    if  (c != '\n') {
        ++j;                            /* пока не придет "перевод строки" считаем знакоместо. */
        if ( c == ' ' || c == '\t') {   /* Если текущий символ пробел, */
            ++nbspaces;                 /* прибавляем 1 к "соседние пробелы", */
            if (c=='\t' || (nbspaces > 1 && (tabplace(j)==1))) {
                                        /* если соседних пробелов больше 0 и текущее место является границуй табуляции - */

                printf("\t");           /* ставим ТАБ, */
                nbspaces=0;             /* и обнуляем счетчик соседних пробелов. */
            }
        } else {                        /* иначе (символ не является пробелом) */
            spacefill(nbspaces);        /* заполняем пространство пробелами (пробелов меньше 8) */
            nbspaces=0;                 /* обнуляем счетчик пробелов */
            putchar(c);                 /* и выводим текущий символ. */
        }
    } else {
        j=0;
        printf("\n");   /* пришел "перевод строки" */
    }
}
}

int tabplace(int j)
{
int r;
for (r=1; r<j; ++r) {   /* перебираем счетчик пока его состояние умноженное на число столбцов в табуляторе не станет больше текущего знакоместа */
    if (r*n==j) {         /* сравнивая его состояние умноженное на число столбцов в табуляторе с текущим знакоместом */
        return 0;          /* возвращаем положительный результат "это место является границей табуляции" */
    }
}
}

void spacefill(int t)
{
int s;
for (s=1; s<=t; ++s) {
        printf("+");    /* просто выводим "пробел" необходимое количество раз */
}
}

[8Observer8]

tungsten, у меня теперь будет больше свободного времени. Можно будет сосредоточится на написании и разборе алгоритмов. Если честно, то с алгоритмами у меня не очень. Ну на то и задачи, чтобы учиться.

Мелкие недочёты.

1. В функции не хватает return.

Вот какое предупреждение выдал Visual C++ 2010 Express Edition:

Warning 1 warning C4715: 'spacediv' : not all control paths return a value
c:\users\ivan\projects\k&r\tungsten \01_20_tungsten\main.c 40

Сообщение от tungsten

int spacediv(int k) /* аналог div но мы же о нем не знаем ;) */
{
    int i,j;
    for (i=1; i<k+1; ++i)
        if( (i*n > k) && ((i-1)*n <= k) ) {
            j = i * n - k; /*
                            * определяем остаток до следующей позиции TAB. Здесь я 
				            * столкнулся с проблемой - внутри предложения последний
                            * символ "съедается" следующей за TAB буквой.
                            */
                return j;
            }
}

2. Символьные константы нужно писать заглавными буквами.

Вместо:

#define n 8

Нужно:

#define N 8

3. Нужно расставлять пробелы после запятой и вокруг операций (сложение, вычитание и т.д.)

Вместо:

int i,j,k,m;

m=spacediv(k);

Нужно:

int i, j, k, m;

m = spacediv(k);

В следующем коде у вас, я считаю, нормально расставлены пробелы, читается хорошо:

if( (i*n > k) && ((i-1)*n <= k) ) {
    ...
}

4. Ставить фигурные скобки в циклах даже если в теле цикла только один оператор.

Чтобы избежать той ошибки, которую вы сами описали в сообщении №33.

5. Не забывайте инициализировать переменные.

В упражнении 1.20 вы забыли инициализировать переменную k. Если при запуске вести символ табуляции, то получим в VC++ 2010:



6. Функция spacediv() из упражнения 1.20 требует замены.

В вашей функции разобраться не смог. Предлагаю свой вариант:

int spacediv(int k, int n)
{
    int residue = k - (k/n) * n;

    return n - residue;
}

Формула для расчёта остатка от деления: ссылка

P.S. Надо будет потом реализовывать версии упражнений с проверкой корректности введённых данных. Это позже. Пока будем алгоритмы оттачивать.
P.S.S. Упражнение 1.21 ещё не смотрел. Решайте. Дальше будет интереснее. Я вас поддержу!

[tungsten]

Спасибо за разбор по косточкам. Занимаюсь я от случая к случаю, не всегда вспоминаю правила оформления. Без return фряха спокойно компилит командой 'cc', в Visual C++ наверняка более строгие правила, но все равно спасибо, попробую не забыть в будущем
С алгоритмами у меня неплохо в голове, а вот математику знаю на твердый НОЛЬ, поэтому остаток от деления выполнен через узкое место, тут я прошу прощения за свой индусский код
Вот попробовал пояснить, думаю поймете.

int spacediv(int k) 			/* аналог div но мы же о нем не знаем ;) */
{
    int i,j;
    for (i=1; i<k+1; ++i)		/* перебираем счетчик до значения k - "текущее положение символа" */
            if( (i*n > k) && ((i-1)*n <= k) ) {		/* если ТЕКУЩАЯ граница табуляции больше k и ПРЕДЫДУЩАЯ граница меньше k, тогда */ 
                j = i * n - k;  	/* определяем остаток до ТЕКУЩЕЙ границы табуляции */
                return j;
            }
}

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

Оффтоп: модераторам и админам портала - хотелось бы спойлеров в сообщениях

[tungsten]

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

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

Листинг не поместился в этом сообщении, кидаю следом.

[tungsten]

/*############################################################################
        K&R Less 1.22
        Упражнение выполнил:
        Юдин Павел aka Tungsten
        в два подхода:
        11 nov 2012 -   реакция на конец экрана/строки на табулятор
                        создал процедуры
        17 nov 2012 -   вспомнил о пробелах lastspace в реакциях на
                        конец экрана

  ############################################################################*/
#include <stdio.h>
#define SCRWDT 80       /* ширина экрана */
#define N 8             /* число пробелов в табуляторе */

char line[SCRWDT];
void despace(char line[], int lastspace);
void printline(char line[], int lastspace);
void clearline(char line[]);

main()
{
        int nbspaces, lstspc, i, k;
        char c;

        nbspaces = lstspc = k = 0;
        clearline(line);                                /* заполняем пробелами */

        for (i = 0; (c = getchar()) != EOF; ++i) {      /* получаем строку из потока */
            if (k < SCRWDT && c != '\n') {              /* проверяем длину результирующей строки К - строки без лишних пробелов и табов */
                if (c == ' ' || c == '\t') {            /* реакция на пробел и таб */
                    if (nbspaces < 1) {                 /* пробелов меньше одного? (первый пробел/таб?) */
                        ++nbspaces;                     /* "есть пробелы" */
                        lstspc = k;                     /* "последний пробел" - текущее значение К */
                        if (c == '\t') {                /* табулятор? */
                            k = k + N;                  /* перемещаем курсор строки К на число табуляции */
                        } else {                        /* иначе */
                            ++k;                        /* перемещаем курсор (пробелы уже есть в despace()) */
                        }
                    }
                } else {
                    line[k] = c;                        /* в противном случае */
                    nbspaces = 0;                       /* пробелов нет, находимся "в слове" */
                    ++k;                                /* перемещаем курсор */
                }
            } else if (k == SCRWDT || c == '\n') {      /* реакция на конец экрана или перевод строки  */
                if (c == '\n') {                        /* перевод строки */
                    ++nbspaces;                         /* не забываем про пробел в lstspc */
                    printline(line, k);                 /* печатаем строку до конца */
                    lstspc = k = 0;                     /* обнуляем счетчик К и координату последнего пробела */
                } else {
                    line[k] = c;                        /* не забываем про последний символ в этой строке */
                    printline(line, lstspc);            /* реакция на ширину экрана печататем до последнего пробела */
                    despace(line, lstspc);              /* убираем пробелы в строке до "последнего пробела" */
                    k = SCRWDT - lstspc;                /* вычисляем положение курсора за вычетом символов до "последнего пробела" */
                }
            }
        }
return 0;
}

void despace(char line[], int lstspc)
{
        int i;

        for (i = 0; i <= SCRWDT - lstspc; ++i) {        /* крутим цикл столько раз сколько осталось символов от последнего пробела до конца строки */
            line[i] = line[i+lstspc+1];                 /* заполняем строку символом следующим ЗА последним пробелом прибавляя текущее положение курсора */
            line[i+lstspc+1] = ' ';                     /* очищаем позицию (использовать clearline нельзя) */
        }
}

void printline(char line[], int lstspc)
{
        int i;

        for (i = 0; i <= lstspc; ++i) {                 /* крутим цикл до "последнего пробела" */
            printf("%c", line[i]);                      /* выводим посимволно */
            line[i] = ' ';                              /* выведенный символ удаляем (цикл крутится ДО последнего символа, использовать clearline нельзя) */
        }
        printf("\n");                                   /* добавляем недостающий перевод строки */
}

void clearline(char line[])
{
int i;

    for (i=0; i<=SCRWDT; ++i) {
        line[i]=' ';                                    /* просто цикл очистки */
    }
}

[tungsten]

return'ы ставить не стал, раздражает

warning: `return' with a value, in function returning void

[8Observer8]

Сообщение от tungsten

Без return фряха спокойно компилит командой 'cc'

Я так понимаю, что вы разрабатываете программы в среде FreeBSD из командной строки. Вы пользуетесь консольным отладчиком? То есть, вы умеете выполнять программы пошагам в косольном отладчике? Если да, то какой отладчик вы используете? Я никогда не пробовал работать с консольным отладчиком. Сейчас посмотрел в гугле нашёл такой http://www.opennet.ru/docs/RUS/gdb/gdb-prog.html.gz

Если будите разрабатывать в Linux, Mac Os или Windows, то рекомендую поставить среду Eclipse.

Вот сайт: http://www.eclipse.org. Скачать отсюда: http://www.eclipse.org/downloads/?osType=win32

Выбираем среду:



Инструкция установки:
- установка не требуется. Нужно распаковать скаченный архив

Eclipse расширяется расчёт плагинов.

Важные приимущества даже для начинающего разработчика:
- Встроенные системы управления версиями (EGit, CVS). Так же можно поставить SVN. Я выбрал EGit. По следующей ссылке инструкция, как начать использовать EGit c нуля: http://www.vogella.com/articles/EGit/article.html (если большие пробемы с английским - пользуйтесь Google переводчиком) С помощью EGit можно сохранять версии разрабатываемой программы. EGit сохраняет изменения в очень экономичном виде, в так называемом, хранилище (repository). Все изменения нужно комментировать. Изменения можно увидеть сравнив версии с помощью инструментов EGit. Всегда можно вернуться к старой версии и, к примеру, развить разработку этой программы по новой ветке. Можно создать много веток и переключаться между ними, развивая каждую. Можно разместить хранилище EGit на хостинге в интернете и разрабатывать ПО в команде. Например, вы загружаете (делаете import) на свой компьютер последнюю версию разрабатываемой программы (или не последнюю). Делаете в ней изменения. Комментируете их. И отгружаете (делаете export) исправленную версию обратно на хостинг. Причём все версии программы всегда доступны.
- Возможность поставить плагины для модульного тестирования (xUnit) по методологии экстремального программирования (TDD). Плагин для Java программ JUnit поставляется вместе с Eclipse. Для С программ - CUnit, для С++ программ - CppUnit и т.д. Вот список: http://c2.com/cgi/wiki?TestingFramework Я для С программ использую CuTest. Это framework для модульного тестирования программ на С. Он не является плагином для Eclipse. Чтобы использовать этот framework нужно подключить к своему проекту два файла: CuTest.h и CuTest.c (скачать с этого сайта: http://cutest.sourceforge.net/)

P.S. Продолжайте решать задачки. Я начну разбирать ваши решения, как только будет появляться время. Впереди ещё много интересных задач, продолжайте в том же духе!