TOC PREV NEXT

Program — Abstract data types with arrays

For this assignment, you gain experience with using strings and pointers in C.

Readings

House, chapters 9, 10, and 14; sections 12.1 through 12.3 and 13.1.

Kernighan and Ritchie, chapters 4, 5, and 7 except sections 4.3, 4.6, 4.7, and 4.11; entries for calloc, printf, and strlen in Appendix B.

Related quizzes

Advanced strings and pointers.

CS 9C programming assignment 3
The "Animal" game

Goals

This assignment is intended to give you practice with arrays and strings.

Background

Animal is a computer game in which the program tries to guess what animal the player is thinking of. A dialog might proceed as follows: 

	Think of an animal. I will try to guess what it is.
	Please answer my questions with yes or no.
	Is it furry?
	no
	Does it have tusks?
	yes
	Does it have big ears?
	no
	Is it a rhinoceros?

If the program's guess is correct, it will print a suitably celebratory message: 

	yes
	I got it right!

If it guessed wrong, it asks for a question that will differentiate between its guess and the correct answer: 

	no
	I give up. What is it? a wild boar
	Provide a question whose answer is yes 
	for a rhinoceros and no for a wild boar.
	Does it have bad breath?

The program then updates its list of questions and answers appropriately.

The animal program internally maintains a tree of questions and answers. A sample tree, from which the above dialog would be produced, is the following.

Problem

Appendix 1 lists a framework for a program to play animal. (The program is online in the file ~cs9c/lib/p3.c.) Complete the framework. You may write extra functions beyond those suggested, but you may not change the main program.

The animal tree is represented in the program as an array of pointers to strings (the questions and answers) using typedef. The 0th element is the root of the tree; the tree element corresponding to a "yes" answer for element k is element 2k+1, and the tree element corresponding to a "no" answer for element k is element 2k+2. An array for the above tree is

Miscellaneous requirements

Don't change any of the code that is already supplied; merely add code for the eleven incomplete functions, plus whatever auxiliary functions they call. The code is more complicated than one might expect. It is set up to simplify the use of a different data structure to store the questions and answers; you'll do this in the next programming assignment.

You may assume that a question or answer is at most 80 characters long, and that the program has at most 32 questions in its repertoire. (Thus the array pictured above should only contain 32 pointers.) Your code for InitTree will call malloc or calloc; the constants MAXSTRLEN and MAXNUMQS are defined in the program in Appendix 1 for use in this call.

Test your functions in isolation. You may wish to test your subprograms as you are building them, for instance, by first testing InitTree and PrintTree, then Question, Answer, and GetNewInfo, and so on. Bring evidence of this incremental development to the Self-Paced Center when you have this assignment graded.

Test your complete program on guesses that exercise "yes" branches as well as "no" branches, and on games that result in successful guesses as well as unsuccessful guesses.

You may initialize the tree any way you want, either with input from the user or with assignment statements. Programming assignment 4 will require that you initialize the tree from a file, so you might want to explore file operations like fopen ahead of time.

Helpful hints

Dealing with pointers in C always causes beginners trouble. A good strategy is to make diagrams of the pointer arrangements you are trying to produce, and to refer to those diagrams when you run into difficulties. (Bring them to the Self-Paced Center if you need help from the tutoring staff!) Common mistakes include

Also, despite the examples in K&R (which might be called "macho C"), resist the impulse to combine the use of * and ++ or ––. For that matter, resist the impulse to use ++ or -- anywhere except for on a line by themselves (e.g. k++).

Checklist

A satisfactory grade on this assignment requires the following:

Printed listings of your program and your tests and test results
Correct behavior in guessing and adding nodes to the animal tree
Sufficient test games
Good style and layout
Reasonable names for functions, variables, and parameters
No function more than 24 lines long
Appropriate use of auxiliary functions
Evidence that subprograms were tested in isolation
Use of malloc or calloc to allocate memory for the tree
No changes to main program other than to complete the specified functions
MJC, DE: 8/95

Appendix 1: Framework of a program to play animal 

typedef int boolean;
#define FALSE 0
#define TRUE !FALSE

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXSTRLEN 80
#define MAXNUMQS 32

typedef char **TreeType;
typedef int PositionType;

/*
 * Function prototypes.
 */
TreeType InitTree ( );
void PrintTree (TreeType tree);
PositionType Top (TreeType tree);
boolean IsLeaf (TreeType tree, PositionType pos);
boolean Answer (char *question);
char *Question (TreeType tree, PositionType pos);
char *Guess (TreeType tree, PositionType pos);
PositionType YesNode (TreeType tree, PositionType pos);
PositionType NoNode (TreeType tree, PositionType pos);
void ReplaceNode (TreeType tree, PositionType pos, char *newA, char *newQ);
void GetNewInfo (TreeType tree, PositionType pos, char **newA, char **newQ);

/*
 *  Play the "animal" game, in which the program attempts to guess an animal
 *  that the user is thinking of by asking yes or no questions. Eventually,
 *  the program either will guess the user's animal or run out of questions
 *  to ask. In the latter case, the program will ask the user to provide a
 *  yes-or-no question that would distinguish between the user's animal and
 *  the program's best guess.
 *  The data structure of questions and guesses is essentially a binary tree,
 *  with each internal node having a "yes" branch and a "no" branch. Leaves
 *  of the tree represent animals to be guessed by the program. If the program
 *  fails to guess the user's animal, it replaces one of the leaves of the tree
 *  by a node containing the new question, whose children are the program's
 *  best guess and the animal provided by the user.
 *  The structure of the program is simple. It initializes the question/guess
 *  data structure, then plays games as long as the user is interested. In each
 *  game, the program starts at the top of the tree (the root) and progresses 
 *  toward the bottom (the leaves) depending on the user's responses. Once it
 *  reaches a leaf, it either has won or lost, and handles the situation as
 *  described above.
 */
int main ( ) {
	TreeType tree;
	PositionType pos;
	char *newQuestion, *newAnswer;
	tree = InitTree ( );
	printf("%s", "Think of an animal. I will try to guess what it is.\n"
	"Please answer my questions with yes or no.\n");
	while (TRUE) {
		pos = Top (tree);
		while (!IsLeaf (tree, pos)) {
			pos = Answer (Question (tree, pos))? 
				YesNode (tree, pos): NoNode (tree, pos);
		}
		if (Answer (Guess (tree, pos))) {
			printf ("I got it right!\n");
		} else {
			GetNewInfo (tree, pos, &newAnswer, &newQuestion);
			ReplaceNode (tree, pos, newAnswer, newQuestion);
		}
		if (!Answer ("Want to play again? ")) {
			return 0;
		}
	}
}

/*
 *	Return an animal tree.
 */
TreeType InitTree ( ) {
    /* Your code goes here -- delete this line */
}

/*
 *	Print an animal tree (useful for debugging).
 */
void PrintTree (TreeType tree) {
    /* Your code goes here -- delete this line */
}

/*
 *	Return the position of the "top" node in the animal tree.
 */
PositionType Top (TreeType tree) {
    /* Your code goes here -- delete this line */
}

/*
 *	Return true exactly when pos is a "leaf" of the animal tree, that is,
 *	when the string stored at pos is a guess rather than a question.
 */
boolean IsLeaf (TreeType tree, PositionType pos) {
    /* Your code goes here -- delete this line */
}

/*
 *	Print the given question, read the user's answer; return true 
 *	if the answer supplied starts with"y", false otherwise.
 */
boolean Answer (char *question) {
    /* Your code goes here -- delete this line */
}

/*
 *	Form a question out of the string stored at position pos in the given
 *	animal tree, and return the string that contains the question.
 */
char *Question (TreeType tree, PositionType pos) {
    /* Your code goes here -- delete this line */
}

/*
 *	Form a guess out of the string stored at position pos in the given
 *	animal tree, and return the string that contains the guess. 
 *	(IsLeaf(tree, pos) must be true.)
 */
char *Guess (TreeType tree, PositionType pos) {
    /* Your code goes here -- delete this line */
}

/*
 *	Return the position of the node that corresponds to a "yes" answer
 *	to the question stored at position pos in the animal tree.
 */
PositionType YesNode (TreeType tree, PositionType pos) {
    /* Your code goes here -- delete this line */
}

/*
 *	Return the position of the node that corresponds to a "no" answer
 *	to the question stored at position pos in the animal tree.
 */
PositionType NoNode (TreeType tree, PositionType pos) {
    /* Your code goes here -- delete this line */
}

/*
 *	Replace the node at position pos in the given animal tree by a node
 *	containing the given new question whose left child (down the tree in 
 *	the "yes" direction) contains the string stored at position pos, and 
 *	whose right child contains the new answer newA. Example:
before replacement
after replacement
 






 *	It's ok to copy the guess from the old node into the new node, and
 *	to copy the new question into the guess node.
 */
void ReplaceNode (TreeType tree, PositionType pos, char *newA, char *newQ) {
    /* Your code goes here -- delete this line */
}

/*
 *	Admit that you guessed wrong, ask the player what animal he/she was 
 *	thinking of, and return this in *newA.  Also ask for a question that 
 *	would be answered "yes" for what you guessed and "no" for what the 
 *	player was thinking of, and return this in *newQ.  (The node with
 *	your guess is at position pos in the tree.)
 */
void GetNewInfo (TreeType tree, PositionType pos, char **newA, char **newQ) {
    /* Your code goes here -- delete this line */
}
TOC PREV NEXT