#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *getstr();
int getInt(int *N);
char* antispace(char* str);
const char *msgs[]={"0. End","1. Add Item", "2. Find Item", "3. Find Minimum", "4. Delete Item", "5. Show Table"};
const int Nmsgs = sizeof(msgs)/sizeof(msgs[0]);
typedef struct node
{
int key;
char* info;
struct node *left;
struct node *right;
struct node *next;
}node;
int dialog(const char *msgs[], int N);
int D_Add(node **root),
D_Find(node **root),
D_FindMin(node **root),
D_Delete(node **root),
D_Show(node **root);
int (*fptr[])(node **root) = {NULL,D_Add,D_Find,D_FindMin,D_Delete,D_Show};
node *delete(node **root, node *x);
node *search(node *root, int k);
node *getpar(node *root, node *x);
node *next(node *root, node *x);
node *prev(node *root, node *x);
int *insert(node **root, node *x);
node *minimum(node *root, int k);
int main()
{
node *root = NULL;
int rc;
while(rc = dialog(msgs, Nmsgs))
{
fptr[rc](&root);
}
return 0;
}
int dialog(const char *msgs[], int N)
{
int rc = 1, i;
do
{
if (rc < 0 || rc >= N)
puts("Sorry, your request is wrong. Please, try again");
else
puts("Please, put the number of selected action:");
for (i = 0; i < N; i++)
puts(msgs[i]);
getInt(&rc);
}
while (rc < 0 || rc >= N) ;
return rc;
}
int D_Add(node **root)
{
int k, n = 1;
char *info;
node* x;
info = (char*)malloc(sizeof(char));
do
{
if(n<0 || k<0)
puts("Wrong key. Please try again:");
else
puts("Enter key:");
n=getInt(&k);
if(search(*root,k))
puts("The element with this key is exist already. Please try again:");
}
while (n < 0 || k < 0 || (search(*root,k)));
if(n == 0)
return 0;
do
{
if (info == NULL)
puts("Info is empty. Please try again:");
else
puts("Enter info:");
info = getstr();
if (info != NULL)
info = antispace(info);
else
return 0;
}
while (info == NULL);
x = (node*)malloc(sizeof(node));
x->info = info;
x->key = k;
x->left = NULL;
x->right = NULL;
x->next = NULL;
insert(root, x);
puts("Table extended");
}
int D_Find(node **root)
{
int k, n = 1;
node *cur;
do
{
if(n < 0 || k < 0)
puts("Wrong key. Please try again:");
else
puts("Enter key:");
n = getInt(&k);
}
while (n < 0 || k < 0);
if(n == 0)
return 0;
if (cur = search(*root, k))
printf("Found node: Key = %d, Info = %s\n", cur
->key
, cur
->info
); else
puts("Node not found");
}
int D_FindMin(node **root)
{
int k, n = 1;
node *cur, *x;
cur=*root;
do
{
if(n < 0 || k < 0)
puts("Wrong key. Please try again:");
else
puts("Enter key:");
n = getInt(&k);
}
while (n < 0 || k < 0);
if(n == 0)
return 0;
if (cur && (x = minimum(*root, k)))
printf("Found node: Key = %d, Info = %s\n", x
->key
, x
->info
); else
puts("Node not found");
}
int D_Delete(node **root)
{
int k, n = 1;
node *x;
do
{
if(n < 0 || k < 0)
puts("Wrong key. Please, try again:");
else
puts("Enter key:");
n = getInt(&k);
}
while (n < 0 || k < 0);
if(n == 0)
return 0;
if(x = search(*root, k))
{
delete(root, x);
puts("Node deleted");
}
else
puts("Item not found");
}
int D_Show(node **root)
{
node* cur;
cur = *root;
if(cur)
for(; cur->left; cur = cur->left);
puts("///////////////////////");
if(cur == NULL)
puts("Table is empty");
for(; cur; cur = cur->next)
printf("Node: Key is %d, Info is %s\n", cur
->key
, cur
->info
); puts("///////////////////////");
}
node *getpar(node *root, node *x)
{
node *cur, *p = NULL;
cur = root;
while (cur && (x->key != cur->key))
{
p = cur;
if(x->key < cur->key)
cur = cur->left;
else
cur = cur->right;
}
if (!cur)
p = NULL;
return p;
}
node *next(node *root,node *x)
{
node* min, *p;
if (x->right)
{
min = x->right;
while(min->left)
min = min->left;
return min;
}
p = getpar(root,x);
while(p && (x == p->right))
{
x = p;
p = getpar(root,p);
}
return p;
}
node *prev(node *root, node *x)
{
node *max, *p;
if (x->left)
{
max = x->left;
while(max->right)
max = max->right;
return max;
}
p = getpar(root, x);
while(p && (x == p->left))
{
x = p;
p = getpar(root, p);
}
return p;
}
node *minimum(node *root, int k)
{
node *cur, *p = NULL;
if (cur = search(root, k))
return next(root, cur);
cur = root;
while (cur)
{
p = cur;
if(k < cur->key)
cur = cur->left;
else
cur = cur->right;
}
if(k < p->key)
return p;
else
while(p && (cur == p->right))
{
cur = p;
p = getpar(root, p);
}
return p;
}
node *delete(node **root, node *x)
{
node *p = NULL, *p2 = NULL, *temp = NULL, *prv, *nxt;
p = x;
if(prv = prev(*root, p))
{
if(nxt = next(*root, p))
{
prv->next = nxt;
}
else
{
prv->next = NULL;
}
}
else if(nxt = next(*root, p))
p = NULL;
if(x->left == NULL || x->right == NULL)
p = x;
else
p = prev(*root,x);
if (p->left)
temp = p->left;
else
temp = p->right;
if ((p2 = getpar(*root,p)) == NULL)
*root = temp;
else if (p == p2->left)
p->left = temp;
else
p2->right = temp;
if (p != x)
{
x->key = p->key;
x->info = p->info;
if(prv = prev(*root,p))
prv->next = x;
}
return p;
}
node *search(node *root, int k)
{
node* cur;
cur = root;
while (cur && (k != cur->key))
{
if(k < cur->key)
cur = cur->left;
else
cur = cur->right;
}
return cur;
}
int *insert(node **root, node *x)
{
node *cur, *p = NULL, *temp, *prv, *nxt;
cur = *root;
while (cur)
{
p = cur;
if(x->key < cur->key)
cur = cur->left;
else
cur = cur->right;
}
if (!p)
*root = x;
else if(x->key < p->key)
temp=p->left=x;
else
temp=p->right=x;
if(nxt=next(*root, x))
temp->next = nxt;
if(prv=prev(*root, x))
prv->next = temp;
return 1;
}
char* antispace(char* str)
{
for(; *str != '\0'; str++)
if (*str != ' ' && *str != '\t')
return str;
return NULL;
}
char* getstr()
{
char *ptr = (char *)malloc(1);
char buf[101];
int n, len = 0;
//printf("Input line: ");
*ptr = '\0';
do
{
n = scanf("%100[^\n]", buf);
if(n < 0)
{
free(ptr);
ptr = NULL;
break;
}
if(n == 0)
scanf("%*c");
else
{
len += strlen(buf);
ptr = (char *) realloc(ptr, len + 1);
strcat(ptr, buf);
}
}
while(n > 0);
return ptr;
}
int getInt(int *k)
{
int n;
n = scanf("%d", k);
if (n < 0)
{
*k = 0;
return 0;
}
if( (n == 0) || (scanf("%[a-z]") == 1) )
{
*k = -1;
fflush(stdin);
return *k;
}
else
{
fflush(stdin);
return n;
}
}
