Difference between revisions of "Lecture 9" - Rhea

Revision as of 05:19, 7 February 2012

 int * arr;

This will initialize a pointer without a value.

int * arr = NULL;

This is a better way to initialize the same pointer. You can then use it to validate the pointer with an if statement (i.e. if (arr == NULL)…)
If you allocate memory in heap, you must release it at the end of your program.
It is a bad idea to allocate and free memory in different functions. You will run into trouble later in your coding experience when your programs get larger and more complex.

2-Dimensional Arrays

int ** arr2d;
arr2d = malloc(sizeof(int *) * numRow);

The first dimension of your array is an array of pointers (addresses).

for(r = 0; r < numRow; r++)
{
arr2d[r] = malloc(sizeof(int) * numCol);
}

This gives you a 1-dimensional array of length numCol at each pointer of the first dimension.
Then you have a 2 dimensional array.
When you free a 2-dimensional array, you must free it in the reverse order that you allocated.

for (r = 0; r < numRow; r++)
{
free(arr2d[r]);
}
free(arr2d); /* malloc first, free last */

You should go to structures if you must go to 4+ dimensions. It is more organized.

Pro Tip:
ECE 264 is moving from “coding” to “problem solving”
Think about how you will go about solving the problem before you write the program.
If you spend 1 hour thinking, you’ll save 10 hours coding/debugging.

How to Search an Array

int search(int * arr, int size, int val)
{
/* given an integer array and its size */
/* return 1 if value is an element in the array */
/* return 0 if value is not an element */
/* assume elements are distinct */
}

What can you do if you know the elements are sorted?
i.e. arr[i] < arr[j] if 0 <= i < j < size

int search(int * arr, int size, int val)
{
int c;
for (c = 0; c < size; c++)
{
if (arr[c] == val)
{
return 1;
}
}

return 0;
}

Binary search:

int low = 0;
int high = size;

int middle = (low + high) / 2;
if (arr[middle] = val)
{
found;
}
if (arr[middle] > val)
{
high = middle -1;
}
if (arr[middle] < val)
{
low = middle + 1;
}