Purpose: Use of binary trees Use of argc/argv Description: Part of the advantage
ID: 3857941 • Letter: P
Question
Purpose:
Use of binary trees
Use of argc/argv
Description:
Part of the advantages of binary trees, or any tree in particular, is that you are able to make sense of large data sets. In this homework, you will have two input files, each containing 5000 entries. However, it is relatively easy to get what we want out of the data through binary trees. Note that the data in the dataset is real data; this makes it easier to check your work. Also note that there is no file format given, because the function to parse through the data is given to you.
Structure Definition
typedef struct n_
{
int zipCode;
char* city;
char state[3];
struct _* left;
struct n_*right;
}Node;
Function Prototypes
Node* addNode(Node* root, Node* newNode)
Input: the root of the tree, and the new node ready to be added to the tree.
Return: the root of the tree
Add the newest node to the tree. The node has been prefilled with data, so you do not have to modify the new node in anyway. Just connect it to the tree in the manner you have been doing. This function must be recursive.
int findStateCount(Node* root, char* state)
Input: the root of the tree and the state you are searching for
Return: the number of instances the state shows up throughout the tree
Using the string for the state, get a count of all nodes in the tree that have that same state. This might take a little thought, but with recursion it’s very simple. This function must be recursive. You are not allowed to use system calls.
Node* findZipCode(Node* root, int zipCode)
Input: the root of the tree and the zip code you are searching for.
Return: a pointer to the node that you found matched the zip code, or NULL if not found.
Using the zip code, search the tree for a matching node. There will either be one node found with that zip code, or none found. This function must be recursive. You are not allowed to use system calls.
void freeTree(Node* root)
Input: the root of the tree.
You are to free everything that the tree has allocated. Note that there is more to the node than just an integer and pointers. The difficulty of the function does not change, however.
int main(int argc, char** argv)
Input: your command line arguments.
Return: a number.
Get your tree made, present options to the user, get user input and call functions accordingly. Loop the program until the user decides to quit. Take note that you will need to read in the state somehow from the user. You can assume that the user puts in a proper 2-character state code, and that there will be no problem with the input.
This function has been done for you (you just have to call it):
Node* importTree(char* filename)
Bonus opportunity:
You are to thoroughly comment the importTree function, properly explaining how the function does what needs to be done. The more in-depth comments you provide the more points you will earn (this does not mean quantity over quality). Someone with less experience than you should be able to follow your thought process through your comments alone as if you wrote the code yourself.
Sample Output
$ ./a.out
Error. Usage: ./a.out <filename>
$ ./a.out sample.txt
1.Find the number of zip codes in a state
2.Find a zip code
3.Exit
> 1
Enter the state: MO
The state of MO has 153 zip codes in the file.
1.Find the number of zip codes in a state
2.Find a zip code
3.Exit
> 11
Error – not a valid option. Try again.
1.Find the number of zip codes in a state
2.Find a zip code
3.Exit
> 2
Enter the zip code you want to find: 444
No results found for zip code 444
1.Find the number of zip codes in a state
2.Find a zip code
3.Exit
> 2
Enter the zip code you want to find: 57349
Result found for zip code 57349:
City: Howard
State: South Dakota
1Find the number of zip codes in a state
2.Find a zip code
3.Exit
> 3
Program Terminated.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXCITYNAME 30
#define MAXLINELENGTH 50
typedef struct n_
{
int zipCode; //A zip code that exists in the given city/state
char* city; //Will point to a city name
char state[3]; //A state abbreviation. Note that we need
//room for the NULL terminator!
struct n_* left; //connections to other nodes
struct n_* right;
} Node;
Node* importTree(char* filename);
Node* addNode(Node* root, Node* newNode);
int findStateCount(Node* root, char* state);
Node* findZipCode(Node* root, int zipCode);
void freeTree(Node* root);
int main(int argc, char** argv)
{
// checking for proper arguments
if(argc != 2) {
printf("Usage: %s <filename> ", argv[0]);
exit(1);
}
// maintain the root of the tree
Node* root = NULL;
// read da file, make da tree
root = importTree(argv[1]);
if(root == NULL) {
printf(" Failed to import tree from file");
exit(1);
}
int results = 0;
int input = 0;
int zipSearch = 0;
Node* zipNode = NULL;
char* stateSearch = malloc(sizeof(char)*3);
// menu operation
while(1) {
printf(" 1: find number in a state");
printf(" 2: find a ZIP code");
printf(" 3: exit");
printf(" > ");
scanf("%d", &input);
switch(input) {
case 1:
printf(" Enter the state you want to search for:");
printf(" > ");
scanf("%s", stateSearch);
// find number of results per state
results = findStateCount(root, stateSearch);
if(results == 0) {
printf(" No results found for that state code");
} else {
printf(" The state has %d results in the sample", results);
}
break;
case 2:
// search for a ZIP code
printf(" Enter the ZIP you want to find:");
printf(" > ");
scanf("%d", &zipSearch);
// TODO: check the zipcode entered is 5 digits
zipNode = findZipCode(root, zipSearch);
if(zipNode == NULL) {
printf(" No results found for %d", zipSearch);
} else {
printf(" Result found for %d: ", zipSearch);
printf(" City: %s", zipNode->city);
printf(" State: %s", zipNode->state);
}
break;
case 3:
// quit
freeTree(root);
free(stateSearch);
exit(0);
break;
default:
printf(" Invalid selection, choose again: ");
}
}
// just in case we break out of our switch statement, make sure everything is free
freeTree(root);
free(stateSearch);
return 0;
}
Node* addNode(Node* root, Node* newNode)
{
// the new node shouldnt be null
if(newNode == NULL) {
printf(" NULL pointer passed to addNode()");
exit(1);
}
// if there is no tree, newnode starts the tree
if(root == NULL) {
return newNode;
} else {
// big zip codes on the right
if(newNode->zipCode > root->zipCode) {
root->right = addNode(root->right, newNode);
}
// lil zip codes on the left
if(newNode->zipCode < root->zipCode) {
root->left = addNode(root->left, newNode);
}
}
return root;
}
int findStateCount(Node* root, char* state)
{
// if the tree is empty, theres no instances of the state
if(root == NULL) {
return 0;
} else {
// this part increments our return if the state match
// strcmp returns 0 if matching
if(strcmp(root->state, state) == 0) {
return 1 + findStateCount(root->left, state) + findStateCount(root->right, state);
}
}
// traverse down the sides of the tree
return findStateCount(root->left, state) + findStateCount(root->right, state);
}
Node* findZipCode(Node* root, int zip)
{
if(root == NULL) {
return NULL;
} else {
if(root->zipCode == zip) {
return root;
}
Node* x = NULL;
// test the left side
x = findZipCode(root->left, zip);
if(x != NULL) {
return x;
}
// test the right side
x = findZipCode(root->right, zip);
if(x != NULL) {
return x;
}
}
// if nothing is found
return NULL;
}
void freeTree(Node* root)
{
if(root == NULL) {
return;
}
freeTree(root->left);
freeTree(root->right);
// make sure to account for the city pointer
free(root->city);
free(root);
}
Node* importTree(char* filename)
{
// we always want to maintain the root of the tree
Node* root = NULL;
// open up the text file
FILE* fp = fopen(filename, "r");
// if opening the file fails, break
if(!fp)
{
printf("Error opening file. ");
return NULL;
}
// this loop continues until the file pointer reaches the EOF
while(!feof(fp))
{
// creat a new node pointer, one for each iteration of the loop
Node* new = malloc(sizeof(Node));
// if the memory allocation fails, something went wrong or we're out of memory
if(!new)
{
printf("Failed to allocate memory. Ending read. ");
exit(1);
}
// the city field inside the node struct is a pointer, so allocate memory
// for that field
new->city = malloc(sizeof(char)*MAXCITYNAME);
// again, if memory allocation fails, something went wrong or we're out
if(!(new->city))
{
printf("Failed to allocate memory. Ending read. ");
exit(1);
}
// set both children pointers of the new node to NULL (beacuse we haven't
// read new children for this node yet. addNode() does that later
new->left = NULL;
new->right = NULL;
// this is the 'buffer' that we're scanning the file into.
char* line = malloc(sizeof(char)*MAXLINELENGTH);
// guess what...if we can't malloc memory for the buffer, something is wrong
if(!line)
{
printf("Failed to allocate memory. Ending read. ");
exit(1);
}
// if fgets() encounters an error, it returns null. this will occur at the
// end of the file as well, but the next if statement accounts for that.
if(fgets(line, MAXLINELENGTH, fp) == NULL)
{
// if fgets() returns null and it's not the end of the file, somethings
// went wrong.
if(!feof(fp))
{
printf("File reading ended prematurely. Check for errors in the file. ");
exit(1);
}
// either way, if fgets() fails (or we're at EOF), we don't have
// anything to put in the pointers that we just allocated memory for,
// so we need to free that up
free(new->city);
free(line);
free(new);
// close up our file.
fclose(fp);
break;
}
// temporary pointer will store the tokens that strtok finds.
char* tmp = strtok(line, ",");
// atoi convertts our char* to an integer which we can put in the node
new->zipCode = atoi(tmp);
// by calling strtok() with a NULL pointer, we advance to the next
// token string
tmp = strtok(NULL, ",");
// we don't use assignment operators with strings, we use strcpy() to copy
// into the memory
strcpy(new->city, tmp);
// since we're dealing with tokens, we need to append NULL terminator
// characters to the city and state fields
new->city[strlen(tmp)+1] = '';
// advancing to the next token: the state field
// the same process follows for the city field as for the state field for the
// next 3 lines
tmp = strtok(NULL, ",");
strcpy(new->state, tmp);
new->state[2] = '';
// finally, once the node has been filled with the parsed info,
// call addNode and stick it in our tree.
root = addNode(root, new);
// if the addNode() calls fail, root will still be NULL, and that's not right.
if(!root)
{
printf("Root of tree is still NULL! Ending read. ");
exit(1);
}
// free up memory from our buffer
free(line);
}
// once we've read the file and built the tree, return it.
return root;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.