Question? Leave a message!




Data Structures and Algorithms PPT

data structures and algorithms book pdf free download
GeorgeThomson Profile Pic
GeorgeThomson,Greenland,Professional
Published Date:09-07-2017
Your Website URL(Optional)
Comment
Data Structures and Algorithms Jennifer Rexford The material for this lecture is drawn, in part, from The Practice of Programming (Kernighan & Pike) Chapter 2 1 Motivating Quotations “Every program depends on algorithms and data structures, but few programs depend on the invention of brand new ones.” Kernighan & Pike “I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” Linus Torvalds 2 Goals of this Lecture •  Help you learn (or refresh your memory) about: •  Common data structures and algorithms •  Why? Shallow motivation: •  Provide examples of pointer-related C code •  Why? Deeper motivation: •  Common data structures and algorithms serve as “high level building blocks” •  A power programmer: •  Rarely creates programs from scratch •  Often creates programs using building blocks 3 A 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 •  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) •  For simplicity, allow duplicate keys (client responsibility) •  In Assignment 3, must check for duplicate keys 4 Data Structures and Algorithms • Data structures •  Linked list of key/value pairs •  Hash table of key/value pairs • Algorithms •  Create: Create the data structure •  Add: Add a key/value pair •  Search: Search for a key/value pair, by key •  Free: Free the data structure 5 Data Structure 1: Linked List •  Data structure: Nodes; each contains key/value pair and pointer to next node "Mantle" "Gehrig" "Ruth" 7 4 3 NULL •  Algorithms: •  Create: Allocate Table structure to point to first node •  Add: Insert new node at front of list •  Search: Linear search through the list •  Free: Free nodes while traversing; free Table structure 6 Linked List: Data Structure struct Node const char key; int value; struct Node next; ; struct Table struct Node first; ; struct struct struct Node Node Table "Gehrig" "Ruth" 4 3 NULL 7 Linked List: Create (1) 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(); … t 8 Linked List: Create (2) 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(); … t NULL 9 Linked 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; … These are Table_add(t, "Ruth", 3); pointers to Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); strings … t "Gehrig" "Ruth" 4 3 NULL 10 Linked 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; … p Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); … t "Gehrig" "Ruth" 4 3 NULL 11 Linked 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; … p Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); "Mantle" … 7 t "Gehrig" "Ruth" 4 3 NULL 12 Linked 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; … p Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); "Mantle" … 7 t "Gehrig" "Ruth" 4 3 NULL 13 Linked 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; … p Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); "Mantle" … 7 t "Gehrig" "Ruth" 4 3 NULL 14 Linked 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; struct Table t; return 0; int value; int found; … found = Table_search(t, "Gehrig", &value); … t "Mantle" "Gehrig" "Ruth" 7 4 3 NULL 15 Linked 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; struct Table t; return 0; int value; int found; … found = Table_search(t, "Gehrig", &value); … p t "Mantle" "Gehrig" "Ruth" 7 4 3 NULL 16 Linked 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; struct Table t; return 0; int value; int found; … found = Table_search(t, "Gehrig", &value); … p t "Mantle" "Gehrig" "Ruth" 7 4 3 NULL 17 Linked List: Search (4) 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; struct Table t; return 0; int value; int found; … found = Table_search(t, "Gehrig", &value); … p t "Mantle" "Gehrig" "Ruth" 7 4 3 NULL 18 Linked List: Search (5) 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; struct Table t; return 0; int value; int found; … found = Table_search(t, "Gehrig", &value); … p t "Mantle" "Gehrig" "Ruth" 7 4 3 NULL 19 Linked List: Search (6) 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; struct Table t; return 0; int value; int found; … found = Table_search(t, "Gehrig", &value); … 1 p 4 t "Mantle" "Gehrig" "Ruth" 7 4 3 NULL 20