|
|
|
|
|
|
|
phabetical or numerical order, and so on. When we define a data type formally-by specifying its properties and the operations that preserve those properties-we are creating an abstract data type. In this chapter, we focus on lists and-later-strings as abstract data types. In Chapter 15, we explore the concept of abstract data types in greater detail. |
|
|
|
|
|
|
|
|
Defining an abstract data type is a paper-and-pencil activity. We conceive of the properties we want the data values to have, and we choose a useful set of operations that manipulate those data values. But to use an abstract data type in a computer program, we must implement the abstract data type by using existing data types. In this chapter, we implement lists by using arrays. But an array is not the only way to implement a list. In Chapter 15, we introduce a new C++ type-the class-which is a tool for implementing abstract data types, and in Chapter 18, we show yet another way to implement lists. |
|
|
|
|
|
|
|
|
Using arrays to implement lists is a widely used technique. The remainder of this section is devoted to developing a set of general-purpose operations for creating and manipulating lists that are stored in arrays. |
|
|
|
|
|
|
|
|
Sequential Search in an Unordered List |
|
|
|
|
|
|
|
|
In the CharCount program (Chapter 11), we used a function ScanList that searched through an array of characters looking for a particular one. Scanning a list to find a particular value is part of many everyday tasks. We scan the television guide to see what time a program is aired. We scan a course syllabus to locate the current reading assignment. |
|
|
|
|
|
|
|
|
The ScanList function assumes that the values in the list are unordered-that is, they are not arranged in any particular order in the list, such as ascending order or descending order of value. Therefore, ScanList uses a sequential search-an algorithm in which we start at the beginning of the list and look at each item in sequence. We stop the search as soon as we find the item we are looking for (or when we reach the end of the list, concluding that the desired item is not present in the list). |
|
|
|
|
|
|
|
|
We recode the ScanList function as a general-purpose sequential search function that can be used in any program that uses a list. To make it more general, we replace the problem-dependent variable names with general ones. The following declarations are assumed to be global declarations. |
|
|
|
|
|
|
|
|
The general-purpose search function needs five parameters: |
|
|
|
|
|
|
|
|
1. The array containing the list to be searched |
|
|
|
|
|
|
|
|
2. The length of the list |
|
|
|
|
|
