Download - Struktur Data

Transcript
Page 1: Struktur Data

Halaman 1

STRUKTUR DATASTRUKTUR DATA

PengajarPengajarJaidanJaidan JauhariJauhari, MT, MT

AlamatAlamat [email protected][email protected]

[email protected][email protected]

DisarikanDisarikan Dari Dari BerbagaiBerbagai SumberSumber, , TerutamaTerutama Dari Diktat Dari Diktat StrukturStruktur Data Data InformatikaInformatikaITB ITB KaranganKarangan Dr. Dr. InggrianiInggriani LiemLiem

Page 2: Struktur Data

Halaman 2

SILABUS MATERI KULIAHSILABUS MATERI KULIAH

Pengantar Struktur DataReview Record dan ArrayStack (Tumpukan)Queue (Antrian)Linked List dan Variasi ListMultiListPohon BinerGraph

Page 3: Struktur Data

Halaman 3

BUKU SUMBERBUKU SUMBER1. Inggriani Liem. 1997. Diktat Kuliah Algoritma dan

Pemrograman Prosedural. Bandung : ITB2. Inggriani Liem. 2003. Diktat Kuliah Struktur Data.

Bandung : ITB3. Rinaldi Munir. 2003. Algoritma dan Pemrograman II.

Bandung : Penerbit Informatika4. Bambang Wahyudi. 2004. Struktur Data dan Algoritma.

Yogyakarta : Andi Offset5. Dwi Sanjaya. 2001. Bertualang dengan Struktur Data di

Planet Pascal. Yogyakarta : JJ Learning6. P. Insap Santoso.1997. Struktur Data dengan Turbo

Pascal. Yogyakarta : Andi Offset

Page 4: Struktur Data

Halaman 4

KomponenKomponen PenilaianPenilaian

Tugas 20%Ujian 1 20 % (Pertemuan ke-4)Ujian 2 20% (Pertemuan ke-8)Ujian 3 20% (Pertemuan ke-12)Ujian Akhir Semester 20%

Page 5: Struktur Data

Halaman 5

AturanAturan dandan SanksiSanksi--sanksisanksiKehadiran minimal 80%, kurang dari 80% tidak lulus (mendapat nilai E)Keterlambatan maksimal 10 menit (Lebih dari 10 menit tidakdiijinkan memasuki ruangan)Pengumpulan Tugas yang melebihi waktu yang telah ditentukanakan diberikan nilai nolKecurangan dalam bentuk apapun akan mendapatkan nilai EMahasiswa berpakaian rapi dan sopan, yang ditunjukkan antara lain 1. Memakai sepatu tertutup2. Memakai baju berkerah3. Tidak memakai aksesoris yang tidak diijinkan4. Tidak memakai pakaian yang kurang dasar atau lebih dasar5. dan lain-lainSelama perkuliahan berlangsung mahasiswa tidak diijinkanmeninggalkan ruang kuliah kecuali sangat terpaksa dan itupunharus membuat surat ijin dan hanya boleh satu kali

Page 6: Struktur Data

Halaman 6

PENGERTIAN STRUKTUR DATAPENGERTIAN STRUKTUR DATA

Struktur data adalah cara menyimpan ataumerepresentasikan data di dalam komputer agar bisa dipakai secara efisien

Sedangkan data adalah representasi dari fakta dunianyata.

Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalambentuk tulisan, suara, gambar, sinyal atausimbol

Page 7: Struktur Data

Halaman 7

Secara garis besar type data dapat dikategorikanmenjadi :1. Type data sederhana

a. Type data sederhana tunggal, misalnyaInteger, real, boolean dan karakter

b. Type data sederhana majemuk, misalnyaString

2. Struktur Data, meliputia. Struktur data sederhana, misalnya array dan

record

Page 8: Struktur Data

Halaman 8

b. Struktur data majemuk, yang terdiridariLinier : Stack, Queue, serta List dan

MultilistNon Linier : Pohon Biner dan Graph

Pemakaian struktur data yang tepat di dalamproses pemrograman akan menghasilkanalgoritma yang lebih jelas dan tepat, sehingga menjadikan program secarakeseluruhan lebih efisien dan sederhana.

Page 9: Struktur Data

Halaman 9

Struktur data yang ″standar″ yang biasanyadigunakan dibidang informatika adalah :

List linier (Linked List) dan variasinyaMultilistStack (Tumpukan)Queue (Antrian) Tree ( Pohon ) Graph ( Graf )

Page 10: Struktur Data

Halaman 10

REVIEW RECORD (REKAMAN)REVIEW RECORD (REKAMAN)

Disusun oleh satu atau lebih field. Tiap field menyimpan data dari tipe dasar tertentu atau dari tipe bentukan lain yang sudah didefinisikan sebelumnya. Nama rekaman ditentukan oleh pemrogram.

Rekaman disebut juga tipe terstruktur.

Contoh :1. type Titik : record <x : real, y : real>

jika P dideklarasikan sebagai Titik maka mengacu field pada P adalah P.x dan P.y.

Page 11: Struktur Data

Halaman 11

2. Didefinisikan tipe terstruktur yang mewakili Jam yang dinyatakan sebagai jam (hh), menit (mm) dan detik (ss), maka cara menulis type Jam adalah :type JAM : record

<hh : integer, {0…23}mm : integer, {0…59}ss : integer {0…59}

>Jika J adalah peubah (variabel) bertipe Jammaka cara mengacu tiap field adalah J.hh, J.mmdan J.ss

Page 12: Struktur Data

Halaman 12

Terjemahan dalam bahasa C :1. type Titik : record <x : real, y : real>

diterjemahkan menjadi :typedef struct { float x;

float y;} Titik;

2. type JAM : record<hh : integer, {0…23}mm : integer, {0…59}

ss : integer {0…59}>

Diterjemahkan menjadi :typedef struct

{ int hh; /*0…23*/int mm; /*0…59*/int ss; /*0…59*/} Jam;

Page 13: Struktur Data

Halaman 13

REVIEW ARRAY (LARIK)REVIEW ARRAY (LARIK)

1. PendahuluanLarik adalah struktur data statik yang menyimpan sekumpulan elemen yang bertipe sama.Setiap elemen diakses langsung melalui indeksnya. Indeks larik harus tipe data yang menyatakan keterurutan misalnya integer atau karakter.

Page 14: Struktur Data

Halaman 14

Banyaknya elemen larik harus sudah diketahui sebelum program dieksekusi.Tipe elemen larik dapat berupa tipe sederhana, tipe terstruktur atau tipe larik lain.Nama lain array adalah Larik, tabel atau vektor

Page 15: Struktur Data

Halaman 15

Cara Pendefinisian Array1. Sebagai Peubah

Contoh :L : array[1..50] of integerNamaMhs : array[‘a’..’j’] of string

2. Sebagai tipe baruContoh :type LarikInt : array[1..100] of integerP : LarikInt

Page 16: Struktur Data

Halaman 16

3. Mendefinisikan ukuran maksimum elemen larik sebagai konstantaContoh :Const Nmaks = 100 type Larikint : array[1..Nmaks] of integerP : LarikInt

Cara menterjemahkan ke bahasa C :#define Nmaks 100typedef int Larikint[Nmaks+1];Larikint P;

Page 17: Struktur Data

Halaman 17

Cara Mengacu Elemen Larik

Elemen larik diacu melalui indeksnya. Nilai indek harus terdefinisi.

Contoh cara mengacu elemen larik adalah :L[4] {mengacu elemen keempat dari larik L }

NamaMhs[‘b’] {mengacu elemen kedua dari larik NamaMhs}

P[k] {mengacu elemen ke-k dari larik P, asalkan nilai k sudah terdefinisi }

Page 18: Struktur Data

Halaman 18

Menginisialisasi Larik

menginisialisasi elemen larik adalah memberikanharga awal untuk seluruh elemen larik, misalnyamenginisialisasi dengan nilai 0 seperti di bawah ini :Procedure InisDgn0(output A:larik, input N:integer){menginisialisasi setiap elemen larik A[1..N] dengan nol} {K. Awal : N adalah banyak elemen efektif larik,

nilainya terdefinisi}{K. Akhir : seluruh elemen larik A bernilai nol}Deklarasi :

K : integerDeskripsi :

for k 1 to N doA[k] 0

endfor

Page 19: Struktur Data

Halaman 19

Mengisi elemen larik dari piranti masukan

Elemen larik dapat diisi dengan nilai yang dibaca dari piranti masukan seperti contoh di bawah ini :Procedure BacaLarik(output A:larik, input N:integer){mengisi elemen larik A[1..N] dengan nilai yang

dibaca dari piranti masukan} {K. Awal : N adalah jumlah elemen efektif larik, nilainya

terdefinisi}{K. Akhir : seluruh elemen larik A berisi nilai-nilai yang dibaca dari

piranti masukan}Deklarasi :

K : integerDeskripsi :

for k 1 to N doread (A[k])

endfor

Page 20: Struktur Data

Halaman 20

Larik Bertype Terstruktur

Larik tidak hanya dapat berisi data bertype tunggal, tapi dapat juga berisi data yang bertipeterstruktur

Contoh :const Nmaks = 100type Mahasiswa : record

<nim : integer,nama_mhs : string,KodeMK : string,Nilai : char >

TabMhs : array[1..Nmaks] of Mahasiswa

Page 21: Struktur Data

Halaman 21

Contoh Cara mengacu elemen TabMhs :1. TabMhs[2].Nim

mengacu field Nim dari elemen kedualarik

2. Write(TabMhs[k].KodeMK)menuliskan field KodeMK dari elemenke k dari larik

Page 22: Struktur Data

Halaman 22

TugasTugas 11

Buatlah dalam notasi algoritma atau bahasa C :1.Definisikan sebuah type terstruktur untuk

menyatakan data nasabah disebuah bank. Data nasabah terdiri atas field Nomor Account, NamaNasabah, Alamat Nasabah, Kota Nasabah, danNomor Telpon Nasabah.Untuk setiap field definisikan type data yang cocok

Page 23: Struktur Data

Halaman 23

2.Dari soal nomor 1 buatlah program dalambahasa pemrograman berbasis bahasa C, untukmemasukkan data nasabah sebanyak N, denganN diinputkan dari papan ketik, kemudianmenuliskan kembali semua data nasabah dalambentuk matrik.Petunjuk :

Gunakan notasi pengulangan untukmenyelesaikan permasalahan tersebut

Tugas dikumpulkan pada pertemuanberikutnya disertai listing program dancontoh keluarannya

Page 24: Struktur Data

Halaman 24

ADT (Abstract Data Type)ADT (Abstract Data Type)ADT adalah definisi type dan sekumpulanprimitif (operasi dasar) terhadap type tersebut.Type diterjemahkan menjadi type terdefinisidalam bahasa pemrograman yang bersangkutan, misalnya menjadi record dalamPascal/Ada dan Struct dalam bahasa C

Page 25: Struktur Data

Halaman 25

Primitif dalam konteks pemrogramanprosedural, diterjemahkan menjadifungsi dan prosedur.

Primitif dikelompokkan menjadi :1. Konstruktor/Kreator, pembentuk nilai

type. Biasanya namanya diawali denganMake.

2. Selektor, untuk mengakses komponen type. Biasanya namanya diawali denganGet.

Page 26: Struktur Data

Halaman 26

3. Prosedur Pengubah nilai komponen4. Validator komponen type, yang

dipakai untuk mengetes apakah dapatmembentuk type sesuai batasan.

5. Destruktor/Dealokator, yaitu untukmenghancurkan nilai objek, sekaligusmemori penyimpannya

6. Baca/tulis, untuk interface denganinput/output device

Page 27: Struktur Data

Halaman 27

7. Operator Relasional terhadap type tersebut untuk mendefinisikan lebihbesar, lebih kecil, sama dengan dansebagainya.

8. Aritmatika terhadap type tersebut, dalam pemrograman biasanya hanyaterdefinisi untuk bilangan numerik.

9. Konversi dari type tersebut ke type dasar dan sebaliknya

Page 28: Struktur Data

Halaman 28

ADT biasanya diimplementasi menjadi dua buahmodul, yaitu :1. Definisi/spesifikasi type dan primitif

- Spesifikasi type sesuai denganbahasa yang dipakai

- Spesifikasi dari primitif sesuai dengan kaidahdalam konteks prosedural, yaitu :a. Fungsi : nama, domain, range, dan pre kondisi

jika adab. Prosedur : Keadaan Awal, Keadaan Akhir dan

proses yang dilakukan2. Body/realisasi dari primitif, berupa kode program dalam

bahasa yang bersangkutan. Realisasi fungsi dan prosedurharus sedapat mungkin memanfaatkan Selektor danKonstruktor

Page 29: Struktur Data

Halaman 29

4. Linked List (List Linier)4. Linked List (List Linier)4.1. DefinisiList linier adalah sekumpulan elemen

bertype sama, yang mempunyaiketerurutan tertentu, yang setiapelemennya terdiri dari 2 bagian :

Type Elmtlist = record< Info : InfoType,

Next : address >

Page 30: Struktur Data

Halaman 30

Dengan Info Type adalah sebuah type terdefenisi yang menyimpan informasisebuah elemen list ; Next adalah address dari elemen berikutnya ( suksesor ).

Dengan demikian, jika didefinisikan First adalah alamt elemen pertama list, makaelemen berikutnya dapat diakses secarasuksesif dari elemen pertama tersebut

Page 31: Struktur Data

Halaman 31

Jadi, sebuah list linier dikenali :elemen pertamanya, biasanya melalui alamatelemen pertama yang disebut : Firstalamat elemen berikutnya ( suksesor ), jikakita mengetahui alamat sebuah elemen , yang dapat diakses melalui field NEXTsetiap elemen mempunyai alamat, yaitutempat elemen disimpan dapat diacu.Untukmengacu sebuah elemen , alamat harusterdefenisi . Dengan alamat tersebut Informasiyang tersimpan pada elemen list dapat diakses. elemen terakhirnya. Ada berbagai cara untukmengenali elemen akhir

Page 32: Struktur Data

Halaman 32

Jika L adalah list , dan P adalah address :Alamat elemen pertama list L dapat diacudengan notasi :

First (L)Elemen yang diacu oleh P dapat dikonsultasiinformasinya dengan notasi :

Info(P)Next(P)

Page 33: Struktur Data

Halaman 33

Beberapa defenisi :1. List L adalah List kosong , jika First (L) = Nil2. Elemen terakhir dikenali, dengan salah satu

cara adalah karena Next(Last) =Nil

Page 34: Struktur Data

Halaman 34

II. Skema traversal untuk list linierList terdiri dari sekumpulan elemen. Seringkali diperlukan untuk memprosessetiap elemen list dengan cara yang sama. Karena itu salah primitif operasi konsultasidasar pada struktur list adalah traversal, yaitu “mengunjungi” setiap elemen list untuk diproses.

Page 35: Struktur Data

Halaman 35

Karena Urutan akses adalah dari elemenpertama sampai dengan elementerakhir, maka traversal list secaranatural dilakukan dari elemen pertama, suksesornya, dan seterusnya sampaidengan elemen terakhir.

Page 36: Struktur Data

Halaman 36

Skema traversal yang dipakai adalah Sbb :

Procedure SKEMAListTransversal1( Input L : List ) {K. Awal : List L terdefinisi , mungkin kosong }{K. Akhir : semua elemen list L dikunjungi dan telah

diproses }{Proses : Traversal sebuah list linier. Dengan MARK,

tanpa pemrosesan khusus pada list kosong}

Deklarasi

Page 37: Struktur Data

Halaman 37

Deklarasi :P : address { address untuk traversal , type

terdefenisi }Deskripsi :

InisialisasiP ← First ( L ) { First Element } While ( P ≠Nil ) do

Proses ( P )P ← Next ( P ) { Next element }

endwhileTerminasi

Page 38: Struktur Data

Halaman 38

Procedure SKEMAListTransversal 2( Input L : List )

{ K. Awal : List L terdefenisi , mungkin kosong } { K. Akhir : semua elemen list L “dikunjungan “

dan telah diproses }{ Proses : Transversal sebuah list linier yang

diidentifikasi oleh elemen pertama L , Dengan MARK dan pemrosesankhusus pada list kosong }

Deklarasi :

Page 39: Struktur Data

Halaman 39

DeklarasiP : address { address untuk traversal , type

terdefenisi }Deskripsi

If (First ( L ) = Nil) then Write ( ‘List kosong ‘ )

else

Page 40: Struktur Data

Halaman 40

InsialisasiP ← First ( L ) { First Element }Repeat

Proses ( P )P ← Next ( P ) { Next element }

until P=NilTerminasi

Page 41: Struktur Data

Halaman 41

III. Skema Sequential Search untuk list linier Selain traversal, proses pencarian suatu elemenlist adalah primitif yang sering kali didefinisikan pada struktur list. Pencariandapat berdasarkan nilai, atau berdasarkanalamat.

III.1. Search suatu Nilai, output adalah addressSearch ini sering dipakai untuk mengenalisuatu elemen list berdasarkan nilai informasiyang disimpan pada elemen yang dicari. Biasanya dengan alamat yang ditemukan, akan dilakukan suatu proses terhadap elemenlist tersebut.

Page 42: Struktur Data

Halaman 42

Procedure SKEMAListSearch1 ( Input L : List, X : InfoType, Output P : address, Found: Boolean )

{ K. Awal : List linier L sudah terdefinisi dan siapdikonsultasi, X terdefenisi }

{ K.Akhir : P : address pada pencarian beurutan, dimana X diketemukan, P = Nil jikatidak ketemu, Found berharga true jikaharga X yang dicari ketemu, false jikatidak }

Page 43: Struktur Data

Halaman 43

{Proses : Sequential Search harga X pada sebuahlist linier L, Semua elemen diperiksa

dengan intruksi yang sama, versidengan Boolean}

Deklarasi

Deskripsi

Page 44: Struktur Data

Halaman 44

P ← First ( L )Found ← falseWhile ( P ≠ Nil ) and ( not found ) do

if X = Info (P) thenFound ←True

else P ← Next (P)

endifendwhile { P = Nil or Found}{Jika Found maka P adalah address dimana

harga yang dicari diketemukan}

Page 45: Struktur Data

Halaman 45

III. 2. Search suatu Elemen yang beralamat tertentu

Procedure SKEMAList Search@( Input L : List, P : address, Found: Boolean )

{K. Awal : List linier L sudah terdefinisi dan siapdikonsultasi, X terdefenisi }

{K.Akhir : Jika ada elemen list beralamat P, Found berharga true, Jika tidak ada elemen list beralamat P, Found berharga false }

{Proses : Sequential Search @ P pada sebuah list linier L, Semua elemen diperiksa dengan intruksiyang sama }

Page 46: Struktur Data

Halaman 46

DeklarasiPt : address

DeskripsiPt ← First ( L )Found ← falseWhile ( Pt ≠ Nil ) and ( not found ) do

if Pt = P thenFound ← true

else Pt ← Next (Pt)

endifendwhile { Pt = Nil or Found}{ Jika Found maka P adalah elemen list}

Page 47: Struktur Data

Halaman 47

IV. Definisi fungsional list linier danalgoritmanyaSecara fungsional, pada sebuah list linier biasanya dilakukan pembuatan,

penambahan atau penghapusan elemen yang dapat ditulis sebagai berkut :

Jika diberikan L, L1 dan L2 adalah list linier dengan elemen ElmtList, makaoperasi yang dapat dilakukan :

ListEmpty, CreateList, Insert, Delete, Concat dan UpdateList

Page 48: Struktur Data

Halaman 48

IV. 1. Pengetesan List KosongPemeriksaan apakah sebuah list kosong sangat

penting, karena Keadaan Awal danKeadaan Akhir beberapa prosedur harusdidefinisikan berdasarkan keadaan list. Operasi pada list kosong sering kali membutuhkan penanganan khususRealisasi algoritmik dari definisifungsional ini adalah sebuah fungsisebagai berikut.

Page 49: Struktur Data

Halaman 49

Function IsEmptyList (L : List ) → boolean{ Test apakah sebuah list L kosong,

Mengirimkan true jika list kosong, falsejika tidak kosong}

DeklarasiDeskripsi

return(First (L) = Nil)

Page 50: Struktur Data

Halaman 50

IV.2 Pembuatan sebuah elemen padalist linier

Pembuatan sebuah list berarti membuatsebuat list KOSONG, yang selanjutnyasiap diproses (ditambah elemennya, dsb). Realisasi algoritmik daridefenisi funfsional ini adalah sebuahprosedur sebagai berikut.

Page 51: Struktur Data

Halaman 51

Procedure CreateList( Output L : List ){K. Awal : Sembarang }K. Akhir : terbentuk list L yang kosong : First

(L) diinisialisasi dengan NIL )Proses : Membuat list kosong}

DeklarasiDeskripsi

First (L) ← Nil

Page 52: Struktur Data

Halaman 52

IV. 3 Penyisipan sebuah elemenpada list linier

Fungsi insert (penyisipan) harus dijabarkan lebihrinci, karena dapat menjadi penyisipan sebagaielemen pertama, setelah sebuah address P ataupenyisipan menjadi elemen terakhir ataubahkan menjadi elemen ditengah

Penyisipan sebuah elemen dapat dilakukanterhadap sebuah elemen yang sudah dialokasi(diketahui address-nya ), atau sebuah elemenyang hanya diketahui nilai Info-nya (berartibelum dialokasi).

Page 53: Struktur Data

Halaman 53

IV. 2.1. INSERT-First (Address)Menambahkan sebuah elemen yang diketahui

alamatnya sebagai elemen pertama list.Procedure InsertFirst (Input/Output L:List, Input

P: address){K. Awal : List L mungkin kosong{K. Akhir : P adalah elemen pertama list L}{Proses : Insert sebuah elemen beralamat P sebagai

elemen pertama list linier L yang mungkinkosong}

DeklarasiDeskripsi

Next (P) ← First (L)First (L) ← P

Page 54: Struktur Data

Halaman 54

IV.2.2 INSERT-First (Nilai)Menambahkan sebuah elemen yang diketahui nilainya sebagai elemen pertama

list.

Procedure InsFirst (Input/output L :List, Input E : infotype ){ K. Awal : List L mungkin kosong }{ K. Akhir : Sebuah elemen dialokasikan dan menjadi elemen

pertama list L, jika alokasi berhasil. Jika alokasi gagallist tetap seperti semula }

{ Proses : Insert sebuah elemen sebagai elemen pertama list} Deklarasi

P : addressDeskripsi

Alokasi (P)If P ≠ Nil then

Info (P) ← ENext (P) ← First (L) First (L) ← P

Page 55: Struktur Data

Halaman 55

IV.2.2. INSERT-AFTER Menyisipkan sebuah elemen beralamat P sebagai

suksesor dari sebuah elemen list linier yang beralamatPrec

Procedure InsertAfter ( Input P, Prec: address ){K. Awal : Prec adalah elemen list, prec ≠ Nil, P sudah

dialokasikan, P ≠ Nil, Next (P) = NilK. Akhir : P menjadi suksesor PrecProses : Insert sebuah elemen beralamat P pada List

linier L}DeklarasiDeskripsi

Next (P) ← Next (Prec) Next (Prec) ← P

Page 56: Struktur Data

Halaman 56

IV. 2.3. INSERT – LastMenyisipkan sebuah elemen beralamat P sebagai elemen

terakhir sebuah list linier. Ada dua kemungkinan list kosong atau tidak kosong

Procedur InsertLast@(Input/Output L: List, Input P : address)

{K. Awal : List L mungkin kosong, P sudah dialokasi, P ≠ Nil, Next (P) = Nil

K. Akhir : P adalah elemen terakhir list LProses : Insert sebuah elemen beralamat P sbg elemen

terakhir dari list linier L yg mungkin kosong }

Page 57: Struktur Data

Halaman 57

DeklarasiLast : address { address untuk traversal}

DeskripsiIf Fisrt (L) = Nil then { insert sebagai elemen pertama}

InsertFirst(L, P)Else{ Traversal list sampai address terakhir}

Last ← First (L)While (Next (Last ) ≠ Nil ) do

Last ← Next (Last )endwhile {Next ( Last) = Nil, Last adalah elemen terakhir;

insert P after last }InsertAfter (P, Last)

endif

Page 58: Struktur Data

Halaman 58

Procedure InsertLast(Input/output L :List, Input E : Infotype){ K. Awal : List L mungkin kosong, P sudah dialokasi,

P ≠ Nil, Next(P)=Nil K. Akhir : P adalah elemen terakhir list L Proses : Insert sebuah elemen beralamat P sebagai

elemen terakhir dari list linier L yang mungkinkosong }

DeklarasiLast : address { address untuk traversal }

DeskripsiAlokasi (P) If (P ≠ Nil) then

Info(P) ←EInsertLast@(L,P)

Page 59: Struktur Data

Halaman 59

IV.3. Penghapusan sebuah elemen pada list linier

Penghapusan harus dijabarkan lebih rinci, Karenapenghapusan elemen dapat merupakanpertama, setelah sebuah address P ataupenghapusan elemen terakhir. Perbedaan inimelehirkan 3 operasi dasar penghapusanelemen list yang diturunkan dari definisifungsional inimenjadi realisasi algoritma.

Operasi penghapusan dapat mengakibatkan list kosong, jika list semula hanya terdiri dari satuelemen.

Page 60: Struktur Data

Halaman 60

IV.3.1. DELETFirst : menghapus elemen pertamalist linier

a. Elemen yang dihapus dicatat alamatnyaProcedure DeleteFirst@ (Input/Output L : List, Output

P : address){K. Awal : List L tidak kosong, minimal 1 elemen

pertama pasti ada }{K. Akhir : menghapus elemen pertama L

P adalah @ elemen pertama L sebelumpenghapusan, L yang baru adalah Next (L)

DeklarasiDeskripsi

P ← First (L) First (L) ← Next ( First (L) )

Page 61: Struktur Data

Halaman 61

Procedure DeleteFirst (Input/Output L : List, Output E : InfoType)

{K. Awal : List L tidak kosong, minimal 1 elemenpertama pasti ada }

{K. Akhir : menghapus elemen pertama LE adalah Nilai elemen pertama L sebelumpenghapusan, L yang baru adalah Next (L)

DeklarasiDeskripsi

P ← First (L) E ← Info (P)First (L) ← Next ( First (L) ) Dealokasi (P)

Page 62: Struktur Data

Halaman 62

IV. 3.2. Delete After :Penghapusan suksesor sebuah elemen :Procedure DeleteAfter ( Input Prec : adrress, Output

P : address ){ K. Awal : List tidak kosong, Prec adalah elemen list

, Next (Prec) ≠ Nil } Prec ≠elemen terakhirK. Akhir : Menghapus suksesor Prec, P adalah @

suksesor Prec sebelum penghapusan, Next (Prec) yang baru adalah suksesor darisuksesor Prec sebelum penghapusan }

DeklarasiDeskripsi

P ← Next (Prec)Next (Prec) ← Next (Next (Prec))

Page 63: Struktur Data

Halaman 63

Dengan primitip ini, maka penghapusan sebuahberalamat P dapat dilakukan dengan : mencaripredesesor dari P, yaitu alamat Prec memakaiDeleteAfter (Prec)

Procedure DeleteP ( Input/Output L ; List, OutputP : address )

{ K. Awal : List L tidak kosong , P adalah elemen list L K. Akhir : Menghapus P dari list, P mungkin

elemen pertama, “tengah” atau terakhir }Deklarasi

Prec : address { alamat predesesor } Deskripsi

Page 64: Struktur Data

Halaman 64

{ Cari predesesor P }if (P = First (L) then {Delete list dengan

satu elemen }DeleteFirst (L,P)

elsePrec ← First (L) While (Next(Prec) ≠ P ) do

Prec ← Next (Prec)endwhile { Next (Prec) = P , hapus P }DeleteAfter (Prec , P)

endif

Page 65: Struktur Data

Halaman 65

IV. 3.3. DELETELast :Menghapus elemen terakhir list dapat dilakukan jika

alamat dari elemen sebelum elemen terakhirdiketahui. Persoalan selanjutnya menjadi persoalanDeleteAfter, kalau last bukan satu- satunya elemenlist linier. Ada dua kasus, yaitu list menjadi kosongatau tidak.

Procedure DeleteLast (Input L : List, Output P : address)

{K. Awal : List L tidak kosong, minimal mengandung1 elemen

K. Akhir : menghapus elemen terakhir dari list, list mungkin menjadi kosong

Proses : P adalah alamat elemen terakhir list sebelum penghapusan }

Page 66: Struktur Data

Halaman 66

DeklarasiLast , preclast :address { address untuk traversal }

Deskripsi{ Find last dan address sebelum last }Last ← First (L) Preclast ← Nil { predesesor dari L tak terdefenisi }While ( Next ( Last ) ≠ Nil do { Traversal list sampai @ terakhir}

Preclast ← Last ; Last ← Next ( last )endwhile { Next ( Last ) = Nil, Last adalah elemen terakhir;

preclast = sebelum last } P ← LastIf Preclast = Nil then { list dg 1 elemen, jadi kosong }

First(L) ← Nil Else

Next ( preclast )← Nil endif

Page 67: Struktur Data

Halaman 67

IV. 5. Konkatenasi dua buah list linierConcat adalah menggabungkan dua list. Dalam contoh

berikut list kedua disambungkan ke list pertama. JadiLast (L1) menjadi predesesor First (L2). Realisasialgoritma adalah sebuah prosedur sebagai berikut :

Procedure CONCAT (Input L1, L2 : List, Output : L3 : List )

{K. awal : L1 ≠ L2, L1 ≠ L3,dan L3 ≠ L2; L1, L2 mungkin kosong

K. Akhir : L3 adalah hasil konkatenasi (menyambung) dua buah list linier, L2 ditaruh dibelakangL1 }

Page 68: Struktur Data

Halaman 68

DeklarasiLast1 : address { alamat elemen terakhir list pertama }

DeskripsiCratelist (L3) {inisialisasi list hasil }If Fist (L1) = Nil then

First (L3) ← First (L2)Else { Traversal list 1 sampai address terakhir,

Hubungkan last dengan Fisrt 2}First (L3) ← First (L1)Last1 ← First (L1) While ( Next (Last 1 ) ≠ Nil ) do

Last1 ← Next (Last 1) endwhile {Next ( Last 1) ← First (L2)}

Next(Last1) ← First (L2)}endif

Page 69: Struktur Data

Halaman 69

Bagian Deklarasi dari algoritma pada List Linier :Deklarasi

type InfoType = … {Sebuah type terdefinisi}type Address pointer to ElmtLtype ElmtL = record

<Info : InfoType,Next : Address >

type List = record <First : Address >{Deklarasi Nama Peubah}

L : ListP : Address

Page 70: Struktur Data

Halaman 70

SoalSoal--SoalSoal LatihanLatihanI. Apakah perbedaan struktur data list linier

ditinjau dari sudut pandang operasinya, jikadibandingkan dengan struktur data stack dan queue?

II. Untuk data yang bagaimanakah yang dapatdirepresentasikan dengan menggunakanstruktur data list linier?

III. Diketahui sebuah list linier dengan elemenbertipe integer, buatlah :1. Sebuah prosedur untuk menghitung

jumlah elemen list yang genap2. Prosedur untuk menghitung rata-rata

elemen list yang ganjil

Page 71: Struktur Data

Halaman 71

3. Prosedur untuk menghitung banyaknyaelemen list yang positif (lebih besar darinol)

4. Prosedur untuk mencetak elemen list yang genap

IV. Diketahui sebuah list dengan elemen bertypeinteger terurut membesar, buatlah :

1. Fungsi untuk mengirimkan elemen pertamalist

2. Fungsi untuk mencari elemen list yang minimum

3. Fungsi untuk menghitung banyaknyaelemen yang lebih besar dari 100

Page 72: Struktur Data

Halaman 72

5. Stack (5. Stack (TumpukanTumpukan))5.1. DefinisiSTACK (Tumpukan) adalah list linier yang : 1. Dikenali elemen puncaknya (TOP)2. Aturan penyisipan dan penghapusan

elemennya tertentu :-Penyisipan selalu dilakukan “di atas “ TOP-Penghapusan selalu dilakukan pada TOP

Page 73: Struktur Data

Halaman 73

Karena aturan penyisipan dan penghapusan semacamitu, TOP adalah satu-satunya alamat tempat terjadioperasi. Elemen yang ditambahkan paling akhir akanmenjadi elemen yang akan dihapus.Dikatakanbahwa elemen Stack akan tersusun secara LIFO

(Last In First Out).Maka secara lojik, sebuah STACK dapat

digambarkan sebagai list linier yang setiapelemennya adalah

Type ElmtS = record<Info : InfoType,

Next : address >

Page 74: Struktur Data

Halaman 74

dengan InfoType terdefinisi yang menentukaninformasi yang disimpan pada setiapelemen stack, dan address adalah“alamat” dari elemen

Selain itu alamat elemen terbaru (TOP) dicatat, sedangkan alamat elemen yang paling “bawah”, yaitu yang paling lama biasanyadiebut BOTTOM.

TOP adalah elemen pertama list, supayapenambahan dan penghapusan denganmudah dan efisien dapat dilakukan.

Page 75: Struktur Data

Halaman 75

Sehingga jika S adalah sebuah Stack, dan P adalah address makaTop (S) adalah alamat elemen TOP, dimanaoperasi penyisipan/penghapusan dilakukan.Info (P) adalah informasi yang disimpan padaalamat PNext (P) adalah alamat suksesor PElmtS (P) adalah sebuah elemen stack yang beralamat P Stack kosong adalah Stack dengan Top (S) = Nil ( tidak terdefinisi )

Page 76: Struktur Data

Halaman 76

Bagian Deklarasi dari algoritma pada Stack :Deklarasi

type InfoType = … {Sebuah type terdefinisi}type Address pointer to ElmtStype ElmtS = record

<Info : InfoType,Next : Address >

type Stack = record <TOP : Address>{Deklarasi Nama Peubah}

S : StackP : Address

Page 77: Struktur Data

Halaman 77

Pada stack, jarang sekali dilakukantraversal, karena keunikan Stack justrupada operasi yang hanya menyangkutelemen TOP. Namun dibutuhkantraversal misalnya untuk mencetak isiStack.

5.3. Search pada StackPada stack, elemen yang diproses hanyalah

elemen pada TOP. Maka hampir tidak pernahdilakukan search.

5.2. Traversal 5.2. Traversal padapada StackStack

Page 78: Struktur Data

Halaman 78

5.4. 5.4. OperasiOperasi dandan fungsifungsi dasardasarpadapada STACK.STACK.

a. Test STACK kosongMengetahui bahwa stack kosong atautidak sangat penting, sebab semua operasiakan dilakukan berdasarkan kosong atautidaknya suatu Stack. Realisasi algoritmadari definisi fungsional ini adalah sebuahfungsi yang melakukan test terhadap Stack sebagai berikut :

Page 79: Struktur Data

Halaman 79

function StackEmpty (S : STACK) →Boolean

{ TEST stack kosong : Mengirim true, jikatumpukan kosong, false jika tumpukan tidakkosong}

Deklarasi

Deskripsireturn (Top (S) = Nil)

Page 80: Struktur Data

Halaman 80

b. Pembuatan STACK kosongMembuat Stack kosong diperlukan untuk memulaimemakai stack. Realisasi algoritma dari definisifungsional ini adalah sebuah prosedur yang melakukan inisialisasi stack sebagai berikut

Procedure CreateEmptyS (Output S : STACK){K. Awal : sembarang, K. Akhir : sebuah stack S yang kosong siap dipakai

terdefinisiProses : Membuat stack kosong }

DeklarasiDeskripsi

Top (S) ← Nil

Page 81: Struktur Data

Halaman 81

c.Penambahan sebuah elemen padaSTACK (Push)Penambahan selalu dilakukan pada TOP, dankarena alamat TOP diketahui maka prosesnyasederhana. Berikut ini akan diberikan skemaprosedur penyisipan tersebut. Realisasi algoritmadari definisi fungsional ini adalah salah satu daridua buah prosedur yang melakukan penambahanelemen stack sebagai berikut. Prosedur pertamamenambahkan suatu ElmtS yang diketahuialamatnya dan yang kedua menambahkan suatunilai ElmtS yang diberikan.

Page 82: Struktur Data

Halaman 82

procedure Push@ (Input/Output S : STACK Input P : address)

{Menambahkan sebuah elemen baru pada TOP sebuahstack, dengan elemen yang diketahui alamatnya}

{K.Awal : Stack mungkin kosong, P terdefinisi (berartiterdefinisi informasinya, Next (P) = Nil}

{K.Akhir : Top (S) adalah P}DeklarasiDeskripsi

{ insert sebagai elemen pertama }Next (P) ← TOP (S)TOP (S) ← P

Page 83: Struktur Data

Halaman 83

procedure Push( Input / Output S:STACK Input E: InfoType ){ Menambahkan sebuah elemen baru pada TOP sebuah stack,

dengan elemen yang diketahui informasinya }{ K. Awal : Stack mungkin kosong , E terdefenisi , alokasi alamat

selalu berhasil } { K. Akhir : TOP (S) berisi E )Deklarasi

P : addressDeskripsi

Alokasi ( P ) { alokasi selau berhasil }Info(P) ← E { insert sebagai elemen pertama }Next(P) ← TOP(S) TOP(S) ← P

Page 84: Struktur Data

Halaman 84

d. Penghapusan sebuah elemen padaSTACK (Pop)Penghapusan elemen Stack selalu dilakukan padaTOP , hanya saja harus diperhitungkan bahwamugkin Stack akan menjadi kosong akibatterjadinya penghapusan. Jika Stack menjadikosong , maka harga TOP harus diganti . Realisasialgoritma dari definisi funsional ini adalah salahsatu dari dua buah prosedur yang melakukanpengambilan elemen stack sebagai berikut . Prosedur pertama mengambil suatu Elmts denganmenyimpan alamatnya dan yang kedua mengambilnilai , dan membebaskan alamat ( dealokasi ) yang tadinya dipakai

Page 85: Struktur Data

Halaman 85

procedure PopStack@(Input/Output S : STACK Output P : address)

{K.Awal : Stack tidak kosongK.Akhir : Alamat elemen Top (S) disimpan pada

P, sehingga informasinya dapat diaksesmelalui P

Proses : Menghapus elemen stack, stack tidak bolehkosong dan mungkin menjadi kosong }

DeklarasiDeskripsi

P ← TOP (S)TOP (S) ← Next(TOP(S))

Page 86: Struktur Data

Halaman 86

procedure PopStack(Input/Output S : STACK Output E : InfoType)

{K.Awal : Stack tidak kosongK.Akhir : Alamat elemen Top (S) disimpan pada

E, alamat TOP yang lama didealokasiProses : Menghapus elemen stack, stack tidak boleh

kosong dan mungkin menjadi kosong }Deklarasi

P : addressDeskripsi

P ← TOP (S)E ← Info(P)TOP (S) ← Next(TOP(S))Dealokasi (P)

Page 87: Struktur Data

Halaman 87

SoalSoal--SoalSoal LatihanLatihan1. Mengapa cara penyusunan elemen pada

Stack sering disebut tersusun secaraLIFO?

2. Mengapa pada Stack Traversal dan Search jarang dilakukan?

3. Penghapusan elemen pada Stack selaludilakukan pada elemen yang paling atas, bagaimana jika terpaksa harus menghapuselemen yang paling bawah?

Page 88: Struktur Data

Halaman 88

4. Buatlah sebuah fungsi untuk menghitung jumlahelemen stack yang genap, jika diketahui sebuahstack dengan elemen bertype integer.

5. Buatlah fungsi/prosedur untuk mencetak elemenstack yang ganjil

6. Buatlah juga fungsi untuk menghitung rata-rata elemen Stack yang genap

7. Buatlah sebuah fungsi untuk mengirimkanelemen pertama Stack

8. Buatlah sebuah fungsi untuk mengirimkanelemen Stack yang maksimum jika diketahuielemen Stack terurut mengecil bertype integer

Page 89: Struktur Data

Halaman 89

6. Queue (6. Queue (AntrianAntrian))6.1. Definisi

Queue (Antrian) adalah list linier yang :1. Dikenali elemen pertama (Head) dan elemen

terakhirnya (Tail)2. Aturan penyisipan dan penghapusan elemennya

disefinisikan sebagai berikut :- Penyisipan selalu dilakukan setelah elementerakhir

- Penghapusan selalu dilakukan pada elemenpertama

3. Satu elemen dengan elemen lain dapat diaksesmelalui informasi Next

Page 90: Struktur Data

Halaman 90

Struktur data ini banyak dipakai dalaminformatika misalnya untuk merepresentasi :1. Antrian job dalam sistem operasi2. Antrian dalam dunia nyata

Maka secara lojik, sebuah Queue dapatdigambarkan sebagai list linier yang setiapelemennya adalah :Type ElmtQ = record

<Info : InfoType, Next : address >

Page 91: Struktur Data

Halaman 91

dengan InfoType terdefinisi yang menentukaninformasi yang disimpan pada setiap elemenqueue, dan address adalah “alamat” darielemen

Selain itu alamat elemen Pertama (Head) danelemen terakhir (Tail) dicatat.

Maka jika Q adalah Queue dan P adalah Address, penulisan untuk Queue adalah :Head(Q)Tail(Q)Next(P)Info(P)

Page 92: Struktur Data

Halaman 92

Bagian Deklarasi dari algoritma pada Queue :Deklarasi

type InfoType = … {Sebuah type terdefinisi}type Address pointer to ElmtQtype ElmtQ = record

<Info : InfoType,Next : Address >

type Queue = record <Head : Address, Tail : Address>

{Deklarasi Nama Peubah}Q : QueueP : Address

Page 93: Struktur Data

Halaman 93

Pada queue, jarang sekali dilakukantraversal, karena keunikan Queue justrupada operasi yang hanya menyangkutelemen pertama dan terakhir. Namundibutuhkan traversal misalnya untukmencetak isi Antrian.

6.3. Search pada QueuePada Queue, elemen yang diproses hanyalah

elemen pada pertama dan terakhir. Makahampir tidak pernah dilakukan search.

6.2. Traversal 6.2. Traversal padapada QueueQueue

Page 94: Struktur Data

Halaman 94

6.4. 6.4. OperasiOperasi dandan fungsifungsi dasardasarpadapada Queue.Queue.

a. Test Queue kosongMengetahui bahwa Queue kosong atau tidaksangat penting, sebab semua operasi akandilakukan berdasarkan kosong atau tidaknyasuatu Queue. Realisasi algoritma dari definisifungsional ini adalah sebuah fungsi yang melakukan test terhadap Queue sebagaiberikut :

Page 95: Struktur Data

Halaman 95

function IsQEmpty (Q : Queue) → Boolean{ TEST Queue kosong : Mengirim true, jika

antrian kosong, false jika antrian tidakkosong}

DeklarasiDeskripsi

return ((Head(Q) = Nil) and (Tail(Q) = Nil))

Page 96: Struktur Data

Halaman 96

b. Pembuatan Queue kosongMembuat Queue kosong diperlukan untuk memulaimemakai Queue. Realisasi algoritma dari definisifungsional ini adalah sebuah prosedur yang melakukan inisialisasi Queue sebagai berikut :

Procedure CreateEmptyQ (Output Q : Queue){K. Awal : sembarang, K. Akhir : sebuah queue Q yang kosong terbentukProses : Membuat queue kosong }

DeklarasiDeskripsi

Head(Q) ← NilTail(Q) ← Nil

Page 97: Struktur Data

Halaman 97

c.Penambahan sebuah elemen padaQueuePenambahan selalu dilakukan pada ekor, dan karena alamat ekor diketahui makaprosesnya sederhana, yaitu hanyaInsertLast.

Berikut ini akan diberikan skema prosedurpenyisipan tersebut.

Page 98: Struktur Data

Halaman 98

Realisasi algoritma dari definisi fungsional iniadalah salah satu dari dua buah proseduryang melakukan penambahan elemenQueue sebagai berikut :

Prosedur pertama menambahkan suatuElemen Queue yang diketahui alamatnyadan yang kedua menambahkan suatu nilaiElemen queue yang diberikan.

Page 99: Struktur Data

Halaman 99

procedure InsertQ@ (Input/Output Q : Queue Input P : address)

{K.Awal : Queue mungkin kosong, P terdefinisi(berarti terdefinisi informasinya, Next (P) = Nil

K.Akhir : P menjadi elemen Tail dari Q danTail yang baru adalah P

Proses : Insert sebuah elemen beralamat P pada Tail dari antrian Q }

Deklarasi

Page 100: Struktur Data

Halaman 100

DeskripsiIf IsQEmpty(Q) then

Head(Q) ← PTail(Q) ← P

elseNext(Tail(Q)) ← PTail(Q) ← P

endif

Page 101: Struktur Data

Halaman 101

procedure InsertQ(Input/Output Q : Queue Input E : InfoType)

{K.Awal : Queue mungkin kosong, E terdefinisi

K.Akhir : Elemen Tail dari Q yang barubernilai E

Proses : Insert sebuah elemen nilai padaTail dari antrian Q }

Deklarasi

Page 102: Struktur Data

Halaman 102

DeskripsiAlokasi (P)Info (P) ← EIf IsQEmpty(Q) then

Head(Q) ← PTail(Q) ← P

elseNext(Tail(Q)) ← PTail(Q) ← P

endif

Page 103: Struktur Data

Halaman 103

d. Penghapusan Elemen Pada QueuEPenghapusan elemen pada queue selaludilakukan pada elemen pertama, hanya sajaperlu diperhitungkan bahwa mungkin queue menjadi kosong akibat terjadinyapenghapusan. Jika queue menjadi kosong, maka harga Tail harus diganti. Jika akibatpenghapusan queue tidak kosong, makaelemen terakhir tidak berubah.

Page 104: Struktur Data

Halaman 104

Berikut adalah skema penghapusan tersebut. Prosedur pertama melakukan penghapusanElmtQ yang berada di Head danyang dicatatadalah alamatnya, yaitu P. Prosedur yang kedua menghapus elemen Head dari queue danmenyimpannya pada suatu elmtQ sertamembebaskan alamat yang tadinya dipakaioleh elemen Head tersebut.

Page 105: Struktur Data

Halaman 105

procedure DeleteQ@(Input/Output Q : Queue Output P : address)

{K.Awal : Queue tidak kosongK.Akhir : P bukan lagi elemen dari Q, P ≠ Nil,

Next(P) = NilProses : Menghapus elemen Head dari antrian,

antrian tidak boleh kosong danmungkin menjadi kosong }

DeklarasiDeskripsi

Page 106: Struktur Data

Halaman 106

P ← Head(Q)Head(Q) ← Next(Head(Q))if (Head(Q) = Nil) then

Tail(Q) ← NilendifNext(P) ← Nil

Page 107: Struktur Data

Halaman 107

procedure DeleteQ(Input/Output Q : Queue Output E : InfoType)

{K.Awal : Queue tidak kosongK.Akhir : Jika P adalah Head(Q). P bukan lagi

elemen dari Q, P ≠ Nil, Next(P) = Nil

Proses : Menghapus elemen Head dari antrian, antrian tidak boleh kosong danmungkin menjadi kosong }

DeklarasiDeskripsi

Page 108: Struktur Data

Halaman 108

P ← Head(Q)E ← Info(Head(Q))Head(Q) ← Next(Head(Q))if (Head(Q) = Nil) then

Tail(Q) ← NilendifNext(P) ← NilDealokasi(P)

Page 109: Struktur Data

Halaman 109

SoalSoal--SoalSoal

1. Mengapa cara penyusunan elemen padaQueue Sering disebut tersusun secaraFIFO?

2. Mengapa pada Queue Traversal danSearch jarang dilakukan?

3. Penghapusan elemen pada Queue selaludilakukan pada elemen yang paling depan, bagaimana jika terpaksa harus menghapuselemen yang paling belakang?

Page 110: Struktur Data

Halaman 110

4. Buatlah sebuah fungsi untuk menghitung jumlahelemen queue yang ganjil, jika diketahui sebuahqueue dengan elemen bertype integer.

5. Buatlah fungsi/prosedur untuk mencetak elemenqueue yang genep

6. Buatlah juga fungsi untuk menghitung rata-rata elemen queue yang ganjil

7. Buatlah sebuah fungsi untuk mengirimkan elemenpertama queue

8. Buatlah sebuah fungsi untuk mengirimkan elemenqueue yang maksimum jika diketahui elemen queue terurut membesar dan bertype integer

Page 111: Struktur Data

Halaman 111

7. 7. PohonPohon (Tree)(Tree)7.1. Definisi Rekurens Dari PohonSebuah pohon adalah himpunan terbatas tidak

kosong, dengan elemen yang dibedakansebagai berikut :

1. Sebuah elemen yang dibedakan dari yang lain yang disebut sebagai AKAR (root) daripohon

2. Elemen yang lain (jika masih ada) dibagi-bagi menjadi beberapa sub himpunan yang disjoint dan masing-masing sub himpunantersebut adalah pohon yang disebut sebagaisub pohon dari pohon tersebut.

Page 112: Struktur Data

Halaman 112

Beberapa Istilah1. Hutan

Hutan adalah sequence (list) dari pohon2. Simpul (Node)

Simpul adalah elemen dari pohon yang memungkinkan akses pada sub pohon dimanasimpul tersebut berfungsi sebagai Akar

3. CabangCabang adalah hubungan antara Akar dengansub pohon

Page 113: Struktur Data

Halaman 113

4. AyahAkar dari sebuah pohon adalah Ayah darisub pohon

5. AnakAnak dari sebuah pohon adalah Sub pohon

6. SaudaraSaudara adalah simpul-simpul yang mempunyai Ayah yang sama

7. DaunDaun adalah simpul terminal dari pohon. Semua simpul selain Daun adalah simpulbukan terminal

Page 114: Struktur Data

Halaman 114

8. Jalan (Path)Jalan adalah suatu urutan tertentu dariCabang

9. DerajatDerajat sebuah pohon adalah banyaknyaanak dari dari pohon tersebut.Jika sebuah simpul berderajat N disebut

pohon N-aire1 disebut pohon 1-aire/uner2 disebut pohon 2-aire/biner

Page 115: Struktur Data

Halaman 115

10. Tingkat (Level)Level pohon adalah panjangnya jalan dariAkar sampai dengan simpul yang bersangkutan. Panjang dari jalan adalahbanyaknya simpul yang dikandung padajalan tersebut. Akar mempunyai tingkat samadengan 1.

Dua buah simpul disebut sebagai Sepupu jikamempunyai tingkat yang sama dalam sebuahpohon.

Page 116: Struktur Data

Halaman 116

11. Kedalaman (Tinggi)Kedalaman (Tinggi) dari pohon adalah nilaimaksimum dari tingkat simpul yang ada padapohon tersebut. Kedalaman adalah panjangmaksimum jalan dari Akar menuju ke sebuahdaun

12. LebarLebar sebuah Pohon adalah maksimumbanyaknya simpul yang ada pada suatuTingkat (Level)

Page 117: Struktur Data

Halaman 117

7.2. Struktur Pohon BinerDefinisiSebuah pohon biner (Binary Tree) adalah

himpunan terbatas yang :Mungkin kosong atauTerdiri dari sebuah simpul yang disebutsebagai Akar dan dua buah himpunan lain yang disjoint yang merupakan pohon bineryang disebut sebagai Sub Pohon Kiri (Left) dan Sub Pohon Kanan (Right) dari pohon binertersebut.

Page 118: Struktur Data

Halaman 118

Pohon biner merupakan tipe yang sangat pentingdari struktur data dan banyak dijumpaidalam berbagai terapan. Karakteristik yang dimiliki oleh pohon biner adalah bahwasetiap simpul paling banyak hanyamemiliki dua buah anak, dan mungkintidak punya anak.

Istilah-istilah yang digunakan sama denganistilah pada pohon secara umum.

Page 119: Struktur Data

Halaman 119

Notasi Prefiks, Infiks dan Postfiks1. Notasi Prefiks

Notasi Prefiks ditulis dengan cara mengikutialur sebagai berikut :

Page 120: Struktur Data

Halaman 120

2. Notasi InfiksNotasi ini ditulis dengan cara mengikuti alursebagai berikut :

Page 121: Struktur Data

Halaman 121

3. Notasi PosfiksNotasi ini ditulis dengan cara mengikuti alursebagai berikut :

Page 122: Struktur Data

Halaman 122

Rekonstruksi Algoritma{Deklarasi Type}

Type Infotype = … {terdefinisi}Type node = record <Info : infotype,

Left : address,Right: address >

Type BinTree : address

{Primitif}

Page 123: Struktur Data

Halaman 123

function Akar (P : BinTree)→ infotype{Mengirimkan nilai Akar pohon biner P}

function Left (P : BinTree)→ infotype{Mengirimkan anak kiri pohon biner P}

function Right (P : BinTree)→ infotype{Mengirimkan anak kanan pohon biner P}

Page 124: Struktur Data

Halaman 124

function IsEmpty(P : BinTree)→boolean{ Test apakah sebuah pohon kosong,

mengirimkan True jika kosong dan False jikatidak}

procedure MakeTree(input Akar : infotype, L : BinTree, R : BinTree, output P : BinTree)

{ K. Awal : sembarangK. Akhir : Terbentuk sebuah pohon binerProses : Menghasilkan sebuah pohon biner

dari Akar, L dan R}

Page 125: Struktur Data

Halaman 125

{Traversal}Procedur PreOrder(input P : BinTree){K. AWAL : P terdefinisiK. AKHIR : Semua simpul P sudah

diproses secara preorder}

Procedure InOrder(input P : BinTree){K. AWAL : P terdefinisiK. AKHIR : Semua simpul P sudah

diproses secara inorder}

Page 126: Struktur Data

Halaman 126

Procedure PostOrder(input P : BinTree){K. AWAL : P terdefinisiK. AKHIR : Semua simpul P sudah

diproses secara postorder}

Procedure PrintTree(input P : BinTree, h : integer){K. AWAL : P terdefinisi, h adalah jarak indentasiK. AKHIR : Semua simpul P sudah ditulis dengan

indentasi}

Page 127: Struktur Data

Halaman 127

{Search}function Search(P : BinTree, X : infotype)→boolean{Mengirimkan True jika ada node P bernilai X, false

jika tidak}

{fungsi lain}function NbElmt(P : BinTree)→integer{Mengirimkan banyaknya elemen (node) pohon

biner P}

Page 128: Struktur Data

Halaman 128

function NbDaun(P : BinTree) →integer{ Mengirimkan banyaknya daun pohon biner P}function IsUnerLeft(P : BinTree) →boolean{ Mengirimkan True jika pohon biner tidak

kosong P adalah pohon unerleft yaitu hanyamempunyai sub pohon kiri}

function IsUnerRight(P : BinTree) →boolean{ Mengirimkan True jika pohon biner tidak

kosong P adalah pohon unerright yaitu hanyamempunyai sub pohon kanan}

Page 129: Struktur Data

Halaman 129

function IsBin(P : BinTree)→boolean{ Mengirimkan True jika pohon biner tidak

kosong P adalah pohon biner yaitu mempunyaisub pohon kanan dan sub pohon kiri}

function IsSkewLeft(P : BinTree)→boolean{ Mengirimkan True jika pohon biner P adalah

pohon condong kiri}

function IsSkewRight(P : BinTree)→boolean{ Mengirimkan True jika pohon biner P adalah

pohon condong kanan}

Page 130: Struktur Data

Halaman 130

function Tinggi(P : BinTree)→integer{ Mengirimkan tinggi dari pohon biner P}

function Level(P : BinTree, X : infotype)→integer{ Mengirimkan level dari node X yang merupakan

salah satu simpul dari pohon biner P}

{Operasi Lain}

Page 131: Struktur Data

Halaman 131

Procedure AddDaunTerkiri(input/output P:BinTree, input X: infotype)

{K. AWAL : P boleh kosongK. AKHIR : P bertambah simpulnya, dengan X

adalah simpul daun terkiri}Procedure AddDaun(input/output P:BinTree, input

X, Y : infotype, input Kiri : boolean){K. AWAL : P tidak boleh kosong, X adalah salah

satu daun pohon Biner PK. AKHIR : P bertambah simpulnya, dengan Y

adalah anak kiri X (jika kiri) atausebagai anak kanan X (jika not kiri)}

Page 132: Struktur Data

Halaman 132

Procedure DelDaunTerkiri(input/outputP:BinTree, output X: infotype)

{K. AWAL : P tidak kosongK. AKHIR: P dihapus daun terkirinya dan

didealokasi, dengan X adalah info yang semula disimpan pada daunterkiri yang dihapus}

Procedure DelDaun(input/output P:BinTree, output X: infotype)

{K. AWAL : P tidak kosong, X adalah salah satudaun

K. AKHIR : X dihapus dari P}


Top Related