Transcript COSC2007DataStructuresIIintro

COSC 2007 Data Structures II
Dr Dave Goforth
FA 377
[email protected]
(705)675-1151x2316
http://www.cs.laurentian.ca/dgoforth/cosc2007/outline.html
(local)
Course Objectives
•Abstract Data Types (ADTs) for
collections of Objects
•JAVA 5.0 generic Collections classes
•Non-linear data structures that
implement ADTs
•Design of applications using ADTs
Course Organization
•6 programming assignments
36%
due Thursday, 10:30 AM
every two weeks
•1 midterm examination (2 hours) 24%
Tuesday June 26 – 10:00 – 11:55 AM
•1 final examination (3 hours)
40%
• Tutorial? 12:00 – 12:30 after lecture?
Review
•linked structures
•object-oriented implementation concepts
•linear data structures
•recursion
Linked lists - references
•variables of an object type contain
addresses or references to objects
Point p;
p = new Point(5,-2);
p
p
x 5
y -2
Linked lists - nodes
•nodes are objects that contain references
to objects of their own type
class Node
Node n1, n2;
{
n1 = new Node(3,null);
int data;
n2 = new Node(5,n1);
Node next;
}
n1
n2
data 5
next
data 3
next
Doubly-linked lists
Why?
– bi-directional movement in list
Effect on implementation
– maintain one reference to ‘current’ – no
need for ‘previous’ reference
BUT…
– insertion and deletion more complex
Nodes for doubly-linked lists
• prev and next Node references
• current may be only reference into list
current
data
34
data
-5
data
90
dat
next
next
next
nex
prev
prev
prev
pre
Nodes for doubly-linked lists
• head and tail of list identified by null references
current
(head)
data
(tail)
34
data
-5
data
next
next
next
prev
prev
prev
90
Inserting new Node
• before or after current?
• four links to manage
data
34
current
data
-5
data
next
next
next
prev
prev
prev
data
next
prev
14
9
Deleting a node
• current Node or before or after?
• four links to manage
current
?
data
?
?
34
data
-5
data
90
dat
next
next
next
nex
prev
prev
prev
pre
Operations: Special cases
• on empty list
• on list with one Node
• at one end of list
data
next
prev
-8
data
next
prev
23
data
next
prev
91
Object-oriented design
Doubly-linked List methods
operations at current node
-get data, update data
-insert node, delete node
operations on current reference
-move forward, backward, head, tail
operations on list
-iterate
Assignment 1 - text editor
•linked structures
•recursion
•object-oriented implementation concepts
•linear data structures
•testing
Assignment 1 - text editor
Evalulation
•code
•javadoc documentation
•testing
Submission
•web-based automated submission
•May 10, 10:30 AM
• value 6%
The editor – ed, the line editor
•
•
•
text is stored in a doubly-linked list of
Strings (no wrap-around from line to line)
changes to text occur at current line by
commands at console
three kinds of operation:
1. movement to another line
2. changes to text in list of Strings
3. file management
The editor – ed, updated version
• text is displayed in a JFrame
• display is updated as changes occur (still
at the console)
• file management is by JFileChooser
Assignment 1
(local)
Recursion
• problem decomposition
– rewrite problem in terms of a reduced
version of itself
• method structure
– base case
– recursive case
Recursion example
• problem decomposition
– tired old example: factorial
F (n)  n.(n  1).( n  2)...2.1
 n.F (n  1)
• method structure
public static int F(int n)
{
if (n<0) throw new IllegalArgumentException();
if (n>1) return n * F(n-1);
return 1;
}
Recursion in assignment
• no iterative structures can be used in
this assignment
– no “for”
– no “while”
– no “do…while”
• use recursive methods instead
Recursion in assignment - example
public Node getHead()
{
Node at = this;
while (at.prev != null) public
at = at.prev;
{ int
return at;
Node
}
class Node
data;
next,
prev;
}
current = current.getHead();
Recursion in assignment - example
public Node getHead()
{
if (prev == null)
public class Node
return this;
return prev.getHead(); { int data;
}
Node next,
prev;
}
current = current.getHead();
Static and instance methods
current = current.getHead();
Problem: case when current is null
Static version:
current = Node.getHead(current);