Underground - Bhasker V K,the Sandman's Hideout

	Create a New Forum Owner Login Contribute & Create Your Member account VoyUser Login (see contribute) VoyForums Directory/Categories No-ads: Completely remove ads from your forum VoyForums Homepage VoyForums News Help Desk VoyForums Exchange FAQ - Frequently Asked Questions Search VoyForums

[ VoyUser Login optional ] [ Contact Forum Admin ] [ Main index ] [ Post a new message ] [ Search | Check update time | Archives: 1 ]

Subject: Re: binary search Author: linked list [ Next Thread | Previous Thread | Next Message | Previous Message ] Date Posted: 18:35:01 09/21/05 Wed Author Host/IP: dsl-TN-024.246.247.61.touchtelindia.net/61.247.246.24 In reply to: b 's message, "Re: binary search" on 18:30:05 09/21/05 Wed #include #include #include #include /* **************************************************************** CODE WRITTEN BY NADIA MIJA, MARCH 27, 2003, BUCHAREST,ROMANIA **************************************************************** You can use this code for any purpuses except publication or selling. **************************************************************** 1) TNODE -- the list nodes type; - lkey -- list key = a value which is different for each node of the list; it can be useful for some applications it's recommendended to use it - name - a string information used only for example; here must be the real information of the list - next - the next node pointer; 2) void CreateList() -- creates a list; for any TNODE structure (general function) 3) void ViewAllList() -- shows the list items for any TNODE structure (general function); 4) void DeleteList() -- removes completely the entire list ; (general function) 5) TNODE* FindNode(int key) -- returns a pointer to a list-node which has the lkey-value equal-to key-parameter; (general function) 6) TNODE* InsertAfterKey(int key) -- inserts a new node (list item) after a list-node which has the lkey-value equal-to key-parameter; (general function) 7) TNODE* InsertAfterLast() -- inserts a new node (list item) after the last-node of the list ; (general function) 8) TNODE* InsertBeforeFirst() -- inserts a new node (list item) before the first-node of the list; (general function) 9) TNODE* InsertBeforeKey(int key) -- inserts a new node (list item) before a list-node which has the lkey-value equal-to key-parameter; (general function) 10) void RemoveByKey(int key) -- removes a list-node which has the lkey-value equal-to key-parameter; (general function) 11) void RemoveFirst() -- removes the first node of the list; (general function) 12) void RemoveLast() -- removes the last node of the list; (general function) I ALSO HAVE WRITTEN A FEW FUNCTIONS WHICH ARE DEPENDENT TO THE TNODE STRUCTURE; THEY NEED TO BE REWRITTEN FOR EVERY APPLICATION 1) void FreeNode(TNODE *p)//function specific to the application -- deallocates the memory for the p node 2) int LoadNode(TNODE *p) //function specific to the application -- loads the information into the nodes of the list but should always return these values 0 - Error 1 - ok; -1 - no more data to load In this case (meaning my function) you shuld reply - anything for yes - n/N for no 3) void PrintNode(TNODE *p) //function specific to the application -- shows the information of the p node PLEASE ALSO READ THE COMMENTS IN THE CODE FOR MORE INFORMATION **************************************************************** */ typedef struct node { int lkey; //key node char name[10]; //specific to the application; node's information struct node* next; } TNODE; TNODE *first, *last; //pointers to the first and last element of the linked list int LoadNode(TNODE *p); void FreeNode(TNODE *p); void PrintNode(TNODE *p); void CreateList() //this function can be used no matter what the structure TNODE looks like { // meaning it can be used for any type of applications concerning lists TNODE *p; //general function int n=sizeof(TNODE); first=last=0; //empty list for(;;) { if( (p=(TNODE*)malloc(n))==0 ) //allocation could not be made { printf("\nNot enough memory"); break; } if(LoadNode(p)!=1) { FreeNode(p); break; } p->next=0; if (first==0) //this list was empty since now first=last=p; else { last->next=p; last=p; } } } int LoadNode(TNODE *p) //function specific to the application { //but should always return these values /* 0 - Error 1 - ok; -1 - no more data to load */ char opt; printf("\nNew node?"); opt=getche(); opt=toupper(opt); if(opt!='N') { puts("\nPlease insert data for the current node:"); printf("\nlkey:\t"); if (scanf("%d",&(p->lkey))!=1) return 0; //could not read lkey value for current node printf("\nname:\t");if (scanf("%s",p->name)!=1) return 0; return 1; } else return -1; } void FreeNode(TNODE *p)//function specific to the application { free(p); } void ViewAllList()//general function { TNODE *p; p=first; while(p) { PrintNode(p); p=p->next; } } TNODE* FindNode(int key) //general function //serches and returns the node having the lkey value equal to the key parameter { TNODE *p; p=first; while(p) { if(p->lkey == key) return p; p=p->next; } return 0; //value not found } void PrintNode(TNODE *p) //function specific to the application { if(p) printf("\n%d\t%s",p->lkey,p->name); } TNODE* InsertBeforeFirst() //general function //returns the node inserted //or 0 for failed insertion { TNODE *p; int n=sizeof(TNODE); if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded { if (first==0) //list was empty { p->next=0; first=last=p; } else { p->next=first; first=p; } return p; } if(p==0) //not enough memory printf("\nNot enough memory"); else //the node could not be loaded FreeNode(p); return 0; //there is no node inserted before first -- insertion failed } TNODE* InsertBeforeKey(int key) //general function //returns the node inserted //or 0 for failed insertion { TNODE *p, *q, *q1; //p=the new node to insert //q=key //q1=the node before key int n=sizeof(TNODE); //find q, q1 q1=0; q=first; while(q) { if(q->lkey == key) break; //key node found q1=q; //keep on searching for key node q=q->next; } if(q==0) { printf("\nThere is no node having such a key or the list is empty");//this case also includes the case of empty list return 0;//there is no node having such a key -- insertion can't be made } //now the key was found -- so we try to make the insertion if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded { if(q==first) //we have to insert before the first node { p->next=first; first=p; } else //the key node is not the first one { p->next=q; q1->next=p; } return p; } if(p==0) //not enough memory printf("\nNot enough memory"); else //the node could not be loaded FreeNode(p); return 0; //there is no node inserted before key -- insertion failed } TNODE* InsertAfterKey(int key) //general function //returns the node inserted //or 0 for failed insertion { TNODE *p, *q; //p=the new node to insert //q=key int n=sizeof(TNODE); //find q q=first; while(q) { if(q->lkey == key) break; //key node found q=q->next; //keep on searching for key node } if(q==0) { printf("\nThere is no node having such a key or the list is empty");//this case also includes the case of empty list return 0;//there is no node having such a key -- insertion can't be made } //now the key was found -- so we try to make the insertion if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded { if(q==last) //we have to insert after the last node { p->next=0; last->next=p; last=p; } else //the key node is not the last one { p->next=q->next; q->next=p; } return p; } if(p==0) //not enough memory printf("\nNot enough memory"); else //the node could not be loaded FreeNode(p); return 0; //there is no node inserted after key -- insertion failed } TNODE* InsertAfterLast() //general function //returns the node inserted //or 0 for failed insertion { TNODE *p; int n=sizeof(TNODE); if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded { p->next=0; if (first==0) //list was empty first=last=p; else { last->next=p; last=p; } return p; } if(p==0) //not enough memory printf("\nNot enough memory"); else //the node could not be loaded FreeNode(p); return 0; //there is no node inserted after last -- insertion failed } void RemoveFirst() //general function //removes the first node of the list; pre and post-conditions: none { TNODE *p; if(first==0)//list was empty return; if(first==last)//there is just one node { FreeNode(first); first=last=0; return; } p=first; first=first->next; FreeNode(p); } void RemoveLast() //general function //removes the last node of the list; pre and post-conditions: none { TNODE *p, *q; if(first==0)//list was empty return; if(first==last)//there is just one node { FreeNode(first); first=last=0; return; } q=0;//there are at least 2 nodes p=first; while(p!=last) { q=p; p=p->next; }//so we have q=the node before the last one p=last;//now we're going to remove the last node FreeNode(p); q->next=0; last=q; } void RemoveByKey(int key) { TNODE *p, *q; //p - the key node //q=the node before the key node if(first==0)//list was empty return; q=0;//there are at least 2 nodes p=first; while(p) { if(p->lkey == key) break; //key node found q=p; p=p->next; }//so we have q=the node before the key one; p=key node if(!p)//There is no node having such a key { printf("\nThere is no node having such a key"); return; } if(first==last)//there is just one node which is the key node { FreeNode(first); first=last=0; return; } if(p==first) //first is the key node { first=first->next; FreeNode(p); return; } if(p==last) // last was the key node { q->next=0; last=q; FreeNode(p); return; } q->next=p->next; FreeNode(p); } void DeleteList() { TNODE *p; p=first; while(p) { first=first->next; FreeNode(p); p=first; } last=0; } void main() { CreateList();//this is an example of using these fonctions ViewAllList(); InsertAfterLast(); ViewAllList(); RemoveFirst(); ViewAllList(); InsertAfterKey(1);//by example ViewAllList(); RemoveByKey(1); ViewAllList(); DeleteList(); ViewAllList(); } [ Next Thread | Previous Thread | Next Message | Previous Message ]

Replies:

[> [> [> Subject: Re: binary search Author: binar search tree implementation [Edit] Date Posted: 18:37:06 09/21/05 Wed Author Host/IP: dsl-TN-024.246.247.61.touchtelindia.net/61.247.246.24 //Binary search tree implementation by Niranjan Yadla #include #include struct node { int data; struct node *left; struct node *right; }; void binsearchtree(struct node **,int); void delatgivendata(struct node **,int); inorder(struct node *); preorder(struct node *); postorder(struct node *); void main() { int data,choice; struct node *p; p=NULL; clrscr(); while(1) { printf("\n1.Add node to the binary search tree"); printf("\n2.Deletion at given data:"); printf("\n3.Exit"); printf("\nEnter the choice"); scanf("%d",&choice); switch(choice) { case 1: printf("\nEnter the data"); scanf("\n%d",&data); binsearchtree(&p,data); printf("\n The inorder traversals are:"); printf("\n"); inorder(p); printf("\n The preorder traversals are:"); printf("\n"); preorder(p); printf("\nThe post order traversals are:"); printf("\n"); postorder(p); break; case 2: printf("\n Please enter the data where you want deleted"); scanf("%d",&data); delatgivendata(&p); printf("\nThe inorder traversals are :"); inorder(p); break; case 3:exit(0); } } } void binsearchtree(struct node **q,int data) { struct node *temp,*r; r=*q; temp=(struct node*)malloc(sizeof(struct node)); temp->data=data; temp->left=NULL; temp->right=NULL; if(r==NULL) { *q=temp; (*q)->left=temp->left; (*q)->right=temp->right; } else { if(r->data==data) printf("\nInvalid input\n"); while(1) { if(r->data>data) { if(r->left==NULL) { r->left=temp; break; } r=r->left; } else { if(r->right==NULL) { r->right=temp; break; } r=r->right; } } } } void delatgivendata(struct node **q,int data) { struct node *r; r=*q; } inorder(struct node *q) { struct node *r; r=q; if(r==NULL) return 0; else { inorder(r->left); printf("%d\t",r->data); inorder(r->right); } } preorder(struct node *q) { struct node *r; r=q; if(r==NULL) return 0; else { printf("%d\t",r->data); preorder(r->left); preorder(r->right); } } postorder(struct node *q) { struct node *r; r=q; if(r==NULL) return 0; else { postorder(r->left); postorder(r->right); printf("%d\t",r->data); } } [ Post a Reply to This Message ]