#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
