Data Structures and AlgorithmsMotivating QuotationGoals of this LectureA Common TaskSlide 5Data Structure #1: Linked ListLinked List: Data StructureLinked List: Create (1)Linked List: Create (2)Linked List: Create (3)Linked List: Create (4)Linked List: Add (1)Linked List: Add (2)Linked List: Add (3)Linked List: Add (4)Linked List: Add (5)Linked List: Add (6)Linked List: Search (1)Linked List: Search (2)Linked List: Search (3)Linked List: Search (4)Linked List: Search (5)Linked List: Free (1)Linked List: Free (2)Linked List: Free (3)Linked List: Free (4)Linked List: Free (5)Linked List: Free (6)Linked List: Free (7)Linked List: Free (8)Linked List: Free (9)Linked List PerformanceData Structure #2: Hash TableHash Table ExampleHow Large an Array?What Kind of Hash Function?Hashing String Keys to IntegersImplementing Hash FunctionSlide 39Hash Table Example (cont.)Slide 41Slide 42Slide 43Slide 44Slide 45Hash Table: Data StructureHash Table: Create (1)Hash Table: Create (2)Hash Table: Create (3)Hash Table: Create (4)Hash Table: Add (1)Hash Table: Add (2)Hash Table: Add (3)Hash Table: Add (4)Hash Table: Add (5)Hash Table: Add (6)Hash Table: Search (1)Hash Table: Search (2)Hash Table: Search (3)Hash Table: Search (4)Hash Table: Search (5)Hash Table: Search (6)Hash Table: Free (1)Hash Table: Free (2)Hash Table: Free (3)Hash Table: Free (4)Hash Table: Free (5)Hash Table: Free (6)Hash Table PerformanceKey OwnershipKey Ownership (cont.)Slide 72SummaryAppendix 1Revisiting Hash FunctionsRecall: Bitwise Operators in CA Faster Hash FunctionSpeeding Up Key ComparisonsAppendix 2: Another Data StructureExpanding ArrayExpanding Array: Data StructureExpanding Array: Create (1)Expanding Array: Create (2)Expanding Array: Create (3)Expanding Array: Create (4)Expanding Array: Create (5)Expanding Array: Add (1)Expanding Array: Add (2)Expanding Array: Add (3)Expanding Array: Add (4)Expanding Array: Add (5)Expanding Array: Search (1)Expanding Array: Search (2)Expanding Array: Search (3)Expanding Array: Search (4)Expanding Array: Search (5)Expanding Array: Free (1)Expanding Array: Free (2)Expanding Array: Free (3)Expanding Array: Free (4)Expanding Array: Free (5)Expanding Array Performance1Data 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 harder3Goals 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)5Data 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"7Linked 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();…9Linked 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();…11Linked 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 section13Linked 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",
View Full Document