Programming & Problem Solving II
Programming & Problem Solving II CECS 274
Popular in Course
Popular in Computer Science and Engineering
This 97 page Class Notes was uploaded by Zackary Cronin on Monday October 5, 2015. The Class Notes belongs to CECS 274 at California State University - Long Beach taught by Staff in Fall. Since its upload, it has received 6 views. For similar materials see /class/218755/cecs-274-california-state-university-long-beach in Computer Science and Engineering at California State University - Long Beach.
Reviews for Programming & Problem Solving II
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/05/15
CHAPTER 4 PART A POINTERS AND DYNAMIC DATA STRUCTURES Problem What if we don t know ahead of time at compile time the amount of variable space we will need If we under estimate an array size we ll get a runtime error If we over estimate an array size we ll have lots of unused memory Solution Allow variables to be created at execution time Dynamic Memory Defn Dynamic memory is space that is allocated for variables at execution time In C the operator new is used to create a variable dynamically new does two things 1 Allocates space for a dynamic variable and calls the associated constructor if it is an abstract data type 2 Returns the address memory location of the space it has allocated Details of new 0 The heap is the part of memory set aside for allocating dynamic variables When a program runs it is given an allotment of memory for the heap new must know how much space to allocate for a variable 0 The address of the newly allocated variable must be returned so that we can access it new returns the start of the address space 0 An pointer variable is a special type of variable that stores an address mm Dynamic Memory Allocation typedef int int ptr int ptr Count Count new int If the heap looks like this lusedlusedl 424 425 426 427 428 429 430 431 0 new allocates addresses 426 and 427 for the dynamic INTEGER variable 0 new returns the address 426 o the address 426 is stored in Count now Count provides access to the new created variable 0 Count is the integer stored in 426 and 427 0 Initially Count will have an unde ned value Example 2 Dynamic Memory Allocation typedef int RecPointer A RecPointer P1 P2 P3 P1 P2 P3 Q B P1 new int P1 P2 P3II C P3 P1 P1 P2 MD M D P1 new int P1 P2 P3 Q E P1 new int Here we see a memory leak P1 P2 MD 0 Example 3 Dynamic Memory Allocation struct Stuff char Initial oat Amount typedef Stuff StuffPtr Stuff Temp StuffPtr APtr BPtr CPtr Templnitial B TempAmount 00 APtr new Stuff APtrgtInitia1 A APtrgtAmount 107 BPtr APtr CPtr new Stuff CPtr Temp APPENDIX A Arrays memory and Allocation Basics Carrano Helman Veroff pp A25A30 A Arrays Defn Arrays are indexed collections of components all of the same type When using an array in C the dimensions and type of elements stored in the array must be declared The dimensions of the array will always begin with 0 Example const int CALENDAR 12 double Income CALENDAR This declaration will create an array called Income made up of twelve variables of type double The indices of the array will be Oto 11 B Memory and Allocation Basics Typical storage types for computers 1 Random Access Memory RAM fast and volatile 2 Disk slow relatively speaking and permanent Typical Memory Organization 0 Bytes are groups of 8 bits 0 A Byte can store 28 256 different values 0 Bytes are indexed by address Storage of Values A11 program variables are stored in Bytes of RAM They may occupy one or more Bytes Usually Characters 1 Byte Integers 2 Bytes Now typically 4 bytes Floats 4 Bytes This can vary depending on the machine being used Larger quantities eg arrays strings etc are made up of combinations of these Byte allotments It is the compiler that decides computes the actual locations where variables will be stored Storage Allocation Consequences The size of the storage space limits the quantities that can be stored Example For INTEGERS o 1 Byte 128127 since 28256 o 2 Bytes 3276832767 since 21665536 o 4 Bytes 2147483648 2147483637 since 2324294967296 For FLOATS The more Bytes available the more digits that can be stored after the decimal point Storing and Accessing an Array typedef int ID4 ID X X0 X1 X2 X3 424 425 426 427 428 429 430 431 To compute the location of Xi 424 j 0 2 In general the formula for an array A is ampAi Starting Address j lSt Index Component Size The compiler calculates this arithmetic formula so that the elements of the array can be easily accessed Arrays of Larger Components typedef int IDlO typedef ID ListlOO List Students The component size of ID is 20 10 integers at 2 I3ytescharacter To nd Studentsj ampStudentsj Starting Address j O 102 Accessing Nested Components of Arrays typedef int Data8 typedef Data Total97 Total S If integers are each 2 Bytes then the size of each component of S is 8 2 16 the full size of Data To nd Si ampSj Starting Address j 1st Index of Total 16 To nd Sjk ampSjllk 5U k 1st Index of Data Component size of Data Starting address j O 16 k O 2 Arrays with Multiple Dimensions In storing a 2dimensional array matrix either the rows or columns can be grouped together For simplicity we will assume the rows are grouped together in rowmaj or order Example typedef float Matrix43 Matrix Z In rowmajor order the rows are stored together The elements are grouped by the 1St index Z0 Z1 Z2 Z3a 100 111 112 123 124 135 136 147 Formulas for 2Dimensi0nal Arrays Rowmajor Order ampZjk Starting address j 1st index of dimension 1 row size k 1st index of dimension 2 component size where the row size last index of dimension 2 1st index of dimension 2 1 component size C Adding Flexibility t0 Arrays in C Defn An unconstrained array is an array in which the bounds of the array and the indices of the array are not speci ed when the type is declared Unlike Ada the C language does not have builtin unconstrained arrays In C the indices of arrays must be declared and all arrays begin with index 0 However a programmer can create an array class that permits the equivalent of Ada39s unconstrained arrays and beginning index value Example A vector class for onedimensional integer arrays class vector public vector constructor lastindex firstindex vectorsize l space is allocated dynamically vectorint vectorsize int firstindex 0 m private int array int size int first int last To instantiate two onedimensional arrays one consisting of 5 elements beginning with index 0 and the other consisting of 10 elements beginning with index 1 vector arrayA5 vector arrayBlO l Example A matrix class can also be created for two dhnenmonalhuegeranaysPohlp189 class matrix public matrix constructor space is allocated dynamically matrixiht horow int hocol int rowihdex 0 int colihdex O m private int mat stores the base address of an array of pointers to int which in turn stores a base address for each row of the matrix type int row int col int begrow int ehdrow int begcol int ehdcol CHAPTER 3 ABSTRACT DATA TYPES A Abstraction Abstraction is the primary technique used to decompose complex computer problems into manageable pieces that can be solved 1 What is abstraction 0 Viewing solutions to a computer problem in natural or appropriate terms 0 The part of a solution made Visible to the user 2 What is implementation 0 A conversion of the abstract solution into a concrete one suitable for coding in a real programming language 0 The messy details which have been hidden away from the user Example 1 Integers int Mathematically C Abstraction Computer Implementation Example 2 Matrices Mathematically C Abstraction Computer Implementation Defn Information hiding is using abstraction to hide the unnecessary details of a data representation or a procedure from those who have no need or no desire to see them C provides a number of features that help with abstraction subtypes types initialization of variables classes private operator overloading B Abstract Data Types Defn An abstract data type ADT is an abstract description of a data type It is a description of the values of the type and the operations that can be performed on those values A program that uses an ADT is called a client program A client program should use the objects and operations of the ADT abstractly ADTs are the primary building blocks we will use to create good programs C C Classes Classes and structures can be used almost identically in C The difference between the two is in the default accessibility associated with the members of each to be discussed later 0 Members are public by default in structs 0 Members are private by default in classes Classes enable the programmer to model objects that have attributes represented as data members and behaviors or operations represented as member functions A C class declaration consists of any number of member functions data members objects and access modes private public or protected The following general form for a class declaration is class classname public memberfunctionprototypes private datamembers The memberfunctionprototypes after the access mode public represent the operations The datamembers after access mode private are the objects that store the state Member functions can be private and data members can be public The accepted standard is to make data members private as much as possible and to allow access to the private data members Via public member functions Member functions are sometimes called methods in other obj ect oriented programming languages and are invoked in response to messages sent to an object A message corresponds to a memberfunction call Example 1 The Class Time Class De nition class Time public Time void setTimeint int int void printMilitary void printStandardO private int hour int minute int second w De nition begins with the keyword class The body of the class de nition is delineated with left and right braces The class de nition terminates with a semicolon The de nition contains the three integer members hour minute and second Notes Cont d The public and private labels are called member access speci ers Any data member or member function declared after member access speci er public and before the next member access speci er is accessible wherever the program has access to an object of class Time Any data member or member function declared after member access speci er private and up to the next member access speci er is accessible only to member functions of the class and friend functions Member access speci ers always end with a colon and can appear multiple times and in any order in a class de nition But use each member access speci er only once in a class de nition for clarity and readability 0 Place public members rst where they are easy to locate o The class de nition contains prototypes for the following four member functions after the public member access speci er Time setTime printMilitary and printStandard These are the public member functions or public services or interface of the class These functions will be used by clients ie portions of a program that are users of the class to manipulate the data of the class The member function with the same name as the class is called a constructor function of that class A constructor is a special member function that initializes the data members of a class object Notes Cont d A class39s constructor function is called automatically when an object of the class is created It is common to have several constructors for a class this is accomplished through function overloading The three integer members appear after the private member access speci er These data members of the class are only accessible to member functions and to be discussed later quotfriendsquot of the class Data members are normally listed in the private portion of a class and member functions are normally listed in the public portion Once the class has been de ned the class name becomes a new type speci er and can be used as a type in declarations as follows Time sunset object of type Time Time arrayOfTimes5 array of Time objects Time gt pointerToTime pointer to a Time object Time ampdinnerTime sunset reference to alias of a Time object Member Functions The full implementation of member functions typically includes the following items The member function39s declared return type 0 The class name 0 The C scope resolution operator two consecutive colons o The member function name 0 The parameters contained between two parentheses o A block that delimits the statements of the member function Syntax retumtype classname memberfunctionname parameter list declarations statements Example 1 The Class Time The following is a listing of the file which contains the specification ie the definition of the class the implementation ie the definition of the functions contained in the class of the class Time and the client routine the driver or main program Note the Time constructor which initializes the data members to 0 the military time equivalent of 12 AM This ensures that the object is in a consistent state when it is created Invalid values cannot be stored in the data members of a Time object because the constructor is automatically called when the Time object is created and all subsequent attempts by a client to modify the data members are scrutinized by the function setTime Member functions can be defined inside a class but it is a good programming practice to define the functions outside the class definition Note the use of the scope resolution operator in each member function definition following the class definition Once a class is defined and its member functions are declared the member functions must be defined Each member function of the class can be defined directly in the class specification rather than including the function prototype of the class or the member function can be defined after the class body When a member function is defined outside of its corresponding class definition the function name is preceded by the class name and the scope resolution operator 2 Because different classes can have the same member names the scope resolution operator quottiesquot the member name to the class name to uniquely identify the member functions of a particular class The member function is considered to be within that class39s scope If a member function is defined in a class definition the member function is automatically inlined Member functions defined outside a class definition may be made inline by explicitly using the keyword inline The compiler reserves the right not to inline any function Time class include ltiostreamhgt Time abstract data type ADT de nition class Time public Time constructor void setTimeint int int set hour minute and second void printMilitary print military time format void printStandardO print standard time format private int hour O 23 int minute O 59 int second O 59 Time constructor initializes each data member to zero Ensures all Time objects start in a consistent state TimeTime hour minute second O Set a new Time value using military time Perform validity checks on the data values Set invalid values to zero void Time setTimeint h int m int s hourhgt0ampamphlt24h0 minutemgt0ampampmlt60m0 secondsgt0ampampslt60s0 Print Time in military format void Time printMilitary cout ltlt hour lt 10 quotOquot quotquot ltlt hour ltlt quotquot ltlt minute lt 10 quotOquot quotquot ltlt minute ltlt quotquot ltlt second lt 10 quotOquot quotquot ltlt second Print time in standard format void Time printStandard cout ltlt hour 0 hour 12 12 hour 12 ltlt quotquot ltlt minute lt 10 quotOquot quotquot ltlt minute ltlt quotquot ltlt second lt 10 quotOquot quotquot ltlt second ltlt hour lt 12 quot AMquot quot PMquot Driver to test simple class Time main Time t instantiate objectt of class Time cout ltlt quotThe initial military time is quot tprintMilitary cout ltlt endl ltlt quotThe initial standard time is quot tprintStandard tsetTimel3 27 6 cout ltlt endl ltlt endl ltlt quotMilitary time after setTime is quot tprintMilitary cout ltlt endl ltlt quotStandard time after setTime is quot tprintStandard tsetTime99 99 99 attempt invalid settings cout ltlt endl ltlt endl ltlt quotAfter attempting invalid settingsz39 ltlt endl ltlt quotMilitary time quot tprintMilitary cout ltlt endl ltlt quotStandard time quot tprintStandard cout ltlt endl return 0 Output is The initial military time is 000000 The initial standard time 120000 AM Military time after setTime is 132706 Standard time after setTime is 12706 PM After attempting invalid settings Military time 000000 Standard time 120000 AM Example 2 The Class Currency an ADT for Currency Speci cation class Currency public Currency Currency MakeCurrency oat f oat MakeFloat int GetDollars int GetCents bool operatorCurrency c Currency operatorCurrency c Additional functions would go here private bool Positive int Dollars int Cents FILE Currencycpp include Currencyh Not all function de nitions are shown CurrencyCurrency Positive true Dollars 0 Cents O Currency CurrencyoperatorCurrency c Currency result int TempCents TempCents Cents cCents if TempCents gt 99 we need to carry resultCents TempCents 100 resultDollars Dollars cDollars l else resultCents TempCents resultDollars Dollars cDollars return result 20 FILE testCurrencycpp include Currencyh void main Currency A B C AMakeCurrency654 Store amount BMakeCurrency200 C A B Use the add function if C B Test for equality if C 854 This will not compile if C AMakeCurrency854 This will compile 21 B ADT for List Operations 1 Create an empty list CreateList PRECONDITION none POSTCONDITION Creates an empty list 2 Destroy a list DestroyList PRECONDITION none POSTCONDITION Destroys a list 3 Determine whether a list is empty ListIsEmpty PRECONDITION none POSTCONDITION Determines whether a list is empty 4 Determine the number of items on a list ListLengthO PRECONDITION none POSTCONDITION Returns the number of items that are in a list 5 Insert an item at a given position in the list ListInsert NewPosition NewItem Success PURPOSE Inserts NewItem at position NewPosition of a list PRECONDITION l lt NewPosition lt ListLength l POSTCONDITION If NewPosition lt ListLengthO items are renumbered as follows The item at NewPosition becomes the item at NewPosition 1 the item at NewPositi0nl becomes the item at Newposition2 and so on Success indicates whether the insertion was successful 22 6 Delete the item at a given position in the list ListDelete Position Success PURPOSE Deletes the item at position Position ofa list PRECONDITION l lt Position lt ListLengthO POSTCONDITION If Position lt ListLengthO items are renumbered as follows The item at P0siti0nl becomes the item at Position the item at P0siti0n2 becomes the item at P0siti0nl and so on Success indicates whether the deletion was successful 7 Look at retrieve the item at a given position in the list ListRetrieve Position Dataltem Success PURPOSE Copies the item at position Position of a list into Dataltem PRECONDITION 1 lt POSITION lt ListLengthO POSTCONDITION The list is left unchanged by this operation Success indicates whether the retrieval was successful 23 Array Implementation of a list Text pages 136 139 Header le ListAh for the ADT list Arraybased implementation const int MAXiLIST maximumsizeoflist typedef desiredtypeoflistitem listltemType class listClass public listClass default constructor destructor is supplied by compiler list operations bool ListIsEmptyO const Determines whether a list is empty Precondition None Postcondition Returns true if the list is empty otherwise returns false int ListLengthO const Determines the length of a list Precondition None Postcondition Returns the number of items that are currently in the list void Listlnsertint NewPosition listltemType Newltem boolamp Success Inserts an item into a list Precondition NewPosition indicates where the insertion should occur Newltem is the item to be inserted Postcondition If insertion was successful Newltem is at position NewPosition in the list other items are renumbered accordingly and Success is true otherwise Success is false Note Insertion will not be successful if NewPosition lt l or gt ListLengthl 24 void ListDeleteint Position boolamp Success Deletes an item from a list Precondition Position indicates where the deletion should occur Postcondition If 1 lt Position lt ListLength the item at position Position in the list is deleted other items are renumbered accordingly and Success is true otherwise Success is false void ListRetrieveint Position listItemTypeamp DataItem boolamp Success const Retrieves a list item by position number Precondition Position is the number of the item to be retrieved Postcondition If 1 lt Position lt ListLength DataItem is the value of the desired item and Success is true otherwise Success is false private listItemType ItemsMAX7LIST array of list items int Size number of items in list int IndeXint Position const Converts the position of an item in a list to the correct index within its array representation end class End of header le 25 Implementation le ListAcpp for the ADT list Arraybased implementation include quotListAhquot header le listClasslistClass Size0 end default constructor bool listClassListIsEmpty const return boolSize 0 end ListIsEmpty int listClassListLength const return Size end ListLength void listClassListInse1tint NewPosition listItemType NewItem boolamp Success Success bool NewPosition gt 1 ampamp NewPosition lt Sizel ampamp Size lt MAXiLIST if Success make room for new item by shifting all items at positions gt NewPosition toward the end of the list no shift if NewPosition Sizel for int Position Size Position gt NewPosition Position ItemsIndeXPositionl ItemsIndeXPosition insert new item Items IndeXNewPosition NewItem Size end if end ListInsert void listClassListDeleteint Position boolamp Success Success bool Position gt 1 ampamp Position lt Size 26 if Success delete item by shifting all items at positions gt Position toward the beginning of the list no shift if Position Size for int FromPosition Positionl FromPosition lt Size FromPosition Items IndeXFromPosition 1 Items IndeXFromPosition Size end if end ListDelete 27 void listClassListRetrieveint Position listItemTypeamp DataItem boolamp Success const Success bool Position gt 1 ampamp Position lt Size if Success DataItem Items IndeXPosition end ListRetrieve int listClassIndeXint Position const return Positionl end Index End of implementation le include ltiostreamhgt include quotListAhquot ADT list operations int main listClass L listItemType DataItem bool Success LListInsertl 20 Success LListRetrievel DataItem Success 28 CHAPTER 7 QUEUES Defn A gueue is a data structure in which the item rst in is the item rst out FIFO Examples 0 checkout line at a grocery store 0 drivethru window at Taco Bell 0 printer queue We want to design an ADT for Queues The data structure must provide the following attributes 0 length 0 front 0 back 0 contents The following operations must be provided in the ADT o enqueue add to the back of the queue o dequeue remove from the front of the queue getFront get information stored in the rst item of the queue o isEmpty check to see if the queue is empty 0 Initialize create an empty queue We will look at two possible implementations of Queue ADTs 0 Simple linked list 0 Circular array Linked List Implementation of Queues Problem In arraybased implementations the maximum queue size is determined at compile time Solution Use a linked structure to store the queue elements dynamically In the Author s ADT o The queue is a simple linked list where frontPtr points to the node at the front of the queue and bacthr points to the node at the back 0 The front of queue is the front of the list 0 The back of queue is the back of the list S eci cation for the Linked ueue typedef desiredetypeeofequeueeitem QueueItemType class Queue public Queue Queueconst Queueamp Q NQueue bool isEmpty void enqueueQueueItemType NeWItem throwQueueException void dequeue throwQueueException void dequeueQueueItemTypeamp queueFront throwQueueException void getFrontQueueItemTypeamp queueFront const throwQueueException const private struct QueueNode QueueItemType item QueueNode next QueueNode frontPtr QueueNode bacthr C Code void void void QueueenqueueQueueltemType newltem throwQueueException QueueNode nethr new QueueNode if nethr NULL throw QueueException quotQueueException enqueue cannot allocate memoryquot else nethr gtitem Newltem if isEmpty frontPtr nethr else bacthr gtnext nethr bacthr nethr new node is at back QueuegetFrontQueueltemTypeamp queueFront const throwQueueException if isEmpty throw QueueException quotQueueException empty queue cannot get frontquot else QueueFront frontPtr gtitem Queuedequeue throwQueueException if isEmpty throw QueueException quotQueueException empty queue cannot dequeuequot else QueueNode temthr frontPtr if frontPtr bacthr one node in queue frontPtr NULL bacthr NULL else frontPtr frontPtr gtnext temthr gtnext NULL safeguard delete temthr void QueuedequeueQueueItemTypeamp queueFront throwQueueException if isEmpty throw QueueException quotQueueException empty queue cannot dequeuequot else queueFront frontPtr gtitem dequeue delete front Circular Array Implementation of Queues Problem With simple arrays the contents of the queue must be shifted to the front upon each deletion Solution Don t slide things to the front use a circular array that allows the front to move Now we need to know where the front is located in the array const int MAX QUEUE maximumesizeeofequeue typedef desiredetypeeofequeueeitem QueueItemType class Queue public Queue Queueconst Queueamp booi isEmpty Const void enqueueQueueItemType newItem throwQueueException void dequeue throwQueueException void dequeueQueueItemTypeamp queueFront throwQueueException void getFrontQueueItemTypeamp queueFront const throwQueueException private QueueItemType itemsMAXiQUEUE int front Init to 0 int back Init to MAX QUEUE 1 int count Init to O C Code 0 The next open spot is back 1 mod MAXQUEUE 0 Changing the index range to 0MAXQUEUE 1 helps with the mod void QueueenqueueQueueltemType newltem throwQueueException if count MAX QUEUE throw QueueException quotQueueException queue full on enqueuequot else back back l MAX QUEUE itemsback newltem count void QueuegetFrontQueueltemTypeamp queueFront const throwQueueException if isEmpty throw QueueException quotQueueException empty queue cannot get frontquot else queueFront itemsfront void Queuedequeue throwQueueException if isEmpty throw QueueException quotQueueException empty queue cannot dequeuequot else front front l MAX QUEUE count void QueuedequeueQueueltemTypeamp queueFront throwQueueException if isEmpty throw QueueException quotQueueException empty queue cannot dequeuequot else queueFront itemsfront front front l MAX QUEUE count Comparison of ADT Implementation for Queues Programming Memory Execution Time Other Dif culty J 39 Simple Linked List W Front and Back Pointers Circular Array Making the Linked List ADT Generic using a Template see pages 409412 in the Textbook include ltcstddefgt include quotListExceptionhquot include quotListIndexOutOfRangeExceptionhquot template ltclass Tgt class List template ltclass tgt class ListNode friend class ListltTgt private ListNode nextNULL ListNodec0nst Tamp nodeItem ListNode ptr itemnodeItem nextptr T item ListNode next template ltclass Tgt class List public constructors and destructor List default constructor Listconst ListltTgtamp aList copy constructor List deletes all nodes in list list operations Listamp operatorconst ListltTgtamp aList bool isEmpty const int getLengthO const void insertint index T newItem throwListIndexOutOfRangeException ListException void removeint index throwListIndexOutOfRangeException void retrieveint index Tamp dataItem const throwListIndexOutOfRangeException private int size number of items in list ListNodeltTgt head pointer to linked list of items ListNodeltTgt ndint index const returns a pointer to the positionth node in the linked list Sample Generic Member Function template ltclass Tgt void ListltTgtinsertint index T newItem throwListIndexOutOfRangeException ListException int newLength getLengthO l ifindex lt l H index gt newLength throw ListIndexOutOfRangeException quotListOutOfRangeException insert index out of rangequot else create new node and place newItem in it ListNodeltTgt nethr new ListNodeltTgt if nethr NULL throw ListException quotListException insert cannot allocate memoryquot else size newLength nethrgtitem newItem attach new node to list if index l insert new node at beginning of list nethrgtnext head head nethr else ListNodeltTgt prev ndindex l insert new node after node to which Prev points nethrgtnext prevgtnext prevgtnext nethr Using the Generic Template List ADT int main Listltdoublegt floatList Listltchargt charList floatListinsertl 11 floatListinsert2 22 charListinsertl 39a39 charListinsert2 39b39 Guidelines for Program Documentation and Coding Style Documenting programs is an essential component of writing good code When documentation is done correctly and before the actual code is written it is part of the design process that helps programs to satisfy their speci cations We shall adopt the following program documentation and coding style model I An initial comment for each C program or class containing the following information in the style as shown with proper spacing between paragraphs File name Where code is stored Author and date Purpose Major algorithms and data structures used Input and output Exceptions or What could go wrong II An initial comment block in each function of the program or class in the following style that include comments as listed returnType functionName parameters Purpose Preconditions Postconditions Functions called if any III Comments in the body of each function to explain difficult code or subtle logic The designlevel program documentation of items I and II should be completed before any C code is written Item III will be written at the time of coding IV Choose identifiers that re ect their purpose Distinguish between keywords and user defined identifiers with the following conventions 0 Keywords in the language eg int are lowercase as provided 0 Names of standard functions eg cout rand are lowercase as provided Userdefined identifiers use both upper and lowercase letters as follows Class names consist of words with first letter of each word capitalized El Function names begin with a lowercase letter with first letter of subsequent internal words capitalized El Variables begin with a lowercase letter with first letter of subsequent internal words capitalized Data types declared in a typedef statement and names of structures and enumerations each begin with an uppercase letter El Named constants and enumerators are entirely uppercase and use underscores to separate words D D Adopted from CECS 274 Program Documentation Guidelines by Maples and Data Abstraction and Problem Solving with C by Carrano and Prichard pp 39742 Data types declared in a typedef statement should end in Type and exception names should end in Exception V A good indentation style will enhance the readability of a program Guidelines for indentation style Blocks should be indented sufficiently so that they stand out clearly Indentation should be consistent ie indent the same amount of space at each level and indent the same type of construct in the same manner The indentation style should provide a reasonable way to handle the problem of rightward drift the problem of nested blocks bumping against the righthand margin of the page When braces are required for a compound statement place the opening brace on the same line as the statement keyword and line up the closing brace with the beginning of the keyword as follows while expression statements end while do statements while expression if expression statements else statements switch expression case condition1 action1 break case conditionz actionz break 0 O Adopted from CECS 274 Program Documentation Guidelines by Maples and Data Abstraction and Problem Solving with C by Carrano and Prichard pp 39742 More vi Here are some additional movement commands current one more current to start Here are some additional edit commands cursor Dr Tracy Bradley Maples CECS 274 Programming and Problem Solving II Program Documentation Documenting programs is an essential component of writing good code When documentation is done correctly and before the actual code is written it is part of the design process that helps programs to satisfy their specifications The documentation model we will use is as follows I An initial comment for each C class or program containing the following information A Purpose B Author and date D Major algorithms and data structures used C Input and output E Exceptions or what could go wrong II Initial comments in each function of the class that include A Purpose B Preconditions C Postconditions D Functions called if any III Comments in the body of each function to explain dif cult code or subtle logic The designlevel program documentation of items I and II should be completed before any C code is written Item III will be written at the time of coding Dr Tracy Bradley Maples Modi ed form Carrano Helman and Veroff p 39 CHAPTER 10 BINARY TREES E Binary Search Tree Implementation The following C statements describe the data in a tree node from Carrano Helmann amp Veroff p 519 typedef desz39red tjpeo searcbkeyKeyType class Keyedltem public Keyedltemo Keyedltemconst KeyTypeamp keyValue searchKeykeyValue KeyType getKeyO const returns search key return searchKey private KeyType searchKey and possibly other data members A pointer based implementation of the ADT binary search tree from Carrano Helmann amp Veroff pp 538546 include quotKeyedltemhquot de nition of Keyedltem typedef Keyedltem TreeltemType class TreeNode friend class BinarySearchTree private TreeNodeO TreeNodeconst TreeltemTypeamp nodeltem TreeNode left NULL TreeNode right NULL itemnodeltem leftChildPtrleft rightChildPtrright TreeltemType item TreeNode leftChildPtr rightChildPtr Note The declaration creates recursively defined le and right subtrees stored by key value Data is stored in each node 10 include quotTreeNodehquot See pages 512513 in the textbook typedef void FunctionTypeTreeItemTypeamp anItem class BinarySearchTree public BinarySearchTreeO BinarySearchTreeconst BinarySearchTreeamp tree virtual BinarySearchTree virtual bool isEmptyO const virtual void searchTreeInsertconst TreeItemTypeamp newItem throwTreeException virtual void searchTreeDeleteKeyType searchKey throwTreeException virtual void searchTreeRetrieveKeyType searchKey TreeItemTypeamp treeItem const throwTreeException virtual void preorderTraverseFunctionType visit virtual void inorderTraverseFunctionType visit virtual void postorderTraverseFunctionType visit virtual BinarySearchTreeamp operatorconst BinarySearchTreeamp rhs protected void insertItemTreeNodeamp treePtr const TreeItemTypeamp newItem throwTreeException void deleteItemTreeNodeamp treePtr KeyType searchKey throwTreeException void deleteNodeItemTreeNodeamp nodePtr void processLeftmostTreeNodeamp nodePtr TreeItemTypeamp treeItem void retrieveItemTreeNode treePtr KeyType searchKey TreeItemTypeamp treeItem const throwTreeException other functions and data members private TreeNode root pointer to root of tree Examgle A tree as represented using our declaration BinarySearchTree T n Rnnt Package Carrano Helman amp Veroff pp 543546 void BinarySearchTree preorderTraverseFunctionType visit preorderroot visit void BinarySearchTree preorder TreeNode treePtr FunctionType visit if treePtr NULL visittreePtrgtItem preordertreePtrgtle ChildPtr visit preordertreePtrgtrightChildPtr visit void BinarySearchTree inorderTraverseFunctionType visit inorderroot visit void BinarySearchTree inorder TreeNode treePtr FunctionType visit if treePtr NULL inordertreePtrgtle ChildPtr visit visittreePtrgtItem inordertreePtrgtrightChildPtr visit void BinarySearchTree postorderTraverseFunctionType visit postorderroot visit void BinarySearchTree postorder TreeNode treePtr FunctionType visit if treePtr NULL postordertreePtrgtle ChildPtr visit postordertreePtrgtrightChildPtr visit visittreePtrgtItem void BinarySearchTree searchTreeInsertconst TreeItemTypeamp newItem insertItemroot newItem void BinarySearchTree insertItemTreeNodeamp treePtr const TreeItemTypeamp newItem throwTreeException if treePtr NULL position of insertion found insert a leaf create a new node treePtr new TreeNodenewItem NULL NULL was allocation successful if treePtr NULL throw TreeExceptionquotTreeException insert failedquot else search for the insertion position else if newItemgetKey lt treePtrgtitemgetKey search the left subtree insertItemtreePtrgtle ChildPtr newItem else search the right subtree insertItemtreePtrgtrightChildPtr newItem void BinarySearchTree searchTreeRetrieveKeyType searchKey TreeItemTypeamp treeItem const throwTreeException retrieveItemroot searchKey treeItem void BinarySearchTree retrieveItemTreeNode treePtr KeyType searchKey TreeItemTypeamp treeItem throwTreeException if treePtr NULL throw TreeExceptionquotTreeException searchKey not foundquot else if searchKey treePtrgtitemgetKey item is in the root of some subtree treeItem treePtrgtitem else if searchKey lt treePtrgtitemgetKey search the left subtree retrieveItemtreePtrgtle ChildPtr searchKey treeItem else search the right subtree retrieveItemtreePtrgtrightChildPtr searchKey treeItem void BinarySearchTree searchTreeDeleteKeyType searchKey throwTreeException deleteItemroot searchKey void BinarySearchTree deleteItemTreeNodeamp treePtr KeyType searchKey throwTreeException if treePtr NULL searchKey not found throw TreeExceptionquotTree exception delete failedquot else if searchKey treePtrgtitemgetKey item is in the root of some subtree deleteNodeItemtreePtr delete the item else if searchKey lt treePtrgtitemgetKey search the left subtree deleteItemtreePtrgtle ChildPtr searchKey else search the right subtree deleteItemtreePtrgtrightChildPtr searchKey void BinarySearchTreedeleteNodeItemTreeNodeamp nodePtr Algorithm note There are four cases to consider l The root is aleaf 2 The root has no left child 3 The root has no right child 4 The root has two children TreeNode delPtr TreeItemType replacementItem test for a leaf if nodePtrgtleftChildPt NULL ampamp nodePtrgtrightChildPtr NULL delete nodePtr nodePtr NULL test for no left child else if nodePtrgtleftChildPtr NULL delPtr nodePtr nodePtr nodePtrgtrightChildPtr delPtrgtrightChildPtr NULL delete delPtr test for no right child else if nodePtrgtrightChildPtr NULL delPtr nodePtr nodePtr nodePtrgtleftChildPtr delPtrgtleftChildPtr NULL delete delPtr there are two childrenretrieve and delete the inorder successor else processLeftmostnodePtrgtrightChildPtr replacementItem nodePtrgtitem replacementItem void BinarySearchTree processLeftmostTreeNodeamp nodePtr TreeItemTypeamp treeItem if nodePtrgtleftChildPt NULL treeItem nodePtrgtitem TreeNode delPtr nodePtr nodePtr nodePtrgtrightChildPtr delPtrgtrightChildPtr NULL delete delPtr else processLeftmostnodePtrgtleftChildPtr treeItem CHAPTER 10 BINARY TREES A Tree Terminology Defn A m can be de ned in one of the following different but equivalent manners o a connected graph with no cycles 0 a directed acyclic graph with one node from which all other nodes are reachable Example Defn Defn Defn Defn Defn In a tree the node from which all other nodes are reachable is called the root The children of a node X are all of the nodes you can access from X by following one edge The parent of a node X is the node of which X is a child The siblings of a node X are all other children with the same parent as X The descendants of a node X are all of the nodes reachable from X Defn The ancestors of a node X are all of the nodes for which X is a descendant Defn A leaf or terminal node of a tree is a node with no descendants Defn An interior or nonterminal node of a tree is a node with descendants Defn A subtree is a node X and all of its descendants Defn The depth of a tree T is the number of edges from the root of T to the furthest leaf of T B Binary Trees Defn A binary tree is a tree in which every node has at most two children Example 9 3 0 G 9 a 6 03 Defn A strictly binary tree is a tree in which every node has either 0 or 2 children Defn A binary tree of depth k is called M if it contains all possible nodes at depth k Example A full tree of depth 2 Defn A complete binary tree is an almost full binary tree except that it may be missing nodes at the righthand side of the lowest level Example A complete tree Defn A binary tree is balanced if for each node in the tree the depth of the left subtree differs from the depth of the right subtree by at most 1 The empty subtree has depth 1 Example A balanced tree C Binary Tree Traversals Defn A tree traversal is a method of traveling from node to node through a tree visiting every node There are three types of traver sals l Pr eorder preorder node visit the node preordernode s left subtree preordernode s right subtree 2 Inorder inorder node inordernode s left subtree visit the node inordernode s right subtree 3 Postorder postorder node postordernode s left subtree postordernode s right subtree visit the node Examgle Tree Traversals 09 Preorder A B D E G C F Inorder D B G E A C F Postorder D G E B F C A D Binary Search Trees Defn A binary search tree is a binary tree with an ordering that follows this rule for each node X in the tree 0 the left subtree of X stores values less than X o the right subtree of X stores values greater than X A binary search tree is useful for storing and retrieving data Example CHAPTER 10 BINARY TREES E Binary Search Tree Implementation The following C statements describe the data in a tree node from Carrano Helmann amp Veroff p 470 class itemClass public keyType Key const returns search key private keyType SearchKey and possibly other data members A pointer based implementation of the ADT binary search tree from Carrano Helmann amp Veroff pp 487495 typedef desz39red tjpeo searcbkeykeyType include quotDatahquot de nition of itemClass typedef itemClass treeltemType See page 464 in the textbook typedef vo39rl mctionTypetreeItemTypeamp AnItem struct treeNode forward reference typedeftreeNode ptrType pointer to node struct treeNode treeltemType Item ptrType LChildPtr RChildPtr constructor treeNodeconst treeltemTypeamp Nodeltem ptrType L ptrType R ItemNodeItem LChildPtrL RChildPtrR Note The declaration creates recursively de ned le and right subtrees stored by key value Data is stored in each node 10 class bstClass public bstClass bstClassconst bstClassamp Tree virtual bstClass virtual bool SearchTreeIsEmptyO const virtual void SearchTreeInsertconst treeItemTypeamp NewItem boolamp Success virtual void SearchTreeDeletekeyType SearchKey boolamp Success virtual void SearchTreeRetrievekeyType SearchKey treeItemTypeamp TreeItem boolamp Success const virtual void PreorderTraversefunctionType Visit virtual void InorderTraversefunctionType Visit virtual void PostorderTraversefunctionType Visit virtual bstClassamp operatorconst bstClassamp Rhs protected void InsertItemptrTypeamp TreePtr const treeItemTypeamp NewItem boolamp Success void DeleteItemptrTypeamp TreePtr keyType SearchKey boolamp Success void DeleteNodeItemptrTypeamp NodePtr void ProcessLeftMostptrTypeamp NodePtr treeItemTypeamp TreeItem void RetrieveItemptrType TreePtr keyType SearchKey treeItemTypeamp TreeItem boolamp Success const other functions and data members private ptrType Root pointer to root of tree Examgle A tree as represented using our declaration bstTree T Package Carrano Helman amp Veroff pp 455463 void bstClassPreorderTraversefunctionType Visit PreorderRoot Visit void bstClassPreorder ptrType TreePtr functionType Visit if TreePtr NULL VisitTreePtrgtItem PreorderTreePtrgtLChildPtr Visit PreorderTreePtrgtRChildPtr Visit void bstClass InorderTraversefunctionType Visit InorderRoot Visit void bstClassInorder ptrType TreePtr functionType Visit if TreePtr NULL InorderTreePtrgtLChildPtr Visit VisitTreePtrgtItem InorderTreePtrgtRChildPtr Visit void bstClassPostorderTraversefunctionType Visit PostorderRoot Visit void bstClassPostorder ptrType TreePtr functionType Visit if TreePtr NULL PostorderTreePtrgtLChi1dPtr Visit PostorderTreePtrgtRChildPtr Visit VisitTreePtrgtItem void bstClassSearchTreeRetrievekeyType SearchKey treeItemTypeamp TreeItem boolamp Success const RetrieveltemR00t SearchKey TreeItem Success void bstClassRetrieveltemptrType TreePtr keyType SearchKey TreeItemTypeamp TreeItem boolamp Success const if TreePtr NULL Success false empty tree else if SearchKey TreePtrgtItemKey item is in the root of some subtree TreeItem TreePtrgtItem Success true else if SearchKey lt TreePtrgtItemKey search the left subtree RetrieveltemTreePtrgtLChildPtr SearchKey TreeItem Success else search the right subtree RetrieveItemTreePtrgtRChildPtr SearchKey TreeItem Success void bstClassInsertItemptrTypeamp TreePtr const treeItemTypeamp NewItem boolamp Success if TreePtr NULL position of insertion found insert after leaf create a new node TreePtr new treeNodeNewItem NULL NULL was allocation successful Success boolTreePtr NULL else search for the insertion position else if NewItemKey lt TreePtr7gtItemKey else search the left subtree InsertItemTreePtrgtLChildPtr NewItem Success search the right subtree InsertItemTreePtrgtRChildPtr NewItem Success void bstClassDeleteItemptrTypeamp TreePtr keyType SearchKey boolamp Success if TreePtr NULL Success false else if SearchKey TreePtrgtItemKey item is in the root of some subtree DeleteNodeItemTreePtr delete the item Success true else if SearchKey lt TreePtrgtItemKey else search the left subtree DeleteItemTreePtrgtLChildPtr SearchKey Success search the right subtree DeleteItemTreePtrgtRChildPtr SearchKey Success void bstClassDeleteNodeItemptrTypeamp NodePtr Algorithm note There are four cases to consider l The root is a leaf 2 The root has no left child 3 The root has no right child 4 The root has two children prtType DelPtr treeItemType Replacementltem test for a leaf if NodePtrgtLChildPt NULL ampamp NodePtrgtRChildPtr NULL delete NodePtr NodePtr NULL test for no left child else if NodePtrgtLChildPtr NULL DelPtr NodePtr NodePtr NodePtrgtRChildPtr DelPtrgtRChildPtr NULL delete DelPtr test for no right child else if NodePtrgtRChildPt NULL DelPtr NodePtr NodePtr NodePtrgtLChildPtr DelPtrgtLChildPtr NULL delete DelPtr there are two children retrieve and delete the inorder successor else ProcessLeftmostNodePtrgtRChildPtr Replacementltem NodePtrgtItem Replacementltem CHAPTER 6 STACKS Defn A stack is a data structure in which the item last in is the item rst out LIFO Examples 0 dishes on a shelf 0 newspapers on a rack o storing context switching information in memory We want to design an ADT for Stacks The data structure must provide the following attributes 0 length 0 top 0 contents The following operations must be provided in the ADT 0 Push add to the top of the stack 0 Pop remove from the top of the stack Top get the information stored in the top item of the stack 0 Empty check to see if the stack is empty 0 Initialize create an empty stack We will look at two possible implementations of Stack ADTs 0 Simple array 0 Simple linked list Simple Array Implementation of Stacks Carrano Helman and Veroff pp 262265 const int MAXSTACK maximum size of stack typedef desired type of stack item stackItemType class stackClass public stackClass stackClassconst stackClassamp S bool StackIsEmpty const void PushstackItemType NewItem boolamp Success void Popboolamp Success void PopstackItemTypeamp StackTop boolamp Success void GetStackTopstackItemTypeamp StackTop boolamp Success const private stackItemType ItemsMAXSTACK int Top Using the Stack ADT include ltiostreamhgt include quotStackAhquot int main stackItemType AnItem stackClass S boolean Success cin gtgt AnItem SPushAnItem Success Potential Implementation Problems 0 Storing gt MAXSTACK items in the stack 0 accessing an empty stack C Code 0 The top of the stack will move Top is initially 1 void stackClassPushstackItemType NewItem boolamp Success Success boolTop lt MAXSTACK 1 if Success Top ItemsTop NewItem void stackClassGetStackTopstackItemTypeamp StackTop boolamp Success const Success boolStackIsEmpty if Success StackTop ItemsTop void stackClassPopboolamp Success Success boolStackIsEmpty if Success Top void stackClassPopstackItemTypeamp StackTop boolamp Success Success boolStackIsEmpty if Success StackTop ItemsTop Top Linked List Implementation of Stacks Problem In array implementations the maximum stack size is determined at compile time Solution Use a linked structure to store stack elements dynamically For our ADT o The stack is a simple linked list with no dummy node and no head and tail pointers o The top of stack is the front of the list Speci cation for the Linked Stack typedef desired type of stack item stackItemType struct stackNode forward reference typedef stackNode ptrType pointer to node struct stackNode stackItemType Item ptrType Next class stackClass public stackClass stackClassconst stackClassamp S stackClass bool StackIsEmpty const void PushstackItemType NewItem boolamp Success void Popboolamp Success void PopstackItemTypeamp StackTop boolamp Success void GetStackTopstackItemTypeamp StackTop boolamp Success const private ptrType Tothr points to top of stack C Code 0 A stack initializes to null void void void void stackClassPushstackItemType NeWItem boolamp Success ptrType Nethr new stackNode Success boolNethr NULL if Success Nethr gtItem NeWItem Nethr gtNext Tothr Tothr Nethr stackClassGetStackTopstackItemTypeamp StackTop boolamp Success const Success boolStackIsEmpty if Success StackTop Tothr gtItem stackClassPopboolamp Success Success boolStackIsEmpty if Success ptrType Temp Tothr Tothr Tothr gtNext Temp gtNext NULL safeguard delete Temp stackClassPopstackItemTypeamp StackTop boolamp Success Success if boolStackIsEmpty Success StackTop Tothr gtItem ptrType Temp Tothr Tothr Tothr gtNext Temp gtNext NULL safeguard delete Temp Comparison of ADT Implementation for Stacks Programming Memory Execution Time Other Dif culty J 39 Simple Array Simple Linked List CECS 274 Programming and Problem Solving II Commonly used UNIX commands and their sample use man make who who am I nger s lam cal 09 1972 date passwd mkdir lab5 ls cp lab4card h lab5 cd lab5 display online manual of the make command try to find manuals for other commands show who39s logged in show who I am display shortform information on all users named lam try other names display a calendar of the month 09 in year 1972 try other and no monthsyears display the current date and time request to change password create a directory named lab5 display current directory copy le named cardh in directory lab4 into lab5 try copy other les change directory to lab5 cp cardh tempcopy le named cardh to temp Vi temp cat temp cat gt prolog more combined mv combined comb ls l chmod gw comb mv comb pwd rm i cd rmdir lab5 rm comb history make telnet linuXXXX hostname Shui Lam edit le temp using vi display content of le named temp request to have lines typed after this command funneled into le named prolog use controld to end typing cat prolog temp gt combined concatenate les prolog and temp into a new le named combined Warning NEVER use command of the form catf gtf1 Content off will be lost display content of combined one screenful at a time rename le combined to comb MAKE SURE you don t have an old le with this name display current directory in long form change access mode of comb to add quotwritequot permission to group user move le named comb into parent directory print working directory MAKE SURE you are in the lab5 subdirectory Go there if not remove all les in this directory but check with me before removing return to parent directory remove directory named lab5 remove le named comb which should have been moved here display a list of commands you have executed to now this history allows you to rerun commands as follows repeat the command I just did lc repeat the most recent command that begins with c 1 3 repeat the command thatl did 3 commands before this wd repeat the most recent command that contains pattern quotwdquot request to update dependent les speci ed in the file named makefile telnet to another rm machine XX represents a 3digit number on the linuX machines in ECS412 display hostname of machine I am using CECS 274 Programming and Problem Solving 11 vi SCREEN EDITOR Vileename to enter editor with existing or new le named lename To get out use one of the following save buffer and exit q quit without saving buffer w write buifer over le wq write buffer over le and exit Cursor control go to line k text text forward or backward search for the given text Arrow keys to move cursor AF AB to scroll the screen forward and backward respectively To insert text ESC to end insert i to insert text at the current cursor position 0 or Oto open up a blank line below or above respectively the current line for the insertion I A to insert text at the beginning or the end respectively of the current line To delete text nx nX delete next or previous n characters respectively delete 1 character if n is omitted delete to end of line J join next line ndw ndb delete next or previous n words respectively ndd delete n lines starting from the current line delete 1 line if n is omitted dG delete the current line through end of le z39jd delete lines itojj must be 2 i Use quotquot to indicate the line at the end ofthe le quotquot for the current line and quotkquot for current line minus k d delete the current character through end of line d delete the current character through end of sentence dtchar delete the current character up to char in current line ckw change away k words forward Cut and paste z39jmk move lines i through j to after line k kdd cut k lines from the currrent line then move cursor to a new position then type p or P paste the k lines cut above to after or before the line of the new cursor position Shui Lam