FIFO (First In First Out)

FIFO (First In First Out)

FIFO adalah suatu metoda pembuatan Linked List dimana data yang masuk paling awal adalah data yang keluar paling awal juga. Hal ini dapat dianalogikan (dalam kehidupan sehari-hari) misalkan saat sekelompok orang yang datang (ENQUEUE) mengantri hendak membeli tiket di loket.
Jika Linked List dibuat dengan metode FIFO, maka terjadi penambahan/Insert simpul di depan.

PROCEDURE INSERT








Head
Penggalan procedure INSERT untuk FIFO


{head mula-mula selalu diidentifikasikan sebagai nil}











Now Head Tail





Now
Head Tail























Now

Head Tail




Head Tail Now







Head Now Tail





Head Now Tail






Head Now Tail






Procedure dan Function Linked List Lainnya
Selain procedure insert di atas, pada linked list juhga terdapat procedure serta function lainnya.
Di bawah ini diberikan procedure-procedure serta function umum dalam aplikasi Linked List.
 Create : Membuat sebuah linked list yang baru dan masih kososng. (ket: procedure ini wajib dilakukan sebelum menggunakan linked list)






Head Tail





 Empty : Function untuk menentukan apakah linked list kosong atau tidak.






 Find First : Mencari elemen pertama dari linked list



Head Now Tail



 Find Next : Mencari elemen sesudah elemen yang ditunjuk now.




Head Now Tail


(ket: gambar lanjutan dari sebelumnya)
 Retrieve : Mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu ditampung pada suatu variabel (di bawah dicontohkan variabel r).




 Update : Mengubah elemen yang ditunjuk oleh now dengan isi dari suatu variabel (di bawah dicontohkan variabel u).




Head Now Tail


 Delete Now : Menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list(head), maka head akan berpindah ke elemen berikut.














Head x Now Tail









Head x Now Tail



 Delete Head : Menghapus elemen yang ditunjuj head. Head berpindah ke elemen sesudahnya.



















Now Head Tail








Head Now Tail






 Clear : Untuk menghapus linked list yang sudah ada.wajib dilakukan bila ingin mengakhiri program yang menggunakan linked list. Jika tidak data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.













Latihan Soal beserta jawaban (Listing Program) dan penjelasan
Buatlah sebuah program untuk mendeteksi password/ kata sandi. Gunakan metode single linked list. Jika passwordnya benar, program akan selesai, jika salah maka user akan diminta memasukkan password kembali. (passw.pas)


Jawaban :
Uses crt;
Type
Point = ^Rec;
Rec = record
Isi : char;
Next : point;
End;
Const
Password = ‘pascal’; {password yang harus dimasukkan}
Var
i : byte;
Tekan : char;
Passwd : Boolean;
Head, Tail, Now : Point;


Procedure Create;
Begin
Head:=nil;
Tail:=nil;
End;
Procedure Push(isi:char);
Var Now:point;
Begin
New(now); {membuat simpul baru}
If Head=Nil then {mendeteksi simpul awal}
Begin
Head:=Now;
Tail:=Head;
end else
begin {menyambung simpul yang baru pada simpul yang sudah ada}
Tail^.next:=Now;
Tail:=Tail^.Next;
end;
Now^.isi:=isi; {mengisi simpul yang baru}
Now^.next:=Nil;
end;
Function Check:Boolean; {function untuk mencheck input}
Var Temp : string[15];
Begin
Temp:=’ ‘; Now:=Head;
While Now <> nil do
Begin
Temp:=temp + Now^.isi;
Now:=Now^.next;
End;
If temp <> Password then check:=False;
End;
Procedure BuatBingkai(x1,y1,x2,y2:byte); {tampilan aplikasi}
Var i : byte;
Begin
GotoXY (x1,y1); write(‘ ’); GotoXY (x2,y1); write (‘ ‘);
GotoXY (x1,y2); write(‘ ’); GotoXY (x2,y2); write (‘ ’);
For i := x1+1 to x2-1 do
Begin
GotoXY (i,y1); write (‘-‘);
GotoXY (i,y2); write (‘-’);
End;
For i := y1+1 to y2-1 do
Begin
GotoXY(x1, i); write(‘ ‘);
GotoXY(x2, i); write (‘ ‘);
End;
End;

Procedure Pop; {procedure penghapus simpul}
Begin
Now:=head;
head:=head^.next;
While Now <> nil do
Begin
Dispose(Now);
Now:=head;
Head:=head^.next;
End;
End;
Begin {program utama}
Repeat
Create; I:=0;
Repeat
Tekan:=ReadKey;
Write(Tekan);
If Tekan <>#13 then Push(Tekan); inc(i);
Until (Tekan= #13) or (I=10); {enter ditekan atau panjang = 10}
Passwd:=check; Pop;
Until Passwd;
End.
















MODUL 9
TREE

Tree
Merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :
a) Prodecessor : node yang berada diatas node tertentu.
b) Successor : node yang berada di bawah node tertentu.
c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
e) Parent : predecssor satu level di atas suatu node.
f) Child : successor satu level di bawah suatu node.
g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.
h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
i) Size : banyaknya node dalam suatu tree.
j) Height : banyaknya tingkatan/level dalam suatu tree.
k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
l) Leaf : node-node dalam tree yang tak memiliki seccessor.
m) Degree : banyaknya child yang dimiliki suatu node.
Contoh :












Beberapa jenis Tree yang memiliki sifat khusus :
1) Binary Tree
Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.














Jenis-jenis Binary Tree :
a) Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.








b) Complete Binary Tree
Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.






c) Skewed Binary Tree
akni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.





Implementasi Binary Tree
Binary Tree dapat diimplemntasikan dalam Pascal dengan menggunakan double Linked List. Untuk nodenya, bisa dideklarasikan sbb :
Type Tree = ^node;
Node = record
Isi : TipeData;
Left,Right : Tree;
end;
Contoh ilustrasi Tree yang disusun dengan double linked list :





(Ket: LC=Left Child; RC=Right Child)
Operasi-operasi pada Binary Tree :
 Create : Membentuk binary tree baru yang masih kosong.
 Clear : Mengosongkan binary tree yang sudah ada.
 Empty : Function untuk memeriksa apakah binary tree masih kosong.
 Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.
 Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)
 Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)
 Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)
 DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.
 Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)
 Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order.


Langkah-Langkahnya Traverse :
 PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.
 InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.
 PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi.

Untuk lebih jelasnya perhatikan contoh operasi-operasi pada Binary Tree berikut ini :


Memasukkan sebuah node ke dalam Tree yang masih kosong (Sebagai Tree)



Menambahkan sebuah node sebagai right child dari Root.




Menambahkan sebuah node sebagai left child dari node yang sebelunya di-insert.





Memindahkan pointer ke Root kemudian menambhakan sebuah node sebagai left child dari root.





Menambhakan sebuah node sebagai left child dari node yang sebelumnya di-insert.




Memindahkan pointer ke Root, kemudian pindahkan lagi pointer ke right child dari Root, kemudian masukkan sebuah node sebagai right child dari node yang sedang ditunjuk oleh pointer.



2) Binary search Tree
Adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree. Contoh binary search tree umum :








Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi insert, update, dan delete.
1. Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat. (Lokasi tidak ditentukan oleh user sendiri).


Memasukkan sebuah node yang berisi angka 12. Karena tree masih kosong, maka secara otomatis node tersebut menjadi root.



Karena 15 lebih besar dari 12, maka sesuai dengan peraturan harus berada disebelah kanan parent (right child)




Karena 13 lebih besar dari 12, maka sesuai dengan peraturan harus berada di sebelah kanan parent (12), lalu bandingkan lagi dengan 15. karena lebih kecil maka 13 menempati left child dari 15.








Proses yang sama seperti sebelumnya berlaku untuk selanjutnya.


















2. Update : Seperti pada Binary Tree biasa, namun disini uapte akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.
3. Delete : Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.
(Keadaan awal merupakan lanjutan gambar sebelumnya)

Karena node yang berisi 5 adalah leaf, maka ia dapat langsung dihapus.





Karena node yang berisi 20 adalah leaf, maka ia dapat langsung dihapus.







Pada operasi di samping, delete dilakukan terhadap Node dengan 2 child. Maka untuk menggantikannya, diambil node paling kiri dari Right SubTree yaitu 13.




Pada operasi di samping, delete dilakukan terhadap node dengan 1 child. Maka child tersebut (11) akan menggantikan posisi dari node yang didelete (9).























MODUL 10
SORT

Definisi Sort
Sort adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu.
Pada umumnya terdapat 2 jenis pengurutan :
 Ascending (Naik)
 Descending (Turun)
Contoh :
Data Acak : 5 6 8 1 3 25 10
Terurut Ascending : 1 3 5 6 8 10 25
Terurut Descending : 25 10 8 6 5 3 1

POINTER

POINTER

Variabel Pointer

Pada materi sebelumnya telah dijelaskan mengenai variabel bertipe array, suatu tipe data yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu ruang memori yang dipakai olehnya tidak dapat dihapus bila variabel bertipe array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Untuk memecahkan masalah diatas, kita dapat menggunakan variabel pointer. Tipe data pointer bersifat dinamis, variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat dialokasikan kembali.

Array vs Pointer
Berikut tabel di bawah ini diberikan perbedaan antara variabel bertipe array dengan varibel bertipe pointer.
Kriteria Array Pointer
Sifat Statis Dinamis
Ukuran Pasti Sesuai kebutuhan
Alokasi variabel Saat program dijalankan sampai selesai Dapat diatur sesuai kebutuhuan

Deklarasi Variabel Pointer
Bentuk umum :
Var : <^tipedata>
Contoh :
Var
Jumlahdata : ^integer;
Namasiswa :^string[25];
Nilaisiswa :^real;
Pendeklarasian variabel pointer tidak jauh berbeda dengan pendeklarasian variabel biasa, hanya perlu ditambahan simbol topi (^) sebelum tipe datanya. Simbol topi tersebut menandahkan bahwa variabel tersebut menunjuk ke lokasi tertentu pada memori.
Anda juga dapat membuat variabel pointer bertipe record yang anda definisikan sendiri. Pendeklarasiannya adalah seperti berikut ini.
Bentuk umum :
Tipe
= <^namarecord>;
= record
:;
:;
…
:;
end;
Var
:;
contoh :
Type
PointMhs = ^RecMhs;
RecMhs = record
Nama : string[25];
NIM : string[10];
Alm : string[30];
IPK : real;
End;
var
datamahasiswa : pointMhs;




Varibel Biasa vs Variabel Pointer
Variabel Pointer adalah suatu variabel yang menunjuk ke alamat memori yang digunakan untuk menampung data yang akan diproses, seperti digambarkan dibawah ini:
memori

P 0100
0200
0300
…
FFFF

P adalah variabel pointer yang menunjuk ke alamat memori 100 yang berisi data bertipe string “Aku”. Apabila anda ingin menambah data dengan menggunakan variabel yang berbeda, maka anda dapat mendeklarasikan variabel pointer baru misalnya Q dan R dst sehingga tampak sbb :
memori
P 0100
Q 0200
R 0300
…
FFFF








Untuk membedakan antara variabel pointer dengan variabel biasa, perhatikan contoh berikut :




























Single Linked List
Apabila setiap kali anda ingin menambahkan data selalu dengan menggunakan variabel pointer yang baru, anda akan membutuhkan banyak sekali variabel pointer(penunjuk).
Oleh karena itu ada baiknya jika anda hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kita sebut Linked List. Jika diterjemahkan, maka berarti suatu daftar isi yang saling berhubungan. Untuk lebih jelasnya perhatikan gambar di bawah ini :

memori
P 0100
0200
0300
… Nill
FFFF

Pada gambar diatas tampak bahwa sebuah data terletak pada sebuah lokasi memory area. Tempat yang disediakan pada suatu area memory tertentu untuk menyimpan data dikenal dengan sebutan node/simpul. Pada setiap node memiliki pointer(penunjuk) yang menunjuk ke simpul berikutnya sehingga terbentuk suatu untaian dan dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List. (ket: Nill tak memiliki nilai apapun. Biasanya linked list pada titik akhirnya akan menunjuk ke Nill).
Dalam pembuatan single linked list dapat menggunakan 2 metode :
 LIFO (Last In First Out), aplikasi : Stack(Tumpukan).
 FIFO (First In First Out), aplikasi : Queue(Antrian).



LIFO (Last In First Out)
LIFO adalah suatu metode pembuatan linked list, dimana data yang masuk paling akhir adalah data yang keluar paling awal. Hal ini dapat dianalogikan (dalam kehidupan sehari-hari) pada saat anda menumpuk barang, seperti digambarkan di bawah ini :

(keadaan mula-mula
adalah kosong)




Pembuatan sebuah simpul dalam suatu linked list seperti digambarkan diatas disebut dengan istilah INSERT. Jika linked list dibuat dengan metode LIFO, maka terjadi penambahan/insert simpul di belakang.

PROSEDURE INSERT
Istilah insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list. Berikut di bawah ini adalah penggalan listing prosecure insert untuk LIFO berserta contoh dan penjelasan cara kerjanya.







Penggalan deklarasi tipe data dan variabel di atas ini akan dipakai pada penjelasan procedure-procedure selanjutnya.












Penggalan procedure INSERT untuk LIFO


Head


(ket : head mula-mula selalu dideklarasikan sebagai nil)



Now






Now Head





Now

QUEUE ( ANTRIAN )

QUEUE ( ANTRIAN )

- Kumpulan data dimana data masuk dan keluar pada ujung yang berbeda.
- Konsep utama FIFO ( Fisrt In First Out ).

Contoh:
1 2 3




Data nomor 1 datang/masuk dan keluar duluan.

Algoritma:
1. Input/tambah data
• Jika ada input maka no antrian yang semula 0 akan tambah 1 demi 1 sampai maksimal antrian.

2. Hapus/Pengambilan data
• Jika ada pengambilan data maka data dipindahkan di variabel lain contohnya temp, antrian ke-dua akan maju ke antrian pertama dan seterusnya. Dan jumlah antrian yang semula maksimal akan berkurang 1 demi 1 sampai antrian 0 kembali.






1. Deklarasi Queue
Type
Const
Max = 5;
Nama record = Record
Data : type data;
Top : byte;
End;
Nama_array = ARRAY [1..max] of Nama record;
Var
Antri : nama Array;

1 2 3 4





Nama Array----- Barang
Nama Record--- Coba
Nama Variabel-- Antri

Contoh Deklarasi dari gambar diatas:
Type
Coba = record
Data :string;
Top : byte;
End;
Barang = ARRAY [1..4] of coba;
Var Antri:barang;
2. Operasi pada queue
• CREATE
Membuat antrian baru yang masih kosong.

Procedure create;
Begin
antri.top:=0;
End;

• FULL
Untuk memeriksa apakah antrian sudah penih..

Fuction full:bolean;
Begin
antri.top:=max;
End;

• PUSH
Menambah sebuah elemen ( data ) kedalam antrian.
Syarat: tidak bisa dilakukan jika antrian sudah penuh.

Procedure push ( input:string );
Begin
If not full then
Begin
antri.top:=antri.top;
antri.data:=input;
End;
End;

• EMPTY
Fuction empty: bolean;
Begin
Empty:=false;
If top:=0 then empty:=true;
End;

• POP
Mengambil 1 elemen dari sebuah antrian.
Syarat: antrian tidak boleh kosong.

Procedure Pop ( elemen:string );
Begin
If not empty then
Begin
Elemen:=antri.data;
antri.top:=top – 1;
End;
End;


Contoh:
1 2 3







Program antrian_1;
Uses wincrt;
Type
Data= array [1..3] of string;
Var
D: data;
I, antri: integer;
Temp: string;
Begin
Antri:=0;