CPSC 241-002 Computer Science IV
(Data Structures and Algorithms)

Fall 1998
TTh 12:30--1:45 Daniel 408
Assignment 3
<http://andrewd.ces.clemson.edu/courses/cpsc241/fall98/hw/asg3.html>

Objectives:
To learn inheritance, doubly-linked list (queue) manipulation.

Due date:
09/17/98

What to hand in:
``Professional-quality'' writeup, including:
  1. Cover page containing:
    Course Id--Section No.
    Name:
    SS No:
    Assignment No.
  2. Assignment description
  3. Solution description (e.g., program design, description of algorithm, etc., however appropriate).
  4. Lessons learned, identified interesting features of your program
  5. Appendix A: Source code listing
  6. Appendix B: Sample input (if any)
  7. Appendix C: Sample output
The entire document should be a clearly written account of what you were to accomplish, what you in fact did accomplish, and what you learned (how you accomplished it). The code and sample runs, listed in the appendices, should be clearly documented (e.g., document the source code, generate informative output).

The general presentation of your document counts! (This includes qualities such as neatness, formatting, and legibility.)

Description:
  1. Using inheritance, design and implement a doubly linked list (queue) where:
    1. the base class is an element of the list, which contains protected front/back pointers, and private data (e.g., an integer value).
    2. the derived class is the head of the list.

  2. Provide the following head class member functions:
    • fadd: add node to front
    • eadd: add node to end
    • fdel: remove and return node from front
    • edel: remove and return node from end
    • fnext: return first/next node after given node
    • lprev: return last/prev node before given node
    • fprint: print list forwards
    • bprint: print list backwards
    The fnext, lprev member functions return the first/last nodes, respectively, if the provided argument is a pointer to the head node.

  3. Test your program by creating a user-specified number of nodes, e.g.,
      // create linked list
      for(int i=0; i < nums; i++) {
        qnode = new QNode(i);
        qhead->eadd(qnode);
      }
    		
    then printing the list frontwards and backwards, and finally removing nodes from either the front or back of the list.

  4. Sample output:
    Enter ll size: 4
    Printing forwards:
    0
    1
    2
    3
    Printing backwards:
    3
    2
    1
    0
    Removing from front:
    0
    1
    2
    3
    queue empty
    		
  5. (Bonus)
    1. Any extra useful list member functions you can think of.

Notes and suggestions:
  1. Initialize the node (and head) so that iniitally its front/back pointers point to itself.
  2. Each node can only be on one list. Therefore, it can only be added to a list if both its pointers point to itself.
  3. This logic can also be used to test if the queue is empty (i.e., if both its front/back pointers point to itself).