LAB Data Structures
LAB Data Structures CS 230
Popular in Course
Popular in ComputerScienence
This 15 page Class Notes was uploaded by Jordon Hermiston on Thursday October 29, 2015. The Class Notes belongs to CS 230 at Wellesley College taught by Panagiotis Metaxas in Fall. Since its upload, it has received 28 views. For similar materials see /class/230931/cs-230-wellesley-college in ComputerScienence at Wellesley College.
Reviews for LAB Data Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
C5230 Data Structures Spring 2009 httpsweJJes eyeduwszgo P Takis Metaxas Objectives of CS 230 2 Teach mah 1deas or programmhg Data ab tractron Modu arrr Pertormanoe anarysrs Basrc abstract data types ADTs Make you a more competent programmer desrgner tester anaryzer debugger Herp you deverop a project Worth Showmg ctr u Have fun in the process Why ADTs AHOW you to wnte comp ex programs easrer T us code yes a 7 To mprove code some pasrc ADTS perrormanoe rrav Lmked hst 391 AHows moduJarrty of Jorge Stack 5 project Easrer to understand Queue 1arge chunks of code Tab e Easrer to coHaporate Wrth pr Ohm queue arge teams 1 Not so basic v To combat Sergeant Tree Spagheth Code set GraDh 11 Do you speak Java u hmlzl java Java summations u nmtrates the tasic structure of a Jews mllmunn snsssssnmsssmnsssssnsssssmnmmmmsmmmmn bmic class LIIcull use are 1 quotnuts a pres aaential auate Systm eat nnntan n aunts by mm Lxmnln 5st eat suntan mater yen are he a quad one u Java portability thlnul bdrm Mamba 11 Java Reserved Words abstract else interface switch assert enuln any synchtnnized baalean extends native this break false new threw byte final null thraws case nally package transient catch Elaat private true cbar far prntected try class gntn public vnid canst if return valatile cantinue implements shurt while default impnr ua instanceaf stricth duuhle int 15 Object Oriented Programming Java t5 an obJectcortented programmtng tanguage As the term trn hes a bJect re a ndamentat ent tv m a Java program Db ects can be used ettectrvetv to represent rearwortd en ttes For tnstance an object rntgnt represent a part cutar photo m a photo nagement program e g rphoto Each photo object handtes the processtng and data management retated to that photograph 15 Classes I An object ts de ned bv a class A ctass t5 the btueprrnt or an object r The dass uses methods to de ne the behavrors or the object The ctass that contatns the main method or a Java program represents the enttre program A dass represents a con cepp and an object represents the embodiment or that concept Muttrpte objects can be created trom the same dass 15 Objects and Classes Junn s Bank Account Eatance 515 Jasun s BankAccuunt Eatance 1 245 DEB Mary s Bank Account Eatance 13833 15 Inheritance One dass can be used to dertve another we inheritance masses can be organrzed rnto hrerarchres 21 Additionjava u mum a a mum u u llamnstxates m are new the mum And mm H amatemtxnn Wexatnts knmkAkNknkANAknmkAkmnkANAknmmmnmmmmxw u yum em md m surqu neat Systmnut punch 24 and d5 comatemmd t 24 45 Systmnut pxxntln 24 mm mm A m 45 1 N 1 Character Strings A Strtng or characters can be represented as a strrng lttera bv puttth doubte quotes around the text quotHellor Worldl quot quot123 Mm acmequot Everv character strrng ts an object tn Java de ned bv dne smug dass Everv Strtng tterat represents a scum object c A Strtng hterat cannot be broken across two hnes 21 Esca pe Sequences n What if we wanted to print a the quote character u The following line would confuse the compiler wh 7 Systemoutpr1ntln quotI sold quotHelloquot to youquot 0 An escape sequence is a series of characters that represents a special character n escape sequence begins with a backslash character Systemoutpr1ndn quotI sold quotHelloquot to youquot 21 Escape Sequences quot Some Java escape sequences Escape Sequence Meaning t n line r carriage return quot double quo e 39 Ingle quote backslash 21 Rosesjava u lases 1 a Enum39bxxnns u in uences the m of eEch seaems knmkkkNknkkNkknmkkkmnkkNkkn mmmmemmmem 5 d imaman i 22 Va riables and Constants A variable i5 a harne for a locat On in rnernorv A variable must be declared bv Specifying the variables name and the tvbe of information that it Will hold data type variable name int count temp result 9 A Constant is ari identifier that holds the same value during itS entire eXiSteriCe e The compilerwill issue an error ifyou trvto change tlie value of a constant 0 irl Java We use the nal modifier to declare a Constant nnal 1n mninmenm as 23 Primitive Data D There are eight primitive data types in Java Four of them represent integers byteshort1ntlong A Two of them represent floating point numbers float double One of them represents characters Char s And one of them represents boolean values boolean 23 Numeric Primitive Data r The difference between the various numeric primitive types is their size and therefore the values they can store Storage Min Value Max Value 327 int 32 bits 2147433643 2147433647 long 64 bits lt e x 101 gt 9 x 101 float 32 bits I 34 X10 with T signi cant di ts double 64 bits I 17 X10Jun with 15 signi cant digits 23 Cha racters 23 Character Sets A char variable stores a Single character I A character set is an ordered list or characters 39 Character i terais are delimited by Single quotes With each character corresponding to a unique nurnber X 7 9 W A Char variable in Java can store any character set i Evarnple declarations a At rrorn the Unicode character that t v 3 mm quot quot Pam 39 quot i The Unicode character set uses 16 bits per character lvote the distinction between a character variable allowing for 65536 unique characters which holds onlv one character and a stung o i Whlch can hold multiple characterg It is an international character set containing svrnbois ages and characters rrorn rnanv World langu 19 2D 23 Boolean 24 Division and Remainder A boolean value represents a true or false 39 Itboth operands to the lelSth operator gt are condition integers the result is an lnteger the rractional part is discarded J The reserved Wordstrue and false are 14 3 equa39s 4 the only valid values for a boolean type a I 12 equals 0 b lea d e false The remainderoperaturretuihsthe remainder arter dividing the second operand into the rirst 39 A boolean variable can also be used to represent any two states such as a light bulb being on or off 14 9 3 equa39s 2 a 95 12 equals B n 22 24 Operator Precedence 24 Assignment Precedence Ope am can be 03 de 0 comp ex WES 0mg The assignment operator has a lower precedence than result total count max 7 offset the a thmet c operators The right and lert hand sides or an assignment operators have a Weiirdeflned precedence which deterrhines statement can contain the sarne variable the order in which thev are evaluated First one is added to the original value of count Multiplication division and remainder are evaluated count prior to addition subtract on and string concatenat on are evaluated rorh left to rig t but parentheses can be used to force the evaluation order Then the result is stored back into count overwriting the original value count 1 24 Increment and Decrement i The increment and decrement operators can be appiied in postrw form count or pre x rorm count When used as part of a iarger expression the two forms can have ditterent ettects i Because of their subtieties the increment and decrement operators shouid be used with care 24 Assignment Operators C Java provides assignment operators to simplify the assignment process Operator Example Equivalent To x x x y x x x y x x x y x x x y x x x 9e y 2 5 Data Conversion Sometimes it is convenient to oonvert data from one tvpe to another For exam pie we mav want to treat an integer as a oating point value These oonversions do not change the tvpe of a variabie or the vaiue mats stored in it thev oiiiv convert a vaitie as part of a computation Conversions must be handied carefLiHv to avoid iosino intormatim id ning rsio e sa t because thev tend to go from a smaii data tvpe to a iarger one such as a sham to an me Narrowing conversions En iose intormanon because the tend to go rrom a iarge data tvpe to a smaiier one in Java data ooniiersions can oocur in three wavs assignment conversion promotion casting 25 Assignment Conversion Assignment conversion occurs when a vaiue of one tvpe is assigned to a variabie of another a float money lnt dollars The following converts the vaiue in aallaes to a that money dollars omv w dening conversions can happen via assignment Note that the vaiue or tvpe oraauaes did not change 2 5 Promotion Promotion happens automatically when operators in expressions convert their operands tloat sum lnt count The value of count is converted to a floating point value to perform the following calculation result sum Count 25 Casting Casting is the most powertui and dangerous technique for convers on Botri widening and narrowing conversions can be accompiished bv exp citiv casting a vaiue i To cast but tvpe in parentheses in front or the vaiue being converted For xarnpie it total and caune are integers but we want a oating point resuit when dividing them we can cast total result tloea cecal count 26 Reading The Scanner Class u The Scanner class provides convenient methods for reading input values of various types A Scanner object can be set up to read input from various sources including values the user types on the keyboar quot Keyboard input is represented by the System1n object 26 Reading Input quot The following line creates a Scanner object t at rea s from t e keyboard Scanner scan new Scanner System1n a The new operator creates the Scanner object a Once created the Scanner object can be used to invoke various input methods such as answer scannexcLine 26 Reading Input i39 The Scanner class is part of the javautll class library and must be imported into a program to be used 9 The nextLlne method reads all of the input until the end of the line is found u The details of object creation and class libraries are discussed further in Chapter 3 26 Echojava 1 REM 1 a S7a7a u u imamaa m a r a mmlm quotan r a sca7 caa u mad am 7 Lil aar knkkakknmkkkmnkkakknkakkkmnmannmkmmmam nip 1 u sca mnc class Eclm saa 7 17 on 1 r a i aaa a ac mama 5m 7 17 iv um i aaaaas 26 Input Tokens u Unless Speci ed otnerWise wnite space is used to separate tne input elernents called to ens e includes space cnaracters taps new line cnaracters The ac rnetnod ottne scanner class reads tne next input token and returns it as a string n Methods Such as nexant and nextDouhle read data of particular types 26 GasMileagejava I mamas java a Sa7a u wort 1 5cm System 7 77 an a n 1 nuaa i n a ac mm System 7 77 1 na gnlmis r 2 ca i can a ac axcnmnao m a nuaa I puma saa c 7 Miles pa p11 l my USING JAVA OBJECTS Objects and Keferences The String Class Using Packages The Random Class The Math Class Enumerateol Types Wrapper Classes Formatting Output 08230 Reading LDC Ch 3 31 Objects Generally we use the new operator to create an object namel new String quotSteve Jobsquot This calls the String constructor which is a special method that sets up the object Creating an object is called instantiation An object is an instance of a palticular class 31 Object References Q A primitive variable contains the value itself but an object variable contains the address of the object An object reference can be thou ht of s a pointer to the location of the object lt9 We usually depict a reference graphically numl namel El 31 Understanding the Assignment ilk Forprimitive t es and stores itin a variab e numl Before num2 Execute num2 numl numl After For object references VJSS39mt takes a Py of a Value assignment copies the address must 551 namez namel 0 Two or more references that refer to the same object are called aliases 30 one object can be accessed using multiple reference variables I t Aliases can be useful but dangerous should be managed carefully 6 Changing an object through one reference changes it for all of its aliases because there is really only one object 4 31 Garbage Collection n an object no longer has any valid references to it it can no longer be accessed by the program Q The object is useless and therefore is called garbage O Java performs automalic garbage colleciion periodically recycling an object39s memory space to the system for future use Q In other languages the programmer is responsible for performing garbage collection 43gt Garbage collection is great but may introduce unexpected delays in the execution of a program 32 String Methods ltgt Because strings are so common we don39t have to use the new operator to create a string object namel quotSteve Jobs all Immutable string Once a String object has been created neither its value nor its length can be changed ltgt However several methods ofthe string class return new string objects that are modi ed versions ofthe original 61 It is occasionally helpful to refer to a particular character within a string This can be done by specifying the character39s numeric index elk In the string quotHelloquot the 39H39 is atindex 0 and 39 4 the 39o39 isatin ex 32 StringMutationjava StringMutationjava Java Fuundatinns Demunstrates the use g the String class and its methods public class Stringt lutatinn Prints a string and various nnitntigns n it public stntie void nnin String args String phrase Change is inevitnhie except mm vending niachines String mutatinnl mutatinnZ mtntigna mutatinnd mutatinnl e phr n n n n N n m 1 is n n m n gtlt mtntigna mutatinn suhstring 3 30 Systemnutprintln Mutation am i i mtntigna Systemnutprintn Mutated length i mtntign41engtho 33 Class Libraries Q A class library is a collection of classes tha we can use when developing programs 43gt The Java standard class library is rt of any Java development environment lav om 39Zselll ldr saai Q lts classes are not part of the Java language per se y but we rely on them heavil Q Various classes we39ve already used System Scanner string are part of the Java standard class library Other class libraries can be obtained through third party vendors or you can create them yourself 33 Packages Q2 The classes ofthe Java standard class library are organized into packages 4 Some of the packages in the standard class library are Package Purpose javaang General support javaappet Creating applets for the web javaawt rap ics and raphical user interfaces javaxswing Additional graphics capa i ie javanet Network communication javauti Ut es 33 The import Declaration A When you want to use a class 39om a package you could use its fully qualified name java utll5canner scan new java utll5canner systemln 0 Or you can import the class import javautll Scanner t and then use just the class name Scanner scan new Scanner systemln To import all classes in a package you can use the wildcard character import javautll M All classes ofthe javalang are imported automatically into all programs That39s why we don t have to impon the system or Strlng classes explici ly canner class on he othe hand is pan ofthe java utll package e The s and therefore must be import in 34 Very useful The Random Class The Random class is part of the java utll package It provides methods that generate pseudorandom numbers lt9 A Random object performs complicated calculations based on a seed value to produce a stream of seemingly random values Useful also in testing main programs by creating random input 34 RandomNumbersjava import javantilkandom class Random umbezs generates random numbers in various ranges public class Random u mbezs public static void main stringll args Random generator new RandomO 39 t numl 1 at num2 numl generatornextlnt Systemoutprintln quota random integer quot numl numl generatornextlntlo Systemoutprintln From 0 to 9 v numl num generator nextInt15 20 Systemoutprintln quotFrom 20 to 34 v numl numl generatornextlnt2o lo Systemoutprintln quotFrom lo to 9 v numl num2 generatornextrloat systemoutprintln quota random float between ol quot num2 num2 generatornextrloat 9 s 00 to 5999999 numl intnum2 l systemoutprintln From 1 to s v numl 35 Very useful The Math Class L 9 The Math class is part ofthe javalang package 9 Math inctionsinclude n absolute value a square root I exponentlatlon u UgonomeUmfundwns t The methods ofthe Math class are static methods aka class methods 9 Static methods can be invoked through the class name 39 39 ed 0 o Ject of he Math class Is need discriminant Mathpowb 2 4 a c ootl 1 b Mathsqztdiscziminant 2 a oot2 1 b Mathsqztdiscziminant 2 a 37 Enumerated Types An enumerated type establishes all possible values for a variable by enumerating them IMH Helps program readability How would you represent the 4 seasons The values are identi ers ofyour own choosing O 6 This declaration creates an enumerated type called Season enum Season Hunter sprlng summer fall Once a type is de ned a variable ofthat type can be declared Q season tlme and it can be assigned a value tlme Seasonfall Enumerated types are typesafe you cannot assign any value other than those listed 37 Ordinal Values and Names L Q Internally each value of an enumerated type is stored as an integer called its ordinal va us The rst value in an enumerated type has an ordinal value ofO the second 1 and so on However you cannot assign a numeric value to an enumerated type even if it corresponds to a valid ordinal value lt9 The declaration of an enumerated type is a special type of class and each variable of that type is an object The ordlnal method returns the ordinal value ofthe object The name method returns the name ofthe identi er corresponding to the object39s value 37 lceCreamjava leeCream j ava Java raunuatiuns nemanstrates the use a enumerated types publie elass leeCream enuln rlavar vanilla ebvevlate strawberry fudgekipple coffee kanad mlntcbueulatecblp cankieDnugh Creates aaa uses variables of tbe rlavar type public statle void main strlnell args r rlavur eunel canle be rla l urrue sad Systemuutprintln canal value l eunel Systemuutprintlu canal uralual l canelnrdinal Systemuutprirtlb canal name i eunelname fut rlavur eune rlavarvalues Systemuutprintln cane value l cane 38 Wrapper Classes Are the primitive types objects t The javalang package contains wrapper classes that correspond to each primitive type Primitive Type Wrapper Class byte Byte short short int Integer long Long float r1oat double Double char character boolean Boolean vord void 38 Wrapper Classes t An Integer object which represents the integer 40 as an object Integer age new Integer4u An object ofa wrapper class can be used in any situation where a primitive value will not suf ce For example some oblects serve as containers ofother oblects 0 Primitive values could not be stored in such containers but wrapper objects coul be 0 Wrapper classes also contain static methods that help manage the associated type For example the Integer class contains a method to convert an integer stored in a String to an int value num Integer parseInt str Q The wrapper classes olten contain useful constants as well 9 For example the Integer class contains MIN VALUE and MAXivALUE which hold the smallest and largest lnt values lE 38 Autoboxing and Unboxing 4 4 Autoboxing is the automatic conversion of a primitive value to a corresponding wrapper object Integer 1 int num 42 1 num Q The assignment creates the appropriate Integer object 4 The reverse conversion unboxing also occurs automatically as needed 142 Let s play Bingo Rules a Each player nas a random card llke gt 5 group gt correspond to each of v 5 letters 9 3925 s E lrls I leash murals swarm 061r75 Caller pulls balls numbered lr75 randomly from a bag 4 The flrst person who eonpletes EINGO in any straight direction Wins f numbers a Q How do 142 BingoBalljava Repxesents a hall used in a ninaa game m puhlic class Hinqonall private ohaa letter private int mmihel Constxucls a Bingo hall with specified numhex and appxnpxiale letter puhlic Binqo all lint mum l numhex a mun f num lte l lette a in else if 1mm lt 3m letter a 1 else if nuln lt 45D letter a II it ltr lett r a my letter a in l tete 142 A Bag Collection 477 A bag is a collection that facilitates the selection of random elements item the group ltgt A bag is nonlinear elements in the bag have no particular positional relationship to each other The implementation of the bag will store the elements in an array or some other technique 141 Introduction to Collections if Q A collection is an object that serves as a repository for other objects Q A collection provides services to add remove and manage the elements it contains The underlying data structure used to implement the collection is independent of the operations provided Q Collections can be separated into two categories linear elements are organized in a straight line no ear elements are organized in something other than a straight line determine the order in which they were added to the collection some inherent relationship among the elements Q Ordering of elements relative to each other is usually d by 31509 141 Your First ADT ltgt An abstract data type ADT is a set of d t the particular operations that are allowed on that data Abstract because the operations you can perform on it are separated from the underlying implementation x A collection is an ADT For every collection we examine we should consider w oes the collection operate conceptuall What operations are included in the interface to the collection What kinds of problems does the collection help us solve How might the collection be implemented a U quot quot 39 39 compare from 39 p 39 141 Separating Interface from Implementation g Services provided by collection ace that adhere to an interf 142 javafoundationsBag Haqjava Java Raunaatinns Defines the inlexface to a hay collection package javafnundatinns public interface EagltTgt extends IterableltTgt Adds the specified element to the bag public void add 391 element Removes and returns a random element from the bag public T removeo Returns true if bag contains no elements false otherwise public boolean isamptyo Returns the number of elements in the bag 39 e public int siz 0 Returns a string representation of the bag public string tostringo 141 On Generic Types 7 J Our de ned class will then be able to operate on store and manage ob39ects whose type is not specified until the class is instantiated Q Example de ne a Group class that stores and manages a group of objects lt0gt Using polymorphism we can de ne Group to store references to the Object class ltgt However any type of object could then be stored in our Group resulting in a loss of control ltgt A better approach is to de ne the Group to store a generic type 391 class Groupltrgt t declarations and code that manages objects of type T 31509 142 Bingojava Sys teu nulpxinl1n w Size t a hinqn anizeH a n l fnx taut mun e 1 uu lt wuguus numl ta e hinqn aqxenmve 1t Systemnulpxinln thaut n Inn at yuu need t cuuuect tn the appxnpxiale package a nus anSSPnTnusexsllml a uns xynxt cLAsst n m a uus echu SanSSPn39nl lquotexsUn x cnmyile with the 11 path um nus javac ecu ueeut Einqnjava 143 javafoundationsArrayBag mxay aqjava Java ruuuaatau II II Repxesenls au allay implementation of hay cuuectauu package javafnundalinns impult javautu impult javafnundalinnsexceptionsEmyLycnuzclinnExceplinn public class Axxay aqltTgt implements Haqltwgt pxivace final int narmnxrfcnvncln gxivale aht cuuutr private m cnuteuts pxivale tatac 1n Random xaua new nauunmtt 143 An Array Implementation of a Bag We could use Java s SDK to implement Bingo Or we could use the library provided by the book authors Let s develop ArrayBag in javafoundatlons package ltgt ltgt ltgt Issues39 AH array can be uSed to store the elements of our collectrorr H Wever arr arr ay has a xed srze once rt rs create Collecuons sometrrrres are llrmted to a specr rc srze We don twlsh to have ourbag llrmted by tms co str When the bag l5 full We grow the collecuon t rrt to support reallocatrrrg space ror the array to 143 javafoundationsArrayBag ll Cxeales au eth hag using the default capacity puhlic mxay aqll cuuut cuuteuts 11m thew nhjectmu mnxricnrncllyn mu the specif ied element to this hag 1 slnxinq the element at the end of the net expanding the allay capacity a needed puhlic void add u e1eett if tcu uut e cuntenls19nqthl expandcapacilyll aueeat ynllx cuue hex to add element max 31509 143 javafoundationsArrayBag 143 javafoundationsArrayBag Remnves a landmn elem fxnm um hay shifting m last element mg n 11 u km W 1m contiguous Thxnws mylycnueclinnlxceplinn if um hay is empty pnhlic 139 lumen lhxnws Ewlycnueclinnilxceplinn if 1cm nt lhxnw new mrlycnuaclinnlxceplinn Human nyexalinn mud The hay 39 Enlyly in mm landuuextlnl cnunlDF 139 mm cnnlenls ndex insexl ynux and hex u xemnve m element at lncacinn index xeunn xesllll max nun Ll if um hay cnnlains nn elemnls and 31 ll amendquot puhlic hnnlean 152pr insexl you and hex nun m numhex of elements in nu hay puhlic m sum insexl yum and hex max 143 javafoundationsArrayBag Cleales a new allay to sum m contents of um hay with twice m capacity of m old one pxivate void exyandcapncily n lnqex u up new hjeclcnnlenlLlenqlh ZD 1m lucaunn m u element contents laxqex1ncalinn elem conunu z laxqet nun a smug xepxesenlalinn of um hay pnhlic Slxinq hustling Slxinq usun Hag conunun in mm indew index lt cnunl indexH xesnll contenls ndex n n xeunn us max 7 143 javafoundationsArrayBag We are not done yet public interface BagltTgt extends IterableltTgt Henlan an ilexalnx in nu hay yuhlic IlexalnxltTgt ilexalan nay1xanxltwgt 191 z nquot Axxayxxanxltwgt fnx int index index lt cnunl indexgt ilexadd1cnnlenlsindexH 19nmn itex 31509