Короткие примеры C++ кода-1 Кувшинов Д

if (list == slow)

return true;
// Один шаг по slow.

slow = slow->next;

}

}
// Тест работоспособности has_loop.

int test_has_loop()

{

// Незакольцованный список.

Link a, b, c, d, e;

a.next = &b;

b.next = &c;

c.next = &d;

d.next = &e;

if (has_loop(&a))

return 1;
// Закольцованный список.

e.next = &a;

if (!has_loop(&a))

return 2;
// "Лассо".

e.next = &c;

if (!has_loop(&a))

return 3;

return 0;

}

///////////////////////////////////////////////////////////////////////////////

// Сортировка списка слияниями

// Требует O(N log N) время и O(1) память.
// Вспомогательная функция: возвращает указатель на звено с минимальным значением.

// Продвигает переменную, указывающую на возвращённое звено на следующую позицию.

inline Link* merging_next(Link *&a, Link *&b)

{

assert(a && b);

auto result = a;

if (b->value < a->value)

{

result = b;

b = b->next;

}

else

a = a->next;

return result;

}
// Слияние двух упорядоченных списков в один упорядоченный список.

Link* merge(Link *a, Link *b)

{

// Если один из списков пуст...

if (!a)

return b;

if (!b)

return a;
// Оба непусты: головой нового списка будет голова с меньшим значением.

for (auto head = merging_next(a, b), tail = head;;)

{

if (!a)

{

tail->next = b;

return head;

}
if (!b)

{

tail->next = a;

return head;

}
tail = tail->next = merging_next(a, b);

}

}
// Найти элемент перед средним элементом списка.

Link* list_premiddle(Link *list)

{

// Два шага по list -- один шаг по mid.

for (auto premid = list, mid = premid;;)

{

if (!list)

return premid;

list = list->next;

if (!list)

return premid;

list = list->next;

premid = mid;

mid = mid->next;

}

}
// Собственно сортировка слияниями (рекурсивный нисходящий вариант).

// Возвращает новую голову исходного списка.

Link* merge_sort(Link *list)

{

// Менее двух элементов?

if (!list || !list->next)

return list;
// Разрезать на два списка посередине.

auto premid = list_premiddle(list);

auto tail = premid->next;

premid->next = nullptr;

// Отсортировать списки по отдельности.

list = merge_sort(list);

tail = merge_sort(tail);

// Слить в общий и вернуть.

return merge(list, tail);

}

///////////////////////////////////////////////////////////////////////////////

// Тестирование работоспособности сортировки

#include

#include

#include

#include

using namespace std;
// Генерирует случайные списки, сортирует и сравнивает с результатом стандартной сортировки на исходном массиве.

int test_merge_sort()

{

mt19937_64 rng(5151);

uniform_int_distribution vg;
static const auto MAX_LENGTH = 2049;

vector reference;
for (int i = 0; i < MAX_LENGTH; ++i)

{

// Заполнить референс-массив.

reference.resize(i);

for (auto &item : reference)

item = vg(rng);



// Скопировать массив в новый список.

auto list = list_from_array(reference.data(), reference.size());
// Отсортировать и то и другое.

sort(reference.begin(), reference.end());

list = merge_sort(list);
// Сравнить на равенство содержимое массива и списка.

bool error = false;

auto pos = list;

for (auto &item : reference)

{

if (item != pos->value)

{

error = true;

break;

}
pos = pos->next;

}
// Удалить список.

delete_list(list);
// Нашли ошибку?

if (error)

return i+1;

}
return 0;

}

int main()

{

cout << "test_has_loop: " << test_has_loop() << endl;

cout << "test_merge_sort: " << test_merge_sort() << endl;

return EXIT_SUCCESS;

}

0850-quick_sort.cpp

// quick_sort.cpp

// Быстрая сортировка (рекурсивный вариант, вариант с одной веткой рекурсии и вариант с явным стеком).

// Сортирует массивы целых.

#include

#include

using namespace std;
// Выполнить обмен значениями двух целочисленных ячеек памяти (переменных).

void swap(int &a, int &b)

{

int t = a;

a = b;

b = t;

}
// Разделить элементы массива a (перемещая их внутри массива) на две части:

// Левая часть: все элементы a, меньшие key.

// Правая часть: все элементы a, не меньшие key.

// Возвращает размер левой части (т.е. индекс первого элемента правой части).

// Левая часть может быть пустой (массив не содержит элементов, меньших key),

// в этом случае функция возвращает 0.

// Предполагается, что массив не пуст (n != 0), и значение key содержится в массиве, поэтому

// правая часть пустой быть не может и результат функции обязательно меньше n.

size_t qpartition(int a[], size_t n, int key)

{

assert(n != 0);

// Движемся в массиве с левого конца (указатель l) вправо

// и с правого конца (указатель r) влево.

int *l = a, *r = a + n - 1;

// Говорим, что "произошло пересечение", если случается ситуация r <= l.

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

while (true)

{

// Установим l на следующую позицию, в которой находится элемент, не меньший key.

while (*l < key)

if (r < ++l) // Произошло пересечение?

return l - a;
// Установим r на следующую позицию, в которой находится элемент, меньший key.

while (!(*r < key))

if (--r < l) // Произошло пересечение?

return l - a;
// Все элементы слева от l меньше key.

// Элемент по адресу l не меньше key.

// Все элементы справа от r не меньше key.

// Элемент по адресу r меньше key.

// Обменять элементы на позициях l и r.

swap(*l, *r);
// Переместить l и r на следующие позиции и проверить наличие пересечения.

if (--r <= ++l)

{

// Может возникнуть ситуация, когда между l и r находился один элемент,

// меньший key. В этом случае, его надо отнести к левой половине.

if (*l < key) ++l;

return l - a;

}

}

}

// Быстрая сортировка, рекурсивный вариант.

// Сортирует массив a на месте.

void quick_sort(int a[], size_t n)

{

if (n > 1)

{

// Выберем в качестве ключа элемент посередине массива

// (можно выбирать любой элемент, средний -- произвольный выбор автора)

// и выполним разделение по нему.

size_t left_n = qpartition(a, n, a[n / 2]);

if (left_n == 0)

{

// Все элементы a не меньше, чем средний элемент,

// т.е. средний элемент равен минимуму из всех элементов массива.

// В этом случае qpartition не изменяет исходный массив.

// Обменяем средний элемент массива с начальным.

swap(a[0], a[n / 2]);

// Отсортируем рекурсивно оставшуюся часть из n - 1 элемента.

quick_sort(a + 1, n - 1);

}

else

{

// Удалось разделить массив на две части.

// Так как любой элемент из левой части меньше любого элемента из правой части,

// то теперь достаточно независимо отсортировать обе части,

// что мы и выполним рекурсивно.

quick_sort(a, left_n);

quick_sort(a + left_n, n - left_n);

}

}

}

// Быстрая сортировка, рекурсивный вариант с раскрытием одной ветки рекурсии в цикл.

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

// позволяет избежать переполнения стека вызовов (полностью рекурсивный вариант,

// приведённый выше, может выполнять до n вложенных рекурсивных вызовов).

void quick_sort_tc(int a[], size_t n)

{

// Пока есть что сортировать.

while (n > 1)

{

// Выполним разделение диапазона по среднему элементу.

size_t left_n = qpartition(a, n, a[n / 2]);
if (left_n == 0)

{

// Разделить не удалось, т.к. средний элемент равен минимуму всех элементов.

// Обменяем его с начальным элементом,

swap(a[0], a[n / 2]);

// а на следующей итерации цикла начнём сортировать оставшуюся часть.

++a;

--n;

}

else if (left_n < n - left_n)

{

// Левая часть меньше правой, отсортируем её рекурсивно.

quick_sort_tc(a, left_n);

// Правую часть отсортируем в цикле.

a += left_n;

n -= left_n;

}

else

{

// Правая часть не больше левой, отсортируем её рекурсивно.

quick_sort(a + left_n, n - left_n);

// Левую часть отсортируем в цикле.

n = left_n;

}

}

}

// Быстрая сортировка, вариант с раскрытием одной ветки в цикле и явным стеком отложенных веток.

void quick_sort_s(int a[], size_t n)

{

// Предполагаем, что размер адреса не превосходит 64 бит.

// Благодаря тому, что откладываются только "меньшие" части,

// глубина стека не может превзойти 64.

struct {

int *a;

size_t n;

} ds[64];
size_t sp = 0; // Количество элементов, помещённых в стек.

while (true)

{

while (n > 1)

{

// Выполним разделение диапазона по среднему элементу.

size_t left_n = qpartition(a, n, a[n / 2]);
if (left_n == 0)

{

// Разделить не удалось, обменяем начальный элемент со средним

swap(a[0], a[n / 2]);

// и будем дальше сортировать оставшиеся.

++a;

--n;

}

else if (left_n < n - left_n)

{

// Вместо выполнения рекурсивного вызова для левой (меньшей) части

// отложим её в стек.

auto &t = ds[sp++];

t.a = a;

t.n = left_n;
// Дальше сортируем правую часть.

a += left_n;

n -= left_n;

}

else

{

// Вместо выполнения рекурсивного вызова для правой части

// отложим её в стек.

auto &t = ds[sp++];

t.a = a + left_n;

t.n = n - left_n;
// Дальше сортируем левую часть.

n = left_n;

}

}
// Нет отложенных задач? Завершить работу.

if (sp == 0)

return;
// Есть отложенные задачи. Извлечь самую верхнюю из них.

auto &t = ds[--sp];

a = t.a;

n = t.n;

}

}

0860-bitmap_works.cpp

// bitmap_works.cpp

// Поиск в глубину и поиск в ширину на картинке:

// заливка связной области картинки заданным цветом,

// обведение контуром заданной ширины (сглаживание не реализовано).

// Загружает и сохраняет 32-битные BMP без сжатия.

#include

#include // size_t

#include

#include // uint32_t etc

#include // memcpy

#include // swap

#include

#include

#include

/// Тип "цвет". Синоним 32-битного беззнакового целого.