Assignment #1: Sorting with Binary Search Tree Through this programming assignme
ID: 3722882 • Letter: A
Question
Assignment #1: Sorting with Binary Search Tree Through this programming assignment, the students will learn to do the following: 1. Know how to process command line arguments. 2. Perform basic file I/O. 3. Use structs, pointers, and strings. 4. Use dynamic memory. This assignment asks you to sort the lines of an input file (or from standard input) and print the sorted lines to an output file (or standard output). Your program, called bstsort (binary search tree sort), will take the following command line arguments: % bstsort [-c] [-o output-file-name] [input file-name] If-c is present, the program needs to compare the strings case sensitive; otherwise, it's case insensitive. If the output_file_name is given with the -o option, the program will output the sorted ines to the given output file; otherwise, the output shall be the standard output. Similarly, if the input_file_name is given, the program will read from the input file; otherwise, the input will be from the standard input. You must use getopt() to parse the command line arguments to determine the cases. All strings will be no more than 100 characters long.Explanation / Answer
Hi, All these files should be in one root folder.
binarySort.c
#include "header.h"
int insertNode(struct Node *root, char *stringB, int caseSensitive){
// printf("Entering Insert Node Function ");
// printf(" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ");
// printf("Current string being inserted CaseType: %d String A: '%s' String B: '%s' ", caseSensitive, root->currLine,stringB);
// printf("Duplicate number '%d' ", root->duplicate);
//check if same
int checkIfSame = sameString(root->currLine,stringB,caseSensitive);
//check if greaterThan
int greaterThanResult = greaterThan(root->currLine,stringB,caseSensitive);
// printf(" same: '%d' , greaterThan: '%d' ", checkIfSame, greaterThanResult);
if(checkIfSame ==1) {
root->duplicate++;
// printf("Duplicate number '%d' ", root->duplicate);
// printf("Leaving Insert Node Function ");
if(caseSensitive ==0) {
// printf("creating linked list ");
// creates a temporary list
struct List *tempList;
tempList = (struct List*)malloc(sizeof(struct List));
tempList->currLine = stringB;
tempList->next = NULL;
if(root->list == NULL) {
root->list = tempList;
}else{
root->list->next = tempList;
}
return 0;
}
return 0; // success
}
if(greaterThanResult == 1) {
// printf("String A is Greater than String B ");
// Means That String B is less than the value inside of root->currLine
if(root->left != NULL) {
// printf(" LEFT CONTAINS '%s' ", root->left->currLine);
insertNode(root->left, stringB, caseSensitive);
// printf(" LEFT IS NOT NULL ");
}else{
// printf(" LEFT IS NULL ");
struct Node *tempNode;
tempNode = (struct Node*)malloc(sizeof(struct Node));
tempNode->currLine = stringB;
tempNode->right = NULL;
tempNode->left = NULL;
tempNode->list = NULL;
tempNode->duplicate = 0;
root->left = tempNode;
// printf(" Adding to LEFTNODE: '%s' ", root->left->currLine);
// printf("Leaving Insert Node Function ");
return 0;
}
}else if (greaterThanResult == 0) {
// printf("String B is Greater than String A ");
if(root->right != NULL) {
// printf(" RIGHT CONTAINS '%s' ", root->right->currLine);
insertNode(root->right, stringB, caseSensitive);
// printf(" RIGHT IS NOT NULL ");
}else{
// printf(" RIGHT IS NULL ");
/*
For my own understanding:
SO i was trying to create a variable tempNode and then
assign it some values and then store the &tempNode (memory Location)
in the root->right (pointer) location. The problem with this
was that i never allocated memory for this ever changing Struct
So you need to create a new struct Node pointer
and then allocate memory for it and then pass in the values
to that allocated memory location
*/
struct Node *tempNode;
tempNode = (struct Node*)malloc(sizeof(struct Node));
tempNode->currLine = stringB;
tempNode->right = NULL;
tempNode->left = NULL;
tempNode->list = NULL;
tempNode->duplicate = 0;
root->right = tempNode;
// printf(" Adding to RIGHTNODE: '%s' ", root->right->currLine);
// printf("Leaving Insert Node Function ");
return 0;
}
}
// printf("Leaving Insert Node Function ");
return 0;
}
void printInOrder(struct Node *root,FILE *fp){
// printf(" Entering printOrder Function ");
// This is only initialized once
static int index = 0;
if(root != NULL) {
// printf("Printing Out left ");
printInOrder(root->left,fp);
// char *someString = root->currLine;
// stores the values inside of this global array
if(fp != NULL) {
fprintf(fp, "%s ", root->currLine);
printLinkedList(fp, root);
}else{
printf("Index '%d' value'%s' ", index, root->currLine);
printLinkedList(fp, root);
}
index++;
// printf("Printing out right ");
printInOrder(root->right,fp);
}
// printf(" Leaving printOrder function ");
}
int printLinkedList(FILE *fp, struct Node *root){
// printf("Inside of printLinkedList ");
if(root->list == NULL) {
return 0;
}
int true = 1;
struct List *tempList;
// printf("Linked List Items ");
tempList = root->list;
while(true) {
if(fp != NULL) {
char message[] = "Linked List Item: ";
strcat(message, tempList->currLine);
fprintf(fp, "%s ", message);
}else{
printf(" LinkList Item: '%s' ",tempList->currLine);
}
if(tempList->next == NULL) {
true = 0;
}else{
tempList = tempList->next;
}
}
// printf("Leaving printLinkedList ");
return 0;
}
void printPostOrder(struct Node *root){
// printf(" Entering printOrder Function ");
// This is only initialized once
static int index = 0;
if(root != NULL) {
// printf("Printing Out left ");
printPostOrder(root->left);
// printf("Printing out right ");
printPostOrder(root->right);
free(root->currLine);
index++;
}
// printf(" Leaving printOrder function ");
}
-------------------------
header.h
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <ctype.h>
#include <stdlib.h>
// Struct Declartions
struct Node {
char *currLine;
int duplicate;
struct Node *left;
struct Node *right;
struct List *list;
} root;
struct List {
struct List *next;
char *currLine;
};
//##########Function Declarations
//String Functions
int sameString(char stringA[],char stringB[],int caseType);
void toUpperCase(char *word,int count);
void toLowerCase(char *word,int count);
int stringLength(char *word);
int greaterThan(char stringA[],char stringB[],int caseType);
//Command Line Function
void parseCommandLineOptions(int argc, char *argv[],int *caseSensitive,char **outputFile,char **inputFile);
//OpenFile Function
int determineRead(char *fileName);
void readFile(char *fileName, int caseSensitive);
void readFromInput(int caseSensitive);
//WriteFile Function
void determineOutput(char *fileName);
void writeToOutputFile(char *fileName);
void writeToScreen();
//BinarySort
int insertNode(struct Node *root,char *line, int caseSensitive);
void printInOrder(struct Node *root,FILE *fp);
void printPostOrder(struct Node *root);
int printLinkedList(FILE *fp, struct Node *root);
-----------------------------------------------
main.c
#include "header.h"
/*
author_name
*/
int main(int argc, char *argv[]){
printf("Welcome To assignment 1 ");
int caseSensitive = 0;
char *outputFile = NULL;
char *inputFile = NULL;
parseCommandLineOptions(argc,argv,&caseSensitive,&outputFile,&inputFile);
// printf("Case '%d' , outputFile '%s' inputfile '%s' ",caseSensitive,outputFile,inputFile);
int readType = determineRead(inputFile);
// printf("Read Type '%d' ", readType);
if(readType){
readFile(inputFile,caseSensitive);
}else{
readFromInput(caseSensitive);
}
determineOutput(outputFile);
printPostOrder(&root);
printf("End Of Assingment ");
return 0;
}
-----------------------------------
readFile.c
#include "header.h"
/*
Reads in the text from the passed in file
and then outputs those values into a the
binarytree creation function
*/
void readFile(char *fileName,int caseType){
// filePath Location
char path[254];
if(getcwd(path, sizeof(path)) == NULL) {
fprintf(stderr, "Error with getting path ");
exit(1);
}
FILE *fp = NULL;
strcat(path,"/");
strcat(path,fileName);
fp = fopen(path,"r");
if(!fp) {
fprintf(stderr, "File Not Found '-%s' ", path);
exit(1);
}
root.left = NULL;
root.right = NULL;
root.duplicate = 0;
char lineBuffer[1024];
char ch = NULL;
int count = 0;
int initalizeRoot = 0;
/*
Streams through the file char by char
Creates a line from those chars
stores those lines in an array
*/
while((ch = getc(fp)) != EOF) {
if((initalizeRoot == 0) && (ch == ' ') && (count != 0)){
// This should only be printed once
char *temp = (char *)malloc(sizeof(char));
lineBuffer[count] = '';
strcpy(temp,lineBuffer);
// printf("First Output '%s' ", temp);
root.currLine = temp;
initalizeRoot++;
count= 0;
}else if(ch == ' ' && count != 0 && initalizeRoot > 0) {
// Copies the lineBuffer String into a arrayStorage
char *temp = (char *)malloc(sizeof(char));
lineBuffer[count] = '';
// printf("Output '%s' ", lineBuffer);
// printf("In the root Node '%s' ", root.currLine);
strcpy(temp, lineBuffer);
insertNode(&root,temp,caseType);
count = 0;
}
if(ch != ' ') {
lineBuffer[count] = ch;
count++;
}
}
// Closes the file
fclose(fp);
// printf("End of ReadFile ");
// int value = binarySort(lineStorage,index);
}
------------------------------------
readFromInput.c
#include "header.h"
void readFromInput(int caseSensitive){
// intiate reading from the terminal input
// printf("Inside of Read Input function ");
//Creates root node
root.left = NULL;
root.right = NULL;
root.list = NULL;
root.duplicate = 0;
int end = 0;
char *inputString = (char *)malloc(sizeof(char));
char *rootVal = (char *)malloc(sizeof(char));
printf("Enter Values To Sort ");
scanf("%[^ ]", rootVal );
root.currLine = rootVal;
// printf("Root Value '%s' ", root.currLine);
// Loops through users inputs then creates nodes for the tree
while(end == 0){
// Scanf needs spaces infront of it so that it can ignore
// the which was created by the previous scanf
printf("Enter Values To Sort ");
scanf(" %[^ ]", inputString );
printf("You Typed '%s' ", inputString);
char *temp = (char *)malloc(sizeof(char));
strcpy(temp, inputString);
// printf("The value of root '%s' ", root.currLine);
insertNode(&root, temp, caseSensitive);
printf("Enter 1 to stop and 0 to continue ");
scanf(" %d", &end );
};
printf("Thank you ");
}
-------------------------------------
parseCommandLineOptions.c
#include "header.h"
void parseCommandLineOptions(int argc, char *argv[],int *caseSensitive,char **outputFile,char **inputFile){
int c;
/*
opterr: If the value of this variable is nonzero then getopts prints an error message
to the standard error stream if it encounters an unkown option character or an
option with a missing required argument (this is the default behavior)
Setting it to 0 will not make getopts print any messages, but it returns
the character ? to indicate an error
*/
opterr = 0;
while((c = getopt(argc,argv, "co:")) != -1) {
switch(c) {
case 'c':
*caseSensitive = 1;
break;
case 'o':
/*
optarg: This variable is set by getopt to point at the value of the
option argument, for those that accept arguments
*/
*outputFile = optarg;
break;
case '?':
/*
optopt: When getopt encounters an unkown option character or an option
with a missing required argument it stores that option character
in this variable
*/
if(optopt == 'c')
fprintf(stderr, "Option -%c requires an argument. ", optopt);
else if(isprint(optopt))
/*
isprint: Checks whether a passed character is printable
*/
fprintf(stderr, "Unkown Option '-%c' ", optopt);
else
// %x prints out hex
fprintf(stderr, "Unkown Option character '\x%x' ", optopt);
exit(1);
default:
abort();
}
}
/*
optind: Is set by the getopts to the index of next element of the argv array
to be processed. Once getopts has found all the option arguments
this can be used to determien where all the non-opion arguments begin.
*/
*inputFile = argv[optind];
// for(index = optind; index < argc; index++) {
// printf("Non-option argument %s ", argv[index]);
// }
}
----------------------------------------------
stringComparisons.c
#include "header.h"
int stringLength(char *word){
int count = 0;
while(word[count]) count++;
return count;
}
void toUpperCase(char *word, int count){
int a =0;
for(a = 0; a < count; a++) {
if(word[a] > 96) {
word[a] = word[a] - 32;
}
}
}
void toLowerCase(char *word, int count){
int a =0;
for(a = 0; a < count; a++) {
if(word[a] < 96) {
word[a] = word[a] + 32;
}
}
}
/*
Returns 1 if true or 0 if false
*/
int sameString(char stringA[], char stringB[], int caseType){
/*
Case type will determine if method should be ran with
checking for case or not
1 = true
0 = false
*/
// printf(" a:%s | b:%s type:%d ",stringA,stringB,caseType);
int lengthA = stringLength(stringA);
int lengthB = stringLength(stringB);
if(lengthA != lengthB) return 0;
// Creates temporary placeholders
char tempA[lengthA], tempB[lengthB];
strcpy(tempA,stringA);
strcpy(tempB,stringB);
int size = 0;
// Does not check for case
if(caseType == 0) {
// printf(" Does not check for case ");
toUpperCase(tempA, lengthA);
toUpperCase(tempB, lengthA);
for(size = 0; size < lengthA; size++) {
if(tempA[size] != tempB[size]) {
return 0;
}
}
return 1;
}
// Case checking matters
for(size = 0; size < lengthA; size++) {
if(tempA[size] != tempB[size]) {
// printf(" TEst ");
return 0;
}
}
return 1;
}
/*
This program will essentially determine if stringA is greater than StringB
It will return:
0 if stringA is less than StringB
1 if stringA is greater than StringB
*/
int greaterThan(char stringA[],char stringB[],int caseType){
/*
Determines if one string is greater than the other
This gets called on after the method that determines if
the strings are the same
Case types
0 = false;
1 = true;
*/
int lengthA = stringLength(stringA);
int lengthB = stringLength(stringB);
// Temporary holders
char tempA[lengthA], tempB[lengthB];
strcpy(tempA,stringA);
strcpy(tempB,stringB);
int count = 0;
// Does not check for case
if(caseType == 0) {
toUpperCase(tempA, lengthA);
toUpperCase(tempB, lengthB);
if(lengthB < lengthA ) {
for(count = 0; count < lengthB; count++) {
if(tempA[count] != tempB[count]) {
if(tempA[count] > tempB[count]) {
return 1;
}else{
return 0;
}
}
}
}else {
// printf("Inside of String comparison Less Than ");
for(count = 0; count < lengthA; count++) {
if(tempA[count] != tempB[count]) {
if(tempA[count] > tempB[count]) {
return 1;
}else{
return 0;
}
}
}
}
}
if(lengthB < lengthA ) {
for(count = 0; count < lengthB; count++) {
if(tempA[count] != tempB[count]) {
if(tempA[count] > tempB[count]) {
return 1;
}else{
return 0;
}
}
}
}else {
for(count = 0; count < lengthA; count++) {
if(tempA[count] != tempB[count]) {
if(tempA[count] > tempB[count]) {
return 1;
}else{
return 0;
}
}
}
}
return 0;
}
----------------------------------------
determineOutput.c
#include "header.h"
void determineOutput(char *fileName){
if(fileName != NULL) {
writeToOutputFile(fileName);
}else{
writeToScreen();
}
}
----------------------------------------
determineRead.c
#include "header.h"
// Returns 1 if true and 0 if false
int determineRead(char *fileName){
if(fileName != NULL) {
return 1;
}
return 0;
}
---------------------------------------------
writeToOutputFile.c
#include "header.h"
void writeToOutputFile(char *fileName){
// printf("Inside of writeToOutputFile function ");
// get current Directory
char path[1024];
if(getcwd(path,sizeof(path)) == NULL) {
fprintf(stderr, "Error with getting path ");
exit(1);
}
FILE *fp = NULL;
strcat(path,"/");
strcat(path,fileName);
fp = fopen(path,"w+");
if(!fp) {
fprintf(stderr, "File Not Found '-%s' ", path);
exit(1);
}
printInOrder(&root,fp);
fprintf(fp, " ");
fclose(fp);
}
-------------------------------------------------------------------
writeToScreen.c
#include "header.h"
void writeToScreen(){
FILE *fp = NULL;
printInOrder(&root,fp);
}
-----------------------------------------
Makefile
CC = gcc
CFLAG=-Wall -g
all: build bin
build: main.o parseCommandLine.o determineRead.o stringComparisons.o binarySort.o determineOutput.o
$(CC) $(CFLAG) -o bstsort2 main.o parseCommandLineOptions.o determineRead.o readFile.o readFromInput.o stringComparisons.o binarySort.o determineOutput.o writeToOutputFile.o writeToScreen.o
main.o: main.c header.h
$(CC) $(CFLAG) -c main.c
parseCommandLine.o: parseCommandLineOptions.c header.h
$(CC) $(CFLAG) -c parseCommandLineOptions.c
determineRead.o: determineRead.c readFile.c readFromInput.c header.h
$(CC) $(CFLAG) -c determineRead.c readFile.c readFromInput.c
stringComparisons.o: stringComparisons.c header.h
$(CC) $(CFLAG) -c stringComparisons.c
binarySort.o: binarySort.c header.h
$(CC) $(CFLAG) -c binarySort.c
determineOutput.o: determineOutput.c writeToOutputFile.c writeToScreen.c header.h
$(CC) $(CFLAG) -c determineOutput.c writeToOutputFile.c writeToScreen.c
bin:
mkdir bin
mv *.o bin/
clean:
rm -rf *.o bin bstsort2
test.txt
bob is working.
david is a new hire.
alice is bob's boss.
charles doesn't like bob.