Program 3: Sorting a List of Lines - Linked List - Part 1

P3 Meow.txt

Download P3 Meow.txt

Banner

Download Banner

A good way to get familiar with pointers, and as an introduction, is to first write a method:
LoadLinkedListNOTSorted(). Add items to the head. Follow the following steps:
1. Open input file: p3Meow.txt
2, Open output file: consoleOuput.txt
3, Get first line from input file
4. Call start() function to initialize Head
5. Start while loop, read next line from file. If EOF exit loop and close files
6. Call insert() function
7. In insert, create a new Cell
8. Save Head's next in new Cell's next.
9. Point Head to new Cell.
10. Repeat steps 5 - 9 above.
11.When EOF found, close files.
The above is a good exercise just to practice populating an UNSORTED linked list. For the final Program 3 assignment, Due next week, the linked list MUST be sorted. At a minimum I will be looking for the functionality for this assignment.

1 Goals

1. Organize a modular program in the C/C++


2. To use an input file (p3Meow.txt
   
   Download p3Meow.txt) and read it line by


3. To use a command-line


4. To handle end of file


5. To use C++ strings and a string


6. To implement and use a linear linked list


7. To implement an insertion

2 The Project

Implement a main function with a command-line argument that does these things:

1. Call banner() at the beginning of your program and bye() at the


2. Instantiate the List class


3. Open and read in the file named by the command-line argument. Handle eof properly. If there are any problems, call fatal)().

The input file contains a series of lines of text.
Do not
modify my file in order to make your program work.
Do not
remove the newline character on the end of the last line.

4. Use List::insert() to insert each line of the file into the List. (This is a linked-list insertion sort.)


5. After end of file, print the sorted You will be alphabetizing based on the entire line, not one letter or one word. Use the
   


6. Call bye() before you return from

3 The List Class and Cell class.

List and Cell comprise a tightly coupled pair of classes: neither makes sense without the other. There are two ways to create a tightly coupled pair of classes. One is shown in Lecture 4, the other is described and used in this assignment. Review the diagrams, descriptions, and code in Lecture 4. Borrow large parts of it. However, delete functions that you do not need and do not use a friend declaration.

1. Make a header file and an implementation file for List and


2. In the header file, write the class declaration for List, with the private class declaration for Cell inside it (at the top).


3. Although Cell is inside the private part of List, make everything in Cell public, so List can use it.


4. In Cell, implement constructor and destructor. The parameters to the constructor should be a string (the input text) and a Cell* that defaults to


5. In the public part of List, write prototypes or inline functions for constructor, destructor, print, and insert (described below).


6. In the private part of List define a pointer for the head of the list, and two scanning pointers: prior and scan. Initialize the head to

7. In the private part of List write a prototype for find() (described below). Add any other private functions that you find


8. If your function fits on one line, put it entirely in the header file, instead of a prototype. This is called an “inline function” and it increases the efficiency of the running

The find() function.

• As shown in class, initialize the scan pointer to the head of the list and the prior pointer to nullptr.


• In a 2-pointer walk, always set prior = scan before you change scan to scan->next.


• Do a 2-pointer walk down the list until scan points at a cell whose data is greater than the new data.


• At this point, prior is pointing to the cell that should precede the new cell.

The insert() function.

• Call find() to position the scan and prior pointers on your linked


• Instantiate a new Cell containing the line of text you just read and pointing to whatever scan

currently points to.

• Then check prior: if it is nullptr, make head point at the new cell. Otherwise, make the cell that prior points at point at the new


• If you do this in the right order, it is four lines of

4 Please Note:

• 
  
  Do not
  go out to the internet to borrow code. First, if it does not follow the diagrams in the lecture, I will reject Second, you will never learn this stuff unless you struggle with it yourself. It is very important for you to become comfortable with linked data structures now, before we go on to complex data structures.


• 
  
  Do not
  lean heavily on other students. Do not borrow code from them. Consult other students only for debugging help. Come to me or to our TA for other


• 
  
  Don’t
  
  
  act
  
  
  helpless
  . Try it, and send it to me for further guidance when you are confused. But remember, I need to see what you have attempted to know why you are confused. I can’t help a person with a blank paper, or a person too timid to contact


• 
  
  Do
  reach out to our available tutors/TAs for help if required.