编程代考 CS61B Lecture #4: Simple Pointer Manipulation Recreation Prove that for eve

CS61B Lecture #4: Simple Pointer Manipulation Recreation Prove that for every acute angle α > 0,
tan α + cot α ≥ 2
Announcements
• Today: More pointer hacking.

• Handing in labs and homework: We’ll be lenient about accepting late homework and labs for lab1, lab2, and hw0. Just get it done: part of the point is getting to understand the tools involved. We will not accept submissions by email.
• We will feel free to interpret the absence of a central repository for you or a lack of a lab1 submission from you as indicating that you intend to drop the course.
• HW1 to be released tonight (roughly).
• Project 0 to be released Friday.
Last modified: Mon Feb 3 16:54:41 2020 CS61B: Lecture #4 1

Small Test of Understanding
• In Java, the keyword final in a variable declaration means that the
variable’s value may not be changed after the variable is initialized. • Is the following class valid?
public class Issue {
private final IntList aList = new IntList(0, null);
public void modify(int k) { this.aList.head = k;
Why or why not?
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 2

Small Test of Understanding
• In Java, the keyword final in a variable declaration means that the
variable’s value may not be changed after the variable is initialized. • Is the following class valid?
public class Issue {
private final IntList aList = new IntList(0, null);
public void modify(int k) { this.aList.head = k;
Why or why not?
Answer: This is valid. Although modify changes the head variable of the object pointed to by aList, it does not modify the contents of aList itself (which is a pointer).
Last modified: Mon Feb 3 16:54:41 2020 CS61B: Lecture #4 3

return null; else {
P.head += n;
P.tail = dincrList(P.tail, n);
Destructive Incrementing
Destructive solutions may modify objects in the original list to save time or space:
/** Destructively add N to P’s items. */
static IntList dincrList(IntList P, int n) { if (P == null)
X = IntList.list(3, 43, 56);
/* IntList.list from HW #1 */
Q = dincrList(X, 2);
/** Destructively add N to L’s items. */
static IntList dincrList(IntList L, int n) {
// ’for’ can do more than count!
for (IntList p = L; p != null; p = p.tail)
p.head += n;
return L; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 4

Another Example: Non-destructive List Deletion
If L is the list [2, 1, 2, 9, 2], we want removeAll(L,2) to be the new list [1, 9].
/** The list resulting from removing all instances of X from L * non-destructively. */
static IntList removeAll(IntList L, int x) { if (L == null)
return /*( null with all x’s removed )*/; else if (L.head == x)
return /*( L with all x’s removed (L!=null, L.head==x) )*/; else
return /*( L with all x’s removed (L!=null, L.head!=x) )*/; }
Last modified: Mon Feb 3 16:54:41 2020 CS61B: Lecture #4 11

Another Example: Non-destructive List Deletion
If L is the list [2, 1, 2, 9, 2], we want removeAll(L,2) to be the new list [1, 9].
/** The list resulting from removing all instances of X from L * non-destructively. */
static IntList removeAll(IntList L, int x) { if (L == null)
return null;
else if (L.head == x)
return /*( L with all x’s removed (L!=null, L.head==x) )*/; else
return /*( L with all x’s removed (L!=null, L.head!=x) )*/; }
Last modified: Mon Feb 3 16:54:41 2020 CS61B: Lecture #4 12

Another Example: Non-destructive List Deletion
If L is the list [2, 1, 2, 9, 2], we want removeAll(L,2) to be the new list [1, 9].
/** The list resulting from removing all instances of X from L * non-destructively. */
static IntList removeAll(IntList L, int x) { if (L == null)
return null;
else if (L.head == x)
return removeAll(L.tail, x); else
return /*( L with all x’s removed (L!=null, L.head!=x) )*/; }
Last modified: Mon Feb 3 16:54:41 2020 CS61B: Lecture #4 13

Another Example: Non-destructive List Deletion
If L is the list [2, 1, 2, 9, 2], we want removeAll(L,2) to be the new list [1, 9].
/** The list resulting from removing all instances of X from L * non-destructively. */
static IntList removeAll(IntList L, int x) { if (L == null)
return null;
else if (L.head == x)
return removeAll(L.tail, x); else
return new IntList(L.head, removeAll(L.tail, x)); }
Last modified: Mon Feb 3 16:54:41 2020 CS61B: Lecture #4 14

Iterative Non-destructive List Deletion
Same as before, but use front-to-back iteration rather than recursion.
/** The list resulting from removing all instances * of X from L non-destructively. */
static IntList removeAll(IntList L, int x) { IntList result, last;
result = last = null; for(;L!=null;L=L.tail) {
if (x == L.head)
else if (last == null)
result = last = new IntList(L.head, null);
last = last.tail = new IntList(L.head, null);
return result; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 15

Iterative Non-destructive List Deletion
Same as before, but use front-to-back iteration rather than recursion.
/** The list resulting from removing all instances * of X from L non-destructively. */
static IntList removeAll(IntList L, int x) {
IntList result, last;
result = last = null; for(;L!=null;L=L.tail) { L:
if (x == L.head)
else if (last == null)
result = last = new IntList(L.head, null);
last = last.tail = new IntList(L.head, null);
return result; }
P: 2 1 2 9 result:
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 16
removeAll (P, 2)

Iterative Non-destructive List Deletion
Same as before, but use front-to-back iteration rather than recursion.
/** The list resulting from removing all instances * of X from L non-destructively. */
static IntList removeAll(IntList L, int x) {
IntList result, last;
result = last = null; for(;L!=null;L=L.tail) { L:
if (x == L.head)
else if (last == null)
result = last = new IntList(L.head, null);
last = last.tail = new IntList(L.head, null);
return result; }
P: 2 1 2 9 result:
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 17
removeAll (P, 2)
P does not change!

Iterative Non-destructive List Deletion
Same as before, but use front-to-back iteration rather than recursion.
/** The list resulting from removing all instances * of X from L non-destructively. */
static IntList removeAll(IntList L, int x) {
IntList result, last;
result = last = null; for(;L!=null;L=L.tail) { L:
if (x == L.head)
else if (last == null)
result = last = new IntList(L.head, null);
last = last.tail = new IntList(L.head, null);
return result; }
P: 2 1 2 9 result: 1
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 18
removeAll (P, 2)
P does not change!

Iterative Non-destructive List Deletion
Same as before, but use front-to-back iteration rather than recursion.
/** The list resulting from removing all instances * of X from L non-destructively. */
static IntList removeAll(IntList L, int x) {
IntList result, last;
result = last = null; for(;L!=null;L=L.tail) { L:
if (x == L.head)
else if (last == null)
result = last = new IntList(L.head, null);
last = last.tail = new IntList(L.head, null);
return result; }
P: 2 1 2 9 result: 1
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 19
removeAll (P, 2)
P does not change!

Iterative Non-destructive List Deletion
Same as before, but use front-to-back iteration rather than recursion.
/** The list resulting from removing all instances * of X from L non-destructively. */
static IntList removeAll(IntList L, int x) {
IntList result, last;
result = last = null; for(;L!=null;L=L.tail) { L:
if (x == L.head)
else if (last == null)
result = last = new IntList(L.head, null);
last = last.tail = new IntList(L.head, null);
return result; }
P: 2 1 2 9 result: 1
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 20
removeAll (P, 2)
P does not change!

Iterative Non-destructive List Deletion
Same as before, but use front-to-back iteration rather than recursion.
/** The list resulting from removing all instances * of X from L non-destructively. */
static IntList removeAll(IntList L, int x) {
IntList result, last;
result = last = null; for(;L!=null;L=L.tail) { L:
if (x == L.head)
else if (last == null)
result = last = new IntList(L.head, null);
last = last.tail = new IntList(L.head, null);
return result; }
P: 2 1 2 9
removeAll (P, 2)
P does not change!
result: last:
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 21

Iterative Non-destructive List Deletion
Same as before, but use front-to-back iteration rather than recursion.
/** The list resulting from removing all instances * of X from L non-destructively. */
static IntList removeAll(IntList L, int x) {
IntList result, last;
result = last = null; for(;L!=null;L=L.tail) { L:
if (x == L.head)
else if (last == null)
result = last = new IntList(L.head, null);
last = last.tail = new IntList(L.head, null);
return result; }
P: 2 1 2 9
removeAll (P, 2)
P does not change!
result: last:
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 22

Destructive Deletion
: Original 1231101
: after Q = dremoveAll (Q,1)
/** The list resulting from removing all instances of X from L. * The original list may be destroyed. */
static IntList dremoveAll(IntList L, int x) { if (L == null)
return /*( null with all x’s removed )*/; else if (L.head == x)
return /*( L with all x’s removed (L != null) )*/; else {
/*{ Remove all x’s from L’s tail. }*/;
return L; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 23

Destructive Deletion
: Original 1231101
: after Q = dremoveAll (Q,1)
/** The list resulting from removing all instances of X from L. * The original list may be destroyed. */
static IntList dremoveAll(IntList L, int x) { if (L == null)
return null;
else if (L.head == x)
return /*( L with all x’s removed (L != null) )*/; else {
/*{ Remove all x’s from L’s tail. }*/;
return L; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 27

Destructive Deletion
: Original 1231101
: after Q = dremoveAll (Q,1)
/** The list resulting from removing all instances of X from L. * The original list may be destroyed. */
static IntList dremoveAll(IntList L, int x) { if (L == null)
else if (L.head == x)
return dremoveAll(L.tail, x); else {
/*{ Remove all x’s from L’s tail. }*/;
return L; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 28

Destructive Deletion
: Original 1231101
: after Q = dremoveAll (Q,1)
/** The list resulting from removing all instances of X from L. * The original list may be destroyed. */
static IntList dremoveAll(IntList L, int x) { if (L == null)
else if (L.head == x)
return dremoveAll(L.tail, x); else {
L.tail = dremoveAll(L.tail, x);
return L; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 29

Iterative Destructive Deletion
/** The list resulting from removing all X’s from L * destructively. */
static IntList dremoveAll(IntList L, int x) { IntList result, last;
result = last = null;
while (L != null) {
IntList next = L.tail; if (x != L.head) {
if (last == null)
result = last = L;
last = last.tail = L;
L.tail = null;
return result; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 30

Iterative Destructive Deletion
/** The list resulting from removing all X’s from L
* destructively. */
static IntList dremoveAll(IntList L, int x) { IntList result, last;
result = last = null;
while (L != null) {
IntList next = L.tail; if (x != L.head) {
if (last == null)
result = last = L;
P: 2129 result:
next: P = dremoveAll (P, 2)
last = last.tail = L;
L.tail = null;
return result; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 31

Iterative Destructive Deletion
/** The list resulting from removing all X’s from L
* destructively. */
static IntList dremoveAll(IntList L, int x) { IntList result, last;
result = last = null;
while (L != null) {
IntList next = L.tail; if (x != L.head) {
if (last == null)
result = last = L;
P: 2129 result:
next: P = dremoveAll (P, 2)
last = last.tail = L;
L.tail = null;
return result; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 32

Iterative Destructive Deletion
/** The list resulting from removing all X’s from L
* destructively. */
static IntList dremoveAll(IntList L, int x) { IntList result, last;
result = last = null;
while (L != null) {
IntList next = L.tail; if (x != L.head) {
if (last == null)
result = last = L;
P: 2129 result:
next: P = dremoveAll (P, 2)
last = last.tail = L;
L.tail = null;
return result; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 33

Iterative Destructive Deletion
/** The list resulting from removing all X’s from L
* destructively. */
static IntList dremoveAll(IntList L, int x) { IntList result, last;
result = last = null;
while (L != null) {
IntList next = L.tail; if (x != L.head) {
if (last == null)
result = last = L;
P: 2129 result:
next: P = dremoveAll (P, 2)
last = last.tail = L;
L.tail = null;
return result; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 34

Iterative Destructive Deletion
/** The list resulting from removing all X’s from L
* destructively. */
static IntList dremoveAll(IntList L, int x) { IntList result, last;
result = last = null;
while (L != null) {
IntList next = L.tail; if (x != L.head) {
if (last == null)
result = last = L;
P: 2129 result:
next: P = dremoveAll (P, 2)
last = last.tail = L;
L.tail = null;
return result; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 35

Iterative Destructive Deletion
/** The list resulting from removing all X’s from L
* destructively. */
static IntList dremoveAll(IntList L, int x) { IntList result, last;
result = last = null;
while (L != null) {
IntList next = L.tail; if (x != L.head) {
if (last == null)
result = last = L;
P: 2129 result:
next: P = dremoveAll (P, 2)
last = last.tail = L;
L.tail = null;
return result; }
Last modified: Mon Feb 3 16:54:41 2020
CS61B: Lecture #4 36

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts