Week 5

Topics

  • Linked Lists
  • Hash Tables
  • Trees
  • Stacks, Queues

Programming Exercises

Below are a few example programming exercises that engage students in hands-on practice on the week’s topics. Keep in mind that class might not be long enough to include all exercises, so be sure to pick just a few! For this week, in particular, you might choose one exercise from each of these topics.

  • Add to the Head of a Linked List
    • Write a program that prompts the user to type in integers, adds each integer one at a time to the head of a linked list, and then prints out the integers in the linked list (they’ll be in reverse order from the input).
    • Note: When running the program, press Ctrl-D to stop entering numbers.
    • Distribute the following code to students, and work through the TODOs one at a time. 
      #include <cs50.h>
#include <stdio.h>

typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(void)
{
    node *list = NULL;

    while (true)
    {
        int x = get_int("Number: ");
        if (x == INT_MAX)
        {
            printf("\n");
            break;
        }

        // TODO: Allocate a new node.
                // TODO: Add new node to head of linked list.

    }

    // TODO: Print all nodes.
    // TODO: Free all nodes.

}
    • Solution to Allocate a new node. 
      node *n = malloc(sizeof(node));
n->number = x;
n->next = NULL;
    • Solution to Add new node to head of linked list. 
      n->next = list;
list = n;
    • Solution to Print all nodes. 
      for (node *ptr = list; ptr != NULL; ptr = ptr->next)
{
    printf("%i\n", ptr->number);
}
    • Solution to Free all nodes. 
      node *ptr = list;
while (ptr != NULL)
{
    node *tmp = ptr;
    ptr = ptr->next;
    free(tmp);
}
  • Add to the End of a Linked List
    • Modify the example above to add new nodes to the end of a linked list, rather than the beginning. As a result, the list of numbers should now print out in order, instead of reverse order.
    • Solution to Add new node to end of linked list. 
      if (list == NULL)
{
    list = n;
}
else
{
    node *ptr = list;
    while (ptr->next != NULL)
    {
        ptr = ptr->next;
    }
    ptr->next = n;
}
  • Add to a Linked List in Sorted Order
    • Modify the example above to add new nodes to the linked list such that the linked list is always kept in ascending order.
    • Solution to Add new node in sorted order. 
      if (list == NULL || x < list->number)
{
    n->next = list;
    list = n;
}
else
{
    node *ptr = list;
    while (ptr->next != NULL && x > ptr->next->number)
    {
        ptr = ptr->next;
    }
    n->next = ptr->next;
    ptr->next = n;
}
  • Search a Linked List
    • Implement search in a Linked List
    • Distribution code: list.c 
      #include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    string phrase;
    struct node *next;
}
node;

#define LIST_SIZE 2

bool search(string phrase, node *list);
bool unload(node *list);
void visualizer(node *list);

int main(void)
{
    node *list = NULL;

    // Add items to list
    for (int i = 0; i < LIST_SIZE; i++)
    {
        string phrase = get_string("Enter a new phrase: ");

        // TODO: add phrase to new node in list
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            return 1;
        }
        new_node->phrase = phrase;
        new_node->next = list;
        list = new_node;
    
        // Visualize list after adding a node.
        visualizer(list);
    }

    // Search for phrase in list
    string search_phrase = get_string("Phrase to search for: ");
        
    if (search(search_phrase, list))
    {
        printf("Recognized the phrase.\n");
    }
    else
    {
        printf("Did not recognize the phrase.\n");
    }
    
    // Free all memory used
    if (!unload(list))
    {
        printf("Error freeing the list.\n");
        return 1;
    }
    
    printf("Freed the list.\n");
    return 0;
}


bool search(string phrase, node *list)
{
    // TODO: Search linked list for phrase
    return false;
}

bool unload(node *list)
{
    // Free all allocated nodes
    node *cursor = list;
    node *behind = NULL;

    while (cursor != NULL)
    {
        behind = cursor;
        cursor = cursor->next;
        free(behind);
    }
    return true;
}

void visualizer(node *list)
{
    printf("\n+-- List Visualizer --+\n\n");
    while (list != NULL)
    {
        printf("Location %p\nPhrase: \"%s\"\nNext: %p\n\n", list, list->phrase, list->next);
        list = list->next;
    }
    printf("+---------------------+\n\n");
}
      • Sample Solution ```c #include #include #include #include

      typedef struct node { string phrase; struct node *next; } node;

      #define LIST_SIZE 2

      bool search(string phrase, node *list); bool unload(node *list); void visualizer(node *list);

      int main(void) { node *list = NULL;

      // Add items to list
for (int i = 0; i < LIST_SIZE; i++)
{
    string phrase = get_string("Enter a new phrase: ");

    // TODO: add phrase to new node in list
    node *new_node = malloc(sizeof(node));
    if (new_node == NULL)
    {
        return 1;
    }
    new_node->phrase = phrase;
    new_node->next = list;
    list = new_node;

    // Visualize list after adding a node.
    visualizer(list);
}

// Search for phrase in list
string search_phrase = get_string("Phrase to search for: ");
if (search(search_phrase, list))
{
    printf("Recognized the phrase.\n");
}
else
{
    printf("Did not recognize the phrase.\n");
}

// Free all memory used
if (!unload(list))
{
    printf("Error freeing the list.\n");
    return 1;
}

printf("Freed the list.\n");
return 0; }

      bool search(string phrase, node *list) { // TODO: Search linked list for phrase while (list != NULL) { if (strcmp(phrase, list->phrase) == 0) { return true; }

          list = list->next;
}

return false; }

      bool unload(node *list) { // Free all allocated nodes node *cursor = list; node *behind = NULL;

      while (cursor != NULL)
{
    behind = cursor;
    cursor = cursor->next;
    free(behind);
}

return true; }

      void visualizer(node *list) { printf(“\n+– List Visualizer –+\n\n”); while (list != NULL) { printf(“Location %p\nPhrase: "%s"\nNext: %p\n\n”, list, list->phrase, list->next); list = list->next; } printf(“+———————+\n\n”); } ```

Discussion Questions

One technique to promote participation in class is a quick, 2–3 minute discussion question. Letting students posit their own reasoning, even if they’re not entirely sure of an answer, can help reinforce material from lecture. One model for introducing these questions is the “Think, Pair, Share” approach, in which students take 30 seconds to think of their own answer and 60 seconds to share their answer with a partner. Afterwards, you can call on random pairs to share their thinking with the larger group. It’s also best to follow up with your own answer, too!

  • Imagine you’re developing a data structure that might store English sentences. What trade-offs might arise if you were to store sentences as linked lists, with each node representing one English word? What about if you used a tree or a trie?

Annotated Sample Slides

Here you’ll find sample slides to adopt or adapt when teaching Week 5.

Some slides contain speaker notes to illustrate why the sample slides take a certain approach to illustrating a concept or leading an exercise. You’re welcome to modify these slides as you see fit, though do try to keep some of the same elements of active learning that have been included in these samples.

Past versions of sample slides are also available under the “Additional Slide Resources” dropdown.