Modul Praktikum. Struktur Data. Oleh: M. Fachrurrozi, MT. Comlabs Fakultas Ilmu Komputer. Universitas Sriwijaya

Modul Praktikum

Struktur Data

Oleh: M. Fachrurrozi, MT

Comlabs Fakultas Ilmu Komputer Universitas Sriwijaya 2009

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

2

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 Tools yang digunakan...........................................................................................................16 Prototipe dan Primitif/Algoritma ..........................................................................................16 Praktik ..................................................................................................................................18 Evaluasi dan Pertanyaan.......................................................................................................18 Kesimpulan...........................................................................................................................19 3. List (bagian 1) .......................................................................................................................20 Tujuan...................................................................................................................................20 Dasar teori ............................................................................................................................20 Tools yang digunakan...........................................................................................................25 Prototipe dan Primitif/Algoritma ..........................................................................................25 3

Praktik ..................................................................................................................................27 Evaluasi dan Pertanyaan.......................................................................................................27 Kesimpulan...........................................................................................................................28 4. List (bagian 2) .......................................................................................................................29 Tujuan...................................................................................................................................29 Dasar teori ............................................................................................................................29 Tools yang digunakan...........................................................................................................29 Prototipe dan Primitif/Algoritma ..........................................................................................29 Praktik ..................................................................................................................................31 Evaluasi dan Pertanyaan.......................................................................................................31 Kesimpulan...........................................................................................................................32 5. List (bagian 3) .......................................................................................................................33 Tujuan...................................................................................................................................33 Dasar teori ............................................................................................................................33 Tools yang digunakan...........................................................................................................33 Prototipe dan Primitif/Algoritma ..........................................................................................34 Praktik ..................................................................................................................................35 Evaluasi dan Pertanyaan.......................................................................................................35 Kesimpulan...........................................................................................................................36 6. Stack .....................................................................................................................................37 Tujuan...................................................................................................................................37 Dasar teori ............................................................................................................................37 Tools yang digunakan...........................................................................................................39 Prototipe dan Primitif/Algoritma ..........................................................................................39 4

Praktik ..................................................................................................................................40 Evaluasi dan Pertanyaan.......................................................................................................41 Kesimpulan...........................................................................................................................41 7. Queue (bagian 1)...................................................................................................................42 Tujuan...................................................................................................................................42 Dasar teori ............................................................................................................................42 Tools yang digunakan...........................................................................................................44 Prototipe dan Primitif/Algoritma ..........................................................................................44 Praktik ..................................................................................................................................46 Evaluasi dan Pertanyaan.......................................................................................................46 Kesimpulan...........................................................................................................................46 8. Queue (bagian 2)...................................................................................................................47 Tujuan...................................................................................................................................47 Dasar teori ............................................................................................................................47 Tools yang digunakan...........................................................................................................49 Prototipe dan Primitif/Algoritma ..........................................................................................50 Praktik ..................................................................................................................................52 Evaluasi dan Pertanyaan.......................................................................................................52 Kesimpulan...........................................................................................................................52 9. Binary Search Tree ................................................................................................................53 Tujuan...................................................................................................................................53 Dasar teori ............................................................................................................................53 Tools yang digunakan...........................................................................................................55 Prototipe dan Primitif/Algoritma ..........................................................................................55 5

Praktik ..................................................................................................................................57 Evaluasi dan Pertanyaan.......................................................................................................57 Kesimpulan...........................................................................................................................57 10. Double Linked List..............................................................................................................58 Tujuan...................................................................................................................................58 Dasar teori ............................................................................................................................58 Tools yang digunakan...........................................................................................................65 Prototipe dan Primitif/Algoritma ..........................................................................................65 Praktik ..................................................................................................................................66 Evaluasi dan Pertanyaan.......................................................................................................66 Kesimpulan...........................................................................................................................67 Referensi...................................................................................................................................68

6

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 hari kiamat dengan kendali dari api neraka”. (Abu Dawud, Attirmidzi)

“Tiada akan pernah mampu seseorang dalam mengerjakan sesuatu tanpa pernah mencobanya terlebih dahulu”.

7

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 kuliah Struktur 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

8

1. Pointer dan Array Tujuan Setelah menyelesaikan modul 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

Dasar teori Pointer Pointer dapat diartikan sebagai suatu nilai yang menunjuk alamat suatu lokasi memori. 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 : a

*c

b

*d

var

2

*

3

*

A

*

B

*

valu e

addres

Step: 1. 2. 3. 4.

d=&a à *d = 2 ; d = A c=&b à *c = 3 ; c = B b=*d à b = 2 ; &b = B *d=*cà *d = 2 ; d = A

Dari contoh di atas terlihat bahwa addres pada variabel pointer dapat berubah – ubah, apabila addres suatu variabel pointer berubah maka valuenya akan berubah sesuai addres yang ditunjuk oleh pointer tersebut. Apabila pada address yang ditunjuk oleh pointer tersebut mengalami perubahan value, maka value pada pointer juga akan berubah.

9

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 : tipe_array nama_array [jumlah data]

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 : tipe_array nama_array [jumlah data][jumlah data]

Ilustrasi array multi dimensi :

Array di atas mempunyai delapan belas element.

Tools yang digunakan 1. PC 2. Dev-C++ / Turbo C++ 4.5

10

Prototipe dan Primitif/Algoritma 1. Pointer

a

b

c

2

3

5

A

B

C

*d

*e

*

*

*

* var

valu e

addres

2. Array Dinamis

1

2

3

4

1

2

3

4

1

2

3

1

2

5

1

11

Praktik 1. Terjemahkan prototipe/primitif kasus pointer di atas ke dalam bahasa C dengan langkah-langkah : 1. d=&a 2. c=a 3. 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 C dengan langkah-langkah : 1. Deklarasikan variable x integer yang dinamis 2. Alokasikan jumlah address di x untuk dimensi pertama sebanyak n=5 3. 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+1 5. 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

12

2. Fungsi dan Prosedur, ADT Tujuan Setelah 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 }

13

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 saat pemanggilan 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 fungsi atau prosedur. Primitif dikelompokkan menjadi : 14

• • • • • • •

• •

Konstruktor/Kreator, pembentuk nilai type. Semua objek (variabel) bertype tsb harus melalui konstruktor. Biasanya namanya diawali Make. Selektor, untuk mengakses komponen type (biasanya namanya diawali dengan Get) Prosedur pengubah nilai komponen (biasanya namanya diawali Get) Validator komponen type, yang dipakai untuk mentest apakah dapat membentuk type sesuai dengan batasan Destruktor/Dealokator, yaitu untuk .menghancurkan. nilai objek (sekaligus memori 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 bahasa pemrograman hanya terdefinisi untuk bilangan numerik Konversi dari type tersebut ke type dasar dan sebaliknya

ADT 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 yang bersangkutan. 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 diatur sehingga fungsi/prosedur yang memakai fungsi/prosedur lain harus sudah ditest dan direalisasi terlebih dulu. Realisasi ADT dalam bahasa C, file header dengan ekstensi .h dan file kode dengan 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

15

tsb. Biasanya ada sebuah pengguna yang khusus yang disebut sebagai main program (program utama) yang memanfaatkan langsung type tsb.


Prototipe dan Primitif/Algoritma 1. Fungsi dan Prosedur Procedure TukarNilai (Input Output: a, b : Integer) { temp=a; a=b; b=temp; } 2. ADT Point 1: /* Nama file point.h */ 2: 3: #ifndef ADTPoint_h 4: #define ADTPoint_h 5: 6: #include <stdio.h> 7: #include <math.h> 8: 9: 10: typedef struct 11: { 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:

16

29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41:

void SetAbsis(point *P, int newX); /* Mengubah nilai komponen absis dari P */

45: 46: 47: 48: 49:

point Plus (point P1, point P2); /* Menghasilkan POINT yang bernilai P1+P2 */

void SetOrdinat(point *P, int newY); /* Mengubah nilai komponen ordinat dari P */ /** Kelompok Interaksi dengan I/O device, BACA/TULIS **/ void BacaPOINT (point *P); /* MakePoint (x, y, p) membentuk P dari x dan y yang dibaca */ void TulisPOINT (point P); /* Nilai P ditulis ke layar dgn format "(x,y)" */

point Minus (point P1, point P2); /* Menghasilkan POINT yang bernilai P1-P2 */

106: 107: 108: 109: 110: 111: 112: 113:

void Geser (point *P, int DeltaX, int DeltaY); /* P digeser absisnya sebesar DeltaX dan ordinatnya sebesar DeltaY */ void GeserKeSbX (point *P); /* P digeser ke sumbu x */ void GeserKeSbY (point *P); /* P digeser ke sumbu y */

1: /* Nama file point.c */ 2: 3: 4: #include "point.h" 5: #include <math.h> 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 */

17

28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60:

{ return P.y; } void SetAbsis(point *P, int newX) /* Mengubah nilai komponen absis dari P */ { (*P).x = newX; } void SetOrdinat(point *P, int newY) /* Mengubah nilai komponen ordinat dari P */ { (*P).y = newY; } /** Kelompok Interaksi dengan I/O device, BACA/TULIS **/ void BacaPOINT (point *P) /* MakePoint (x, y, p) membentuk P dari x dan y yang dibaca */ { printf("Masukkan absis dari point:"); scanf("%d", &((*P).x)); printf("Masukkan ordinat dari point:"); scanf("%d", &((*P).y)); MakePoint((*P).x, (*P).y); } void TulisPOINT (point P) /* Nilai P ditulis ke layar dgn format "(x,y)" */ { printf("(%d,%d)\n", P.x, P.y); }

Praktik 1. Implementasikan fungsi dan prosedur yang belum diimplementasikan 2. Buat file drivernya: mpoint.c

Evaluasi dan Pertanyaan 1. Apa yang dimaksud variabel lokal, variabel lokal, called function, calling function? 2. Tuliskan algoritma GeserKeSbX dan algoritma GeserKeSbY ?

18

Kesimpulan

19

3. List (bagian 1) Tujuan Setelah 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 mengenai elemennya, dan informasi mengenai alamat elemen suksesornya : type ElmtList : dengan InfoType adalah sebuah type terdefinisi yang menyimpan informasi sebuah elemen list; Next adalah address ("alamat") dari elemen berikutnya (suksesor). Dengan demikian, jika didefinisikan First adalah alamat elemen pertama list, maka elemen berikutnya dapat diakses secara suksesif dari field Next elemen tersebut Alamat yang sudah didefinisikan disebut sudah di-alokasi. Didefinisikan suatu konstanta Nil, yang artinya alamat yang tidak terdefinisi. Alamat ini nantinya akan didefinisikan secara lebih konkret ketika list linier diimplementasi pada struktur data fisik

Jadi, sebuah list linier dikenali : elemen pertamanya, biasanya melalui alamat elemen pertama yang disebut : 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 20

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 :

21

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

22

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

23

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 :

24

List tidak menjadi kosong (masih mengandung elemen) :


Prototipe dan Primitif/Algoritma /*file : list1.h*/ /*contoh ADT list berkait dengan representasi fisik pointer*/ /*representasi address dengan pointer*/ /*infotype adalah integer*/ #ifndef list_H #define list_H #include "boolean.h" #define #define #define #define

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

#define infotype int typedef struct tElmtlist *address; typedef struct tElmtlist { infotype info; address next; } Elmtlist;

25

/*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 elemen pertama yang lama*/ void DelP(List *L, infotype X); /*jika ada elemen list beraddress P, dengan info(P) = X*/ /*maka P dihapus dari list dan didealokasi*/

26

/*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.c yang berisi implementasi dari list.h. 4. Buat file main driver mlist.c.

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

27

Kesimpulan

28

4. List (bagian 2) Tujuan Setelah 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.




#define infotype int typedef struct tElmtlist *address; typedef struct tElmtlist { infotype info;

29

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); /*jika ada elemen list beraddress P, dengan info(P) = X*/ /*maka P dihapus dari list dan didealokasi*/ /*jika tak ada, maka list tetap*/ void DelLast (List *L, address *P); /*P adalah alamat elemen terakhir list sebelum penghapusan*/ /*Last Elemen yang baru adalah predesesor elemen pertama yang lama*/ void DelAfter(List *L, address *Pdel, address Prec); /*Prec adalah anggota list*/ /*menghapus Next (Prec)*/ int NbElmt(List L); /*mengirimkan banyaknya elemen list, 0 bila list kosong*/ infotype Max(List L); /*mengirimkan nilai info(P) yang maksimum*/ infotype Min(List L); /*mengirimkan nilai info(P) yang minimum*/ /*PRIMITIF BERDASARKAN NILAI*/ void InsVFirst (List *L, infotype X); /*melakukan alokasi sebuah elemen, dan menambahkan elemen pertama dengan nilai X*/ /*bila alokasi berhasil*/ void InsVLast (List *L, infotype X); /*menambahkan elemen list di akhir, elemen terakhir yang baru*/ /*PENCARIAN SEBUAH ELEMEN LIST*/ address Search (List L, infotype X); /*mencari apakah ada elemen list dengan info(P) = X*/ /*Jika ada, kirimkan address. Jika tak ada kirimkan Nil*/

30

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 alamat elemen pertama*/ /*di dealokasi*/ void DelVLast (List *L, infotype *X); /*Elemen terakhir list dihapus, nilai info disimpan pada X*/ #endif



Evaluasi dan Pertanyaan 1. Apa perbedaan operasi list berdasarkan address dengan operasi list berdasarkan

value ? beri penjelasan ? 2. Sehunbungan dengan pertanyaan 1, bagaimana dengan algoritmanya ?

31

Kesimpulan

32

5. List (bagian 3) Tujuan Setelah 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 kedua disambungkan ke list pertama. Jadi Last(L1) menjadi predesesor First(l2). Realisasi algoritmiknya adalah sebuah prosedur sebagai berikut.


33



#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; 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 elemen L*/ /*semua elemen yang terlanjur dialokasi, harus didealokasi*/ void CopyList (List *L1, List *L2);

34

/*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 yang terlanjur*/ /*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 harus didealokasi dan L3 = Nil*/ void konkat1 (List *L1, List *L2, List *L3); /*konkatenasi L1 serta L2 menjadi L3. L1 dan L2 sendiri menjadi list kosong*/ /*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



Evaluasi dan Pertanyaan 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? 35

Kesimpulan

36

6. Stack Tujuan Setelah 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

37

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 Fungsional Diberikan 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 :

38


Prototipe dan Primitif/Algoritma 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 kosong boolean IsEmpty(Stackt *S); //mengirim true jika penampung sudah penuh boolean IsFull(Stackt *S); //menambahkan elemen ke stack void Push(Stackt *S, infotype X); //menghapus sebuah elemen stack void Pop(Stackt *S); #endif

2. Stack Dinamis /* File: stack.h */ #ifndef stack_h #define stack_h

39

#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. 2. 3. 4.

Buat file boolean.h. Ketik prototipe/primitif di atas dan simpan dengan nama stackt.h dan stack.h. Buat file .c yang berisi implementasi dari file .h. Buat file main driver-nya. 40

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

Kesimpulan

41

7. Queue (bagian 1) Tujuan Setelah 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))

42

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 :

43

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.


Prototipe dan Primitif/Algoritma 1. Queue Versi 1 /* Nama file ADTQueue1.h */ #ifndef ADTQueue1_H #define ADTQueue1_H #include "boolean.h" #include <stdlib.h> #define Nil 0 /* Definisi elemen dan address */ typedef int infotype; typedef int address; /* Indeks tabel */ typedef struct

44

{ 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

45

Praktik 1. 2. 3. 4.

Buat file boolean.h. Ketik prototipe/primitif di atas dan simpan dengan nama ADTQueue1.h. Buat file .c yang berisi implementasi dari file .h Buat file main driver-nya.

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

Kesimpulan

46

8. Queue (bagian 2) Tujuan Setelah 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 sebuah elemen 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:

47

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 elemen HEAD, 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 di posisi awal, tetapi masih lebih kecil atau sebelum TAIL. Hal ini terjadi akibat algoritma penghapusan/Penambahan yang dilakukan (lihat keterangan).

48

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 dengan memajukan 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 elemen jika 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 dengan DEFINISI. 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.


49

Prototipe dan Primitif/Algoritma 1. Queue Versi 2 /* Nama file ADTQueue2.h */ #ifndef ADTQueue2_H #define ADTQueue2_H #include "boolean.h" #include <stdlib.h> #define Nil 0 /* Definisi elemen dan address */ typedef int infotype; typedef int address; /* Indeks tabel */ 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 */

50

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 <stdlib.h> #define Nil 0 /* Definisi elemen dan address */ typedef int infotype; typedef int address; /* Indeks tabel */ 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 */

51

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

/** ===== 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 dan ADTQueue3.h. 3. Buat file .c yang berisi implementasi dari file .h. 4. Buat file main driver-nya.

Evaluasi dan Pertanyaan 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

52

9. Binary Search Tree Tujuan Setelah 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 Biner sebuah 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/skewed tree)

53

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

54


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;

55

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

56

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. 2. 3. 4.

Buat file boolean.h. Ketik prototipe/primitif di atas dan simpan dengan nama bst.h. Buat file .c yang berisi implementasi dari file .h. Buat file main driver-nya.

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

Kesimpulan

57

10. Double Linked List Tujuan Setelah 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 data pada 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 58

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 penambahan 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 awal linked list adalah : • Hubungkan baru à kanan agar menunjuk ke awal

•

Hubungkan awal à kiri agar menunjuk ke posisi pointer baru

59

•

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 60

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 akhir à kanan agar menunjuk ke pointer baru

•

Hubungkan baruà kiri agar menunjuk ke posisi pointer akhir

•

Pindahkan pointer akhir ke pointer baru

61

Hapus data awal (DeleteFisrt) Operasi ini berguna untuk menghapus data pada posisi pertama. Ada 3 keadaan yang 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 dengan perintah 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 nama pointer bantu.

62

•

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 di bawah ini.

Hapus data terakhir Operasi ini berguna untuk menghapus data pada posisi terakhir. Ada 3 keadaan yang 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

63

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 dengan perintah 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 (bantu à kiri atau akhir àkiri).

•

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

64

•

Langkah terakhir adalah hapus elemen yang ditunjuk pointer bantu.

•

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


Prototipe dan Primitif/Algoritma /** filename: DoubleLinkList.h **/ #ifndef DoubleLinkList_H #define DoubleLinkList_H #include <stdlib.h> #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 { infotype info; address next;

65

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 ada menghasilkan 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. 2. 3. 4.

Buat file boolean.h. Ketik prototipe/primitif di atas dan simpan dengan nama DoubleLinkList.h. Buat file .c yang berisi implementasi dari file .h. Buat file main driver-nya.

Evaluasi dan Pertanyaan 1. Tambahkan proses tambah data di tengah ! 2. Tambahkan proses hapus data tengah !

66

Kesimpulan

67

Referensi 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

68

Modul Praktikum. Struktur Data. Oleh: M. Fachrurrozi, MT. Comlabs Fakultas Ilmu Komputer. Universitas Sriwijaya

Recommend Documents