Design of Algorithms

C Review

menu_book

C Review

Table of Contents

Data types

Integer

Floating point numbers

chars and strings

Boolean values

Function declarations

// prototype (at top of file)
return_type function_name(arg_type arg_name);

// function implementation
return_type function_name(arg_type arg_name) {
    return ret_value;
}

main Function

Program to print the number of arguments and what they are:

int main(int argc, char **argv) {
    int i;

    printf("Number of arguments: %d\n", argc);
    for (i = 0; i < argc; i++) {
        printf("%s\n", argv[i]);
    }
    return 0;
}

Compilation

To compile hello.c

$ gcc -Wall -pedantic -o hello hello.c

Preprocessor directives

Library functions

Standard library header files imported using #include preprocessor directive

#include <assert.h> // contains assert, frequently used to verify malloc
#include <math.h>   // math functions e.g. cos, sin, log, sqrt, ceil, floor
#include <stdio.h>  // input/output e.g. printf, scanf
#include <stdlib.h> // contains NULL, memory allocation e.g. malloc, free

int main(int argc, char **argv) {
    /* ... */
    return 0;
}

Pointers

Arrays

Structs

Accessing fields

Student matthew;
// dot notation
matthew.student_number = 123456; 

Student *james = malloc(sizeof(*james));
assert(james);
// arrow notation
james->student = 654321;
free(james);
james = NULL;

Dynamic Memory Allocation

void *malloc(size_t size)   // size: size of memory block [bytes]

Example: allocating memory for an int

int *my_int = malloc(sizeof(*my_int)); // cast to (int *)
assert(my_int);     // check pointer is not null, i.e. malloc succeeded
/* do stuff */
free(my_int);       // free the memory
my_int = NULL;      // ensure that we don't inadvertently access freed memory

Variable-sized array

Header Files

Import guards

e.g. to write a hello world module

hello.h:

// import guard
#ifndef HELLO_H
#define HELLO_H

// print "hello, {name}!" on a line
void hello(char *name);
#endif

hello.c:

#include <stdio.h>
#include "hello.h"

// print "hello, {name}!" on a line
void hello(char *name) {
  printf("Hello, %s!\n", name);
}

main.c

#include "hello.h"

int main(int argc, char **argv) {
    char *name = "Barney";
    hello(name);
    return 0;
}

To compile a program with multiple `.c` files:
```console
$ gcc -o <executable name> <list of .c files>

For this example

$ gcc -o main main.c hello.c

Makefiles

make keeps track of changes across various files, only compiles what needs to be recompiled when something changes

# # # # # # #
# Sample Makefile for compiling a simple multi-module C program
#
# created for COMP20007 Design of Algorithms 2017
# by Matt Farrugia <matt.farrugia@unimelb.edu.au>
#

# Welcome to this sample Makefile. If you're new to make and makefiles, have a
# read through with the comments and follow their instructions.


# VARIABLES - change the values here to match your project setup

# specifying the C Compiler and Compiler Flags for make to use
CC     = gcc
CFLAGS = -Wall

# exe name and a list of object files that make up the program
EXE    = main-2
OBJ    = main-2.o list.o stack.o queue.o


# RULES - these tell make when and how to recompile parts of the project

# the first rule runs by default when you run 'make' ('make rule' for others)
# in our case, we probably want to build the whole project by default, so we
# make our first rule have the executable as its target
#  |
#  v
$(EXE): $(OBJ) # <-- the target is followed by a list of prerequisites
	$(CC) $(CFLAGS) -o $(EXE) $(OBJ)
# ^
# and a TAB character, then a shell command (or possibly multiple, 1 line each)
# (it's very important to use a TAB here because that's what make is expecting)

# the way it works is: if any of the prerequisites are missing or need to be
# recompiled, make will sort that out and then run the shell command to refresh
# this target too

# so our first rule says that the executable depends on all of the object files,
# and if any of the object files need to be updated (or created), we should do
# that and then link the executable using the command given


# okay here's another rule, this time to help make create object files
list.o: list.c list.h
	$(CC) $(CFLAGS) -c list.c

# this time the target is list.o. its prerequisites are list.c and list.h, and
# the command (its 'recipe') is the command for compiling (but not linking)
# a .c file

# list.c and list.h don't get their own rules, so make will just check if the
# files of those names have been updated since list.o was last modified, and
# re-run the command if they have been changed.


# actually, we don't need to provide all that detail! make knows how to compile
# .c files into .o files, and it also knows that .o files depend on their .c 
# files. so, it assumes these rules implicitly (unless we overwrite them as 
# above).

# so for the rest of the rules, we can just focus on the prerequisites!
# for example stack.o needs to be rebuilt if our list module changes, and
# also if stack.h changes (stack.c is an assumed prerequisite, but not stack.h)
stack.o: stack.h list.h

# note: we only depend on list.h, not also list.c. if something changes inside
# list.c, but list.h remains the same, then stack.o doesn't need to be rebuilt,
# because the way that list.o and stack.o are to be linked together will remain
# the same (as per list.h)

# likewise, queue.o depends on queue.h and the list module
queue.o: queue.h list.h

# so in the future we could save a lot of space and just write these rules:
# $(EXE): $(OBJ)
# 	$(CC) $(CFLAGS) -o $(EXE) $(OBJ)
# list.o: list.h
# stack.o: stack.h list.h
# queue.o: queue.h list.h



# finally, this last rule is a common convention, and a real nice-to-have
# it's a special target that doesn't represent a file (a 'phony' target) and
# just serves as an easy way to clean up the directory by removing all .o files
# and the executable, for a fresh start

# it can be accessed by specifying this target directly: 'make clean'
clean:
	rm -f $(OBJ) $(EXE)

Linking with external libraries

Introduction to GCC

e.g. to access math functions sqrt, log etc. in math.h, C source code: calc.c

#include <math.h>

-l<name>

Link the math library with full path:

$ gcc -Wall calc.c /usr/lib/libm.a -o calc

More succinctly: compile with -lm flag to link math library

$ gcc -Wall calc.c -lm -o calc

-I/path/to/dir and -L/path/to/dir

Environment variables

Shared libraries

Forced static linking

Warnings

Debug

#ifdef DEBUG // stuff here only compiles when DEBUG is defined #endif

- `gcc` has built in debug support with the `-DDEBUG` flag, without you needing
  to define `DEBUG`
```console
$ gcc -Wall -DDEBUG -o program program.c

Function pointers

Polymorphism

e.g. Moffatt 10.5

// treeops.h
typedef struct node node_t;

struct node {
    void *data;     // pointer to stored structure
    node_t *left;   // left subtree of node
    node_t *right;  // right subtree of node
};

typedef struct {
    node_t *root;               // root node of tree
    int (*cmp)(void*, void*);   // function pointer
} tree_t;

// create an empty tree, pass in a comparison function to be used subsequently
tree_t *make_empty_tree(int func(void*, void*));
int is_empty_tree(tree_t *tree);
void *search_tree(tree_t *tree, void *key);
tree_t *insert_in_order(tree_t, *tree, void *value);
// traverse the tree, with pointer to action function to take
void traverse_tree(tree_t *tree, void action(void*));
void free_tree(tree_t *tree);

static

const

Edit this page.