CPS 125
Alexander Ferworn
Week 7
One Dimensional Arrays
What we will cover this week
Arrays
What is an array?
-------------------
o An array is a collection of variables of the same type.
o The purpose is to store large amounts of related data that share the same data type.
e.g. suppose you wanted to keep track of the ages of all your friends. This is fine as long as you only have a few friends...make up a variable name for each. Suppose you had thousands of friends?
o Individual array elements are identified by an integer index.
o In C the index begins at zero and is always written inside square brackets.
Basic format:
<type> <array name> [ <array size> ] <initializer>;
For example "results" is an array of 20 elements (0 to 19) called results;
int results[20];
Arrays can have more dimensions, in which case they might be declared as
int results_2d[20][5];
int results_3d[20][5][3];
Each index has its own set of square brackets.
o Where an array is declared in the main function it will usually have details of dimensions included.
o It is possible to use a pointer in place of an array.
o This means that dimensions are not fixed immediately, but space can be allocated as required.
Initializing Arrays
----------------------
This can be done in a declaration (all at once) or with a series of statements (one at a time).
e.g. declare and initialize the array ted.
double ted[4] = {1.0,2.0,3.0,4.0};
or
double ted[4];
ted[0] = 1.0;
ted[1] = 1.0;
ted[2] = 1.0;
ted[3] = 1.0;
or
double ted[4];
int j;
for(j=0;j<4;j++)
ted[j] j+1;
Fibonacci Series Using an Array
--------------------------------
o The program prints out a table of Fibonacci numbers.
o These are defined by a series in which any element is the sum of the previous two elements.
o This program stores the series in an array, and after calculating it, prints
the numbers out as a table.
#include <stdio.h>
void main()
{
int fib[24];
int i;
fib[0] = 0;
fib[1] = 1;
for(i = 2; i < 24; i++)
fib[i] = fib[i-1] + fib[i-2];
for (i = 0; i < 24; i++)
printf("%3d %6d\n", i, fib[i]);
}
Note:
In memory, each element of the array is stored beside another.
Array name and pointer equivalency
-----------------------------------
In C an array name is equivalent to a pointer to the first element (element zero) of the array.
For example take the following declarations;
...
int fib[20];
int *ptr_to_fib;
...
Since we know that each element of an array is right beside the next,
we could get the location of the first element by doing the following;
ptr_to_fib = &(fib[0]);
or we could take advantage of the pointer/array name equivalency with;
ptr_to_fib = fib;
Pointer arithmetic
-------------------
Because array elements are of the same type and are stored contiguously
we can jump around in an array by manipulating the index.
for example...if we want to print out the fifth element of
...
printf("%d\n",fib[3]);
...
we know that each int takes up 4 bytes so fib looks like the following when stored
(bn stands for byte n)
b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15
--fib[0]--- --fib[1]--- ----fib[2]--- ----fib[3]-----
o We know that the address of fib[0] can be found using &fib[0] and will be b0
o What if we ask for the address of fib[1] (&fib[1])? It should be b4 (4 byte ints)
o Note that the indexes go up by one but the byte counts go up by four.
o C lets you manipulate pointers the same way you manipulate the indexes in an array.
o This is called pointer arithmetic.
For example, the following are equivalent
x = fib[2-1] will put the value of x in fib[1]
which is the same as x = *(fib+2-1)
Note that when we add we are really adding 4 bytes at a time rather than just one.
Passing array names as arguments to functions
-----------------------------------------------
There are two ways to pass an array into a function, these are addressed below in a call to f1() and f2(), both functions set the second element in the array to 7.0;
f1(float *arr1,int index)
{
/* function receives array as pointer to first element,
second argument gives size of array */
*(arr1+1) =7.0;
}
f2(float arr[],int index)
{
/* function receives array as an array,
still need second argument to do bounds checking */
arr1[1]=7.0;
}
void main()
{
float arr1[20];
...
f1(arr1,20);
f2(arr1,20);
...
}
o When passed as an argument to a function, the receiving function need not know
the size of the array.
o for example if we have a function which sorts a list (represented by an array)
then the function will be able to sort lists of different sizes.
o The drawback is that the function is unable to determine what size the list is,
so this information will have to be passed as an additional argument.
As an example, here is a simple function to add up all of the integers in a
single dimensioned array.
int add_array(int array[], int size)
{
int i;
int total = 0;
for(i = 0; i < size; i++)
total = total + array[i]; /* could do it as total = total + *(array + I); */
return(total);
}
Sorting an Array
-----------------
o In this section we will show a simple function which is capable of sorting an
array into numerical or alphabetical order.
o This function implements something called bubble sort.
o The basic idea is very simple.
o Compare two values and if they are out of order swap them.
o Go onto the next two values and do the same...etc.
o When you hit the end go back to the beginning of the list.
o Stop when no values have been exchanged.
/* Bubble sort */
#define FALSE 0
#define TRUE 1
#include <stdio.h>
void bubble_sort(int list[], int list_size)
{
int j,k,temp,sorted=FALSE;
while(!sorted)
{
sorted = TRUE; /* assume the list is sorted */
for(j=0;j<list_size-1;j++)
{
if(list[j] > list[j+1])
{
sorted = FALSE;
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
void main()
{
int array1[5]={2,4,6,4,5},
array2[10]={1,6,5,4,3,9,0,8,1,2};
bubble_sort(array1,5);
bubble_sort(array2,10); /* note different sizes of array function handles */
}
Review questions
-----------------
example 1: What does the following program output?
#include <stdio.h>
#define TRUE 1
void main()
{
int j =7/2;
while(TRUE)
{
printf("%d\n",j=j-1);
if(!j) break;
}
}
example 2: What is the value of k when the program terminates?
void main()
{
short k=0,m,n=-3;
for(m=0;m<n;m++)
for(k=m;k<40;k++)
}
example 3: what is the value of j when the program terminates?
void main()
{
short k,m=7,n,j=0;
for(k=0;k<5;k++)
if((m<7) && (j++)) n=n+1;
m++;
}