После стандартизации в 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.

Бинарные деревья
Определение
Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.

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

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

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

Таблица – это список, состоящий из конечного множества элементов, при чем каждый элемент характеризуется рядом признаков (свойств). Один из признаков, называемый ключом, позволяет отличить один элемент от другого (идентифицировать элемент). Ключ может однозначно определять элемент таблицы (ключи всех элементов различны) или неоднозначно (в таблице есть элементы с равными ключами).
Неупорядоченная таблица – это таблица, элементы которой располагаются в порядке их поступления в таблицу.
Упорядоченная таблица – это таблица, между элементами которой
установлено отношение порядка. Это отношение, как правило,
устанавливается на признаке ключ. Поэтому говорят, что таблица упорядочена по ключам элементов. Таблица упорядочена по возрастанию значений ключа, если ключ( Ti ) < ключ( Ti+1 ) для всех i = 1, 2 , . . . , n-1
( здесь Ti - i -й элемент таблицы T). Таблица упорядочена по убыванию значений ключа, если ключ( Ti ) > ключ( Ti+1) для всех i = 1, 2, . . . , n-1.
В неупорядоченной таблице поиск элемента в среднем будет выполнен за n/2 сравнений, так как поиск заключается в последовательном просмотре элементов таблицы (максимальное число сравнений n). В упорядоченной таблице кроме последовательного просмотра можно применять бинарный поиск, максимальное число сравнений при котором 1 + log2 n.
Время поиска в хеш-таблице без коллизий постоянно – это время вычисления функции расстановки. Время поиска в таблицах с перемешиванием для метода линейного рехеширования зависит от коэффициента загрузки таблицы k = n/N, среднее число сравнений
e = ( 1 - k/2 ) ( 1 - k).

Далее следует информация, которая возможно пригодиться.

Разрешать коллизии можно в исходной или в дополнительной таблице. Если в исходной, то такая таблица называется таблицей с перемешиванием или с открытой адресацией. Таблица с перемешиванием должна быть инициирована, чтобы элементы таблицы получили в начале значение «пусто» (при взятии элемента из такой таблицы надо различать еще одно состояние: элемент удален из таблицы). В таблицах с перемешиванием применяют линейное (метод последовательных испытаний или проб), случайное или квадратичное рехеширование. Наиболее простой метод - линейное рехеширование, который заключается в том, что функция вторичной расстановки fú определяется как
fú (ключ, i) = ( f (ключ) + i ) mod N ,
здесь значение i равно 1, 2, . . . , а f (ключ) это значение, дающее коллизию. Рехеширование продолжается до тех пор, пока очередная позиция массива с номером fú (ключ, i) не окажется пустой или равной снова своему начальному значению ( в этом случае таблица полна ). Линейное рехеширование применяют, если таблица никогда не бывает полностью заполненной (лучше, если она заполнена не более чем на 70%).
В случае разрешения коллизии в дополнительной таблице удобно использовать хеширование с цепочками. В таких таблицах элементы, которым соответствует одно и то же хеш-значение, связываются в цепочку – список, а в самом элементе таблицы хранится ссылка на список

Модуль в программировании представляет собой функционально законченный фрагмент программы, оформленный в виде отдельного файла с исходным кодом, предназначенный для использования в других программах. Модули позволяют разбивать сложные задачи на более мелкие. Обычно проектируются таким образом, чтобы предоставлять программистам удобный для многократного использования функционал (интерфейс) в виде набора функций, классов, констант. Модули могут объединяться в пакеты и, далее, в библиотеки.
Модули могут быть обычными, т.е. написанными на том же языке, что и программа, в которой они используются, либо модулями расширения, которые пишутся на отличном от языка основной программы языке. Модули расширения обычно пишутся на более низкоуровневом языке, что позволяет получить выигрыш в скорости выполнения (производительности) программы.
В си модули подключаются с помощью директивы #include. Директива #include дает указание компилятору читать еще один исходный файл — в дополнение к тому файлу, в котором находится сама эта директива. Имя исходного файла должно быть заключено в двойные кавычки или в угловые скобки. Например, обе директивы
#include "stdio.h"
#include <stdio.h>
дают компилятору указание читать и компилировать заголовок для библиотечных функций системы ввода/вывода.
Файлы, имена которых находятся в директивах #include, могут в свою очередь содержать другие директивы #include. Они называются вложенными директивами #include. Количество допустимых уровней вложенности у разных компиляторов может быть разным. Однако в стандарте С89 предусмотрено, что компиляторы должны допускать не менее 8 таких уровней. А в стандарте С99 предусмотрена поддержка не менее 15 уровней вложенности.
Способ поиска файла зависит от того, заключено ли его имя в двойные кавычки или же в угловые скобки. Если имя заключено в угловые скобки, то поиск файла проводится тем способом, который определен в компиляторе. Часто это означает поиск определенного каталога, специально предназначенного для хранения таких файлов. Если имя заключено в кавычки, то поиск файла проводится другим способом. Во многих компиляторах это означает поиск файла в текущем рабочем каталоге. Если же файл не найден, то поиск повторяется уже так, как будто имя файла заключено в угловые скобки.
Обычно большинство программистов имена стандартных заголовочных файлов заключают в угловые скобки. А использование кавычек обычно приберегается для имен специальных файлов, относящихся к конкретной программе. Впрочем, твердого и простого правила, по которому кавычки требуется использовать именно таким образом, не существует.
В С-программе директиву #include можно использовать не только для указания имени файла, содержащего обычный исходный текст программы, но и для указания заголовка. В языке С определен набор стандартных заголовков, содержащих необходимую информацию о различных библиотеках этого языка. Заголовок — это стандартный идентификатор, который может соответствовать имени файла, а может и не соответствовать ему. Таким образом, заголовок является просто абстракцией, которая гарантирует наличие некоторой информации. Однако на практике в языке С заголовки почти всегда являются именами файлов.
Директивы #if, #else, #elif и #endif
Возможно, самыми распространенными директивами условной компиляции являются #if, #else, #elif и #endif. Они дают возможность в зависимости от значения константного выражения включать или исключать те или иные части кода.
В общем виде директива #if выглядит таким образом:
#if константное выражение
последовательность операторов
#endif
Если находящееся за #if константное выражение истинно, то компилируется код, который находится между этим выражением и #endif. В противном случае этот промежуточный код пропускается. Директива #endif обозначает конец блока #if. Например,
/* Простой пример #if. */
#include <stdio.h>

#define MAX 100

int main(void)
{
#if MAX>99
printf("Компилирует для массива, размер которого больше 99.\n");
#endif

return 0;
}
Это программа выводит сообщение на экран, потому что МАХ больше 99.
Директива #else работает в основном так, как else — ключевое слово языка С: задает альтернативу на тот случай, если не выполнено условие #if. Предыдущий пример можно дополнить следующим образом:
/* Простой пример #if/#else. */
#include <stdio.h>

#define MAX 10

int main(void)
{
#if MAX>99
printf("Компилирует для массива, размер которого больше 99.\n");
#else
printf("Компилирует для небольшого массива.\n");
#endif

return 0;
}
В этом случае выясняется, что МАХ меньше 99, поэтому часть кода, относящаяся к #if, не компилируется. Однако компилируется альтернативный код, относящийся к #else, и откомпилированная программа будет отображать сообщение Компилируется для небольшого массива.
Директива #elif означает "else if" и устанавливает для множества вариантов компиляции цепочку if-else-if. После #elif находится константное выражение. Если это выражение истинно, то компилируется находящийся за ним блок кода, и больше не проверяются никакие другие выражения #elif. В противном же случае проверяется следующий блок этой последовательности. В общем виде #elif выглядит таким образом:
#if выражение
последовательность операторов
#elif выражение 1
последовательность операторов
#elif выражение 2
последовательность операторов
#elif выражение 3
последовательность операторов
#elif выражение 4
.
.
.
#elif выражение N
последовательность операторов
#endif
Например, в следующем фрагменте для определения знака денежной единицы используется значение ACTIVE_COUNTRY (для какой страны):
#define US 0
#define ENGLAND 1
#define FRANCE 2

#define ACTIVE_COUNTRY US

#if ACTIVE_COUNTRY == US
char currency[] = "dollar";
#elif ACTIVE_COUNTRY == ENGLAND
char currency[] = "pound";
#else
char currency[] = "franc";
#endif
В соответствии со стандартом С89 у директив #if и #elif может быть не менее 8 уровней вложенности. А в соответствии со стандартом С99 программистам разрешается использовать не менее 63 уровней вложенности. При вложенности каждая директива #endif, #else или #elif относится к ближайшей директиве #if или #elif. Например, совершенно правильным является следующий фрагмент кода:
Директивы #ifdef и #ifndef
Другой способ условной компиляции — это использование директив #ifdef и #ifndef, которые соответственно означают "if defined" (если определено) и "if not defined" (если не определено). В общем виде #ifdef выглядит таким образом:
#ifdef имя_макроса
последовательность операторов
#endif
Блок кода будет компилироваться, если имя макроса было определено ранее в операторе #define.
В общем виде оператор #ifndef выглядит также как и #ifdef образом:
Блок кода будет компилироваться, если имя макроса еще не определено в операторе #define.
И в #ifdef, и в #ifndef можно использовать оператор #else или #elif. Например,
#include <stdio.h>

#define TED 10

int main(void)
{
#ifdef TED
printf("Привет, Тед\n");
#else
printf("Привет, кто-нибудь\n");
#endif
#ifndef RALPH
printf("А RALPH не определен, т.ч. Ральфу не повезло.\n");
#endif

return 0;
}
выведет Привет, Тед, а также A RALPH не определен, т.ч. Ральфу не повезло.
В соответствии со стандартом С89 допускается не менее 8 уровней #ifdef и #ifndef. А стандарт С99 устанавливает, что должно поддерживаться не менее 63 уровней вложенности.

Несмотря на то, что большая часть кода Си будет справедлива и для Си++, Си++ не является надмножеством Си и не включает его в себя. Существует и такой верный для Си код, который неверен для Си++.
Существуют и другие различия. Например, Си++ не разрешает вызывать функцию 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] являются программами на С++. В процессе изучения С++ будет полезен опыт работы с любым языком со статическими типами.

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

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

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

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

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

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

Применение сильноветвящихся деревьев
Один из примеров применения сильноветвящихся деревьев был связан с представлением арифметических выражений произвольного вида. Рассмотрим использование таких деревьев для представления иерархической структуры каталогов файловой системы. Во многих файловых системах структура каталогов и файлов, как правило, представляет собой одно или несколько сильноветвящихся деревьев. В файловой системе MS Dos корень дерева соответствует логическому диску. Листья дерева соответствуют файлам и пустым каталогам, а узлы с ненулевой степенью - непустым каталогам.

Выполняется на упорядоченном одномерном массиве. Производит самый быстрый поиск при таких условиях.
Максимальное количество сравнений(проходов) log2n. Работает следующим образом: смотрим середину первоначального интервала - больше, меньше, равна ли искомому значению? Если равна – то искомый элемент найден, если меньше, то делаем новый интервал, который начинается с середины предыдущего интервала и заканчивается той же верхней границей предыдущего, т.е. это вторая половина исходного интервала, далее вся процедура повторяется. Если середина - больше искомого значения, то новый интервал будет первой половиной исходного интервала. И так итеративно сужаем наш интервал до тех пор, пока искомый элемент не будет найден или не дойдем до пустого интервала.

while((low <= high)&&(!found)) {
mid=(low+high)/2;
if(keys[mid] == key) found = 1;
else if(key > keys[mid]) low = mid + 1;
else high = mid - 1;
}
if (found==1) return mid;
if(found==0) {
printf("Record not found!\n");
return -1;
}

Интерфейс отражает внешнее поведение объекта, описывая абстракцию поведения всех
объектов данного класса. Внутренняя реализация описывает представление этой абстракции и механизмы достижения желаемого поведения объекта. Разделение интерфейса и реализации позволяет защитить объекты от деталей реализации объектов более низкого уровня. Инкапсуляция позволяет вносить в программу изменения, сохраняя ее надежность и минимизируя затраты на этот процесс. Традиционным в C++ является помещение интерфейсной части модулей в отдельные файлы с расширением .h.
Класс - множество объектов, связанных общностью структуры и поведением. Существует явное разделение внутреннего и внешнего описания класса. Интерфейсная часть описания класса соответствует его внешнему проявлению, подчёркивает его абстрактность, но скрывает структуру и особенности поведения.
Реализация составляет его внутреннее проявление и определяет особенности поведения. Интерфейсная часть описания класса может быть разделена на три составные части: общедоступную; защищённую и обособленную.
С точки зрения контрактного программирования класс - это генеральный контракт между абстракцией и всеми ее клиентами. Все обязательства класса выражены в его интерфейсе.
Состояние объекта задается в его классе через определение констант или переменных, помещаемых в его защищенной или закрытой части.
Интерфейсом называется набор операций, используемый для определения услуг, предоставляемых классом или компонентом, выполняемых прецедентом или подсистемой. Интерфейс изображается в виде круга, присоединенному к реализующему его классу или компоненту. Интерфейс может быть изображен также как стереотипный класс с множеством операций. Для интерфейса определена операция реализации. Он может быть реализован несколькими классами и наоборот один класс может реализовывать несколько интерфейсов. Отметим, что у интерфейса нет атрибутов и нет непосредственных экземпляров.

В стандарте С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-разрядные целые значения с помощью встроенного типа.

Сокращенный обход право-прошитого бинарного дерева Сокращенный обход бинарного дерева — разновидность обхода бинарного дерева поиска, позволяющая, используя O(1) дополнительной памяти, обходить все элементы дерева за O(N), где N — количество элементов в дереве. При этом каждый элемент дерева будет просмотрен не больше двух раз. Прошитое дерево В общем случае это обычное бинарное дерево, ссылки "лево" и "право" которого вместо того, чтобы равняться null ссылаются на своего "родителя". Таким образом деревья можно пробегать быстрее. Для того, чтобы распознать где нормальная ссылка, а где ссылка на родителя используют дополнительные одну-две переменные в которой хранится данная информация. Рассмотрим разновидность бинарного дерева поиска. В каждом узле которого, кроме ссылок left, right и parent будем ещё хранить ссылку uplink. Ссылка uplink каждого узла дерева должна удовлетворять следующим свойствам: если right ≠ null, то uplink = null; если right = null, то uplink указывает на элемент следующий по величине, если таковой существует. У наибольшего элемента дерева uplink = null, также как и right = null. Ссылки left, right имеют то же значение, что и у обычного бинарного дерева поиска. Операция обхода дерева Операция обхода прошитого дерева позволяет перечислить все элементы дерева в порядке возрастания ключа за время O(N) и используя O(1) дополнительной памяти. Операцию обхода прошитого дерева реализуем следующим образом. В качестве стартового элемента возьмем минимальный элемент дерева. Рассмотрим текущий элемент. Если right ≠ null, то следующий по величине элемент за текущим будет минимальный элемент в нашем правом поддереве. Если right = null, то следующий по величине элемент будет элемент uplink. Согласно определению uplink. Если и right = null и uplink = null, то текущий элемент в дереве имеет наибольший ключ и обход дерева можно завершить. Заметим, что при этом каждый элемент будет просмотрен не больше чем два раза: первый раз при движении к минимальному элементу в правом поддереве некого элемента, а второй раз при переходе по uplink. Т.к. каждый элемент будет просмотрен не больше чем константу раз, а количество элементов N, то время работы алгоритма есть O(N). Операция вставки в дерево Операция вставки является аналогичной операции вставки в обычное бинарное дерево поиска, но требует дополнительной корректировки поля uplink. У только что вставленного узла, обозначим его n, поле right = null. Значит uplink должен содержать ссылку на следующий по величине элемент после нашего. Если n — левый сын своего родителя, то следующий по величине за ним элемент будет его родитель. Если n — стал правым сыном своего родителя, то это означает, что у его родителя uplink ≠ null и указывает на следующий после его родителя элемент. Поэтому нам необходимо uplink родителя записать узлу n, а uplink родителя обнулить. Операция вставки в прошитое дерево выполняет на константу операций больше чем в простое бинарное дерево, поэтому работает также O(logN). Операция удаления из дерева Операция удаления, также как и вставки, реализуется аналогично удалению из бинарного дерева поиска, только необходимо соответствующим образом откорректировать поля uplink. Предположим, что в дереве необходимо удалить некий элемент e. Рассмотрим четыре случая. Пусть e лист. Если e является левым сыном своего родителя, то мы можем просто удалить этот элемент из дерева. Если e — правый сын своего родителя, то мы должны наш uplink записать нашему родителю, а затем удалить элемент. Пусть e имеет только правого потомка. Тогда операция удаления e является полностью аналогичной операции удаления из бинарного дерева. Пусть e имеет только левого потомка. Запишем нашего потомка на место удаляемого узла. Т.к. uplink наибольшего элемента в нашем левом поддереве ссылается на элемент e необходимо его модифицировать, чтобы теперь он ссылался на нашего левого потомка. Пусть e имеет обоих потомков. По аналогии с обычным бинарным деревом, найдем следующий (обозначим его f) за удаляемым элемент (это будет наименьший элемент в его правом поддереве), перепишем содержимое элемента f в элемент e. И попробуем удалить f. Т.к. узел f максимум может содержать только одного потомка, то при его удалении могут иметь место только первые три случая. Несложно показать, что операция удаления элемента из прошитого дерева, также будет выполняться за O(logN), где N — количество элементов в дереве. Операция поиска Операция поиска также может быть реализована на прошитом дереве. При этом она будет полностью эквивалентна операции поиска в бинарном дереве. Поэтому она не представляет интереса.

Алгоритм Рабина — Карпа

Алгоритм Рабина—Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он не широко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов. Для текста длины n и шаблона длины m, его среднее время исполнения и лучшее время исполнения это O(n), но в (весьма нежелательном) худшем случае он имеет производительность O(nm), что является одной из причин того, почему он не используется широко. Однако, он имеет уникальную особенность быть способным находить любую из k строк менее, чем за время O(n) в среднем, независимо от размера k.

Одно из простейших практических применений алгоритма Рабина—Карпа состоит в определении плагиата. Скажем, например, что студент пишет работу по Моби Дику. Коварный профессор находит различные исходные материалы по Моби Дику и автоматически извлекает список предложений в этих материалах. Затем, алгоритм Рабина—Карпа может быстро найти в проверяемой статье примеры вхождения некоторых предложений из исходных материалов. Для лёгкого избежания расстройства системы из-за небольших изменений, можно игнорировать детали, такие как регистр или пунктуация при помощи их удаления. Поскольку количество строк, которые мы ищем, k, очень большое, обычные алгоритмы поиска одиночных строк неэффективны.

Алгоритм Бойера-Мура

Алгоритм Бойера-Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ. Robert S. Boyer) и Джеем Муром (англ. J Strother Moore) в 1977 году. Преимущество этого алгоритма в том, что не нужно сравнивать шаблон (строка, которую хотим найти) с каждой буквой исходного текста, так как некоторые из них можно пропустить. Чем длиннее шаблон, тем быстрее работает алгоритм.

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

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

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

Алгоритм Кнута — Морриса — Пратта

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

Рассмотрим сравнение на позиции i, где образец x[ 0, m - 1 ] сопоставляется с частью текста y[ i, i + m - 1 ]. Предположим, что первое несовпадение произошло между y[ i + j ] и x[ j ] , где 1 < j < m. Тогда y[ i, i + j - 1 ] = x[ 0, j - 1 ] = u и a = y[ i + j ] =/= x[ j ] = b.

При сдвиге вполне можно ожидать, что префикс образца u сойдется с каким-нибудь суффиксом подслова текста u. Более того, если мы хотим избежать выявления другого несовпадения ( то есть не тратить на это операцию сравнения ;-) ), буква, находящаяся за префиксом v в образце должна отличаться от b. Наиболее длинный такой префикс v называется границей u ( он встречается по обоим сторонам u ).

Это приводит к следующему алгоритму: пусть kmp_next[ j ] - длина длиннейшей границы x[ 0, j - 1 ], за которой следует символ c, отличающийся от x[ j ]. Тогда после сдвига мы можем возобновить сравнения между символами y[ i + j ] и x[ j - kmp_next[ j ] ] без возможной потери местонахождения образца. Таблица kmp_next может быть вычислена за O( m ) перед поиском через применение этого же алгоритма поиска к самому образцу ( т.е y = x ). При этом максимальное количество сравнений для одного символа текста - logФ( m ), где Ф - золотое сечение: ( корень из 5 + 1 ) / 2.

ОБЪЕКТНЫЙ МОДУЛЬ
Обье́ктный мо́дуль (также — объектный файл, англ. object file) — файл с промежуточным представлением отдельного модуля программы, полученный в результате обработки исходного кода компилятором. Объектный файл содержит в себе особым образом подготовленный код (часто называемый бинарным), который может быть объединён с другими объектными файлами при помощи редактора связей (компоновщика) для получения готового исполняемого модуля либо библиотеки.
Объектные файлы представляют собой блоки машинного кода и данных, с неопределенными адресами ссылок на данные и процедуры в других объектных модулях, а также список своих процедур и данных. Компоновщик собирает код и данные каждого объектного модуля в итоговую программу, вычисляет и заполняет адреса перекрестных ссылок между модулями. Также в процессе компоновки происходит связывание программы со статическими и динамическими библиотеками (являющихся архивами объектных файлов.
Объектный модуль программы получается в результате трансляции исходного текста модуля. В состав объектного модуля программы помещается оттранслированный код модуля, информация для редактора связей, позволяющая объединять модули в единую программу, и отладочная информация (переменные, константы, метки и их адреса).
В большинстве современных языков программирования программа состоит из отдельных слабо связанных модулей. Как правило, каждому такому модулю соответствует отдельный файл исходного текста. Эти файлы независимо обрабатываются языковым процессором (компилятором), и для каждого из них генерируется отдельный файл, называемый объектным модулем.

Трансляция + Редактирование связей (комапоновка).

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

Процесс создания
В большинстве современных языков программирования программа состоит из отдельных слабо связанных модулей. Как правило, каждому такому модулю соответствует отдельный файл исходного текста. Эти файлы независимо обрабатываются языковым процессором (компилятором), и для каждого из них генерируется отдельный файл, называемый объектным модулем. Затем запускается программа,- называемая редактором связей, компоновщиком или линкером (linker — тот, кто связывает), которая формирует из заданных объектных модулей цельную программу.
Объектный модуль отчасти похож по структуре на перемещаемый загрузочный модуль. Дело в том, что сборку программы из нескольких модулей можно уподобить загрузке в память нескольких программ.
Кроме того, в объектных файлах может содержаться отладочная информация, формат которой может быть очень сложным. Следовательно, объектный файл представляет собой довольно сложную и рыхлую структуру. Размер собранной программы может оказаться в два или три раза меньше суммы длин объектных модулей.
Типичный объектный модуль содержит следующие структуры данных.
• Таблицу перемещений, т. е. таблицу ссылок на перемещаемые объекты внутри модуля.
• Таблицу ссылок на внешние объекты. Иногда это называется таблицей или списком импорта.
• Таблицу объектов, определенных в этом модуле, на которые можно ссылаться из других модулей. В некоторых случаях ее называют списком экспорта. Иногда таблицы экспорта и импорта объединяют и называют все это таблицей глобальных символов. В этом случае для каждого символа приходится указывать, определен он в данном модуле или нет, а если определен, то как.
• Различную служебную информацию, такую, как имя модуля, программу, которая его создала (например, строка "gcc compiled").
• Отладочную информацию.
• Собственно код и данные модуля.
Редактор связей и то, что с ним связано.
реда́ктор свя́зей, англ. linker, link editor) — программа, которая производит компоновку — принимает на вход один или несколько объектных модулей и собирает по ним исполняемый модуль.
Для связывания модулей, компоновщик использует таблицы имён, созданные компилятором в каждом из объектных модулей. Такие имена могут быть двух типов:
• Определённые или экспортируемые имена — функции и переменные, определённые в данном модуле и предоставляемые для использования другим модулям
• Неопределённые или импортируемые имена — функции и переменные, на которые ссылается модуль, но не определяет их внутри себя
Работа компоновщика заключается в том, чтобы в каждом модуле разрешить ссылки на неопределённые имена. Для каждого импортируемого имени находится его определение в других модулях, упоминание имени заменяется на его адрес.

Опция –l + Библиотеки

Ключи компоновщика задают режими работы компоновщика, наиболее часто используется ключ -l задающий имена системных библиотек объектных модулей. Системные библиотеки хранятся в каталоге /lib или /usr/lib а их имена начинаются с lib и заканчиваются .a. Например стандартная библиотека Си называется libc.a (эта библиотека используется всегда и ее указывать не требуется), библиотека математических функций хранится в файле libm.a. При использовании ключа -l нужно указать оригинальную часть имени системной библиотеки, т.е. для использования libm.a нужно указать ключ -lm.
Исходные_модули это имена одного или нескольких файлов с окончанием .c содержащих тексты программ на Си.
Объектные_модули это имена одного или нескольких файлов с расширением .o содержащих объектные модули, которые будут использованы для получения исполняемой программы.

3.1. Введение в библиотеки
Как уже неоднократно упоминалось в предыдущей главе, библиотека - это набор скомпонованных особым образом объектных файлов. Библиотеки подключаются к основной программе во время линковки. По способу компоновки библиотеки подразделяют на архивы (статические библиотеки, static libraries) и совместно используемые (динамические библиотеки, shared libraries). В Linux, кроме того, есть механизмы динамической подгрузки библиотек. Суть динамической подгрузки состоит в том, что запущенная программа может по собственному усмотрению подключить к себе какую-либо библиотеку.

Опция -l, переданная компилятору, обрабатывается и посылается линковщику для того, чтобы тот подключил к бинарнику библиотеку. Как вы уже заметили, у имени библиотеки "обрублены" префикс и суффикс. Это делается для того, чтобы создать "видимое безразличие" между статическими и динамическими библиотеками. Сейчас важно знать лишь то, что и библиотека libfoo.so и библиотека libfoo.a подключаются к проекту опцией -lfoo. В нашем случае libworld.a "урезалось" до -lworld.
Опция -L указывает линковщику, где ему искать библиотеку. В случае, если библиотека располагается в каталоге /lib или /usr/lib, то вопрос отпадает сам собой и опция -L не требуется. В нашем случае библиотека находится в репозитории (в текущем каталоге). По умолчанию линковщик не просматривает текущий каталог в поиске библиотеки, поэтому опция -L. (точка означает текущий каталог) необходима.

-Lкаталог
Добавить каталог в список каталогов, которые содержат объектные библиотечные модули.
-lбиблиотека
При редактировании связей подключить модули из библиотеки.

Библиотека (в программировании, от англ. library) — сборник подпрограмм или объектов для решения близких по тематике задач.
С точки зрения ОС и прикладного ПО библиотеки разделяются на: динамические и статические.
Также называются библиотеки общего пользования или разделяемые библиотеки (англ. shared library) или динамически подключаемые библиотеки (англ. Dynamic Link Library, DLL). Это отдельные файлы, предоставляющие прикладным программам набор наиболее часто используемых функций, и загружаемые на этапе выполнения при обращении программы к ОС с заявкой на выполнение функции из библиотеки. Если запрошенная библиотека уже загружена в ОЗУ, программа будет пользоваться загруженной копией. Такой подход позволяет экономить память, поскольку несколько программ используют одну копию библиотеки, загруженную в память.
Динамические библиотеки хранятся обычно в определенном месте и имеют стандартное расширение. Например, файлы .library в логическом томе Libs: в AmigaOS; в Microsoft Windows и OS/2 файлы библиотек общего пользования имеют расширение .dll; в UNIX‐подобных ОС — обычно .so; в MacOS — .dylib.
При написании программы программисту достаточно указать транслятору языка программирования (компилятору или интерпретатору), что следует подключить такую-то библиотеку и использовать такую-то функцию из указанной библиотеки. Ни исходный текст, ни исполняемый код функции в состав программы не входит.
Могут быть в виде исходного текста, подключаемого программистом к своей программе на этапе написания (например, для языка Fortran существует огромное количество библиотек для решения разных задач именно в исходных текстах), либо в виде объектных файлов, присоединяемых (линкуемых) к исполняемой программе на этапе компиляции (в Microsoft Windows такие файлы имеют расширение .lib, в UNIX‐подобных ОС — обычно .a). В результате программа включает в себя все необходимые функции, что делает её автономной, но увеличивает размер.
DLL (англ. Dynamic-link library — динамически подключаемая библиотека) — понятие операционной системы Microsoft Windows; динамическая библиотека, позволяющая многократное применение различными программными приложениями. K DLL относятся также элементы управления ActiveX и драйверы. В мире UNIX аналогичные функции выполняют т. н. shared objects («разделяемые объекты»).
Первоначально предполагалось, что введение DLL позволит эффективно организовать память и дисковое пространство, используя только одну инстанцию библиотечных модулей для многих приложений. Это было особенно важно для ранних версий Microsoft Windows с жёсткими ограничениями по памяти.
Далее, предполагалось улучшить эффективность разработок и использования системных средств за счёт модульности. Замена DLL-программ с одной версии на другую должна была позволить независимо наращивать систему, не затрагивая приложений. Кроме того, библиотеки DLL могли использоваться разнотипными приложениями — например, Microsoft Office, Microsoft Visual Studio и т. п.
В дальнейшем идея модульности выросла в концепцию COM.
Фактически, полных преимуществ от внедрения DLL получить не удалось по причине явления, называемого DLL_hell («ад DLL»). DLL Hell возникает, когда несколько приложений требуют одновременно различные, не полностью совместимые, версий DLL-библиотек, что приводит к сбоям в этих приложениях. Когда система выросла до определённых размеров, количество DLL стало превышать многие тысячи, не все из них обладали полной надёжностью и совместимостью, и конфликты типа DLL Hell стали возникать очень часто, резко понижая общую надёжность системы. Поздние версии Microsoft Windows стали разрешать параллельное использование разных версий DLL, что свело на нет преимущества изначального принципа модульности.

Константное выражение – это выражение, содержащее только константы. Такие выражения могут вычисляться в ходе компиляции, а не выполнения программы, и соответственно употребляться в любом месте, где допускается применение одной константы:
#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

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

Сокращенный обход право-прошитого бинарного дерева
Сокращенный обход бинарного дерева — разновидность обхода бинарного дерева поиска, позволяющая, используя O(1) дополнительной памяти, обходить все элементы дерева за O(N), где N — количество элементов в дереве. При этом каждый элемент дерева будет просмотрен не больше двух раз.
Прошитое дерево
В общем случае это обычное бинарное дерево, ссылки "лево" и "право" которого вместо того, чтобы равняться null ссылаются на своего "родителя". Таким образом деревья можно пробегать быстрее. Для того, чтобы распознать где нормальная ссылка, а где ссылка на родителя используют дополнительные одну-две переменные в которой хранится данная информация.
Рассмотрим разновидность бинарного дерева поиска. В каждом узле которого, кроме ссылок left, right и parent будем ещё хранить ссылку uplink. Ссылка uplink каждого узла дерева должна удовлетворять следующим свойствам:
если right ≠ null, то uplink = null;
если right = null, то uplink указывает на элемент следующий по величине, если таковой существует.

У наибольшего элемента дерева uplink = null, также как и right = null.

Ссылки left, right имеют то же значение, что и у обычного бинарного дерева поиска.
Операция обхода дерева
Операция обхода прошитого дерева позволяет перечислить все элементы дерева в порядке возрастания ключа за время O(N) и используя O(1) дополнительной памяти.

Операцию обхода прошитого дерева реализуем следующим образом. В качестве стартового элемента возьмем минимальный элемент дерева. Рассмотрим текущий элемент. Если right ≠ null, то следующий по величине элемент за текущим будет минимальный элемент в нашем правом поддереве. Если right = null, то следующий по величине элемент будет элемент uplink. Согласно определению uplink. Если и right = null и uplink = null, то текущий элемент в дереве имеет наибольший ключ и обход дерева можно завершить.

Заметим, что при этом каждый элемент будет просмотрен не больше чем два раза: первый раз при движении к минимальному элементу в правом поддереве некого элемента, а второй раз при переходе по uplink. Т.к. каждый элемент будет просмотрен не больше чем константу раз, а количество элементов N, то время работы алгоритма есть O(N).
Операция вставки в дерево

Операция вставки является аналогичной операции вставки в обычное бинарное дерево поиска, но требует дополнительной корректировки поля uplink. У только что вставленного узла, обозначим его n, поле right = null. Значит uplink должен содержать ссылку на следующий по величине элемент после нашего. Если n — левый сын своего родителя, то следующий по величине за ним элемент будет его родитель. Если n — стал правым сыном своего родителя, то это означает, что у его родителя uplink ≠ null и указывает на следующий после его родителя элемент. Поэтому нам необходимо uplink родителя записать узлу n, а uplink родителя обнулить. Операция вставки в прошитое дерево выполняет на константу операций больше чем в простое бинарное дерево, поэтому работает также O(logN).
Операция удаления из дерева

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

Пусть e лист. Если e является левым сыном своего родителя, то мы можем просто удалить этот элемент из дерева. Если e — правый сын своего родителя, то мы должны наш uplink записать нашему родителю, а затем удалить элемент.

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

Пусть e имеет только левого потомка. Запишем нашего потомка на место удаляемого узла. Т.к. uplink наибольшего элемента в нашем левом поддереве ссылается на элемент e необходимо его модифицировать, чтобы теперь он ссылался на нашего левого потомка.

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

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

Внутреннее упорядочивание оперирует с последовательностями, целиком помещающимися в памяти с произвольным доступом к любой её ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
В современных компьютерах широко применяется подкачка и кэширование памяти. Алгоритм упорядочивания должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
Внешнее упорядочивание оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (дисковые файлы), т.е в данный момент мы "видим" только один элемент. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к особым методам упорядочивания, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем работа с оперативной памятью.
доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим объём данных не позволяет им разместиться в оперативной памяти компьютера.
Принято называть "внешней" сортировкой сортировку последовательных файлов, располагающихся во внешней памяти и слишком больших, чтобы можно было целиком переместить их в основную память и применить один из рассмотренных в предыдущем разделе методов внутренней сортировки. Наиболее часто внешняя сортировка применяется в системах управления базами данных при выполнении запросов, и от эффективности применяемых методов существенно зависит производительность СУБД.

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

В этой и следующей частях книги мы будем обсуждать методы сортировки информации. В общей постановке задача ставится следующим образом. Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (далее мы будем называть его ключом сортировки). Тип данных ключа должен включать операции сравнения ("=", ">", "<", ">=" и "<="). Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.

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

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

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

Основными операциями, выполняемыми над таблицами, являются упорядочение (сортировка) записей и поиск в таблице записи по заданному условию( по ключу ). Сортировка является операцией расстановки записей таблицы в определенном порядке в соответствии с некоторым критерием упорядочения. Сортировка осуществляется в соответствии со значением ключей всех записей (напр., упорядочение фамилий по алфавиту или чисел по возрастанию ). Существует достаточно много методов сортировки, принципиально отличающихся друг от друга. Если таблица целиком помещается в оперативной памяти ЭВМ,то ее упорядочение называют внутренним. Если для хранения упорядочиваемых данных используются внешнее запоминающее устройство, то такое упорядочение называют внешним. Критериями оценки методов сортировки являются :
С - количество операций сравнения пар ключей,
Р - число перестановок элементов ,
S - резерв памяти.

Среднее количество операций сравнения зависит от метода сортировки и при рациональном выборе метода достигает некоторого минимума,зависящего от n - размера таблицы ( размер таблицы - количество содержащихся в ней записей). Методы внутренней сортировки можно разделить на две группы:
- методы, не требующие резерва памяти;
- методы, требующие резерва памяти.

К первой группе относятся такие методы, как метод выборки, "пузырька", вставки, Шелла. Ко второй группе относятся метод квадратичной выборки, метод слияния и другие. Простые методы сортировки (выбором, обменом, вставкой) требуют приблизительно n**2 сравнений. Более сложные алгоритмы обычно обеспечивают получение результата за n*log2(n) сравнений в среднем: сортировка методом Шелла, слиянием, "быстрая сортировка". Однако оптимальной в любом случае сортировки не существует, так как их эффективность существенно зависит от типа ключей в таблице и их предварительной упорядоченности.

Все дело в том, что практически все используемые в настоящее время дисковые устройства снабжены подвижными магнитными головками. При выполнении обмена с дисковым накопителем выполняется подвод головок к нужному цилиндру, выбор нужной головки (дорожки), прокрутка дискового пакета до начала требуемого блока и, наконец, чтение или запись блока. Среди всех этих действий самое большое время занимает подвод головок. Именно это время определяет общее время выполнения операции. Единственным доступным приемом оптимизации доступа к магнитным дискам является как можно более "близкое" расположение на накопителе последовательно адресуемых блоков файла. Но и в этом случае движение головок будет минимизировано только в том случае, когда файл читается или пишется в чисто последовательном режиме. Именно с такими файлами при потребности сортировки работают современные СУБД.

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

Оператор 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

AVL-деревья имеют структуру, похожую на бинарные деревья поиска. Все операции идентичны описанным для бинарных деревьев, за исключением методов Insert и Delete, которые должны постоянно отслеживать соотношение высот левого и правого поддеревьев узла. Для сохранения этой информации мы расширили определение объекта TreeNode, включив поле balanceFactor (показатель сбалансированности), которое содержит разность высот правого и левого поддеревьев.

balanceFactor = height(right subtree) - height(left subtree)

Алгоритм AVL-вставки

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

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

Случай 1. Узел на поисковом маршруте изначально является сбалансированным (balanceFactor = 0). После вставки в поддерево нового элемента узел стал перевешивать влево или вправо в зависимости от того, в какое поддерево была произведена вставка. Если элемент вставлен в левое поддерево, показателю сбалансированности присваивается -1, а если в правое, то 1. Например, на пути 40-50-60 каждый узел сбалансирован. После вставки узла 55 показатели сбалансированности изменяются.

Случай 2. Одно из поддеревьев узла перевешивает, и новый узел вставляется в более легкое поддерево. Узел становится сбалансированным. Сравните, например, состояния дерева до и после вставки узла 55.

Случай 3. Одно из поддеревьев узла перевешивает, и новый узел помещается в более тяжелое поддерево. Тем самым нарушается условие сбалансированности, так как balanceFactor выходит за пределы -1..1. Чтобы восстановить равновесие, нужно выполнить поворот.

template <class T>
void AVLTree<T>::AVLInsert(AVLTreeNode<T>* &tree,
AVLTreeNode<T>* newNode, int &reviseBalanceFactor)
{
// флаг "Показатель сбалансированности был изменен"
int rebalanceCurrNode;

// встретилось пустое поддерево. Пора вставлять новый узел
if (tree == NULL)
{
// вставить новый узел
tree = newNode;

// объявить новый узел сбалансированным
tree->balanceFactor = balanced;

// сообщить об изменении показателя сбалансированности
reviseBalanceFactor = 1;
}
// рекурсивно спускаться по левому поддереву, если новый узел меньше текущего
else if (newNode->data < tree->data)
{
AVLInsert(tree->Left(), newNode, rebalanceCurrNode);
// проверить, нужно ли корректировать balanceFactor
if (rebalanceCurrNode)
{
// вставка слева от узла, перевешивающего влево. будет нарушено
// условие сбалансированности; выполнить поворот (случай 3)
if (tree->balanceFactor == leftheavy)
UpdateLeftTree(tree, reviseBalanceFactor);

// вставка слева от сбалансированного узла.
// узел станет перевешивать влево (случай 1)
else if (tree->balanceFactor == balanced)
{
tree->balanceFactor = leftheavy;
reviseBalanceFactor = 1;
}
// вставка слева от узла, перевешивающего вправо.
// узел станет сбалансированным (случай 2)
else
{
tree->balanceFactor = balanced;
reviseBalanceFactor = 0;
}
}
else
// перебалансировка не требуется. не опрашивать предыдущие узлы
reviseBalanceFactor = 0;
}
// иначе рекурсивно спускаться по правому поддереву
else if (newNode->data < tree->data)
{
AVLInsert(tree->Right(), newNode, rebalanceCurrNode);
// проверить, нужно ли корректировать balanceFactor
if (rebalanceCurrNode)
{
// вставка справа от узла, перевешивающего вправо. будет нарушено
// условие сбалансированности; выполнить поворот (случай 3)
if (tree->balanceFactor == rightheavy)
UpdateRightTree(tree, reviseBalanceFactor);

// вставка справа от сбалансированного узла.
// узел станет перевешивать вправо (случай 1)
else if (tree->balanceFactor == balanced)
{
tree->balanceFactor = rightheavy;
reviseBalanceFactor = 1;
}
// вставка справа от узла, перевешивающего влево.
// узел станет сбалансированным (случай 2)
else
{
tree->balanceFactor = balanced;
reviseBalanceFactor = 0;
}
}
else
// перебалансировка не требуется. не опрашивать предыдущие узлы
reviseBalanceFactor = 0;
}
}

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем;
Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.
Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Трудоемкость худшего случая для этих алгоритмов составляет O(n*log(n)), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.
доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим
объём данных не позволяет им разместиться в ОЗУ

Если некоторый объект объявлен внутри блока, то он видим в этом блоке, и во всех внутренних блоках. Если объект объявлен на внешнем уровне, то он видим от точки его объявления до конца данного исходного файла.
Объект может быть сделан глобально видимым с помощью соответствующих объявлений во всех исходных файлах, образующих программу.
Спецификатор класса памяти в объявлении переменной может быть auto, register, static или extern. Если класс памяти не указан, то он определяется по умолчанию из контекста объявления.
Переменная, объявленная локально с классом памяти extern, является ссылкой на переменную с тем же самым именем, определенную глобально в одном из исходных файлов программы. Цель такого объявления состоит в том, чтобы сделать определение переменной глобального уровня видимым внутри блока.
Пример:
/* объявления переменной i, являющейся именем внешнего
массива длинных целых чисел, на локальном уровне */
/* исходный файл file1.c */
main()
{ ...
}
fun1()
{ extern long i[]; ...
}
/* исходный файл file2.c */
long i[MAX]={0};
fun2()
{ ...
}
fun3()
{ ...
}
Объявление переменной i[] как extern в приведенном примере делает ее видимой внутри функции fun1. Определение этой переменной находится в файле file2.c на глобальном уровне и должно быть только одно, в то время как объявлений с классом памяти extern может быть несколько.
Объявление с классом памяти extern требуется при необходимости использовать переменную, описанную в текущем исходном файле, но ниже по тексту программы, т.е. до выполнения ее глобального определения. Следующий пример иллюстрирует такое использование переменной с именем st.
Пример:
main()
{ extern int st[]; ...
}
static int st[MAX]={0};
fun1()
{ ...
}
Объявление переменной со спецификатором extern информирует компилятор о том, что память для переменной выделять не требуется, так как это выполнено где-то в другом месте программы.

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

Строковый тип (в программировании) — тип данных, значениями которого является произвольная последовательность символов алфавита. Каждая переменная такого типа может быть представлен фиксированным количеством байтов или иметь произвольную длину.
Представление в памяти
Некоторые языки программирования накладывают ограничения на максимальную длину строки, но в большинстве языков подобные ограничения отсутствуют.
Основные проблемы в машинном представлении строкового типа:
строки могут иметь достаточно существенный размер (до нескольких десятков мегабайтов);
изменяющийся со временем размер — возникают трудности с добавлением и удалением символов.
В представлении строк в памяти компьютера существует два принципиально разных подхода.
Представление массивом символов
В этом подходе строки представляются массивом символов; при этом размер массива хранится в отдельной (служебной) области. От названия языка 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 байтов. Последний нулевой байт при определении длины строки не принимается во внимание. Рассмотрим в заключение применение этой функции для вычисления длины строки, вводимой с клавиатуры.

Алгоритм удаления вершины

Для простоты опишем рекурсивный алгоритм удаления. Если вершина - лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления.
Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировки высота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может изменится) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1.
Очевидно, в результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет одного из поддеревьев. Но поиск ближайшего каждый раз требует O(N) операций, отсюда видна очевидная оптимизация: поиск ближайшей вершины производится по краю поддерева. Отсюда количество действий O(lg(N)).

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

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

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

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

template<class T>
void bubbleSort(T a[], long size) {
long i, j;
T x;

for( i=0; i < size; i++) { // i - номер прохода
for( j = size-1; j > i; j-- ) { // внутренний цикл прохода
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
}
}
}
}
Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta(n2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся.

Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Что это значит ?

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

Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.

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

Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.

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

template<class T>
void shakerSort(T a[], long size) {
long j, k = size-1;
long lb=1, ub = size-1; // границы неотсортированной части массива
T x;

do {
// проход снизу вверх
for( j=ub; j>0; j-- ) {
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
k=j;
}
}

lb = k+1;

// проход сверху вниз
for (j=1; j<=ub; j++) {
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
k=j;
}
}

ub = k-1;
} while ( lb < ub );
}

Насколько описанные изменения повлияли на эффективность метода ? Среднее количество сравнений, хоть и уменьшилось, но остается O(n2), в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее) количество операций остается квадратичным.

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

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

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

С помощью утилиты make можно не только быстро создать исполняемый файл, но также и задать некоторые скрипты используя операцию clear: и run: Также можно задать отдельное создание объектного файла и если есть объектный файл, то отдельно создание исполняемого файла. В утилите make объектные файлы и исполняемый файлы можно задать как переменные. Также можно выбрать компилятор.
Рассмотрим пример: есть библиотека stack.h, программа stack.c , где описаны все функции библиотеки stack.h и main файл lab26.c, все они находятся в папке scr. Объектный файл stack.o содержится в папке tmp.

СС=gcc #выбор компилятора
CFALGS= -c -std=c99 -Wall

LD=gcc
LDFLAGS=

all: objects prog #задание целий

objects: ./tmp/stack.o #создание объектного файла

./tmp/stack.o: ./scr/stack.c ./scr/stack.h

$(CC) $(CFALGS) -o ./tmp/stack.o ./scr/stack.c

prog: ./lab26 #исполняемого файла
./lab26: ./scr/lab26.c objects
$(LD) $(LDFLAGS) -o ./lab26 ./scr/lab26.c ./tmp/stack.o

clear: #скрипт удаляет запрашиваемые данные из данный папок
rm -i ./lab26 ./tmp/* ./scr/*~ ./scr/\#* ./scr/*.swp

run:
make all #скрипт создаёт исполняемый файл и тут же запускает его
./lab26

В версии 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.

Красно-черные деревья

Красно-черные деревья - один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева. Оценкой как среднего время, так и наихудшего является O(log n).

Теория

Красно-черное дерево - это бинарное дерево с следующими свойствами:
Каждый узел покрашен либо в черный, либо в красный цвет.
Листьями объявляются NIL-узлы (т.е. "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" NULL указатели). Листья покрашены в черный цвет.
Если узел красный, то оба его потомка черны.
На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.
Количество черных узлов на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с черной высотой 2. Кратчайшее возможное расстояние от корня до листа равно двум - когда оба узла черные. Длиннейшее расстояние от корня до листа равно четырем - узлы при этом покрашены (от корня к листу) так: красный, черный, красный, черный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия черной высоты. Поскольку согласно свойству 3 у красных узлов непременно черные наследники, в подобной последовательности недопустимы и два красных узла подряд. Таким образом, длиннейший путь, который мы можем сконструировать, состоит из чередования красных и черных узлов, что и приводит нас к удвоенной длине пути, проходящего только через черные узлы. Все операции над деревом должны уметь работать с перечисленными свойствами. В частности, при вставке и удалении эти свойства должны сохраниться.

Вставка

Чтобы вставить узел, мы сначала ищем в дереве место, куда его следует добавить. Новый узел всегда добавляется как лист, поэтому оба его потомка являются NIL-узлами и предполагаются черными. После вставки красим узел в красный цвет. После этого смотрим на предка и проверяем, не нарушается ли красно-черное свойство. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево.
Вставив красный узел с двумя NIL-потомками, мы сохраняем свойство черной высоты (свойство 4). Однако, при этом может оказаться нарушенным свойство 3, согласно которому оба потомка красного узла обязательно черны. В нашем случае оба потомка нового узла черны по определению (поскольку они являются NIL-узлами), так что рассмотрим ситуацию, когда предок нового узла красный: при этом будет нарушено свойство 3. Достаточно рассмотреть следующие два случая:

Красный предок, красный "дядя": Ситуацию красный-красный иллюстрирует рис. 1. У нового узла X предок и "дядя" оказались красными. Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить "дедушку" нового узла (узел B), поскольку он может оказаться красным. Обратите внимание на распространение влияния красного узла на верхние узлы дерева. В самом конце корень мы красим в черный цвет корень дерева. Если он был красным, то при этом увеличивается черная высота дерева.

Красный предок, черный "дядя": На рис. 2 представлен другой вариант красно-красного нарушения - "дядя" нового узла оказался черным. Здесь узлы может понадобиться вращать, чтобы скорректировать поддеревья. В этом месте алгоритм может остановиться из-за отсутствия красно-красных конфликтов и вершина дерева (узел A) окрашивается в черный цвет. Обратите внимание, что если узел X был в начале правым потомком, то первым применяется левое вращение, которое делает этот узел левым потомком.
Каждая корректировка, производимая при вставке узла, заставляет нас подняться в дереве на один шаг. В этом случае до остановки алгоритма будет сделано 1 вращение (2, если узел был правым потомком). Метод удаления аналогичен.

Рис. 1: Вставка - Красный предок, красный "дядя

Рис. 2: Вставка - красный предок, черный "дядя"

рисунки здесь http://www.algolist.manual.ru/ds/rbtree.php

Реализация

Операторы typedef T, а также сравнивающие compLT и compEQ следует изменить так, чтобы они соответствовали данным, хранимым в узлах дерева. В каждом узле типа Node хранятся указатели left, right на двух потомков и parent на предка. Цвет узла хранится в поле color и может быть либо RED, либо BLACK. Собственно данные хранятся в поле data. Все листья дерева являются "сторожевыми" (sentinel), что сильно упрощает коды. Узел root является корнем дерева и в самом начале является сторожевым.
Функция insertNode запрашивает память под новый узел, устанавливает нужные значения его полей и вставляет в дерево. Соответственно, она вызывает insertFixup, которая следит за сохранением красно-черных свойств. Функция deleteNode удаляет узел из дерева. Она вызывает deleteFixup, которая восстанавливает красно-черные свойства. Функция findNode ищет в дереве нужный узел.

/* red-black tree */

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

typedef int T; /* type of item to be stored */
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

/* Red-Black tree description */
typedef enum { BLACK, RED } nodeColor;

typedef struct Node_ {
struct Node_ *left; /* left child */
struct Node_ *right; /* right child */
struct Node_ *parent; /* parent */
nodeColor color; /* node color (BLACK, RED) */
T data; /* data stored in node */
} Node;

#define NIL &sentinel /* all leafs are sentinels */
Node sentinel = { NIL, NIL, 0, BLACK, 0};

Node *root = NIL; /* root of Red-Black tree */

void rotateLeft(Node *x) {

/**************************
* rotate node x to left *
**************************/

Node *y = x->right;

/* establish x->right link */
x->right = y->left;
if (y->left != NIL) y->left->parent = x;

/* establish y->parent link */
if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
} else {
root = y;
}

/* link x and y */
y->left = x;
if (x != NIL) x->parent = y;
}

void rotateRight(Node *x) {

/****************************
* rotate node x to right *
****************************/

Node *y = x->left;

/* establish x->left link */
x->left = y->right;
if (y->right != NIL) y->right->parent = x;

/* establish y->parent link */
if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->right)
x->parent->right = y;
else
x->parent->left = y;
} else {
root = y;
}

/* link x and y */
y->right = x;
if (x != NIL) x->parent = y;
}

void insertFixup(Node *x) {

/*************************************
* maintain Red-Black tree balance *
* after inserting node x *
*************************************/

/* check Red-Black properties */
while (x != root && x->parent->color == RED) {
/* we have a violation */
if (x->parent == x->parent->parent->left) {
Node *y = x->parent->parent->right;
if (y->color == RED) {

/* uncle is RED */
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {

/* uncle is BLACK */
if (x == x->parent->right) {
/* make x a left child */
x = x->parent;
rotateLeft(x);
}

/* recolor and rotate */
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateRight(x->parent->parent);
}
} else {

/* mirror image of above code */
Node *y = x->parent->parent->left;
if (y->color == RED) {

/* uncle is RED */
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {

/* uncle is BLACK */
if (x == x->parent->left) {
x = x->parent;
rotateRight(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateLeft(x->parent->parent);
}
}
}
root->color = BLACK;
}

Node *insertNode(T data) {
Node *current, *parent, *x;

/***********************************************
* allocate node for data and insert in tree *
***********************************************/

/* find where node belongs */
current = root;
parent = 0;
while (current != NIL) {
if (compEQ(data, current->data)) return (current);
parent = current;
current = compLT(data, current->data) ?
current->left : current->right;
}

/* setup new node */
if ((x = malloc (sizeof(*x))) == 0) {
printf ("insufficient memory (insertNode)\n");
exit(1);
}
x->data = data;
x->parent = parent;
x->left = NIL;
x->right = NIL;
x->color = RED;

/* insert node in tree */
if(parent) {
if(compLT(data, parent->data))
parent->left = x;
else
parent->right = x;
} else {
root = x;
}

insertFixup(x);
return(x);
}

void deleteFixup(Node *x) {

/*************************************
* maintain Red-Black tree balance *
* after deleting node x *
*************************************/

while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
Node *w = x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateLeft (x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rotateRight (w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
rotateLeft (x->parent);
x = root;
}
} else {
Node *w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateRight (x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
rotateLeft (w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rotateRight (x->parent);
x = root;
}
}
}
x->color = BLACK;
}

void deleteNode(Node *z) {
Node *x, *y;

/*****************************
* delete node z from tree *
*****************************/

if (!z || z == NIL) return;

if (z->left == NIL || z->right == NIL) {
/* y has a NIL node as a child */
y = z;
} else {
/* find tree successor with a NIL node as a child */
y = z->right;
while (y->left != NIL) y = y->left;
}

/* x is y's only child */
if (y->left != NIL)
x = y->left;
else
x = y->right;

/* remove y from the parent chain */
x->parent = y->parent;
if (y->parent)
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
else
root = x;

if (y != z) z->data = y->data;

if (y->color == BLACK)
deleteFixup (x);

free (y);
}

Node *findNode(T data) {

/*******************************
* find node containing data *
*******************************/

Node *current = root;
while(current != NIL)
if(compEQ(data, current->data))
return (current);
else
current = compLT (data, current->data) ?
current->left : current->right;
return(0);
}

void main(int argc, char **argv) {
int a, maxnum, ct;
Node *t;

/* command-line:
*
* rbt maxnum
*
* rbt 2000
* process 2000 records
*
*/

maxnum = atoi(argv[1]);

for (ct = maxnum; ct; ct--) {
a = rand() % 9 + 1;
if ((t = findNode(a)) != NULL) {
deleteNode(t);
} else {
insertNode(a);
}
}
}

Сортировка вставками (англ. insertion sort) — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

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

typedef int array_type; /* или typedef char array_type;*/

void insertSort(array_type a[], int length) {
int i, j;
array_type value;
for (i = 1; i < length; i++) {
value = a[i];
for (j = i-1; (j >= 0) && (a[j] > value); j--) {
a[j+1] = a[j];
}
a[j+1] = value;
}

Функция это независимый набор объявлений и операторов, который обычно разрабатывается для выполнения конкретной задачи. Программы на языке С имеют по крайней мере одну функцию, 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 имя = выражение;

Важным для информатики классом двоичных деревьев являются деревья арифметических выражений с бинарными и унитарными операциями, где каждой операции соответствует вершина, поддеревьями которой являются ее операнды.
Обходя дерево выражений (a+b/c)*(d-e*f) разными способами, мы получаем три различные очереди вершин:
КЛП * + a / b c - d *e f ;
ЛКП a+b / c * d - e * f;
ЛПК a b c / + d e f * - *
которые представляют собой ни что иное, как широко используемые в информатике различные формы записи выражений: префикстную (ассемблер, код операции перед (pre) операндами, называемую также польской), привычную инфикстную (математичекую, знак операции между (in) операндами), но без скобок, задающих порядок выполнения операций, и постфикстную (обратную польскую). Бесскобочная форма записи представляет собой линейную последовательность действий, пригодную для выполнения обычных фон Неймановским компьютером.

Сортировка выбором
Cортировка выбором (англ. selection sort) — алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.
Шаги алгоритма:
1. находим минимальное значение в текущем списке
2. производим обмен этого значения со значением на первой позиции
3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированный первый элемент
Если вы захотите сами изобрести алгоритм сортировки, то вполне вероятно, что вы напишете алгоритм подобный сортировке методом вставок, потому что он, по-видимому, наиболее интуитивно понятный и легко описываемый.
Существует также двунаправленный вариант сортировки методом вставок, в котором на каждом проходе отыскивается и устанавливается на своё место и минимальное, и максимальное значения..
C
for (i = 0; i < n-1; i++) {
min = i;
for (j = i+1; j < n; j++) {
if (x[min] > x[j]) {
min = j;
}
}
temp = x[i];
x[i] = x[min];
x[min] = temp;
}

Сортировка подсчётом — алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.
Описание алгоритма
Идея сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.
Пусть n — длина исходного массива, k — максимальное число в массиве.
Тогда временная сложность алгоритма равна O(n+k), а ёмкостная — O(n+k).
Можно работать и с массивом целых чисел, все элементы которого принадлежат указанному диапазону от min до max. Для оценки сложности получим k = max - min + 1.
C
void CountingSort (int *a, int n, int min, int max)
{
int i, j, c;
int *b;
assert(n > 0);
assert(min <= max);
b = (int *)calloc(max - min + 1, sizeof(int));
assert(b != NULL);
for (i = 0; i <= n - 1; ++i) ++b[a[i] - min];
for (j = min; j <= max; ++j)
{
c = b[j - min];
while (c > 0)
{
*a = j; ++a; --c;
}
}
free(b);
}

Для энтузиастов платформы Alpha-Linux компания Compaq предлагает бесплатную лицензию на компиляторы C (ccc) и C++ (cxx).
Базовая оптимизация достигается вызовом компиляторов с ключом '-fast'.
Compaq С , существующий для Compaq Tru64 UNIX, OpenVMS Alpha, Linux Alpha портирован на FreeBSD Alpha и включен в дерево портов в 2000 г

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

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

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 появилась новая возможность для С - назначенные инициализаторы. Инициализаторы бывают:
инициализаторы для массива;
инициализоторы для структур и объединений;

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

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

Алгоритм Рутисхаузера

Данный алгоритм является одним из наиболее ранних. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявное старшинство операций при этом не учитывается. Например:
D:=((C-(B*L))+K)

Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему пpавилу:

1. если это откpывающаяся скобка или пеpеменная, то значение увеличивается на 1;

2. если знак опеpации или закpывающаяся скобка, то уменьшается на 1.

Для выражения (А+(В+С)) присваивание значений уровня будет происходить следующим образом :
|-------|---------------------------------------|
|N симв.| 1 2 3 4 5 6 7 8 9 |
|-------|---------------------------------------|
|Символы| |
|строки | ( A + ( B * C ) ) |
|-------|---------------------------------------|
|Номера | |
|уровней| 1 2 1 2 3 2 3 2 1 |
|-------|---------------------------------------|

Алгоритм складывается из следующих шагов:

1. выполнить расстановку уровней;

2. выполнить поиск элементов строки с максимальным значением уровня;

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

4. результат вычисления тройки обозначить вспомогательной переменной;

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

6. выполнять п.п.2 - 5 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.
Пример разбора :

|-----------------|-----------------------------------------------|
|Генерируемые| Выражение |
| тройки | |
|-----------------|-----------------------------------------------|
| | ( ( ( ( А + В ) * С ) / D ) - E ) |
| | 0 1 2 3 4 5 4 5 4 3 4 3 2 3 2 1 2 1 0 |
| | |
|+ А В - > R | ( ( ( R * C ) / D ) - E ) |
| | 0 1 2 3 4 3 4 3 2 3 2 1 2 1 0 |
| | |
|* R C -> S | ( ( S / D ) - E ) |
| | 0 1 2 3 2 3 2 1 2 1 0 |
| | |
|-----------------|-----------------------------------------------|

|------------------|-----------------------------------|
|Генерируемые | Выражение |
| тройки | |
|------------------|-----------------------------------|
|/ S D -> Q | ( Q - E ) |
| | 0 1 2 1 2 1 0 |
| | |
|- Q E -> T | T |
|------------------|-----------------------------------|

А построение дерева покажу завтра на пальцах =)
)))

Соpтиpовка Шелла. Это еще одна модификация пyзыpьковой соpтиpовки. Сyть ее состоит в том, что здесь выполняется сpавнение ключей, отстоящих один от дpyгого на некотоpом pасстоянии d. Исходный pазмеp d обычно выбиpается соизмеpимым с половиной общего pазмеpа соpтиpyемой последовательности. Выполняется пyзыpьковая соpтиpовка с интеpвалом сpавнения d. Затем величина d yменьшается вдвое и вновь выполняется пyзыpьковая соpтиpовка, далее d yменьшается еще вдвое и т.д. Последняя пyзыpьковая соpтиpовка выполняется пpи d=1. Качественный поpядок соpтиpовки Шелла остается O(N^2), сpеднее же число сpавнений, опpеделенное эмпиpическим пyтем - log2(N)^2*N. Ускоpение достигается за счет того, что выявленные "не на месте" элементы пpи d>1, быстpее "всплывают" на свои места.
[править] C++
template <class T>
void Shell_sort( T a[], const int n )
{
for(int step = n/2 ; step>0 ; step >>= 1){
for( int i=0; i<(n-step); ++i ){
int j = i;
while ( (j>=0) && (a[j]>a[j+step]) ){
T tmp = a[j];
a[j] = a[j+step];
a[j+step] = tmp;
--j;
}
}
}
}

Ваша программа должна включать стандартный 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, если произошла ошибка.

Эдскер Дейкстра изобрёл алгоритм для преобразования выражений из инфиксной нотации в ОПН. Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. Инфиксная нотация — это форма математических записей, которую использует большинство людей (например, 3 + 4 или 3 + 4 * (2 - 1)). Как и алгоритм вычисления ОПН, алгоритм сортировочной станции основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операторы. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.

Алгоритм построение постфиксной записи из инфиксной(обычной)
Пока есть ещё символы для чтения:
Читаем очередной символ.
Если символ является числом, добавить его к выходной строке.
Если символ является символом функции, помещаем его в стек.
Если символ является разделителем аргументов функции (то есть, запятая):
До тех пор, пока верхним элементом стека не станет открывающаяся скобка, выталкиваем элементы из стека в выходную строку. Если открывающаяся скобка не встретилась, это означает, что в выражении либо неверно поставлен разделитель, либо несогласованы скобки.
Если символ является оператором, о1, тогда:
1) пока…
… (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…
… (если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…
… выталкиваем верхние элементы стека c бо́льшим либо равным приоритетом в выходную строку;
2) помещаем оператор o1 в стек.
Если символ является открывающейся скобкой, помещаем его в стек.
Если символ является закрывающейся скобкой, выталкиваем элементы из стека в выходную строку до тех пор, пока на вершине стека не окажется открывающаяся скобка. При этом открывающаяся скобка удаляется из стека, но в выходную строку не добавляется. Если после этого шага на вершине стека оказывается символ функции, выталкиваем его в выходную строку. Если стек закончился раньше, чем мы встретили открывающуюся скобку, это означает, что в выражении несогласованы скобки.
Когда входная строка закончилась, вытолкнуть все символы из стека в выходную строку. (В стеке должны были остаться только символы операторов; если это не так, значит в выражении несогласованы скобки.)

Простой пример

Вход: 3 + 4

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

Помещаем + (или его Идентификатор) в стек операторов.

Добавим 4 к выходной строке.

Мы прочитали всё выражение, теперь выталкиваем все оставшиеся в стеке операторы в выходную строку. В нашем примере в стеке содержится только +.

Выходная строка: 3 4 +

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

Сложный пример
Приоритеты:
• ^ высокий
• * / средний
• + - низкий

Вход: 3 + 4 * 2 / (1 - 5)^2

Читаем «3»
Добавим «3» к выходной строке
Выход: 3

Читаем «+»
Кладём «+» в стек
Выход: 3
Стек: +

Читаем «4»
Добавим «4» к выходной строке
Выход: 3 4
Стек: +

Читаем «*»
Кладём «*» в стек
Выход: 3 4
Стек: + *

Читаем «2»
Добавим «2» к выходной строке
Выход: 3 4 2
Стек: + *

Читаем «/»
Выталкиваем «*» из стека в выходную строку, кладём «/» в стек
Выход: 3 4 2 *
Стек: + /

Читаем «(»
Кладём «(» в стек
Выход: 3 4 2 *
Стек: + / (

Читаем «1»
Добавим «1» к выходной строке
Выход: 3 4 2 * 1
Стек: + / (

Читаем «-»
Кладём «-» в стек
Выход: 3 4 2 * 1
Стек: + / ( -

Читаем «5»
Добавим «5» к выходной строке
Выход: 3 4 2 * 1 5
Стек: + / ( -

Читаем «)»
Выталкиваем «-» из стека в выходную строку, выталкиваем «(»
Выход: 3 4 2 * 1 5 -
Стек: + /

Читаем «^»
Кладём «^» в стек
Выход: 3 4 2 * 1 5 -
Стек: + / ^

Читаем «2»
Добавим «2» к выходной строке
Выход: 3 4 2 * 1 5 - 2
Стек: + / ^

Конец выражения
Выталкиваем все элементы из стека в строку
Выход: 3 4 2 * 1 5 - 2 ^ / +

Алгоритм построения дерева из постфиксной записи
1) Если не достигнут конец строки ввода, прочитать очередной символ.
2) Создать новую вершину дерева, записать в нее этот символ.
3) Если символ - операция, то:
1) вызвать алгоритм Prefix для левого поддерева;
2) вызвать алгоритм Prefix для правого поддерева.

Итак, мы постепенно переходим от более-менее простых к сложным, но эффективным методам. Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).

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

Пример действий для массива a[0]... a[7]:

44 55 12 42 94 18 06 67 исходный массив
44 55 12 42 67 18 06 |94 94 <-> 67
44 55 12 42 06 18 |67 94 67 <-> 06
44 18 12 42 06 |55 67 94 55 <-> 18
06 18 12 42 |44 55 67 94 44 <-> 06
06 18 12 |42 44 55 67 94 42 <-> 42
06 12 |18 42 44 55 67 94 18 <-> 12
06 |12 18 42 44 55 67 94 12 <-> 12

Вертикальной чертой отмечена левая граница уже отсортированной(правой) части массива.

Рассмотрим оценку количества операций подробнее.
Всего выполняется n шагов, каждый из которых состоит в выборе наибольшего элемента из последовательности a[0]..a[i] и последующем обмене. Выбор происходит последовательным перебором элементов последовательности, поэтому необходимое на него время: O(n). Итак, n шагов по O(n) каждый - это O(n2).

Произведем усовершенствование: построим структуру данных, позволяющую выбирать максимальный элемент последовательности не за O(n), а за O(logn) времени. Тогда общее быстродействие сортировки будет n*O(logn) = O(n log n).

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

Итак, назовем пирамидой(Heap) бинарное дерево высоты k, в котором

* все узлы имеют глубину k или k-1 - дерево сбалансированное.
* при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо, т.е форма пирамиды имеет приблизительно такой вид:
* выполняется "свойство пирамиды": каждый элемент меньше, либо равен родителю.

Как хранить пирамиду? Наименее хлопотно - поместить ее в массив.

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

* в a[0] хранится корень дерева
* левый и правый сыновья элемента a[i] хранятся, соответственнно, в a[2i+1] и a[2i+2]

Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i] >= a[2i+1] и a[i] >= a[2i+2].

Плюсы такого хранения пирамиды очевидны:

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

Запишем в виде массива пирамиду.. Слева-направо, сверху-вниз: 94 67 18 44 55 12 06 42.

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

Фаза 1 сортировки: построение пирамиды

Hачать построение пирамиды можно с a[k]...a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i,j: i = 2i+1 ( или j = 2i+2 )... Просто потому, что такие i,j находятся за границей массива.

Следует заметить, что неправильно говорить о том, что a[k]..a[n] является пирамидой как самостоятельный массив. Это, вообще говоря, не верно: его элементы могут быть любыми. Свойство пирамиды сохраняется лишь в рамках исходного, основного массива a[0]...a[n].

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

Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]..a[n] на элемент a[i] влево:

1. Смотрим на сыновей слева и справа - в массиве это a[2i+1] и a[2i+2] и выбираем наибольшего из них.
2. Если этот элемент больше a[i] - меняем его с a[i] местами и идем к шагу 2, имея в виду новое положение a[i] в массиве. Иначе конец процедуры.

Новый элемент "просеивается" сквозь пирамиду.

template
void downHeap(T a[], long k, long n) {
// процедура просеивания следующего элемента
// До процедуры: a[k+1]...a[n] - пирамида
// После: a[k]...a[n] - пирамида
T new_elem;
long child;
new_elem = a[k];

while(k <= n/2) { // пока у a[k] есть дети
child = 2*k;
// выбираем большего сына
if( child < n && a[child] < a[child+1] )
child++;
if( new_elem >= a[child] ) break;
// иначе
a[k] = a[child]; // переносим сына наверх
k = child;
}
a[k] = new_elem;
}

Учитывая, что высота пирамиды h <= log n, downheap требует O(log n) времени. Полный код процедуры построения пирамиды будет иметь вид:

// вызвать downheap O(n) раз для преобразования массива в пирамиду целиком
for(i=size/2; i >= 0; i--) downHeap(a, i, size-1);

Ниже дана иллюстрация процесса для пирамиды из 8-и элементов:

44 55 12 42 // 94 18 06 67 Справа - часть массива, удовлетворяющая
44 55 12 // 67 94 18 06 42 свойству пирамиды,
44 55 // 18 67 94 12 06 42
44 // 94 18 67 55 12 06 42 остальные элементы добавляются
// 94 67 18 44 55 12 06 42 один за другим, справа налево.

В геометрической интерпретации ключи из начального отрезка a[size/2]...a[n] является листьями в бинарном дереве, как изображено ниже. Один за другим остальные элементы продвигаются на свои места, и так - пока не будет построена вся пирамида.

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

Фаза 2: собственно сортировка

Итак, задача построения пирамиды из массива успешно решена. Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2:

1. Берем верхний элемент пирамиды a[0]...a[n] (первый в массиве) и меняем с последним местами. Теперь "забываем" об этом элементе и далее рассматриваем массив a[0]...a[n-1]. Для превращения его в пирамиду достаточно просеять лишь новый первый элемент.
2. Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента.

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

94 67 18 44 55 12 06 42 // иллюстрация 2-й фазы сортировки
67 55 44 06 42 18 12 // 94 во внутреннем представлении пирамиды
55 42 44 06 12 18 // 67 94
44 42 18 06 12 // 55 67 94
42 12 18 06 // 44 55 67 94
18 12 06 // 42 44 55 67 94
12 06 // 18 42 44 55 67 94
06 // 12 18 42 44 55 67 94

Код внешней процедуры сортировки:

template
void heapSort(T a[], long size) {
long i;
T temp;

// строим пирамиду
for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1);

// теперь a[0]...a[size-1] пирамида

for(i=size-1; i > 0; i--) {
// меняем первый с последним
temp=a[i]; a[i]=a[0]; a[0]=temp;

// восстанавливаем пирамидальность a[0]...a[i-1]
downHeap(a, 0, i-1);
}
}

Каково быстродействие получившегося алгоритма ?

Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения downheap зависит от высоты уже созданной части пирамиды.

Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.

Пирамидальная сортировка не использует дополнительной памяти.

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

Поведение неестественно: частичная упорядоченность массива никак не учитывается.

Логические переменные и выражения
Логические переменные принимают два значения: истина и ложь. Логические, или условные, выражения используются в качестве условия в конструкциях ветвления "если ... то ... иначе ... конец если" и цикла "пока". В первом случае в зависимости от истинности условия выполняется либо ветвь программы после ключевого слова "то", либо после "иначе"; во втором случае цикл выполняется до тех пор, пока условие продолжает оставаться истинным.
В качестве элементарных условных выражений используются операции сравнения: можно проверить равенство двух выражений или определить, какое из них больше. Любая операция сравнения имеет два аргумента и вырабатывает логическое значение "истина" или "ложь. В языке Си приняты следующие обозначения операции сравнения:
• операция проверки равенства двух выражений обозначается двойным знаком равенства == (мы не используем обычный знак равенства во избежание путаницы, поскольку часто знак равенства применяется для обозначения операции присваивания);
• неравенство обозначается != (в Си восклицательный знак используется для отрицания);
• для сравнения величин выражений применяются четыре операции больше >, больше или равно `>=, меньше <, меньше или равно <=.
Несколько примеров логических выражений:
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" - нет. Программисты очень часто сознательно используют эту особенность реализации логических операций.

Быстрая сортировка
Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Самый быстрый из известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов).
Алгоритм
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать либо средний по положению элемент (элемент с индексом [n/2], тогда алгоритм будет работать за время O(n log n) в худшем случае), либо элемент со случайно выбранным индексом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
1. два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;
2. вычисляется опорный элемент m;
3. индекс l последовательно увеличивается до m или до тех пор, пока l-й элемент не превысит опорный;
4. индекс r последовательно уменьшается до m или до тех пор, пока r-й элемент не окажется меньше опорного;
5. если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент;
6. если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.
Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты.
Оценка эффективности
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь меняются местами наиболее удалённые друг от друга элементы массива. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате самый эффективный улучшенный метод.
• Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения CN = 2CN/2+N. Это дало бы наименьшее время сортировки.
• Среднее. Даёт в среднем O(n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
На практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2CN/2 покрывает расходы по сортировке двух полученных подмассивов; N — это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно CN = N lg N.
• Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
Худший случай даёт O(n²) обменов, но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.
[править] Достоинства и недостатки
Достоинства:
• Самый быстродействующий из всех существующих алгоритмов обменной сортировки — быстрее него только специализированные алгоритмы, использующие специфику сортируемых данных.
• Простая реализация.
• Хорошо сочетается с алгоритмами кэширования и подкачки памяти.
• Хорошо работает на «почти отсортированных» данных — если исходный массив уже близок к отсортированному, алгоритм не приводит к излишним перестановкам уже стоящих в правильном порядке элементов.
Недостатки:
• При классической реализации требует в худшем случае много дополнительной памяти. Правда, вероятность возникновения худшего случая ничтожна.
• Неустойчив — если требуется устойчивость, приходится расширять ключ.
C
Первый вариант Работает для любых чисел
int partition (mytype * m, int a, int b)
{
int i = a;
for (int j = a; j <= b; j++) // просматриваем с a по b
{
if (m[j] <= m[b]) // если элемент a[j] не превосходит a[b],
{
swap(m[i], m[j]); // меняем местами a[j] и a[a], a[a+1], a[a+2] и так далее...
// то есть переносим элементы меньшие a[b] в начало, а затем и сам a[b] «сверху»
i++; // таким образом последний обмен: a[b] и a[i], после чего i++
}
}
return i-1; // в индексе i хранится <новая позиция элемента a[b]> + 1
}

void quicksort (mytype * m, int a, int b) // a - начало подмножества, b - конец
{ // для первого вызова: a = 0, b = <элементов в массиве> - 1
if (a >= b) return;
int c = partition (m, a, b);
quicksort (m, a, c-1);
quicksort (m, c+1, b);
}

При использовании рекурсивного кода, быстрая сортировка будет означать n вложенных рекурсивных вызовов функции quickSort. Каждый рекурсивный вызов означает сохранение информации о текущем положении дел. Таким образом, сортировка требует O(n) дополнительной памяти.. И не где-нибудь, а в стеке. При достаточно большом n такое требование может привести к непредсказуемым последствиям. Для исключения подобной ситуации можно заменить рекурсию на итерации, реализовав стек на основе массива. Процедура разделения будет выполняться в виде цикла. Каждый раз, когда массив делится на две части, в стек будет направляться запрос на сортировку большей из них, а меньшая будет обрабатываться на следующей итерации. Запросы будут выбираться из стека по мере освобождения процедуры разделения от текущих задач. Сортировка заканчивает свою работу, когда запросы кончаются.
Псевдокод.
Итеративная QuickSort (массив a, размер size) {
Положить в стек запрос на сортировку массива от 0 до size-1.

do {
Взять границы lb и ub текущего массива из стека.
do {
1. Произвести операцию разделения над текущим массивом a[lb..ub].
2. Отправить границы большей из получившихся частей в стек.
3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.
} пока меньшая часть состоит из двух или более элементов
} пока в стеке есть запросы
}
Реализация на Си.
#define MAXSTACK 2048 // максимальный размер стека

template<class T>
void qSortI(T a[], long size) {
long i, j; // указатели, участвующие в разделении
long lb, ub; // границы сортируемого в цикле фрагмента
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
T pivot; // опорный элемент
T temp;
lbstack[1] = 0;
ubstack[1] = size-1;
do {
// Взять границы lb и ub текущего массива из стека.
lb = lbstack[ stackpos ];
ub = ubstack[ stackpos ];
stackpos--;
do {
// Шаг 1. Разделение по элементу pivot
ppos = ( lb + ub ) >> 1;
i = lb; j = ub; pivot = a[ppos];
do {
while ( a[i] < pivot ) i++;
while ( pivot < a[j] ) j--;
if ( i <= j ) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i <= j );
// Сейчас указатель i указывает на начало правого подмассива,
// j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
// Возможен случай, когда указатель i или j выходит за границу массива
// Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub
if ( i < ppos ) { // правая часть больше
if ( i < ub ) { // если в ней больше 1 элемента - нужно
stackpos++; // сортировать, запрос в стек
lbstack[ stackpos ] = i;
ubstack[ stackpos ] = ub;
}
ub = j; // следующая итерация разделения
// будет работать с левой частью
} else { // левая часть больше
if ( j > lb ) {
stackpos++;
lbstack[ stackpos ] = lb;
ubstack[ stackpos ] = j;
}
lb = i;
}
} while ( lb < ub ); // пока в меньшей части более 1 элемента
} while ( stackpos != 0 ); // пока есть запросы в стеке
}
Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

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

Сортировка слиянием также построена на принципе "разделяй-и-властвуй", однако реализует его несколько по-другому, нежели quickSort. А именно, вместо разделения по опорному элементу массив просто делится пополам.
// a - сортируемый массив, его левая граница lb, правая граница ub
template
void mergeSort(T a[], long lb, long ub) {
long split; // индекс, по которому делим массив

if (lb < ub) { // если есть более 1 элемента

split = (lb + ub)/2;

mergeSort(a, lb, split); // сортировать левую половину
mergeSort(a, split+1, last);// сортировать правую половину
merge(a, lb, split, ub); // слить результаты в общий массив
}
}

Функция merge на месте двух упорядоченных массивов a[lb]...a[split] и a[split+1]...a[ub] создает единый упорядоченный массив a[lb]...a[ub].

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

Один из способов состоит в слиянии двух упорядоченных последовательностей при помощи вспомогательного буфера, равного по размеру общему количеству имеющихся в них элементов. Элементы последовательностей будут перемещаться в этот буфер по одному за шаг.
merge ( упорядоченные последовательности A, B , буфер C ) {
пока A и B непусты {
cравнить первые элементы A и B
переместить наименьший в буфер
}
если в одной из последовательностей еще есть элементы
дописать их в конец буфера, сохраняя имеющийся порядок
}

Результатом является упорядоченная последовательность, находящаяся в буфере. Каждая операция слияния требует n пересылок и n сравнений, где n - общее число элементов, так что время слияния: Theta(n).
template
void merge(T a[], long lb, long split, long ub) {
// Слияние упорядоченных частей массива в буфер temp
// с дальнейшим переносом содержимого temp в a[lb]...a[ub]

// текущая позиция чтения из первой последовательности a[lb]...a[split]
long pos1=lb;

// текущая позиция чтения из второй последовательности a[split+1]...a[ub]
long pos2=split+1;

// текущая позиция записи в temp
long pos3=0;

T *temp = new T[ub-lb+1];

// идет слияние, пока есть хоть один элемент в каждой последовательности
while (pos1 <= split && pos2 <= ub) {
if (a[pos1] < a[pos2])
temp[pos3++] = a[pos1++];
else
temp[pos3++] = a[pos2++];
}

// одна последовательность закончилась -
// копировать остаток другой в конец буфера
while (pos2 <= ub) // пока вторая последовательность непуста
temp[pos3++] = a[pos2++];
while (pos1 <= split) // пока первая последовательность непуста
temp[pos3++] = a[pos1++];

// скопировать буфер temp в a[lb]...a[ub]
for (pos3 = 0; pos3 < ub-lb+1; pos3++)
a[lb+pos3] = temp[pos3];

delete temp[ub-lb+1];
}

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

Библиотечные средства обработки списков в С++
Контейнерные классы в С++ – это классы предназначенные для хранения данных, организованных определенным образом. К этим классам, в частности, относятся массивы, стеки и списки. Для каждого типа контейнера определены методы для работы с его элементами, не зависящие от конкретного типа данных, поэтому один и тот же тип контейнера можно использовать для хранения данных различных типов. Эта возможность реализована с помощью стандартной библиотекой шаблонов (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

В случае прямого слияния мы не получаем никакого преимущества, если данные уже
являются частично упорядоченными. Размер сливаемых при каждом проходе
последовательностей не зависит от существования более длинных уже упорядоченных
последовательностей, которые можно было бы просто объединить.
Сортировка, при которой всегда сливаются две самые длинные из возможных
последовательностей, назвается естественным слиянием.
Эта сортировка является двухфазной сортировкой слиянием с тремя
лентами(файлами).
Максимальную упорядоченную последовательность будем называть серией.
Пусть имеется начальный файл А. Каждый проход состоит из фазы распределения
серий из фалйа А поровну в файлы В и С и фазы слияния, объединяющей серии из
файлов В и С в файл А.
Процесс сортировки заканчивается, как только в файле А останется только одна
серия.
Рассмотрим сортировку естественным слиянием на примере (серии подчеркнуты).
Пусть задан файл А:

А - 17 31 05 59 13 41 43 76 11 23 29 47 03 07 71 02 19 57 37
61

B - 17 31 13 41 43 76 03 07 71 37 61

C - 05 59 11 23 29 47 02 19 57

A - 05 17 31 59 11 13 23 29 41 43 47 76 02 03 07 19 57 71 37 61

B - 05 17 31 59 02 03 07 19 57 71

C - 11 13 23 29 41 43 47 76 37 61

A - 05 11 13 17 23 29 31 41 43 47 59 76 02 03 07 19 37 57 61 71

B - 05 11 13 17 23 29 31 41 43 47 59 76

C - 02 03 07 19 37 57 61 71

A - 02 03 05 07 11 13 17 19 23 29 31 37 41 43 47 57 59 61 71 76
Hа основе рассмотренного выше алгоритма легко получить алгоритм однофазной
сортировки естественным слиянием с четырьмя файлами.

Библиотечные средства обработки списков в 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);
}
}

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

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

*********** сортировка с помощью двоичного дерева *************/
#include
#include
typedef struct tree
{
int a; // данные
struct tree *left; // левый сын
struct tree *right; // правый сын

} TREE;

TREE *add_to_tree(TREE *root, int new_value)
{
if (root==NULL) // если нет сыновей - создаем новый элемент
{
root = (TREE*)malloc(sizeof(TREE));
root->a = new_value;
root->left = root->right = 0;
return root;
}
if (root->a < new_value) // добавлем ветвь
root->right = add_to_tree(root->right, new_value);
else
root->left = add_to_tree(root->left, new_value);
return root;
}

void tree_to_array(TREE *root, int a[]) // процедура заполнения массива
{
static max2=0; // счетчик элементов нового массива
if (root==NULL) return; // условие окончания - нет сыновей
tree_to_array(root->left, a); // обход левого поддерева
a[max2++] = root->a;
tree_to_array(root->right, a); // обход правого поддерева
free(root);
}

void sort_tree(int a[], int elem_total) // собственно сортировка
{
TREE *root;
int i;
root = NULL;
for (i=0; i < max; i++)
root = add_to_tree(root, a[i]);
tree_to_array(root, a); // заполнение массива
}
/* тестовая программа */

void main() {
int i;
/* Это будем сортировать */
int a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
sort_tree(a, 14);

printf("sorted array:\n");
for (i=0;i<14;i++) printf("%d ",a[i]);
}

В Прологе список (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). В этом списке первый элемент это знак плюс +, за которым следуют два числа, разделенные пробелами.
В Лиспе и данные, и программы представляются одинаковым образом, то есть в виде списков, состоящих из слов, чисел или других списков, разделенные пробельными символами и окруженные круглыми скобками. (Так как программы выглядят как данные, то одна программа легко может служить данными для другой программы --- это очень мощное свойство Лиспа). (Кстати, эти два замечания в скобках не являются допустимыми списками Лиспа, поскольку они содержат знаки препинания `;' и `.').
Вот другой список, в этот раз со списком внутри себя:
'(этот список содержит список (внутри себя))
Элементами этого списка являются слова `этот', `список', `содержит' и список `(внутри себя)'. Внутренний список составлен из слов `внутри', `себя'.
*/