Datové struktury a algoritmy Část 4
Abstraktní datové typy Petr Felkel
Data structures and algorithms Part 4
Abstract data types Petr Felkel
Abstraktní datové typy Zdůrazňují vnější chování datové struktury Input
Control Output BLACK BOX Emphasize outer behavior of the data structure DSA
3 / 82
Abstraktní datové typy • Abstrahují od jak?
• •
Jak jsou data zobrazena v paměti… Jak jsou prováděny operace…
• Zdůrazňují co?
•
DSA
Co s nimi operace s daty provádějí nezávisle na konkrétní implementaci
4 / 82
Abstract data types • Abstract from: How?
• •
How is the data stored in memory? How are the operations executed?
• Emphasize: What?
•
DSA
What do the operations do with the data (independent of any particular implementation)? 5 / 82
Example – Queue (Fronta)
Čelo Front DSA
6 / 82
Queue (Fronta) • FIFO = First-in, First-out • Access to front • Insert to back
DSA
7 / 82
Abstract Queue (Fronta) Operations: Variables: e…element, Q…queue init(), front( Q ), delFront( Q ), insLast( e, Q ) Axioms: 1. init() returns a queue 2. front( insLast( e, init() )) = e 3. delFront( insLast( e, init() ) ) = init() 4. front( insLast( e, insLast( f, Q ) )) = front( insLast( f, Q ) ) 5. delFront( insLast( e, insLast( f, Q ) )) = insLast( e, delFront( insLast( f, Q ) )) DSA
8 / 82
Abstract Queue (Fronta) Expression is a way of construction of data object by means of a sequence of operations
Ex: insLast(4, insLast(3, insLast(2, init() ))) represents a queue
4 3 2
front(insLast(4, insLast(3, insLast(2, init() )))) represents its first element (head), … 2 DSA
9 / 82
Abstract Queue (Fronta) 1. init() Returns a queue Is informally “empty” Must not be formally defined
DSA
10 / 82
Abstract Queue (Fronta) 2. front( insLast( e, init() )) = e
= is a “rewrite operation” axiom A=B means instead A, write B Ex: front( insLast( 99, init() )) means 99
DSA
11 / 82
Abstract Queue (Fronta) 3. delFront( insLast( e, init() )) = init() Axioms
allow reduction of expressions
Ex. delFront( insLast( 6, init() )) means init() DSA
12 / 82
Abstract Queue (Fronta) 4. front( insLast( e, insLast( f, Q ) )) = front( insLast( f, Q ) ) Ex: front( insLast( 11, insLast( 5, init() ))) means [according to axiom 4]
front( insLast( 5, init() )) means [ax. 2]
5
DSA
13 / 82
Abstract Queue (Fronta) 5. delFront( insLast( e, insLast( f, Q ) )) = insLast( e, delFront( insLast( f, Q ) )) Ex: delFront( insLast( 8, insLast( 6, init() ))) means [according to axiom 5]
insLast( 8, delFront( insLast( 6, init() ))) means [ax. 3]
insLast( 8, init() ) DSA
14 / 82
Abstract Queue (Fronta) And what to do with: front( init() )
?
delFront( init() )
?
Behavior is in the queue undefined!
• Add error states 6. error_empty_queue(Q) = Q error_empty_elem() = e 7. front( init() ) = error_empty_elem()
• Ignore 8. delFront( init() ) = init() DSA
15 / 82
Abstract Queue (Fronta) complete init()
returns a queue
Variables: e…element, Q…queue
front( init() ) = error_empty_elem() front( insLast( e, init() )) = e front( insLast( e, insLast( f, Q ) )) = front( insLast( f, Q ) ) delFront( init() ) = init() delFront( insLast( e, init() ) ) = init() delFront( insLast( e, insLast( f, Q ) )) = insLast( e, delFront( insLast( f, Q ) )) error_empty_queue(Q) = Q DSA
16 / 82
Abstract Queue - extensions Variables: e…element, Q…queue
empty( init() ) = true empty( insLast( e, Q )) = false length( init() ) = 0 length( insLast( e, Q ) ) = succ( length( Q ) )
…
DSA
17 / 82
Some theory…
DSA
18 / 82
Abstraktní datový typ Abstraktní datový typ (ADT) je množina druhů a příslušných operací, které jsou přesně specifikovány. Je nezávislý na konkrétní implementaci. Abstract data type is a set of data sorts and associated operations that are precisely specified independent of any particular implementation. [PEB, nist.gov] DSA
19 / 82
Abstraktní datový typ • SYNTAXE
… signatura
= deklarace druhů
•
Jména oborů hodnot
+ deklarace operací
• • •
Jména operací Druhy (a pořadí) argumentů operací Druh výsledku
• SÉMANTIKA
… axiomy
= popis vlastností operací! DSA
20 / 82
Abstract data type • SYNTAX
… signature
= declaration of sorts
•
Names of scopes of values
+ declaration of operations
• • •
Names of operations Sorts (and order of) arguments of operations Sort of the result
• SEMANTICS
… axioms
= descritption of the operations properties! DSA
21 / 82
Abstract Queue SIGNATURE Signature as a diagram
init
Queue Elem
empty insLast Bool
delFront front error_empty_queue
DSA
22 / 82
Abstract Queue SIGNATURE Signature in symbols init: -> Queue insLast(_,_): Elem,Queue -> Queue empty(_): Queue -> Bool front(_): Queue -> Elem delFront(_): Queue -> Queue
DSA
23 / 82
Why syntax not enough? Example: Interval {1, 2, 3, 4, 5, ..., 11, 12} a) month_in_year b) natural_number_from_interval_1_až_12 BUT! Operation successor (12)
DSA
a) 1
for month_in_year
b) undefined
for number_from_interval
24 / 82
Implementation From Abstract Data Type to Data Structure
DSA
25 / 82
Data structure Data structure = a realization of ADT 1. Choose data type B for implementation of A …. [integer / interval 1..12] 2. Choose representation of objects of type A by means of objects of type B .… [1..January, 2..February,…] 3. Code the operations on A by means of operations of B DSA
26 / 82
Queue implementation In Array Circular
0 1
2
3
4
5
A D B
0 1
3
A D B
or
last
2
first
SIZE-1
4
5
=
A
last SIZE-1
In Dynamic Memory front last
DSA
A
D
B
27 / 82
B
Linear
D
Example – SPECIFIC Queue Interface (Syntax): Class Queue
Co
ed up l
t og
e
rw th e
ith
Implementation:
{ int _size; Elem elems[MAX_SIZE];
= public: Queue
init();
Elem front(); Queue delFront(); Queue insLast( Elem elem ); bool empty(); … }
DSA
28 / 82
Specific Queue x Abstract Queue Implementation bool empty() { return (_size == 0) }; or bool empty() { return (_front == null ) }; or bool empty() { return (_front == _last ) };
DSA
Axioms
vars: Elem e; Queue q; eqns: empty( init ) = true empty( insLast( e, q )) = false
29 / 82
Specific Queue x Abstract Queue Implementation
Axioms
Elem front(){ if(_front == null ) error; else return ( _front->val ) };
front( init ) = error_empty_elem
or Elem front() { if(_frontIdx == _lastIdx ) error; else return( elems[_frontIdx] ) };
front( insLast( e, q )) = if( empty( q )) then e else front( q ) Or front( insLast( e, init() )) = e front( insLast( e, insLast( f, Q ) )) = front( insLast( f, Q ) )
Details later on DSA
30 / 82
Queue – in an Array Elem queue ::front(void) { if( last == 0 ) return error_empty_elem(); else return array[front]; }
void queue::delFront(void) { if( last != 0) { //!empty() { last--; for(int i=0; i
31 / 82
Queue – in Dynamic Mem. Elem queue ::front(void) { if( last != null ) return error_empty_elem(); else return front->val; }
void queue::delFront(void) { if( first != null) { //!empty() delItem Item *delItem = first; front first = first.next; delete delItem; A D B last } } DSA
32 / 82
E
Queue – in Dynamic Mem. void queue::insLast( elem e ) { Item *newItem = new Item; newItem->val = e; front newItem->next = null; last.next = newItem; last A last = newItem; }
newItem
D
B
E
bool queue ::empty(void) // empty(): Queue -> Bool { if( last == NULL ) return true; else return false; } DSA
33 / 82
Fronta – Shrnutí • úlohy hromadné obsluhy • FIFO = First-in, First-out kdo dřív přijde, ten dřív mele
• přístup pouze k prvnímu prvku (front) • vkládání pouze na konec (back) • homogenní, lineární, dynamická DSA
34 / 82
Queue - Summary • multi-user services • FIFO = First-in, First-out • only first element accessible (front) • insert only at and (back) • homogeneous, linear, dynamic DSA
35 / 82
(Abstraktní) datové typy Počet a vzájemné uspořádání složek
• •
statické = nemění se dynamické = mění se
Typ komponent
• •
homogenní = všechny stejného typu nehomogenní = různého typu
Existuje bezprostřední následník
• •
DSA
lineární = existuje [např. pole, seznam,…] nelineární = neexistuje [strom, tabulka,…] 36 / 82
(Abstract) data types Number and arrangement of elements
• •
static = fixed, does not change dynamic = changes
Type of the components
• •
homogeneous = all of equal type inhomogeneous = different types
Direct successor existence
• •
DSA
linear = direct successor exists nonlinear = direct successor does not exist 37 / 82
Abstraktní datové typy 9Fronta (Queue) • Zásobník (Stack) • Pole (Array) • Tabulka (Table) • Seznam (List) • Strom (Tree) • Množina (Set)
DSA
38 / 82
Zásobník (Stack) • Kdy?
• • • • •
DSA
odložení informace, výběr v opačném pořadí (návrat z procedury, uzlové body cesty, náboje v pistoli,...) LIFO = Last-in, First-out „poslední tam, první ven“ přístup pouze k prvku na vrcholu (top) vkládání pouze na vrchol (top) homogenní, lineární, dynamický 39 / 82
Stack (Zásobník) • When?
• • • • •
DSA
temporary data storage, access in reverse order (return from the procedure call), important nodes along the path, ammunition in pistol,...) LIFO = Last-in, First-out only top element accessible (top) insert on the top only homogeneous, linear, dynamic 40 / 82
Stack (Zásobník) length init
Stack Elem
empty full
push Bool
DSA
Nat
pop
max
top 41 / 82
Stack (Zásobník) Operations: init: -> Stack empty(_): Stack -> Bool push(_,_): Elem, Stack -> Stack top(_): Stack -> Elem pop(_): Stack -> Stack length(_): Stack -> Nat max: -> Nat full(_): Stack -> Bool ...omezen DSA
42 / 82
Stack (Zásobník) empty( init ) = true empty( push( e, s )) = false top( init ) = error_elem top( push( e, s )) = e pop( init ) = init pop( push( e, s )) = s DSA
43 / 82
Stack (Zásobník) 1. empty( init() ) = true 2. empty( push( e, s )) = false
Ex: empty( push(“X”, push(“Y”, pop( push( “A”, init() ))))) -> false empty( pop( push( “A”, init() ))) -> ??? Need for more axioms!
DSA
44 / 82
Stack (Zásobník) 3. top( init() ) = error_elem() 4. top( push( e, s )) = e
Ex: top( push(“X”, push(“Y”, pop( push( “A”, init() ))))) -> “X” top( init() ) -> error_elem top( pop( push( “A”, init() ))) -> ??? Need for more axioms!
DSA
45 / 82
Stack (Zásobník) 5. pop( init ) = init() 6. pop( push( e, s )) = s
Ex: pop( push(“A”, init() )) -> init() pop( push(“X”, push(“Y”, pop( push( “A”, init() ))))) -> push(“Y”, pop( push( “A”, init() ))) -> push(“Y”, init() ) DSA
46 / 82
Stack (Zásobník) – ext. 7. length( init ) = 0 8. length( push( e, s )) = succ( length( s )) Ex: length( push(“A”, init() )) -> succ( length( init() )) -> succ( 0 ) -> 1
DSA
47 / 82
Stack (Zásobník) – limit. 9. full( s ) = eq( length( s ), max ) 10. push( e, s ) = if full( s ) then error_stack
DSA
48 / 82
Stack - implementation In Array 0 1
vals
2
3
4
5
A D B E last SIZE-1
In Dynamic Memory tos E
DSA
B
D
A
49 / 82
Stack – in Array class stack { private: elem vals[SIZE]; int last;
// array of elements // index behind (place for next item)
public: void init( void ); elem top( void ); void pop( void ); void push( elem e ); void error( const char errorText[] ); stack(void); ~stack(void);
// just calls init()
}; DSA
50 / 82
Stack – in Array void stack::init(void) { last = 0; }
// init: -> Stack
elem stack::top(void){ // top(_): Stack -> Elem if( last > 0 ) return vals[last-1]; else error("Stack is empty during top()"); return 0; } void stack::pop(void){ // pop(_): Stack -> Stack if( last > 0 ) last--; else error("Stack is empty during pop()"); } DSA
51 / 82
Stack – in Array void stack::push( elem e ) //push(_,_):Elem, Stack -> Stack { if( last < SIZE ) vals[ last ++ ] = e; } bool stack::empty(void)// empty(_): Stack -> Bool { if( last == 0 ) return true; else return false; }
DSA
52 / 82
Stack – Usage #include "stack.h" //#include "stackDyn.h" void main( void ) { stack s; cout << s.empty() << endl; s.push( 2 ); s.push( 3 ); cout << s.empty() << endl; cout << s.top() << endl; s.pop(); cout << s.top() << endl; s.pop(); cout << s.top() << endl; cout << s.empty() << endl;
// OUTPUT: // 1
// 0 // 3 // 2 // Stack is empty during top // 1
}
DSA
53 / 82
Stack – in Dynamic Mem. class stack { private: Item * s;
// head of the list of elements
public: void init( void ); elem top( void ); void pop( void ); void push( elem e ); void error( const char errorText[] ); stack(void); ~stack(void);
// just calls init()
};
DSA
54 / 82
Stack – in Dynamic Mem. void stack::init(void) { s = NULL; }
// init: -> Stack
elem stack::top(void){ // top(_): Stack -> Elem if( s != NULL ) return s->val; else error( "Stack is empty during top()" ); return 0; } void stack::pop(void){ // pop(_): Stack -> Stack if( s != NULL ) { Item* tmp = s; s = s->next; delete( tmp ); } else error( "Stack is empty during pop()" ); } DSA
55 / 82
Abstraktní datové typy 9Fronta (Queue) 9Zásobník (Stack) • Pole (Array) • Tabulka (Table) • Seznam (List) • Strom (Tree) • Množina (Set)
DSA
56 / 82
Pole (array) j 1
i
6 7
2
3
A B C D E F
Array A of 2x3 elements
• Row index i ∈ {6,7} • Column index j ∈ {1, 2, 3}
A[6,3] -> C
DSA
57 / 82
Pole (array) • Kdy?
6 A B C 7 D E F A[6,3] -> C
• • • • •
prvky stejného typu - homogenní všechny prvky současně v paměti rychlý náhodný přístup (random-access) známý počet prvků - statické indexy uspořádány - lineární
• •
dán počet dimenzí (n) a meze indexů přístup k prvkům - mapovací funkce
----
DSA
1 2 3
58 / 82
Array (pole) • When?
6 A B C 7 D E F A[6,3] -> C
• • • • •
all elements equal - homogeneous all elements in memory fast random access fixed number of elements - static indexes ordered - linear
•
given: number of dimensions (n) and index range access to elements - map function
----
DSA
1 2 3
•
59 / 82
1 2 3
Pole (array)
6 A B C 7 D E F
Elem init
Idx
DSA
Array
lower upper
set get
60 / 82
Pole (array) Operations
1 2 3 6 A B C 7 D E F
init(_,_): Idx, Idx -> array upper(_): Array -> Idx lower(_): Array -> Idx set(_,_,_): Array,Idx,Elem->Array get(_,_): Array, Idx -> Elem
1-D (one dimensional) n-D -> Elem ~ (n-1)D Array DSA
61 / 82
Pole (array) lower( lower( upper( upper(
1 2 3 6 A B C
7 D E init(m,n) ) = m set(a,i,e) ) = lower( a ) init(m,n) ) = n set(a,i,e) ) = upper( a )
set( a, i, e ) = if( or(
lt(i,lower(a)), lt(upper(a),i) )) then error_array else set( a, i, e ) DSA
62 / 82
F
Pole (array)
1 2 3 6 A B C 7 D E F
get( init(m,n), i ) = error_elem get( set( a, i1, e ) , i2 ) = = if( eq(i1, i2)) then e else get( a, i2 ) Praxe: array[i] = e zápis set(array,i,e) e = array[i] zápis e = get(array,i) DSA
63 / 82
Array (Pole) – mapping function Logical structure
1 2 3
Array a[6..7, 1..3] Ex: a[7,2]->E
6 A B C i 7 D E F
j Indices
Physical location in memory Row order (po řádcích) Column order (po sloupcích) Relative address (offset) 0 1 2 3 4 5 0 1 2 3 4 5 A B C D E F row 6
A D B E C F col 1
row 7
col 2 col 3
Base address map(7,2) -> (base + 4) DSA
map(7,2) -> (base + 3) 64 / 82
Array (Pole) – mapping function 0 1 2
3 4 5
A B C
D E F
row order (po řádcích) 2D
map(i,j) = a(imin, jmin) + (i-imin) nj + (j-jmin) Base address
Column offset
map(i,j) = a(0,0) + (i*nj + j)
Row offset row length = Number of columns Relative address
… for indices from (0,0) 1 2 3
6 Ex: map(7,2) = a(6,1) + (i-6)*3 + (j-1) i 7 map(7,2) = a(6,1) + (7-6)*3 + (2-1) 0 1 2 = a(6,1) + 4 A B C DSA
65 / 82
A B C D E F 3 4 5 D E F
j
Array (Pole) – mapping function 0 1 2
3 4 5
A B C
D E F
row order (po řádcích) 3D
map(i,j,k) = a(imin, jmin, kmin) + (i-imin) nj nk + + (j-jmin) nk + + (k-kmin) Base address
Relative address (element offset)
map(i,j,k) = a(0,0,0) + (i*nj + j) * nk + k … for indices from (0,0)
DSA
66 / 82
Array (Pole) – mapping function 0 1
2 3
4 5
A D
B E
C F
column order (po sloupcích) 2D
map(i,j) = a(imin, jmin) + (i-imin) + + (j-jmin) ni Base address
map(i,j) = a(0,0) + j * ni + i
Relative address
… for indices from (0,0)
Ex: map(7,2) = a(6,1) + (7-6) + (2-1) * 2 = a(6,1) + 3 DSA
67 / 82
Array (Pole) – mapping function 0 1
2 3
4 5
A D
B E
C F
column order (po sloupcích) 3D
map(i,j,k) = a(imin, jmin, kmin) + (i-imin) + + (j-jmin) ni + Base address
+ (k-kmin) ni nj Relative address
map(i,j,k) = a(0,0,0) + (k*nj + j) * ni + i … for indices from (0,0)
DSA
68 / 82
Array – speedup by Iliff’s vectors Mapping functions need multiplications -> change them to additions (0) (1) (2) 3 4 A: array [3..4, 1..3, 0..2]
i
j (0)
1
2
j
3
(0)
1
2
3
k 0 1 2
0 1 2 0 1 2
A B C E F G H I
0 1 2 0 1 2 0 1 2
J K L M N O P Q R S [Hudec93, PT]
DSA
69 / 82
Abstraktní datové typy 9Fronta (Queue) 9Zásobník (Stack) 9Pole (Array) • Tabulka (Table) • Seznam (List) • Strom (Tree) • Množina (Set)
DSA
70 / 82
Vyhledávací Tabulka (Look-up Table) • Kartotéka, asociativní paměť, převod mezi kódy, četnost slov,...
• homogenní, dynamická (nejen) • Obsahuje a nelineární
• • •
položky jednoznačně identifikované klíčem (podle klíče se položky vyhledávají) klíč jen 1x (je jedinečný)
• Př.: seznam hospod, klíčem je jejich jméno. DSA
71 / 82
Look-up Table (Vyhledávací Tabulka) • Card-register, associative memory, code conversion, word count • homogeneous, dynamic (not only), • Contains and nonlinear
• • •
items items fully qualified by the key (item are searched according to their key) key is unique
• Ex.: directory of bars, the bar name is its key. DSA
72 / 82
Tabulka (Look-up Table) read
delete Table
Elem
Key search Bool
DSA
insert
init 73 / 82
Tabulka (Look-up Table) Operace: init: -> Table insert(_,_,_): Key, Elem, Table -> Table read(_,_): Key, Table -> Elem delete(_,_): Key, Table -> Table search(_,_): Key, Table -> Bool
DSA
74 / 82
Tabulka (Look-up Table) search( k, init ) = false search( k1, insert(k2,e,t)) = if( eq(k1, k2) ) then true else search( k1, t )
DSA
75 / 82
Tabulka (Look-up Table) delete( k, init ) = init delete( k1, insert(k2,e,t)) = if( eq(k1, k2) ) then delete( k1, t ) else insert(k2,e,delete(k1, t))
DSA
76 / 82
Tabulka (Look-up Table) read( k, init ) = error_elem read( k1, insert(k2,e,t)) = if( eq(k1, k2) )
then e else read( k1, t )
DSA
77 / 82
Tabulka (Look-up Table) insert(k1,e1, insert(k2,e2,t)) =
if( eq(k1, k2) ) then insert(k1,e1, t) else insert(k2,e2, insert(k1,e1, t))
DSA
78 / 82
Look-up Table – Implementation In Array • For small interval of keys • sequential search … O(n) • direct access (key = index) … O(1) • convertToLatin2( char_kamenický) LUT[char_kamenický] •For large universum of keys • Hash tables … average O(1) to O(n) Wait for a separate lecture DSA
79 / 82
Abstraktní datové typy 9Fronta (Queue) 9Zásobník (Stack) 9Pole (Array) 9Tabulka (Table) • Seznam (List) • Strom (Tree) • Množina (Set)
DSA
80 / 82
Prameny / References • Jan Honzík: Programovací techniky, skripta, VUT Brno, 19xx
• Karel Richta: Datové struktury, skripta pro postgraduální studium, ČVUT Praha, 1990
• Bohuslav Hudec: Programovací techniky, skripta, ČVUT Praha, 1993
DSA
81 / 82
Prameny / References • Steven Skiena: The Algorithm Design Manual, Springer-Verlag New York, 1998 http://www.cs.sunysb.edu/~algorith
• Gang of four (Cormen, Leiserson, Rivest, Stein): Introduction to Algorithms, MIT Press, 1990
• Code exapmples: M.A.Weiss: Data Structures and Problem Solving using JAVA, Addison Wesley, 2001, code web page:
http://www.cs.fiu.edu/~weiss/dsj2/c ode/code.html DSA
82 / 82
