CS210 Lab: Sorted Lists and Inheritance

Prelab Questions:

For a review of relevant topics click here.

Highlights of This Lab:

Lab Exercise:


Click the little computer above for a detailed description.
For this excercise you will be asked to make use of sorted list functions to reassemble a message that has been sent as packets in mixed-up order.

1. Review of Lists

"The list is perhaps the most commonly used data structure. Just think how often you make lists of things to do, places to be, and so on. The defining property of a list is that the data items are organized linearly--that is, every data item has one data item immediately before it and another immediately after it (except, of course, the data items at the beginning and end of the list)."
(A Laboratory Course in C++ Data Structures, page 24)

There are two different kinds of lists: unsorted and sorted. Last week, we focused on unsorted lists--where there is no particular order to the data. This week we focus on sorted lists-- where data are maintained in ascending (or descending order).

Regardless of whether the list is sorted or unsorted, there are a set of general purpose operations.

1.1 Typical Operation of a Sorted List

The following are some typical operations of the Sorted List Note: The last five functions (gotoBeginning(), gotoEnd(), gotoNext(), gotoPrior(), and getCursor()) are relevant to the cursor. They allow you to iterate through the entire list--processing it item by item. This gives the user access to each item in sequence.

2. Difference between Sorted and Unsorted Lists

The main difference between the unsorted and sorted lists comes in the implementations of:

2.1 Insert

For the sorted list, instead of simply adding items after the cursor, we must search through the list to find the appropriate location. For instance, the following diagram shows the difference between the order of the items in the unsorted and sorted lists after the same series of insert statements.

Unsorted
insert a, b, r, p 		Sorted
insert a, b, r, p

In the unsorted list, the placement of the items depends on the order of the insert statements. In the sorted list, the items are in alphabetical order, regardless of the insert statements.

2.2 Replace

Previously, for the unsorted list, we just swapped out the old value (indicated by the cursor) with a new value. This will not work in a sorted list. We want to be sure to maintain the order of the list. We, therefore, remove the old value and insert a new value in the appropriate location.

The following diagram shows the difference between what happens in the replace statements for the unsorted and sorted lists (given the initial list below).

Initial List Unsorted
replace x 		Sorted
replace x

Notice that for the sorted list, although the p is replaced, the x is in its appropriate ordered location (at the end of the list).

2.3 Find/Retrieve

Before (in unsorted lists), we had to cycle through each item in the list to find a match. When the target item is last in the list, we have to go through each item in the list.

If the list is sorted, however, we can make use of a binary search, which is typically a faster search algorithm. Consider the following example.

If we are looking for 'x' at the end of the list, a binary search will do 4 comparisons, while a sequential search (such as in an unsorted list) will do 8 comparisons.

Note: binary searches can only be done on sorted lists. This is why unsorted lists do not make use of the binary search.

2.4 More about Sorted Lists

Something has been omitted in the above discussion. That is, sorted lists are typically sorted by some key. In the above examples, the lists have have been shown with one item (a letter). In fact, sorted lists, contain items which are structures.

Let's demonstrate this pictorially (below) using a list of student records. Student records contain at least the student name and number (two components). We can sort this list by either name or number. In the first case, the key is the student name and in the second case, the key is the student number.

Key is Student Name Key is Student Number

The key that is used for sorting is indicated in yellow.

3. Inheritance

We said above that the only difference between the Unsorted and Sorted List is the implementation of the insert, retrieve, and replace operations. Instead of typing up all of the functions twice, we can "reduce/reuse/recycle" the code that we used in the previous lab for the unsorted list.

Summary of List Operations
*(indicates different implementation)
isEmpty()
isFull()
insert(DataType)*
retrieve(char, DataType)*
replace(DataType)*
clear()
showStructure()
gotoBeginning()
gotoEnd()
gotoNext()
gotoPrior()
getCursor()

We recycle this code using inheritance. We will derive the Sorted List from the Unsorted List. The derived class (the Sorted List) will inherit the member functions and data members of the existing base class (the Unsorted List). In additon, the derived class may have its own member functions and data members. The following declaration from ordlist.h derives a class called OrdList from the List class. 

class OrdList : public List
{
  public:

    // Constructor
    OrdList ( int maxNumber = defMaxListSize );

    // Modified (or new) list manipulation operations
    virtual void insert ( const DataType &newDataItem )
        throw ( logic_error );
    virtual void replace ( const DataType &newDataItem )
        throw ( logic_error );
    bool retrieve ( char searchKey, DataType &searchDataItem );

    // Output the list structure -- used in testing/debugging
    virtual void showStructure () const;

  private:

    // Locates an element (or where it should be) based on its key
    bool binarySearch ( char searchKey, int &index );
};
Note that the declaration 
class OrdList : public List
Indicates that Ordlist is derived from List. The keyword "public" specifies that this is a public inheritance. Therefore, OrdList will have access to List's public member functions, but not to its private data members (or private member functions).

However, because we want the member functions in OrdList to have access to List's private data members, we must change the data members in the List class declaration from private to protected as follows: 

class List
{
  . . .
  protected:

    // Data members
    int maxSize,   	 	// Maximum number of elements in the list
        size,       	 	// Actual number of elements in the list
        cursor;     		// Cursor array index
    DataType *dataItems;  	// Array containing the list elements
};
Before this change, List's data members were private and therefore could only be accessed by List's member functions. Now, with protected data members, the derived (OrdList) class has access (through its member functions) to List's data members.

A few other things can be noted about this derived OrdList class: 

class List
{
  public:
    
    ...
    // List manipulation operations
    virtual void insert ( const DataType &newDataItem )  // Insert
        throw ( logic_error );    
    virtual void replace ( const DataType &newDataItem ) // Replace
        throw ( logic_error );
    ...

  protected:

    // Data members
    int maxSize,    // Maximum number of elements in the list
        size,       // Actual number of elements in the list
        cursor;     // Cursor array index
    DataType *dataItems;  // Array containing the list elements
};

4. Application: Sorting Packets

The following section describes an application of the Sorted List. Later, in the lab exercise, you will be given a chance to implement this program.

When a message is sent through a packet-switching network, the message is NOT sent as a continuous stream of data. Instead, it is divided into pieces called packets. These packets are sent through the network to a receiving site, which reassembles the message.

Each packet may come by a different path, and, therefore, arrive in a different order then they were intended. In order for the receiving site to reassemble the message, each packet must contain its order relative to the sequence of packets.

For example, if we want to send the message "HELLO! CS 210 IS FUN" as packets of five characters long. Each packet will also contain a number indicating its position in the message. The result will be the following set of packets:

1 HELLO
2 ! CS
3 210 I
4 S FUN

No matter in what order these packets arrive, a receiving site can correctly reassemble the message by placing the packets in ascending order based on their position numbers.

Your job is to create a program that reassembles the packets contained in a text file (message.dat). The contents of this file are the following: 

13 ions!
4 sfull
11 ongra
8  the
5 y rec
9 messa
3 ucces
2 ave s
10 ge. C
7 ucted
1 You h
12 tulat
6 onstr
14 1!!2!
Your program will make use of the Sorted List to reassemble the packets in this message. Assume that each packet in the message file contains a position number and five characters from the message.

Your program will have the following declarations: 

const int packetSize = 6;  // Number of characters in a packet
                           // including null ('\0') terminator,
                           // but excluding the key (char 0).

struct DataType 
{
    int position;              // (Key) Packet's position w/in message
    char body[packetSize];     // Characters in the packet
    int getKey () const
        { return position; }   // Returns the key field
};
Notice that the position is the key, and the body contains the five characters of the message.

5. Lab Exercise

Test Plan for Message Processing Program
Test Case Checked
Message in the file message.dat  
   
   

If you would like to, make your own message files and test them with this program.

6. Postlab Exercises

For postlab exercices, click here.

This page last modified by Nova Scheidt:
Friday, 21-Aug-2020 15:22:14 CST
Accessed     times.

CS Dept Home Page
CS Dept Class Files
CS210 Class Files


Copyright: Department of Computer Science, University of Regina.