|
|
|
|
|
|
|
Chapter 11 introduced the concept of a one-dimensional array, a data structure that is a collection of components of the same type given a single name. In general, a one-dimensional array is a structure used to represent a list of items. In this chapter, we examine some common algorithms that are applied again and again to data stored as a list in a one-dimensional array. These are implemented as general-purpose functions that can be modified easily to work with many kinds of lists. |
|
|
|
|
|
|
|
|
We also consider the string, a special kind of one-dimensional array that is used to process character information like words or names. We use strings to rewrite the GetMonth function in the BirthdayReminder program, as promised in Chapter 10. We conclude with some case studies that make use of the algorithms developed in this chapter. |
|
|
|
|
|
|
|
|
Lists and List Algorithms |
|
|
|
|
|
|
|
|
As defined in Chapter 11, a one-dimensional array is a data structure that consists of a fixed number of homogeneous components. By homogeneous we mean that all the components are of the same data type. One use for an array is to store a list of values. We noted that a list may contain fewer values than the number of places reserved in the array. We used a variable length to keep track of the number of values currently stored in the array, and we employed subarray processing in the case studies to prevent processing array components that were not part of the list of values. That is, the number of places in the array is fixed, but the number of values in the list stored there may vary. |
|
|
|
|
|
|
|
|
For a moment, let's think of the concept of a list not in terms of arrays but as a separate data type. We can define a list as a varying-length, linear collection of homogeneous components. That's quite a mouthful. By linear we mean that each component (except the first) has a unique component that comes before it and each component (except the last) has a unique component that comes after it. The length of a list-the number of values currently stored in the list-can vary during the execution of the program. |
|
|
|
 |
|
|
|
|
List A variable-length, linear collection of homogeneous components. |
|
|
|
|
|
|
|
|
Length The actual number of values stored in the list. |
|
|
|
|
|
|
|
|
Like any data type, a list must have associated with it a set of allowable operations. What kinds of operations would we want to define for a list? Here are some possibilities: create a list, add an item to a list, delete an item from a list, print a list, search a list for a particular value, sort a list into al- |
|
|
|
|
|