Transcript Array

Arrays
• What is an array…
– A data structure that holds a set of
homogenous elements (of the same type)
– Associate a set of numbers with a single variable name
– All of these numbers must be of identical data type
• Similar to a multi-dimensional vector
How to Define
• Declaration
type <var_name>[size];
• Example
– To define an integer array
called numbers of size
• int numbers[5];
numbers 0
1
2
3
4
How to Use Arrays
• How to refer to an individual
element of an array
– Accessed by their position
(index) in the array, e.g.
numbers[1] = 2;
numbers[0]
numbers[1]
• Array elements are always
numbered beginning with 0
numbers[2]
numbers[3]
numbers[4]
2
Example – 0
• Get a set of numbers from the user
int numbers[5];
int i;
for( i = 0; i < 5; i++ )
scanf("%i", &numbers[i]);
Example – I
• Calculate statistics of a set of numbers
– Summation
int sum = 0;
for( i = 0; i < 5; i++ )
sum = sum + numbers[i];
– Finding the maximum value
int maxValue = numbers[0];
for( i = 1; i < 5; i++ ) {
if (numbers[i] > maxValue)
maxValue = numbers[i];
}
Fibonacci Numbers in an Array
n
0
1
2
3
4
5
6
F(n)
0
1
1
2
3
5
8
Code
#include <stdio.h>
#define SIZE 15
int main()
{
int fib[SIZE], i;
fib[0] = 0; //set initial values
fib[1] = 1; //set initial values
for ( i = 2; i < SIZE; i++ ) {
fib[i] = fib[i - 2] + fib[i - 1];
}
for ( i = 0; i < SIZE; i++ ) {
printf(”fibonacci[%i] = %i\n", i, fib[i]);
}
return 0;
}
Prime Number
• Definition (could be you already know this?)
– A positive integer that has no positive integer
divisors other than 1 and itself.
• Testing whether a number p is a prime
number
Is there an integer divisor between 2 and p-1
for p?
Approaches – I
• Base version 1
int d; /* possible divisor */
int p; /* number whose “primeness”
we are testing. */
for (d = 2; d < p; d++) {
if (p % d == 0) {
printf(“%i is not a prime!\n”, p);
break;
}
}
Approaches – II
• Version 2
#define TRUE 1
#define FALSE 0
int isPrime = TRUE;
int d,p;
for (d = 2; d < p; d++) {
if (p % d == 0) {
isPrime = FALSE;
break;
}
}
if (isPrime)
printf(“%i is prime\n”, p);
else
printf(“%i is not prime\n”, p);
Approaches – III
• Observation
– Only need to test whether there is a integer divisor
between 2 and p for p
for (d = 2; d * d <= p; d++) {
if (p % d == 0) {
isPrime = FALSE;
break;
}
}
Approaches – IV
• Observation
– Only need to check whether a prime
number between 2 and p is a divisor
– Need to record which numbers are
prime so we only test them once
• Using arrays!
Code
• Declare variables
int
int
int
int
p, i;
primes[PRIMES]; // for noting prime numbers
primeIndex; // next place to store a prime
isPrime;
// boolean variable
• Initial setup
primes[0] = 2;
primes[1] = 3;
primeIndex = 2;
// we know 2 is prime
// we know 3 is prime
// the next array slot is [2]
Code – cont
for (p = 5; p <= PRIMES; p += 2 ) {
isPrime = TRUE; // start by assuming p is prime
i = 1;
// let’s skip the first prime (its 2)
while (i < primeIndex) {
if ( p % primes[i] == 0 ) {
isPrime = FALSE;
break;
// leave loop, no point to
// testing more divisors
}
i++;
}
if (isPrime) {
primes[primeIndex] = p;
// Store prime p
++primeIndex;
// advance index
if (primeIndex > PRIMES) break; // prime array is full
}
}
Initializing arrays
• Initializing an array using a commaseparated list of constants in { }
– int number[] = { 5, 7, 2 };
• Size of an array is automatically set as the number
of elements within { }
Character Arrays and Strings
• A Character Array contains characters (naturally)
– char word[ ] = {‘H’,’e’,’l’,’l’,’o’,’!’}
• Strings
– A special character ‘\0’ (called a “null” character) at
the end of a character array indicates the end of a
string.
– Use %s in printf to print a string
– initialization
• char word[]="hello";
h
e
l
l
o
\0
The const qualifier
• When we need the const qualifier
– Specify a variable whose value is constant, i.e., value
will not be changed
• How to use
– Put const in front of variable definition
const double pi = 3.141592654;
• What if I attempt to change its value
– E.g.
pi = pi * 2;
– I will get a compiler Warning/Error:
• “Assignment of read-only variable `pi’”
Multidimensional Arrays
• Declaration
– type name[ nrows][ncols];
e.g. int m[5][10];
• Access
– m[3][4];
ai , j
n columns
m
a
rows  0 , 0
i changes
Not m[3,4],
or m(3)(4)
m–by–n matrix
a
 1, 0
 a2 , 0

 
a0,1
a1,1
a2,1

j changes
a0, 2 

a1, 2 
a2, 2 

 
Multidimensional Arrays
• Initialization
int M[2][3] = {{1, 2, 3}, {4, 5,6}};
– Or
int M[2][3] = {1, 2, 3, 4, 5, 6};
• Numbers will fill up the first row, then the second
row,…