1
Applied Arrays,
Lists and Strings
2
Chapter 13 Topics
Meaning of a List
Insertion and Deletion of List Elements
Selection Sort of List Elements
Insertion and Deletion using a Sorted List
Binary Search in a Sorted List
Order of Magnitude of a Function
Declaring and Using C Strings
Using typedef with Arrays
3
What is a List?
A list is a variable-length,linear
collection of homogeneous elements.
linear means each list element (except
the first) has a unique predecessor,and
each element (except the last) has a
unique successor
4
3 Basic Kinds of ADT Operations
Constructor -- creates a new instance
(object) of an ADT
Transformer -- changes the state of one or
more of the data values of an instance
Observer -- allows us to observe the state
of one or more of the data values of an
instance without changing them
5
ADT List Operations
Transformers
Insert
Delete
SelSort
Observers
IsEmpty
IsFull
Length
IsPresent
Print
change state
observe state
6
ADT Unsorted List
Data Components
length
data[ 0,,MAX_LENGTH -1 ]
number of
elements in list
array of list
elements
7
Array-based class List
IsFull
Length
SelSort
IsPresent
Delete
IsEmpty
Insert
Print
Private data:
length
data [ 0 ]
[ 1 ]
[ 2 ]
[MAX_LENGTH-1]
8
// SPECIFICATION FILE ARRAY-BASED LIST ( list.h )
const int MAX_LENGTH = 50 ;
typedef int ItemType ;
class List // declares a class data type
{
public,// public member functions
List ( ) ; // constructor
bool IsEmpty ( ) const ;
bool IsFull ( ) const ;
int Length ( ) const ; // returns length of list
void Insert ( ItemType item ) ;
void Delete ( ItemType item ) ;
bool IsPresent( ItemType item ) const ;
void SelSort ( );
void Print ( ) ;
private,// private data members
int length ; // number of values currently stored
ItemType data[MAX_LENGTH] ;
} ;
9
// IMPLEMENTATION FILE ARRAY-BASED LIST ( list.cpp )
#include,list.h”
#include <iostream>
using namespace std;
int List,,Length ( ) const
// Post,Function value == length
{
return length ;
}
bool List,,IsFull ( ) const
// Post,Function value == true,if list == MAX_LENGTH
// == false,otherwise
{
return ( length == MAX_LENGTH ) ;
}
10
List,,List ( )
// Constructor
// Post,length == 0
{
length = 0 ;
}
void List,,Insert ( /* in */ ItemType item )
// Pre,length < MAX_LENGTH && item is assigned
// Post,data[length@entry] == item && length == length@entry + 1
{
data [ length ] = item ;
length++ ;
}
11
Before Inserting 64 into an
Unsorted List
length 3
data [ 0 ] 15
[ 1 ] 39
[ 2 ] -90
[ 3 ]
.
.
.
[MAX_LENGTH-1]
The item will be placed
into the length location,
and length will be
incremented.
item 64
12
After Inserting 64 into an
Unsorted List
length 4
data [ 0 ] 15
[ 1 ] 39
[ 2 ] -90
[ 3 ] 64
.
.
.
[MAX_LENGTH-1]
item 64
13
bool List,,IsEmpty ( ) const
// Post,Function value == true,if length == 0
// == false,otherwise
{
return ( length == 0 ) ;
}
bool List,,IsPresent ( /* in */ ItemType item ) const
// Searches the list for item,reporting whether it was found
// Post,Function value == true,if item is in data [ 0,,length-1 ]
// == false,otherwise
{ int index = 0 ;
while ( index < length && item != data [ index ] )
index++ ;
return ( index < length ) ;
}
14
void List,,Delete ( /* in */ ItemType item )
// Pre,length > 0 && item is assigned
// Post,IF item is in data array at entry
// First occurrence of item is no longer in array
// && length == length@entry - 1
// ELSE
// length and data array are unchanged
{ int index = 0 ;
while ( index < length && item != data [ index ] )
index++;
// if item found,move last element into item’s place
if ( index < length )
{
data [ index ] = data [length - 1 ] ;
length-- ;
}
}
15
Deleting 39 from an
Unsorted List
index,0
39 has
not been matched.
item 39
length 4
data [ 0 ] 15
[ 1 ] 39
[ 2 ] -90
[ 3 ] 64
.
.
.
[MAX_LENGTH-1]
16
Deleting 39 from an
Unsorted List
index,1
item 39
length 4
data [ 0 ] 15
[ 1 ] 39
[ 2 ] -90
[ 3 ] 64
.
.
.
[MAX_LENGTH-1]
39 has
been matched.
17
Deleting 39 from an
Unsorted List
index,1
item 39
length 4
data [ 0 ] 15
[ 1 ] 64
[ 2 ] -90
[ 3 ] 64
.
.
.
[MAX_LENGTH-1]
Placed copy of last list
element into the position
where 39 was before.
18
Deleting 39 from an
Unsorted List
index,1
item 39
length 3
data [ 0 ] 15
[ 1 ] 64
[ 2 ] -90
[ 3 ] 64
.
.
.
[MAX_LENGTH-1]
Decremented length.
19
void List,,Print ( )
// Prints the list
// Post,Contents of data [0,,length-1 ] have been output
{
int index ;
for ( index = 0 ; index < length ; index++ )
cout << data [ index ] << endl ;
}
Printing the List
20
Sorting
Arranging the components of a list
into order( for instance,words into
alphabetical order or numbers into
ascending or descending order)
21
Selection Sort Process
examines the entire list to select the smallest
element,Then places that element where it belongs
(with array subscript 0)
examines the remaining list to select the smallest
element from it,Then places that element where it
belongs (with array subscript 1)
.
.
.
examines the last 2 remaining list elements to select
the smaller one,Then places that element where it
belongs in the array
22
Selection Sort Algorithm
FOR passCount going from 0 through length - 2
Find minimum value in data [ passCount,,length-1 ]
Swap minimum value with data [ passCount ]
length = 5
data [ 0 ] 40 25
data [ 1 ] 100 100
data [ 2 ] 60 60
data [ 3 ] 25 40
data [ 4 ] 80 80
passCount
= 0
23
void List,,SelSort ( )
// Sorts list into ascending order using selection sort
{ ItemType temp ;
int passCount ;
int sIndx ;
int minIndx ; // index of minimum so far
for ( passCount = 0 ; passCount < length - 1 ; passCount++ )
{
minIndx = passCount ;
// find index of smallest of data [ passCount,,length-1 ]
for ( sIndx = passCount + 1 ; sIndx < length ; sIndx++ )
if ( data [ sIndx ] < data [ minIndx ] )
minIndx = sIndx ;
temp = data [ minIndx ] ; // swap
data [ minIndx ] = data [ passCount ] ;
data [ passCount ] = temp ;
}
}
24
Sorted and Unsorted Lists
UNSORTED LIST
Elements are placed
into the list in
no particular order.
SORTED LIST
List elements are in
an order that is
sorted in some way
-- either numerically
or alphabetically.
25
Array-based class SortedList
IsFull
Length
IsPresent
Delete
IsEmpty
Insert
Print
Private data:
length
data [ 0 ]
[ 1 ]
[ 2 ]
[MAX_LENGTH-1]
SortedList
26
// SPECIFICATION FILE ARRAY-BASED SORTED LIST ( slist.h )
const int MAX_LENGTH = 50 ;
typedef int ItemType ;
class SortedList
{
public,// public member functions
SortedList ( ) ; // constructor
bool IsEmpty ( ) const ;
bool IsFull ( ) const ;
int Length ( ) const ; // returns length of list
void Insert ( ItemType item ) ;
void Delete ( ItemType item ) ;
bool IsPresent( ItemType item ) const ;
void Print ( ) ;
private,// private data members
int length ; // number of values currently stored
ItemType data[MAX_LENGTH] ;
void BinSearch ( ItemType item,bool& found,int& position ) const ;
} ;
27
How does the declaration of SortedList differ
from the declaration of our original List class?
There are two main differences:
The SortedList class does not supply a sorting operation
to the client,Such an operation is needless.
The SortedList class has an additional class member in
the private part,a BinSearch function,This function is
an auxiliary(“helper”) function that is used only by other
class member functions and is inaccessible to client,
We will discuss its purpose later.
28
Basic Operations of Sorted Lists
The algorithms for
the class constructor,IsEempty,IsFull,
Length and Print
are identical to those in the List class
29
Member Functions
Which member function specifications
and implementations must change to
ensure that any instance of SortedList
ADT remains sorted at all times?
Insert
Delete
30
Insert Algorithm for
SortedList ADT
create space for the new item by
shifting down all the larger list
elements
put the new item in the list
increment length
31
Implementing SortedList
Member Function Insert
// IMPLEMENTATION FILE ( slist.cpp )
void SortedList,,Insert ( /* in */ ItemType item )
// Pre,length < MAX_LENGTH && item is assigned
// && data [ 0,,length-1 ] are in ascending order
// Post,item is in the list && length == length@entry + 1
// && data [ 0,,length-1 ] are in ascending order
{
.
.
.
}
32
void SortedList,,Insert ( ItemType item )
{
int index ;
// find proper location for new element
index = length - 1 ;
// starting at bottom of array
// shift down values larger than item
// to make room for new item
while ( index >= 0 && item < data [ index ] )
{
data [ index + 1 ] = data [ index ] ;
index -- ;
}
// insert item into array
data [ index ] = item ;
length++ ;
}
33
Delete Algorithm for
SortedList ADT
find the position of the element to be
deleted from the sorted list
eliminate space occupied by the item
being deleted by shifting up all the
larger list elements
decrement length
34
Implementing SortedList
Member Function Delete
void SortedList,,Delete ( /* in */ ItemType item )
// Deletes item from list,if it is there
// Pre,0 < length <= INT_MAX/2 && item is assigned
// && data [ 0,,length-1 ] are in ascending order
// Post,IF item is in data array at entry
// First occurrence of item is no longer in array
// && length == length@entry-1
// && data [ 0,,Length-1 ] are in ascending order
// ELSE
// length and data array are unchanged
{
.
.
.
}
35
void SortedList,,Delete ( /* in */ ItemType item )
{
bool found ; // true,if item is found
int position ; // position of item,if found
int index ;
// find location of element to be deleted
BinSearch ( item,found,position) ;
if ( found )
{
// shift up elements that follow deleted item in sorted list
for ( index = position ; index < length + 1 ; index++ )
data [ index ] = data [ index + 1 ] ;
length--;
}
}
36
The reason to restrict the value of length to
INT_MAX/2 in the Delete function precondition:
The calculation
middle=(first + last) / 2;
explains why …
If length is greater than INT_MAX/2,the sum
length+length would produce an integer overflow
notice
37
Improving Member Function
IsPresent for SortedList
Recall that with the unsorted List ADT
we examined each list element beginning
with data[ 0 ],until we either found a
match with item,or we had examined all
the elements in the unsorted List.
How can the searching algorithm be
improved for SortedList ADT?
38
Searching for 55 in a
SortedList
item 55
length 4
data [ 0 ] 15
[ 1 ] 39
[ 2 ] 64
[ 3 ] 90
.
.
.
[MAX_LENGTH-1]
A sequential search
for 55 can stop when
64 has been examined,
39
Binary Search in SortedList
Examines the element in the middle of the array.
Is it the sought item? If so,stop searching,
Is the middle element too small? Then start
looking in second half of the array,
Is the middle element too large? Then begin
looking in first half of the array.
Repeat the process in the half of the data that
should be examined next.
Stop when item is found,or when there is nowhere
else to look and item has not been found.
40
void SortedList::BinSearch ( ItemType item,bool& found,int& position )
// Searches sorted list for item,returning position of item,if item was found
{
int middle ;
int first = 0;
int last = length - 1 ;
found = false ;
while ( last >= first && !found )
{ middle = ( first + last ) / 2 ; // INDEX OF MIDDLE ELEMENT
if ( item < data [ middle ] )
last = middle - 1 ; // LOOK IN FIRST HALF NEXT
else if ( item > data [ middle ] )
first = middle + 1 ; // LOOK IN SECOND HALF NEXT
else
found = true ; // ITEM HAS BEEN FOUND
}
if ( found )
position = middle ;
}
41
Trace of Binary Search
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9 ]
15 26 38 57 62 78 84 91 108 119
item = 84
first middle last
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9 ]
15 26 38 57 62 78 84 91 108 119
first middle last
item > data [ middle ] first = middle + 1
item < data [ middle ] last = middle - 1
42
Trace continued
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
15 26 38 57 62 78 84 91 108 119
item = 84
first,
last,
middle
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
15 26 38 57 62 78 84 91 108 119
first,last
middle
item == data [ middle ] found = true
item > data [ middle ] first = middle + 1
43
Another Binary Search Trace
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9 ]
15 26 38 57 62 78 84 91 108 119
item = 45
first middle last
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9 ]
15 26 38 57 62 78 84 91 108 119
first middle last
item < data [ middle ] last = middle - 1
item > data [ middle ] first = middle + 1
44
Trace continued
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
15 26 38 57 62 78 84 91 108 119
item = 45
first,
middle,
last
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
15 26 38 57 62 78 84 91 108 119
first,last
middle
item < data [ middle ] last = middle - 1
item > data [ middle ] first = middle + 1
45
Trace concludes
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9 ]
15 26 38 57 62 78 84 91 108 119
item = 45
last first
first > last found = false
46
bool SortedList,,IsPresent ( /* in */ ItemType item ) const
// Searches the list for item,reporting whether it was found
// Pre,length <= INT_MAX/2 && item is assigned
// && data [ 0,,length-1 ] are in ascending order
// Post,Function value == true,if item is in data [ 0,,length-1 ]
// == false,otherwise
{
bool found ;
int position ;
BinSearch ( item,found,position ) ;
return found ;
} 46
More Efficient IsPresent
for SortedList
47
Comparison of
Sequential and Binary Searches
Average Number of Iterations to Find item
Length Sequential Search Binary Search
10 5.5 2.9
100 50.5 5.8
1,000 500.5 9.0
10,000 5000.5 12.4
48
Order of Magnitude of a Function
The order of magnitude,or Big-O notation,
of an expression describes the complexity
of an algorithm according to the highest
order of N that appears in its complexity
expression.
49
Names of Orders of Magnitude
O(1) constant time
O(log2N) logarithmic time
O(N) linear time
O(N2) quadratic time
O(N3 ) cubic time
50
N log2N N*log2N N2
1 0 0 1
2 1 2 4
4 2 8 16
8 3 24 64
16 4 64 256
32 5 160 1024
64 6 384 4096
128 7 896 16,384
51
Big-O Comparison of List Operations
OPERATION UnsortedList SortedList
IsPresent O(N) O(N) sequential search
O(log2N) binary search
Insert O(1) O(N)
Delete O(N) O(N)
SelSort O(N2)
52
In Addition,,,
To the string class from the standard
library accessed by #include <string>
C++ also has another library of string
functions for C strings that can be
accessed by #include <cstring>
53
What is a C String?
A C string is a char array terminated by the null
character?\0? ( with ASCII value 0 ).
A C string variable can be initialized in its
declaration in two equivalent ways.
char message [ 8 ] = {?H?,?e?,?l?,?l?,?o?,?\0? };
char message [ 8 ] =,Hello” ;
message [0] [1] [2] [3] [4] [5] [6] [7]
‘ Hello\0?
54
More about initializing C Strings
Remember that array initialization is legal;
but aggregate array assignment is not.
Char myStr[20]=“Hello”; // OK
:
myStr=“How are you”; // Not allowed
55
char vs,C string
‘ A? has data type char
and is stored in 1 byte
“A” is a C string of 2 characters
and is stored in 2 bytes
5000
‘ A?
6000
‘ A?
6001
‘ \0’
56
Recall that,,,
char message[8]; // declaration allocates memory
To the compiler,the value of the identifier message
alone is the base address of the array,We say
message is a pointer (because its value is an
address),It,points” to a memory location.
message [0] [1] [2] [3] [4] [5] [6] [7]
‘ Hello\0?
6000
57
Aggregate C String I/O in C++
I/O of an entire C string is possible using
the array identifier with no subscripts
and no looping.
EXAMPLE
char message [ 8 ] ;
cin >> message ;
cout << message ;
HOWEVER,,,
58
Extraction operator >>
When using the extraction operator ( >> ) to read
input characters into a string variable,
the >> operator skips any leading whitespace
characters such as blanks and newlines
it then reads successive characters into the
array,and stops at the first trailing whitespace
character (which is not consumed,but remains
waiting in the input stream)
the >> operator adds the null character to the
end of the string
59
Example Using >>
char name [ 5 ] ;
cin >> name ;
Suppose input stream looks like this:
J o e
name [0] name [1] name [2] name [3] name [4]
7000
total number of elements in the array
null character is added
‘ Joe\0?
60
Two potential drawbacks of the >> operator
because the extraction operator stops
reading at the first trailing whitespace,
>> cannot be used to input a string with
blanks in it
if your string?s declared size is not large
enough to hold the input characters and
add the?\0?,the extraction operator
stores characters into memory beyond
the end of the array
61
Function get( )
use get function with 2 parameters to
overcome these above obstacles
EXAMPLE
char message [ 8 ] ;
cin.get ( message,8 ) ; // inputs at most 7 characters
plus ‘\0’
62
inFileStream.get ( str,count + 1)
get does not skip leading whitespace characters
such as blanks and newlines
get reads successive characters (including
blanks) into the array,and stops when it either
has read count characters,or it reaches the
newline character?\n?,whichever comes first
get appends the null character to str
if it is reached,newline is not consumed by get,
but remains waiting in the input stream
63
Function ignore( )
can be used to consume any remaining
characters up to and including the newline
‘\n’ left in the input stream by get
EXAMPLE
cin.get ( string1,81 ) ; // inputs at most 80 characters
cin.ignore ( 30,?\n? ) ; // skips at most 30 characters
// but stops if ‘\n’ is read
cin.get ( string2,81 ) ;
64
Another Example Using get( )
char ch ;
char fullName [ 31 ] ;
char address [ 31 ] ;
cout <<,Enter your full name:,;
cin.get ( fullName,31 ) ;
cin.get (ch) ; // to consume the newline
cout <<,Enter your address:,;
cin.get ( address,31 ) ;
fullName [0]
‘ NellDale\0?,,,
address [0]
‘ AustinTX\0?,,,
65
String Function Prototypes in
<cstring >
int strlen (char str [ ] );
// FCTNVAL == integer length of string str ( not including ‘\0’ )
int strcmp ( char str1 [ ],char str2 [ ] );
// FCTNVAL == negative,if str1 precedes str2 lexicographically
// == positive,if str1 follows str2 lexicographically
// == 0,if str1 and str2 characters same through ‘\0’
char * strcpy ( char toStr [ ],char fromStr [ ] );
// FCTNVAL == base address of toStr ( usually ignored )
// POSTCONDITION,characters in string fromStr are copied to
// string toStr,up to and including ‘\0’,
// overwriting contents of string toStr
66
# include <cstring >
.
.
.
char author [ 21 ] ;
int length ;
cin.get ( author,21 ) ;
length = strlen ( author ) ; // What is the value of length?
5000
author [0]
‘ ChipWeems\0?,,,,
67
char myName [ 21 ] =,Huang” ; // WHAT IS OUTPUT?
char yourName [ 21 ] ;
cout <<,Enter your last name,,;
cin.get ( yourName,21 ) ;
if ( strcmp ( myName,yourName ) == 0 )
cout <<,We have the same name!,;
else if ( strcmp ( myName,yourName ) < 0 )
cout << myName <<,comes before,<< yourName ;
else if ( strcmp ( myName,yourName ) > 0 )
cout << yourName <<,comes before,<< myName ;
myName [0]
‘ Huang\0?,,,
yourName [0]
‘ Headin gton\0?,,
.
68
char myName [ 21 ] =,Huang” ;
char yourName [ 21 ] ;
if ( myName == yourName ) // compares addresses only!
{ // That is,4000 and 6000 here.
,// DOES NOT COMPARE CONTENTS!
.
.
}
myName [0]
‘ Huang\0?,,,
yourName [0]
‘ Headin gton\0?,,
.
4000
6000
69
char myName [ 21 ] =,Huang” ;
char yourName [ 21 ] ;
cin.get ( yourName,21 ) ;
yourName = myName; // DOES NOT COMPILE!
// What is the value of myName?
myName [0]
‘ Huang\0?,,,
yourName [0]
4000
6000
‘ Headin gton\0?,,
.
70
char myName [ 21 ] =,Huang” ;
char yourName [ 21 ] ;
cin.get ( yourName,21 ) ;
strcpy ( yourName,myName ) ; // changes string yourName
// OVERWRITES CONTENTS!
myName [0]
‘ Huang\0?,,,
yourName [0]
‘ Headin gton\0?,,
.
4000
6000 ‘ ung\0?
71
Using typedef with Arrays
typedef char String20 [ 21 ] ; // names String20 as an array type
String20 myName ; // these declarations
String20 yourName ; // allocate memory for 3 variables
bool isSeniorCitizen ;
5000
7000
6000
72
Write a program that will...
Read the ID numbers,hourly wages,and
names,for up to 50 persons from a data
file.
Then display the ID number and hourly wage
for any person in the file whose name is
entered at the keyboard,or indicate that
the person was not located,if that is the
case.
73
Assume file has this form with
data for no more than 50 persons
4562 19.68 Dale Nell
1235 15.75 Weems Chip
6278 12.71 Headington Mark
.,,
.,,
.,,
8754 17.96 Cooper Sonia
2460 14.97 Huang Jeff
74
Parallel arrays hold related data
const int MAX_PERSONS = 50;
typedef char String20[ 21] ; // define data type
.
.
.
// declare 3 parallel arrays
int idNums[ MAX_PERSONS ] ;
float wages[ MAX_PERSONS ] ;
String20 names[ MAX_PERSONS ] ;
// holds up to 50 strings each with
// up to 20 characters plus null character ‘\0’
75
idNums[ 0 ] 4562 wages[ 0 ] 19.68 names[ 0 ],Dale Nell”
idNums[ 1 ] 1235 wages[ 1 ] 15.75 names[ 1 ],Weems Chip”
idNums[ 2 ] 6278 wages[ 2 ] 12.71 names[ 2 ],Headington Mark”
.,,,,,
.,,,,,
.,,,,,
idNums[ 48] 8754 wages[ 48] 17.96 names[ 48],Cooper Sonia”
idNums[ 49] 2460 wages[ 49] 14.97 names[ 49],Huang Jeff”
int idNums [ MAX_PERSONS ] ; // parallel arrays
float wages [ MAX_PERSONS ] ;
String20 names [ MAX_PERSONS ] ;
76
#include < iomanip >
#include < iostream >
#include < fstream >
#include < cctype >
#include < cstring >
using namespace std ;
typedef char String20 [ 21 ] ;
const int MAX_PERSONS = 50 ;
void GetData ( int [ ],float [ ],String20 [ ],int & ) ; // prototypes
void HandleRequests ( int [ ],float [ ],String20 [ ],int ) ;
void LookUp ( String20 [ ],String20,int,Boolean &,int & ) ;
Using Array of Strings
77
Main Program
int main ( )
{
int idNums [MAX_PERSONS] ; // holds up to 50 IDs
float wages [MAX_PERSONS] ; // holds up to 50 wages
String20 names [MAX_PERSONS] ; // holds up to 50 names
int numPersons; // number of persons’ information in file
GetData ( idNums,wages,names,numPersons ) ;
HandleRequests ( idNums,wages,names,numPersons ) ;
cout <<,End of Program.\n”;
return 0 ;
}
78
Module Structure Chart
Main
GetData
LookUp
HandleRequests
names
oneName
numPersons
idNums
wages
names
numPersons
idNums
wages
names
numPersons
found
index
79
void GetData ( /* out */ int ids[ ],/* out*/ float wages[ ],
/* out */ String20 names[ ],/* out */ int & howMany )
{ ifstream myInfile ; // Reads data from data file
int k = 0 ;
char ch ;
myInfile.open (“A:\\my.dat”) ;
if ( ! myInfile )
{ cout <<,File opening error,Program terminated!,<< endl ;
exit ( 1 ) ;
}
myInfile >> ids[ k ] >> wages [k] ; // get information for first person
myInfile.get(ch) ; // read blank
myInfile.get (names[ k ],21) ;
myInfile.ignore(30,?\n?) ; // consume newline
while (myInfile) // while the last read was successful
{ k++ ;
myInfile >> ids[ k ] >> wages [k] ;
myInfile.get(ch) ; // read blank
myInfile.get (names[ k ],21) ;
myInfile.ignore(30,?\n?) ; // consume newline
}
howMany = k;
}
80
void HandleRequests( const /* in */ int idNums[ ],const /* in */ float wages[ ],
const /* in */ String20 names[ ],/* in */ int numPersons )
{ String20 oneName ; // string to hold name of one person
int index ; // will hold an array index value
char response; // user’s response whether to continue
bool found; // has oneName been located in array names
do
{ cout <<,Enter name of person to find:,;
cin.get (oneName,21) ;
cin.ignore (100,?\n?); // consume newline
LookUp (names,oneName,numPersons,found,index );
if ( found )
cout << oneName <<,has ID #,<< idNums [index]
<<,and hourly wage $,<< wages [index] << endl;
else
cout << oneName <<,was not located.,<< endl;
cout <<,Want to find another (Y/N)?,;
cin >> response ;
response = toupper ( response );
} while ( response ==?Y? );
}
81
void LookUp ( const /* in */ String20 names [ ],
const /* in */ String20 oneName,
/* in */ int numPersons,
/* out */ bool& found,/* out */ int & index)
// Sequential search of unordered array,
// POSTCONDITION:
// IF oneName is in names array
// found == true && names[index] == oneName
// ELSE
// found == false && index == numPersons
{
index = 0;
found = false; // initialize flag
while ( ( ! found ) && ( index < numPersons ) ) // more to search
{
if ( strcmp ( oneName,names[index] ) == 0 ) // match here
found = true ; // change flag
else
index ++ ;
}
}
Applied Arrays,
Lists and Strings
2
Chapter 13 Topics
Meaning of a List
Insertion and Deletion of List Elements
Selection Sort of List Elements
Insertion and Deletion using a Sorted List
Binary Search in a Sorted List
Order of Magnitude of a Function
Declaring and Using C Strings
Using typedef with Arrays
3
What is a List?
A list is a variable-length,linear
collection of homogeneous elements.
linear means each list element (except
the first) has a unique predecessor,and
each element (except the last) has a
unique successor
4
3 Basic Kinds of ADT Operations
Constructor -- creates a new instance
(object) of an ADT
Transformer -- changes the state of one or
more of the data values of an instance
Observer -- allows us to observe the state
of one or more of the data values of an
instance without changing them
5
ADT List Operations
Transformers
Insert
Delete
SelSort
Observers
IsEmpty
IsFull
Length
IsPresent
change state
observe state
6
ADT Unsorted List
Data Components
length
data[ 0,,MAX_LENGTH -1 ]
number of
elements in list
array of list
elements
7
Array-based class List
IsFull
Length
SelSort
IsPresent
Delete
IsEmpty
Insert
Private data:
length
data [ 0 ]
[ 1 ]
[ 2 ]
[MAX_LENGTH-1]
8
// SPECIFICATION FILE ARRAY-BASED LIST ( list.h )
const int MAX_LENGTH = 50 ;
typedef int ItemType ;
class List // declares a class data type
{
public,// public member functions
List ( ) ; // constructor
bool IsEmpty ( ) const ;
bool IsFull ( ) const ;
int Length ( ) const ; // returns length of list
void Insert ( ItemType item ) ;
void Delete ( ItemType item ) ;
bool IsPresent( ItemType item ) const ;
void SelSort ( );
void Print ( ) ;
private,// private data members
int length ; // number of values currently stored
ItemType data[MAX_LENGTH] ;
} ;
9
// IMPLEMENTATION FILE ARRAY-BASED LIST ( list.cpp )
#include,list.h”
#include <iostream>
using namespace std;
int List,,Length ( ) const
// Post,Function value == length
{
return length ;
}
bool List,,IsFull ( ) const
// Post,Function value == true,if list == MAX_LENGTH
// == false,otherwise
{
return ( length == MAX_LENGTH ) ;
}
10
List,,List ( )
// Constructor
// Post,length == 0
{
length = 0 ;
}
void List,,Insert ( /* in */ ItemType item )
// Pre,length < MAX_LENGTH && item is assigned
// Post,data[length@entry] == item && length == length@entry + 1
{
data [ length ] = item ;
length++ ;
}
11
Before Inserting 64 into an
Unsorted List
length 3
data [ 0 ] 15
[ 1 ] 39
[ 2 ] -90
[ 3 ]
.
.
.
[MAX_LENGTH-1]
The item will be placed
into the length location,
and length will be
incremented.
item 64
12
After Inserting 64 into an
Unsorted List
length 4
data [ 0 ] 15
[ 1 ] 39
[ 2 ] -90
[ 3 ] 64
.
.
.
[MAX_LENGTH-1]
item 64
13
bool List,,IsEmpty ( ) const
// Post,Function value == true,if length == 0
// == false,otherwise
{
return ( length == 0 ) ;
}
bool List,,IsPresent ( /* in */ ItemType item ) const
// Searches the list for item,reporting whether it was found
// Post,Function value == true,if item is in data [ 0,,length-1 ]
// == false,otherwise
{ int index = 0 ;
while ( index < length && item != data [ index ] )
index++ ;
return ( index < length ) ;
}
14
void List,,Delete ( /* in */ ItemType item )
// Pre,length > 0 && item is assigned
// Post,IF item is in data array at entry
// First occurrence of item is no longer in array
// && length == length@entry - 1
// ELSE
// length and data array are unchanged
{ int index = 0 ;
while ( index < length && item != data [ index ] )
index++;
// if item found,move last element into item’s place
if ( index < length )
{
data [ index ] = data [length - 1 ] ;
length-- ;
}
}
15
Deleting 39 from an
Unsorted List
index,0
39 has
not been matched.
item 39
length 4
data [ 0 ] 15
[ 1 ] 39
[ 2 ] -90
[ 3 ] 64
.
.
.
[MAX_LENGTH-1]
16
Deleting 39 from an
Unsorted List
index,1
item 39
length 4
data [ 0 ] 15
[ 1 ] 39
[ 2 ] -90
[ 3 ] 64
.
.
.
[MAX_LENGTH-1]
39 has
been matched.
17
Deleting 39 from an
Unsorted List
index,1
item 39
length 4
data [ 0 ] 15
[ 1 ] 64
[ 2 ] -90
[ 3 ] 64
.
.
.
[MAX_LENGTH-1]
Placed copy of last list
element into the position
where 39 was before.
18
Deleting 39 from an
Unsorted List
index,1
item 39
length 3
data [ 0 ] 15
[ 1 ] 64
[ 2 ] -90
[ 3 ] 64
.
.
.
[MAX_LENGTH-1]
Decremented length.
19
void List,,Print ( )
// Prints the list
// Post,Contents of data [0,,length-1 ] have been output
{
int index ;
for ( index = 0 ; index < length ; index++ )
cout << data [ index ] << endl ;
}
Printing the List
20
Sorting
Arranging the components of a list
into order( for instance,words into
alphabetical order or numbers into
ascending or descending order)
21
Selection Sort Process
examines the entire list to select the smallest
element,Then places that element where it belongs
(with array subscript 0)
examines the remaining list to select the smallest
element from it,Then places that element where it
belongs (with array subscript 1)
.
.
.
examines the last 2 remaining list elements to select
the smaller one,Then places that element where it
belongs in the array
22
Selection Sort Algorithm
FOR passCount going from 0 through length - 2
Find minimum value in data [ passCount,,length-1 ]
Swap minimum value with data [ passCount ]
length = 5
data [ 0 ] 40 25
data [ 1 ] 100 100
data [ 2 ] 60 60
data [ 3 ] 25 40
data [ 4 ] 80 80
passCount
= 0
23
void List,,SelSort ( )
// Sorts list into ascending order using selection sort
{ ItemType temp ;
int passCount ;
int sIndx ;
int minIndx ; // index of minimum so far
for ( passCount = 0 ; passCount < length - 1 ; passCount++ )
{
minIndx = passCount ;
// find index of smallest of data [ passCount,,length-1 ]
for ( sIndx = passCount + 1 ; sIndx < length ; sIndx++ )
if ( data [ sIndx ] < data [ minIndx ] )
minIndx = sIndx ;
temp = data [ minIndx ] ; // swap
data [ minIndx ] = data [ passCount ] ;
data [ passCount ] = temp ;
}
}
24
Sorted and Unsorted Lists
UNSORTED LIST
Elements are placed
into the list in
no particular order.
SORTED LIST
List elements are in
an order that is
sorted in some way
-- either numerically
or alphabetically.
25
Array-based class SortedList
IsFull
Length
IsPresent
Delete
IsEmpty
Insert
Private data:
length
data [ 0 ]
[ 1 ]
[ 2 ]
[MAX_LENGTH-1]
SortedList
26
// SPECIFICATION FILE ARRAY-BASED SORTED LIST ( slist.h )
const int MAX_LENGTH = 50 ;
typedef int ItemType ;
class SortedList
{
public,// public member functions
SortedList ( ) ; // constructor
bool IsEmpty ( ) const ;
bool IsFull ( ) const ;
int Length ( ) const ; // returns length of list
void Insert ( ItemType item ) ;
void Delete ( ItemType item ) ;
bool IsPresent( ItemType item ) const ;
void Print ( ) ;
private,// private data members
int length ; // number of values currently stored
ItemType data[MAX_LENGTH] ;
void BinSearch ( ItemType item,bool& found,int& position ) const ;
} ;
27
How does the declaration of SortedList differ
from the declaration of our original List class?
There are two main differences:
The SortedList class does not supply a sorting operation
to the client,Such an operation is needless.
The SortedList class has an additional class member in
the private part,a BinSearch function,This function is
an auxiliary(“helper”) function that is used only by other
class member functions and is inaccessible to client,
We will discuss its purpose later.
28
Basic Operations of Sorted Lists
The algorithms for
the class constructor,IsEempty,IsFull,
Length and Print
are identical to those in the List class
29
Member Functions
Which member function specifications
and implementations must change to
ensure that any instance of SortedList
ADT remains sorted at all times?
Insert
Delete
30
Insert Algorithm for
SortedList ADT
create space for the new item by
shifting down all the larger list
elements
put the new item in the list
increment length
31
Implementing SortedList
Member Function Insert
// IMPLEMENTATION FILE ( slist.cpp )
void SortedList,,Insert ( /* in */ ItemType item )
// Pre,length < MAX_LENGTH && item is assigned
// && data [ 0,,length-1 ] are in ascending order
// Post,item is in the list && length == length@entry + 1
// && data [ 0,,length-1 ] are in ascending order
{
.
.
.
}
32
void SortedList,,Insert ( ItemType item )
{
int index ;
// find proper location for new element
index = length - 1 ;
// starting at bottom of array
// shift down values larger than item
// to make room for new item
while ( index >= 0 && item < data [ index ] )
{
data [ index + 1 ] = data [ index ] ;
index -- ;
}
// insert item into array
data [ index ] = item ;
length++ ;
}
33
Delete Algorithm for
SortedList ADT
find the position of the element to be
deleted from the sorted list
eliminate space occupied by the item
being deleted by shifting up all the
larger list elements
decrement length
34
Implementing SortedList
Member Function Delete
void SortedList,,Delete ( /* in */ ItemType item )
// Deletes item from list,if it is there
// Pre,0 < length <= INT_MAX/2 && item is assigned
// && data [ 0,,length-1 ] are in ascending order
// Post,IF item is in data array at entry
// First occurrence of item is no longer in array
// && length == length@entry-1
// && data [ 0,,Length-1 ] are in ascending order
// ELSE
// length and data array are unchanged
{
.
.
.
}
35
void SortedList,,Delete ( /* in */ ItemType item )
{
bool found ; // true,if item is found
int position ; // position of item,if found
int index ;
// find location of element to be deleted
BinSearch ( item,found,position) ;
if ( found )
{
// shift up elements that follow deleted item in sorted list
for ( index = position ; index < length + 1 ; index++ )
data [ index ] = data [ index + 1 ] ;
length--;
}
}
36
The reason to restrict the value of length to
INT_MAX/2 in the Delete function precondition:
The calculation
middle=(first + last) / 2;
explains why …
If length is greater than INT_MAX/2,the sum
length+length would produce an integer overflow
notice
37
Improving Member Function
IsPresent for SortedList
Recall that with the unsorted List ADT
we examined each list element beginning
with data[ 0 ],until we either found a
match with item,or we had examined all
the elements in the unsorted List.
How can the searching algorithm be
improved for SortedList ADT?
38
Searching for 55 in a
SortedList
item 55
length 4
data [ 0 ] 15
[ 1 ] 39
[ 2 ] 64
[ 3 ] 90
.
.
.
[MAX_LENGTH-1]
A sequential search
for 55 can stop when
64 has been examined,
39
Binary Search in SortedList
Examines the element in the middle of the array.
Is it the sought item? If so,stop searching,
Is the middle element too small? Then start
looking in second half of the array,
Is the middle element too large? Then begin
looking in first half of the array.
Repeat the process in the half of the data that
should be examined next.
Stop when item is found,or when there is nowhere
else to look and item has not been found.
40
void SortedList::BinSearch ( ItemType item,bool& found,int& position )
// Searches sorted list for item,returning position of item,if item was found
{
int middle ;
int first = 0;
int last = length - 1 ;
found = false ;
while ( last >= first && !found )
{ middle = ( first + last ) / 2 ; // INDEX OF MIDDLE ELEMENT
if ( item < data [ middle ] )
last = middle - 1 ; // LOOK IN FIRST HALF NEXT
else if ( item > data [ middle ] )
first = middle + 1 ; // LOOK IN SECOND HALF NEXT
else
found = true ; // ITEM HAS BEEN FOUND
}
if ( found )
position = middle ;
}
41
Trace of Binary Search
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9 ]
15 26 38 57 62 78 84 91 108 119
item = 84
first middle last
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9 ]
15 26 38 57 62 78 84 91 108 119
first middle last
item > data [ middle ] first = middle + 1
item < data [ middle ] last = middle - 1
42
Trace continued
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
15 26 38 57 62 78 84 91 108 119
item = 84
first,
last,
middle
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
15 26 38 57 62 78 84 91 108 119
first,last
middle
item == data [ middle ] found = true
item > data [ middle ] first = middle + 1
43
Another Binary Search Trace
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9 ]
15 26 38 57 62 78 84 91 108 119
item = 45
first middle last
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9 ]
15 26 38 57 62 78 84 91 108 119
first middle last
item < data [ middle ] last = middle - 1
item > data [ middle ] first = middle + 1
44
Trace continued
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
15 26 38 57 62 78 84 91 108 119
item = 45
first,
middle,
last
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
15 26 38 57 62 78 84 91 108 119
first,last
middle
item < data [ middle ] last = middle - 1
item > data [ middle ] first = middle + 1
45
Trace concludes
data[0] [1] [2] [3] [4] [5] [6] [7] [8] [9 ]
15 26 38 57 62 78 84 91 108 119
item = 45
last first
first > last found = false
46
bool SortedList,,IsPresent ( /* in */ ItemType item ) const
// Searches the list for item,reporting whether it was found
// Pre,length <= INT_MAX/2 && item is assigned
// && data [ 0,,length-1 ] are in ascending order
// Post,Function value == true,if item is in data [ 0,,length-1 ]
// == false,otherwise
{
bool found ;
int position ;
BinSearch ( item,found,position ) ;
return found ;
} 46
More Efficient IsPresent
for SortedList
47
Comparison of
Sequential and Binary Searches
Average Number of Iterations to Find item
Length Sequential Search Binary Search
10 5.5 2.9
100 50.5 5.8
1,000 500.5 9.0
10,000 5000.5 12.4
48
Order of Magnitude of a Function
The order of magnitude,or Big-O notation,
of an expression describes the complexity
of an algorithm according to the highest
order of N that appears in its complexity
expression.
49
Names of Orders of Magnitude
O(1) constant time
O(log2N) logarithmic time
O(N) linear time
O(N2) quadratic time
O(N3 ) cubic time
50
N log2N N*log2N N2
1 0 0 1
2 1 2 4
4 2 8 16
8 3 24 64
16 4 64 256
32 5 160 1024
64 6 384 4096
128 7 896 16,384
51
Big-O Comparison of List Operations
OPERATION UnsortedList SortedList
IsPresent O(N) O(N) sequential search
O(log2N) binary search
Insert O(1) O(N)
Delete O(N) O(N)
SelSort O(N2)
52
In Addition,,,
To the string class from the standard
library accessed by #include <string>
C++ also has another library of string
functions for C strings that can be
accessed by #include <cstring>
53
What is a C String?
A C string is a char array terminated by the null
character?\0? ( with ASCII value 0 ).
A C string variable can be initialized in its
declaration in two equivalent ways.
char message [ 8 ] = {?H?,?e?,?l?,?l?,?o?,?\0? };
char message [ 8 ] =,Hello” ;
message [0] [1] [2] [3] [4] [5] [6] [7]
‘ Hello\0?
54
More about initializing C Strings
Remember that array initialization is legal;
but aggregate array assignment is not.
Char myStr[20]=“Hello”; // OK
:
myStr=“How are you”; // Not allowed
55
char vs,C string
‘ A? has data type char
and is stored in 1 byte
“A” is a C string of 2 characters
and is stored in 2 bytes
5000
‘ A?
6000
‘ A?
6001
‘ \0’
56
Recall that,,,
char message[8]; // declaration allocates memory
To the compiler,the value of the identifier message
alone is the base address of the array,We say
message is a pointer (because its value is an
address),It,points” to a memory location.
message [0] [1] [2] [3] [4] [5] [6] [7]
‘ Hello\0?
6000
57
Aggregate C String I/O in C++
I/O of an entire C string is possible using
the array identifier with no subscripts
and no looping.
EXAMPLE
char message [ 8 ] ;
cin >> message ;
cout << message ;
HOWEVER,,,
58
Extraction operator >>
When using the extraction operator ( >> ) to read
input characters into a string variable,
the >> operator skips any leading whitespace
characters such as blanks and newlines
it then reads successive characters into the
array,and stops at the first trailing whitespace
character (which is not consumed,but remains
waiting in the input stream)
the >> operator adds the null character to the
end of the string
59
Example Using >>
char name [ 5 ] ;
cin >> name ;
Suppose input stream looks like this:
J o e
name [0] name [1] name [2] name [3] name [4]
7000
total number of elements in the array
null character is added
‘ Joe\0?
60
Two potential drawbacks of the >> operator
because the extraction operator stops
reading at the first trailing whitespace,
>> cannot be used to input a string with
blanks in it
if your string?s declared size is not large
enough to hold the input characters and
add the?\0?,the extraction operator
stores characters into memory beyond
the end of the array
61
Function get( )
use get function with 2 parameters to
overcome these above obstacles
EXAMPLE
char message [ 8 ] ;
cin.get ( message,8 ) ; // inputs at most 7 characters
plus ‘\0’
62
inFileStream.get ( str,count + 1)
get does not skip leading whitespace characters
such as blanks and newlines
get reads successive characters (including
blanks) into the array,and stops when it either
has read count characters,or it reaches the
newline character?\n?,whichever comes first
get appends the null character to str
if it is reached,newline is not consumed by get,
but remains waiting in the input stream
63
Function ignore( )
can be used to consume any remaining
characters up to and including the newline
‘\n’ left in the input stream by get
EXAMPLE
cin.get ( string1,81 ) ; // inputs at most 80 characters
cin.ignore ( 30,?\n? ) ; // skips at most 30 characters
// but stops if ‘\n’ is read
cin.get ( string2,81 ) ;
64
Another Example Using get( )
char ch ;
char fullName [ 31 ] ;
char address [ 31 ] ;
cout <<,Enter your full name:,;
cin.get ( fullName,31 ) ;
cin.get (ch) ; // to consume the newline
cout <<,Enter your address:,;
cin.get ( address,31 ) ;
fullName [0]
‘ NellDale\0?,,,
address [0]
‘ AustinTX\0?,,,
65
String Function Prototypes in
<cstring >
int strlen (char str [ ] );
// FCTNVAL == integer length of string str ( not including ‘\0’ )
int strcmp ( char str1 [ ],char str2 [ ] );
// FCTNVAL == negative,if str1 precedes str2 lexicographically
// == positive,if str1 follows str2 lexicographically
// == 0,if str1 and str2 characters same through ‘\0’
char * strcpy ( char toStr [ ],char fromStr [ ] );
// FCTNVAL == base address of toStr ( usually ignored )
// POSTCONDITION,characters in string fromStr are copied to
// string toStr,up to and including ‘\0’,
// overwriting contents of string toStr
66
# include <cstring >
.
.
.
char author [ 21 ] ;
int length ;
cin.get ( author,21 ) ;
length = strlen ( author ) ; // What is the value of length?
5000
author [0]
‘ ChipWeems\0?,,,,
67
char myName [ 21 ] =,Huang” ; // WHAT IS OUTPUT?
char yourName [ 21 ] ;
cout <<,Enter your last name,,;
cin.get ( yourName,21 ) ;
if ( strcmp ( myName,yourName ) == 0 )
cout <<,We have the same name!,;
else if ( strcmp ( myName,yourName ) < 0 )
cout << myName <<,comes before,<< yourName ;
else if ( strcmp ( myName,yourName ) > 0 )
cout << yourName <<,comes before,<< myName ;
myName [0]
‘ Huang\0?,,,
yourName [0]
‘ Headin gton\0?,,
.
68
char myName [ 21 ] =,Huang” ;
char yourName [ 21 ] ;
if ( myName == yourName ) // compares addresses only!
{ // That is,4000 and 6000 here.
,// DOES NOT COMPARE CONTENTS!
.
.
}
myName [0]
‘ Huang\0?,,,
yourName [0]
‘ Headin gton\0?,,
.
4000
6000
69
char myName [ 21 ] =,Huang” ;
char yourName [ 21 ] ;
cin.get ( yourName,21 ) ;
yourName = myName; // DOES NOT COMPILE!
// What is the value of myName?
myName [0]
‘ Huang\0?,,,
yourName [0]
4000
6000
‘ Headin gton\0?,,
.
70
char myName [ 21 ] =,Huang” ;
char yourName [ 21 ] ;
cin.get ( yourName,21 ) ;
strcpy ( yourName,myName ) ; // changes string yourName
// OVERWRITES CONTENTS!
myName [0]
‘ Huang\0?,,,
yourName [0]
‘ Headin gton\0?,,
.
4000
6000 ‘ ung\0?
71
Using typedef with Arrays
typedef char String20 [ 21 ] ; // names String20 as an array type
String20 myName ; // these declarations
String20 yourName ; // allocate memory for 3 variables
bool isSeniorCitizen ;
5000
7000
6000
72
Write a program that will...
Read the ID numbers,hourly wages,and
names,for up to 50 persons from a data
file.
Then display the ID number and hourly wage
for any person in the file whose name is
entered at the keyboard,or indicate that
the person was not located,if that is the
case.
73
Assume file has this form with
data for no more than 50 persons
4562 19.68 Dale Nell
1235 15.75 Weems Chip
6278 12.71 Headington Mark
.,,
.,,
.,,
8754 17.96 Cooper Sonia
2460 14.97 Huang Jeff
74
Parallel arrays hold related data
const int MAX_PERSONS = 50;
typedef char String20[ 21] ; // define data type
.
.
.
// declare 3 parallel arrays
int idNums[ MAX_PERSONS ] ;
float wages[ MAX_PERSONS ] ;
String20 names[ MAX_PERSONS ] ;
// holds up to 50 strings each with
// up to 20 characters plus null character ‘\0’
75
idNums[ 0 ] 4562 wages[ 0 ] 19.68 names[ 0 ],Dale Nell”
idNums[ 1 ] 1235 wages[ 1 ] 15.75 names[ 1 ],Weems Chip”
idNums[ 2 ] 6278 wages[ 2 ] 12.71 names[ 2 ],Headington Mark”
.,,,,,
.,,,,,
.,,,,,
idNums[ 48] 8754 wages[ 48] 17.96 names[ 48],Cooper Sonia”
idNums[ 49] 2460 wages[ 49] 14.97 names[ 49],Huang Jeff”
int idNums [ MAX_PERSONS ] ; // parallel arrays
float wages [ MAX_PERSONS ] ;
String20 names [ MAX_PERSONS ] ;
76
#include < iomanip >
#include < iostream >
#include < fstream >
#include < cctype >
#include < cstring >
using namespace std ;
typedef char String20 [ 21 ] ;
const int MAX_PERSONS = 50 ;
void GetData ( int [ ],float [ ],String20 [ ],int & ) ; // prototypes
void HandleRequests ( int [ ],float [ ],String20 [ ],int ) ;
void LookUp ( String20 [ ],String20,int,Boolean &,int & ) ;
Using Array of Strings
77
Main Program
int main ( )
{
int idNums [MAX_PERSONS] ; // holds up to 50 IDs
float wages [MAX_PERSONS] ; // holds up to 50 wages
String20 names [MAX_PERSONS] ; // holds up to 50 names
int numPersons; // number of persons’ information in file
GetData ( idNums,wages,names,numPersons ) ;
HandleRequests ( idNums,wages,names,numPersons ) ;
cout <<,End of Program.\n”;
return 0 ;
}
78
Module Structure Chart
Main
GetData
LookUp
HandleRequests
names
oneName
numPersons
idNums
wages
names
numPersons
idNums
wages
names
numPersons
found
index
79
void GetData ( /* out */ int ids[ ],/* out*/ float wages[ ],
/* out */ String20 names[ ],/* out */ int & howMany )
{ ifstream myInfile ; // Reads data from data file
int k = 0 ;
char ch ;
myInfile.open (“A:\\my.dat”) ;
if ( ! myInfile )
{ cout <<,File opening error,Program terminated!,<< endl ;
exit ( 1 ) ;
}
myInfile >> ids[ k ] >> wages [k] ; // get information for first person
myInfile.get(ch) ; // read blank
myInfile.get (names[ k ],21) ;
myInfile.ignore(30,?\n?) ; // consume newline
while (myInfile) // while the last read was successful
{ k++ ;
myInfile >> ids[ k ] >> wages [k] ;
myInfile.get(ch) ; // read blank
myInfile.get (names[ k ],21) ;
myInfile.ignore(30,?\n?) ; // consume newline
}
howMany = k;
}
80
void HandleRequests( const /* in */ int idNums[ ],const /* in */ float wages[ ],
const /* in */ String20 names[ ],/* in */ int numPersons )
{ String20 oneName ; // string to hold name of one person
int index ; // will hold an array index value
char response; // user’s response whether to continue
bool found; // has oneName been located in array names
do
{ cout <<,Enter name of person to find:,;
cin.get (oneName,21) ;
cin.ignore (100,?\n?); // consume newline
LookUp (names,oneName,numPersons,found,index );
if ( found )
cout << oneName <<,has ID #,<< idNums [index]
<<,and hourly wage $,<< wages [index] << endl;
else
cout << oneName <<,was not located.,<< endl;
cout <<,Want to find another (Y/N)?,;
cin >> response ;
response = toupper ( response );
} while ( response ==?Y? );
}
81
void LookUp ( const /* in */ String20 names [ ],
const /* in */ String20 oneName,
/* in */ int numPersons,
/* out */ bool& found,/* out */ int & index)
// Sequential search of unordered array,
// POSTCONDITION:
// IF oneName is in names array
// found == true && names[index] == oneName
// ELSE
// found == false && index == numPersons
{
index = 0;
found = false; // initialize flag
while ( ( ! found ) && ( index < numPersons ) ) // more to search
{
if ( strcmp ( oneName,names[index] ) == 0 ) // match here
found = true ; // change flag
else
index ++ ;
}
}
