5/28/2018 Modul Praktikum Struktur Data1
1/68
Modul Praktikum
Struktur Data
Oleh:
M. Fachrurrozi, MT
Comlabs Fakultas Ilmu Komputer
Universitas Sriwijaya
2009
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
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
5/28/2018 Modul Praktikum Struktur Data1
4/68
4
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
5/28/2018 Modul Praktikum Struktur Data1
5/68
5
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/28/2018 Modul Praktikum Struktur Data1
6/68
6
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
5/28/2018 Modul Praktikum Struktur Data1
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.
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
}
5/28/2018 Modul Praktikum Struktur Data1
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 :
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
Prototipe dan Primitif/Algoritma
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:
5/28/2018 Modul Praktikum Struktur Data1
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 */
5/28/2018 Modul Praktikum Struktur Data1
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
Evaluasi dan Pertanyaan
1. Apa yang dimaksud variabel lokal, variabel lokal, called function, callingfunction?
2. Tuliskan algoritma GeserKeSbX dan algoritma GeserKeSbY ?
5/28/2018 Modul Praktikum Struktur Data1
19/68
19
Kesimpulan
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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 :
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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 :
5/28/2018 Modul Praktikum Struktur Data1
25/68
25
List tidak menjadi kosong (masih mengandung elemen) :
Tools yang digunakan
1. PC2. Dev-C++ / Turbo C++ 4.5
Prototipe dan Primitif/Algoritma
/*file : list1.h*/
/*contoh ADT list berkait dengan representasi fisik pointer*//*representasi address dengan pointer*/
/*infotype adalah integer*/
#ifndef list_H#define list_H
#include "boolean.h"
#define Nil NULL#define info(P) (*P).info#define next(P) (P)->next
#define First(L) ((L).First)
#define infotype int
typedef struct tElmtlist *address;typedef struct tElmtlist{
infotype info;address next;
} Elmtlist;
5/28/2018 Modul Praktikum Struktur Data1
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*/
5/28/2018 Modul Praktikum Struktur Data1
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 ?
5/28/2018 Modul Praktikum Struktur Data1
28/68
28
Kesimpulan
5/28/2018 Modul Praktikum Struktur Data1
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.
Tools yang digunakan
1. PC2. Dev-C++ / Turbo C++ 4.5
Prototipe dan Primitif/Algoritma
/*file : list1.h*/
/*contoh ADT list berkait dengan representasi fisik pointer*//*representasi address dengan pointer*/
/*infotype adalah integer*/
#ifndef list_H#define list_H
#include "boolean.h"
#define Nil NULL
#define info(P) (*P).info#define next(P) (P)->next#define First(L) ((L).First)
#define infotype int
typedef struct tElmtlist *address;typedef struct tElmtlist{
infotype info;
5/28/2018 Modul Praktikum Struktur Data1
30/68
30
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 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*/
5/28/2018 Modul Praktikum Struktur Data1
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. 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 Pertanyaan
1. Apa perbedaan operasi list berdasarkan address dengan operasi list berdasarkanvalue ? beri penjelasan ?
2. Sehunbungan dengan pertanyaan 1, bagaimana dengan algoritmanya ?
5/28/2018 Modul Praktikum Struktur Data1
32/68
32
Kesimpulan
5/28/2018 Modul Praktikum Struktur Data1
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.
Tools yang digunakan
1. PC2. Dev-C++ / Turbo C++ 4.5
5/28/2018 Modul Praktikum Struktur Data1
34/68
34
Prototipe dan Primitif/Algoritma
/*file : list1.h*/
/*contoh ADT list berkait dengan representasi fisik pointer*/
/*representasi address dengan pointer*/
/*infotype adalah integer*/
#ifndef list_H#define list_H
#include "boolean.h"
#define Nil NULL#define info(P) (*P).info#define next(P) (P)->next#define First(L) ((L).First)
#define infotype int
typedef struct tElmtlist *address;typedef struct tElmtlist{
infotype info;address next;
} Elmtlist;
/*Definisi list*//*List kosong : First(L) = Nil*//*Setiap elemen dengan address P dapat diacu info(P), Next (P)*//*Elemen terakhir list : jika addressnya Last, maka Next(Last) = Nil*/
typedef struct{
address First;} List;
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);
5/28/2018 Modul Praktikum Struktur Data1
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. 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 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?
5/28/2018 Modul Praktikum Struktur Data1
36/68
36
Kesimpulan
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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 :
5/28/2018 Modul Praktikum Struktur Data1
39/68
39
Tools yang digunakan
1. PC2. Dev-C++ / Turbo C++ 4.5
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 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
5/28/2018 Modul Praktikum Struktur Data1
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.
5/28/2018 Modul Praktikum Struktur Data1
41/68
41
Evaluasi dan Pertanyaan
1. Tulis algoritma Push dan Pop pada stack statis dan dinamis ?2. Sehubungan dengan pertanyaan 1, ada perbedaankah ? beri penjelasan ?Kesimpulan
5/28/2018 Modul Praktikum Struktur Data1
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))
5/28/2018 Modul Praktikum Struktur Data1
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 :
5/28/2018 Modul Praktikum Struktur Data1
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.
Tools yang digunakan
1. PC2. Dev-C++ / Turbo C++ 4.5
Prototipe dan Primitif/Algoritma
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
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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.
Evaluasi dan Pertanyaan
1. Tuliskan algoritma add dan delete pada queue di atas ?2. Buat kesimpulan Anda !
Kesimpulan
5/28/2018 Modul Praktikum Struktur Data1
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:
5/28/2018 Modul Praktikum Struktur Data1
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).
5/28/2018 Modul Praktikum Struktur Data1
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.
Tools yang digunakan
1. PC2. Dev-C++ / Turbo C++ 4.5
5/28/2018 Modul Praktikum Struktur Data1
50/68
50
Prototipe dan Primitif/Algoritma
1. Queue Versi 2
/* Nama file ADTQueue2.h */#ifndef ADTQueue2_H#define ADTQueue2_H#include "boolean.h"#include #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 */
5/28/2018 Modul Praktikum Struktur Data1
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
/* 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 */
5/28/2018 Modul Praktikum Struktur Data1
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.
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
5/28/2018 Modul Praktikum Struktur Data1
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)
5/28/2018 Modul Praktikum Struktur Data1
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:
5/28/2018 Modul Praktikum Struktur Data1
55/68
55
Tools yang digunakan
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;
5/28/2018 Modul Praktikum Struktur Data1
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 */
5/28/2018 Modul Praktikum Struktur Data1
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.
Evaluasi dan Pertanyaan
1. Tuliskan algoritma add dan delete tree di atas ?2. Buat kesimpulan Anda !Kesimpulan
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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.
5/28/2018 Modul Praktikum Struktur Data1
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
5/28/2018 Modul Praktikum Struktur Data1
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.
5/28/2018 Modul Praktikum Struktur Data1
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.
Tools yang digunakan
1. PC2. Dev-C++ / Turbo C++ 4.5
Prototipe dan Primitif/Algoritma
/** 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{
infotype info;address next;
5/28/2018 Modul Praktikum Struktur Data1
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.
Evaluasi dan Pertanyaan
1. Tambahkan proses tambah data di tengah !2. Tambahkan proses hapus data tengah !
5/28/2018 Modul Praktikum Struktur Data1
67/68
67
Kesimpulan
5/28/2018 Modul Praktikum Struktur Data1
68/68