New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Dr. Garrison Mohr


Dr. Garrison Mohr
GPA 3.87

Rose Lowe

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Rose Lowe
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 51 page Class Notes was uploaded by Dr. Garrison Mohr on Saturday September 26, 2015. The Class Notes belongs to CP SC 102 at Clemson University taught by Rose Lowe in Fall. Since its upload, it has received 55 views. For similar materials see /class/214259/cp-sc-102-clemson-university in ComputerScienence at Clemson University.

Similar to CP SC 102 at Clemson




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: 09/26/15
A Second Course in Java Brief Notes for Computer Science 102 Wayne Goddard Clemson University 2006 CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 1 Java Review 11 Primitive Data Types and Operators In Java the primitive data types include int7 double7 boolean7 char An int variable stores a 32 bit integer which can be positive or negative This can be initialized at declaration int count 0 There are operators for much arithmetic The operator is the mod operator it calculates the remainder for example7 113 has the value 2 The increment operator and decrement operator change the value of the variable they are applied to For example7 System out printlnx prints out the value of x and THEN increments it 12 Conditionals and Loops The standard conditional is an if construction or an ifelse construction if condition done if true if condition done if true else done if f alse The standard loops are the forloop and the whileloop forinitialization condition post body action statements to be repeated initialization whilecondition statements to be repeated post body action Nested loops are when there is one loop inside another 13 Arrays An array has a xed length and the length is a eld instance variable For example7 int hourCount new int 24 produces an array of integers with indices from 0 up to 23 Arrays are automatically initialized eg ints to 0 Example determine the maximum entry in the above array int maXSoFar hourCount O for int X1 xlthourCountlength X if hourCount x gtmaXSoFar maXSoFar hourCount X But what happens if hourCount has length 0 An array can be initialized with a braces construct double data 1414 31415 100 42 This can be printed out with the for each construct for double D data SystemoutprintfquotThe next value is dnquot D 14 Booleans A boolean variable stores either true or false It is good practice to make its name a verb phrase eg isl ositive77 or hasMoreEntries It should NOT be tested against true or false while hasMoreEntries printDutNeXt if isPositive ChangeSign Boolean expressions use ampamp for and7 for 017 for not Note that ampamp and are shortcircuit operators these enable one to check for conditions which might cause exceptions eg an array index out of range7 or division by zero if divisor0 ampamp valdivisorlt50 15 Strings and Characters A String is an immutable object with lengtho a method The operator denotes con catenation Other available methods include substring7 char t7 trim7 lowerCase Always look at the help page for the String class A char variable stores a single character Conversion from char to int is automatic Character arithmetic is available The following converts a letter to its position in the alphabet char lowerCaseLetter int pos lowerCaseLetter a 1 16 Program Structure If a Java class is to be run as a program7 then it must have a main method declared a speci c way public static void mainString args In a method7 a return statement causes execution to halt7 and to return a value as required Exercise Write a program that will print out all two digit numbers which equal twice the sum of the squares of their digits Sample Program ArrayExamplejava a silly few array methods for c5102 wdg 2006 public class ArrayExample public static void mainString args String test quotaaaaquot quotabbaquot quoteiEloquot forint XO xlttestlength X Systemoutprinttestx System outprint isAllDifftestX quot Differentquot quot Has repeatquot System outprint Lower vowels are quot printLowerVowelstestX prints out the lowercase vowels in the string in order post vowels are printed on standard output with line feed public static void printLowerVowelsString S forint XO XltSlength X char tempScharAtX iftemp a ll temp e ll temp i ll temp o ll temp u Systemoutprinttemp Systemoutprintln determines whether there are any duplicate characters in a string parameter String S input returns true if every two chars are different else false public static boolean isAllDiffString S char A StoCharArray boolean isDkaytrue forint XO xltA length X forint yx1 yltA length y if AXAy isDkayfalse return isDkay CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 2 Basic Objects 21 Terminology Classes de ne types Objects are concrete instances of class and there may be multiple instances of a class Objects store data in elds or instance variables7 initialize this data with constructors7 and manipulate this data with methods The current value of the elds is the state of the object A variable of class type stores either a reference to an object or the value null 22 Constructors and Methods A constructor sets up an object at creation For example Prof wayne new ProfO A constructor can have arguments that are used to initialize the instance variables Prof waynenew Profquotgoddardquot A constructor must NOT have a type public Class Prof String name ProfString n name n When a class is created7 instance variables are initialized to default values 0 for int7 null for objects etc Nevertheless7 you should explicitly set primitive variables A method has a header with formal parameters7 and a body lts signature is the types of its parameters and its own type The return type void means that the method returns nothing A method is called with the notation For example object methodO Most objects have accessor methods these allow the user to get data from the object Mutator methods allow the user to set data in the object A method should normally check its arguments lt noti es the caller of a problem by using an exception or a special return value The programmer should try to avoid exceptions consider error recovery and avoidance 23 Access Modi ers The elds of an object are accessible by all the methods of that object A variable has a scope where it is accessible from and a lifetime when it exists The variables de ned in a method are called local variables and are accessible only within the method and exist only while the method is being executed an exception is static variables whose lifetime is the programs execution they are always available A method or eld can be made private public or protected private means it is accessible by no other class and public that it is accessible by all other classes We will discuss protected later Note that within the code for the class one can access all elds of all objects of that type even if they are private For example if one created one7s own version of an integer one could write public class Mylnteger private int val public boolean isGreaterThanMyInteger other return thisvalgtotherval l The this refers to the current object in this case it could be omitted return valgtotherval Constants are usually uppercase for example public final static int MAXSIZE100 There are also static methods Consider for example a Coord class that stores a point A static method might be used to compute the distance between two points public static double distance Coord p1 Coord p2 It is then called as follows Coord X new Coord0000 Coord Y new Coord3040 Systemoutprintln CoorddistanceXY 24 Objects as Return Values and Parameters An object even an array can be returned from a method but only one An object can also be a parameter to a method Note that the method receives a reference to an object this is called pass by reference This means that changes to the object so referenced ARE re ected outside the class On the other hand changing a primitive data type parameter does NOT affect the value outside the class void Clearint Xint A XO forint iOiltAlengthi Ai0 is called from int y 42 intE B 12345 ClearyB will cause all the values of B to be zero7 but will not change y 25 Objects for Numbers For every primitive data type there is a corresponding object called its wrapper So there are Integer7 Double and Character classes7 etc These have several methods in cluding o constructors which take the corresponding base type 0 accessor methods such as double doubIeVa which return the base type and 0 static utilities such as ntegerparsentString str that translate a String into the base type Most of the time Java will automatically convert between a primitive data type and its wrapper 26 Exceptions Java uses Exceptions to signal problems with execution7 such as an array index out of range or running out of memory A RuntimeException is called an unchecked ea cept39ion since it does not require compiler check Other Exceptions are checked and require throws statements andor try catch construction7 discussed later Example usage if indexlt0 throw new RuntimeExceptionquotBad indexquot Sample Program Should be re implemented to use enums Cardjava a silly class for storing a playing card wdg 2006 public class Card public final static String suitChars quotSHDCquot public final static String denomChars quotA23456789TJQKquot public final static int numSuits suitCharslength public final static int numDenoms denomCharslength private int suit stores the suit OS 1H 2D 3C private int denom stores the denom OA 12 12K constructor public CardString name ifnamelength2 throw new RuntimeExceptionquotInvalid card quotname setSuitnamecharAtO setDenomnamecharAt1 mutator methods private void setSuitchar suitChar suit suitCharsindeXDfsuitChar ifsuitltO no match throw new RuntimeExceptionquotInvalid suit quotsuitChar private void setDenomchar denomChar denom denomCharsindeXDfdenomChar ifdenomltO no match throw new RuntimeExceptionquotInvalid denom quotdenomChar accessor methods public int getSuit return suit public int getDenom return denom overrides toString method of Object public String toString return suitCharscharAtsuitquotquotdenomCharscharAtdenom an example method to use it input array of Cards returns whether all the Cards have the same suit public static boolean isFlush Card hand for int c1 clthandlength c if handcgetSuit handOgetSuit return false failing which return true CardDriverjava simple class to exercise Card class wdg 2004 public class CardDriver public static void mainString args Card A A new CardquotSAquot System outprintlnquotA is quot A Card hand hand new Card3 handO new CardquotSKquot hand1 new CardquotSSquot hand2 A ifCardisFlushhand SystemoutprintlnquotYes it s a flushquot else SystemerrprintlnquotDDDPSquot hand0 new CardquotD7quot ifCardisFlushhand SystemoutprintlnquotNo longer a flushquot else SystemerrprintlnquotDDDPSquot A new CardquotC4quot Systemoutprintlnquothand2 is still quot hand2 next should cause exception A new CardquotsillyMequot CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 3 Program Development 31 OOP Design Object oriented programming rests on three principles 0 Abstraction ignore the details 0 Modularization break into pieces 0 Information hiding separate the implementation and the function We strive for responsibilitydriven design each class should be responsible for its own data We strive for loose coupling each class is largely independent and communicates with other classes via a small well de ned interface We strive for cohesion each class performs one and only one task for readability reuse UML is an extensive language for modeling programs especially those for an object oriented programming language It is a system of diagrams designed to capture objects interaction between objects and organization of objects and then some 32 Literate Programming Good programming means extensive comments and documentation At the very least erplain the function of each instance variable and for each method erplain its purpose parameters returns where applicable You should also strive for a consistent layout and for expressive variable names JauaDoc is a program that will automatically extractgenerate an HTML help page from code that is properly commented In particular it produces a help le that for a class lists the methods constructors and public elds and for each method explains what it does together with pre conditions post conditions the meaning of the parameters exceptions that may be thrown and other things 33 Testing One needs to test extensively Look at the boundary values make sure it handles the smallest or largest value the program must work for and suitably rejects the value just out of range Add watches or debug statements so that you know what is happening at all times Especially look at the empty case or the 0 input CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 4 More Java 41 TOString The class Object7which every other class extends7has several standard methods One is the toString method this is automatically called to convert an object to a string You should override this that is replace with code suitable for your class since the standard method prints out just the type and address in memory A class String Builder is available for use when building up a string For example public String toString StringBuilder result new StringBuilderO forString S list resultappend Squot quot return result toString 42 Assignment and Equality Testing If A and B are primitive data types then AB sets A to the value of B changing B will have no impact on A If A and B are objects then AB sets A to refer to the same object that B references until either A or B is re assigned they will point to the same object If you want to make a separate copy you need to use a suitable version of the clone method discussed later The test AB for objects only compares whether they reference the SAME object in memory It is good practice to override the equas method if one will need to test two objects of ones class for equality For example producing an equals method for the Coord class mentioned earlier public boolean equalsDbjeCt other ifother instanceof Coord Coord otherPoint Coord other return thisxotherPointX ampamp thisyotherPointy else return false This uses a cast which we now discuss 43 Casting Recall that the type of a variable speci es what it can reference it can reference any object that is of that type or a subtype ofthat type It is an informational message to the compiler On the other hand an actual object has a xed type The type of the object that a variable references is sometimes called the runtime type of that variable A cast tells the compiler that it may assume that the object has the type that the cast says If at run time the object doesnt have the claimed type you will get a CIassCastException This occurs in the above code where we say Coord otherPoint Coord other Casting is also used for primitive data types but this is more like a conversion For example Systemoutprint Char A 2 prints out C without the char cast it prints out 67 the code for C 44 More on Exceptions An exception is explicitly thrown using a throw statement All exceptions that are thrown must be eventually caught A method might not handle an exception but instead propagate it for another method to handle A try clause is used to delimit a block of code in which a method call or operation might cause an exception If an exception occurs within a try block then Java aborts the try block executes the corresponding catch block and then continues with the statements that follow the catch block If there is no exception the catch block is ignored You can de ne your own exception classes public Class SillyException extends RuntimeException SillyExceptionString w super w 45 Commandline Arguments It is common to get the user to specify data on the command line This is available to the programmer via the args array that is the parameter to the main method public static void main String args if argslength1 throw new RuntimeExceptionquotUsage java MyProg limitquot process IntegerparseIntargs 0 46 Packages and Scanner Java has an extensive library for doing many tasks The library is organized as a collection of packages To use methodsclasses from a package you need the import command for example7 the following provides access to all classes in javauti import javautil The Scanner is a simpli ed reader class which accesses the input or a le7 and does limited conversion for the user almost without Exceptions import java util Scanner Scanner inn new ScannerSystemin SystemoutprintquotEnter gradegt quot int grade innneXtInt 47 File Input To read data from a le in Java is relatively complex as compared to printing to the standard output The package javaio has many classes7 and the input and le methods tend to throw checked exceptions7 so that the user is forced to deal with exception handling This is somewhat simpli ed by the Scanner class import javaio import javautil Scanner in null try in new Scanner new FileReaderargs 0 catchFileNotFoundException e SystemerrprintlnquotCould not open filequotargs 0 return CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 5 Yet More Java We consider some important Java features interfaces7 inheritance and generics 51 Interfaces An interface speci es the methods which a class should contain A class can then implement an interface actually it can implement more than one In doing so7 it must implement every method in the interface it can have more An interface cannot specify the behavior of the constructor Note that an interface is a valid type for a variable Example the interface interface Number void incrementO void addNumber other ETC the implementation class Mylnteger implements Number private int X public void incrementx ETC the calling program but then one can only execute Number7s methods on ticket Number ticket new MylntegerO ticket increment There are also abstract classes where some of the methods are implemented and some are not 52 Inheritance In Java you can make one class an extension of another This is called inheritance The classes form an isa hierarchy The advantage of inheritance is that it avoids code duplication7 promotes code reuse7 and improves maintenance and extendibility ln fact7 every class automatically extends Object To create a class Rectangle which extends a class Shape7 one starts with Class Rectangle extends Shape The class Rectangle then automatically has all the methods of class Shape and you can add some of your own The default constructor for Rectangle is automatically called at the start of the constructor for Shape The methods and the instance variables of the superclass can be accessed if not declared as private This can be done with the pre x super The methods and instance variables of a class may be declared as protected to allow direct access only to extensions Overriding is providing a method with the same signature as the superclass but different body This method takes precedence on the subclass object Substitutionsubtyping A variable may reference objects of its declared type or any subtype of its declared type subtype objects may be used whenever supertype objects are expected There are times an objects may need to be cast back to original type Note that the actual type of an object is forever xed Suppose class Rectangle extends class Shape Then we could do the following as signments Shape X Rectangle Y Y new Rectangle X Y Okay X new Rectangle okay Y RectangleX cast needed 53 Using Generics Java collections used to handle all elements as Objects This avoided writing a new version of the collection for each type of element lnteger String etc However since we can add anything to a collection when we extracted things we had to promise the compiler by using a cast that we knew what we were doing Generics let us tell the compiler what kind of thing we want to store in a particular instance of a collection It can then check that we are adding the right thing and give us a compile time warning if we are not If we want an ArrayList that stores Strings we say ArrayListltStringgt L new ArrayListltStringgt Example Code NewCardjava extending the silly Class for storing a playing card 17 which had private instance variables wdg 2005 public class NewCard extends Card calls constructor of super class NewCardString name supername overrides equals method of Object public boolean equalsDbject other ifother instanceof Card return false else Card otherCard Cardother boolean sameSuit thisgetSuitotherCardgetSuit thisgetDenomotherCardgetDenom return sameSuit ampamp sameDenom boolean sameDenom CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 6 Collections 61 Basic Collections There are three basic collections 1 The basic collection is often called a bag It stores objects with no ordering of the objects and no restrictions on them 2 Another unstructured collection is a set where repeated objects are not permit ted it holds at most one copy of each item A set is often from a prede ned universe 00 A collection where there is an ordering is often called a list Speci c examples include an array a vector and a sequence These have the same idea but vary as to the methods they provide and their ef ciency 62 The Bag ADT An ADT or abstract data type de nes a way of storing data it speci es only how the ADT can be used and says nothing about the implementation of the structure An ADT is more abstract than a Java speci cation The Bag ADT has 0 accessors methods such as size countOccurrence possibly an iterator which steps through all the elements 0 modi er methods such as add remove and addAII 0 also a union method which combines two bags to produce a third 63 The Array Implementation A common implementation of a collection is a partially lled array This is often expanded every time it needs to be but rarely shrunk It has a pointercounter which keeps track of where the real data ends 0 l 2 3 4 5 6 Al Bart Carl Don NULL NULL NULL size4 64 The Java Collection The javauti package provides some ready made collections The root interface is Col lection and Bags should implement this directly Two specialization interfaces are List which speci es a listsequence and Set which prohibits duplicates These have so called optional77 operations That is the user has to provide code for the method but it might just throw an UnsupportedOperationException 65 Issues for Implementing Data Structures There are many decisions to make when implementing an ADT Often more than one way will work 1 General or speci c data types Suppose you want to store ints Well you can choose to write a speci c structure in terms of ints or you can choose to imple ment a structure that stores Objects and then wrap this with a structure that converts ints to Integers E0 Emeeptz39on handling The methods should check for anomalous situations For example consider adding a value in an invalid position You might choose to throw an Exception even create your own Exception class or you might simply not perform the addition either printing an error message or returning a fail value 9 Overflowng Java You can run out of memory or you can add too many things that can be addressed by an int You might choose to ignore the running out of memory since that would trigger an Exception anyway or handle it With the index going past 231 probably should deal with it 66 Wrappers A wrapper class is a class which simply contains another class but makes for eas ierdifferent user access For example Integer is the wrapper class for int it is an object whereas int is a primitive data type Wrappers shield the user from details or from dealing with a more general situation Suppose we have a generic collection MyBag that stores objects but we want a collection that stores only nonnegative integers The class MyPosIntBag has as its only instance variable something of type MyBag Any method designed to add something to the collection simply wraps the int and adds it to the inner collection Any method designed to retrieve something from the collection simply retrieves the object and unwraps it Often the wrapper has the same methods as the underlying object 20 67 Sample Program MyPoslntBag wdg 2006 stores nonnegative integers just to show the use of wrappers public class MyPoslntBag MyCollectionltlntegergt C constructor MyPoslntBag C new MyCollectionltlntegergt a typical add method void addint elem if elemltO throw new lllegalArgumentException Integer wrapped new lntegerelem Caddwrapped could use autobox a typical retrieve method int retrieveUne Integer retrieved CretrieveDne return retrievedintValue could use autounbox public static void mainString args MyPoslntBag B new MyPoslntBag forint i0 ilt10 i Baddi forint i0 ilt10 i Systemoutprintln BretrieveUne 21 MyCollection wdg 2006 just for show stores a collection using partially filled array public class MyCollectionltEgt E arr int size real data is in positions 0 to size 1 constructor MyCollection arr Enew Ubject10 causes compiler complaint a typical add method void addE item arrsize item size a typical retrieve method E retrieveUne size return arrsize 22 CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 7 Order Notation The order of a task measures how the time required for a task grows as the input grows In this notation the variable n always stands for the size of the input We write that a task takes time Ofn if it is at most proportional to This is said O of fn77 or order fn The most common case is that the time taken is proportional to the input This is written On also called linear time For example printing out the contents of an array takes time The second most common case is that the time taken does not depend at all on the size of the input This is called constant time and is written 01 For example accessing the rst entry in the array or the last takes time 01 Sometimes the length of the task might vary depending on the actual data etc The big O notation only considers the worst case For example searching through an array for a particular value is considered lf you7re lucky there will be a match on the rst element but if the value is not there you will have to look at the entire array A useful rule to note is that if you have a loop then the overall time is usually given by the product rule the worst case number of times the loop body can be performed times the worst case time of the loop body CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 8 Linked Lists 81 Links References and Pointers The linked list is not an ADT in its own right rather it is a way of implementing many data structures It is designed to replace an array A linked list is a sequence of nodes each with a lmk t0 the new node These links are also called pointers Both metaphors work They are links because they go from one node to the next7 and because if the link is broken the rest of the list is lost They are called pointers because this link is usually one directional The rst node is called the head node The last node is called the tail node The rst node has to be pointed to by some external holder often the tail node is too l l l Head Node Tail Node The Java way of having this is Class Node ltdatagt Node link where ltdatagt means any type of data7 or multiple types The class usingcreating the linked list then has the declaration Node head 82 Insertion and Traversal For traversing a list7 the idea is to initialize a pointer to the rst node pointed to by head Then repeatedly advance to the next node null indicates you7ve reached the end Such a pointerreference is called a cursor There is a standard construct for a for loop to traverse the linked list for cursorhead cursornull cursorcursorlink ltdo something with object referenced by cursorgt For insertion7 there are two separate cases to consider 1 addition at the root7 and 2 addition elsewhere For addition at the root7 one creates a new node7 changes its pointer to where head currently points7 and then gets head to point to it head g In Java head new Node ltnewDatagt head assuming a suitable constructor This also works if the list is empty To insert elsewhere7 one need a reference to the node BEFORE where one wants to insert One creates a new node7 changes its pointer to where the node before currently points7 and then gets the node before to point to it CUI SOI In Java assuming cursor references node before cursorlink new Node ltnewDatagt cursorlink Traps for Linked Lists 1 You MUST think of and test the exceptional cases The empty list7 the beginning of the list7 the end of the list 2 Draw a diagram you have to get the picture right7 and you have to get the order right 25 83 Removal The easiest case is removal of the rst node For this one simply advances the head to point to the next node The rst node is no longer referenced and Java garbage collection destroys it head headlink In general to remove a node that is elsewhere in the list one needs a reference to the node BEFORE the node one wants to remove Then one needs only to update the link of the node before to skip that node that is point to the node after the one wants to delete CUI SOI If the node before is referenced by cursor then cursorink refers to the node to be deleted and cursorinkink refers to the node after Hence the Java is cursor link cursor link link The problem is to organize cursor to be in the right place In theory one would like to traverse the list nd the node to be deleted and then back up one but that7s not possible lnstead one has to look one node ahead And then beware null pointers 84 And Beyond Arrays are better at mndom access they can provide an element given a position in constant time Linked lists are better at additionsremovals at the cursor done in constant time Resizing arrays can be inef cient but is on average77 constant time Doublylinked lists have pointer both forward and backward These are useful if need to traverse the list in both directions or to addremove at both ends Dummy headertail nodes are sometimes used These allow some of the special cases eg empty list to be treated the same as a typical case While searching takes a bit more care both removal and addition are simpli ed 85 Direct Access in Nodes Long before objects languages such as C and Pascal allowed one to group data called structs or records However only with objects can one group data with its methods 26 Sorne languages7 such as C7 allow structsrecords to co eXist with objects but in Java everything E an object In principle7 instance variables should be private However7 some classes are just helpers for other classes For exarnple7 a linked list class uses a node class7 and it is the linked list that the user sees So7 we grant the linked list class direct access to the elds of the node class This is purely for readability one can write linked lists without direct access to the instance variables Exercise Develop code for making a copy of a list Sample Code StringNodejava a primitive version of node for strings wdg 2006 public class StringNode String data stores data StringNode next references constructors StringNode StringNodeString datStringNode nXt datadat neXtnXt toString public String toString return data StringLinkedBagjava uses a linked list to implement a primitive Bag wdg 2006 27 public class StringLinkedBag StringNode head int size no argument constructor StringLinkedBag headnull sizeO add creates new node and adds at beginning of list void addString newElement head new StringNode newElement head size tries to delete one node with that value returns true if target found and false otherwise boolean removeString target first special case list is empty ifheadnull return false second special case first item is deleted ifheaddataequalstarget headheadneXt size return true so the list is nonempty and newElement does not match first StringNode cursorhead whilecursorneXtnull ampamp cursorneXtdataequalstarget cursorcursornext ifcursorneXtnull return false not found else cursorneXt cursorneXtneXt size return true 28 dump prints out list void dump ifheadnull SystemoutprintlnquotgtgtgtEmptyquot else forStringNode cursorhead cursorlnull cursorcursornext Systemoutprintlncursordata System out printlnsizequot quotgt 29 CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 9 Stacks A linear data structure is one which is ordered There are two special types with restricted access a stack and a queue 91 Stacks Basics A stack is a data structure of ordered items such that items can be inserted and removed only at one end called the top It is also called a LIFO structure last in7 rst out The standard and usually only modi cation operations are 0 push add the element to the top of the stack 0 pop remove the top element from the stack and return it If the stack is empty and one tries to remove an element7 this is called under ow Another common operation is called peek this returns a reference to the top element on the stack leaving the stack unchanged A simple stack algorithm could be used to reverse a word push all the characters on the stack7 then pop from the stack until its empty 5 i thlS 7gtslht 92 Implementation A stack is commonly implemented using either an array or a linked list In the latter case7 the head points to the top of the stack so additionremoval pushpop occurs at the head of the linked list 93 Sample Code ArrayStack ArrayStack java minimal array implementation of Stack no test for overflow wdg 2006 public class ArrayStackltEgt private E arr stores data private int size number of elements in stack note that valid data always in O size l constructor arbitrarily sets upper limit public ArrayStack size O arr Enew Dbject100 pushes object onto stack post reference to item placed at right end of array public void pushE item arrsize item returns whether stack is empty or not public boolean isEmpty return sizeO pops top element from stack returns previous top element post the top element is removed throws EmptyStackException if stack is empty public E pop ifisEmpty throw new javautilEmptyStackException return arr size 31 returns reference to data on top of stack or null if stack is empty public E peek ifisEmpty return null else return arrsize 1 returns String representation public String toString ifisEmpty return quot quot StringBuffer temp new StringBuffer forint XO xltsize X tempappend arrXquot quot return temptoString 32 CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 10 Stack Applications 101 Balanced Parentheses A common application of stacks is the parsing and evaluation of arithmetic expressions lndeed7 compilers use a stack in parsing checking the syntax of programs Consider just the problem of checking the bracketsparentheses in an expression Say 345 784 The brackets here are okay for each left bracket there is a matching right bracket Actually7 they match in a speci c way two pairs of matched brackets must either nest or be disjoint You can have or but not We can use a stack to store the unmatched brackets The algorithm is as follows Scan the string from Left to right and for each char 1 If a Left bracket push onto stack 2 If a right bracket pop bracket from stack if not match or stack empty then fail At end of string if stack empty and always matched then accept For example7 suppose the input is Then the stack goes MENU and then a bracket mismatch occurs 102 Evaluating Arithmetic Expressions Consider the problem of evaluating the expression 38 584 We assume for this that the brackets are compulsory for each operation there is a surrounding bracket If we do the evaluation by hand7 we could repeatedly evaluate the rst closing bracket and substitute 38584 11 584 684 62 12 With two stacks7 we can evaluate each subexpression when we reach the closing bracket Algorithm assuming brackets are correct is as follows Scan the string from left to right and for each char 1 If a left bracket do nothing 2 If a number push onto numberStack 3 If an operator push onto operatorStack 4 If a right bracket do an evaluation a pop from the operatorStack b pop two numbers from the numberStack c perform the operation on these numbers in the right order d push the result back on the numberStack At end of string the single value on the numberStack is the answer The above example 38 584 at the right brackets 8 3 m a 11 U TO BE READ 584 nums OPS nums OPS 5 11 a 6 TO BE READ 84 nums OPS nums OPS 4 8 2 6 a 6 TO BE READ nums OPS nums OPS 2 6 a 12 nums OPS nums OPS 34 CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 11 Queues A queue is a linear data structure that allows objects to be added only to the rear of the queue and removed only from the front of the queue Queues are FIFO structures First in First out They are used in operating systems to schedule access to resources such as a printer 1 11 Queue Methods The two standard modi cation methods are 0 void enqueueObject ob insert the object to the rear of the queue 0 Object dequeue delete and return the object at the front of the queue some times called the rst item A simple task with a queue is echoing the input in the order it came repeatedly insert into the queue and then repeatedly dequeue 112 Queue Implementation as Array The natural approach to implementing a queue is of course an array This suffers from the problem that as items are enqueued and dequeued we reach the end of the array but are not using much of the start of the array The solution is to allow wrap around after lling the array you start lling it from the front again assuming these positions have been vacated Of course if there really are too many items in the queue then this approach will also fail This is sometimes called a circular array You maintain two markers for the two ends ofthe queue The simplest is to maintain instance variables 0 double data stores the data 0 int size records the number of elements currently in the queue and int capacity the length of the array 0 int front and int rear are such that if reargfront then the queue is in positions datafront datarear otherwise it is in datafront datacapacity l dataO datarear For example the enqueue method is void enqueuedouble elem if size capacity throw new QueuererflowException rear rear1 Z capacity datarear elem size As an exercise7 provide the dequeue method 113 Queue Implementation as Linked List A conceptually simpler implementation is a linked list Since we need to add at one end and remove at the other7 we maintain two pointers one to the front and one to the rear The front will correspond to the head in a normal linked list doing it the other way round doesn7t work why 36 CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 12 Queue Applications 121 Simulation There are two very standard uses of queues in programming The rst is in implement ing certain searching algorithms The second is in doing a simulation of a scenario that changes over time So we examine the CarWash simulation taken from Main The idea we want to simulate a CarWash to gain some statistics on how service times etc are affected by changes in customer numbers etc In particular there is a single Washer and a single Line to wait in We are interested in how long on average it takes to serve a customer We assume the customers arrive at random intervals but at a known rate We assume the washer takes a xed time So we create an arti cial queue of customers We dont care about all the details of these simulated customers just their arrival time is enough for currentTime running from 0 up to end of simulation 1 toss coin to see if new customer arrives at currentTime if so enqueue customer 2 if washer timer expired then set washer to idle 3 if washer idle and queue nonempty then dequeue nemt customer set washer to busy and set timer update statistics It is important to note a key approach to such simulations wherever possible you look ahead Thus when we move the Customer to the Washer we immediately calculate what time the Washer will nish and then update the statistics In this case it actually allows us to discard the Customer the only pertinent information is that the Washer is busy CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 13 Recursion Often in solving a problem one breaks up the problem into subtasks Recursion can be used if one of the subtasks is a simpler version of the original problem 131 An Example Suppose we are trying to sort a list of numbers We could rst determine the minimum element and what remains to be done is to sort the remaining numbers So the Java code might look something like this void sortCollection C min CgetMinimum Systemout print min Cremove min sort C Every recursive method needs a stopping case otherwise we have an in nite loop or an error In this case7 we have a problem when C is empty So one always checks to see if the problem is simple enough to solve directly void sortCollection C if C isEmpty return as before Example Printing out a decimal number The idea is to extract one digit and then recursively print out the rest Its hard to get the most signi cant digit7 but one can obtain the least signi cant digit the ones column use num 10 And then numlO is the rest77 of the number void print int n if ngto print nlO Systemoutprint n olO 132 Tracing Code It is important to be able to trace recursive calls step through what is happening in the execution Consider the following code void g int n if nO return gn 1 Systemout print1nn It is not hard to see that7 for example7 g3 prints out the numbers from 3 down to 1 But7 you have to be a bit more careful The recursive call occurs before the value 3 is printed out This means that the output is from smallest to biggest 1 2 3 Here is some more code to trace void f int n Systemout print n if ngt1 f n l if ngt2 f n 2 If you call the method f47 it prints out 4 and then calls f3 and f2 in succession The call to f3 calls both f2 and f17 and so on One can draw a recursion tree this looks like a family tree except that the children are the recursive calls f4 3 2 l 2 1 1 1 Then one can work out that f1 prints 17 that f2 prints 21 and f3 prints 3211 What does f4 print out 39 Exercise Give recursive Java code so that brackets5 prints out 133 Methods that Return Values Sorne recursive methods return values For example7 the sequence of Fibonacci numbers l7 17 27 37 57 87 137 217 347 is de ned as follows the rst two numbers are l and 17 and then each next number is the sum of the two previous nurnbers There is obvious recursive code for the Fibonacci nurnbers int fibint n if nlt2 return 1 else return fibn 1 fibn 2 WARNING Recursion is often easy to write once you get used to itl But occa sionally it is very inef cient For example7 the code for fib above is terrible Try to calculate fib30 40 CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 14 Recursion Applications 141 The Steps problem THE STEPS PROBLEM One can use recursion to solve the Steps problem In this problem7 one can take steps of speci ed lengths and has to travel a certain distance exactly for example7 a cashier making change for a speci c amount using coins of various denominations The Javapseudocode is as follows boolean canStepint required if required0 return true for each allowed length if lengthltrequired ampamp canSteprequired length return true failing which return false The recursive boolean method takes as parameter the remaining distance required7 and returns whether this is possible or not If the remaining distance is 07 it returns true Else it considers each possible rst step in turn If it is possible to get home after making that rst step7 it returns true failing which it returns false One can adapt this to actually count the minimum number of steps needed See attached code Example Program StepsByRecursionjava a recursive program to solve Steps problem wdg 2005 public class StepsByRecursion public static final int lMPDSSlBLE 1 pre requiredgtO returns minimum number of steps a value of 1 means impossible static int minStepsint required int allowed ifrequired0 return 0 else int min required1 guaranteed to be too large consider all valid first steps forint possO possltallowedlength poss if allowedpossltrequired call recursively to determine best way to do remainder int temp minSteps required allowedposs allowed iftempltmin ampamp templMPUSSlBLE mintemp return ifminrequired1 return IMPOSSIBLE else return 1min else public static void mainString args int coins 1510 SystemoutprintlnminSteps17coins dime nickel and 2 pennies int silly 246 SystemoutprintlnminSteps17silly odd is impossible 42 142 The Queens problem One can also use recursion to solve the Queens problem The old puzzle is to place 8 queens on a 8 gtlt 8 chesscheckers board such that no pair of queens attack each other That is7 no pair of queens are in the same row7 the same column7 or the same diagonal The solution uses search and backtracking We know we will have exactly one queen per row The recursive method tries to place the queens one row at a time The main method calls place0 Here is the Javapseudocode void placeint row ifrow8celebrateAndStop else for queenrow all possible vals check if new queen legal record columns and diagonals it attacks recurse placerow1 if reach here have failed and need to backtrack erase columns and diagonals it attacks One can also use recursion to explore a maze or to draw a snow ake fractal 43 CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 15 Searching and Sorting 151 Linear Search and Binary Search The simplest search is called linear search In this search the data is stored in an array The search starts at one end of the array and proceeds to the other It stops if a match is found If there is no match the entire array is accessed So the running time is A classic search is binary search This can be used if the array is sorted say the array is sorted in increasing order Binary search compares the target value with the middle entry of the array If there is a match we are done not likelyl If the target is bigger than the middle entry then one can discard the rst half of the array Otherwise the target is smaller than the middle entry and so one can discard the second half of the array Since the array size shrinks by a factor of 2 each time the running time is Olog2 The code is provided at the end of the chapter For example searching for 32 in the following array 7 22 29 32 42 52 59 66 69 76 0 4 9 Start rst0 last9 middle4 32 is less than A442 Calls rst0 last3 middle2 32 is more than A229 Calls rst3 last3 middle3 a match 3 is returned Example Code public class BinarySearch static final boolean DEBUGtrue public static final int UNFDUND 1 look for TARGET in window positions FIRST FIRST1 LAST public static int searchint target int A int first int last ifDEBUGSystemoutprintlnquotSearching quotfirstquot quotlastquotquot iflastltfirst return UNFDUND else int middle first last2 iftarget Amiddle return middle else iftarget lt Amiddle return searchtarget A first middle 1 else return searchtarget A middle1 last public static int searchint target int A return searchtarget A O Alength 1 public static void mainString args int test 7222932425259666976 Systemoutprintln search32test 45 CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 16 Sorting 161 Quadratic Sorting Say we are trying to sort a list of numbers in increasing order There are two obvious sorting methods Both take 0n2 time In selection sort the entire list is scanned to nd an extreme element say the largest element This is then placed at the end of the list Then we recurse We can implement Selection Sort without any signi cant extra storage it is called an in situ77 sort The idea is to scan the array for the largest entry keeping track of its index Then swop the largest entry with the entry in the last position And repeat ignoring the last position of the array Here is the start array and the array after one pass INITIAL ARRAY 11 3 14 22 37 45 5 16 ARRAY AFTER ONE PASS 11 3 14 22 37 16 5H4S In insertion sort we build up the sorted list one entry at a time Each time we add a new entry We do binary search to determine where it belongs quickl But then we have to move everything down in the array to make space for it slow For example here is the array after six numbers have been added when the 5 is added almost all the numbers shift down ARRAY AFTER SIX NUMBERS ADDED 3 11 14 22 37 45 0 0 ARRAY AFTER SEVEN NUMBERS ADDED 3 5 11 14 22 37 45 0 162 Merge Sort Other famous sorts include Shell Sort7 Quick Sort7 Heap Sort and Merge Sort We nish with a discussion of the latter This is an example of a recursive sort MergeSort list A Arbitrarily split the list into two halves Use MergeSort to sort each half Merge the two sorted halves One divides the list into two pieces just by slicing in the middle Then one sorts each piece using recursion Finally one is left with two sorted lists And one must now combine them The process of combining is known as merging How to merge Well7 think of the two sorted lists as stacks of test papers sitting on the desk with the worst grade on top of each pile The worst grade in the entire list is either the worst grade in the rst pile or the worst grade in the second pile So compare the two top elements and set the worst aside The second worst grade is now found by comparing the top grade on both piles and setting it aside Etc INITIAL ARRAY 11 3 14 22 37 45 5 16 AFTER THE TWO RECURSIVE CALLS 3 11 14 22H5 16 37 45 MERGINGZ 3 7 5 1 416 1 14Z37 22 45 It follows that the merge part takes 0n time It can be shown we do no try to prove this that overall time is 0n log2 And Merge Sort is provably optimal CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 17 Iterators A great ideal An iterator enables one to step through the collection Conceptually forEaCh object in collection in turn do something with the object The Iterator interface in Java in package javauti provides two basic methods 0 boolean hasNext indicates whether the iterator is nished or not 0 Object next returns the next element in the collection and adjusts the iterator to the following element if hasNext is false7 then throws an Exception Further7 the constructor should initialize the Iterator to the rst element of the collec tion Note You shouldn7t modify a collection while an iterator is working7 even if the writers of Java provide a remove method To print out a list using an Iterator for a collection C7 we might write Iterator I CgetIterator while IhasNeXt Systemoutprintln Inext A collection C that has an iterator also allows one to use the for each77 construct forDbject ob C Systemoutprintln ob For this course7 we will implement an iterator with an external class That class will contain a reference to the collection that one is stepping through passed in by the constructor So the code for the Iterator of a Bag might be import javautillterator public class MyBaglteratorltEgt implements lteratorltEgt private BagltEgt B private pointer p J MyBaglteratorBagltEgt b Bb initialize p J public boolean hasNeXt return some test on p J public E next ifhasNeXt throw new NoSuchElementException E toBeReturned what p references J advance p J return toBeReturned public void remove not implemented throw new UnsupportedeerationException Note that the pointer always points to the next item that will be returned7 not the one that was last returned 49 CpSc 102 7 Fall 06 7 Goddard 7 Notes Chapter 18 More OOPJava We discuss some further Java features These include polymorphism comparators and cloning 181 Inheritance Revisited Polymorphism Polymorphism multiple forms is achieved in Java through over riding methods in a sub class For example suppose we have a class Sound that has a method play We might have sub classes Flute and Drum that extend Sound and over ride this method to provide effects speci c to that instrument Thus objects which are Sounds can come in many forms Java ensures that the appropriate form of the method is used Hence we can obtain multiple behaviors but at the same time we can have some general methods which treat all Sounds the same For example we could create an array of Sounds to represent some music Then an iterator through the array calling play at each step will produce the right sound at the right place We can also create sub classes that do not override the method7then the play of Sound will be used Another example of polymorphism is our writing of a toString method for most of our classes 182 Comparable and Comparator The Comparable interface is an in built interface to enable Java to provide facilities for sorting and searching problems The idea is that to sort a collection be it Strings ints or database records one needs a way to compare two items Implementing the ComparableltEgt interface guarantees that there is a method 0 int compareToE other which returns one of three values 71 if this comes before other 1 if this comes after other and 0 if the two objects are to be considered the same This method would usually be compatible with the equals method compareTo0 if and only if equalstrue ln built classes such as String and Integer implement this interface Thejavautilrray package has Sorting methods which takes arrays whose elements implement Compara ble A more general idea is a Comparator Suppose for example one wanted to sort Strings in a different way to the standard way The idea is to de ne a comparator which speci es how two Strings are to be compared with methods compare and equals The comparator is then a parameter to the constructor of the Collection 183 Cloneable This is a kludge The Cloneable interface has NO methodsl lts implementation means that the class may be cloned and should have a suitable clone method It is a shallow copy only the top level variables are duplicated7 not the objects that they reference 51


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.