Sign in to follow this  
Nokturnal

Linked List's (Queue) - BFS

Recommended Posts

Hi, I am trying to implement a BFS search using linked lists. Well , i am not sure as to how to go about it, so far i have made a linked list, a function which adds more nodes to the existing list (more nodes will be added as the depth increase ). what i have planned is to have a pointer to a particular node , when a operator is applied to it , it would push the resulting nodes at the back of the queue for further evaluation (provided none of them are goal nodes).Make the node point to the next one in the queue, rinse repeat. I could let the queue stay as it is , but what i would really love to do , would be to delete the node which has been examined/expanded. From the structure i have chosen , i cant seem to figure out a way to free the memory used. Any suggestions regarding alternate approaches are welcome. Thanks.

#include <iostream>

using namespace std;


struct data
{
	int number;
	struct data * next;
};


void display(struct data * headref);
struct data * CreateList(struct data * headref,int start,int end);
struct data *  KillFirst(struct data *headref,int number);

void main()
{
struct data *head=NULL;
head=CreateList(head,1,10);
//display(head);
CreateList(head,11,20);
display(head);
cout<<endl;
head=KillFirst(head,2);
display(head);
}


struct data *  KillFirst(struct data *headref,int no)
{
struct data *retnode;
struct data *tempnode;
retnode=headref;

	for(int i=0;i<no;i++)
	retnode=retnode->next;
/*
	for(i=0;i<no;i++)
	{
	tempnode=headref->next;
	headref=headref->next;
	delete headref;
	}
*/
	return retnode;
}



void display(struct data * headref)
{
	while(headref!=NULL)
	{
		cout<<"Data in node is "<<headref->number<<endl;
		headref=headref->next;
	}
}

struct data * CreateList(struct data * headref,int start,int end)
{
	
	if(headref==NULL)
	{
	headref=new struct data();
	struct data * node = new struct data();
	
	node->number=start;
	node->next=NULL;
	headref=node;

		for(int i=start+1;i<=end;i++)
		{
		struct data * temp = headref;
		struct data * node = new struct data();
	
		node->number=i;
		node->next=NULL;
		
		while(temp->next!=NULL)
		temp=temp->next;
		
		temp->next=node;

		}
	}//close if
	else
	{
		for(int i=start;i<=end;i++)
		{
		struct data * temp = headref;
		struct data * node = new struct data();
	
		node->number=i;
		node->next=NULL;
		
		while(temp->next!=NULL)
		temp=temp->next;
		
		temp->next=node;

		}
	}
	return headref;
}


Share this post


Link to post
Share on other sites
If you're using C++, then you should probably just go with std::list or a std::queue and not worry about explicitly freeing the memory .

Share this post


Link to post
Share on other sites
Yup , i am using c++. I am quite bad at pointers-related-tasks, so i thought this would be a good way to mess around some of them. I will definitely check out the ones you mentioned. :)

Share this post


Link to post
Share on other sites
I may be misunderstanding what your saying but how can you do a breath first search (I'm assuming thats what you mean by BFS) on a linked list, that would just be search through each element from the beginning to the end.

In general BFS is used with trees.

Share this post


Link to post
Share on other sites
With linear linked lists you start from the head, and search all the way down until you reach the element with data->next being NULL.
At that point you've searched the entire list.

To deallocate the head you simply;
take the data->next value, save it in a buffer
deallocate the head
reassign the head the buffer

To deallocate inbetween;
take the previous value, save it in a buffer
take the data->next value, save it in a buffer
deallocate the current node
reassign the previous value to the next value

To deallocate at the end;
take the previous data->next, set to NULL
deallocate the current node

If you use STL (standard template library) you can do things like this without really needing to manage the data structures. I know nothing about BFS though.

Share this post


Link to post
Share on other sites
Thanks EmperiorRune ,just did that and added a nifty path variable to it , here's the finished product :p
(assuming i start with 5 , goal = 0 , by reducing either 1 or 2 only )



#include <iostream>

using namespace std;


struct data
{
int number;
int path;
struct data * next;
};


void display(struct data * headref);
struct data * CreateList(struct data * headref,int start,int end);
struct data * KillFirst(struct data *headref,int number);
struct data * ApplyOperator(struct data * headref);

void main()
{
struct data *head=NULL;
head=new struct data();
head->number=5;
head->path=0;
head->next=NULL;

//apply operator - check for goal, no , apply

while(head->number!=0)
{
cout<<"inside while headnumber"<<head->number<<endl;
head=ApplyOperator(head);
display(head);
cout<<endl<<endl;
}

cout<<"The path cost is "<<head->path<<endl;
//display(head);
cout<<endl;
}



struct data * LinkList(struct data * headref,struct data * tailref)
{
struct data * tempnode=headref;

while(headref->next!=NULL)
headref=headref->next;

headref->next=tailref;

return tempnode;
}


struct data * ApplyOperator(struct data * headref)
{
struct data * node_1=new struct data();
struct data * node_2=new struct data();

node_1->number=headref->number-1;
node_2->number=headref->number-2;

node_1->path=headref->path+1;
node_2->path=headref->path+1;

node_1->next=NULL;
node_2->next=NULL;

if(node_1->number >= 0)
LinkList(headref,node_1);
if(node_2->number >= 0)
LinkList(headref,node_2);

headref=KillFirst(headref,1);
return headref;
}

struct data * KillFirst(struct data *headref,int no)
{
struct data *retnode;
struct data *tempnode;
retnode=headref;


for(int i=0;i<no;i++)
retnode=retnode->next;

for(i=0;i<no;i++)
{
tempnode=headref;
headref=headref->next;
delete tempnode;
}
return retnode;
}



void display(struct data * headref)
{
while(headref!=NULL)
{
cout<<"Data in node is "<<headref->number<<endl;
headref=headref->next;
}
}

struct data * CreateList(struct data * headref,int start,int end)
{

if(headref==NULL)
{
headref=new struct data();
struct data * node = new struct data();

node->number=start;
node->next=NULL;
headref=node;

for(int i=start+1;i<=end;i++)
{
struct data * temp = headref;
struct data * node = new struct data();

node->number=i;
node->next=NULL;

while(temp->next!=NULL)
temp=temp->next;

temp->next=node;

}
}
else
{
for(int i=start;i<=end;i++)
{
struct data * temp = headref;
struct data * node = new struct data();

node->number=i;
node->next=NULL;

while(temp->next!=NULL)
temp=temp->next;

temp->next=node;

}
}
return headref;
}


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this