#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;
}
Linked List's (Queue) - BFS
Author
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.
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 .
Author
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. :)
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.
In general BFS is used with trees.
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.
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.
Author
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 )
(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 , applywhile(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;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
