COP 3540 Data Structures with OOPThe Basics of Arrays in Java – Array CreationThe Basics of Arrays in Java – Accessing Array ElementsThe Basics of Arrays in Java – InitializationThe Basics of Arrays in Java – Array Example – p1The Basics of Arrays in Java – Array Example – p2Program OrganizationDividing the Program into ClassesBetter Approach: the lowArray.java ProgramSlide 10Evaluation?First: A little bit on Class InterfacesDiscussion: pg. 1 of 2 (We’ve already talked about these, but…)Discussion: pg 2 of 2.Slide 15Slide 16Ordered ArraysSlide 18Binary Search with the find() MethodSlide 20More on Ordered Arrays (1 of 2)More on Ordered Arrays (2 of 2)SearchingSlide 24Binary Search PerformanceSequential (Linear) Search performanceTo start with: You must know ‘some’ integer powers of 2!Slide 28Insertions into ordered / unordered arraysInsertions into an Unordered Array = ConstantInsertions into an Ordered Array = TerribleSearches – linear and binaryLinear Search: Unordered Array: Proportional to nBinary Search: Ordered Array: Proportional to log2nSlide 35Big O NotationSlide 37Bottom Lines – Big O NotationRun Times using Big O – Know this TableAdditional Relationships using Big O NotationArrays for the World – Advantages and DisadvantagesBetter Choices in Different CircumstancesStoring ObjectsQuestions?141COP 3540 Data Structures with OOPArraysChapter 2241The Basics of Arrays in Java – Array CreationTwo kinds of Arrays: primitive (ints, floats, double, char, unsigned, …) andobjectsIn Java arrays are objects not primitives.Since all arrays are objects, must use ‘new’ to create. Two ways to create an array in Java 1. int[ ] intArray; // only the reference intArray = new int[100]; // creates the array with space for 100 integers // intArray now points (references) this array. 2. Alternatively: int intArray[ ] = new int[100]; Either format is acceptable. (I prefer the latter)What is a primitive?Where is the array data actually stored?Where is the reference stored?Attribute: int arrayLength = intArray.length; // number of elementsWhere does this ‘length’ attribute come from? How do you know intArray.length is not a method?341The Basics of Arrays in Java – Accessing Array ElementsArray access is via an index numberWhat is an index? Same as a subscript?temp = intArray[3]; //assign value of fourth element // in intArray to temp (assumes // temp is an int).intArray[7] = 66; // assigns value of 66 to // intArray[7]. (8th element)Array Index Out of Bounds – discuss….intArray = new int [100]; // bounds?441The Basics of Arrays in Java – InitializationUnlike other languages, integer arrays are set to 0.autoData[ ] carArray = new autoData[4000];“I have an array of autoData objects named carArray and have 4000 of them.”Each array element has null value (pointer value is null)No object values have been created. Assigning values to primitive array types:int[ ] intArray = {2,4,78,54,67}; // initialization listAlso sets array to five elements: intArray[0] … inArray[4].541The Basics of Arrays in Java – Array Example – p1// array.java - // demonstrates Java arrays This is an array of primitives / not objects!!class ArrayApp { public static void main(String[] args) { long[ ] arr; // reference to array // what is a ‘long?’ arr = new long[100]; // allocates array for 100 ‘longs.’ // ‘long’ is a primitive or object? int nElems = 0; // number of items (to be used for size of arr) int j; // loop counter long searchKey; // key of item to search for//-------------------------------------------------------------- arr[0] = 77; // insert 10 items // brute force approach!! arr[1] = 99; // specifically assigning each element to arr[2] = 44; // a specific location in the array! arr[3] = 55; arr[4] = 22; //’hard coded values” arr[5] = 88; arr[6] = 11; arr[7] = 00; arr[8] = 66; arr[9] = 33; nElems = 10; // now 10 items in array//-------------------------------------------------------------- for (j=0; j< nElems; j++) // display items // value of j upon leaving loop? System.out.print( arr[j] + " "); // How many times is the ‘for’ executed? System.out.println (""); // How many time is the System.out… executed//--------------------------------------------------------------641The Basics of Arrays in Java – Array Example – p2// Continuing… searchKey = 66; // find item with key 66 for(j=0; j<nElems; j++) // for each element, // any difference here j++ or ++j ?? if(arr[j] == searchKey) // found item? break; // yes, exit before end // What does ‘break’ do? if(j == nElems) // at the end? System.out.println("Can't find " + searchKey); // yes Will this always work??? else System.out.println("Found " + searchKey); //-------------------------------------------------------------- searchKey = 55; // delete item with key 55 for(j=0; j<nElems; j++) // look for it if(arr[j] == searchKey) break; for(int k=j; k<nElems; k++) // move higher ones down // what if k = nElems? Will this work? arr[k] = arr[k+1]; nElems--; // decrement size // check: either we get a hit or not. Check both!// What is wrong with this little routine?//-------------------------------------------------------------- for(j=0; j<nElems; j++) // display items System.out.print( arr[j] + " "); System.out.println(""); } // end main() } // end class ArrayAppNote: all processing is in one single method, main!741Program OrganizationProgram looks like a COBOL program or a C program.All components: data and procedure – are smushed together.No chance for reuse; extension; information hiding, etc.Will it work? Yes. But it does NOT take any advantage of OO features.In general, this is poor programming…841Dividing the Program into Classes To build a much
View Full Document
Unlocking...