Отладка разделяемой библиотеки в детективном жанре

Одна из проблем при разрабоке -- сделать так, чтобы программа собиралась и работала не только на машине у разработчика, но и на машине конечного пользователя. А ещё лучше -- чтобы всё работало без присутствия разработчика рядом.

Собственно, о чём речь

При работе над Guile-SSH столкнулся с интересной проблемой -- на Gentoo GNU/Linux (моей основной системе) библиотека работает без нареканий, а на Debian GNU/Linux 6.0.7 тестовая программа завершается с ошибкой.

Проблема была обнаружена уже на Linux Install Fest'е, перед презентацией проекта, где я должен был показать пример использования библиотеки. И вот ведь незадача -- оказалось, что эту проблему не так-то просто решить. Я потратил кучу времени, пытаясь понять -- из-за чего, собственно, происходит аварйный останов тестовой программы.

Тестовая программа -- sssh, или Scheme Secure Shell -- работает, как упрощенный вариант ssh в неинтерактивном режиме. То есть, выполняет команду на хосте и возвращает результат. Авторизация на хосте происходит по открытым ключам.

Характерные признаки Bug'а

Bug проявляет себя громким шуршанием за плинтусом и чередующиемися ошибками вида Segmentation Fault (SIGSEGV) и Illegal Hardware Instruction (SIGILL):

$ ./sssh.scm -i /home/avp/.ssh/lazycat localhost uname
libssh version:       0.5.2
libguile-ssh version: 0.2
1. ssh_new
2. ssh_options_set
3. ssh_connect
4. ssh_is_server_known
   ok
[1]    2205 segmentation fault  ./sssh.scm -i /home/avp/.ssh/lazycat localhost uname

Инструменты сыщика

Один из способов отладки -- это добавление отладочных сообщений (или трейсов, от англ. trace, т.е. след) в код. Это на удивление эффективный способ узнать, как работает (или не работает) программа -- в том числе, он может помочь выследить даже хитрого bug'а.

С кодом на Scheme всё достаточно просто -- можно использовать, например, display и write. Примеры:

(display "debug message\n")
=> debug message

...

(write "Hello Scheme World\n")
=> "Hello Scheme World
"

...

(define value 1024)
(display (string-append "Value:" (number->string value))
=> Value: 1024

...

(define some-list '(a b c d e))
(display some-list)
=> (a b c d e)

А вот так можно добавить вывод отладочного сообщения в код на C, чтобы он печатался из Scheme:

scm_display (scm_from_locale_string ("debug message\n"),
             scm_current_output_port ());

То же самое, но в виде удобного макроса:

#define PRINT_DEBUG(data)\
  scm_display (data, scm_current_output_port ())

...

PRINT_DEBUG(scm_from_locale_string ("debug message\n"));

Сужаем круг поиска

Вернёмся к нашему логу.

...
3. ssh_connect
4. ssh_is_server_known
   ok
[1]    2205 segmentation fault  ./sssh.scm -i /home/avp/.ssh/lazycat localhost uname

Путём добавления дополнительных отладочных сообщений после 4-го (в логе выше) можно легко понять, что sssh аварийно завершает свою работу при вызове библиотечной функции guile_ssh_public_key_to_string (ssh:public-key->string)

...
(display "4. ssh_is_server_known\n")
...
(let ((public-key (ssh:public-key->string
                    (ssh:private-key->public-key private-key))))
  ...

которая, в свою очередь, обращается к функции ssh_string_to_char из библиотеки libssh, где и происходит ошибка:

...
str_key = publickey_to_string (data->ssh_public_key);
ret = scm_from_locale_string (ssh_string_to_char (str_key));
ssh_string_free (str_key);
...

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

Вопрос к линковщику

Изучение документации по созданию разделяемых библиотек (к слову, вот этот замечательный документ) дало подсказку, что нужно посмотреть, как идёт процесс динамического связывания. Как-никак, мы же отлаживаем разделяемую библиотеку, верно? Для того, чтобы увидеть этот процесс в действии, нам потребуется увеличительное стекло и одна переменная окружения: имя её LD_DEBUG. В вышеупомянутом замечательном документе пишут, что этой переменной можно присвоить несколько значений. На самом деле, вы можете присвоить ей любое значение, просто только некоторые, вполне определённые значения несут смысл.

Одно из таких сакральных слов -- ну конечно, help. Присвоим же это значение, ударим в бубен и посмотрим, что из этого получится:

$ export LD_DEBUG=help
$ ./sssh.scm -i /home/avp/.ssh/lazycat localhost uname
Valid options for the LD_DEBUG environment variable are:

  libs        display library search paths
  reloc       display relocation processing
  files       display progress for input file
  symbols     display symbol table processing
  bindings    display information about symbol binding
  versions    display version dependencies
  all         all previous options combined
  statistics  display relocation statistics
  unused      determined unused DSOs
  help        display this help message and exit

To direct the debugging output into a file instead of standard output
a filename can be specified using the LD_DEBUG_OUTPUT environment variable.

Voilà! Вместо ошибки сегментации от нашей программы мы получили замечательный вывод справки от линковщика о доступных значениях LD_DEBUG. Наиболее интересным для нас сейчас будет значение symbols. Присвоим его переменной и попробуем запустить программу снова (надеюсь, вы не забыли надеть защитные очки?):

$ export LD_DEBUG=symbols
$ ./sssh.scm -i /home/avp/.ssh/lazycat localhost uname
...
      2487: symbol=ssh_string_to_char;  lookup in file=/usr/lib/i686/cmov/libcrypto.so.0.9.8 [0]
      2487: symbol=ssh_string_to_char;  lookup in file=/lib/i686/cmov/libpthread.so.0 [0]
      2487: /usr/local/lib/libguile-ssh.so.0: error: symbol lookup error: undefined symbol: ssh_string_to_char (fatal)
[2]    2487 segmentation fault  ./sssh.scm -i /home/avp/.ssh/lazycat localhost uname

Итак, мы получили ОЧЕНЬ много информации на выходе (я пропустил здесь эту часть), но нам важны последние несколько строчек. Вот оно! Линковщик не может найти символ ssh_string_to_char. Если посмотреть лог выше, то видно, что он просматривает, в том числе, и libssh:

...
 2505: symbol=ssh_string_to_char;  lookup in file=/usr/lib/libssh.so.4 [0]
...

Но ведь эта библиотека как раз и должна содержать в себе определение данной функции!

Идём по следу

Посмотрим-ка на версию библитеки в Debian GNU/Linux. Но прежде выключим подробный вывод сообщений от линковщика, присвоив LD_DEBUG пустую строку:

$ export LD_DEBUG=""
$ aptitude search libssh
...
i A libssh-4            - tiny C SSH library
...
$ aptitude versions libssh-4
i A 0.4.5-3+squeeze1    oldstable                  500 
p A 0.5.3-1~bpo60+1     squeeze-backports          100 

То есть, на Debian GNU/Linux у меня сейчас стоит версия libssh 0.4.x, тогда как мне известно, что API библиотеки был изменён в версии 0.5.x.

Попробуем поставить libssh 0.5 и запустить программу снова. Я собрал версию 0.5.3 из исходников, make install установил её в /usr/local/lib. Укажем программе, где искать библиотеку через переменную LD_LIBRARY_PATH:

$ LD_LIBRARY_PATH=/usr/local/lib ./sssh.scm -i /home/avp/.ssh/lazycat localhost uname
libssh version:       0.5.2
libguile-ssh version: 0.2
1. ssh_new
2. ssh_options_set
3. ssh_connect
4. ssh_is_server_known
   ok
5. ssh_userauth_pubkey
6. ssh_channel_new
7. ssh_channel_open_session
8. ssh_channel_request_exec
Linux

Наконец-то! Заработало! Последняя строчка вывода получена по протоколу SSH и является выводом команды uname.

Заключение

Получается, что баг скрывался даже не в коде (точнее, не совсем в коде), а в динамической линковке с разделяемой библиотекой. При динамическом связывании линковщику не удавалось найти функцию ssh_string_to_char из libssh, тем не менее вызов этой функции всё же происходил. Я думаю так: процессор закладывал аргументы в стэк и прыгал на начало несуществующей функции -- из-за этого-то мы и получали чередующиеся ошибки SIGSEGV/SIGILL. Элементарно, Ватсон.

Странно только, что эта ошибка так себя проявляла -- вот уж чего бы я не ожидал, так это SIGSEGV/SIGILL на этапе исполнения программы из-за того, что линковщик не смог найти искомую функцию при динамическом связывании.

Одно из возможных решений проблемы -- это привязка библиотеки Guile-SSH к конкретной стабильной версии libssh. Это не самый лучший вариант, так как не во всех дистрибутивах используется новая версия библитеки (примером тому могут служить Debian GNU/Linux и старые версии Ubuntu GNU/Linux). Однако это решение позволит избежать проблем с поддержкой совместимости Guile-SSH с libssh 0.4.x.

На этом у меня всё. Надеюсь, что это расследование вам было интересно.

- Артём

Guile-SSH

Доброго времени суток, случайные и не случайные читатели этого блога.

Занимаюсь сейчас разработкой библиотеки Guile-SSH, которая призвана обеспечить возможность работы с протоколом SSH из программ, написанных на языке Scheme (с использованием интерпретатора GNU Guile).

Презентация по проекту: odp pdf (CC-BY-SA 3.0)

Guile-SSH является обёрткой над libssh и находится на начальной стадии разработки. На данный момент библиотека предоставляет API для создания простого SSH-клиента (пример клиента можно посмотреть здесь). API для создания SSH-сервера планируется.

Для сборки текущей версии библиотеки вам нужны GNU Guile 1.8 и libssh 0.5.3 или новее. Инструкции по сборке и установке можно найти здесь. Последняя версия Guile-SSH на данный момент -- 0.2, но если надумаете собирать, то лучше берите последний коммит с master'а. Код относительно стабилен (по крайней мере, стараюсь ничего не ломать в коммитах).

- Артём

Переворот строки c помощью указателей

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

Вот мой вариант ответа:

#include <stdio.h>

void reverse(char *str)
{
 char *p = str;

 while (*p && *(p + 1) && *p++)
  ;

 while ((p > str) && (*str += *p) && (*p = *str - *p) && (*str++ -= *p--))
  ;
}

int main(int argc, char **argv)
{
 char *str = argv[1];
 reverse(str);
 printf("desrever -- %s\n", str);
 return 0;
}

И, разумеется, "hello world":

$ gcc reverse.c -o reverse
$ ./reverse "hello world"
desrever -- dlrow olleh

- Артём

Препроцессор C

Доброго времени суток, случайные и не случайные читатели.

На прошлой неделе, изучая код ядра Linux, я наткнулся на довольно занятный заголовочный файл. В файле объявлено два макроса и одна inline-функция. Заинтересовало же меня следующее: название одного из макросов совпадает с именем функции, равно как и набор их параметров. Я подумал -- как будет работать этот код? И решил провести эксперимент, как только появится свободное время.

На следующий день я вспомнил про этот файл -- и понял, что результат компиляции очевиден и без проведения эксперимента: достаточно вспомнить, как работает компилятор gcc.

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

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

После этого происходит компиляция, потом -- преобразование ассемблерного кода в машинный код и, наконец, линковка.

На этапе линковки можно увидеть (конечно же) ошибки линковки. Эти ошибки обычно сводятся к тому, что линковщику не удаётся найти в данных ему файлах функцию, на которую есть ссылка где-то в коде (undefined reference).

Если же всё прошло нормально, то в конце-концов мы получаем исполняемый файл.

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

Посмотрим на примере.

Итак, допустим, у нас есть заголовочный файл и файл с исходным кодом -- назовём их test.h и test.c соответственно. Вот содержимое test.h:

 
#ifndef __TEST_H__ 
#define __TEST_H__

inline int function1(int param) 
{
 return param; 
}

#define function1(param) function1(param)

#endif /* ifndef __TEST_H__ */

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

А вот содержимое test.c:

 
#include <stdio.h> 
#include "macros.h"

int main(int argc, char *argv[])
{ 
 printf("Result of calling function1: %d\n", 
  function1(100));

 return 0;
}

Результат работы препроцессора можно увидеть, передав gcc ключ -E, вот так:

$ gcc -E test.c -o test.i

Не буду приводить здесь этот файл test.i полностью (он достаточно объёмен) -- посмотрим лишь на последние 15 строк:

 
$ tail -15 test.i 


inline int function1(int param)
{
 return param;
}
# 3 "test.c" 2

int main(int argc, char *argv[])
{
 printf("Result of calling function1: %d\n",
  function1(100));

 return 0;
}

Здесь мы видим, что в main() всё так же вызывается function1(), однако этот вызов был получен в результате работы препроцессора: он нашёл макрос function1, потом встретил имя function1 в main(), и подменил его результатом обработки макроса.

Попробуем сделать следующее: поменяем макрос function1() в test.h таким образом, чтобы он разворачивался в вызов несуществующей функции function2():

 
#define function1(param) function2(param)

Теперь, после работы препроцессора мы увидим следующую картину:

 
$ tail -15 test.i        


inline int function1(int param)
{
 return param;
}
# 3 "test.c" 2

int main(int argc, char *argv[])
{
 printf("Result of calling function1: %d\n",
  function2(100));

 return 0;
}

Видно, что препроцессор совершенно не обратил внимание на то, что функция function2() нигде не объявлена -- он просто подменил макрос на результат его обработки. Об этой возмутительной оплошности нам скажет линковщик:

 
$ gcc test.c 
/tmp/ccUBRByP.o: In function `main':
test.c:(.text+0x19): undefined reference to `function2' collect2:
выполнение ld завершилось с кодом возврата 1

Из этого можно сделать интересный вывод: если у нас существует функция и макрос с одинаковым именем и набором параметров, то нам не удастся вызвать функцию напрямую -- её вызов прежде будет обработан препроцессором, который подставит в место вызова результат обработки макроса. Таким образом, функция может быть "скрыта" от компилятора, или подменена. Например, поменяв макрос следующим образом:

 
#define function1(param) 0

И скомпилировав программу, мы увидим следующее:

$ gcc test.c 
$ ./a.out 
Result of calling function1: 0

Мы получили ноль, несмотря на то, что передавали в функцию число 100, так как вызов функции был принят препроцессором за вызов макроса, и заменён на тело макроса -- то есть, на ноль.

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

Нестандартное применение функции getopt(3)

Доброго времени суток, случайные и неслучайные читатели этого блога. Сегодня я хочу рассказать об одном любопытном способе применения функции getopt(3).

Как вы наверняка знаете, getopt(3) позволяет легко разбирать (или "парсить", да простит меня русский язык) опции командной строки, переданные программе.

Вместо термина "опция" так же используются термины "флаг" или "ключ".

Вот простой пример, демонстрирующий работу getopt(3):

#include <stdio.h>
#include <unistd.h>

int
main(int argc, char* argv[])
{
  int opt;

  while ((opt = getopt(argc, argv, "ab:")) > 0)
    {
      switch (opt)
      {
      case 'a':
          puts("'a' option was found.");
          break;

      case 'b':
          printf("'b' option was found. number = %d\n", atoi(optarg));
          break;
      }
    }

  return 0;
}

Работа с программой может выглядить следующим образом:

$ ./a.out -a -b 10
'a' option was found.
'b' option was found. number = 10


В данном примере используются только короткие опции - то есть, которые начинаются с "-", например, "-h", "-n 9". Родственная функция getopt_long(3) позволяет парсить так же и длинные опции, начинающиеся с "--" (например, "--verbose" или "--option=value").

Использование getopt(3) позволяет избежать создания собственного "велосипеда" для разбора опций командной строки. А теперь представим, что нам нужно разобрать подобным образом массив строк, передаваемый в качестве параметра нашей собственной функции. Почему бы не использовать для этого столь удобный инструмент, как getopt(3)? Тем более, что функция main() очень похожа на другие функции (точнее, другие функции очень похожи неё). Разве что main() является стандартной точкой входа в программу, с которой начинается её выполнение. Но для нашего эксперимента это не столь важно. Попробуем "подделать" обычную функцию под main(), чтобы getopt(3) не обнаружила подмены. Для этого посмотрим внимательно на main().

Итак, main() принимает в качестве параметров количество аргументов командной строки argc и собственно сам список аргументов argv, который представляет собой массив указателей на строки (массивы символов). Чтобы getopt(3) работала корректно, нужно создать функцию с подобным набором параметров. Внутри функции организуем разбор "командной строки":

void
fun1(int argc, char* argv[])
{
  int opt;
  
  while ((opt = getopt(argc, argv, "ab:c:")) > 0)
    {
      switch (opt)
 {
 case 'a':
   puts("'a' was found.");
   break;

 case 'b':
   printf("'b' was found. optarg = %d\n", atoi(optarg));
   break;

 case 'c':
   printf("'c' was found. optarg = %d\n", atoi(optarg));
   break;
 }
    }
}  

Теперь возьмёмся за main():

#include <stdio.h>
#include <unistd.h>

void fun1(int argc, char* argv[]);

int
main(void)
{
  int   argc = 3;
  char* test_array[] = { "-a", "-b 10", "-c 20" };

  fun1(argc, test_array);

  return 0;
}

Скомпилируем и запустим программу:

$ gcc -o getopt-test getopt-test.c
$ ./getopt-test
'b' was found. optarg = 10
'c' was found. optarg = 20


Как можно заметить, куда-то подевался нулевой элемент массива argv - словно getopt(3) начала просмотр массива с первого элемента. Разберёмся, почему. Вспомним, что при запуске программы нулевой элемент массива argv, передаваемый в main(), содержит имя исполняемого файла программы. Поэтому функция getopt(3) попросту пропускает его, так как он не содержит опций командной строки.

Решение проблемы выглядит следующим образом:

int
main(void)
{
  int   argc = 4; /* 3 аргумента командной строки + имя программы */
  char* test_array[] = { "fun1", "-a", "-b 10", "-c 20" };

  fun1(argc, test_array);

  return 0;
}

Скомпилируем и проверим исправленную версию программы:

$ gcc -o getopt-test getopt-test.c
$ ./getopt-test
'a' was found.
'b' was found. optarg = 10
'c' was found. optarg = 20


По результатам работы программы видно, что теперь getopt(3) находит опцию "-a".

Конвейерная обработка данных в Unix

Доброго времени суток, случайные и не случайные читатели этого блога.

Сегодня я хотел бы рассмотреть пример программы, которая может работать в режиме "конвейера" (pipeline), что является обыденным делом для утилит Unix-подобных систем.

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

Наша программа будет принимать на вход вывод некой другой программы, обрабатывать эти данные неким образом и передавать на стандартный вывод.

Просто? Просто.

Исходный текст программы тоже очень простой:

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

int
main(void)
{
  char ch;

  while (fread(&ch, sizeof(char), 1, stdin))
    putchar(toupper(ch));
  
  exit(EXIT_SUCCESS);
}

Теперь немного технических деталей. Когда вы пишете что-то вроде

$ cat my-file.txt | sort

командная оболочка (shell) связывает стандартный поток вывода stdout команды cat(1) со стандартным потоком ввода stdin команды sort(1). Таким образом, эти команды связываются в конвейер, проходя через который данные преобразуются определённым образом. В данном примере, мы выводим (считываем) содержимое файла my-file.txt на stdout, команда sort(1) принимает эти данные на stdin, сортирует их и выводит на stdout. На этом конвейер заканчивается и обработанные данные выводятся на терминал.

Поскольку для организации конвейера используются стандартные потоки ввода-вывода stdin и stdout, и связывание программ в конвейер осуществляет командная оболочка, от программы в общем случае требуется только получить данные с stdin, обработать их и вывести в stdout для (возможно) последующей обработки. Ещё более замечательным является тот факт, что одной программе не нужно знать внутреннее устройство другой программы, чтобы работать с ней в одном конвейере.

Важно заметить, что программы, составляющие конвейер, выполняются параллельно. Если рассматривать приведённый ранее пример, то команда cat(1) и sort(1) работают одновременно. Как только cat(1) выводит данные на stdout, они сразу же могут быть считаны командой sort(1) из stdin.

Сравните с последовательностью команд, разделённых точкой с запятой, которые выполняются одна за другой:

$ cat my-file.txt; sort

Сначала будет выполнена команда cat(1), которая выведет содержимое файла my-file.txt на экран, а потом будет выполнена команда sort(1), которая будет ждать ввода данных с stdin.

Скомпилируем наконец нашу программу и посмотрим, что полезного она может сделать.

$ gcc tu.c -o tu

Протестируем работу программы. Свяжем в конвейер команду awk(1) и нашу програму:

$ awk --copyleft | ./tu

Команда awk(1) с параметром --copyleft выводит краткий вариант лицензии GPL на stdout. Далее наша программа считывает в цикле по одному символу с stdin, преобразует считанный символ в прописной и выводит этот символ на stdout.

Вывод нашей программы можно так же отправить дальше по конвейеру.

$ awk --copyleft | ./tu |\
   sed s/'1989, 1991-2010 FREE SOFTWARE FOUNDATION'/'2012 Artyom Poptsov'/

Неплохой обзор конвейерной обработки данных в Unix дан в следующих статьях:

• Использование UNIX: Что внутри конвейера?
• http://en.wikipedia.org/wiki/Pipeline_(Unix) (en)

Рисуем новогоднюю ёлку с помощью Си: алгоритм номер 2.

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

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

Постановка задачи

Последний (и самый, на мой взгляд, интересный) способ отрисовки ели заключается в следующем. Я рисую в строке количество звёздочек, равное номеру строки. Для того, чтобы ель сохраняла некоторую симметричность, я сдвигаю каждую чётную строку вправо на 1 символ.

В итоге, должно получиться следующее:

01      X
02      **
03     ***
04     ****
05    *****
06    ******
07   *******
08   ********
09  *********
10  **********
12      ##
13      ##

Реализация

Для начала, зададим цвет для звезды на верхушке ели, цвет для самой ели и цвет для ствола дерева. Несмотря на то, что программа будет работать в консоли, это не проблема - можно использовать управляющие символы. О них можно прочитать, например, здесь:
http://www.linuxjournal.com/article/8603

Чтобы каждый раз не писать управляющие последовательности для задания цвета строки, я решил поступить следующим образом:

#include <stdio.h>

#define N 15

int main() {
  char c_red[N]    = "\033[49;31;5m"; // Красный
  char c_green[N]  = "\033[49;32;5m"; // Зелёный
  char c_yellow[N] = "\033[49;33;5m"; // Жёлтый
  char c_reset[N]  = "\033[0;0;0m";   // Возврат к первоначальным
                                      //   значениям
  // ...
}

Теперь я могу использовать более осмысленные названия цветов в вызове функции printf(), например:

printf("%sHello %sWorld%s\n", c_yellow, c_green, c_reset); 

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

  int base_width, half_base_width;
  int i, j;

  printf("Please enter height of the fir-tree:\n> ");
  scanf("%d", &base_width);

  half_base_width = base_width / 2;

  for(i = 1; i <= base_width; i++) {
    /* Печатаю номер строки */
    printf("%s%02d\t", c_red, i);

    /* Печатаю одну линию */
    for(j = 1; j < (half_base_width + (i / 2) + 1); j++) {
      if(((i % 2) >  0) && (j <  (half_base_width - (i / 2))) ||
         ((i % 2) == 0) && (j <= (half_base_width - (i / 2))))
        putchar(' ');
      else
        if(i == 1)
          printf("%sX", c_red);  // Большая звезда на верхушке
        else
          printf("%s*", c_green); // Ель
    }
    
    putchar('\n');
  }

Для повышения реалистичности, в завершении отрисовки ёлки нарисую ещё ствол дерева.

  for(i = base_width + 1; 
      i < (base_width + base_width / 10 * 3); i++) {
    printf("%s%02d\t", c_red, i);
    for(j = 0; j <= half_base_width + (base_width / 10) / 2; j++)
      if(j < half_base_width - (base_width / 10))
        putchar(' ');
      else
        printf("%s#", c_yellow);
    putchar('\n');
  }

Значение (base_width + base_width / 10 * 3) используется для задания высоты ствола в зависимости от высоты ели. Значение half_base_width + (base_width / 10) / 2 и half_base_width - (base_width / 10) используется для задания ширины ствола.

В итоге, ель у меня выглядит вот так:

Рисуем новогоднюю ёлку с помощью Си: алгоритм номер 1.

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

Теперь пришло время нарисовать первое подобие ёлки.

Постановка задачи

Должно получиться следующее:

   _
  |      X <-------- звезда
  |      *
  |     ***
  |     ***
 10    *****
  |    ***** <------ ёлка
  |   ******* 
  |   *******
  |  *********
  |_ *********
    |----9----|

       рис.1

Всё очень просто: нужно взять за основу алгоритм отрисовки треугольника и удвоить каждую строку: 1, 1, 3, 3, 5, 5...

Высота дерева задаётся пользователем.

Дабы повысить соответствие оригиналу, я хочу поместить на верхушку ёлки "звезду". Ну, вроде тех массивных стеклянных/пластмассовых штуковин, которые часто надевают на верхушку ёлки для усиления праздничного эффекта. За звезду сойдёт английская буква "X" (см. рис.1)

Реализация

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

for(i = 0; i < height; i++) {
  // ...
}

С ним не будет особых проблем. А вот над вложенным циклом нужно подумать. Каким образом реализовать удвоение каждой строки? Посмотрим, как будет расти количество звёздочек в строке, в зависимости от номера строки. Как видно из куска кода выше, переменная i изменяется в цикле от 0 до height - 1 (о чём говорит знак "меньше").

  i | кол. звёздочек в строке
  --|------------------------
  0 | 1        X
  1 | 1        *
  2 | 3       ***
  3 | 3       ***
  4 | 5      *****
  5 | 5      *****
  6 | 7     *******
  7 | 7     *******
  8 | 9    *********
  9 | 9    *********
  ...
        рис.2

Из рисунка выше видно, что количество звёздочек увеличивается на 2 на каждой чётной строке. Это даёт подсказку, как можно реализовать алгоритм.

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

for(i = 1; i <= h; i++)
  for(j = 1; j <= (h + i); j++) {
    if(j <= (h - i + 1))
      putchar(' ');
    else
      putchar('*');
    putchar('\n');
  }

Начальное значение счётчиков i, j равно 1, чтобы обеспечить отступ в один дополнительный символ перед каждой строкой.

Нарисуем 3 строку треугольника (i = 3). Пусть высота h равна 5.

h + i = 8;
h - i + 1 = 3;

 |<------------- 8 ------------->|
  _______________________________
 |   |   |   | * | * | * | * | * |
  -------------------------------
             |<----- j > 3 ----->|

             рис.3

Я думаю, из рисунка 3 можно понять работу этого алгоритма.

В алгоритме отрисовки ёлки половину её ширины нужно вычислять отдельно - ведь теперь эта величина не равна высоте, как в случае с отрисовкой треугольника. Однако, не всё так уж и плохо - есть простая формула, о которой я уже говорил в предыдущем посте.

hw = h / 2 - 1          (1)

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

Теперь вернёмся к проблеме удвоения каждой строки. Поскольку, как уже было сказано выше, количество звёздочек увеличивается на 2 на чётной строке, попробуем сделать вот что.

Я просто разделю i на 2 во всех проверках условий во вложенном цикле. Вот так:

// ...
int hw;
// ...
hw = height / 2 - 1;

for(i = 0; i < height; i++)
  /* Печатаю номер строки в обратном порядке (снизу вверх) */
  printf("%02d\t", height-i);

  for(j = 0; j <= (hw + i / 2); j++) { // <-- здесь
    if(j < (hw - i / 2)) // <-- и здесь
      putchar(' ');
    else
      if(i == 0) // или можно написать: if(!i)
        /* Рисую большую звезду на верхушке ёлки */
        putchar('X');
      else
        putchar('*');

    putchar('\n');
  }
// ...

Если строка нечётная, то hw будет увеличиваться в проверке условия завершения цикла for() и уменьшаться в условии if() - на остаток от деления, т.е. на 1. В результате, количество звёздочек в нечётной строке увеличиться на 2. Если же номер строки - чётный, то никаких изменений не происходит, просто копируется предыдущая строка.

Мне кажется, это потрясающе просто и понятно.

Рисуем новогоднюю ёлку с помощью Си: алгоритм номер 0.

Некоторые даже в предпраздничные дни забивают себе голову алгоритмами, программированием и прочими непраздничными вещами.

Вот и я перед новым годом (который, кстати, уже наступил - если что) придумал себе проблему, и упорно решал её на протяжении длительного времени.

С чего всё началось

А началось всё со следующей задачи.

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

    *
   ***
  *****

Для примера, положим, что я ввёл высоту, равную 5 строкам.

 _
|      *
|     ***
5    *****
|   *******
|_ *********
  |----9----|

Тогда, как видно на примере выше, ширина основания треугольника равна 9 звёздочкам. Если я возьму другую высоту - например, 10 строк - то получу треугольник шириной 19 звёздочек. Отсюда выводим формулу:

w = h / 2 - 1          (1)

где w - ширина, h - высота.

Рисую равнобедренный треугольник

Чтобы нарисовать ровный треугольник, мне нужно помещать определённое количество пробелов перед каждой строкой, в зависимости от номера строки.

 -Что есть-  -Что должно получиться-
1 *              1     *
2 ***            2    ***
3 *****      =>  3   *****
4 *******        4  *******
5 *********      5 *********
 \             /
  номер строки 

Чтобы это осуществить, надо знать номер центрального "столбца".

строки
  1     *
  2    ***
  3   *****
  4  *******
  5 *********
    123456789  <-- столбцы
        ^
   центральный
     столбец

Очевидно, в треугольнике высотой 5 строк, центральным будет 5-й столбец. И тут оказывается, что для нахождения центрального столбца нам нужно знать только высоту h треугольника, введённую пользователем - ведь, если верить формуле 1, то номер центрального столбца всегда будет совпадать с высотой. Это позволяет упростить программу.

Вот, кстати, код на Си:

#include <stdio.h>

int main() {
  int height;
  int i, j;

  printf("Please enter height:\n> ");
  scanf("%d", &height);

  for(i = 1; i <= height; i++) {
    for(j = 1; j <= (height + i); j++) {
      if(j <= (height - i + 1))
        putchar(' '); // Печатаем пробел
      else
        putchar('*'); // Печатаем звёздочку
    }
    putchar('\n'); // Переходим на новую строку
  }

  return 0;    
}

Этот код, несмотря на его простоту, нуждается в дополнительных комментариях для понимания.

Первый цикл работает, пока i меньше или равно половины ширины треугольника. А поскольку, как уже было сказано выше, высота треугольника совпадает с номером центрального столбца, т.е. его центра - то я могу использовать значение введённой пользователем высоты height. Что я и делаю.

Второй цикл работает, пока j меньше или равно height плюс значение i (т.е. номер текущей строки).

Далее я проверяю, если j меньше или равно height минус i плюс 1. Единица здесь задаёт смещение всего треугольника от левой границы экрана. Если условие выполняется, то я печатаю пробел, иначе - звёздочку.

Эта программа решает поставленную задачу - рисует треугольник из звёздочек высотой N строк. Но...

Что не так с этим алгоритмом?..

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

Как бы нарисовать что-то, похожее на ёлку - да ещё так, чтобы эта ёлка высотой N, будучи вписанной в квадрат размером NxN, в основании была так же равной N?

Я подошёл к решению этой проблемы со всей серьёзностью, и нарисовал следующее:

fig. 1 отображает алгоритм отрисовки звёздочек, который я уже описывал выше. Получается равнобедренный треугольник.

Алгоритм отрисовки треугольника я не случайно назвал "алгоритмом номер 0" - следующие два алгоритма отрисовки ёлки реализуются на основе идей, реализованных в программе, решающей задачу с треугольником.

fig. 2 показывает, как можно нарисовать нечто похожее на ёлку - путём удвоения каждой строки. Но ширина основания по-прежнему меньше высоты.

fig. 3 показывает алгоритм отрисовки ёлки. Это как раз то, что нужно. Как видно из рисунка, ширина ёлки при таком способе заполнения строк равна высоте. Причём, здесь можно заметить интересную особенность данного алгоритма - она показана на рисунке справа от fig. 3.

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

Реализацию второго алгоритма я рассмотрю в следующем посте.

Нахождение последовательностей одинаковых символов в строке с помощью указателей

Понадобилось мне для одной программы найти в строке все последовательности одинаковых символов, и провести с ними необходимые операции (допустим, посчитать и вывести на экран - сейчас это не важно).

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

Отлично, теперь пора перейти к реализации.

Считываю строку в массив

Мне понадобится символьный массив размером N, массив указателей на тип char (тоже размером N), переменная для хранения количества последовательностей, счётчик для цикла вывода последовательностей и... всё.

#include <stdio.h>

#define N 256

/* Прототип будущей функции */
int findSequences(const char *arr, char **arrPtr);

int main() {
  char charray[N];
  char *sequence[N];
  int count = 0;
  int i;

  printf("Please enter string:\n> ");
  fgets(charray, N, stdin);

  count = findSequences(charray, sequence);

  // ...

  return 0;
}

/* Полное описание функции */
int findSequences(const char *arr, char **arrPtr) {
  // невидимый текст ;)
}

Кое-что о функциях и их прототипах

Прототип функции не является обязательным элементом программы. Он необходим, если нужно обратиться к функции до её полного объявления, и для проверки передаваемых функции параметров. Например, я мог бы написать полное объявление функции findSequences() до функции main() - в таком случае, мне не потребовался бы её прототип. Но у данного способа объявления функций есть два недостатка:

• Во-первых, если функций много, то главная функция main(), с которой начинается выполнеие любой программы на Си, оказывается где-то далеко в конце файла исходника. Читать такой код стороннему человеку, да и самому тоже, неудобно.
• Во-вторых,иногда нужно сделать так, чтобы функция f1 вызывала функцию f2, а дать полное описание функции f2 до её использования в функции f1 не представляется возможным. А если из функции f1 нужно вызвать f2, а из f2 - f1 (т.е. необходима косвенная рекурсия)? Тогда без прототипов никак не обойтись.

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

Разумеется, никто не требует давать полное описание всех функций до main(), или же после - и использовать прототипы. Можно комбинировать эти два метода, в зависимости от удобства и задачи.

Всё это, конечно, хорошо, но... что насчёт функции findSequences()?

В поисках последовательностей...

Посмотрим ещё раз на прототип функции findSequences():


int findSequences(const char *arr, char **arrPtr);


Ясно, что она возвращает значение типа integer. А в качестве параметров принимает ссылку на начало строки (т.е. на начало символьного массива charray, в котором хранится строка), и указатель на массив указателей. Причём, ключевое слово const перед типом параметра говорит, что этот параметр ни за что, ни при каких условиях не должен (и не будет) изменяться. Что мне и нужно - я хочу, чтобы функция только искала и считала последовательности в строке, а не портила её.

Пришло время заглянуть внутрь функции.

int findSequences(const char *arr, char **arrPtr) {
  char *p = arr;
  int count = 0;

  arrPtr[0] = p;
  while(*p && ('\n' != *p))
    if(*p != *(p+1)) 
      arrPtr[++count] = ++p;
    else
      p++;

  return count;
}

В начале, я создаю указатель на тип char и присваиваю ему адрес первого элемента массива arr. Соответственно, первый элемент массива указателей arrPtr должен содержать ссылку на первый элемент arr (т.к. начало массива - это начало последовательности).

В цикле я перемещаюсь по массиву arr слева направо, перемещая указатель вправо с каждой итерацией. То есть, я прибавляю к указателю единицу, и он смещается вправо по массиву... нет, не на единицу. Он смещается на одну ячейку массива, т.е. на длину типа char.

Цикл while() работает, пока символ по адресу p не равен 0 (т.е. не достигнут конец строки) и не равен '\n' (т.е. символу перевода строки). Звёздочка '*' перед указателем p говорит о том, что я работаю не самим указателем, а с данными, на которые он указывает. В цикле я делаю проверку на определённое событие - если символ *p не равен символу *(p+1), т.е. символу в следующей ячейке массива, то я увеличиваю счётчик найденных последовательностей на 1, передвигаю указатель вправо, чтобы он указывал на следующую ячейку массива, и сохраняю его адрес в массиве указателей. Поскольку знак инкремента '++' стоит до переменной, которую он увеличивает - то действие инкремента, т.е. увеличения значения переменной на единицу, происходит до того, как её значение будет использовано в выражении.

По завершению цикла, я возвращаю значение count, т.е. количество найденных последовательностей в строке.

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

Замечания по задаче удаления из строки лишних пробелов

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

Я получил от Антона Александровича (преподавателя из НИИТа) несколько замечаний по решению этой задачи:


1. Бесконечный цикл while(1) можно заменить на цикл while(charray [i]).

Известно, что строка (в отличии от массива символов) всегда заканчивается нулевым символом, он же '\0'. Так же известно, что 0 (ноль) в языке Си (да и во многих других ЯП) означает "ложь" (false). Исходя из этих двух фактов становится ясно, что я могу использовать проверку кода i-того символа из строки в условии завершения цикла while().

while('\0' != charray[i]) {
  ...
  i++;
}

Проверку условия можно упростить следующим образом:

а) while('\0' != charray[i]) - цикл выполняется, пока i-й элемент строки не равен символу '\0'
б) while(0 != charray[i]) - цикл выполняется, пока i-й элемент строки не равен нулю
в) while(charray[i]) - цикл выполняется, пока проверка i-го элемента не возвращает значение "false".

Очевидно, что вышеперечисленные варианты равнозначны. Однако, вариант "в" работает не хуже варианта "а", а если нет разницы - то зачем писать больше? Поэтому, в конечном счёте я использовал вариант "в".

Использование вместо бесконечного цикла while(1) цикл с проверкой i-того элемента строки на соответствие нулевому символу позволило избавиться от двух строк в теле цикла:

if(i == len)
  break;

Понятно, что теперь эти строки не нужны, т.к. цикл завершится, когда проверка charray[i] вернёт "false".


2. Из функций можно выкинуть переменную len2.

Возьму для примера функцию удаления лишних пробелов.

int remove_n(char *arr, int len, int pos) {
  int i;
  int len2 = len-1;

  for(i = pos; i <= len2; i++)
    arr[i] = arr[i+1];
  
  return 0;
}

Я использовал дополнительную переменную len2 для сохранения результата вычисления len-1, чтобы не вычислять это значение при каждой итерации в цикле for(). Как я понимаю, в данном случае использование len2 излишне, и цикл можно переписать следующим образом:

for(i = pos; i <= len-1; i++)
  arr[i] = arr[i-1];

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


3. Проверка на наличие лишнего пробела, после работы конечного автомата, не является "костылём"

После размышлений, я понял, почему конечный автомат не может удалить все пробелы в конце строки. Рассмотрим два случая:

    _______________________
1. | * | * | * | * |   | 0 |
    -----------------------
                     ^
    _______________________
2. | * | * | * |   |   | 0 |
    -----------------------
                 ^

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

while(charray[i])

  switch(state) {

  case STATE_1:
    if(' ' == charray[i]) {
      state = STATE_2;
      if((0 == i) || !charray[i+1])) // <-- здесь
        continue;
    }
    break;

  case STATE_2:
    ...
    break;

  }

  i++;
}
...

То есть, если символ, находящийся в строке на позиции i+1 является нулём, я перехожу к следующей итерации цикла while(charray[i]) без инкремента i. Таким образом, я могу удалить последний пробел тем же способом, что я удаляю все пробелы в начале строки.

Но если я попробую использовать приведённый выше код для второго варианта (когда пробелов в конце строки больше 1), то опять же получу один лишний пробел в конце строки после работы программы. Почему? А потому, что условие !charray[i+1] никогда не выполнится уже в том случае, если количество пробелов в конце строки будет хотя бы равно двум: элемент строки, находящийся на позиции i+1, так же будет являться пробелом.

Поэтому я согласен с Антоном Александровичем, что проверка на наличие лишнего пробела после работы конечного автомата не является "костылём", а всего лишь дополняет решение задачи.

Тем не менее, я понял, что можно обойтись без дополнительной проверки длины строки, чтобы удалить последний пробел в строке. Ведь переменная i в цикле while() увеличивается до тех пор, пока i-тый элемент в строке не будет равен нулю.

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

...
while(charray[i]) {
  ...
  i++;
}

if(' ' == charray[i-1])
  charray[i-1] = 0;
...

Заполнение массива равным количеством случайных положительных и отрицательных чисел

В процессе решения одной из задач столкнулся с интересной проблемой. Как заполнить массив размером N случайными положительными и отрицательными числами так, чтобы количество отрицательных чисел в массиве было равно количеству положительных? И не подряд (например, сначала отрицательные числа, потом - положительные), а, цитируя знаменитое произведение Льюиса Кэрролла в переводе Бориса Заходера, "строго как попало"?

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

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

Генерирую случайное число

Для генерации случайных чисел, мне потребуются библиотеки


#include <stdlib.h>
#include <time.h>


Разумным будет задание размера массива N и максимальное значение MAX для генератора случайных чисел с помощью define:


#define N 10
#define MAX 100


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

Чтобы генерировать числа от 0 до 99, я должен получить остаток от деления результата работы rand() на MAX.


srand(time(0)); // Завожу генератор случайных чисел
buf = rand() % MAX; // Генерирую случайное число


Отлично, но мне нужно, чтобы генератор случайных чисел генерировал и отрицательные числа. В таком случае, нужно вычесть из полученного случайного числа другое число. Например, если мне требуется получить случайные числа в диапазоне от -50 до 49, то я могу сделать следующее:


buf = rand % MAX - (MAX / 2);


Теперь самое интересное. Мне предстоит...

Заполнение массива

Как заполнить массив одинаковым количеством положительных и отрицательных чисел в случайном порядке? Судя по условию поставленной задачи, количество положительных и отрицательных чисел в массиве размером N должно быть равно N / 2.

Отсюда следует, что можно проследить за количеством накиданных в массив положительных и отрицательных чисел. Так же можно предварительно сохранить случайно сгенерированное число в некий буфер, и посмотреть его знак. На основании этого, принимать решение - заносить очередное сгенерированное число в массив, или нет?

Отлично. Завожу два счётчика, один из которых будет считать количество "положенных" в массив отрицательных чисел, другой - положительных. Цикл while() будет выполняться, пока rand() не сгенерирует достаточное количество случайных чисел для заполнения массива.

int array_fill(int *arr, int len, int max) {
  int max_h = max / 2;
  int len_h = len / 2;
  int buf;
  int p = 0; // Счётчик положительных чисел
  int n = 0; // Счётчик отрицательных чисел
  int i = 0;

  srand(time(0));
  
  while(i < len) {
    buf = rand() % max - max_h;
 
    if((buf < 0) && (n < len_h)) {
      arr[i] = buf;
      n++;
      i++;
    }

    if((buf >= 0) && (p < len_h)) {
      arr[i] = buf;
      p++;
      i++;
    }
    
  }

  return 0;
}

Итак, предположим, что "лимит" на отрицательные числа исчерпан (n == len_h). Цикл будет повторяться, пока в buf не окажется положительное число. То же произойдёт, если p == len_h, только в этом случае цикл будет повторяться до появления в buf отрицательного числа. Таким образом, мы получаем массив, заполненный в равном количестве как положительными, так и отрицательными числами. Задача решена.

Пример вызова функции:


array_fill(arr, N, MAX);



P.S. На самом деле, у этой функции есть один недостаток - при нечётном размере массива она зацикливается. Этот недостаток можно преодолеть, добавив в функцию проверку на чётность размера массива. Если проверка даёт положительный результат, то остаётся сгенерировать ещё одно число и записать его в начало (или конец) массива.

Удаление из строки "лишних" пробелов

У меня есть программа, которая должна запросить у пользователя строку, и произвести с полученной строкой определённые действия. Но вот ведь незадача - некоторые очень неаккуратно работают с клавиатурой, и при вводе данных могут случайно нажать пробел несколько раз вместо одного, добавить совершенно ненужных пробелов в начале строки, или даже в конце. А представьте, что будет, если по клавиатуре пройдётся ваш любимый кот? Это будет катастрофа! Но спокойно, можно предусмотреть и это. Далее я хочу рассмотреть метод (несомненно, один из многих) удаления лишних пробелов из строки.

Для начала определим, какие пробелы считаются лишними. Лишними считаются

1. все пробелы, которые стоят в начале строки (т. е. перед первым символом строки, не являющегося пробелом);
2. пробелы между символами, если количество идущих подряд пробелов равно двум или более;
3. все пробелы в конце строки.

По условию задачи, нельзя пользоваться дополнительными массивами, кроме как массивом для хранения введённой пользователем строки.

Копать или не копать?

Для решения этой задачи удобно использовать так называемый конечный автомат. То есть, некий абстрактный автомат, который может пребывать в конечном количестве состояний. Например, в двух: "копать" или "не копать". Этот автомат будет переключаться из одного состояния в другое, в зависимости от выполнения каких-то условий.

Итак, звучит неплохо. Осталось придумать, как это использовать для решения задачи удаления пробелов.

Но прежде, чем что-то удалять из строки, мне нужна сама строка.

Получаю строку c помощью функции fgets()

Напишем работающую программу, которая считывает строку.

#include <stdio.h>
#include <string.h>
#define N 256

int main() {
  int charray[N];

  printf("Please enter string:\n> ");
  fgets(charray, N, stdin);
  
  return 0;
}

Эта программа пока только считывает строку со стандартного ввода (stdin) с помощью функции fgets() в массив символов размером N.

У функции fgets() есть замечательное свойство - используя её, я никогда не выйду за границу массива, если попытаюсь ввести строку длиннее, чем размер массива. Однако, у неё есть одна особенность: стоит мне ввести строку и нажать [Enter], как в конец введённой строки добавиться знак "\n", т.е. символ перехода на новую строку. Эта проблема решается гениально просто. Нужно лишь узнать длину введённой строки с помощью strlen():

len = strlen(charray); // Определяем длину строки
if('\n' == charray[len-1]) // Если предпоследний символ в строке='\n'
  charray[len-1] = 0;      // то заменяем его на нулевой символ, 
                           // т.е. символ конца строки, он же '\0'

Теперь у меня есть строка, готовая к дальнейшей обработке.

Реализация конечного автомата

Для удаления одного лишнего пробела, нужно сдвинуть элементы массива влево на 1. То есть, если пробел находится на позиции S, то на его место запишется символ из ячейки S+1, вместо S+1 запишется S+2 и т.д.

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

int remove_spc(char *arr, int len, int pos) {
  int i;
  int len2 = len-1;

  for(i = pos; i <= len2; i++)
    arr[i] = arr[i + 1];

  return 0;
}

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

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

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

Работу автомата удобно представить ввиде ленты и считывающей/записывающей головки над ней. Пустые ячейки - это пробелы, звёздочками отмечены занятые ячейки, т.е. в которых присутствуют символы, не являющиеся пробелами.

   _______________________________
1 | * | * |   |   |   | * | * | * |
   -------------------------------
        ^
   _______________________________
2 | * | * |   |   |   | * | * | * |
   -------------------------------
            ^
   _______________________________
3 | * | * |   |   |   | * | * | * |
   -------------------------------
                ^
   _______________________________
4 | * | * |   |   | * | * | * |   |
   -------------------------------
                ^
   _______________________________
5 | * | * |   | * | * | * |   |   |
   -------------------------------
                ^

На шаге 1 автомат находится в состоянии STATE_1. Ячейка занята, так что считывающая головка передвигается вправо на одну клетку.

На шаге 2 автомат всё ещё пребывает в состоянии STATE_1. Считывающая головка находится над пустой ячейкой, поэтому автомат перемещает считывающую головку вправо на одну ячейку и переключается в состояние STATE_2. Но здесь не всё так просто. Если мы хотим удалить пустую ячейку в начале строки, то нам не нужно перемещать считывающую головку на следующую ячейку перед переключением в STATE_2.

Теперь посмотрим, что же происходит, когда автомат находится в состоянии STATE_2. А происходит вот что: автомат начинает выкидывать пробелы из строки, вызывая функцию remove_spc (шаг 4). При этом, сама "считывающая головка" остаётся неподвижной, и после каждого вызова функции проверяет содержимое ячейки, над которой она находится.
Как только в ней оказывается какой-либо символ (шаг 5), не являющийся пробелом, автомат переключается вновь в состояние STATE_1.

Вот, как это выглядит в программном коде:

#define STATE_1 1
#define STATE_2 2

...

while(1) {
  switch(state) {
  
  case STATE_1:
    if(' ' == charray[i]) {
      state = STATE_2;
      if(0 == i)
        continue;
    }
    break;

  case STATE_2:
    if(' ' != charray[i])
      state = STATE_1;
    else {
      remove_spc(charray, len, i);
      continue;
    }
    break;

  } // end switch

  i++;

  if(i == len)
    break;

} // end while

А теперь плохая новость. После работы автомата, при количестве лишних пробелов в конце строки больше одного, после последнего символа всё равно оставался один пробел. Я не смог пока разобраться, почему так происходит. Поэтому, после завершения бесконечного цикла while(1), пришлось использовать костыль в виде следующих строчек:

len = strlen(charray);
if(' ' == charray[len-1])
  charray[len-1] = 0;

Этот кусок кода удаляет самый последний пробел, если он остаётся после работы автомата.

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

Исходник:
remove-spaces.c

Вывод приветствия в зависимости от времени, введённого пользователем

Задача заключается в том, чтобы запросить у пользователя время в формате ЧЧ:ММ:СС и вывести приветствие на английском языке - "Good morning!", "Good evening!" etc.

Задача достаточно простая, для ввода данных используется функция scanf(), которая принимает время в заданном формате. Далее мы должны проверить часы (ЧЧ) на принадлежность определённому времени суток.

Основная идея заключается в том, чтобы сопоставить временные интервалы с приветствием:

• Утро - с 6 часов до 12 - "Good moring!"
• День - с 12 до 18 - "Good afternoon!"
• Вечер - с 18 до 22 - "Good evening!"
• Ночь - с 22 до 6 - "Good night!"

Попробую усовершенствовать задачу. Пусть программа не только приветствует нас, но и сообщает человеческим голосом по-английски текущее время. Например, "It's twenty to nine." Для этого создам новый тип:


typedef char TString[60];


Далее, создаю массив из 12 элементов типа TString, в которые сразу заношу части фраз, характеризующие положение минутной стрелки (т.е. текущую часть часа):

TString currenttime[12]={"o'clock",          // 0
                         "five past",        // 1
                         "ten past",         // 2
                         "quarter past",     // 3
                         "twenty past",      // 4
                         "twenty-five past", // 5
                         "half past",        // 6
                         "twenty-five to",   // 7
                         "twenty to",        // 8
                         "quarter to",       // 9
                         "ten to",           // 10
                         "five to"};         // 11

В отдельную функцию можно вынести операцию определения положения минутной стрелки на основе введённых пользователем минут (ММ).

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

Всё хорошо, но почему бы программе, раз уж я взялся её учить говорить на человеческом языке, не называть часы словами? Для этого мне потребуется ещё один массив, размером в 23 элемента (массивы нумеруются с нуля, поэтому 23, а не 24). Тип использую тот же, TString.

В моём варианте секунды не учитываются вообще. Но думаю, можно найти применение и им.

Пример работы программы:


Please enter a time:
> 21:40:55
Good evening!
It's twenty to twenty-two.


Исходник:
greetings.c