Modul Praktikum Struktur Data1

5/28/2018 Modul Praktikum Struktur Data1

1/68

Modul Praktikum

Struktur Data

Oleh:

M. Fachrurrozi, MT

Comlabs Fakultas Ilmu Komputer

Universitas Sriwijaya

2009


2/68

2

Editor : Ferry Gustiawan

Buku ini diterbitkan dalam rangka pengadaan buku ajar untuk pendidikan di perguruan tinggi

khususnya di lingkungan Fakultas Ilmu Komputer Universitas Sriwijaya.

Hak Cipta pada Comlabs Fakultas Ilmu Komputer Universitas Sriwijaya


3/68

3

Daftar Isi

Daftar Isi.....................................................................................................................................3

Muqaddimah..............................................................................................................................7

1. Pointer dan Array ...................................................................................................................9

Tujuan.....................................................................................................................................9

Dasar teori ..............................................................................................................................9

Tools yang digunakan...........................................................................................................10

Prototipe dan Primitif/Algoritma ..........................................................................................11

Praktik ..................................................................................................................................12

Evaluasi dan Pertanyaan.......................................................................................................12

Kesimpulan...........................................................................................................................12

2. Fungsi dan Prosedur, ADT....................................................................................................13

Tujuan...................................................................................................................................13

Dasar teori ............................................................................................................................13



Praktik ..................................................................................................................................18


Kesimpulan...........................................................................................................................19

3. List (bagian 1).......................................................................................................................20

Tujuan...................................................................................................................................20

Dasar teori ............................................................................................................................20




4/68

4

Praktik ..................................................................................................................................27


Kesimpulan...........................................................................................................................28

4. List (bagian 2).......................................................................................................................29

Tujuan...................................................................................................................................29

Dasar teori ............................................................................................................................29



Praktik ..................................................................................................................................31


Kesimpulan...........................................................................................................................32

5. List (bagian 3).......................................................................................................................33

Tujuan...................................................................................................................................33

Dasar teori ............................................................................................................................33



Praktik ..................................................................................................................................35


Kesimpulan...........................................................................................................................36

6. Stack .....................................................................................................................................37

Tujuan...................................................................................................................................37

Dasar teori ............................................................................................................................37




5/68

5

Praktik ..................................................................................................................................40


Kesimpulan...........................................................................................................................41

7. Queue (bagian 1)...................................................................................................................42

Tujuan...................................................................................................................................42

Dasar teori ............................................................................................................................42



Praktik ..................................................................................................................................46


Kesimpulan...........................................................................................................................46

8. Queue (bagian 2)...................................................................................................................47

Tujuan...................................................................................................................................47

Dasar teori ............................................................................................................................47



Praktik ..................................................................................................................................52


Kesimpulan...........................................................................................................................52

9. Binary Search Tree ................................................................................................................53

Tujuan...................................................................................................................................53

Dasar teori ............................................................................................................................53




6/68

6

Praktik ..................................................................................................................................57


Kesimpulan...........................................................................................................................57

10. Double Linked List..............................................................................................................58

Tujuan...................................................................................................................................58

Dasar teori ............................................................................................................................58



Praktik ..................................................................................................................................66


Kesimpulan...........................................................................................................................67

Referensi...................................................................................................................................68


7/68

7

Muqaddimah

Allah mengangkat derajat orang yang beriman dan orang yang berilmu pengetahuan

beberapa derajat. (Mujaddalah 11)

Abu Hurairah r.a. berkata: Rasulullah SAWbersabda: Barang siapa yang ditanya suatu

ilmu agama lalu menyembunyikannya, maka akan dikendalikan mulutnya pada harikiamat dengan kendali dari api neraka. (Abu Dawud, Attirmidzi)

Tiada akan pernah mampu seseorang dalam mengerjakan sesuatu tanpa pernah

mencobanya terlebih dahulu.


8/68

8

Dari ketiga sumber ilmu inilah penulis ingin berusaha membuat sesuatu yang

bermanfaat bagi orang lain, walaupun masih banyak kekurangan yang terdapat di

dalam buku ini.

Buku praktikum ini merupakan salah satu bahan ajar pendukung untuk mata kuliahStruktur Data. Dari buku ini diharapkan mahasiswa dapat dengan mudah mempelajari,

memahami, dan mempraktikkan materi materi yang telah diajarkan pada kelas teori

mata kuliah Struktur Data. Kemudian buku ini diharapkan dapat menjadi referensi

untuk pemecahan permasalahan umum diluar materi perkuliahan. Sebagian besar isi

dari buku ini merupakan rangkuman dari sumber-sumber yang telah dibuat penulis

lain. Penulis berharap agar buku ini dapat bermanfaat bagi semua kalangan pembaca.

Terima kasih untuk semuanya yang telah memberikan banyak kritik dan saran serta

dukungan dalam penulisan buku ini. Dunia akan selalu indah karena kejujuran dan

kebersamaan.

Palembang, September 2009

Penulis


9/68

9

1. Pointer dan Array

Tujuan

Setelah menyelesaikan modul ini, anda diharapkan dapat :1. Memahami konsep pointer dan array di dalam Bahasa C2. Memahami konsep copy value dan copy address3. Menggunakan pointer dan array di dalam program lainnya

Dasar teori

Pointer

Pointer dapat diartikan sebagai suatu nilai yang menunjuk alamat suatu lokasimemori. Lokasi memori tersebut mungkin diwakili oleh sebuah variabel atau

mungkin juga lokasi bebas dalam memori. Sedangkan pointer sendiri yang berupa

nilai ditampung dalam sebuah variabel yang disebut variabel pointer. Jadi variabel

pointer atau pointer berisi suatu nilai yang menyatakan alamat suatu lokasi.

Contoh :

Step:

1. d=&a*d = 2 ; d = A2. c=&b*c = 3 ; c = B3. b=*d b = 2 ; &b = B4. *d=*c*d = 2 ; d = ADari contoh di atas terlihat bahwa addres pada variabel pointer dapat berubah

ubah, apabila addres suatu variabel pointer berubah maka valuenya akan berubahsesuai addres yang ditunjuk oleh pointer tersebut. Apabila pada address yang

ditunjuk oleh pointer tersebut mengalami perubahan value, maka value pada

pointer juga akan berubah.

2

A

3

B

* *

*

a b*c *d

valu

addre

var


10/68

10

Array satu dimensi

Dalam bahasa pemrograman, array adalah variabel yang sejenis yang berderet

sedemikian rupa sehingga alamatnya saling bersambung/kontigu atau dengan kata

lain variabel berindeks.

Bentuk umum :

Ilustrasi array satu dimensi :

Array di atas mempunyai enam element.

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 multi dimensi :

Array di atas mempunyai delapan belas element.

Tools yang digunakan

1. PC2. Dev-C++ / Turbo C++ 4.5

tipe_array nama_array [jumlah data]

tipe_array nama_array [jumlah data][jumlah


11/68

11

Prototipe dan Primitif/Algoritma

1. Pointer

2. Array Dinamis

2

A

3

B

5

C

**

*

a b c

*d *e

valu

addre

var

1

1

1

1

1

2

2

3 4 5

3 4

2 3

2


12/68

12

Praktik

1. Terjemahkan prototipe/primitif kasus pointer di atas ke dalam bahasa C denganlangkah-langkah :

1. d=&a

2. c=a3. e=&b

4. b=c

5. *d=c

Cetak nilai dan alamat variabel-variabel di atas.

2. Terjemahkan prototipe/primitif kasus array dinamis diatas ke dalam bahasa Cdengan langkah-langkah :

1.

Deklarasikan variable x integer yang dinamis2. Alokasikan jumlah address di x untuk dimensi pertama sebanyak n=53. Tiap-tiap indeks yang ada di dimensi satu, alokasikan jumlah address

sebanyak n-j (j=0..4)

4. Isi value tiap-tiap elemen indeks i,j dengan nilai j+15. Di akhir program, bebaskan semua address yang dipakai oleh x.

Evaluasi dan Pertanyaan

1. Untuk kasus pointer, ketikkan code berikut ;&c = d;

Apa yang terjadi ? alasanya ?

2. Untuk kasus pointer, hapus code &c = d;, ganti dengan kode berikut :d = &c;

Apakah masih error ? alasannya ?

3. Untuk kasus array, bagaimana jika nilai n diubah menjadi n=3?

Kesimpulan


13/68

13

2. Fungsi dan Prosedur, ADT

TujuanSetelah menyelesaikan modul ini, anda diharapkan dapat :1. Memahami fungsi dan prosedur di dalam Bahasa C dan menggunakannya di

dalam konsep ADT.

2. Memahami pembuatan ADT di dalam bahasa C.

Dasar teori

Fungsi

Fungsi adalah sejumlah instruksi yang dikelompokkan menjadi satu, berdiri sendiri,yang berfungsi untuk menyelesaikan suatu pekerjaan. Bahasa C minimal

mempunyai satu buah fungsi yang disebut Fungsi main() yaitu fungsi induk/utama.

Sintaks penulisannya adalah sebagai berikut :

TipeData NamaFungsi()

{

Statement

return variabel

}

Ingat bahwa pemrograman bersifat terstruktur, karena itu untuk fungsi yang dibuat

setelah main, harus dideklarasikan lebih dahulu di bagian atas.

Prosedur

Prosedur adalah suatu fungsi yang tidak mengembalikan nilai, karena itu tipe data

untuk prosedur adalah void atau kosong. Sintaks penulisannya adalah sebagai

berikut :

void NamaProsedur()

{

Statement

}


14/68

14

Ingat bahwa pemrograman bersifat terstruktur, karena itu untuk prosedur yang

dibuat setelah main, harus dideklarasikan lebih dahulu di bagian atas.

Penggunaan Parameter

Ada 2 jenis Parameter Formal Parameter, merupakan parameter yang muncul di definisi fungsi atau

prosedur.

Actual Parameter, merupakan parameter yang muncul di program saatpemanggilan fungsi atau prosedur.

Berikut adalah sintaks untuk penggunaan parameter

TipeData NamaFungsi(TipeData Variabel1, TipeData Variabel2)

{

Statement

return variabel

}

TipeData NamaProsedur(TipeData Variabel1, TipeData Variabel2)

{

Statement

return variabel

}

Abstract Data Type (ADT)

ADT adalah definisi TYPE dan sekumpulan PRIMITIF (operasi dasar) terhadap

TYPE tersebut. Selain itu, dalam sebuah ADT yang lengkap, disertakan pula definisi

invarian dari TYPE dan aksioma yang berlaku. ADT merupakan definisi statik.

Definisi type dari sebuah ADT dapat mengandung sebuah definisi ADT lain.

Misalnya:

ADT Waktu yang terdiri dari ADT JAM dan ADT DATE GARIS yang terdiri dari dua buah POINT SEGI4 yang terdiri dari pasangan dua buah POINT (Top, Left) dan

(Bottom,Right)

Type diterjemahkan menjadi type terdefinisi dalam bahasa yang bersangkutan,

misalnya menjadi record dalam bahasa Ada/Pascal atau struct dalam bahasa C.

Primitif, dalam konteks prosedural, diterjemahkan menjadi fungsiatau prosedur.

Primitif dikelompokkan menjadi :


15/68

15

Konstruktor/Kreator, pembentuk nilai type. Semua objek (variabel) bertype tsbharus melalui konstruktor. Biasanya namanya diawali Make.

Selektor, untuk mengakses komponen type (biasanya namanya diawali denganGet)

Prosedur pengubah nilai komponen (biasanya namanya diawali Get)

Validator komponen type, yang dipakai untuk mentest apakah dapatmembentuktype sesuai dengan batasan

Destruktor/Dealokator, yaitu untuk .menghancurkan. nilai objek (sekaligusmemori penyimpannya)

Baca/Tulis, untuk interface dengan input/output device Operator relational, terhadap type tsb untuk mendefinisikan lebih besar, lebih

kecil, sama dengan, dsb

Aritmatika terhadap type tsb, karena biasanya aritmatika dalam bahasapemrograman hanya terdefinisi untuk bilangan numerik

Konversi dari type tersebut ke type dasar dan sebaliknyaADT biasanya diimplementasi menjadi dua buah modul, yaitu:

Definisi/Spesifikasi Type dan primitif. Spesifikasi type sesuai dengan bahasa yang bersangkutan. Spesifikasi dari primitif sesuai dengan kaidah dalam konteks prosedural,

yaitu:

Fungsi : nama, domain, range dan prekondisi jika ada Prosedur : Initial State, Final State dan Proses yang dilakukan

Body/realisasi dari primitif, berupa kode program dalam bahasa yangbersangkutan. Realisasi fungsi dan prosedur harus sedapat mungkin

memanfaatkan selektor dan konstruktor.

Supaya ADT dapat di-test secara tuntas, maka dalam kuliah ini setiap kali membuat

sebuah ADT, harus disertai dengan sebuah program utama yang dibuat khusus

untuk men-test ADT tsb, yang minimal mengandung pemakaian (call) terhadap

setiap fungsi dan prosedur dengan mencakup semua kasus parameter. Program

utama yang khusus dibuat untuk test ini disebut sebagai driver. Urutan

pemanggilan harus diatursehingga fungsi/prosedur yang memakai fungsi/prosedur

lain harus sudah ditest dandirealisasi terlebih dulu.Realisasi ADT dalam bahasa C, fileheader dengan ekstensi .hdan file kodedengan ekstensi .c.

Dalam modul ADT tidak terkandung definisi variabel. Modul ADT biasanya

dimanfaatkan oleh modul lain, yang akan mendeklarasikan variabel bertype ADT

tsb dalam modulnya. Jadi ADT bertindak sebagai Supplier (penyedia type dan

primitif),sedangkan modul pengguna berperan sebagai Client (pengguna) dari ADT


16/68

16

tsb. Biasanya ada sebuah pengguna yang khusus yang disebut sebagai main

program(program utama) yang memanfaatkan langsung type tsb.

Tools yang digunakan1. PC2. Dev-C++ / Turbo C++ 4.5


1. Fungsi dan Prosedur

Procedure TukarNilai (Input Output: a, b : Integer)

{

temp=a;a=b;

b=temp;

}

2. ADT Point1: /* Nama file point.h */2:3: #ifndef ADTPoint_h4: #define ADTPoint_h5:

6: #include 7: #include 8:9:10: typedef struct11: {12: int x;13: int y;14: } point;15:16: /**===== Konstruktor =====**/17:18: point MakePoint (int x, int y);19: /* Membentuk sebuah POINT dari komponen-komponennya */20:21: /**===== Selektor =====**/22:23: int GetAbsis (point P);24: /* Mengirimkan komponen absis dari P */25:26: int GetOrdinat (point P);27: /* Mengirimkan komponen ordinat dari P */28:


17/68

17

29: void SetAbsis(point *P, int newX);30: /* Mengubah nilai komponen absis dari P */31:32: void SetOrdinat(point *P, int newY);33: /* Mengubah nilai komponen ordinat dari P */34:35: /** Kelompok Interaksi dengan I/O device, BACA/TULIS **/36:37: void BacaPOINT (point *P);38: /* MakePoint (x, y, p) membentuk P dari x dan y yang dibaca */39:40: void TulisPOINT (point P);41: /* Nilai P ditulis ke layar dgn format "(x,y)" */

45: point Plus (point P1, point P2);46: /* Menghasilkan POINT yang bernilai P1+P2 */47:48: point Minus (point P1, point P2);49: /* Menghasilkan POINT yang bernilai P1-P2 */

106: void Geser (point *P, int DeltaX, int DeltaY);107: /* P digeser absisnya sebesar DeltaX dan ordinatnya sebesar DeltaY */108:109: void GeserKeSbX (point *P);110: /* P digeser ke sumbu x */111:112: void GeserKeSbY (point *P);113: /* P digeser ke sumbu y */

1: /* Nama file point.c */2:3:4: #include "point.h"

5: #include 6:7: /**===== Konstruktor =====**/8:9: point MakePoint (int x, int y)10: /* Membentuk sebuah POINT dari komponen-komponennya */11: {12: point P;13: P.x = x;14: P.y = y;15: return P;16: }17:18: /**===== Selektor =====**/19:20: int GetAbsis (point P)21: /* Mengirimkan komponen absis dari P */22: {23: return P.x;24: }25:26: int GetOrdinat (point P)27: /* Mengirimkan komponen ordinat dari P */


18/68

18

28: {29: return P.y;30: }31:32: void SetAbsis(point *P, int newX)33: /* Mengubah nilai komponen absis dari P */34: {35: (*P).x = newX;36: }37:38: void SetOrdinat(point *P, int newY)39: /* Mengubah nilai komponen ordinat dari P */40: {41: (*P).y = newY;42: }43:44: /** Kelompok Interaksi dengan I/O device, BACA/TULIS **/45:46: void BacaPOINT (point *P)47: /* MakePoint (x, y, p) membentuk P dari x dan y yang dibaca */

48: {49: printf("Masukkan absis dari point:");50: scanf("%d", &((*P).x));51: printf("Masukkan ordinat dari point:");52: scanf("%d", &((*P).y));53: MakePoint((*P).x, (*P).y);54: }55:56: void TulisPOINT (point P)57: /* Nilai P ditulis ke layar dgn format "(x,y)" */58: {59: printf("(%d,%d)\n", P.x, P.y);60: }

Praktik

1. Implementasikan fungsi dan prosedur yang belum diimplementasikan2. Buat file drivernya: mpoint.c


1. Apa yang dimaksud variabel lokal, variabel lokal, called function, callingfunction?

2. Tuliskan algoritma GeserKeSbX dan algoritma GeserKeSbY ?


19/68

19

Kesimpulan


20/68

20

3. List (bagian 1)

TujuanSetelah menyelesaikan modul ini, anda diharapkan dapat :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 mengenaielemennya, 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 suatukonstanta 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 : First

alamat elemen berikutnya (suksesor), jika kita mengetahui alamat sebuah

elemen,yang dapat diakses melalui informasi NEXT. NEXT mungkin ada secara

eksplisit (seperti contoh di atas), atau secara implisit yaitu lewat kalkulasi atau

fungsi suksesor. Setiap elemen mempunyai alamat, yaitu tempat elemen disimpan


21/68

21

dapat diacu. Untuk mengacu sebuah elemen, alamat harus terdefinisi. Dengan

alamat tersebut Informasi yang tersimpan pada elemen list dapat diakses elemen

terakhirnya.

Ada berbagai cara untuk mengenali elemen akhir

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

First(L)

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

Info(P)

Next(P)

Beberapa definisi :

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

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

Next(Last) =Nil

INSERT-First

Menambahkan sebuah elemen yang diketahui alamatnya sebagai elemen pertama

list.

Insert elemen pertama, List kosong :


22/68

22

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


23/68

23

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


24/68

24

DELETE-First: menghapus elemen pertama list linier

Elemen yang dihapus dicatat alamatnya :

DELETE-After:Penghapusan suksesor sebuah elemen :

DELETE-Last:

Menghapus elemen terakhir list dapat dilakukan jika alamat dari eemen 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 :


25/68

25

List tidak menjadi kosong (masih mengandung elemen) :


1. PC2. Dev-C++ / Turbo C++ 4.5


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


26/68

26

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

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


27/68

27

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

Praktik

1. Ketik kode program di bawah ini kemudian simpan dengan nama boolean.h

2. Ketik prototipe/primitif di atas dan simpan dengan nama list.h.3. Buat file list.cyang berisi implementasi dari list.h.4. Buat file main driver mlist.c.

Evaluasi dan Pertanyaan1. Tuliskan algoritma untuk nilai maksimum list dan minimum list ?2. Tambahkan program untuk mencetak address max dan address min ?


28/68

28

Kesimpulan


29/68

29

4. List (bagian 2)

TujuanSetelah menyelesaikan modul 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.

Dasar teori

Tidak ada perbedaan dengan teori pada Modul List (bagian 1) sebelumnya hanya

saja pada modul ini proses pada list berdasarkan value.


1. PC2. Dev-C++ / Turbo C++ 4.5


/*file : list1.h*/

/*contoh ADT list berkait dengan representasi fisik pointer*//*representasi address dengan pointer*/




#define Nil NULL

#define info(P) (*P).info#define next(P) (P)->next#define First(L) ((L).First)



infotype info;


30/68

30

address next;} Elmtlist;


typedef struct{


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

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


31/68

31

boolean FSearch(List L, address P);/*mencari apakah ada elemen list yang beralamat P*//*true jika ada*/

address SearchPrec (List L, infotype X, address *Prec);/*mengirimkan address elemen sebelum elemen yang nilainya X*//*mencari apakah ada elemen list dengan info(P) = X*//*jika ada mengirimkan address Prec dengan Next(Prec) = P*/

/*PENGHAPUSAN ELEMEN*/

void DelVFirst(List *L, infotype *X);/*Elemen pertama list dihapus : nilai info disimpan pada X dan alamatelemen pertama*//*di dealokasi*/

void DelVLast (List *L, infotype *X);/*Elemen terakhir list dihapus, nilai info disimpan pada X*/

#endif

Praktik




1. Apa perbedaan operasi list berdasarkan address dengan operasi list berdasarkanvalue ? beri penjelasan ?

2. Sehunbungan dengan pertanyaan 1, bagaimana dengan algoritmanya ?


32/68

32

Kesimpulan


33/68

33

5. List (bagian 3)

TujuanSetelah menyelesaikan modul ini, anda diharapkan dapat :1. Memahami konsep list dan mampu mengimplementasikannya ke bahasa C.2. Mampu melakukan operasi invers, concate, copy dan pecah list.

Dasar teori

Konkatenasi dua buah list linier

Concat : L1 x L2 L{ Menyambung L1 dengan L2 }

Konkatenasi adalah menggabungkan dua list. Dalam contoh berikut list keduadisambungkan ke list pertama. Jadi Last(L1) menjadi predesesor First(l2). Realisasi

algoritmiknya adalah sebuah prosedur sebagai berikut.


1. PC2. Dev-C++ / Turbo C++ 4.5


34/68

34


/*file : list1.h*/

/*contoh ADT list berkait dengan representasi fisik pointer*/

/*representasi address dengan pointer*/




#define Nil NULL#define info(P) (*P).info#define next(P) (P)->next#define First(L) ((L).First)




} Elmtlist;


typedef struct{


infotype Average(List L);/*mengirimkan nilai rata-rata info(P)*/

/*PROSES TERHADAP LIST*/

void DelAll(List *L);/*mendelete semua elemen list dan alamat elemen di-dealokasi*/

void InversList (List *L);/*membalik elemen list, tanpa melakukan alokasi * dealokasi*/

List FInversList (List L);/*mengirimkan list baru hasil invers dari L dengan menyain ssemua elemenL*//*semua elemen yang terlanjur dialokasi, harus didealokasi*/

void CopyList (List *L1, List *L2);


35/68

35

/*L1 dan L2 menunjuk pada list yang sama*/

List FCopyList(List L);/*mengirimkan list yang merupakan salinan L*/

void CpAlokList (List Lin, List *Lout);/*jika semua alokasi berhasil maka Lout harus berisi hasil copy Lin*//*Jika ada alokasi yang gagal, maka Lout = Nil dan semua elemen yangterlanjur*//*dialokasi, didealokasi dengan melakukan alokasi elemen*//*Lout adalah list kosong jika ada alokasi elemen yang gagal*/

void konkat (List L1, List L2, List *L3);/*L3 adalah hasil konkatenasi L1 dan L2*//*Jika ada alokasi yang gagal, semua elemen yang sudah dialokasi harusdidealokasi dan L3 = Nil*/

void konkat1 (List *L1, List *L2, List *L3);/*konkatenasi L1 serta L2 menjadi L3. L1 dan L2 sendiri menjadi listkosong*/

/*tidak ada alokasi / dealokasi pada prosedur ini*/

void PecahList(List *L1, List *L2, List L);/*berdasarkan L, membentuk dua buah list L1 dan L2*//*L1 dan L2 harus di alokasi*//*L1 berisi separuh elemen L dan L2 sisanya*//*Jika elemen L ganjil, maka separuh adalah NbElmt(L) div 2*/

#endif

Praktik




1. Tuliskan algoritma invers list dan copy list ?2. Tambahkan program untuk menyalin semua elemen List L1 yang info-nya

bernilai ganjil, simpan hasilnya di List L2?


36/68

36

Kesimpulan


37/68

37

6. Stack

TujuanSetelah menyelesaikan modul ini, anda diharapkan dapat :1. Memahami konsep stack dan mengimplemetasikannya ke bahasa C.2. Mampu melakukan operasi pop dan push pada stack.

Dasar teori

Stack

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

alamat tempat terjadi operasi, elemen yang ditambahkan paling akhir akan menjadi

elemen yang akan dihapus. Dikatakan bahwa elemen Stack akan tersusun secara

LIFO (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


38/68

38

Perhatikan bahwa dengan definisi semacam ini, representasi tabel sangat tepat

untuk mewakili stack, karena operasi penambahan dan pengurangan hanya

dilakukan di salah satu ujung tabel.

Definisi FungsionalDiberikan S adalah Stack dengan elemen ElmtS, maka definisi fungsional stack

adalah :

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 :


39/68

39


1. PC2. Dev-C++ / Turbo C++ 4.5


1. Stack Statis

/* file : stackt.h *//* 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 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

2. Stack Dinamis/* File: stack.h */

#ifndef stack_h#define stack_h


40/68

40

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

Praktik

1. Buat file boolean.h.2. Ketik prototipe/primitif di atas dan simpan dengan nama stackt.h dan stack.h.3. Buat file .cyang berisi implementasi dari file .h.4. Buat file main driver-nya.


41/68

41


1. Tulis algoritma Push dan Pop pada stack statis dan dinamis ?2. Sehubungan dengan pertanyaan 1, ada perbedaankah ? beri penjelasan ?Kesimpulan


42/68

42

7. Queue (bagian 1)

TujuanSetelah menyelesaikan modul ini, anda diharapkan dapat :1. Memahami konsep Queue dan mengimplementasikannya ke bahasa C.2. Mampu melakukan operasi add dan delete pada queue versi 1.

Dasar teori

Queue (Antrian)

Queue adalah list linier yang :

1. Dikenali elemen pertama (HEAD) dan elemen terakhirnya (TAIL),2. Aturan penyisipan dan penghapusan elemennya didefinisikan sebagai berikut:

- Penyisipan selalu dilakukan setelah elemen terakhir

- Penghapusan selalu dilakukan pada elemen pertama

3. 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 setiap

elemennya adalah

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

dengan InfoType adalah sebuah type terdefinisi yang menentukan informasi yang

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


43/68

43

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.

Alternatif I:

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 :


44/68

44

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, gesersemua 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.


1. PC2. Dev-C++ / Turbo C++ 4.5


1. Queue Versi 1/* Nama file ADTQueue1.h */

#ifndef ADTQueue1_H#define ADTQueue1_H#include "boolean.h"

#include

#define Nil 0

/* Definisi elemen dan address */typedef int infotype;typedef int address; /* Indeks tabel */

typedef struct


45/68

45

{infotype *T; /* Tabel penyimpan elemen */address HEAD; /* Alamat penghapusan */address TAIL; /* Alamat penambahan */int MaxEl; /* Max elemen queue */

} queue;

/** ===== Akses Selektor ===== **/#define Head(Q) (Q).HEAD#define Tail(Q) (Q).TAIL#define InfoHead(Q) (Q).T[(Q).HEAD]#define InfoTail(Q) (Q).T[(Q).TAIL]#define MaxEl(Q) (Q).MaxEl/** ========== **/

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

int NbElmt(queue Q);/* Mengirimkan banyaknya elemen queue. Mengirimkan 0 jika Q kosong *//** ========== **/

/** ===== Kreator ===== **/void CreateEmpty(queue *Q, int MaxEl);/* Melakukan alokasi, membuat sebuah Q kosong *//** ========== **/

/** ===== Destruktor ===== **/

void DeAlokasi(queue *Q);/* Mengembalikan memori Q dan Q menjadi tidak terdefinisi lagi, MaxEl(Q)diset 0 *//** ========== **/

/** ===== Primitif Add/Delete ===== **/

void Add(queue *Q, infotype X);/* Menambahkan X pada Q dengan aturan FIFO *//* precondition: tabel penampung elemen Q tidak penuh */

void Del(queue *Q, infotype *X);/* Menghapus X pada Q dengan aturan FIFO *//* setiap kali menghapus elemen, elemen Head + 1 sampai dengan Tail

digeser/* sehingga Head tetap bernilai 1 untuk Queue tidak kosong *//* precondition: tabel penampung elemen Q tidak kosong *//** ========== **/

#endif


46/68

46

Praktik

1. Buat file boolean.h.2. Ketik prototipe/primitif di atas dan simpan dengan nama ADTQueue1.h.3. Buat file .cyang berisi implementasi dari file .h4. Buat file main driver-nya.


1. Tuliskan algoritma add dan delete pada queue di atas ?2. Buat kesimpulan Anda !

Kesimpulan


47/68

47

8. Queue (bagian 2)

TujuanSetelah menyelesaikan modul ini, anda diharapkan dapat :1. Memahami konsep queue dan mengimplemntasikannya ke bahasa C.2. Mampu melakukan operasi add dan delete pada queue versi 2 dan 3.

Dasar teori

Queue

Alternatif II :

Tabel dengan representasi HEAD dan TAIL, HEAD .bergerak. ketika sebuahelemen dihapus jika Queue tidak kosong. Jika Queue kosong, maka HEAD=0.

Ilustrasi Queue tidak kosong, dengan 5 elemen, kemungkinan pertama HEAD

sedang berada di posisi awal:

Ilustrasi Queue tidak kosong, dengan 5 elemen, kemungkinan pertama HEAD tidak

berada di posisi awal. Hal ini terjadi akibat algoritma penghapusan yang dilakukan

(lihat keterangan)

Ilustrasi Queue kosong:


48/68

48

Algoritma untuk penambahan elemen sama dengan alternatif I: jika masih ada

tempat adalah dengan .memajukan. TAIL. Kasus khusus untuk Queue kosong

karena HEAD harus diset nilainya menjadi 1. Algoritmanya sama denganalternatif I

Algoritma untuk penghapusan elemen jika Queue tidak kosong: ambil nilai elemenHEAD, kemudian HEAD .maju.. Kasus khusus untuk Queue dengan keadaan awal

berelemen 1, yaitu menyesuaikan HEAD dan TAIL dengan DEFINISI. Algoritma ini

TIDAK mencerminkan pergeseran orang yang sedang mengantri di dunia nyata,

tapi efisien. Namun suatu saat terjadi keadaan Queue penuh tetapi .semu sebagai

berikut :

Jika keadaan ini terjadi, haruslah dilakukan aksi menggeser elemen untuk

menciptakan ruangan kosong. Pergeseran hanya dilakukan jika dan hanya jika

TAIL sudah mencapai IndexMax.

Alternatif III :

Tabel dengan representasi HEAD dan TAIL yang berputar mengelilingi indeks tabel

dari awal sampai akhir, kemudian kembali ke awal. Jika Queue kosong, maka

HEAD=0. Representasi ini memungkinkan tidak perlu lagi ada pergeseran yang

harus dilakukan seperti pada alternatif II pada saat penambahan elemen.

Ilustrasi Queue tidak kosong, dengan 5 elemen, dengan HEAD sedang berada di

posisi awal:

Ilustrasi Queue tidak kosong, dengan 5 elemen, dengan HEAD tidak berada diposisi awal, tetapi masih lebih kecil atau sebelum TAIL. Hal ini terjadi akibat

algoritma penghapusan/Penambahan yang dilakukan (lihat keterangan).


49/68

49

Ilustrasi Queue tidak kosong, dengan 5 elemen, HEAD tidak berada di posisi awal,

tetapi lebih besar atau sesudah TAIL. Hal ini terjadi akibat algoritma

penghapusan/Penambahan yang dilakukan (lihat keterangan)

Algoritma untuk penambahan elemen: jika masih ada tempat adalah denganmemajukan TAIL. Tapi jika TAIL sudah mencapai IdxMax, maka suksesor dari

IdxMax adalah 1 sehingga TAIL yang baru adalah 1. Jika TAIL belum mencapai

IdxMax, maka algoritma penambahan elemen sama dengan alternatif II. Kasus

khusus untuk Queue kosong karena HEAD harus diset nilainya menjadi 1.

Algoritma untuk penghapusan elemenjika Queue tidak kosong: ambil nilai elemen

HEAD, kemudian HEAD maju. Penentuan suatu suksesor dari indkes yang

diubah/maju dibuat seperti pada algoritma penambahan elemen: jika HEAD

mencapai IdxMAx, maka suksesor dari HEAD adalah 1. Kasus khusus untuk Queue

dengan keadaan awal berelemen 1, yaitu menyesuaikan HEAD dan TAIL denganDEFINISI. Algoritma ini efisien karena tidak perlu pergeseran, dan seringkali

strategi pemakaian tabel semacam ini disebut sebagai circular buffer, dimana tabel

penyimpan elemen dianggap sebagai buffer. Salah satu variasi dari representasi

pada alternatif III adalah : menggantikan representasi TAIL dengan COUNT, yaitu

banyaknya elemen Queue. Dengan representasi ini, banyaknya elemen diketahui

secara eksplisit, tetapi untuk melakukan penambahan elemen harus dilakukan

kalkulasi TAIL.


1. PC2. Dev-C++ / Turbo C++ 4.5


50/68

50


1. Queue Versi 2

/* Nama file ADTQueue2.h */#ifndef ADTQueue2_H#define ADTQueue2_H#include "boolean.h"#include #define Nil 0


typedef struct{

infotype *T; /* Tabel penyimpan elemen */address HEAD; /* Alamat penghapusan */

address TAIL; /* Alamat penambahan */int MaxEl; /* Max elemen queue */

} queue;

/** ===== Akses Selektor ===== **/#define Head(Q) (Q).HEAD#define Tail(Q) (Q).TAIL#define InfoHead(Q) (Q).T[(Q).HEAD]#define InfoTail(Q) (Q).T[(Q).TAIL]#define MaxEl(Q) (Q).MaxEl

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

int NbElmt(queue Q);/* Mengirimkan banyaknya elemen queue. Mengirimkan 0 jika Q kosong */

/** ===== Kreator ===== **/void CreateEmpty(queue *Q, int MaxEl);/* Melakukan alokasi, membuat sebuah Q kosong */

/** ===== Destruktor ===== **/

void DeAlokasi(queue *Q);/* Mengembalikan memori Q dan Q menjadi tidak terdefinisi lagi, MaxEl(Q)diset 0 */

/** ===== Primitif Add/Delete ===== **/void Add(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 */


51/68

51

void Del(queue *Q, infotype *X);/* Menghapus X pada Q dengan aturan FIFO *//* precondition: tabel penampung elemen Q tidak kosong *//** ========== **/

2. Queue Versi 3/* Nama file ADTQueue3.h */

#ifndef ADTQueue3_H#define ADTQueue3_H

#include "boolean.h"#include #define Nil 0


typedef struct{

infotype *T; /* Tabel penyimpan elemen */address HEAD; /* Alamat penghapusan */address TAIL; /* Alamat penambahan */int MaxEl; /* Max elemen queue */

} queue;

/** ===== Akses Selektor ===== **/#define Head(Q) (Q).HEAD#define Tail(Q) (Q).TAIL#define InfoHead(Q) (Q).T[(Q).HEAD]#define InfoTail(Q) (Q).T[(Q).TAIL]#define MaxEl(Q) (Q).MaxEl/** ========== **/

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

int NbElmt(queue Q);/* Mengirimkan banyaknya elemen queue. Mengirimkan 0 jika Q kosong *//** ========== **/

/** ===== Kreator ===== **/void CreateEmpty(queue *Q, int MaxEl);/* Melakukan alokasi, membuat sebuah Q kosong *//** ========== **/

/** ===== Destruktor ===== **/void DeAlokasi(queue *Q);/* Mengembalikan memori Q dan Q menjadi tidak terdefinisi lagi, MaxEl(Q)diset 0 */


52/68

52

/** ========== **/

/** ===== Primitif Add/Delete ===== **/void Add(queue *Q, infotype X);/* Menambahkan X pada Q dengan aturan FIFO secara sirkuler *//* precondition: tabel penampung elemen Q tidak penuh */

void Del(queue *Q, infotype *X);/* Menghapus X pada Q dengan aturan FIFO secara sirkuler *//* precondition: tabel penampung elemen Q tidak kosong *//** ========== **/

#endif

Praktik

1.

Buat file boolean.h.2. Ketik prototipe/primitif di atas dan simpan dengan nama ADTQueue2.h danADTQueue3.h.

3. Buat file .cyang berisi implementasi dari file .h.4. Buat file main driver-nya.


1. Tuliskan algoritma add dan delete pada queue versi 2 dan 3 ?2. Sehubungan dengan pertanyaan 1, apakah perbedaannya queue versi 1, 2 dan 3 ?

Kesimpulan


53/68

53

9. Binary Search Tree

TujuanSetelah menyelesaikan modul ini, anda diharapkan dapat :1. Memahami konsep binary search tree dan mengimplementasikannya ke bahasa

C.

2. Melakukan operasi add, delete, dan search pada tree.

Dasar teori

Stuktur Pohon Binersebuah pohon biner adalah himpunan terbatas yang

- mungkin kosong, atau

- terdiri dari sebuah simpul yang disebut akar

dan dua buah himpunan lain yang disjoint yang merupakan pohon biner, yang

disebut sebagai sub pohon kiri dan sub pohon kanan dari pohon biner tersebut.

Perhatikanlah perbedaan pohon biner dengan pohon biasa : pohon biner mungkin

kosong, 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/skewedtree)


54/68

54

Sub pohon ditunjukkan dengan penulisan ()

Pohon Seimbang (balanced tree)

Pohon seimbang:

Pohon seimbang tingginya: perbedaan tinggi sub pohon kiri dengan sub pohon

kanan maksimum 1

Pohon seimbang banyaknya simpul: perbedaan banyaknya simpul sub pohon kiridengan 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:


55/68

55


1. PC2. Dev-C++ / Turbo C++ 4.5

Prototipe dan Primitif/Algoritma/* file : bst.h */

#ifndef BST_H_#define BST_H_#include #include #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;


56/68

56

addrTree left;addrTree right;

} ElmtTree;

typedef addrTree BinTree;

BinTree Alokasi(infotype I);/* 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 */


57/68

57

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

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_

Praktik

1. Buat file boolean.h.2. Ketik prototipe/primitif di atas dan simpan dengan nama bst.h.3. Buat file .cyang berisi implementasi dari file .h.4. Buat file main driver-nya.


1. Tuliskan algoritma add dan delete tree di atas ?2. Buat kesimpulan Anda !Kesimpulan


58/68

58

10. Double Linked List

TujuanSetelah menyelesaikan modul ini, anda diharapkan dapat :1. Memahami konsep double linked list dan mampu mengimplementasikannya ke

bahasa C.

2. Mampu melakukan operasi add dan delete pada double linked list.

Dasar teori

Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat

bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian datapada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi

kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini

dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.

Double linked list adalah suatu senarai/list berkait dimana setiap node (elemen)

mempunyai 2 penunjuk yaitu satu penunjuk ke node(elemen) pendahulunya

(predesesor) dan satu penunjuk ke node (elemen) penerusnya (suksesor).

Tambah di awal (addFirst)

Operasi ini berguna untuk menambahkan elemen baru di posisi pertama. Langkah

pertama untuk penambahan data adalah pembuatan elemen baru dan pengisian

nilai infonya. Pointer yang menunjuk ke data tersebut dipanggil dengan nama baru.

Kondisi di setelah ada pembuatan elemen baru tersebut adalah :

Ada 2 kondisi yang harus diperhatikan dalam penambahan data di awal yaitu :

a. Ketika linked list masih kosong


59/68

59

Kalau kondisi linked list masih kosong, maka elemen baru akan menjadi awal dan

akhir linked list.

Perhatikan gambar di bawah ini :

Kondisi sebelum disisipkan

Kondisi setelah operasi penambahanOperasi penambahan awal ketika linked list masih kosong adalah dengan

mengisikan alamat pointer baru ke pointer awal dan pointer akhir. Lihat gambar

di bawah ini.

b. Ketika linked list sudah mempunyai data

Kondisi linked list ketika sudah mempunyai data elemen dan elemen yang baru

telah dibuat, dapat dilihat di gambar di bawah ini.

Proses penambahan data di awal linked list adalah :

Hubungkan barukanan agar menunjuk ke awal

Hubungkan awalkiri agar menunjuk ke posisi pointer baru


60/68

60

Pindahkan pointer awal ke pointer baru

Tambah di akhir (AddLast)

Operasi ini berguna untuk menambahkan elemen baru di posisi akhir. Langkah

pertama untuk penambahan data adalah pembuatan elemen baru dan pengisian

nilai infonya. Pointer yang menunjuk ke data tersebut dipanggil dengan nama baru.

Kondisi di setelah ada pembuatan elemen baru tersebut adalah :

Ada 2 kondisi yang harus diperhatikan dalam penambahan data di akhir yaitu :

a. Ketika linked list masih kosong

Kalau kondisi linked list masih kosong, maka elemen baru akan menjadi awal dan

akhir linked list.

Perhatikan gambar di bawah ini :

Kondisi sebelum penambahan

Kondisi setelah operasi penambahan


61/68

61

Operasi penambahan awal ketika linked list masih kosong adalah dengan

mengisikan alamat pointer baru ke pointer awal dan pointer akhir. Lihat gambar di

bawah ini.

b. Ketika linked list sudah mempunyai data

Kondisi linked list ketika sudah mempunyai data elemen dan elemen yang baru

telah dibuat, dapat dilihat di gambar di bawah ini.

Proses penambahan data di akhir linked list adalah :

Hubungkan akhirkanan agar menunjuk ke pointer baru

Hubungkan barukiri agar menunjuk ke posisi pointer akhir

Pindahkan pointer akhir ke pointer baru


62/68

62

Hapus data awal (DeleteFisrt)

Operasi ini berguna untuk menghapus data pada posisi pertama. Ada 3 keadaanyang mungkin terjadi ketika akan melakukan proses hapus yaitu :

a. Kondisi linked list masih kosong

Jika kondisi ini terjadi, maka proses penghapusan data tidak bisa dilakukan karena

linked list masih kosong.

b. Kondisi linked list hanya memiliki 1 data

Langkah yang perlu dilakukan ketika ingin melakukan proses penghapusan linked

list yang memiliki hanya 1 data adalah dengan langsung menghapus data dari

memori dan kemudian pointer awal dan akhir di-NULL-kan. Untuk lebih jelas

perhatikan urutan penghapusannya di bawah ini :

Kondisi data sebelum dihapus

Proses penghapusan yaitu dengan menghilangkan data dari memori denganperintah free(awal) atau free(akhir).

Kemudian pointer awal dan akhir diisi dengan NULL.

c. Kondisi linked list memiliki data lebih dari 1 buah

Untuk operasi penghapusan data di posisi pertama pada double linked list yang

mempunyai data lebih dari 1 buah adalah :

Simpan pointer yang akan dihapus (awal) ke suatu pointer lain yang diberi namapointer bantu.


63/68

63

Pindahkan pointer awal ke data berikutnya (bantu

kanan atau awal

kanan).

Field kiri dari awal yang baru (awal kiri) di-NULL-kan.

Langkah terakhir adalah hapus elemen yang ditunjuk pointer bantu.

Setelah data dihapus, maka kondisi linked list adalah seperti di gambar dibawah ini.

Hapus data terakhir

Operasi ini berguna untuk menghapus data pada posisi terakhir. Ada 3 keadaanyang mungkin terjadi ketika akan melakukan proses hapus yaitu :

a. Kondisi linked list masih kosong

Jika kondisi ini terjadi, maka proses penghapusan data tidak bisa dilakukan karena

linked list masih kosong.

b. Kondisi linked list hanya memiliki 1 data


64/68

64

Langkah yang perlu dilakukan ketika ingin melakukan proses penghapusan linked

list yang memiliki hanya 1 data adalah dengan langsung menghapus data dari

memori dan kemudian pointer awal dan akhir di-NULL-kan. Untuk lebih jelas

perhatikan urutan penghapusannya di bawah ini :

Kondisi data sebelum dihapus

Proses penghapusan yaitu dengan menghilangkan data dari memori denganperintah free(awal) atau free(akhir).

Kemudian pointer awal dan akhir diisi dengan NULL.

c. Kondisi linked list memiliki data lebih dari 1 buah

Untuk operasi penghapusan data di posisi terakhir pada double linked list yang

mempunyai data lebih dari 1 buah adalah : Simpan pointer yang akan dihapus (akhir) ke suatu pointer lain yang diberi

nama pointer bantu.

Pindahkan pointer akhir ke data sebelumnya (bantukiri atau akhirkiri).

Field kanan dari akhir baru (akhir kanan) di-NULL-kan.


65/68

65

Langkah terakhir adalah hapus elemen yang ditunjuk pointer bantu.

Setelah data dihapus, maka kondisi linked list adalah seperti di gambar dibawah ini.


1. PC2. Dev-C++ / Turbo C++ 4.5


/** filename: DoubleLinkList.h **/

#ifndef DoubleLinkList_H#define DoubleLinkList_H

#include #include "boolean.h"#define Nil NULL#define Info(P) (P)->info

#define Next(P) (P)->next#define Prev(P) (P)->prev#define First(L) ((L).First)

typedef int infotype;typedef struct telmtlist *address;typedef struct telmtlist{



66/68

66

address prev;}ElmtList;

typedef struct{

address First;}List;

boolean ListEmpty(List L);/* Mengirim TRUE jika list kosong */

void CreateList(List *L);/* Membentuk sebuah list kosong */

address Alokasi(infotype X);/* Menghasilkan address alokasi sebuah elemen */

void Dealokasi(address P);/* Melakukan dealokasi/pengembalian address P */

address Search(List L, infotype X);/* Menghasilkan address yang mengandung infotype X, jika tidak adamenghasilkan Nil */

void AddFirst(List *L, infotype X);/* Menambahkan elemen X pada elemen pertama List */

void AddLast(List *L, infotype X);/* Menambahkan elemen X pada elemen terakhir List */

void DelFirst(List *L, infotype *X);/* Menghapus elemen pertama List */

void DelLast(List *L, infotype *X);/* Menghapus elemen terakhir List */

#endif

Praktik

1. Buat file boolean.h.2. Ketik prototipe/primitif di atas dan simpan dengan nama DoubleLinkList.h.3. Buat file .cyang berisi implementasi dari file .h.4. Buat file main driver-nya.


1. Tambahkan proses tambah data di tengah !2. Tambahkan proses hapus data tengah !


67/68

67

Kesimpulan


68/68

Documents

Modul Praktikum Struktur Data1