Merge Sort

Sort the left half, then sort the right half, then merge the two halves together. The left half can be sorted using the same algorithm. Recursively applying this will eventually lead to just one element that requires "sorting", another element which requires "sorting" and then merging these two together. When they get merged they are merged into a new array. This is followed by the right half of that half, then unwind back up the stack, merging as we go until the entire array is sorted. Running time is O(n log n). Takes more memory due to having to hold and extra array which the halves are merged into.

File IO

FILE* f = fopen("filename", "r") // open the file in read only mode

where the last argument is one of "r", "W", "a" (a for append) Always check for NULL after trying to open the file

fputs("hello world", f); // writes the string to a file
fputs("\n", f);

fgets(output, sizeof(output), f); // reads a line from a file

// read a text file line by line
for (int i = 1; fgets(output, sizeof(output), f) != NULL; i++)
    printf("Line %02d: %s", i, output);

To check that the reason the NULL pointer is reached is due to the end of the file (and not some other error) it is possible to check either the ferror or feof functions.

if (feof(f)) { ... }

fclose(f);  // close the file

Structs

struct
{
    int age;
    char *name;
};

Useful, but this doesn't create anything e.g. like saying int;.

struct
{
    int age;
    char *name;
} student;

Now we have an anonymous struct and a variable student which has 2 attributes name and age which we can use via . e.g. student.name = 12.

In order to create multiple objects, we need to give the struct a name:

struct student
{
    int age;
    char *name;
} s1;

struct student s1; // alternative way to declare a struct student
Struct student s2 = {1, "Fred"}; // concise initialisation, similar to arrays

s1 = s2; // assign s1 the same values as s2
s1.age = 10; // here s2 does not change (just as y does not change when you say x = y and then x = 4;)

Instead of writing struct student everywhere we could use a typedef

typedef struct
{
    int age;
    char *name;
} student;

Now we can use student everywhere that we used to use struct student. This typedef's an anonymous struct and calls it student.

Structs and Functions

void func(student s) { ... }
func(s1);

The struct behaves exactly as an integer would if passed to a function. The function recieves a copy of s1 and so can't modify s1. To actually pass in s1, you need to change the function definition to take a *student and pass s1 in by address:

void func(student *s) { ... }
func (&s1);

Added benefit is that the fields in the struct don't need to be passed into the stack frame now (even if we don't want to modify s1).

Structs and Pointers

Creating a pointer to a struct is also possible.

student *s = malloc(sizeof(student));

BUT how do we now access the age member?

*s.age = 32;    // by default this puts the brackets around s.age as in *(s.age) = 32 so won't work
(*s).age = 32;  // correct, but annoying / confusing syntax
s->age = 32;    // nice syntax

Valgrind

Helps to detect memory leaks. Runs on the executable of a program.