11Data Structures and AlgorithmsThe material for this lecture is drawn, in part, fromThe Practice of Programming (Kernighan & Pike) Chapter 2Professor Jennifer Rexfordhttp://www.cs.princeton.edu/~jrex2Motivating Quotation“Every program depends on algorithms and data structures, but few programs depend on the invention of brand new ones.”-- Kernighan & PikeCorollary: work smarter, not harder23Goals of this Lecture• Help you learn (or refresh your memory) about:• Commonly used data structures and algorithms• Shallow motivation• Provide examples of typical pointer-related C code• Deeper motivation• Common data structures and algorithms serve as “high level building blocks”• A power programmer:• Rarely creates large programs from scratch• Creates large programs using high level building blocks whenever possible4A Common Task• Maintain a table of key/value pairs• Each key is a string; each value is an int• Unknown number of key-value pairs• For simplicity, allow duplicate keys (client responsibility)• In Assignment #3, must check for duplicate keys!•Examples• (student name, grade)• (“john smith”, 84), (“jane doe”, 93), (“bill clinton”, 81)• (baseball player, number)• (“Ruth”, 3), (“Gehrig”, 4), (“Mantle”, 7)• (variable name, value)• (“maxLength”, 2000), (“i”, 7), (“j”, -10)35Data Structures and Algorithms• Data structures: two ways to store the data• Linked list of key/value pairs• Hash table of key/value pairs• Expanding array of key/value pairs (see Appendix)• Algorithms: various ways to manipulate the data• Create: Create the data structure•Add: Add a key/value pair• Search: Search for a key/value pair, by key•Free: Free the data structure6Data Structure #1: Linked List• Data structure: Nodes; each node contains a key/value pair and a pointer to the next node• Algorithms:• Create: Allocate “dummy” node to point to first real node•Add: Create a new node, and insert at front of list• Search: Linear search through the list•Free: Free nodes while traversing; free dummy node4"Gehrig"3"Ruth"NULL7"Mantle"47Linked List: Data Structurestruct Node {const char *key;int value;struct Node *next;};struct Table {struct Node *first;};8Linked List: Create (1)STACK HEAPtstruct Table *Table_create(void) {struct Table *t;t = (struct Table*)malloc(sizeof(struct Table));t->first = NULL;return t;}struct Table *t;…t = Table_create();…59Linked List: Create (2)STACK HEAPttstruct Table *Table_create(void) {struct Table *t;t = (struct Table*)malloc(sizeof(struct Table));t->first = NULL;return t;}struct Table *t;…t = Table_create();…10Linked List: Create (3)STACK HEAPttNULLstruct Table *Table_create(void) {struct Table *t;t = (struct Table*)malloc(sizeof(struct Table));t->first = NULL;return t;}struct Table *t;…t = Table_create();…611Linked List: Create (4)struct Table *Table_create(void) {struct Table *t;t = (struct Table*)malloc(sizeof(struct Table));t->first = NULL;return t;}struct Table *t;…t = Table_create();…STACK HEAPtNULL12Linked List: Add (1)void Table_add(struct Table *t,const char *key, int value) {struct Node *p = (struct Node*)malloc(sizeof(struct Node));p->key = key;p->value = value;p->next = t->first;t->first = p;}struct Table *t;…Table_add(t, "Ruth", 3);Table_add(t, "Gehrig", 4);Table_add(t, "Mantle", 7);…STACK HEAPt4"Gehrig"3"Ruth"NULLThese are pointers tostrings that exist in the RODATA section713Linked List: Add (2)void Table_add(struct Table *t,const char *key, int value) {struct Node *p = (struct Node*)malloc(sizeof(struct Node));p->key = key;p->value = value;p->next = t->first;t->first = p;}struct Table *t;…Table_add(t, "Ruth", 3);Table_add(t, "Gehrig", 4);Table_add(t, "Mantle", 7);…STACK HEAPt4"Gehrig"3"Ruth"NULLt"Mantle"key7valueThis is a pointer toa string that exists in the RODATA section14Linked List: Add (3)void Table_add(struct Table *t,const char *key, int value) {struct Node *p = (struct Node*)malloc(sizeof(struct Node));p->key = key;p->value = value;p->next = t->first;t->first = p;}struct Table *t;…Table_add(t, "Ruth", 3);Table_add(t, "Gehrig", 4);Table_add(t, "Mantle", 7);…STACK HEAPt4"Gehrig"3"Ruth"NULLt"Mantle"key7value7"Mantle"p815Linked List: Add (4)void Table_add(struct Table *t,const char *key, int value) {struct Node *p = (struct Node*)malloc(sizeof(struct Node));p->key = key;p->value = value;p->next = t->first;t->first = p;}struct Table *t;…Table_add(t, "Ruth", 3);Table_add(t, "Gehrig", 4);Table_add(t, "Mantle", 7);…STACK HEAPt4"Gehrig"3"Ruth"NULLt"Mantle"key7value7"Mantle"p16Linked List: Add (5)void Table_add(struct Table *t,const char *key, int value) {struct Node *p = (struct Node*)malloc(sizeof(struct Node));p->key = key;p->value = value;p->next = t->first;t->first = p;}struct Table *t;…Table_add(t, "Ruth", 3);Table_add(t, "Gehrig", 4);Table_add(t, "Mantle", 7);…STACK HEAPt4"Gehrig"3"Ruth"NULLt"Mantle"key7value7"Mantle"p917Linked List: Add (6)void Table_add(struct Table *t,const char *key, int value) {struct Node *p = (struct Node*)malloc(sizeof(struct Node));p->key = key;p->value = value;p->next = t->first;t->first = p;}struct Table *t;…Table_add(t, "Ruth", 3);Table_add(t, "Gehrig", 4);Table_add(t, "Mantle", 7);…STACK HEAPt4"Gehrig"3"Ruth"NULL7"Mantle"18Linked List: Search (1)int Table_search(struct Table *t,const char *key, int *value) {struct Node *p;for (p = t->first; p != NULL; p = p->next)if (strcmp(p->key, key) == 0) {*value = p->value;return 1;}return 0;}struct Table *t;int value;int found;…found =Table_search(t, "Gehrig", &value);…STACK HEAPt4"Gehrig"3"Ruth"NULL7"Mantle"valuefound1019Linked List: Search (2)int Table_search(struct Table *t,const char *key, int *value) {struct Node *p;for (p = t->first; p != NULL; p = p->next)if (strcmp(p->key, key) == 0) {*value = p->value;return 1;}return 0;}struct Table *t;int value;int found;…found =Table_search(t, "Gehrig", &value);…STACK HEAPt4"Gehrig"3"Ruth"NULL7"Mantle"valuefoundt"Gehrig"keyvalue20Linked List: Search (3)int Table_search(struct Table *t,const char *key, int *value) {struct Node *p;for (p = t->first; p != NULL; p = p->next)if (strcmp(p->key, key) == 0) {*value = p->value;return 1;}return 0;}struct Table *t;int value;int found;…found =Table_search(t, "Gehrig", &value);…STACK HEAPt4"Gehrig"3"Ruth"NULL7"Mantle"valuefoundt"Gehrig"keyvaluep1121Linked List: Search (4)int Table_search(struct Table *t,const char *key, int *value) {struct
View Full Document
Unlocking...