Smatchcube's website 🌍


Exercise 17.8

file: 8_petclub.c

/* compile with 8_tree.c */
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "8_tree.h"
#define SLEN 50

char menu(void);
void addpet(Tree * pt);
void droppet(Tree * pt);
void showpets(const Tree * pt);
void findpet(const Tree * pt);
void printitem(Item item);
void uppercase(char * str);
char * s_gets(char * st, int n);
char name[SLEN];
void print_if_same_kind(Item);

int main(void)
{
	Tree pets;
	char choice;
	InitializeTree(&pets);
	while ((choice = menu()) != 'q') {
		switch (choice) {
		case 'a' : addpet(&pets);
			break;
		case 'l' : showpets(&pets);
			break;
		case 'f' : findpet(&pets);
			break;
		case 'n' : printf("%d pets in club\n",
				  TreeItemCount(&pets));
			break;
		case 'd' : droppet(&pets);
			break;
		default : puts("Switching error");
		}
	}
	DeleteAll(&pets);
	puts("Bye.");
	return 0;
}

char menu(void)
{
	int ch;
	puts("Nerfville Pet Club Membership Program");
	puts("Enter the letter corresponding to your choice:");
	puts("a) add a pet       l) show list of pets");
	puts("n) number of pets  f) find pets");
	puts("d) delete a pet    q) quit");
	while ((ch = getchar()) != EOF) {
		while (getchar() != '\n') /* discard rest of line */
			continue;
		ch = tolower(ch);
		if (strchr("alrfndq",ch) == NULL)
			puts("Please enter an a, l, f, n, d, or q:");
		else
			break;
	}
	if (ch == EOF)
		ch = 'q';         /* make EOF cause program to quit */
	return ch;
}

void addpet(Tree * pt)
{
	Item temp;
	if (TreeIsFull(pt))
		puts("No room in the club!");
	else {
		puts("Please enter name of pet:");
		s_gets(temp.petname,SLEN);
		puts("Please enter pet kind:");
		s_gets(temp.petkind,SLEN);
		uppercase(temp.petname);
		uppercase(temp.petkind);
		AddItem(&temp, pt);
	}
}

void showpets(const Tree * pt)
{
	if (TreeIsEmpty(pt))
		puts("No entries!");
	else
		Traverse(pt, printitem);
}

void printitem(Item item)
{
	printf("Pet: %-19s Kind: %-19s\n", item.petname,
	       item.petkind);
}

void findpet(const Tree * pt)
{
	if (TreeIsEmpty(pt)) {
		puts("No entries!");
		return; /* quit function if tree is empty */
	}
	puts("Please enter name of pet you wish to find:");
	s_gets(name, SLEN);
	uppercase(name);
	puts("Here are pets with same name:");
	Traverse(pt, print_if_same_kind);
}

void droppet(Tree * pt)
{
	Item temp;
	if (TreeIsEmpty(pt)) {
		puts("No entries!");
		return; /* quit function if tree is empty */
	}
	puts("Please enter name of pet you wish to delete:");
	s_gets(temp.petname, SLEN);
	puts("Please enter pet kind:");
	s_gets(temp.petkind, SLEN);
	uppercase(temp.petname);
	uppercase(temp.petkind);
	printf("%s the %s ", temp.petname, temp.petkind);
	if (DeleteItem(&temp, pt))
		printf("is dropped from the club.\n");
	else
		printf("is not a member.\n");
}

void uppercase(char * str)
{
	while (*str) {
		*str = toupper(*str);
		str++;
	}
}

char * s_gets(char * st, int n)
{
	char * ret_val;
	char * find;
	ret_val = fgets(st, n, stdin);
	if (ret_val) {
		find = strchr(st, '\n');
		if (find)
			*find = '\0';
		else
			while (getchar() != '\n')
				continue;
	}
	return ret_val;
}

void print_if_same_kind(Item item)
{
	if (strcmp(item.petname, name) == 0)
		printitem(item);
	return;
}

file: 8_tree.c

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "8_tree.h"


/* local data type */
typedef struct pair {
	Trnode * parent;
	Trnode * child;
} Pair;


/* protototypes for local functions */
static Trnode * MakeNode(const Item * pi);
static bool ToLeft(const Item * i1, const Item * i2);
static bool ToRight(const Item * i1, const Item * i2);
static void AddNode (Trnode * new_node, Trnode * root);
static void InOrder(const Trnode * root, void (* pfun)(Item item));
static Pair SeekItem(const Item * pi, const Tree * ptree);
static void DeleteNode(Trnode **ptr);
static void DeleteAllNodes(Trnode * ptr);

/* function definitions */
void InitializeTree(Tree * ptree)
{
	ptree->root = NULL;
	ptree->size = 0;
}

bool TreeIsEmpty(const Tree * ptree)
{
	if (ptree->root == NULL)
		return true;
	else
		return false;
}

bool TreeIsFull(const Tree * ptree)
{
	if (ptree->size == MAXITEMS)
		return true;
	else
		return false;
}

int TreeItemCount(const Tree * ptree)
{
	return ptree->size;
}

bool AddItem(const Item * pi, Tree * ptree)
{
	Trnode * new_node;
	if  (TreeIsFull(ptree)) {
		fprintf(stderr,"Tree is full\n");
		return false; /* early return */
	}
	if (SeekItem(pi, ptree).child != NULL) {
		fprintf(stderr, "Attempted to add duplicate item\n");
		return false; /* early return */
	}
	new_node = MakeNode(pi); /* points to new node */
	if (new_node == NULL) {
		fprintf(stderr, "Couldn't create node\n");
		return false; /* early return */
	}
        /* succeeded in creating a new node */
	ptree->size++;
	if (ptree->root == NULL)        /* case 1: tree is empty */
		ptree->root = new_node; /* new node is tree root */
	else                            /* case 2: not empty     */
		AddNode(new_node,ptree->root); /* add node to tree */
	return true; /* successful return */
}

bool InTree(const Item * pi, const Tree * ptree)
{
	return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

Item * FindItem(const Item * pi, const Tree * ptree)
{
	return &(SeekItem(pi, ptree).child->item);
}

bool DeleteItem(const Item * pi, Tree * ptree)
{
	Pair look;
	look = SeekItem(pi, ptree);
	if (look.child == NULL)
		return false;
	if (look.parent == NULL) /* delete root item */
		DeleteNode(&ptree->root);
	else if (look.parent->left == look.child)
		DeleteNode(&look.parent->left);
	else
		DeleteNode(&look.parent->right);
	ptree->size--;

	return true;
}

void Traverse (const Tree * ptree, void (* pfun)(Item item))
{
	if (ptree != NULL)
		InOrder(ptree->root, pfun);
}

void DeleteAll(Tree * ptree)
{
	if (ptree != NULL)
		DeleteAllNodes(ptree->root);
	ptree->root = NULL;
	ptree->size = 0;
}

/* local functions */
static void InOrder(const Trnode * root, void (* pfun)(Item item))
{
	if (root != NULL) {
		InOrder(root->left, pfun);
		(*pfun)(root->item);
		InOrder(root->right, pfun);
	}
}

static void DeleteAllNodes(Trnode * root)
{
	Trnode * pright;
	if (root != NULL) {
		pright = root->right;
		DeleteAllNodes(root->left);
		free(root);
		DeleteAllNodes(pright);
	}
}

static void AddNode (Trnode * new_node, Trnode * root)
{
	if (ToLeft(&new_node->item, &root->item)) {
		if (root->left == NULL) /* empty subtree */
			root->left = new_node; /* so add node here */
		else
			AddNode(new_node, root->left); /* else process subtree*/
	}
	else if (ToRight(&new_node->item, &root->item)) {
		if (root->right == NULL)
			root->right = new_node;
		else
			AddNode(new_node, root->right);
	}
	else { /* should be no duplicates */
		fprintf(stderr,"location error in AddNode()\n");
		exit(1);
	}
}
static bool ToLeft(const Item * i1, const Item * i2)
{
	int comp1;

	if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)
		return true;
	else if (comp1 == 0 &&
			strcmp(i1->petkind, i2->petkind) < 0)
		return true;
	else
		return false;
}

static bool ToRight(const Item * i1, const Item * i2)
{
	int comp1;

	if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)
		return true;
	else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0)
		return true;
	else
		return false;
}

static Trnode * MakeNode(const Item * pi)
{
	Trnode * new_node;
	new_node = (Trnode *) malloc(sizeof(Trnode));
	if (new_node != NULL) {
		new_node->item = *pi;
		new_node->left = NULL;
		new_node->right = NULL;
	}
	return new_node;
}

static Pair SeekItem(const Item * pi, const Tree * ptree)
{
	Pair look;
	look.parent = NULL;
	look.child = ptree->root;
	if (look.child == NULL)
		return look;
	while (look.child != NULL) {
		if (ToLeft(pi, &(look.child->item))) {
			look.parent = look.child;
			look.child = look.child->left;
		}
		else if (ToRight(pi, &(look.child->item))) {
			look.parent = look.child;
			look.child = look.child->right;
		}
		else /* must be same if not to left or right */
			break; /* look.child is address of node with item */
	}
	return look; /* successful return */
}

static void DeleteNode(Trnode **ptr) /* ptr is address of parent member pointing to target node */
{
	Trnode * temp;
	if ( (*ptr)->left == NULL)
	{
		temp = *ptr;
		*ptr = (*ptr)->right;
		free(temp);
	}
	else if ( (*ptr)->right == NULL) {
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	}
	else { /* deleted node has two children */
		/* find where to reattach right subtree */
		for (temp = (*ptr)->left; temp->right != NULL;
		     temp = temp->right)
			continue;
		temp->right = (*ptr)->right;
		temp = *ptr;
		*ptr =(*ptr)->left;
		free(temp);
	}
}

file: 8_tree.h

#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>

typedef struct item
{
	char petname[20];
	char petkind[20];
} Item;

#define MAXITEMS 10

typedef struct trnode
{
	Item item;
	struct trnode * left; /* pointer to right branch */
	struct trnode * right; /* pointer to left branch */
} Trnode;

typedef struct tree
{
	Trnode * root;
	int size;
} Tree;

/* function prototypes */

/* operation: initialize a tree to empty            */
/* preconditions: ptree points to a tree            */
/* postconditions: the tree is initialized to empty */
void InitializeTree(Tree * ptree);

/* operation: determine if tree is empty             */
/* preconditions: ptree points to a tree             */
/* postconditions: function returns true if tree is  */
/*                 empty and returns false otherwise */
bool TreeIsEmpty(const Tree * ptree);

/* operation: determine if tree is full             */
/* preconditions: ptree points to a tree            */
/* postconditions: function returns true if tree is */
/*                 full and returns false otherwise */
bool TreeIsFull(const Tree * ptree);

/* operation: determine number of items in tree        */
/* preconditions: *ptree points to a tree              */
/* postconditions: function returns number of items in */
/*                 tree                                */
int TreeItemCount(const Tree * ptree);

/* operation: add an item to a tree                    */
/* preconditions: pi is address of item to be added    */
/*                ptree points to an initialized tree  */
/* postconditions: if possible, function adds item to  */
/*                 tree and returns true; otherwise,   */
/*                 the function returns false          */
bool AddItem(const Item * pi, Tree * ptree);

/* operation: find an item in a tree                    */
/* preconditions: pi points to an item                  */
/*                ptree points to an initialized tree   */
/* postconditions: function returns true if item is in  */
/*                 tree and returns false otherwise     */
bool InTree(const Item * pi, const Tree * ptree);

/* operation: delete an item from a tree                */
/* preconditions: pi is address of item to be deleted   */
/*                ptree points to an initialized tree   */
/* postconditions: if possible, function deletes item   */
/*                 from tree and returns true;          */
/*                 otherwise the function returns false */
bool DeleteItem(const Item * pi, Tree * ptree);

/* operation: apply a function to each item in          */
/*            the tree                                  */
/* preconditions: ptree points to a tree                */
/*                pfun points to a function that takes  */
/*                an Item argument and has no return    */
/*                value                                 */
/* postcondition: the function pointed to by pfun is    */
/*                executed once for each item in tree   */
void Traverse (const Tree * ptree, void (* pfun)(Item item));

/* operation: delete everything from a tree           */
/* preconditions: ptree points to an initialized tree */
/* postconditions: tree is empty                      */
void DeleteAll(Tree * ptree);

#endif