Lecture 20OutlineLinked List Toolkitlist_copy 1list_copy 2Classes and Linked ListsBag Class Atttributes 1Bag Class Attributes 2Bag ObjectNode Class FilesBag Class Definition 1Bag Class Definition 2Bag Class UsageBag Class Implementationinserterase_oneFinding the Next Occurrence 1Finding the Next Occurrence 2count, eraseoperator+=Destructor, Copy Constructor, Assignment OperatorgrabFriday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 1Lecture 20Log into Linux. Copy files on csserver from /home/hwang/cs215/lecture20/*.* into a separate directory. Midterm exam review sheet has been posted.Reminder: Homework 9 is due at the beginning of class on Monday, no late work accepted, to be covered during the exam review.Questions?Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 2OutlineReview linked list toolkitClasses and linked listsExample class: Bag classAttributesReimplementation of operationsgrab operationFriday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 3Review: Linked-List ToolkitOperations on linked lists. All receive node pointer, often the head pointer.list_lengthlist_writelist_head_insert, list_insertlist_search, list_locatelist_head_remove, list_remove, list_clearlist_copyFriday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 4list_copyThe copy constructor and assignment operator of classes using a linked list as an implementation need to be able to make a copy of a linked list.list_copy receives the head pointer for a source list and passes back the head and tail pointers of the copy. Since this is a true copy, the two lists do not share any nodes.void list_copy (const node *source_ptr, node * & head_ptr, // of copy node * & tail_ptr); // of copyFriday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 5In-class Exercise: list_copyImplement this function in node1.cpp (of last class exercise)The design for this function is1. Initialize head_ptr and tail_ptr to 0.2. Handle the case of an empty source list.3. Create a copy of the source's head node and make head_ptr and tail_ptr point to it.4. For each of the remaining source nodes, make a copy and add at the tail of the new list.Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 6Classes and Linked ListsLinked lists are rarely used for their own sakes. Instead, they are like arrays, used as an implementation technique.As with dynamic arrays, the use of a linked list requires that class operations create and delete (node) objects as they execute, and that the destructor, copy constructor, and assignment operator be implemented.Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 7Bag Class AttributesThis bag class will be implemented using a linked list. There are two attributes:head_ptr – a pointer to the head node of the linked list that contains the bag itemsnum_nodes – an integer that keeps track of the number of nodes in the linked list as they are inserted and removedFriday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 8Bag Class AttributesNote that num_nodes is not required as we could use list_length( ) to implement the size( ) operation. However, doing so makes size( ) an O(n) operation, since list_length( ) accesses every node in the list. By keeping track of the nodes as they are inserted and removed, the size( ) operation becomes O(1) as it is for the array implementations of the bag class.Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 9Bag ObjectHere is a way to think about how this works. (Insert operation inserts at the head of the list.)bag b;b.insert(15);b.insert(34);head_ptrnum_nodes234 15Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 10Node Class FilesCopy your node1.h and node1.cpp files from last in-class exercise to the directory with today's files.In node1.h, change the typedef to use int (rather than double).Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 11Bag Class DefinitionExamine file bag3.hHas the same typedefs as the other bag classes, but value_type is the node struct value_type. Does not have a static constant member.Since the underlying linked list is built one node at a time, there is only a default constructor that creates an empty bag object.Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 12Bag Class DefinitionOtherwise the bag operation prototypes are the exactly the same as the previous bag class. Note that a bag only receives and returns data items; never pointers to the nodes.New operation grab( ) has been added.Destructor, copy constructor, and assignment operator have been added.Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 13Bag Class UsageExamine files Makefile.Inclass20 and bag3demo.cppThe makefile now has three .o targets, one for the main program, one for the bag class, and one for the linked-list toolkit (in node1.cpp).Demo program is exactly the same as the last one (Lecture 15). It just asks user for integers, adds them to a bag, and then asks the user for the integers again and removes them from the bag.Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 14Bag Class ImplementationExamine file bag3.cppAs before, we ignore any bad_alloc exceptions.The default constructor just initializes the head pointer to null and num_nodes to 0 to represent an empty list/bag.The size( ) operation returns num_nodes attribute.The rest of the bag operations use the linked-list operations from the toolkit.Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 15insertSince the order of the elements does not matter, the insert( ) operation simply does the following:1. Insert the entry at the head of the list using list_head_insert( )2. Increment num_nodes.Friday, February 25 CS 215 Fundamentals of Programming II - Lecture 20 16erase_oneTo erase one value, we must remove one node. Once again, since the order does not matter, we can choose to remove the head node. (It is the easiest to remove. Why?) So the algorithm for this operation is:1. Find a target pointer using list_search( )2. If the target pointer is null, return false3. Move the head node's data to the target node.4. Remove the head node using
View Full Document
Unlocking...