This program is called: bstsort.c
This program will use:
- structs, pointers, strings, and dynamic memory.
- getopt for processing command line.
- malloc/free functions for dynamically allocating and deallocating nodes and the buffer for strings.
This program will NOT use:
- any libc string comparison funtions.
- strcmp() and strcasecmp() functions.
This program will perform the following:
- (1) Sorts the lines of an input file (or from standard input)
- (2) print the sorted lines to an output file (or standard output).
This program will take the following command line arguments:
% bstsort [-c] [-o output_file_name] [input_file_name]
If -c is present, the program will compare the strings case sensitive.
Otherwise, its case insensitive.
If the output_file_name is given with the -o option, the program will output the sorted lines 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.
It will use getopt() to parse the command line arguments to determine the cases.
In addition to parsing and processing the command line arguments, this program will perform the following:
- constructs a binary search tree as it reads from input.
- each node will have at most two child nodes.
- Either one or both can be empty.
- If a child node exists, it is the root of a BST called subtree.
- Each node contains a string.
- If the left subtree of a node exists, it contains only nodes with strings greater than the nodes string.
- In case of duplicate strings, this program uses a counter scheme.
NOTE: this program does not balance the BST.
Program's intended sequence:
- Initially the tree is empty(root is null).
- Program reads from the input file(or stdin) one line at a time.
- If the line is not an empty line, it should create a tree node that stores a copy of the string.
- Then it will remove the trailing line feed and then insert the tree node to the BST.
- If a duplicate is found, it will simply increment the count and remove the new code.
- As opposed to inserting the duplicate node.
- An empty line would indicate the end of input for stdin.
- An empty line or end of file would indicate the end of input for an input file.
- In the situation where case insensitive is chosen, then it will use all lower case for the strings.
- Once the program has read all the input, the program performs an in order traversal of the BST.
- Then it prints out all the strings one line at a time to the output file or stdout.
- Before the program ends it reclaims the tree by performing a post-order traversal.
Here's an example:
bash$ cat myfile
bob is working.
david is a new hire.
alice is bob's boss.
charles doesn't like bob.
bash$ ./bstsort myfile
alice is bob's boss.
bob is working.
charles doesn't like bob.
david is a new hire.
One should also be able to use './bstsort -o sortedfile < myfile' to take input from stdin (in this case, it's replaced by a file by the shell) and output the sorted lines in the output file (called sortedfile in the example).
