modul praktikum kurikulum 2015 - struktur data ti
Post on 20-Feb-2018
220 Views
Preview:
TRANSCRIPT
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
1/57
PANDUAN PRAKTIKUM
STRUKTUR DATA - TI
Disusun Oleh :
Deborah Kurniawati, S.Kom., M.Kom.
Femi Dwi Astuti, S.Kom.
Inra !atini "., S.Kom., M.Kom.
#N $arnanin%rum, S.Si., M.T.
Nurul A&i&ah K., S.Kom.
STMIK AKAKOM
!o%'a(arta
)*+
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
2/57
KATA PENGANTAR
Puji Syukur kepada Tuhan karena modul Algoritma dan Pemrograman ini dapat
terselesaikan. Modul ini dibuat karena tuntutan kurikulum baru atau disebut sebagai kurikulum
2014 STMI AA!M yang mulai diberlakukan pada tahun akademik 2014"201#.
Modul ini membahas tentang struktur data dan implementasinya dalam bahasa $%%.
Materi yang dibahas meliputi tipe data& larik& pointer& sta'k& (ueue& single link list& double link
list& binary tree& hash.
Tentu saja dengan segala keterbatasan yang ada& modul ini jauh dari sempurna. )ntuk
itu masukan dan saran untuk perkembangan modul ini sangat diharapkan.
Akhirnya semoga modul ini berguna dalam membantu mahasis*a untuk mempelajari
tentang Struktur +ata.
,ogyakarta& September 2014.
Penulis
ii
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
3/57
DAFTAR ISI
-uul.................................................................................................................................i
Kata Pen%antar................................................................................................................ii
Datar Isi........................................................................................................................iii
Pertemuan (e +................................................................................................................+
Pertemuan (e )................................................................................................................
Pertemuan (e /................................................................................................................0
Pertemuan (e ..............................................................................................................+*
Pertemuan (e 1..............................................................................................................+/
Pertemuan (e 2..............................................................................................................+2
Pertemuan (e 0..............................................................................................................+3
Pertemuan (e 4..............................................................................................................))
Pertemuan (e 3..............................................................................................................)1
Pertemuan (e +*............................................................................................................/*
Pertemuan (e ++............................................................................................................/1
Pertemuan (e +)............................................................................................................*
Pertemuan (e +/............................................................................................................1
Pertemuan (e +............................................................................................................4
iii
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
4/57
PERTEMUAN KE 1
TIPE DATA
A. TU-UAN :
Memahami tentan% 5en%%unaan ti5e ata lari( an 5ointer Men%%una(an ti5e ata untu( men'elesai(an soal
". T6ORI SIN7KAT
LARIK
#ari( 8arra'9 men'ata(an (um5ulan ata. Paa bebera5a bahasa 5emro%raman, ata 'an%
ter(anun% alam suatu lari( harus berti5e sama. #ari( in'ata(an en%an awalan huru (a5ital an
notasi ; i5a(ai untu( men'ata(an ata alam lari(.
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
5/57
Operator new dan delete
ne!O5erator new menEi5ta(an ob@e( saat run-time, an teta5 a(ti selama 5ro%ram a(ti. Sinta(
untu( o5erator newaalah
BBBBD 5 G new BBBB89?
imana BBBB aalah (elas ob@e(. 6(s5resi newBBBB89meman%%il ElassEontruEtoruntu( menEi5ta(an
ob@e( baru an men%embali(an 5ointer 5aan'a. $asiln'a aalah ob@e( anonim, an ia(ses en%an
men%%una(an 5 atau H imana H 5ointer lainn'a 'an% sama en%an 5.
de"ete. Untu( bebera5a (asus, 5entin% untu( men%henti(an (eberaaan ob@e( sebelum a(hir
5ro%ram. Untu( ma(su tersebut i%una(an o5erator elete.
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
6/57
#include
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
7/57
PERTEMUAN KE #
SORTING
A. TU-UAN :
Memahami tentan% sortin% en%an metoe insertion sort an seleEtion sort Men%%una(an sortin% tersebut alam im5lementasi 5ro%ram
". T6ORI SIN7KAT
Pen%urutan 8Sort9
Sort aalah 5roses 5en%urutan ata 'an% sebelumn'a isusun seEara aEa( sehin%%a men@ai
tersusun seEara teratur menurut suatu aturan tertentu. Sort bisa nai( atau turun.
SeleEtion Sort
Membanin%(an elemen 'an% se(aran% en%an elemen 'an% beri(utn'a sam5ai en%anelemen 'an% tera(hir. -i(a itemu(an elemen lain 'an% lebih (eEil ari elemen se(aran%, ma(a
iEatat 5osisin'a an (emuian itu(ar.
Insertion Sort
Pen%urutan ila(u(an en%an Eara membanin%(an ata (ei 8imana i imulai ari ata (e
) sam5ai en%an ata tera(hir9 en%an ata beri(utn'a. -i(a itemu(an ata 'an% lebih (eEil, ma(a
ata tersebut isisi5(an (e e5an sesuai en%an 5osisi 'an% seharusn'a.
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
8/57
{ int ,6,tem3; 'or (%&;>9
EoutLLData (e LLi>+LL G ? EinAi;?
Q
Q
=oi Eeta(ata8Eonst int A;, int n9
STRUKTUR DATA - TI 1
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
9/57
int i?
or 8iG*? iLn?i>>9
EoutLLAi;LL ?
EoutLLenl?Q
=oi tu(ar8int a, int b9
int tem5?
tem5Ga?
aGb?
bGtem5?
Q
=oi SeleEtionsort8int A;, int n9
int i,t,min?
or 8iG*?iLn?i>>9
minGi?
or 8tGi>+?tLn?t>>9
i 8At;LAmin;9
minGt?
i 8minGi9
tu(ar8Ai;,Amin;9?
QQ
=oi main89
int ata+*;,n?
EoutLL"an'a( ata : ?
Einn?
baEaata8ata,n9?
Eeta(ata8ata,n9?
SeleEtionsort8ata,n9?
Eeta(ata8ata,n9? %etEh89?
Q
JJ
D. #ATI$AN
A(an isam5ai(an oleh Dosen Pen%am5u saat 5ra(ti(um
6. TU7AS :
A(an isam5ai(an oleh Dosen Pen%am5u saat 5ra(ti(um
STRUKTUR DATA - TI 2
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
10/57
PERTEMUAN KE $
MERGE SORT
A. TU-UAN :
Memahami (ara(teristi( al%oritma mer%e sort Men%%una(an al%oritma mer%e sort untu( men%urut(an ata
". T6ORI SIN7KAT
Al%oritma 5en%urutan ata mer%esort ila(u(an en%an men%%una(an Eara
i=ieanEonHuer 'aitu en%an memeEah (emuian men'elesai(an setia5 ba%ian (emuian
men%%abun%(ann'a (embali. Pertama ata i5eEah men@ai ) ba%ian imana ba%ian 5ertama
meru5a(an seten%ah 8@i(a ata %ena59 atau seten%ah minus satu 8@i(a ata %an@il9 ari seluruh ata,
(emuian ila(u(an 5emeEahan (embali untu( masin%masin% blo( sam5ai han'a teriri ari satu
ata tia5 blo(.
Setelah itu i%abun%(an (embali en%an membanin%(an 5aa blo( 'an% sama a5a(ah ata
5ertama lebih besar ari5aa ata (eten%ah>+, @i(a 'a ma(a ata (eten%ah>+ i5inah seba%ai
ata 5ertama, (emuian ata (e5ertama sam5ai (eten%ah i%eser men@ai ata (eua sam5ai (e
ten%ah>+, emi(ian seterusn'a sam5ai men@ai satu blo( utuh se5erti awaln'a. Sehin%%a metoe
mer%esort meru5a(an metoe 'an% membutuh(an un%si re(ursi untu( 5en'elesaiann'a.
Den%an hal ini es(ri5si ari al%oritma irumus(an alam / lan%(ah ber5ola i=iean
EonHuer. "eri(ut men@elas(an lan%(ah (er@a ari Mer%esort.
+. Di%ide
Memilah elemen elemen ari ran%(aian ata men@ai ua ba%ian.
). &on'(er
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
11/57
+void mere(int lo,int mid,int hih){int h,i,6,b[5&],;
h%lo;i%lo;6%mid;hile((h
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
12/57
'or(i%;i
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
13/57
PERTEMUAN KE +
REKURSIF DAN UI&K SORT
A. TU-UAN :
Memahami (ara(teristi( al%oritma HuiE( sort Men%%una(an al%oritma HuiE( sort untu( men%urut(an ata
". T6ORI SIN7KAT
Re-(rsif ada"a. un%si 'an% meman%%il irin'a seniri seEara lan%sun% atau5un tia(, an 5roses
5eman%%ilann'a itu isebut re(ursi.
Masalah 'an% a5at iselesai(an seEara re(ursi aalah masalah 'an% di*a/imen@ai satu atau
lebih )asa"a.0)asa"a. ser(pa'an%"e*i. -ei".
Si)p"e &asesaalah (onisi(onisi 'an% a5at iselesai(an seEara lan%sun% tan5a 5erlu ire(ursi
an biasan'a i%una(an seba%ai tana a(hir ari sebuah re(ursi.
Re(rsi%e &aseaalah (onisi(onisi 'an% iselesai(an en%an Eara meman%%il un%si itu seniri
en%an 5roblem 'an% sema(in ber(uran% mene(ati sim5le Ease.
uiE( sort meru5a(anAlgoritma Pembagi. Pertama se(ali HuiE(sort memba%i list 'an% besar
men@ai ua buah sub list 'an% lebih (eEil: element (eEil an element besar. uiE(sort (emuian
a5at men'ortir sub list itu seEara re(ursi.
#an%(ah#an%(ah 5en%er@aann'a ialah:
+. Ambil sebuah elemen, 'an% isebut en%anpivot, 5aa sebuah atar.
). Urut(an (embali sebuah list sehin%%a elemen en%an nilai 'an% (eEil ari 5i=ot beraa
sebelum 5i=ot, sean%(an seluruh element 'an% memili(i nilai 'an% lebih besar ari 5i=ot
beraa setelahn'a 8nilai 'an% sama a5at beraa 5aa 5i=ot setelahn'a9. Setelah 5emisahan,
5i=ot beraa 5aa 5osisi a(hirn'a. O5erasi ini isebut Partition.
/. Sub list (emuian isortir seEara reEursi ari elemen 'an% lebih (eEil an sub list ari
elemen 'an% lebih besar.
Kasus asar ari re(usri ialah list ari besaran nol atau satu, 'an% tia( 5erlu untu( i sortin%.
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
14/57
etch(); + lon int 'atorial(int 2) 1'unsi ini memberian nilai bali beru3a hasil 'atorial dari data in3utan1
{ i' (2%%) return(2); else return (21'atorial(20));
+
#include
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
15/57
cin$$n;
ub%n; cout
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
16/57
PERTEMUAN KE 2
SEAR&3ING
A. TU-UAN :
Memahami (ara(teristi( al%oritma searEhin%
Men%%una(an al%oritma searEhin% untu( 5enEarian ata
". T6ORI SIN7KAT
SearEhin% aalah metoe 5enEarian inormasi alam suatu a5li(asi, en%an suatu (unEi8 (e' 9.
PenEarian i5erlu(an untu( menEari inormasi (husus ari table 5aa saat lo(asi 'an% 5asti ari
inormasi tersebut sebelumn'a tia( i(etahui. PenEarian selalu in'ata(an en%an reerensi
5aa aan'a se(elom5o( ata 'an% tersim5an seEara teror%anisasi, (elom5o( ata tersebut (itasebut table.
Paa metoe searEhin% 85enEarian9 aa ) te(ni( 'an% i%una(an 'aitu : PenEarian se(uensial
8seHuential searEh9 an PenEarian biner 8"inar' searEh9.
1! Penarian se-(ensia" 4se'(entia" sear.5
PenEarian se(uensial 8seHuential searEh9 atau serin% isebut 5enEarian linier men%%una(an
5rinsi5 seba%ai beri(ut : ata 'an% aa i banin%(an satu 5ersatu seEara berurutan en%an
'an% iEari.
Paa asarn'a, 5enEarian ini han'a mela(u(an 5en%ulan%an ari + sam5ai en%an @umlah
ata. Paa setia5 5erulan%an , i banin%(an ata (ei en%an 'an% iEari. A5abila sama ,
berarti ata telah itemu(an . Sebali(n'a a5abila sam5ai a(hir 5en%ulan%an , tia( aa 'an%sama berarti ata tia( aa.
#! Penarian 6iner 46inar7 Sear.5
Salah satu s'arat 5enEarian biner 8binar' searEh9 a5at ila(u(an aalah ata suah alam
(eaaan terurut. Den%an (ata lain, a5abila ata belum alam (eaaan terurut , 5enEarian
biner tia( a5at ila(u(an . Dalam (ehiu5an seharihari, sebenarn'a (ita @u%a seri%
men%%una(an 5enEarian biner. Misaln'a saat (ita in%in menEari suatu (ata alam (amus.
#an%(ah alam 5enEarian biner aalah :
+. Mulamula iambil ari 5osisi awalG+ an 5osisi a(hir G n
). Kemuian (ita Eari 5osisi ata ten%ah en%an rumus 5osisi ten%ah G 85osisi awal > 5osisia(hir 9 i= )
/. Kemuian ata 'an% i Eari ibanin%(an en%an ata ten%ah
a. -i(a sama, ata itemu(an, Proses selesai
b. -i(a lebih (eEil, 5roses ila(u(an (embali teta5i 5osisi a(hir ian%%a5 sama en%an
5osisi ten%ah +,
E. -i(a lebih besar , 5roses ila(u(an (embali teta5i 5osisi awal ian%%a5 sama en%an
5osisi ten%ah >+.
. Ulan%i lan%(ah (eua hin%%a ata itemu(an , atau tia( itemu(an.
1. PenEarian biner ini a(an bera(hir @i(a ata itemu(an 5osisi awal lebih besar ari 5aa
5osisi a(hir. -i(a 5osisi awal suah lebih besar ari 5osisis a(hir berarti ata tia(
i(etemu(an.
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
17/57
#include
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
18/57
int cari; cin$$cari; 3encarian int hasil;
hasil % binar!9s(data, siHe, cari); i' (hasil%%&) cout
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
19/57
PERTEMUAN KE 8
STACK (Tumpukan)
A. TU-UAN :
Memahami (onse5ta!k8tum5u(an9 Mam5u membuat 5ro%ram 'an% men%im5lementasi(an (onse5 tum5u(an en%an lari(
an lin( list
". T6ORI SIN7KAT
SeEara seerhana Sta!k 8tum5u(an9 bisa iarti(an seba%ai (um5ulan ata 'an% seolaholah
ata 'an% satu ileta((an i atas ata 'an% lain. Penambahan an 5en%ha5usan ata han'a a5at
ila(u(an ari u@un% 'an% sama, 'an% isebut seba%ai u@un% atas tum5u(an "top o# ta!k9. Den%an
(onisi emi(ian ma(a 5rinsi5 'an% i%una(an 5aa staE( 8tum5u(an9 aalah #IFO 8lat in #irt
out9.
Aa ua o5erasi asar 'an% a5at ila(u(an 5aa sebuah staE( 8tum5u(an9, 'aitu o5erasi
5enambahan ata 8PUS$9 an o5erasi 5en%uran%anJ5en%ambilan ata 8POP9. 7ambar 2.+men%ilustrasi(an o5erasi PUS$ an POP 5aa staE( 'an% iim5lementasi(an en%an arra'
beru(uran 2 ari 5roses berurutan seba%ai beri(ut,
P+ : 5enambahan / ata, 'aitu A " < D 6
P) : 5en%uran%an ) ata
P/ : 5enambahan / ata, 'aitu F 7 $
2 2 2
1 1 Posisi to5 G 1 $
Posisi to5 G 6 7
/ D / / F) < Posisi to5 G) < ) inleFist, RER); *aca9Ma6u(>inleFist); ambah9enah(>inleFist, R@R, 8); *aca9Ma6u(>inleFist); coutinleFist); etch();
+
D. #ATI$ANDiberikan oleh $oen pengampu pa$a aat praktikum%
6. TU7AS :
Diberikan oleh $oen pengampu pa$a akhir praktikum%
Dikerjakan $i rumah $an $ilampirkan pa$a laporan%
STRUKTUR DATA - TI )4
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
32/57
STRUKTUR DATA - TI )3
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
33/57
MODUL 1
o
Mam5u membuat 5roram untu( men%im5lementasi(an o5erasi 5enambahan sim5ul i e5anan i bela(an% 5aa Double #in( #ist
6! TEORI SINGKAT
Double linke$ litatau isebut @u%a Senarai "erantai 7ana ham5ir sama en%an Single Linke$ Lit
'an% telah ibahas 5aa bab sebelumn'a, 'aitu 5en%alo(asian memori seEara inamis 'an%
i%una(an untu( men'im5an ata. "ean'a Double Linke$ Lit lebih #le*ibel ibanin% Single
Linke$ Lit (arena 5aa Double Linke$ Lit semua sim5ulsim5uln'a 'an% aa ialamn'a
memili(i ) buah 5enun@u( 'an% i%una(an untu( men%(ait(an iri en%an sim5ul lain 'an% aa i
sebelah (anann'a an i sebelah (irin'a.
Di alam (onse5Double Linke$ Litaa / unsur 5enu(un% 'an% 5entin%, 'aitu :
+. Penun@u( 8biasa isebutpointer9.Penun@u( atau pointer 'an% ima(su isini alat 'an% i%una(an untu( menun@u( sebuah
sim5ul, se5erti 5aa 7ambar +*.+.
Ga)*ar 1
Se5erti senarai berantai tun%%al, Senarai berantai 7ana meru5a(an (um5ulan sim5ulsim5ul
'an% terhubun% satu en%an 'an% lain. $an'a bean'a 5aa senarai ini setia5 sim5uln'a
mem5un'ai ) 5en%hubun%, (iri an (anan, se5erti 7ambar +*./.
STRUKTUR DATA - TI /*
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
34/57
Ga)*ar 1
Untu( 5embuatan Senarai "erantai 7ana a5at ie(larasi(an en%an membuat tru!t
strSenerai7ana 'an% memili(i ) an%%ota berti5e Sim5ul, 'aitu: awal an a(hir 'an% berun%si
seba%ai 5enun@u(. Kemuian, tru!t strSenerai7ana tersebut ibuat aliasn'a en%an nama
Senerai7ana. Selain itu i5erlu(an @u%a un%si untu( membuat Senarai "erantai 7ana
en%an nama buat an 5arameter beru5a 5ointer H, 'an% memili(i an%%ota awal an a(hir
en%an nilai awal masih (oson% 8null9, se5erti Eontoh ibawah ini:t!3ede' struct str>enerai=anda{ >im3ul 1aal; >im3ul 1ahir;+ >enerai=anda;
void buat(>enerai=anda 17){ 70$aal%QFF; 70$ahir%QFF;
+
7ambar +*. meru5a(an ilustrasi 5enambahan ata i bela(an% 5aa $ouble link lit.
Ga)*ar 1
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
35/57
"eri(ut Eontoh im5lementasi Double #in( #ist untu( menambah ata ie5an, ibela(an%
an membaEa ata ma@u.
000000000000000000000000000000000000000000000000000000000000000000000000000
#3rama hdrsto3#includeim3ul 1iri;+ >im3ul;
t!3ede' struct str>enerai=anda{ >im3ul 1aal; >im3ul 1ahir;+ >enerai=anda;
void buat(>enerai=anda 17){
70$aal%QFF; 70$ahir%QFF;+
void ambah9:e3an(>enerai=anda 17, data elemen){ >im3ul 1baru%ne >im3ul(); baru0$masuan%elemen; i' (70$aal%%QFF 44 70$ahir%%QFF) { 70$aal%baru;
70$ahir%baru; baru0$anan%QFF; baru0$iri%QFF; + else { 70$aal0$iri%baru; baru0$anan%70$aal; 70$aal%baru; 70$aal0$iri%QFF; +
+
void ambah9*elaan(>enerai=anda 17, data elemen){ >im3ul 1baru%ne >im3ul(); baru0$masuan%elemen;
STRUKTUR DATA - TI /)
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
36/57
i' (70$aal%%QFF 44 70$ahir%%QFF) { 70$aal%baru; 70$ahir%baru;
baru0$anan%QFF; baru0$iri%QFF; + else { 70$ahir0$anan%baru; baru0$iri%70$ahir; 70$ahir%baru; 70$ahir0$anan%QFF; ++
void *aca9Ma6u(>enerai=anda 17){ >im3ul 1bantu%ne >im3ul();
bantu%70$aal; hile (bantuP%QFF) { cout
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
37/57
cin$$hasil; ambah9*elaan(>nr=d, hasil); clrscr(); +
brea; case RIR { clrscr(); *aca9Ma6u(>nr=d); + brea; de'ault { coutnr=d);+000000000000000000000000000000000000000000000000000000000000000000000000000
&! LATI3AN
Diberi(an oleh osen 5en%am5u 5aa saat 5ra(ti(um.
D! TUGAS
Diberi(an oleh osen 5en%am5u 5aa a(hir 5ra(ti(um.
Di(er@a(an i rumah an ilam5ir(an 5aa la5oran.
STRUKTUR DATA - TI /
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
38/57
MODUL 11
DOU6LE LINK LIST
E! TU=UAN >
o
Mam5u membuat 5ro%ram untu( men%im5lementasi(an 5enambahan sim5ul i ten%ah anmen%ha5us Double #in( #ist
F! TEORI SINGKAT
Menambah sim5ul 5aa Double Link Litaa ti%a maEam 'aitu menambah i e5an, bela(an%
8telah ibahas 5aa moul +*9 an ten%ah 'an% a(an ibahas 5aa moul ini. Paa %ambar ++.+ ini
itun@u((an ilustrasi 5enambahan ata i ten%ah 5aaDouble Link Lit.
Ga)*ar 11!1 I"(strasi Pena)*a.an Data di Ten/a. padaDu!le Link Li"t
O5erasi men%ha5us sim5ul 5aaDouble Link Lit@u%a aa ti%a maEam 'aitu men%ha5us sim5ul i
e5an, bela(an% an ten%ah. Ta5i en%an men%%una(anDouble Link Lit5roses 5enEarian sim5ul
'an% a(an iha5us men@ai sema(in Ee5at. Untu( men%ha5us sebuah sim5ul i5erlu(an satu buah
tambahan =ariabel 5ointer 'aitu =ariabel bantu 'an% ber%una untu( menun@u((an sim5ul mana(ah
'an% a(an iha5us.
Ga)*ar 11!# I"(strasi Pen/.ap(san Data padaDu!le Link Li"t
&! PRAKTIK >
"eri(ut Eontoh im5lementasi Double #in( #ist se5erti 5aa moul +*, itambah en%an
o5erasi menambah ata i ten%ah, men%ha5us ata an membaEa ata munur.
JJTulis(an 5ro%ram 'an% suah ibuat 5aa 5ertemuan (e+*, sam5ai sebelum =oi main89JJKemuian lan@ut(an en%an 5ro%ram beri(ut
=oi TambahTen%ah8Senerai7ana H, ata elemen, int Posisi9
Sim5ul baruGnew Sim5ul89?
STRUKTUR DATA - TI /1
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
39/57
Sim5ul bantuGnew Sim5ul89?
Sim5ul bantu+Gnew Sim5ul89?
barumasu((anGelemen?
i 8HawalGGNU## Ha(hirGGNU##9 JJmasih (oson%
HawalGbaru?
Hawal(iriGNU##?
Ha(hirGbaru?
Ha(hir(ananGNU##?
Q
else
i 8PosisiGG*9 JJ5osisi 5ertama, tambah e5an
Hawal(iriGbaru?
baru(ananGHawal? HawalGbaru?
Hawal(iriGNU##?
Q
else
bantuGHawal?
or 8int iG+?iLPosisi?i>>9
i 8bantu(ananGNU##9
bantuGbantu(anan?
i 8bantu(ananGGNU##9 JJ5osisi tera(hir, tambah bela(an%
Ha(hir(ananGbaru?
baru(iriGHa(hir?
Ha(hirGbaru?
Ha(hir(ananGNU##?Q
else JJ5osisi ten%ah beneran
bantu+Gbantu(anan?
baru(iriGbantu?
baru(ananGbantu+?
bantu(ananGbaru?
bantu+(iriGbaru?Q Q
Q
Q
=oi $a5usSim5ul8Senerai7ana H, ata elemen9
Sim5ul bantuGnew Sim5ul89?
Sim5ul bantu+Gnew Sim5ul89?
Sim5ul ha5usGnew Sim5ul89?
i 8HawalGGNU## Ha(hirGGNU##9
EoutLL#ist masih (oson%LLenl? else
i 8Hawalmasu((anGGelemen9JJha5us awal list
ha5usGHawal?
HawalGha5us(anan?
Hawal(iriGNU##?
STRUKTUR DATA - TI /2
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
40/57
elete8ha5us9?
EoutLLDitemu(an list 5alin% (iriLLenl?
Q
else
bantuGHawal?
while 88bantu(anan(ananGNU##9 8elemenGbantu(ananmasu((an99
bantuGbantu(anan?
i 88bantu(anan(ananGGNU##98elemenGbantu(ananmasu((an99
EoutLLData tia( itemu(anLLenl?
else
ha5usGbantu(anan?
i 8ha5usGNU##9
i 8ha5usGHa(hir9JJha5us i ten%ah list
bantu+Gha5us(anan?
bantu(ananGha5us(anan?
bantu+(iriGha5us(iri?
EoutLLDitemu(an i ten%ah listLLenl?
Q
else JJha5us a(hir list
Ha(hirGbantu?
Ha(hir(ananGNU##?
EoutLLDitemu(an i a(hir listLLenl?
Q elete8ha5us9?
Q
Q
Q
Q
=oi "aEaMa@u8Senerai7ana H9
Sim5ul bantuGnew Sim5ul89?
bantuGHawal?
while 8bantuGNU##9
EoutLLbantumasu((anLL ?
bantuGbantu(anan?
Q
EoutLLenl?
Q
=oi "aEaMunur8Senerai7ana H9
Sim5ul bantuGnew Sim5ul89?
bantuGHa(hir? while 8bantuGNU##9
EoutLLbantumasu((anLL ?
bantuGbantu(iri?
Q
EoutLLenl?
STRUKTUR DATA - TI /0
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
41/57
Q
=oi main89
Senerai7ana Snr7Gnew Senerai7ana89? buat8Snr79?
int tem5at?
ata hasil, Eari?
Ehar 5ilihGX+X?
while 85ilihGGX+XYY5ilihGGX)XYY5ilihGGX/XYY5ilihGGXXYY5ilihGGX1XYY5ilihGGX2X9
EoutLLPilih menuLLenl?
EoutLL+. Tambah De5anLLenl?
EoutLL). Tambah "ela(an%LLenl?
EoutLL/. Tambah Ten%ahLLenl?
EoutLL. $a5us DataLLenl? EoutLL1. "aEa Ma@uLLenl?
EoutLL2. "aEa Munur LLenl?
EoutLL0. Selesai LLenl?
EoutLLPilihan G ?
Ein5ilih?
switEh 85ilih9
Ease X+X :
EoutLLMasu((an atan'a : ?
Einhasil?
TambahDe5an8Snr7, hasil9? ElrsEr89?
Q
brea(?
Ease X)X :
EoutLLMasu((an atan'a : ?
Einhasil?
Tambah"ela(an%8Snr7, hasil9?
ElrsEr89?
Q
brea(?
Ease X/X : EoutLLMasu((an atan'a : ?
Einhasil?
EoutLLMasu((an 5osisin'a : ?
Eintem5at?
TambahTen%ah8Snr7, hasil, tem5at9?
ElrsEr89?
Q
brea(?
Ease XX :
ElrsEr89?
EoutLLMau ha5us sim5ul a5aZ ? EinEari?
$a5usSim5ul8Snr7, Eari9?
ElrsEr89?
Q
brea(?
Ease X1X :
STRUKTUR DATA - TI /4
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
42/57
ElrsEr89?
"aEaMa@u8Snr79?
Q
brea(?
Ease X2X : ElrsEr89?
"aEaMunur8Snr79?Q
brea(?
eault :
EoutLLSelesai. Te(an enter?
Q
brea(?
Q
Q
%etEh89?
elete8Snr79?Q
JJ
G! LATI3AN
Diberi(an oleh osen 5en%am5u 5aa saat 5ra(ti(um.
3! TUGAS
Diberi(an oleh osen 5en%am5u 5aa a(hir 5ra(ti(um.
Di(er@a(an i rumah an ilam5ir(an 5aa la5oran.
STRUKTUR DATA - TI /3
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
43/57
PERTEMUAN KE #$
%inar& Tree
A. TU-UAN :
Men%enal an memahami tentan% "inar' Tree Da5at membuat "inar' Tree
". T6ORI SIN7KAT
"inar' Tree aalah tree en%an sarat aalah tia5 noe han'a boleh memili(i ma(simal ua subtree
an (eua subtree tersebut harus ter5isah. Sesuai en%an einisi tersebut, ma(a tia5 noe alam
binar' tree han'a boleh memili(i 5alin% ban'a( ua Ehil.
7ambar +).+. "inar' Tree
Istilahistilah umum alam tree:
a. Preesesor noe 'an% beraa i atas noe tertentu.
b. SuEEesor noe 'an% beraa ibawah noe tertentu.
E. AnEestor seluruh noe 'an% terleta( sebelum noe tertentu an terleta( 5aa @alur 'an%
sama.. DesEenant seluruh noe 'an% terleta( sesuah noe tertentu an terleta( 5aa @alur 'an%
sama.
e. Parent 5reesesor satu le=el i atas satu noe.
.
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
44/57
000000000000000000000000000000000000000000000000000000000000000000000000000#3rama hdrsto3
#include
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
45/57
ode9t!3e 13%root; hile (3P%QFF) { i' (nenode0$in'o.e! < 30$in'o.e!) node baru lebih ecil dari 3
i' (30$iri) 3%30$iri; else {30$iri % nenode; 30$iri0$in'o.3osisi%(char1)" iri"; 30$iri0$in'o.no%nourut;brea; + else i' (nenode0$in'o.e! $ 30$in'o.e!) i' (30$anan) 3%30$anan; else {30$anan%nenode; 30$anan0$in'o.3osisi%(char1)" anan";
30$anan0$in'o.no%nourut;brea; + else { coutearch(30$iri,taret); else i' (taret $ 30$in'o.e!) 3 % ree>earch(30$anan, taret); return 3;+
void main(){ ode9t!3e 1root%QFF; ode9t!3e 13%root; Etem9t!3e in'o; data e in'o.e!%&; 3%root; ode9t!3e1 7%Maeode(in'o);
STRUKTUR DATA - TI )
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
46/57
root%Ensertree(root,7); data e 8 in'o.e!%5; 3%root;
7%Maeode(in'o); root%Ensertree(root,7); data e I in'o.e!%5; 3%root; 7%Maeode(in'o); root%Ensertree(root,7);
3%ree>earch(3,in'o.e!); i' (3) {
cout
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
47/57
=! TUGAS
Diberi(an oleh osen 5en%am5u 5aa a(hir 5ra(ti(um.
Di(er@a(an i rumah an ilam5ir(an 5aa la5oran.
STRUKTUR DATA - TI
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
48/57
PERTEMUAN KE #'
%inar& Tree
(Se"i $)
A. TU-UAN : Da5at mela(u(an menelusuran terhaa5 "inar' Tree
". T6ORI SIN7KAT
Pohon Telusur "iner aalah 5ohon biner 'an% 5aa setia5 noe men'im5an ata atau (unEi
'an% lebih besar ari semua noe 5aa sub tree (irin'a 'an% lebih (eEil ari semua noe 5aa sub
tree (anann'a. Paa noe tertentu, aa ti%a (un@un%an 'an% (ita la(u(an en%an aturan: (ita
men%un@un%i noe itu seniri? (ita melintasi sub5ohon (iri? (ita melintasi sub5ohon (anan. -i(a (ita
beri nama ti%a (un@un%an ini seba%ai , #, R, ma(a aa enam Eara 5enelusuran:
U # R # U R # R U
U R # R U # R # U
7ambar +/.+. Pohon "iner 'an% mem5un'ai )
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
49/57
void Enorder(ode9t!3e 1root, char 1s){i' (root){
Enorder(root0$iri," Uiri"); cout
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
50/57
EoutLLAn%(a 'an% iEari LL5ino.(e'LLenl?
EoutLL"eraa i 5osisi LL5ino.5osisi?
Q
else EoutLLTia( aa he...LLenl?
ree8root9? %etEh89?
Q
JJ
2. -alan(an an amati hasiln'a.
0. Telusuri @u%a binar' tree lain 'an% suah ibuat 5aa 5ertemuan beri(utn'a.
K! LATI3AN
Diberi(an oleh osen 5en%am5u 5aa saat 5ra(ti(um.
L! TUGAS
Diberi(an oleh osen 5en%am5u 5aa a(hir 5ra(ti(um.
Di(er@a(an i rumah an ilam5ir(an 5aa la5oran.
STRUKTUR DATA - TI 0
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
51/57
MODUL 1+
3AS3 TA6LES
M! TU=UAN >
o
Men%enal+ah Tablean+ahingo Men%etahui (elebihan al%oritma $ash
o Memilih Fun%si $ash "+ah un!tion(an Metoe metoe 5enan%anan u5li(asi (unEi
5aa ata atau tabra(an "!olliion(5aa tabel hash
o Mam5u membuat 5ro%ram 'an% men%im5lementasi(an (onse5 hash
N! TEORI SINGKAT
+ah TableJ Tabel hash i%una(an untu( men%ineB se(um5ulan arra' untu( memuah(an 5roses
5enEarian. Misal(an NIP alam sebuah Perusahaan men%%una(an 1 i%it, en%an emi(ian
nilain'a ber(isar antara ***** 33333. "ila men%%una(an arra) i5erlu(an arra)'an% mam5u
menam5un% +**.*** elemen. Fa(ta 'an% aa Perusahaan han'a memili(i +** 5e%awai. Tentu sa@a
5en%%unaan +**.*** elemen a(an membuat ban'a( ruan% tia( ter5a(ai J 5emborosan memori.#alu bera5a @umlah arra) 'an% sebai(n'a i%una(an a%ar 5enEarian ata menurut (unEi bisa
ila(u(an en%an Ee5atZ tentu sa@a i5erlu(an arra)'an% beru(uran (eEil teta5i bisa menam5un%
semua ata. #alu ba%aimana Eara memeta(an antara NIP en%an lo(asiArra)Z -awabann'a en%an
un%si $ash "hah #un!tion(.
Fun%si $ash aalah un%si 'an% i%una(an untu( mener@emah(an suatu nilai (unEi men@ai suatu
nilai 'an% inama(an alamat hash. Alamat hash inilah 'an% men'ata(an ine(s lo(asi alam arra).
Te(ni( 'an% memun%(in(an lo(asi suatu re!or$a5at i5eroleh en%an muah an Ee5at melalui
un%si hash inama(an a"inen%an Eara se5erti itu 5enEarian ata 5e%awai a5at ila(u(an
tan5a mela(u(an 5embanin%an terhaa5 (unEi lain.Arra)'an% i%una(an untu( men'im5an ata
en%an Eara hahing en%an nama tabel hash . Table hash itulah 'an% serin% isebut seba%aistru(tur ata 'an% i%una(an untu( men'im5an ata en%an asar un%si hash.
Me)i"i. F(n/si 3as.
Kriteria alam memilih un%si hash 5erlu i5ertimban%(an 5ertama Kom5utasi harus muah an
Ee5at (eua $arus men%hasil(an nilai tersebar ise5an@an% @an%(auan ine(s arra)%Metoe 'an%
i5a(ai untu( membentu( un%si hash 'aitu : Sisa Pemba%ian, Pemoton%an an Peli5atan "ol$ing(
Sisa Pe)*a/ian
Konse5 ari sisa 5emba%ian aalah memba%i nilai (unEi Misaln'a NIP 5aa ata 5e%awai en%an
suatu nilai an sisa 5emba%iann'alah 'an% i%una(an seba%ai alamat hash. SeEara matemati(a
un%si hash itulis men@ai :34-5 - )od ), )Bn
en%an :
( aalah (unEi
m aalah suatu bilan%an 5emba%i
n aalah @umlah ata
men%in%at ( mo m men%hasil(an bilan%an antara * sam5ai m+ ma(a a5abila lo(asi memori
8ine(s arra'9 berawal en%an +, hasil 5emba%ian 5erlu itambah en%an an%(a +. Den%an
emi(ian un%si hash beru5a
34-54- )od )5 C1
Pe)oton/an
Metoe 5emoton%an ila(u(an en%an men%abai(an ba%ian ba%ian tertentu alam (unEi an
men%%una(an 'an% tersisa seba%ai ine(s untu( men%a(ses ata alam tabel hash.
Pe"ipatan (*ldin)
Paa metoe 5eli5atan (unEi iba%iba%i men@ai bebera5a ba%ian misaln'a 5er ua i%it (emuian
i@umlah(an . $asiln'a i5oton% sehin%%a masu( @an%(auan ine(s alam tabel hash.
STRUKTUR DATA - TI 4
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
52/57
Menan/ani ta*ra-an (Clli"in)da"a) ta*e" .as.
A5a5un metoe 'an% i%una(an bisa sa@a menimbul(an ) buah (unEi atau lebih iter@emah(an oleh
un%si hash (e alam nilai 'an% sama. Situasi 'an% membuat bebera5a (unEi memili(i alamat hash
'an% sama atau isebut en%an tabra(an hash "hah !olliion(. Untu( men%atasin'a tera5at /te(ni( 'aitu : Pen%alamatan Terbu(a "pen A$$reing(, Pembentu(an rantai ".haining( an
Pen%alamatan "u(et "bu!ket a$$reing(
1! Pen/a"a)atan Ter*(-a (+pen Addre""in)
Paa 5en%alamatan terbu(a semua elemen isim5an alam tabel hash itu seniri. "ebera5a
5emeri(saan 'an% termasu( 5en%alamatan terbu(a sbb :
Pe)eri-saan "inear (linear pr!in)
Tabra(an hash itan%ani en%an menEari lo(asi tere(at 'an% masih (oson% atau 'an% i(enal
en%an 5emeri(saan linear. Aa5un un%si hash bisa men@ai :
.4-,i5 4.4-5Ci5 )od ), )
Pe)eri-saan K(adrati-'an% ila(u(an en%an urutan sbb :
.4-,i5 4.4-5Ci#5)od ), i
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
53/57
strin nama;
Uonstrutor :ataAash(int ni3, strin nama);
+;
class AashFinear{ 3rivate vector
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
54/57
i' (data[i]0$ni3 P% 0) delete data[i]; +
delete 3trerha3us;+ hasunction (3ubli) Menhasilan alamat hash berdasaran ni3int AashFinearhashunction(int ni3){ return ni3 Y uuranabel;+ insert (3ubli) Qntu men!isi3an data e tabel hashvoid AashFinearinsert(int ni3, strin nama){ int alamatAash % hashunction(ni3);
int i % &; hile ((data[alamatAash] P% QFF) 44 (data[alamatAash]0$ni3 P% 0)) { i' (i $ uuranabel) brea; Ueluar alau sudah 3enuh
@eroleh alamat beriutn!a alamatAash % (alamatAash ) Y uuranabel; i; Qntu menhitun sam3ai 3enuh +
i' (i < uuranabel) data[alamatAash] % ne :ataAash(ni3, nama);+ Bnd() (3ubli). Mencari data. ilai bali beru3a data namastrin AashFinearBnd(int ni3){ int alamatAash % hashunction(ni3); int i % ; hile (data[alamatAash] P% QFF) {
i' (i $ uuranabel) brea; Ueluar alau semua sudah dice
De nilai Beld i3 sama denan i3 i' (data[alamatAash]0$ni3 %% ni3) brea; Ueluar hile
@eroleh alamat beriutn!a alamatAash % (alamatAash ) Y uuranabel; i; Qntu menhitun sam3ai semua + i' ((i
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
55/57
remove (3ubli) 'alse 6ia aal menha3us i3 sebalin!a ruebool AashFinearremove(int ni3){ int alamatAash % hashunction(ni3);
int i % ; hile (data[alamatAash] P% QFF) { i' (i $ uuranabel) brea; Ueluar alau semua sudah dice
De nilai Beld i3 sama denan i3 i' (data[alamatAash]0$ni3 %% ni3) { *ebasan memori !an diunaan untu men!im3an data delete data[alamatAash];
2lihan e 3ointer !an men!ataan data terha3us data[alamatAash] % 3trerha3us; brea; Ueluar hile +
@eroleh alamat beriutn!a alamatAash % (alamatAash ) Y uuranabel; i; Qntu menhitun sam3ai semua +
i' ((i < uuranabel) 44 (data[alamatAash] P% QFF)) return true; else return 'alse; aal menha3us+ dis3la! (3ubli) Menam3ilan isi tabel hashvoid AashFineardis3la!(){ 'or (int i%&; i < uuranabel; i) {
i' (data[i] %% QFF) cout
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
56/57
int main(){ *uat tabel hash untu data
AashFinear tabel();
Memasuan data e dalam tabel hash tabel.insert(8, "2ndia"); tabel.insert(I, "/atna"); tabel.insert(J, ":ei"); tabel.insert(G, "2ri Zardi"); tabel.insert(8&, "Uarmila");
cout
-
7/24/2019 Modul Praktikum Kurikulum 2015 - Struktur Data TI
57/57
top related