Lecture 19OutlineNode StructureBuilding a Linked ListLinked List Toolkit 1Linked List Toolkit 2list_lengthlist_writelist_head_insert 1list_head_insert 2list_insert 1list_insert 2list_insert 3list_searchlist_locatelist_head_remove 1list_head_remove 2list_remove 1list_remove 2list_clearlist_copy 1list_copy 2Wednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 1Lecture 19Log into Linux. Copy files on csserver from /home/hwang/cs215/lecture19/*.*Reminder: Homework 8 due today.Homework 9 is posted (PDF only). They are sample written midterm exam problems. It is due on Monday at the beginning of class (no late work accepted) as part of the midterm exam review.Questions?Wednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 2OutlineReview node struct, list_lengthLinked list toolkit – build as we golist_write – not in the textbooklist_head_insert, list_insertlist_search – const and non-constlist_locate – const and non-constlist_head_remove, list_remove, list_clearlist_copyWednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 3Review: node StructureRecall the node structure used in linked lists.struct node { typedef double value_type; // CONSTRUCTOR node(const value_type & init_data = value_type(), node *init_link = 0) { data = init_data; next = init_link; } // note, do not need ';' here // FIELDS value_type data; node *next; }; 3.14data nextWednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 4Review: Building a Linked ListExamine file list-examples.cppThe first part is the examples from the last lecture that builds a linked list by hand using pointer variables to each node. The head pointer is r.12.1 14.6 9.3 -4.8r q t pWednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 5Linked-List ToolkitExamine file node1.hIn addition to the node structure, it has the prototypes for some common functions that are used to access and manipulate linked lists.Call this the linked-list toolkit.Last time we looked at list_length, a function that computes the number of nodes in a linked list given its head pointer.size_t list_length (const node *head_ptr);Wednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 6Linked List ToolkitImplementations for the toolkit functions are in file node1.cpp. A driver program is in file list-examples.cpp. A makefile is provided.Note that many functions are stubs and output a message saying so. This allows us to compile and run the entire program that uses them without implementing all the functions.Most the code that is missing is in the textbook using a node class; we will build the toolkit using the node struct as we go.Wednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 7Review: list_LengthPattern for accessing every node in a linked list is a for-loop.size_t list_length (const node *head_ptr){ size_t count = 0; const node *cursor; // lcv decl for (cursor = head_ptr; // init lcv cursor != 0; // lcv end test cursor = cursor->link; // "incr" lcv count++; // loop body return count;}Wednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 8In-class Exercise: list_writelist_write outputs each item in a linked list to an output stream on a separate line. It receives the head pointer and an output stream.void list_write (const node *head_ptr, std::ostream & out);Write the implementation of list_write in the file node1.cpp. Compile and run the program. All of the calls to list_write should show the same 4 items, since the rest of the toolkit is not implemented.Wednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 9list_head_insertA common operation on linked lists is to insert a new item at the head of the list.list_head_insert receives and passes back the head pointer (since it uses the head pointer's value and also changes it) and receives the item to be inserted.void list_head_insert (node * & head_ptr, const node::value_type & entry);Wednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 10In-class Exercise: list_head_insertImplement this function in node1.cppThe design for this function is1. Create a new node with entry as its data value and head_ptr as its link.2. Make head_ptr point to the new nodeHere is a picture of list_head_insert(r, 1.2):12.1headPtr1.2entryAt the beginning of the function At the end of the function12.11.2headPtrinsertPtrWednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 11list_insertlist_insert is used to insert items anywhere else besides the head of the list. In order to do this, it receives a pointer to the node that will be in front of the new node containing entry. Call this the previous pointer.void list_insert (node * previous_ptr, const value_type & entry);Wednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 12In-class Exercise: list_insertImplement this function in node1.cppThe design for this function is1. Create a new node with entry as its data value and previous_ptr's node's link as its link.2. Make previous_ptr's node's link point to the new nodeNote this works even when previous_ptr is pointing the last node in the list.A picture of list_insert(q, -7.8) is shown on the next slide.Wednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 13list_insert14.6previousPtr-7.8entryAt the beginning of the functionAt the end of the function9.314.6previousPtr-7.89.3insertPtrWednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 14list_searchlist_search receives a head pointer and a target value. It returns a pointer to the first node that contains the target value or 0 if the target is not found.As with searching arrays and vectors, the design of this function is to iterate through the list and returning a pointer when the target is found.It has both const and non-const versions.Wednesday, February 23 CS 215 Fundamentals of Programming II - Lecture 19 15list_locatelist_locate receives a head pointer and a position. It returns a pointer to the node at that position, or 0 if there is no such position. Per the specifications in the textbook, item positions start at 1 (not 0). This function uses an assert to ensure that position > 0.The design of
View Full Document
Unlocking...