Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // main.c
- // trees
- //
- // Created by Mahmoud ElMarakshy on 4/28/13.
- // Copyright (c) 2013 Mahmoud ElMarakshy. All rights reserved.
- //
- #include<stdio.h>
- #include<stdio.h>
- #include <ctype.h>
- struct node{
- char * data;
- struct node *left;
- struct node *right;
- char * id;
- }*root=NULL,*root2=NULL,*temp;
- struct node* insert(struct node *root,char x[],char id[]);
- struct node* insert2(struct node *root,char x[],char id[]);
- struct node * delete(struct node*ptr,char a[]);
- void traverse(struct node*ptr);
- struct node * Findmin(struct node*ptr);
- char* search(struct node *root,char x[]);
- char* search2(struct node *ptr,char x[]);
- struct node * delete2(struct node*T,char id[]);
- int validname(char x[]);
- int validid(char x[]);
- void load();
- int main(){
- int choice;
- char a[10],id[10];
- // load();
- printf("enter choice(1 to insert , 2 delete by name 6 delete by id , 3 traverse ,4 search by name search 5 by id ):");
- scanf("%d",&choice);
- while(choice!=-1){
- switch (choice) {
- case 1:
- printf("enter name:");
- scanf("%s",a);
- while(!validname(a)){
- printf("INVALID ,enter name:");
- scanf("%s",a);
- }
- printf("enter id:");
- scanf("%s",id);
- while(!validid(id)){
- printf("INVALID ,enter id:");
- scanf("%s",id);
- }
- root=insert(root,a,id);
- root2=insert2(root2,a,id);
- break;
- case 2:
- printf("enter name to delete:");
- scanf("%s",a);
- while(!validname(a)){
- printf("INVALID ,enter name:");
- scanf("%s",a);
- }
- delete2(root2,search(root, a));
- delete(root,a);
- break;
- case 3:
- traverse(root);
- printf("tree 2\n");
- traverse(root2);
- break;
- case 4:
- printf("enter name to search:");
- scanf("%s",a);
- while(!validname(a)){
- printf("INVALID ,enter name:");
- scanf("%s",a);
- }
- search(root,a);
- break;
- case 5:
- printf("enter id to search:");
- scanf("%s",id);
- while(!validid(id)){
- printf("INVALID ,enter id:");
- scanf("%s",id);
- }
- search2(root2, id);
- break;
- case 6:
- printf("enter id to delete:");
- scanf("%s",id);
- while(!validid(id)){
- printf("INVALID ,enter id:");
- scanf("%s",id);
- }
- delete(root,search2(root2,id));
- delete2(root2, id);
- break;
- default:
- break;
- }
- printf("enter choice:");
- scanf("%d",&choice);
- }
- }
- struct node * insert(struct node *root, char x[],char id[])
- {int a;
- if(!root)
- {
- root=(struct node*)malloc(sizeof(struct node));
- free( root->data );
- free( root->id );// free previously allocated memory, if any
- root->data = strdup( x ); // malloc and copy
- root->id=strdup(id);
- root->left = NULL;
- root->right = NULL;
- // printf("1\n");
- return(root);
- }
- if((a=strcmp(root->data,x))>0){
- root->left = insert(root->left,x,id);
- }
- else
- {
- if(strcmp(root->data,x)<0)
- root->right = insert(root->right,x,id);
- }
- return(root);
- }
- struct node * insert2(struct node *root, char x[],char id[])
- {
- if(!root)
- {
- root=(struct node*)malloc(sizeof(struct node));
- free( root->data );
- free( root->id );// free previously allocated memory, if any
- root->data = strdup( x ); // malloc and copy
- root->id=strdup(id);
- root->left = NULL;
- root->right = NULL;
- // printf("1\n");
- return(root);
- }
- printf("string comp %d of %s of %s\n",strcmp(root->id,id),root->id,id);
- if((strcmp(root->id,id))>0){
- root->left = insert(root->left,x,id);
- printf("go left\n");
- }
- else
- {
- if(strcmp(root->id,id)<0){
- printf("go right\n");
- root->right = insert(root->right,x,id);}
- }
- return(root);
- }
- void traverse(struct node*ptr){
- if(ptr!=NULL){
- traverse(ptr->left);
- printf("%s %s\n",ptr->data,ptr->id);
- traverse(ptr->right);
- }
- }
- struct node * delete(struct node*T,char a[])
- {
- if(T==NULL) ; // element is not found in the tree
- else if(strcmp(a,T->data)<0)
- T->left = delete(T->left,a);
- else if(strcmp(a,T->data)>0)
- T->right = delete(T->right,a);
- else if((T->left)!=NULL && (T->right)!=NULL) { // node with 2 children
- temp = Findmin(T->right);
- T->data = temp->data;
- T->id= temp->id;
- T->right = delete(T->right,T->data); }
- else {
- temp = T;
- if(T->left==NULL)
- T = T->right;
- else if(T->right==NULL)
- T = T->left;
- // free(temp);
- }
- return T; }
- struct node * Findmin(struct node*ptr){
- if((ptr->left)==NULL){
- // printf("min is :%s",ptr->data);
- return ptr;
- }
- else
- return Findmin(ptr->left);
- }
- char * search(struct node *ptr,char x[])
- {
- while (ptr!=NULL) {
- if(strcmp(x,ptr->data)==0){
- printf("found data is :%s %s\n",ptr->data,ptr->id);
- return ptr->id;
- }
- else{
- if(strcmp(x,ptr->data)<0)
- ptr=ptr->left;
- else
- ptr=ptr->right;
- }
- }
- printf("not found\n");
- return NULL;
- }
- char* search2(struct node *ptr,char x[])
- {
- while (ptr!=NULL) {
- if(strcmp(x,ptr->id)==0){
- printf("found data is :%s %s\n",ptr->data,ptr->id);
- return ptr->data;
- }
- else{
- if(strcmp(x,ptr->id)<0)
- ptr=ptr->left;
- else
- ptr=ptr->right;
- }
- }
- printf("not found\n");
- return NULL;
- }
- struct node * delete2(struct node*T,char id[])
- {
- if(T==NULL) ; // element is not found in the tree
- else if(strcmp(id,T->id)<0)
- T->left = delete(T->left,id);
- else if(strcmp(id,T->id)>0)
- T->right = delete(T->right,id);
- else if((T->left)!=NULL && (T->right)!=NULL) { // node with 2 children
- temp = Findmin(T->right);
- T->data = temp->data;
- T->id= temp->id;
- T->right = delete(T->right,T->data); }
- else {
- temp = T;
- if(T->left==NULL)
- T = T->right;
- else if(T->right==NULL)
- T = T->left;
- // free(temp);
- }
- return T;
- }
- void load()
- {
- FILE * ptr;
- char data[10];
- char path[10];
- char id[10];
- printf("enter path of file:");
- scanf("%s",path);
- if((ptr=fopen("/Users/mahmoudelmarakshy/Documents/proj/Mah.txt","r"))==NULL)
- {
- printf("invalid file\n");
- }
- else
- {
- while(!feof(ptr))
- {
- fscanf(ptr,"%[^,],%s\n",data,id);
- root=insert(root,data,id);
- root2=insert2(root2,data,id);
- }
- printf("FILE FOUND\n");
- printf("FILE LOADED\n");
- }
- }
- int validname(char a[]){int c,flag=0;
- for(c=0; (a[c])!='\0'; c++)
- {
- if(isdigit(a[c]))
- flag=1;
- }
- if (flag==1)
- {
- return 0;
- }
- else
- return 1;
- }
- int validid(char a[]){int c,flag=0;
- for(c=0; (a[c])!='\0'; c++)
- {
- if(isalpha(a[c]))
- flag=1;
- }
- if (flag==1)
- {
- return 0;
- }
- else
- return 1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement