Announcements and Demos
-
Fifth Monday is on 10/7! This is the deadline for changing your grading status in the course. Switching to SAT/UNS or Pass/Fail requires a signature, so please do approach David, Rob, or Lauren if you need.
Pointers
noswap.c
-
Pointers are one of the more complex topics we cover, so don’t feel bad if your mind feels stretched in the next few weeks. That’s a good thing!
-
Recall last time we ended with a function that didn’t live up to its name:
#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; }
-
Though we expected to see
x
andy
have the values 2 and 1, respectively, we actually saw that they still had their original values 1 and 2. -
To see why this doesn’t work, let’s bring a volunteer onstage. We’ll ask her to pour orange juice and milk into two separate glasses representing two different
int
. If we ask her to swap the orange juice and milk, she wisely chooses to use another glass. This glass represents some temporary storage which we calltmp
in theswap
function above. Interestingly, if we implement the same code directly inmain
, the swapping actually works:#include <stdio.h> int main(void) { int x = 1; int y = 2; printf("x is %i\n", x); printf("y is %i\n", y); printf("Swapping...\n"); int tmp = x; x = y; y = tmp; printf("Swapped!\n"); printf("x is %i\n", x); printf("y is %i\n", y); }
-
So why does this logic work in
main
but not inswap
?a
andb
are actually copies ofx
andy
, so when we swapa
andb
,x
andy
are unchanged. -
One way to fix this would be to make
x
andy
global variables, declaring them outside ofmain
. Infifteen.c
, it made sense to make certain variables global because they were to be used by the whole program. However, in a small program likenoswap.c
, using global variables is sloppy design.
swap.c
-
How can we change the definition of
swap
to work as intended? Turns out we just need to add asterisks:void swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; }
-
What is an
int*
? It’s the memory address of anint
. More properly speaking, it is a pointer to anint
. If your computer has 2 gigabytes of RAM, then there are 2 billion bytes, each of which has a memory address. Let’s say theint
thata
points to is stored at the 123rd byte of RAM. The value ofa
then, is 123. To get at the actual integer value that’s stored at byte 123, we write*a
.*a = *b
says "store at locationa
whatever is at locationb
." -
Now that we’ve changed
swap
, we need to change how we callswap
. Instead of passingx
andy
, we want to pass the address ofx
and the address ofy
:swap(&x, &y)
-
&
is the "address-of" operator and*
is the dereference operator. -
Let’s assume our integers 1 and 2 are stored next to each other in memory and 1 is stored at byte 123. That means 2 is stored 4 bytes away (since an
int
requires 4 bytes), so we’ll assume that it’s stored at byte 127. The values ofa
andb
, then, are 123 and 127. We can simulate passing those toswap
by writing them on pieces of paper and putting them in a black box. -
We ask a volunteer to come onstage and retrieve the pieces of paper from the black box. Next he needs to allocate a little bit of memory for variable
tmp
. Intmp
, he stores the value of theint
whose address is ina
. This is 1. -
Next, at address 123, he erases the number 1 and writes in the number 2. This corresponds to the
*a = *b
line, which says "store at locationa
whatever is at locationb
." -
Finally, at address 127, he erases the number 2 and writes in the number 2, which was stored in
tmp
.tmp
is a local variable, but goes away whenswap
returns.
compare-0.c
-
For the first few weeks, we have worked with
string
as a data type. However, this is a type that we defined for you in the CS50 Library. Astring
is really achar*
. It’s the address of achar
. In fact, it’s the address of the firstchar
in the string. -
Consider the following program which claims to compare two strings:
#include <cs50.h> #include <stdio.h> int main(void) { // get line of text printf("Say something: "); string s = GetString(); // get another line of text printf("Say something: "); string t = GetString(); // try (and fail) to compare strings if (s == t) { printf("You typed the same thing!\n"); } else { printf("You typed different things!\n"); } }
-
Here, we simply ask the user for two strings and store them in
s
andt
. Then we ask ifs == t
. Seems reasonable, no? We’ve used the==
operator for all the other data types we’ve seen thus far. -
But if we compile and run this program, typing "hello" twice, we always get "You typed different things!"
-
Recall that a string is just an array of characters, so "hello" looks like this in memory:
h
e
l
l
o
\0
-
Although we’re able to access the first character "h" using bracket notation, under the hood it’s really located at one of 2 billion or so memory addresses. Let’s call it address 123 again. Then "e" is at address 124, "l" is at address 125, and so on. A
char
only takes 1 byte, so this time the memory addresses are only 1 apart. -
If
GetString
is getting us this string, then what does it actually return? The number 123! Before it does so, it allocates the memory necessary to store "hello" and inserts those characters along with the null terminator. -
But if we only know the memory address of the first character, how do we know how long the string is? Recall that strings end with the special
\0
character, so we can just iterate until we find it. -
compare-0.c
is buggy because it’s comparing the memory addresses of the two strings, not the strings themselves. Maybes
is stored at memory address 123 andt
is stored at memory address 200. Since 123 does not equal 200, our program says they’re different strings.
copy-0.c
-
Let’s take a look at a program that tries, but fails to copy a string:
#include <cs50.h> #include <ctype.h> #include <stdio.h> #include <string.h> int main(void) { // get line of text printf("Say something: "); string s = GetString(); if (s == NULL) { return 1; } // try (and fail) to copy string string t = s; // change "copy" printf("Capitalizing copy...\n"); if (strlen(t) > 0) { t[0] = toupper(t[0]); } // print original and "copy" printf("Original: %s\n", s); printf("Copy: %s\n", t); }
-
We check that
s
isn’tNULL
in case the user has given us more characters than we have memory for.NULL
is actually the memory address 0. By convention, no user data can ever be stored at byte 0, so if a program tries to access this memory address, it will crash. -
Now that we have the user-provided string in
s
, we assign the value ofs
tot
. But ifs
is just a memory address, say 123, thent
is now the same memory address. Boths
andt
are pointing to the same chunks of memory. -
To prove that this program is buggy, we’ll try to capitalize
t
, but nots
. The output, though, shows that boths
andt
are capitalized. -
To emphasize that their role is to point to other variables, pointers are often represented as arrows.
compare-1.c
-
Finally, a program that truly compares two strings:
#include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { // get line of text printf("Say something: "); char* s = GetString(); // get another line of text printf("Say something: "); char* t = GetString(); // try to compare strings if (s != NULL && t != NULL) { if (strcmp(s, t) == 0) { printf("You typed the same thing!\n"); } else { printf("You typed different things!\n"); } } }
-
Now that we know a
string
is really just achar*
, we need to be careful it’s notNULL
. -
strcmp
is short for "string compare." It’s a function that comes instring.h
, which, according to the man page, returns 0 if two strings are identical, a negative number if the first string argument comes before the second string alphabetically, or a positive number if the first string argument comes after the second string alphabetically.
copy-1.c
-
Copying a string is a little more complicated than just using the assignment operator:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
#include <cs50.h> #include <ctype.h> #include <stdio.h> #include <string.h> int main(void) { // get line of text printf("Say something: "); char* s = GetString(); if (s == NULL) { return 1; } // allocate enough space for copy char* t = malloc((strlen(s) + 1) * sizeof(char)); if (t == NULL) { return 1; } // copy string, including '\0' at end int n = strlen(s); for (int i = 0; i <= n; i++) { t[i] = s[i]; } // change copy printf("Capitalizing copy...\n"); if (strlen(t) > 0) { t[0] = toupper(t[0]); } // print original and copy printf("Original: %s\n", s); printf("Copy: %s\n", t); // success return 0; }
-
In line 17, we’re declaring a pointer
t
and initializing it with the return value of a function namedmalloc
.malloc
takes a single argument, the number of bytes of memory requested, and returns the address in memory of the first of those bytes orNULL
if the memory couldn’t be allocated. -
In this case, we’re allocating enough memory for all the characters in
s
plus 1 extra for the null terminator. We multiply this number of characters bysizeof(char)
, which gives the size in bytes of achar
on this particular operating system. Normally it will be 1, but we’re handling other cases correctly, too. -
Once we have enough memory, we iterate through all of the characters in
s
and assign them one at a time tot
.
Teaser
-
Let’s analyze some seemingly innocuous lines of code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
int main(void) { int* x; int* y; x = malloc(sizeof(int)); *x = 42; *y = 13; y = x; *y = 13; }
-
First, we declare two pointers
x
andy
. We allocate enough memory to store anint
and assign its address tox
. We store the value 42 in this memory. Then we store in the memory addressy
the value 13. But wait, we didn’t allocate memory for a secondint
, so what doesy
point to? Who knows! That’s the problem. Line 10 is pretty painful for Binky.