Week 4

Last Time

  • Last time we looked at numbers and how we might search them and sort them, with algorithms like:

    • linear search

    • binary search

    • bubble sort

    • selection sort

    • insertion sort

    • merge sort

  • We started using basic terms to describe running time (in units of steps taken), like:

    • n2

    • n log n

    • n

    • log n

    • 1

    • …​

  • The notation for running time includes:

    • O, worst-case running time

    • Ω, best-case running time

    • Θ, if both of those are the same

Strings

  • Now we’ll take a closer look at strings and how they are actually stored by the computer.

  • Let’s look at compare0.c:

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

int main(void)
{
    printf("s: ");
    string s = get_string();

    printf("t: ");
    string t = get_string();

    if (s == t)
    {
        printf("same\n");
    }
    else
    {
        printf("different\n");
    }
}

    • It looks like this program takes two strings from the user and compares them.

    • But it doesn’t work, when we put in two strings that look the same.

  • Hm, mysterious. Let’s try to copy the string:

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

int main(void)
{
    printf("s: ");
    string s = get_string();
    if (s == NULL)
    {
        return 1;
    }

    string t = s;

    if (strlen(t) > 0)
    {
        t[0] = toupper(t[0]);
    }

    printf("s: %s\n", s);
    printf("t: %s\n", t);

    return 0;
}

    • Now we’re getting a string s from the user, copying it to a string called t, and then making the first letter of t uppercase.

    • But when we run the program, it again doesn’t behave like we might expect. Both s and t are capitalized!

  • Another example we can look at:

    #include <stdio.h>

void swap(int a, int b);

int main(void)
{
    int x = 1;
    int y = 2;

    printf("x is %i\n", x);
    printf("y is %i\n", y);
    printf("Swapping...\n");
    swap(x, y);
    printf("Swapped.\n");
    printf("x is %i\n", x);
    printf("y is %i\n", y);
}

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

    • We have a function called swap that’s supposed to take two values, a and b, and swaps them. It takes a, puts the value into a temporary variable called tmp, and then stores the value of b into a. Then the value of tmp, which is the original a, is stored into b.

    • But when we run this program, too, it doesn’t swap the values of x and y in main.

  • So we open our debugger, and step over each line of our program: