// Pointers!!! /* Pass by reference int 4 char 1 float 8 double 8 long long 8 A pointer is nothing more than an address value is a memory address type describes the data located at that memory address
- When you create a pointer and don't set its value immediately, you should always set the pointer's value to NULL.
& is the address extraction operator. int x; &x is a pointer to an integer to the address of x. double arr[]; &arr[i] is a pointer to double who value is the address of the ith element of arr; if pc is a pointer to char, then *pc is the data that lives at the memory address stored inside pc. Dereferencing a null pointer causes a Segmentation Fault.
Dynamic Memory Allocation Dynamically allocated memory comes from the heap.
Any time we can give a variable a name it typically lives on the stack.
malloc() // Memory allocation, returns a pointer to allocated memory. if malloc() fails, it returns NULL;
int x;
int *px = malloc(sizeof(int));
int x = GetInt();
float stack_array[x];
float* heap_array = malloc(x * sizeof(float));
free(heap_array)
Dynamic memory is not automatically returned when the function that created it ends
must free() memory
- Every block of memory that you malloc() must subsequently be free()d.
- Only memory that you malloc() should be free()d.
- Do not free() a block of memory more than once. */
int m;
int* a; // pointer to int
int* b = malloc(sizeof(int)); // creates two boxes, a block of memory and an address pointing
// to that block of memory.
a = &m; // a gets the address of m; m <- a
a = b; // a now points to b;
m = 10;
*b = m + 2; // block pointed to by b now contains 12;
free(b); // memory released back to system.
*a = 11; // accessing unallocated memory, segfault!
struct car
{
int year;
char model[10];
char plate[7];
int odometer;
double engine_size;
};
struct car mycar;
// field access
mycar.year = 2011;
mycar.plate = "CS50";
mycar.odometer = 100;
/*
Access fields with '.' operator;
Structures, like variables of other data types, do not need to be created on the stack. We can dynamically allocate structures at run time if our program requires it.
In order to access the fields of our structures in that situation, we first need to dereference the pointer to the structure, and then we can access its fields.
*/
// variable declaration struct car *mycar = malloc(sizeof(struct car));
(*mycar).year = 2011; (*mycar).plate = "CS50"; mycar->plate = "CS50";
/* -> arrowo operator dereferences the pointer and access the field on the right.
Arrays are a fundamental data structure. A block of contigous space in memory. Accessed directly by index, starting from 0;
type name[size]; */ int grades[40]; // array of 40 integers // instantiation syntax bool truthtable[3] = { false, true, true }; bool truthtable[] = { false, true, true }; // also legal bool battleship[10][10]; // really just a 100 element one-dimensional array.
/* arrays are passed by reference
Linked Lists Random array insertion is costly. Arrays are also inflexible, must know proper size at start of program. Pointers + Structs = Singly Linked List;
A node is a struct with two members. Data of some type (int, char, float); A pointer to another node of the same type.
/ typedef struct sllist // sllist is a placeholder because sllnode is self-referential { val; struct sllist next; } sllnode; // this is the actual permanent name of the type
/*
- Create a linked list when it doesn't exist.
- Search a linked list to find an element
- Insert a new node into the linked list.
- Delete a single element from a linked list. // hard to do with a SLL
- Delete an entire linked list.
// Create sllnode* create( val);
a. dynamically allocate space for a new sllnode b. check to make sure we didn't run out of memory c. initialize val field d. initialize next field e. return a pointer to the new node.
// Search bool find(sllnode* head, val); // always want to keep track of head a. create a traversal pointer pointing to hte list's head. b. if the current node's val field is what we're lookning for, report success c. if not, set the traversal pointer to the next pointer in the list and go back to step b. d. if you've reached the end of the list, report failure. (linear search)
// Insert sllnode* insert(sllnode* head, val); a. dynamicall create a new node b. check for NULL b. set nodes next to previous head of list c. return a pointer to know head of linked list (order matters) // Delete node
// Destroy void destroy(sllnode* head); a. if we've reached a null pointer, stop. b. delete the rest of the list. c. free the current nod.
/ typedef struct dllist { val; struct dllist prev; struct dllist* next; } dllnode; /* create, search, insert, delete single element, destroy list;
dllnode* insert(dllnode* head, val); a. connect new node to head b. set new node prev to null c. connect old head to new head d. make new node new head
void delete(x); // in the middle, ends are handled slightly differently a. rearrange pointers to skip over deleted element. b. free() deleted element
LL support constant time insert and delete. Accessing an element may now take linear time. */