Andrew Sellergren
style50 to correct them automatically! It’s not perfect, but it will help you clean up your style.check50 which will check your code for correctness. For example, run check50 -c 2012/pset4/recover recover.c to check your solution to one of Problem Set 4’s assignments. A red sad face indicates that a test failed, a green smiley face indicates that a test passed, and a yellow straight face indicates that a test wasn’t run. Note that the tests aren’t exhaustive: your code isn’t perfect just because it passes all the tests.string is actually a char*. A char* is a pointer to the first character in a string. The rest of the string can be found by iterating until the null terminator (\0) is encountered.Under the hood, GetString was actually using a function named sscanf to get input from the user. Let’s use a similar function on our own to get an integer from the user:
/****************************************************************************
* scanf1.c
*
* David J. Malan
* malan@harvard.edu
*
* Reads a number from the user into an int.
*
* Demonstrates scanf and address-of operator.
***************************************************************************/
#include <stdio.h>
int main(void)
{
int x;
printf("Number please: ");
scanf("%d", &x);
printf("Thanks for the %d!\n", x);
return 0;
}
printf, scanf takes formatting characters like %d as input. We use &x as the second argument instead of just x because we want to pass by reference, not by value. When we pass &x, we’re giving scanf the address of x so that it can fill in the memory with whatever integer it gets from the user. Think of it as drawing a map to a chunk of memory which scanf can follow. To access the memory that a pointer points to, we use the dereferencing operator (*).Oops, we screwed up in scanf2.c:
/****************************************************************************
* scanf2.c
*
* David J. Malan
* malan@harvard.edu
*
* Reads a string from the user into memory it shouldn't.
*
* Demonstrates possible attack!
***************************************************************************/
#include <stdio.h>
int main(void)
{
char* buffer;
printf("String please: ");
scanf("%s", buffer);
printf("Thanks for the \"%s\"!\n", buffer);
return 0;
}
main doing? We’re declaring a variable named buffer that will point to the address of the first character of a string. Two lines later, we’re reading a string into buffer. But wait, we never actually allocated any valid memory to buffer, so we have nowhere to put the string. Not only that, we’re not telling scanf how big buffer is. Without knowing this, it might try to write too much into buffer’s memory and thus overflow it.scanf3.c does a little better:
/****************************************************************************
* scanf3.c
*
* David J. Malan
* malan@harvard.edu
*
* Reads a string from the user into an array (dangerously).
*
* Demonstrates potential buffer overflow!
***************************************************************************/
#include <stdio.h>
int main(void)
{
char buffer[16];
printf("String please: ");
scanf("%s", buffer);
printf("Thanks for the \"%s\"!\n", buffer);
return 0;
}
buffer is actually a chunk of memory (of size 16 bytes). Unfortunately, one of the problems from scanf2.c remains. What if the user types in 17 characters? Or 1 million characters? There’s a good chance it will fail with a segmentation fault. Bugs like these are often hard to track down because they only manifest themselves in certain scenarios. When a segmentation fault occurs, a file named core will be dumped into your present working directory. You can actually open this file with GDB to identify the line on which your program failed. More on this in section.& next to buffer? For our purposes, arrays are effectively pointers. This isn’t true in all contexts, but it’s a reasonable simplification.
To implement a linked list, we’ll borrow some of the syntax we used for structs:
typedef struct node
{
int n;
struct node *next;
}
node;
struct node *next defines a pointer to another node. Because the compiler reads from top to bottom, a node won’t be defined until after all of these lines are executed. Thus, we have to write struct node instead of just node, both before the curly braces and inside the curly braces.Let’s depict the linked list above using volunteers onstage. Each volunteer holds a piece of paper with a number on it (9, 17, 22, 26, or 34) and points to the next node of the list with his or her left hand. One volunteer will hold a piece of paper that reads “first” and will point to the first node of the list. One volunteer (named Anita) will represent a pointer that we’ll use to search the list. To begin with, Anita points to the first node of the list, which has already been allocated:
node* first;
// it's been allocated a list…
node* anita = first;
To search the list for the value 22, Anita points to each node successively and checks if the node’s value equals 22. We might write this prorammatically as follows:
bool find(node* list, int n)
{
node* anita = list;
while (anita != NULL)
{
if ((*anita).n == n)
return true;
anita = (*anita).next;
}
}
*anita to dereference her and get to the struct she’s pointing to. To point her to the next node in the list, we can’t simply write anita++. The memory in a linked list is not contiguous, so the next node in the list is not necessarily right next to where Anita is pointing. Instead, Anita needs to point where the next pointer is pointing.This syntax is a bit of a mess. Thankfully the -> operator is actually a shortcut for * plus .:
bool find(node* list, int n)
{
node* anita = list;
while (anita != NULL)
{
if (anita->n == n)
return true;
anita = anita->next;
}
}
The arrow both dereferences the pointer and accesses the underlying struct it points to. One last line of code needs to be added to this function, though, to ensure its correctness:
bool find(node* list, int n)
{
node* anita = list;
while (anita != NULL)
{
if (anita->n == n)
return true;
anita = anita->next;
}
return false;
}
n we were looking for.Let’s walk through the process of inserting a node into our linked list. To begin with, we need to request memory for a new node, named after our intrepid volunteer Rebecca:
node* rebecca = malloc(sizeof(node));
We should also initialize her:
rebecca->n = 55;
rebecca->next = NULL;
Rebecca belongs at the end of the list, so it’s pretty easy to insert her. We just point the last node of the list to Rebecca and leave Rebecca pointed to NULL.
Next, let’s try inserting Saad, who represents the number 20. As before, we initialize him:
saad->n = 22;
saad->next = NULL;
first points to. Then we update first to point to the new node.In C, we might represent a stack like so:
typedef struct
{
int numbers[CAPACITY];
int size;
}
stack;
size is set to 0 and numbers is filled with garbage values. When we insert a value into the 0th element of numbers, we set size to 1. When we insert a value into the 1st element of numbers, we set size to 2. And so on. When we want to pop a number off the stack, we simply decrement size. We don’t actually have to change any of the values of numbers. When we go to insert another value into numbers, though, we’ll overwrite the previous last value.CAPACITY elements.Our implementation of a queue resembles a stack except for one additional member of the struct:
typedef struct
{
int head;
int numbers[CAPACITY];
int size;
}
head), we avoid having to shift all the elements of the array down every time we remove an element. We don’t actually need to keep the first element of the queue at the 0th index of the array; instead, we know that the first element of the queue is actually stored at the index equal to head, which we constantly update. The price of not having to shift all the elements of the array every time we remove an element is the additional storage required for head.Stacks and queues both have their advantages and disadvantages, but soon we’ll look at a data structure called a hash table that offers the holy grail of lookups: constant time. The important decision we’ll have to make is how big our hash table should be. And to make this decision, we’ll need to answer the following question:
In a room of n CS50 students, what’s the probability that at least 2 students have the > same birthday?