/**********
* Сортировки выбором, слиянием и
* пирамидальная, быстрая на Си
* evgeniy-korniloff@yandex.ru
* 2025
*****************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int v[],int a,int b){ int t = v[a];v[a]=v[b];v[b]=t;}
void init_rnd(int v[],int n, int max){
srand(time(0));
while(--n>=0)v[n]=rand()%(max+1);
}
void print_arr(int v[],int n){
int j;
for(j=0;j<n;j++)
printf("%d, ",v[j]);
printf("\n");
}
int check_array(int v[],int n){
int j;
for(j=0;j<n-1;j++)
if(v[j]<v[j+1])return 0;
return 1;
}
//////
int foo=0;
void sort_buble(int v[],int n){
int j,k,find;
for(j=0;j<n;j++)
{
find=0;
for(k=n-1;k>j;k--)
{
if(v[k]>v[k-1]){
swap(v,k,k-1);
find=1;
//??
foo++;
}
}
if(!find) return;
}
}
void QsortHelper(int v[],int a,int b, int min, int max){
void sort_buble(int v[],int n);
int mid,k,j;
if(b-a<5 || max-min<3){
sort_buble(&v[a],b-a+1);
return;
}
mid = min + (max-min)/2;
k=a;
for(j=a;j<=b;j++){
if(v[j]>mid) swap(v,k++,j);
}
QsortHelper(v,a,k-1,mid+1,max);
QsortHelper(v,k,b,min,mid);
}
void Qsort(int v[],int n){
int j,min,max;
if(n<2) return;
min=max=v[0];
for(int j=0;j<n;j++){
if(v[j]<min){ min=v[j];}
if(v[j]>max){ max=v[j];}
}
QsortHelper(v,0,n-1,min,max);
}
//////////
void sort_vibor(int v[],int n){
int j,k,max,max_i;
for(j=0;j<n-1;j++){
max=v[j]; max_i=j;
for(k=j+1;k<n;k++){
if(v[k]>max){
max=v[k];
max_i=k;
}
}
if(max_i!=j) swap(v,j,max_i);
}
}
///////////
void sort_sliyaniem(int v[], int n){
if(n<6) sort_vibor(v,n);
else{
int j,i,q,w,e;
int d = n/2+1;
int a[d], b[d];
for(j=0;j<d;j++) a[j]=v[j];
for(j=d,i=0; j<n; j++,i++) b[i]=v[j];
sort_sliyaniem(a,d);
sort_sliyaniem(b,i);
for(q=0,w=0,e=0;q<d && w<i;){
if(a[q]>b[w]){
v[e++] = a[q++];
}else{
v[e++] = b[w++];
}
}
while(q<d) v[e++] = a[q++];
while(w<i) v[e++] = b[w++];
}
}
void heap_sort_shift_down(int v[],int b, int n){
int j,i,max_i;
do{
j = b*2 + 1;
i = b*2 + 2;
if(j>=n && i>=n) return;
if(j>=n) max_i=i;
else if(i>=n) max_i=j;
else max_i = v[j]>v[i]? j:i;
if(v[max_i] <= v[b]) return;
swap(v,b,max_i);
b = max_i;
}while(1);
}
//один лучший гарантированно наверх
void heap_sort(int v[],int n){
int b;
for(b=n/2+1;b>=0;b--)
heap_sort_shift_down(v,b,n);
}
int pick(int v[],int *N,int *best){
int n = *N;
if(n<=0)return 0;
if(n==1){*best=v[0];(*N)--;return 1;};
*best = v[0];
v[0] = v[n-1];
heap_sort_shift_down(v,0,n-1);
(*N)--;
*best = v[0];
return 1;
}
#define N 2000000
int v[N];
int main(){
init_rnd(v,N,N);
//sort_buble(v,N);
Qsort(v,N);
/***
do{
heap_sort(v,N);
int n = N,best;
while(n>0){
pick(v,&n,&best);
printf("%d, ",best);
}
printf("\n");
}while(0);
***/
// print_arr(v,N);
printf("check_array: %d\n", check_array(v,N));
printf("? %d\n",foo);
return 0;
}
среда, 25 июня 2025 г.
Сортировки выбором, слиянием и пирамидальная, быстрая на Си
вторник, 24 июня 2025 г.
Двоичное дерево поиска
#include <stdio.h>
#include <stdlib.h>
// Структура узла дерева
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
// Создание нового узла
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Ошибка выделения памяти!\n");
exit(1);
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Вставка значения в дерево
Node* insert(Node* root, int value) {
if (root == NULL) {
return createNode(value);
}
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root;
}
// Поиск значения в дереве
Node* search(Node* root, int value) {
if (root == NULL || root->data == value) {
return root;
}
if (value < root->data) {
return search(root->left, value);
}
return search(root->right, value);
}
// Нахождение минимального значения в дереве
Node* findMin(Node* root) {
while (root != NULL && root->left != NULL) {
root = root->left;
}
return root;
}
// Удаление узла из дерева
Node* deleteNode(Node* root, int value) {
if (root == NULL) {
return root;
}
if (value < root->data) {
root->left = deleteNode(root->left, value);
} else if (value > root->data) {
root->right = deleteNode(root->right, value);
} else {
// Узел с одним потомком или без потомков
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
// Узел с двумя потомками
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Обход дерева в порядке "in-order" (левый-корень-правый)
void inOrderTraversal(Node* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
// Обход дерева в порядке "pre-order" (корень-левый-правый)
void preOrderTraversal(Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// Обход дерева в порядке "post-order" (левый-правый-корень)
void postOrderTraversal(Node* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
}
// Освобождение памяти, занятой деревом
void freeTree(Node* root) {
if (root != NULL) {
freeTree(root->left);
freeTree(root->right);
free(root);
}
}
int main() {
Node* root = NULL;
// Вставка элементов
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("In-order обход: ");
inOrderTraversal(root);
printf("\n");
printf("Pre-order обход: ");
preOrderTraversal(root);
printf("\n");
printf("Post-order обход: ");
postOrderTraversal(root);
printf("\n");
// Поиск элемента
int key = 60;
Node* found = search(root, key);
if (found != NULL) {
printf("Элемент %d найден в дереве.\n", key);
} else {
printf("Элемент %d не найден в дереве.\n", key);
}
// Удаление элемента
printf("Удаляем элемент 20\n");
root = deleteNode(root, 20);
printf("In-order обход после удаления: ");
inOrderTraversal(root);
printf("\n");
// Освобождение памяти
freeTree(root);
return 0;
}
Красно-черное дерево на Си
Красно-черное дерево на Си
Красно-черное дерево - это самобалансирующееся бинарное дерево поиска, которое гарантирует логарифмическую высоту дерева и эффективные операции вставки, удаления и поиска.
Вот пример реализации красно-черного дерева на языке Си:
#include <stdio.h> #include <stdlib.h> // Определение цвета узла typedef enum { RED, BLACK } Color; // Структура узла красно-черного дерева typedef struct Node { int data; Color color; struct Node *left, *right, *parent; } Node; // Создание нового узла Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->color = RED; // Новый узел всегда красный newNode->left = newNode->right = newNode->parent = NULL; return newNode; } // Вспомогательная функция для левого поворота void leftRotate(Node **root, Node *x) { Node *y = x->right; x->right = y->left; if (y->left != NULL) y->left->parent = x; y->parent = x->parent; if (x->parent == NULL) *root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; } // Вспомогательная функция для правого поворота void rightRotate(Node **root, Node *y) { Node *x = y->left; y->left = x->right; if (x->right != NULL) x->right->parent = y; x->parent = y->parent; if (y->parent == NULL) *root = x; else if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; x->right = y; y->parent = x; } // Функция для восстановления свойств красно-черного дерева после вставки void fixInsert(Node **root, Node *z) { while (z != *root && z->parent->color == RED) { if (z->parent == z->parent->parent->left) { Node *y = z->parent->parent->right; if (y != NULL && y->color == RED) { // Дядя красный - случай 1 z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->right) { // Дядя черный и z - правый ребенок - случай 2 z = z->parent; leftRotate(root, z); } // Дядя черный и z - левый ребенок - случай 3 z->parent->color = BLACK; z->parent->parent->color = RED; rightRotate(root, z->parent->parent); } } else { // Симметричный случай Node *y = z->parent->parent->left; if (y != NULL && y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->left) { z = z->parent; rightRotate(root, z); } z->parent->color = BLACK; z->parent->parent->color = RED; leftRotate(root, z->parent->parent); } } } (*root)->color = BLACK; // Корень всегда черный } // Вставка узла в красно-черное дерево void insert(Node **root, int data) { Node *z = createNode(data); Node *y = NULL; Node *x = *root; // Обычная вставка в бинарное дерево поиска while (x != NULL) { y = x; if (z->data < x->data) x = x->left; else x = x->right; } z->parent = y; if (y == NULL) *root = z; else if (z->data < y->data) y->left = z; else y->right = z; // Восстановление свойств красно-черного дерева fixInsert(root, z); } // Вспомогательная функция для вывода дерева (обход в порядке in-order) void inOrder(Node *root) { if (root == NULL) return; inOrder(root->left); printf("%d(%s) ", root->data, root->color == RED ? "RED" : "BLACK"); inOrder(root->right); } // Основная функция для демонстрации int main() { Node *root = NULL; // Вставка элементов insert(&root, 10); insert(&root, 20); insert(&root, 30); insert(&root, 15); insert(&root, 25); insert(&root, 5); insert(&root, 35); // Вывод дерева printf("In-order traversal of the constructed tree:\n"); inOrder(root); printf("\n"); return 0; }
Объяснение кода:
Структура узла: Каждый узел содержит данные, цвет (красный или черный), указатели на левого и правого потомков, а также на родителя.
Вращения:
leftRotateиrightRotate- операции, которые помогают сохранять баланс дерева.
Вставка:
Сначала выполняется стандартная вставка как в бинарное дерево поиска.
Затем вызывается
fixInsertдля восстановления свойств красно-черного дерева.
Восстановление свойств (
fixInsert):Исправляет возможные нарушения свойств красно-черного дерева после вставки.
Рассматривает три основных случая в зависимости от цвета дяди текущего узла.
Свойства красно-черного дерева:
Каждый узел либо красный, либо черный.
Корень всегда черный.
Все листья (NIL) черные.
У красного узла оба потомка черные.
Все пути от узла до его листьев содержат одинаковое количество черных узлов.
Этот код демонстрирует базовые операции красно-черного дерева. Для полной реализации нужно также добавить функции удаления узла и обработки других случаев балансировки.