Chapter 1 Arrey and String

Download as pptx, pdf, or txt
Download as pptx, pdf, or txt
You are on page 1of 49

ITec 2042

Fundamentals of Programming II

Arrays and Strings


1
October 2013
Arrays
Array
- Structures of related data items
- Static entity – same size throughout program
- Group of consecutive memory locations
- Same name and type
Referring to an element, specify
- Array name
- Position number
Format
2
type arrayName [integer value];
Arrays
Name of array (Note that
all elements of this array
have the same name, c) array c

c[0] -45 - First element at position 0


c[1] 6
c[2] 0 - n element array named c:
c[3] 72
c[4] 1543 o c[0], c[1],…c[n-1]
c[5] -89
c[6] 0
c[7] 62
c[8] -3
c[9] 1 - Array elements are like
c[10] 6453
c[11] 78 normal variables
c [8] = -3 3
Position number of the
element within array c
Declaring Arrays
When declaring arrays, specify
- Types of array
- Name of array
- Number of elements
arrayType arrayName[ numberOfElements ];
- Examples:
int c[ 10 ];
float myArray[ 3284 ];

Declaring multiple arrays of same type


- Format similar to regular variables
- Example: 4
int b[ 100 ], x[ 27 ];
Array index out of Bounds
Index of an array is in bounds if the index is
>=0 and <= ARRAY_SIZE-1
- Otherwise, the index is out of bounds
In C++, there is no guard against indices that
are out of bounds

5
Initializing Arrays
Elements in array may be initialized in two ways:
- Explicitly (using an assignment statement for
each element)
- Using a list a list is denoted using braces, with
element in the list separated by a comma.
Initializing arrays explicitly Easily accomplished
using a for loop.
- Example: Explicitly initialize all elements in an
array to 5.0
const int Asize = 100;
int A[Asize]; 6
for (int i = 0; i < Asize; i++) A[i] = 5.0;
Initializing arrays explicitly
Example: Determine the contents of each array below after the ff instructions.
const int Size = 8;
int A[Size], B[Size], C[Size], D[Size], E[Size];
for (int i = 0; i < Size; i++) A[i] = 10 + i%2*10;
for (int j = Size-1; j >=0; j--) B[j] = j*j;
for (int k = 0; k < Size; k++) A B C D E
{ C[Size-1-k] = 5*k – A[k];
if(A[k] > B[k])
D[k] = A[k];
else
D[k] = B[k];
}
for (int m = 0; m < Size/2; m++)
{ E[m] = m; 7
E[Size-1-m] = m;
}
Initializing arrays using a list
Elements in array may be initialized using a list of values
in braces.
- If not enough initializers, rightmost elements
become 0.
int n[ 5 ] = { 0 } // All elements 0
- If array size omitted, array size is set to the number of elements
in the list.
Example:
double X[4] = {1.1, 2.2, 3.3, 4.4}; // initialize array X with a list
Using the list above is equivalent to:
double X[4];
X[0] = 1.1;
X[1] = 2.2; 8
X[2] = 3.3;
X[3] = 4.4;
Example: Initializing arrays using a list
int A[5] = {11,22}; // initializes array values to 11,22,0,0,0
double Sum[7] = {0.0}; // initializes all 7 sums to 0.0
int B[ ] = {2,4,6,8}; // array B is assigned an array size of 4
char Vowels[8] = “aeiou”;// Vowels[0] = ‘a’, Vowels[1] = ‘e’, etc.
Array Array Sum Array Array Vowels
A 0 B a
11 0 2 e
22 0 4 i
0 0 6 o
0 0 8 u
0 0 \0
0 \0 9

\0 is the “null character” \0


Some Restrictions on Array Processing
Aggregate operation: any operation that
manipulates the entire array as a single
unit
- Not allowed on arrays in C++
Example:

Solution:
10
Printing Arrays
Arrays are easily printed using for loops.
Example 1:
int Grades[12]={78,80,82,84,86,88,90,92,94,96,98,100};
for (int j = 0; j < 12; j++)
cout << Grades[ j ] << endl;

Example 2:
for (int Row = 0; Row <= 2; Row++)
{
for (int Col = 0; Col <=3; Col++)
cout << Grades[ 4*Row+Col ];
11
cout << endl;
}
Printg example 1
//For loop to fill & print a 10-int
array
#include <iostream>
using namespace std;
int main ( ) {
int index, ar[10]; // array for 10
integers
// Read in 10 elements.
cout << "Enter 10 integers: ";
for(index = 0; index < 10; index ++)
cin >> ar[index];
cout << endl;
cout << "The integers are ";
for(index = 0; index < 10; index ++)
cout << ar[index] << " ";
cout << endl; 12
return 0;
}
Passing arrays to functions
Arrays are passed as parameter by reference
only
o Modifications to the array are reflected to
main program
Do not use symbol & when declaring an array
The array name is the address of the first
element
The maximum size of the array must be
specified at the time the array is declared (in
main function)
13
Passing arrays to functions
Passing arrays
- To pass an array argument, specify name of the
array without any brackets
int myArray[24];
myFunction(myArray,24);
 Array size usually passed to function
- Function knows where the array is stored
Function prototype
void modifyArray( int b[], int arraySize );
- Parameter names optional in prototype
 int b[] could be written int [] 14

 int arraySize could be simply int


Searching arrays: Linear search & Binary
Search
Sequential search (or linear search):
- Simple
- Searching a list for a given item, starting from the
first array element
- Compare each element of array with key value
being searched for
- Continue the search until item is found or no
more data is left in the list
- Useful for small and unsorted arrays
15
Searching arrays: Linear search & Binary
Search
Binary search
- For sorted arrays
- Compares middle element with key
- If equal, match found
- If key < middle, looks in first half of
array
- If key < middle, looks in last half
- Repeat
- Very fast; at most n steps, where 2n > # of elements
- 30 element array takes at most 5 steps 16

o 25 > 30 so at most 5 steps


Selection sort
Selection sort: rearrange the list by
selecting an element and moving it to its
proper position
Steps:
- Find the smallest element in the unsorted portion
of the list
- Move it to the top of the unsorted portion by
swapping with the element currently there
- Start again with the rest of the list
17
Selection sort (cont’d.)

18
Bubble sort
Bubble sort (Sinking sort)
- Several passes through the array
- Successive pairs of elements are compared
- If increasing order (or identical), no change
- If decreasing order, elements exchanged
- Repeat
Example
- Original: 3 4 2 6 7
- Pass 1: 3 2 4 6 7
- Pass 2: 2 3 4 6 7
- Small elements “bubble” to the top
19
Sorting with arrays: ex.
//Compare and sort three integers //Bubble sort
void swap (int&, int&);
int main ( ) {
int ar[3]; // input integers
// Read in three elements.
cout << "Enter three integers: ";
cin >> ar[0] >> ar[1] >> ar[2];
if (ar[0] > ar[1]) swap (ar[0], ar[1]);
if (ar[1] > ar[2]) swap (ar[1], ar[2]);
if (ar[0] > ar[1]) swap (ar[0], ar[1]);
cout << "The sorted integers are " << ar[0]
<<", " << ar[1] << ", " << ar[2]
<< endl;
return 0;
}
void swap (int& first, int& second) {
int temp;
temp = first; 20
first = second;
second = temp; }
Strings (Character arrays)
Char is a one-byte data type capable of holding a character
Character constants
- 'a', 'b', …'z', '0', … '9', '+', '-', '=', '!',
'~', '\n', '\t', '\0', etc.
String: is a character array ending in '\0' — i.e.,
- char s[256];
- char t[] = "This is an initialized string!";

String constants are in double quotes


- May contain any characters
Requires #include <string>
Example:
- 'A' is the character A 21
- "A" is the string A
- "A" represents two characters, 'A' and '\0‘
Strings (cont’d.)
Size of an array can be omitted if the array is
initialized during declaration
Example:
- char name[] = “Getachew";
- Declares an array of length 5 and stores the
C++ string “Getachew” in it
Useful string manipulation functions
- Strcpy, strcmp, and strlen

22
Initializing a string
To initialize a string during declaration:
char my_message[20] = "Hi there.";
- The null character '\0' is added
Another alternative:
char short_string[ ] = "abc";
but not this:
char short_string[ ] = {'a', 'b', 'c'};
This attempt to initialize a string does not
cause the \0 to be inserted in the array 23

• char short_string[]= {'a', 'b', 'c'};


String comparison
== operator does not work
compared character by character
- Use the predefined function strcmp
- strcmp(string1,string2);
If the two strings are the same, strcmp returns 0
- 0 is interpreted as false
If using the ASCII character set:
- “Air” < “Boat”
- “Air” < “An”
- “Bin” < “Bini” 24

- “Hello” < “hello”


String copy
strncpy - uses a third argument representing
the maximum # of character to copy.
Example: char another_string[10];
strncpy(another_string,
a_string_variable, 9);
This code copies up to 9 characters into
another_string, leaving one space for '\0'

25
More functions
strlen – returns the number of characters in
a string
int x = strlen( a_string);
strcat – concatenates two string
• The second argument is added to the end of
the first
• The result is placed in the first argument
• Example:
char string_var[20] = "The rain";
strcat(string_var, "in Spain");
26

Now string_var contains "The rainin Spain"


Reading and Writing String
String Input:
- cin>>name; stores the next input string
in name
- String that contain blanks cannot be read
using the extraction operator >>
- Whitespace ends reading of data
- Example:
char a[80], b[80];
cout << "Enter input: " << endl;
cin >> a >> b; 27

cout << a << b << "End of Output";


Reading and Writing String
- could produce:
Enter input:
Hey welcome student!
HeywelcomeEnd of Output
To read strings with blanks, use the predefined
member getline function, syntax
cin.getline(str,m+1); 2 arguments
• The first variable str receives input
• 2nd is an integer m , usually the size of the
first argument specifying the maximum # 28
of elements
Reading and Writing String
The ff code is used to read an entire line
including spaces into a single variable
char a[80];
cout<<"Enter input:\n";
cin.getline(a, 80);
cout << a << End Of Output\n";
and could produce:
Enter some input:
Do be do to you!
Do be do to you!End of Output
29
(continued)
String Output:
- cout<<name; outputs the content of
name on the screen
- The insertion operate << continues to write
the contents of name until it finds the null
character
• If name does not contain the null
character, then we will see strange output:
• << continues to output data from memory
adjacent to name until ‘\0’ is found 30
Multi-Dimensional Arrays
So far we have used one-dimensional (1D) arrays,
nextly arrays with 2 (2D) or more dimensions.
2D arrays essentially correspond to matrices.
Examples:
int A; // single variable
int B[6]; // 1D array
int C[3][4]; // 2D array (matrix)
int D[3][4][5]; // 3D array
int E[3][4][5][3]; // 4D array
//etc 31
Visualizing multi-dimensional arrays
1D – single row or column
2D – matrix
3D – cube of cells
4D – row or column of cubes
Example:
int A, B1[6], B2[6], C[3][4], D[3][4][5], E[3][4][5][3];
A B1 C D E

32

B2
Two-dimensional array
Two-dimensional array: collection of a fixed
number of components (of the same type)
arranged in two dimension
- Sometimes called matrices or tables
Declaration syntax:

- intExp1 and intExp2 are expressions with


positive integer values specifying the number of 33
rows and columns in the array
Two-dimensional array
- Tables with rows and columns (m by n array)
- A 2D array is typically represented as a matrix
Example:
int a[3][3]; // 2D array (matrix) with 3 rows and 3 columns
Column 0 Column 1 Column 2 Column 3

Row 0 a[ 0 ][ 0 ] a[ 0 ][ 1 ] a[ 0 ][ 2 ] a[ 0 ][ 3 ]
Row 1 a[ 1 ][ 0 ] a[ 1 ][ 1 ] a[ 1 ][ 2 ] a[ 1 ][ 3 ]
Row 2
a[ 2 ][ 0 ] a[ 2 ][ 1 ] a[ 2 ][ 2 ] a[ 2 ][ 3 ]

Column subscript
Array name 34
Row subscript
Two-dimensional array

Initialization
- int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } }; 1 2

- Initializers grouped by row in braces 3 4

- If not enough, unspecified elements set to zero


int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } };
1 0

Referencing elements 3 4

- Specify row, then column


cout << b[ 0 ][ 1 ];

35
Initialization Example:

- To initialize row number 4 (fifth row) to 0:

- To initialize the entire matrix to 0:

36
Accessing array components
Accessing components in a two-dimensional
array:

- Where indexExp1 and indexExp2 are


expressions with positive integer values, and
specify the row and column position
Example:

sales[5][3] = 25.75;
37
Accessing array components (cont’d.)

38
Input
Example:
- To input into row number 4 (fifth row):

- To input data into each component of


matrix:

39
Print
Use a nested loop to output the components of
a two dimensional array:

40
Example: Sum
By raw- to find the sum of row number 4:

By column- to find the sum of each individual


column :

41
Large elements in each Row & each Column
Example:
- To find the largest element in each row:

42
Arrays of Strings
Strings in C++ can be manipulated using
either the data type string or
character arrays (C-strings)
On some compilers, the data type
string may not be available

43
Arrays of Strings & string Type
To declare an array of 100 components of type
string:
string list[100];
Basic operations, such as assignment,
comparison, and input/output can be
performed on values of the string type
The data in list can be processed just like
any one-dimensional array

44
Arrays of Strings & C-string (Character arrays)

45
Summary
Array: structured data type with a fixed
number of components of the same type
- Components are accessed using their
relative positions in the array
Elements of a one-dimensional array are
arranged in the form of a list
An array index can be any expression that
evaluates to a nonnegative integer
- Must always be less than the size of the array 46
Summary (cont’d.)
The base address of an array is the address of
the first array component
When passing an array as an actual parameter,
use only its name
- Passed by reference only
A function cannot return an array type value
Strings are null terminated and are stored in
character arrays

47
Summary (cont’d.)
Commonly used string manipulation functions:
strcpy, strcmp, and strlen
Parallel arrays are used to hold related information
In a two-dimensional array, the elements are arranged
in a table form
To access an element of a two-dimensional array, you
need a pair of indices:
- One for row position, one for column position
In row processing, a two-dimensional array is
processed one row a time
In column processing, a two-dimensional array is 48
processed one column a time
Thank You !!!
Any Questions
??
49

You might also like