This preview shows page 1-2-3-4-5-6-7-48-49-50-51-52-53-54-97-98-99-100-101-102-103 out of 103 pages.
Data Structures and AlgorithmsSlide 2Goals of this LectureA Common TaskOverviewLinked 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 PerformanceHash TableHash Table (cont.)ExampleHow Large an Array?What Kind of Hash Function?Hashing String Keys to IntegersImplementing Hash FunctionHash Table ExampleHash Table Example (cont.)Slide 42Slide 43Slide 44Slide 45Slide 46Hash 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 73SummaryAppendix 1Revisiting Hash FunctionsBitwise 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 22“Every program depends on algorithms and data structures, but few programs depend on the invention of brand new ones.”-- Kernighan & Pike3Goals of this Lecture•Help you learn (or refresh your memory) about:•Commonly used data structures and associated algorithms•Why? (Shallow motivation)•Provide examples of typical pointer-related C code•Why? (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•Common task•Maintain a table of key/value pairs•Each key is a string; each value is an int•Unknown number of pairs•For simplicity, allow duplicate keys (client responsibility)•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)•Let’s consider data structures and associated algorithms for that task…5Overview•Data structures examined•Linked list of key/value pairs•Hash table of key/value pairs•Associated algorithms examined•Create: Create the data structure•Add: Add a key/value pair•Search: Search for a key/value pair, by key•Free: Free the data structure6Linked List•The general idea…•Data structure: Nodes; each node contains a key/value pair and a pointer to the next node•Create algorithm: Allocate a “dummy” node to point to the first “real” node•Add algorithm: Create a new node; insert at front of list•Search algorithm: Linear search•Free algorithm: Free nodes while traversing; free dummy node7Linked 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", 7);…STACK HEAPt4"Gehrig"3"Ruth"NULLt"Mantle"key7value7"Mantle"p15Linked 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;
View Full Document
Unlocking...