modul praktikum kurikulum 2015 - struktur data ti

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

)*+


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


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


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(.


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.


6/57

#include


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.


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


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



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


11/57

+void mere(int lo,int mid,int hih){int h,i,6,b[5&],;

h%lo;i%lo;6%mid;hile((h


12/57

'or(i%;i


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%.


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


15/57

cin$$n;

ub%n; cout


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.


17/57

#include


18/57

int cari; cin$$cari; 3encarian int hasil;

hasil % binar!9s(data, siHe, cari); i' (hasil%%&) cout


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


32/57

STRUKTUR DATA - TI )3


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 /*


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


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 /)


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


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 /


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


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 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##?



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


bantuGHawal?

while 8bantuGNU##9

EoutLLbantumasu((anLL ?

bantuGbantu(anan?

Q

EoutLLenl?

Q

=oi "aEaMunur8Senerai7ana H9


bantuGHa(hir? while 8bantuGNU##9

EoutLLbantumasu((anLL ?

bantuGbantu(iri?

Q

EoutLLenl?



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 :



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


3! TUGAS





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.

.


44/57

000000000000000000000000000000000000000000000000000000000000000000000000000#3rama hdrsto3

#include


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 )


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


47/57

=! TUGAS



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 )


49/57

void Enorder(ode9t!3e 1root, char 1s){i' (root){

Enorder(root0$iri," Uiri"); cout


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


L! TUGAS





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.



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


53/57

strin nama;

Uonstrutor :ataAash(int ni3, strin nama);

+;

class AashFinear{ 3rivate vector


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


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


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


57/57

modul praktikum kurikulum 2015 - struktur data ti

Documents