#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>
typedef struct Node {
int n;
char *info[3];
int key[3];
struct Node *parent;
struct Node *ptr[4];
}Node;
typedef struct Table{
char *fd;
Node *root;
}Table;
const char *msgs[] = {"0. Quit","1. Add", "2. Show", "3. Delete", "4. Find", "5. Timing","6. Return next"};
const int NMsgs = sizeof(msgs)/ sizeof (msgs[0]);
Node *split(Node *,int );
Node *workhead(Node *);
Node *sit1(Node *,int k );
Node *sit2(Node *,int );
int D_Timing(Node **);
int dialog (const char *msgs[], int );
char *getstr();
const char *errmsgs[]={"Ok", "Duplicate key"};
const char *msgdel[]={"Ok","No Item"};
int dialog (const char *msgs[], int N)
{
char *errmsg = "";
int rc;
int i,n;
do{
puts(errmsg);
errmsg = "Wrong.Repeat";
for (i=0;i<N;++i)
puts(msgs[i]);
puts("Make your choise: -->");
n= getInt(&rc);
if (n == 0)
rc=0;
} while (rc < 0 || rc >= N);
return rc;
}
int getInt (int *a)
{
int n;
do{
n=scanf("%d",a,sizeof(int));
if (n<0)
return 0;
if (n==0)
{
printf("%s\n","Error! Repeat input");
scanf("%*c",0);
}
}while (n == 0);
return 1;
}
char *getstr()
{
char *ptr = (char *)malloc(1);
char buf[81];
int n, len = 0;
*ptr = '\0';
do {
n = scanf("%80[^\n]",buf);
if (n < 0)
{
free(ptr);
ptr = NULL;
continue;
}
if (n==0)
scanf("%*c");
else
{
len += strlen(buf);
ptr = (char *)realloc(ptr,len +1);
strcat(ptr,buf);
return ptr;
}
}while (n >= 0);
return ptr;
}
int D_Return(Node **root)
{
int k,rc,n,i,ver,c;
printf("Enter key:-->");
n=getInt(&k);
if (n==0)
return 0;
rc = findr (root,k);
if (rc==1)
printf("No item\n");
else
printf("Ok\n",k);
return 1;
}
int findr(Node **root,int k)
{
Node *cur=*root;
char *in;
int i,j,l,n;
while (cur != NULL)
{
j=cur->n;
for (i=0;i<cur->n;++i)
{
if (k==cur->key[i])
{
n=cur->n;
if (i< cur->n-1)
{
l=cur->key[i+1];
in=cur->key[i+1];
}
cur=cur->ptr[i+1];
if (cur != NULL)
{
printf("\"%s\" key:%d\n",cur->info[0],cur->key[0]);
return 0;
}
else
{
if (i< n-1)
{
printf("\"%s\" key:%d\n",in,l);
return 0;
}
}
return 1;
}
if (k < cur->key[i])
{
j=i;
break;
}
}
cur=cur->ptr[j];
}
}
int D_Find (Node **root)
{
int k,rc,n,i,ver,c;
printf("Enter key:-->");
n=getInt(&k);
if (n==0)
return 0;
rc = find (root,k);
if (rc==0)
printf("No item\n");
else
printf("Ok\n",k);
return 1;
}
int D_Add(Node **root)
{
int k,rc,ks,n;
char *info = NULL;
printf("Enter key:-->");
n=getInt(&k);
if (n==0)
return 0;
printf ("Enter info:\n");
info = getstr();
if (info == NULL)
return 0;
rc = insert(root,k ,info);
free(info);
printf("%s: %d\n",errmsgs[rc],k);
return 1;
}
int findplace(Node *cur)
{
int i,j,k;
Node *par=NULL;
k=cur->key[1];
par=cur->parent;
for (i=0;i<par->n;++i)
{
if (k < par->key[i])
return i;
}
return par->n;
}
int D_Delete (Node **root)
{
int k,rc,n,i,ver;
printf("Enter key:-->");
n=getInt(&k);
if (n==0)
return 0;
rc = del(root,k);
printf("%s: %d\n",msgdel[rc],k);
return 1;
}
Node *sit1(Node *cur,int k)
{
int j,i,p,n,s,r;
Node *rod,*x1=NULL,*x2=NULL,*z1,*z2;
while (cur != NULL)
{
j=cur->n;
for (i=0;i<cur->n;++i)
{
if (k==cur->key[i])
{
rod=cur->parent;
for(p=0;p<rod->n+1;++p)
{
if (rod->ptr[p]==cur)
break;
}
if (p+1 <=rod->n)
x1=rod->ptr[p+1];
if (p-1 >= 0)
x2=rod->ptr[p-1];
//if (x1 == NULL)
// x1=x2;
if (cur->n==1)
{
if (x1 != NULL)
if (x1->n >=2)
{
cur->key[1]=rod->key[p];
cur->info[1]=rod->info[p];
cur->n=cur->n+1;
rod->key[p]=x1->key[0];
rod->info[p]=x1->info[0];
cur->ptr[2]=x1->ptr[0];
x1->key[0]=x1->key[1];
x1->info[0]=x1->info[1];
x1->key[1]=x1->key[2];
x1->info[1]=x1->info[2];
x1->n=x1->n-1;
return cur;
}
if (x2 != NULL)
if ((x2->n >=2) && (rod->n > 1))
{
if (p < rod->n)
{
cur->key[1]=cur->key[0];
cur->info[1]=cur->info[0];
cur->ptr[2]=cur->ptr[1];
cur->ptr[1]=cur->ptr[0];
cur->ptr[0]=x2->ptr[x2->n-1];
cur->key[0]=rod->key[p-1];
cur->info[0]=rod->info[p-1];//
cur->n=cur->n+1;
}
//for(r=rod->n-1;r>p;--r)
//rod->ptr[r]=rod->ptr[r-1];
//rod->info[2]=rod->info[1];
//rod->key[1]=rod->key[0];
//rod->info[1]=rod->info[0];
//for (r=rod->n;r>p;--r)
//rod->ptr[r]=rod->ptr[r-1];
//rod->ptr[3]=rod->ptr[2];
//rod->ptr[2]=rod->ptr[1];
//rod->ptr[1]=rod->ptr[0];
// rod->ptr[p]=x2;
rod->key[p-1]=x2->key[x2->n-1];//
rod->ptr[p-1]=x2;
rod->info[p-1]=x2->info[x2->n-1];
if (p>= rod->n)
rod->n=rod->n+1;
x2->n=x2->n-1;
return cur;
}
}
else
{
if ((x1 != NULL) && (x2 != NULL))
if ((x1->n==1) && (x2->n==1) && (cur->n==1))
{
if ( x1 != NULL)
{
cur->key[1]=rod->key[p];
cur->info[1]=rod->info[p];
cur->key[2]=x1->key[0];
cur->info[2]=x1->info[0];
cur->ptr[2]=x1->ptr[0];
cur->ptr[3]=x1->ptr[1];
rod->n=rod->n-1;
for (s=p;s<rod->n-p;++s)
{
rod->key[s]=rod->key[s+1];
rod->info[s]=rod->info[s+1];
}
if (p==0)
{
rod->ptr[1]=rod->ptr[2];
rod->ptr[2]=rod->ptr[3];
}
if (p==1)
{
rod->ptr[2]=rod->ptr[3];
}
z1=x1->ptr[0];
z2=x1->ptr[1];
if (z1 != NULL)
z1->parent=cur;
if (z2 != NULL)
z2->parent=cur;
cur->n=3;
return cur;
}
/*else
if (x2 != NULL)
{
cur->key[2]=rod->key[p];
cur->info[2]=rod->info[p];
cur->key[2]=x1->key[0];
cur->info[2]=x1->info[0];
cur->ptr[2]=x1->ptr[0];
cur->ptr[3]=x1->ptr[1];
z1=x1->ptr[0];
z2=x1->ptr[1];
z1->parent=cur;
z2->parent=cur;
cur->n=3;
return cur;
}*/
}
}
return cur;
}
if (k < cur->key[i])
{
j=i;
break;
}
}
cur=cur->ptr[j];
}
return NULL;
}
Node *sit2(Node *cur,int i)
{
Node *y=cur->ptr[i],*z=cur->ptr[i+1],*z1,*z2,*rod;
int k,j;
char *in;
if (z->n >= 2 )
{
k=cur->key[i];
in=cur->info[i];
cur->key[i]=z->key[z->n-1];
cur->info[i]=z->info[z->n-1];
z->key[z->n-1]=k;
z->info[z->n-1]=in;
cur=z;
}
if (y->n >= 2 )
{
k=cur->key[i];
in=cur->info[i];
cur->key[i]=y->key[y->n-1];
cur->info[i]=y->info[y->n-1];
y->key[y->n-1]=k;
y->info[y->n-1]=in;
cur=y;
}
else
if (y->n >= 2 )
{
k=cur->key[i];
in=cur->info[i];
cur->key[i]=y->key[y->n-1];
cur->info[i]=y->info[y->n-1];
y->key[y->n-1]=k;
y->info[y->n-1]=in;
cur=y;
}
else if ((y->n == 1) && (z->n == 1))
{
y->key[1]=cur->key[i];
y->info[1]=cur->info[i];
cur->n=cur->n-1;//
cur->ptr[i+1]=NULL;
y->ptr[2]=z->ptr[0];
y->ptr[3]=z->ptr[1];
y->key[2]=z->key[0];
y->info[2]=z->info[0];
y->n=3;
z1=z->ptr[0];
z2=z->ptr[1];
if (z1 != NULL)
z1->parent=y;
if (z2 != NULL)
z2->parent=y;
for (j=i;j<cur->n-i;++j)//
{
cur->key[j]=cur->key[j+1];
cur->info[j]=cur->info[j+1];
}
if (i==0)
{
cur->ptr[1]=cur->ptr[2];
cur->ptr[2]=cur->ptr[3];
}
if (i==1)
{
cur->ptr[2]=cur->ptr[3];
}
free(z);
if (cur->n==0)
{
y->parent=cur->parent;
rod=cur->parent;
for (j=0;j<rod->n+1;++j)
if (rod->ptr[j]==cur)
{
rod->ptr[j]=y;
free(cur);
}
}
cur=y; //слияние
}
return cur;
}
int del(Node **root,int k)
{
Node *cur=*root,*br=NULL,*rod=NULL;
int i,j,c;
cur=workhead(cur);
*root=cur;
//cur=findIt(root,k);
if (cur==NULL)
return 1;
while((cur->ptr[0] != NULL) && (cur->ptr[0] != NULL) && (cur->ptr[0] != NULL) && (cur->ptr[0] != NULL))
{
for (i=0;i<cur->n;++i)
if (cur->key[i]==k)
{
cur=sit2(cur,i);
c++;
break;
}
if (c != 1)
cur=sit1(cur,k);
c=0;
if (cur==NULL)
return 1;
}
if (cur->n > 1)
{
for (i=0;i<cur->n;++i)
if (cur->key[i]==k)
{
cur->n=cur->n-1;
for (j=i;j<cur->n;++j)
{
cur->key[j]=cur->key[j+1];
cur->info[j]=cur->info[j+1];
}
return 0;
}
}
else {
rod=cur->parent;
if (rod == NULL)
{
*root=NULL;
free(cur);
return 0;
}
for(i=0;i<rod->n+1;++i)
{
if (rod->ptr[i] == cur)
{
if ((rod->ptr[i+1] != NULL) && (rod->n >= i+1))
{
br=rod->ptr[i+1];
if (br->n>1)
{
cur->key[0]=rod->key[i];
cur->info[0]=rod->info[i];
rod->key[i]=br->key[0];
rod->info[i]=br->info[0];
br->key[0]=br->key[1];
br->info[0]=br->info[1];
br->key[1]=br->key[2];
br->info[1]=br->info[2];
br->n=br->n-1;
return 0;
}
else
{
if (rod->n==1)
{
rod->n=2;
rod->key[1]=rod->key[0];
rod->info[1]=rod->info[0];
rod->key[0]=br->key[0];
rod->info[0]=br->info[0];
for (j=0;j<3;++j)
rod->ptr[j]=NULL;
free(cur);
free(br);
return 0;
}
else
rod->ptr[i]=NULL;
free(cur);
return 0;
}
}
else {
rod->ptr[i]=NULL;
free(cur);
return 0;
}
}
}
}
}
Node *workhead(Node *root)
{
Node *cur=root,*y,*z,*z1,*z2;
if ((cur->n==1) && (cur->ptr[0] != NULL) && (cur->ptr[1] != NULL))
{
if ((cur->ptr[0]->n==1) && (cur->ptr[1]->n==1))
{
y=cur->ptr[0];
z=cur->ptr[1];
z1=z->ptr[0];
z2=z->ptr[1];
y->n=3;
y->parent=NULL;
y->key[1]=cur->key[0];
y->key[2]=z->key[0];
y->ptr[2]=z->ptr[0];
y->ptr[3]=z->ptr[1];
z1->parent=y;
z2->parent=y;
free(z);
free(cur);
root=y;
//return *root;
}
}
return root;
}
Node *split(Node *cur,int j)
{
int i;
Node *par=cur->parent, *y=NULL,*x1=NULL,*x2=NULL;
if (par==NULL)
{
x1=cur->ptr[2];
x2=cur->ptr[3];
par=(Node *)malloc(sizeof(Node));
for (i=0;i<4;++i)
par->ptr[i]=NULL;
par->n=1;
y=(Node *)malloc(sizeof(Node));
for (i=0;i<4;++i)
y->ptr[i]=NULL;
y->n=1;
par->key[0]=cur->key[1];
par->info[0]=cur->info[1];
cur->n=1;
y->key[0]=cur->key[2];
y->info[0]=cur->info[2];
par->parent=NULL;
par->ptr[0]=cur;
par->ptr[1]=y;
par->ptr[2]=NULL;
par->ptr[3]=NULL;
cur->parent=par;
y->parent=par;
y->ptr[0]=cur->ptr[2];
y->ptr[1]=cur->ptr[3];
cur->ptr[2]=NULL;
cur->ptr[3]=NULL;
if(x1 != NULL)
x1->parent=y;
if (x2 != NULL)
x2->parent=y;
}
else {
x1=cur->ptr[2];
x2=cur->ptr[3];
for (i=2;i>j;--i)
{
par->key[i]=par->key[i-1];
par->info[i]=par->info[i-1];
}
for (i=3;i>j+1;--i)
par->ptr[i]=par->ptr[i-1];
par->ptr[j]=cur;
par->key[j]=cur->key[1];
par->info[j]=cur->info[1];
par->n=par->n+1;
y=(Node *)malloc(sizeof(Node));
for (i=0;i<4;++i)
y->ptr[i]=NULL;
par->ptr[j+1]=y;
y->parent=par;
y->n=1;
y->key[0]=cur->key[2];
y->info[0]=cur->info[2];
y->ptr[0]=cur->ptr[2];
y->ptr[1]=cur->ptr[3];
cur->n=1;
cur->parent=par;
cur->ptr[2]=NULL;
cur->ptr[3]=NULL;
if(x1 != NULL)
x1->parent=y;
if (x2 != NULL)
x2->parent=y;
}
return par;
}
int insert(Node **root,int k,char *info)
{
int i,j=0,f=0;
Node *newnode=NULL,*cur=NULL,head={0,{NULL,NULL,NULL},{0,0,0},NULL,{NULL,NULL,NULL,NULL}};
if (*root == NULL)
{
newnode=(Node *)malloc(sizeof(Node));
newnode->n=1;
newnode->key[0]=k;
newnode->info[0]=(char *)malloc(sizeof(char));
*(newnode->info[0])='\0';
newnode->info[0]=strcat(newnode->info[0],info);
newnode->parent=NULL;
for (i=0;i<4;++i)
newnode->ptr[i]=NULL;
//*(root).parent=newnode;
//root->parent=newnode;
head.ptr[0]=newnode;
*root=head.ptr[0];
return 0;
}
cur=*root;
while (cur != NULL)
{
if (cur->n==3)
{
if (cur->parent == NULL)
f=1;
if (!f)
j=findplace(cur);
cur=split(cur,j);
if (f)
*root=cur;
f=0;
}
for(i=0;i<cur->n;++i)
{
if (cur->key[i] == k)
return 1;
}
if (cur->key[0] > k)
{
if (cur->ptr[0]==NULL)
{
cur->key[2]=cur->key[1];
cur->info[2]=cur->info[1];
cur->key[1]=cur->key[0];
cur->info[1]=cur->info[0];
cur->key[0]=k;
cur->info[0]=(char *)malloc(sizeof(char));
*(cur->info[0])='\0';
cur->info[0]=strcat(cur->info[0],info);
cur->ptr[3]=cur->ptr[2];
cur->ptr[2]=cur->ptr[1];
cur->ptr[1]=NULL;
cur->n=cur->n+1;
return 0;
}
else
{
cur=cur->ptr[0];
continue;
}
}
if (((cur->key[0] < k) && (k < cur->key[1])) || ((cur->key[0] < k) &&(cur->n==1)))
{
if (cur->ptr[1]==NULL)
{
cur->key[2]=cur->key[1];
cur->info[2]=cur->info[1];
cur->ptr[3]=cur->ptr[2];
cur->ptr[2]=NULL;
cur->key[1]=k;
cur->info[1]=(char *)malloc(sizeof(char));
*(cur->info[1])='\0';
cur->info[1]=strcat(cur->info[1],info);
cur->n=cur->n+1;
return 0;
}
else {
cur=cur->ptr[1];
continue;
}
}
if ((k > cur->key[1]) && (cur->n==2))
{
if (cur->ptr[2]==NULL)
{
cur->key[2]=k;
cur->info[2]=(char *)malloc(sizeof(char));
*(cur->info[2])='\0';
cur->info[2]=strcat(cur->info[2],info);
cur->n=3;
cur->ptr[3]=NULL;
return 0;
}
else {
cur=cur->ptr[2];
}
}
}
}
int find(Node **root,int k)
{
Node *cur=*root;
int i,j;
while (cur != NULL)
{
j=cur->n;
for (i=0;i<cur->n;++i)
{
if (k==cur->key[i])
{
printf("\"%s\" key:%d\n",cur->info[i],cur->key[i]);
return 1;
}
if (k < cur->key[i])
{
j=i;
break;
}
}
//if (cur->ptr[j] != NULL)
cur=cur->ptr[j];
}
return 0;
}
int findt(Node **root,int k)
{
Node *cur=*root;
int i,j;
while (cur != NULL)
{
j=cur->n;
for (i=0;i<cur->n;++i)
{
if (k==cur->key[i])
return 1;
if (k < cur->key[i])
{
j=i;
break;
}
}
//if (cur->ptr[j] != NULL)
cur=cur->ptr[j];
}
return 0;
}
void printTree(Node *root,int level)
{
int i;
if (root)
{
printTree(root->ptr[0],level+1);
for ( i=0;i<level;i++)
printf(" ");
if (root->n==1)
{
printf(" {%d} \n",root->key[0]);
printf("\n");
}
else printf(" {%d \n",root->key[0]);
if (root->n > 1)
{
for ( i=0;i<level;i++)
printf(" ");
if (root->n==2)
{
printf(" %d} \n",root->key[1]);
printf("\n");
}
else printf(" %d \n",root->key[1]);
}
printTree(root->ptr[1],level+1);
printTree(root->ptr[2],level+1);
if (root->n > 2){
for ( i=0;i<level;i++)
printf(" ");
printf(" %d}\n",root->key[2]);
printf("\n");
}
printTree(root->ptr[3],level+1);
}
}
void reserve(Node *root)
{
if (root ==NULL)
{
return;
}
reserve(root->ptr[3]);
if (root->n ==3)
printf("%d:%s ",root->key[2],root->info[2]);
reserve(root->ptr[2]);
if (root->n>1)
printf("%d:%s ",root->key[1],root->info[1]);
reserve(root->ptr[1]);
printf("%d:%s ",root->key[0],root->info[0]);
reserve(root->ptr[0]);
}
int D_Show(Node **root)
{
int level=0,k,n;
Node *cur=*root;
printf("Which kind of form?\n");
printf("0.Tree N.Inverse\n");
n=getInt(&k);
if (n==0)
return 0;
if (k==0)
printTree(cur,level);
else
reserve(cur);
return 1;
}
int D_Load (Table *ptab)
{
//int SZ;
int rc;
char *fname = NULL;
printf("Enter file name: -->");
fname = getstr();
if (fname == NULL)
return 0;
rc=load(ptab,fname);
if (rc == 0)
puts("The appropriate date file is not exists");
free(fname);
return rc;
}
int load(Table *ptab,char *fname)
{
FILE *ft=NULL;
int ln=strlen(fname),k,i,rc;
char *info=NULL;
ptab->fd=(char *)malloc(1);
*(ptab->fd)='\0';
ptab->fd=(char *)realloc(ptab->fd,ln);
ptab->fd=strcat(ptab->fd,fname);
//fopen_s(&(ptab->fi),fd,"r+b");//файл данных
ft=fopen(fname,"r");
if (ft==NULL)
{
ft=fopen(fname,"w");
if (ft==NULL)
return 0;
close(ft);
}
else
{
fseek(ft,0,SEEK_SET);
while (1)
{
rc=fscanf(ft,"%d",&k);
if (rc == -1)
break;
info=(char *)malloc(sizeof(char));
rc=fscanf(ft,"%s\n",info);
insert(&(ptab->root),k,info);
}
}
close(ft);
return 1;
}
int D_Save(Table *ptab)
{
FILE *fd=NULL;
int i,c=0;
fd=fopen(ptab->fd,"w");
if (fd==NULL)
return 0;
save(fd,ptab->root,c);
//fseek(fd,0,SEEK_END);
//fprintf(fd,"%d\n",ptab->n);
fclose(fd);
return 1;
}
void save(FILE *fp,Node *cur)
{
//Node *cur=*root;
if (cur ==NULL)
{
return;
}
save(fp,cur->ptr[3]);
if (cur->n==3)
{
fprintf(fp,"%d\n",cur->key[2]);
fprintf(fp,"%s\n",cur->info[2]);
}
save(fp,cur->ptr[2]);
if(cur->n > 1)
{
fprintf(fp,"%d\n",cur->key[1]);
fprintf(fp,"%s\n",cur->info[1]);
}
save(fp,cur->ptr[1]);
fprintf(fp,"%d\n",cur->key[0]);
fprintf(fp,"%s\n",cur->info[0]);
save(fp,cur->ptr[0]);
}
void delTree(Node *root)
{
if (root ==NULL)
{
return;
}
delTree(root->ptr[0]);
delTree(root->ptr[1]);
delTree(root->ptr[2]);
delTree(root->ptr[3]);
free(root);
}
int D_Timing(Node **cur)
{
Node *root=NULL;
int n=10, key[10000],k,cnt=1000000,i,m;
clock_t first,last;
srand(time(NULL));
while (n-- > 0)
{
for (i=0;i < 10000; ++i)
key[i]= rand()*rand();
for (i = 0;i<cnt;)
{
k=rand()*rand();
if (!insert(&root,k,"a"))
++i;
}
m=0;
first = clock();
for (i=0;i<10000;++i)
if (findt(&root,key[i]))
++m;
last=clock();
printf("%d items was found\n",m);
printf("test #%d, number of nodes = %d, time = %d\n", 10-n,(10-n)*cnt,last-first);
}
delTree(root);
return 1;
}
int main() {
Table ptab;
int rc,kc;
int (*fptr[])(Node **)={NULL,D_Add,D_Show,D_Delete,D_Find,D_Timing,D_Return};
ptab.root=NULL;
if (D_Load(&ptab)==0)
return 1;
while (rc=dialog(msgs,NMsgs))
if (!fptr[rc](&(ptab.root)))
break;
kc=D_Save(&ptab);
if (kc==0)
printf("Invalid save");
delTree(ptab.root);
printf("That all");
return 0;
}