Сортировка MergeSort

#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <IO.H>
#include <FCNTL.H>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
using namespace std;
#pragma warning(disable : 4996)
 
/*----------------------------------------------------------------------------*/
/* constantes                                                                 */
/*----------------------------------------------------------------------------*/
#define MAX 3999
#define Base_name "C:\\testBase3.dat"
#define default "C:\\testBase3.dat"
/*----------------------------------------------------------------------------*/
/* variables                                                                  */
/*----------------------------------------------------------------------------*/
int   index[MAX + 1];
int   VR = 0, HR = 0;
/*----------------------------------------------------------------------------*/
struct obmanVkladckik {
    char Vkladchik[30];
    unsigned short int Summavklada;
    char Datavklada[10];
    char Advokat[22];
};
/*----------------------------------------------------------------------------*/
struct qel {
    struct qel *next;
    struct obmanVkladckik *data;
};
/*----------------------------------------------------------------------------*/
struct queueS {
    qel *head;
    qel *tail;
};
/*----------------------------------------------------------------------------*/
struct queue {
    int index;
    struct queue *next;
} *headq = NULL, *tailq, *spis;
/*----------------------------------------------------------------------------*/
struct derevo {
    int x;
    int balance;
    struct derevo *left;
    struct derevo *right;
} *Dbd, *q;
 
struct obmanVkladckik *el[MAX];
/*----------------------------------------------------------------------------*/
FILE *fin;
float P[256], P1[256];
int p_to_s[256];
int s_to_p[256];
int maxpower; long amount; int i, j, k;
/*----------------------------------------------------------------------------*/
float q1;
unsigned char C[256][30], L[256];
unsigned char S[30], l;
/*----------------------------------------------------------------------------*/
/* prototypus&functions                                                       */
/*----------------------------------------------------------------------------*/
/*  1 */ void   menu();
/*  2 */ void   info();
/*---------------------------------------------------------------------*/
/*  3 */ struct qel * LoadMem();
/*  4 */ void   ViewBase(struct obmanVkladckik **el, int iN);
/*---------------------------------------------------------------------*/
/*  5 */ void   InvertDate(char aData[], int n);
/*  6 */ char   compare(char aData[], char bData[], int n);
/*  7 */ int    Devide(qel* &s, qel* &a, qel* &b);
/*  8 */ void   Merging(qel* &a, qel* &b, queueS &c, int q, int r);
/*  9 */ qel*   MergeSort(qel* s);
/*---------------------------------------------------------------------*/
/* 10 */ int    BinSearch(struct obmanVkladckik **x, int N, int *pointers, char *value);
/* 11 */ void   FreeQueue(queue *p);
/* 12 */ void   MakeQueue(char *n, struct queue *pq, int *index, int pos);
/* 13 */ void   PrintQueue(struct queue *p);
/*---------------------------------------------------------------------*/
/* 14 */ void   FreeTree(derevo *p);
/* 15 */ void   CreateDBD(int D, struct obmanVkladckik **base, struct derevo **p, int *index);
/* 16 */ void   PrintTree(struct obmanVkladckik **x, struct derevo *p, int *index);
/* 17 */ struct derevo *SearchInTree(char key[], struct obmanVkladckik **x, struct derevo *p);
/* 18 */ void   PrintSearch(char key[], struct obmanVkladckik **x, struct derevo *p);
/*---------------------------------------------------------------------*/
void menu() {
    int i;
    char ch;
    struct qel *head, *tail, *p;
    head = LoadMem();
    printf("\n  Press any key to back to menu...");
    _getch();
    for (i = 0; i <= MAX; i++) index[i] = i;
    i = 0;
    for (p = head; p != NULL; p = p->next) el[index[i++]] = p->data;
    while (1) {
        system("cls");
        info();
        ch = _getch();
 
        switch (ch) {
 
        case '1':
            system("cls");
            i = 0;
            qel *q;
            for (p = MergeSort(head); p != NULL; p = p->next) {
                el[index[i++]] = p->data;
            }
            printf("\n  Base was sorted");
            printf("\n  Press any key to back to menu...");
            _getch();
            break;
 
        case '2':
            system("cls");
            printf("\n  BASE  \n");
            ViewBase(el, i);
            printf("\n  THE END OF BASE  \n");
            printf("\n  Press any key to back to menu...");
            _getch();
            break;
 
        case '3':
            system("cls");
            printf("\n  Enter key of search (format 'yy'): ");
            char x[2];
            int y;
            scanf("%s", x);
            y = BinSearch(el, MAX, index, x);
            system("cls");
            if (y == -1) { printf("  Element not found"); _getch(); break; }
            FreeQueue(spis);
            MakeQueue(x, spis, index, y);
            spis = headq;
            printf("\n  QUEUE  \n");
            PrintQueue(spis);
            printf("\n  THE END OF QUEUE  \n");
            printf("\n  Press any key to back to menu...");
            _getch();
            break;
 
        case '4':
            system("cls");
            spis = headq;
            VR = 0, HR = 0;
            FreeTree(Dbd); Dbd = NULL;
            if (spis == NULL) {
                printf("\n  Tree is not created");
                _getch();
                break;
            }
            while (spis != NULL) {
                CreateDBD(spis->index, el, &Dbd, index);
                spis = spis->next;
            }
            derevo *temp;
            temp = Dbd;
            printf("\n  TREE  \n");
            PrintTree(el, temp, index);
            printf("\n  THE END OF TREE  \n");
            printf("\n  Press any key to back to menu...");
            _getch();
            break;
 
        case '5':
            system("cls");
            char ch[8];
            struct derevo *tmp, *searchSubTree;
            printf("\n  Enter key of search in tree (format 'dd-mm-yy'): ");
            scanf("%s", &ch);
            tmp = Dbd;
            searchSubTree = SearchInTree(ch, el, tmp);
            if (searchSubTree != NULL) PrintSearch(ch, el, tmp);
            else printf("\n  Element not found");
            printf("\n  Press any key to back to menu...");
            _getch();
            break;
        case 27:
            exit(1);
        }
    }
}
/*----------------------------------------------------------------------------*/
void info() {
    printf("\n");
    printf("  [ 1 ] Sort base\n");
    printf("  [ 2 ] Print base\n");
    printf("  [ 3 ] Create queue\n");
    printf("  [ 4 ] Create tree\n");
    printf("  [ 5 ] Search in tree\n");
    printf("  [ESC] Exit\n");
}
/*----------------------------------------------------------------------------*/
struct qel * LoadMem() {
    int i = 0, j, f;
    struct qel *head, *p, *tail;
 
    printf("\n  Load base...\n");
 
    f = open(Base_name, O_RDONLY | O_BINARY);
    head = NULL;
    tail = head;
    while (!eof(f)) {
        p = (struct qel *)malloc(sizeof(struct qel));
        if (p == NULL) {
            printf("\n  ERROR: Out of Memory");
            _getch();
            exit(0);
        }
        p->data = (struct obmanVkladckik *)malloc(sizeof(struct obmanVkladckik));
        if (p->data == NULL) {
            printf("\n  ERROR: Out of Memory");
            _getch();
            exit(0);
        }
        read(f, p->data, sizeof(struct obmanVkladckik));
 
        p->next = NULL;
        if (head != NULL) tail->next = p;
        else head = p;
        tail = p;
        i++;
    }
    close(f);
    printf("\n  Base was loaded\n");
    return(head);
}
/*----------------------------------------------------------------------------*/
 
 
void ViewBase(struct obmanVkladckik **el, int iN) {
 
    for (int i = 0, counter = 0; i < MAX; ++i, ++counter) {
        printf("\n%4d. ", index[i] + 1);
        printf("%.30s", el[index[i]]->Vkladchik);
        printf("\n     %d", el[index[i]]->Summavklada);
        printf("\n   %.10s", el[index[i]]->Datavklada);
        printf("\n  %.22s", el[index[i]]->Advokat);
        printf("\n");
 
        if (counter == 19) {
            cout << "Вывести ещё? (y/n)" << endl;
            char flag;
            cin >> flag;
            counter = -1;
            if (flag != 'y')
                return;
        }
    }
}
/*----------------------------------------------------------------------------*/
void InvertDate(char aData[], int n) {
    char a[100];
    int i = 0, j = n - 2;
    while (i<n) {
        a[i] = aData[j];
        break;
        a[++i] = aData[j + 1];
        a[++i] = '-';
        i++;
        j = j - 3;
    }
    for (i = 0; i < n; i++)
    {
        aData[i] = a[i];
    }
}
/*----------------------------------------------------------------------------*/
char compare(char aData[], char bData[], int n) {
    char a[100];
    char b[100];
    int i;
    for (i = 0; i<n; i++) {
        a[i] = aData[i];
        b[i] = bData[i];
    }
    InvertDate(a, n);
    InvertDate(b, n);
    for (i = 0; i<n; i++) {
        if (a[i]>b[i])return 2;
        else if (a[i]<b[i])return 1;
    }
    return 1;
}
/*----------------------------------------------------------------------------*/
int Devide(qel* &s, qel* &a, qel* &b) {
    qel *k, *p;
    int n;
 
    a = s;
    b = s->next;
 
    n = 1;
    k = a;
    p = b;
    while (p) {
        n++;
        k->next = p->next;
        k = p;
        p = p->next;
    }
    return n;
}
/*----------------------------------------------------------------------------*/
void Merging(qel* &a, qel* &b, queueS &c, int q, int r) {
    qel *p;
 
    while ((q != 0) && (r != 0)) {
        if (compare(a->data->Datavklada, b->data->Datavklada, 10) == 1) {
            p = a;
            a = a->next;
            p->next = NULL;
            if (c.head) c.tail->next = p;
            else c.head = p;
            c.tail = p;
            q--;
        }
        else {
            p = b;
            b = b->next;
            p->next = NULL;
            if (c.head) c.tail->next = p;
            else c.head = p;
            c.tail = p;
            r--;
        }
    }
    while (q>0) {
        p = a;
        a = a->next;
        p->next = NULL;
        if (c.head) c.tail->next = p;
        else c.head = p;
        c.tail = p;
        q--;
    }
    while (r>0) {
        p = b;
        b = b->next;
        p->next = NULL;
        if (c.head) c.tail->next = p;
        else c.head = p;
        c.tail = p;
        r--;
    }
}
/*----------------------------------------------------------------------------*/
qel* MergeSort(qel* s) {
    int n, p, q, r, m, i;
    struct queueS Cs[2];
    struct qel *a, *b;
    n = Devide(s, a, b);
    p = 1;
    while (p<n) {
        Cs[0].head = NULL;
        Cs[1].head = NULL;
        Cs[0].tail = Cs[0].head;
        Cs[1].tail = Cs[1].head;
        i = 0;
        m = n;
        while (m>0) {
            if (m >= p) q = p;
            else q = m;
            m -= q;
            if (m >= p) r = p;
            else r = m;
            m -= r;
            Merging(a, b, Cs[i], q, r);
            i = 1 - i;
        }
        a = Cs[0].head;
        b = Cs[1].head;
        p *= 2;
    }
    Cs[0].tail->next = NULL;
    return Cs[0].head;
}
/*----------------------------------------------------------------------------*/
int BinSearch(struct obmanVkladckik **x, int N, int *pointers, char *key) {
    int m, L, R;
    int i; char y[2];
    L = 0;
    R = N;
    while (L<R) {
        m = (L + R) / 2;
        for (i = 0; i<2; i++) y[i] = x[pointers[m]]->Datavklada[i + 6];
        if (strncmp(y, key, 2)<0) L = m + 1;
        else R = m;
    }
    for (i = 0; i<2; i++) y[i] = x[pointers[R]]->Datavklada[i + 6];
    if (strncmp(y, key, 2) == 0)return R;
    else return -1;
}
/*----------------------------------------------------------------------------*/
void FreeQueue(queue *p) {
    queue *q;
    while (p != NULL) {
        q = p;
        p = p->next;
        free(q);
    }
    p = NULL;
}
/*----------------------------------------------------------------------------*/
void MakeQueue(char *n, struct queue *pq, int *index, int pos) {
    char y[2];
    headq = NULL;
    while (1) {
        for (int i = 0; i<2; i++) y[i] = el[index[pos]]->Datavklada[i + 6];
        if (strncmp(y, n, 2) != 0) break;
        pq = (queue *)malloc(sizeof(queue));
        pq->next = NULL;
        pq->index = index[pos];
        if (headq != NULL) tailq->next = pq;
        else
            headq = pq;
        tailq = pq;
        pos++;
        if (pos == 4000)break;
    }
 
}
/*----------------------------------------------------------------------------*/
void PrintQueue(struct queue *p) {
    while (p != NULL) {
        printf("\n  %.30s", el[p->index]->Vkladchik);
        printf("  %d", el[p->index]->Summavklada);
        printf("  %.10d", el[p->index]->Datavklada);
        printf("  %.22s \n", el[p->index]->Advokat);
        p = p->next;
    }
}
/*----------------------------------------------------------------------------*/
/* 14 - 18                                                                    */
/*----------------------------------------------------------------------------*/
void FreeTree(derevo *p) {
    if (p != NULL) {
        FreeTree(p->left);
        FreeTree(p->right);
        free(p);
    }
    p = NULL;
}
/*----------------------------------------------------------------------------*/
void CreateDBD(int x, struct obmanVkladckik **base, struct derevo **p, int *index) {
    if (!(*p)) {
        (*p) = new(struct derevo);
        (*p)->x = x; (*p)->left = NULL; (*p)->right = NULL;
        (*p)->balance = 0; VR = 1;
    }
    else {
        if (strcmp(base[x]->Datavklada, base[(*p)->x]->Datavklada) <= 0) {
            CreateDBD(x, base, &(*p)->left, index);
            if (VR == 1) {
                if ((*p)->balance == 0) {
                    q = (*p)->left;
                    (*p)->left = q->right;
                    q->right = (*p);
                    (*p) = q;
                    (*p)->balance = 1;
                    VR = 0; HR = 1;
                }
                else {
                    (*p)->balance = 0; HR = 0; VR = 1;
                }
            }
            else {
                HR = 0;
            }
        }
        else {
            if (strcmp(base[x]->Datavklada, base[(*p)->x]->Datavklada)>0) {
                CreateDBD(x, base, &(*p)->right, index);
                if (VR == 1) {
                    (*p)->balance = 1;
                    VR = 0;
                    HR = 1;
                }
                else {
                    if (HR == 1) {
                        if ((*p)->balance>0) {
                            q = (*p)->right;
                            (*p)->right = q->left;
                            (*p)->balance = 0;
                            q->balance = 0;
                            q->left = (*p);
                            (*p) = q;
                            VR = 1;
                            HR = 0;
                        }
                        else {
                            HR = 0;
                        }
                    }
                }
            }
        }
    }
}
/*----------------------------------------------------------------------------*/
void PrintTree(struct obmanVkladckik **x, struct derevo *p, int *index) {
    if (p != NULL) {
        PrintTree(x, p->left, index);
        printf("\n  %.30s", x[p->x]->Vkladchik);
        printf("  %d", x[p->x]->Summavklada);
        printf("  %.10d", x[p->x]->Datavklada);
        printf("  %.22s \n", x[p->x]->Advokat);
        PrintTree(x, p->right, index);
    }
}
/*----------------------------------------------------------------------------*/
struct derevo *SearchInTree(char key[], struct obmanVkladckik **x, struct derevo *p) {
    while (p != NULL) {
        if (strncmp(key, x[p->x]->Datavklada, 10)<0)p = p->left;
        else if (strncmp(key, x[p->x]->Datavklada, 10)>0)p = p->right;
        else return p;
    }
    return NULL;
}
/*----------------------------------------------------------------------------*/
void PrintSearch(char key[], struct obmanVkladckik **x, struct derevo *p) {
    if (p != NULL) {
        PrintSearch(key, x, p->left);
        if (strncmp(key, x[p->x]->Datavklada, 10) == 0) {
            printf("\n  %.30s", x[p->x]->Vkladchik);
            printf("  %d", x[p->x]->Summavklada);
            printf("  %.10d", x[p->x]->Datavklada);
            printf("  %.22s \n", x[p->x]->Advokat);
        }
        PrintSearch(key, x, p->right);
    }
}
/*----------------------------------------------------------------------------*/
int main() {
    menu();
}
/*----------------------------------------------------------------------------*/