| 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
] |
|
Feedback: 