DOC PREVIEW
UF COP 3530 - Lecture notes

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Data Structuresdata objectset or collection of instancesinteger = {0, +1, -1, +2, -2, +3, -3, …}daysOfWeek = {S,M,T,W,Th,F,Sa}Data Objectinstances may or may not be relatedmyDataObject = {apple, chair, 2, 5.2, red, green, Jack}2Data StructureData object +relationships that exist among instancesand elements that comprise an instanceAmong instances of integer369 < 370280 + 4 = 284Data StructureAmong elements that comprise an instance3693 is more significant than 63 is immediately to the left of 69 is immediately to the right of 63The relationships are usually specified by specifying operations on one or more instances.add, subtract, predecessor, multiplyData StructureLinear (or Ordered) Listsinstances are of the form(e0, e1, e2, …, en-1)where eidenotes a list elementn >= 0 is finitelist size isn4Linear ListsL = (e0, e1, e2, e3, …, en-1)relationshipse0is the zero’th (or front) elementen-1is the last elementeiimmediately precedes ei+1Linear List Examples/InstancesStudents in COP3530 =(Jack, Jill, Abe, Henry, Mary, …, Judy)Exams in COP3530 =(exam1, exam2, exam3)Days of Week = (S, M, T, W, Th, F, Sa)Months = (Jan, Feb, Mar, Apr, …, Nov, Dec)5Linear List Operations—size()determine list sizeL = (a,b,c,d,e)size = 5Linear List Operations—get(theIndex)get element with given indexL = (a,b,c,d,e)get(0)= aget(2) = cget(4) = eget(-1) = errorget(9) = error6Linear List Operations—indexOf(theElement)determine the index of an elementL = (a,b,d,b,a)indexOf(d)= 2indexOf(a) = 0indexOf(z) = -1Linear List Operations—remove(theIndex)remove and return element with given indexL = (a,b,c,d,e,f,g)remove(2)returns cand L becomes (a,b,d,e,f,g)index of d,e,f, and g decrease by 17Linear List Operations—remove(theIndex)remove and return element with given indexL = (a,b,c,d,e,f,g)remove(-1)=> errorremove(20) => errorLinear List Operations—add(theIndex, theElement)add an element so that the new element has a specified indexL = (a,b,c,d,e,f,g)add(0,h)=> L = (h,a,b,c,d,e,f,g)index of a,b,c,d,e,f, and g increase by 18Linear List Operations—add(theIndex, theElement)L = (a,b,c,d,e,f,g)add(2,h) => L = (a,b,h,c,d,e,f,g)index of c,d,e,f, and g increase by 1add(10,h) => erroradd(-6,h) => errorData Structure SpecificationLanguage independent¾Abstract Data TypeJava¾Interface¾Abstract Class9Linear List Abstract Data TypeAbstractDataType LinearList{instancesordered finite collections of zero or more elementsoperationsisEmpty(): return true iff the list is empty, false otherwisesize(): return the list size (i.e., number of elements in the list)get(index): return the indexth element of the listindexO f(x): return the index of the first occurrence of x in the list, return -1 if x is not in the listremove(index): remove and return the indexth element, elements with higher index have their index reduced by 1add(theIndex, x): insert x as the indexth element, elementswiththeIndex >= index have their index increased by 1output(): output the list elements from left to right}Linear List as Java InterfaceAn interface may include constants and abstract methods (i.e., methods for which no implementation is provided).10Linear List as Java Interfacepublic interfaceLinearList{public boolean isEmpty();public int size();public Object get(int index);public int indexOf(Object elem);public Object remove(int index);public void add(int index, Object obj);public String toString();}Implementing An Interfacepublic classArrayLinearList implements LinearList{// code for all LinearList methods must be provided here }11Linear List As An Abstract ClassAn abstract class may include constants, variables, abstract methods, and nonabstract methods.Linear List As Java Abstract Classpublic abstract classLinearListAsAbstractClass{public abstract boolean isEmpty();public abstract int size();public abstract Object get(int index);public abstract int indexOf(Object theElement);public abstract Object remove(int index);public abstract void add(int index, Object theElement);public abstract String toString();}12Extending A Java Classpublic classArrayLinearListextends LinearListAsAbstractClass{// code for all abstract classes must come here}Implementing Many Interfacespublic classMyInteger implements Operable, Zero,CloneableObject{// code for all methods of Operable, Zero,// and CloneableObject must be provided}13Extending Many ClassesNOT PERMITTED IN JAVAA Java class may implement as many interfaces as it wants but can extend at most 1 class.Data Structures In TextAll but 1 of our data structures are specified as Java interfaces.Exception is Graph in Chapter 17.Java specifies all of its data structures as


View Full Document

UF COP 3530 - Lecture notes

Download Lecture notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?