← back

CS50 Cheatsheet for C

C Programming

Hello World

The Hello World program in C below prints “Hello, world!” to the terminal. It also includes a few basic elements of C programming, such as the #include directive, the main function, and the printf function.

#include <stdio.h>

int main(void)
{
    printf("Hello, world!\n");
}

Comments

Why are comments important?

Comments are used to explain the code and make it easier to understand. They are ignored by the compiler and are for the programmer’s benefit (you might to come back to your code later and wonder what you were thinking or you might be working with a team and want to explain your code to them).

// this is a single line comment

/*
this is a 
multi-line
comment
*/

#include

You can include libraries in your C program using the #include directive. The #include directive tells the compiler to include the contents of the specified file in the program.

#include <stdio.h>

Some common libraries you might include are:

  • stdio.h - standard input/output library (for functions like printf)
  • cs50.h - CS50 library (for functions like get_int)
  • stdlib.h - standard library (for functions like malloc)
  • math.h - math library (for functions like sqrt)
  • string.h - string library (for functions like strlen)

For a reference of the functions in each library, you can check the CS50 Manual.

main Function

The main function is the entry point of a C program. When you run a C program, the operating system calls the main function to start the program. The main function is required in every C program.

int main(void)
{
    // code goes here
}

Note that int is the return type of the function, and void is the parameter list. void means that the function does not take any parameters.

Variables

Data Types

  • int - integer
  • float - floating point number
  • double - double-precision floating point number
  • char - character
  • string - string of characters (array of characters, technically)
  • bool - boolean
  • void - no value
  • long - long integer

Variable Declaration

int num = 2;
float pi = 3.14;
char letter = 'a';
string name = "Alice"; // must include #include <string.h> or #include <cs50.h>
bool is_true = true;

// you can also declare multiple variables of the same type on the same line
int x, y, z;

// you can also declare and initialize variables without specifying the type
int a = 2, b = 3;

Variable Assignment

You can assign a value to a variable using the assignment operator =.

int num;
num = 2;

Variable Naming

  • Variable names must start with a letter or an underscore.
  • Variable names can contain letters, numbers, and underscores.
  • Variable names are case-sensitive.
  • Variable names cannot be keywords (e.g., int, float, char).

Variable Scope

Variables can have different scopes depending on where they are declared:

  • Global - declared outside of any function
    • Global variables are accessible from any function in the program.
  • Local - declared inside a function
    • Local variables are only accessible within the function where they are declared.

Here is a simple example to illustrate variable scope:

int global_var = 2;

int main(void)
{
    int local_var = 3;
    printf("%i\n", global_var); // prints 2
    printf("%i\n", local_var); // prints 3
}

void another_function(void)
{
    printf("%i\n", global_var); // prints 2
    printf("%i\n", local_var); // error: local_var is not accessible
}

Constants

Constants are variables whose values cannot be changed once they are assigned. You can define a constant using the const keyword.

const int NUM = 2;

Operators

Arithmetic Operators

  • + - addition
  • - - subtraction
  • * - multiplication
  • / - division
  • % - modulo
int sum = 2 + 3;
int difference = 5 - 2;
int product = 2 * 3;
int quotient = 10 / 2;
int remainder = 10 % 3;

A few notes about operators:

  • modulo operator % returns the remainder of a division operation.
  • division operator / returns a float if one of the operands is a float, and an integer if both operands are integers.

Relational Operators

Relational operators are used to compare two values and return a boolean result (true or false).

  • == - equal to
int x = 2;
int y = 3;

if (x == y)
{
    printf("x is equal to y\n");
}
  • != - not equal to
if (x != y)
{
    printf("x is not equal to y\n");
}
  • > - greater than
if (x > y)
{
    printf("x is greater than y\n");
}
  • < - less than
if (x < y)
{
    printf("x is less than y\n");
}
  • >= - greater than or equal to
if (x >= y)
{
    printf("x is greater than or equal to y\n");
}
  • <= - less than or equal to
if (x <= y)
{
    printf("x is less than or equal to y\n");
}

Logical Operators

Logical operators are used to combine multiple conditions and return a boolean result.

  • && - and
  • || - or
  • ! - not
int x = 2;
int y = 3;

if (x > 0 && y > 0)
{
    printf("x and y are positive\n");
}

if (x > 0 || y > 0)
{
    printf("x or y is positive\n");
}

if (!(x > 0))
{
    printf("x is not positive\n");
}

Assignment Operators

Assignment operators are used to assign/update values to variables. Besides the basic assignment operator (=), they often combine an arithmetic operation with assignment.

  • = - assignment
  • += - addition assignment
  • -= - subtraction assignment
  • *= - multiplication assignment
  • /= - division assignment
  • %= - modulo assignment
  • ++ - increment
  • -- - decrement
int x = 2;
x += 3; // x is now 5

int y = 5;
y -= 2; // y is now 3

int z = 3;
z *= 2; // z is now 6

int a = 10;
a /= 2; // a is now 5

int b = 10;
b %= 3; // b is now 1

int c = 2;
c++; // c is now 3

int d = 3;
d--; // d is now 2

// you can even combine operators
int e = 2;
e *= 3 + 2; // e is now 10

Input/Output and Printing

printf

printf prints a formatted string to the terminal:

// print text
printf("hi\nhi")

// print a new line
printf("\n")

// print the value of variables
int num = 2
printf("the value of this number is %i", num)
/* 
can also do for 
strings, doubles, floats, etc. 
using %s, %d, %f, etc., 
as seen below
*/

Format Codes

Format codes are used to specify the type of data that is being printed. These are placeholders that are replaced by the actual values when the printf function is executed.

  • %i - integer
  • %f - float
  • %c - char
  • %s - string
  • %b - boolean

Escape Sequences

Escape sequences are special characters that are used to format the output of a string. They are preceded by a backslash \.

  • \n create a new line
  • \r return to the start of a line
  • \” print a double quote
  • \` print a single quote
  • \\ print a backslash

get_int, get_float, get_string

get_int, get_float, and get_string are functions from the CS50 library that prompt the user for input and return the value as an integer, float, or string, respectively.

int num = get_int("Enter an integer: ");
float pi = get_float("Enter a float: ");
string name = get_string("Enter a string: ");

You must include the cs50.h library to use these functions.

scanf

scanf reads input from the user and stores it in a variable:

int num;
scanf("%i", &num);

The & operator is used to get the memory address of the variable.


Loops and Conditionals

if Statements

if statements are used to execute a block of code if a condition is true. You can also use else if and else to specify alternative conditions.

if (x < y)
{
    printf("x is less than y\n");
}
else if (x > y)
{
    printf("x is greater than y\n");
}
else
{
    printf("x is equal to y\n");
}

for Loops

for loops are used to execute a block of code a specified number of times. The loop has three parts: initialization, condition, and update.

for (int i = 0; i < 10; i++)
{
    printf("%i\n", i);
}

while Loops

while loops are used to execute a block of code as long as a condition is true. It is important to update the condition inside the loop to avoid an infinite loop.

int i = 0;
while (i < 10)
{
    printf("%i\n", i);
    i++;
}

do while loops

do while loops are similar to while loops, but the condition is checked at the end of the loop. This means that the loop will always execute at least once.

int input;
do
{
    input = get_int("Enter an integer: ");
}
while (input < 0)

Functions

Function Declaration

To declare a function, you need to specify the return type (e.g., int), function name (e.g., add), and parameters (if any). For each parameter, you need to specify the type and name.

int add(int a, int b);

Function Definition

Below is an example of a function definition that adds two integers and returns the result.

int add(int a, int b)
{
    return a + b;
}

Function Call

If a function returns a value, you can store the result in a variable.

int sum = add(2, 3);

However, if the function does not return a value, you can call it like this:

void print_hello(void)
{
    printf("Hello!\n");
}

int main(void)
{
    print_hello();
}

Function Prototypes

To use a function before it is defined, you can declare a function prototype at the beginning of the file.

// function prototype
int add(int a, int b);

// main function
int main(void)
{
    int sum = add(2, 3);
    printf("%i\n", sum);
}

// full function definition
int add(int a, int b)
{
    return a + b;
}

Arrays

Array Declaration

You can declare an array by specifying the data type and the number of elements in the array.

int numbers[5];

Array Initialization

You can initialize an array by specifying the values of the elements.

int numbers[5] = {1, 2, 3, 4, 5};

You can also initialize an array with a for loop.

int numbers[5];
for (int i = 0; i < 5; i++)
{
    numbers[i] = i + 1;
}

Accessing Array Elements

You can access elements of an array using the index (starting from 0).

int numbers[5] = {1, 2, 3, 4, 5};
printf("%i\n", numbers[0]); // prints 1
printf("%i\n", numbers[2]); // prints 3

Array Length

You can get the length of an array using the sizeof operator.

int numbers[5] = {1, 2, 3, 4, 5};
int length = sizeof(numbers) / sizeof(numbers[0]);
printf("%i\n", length); // prints 5

Multidimensional Arrays

You can create multidimensional arrays by specifying the number of rows and columns.

int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

To access elements of a multidimensional array, you need to specify the row and column.

int element = matrix[1][2]; // gets the element in the second row and third column (6)

Strings as Arrays

Strings in C are arrays of characters. You can declare a string by specifying the characters enclosed in double quotes.

char name[6] = "Alice";

String Array Functions

You can use string functions from the string.h library to manipulate strings.

  • strlen - get the length of a string
  • strcpy - copy one string to another
  • strcat - concatenate two strings
  • strcmp - compare two strings
#include <string.h>

int main(void)
{
    char name[] = "Alice";
    int length = strlen(name);
    printf("%i\n", length); // prints 5
}

Here is an example of using the strcpy function:

#include <string.h>

int main(void)
{
    char source[] = "Hello";
    char destination[6];
    strcpy(destination, source);
    printf("%s\n", destination); // prints "Hello"
}

Structs

Struct Declaration

A struct is a user-defined data type that allows you to group related data together. You can define a struct by specifying the data members inside the struct.

typedef struct
{
    string name;
    int age;
} person;

Struct Initialization

You can initialize a struct by specifying the values of the data members.

person p;
p.name = "Alice";
p.age = 30;

You can also initialize a struct using a compound literal.

person p = {"Alice", 30};

Accessing Struct Members

You can access the members of a struct using the dot operator.

printf("%s is %i years old\n", p.name, p.age);

Struct Array

You can create an array of structs by specifying the number of elements in the array.

person people[3];
for (int i = 0; i < 3; i++)
{
    people[i].name = get_string("Name: ");
    people[i].age = get_int("Age: ");
}

Struct Functions

You can define functions that take structs as parameters or return structs.

person create_person(string name, int age)
{
    person p;
    p.name = name;
    p.age = age;
    return p;
}

Struct Exercise

#include <cs50.h>
#include <stdio.h>

// defining a candidate
typedef struct
{
    string name;
    float prob;
} candidate;

// uses candidate after the definition
candidate get_candidate();

int main(void)
{
    candidate arr[3];

    for(int i = 0; i < 3; i++)
    {
        arr[i] = get_candidate();
    }

    for(int i = 0; i < 3; i++)
    {
        printf("%s has a probability of winning of %f\n", arr[i].name, arr[i].prob);
    }
}

candidate get_candidate()
{
    candidate new;
    new.name = get_string("Name: ");
    new.prob = get_float("Probability: ");

    return new;
}


Runtime Analysis

Big O Notation

Big O notation is used to describe the performance of an algorithm in terms of its input size. It provides an upper bound on the growth rate of the algorithm.

  • O(1) - constant time
  • O(log n) - logarithmic time
  • O(n) - linear time
  • O(n log n) - linearithmic time
  • O(n^2) - quadratic time
  • O(2^n) - exponential time

Big O can be thought of in terms of the worst-case scenario or the scaling factor of the algorithm.

  • worst-case scenario - the maximum number of operations required for the worst input.
  • scaling factor - how the number of operations grows as the input size increases.

Big O Examples

  • O(1) - accessing an element in an array by index
  • O(n) - linear search
  • O(n^2) - bubble sort or selection sort
  • O(log n) - binary search or merge sort

Best, Worst, and Average Case

  • Best Case (Ω) - the minimum number of operations required for the best input.
    • For example, the best case for linear search is when the element is found at the beginning of the list (Ω(n)).
  • Worst Case (O) - the maximum number of operations required for the worst input.
    • For example, the worst case for linear search is when the element is not found in the list (O(n)).
  • Average Case (Θ) - the average number of operations required for all possible inputs.
    • For example, the average case for linear search is when the element is found in the middle of the list (Θ(n)).

Memory

Hexadecimal Numbers

Hexadecimal numbers are often used to represent memory addresses. They are base-16 numbers that use the digits 0-9 and the letters A-F.

Some examples of hexadecimal numbers are:

  • 0x0 - 0
  • 0x1 - 1
  • 0x9 - 9
  • 0xA - 10
  • 0xF - 15
  • 0x10 - 16
  • 0x1F - 31
  • 0x100 - 256

Memory Addresses

Memory addresses are unique identifiers for locations in memory. They are used to store and retrieve data in a computer’s memory.

int x = 5;
printf("%p\n", &x); // prints the memory address of x

Pointers

A pointer is a variable that stores the memory address of another variable. Pointers are used to work directly with memory addresses and can be used to create complex data structures.

int x = 5;
int *p = &x;
// p now stores the memory address of x

Pointer Arithmetic

You can perform arithmetic operations on pointers to navigate through memory.

int arr[5] = {1, 2, 3, 4, 5};
int *p = arr;

printf("%i\n", *p); // prints 1
printf("%i\n", *(p + 1)); // prints 2

Pointer Functions

You can pass pointers to functions to modify the value of a variable.

void increment(int *x)
{
    *x += 1;
}

int main(void)
{
    int num = 5;
    increment(&num);
    printf("%i\n", num); // prints 6
}

malloc

malloc allocates memory on the heap and returns a pointer to the allocated memory.

For example, to allocate memory for an integer and assign a value to it:

int *x = malloc(sizeof(int));
*x = 5;

realloc

realloc changes the size of a previously allocated block of memory.

For example, to reallocate memory for an array of integers and assign values to them:

int *arr = malloc(5 * sizeof(int));
for (int i = 0; i < 5; i++)
{
    arr[i] = i + 1;
}

arr = realloc(arr, 10 * sizeof(int));
for (int i = 5; i < 10; i++)
{
    arr[i] = i + 1;
}

free

free deallocates memory on the heap.

int *x = malloc(sizeof(int));
// do something with x
free(x);

NOTE: Always remember to free memory that you have allocated to avoid memory leaks.

Memory Leaks

Memory leaks occur when memory is allocated but not deallocated, leading to a loss of available memory over time.

int *x = malloc(sizeof(int));
// do something with x
// forgot to free x

Dangling Pointers

Dangling pointers occur when a pointer points to memory that has been deallocated.

int *x = malloc(sizeof(int));
free(x);
// x is now a dangling pointer

*x = 5; // error: accessing memory that has been deallocated

Swap Function

You can use pointers to swap two variables.

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main(void)
{
    int x = 2;
    int y = 3;
    swap(&x, &y);
    printf("x = %i, y = %i\n", x, y); // prints "x = 3, y = 2"
}

File I/O

Opening a File

You can open a file using the fopen function.

FILE *f = fopen("file.txt", "r");

The second argument specifies the mode in which the file is opened:

  • "r" - read mode
  • "w" - write mode
  • "a" - append mode

Reading from a File

You can read data from a file using the fread function.

char buffer[100];
fread(buffer, 1, 100, f);

The first argument is the buffer where the data will be stored, the second argument is the size of each element to be read, the third argument is the number of elements to be read, and the fourth argument is the file pointer.

Writing to a File

You can write data to a file using the fwrite function.

char buffer[100] = "Hello, world!";
fwrite(buffer, 1, 100, f);

Closing a File

You should always close a file after you are done using it.

fclose(f);

File I/O Example

Here is an example of reading data from a file and printing it to the terminal.

#include <stdio.h>

int main(void)
{
    FILE *f = fopen("file.txt", "r");
    char buffer[100];
    fread(buffer, 1, 100, f);
    printf("%s\n", buffer);
    fclose(f);
}

Data Structures

Stacks and Queues

  • Stack - a data structure that follows the Last In, First Out (LIFO) principle. Elements are added and removed from the top of the stack.
    • Operations: push (add), pop (remove), peek (get top element)
  • Queue - a data structure that follows the First In, First Out (FIFO) principle. Elements are added at the rear and removed from the front of the queue.
    • Operations: enqueue (add), dequeue (remove), peek (get front element)

Linked Lists

A linked list is a data structure that consists of nodes linked together by pointers. Each node contains data and a pointer to the next node.

typedef struct node
{
    int data;
    struct node *next;
} node;

Linked List Functions

You can define functions to manipulate linked lists, such as adding nodes, deleting nodes, and searching for nodes.

node *create_node(int data)
{
    node *new = malloc(sizeof(node));
    new->data = data;
    new->next = NULL;
    return new;
}

void insert_node(node **head, int data)
{
    node *new = create_node(data);
    new->next = *head;
    *head = new;
}

void delete_node(node **head, int data)
{
    node *current = *head;
    node *prev = NULL;

    while (current != NULL)
    {
        if (current->data == data)
        {
            if (prev == NULL)
            {
                *head = current->next;
            }
            else
            {
                prev->next = current->next;
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

Trees

A tree is a hierarchical data structure that consists of nodes connected by edges. Each node has a parent and zero or more children.

typedef struct tree_node
{
    int data;
    struct tree_node *left;
    struct tree_node *right;
} tree_node;

Dictionaries

A dictionary is a data structure that stores key-value pairs. It allows you to quickly retrieve the value associated with a given key.

typedef struct dictionary
{
    char *key;
    int value;
    struct dictionary *next;
} dictionary;

Hash Tables

A hash table is a data structure that uses a hash function to map keys to values. It provides fast access to values based on their keys.

typedef struct hash_table
{
    int size;
    dictionary **table;
} hash_table;

You will need to a function that generates a hash value for a given key and a function that inserts a key-value pair into the hash table.

unsigned int hash(const char *word)
{
    return toupper(word[0]) - 'A';
}

Tries

A trie is a data structure that stores a set of strings. It allows you to quickly search for a string in the set.

typedef struct trie_node
{
    bool is_word;
    struct trie_node *children[26];
} trie_node;