level order traversal and a que issues

Discussion in 'C++' started by GrispernMix, Dec 2, 2006.

  1. GrispernMix

    GrispernMix Guest

    #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
     
    GrispernMix, Dec 2, 2006
    #1
    1. Advertising

  2. On 2006-12-02 19:49, GrispernMix wrote:
    > #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
    >

    [....]

    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.

    --
    Erik Wikström
     
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Dec 2, 2006
    #2
    1. Advertising

  3. GrispernMix

    David Harmon Guest

    On 2 Dec 2006 10:49:30 -0800 in comp.lang.c++, "GrispernMix" <> wrote,
    >//any help would be great


    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.
     
    David Harmon, Dec 2, 2006
    #3
  4. GrispernMix

    Salt_Peter Guest

    GrispernMix wrote:
    > #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
    >


    <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).
     
    Salt_Peter, Dec 3, 2006
    #4
  5. GrispernMix

    David Harmon Guest

    On Sat, 02 Dec 2006 21:11:49 GMT in comp.lang.c++, David Harmon <> wrote,
    >Maybe I'll have more time later,


    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()
     
    David Harmon, Dec 3, 2006
    #5
  6. GrispernMix

    GrispernMix Guest

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


    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.
     
    GrispernMix, Dec 3, 2006
    #6
  7. GrispernMix

    GrispernMix Guest

    > 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");
    >

    why would res = 2?
     
    GrispernMix, Dec 3, 2006
    #7
  8. GrispernMix

    David Harmon Guest

    On 3 Dec 2006 09:18:18 -0800 in comp.lang.c++, "GrispernMix"
    <> wrote,
    >> memset(temp, 0, sizeof(info_node)); // <<<=== Lookee here!

    >why do you need memset here?


    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!");

    >> int res = fscanf(infile, "%s%d", new_node->code, &new_node->
    >> weight);
    >> if (res != 2)
    >> perror("infile");
    >>

    >why would res = 2?


    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.
     
    David Harmon, Dec 3, 2006
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Wynan James
    Replies:
    1
    Views:
    1,595
    Miguel De Anda
    Oct 6, 2003
  2. pabbu
    Replies:
    8
    Views:
    768
    Marc Boyer
    Nov 7, 2005
  3. GrispernMix

    ques and and level order traversal

    GrispernMix, Dec 2, 2006, in forum: C Programming
    Replies:
    6
    Views:
    482
    GrispernMix
    Dec 3, 2006
  4. Christian Rühl
    Replies:
    22
    Views:
    1,754
    Christian Rühl
    Dec 13, 2007
  5. Replies:
    4
    Views:
    9,443
    Kaz Kylheku
    Feb 15, 2008
Loading...

Share This Page