COMP SCI 11 WITH C++
COMP SCI 11 WITH C++ CSC 1254
Popular in Course
Popular in ComputerScienence
This 22 page Class Notes was uploaded by Mr. Molly Kessler on Tuesday October 13, 2015. The Class Notes belongs to CSC 1254 at Louisiana State University taught by W. Duncan in Fall. Since its upload, it has received 7 views. For similar materials see /class/222858/csc-1254-louisiana-state-university in ComputerScienence at Louisiana State University.
Reviews for COMP SCI 11 WITH C++
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/13/15
CBC 1254 Lecture 18 19 Linked list based Unsorted List ADT November 4 amp 9 2009 0 Basic Operations 0 Variations on Linked Lists 0 Doubly Linked Lists 0 Linked List ADT with Iterator 1 Unordered List ADT Operations An unordered list is a nite sequences of items 2391723927239n The primitive operations associated with an unordered list are 1 Create an empty list 3 Determine whether a list is empty C40 Determine the number of items on a list 4 lnsert items in the list Cf Remove items from the list CT Look at retrieve items in the list 2 Variations on Linked Lists A linked list is one of the fundamental data structures used in computer programming A linked list consists of nodes which are self referential The nodes of a list are self referential because each node contains a pointer or link to another data of the same type Linked lists permit insertion and removal of nodes at any point in the list in constant time7 but do not allow random access Several different types of linked list exist singly linked lists7 doubly linked lists7 and circularly linked lists Most linked list based ADT will consist of a class in which the metadata elements are declared7 including one or more pointers to a linked list 21 Singly Linked Lists It consists of a sequence of nodes7 each containing arbitrary data elds and one link pointing to the next Some operations may be inef cient since a singly linked list can be traversed only one way forward Head link link link link Figure 1 Singly Linked List 22 Circularly Linked Lists Every node in a circular linked list has a successor No node in a circular linked list contains NULL There are some variations of circular linked lists in which there is an external pointer to the last node 23 DoublyLinked List It consists of a sequence of nodes7 each containing arbitrary data elds and two references links pointing to the next andor previous nodes Various operations require only one pointer for traversal since we can for example get a pointer to a preceding node by gt4 gt6 gt8o List Figure 2 Circularly Linked List previous current gtprecede Pointer assignment operations on doubly linked lists are somewhat cumber some Consider deleting a node as an example current gtprecede gtnext current gtnext current gtnext gtprecede current gtprecede Convince yourself that these statements do work for all nodes but the head node when we do not have a dummy node and for all data nodes when there is a dummy node To insert a node newptr gtnext current newptr gtprecede current gtprecede current gtprecede newptr newptr gtprecede gtnext newptr Again7 convince yourself these statements insert the data node that newptr points to Will it work if we swap the rst two lines Why or why not Bakeri SHJoneei 3918mith Hij mlsorl Figure 3 A doubly linked list 24 Unsorted Linkedlist Implementation An elegant way to implement a list ADT is to use doubly linked nodes with iterators This is the approach taken in the STL Standard Template Li brary linked list implementation Here is an STL style list implementation that mimics the implementation in the STL In a subsequent programming exercise you will enhance this unsorted list implementation and transform it into a sorted list ADT and make one or two other minor modi cations file listh author William Duncan date 2007 03 22 Description interface for the sorted list ADT Project 3 Instructor William Duncan include ltstringgt include ltiostreamgt define SLISTH using namespace std exception class class ListException public ListExceptionconst stringamp aMessage message aMessage string what const return message private string message template lttypename Lgt class List public forward declaration template lttypename Ugt class Iterator Constructs an empty list ListltLgt Appends an element to the list param item the value to append void pushBackL item Inserts an element into the list param iter the position before which to insert param item the value to append void insertIteratorltLgt iter L item This function removes an element from the list that the iterator i points to param i the position to remove return an iterator pointing to the element after the erased element IteratorltLgt eraseIteratorltLgt i Gets the beginning position of the list return an iterator pointing to the beginning of the list IteratorltLgt begin Gets the pasttheend position of the list return an iterator pointing past the end of the list IteratorltLgt end return the number of elements in the list long size const private template lttypename Vgt class Node NodeltLgt first NodeltLgt last long length nested Node class template lttypename Lgt template lttypename Tgt class ListltLgtNode public Constructs a node with a given data value param s the data to store in this node NodeT s private friend class ListltLgt friend class IteratorltLgt T data NodeltTgt previous NodeltTgt next nested Iterator class templatelttypename Lgt templatelttypename Tgt class ListltLgt Iterator public Constructs an iterator that does not point into any list Iterator Looks up the value at a position return the value of the node to which the iterator points T get const Advances the iterator to the next node void next Moves the iterator to the previous node void previous Compares two iterators param b the iterator to compare with this iterator return true if this iterator and b are equal bool equalsIteratorltTgt b const private NodeltTgt position NodeltTgt last friend class ListltLgt SLISTH endif file list cpp author William Duncan date 2007 03 24 Description implementation for list class include ltiostreamgt include quotlist hquot using namespace std template lttypename Lgt ListltLgtList first NULL last NULL length 0 template lttypename Lgt void ListltLgt pushBackL item NodeltLgt newnode new NodeltLgtitem if last list is empty first newnode last newnode else newnodegtprevious last lastgtnext newnode last newnode length void ListltLgtzinsertIteratorltLgt iter L item if iterposition pushBackitem return length NodeltLgt after NodeltLgt before NodeltLgt newnode newnode gtprevious before newnode gtnext after after gtprevious newnode if before insert at beginning iterposition after gtprevious new NodeltLgtitem first newnode else before gtnext newnode ListIterator ListeraseIterator i Iterator iter i assertiterposition NULL Node remove iterposition Node before Node after removegtnext first remove gtprevious if remove after first else before gtnext after if remove last last before else after gtprevious before iterposition after delete remove length return iter templatelttypename Lgt ListltLgt lteratorltLgt ListltLgt begin IteratorltLgt iter iterposition first iterlast last return iter templatelttypename Lgt ListltLgt lteratorltLgt ListltLgt end IteratorltLgt iter iterposition NULL iterlast last return iter templatelttypename Lgt long ListltLgt size const return length template lttypename Lgt template lttypename Tgt ListltLgt NodeltTgt NodeT item data item previous NULL next NULL template lttypename Lgt template lttypename Vgt ListltLgtIteratorltVgtIterator position NULL last NULL template lttypename Lgt template lttypename Vgt V ListltLgt IteratorltVgt get const assertposition NULL return position gtdata template lttypename Lgt template lttypename Vgt void ListltLgt IteratorltVgt neXt assertposition NULL position position gtneXt template lttypename Lgt template lttypename Vgt void ListltLgt IteratorltVgt previous if position NULL position last else position position gtprevious template lttypename Lgt template lttypename Vgt bool ListltLgtzIteratorltVgtequalsIteratorltVgt b const return position bposition end of listcpp file uselistcpp author William Duncan date 2006 10 20 Description sample client program include ltiostreamgt include ltstringgt include quotlistcppquot using namespace std int main Listltstringgt students studentspushBackquotHarris Christopherquot studentspushBackquotGarner Jamesquot studentspushBackquotBrown Gaynellequot studentspushBackquotJones Jaredquot studentspushBackquotKamar Josequot studentspushBackquotLeblanc Rickeyquot studentspushBackquotMeng Chaoquot studentspushBackquotSchrock Kevinquot add a value in fourth place ListltstringgtzIteratorltstringgt pos pos studentsbegin posnext posnext posnext studentsinsertpos quotSavoie Kamiquot remove the name in second place pos studentsbegin posnext studentserasepos print all names for pos studentsbegin posequalsstudentsend posnext cout ltlt posget ltlt quotnquot coutltltquotThere are quotltltstudentssizeltltquot elements in the listquotltltendl return 0 CBC 1254 Lecture 18 Queue ADT November 2 2009 0 De nition of A Queue 0 Queue Interface 0 A Singly Linked List based Queue 1 De nition of A Queue A queue is a FIFO rst in rst out linear data structure De nition 1 A queue Q of item type E is formally de ned as a sequence of items of type E on which the following operations are de ned H Create the queue Q to be the empty queue D Determine whether or not the queue Q is is empty C40 Determine whether or not the queue Q is full for queues with a nite capacity 4 add enqueue an item onto the rear of the queue Q 9 If Q is nonempty remove dequeue an item from the front of Q We will add two operations which may be useful for debugging or other purposes from time to time one operation to destroy Q free any memory allocated for creating the queue instance and obtaining the length of the queue the number of items enqueued Additionally7 we will add an accessor operation to determine the item at the head of the queue At times we add a copy constructor which creates a an instance of a queue using the data in another queue 2 Queue Interface file queue h author William Duncan date 9999 99 99 Description interface for the queue ADT include ltstringgt include ltiostreamgt include ltcassertgt include ltstdexceptgt ifndef QUEUEH define QUEUEH using namespace std exception class class QueueException public QueueExceptionconst stringamp aMessage message aMessage string what const return message private string message template lttypename Tgt class Queue public Constructs an empty queue QueueltTgt Copy constructor QueueltTgt Queueconst QueueltTgtamp another destructor returns the queue memory to the system virtual QueueltTgt Determine whether the queue is empty return this function returns true if the queue is empty otherwise it returns false if the queue contains at least one node bool isEmpty const Inserts an item into the queue param item the value to be inserted void enqueueT item Returns the item at the front of a nonempty queue or generates an exception if the queue is empty return item at the front of the queue const Tamp getQueueFront const throw QueueException Delete an item from the front of the queue Generates an exception if the queue is empty return the item at the front of the queue T dequeue throw QueueException returns the size of the queue return the size of the queue long size const private template lttypename Ugt class Node NodeltTgt head NodeltTgt rear long length template lttypename Ugt template lttypename Tgt class QueueltUgtNode public Constructs a node with a given data value param s the data to store in this node NodeT s NodeltTgt next friend class QueueltUgt QueueH endif 3 A Queue Implementation file queue cpp author William Duncan date 9999 99 99 Description implementation for the Queue class include quotqueue hquot Nested Node class definitions template lttypename Ugt template lttypename Tgt QueueltUgt NodeltTgt NodeT s data s next NULL Outer Queue class definitions template lttypename Tgt QueueltTgtQueue head NULL rear NULL length 0 template lttypename Tgt QueueltTgtQueueconst QueueltTgtamp another length O NodeltTgt tmp another head whiletmp enqueuetmpgtdata tmp tmpgtnext template lttypename Tgt QueueltTgt Queue NodeltTgt tmp while head tmp head head headgtnext delete tmp template lttypename Tgt bool QueueltTgt isEmpty const return length 0 templatelttypename Tgt void QueueltTgt enqueueT item NodeltTgt tmp NodeltTgt newNode new NodeltTgtitem if isEmpty head newNode rear newNode else reargtnext newNode rear newNode length templatelttypename Tgt const Tamp QueueltTgt getQueueFront const throw QueueException if head throw QueueExceptionquotQueue Exception getFront called on empty queuequot return headgtdata templatelttypename Tgt T QueueltTgt dequeue throw QueueException NodeltTgt tmp T item if head throw QueueExceptionquotQueue Exception dequeue called on empty queuequot item headgtdata if length 1 delete head head NULL rear NULL else tmp head head headgtnext delete tmp length return item templatelttypename Tgt long QueueltTgt size const return length 4 Linkedlistbased Implementation Tips There are many ways of implementing a queue which consists of dynamically linked nodes For example7 one popular implementations uses doubly linked nodes In this lecture7 the strategy we considered is the one in which the Queue class has two external pointers one to the head of the queue and one to the rear of the queue The nodes are singly linked Here is the Visual representation of the Queue Queue Empty Queue hi3 2 gt4 gt6 gt8l E Queue Queue With 4 data nodes Figure 1 linked list based Queue with two external pointers In your next programming project7 you will be expected to gure out how you can implement another variant of the Queue ADT7 de ning the classes as done above but with the Queue class consisting of only one external pointer7 rear To keep track of the head of the queue7 the last node of the queue has a pointer to the rst node of the queue Like the implementation above7 the nodes are singly linked This strategy is the so called singly linked circular list implementation You will need to rewrite most of the functions above to get the new implementation to work properly Here is a visual representation of the circular Queue rear 1 length 3 nH l ll l elxl 1 Q A circular queue with 3 nodes Figure 2 circular singly linked list based Queue with one external pointer We usually implement a destructor function for ADTs with dynamic node allocation7 rather than allow the compiler to automatically generate its code for us The compiler generated destructor performs shallow memory deal location Because the compiler generated destructor does not do deep deal location7 this leads to the so called memory leak having memory that is being used but cannot be accessed Also7 it is usually recommended that you make destructors virtual functions so that they may be over ridden by derived classes7 if desired We will have more to say on derived classes when we study inheritance For now7 just make the destructor virtual It is only in the function declaration prototype that you use the virtual modi er You do not use it in the function de nition To make a function virtual7 just put the reserved word virtual in front of its declaration prototype Arraybased Singly Linked and DoublyLinked Listbased ADTS We have implemented an ADT using doubly linked nodes and an using singly linked nodes We may even choose to use arrays rather than dynamically linked nodes for implementing the ADTs we are studying in this course Which implementation is the best The answer depends on what application you intend to use the ADT 21 Arrays are better at random access b Singly linked lists are better at deletion and insertion at a cursor c Doubly linked lists are better for two way cursor d Resizing is inef cient for dynamic arrays
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'