Author: Not specified Language: c
Description: Not specified Timestamp: 2013-06-01 12:41:21 +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. Delete Item", "4. Show in the order of addition", "5. Show from the largest key"};
  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, node **first),
  22.     D_Find(node **root, node **first),
  23.     D_ShowL(node **root, node **first),
  24.     D_Delete(node **root, node **first),
  25.     D_Show(node **root, node **first);
  26. int (*fptr[])(node **root, node **first) = {NULL,D_Add,D_Find,D_Delete,D_Show,D_ShowL};
  27.  
  28. node *delete(node **root,node **first,node *x);
  29. node *search(node *root, int k);
  30. node *getpar(node *root,node *x);
  31. node *next(node *root,node *x);
  32. int *insert(node **root, node **first, node *x);
  33. void out(node *cur, int k);
  34.  
  35. int main()
  36. {
  37.  
  38.     node *root=NULL, *first=NULL;
  39.     int rc;
  40.     while(rc = dialog(msgs, Nmsgs))
  41.     {
  42.         fptr[rc](&root, &first);
  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, node **first)
  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("Your key is wrong. 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 already exists. Please try again:");
  82.     }
  83.     while (n<0 || k<0 || (search(*root,k)));
  84.  
  85.     if(n == 0)
  86.         return 0;
  87.     do
  88.     {
  89.         if (info == NULL)
  90.             puts("Info is empty. Please try again:");
  91.         else
  92.             puts("Enter info:");
  93.  
  94.         info = getstr();
  95.         if (info != NULL)
  96.         info = antispace(info);
  97.             else
  98.         return 0;
  99.     }
  100.     while (info == NULL);
  101.  
  102.     x=(node*)malloc(sizeof(node));
  103.     x->info=info;
  104.     x->key=k;
  105.     x->left=NULL;
  106.     x->right=NULL;
  107.     x->next=NULL;
  108.     insert(root,first,x);
  109.     puts("Table added");
  110.  
  111. }
  112.  
  113. int D_Find(node **root, node **first)
  114. {
  115.     int k,n=1;
  116.     node *cur;
  117.     do
  118.     {
  119.         if(n<0 || k<0)
  120.             puts("Your key is wrong. 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_Delete(node **root, node **first)
  137. {
  138.  int k,n=1;
  139.  node *x, *nxt, *prv;
  140.     do
  141.     {
  142.         if(n<0 || k<0)
  143.             puts("Your key is wrong. Please try again:");
  144.         else
  145.             puts("Enter key:");
  146.         n=getInt(&k);
  147.     }
  148.     while (n<0 || k<0);
  149.  
  150.     if(n == 0)
  151.         return 0;
  152.  
  153.     if(x=search(*root,k))
  154.     {
  155.         free(delete(root,first,x));
  156.         puts("Node deleted");
  157.     }
  158.     else
  159.         puts("Item not found");
  160. }
  161.  
  162. int D_Show(node **root, node **first)
  163. {
  164.     node* cur;
  165.     cur=*first;
  166.     puts("/////////////");
  167.     for(;cur;cur=cur->next)
  168.         if(cur->key)
  169.             printf("Node: Key is %d, Info is %s\n",cur->key,cur->info);
  170.     if(!(*root))
  171.         puts("Table is empty");
  172.     puts("/////////////");
  173.  
  174. }
  175. int D_ShowL(node **root, node **first)
  176. {
  177.     node* cur;
  178.     cur=*root;
  179.     int k,n=1;
  180.     if((*root)->left)
  181.     puts("/////////////");
  182.     if(cur)
  183.         out(cur,k);
  184.     else
  185.         puts("Table is empty");
  186.     puts("/////////////");
  187.  
  188. }
  189.  
  190. void out(node *cur, int k)
  191. {
  192.     if(cur->right && (cur->right->key))
  193.         out((cur->right),k);
  194.     if(cur->key)
  195.     printf("Item: Key - %d, Info - %s\n",cur->key,cur->info);
  196.     if(cur->left && (cur->left->key))
  197.         out((cur->left),k);
  198.     free(cur->key);
  199.  
  200. }
  201.  
  202. node *next(node *root,node *x)
  203. {
  204.     node* min, *p;
  205.     if (x->right)
  206.     {
  207.         min=x->right;
  208.         while(min->left)
  209.             min=min->left;
  210.         return min;
  211.     }
  212.     p=getpar(root,x);
  213.     while(p && (x == p->right))
  214.     {
  215.         x=p;
  216.         p=getpar(root,p);
  217.     }
  218.     return p;
  219. }
  220.  
  221. node *getpar(node *root,node *x)
  222. {
  223.  
  224.     node *cur, *p=NULL;
  225.     cur=root;
  226.     while (cur && (x->key != cur->key))
  227.     {
  228.         p=cur;
  229.         if(x->key < cur->key)
  230.             cur=cur->left;
  231.         else
  232.             cur=cur->right;
  233.     }
  234.     if (!cur)
  235.         p=NULL;
  236.  
  237.     return p;
  238. }
  239.  
  240. node *delete(node **root,node **first,node *x)
  241. {
  242.     node *p=NULL,*p2=NULL,*temp=NULL, *cur;
  243.  
  244.     if(x->left == NULL || x->right == NULL)
  245.         p=x;
  246.     else
  247.         p=next(*root,x);
  248.  
  249.     if (p->left)
  250.         temp=p->left;
  251.     else
  252.         temp=p->right;
  253.     if ((p2=getpar(*root,p)) == NULL)
  254.         *root=temp;
  255.  
  256.     else if (p == p2->left)
  257.         p2->left=temp;
  258.     else
  259.         p2->right=temp;
  260.  
  261.     if ((*root) == (*first))
  262.         if ((*root))
  263.             (*first)=(*first)->next;
  264.     if (p != x)
  265.     {
  266.  
  267.         x->key=p->key;
  268.         x->info=p->info;
  269.         x->next=p->next;
  270.         for(cur=(*first);cur->next;cur=cur->next)
  271.             if(cur->next == x)
  272.                 cur->next=x->next;
  273.  
  274.         if(x->next != p)
  275.         {
  276.             if(x == (*first))
  277.                 (*first)=x->next;
  278.             for(cur=(*first);cur->next;cur=cur->next)
  279.                 if(cur->next == p)
  280.                     cur->next=x;
  281.         }
  282.         else
  283.             x->next=p->next;
  284.  
  285.  
  286.     }
  287.     else
  288.     {
  289.         if((*first)->next && x == (*first))
  290.             (*first)=(*first)->next;
  291.         else
  292.             for(cur=(*first);cur->next;cur=cur->next)
  293.                 if(cur->next == x)
  294.                     cur->next=x->next;
  295.     }
  296.  
  297.  
  298.    return p;
  299.  
  300.  
  301. }
  302.  
  303. node *search(node *root, int k)
  304. {
  305.     node* cur;
  306.  
  307.     cur=root;
  308.  
  309.     while (cur && (k != cur->key))
  310.     {
  311.  
  312.         if(k < cur->key)
  313.             cur=cur->left;
  314.         else
  315.             cur=cur->right;
  316.  
  317.     }
  318.  
  319.     return cur;
  320. }
  321.  
  322. int *insert(node **root, node **first, node *x)
  323. {
  324.     node *cur, *p=NULL, *last;
  325.     cur=*root;
  326.     while (cur)
  327.     {
  328.         p=cur;
  329.         if(x->key < cur->key)
  330.             cur=cur->left;
  331.         else
  332.             cur=cur->right;
  333.     }
  334.  
  335.     if (!p)
  336.     {
  337.         *root=x;
  338.         *first=x;
  339.     }
  340.  
  341.  
  342.  
  343.     else
  344.  
  345.     {
  346.         for(last=*first;last->next;last=last->next);
  347.         last->next=x;
  348.         if(x->key < p->key)
  349.             p->left=x;
  350.         else
  351.             p->right=x;
  352.     }
  353.  
  354.     return 1;
  355. }
  356.  
  357.  
  358. char* getstr()
  359. {
  360.  
  361.     char *ptr = (char *)malloc(1);
  362.     char buf[21];
  363.     int n, len = 0;
  364.     *ptr = '\0';
  365.     do
  366.     {
  367.         n = scanf("%20[^\n]", buf);
  368.         if(n < 0)
  369.         {
  370.  
  371.             free(ptr);
  372.             ptr = NULL;
  373.             break;
  374.  
  375.         }
  376.         if(n == 0)
  377.             scanf("%*c");
  378.  
  379.  
  380.         else
  381.         {
  382.             len += strlen(buf);
  383.             ptr = (char *) realloc(ptr, len + 1);
  384.             strcat(ptr, buf);
  385.         }
  386.  
  387.     }
  388.  
  389.     while(n > 0);
  390.     return ptr;
  391. }
  392.  
  393. int getInt(int *N)
  394. {
  395.     int n;
  396.     n=scanf("%d",N);
  397.  
  398.         if (n < 0)
  399.         {
  400.             *N=0;
  401.             return 0;
  402.         }
  403.  
  404.         if( (n == 0) || (scanf("%[a-z]") == 1) )
  405.         {
  406.             *N=-1;
  407.             fflush(stdin);
  408.             return*N;
  409.         }
  410.         else
  411.         {
  412.             fflush(stdin);
  413.             return n;
  414.         }
  415.  
  416.  
  417. }
  418.  
  419.  
  420. char* antispace(char* str)
  421. {
  422.     for(;*str!='\0';str++)
  423.         if (*str != ' ' && *str != '\t')
  424.             return str;
  425.     return NULL;
  426. }
View raw paste Reply