Week 3: Structs and Sorting in C

Hello and welcome to CS50!

We’re onto the third week of C! This week we will be learning about structs and sorting in C. Structs are a powerful data structure that allow you to group related data together. They are used in many different applications, from representing a point in 3D space to representing a student in a database. This week we will be learning how to declare, initialize, and access structs, as well as how to use them in loops and conditionals.

We will also be learning about sorting algorithms, which allow you to arrange data in a specific order. Sorting is an important problem in computer science, and there are many different algorithms that can be used to solve it. This week we will be learning about various searching and sorting algorithms, including selection sort, bubble sort, and merge sort.

Finally, we will be learning about recursion and how to use it to solve problems in C. Recursion is a powerful technique that allows a function to call itself, and it can be used to solve many different types of problems.

Resources:

Section-Specific:

Sections are held Thursdays 9AM-11:45AM in 2 Arrow St. Room 420
Section Slides

Course-wide:

Office Hours:

My Office Hours: Friday 10:30AM-11:30AM in HSA Building 4th Floor
All-Staff Office Hours: Sunday 3-5PM in Widener Library
Office Hours Schedule
- Add this Google Calendar
If you have any questions at all, email me!

Helpful Functions from the CS50 Manual / Documentation

Compare two strings

strcmp(string1, string2);
// returns 0 if the strings are equal
// returns a negative number if string1 is less than string2
// returns a positive number if string1 is greater than string2

For two arrays of strings, you can compare each same-index string in the arrays using a loop:

list1 = ["abcd", "efgh", "iJkl"];
list2 = ["abcd", "eFgh", "ijkl"];

for (int i = 0; i < 3; i++)
{
    // compare two strings
    if(strcmp(list1[i], list2[i]) == 0)
    {
        printf("The strings are equal\n");
    }
    else
    {
        printf("The strings are not equal\n");
    }
}

The above code will compare the strings at index 0, 1, and 2 in the two arrays and print whether they are equal or not. The output will be:

The strings are equal
The strings are not equal
The strings are not equal

Common Patterns for the Problem Set

Loops, nested loops, breaks, returns

// check for a single item to satisfy a condition
for (int i = 0; i < n; i++)
{
    // check condition
    if (condition)
    {
        return true;
        // if the condition is true at least once in the loop, return true
    }
}
return false;
// if the condition is never true in the loop, return false

// nested loop
// check for a condition once within each "row"
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        if (condition)
        {
            break;
            // if the condition is true at least once in the loop, break out of the inner loop
            // and continue to the next "row", skipping the rest of the inner loop
        }
    }
}

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;
}

Recursion with Fibonacci

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

int get_fibonacci_n(int n);

int main(void)
{
    int n = get_int("N: ");
    int fibonacci = get_fibonacci_n(n);
    printf("%i\n", fibonacci);
}

int get_fibonacci_n(int n)
{
    // f(n) = f(n-1) + f(n-2)

    if (n == 0 || n == 1)
    {
        return n;
        // return 0 or 1 if n is either
    }

    return get_fibonacci_n(n - 1) + get_fibonacci_n(n - 2);
}