CSC 2105 Data Structures
Lecture 1: Array
The first Data Structure - An Array!
• Lets Get Started:
• Arrays are data structures
– Finite
– Contiguous
– Fast
– Direct Access
– All elements of same data type
• (Can be based upon primitive or ADT)
– Insertion / Deletion ??? HOW??
Arrays
• How to Input arrays
• How to process arrays
• How to insert an item in an array
• How to delete an item from an array
• How to pass an array
An Array!
An array in C / C++ is a collection of related data elements of
the same type that are referenced by a common name and
stored in a contiguous memory location.
The simplest form of an Array is a one dimensional array that
may be defined as a finite ordered set of homogenous
elements.
a 3 7 5 9 4 1 . . 2
For Example 0 1 2 . . . . . 99
int a[100];
This will reserve 100 contiguous/sequential memory locations
4
Why Array?
If we have 100 marks to be stored, by using normal variable declaration
we will declare it as follows:
int mark1, mark2, mark3, ..., mark100;
By using an array, we just declare like this:
int mark[100];
This will reserve 100 contiguous/sequential memory locations as follows:
One Dimensional Array: Declaration
A single dimensional array declaration has the following form:
data_type array_name[array_size];
Here,
data_type : declares the data type of each element.
array_name is any valid C / C++ identifier, defines the common
name that use as a reference of the elements.
array_size defines how many elements the array will hold/store.
Examples of the one-dimensional array declarations:
int x[20], y[50];
float price[10], yield;
char letter[70]; 6
Array Initialization
▪In line initialization of an array may takes the
following form:
type array_name[size] = {element_list};
▪For example:
int id[7] = {1, 2, 3, 4, 5, 6, 7};
float x[5] = {5.6, 5.7, 5.8, 5.9, 6.1};
char vowel[6] = {'a', 'e', 'i', 'o', 'u', ‘\0'};
The first line declares an integer array id and it immediately assigns the values
1, 2, 3, ..., 7 to id[0], id[1], id[2],..., id[6].
In the second line assigns the values 5.6 to x[0], 5.7 to x[1], and so on.
Similarly the third line assigns the characters ‘a’ to vowel[0], ‘e’ to vowel[1],
and so on. Note again, for characters we must use the single apostrophe (’) to
enclose them. Also, the last character in the array vowel is the NULL character
(‘\0’).
Initializing With a String
• Character array can be initialized by a string, adding
character-by-character, must add ‘\0’ explicitly at the
end.
char fName[6] =
{'H', 'e', 'n', 'r', 'y', '\0'};
Character array (Strings)
Review char A[5] ;
A[0] A
A[1] L
A L I \0 A[2] I
A[3] \0
A[4] Garbage
Partial Array Initialization
• If array is initialized with fewer initial values
than the size declarator, the remaining
elements will be set to 0:
Implicit Array Sizing
• Can determine array size by the size of the
initialization list:
int quizzes[]={12,17,15,11};
12 17 15 11
• Must use either array size declaratory or
initialization list at array definition
Basic Operations
Data Extraction
A function that accepts an array “a” and an index
“i”, and returns an element of the array.
Example
a[i]
Data Storing
It accepts array “a” an index “i” and an element x.
Example
a[i]=x
Accessing Array Elements
• Arrays must be accessed via individual elements:
cout << tests; // not legal
• Array elements can be used as regular variables:
tests[0] = 79;
cout << tests[0];
cin >> tests[1];
tests[4] = tests[0] + tests[1];
Memory view of an array
int a[5] 2 3 4 7 8
//Help me give output of this
program
a[0] 2 0x4
void main(void) a[1] 3
{ 0x8
a[2] 4 0xC
int a[5] = { 2,3,4,7,8 }; a[3] 7 0x10
cout << a[3] << endl;
cout << a <<endl; a[4] 8 0x14
cout << *(a+1) <<endl;
cout << *a+1 <<endl;
}
Storing data into an Array
int ARRAY_SIZE = 5;
int tests[ARRAY_SIZE] = {2,3,4,7,8};
OR
•Store element-by-element into array:
for (i = 0; i < ARRAY_SIZE; i++)
cin >> tests[i];
Data Extraction:
Printing the Contents of an Array
int tests[ARRAY_SIZE] = {5,7,3,4,9,2,1};
•Array elements print element-by-element:
for (i = 0; i < ARRAY_SIZE; i++)
cout << tests[i] << endl;
*a +1 without brackets leads to adding 1 to
contents (value) of a[0]
Array
2 3 7 8
How to add 4
2 3 4 7 8
How to add 1 in the array?
Not possible
Implementing Operations
• Insertion
– At the beginning
– At the middle (or a fixed location)
– At the end
• Deletion
– Starting item
– Middle item (or a fixed item)
– last item
Insertion Operations
int array[10]={21,25,27,33,44};
int n = 5;
// last index = n-1 = 4
21 25 27 33 44
0 1 2 3 4 (n-1) S-1
1. Add a new item=71 at the end (i = last+1 or i=n)
21 25 27 33 44 71
0 1 2 3 4 i S-1
array[n] = item;
//Num of item and last subscript need to increase by one
n++;
2. Add a new item=71 at the kth location (i = k = 2)
21 25 27 33 44
0 1 2 3 4 (n-1) S-1
First we need to do right shift of data from last location to kth
location then we will insert new item at kth location.
for(i = n-1; i > = k ; i--)
array[i+1] = array[i];
21 25 27 33 44
0 1 k=2 3 4 5 S-1
array[ k ] = item;
//Num of item and last subscript need to increase by one
n++;
21 25 71 27 33 44
0 1 2 3 4 5 S-1
3. Add a new item = 71 at the beginning (i=0)
21 25 27 33 44
0 1 2 3 4 (n-1) S-1
First we need to do right shift of data from 1st location to last
location then we will insert new item at 1st location.
for(i=n-1; i >= 0; i--)
array[i+1] = array[i];
22 25 27 33 44
0 1 2 3 4 5 n-1
array[0] = item;
//Num of item and last subscript need to increase by one
n++;
71 22 25 27 33 44
0 1 2 3 4 5 n-1
Delete Operations
int array[10]={2,5,7,3,4};
2 5 7 3 4
1. Delete last item
2 5 7 3
0 1 2 3 4 5 n-1
array[last] = NULL;
2. Delete kth location item (k = 2)
2 5 3 4
0 1 2 3 4 5 n-1
2 5 3 4
0 1 2 3 4 5 n-1
for(i=k; i<last; i++)
array[i] = array[i+1];
No of item and last subscript need to decrease by one
n--;
Delete Operations
int array[10]={2,5,7,3,4};
2 5 7 3 4
3. Delete 1st item
5 7 3 4
0 1 2 3 4 5 n-1
5 7 3 4
0 1 2 3 4 5 n-1
for(i=0; i<n-1; i++)
array[i] = array[i+1];
No of item and last subscript need to decrease by one
n--;
Using Parallel Arrays
• Parallel arrays: two or more arrays that
contain related data but different types and
• A single subscript is used to relate arrays:
elements at same subscript are related
Parallel Array Example
const int SIZE = 5; // Array size
int id[SIZE]; // student ID
double average[SIZE]; //course average
char grade[SIZE]; // course grade
for(int i = 0; i < SIZE; i++)
{
cout << "Student ID: " << id[i]
<< " average: " << average[i]
<< " grade: " << grade[i]
<< endl;
}
Two-Dimensional Array
• Some data fit better in a table with several rows and
columns.
• This can be constructed by using two-dimensional arrays
using two subscripts/indices. The first refers to the row, and
the second, to the column.
datatype array_name[1st dimn size][2nd dimn size];
Example
const int ROWS = 4, COLS = 3;
int exams[ROWS][COLS];
Two-Dimensional Array Representation
const int ROWS = 4, COLS = 3;
int exams[ROWS][COLS];
columns
exams[0][0] exams[0][1] exams[0][2]
r exams[1][0] exams[1][1] exams[1][2]
o
w exams[2][0] exams[2][1] exams[2][2]
s
exams[3][0] exams[3][1] exams[3][2]
• Use two subscripts to access element:
exams[2][2] = 86;
2D Array Initialization
• Two-dimensional arrays are initialized row-by-row:
const int ROWS = 2, COLS = 2;
int exams[ROWS][COLS] = { {84, 78},{92, 97} };
84 78
92 97
• Can omit inner { }, some initial values in a row –
array elements without initial values will be set to 0
or NULL
Example of Strings Array
columns
S a l l y \0
r
o J o y c e \0
w L i s a \0
s
A l i c e \0
char name[4][10] = {"Sally", "Joyce", "Lisa", "Alice"};
string name[4];
name[0] = "Sally" name[1] = "Joyce"
name[2] = "Lisa" name[3] = "Alice"
30
Arrays with Three or More Dimensions
• Can define arrays with any number of dimensions by
using same number indices/subscripts:
short rectSolid[2][3][5];
double timeGrid[3][4][3][4];
• Three indices/subscript is used for three dimensional array
• Four indices/subscript is used for four dimensional array
Accessing Array’s Element: (LAB work)
// a program to find the total of all the elements in array y
#include <iostream>
using namespace std;
#define n 7
int main()
{
int i, total = 0, y[n] = {6,9,2,4,5,23,12};
for (i=0; i<n; i++)
{
cout<<y[i]<<" "; // display the array contents...
total = total + y[i]; // do the summing up…
}
// display the result...
cout<<"\nSum of 7 numbers in an array is = "<<total<<endl;
return 0;
}
32
Finding the Highest Value in an Array
(LAB work)
int count;
int highest;
highest = numbers[0];
for (count = 1; count < SIZE;
count++)
{
if (numbers[count] > highest)
highest = numbers[count];
}
When this code is finished, the highest variable will contains the
highest value in the numbers array.
Finding the Lowest Value in an Array
(LAB work)
int count;
int lowest;
lowest = numbers[0];
for (count = 1; count < SIZE; count+
+)
{
if (numbers[count] < lowest)
lowest = numbers[count];
}
When this code is finished, the lowest variable will contains the lowest
value in the numbers array.
1-34
Passing One Dimensional Arrays To Function
(Lab work)
A function can receive the address of an array by using:
1. A pointer.
2. A sized array e.g. s[20] or
3. An unsized array e.g. p[ ].
For example:
// pointers, will be explained in another Module
int myfunction(float *x)
// sized array
char yourfunction(float x[5])
// unsized array
void ourfunction(float x[ ])
▪the second and third methods not used in practice.
35
Passing One Dimensional Arrays To Function
(Lab work)
// function prototype
void func(float *);
int main()
{
float x[5];
// an array name (without the bracket) is
// the pointer to the first array element
func(x);
return 0;
}
// function definition
void func(float *pter)
{ return; }
36
How to determine length of the
string (self practice)
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
int len_str(char str[25]);
int len_str_while(char s[25]);
void main(void)
{
char l[25];
cin >> l;
cout << len_str(l) << endl << len_str_while(l);
}
//function with for loop
int len_str(char s[25])
{
for (int i = 0; s[i] != '\0'; i++);
return i;
}
Cont…
//another method using while loop
int len_str_while(char s[25])
{
int i=0;
while (s[i] != '\0')
{
i++;
}
return i;
}
Two dimensional Arrays
Main Program (self practice)
#include <iostream.h>
#include <conio.h>
void mult_matrices(int a[][2], int b[][2], int result[][2]);
void print_matrix(int a[][2]);
void main(void)
{
int p[2][2] = { {10, 20}, {30,40 } };
int q[2][2] = { {50, 60}, {70, 80} };
int r[2][2];
Why New
print_matrix(p);
Array?
print_matrix(q);
mult_matrices(p, q, r);
print_matrix(r);
}
Print a Matrix
void print_matrix(int a[][2])
{
int i, j;
for (i=0; i<2; i++)
Why mention 2?
{
for (j=0; j<2; j++)
{
cout << "\t" << a[i][j];
}
cout << endl;
}
cout << endl;
}
Multiply a Matrix
void mult_matrices(int a[][2], int b[][2], int result[][2])
{
int i, j, k;
for(i=0; i<2; i++)
{
for(j=0; j<2; j++)
{
Why passed
result[i][j] = 0;
so many
for(k=0; k<2; k++)
variables?
{
result[i][j] = result[i][j] + (a[i][k] * b[k][j]);
Are these
}
Variables
}
Called by
}
reference or
} By value?
