Solved

Dealing with malloc'd structs

Posted on 2003-12-06
11
526 Views
Last Modified: 2010-04-15
Hi guys, I am trying to code a game that tries to guess what object/animal/thing the user is thinking, i am using structs for the nodes in the tree.

Each struct has
a node number,
a nodetype,
a char array for an object & question - which can be empty,
a YES_ptr to another struct  - which can be empty,
a NO_ptr to another struct  - which can be empty,

When the game starts it checks whether the current node is an object or a question.
If it is an object it asks if the user was thinking of that object.
It it is a question, it asks that question, then according to the users response follows the appropriate pointer.

A restrictions
Please only use y and n for the answers, anything else wont work with the program at the moment.

My question is how to refer to the malloc'd nodes once they have been created.

E.g
When the program is first run it asks if you are thinking of a DOG?
If you say: n , And enter: e.g. a horse
it then asks for a question to distinguish between a horse and a dog
enter e.g. Does it gallop?
then it asks what is the answer for horse
enter y or n, it then sets the YES_ptr and NO_ptr for that question node appropriately.

This works fine for the first object you add.
Lets say now we are thinking of a lion
When you run it again it asks the previous question "Does it gallop?"
enter: n
it will ask if you are thinking of a DOG which is fine.
enter: n
It then asks what you were thinking
enter: lion
it then asks for a qeuestion to distinguish
e.g. enter : Does it have a main?
it then asks, what is the answer for a lion
if we enter: y (yes) it then sets the YES_ptr for that question to be lion, and it sets the NO_ptr to be Dog
but here i need to also change the previous question's (Does it gallop?)  NO_ptr to this new question, and I am not sure how to refer to the previously malloc'd struct.

I hope you understand what I mean. If you run my prog you will see my problem.

Thanks


#include <stdio.h>

struct node
{
     int nodetype; /*1 = question, 2 = object*/
     int nodenumber;
     char object[25];
     char question[25];
     struct node *YES_ptr;
     struct node *NO_ptr;
};

int main()
{
     struct node *new_ObjectNode,  *current_node, *new_questionNode, dog;
     char  buffer[255], buffer1[255];
     char *new_object1;
     char  user_input;
     char *new_object, *new_question;
     int nodecount = 1;
     
     /* HARD CODE AN OBJECT NODE */
     //struct node dog;

     dog.nodetype = 2;
     dog.nodenumber = 0;
     dog.YES_ptr = NULL;
     dog.NO_ptr = NULL;
     strcpy(dog.object, "Dog");
     
     //Allocate memory for the 2 new structs
     new_ObjectNode = (struct node*)malloc (sizeof(struct node));
     new_questionNode = (struct node*)malloc (sizeof(struct node));  
     
     printf("______________________________\n");
     printf("|                            |\n");      
     printf("|       GUESSING GAME        |\n");
     printf("|                            |\n");      
     printf("______________________________\n\n");      
     printf("Welcome to my game\nPlease thing of an object/animal/thing\n");
     printf("______________________________\n");
     
     //Set the current node to Dog when prog is first run
     current_node= &dog;
     
//Outer loop for game
     while (1)
     {
//Inner loop for  questions
       while (1)
       {
      
                //If we are at a question node
         if (current_node->nodetype == 1)
       {
          //ask the question
          printf("%s \n", current_node->question);
          fgetc(stdin);
          
          //Get answer from user
          scanf("%c", &user_input );
            user_input = toupper( user_input );
            //If answer is yes set current node to YES_ptr
          if(user_input == 'Y'){
               current_node = current_node->YES_ptr;
               }
          //If answer is no set current node to NO_ptr
            if(user_input == 'N'){
             current_node = current_node->NO_ptr;
            }
             
       }//if (question node)
      
      
         if (current_node->nodetype == 2)
      { //Object Node
            printf("Are you thinking of a %s?",current_node->object);
            fflush(stdin);
          scanf("%c", &user_input );
            user_input = toupper( user_input );
            if(user_input == 'Y')
         {
               printf("I win\n");
               break; //Break out of the loop
            }

            if(user_input == 'N')
         {
               printf("You Win .....\n");
               printf("What where you thinking?\n ");

               //Enter new object and question into a new node
     
               printf("Please Enter An Object \n");
               fgetc(stdin);
               new_object = fgets(buffer, 255, stdin);
               printf("You have entered: %s\n", new_object);
               memset(new_ObjectNode ->object, 0, 25);
             memcpy(new_ObjectNode ->object, new_object,24);
             new_ObjectNode ->nodetype = 2;
             new_ObjectNode ->nodenumber = nodecount+1;
             nodecount ++;
     
               printf("Please Enter A Question \n");          
               new_question = fgets(buffer, 255, stdin);
               memset(new_questionNode ->question, 0, 25);
             memcpy(new_questionNode ->question, new_question,24);               
             new_questionNode ->nodetype = 1;
             new_questionNode ->nodenumber = nodecount+1;
             nodecount ++;    
              
             //Ask a question to distinguish between the new object and
             //the current object
            
             printf("Is the answer for %s Yes?",new_ObjectNode->object);
               scanf("%c", &user_input );
               user_input = toupper( user_input );
            
             //Set the question's pointers according to user answer
               if(user_input == 'Y'){
               new_questionNode ->YES_ptr = new_ObjectNode;
               new_questionNode ->NO_ptr = current_node;
                 printf("Yes PTR: %s\n", new_questionNode->YES_ptr->object);
                 printf("No PTR: %s\n", new_questionNode->NO_ptr->object);
                 }  
               if(user_input == 'N'){
               new_questionNode ->NO_ptr = new_ObjectNode;
               new_questionNode ->YES_ptr = current_node;
                 printf("Yes PTR: %s\n", new_questionNode->YES_ptr->object);
                 printf("No PTR: %s\n", new_questionNode->NO_ptr->object);
                 }  
                            
               //printf("Object You entered into struct is: %s \n", new_ObjectNode->object);
               //printf("Question You entered into struct is: %s \n", new_questionNode->question);
               
             //Set the current node to the new question node
             current_node= new_questionNode;
               break; //Break out of loop
           } // (User input N)
        
          else  printf("\007Error: Invalid choice\n");
     } // if (Object Node)
     

              
     }

     
     printf("Another Go?\n");        
     /*Get Response From User */
     scanf("  %c", &user_input );
     user_input = toupper( user_input );
 
     /*If answer is No exit*/
     if(user_input == 'N'){
       printf("Thanks for playing\n");
       break;
       }      
  }
}

0
Comment
Question by:welsh_boy
  • 4
  • 3
  • 2
  • +2
11 Comments
 

Author Comment

by:welsh_boy
ID: 9889632
sorry about some of the indentation, it has pasted in wrong!
0
 

Author Comment

by:welsh_boy
ID: 9889645
sorry about the indetation, it lost some of it when pasted in
0
 
LVL 44

Assisted Solution

by:Karl Heinz Kremer
Karl Heinz Kremer earned 50 total points
ID: 9889712
You need to keep the old pointer to your struct around so that you can change the data. One way to do this is to add another pointer to your structure:
    struct node *previous;

At the time you create your new node, you would then assign the the address of the struct you came from to the previous pointer. This way you can traverse your tree back and forward again.

This is in essence the idea behind a double-linked list: You can traverse it forward and backward.
0
 
LVL 84

Expert Comment

by:ozo
ID: 9890014
#include <stdio.h>

struct node
{
     int nodetype; /*1 = question, 2 = object*/
     int nodenumber;
     char object[25];
     char question[25];
     struct node *YES_ptr;
     struct node *NO_ptr;
};

int main()
{
    struct node *new_ObjectNode,  *current_node, *new_questionNode, dog;
    struct node *root_node;
    char  buffer[255], buffer1[255];
    char *new_object1;
    char  user_input;
    char *new_object, *new_question;
    int nodecount = 1;
     
    /* HARD CODE AN OBJECT NODE */
    //struct node dog;

    dog.nodetype = 2;
    dog.nodenumber = 0;
    dog.YES_ptr = NULL;
    dog.NO_ptr = NULL;
    strcpy(dog.object, "Dog");
     
    //Allocate memory for the 2 new structs
     
    printf("______________________________\n");
    printf("|                            |\n");      
    printf("|       GUESSING GAME        |\n");
    printf("|                            |\n");      
    printf("______________________________\n\n");      
    printf("Welcome to my game\nPlease thing of an object/animal/thing\n");
    printf("______________________________\n");
     
    //Set the current node to Dog when prog is first run
    root_node= &dog;
//Outer loop for game
    while (1)
    {
//Inner loop for  questions
     current_node= root_node;
        while (1)
        {
     
            //If we are at a question node
            if( current_node->nodetype == 1 ){
                //ask the question
                printf("%s \n", current_node->question);
                //fgetc(stdin);
         
                //Get answer from user
                scanf(" %c", &user_input );
                user_input = toupper( user_input );
                //If answer is yes set current node to YES_ptr
                if( user_input == 'Y' ){
                    current_node = current_node->YES_ptr;
                }
                //If answer is no set current node to NO_ptr
                if( user_input == 'N' ){
                    current_node = current_node->NO_ptr;
                }
             
            }//if (question node)
     
            if( current_node->nodetype == 2 ){
                //Object Node
                printf("Are you thinking of a %s?",current_node->object);
                fflush(stdin);
                scanf(" %c", &user_input );
                user_input = toupper( user_input );
                if( user_input == 'Y' ){
                    printf("I win\n");
                    break; //Break out of the loop
                }

                if( user_input == 'N' ){
                     printf("You Win .....\n");
                     printf("What where you thinking?\n ");
 
                     //Enter new object and question into a new node
     
                     printf("Please Enter An Object \n");
                     fgetc(stdin);
                     new_object = fgets(buffer, 255, stdin);
                     printf("You have entered: %s\n", new_object);
                     new_ObjectNode = (struct node*)malloc (sizeof(struct node));
                     memset(new_ObjectNode ->object, 0, 25);
                     memcpy(new_ObjectNode ->object, new_object,24);
                     new_ObjectNode ->nodetype = 2;
                     new_ObjectNode ->nodenumber = nodecount+1;
                     nodecount ++;
     
                     printf("Please Enter A Question \n");          
                     new_question = fgets(buffer, 255, stdin);
                     new_questionNode = (struct node*)malloc (sizeof(struct node));  
                     memset(new_questionNode ->question, 0, 25);
                     memcpy(new_questionNode ->question, new_question,24);              
                     new_questionNode ->nodetype = 1;
                     new_questionNode ->nodenumber = nodecount+1;
                     nodecount ++;    
             
                     //Ask a question to distinguish between the new object and
                     //the current object
           
                      printf("Is the answer for %s Yes?",new_ObjectNode->object);
                      scanf(" %c", &user_input );
                      user_input = toupper( user_input );
           
                      //Set the question's pointers according to user answer
                      if( user_input == 'Y' ){
                           new_questionNode ->YES_ptr = new_ObjectNode;
                           new_questionNode ->NO_ptr = root_node;
                           printf("Yes PTR: %s\n", new_questionNode->YES_ptr->object);
                           printf("No PTR: %s\n", new_questionNode->NO_ptr->object);
                      }  
                     if( user_input == 'N' ){
                         new_questionNode ->NO_ptr = new_ObjectNode;
                         new_questionNode ->YES_ptr = root_node;
                         printf("Yes PTR: %s\n", new_questionNode->YES_ptr->object);
                         printf("No PTR: %s\n", new_questionNode->NO_ptr->object);
                      }  
                           
                       //printf("Object You entered into struct is: %s \n", new_ObjectNode->object);
                       //printf("Question You entered into struct is: %s \n", new_questionNode->question);
               
                       //Set the current node to the new question node
                       root_node= new_questionNode;
                       break; //Break out of loop
                } // (User input N)      
                else  printf("\007Error: Invalid choice\n");
            } // if (Object Node)
        }
     
        printf("Another Go?\n");        
        /*Get Response From User */
        scanf(" %c", &user_input );
        user_input = toupper( user_input );
 
        /*If answer is No exit*/
        if( user_input == 'N' ){
             printf("Thanks for playing\n");
             break;
        }      
    }
}
0
 
LVL 45

Assisted Solution

by:Kdo
Kdo earned 200 total points
ID: 9890124
Hi welsh_boy,

I take it that this is the next topic after "Dealing with malloc'd structs" to help get the game underway?  :)

Double linked lists have their place, but this is the wrong application.  You've already selected a data structure (a binary tree) that is well suited to this type of problem since the problem is binary in nature.

As the binary tree builds, each node will be either an object node or a question node.  If the node is at the bottom of any branch (the node has no descendents) it MUST be an object.  If the node has descendents it MUST be a question.

Once the program reaches a bottom node and ventures a guess that is incorrect, you need to modify the tree to ask another question to differentiate between the program's guess and the actual object.  You seem to be attempting this very thing.

Here's a sample "tree" according to you example.


                      (1)  1 - Q:Does it Gallop?
                      /  \
                     /     \
                   (2)Y  (3)N    2 - Object: Horse?    3 - Object: Dog?

Upon answering No to "Does it Gallop" the program takes the "No" branch to node 3.  Node 3 is an object node where the object is "Dog".  The program guesses "Is it a Dog"?  You answer "No" because your guess is a "Lion".

Now you want to modify the tree to resemble:

                      (1)  Q:Does it Gallop?
                      /  \
                     /     \
                   (2)Y  (3)N    2 - Object: Horse?    3 - Q:Does it have a mane?
                           /  \
                          /    \
                        (4)Y (5)N  4 - Object: Lion?  5 - Object: Dog?

The easiest way to do this is to simply replicate the current node and modify the current node to ask the new question.  Here's  an example.

struct node    /* Inserted here for quick reference  */
{
     int nodetype; /*1 = question, 2 = object*/
     int nodenumber;
     char object[25];
     char question[25];
     struct node *YES_ptr;
     struct node *NO_ptr;
};

node *CurrentNode;
node *NewNode;

/*
    The current node is 3, an Object Node where the object is "Dog".
    CurrentNode->nodetype == 2;
    CurrentNode->nodenumber == 3;  // but it doesn't really matter
    Currentnode->object == "Dog";
    Currentnode->question == "";
    YES_ptr == NULL;
    NO_ptr == NULL;
*/

The program then asks for a question to distinguish between a horse and a dog.  "Does it have a mane" is entered.  The following code should very nicely solve your problem:

/*  Create a new node that will become the new object  */

  NewNode = (struct node *)malloc (sizeof (struct node));
  NewNode->nodenumber == NodeCount++;

/*  Copy the current node over the new one  */

  memcpy (NewNode, CurrentNode, sizeof (struct node));

/*  Set the link from the current node to the new one  */

  CurrentNode->NO_ptr = NewNode;

/*  Change the current node to be a question  */

  CurrentNode->nodetype = QUESTION;  /*  You should enum {QUESTION, OBJECT};  */

/*  Save the question  */

  strcpy (CurrentNode->question, buffer);


There you have it.  The tree has been expanded by adding the question "Does it have a mane?" and adding the node for "Lion".  No recursion and no travelling up the tree backwards.


Good Luck,
Kent
0
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 

Author Comment

by:welsh_boy
ID: 9890384
thanks kent, I am trying your approach, here is my changed code.
I have changed it so that it sets the YES and NO ptrs depending on the users input from the question he has entered.


Trouble is that I am now getting a segmentation fault
:(


printf("Please Enter A Question \n");          
               new_question = fgets(buffer, 255, stdin);
             struct node *NewNode = (struct node *)malloc (sizeof(struct node));
             NewNode->nodenumber ==nodecount ++;
               memcpy (NewNode, current_node, sizeof(struct node));

             
            //Ask a question to distinguish between the new object and
            //the current object
           
            printf("What is the answer for %s?",new_ObjectNode->object);
               scanf("%c", &user_input );
               user_input = toupper( user_input );
           
            //Set the question's pointers according to user answer
               if(user_input == 'Y'){
             current_node->YES_ptr = NewNode;
             current_node->NO_ptr = new_ObjectNode;
             current_node->nodetype = 1;
             strcpy (current_node->question, buffer);
                 printf("Yes PTR: %s\n", current_node->YES_ptr->object);
                 printf("No PTR: %s\n", new_questionNode->NO_ptr->object);
                 }  current_node
               if(user_input == 'N'){
             current_node->YES_ptr = new_ObjectNode;
             current_node->NO_ptr = NewNode;
             current_node->nodetype = 1;
             strcpy (current_node->question, buffer);
                 printf("Yes PTR: %s\n", current_node->YES_ptr->object);
                 printf("No PTR: %s\n", current_node->NO_ptr->object);
                 }  
                         
               //printf("Object You entered into struct is: %s \n", new_ObjectNode->object);
               //printf("Question You entered into struct is: %s \n", new_questionNode->question);
               
            //Set the current node to the new question node
            //current_node= new_questionNode;
               break; //Break out of loop
           } // (User input N)
       
         else  printf("\007Error: Invalid choice\n");
     } // if (Object Node)
     

0
 
LVL 84

Accepted Solution

by:
ozo earned 200 total points
ID: 9890548
#include <stdio.h>

struct node
{
     int nodetype; /*1 = question, 2 = object*/
     int nodenumber;
     char object[25];
     char question[25];
     struct node *YES_ptr;
     struct node *NO_ptr;
};

int main()
{
    struct node *new_ObjectNode,  *current_node, *old_ObjectNode, root;
    char  buffer[255], buffer1[255];
    char *new_object1;
    char  user_input;
    char *new_object, *new_question;
    int nodecount = 1;
     
    /* HARD CODE AN OBJECT NODE */
    //struct node root;

    root.nodetype = 2;
    root.nodenumber = 0;
    root.YES_ptr = NULL;
    root.NO_ptr = NULL;
    strcpy(root.object, "Dog");
     
    //Allocate memory for the 2 new structs
     
    printf("______________________________\n");
    printf("|                            |\n");      
    printf("|       GUESSING GAME        |\n");
    printf("|                            |\n");      
    printf("______________________________\n\n");      
    printf("Welcome to my game\nPlease thing of an object/animal/thing\n");
    printf("______________________________\n");
     
    //Set the current node to Dog when prog is first run
//Outer loop for game
    while (1)
    {
//Inner loop for  questions
     current_node= &root;
        while (1)
        {
     
            //If we are at a question node
            if( current_node->nodetype == 1 ){
                //ask the question
                printf("%s \n", current_node->question);
                //fgetc(stdin);
         
                //Get answer from user
                scanf(" %c", &user_input );
                user_input = toupper( user_input );
                //If answer is yes set current node to YES_ptr
                if( user_input == 'Y' ){
                    current_node = current_node->YES_ptr;
                }
                //If answer is no set current node to NO_ptr
                if( user_input == 'N' ){
                    current_node = current_node->NO_ptr;
                }
             
            }//if (question node)
     
            if( current_node->nodetype == 2 ){
                //Object Node
                printf("Are you thinking of a %s?",current_node->object);
                fflush(stdin);
                scanf(" %c", &user_input );
                user_input = toupper( user_input );
                if( user_input == 'Y' ){
                    printf("I win\n");
                    break; //Break out of the loop
                }

                if( user_input == 'N' ){
                     printf("You Win .....\n");
                     printf("What where you thinking?\n ");
 
                     //Enter new object and question into a new node
     
                     printf("Please Enter An Object \n");
                     fgetc(stdin);
                     new_object = fgets(buffer, 255, stdin);
                     printf("You have entered: %s\n", new_object);
                     new_ObjectNode = (struct node*)malloc (sizeof(struct node));
                     memset(new_ObjectNode ->object, 0, 25);
                     memcpy(new_ObjectNode ->object, new_object,24);
                     new_ObjectNode ->nodetype = 2;
                     new_ObjectNode ->nodenumber = nodecount+1;
                     nodecount ++;
     
                     printf("Please Enter A Question \n");          
                     new_question = fgets(buffer, 255, stdin);
                     old_ObjectNode = (struct node*)malloc (sizeof(struct node));  
                     *old_ObjectNode = *current_node;
                     memset(current_node ->question, 0, 25);
                     memcpy(current_node ->question, new_question,24);              
                     current_node ->nodetype = 1;
                     current_node ->nodenumber = nodecount+1;
                     nodecount ++;    
             
                     //Ask a question to distinguish between the new object and
                     //the current object
           
                      printf("Is the answer for %s Yes?",new_ObjectNode->object);
                      scanf(" %c", &user_input );
                      user_input = toupper( user_input );
           
                      //Set the question's pointers according to user answer
                      if( user_input == 'Y' ){
                           current_node ->YES_ptr = new_ObjectNode;
                           current_node ->NO_ptr = old_ObjectNode;
                           printf("Yes PTR: %s\n", current_node->YES_ptr->object);
                           printf("No PTR: %s\n", current_node->NO_ptr->object);
                      }  
                     if( user_input == 'N' ){
                         current_node ->NO_ptr = new_ObjectNode;
                         current_node ->YES_ptr = old_ObjectNode;
                         printf("Yes PTR: %s\n", current_node->YES_ptr->object);
                         printf("No PTR: %s\n", current_node->NO_ptr->object);
                      }  
                           
                       //printf("Object You entered into struct is: %s \n", new_ObjectNode->object);
                       //printf("Question You entered into struct is: %s \n", current_node->question);
               
                       //Set the current node to the new question node
                       break; //Break out of loop
                } // (User input N)      
                else  printf("\007Error: Invalid choice\n");
            } // if (Object Node)
        }
     
        printf("Another Go?\n");        
        /*Get Response From User */
        scanf(" %c", &user_input );
        user_input = toupper( user_input );
 
        /*If answer is No exit*/
        if( user_input == 'N' ){
             printf("Thanks for playing\n");
             break;
        }      
    }
}
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9890808

Your structure has fixed length buffers for both 'object' and 'question'.  Is the question that you're asking short enough to fit in 24 character?

Other than that, it's hard to tell exactly where the segmentation fault is occurring.  If you'll put a fflush(stdout); after each printf() we'll know the last print statement to get executed.


Kent
0
 
LVL 24

Assisted Solution

by:fridom
fridom earned 50 total points
ID: 9891139
Dear welsh_boy, this is a sort of follow-up to anoter question you asked. Asking is not bad, but a lot of the questions are beter answered in a book. What you have is  a binary search tree, check any decent book about C and you will see how to use it.

I mentioned before that I see problems in you code regarding the limits. You assume always that it will fit. It won't.  And you better be prepared to use those API calls which give you the chance to limit you input.

Another problem I saw for you is your understanding about char*, therefor I just can repeat myself. Have a look into a decent C book or look out there for online-C tutorials. Read the FAQs about C, you will have better programs while doing that.

Regards
Friedrich
0
 

Author Comment

by:welsh_boy
ID: 9891770
thanks Friedrich, and Kdo for all the help.
Will ask santa for a C book!! :)
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9892136
Hi welsh_boy,

Accepting an answer of "Go read a book" when you've got someone willingly assisting you defeats the spirit of these boards.

If you want to pursue this discussion, I'll be glad to continue walking you through the steps of finding and fixing the problems.  Both with code recommendations and detailed explanations.


Kent
0

Featured Post

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!

Get 1:1 Help Now