struktur data c

7/25/2019 Struktur Data c

1/61

Bab 1. POINTER

Pointer merupakan tipe data berukuran 32 bit yang berisi satu nilai yang berpadanan

dengan alamat memori tertentu. Sebagai contoh, sebuah variabel P bertipe pointer

bernilai 0x00412!, berarti P menun"uk pada alamat memori 00412!. Pointer

dideklarasikan seperti variabel biasa dengan menambahkan tanda # $asterik% yang

menga&ali nama variabel.

'entuk (mum) *tipe data+ namaariabel-

ontoh) /loat # px-

Statement di atas mendeklarasikan variabel px yang merupakan pointer. Penyebutan

tipe data /loat berarti bah&a alamat memori yang ditun"uk oleh px dimaksudkan

untuk berisi data bertipe /loat.

ontoh Program)

1)

utput)


2/61

utput)


3/61

Bab 2. ARRAY

!rray adalah suatu struktur yang terdiri dari se"umlah elemen yang memiliki tipe data

yang sama. lemenelemen array tersusun secara sekuensial dalam memori komputer.

!rray dapat berupa satu dimensi, dua dimensi, tiga dimensi ataupun banyak dimensi

$multi dimensi%.

2.1. Array Satu Dimensi

!rray Satu dimensi tidak lain adalah kumpulan elemenelemen identik yang tersusun

dalam satu baris. lemenelemen tersebut memiliki tipe data yang sama, tetapi isi dari

elemen tersebut boleh berbeda.

lemen ke 0 1 2 3 4 5 6 7

8ilai 23 34 32 12 25 14 23 12 11 10

'entuk umum) *tipe data+ 8ama!rray9n: ;


4/61


5/61

utput)

2.2. Array Dua Dimensi

!rray dua dimensi sering digambarkan sebagai sebuah matriks, merupakan perluasan

dari array satu dimensi. >ika array satu dimensi hanya terdiri dari sebuah baris dan

beberapa kolom elemen, maka array dua dimensi terdiri dari beberapa baris dan

beberapa kolom elemen yang bertipe sama sehingga dapat digambarkan sebagai

berikut)

0 1 2 3 4


6/61

1 4 43 12 21 12 21

2 32 34 23 4 34 4

32 11 12 32 23 5 4

'entuk umum)

*tipe data+ 8ama!rray 9m:9n:-

!tau

*tipe data+ 8ama!rray 9m:9n: ; <


7/61


8/61


9/61

utput)


10/61

2.


11/61


12/61

utput)


13/61

Aatihan)

1. 'uat program menghitung pen"umlahan matrik 3x3.

2. 'uat program menghitung perkalian matrik 3x3.


14/61

Bab 3. STRUCTURE

Structure $struktur% adalah kumpulan elemenelemen data yang digabungkan men"adi

satu kesatuan. Basingmasing elemen data tersebut dikenal dengan sebutan /ield.

ield data tersebut dapat memiliki tipe data yang sama ataupun berbeda. Calaupun

/ield/ield tersebut berada dalam satu kesatuan, masingmasing /ield tersebut tetap

dapat diakses secara individual.

ield/ield tersebut digabungkan men"adi satu dengan tu"uan untuk kemudahan dalam

operasinya. Bisalnya !nda ingin mencatat datadata mahasis&a dan pela"ar dalam

sebuah program, (ntuk membedakannya !nda dapat membuat sebuah record

mahasis&a yang terdiri dari /ield nim, nama, alamat dan ipk serta sebuah record

pela"ar yang terdiri dari /ield/ield nama, nonurut, alamat dan "umnilai. Dengan

demikian akan lebih mudah untuk membedakan keduanya.

'entuk umum)

ontoh)

(ntuk menggunakan struktur, tulis nama struktur beserta dengan /ieldnya yangdipisahkan dengan tanda titik $E . E%. Bisalnya !nda ingin menulis nim seorang

mahasis&a ke layar maka penulisan yang benar adalah sebagai berikut)


15/61

>ika Pmhs adalah pointer bertipe mahasis&a# maka /ield dari Pmhs dapat diakses

dengan mengganti tanda titik dengan tanda panah $E E%.

out**mahasis&a%nim)

ontoh program)

1.

Aatihan)1. 'uat program menghitung durasi rental &arnet, dengan ketentuan

hit 30 d tik F 130


16/61

8ilai Iuru/)

8ilai akhir +6 ) !

6 +; nilai akhir + 50 ) '

50 +; nilai akhir + )

+; nilai akhir + 40 ) D

8ilai akhir *;40 )


17/61

Bab 4. LINKED LIST

Pada bab sebelumnya telah di"elaskan mengenai variabel array yang bersi/at statis

$ukuran dan urutannya sudah pasti%. Selain itu, ruang memori yang dipakai olehnya

tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program

di"alankan. (ntuk memecahkan masalah di atas, kita dapat menggunakan variabel

pointer. Jipe data pointer bersi/at dinamis, variabel akan dialokasikan hanya pada saat

dibutuhkan dan sesudah tidak dibutuhkan dapat direlokasikan kembali.

Setiap ingin menambahkan data, !nda selalu menggunakan variabel pointer yang

baru, akibatnya !nda akan membutuhkan banyak sekali pointer. leh karena itu, ada

baiknya "ika !nda hanya menggunakan satu variabel pointer sa"a untuk menyimpan

banyak data dengan metode yang kita sebut Ainked Aist. Ainked list adalah

sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap

elemennya terdiri dari dua bagian.

'entuk (mum )

in/otype K sebuah tipe terde/inisi yang menyimpan in/ormasi sebuah elemen list

next K address dari elemen berikutnya $suksesor%

>ika A adalah list, dan P adalah address, maka alamat elemen pertama list A dapat

diacu dengan notasi )

Sebelum digunakan harus dideklarasikan terlebih dahulu )

lemen yang diacu oleh P dapat dikonsultasi in/ormasinya dengan notasi )


18/61

1. 1. Aist l adalah list kosong, "ika irst$A% ; 8il

2. 2. lemen terakhir dikenali, dengan salah satu cara adalah karena

8ext$Aast% ; 8il 8il adalah pengganti 8ull, perubahan ini dituliskan dengan

Lde/ine 8il 8ull


19/61

4.1. Single Linked List

00001000 00001004 00001006

ield bertipe data ield bertipe pointertertentu untuk untuk menun"uk ke

menampung sebuah node berikutnyadata@in/ormasi

Pada gambar di atas tampak bah&a sebuah data terletak pada sebuah lokasi memori area.

Jempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal

dengan sebutan node@simpul. Setiap node memiliki pointer yang menun"uk ke simpul

berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah

variabel pointer. Susunan berupa untaian semacam ini disebut Single Ainked Aist $8(AA

memilik nilai khusus yang artinya tidak menun"uk ke manamana. 'iasanya Ainked Aist

pada titik akhirnya akan menun"uk ke 8(AA%.

Pembuatan Single Ainked Aist dapat menggunakan 2 metode)

G K AM $Aast Mn irst ut%, aplikasinya ) Stack $Jumpukan%

G K M $irst Mn irst ut%, aplikasinya ) Nueue $!ntrean%

LIFO ( Last In F!st O"t#

Ai/o adalah suatu metode pembuatan Ainked Aist di mana data yang masuk paling akhir

adalah data yang keluar paling a&al. Ial ini dapat dianalogikan $dalam kehidupan sehari

hari% dengan saat !nda menumpuk barang seperti digambarkan diba&ah ini. Pembuatan


20/61

sebuah simpul dalam suatu linked list seperti digambarkan diba&ah ini. >ika linked list

dibuat dengan metode AM, ter"adi penambahan @ Mnsert simpul di belakang, dikenal

dengan istilah M8SFJ.

Oeadaan mulamula Setelah ditumpuk adalah kosong

Gambar. Ilustrasi Single Linked List dengan metode LIFO

FIFO (Fs!t In Fs!t O"t#

M adalah suatu metode pembuatan Ainked Aist di mana data yang masuk paling a&al

adalah data yang keluar paling a&al "uga. Ial ini dapat di analogikan $dalam kehidupan

seharihari%, misalnya saat sekelompok orang yang datang $8N((% mengantri

hendak membeli tiket di loket.

>ika linked list dibuat dengan metode M, ter"adi penambahan @ Mnsert simpul didepan.

4.3. Double Linked List

Salah satu kelemahan single linked list adalah pointer $penun"uk% hanya dapat bergerak

satu arah sa"a, ma"u@ mundur, atau kanan@kiri sehingga pencarian data pada single linked

list hanya dapat bergerak dalam satu arah sa"a. (ntuk mengatasi kelemahan tersebut,

anda dapat menggunakan metode double linked list. Ainked list ini dikenal dengan nama

Ainked list berpointer anda atau Double Ainked Aist.


21/61

4.4. Circular Double Linked List

Mni adalah double linked list yang simpul terakhirnya menun"uk ke simpul terakhirnya

menun"uk ke simpul a&alnya menun"uk ke simpul akhir sehingga membentuk suatu

lingkaran.

O$%!as&O$%!as 'an a)a $a)a Ln*%) Lst

Insert

Mstilah Mnsert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

Ismpty

ungsi ini menentukan apakah linked list kosong atau tidak.

!ind !irst

ungsi ini mencari elemen pertama dari linked list

!ind "e#t

ungsi ini mencari elemen sesudah elemen yang ditun"uk no&.

$etrie%e

ungsi ini mengambil elemen yang ditun"uk oleh no&. lemen tersebut lalu dikembalikan

oleh /ungsi.

&pdate

ungsi ini mengubah elemen yang ditun"uk oleh no& dengan isi dari sesuatu.

Delete "o'

ungsi ini menghapus elemen yang ditun"uk oleh no&. >ika yang dihapus adalah elemen

pertama dari linked list $head%, head akan berpindah ke elemen berikut.


22/61

Delete (ead

ungsi ini menghapus elemen yang ditun"uk head. Iead berpindah ke elemen

sesudahnya.

Clear

ungsi ini menghapus linked list yang sudah ada. ungsi ini &a"ib dilakukan bila anda

ingin mengakhiri program yang menggunakan linked list. >ika anda melakukannya, data

data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di

dalam memori.

ontoh Program)

1. Bembuat Single Ainked Aist


23/61


24/61


25/61

utput)

2. Pencarian 8ilai Jerkecil dan 8ilai Jerbesar dalam sebuah Single Ainked Aist


26/61


27/61


28/61

utput)


29/61

Bab 5. STACK

).1. De*inisi Stack

Stack adalah suatu tumpukan dari benda. Oonsep utamanya adalah AM $Aast Mn irst

ut%, benda yang terakhir masuk dalam stack akan men"adi benda pertama yang

dikeluarkan dari stack.

Oeadaan mulamula Setelah ditumpuk adalah kosong

Pada gambar di atas, "ika kita ingin mengambil sesuatu dari tumpukan maka kita harus

mengambil benda paling atas dahulu, yakni compo. Bisalnya "ika D langsung

diambil, compo akan "atuh. Prinsip stack ini bisa diterapkan dalam pemrograman. Di H

H, ada dua cara penerapan prinsip stack, yakni dengan a!!a' dan +n*%) +st. Setidaknya

stack haruslah memiliki operasioperasi sebagai berikut.

Push (ntuk menambahkan item pada tumpukan paling atas

Pop (ntuk mengambil item teratas

lear (ntuk mengosongkan stack

Msmpty (ntuk memeriksa apakah stack kosong

Msull (ntuk memeriksa apakah stack sudah penuh

Fetreive (ntuk mendapatkan nilai dari item teratas


30/61

).2. Stack dengan Array

Sesuai dengan si/at stack, pengambilan @ penghapusan di elemen dalam stack harus

dimulai dari elemen teratas.

O$%!as&,$%!as $a)a Sta-* )%nan A!!a'

Is!ull

ungsi ini memeriksa apakah stack yang ada sudah penuh. Stack penuh "ika puncak stack

terdapat tepat di ba&ah "umlah maksimum yang dapat ditampung stack atau dengan kata

lain Jop ; B!QRSJ!O 1.

+ush

ungsi ini menambahkan sebuah elemen ke dalam stack dan tidak bisa dilakukan lagi

"ika stack sudah penuh.

Ismpty

ungsi menentukan apakah stack kosong atau tidak. Janda bah&a stack kosong adalah

Jop bernilai kurang dari nol.

+op

ungsi ini mengambil elemen teratas dari stack dengan syarat stack tidak boleh kosong.

Clear

ungsi ini mengosongkan stack dengan cara mengeset Jop dengan 1. >ika Jop bernilai

kurang dari nol maka stack dianggap kosong.

$etrei%e

ungsi ini untuk melihat nilai yang berada pada posisi tumpukan teratas.


31/61

ontoh Program )

Program untuk Mnsert $Push% 8ilai dan Delete $Pop% 8ilai dalam Stack


32/61

utput )


33/61

).3. Double Stack dengan Array

Betode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian

memori dalam pembuatan dua stack dengan array. Mntinya adalah penggunaan hanya

sebuah array untuk menampung dua stack. Jampak "elas bah&a sebuah array dapat dibagi

untuk dua stack, stack 1 bergerak ke atas dan stack 2 bergerak ke ba&ah. >ika Jop1

$elemen teratas dari Stack 1% bertemu dengan Jop 2 $elemen teratas dari Stack 2% maka

double stack telah penuh. Mmplementasi double stack dengan array adalah dengan

meman/aatkan operasioperasi yang tidak berbeda "auh dengan operasi single stack

dengan array.

O$%!as&,$%!as D,"b+% Sta-* A!!a'

Is!ull

ungsi ini memeriksa apakah double stack sudah penuh. Stack dianggap penuh "ika

Jop90: dan Jop91: bersentuhan sehingga stack tida memiliki ruang kosong. Dengan kata

lain, $Jop90: H 1% + Jop91:.

+ush

ungsi ini memasukkan sebuah elemen ke salah satu stack.

Ismpty

ungsi memeriksa apakah stack pertama atau stack kedua kosong. Stack pertama

dianggap kosong "ika puncak stack bernilai kurang dari nol, sedangkan stack kedua

dianggap kosong "ika puncak stack sama atau melebihi B!QRSJ!O.

+op

ungsi ini mengeluarkan elemen teratas dari salah satu stack


34/61

Clear

ungsi ini mengosongkan salah satu stack.

).4. Stack dengan Single Linked List

Selain implementasi stack dengan array seperti telah di"elasnkan sebelumnya, ada cara

lain untuk mengimplementasi stack dalam HH, yakni dengan single linked list.

Oeunggulannya dibandingkan array tebtu sa"a adalah penggunaan alokasi memori yang

dinamis sehingga menghindari pemborosan memori. Bisalnya sa"a pada stack dengan

array disediakan tempat untuk stack berisi 10 elemen, sementara ketika dipakai oleh

user stack hanya diisi 0 elemen, maka telah ter"adi pemborosan memori untuk sisa 100elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan

akan sesuai dengan banyaknya elemen yang mengisi stack. leh karena itu pula dalam

stack dengan linked list tidak ada istilah "++, sebab biasanya program tidak menentukan

"umlah elemen stack yang mungkin ada $kecuali "ika sudah dibatasi oleh pembuatnya%.

8amun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh

"umlah memori yang tersedia.

O$%!as&,$%!as "nt"* Sta-* )%nan Ln*%) Lst

Ismpty

ungsi memeriksa apakah stack yang adamasih kosong.

+ush

ungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam

single linked list biasa.

+op

ungsi ini mengeluarkan elemen teratas dari stack.


35/61

Clear

ungsi ini akan menghapus stack yang ada.

ontoh Program)1. Stack dengan Single Ainked Aist


36/61


37/61

utput)

Aatihan) Oasus Benara Ianoi Benggunakan Jurbo HH 4. Bemindahkan lempengan

dari menara ! ke menara ' dengan perantara menara dengan "umlah data ; 3 $0, 5,

100%. Step program)1. 1. Pindahkan batu 0 dari ! ke 2. 2. Pindahkan batu 5 dari ! ke

3. 3. Pindahkan batu 100 dari ! ke '

4. 4. Pindahkan batu 5 dari ke '. . Pindahkan batu 0 dari ke '

O"t$"t/


38/61


39/61

Bab . UEUE

,.1. De*inisi -ueue

>ika diartikan secara hara/iah, Tueue berarti antrian, Tueue merupakan salah satu contoh

aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam

kehiduypan seharihari, misalnya saat !nda mengantri di loket untuk membeli tiket.

Mstilah yang cukup sering dipakai seseorang masuk dalam sebuah antrian adalah %n"%"%.

Dalam suatu antrian, yang dating terlebih dahulu akan dilayani lebih dahulu. Mstilah yang

sering dipakai bila seseorang keluar dari antrian adalah )%"%"%. Calaupun berbeda

implementasi, struktur data Tueue setidaknya harus memiliki operasioperasi sebagai

berikut )

nNueue Bemasukkan data ke dalam antrian

DeNueue Bengeluarkan data terdepan dari antrian

lear Benghapus seluruh antrian

Msmpty Bemeriksa apakah antrian kosong

Msull Bemeriksa apakah antrian penuh

,.2. Implementasi -ueue dengan Linear Array

Ln%a! A!!a'

Ainear array adalah suatu array yang dibuat seakanakan merupakan suatu garis lurus

dengan satu pintu masuk dan satu pintu keluar. 'erikut ini diberikan deklarasi kelas

Nueue Ainear sebagai implementasi dari Nueue menggunakan linear array. Dalam

prakteknya, anda dapat menggantinya sesuai dengan kebutuhan !nda. Data diakses

dengan /ield data, sedangkan indeks item pertama dan terakhir disimpan dalam /ield

Iead dan Jail. Oonstruktor akan menginisialisasikan nilai Iead dan Jail dengan 1 untuk

menun"ukkan bah&a antrian masih kosong dan

mengalokasikan data sebanyak B!QRN(( yang ditun"uk oleh Data. Destruktor akan


40/61

mengosongkan antrian kembali dan mendealokasikan memori yang digunakan oleh

antrian.

O$%!as&O$%!as "%"% )%nan Ln%a! A!!a'

Ismpty

ungsi Msmpty berguna untuk mengecek apakah Tueue masih kosong atau sudah berisi

data. hal ini dilakukan dengan mengecek apakah tail bernilai 1 atau tidak. 8ilai 1

menandakan bah&a Tueue masih kosong.

Is!ull

ungsi Msull berguna untuk mengecek apakah Tueue sudah penuh atau masih bisa

menampung data dengan cara mengecek apakah nilai tail sudah sama dengan "umlah

maksimal Tueue. >ika nilai keduanya sama, berarti Tueue sudah penuh.

n-ueue

ungsi nNueue berguna untuk memasukkan sebuah elemen dalam Tueue.

De-ueue

ungsi DeNueue berguna untuk mengambil sebuah elemen dari Tueue. perasi ini sering

disebut "uga s%!%. Ial ini dilakukan dengan cara memindahkan se"auh satu langkah ke

posisi di depannya sehingga otomatis elemen yang paling depan akan tertimpa dengan

elemen yang terletak di belakangnya.

Clear

ungsi lear berguna untuk menghapus semua lemen dalam Tueue dengan "alan

mengeluarkan semua elemen tersebut satu per satu hingga Tueue kosong dengan


41/61

meman/aatkan /ungsi DNueue.

,.3. Implementasi -ueue dengan Circular Array

C!-"+a! A!!a'

ircular array adalah suatu array yang dibuat seakanakan merupakan sebuah lingkaran

dengan titik a&al $head% dan titik akhir $tail% saling bersebelahan "ika array tersebut masih

kosong. Posisi head dan tail pada gambar diatas adalah bebas asalkan saling

bersebelahan. 'erikut ini diberikan deklarasi kelas Nueue ircular sebagai implementasi

circular array. Dalam prakteknya, !nda dapat menggantikanny sesuai dengan kebutuhan

!nda. Data diakses dengan /ield data, sedangkan indeks itemn pertama dan terakhir

disimpan dalam /ield Iead dan Jail. Oonstruktor akan menginisialisasi nilai Iead dan

Jail dengan 0 dan B!QN((1 untuk menun"ukkan bah&a antrian masih kosong dan

mengalokasikan data sebanyak B!QN(( yang ditun"uk oleh Data. destruktor akan

mengosongkan antrian kembali dan mendealokasikan memori yang digunakan oleh

antrian.

O$%!as&O$%!as "%"% )%nan C!-"+a! A!!a'

Ismpty

ungsi Msmpty berguna untuk mengecek apakah Nueue masih kosong atau sudah berisi.

Ial ini dilakukan dengan mengecek apakah tail masih terletak bersebelahan dengan head

dan tail lebih besar dari head atau tidak. >ika benar, maka Tueue masih kosong.

Is!ull

ungsi Msull berguna untuk mengecek apakah Tueue sudah penuh atau masih bias

menampung data dengan cara mengecek apakah tempat yang masih kosong tinggal

satu atau tidak $untuk membedakan dengan empty dimana semua tempat kosong%. >ika

benar berarti Tueue penuh.


42/61

n-ueue

ungsi nNueue berguna untuk memasukkan sebuah elemen ke dalam Tueue tail dan

head mulamula bernilai nol $0%.

De-ueue

DeNueue berguna untuk mengambil sebuah elemen dari Tueue. Ial ini dilakukan dengan

cara memindahkan posisi head satu langkah ke belakang.

,.4. Implementasi -ueue dengan Double Linked List

Selain menggunakan array, Tueue "uga dapat dibuat dengan linked list. Betode linked

list yang digunakan adalah double linked list.

O$%!as&,$%!as "%"% )%nan D,"b+% Ln*%) Lst

Ismpty

ungsi Msmpty berguna untuk mengecek apakah Tueue masih kosong atau sudah berisi

data. Ial ini dilakukan dengan mengecek apakah head masih menun"ukkan pada 8ull

atau tidak. >ika benar berarti Tueue masih kosong.

Is!ull

ungsi Msull berguna untuk mengecek apakah Tueue sudah penuh atau masih bias

menampung data dengan cara mengecek apakah >umlah Nueue sudah sama dengan

B!QRN(( atau belum. >ika benar maka Tueue sudah penuh.

n-ueue

ungsi nNueue berguna untuk memasukkan sebuah elemen ke dalam Tueue $head dan

tail mulamula meun"ukkan ke 8(AA%.


43/61

De-ueue

Procedure DeNueue berguna untuk mengambil sebuah elemen dari Tueue. Ial ini

dilakukan dengan cara menghapus satu simpul yang terletak paling depan $head%.

ontoh Program )

1. Nueue dengan Benggunakan !rray


44/61


45/61

utput)

2. Nueue menggunakan Ainked Aist


46/61


47/61


48/61

utput)

.1. De*inisi /ree

Jree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan

hubungan yang bersi/at hierarkis $hubungan one to many% antara elemenelemen. Jree

bias dide/inisikan sebagai kumpulan simpul@node dengan elemen khusus yang disebut

Foot. 8otde lainnya terbagi men"adi himpunanhimpunan yang saling tak berhubungan

satu sama lain $disebut Subtree%. (ntuk lebih "elasnya, di ba&ah akan diuraikan istilah

istilah umum dalam tree.

P!%)%-%ss,! 8ode yang berada di atas node tertentu

S"--%ss,! 8ode yang berada diba&ah node tertentu

An-%st,! Seluruh node yang terletak sebelum node tertentu dan terletak

pada "alur yang sama

D%s-%n)ant Seluruh node yang terletak sebelum node tertentu dan terletak

pada "alur yang sama

Pa!%nt Predecessor satu level di atas suatu node

C+) Successor satu level di ba&ah suatu node

Sb+n 8odenode yang memiliki parent yang sama dengan suatu

node


49/61

S"bt!%% 'agian dari tree yang berupa suatu node beserta descendantnya

dan memiliki semua karakteristik dari tree tersebut.

S% 'anyaknya node dalam suatu tree

6%t 'anyaknya tingkatan @ level dalam suatu tree

R,,t Satusatunya node khususdala

mtree yang tak punyak

predecessor

L%a 8odenode dalam tree yang tak memiliki successor

D%!%% 'anyaknya child yang dimiliki suatu node

.2. 7%ns&7%ns T!%%0inary

/ree

'inary Jree adalah tree dengan syarat bah&a tiap node hanya boleh memiliki maksimal

dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan de/inisi tersebut tiap

node dalam binary tree hanya boleh memiliki paling banyak dua child. >enis>enis 'inary

Jree )

!ull 0inary /ree

>enis binary tree ini tiap nodenya $kecuali lea/% memiliki dua child dan tiap subtree harus

mempunyai pan"ang path yang sama.

Complete 0inary /ree

>enis ini mirip dengan ull 'inary Jree, namun tiap subtree boleh memiliki pan"ang path

yang berbeda dan setiap node kecuali lea/ hanya boleh memiliki 2 child.

Ske'ed 0inary /ree

Ske&ed 'inary Jree adalah 'inary Jree yang semua nodenya $kecuali lea/% hanya

memiliki satu child.


50/61

Implementasi 0inary /ree

'inary tree dapat diimplementasikan dalam HH dengan menggunakan double linkedlist.

.3. O$%!as&O$%!as $a)a Bna!' T!%%

reate Bembentuk binary tree baru yang masih kosong

lear Bengosongkan binary tree yang sudah ada

mpty unction untuk memeriksa apakah binary tree masih kosong

Mnsert Bemasukkan sebuah node ke dalam tree. !da tiga pilihan

insert ) sebagai root, le/t child, atau right child. Ohusus insert

sebagai root, tree harus dalam keadaan kosong

ind Bencari root, parent, le/t child, atau right child dari suatu

node. $tree tidak boleh kosong%.

(pdate Bengubah isi dari node yang ditun"uk oleh pointer curret

$Jree tidak boleh kosong%

Fetrieve Bengetahui isi dari node yang ditun"uk oleh pointer current

$Jree tidak boleh kosong%

DeleteSub Benghapus sebuah subtree $node beserta seluruh descendantnya% yang ditun"uk current. Jree tidak boleh kosong. Setelah

itu, pointer current dakan berpindah ke parent dari node yang

dihapus.

haracteristic Bengetahui karakteristik dari suatu tree, yakni) si?e, height,

serta average length. Jree tidak boleh kosong.

Jraverse Bengun"ungi seluruh nodenode pada tree, masingmasing

sekali. Iasilnya adalah urutan in/ormasi secara linear yang

tersimpan dalam tree. !da tiga cara traverse,yaitu Prerder,

Mnrder, dan Postrder.

Aangkahlangkah Jranverse )

G K Prerder ) cetak isi node yang dikun"ungi, kun"ungi Ae/t hild, kun"ungi


51/61

Fight hild

G K Mnrder ) kun"ungi Ae/t hild, cetak isi node yang dikun"ungi, kun"ungi

Fight hildG K Postrder ) kun"ungi Ae/t hild, kun"ungi Fight hild cetak isi node yang

dikun"ungi.

.4. 0inary Search /ree

'inary Jree ini memiliki si/at dimana semua le/t child harus lebih kecil dari pada right

child dan parentnya. Semua right child "uga harus lebih besar dari le/t child serta parent

nya. 'inary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu

kesulitan dalam searching @ pendarian node tertentu dalam binary tree. Pada dasarnya

operasi dalam 'inary Search Jree sama dengan 'inary Jree biasa, kecuali pada operasi

insert, update, dan delete.

Insert

Pada 'inary Search Jree insert dilakukan setelah lokasi yang tepat ditemukan $lokasi

tidak ditentukan oleh user sendiri %.

&pdate

(pdate ini seperti yang ada pada 'inary Jree biasa, namun di sini update akan

berpengaruh pada posisi node tersebut selan"utnya. 'ila update mengakibatkan tree

tersebut bukan 'inary Search Jree lagi, harus dilakukan perubahan pada tree dengan

melakukan rotasi supaya tetap men"adi 'inary Search Jree.

Delete

Seperti halnya update, delete dalam 'inary Search Jree "uga turut mempengaruhi

struktur dari tree tersebut.

A8L T!%%

!A Jree adalah 'inary Search Jree yang memiliki perbedaan tinggi@ level maksimal 1


52/61

antara subtree kiri dan subtree kanan. !A Jree muncul untuk menyeimbangkan 'inary

Search Jree. Dengan !A Jree, &aktu pencarian dan bentuk tree dapat dipersingkat dan

disederhanakan. Selain !A Jree, terdapat pula Ieight 'alanced n Jree, yakni 'inary

Search Jree yang memiliki perbedaan level antara subtree kiri dan subtree kanan

maksimal adalah n sehingga dengan kata lain !A Jree adalah Ieight 'alanced 1 Jree.

(ntuk memudahkan dalam menyeimbangkan tree, digunakan simbolsimbol 'antu )

$tanda minus% ) digunakan apabila Subtree kiri lebih pan"ang dari Subtree kanan.

H $tanda plus% ) digunakan apabila Subtree kanan lebih pan"ang dari Subtree kiri.

0 $nol% ) digunakan apabila Subtree kiri dan Subtree kanan mempunyai

height yang sama.

DAFTAR ISTILA6&ISTILA6

A+,!t9a ) Aangkahlangkah menyelesaikan suatu masalah yang disusun

secara logis dan berurutan

An9as ) ambar yang tampak bergerak, terdiri dari banyak gambargambar

tunggal $disebut /rame% yang ditampilkan satu per satu secara

bergantian dengan cepat sehingga ob"ek dalam gambar tampak

seolaholah bergerak.

A!!a' ) Struktur data yang memiliki banyak elemen di dalamnya, dengan

masingmasing elemen memiliki tipe data yang sama.

C+%a! ) Benghapus secara keseluruhan, biasanya digunakan sebagai nama

/ungsi@metode yang bertu"uan untuk mengosongkan list atau

menghapus keseluruhan elemen.

C,ns,+% ) Mstilah dalam komputer yang menun"uk pada antarmukaantara pemakai dengan komputer yang berbasiskan teks. ara

ker"a konsol sangat sederhana yaitu menggunakan standar

input untuk membaca input dari keyboard dan standar output

untuk menampilkan teks ke layer monitor.


53/61

Data ) Mn/ormasi yang disimpan komputer, dapat berbentuk teks,

gambar, suara, video, dan sebagainya.

D%+%t% ) Benghapus sebuah elemen, biasanya digunakan sebagai nama

/ungsi@metode yang bertu"uan untuk menghapus sebuah

elemen dalam suatu list@tree

D%!%t

%,9%t!-) Deretan bilangan yang setiap bilangan merupakan hasil kali

bilangan sebelumnya dengan suatu konstanta.

D%st!"*t,! ) Betode khusus dalam sebuah kelas untuk menghapus ob"ek

hasil instansiasi kelas tersebut

D9%ns ) >umlah indek yang diperlukan untuk menyatakan sebuah

elemen dalam array

E+%9%n ) Sebuah data tunggal yang paling kecil dari sebuah array atau

list. Data tunggal disini tidak perlu data sederhana, melainkan

bisa berupa kumpulan data atau list yang lain.

E9$t' ) Oeadaan di mana list ada dalam keadaan kosong

Fb,na-- ) 'arisan bilangan yang setiap bilangan merupakan "umlah dari

dua bilangan sebelumnya.

F%+) ) Data yang dimiliki oleh sebuah ob"ek

FIFO ) irst Mn irst ut si/at suatu kumpulan data. "ika sebuah

elemen ! dimasukkan lebihdulu

dari

' maka ! harus

dikeluarkan dulu dari '

FPB ) aktor Persekutuan terbesar, /aktor yang paling besar "ika

se"umlah bilangan memiliki beberapa /aktor yang sama.

F"++ ) Oeadaan di mana list penuh, tidak boleh menerima data lagi

F"ns ) Suatu modul atau bagian program yang menger"akan suatu


54/61

69$"nan

In)%*s ) )

program tertentu. Oumpulan dari ob"ekob"ek, misalnya

sebuah himpunan dari buahbuahan dapat terdiri dari pisang,

mangga, "ambu dll. 'ilangan yang digunakan untukmenyatakan posisi suatu

In$"t )

elemen dalam array atau list. Data masukkan, dalam /ungsiberarti parameter yang dimasukkan, sedangkan dalam program

secara keseluruhan

berarti data yang dimasukkan pemakai, bias melalui

Ins%!t )

parameter program, /ile maupun le&at keyboard Bemasukkan

sebuah elemen baru ke dalam list. 'iasanya insert dilakukanbaik di tengahtengah list, a&al, maupun di

akhir list.

It%!as ) Perulangan dengan struktur perulangan, &hile, do &hile,

K%+as )

maupun /or. Suatu struktur yang digunakan sebagai template

bagi ob"ek

K,9$+as )

ob"ek yang sama si/atnya. Proses mener"emahkan bahasasumber $source code% ke dalam

K,9$+%!

K,nst!"*t,! ) )

bahasa lain, biasanya bahasa mesin, untuk dapat di"alankanlangsung oleh computer melalui system operasi. Program

yang menger"akan kompilasi. Betode khusus yang dimiliki

suatu kelas untuk membentuk

Lb!a!' )

suatu ob"ek baru berdasarkan kelas tersebut Oumpulan /ungsi,makro, template, dan kelas yang disediakan

LIFO Ln*%)

Lst) )

bersama compiler HH. Aast Mn isrt ut, si/at kumpulan data,kebalikan dari M Aist yang didesain dengan cara

mende/inisikan sebuah elemen yang memiliki hubungan atau

link dengan elemen lain yang

:at!*s


55/61

:%t,)% Ob;%*

O"t$"t P,nt%!

P,$

P!9a

P"s "%"%

R%-,!)

R%*"!s

S,!t S,"!-% C,)%

dihubungkan dengan elemen yang lain lagi.

) Dalam matematika berarti kumpulan bilangan yang disusun dalam bentuk kolom dan

baris.

) ungsi yang dimiliki suatu ob"ek

) Struktur data yang terdiri dari data yang lebih sederhana yang disebut /ield yang

memiliki operasi sendiri untuk menangani datadata yang dimilikinya.

) Data yang dihasilkan oleh program

) Jype data khusus yang pada umumnya berukuran 32 bit yang ber/ungsi untuk


56/61

menampung bilangan tertentu yang menun"uk pada lokasi memory tertentu

) Bengeluarkan satu elemen dari dalam list dengan cara menyalin data elemen tersebut,

kemudian menghapus elemen tersebut dari list biasanya digunakan untuk stack.

) 'ilangan yang tidak memiliki /aktor selain 1 dan bilangan itu sendiri.

) Bemasukkan sebuah elemen baru ke dalam list.

) Struktur list dengan si/at M, cara ker"anya seperti antrian manusia.

) Struktur data yang terdiri dari satu atau lebih elemen yang tipe data bias berbeda.

) >enis perulangan yang tidak menggunakan struktur perulangan, tetapi dengan

memanggil /ungsi yang bersangkutan.

) Benyusun elemenelemen suatu list secara berurutan.

) Program yang ditulis menggunakan bahasa pemrograman tertentu. Oode sumber

belum dapat di"alankan oleh komputer dan perlu men"alani proses kompilasi sehingga

dapat di"alankan.

Sta-* ) Aist yang memiliki si/ar AM. Data yang hendak di keluarkan

dari stack haruslah data yang paling terakhir dari stack.

STL ) Standar Jemplete Aibrary merupakan kumpulan yang

disertakan dalam setiap compiler HH yang memenuhi standar

!8SMH

Hyang menyediakan berbagai struktur data,

algoritma dan template yang sering dipakai.

St!%a9 ) !liran merupakan konsep dalam HH untuk input dan ouput

data tanpa memperdulikan isi data maupun media

penampung data tersebut.

St!"*t"!

*,nt!,+

) Struktur yang digunakan untuk mengontrol "alannya program.

T%*s ) Data yang terdiri dari karakterkarakter yang dapat dibaca

$huru/ bilangan, tanda baca%.

T!%% ) Suatu struktur data yang setiap elemen terhubung sedemikian

rupa sehingga berbentuk seperti pohon.


57/61

ontohProgram)

1.


58/61


59/61


60/61

utput)


61/61

struktur data c

Documents