MODUL PRAKTIKUM “STRUKTUR DATA”
LABORATORIUM KOMPUTER FAKULTAS ILMU KOMPUTER UNIVERSITAS SRIWIJAYA 2011
Universitas Sriwijaya Fakultas Ilmu Komputer Laboratorium
No. Dokumen Revisi
LEMBAR PENGESAHAN MODUL PRAKTIKUM
……. 0
SISTEM MANAJEMEN MUTU ISO 9001:2008
Tanggal Halaman
4 JUNI 2011 2 DARI 49
MODUL PRAKTIKUM Mata Kuliah Praktikum Kode Mata Kuliah Praktikum SKS Program Studi Semester
: Struktur data : FIK28211 :1 : Sistem Informasi : 3 (Ganjil)
DIBUAT OLEH
DISAHKAN OLEH
DIKETAHUI OLEH
TIM LABORAN LABORATORIUM FASILKOM UNSRI
TIM DOSEN SISTEM INFORMASI FASILKOM UNSRI
KEPALA LABORATORIUM
2/49
Daftar Isi Halaman Depan..........................................................................................................
1
Halaman Pengesahan .................................................................................................
2
Daftar Isi ....................................................................................................................
3
Lembar Kerja Praktikum 1 : Pengenalan Algoritma dan Pemrograman ...................
4
Lembar Kerja Praktikum 2 : Record dan Array.........................................................
11
Lembar Kerja Praktikum 3 : Stack.............................................................................
17
Lembar Kerja Praktikum 4 : Stack Lanjutan .............................................................
21
Lembar Kerja Praktikum 6 : Queue ...........................................................................
23
Lembar Kerja Praktikum 7 : Queue Lanjutan............................................................
27
Lembar Kerja Praktikum 8 : List (Bagian 1) .............................................................
32
Lembar Kerja Praktikum 9: List (Bagian 2) ..............................................................
39
Lembar Kerja Praktikum 11 : Multi List ..................................................................
42
Lembar Kerja Praktikum 12 : Binary Search Tree ....................................................
44
Referensi ....................................................................................................................
49
3/49
Lembar Kerja Praktikum 1 : Pengenalan I.
Tujuan
Setelah 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.
II.
Dasar Teori
Pengenalan 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 :
4/49
1. Buka Turbo C++ 4.5 dari menu program sehingga akan keluar jendela Turbo C++ berikut :
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.
5/49
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 langkahlangkahnya 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.
6/49
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 void main() { // Batang Tubuh Program Utama }
Prepocessor Directive Adalah salah satu pengarah prepocessor directive yang tersedia pada C++. Preprocessor selalu dijalankan terlebih dahulu pada saat proses kompilasi terjadi. Bentuk umumnya :
7/49
# include
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
Diperlukan pada program yang melibatkan objek cout
#include
Diperlukan
bila
melibatkan
clscr(),yang
perintah
unrtuk
membersihkan layar #include
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 Fungsi yang akan dieksekusi pertama kali oleh c++ Menyatakan bahwa fungsi main tidak memiliki nilai balik Menyatakan bahwa fungsi tidak memiliki argumen Voidmain()
Batas atas program
{ cout<<”Hallo dunia”<<endl;
}
Pernyataan Tubuh Fungsi main ()
Batas akhir program Komentar Komentar merupakan bagian yang penting dalam program.Kehadirannya sangat membantu pemrogram taupun orang lain dalm memahami program,karena berupa penjelasan mengenai
8/49
program 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. Cout (dibaca : C out) Pernyataan cout merupakan sebuah objek di dalam C++, yang digunakan untuk mengarahkan data ke dalam standar output (cetak pada layar).
III. Prepraktikum 1. Instal program Turbo C++ pada computer atau laptop
IV. Kegiatan Praktikum 1. 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 1: 2: 3: 4: 5: 6:
#include <stdio.h> //header void main()//fungsi utama { printf(“Selamat Datang di }
Fakultas Ilmu Komputer”);//statement
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
9/49
6. Buka file baru dengan menekan File New 7. Ketikkan kode program berdasarkan algoritma yang diberikan Algoritma 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
V. No
Hasil LKP (ditulis tangan di kertas A4) Deskripsi Jawaban
1 . . . 9
10/49
VI. Kesimpulan
Lembar Kerja Praktikum 2 : Record dan Array I.
Tujuan
Setelah mengerjakan LKP 1 ini, anda diharapkan dapat:
II.
1.
Memahami konsep pointer dan array di dalam Bahasa C
2.
Memahami konsep copy value dan copy address
3.
Menggunakan pointer dan array di dalam program lainnya
Dasar Teori
Record Record adalah suatu tipe data terstruktur yang berisi sejumlah data yang dapat berlainan jenisnya (tipedatanya tidak sama). Jadi record hampis sama dengan array, bedanya kalau record tipe data yang dimiliki setiap data bentukan dapat bebeda-beda. Sedangkan array tipe datanya harus sama. Bentuk struktur data yang dapat menyimpan variabel-variabel dalam 1 nama, namun memiliki tipe data yang berbeda ataupun sama. Variable-variabel tersebut memiliki kaitan satu sama yang lain. Bentuk umum : typedef struct nama_struct{ tipe_data ; tipe_data ; .... };
DEKLARASI
Ada 2 cara pendeklarasian struct, yaitu :
11/49
Deklarasi 1: typedef struct Mahasiswa { char NIM[8]; char nama[50]; float ipk; };
Deklarasi 2 : struct { char NIM[8]; char nama[50]; float ipk; } mhs;
Contoh struct: #include <stdio.h> #include void main() { struct orang { char nama[40]; short umur; }saya; printf("nama : "); cin.getline(saya.nama,40); printf("umur :" ); scanf("%i",&saya.umur); printf("%s berumur %i",saya.nama,saya.umur); }
ARRAY OF STRUCT Apabila hendak menggunakan 1 struct untuk beberapa kali, ada 2 cara : 1. Deklarasi manual Contoh : #include <stdio.h> typedef struct Mahasiswa { char NIM[8]; char nama[50]; float ipk; }; void main() { Mahasiswa a,b,c; …… …… …… }
artinya struct mahasiswa digunakan untuk 3 variabel, yaitu a,b,c 2. Array of struct Contoh : #include <stdio.h>
12/49
typedef struct Mahasiswa { char NIM[8]; char nama[50]; float ipk; }; void main() { Mahasiswa mhs[3]; …… …… …… }
artinya struct mahasiswa dapat digunakan untuk tiga variabel mhs, yaitu mhs[0], mhs[1], dan mhs[2].
Contoh lainnya : #include <stdio.h> #include #include typedef struct orang { char nama[30]; short umur; }; void main() { orang saya[5]; int i,x; for(i=0;i<=4;i++) { printf("nama ke-%i : ",i+1); cin.getline(saya[i].nama,30); printf("umur ke-%i : ",i+1); scanf("%i",saya[i].umur); printf("%s berumur %i",saya[i].nama,saya[i].umur); } for(x=0;x<=4;x++) { printf("nama %s berumur %d",saya[x].nama,saya[x].umur); } }
Array Satu Dimensi Bentuk umum : tipe_array nama_array [jumlah data] Ilustrasi array satu dimensi
Array di atas mempunyai enam element. Contoh Program :
13/49
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
#include <stdio.h> void main() { int a[5] = {10,25,30,45,50}; int i; for(i=0;i<5;i++) { printf(“%d = %d\n”,i,a[i]); } }
Array Multidimensi Array multidimensi adalah array yang mempunyai lebih dari satu dimensi. Misal : A[3][5] artinya array tersebut mempunyai 3 baris 5 kolom. Bentuk umum : tipe_array nama_array [jumlah data][jumlah data] Ilustrasi array satu dimensi
Array di atas mempunyai delapan belas element. Contoh Program : 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
#include <stdio.h> void main() { int a[3][3] = {{10,20,30},{40,50,60},{70,80,90}}; int i,j; for(i=0;i<3;i++) { for(j=0;j<3;j++) { printf(“%d ”,a[i][j]); } printf(“\n”); } }
Array Dinamis Array dinamis merupakan array yang dibuat dengan menggunakan pointer dinamis Contoh Program :
14/49
1: /* Pointer3.c */ 2: 3: #include <stdio.h> 4: #include <malloc.h> 5: intmain() 6: { 7: 8: int i,j; 9: int **x; 10: 11: x=(int **) malloc(3*sizeof (int *)); 12: 13: for (i=0;i<3;i++) 14: { 15: x[i]=(int *) malloc(3*sizeof (int )); 16: for (j=0;j<3;j++) 17: { 18: x[i][j]=i+j; 19: printf("%d ",x[i][j]); 20: } 21: printf("\n"); 22: } 23: 24: return 0; 25: }
III. Prepraktikum 2. Pada kasus apa saja sebuah array dapat dibuat menjadi array dinamis ?Jelaskan ?
IV. Kegiatan Praktikum Buatlah struct untuk buku dengan deklarasi manual. Ketentuan : Yang harus disimpan adalah judul buku, tahun terbit dan harga buku. Source code :
15/49
#include <stdio.h> #include typedef struct buku{ char judul[15]; int tahun_terbit; int harga; }; void main(){ buku book; printf("Judul buku : ");scanf("%s",&book.judul); printf("Tahun terbit : ");scanf("%i",&book.tahun_terbit); printf("Harga : ");scanf("%i",&book.harga); printf("\nJudul buku : %s\n",book.judul); printf("Tahun terbit : %i\n",book.tahun_terbit); printf("Harga : %i",book.harga); }
V.
Hasil LKP (ditulis tangan di kertas A4)
No
Deskripsi Jawaban
1 2
VI. Evaluasi dan Pertanyaan 1. Untuk kasus array, bagaimana jika nilai n diubah menjadi n=3 ? 2. Buatlah struct untuk data lagu yang berisi tentang judul lagu, penyanyi, tahun produksi, nomor track dan kode album.
Ketentuan : program ini akan memiliki dua buah struct, yaitu struct lagu dan struct kodeRBT.
VII. Kesimpulan
16/49
Lembar Kerja Praktikum 3 : Stack I.
Tujuan
Setelah mengerjakan LKP 5 ini, anda diharapkan dapat: 1. Memahami konsep stack dan mengimplemetasikannya ke bahasa C. 2. Mampu melakukan operasi pop dan push pada stack.
II.
Dasar Teori
Stack (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
Karena aturan penyisipan dan penghapusan semacam itu, TOP adalah satu-satunyaalamat tempat terjadi operasi, elemen yang ditambahkan paling akhir akan menjadielemen yang akan dihapus. Dikatakan bahwa elemen Stack akan tersusun secaraLIFO (Last In First Out). Struktur data ini banyak dipakai dalam informatika, misalnya untuk merepresentasi : -
pemanggilan prosedur
-
perhitungan ekspresi artimatika
-
rekursifitas
-
backtracking
-
dan algoritma lanjut yang lain
Definisi Fungsional Diberikan S adalah Stack dengan elemen ElmtS, maka definisi fungsional stack adalah :
17/49
Definisi Selektor adalah Jika S adalah sebuah Stack, maka Top(S) adalah alamat elemen TOP, di mana operasi penyisipan/penghapusan dilakukan InfoTop(S) adalah informasi yang disimpan pada Top(S). Definisi Stack kosong adalah Stack dengan Top(S)=Nil (tidak terdefinisi). Implementasi Stack dengan tabel : Tabel dengan hanya representasi TOP adalah indeks elemen Top dari Stack. Jika Stack kosong, maka TOP=0. Ilustrasi Stack tidak kosong, dengan 5 elemen :
III. Preparktikum 1. Jelaskan struktur data stack! 2. Buatlah ilustrasi untuk masing-masing operasi pada stack! Prototipe dan Primitif /Algoritma 1. Stack Statis /* file : stackt.h */
18/49
/* deklarasi type dan prototype */
#ifndef stackt_H #define stackt_H #include "boolean.h" #define MaxEl 10 #define Nil 0 typedef int infotype; typedef int address; typedef struct { infotype T[MaxEl+1]; address Top; } Stackt; //Prototype //Kreator void CreateEmpty(Stackt *S); //Mengirim true jika stack kosong boolean IsEmpty(Stackt *S); //mengirim true jika penampung sudah penuh boolean IsFull(Stackt *S); //menambahkan elemen ke stack void Push(Stackt *S, infotype X); //menghapus sebuah elemen stack void Pop(Stackt *S); #endif
IV.
Kegiatan Praktikum 1. Buat file boolean.h 2. Ketik prototipe/primitif di atas dan simpan dengan namastackt.h dan stack.h. 3. Buat file .c yang berisi implementasi dari file .h. 4. Buat file main driver-nya.
V. No
Hasil LKP (ditulis tangan di kertas A4) Deskripsi Jawaban
1 . . 4
19/49
VI.
Evaluasi dan Pertanyaan 1. Tulis algoritma Push dan Pop pada stack statis ? 2. Tentukan apakah sebuah kalimat yang diinputkan dalam program (dengan menggunakan stack) adalah sebuah polindrom atau bukan. Polindrom adalah kalimat yang jika dibaca dari depan dan dari belakang, maka bunyinya sama. Contoh : Kalimat
: sugus
Kalimat tersebut adalah polindrom
VII.
Kesimpulan
20/49
Lembar Kerja Praktikum 4 : Stack Lanjutan Tujuan
I.
Setelah mengerjakan LKP 5 ini, anda diharapkan dapat: 1. Memahami konsep stack dan mengimplemetasikannya ke bahasa C. 2. Mampu melakukan operasi pop dan push pada stack dinamis. II.
III.
Dasar Teori
Preparktikum 1. Jelaskan struktur data stack! 2. Buatlah ilustrasi untuk masing-masing operasi pada stack!
Prototipe dan Primitif /Algoritma 2. Stack Dinamis /* File: stack.h */ #ifndef stack_h #define stack_h #define true 1 #define false 0 #define boolean unsigned char
int infotype, address; typedef struct{ int top; int *T; int size; } stack; /* ***** Konstruktor/Kreator ***** */ /* Membuat sebuah stack s yang kosong berkapasitas size */ void CreateEmpty(stack *s, int size); /* Destruktor : Dealokasi seluruh table memori sekaligus */ void destruct(stack *s); /* Mengirim true jika tabel penampung nilai elemen stack penuh */ boolean IsFull(stack s); /* Mengirim true jika stack kosong */
21/49
boolean IsEmpty(stack s); /* Menambahkan x sebagai elemen stack s */ void push(stack *s, int x); /* Menghapus x dari stack s */ void pop(stack *s, int *x); /* Menambahkan x sebagai elemen stack s, jika s mencapai nilai maksimum */ /* maka s akan melakukan grow, yaitu menambah kapasitas maksimum */ void pushgrow(stack *s, int x); /* Menambah kapasitas penampung stack s */ void grow(stack *s); /* Menghapus x dari stack s. Jika s mencapai nilai minimum */ /* maka s akan melakukan shrink, yaitu mengurangi kapasitas maksimum */ void popshrink(stack *s, int *x); /* Mengurangi kapasitas maksimum penampung stack s */ void shrink(stack *s); #endif
IV.
Kegiatan Praktikum 1. Buat file boolean.h 2. Ketik prototipe/primitif di atas dan simpan dengan namastackt.h dan stack.h. 3. Buat file .c yang berisi implementasi dari file .h. 4. Buat file main driver-nya.
V.
Hasil LKP (ditulis tangan di kertas A4)
No
Deskripsi Jawaban
1 . . 4
VIII. Evaluasi dan Pertanyaan 1. Tulis algoritma Push dan Pop pada stack dinamis? 2. Apa perbedaan stack statis dan stack dinamis? Gabungkan dua jenis stack tersebut!
22/49
IX.
Kesimpulan
Lembar Kerja Praktikum 6 : Queue I.
Tujuan
Setelah mengerjakan LKP 6 ini, anda diharapkan dapat: 1. Memahami konsep Queue dan mengimplementasikannya ke bahasa C. 2. Mampu melakukan operasi add dan delete pada queue.
II.
Dasar Teori
Queue adalah list linier yang : a. Dikenali elemen pertama (HEAD) dan elemen terakhirnya (TAIL), b. Aturan penyisipan dan penghapusan elemennya didefinisikan sebagai berikut: -
Penyisipan selalu dilakukan setelah elemen terakhir
-
Penghapusan selalu dilakukan pada elemen pertama
c. Satu elemen dengan yang lain dapat diakses melalui informasi NEXT. Struktur data ini banyak dipakai dalam informatika, misalnya untuk merepresentasi: -
antrian job yang harus ditangani oleh sistem operasi
-
antrian dalam dunia nyata.
Maka secara lojik, sebuah QUEUE dapat digambarkan sebagai list linier yang setiapelemennya adalah type ElmtQ : < Info : InfoType, Next :address> dengan InfoType adalah sebuah type terdefinisi yang menentukan informasi yangdisimpan pada setiap elemen queue, dan address adalah "alamat" dari elemen.Selain itu alamat elemen pertama (HEAD) dan elemen terakhir(TAIL) dicatat :Maka jika Q adalah Queue dan
23/49
P adalah adaress, penulisan untuk Queue adalah :Head(Q),Tail(Q), Info(Head(Q)), Info(Tail(Q)).
Definisi Fungsional Queue Diberikan Q adalah QUEUE dengan elemen ElmtQ maka definisi fungsional antrian adalah:
Implementasi QUEUE dengan tabel : Memori tempat penyimpan elemen adalah sebuah tabel dengan indeks 1..IdxMax. IdxMax dapat juga dipetakan ke kapasitas Queue. Representasi field Next: Jika i adalah address sebuah elemen, maka suksesor i adalah Next dari elemen Queue. Tabel dengan hanya representasi TAIL adalah indeks elemen terakhir, HEAD selalu diset sama dengan 1 jika Queue tidak kosong. Jika Queue kosong, maka HEAD=0. Ilustrasi Queue tidak kosong, dengan 5 elemen :
Algoritma paling sederhana untuk penambahan elemen jika masih ada tempat adalah
24/49
dengan memajukan TAIL. Kasus khusus untuk Queue kosong karena HEAD harus diset nilainya menjadi 1. Algoritma paling sederhana dan naif untuk penghapusan elemen jika Queue tidak kosong: ambil nilai elemen HEAD, geser semua elemen mulai dari HEAD+1 s/d TAIL (jika ada), kemudian TAIL mundur. Kasus khusus untuk Queue dengan keadaan awal berelemen 1, yaitu menyesuaikan HEAD dan TAIL dengan DEFINISI. Algoritma ini mencerminkan pergeseran orang yang sedang mengantri di dunia nyata, tapi tidak efisien.
III. Prepraktikum 1. Jelaskan struktur data queue! 2. Buatlah ilustrasi untuk masing-masing operasi pada queue! Prototipe dan Primitif /Algoritma /* Nama file QueueList.h */ #ifndef QueueList_H #define QueueList_H #include "boolean.h" #include <stdio.h> #include <stdlib.h> #define Nil 0 #define MaxIdx 15 /* Definisi elemen dan address */ typedef int infotype; typedef int address; /* Indeks tabel */ typedef struct { infotype Info; address Next; } ElmtQueue; externElmtQueue TabMem[MaxIdx+1]; typedef struct { address HEAD; /* Alamat penghapusan */ address TAIL; /* Alamat penambahan */ } queue; /** ===== Akses Selektor ===== **/ #define Head(Q) (Q).HEAD #define Tail(Q) (Q).TAIL #define InfoHead(Q) TabMem[(Q).HEAD].Info #define InfoTail(Q) TabMem[(Q).TAIL].Info #define Info(P) TabMem[(P)].Info #define Next(P) TabMem[(P)].Next /** ========== **/ /** ===== Prototype ===== **/ boolean IsEmpty(queue Q); /* Mengirim TRUE jika Q kosong: Head=Nil dan Tail=Nil */ boolean IsFull(queue Q); /* Mengirim TRUE jika tabel penampung elemen Q sudah penuh */ /* Yaitu mengandung MaxEl elemen */ intNbElmt(queue Q); /* Mengirimkan banyaknya elemen queue. Mengirimkan 0 jika Q kosong */
25/49
/** ========== **/ /** ===== Kreator ===== **/ voidInisialisasi(void); /* Menyiapkan memori untuk linked Queue agar siap dipakai */ voidCreateEmpty(queue *Q); /* Membuat sebuah Q kosong */ /** ========== **/ /** ===== Manajemen Memori ===== **/ voidAlokasi (address *P, infotype X); /* Mengirimkan address hasil alokasi sebuah elemen */ /* Jika alokasi berhasil, maka address tidak nil, dan misalnya */ /* menghasilkan P , maka info(P) = X, Next(P) = Nil */ /* Jika alokasi gagal, mengirimkan Nil */ voidDealokasi (address P); /* I.S : P terdefinisi */ /* F.S : P dikembalikan ke sistem */ /* Melakukan dealokasi/pengembalian address P */ /** ========== **/ /** ===== Primitif Add/Delete ===== **/ voidAdd(queue *Q, infotype X); /* Menambahkan X pada Q dengan aturan FIFO */ /* Jika Tail(Q)=MaxEl+1 maka geser isi tabel, shg Head(Q)=1 */ /* precondition: tabel penampung elemen Q tidak penuh */ voidDel(queue *Q, infotype *X); /* Menghapus X pada Q dengan aturan FIFO */ /* precondition: tabel penampung elemen Q tidak kosong */ /** ========== **/ #endif
IV.
Kegiatan Praktikum 1. Buat file boolean.h 2. Ketik prototipe/primitif di atas dan simpan dengan namaADT Queue1.h. 3. Buat file .c yang berisi implementasi dari file .h. 4. Buat file main driver-nya.
V.
Hasil LKP (ditulis tangan di kertas A4)
No
Deskripsi Jawaban
1 . . 4
VI.
Evaluasi dan Pertanyaan 1. Tuliskan algoritma add dan delete pada queue di atas ? 2. Buatlah program antrian nasabah bank dengan skenario seperti berikut ! Terdapata 2 buah loket yaitu Teller dan Custumer service.
26/49
Data nasabah terdiri dari Nama dan Tujuan. Maksimal antrian 20 orang nasabah untuk setiap loket. Jika nasabah yang datang menuju teller, masukkan antrian ke teller dan sebaliknya jika nasabah ingin menuju Custumer Service, masukkan pada antrian Custumer service.Untuk mengetahui apakah nasabah menuju ke Teller atau Custumer service dapat dilihat pada data tujuan.Berikan pula fungsi untuk mengitung jumlah nasabah baik yang ada di loket Teller maupun loket Custumer service.
VII. Kesimpulan
Lembar Kerja Praktikum 7 : Queue Lanjutan I.
Tujuan
Setelah mengerjakan LKP 7 ini, anda diharapkan dapat: 1. Memahami konsep Queue dan mengimplementasikannya ke bahasa C. 2. Mampu melakukan operasi add dan delete pada queue.
II.
Dasar Teori
Queue adalah list linier yang : a. Dikenali elemen pertama (HEAD) dan elemen terakhirnya (TAIL), b. Aturan penyisipan dan penghapusan elemennya didefinisikan sebagai berikut: -
Penyisipan selalu dilakukan setelah elemen terakhir
-
Penghapusan selalu dilakukan pada elemen pertama
c. Satu elemen dengan yang lain dapat diakses melalui informasi NEXT. Struktur data ini banyak dipakai dalam informatika, misalnya untuk merepresentasi: -
antrian job yang harus ditangani oleh sistem operasi
27/49
-
antrian dalam dunia nyata.
Maka secara lojik, sebuah QUEUE dapat digambarkan sebagai list linier yang setiapelemennya adalah type ElmtQ : < Info : InfoType, Next :address> dengan InfoType adalah sebuah type terdefinisi yang menentukan informasi yangdisimpan pada setiap elemen queue, dan address adalah "alamat" dari elemen.Selain itu alamat elemen pertama (HEAD) dan elemen terakhir(TAIL) dicatat :Maka jika Q adalah Queue dan P adalah adaress, penulisan untuk Queue adalah :Head(Q),Tail(Q), Info(Head(Q)), Info(Tail(Q)).
Definisi Fungsional Queue Diberikan Q adalah QUEUE dengan elemen ElmtQ maka definisi fungsional antrian adalah:
Implementasi QUEUE dengan tabel : Memori tempat penyimpan elemen adalah sebuah tabel dengan indeks 1..IdxMax. IdxMax dapat juga dipetakan ke kapasitas Queue. Representasi field Next: Jika i adalah address sebuah elemen, maka suksesor i adalah Next dari elemen Queue. Tabel dengan hanya representasi TAIL adalah indeks elemen terakhir, HEAD selalu diset sama dengan 1 jika Queue tidak kosong. Jika Queue kosong, maka HEAD=0. Ilustrasi Queue tidak kosong, dengan 5 elemen :
28/49
Algoritma paling sederhana untuk penambahan elemen jika masih ada tempat adalah dengan memajukan TAIL. Kasus khusus untuk Queue kosong karena HEAD harus diset nilainya menjadi 1. Algoritma paling sederhana dan naif untuk penghapusan elemen jika Queue tidak kosong: ambil nilai elemen HEAD, geser semua elemen mulai dari HEAD+1 s/d TAIL (jika ada), kemudian TAIL mundur. Kasus khusus untuk Queue dengan keadaan awal berelemen 1, yaitu menyesuaikan HEAD dan TAIL dengan DEFINISI. Algoritma ini mencerminkan pergeseran orang yang sedang mengantri di dunia nyata, tapi tidak efisien.
III.
Prepraktikum
3. Jelaskan struktur data queue! 4. Buatlah ilustrasi untuk masing-masing operasi pada queue! Prototipe dan Primitif /Algoritma /* Nama file QueueList.h */ #ifndef QueueList_H #define QueueList_H #include "boolean.h" #include <stdio.h> #include <stdlib.h> #define Nil 0 #define MaxIdx 15 /* Definisi elemen dan address */ typedef int infotype; typedef int address; /* Indeks tabel */ typedef struct { infotype Info; address Next; } ElmtQueue; externElmtQueue TabMem[MaxIdx+1]; typedef struct { address HEAD; /* Alamat penghapusan */ address TAIL; /* Alamat penambahan */ } queue; /** ===== Akses Selektor ===== **/ #define Head(Q) (Q).HEAD
29/49
#define Tail(Q) (Q).TAIL #define InfoHead(Q) TabMem[(Q).HEAD].Info #define InfoTail(Q) TabMem[(Q).TAIL].Info #define Info(P) TabMem[(P)].Info #define Next(P) TabMem[(P)].Next /** ========== **/ /** ===== Prototype ===== **/ boolean IsEmpty(queue Q); /* Mengirim TRUE jika Q kosong: Head=Nil dan Tail=Nil */ boolean IsFull(queue Q); /* Mengirim TRUE jika tabel penampung elemen Q sudah penuh */ /* Yaitu mengandung MaxEl elemen */ intNbElmt(queue Q); /* Mengirimkan banyaknya elemen queue. Mengirimkan 0 jika Q kosong */ /** ========== **/ /** ===== Kreator ===== **/ voidInisialisasi(void); /* Menyiapkan memori untuk linked Queue agar siap dipakai */ voidCreateEmpty(queue *Q); /* Membuat sebuah Q kosong */ /** ========== **/ /** ===== Manajemen Memori ===== **/ voidAlokasi (address *P, infotype X); /* Mengirimkan address hasil alokasi sebuah elemen */ /* Jika alokasi berhasil, maka address tidak nil, dan misalnya */ /* menghasilkan P , maka info(P) = X, Next(P) = Nil */ /* Jika alokasi gagal, mengirimkan Nil */ voidDealokasi (address P); /* I.S : P terdefinisi */ /* F.S : P dikembalikan ke sistem */ /* Melakukan dealokasi/pengembalian address P */ /** ========== **/ /** ===== Primitif Add/Delete ===== **/ voidAdd(queue *Q, infotype X); /* Menambahkan X pada Q dengan aturan FIFO */ /* Jika Tail(Q)=MaxEl+1 maka geser isi tabel, shg Head(Q)=1 */ /* precondition: tabel penampung elemen Q tidak penuh */ voidDel(queue *Q, infotype *X); /* Menghapus X pada Q dengan aturan FIFO */ /* precondition: tabel penampung elemen Q tidak kosong */ /** ========== **/ #endif
IV.
Kegiatan Praktikum
5. Buat file boolean.h 6. Ketik prototipe/primitif di atas dan simpan dengan namaADT Queue1.h. 7. Buat file .c yang berisi implementasi dari file .h. 8. Buat file main driver-nya.
V. No
Hasil LKP (ditulis tangan di kertas A4) Deskripsi Jawaban
30/49
1 . . 4
VI.
Evaluasi dan Pertanyaan
1. Tuliskan algoritma add dan delete pada queue di atas ? 2. Buatlah program antrian nasabah bank dengan skenario seperti berikut ! Terdapata 2 buah loket yaitu Teller dan Custumer service. Data nasabah terdiri dari Nama dan Tujuan. Maksimal antrian 20 orang nasabah untuk setiap loket. Jika nasabah yang datang menuju teller, masukkan antrian ke teller dan sebaliknya jika nasabah ingin menuju Custumer Service, masukkan pada antrian Custumer service.Untuk mengetahui apakah nasabah menuju ke Teller atau Custumer service dapat dilihat pada data tujuan.Berikan pula fungsi untuk mengitung jumlah nasabah baik yang ada di loket Teller maupun loket Custumer service.
VII.
Kesimpulan
31/49
Lembar Kerja Praktikum 8 : List (bagian I) I.
Tujuan
Setelah mengerjakan LKP 3 ini, anda diharapkan dapat:
II.
1.
Memahami konsep list dan mampu mengimplementasikannya ke bahasa C.
2.
Mampu melakukan operasi insert dan delete pada list.
Dasar Teori
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 : 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 didefinisikan disebut sudah di-alokasi. Didefinisikan suatu konstanta Nil, yang artinya alamat yang tidak terdefinisi. Alamat ini nantinya akan didefinisikan secara lebih konkret ketika list linier diimplementasi pada struktur data fisik
Jadi, sebuah list linier dikenali : elemen pertamanya, biasanya melalui alamat elemen pertama yang disebut : Firstalamat elemen berikutnya (suksesor), jika kita mengetahui alamat sebuahelemen,yang dapat diakses melalui informasi NEXT. NEXT mungkin ada secaraeksplisit (seperti contoh di atas), atau secara implisit yaitu lewat kalkulasi ataufungsi suksesor. Setiap elemen mempunyai alamat, yaitu tempat elemen disimpandapat diacu. Untuk mengacu sebuah
32/49
elemen, alamat harus terdefinisi. Dengan alamat tersebut Informasi yang tersimpan pada elemen list dapat diakses elementerakhirnya. 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 : o List L adalah list kosong, jika First(L) = Nil o Elemen terakhir dikenali, misalnya jika Last adalah alamat element terakhir, maka Next(Last) =Nil
INSERT-First Menambahkan sebuah elemen yang diketahui alamatnya sebagai elemen pertama list.Insert elemen pertama, List kosong :
33/49
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
34/49
INSERT-After : Menyisipkan sebuah elemen beralamat P setelah sebagai suksesor dari sebuah elemen list linier yang beralamat Prec
INSERT-Last Menyisipkan sebuah elemen beralamat P setelah 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
DELETE-First : menghapus elemen pertama list linier Elemen yang dihapus dicatat alamatnya :
35/49
DELETE-After : Penghapusan suksesor sebuah elemen :
DELETE-Last : Menghapus elemen terakhir list dapat dilakukan jika alamat dari elemen sebelum elemen terakhir diketahui. Persoalan selanjutnya menjadi persoalan DELETEAFTER, kalau Last bukan satu-satunya elemen list linier. Ada dua kasus, yaitu list menjadi kosong atau tidak. Kasus list menjadi kosong :
List tidak menjadi kosong (masih mengandung elemen) :
III. Prepraktikum 1.
Jelaskan struktur data linked list!
2.
Jelaskan operasi-operasi pada linked list!
3.
Jelaskan macam-macam linked list dan gambar dari macam-macam linked list tersebut!
36/49
Prototipe dan Primitif /Algoritma /*file : list1.h*/ /*contoh ADT list berkait dengan representasi fisik pointer*/ /*representasi address dengan pointer*/ /*infotype adalah integer*/ #ifndef list_H #define list_H #include "boolean.h" #define #define #define #define
Nil NULL info(P) (*P).info next(P) (P)->next First(L) ((L).First)
#define infotype int typedef struct tElmtlist *address; typedef struct tElmtlist { infotype info; address next; } Elmtlist; /*Definisi list*/ /*List kosong : First(L) = Nil*/ /*Setiap elemen dengan address P dapat diacu info(P), Next (P)*/ /*Elemen terakhir list : jika addressnya Last, maka Next(Last) = Nil*/ typedef struct { address First; } List; /*PROTOTYPE*/ /*test list kosong*/ boolean ListEmpty (List L); /*true jika list kosong*/ /*PEMBUATAN LIST KOSONG*/ void CreateList (List *L); /*membentuk list kosong*/ /*MANAJEMEN MEMORI*/ address alokasi (infotype X); /*mengirimkan address hasil alokasi sebuah elemen*/ /*jika alokasi berhasil, maka address tidak nil, dan */ /*bila menghasilkan P, maka info(P) = X, Next(P) = Nil*/ /*jika alokasi gagal, mengirimkan Nil*/ void dealokasi (address P); /*mengembalikan P ke sistem*/
37/49
/*melakukan dealokasi/pengembalian address P*/ /*PRIMITF BERDASARKAN ALAMAT*/ void InsertFirst(List *L, address P); /*menambahkan elemen beraddress P sebagai elemen pertama*/ void InsertAfter(List *L, address P, address Prec); /*Prec pastilah elemen list dan bukan elemen terakhir*/ void InsertLast(List *L, address P); /*P ditambahkan sebagai elemen terakhir yang baru*/
/*PENGHAPUSAN SEBUAH ELEMEN*/ void DelFirst(List *L, address *P); /*P adalah alamat elemen pertama list sebelum penghapusan*/ /*elemen list berkurang satu, firstelemen baru adalah suksesor elemen pertama yang lama*/ void DelP(List *L, infotype X); /*jika ada elemen list beraddress P, dengan info(P) = X*/ /*maka P dihapus dari list dan didealokasi*/ /*jika tak ada, maka list tetap*/ void DelLast (List *L, address *P); /*P adalah alamat elemen terakhir list sebelum penghapusan*/ /*Last Elemen yang baru adalah predesesor elemen pertama yang lama*/ void DelAfter(List *L, address *Pdel, address Prec); /*Prec adalah anggota list*/ /*menghapus Next (Prec)*/ /*PROSES SEMUA ELEMEN LIST*/ void Printinfo(List L); /*semua info yang disimpan pada elemen list diprint*/ /*jika list ksoong, hanya menuliskan "list kosong"*/ int NbElmt(List L); /*mengirimkan banyaknya elemen list, 0 bila list kosong*/ infotype Max(List L); /*mengirimkan nilai info(P) yang maksimum*/ infotype Min(List L); /*mengirimkan nilai info(P) yang minimum*/ #endif
IV. Kegiatan Praktikum 2. Ketik kode program dibawah ini kemudian simpan dengan nama boolean.h
38/49
3. Ketik prototipe/primitif di atas dan simpan dengan namalist.h. 4. Buat file list.c yang berisi implementasi dari list.h. 5. Buat file main driver mlist.c.
V.
Hasil LKP (ditulis tangan di kertas A4)
No
Deskripsi Jawaban
1 . . 4
VI. Evaluasi dan Pertanyaan 1.
Tuliskan algoritma untuk nilai maksimum list dan minimum list ?
2.
Tambahkan program untuk mencetak address max dan address min ?
VII. Kesimpulan
Lembar Kerja Praktikum 9 : List (lanjutan) I.
Tujuan
Setelah mengerjakan LKP 4 ini, anda diharapkan dapat:
39/49
II.
1.
Memahami konsep list dan mampu mengimplementasikannya ke bahasa C.
2.
Mampu melakukan operasi insert dan delete berdasarkan value pada list.
Dasar Teori
List Linier Tidak ada perbedaan dengan teori pada Modul List (bagian 1) sebelumnya hanyasaja pada modul ini proses pada list berdasarkan value Prototipe dan Primitif /Algoritma /*file : list1.h*/ /*contoh ADT list berkait dengan representasi fisik pointer*/ /*representasi address dengan pointer*/ /*infotype adalah integer*/ #ifndef list_H #define list_H #include "boolean.h" #define #define #define #define
Nil NULL info(P) (*P).info next(P) (P)->next First(L) ((L).First)
#define infotype int typedef struct tElmtlist *address; typedef struct tElmtlist { infotype info; address next; } Elmtlist; /*Definisi list*/ /*List kosong : First(L) = Nil*/ /*Setiap elemen dengan address P dapat diacu info(P), Next (P)*/ /*Elemen terakhir list : jika addressnya Last, maka Next(Last) = Nil*/ typedef struct { address First; } List; void InsertAfter(List *L, address P, address Prec); /*Prec pastilah elemen list dan bukan elemen terakhir*/ void InsertLast(List *L, address P); /*P ditambahkan sebagai elemen terakhir yang baru*/ void DelP(List *L, infotype X);
40/49
/*jika ada elemen list beraddress P, dengan info(P) = X*/ /*maka P dihapus dari list dan didealokasi*/ /*jika tak ada, maka list tetap*/ void DelLast (List *L, address *P); /*P adalah alamat elemen terakhir list sebelum penghapusan*/ /*Last Elemen yang baru adalah predesesor elemen pertama yang lama*/ void DelAfter(List *L, address *Pdel, address Prec); /*Prec adalah anggota list*/ /*menghapus Next (Prec)*/ int NbElmt(List L); /*mengirimkan banyaknya elemen list, 0 bila list kosong*/ infotype Max(List L); /*mengirimkan nilai info(P) yang maksimum*/ infotype Min(List L); /*mengirimkan nilai info(P) yang minimum*/ /*PRIMITIF BERDASARKAN NILAI*/ void InsVFirst (List *L, infotype X); /*melakukan alokasi sebuah elemen, dan menambahkan elemen pertama dengan nilai X*/ /*bila alokasi berhasil*/ void InsVLast (List *L, infotype X); /*menambahkan elemen list di akhir, elemen terakhir yang baru*/ /*PENCARIAN SEBUAH ELEMEN LIST*/ address Search (List L, infotype X); /*mencari apakah ada elemen list dengan info(P) = X*/ /*Jika ada, kirimkan address. Jika tak ada kirimkan Nil*/
III. Kegiatan Praktikum 1. Ketik kode program dibawah ini kemudian simpan dengan nama boolean.h
2. Ketik prototipe/primitif di atas dan simpan dengan namalist.h. 3. Buat file list.c yang berisi implementasi dari list.h. 6. Buat file main driver mlist.c.
IV. Hasil LKP (ditulis tangan di kertas A4) No
Deskripsi Jawaban
41/49
1 . . 4
V.
Evaluasi dan Pertanyaan 1. Apa perbedaan operasi list berdasarkan address dengan operasi list berdasarkanvalue ?beri penjelasan ? 2. Sehubungan dengan pertanyaan 1, bagaimana dengan algoritmanya ?
VI. Kesimpulan
Lembar Kerja Praktikum 11: Multi List I.
Tujuan
Setelah mengerjakan LKP 4 ini, anda diharapkan dapat: 1. 2.
Memahami konsep list dan mampu mengimplementasikannya ke bahasa C. Mampu melakukan operasi insert dan delete berdasarkan value pada list.
42/49
II.
Dasar Teori
Multi List Salah satu alternatif merepresentasikan multi list :
Tidak ada perbedaan dengan teori pada Modul List (bagian 1) sebelumnya hanyasaja pada modul ini proses pada list berdasarkan value
III.
Evaluasi dan Pertanyaan
1. Apa perbedaan operasi list dengan multi lis ?beri penjelasan ? 2. Sehubungan dengan pertanyaan 1, bagaimana dengan implementasi programnya ?
43/49
IV.
Kesimpulan
Lembar Kerja Praktikum 12 : Binary Search Tree I.
Tujuan
Setelah mengerjakan LKP 7 ini, anda diharapkan dapat: 1. Memahami konsep binary search tree dan mengimplementasikannya ke bahasa C. 2. Mampu melakukan operasi add dan delete dan search pada tree.
II.
Dasar Teori
Sebuah pohon biner adalah himpunan terbatas yang -
mungkin kosong, atau
-
terdiri dari sebuah simpul yang disebut akar
dan dua buah himpunan lain yang disjointyang merupakan pohon biner, yangdisebut sebagai sub pohon kiri dan sub pohon kanan dari pohon biner tersebut.Perhatikanlah perbedaan pohon biner dengan pohon biasa : pohon biner mungkinkosong, sedangkan pohon n-aire tidak mungkin kosong. Contoh pohon ekspresi aritmatika
Karena adanya arti bagi sub pohon kiri dan sub pohon kanan, maka dua buah pohon biner sebagai berikut berbeda (pohon berikut disebut pohoncondong/skewed tree)
44/49
Sub pohon ditunjukkan dengan penulisan ()
Pohon Seimbang (balanced tree)
Pohon seimbang tingginya: perbedaan tinggi sub pohon kiri dengan sub pohon kanan maksimum 1
Pohon seimbang banyaknya simpul: perbedaan banyaknya simpul sub pohon kiri dengan sub pohon kanan maksimum 1
Pohon Biner Terurut (Binary serach tree) Pohon biner terurut P memenuhi sifat :
Semua simpul subpohon kiri selalu < dari Info(P)
Semua simpul subpohon kiri selalu > dari Info(P)
Untuk simpul yang sama nilainya : disimpan berapa kali muncul. Maka sebuah node P akan menyimpan informasi : Info(P), Left(P), Right(P) , Count(P) yaitu banyaknya kemunculan Info(P). Contoh eksekusi penghapusan node pada pohon biner terurut:
45/49
III. Prepraktikum 1. Jelaskan struktur data tree/pohon! 2. Jelaskan masing - masing jenis traverse dan buatlah ilustrasinya! Prototipe dan Primitif /Algoritma /* file : bst.h */ #ifndef BST_H_ #define BST_H_ #include <stdlib.h> #include <stdio.h> #define Nil NULL /* Lengkapilah definisi selektor dibawah ini */ #define Akar(P) (P)->info #define Left(P) (P)->left #define Right(P) (P)->right #define IsUnerLeft(P) Left(P)!=Nil && Right(P)==Nil #define IsUnerRight(P) Left(P)==Nil && Right(P)!=Nil #define IsBin(P) Left(P)!=Nil && Right(P)!=Nil #define IsDaun(P) Left(P)==Nil && Right(P)==Nil typedef int infotype; typedef struct tElmtTree *addrTree; typedef struct tElmtTree { infotype info; addrTree left; addrTree right; } ElmtTree; typedef addrTree BinTree; BinTree Alokasi(infotype I);
46/49
/* Mengembalikan hasil alokasi sebuah BinTree P dengan Akar(P)=I, */ /* Left(P)=Nil dan Right(P)=Nil */ void Dealokasi(BinTree Node); /* I.S : Node adalah sebuah BinTree dengan Left(Node)=Nil */ /* dan Right(Node)=Nil */ /* F.S : Node dihancurkan dan Node=Nil */ /* Proses : Menghancurkan alamat memori yang ditunjuk Node, dan */ /* nilai Node diset Nil */ void MakeTree(infotype I,BinTree L,BinTree R,BinTree *P); /* I.S : I adalah infotype sembarang, L dan R mungkin Nil ,P */ /* sembarang */ /* F.S : P adalah sebuah pohon baru dengan Akar(*P)=I, */ /* Left(*P)=L, dan Right(*P)=Nil */ /* Proses : Mengalokasikan sebuah pohon baru *P dengan nilai */ /* Akar(*P)=I, Left(*P)=L, dan Right(*P)=Nil jika */ /* alokasi berhasil. Jika alokasi gagal P=Nil */ void DestroyTree(BinTree *P); /* I.S : P adalah pointer ke BinTree, mungkin Nil */ /* F.S : Pohon Biner P dihancurkan, semua memori yang digunakan */ /* dikembalikan, dan P=Nil */ /* Proses : Menghancurkan pohon biner P, semua memori yang */ /* digunakan dihancurkan dan P=Nil */ void PrintTree(BinTree P); /* I.S : P adalah pohon biner mungkin kosong */ /* F.S : P tidak berubah, semua nilai dituliskan ke layar */ /* Proses : Menuliskan semua nilai info dari setiap simpul pohon /* dengan notasi prefix contoh : (7(3()(5()()))(11()())) */ BinTree Search(BinTree P,infotype I); /* Mengembalikan alamat simpul pohon P dimana nilai info = I, jika */ /* tidak ada mengembalikan Nil */ int NbElmt(BinTree P); /* Mengembalikan jumlah simpul dari pohon P, P mungkin kosong */ int NbDaun(BinTree P); /* Mengembalikan jumlah daun dari pohon P, P mungkin kosong */ int IsSkewLeft(BinTree P); /* Mengembalikan 1 jika P adalah pohon condong kiri, atau 0 jika /* bukan condong kiri */ int IsSkewRight(BinTree P); /* Mengembalikan 1 jika P adalah pohon condong kanan, atau 0 */ /* jika bukan condong kanan */ int Level(BinTree P,infotype I); /* Mengembalikan level I dalam pohon P, jika I tidak ada dalam */ /* pohon P mengembalikan 0 */ void Add(BinTree *P,infotype I); /* I.S : P adalah pointer ke pohon biner P mungkin kosong, */ /* Pohon P tidak mempunyai simpul dengan nilai I */ /* F.S : I menjadi salah satu simpul pohon P, dan P tetap */ /* memenuhi aturan biner search tree */ /* Proses : menambahkan I menjadi salah satu simpul pohon P */ /* dengan aturan biner search tree */
47/49
void Del(BinTree *P,infotype I); /* I.S : P adalah pointer ke pohon biner P mungkin kosong, */ /* I bernilai sembarang */ /* F.S : Jika terdapat simpul dari P dengan nilai info = I, maka */ /* simpul dihapus */ /* Proses : Menghapus simpul dari pohon P jika nilai info = I dan P */ /* tetap memenuhi aturan biner search tree */ infotype Sum(BinTree P); /* Mengembalikan hasil penjumlahan semua nilai info dari setiap */ /* simpul yang dimiliki pohon P */ #endif // BST_H
IV.
Kegiatan Praktikum 1. Buat file boolean.h 2. Ketik prototipe/primitif di atas dan simpan dengan namabst.h 3.
Buat file .c yang berisi implementasi dari file .h.
4.
Buat file main driver-nya.
V.
Hasil LKP (ditulis tangan di kertas A4)
No
Deskripsi Jawaban
1 . . 4
VI.
Evaluasi dan Pertanyaan 1. Tuliskan algoritma add dan delete tree di atas ? 2. Buatlah fungsi untuk menampilkan data secara inorder, preorder, postorder, dan fungsi menghapus suatu node pada tree! 3. Buatlah program lengkap untuk semua operasi-operasi didalam tree (insert, find, traverse, count, height, find max, find min, child) dengan berbasis menu !
VII. Kesimpulan
48/49
Referensi Fachrurrozi, M (2009). Modul Praktikum Algoritma dan Pemrograman I Fasilkom Unsri Kernighan, Brian W and Dennis M. Ritchie. (1988). The C Programming Languange. New Delhi : Prentice Hall of India Liem, Inggriani. (2007). Diktat Algoritma dan Pemrograman Prosedural. Teknik Informatika ITB Sjukani, Moh. (2007). Algoritma (Algoritma dan Struktur Data 1) dengan C, C++, dan Java. Jakarta : Mitra Wacana Media
49/49
