Int* keys; // An array of keys

Int t; // Minimum degree (defines the range for number

// of keys)

BTreeNode** C; // An array of child pointers

Int n; // Current number of keys

bool leaf; // Is true when node is leaf. Otherwise fals

}

class BTree {

BTreeNode* root; // Pointer to root node

int t; // Minimum degree

}

13. Графы, способы представления.

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

Есть 4 способа представления графа:

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

2. список смежности - список вершин графа, хранящих в себе список смежных вершин. Идеально для разреженного (sparse) графа.

3. Список ребер - компактный способ хранения графа. Удобен для передачи данных.

4. Матрица инцидентности - Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа. В ячейку матрицы на пересечении строки i со столбцом j записывается:1 в случае, если связь j «выходит» из вершины i, −1, если связь «входит» в вершину, 0 во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине). Требует очень много памяти для хранения, потому применяется редко.

14. Сортировка вставками (включением),сортировка Шелла.

Сортировка вставками:

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

void insertionsort(int *arr, int size)

{

for(int i = 1; i < size; ++i)

for(int j = i; j > 0 && arr[j-1] > arr[j]; --j) // пока j > 0 и элемент j-1 > j

swap(arr[j-1], arr[j]); // меняем местами элементы j и j-1

}

сложность: О( )

Источник: https://habr.com/ru/articles/181271/

Сортировка Шелла:

Идея сортировки заключается в сравнении разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно gap или size/2, где size — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии size/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние gap сокращается на gap/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на gap=1 проход по массиву происходит в последний раз.

void shellsort(int* arr, int size)

{

for (int gap = size / 2; gap > 0; gap /= 2)

{

for (int i = gap; i < size; i += 1)

{

//сортировка подсписков, созданных с помощью gap

int temp = arr[i];

int j;

for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)

arr[j] = arr[j - gap];

arr[j] = temp;

}

}

}

сложность: О( )