A Homogeneous Data Structure

A one-dimensional array is a structure that will hold large amounts of the same type of data...hence the title above. 

Define a Java array of int and sketch a drawing of its memory.

Here's how we define an array of int in C

int numbers[LENGTH];  

where LENGTH is a #define somewhere at the top of your program.

Sketch a drawing of the memory.  Note the subtle difference!

int numbers [8] = {5, 16, 27, 38, 59, 110, 230, 325};    //define an array of 8 integer and initialize

     0           1          2          3          4           5          6           7
//each element has a corresponding index (or subscript).

An element is the actual storage position.  Its address is designated with the help of its index.

numbers[4], the fourth element
numbers[0], the zeroth element
numbers[k], the kth element
 
Be careful that you always have valid index numbers for the array!!!
 

• numbers[8] is a common error b/c there are 8 elements in the array, but the index values are 0-7.  This would cause an error of some kind.  Usually, it would run as expected w/ unexpected results.  numbers[8] is garbage and may crash the program.

**accessing an element can be done by simply using the array's name and the element's proper index.**
**This is also called "random access" since you can access any elements without going through the predecessors first.

numbers[2] = 4;    //this would assign 4 to the 2nd element replacing 27.

numbers[0] = numbers[5] % numbers[0] + 1; //variable expressions can be used.

printf("%i", numbers[7]);

OTHER array definitions:
 

int counters [100];

double speeds [MAXNUM]; //MAXNUM is some constant

char vowels [ ] = { 'a', 'e', 'i', 'o', 'u'};  //the size is determined by the initial data

int evens [10] = {2}
//when the initializing sequence is shorter than the size of the array, the rest are initialized to zero

      0            1             2            3             4            5            6            7                8            9

Unfortunately, an array cannot be assigned to another array.

evens = numbers;   is an illegal statement.

To do this, one needs to create an array copying function.

Traversing

In managing an array, one must be able to traverse (move through several elements sequentially) the array.  That is done with the help of a loop.
 

for (k = (some initial index); k < (some terminating index); update k)
{
    myArray[k] = whatever you need to do;  //what do you want to do as you visit each element
}

int counters[10], numbers[20];
int k;

for (k = 0; k < 10; k++)  //don't include 10 b/c the indices are 0 - 9
{
    counters[k] = 100;    //initializes all elements to 100
}

for (k = 0; k < 20; k++)    //don't include 20 b/c the indices are 0 - 19
{
    scanf("%i", &numbers[k]);    //reads value from user
}

Sketch a picture of the following declarations:

1. int nums [5] = {2,3,4,5,6};
2. double temps [7] = {2.5, 3.2,5};
3. char letters [ 26 ];

char k;
for (k = 'a'; k <= 'z' ; k++)
    letters [k - 'a'] = k;
4. int values [13];

int k;
for (k = 0; k < 10; k ++)
    values[k] = 2 * k + 1;

Arrays and Functions

max.c

Arrays must be defined equal  to or larger than the number of data values stored in them.

As a result, arrays fall into two categories,

1. Every element contains valid usable data.  This is called a "packed array".  One can use the constant in the declaration throughout the program to help traverse the array correctly.
2. NOT every element contains valid data.  Some contain data, others contain garbage.  These arrays need a variable to keep track of how many elements contain data.  As in the program above, numPts was used.  Other descriptive identifiers could be numElements, numData, and so on.  These variables must be passed through parameters to other functions so that traversing the array is done correctly.

In 'C', one must be very careful when working with an array that was passed as a parameter.

So far, that parameters have all been "value parameters".  In other words, copies of the original variables.

However, an array in 'C' is passed as a "reference parameter" which means it refers to the original.

Any changes made to a parameter array in a function will change the original forever!!!!

This may cause a "side effect" or unexpected result.  But, it may also be helpful if that IS what's intended.  Examples to follow.

const and parameters

Statistics & Arrays

double median(const double nums[], int numEls)
/*returns median value in array with numEls elements*/
{
    int k;

    k = floor(numEls/2);
    if (numEls % 2 != 0)
        return nums[k];
    else
        return (nums[k - 1] + nums[k])/2;
}
 

double variance(const double nums[], int numEls)
/*returns variance of values in array with numEls elements*/
{
    int k;
    double sum = 0;
    double avg = getAvg (nums, numEls);

    for(k = 0; k < numEls; k ++)
    {
        sum += pow (nums[k] - avg, 2);
    }

    return sum/(numEls - 1);
}
 

double stdDev(const double nums[], int numEls)
/*returns standard deviation of values in array with numEls elements*/
{
    return sqrt (variance(nums, numEls));
}

Sorting (we will spend more time w/ this later before exam #1)

It is often necessary to sort the data found in an array into either ascending or descending order.

You will be expected to simulate the following sorting algorithm.  The code can be copied and pasted into any program, and then modified to that particular problem and syntax.

You know how to manipulate arrays.  Sorting algorithms show how you can put several simple concepts together to create a powerful new algorithm.  Selection sort uses 3:  traverse the array, find a min, swap two values.

void selectionSort (double numbers [], int numVals)
{
    int k, j, min;
    double hold;

    for (k = 0; k < numVals - 1; k ++)
    {
        min = k;
        for (j = k + 1; j < numVals ; j ++)
        {
            if (numbers[j] < numbers [min])
                min = j;
        }
        //swap
        hold = numbers[min];
        numbers [min] = numbers[k];
        numbers[k] = hold;
    }
}
 

Maintaining a sorted array (this is not sorting, this is adding a single element to an array in a particular position)

Sometimes it is better to maintain data in sorted order by placing them in the proper position at the time one places the data into the array.  The following block of code will do that and can be modified for any situation.

There are two search algorithms for which you will be responsible.

1. Linear Search - As the name describes, start at the front of the line and search for the target.

int search (const int values[], int numVals, int target)
/*returns index of target or -1 if target not found*/
{

 
 
 
 
 
 


 

2. Binary Search - Divide and Conquer!!!  The data must be sorted for this to work!

int search (const int values[], int numVals, int target)
/*returns index of target or -1 if target not found*/
{
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Created By Mike Maltrud : The University of Texas at San Antonio