Week 4

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

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

The notation for running time includes:

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

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

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

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

Stepping into the swap function, we see that a and b are indeed the right values. But when we get back to main, x and y are still the same.

It turns out that programs are given memory by the operating system, and areas of memory are set aside in a fairly standard way:

Then we have something we call the stack. The "bottom" of our computer’s memory, or the area with high addresses, is used for functions. In fact, for our C programs, the very bottom of the stack contains a chunk of memory for our main function, with any local variables or arguments:

And we can realize that each block, or byte, is individually addressed and stores some value, which explains what we saw earlier:

And once swap returns, its part of the stack is marked as usable (since it’s returned), so main still sees the same x and y.

And when we were comparing s and t earlier, we were actually comparing two memory addresses. When we call get_string(), we’re actually storing the characters of the string somewhere else in memory (since we don’t know how big the string will be). For example, if we called get_string and the user typed in Zamyla, the characters might be stored in memory starting at address 123. (Recall that a string is just an array of characters, each one in a byte in a consecutive set of bytes.) So our s will have the value 123.

And when we call get_string again for another string, t, whatever the user types in will be stored somewhere else in memory, regardless of its contents. So t might have the value 234 if the second string was stored starting at byte 234. (And this address is "dynamically allocated" by a C library, since we don’t necessarily know ahead of time how big the string will be.)

When we tried to capitalize just one string, too, we were just setting t to the address of the string s was pointing to:

In fact, we can think of both s and t as "pointers" to values that we care about. So in the end, what we knew as a string type was really just a pointer to a character (the start of a "string"). (And recall that we recognize the end of a string by the \0 character, so we don’t need to store the length or the ending address.)

So how might we compare a string?

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

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

    printf("t: ");
    char *t = get_string();

    if (s != NULL && t != NULL)
    {
        if (strcmp(s, t) == 0)
        {
            printf("same\n");
        }
        else
        {
            printf("different\n");
        }
    }
}

To make a copy of a string, we do something a little fancier:

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

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

    char *t = malloc((strlen(s) + 1) * sizeof(char));
    if (t == NULL)
    {
        return 1;
    }

    for (int i = 0, n = strlen(s); i <= n; i++)
    {
        t[i] = s[i];
    }

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

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

    free(t);

    return 0;
}