Computer science c++

ivan5095

ch7.ppt

Home >Computer Science homework help >Computer science c++

Chapter 7

Arrays

Overview

7.1 Introduction to Arrays

7.2 Arrays in Functions

7.3 Programming with Arrays

7.4 Multidimensional Arrays

Slide 7- *

7.1

Introduction to Arrays

An array is used to process a collection of data
of the same type
Examples: A list of names
A list of temperatures
Why do we need arrays?
Imagine keeping track of 5 test scores, or 100, or 1000 in memory
How would you name all the variables?
How would you process each of the variables?

Slide 7- *

Declaring an Array

An array, named score, containing five variables
of type int can be declared as
int score[ 5 ];
This is like declaring 5 variables of type int:
score[0], score[1], … , score[4]
The value in brackets is called
A subscript
An index

Slide 7- *

The Array Variables

The variables making up the array are referred to
as
Indexed variables
Subscripted variables
Elements of the array
The number of indexed variables in an array is
the declared size, or size, of the array
The largest index is one less than the size
The first index value is zero

Slide 7- *

Array Variable Types

An array can have indexed variables of any type
All indexed variables in an array are of the
same type
This is the base type of the array
An indexed variable can be used anywhere an
ordinary variable of the base type is used

Slide 7- *

Using [ ] With Arrays

In an array declaration, [ ]'s enclose the size
of the array such as this array of 5 integers:
int score [5];
When referring to one of the indexed variables,
the [ ]'s enclose a number identifying one of
the indexed variables
score[3] is one of the indexed variables
The value in the [ ]'s can be any expression that evaluates to one of the integers 0 to (size -1)

Slide 7- *

Indexed Variable Assignment

To assign a value to an indexed variable, use
the assignment operator:

int n = 2;
score[n + 1] = 99;
In this example, variable score[3] is assigned 99

Slide 7- *

Loops And Arrays

for-loops are commonly used to step through
arrays
Example: for (i = 0; i < 5; i++)
{
cout << score[i] << " off by "
<< (max – score[i]) << endl;
}
could display the difference between each score and the maximum score stored in an array

Slide 7- *

First index is 0

Display 7.1

Last index is (size – 1)

Display 7.1

Slide 7- *

Back

Constants and Arrays

Use constants to declare the size of an array
Using a constant allows your code to be easily
altered for use on a smaller or larger set of data
Example: const int NUMBER_OF_STUDENTS = 50;
int score[NUMBER_OF_STUDENTS];
…
for ( i = 0; i < NUMBER_OF_STUDENTS; i++)
cout << score[i] << " off by "
<< (max – score[i]) << endl;
Only the value of the constant must be changed to make this code work for any number of students

Slide 7- *

Variables and Declarations

Most compilers do not allow the use of a variable
to declare the size of an array

Example: cout << "Enter number of students: ";
cin >> number;
int score[number];
This code is illegal on many compilers

Slide 7- *

Array Declaration Syntax

To declare an array, use the syntax:
Type_Name Array_Name[Declared_Size];
Type_Name can be any type
Declared_Size can be a constant to make your
program more versatile
Once declared, the array consists of the indexed
variables:
Array_Name[0] to Array_Name[Declared_Size -1]

Slide 7- *

Computer Memory

Computer memory consists of numbered
locations called bytes
A byte's number is its address
A simple variable is stored in consecutive bytes
The number of bytes depends on the variable's type
A variable's address is the address of its first byte

Slide 7- *

Arrays and Memory

Declaring the array int a[6]
Reserves memory for six variables of type int
The variables are stored one after another
The address of a[0] is remembered
The addresses of the other indexed variables is not
remembered
To determine the address of a[3]
Start at a[0]
Count past enough memory for three integers to find a[3]

Slide 7- *

Display 7.2

Slide 7- *

Back

Array Index Out of Range

A common error is using a nonexistent index
Index values for int a[6] are the values 0 through 5
An index value not allowed by the array declaration is out of range
Using an out of range index value doe not produce an error message!

Slide 7- *

Out of Range Problems

If an array is declared as: int a[6];
and an integer is declared as: int i = 7;
Executing the statement a[i] = 238; causes…
The computer to calculate the address of the illegal a[7]
(This address could be where some other variable is stored)
The value 238 is stored at the address calculated for a[7]
No warning is given!

Slide 7- *

Initializing Arrays

To initialize an array when it is declared
The values for the indexed variables are enclosed in braces and separated by commas
Example: int children[3] = { 2, 12, 1 };
Is equivalent to:
int children[3];
children[0] = 2;
children[1] = 12;
children[2] = 1;

Slide 7- *

Default Values

If too few values are listed in an initialization
statement
The listed values are used to initialize the first of the indexed variables
The remaining indexed variables are initialized to a zero of the base type
Example: int a[10] = {5, 5};
initializes a[0] and a[1] to 5 and
a[2] through a[9] to 0

Slide 7- *

Un-initialized Arrays

If no values are listed in the array declaration,
some compilers will initialize each variable to a
zero of the base type
DO NOT DEPEND ON THIS!

Slide 7- *

Section 7.1 Conclusion

Can you
Describe the difference between a[4] and

int a[5]?

Show the output of

char symbol[3] = {'a', 'b', 'c'};
for (int index = 0; index < 3; index++)
cout << symbol[index];

Slide 7- *

7.2

Arrays in Functions

Indexed variables can be arguments to functions
Example: If a program contains these declarations:
int i, n, a[10];
void my_function(int n);
Variables a[0] through a[9] are of type int, making these calls legal:
my_function( a[ 0 ] );
my_function( a[ 3 ] );
my_function( a[ i ] );

Slide 7- *

Display 7.3

Slide 7- *

Back

Arrays as Function Arguments

A formal parameter can be for an entire array
Such a parameter is called an array parameter
It is not a call-by-value parameter
It is not a call-by-reference parameter
Array parameters behave much like call-by-reference parameters

Slide 7- *

Array Parameter Declaration

An array parameter is indicated using empty
brackets in the parameter list such as

void fill_up(int a[ ], int size);

Slide 7- *

Function Calls With Arrays

If function fill_up is declared in this way:
void fill_up(int a[ ], int size);
and array score is declared this way:
int score[5], number_of_scores;
fill_up is called in this way:
fill_up(score, number_of_scores);

Slide 7- *

Display 7.4

Slide 7- *

Back

Function Call Details

A formal parameter is identified as an array
parameter by the [ ]'s with no index expression

void fill_up(int a[ ], int size);
An array argument does not use the [ ]'s

fill_up(score, number_of_scores);

Slide 7- *

Array Formal Parameters

An array formal parameter is a placeholder for
the argument
When an array is an argument in a function call, an action performed on the array parameter is performed on the array argument
The values of the indexed variables can be changed by the function

Slide 7- *

Array Argument Details

What does the computer know about an array?
The base type
The address of the first indexed variable
The number of indexed variables
What does a function know about an array
argument?
The base type
The address of the first indexed variable

Slide 7- *

Array Parameter Considerations

Because a function does not know the size of
an array argument…
The programmer should include a formal parameter that specifies the size of the array
The function can process arrays of various sizes
Function fill_up from Display 7.4 can be used to fill
an array of any size:

fill_up(score, 5);
fill_up(time, 10);

Slide 7- *

const Modifier

Array parameters allow a function to change the
values stored in the array argument
If a function should not change the values of the
array argument, use the modifier const
An array parameter modified with const is a
constant array parameter
Example:
void show_the_world(const int a[ ], int size);

Slide 7- *

Using const With Arrays

If const is used to modify an array parameter:
const is used in both the function declaration and definition to modify the array parameter
The compiler will issue an error if you write code that changes the values stored in the array parameter

Slide 7- *

Function Calls and const

If a function with a constant array parameter
calls another function using the const array
parameter as an argument…
The called function must use a constant
array parameter as a placeholder for the array
The compiler will issue an error if a function is
called that does not have a const array parameter to accept the array argument

Slide 7- *

const Parameters Example

double compute_average(int a[ ], int size);

void show_difference(const int a[ ], int size)
{
double average = compute_average(a, size);
…
}
compute_average has no constant array parameter
This code generates an error message because
compute_average could change the array parameter

Slide 7- *

Returning An Array

Recall that functions can return a value of
type int, double, char, …, or a class type
Functions cannot return arrays
We learn later how to return a pointer to an array

Slide 7- *

Case Study:
Production Graph

Problem Definition:
We are writing a program for the Apex Plastic
Spoon Company
The program will display a bar graph showing the production of each of four plants for a week
Each plant has separate records for each department
Input is entered plant by plant
Output shows one asterisk for each 1000 units, and production is rounded to the nearest 1,000 units

Slide 7- *

Analysis of The Problem

Use an array named production to hold total
production of each plant
Production for plant n is stored in production[n-1]
Program must scale production to nearest
1,000 units to display asterisks in the bar

Slide 7- *

Production Graph Sub-Tasks

Analysis leads to the following sub-tasks
input_data: Read input for each plant
Set production [plant_number -1]

to the total production for plant

number n

scale: For each plant, change production[plant_number]
to the correct number of asterisks
graph: Output the bar graph

Slide 7- *

More Analysis Details

The entire array will be an argument for the
functions we write to perform the subtasks
We will also include a formal parameter for the size
The size of the array is equal to the number of plants
We will use a constant for the number of plants

The function declarations and main function
for the production graph program are found in

Slide 7- *

Display 7.5

Slide 7- *

Back

Algorithm Design: input_data

We must read all departments' data for each
plant and add them to produce a plant's total
Algorithm for input_data:
for plant_number is 1, 2, …, last_plant_number

do the following
Read all the data for plant number plant_number
Sum the numbers
Set production[plant_number – 1] to the total

Slide 7- *

Coding input_data

The algorithm can be translated to C++ as:
void input_data(int a [ ], int last_plant_number)
{
using namespace std;

for (int plant_number = 1;
plant_number <= last_plant_number;
plant_number++)
{
cout << endl
<< "Enter production for plant"
<< plant_number << endl;
get_total( a[plant_number -1] );
}
}

Slide 7- *

Testing input_data

Each function should be tested in a program in
which it is the only untested function
Because input_data calls get_total, get_total
is tested first
Once tested, get_total can be used to test
input_data

Slide 7- *

Display 7.6 (1)

Display 7.6 (2)

Display 7.6 (3)

Display 7.6 (1/3)

Slide 7- *

Back

Display 7.6 (2/3)

Slide 7- *

Back

Display 7.6 (3/3)

Slide 7- *

Back

Test Data for input_data

Remember that input_data should be tested
With a plant that contains no production figures
With a plant having only one production figure
With a plant having more than one figure
With zero and non-zero production figures

Slide 7- *

Algorithm for scale

scale changes the value of the indexed variable
to show the whole number of asterisks to print
Scale is called using
scale (production, NUMBER_OF_PLANTS);

and its algorithm is
for (int index = 0; index < size; index++)
Divide the value of a[index] by 1,000 and round the result to the nearest integer

Slide 7- *

Coding scale

The code for scale, below, uses a function named
round that must be defined as well
void scale(int a[ ], int size)
{
for (int index = 0; index < size; index++)
a[index] = round (a[index] / 1000.0);
}

Slide 7- *

Why not 1000?

Function floor

Function round, called by scale, uses the floor
function from the cmath library
The floor function returns the first whole number less than its argument:
floor (3.4) returns 3
floor (3.9) returns 3
Adding 0.5 to the argument for floor is how round performs its task
floor (3.4 + 0.5) returns 3
floor (3.9 + 0.5) returns 4

Slide 7- *

Testing scale

To test scale
First test round
Scale should be tested with arguments that
Are 0
Round up
Round down

Slide 7- *

Display 7.7 (1)

Display 7.7 (2)

Display 7.7 (1/2)

Slide 7- *

Back

Display 7.7
(2/2)

Slide 7- *

Back

Function graph

The design of graph is quite straightforward
and not included here
The complete program to produce the bar
graph is found in

Slide 7- *

Display 7.8 (1)

Display 7.8 (2)

Display 7.8 (3)

Display 7.8 (4)

Display 7.8
(1/4)

Slide 7- *

Back

Display 7.8 (2/4)

Slide 7- *

Back

Display 7.8 (3/4)

Slide 7- *

Back

Display 7.8
(4/4)

Slide 7- *

Back

Section 7.2 Conclusion

Can you
Write a function definition for a function called
one_more, which has a formal parameter for an array of integers and increases the value of each array element by one. Are other formal parameters needed?

Slide 7- *

7.3

Programming with Arrays

Programming With Arrays

The size needed for an array is changeable
Often varies from one run of a program to another
Is often not known when the program is written
A common solution to the size problem
Declare the array size to be the largest that could be needed
Decide how to deal with partially filled arrays

Slide 7- *

Partially Filled Arrays

When using arrays that are partially filled
Functions dealing with the array may not need to know the declared size of the array, only how many elements are stored in the array
A parameter, number_used, may be sufficient to ensure that referenced index values are legal
A function such as fill_array in Display 7.9 needs to know the declared size of the array

Slide 7- *

Display 7.9 (1)

Display 7.9 (2)

Display 7.9 (3)

Display 7.9 (1/3)

Slide 7- *

Back

Display 7.9 (2/3)

Slide 7- *

Back

Display 7.9
(3/3)

Slide 7- *

Back

Constants as Arguments

When function fill_array (Display 7.9) is called,
MAX_NUMBER_SCORES is used as an
argument
Can't MAX_NUMBER_SCORES be used directly without making it an argument?
Using MAX_NUMBER_SCORES as an argument makes it clear that fill_array requires the array's declared size
This makes fill_array easier to be used in other programs

Slide 7- *

Searching Arrays

A sequential search is one way to search
an array for a given value
Look at each element from first to last to see if the target value is equal to any of the array elements
The index of the target value can be returned to indicate where the value was found in the array
A value of -1 can be returned if the value was not found

Slide 7- *

The search Function

The search function of Display 7.10…
Uses a while loop to compare array elements to the target value
Sets a variable of type bool to true if the target
value is found, ending the loop
Checks the boolean variable when the loop ends to see if the target value was found
Returns the index of the target value if found,
otherwise returns -1

Slide 7- *

Display 7.10 (1)

Display 7.10 (2)

Display 7.10 (1/2)

Slide 7- *

Back

Display 7.10 (2/2)

Slide 7- *

Back

Program Example:
Sorting an Array

Sorting a list of values is very common task
Create an alphabetical listing
Create a list of values in ascending order
Create a list of values in descending order
Many sorting algorithms exist
Some are very efficient
Some are easier to understand

Slide 7- *

Program Example:
The Selection Sort Algorithm

When the sort is complete, the elements of the
array are ordered such that

a[0] < a[1] < … < a [ number_used -1]
This leads to an outline of an algorithm:
for (int index = 0; index < number_used; index++)
place the indexth smallest element in a[index]

Slide 7- *

Program Example:
Sort Algorithm Development

One array is sufficient to do our sorting
Search for the smallest value in the array
Place this value in a[0], and place the value that was in a[0] in the location where the smallest was found
Starting at a[1], find the smallest remaining value swap it with the value currently in a[1]
Starting at a[2], continue the process until the array is sorted

Slide 7- *

Display 7.11

Display 7.12 (1-2)

Display 7.11

Slide 7- *

Back

Display 7.12 (1/2)

Slide 7- *

Back

Display 7.12 (2/2)

Slide 7- *

Back

Section 7.3 Conclusion

Can you
Write a program that will read up to 10 letters into an array and write the letters back to the screen in the reverse order?

abcd should be output as dcba

Use a period as a sentinel value to mark the end of input

Slide 7- *

7.4

Multidimensional Arrays

Multi-Dimensional Arrays

C++ allows arrays with multiple index values
char page [30] [100];
declares an array of characters named page
page has two index values:
The first ranges from 0 to 29
The second ranges from 0 to 99
Each index in enclosed in its own brackets
Page can be visualized as an array of
30 rows and 100 columns

Slide 7- *

Index Values of page

The indexed variables for array page are
page[0][0], page[0][1], …, page[0][99]
page[1][0], page[1][1], …, page[1][99]
…
page[29][0], page[29][1], … , page[29][99]
page is actually an array of size 30
page's base type is an array of 100 characters

Slide 7- *

Multidimensional Array Parameters

Recall that the size of an array is not needed
when declaring a formal parameter:
void display_line(const char a[ ], int size);
The base type of a multi-dimensional array must
be completely specified in the parameter
declaration
void display_page(const char page[ ] [100],
int size_dimension_1);

Slide 7- *

Program Example:
Grading Program

Grade records for a class can be stored in a
two-dimensional array
For a class with 4 students and 3 quizzes the array could be declared as

int grade[4][3];
The first array index refers to the number of a student
The second array index refers to a quiz number
Since student and quiz numbers start with one,
we subtract one to obtain the correct index

Slide 7- *

Grading Program:
average scores

The grading program uses one-dimensional
arrays to store…
Each student's average score
Each quiz's average score
The functions that calculate these averages
use global constants for the size of the arrays
This was done because the functions seem to be
particular to this program

Slide 7- *

Display 7.13 (1-3)

Display 7.14

Display 7.15

Display 7.13 (1/3)

Slide 7- *

Back

Display 7.13 (2/3)

Slide 7- *

Back

Display 7.13 (3/3)

Slide 7- *

Back

Display 7.14

Slide 7- *

Back

Display 7.15

Slide 7- *

Back

Section 7.5 Conclusion

Can you
Write code that will fill the array a(declared below) with numbers typed at the keyboard? The numbers will be input fiver per line, on four lines.

int a[4][5];

Slide 7- *

Chapter 7 - End

Slide 7- *