1 of 58

This is CS50

2 of 58

Agenda

  • Data Structures and Trade Offs
  • Linked Lists
    • Review
    • Exercise
  • Hash Tables
    • Review
    • Hash Function Example
  • Inheritance

3 of 58

Deletion

Insertion

Search

4 of 58

  • Search
  • Insertion
  • Deletion

5 of 58

  • Insertion
  • Search
  • Deletion

6 of 58

"Hi!"

NULL

"Hey!"

list

Linked List

7 of 58

…

H

I

J

K

L

…

"Hey!"

"Hello!"

"Lo there!"

Hash Table

8 of 58

H

E

L

L

O

Y

Trie

P

9 of 58

Trade-offs

10 of 58

11 of 58

12 of 58

Nodes

13 of 58

typedef struct node

{

string phrase;

struct node *next;

}

node;

14 of 58

typedef struct node

{

string phrase;

struct node *next;

}

node;

node

15 of 58

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

node

16 of 58

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

"Hi!"

node

17 of 58

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

"Bye!"

node

18 of 58

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

next

node

19 of 58

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

0x123

next

node

20 of 58

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

0x456

next

node

21 of 58

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

next

node

22 of 58

Creating a Linked List

23 of 58

node *list = NULL;

list

24 of 58

node *n = malloc(sizeof(node));

list

25 of 58

node *n = malloc(sizeof(node));

list

26 of 58

node *n = malloc(sizeof(node));

n

list

27 of 58

node *n = malloc(sizeof(node));

n->phrase = "Hi!";

"Hi!"

n

list

28 of 58

node *n = malloc(sizeof(node));

n->phrase = "Hi!";

n->next = NULL;

"Hi!"

NULL

n

list

29 of 58

list = n;

"Hi!"

NULL

n

list

30 of 58

list = n;

"Hi!"

NULL

n

list

31 of 58

Inserting Nodes

32 of 58

n = malloc(sizeof(node));

"Hi!"

NULL

list

33 of 58

n = malloc(sizeof(node));

"Hi!"

NULL

list

n

34 of 58

n = malloc(sizeof(node));

n->phrase = "Hey!";

"Hi!"

NULL

list

"Hey!"

n

35 of 58

n = malloc(sizeof(node));

n->phrase = "Hey!";

n->next = list;

"Hi!"

NULL

list

"Hey!"

n

36 of 58

list = n;

"Hi!"

NULL

"Hey!"

list

n

37 of 58

list = n;

"Hi!"

NULL

"Hey!"

list

38 of 58

"Hi!"

NULL

"Hey!"

list

39 of 58

free(list);

"Hi!"

NULL

"Hey!"

list

40 of 58

free(list);

"Hi!"

NULL

"Hey!"

list

41 of 58

"Hi!"

NULL

"Hey!"

list

42 of 58

node *ptr = list->next;

"Hi!"

NULL

"Hey!"

list

ptr

43 of 58

free(list);

"Hi!"

NULL

"Hey!"

ptr

list

44 of 58

list = ptr;

"Hi!"

NULL

"Hey!"

ptr

list

45 of 58

list = ptr;

"Hi!"

NULL

ptr

list

46 of 58

ptr = list->next;

"Hi!"

NULL

ptr

list

47 of 58

ptr = list->next;

"Hi!"

NULL

list

48 of 58

free(list);

"Hi!"

NULL

list

49 of 58

list = ptr;

list

50 of 58

Inserting and Unloading a Linked List

Download and open list.c at cs50.ly/supersection1.

  • TODO: implement code to add a node to the linked list. Ensure that list always points to the head of the linked list. Also ensure your new node contains a phrase.
  • TODO: implement unload such that all nodes in the linked list are free'd when the function is called. Return true when successful.

51 of 58

"Hey!"

"Hello!"

"Lo there!"

52 of 58

…

H

I

J

K

L

…

"Hey!"

"Hello!"

"Lo there!"

53 of 58

…

…

7

H

8

I

9

J

10

K

11

L

…

…

"Hey!"

"Hello!"

"Lo there!"

54 of 58

Hash Function

"Hey!"

7

55 of 58

Hashing

Download and open table.c at cs50.ly/supersection2.

TODO: complete hash to return a number, 0–25, depending on the first character in the word.

We will walk through it together!

56 of 58

A good hash function…

Always gives you the same value for the same input

Produces an even distribution across buckets

Uses all buckets

​

57 of 58

Inheritance

58 of 58

This was CS50