Struktur Data

-à Kumpulan data dimana data masuk dan keluar pada ujung yang berbeda.

-à Konsep utama FIFO ( Fisrt In First Out ).

Contoh:

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;

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:

Program antrian_1;

Uses wincrt;

Type

Data= array [1..3] of string;

Var

D: data;

I, antri: integer;

Temp: string;

Begin

Antri:=0;

{untuk input}

For I:=1 to 3 do

Begin

Writeln(’masukkan nama ke’,’ ’,i);

Readln(d[i]);

Antri:=antri+1;

End;

{untuk Output}

For I:=1 to 3 do

Begin

Temp:=d[i];

Antri:=antri-1;

End;

{lihat output di var temp setelah pengambilan }

Writeln(’hasil var temp=’,temp);

Readln;

End.

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.

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:

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 :

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 :

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 :

v LIFO (Last In First Out), aplikasi : Stack(Tumpukan).

v 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

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

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.

v Create : Membuat sebuah linked list yang baru dan masih kososng. (ket: procedure ini wajib dilakukan sebelum menggunakan linked list)

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

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

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

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