fork download
copy 
  1. #define _CRT_SECURE_NO_DEPRECATE
  2.  
  3. #include <cstring>
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <conio.h>
  7.  
  8.  
  9. using namespace std;
  10. const int n = 4000;
  11. const int B = 256;
  12. struct record2 {
  13.     char a[30];
  14.     union {
  15.         unsigned short int b;
  16.         unsigned char Digit[2];
  17.     };
  18.  
  19.     char c[10];
  20.     char d[22];
  21. };
  22.  
  23. struct Vertex {
  24.     record2 *Data;
  25.     int Bal;
  26.     Vertex *left;
  27.     Vertex *right;
  28. };
  29. bool Rost;
  30. bool Decrease;
  31.  
  32.  
  33.  
  34. struct list {
  35.     list *next;
  36.     record2 *Data;
  37. };
  38.  
  39. typedef struct queue {
  40.     list *head;
  41.     list *tail;
  42. };
  43.  
  44. void PrintList(list *p) {
  45.     int i = 1;
  46.     char c = 'y';
  47.  
  48.     while (c == 'y') {
  49.         for (int j = 0; j < 20; j++) {
  50.             printf("%d %s %d %s %s \n", i, p->Data->a, p->Data->b, p->Data->c, p->Data->d);
  51.             p = p->next;
  52.             i++;
  53.         }
  54.  
  55.         c = '0';
  56.         while ((c != 'y') && (c != 'n')) {
  57.             c = '0';
  58.             printf("\n\nPrint next 20 records? y/n\n");
  59.             scanf("%s", &c);
  60.             if ((c != 'y') && (c != 'n')) printf("Invalid input\n");
  61.         }
  62.  
  63.     }
  64.  
  65.  
  66.     if (c == 'n') {
  67.         do {
  68.             while ((_kbhit() != 1) && (p != NULL)) {
  69.                 printf("%d %s %d %s %s \n", i, p->Data->a, p->Data->b, p->Data->c, p->Data->d);
  70.                 p = p->next;
  71.                 i++;
  72.             }
  73.             system("PAUSE");
  74.         } while (p != NULL);
  75.     }
  76.  
  77.  
  78. }
  79.  
  80.  
  81. void DigitalSort2(list *&head) {
  82.  
  83.     queue Q[257];
  84.  
  85.     for (int i = 0; i < 257; i++) {
  86.         Q[i].tail = (list *) &(Q[i].head);
  87.     }
  88.  
  89.     list *p;
  90.  
  91.  
  92.     for (int j = 30; j >= 0; j--) {
  93.         for (int i = 0; i < 256; i++) {
  94.             Q[i].tail = Q[i].head = NULL;
  95.         }
  96.         while (head) {
  97.             int d;
  98.             d = head->Data->a[j] + 129;
  99.             p = Q[d].tail;
  100.             if (Q[d].head == NULL) {
  101.                 Q[d].head = head;
  102.             } else {
  103.                 p->next = head;
  104.             }
  105.             p = Q[d].tail = head;
  106.             head = head->next;
  107.             p->next = NULL;
  108.         }
  109.         head = NULL;
  110.         int i;
  111.         for (i = 0; i < 256; i++) {
  112.             if (Q[i].head != NULL) {
  113.                 break;
  114.             }
  115.         }
  116.         head = Q[i].head;
  117.         p = Q[i].tail;
  118.         for (int k = i + 1; k < 256; k++) {
  119.             if (Q[k].head != NULL) {
  120.                 p->next = Q[k].head;
  121.                 p = Q[k].tail;
  122.             }
  123.         }
  124.     }
  125. }
  126.  
  127. void deleteList(list *head) {
  128.     do {
  129.         list *q;
  130.         q = head;
  131.         head = q->next;
  132.         delete (q);
  133.     } while (head != NULL);
  134.  
  135. }
  136.  
  137.  
  138. void DigitalSort(queue *S, int L) {
  139.     queue Q[B];
  140.     list *p;
  141.  
  142.     for (int j = 0; j < L; j++) {
  143.         for (int i = 0; i < B; i++) Q[i].tail = (list *) &Q[i].head;
  144.         p = S->head;
  145.         while (p) {
  146.             int d = p->Data->Digit[j];
  147.             Q[d].tail->next = p;
  148.             Q[d].tail = p;
  149.             p = p->next;
  150.         }
  151.         p = (list *) &S->head;
  152.  
  153.         for (int i = 0; i < B; i++) {
  154.             if (Q[i].tail != (list *) &Q[i].head) {
  155.                 p->next = Q[i].head;
  156.                 p = Q[i].tail;
  157.             }
  158.         }
  159.  
  160.         p->next = NULL;
  161.     }
  162. }
  163.  
  164. void RL(Vertex *&p, Vertex *&r, Vertex *&q) {
  165.  
  166.     q = p->right;//RL
  167.     r = q->left;
  168.     if (r->Bal < 0) p->Bal = 1;
  169.     else p->Bal = 0;
  170.     if (r->Bal > 0) q->Bal = -1;
  171.     else {
  172.         q->Bal = 0;
  173.         r->Bal = 0;
  174.         q->left = r->right;
  175.         p->right = r->left;
  176.         r->right = q;
  177.         r->left = p;
  178.         p = r;
  179.         Rost = false;
  180.     }
  181. }
  182.  
  183.  
  184. void RR(Vertex *&p, Vertex *&r, Vertex *&q) {
  185.     q = p->right;//RR
  186.     p->Bal = 0;
  187.     q->Bal = 0;
  188.     p->right = q->left;
  189.     q->left = p;
  190.     p = q;
  191.     Rost = false;
  192. }
  193.  
  194. void LR(Vertex *&p, Vertex *&r, Vertex *&q) {
  195.     q = p->left;//LR
  196.     r = q->right;
  197.     if (r->Bal < 0) p->Bal = 1;
  198.     else p->Bal = 0;
  199.     if (r->Bal > 0) q->Bal = -1;
  200.     else {
  201.         q->Bal = 0;
  202.         r->Bal = 0;
  203.         q->right = r->left;
  204.         p->left = r->right;
  205.         r->left = q;
  206.         r->right = p;
  207.         p = r;
  208.         Rost = false;
  209.     }
  210. }
  211.  
  212. void LL(Vertex *&p, Vertex *&r, Vertex *&q) {
  213.     q = p->left;//LL
  214.     p->Bal = 0;
  215.     q->Bal = 0;
  216.     p->left = q->right;
  217.     q->right = p;
  218.     p = q;
  219.     Rost = false;
  220. }
  221.  
  222. Vertex *AVL(list *k, Vertex *&p) {
  223.  
  224.         Vertex *q = NULL, *r = NULL;
  225.  
  226.         if (p == NULL) {
  227.             p = new Vertex;
  228.             p->Data = (k->Data);
  229.             p->left = p->right = NULL;
  230.             p->Bal = 0;
  231.             Rost = true;
  232.         } else if (p->Data->d > k->Data->d) {
  233.             AVL(k, p->left);
  234.             if (Rost) {
  235.                 if (p->Bal > 0) {
  236.                     p->Bal = 0;
  237.                     Rost = false;
  238.                 } else if (p->Bal == 0) {
  239.                     p->Bal = -1;
  240.                     Rost = true;
  241.                 } else if (p->left->Bal < 0)
  242.                     LL(p, r, q);
  243.                 else LR(p, r, q);
  244.             }
  245.         } else if (p->Data->d < k->Data->d) {
  246.             AVL(k, p->right);
  247.             if (Rost) {
  248.                 if (p->Bal < 0) {
  249.                     p->Bal = 0;
  250.                     Rost = false;
  251.                 } else if (p->Bal == 0) {
  252.                     p->Bal = 1;
  253.                     Rost = true;
  254.                 } else if (p->right->Bal > 0) RR(p, r, q);
  255.                 else
  256.                     RL(p, r, q);
  257.             }
  258.         } else return p;
  259.     }
  260.  
  261.  
  262.  
  263. void obhod(Vertex *p) {
  264.     if (p != NULL) {
  265.         obhod(p->left);
  266.         cout<<" "<<p->Data->d;
  267.         obhod(p->right);
  268.     }
  269. }
  270.  
  271.  
  272. int main() {
  273.  
  274.     FILE *input;
  275.     queue q;
  276.     Vertex *root = NULL;
  277.     input = fopen("testBase3.dat", "rb");
  278.     record2 *mas2;
  279.     mas2 = new record2[n];
  280.     int i = 0;
  281.  
  282.     list *head, *p, *r;
  283.     q.head = p = new list;
  284.  
  285.     p->Data = new record2;
  286.     fread((record2 *) p->Data, sizeof(record2), 1, input);
  287.  
  288.     for (i = 1; i < n; i++) {
  289.         p = p->next = new list;
  290.         p->Data = new record2;
  291.         fread((record2 *) p->Data, sizeof(record2), 1, input);
  292.     }
  293.     p->next = NULL;
  294.     q.tail = p;
  295.     int *key = new int[3];
  296.     /*for (i = 0; i < 3; i++) {
  297.         char my_key = 0;
  298.         scanf("%c", &my_key);
  299.         key[i]=(int)my_key;
  300.     }*/
  301.  
  302.  
  303.     DigitalSort(&q, 2);
  304.     DigitalSort2(q.head);
  305.    // PrintList(q.head);
  306.       r=q.head;
  307. i=0;
  308.        while(i<1000)
  309.       {
  310.           i++;
  311.           AVL(r,root);
  312.           r=r->next;
  313.  
  314.       }
  315.      obhod(root);
  316.  
  317.     delete (mas2);
  318.     deleteList(q.head);
  319.     return 0;
  320. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:3:10: fatal error: cstring: No such file or directory
 #include <cstring>
          ^~~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/FsWfP1
language:
C (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!