STRUKTUR DATA Terttiaavini, S.Kom.,M.Kom PROGRAM STUDI SISTEM INFORMASI

STRUKTUR DATA Terttiaavini, S.Kom.,M.Kom PROGRAM STUDI SISTEM INFORMASI

Univ. Indo Global Mandiri

BAB I PENDAHULUAN Struktur data adalah cara menyimpan atau merepresentasikan data didalam komputer agar bisa dipakai secara efisien. Sedangkan data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol. Struktur data dapat di artikan juga sebagai representasi data pada memory secara logika dan meng-karakterisasikan setiap variabel dalam program secara eksplisit ataupun implisit, Untuk operasi yang dibolehkan/berlaku pada object data tersebut sehingga sangat diperlukan dalam perencanaan Algoritma dan penyusunan program sebagai dasar teknik dari Database Pemakaian struktur data yang tepat didalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana. Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolomkolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkasberkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data. Dalam pengertian lain, Struktur Data dapat juga di sebut sebagai suatu kumpulan objekobjek data yang memiliki aturan (terorganisir) yang kemudian di golongkan berdasarkan operasi-operasi untuk memanipulasinya. Contoh objek data tersruktur adalah Array, Record, shorting, linklist,Stack, Queue, Tree, graph..dll I.2. Dasar Pengetahuan Struktur data Dalam mempelajari struktur data hal-hal awal yang perlu kita ketahui adalah tentang indentifier, konstanta, variable, dan tipe data. a) Identifier Identifier merupakan nama yang digunakan untuk keperluan menyimpan suatu nilai, pendeklarasian variabel, konstanta, tipe dan nama program atau sub program. Identifier tidak boleh ditulis secara sembarangan. Aturan Penulisan Identifier - Nama identifier harus dimulai dengan karakter huruf alfabet a-z atau A-Z. - Setelah karakter pertama, dapat dilanjutkan dengan karakter alfanumerik (angka maupun huruf) dan underscore (_). - Dalam penulisan identifier tidak boleh menggunakan karakter-karakter berikut ini : ~ ! @ # $ % ^ & () * ) - + = `; : “ „ < > , . ? / { } [ ] | \ - Tidak boleh menuliskan identifier dengan nama yang sama pada kata kunci dari Pascal, seperti Copyright 2013

1



and, array, begin, case, const, div, do, downto, else, end, file, for, forward, function, goto, if, in, label, mod, nil, not, of, or, packed, procedure, program, record, repeat, set, then, to, type, until, var, while, with

-

Jika ingin tetap digunakan, maka kata tersebut harus dirangkai dengan kata/karakter yang lain. Misal program_if, begin1.

b) Konstanta Suatu konstanta direferensikan lewat identifier dan dapat diberikan nilai tertentu. Nilai yang disimpan di dalam konstanta tidak dapat berubah. Kata kunci di dalam Pascal untuk mendeklarasikan konstanta adalah const. Contoh program konst; uses crt; const phi = 3.1415926535897932; (* real *) fakultas = „Teknologi Informasi‟; (* string *) begin clrscr; writeln(phi); writeln(fakultas); readln; end.

c) Variabel Varibel hampir mirip dengan konstanta. Nilai yang disimpan di dalam variabel dapat diubah kapan saja di dalam program. Kata kunci di dalam Pascal untuk mendeklarasikan konstanta adalah var. Setiap variabel yang dibuat di dalam satu baris harus dipisah dengan tanda koma. Contoh Variabel program vari; uses crt; var nama : string; nim : integer; nilai : char; begin clrscr; nama := „Annisa Fitriani‟; nim := 12293678; nilai := „A‟; writeln(„NAMA: ‟,nama); writeln(„NIM: ‟,nim); writeln(„AKSARA: ‟,aksara); readln; end.

d) Type data Berdasarkan nilai yang disimpan di dlam variabel, terdapat 4 jenis tipe data. 1) Integer Integer adalah tipe data nilainya merupakan bilangan bulat dan terbagi atas beberapa macam. Berikut ini adalaha tabelnya: Type ShortInt Integer LongInt Byte Word

Range -128…127 -32768...32767 -2147483648…2147483647 0…255 0…65535

Ukuran 1 2 4 1 2

Format Signed 8-bit Signed 16-bit Signed 32-bit Unsigned 8-bit Unsigned 16-bit

2 Copyright 2013



2) Boolean Boolean digunakan untuk merepresentasikan logika. Boolean hanya dapat bernilai True(1) dan False(0). Di bawah ini adalah beberapa tipe data Boolean: Type Boolean ByteBool WordBool LongBool

Range Byte-sized Byte-sized Word-sized Long-sized

Ukuran 1 (8bit) 1 (8bit) 2 (16bit) 4 (32bit)

3) Real Real biasanya digunakan untuk merepresentasikan nilai pecahan. Jenis-jenis tipe data real seperti pada tabel berikut ini: Type Real Single Double Extended Comp

Range ±2.9×10-39 … 1.7×1038 ±1.5×10-45 ... 3.4×1038 ±5×10-324 ... 1.7×10308 ±3.4×10-4932 ... 1.1×104932 ±9.2×1018 ... 9.2×1018

Ukuran 6 4 8 10 8

Digit 11-12 7-8 15-16 19-20 19-20

4) Karakter Tipe data karakter hanya dapat menampung satu karakter saja dan mengalokasikan satu byte memori. 5) String String adalah tipe data gabungan (array) dari bebrapa karakter. e)

Operasi Aritmetika Macam-macam operator aritmetik pada Pascal Operator + * / div mod

Operation Penjumlahan Pengurangan Perkalian Pembagian Pembagian Integer Modulus

Operands real/integer real/integer real/integer real/integer integer integer

Result real/integer real/integer real/integer real integer integer

Operasi Aritmetika Operasi aritmetik dalam Pascal tidak dapat diterapkan pada variabel bertipe data boolean dan char. Untuk menyatakan tanda negatif dari suatu nilai digunakan tanda minus (-). Contoh operasi aritmetika. bilBulat := (2*15)+(-2) bilRiil := 37.5 * 3 - 9 Contoh Operasi Aritmetika program arit;

uses crt; const phi = 3.14; var jari : integer; luas : real; begin clrscr; jari := 5; luas := phi * (jari*jari); writeln(„LUAS: ‟,luas); end.

3 Copyright 2013



BAB II JENIS STRUKTUR DATA II.1. Jenis Data dapat dikatagorikan menjadi : a) Type data sederhana terdiri atas - Data sedehana tunggal Contoh: integer, real,boolean,karakter - Data sederhana majemuk Contoh : string b) Struktur data terdiri atas - Struktur data sederhana Contoh type data sederhana, type terstruktur, matrik, array, record - Struktur data majemuk, terdiri atas : Linier Contoh linked list,stack (tumpukan), queue (antrian) Non linier Contoh pohon binary (binary tree), pohon cari binar (Binary search tree), pohon cari M Way (M Way search) , general tree, graph II.2. Array Array adalah suatu tipe data terstruktur yang terdapat didalam memori, yang mempunyai tipe data yang sama dengan jumlah komponen yang tetap. Digunakan untuk merepresentasikan sekumpulan informasi yang bertipe sama dan disimpan dalam urutan yang sesuai dengan defenisi indeks secara kontigue dalam memori komputer. Tipe data indeks yang dapat digunakan adalah tipe data yang memiliki keterurutan misalkan integer, karakter Penyimpanan array secara logik dlm memori komputer seperti dibawai ini

Deklarasi Array type = array[index array] of

Contoh Deklarasi array untuk nama hari Hari = (senin,selas,rabu,kamis,jumat,sabtu,minggu); Type namaHari : array[hari] of string;

Deklarasi array untuk nama bulan Type bulan : array[12] of string

Deklarsi array menggunakan konstanta untuk menentukan indeks array Const maks = 100; Type nilai : array[maks] of string;

Kekebihan Array Keunggulan array adalah sebagai berikut : 1. Array sangat cocok untuk pengaksesan acak. Sembarang elemen di array dapat diacu secara langsung tanpa melalui elemen-elemen lain. 2. Jika berada di suatu lokasi elemen, maka sangat mudah menelusuri ke elemenelemen tetangga, baik elemen pendahulu atau elemen penerus. 3. Jika elemen-elemen array adalah nilai-nilai independen dan seluruhnya harus terjaga, maka penggunaan penyimpanannya sangat efisien. Copyright 2013

4

STRUKTUR DATA Univ. Indo Global Mandiri

Terttiaavini, S.Kom.,M.Kom PROGRAM STUDI SISTEM INFORMASI

Kelemahan Array Array mempunyai fleksibilitas rendah, sehingga tidak cocok untuk berbagai aplikasi karena array mempunyai batasan sebagai berikut : 1. Array harus bertipe homogen. Kita tidak dapat mempunyai array dimana satu elemen adalah karakter, elemen lain bilangan, dan elemen lain adalah tipe-tipe lain. 2. Kebanyakan bahasa pemrograman mengimplementasikan array statik yang sulit diubah ukurannya di waktu eksekusi. Bila penambahan dan pengurangan terjadi terus-menerus, maka representasi array : - Tidak efisien dalam penggunaan memori - Menyiakan banyak waktu komputasi - Pada suatu aplikasi, representasi statis tidak dimungkinkan Bila penambahan dan pengurangan terjadi terus menerus, maka representasi array : - Tidak efisien dalam penggunaan memory - Menyiakan banyak waktu komputasi - Pada suatu aplikasi, representasi statis tidak di mungkinkan. II.3. Record Record (rekaman) merupakan kumpulan data yang terdiri dari beberapa field yang memiliki tipe data berbeda ataupun sama. Penyimpanan Record secara logik dalam memori komputer seperti dibawah ini.

Kelemahan Record - Hanya dapat menginput satu set/baris data Kelebihan Record - Pada satu set/baris data dapat terdiri beberapa field yang memiliki tipe data yang berbeda. Pada implementasi ke bahasa pemrograman Array dan Record dapat di gabungkan dalam satu type data bentukan Record. II.4. Pointer Pointer adalah variabel yang berisi alamat memori sebagai nilainya. Pointer digunakan bersamaan dengan dynamic memory allocation. Data yang ditunjuk dengan variabel pointer merupakan alokasi dinamik, selama eksekusi program. Ini berarti program dapat mengciptakan dan menghapus data yang di tunjuk oleh variabel pointer. Larik dan record merupakan perubah statik (banyak data yang diolah terbatas). Peubah Dinamis adalah peubah yang akan dialokasikan hanya pada saat diperlukan yaitu setelah program dieksekusi. Peubah dinamis menggunakan variabel Pointer Pointer adalah variabel yang sering dikatakan sebagai variabel yang menunjuk ke variabel yang lain. Perbedaan antara variabel bertipe array dan pointer 5 Copyright 2013



Deklarasi Pointer - Bentuk Umum Type = ^ = Var PI,P2 =

Contoh Type point = ^data; data = integer; Var PI,P2 = pointer;

-

Bentuk Umum Type

end; Var PI,P2 =

= = = = =

^ record;

Contoh Type point = ^data; data = record; nama : string[25]; alamat : string[35]; pekj : string[30]; end; Var PI,P2 = point; New(p1); New(p2);

II.4.1. Operasi Pada Pointer Ada 2 operasi dasar yang bisa kita lakukan data yg bertipe pointer yaitu - Pengkopian Pointer Contoh : New(p1); New(p2); P1^.nama := “Anisa “; P1^.nama := “Km. 5”; P1^.Pekj := “Wiraswasta”

-

Pengkopian isi simpul Jika statemen yang diberikan adalah P2^ :=

P1^

maka hasil yang diperoleh

6 Copyright 2013



BAB III PENGURUTAN DATA (SHORTING) Pengurutan Internal dan Pengurutan Ekternal Pengurutan dibagi menjadi 2 kelompok : 1. Pengurutan Internal Pengurutan terhadap sekumpulan data yang disimpan di memori utama komputer. Bersifat sementara 2. Pengurutan Eksternal Pengurutan data yang disimpan didalam memori sekunder. Bersifat tetap. Banyaknya algoritma pengurutan yang tersedia menimbulkan pertanyaan : algoritma manakah yang memiliki kinerja paling baik?. Kinerja pengurutan data sangatlah menentukan kinerja sistem. Karena itu pemilihan Metode pengurutan yang cocok akan berperan penting dalam suatu aplikasi. Pada Bab ini metode pengurutan yang akan dibahas hanya tiga yaitu 1. Pengurutan Gelembung (Bubble Sort) 2. Pengurutan Maksimum/Minimun (Maximum / Minimum Sort) 3. Pengurutan Sisip (Inserrtion Sort) Pengurutan gelembung (Bubble sort) Metode pengurutan gelembung di inspirasi dari gelembung sabun yang berada di atas permukaan air Karena berat jenis sabun lebih ringan dari pada berat jenis air, maka gelembung sabun akan selalu terapung diatas air. Prinsip pengapungan diatas digunakan pada pengurutan gelembung. Elemen larik yang berharga paling kecil “diapungkan” artinya diangkat keatas (atau ke ujung larik) melalui pertukaran Proses pengapungan ini dilakukan sebanyak N kali langkah. Pada akhir setiap langkah ke K, larik L[1..N] akan terdiri dari dua bagian yang sudah terurut yaitu L[1..K] dan bagian yang belum terurut L[K+1..N]. Setelah langkah terakhir diperoleh larik L[1..N] terurut menaik Algoritma Pengurutan gelembung Langkah 1 : Mulai dari elemen K = N, N-1,…2, bandingkan L[K] dengan L[K-1], jika L[K] < L[K-1], tukar L[K] dengan L[K-1] Pada akhir langkah 1, elemen L[1] berisi harga minimum pertama. Langkah 2 : Mulai dari elemen K = N, N-1,…3, bandingkan L[K] dengan L[K-1], jika L[K] < L[K-1] tukar L[K] dengan L[K-1] Pada akhir langkah 2, elemen L[2] berisi harga minimum kedua dari larik L[1..2] yang terurut. Langkah 3 : Mulai dari elemen K = N, N-1,…4, bandingkan L[K] dengan L[K-1], jika L[K] < L[K-1] tukar L[K] dengan L[K-1] Pada akhir langkah 3, elemen L[3] berisi harga minimum kedua dari larik L[1..3] yang terurut. Copyright 2013

7



Langkah N - 1 : Mulai dari elemen K = N, bandingkan L[K] dengan L[K-1], jika L[K] < L[K-1] tukar L[K] dengan L[K-1] Pada akhir langkah N, elemen L[N] berisi harga minimum dari larik L[1..N] yang terurut. Contoh : Terdapat larik berisi dengan 6 buah elemen ( N=6) yang belum terurut. Lakukan metode Bubble Sort untuk isi larik tersebut.

Akhir dari langkah 5 menghasilkan deretan data didalam larik L yang sudah terurut menaik. Untuk seluruh prosedur pengurutan pada Bab ini menggunakan Deklarasi Array sebagai berikkut : 8 Copyright 2013



{**Mendefenisikan struktur data**} type larik = array[1..100] of integer; var l : larik; i,n,k,temp : integer; Prosedur untuk menginput data sebanyak N data adalah write('Banyak data yang di input : ');readln(n); for i :=1 to n do begin write ('Data ke ',i,' : ');readln(l[i]); end;

Prosedur untuk menampilkan data sebanyak data yang di input adalah writeln;writeln('Data yang sudah terurut adalah'); for k := 1 to n do write(l[k],' '); end.

Prosedur pengurutan gelembung Prosedur Pengurutan Gelembung for i := 1 to n-1 do begin for k :=n downto i+1 do begin if l[k] < l[k-1] then begin {pertukaran l[k] dengan l[k-1]} temp := l[k]; l[k] := l[k-1]; l[k-1] := temp; end; end; end;

Pengurutan Maksimum dan minimum (Maksimum sort / Minimum Sort) Metode pengurutan ini berdasarkan pada pemilihan nilai maksimum atau minimum didalam larik. Gagasannya adalah memilih elemen maksimum atau minimum yang di pertukarkan pada elemen ujung larik. Kemudian elemen ujung tersebut di isolasi untuk tidak disertakan lagi pada proses selanjutnya. Proses yang sama diulang untuk elemen larik yang tersisa sampai data telah terurut maksimum/minimum dan tidak dapat ditukar lagi. Metode pengurutan maksimum atau minimum disebut juga sebagai pegurutan berdasarkan pemilihan/seleksi (selection Sort)

9 Copyright 2013



Algoritma Pengurutan Maksimum Secara ringkas, algoritma pengurutan maksimum dinyatakan dalam urutan langkah sebagai berikut : Langkah 1 Tentukan harga maksimum didalalam L[1..k] Pertukarkan harga maksimum dengan elemen L[k] Langkah 2 Tentukan harga maksimum didalalam L[1..k-1] Pertukarkan harga maksimum dengan elemen L[k-1] Langkah 3 Tentukan harga maksimum didalalam L[1..k-2] Pertukarkan harga maksimum dengan elemen L[k-2] Langkah N - 1 Tentukan harga maksimum didalalam L[1.. K-2] Pertukarkan harga maksimum dengan elemen L[N-2] Elemen yang tersisa adalah L[1], tidak perlu diurut lagi karena karna sudah terurut. Contoh : tinjau larik dengan k = 6 buah elemen dibawah ini yang belum terurut. Larik ini akan diurut menaik

10 Copyright 2013



Akhir dari langkah 5 menghasilkan deretan data didalam larik L yang sudah terurut menaik. Prosedur Pengurutan Maksimum Menaik u := n; for i := 1 to n-1 do begin maks := l[1]; imaks := 1; for j := 2 to u do begin if l[j] > maks then begin maks := l[j]; imaks := j; end; end; {pertukaran maks dengan l[u]} temp := l[u]; l[u] := l[imaks]; l[imaks] := temp; {larik l[u..n] terurut, larik l[1..u-1] belum terurut} u := u-1; end;

Untuk prosedur minimum, silakan anda lakukan sendiri sebagai latihan Pengurutan Sisip ( Insertion Sort ) Pengurutan sisip (Insertion sort) adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi yang tepat dapat dilakukan dengan cara melakukan pencarian pencarian beruntun didalam larik. Selama pencarian posisi yang tepat dilakukan pergeseran elemen larik. Algoritma pengurutan sisip menaik Andaikan : Misalkan L[1] dianggap sudah pada tempatnya Langkah 2 L[2] harus dicari tempatnya yang tepat pada L[1..2] dengan cara menggeser elemen L[1..1] kekanan, bila L[1..1] > L[2]. Misalkan posisi yang tepat adalah K, sisipkan L[2] pada L[K] Langkah 3 L[3] harus dicari tempatnya yang tepat pada L[1..3] dengan cara menggeser elemen L[1..2] kekanan, bila L[1..2] > L[3]. Misalkan posisi yang tepat adalah K, sisipkan L[3] pada L[K] Langkah N L[N] harus dicari tempatnya yang tepat pada L[1..N] , dengan cara menggeserkan 11 Copyright 2013



elemen L[1…N-1] kekanan , bila L[1..N-1] > L[N]. Misalkan posisi yang tepat adalah K, sisipkan L[N] pada L[K] Contoh : tinjau larik dengan N = 6 buah elemen dibawah ini yang belum terurut. Larik ini akan diurut menaik

Akhir dari langkah 5 menghasilkan deretan data didalam larik L yang sudah terurut menaik. Prosedur Pengurutan Sisip Menaik for k := 1 to n do begin temp := l[k]; j := k-1; while (temp <= l[j])and (j>1) do begin l[j+1] := l[j];j := j-1; end;

if temp >= l[j] then l[j+1] := temp else begin l[j+1] := l[j]; l[j] := temp; end; end;

12 Copyright 2013



QUIZ Lakukanlah pengurutan pada data dibawah ini :

Dengna metode : (pilih 2 metode pengurutan saja) 1. Bubble Sort (menaik dan menurun ) 2. Max Sort (menaik dan menurun ) 3. Min Sort (menaik dan menurun ) 4. Insertion Sort (menaik dan menurun )

Kerjakan perkelompok : maksimal 4 orang

13 Copyright 2013



BAB IV SENARAI BERANTAI (LINKED LIST) III.1. Defenisi Linked List Adalah struktur berupa rangkaian elemen saling berkait dimana tiap elemen dihubungkan dengan elemen lain dengan menggunakan Pointer. Penggunaan pointer untuk mengacu elemen, mengakibatkan elemen bersebelahan secara logik namun tidak secara fisik dimemori. Senarai Berantai sering disebut juga dengan Linked List. Perhatikan gambar linked list dibawah ini

- Terdapat dua simpul yaitu: 1. Start : merupakan variabel penuding list 2. Data/ info : berisikan informasi dari suatu simpul 3. Nextpointer/link/penuding : berisikan alamat untuk menuju ke simpul berikutnya. - Bagian pointer yang berisikan nilai nil, maka simpul tidak menuding kemanapun. III.2 Penyajian Linked Llist secara logic didalam memori Contoh 1 : Data Larik Info(K) adalah sebuah karakter tunggal. Kita ingin membentuk Linked list yang elemennya membentuk sebuah string atau untai. String yang dimaksud adalah NO EXIT

Contoh 2: Pada sebuah bangsal Rumah Sakit terdapat 12 tempat tidur. 9 diantaranya telah ditempati pasien. Kita ingin membuat List nama pasien secara alpabetik. Untuk itu kita buat sebuah linked List dengan Penuding Next. Varaibel Start kita gunakan untuk menyatakan Lokasi Pasien petama dalam List 14 Copyright 2013



Contoh 3 : Diperlukan dua buah Linked List ALGO dan GEOM yang berturut-turut berisi nilai testing mahasiswa Agoritma dan Geometri. Tersimpan dalam larik TEST dan link yang sama. Perhatikan nama dari List sekaligus digunakan sebagai variabel penuding. Disini penuding ALGO berisi nilai 11, yakni lokasi simpul pertama list ALGO, sedangkan penuding GEOM berisi bernilai 5, yakni lokasi simpul pertama dari list GEOM. Mengikuti penuding tersebut dapat dilihat bahwa List ALGO dan GEOM berisi nilainilai

15 Copyright 2013



III.3. Operasi dasar pada linked list III.3.1. Penciptaan dan penghancuran simpul Untuk menjelaskan operasi tersebut, kita gunakan deklarasi pointer berikut ini : type simpul = ^ data Data = record Info : char; Berikut : simpul; end; Var elemen : chart; awal,akhir,baru : simpul;

Perintah penciptaan simpul adalah New(nama_simpul), Perintah penghancuran simpul adalah dispose(nama_simpul) III.3.2 . Penyisipan simpul ke linked list Dalam Penyisipan simpul pada saat simpul awal belum menunjuk ke simpul manapun (linklist belum ada) maka untuk penyisipan simpul di awal, akhir dan tengah diperlakukan sama. 1) Pernyataan New (Baru) adalah pernyataan untuk membuat simpul baru.

2) Pada kondisi tersebut maka simpu baru merupakan simpul awal dan akhir

a) Penyisipan sebagai simpul pertama ( Insert_First) 1) Pointer awal adalah pointer yang menunjuk ke simpul pertama. Pointer akhir adalah pointer yang menunjuk ke simpul terakhir dan simpul yang ditunjuk oleh simpul baru adalah simpul yang akan ditambahkan ke gambar (a). 2) Berikut dari simpul baru dibuat menunjuk ke simpul awal. 3) Pointer awal dibuat sama menunjuk ke simpul baru. Dengan cara ini simpul baru selalu diperlakukan sebagai simpul awal.

16 Copyright 2013



Prosedur insert first Procedure insert_first; Var baru : simpul; begin New(baru); Baru^.info := elemen; If awal = nil then Akhir := baru; Awal := baru; Akhir^.berikut = nil; Else baru^.berikut := awal; Awal := baru;

2. Penyisipan setelah simpul tertentu (insert after linked list) a) Untuk menambah simpul ditengah senarai kita perlu bantuan sebuah pointer lain, misalnya pointer bantu. Dalam hal ini simpul baru akan diletakkan setelah simpul yang ditunjuk oleh pointer bantu. b) Secara garis besar operasi penambahan simpul tertentu dapat dijelaskan sebagai berikut : c) Pertama tentukan dimana simpul baru akan ditambahkan, lalu letakkan pointer bantu sebelum simpul baru. d) Berikut pada simpul baru dibuat sama menunjuk pada berikut simpul bantu. Berikut pada simpul bantu dibuat menunjuk ke simpul baru

Procedure insert_after (var awal,akhir : simpul; elemen : char) Var baru ,bantu: simpul; begin new(baru); baru^.info := elemen; If awal = nil then akhir := baru; awal := baru; akhir^.berikut = nil; Else Begin {*mencari lokasi yang sesuai*} Bantu := awal; While elemen >= bantu.^info do Bantu := bantu^.berikut;

17 Copyright 2013



{*menyisipkan elemen baru *} baru^.berikut := bantu^.berikut; bantu^.berikut := baru; end; end;

3. Penyisipan pada simpul terakhir ( insert last) a) Dalam hal ini simpul baru akan ditambahkan menjadi simpul terakhir; b) Berikut pada simpul akhir menunjuk ke simpul baru. c) Pointer akhir dibuat sama menunjuk ke simpul baru.

Procedure insert_last; var baru : simpul; begin New(baru); Baru^.info := elemen; If awal = nil then begin akhir := baru; awal := baru; akhir^.berikut= nil; end else begin akhir^.berikut:=baru; akhir := baru; akhir^.berikut:=nil; end; end;

18 Copyright 2013



III.3. 3. Penghapusan simpul suatu linked list Dalam penghapusan simpul ada hal yang perlu diperhatikan yaitu simpul yang bisa dihapus adalah simpul yang berada sesudah simpul yang ditunjuk oleh suatu pointer. 1. Penghapusan simpul pertama (delete first) Penghapusan di awal dapat dijelaskan sebagai berikut a) Pointer Hapus kita buat sama dengan pointer Awal. b) Pointer Awal menunjuk ke simpul setelah Hapus. c) Dispose (hapus) simpul hapus.

2. Penghapusan simpul Akhir (delete Last Linked List ) Penghapusan di Akhir dapat dijelaskan sebagai berikut a) Kita letakkan pointer bantu sebelum simpul akhir. b) Kemudian Pointer Hapus buat sama dengan Pointer Akhir . c) Pointer Akhir menunjuk ke simpul Bantu d) Dispose (hapus) simpul hapus.

3. Penghapusan simpul Tengah (delete after linked list ) Penghapusan di Tengan atau dikhir dapat dijelaskan sebagai berikut a) Kita letakkan pointer bantu menunjuk ke simpul sebelum simpul yang akan dihapus. Simpul yang akan dihapus kita tunjuk dengn Pointe Hapus. 19 Copyright 2013



b) Kemudian Simpul Bantu menunjuk ke simpul setelah simpul Hapus (yang ditunjuk simpul hapus). c) Dispose (hapus) simpul hapus.

Prosedur untuk menghapus simpel didepan atau diakhir linked list (Delete After and Last LinkedList ) Silakan anda coba sebagai latihan.

III.3.4. Pembacaan Isi Linked List Dapat dilakukan dengan 2 cara 1. Membaca Maju Membaca Linked List dari simpul awal sampai simpul akhir Dapat diselesaikan sebagai berikut : a) Pointer Bantu menunjuk ke simpul Awal b) Lakukan Kunjungan di setiap simpul sambil membaca isi simpul. c) Pada saat Pointer Bantu telah membaca isi simpul Akhir, maka proses berhenti.

20 Copyright 2013



Procedure baca_maju(awal,akhir, simpu); Var bantu : simpul; begin Bantu= := awal; repeat write (bantu^.info:2); Bantu := bantu^.berikut; Until bantu^.berikut = nil; Writeln; End;

2. Membaca Mundur Membaca Mundur Linked List dilakukan dengan cara merubah arah Pointer, dimana simpul akhir nantinya menjadi simpul Awal dan simpul Awal menjadi Simpul Akhir. Prosedurnya adalah sebagai berikut a) Pointer Bantu menunjuk ke simpul Awal b) Pointer Awal menunjuk ke simpul Akhir. c) Proses ini adalah proses merubah arah pointer. Dengan cara : Pakai Pointer Bantu1 yang juga menunjuk ke Pointer Bantu. d) Lakukan kunjungan ke simpul-simpul menuju simpul sebelum simpul akhir. e) Lakukan perubah arah pointer, dengan cara simpul Akhir menunjuk ke simpul bantu1. f) Rubah pointer Akhir menunjuk ke simpul bantu1 g) Ulangi langkah c sampai simpul Akhir = simpul Bantu. h) Lakukan Pembacaan dari Simpul Awal sampai simpul Akhir dengan cara pembacaan maju

21 Copyright 2013



Procedure baca_mundur(var awal,akhir : bantu); Var bantu : simpul; begin Bantu= := awal; Awal := akhir; repeat {*Proses membalik Pointer*} Bantu1 := bantu; {*Mencari letak simpul bantu1*} While bantu1^.berikut <> akhir do Bantu1 := bantu1^.berikut; Akhir^.berikut := bantu1; Akhir := bantu1; Until akhir = bantu; Akhir^.berikut := nil; End;

III.3.5. Senarai Berantai Berkepala (Header Linked List ) Adalah senarai yang memiliki simpul kepala, dimana simpul kepala tersebut bertipe data sama dengan simpul yang lain, tetapi tidak memiliki info didalamnya.

22 Copyright 2013



Procedure initial_header(var kepala,ekor: simpul); Begin new(kepala); ekor := kepala; kepala^.berikut := nil; End;

Dengan adannya simpul header maka prosedur dan fungsi yang telah dijelaskan diatas perlu dimodifikasi. Untuk memodifikasi diserahkan kepada anda untuk membuatnya sekaligus sebagai latihan. Tugas 1. Buatlah program Header Linked List untuk operasi penambahan dan penghapusan simpul dan pembacaan simpul. 2. Buatlah program Circular linked List untuk operasi penambahan dan penghapusan dan pembacaan simpul.

23 Copyright 2013



BAB V TUMPUKAN (STACK) V.1. Pengertian Tumpukan(Stack) adalah bentuk khusus dari list linier, penghapusan dan pemasukan elemen hanya dapat dilakukan pada satu posisi yaitu akhir list. Posisi ini disebut posisi puncak (Top) Jelas maka bila stack S = [S1, S2,… St] maka Top (S) = t V.2 Operasi pada Tumpukan (Stack) Ada 2 operasi dasar yang bisa dilakukan pada tumpukan yaitu menyisipkan data (Push) dan mengeluarkan data (Pop) Ilustrasi dibawah ini mengambarkan kerja kedua operator tersebut Push (A,B)

Push (C,D)

Pop 1 data D C B

Pop 2 data 4 D

4

4

4

3

3

3

2

2

1 A Larik A

1

1

Larik A

Larik A

B 1 A Larik A 2

3 2

V.3. Penyajian Tumpukan Ada 2 cara dalam menyajikan tumpukan ke dalam bahasa pemrograman yaitu 1. Penyajian Tumpukan dengan menggunakan Larik (array) Pemakaian larik dalam menyajikan tumpukan memiliki kekurangan yaitu banyaknya elemen larik terbatas. Pada suatu saat ukuran tumpukan akan sama dengan ukuran larik. Bila terus ditambahkan akan menyebabkan overflow. Dalam penyajian Tumpukan yang menggunakan tipe data larik dapat digabungkan dengan tipe data terstruktur (record) sehingga larik dapat terdiri dari beberapa field. Deklarasi array-record

Dengan deklarasi diatas elemen tumpukan disimpan dalam dua field, filed pertama untuk menyimpan elemen tumpukan, field yang kedua untuk mencatat posisi ujung tumpukan 

Implementasi Operasi Push, Implementasi Procedure Push adalah

24 Copyright 2013



Dengan ditambahnya testing prosedur diatas lebih sempurna untuk mencegah terjadinya overflow Operasi Pop, implementasi prosedur Pop adalah

Operasi Pop ditambahkan kondisi agar prosedur tidak melakukan pengurangan T.atas terus menerus saat data pada tumpukan sudah kosong 2.

Penyajian Tumpukan dengan menggunakan Pointer. Kita dapat Menyajikan tumpukan dengan senarai berantai Linier (Linked List). Elemen pertama dalam senarai berantai diperlakukan sebagai elemen teratas dari tumpukan dengan mengacu pada prosedur Push dan Pop Untuk menjelaskan kedua operasi ini, maka terlebih dahulu dideklarasikan tipe data yang diperlukan

Karna senarai berantai kita tentukan sebagai senarai berantai berkepala, maka terlebih dahulu kita mulai dengan initialisasi tumpukan untuk simpul kepala.

Bila senarai berantai hanya berisi simpul kepala berarti tumpukan masih kosong Implementasi Operasi Push

25 Copyright 2013



Implementasi Prosedur Pop

V.4 Aplikasi pada tumpukan Salah satu aplikasi yang menggunakan konsep tumpukan adalah perjodohan tanda kurung (Matching parantheses). Aplikasi ini digunakan untuk merubah notasi Infix menjadi notasi Posfix Algoritma untuk merubah notasi Infix menjadi notasi Posfix

26 Copyright 2013



Contoh : Notasi Infix : ( ( A + B ) * C / D + E ^ F ) / G , rubahlah menjadi notasi Posfix.

Menghasilkan notasi Posfix : AB+C*D/EF^+G/

Tugas : 1. Buatlah program tumpukan dengan tipe data array 2. Buatlah program tumpukan dengan tipe data pointer 3. Buatlah program pembalikan kalimat 4. Buatlah program untuk deret Polindrom 5. Buatlah program konversi basis 10 ke basis 2

27 Copyright 2013



BAB VI ANTRIAN (QUEUE) V.1. Pengertian antrian Queue / Antrian adalah suatu kumpulan data yang mana penambahan elemen hanya bisa dilakukan pada satu ujung (disebut dengan sisi belakang atau rear) dan penghapusan atau pengambilan elemen dilakukan lewat ujung lain (disebut dengan sisi depan atau front). Antrian menggunakan prinsip Pertama Masuk Pertama Keluar, First In First Out (FIFO). Antrian banyak dijumpai dalam kehidupan sehari-hari, seprti Mobil-mobil yang mengantri digerbang tol untuk membeli karcis tol; orang-orang yang mengantri di loket untuk membeli karcis film juga membentuk antrian Pada antrian kita tidak menentukan batasan seberapa banyak antrian itu akan berakhir tapi jika kita menggunakan array untuk mengimplementasikan queue/tumpukan kita harus membatasi jumlah antrian yang dapat masuk. Ini dikarenakan array memiliki batasan (upperbound) yang menjadi penghambat jika kita menggunakan antrian. Oleh sebab itu kita dapat mengimplementasikan antrian ini dengan menggunakan link list. Dengan menggunakan link list tepatnya Single Link List maka elemen dapat dimasukkan secara tidak terbatas. Implementasi Link list menngunakan Header Single Link List 6.2. Notasi Pada Queue Notasi yang dapat digunakan didalam Queue Q adalah : 1. FRONT(Q) menunjukkan posisi terdepan dari suatu antrian. Contoh jika kita mempunyai antrian Q = [A,B,C,D,E] maka FRONT(Q) = A. 2. REAR(Q) menunjukkan posisi terakhir dari suatu antrian. Contoh jika kita mempunyai antrian Q = [A,B,C,D,E] maka REAR(Q) = E. 3. NOEL(Q) menunjukkan jumlah elemen di dalam Antrean Q. Contoh jika kita mempunyai antrian Q = [A,B,C,D,E] maka NOEL(Q) = 5. 6.3. Deklarasi Queue Dalam Link List Pendeklarasian Queue di dalam link list sama seperti kita mendeklarasikan link list. Deklarasi Queue menggunakanHeader Linked List Type Queue = ^Simpul Simpul = Record Info : Char; Next : Queue; End; Var Head, Tail : Queue; Max : Byte;

6.4. Operasi Dasar Pada Queue Ada 4 operasi dasar yang dapat dilakukan pada struktur data antrian, yaitu: 1. CREATE(Q) : CREATE(Q) adalah suatu operator yang digunakan untuk membentuk dan menunjukkan suatu antrian hampa. Contoh : NOEL(CREATE(Q)) = 0 , FRONT(CREATE(Q)) = Tidak Terdefinisi REAR(CREATE(Q)) = Tidak Terdefinisi Berikut ini merupakan procedure CREATE simpul pada Pascal : Procedure CREATE(Var Head, Tail : Queue); Begin New(Head);

28 Copyright 2013



Head^.Info := 0; Head^.Next := Head; Tail := Head; End;

2. ISEMPTY(Q) : ISEMPTY(Q) adalah operator yang menentukan apakah antrian Q hampa atau tidak. ISEMPTY(Q) di terapkan di dalam pascal menjadi sebuah function yang bertipe boolean sehingga hasil dari function ini akan bernilai True jika antrian dalam keadaan kosong / hampa (NOEL(Q) = 0) dan akan bernilai False jika antrian dalam keadaan terisi / tidak kosong (NOEL(Q) > 0). Contoh : ISEMPTY(CREATE(Q)) = True Berikut ini merupakan procedure ISEMPTY simpul pada Pascal : Function ISEMPTY(Head : Queue); Begin ISEMPTY := (Head^.Next = Head); End;

3. INSERT(E,Q) : INSERT(E,Q) adalah operator yang digunakan untuk memasukkan elemen E pada antrian Q di posisi depan dari antrian. Hasil dari operator ini adalah antrian yang lebih panjang. Berikut ini merupakan procedure INSERT : Procedure INSERT(Elemen : Byte; Var Head, Tail : Queue); Var Temp : Queue; Begin New(Temp); Temp^.Info := Elemen; Temp^.Next := Head; Tail := Temp; Inc(Head^.Info); End

4. REMOVE(Q) : REMOVE(Q) adalah operator yang menghapus elemen bagian depan dari antrian Q. Hasilnya merupakan antrian yang lebih pendek. Pada setiap operasi ini, harga dari NOEL(Q) berkurang satu, dan elemen kedua dari Q menjadi elemen terdepan. Jika NOEL(Q) = 0, maka REMOVE(Q) memberikan suatu kondisi error, yakni suatau UNDERFLOW. Contoh : REMOVE(CREATE(Q)) = UNDERFLOW. Berikut ini merupakan procedure REMOVE : Procedure REMOVE(Var Head : Queue); Var Temp : Queue; Begin If Not (ISEMPTY(Head)) Then Begin Temp := Head^.Next; Head^.Next := Temp^.Next; Dispose(Temp); Dec(Head^.Info); End; End;

29 Copyright 2013



Untuk memahami pengertian antrian sekaligus penerapan operator-operator queue dan notasi-notasinya perhatikan ilustrasi berikut :

6.5. Jenis-jenis Antrian Queue memiliki dua variasi yang penggunaannya juga banyak di dalam kehidupan sehari hari atau dalam dunia komputer itu sendiri, diantaranya adalah : 1. DEQUE : DEQUE adalah antrian dimana elemennya bisa masuk dan keluar lewat kedua ujungnya (berbeda dengan queue yang hany bisa masuk lewat ujung belakang dan keluar lewat ujung depan). Biasanya DEQUE disajikan dengan menggunakan Double link list yang memiliki dua buah pointer yang menunjuk ke posisi sebelumnya dan sesudahnya. Gambar dibawah ini menunjukkan struktur umum dari sebuah DEQUE.

30 Copyright 2013



DEQUE juga mempunyai dua jenis variasi yaitu : a. Deque input terbatas : suatu deque yang membatasi pemasukkan elemen hanya pada satu ujung dari list, sementara penghapusan elemen boleh dilakukan pada kedua ujung list. b. Deque output terbatas : merupakan kebalikan dari deque input terbatas yaitu suatu deque yang membatasi penghapusan elemen hanya pada satu ujung dari list, sementara pemasukkan elemen boleh dilakukan pada kedua ujung list. 2. ANTRIAN BERPRIORITAS : Antrian berprioritas adalah suatu queue yang setiap elemennya telah diberikan sebuah prioritas, dan urutan proses penghapusan elemen adalah berdasarkan aturan berikut : a. Elemen yang prioritasnya lebih tinggi, diproses lebih dahulu dibandingkan dengan elemen yang prioritas lebih rendah. b. Dua elemen dengan prioritas yang sama, diproses sesuai dengan urutan mereka sewaktu dimasukkan ke dalam priority queue. Salah satu contoh antrian berprioritas ini adalah sistem berbagi waktu (time sharing system), dimana program yang mempunyai prioritas tinggi akan dikerjakan lebih dahulu dan program-program yang berprioritas sama akan membentuk antrian yang biasa. Anda bisa mencoba prosedur antrian beprioritas sebagai latihan.

31 Copyright 2013

STRUKTUR DATA Terttiaavini, S.Kom.,M.Kom PROGRAM STUDI SISTEM INFORMASI

Recommend Documents