CprS 157 Schedule
CprS 157 Class 17
CprS 157 Class 19
Array-based Unsorted Lists
Chapter 13 - Class 18
- searching an unordered list
- generic features (p. 649)
- code for Search
- testing with a driver
- how Search2 differs
- sequential search in a sorted list
- code for SearchOrd
- how it differs
- inserting in an ordered list
- binary search in an ordered list
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
// 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
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.
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.
Programming Warm-up Exercises (page 797)
13.2 (number of occurrences a specific item in an unsorted list)
13.4 (searching through an unsorted list)
Homework For Chapter 13
Have Americans ever been more aware of the stockmarket? Our country is in an unparalleled phase of economic prosperity and financial health, and today you can do your bit to reinforce that health. Only authorized stockholders are allowed to attend shareholders meetings, and this morning's problem is to write a computer program that could be used at such a meeting to authenticate authorized attendees and deny access to unauthorized persons. Furthermore, your program should output a report at the end of the meeting on just who attended and how many persons were turned away by the authentication software. Carefully follow the specifications in the text and use all of the software development guidelines you know to make a disciplined, careful development of your program design. Strive for clear, elegant, and correct code. Include enough comments for a knowledgeable reader to have no difficulties in following your lines of thought. Enjoy!
Programming Problems 13.2 and 13.3, page 798 (Stockholders Meeting)