CprS 157 Schedule
CprS 157 Class 18
CprS 157 Class 20

Array-based Sorted Lists
Chapter 13 - Class 19





Reading Some Sample Programs


Today's readings illustrate how arrays help support several tasks that we normally think of as list processing:


// SPECIFICATION FILE (list.h)
// This file gives the specification of a list abstract data type.
// The list components are not assumed to be in order by value


// IMPLEMENTATION FILE (list.cpp)
// This file implements the List class member functions
// List representation: a one-dimensional array and a length
// variable


// SPECIFICATION FILE (slist.h)
// This file gives the specification of a sorted list abstract data
// type. The list components are maintained in ascending order
// of value


// IMPLEMENTATION FILE (slist.cpp)
// This file implements the SortedList class member functions
// List representation: a one-dimensional array and a length
// variable


// Exam program
// This program compares students who come to take an exam against
// a class roster. A list of students who took the exam and a list
// of students who missed the exam are printed.
// Assumption: Student names are unique within the first 10
// characters

Pay particular attention to the programming structures and idioms that allow arrays to model the manipulation of dynamic lists. Especially important in this regard is the ability to pass arrays to the functions that will manipulate them. Notice the inclusion of the header files at the beginning of each of the implementation files. Careful use of header files becomes more and more important, indeed crucial, as program complexity increases, and we will soon reach the point where their inclusion in our programming projects will be routine.
 
 

Programming Exercises

  Solve these exercises in class, to your own satisfaction. If called for, create the appropriate data files and test your program on your data. Demonstrate your solutions to the instructor or to the class TA. There is nothing to hand in from this activity.
 
 

Homework For Chapter 13

  We have now built two classes supporting the abstract datatypes of sorted and unsorted lists. Both of these classes were written to accommodate data items of an arbitrary, but simple, datatype. This morning's project involves modifying one of the classes (your choice) to accommodate a compound datatype. The list elements in these new lists will be records (C structs). We will need to sort these new lists on just a specific field of their records, eg., sort on the person's names rather than their addresses. We will also need some selectors for extracting data from such records, so this morning's project is an opportunity to use several of the topics we have studied recently. Enjoy!