язык C в Linux: вопросы начального уровня

Вопросы написания собственного программного кода (на любых языках)

Модератор: Olej

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: язык C в Linux: вопросы начального уровня

Непрочитанное сообщение Olej » 19 ноя 2013, 18:48

Виктория писал(а):
Но то, о чём говорю я - это не тесты ... в понимании тестов, это просто "очень маленькие задачки"...
Маленькие задачи? Или задачи с некоторым припрятанным смыслом?
То, что я писал, относится к examples.tgz.
Да, там "очень маленькие задачки" записаны мной с некоторыми попутными трюками: передача параметра по значению, несколько странные синтаксические формы записи, неявные переполнения и др. - такие вещи нужно привыкать сразу видеть, отмечать, и к ним привыкать ;-)

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: язык C в Linux: вопросы начального уровня

Непрочитанное сообщение Olej » 20 ноя 2013, 13:51

Виктория писал(а):В Компьютерре раньше статей на эту тему много было, типа как сейчас на habrahabre
Что нужно знать про арифметику с плавающей запятой (из песочницы)
Хорошее, понятное и внятное объяснение.

Повеселила фраза:
Ирония в том, что Intel знала, как сделать свою спецификацию такой же производительной, ...
Пробашлять? Кэш? :lol: ... обычно эти парни именно так подтверждают свою ... "производительность". :lol:
(мне приходилось наблюдать такие "подтверждения" на реальных проектах ... со стороны "Сименс" ... и "Шнайдер-Электрик" ... общеизвестно как "подтверждает" Microsoft ...)

Единственный минус этой и подобных публикаций, умаляющих их достоинства, состоит в том, что большинство вещей рассказывается умозрительно, "на пальцах" ... "как оно должно быть".
Но разговор то идёт о конкретной технической дисциплине? ... и чем 10 раз рассказать - лучше 1 раз показать на примере простейшего кода в 2 строчки, который может быть воспроизведён, и имеет своим результатом не совсем тривиальный итог.

В этом беда многих пишущих: подтверждайте свои утверждения кодом. ;-)

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: язык C в Linux: вопросы начального уровня

Непрочитанное сообщение Olej » 20 ноя 2013, 19:15

Olej писал(а):Динамическими такие структуры являются не в силу динамичности её узлов (это дело 2-е), а в силу динамичности связей этих узлов, выраженных через ссылки. Поэтому куда точнее для таких структур будет название, иногда употребляемое, как "ссылочные структуры данных".
По поводу связных структур (динамических) у меня тоже есть замечание, которое а). не очевидное, б). появилось в процессе длительных разборок с кодом ядра Linux (т.е. в Linux особо актуально) и в). совсем не лишне обратить на это внимание тех, кто совершенствуется в использовании C:

... во многих (во всех?) книгах, где затрагиваются списковые структуры, объяснения и примеры строятся на связанных в список структурах по типу:

Код: Выделить всё

struct list_head {
   struct list_head *next;
   ... // здесь все остальные поля данных увязываемых структур
}

В таком списке признаком конца списка является равенство NULL поля связи next (это классика, описываемая в любой книжке).

Естественно, что в коде ядра любой ОС полно разнообразных списковых структур (кольцевая очередь задач шедулера, очереди обслуживания ... и всё, всё, всё).

Но начиная с ядра 2.6:
а). все списковые структуры ядра Linux были переписаны на использование только одной структуры связи (см. определения "/lib/modules/<версия_ядра>/source/include/linux/list.h"):

Код: Выделить всё

struct list_head {
   struct list_head *next, *prev;
} list_head_t;
б). все списки строятся как кольцевые 2-х-связные списки, независимо от того, как они будут использоваться (возможно, как простейшая одностязная очередь)...
в). как оказалось, на основе именно таких списков можно построить любые связные структуры: деревья, направленные графы и т.д.
г). но ещё одним важнейшим преимуществом есть то, что из-за отсутствия признака проверки поля связи на NULL (поля связи теперь никогда не могут стать NULL), исключаются тяжелейшие ошибки разыменования указателя NULL в результате ошибки кода.

А вот это уже не классика, и не описана она ни в одной книжке ;-) ... не считая нескольких книг в природе (а их таких совсем немного) по ядру Linux.
Но часто и станет читать книжки по ядру Linux прикладной программист, работающий в Windows? ;-)

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: язык C в Linux: вопросы начального уровня

Непрочитанное сообщение Olej » 20 ноя 2013, 23:43

Olej писал(а): В таком списке признаком конца списка является равенство NULL поля связи next (это классика, описываемая в любой книжке).
Вот одна из множества возможных реализаций (односвязный линейный список), иллюстрирующий такой классический вариант:

Код: Выделить всё

#define SIZE 7

typedef struct node_single {
   struct node_single *next;
   int data;  // данные узла
} node_single_t;

node_single_t* single_add_after( node_single_t *new, node_single_t *node ) {
   new->next = node->next;
   node->next = new;
   return new;
}

void test020( void ) {
   struct node_single nd = { NULL, 1 }, *head = &nd, *pc = head;
   int i;
   for( i = 0; i < SIZE; i ++ )
      ( pc = single_add_after( (node_single_t*)alloca( sizeof( node_single_t) ), pc )
      )->data = i + 2;
   pc = head;
   do {                        // проход по списку
      printf( "%d, ", pc->data );
      pc = pc->next;
   } while( pc != NULL );
   printf( "\n" ); 
}

Код: Выделить всё

olej@notebook:~/2013_WORK/AntonG/examples$ ./ptrs 1
01 ---------------------------------------
1, 2, 3, 4, 5, 6, 7, 8, 
------------------------------------------
P.S. Обратите внимание как в примере лихо (на грани фола) используется alloca() ;-)
Вложения
7.c
(3.84 КБ) 397 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: язык C в Linux: вопросы начального уровня

Непрочитанное сообщение Olej » 20 ноя 2013, 23:54

Olej писал(а):
Olej писал(а): В таком списке признаком конца списка является равенство NULL поля связи next (это классика, описываемая в любой книжке).
Вот одна из множества возможных иллюстраций такой классики:
Olej писал(а): А вот это уже не классика, и не описана она ни в одной книжке ;-) ... не считая нескольких книг в природе (а их таких совсем немного) по ядру Linux.
А вот аналогичный (почти) предыдущему пример в "стиле ядра Linux":

Код: Выделить всё

// from kernel: "/lib/modules/.../source/include/linux/list.h"
typedef struct list_head {
   struct list_head *next, *prev;
} list_head_t;

void INIT_LIST_HEAD( list_head_t *list ) {
   list->next = list;
   list->prev = list;
}

list_head_t* list_add_after( list_head_t *new, list_head_t *node ) {
   node->next->prev = new;
   new->next = node->next;
   new->prev = node;
   node->next = new;
   return new;
}

struct node {
   list_head_t link;
   int data;  // данные узла
};

void test021( void ) {
   struct node nd = { {}, 1 }, *head = &nd;
   INIT_LIST_HEAD( (list_head_t*)head );
   int i;
   list_head_t *pc = (list_head_t*)head;
   for( i = 0; i < SIZE; i ++ )
      ((struct node*)( pc = list_add_after(
                               (list_head_t*)alloca( sizeof( list_head_t ) ), pc )
                     ))->data = i + 2;
   pc = (list_head_t*)head;
   do {                        // обход кольцевого списка вперёд
      printf( "%d, ", ((struct node*)pc)->data );
      pc = pc->next;
   } while( pc != (list_head_t*)head );
   pc = pc->prev;
   do {                        // обход кольцевого списка назад
      printf( "%d, ", ((struct node*)(pc->prev))->data );
      pc = pc->prev;
   } while( pc != (list_head_t*)head );
   printf( "\n" ); 
}
P.S. Интересно, что определения и макросы для struct list_head, присутствующие в хэдерах ядра Linux, отсутствуют а определениях пользовательского пространства (/usr/include/*.h), я их позаимствовал из определений ядра (/lib/modules/<версия_ядра>/source/include/linux/list.h). Но это только подчёркивает ещё раз тот факт, что ядро Linux и библиотеки GCC пишут совершенно разные люди (и как мы знаем ;-) - не соприкасающиеся, и не сильно любящие друг друга).

Здесь список а). кольцевой и б). 2-х-связный ... поэтому и тестовый пример проходит по нему сначала вперёд, а потом обратно:

Код: Выделить всё

olej@notebook:~/2013_WORK/AntonG/examples$ ./ptrs 2
02 ---------------------------------------
1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 
------------------------------------------
P.P.S. Признаком достижение конца такого кольцевого списка не равенство указателя очередного узла NULL, а совпадение адреса очередного элемента с указателем головы списка. За этим нужно тщательно следить, чтоб не ездить по кругу ... как, говорят, в эстонских правилах дорожного движения под знаком "круговое дивжение" предусмотрена табличка: "Нэ болэе трох раз!". :lol:
Вложения
7.c
(3.84 КБ) 403 скачивания

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: язык C в Linux: вопросы начального уровня

Непрочитанное сообщение Olej » 21 ноя 2013, 16:10

Olej писал(а): Ещё один очень интересный, хоть и частный вопрос - рекурсия.
Выразительная мощь рекурсивных решений - огромная.
Ещё пару слов относительно рекурсии...

Изучающие язык (C или любой другой) не понимают ... или не сразу замечают, что рекурсия на одних и тех же задачах всегда может быть 2-х сортов: 1). восходящая (что делается чаще) и 2). нисходящая.
При нисходящей рекурсии требуемые действия текущего уровня проделываются раньше рекурсивного вызова следующего уровня, при восходящей - после возврата с рекурсивного вызова следующего уровня.

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

Пример:

Код: Выделить всё

#define SIZE 7

typedef struct node_single {
   struct node_single *next;
   int data;  // данные узла
} node_single_t;

node_single_t *new_list( int level ) {
   struct node_single *p = malloc( sizeof( node_single_t ) );
   p->data = level;
   p->next = level ? new_list( --level ) : NULL;
   return p;
}

void put_list( node_single_t *list, int direct ) {
   if( !list ) return;
   if( direct ) printf( "%d , ", list->data );
   put_list( list->next, direct );  
   if( !direct ) printf( "%d , ", list->data );
}

void destroy( struct node_single *p ) {
   if( p->next ) destroy( p->next );
   free( p );
}

void test07( void ) {               // восходящая и нисходящая рекурсии
   struct node_single *head = new_list( SIZE );
   printf( "нисходящая рекурсия: " );
   put_list( head, 1 );
   printf( "\n" );
   printf( "восходящая рекурсия: " );
   put_list( head, 0 );
   printf( "\n" );
   destroy( head );                 // уничтожение списка
}


Результат:
olej@notebook:~/2013_WORK/AntonG/examples$ ./opera 8
08 ---------------------------------------
нисходящая рекурсия: 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 ,
восходящая рекурсия: 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ,
------------------------------------------

Абсолютно одни и те же ссылочные структуры данных ... но результат радикально меняется от порядка применения рекурсии.
Вложения
3.c
(5.57 КБ) 389 скачиваний

Аватара пользователя
Виктория
Писатель
Сообщения: 113
Зарегистрирован: 28 дек 2012, 14:05
Откуда: Самара
Контактная информация:

Re: язык C в Linux: вопросы начального уровня

Непрочитанное сообщение Виктория » 24 ноя 2013, 12:24

Olej писал(а):
Виктория писал(а):Если посмотреть на эту задачу совсем уж прагматично, то правильный ответ возможен с использованием объединения union и сравнения целых чисел. Хотя, как мне кажется, возможны и более элегантные решения...
2. Кстати, по всей книге Моулер & Форсайт (а они считаются крупнейшими мировыми авторитетами в численных методах, наряду с Хэмингом) предел погрешности вычислений определяется именно по схеме:

Код: Выделить всё

do {
   X /= 2.
} while ( 1. + X != 1. + X / 2. );
Ну так они же использовали дремучий Фортран! Мое решение средствами языка Си для приложений типа embedded, без глянца. Я не спорю и вполне с Вами согласна, что при реальном использовании придется попотеть над пропущенными в первом приближении мелочами...

Есть ещё один такой момент, который хотелось бы отметить. Думаю, что красота и выразительность решения зависят от конструкций используемого языка. В свое время был такой язык с обратной польской записью - Форт. Алгоритм решения этой задачи на Форте наверняка будет выглядеть очень впечатляющим!

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: язык C в Linux: вопросы начального уровня

Непрочитанное сообщение Olej » 26 ноя 2013, 18:40

Olej писал(а): Но после K&R (образца 1970г.) и даже после других более поздних книг в C происходило достаточно много изменений-дополнений - C99:
Изменения C99 тоже заслуживают отдельного рассмотрения:
- они плохо описаны в "штатной" литературе по C (коротая, в лучшем случае, описывает C89);
- они все между собой не равнозначны по значению своему;
- они описаны в стандартах и статьях, но описаны сами изменения (списком), а не примеры применения самых существенных дополнений.

Сам стандарт C99 смотрим:

- глава C99 перевода : Полный справочник по C.

- если уж очень тонкие детали нужны, или очень хочется - оригинал опубликованного черновика (Draft — August 11, 2008) стандарта ISO: ISO/IEC 9899:201x - последнего, готовящегося стандарта C11 (только нужно быть сразу готовым к тому, что там 556 страниц строго формализованного текста).

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: язык C в Linux: вопросы начального уровня

Непрочитанное сообщение Olej » 26 ноя 2013, 18:48

Виктория писал(а): Есть ещё один такой момент, который хотелось бы отметить. Думаю, что красота и выразительность решения зависят от конструкций используемого языка. В свое время был такой язык с обратной польской записью - Форт. Алгоритм решения этой задачи на Форте наверняка будет выглядеть очень впечатляющим!
На FORTH было много элегантных решений.
И в своё время он стал даже весьма широко использоваться, особенно в области робототехники.
Но к сегодня - это уже только экзотика ... хотя и существуют отдельные сайты любителей, посвящённые "FORTH vs всё остальное" ;-)

Часть таких же красивых решений, как на FORTH, можно выписать на Python.
Но это уже всё из области:
- ... выразительная мощность языка большая, когда у него динамическая типизация (или вообще отсутствует типизация как LISP)...
- но платой за это будет сложность написания и сложность отлаживания скрытых ошибок...
- а поэтому такие мощные языки редко будут использоваться IT индустрией, производством, мэйнстримом ... а будут уделом энтузиастов ;-)

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: язык C в Linux: вопросы начального уровня

Непрочитанное сообщение Olej » 26 ноя 2013, 19:17

Olej писал(а):C99 тоже заслуживают отдельного рассмотрения:
Одно из нововведений:
Olej писал(а):в большинстве учебников-руководств по языку C я вообще не вспомню где бы упоминали о наличии даже такого целого раздела, как комплексная математика - complex.h.
Казалось бы: кому нужны комплексные вычисления кроме:
- электротехники-радиотехники, где все расчёты комплексные;
- цифровой обработки сигналов ... на алгоритмах которой скрыто (внутри) работают все системы передачи данных, гаджеты все и т.д.

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

1. можно, например, "паковать" для return 2 найденных функцией корня квадратного уравнения ... как показывалось 2-мя стр. раньше ...

2. и если предыдущий пример сильно искусственный (для иллюстрации), то есть широченная область задач, где данные естественным образом отображаются в 2-х компонентные - это 2D графика, планиметрия.
И это совершенно естественное представление, потому что комплексное значение - это 2-х координатное отображение точки комплексной плоскости, а метрика комплексного пространства (функция cabs()) совпадает с метрикой декартового простанства: sqrt( (x1-x2)^2 + (y1-y2)^2 ).
И здесь мы используем тип complex вместо определения 2D точки типа:

Код: Выделить всё

struct {
   int X, Y;
}
При этом все комплексные (векторные) операции наполняются естественным для 2D смыслом: x + y, x - y, cabs( x + y ) и т.д.

Ответить

Вернуться в «Программирование»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 11 гостей