c++ homework

20.docx

Home >Computer Science homework help >c++ homework

Lab 20 -- Linked List Variation: Circular Doubly Sorted Linked List with Dummy Head

In this lab, we will practice coding one type of linked list variation: the Circular Doubly Linked List with Dummy Head. The list is to be maintained in sorted (ascending) order. The advantages of this linked list variation include :

1. When coding for "insertion" and "deletion", only one case needs to be considered, i.e., there is no need to differentiate between the two cases: (1) insert/delete at the beginning of the list; (2) insert/delete at the middle or end of the list

2. For maintaining a sorted list, only one temporary pointer "cur" is needed to locate the insertion/deletion location and to perform the insertion/deletion operation.

This program reads in a number of values from the data file and inserts the items into a sorted list in alphabetical order. The format of the data file is as the following:

apple

pineapple

orange

milk

...

Your program will read the items from the data file one at a time and inserts the item into the list. It repeats these read-insert steps til the end of the data file is reached. The content of the sorted list after each read-insert step is as following:

· When the list is first created, an empty circular doubly linked list with dummy head is: head<->dummy (and dummy->next points to head; head->precede points to dummy.)

· After the first item "apple" is read, the list content is head<->dummy<->apple. (apple->next points to head, head->precede points to apple)

· After the item "pineapple" is read, the list is : head<->dummy<->apple<->pineapple. (pineapple->next points to head, head->precede points to pineapple)

· After the item "orange" is read, the list is : head<->dummy<->apple<->orange<->pineapple. (pineapple->next points to head, head->precede points to pineapple)

· After the item "milk" is read, the list is : head<->dummy<->apple<->milk<->orange<->pineapple. (pineapple->next points to head, head->precede points to pineapple)

Copy the data file using the following command:

cp ~cen/data/produce.dat workspace-directory/project-directory/.

We are not going to use a C++ class for this lab. The linked list will be developed entirely in the client program.

Write a client program with the following components:

// fill in the blank area

#include

using namespace std;

typedef string ListItemType;

struct Node {

Node * precede;

ListItemType data;

Node * next;

};

typedef Node * NodePtr;

// Declare the function "BuildSortedList" here

// Declare the function "SortedListInsert" here

// Declare the function "DisplayList" here

// Declare the function "DestroyList" here

int main()

{

ifstream myIn;

NodePtr head;

myIn.open("../produce.dat");

assert(myIn);

// call function "BuildSortedList" to read data from the data file and

// construct the list

// call function "DisplayList" to display the list

// call function "DestroyList" here

return 0;

}

// define the function "BuildSortedList" below

// Write a "while" loop to read position-item pairs from the data file.

// insert the item into the list at the specified position. Call "SortedListInsert" function for insertion.

// The loop terminates when the end of the data file is reached.

// define the function "SortedListInsert" below

// define the function "DisplayList" below

// define the function "DestroyList" below

For this lab, you need to submit one file: main.cpp.

Steps to edit, compile, run, and submit the program:

· If after you compile your program, there is compilation errors, then you need to modify the program according to the error messages. You may need to edit and compile your program multiple times before it compiles successfully.

· Now you can run the program, check to make sure the output is correct. If not, you need to modify the program and recompile and rerun the program.

· Once you are able to successfully run the program with the correct outputs, you are ready to submit the program electronically. Only submit the source file. Locate the source file in your "project" directory under your "workspace" directory. For example, if you named your "workspace" as "codelite" under your home directory, and named the project "cla20", then "main.cpp" should be in ~/codelite/cla20 directory.