level order traversal and a que issues

G

GrispernMix

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <iostream>
#include <string.h>
using namespace std;

#define TRUE 1
#define FALSE 0

struct info_node
{
char code[8] ;
int weight ;
int level ;
struct info_node* father ;
struct info_node* left ;
struct info_node* right ;
struct info_node* next ;

} ;

struct prqueue
{
struct info_node * prqtop ;
} ;

struct lo_queue
{
struct info_node* front ;
struct info_node* rear ;
} ;

void create(struct prqueue* pq);
int empty(struct prqueue* pq);
void insert(struct prqueue* pq, struct info_node* new_node);
struct info_node* remove(struct prqueue* pq);
int oneleft(prqueue* pque);
void visit(info_node* node);
void qInsert( lo_queue* pdq, info_node* node);
int qEmpty(lo_queue* pdq);
void qCreate(struct lo_queue* pdq);
struct info_node* remove(struct prqueue* pq);
void levelOrderTraversal(lo_queue* pdq,info_node* root, int level);
void levelorder(lo_queue* pdq,info_node* root);
void main(void)
{
FILE* infile;
struct prqueue pque ;
struct lo_queue que ;
struct prqueue* pmain_queue ;
struct info_node* pleaf_location[7] ;
struct info_node* tree_root ;
struct info_node* new_node;
struct info_node* move;
struct info_node* test;
int count=0,level=0;
int numAllow = 2*level;

create(&pque);
qCreate(&que);
new_node = NULL;
test = NULL;
infile = fopen("c:/prq_data.txt", "r");
struct info_node* p1 ; // can be used in the loop which
removes 2
nodes from
struct info_node* p2 ; // your priority queue
new_node = ( struct info_node* ) malloc( sizeof ( struct
info_node )
);
test = ( struct info_node* ) malloc( sizeof ( struct info_node
) );
//fscanf(infile,"%s %d ",new_node->code,&new_node->weight);
while(!feof(infile))
{
new_node = ( struct info_node* ) malloc( sizeof (
struct info_node )
);
fscanf(infile,"%s%d
",new_node->code,&new_node->weight);
pleaf_location[count++] = new_node;
insert(&pque,new_node);
}
move = pque.prqtop;
// remove 2
while(!oneleft(&pque))
{
new_node = ( struct info_node* ) malloc( sizeof (
struct info_node )
);// create new node
p1 = ( struct info_node* ) malloc( sizeof ( struct
info_node ) ); //
create node holder 1
p2 = ( struct info_node* ) malloc( sizeof ( struct
info_node ) );//
create node holder 2
p1 = remove(&pque);// remove first node out of pque
p2 = remove(&pque); // remove second node out of pque
strcpy(new_node->code, p1->code);// copy
new_node->code, from the
first node
strcat(new_node->code, p2->code); // copy
new_node->code, from the
second node
cout << "newNode Code" << new_node->code << endl;
new_node->weight = p1->weight + p2->weight;// add the weight
together
new_node->father = new_node; // initialize the father
cout << "left p1->code = " << p1->code << endl;
cout << "right p2->code = " << p2->code << endl;
new_node->left = p1;// itialize the left
new_node->right = p2; //intialize the right
insert(&pque,new_node);//insert it into the que
}

// the last node will be the root
move = pque.prqtop;
tree_root = remove(&pque);
//tree_root = remove(&pque);
//visit(tree_root);
levelorder(&que, tree_root);

printf("End of program: ");
getch();

} // end of function main()

void create(struct prqueue* pq)
{
pq->prqtop = NULL;
}

void qCreate(lo_queue *pdq)
{
pdq->front = NULL;
pdq->rear = NULL;
}

int empty(struct prqueue* pq)
{
if(pq->prqtop == NULL)
{
return(1);
}
else
{
return(0);
}
}

void insert(struct prqueue* pq, struct info_node* new_node)
{
struct info_node* move;
struct info_node* pre_pntr;

move = pq->prqtop;
pre_pntr = pq->prqtop;
if(empty(pq))//check for empty
{
new_node->next = NULL;
pq->prqtop = new_node;
}
else
{
while(move != NULL && new_node->weight > move->weight)
{
pre_pntr = move;
move = move->next;
}
if(move == pq->prqtop)
{
new_node->next = move;
pq->prqtop = new_node;
}
else if(move == NULL)
{
new_node->next = NULL;
pre_pntr->next = new_node;
}
else
{
new_node->next = move;
pre_pntr->next = new_node;
}
}
}

struct info_node* remove(struct prqueue* pq)
{
struct info_node* remove;
remove = NULL;
if(empty(pq))
{
printf("ERROR EMPTY!!!");
}
else if(pq->prqtop->next == NULL)
{
remove = pq->prqtop;
pq->prqtop = NULL;
}
else
{
remove = pq->prqtop;
pq->prqtop = pq->prqtop->next;
}
return(remove);
//printf("%s %d\n",remove->code,remove->weight);
}

int oneleft(prqueue *pque)
{
info_node* node;
node = remove(pque);
if(empty(pque))
{
insert(pque,node);
return(1);
}
else
{
insert(pque,node);
return(0);
}
}

void visit(info_node* node)
{
if(node != NULL)
printf("%s\n", node->code) ;
}// end of function visit()

info_node* qRemove(lo_queue* pdq)
{
info_node* auxinfo;
if(qEmpty(pdq))
{
cout << "priority que empty" << endl;
}
else if(pdq->front->next == NULL)
{
auxinfo = pdq->front;
pdq->front = NULL;
pdq->rear = NULL;
}
else
{
auxinfo = pdq->front;
pdq->front = pdq->front->next;
}
return(auxinfo);

}

void qInsert(lo_queue* pdq, info_node* node )
{
if(qEmpty(pdq))
{
pdq->front = node;
pdq->rear = node;
}
else
{
pdq->rear->next = node;
pdq->rear = node;
}
}

int qEmpty(lo_queue* pdq)
{
if(pdq->front == NULL && pdq->rear == NULL)
{
return(1);
}
else
{
return(0);
}
}

void levelorder(lo_queue* pdq,info_node* root)
{

int testCounter = 0;
if(root == NULL)
cout << " ";

else{

cout << " ";

// Insert the first node

qInsert(pdq,root);

// The level we're at in the tree

int level = 0;
//cout << "level" << level << endl;

// The number of items we can take out (Binary Tree = 2 *
level)

int numAllow = 2 * level;

while(!qEmpty(pdq)){
while(numAllow < 2*level)
{
info_node* temp = qRemove(pdq);
cout << temp->code << " ";

if(temp->left != NULL)
{

qInsert(pdq, temp->left);
} // end if()

if(temp->right != NULL)
{
qInsert(pdq, temp->right);
} // end if()

// We've output one of our allowed
elements

numAllow++;
//cout << "numallow = " << numAllow << endl;

} // end while()
//cout << "loop" << endl;
cout << "\n ";
level++;

} // while()

cout << " ";

} // end else()
} // end breadthFirstString()

//my problem is with my level order function which keeps giving me this
error Unhandled exception //at 0x00402008 in meteor.exe: 0xC0000005:
Access violation writing location 0xbaadf029. I dont //see where i am
stepping out of my boundry, the input file is
//A 8
//B 1
//C 3
//D 5
//E 12
//F 4
//G 2
//any help would be great
 
?

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <iostream>
#include <string.h>
using namespace std;

#define TRUE 1
#define FALSE 0
Click to expand...
[....]

First of all, this does not look like C++ to me, it looks like C with a
few usages of C++-features. If it was C++ you should include <string>
and not <string.h> (which you includes twice) and use bool instead of
defining TRUE and FALSE, and even in C there is <stdbool.h> which you
could use.

Now, it seems like you are having trouble with a queue, and unless you
have a very pressing need to make one yourself (in which case I can't
help you) I would recomend to take a look at std::queue (you get it by
including <queue>).

If you must use your implementation all the help I can give you is
saying that your problem most likely comes from a stray pointer you are
trying to use, running your app in a debuger might give you some help.
 
D

David Harmon

On 2 Dec 2006 10:49:30 -0800 in comp.lang.c++ said:
//any help would be great
Click to expand...

Dude, sorry, but your code sucks.
Maybe I'll have more time later, but for now, numallow++ is wrong.
Reenable cout << numallow.
And initialize ALL your variables, uninitialized variables are death.
 
S

Salt_Peter

GrispernMix said:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <iostream>
#include <string.h>
using namespace std;

#define TRUE 1
#define FALSE 0
Click to expand...

<snip>

I'll second that - the code sucks. This is the perfect example on how
not to code.
If you fail to initialize pointers (a coder's ultimate nemesis) be
prepared to suffer the consequences.
Just in case you didn't get it -> initialize ALL your variables. And by
ALL we mean every single one.
hint -> use ctors + init list.
Prefer references over pointers.
pointer == bugs. Uninitialized pointers is a disease.
void main() is illegal (even in C).
 
D

David Harmon

On Sat said:
Maybe I'll have more time later,
Click to expand...

OK, now is later. You still here?
Here is a chopped and reformed version of your code.
There are plenty of things I don't like about it, but I think the
changes I made should bust the debugging roadblock you hit.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <iostream>
#include <string.h>
using namespace std;

#include <assert.h>

#define TRUE 1
#define FALSE 0

struct info_node
{
char code[8];
int weight;
int level;
info_node * father;
info_node * left;
info_node * right;
info_node * next;
};

info_node *malloc_node()
{
info_node * new_node = (info_node *)malloc(sizeof(info_node));
memset(new_node, 0, sizeof(info_node));
return new_node;
}


struct prqueue
{
info_node * prqtop;
};

struct lo_queue
{
info_node * front;
info_node * rear;
};

/* Please remove unnecessary forward declarations.
void create(prqueue * pq);
int empty(prqueue * pq);
void insert(prqueue * pq, info_node * new_node);
info_node * remove(prqueue * pq);
int oneleft(prqueue * pque);
void visit(info_node * node);
void qInsert( lo_queue * pdq, info_node * node);
int qEmpty(lo_queue * pdq);
void qCreate(lo_queue * pdq);
info_node * remove(prqueue * pq);
void levelOrderTraversal(lo_queue * pdq, info_node * root, int level);
void levelorder(lo_queue * pdq, info_node * root);
*/


void create(prqueue * pq)
{
assert(pq);
pq->prqtop = NULL;
}

void qCreate(lo_queue * pdq)
{
assert(pdq);
pdq->front = NULL;
pdq->rear = NULL;
}

int empty(prqueue * pq)
{
assert(pq);
if (pq->prqtop == NULL) {
return 1;
} else {
return 0;
}
}

void insert(prqueue * pq, info_node * new_node)
{
assert(new_node);
assert(pq);
info_node * move = pq->prqtop;
info_node * pre_pntr = pq->prqtop;

if (empty(pq)) { //check for empty
new_node->next = NULL;
pq->prqtop = new_node;
} else {
while (move != NULL && new_node->weight > move->weight) {
pre_pntr = move;
move = move->next;
}
if (move == pq->prqtop) {
new_node->next = move;
pq->prqtop = new_node;
} else if (move == NULL) {
new_node->next = NULL;
pre_pntr->next = new_node;
} else {
new_node->next = move;
pre_pntr->next = new_node;
}
}
}

info_node * remove(prqueue * pq)
{
info_node * remove = NULL;
assert(pq);

if (empty(pq)) {
printf("ERROR EMPTY!!!");
} else if (pq->prqtop->next == NULL) {
remove = pq->prqtop;
pq->prqtop = NULL;
} else {
remove = pq->prqtop;
pq->prqtop = pq->prqtop->next;
}
assert(remove);
return remove;
//printf("%s %d\n",remove->code,remove->weight);
}

int oneleft(prqueue * pque)
{
assert(pque);
info_node * node = remove(pque);
if (empty(pque)) {
insert(pque, node);
cout << "one left!" << endl;
return 1;
} else {
insert(pque, node);
return 0;
}
}

void visit(info_node * node)
{
if (node != NULL)
printf("Visit %s\n", node->code);
} // end of function visit()


int qEmpty(lo_queue * pdq)
{
assert(pdq);
if (pdq->front == NULL && pdq->rear == NULL) {
return 1;
} else {
return 0;
}
}


info_node * qRemove(lo_queue * pdq)
{
info_node * auxinfo = 0;
assert(pdq);
if (qEmpty(pdq)) {
cout << "priority que empty" << endl;
} else if (pdq->front->next == NULL) {
auxinfo = pdq->front;
pdq->front = NULL;
pdq->rear = NULL;
} else {
auxinfo = pdq->front;
pdq->front = pdq->front->next;
}
return auxinfo;
}

void qInsert(lo_queue * pdq, info_node * node )
{
assert(pdq);
assert(node);
if (qEmpty(pdq)) {
pdq->front = node;
pdq->rear = node;
} else {
pdq->rear->next = node;
pdq->rear = node;
}
}

void levelorder(lo_queue * pdq, info_node * root)
{
int testCounter = 0;
if (root == NULL) {
cout << "NULL\n";
return;
}

cout << " ";

// Insert the first node

assert(pdq);
qInsert(pdq, root);

// The level we're at in the tree

int level = 0;

// The number of items we can take out (Binary Tree = 2 * level)

int numAllow = 2 * level;

while (!qEmpty(pdq)) {
cout << "level " << level << endl;

while (!qEmpty(pdq) && numAllow < 2*level) {

info_node * temp = qRemove(pdq);
cout << "(" << temp->code << ") ";

if (temp->left != NULL) {
cout << " L(" << temp->left->code << ") ";
qInsert(pdq, temp->left);
} // end if()
if (temp->right != NULL) {
cout << "R(" << temp->right->code << ") ";
qInsert(pdq, temp->right);
} // end if()
memset(temp, 0, sizeof(info_node)); // <<<=== Lookee here!

// We've output one of our allowed elements
numAllow++;
cout << "numallow = " << numAllow << endl;
} // end while()
cout << "\n ";
level++;
}
cout << " ";
}


int main()
{
FILE * infile;
prqueue pque = { 0 };
lo_queue que = { 0 };
//info_node * pleaf_location[7] = { 0 };
int count = 0, level = 0;
int numAllow = 2*level;

create(&pque);
qCreate(&que);

infile = fopen("prq_data.txt", "r");
if (!infile)
perror("prq_data.txt");

//fscanf(infile,"%s %d ",new_node->code,&new_node->weight);
while (!feof(infile)) {
info_node * new_node = malloc_node();
int res = fscanf(infile, "%s%d", new_node->code, &new_node->
weight);
if (res != 2)
perror("infile");

//pleaf_location[count++] = new_node;
insert(&pque, new_node);
}

// remove 2

while (!oneleft(&pque)) {
info_node * p1 = remove(&pque); // remove first node out of pque
info_node * p2 = remove(&pque); // remove second node out of pque
info_node * new_node = malloc_node(); // create new node
strcpy(new_node->code, p1->code); // copy new_node->code, from the first node
strcat(new_node->code, p2->code); // copy new_node->code, from the second node
cout << "newNode Code" << new_node->code << endl;
new_node->weight = p1->weight + p2->weight; // add the weight together
new_node->father = new_node; // initialize the father
cout << "left p1->code = " << p1->code << endl;
cout << "right p2->code = " << p2->code << endl;
new_node->left = p1; // itialize the left
new_node->right = p2; //intialize the right
insert(&pque, new_node); //insert it into the que
}

// the last node will be the root
info_node * tree_root = remove(&pque);
//tree_root = remove(&pque);
//visit(tree_root);
levelorder(&que, tree_root);

printf("End of program: ");
getch();
} // end of function main()
 
G

GrispernMix

OK, now is later. You still here?
Here is a chopped and reformed version of your code.
Click to expand...

Ya I am still here, I really appreciate the effort, first i have been
using void main(void) in order to get the program to run and stop
while debugging, You say its illegal, yet it is accepting it, though i
have come to realize that it accepts alot of things that are even close
to being right, which definetly puts me into a quandry as i am a
student. And anything else you dont like about my code, please tell me
and don't hold back. Well in the mean time, there are alot of stuff in
your code that i dont know so i am going to go over it, thanks again.
 
G

GrispernMix

memset(temp, 0, sizeof(info_node)); // <<<=== Lookee here!
why do you need memset here?
int res = fscanf(infile, "%s%d", new_node->code, &new_node->
weight);
if (res != 2)
perror("infile");
Click to expand...
why would res = 2?
 
D

David Harmon

On 3 Dec 2006 09:18:18 -0800 in comp.lang.c++, "GrispernMix"
why do you need memset here?
Click to expand...

It is a cheap hack, a bad example, and I shouldn't have done it.
It is just a way of setting the whole thing to zeros, but the real way
is of course assigning all of the members = 0.

If I understand the code, that node temp-> should be removed from the
list and no longer used (should be deallocated with free(), but you
never free() anything). But it IS still affecting the program somehow,
and setting all of its pointers to zero is avoiding the crash that was
troubling you. I only hope that with that improvement, you could figure
out where the real bug lies.

Please change that line to:
temp->father = temp->left = temp->right = temp->next = 0;
strcpy(temp->code, "Boo!");
why would res = 2?
Click to expand...

The result of fscanf() is the number of data items read. If it is not
the number expected, it usually means a problem. So I stuck that error
check in while I had no idea what was going wrong, just to eliminate
that possibility. The lack of error checking while reading input is one
example of "things I did not like." It may seem unnecessary in a
program that is all about other things, but the simplest typo error can
cause fscanf() to fail, your program to get wrong input without you
knowing it, and your sanity to evaporate.

Lastly, the return type from main() should always be int. It is the
only return type that has ever been allowed in standard C or C++.
void main() is warning sign for book authors or teachers who are not
paying attention or who don't care much about correctness.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

ques and and level order traversal 6
Infinite loop problem 1
level order traversal of binary tree 4
I dont know how to modify this. Can someone help. 0
stuck in Infinite-loop 24
GET NEIL DEGRASSES TYSON, I ripped a hole with this one... 0
Queue in C 25
Lexical Analysis on C++ 1

Members online

Total: 68 (members: 4, guests: 64)
Robots: 479

Forum statistics

Threads
473,995
Messages
2,570,226
Members
46,815
Latest member
treekmostly22

Latest Threads

Top