Introduction to Computer Science I by James Tam Return to the course web page

CPSC 231: Assignment 9 (Worth 8%)

New concepts to be applied for the assignment

  1. Dynamic (singly linked) lists

 

Writing a list management program:

Unless otherwise indicated the features for this assignment are the same as with the previous assignment. The main difference is that rather than storing the information in an array of records of some arbitrary size, this version of the program stores the list information in a linked list which should grow and shrink as necessary.

Features to be implemented
 
  1. Declare a new type 'CDPointer' that is a pointer to a CDNode (analogous to 'NodePointer' from my notes on linked lists).
 
  1. Declare a new type 'CDNode' (analogous to 'Node' from my notes on linked lists) which is a record with two fields: a) 'Data' which is of type 'CD' as declared in the previous assignment b) 'Next' which is a CDPointer.
 
  1. Declares a head pointer of type 'CDPointer'.
 
  1. Displays instructions on how to use the program each time that it is run.
 
  1. Display a signoff message to indicate to the user that he or she has quit the program.
 
  1. Some form of debug mode has been implemented.
 
  1. Displays a menu showing the list management functions.
 
  1. (Q)uit implemented: The user can quit the program. Until the user quits the program loops in the fashion described with the previous assignment.
 
  1. (D)isplay implemented: The program display the list in a fashion that is similar to the previous assignment.
 
  1. CD prices are displayed in dollar values (as described in the previous assignment).
 
  1. (L)oad implemented: This feature can be implemented in one of the two ways (you will only get credit for one way because the second way is an improved version of the first).
   
  1. As the information for each CD is read in from file it's added to the end of the list.
   
  1. As the information for each CD is read in from file it's inserted in correct alphabetical order (and not sorted) according to the name of the CD (no shifting of elements should be necessary).
 
  1. Correctly handle the case of an empty input file. This feature is identical to the previous assignment.
 
  1. (S)ave implemented: This feature is identical to the previous assignment.
 
  1. (F)ind implemented:  This feature is identical to the previous assignment.
 
  1. (P)resent implemented: You can implement either the basic or enhanced version as described in the previous assignment.
 
  1. (A)dd implemented: You can implement this feature in one of two possible ways (you will only get credit for one way because the second way is an improved version of the first).
   
  1. New CDs will be added to the end of the list.
   
  1. New CDs will be inserted in it's correct alphabetical order (and not sorted) according to the name of the CD (no shifting of elements should be necessary).
 
  1. (R)emove implemented: You can implement this feature in one of two possible ways (you will only get credit for one way because the second way is an improved version of the first).
   
  1. When this feature is invoked the last CD is removed.
   
  1. When this feature is invoked, the user is prompted to enter the name of the CD and the program will search for that title in the fashion described in the previous assignment except that no shifting should be needed.
 
  1. (O)rder reverse display implemented: In order to receive credit for this feature you cannot use doubly linked lists (which has pointers to the previous and successor nodes - don't worry if you don't know what I am referring to because this topic will covered in a later course: CPSC 331).  Instead you must use a recursive function or procedure call to display the list in reverse order.  That is, the last element is displayed first, the second last element is displayed second until the first element is reached and it is displayed last.  Note: The list should only be displayed in reverse order, the list should not actually be resorted into reverse order by invoking this feature.  Because this features is a 'bonus' (actually a bonus on top of a bonus) you may have to do some extra reading to in order to sufficiently understand recursion to implement it for this assignment.  Consequently I recommend that you work on this feature last, after you've gotten all the other features working because it will likely take up substantially more time than everything else.   (JT:  Hint  completing this feature depends upon your ability think and trace code in a backwards fashion).

 

Submission requirements

In addition to having to fulfill the generic assignment requirements, the requirements specific to this assignment include:

  1. Include a README file in your submission:  For this assignment you need to include a file called 'README' which includes your contact information: your name, university identification number and UNIX login name as well as all the features of the program that you implemented so that your marker knows whose assignment that he or she is marking and what features to look for.

  2. Assignments (source code/'dot-p' file and the README file) must be electronically submitted.  In addition a paper print out of the source code and README must be handed into the assignment drop box (located on the second floor of the Math Sciences building) for the tutorial that you are registered in.  Electronically submitting the assignment allows your marker to compile and run the code in order to quickly determine what features were implemented.  Providing a paper printout makes it easier for your marker to read and flip through your source code to check for things like program style.

  3. As a reminder, you are not allowed to work in groups for this class.   Copying the work of another student will be regarded as academic misconduct (cheating).  For additional details about what is and is not okay for this class please refer to the following link.

To help make sure that you haven't missed anything here is a [checklist] of items to be used in marking.  A sample executable 'music' can be found in UNIX under the directory: /home/231/assignments/assignment9. Sample input files that you can use include 'empty.txt', 'mini.txt' and 'cd.txt'.