SE250:March 17
| |
|---|---|
| REST | |
| The reason we have lectures. | |
- Lab 3 Overview
- 2007's Hypertext book to get an overview of the type of stuff that need to be produced for this years Hypertext book
- Notice: Shadow class #2 is on Tuesday (tomorrow). See here for details.
Mid-lecture Annocement
Hello
This is to announce the second shadow class for this year.SESA will be hosting a second shadow class, based on feedback from our various spies in your classes , we will be running through a brief overview of the basic concepts people still seem to struggle with followed by the topics of constructors, inheritance etc.
What: 2nd Shadow Class on JAVA
When: Tuesday, 18th of March, 1pm to 2pm
Where: Engineering Lab 1.312, Level 3 - where the engineering cafe is.
Cost: FREE (members allowed only!)
Don't worry if you haven't signed up already! Come along to the class and sign up there and collect your membership card. Its $5 to sign up for the whole year.
Cheers, SESA Exec Team
Minutes
Minute taker: sdal039
- Un-lecture - a success. more to come.
Overview of HTTB Has the categories
- Pointers
- Array Based Lists
- Linked Lists
- Binary Search Trees
- Hash Tables
- Trade offs
- Big O
- Amortized Analysis
- Parsing
- State-space Search
* Exam Style Questions
Our book will be very similar to this, but hopefully with less text and more screencasts.
Array Based Lists
The two types or normal arrays are 'size fixed at compile-time' and 'size fixed at run-time'. They are declared as:
int arr1[ 10 ]; int *arr2 = malloc(actual_size * sizeof(type));
where actual_size is the final size of the array and type is the type of elements that the array will contain (int, char, float etc...)
- note: when compiling use gcc -Wall to give warnings on everything
These types of arrays are very easy to use but are quite rare because in most cases, we have no idea how many elements we are going to store in the array.
To get around this we can use something called a Dynamically Resizing Array or, an array list.
The structure of it is:
__________ |__________| --pointer to an array--> |0|1|2|3|4|.....| |__________| --value--> how much of the array is used |__________| --value--> how big is the actual array (capacity)
When the array fills up 3 things happen: 1) a slot of memory is allocated that is larger than the initial array 2) the old array is copied to the new one 3) the old array memory is freed and we can now start using the new, larger, array.
Question asked: why can't you just resize the old one? Answer: Malloc allocates memory wherever it best fits. If the inital array is stored in memory it may be in a place where there is no free memory either side of it. This means that it cannot simply add more memory on to the end. Malloc has to find a new, bigger, area of memory to use instead.
Code for the array:
typedef double element_t <--allows us to easily changed the type of values that will be stored
typedef
struct {
element_t *arr;
int used;
int capacity;
} ArrayList;
When an ArrayList is declared, *arr, used and capacity will also be declared.
To use the array list we need to create some functions such as :
void arraylist_init( ArrayList *alist ) {
alist->arr = 0;
alist->length = 0;
alist->capacity = 0;
}
This function initializes the array and sets default values.
Note: you must use a pointer to pass a list to a function because otherwise any operation performed on the list inside the function will only happen on the local copy of the list. When the function returns and the memory allocated for it is freed, any operation it has performed will be lost.
There are two methods of inserting into an array list: push and put.
|0|1|2|3|4| free | <- memory block allocated for the array
^
'Push 5' adds the value 5 in here ^
This gives us the new array
|0|1|2|3|4|5|free|
The second method, put, is a bit more involved.
|a|b|c|e|f|g| free|
Put (d, 3) inserts the value 'd' into the array space 3. To do this, all values to the right of this space (e, f, g) must be shifted to the right.
|--these values have moved to the right-> |a|b|c|d|e|f|g|free|