DOC PREVIEW
Berkeley COMPSCI 61B - Lecture Notes

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 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 12 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 12 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 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

IntroductionWaiting list: You should be let in if you meet the CS61Arequirement. Otherwise, you must appeal.Concurrent enrollment: See me today.For today: More on pointer fundamentals, arrays.Readings covered today: On To Java, Chapter 28;Programming Into Java, Section 5.6.4.Review readings: At this point, you should be ableto benefit from more details of statements and simpleexpressions. See Programming Into Java, Sections 4.1,4.2, Chapter 6.Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 1Passing by value• In Java, as in Scheme, all parameter values are passedby value.• This means that when you see a function definitionsuch as... f (some type x) { some statements }and a call such as f(something), the effect is some-thing like{ some type x = something;some statements;}(Quibble: only “something like” because of possiblename clashes, and because of returning values).static void zap (int x){print (x+3);}-------------------------zap (y + 17);⇒{int x = y + 17;print (x+3);}Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 2Effect of passing by value• So what happens here?int y = 42;incr(y);// What is y?where I have definedstatic void incr (int x) {x += 1;}• And what happens here?IntList Q = new IntList (1, null);next(Q);// What does Q point to?where I have definedstatic void next (IntList L) {L.tail = new IntList (2, null);L = L.tail;}Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 3Answers• Same thing happens in both cases:– The value of y (42) does not change after incr.– The value of Q (the pointer value—which IntListobject it points to) is the same before and aftercall to next (although the pointed-to object doeschange).Before callQ: 1After callQ: 1 2L:• In fact, in Java there is no way to define incr or nextso that they do change their arguments.• In C++ or Pascal, by contrast, the assignments to xand L can be made to change y and Q.• Those languages allow one to pass containers aswell as values. This is called “passing by reference.”• Warning: some authors incorrectly write that Java“passes numbers by values and objects by reference.”Suspect them of incompetence.Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 4Arrays• An array is structured container whose componentsare– length, a fixed integer.– a sequence of length simple containers of thesame type, numbered from 0.– (.length field usually implicit in diagrams.)• Arrays anonymous, like other structured containers.• Always referred to with pointers.• For array pointed to by A,– Length is A.length– Numbered component i is A[i] (i is the index)– Important feature: index can be any integer ex-pression.Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 5A Few SamplesJava Resultsint[] x, y, z;String[] a;x = new int[3];y = x;a = new String[3];x[1] = 2;y[1] = 3;a[1] = "Hello";int[] q;q = new int[] { 1, 2, 3 };int[] r ={ 7, 8, 9 };x: 0 3 0y:z:a:Helloq: 1 2 3r: 7 8 9Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 6Multidimensional Arraysint[][] B, C, D;B = new int[3][];C = new int[3][2];D = new int[3][];D[0] = D[1] = D[2]= new int[2];int[][] E ={ { 1, 2 },{ 3, 4 },{ 5, 6 } };// E[2][0] == 5int[][] T ={ { 1 },{ 2, 3 },{ 4, 5, 6 } };B:C:0 00 00 0D:0 0E:1 23 45 6T:12 34 5 6Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 7Example: Accumulate ValuesProblem: Sum up the elements of array A.static int sum (int[] A) {int N;N = 0;for (int i = 0; i < A.length; i += 1)N += A[i];return N;}// For the hard-core: could have writtenint N, i;for (i=0, N=0; i<A.length; N += A[i], i += 1){ } // or just ;// But don’t: it’s obscure.Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 8Example: Insert into an ArrayProblem: Want a call like insert (A, 2, "gnu") toconvert (destructively)A: beargazellehartebeestskunk⇓A: beargazellegnuhartebeest/** Insert X at location K in ARR, moving items* K, K+1, ... to locations K+1, K+2, ....* The last item in ARR is lost. */static void insert (String[] arr, int k, String x) {for (int i = arr.length-1; i > k; i -= 1) // Why?arr[i] = arr[i-1];// Alternative:// System.arraycopy (arr, k, arr, k+1,// arr.length-k-1);arr[k] = x;}Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 9Growing an ArrayProblem: Want A = assign(A, 3, 5) to make A pointto an array containing the original contents, but with 5assigned to A[3]. “Grows” A if necessary to allow the as-signment, using default values for new elements. (LikeA[3] = 5, but avoids bounds errors).Example with no growth:A: 0 7 1 8⇓A: 0 7 1 5Example with growth:A: 0 7⇓A: 0 7 0 50 7 (garbage)Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 10Growing an Array: The Program/** Return an array with element K equal to X,* elements 0 .. A.length-1 other than K* copied from A, and elements A.length .. K-1* (if any) set to 0. Result has length* max(A.length,K+1). Destructive operation. */static int[] assign (int[] A, int k, int x){if (k >= A.length) {int[] newA = new int[k+1];System.arraycopy(A, 0, newA, 0, A.length);A = newA;}A[k] = x;return A;}Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4 11Matrix MultiplyProblem: Given an m × k array A and a k × n array B,compute the m × n matrix product. E.g.,1 −1 23 1 0×1 23 45 6=8 106 10/** The matrix product of A and B. Undefined if* A and B do not have compatible dimensions,* are not rectangular, or have no elements. */static int[][] mult (int[][] A, int[][] B) {int[][] C = new int[A.length][B[0].length];for (int i = 0; i < A.length; i += 1)for (int j = 0; j < B[0].length; j += 1)for (int k = 0; k < B.length; k += 1)C[i][j] += A[i][k] * B[k][j];return C;}// Where do errors show up?Last modified: Wed Sep 19 01:48:12 2001 CS61B: Lecture #4


View Full Document

Berkeley COMPSCI 61B - Lecture Notes

Documents in this Course
Lab

Lab

4 pages

Matrix

Matrix

3 pages

Numbers

Numbers

14 pages

Lectures

Lectures

12 pages

Project 1

Project 1

24 pages

Exam

Exam

8 pages

Load more
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?