Igorochenka

3A

Apr 13th, 2021 (edited)
452
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include <malloc.h>
  4. #include <string.h>
  5.  
  6.  
  7.  
  8. typedef int KeyType1;
  9. typedef int KeyType2;
  10. typedef int IndexType1;
  11. typedef int IndexType2;
  12. typedef short int BusyType1;
  13. typedef short int BusyType2;
  14. typedef short int RelType1;
  15.  
  16.  
  17. typedef struct InfoType {
  18.     int a;
  19.     int b;
  20.     char* string;
  21. } InfoType;
  22.  
  23. typedef struct Item {
  24.     InfoType* info;
  25.     /* указатель на информацию                 */
  26.     KeyType1 key1;
  27.     /* ключ элемента из 1-го пространства ключей;         */
  28.     KeyType2 key2;
  29.     IndexType1  ind1;
  30.     /* связь с элементом 1-го пространства ключей по индексу;   */
  31.     IndexType2 ind2;
  32.  
  33. } Item;
  34.  
  35. typedef struct KeySpace1 {
  36.     BusyType1 busy;         /* признак занятости элемента           */
  37.     KeyType1 key;           /* ключ элемента                */
  38.     RelType1 release;       /* номер версии элемента         */
  39.     Item* info;         /* указатель на информацию         */
  40. } KeySpace1;
  41.  
  42. typedef struct KeySpace2 {
  43.     BusyType2 busy;
  44.     KeyType2 key;
  45.     Item* info;
  46. } KeySpace2;
  47.  
  48. typedef struct Table {
  49.     KeySpace1* ks1;
  50.     /* указатель на первое пространство ключей           */
  51.     KeySpace2* ks2;
  52.  
  53.     IndexType1  msize1;
  54.     /* размер области 1-го пространства ключей             */
  55.     IndexType2 msize2;
  56.  
  57.     IndexType1  size1;
  58.     /* количество элементов в области 1-го пространства ключей   */
  59.     IndexType2 size2;
  60. } Table;
  61.  
  62.  
  63. Table* table_new(int msize1, int msize2) {
  64.     Table* t = (Table*)malloc(sizeof(Table));
  65.     t->msize1 = msize1;
  66.     t->size1 = 0;
  67.     t->ks1 = (KeySpace1*)malloc(msize1 * sizeof(KeySpace1));
  68.     for (int i = 0; i < msize1; i++) {
  69.         t->ks1[i].info = NULL;
  70.         t->ks1[i].busy = 0;
  71.         t->ks1[i].key = NULL;
  72.         t->ks1[i].release = NULL;
  73.     }
  74.  
  75.     t->msize2 = msize2;
  76.     t->size2 = 0;
  77.     t->ks2 = (KeySpace2*)malloc(msize2 * sizeof(KeySpace2));
  78.     for (int i = 0; i < msize2; i++) {
  79.         t->ks2[i].info = NULL;
  80.         t->ks2[i].busy = 0;
  81.         t->ks2[i].key = NULL;
  82.     }
  83.  
  84.     return t;
  85. }
  86.  
  87. int dialog(const char* msgs[], int n) {
  88.     char* error = (char*)"";
  89.     int choice;
  90.     do {
  91.         puts(error);
  92.         error = (char*)"You're wrong. Try again!";
  93.         for (int i = 0; i < n; ++i) {
  94.             puts(msgs[i]);
  95.         }
  96.         puts("Make your choice: ");
  97.         choice = get_int();
  98.         while (getchar() != '\n') {}
  99.     } while (choice < 0 || choice >= n);
  100.     return choice;
  101. }
  102.  
  103. int get_int() {
  104.     int n = 0;
  105.     int res;
  106.     do {
  107.         n = scanf("%d", &res);
  108.         if (n < 0) {
  109.             exit(-1);
  110.             return -1;
  111.         }
  112.         else if (n == 0) {
  113.             while (getchar() != '\n');
  114.             printf("Please enter integer:");
  115.         }
  116.     } while (n == 0);
  117.     return res;
  118. }
  119.  
  120. char* get_str() {
  121.     char buf[81] = { 0 };
  122.     char* res = NULL;
  123.     int len = 0;
  124.     int n = 0;
  125.     do {
  126.         n = scanf("%s", buf);
  127.         if (n < 0) {
  128.             if (!res) {
  129.                 return NULL;
  130.             }
  131.         }
  132.         else if (n > 0) {
  133.             int chunk_len = strlen(buf);
  134.             int str_len = len + chunk_len;
  135.             res = (char*)realloc(res, str_len + 1);
  136.             memcpy(res + len, buf, chunk_len);
  137.             len = str_len;
  138.         }
  139.         else {
  140.             scanf("%*c");
  141.         }
  142.     } while (n == 0);
  143.  
  144.     if (len > 0) {
  145.         res[len] = '\0';
  146.     }
  147.     else {
  148.         res = (char*)calloc(1, sizeof(char));
  149.     }
  150.  
  151.     return res;
  152. }
  153.  
  154. void include_element(Table* t) {
  155.     InfoType info;
  156.     printf("Input INFO:\n\ta: ");
  157.     info.a = get_int();
  158.     printf("\tb: ");
  159.     info.b = get_int();
  160.     printf("\tstr: ");
  161.     info.string = get_str();
  162.  
  163.     printf("Input Key 1: ");
  164.     KeyType1 key1 = get_int();
  165.  
  166.     printf("Input Key 2: ");
  167.     KeyType1 key2 = get_int();
  168.    
  169.     int res = table_include(t, info, key1, key2);
  170.    
  171.     if (res == 1)
  172.         printf("Success!\n");
  173.     else if (res == -1)
  174.         printf("Error: Table is full!\n");
  175.     else if (res == 0)
  176.         printf("Error: key is already exists\n");
  177. }
  178.  
  179. Item* keyspace1_find_key(KeySpace1* ks, KeyType1 key, int size) {
  180.     int i = 0;
  181.     int ind = size;
  182.  
  183.     for (i = 0; i < ind; i++) {
  184.         if (ks[i].key == key) {
  185.             if (ks[i].busy == 1) {
  186.                 return ks[i].info;
  187.             }
  188.         }
  189.     }
  190.     return 0;
  191. }
  192.  
  193. int keyspace2_hash(KeyType2 key, int msize) {
  194.     int hash = key % msize;
  195.     return hash;
  196. }
  197.  
  198. Item* keyspace2_find_key(KeySpace2* ks, KeyType2 key, int msize) {
  199.     int ind = keyspace2_hash(key, msize);
  200.     if (ks[ind].busy == 0)
  201.         return 0;
  202.     if (ks[ind].busy == 1 && ks[ind].key == key)
  203.         return ks[ind].info;
  204.  
  205.     for (int i = ind + 1; i != ind; i = (i + 1) % msize) {
  206.         if (ks[i].busy == 0)
  207.             return 0;
  208.         if (ks[i].busy == 1 && ks[i].key == key)
  209.             return ks[ind].info;
  210.     }
  211.  
  212.     return 0;
  213. }
  214.  
  215. void keyspace1_include(KeySpace1* ks, Item* info, KeyType1 key, int size) {
  216.     while (ks->info) {
  217.         *ks++;
  218.     }
  219.     ks->key = key;
  220.     ks->info = info;
  221.     ks->busy = 1;
  222.  
  223.  
  224.     return;
  225. }
  226.  
  227. void keyspace2_include(KeySpace2* ks, Item* info, KeyType2 key, int msize) {
  228.     int ind = keyspace2_hash(key, msize);
  229.     if (ks->busy != 1) {
  230.         ks->busy = 1;
  231.         ks->info = info;
  232.         ks->key = key;
  233.         info->ind2 = ind;
  234.         return;
  235.     }
  236.  
  237.     for (int i = ind + 1; i != ind; i = (i + 1) % msize) {
  238.         if (ks[i].busy != 1 && ks->key != key) {
  239.             ks[i].busy = 1;
  240.             ks[i].info = info;
  241.             ks[i].key = key;
  242.             info->ind2 = i;
  243.             return;
  244.         }
  245.     }
  246.  
  247.     return;
  248. }
  249.  
  250. Item* item_new(InfoType info, KeyType1 key1, KeyType2 key2) {
  251.     Item* item = (Item*)malloc(sizeof(Item));
  252.     item->info = (InfoType*)malloc(sizeof(InfoType));
  253.     (*item->info) = info;
  254.     item->key1 = key1;
  255.     item->key2 = key2;
  256.     return item;
  257. }
  258.  
  259. int table_include(Table* t, InfoType info, KeyType1 key1, KeyType2 key2) {
  260.     if (t->msize1 == t->size1 || t->msize2 == t->size2)
  261.         return -1;
  262.  
  263.     if (keyspace1_find_key(t->ks1, key1, t->size1) || (keyspace2_find_key(t->ks2, key2, t->msize2)))
  264.         return 0;
  265.  
  266.     Item* item = item_new(info, key1, key2);
  267.  
  268.     keyspace1_include(t->ks1, item, key1, t->size1);
  269.     keyspace2_include(t->ks2, item, key2, t->msize2);
  270.  
  271.     t->size1++;
  272.     t->size2++;
  273.  
  274.     return 1;
  275. }
  276.  
  277. void print_table(Table* t) {
  278.     printf("1: \n");
  279.     for (int i = 0; i < t->msize1; i++) {
  280.         if (t->ks1[i].info)
  281.             printf(" Busy: %d Key1: %d      Int A:%d Int B:%d String:'%s'\n", t->ks1[i].busy, t->ks1[i].key, t->ks1[i].info->info->a, t->ks1[i].info->info->b, t->ks1[i].info->info->string);
  282.         else
  283.             printf("-\n");
  284.     }
  285.     printf("2:\n");
  286.     for (int i = 0; i < t->msize2; i++) {
  287.         if (t->ks2[i].info)
  288.             printf(" Busy: %d Key2: %d      Int A:%d Int B:%d String:'%s'\n", t->ks2[i].busy, t->ks2[i].key, t->ks2[i].info->info->a, t->ks2[i].info->info->b, t->ks2[i].info->info->string);
  289.         else
  290.             printf("-\n");
  291.     }
  292. }
  293.  
  294. void find_element_with_key(Table* t) {
  295.     printf("From key space 1 or key space 2? (1/2): ");
  296.     int space = get_int();
  297.     while (space < 1 || space > 2) {
  298.         printf("Please choose between 1 and 2\n");
  299.         printf("From key space 1 or key space 2? (1/2): ");
  300.         space = get_int();
  301.     }
  302.  
  303.     Item* res = 0;
  304.     if (space == 1) {
  305.         printf("Input Key 1: ");
  306.         KeyType1 key1 = get_int();
  307.         res = keyspace1_find_key(t->ks1, key1, t->size1);
  308.     }
  309.     else {
  310.         printf("Input Key 2: ");
  311.         KeyType2 key2 = get_int();
  312.         res = keyspace2_find_key(t->ks2, key2, t->msize2);
  313.     }
  314.  
  315.     if (res != 0)
  316.         printf("Success: %d %d %d %d %s\n", res->key1, res->key2, res->info->a, res->info->b, res->info->string);
  317.     else
  318.         printf("Error: Not Exist!\n");
  319. }
  320.  
  321. Item* table_find_composite(Table* t, KeyType1 key1, KeyType2 key2) {
  322.     int i = 0;
  323.     for (i = 0; (i < t->size1) || (i < t->size2); i++) {
  324.         if ((t->ks1[i].key == key1) && (t->ks2[i].key == key2)) {
  325.             if ((t->ks1[i].busy == 1) && (t->ks2[i].busy == 1)) {
  326.                 return t->ks1[i].info;
  327.             }
  328.         }
  329.     }
  330.     return 0;
  331. }
  332.  
  333. void find_element_with_composite(Table* t) {
  334.     printf("Input Key 1: ");
  335.     KeyType1 key1 = get_int();
  336.     printf("Input Key 2: ");
  337.     KeyType2 key2 = get_int();
  338.  
  339.  
  340.     Item* res = table_find_composite(t, key1, key2);
  341.     if (res)
  342.         printf("Success: %d %d      %d %d %s\n", res->key1, res->key2, res->info->a, res->info->b, res->info->string);
  343.     else
  344.         printf("Error: Not Exist!\n");
  345. }
  346.  
  347.  
  348. void table_delete_item(Table* t, Item* item) {
  349.     printf("DELETING - Key1: %d Key2: %d\n", item->key1, item->key2);
  350.     t->ks1->busy = 0;
  351.     t->ks2->busy = 0;
  352. }
  353.  
  354. // 1 If deleted -1 if not found
  355. int table_delete_composite(Table* t, KeyType1 key1, KeyType2 key2) {
  356.     Item* item = table_find_composite(t, key1, key2);
  357.     if (item) {
  358.         table_delete_item(t, item);
  359.         return 1;
  360.     }
  361.     return -1;
  362. }
  363.  
  364. void delete_element_with_composite(Table* t) {
  365.     printf("Input Key 1: ");
  366.     KeyType1 key1 = get_int();
  367.     printf("Input Key 2: ");
  368.     KeyType2 key2 = get_int();
  369.  
  370.     int res = table_delete_composite(t, key1, key2);
  371.     if (res == 1)
  372.         printf("Success!");
  373.     else
  374.         printf("Error: Not Exist!\n");
  375. }
  376.  
  377.  
  378.  
  379. void delete_element_with_key(Table* t) {
  380.     printf("From key space 1 or key space 2? (1/2): ");
  381.     int space = get_int();
  382.     while (space < 1 || space > 2) {
  383.         printf("Please choose between 1 and 2\n");
  384.         printf("From key space 1 or key space 2? (1/2): ");
  385.         space = get_int();
  386.     }
  387.  
  388.     Item* res;
  389.     if (space == 1) {
  390.         printf("Input Key 1: ");
  391.         KeyType1 key1 = get_int();
  392.         res = keyspace1_find_key(t->ks1, key1, t->size1);
  393.     }
  394.     else {
  395.         printf("Input Key 2: ");
  396.         KeyType2 key2 = get_int();
  397.         res = keyspace2_find_key(t->ks2, key2, t->msize2);
  398.     }
  399.  
  400.     if (res) {
  401.         table_delete_item(t, res);
  402.         printf("Success!");
  403.     }
  404.     else {
  405.         printf("Error: Not Exist!\n");
  406.     }
  407. }
  408.  
  409. void reorganize_first_key(Table* t) {
  410.     KeySpace1 tmp1;
  411.     KeySpace2 tmp2;
  412.     int i = 0;
  413.     for (i = 0; i < t->msize1; i++) {
  414.         if (t->ks1[i].busy == 0 && t->ks1[i + 1].busy != 0) {
  415.             tmp1 = t->ks1[i];
  416.             t->ks1[i] = t->ks1[i + 1];
  417.             t->ks1[i + 1] = tmp1;
  418.             tmp2 = t->ks2[i];
  419.             t->ks2[i] = t->ks2[i + 1];
  420.             t->ks2[i + 1] = tmp2;
  421.             t->size1 -= 1;
  422.         }
  423.     }
  424. }
  425.  
  426. int main() {
  427.     const char* MSGS[] = { "0. Quit", "1. Including new element", "2. Finding element with composite key", "3. Deleting element with composite key", "4. Finding element with one key", "5. Deleting element with one key", "6. Print table", "7. Reorganize First Keys" };
  428.     const int MSGS_SIZE = sizeof(MSGS) / sizeof(MSGS[0]);
  429.     int c = 0;
  430.     printf("Enter msize1: ");
  431.     int msize1 = get_int();
  432.     printf("Enter msize2: ");
  433.     int msize2 = get_int();
  434.     Table* t = table_new(msize1,msize2);
  435.     do {
  436.         c = dialog(MSGS, MSGS_SIZE);
  437.         switch (c) {
  438.         case 0: {
  439.             free(t);
  440.             break;
  441.         } case 1: {
  442.             include_element(t);
  443.             break;
  444.         } case 2: {
  445.             find_element_with_composite(t);
  446.             break;
  447.         } case 3: {
  448.             delete_element_with_composite(t);
  449.             break;
  450.         } case 4: {
  451.             find_element_with_key(t);
  452.             break;
  453.         } case 5: {
  454.             delete_element_with_key(t);
  455.             break;
  456.         } case 6: {
  457.             print_table(t);
  458.             break;
  459.         } case 7: {
  460.             reorganize_first_key(t);
  461.             break;
  462.         }
  463.         }
  464.     } while (c != 0);
  465.     return 0;
  466. }
  467.    
  468.  
RAW Paste Data