BAB 1 KONSEP DASAR 1.1 Algoritma Algoritma + struktur data = program Algoritma adalah urutan langkah-langkah logis untuk menyelesaikan sebuah masalah yang disusun secara sistematis. Notasi untuk menuliskan algoritma disebut notasi algoritmik yang tidak dapat dijalankan oleh komputer. Agar dapat dijalankan oleh komputer maka program dalam notasi algoritmik harus ditranslasikan {diterjemah} kedalam notasi bahasa pemograman yang dipilih. Notasi algoritmik Instruksi Pemberian harga
Bentuk umum nama-data nama-data nama-data
nama –data konstanta ekspresi
Masukan
Input (nama-data)
Keluaran
output (nama-data) output (konstanta) output (ekspresi) If kondisi then aksi-1 else aksi-2
Pemilihan kondisi
Pengulangan
Contoh P Q P Q P Q input (N) input (harga) output (N) output („hello‟) output (X+Y)
depend on (nama-data) aksi-1 aksi-2 Repeat N times Aksi
Repeat 5 times Output („hello‟)
Repeat Aksi Until kondisi-berhenti
Repeat X Until X>5
While kondisi do Aksi
While X <= 5 do X X+1
Itraversal [1...N] Aksi
X traversal [1..5] Output („hello‟)
X+1
1.2 Pengertian Struktur Data Struktur Data adalah membuat sebuah struktur penyimpanan data yang digunakan saat program dijalankan.
58
Struktur data berada pada level pemograman dimana digunakan untuk tempat penyimpanan data yang digunakan oleh program terkaikt dengan alokasinya dimemori (bukan storage atau hardisk). Struktur alokasi dimemori untuk menyimpan data yang sedang digunakan oleh Program inilah fokus dari struktur data. Ilustrasi dari struktur data dapat dilihat pada gambar berikut :
Lingkup Struktur Data Dapat disimpan
Data
Menggunakan
Data Memori
Hardisk/ Storage
Gambar 1 Ilustri Struktur data 1.2.1 Tujuan Struktur Data Struktur data bertujuan agar cara merepresentasikan data dalam membuat program dapat dilakukan secara efisien dalam pengolahan di memori dan pengolahan penyimpanan dari program ke storage juga lebih mudah dilakukan. Struktur data sebenarnya meliputi larik (array) dan record (rekaman) pada berkas beruntun (sequential file). 1.2.2 Langkah Pembuatan Struktur Data Pembuatan Struktur data dimulai dari : Langkah 1 : Analisis perancangan data apa yang harus dimanipulasi di memori agar program yang dibuat lebih efisien. Langkah 2 : Mengimplementasikan struktur data dalam bahasa pemograman. Langkah 3 : Menggunakan struktur data yang sudah dibuat untuk memanipulasi data di memori dalam sebuah program. Contoh ilustrasi langkah-langkah berikut : Ilustrasi Keterangan Misalkan ada sebuah data manusia yang terdiri dari : nama alamat TTL No_telp *nama ? ? ? ? *alamat *TTL (Tempat/ Tanggal lahir) *no_telp (nomor telepon) Dan diperlukan untuk menyimpan data manusia, maka dalam logika akan dipersiapkan tempat untuk menyimpan
59
nama faiz
nama
alamat jakarta
alamat
faiz
jakarta
faris
medan
TTL No_telp Palembang/07 444000 april 2007
TTL Palembang/07 april 2007 Palembang/03 agustus 2009
No_telp 444000
sebuah data manusia, maka dibuat tipe data bentukan untuk menyimpan data manusia. Misalkan dari data manusia yang ada diisi dengan data seorang manusia.
Misalkan dari data manusia yang ada digunakan untuk menampung beberapa data manusia.
445000
Dari ilustrasi diatas dapat dilihat bahwa struktur data adalah cara menyediakan tempat yang baik dan tersusun secara terstruktur agar data yang disimpan dapat dibaca dengan lebih mudah. Struktur data dapat dikatagorikan dengan type, yaitu : 1. Tipe data dasar a. Integer, untuk mendefinisikan nama-data yang menyimpan harga berupa bilangan bulat. Contoh : X : integer Nilai angka : integer [0..100] b. Real, untuk mendefinisikan nama-data berupa bilangan pecahan yang mengandung pecahan desimal. Contoh : Harga : real Potongan : real c. Karakter, untuk mendefinisikan nama-data yang menyimpan harga berupa karakter yang tidak dapat diproses secara aritmatika. Contoh : Nilai huruf : charakter [„A‟....‟E‟] d. Logika, untuk mendefinisikan nama-data yang menyimpan harga benar-salah Contoh : Ketemu :boolean 2. Tipe data bentukkan Tipe data bentukkan adalah tipe yang didefinisikan sendiri oleh pemograman, yang disusun oleh satu atau lebih tipe dasar. Contoh: tipe data string, yang dibangun dari tipe dasar karakter 3. File 60
Sekumpulan rekaman yang disimpan dalam media penyimpanan mulai dari rekaman pertama sampai terakhir satu persatu, secara searah. 4. Tabel Tabel, untuk merepresentasikan sekumpulan informasi yang bertipe sama dan disimpan dengan urutan yang sesuai dengan definisi secara kontigu dalam memori komputer. Contoh : TabNilMhs : array [1....Nmhs] of real
1.2.3 Tiga tingkatan struktur data 1. Definisi fungsional Pendefinisian struktur data dan operator-operator yang berlakupada struktur data tersebut mendefinisi tipe data 2. Representasi logika Pendefinisian spesifikasi „type‟ dari struktur yang menyengkut nama tipe dan spesifikasi semua operator. 3. Representasikan fisik (implementasikan) Spesifikasi dari struktur data sesuai dengan implentasinya dalam memori komputer. 1.3 Pengenalan C++ Tahun 1969, laboratorium Bell AT&T di Muray Hill, New Jersey menggunakan bahasa assembly ini untuntuk mengembangkan sistem operasi UNIX. Maksudnya adalah untuk membuat sistem operasi yang bersifat “programmer_friendly”. Setelah UNIX berjalan Ken Thompson seorang pengembang sistem dilabotorium tersebut mengembangkan bahasa baru dengan nama bahasa B. Oleh karena bahasa B ini masih bersifat interpret dan lambat, maka pada tahun 1971, sistem operasi UNIX kemudian ditulis ulang dengan ulang dengan menggunakan bahasa C, yaitu bahasa pemograman yangdikembangkan oleh Dennis Ritchie, seorang pengembang sistem dilaboratorium yang sama.Pada tahun 1993, seorang doktor bernama Bjarne Stroustrup yang juga bekerja dilaboratorium yang sama menciptakan bahasa baru yaitu bahasa C++. Keistimewaan dari bahasa C++ adalah karena bahasa ini mendukung pemograman berarah objek atau yang lebih seringdikenal dengan istilah Object Oriented Programming (OOP). Konsep Kompilasi dan Eksekusi Program Preprocessor Mula-mula kode program akan dimasukkan kebagian preprosesor yaitu yang diawali dengan tanda # (pound) dan menghasilkan file yang akan dilewatkankebeberapa kompiler. Beberapa preprocessor tersebut diantaranya adalah sebagai berikut :
#include #define #ifdef, dll
Kode program (source code)
preprosesor
kompiler
assembler
61
Kompiler C++ Kompiler akan menterjemahkan kode program yang telah dilewatkan oleh preprosesor ke dalam bahasa assembly. Assembler Assembler menerima keluaran dari kompiler C++ dan akan membuat sebuah kode objek. Jika dalam kode program kita tidak menggunakan fungsi-fungsi yang terdapat pada library lain, maka kode objek ini akan langsung dieksekusi menjadi file EXE. Link Editor Bagian ini dikerjakan jika kode program yang kita buat menggunakan fungsi-fungsi yang disimpan pada suatu library lain. Link editor akan mengkombinasikan kode objek dan library yang ada untuk menjadikan sebuah file EXE. Contoh program yang ditulis dalam bahasa C #include
Int main() { Int X; Cout<<”Masukkan sebuah bilangan bulat : ”; Cin>>X; Cout<<”Bilangan yang telah Anda masukkan adalah “<<X; Return 0; } Contoh hasil yang akan diberikan dari program diatas adalah sebagai berikut : Masukkan sebuah bilangan bulat :2 Bilangan yang telah anda masukkan adalah 2
62
PENGURUTAN (SORTING) 2.1 Definisi Pengurutan Pengurutan (sorting) adalah proses mengatur sekumpilan objek menurut urutan atau susunan tertentu. Pengurutan tersebut dapat menaik (Ascending) atau menurun (Decending). Data yang diurut dapat berupa data type data sederhana (kecuali boolean) atau type data terstruktur. Keuntungan dari data yang telah berurut dapat mempercepat pencarian, juga dapat harga maksimum dan minimum secara langsung. 2.2 Metode Pengurutan Metode pengurutan yang akan dibahas: 1. Pengurutan Gelembung (Bubble sort) 2. Pengurutan Maksimum/ Minimum (Maximum/ minimum sort) 3. Pengurutan Sisip (insertion Sort) 2.3 Pengurutan Gelembung (Bubble Sort) PENGURUTAN BILANGAN DENGAN METODE BUBBLE SORT
Proses Pengurutan
Bubble Sort adalah nama yang diberikan pada prosedur untuk mengatur sekelompok bilangan dengan urutan dari kecil ke besar.
Untuk mengurutkan bilangan diperlukan variabel array yang digunakan untuk menampung semua bilangan yang akan diurutkan.
Proses pengurutan dilakukan dengan membandingkan semua elemen array satu persatu.
Contoh : 20
12
35
11
17
9
58
23
63
Dalam metode bubble sort, pengurutan demulai dengan membandingkan elemen pertama untuk mendapatkan angka terbesar. Lalu angka tersebut ditempatkan pada elemen terakhir.
64
IMPLEMENTASI DALAM BENTUK FLOWCHART 1
START
J=J+1 2
I = 0
I=I+1
J = 0 N=0
INPUT
BILLAR(I)
BIL
< BILLAR(I+1)
BIL=0
N=N+1
1
TIDAK
TEMP
= BILLAR(I)
BILLAR(I) = BILLAR(I+1) BILLAR
= TEMP
BILLAR(N) = BIL I=N-J 2
YA YA
PRINT BILLAR(I)
I=I+1
J=N-1
I=0
TIDAK
I=N
I=0
Bubble Sort tidak lain adalah pengulangan prosedur1 hingga bilangan –
END
bilangan yang ada tersusun menurut urutan dari yang kecil ke yang besar. Contoh Buble Sort 6
5
8
3
8
3
Pertama : 6
5
5
6
8
3
5
6
3
8
5
6
3
8
6
8
Pada akhir proses pertama ini, bilangan yang terbesar menempati tempat yang sesuai.
Kedua : 5
6
3
8
5
6
3
8
5
3
6
8
5
3
Pada akhir proses kedua ini, bilangan terbesar kedua menempatkan tempat yang sesuai.
Ketiga : 5
3
6
8
5
3
6
8
3
5
6
8
3
5
6
8
Bila proses ini dilanjutkan, tidak ada pertukaran tempat lagi bagi bilangan – bilangan tersebut, sebab bilangan tersebut telah selesai disusun.
BAB 2 SENARAI (List) 2.1 Pengertian Senarai (List) List atau senarai adalah sebuah pemikiran / konsep struktur data yang sangat dasar pada pemograman agar lebih fleksibel, di mana setiap elemen akan ditambahkan saat dibutuhkan, tidak dialokasikan dengan tempat tertentu dari awal. List merupakan kumpulan elemen dengan struktur tertentu. Struktur dasar dari list dapat dilihat pada gambar 2 yang merupakan list dengan tiga buah elemen. Kepala (first)
NULL
Gambar 2 Senarai dengan Tigah Buah Elemen Kepala (first)
NULL
Gambar 3 Representasi Lain Senarai dengan Tiga Elemen Sebuah list akan terdiri dari elemen pertama yang disebut dengan kepala atau first, next adalah alamat dari elemen berikutnya. serta beberapa elemen atau bahkan tanpa elemen yang biasa disebut list kosong. Misalkan jika kita ingin membuat sebuah elemen data nilai mahasiswa yang terdiri dari nomor induk, nama, dan nilai maka representasinya dapat dilihat pada gambar 4:
Nim 001
nama
nilai
faiz
A
next
Petunjuk ke elemen berikutnya
Gambar 4 Representasi Elemen
2.2 Tipe-tipe List 2.2.1 List Kosong List kosong hanya terdiri dari sebuah petunjuk elemen yang berisi NULL (kosong). List kosong tidak memiliki satu buah elemen pun sehingga hanya berupa petunjuk awal elemen yang berisi NULL (kosong). Gambar 6 Senarai Kosong Kepala (first)
NULL
Sehingga list kosong merupakan list yang belum memiliki elemen yang terkait pada first. Sehingga ketika first diakses belum ada bendanya. 2.2.2 List Tunggal List tunggal adalah sebuah list yang elemennya hanya menyimpan informasi elemen setelahnya (Next) sehingga jalannya pengaksesan list hanya dapat dilakukan secara maju. List tunggal memiliki beberapa jenis list yaitu list tunggal dengan first dan tail, list tunggal dengan kepala first, dan list tunggal berputar.
Representasi list tunggal dengan kepala dan tail (ekor) memiliki dua buah petunjuk elemen yaitu elemen pertama (first) dan petunjuk elemen terakhir (tail), sehingga pada awal pengaksesan, elemen yang dapat diakses adalah elemen awal dan akhir. Ekor (tail) Kepala (first)
NULL
Gambar 5 senarai tunggal dengan dua petunujuk elemen Deklarasi list tunggal dengan kepala dan ekor :
Type list : < First : elemen, Tail : elemen >
Representasi list tunggal dengan kepala hanya dapat diakses elemen pertamanya saja karena petunjuk hanya berupa petunjuk elemen awal (first). Kepala (first)
NULL
Gambar 6 senarai tunggal dengan kepala
Representasi list tunggal berputar elemen terkhir ditandai dengan elemen setelahnya sama dengan elemen pertama seperti sehingga penelususran list akan berhenti jika petunjuk bantu telah sampai pada elemen yang elemen setelahnya sama dengan elemen yang ditunjuk oleh penunjuk elemen awal (first) yang dalam bahasa algoritmik : While now.text <> L1.first do {proses penelusuran list} Now
now.while
(end while)
Gambar 7 senarai berputar 2.2.3 List ganda List ganda adalah sebuah list yang elemennya menyimpan informasi elemen sebelumnya dan informasi elemen setelahnya sehingga penelusuran list dapat dilakukkan secara maju dan mundur. List ganda terdiri dari list ganda dengan kepala dan tail(ekor) dan list ganda dengan kepala dan list ganda berputar.
Representasi list ganda dengan kepala dan ekor, memiliki dua petunjuk yang dapat diakses (tail). Kepala (first)
Ekor (tail)
NULL NULL
Gambar 8 senarai ganda dengan dua petunjuk
Representasi list ganda dengan kepala, hanya memiliki sebuah petunjuk elemen yaitu penunjuk pada elemen awal list (first). Kepala (first)
NULL NULL
Gambar 9 senarai ganda dengan kepala
Representasi list ganda berputar, elemen terakhir list ganda berputar ditandai dengan elemen setelahnya adalah merupakan elemen pertama list yang ditunjuk awal list (first).Kepala (first)
Gambar 10 senarai ganda berputar 2.3 Operasi pada List Operasi-operasi yang dilakukan pada list adalah penelusuran (traversal),pencarian sebuah elemen (search),penciptaan (create),penambahan elemen (insert) dan penghapusan elemen (delete), menggabung Dua Buah List (concat).
2.3.1 Penelusuran (traversal) Dibutuhkan untuk pemrosesan terhadap data/ informasi yang ada dielemen list, perlu dilakukan penelusaran list, yaitu “mengunjungi” setiap elemen list.
Traversal1 (input L:list) {untuk menelusuri list} {L terdefinisi, mungkin kosong} {elemen list L “dikunjungi” & telah diproses} Addres{address untuk traversal, tipe terdefinisi} Procedure Proses(input P:address) Procedure Insisialisasi {aksi sebelum proses dilakukan} Procedure terminasi {aksi sesudah semua pemrosesan} Algoritma: Inisialisasi(P) P first (L) While (P=Nil) do Proses(P) P Next(P) terminasi Traversal2 (input L:list) {untuk menelusuri list dengan kasus kosong} {L terdefinisi, mungkin kosong} {elemen list L “dikunjungi” & telah diproses} Addres{address untuk traversal, tipe terdefinisi} Procedure Proses(input P:address) Procedure Insisialisasi {aksi sebelum proses dilakukan} Procedure terminasi {aksi sesudah semua pemrosesan} Algoritma: First (L) = Nil then Input („list kosong‟) Inisialisasi First (L) Input Proses (P) P Next (L) While (P=Nil) terminasi Traversal3 (input L:list) {untuk menelusuri list} {L terdefinisi, tidak kosong} {elemen list L “dikunjungi” & telah diproses} Address{address untuk traversal, tipe terdefinisi} Procedure Proses(input P:address) Procedure Insisialisasi {aksi sebelum proses dilakukan} Procedure terminasi {aksi sesudah semua pemrosesan}
Algoritma: Inisialisasi(P) P first (L) Address(P) Next(P)=Nil Next(P) terminasi 2.3.2 Pencarian Elemen List (Search) Search ini sering dipakai untuk mengenali elemen list berdasarkan nilai informasi yang disimpan pada elemen yang dicari.Biasanya dengan alamat yang ditemukan, dilakukan suatu proses terhadap elemen list tersebut. searchNilai (input L:list, X:infoType, output P: address, found: boolean) {Found X terdefinisi} {P adalah alamat elemen dimana X ditemukan Nil jika tidak ditemukan} Found berharga true jika X ditemukan, Found berharga false jika X tidak ditemukan Kamus : Algoritma: Read(X) Search Nilai(L,X,Prec,found) If found then Insertafter(L,Prec,P) P first(L) found false while (P = Nil) and (not found) do if( X = info(p)) then found true else P Next(P) While p = Nil or found) Pencarian suatu elemen beralamat tertentu Search ini sering digunakan untuk memposisikan list pointer pada suatu elemen list. searchAlamat (input L:list, X:infoType, output P: address, found: boolean) {Found P terdefinisi} {Ada elemen list yang beralamat P,
Found berharga true jika tidak Found berharga false} Kamus : Algoritma: {P first(L) found false while (Pt = Nil) and (not found) do if (X = info(p)) then found true else P Next(Pt) While Pt = Nil or found)} 2.3.4 Penciptaan List Penciptaan sebuah list berarti membuat sebuah list yang selanjutnya siap diproses ditambah data. Algoritma penciptaan sebuah list sebagai berikut : CreateList ( output L : List) {Bentuk list L yang kosong artinya first dari harga awal Nil} Kamus : Algoritma: Void createlist (list *L) { *L = Nil; } 2.3.5 Penyisipan sebuah List Penyisipan elemen dapat dilakukan sebagai elemen setelah sebuah elemen dengan alamat P atau elemen terakhir. Insert First Tambah sebuah elemen sebagai elemen pertama list,insert elemen pertama, list kosong : Kepala (first) Null Elemen baru
Insert elemen pertama, list tidak kosong : Kepala (first)
Null
Elemen baru
Gambar 12 InsertFirst
Procedure insertfirst( input/output L : List, p: address) {IS: List L mungkin kosong, P sudah dialokasi, P = Nil, Next (P) = Nil} {FS: P adalah elemen pertama list first} Kamus : Algoritma: Next (P) first(L) First (L) P If First(L) = Nill then Next (P) First(L) Endif First(L) P Insert After Menyisipkan sebuah elemen beralamat P sebagai suksesor dari sebuah elemen list yang beralamat Prec. Kepala (first)
Elemen baru
Null
Elemen baru
Kepala (first)
prec Null
Procedure insertAfter(input/output L : List, input Prec,P: address) {IS: Prec adalah elemen list, prec = Nil, P sudah dialokasi, P=Nil, Next (P) =Nil} {FS: P menjadi suksesor Prec} Kamus : Algoritma: Void InsertAfter (List *L, address P) Next (P) Next (Prec) Next (Prec) P
Insert Last Menyisipkan sebuah elemen beralamat P sebagai elemen terakhir sebuah list.
Elemen baru Kepala(first)
Null
Procedure insertLast(input/output L : List, input P: address) {IS: List L mungkin kosong P sudah dialokasi,P = Nil, Next(P) = Nil} {FS: P adalah elemen terakhir list L} Kamus : Last: address {alamat elemen terakhir} Algoritma: If (first(L) = Nil)then Insertfirst (L,P) Else Last first (L) While (next (Last) = Nil) do Last Next(last) {endwhile, last adalah elemen terakhir} insertAfter (L,last,P)
2.3.6 Penghapusan Sebuah Elemen pada List (Delete) Penghapusan dapat dilakukan apabila elemen list tidak digunakan lagi.
Penghapusan Elemen list di Awal Kepala (first)
Kepala (first)
Null
Procedure DeleteFirst(input/output L : List, Output P: address) {IS: List L tidak kosong P minimal 1 elemen} {FS:Elemen pertama dihapus, P adalah alamat elemen pertama L sebelum penghapusan} Kamus :
Algoritma: P first (L) First (L)
Next(First(L)) Null
Penghapusan Elemen List After/Tengah
Kepala (first)
Kepala (first) Null
Null
Procedure DeleteAfter(input/output L : List, Output P: address) {IS: List L tidak kosong Prec adalah elemen list, Next (prec) = Nil} {FS:Menghapus suksesor Prec, p adalah suksesor Prec sebelum penghapusan, next (Prec) yang baru adalah suksesor dari suksesor Prec sebelum penghapusan} Kamus : Algoritma: P first (L) Next (Prec) Next(Next(Prec)) Next (P) Nil Penghapusan Elemen di Akhir List Kepala (first)
Kepala (first)
Null Null
Procedure DeleteLast(input/output L : List, Output P: address) {IS: List L tidak kosong, minimal ada satu elemen} {FS:Elemen terakhir dihapus, list mungkin jadi kosong, p adalah alamat elemen terakhir list sebelum penghapusan} Kamus : Last, PrecLast: address
Null
Algoritma: Last first (L) PrecLast Nil {pred dari L tidak terdefinisi} {menelusuri List sampai elemen terakhir} While (next (Last) = Nil) do PrecLast Last Last Next (Last) {endwhile, Next (last) = Nil} P Last if (Preclast = Nil) then { list dgn 1 elemen} First (L) Nil Else Next (PrecLast) Nil
Menghapus elemen tertentu dengen alamat P Procedure DeleteP(input/output L : List, Output P: address) {IS: List L tidak kosong, P adalah elem list L} {FS:menghapus P dari list, P mungkin elemen pertama, tengah, atau akhir} Kamus : Prec : address Algoritma: if (P= first (L))then DeleteFirst (L,P) Else Prec First(L) While (next (Prec) = P) do Prec Next (Prec) {endwhile, Next (Prec) = P, hapus P} DeleteAfter (L, Prec, P)
2.3.7 Menggabungkan Dua Buah List (Concat) Jika ada dua buah list dimana list kedua disambungkan ke list pertama maka last (L1) menjadi predesedor First(L2) Procedure concat(input L1, L2 : List, output L3 :List) {IS: L1=L2, L1=L3, dan L2=L3, L1,L2 mungkin kosong} {FS:L3 adalah hasil konkatenasi L1 dgn L2, L2 diletakkan dibelakang L1} Kamus : Last1 : address {elemen terakhir list pertama
Algoritma: CreatList(L3) if (First (L1) = Nil)then first (L3) first(L2) else first (L3) First (L1) last1 First (L1) {menelusuri list sampai elemen terakhir} While (next (Last1) = Nil) do Last1 Next(Last1) {endwhile, Next(last1) = nil) Next (last1) First (L2)
BAB 3 REPRESENTASI FISIK LIST Representasi list adalah sekumpulan elemen bertipe sama yang terdiri dari 2 bagian : dimana Infotype adalah tipe terdefinisi dan Next adalah “alamat” elemen berikutnya. List Representasi fisik adalah implementasi list dalam struktur data yang dapat ditangani oleh pemrosesan bahasa pemograman. Ada 2 cara untuk merepresentasikan list secara fisik yaitu berkait dan kontigu. Representasi berkait dapat diimplementasikan dalam 2 macam struktur fisik yaitu berkait dengan pointer dan berkait dengan tabel. Sedangkan representasi kontigu hanya dapat diimplementasikan dengan struktur yang secara fisik kontigu adalah tabel. 3.1 Representasi List berkait dengan Pointer Cara mengacu : Jika P adalah nama variabel yang bertipe pointer, maka P adalah alamat memori mesin dari elemen data yang ditunjuknya. Elemen data yang ditunjuknya boleh bertipe apa saja.
Contoh : KAMUS: Type Elmt : integer P: pointer to Elmt {maka P akan bertipe integer} Type Mhs : PMhs pointer to Mhs {Maka PMhs akan bertipe Mhs PMhs . NIM akan bertipe integer} Procedure Allocate (output P: Pointer) {Memberikan sebuah elemen yang ditunjuk oleh P} Procedure Deallocate (input P: Pointer) {Mengembalikan alamat P ke sistem} Contoh untuk pengisian sebuah elemen data yang bertipe sebagai berikut : KAMUS: Type Mhs : PMhs pointer to Mhs Algoritmik: Allocate (PMhs) {baru disediakan memori pada saat ini} PMhs . NIM 9911050 PMhs . Nama „Leni‟ PMhs . Nilai 80
Pada saat sebuah elemen dihapus maka memori dapat dikembalikan ke sistem dengan prosedure Deallocate. Jadi Representasi fisik list linier berkait dengan pointer adalah :
KAMUS: Type ElmtList : Type Address: Pointer to ElmtList Type List: address {infoType adalah tipe terdefinisi} {deklarasi untuk variabel kerja} L: List {alamat elemen pertama list} P: Address { alamat untuk traversal}
Maka ntuk mengacu elemen
dengan alamat P adalah: First(L) dituliskan menjadi L Info(P) dituliskan menjadi P
.Info
Next(P) dituliskan menjadi P
.Next
3.2 Representasi List berkait dengan Tabel Representasi berkait dengan tabel alokasi memorinya tidak dinamis. Alokasi tabel sesuai dengan batasan indeksnya. Representasi fisik dengan tabel digunakan jika maksimum elemen datanya dapat diprediksi. Dengan representasi ini kita dapat menelusuri alamat elemen melalui indeks tabel. Representasi fisik list berkaitan dengan tabel adalah: KAMUS: {Tabel memori list, global} Constant IndekxMin: integer = 1 Constant IndekxMax: integer = 100 Constant Nil: integer = 0 Type InfoType : ......{terdefinisi} Type ElmtList : TabElmt: array [IndexMin...IndexMax] of ElmtList Type Address: Address { alamat pertama list siap dipakai} {deklarasi variable kerja} Type List: Address P: address Procedure IniTab {IS: sembarang} {FS: TabElmt{IndexMin..IndexMax] terinisialisasi untuk dipakai sebagai elemn list berkait elemen pertama yang dapat dipakai adalah FistAvail =1} {inisialisasi tabel yang akan dipakai sebagai memori list} Function Memfull boolean {true jika semua elemen tabel sudah dipakai, false jika tidak}
Procedure AllocTab(output P: Address) {IS: FirstAvail mungkin kosong} {FS: Jika FirstAvail ntidak Nil maka P adalah FirstAvail dan FirstAvail yang baru adalah Next(firstavail) Jika firstAvail = Nil, P=Nil, tuliskan pesan {mengambil sebuah elemen siap pakai P} Procedure DeAllocTab (Input P: Address) {IS: FirstAvail mungkin kosong, P tidak Nil) {FS:firstAvail = P} {mengembalikan sebuah elemen P pada FirstAvail}
Jika didefinisi :
P: Address Maka untuk mengacu elemen dengan alamat P adalah: Info(P) dituliskan menjadi: TabElmtp. Info Next(P) dituliskan menjadi: TabElmtp. Next *Untuk Menginisialisasi Tabel Procedure IniTab {IS: sembarang} {FS: TabElmt[IndexMin...IndexMax] terinisialisasi untuk dipakai sebagai elemen list berkait elemen pertama yang dapat dipakai adalah FirstAvail = 1} {inisialisasi tabel yang akan dipakai sebagai memori List} Kamus : i: address Algoritma: I traversal{IndexMin..IndexMax-1} TabElmt1. Next i+1 TabElmtIndexMax . Next Nil FirstAvail IndexMin Fungsi MemFull digunakan mengecek apakah sebuah elemen tabel sudah dipakai Function MemFull Boolean {true jika semua elemen tabel sudah dipakai, false jika tidak} Kamus : Algoritma: (FirstAvail = Nil)
Prosedur Allocate digunakan jika kita akan memesan tempat untuk list Procedure Allocate(output P: Address) {IS: FirstAvail mungkin kosong} {FS: Jika firstAvail tidak Nil maka P adalah FirstAvail dan FirstAvail yang baru adalah Next(FirstAvail) Jika FirstAvail = Nil, tulislah pesan „tidak tersedia lagi elemen siap Pakai‟ {mengambil sebuah elemen siap pakai P} Kamus : Algoritma: If (not memfull) then P FirstAvail FirstAvail TabElmfirstAvail . Next else output („ tidak tersedia lagi elemn siap pakai‟0 P Nil Jika elemen list tersebut tidak diperlukan lagi dan elemen tersebut sudah dihapus dari list maka “tempatnya” dikembalikan lagi ke tabel agar dapat digunakan untuk elemen list lainnya. Untuk Mengembalikan elemen list adalah: Procedure DeAllocTab (input P: Address) {IS: FirstAvail mungkin kosong, P tidak Nil} {FS: FirstAvail = P} {mengembalikan sebuah elemen p pada FirstAvail} Kamus : Algoritma: P FirstAvail TabElmfirstAvail . Next FirstAvail FirstAvail P
Beberapa contoh keadaan tabel untuk elemen list FirstAvail
FirstAvail
FirstList
Keadaan Awal
FirstAvail
Tabel terpakai 2 elemen FirstList 2
L2
1 L1 10
FirstAvail
4
9
L1
5
7
8
L2 2
1
Info
Next
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Info 1 2 3 4 5 6 7 8 9 10
Info
Next
Next
6
3.3 Representasi Fisik List secara Kontigu Dengan representasi fisik kontigu, struktur data yang dapat menyimpan adalah tabel. Karena hanya tabel yang punya struktur Kontigu. Setiap elemen tabel mengandung informasi info. Sedangkan informasi mengenai Next tidak perlu lagi diseimpan secarabeksplisit, karena secara implisit sudah tersirat dalam struktur data yang menjadi tempat penyimpanannya. Elemen terakhirt tidak dikenali dari Next, karena Next tidak disimpan secara eksplisit, satusatunya cara untuk mengetahui elemen terakhir adalah dari alamatnya : P = Nil, dimana N terakhir dengan harus diketahuinya alamat elemen terakhir, maka representasi list L bukan murni seperti diatas, tetapi harus mengandung First(L) dan Last(L). {list direpresentasi pada tabel secara kontigu} KAMUS: Constant IndekxMin: integer = 1 Constant IndekxMax: integer = 100 Constant Nil: integer = 0 Type InfoType : ......{elmtype : terdefinisi} Info : infotype : (tidak perlu mengandung next : karena dapat dikalkulasi) TabElmt: array [IndexMin...IndexMax] of info Type Address: integer[IndexMin...IndexMax,nil] {deklarasi variable kerja} N : address {nama elemen terakhir, karena field NEXT tidak ada secara eksplisit, maka satu-satunya jalan untuk mengenali elemen terakhir adalah dengan @-nya} Type List: Address First : list {deklarasi alamat} P : address {address untuk traversal} {maka first (L)..last(L) adalah indeks effektif elemen tabel anggota list {next (P) tidak terdefinisi utk P=N next (P) P P+1 Info (P) menjadi TabelmtListp.info}
BAB 4 TUMPUKAN (STACK) 4.1 Pengertian Tumpukan (Stack) Tumpukan atau stack adalah salah satu konsep struktur data yang memiliki sistem kerja yang terakhir masuk adalah yang pertama keluar (LIFO = Last In First Out). Elemen atas tumpukan (Top of Stack)
Tumpukan (stack)
Sebuah stack hanya dapat ditambahkan dan dikurangi elemennya hanya dari sebuah sisi. Elemen paling atas dari sisi tersebut disebut elemen atas atau top of stack. Semua operasi pada sebuah stack diawali dari elemen atas ini, misalkan ingin mengambil elemen stack maka dilakukan satu persatu diawali dari elemen atas, dan jika ingin menambah elemen stack maka petunjuk elemen atas diganti menjadi elemen yang ditambahkan pada bagian atas stack. 4.2 Operasi pada Tumbukan 4.2.1 Operasi Push Operasi push pada stack adalah operasi menambahkan elemen baru pada sebuah stack. Elemen baru Top
Top
Elemen baru
Tumpukan (stack)
Procedure Push(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) then Top(S) P else Next (P) Top(S) Top(S) P
Tumpukan (stack)
Procedure Push(input/output S : Stack, input E: Elmts) {IS: Stack S mungkin kosong, E terdefinisi, alokasi} {FS: Top(S) berisi E} Kamus : P : address Algoritma: Alokasi (P) Elmt (P) E If StackEmpty(S) then Top(S) P else Next (P) Top(S) Top(S) P 4.2.2 Operasi POP Operasi pop pada stack adalah operasi mengambil sebuah elemen dari sebuah stack. Top
dikeluarkan
Top
Procedure Pop(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)) Procedure Pop(input/output S : Stack, output E:ElmtS) {IS: Stack S terdefinisi, tidak kosong} {FS: P adalah alamat elemen yang diambil} Kamus : Algoritma: P Top(S); E.Info Info(P); E.Next Top(S) Next( Top(S)) Dealokasi (P)
Nil
4.3 Stack Representasi Statis Stack dengan representasi statis biasanya diimplentasinya dengan menggunakan array. Sebuah array memiliki tempat yang dialokasikan diawal sehingga sebuah elemen yang dimasukan dalam sebuah array terbatas pada tempat yang ada pada array. Karena menggunakan array maka stack dengan representasi statis dapat mengalami kondisi elemen penuh. array
elemen Elemen Elemen Elemen Elemen Elemen
indeks
1 2 3 4 5 6 7 8 9 10
KAMUS UMUM Constant Nmax: integer = 100 Constant Nil: integer = 0 Type Address: integer [0..NMax] {alamat 0 untuk menyatakan stack kosong} Type Elmts:....{terdefinisi, hanya terdiri dari info} Type Stack: S: Stack {cara penulisan ; TOP (S) dituliskan S.Top Info (P) dituliskan S.TsbElmtp.Elmts Next (P) dituliskan P P+1
Function StackEmpty (S: Stack) boolean {mengirimtrue jika stack kosong dan false jika stack kosong}
Kamus : Algoritma: (S.TOP = Nil)
Procedure CreateStack(Output S:Stack) {IS: sembarang} {FS:Stack S tercipta, Top = Nil} Algoritma : S.Top Nil
Procedure Popkon(input/output S : Stack, input E:ElmtS) Procedure Pushkon(input/output S : Stack, {IS: Stack S terdefinisi, mungkin kosong} input E:ElmtS) {FS: jika stack S kosong, maka E= -99 {IS: Stack S dan E terdefinisi} Jikastack S tidak kosong maka Top = {FS: jika masih tersedia tempat maka E Top-1 E adalah elemen yang dipop}} menjadi elemen paling baru dari stack S, jika Kamus : tidak tersedia tempat lagi tampilkan pesan Algoritma: „overflow‟} If (StackEmpty(S)) then Kamus : Output(E=-99) Algoritma: Else If (S.Top < Nmax) then E S.TabElmts.Top S.Top S.Top + 1 S.Top S.Top – 1 S.tabelmtss.top E Else Output(„overflow‟) 4.4 Stack Representasi Dinamis Stack dengan representasi dinamis biasanya diimplementasikan dengan menggunakan pointer yang menunjukkan pada elemen-elemen yang dialokasikan pada memori. Kepala (first)
NULL
Gambar Representasi Tumpukkan dinamis Karena semua operasi pada sebuah stack diawali dengan elemen yang paling atas maka jika menggunakan representasi dinamis saat elemen ditambah akan menggunakan penambahan elemen pada awal stack (addfirst) dan saat pengambilan atau penghapusan elemen menggunakan penghapusan diawal stack (delfirst).
KAMUS UMUM Type infotype :...{type terdefinisi, menyimpan informasi elemen stack} Type Address: pointer to ElmtStack Type ElmtStack: S: Stack {cara penulisan : Top (S) dituliskan S.Top Info (P) dituliskan P . Info Next (P) dituliskan P . Next Primitif Alokasi : Allocate (P) Dealokasi : Dealocate (P)} Function StackEmpty (S: Stack) boolean {mengirimtrue jika stack kosong dan false jika stack kosong} Kamus : Algoritma: (S.TOP = Nil)
Procedure CreateStack(Output S:Stack) {IS: sembarang} {FS:Stack S tercipta, Top = Nil} Kamus : Algoritma: S.TOP Nil
Procedure Popkon(input/output S : Stack, input P: Address) {IS: Stack S terdefinisi, mungkin kosong} Procedure PushP (input/output S : Stack, {FS: jika stack kosong, tulis pesan “stack input P: Address) {IS: Stack S terdefinisi, mungkin kosong, P = kosong” Jika Stack tidak kosong P adalah alamat Nil} Top sebelum Pop, Stack mungkin menjadi {FS: jika masih tersedia tempat maka E menjadi elemen paling baru dari stack S, jika kosong}} Kamus : tidak tersedia tempat lagi tampilkan pesan Algoritma: „overflow‟} P S.Top Kamus : If not StackEmpy (S) then Algoritma: S.Top S.Top . Next If Not stackEmpty (S) then P
.Next
Latihan Soal x
3
y
5
createstack (s)
S.Top
push (s,x) push (s,4) pop (s,z) push (s,y) push (s,3) push (s,z) pop (s,x) push(s,2) push(s,x) while not EmptyStack (s) do pop (s,x) output(x) {endwhile}
y
1
createStack (S) push (S,5) pop (S,X Z
X+Y
Pop (S,X) Push (S,3) Push(S,Z) Pop (S,X) Push(S,2) Push(S,X) while not EmptyStack (s) do
pop (s,x) output(x) {endwhile}
ANTRIAN (QUEUE) 4.1 Pengertian Antrian Antrian atau queue adalah salah satu konsep struktur data yang memiliki sistem kerja pertama masuk maka akan menjadi yang pertama keluar (FIFO = First In First Out) Last
First
masuk
keluaran
Antrian (Queue)
Gambar representasi Antrian Pada sebuah antrian elemen hanya dapat ditambahkan melalui sisi belakang queue dan elemen hanya dapat diambil dari sisi bagian depan queue. Oleh karena itu, ada dua penunjuk elemen pada sebuah queue yaitu belakang atau last sebagai penunjuk elemen paling belakang dan depan atau first sebagai penunjuk elemen bagian depan. Kondisi antrian yang menjadi perhatian adalah: 1. Penuh Bila elemen pada antrian mencapai kapasitas maksimum antrian. Pada kondisi ini tidak mungkin dilakukan penambahan keantrian. Penambahan elemen menyebabkan kondisi kesalahan overflow. 2. Kosong Bila tak ada elemen pada antrian. Pada kondisi ini tidak mungkin dilakukan pengambilan elemen dari antrian. Pengambilan elemen menyebabkan kondisi kesalahan underflow. 4.5 Operasi pada Antrian Operasi yang dapat dilakukan pada antrian atau queue adalah memasukkan elemen dari sisi bagian belakang queue dan mengeluarkan elemen dari sisi depan queue. Last
First
masuk
Last
First
keluaran
Antrian (Queue)
Antrian (Queue)
Aturan Memasukkan Queue Last
First
Last
First
keluaran
Antrian (Queue) Antrian (Queue)
Antrian (queue) adalah list linier yang: 1. 2. 3. 4.
Dikenali elemen pertama (Head) dan terakhirnya (Tail) Penyisipan elemen selalu dilakukan setelah elemen terakhir Penghapusan elemen selalu dilakukan pada elemen pertama Elemen yang satu dengan yang lain diakses melalui Next.
Contoh: Antrian tersebut berisi 6 elemen yaitu A,B,C,D,E dan F. Elemen A terletak dibagian depan antrian, elemen F terletak dibelakang antrian. Depan/Front
A
B
C
D
E
F Belakang/Tail
Memasukkan elemen G maka penambahan elemen dilakukan dibelakang Depan/Front
A
B
C
D
E
F
G Belakang/Tail
Jika ada elemen yang dihapus maka elemen A akan dihapus terlebih dahulu Depan/Front
A
B
C
D
E
F
G
Belakang/Tail
Function QEmpty (Q: Queue) boolean {mengirim true jika antrian kosong dan false jika antrian kosong} Kamus : Algoritma: (Q.Head = Nil) and (Q.Tail = Nil) Procedure CreateStack(Output Q:queue) {IS: sembarang} {FS:terbentuk sebuah queue yang kosong} Kamus : Algoritma: Q.Head Nil Q.Tail Nil rocedure 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}
Kamus : Algoritma:
Memeriksa antrian kosong
Pembuatan queue kosong
Penambahan sebuah elemen pada antrian
If QEmpty (Q) then Head (Q) P Else Next (tail (Q)) P Tail (Q) P Procedure DeleteQ (input/output Q : Queue, output P: Address) {IS: Q terdefinisi, tidak kosong } {FS: P adalah alamat yang diambil, P = Nil, Next (P) = Nil, antrian mungkin jadi kosong} Kamus : Algoritma: P Head (Q) Head (Q) Next (Head(Q)) If Head (Q) = Nil then Tail (Q) Nil Else Next (P) nil
Penghapusan sebuah elemen pada antrian
Representasi Statis Queue dengan representasi statis biasanya diimplementasikannya dengan menggunakan array. Sebuah array memiliki tempat yang dialokasikan diawal sehingga sebuah elemen yang dimasukkan dalam sebuah array terbatas pada tempat yang ada pada array. Karena menggunakan array maka queue dengan representasi statis dapat mengalami kondisi elemen penuh. 8 7 6
5 4 3 2 1 first/Front
Last/belakang
Karena menggunakan array yang tidak dapat diubah strukturnya secara dinamis maka operasi mengeluarkan elemen dari queue dengan representasi statis perlu penanganan secara khusus
yaitu menggeser semua elemen kedepan begitu ada elemen yang dikeluarkan dari queue, agar lebih jelas. 8 7 6
5 4 3 2
Last/belakang
8 7 6
first/Front
5 4 3 2 1
first/Front
Last/belakang
Procedure InsertQ (input/output Q : Queue, input ElmtQ: infotype) {IS: Q mungkin kosong, ElmtQ terdefinisi} FS: elemen Tail dari Q bernilai ElmtQ } {menyisipkan sebuah elemen ElmtQ sebagai Tail} Kamus : Algoritma: If QEmpty (Q) then Qtail 1 QHead 1 QTabElmtQQtail elmtQ Else If (Qtail < Nmax) then Qtail Qtail + 1 QTabElmtQQtail elmtQ Else Output („overflow‟) Head Head 50 75 100 150 1
2
3
4
5 Tail
Nmax = 5 Head = 1 Tail = 4 Head
50
Tail
75
100
150
25
Nmax = 5, Inset (Q,25)
1
2
3
4
5
Head = 1
Tail = 5 X=25 Procedure DeleteQ (input/output Q : Queue, input ElmtQ: infotype) {IS: Q tidak kosong FS: elemen yang dihapus disimpan informasinya pada ElmtQ, ElmtQ digeser} {menyisipkan sebuah elemen ElmtQ sebagai Tail} Kamus : Algoritma: QEmpty Q.TabElmtQQ.Head If (Qtail = Qhead) then (ada lebih dari satu elemen, geser semua elemen sisa) I traversal [2..Qtail] QtabElmtQ1-1 QtabElmtQ1 Qtail Qtail -1 Else QTail Nol Q.Head Nol
Head
50
75
100
150
200
1
2
3
4
5
Tail
Head =1 Tail = 5 x = 200
Head
75
100
150
200
1
2
3
4
Delete Q(Q,x)
5 Tail
Head = 2 Tail = 4 x=50
Procedure InsertQ (input/output Q : Queue, input ElmtQ: infotype) {IS: Q mungkin kosong, ElmtQ terdefinisi} FS: elemen Tail dari Q bernilai ElmtQ } {menyisipkan sebuah elemen ElmtQ sebagai Tail} Kamus : Algoritma: If QEmpty (Q) then Qtail 1 QHead 1 QTabElmtQQtail elmtQ Else If (Qtail < Nmax) then Qtail Qtail + 1 QTabElmtQQtail elmtQ Else If (Qhead > 1) then For ( i Qhead to Qtail do) QTabElmtQ[i-Qhead + 1] QtabElmtQ[i] End for Qtail Qtail – Qhead+1` Qhead 1
Qtail Qtail +1 QtabElmtQ[Qtail] Else Write (overflow) Endif
ElmtQ
Head = 3; tail =5 Nmax =5 Head
5
10
15
20
25
1
2
3
4
5
Tail
Inser (Q,100) Head
15
20
25
100
1
2
3
4
Head = 1
5 Tail
Tail = 4 Overflow? Tdk
Procedure InsertQ (input/output Q : Queue, input ElmtQ: infotype) {IS: Q mungkin kosong, ElmtQ terdefinisi} FS: elemen Tail dari Q bernilai ElmtQ } {menyisipkan sebuah elemen ElmtQ sebagai
Tail} Kamus : NewTail : Address Algoritma: If Qcount = Nmax then Output („overflow‟) Else Newtail Qhead + Qcount If Newtail > Nmax then Newtail Newtail – Nmax QTabElmtQQtail elmtQ Qcount Qcount + 1
Z
Count = 2 Newtail Head = 7 X Head
Y
Z
Count = 3 Head = 7, Tail
Tail =1
Head
x
Y
Z
Head = 5,Tail = 1 Count = 5 Elmt =‟A‟, Nmax = 8 P
Q 1
R 2
S 3
T
U
V
W
4
5
6
7
T
U
V
W
4
5
6
7
8
Insert (Q,Elmt) Head = 5, Tail = 2 Count = 6 P
A 1
2
3
8
Procedure DeleteQ (input/output Q : Queue, input ElmtQ: infotype) {IS: Q tidak kosong} FS: element yang dihapus disimpaninformasinyapada elmtQ {elemen Q berkurang satu} Kamus : Algoritma: ElmtQ QTabElmtQQhead Qcount Qcount -1 if Qempty(Q) or Head = Nmax then Qhead 1 else QHead Qhead + 1
Head = 5, Tail = 2 Count = 6 P
A 1
2
3
T
U
V
W
4
5
6
7
U
V
W
P
4
5
6
7
8
Delete(Q, T) Head = 5, Tail = 1 Count = 5 A 1
2
3
8
Representasi Dinamis Queue dengan representasi Dinamis biasanya diimplementasikan dengan menggunkan pointer yang menunjuk pada elemen-elemen yang dialokasikan pada memori.
head
Tail
Karena semua operasi penambahan elemen pada sebuah queue ditambahkan pada akhir queue maka jika menggnakan representasi dinamis saat elemen ditambahkan akan menggunakan penambahan elemen pada akhir queue(addlast) dan saat pengambilan atau penghapusan elemen menggunakan penghapusan diawal queue (delfirst). Procedure insetQP (input/output Q : Queue, input P: Address) {IS: Q terdefinisi, mungkin kosong, P terdefinisi next(P) = nil} {FS:tail yang baru adalah P} Kamus : Algoritma: If EmptyQ(Q) then
Qhead Qtail else Qtail Qtail
. Next P
P P P
Procedure DeleteQP (input/output Q : Queue, input P: Address) {IS: Q tidak kosong {FS:P adalah elemen yang dihapus, Q mungkin kosong} Kamus : Algoritma: P Qhead QHead Qhead .Next P . Next Nil If (Qhead = Nil) then QTail = Nil Prioritas (Priority Qeue)
Antrian dengan
Antrian berprioritas ataun priority queue mengeluarkan elemen dari queue berdasarkan prioritas pada elemen itu, oleh karena itu elemen pada antrian berprioritas untuk menyimpan nilai prioritas pada setiap elemn. Untuk memasukkan elemen pada sebuah antrian erprioritas tidak harus melalui sisi belakang antrian disisipkan dan diurutkan berdasarkan prioritas elemen, sedangkan mengeluarkan elemne dari antrian berdasarkan prioritas elemen. Hal yang perlu diperhatikan saat memasukkan elen ke antrian berprioritas adalah sebagai berikut : 1. Elemen yang memiliki prioritas leih tinggi akan leih dahulu keluar dari queue 2. Jika ada dua elemen yang memiliki prioritas sama maka yang akan keluar terlebih dahulu dari antrian adalah yang terlebih dahulu masuk kedalam antrian.
Operasi memasukkan elemen pada antrian berprioritas adalah sebagai berikut: Elemen baru
3
head
1
2
4
6
9
12 Tail 3 Tail
head
1
2
4
6
9
12
Hasil : 1
2 head
3
4
6
9
12 Tail
Procedure InsertPrioQ (input/output PrioQ : Queue, input P : address) {IS: Q terdefinisi, tidak kosong, Pterdefinisi} p FS: P menjadi elemen antrian sesuai dengan Prio(P) } {P disiisipkan dalam antrian sesuai dengan prioritasnyal} Kamus : Pt, Prec : Address Found : Boolean
Algoritma: If Qempty(Q) then Qhead P Qtail P Else Found false Prec Nil Pt head(Q) While ( Pt = Nil) and (not found) do If Prio(Pt) > Prio (P) then Found True Else Prec Pt Pt Next(Pt) {Endwhile, Pt = Nil or found} If prec = nil then {sisip dielemen ke 1} Next (P) Pt head(Q) P else if found then {sisip ditengah} Next(P) Pt Next (tail(Q)) P Else{sisip dielemen ke 1} Next(Tail(Q)) P Tail(Q) P
Tugas
3. Insert(Q,H)
1. Bagaimana keluaran dari potongan berikut: InitQ(Q) InsertQ(Q,5) 5 InsertQ(Q,6) InsertQ(Q,7) InsertQ(Q,8) DeleteQ(Q,X) DeleteQ(Q,Y) InsertQ(Q,X) InsertQ(Q,5) InsertQ(Q,Y+1) DeleteQ(Q,X) InsertQ(Q,Y) While no emptyQ(Q) do Delete(Q, X) Output (X) {endwhile} 2. a. Head = 1, Tail = 4
A
A
B
C
D
D
G
1
M
2
K
algoritma
3
head = 3.,tail = 2.,Count =........
4. Delete(Q, ElmtQ) dari data diatas
E
Setelah operasi InsertQ (Q,‟F‟) maka keadaan anrian menjadi
4
Head = .., Tail = ... Overflow? b.Head = 5, Tail = 3 A
B
C
D
E
Setelah operasi Delete (Q,‟ElmtQ‟) maka keadaan anrian menjadi Head = ...., Tail = ....., elmt=...., overflow?
Head = 3, Tail = 3 A
B
C
D
E
Setelah operasi InsertQ (Q,‟F‟) maka keadaan anrian menjadi Head = .., Tail = ... Overflow?
1. Bagaimana keluaran dari potongan algoritma berikut: InitQ(Q) X 5 Y 7 InsertQ(Q,X) InsertQ(Q,8) InsertQ(Q,y) DeleteQ(Q,z) InsertQ(Q,2)
InsertQ(Q,z) InsertQ(Q,6) If Z = 0 then While not emptyQ9Q) do DeleteQ(Q, X) Output (X) {endwhile} Else Output(„selesai‟) 2. a. Nmax=5, Head = 1, Tail = 4 10
20
30
40
50
Setelah operasi InsertQ (Q,‟60‟) maka keadaan anrian menjadi Head = .., Tail = .., X=... Overflow? b. Nmax=5, Head = 1, Tail = 4 10
20
30
40
50
Setelah operasi DeleteQ (Q,‟elmtQ‟) maka keadaan anrian menjadi Head = .., Tail = ..., ElmtQ=.... Overflow?
3. a. Nmax=5, Head = 5, Tail = 4 30
50
70
90
100
Setelah operasi InsertQ (Q,‟200‟) maka keadaan anrian menjadi Head = .., Tail = ..., X=....,Overflow?
b. Nmax=5, Head =5, Tail = 3
30
50
70
90
100
Setelah operasi DeleteQ (Q,‟elmtQ‟) maka keadaan anrian menjadi Head = .., Tail = ...,ElmtQ=......,Overflow?
4. a. Head = 1, Tail = 4 10
20
30
40
50
Setelah operasi InsertQ (Q,‟60‟) maka keadaan anrian menjadi Head = .., Tail = .....,X=......,count=....., Overflow?
b. Head = 1, Tail = 3 10
20
30
40
50
Setelah operasi DeleteQ (Q,‟elmtQ‟) maka keadaan anrian menjadi Head = .., Tail = .., elmtQ=......,count=........, Overflow?
5. a. Head = 3, Tail = 5 30
50
70
90
100
Setelah operasi InsertQ (Q,‟200‟) maka keadaan anrian menjadi Head = .., Tail = ..., X=......, count=......,Overflow?
b. Head = 2, Tail =5 30
50
70
90
100
Setelah operasi DeleteQ (Q,‟elmtQ‟) maka keadaan anrian menjadi Head = .., Tail = ..., elmtQ=...., count=....,Overflow?
6. a. Head = 1, Tail = 4 10
30
60
70
90
Setelah operasi InsertQ (Q,‟40‟) maka keadaan anrian menjadi Head = .., Tail = ..,X=...
b. Head = 1, Tail = 5 10
30
60
70
90
Setelah operasi DeleteQ (Q,‟60‟) maka keadaan anrian menjadi Head = .., Tail = ...,X=.....
POHON (TREE) 5.1 Pengertian Pohon Pohon atau tree adalah salah satu bentuk konsep struktur data yang terdiri dari akar dan simpul-simpul yang berada dibawah akar. Misalnya pohon sisilah keluarga, struktur organisasi,dll. Pada gambar dibawah sebuah KOTAK dianggap sebagai SIMPUL (node atau vetex) sedangkan simpul yang paling atas yang berisi “Ketua Umum” dianggap sebagai AKAR (root). Bagian simpul “Wakil Ketua 1” kebawah disebut sebagai SUBPOHON (subtree) begitu juga dengan simpul “Wakil ketua 2” kebawah.
1
Ketua Umum A
2 Wakil Ketua 1 B Kepala Devisi Keuangan D
Wakil ketua 2 C
Kepala Divisi kekeluargaan E
Kepala Divisi Produksi F
3 Kepala Divisi pemasaran G
4 Bendahara 2 h
Bendahara 1 i
Staf Administrasi j
Pengembang K
Staf Pemasaran L
Anak(child) dan Orang tua (parent) Jika X adalah Simpul, maka akar tiap-tiap subpohon dari X disebut anak, dan X adalah orang tua setiap akar subpohon. Pada gambar diatas, B dan C adalah anak dari A, dan A adalah orang tua dari anak-anaknya itu. Begitu juga F,G adalah anak dari C, dan C adalah orang tua dari F,G Derajad (degree) Derajad adalah jumlah subpohon pada setiap simpul/ banyaknya tingkat simpul turunan dari suatu simpul tertentu, Misal : “Ketua Umum(A) memiliki derajad 2, Kepala Divisi kekeluargaan(E) memiliki derajad 1, dsb. Daun (Leaf) Simpul yang mempunyai derajat nol disebut daun. H,i,j,k,l adalah daun dari pohon pada gambar 1. Daun sering dinamakan simpul terminal atau yang tidak mempunyai subpohon. Dalam struktur pohon juga dukenal istilah kedalaman (depth). Simpul bukan terminal disebut simpul dalam (internal nodes). Lintasan (path) Lintasan dari simpul n1 ke simpul simpul nk adalah runtunan simpul n1, n2,..,nk sedemikian sehingga n1 adalah orang tua dari n(i+1) untuk 1>/ < k. Pohon pada gambar 1, lintasan dari A ke J adalah A,B,E,J. Lintasan dari B ke i adalah A,B,D,I. Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan. Panjang lintasan dari A ke i adalah 3, Panjang lintasan dari C ke K adalah 2.
A
B
E
C
F
G
D
H
I
MENGGUNAKAN NOTASI KURUNG : (A ( B ( E, F ), C ( G ), D ( H, I ) )
5.2 POHON BINER Pohon Biner atau binary tree adlah pohon yang setiap simpulnya memiliki simpul turunan atau sub pohon maksimal dua yang disebut sebagai pohon kiri (left subtree) dan subpohon kanan (right subtree). Jenis-jenis pohon iner sebagai berikut: Pohon biner lengkap (complete binary tree) yaitu pohon biner yang setiap simpulnya mempunyai dua buah simpul turunan.
A
B
E
Pohon biner condong kekiri (Left skewed binary tree)
B
C
E
F
D
I
H
G
A
Pohon biner condong kanan (right skewed binary tree) D
i
A
Pohon biner sembarang
B
E
C
F
G
Contoh pohon dan representasinya dengan larik 30
14
21
70
8
15
12
10
11
27
Representasi dengan larik 1 2 3 4 5 6
info 30 14 70 21 8 12
kiri 2 4 6 8 0 0
kanan 3 5 7 0 0 0
7 8 9 10
15 10 11 27
9 0 0 0
10 0 0 0
5.2.1 Operasi pada Pohon Biner Operasi yang dapat dilakukan pada pohon biner antara lain kunjungan terhadap simpulsimpulnya. Jenis-jenis knjungan pada pohon biner antara lain preorder, inorder, postorder, dan levelorder. Kunjungan dengan orientasi LRO(Left to Riight Oriented) dimana kunjungan selalu dimulai dari supohon kiri baru kemudian supohon kanan. Juga ada RLO (Right to Left Oriented) dimana kunjungan selalu dimulai dari subpohon kanan baru kemudian kesubpohon kiri. PreOrder Kunjungan preorder merupakan kunjungan pada pohon biner yang dimulai dari akar kemudian kesubpohon kiri dikunjungi baru kesubpohon kanan dikunjungi. Maka : A – B – D – E – C – F – G - H
A
B
D
C
E
G
F
H
Maka dengan kunjungan preorder akan menghasilkan urutan simpul yang dikunjungi A – B – D – E – C – F – G – H. InOrder
Kunjungan inorder merupakan kunjungan pada pohon biner yang dimulai dari simpul-simpul turunan subpohon kiri, akar, baru kemudian simpul-simpul turunan pada supohon kanan, misalnya pada contoh diatas maka kunjungan inorder menghasilkan simpul yang dikunjungi D – B – E – A – F – C –H – G. PostOrder Kunjungan postorder merupakan kunjungan pada pohon biner yang dimulai dari simpulsimpul turunan subpohon kiri, baru kemudian simpul-simpul turunan pada subpohon kanan, kemudian akar, Misalnya pada contoh diatas maka dengan kunjungan postordermenghasilkan urutan simpul yang dikunjungi D – E – B –F – H – G – C –A.
Menyalin dan Membandingkan Pohon Biner Menyalin pohon biner ke pohon biner lainnya dapat dilakukan dengan menggunakan salah satu operasi kunjungan sambil membuat simpul baru yang sama dengan simpul yang disalin sebagai simpul pohon biner hasil dari penyalinan pohon biner yang disalin. Egitu juga dengan membandingkan dua buah pohon biner, jika semua simpul yang dikunjungi sama maka dapat dikatakan bahwa dua buah pohon biner merupakan pohon biner yang sama. Contoh;
*
PreOrder : * + a / b c – d *e f
(prefix) +
-
InOrder (infix) a
*
d
/
:a + b / c * d – e * f
Postorder : a b c / + d e f * - * (postfix) b
C
f
e
Procedure PreOrder (input T : pohon_biner) {mengunjungi simpul pohon secara preorder IS: T mungkin kosong} {FS:semua simpul T sudah dikunjungi secara preorder} Kamus :
Algoritma: If T = then Proses (Info(T)) PreOrder(kiri(T)) PreOrder(kanan(T))
Procedure InOrder (input T : pohon_biner) {mengunjungi simpul pohon secara InOrder IS: T mungkin kosong} {FS:semua simpul T sudah dikunjungi secara InOrder} Kamus : Algoritma: If T = then InOrder (Kiri(T)) Proses (Info(T)) InOrder(kanan(T)) Procedure PostOrder (input T : pohon_biner) {mengunjungi simpul pohon secara postOrder IS: T mungkin kosong} {FS:semua simpul T sudah dikunjungi secara postOrder} Kamus : Algoritma: If T = then PostOrder(kiri(T)) PostOrder(kanan(T)) Proses (Info(T)) Procedure cariX (input T : pohon_biner, x: infotype output ketemu : boolean) {mengunjungi apakah X terdapat didalam pohon} IS: T mungkin kosong, x adalah info yang dicari} {FS:ketemu=true jika X ditemukan, false jika tdk} Kamus : Algoritma: If T = then Ketemu false else if info(T) = X then ketemu true
Mencari apakah X terdapat didalam pohon T
else CariX(kiri(T), X, ketemu) CariX(kanan(T), X, ketemu)
Pohon n-er Pengertian pohon n-er Pohon n-er adalah struktur pohon yang memiliki simpul turunan lebih dari dua.
A
B
C
E
F
D
I
H
G
K
L
M
Pada sebuah pohon n-er juga dapat dilakukan kunjungan pada simpul-simpulnya seperti halnya pada pohon biner, misalkan jika pohon pada gambar diatas dikunjungi secara preorder akan menghasilkan urutan simpul A – B – E – F – C – G – D – H – I – J – K – L M. Jika dilakukan kunjungan secara post order akan menghasilkan urutan simpul E – F – B – G – C – H – I - K – L – M – J – D – A. CONTOH ; a*b – 3^x
-
*
a
^
b
3
X
GRAF(GRAFH) GRAF(GRAFH) adalah sebuah konsep struktur data yang terdiri dari kumpulan simpul (node) dan garis (arc). Sebuah garis harus diawali dan diakhiri dengan sebuah simpul. Misalnya garis a dinyatakan dengan a={A, B) diartikan bahwa garis a diawali dengan simpul A dan diakhiri dengan simpul B sedangkan simpul yang terhubung dengan sebuah garis e disebut dengan simpul tetanggga sehingga dapat dikatakan simpul A bertetangga dengan B E i simpul B.a b g
A
G D h d
c
F
C
f
Pada sebuah Graf juga terdapat istilah yang disebut jalur (path) dimana jalur adalah kumpulan garis dan simpul yang berawal dari suatu simpul menuju simpul tertentu, misal P adalah sebuah jalur dari simpul A ke simpul G maka dapat dinyatakan bahwa P={A,B,E,G}. Sebah jalur yang memiliki simpul akhir sama dengan simpul awal disebut dengan jalur tetutup (closed path) sedangkan jalur yang terbentuk dari simpul-simpul yang berbeda disebut dengan jalur sederhanan (simple path) seperti halnya jalur dari simpul A ke simpul G. Sebuah graf dikatakan sebagai graf lengkap (complete graph) jika dari semua simpul yang ada dapat dibuat sebuah garis ke semua simpul yang lain. B e
a d
D
A c b
f
C
Sebuah graf disebut graf terhubung (connected graph) jika semua simpul yang ada terhubung dengan minimal satu simpul lain seperti pada gambar diatas tidak ada sebuah simpul yang berdiri sendiri. Sebuah graf pada garisnya memiliki arah disebut dengan graf berarah (directed graph) seperti gambar. Dimana pada graf berarah sebuah garis atau jalur harus ditulis sesuai dengan f arah yang ada pada graf. B
a
E d
c
g
A
i
D e
b
F
h
C
Implementasi Graf Representasi statis Sebuah graf dapat diimplementasikan dengan representasi statis dengan menggunakan array. Ada beberapa cara mengimplementasikan sebuah graf dengan menggunakan sebuah array: a. Matrik tetangga Matrik tetangga merupakan salah satu cara untuk merepresentasikan graf berarah dengan menggunakan array. Dimana angka 1 (satu) menyatakan bahwa simpul awal tidak mempunyai jalur ke simpul tujuan. Simpul-simpul yang memiliki jalur adalah sebagai berikut: A B C D E F
SIMPUL AWAL
A
0
1
O
O
O
0
B
0
0
0
1
1
0
C D
1 1
0 0
0 1
0 0
0 0
0 0
E
0
0
0
1
0
1
F
0
0
0
1
0
0
SIMPUL TUJUAN
Simpul A memiliki jalur dan bertetangga dengan simpul B Simpul B memiliki jalur dan bertetangga dengan simpul D dan E Simpul C memiliki jalur dan bertetangga dengan simpul A Simpul D memiliki jalur dan bertetangga dengan simpul A dan C Simpul E memiliki jalur dan bertetangga dengan simpul D dan F Simpul F memiliki jalur dan bertetangga dengan simpul D
Implementasi dengan bahasa algoritmik : Matgraph : array [1..6, 1..6] of integer
(0, (0, (1, (1, (0, (0,
1, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 1, 1,
0, 1, 0, 0, 0, 0,
0), 0), 0), 0), 1), 0) f
E
B
a
d c
g
A
i
D e
b
h
F
C
Matrik Jalur Matrik jalur merupakan salah satu cara untuuk merepresentasikan graf berarah dengan menggunakan array. Dimana angka 1 (satu) menyatakan bahwa simpul awal tidak memiliki jalur ke simpul tujuan, dan angka 0 (nol) menyatakan bahwa simpul awal tidak memiliki jalur ke simpul tujuan. Bedanya dengan matrik tetangga, angka 1 menyatakan jika simpul
awal bertetangga secara langsung dengan simpul tujuan, sedangkan matrik jalur, simpul awal tidak harus bertetangga secara langsung dengan simpul tujuan, asalkan ada jalur yang dari simpul awal ke simpul tujuan melewati simpul manapun maka dianggap bernilai 1. A
B
C
D
E
F
A
1
1
1
1
1
1
B
1
1
1
1
1
1
C D
1 1
1 1
1 1
1 1
1 1
1 1
E
1
1
1
1
1
1
F
1
1
1
1
1
1
Dari representasi diatas bahwa semua simpul dapat ditempuh dari simpul manapun. Implementasi dengan ahasa algoritmik: array [1..6, 1..6] of integer matgraph ={
(1, (1, (1, (1, (1, (1,
1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1,
1), 1), 1), 1), 1), 1)
3. Matrik Beban Matrik beban merupakan salah satu cara untuk merepresentasikan graf berrarah yang memiliki beban dengan menggunakan array. Matrik beban biasa digunakan untuk merepresentasikan graf berarah yang pada jalurnya terdapat nilai atau eban tempuh. Graf berarah yang memiliki beban biasanya digunakan untuk menggambarkan letakletak kota-kota besarta jarak tempuhnya. Representasi graf dengan menggunakan matrik beban: Dimana angka bukan nol menyatakan bahwa simpul awal memiliki jalur ke simpul tujuan dengan beban yang dituliskan pada matrik, dan angka 0 (nol) menyatakan bahwa simpul awal tidak memiliki jalur ke simpul tujuan. Pada dasarnya matrik beban sama dengan matrik tetangga hanya berbeda penanda adanya jalur, angka 1 (satu) pada matrik tetangga dan nilai beban pada matrik beban.
7
B
3
E 3
8
4
A
4
D 3
3
C
A
B
C
D
E
F
A
0
3
O
O
O
0
B
0
0
0
3
7
0
C D
3 8
0 0
0 3
0 0
0 0
0 0
E
0
0
0
4
0
4
F
0
0
0
2
0
0
MATRIK BEBAN Matgraph : array [1..6, 1..6] of integer Matgraf = {
(0, (0, (3, (8, (0, (0,
3, 0, 0, 0, 0, 0,
0, 0, 0, 3, 0, 0,
0, 3, 0, 0, 4, 2,
0, 7, 0, 0, 0, 0,
0), 0), 0), 0), 4), 0)
CONTOH SOAL Buatlah graf yang memggunakan matrik tetangga:
2
F
SIMPUL AWAL
A
B
C
D
E
F
A
0
1
O
O
O
0
B
0
0
0
1
1
0
C D
1 1
0 0
0 1
0 0
0 0
0 0
E
0
0
0
1
0
1
F
0
0
0
1
0
0
SIMPUL TUJUAN
