1CMSC 212 – S07 (lect 10)Announcementsz Exam #1 – Thursday, March 8, 6:00 – 7:30 in Armory 0126z Program #2– Due todayz Reading– Chapter 12, 10.22CMSC 212 – S07 (lect 10)Linked Data Structuresz Like classes with refs to same class in Javaz Have pointers to a struct of the same typez Example Declaration:typedef struct NODE {struct NODE *next;int value;} Node;Node * root;z next and root are pointers to Nodesroot51015NULL3CMSC 212 – S07 (lect 10)Finding a value in a Linked StructureNode *find(Node *current, int val) {while (current && current->value != val) {current = current->next;}return current;}int IsIn(Node *current, int val) {while ((current != NULL) && ((current->value) != val)) {current = current->next;}if (current) {return 1;} else {return 0;}}4CMSC 212 – S07 (lect 10)Tracing Through Inserthead51015X7newItem(Insert 7)X2newItem(Insert 2)NULL5CMSC 212 – S07 (lect 10)Inserting Into a Linked Listint insert(Node **head, int new_value) {Node *current = *head;Node *pred = NULL;Node *newItem; while (current && current->value < new_value) {pred = current;current = current->next;}newItem = (Node *) malloc(sizeof(Node));if (!newItem) return -1;newItem->value = new_value;newItem->next = current;if (!pred) {*head = newItem;} else {pred->next = newItem;}return 0;}6CMSC 212 – S07 (lect 10)Tracing Through Deletehead51015Delete 72Delete 2NULL77CMSC 212 – S07 (lect 10)Deleting From A Single Linked Listint delete(Node **head, int new_value) {Node *pred = NULL;Node *current = *head;while (current && (current->value != new_value)) {pred = current;current = current->next;}if (!current) {return -1; /* not found */}if (pred) {pred->next = current->next;} else {*head = current->next; /* deleted first item */}free (current);return 0;}8CMSC 212 – S07 (lect 10)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;root51015NULLNULL9CMSC 212 – S07 (lect 10)Insert into a doubly Linked listz Think about 4 cases:– Middle of the list• Update previous element's next pointer– new node’s previous pointer set to this node• Update next element’s previous pointer– new node’s next point set to that node– End of the list• Update previous element's next pointer– new node’s previous pointer set to this node– new node’s next pointer set to NULL– Start of the list• Update head of list• Update old head of list's previous element– new node’s next pointer set to this node– new node’s previous pointer set to NULL– An initially empty list• Update head of the list– new node’s next and previous pointer both NULL10CMSC 212 – S07 (lect 10)Inserting Into A Doubly Linked Listint insert(Node **head, int new_value) {Node *pred = NULL, *newItem;Node *current = *head;while (current && current->value < new_value) {pred = current;current = current->next;}newItem = (Node *) malloc(sizeof(Node));if (!newItem) return -1;newItem->value = new_value;newItem->next = current;newItem->prev = pred;if (!pred) {*head = newItem;} else {pred->next = newItem;}if (current) {current->prev = newItem;}}11CMSC 212 – S07 (lect 10)Deleting from a Doubly Linked Listint delete(Node **head, int new_value) {Node *pred = NULL;Node *current = *head;while (current && (current->value != new_value)) {pred = current;current = current->next;}if (!current) return -1; /* not found */if (pred) {pred->next = current->next;} else {*head = current->next; /* deleted first item */}if (current->next) {current->next->prev = pred;}free (current);return 0;}12CMSC 212 – S07 (lect 10)Binary Treesz Each node– 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;1007510 8350913CMSC 212 – S07 (lect 10)Lookup In A Binary Search Treez If the element is less than the current node– Look in the left child treez If the element is greater than current node– Look in the right child treez Example:int Lookup(Node *root, int value) {if (!root) return -1;if (root->value == value) {return 1;} else if (root->value > value) {return Lookup(root->left, value);} else { return Lookup(root->right, value);}}14CMSC 212 – S07 (lect 10)Insert Into a Binary SearchTreeint insert(Node **root, int value) {Node *new;if (!(*root)) {new = (Node *) malloc(sizeof(Node));if (!new) return -1;*root = new;new->left = new->right = NULL;new->value = value;return 0;} else if ((*root)->value > value) {return insert(&((*root)->left), value);} else {return insert(&((*root)->right),
View Full Document
Unlocking...