DATA STRUCTURES CSCI 1200
Popular in Course
Popular in ComputerScienence
This 6 page Class Notes was uploaded by Ransom Blanda on Monday October 19, 2015. The Class Notes belongs to CSCI 1200 at Rensselaer Polytechnic Institute taught by Staff in Fall. Since its upload, it has received 17 views. For similar materials see /class/224865/csci-1200-rensselaer-polytechnic-institute in ComputerScienence at Rensselaer Polytechnic Institute.
Reviews for DATA STRUCTURES
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/19/15
CSCI1200 Review from Lecture 8 Computer Science II Fall 2008 Lecture 9 Lists 0 We wrote several versions of a program to maintain a class enrollment list and an associated waiting list 7 The rst version used vectors to store the information inef c ient Unfortunately erasing items from vectors is 7 In the second version we explored iterators and iterator operations as a different means of manipulating the contents of the vector 7 This allows us to replace the vector with a list in the third version There is an erase function for both vectors and lists The vector erase function does pretty much what we did in our enrollment example programl The list erase function is much more ef cient more on this next week 0 For the enrollment problem the list is a better sequential container class than the vector Today7s Class 0 Returning references to member variables from member functions 0 Review of iterators and iterator operations 0 STL Lists erase and insert on lists 0 Differences between indices and iterators differences between lists and vectors 0 Introductory example on linked lists 0 Basic linked list operations 7 Stepping through a list 7 Push back 7 amp we7ll continue on Tuesday References and Return Values 0 A reference is an alias for another variablel For example 91 string a quotTommyquot string b a a stringamp c a c b1 i cout ltlt a ltlt quot quot ltlt b ltlt c1 a cout ltlt a ltlt quot quot ltlt b ltlt new string is created using the string copy constructor is an aliasreference to the string object a quot quot ltlt c ltlt endl outputs Tommy Timmy Tommy quot quot ltlt c ltlt endl outputs Tammy Timmy Tammy The reference variable c refers to the same string as variable a Therefore when we change c we change at o Exactly the same thing occurs with reference parameters to functions and the return values of functions Let7s look at the Student class from Lecture 4 again class Student public const stringamp firstname const return firstname const stringamp lastname const return lastname etc private string firstname string lastname etc 0 In the main function we had a vector of students vectorltStudentgt students Based on our discussion of references above and looking at the class declaration what if we wrote the following Would the code then be changing the internal contents of the ith Student object string amp fname studentsi firstname fname1 i o The answer is NO The Student class member function firstname returns a const reference The compiler will complain that the above code is attempting to assign a const reference to a nonconst reference variable o If we instead wrote the following then compiler would complain that you are trying to change a const objecti const string amp fname studentsi firstname fname1 i 0 Hence in both cases the Student class would be safe from attempts at external modi cation 0 However the author of the Student class would get into trouble if the member function return type was only a reference and not a const reference Then external users could access and change the internal contents of an object This is a bad idea in most cases 92 The list Standard Library Container Class 0 Lists are formed as a sequentially linked structure instead of the arraylike randomaccess indexing structure of vectors arrayvector list I I a ll an 0 Lists have pushiront and popiront functions in addition to the pushlback and poplback functions of vectors 0 Erase is very ef cient for a list independent of the size of the list we ll see why when we learn the implemen tation details later in the semester i 0 We can7t use the standard sort function we must use a special sort function de ned by the list type 0 Lists have no subscripting operation aikiai they do not allow randomaccess 93 Iterators and Iterator Operations 7 General 0 An iterator type is de ned by each container class For example vectorltdoublegt iterator vitr listltstringgt iterator litr string iterator sitr 0 An iterator is assigned to a speci c location in a container For example Note We can add an integer to vector and string iterators but not to list iteratorsi vitr vec begin i ith location in a vector litr lst begin first entry in a list sitr str begin first char of a string 0 The contents of the speci c entry referred to by an iterator are accessed using the dereference operatm In the rst and third lines vlitr and llitr are l valuesi In the second sitr is an rva uei vitr 314 cout ltlt sitr ltlt endl litr quotHelloquot o Stepping through a container either forward and backward is done using increment and decrement operators itr itr itr itr These operations move the iterator to the next and previous locations in the vector list or string The operations do not change the contents of container 0 Finally we can change the container that a specific iterator is attached to as long as the types match Thus if v and w are both vectorltdoub1egt then the code v itr vbegin v itr 314 changes 151 entry in v v itr wbegin 2 vitr 278 changes 3rd entry in w works ne because vitr is a vectorltdoub1egt iterator but if a is a vectorltstringgt then vitr abegin is a syntax error because of a type clashl 94 Iterators and Iterator Operations 7 Vector Iterators Vector and string iterators have special capabilities that most other container iterators do not have 0 lnitialization at a random spot in the vector p vbegin i o Jumping around inside the vector through addition and subtraction of location counts P P 5 moves p 5 locations further in the vector 0 Neither of these is allowed for list iterators and most other iterators for that matter because of the way the corresponding containers are built 95 Iterators vs Indices for Vectors and Strings 0 Students are often confused by the difference between iterators and indices for vectors Consider the following declarations vectorltdoublegt a10 25 vectorltdoublegt iterator p abegin 5 unsigned int i5 0 lterator p refers to location 5 in vector a The value stored there is directly accessed through the operator p 60 cout ltlt p ltlt endl o The above code has Changed the contents of vector a Here s the equivalent code using subscripting ai 60 cout ltlt ai ltlt endl 96 Lists vs Vectors 0 Lists are a chain of separate memory blocks one block for each entry 0 Vectors are formed as a contiguous and bigger block of memory 0 Lists therefore allow easyfast insert and remove in the middle but not indexing o Vectors therefore allow indexing which depends on jumping around inside the block of memory but slow insert and remove in the middle 97 Erase 0 Lists and vectors each have a special member function called eraser In particular given list of ints 5 consider the examp e listltintgt iterator p sbegin p listltintgt iterator q serasep 0 After the code above is executed 7 The integer stored in the second entry of the list has been removed 7 The size of the list has shrunk by one 7 The iterator 1 does not refer to a valid entry 7 The iterator q refers to the item that was the third entry and is now the second 0 To reuse the iterator p and make it a valid entry you will often see the code written listltintgt iterator p sbegin P p serasep 0 Now we can rewrite the eraseirommector function from the Lecture 8 enrollment example 1 verasep 0 Even though this has the same syntax for vectors and for list the vector version is 0n whereas the list version is O 1 i 98 Insert 0 Similarly there is an insert function for lists that takes an iterator and a value and adds a link in the chain with the new value immediately before the item pointed to by the iterator o The call returns an iterator that points to the newly added elementi Variants on the basic insert function are also de ned 99 Exercise Erase amp Insert Write a function that takes a list of integers 151 and an integer x The function should 1 remove all negative numbers from the list 2 verify that the remaining elements in the list are sorted in increasing order and 3 insert x into the list such that the order is maintained 910 Motivation 0 Thus far our discussion of how 1istltTgt is implemented has been only intuitive it is a chain of objects 0 Now we Will look at the mechanism 7 linked lists 0 Learning this isgood forh39 h l is important 1 courses Where the design of novel data structures 911 Objects With Pointers Linking Objects o The two fundamental mechanisms of linked lists are 7 creating objects With pointers as one of the member variables7 and 7 making these pointers point to other objects of the same type 0 These mechanisms are illustrated in the following program include ltiostreamgt using namespace std template ltclass Tgt class Node pub ic T value Node ptr y void main Nodeltintgt 11 11 new Nodeltintgt Create a Node and assign its memory address to 11 llgtvalue 6 This is the same as llvalue llgtptr NULL NULL 0 which indicates a quotnullquot pointer 11 is a pointer to a nonexistent Node Nodeltintgt q new Nodeltintgt qgtvalue 8 11 Mu NULL E set ll s ptr member variable to point to the same thing as variable q llgtptr q cout ltlt II1st value quot ltlt ll gtvalue ltlt quotnquot ltlt quot2nd value quot ltlt llgtptrgtvalue ltlt endl 912 De nition A Linked List 0 The de nition is recursive A linked list is either 7 Empty7 or 7 Contains a node storing a value and a pointer to a linked list 0 The rst node in the linked list is called the head node and the pointer to this node is called the head pointer The pointer s value Will be stored in a variable called head 913 Visualizing Linked Lists 0 The head pointer variable is drawn with its own box It is an individual variable It is important to have a separate pointer to the rst node since the rst node may change o The objects nodes that have been dynamically allocated and stored in the linked lists are shown as boxes with arrows drawn to represent pointers 7 Note that this is a conceptual view only The memory locations could be anywhere and the actual values of the memory addresses aren t usually meaningful o The last node MUST have NULL for its pointer value 7 you will have all sorts of trouble if you don7t ensure his 0 You should make a habit of drawing pictures of linked lists to gure out how to do the operations 914 Basic Mechanisms Stepping Through the List 0 We7d like to write a function to determine if a particular value stored in x is also in the list 0 You can think of this as a precursor to the find function Our function isn7t yet returning an iterator however 0 We can access the entire contents of the list one step at a time by starting just from the head pointer 7 We will need a separate local pointer variable to point to nodes in the list as we access them 7 We will need a loop to step through the linked list using the pointer variable and a check on each value 915 Exercise Write isthere template ltclass Tgt bool isthereNodeltTgt head const Tamp x f 916 Basic Mechanisms Pushing on the Back 0 Goal place a new node at the end of the list 0 We must step to the end of the linked list remembering the pointer to the last node 7 This is an 0n operation and is a major drawback to the ordinary linkedlist data structure we are discussing now We will correct this drawback by creating a slightly more complicated linking structure in our next lecture 0 We must create a new node and attach it to the end 0 We must remember to update the head pointer variable s value if the linked list is initially empty 7 Hence in writing the function we must pass the pointer variable by reference 917 Exercise Write pushback template ltclass Tgt void pushback NodeltTgt amp head T constamp value f
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'