Author: Pavel Kravtsov Language: c
Description: 4 Timestamp: 2013-05-28 22:34:51 +0000
View raw paste Reply
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. char *getstr();
  6. int getInt(int *N);
  7. char* antispace(char* str);
  8.  
  9. const char *msgs[]={"0. End","1. Add Item", "2. Find Item", "3. Find Minimum", "4. Delete Item", "5. Show Table"};
  10. const int Nmsgs = sizeof(msgs)/sizeof(msgs[0]);
  11.  
  12. typedef struct node
  13. {
  14.     int key;
  15.     char* info;
  16.     struct node *left;
  17.     struct node *right;
  18.     struct node *next;
  19. }node;
  20. int dialog(const char *msgs[], int N);
  21. int D_Add(node **root),
  22.     D_Find(node **root),
  23.     D_FindMin(node **root),
  24.     D_Delete(node **root),
  25.     D_Show(node **root);
  26. int (*fptr[])(node **root) = {NULL,D_Add,D_Find,D_FindMin,D_Delete,D_Show};
  27.  
  28. node *delete(node **root, node *x);
  29. node *search(node *root, int k);
  30. node *getpar(node *root, node *x);
  31. node *next(node *root, node *x);
  32. node *prev(node *root, node *x);
  33. int *insert(node **root, node *x);
  34. node *minimum(node *root, int k);
  35.  
  36. int main()
  37. {
  38. node *root = NULL;
  39. int rc;
  40.     while(rc = dialog(msgs, Nmsgs))
  41.     {
  42.         fptr[rc](&root);
  43.     }
  44.     return 0;
  45.  
  46. }
  47.  
  48. int dialog(const char *msgs[], int N)
  49. {
  50. int rc = 1, i;
  51.     do
  52.     {
  53.         if (rc < 0 || rc >= N)
  54.             puts("Sorry, your request is wrong. Please, try again");
  55.         else
  56.             puts("Please, put the number of selected action:");
  57.         for (i = 0; i < N; i++)
  58.             puts(msgs[i]);
  59.  
  60.         getInt(&rc);
  61.     }
  62.     while (rc < 0 || rc >= N) ;
  63.     return rc;
  64. }
  65.  
  66. int D_Add(node **root)
  67. {
  68. int k, n = 1;
  69. char *info;
  70. node* x;
  71. info = (char*)malloc(sizeof(char));
  72.  
  73.     do
  74.     {
  75.         if(n<0 || k<0)
  76.             puts("Wrong key. Please try again:");
  77.         else
  78.             puts("Enter key:");
  79.         n=getInt(&k);
  80.         if(search(*root,k))
  81.             puts("The element with this key is exist already. Please try again:");
  82.     }
  83.     while (n < 0 || k < 0 || (search(*root,k)));
  84.  
  85.     if(n == 0)
  86.         return 0;
  87.  
  88.     do
  89.     {
  90.         if (info == NULL)
  91.             puts("Info is empty. Please try again:");
  92.         else
  93.             puts("Enter info:");
  94.  
  95.         info = getstr();
  96.         if (info != NULL)
  97.         info = antispace(info);
  98.             else
  99.         return 0;
  100.     }
  101.     while (info == NULL);
  102.  
  103.     x = (node*)malloc(sizeof(node));
  104.     x->info = info;
  105.     x->key = k;
  106.     x->left = NULL;
  107.     x->right = NULL;
  108.     x->next = NULL;
  109.     insert(root, x);
  110.     puts("Table extended");
  111. }
  112.  
  113. int D_Find(node **root)
  114. {
  115. int k, n = 1;
  116. node *cur;
  117.     do
  118.     {
  119.         if(n < 0 || k < 0)
  120.             puts("Wrong key. Please try again:");
  121.         else
  122.             puts("Enter key:");
  123.         n = getInt(&k);
  124.     }
  125.     while (n < 0 || k < 0);
  126.  
  127.     if(n == 0)
  128.         return 0;
  129.  
  130.     if (cur = search(*root, k))
  131.         printf("Found node:  Key = %d, Info = %s\n", cur->key, cur->info);
  132.     else
  133.         puts("Node not found");
  134. }
  135.  
  136. int D_FindMin(node **root)
  137. {
  138. int k, n = 1;
  139. node *cur, *x;
  140.     cur=*root;
  141.  
  142.     do
  143.     {
  144.         if(n < 0 || k < 0)
  145.             puts("Wrong key. Please try again:");
  146.         else
  147.             puts("Enter key:");
  148.         n = getInt(&k);
  149.     }
  150.     while (n < 0 || k < 0);
  151.  
  152.     if(n == 0)
  153.         return 0;
  154.  
  155.     if (cur && (x = minimum(*root, k)))
  156.         printf("Found node:  Key = %d, Info = %s\n", x->key, x->info);
  157.     else
  158.         puts("Node not found");
  159.  
  160. }
  161.  
  162. int D_Delete(node **root)
  163. {
  164. int k, n = 1;
  165. node *x;
  166.     do
  167.     {
  168.         if(n < 0 || k < 0)
  169.             puts("Wrong key. Please, try again:");
  170.         else
  171.             puts("Enter key:");
  172.         n = getInt(&k);
  173.     }
  174.     while (n < 0 || k < 0);
  175.  
  176.     if(n == 0)
  177.         return 0;
  178.  
  179.     if(x = search(*root, k))
  180.     {
  181.         delete(root, x);
  182.         puts("Node deleted");
  183.     }
  184.     else
  185.         puts("Item not found");
  186. }
  187.  
  188. int D_Show(node **root)
  189. {
  190. node* cur;
  191. cur = *root;
  192.     if(cur)
  193.         for(; cur->left; cur = cur->left);
  194.     puts("///////////////////////");
  195.     if(cur == NULL)
  196.         puts("Table is empty");
  197.     for(; cur; cur = cur->next)
  198.             printf("Node: Key is %d, Info is %s\n", cur->key, cur->info);
  199.     puts("///////////////////////");
  200. }
  201.  
  202. node *getpar(node *root, node *x)
  203. {
  204.  
  205. node *cur, *p = NULL;
  206. cur = root;
  207.     while (cur && (x->key != cur->key))
  208.     {
  209.         p = cur;
  210.         if(x->key < cur->key)
  211.             cur = cur->left;
  212.         else
  213.             cur = cur->right;
  214.     }
  215.     if (!cur)
  216.         p = NULL;
  217.  
  218. return p;
  219. }
  220.  
  221. node *next(node *root,node *x)
  222. {
  223. node* min, *p;
  224.     if (x->right)
  225.     {
  226.         min = x->right;
  227.         while(min->left)
  228.             min = min->left;
  229.         return min;
  230.     }
  231.     p = getpar(root,x);
  232.     while(p && (x == p->right))
  233.     {
  234.         x = p;
  235.         p = getpar(root,p);
  236.     }
  237. return p;
  238. }
  239.  
  240. node *prev(node *root, node *x)
  241. {
  242. node *max, *p;
  243.     if (x->left)
  244.     {
  245.         max = x->left;
  246.         while(max->right)
  247.             max = max->right;
  248.         return max;
  249.     }
  250.     p = getpar(root, x);
  251.     while(p && (x == p->left))
  252.     {
  253.         x = p;
  254.         p = getpar(root, p);
  255.     }
  256. return p;
  257. }
  258.  
  259. node *minimum(node *root, int k)
  260. {
  261. node *cur, *p = NULL;
  262.     if (cur = search(root, k))
  263.         return next(root, cur);
  264.  
  265.     cur = root;
  266.     while (cur)
  267.     {
  268.         p = cur;
  269.         if(k < cur->key)
  270.             cur = cur->left;
  271.         else
  272.             cur = cur->right;
  273.     }
  274.     if(k < p->key)
  275.         return p;
  276.     else
  277.         while(p && (cur == p->right))
  278.     {
  279.         cur = p;
  280.         p = getpar(root, p);
  281.     }
  282. return p;
  283. }
  284.  
  285.  
  286. node *delete(node **root, node *x)
  287. {
  288. node *p = NULL, *p2 = NULL, *temp = NULL, *prv, *nxt;
  289.     p = x;
  290.     if(prv = prev(*root, p))
  291.     {
  292.         if(nxt = next(*root, p))
  293.         {
  294.             prv->next = nxt;
  295.         }
  296.         else
  297.         {
  298.             prv->next = NULL;
  299.         }
  300.     }
  301.         else if(nxt = next(*root, p))
  302.             p = NULL;
  303.  
  304.     if(x->left == NULL || x->right == NULL)
  305.         p = x;
  306.     else
  307.         p = prev(*root,x);
  308.     if (p->left)
  309.         temp = p->left;
  310.     else
  311.         temp = p->right;
  312.     if ((p2 = getpar(*root,p)) == NULL)
  313.         *root = temp;
  314.     else if (p == p2->left)
  315.         p->left = temp;
  316.     else
  317.         p2->right = temp;
  318.  
  319.     if (p != x)
  320.     {
  321.         x->key = p->key;
  322.         x->info = p->info;
  323.         if(prv = prev(*root,p))
  324.             prv->next = x;
  325.     }
  326.  
  327. return p;
  328. }
  329.  
  330. node *search(node *root, int k)
  331. {
  332. node* cur;
  333.     cur = root;
  334.  
  335.     while (cur && (k != cur->key))
  336.     {
  337.         if(k < cur->key)
  338.             cur = cur->left;
  339.         else
  340.             cur = cur->right;
  341.     }
  342. return cur;
  343. }
  344.  
  345. int *insert(node **root, node *x)
  346. {
  347. node *cur, *p = NULL, *temp, *prv, *nxt;
  348. cur = *root;
  349.     while (cur)
  350.     {
  351.         p = cur;
  352.         if(x->key < cur->key)
  353.             cur = cur->left;
  354.         else
  355.             cur = cur->right;
  356.     }
  357.  
  358.     if (!p)
  359.         *root = x;
  360.  
  361.     else if(x->key < p->key)
  362.         temp=p->left=x;
  363.     else
  364.         temp=p->right=x;
  365.  
  366.     if(nxt=next(*root, x))
  367.         temp->next = nxt;
  368.     if(prv=prev(*root, x))
  369.         prv->next = temp;
  370.  
  371. return 1;
  372. }
  373.  
  374. char* antispace(char* str)
  375. {
  376.     for(; *str != '\0'; str++)
  377.         if (*str != ' ' && *str != '\t')
  378.             return str;
  379. return NULL;
  380. }
  381.  
  382. char* getstr()
  383. {
  384. char *ptr = (char *)malloc(1);
  385. char buf[101];
  386. int n, len = 0;
  387.     //printf("Input line: ");
  388.     *ptr = '\0';
  389.  
  390.     do
  391.     {
  392.         n = scanf("%100[^\n]", buf);
  393.  
  394.         if(n < 0)
  395.             {
  396.                 free(ptr);
  397.                 ptr = NULL;
  398.                 break;
  399.             }
  400.  
  401.     if(n == 0)
  402.         scanf("%*c");
  403.  
  404.     else
  405.         {
  406.             len += strlen(buf);
  407.             ptr = (char *) realloc(ptr, len + 1);
  408.             strcat(ptr, buf);
  409.         }
  410.  
  411.     }
  412.     while(n > 0);
  413. return ptr;
  414. }
  415.  
  416. int getInt(int *k)
  417. {
  418. int n;
  419.     n = scanf("%d", k);
  420.  
  421.     if (n < 0)
  422.         {
  423.             *k = 0;
  424.             return 0;
  425.         }
  426.  
  427.     if( (n == 0) || (scanf("%[a-z]") == 1) )
  428.         {
  429.             *k = -1;
  430.             fflush(stdin);
  431.             return *k;
  432.         }
  433.     else
  434.         {
  435.             fflush(stdin);
  436.             return n;
  437.         }
  438. }
  439.  
View raw paste Reply