Transcript

MODUL PRAKTIKUM

“STRUKTUR DATA”

LABORATORIUM KOMPUTER

FAKULTAS ILMU KOMPUTER

UNIVERSITAS SRIWIJAYA

2011

2/49

Universitas SriwijayaFakultas Ilmu KomputerLaboratorium

LEMBAR PENGESAHANMODUL PRAKTIKUM

SISTEM MANAJEMENMUTU

ISO 9001:2008

No. Dokumen ……. Tanggal 4 AGUSTUS 2011Revisi 0 Halaman 2 DARI 49

MODUL PRAKTIKUM

Mata Kuliah Praktikum : Struktur dataKode Mata Kuliah Praktikum : FIK28211SKS : 1Program Studi : Teknik InformatikaSemester : 3 (Ganjil)

DIBUAT OLEH DISAHKAN OLEH DIKETAHUI OLEH

TIM LABORANLABORATORIUMFASILKOM UNSRI

TIM DOSEN TEKNIKINFORMATIKA FASILKOM

UNSRI

KEPALA LABORATORIUM

3/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

4/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 : Menu Utama

2 : Toolbar

3 : Jendela pengetikan kode program

4 : Jendela Message/Pesan kesalahan kode

Create new, Open, Save, Save As File

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

sebagai berikut :

1

2

3

4

5/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.

6/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 langkah-

langkahnya adalah sebagai berikut :

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

status compile seperti berikut :

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

7/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

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

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

# prepocessor directivevoid main(){

// Batang Tubuh Program Utama}

8/49

# include <nama_file>

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

pernyataan, tetapi merupakan prepocessor directive. Baris tersebut menginstrusikan kepada

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

file yang berisi sebagai deklarasi contohnya:

Preprocessor Directive Fungsi

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

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

membersihkan layar

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

lebar dari suatu tampilan data

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

bermanfaat untuk operasi matematika kuadrat

Fungsi Main ()

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

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

berada didalam fungsi main( ).

Kata void yang mendahului main() dipakai untuk menyatakan bahwa fungsi ini tidak

memiliki nilai balik

Komentar

Komentar merupakan bagian yang penting dalam program.Kehadirannya sangat membantu

pemrogram taupun orang lain dalm memahami program,karena berupa penjelasan mengenai

Voidmain()

{

cout<<”Hallo dunia”<<endl;

}

Pernyataan

Tubuh Fungsi main ()

Fungsi yang akan dieksekusi pertama kali oleh c++Menyatakan bahwa fungsi main tidak memiliki nilai balik

Menyatakan bahwa fungsi tidak memiliki argumen

Batas atas program

Batas akhir program

9/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

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

1: #include <stdio.h> //header2:3: void main()//fungsi utama4: {

5: printf(“Selamat Datang di Fakultas Ilmu Komputer”);//statement6: }

10/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. Hasil LKP (ditulis tangan di kertas A4)

No Deskripsi Jawaban

1

.

.

.9

11/49

VI. Kesimpulan

Lembar Kerja Praktikum 2 : Record dan Array

I. Tujuan

Setelah mengerjakan LKP 1 ini, anda diharapkan dapat:

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

II. 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 <nama_var>;tipe_data <nama_var>;....};

DEKLARASIAda 2 cara pendeklarasian struct, yaitu :

12/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 <iostream.h>

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 STRUCTApabila 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 structContoh :

#include <stdio.h>

13/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 <iostream.h>#include <conio.h>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 :

Ilustrasi array satu dimensi

Array di atas mempunyai enam element.

Contoh Program :

tipe_array nama_array [jumlah data]

14/49

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 :

Ilustrasi array satu dimensi

Array di atas mempunyai delapan belas element.

Contoh Program :

Array Dinamis

Array dinamis merupakan array yang dibuat dengan menggunakan pointer dinamis

Contoh Program :

1: #include <stdio.h>2:3: void main()4: {5: int a[3][3] = {{10,20,30},{40,50,60},{70,80,90}};6: int i,j;7:8: for(i=0;i<3;i++)9: {10: for(j=0;j<3;j++)11: {12: printf(“%d ”,a[i][j]);13: }14: printf(“\n”);15: }16: }

tipe_array nama_array [jumlah data][jumlah data]

1: #include <stdio.h>2:3: void main()4: {5: int a[5] = {10,25,30,45,50};6: int i;7:8: for(i=0;i<5;i++)9: {10: printf(“%d = %d\n”,i,a[i]);11: }12: }

15/49

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 :

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: }

16/49

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 structkodeRBT.

VII. Kesimpulan

#include <stdio.h>#include <conio.h>

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);

}

17/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 :

18/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 */

19/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

//Kreatorvoid CreateEmpty(Stackt *S);

//Mengirim true jika stack kosongboolean IsEmpty(Stackt *S);

//mengirim true jika penampung sudah penuhboolean IsFull(Stackt *S);

//menambahkan elemen ke stackvoid Push(Stackt *S, infotype X);

//menghapus sebuah elemen stackvoid 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. Hasil LKP (ditulis tangan di kertas A4)

No Deskripsi Jawaban

1

.

.4

20/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

21/49

Lembar Kerja Praktikum 4 : Stack Lanjutan

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 dinamis.

II. Dasar Teori

III. 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 */

22/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 nilaimaksimum *//* 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!

23/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

24/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

25/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 */

26/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.

27/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

28/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 :

29/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

30/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. Hasil LKP (ditulis tangan di kertas A4)

No Deskripsi Jawaban

31/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

32/49

Lembar Kerja Praktikum 8 : List (bagian I)

I. Tujuan

Setelah mengerjakan LKP 3 ini, anda diharapkan dapat:

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

2. Mampu melakukan operasi insert dan delete pada list.

II. Dasar Teori

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 :

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

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

33/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 :

34/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

35/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 :

36/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!

37/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 Nil NULL#define info(P) (*P).info#define next(P) (P)->next#define 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*/

38/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 elemenpertama 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

39/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:

40/49

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

2. Mampu melakukan operasi insert dan delete berdasarkan value pada list.

II. 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 Nil NULL#define info(P) (*P).info#define next(P) (P)->next#define 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);

41/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 dengannilai 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

42/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. Memahami konsep list dan mampu mengimplementasikannya ke bahasa C.

2. Mampu melakukan operasi insert dan delete berdasarkan value pada list.

43/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 ?

44/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)

45/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:

46/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);

47/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 */

48/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

49/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


Top Related