Datové struktury obsah přednášky 1. Úvod 2. Třídy Type-wrapper (obalový typ) pro primitivní typy – automatické převody 3. Automatické převody mezi primitivními a obalovými typy 4. Třídy odkazující sama na sebe (self referential) 5. Dynamické přidělování paměti 6. Spojové seznamy 7. Zásobníky 8. Fronty 9. Stromy
1
2
Úvod • statické datové struktury – typ array, jedno vícerozměrné • spojové seznamy – kolekce dat, kde rozšíření / zmenšení seznamu, je provedeno kdykoli za běhu programu
Třídy Type-Wrapper pro primitivní typy (obalový typ) • primitivní typy a objektové typy • na primitivní typy se nedá odkazovat referencí • každý primitivní typ má odpovídající třídu type wrapper – obalovou třídu v balíčku (java.lang) • třídy type-wrapper jsou: – Boolean, Byte, Character, Double, Float, Integer, Long, Short
• třídy type wrapper (obalové třídy) nemohou manipulovat s proměnnými primitivních typů jako s objekty, ale dovolují manipulovat s objekty typových obalových tříd
3
Třídy Type-Wrapper pro primitivní typy (obalový typ) • Každá z type wrapper tříd (obalových tříd) je podtřídou třídy Number • třídy type wrapper jsou final třídy, nemohou mít podtřídy (extends)
4
Automatické převody mezi primitivními a obalovými typy • třídy type wrapper jsou nutné pro ukládání primitivních typů do kolekcí • předchozí verze Javy Integer[] integerArray = new Integer[5]; integerArray[0] = new Integer(10); int value = integerArray[0].intValue();
• Java verze 5.0 Integer[] integerArray = new Integer[5]; integerArray[0] = 10; int value = integerArray[0];
5
6 // drivejsi prirazeni public static void drive() drive() { int i2 = 12; Integer ctyri = new Integer(2 * i2); int i6 = 2*ctyri.intValue 2*ctyri.intValue(); ctyri.intValue(); ... } public static void nyni() nyni() { int i2 = 2; Integer ctyri = 2 * i2; int i6 = 2 + ctyri; ctyri; ... }
Osnova
Třídy Self Referential (třídy odkazující se na své prvky) • obsahují objekt, který odkazuje na jiný objekt stejné třídy class Node { private int data; //datovy atribut private Node nextNode; //referencni atribut public Node(int data) // konstruktor public void setData(int data) //metody - datove atributy public int getData() public void setNext( Node next) //metody – ref. atributy public Node getNext() }
7
8
Třídy odkazující se sami na sebe
15
10
Self-referential-class objects spojené k sobě
9
Dynamické přidělení paměti • vytváření a manipulace s dynamickými datovými strukturami vyžaduje dynamické přidělení paměti • schopnost programu získat za běhu programu paměťový prostor a posléze ho uvolnit (není-li třeba) • Java automaticky čistí paměť od již nepotřebných objektů (nejsou na ně odkazy) Node nodeToAdd = new Node(10);
10
Spojové seznamy • Spojový seznam – Lineární kolekce samoodkazujících tříd (uzlů) – Propojení pomocí odkazů – Uzly mohou být vkládány nebo rušeny kdekoli ve spojovém seznamu – Poslední uzel ukazuje na null (k označení konce seznamu)
11
Spojové seznamy
firstNode
H
lastNode
D
...
Spojový seznam grafická reprezentace
Q
12 // ListNode and List class definitions. definitions. // class to represent one node in a list class ListNode { // package access members; members; List can access these directly Object data; //datovy //datovy atribut ListNode nextNode; nextNode; // referencni atribut // constructor creates a ListNode that refers to object ListNode( ListNode( Object object ) { this( this( object, object, null ); } // end ListNode oneone-argument constructor // constructor creates ListNode that refers to // Object and to next ListNode ListNode( ListNode( Object object, object, ListNode node ) { data = object; object; nextNode = node; node; } // end ListNode twotwo-argument constructor // return reference to data in node Object getObject() getObject() { return data; // return Object in this node } // end method getObject
Osnova Třída ListNode
13 // return reference to next node in list ListNode getNext() getNext() { return nextNode; nextNode; // get next node } // end method getNext } // end class ListNode // class List definition public class List { private ListNode firstNode; firstNode; private ListNode lastNode; lastNode; private String name; name; // string like "list" used in printing // constructor creates empty List with "list" as the name public List() { this( this( "list" ); } // end List nono-argument constructor // constructor creates an empty List with a name public List( String listName ) { name = listName; listName; firstNode = lastNode = null; null; } // end List oneone-argument constructor
Osnova
14 // insert Object at front of List public void insertAtFront( insertAtFront( Object insertItem ) { if ( isEmpty() isEmpty() ) // firstNode and lastNode refer to same object firstNode = lastNode = new ListNode( ListNode( insertItem ); else // firstNode refers to new node firstNode = new ListNode( ListNode( insertItem, insertItem, firstNode ); } // end method insertAtFront // insert Object at end of List public void insertAtBack( insertAtBack( Object insertItem ) { if ( isEmpty() isEmpty() ) // firstNode and lastNode refer to same Object firstNode = lastNode = new ListNode( ListNode( insertItem ); else // lastNode's lastNode's nextNode refers to new node lastNode = lastNode. lastNode.nextNode = new ListNode( ListNode( insertItem ); } // end method insertAtBack // remove first node from List public Object removeFromFront() removeFromFront() throws EmptyListException { if ( isEmpty() isEmpty() ) // throw exception if List is empty throw new EmptyListException( EmptyListException( name ); Object removedItem = firstNode.data; firstNode.data; // retrieve data being removed
Osnova
15 // update references firstNode and lastNode if ( firstNode == lastNode ) firstNode = lastNode = null; null; else firstNode = firstNode. firstNode.nextNode; nextNode; return removedItem; removedItem; // return removed node data } // end method removeFromFront // remove last node from List public Object removeFromBack() removeFromBack() throws EmptyListException { if ( isEmpty() isEmpty() ) // throw exception if List is empty throw new EmptyListException( EmptyListException( name ); Object removedItem = lastNode.data; lastNode.data; // retrieve data being removed // update references firstNode and lastNode if ( firstNode == lastNode ) firstNode = lastNode = null; null; else // locate new last node { ListNode current = firstNode; firstNode; // loop while current node does not refer to lastNode while ( current. current.nextNode != lastNode ) current = current. current.nextNode; nextNode; lastNode = current; current; // current is new lastNode current. current.nextNode = null; null; } // end else
Osnova
16 return removedItem removedItem; ; // return removed node data } // end method removeFromBack // determine whether list is empty public boolean isEmpty() isEmpty() { return firstNode == null; null; // return true if List is empty } // end method isEmpty // output List contents public void print() print() { if ( isEmpty() isEmpty() ) { System. System.out. out.printf( printf( "Empty "Empty %s\ %s\n", name ); return; return; } // end if System. "The The %s is: System.out. out.printf( printf( " is: ", name ); ListNode current = firstNode; firstNode; // while not at end of list, output current node's node's data while ( current != null ) { System. System.out. out.printf( printf( "%s ", current.data current.data ); current = current. current.nextNode; nextNode; } // end while System. "\ \n" ); System.out. out.println( println( " } // end method print } // end class List
Osnova
17 // Class EmptyListException definition. definition. public class EmptyListException extends RuntimeException { // nono-argument constructor public EmptyListException() EmptyListException() { this( this( "List" ); // call other EmptyListException constructor } // end EmptyListException nono-argument constructor // oneone-argument constructor public EmptyListException( EmptyListException( String name ) { super( name + " is empty" empty" ); // call superclass constructor } // end EmptyListException oneone-argument constructor } // end class EmptyListException
Osnova Třída EmptyException
18 // ListTest class to demonstrate List capabilities. capabilities. public class ListTest { public static void main( main( String args[] args[] ) { List list = new List(); // create the List container // insert integers in list list.insertAtFront list.insertAtFront( insertAtFront( -1 ); list.print list.print(); print(); list.insertAtFront list.insertAtFront( insertAtFront( 0 ); list.print list.print(); print(); list.insertAtBack list.insertAtBack( insertAtBack( 1 ); list.print list.print(); print(); list.insertAtBack list.insertAtBack( insertAtBack( 5 ); list.print list.print(); print(); // remove objects from list; print after each removal try { Object removedObject = list.removeFromFront list.removeFromFront(); removeFromFront(); System. System.out. out.printf( printf( "%s removed\ removed\n", removedObject ); list.print list.print(); print(); removedObject = list.removeFromFront list.removeFromFront(); removeFromFront(); System. System.out. out.printf( printf( "%s removed\ removed\n", removedObject ); list.print list.print(); print();
Osnova Třída ListTest
19 removedObject = list.removeFromBack list.removeFromBack(); removeFromBack(); System. System.out. out.printf( printf( "%s removed\ removed\n", removedObject ); list.print list.print(); print(); removedObject = list.removeFromBack list.removeFromBack(); removeFromBack(); System. System.out. out.printf( printf( "%s removed\ removed\n", removedObject ); list.print list.print(); print(); } // end try catch ( EmptyListException emptyListException ) { emptyListException. emptyListException.printStackTrace(); printStackTrace(); } // end catch } // end main } // end class ListTest
Osnova
20
Osnova
The list is: -1 The list is: 0
-1
The list is: 0
-1
1
The list is: 0
-1
1
1
5
0 removed The list is: -1 -1 removed The list is: 1 5 removed The list is: 1 1 removed Empty list
5
5
21
Spojové seznamy (a)
firstNode 7
11
new Listnode 12
(b)
firstNode 7
new Listnode 12
11
22
Spojové seznamy (a)
12
(b)
lastNode
firstNode
7
lastNode
firstNode
12
11
7
11
new Listnode
5
new Listnode
5
23
Spojové seznamy
(a)
firstNode
12
(b)
lastNode
7
11
firstNode
12
removeItem
5
lastNode
7
11
5
24
Spojové seznamy
(a)
12
(b)
lastNode
firstNode
7
11
firstNode
12
removeItem
5
lastNode
7
11
5
25
Zásobníky - stacks • Zásobník – Omezená verze spojového seznamu • Přidává a odstraňuje uzly pouze z vrcholu zásobníku – Metoda push přidává uzel na vrchol zásobníku – Metoda pop odstraňuje uzel z vrcholu zásobníku
26 // Derived from class List. public class StackInheritance extends List { // nono-argument constructor public StackInheritance() StackInheritance() { super( "stack "stack" stack" ); } // end StackInheritance nono-argument constructor // add object to stack public void push( push( Object object ) { insertAtFront( insertAtFront( object ); } // end method push // remove object from stack public Object pop() throws EmptyListException { return removeFromFront(); removeFromFront(); } // end method pop } // end class StackInheritance
Osnova Zásobník dědičnost
27 // Class StackInheritanceTest. StackInheritanceTest. import com. com.deitel.jhtp6.ch17. deitel.jhtp6.ch17.StackInheritance .jhtp6.ch17.StackInheritance; StackInheritance; import com. com.deitel.jhtp6.ch17. deitel.jhtp6.ch17.EmptyListException .jhtp6.ch17.EmptyListException; EmptyListException;
Osnova Třída ZasobnikTest
public class StackInheritanceTest { public static void main( main( String args[] args[] ) { StackInheritance stack = new StackInheritance(); StackInheritance(); // use push method stack. stack.push( push( -1 ); stack. stack.print(); print(); stack. stack.push( push( 0 ); stack. stack.print(); print(); stack. stack.push( push( 1 ); stack. stack.print(); print(); stack. stack.push( push( 5 ); stack. stack.print(); print(); // remove items from stack try { Object removedObject = null; null;
28 while ( true ) { removedObject = stack.pop(); stack.pop(); // use pop method System. System.out. out.printf( printf( "%s popped\ popped\n", removedObject ); stack. stack.print(); print(); } // end while } // end try catch ( EmptyListException emptyListException ) { emptyListException. emptyListException.printStackTrace(); printStackTrace(); } // end catch } // end main } // end class StackInheritanceTest
Osnova
29 The stack is: -1
Osnova
The stack is: 0 -1 The stack is: 0
0
-1
The stack is: 5
1
0
5 popped The stack is: 1
0
-1
1 popped The stack is: 0
-1
-1
0 popped The stack is: -1 -1 popped Empty stack struktury.EmptyListException: struktury.EmptyListException: stack is empty at struktury.List.removeFromFront(List.java:79) at struktury.StackInheritance.pop(StackInheritance.java:20) at struktury.StackInheritanceTest.main (StackInheritanceTest.java:26) (StackInheritanceTest.java:26)
30 // Class StackComposition definition with composed List object. object. public class StackComposition { private List stackList; stackList; //datovy //datovy atribut seznam // nono-argument constructor public StackComposition() StackComposition() { stackList = new List( "stack "stack" stack" ); } // end StackComposition nono-argument constructor // add object to stack public void push( push( Object object ) { stackList. stackList.insertAtFront( insertAtFront( object ); } // end method push // remove object from stack public Object pop() throws EmptyListException { return stackList. stackList.removeFromFront(); removeFromFront(); } // end method pop // determine if stack is empty public boolean isEmpty() isEmpty() { return stackList. stackList.isEmpty(); isEmpty(); } // end method isEmpty
Osnova Zásobník skládání
31 // output stack contents public void print() print() { stackList. stackList.print(); print(); } // end method print } // end class StackComposition
Osnova
32
Fronty queues • Fronta – Podobná frontě ze supermarketu u pokladny – Uzly jsou vkládány pouze na konec (tail) • Metoda enqueue
– Uzly jsou odstraňovány z čela fronty (head of the front) • Metoda dequeue
33 // Class Queue. Queue. public class Queue { private List queueList; queueList; // datovy atribut seznam // nono-argument constructor public Queue() Queue() { queueList = new List( "queue queue" " ); "queue } // end Queue nono-argument constructor // add object to queue public void enqueue( enqueue( Object object ) { queueList. queueList.insertAtBack( insertAtBack( object ); } // end method enqueue // remove object from queue public Object dequeue() dequeue() throws EmptyListException { return queueList. queueList.removeFromFront(); removeFromFront(); } // end method dequeue // determine if queue is empty public boolean isEmpty() isEmpty() { return queueList. queueList.isEmpty(); isEmpty(); } // end method isEmpty
Osnova Fronta skládání
34 // output queue contents public void print() print() { queueList. queueList.print(); print(); } // end method print } // end class Queue
Osnova
35 // Class QueueTest. QueueTest. import com. com.deitel.jhtp6.ch17. deitel.jhtp6.ch17.Queue .jhtp6.ch17.Queue; Queue; import com. com.deitel.jhtp6.ch17. deitel.jhtp6.ch17.EmptyListException .jhtp6.ch17.EmptyListException; EmptyListException;
Osnova Třída FrontaTest
public class QueueTest { public static void main( main( String args[] args[] ) { Queue queue = new Queue(); Queue(); // use enqueue queue. queue.enqueue( enqueue( queue. queue.print(); print(); queue. queue.enqueue( enqueue( queue. queue.print(); print(); queue. queue.enqueue( enqueue( queue. queue.print(); print(); queue. queue.enqueue( enqueue( queue. queue.print(); print();
method -1 ); 0 ); 1 ); 5 );
36 // remove objects from queue try { Object removedObject = null; null; while ( true ) { removedObject = queue. queue.dequeue(); dequeue(); // use dequeue method System. System.out. out.printf( printf( "%s dequeued\ dequeued\n", removedObject ); queue. queue.print(); print(); } // end while } // end try catch ( EmptyListException emptyListException ) { emptyListException. emptyListException.printStackTrace(); printStackTrace(); } // end catch } // end main } // end class QueueTest
Osnova
37
The queue is: -1
The queue is: -1
Osnova 0
The queue is: true -1
The queue is: -1
0
1
0
1
5
-1 dequeued The queue is: 0
1
5
0 dequeued The queue is: 1
5
1 dequeued The queue is: 5
5 dequeued Empty queue struktury.EmptyListException: struktury.EmptyListException: queue is empty at struktury.List.removeFromFront(List.java:79) at struktury.Queue.dequeue(Queue.java:22) at struktury.QueueTest.main(QueueTest.java:26)
38
Stromy trees • Strom – Nelineární, dvoudimenzionální datová struktura se speciálními vlastnostmi • (spojové seznamy, zásobníky, fronty jsou lineární datové struktury)
– Uzly stromu obsahují dva nebo více odkazů (referencí) – Kořenový uzel (Root node) je první uzel (počátek) – Každá reference odkazuje na dítě (child) • • • •
Levé dítě je prvním uzlem v levém podstromu (subtree) Pravé dítě je prvním uzlem v pravém podstromu Děti v uzlech se nazývají sourozenci (siblings) Uzly, které nemají pokračování (děti) jsou uzly listů (leaf nodes)
39
Stromy - pokračování • Binary search tree – Speciální řazení uzlů – bez duplikátů (hodnot uzlů) • Hodnoty v levých podstromech jsou menší než hodnoty v pravých podstromech
– Inorder traversal - průchod • Prochází levý podstrom, získá hodnotu uzlu, prochází pravý podstrom
– Preorder traversal - průchod • Získá datový atribut uzlu, prochází levý podstrom, prochází pravý podstrom
– Postorder traversal - průchod • Prochází levý podstrom, prochází pravý podstrom, získá datový atribut (hodnotu) uzlu
40
Stromy - pokračování
B
A
D
C
Binární strom grafická reprezentace.
41
Stromy - pokračování
47
25
11
7
17
77
43
31 44
65
93
68
Binary search tree obsahující 12 hodnot.
42 // Definition of class TreeNode and class Tree. Tree. // class TreeNode definition class TreeNode { // package access members TreeNode leftNode; leftNode; // left node int data; // node value TreeNode rightNode; rightNode; // right node // constructor initializes data and makes this a leaf node public TreeNode( TreeNode( int nodeData ) { data = nodeData; nodeData; leftNode = rightNode = null; null; // node has no children } // end TreeNode nono-argument constructor // locate insertion point and insert new node; node; ignore duplicate values public void insert( int insertValue ) { // insert in left subtree if ( insertValue < data ) { // insert new TreeNode if ( leftNode == null ) leftNode = new TreeNode( TreeNode( insertValue ); else // continue traversing left subtree leftNode.insert( leftNode.insert( insertValue ); } // end if
Osnova
43 else if ( insertValue > data ) // insert in right subtree { // insert new TreeNode if ( rightNode == null ) rightNode = new TreeNode( TreeNode( insertValue ); else // continue traversing right subtree rightNode.insert( rightNode.insert( insertValue ); } // end else if } // end method insert } // end class TreeNode // class Tree definition public class Tree { private TreeNode root; root; // constructor initializes an empty Tree of integers public Tree() Tree() { root = null; null; } // end Tree nono-argument constructor // insert a new node in the binary search public void insertNode( insertNode( int insertValue ) { if ( root == null ) root = new TreeNode( TreeNode( insertValue ); else root.insert( root.insert( insertValue ); // call } // end method insertNode
tree
// create the root node here the insert method
Osnova
44 // begin preorder traversal public void preorderTraversal() preorderTraversal() { preorderHelper( preorderHelper( root ); } // end method preorderTraversal // recursive method to perform preorder traversal private void preorderHelper( preorderHelper( TreeNode node ) { if ( node == null ) return; return; System. System.out. out.printf( printf( "%d ", node.data node.data ); // output node data preorderHelper( preorderHelper( node. node.leftNode ); // traverse left subtree preorderHelper( // traverse right subtree preorderHelper( node. node.rightNode ); } // end method preorderHelper // begin inorder traversal public void inorderTraversal() inorderTraversal() { inorderHelper( inorderHelper( root ); } // end method inorderTraversal
Osnova
45 // recursive method to perform inorder traversal private void inorderHelper( inorderHelper( TreeNode node ) { if ( node == null ) return; return; inorderHelper( inorderHelper( node. node.leftNode ); // System. System.out. out.printf( printf( "%d ", node.data node.data ); // inorderHelper( inorderHelper( node. node.rightNode ); // } // end method inorderHelper
traverse left subtree output node data traverse right subtree
// begin postorder traversal public void postorderTraversal() postorderTraversal() { postorderHelper( postorderHelper( root ); } // end method postorderTraversal // recursive method to perform postorder traversal private void postorderHelper( postorderHelper( TreeNode node ) { if ( node == null ) return; return; postorderHelper( postorderHelper( node. node.leftNode ); // traverse left subtree postorderHelper( // traverse right subtree postorderHelper( node. node.rightNode ); System. System.out. out.printf( printf( "%d ", node.data node.data ); // output node data } // end method postorderHelper } // end class Tree
Osnova
46 // This program tests class Tree. Tree. import java. java.util. util.Random; Random; public class TreeTest { public static void main( main( String args[] args[] ) { Tree tree = new Tree(); Tree(); int value; value; Random randomNumber = new Random(); Random(); System. System.out. out.println( println( "Inserting "Inserting the following values: values: " ); // insert 10 random integers from 0-99 in tree for ( int i = 1; i <= 10; i++ ) { value = randomNumber. randomNumber.nextInt( nextInt( 100 ); System. System.out. out.print( print( value + " " ); tree. tree.insertNode( insertNode( value ); } // end for System. System.out. out.println ( "\ "\n\nPreorder traversal" traversal" ); tree. tree.preorderTraversal(); preorderTraversal(); // perform preorder traversal of tree System. System.out. out.println ( "\ "\n\nInorder traversal" traversal" ); tree. tree.inorderTraversal(); inorderTraversal(); // perform inorder traversal of tree
Osnova Třída TreeTest
47
Osnova System. System.out. out.println ( "\ "\n\nPostorder traversal" traversal" ); tree. tree.postorderTraversal(); postorderTraversal(); // perform postorder traversal of tree System. System.out. out.println(); println(); } // end main } // end class TreeTest
Inserting the following values: 92 73 77 16 30 30 94 89 26 80 Preorder traversal 92 73 16 30 26 77 89 80 94 Inorder traversal 16 26 30 73 77 80 89 92 94 Postorder traversal 26 30 16 80 89 77 73 94 92
System.out.println ( "\n\nPostorder traversal" ); tree.postorerTraversal(); // perform postorder traversal of tree System.out.println(); } // end main } // end class TreeTest
