HOT

02Data Structures--Operations on Arrays
3 点赞
1 收藏
0下载
The course is mainly about Operations on Arrays.Generally covered Example of Insertion sort,Inheritance, subclass,Advantages and Disadvantages of Lists,Linked List,ArrayList implements a Dynamic Array and so on.

1.Operations on Arrays Here is a partial list of some common operations: • Read A[i] • Get the length of A • Sort A in the ascending or descending order • Update A[i] to x • Delete A[i] Java.util methods for Arrays support some of the following operations equals (A, B) {When are two arrays equal?) fill (A, x) copyOf (A, n) (What if n ≠ A.length) toString(A) sort(A) binarySearch(A, x)

2.class Test { public static void main (String[] args) { int arr1[] = {1, 2, 3}; int arr2[] = {1, 2, 3}; if (arr1 == arr2) // Same as arr1.equals(arr2) System.out.println("Same"); else System.out.println("Not same"); } } What should be the output?       import java.util.Arrays; class Test { public static void main (String[] args) { int arr1[] = {1, 2, 3}; int arr2[] = {1, 2, 3}; if (Arrays.equals(arr1, arr2)) System.out.println("Same"); else System.out.println("Not same"); } }   What should be the output?

3.Strings (not arrays) are immutable String s1 = "Hi";   String s2 = s1; // s1 and s2 now point at the same string - "Hi" Now, you can do nothing to s1 that would affect the value of s2. They refer to the same object - the string "Hi" - but that object is immutable and thus cannot be altered. Hello s1 Hi s1 Hi s2 s2 Before After If we do something like this: s1 = "Hello!"; System.out.println(s2); // still prints "Hi"

4.Example of Insertion sort   Algorithm InsertionSort(A) Input:       An  array  of  comparable  elements   Output:       The  array  with  elements  arranged  in  the  non-­‐decreasing  order   Main  idea:     for  k  from  1  to  (n-­‐1)  do     Insert  A[k]  at  its  proper  location  within  A,  A[1},  …,  A[n-­‐1]           Image source: “Introduction to Algorithms”, The MIT Press

5.Things to observe After i iterations the first i elements are ordered. After each iteration, the next element bubbles through the sorted section until it reaches the right spot: sorted | unsorted 1358|46792 13458|6792 Pseudocode for insertion sort for i in 1 to n   for j in i downto 2 if array[j - 1] > array[j] then swap(array[j - 1], array[j]) else break What is the maximum number of swap operations?

6.public static void insertionSort(int[] A){ int temp; for (int i = 1; i < A.length; i++) { for(int j = i ; j > 0 ; j--){ if(A[j] < A[j-1]){ temp = A[j]; A[j] = A[j-1]; A[j-1] = temp; } } } return A; }     Now,  use  java.util.Arrays to sort     import java.util.Arrays; public class HowToSortAnArray { public static void main(String[] args) { //Array of Integers int[] myIntArray = new int[]{31,108,69,4, 81}; //Sorts array in non-decreasing order Arrays.sort(myIntArray); //Loop to print Array values to console for (int i = 0; i < myIntArray.length; i++) { System.out.println(myIntArray[i]); } } }   Output: 4, 31, 69, 81, 108

7.Inheritance     One class inherits the properties (methods and fields) of another class.

8.Example 1 public class Calculation{ int z; public void addition(int x, int y){ z = x+y; System.out.println("The sum is:"+z); } public void Subtraction(int x, int y){ z = x-y; System.out.println("The difference is:"+z); } } public class My_Calculation extends Calculation{ public void multiplication(int x, int y){ z = x*y; System.out.println("The product is:"+z); } public static void main(String args[]){ int a = 20, b = 10; My_Calculation demo = new My_Calculation(); demo.addition(a, b); demo.Subtraction(a, b); demo.multiplication(a, b); } }

9.Example 2 class Super_class{ int num = 20; //display method of superclass public void display(){ System.out.println("This is the display method of superclass"); } public class Sub_class extends Super_class { int num = 10; //display method of sub class public void display(){ System.out.println("This is the display method of subclass"); } public void my_method(){ //Instantiating subclass Sub_class sub = new Sub_class(); //Invoking the display() method of sub class sub.display(); //Invoking the display() method of superclass super.display(); //printing the value of variable num of subclass System.out.println("value of num in sub class:"+ sub.num); //printing the value of variable num of superclass System.out.println("value of num in super class:"+ super.num); } public static void main(String args[]){ Sub_class obj = new Sub_class(); obj.my_method(); } }

10.Example 3   (Simple) progression 0, 1, 2, 3, 4 … Arithmetic progression 4, 9, 14, 19, 24 … 0, 3, 6, 9, 12,15… Geometric Progression 1, 2, 4, 8, 16, 32, … 2, 20, 200, 2000, 20000, 200000, … The difference is how you compute the next value.

11. 19   protected  void  advance  ()  {      20       current++   } Study how two other sub-classes: Arithmetic Progression and Geometric Progression can be created from this super-class.

12. What can a subclass do 1. It can declare new fields 2. It can declare new methods 3. It can override old methods with new implementations class Base { int x = 100; } class Sup1 extends Base { int x = 200; void Show() { System.out.println(super.x); System.out.println(x); } public static void main(String[] args) { new Sup1().Show(); } } What is the output?

13.Lists Consider the problem of storing a set of items, where the order is important (as in a phone directory, or student records at the university). How will you store them? Use an array? Advantages Know the index, and locate the item! Disadvantages 1. Insertion of a new item at the beginning or the middle of the takes time proportional to the length of the array. 2. Arrays, once declared, have a fixed length. To increase the length of the array, there is the overhead of copying the array. **(However, ArrayList facilitates this. More on this later.)** Linked list resolves the problem.

14.Linked List Example of a recursive data type: public class ListNode { {int item; ListNode next; //recursive definition } // Construct three ListNodes ListNode n1 = new ListNode(); ListNode n2 = new ListNode(); ListNode n3 = new ListNode(); n1.item = 15; n2.item = 7; n3.item = 42; n1.next = n2; n2.next = null; n3.next = 42;

15.Why is this a good idea? 1. Inserting an item takes “constant time.”