Class Note for EECS 168 at KU
Popular in Course
Popular in Department
This 46 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 26 views.
Reviews for Class Note for EECS 168 at KU
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: 02/06/15
LIDPointers amp Linked Structures Read Chpt 9 amp 13 Recall that every data object is stored in some location in memory Example void func IU39IerTICIr r int x fun int y 10 f X k 3 J Hence every variable in a program has two attributes Location Address of memory Content of the location Value Accessing a Data Object o Symbolic name 0 Address of memory location A New Referencing Mechanism One may use address of memory location pointer variable to access a data object Without an assigned symbolic name for the variable Pointer The memory addresslocation of a variable Pointer Variables A variable that stores the actual memory address of a data object Remarks 0 Memory addresses can be used as names for variables 0 Pointers point to a variable by telling Where the variable is located in memory Declaring a Pointer Variable Use a following the type or preceding the identi er Which is to be the pointer variable Syntax typename pointername typename pointername typename pointername Multiple Variables Declaration Syntax typename ptrname1 ptrname2 ptrnamek Example int v pl p2 V is a variable of int type p1 and p2 are pointers pointing to variables of int type double q1 q2 w ql is pointer pointing to variable of type double q2 and W are variables of type double Warning int 1 q r p is of pointer type but q and r are of int type The amp and Operators amp The address of operator When used in front of a variable v ampv corresponds to the address ofv The dereferencing operator When used in front of a pointer p p corresponds to the variable referencing point to by p Assignment Operator The assignment operator is used to assign the value of one pointer to another Example int v pl p2 V 168 pl ampv pl is a pointer pointing to variable V p1 268 the variable pointed to by pl holds 268 cout ltlt v ltlt v ltlt endl p2 pl v pl p2 reference the same variable p2 368 cout ltlt v ltlt v ltlt endl Output v 268 v 368 Remarks 0 p2 pl changes the location that p2 is pointing to 0 p2 p3 changes the value at the location that p2 is pointing to NULL Pointer Value Null is a special constant pointer value that can be assigned to a pointer variable of any type Example int p NULL doub1e q NULL Q How do we make pointers point to things 0 Use amp operator 0 Use dynamic allocation Using ampOperat0r int p v v 168 pampm p V p 168 V Dynamic Allocation of Variables To create new unnamed instances of variables during runtime Using new Operator Syntax Mytype p De ne pointer variable p p new Mytype Create dynamic variable pointed at by p Or Mytype p new Mytype P3 Dynamic vs Variables Variables created using the new operator are called dynamic variables They are created and destroyed while the program is running A static variable is created during compilation time Remark If Mytype is a class type then the default constructor will be called automatically when the dynamic variable is rst created If there is a constructor Mytype int double in the class Mytype it can be invoked by using Mytype p p new Mytypel68 2680 Example void dynamicallyAllocateO doub1e p new double p 107 int val new int7 cout ltlt Values ltlt p ltlt ltlt Val ltlt endl 107 heap Basic Pointer Munipulufions Program to demonstrate pointers and dynamic variabTes incTude ltiostreamgt using namespace std int main int pl pZ pl new int p1 42 p2 p1 cout ltlt quotpl ltlt pl ltlt end1 cout ltlt quotp2 quot ltlt pZ ltlt end1 p2 53 cout ltlt quotpl quot ltlt pl ltlt end1 cout ltlt quotp2 quot ltlt pZ ltlt end1 p1 new int p1 88 cout ltlt quotpl quot ltlt pl ltlt end1 cout ltlt quotpZ quot ltlt p2 ltlt end1 cout ltlt quotHope you got the point of this examp1enquot return 0 Sample Dialogue pl 42 p2 42 pl 53 p2 53 pl 88 p2 53 Hope you got the point of this examp1e DISPLAY 93 Explanation of Display 92 21 int pl p2 39U H U N E T iiiw 397 39l A 39U H Q m g A 395 H 395 H m EA 4 ii 395 H U H n H Allocating amp Deallocating Dynamic variables Basic Memory Management 0 Memory for dynamic variable is allocated om heap 0 Size of heap varies o If new is called and there is no more memory available in the heap the program will end Remark Older compiler may return a pointer value NULL when no more new dynamic variable can be created Null is a special constant pointer value that can be assigned to a pointer variable of any type 0 When no longer used memory for dynamic variables should be freed and returned to the heap using delete operator Once deleted the dynamic variable will be destroyed all pointers pointing to this variable are now unde ned The delete Operator Syntax delete ptrVar Example int 1 q p new int168 Cl 2 P delete p cout ltlt q What happens The pointers p and q are dangling pointers 10 Scope considerations Recall scope describes the region of a program over which a particular variable is alive and visible Going out of scope All memory used for local variables Will be deallocated The rules for dynamically allocated variables are different Dynamically allocated variables must be assigned to locations in a special area of memory called the heap A dynamically allocated variable remains allocated until it is explicitly deallocated deleted via the delete operator Pointers may go out of scope and be deleted but the things to Which they point at will not if they were dynamically allocated Memory Leak Term Which describes the case When a programmer allocates one or more variables dynamically but never explicitly deletes them 11 Programming Strategy 0 Whenever you use new to allocate a variable have a plan for exactly where and when you will use delete on that variable 0 Do not delete a variable more than once 0 Do not apply delete to a pointer variable that is 1 Currently pointing to a variable which was not dynamically allocated via new 2 Currently set to NULL 3 Uninitialized 0 Do not try to access a variable once it has been deleted Passing and Returning Pointer in Function Pointer can be passed as parameter andor returned as a function value Remark The operator is associated with the typename instead of the parameter in the function prototype Example void exampleint p double calculatedouble a double b 12 Example double calculatedouble a double b Return a pointer to a dynamically allocated variable holding the product ab Caller responsible for deleting the dynamically allocated memory double p new doubleab return p void aCaller double p calculate37 26 cout ltlt The answer is ltlt p ltlt endl delete p l3 De ning Your Own Types 0 In C a userde ned type name can be created and assigned to a type de nition Once de ned this userde ned type name can then be used to declare variables of the named type 0 We use the keyword typedef to de ne a new type name Syntax typedef knownDalaType yourTypeName Example typedef int exam typedef double average exam numOfExam average examAve Note that numOfExam is of exam type and hence also is of int type Similarly examAve is of average type and hence also is of double type Remarks 0 It is usually less confusing and also more informative to use typedef to de ne your pwn types 0 It can also be used to simplify variables declaration 14 To minimize the chance in making mistake When manipulating pointer variables we often de ne a pointer type name De ning pointer types Syntax typedef knownDalaType yourTypeName Example typedef int IntPtr de ne int pointer type IntPtr IntPtr p q double r void ptrExamplelntPtramp p IntPtr q double r 15 Recall that in using arrays 0 Array has xed size 0 Data must be shifted during insertions and deletions Possible Solution Linked data structures 0 Linked list is able to grow in size While the program is running 0 Does not require the shifting of items during insertions and deletions A linked list is a collection of objects being linked together With pointers such that 0 Each element node of the linked list has some data and apointer to the location in memory Where the next element of the list can be found 0 The last element of the list Will have a pointer value NULL 0 A linked list can be Visualized as items nodes drawn as boxes connected to other items by arrows pointers l6 Data Structure Node structure Item next Linked list head I l gt 39 39 39 gt NULL Empty List head NULL Remarks 0 The boxes in the previous drawing represent the nodes of a linked list 0 Nodes contain the data items and a pointer that can point to another node of the same type 0 The pointers point to the entire node not an individual item that might be in the node 0 The arrows in the drawing represent pointers o The box labeled head is not a node but a pointer variable that points to a node 17 C Implementation Strategy Recall that struct and class are essentially the same in C except their default accessibility When we design data structures we Will usually use struct Hence a node in a linked list is usually implemented using struct Example A linked list of strings struct ListNode string item int count ListNode link link is a pointer to ListNode typedef ListNode ListNodePtr Example A linked list of integers struct Node 1nt 1tem N0de next N0deint val itemval nextNULL constructor 18 typedef Nodeilt NodePtr NodePtr head Simple Insertion and Deletion in Linked List a b c 20 45 51 76 84 Old value 20 45 51 7s 84 60 Inserted Nam 20 7 45 51 H 60 76 84 Deleted item 19 Allocating a Node Dynamically ListNode p p new ListNode P Item next Accessing Node Member pitem 268 Remarks 0 p is a pointer variable so p is the node that p points to o The parentheses are necessary because the dot operator has higher precedence than the dereference operator Using gt Operator 0 The arrow operator gt combines the actions of the dereferencing operator and the dot operator to specify a member of 21 struct or object pointed to by a pointer o The statement p gt item 268 It is the same as pitem 268 20 Example Searching an Item in a List Node searchNode head int target Prec0nditi0n The pointer head points to the rst object of a linked list The pointer variable in the last node is NULL If the list is empty then head is NULL P0stc0nditi0n Returns a pointer that points to the rst node that contains the target If no node contains the target the function returns NULL Node temptr head use temptr for traversal if temp NULL check for empty list return NULL else While temptr gt item target ampamp temptr gt next NULL temptr temptr gt next check next node if temptr gt item target target found return temptr 21 else return NULL end search List Modification Algorithms Deleting a Node from a Linked Ordinal List Required function prototype bool removeNodeamp head int pos If a node at the indicated position eXists delete it amp return TRUE otherwise return FALSE Remarks 1 Generally NEVER want routines like this to print error messages and the like Simply return some sort of status code here a Boolean success code suffices 2 One must return the deleted node to system Approach Use prev and cur pointers for deletion where cur points at the node to be deleted Node M 8 gt10 gt gt100 V L T i V head A next A prev cur 22 Initially prev NULL cur head Special Cases 1 Position to be deleted does not exist or list is empty 2 Delete an interior node of list 3 Delete rst node of list Algorithm Consider a typica list With some elements Before head I i removehead 3 10 20T gt 4OT gt 80 prev cur After our 1 head 4O 10 20 80 prev gt nextcur gt next 23 bool removeN0deamp head int pos N0de prev NULL initialize prev and our pointers N0de cur head int curPos l start searching at pos 1 While cur NULL ampamp curPos pos searching for pos to delete prev cur cur cur gt next curP0s if cur NULL no deletion return false cur points to node to be deleted if prev NULL delete rst node head cur gt next else delete an interior node prev gt next cur gt next delete cur return node to memory return true 24 Complication A general design principle is that functions should do only one thing The function remove does two things i Find an element ii Delete an element Remedy Suppose we define a function say N0defindint pos which would return a pointer pointing at the item based on position to be deleted Function remove would then call find and delete the item found Slight Problem We want prev not our Solution In the case of ordinal unsorted lists do prev ndpos 1 cur prev gt next We now need to check for special cases when 1 pos 2 pos 1engthOfList 1 25 Implementing find Operation N0de ndN0de head int pos if pos lt 1 return NULL N0de cur head int curPos 1 While cur NULL ampamp curPos pos cur cur gt next curP0s return cur 26 An Improved remove Operation bool removeNodeamp head int pos check for special cases then use quot ndquot if necessary if hea NULL return false if pos 1 delete rst item Node p head head head gt next delete p return true nd quotprevquot and quotcurquot as identi ed above Use quot ndquot to locate quotprevquot quotcurquot is the next one Node prev ndpos l if prev NULL position not found return false Node cur prev gt next if cur NULL pos lengthOfList 1 return false prev gt next cur gt next delete node delete cur cur NULL return true 27 Inserting a Node into a Linked Ordinal List We use 3 prev pointer to point at the node preceding the new node after insertion Insert at the beginning of List head P ggggggggg 7 3 6 100 T 1 prev nethr Nodeilt nethr new Nodeitem nethr gt next head head p General insert a 20 7 77777777 7 40 gt gt W00 1 3O prev T Cur l nethr Nodeilt nethr new Nodeitem nethr gt next prev gt next prev gt next nethr 28 bool insertNodeamp head int pos int item preconditions 1 head is either NULL or it points to the rst node in a linked list 2 pos identi es the ordinal position where a new node containing quotitemquot is to be placed postconditions If it is possible to do so a new node containing the quotitemquot is created and linked into the appropriate spot in the list if pos 1 insert at the beginning of list Node nethr new Nodeitem nethr gt next head head nethr return true Node prev ndposl nd prev for insert if prev NULL position not found return false Node nethr new Nodeitem create new node nethr gt next prev gt next prev gt next nethr return true 29 Traversing a Linked List Use a pointer variable cur to keep track of the current node for Node cur head cur NULL cur cur gt next cout ltlt cur gt Item ltlt endl Example Executing cur cur gt next Before After gt 5 gt 10 o gt gt 5 1O o gt V cur cur Packaging Issues Node as we de ned it above is unsuitable for a variety of reasons 0 The application data namely the int item in struct Node is intermixed with list implementation data namely next Methods such as remove insert and the like should be methods of the list class not an individual list element 30 Consider Node p Q Is p a pointer to a list of nodes or a pointer to an individual node or a pointer to application data The problem is that so far we have combined three separate abstractions together The application data List elements The List itself Three Explicit Classes Data Class class Data public Data Dataconst Dataamp 1 Data private in our case this would be the single integer but The other two required classes are the List class and the ListNode class With the latter class being de ned as a private struct Within the former 31 PointerBased Implementation of ADT List Header le ListPh for the ADT list using pointer include quotListExceptionhquot include quotListlndexOutOfRangeExceptionhquot typedef Data ListltemType class List public List default constructor Listconst Listamp aList copy constructor List destructor standard list operations bool isEmpty const int getLength const void insertint index ListltemType newltem void removeint index void retrieveint index ListltemTypeamp dataltem const 32 private Note private data structure for the nodes struct ListNode a node on the list ListItemType item a data item on the list ListNode next pointer to next node end struct int size number of items in list ListNode head pointer to list of items ListNode ndint index const Returns a pointer to the indeXth node in the linked list end class End of header le Default Constructor ListList size0 headNULL 33 Copy Constructor Shallow Copy a size head 4 Copy of size Copy of head Only the data members head size will be copied Deep Copy b 4 gt 12 gt 3 gt 25 18 size head 4 gt 12 gt 3 gt 25 18 The whole list is copied must implement copy Copy of Copy of size head constructor Copy of the linked list 34 ListListconst Listamp aList sizeaListsize if aListhead NULL empty list head NULL else head new ListNode get rst node asserthead NULL check memory allocation copy rst item of old list head gt item aListhead gt item copy rest of old list ListNode neWPtr head for ListNode origPtr aListhead gt next origPtr NULL origPtr origPtr gt next nethr gt next new ListNode assertneWPtr gt next NULL neWPtr neWPtr gt next neWPtr gt item origPtr gt item neWPtr gt next NULL endif end copy constructor 35 assert Statement Must use include ltcassertgt Syntax assertb001eanexpression terminates program if false Destructor List List While lisEmptyO remove1 end destructor isEmpty bool List isEmpty const return b001size 0 end isEmpty getLength int List getLength const return size end getLength 36 ndindex List ListNode List ndint index const if index lt 1 index gt getLength return NULL index out of range else marching down the list ListNode cur head for int skip 1 skip lt index skip cur cur gt next return cur end nd Comparing Array amp PointerBased Implementations Size 7 Increasing the size of a resizable array can waste storage and time Storage requirements 7 Arraybased implementations require less memory than a pointerbased ones Access time 7 Arraybased Requires constant access time 7 Pointerbased The time to access the ith node depends on i Insertion and deletions 7 Arraybased Require shifting of data 7 Pointerbased Require traversing the list 37 Variations of Linked List 0 Sineg linked list 1 Linked list with dummy header n0de head Dummy head node Empty list head gt next NULL 2 Linked list with head and tail pointers head I tail Empty list head tail NULL 3 Doubly linked list H Able 39 Baker 39 Jones T l head Smith W1lson H39 Empty list head NULL 38 4 Circular linked list gt2 HA4 H FB Hg L list Empty list list NULL 5 Circular linked list with header node list V 10 20 header Empty list list list gt next 6 Circular doubly linked list with header node a listHead I 1 Able 392 Baker 1 Jones 1 Smnh 391 Wl SOH I Dummy head node T b llstHead im 1 I U Empty list list list gt next Array and Pointer Variables In C an array variable is a const pointer variable pointing to the rst indexed array variable Example include lti0streamgt using namespace std typedef int IntPtr int main IntPtr p int alO int index for index 0 index lt 10 index aindex index P 2 a for index 0 index lt 10 index cout ltlt pindex ltlt quot quot cout ltlt endl for index 0 index lt 10 index pindex pindex l for index 0 index lt 10 index cout ltlt aindex ltlt quot quot cout ltlt endl return 0 41 Output 0123456789 12345678910 Example void funcdouble p int length void useArrayO double p double X5 forinti0ilt5i Xi 20 i P 2 X M3 13 funcX5 void funcdouble p int length for int i O i lt length i cout ltlt pi ltlt endl Remark void funcd0uble p int length is equivalent to void funcd0uble p int length 42 Dynamic Array Dynamic array variable array size can be determined during runtime Creating Dynamic Arrays using Pointer Type typedef typeName yourTypeName yourTypeName arrayExample arrayExample new typenamearraysize Example int numExam 3 typedef d0uble avePtr avePtr examAve examAve new d0ublenumExam Remark This will create an array examAve of size 3 With base type double If numExam is input then the size of examAve Will be determined during runtime Destroying Dynamic Arrays using delete Operator delete arrayPtr Example delete examAve 43 Example Suppose I am reading a series of numbers om a le which need to be averaged sorted and printed Each set of numbers Will be stored in the form n V V I want arrays of exactly the right size I can neither afford to allocate arrays that are too large or too small include ltiostreamgt include ltfstreamgt using namespace std double readASetistreamamp is intamp nValues if is gtgt nValues make sure we are not at EOF double p new doublenValues for int i0 iltnValues i isgtgtpm return p return NULL signal EOF encountered 44 double averagedoub1e va1 int n equiv double averagedouble val int n Left as an exercise void printdoub1e va1 int n equiv void printdoub1e val int n Left as an exercise void sortdouble va1 int n equiv void sortdoub1e val int n Left as an exercise 45 void executive ifstream inputFilequotnumbersdatquot if inputFilefail return int n 0 double p readASetinputFilen While p NULL double avg averagepn sortpn printpn delete it to prevent a memory leak delete p NOTE delete p readASetinputFilen Classes amp Dynamic Arrays o A dynamic array like an ordinary array can have a class or struct type as a base type 0 A class or a struct can also have a dynamic array as a member 0 The basic techniques are exactly as you expect However there are some details When using classes and dynamic arrays that if neglected can cause a disaster 46
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'