Ask Computer Engineering Expert

Through this programming assignment, the students will learn to do the following:

Know how to process command line arguments.

Perform basic file I/O.

Use structs, pointers, and strings.

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 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. You must use getopt() to parse the command line arguments to determine the cases.

In addition to parsing and processing the command line arguments, your program needs to do the following:

You need to construct a binary search tree as you read from input. A binary search tree is a binary tree. Each node can have at most two child nodes (one on the left and one on the right), both or either one can be empty. If a child node exists, it's the root of a binary search tree (we call subtree). Each node contains a key (in our case, it's a string). If the left subtree of a node exists, it contains only nodes with keys less than the node's key. If the right subtree of a node exists, it contains only nodes with keys greater than the node's key. In case of duplicate keys, you can use a counter scheme (i.e., using an integer to indicate the number of duplicate keys the node is currently representing). You can look up binary search tree on the web or in your Data Structure textbook. Note that you do not need to balance the binary search tree (that is, you can ignore all those rotation operations) in this assignment.

Initially the tree is empty (that is, the root is null). The 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 (you shall remove the trailing line feed) and then insert the tree node to the binary search tree. Pay attention to situations that a duplicate is found, in which case, you ought to simply increment the count and remove the new node, instead of inserting the duplicate node.

You must develop two string comparison functions, one for case sensitive and the other for case insensitive. You must not use strcmp() and strcasecmp() functions provided by the C library. You must implement your own version.

Once the program has read all the input (when EOF is returned), the program then performs an in-order traversal of the binary search tree to print out all the strings one line at a time to the output file or stdout.

Before the program ends, it must reclaim the tree! You can do this by performing a post-order traversal, i.e., reclaiming the children nodes before reclaiming the node itself. Make sure you also reclaim the memory occupied by the string as well.

It is required that you use getopt for processing command line and use malloc/free functions for dynamically allocating and deallocating nodes and the buffers for the strings. It is required that you implement your own string comparison functions instead of using the corresponding libc functions.

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 can also 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).

Please submit your work through moodle as one zip file. Follow the instructions below carefully (to avoid unnecessary loss of grade):

To start, first create a directory for this homework and name it firstname-lastname-assignment1 (of course, you'd use your real name here). You should place the source code and the Makefile in the directory. One should be able to create the executable by simply 'make'. The Makefile should also contain a 'clean' target for cleaning up the directory (removing all temporary files, object files and executable files). Make sure you don't include intermediate files: *.o, executables, *~, etc., in your submission. (There'll be a penalty for including unnecessary intermediate files).

Please make sure you submit homework before the deadline. Late submission will incur penalties as specified in the syllabus.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M91521850
  • Price:- $20

Guranteed 24 Hours Delivery, In Price:- $20

Have any Question?


Related Questions in Computer Engineering

Does bmw have a guided missile corporate culture and

Does BMW have a guided missile corporate culture, and incubator corporate culture, a family corporate culture, or an Eiffel tower corporate culture?

Rebecca borrows 10000 at 18 compounded annually she pays

Rebecca borrows $10,000 at 18% compounded annually. She pays off the loan over a 5-year period with annual payments, starting at year 1. Each successive payment is $700 greater than the previous payment. (a) How much was ...

Jeff decides to start saving some money from this upcoming

Jeff decides to start saving some money from this upcoming month onwards. He decides to save only $500 at first, but each month he will increase the amount invested by $100. He will do it for 60 months (including the fir ...

Suppose you make 30 annual investments in a fund that pays

Suppose you make 30 annual investments in a fund that pays 6% compounded annually. If your first deposit is $7,500 and each successive deposit is 6% greater than the preceding deposit, how much will be in the fund immedi ...

Question -under what circumstances is it ethical if ever to

Question :- Under what circumstances is it ethical, if ever, to use consumer information in marketing research? Explain why you consider it ethical or unethical.

What are the differences between four types of economics

What are the differences between four types of economics evaluations and their differences with other two (budget impact analysis (BIA) and cost of illness (COI) studies)?

What type of economic system does norway have explain some

What type of economic system does Norway have? Explain some of the benefits of this system to the country and some of the drawbacks,

Among the who imf and wto which of these governmental

Among the WHO, IMF, and WTO, which of these governmental institutions do you feel has most profoundly shaped healthcare outcomes in low-income countries and why? Please support your reasons with examples and research/doc ...

A real estate developer will build two different types of

A real estate developer will build two different types of apartments in a residential area: one- bedroom apartments and two-bedroom apartments. In addition, the developer will build either a swimming pool or a tennis cou ...

Question what some of the reasons that evolutionary models

Question : What some of the reasons that evolutionary models are considered by many to be the best approach to software development. The response must be typed, single spaced, must be in times new roman font (size 12) an ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As