FIT1008 Lecture Notes - Lecture 6: Parsing, Init, Delimiter
18 Jun 2018
School
Department
Course
Professor
!""#$%&#'()
*+,()-'+.(
/
0#1#-+1(2'-'13"()-'(45(61+#77$
/
8#9:-+1(2-3995;+('-'#2(-#23561-3<-';#9(
/
="3'>
?("$-<#'1-#99(''
/
?("$-932;#91-"(;"('(61#1+36
/
@36'>
A36%"('+.#&7(-#<1("-9"(#1+36-%2#,+252-'+.(-';(9+<+()-36-9"(#1+36
/
@:#6B+6B-'+.(-+'-93'17$-%9"(#1(-6(C-#""#$-D-93;$-#77-+1(2'-3E("
/
F73C-3;'-+<-(7(2-':5<<7+6B-+'-"(45+"()
/
G+'1-'+.( +'-H63C6I-<7(,+&+7+1$ 631-6(()()-J"#6)32-#99(''I-<(C-+6'("1+36'-#6)-
)(7(1+36'K
List ADT
@"(#1(-#-6(C-<+7(
LM
N2;3"1O93;$-3E("-&5+7)P#""#$-<5691+36-13-9"(#1(-#""#$'
from referential_array import build_array
QM
!))-#6$-3;'O2(1:3)'-5'("'-2#$-6(()-13-5'(
__init__(self)
self.array J'13"('-1:(-+1(2'-+6-1:(-3")("-1:($-#""+E(K
§
self.count JH((;'-1"#9H-3<-652&("-3<-+1(2'-+6-!0RK
§
○
__len__(self)
return self.count
§
○
is_empty(self)
○
is_full(self)
○
add(self, new_item)
○
delete(self, index)
○
__str__(self)
○
__contains__(self, item)
○
SM
N6E#"+#61>-E#7+)-)#1#-#;;(#"'-+6-1:(-TUJ93561%LK-;3'+1+36'
/
V(11("-<3"-'(#"9:+6B 932;#"()-13-7+6H%&#'()-E("'+36-%WJ73B6K
/
Sorted-List ADT
X-'(45(69(-3<-+1(2'-+6-+69"(#'+6B-3")("
F#2(-3;'-#'-G+'1-!0R
WE("73#)+6B-3;("#13"'-J&#'+9#77$-#6$1:+6B-C+1:-PPPY3;ZPPK>
__getitem__(self, index)
/
__setitem__(self, index, value)
/
__eq__(self, RHS)
/
__lt__(self, RGS) -less than
/
0+<<("(61-23)(7'>
GN*W JG#'1-N6-*+"'1-W51K-%'1#9H[/
X-7#'1-(7(2(61-13-(61("-+'-<+"'1-13-&(-;"39(''()O)(7(1()
*N*W J*+"'1-N6-*+"'1-W51K-%45(5([/
X-<+"'1-(7(2(61-13-(61("-+'-<+"'1-13-&(-;"39(''()O)(7(1()
Stack ADT
W;'>
__init__(self)
self.array
§
self.count
§
self.top J+6)+9#1+6B-13;-+1(2-+6-'1#9HK
§
○
__len__(self)
return self.count
§
○
is_empty(self)
○
is_full(self)
○
reset(self) J(2;1+('-7+'1K
○
push(self, item) J#))-+1(2-13-13;K
○
pop(self) J1#H(-+1(2-3<<-13;I-'+69(-GN*WK
○
peek(self) J733H-#1-+1(2-36-13;-C+1:351-#71("+6BK
○
__str__(self)
○
/
N6E#"+#61>-E#7+)-)#1#-#;;(#"'-+6-1:(-TUJ93561%LK-;3'+1+36'/
!;;7+9#1+36'
\6)3-()+1+6B
○
N2;7(2(61-"(95"'+36
○
=#"'+6B-J)(7+2+1("-2#19:+6BI-"(E("'(-;37+':-631#1+36K
○
]561+2(-2(23"$-2#6#B(2(61-J?^'I-<5691+36%9#77+6BK
○
/
Queue ADT
W;'>
__init__(self)
self.array
§
self.count
§
self.front J2#"H'-<"361-3<-45(5(I-"(<("'-13-<+"'1-(7(2-13-&(-
'("E()K
§
self.rear J2#"H'-"(#"-3<-45(5(I-"(<("'-13-<+"'1-(2;1$-'731-#1-
"(#"K
§
○
append(self) J#))'-+1(2-#1-"(#"K
○
serve(self) J"(23E('-+1(2-<"32-<"361K
○
/
N6E#"+#61>-E#7+)-)#1#-#;;(#"'-+6-1:(-TUJ93561%LK-;3'+1+36'/
!;;7+9#1+36'
F9:()57+6B-#6)-&5<<("+6B-J;"+61("'I-H($&3#")'I-(,(951+6B-#'$69:"3635'-
;"39()5"(-9#77'K
○
/
__-9+"957#"-45(5(-&(11("-1:#6-7+6(#"I-'+69(-+1-#E3+)'-C#'1+6B-';#9(-&$-C"#;;+6B-
#"356)-1:(-#""#$-1:#1-'5;;3"1'-1:(-45(5(M
Week$6:$container$ADTs$(array-based)
R:5"')#$I-L`-a56(-QTLb
QQ>Qc
Document Summary
Non-resizable after creation - maximum size specified on creation. Changing size is costly - create new array + copy all items over. List size is known, flexibility not needed (random access, few insertions and deletions) Import/copy over build_array function to create arrays from referential_array import build_array. Add any ops/methods users may need to use. __init__(self) self. array (stores the items in the order they arrive) self. count (keeps track of number of items in adt) __len__(self) return self. count is_empty(self) is_full(self) add(self, new_item) delete(self, index) Better for searching compared to link-based version - o(logn) = last element to enter is first to be processed/deleted. = first element to enter is first to be processed/deleted. __init__(self) self. array self. count self. top (indicating top item in stack) __len__(self) return self. count is_empty(self) is_full(self) reset(self) (empties list) push(self, item) (add item to top) pop(self) (take item off top, since lifo) peek(self) (look at item on top without altering) Invariant: valid data appears in the 0 (count-1) positions.
