После стандартизации в ANSI спецификация языка Си оставалась относительно неизменной в течение долгого времени, в то время как Cи++ продолжал развиваться (в 1995 году в стандарт Си была внесена Первая нормативная поправка, но её почти никто не признавал). Однако в конце 1990-х годов стандарт подвергся пересмотру, что привело к публикации ISO 9899:1999 в 1999 году. Этот стандарт обычно называют «С99». В марте 2000 года он был принят и адаптирован ANSI.
Сравнение С99 с С89.
Отличия между С99 и С89 можно разбить на три общие категории:
 новые возможности, добавленные к С89
 возможности, удаленные из С89
 возможности, которые были изменены или расширены
Многие из отличий между С89 и С99 достаточно незначительны и относятся лишь к нюансам языка. А в этой книге основное внимание уделяется достаточно заметным изменениям — заметным настолько, чтобы влиять на способ написания программ.
Новые возможности
Скорее всего, самыми заметными из новых средств, которых не было в С89, являются те, которые связаны с использованием новых ключевых слов:
inline
restrict
_Bool
_Complex
_Imaginary
К другим важным новинкам относятся:
 массивы переменной длины
 поддержка арифметических операций с комплексными числами
 тип данных long long int
 комментарий //
 возможность распределять код и данные
 добавления к препроцессору
 объявления переменных внутри оператора for
 составные литералы
 массивы с переменными границами в качестве членов структур
 назначенные инициализаторы
 изменения в семействе функций printf() и scanf()
 зарезервированный идентификатор __func__
 новые библиотеки и заголовки
Большинство возможностей были созданы комитетом по стандартизации, причем многие из этих возможностей созданы с учетом расширений языка, имеющихся в разных реализациях языка С. Впрочем, в некоторых случаях возможности были позаимствованы у C++, как, например, ключевое слово inline и комментарии вида //. Важно понять, что при создании С99 не были добавлены классы в стиле C++, наследование и функции-члены. В том, что С должен остаться С — в этом комитет по стандартизации был единодушен.
Удаленные средства
Самым заметным "излишеством", удаленным при создании С99, было правило "неявного int". В С89 во многих случаях, когда не было явного указания типа данных, подразумевался тип int. А в С99 такое не допускается. Также удалено неявное объявление функций. В С89, если функция перед использованием не объявлялась, то подразумевалось неявное объявление. А в С99 такое не поддерживается. Если программа должна быть совместима с С99, то из-за двух этих изменений, возможно, придется немного подправить код.
Измененные средства
При создании С99 было сделано несколько изменений имевшихся средств. По большей части, эти изменения расширяют возможности или вносят определенную ясность в их значение. И только в небольшом количестве случаев изменения ограничивают или сужают применение средства. Многие изменения небольшие, однако некоторые из них являются достаточно важными, в том числе:
 уменьшение ограничений транслятора
 новые целые типы
 расширение правил продвижения целых типов
 более строгие правила употребления оператора return
Что касается влияния этих изменений на уже написанные программы, то самое значительный эффект имеет изменение правил употребления оператора return, из-за чего код, возможно, придется немного подправить.
• Ключевое слово inline
При разработке С99 было добавлено ключевое слово inline, которое применяется к функциям. Ставя inline в начале объявления функции, вы предлагаете компилятору оптимизировать вызовы к этой функции. Обычно это означает, что при компиляции код этой функции будет вставляться на месте вызовов. Однако ключевое слово inline является всего лишь запросом к компилятору и может быть проигнорировано. В С99 особо отмечено, что использование inline "предполагает, что вызовы функции должны быть максимально быстрыми". Спецификатор inline также поддерживается в языке C++, и синтаксис С99 для этого ключевого слова совместим с C++.
• Новые встроенные типы данных

• Расширение массивов
Массивы переменной длиныВ С89 размерности массивов необходимо объявлять при помощи выражений из целых констант, причем размер массива фиксируется во время компиляции. В силу определенных обстоятельств, в С99 это правило было изменено. В С99 можно объявить массив, размерности которого определяются любыми допустимыми целыми выражениями, в том числе и такими, значения которых становятся известны только во время выполнения. Такой массив называется массивом переменной длины (variable-length array, VLA). Однако такими массивами могут быть только локальные массивы (то есть те, у которых область видимости — прототип или блок). Вот пример массива переменной длины:
void f(int diml, int dim2)
{
int matrix[diml][dim2]; /* двумерный массив переменной длины */
/* ... */
}
В данном случае размер matrix определяется значениями, передаваемыми функции f() через переменные dim1 и dim2. Таким образом, в результате каждого вызова f() может получиться массив matrix с самыми разными измерениями.
• Однострочные комментарии
Благодаря Стандарту С99, в языке С появились однострочные комментарии. Комментарий такого вида начинается с // и доходит до конца строки. Например,
// Это комментрий
int i; // это другой комментарий
• Распределение кода и объявлений
В соответствии со Стандартом С89 все объявления, находящиеся внутри блока, должны предшествовать первому оператору кода. Но к Стандарту С99 это правило не относится. Рассмотрим, например, программу
#include

int main(void)
{
int i;
i = 10;
int j; // неправильно для С89; допустимо для С99 и C++
j = i;
printf("%d %d", i, j);
return 0;
}
Здесь выражение
i = 10 находится между двумя объявлениями: переменной i и переменной j. Стандарт С89 такое не разрешает. Зато это вполне допускается в С99 (да и в C++ тоже)
• Изменения препроцессора
Возможно, самым важным изменением препроцессора является возможность обрабатывать макросы с переменным количеством аргументов. На переменное количество аргументов указывает многоточие (...), находящееся в определении макроса. Встроенный препроцессорный идентификатор __VA_ARGS__ определяет, куда будут подставляться аргументы. Например, после включения в программу определения
#define MyMax(...) max(__VA_ARGS__)
• Объявление переменных внутри цикла for
#include

int main(void)
{
// объявить i внутри for
for(int i=0; i < 10; i++)
printf("%d ", i);

return 0;
}
• Назначенные инициализаторы
В С99 появилась новая для С возможность, которая будет особенно полезна для программистов, работающих с разреженными массивами. Это назначенные инициализаторы. Такие инициализаторы бывают двух видов: одного вида — для массивов, а другого — для структур и объединений. Для массивов используется назначенные инициализаторы такого вида:
[индекс] = знач
где индекс указывает элемент, инициализируемый с помощью значения знач (то есть тот элемент, которому присваивается начальное значение знач). Например,
int а[10] = { [0] = 100, [3] = 200};
В данном случае инициализируются только элементы с индексами 0 и 3.
Для членов структур или объединений используется назначенные инициализаторы такого вида:
.имя-члена
Применение к структуре назначенного инициализатора позволяет легко инициализировать только нужные члены структуры. Например,
struct mystruct {
int a;
int b;
int c;
} ob = { .c = 30, .a = 10 };
В данном случае член b остается неинициализированным. Кроме того, применение назначенных инициализаторов дает возможность инициализировать структуру, даже не зная порядка расположения ее членов
• Новые возможности семейства функций printf() и scanf()
В С99 для семейства функций printf() и scanf() предусмотрена новая возможность: они могут манипулировать с типами данных long long int и unsigned long long int.
• Новые библиотеки С99
Заголовок Назначение
Поддерживает арифметические операции с комплексными числами.
Дает доступ к флажкам состояния вычислителя, выполняющего операции с плавающей точкой и другим сигналам этого вычислителя.
Определяет стандартный, переносимый набор имен целых типов. Также поддерживает функции, которые работают с целыми значениями наибольшей разрядности.
Добавлен в 1995 году Поправкой 1. Определяет имена макросов,соответствующие разным операторам, таким как && и ^.
Поддерживает логические типы данных. Определяет имена макросов bool, true и false, что помогает обеспечивать совместимость с C++.
Определяет стандартный, переносимый набор имен целых типов. Этот заголовок входит в состав .
Определяет макросы для родового (абстрактного) типа чисел с плавающей точкой.
Добавлен в 1995 году Поправкой 1. Поддерживает многобайтовые и двухбайтовые функции.
Добавлен в 1995 году Поправкой 1. Поддерживает многобайтные и двухбайтовые функции классификации.
• Расширение граничных значений трансляции
Термин "граничные значения трансляции" означает минимальное число разнообразных элементов, которые должен обрабатывать компилятор С. Сюда входит длина идентификаторов, количество уровней вложенности, количество выражений case и допустимое количество членов структуры или объединения. В С99 увеличены некоторые из предельных значений для количества этих элементов несмотря на то, что они и так были достаточно щедро определены Стандартом С89. Вот некоторые примеры:
Граничное значение для количества C89 C99
уровней вложенности блоков 15 127
уровней вложенности условных включений 8 63
значащих символов во внутреннем идентификаторе 31 63
значащих символов во внешнем идентификаторе 6 31
членов структуры или объединения 127 1023
аргументов при вызове функции 31 127
________________________________________
• Неявный int больше не поддерживается
Несколько лет назад язык C++ отменил правило неявного int, а с приходом С99 этому примеру последовал и язык С. В С89 правило неявного int гласит, что если явный спецификатор типа отсутствует, то подразумевается тип int. Больше всего это правило применялось к возвращаемому типу функций.
• Удалены неявные объявления функций
Если в С89 встречался вызов функции до явного объявления, то создавалось неявное объявление этой функции. Это неявное объявление имеет такой вид:
extern int имя();
В С99 неявные объявления функций не поддерживаются.
• Ограничения на return
В С89 в функции, которая имеет возвращаемый тип, отличный от void (т.е. предполагается, что такая функция возвращает значение), может встретиться оператор return без выражения. Хотя в результате этого теоретически поведение программы было неопределенным, технически в этом не было ничего "незаконного". Но в С99 в функции, тип которой отличен от void, оператор return обязан иметь выражение. То есть в С99 внутри функции, которая согласно определению возвращает значение, любой оператор return обязан иметь ассоциированное с ним значение, которое и будет возвращено этой функцией. Таким образом, следующая функция является синтаксически допустимой в С89, но недопустима в С99:
int f(void)
{
/* ... */
return ; // в С99 этот оператор должен возвращать значение
}

• Расширенные целые типы
С99 в определяет несколько расширенных целых типов. Расширенные типы включают в себя типы с точной разрядностью, минимальной разрядностью, максимальной разрядностью и самый быстрый целый тип. Вот подборка таких типов:
Расширенный тип Что означает
int16_t Тип 16-разрядных целых
int_least16_t Тип целых, содержащий не менее 16 разрядов
int_fast32_t Самый быстрый тип целых, содержащий не менее 32 разрядов
intmax_t Тип самых больших целых
uintmax_t Тип самых больших целых без знака

После стандартизации в ANSI спецификация языка Си оставалась относительно неизменной в течение долгого времени, в то время как Cи++ продолжал развиваться (в 1995 году в стандарт Си была внесена Первая нормативная поправка, но её почти никто не признавал). Однако в конце 1990-х годов стандарт подвергся пересмотру, что привело к публикации ISO 9899:1999 в 1999 году. Этот стандарт обычно называют «С99». В марте 2000 года он был принят и адаптирован ANSI.

Несмотря на то, что большая часть кода Си будет справедлива и для Си++, Си++ не является надмножеством Си и не включает его в себя. Существует и такой верный для Си код, который неверен для Си++.
Существуют и другие различия. Например, Си++ не разрешает вызывать функцию main() внутри программы, в то время как в Си это действие правомерно. Кроме того, Си++ более строг в некоторых вопросах; например, он не допускает неявное приведение типов между несвязанными типами указателей и не разрешает использовать функции, которые ещё не объявлены.
Более того, код, верный для обоих языков, может давать разные результаты в зависимости от того, компилятором какого языка он оттранслирован. Например, следующая программа печатает «С», если компилируется компилятором Си, и «С++» — если компилятором Си++. Так происходит из-за того, что символьные константы в Си (например 'a') имеют тип int, а в Си++ — тип char.
Язык программирования С++ произошёл от Си. Однако Си и Си++ развивались независимо, что привело к росту несовместимостей между ними. Последняя редакция Си, С99, добавила в язык несколько конфликтующих с С++ особенностей. Эти различия затрудняют написание программ и библиотек, которые могли бы нормально компилироваться и работать одинаково в компиляторах Си и Си++, что, конечно, запутывает тех, кто программирует на обоих языках.
Бьярне Строуструп, придумавший Си++, неоднократно выступал за максимальное сокращение различий между Си и Си++ для создания максимальной совместимости между этими языками. Противники же такой точки зрения считают, что так как Си и Си++ являются двумя различными языками, то и совместимость между ними не так важна, хоть и полезна. Согласно этому лагерю, усилия по уменьшению несовместимости между ними не должны препятствовать попыткам улучшения каждого языка в отдельности.
Вот различия между этими языками, существующие на сегодня:
• inline — подставляемые функции существуют в глобальном пространстве С++, а в Си — в пространстве файла (статическом пространстве). Другими словами, это значит, что в С++ любое определение подставляемой функции (независимо от переопределения функций) должно соответствовать правилу одного определения, требующего того, чтобы любая подставляемая функция была определена только один раз. В Си же одна и та же подставляемая функция может быть определена по-разному в разных компилируемых файлах одной программы.
• В отличие от Си++, ключевое слово bool в С99 требует включения соответствующего заголовочного файла stdbool.h. Предыдущие стандарты Си не определяли булевый тип вообще, поэтому для этого часто использовались различные (а значит, несовместимые) методы.
• Символьные константы (заключённые в одинарные кавычки) имеют тип int в Си и тип char в Си++. Поэтому в Си справедливо равенство sizeof('a') == sizeof(int), а в Си++ — равенство sizeof('a') == sizeof(char).
• Некоторые новые возможности C99, в первую очередь, restrict, не включены в стандарт Cи++.
Си перенял от Си++ ряд особенностей:
• прототипы объявления функций;
• однострочные комментарии, начинающиеся на // и заканчивающиеся символом перевода строки;
• более сильную проверку типов, включая добавление типа void, спецификатора const и удаление принятия по умолчанию типа int в качестве возвращаемого значения.
• После утверждения нового стандарта C99 понятие совместимости со спецификациями представляется еще менее четким, чем ранее. Является ли обратная совместимость со спецификациями Си одним из необходимых условий дальнейшего совершенствования Си++? Если да, то что нужно сделать для того, чтобы минимизировать растущий разрыв между двумя этими языками?
Язык C99 нацелен на расширение низкоуровневых функций Си в области численного программирования. Он игнорирует концепцию абстрагирования и ориентацию на решение задач общего назначения, характерную для Си++. Это обеспечивает более тесную совместимость с Си и интеграцию элементов специального назначения там, где Си++ использует встроенные библиотеки, включающие в себя конструкции языка общего назначения. В качестве примера можно привести массивы переменной длины C99, реализованные в Си++ в виде векторов. Координированное развитие двух языков помогло бы избежать подобных расхождений.
Идеальным вариантом мне по-прежнему представляется единый язык, в котором рационально сочетались бы конструкции Си++ и C99. Думаю, такой язык смог бы удовлетворить любым разумным техническим потребностям. Однако я не уверен, что у заинтересованных сторон окажется достаточно воли для принятия столь ответственного решения. Для начала это потребует объединения комитетов по стандартизации Си и Си++; ведь поддерживать параллельное развитие двух языков силами различных групп людей невозможно. Большинство представителей одного комитета не разделяет идеи другого и не желает искать компромисса. В то время как внутри каждого из комитетов царят взаимопонимание, доверие и готовность идти на уступки, сосуществование сразу двух органов приводит к обострению разногласий и жесткому противодействию неудобным взглядам и мнениям. Я полагаю, что комитетам следует совместными усилиями разработать соглашение об объединении, а затем выбрать удобное время, чтобы претворить это в жизнь до момента обновления комитета ISO по стандартизации Си++. Таким образом, мы получим более качественный язык и более сплоченное сообщество.
• Выбор С в качестве базового языка для С++ объясняется следующими его достоинствами:
1. универсальность, краткость и относительно низкий уровень;
2. адекватность большинству задач системного программирования;
3. он идет в любой системе и на любой машине;
4. полностью подходит для программной среды UNIX.
В С существуют свои проблемы, но в языке, разрабатываемом "с нуля" они появились бы тоже, а проблемы С, по крайней мере, хорошо известны. Более важно то, что ориентация на С позволила использовать язык "С с классами" как полезный (хотя и не очень удобный) инструмент в течение первых месяцев раздумий о введении в С классов в стиле Симулы.
С++ стал использоваться шире, но по мере роста его возможностей, выходящих за пределы С, вновь и вновь возникала проблема совместимости. Ясно, что отказавшись от части наследства С, можно избежать некоторых проблем (см., например, [15]). Это не было сделано по следующим причинам:
1. существуют миллионы строк программ на С, которые можно улучшить с помощью С++, но при условии, что полной переписи их на язык С++ не потребуется;
2. существуют миллионы строк библиотечных функций и служебных программ на С, которые можно было бы использовать в С++ при условиях совместимости обоих языков на стадии связывания и их большого синтаксического сходства;
3. существуют сотни тысяч программистов, знающих С; им достаточно овладеть только новыми средствами С++ и не надо изучать основ языка;
4. поскольку С и С++ будут использоваться одними и теми же людьми на одних и тех же системах многие годы, различия между языками должны быть либо минимальными, либо максимальными, чтобы свести к минимуму количество ошибок и недоразумений. Описание С++ было переработано так, чтобы гарантировать, что любая допустимая в обоих языках конструкция означала в них одно и то же.
Язык С сам развивался в последние несколько лет, что отчасти было связано с разработкой С++ [14]. Стандарт ANSI для С [27] содержит, например, синтаксис описания функций, позаимствованный из языка "С с классами". Происходит взаимное заимствование, например, тип указателя void* был придуман для ANSI С, а впервые реализован в С++. Как было обещано в первом издании этой книги, описание С++ было доработано, чтобы исключить неоправданные расхождения. Теперь С++ более совместим с языком С, чем это было вначале ($.18). В идеале С++ должен максимально приближаться к ANSI C, но не более [9]. Стопроцентной совместимости никогда не было и не будет, поскольку это нарушит надежность типов и согласованность использования встроенных и пользовательских типов, а эти свойства всегда были одними из главных для С++.
Для изучения С++ не обязательно знать С. Программирование на С способствует усвоению приемов и даже трюков, которые при программировании на С++ становятся просто ненужными. Например, явное преобразование типа (приведение) , в С++ нужно гораздо реже, чем в С (см. "Замечания для программистов на С" ниже). Тем не менее, хорошие программы на языке С по сути являются программами на С++. Например, все программы из классического описания С [8] являются программами на С++. В процессе изучения С++ будет полезен опыт работы с любым языком со статическими типами.

В стандарте С99 появились новые для С встроенные типы данных. Здесь подробно рассказывается о каждом из них.

_Вооl

Один из новых типов данных, появившихся в С99, — это _Bool, в котором можно хранить значения 1 и 0 (истина (true) и ложь (false)). _Bool представляет собой целый тип данных. Как известно многим читателям, в языке C++ определяется ключевое слово bool, которое, несмотря на сходство, все же отличается от _Bool. Таким образом, в написании этого типа С99 и C++ несовместимы. Кроме того, в C++ определяются встроенные логические константы true и false, а в С99 этого не делается. Однако в С99 имеется заголовок <stdbool.h>, в котором определены имена макросов bool, true и false. Таким образом, можно легко создавать код, совместимый с C/C++.

Причина того, что в качестве ключевого слова указывается _Bool, а не bool, состоит в том, что во многих уже имеющихся С-программах определены их собственные варианты bool. Определяя логический тип как _Bool, C99 дает возможность не менять уже написанный код. Однако в новые программы лучше всего вставлять <stdbool.h>, а затем использовать имя макроса bool.

_Complex

Стандарт С99 появился вместе с новой для С поддержкой арифметических операций с комплексными числами; эта поддержка включает в себя ключевые слова _Complex, дополнительные заголовки и несколько новых библиотечных функций. Однако никаких реализаций не требуется, чтобы реализовать типы мнимых чисел, а автономные приложения (которые обходятся без операционной системы) не обязаны поддерживать комплексные типы. Арифметические операции с комплексными числами появились в С99 для упрощения программирования численных методов.

Определены следующие комплексные типы:

float_Complex

double_Complex

long double_Complex

Причина того, что в качестве ключевых слов определены _Complex , а не complex, состоит в том, что во многих имеющихся С-программах уже определены их собственные типы комплексных данных, использующие имена complex. Определяя ключевые слова _Complex и, C99 позволяет не менять уже написанный код. Заголовок <complex.h> определяет (кроме всего прочего) макросы complex, которые в результате макроподстановки превращаются в _Complex. Таким образом, в новые программы лучше всего вставлять <complex.h>, а затем использовать макросы complex. Комплексный тип данных зафиксирован в стандарте 99 языка Си : #include <complex.h> complex float x, y = 1.0 + 3.0 * I; Для комплексного типа определен набор обычных операций и библиотечных функций.

Типы целых данных long long

В стандарте С99 появились новые для С типы данных long long int и unsigned long long int. Диапазон значений типа данных long long int не уже, чем интервал от -(2^(63-1)) до (2^(63-1)). А диапазон значений типа данных unsigned long long int обязан содержать интервал от 0 до 2^(64-1). Типы long long позволяют поддерживать 64-разрядные целые значения с помощью встроенного типа.

Константное выражение – это выражение, содержащее только константы. Такие выражения могут вычисляться в ходе компиляции, а не выполнения программы, и соответственно употребляться в любом месте, где допускается применение одной константы:
#define MAXLINE 1000
char line[MAXLINE+1];
Ещё один пример:
#define LEAP 1 /* в високосных годах */
int days[31+28+LEAP+31+30+31+30+31+31+30+31+30+31];

С синтаксической точки зрения константное выражение - это выражение с ограниченным подмножеством операций. В ряде контекстов разрешаются выражения только эквивалентные константам: после меток case в операторе switch, при задании границ массивов и для битовых полей, в качестве значений перечеслимых констант, в инициализаторах, а также в некоторых выражениях директив препроцессора.
Константные выражения не могут содержать присваивания и декрментирования, вызовы функций и операции "запятая"; эти ограничения не распространяются на операнды операции sizeof. Если требуется целочисленное константное выражение, то его операнды должны состоять из целых, перечислимых, символьных и вещественных констант. Операции приведения должны преобразовывать велечины только к целочисленным типам, а любая вещественная константа должна явно приводится к целому типу. Из этого следует что в константном выражении не может быть массивов, операций обращения по указателю, взятия адреса и обращения к полям структуры. (Однако операция sizeof может иметь операнды любого вида.)
Для константных выражений в инициализаторах допускается большая свобода. Операндами могут быть константы любого типа, а к внешним или статическим объектам, а также к внешним и статическим массивам, индексируемым константными выражениями, можно применять одноместную операцию &. Она также может применяться неявно при использовании массива без индекса или функции без списка аргументов. Вычисление инициализирующего значения должно давать константу либо адрес ранее объявленного внешнего или статического объекта плюс-минус константа.
Меньшая свобода допускается для целочисленных константных выражений в директиве #if: не разрешаются выражения с sizeof, константы перечислимых типов и операции приведения типа.
Недесятичная запись целых констант.
Значение целого числа можно указывать в восьмеричной и шестнадцатеричной системе вместо десятичной. Если целая константа начинается с нуля (0), то она записана в восьмеричном представлении, а если с 0x или 0X – то в шестнадцатиричном. Например, десятичное число 31 можно записать как 037 в восьмеричной системе и 0x1f или 0X1F в шестнадцатеричной. В конце восьмеричных и шестнадцатеричных констант также можно ставить L для превращения их в длинные, а U – для лишения их знака. Так число 0XFUL является константой типа unsigned long с десятичным значением 15.

Восьмеричные и шестнадцатеричные формы записи достачно распространены. Восьмеричные удобно использовать, например, для задания прав доступа к файлам в операционных системах типа *nix или битовых полей. А шестнадцатеричные - для описания цветов (RGB - по 2 цифры на красный, зеленый и синий), в интернете такая форма встречается повсеместно.

Системно-зависимые константы: <limits.h>.
В заголовочном файле <limits.h> определяются константы, описывающие размеры целочисленных типов. Ниже приведены минимально допустимые величины, а в конкретных реализациях возможны значения больше указанных.
CHAR_BIT 8 Битов в char
SCHAR_MAX UCHAR_MAX или SCHAR_MAX Максимальное значение char
CHAR_MIN 0 или CHAR_MIN Минимальное значение char
INT_MAX +32767 Максимальное значение int
INT_MIN -32767 Минимальное значение int
LONG_MAX +2147463647 Максимальное значение long
LONG_MIN -2147463647 Минимальное значение long
SCHAR_MAX +127 Максимальное значение signed char
SCHAR_MIN -127 Минимальное значение signed char
SHRT_MAX +32767 Максимальное значение short
SHRT_MIN -32767 Минимальное значение short
UCHAR_MAX 255 Максимальное значение unsigned char
UINT_MAX 65535 Максимальное значение unsigned int
ULONG_MAX 4294967295 Максимальное значение unsigned long
USHRT_MAX 65535 Максимальное значение unsigned short

Наряду с <limits.h> существует заголовочный файл <float.h>. В нём определены подобные константы для использования в вещественной арифметике с плавающей точкой.

stdint.h
stdint.h - это заголовочный файл С и С++ впервые увидевший свет вместе со стандартной библиотекой С99. Его появление наконец-то позволило программистам использовать целые числа фиксированной длины не завися от настроек конкретной системы, что очевидно хорошо сказалось на переносимости и предсказуемости программ. Наиважнейшей сферой применения "стандартных целых чисел" стала работа с "железом", где, как правило, данные необходимо передавать в регистры фиксированных размеров, вписывать в специальные области памяти или же использовать их для задания точных смещений.
stdint.h объявляет системно-независимые типы, наименования которых строятся по следующему принципу, intN_t для целых чисел со знаком, uintN_t для целых чисел без знака. Например, int8_t и uint64_t среди прочих могут быть объявлены вместе, причем включая описание соответствующих диапазонов, от INT8_MIN до INT8_MAX и от 0 (нуля) до UINT64_MAX. Легко заметить что для диапазонов использованы те же имена, только написанные заглавными буквами. Помимо этого stdint.h описывает пределы целых типов, которые способны хранить указатели на объекты. Например, UINTPTR_MAX, чье значение зависит от процессора и его адресного пространства. Целые числа фиксированной длины и их соответствующие границы будут включены в заголовок только тогда, когда они существуют для данного конкретного компилятора и процессора.

Итак, что же на самом деле описывает <stdint.h>?
1. Целые типы фиксированной длины вида intN_t и uintN_t, где N=8,16,32 или 64. Причем если, скажем, N=64 не поддерживается - оно не будет включено в описание.
тип эквивалент знак бит байт минимальное значение максимальное значение
int8_t signed char Signed 8 1 −128 127
uint8_t unsigned char Unsigned 8 1 0 255
int16_t short Signed 16 2 −32,768 32,767
uint16_t unsigned short Unsigned 16 2 0 65,535
int32_t long Signed 32 4
uint32_t unsigned long Unsigned 32 4
int64_t long long Signed 64 8
uint64_t unsigned long long Unsigned 64 8

2. Наименьший возможный int тип. Пишется в виде int_leastN_t и uint_leastN_t. Для N 8, 16, 32, 64 соответственно. Единственное требование - чтобы ширина его была не меньше N.

INT_LEASTN_MIN
INT_LEASTN_MAX
UINT_LEASTN_MAX
INTN_C(value)
UINTN_C(value)

3. Быстрые целые типы минимальной длины (Fastest minimum-width integer types). Вид: int_fastN_t и uint_fastN_t.
Что такое "быстрые" в стандарте не сказано, единственное ограничение, длина не меньше N. Где N - 8, 16, 32, 64.

INT_FASTN_MIN INT_FASTN_MAX UINT_FASTN_MAX

4. Типы достаточно широкие для хранения указателей.
intptr_t uintptr_t

INTPTRN_MIN INTPTRN_MAX UINTPTRN_MAX

5. Целые типы наибольшей длины.
intmax_t uintmax_t

INTMAXN_MIN INTMAXN_MAX UINTMAXN_MAX
INTMAX_C(value) UINTMAX_C(value)

6. Другие целые границы.
PTRDIFF_MIN PTRDIFF_MAX
SIZE_MAX
WCHAR_MIN WCHAR_MAX
WINT_MIN WINT_MAX
SIG_ATOMIC_MIN SIG_ATOMIC_MAX

Сам заголовок добавляется в программу очень просто:
#include <stdint.h>
А вот небольшой пример описания типа из него же:
#ifndef INT32_MAX
# define INT32_MAX (0x7fffffffL)
#endif
#ifndef INT32_MIN
# define INT32_MIN INT32_C(0x80000000)
#endif
#ifndef int32_t
#if (LONG_MAX == INT32_MAX) || defined (S_SPLINT_S)
typedef signed long int32_t;
# define INT32_C(v) v ## L
# ifndef PRINTF_INT32_MODIFIER
# define PRINTF_INT32_MODIFIER "l"
# endif
#elif (INT_MAX == INT32_MAX)
typedef signed int int32_t;
# define INT32_C(v) v
# ifndef PRINTF_INT32_MODIFIER
# define PRINTF_INT32_MODIFIER ""
# endif
#elif (SHRT_MAX == INT32_MAX)
typedef signed short int32_t;
# define INT32_C(v) ((short) (v))
# ifndef PRINTF_INT32_MODIFIER
# define PRINTF_INT32_MODIFIER ""
# endif
#else
#error "Platform not supported"
#endif
#endif

Источники:
Б. Керниган, Д. Ритчи "Язык программирования ANSI C"
http://en.wikipedia.org/wiki/Stdint.h

Оператор sizeof позволяет выяснить, сколько байт занимает тот или иной тип. В качестве параметра он принимает или название типа, или переменную соответствующего типа.
<sizeof> ::= sizeof '(' (<имя типа> | <выражение>) ')'
Вот пример:

type mystuct {
uint a, b
byte c
}
...
sizeof( uint ) // = 4
sizeof( byte ) // = 1
sizeof( mystruct ) // = 9

Параметр может быть не только встроенным типом. Пример со структурой:

struct vector
{
float x;
float y;
};
void main()
{
vector s;
cout<<sizeof(s)<<"\n"; //Выведется 8.
}

Пример выведет 8, так как float занимает 4 байта и в нашей структуре 2 переменной типа float.

Операторы @=
1. *=
int a=2;
int b=3;
a*=b; // a=a*b
cout<<b; //выведет 3
cout<<a; // выведет 6
2. +=
Аналогично, т.е. a+=b идентично a=a+b
3. /=
Аналогично, т.е. a/=b идентично a=a/b
4. -=
Аналогично, т.е. a-=b идентично a=a-b
5. %=
Аналогично, т.е. a%=b идентично a=a%b

Операторы *, & и ->.
В языке С определены две операции для работы с указателями: * и &. Оператор & — это унарный оператор, возвращающий адрес своего операнда. (унарный оператор имеет один операнд). Например, оператор

m = &count;

присваивает переменной m адрес переменной count. Можно сказать, что адрес — это номер первого байта участка памяти, в котором хранится переменная. Адрес и значение переменной — это совершенно разные понятия. Оператор & можно представить себе как оператор, возвращающий адрес объекта. Следовательно, предыдущий пример можно прочесть так: "переменной m присваивается адрес переменной count".

Предположим, переменная count хранится в ячейке памяти под номером 2000, а ее значение равно 100. Тогда переменной m будет присвоено значение 2000.

Вторая операция для работы с указателями (ее знак, т.е. оператор, *) выполняет действие, обратное по отношению к &. Оператор * — это унарный оператор, возвращающий значение переменной, расположенной по указанному адресу. Например, если m содержит адрес переменной count, то оператор

q = *m;

присваивает переменной q значение переменной count. Таким образом, q получит значение 100, потому что по адресу 2000 расположена переменная count, которая имеет значение 100. Действие оператора * можно выразить словами "значение по адресу", тогда предыдущий оператор может быть прочитан так: "q получает значение переменной, расположенной по адресу m".

Оператор ->
struct bal
{
float balance;
char name[80];
} person;

struct bal *p; /* объявление указателя на структуру */

Чтобы с помощью указателя на структуру получить доступ к ее членам, необходимо использовать оператор стрелка ->. Вот, например, как можно сослаться на поле balance:

p->balance

Или проще говоря

tree->root; идентично
(*tree).root;

Операторы сдвига <<, >>

Операторы сдвига манипулируют битами. Они могут использоваться исключительно с примитивными, целыми типами. Оператор сдвига влево (<<) производит действия над операндом, расположенным слева от оператора, сдвигая влево на число бит, указанное после оператора (вставляя нули в биты младшего порядка). Оператор сдвига вправо с учетом знака (>>) производит действия над операндом, расположенным слева от оператора, сдвигая вправо на число бит, указанное после оператора. Сдвиг вправо с учетом знака >> использует знаковое дополнение: если значение положительное в биты старшего порядка вставляются нули; если значение отрицательное, в старшие биты вставляются единицы.
Если вы сдвигаете char, byte или short, это переводится в int перед сдвигом, а результат будет типа int. Будут использоваться только пять младших бит с правой стороны. Это предохранит вас от сдвига на большее число бит, чем есть в int. Если вы работаете с long, в результате вы получите long. Будут использоваться только шесть младших бит с правой стороны, так что вы не сможете сдвинуть на большее число бит, чем есть в long.

13_788, 18_788

Строковый тип (в программировании) — тип данных, значениями которого является произвольная последовательность символов алфавита. Каждая переменная такого типа может быть представлен фиксированным количеством байтов или иметь произвольную длину.
Представление в памяти
Некоторые языки программирования накладывают ограничения на максимальную длину строки, но в большинстве языков подобные ограничения отсутствуют.
Основные проблемы в машинном представлении строкового типа:
строки могут иметь достаточно существенный размер (до нескольких десятков мегабайтов);
изменяющийся со временем размер — возникают трудности с добавлением и удалением символов.
В представлении строк в памяти компьютера существует два принципиально разных подхода.
Представление массивом символов
В этом подходе строки представляются массивом символов; при этом размер массива хранится в отдельной (служебной) области. От названия языка Pascal, где этот метод был впервые реализован, данный метод получил название Pascal Strings.
Преимущества
программа в каждый момент времени «знает» о размере строки, и операции добавления символов в конец, копирования и получения размера строки выполняются достаточно быстро;
строка может содержать любые данные;
возможно на программном уровне следить за выходом за границы строки при её обработке;
возможно быстрое выполнение операции вида «взятие N-ого символа с конца строки».
Недостатки
проблемы с хранением и обработкой символов произвольной длины;
увеличение затрат на хранение строк — значение «длина строки» также занимает место и в случае большого количества строк маленького размера может существенно увеличить требования алгоритма к оперативной памяти;
ограничение максимального размера строки. В современных языках программирования это ограничение скорее теоретическое, так как обычно размер строки хранится в 32-битовом поле, что даёт максимальный размер строки в 2 147 483 647 байт (2 гигабайта).
Метод «завершающего байта»
Второй метод заключается в использовании «завершающего байта». Одно из возможных значений символов алфавита (как правило, это символ с кодом 0) выбирается в качестве признака конца строки, и строка хранится как последовательность байтов от начала до конца. Есть системы, в которых в качестве признака конца строки используется не символ 0, а байт 0xFF (255) или код символа «$».
Метод имеет три названия — ASCIIZ (символы в кодировке ASCII с нулевым завершающим байтом), C-strings (наибольшее распространение метод получил именно в языке Си) и метод нуль-терминированных строк.
Преимущества
отсутствие дополнительной служебной информации о строке (кроме завершающего байта);
возможность представления строки без создания отдельного типа данных;
отсутствие ограничения на максимальный размер строки;
экономное использование памяти;
простота получения суффикса строки;
возможность использовать алфавит с произвольным размером символа (например, UTF-8).
Недостатки
долгое выполнение операций получения длины и конкатенации строк;
отсутствие средств контроля за выходом за пределы строки, в случае повреждения завершающего байта возможность повреждения больших областей памяти, что может привести к непредсказуемым последствиям — потере данных, краху программы и даже всей системы;
невозможность использовать символ завершающего байта в качестве элемента строки.

Операции
Простейшие операции со строками:
получение символа по номеру позиции (индексу) — в большинстве языков это тривиальная операция;
конкатенация (соединение) строк.
получение подстроки по индексам начала и конца;
проверка вхождения одной строки в другую (поиск подстроки в строке);
проверка на совпадение строк (с учётом или без учёта регистра символов);
получение длины строки;
замена подстроки в строке.
Операции при трактовке строк как списков
свёртка;
отображение одного списка на другой;
фильтрация списка по критерию.

Наиболее часто используемые функции для работы со строками в Си.

Строковые функции языка Си находятся в специальной библиотеке: string.h. Это такие функции как:
strcpy()
strcat()
strcmp()

2.1. Вызов функции strcpy() имеет вид: strcpy(s1, s2).

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

2.2. Вызов функции strcat() имеет вид: strcat(s1, s2).

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

2.3. Вызов функции strcmp() имеет вид: strcmp(s1, s2).

Функция сравнивает строки s1 и s2 и возвращает значение 0, если строки равны. Что значит равенство строк? Это значит, что обе строки имеют одно и то же число одинаковых символов. Здесь происходит посимвольное сравнение кодов символов. При этом сравнение основано на использовании обычного лексикографического расположения символов. По алфавиту, например, как это делается при расположении слов в словаре. Код первого символа первой строки сравнивается с кодом первого символа второй строки, код второго символа первой строки сравнивается с кодом второго символа второй строки и так далее. Если символы, расположенные на одном и том же месте в двух строках равны, то сравниваются следующие символы и так далее. Если обычное лексикографическоев (как в словаре) сравнение показывает, что символ s1 больше символа s2, то функция возвращает положительное значение. В противном случае - возвращает отрицательное значение. Это будет означать, что символ s1 меньше символа s2.

2.4. Вызов функции strlen() имеет вид: strlen(s).

Функция возвращает длину строки s. Нулевой байт не прибавляется к длине строки. Например, если Вы обратитесь в функции strlen() с запросом: strlen("Krasnodar"), то данное обращение вернет Вам число 9. Хотя в массиве под эту величину отведено 10 байтов. Последний нулевой байт при определении длины строки не принимается во внимание. Рассмотрим в заключение применение этой функции для вычисления длины строки, вводимой с клавиатуры.

В версии C99 математическая библиотека была значительно пополнена; при этом число ее функций увеличилось более чем в три раза (стандарт C89 определял всего лишь 22 математические функции). Одной из основных целей комитета по версии C99 было повышение применимости языка C для численных расчетов. Теперь с уверенностью можно сказать, что эта цель достигнута! Для использования математических функций в программу необходимо включить заголовок . Помимо объявления математических функций, этот заголовок определяет один или несколько макросов. В версии C89 заголовком определяется только макрос HUGE_VAL, который представляет собой значение типа double, сигнализирующее о возникшем переполнении. В версии C99 кроме него определены следующие макросы.
HUGE_VALF версия макроса HUGE_VAL с типом float
HUGE_VALL версия макроса HUGE_VAL с типом long double
INFINITY Значение, представляющее бесконечность
math_errhandling содержит макросы MATH_ERRNO и\или MATH_ERREXCEPT
MATH_ERRNO Встроенная глобальная переменная errno,используемая для вывода сообщений об ошибках
MATH_ERREXCEPT Исключение, возбуждаемое при выполнении операций над вещественными числами, с целью вывода сообщений об ошибках
NAN не число
Ошибки в версиях C89 и C99 обрабатываются по-разному. Так, в версии C89, если аргумент математической функции не попадает в область определения, возвращается некоторое значение, зависящее от конкретной реализации, а встроенная глобальная целая переменная errno устанавливается равной значению EDOM. В версии C99 нарушение области определения также приводит к возврату значения, зависящего от конкретной реализации.
В версии C89, если функция генерирует результат, который слишком велик и потому не может быть представлен в машинном формате, то происходит переполнение. В этом случае функция возвращает значение HUGE_VAL. В версии C99 ошибка переполнения также приводит к тому, что функция возвращает значение HUGE_VAL, а при потере значимости – нуль.
В версии C89 аргументами математических функций должны быть значения типа double, причем значения, возвращаемые функциями, тоже имеют тип double. В версии C99 добавлены варианты этих функций, работающие с типами float и long double. В этих функциях используются суффиксы f и l соответственно. Например, в версии C89 функция sin() определена следующим образом.
___double sin(double arg);
Версия C99 поддерживает приведенное выше определение функции sin(), но в ней добавлены еще две ее модификации – sinf() и sinl().
___float sinf(float arg);
___long double sinl(long double arg);
Операции, выполняемые всеми тремя функциями, одинаковы; различаются лишь типы данных, над которыми выполняются эти операции. Добавление модификаций f и l математических функций позволяет использовать версию, которая наиболее точно соответствует данным, с которыми работают функции.
Поскольку в версии C99 добавлено так много новых функций, стоит отдельно перечислить те из них, которые поддерживаются версией C89. Это следующие функции.
___acos cos fmod modf tan asin cosh frexp pow tanh atan exp ldexp sin atan2 fabs log sinh ceil floor log10 sqrt
Семейство функций acos
Каждая функция семейства acos() возвращает значение арккосинуса от аргумента arg. Значение аргумента должно находиться в диапазоне от -1 до 1; в противном случае возникает ошибка из-за выхода за пределы области допустимых значений (ошибка из-за нарушения области определения).
Семейство функций acosh
Каждая функция семейства acosh() возвращает значение гиперболического арккосинуса от аргумента arg. Значение аргумента должно быть больше или равно нулю; в противном случае возникает ошибка из-за выхода за пределы области допустимых значений (ошибка из-за нарушения области определения).
Семейство функций asin
Каждая функция семейства asin() возвращает значение арксинуса от аргумента arg. Значение аргумента должно находиться в диапазоне от -1 до 1; в противном случае возникает ошибка из-за выхода за пределы области допустимых значений (ошибка из-за нарушения области определения).
Семейство функций asinh
Каждая функция семейства asinh() возвращает значение гиперболического арксинуса от аргумента arg.
Семейство функций atan
Каждая функция семейства atan() возвращает значение арктангенса от аргумента arg.
Семейство функций atanh
Каждая функция семейства atanh() возвращает значение гиперболического арктангенса от аргумента arg. Значение аргумента должно находиться в диапазоне от -1 до 1 (не включая границы); в противном случае возникает ошибка из-за выхода за пределы области допустимых значений (ошибка из-за нарушения области определения). Если arg равен 1 или -1, возможен выход за пределы допустимого диапазона.
Семейство функций atan2
Каждая функция семейства atan2() возвращает значение арктангенса отношения a/b. Для вычисления квадранта возвращаемого значения используются знаки аргументов функции.
Семейство функций cbrt
Каждая функция семейства cbrt() возвращает значение кубического корня от аргумента num.
Семейство функций ceil
Каждая функция семейства ceil() возвращает наименьшее целое (представленное в виде значения с плавающей точкой), которое больше значения аргумента num или равно ему. Например, если num равно 1.02, функция ceil() вернет значение 2.0, а при num, равном -1.02, – значение -1.
Семейство функций copysign
Каждая функция семейства copysign() наделяет аргумент val знаком, который имеет аргумент signval, и возвращает полученный результат. Таким образом, возвращаемое значение имеет величину, равную величине аргумента val, а его знак совпадает со знаком аргумента signval.
Семейство функций cos
Каждая функция семейства cos() возвращает значение косинуса аргумента arg. Значение аргумента должно быть выражено в радианах.
Семейство функций cosh
Каждая функция семейства cosh() возвращает значение гиперболического косинуса аргумента arg.
Семейство функций erf, erff, erfc, erfcf
erf вычисляет приближение к "функции ошибки" , которая оценивает вероятность того, что некое наблюдение окажется внутри рамок отклонения х от среднего значения на числовой оси (подразумевается нормальное вероятностное распределение)
erfc вычисляет дополнительную вероятность, т. е. erfc(x) = 1 - erf(x). функция erfc вычисляется непосредственно, поэтому используется для избежания потери точности, которая возникла бы при вычитании больших вероятностей (когда x велик) из 1.
erff и erfcf отличаются только типами входных данных и результатов.
exp, expf - экспонента
х exp и expf вычисляют значение экспоненты от х, e (где e - основание натуральной системы логарифмов, приблизительно равное 2.71828).
expm1, expm1f - экспонента минус 1
Результат остается точным даже для малых значениях х, в то время как использование exp(x)-1 вызвало бы потерю многих значащих цифр.
fabs, fabsf - абсолютное значение (модуль)
fabs и fabsf вычисляют ЁxЁ, абсолютное значение (модуль) от аргумента х. непосредственным обращением к битовому представлению аргумента.
Возвращается вычисленное значение. Никаких ошибок не возникает.
fmod, fmodf - остаток от деления в виде числа с плавающей точкой
fmod и fmodf вычисляют остаток от деления х/у в формате плавающей точки (х ( mod y)).
frexp,frexpf - разбиение числа с плавающей точкой
Все ненулевые нормализованные числа можно представить в виде m*(2**p) . frexp разбивает переменную типа double val на мантиссу m и степень двойки р. В результате мантисса всегда будет больше 0.5 и меньше чем 1.0 (поскольку val не ноль). Степень двойки хранится в переменной *exp.
gamma, gammaf, lgamma, lgammaf, gamma_r, gammaf_r, lgamma_r, lgammaf_r
gamma вычисляет ln(Г(х)), натуральный логарифм от гамма-функции от х. Гамма-функция (exp(gamma(x)) eсть обобщение факториала и использует то свойство, что Г(N) = N*Г(N-1). В соответствии с этим, значения гамма-функции растут очень быстро. gamma определяется как ln(Г(х)) а не как просто Г(х) для того чтобы расширить полезное поле представляемых результатов.
hypot, hypotf - расстояние от начала координат
hypot вычисляет евклидово расстояние sqrt( x**2 + y**2 ) между началом координат и точкой, представленной декартовыми координатами (х, y). hypotf отличается только типом аргументов и результата.
ilogb, ilogbf - получение показателя степени в представлении числа с плавающей точкой
Все ненулевые нормальные числа могут быть представлены в р виде m*2 . ilogb и ilogbf запрашивают аргумент val и возвращают число p. Функции frexp и frexpf подобны функциям ilogb и ilogbf, но помимо этого возвращают m.
infinity, infinityf - представление бесконечности
infinity и infinityf возвращают специальное значение, объявленное в IEEE двойной и единичнойной точности соответственно.
ldexp, ldexpf - задание показателя
ldexp вычисляет величину val*(p**exp). ldexpf аналогична с точностью до типов.
log, logf - натуральные логарифмы
Возвращают значение натурального логарифма от х, то есть логарифм по основанию e ( где e - основание натуральной системы логарифмов, 2.71828...). log и logf идентичны с точностью до типов входных и выходных данных
log10, log10f - логарифмы по основанию 10
modf, modff - разбиение на дробную и целую части
rint, rintf, remainder, remainderf - округление и остаток
rint и rintf возвращают свой аргумент, округленный до ближайшего целого. remainder и remainderf находят остаток от деления x/y; это будет число между -y/2 и y/2.
sqrt, sqrt - арифметический квадратный корень
qrt вычисляет арифметический (неотрицательный) квадратный корень из аргумента.

Версия библиотеки
Существуют четыре различных версии программ математических библиотек: IEEE, POSIX, X/Open, и SVID. Версия может быть выбрана Вами в период прогона программы заданием глобальной переменной _LIB_VERSION, определенной в 'math.h'. Она может принимать значение одной из следующих констант, определенных в 'math.h': _IEEE_, _POSIX_, _XOPEN_, или _SVID_. Переменная _LIB_VERSION не является специальной для каждой части программы, и изменение ее сказывается на всех частях.

Версии библиотеки различаются только по принципу обработки ошибок.

В режиме IEEE функция matherr не вызывается, не печатается сообщение об ошибке, и не задается значение переменной errno.
В режиме POSIX переменной errno присваивается необходимое значение, но функция matherr не вызывается, и не выводится сообщение об ошибке.
В режиме X/Open переменная errno принимает соответствующее значение, вызывается функция matherr, но сообщение об ошибке не выводится.
В режиме SVID функции, в случае переполнения, не принимают значение бесконечности, а становятся равными 3.40282346638528860e+38, максимально возможному одноразрядному числу с плавающей точкой. Также переменной errno присваивается правильное значение, вызывается функция matherr, и, если matherr обращается в 0, то для некоторых ошибок выводится соответствующее сообщение. Например, в ответ на 'log(-1.0)' печатается сообщение об ошибке в стандартном виде вывода: log: DOMAIN error. По умолчанию реализуется режим X/Open.

Функция это независимый набор объявлений и операторов, который обычно разрабатывается для выполнения конкретной задачи. Программы на языке С имеют по крайней мере одну функцию, main, и могут содержать и другие функции.
В определении функции задается ее имя, тип и число ее формальных параметров и приводятся объявления и операторы, которые задают ее действие. Эти объявления и операторы называются "телом функции". Кроме того, определение функции задает ее тип возвращаемого значения и ее класс хранения. Если возвращаемый тип и класс хранения не заданы явно, то по умолчанию они устанавливаются соответственно int и extern.
С помощью спецификатора класса хранения в определении функции можно задать класс хранения для функции extern или static. Если определение функции не содержит спецификатора класса хранения, то по умолчанию устанавливается класс хранения extern. Можно явно задать спецификатор класса хранения extern в определении функции, хотя это и не обязательно.

Функция с классом хранения static доступна только в том исходном файле, где она появляется. Все другие функции, явно или неявно определенные с классом хранения extern, доступны из всех исходных файлов, составляющих программу.

"Тело функции" это составной оператор, который состоит из операторов, задающих конкретное действие функции. Тело функции кроме того может содержать объявления переменных, которые используются этими операторами.
Все объявленные в теле функции переменные имеют класс хранения auto, если явно не задан другой класс. При вызове функции локальным переменным выделяется память и выполняется их локальная инициализация. Управление выполнением программы передается на первый оператор составного оператора и работа происходит до выполнения оператора return или прохода до конца тела функции. Затем управление возвращается на точку, из которой был произведен вызов функции.
Если функция должна возвращать значение, то должен быть выполнен оператор return, содержащий выражение. Если в операторе return нет выражения или оператор return не выполняется, то возвращаемое функцией значение не определено.
<тип> <имя_функции>(<тип> <имя_переменной>,<тип> <имя_переменной>…){
//тело функции
return возвращаемое_значение;
}
Вложенная функция - это функция, определенная внутри другой функции. Имя вложенной функции является локальным в блоке, где она определена. Например, здесь мы определяем вложенную функцию с именем square и вызываем ее дважды:
foo (double a, double b)
{
double square (double z) { return z * z; }

return square (a) + square (b);
}
Вложенная функция имеет доступ ко всем переменным объемлющей функции, которые видны в точке ее определения. Это называется "лексическая область действия". Например, ниже мы показываем вложенную функцию, которая использует наследуемую переменную с именем offset:
bar (int *array, int offset, int size)
{
int access (int *array, int index)
{ return array[index + offset]; }
int i;
...
for (i = 0; i < size; i++)
... access (array, i) ...
}
Определения вложенных функций разрешаются внутри функций, где допустимы определения переменных; то есть в любом блоке перед первым оператором в блоке.
Можно вызвать вложенную функцию из точки вне области действия ее имени, сохранив ее адрес или передав адрес в другую функцию:
hack (int *array, int size)
{
void store (int index, int value)
{ array[index] = value; }
intermediate (store, size);
}
Здесь функция intermediate получает адрес функции store в качестве параметра. Если intermediate вызывает store, аргумент, передаваемый в store, используется для записи в array. Но эта техника работает только до тех пор, пока объемлющая функция (в этом примере hack) не возвратит управление.
Если вы пытаетесь вызвать вложенную функцию с помощью ее адреса после того, как объемлющая функция возвратила управление, всеиспортиться. Если вы пытаетесь вызвать ее после того, как объемлющая область действия закончила работу, и если она ссылается на одну из переменных, которые больше не лежат в области действия, может вам и повезет, но неразумно рисковать. Однако, если вложенная функция не ссылается ни на что, вышедшее из области действия, вы в безопасности.
Если вам нужно объявить вложенную функцию до ее определения, используйте auto (который в противном случае бесполезен для объявлений функций).
bar (int *array, int offset, int size)
{
__label__ failure;
auto int access (int *, int);
...
int access (int *array, int index)
{
if (index > size)
goto failure;
return array[index + offset];
}
...
}
Пример рекурсивной функции:
int walk_Direct(Node node, int depth, int (*apply)(Node,int)){
apply(node,depth);
if (node!=NULL){
walk_Direct(node->left, depth+1,apply);
walk_Direct(node->right, depth+1,apply);
}
}
Каждый раз при рекурсивном вызове функции выделяется новая область памяти для формальных параметров и переменных auto и register, так что значения предыдущего, не законченного, вызова не перезаписываются. непосредственный доступ к параметрам имеется только в той функции, в которой они были созданы. Для обеспечения независимости функций нет прямого доступа к предыдущим параметрам.
Пример функции, кторая вызывает в качестве агргумента другую функцию:
int printTree(Tree tree, int(*walk)(Node, int, int(*apply)(Node,int))) {
assert(tree!=NULL);
walk(tree->root, 0, printNode);
}

При вызове функции с переменным числом аргументов нужно в вызове функции просто задать произвольное число аргументов. Если есть объявление прототипа функции, то переменное число аргументов может быть задано помещением запятой с многоточием (,...) в конце списка формальных параметров или списка типов аргументов Вызов функции должен включать один аргумент для каждого имени типа, объявленного в списке формальных параметров или списке типов аргументов.
Аналогично, список формальных параметров в определении функции может заканчиваться запятой с многоточием для индикации переменного числа аргументов.
Все заданные в вызове функции аргументы помещаются в стек. Число объявленных для функции формальных параметров определяет число аргументов, которые будут взяты из стека и присвоены формальным параметрам. Пользователь сам отвечает за поиск любых дополнительных аргументов в стеке и за определения количества заданных аргументов.
Конструирование Вызовов Функций
Используя встроенные функции, описанные ниже, вы можете записать полученные аргументы функции и вызвать другую функцию с теми же аргументами, не зная количество и типы аргументов.
Вы можете также записать возвращаемое значение этого вызова функции и позже вернуть это значение, не зная, какой тип данных функция пыталась вернуть (если вызывавшая функция ожидает этот тип данных).
__builtin_apply_args ()
Эта встроенная функция возвращает указатель типа void * на данные, описывающие, как выполнять вызов с теми же аргументами, которые были переданы текущей функции.
Функция сохраняет регистр указателя аргументов, адреса структурного значения и все регистры, которые могут быть использованы для передачи аргументов в функцию в блок памяти, выделяемый на стеке. Затем она возвращает адрес этого блока.
__builtin_apply (функция, аргументы, размер)
Эта встроенная функция вызывает 'функцию' (типа void (*)()) с копированием параметров, описываемых 'аргументами' (типа void *) и 'размером' (типа int).
Значение 'аргументы' должно быть значением, которое возвращено __builtin_apply_args (). Аргумент 'размер' указывает размер стековых данных параметров в байтах.
Эта функция возвращает указатель типа void * на данные, описывающие, как возвращать какое-либо значение, которое вернула 'функция'. Данные сохраняются в блоке памяти, выделенном на стеке.
Не всегда просто вычислить подходящее значение для 'размера'. Это значение используется __builtin_apply () для вычисления количества данных, которые должны быть положены на стек и скопированы из области входных аргументов.
__builtin_return (результат)
Эта встроенная функция возвращает значение, описанное 'результатом' из объемлющей функции. Вы должны указать в качестве 'результата' значение, возвращенное __builtin_apply ().

Именование Типа Выражения

Вы можете дать имя типу выражения, используя объявление typedef с инициализатором. Ниже показано, как определить имя как имя типа выражения:
typedef struct
{
char Name[20];
char Surname[20];
char age[3];
char trip[20];
char number_of_train[10];
char type[10];
char seat[3];
char tickets_number[7];
char passport[10];
int quantity_of_things;
int number;
} Passenger;

Для создания новых наименований типов для уже существующих типов данных используйте описание typedef. Применение описаний typedef может сделать программы более мобильными и надежными.
Определяемый тип может обозначать тип операции, разрешенной с данной переменной (например, логической операции). Испольщуйте ключевое слово typedef для защиты ваших программ в проблемах переносимости. Применяйте описание typedef для тех типов данных, которые являются машинно-зависимыми. Тогда, при перемещении программы будут требовать изменения только описание typedef. Наконец, typedef можно использовать для лучшего документирования вашей программы. Например, тип данных "employee" (служащий) легче понять, чем что-то описанное в виде сложной структуры.
Пример переименования:
typedef int bool;
typedef char *string;
typedef struct STree *Tree;
typedef struct SNode *Node;
Ниже показано, как определить имя как имя типа выражения:
typedef имя = выражение;

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

Общий вид объявления структуры такой:

struct тег{
тип имя-члена;
тип имя-члена;
тип имя-члена;
...
...
} переменные-структуры;

Причем тег или переменные-структуры могут быть пропущены, но только не оба одновременно.

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

Членами структур могут являться как масивы так и структуры(вложенные структуры)

Немного про С99))

В этом стандарте есть возможность в качестве последнего члена структуры объявить массив без размера(массив с переменными границами). При этом в структуре перед гибким массивом должен стоять как минимум еще один член.

Пример:

struct mystruct{
int a;
int b;
float fa[]; // массив с переменными границами
}

выделение памяти:

struct mystruct *p;
p = (struct mystruct *) malloc(sizeof(struct mystruct) +10 * sizeof(float));

Здесь 10 * sizeof(float); дополнительно выделяется место для размещения массива из 10 элементов типа float.

Также в С99 появилась новая возможность для С - назначенные инициализаторы. Инициализаторы бывают:
инициализаторы для массива;
инициализоторы для структур и объединений;

для структур используют инициализаторы вида:
.имя-члена

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

Ваша программа должна включать стандартный I/O заголовочный файл, а имено строку:
#include
Сообщения об ошибках
Часто бывает удобно и полезно сообщать об ошибках при выполнении C-программы. Стандартная библиотечная функция perror() позволяет это делать. Она используетя совместно с errno. Часто при возникновении ошибки необходимо прекратить работу программы. Для этого используют функцию exit().
perror()
void perror(const char *message);
perror() выводит сообщение (в стандартный поток ошибок), затем описание последней случившейся ошибки (на основании errno) (см. ниже), произошедшей при обращении к системной или библиотечной функции. Аргумент строка message печатается сначала, потом двоеточие и пробел, потом сообщение и перевод строки. Если message is указатель NULL или указывает на строку нулевой длины, то двоеточие не печатается.
Потоки
Потоки представляют собой удобный переносимый способ чтении и записи данных. Они обеспечивают гибкие и эффективные средства для I/O.
Существует внутренняя C-структура данных FILE, которая используется для работы с потоками и определена в stdio.h. При вводе/выводе посредством потоков необходимо использовать эту структуру FILE.
Необходимо обявить переменную или указатель этого типа в нашей программе.
Мы должны сначала открыть поток перед выполнение каких-либо операций I/O,
затем выполнить эти операции доступа (чтения/записи)
и потом закрыть.
В UNIX заданы 3 предопределенныч потока (в stdio.h):
stdin (стандартный поток ввода), stdout (стандартный поток вывода), stderr (стандартный поток ошибок)
printf
int printf(char *format, arg list ...) --
выводит в стандартный поток вывода stdout список аргументов согласно специальной форматной строке. Возвращает число напечатанных символов.
scanf
int scanf(char *format, args....) -- читает из stdin и кладет прочитанные данные по адресам, указанным в списке args. Возращает число прочитанных данных.
Форматная строка подобна строке для printf
В scanf необходимо передавать адрес переменной или указатель на нее.
scanf("%d",&i);
Мы можем передать также имя массива или строки, т.к, это и будет адресом начала массива или строки.
char string[80];
scanf("%s",string);
Файлы
Сначала открываем файл. Функция fopen() выполняет это:
FILE *fopen(char *name, char *mode)
fopen возвращает указатель на структуру FILE. Строка name содержит имя файла. Строка mode определяет способ доступа. Если файл не может быть открыт по какой-либо причине, функция возвращает NULL.
Способы доступа включают:
"r" -- чтение,
"w" -- запись,
"a" -- добавление в конец.
Также способ доступа может включать:
"t" - текстовый,
"b" - бинарный.
Чтение и запись файлов
Функции fprintf и fscanf часто используются для доступа к файлам.
int fprintf(FILE *stream, char *format, args..)
int fscanf(FILE *stream, char *format, args..)
Они сходны с printf и scanf за исключением того, что данные читаются и пишутся в поток stream, который должен быть открыт при помощи fopen().
Другие функции для файлов
int getc(FILE *stream), int fgetc(FILE *stream)
int putc(char ch, FILE *s), int fputc(char ch, FILE *s)
Они подобны getchar, putchar.
fflush(FILE *stream) -- очищает буфер потока.
fclose(FILE *stream) -- закрывает поток.
sprintf и sscanf
Эти функции подобны fprintf и fscanf, только пишут и читают не в поток/из поток, а в строку/из строки.
int sprintf(char *string, char *format, args..)
int sscanf(char *string, char *format, args..)
Определение статуса потока
Есть несколько функций, позволяющих определить статус потока:
int feof(FILE *stream);
int ferror(FILE *stream);
void clearerr(FILE *stream);
int fileno(FILE *stream);
feof()
-- Возвращает не ноль, если достигнут конец потока. Конец потока считается достигнут, если выставлен соответствующий флаг в структуре FILE. Этот флаг выставляется при попытке прочитать данные, а данные потока(файла) закончились.
ferror()
-- возвращает не ноль, если была ошибка при работе с потоком.
clearerr()
-- опускает флаг ошибки и флаг достижения конца файла.
fileno()
-- возвращает номер файлового дескриптора, связанного с потоком.
Файловые дескрипторы для стандартных потоков stdin, stdout, stderr равны 0, 1, 2 соответственно. Файловый дескриптор - это номер строки в таблице файловых дескрипторов, каждая строка которой содержит адрес структуры, описывающей I/O в какой-либо файл.
Низкоуровневый I/O
Этот вид I/O не буферизуется -- каждый запрос на чтение/запись реализуется путем обращения к диску (устройству) напрямую и происходит чтение/запись указанного количества байтов.
Здесь не предусматривается форматирования. Такой вид I/O удобен при передаче больших объемов данных.
Мы используем бинарные, а не текстовые, файлы.
Для открытия файла:
int open(char *filename, int flag, int perms) -- возвращает файловый дескриптор или -1 в случае неудачи.
Функция: creat(char *filename, int perms) также может быть использована для создания файлов.
int close(int handle) -- закрывает файловый дескриптор
int read(int handle, char *buffer, unsigned length)
int write(int handle, char *buffer, unsigned length)
используется для чтения/записи указанного количества байтов через дескриптор в участок памяти/из участка памяти, определенный указателем buffer. Возвращает число прочитанных/записанных байтов или -1, если произошла ошибка.

Логические переменные и выражения
Логические переменные принимают два значения: истина и ложь. Логические, или условные, выражения используются в качестве условия в конструкциях ветвления "если ... то ... иначе ... конец если" и цикла "пока". В первом случае в зависимости от истинности условия выполняется либо ветвь программы после ключевого слова "то", либо после "иначе"; во втором случае цикл выполняется до тех пор, пока условие продолжает оставаться истинным.
В качестве элементарных условных выражений используются операции сравнения: можно проверить равенство двух выражений или определить, какое из них больше. Любая операция сравнения имеет два аргумента и вырабатывает логическое значение "истина" или "ложь. В языке Си приняты следующие обозначения операции сравнения:
• операция проверки равенства двух выражений обозначается двойным знаком равенства == (мы не используем обычный знак равенства во избежание путаницы, поскольку часто знак равенства применяется для обозначения операции присваивания);
• неравенство обозначается != (в Си восклицательный знак используется для отрицания);
• для сравнения величин выражений применяются четыре операции больше >, больше или равно `>=, меньше <, меньше или равно <=.
Несколько примеров логических выражений:
x == 0 - выражение истинно, если значение переменной x равно нулю, и ложно в противном случае;
0!= 0 - выражение ложно;
3>= 2 - выражение истинно.
Из элементарных логических выражений и логических переменных можно составлять более сложные выражения, используя три логические операции "и", "или", "не":
1. результат логической операции "и" истинен, когда истинны оба ее аргумента. Например, логическое выражение
2. 0 <= x и x <= 1
истинно, когда значение переменной x принадлежит отрезку [0, 1]. Логическую операцию "и" называют также логическим умножением или конъюнкцией; в языке Си логическое умножение обозначается двойным амперсандом &&;
3. результат логической операции "или" истинен, когда истинен хотя бы один из ее аргументов. Например, логическое выражение
4. x != 0 или y != 0
ложно в том и только том случае, когда значения обеих переменных x и y равны нулю. Логическую операцию "или" называют также логическим сложением или дизъюнкцией; в Си логическое сложение обозначается двойной вертикальной чертой ||;
5. в отличие от логических операций "и" и "или", логическая операция "не" имеет только один аргумент. Ее результат истинен, когда аргумент ложен, и, наоборот, ложен, когда аргумент истинен. Например, логическое выражение
6. не x == 0
истинно, когда значение переменной x отлично от нуля. Логическая операция "не" называется логическим отрицанием (иногда негацией); в Си логическое отрицание обозначается восклицательным знаком "!".
В сложных логических выражениях можно использовать круглые скобки для указания порядка операций. При отсутствии скобок считается, что наивысший приоритет имеет логическое отрицание; затем идет логическое умножение, а низший приоритет у логического сложения.
Обратим внимание на чрезвычайно важную особенность операций реализации логического сложения и умножения - так называемое сокращенное вычисление результата. А именно, в случае логического умножения всегда сначала вычисляется значение первого аргумента. Если оно ложно, то значение выражения полагается ложным, а второй аргумент не вычисляется вообще! Благодаря этой особенности можно корректно использовать выражения вроде
x != 0 и y/x > 1
При вычислении значения этого выражения сначала вычисляется первый аргумент конъюнкции "x != 0". Если значение переменной x равно нулю, то первый аргумент ложен и значение второго аргумента "y/x > 1" уже не вычисляется. Это очень хорошо, поскольку при попытке его вычислить произошло бы аппаратное прерывание из-за деления на ноль.
То же самое относится и к логическому сложению. Сначала всегда вычисляется первый аргумент логической операции "или". Если он истинен, то значение выражения полагается истинным, а второй аргумент не вычисляется вообще. Таким образом, операции логического сложения и умножения, строго говоря, не коммутативны. Может так случиться, что выражение "a и b" корректно, а выражение "b и a" - нет. Программисты очень часто сознательно используют эту особенность реализации логических операций.

FIRST ARTICLE
Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера.

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

Если для обработки таких данных не использовать внешнюю память (файлы), то разумно расположить их в динамической памяти. Во-первых, динамическая память позволяет хранить больший объем информации, чем статическая. А во-вторых, в динамической памяти эти числа можно организовать в связанный список, который не требует предварительного указания количества чисел, подобно массиву.
Согласно определению, список располагается в динамически распределяемой памяти, в статической памяти хранится лишь указатель на заглавное звено. Структура, в отличие от массива, является действительно динамической: звенья создаются и удаляются по мере необходимости, в процессе выполнения программы.

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

Type U = ^Zveno;
Zveno = Record Inf : BT; Next: U End;
Здесь BT — некоторый базовый тип элементов списка.

Если указатель ссылается только на следующее звено списка (как показано в объявленной выше структуре), то такой список называют однонаправленным, если на следующее и предыдущее звенья — двунаправленным списком. Если указатель в последнем звене установлен не в Nil, а ссылается на заглавное звено списка, то такой список называется кольцевым. Кольцевыми могут быть и однонаправленные, и двунаправленные списки.

Более подробно рассмотрим работу со связанными списками на примере однонаправленного некольцевого списка.

Выделим типовые операции над списками:

* добавление звена в начало списка;
* удаление звена из начала списка;
* добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан);
* удаление звена из произвольного места списка, отличного от начала (например, после звена, указатель на которое задан);
* проверка, пуст ли список;
* очистка списка;
* печать списка.

SECOND ARTICLE
Организация списков в динамической памяти

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

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

Алгоритм создания списка в прямом направлении:

1. Создать первый элемент nach.
Ввести nach^.d; pred:=nach;

2. Создать текущий элемент tek.
Ввести tek^.d;
Установить связь предыдущего с текущим: pred^.link:=tek;
текущий элемент становится предыдущим: pred:=tek;

3. Если не конец списка, то перейти на 2.
Обнулить адресную часть последнего элемента: tek^.link:=nil.

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

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

tek:=nach;{Встали на начало списка}
while tek<>nil do
begin
wtiteln(tek^.d);{Вывести информационную часть}
tek:=tek^.link; {Шаг по связи}
end;

Рассмотрим еще раз строку tek:=tek^.link; . Ее можно интерпретировать по-другому: значению адреса tek присвоить то, что хранится в адресной части элемента tek, а там хранится адрес элемента, следующего за tek. Вообще нотацию tek^.link следует различать в контексте ее нахождения: если она стоит слева от присваивания, имеется ввиду сама адресная часть элемента tek, а если справа от присваивания – то, что хранится в адресной части tek. Таким образом, например, tek^.link:=tek^.link будет означать: в адресную часть tek занести адрес элемента, следующего за tek.

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

Алгоритм добавления элемента в начало списка:

1. Создать новый элемент nov.
Ввести информационную часть nov^.d.

2. Построить связь: nov^.link:=nach.

3. Новый элемент сделать начальным: nach=nov.

Нетрудно удалить первый элемент (nach:=nach^.link). Главное - не забыть физически удалить его из памяти (процедура Dispose).

Добавление элемента в середину списка: пусть переменная tek указывает на элемент, после которого необходимо вставить в список элемент nov. Сначала нужно заполнить связь у элемента nov: nov^.link:=tek^.link; затем соединить tek и nov: tek^.link:=nov.

Добавление элемента в конец списка. Пусть переменная pos указывает на последний элемент списка, nov – добавляемый элемент. Тогда операция pos^.link:=nov соединяет элементы; присваивание nov^.link:=nil обнуляет адресную часть нового элемента.

Удаление элемента из середины списка. Пусть переменная pred - элемент, предшествующий удаляемому элементу. Необходимо идти по ссылке, хранящейся в pred в поле link (адрес удаляемого элемента), затем идти по ссылке link удаляемого элемента (а это адрес следующего за удаляемым). Полученное значение записать в поле link элемента pred: pred^.link:=pred^.link^.link.

Исключение последнего элемента. Пусть pos - последний элемент, pred– предыдущий перед последним. Тогда присваивание pred^.link:=nil исключит последний элемент из цепи .

THIRD ARTICLE

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

Существует два основных способа построения односвязного списка. Первый способ — помещать новые элементы в конец списка[1]. Второй — вставлять элементы в определенные позиции списка, например, в порядке возрастания. От способа построения списка зависит алгоритм функции добавления элемента. Давайте начнем с более простого способа создания списка путем помещения элементов в конец.

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

struct address {
char name[40];
char street[40];
char city[20];
char state[3];
char zip[11];
struct address *next; /* ссылка на следующий адрес */
} info;

Приведенная ниже функция slstore() создает односвязный список путем помещения каждого очередного элемента в конец списка. В качестве параметров ей передаются указатель на структуру типа address, содержащую новую запись, и указатель на последний элемент списка. Если список пуст, указатель на последний элемент должен быть равен нулю.

void slstore(struct address *i,
struct address **last)
{
if(!*last) *last = i; /* первый элемент в списке */
else (*last)->next = i;
i->next = NULL;
*last = i;
}

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

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

Следует помнить, что при вставке элемента в начало (первую позицию) списка необходимо также изменить адрес входа в список где-то в другом месте программы. Чтобы избежать этих сложностей, можно в качестве первого элемента списка хранить служебный сторожевой элемент[2]. В случае упорядоченного списка необходимо выбрать некоторое специальное значение, которое всегда будет первым в списке, чтобы начальный элемент оставался неизменным. Недостатком данного метода является довольно большой расход памяти на хранение сторожевого элемента, но обычно это не столь важно.

Следующая функция, sls_store(), вставляет структуры типа address в список рассылки, упорядочивая его по возрастанию значений в поле name. Функция принимает указатели на указатели на первый и последний элементы списка, а также указатель на вставляемый элемент. Поскольку первый или последний элементы списка могут измениться, функция sls_store() при необходимости автоматически обновляет указатели на начало и конец списка. При первом вызове данной функции указатели first и last должны быть равны нулю.

/* Вставка в упорядоченный односвязный список. */
void sls_store(struct address *i, /* новый элемент */
struct address **start, /* начало списка */
struct address **last) /* конец списка */
{
struct address *old, *p;

p = *start;

if(!*last) { /* первый элемент в списке */
i->next = NULL;
*last = i;
*start = i;
return;
}

old = NULL;
while(p) {
if(strcmp(p->name, i->name)<0) {
old = p;
p = p->next;
}
else {
if(old) { /* вставка в середину */
old->next = i;
i->next = p;
return;
}
i->next = p; /* вставка в начало */
*start = i;
return;
}
}
(*last)->next = i; /* вставка в конец */
i->next = NULL;
*last = i;
}

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

void display(struct address *start)
{
while(start) {
printf("%s\n", start->name);
start = start->next;
}
}

При вызове функции display() параметр start должен быть указателем на первую структуру в списке. После этого функция переходит к следующему элементу, на который указывает указатель в поле next. Процесс прекращается, когда next равно нулю.

Для получения элемента из списка нужно просто пройти по цепочке ссылок. Ниже приведен пример функции поиска по содержимому поля name:

struct address *search(struct address *start, char *n)
{
while(start) {
if(!strcmp(n, start->name)) return start;
start = start->next;
}
return NULL; /* подходящий элемент не найден */
}

Поскольку функция search() возвращает указатель на элемент списка, содержащий искомое имя, возвращаемый тип описан как указатель на структуру address. При отсутствии в списке подходящих элементов возвращается нуль (NULL).

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

Ниже приведена функция, удаляющая заданный элемент из списка структур address.

void sldelete(
struct address *p, /* предыдущий элемент */
struct address *i, /* удаляемый элемент */
struct address **start, /* начало списка */
struct address **last) /* конец списка */
{
if(p) p->next = i->next;
else *start = i->next;

if(i==*last && p) *last = p;
}

Функции sldelete() необходимо передавать указатели на удаляемый элемент, предшествующий удаляемому, а также на первый и последний элементы. При удалении первого элемента указатель на предшествующий элемент должен быть равен нулю (NULL). Данная функция автоматически обновляет указатели start и last, если один из них ссылается на удаляемый элемент.

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

FOURTH ARTICLE

Двусвязные списки

Двусвязный список состоит из элементов данных, каждый из которых содержит ссылки как на следующий, так и на предыдущий элементы.

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

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

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

struct address {
char name[40];
char street[40] ;
char city[20];
char state[3];
char zip[11];
struct address *next;
struct address *prior;
} info;

Следующая функция, dlstore(), создает двусвязный список, используя структуру address в качестве базового типа данных:

void dlstore(struct address *i, struct address **last)
{

if(!*last) *last = i; /* вставка первого элемента */
else (*last)->next = i;
i->next = NULL;
i->prior = *last;
*last = i;
}

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

Подобно односвязным, двусвязные списки можно создавать с помощью функции, которая будет помещать элементы в определенные позиции, а не только в конец списка. Показанная ниже функция dls_store() создает список, упорядочивая его по возрастанию имен:

/* Создание упорядоченного двусвязного списка. */
void dls_store(
struct address *i, /* новый элемент */
struct address **start, /* первый элемент в списке */
struct address **last /* последний элемент в списке */
)
{
struct address *old, *p;

if(*last==NULL) { /* первый элемент в списке */
i->next = NULL;
i->prior = NULL;
*last = i;
*start = i;
return;
}

p = *start; /* начать с начала списка */

old = NULL;
while(p) {
if(strcmp(p->name, i->name)<0){
old = p;
p = p->next;
}
else {
if(p->prior) {
p->prior->next = i;
i->next = p;
i->prior = p->prior;
p->prior = i;
return;
}
i->next = p; /* новый первый элемент */
i->prior = NULL;
p->prior = i;
*start = i;
return;
}
}
old->next = i; /* вставка в конец */
i->next = NULL;
i->prior = old;
*last = i;
}

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

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

При удалении элемента двусвязного списка могут возникнуть три случая: удаление первого элемента, удаление элемента из середины и удаление последнего элемента. На рис. 22.7 показано, как при этом изменяются ссылки. Показанная ниже функция dldelete() удаляет элемент двусвязного списка:

void dldelete(
struct address *i, /* удаляемый элемент */
struct address **start, /* первый элемент */
struct address **last) /* последний элемент */
{
if(i->prior) i->prior->next = i->next;
else { /* new first item */
*start = i->next;
if(start) start->prior = NULL;
}

if(i->next) i->next->prior = i->prior;
else /* удаление последнего элемента */
*last = i->prior;
}

Поскольку первый или последний элементы списка могут быть удалены, функция dldelete() автоматически обновляет указатели на начало и конец списка посредством параметров start и last. При вызове ей передаются указатель на удаляемый элемент и указатели на указатели на начало и конец списка.

done by:
13_788
edited by
18_788

Библиотечные средства обработки списков в С++
Контейнерные классы в С++ – это классы предназначенные для хранения данных, организованных определенным образом. К этим классам, в частности, относятся массивы, стеки и списки. Для каждого типа контейнера определены методы для работы с его элементами, не зависящие от конкретного типа данных, поэтому один и тот же тип контейнера можно использовать для хранения данных различных типов. Эта возможность реализована с помощью стандартной библиотекой шаблонов (STL – Standart Template Library), части С++, куда входят контейнерные классы, алгоритмы и итераторы.
Использование контейнеров позволяет значительно повысить надежность программ, их переносимость и универсальность, а также уменьшить сроки их разработки.
Естественно, эти преимущества не даются даром: универсальность и безопасность использования контейнерных классов не могут не отражаться на быстродействии программы. Снижение быстродействия в зависимости от реализации компилятора может быть весьма значительным. Кроме того, для эффективного использования контейнеров требуется затратить значитильные усилия на вдумчивое освоение библиотеки.
Преимущества списков в целом:
1. Эффективная вставка и удаление элементов по всему списку (фиксированное время).
2. Эффективное перемещение элементов внутри списка или между ними (фиксированное время).
3. Перемещение между элементами назад-вперед (время изменяется линейно).
По сравнению с другими типами контейнеров списки лучше приспособлены к вставке, удалению и перемещению элементов. То есть, в частности, к сортировке.
Однако, ссылки назад-вперед заполняют память, а отсутствие индексов замедляет доступ к данным.
Реализация.
Класс list в STL реализован в виде простого двунаправленного списка, с указателями на предыдущий и следующий элементы. Класс же следит за хранением списка в памяти, сжимая или расширяя его в соответствии с выполняемым действием. Для задания списка на С++ нужно два параметра.
Объявление шаблона:
template < class T, class Allocator = allocator<T> > class list;

Где Т – тип элемента, а Allocator (необязательный параметр) – объект отвечающий за выделение памяти. По умолчанию используется шаблон класса allocator, который универсален и работает по простейшему алгоритму.
Пример объявления списков в коде программы:
#include <list>
list<int> first; // пустой список int-ов;
list<int> second (4,100); // в списке 4 элемента со значением 100;
list<int> third (second.begin(),second.end()); //пробегает от second.begin до second.end и записывает полученные значения в список (элемент second.begin записывается, а second.end уже нет);
list<int> fourth (third); // копирует список third в fourth.

Пример задания списка из массива:
int myints[] = {16,2,77,29};
list<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

Публичные функции класса(Public member functions):
(constructor) Создает список;
(destructor) Удаляет список;
operator= Копирует список (определяет оператор =, например, third=fifth, в этом случае список third удаляется, потом в него копируется содержимое списка fifth. При этом они оба становятся одинаковой длины, но хранятся в памяти отдельно, т.е. third не ссылается на fifth);

Итераторы (iterator и reverse_iterator – типы, определены внутри класса):
begin Устанавливает итератор на начало списка;
end Устанавливает итератор на конец списка;
rbegin Устанавливает реверсный итератор на реверсное начало (то есть итератор, просматривающий список с конца на конец списка);
rend Устанавливает реверсный итератор на реверсный конец (то есть итератор, просматривающий список с конца на начало списка);

Память:
empty Проверяет список на пустоту;
size Возвращает размер списка;
max_size Возвращает максимально достижимый размер списка судя по оставшейся памяти и библиотечным ограничениям (если такие есть);
resize Меняет размер;

Доступ к значению:
front К значению первого элемента (именно к значению, как к обычной переменной);
back К значению последнего элемента;

Модификаторы:
assign Присваивает новые значения списку (удаляя старые). Работает как конструктор;
push_front Вставить элемент вначало;
pop_front Удалить первый элемент;
push_back Вставить элемент в конец;
pop_back Удалить первый элемент с конца;
insert Вставляет значения в список перед итератором, не меняет созданные до этого ссылки и итераторы;
erase Удаляет элемент или их последовательность, границы задаются итераторами;
swap Меняет списки местами (все итераторы и ссылки остаются верными);
clear Полностью очищает список;

Операции:
splice Перемещает элементы из списка в список на место перед заданным итератором;
remove Удаляет элементы с определенным значением;
remove_if Удаляет элементы при выполнении некоего условия;
unique Из последовательности одинаковых, идущих подряд элементов оставляет только первый;
merge Совмещает отсортированные списки, ставя элементы так, чтобы сохранить порядок от меньшего к большему, и освобождает «донора»;
sort Сортирует список (от меньшего к большему);
reverse Зеркально меняет порядок всех элементов (все ссылки и итераторы остаются верными);

Allocator:
get_allocator Вытаскивает функцию аллокатор на свет божий (с её помощью можно выделить память под то, что нам хочется).

Код.
По итераторам:
#include <iostream>
#include <list>
using namespace std;

int main ()
{
int myints[] = {75,23,65,42,13};
list<int> mylist (myints,myints+5);

list<int>::iterator it;

cout << "mylist contains:";
for ( it=mylist.begin() ; it != mylist.end(); it++ )
cout << " " << *it;

cout << endl;

return 0;
}

Output:
mylist contains: 75 23 65 42 13

Доступ к элементам:
#include <iostream>
#include <list>
using namespace std;

int main ()
{
list<int> mylist;

mylist.push_back(77);
mylist.push_back(16);

// now front equals 77, and back 16

mylist.front() -= mylist.back();

cout << "mylist.front() is now " << mylist.front() << endl;

return 0;
}

Output:
mylist.front() is now 61

Модификаторы:
#include <iostream>
#include <list>
using namespace std;

main ()
{
list<int> first (3,100); // three ints with a value of 100
list<int> second (5,200); // five ints with a value of 200
list<int>::iterator it;

first.swap(second);

cout << "first contains:";
for (it=first.begin(); it!=first.end(); it++) cout << " " << *it;

cout << "\nsecond contains:";
for (it=second.begin(); it!=second.end(); it++) cout << " " << *it;

cout << endl;

return 0;
}

Output:
first contains: 200 200 200 200 200
second contains: 100 100 100

Аллокатор:
#include <iostream>
#include <list>

using namespace std;

int main ()
{
list<int> mylist;
int * p;
unsigned int i;

// allocate an array of 5 elements using mylist's allocator:
p=mylist.get_allocator().allocate(5);

// assign some values to array
for (i=0; i<5; i++) p[i]=i;

cout << "The allocated array contains:";
for (i=0; i<5; i++) cout << " " << p[i];
cout << endl;

mylist.get_allocator().deallocate(p,5);

return 0;
}

Пример демонстрирует красивый способ выделения памяти для массива целых чисел используя аллокатор контейнера. Output:
The allocated array contains: 0 1 2 3 4

Источники:
СПб, Т.А. Павловская, «С/C++ Программирование на языке высокого уровня»
http://www.cplusplus.com/reference/stl/list/
Content-Disposition: form-data; name="format"

1
------------RPE4eTyvo4kcV9O1FquLwF
Content-Disposition: form-data; name="format"

1

Библиотечные средства обработки списков в JAVA.
Коллекции в Java представляют собой реализацию абстрактных типов (структур) данных. Коллекции объединены в библиотеку классов java.util и представляют собой контейнеры для хранения и манипулирования объектами.
Списки.
Класс ArrayList – динамический массив объектных ссылок. Расширяет класс AbstractList и реализует интерфейс List. Класс имеет конструкторы:
ArrayList()
ArrayList(Collection c)
ArrayList(int capacity)
Практически все методы класса являются реализацией абстрактных методов из суперклассов и интерфейсов. Методы интерфейса List позволяют вставлять и удалять элементы из позиций, указываемых через отсчитываемый от нуля индекс:
void add(int index, Object obj) – вставляет obj в позицию, указанную в index;
void addAll(int index, Collection c) – вставляет в вызывающий список все элементы коллекции с, начиная с позиции index;
Object get(int index) – возвращает элемент в виде объекта из позиции index;
int indexOf(Object ob) – возвращает индекс указанного объекта;
Object remove(int index) – удаляет объект из позиции index.
Удаление элементов такой коллекции представляет собой ресурсоемкую задачу, поэтому объект ArrayList лучше всего подходит для хранения неизменяемых списков.
/* пример # 1 : работа со списком : DemoList1.java */
import java.util.*;
public class DemoList1 {
public static void main(String[] args) {
List c = new ArrayList();
//Collection c = new ArrayList();//попробуйте так!
int i = 2, j = 5;
c.add(new Integer(i));
c.add(new Boolean("True"));
c.add("<STRING>");
c.add(2, Integer.toString(j) + "X");
//заменить 2 на 5 !
System.out.println©;
if (c.contains("5X"))
c.remove(c.indexOf("5X"));
System.out.println©;
}
}
В результате на консоль будет выведено:
[2, true, 5X, <STRING>]
[2, true, <STRING>]
Для доступа к элементам списка может использоваться интерфейс ListIterator, в то же время класс ArrayList обладает аналогичными методами, в частности Object set(int index, Object ob), который позволяет заменить элемент списка без итератора, возвращая при этом удаляемый элемент.
/* пример # 2 : замена и удаление элементов : DemoList2.java */
import java.util.*;
public class DemoList2 {
static ListIterator it;
public static void main(String[] args) {
ArrayList a = new ArrayList();
int index;
System.out.println("коллекция пуста: "
+ a.isEmpty());
Character ch = new Character('b');
a.add(ch);
for (char c = 'a'; c < 'h'; ++c)
a.add(new Character©);
System.out.println(a + "число элементов:"
+ a.size());
it = a.listIterator(2); //извлечение итератора списка
it.add("new"); //добавление элемента без замены
System.out.println(
a + "добавление элемента в позицию");
System.out.println("число элементов стало:"
+ a.size());
//сравнить методы
index = a.lastIndexOf(ch); //index = a.indexOf(ch);
a.set(index, "rep"); //замена элемента
System.out.println(a + "замена элемента");
a.remove(6); //удаление элемента
System.out.println(a + "удален 6-й элемент");
System.out.println("коллекция пуста: "
+ a.isEmpty());
}
}
Коллекция LinkedList реализует связанный список. В отличие от массива, который хранит объекты в последовательных ячейках памяти, связанный список хранит объекты отдельно, но вместе со ссылками на следующее и предыдущее звенья последовательности. В списке, состоящем из N элементов, существует N+1 позиций итератора.
В добавление ко всем имеющимся методам в LinkedList реализованы методы void addFirst(Object ob), void addLast(Object ob), Object getFirst(), Object getLast(), Object removeFirst(), Object removeLast() добавляющие, извлекающие, удаляющие и извлекающие первый и последний элементы списка соответственно.
/* пример # 3 : добавление и удаление элементов :
DemoLinkedList.java */
import java.util.*;
public class DemoLinkedList {
public static void main(String[] args){
LinkedList aL = new LinkedList();
for(int i = 10; i <= 20; i++)
aL.add("" + i);
Iterator it = aL.iterator();
while(it.hasNext())
System.out.print(it.next() + " -> ");
ListIterator list = aL.listIterator();
list.next();
System.out.println("\n" + list.nextIndex()
+ "-й индекс");
//удаление элемента с текущим индексом list.remove();
while(list.hasNext())
list.next();//переход к последнему индексу
while(list.hasPrevious())
/*вывод в обратном порядке */
System.out.print(list.previous() + " ");
//методы, характерные для LinkedList aL.removeFirst();
aL.removeLast();
aL.removeLast();
aL.addFirst("FIRST");
aL.addLast("LAST");
System.out.println("\n" + aL);
}
}

В Прологе список (list) является объектом, содержащим внутри произвольное число других объектов. [ 1, 2, 3 ] - пример списка. Порядок элементов значим. Один и тот же элемент может быть представлен в списке несколько раз, например: [ 1, 2, 1, 3, 1 ].
Список на самом деле является рекурсивным составным объектом. Он состоит из двух частей - головы списка, которым является первый элемент, и хвоста - списка, который включает все следующие элементы. Хвост списка всегда есть список; голова списка есть элемент. Например, голова списка [a, b, c] есть a, хвост списка [a, b, c] есть [b, c]. Если в списке [c] лишь один элемент, то головой списка [c] является c
хвостом списка [c] является [].
Пустой список не может быть разбит на голову и хвост.
Таким образом, подобно другим составным объектам списки имеют древовидную структуру. Древовидная структура списка [a, b, c, d] есть:

list
/ \
a list
/ \
b list
/ \
c list
/ \
d []
Более того, одноэлементный список, такой как [a] - это не тот же самый элемент, который этот список содержит, поскольку [a] является действительно составной структурой данных, как это видно здесь:

list
/ \
a []

Пролог содержит метод для явного обозначения головы и хвоста списка. Вместо разделения элементов запятыми можно отделять голову от хвоста вертикальной чертой (|). Например,
[a, b, c] эквивалентно [a|[b, c]]
и, продолжая процесс,
[a|[b,c]] эквивалентно [a|[b|[c]]],
что эквивалентно [a|[b|[c|[]]]]

Лисп (LISP, от англ. LISt Processing — «обработка списков»; современное написание: Lisp) — семейство языков программирования, программы и данные в которых представляются системами линейных списков символов.
Основное понятие языка Лисп - список.
Список - это упорядоченная последовательность, элементами которой являются атомы или списки (подсписки). Списки заключаются в круглые скобки, элементы списка разделяются пробелами. Открывающие и закрывающие скобки находятся в строгом соответствии. Список всегда начинается с открывающей и заканчивается закрывающей скобкой. Список, который состоит из 0 элементов называют пустым и обозначают () или NIL. Пустой список - это атом. Например: (а в (с о) р), (+ 3 6).
Как видно из определения, списки могут быть вложенными. А что же такое атом в Лиспе? Это простой (в отличие от списка) тип данных: число, символьная строка, функция.
Внимание: в Лиспе нет различия между текстом программы и обрабатываемыми ею данными!
В других языках (например, в Паскале) программа (PROCEDURE, FUNCTION) и данные (VAR, CONST) жестко разделены. В Лиспе же и данные, и текст программы являются списками. Разумеется, список, являющийся программой, включает в себя атомы-функции, которые и вызываются при выполнении программы. То, что с программой можно работать, как с данными, и определяет возможность динамической модификации текста программы, что является свойством языков искусственного интеллекта. Как же отличить список-программу от списка-данных?
В Лиспе по умолчанию любой список является программой и интерпретатор будет пытаться ее выполнить. Если список - не программа, а данные, надо явно отключить его интерпретацию.
Из того, что текст программы - тоже список, вытекает необходимость использования специальной системы его записи - обратной польской нотации (названа так по причине изобретения ее польским математиком Яном Лукасевичем). Вызов любой функции в данной нотации записывается как список следующего вида:

(имя_функции а1,а2...аn) | (1.2)
где а1,а2...аn - аргументы функции.
Например, если функция сложения двух чисел имеет имя "+", то операция 2+3 запишется как ( + 2 3 ). В качестве аргументов могут фигурировать другие функции, что позволяет записывать сколь угодно сложные формулы в обратной польской нотации.
Пусть дана функция f(x,y)=(2x+3)*(y-x)\(y-1). В обратной польской записи она приобретет следующий вид:
( * ( / ( + ( * 2 x ) 3 ) ( - y 1 ) ) ( - y x ) ).

Любая программа на Лиспе состоит из последовательности выражений (форм). Результат работы программы состоит в вычислении этих выражений. Все выражения записываются в виде списков — одной из основных структур Лиспа, поэтому они могут легко быть созданы посредством самого языка. Это позволяет создавать программы, изменяющие другие программы или макросы, позволяющие существенно расширить возможности языка.
Список является последовательностью элементов любого рода, в том числе других списков. Например, (1 3/7 'foo #'+) состоит из целого числа, рациональной дроби, символа foo и указателя на функцию сложения. Выражения представляются списками в префиксной записи: первый элемент должен быть формой, то есть функцией, оператором, макросом или специальным оператором; прочие элементы суть аргументы, передаваемые форме для обработки. Функция list возвращает список состоящий из её аргументов: например, (list 1 3/7 'foo #'+) возвращает список, упомянутый ранее. Если некоторые элементы являются выражениями, то сначала вычисляется их значение: (list 1 2 (list 1 2)) возвращает (1 2 (1 2)). Арифметические операторы действуют так же, например (+ 4 (* 2 3)) выдаёт 10.

При записи на ЛИСПе, список ограничивается круглыми скобками, а его элементы разделяются пробелами.
Какие данные может содержать список? - в ЛИСПе - практически любые! Элементами списка могут быть константы, имена переменных и функций (в терминологии ЛИСПа - символы) и, конечно, другие списки:
(1 2 "abc" var (34 "w"))
Можно без преувеличения сказать, что список в ЛИСПе - основной структурный и аггрегирующий тип данных. Записи - аналогои struct или record в Common LISP реализованы средствами самого языка, а в newLISP-е вообще отсутствуют. Современные реализации (включая и newLISP) имеют встроенную поддержку массивов и хэшей, однако реально они используются только в случаях, когда для алгоритма действительно нужны массивы или хэши, т.е., как ни удивительно, достаточно редко. Следует отметить, что вместо хэшей в ЛИСПе обычно используются "ассоциативные списки".
Ассоциативный список - это "список списков", в которых первый элемент используется как ключ для поиска:
((ключ1 значение1_1 значение1_2) (ключ2 значение2_1 значение2_2) .....)
Для поиска в ассоциативных списках используются функции "assoc" и "lookup". С одной стороны, такой подход (теоретически) приводит к снижению производительности поиска (на практике - это вопрос спорный...), зато с другой - вы можете иметь несколько элментов с одинаковым ключом и у вас всегда фиксирован порядок следования записей.

Внутреннее представление списка.
Оперативная память машины логически разбивается на маленькие области, называемые списочными ячейками. Списочная ячейка состоит из двух частей, полей CAR и CDR (головы и хвоста соответственно). Каждое из полей содержит указатель. Указатель может ссылаться на другую списочную ячейку или на другой лисповский объект, например, атом. Указатели между ячейками образуют как бы цепочку, по которой можно из предыдущей ячейки попасть в следующую и так до атомарных объектов. Каждый известный системе атом записан в определенном месте памяти лишь один раз. Указателем списка является указатель на первую ячейку списка. На одну и ту же ячейку может указывать несколько указателей, но исходить только один.
Графически списочная ячейка представляется прямоугольником (рис3), разделенным на части CAR и CDR. Указатель изображается в виде стрелки, начинающейся в одной из частей прямоугольника и заканчивающейся на изображении другой ячейки или атоме, на которые ссылается указатель.

Логически идентичные атомы содержатся в системе лишь один раз. Но логически идентичные списки могут быть представлены различными списочными ячейками. Например, список ((d c) a d c) изображается как показано на рис.4. В результате вычислений в памяти могут возникнуть структуры на которые нельзя потом сослаться. Это происходит, если структуры не сохранены с помощью функции SETQ или теряется ссылка на старое значение в связи с новым переприсваиванием.

В зависимости от способа построения логическая и физическая структуры двух списков могут оказаться различными. Например, список ((d c) a d c) может иметь и другую структуру (рис5). Логическая структура всегда топологически имеет форму двоичного дерева, в то время как физическая структура может быть ациклическим графом, т. е. ветви могут снова сходиться, но никогда не могут образовывать замкнутые циклы (указывать назад).
При логическом сравнивании списков используют предикат EQUAL, сравнивающий не физические указатели, а совпадение структурного построения списков и совпадение атомов, формирующих список.
Предикат EQ можно использовать лишь для сравнения двух символов. Во многих реализациях Лиспа этот предикат обобщен таким образом, что с его помощью можно определить физическое равенство двух выражений (т. е. ссылаются ли значения аргументов на один физический лисповский объект) не зависимо от того, является ли он атомом или списком.

/*
В Лиспе список выглядит следующим образом: '(роза фиалка маргаритка лютик). Перед этим списком поставлен один апостроф. Этот список можно переписать по другому, именно так в дальнейшем и будут выглядеть списки с которыми вам придется иметь дело:
'(роза
фиалка
маргаритка
лютик)
Элементами этого списка являются названия четырех разных цветов, разделенные друг от друга пробелами и окруженные круглыми скобками, подобно цветам в саду с каменной оградой.
Списки могут также содержать числа, например: (+ 2 2). В этом списке первый элемент это знак плюс +, за которым следуют два числа, разделенные пробелами.
В Лиспе и данные, и программы представляются одинаковым образом, то есть в виде списков, состоящих из слов, чисел или других списков, разделенные пробельными символами и окруженные круглыми скобками. (Так как программы выглядят как данные, то одна программа легко может служить данными для другой программы --- это очень мощное свойство Лиспа). (Кстати, эти два замечания в скобках не являются допустимыми списками Лиспа, поскольку они содержат знаки препинания `;' и `.').
Вот другой список, в этот раз со списком внутри себя:
'(этот список содержит список (внутри себя))
Элементами этого списка являются слова `этот', `список', `содержит' и список `(внутри себя)'. Внутренний список составлен из слов `внутри', `себя'.
*/

Список являются одним из самых используемых типов данных в языке Python. Если все ваше знакомство со списками ограничивается массивами в Visual Basic или (не дай бог) datastore в Powerbuilder, возмите себя в руки для знакомства со списками в языке Python.

• Списки в языке Python похожи на массивы в языке Perl. Имена пееменных, хранящих массивы, в языке Perl всегда начинаются с символа @. Python не накладывает никаких дополнительных ограничений на имя переменных, в которых хранятся списки, интерпретатор сам определяет тип переменной.
  
• Списки в языке Python — нечто большее, чем массивы в Java (хотя вы можете использовать их в таком качестве, если это все, что вам требуется от жизни). Более близкой аналогией будет класс Vector, способный содержать произвольные объекты и динамически увеличиваться при добавлении новых элементов.
  

Пример 1.14. Определение списков

>>> li = ["a", "b", "mpilgrim", "z", "example"]
>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li[0]
'a'
>>> li[4]
'example'

• Сначала мы определяем список из пяти элементов. Обратите внимание, что исходный порядок элементов сохраняется. Это не случайно, список является упорядоченным множеством элементов, перечисленных в квадратных скобках.
  
• Списки могут быть использованы в качестве массивов. Отсчет элементов всегда ведется от нуля, так что первый элемент непустого списка — li[0].
  
• Последний элемент списка из пяти элементо — li[4], так как отсчет ведется от нуля.
  

Пример 1.15. Отрицательные индексы

>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li[-1]
'example'
>>> li[-3]
'mpilgrim'

• При использовании отрицательных индексов отсчет ведется с конца списка. Послединий элемент любого непустого списка можно получить, используя выражение li[-1].
  
• Если вас смущают отрицательные индексы, запомните простое правило: li[-n] == li[len(li) - n]. То есть, в нашем случае li[-3] == li[5 - 3] == li[2].
  

Пример 1.16. Срез

>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li[1:3]
['b', 'mpilgrim']
>>> li[1:-1]
['b', 'mpilgrim', 'z']
>>> li[0:3]
['a', 'b', 'mpilgrim']

• Указав через двоеточие два индекса, вы можете получить подмножество элементов списка, называемое “срезом”. Получаемое значение является новым списком, содержащим все элементы исходного списка в том же порядке, начиная с первого индекса (здесь li[1]) до, но не включая, второго индекса (здесь li[3]).
  
• В операции среза также можно использовать отрицательные идексы. Если это поможет, считайте первый индекс соответствующим первому элементу, который вам нужен, и второй — первому элементу, который не нужен. Получаемое значение — все, что между ними находится.
  
• Нумерация элементов начинается с нуля, так что li[0:3] дает первые три элемента исходного списка.
  

Пример 1.17. Сокращения в записи среза

>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li[:3]
['a', 'b', 'mpilgrim']
>>> li[3:]
['z', 'example']
>>> li[:]
['a', 'b', 'mpilgrim', 'z', 'example']

• Если первый индекс среза равен нулю, то его можно опустить. Аналогично можно опустить второй индекс, если он равен длине списка. То есть li[:3] дает такой же результат, как и li[0:3] в предыдущем примере.
  
• Обратите внимание на симметрию. Для данного списка из пяти элементов li[:3] дает первые три элемента и li[3:] — последние два. В самом деле, li[:n] всегда дает первые n элементов, а li[n:] — все остальное.
  
• Если опущены оба индекса, будут включены все элемента исходного списка. Но это не тот же список, это новый список с теми же элементами. Таким образом, li[:] позволяет создать копию списка.
  

Пример 1.18. Добавление элементов в список

>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li.append("new")
>>> li
['a', 'b', 'mpilgrim', 'z', 'example', 'new']
>>> li.insert(2, "new")
>>> li
['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new']
>>> li.extend(["two", "elements"])
>>> li
['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']

• Метод append добавляет один элемент в конец списка.
  
• Метод insert вставляет один элемент в список. Целочисленный аргумент является индексом первого элемента, позиция которого изменится. Обратите внимание, что элементы списка могут быть не уникальными — после этой операции в списке содержится два элемента со значением "new", li[2] и li[6].
  
• Метод extend добавляет в конец элементы другого списка. В данном случае второй список содержит два элемента.
  

Пример 1.19. Поиск в списке

>>> li
['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']
>>> li.index("example")
5
>>> li.index("new")
2
>>> li.index("c")
Traceback (innermost last):
File "<interactive input>", line 1, in ?
ValueError: list.index(x): x not in list
>>> "c" in li
0

• Метод index находит первое вхождение элемента в списке и возвращает его индекс.
  
• index позволяет найти только первое вхождение элемента. В нашем списке строка "new" присутствует дважды (li[2] и li[6]), но метод index вернет индекс только первого — 2.
  
• Если указанный элемент в списке не найден, генерируется исключение. Такое поведение заметно отличается от поведения аналогичных средств в других языках, возвращающих какой-либо некорректный индекс. Генерация исключения более удобна, так как работа программы останавливается в месте возникновения ошибки, а не в момент использования некорректного индекса.
  
• Для проверки наличия элемента в списке используйте оператор in, возвращающий 1, если значение найдено, и 0, если в списке такого значения нет.
  

Python не имеет отдельного булева типа. В булевом контексте (например, в условии инструкции if), 0 является ложью, а все остальные сисла являются истиной. Аналогично и для других типов: пустая строка (""), список ([]) и словарь ({}) являются ложью, а все остальные строки, списки и словари — истиной.

Пример 1.20. Удаление элементов из списка

>>> li
['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']
>>> li.remove("z")
>>> li
['a', 'b', 'new', 'mpilgrim', 'example', 'new', 'two', 'elements']
>>> li.remove("new")
>>> li
['a', 'b', 'mpilgrim', 'example', 'new', 'two', 'elements']
>>> li.remove("c")
Traceback (innermost last):
File "<interactive input>", line 1, in ?
ValueError: list.remove(x): x not in list
>>> li.pop()
'elements'
>>> li
['a', 'b', 'mpilgrim', 'example', 'new', 'two']

• Метод remove удаляет из списка первый элемент с указанным значением.
  
• remove удаляет только один элемент. В данном случае строка "new" присутствует в списке дважды, но li.remove("new") удалит только первую.
  
• Если элемент с указанным значением в списке не найден, remove, как и index, генерирует исключение.
  
• Метод pop выполняет сразу два действия: удаляет последний элемент из списка и возвращает его. Этим он отличается от li[-1], возвращающего последний элемент, но не изменяющего список, и li.remove(value), изменяющего список, но не возвращающего элемент.
  

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

>>> li = ['a', 'b', 'mpilgrim']
>>> li = li + ['example', 'new']
>>> li
['a', 'b', 'mpilgrim', 'example', 'new']
>>> li += ['two']
>>> li
['a', 'b', 'mpilgrim', 'example', 'new', 'two']
>>> li = [1, 2] * 3
>>> li
[1, 2, 1, 2, 1, 2]

• С помощью оператора + можно “склеивать” списки. list = list + otherlist эквивалентно list.extend(otherlist), но при этом создается новый список, в то время как extend изменяет существующий.
  
• Python поддерживает операцию +=. li += ['two'] полностью эквивалентно li.extend(['two']). Операция += работает для списков, строк, чисел и может быть переопределена для классов (более подробно о классах читайте в главе 3).
  
• Оператор * размножает элементы списка. li = [1, 2] * 3 эквивалентно li = [1, 2] + [1, 2] + [1, 2].
  

Сборка мусора
В программировании, сборка мусора — одна из форм автоматического управления памятью. Специальный код, называемый сборщиком мусора (garbage collector), в определённые моменты времени пытается освободить память, использованную объектами, которые уже не будут востребованы приложением — то есть производит сборку мусора.

Проблемы управления временем жизни объектов

В любом языке, допускающем создание объектов в динамической памяти, потенциально возможные две проблемы: висячие ссылки (англ. dangling pointer) и утечки памяти (англ. memory leak). Обе эти проблемы возникают из-за неправильного управления временем жизни объектов, создаваемых в динамической памяти.

Висячие ссылки

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

Утечки памяти

Предположим, объект был создан и его адрес был записан в указатель. Затем этому указателю присвоили новое значение, не удалив перед этим объект и не присвоив его адрес другому указателю. В результате в программе не осталось ни одного указателя, по которому можно перейти к объекту или удалить объект. Такая ситуация называется утечкой памяти. Утечки памяти приводят к постепенному увеличению потребляемого программой объема памяти, и если программа работает долго, она может через достаточно большое время затормозить работу системы или исчерпать доступный объем адресного пространства (и завершиться с ошибкой).

Способы управления памятью

Сборка мусора часто противопоставляется ручному управлению памятью, при котором программист явно указывает, когда и какие области памяти надо освободить. Однако есть языки, в которых используется комбинация двух методов управления памятью, равно как есть и другие технологии решения той же фундаментальной проблемы (например, en:region inference).

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

Некоторые языки программирования требуют использования механизма сборки мусора в соответствии со своей спецификацией (Java, C#), другие — по причинам эффективности реализации (например, формальные языки для лямбда-исчисления) — эти языки называются языками со сборкой мусора. Многие языки со сборкой мусора не имеют возможностей для явного ручного удаления объектов (например, оператора delete), благодаря чему возникновение висячих ссылок исключается в принципе, а сборщик мусора лишь занимается удалением объектов, на которые нет ссылок из программы.

Базовые принципы работы сборщика мусора:

1. на время работы сборщика мусора выполнение программы останавливается
2. определение объектов программы, которые в будущем не будут использоваться;
3. освобождение памяти, занимаемой этими объектами.

Хотя в общем случае невозможно точно определить момент, когда объект был использован в последний раз и больше не нужен, сборщики мусора используют консервативные оценки, позволяющие определить, что в будущем объект уже не будет использоваться. Например, если в системе нет больше ссылок на данный объект — то он больше не может быть использован программой. Этот критерий используется большинством современных сборщиков мусора.
Отслеживающие сборщики мусора

Сборщики мусора этого типа отслеживают, какие объекты являются достижимыми (или потенциально достижимыми) и затем удаляют из памяти все остальные.

Достижимость объекта

Неформально можно задать следующее рекурсивное определение достижимого объекта:

* Определённое множество объектов считается достижимым изначально. Такие объекты называются корневыми. Обычно в их число включают все глобальные переменные и объекты, на которые есть ссылки в стеке вызовов.
* Любой объект, на который есть ссылка из достижимого объекта тоже считается достижимым. Исключение составляют слабые ссылки.

Такое определение не является наилучшим. Оптимальнее было бы считать недостижимым объект, к которому в процессе дальнейшей работы программы не будет ни одного обращения. Однако определение таких объектов можно свести к неразрешимой задаче об останове. Для этого достаточно предположить, что некоторый объект X будет использован в том и только в том случае, если успешно завершится программа P.

Как только определено множество недостижимых объектов, сборщик мусора может освободить память, занимаемую ими, и оставить остальное как есть. Также можно переместить все или часть оставшихся объектов в другие области памяти, обновив вместе с этим все ссылки на них. Эти два варианта реализации называются, соответственно, перемещающим и неперемещающим.

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

* На этапе сборки мусора можно выполнить дефрагментацию памяти.
* Перемещение позволяет использовать чрезвычайно простой и быстрый (O(1)) алгоритм выделения памяти. Для этого достаточно подвинуть объекты так, чтобы разделить всю память на две большие области — занятую и свободную, и хранить указатель на их границу. Тогда для выделения новой памяти достаточно будет лишь переместить эту границу, вернув кусок из начала свободной памяти.
* Объекты, поля которых используются совместно, можно разместить в памяти недалеко друг от друга. Тогда они вероятнее окажутся в кэше процессора одновременно, что уменьшит количество обращений к относительно медленной ОЗУ.

Ещё один недостаток перемещающего сборщика заключается в том, что он должен уследить за всеми ссылками на объект, чтобы иметь возможность изменить их при перемещении. Для работы с кодом, который не позволяет этого делать (такой код называется инородным (foreign) в традиционной терминологии или неуправляемым в терминологии Microsoft), используются различные приёмы. Например, pinning — блокировка объекта, запрещающая его перемещение во время сборки мусора.

Управление памятью под ответственностью программиста

В языке C++ (именно на его примере рассмотрим системы, где ответственность за своевременное освобождение блоков памяти лежит на программисте) существуют предусмотренные стандартом C++, а также перешедшие "в наследство" от C средства выделения и освобождения памяти. Кроме того, каждая платформа предоставляет свои средства управления памятью (как правило, стандартные языковые средства как раз к ним и обращаются, но у программиста есть возможность обратиться к ним непосредственно). Проблема этих систем и языков (в том числе C++) состоит в том, что программист сам отвечает за своевременное освобождение блоков памяти после того, как в них отпадает необходимость - для этого тоже есть специальные функции. Если программист забудет освободить блок, впоследствии может возникнуть нехватка памяти - виртуальное адресное пространство процесса "забьется" и свободного места не останется, хотя в то же время в памяти будут присутствовать блоки, которые фактически не используются.

Рассмотрим коротко средства управления памятью.

Оператор new очень удобен - он не требует указания размера блока, который нужно выделить. Размер определяется компилятором автоматически исходя из типа, который указывается после ключевого слова new. Кроме вызова самой функции выделения памяти происходит еще и вызов конструктора объекта, если указан объектный тип. Синтаксис вызова оператора имеет несколько вариантов, рассмотрим наиболее часто употребляемый:

new Type (parameters)

где Type - тип создаваемого объекта, на основе которого компилятор автоматически определит требуемый для него объем памяти;

parameters - необязательный список параметров, который будет передан конструктору объекта. В случае отсутствия списка параметров скобки указывать необязательно.

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

Функции операционной системы Windows - LocalAlloc и GlobalAlloc - считаются устаревшими, хотя и поддерживаются в целях совместимости. Современным приложениям рекомендуется пользоваться HeapAlloc, а также VirtualAlloc, которая, помимо выделения памяти, поддерживает операцию резервирования памяти и выделения зарезервированной памяти.

Соответственно, средства освобождения памяти следующие.

Оператор delete освобождает занятый приложением блок, но перед этим вызывает деструктор объекта, если переменная объектного типа. Ничего, кроме параметра, содержащего адрес удаляемого блока, передавать не надо.

Функция free () освобождает выделенный с помощью malloc () блок. Следует передать адрес блока.

Функции Windows по освобождению памяти называются LocalFree, GlobalFree, HeapFree и VirtualFree.

Объясню суть проблемы такого управления памятью подробнее. Допустим, программисту нужно в цикле копировать файлы. Для этого он выделяет блок памяти необходимого размера, читает туда содержимое файла-источника, затем пишет содержимое блока в файл-приемник. Допустим теперь, что перед выходом из цикла человек забыл освободить выделенный блок. Начинается следующая итерация цикла, и происходит новое выделение памяти. Переменная, которая раньше содержала адрес первого блока, содержит теперь новый адрес - таким образом, адрес первого блока теряется! Значит, если вовремя не освободить выделенную память, есть вероятность, что адрес этого блока будет навсегда "забыт" приложением, и оно никогда не сможет его освободить.

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

Кроме очевидного преимущества, у системы сборки мусора есть свои подводные камни. В этих системах невозможно или сложно реализовать "ручные" механизмы выделения и освобождения памяти - к примеру, если на C++ вы можете с легкостью запросить память у операционной системы огромным куском, а внутри этого большого "куска" реализовать свои механизмы выделения/освобождения памяти, перегрузив операторы new и delete, вы теоретически сможете путем ручного управления памятью ускорить работу своего приложения (если, конечно, сможете придумать алгоритм, более оптимальный, чем стандартные), то в таких языках и средах вы этого сделать не сможете. А стандартные методы освобождения и выделения приходится иногда переписывать - например, если вы хотите хранить данные в файле и использовать отображение файлов на память. Другой подводный камень - система сборки мусора может физически переместить объект (естественно, поскольку адрес объекта изменился, все ссылки на него стали недействительными - их надо исправить, и это дело системы сборки мусора). Таким образом, вы не можете "доверять" адресу переменной (если вообще есть возможность его получить), так как он непостоянен. Кроме того, чтобы у сборщика мусора была возможность перемещать объекты физически, объект должен содержать не просто счетчик ссылок, а список самих ссылок, что увеличивает расходы (как расход памяти, так и ресурс времени) на содержание объектов.

Дерево отрезков

Дерево отрезков - структура данных, которая позволяет реализовать за O (log N) операции следующего типа: нахождение суммы/минимума элементов массива в заданном отрезке (A[L..R], где L и R - это параметры запроса), изменение одного элемента массива, изменение/прибавление элементов на отрезке (A[L..R]). При этом объём дополнительно используемой памяти составляет O (N), или, если быть точным, не более 4 N.
Описание

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

Построим бинарное дерево T следующим образом. Корень дерева будет храниться в элементе T[1]. Он будет содержать сумму элементов A[0..N-1], т.е. всего массива. Левый сын корня будет храниться в элементе T[2] и содержать сумму первой половины массива A: A[0..N/2], а правый сын - в элементе T[3] и содержать сумму элементов A[N/2+1..N-1]. В общем случае, если T[i]-ый элемент содержит сумму элементов с L-го по R-ый, то его левым сыном будет элемент T[i*2] и содержать сумму A[L..(L+R)/2], а его правым сыном будет T[i*2+1] и содержать сумму A[(L+R)/2+1..R]. Исключение, разумеется, составляют листья дерева - вершины, в которых L = R.

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

Рассмотрим теперь операцию суммы на некотором отрезке [L; R]. Мы встаём в корень дерева (i=1), и рекурсивно движемся вниз по этому дереву. Если в какой-то момент оказывается, что L и R совпадают с границами отрезка текущего элемента, то мы просто возвращаем значение текущего элемента T. Иначе, если отрезок [L; R] целиком попадает в отрезок левого или правого сына текущего элемента, то мы рекурсивно вызываем себя из этого сына и найденное значение возвращаем. Наконец, если отрезок [L; R] частично принадлежит и отрезку левого сына, и отрезку правого сына, то делим отрезок [L; R] на два отрезка [L; M] и [M+1; R] так, чтобы первый отрезок целиком принадлежал отрезку левого сына, а второй отрезок - отрезку правого сына, и рекурсивно вызываем себя и от первого, и от второго отрезков, возвращая сумму найденных сумм. В итоге вся операция суммирования работает за O (log N).

Теперь рассмотрим операцию изменения значения некоторого элемента с индексом K. Будем спускаться по дереву от корня, ища тот лист, который содержит значение элемента A[K]. Когда мы найдём этот элемент, просто изменим соответствующее значение в массиве T и будем подниматься от текущего элемента обратно к корню, пересчитывая текущие значения T. Понятно, что таким образом мы изменим все значения в дереве, которые нужно изменить. Итого асимптотика O (log N).

Наконец, рассмотрим операцию изменения на отрезке. Для реализации этой операции нам понадобится немного модифицировать дерево. Пусть каждый элемент дерева, помимо суммы, будет содержать значение Val[i]: если все элементы массива A в текущем отрезке равны друг другу, то Val[i] будет содержать это значение, а иначе он будет содержать некое значение "неопределённость". Изначально его можно просто заполнить значениями "неопределённость". А при выполнении операции изменения на отрезке мы будем спускаться по дереву, как в вышеописанном алгоритме суммирования, и если в какой-то момент L и R совпали с границами текущего отрезка, то мы присвоим Val[i] новое значение, которое мы хотим записать. Понятно, что теперь надо будет модифицировать операцию суммирования - если она в какой-то момент встречает Val[i], отличное от "неопределённости", то она прекращает спуск по дереву и сразу возвращает нужное значение - действительно, результат уже определён значением Val[i], а вот если мы продолжим спуск, то уже будем считывать неправильные, старые значения.

Операция прибавления на отрезке реализуется подобным образом, но несколько проще. В каждом элементе мы храним Add[i] - значение, которое нужно прибавить ко всем элементам этого отрезка. Операция прибавления на отрезке будет модифицировать эти значения, а операция суммирования - просто прибавлять к ответу все встретившиеся значения Add.

long long sum (int l, int r, int i = 1, int tl = 0, int tr = n-1) {
if (l == tl && r == tr)
return t[i];
int m = (l + r) / 2;
if (r <= m)
return sum (l, r, i*2, tl, m);
if (l > m)
return sum (l, r, i*2+1, m+1, tr);
return sum (l, m, i*2, tl, m) + sum (m+1, r, i*2+1, m+1, tr);
}

void update (int pos, int newval, int i = 1, int l = 0, int r = n-1) {
if (l == r)
t[i] = newval;
else {
int m = (l + r) / 2;
if (i <= m)
update (pos, newval, i*2, l, m);
else
update (pos, newval, i*2+1, m+1, r);
t[i] = t[i*2] + t[i*2+1];
}
}

материал: http://maximal.hocomua.ru/segment_tree.htm

Дерево Фенвика

Дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:

1) позволяет вычислять значение некоторой обратимой операции G на любом отрезке [L; R] за время O (log N);

2) позволяет изменять значение любого элемента за O (log N);

3) требует O (N) памяти, а точнее, ровно столько же, сколько и массив из N элементов;

4) легко обобщается на случай многомерных массивов.

Наиболее распространённое применение дерева Фенвика - для вычисления суммы на отрезке, т.е. функция G (X1, ..., Xk) = X1 + ... + Xk.

Дерево Фенвика было впервые описано в статье "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).
Описание

Для простоты описания мы предполагаем, что операция G, по которой мы строим дерево, - это сумма.

Пусть дан массив A[0..N-1]. Дерево Фенвика - массив T[0..N-1], в каждом элементе которого хранится сумма некоторых элементов массива A:

Ti = сумма Aj для всех F(i) <= j <= i, где F(i) - некоторая функция.

Определим значение F(X) следующим образом. Рассмотрим двоичную запись этого числа и посмотрим на его младший бит. Если он равен нулю, то F(X) = X. Иначе двоичное представление числа X оканчивается на группу из одной или нескольких единиц. Заменим все единицы из этой группы на нули, и присвоим полученное число значению функции F(X).

Этому довольно сложному описанию соответствует очень простая формула:

F(X) = X & (X+1), где & - это операция побитового логического "И".

Нам осталось только научиться быстро находить такие числа j, для которых F(j) <= i <= j.

Однако нетрудно убедиться в том, что все такие числа j получаются из i последовательными заменами самого правого (самого младшего) нуля в двоичном представлении. Например, для i = 10 мы получим, что j = 11, 15, 31, 63 и т.д.

Как ни странно, такой операции (замена самого младшего нуля на единицу) также соответствует очень простая формула:

H(X) = X | (X+1), где | - это операция побитового логического "ИЛИ".

int sum (int r)
{
int result = 0;
for (; r >= 0; r = (r & (r+1)) - 1)
result += t[r];
return result;
}

void inc (int i, int delta)
{
for (; i < n; i = (i | (i+1)))
t[i] += delta;
}

int sum (int l, int r)
{
return sum ® - sum (l-1);
}

Функция sum работает следующим образом. Вместо того чтобы идти по всем элементам массива A, она движется по массиву T, делая "прыжки" через отрезки там, где это возможно. Сначала она прибавляет к ответу значение суммы на отрезке [F®; R], затем берёт сумму на отрезке [F(F®-1); F®-1], и так далее, пока не дойдёт до нуля.

Функция inc движется в обратную сторону - в сторону увеличения индексов, обновляя значения суммы Tj только для тех позиций, для которых это нужно, т.е. для всех j, для которых F(j) <= i <= j.

материал: http://maximal.hocomua.ru/Fenwick_tree.htm

Свя́занный спи́сок — это структура данных, в которой объекты расположены в линейном порядке. Однако, в отличие от массива, в котором этот порядок определяется индексами, порядок в связанном списке определяется указателями на каждый объект. Связанные списки обеспечивают простое и гибкое представление динамических множеств и поддерживают все операции (возможно, недостаточно эффективно).

Линейный связанный список

Односвязный список

В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента невозможно.

Двусвязный список

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

Xor-связанный список

XOR-связанный список — структура данных, похожая на обычный двухсвязный список, однако в каждом элементе хранящая только ОДИН адрес — результат выполнения операции XOR над адресами предыдущего и следующего элемента списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию исключающего ИЛИ, которая и даст реальный адрес следующего элемента. В сравнении с обычным двусвязным списком, XOR список расходует в два раза меньше памяти для хранения связей между элементами. Из недостатков можно упомянуть более сложную реализацию, невозможность использования стандартного сборщика мусора, затруднения при отладке программы. Употребляется довольно редко, так как существуют хорошие альтернативы, как, например, развёрнутый связанный список.

Кольцевой связанный список

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

Список с пропусками

Список с пропусками - разновидность упорядоченного списка, позволяющий быстро находить любой его элемент. В обычном упорядоченном списке для поиска необходимо просматривать все элементы по порядку, таким образом поиск произвольного элемента занимает в среднем n/2 операций, где n - количество элементов в списке. Список с пропусками содержит специальные дополнительные указатели, позволяющие "перескочить" через определённое количество элементов, таким образом можно реализовать более быстрый поиск, занимая всего O(log1/p n / p) операций, где p - константа.

Развёрнутый связанный список

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

Позволяет значительно уменьшить размер памяти и увеличить производительность по сравнению с обычным списком. Особенно большая экономия памяти достигается при очень малом размере логических элементов и большом их количестве — так, односвязный список из 10000 четырёхбайтовых целых чисел при четырёхбайтовой же адресации памяти занимает 10000 дополнительных байт под адреса, если же обьединить числа в массивы по 100, расход памяти упадёт до 100 байт.

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

Достоинства
• лёгкость добавления и удаления элементов
• размер ограничен только объёмом памяти компьютера и разрядностью указателей
Недостатки
• сложность определения адреса элемента по его индексу (номеру) в списке
• на поле указателей расходуется дополнительная память (в массивах, например, указатели не нужны)
• работа со списком медленнее, чем с массивами, так как к любому элементу списка можно обратится, только пройдя все предшествующие ему элементы

Стек

Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (Last In — First Out, последним пришел — первым вышел). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно взять верхнюю.

Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху), выталкивание (pop) — также только из вершины стека, при этом второй сверху элемент становится верхним.

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

Очередь

Очередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть dequeue, при этом выбранный элемент из очереди удаляется).

Способы реализации очереди

Существуют два основных способа реализации очереди на языке программирования.

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

Переменные start и end указывают на голову и хвост очереди соответственно. При добавлении элемента в очередь переменная end уменьшается на 1 и в q[end] записывается новый элемент очереди. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично (при извлечении элемента q[start] из очереди, переменная start уменьшается на 1).

Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.
Недостатки: ограничение на максимальное количество элементов в очереди размером массива (n).

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

Преимущества данного метода: размер очереди ограничен лишь объемом памяти.
Недостатки: сложнее в разработке.

Очереди в различных языках программирования

Практически во всех развитых языках программирования реализованы очереди. В CLI для этого предусмотрен класс System.Сollections.Queue с методами Enqueue и Dequeue. В STL также присутствует класс queue<>, определённый в заголовочном файле queue. В нём используется та же терминология (push и pop), что и в стеках.

Применение очередей

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

Дек

Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

Операции над деком:

включение элемента справа;
включение элемента слева;
исключение элемента справа;
исключение элемента слева;
определение размера;
очистка.

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

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

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