Unformatted text preview:

1CMSC 212 – S05 (lect 12)Announcementsz Midterm #1 – Re-grade requests due by 1:45 PMz Program #2– Due on Tuesdayz Reading– Chapter 12, 10.2 (Today)– Notes (Tuesday)2CMSC 212 – S05 (lect 12)Linked Data Structuresz Like classes with refs to same class in Javaz Have pointers to a struct of the same timez Example Declaration:typedef struct NODE {struct NODE *next;int value;} Node;z Next is a pointer to another Noderoot51015NULL3CMSC 212 – S05 (lect 12)Lookup in a Linked Structureint Lookup(Node *current, int value) {while (current && current->value != new_value) {current = current->next;}if (current) {return 1;} else {return -1;}}4CMSC 212 – S05 (lect 12)Inserting Into a Linked Listint insert(Node **head, int new_value) {Node *prev = NULL, *newItem;Node *current = *head;while (current && current->value < new_value) {prev = current;current = current->next;}newItem = (Node *) malloc(sizeof(Node));if (!newItem) return -1;newItem->value = new_value;newItem->next = current;if (!prev) {*head = newItem;} else {prev->next = newItem;}}5CMSC 212 – S05 (lect 12)Tracing Through Insertz Insert 7z Insert 2head51015NULL7X2X6CMSC 212 – S05 (lect 12)Deleting From A Single Linked Listint delete(Node **head, int new_value) {Node *prev = NULL;Node *current = *head;while (current && (current->value != new_value)) {prev = current;current = current->next;}if (!current) {return -1; /* not found */}if (prev) {prev->next = current->next;} else {*head = current->next; /* deleted first item */}free (current);return 0;}7CMSC 212 – S05 (lect 12)Doubled Linked Listsz Each nodes– contains a value– a pointer the next and previous elementz Typical Declaration:typedef struct NODE {struct NODE *next;struct NODE *prev;int value;} Node;root51015NULLNULL8CMSC 212 – S05 (lect 12)Insert into a doubly Linked listz Think about 4 cases:– Middle of the list• Update previous element's next pointer• Update next elements previous pointer– End of the list• Update previous element's next pointer– Start of the list• Update head of list• Update old head of list's previous element– An initially empty list• Update head of the list9CMSC 212 – S05 (lect 12)Inserting Into A Doubly Linked Listint insert(Node **head, int new_value) {Node *prev = NULL, *newItem;Node *current = *head;while (current && current->value < new_value) {prev = current;current = current->next;}newItem = (Node *) malloc(sizeof(Node));if (!newItem) return -1;newItem->value = new_value;newItem->next = current;newItem->prev = prev;if (!prev) {*head = newItem;} else {prev->next = newItem;}if (current) {current->prev = next;}}10CMSC 212 – S05 (lect 12)Deleting from a Doubly Linked Listint delete(Node **head, int new_value) {Node *prev = NULL;Node *current = *head;while (current && (current->value != new_value)) {prev = current;current = current->next;}if (!current) return -1; /* not found */if (prev) {prev->next = current->next;} else {*head = current->next; /* deleted first item */}if (current->next) {current->next->prev = prev;}free (current);return 0;}11CMSC 212 – S05 (lect 12)Binary Treesz Each nodes– contains a value– a pointer a left child and a right childz Typical Declaration:typedef struct NODE {struct NODE *left;struct NODE *right;int value;} Node;NullNullNull Null Null Null1007510 8350912CMSC 212 – S05 (lect 12)Lookup In A Binary Search Treez If the element is less than the current node– Look in left child treez If the element is greater than current node– Look in the right child treez Example (assumes values >= 0):int Lookup(Node *root, int value) {if (!root) return -1;if (root->value == value) {return value;} else if (root->value > value) {return Lookup(root->left, value);} else { return Lookup(root->right, value);}}13CMSC 212 – S05 (lect 12)Insert Into a Binary Treeint insert(Node **root, int value) {Node *new;if (!*root) {new = (Node *) malloc(sizefof(Node));if (!new) return -1;*root = new;new->left = new->right = NULL;new->value = value;return 0;} if ((*root)->value > value) {return insert(&((*root)->left), value);} else {return insert(&((*root)->right), value);}}14CMSC 212 – S05 (lect 12)Graphs - Directedz Examples– List of web pages that link to each otherz Nodes can – have an arbitrary number of out arcs– have an arbitrary number of inbound arcsz Declarationstypedef struct ARC {struct NODE *nodePtr;struct ARC *next;} Arc;typedef struct NODE {Arc *outArcs;int value;} Node;15CMSC 212 – S05 (lect 12)GraphsNULLNodeArcNULLNULL16CMSC 212 – S05 (lect 12)Adding Node To a GraphNode *AddNode(int value) {Node *new;new = (Node *) malloc(sizeof(Node));new->value = value;new->outArcs = NULL;}17CMSC 212 – S05 (lect 12)Adding Items To a Graphint AddArc(Node *from, Node *to) {Arc *new, *prev, *current;prev = NULL;for (current=from->outArcs; current; current=current->next) {if (current->nodePtr == to) return 1; /* already defined this arc */prev = current;}new = (Arc *) malloc(sizeof(Arc));if (!new) return -1;new->nodePtr = to;new->next = NULL;if (!prev) {from->outArcs = new; /* first out arch for this node */} else {prev->next =


View Full Document

UMD CMSC 212 - Lecture Slides

Download Lecture Slides
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Slides and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Slides 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?