universitas riwijaya -...

29

Upload: phamngoc

Post on 21-Mar-2019

224 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum
Page 2: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

Universitas riwijaya

Fakultas Ilmu

Komputer

Laboratorium

LEMBAR

PENGESAHAN

MODUL

PRAKTIKUM

SISTEM

MANAJEMEN

MUTU ISO

9001:2008

No. Dokumen Tanggal 4 AGUSTUS 2016

Revisi Halaman 2 DARI 48

MODUL PRAKTIKUM

Mata Kuliah Praktikum : Struktur Data

Kode Mata Kuliah Praktikum : FIK214009

SKS : 1

Program Studi : SISTEM INFORMASI

Semester : 3 (Ganjil) 2016/2017

DIBUAT OLEH DISAHKAN OLEH DIKETAHUI OLEH

DOSEN PENGAMPUH

Dinna Yunika Hardiyanti,

M.T.

KETUA JURUSAN

Endang Lestari R, M.T.

WAKIL DEKAN 1

BIDANG AKADEMIK

Syamsuryadi, S. SI., M. Kom

Page 3: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

DAFTAR ISIMODUL I...................................................................................................................................2

Pengenalan..............................................................................................................................2

MODUL II..................................................................................................................................8

LIST I.........................................................................................................................................8

MODUL III..............................................................................................................................19

STACK.....................................................................................................................................19

MODUL IV.............................................................................................................................. 22

QUEUE....................................................................................................................................22

MODUL V................................................................................................................................25

TREE.......................................................................................................................................25

Page 4: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

MODUL IPengenalan

I. TujuanSetelah mengerjakan LKP 1 ini, anda diharapkan dapat :

1. Mengenal lingkungan salah satu compiler bahasa pemrograman C yaitu Turbo C++ 4.5.

2. Menggunakan compiler tersebut untuk menyelesaikan kasus sederhana.

AI. Dasar TeoriPengenalan Lingkungan Turbo C++ 4.5

Turbo C++ 4.5 adalah tool yang dipakai untuk membuat code program dalam bahasa

C ataupun C++. Berikut adalah jendela utama Turbo C++ 4.5.

1

2

3

4

1 : Menu Utama

2 : Toolbar

3 : Jendela pengetikan kode program

4 : Jendela Message / pesan kesalahan kode

Create new, Open, Save, Save As File

Untuk memulai membuat kode program di Turbo C++ 4.5 langkah-langkahnya adalah

sebagai berikut :

1. Buka Turbo C++ 4.5 dari menu program sehingga akan keluar jendela Turbo C++

berikut :

Page 5: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

2. Kemudian pilih menu File > New maka akan tampil jendela baru (di dalam jendela

utama Turbo C++) untuk menuliskan kode program.

3. Setelah menuliskan kode program maka simpan dengan memilih menu File > Save as

(untuk menyimpan dengan nama baru) atau File > Save (Tidak menyimpan dengan

nama baru bila sudah pernah disimpan). Tentukan dirve dan direktori tempat

penyimpanan.

Page 6: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

Untuk membuka file atau kode program yang sudah pernah dibuat maka langkah-langkahnya

adalah seperti berikut :

1. Pilih menu File > Open maka akan tampil jendela seperti berikut :

2. Tentukan drive dan direktori lokasi tempat menyimpan file program kemudian klik OK.

Compile Program, Pendeteksian Error dan Warning, Run Program

Setelah menuliskan kode program, maka berikutnya adalah compile program dengan

tujuan untuk mendeteksi kesalahan-kesalahan dalam penulisan kode program.Adapun

langkah-langkahnya adalah sebagai berikut :

1. Pilih menu Project > Compile, atau kombinasi tombol ALT+F9, akan tampil jendela

status compile seperti berikut :

Dari status di atas maka tidak ditemukan error atau warning pada program.

Page 7: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

Dari status di atas dapat dilihat bahwa terdapat error pada program. Untuk melihat pesan

error tersebut klik OK maka akan tampil jendela pesan error seperti berikut :

Jendela di bawah ini menunjukkan terdapat warning pada program.

Untuk melihat pesan warning tersebut, klik tombol OK.

2. Setelah kode program di-compile maka langkah berikutnya adalah menjalankannya,

yaitu dengan memilih menu Debug > Run atau kombinasi tombol CTRL+F9.

Pengenalan C++

Setiap program C++ mempunyai bentuk seperti berikut ini yaitu:

Prepocessor Directive

Page 8: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

Adalah salah satu pengarah prepocessor directive yang tersedia pada C++. Preprocessor

selalu dijalankan terlebih dahulu pada saat proses kompilasi terjadi. Bentuk umumnya :

# include <nama_file>

tidak diakhiri dengan tanda semicolon, karena bentuk tersebut bukanlah suatu bentuk

pernyataan, tetapi merupakan prepocessor directive. Baris tersebut menginstrusikan kepada

kompiler yang menyisipkan file lain dalam hal ini file yang berakhiran .h(file header) yaitu

file yang berisi sebagai deklarasi contohnya:

Preprocessor Directive Fungsi

#include <iostream.h> Diperlukan pada program yang melibatkan objek cout

#include<conio.h> Diperlukan bila melibatkan clscr(),yang perintah unrtuk

membersihkan layar

#include<iomanip.h> Diperlukan bila melibatkan setw() yang bermanfaat untuk mengatur

lebar dari suatu tampilan data

#include<math.h> Diperlukan pada program yang menngunakan operasi sqrt() yang

bermanfaat untuk operasi matematika kuadrat

Fungsi Main ()

Fungsi ini menjadi awal dan akhir eksekusi program C++. main adalah nama judul fungsi.

Melihat bentuk seperti itu dapat kita ambil kesimpulan bahwa batang tubuh program utama

berada didalam fungsi main( ). Kata void yang mendahului main() dipakai untuk

menyatakan bahwa fungsi ini tidak memiliki nilai balik.

Komentar

Komentar merupakan bagian yang penting dalam program. Kehadirannya sangat membantu

pemrogram ataupun orang lain dalm memahami program,karena berupa penjelasan

Page 9: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

mengenaiprogram atau bagian-bagian dari program.Komentar tidak pernah dicompile oleh

compiler. Dalam C++ terdapat 2 jenis komentar, yaitu :

Jenis 1 : /* Komentar anda diletakkan di dalam ini

Bisa mengapit lebih dari satu baris */

Jenis 2 : // Komentar anda diletakkan disini ( hanya bisa perbaris )

Tanda Semikolon

Tanda semicolon “ ; ” digunakan untuk mengakhiri sebuah pernyataan. Setiap pernyataan

harus diakhiri dengan sebuah tanda semicolon.

BI. PrepraktikumInstal program Turbo C++ pada computer atau laptop

IV. Kegiatan Praktikum1. Bukalah software Turbo C++

2. Program mengeluarkan tulisan ”Selamat Datang di Fakultas Ilmu Komputer”

Algoritma

Deklarasi :

-

Algoritma :

write(“Selamat Datang di Fakultas Ilmu Komputer”)

Ketikkan kode program berikut berdasarkan algoritma yang diberikan diatas

3. Compile program dengan menekan Alt + F9 atau pilih menu Project Compile

4. Jalankan program dengan menekan Ctrl + F9 atau pilih menu Debug Run

5. Simpan file dengan nama Praktikum1.cpp

6. Buka file baru dengan menekan File New

7. Ketikkan kode program berdasarkan algoritma yang diberikan

Algoritma

Page 10: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

Deklarasi :

-

Algoritma :

write(“Selamat Datang di Fakultas Ilmu Komputer”)

write(“Nama Anda”)

write(“NIM Anda”)

write(“Jurusan Anda”)

8. Simpan file dengan nama Praktikum2.cpp

9. Jalankan program praktikum2.cpp

I. Hasil LKP (ditulis tangan di kertas A4)

LEMBAR KERJA PRAKTIKUMSTRUKTUR DATA

NAMA TANGGALNIM WAKTU

KELAS PERTEMUAN

MODUL IILIST I

I. TujuanSetelah mengerjakan LKP ini, anda diharapkan dapat :

1. Memahami konsep list dan mampu mengimplementasikannya ke bahasa C.

2. Mampu melakukan operasi insert dan delete pada list.

II. Dasar Teori

Page 11: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

List Linier

List linier adalah sekumpulan elemen bertype sama, yang mempunyai keterurutan

tertentu, dan setiap elemennya terdiri dari dua bagian, yaitu informasi mengenai elemennya,

dan informasi mengenai alamat elemen suksesornya :

type ElmtList : <Info : InfoType, Next : address>

Dengan InfoType adalah sebuah type terdefinisi yang menyimpan informasi sebuah

elemen list; Next adalah address (“alamat”) dari elemen berikutnya (suksesor). Dengan

demikian, jika didefinisikan First adalah alamat elemen pertama list, maka elemen berikutnya

dapat diakses secara suksesif dari field Next elemen tersebut. Alamat yang sudah

didesfinisikan disebut sudah di alokasikan. Didefinisikan suatu konstanta Nil, yang artinya

alamat tidak terdefinisi. Alamat ini nantinya akan didefinisikan secara lebih konkret list linier

diimplementasi pada struktur data fisik.

Jadi, sebuah list linier dikenali :

- elemen pertamanya, biasanya melalui alamat elemen pertama yang disebut : First.

- Alamat elemen berikutnya (suksesor), jika kita mengetahui alamat sebuah elemen yang

dapat diakses melalui informasi NEXT. NEXT mungkin ada secara eksplisit (seperti

contoh di atas), atau secara implisit yaitu lewat kalkulasi atau fungsi suksesor

- Setiap elemen mempunyai alamat, yaitu tempat elemen disimpan dapat diacu. Untuk

mengacu sebuah elemen, alamat harus terdefinisi. Dengan alamat tersebut informasi yang

tersimpan pada elemen list dapat diakses.

- Elemen terakhirnya

Ada berbagai cara untuk mengenali elemen akhir Jika L adalah list, dan P adalah address :

Alamat elemen pertama list L dapat diacu dengan notasi :

First(L)

Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi Selektor :

Info(P)

Next(P)

Beberapa definisi :

List L adalah list kosong, jika First(L) = Nil

Elemen terakhir dikenali, misalnya jika Last adalah alamat element terakhir, maka

Page 12: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

Next(Last) =Nil

Skema Traversal untuk List Linier

List terdiri dari sekumpulan elemen. Seringkali diperlukan untuk memproses setiap

elemen list dengan cara yang sama. Karena itu salah primitif operasi konsultasi dasar pada

struktur list adalah traversal, yaitu “mengunjungi” setiap elemen list untuk diproses. Karena

Urutan akses adalah dari elemen pertama sampai dengan elemen terakhir, maka traversal list

secara natural dilakukan dari elemen pertama, suksesornya, dan seterusnya sampai dengan

elemen terakhir.

Page 13: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

Skema Sequential Search untuk list linier

Selain traversal, proses pencarian suatu elemen list adalah primitif yang sering kali

didefinisikan pada struktur list. Pencarian dapat berdasarkan nilai, atau berdasarkan

alamat.

o Search suatu Nilai, output a/ address

Search ini sering dipakai untuk mengenali suatu elemen list berdasarkan

nilai informasi yang disimpan pada elemen yang dicari. Biasanya dengan alamat

yang ditemukan, akan dilakukan suatu proses terhadap elemen list tersebut.

Page 14: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

1. INSERT-First by Address

Menambahkan sebuah elemen yang diketahui alamatnya sebagai elemen pertama list.

Insert elemen pertama, List kosong :

2. INSERT-First by Value

Menambahkan sebuah elemen yang diketahui nilainya sebagai elemen pertama list.

Tahap Pertama :

Insert nilai 3 sebagai elemen pertama list. Karena yang diketahui adalah nilai, maka harus

dialokasikan dahulu sebuah elemen supaya nilai 3 dapat di-insert.

Jika alokasi berhasil, P tidak sama dengan Nil.

Tahap Kedua : Insert ke list kosong

Page 15: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

3. INSERT-After by Address

Menyisipkan sebuah elemen beralamat P setelah sebagai suksesor dari sebuah

elemen list linier yang beralamat Prec.

Page 16: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

4. INSERT-Last by Address

Menyisipkan sebuah elemen beralamat P sebagai elemen terakhir sebuah list linier. Ada dua

kemungkinan list kosong atau tidak kosong.

Insert sebagai elemen terakhir list tidak kosong :

Insert sebagai elemen terakhir list tidak kosong :

Page 17: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

5. INSERT-Last by Value

Menambah sebuah elemen yang diketahui nilainya pada elemen terakhir list.

6. DELETE-First by Address

Menghapus elemen pertama list yang diketahui alamatnya sebagai elemen pertama list.

Elemen yang dihapus dicatat alamatnya.

7. DELETE-First by Values

Menghapus elemen pertama list linier yang diketahui nilainya sebagai elemen pertama list.

Page 18: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

8. DELETE – After by Address

Penghapusan suksesor sebuah elemen :

9. DELETE –Last :

Menghapus elemen terakhir list dapat dilakukan jika alamat dari elemen sebelum

elemen terakhir diketahui. Persoalan selanjutnya menjadi persoalan DELETE AFTER,

kalau Last bukan satu-satunya elemen list linier. Ada dua kasus, yaitu list menjadi kosong

atau tidak. Kasus list menjadi kosong :

Page 19: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

List tidak menjadi kosong (masih mengandung sebuah elemen);

CONCAT : L1 x L2 → L { Menyambungkan L1 dengan L2}

Konkatenasi adalah menggabungkan dua list. Dalam contoh berikut list kedua disambungkan

ke list pertama. Jadi Last(L1) menjadi predesesor First(L2). Realisasi algoritmanya adalah

sebagai berikut :

Page 20: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum
Page 21: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

MODUL IIISTACK

Stack (tumpukan) adalah list linier yang :1. Dikenali elemen puncaknya (TOP)2. Aturan penyisipan dan penghapusan elemennya tertentu :

a. Penyisipan selalu dilakukan “diatas” TOPb. Penghapusan selalu dilakukan pada TOP

TOP adalah satu – satunya alamat tempat terjadi operasi, elemen yang ditambahkan palingakhir menjadi elemen – elemen yang akan dihapus. Dikatakan bahwa elemen stack akantersusun secara LIFO (Last In First Out).

Operasi dan Fungsi StackOperasi dasar stack digunakan dari definisi fungsional stack. Bila S adalah stack dengan

elemen ElmtS, maka :

Page 22: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

1. Operasi untuk menciptakan stackprocedur CreateStack (output S : Stack){IS : Sembarang }{FS : Stack S tercipta, Top = Nil }Kamus :

Algoritma :Top (S) ← Nil

2. Operasi untuk menambah elemen pada stackprocedure pushbyAddress (input/output S : stack, input P : Address){IS : Stack S mungkin kosong, P terdefinisi }{FS : P menjadi TOP dari stack S }Kamus :Algoritma :

If StackEmpty (S) thenTOP (S) ←P

ElseNext (P) ← TOP (S)TOP (S) ← P

procedure pushbyValue (input/output S : stack, input P : Elmts){IS : Stack S mungkin kosong, E terdefinisi, alokasi alamat selalu berhasil }{FS : TOP (S) berisi E }Kamus :

P : addressAlgoritma :

Alokasi (P) { alokasi selalu berhasil }Elmts (P) ← EIf StackEmpty (S) then

TOP (S) ←PElse

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

3. Operasi untuk menghapus (mengambil) elemen stackprocedure popbyAddress (input/output S : stack, output P : Address){IS : Stack S terdefinisi, mungkin kosong }{FS : P adalah alamat elemen yang diambil }Kamus :Algoritma :

P ← TOP (S)If not StackEmpty (S) then

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

Page 23: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

procedure popbyValue (input/output S : stack, output P : Address){IS : Stack S terdefinisi, mungkin kosong }{FS : Elemen TOP disimpan pada E, alamat TOP yang lama di-dealokasi }Kamus :Algoritma :

P ← TOP (S); E.Info ← Info (P); E.Next ← NilTOP (S) ← Next (TOP(S))Dealokasi (P)

4. Fungsi untuk memeriksa apakah stack kosong atau tidakfunction StackEmpty (S : Stack) → Boolean{ mengirim true jika stack kosong dan false jika stak tidak kosong}Kamus :Algoritma :→ (TOP (S) = Nil)

Page 24: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

MODUL IVQUEUE

Queue (atrian) adalah list linier yang :1. Dikenali elemen pertamanya (HEAD) dan elemen terakhirnya (TAIL)2. Aturan penyisipan dan penghapusan elemena didefinisikan sebagai berikut :

a. Penyisipan selalu dilakukan setelah elemen terakhirb. Penghapusan selalu dilakukan pada elemen pertama

3. Satu elemen dengan yang lain dapat diakses melalui informasi NEXTMaka secara logic, sebuah QUEUE dapat digambarkan sebagai list linier yang setiapelemenya adalah

Type ElmtQ : < Info : InfoType, Next : Address >Dengan InfoType adalah sebuah type terdefinisi yang menentukan informasi yang disimpanpada setiap elemen queue, dan address adalah “alamat” dari elemen. Selain itu, alamatelemen pertama (HEAD) dan elemen terakhir (TAIL) dicatat. Maka jika Q adalah Queue danP adalah address, penulisan untuk Queue adalah :

Head (Q), Tail (Q), Info (Head(Q)), Info(Tail(Q))

Operasi dan Fungsi Dasar pada AntrianDiberikan Q adalah Queue dengan elemen ElmtQ maka definisi fungsional antrian adalah :

Page 25: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

1. Fungsi untuk memeriksa antrian kosongfunction QEmpty (Q : Queue) → boolean{ mengirim true jika antrian kosong dan false jika antrian tidak kosong }Deklarasi :Deskripsi :

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

2. Pembuatan sebuah Queue kosongprocedure CreateQ (output Q : Queue){IS : sembarang }{FS : tercipta sebuah queue kosong }Deklarasi :Deskripsi :

Head(Q) ← Nil ; Tail(Q) ← Nil

3. Penambahan sebuah elemen pada antrianprocedure InsertQ (input/output Q : Queue, input P : address){IS : Antrian Q terdefinisi mungkin kosong, P sudah dialokasi, P ≠ nil,

Next (P) = nil}{FS : P menjadi elemen Tail dari antrian Q}Deklarasi :Deskripsi :

If QEmpty (Q) then {insert sebagai elemen pertama}Head(Q) ← P

ElseNext (Tail(Q) ← P)Tail (Q) ← P

4. Penghapusan sebuah elemen pada antrianprocedure DeleteQ@ (input/output Q : Queue, output P : address){IS : Q terdefinisi tidak kosong}{FS : P adalah alamat elemen yang diambil, P ≠ nil, Next (P) = nil, antrianmungkin menjadi kosong }Deklarasi :Deskripsi :

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

Tail (Q) ← NilElse

Next (P) ← Nil

procedure DeleteQ (input/output Q : Queue, output E : ElmtQ){IS : Q terdefinisi tidak kosong}{FS : E adalah alamat elemen yang diambil, antrian mungkin menjadi kosong }

Page 26: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

Deklarasi :P : address

Deskripsi :P ← Head (Q)Head (Q) ← Next (Head (Q))If (Head (Q) = Nil) then

Tail (Q) ← NilElse

Next (P) ← NilE.Info ← Info (P)E.Next ← Next (P)

Page 27: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

MODUL VTREE

Tree merupakan salah satu bentuk struktur data linier yang menggambarkanhubungan yang bersifat hierarkis (hubungan one to many) antara elemen – elemen. Tree bisadidefinisikan sebagai kumpulan simpun/node dengan elemen khusus yang disebut Root.Node lainnya terbagi menjadi himpunan – himpunan yang saling tak berhubungan satu samalain (disebut subtree).

1. Beberapa Istilah pada TREE :

Simpul (node) adalah elemen dari pohon yang memungkinkan akses pada sub pohondimana simpul tersebut berfungsi sebagai AKAR.

Cabang (path) adalah hubungan antara akar dengan sub pohon. Ayah adalah akar dari sebuah pohon. Anak adalah sub pohon dari sebuah akar. Saudara adalah simpul – simpul yang mempunyai ayah yang sama. Daun adalah simpul terminal dari pohon. Semua simpul selain daun adalah simpul bukan

terminal. Jalan (path) adalah suatu urutan tertentu dari cabang. Derajat sebuah pohon adalah banyaknya anak dari pohon tersebut. Sebuah simpul

berderajat N disebut sebagai pohon N-aire. Pada pohon biner, derajat dari sebuah simpulmungkin 0-aire (daun), 1-aire/uner atau 2-aire/biner.

Tingkat (level) pohon adalah panjangnya jalan dari akar sampai dengan simpul yangbersangkutan. Dua buah simpul disebut sepupu jika mempunyai tingkat yang sama dalamsatu pohon.

Kedalaman atau Tinggi sebuah pohon adalah nilai maksimum dari tingkat simpul yangada pada pohon tersebut. Kedalaman adalah panjang maksimum jalan dari akar menujuke sebuah daun.

Lebar sebuah pohon adalah maksimum banyaknya simpul yang ada pada suatu tingkat.

2. POHON BINER

Pohon biner merupakan struktur pohon yang paling penting dan paling banyakpenggunaannya. Tiap simpul pda pohon biner, kecuali daun, mempunyai maksimum 2buah sub pohon. Jadi pohon biner mungkin salah satu dari pernyataan berikut : Kosong Terdiri dari akar dan tidak memiliki sub pohon kiri maupun sub pohon kanan Terdiri dari akar dan sub pohon kiri, tidak memiliki sub pohon kanan Terdiri dari akar dan sub pohon kanan, tidak memiliki sub pohon kiri Terdiri dari akar, sub pohon kanan, dan sub pohon kiri

Istilah kiri dan kanan hanya istilah dari kacamata manusia, karena memori computertidak mengenal bagian kiri atau bagian kanan. Pemrogram yang harus mendefinisikan kiridan kanan itu sendiri.

Page 28: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

3. Refresentasi Pohon Biner

Pohon Biner dapat direfresentasikan dengan cara larik dan list berkait.

Refresentasi dengan Larik/Array :

Kamus :Constant N : integer = 100 { jumlah maksimum simpul }Type InfoType = ………… { terdefinisi }Type simpul : <Info : InfoType, Kiri : integer, Kanan : integer>Type Pohon_biner = array [1…N] of simpulT : Pohon_biner

Refresentasi dengan List :Kamus :Type InfoType = ………………. { terdefinisi }Type Pohon_biner = address { tipe terdefinisi mengacu ke simpul suatu

pohon_biner dengan pointer ditulis sbb : typePohon_biner = pointer to simpul }

Type simpul : < info : InfoType, Kiri : Pohon_biner, Kanan : Pohon_biner >T : Pohon_biner

4. Operasi Dasar Pohon Biner

Menghitung Tinggi Pohon BinerJika T adalah pohon biner, maka tinggi pohon T dapat dihitung secara rekrusif.Function Tinggi ( T : Pohon_biner ), integer{ Pohon biner mungkin kosong, tinggi mengirim ‘depth’ dari pohon binerBase : T kosong, maka tingginya nolRekrusif : T tidak kosong, maka Tinggi (T) = 1+ maks dari Tinggi ankanya}Kamus :Algoritma :Depend on TT = NilT ….

Menghitung Jumlah Simpul Pohon BinerFunction JumlahSimpul (T : Pohon_biner) integer{ Menghitung jumlah simpul pohon biner TBase : T kosong, maka jumlah simpul = 0Rekrusif : T tidak kosong, maka jumlah simpul (T) = 1+ JumlahSimpul (kiri(T)) +

JumlahSimpul (kanan(T)) }Kamus :Algoritma :Depend on T

T = NilT ≠ Nil

Page 29: Universitas riwijaya - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/.../2018/11/Modul-Praktikum-Struktur-Data-FIX.pdf · Mata Kuliah Praktikum : Struktur Data Kode Mata Kuliah Praktikum

Menghitung Jumlah Daun Pohon BinerFunction JumlahDaun (T : Pohon_biner) integer{ Menghitung jumlah daun pohon biner TBase : T kosong, maka jumlah daun = 0

T hanya simpul akar, maka jumlah daun = 1Rekrusif : T tidak kosong, maka JumlahDaun (T) = JumlahDaun (kiri(T)) +

JumlahDaun (kanan(T)) }Kamus :Algoritma :If T = Nil then

JumlahDaun ← 0Else

If (kiri (T) = Nil) and (kanan (T) = Nil) thenJumlahDaun ← 1

elseJumlahDaun ← JumlahDaun (kiri(T)) + JumlahDaun (kanan(T))