Skip to content

Instantly share code, notes, and snippets.

@cbourke
Created October 9, 2018 17:10
Show Gist options
  • Save cbourke/6306d21d487063e0d60b0f67918129ed to your computer and use it in GitHub Desktop.
Save cbourke/6306d21d487063e0d60b0f67918129ed to your computer and use it in GitHub Desktop.
auto-posted gist

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);













Debugging

  • Using printf statements to view the value(s) of variables is referred to as "poor man's" debugging
  • Using a proper debugger is better
  • A debugger is a program that simulates/runs another program and allows you to:
    • pause the execution
    • View varible values
    • "step" through the program line by line
    • set break points in a program and continue execution up to that point
  • GDB (Gnu's Debugger) is a command line debugger
  • Usage:
    • Compile with -g flag to preserve variable and function names gcc -g arrayProgram.c
    • Start GDB with your program: gdb a.out
    • Run your program: run
    • Set a break point: break main
    • See your code: layout next
    • Step: next (shorthand: n)
    • print a variable: print foo
    • print an array: print *arr@len
    • Set anothe break point base on a line number: break 25
    • Continue: continue
    • Watch a variable: watch total



















Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment