CSCE 155H - Computer Science I Honors

Arrays

It is rare to only deal with one piece of data
Usually, more than one number, string, object, etc.
Collections of data can be stored in arrays
In general:
- arrays have a single identifier (name)
  - You can access individual elements in an array using an index
  - Usually arrays are 0-indexed: the first element is at index 0, the second is at index 1, etc.
  - If there are $n$ elements in an array, the last element is at index $n-1$
  - Indexing is done using square brackets: arr[2] (third element!)

Array in C

Static Arrays

Static arrays are arrays of a fixed size that are allocated (created) on the program call stack
Syntax:

int arr[10];
double numbers[20];

numbers[0] = 42; //it takes the value 42.0
arr[0] = 3.14; //takes on the value 3

arr[1] = 12;
arr[2] = -42;
arr[9] = 42;
arr[10] = 17;

In C, accessing elements outside the bounds of an array is undefined behavior: it could be a segmentation fault, it could corrupt your own program's memory, or just lead to garbage results
Observation: recall that there are no default values for variables in C, likewise there are no defaults for array values
Alternative syntax:

int n = 7;
int primes[] = {2, 3, 5, 7, 11, 13, 17};

In the above, the compiler takes care of the sizing for us, but
We always are responsible in C for our own bookkeeping

Sizing and Iteration

In C, there is absolutely no way to consistently determine the size of an array after it is created
Thus, we always need to keep track of an array's size in a separate integer variable
If you pass an array to a function, you also need to pass its szie
If you return an array from a function, the calling function needs a way to determine how big it is

Pitfall: Variable Length Arrays (VLAs)

int n;
printf("Enter the size of the array you want:");
scanf("%d", &n);
int arr[n];

Drawback: static arrays and VLAs are allocated on the stack; the stack is small and so it may not be able to handle even moderately large pieces of data

Dynamic Arrays

Dynamic arrays are allocated in a program's heap instead of its stack
The heap is generally much larger though more inefficient
You can dynamically allocate memory on the heap using a function called malloc (memory allocation)
You give malloc one argument: the number of bytes you want to allocate
malloc returns a generic void pointer to the memory that it allocated

int *arr = NULL;
//want to create a "large" array of 1 million integers
int n = 1000000;
arr = (int *) malloc(n * sizeof(int));

arr[0] = 42;
arr[n-1] = 9;

You can use sizeof to determine how many bytes any particular type of variable takes
If malloc fails it returns NULL
After you've allocated memory, you can use the array like any other array
Usually, it is best practice to type cast the returned pointer to its proper type
There is only one malloc function: there is a separate function to allocate ints, doubles, etc.
Consequently, malloc returns a generic void pointer, void *: a pointer to anything! It is just a generic memory address!
To change the generic void pointer into an integer pointer or a double pointer, you Type cast it

//create an array that can hold 100 double values
int n = 100;
double *numbers = (double *) malloc(n * sizeof(double));
if(numbers == NULL) {
	printf("something happened!, quitting...\n");
	exit(1);
}

Once you are done using an array, you need to be a good steward of the system's resources: you should give the memory back
Failure to do so may lead to wasted resources or memory leaks
To free memory and give it back to the operating system (so other programs can use or your own program can reuse it) use the function called free
It only takes one argument: the pointer to the memory you want to free

free(arr);
free(numbers);

After memory has been freed, you cannot expect to access it anymore
Don't free things twice!
Make sure to only free after you're are done with it

Arrays in Java

Java has NO static arrays, NO VLAs, only dynamic arrays
Instead of malloc you use new
There is no free in Java because you don't do your own memory management: the JVM takes care of that for you
Example:

int arr[] = new arr[10];
double numbers[] = new double[20];
//using a variable:
int n = 100;
double scores[] = new double[n];

In Java, you don't need to do your bookkeeping
The size of an array is stored in a property called .length
Example:

int arr[] = new arr[10];
for(int i=0; i<arr.length; i++) {
	System.out.println(arr[i]);
}

With arrays, you can use an enhanced for loop:

int arr[] = new arr[10];
for(int x : arr) {
	System.out.println(x);
}

If you access an element outside the bounds of an array in Java: IndexOutOfBoundsException
But... should you use arrays in Java? Or is there something better?

Dynamic Collections

Example: instead of arrays you can use ArrayLists

List<Integer> arr = new ArrayList<Integer>();
arr.add(10); //adds it at the end of the list
arr.add(20);
arr.add(30); //[10, 20, 30]
for(int i=40; i<=100; i+=10) {
	arr.add(i);
}
arr.remove(50);

for(int i=0; i<arr.size(); i++) {
	System.out.println(arr.get(i));
}

for(Integer x : arr) {
	System.out.println(x);
}

List<Double> numbers = new ArrayList<Double>();
List<String> names = new ArrayList<String>();
numbers.add(3.5); //okay
numbers.add("four"); //compiler error

names.add("Chris");
names.add("four"); //okay too
names.add(3.5); //compiler error!

Maps!

Maps allow you to create a key-value pair collection
The key can be any type, the value can be any type!

Map<Integer, String> m = new HashMap<Integer, String>();
m.put(35140602, "Chris");
m.put(12345678, "Kyle");

String s = m.get(35140602);
//s now stores "Chris"

//iterate over the keys in a map:
for(Integer key : m.keySet()) {
  System.out.println(key + " maps to " + m.get(key));
}

Sets

Sets are like lists but are unordered and only contain unique elements

Set<Integer> s = new HashSet<Integer>();
s.add(10);
s.add(20);
s.add(10); //no effect, 10 is already in the set!
//since it is unordered you cannot use s.get(0)
//you must use an enhanced for loop:
for(Integer x : s) {
  System.out.println(s);
}

Arrays with Functions

In C, an array's name is its pointer, it is a reference to the beginning of the array
When you pass an array to a function in C, you are passing by reference: you are passing a pointer to the "first" element in the array
IN addition, remember to pass a variable to represent the size of the array, you need to do your own bookkeeping!

/**
 * This function takes an integer array (of size n) and
 * returns the sum of its elements.  It returns 0 if the
 * array is NULL or if its size is <= 0
 */
int sum(const int *arr, int n) {
  if(arr == NULL || n <= 0) {
    return 0;
  }
  int total = 0;
  for(int i=0; i<n; i++) {
    total += arr[i];
  }
  return total;
}

If you do not plan to make changes to an array, make it const
Functions in C can also "return" an array

/**
 * This function creates a new integer array of the given size filled with
 * ones.
 * Returns NULL if n is less than 0
 */
int * arrayOfOnes(int n) {
  if(n < 0) {
    return NULL;
  }
  int *result = (int *) malloc(n * sizeof(int));
  for(int i=0; i<n; i++) {
    result[i] = 1;
  }
  return result;
}

Java

When passing an array to a method in Java, you use the square brackets

public static int sum(int arr[]) {

  int total = 0;
  // for(int i=0; i<arr.length; i++) {
  //   total += arr[i];
  // }
  for(int x : arr) {
    total += arr[i];
  }
  return total;
}

public static int [] arrayOfOnes(int n) {
  if(n < 0) {
    return null;
  }
  int result[] = new int[n];
  for(int i=0; i<result.length; i++) {
    result[i] = 1;
  }
  return result;
}

Multidimensional Arrays

You can have arrays with multiple dimensions
1-D Arrays: what we've covered so far
2-D Arrays: rows/columns (matrix, tables): you can have $n \times n$ or $n \times m$ 2-D arrays, $n$ rows, $m$ columns
3-D Arrays: rows/columns/aisles or lanes
4+D Arrays: really rethink what you're doing
Focus: 2-D arrays, with rows/columns

In C:

You need a pointer to a pointer which points to an array of pointers. Each pointer in the array points to a "row" in the table/matrix

int **m = NULL;
m = (int **) malloc(n * sizeof(int*));
for(int i=0; i<n; i++) {
  m[i] = (int *) malloc(m * sizeof(int));
}

m[0][0] = 42;//first row, first column
m[3][5] = 17;//4th row, 6th column
m[n-1][m-1] = 101;

//clean up: clean up the rows first, then the column of pointers:
for(int i=0; i<n; i++) {
  free(m[i]); //free the i-th row
}
free(m);

In Java:

Java has no pointers

int n, m;
//want an n x m array:
int m[][] = new int[n][m];

m[0][0] = 42;//first row, first column
m[3][5] = 17;//4th row, 6th column
m[n-1][m-1] = 101;

//clean up: don't worry about it!
//Java is memory managed, it cleans up memory for you!

Shallow vs Deep Copies

Consider the following C code:

int i, n = 10;
int *a = (int *) malloc(n * sizeof(int));
for(i=0; i<n; i++) {
  a[i] = i*10;
}

//make a "copy" of a:
int *b = a;
b[0] = 42;
printf("a[0] = %d\n", a[0]); //prints what?

The above is an example of a shallow copy: you only copy a reference
Both pointers are pointing to the same memory, same array
Changes to one affect the other and vice versa
Often you don't want this, you want a deep copy instead
Example: write a function that creates a deep copy of an integer array

int * deepCopyInt(const int *arr, int n) {
  int * result = (int *) malloc(n * sizeof(int));
  for(int i=0; i<n; i++) {
    result[i] = arr[i];
  }
  return result;
}

Java

In Java you have the same problem

int n = 10;
int a[] = new int[n];
for(i=0; i<a.length; i++) {
  a[i] = i*10;
}

int b[] = a;//shallow copy!
b[0] = 42; //a[0] is also now 42

//deep copy:
b = ArrayUtils.copy(a);

cbourke/arrays-155H.md

CSCE 155H - Computer Science I Honors

Arrays

Array in C

Static Arrays

Sizing and Iteration

Pitfall: Variable Length Arrays (VLAs)

Dynamic Arrays

Arrays in Java

Dynamic Collections

Maps!

Sets

Arrays with Functions

Java

Multidimensional Arrays

In C:

In Java:

Shallow vs Deep Copies

Java

Debugging