TITLE

ORDERING AND MERGING TWO LISTS USING LINKED LISTS

INTRODUCTION

We have recently described pointers in C++ and how to use them to build linked lists. This project implements an ordered list abstract data type in a class with a linked list, and it uses that class in a program that orders two groups of integers, each group in its own list, and then merges them into one ordered list.

DESCRIPTION

Design, implement, test, and document a C++ program that reads two sets of integers from two files and stores them in two lists, in ascending order.

The values in the input files may be in any order. Values that appear in an input file more than once are recorded in the corresponding list only once. The program will report the values in the two lists, in order, and how many there are in each list.

The program then merges the two ordered lists into one new list, in which no value is duplicated and all the values are in ascending order. The program writes the values in this new list to the terminal, along with the number of values in the merged list.

INPUT

The program reads the names of the two input files from the terminal, and the input values themselves from the two named files. In the files, values may be in any order.

OUTPUT

The program directs its output to the terminal. It prompts for the input file names and reports the values in the two initial lists and the merged list, as well as their counts.

ERRORS

The program may assume that the input is as described; it need not detect any errors, though it should respond gracefully to an incorrect input file name. Note the file-opening function in the programming project example.

EXAMPLE

If the two files values.dat and nums.dat contain these values:

 values.dat: 35 17 22 42 21 17 33 nums.dat: 26 33 19 56 17 25 56 26 42 

then a run of the program might look like this:

 Enter input file name: values.dat Enter input file name: nums.dat There are 6 values in the first list: 17 21 22 33 35 42 There are 7 values in the second list: 17 19 25 26 33 42 56 The merged list contains 10 values: 17 19 21 22 25 26 33 35 42 56 

OTHER REQUIREMENTS

Implement an ordered list abstract data type in a class, using a pointer-based linked list. The items in a list will be integers, as specified in a typedef statement. The class should provide these operations on ordered lists:

A constructor that initializes a newly declared list to be empty.

A destructor that gives back the dynamic part of a list object.

A function length() that returns the length of the list that invokes it.

A function insert(n) that inserts the item n into the invoking list, in the appropriate position. If a value is already in the invoking list, it is not inserted.

A function merge(l1,l2) that merges the two lists l1 and l2 into the invoking list. (Any items initially in the invoking list disappear.)

A function that writes the contents of a list to an output stream. Overload the inserter operator to name this function.

A private function get_node() that allocates, initializes, and returns the address of a new node.

In the client program, use a function that opens a file for input and another that reads values from a file and inserts them into a list.

HINTS

Include in the class a function that re-initializes an existing list to be empty.