//majdal hindi //1071842 //project #3 #include #include #include #include #include #include typedef struct avlnode *avltree; struct avlnode{ char name[100] ; char number[100]; avltree left; avltree right; int height; }; typedef avltree AvlTree; /* locate a value in the btree */ AvlTree find (AvlTree p, char* key) { AvlTree temp; temp = p; while(temp != NULL) { if(strcmp(temp->name, key)==0) return temp; else if(strcmp(temp->name, key)==1) temp = temp->left; else temp = temp->right; } return NULL; } AvlTree FindMin( AvlTree T ) { if( T == NULL ) return NULL; else if( T->left == NULL ) return T; else return FindMin( T->left ); } AvlTree FindMax( AvlTree T ) { if( T != NULL ) while( T->right != NULL ) T = T->right; return T; } int Height(AvlTree P ) { if( P == NULL ) return -1; else return P->height; } int Max( int Lhs, int Rhs ) { return Lhs > Rhs ? Lhs : Rhs; } /* This function can be called only if K2 has a left child */ /* Perform a rotate between a node (K2) and its left child */ /* Update heights, then return new root */ AvlTree SingleRotateWithLeft( AvlTree K2 ) { AvlTree K1; K1 = K2->left; K2->left = K1->right; K1->right = K2; K2->height = Max( Height( K2->left ), Height( K2->right ) ) + 1; K1->height = Max( Height( K1->left ), K2->height ) + 1; return K1; /* New root */ } /* END */ /* This function can be called only if K1 has a right child */ /* Perform a rotate between a node (K1) and its right child */ /* Update heights, then return new root */ AvlTree SingleRotateWithRight( AvlTree K1 ) { AvlTree K2; K2 = K1->right; K1->right = K2->left; K2->left = K1; K1->height = Max( Height( K1->left ), Height( K1->right ) ) + 1; K2->height = Max( Height( K2->right ), K1->height ) + 1; return K2; /* New root */ } /* This function can be called only if K3 has a left */ /* child and K3's left child has a right child */ /* Do the left-right double rotation */ /* Update heights, then return new root */ AvlTree DoubleRotateWithLeft( AvlTree K3 ) { /* Rotate between K1 and K2 */ K3->left = SingleRotateWithRight( K3->left ); /* Rotate between K3 and K2 */ return SingleRotateWithLeft( K3 ); } /* END */ /* This function can be called only if K1 has a right */ /* child and K1's right child has a left child */ /* Do the right-left double rotation */ /* Update heights, then return new root */ AvlTree DoubleRotateWithRight( AvlTree K1 ) { /* Rotate between K3 and K2 */ K1->right = SingleRotateWithLeft( K1->right ); /* Rotate between K1 and K2 */ return SingleRotateWithRight( K1 ); } /* START: fig4_37.txt */ AvlTree Insert( char nam[],char num[], AvlTree T ) { if( T == NULL ) { /* Create and return a one-node tree */ T = malloc( sizeof( struct avlnode ) ); if( T == NULL ) printf( "Out of space!!!" ); else { strcpy(T->name ,nam); strcpy(T->number,num); T->height = 0; T->left = T->right = NULL; } } else if( strcmp(nam , T->name )<0) { T->left = Insert( nam,num, T->left ); if( Height( T->left ) - Height( T->right ) == 2 ) { if(strcmp( nam , T->left->name )<0) T = SingleRotateWithLeft( T ); else T = DoubleRotateWithLeft( T ); } } else if( strcmp(nam , T->name )>0) { T->right = Insert( nam,num, T->right ); if( Height( T->right ) - Height( T->left ) == 2 ) { if( strcmp(nam , T->right->name )>0) T = SingleRotateWithRight( T ); else T = DoubleRotateWithRight( T ); } } /* Else X is in the tree already; we'll do nothing */ T->height = Max( Height( T->left ), Height( T->right ) ) + 1; return T; } /* END */ AvlTree Delete( char X[] , AvlTree T ) { AvlTree TmpCell; if( T == NULL ) printf( "Element not found" ); else if ( strcmp(X , T->name )<0) { /* Go left */ T->left = Delete( X, T->left ); if(Height(T->left)-Height(T->right)==2){ if(strcmp(X,T->left->name)<0) T=SingleRotateWithRight(T); else T=DoubleRotateWithRight(T); } } else if(strcmp( X , T->name ) >0) /* Go right */ T->right = Delete( X, T->right ); if(Height(T->right)-Height(T->left)==2) { if(strcmp(X,T->right->name)>0) T=SingleRotateWithLeft(T); else T=DoubleRotateWithLeft(T); } else { /* Found element to be deleted */ if( T->left && T->right ) /* Two children */ { /* Replace with smallest in right subtree */ TmpCell = FindMin( T->right ); strcpy(T->name , TmpCell->name); strcpy(T->number,TmpCell->number); T->right = Delete( T->name, T->right ); } else /* One or zero children */ { TmpCell = T; if( T->left == NULL ) /* Also handles 0 children */ T = T->right; else if( T->right == NULL ) T = T->left; free( TmpCell ); } } return T; } /* END */ void inorder(AvlTree T) { if(T!=NULL) { inorder(T->left); printf("%s\t%s\n ",T->name,T->number); inorder(T->right); } } void preorder(AvlTree T) { if(T!='\0') { printf("%s\t%s\n",T->name,T->number); preorder(T->left); preorder(T->right); } } void postorder(AvlTree T) { if(T!=NULL) { postorder(T->left); postorder(T->right); printf("%s\t%s\n",T->name,T->number); } } void writetofile(AvlTree T,FILE*in) { if(T!=NULL) { writetofile(T->left,in); fprintf(in,"%s\t%s\n",T->name,T->number); writetofile(T->right,in); } } int count_number_line(char a[]) { char ch; int count =0; FILE*in; in=fopen(a,"r"); if(in==NULL) printf("%s is not found \n",a); while((ch=fgetc(in))!=EOF) { if(ch=='\n') ++count; } return ++count; } AvlTree read_data_tree( char filename[]) { FILE *in; char st[80],nam[80],num[80]; int i=0; in= fopen(filename,"r"); int k; int s; AvlTree T; T=NULL; s=count_number_line(filename); for(k=0;kflag==1){ key=(key+i)%hsize; i++; } strcpy(ht[key]->name,nam); strcpy(ht[key]->number,num); ht[key]->flag=1; } void read_data_hash (hashtable ht[],int hsize,char filename[]) { int i; FILE *in; for(i=0;iflag=0; } char st[80],nam[80],num[80]; i=0; in= fopen(filename,"r"); int k; int s; s=count_number_line(filename); for(k=0;kname,nam)!=0)&&(i<=hsize)) { key=(key+i)%hsize; i++; } if(i>hsize||ht[key]->flag==2) return -1; else return key; } void hashdelete(hashtable ht[],int hsize,char nam[]) { int key=0; int i=1; key=hashfunction(nam,hsize); while(strcmp(ht[key]->name,nam)!=0&&i<=hsize) { key=(key+i)%hsize; i++; } if(!(iflag==2)) ht[key]->flag=2; } void print(hashtable ht[],int hsize,int choice) { int i=0; if(choice==1) { for(i=0;iflag==1) printf("%s\t%s\n",ht[i]->name,ht[i]->number); } } else if(choice==2) { char st[80]; FILE *out; printf("enter the file name\n"); scanf("%s",st); out=fopen(st,"w"); for(i=0;iflag==1) fprintf(out,"%s\t%s\n",ht[i]->name,ht[i]->number); } } else if(choice!=1&&choice!=2) exit(0); } int main() { char file[80],nam[80],num[80]; int size,f; AvlTree k,t; k=NULL; t=NULL; hashtable H[400]; for(;;) { int i=menu(); switch(i) { case 1: { int sub=sub_menu(); switch(sub) { case 1:{ printf("enter the name of the file: \n"); scanf("%s",file); size=count_number_line(file); k=read_data_tree(file); }break; case 2: { printf("Enter name, find: "); scanf("%s", nam); t = find(k, nam); if(t == NULL) printf(" * %s Not! found in file\n",nam); else printf(" the number %s \n", t->number); }break; case 3: { printf("enter the name \n"); scanf("%s",nam); printf("enter the number\n"); scanf("%s",num); k=Insert(nam,num,k); }break; case 4: { int h; printf("\t\t print\n"); printf("1-inorder\n2-preorder\n3-postorder\n"); scanf("%d",&h); switch(h) { case 1: { printf("inorder\n"); inorder(k); } break; case 2: { printf("preorder\n"); preorder(k); }break; case 3: { printf("postorder\n"); postorder(k); }break; }break; case 5: { printf("enter the name you want to delete \n"); scanf("%s",nam); k=Delete(nam,k); }break; case 6: { printf("enter the name of the file \n"); scanf("%s",nam); FILE*d; d=fopen(nam,"w"); writetofile(k,d); }break; case 7: { int i=Height(k); printf(" the height = %d",i); }break; case 8:exit(0);break; } }break; case 2: { int sub2=sub_menu_3(); switch(sub2) { case 1: { printf("enter the name of the file\n"); scanf("%s",file); size=count_number_line(file); size=nextprime(2*size); read_data_hash(H,size,file); }break; case 2:{ printf("Enter the name you want to search \n"); scanf("%s",nam); f=hashsearch(H,size,nam); printf("%s\t%s",nam,H[f]->number); }break; case 3: { printf("enter the string you want to insert\n"); scanf("%s",nam); printf("enter the number\n"); scanf("%s",num); hashinsert(H,size,nam,num); }break; case 4: { int sub3=sub_menu_4(); switch(sub3) { case 1:print(H,size,1); break; case 2:print(H,size,2); break; case 3:exit(0); break; } }break; case 5: { printf("Enter the string you want to delete\n"); scanf("%s",nam); hashdelete(H,size,nam); }break; case 6: { printf("about hashing :\n"); printf("the size=%d",size); }break; case 7:exit(0); break; } }break; case 3:exit(0); break; } } } return 0; }