MODUL STRUKTUR DATA
ADI PRATOMO NIP.19750925 200912 1 002
KEMENTERIAN PENDIDIKAN NASIONAL POLITEKNIK NEGERI BANJARMASIN JURUSAN ADMINISTRASI BISNIS BANJARMASIN 2010
i
DAFTAR ISI
Kata Pengantar .............................................................................................
i
Daftar Isi ........................................................................................................
ii
BAB I : Jenis-Jenis Data 1.1
Tipe Data Tunggal ...........................................................................
1
1.1.1
Integer .....................................................................................
1
1.1.2
Real .........................................................................................
2
1.1.3
Boolean ...................................................................................
2
1.1.4
Karakter ...................................................................................
2
1.1.5
String .......................................................................................
3
1.1.5.1
Length ............................................................................
3
1.1.5.2
Concatenation ................................................................
4
1.1.5.3
Substring ........................................................................
4
1.1.5.4
Insert ..............................................................................
5
1.1.5.5
Delete .............................................................................
5
1.2
Deklarasi Data dalam Bahasa Pemrograman ...................................
6
1.3
Pemetaan ke Storage ........................................................................
6
1.3.1
Integer .....................................................................................
6
1.3.2
Karakter ...................................................................................
7
1.3.3
String .......................................................................................
8
BAB II : ARRAY DAN RECORD 2.1
Array Satu Dimensi .........................................................................
11
2.2
Array Multi Dimensi ........................................................................
11
2.2.1
Cross Section ..........................................................................
12
2.2.2
Transpose ................................................................................
13
2.3
Deklarasi Array dalam Bahasa Pemrograman .................................
14
2.4
Pemetaan Array ke Storage ..............................................................
14
2.4.1
Array Satu Dimensi .................................................................
ii
14
2.4.2
Array Multi Dimensi ...............................................................
15
2.5
Record ..............................................................................................
17
2.6
Deklarasi Record dalam Bahasa Pemrograman ...............................
17
BAB III : STACK .........................................................................................
18
3.1
Linier List .........................................................................................
18
3.2
Definisi Stack ...................................................................................
18
3.3
Operasi Dasar Pada Stack ................................................................
19
3.3.1
CREATE .................................................................................
19
3.3.2
ISEMPTY ...............................................................................
19
3.3.3
PUSH ......................................................................................
19
3.3.4
POP .........................................................................................
20
3.4
Deklarasi Stack dalam Bahasa Pemrograman ..................................
20
3.5
Penggunaan/ Aplikasi Stack ............................................................
22
3.5.1
Matching Parentheses .............................................................
22
3.5.2
Notasi Postfix ..........................................................................
23
3.5.3
Proses Rekursif .......................................................................
25
Mapping ke Storage dari Stack ........................................................
27
BAB IV : QUEUE ........................................................................................
29
3.6
4.1
Definisi .............................................................................................
29
4.2
Gambar Queue .................................................................................
29
4.3
Prinsip Kerja pada Queue ................................................................
30
4.4
Operasi –Operasi pada Queue ..........................................................
30
4.5
Deklarasi Queue dalam Pascal .........................................................
31
4.6
Circular Queue .................................................................................
33
BAB V : LINKED LIST .............................................................................
38
5.1
Pendahuluan .....................................................................................
38
5.2
Definisi .............................................................................................
38
5.3
Operasi Dasar pada Linked List .......................................................
39
5.4
Menghapus Suatu Node dari Linked List (Remove) ........................
40
5.5
Menyisipkan Suatu Node ke dalam Linked List ..............................
42
5.5.1
Procedure Getnode(NEW) ......................................................
iii
42
5.5.2
Algoritma Menyisipkan sebuah Node ....................................
42
5.6
Logika Linked List pada Array ........................................................
44
5.7
Mendefinisikan Linked List dalam Pascal .......................................
45
5.8
Menghapus sebuah Node dalam Pascal ...........................................
45
5.9
Menyisipkan sebuah Node dalam Pascal .........................................
46
5.10 Penyisipan Pada Akhir Dari Suatu Linked List (Linked List Antrean) Dalam Pascal ...............................................................................................
46
5.11 Circular Linked List .........................................................................
47
5.12 Algoritma Penyisipan Node Yang Berisi Variabel Name Pada Head Dalam Linked List .......................................................................................
48
5.13 Menghapus Node Khusus ................................................................
48
5.14 Doubly Linked List ..........................................................................
49
5.14.1 Double Linked List Kosong ....................................................
49
5.14.2 Procedure Menghapus Sebuah Node Pada Double Linked List
50
5.14.3 Menyisipkan Sebuah Node pada Doubly Linked List .............
51
5.15 Contoh Aplikasi Linked List ............................................................
51
5.15.1 Polynomial ..............................................................................
51
BAB VI : GRAPH 6.1
Definisi .............................................................................................
53
6.2
Out Degree, In Degree, Degree dari suatu vertex a .........................
57
6.3
Penggambaran Node Directory ........................................................
59
BAB VII : TREE ............................................................................................
62
7.1
General Tree .....................................................................................
62
7.2
Forest ................................................................................................
63
7.3
Binary Tree ......................................................................................
63
7.4
Similar & Ekivalen Dalam 2 Binary Tree ........................................
64
7.5
Complete ..........................................................................................
65
7.6
Almost Complete .............................................................................
66
7.7
Height Min Dan Height Max ...........................................................
67
7.8
Representasi Binary Tree .................................................................
67
7.9
Binary Tree Transversal ...................................................................
69
iv
7.10 Binary Search Tree ..........................................................................
72
7.10.1 Direct Search ...........................................................................
72
7.10.2 Sequential Search ....................................................................
73
7.10.3 Insert Search ............................................................................
74
7.10.4 Delete search ...........................................................................
74
7.11 BALANCED TREE .........................................................................
74
7.12 Height Balanced Tree ......................................................................
74
BAB VIII : SEARCHING & SORTING .......................................................
76
8.1
Pendahuluan .....................................................................................
76
8.2
Sorting ..............................................................................................
76
8.3
Insertion Sort ....................................................................................
77
8.4
Selection Sort ...................................................................................
79
8.5
Merging ............................................................................................
81
8.6
Merge Sort .......................................................................................
82
8.7
Tournament Sort ..............................................................................
82
8.8
Shell Sort ..........................................................................................
87
8.9
Searching ..........................................................................................
89
8.10 Sequential Searching ........................................................................
89
8.11 Skema Move to the Front .................................................................
90
8.12 Skema Transposition ........................................................................
90
DAFTAR PUSTAKA ....................................................................................
91
v
BAB I JENIS-JENIS DATA
Suatu koleksi/ kelompok data yang dapat dikarakterisasikan oleh organisasi serta operasi yang didefinisikan terhadapnya. Data di kategorikan menjadi : 1. Tipe data tunggal (data primitif)
: Integer, Real, Boolean dan Karakter
2. Tipe data majemuk (data campuran)
: String (Untai)
Struktur data di kategorikan menjadi : 1. Struktur Data sederhana
: Array dan Record
2. Struktur Data majemuk
: Linier dan Non Linier
1.1 TIPE DATA TUNGGAL 1.1.1 INTEGER Suatu integer adalah anggota dari himpunan bilangan : ( ....., -(n+1), -n, ....., -2, -1, 0, 1, 2, ....., n, n+1, ..... ) Operasi-operasi dasar yang ada dalam integer antara lain :
Penjumlahan
Pengurangan
Perkalian
Pembagian
Perpangkatan, dsb Masing-masing operator pada operasi di atas, yang bekerja terhadap
sepasang integer (operand) disebut sebagai "binary operator". Sedangkan operator yang hanya bekerja terhadap satu operand saja disebut sebagai "unary operator". Contoh dari unary operator adalah operator negasi. Operator ini berfungsi untuk mengubah tanda suatu operand.
1
1.1.2
REAL Data numerik yang bukan termasuk integer, digolongkan dalam jenis data real. Jenis data ini ditulis menggunakan titik desimal (atau koma desimal). Bilangan real dimasukkan ke dalam memori komputer memakai sistem floating point, merupakan versi yang disebut Scientific Notation. Disini penyajiannya terdiri atas dua bagian, yaitu : mantissa (pecahan) & eksponen. Contoh : Di dalam sistem desimal, bilangan 123000 = 0.123 * 106. Disini 0.123 adalah mantissa (pecahan), sedangkan 6 adalah eksponennya. Secara umum suatu bilangan real X dituliskan M * RE
1.1.3 BOOLEAN Jenis data ini disebut juga jenis data "logical". Elemen dari jenis data ini mempunyai nilai salah satu dari "true" atau "false". Operator-operator yang dikenal pada jenis data ini terdiri atas: 1. Operator Logika, yaitu : NOT, AND dan OR.
Operator OR akan menghasilkan nilai "true", jika salah satu atau kedua operand bernilai "true".
Operator AND akan menghasilkan nilai "true", jika kedua operand bernilai "true".
Sedangkan operator NOT akan menghasilkan nilai "true", jika operand bernilai "false", dan sebaliknya.
Operator NOT merupakan "precedence" dari operator AND dan OR.
Dalam suatu ekspresi yang tidak menggunakan tanda kurung, operator NOT harus dievaluasi sebelum operator AND dan OR. 2. Operator Relasional, yaitu : >, <, >=, <=, <> dan =.
1.1.4 KARAKTER Jenis data karakter merupakan elemen dari suatu himpunan simbol aksara yang terdiri atas bilangan, abjad dan simbol-simbol khusus
2
1.1.5 STRING Jenis data string merupakan jenis data campuran, karena elemenelemennya dibentuk dari karakter-karakter di atas. String adalah barisan hingga simbol yang diambil dari himpunan karakter. Karakter yang digunakan untuk membentuk suatu string disebut sebagai alphabet. Dalam penulisannya, suatu string berada dalam tanda "aphosthrope". Contoh : Misal, diberikan himpunan alphabet A = { C, D, 1 } String-string yang dapat dibentuk dari alphabet di atas antara lain adalah : 'CD1', 'CDD', 'DDC', 'CDC1', ...dsb, termasuk "null string" atau "empty string".
Himpunan yang anggotanya adalah semua string yang dapat dibentuk dari suatu himpunan alphabet disebut sebagai "vocabulary". Suatu vocabulary V yang dihasilkan dari himpunan alphabet A dinotasikan dengan VA atau A*. Jika suatu string dibentuk dari alphabet {0,1}, maka string yang terbentuk disebut dengan "Bit String". Secara umum, suatu string S yang dibentuk dari himpunan alphabet A, dituliskan S = 'a1a2 ..... aN' , di mana setiap karakter ai anggota A untuk, 1 i N. Dalam suatu string terdapat beberapa operasi utama, yaitu : 1. Length 2. Concatenation 3. Substring 4. Insert 5. Delete
1.1.5.1
LENGTH Nilai dari operasi ini adalah suatu integer yang menunjukkan panjang dari
suatu string. Panjang dari string didefinisikan sebagai banyaknya karakter, atau dapat ditulis : S = N atau Length (S) = N.
3
Contoh : a. Jika diberikan string S = 'a1a2 ..... aN'. Maka LENGTH(S) = N. b. Jika diberikan string S = 'ABCD13AB', maka LENGTH(S) = 8.
1.1.5.2
CONCATENATION Operasi ini bekerja terhadap dua string dan hasilnya merupakan resultan
dari kedua string tersebut. Operasi ini hampir sama dengan operasi gabungan. Jika S1 dan S2 masing-masing adalah suatu string, maka bentuk operasi concatenation dinotasikan dengna : CONCAT(S1,S2). Contoh : Misal S1 = 'a1a2 ..... aN' dan S2 = 'b1b2 ..... bM' Maka CONCAT(S1,S2) = ' a1a2 ..... aNb1b2 ..... bM' Panjang dari string yang baru (resultan) merupakan jumlah panjang dari masingmasing string atau : LENGTH(CONCAT(S1,S2)) = LENGTH(S1) + LENGTH(S2) 1.1.5.3
SUBSTRING Operasi ini adalah operasi membentuk string baru, yang merupakan bagian
dari string yang diketahui. Notasinya adalah : SUBSTR(S,i,j) di mana : S = string yang diketahui. i dan j adalah integer i = posisi awal substring, 0 i LENGTH(S) j = banyak karakter yang diambil, 0 j LENGTH(S) dan 0 i+j-1 LENGTH(S) Contoh : Diberikan S = 'a1a2 ..... aN' ; i = 2 ; j = 4. Maka SUBSTR(S,i,j) = SUBSTR(S,2,4) = 'a2a3a4a5' Catatan : 1. LENGTH(SUBSTR(S,i,j)) = j
4
2. SUBSTR(CONCAT(S1,S2),1,LENGTH(S1)) = S1 3. SUBSTR(CONCAT (S1,S2),LENGTH(S1)+1,LENGTH(S2)) = S2
1.1.5.4
INSERT Operasi ini adalah untuk menyisipkan suatu string ke dalam string lain.
Bentuk umumnya adalah : INSERT(S1,S2,i). S1 dan S2 masing-masing adalah suatu string dan i adalah posisi awal S2 pada S1. Contoh : Misalkan:
S1 = 'a1a2 ..... aN' S2 = 'b1b2..... bM' INSERT(S1,S2,3) = 'a1a2b1b2..... bMa3a4 ..... aN'
1.1.5.5
DELETE Operasi ini digunakan untuk menghapuskan sebagian karakter dalam suatu
string. Bentuk umumnya adalah : DELETE(S,i,j) Maksudnya adalah menghapuskan sebagian karakter dalam string S, mulai dari posisi i dengan panjang j. Contoh : Diberikan string S = 'a1a2 ..... aN' DELETE(S,3,4) = 'a1a2a7a8 ..... aN' Catatan : INSERT(S1,S2,i) = CONCAT(CONCAT (SUBSTR(S1,1,i-1),S2), SUBSTR(S1,i,LENGTH(S1)-(i-1))) DELETE(S,i,j)=CONCAT(SUBSTR(S,1,i-1),SUBSTR(S,i+j,LENGTH(S)-(i+j1))) di mana :
1 i LENGTH(S1) 0 i LENGTH(S1) 0 i+j-1 LENGTH(S1) Untuk i,j integer.
5
1.2 DEKLARASI DATA DALAM BAHASA PEMROGRAMAN
PASCAL Var
Count : integer; Switch : boolean; Betha : char; Alamat : packed array[1..25] of char;
1.3 PEMETAAN KE STORAGE 1.3.1 INTEGER Bentuk mapping ke storage dari integer dapat dilakukan dengan beberapa cara, yaitu : 1. Skema Sign dan Magnitude 2. Skema One's Complement 3. Skema Two's Complement
a. Skema Sign and Magnitude Cara ini merupakan bentuk konvensional yang digunakan manusia untuk menyatakan suatu bilangan dalam bentuk biner. Di sini representasi bilangan positif dan negatif hanya dibedakan dengan tanda saja. Biasanya tanda positif atau negatif ditunjukkan oleh digit terdepan dari bentuk binernya, untuk representasi dengan jumlah digit tertentu. Contoh : + 7 à + 111 à representasi dengan 4 digit : 0111 -7
à - 111 à representasi dengan 4 digit : 1111
Dengan cara ini kita akan mendapatkan kesulitan dalam menentukan tanda pada saat melakukan operasi terhadap dua bilangan yang berbeda tandanya.
b. Skema Two's Complement dan One's Complement Kedua skema ini merupakan cara yang digunakan untuk mengatasi kesulitan yang telah disebutkan di atas. Diberikan bilangan integer non negatif X, X' dan R. Didefinisikan bahwa X' adalah komplemen dari X relatif terhadap R,
6
jika X + X' = R. X disebut sebagai bentuk true, sedangkan X' = R - X disebut bentuk komplemen. Bentuk komplemen X' = R - X menyatakan bilangan integer negatif X. Sedangkan bentuk true X menyatakan integer positif X. Skema Two's Complement menggunakan R = 2N. Skema One's Complement menggunakan R = 2N - 1. Contoh : Misal diberikan integer = 7, akan dicari bentuk binernya dengan skema Two's Complement untuk representasi 4 digit. X = 7 ; R = 24 ; à X + X' = R X' = R - X = 24 - 7 = 16 - 7 =9
à
dalam biner = 1001
1.3.2 KARAKTER Saat ini banyak sekali skema yang digunakan untuk merepresentasikan karakter dalam storage. Pada umumnya skema yang paling banyak digunakan adalah : 1. Extended Binary Coded Decimal Interchange Code (EBCDIC) 2. American Standard Code for Information Interchange (ASCII)
Pada skema EBCDIC digunakan kode 8 bit untuk menyatakan sebuah karakter. Jika dihitung, kemungkinan kombinasi seluruhnya adalah : 28. Sedangkan skema ASCII menggunakan kode 7 bit untuk menyatakan suatu karakter. Skema ini mempunyai jumlah kemungkinan kombinasi yang lebih sedikit jika dibandingkan dengan skema EBCDIC. Selain dua skema tersebut di atas ada sebuah skema yang disebut dengan kode Huffman. Pada cara ini, jumlah bit yang digunakan tergantung dari frekuensi penggunaan suatu karakter.
7
1.3.3 STRING Untuk mengetahui bentuk mapping pada storage dari suatu string, perlu diketahui beberapa hal yang menyangkut ruang untuk string yang bersangkutan, antara lain : - letak posisi awal (start) dan posisi akhir (terminal) - suatu pointer yang menunjukkan lokasi pada storage Ada tiga cara yang umum digunakan untuk mapping suatu string ke dalam storage. Misal diberikan dua string, yaitu : S1 = 'ABCDEFG' dan S2 = 'BCD'
a. Cara ke-1 Jika diberikan suatu informasi tentang : - nama string - starting address - panjang string Contoh : Nama String
Start
Panjang
String1
Ptr1
7
String2
Ptr2
3
Maka secara fisik bentuk formatnya pada storage adalah :
A
B
C
D
E
F G
Ptr1
B Ptr2
atau
A
B
C
D
Ptr2 Ptr1
8
E
F
G
C
D
b. Cara ke-2 Jika diberikan informasi sebagai berikut : - nama string - starting address - terminal address Misalnya diberikan tabel sbb : Nama String
Start
Terminal
String1
Ptr1s
Ptr1t
String2
Ptr2s
Ptr2t
Maka secara fisik bentuknya pada storage adalah :
A
B
C
D
E
F G
Ptr1s
B
C
Ptr2s Ptr1t
D
Ptr2t
atau
A
B
C
Ptr2s Ptr1s
D
E
F
Ptr2t
G Ptr1t
c. Cara ke-3 Jika diberikan informasi :
- nama string - starting address - suatu tanda yang menunjukkan batas string
Misalnya : Nama String
Start
String1
Ptr1
String2
Ptr2
9
Maka bentuknya secara fisik pada storage adalah :
A
B
C
D
E
F #
B
Ptr1
C
D #
Ptr2
Selain cara-cara di atas, representasi suatu string pada storage dapat pula dalam bentuk packed atau unpacked. Suatu string yang direpresentasikan dalam bentuk packed terbagi atas beberapa word. Banyaknya karakter untuk masingmasing word tergantung dari kode yang digunakan oleh mesin (bitnya). Secara umum jumlah word yang digunakan untuk merepresentasikan string S dalam storage dengan R karakter per word adalah : LENGTH(S)
notasi
disebut dengan ceiling function
K
Contoh : Misal diberikan string S = "StrukturData", direpresentasikan dalam 4 karakter per word dalam bentuk packed. Maka secara fisik dapat digambarkan : Stru
ktur
Data
Jumlah Word : 3, Jumlah Karakter/Word : 4
Sedangkan cara unpacked, setiap word terdiri hanya satu karakter, berarti jumlah word yang diperlukan untuk merepresentasikan suatu string S adalah LENGTH(S). Contoh : Diberikan string S = "StmikAsia". Representasinya dalam bentuk unpacked adalah : S
t
m
i
k
10
A
s
i
a
BAB II ARRAY DAN RECORD
Sebuah array dapat dikatakan sebagai suatu himpunan terurut dengan elemenelemen homogen. Terurut, dimaksudkan bahwa elemen pertama, elemen kedua, dst masing-masing dapat diidentifikasi. Sedangkan homogen berarti masing-masing elemen tersebut mempunyai tipe data yang sama. Array dapat dikelompokkan atas 2 bagian, yaitu : 1. Array satu dimensi. 2. Array multi dimensi.
2.1 ARRAY SATU DIMENSI Bentuk array yang paling sederhana adalah array satu dimensi. Array jenis ini dapat dianggap sebagai sebuah vektor. Suatu array A berdimensi satu dengan N buah elemen, secara fisik dapat digambarkan sebagai berikut : A(1)
A(2)
.....
A(I)
.....
A(n)
Indeks dari elemen suatu array menyatakan posisinya dalam urutan secara umum suatu array A berdimensi satu dengan elemen berjenis data T yang mempunyai indeks dari L s/d U dituliskan sbb: A(L:U) = {A(I)} Untuk I = L, L+1, L+2, ................., U-1, U, dimana masing-masing A(I) berjenis data T. L disebut sebagai batas bawah dari indeks A dan U sebagai batas atas dari A. Jumlah elemen dalam suatu array disebut sebagai range. Range dari array A(L:U) adalah U - L + 1. Range dari array B(1:N) adalah N - l + 1= N.
2.2 ARRAY MULTI DIMENSI Array dua dimensi adalah salah satu contoh dari array jenis multi dimensi (dimensi banyak). Array ini elemen-elemennya merupakan array pula. Bentuk yang dianggap dapat mewakili array dua dimensi ini adalah matriks. Suatu array B yang
11
terdiri atas M elemen dimana masing-masing elemennya berupa array dengan N elemen, dapat digambarkan sebagai suatu tabel MxN, dengan bentuk sbb: 1
2
3
...
J
...
N
1 2 3 ... I ... M
Array ini dituliskan : B(1:M,1:N) = {B(I,J)}, Untuk I = 1,2,...,M J = 1,2,...,N Jumlah elemen (range) dari array B ini adalah M x N. Secara umum, array 2 dimensi B dengan batas bawah indeks pertama L1, batas atas indeks pertama U1, batas bawah indeks kedua L2 batas atas indeks kedua U2, dituliskan: B(L1 : U1, L2 : U2) = {B(I,J)} Untuk L1 < I < U1 dan L2 < J < U2 Jumlah elemen baris dari array B adalah : ( U2 – L2 + 1 ) Jumlah elemen kolom dari array B adalah : ( U1 - L1 + 1) Jumlah total elemen array B adalah : (U2 – L2 + 1 )(U1 - L1 + 1)
2.2.1 CROSS SECTION Yang dimaksud dengan Cross section dari array 2 dimensi adalah suatu himpunan yang anggotanya adalah elemen-elemen dalam satu baris saja atau satu kolom saja. Notasinya menggunakan *. Contoh : Misal diberikan array B(1:M,1:N).
B(4,*) = {B(4,1), B(4,2), ...,B(4,N)} B(*,4) = {B(1,4), B(2,4), ...,B(M,4)} 12
2.2.2 TRANSPOSE Transpose dari suatu array dua dimensi, adalah suatu array dua dimensi pula dengan menukar posisi indeksnya. Transpose dari array berukuran M x N adalah suatu array berukuran N x M. Transpose dari suatu array dari B dinotasikan dengan BT, dan didefinisikan: B(I,J) = BT (J,I) Selanjutnya secara umum, suatu array A berdimensi N dapat dituliskan sbb: A(L1:U1,L2:U2,...,LN:UN) Jumlah elemen array ini adalah : N (U1 - L1 + 1)(U2- L2+ 1)... (UN - LN + 1) (UK - LK + 1) k=1 Sebagai contoh perhatikan sebuah array berdimensi 3 yang menggambarkan (berisi) jumlah mahasiswa STMIK Asia untuk kelas reguler dan eksekutif. Array ini dapat digambarkan sbb :
2 Eksekutif 2 mlm 1 Reguler 1 pg
P
kls kls 2D 1E
w
kls kls 5A 4 kls B 3C
Jika array ini diberi nama Asia, maka bentuknya dapat dituliskan sbb: Asia(1:2,1:2, A:E) = {Asia(i,j,k)} dimana
I = 1,2 (1 = pria, 2 = wanita) J = 1,2 (1 = reguler, 2 = eksekutif) K = A,B,C,D,E (kelas A s/d E)
Seluruh mahasiswa reguler dapat ditunjukkan dengan Asia (*,1,*) sedangkan seluruh mahasiswa eksekutif dapat ditunjukkan dengan Asia (*,2,*)
13
2.3 DEKLARASI ARRAY DALAM BAHASA PEMROGRAMAN. Misal diberikan array dengan nama A yang mempunyai 24 elemen dengan masing-masing elemen berjenis data integer, maka deklarasinya dalam bahasa pemrograman adalah sbb:
VAR A : ARRAY [1..24] OF INTEGER;
Dalam mendeklarasikan suatu array ada 3 hal yang harus ada pada deklarasi tersebut, yaitu: 1. Nama array 2. Range dari indeksnya 3. Tipe elemen-elemen datanya
2.4 PEMETAAN ARRAY KE STORAGE Ada beberapa cara untuk menyatakan suatu array pada storage, tetapi konsepnya hampir sama dengan apa yang ada pada data fungsi. 2.4.1 ARRAY SATU DIMENSI Misal diberikan array satu dimensi dengan nama A yang mempunyai indeks 1 s/d N, yaitu A(1:N). Secara fisik array A(1:N) dapat digambarkan sbb: A(1)
A(2)
A(3)
...
A(I)
...
A(N)
Yang perlu kita ketahui disini adalah letak elemen ke I dari array A(1:N), atau letak masing-masing elemen array pada storage. Letak suatu elemen biasanya disebut sebagai starting address atau starting location atau base location. Untuk mengetahui starting address suatu elemen array, perlu diketahui lebih dulu antara lain : 1. Starting address dari array yang bersangkutan. 2. Ukuran masing-masing elemen array atau ruang yang digunakan masing-masing elemen array. Misal starting address dari array A(1:N) adalah B dan masing-masing elemennya menggunakan ruang sebanyak S bit. Maka starting address elemen ke I dari array A(1:N) adalah : B + ( I - 1 ) * S Hal ini disebabkan ada (I - 1) elemen array A, masing-masing dengan ukuran atau panjang S secara fisik mendahului elemen ke I pada array tersebut.
14
Secara umum dapat dikatakan bahwa : Starting address elemen ke I dari array A(L:U) adalah (B +( I – L ) * S jika starting address array A adalah B dan masing-masing elemenya menggunakan ruangan sebanyak S bit.
2.4.2 ARRAY MULTI DIMENSI Prinsip yang digunakan disini tetap didasarkan pada array satu dimensi. Oleh karena itu untuk array multi dimensi, linierisasi-nya dapat dilakukan berdasarkan baris atau kolom. Contoh : Misal diberikan array A(1:3,1:4). Array ini secara fisik dapat digambarkan sbb : 1
2
3
4
1 2 3
Linierisasi menurut baris akan mengakibatkan bentuk diatas menjadi :
1
2
3
Jika B adalah starting address array A(1:3,1:4) dan S adalah ruang yang digunakan oleh masing-masing elemennya, maka starting address dari elemen A(I,J) adalah : B + (I-1) * 4 * S + (J-1) * S Hal ini karena ada ( I - 1) baris, masing-masing dengan panjang 4 * S yang mendahului baris dimana elemen A(I,J) berada dan ada (J-1) elemen masing-masing dengan panjang S yang mendahului elemen A(I,J) pada baris ke I. Contoh Dari array A(1:3,1:4) akan dicari starting adress elemen A(2,4).
baris
1
baris
2
A(2,4) 15
baris
3
Starting address A(2,4)
= B + (2 - 1) * 4 * S + (4 - 1) * S =B+7*S
Secara umum elemen A(I,J) dari array A(l:U,L:U) mempunyai starting address : B + (I-L1) * (U2-L2+1) * S + (J-L2) * S
Alternatif lain untuk linierisasi adalah dengan menggunakan cara kolom jika diberikan array A(1:3,1:4) diatas, maka bentuk linierisasinya :
kolom
1
kolom
2
kolom
3
kolom
4
Jika B adalah starting address dari array A(1:4,1:6) dan S adalah ruang digunakan untuk masing-masing elemennya, maka starting address dari A(I,J) adalah : B + (J - 1) * 4 * S + (I - 1) * S Hal ini disebabkan ada (J - I) kolom masing-masing dengan 4 elemen yang panjangnya s yang mendahului kolom tempat elemen A(I,J) berada dan ada (I-1) elemen masingmasing dengan panjang S yang mendahului elemen A(I,J) pada kolom ke J. Secara umum dapat dikatakan bahwa elemen A(I,J) dari array A(L1:U1,L2:U2), menurut kolom mempunyai starting address : B + (J-L2) * (U1-L1+1) * S + (I-L1) * S Jika starting adress array tersebut adalah B dan masing-masing elemenya menggunakan ruang sebanyak S bit. Contoh : Misal diberikan array K(1:4,1:6) dengan starting address B dan masing-masing elemenya menggunakan ruang S bit. Maka starting adress dari elemen k(2,4) adalah : = B + (4 - 1) * (4-1+1) * S + (2 - 1) * S = B + 3 * 4* S + 1 * S = B + 13 * S
16
2.5 RECORD Record adalah himpunan dari elemen-elemen yang heterogen. Heterogen adalah elemen-elemennya dapat mempunyai tipe data yang berbeda. Beberapa hal yang perlu diketahui dalam record sbb: 1. ELEMENTARY ITEM adalah suatu field yang tidak mempunyai subfield. 2. GROUP ITEM adalah suatu field yang mempunyai subfield. 3. TUPEL adalah gabungan atribut yang menjadi suatu informasi dari proses basis data. Contoh RECORD : PEGAWAI Job Tittle
Emp. No
Pay Rate
Analys
00012724
1.000.000
Programmer
00023451
800.000
( String(20) )
( String(8) )
( Real(9,2) )
Name
Telp. No
Bob Geldof
7801725
Ceu Rika
7521475
( String(25) )
( String(7) )
Record-record yang tipenya sama : FILE. Untuk menyatakan suatu data dalam record yang mempunyai identifikasi yang khusus, maka harus punya 1 field khusus yang disebut KEY (kunci field).
2.6 DEKLARASI RECORD DALAM BAHASA PEMROGRAMAN PROGRAM DALAM PASCAL Type Pegawai = Record; Job_Tittle : String[20]; Emp_No : String[8]; Pay_Rate : Real; Name
: String[25];
Telp_No : String[7]; End;
17
BAB III STACK
3.1
LINEAR LIST Linear List adalah suatu struktur data yang merupakan himpunan terurut. Misal
didefinisikan suatu linear list A yang terdiri atas T buah elemen sebagai berikut : A = [a1, a2, .........., aT] Jika T = 0, maka A dikatakan sebagai “Null List”. Suatu elemen dari sembarang posisi pada linear list A dapat dihilangkan. Sebaliknya, suatu elemen baru dapat dimasukkan ke dalam list dan dapat menempati sembarang posisi pada list tersebut. Jadi suatu linear list dapat berkurang atau bertambah setiap saat.
3.2 DEFINISI STACK Stack adalah suatu bentuk khusus dari linear list di mana operasi penyisipan dan penghapusan atas elemen-elemennya hanya dapat dilakukan pada satu sisi saja yang disebut sebagai “TOP”. Misal diberikan Stack S sebagai berikut : S = [ S1, S2, .........., ST ] maka TOP(S) = ST. Untuk menunjukkan jumlah elemen suatu stack digunakan notasi NOEL. Dari stack di atas, maka NOEL(S) = T. Selanjutnya, jika diberikan sebuah stack S = [A,B,C,D], maka stack S ini dapat digambarkan sebagai berikut :
A D
Top
A
B
C
D
B Top
C
C
B
D
Top
D
A Top
18
C
B
A
3.3 OPERASI DASAR PADA STACK Ada empat operasi dasar yang didefinisikan pada stack, yaitu : 1. CREATE(stack) 2. ISEMPTY(stack) 3. PUSH(elemen,stack) 4. POP(stack)
3.3.1
CREATE
Operator ini berfungsi untuk membuat sebuah stack kosong dan didefinisikan bahwa : NOEL(CREATE(S)) = 0 dan TOP(CREATE(S)) = null
3.3.2
ISEMPTY
Operator ini berfungsi untuk menentukan apakah suatu stack adalah stack kosong. Operasinya akan bernilai boolean, dengan definisi sebagai berikut : ISEMPTY(S) = true, jika S adalah stack kosong = false, jika S bukan stack kosong atau ISEMPTY(S) = true, jika NOEL(S) = 0 = false, jika NOEL(S) 0
Catatan : ISEMPTY(CREATE(S)) = true.
3.3.3
PUSH
Operator ini berfungsi untuk menambahkan satu elemen ke dalam stack. Notasi yang digunakan adalah : PUSH(E,S) Artinya : menambahkan elemen E ke dalam stack S. Elemen yang baru masuk ini akan menempati posisi TOP. Jadi : TOP(PUSH(E,S)) = E.
19
Akibat dari operasi ini jumlah elemen dalam stack akan bertambah, artinya NOEL(S) menjadi lebih besar atau stack menjadi tidak kosong (ISEMPTY(PUSH(E,S)) = false).
3.3.4
POP
Operator ini berfungsi untuk mengeluarkan satu elemen dari dalam stack. Notasinya : POP(S) Elemen yang keluar dari dalam stack adalah elemen yang berada pada posisi TOP. Akibat dari operasi ini jumlah elemen stack akan berkurang atau NOEL(S) berkurang dan elemen pada posisi TOP akan berubah. Operator POP ini tidak dapat digunakan pada stack kosong, artinya : POP(CREATE(S)) = error condition
Catatan : TOP(PUSH(E,S)) = E
3.4 DEKLARASI STACK PADA BAHASA PEMROGRAMAN Dalam bahasa pemrograman, untuk menempatkan stack biasanya digunakan sebuah array. Tetapi perlu diingat di sini bahwa stack dan array adalah dua hal yang berbeda. Misalkan suatu variabel S adalah sebuah stack dengan 100 elemen. Diasumsikan elemen S adalah integer dan jumlah elemennya maksimum adalah 100 elemen. Untuk mendeklarasikan stack dengan menggunakan array, harus dideklarasikan pula variabel lain yaitu TOP_PTR yang merupakan indeks dari array. Variabel TOP_PTR ini digunakan untuk menyatakan elemen yang berada pada posisi TOP dalam stack tersebut. Selanjutnya gabungan kedua variabel ini diberi nama STACK_STRUCT. Kemudian didefinisikan bahwa : NOEL(S) = TOP_PTR ISEMPTY(S) = TRUE, jika TOP_PTR = 0 dan FALSE, jika TOP_PTR > 0.
20
Maka bentuk deklarasinya dalam PASCAL adalah : TYPE Stack_Struct = Record Stack : array[1..100] of integer; TopPtr : integer; End; VAR S : Stack_Struct;
Selanjutnya, untuk keperluan operasi PUSH dan POP harus dibuat suatu prosedur tersendiri, yaitu : PROCEDURE PUSH(Eon : integer); Begin If (S.TopPtr < NoelMax) Then Begin S.TopPtr := S.TopPtr + 1; S.Stack [S.TopPtr] := Eon End Else Overflow_Condition End;
PROCEDURE POP(Eoff : integer); Begin If (S.TopPtr > 0) Then Begin Eoff := S.Stack[S.TopPtr]; S.TopPtr := S.TopPtr - 1 End Else Underflow_Condition End;
Catatan : Overflow adalah suatu keadaan di mana kita melakukan operasi PUSH terhadap stack dalam keadaan penuh. Underflow adalah keadaan di mana kita melakukan operasi POP
21
terhadap stack kosong. Eon adalah elemen yang akan dimasukkan ke dalam stack dan Eoff adalah elemen yang akan dikeluarkan dari dalam stack.
3.5 PENGGUNAAN/ APLIKASI STACK Logika stack digunakan untuk menyelesaikan berbagai macam masalah. Antara lain digunakan pada compiler, operating system dan dalam program-program aplikasi. Berikut ini tiga buah contoh aplikasi stack, yaitu :
3.5.1
MATCHING PARENTHESES
Proses ini dilakukan compiler untuk memeriksa kelengkapan tanda kurung yang terdapat pada suatu ekspresi aritmetik. Sedangkan stack di sini digunakan sebagai tempat prosesnya. Algoritma yang digunakan adalah : 1. Elemen-elemen suatu ekspresi aritmetik (string) di-Scan dari kiri ke kanan. 2. Jika ditemukan simbol "(" atau "Left parenthesis", maka simbol tersebut di-push ke dalam stack. 3. Jika ditemukan simbol ")" atau "Right parenthesis", maka isi stack diperiksa.
Jika stack kosong terjadi kesalahan. berarti : ada simbol ")", tetapi tidak ada simbol "(" yang seharusnya mendahului.
Jika stack tidak kosong artinya ada pasangannya dan langsung di-POP keluar stack.
Misalkan NEXT CHAR adalah suatu karakter terakhir dalam suatu string. Berikut ini bentuk flowchart (logika proses) yang digunakan pada proses matching ini :
22
position NEXT CHAR at end of string
y
end of string
stack empty
y valid syntax
n
n
invalid syntax(unclosed left parenthesis) found "("
y
done
push "(" on to stack
n
found ")"
y
stack empty
y
invalid syntax(unclosed left parenthesis)
n
n
pop stack
done
increament NEXT CHAR to next character in string
3.5.2
NOTASI POSTFIX
Bentuk aplikasi stack yang lain adalah mengubah suatu ekspresi aritmatik (string) ke dalam notasi postfix. Notasi postfix ini digunakan oleh compiler untuk menyatakan suatu ekspresi aritmatik dalam bahasa tingkat tinggi (high level language). Stack digunakan oleh compiler untuk mentransformasikan ekspresi aritmatik menjadi suatu ekspresi dalam bentuk/notasi postfix. Contoh : Misal diberikan ekspresi aritmatik : A + B ; Maka bentuknya dalam notasi postfix menjadi : AB+ Urutan (prioritas) dari operator adalah : 1. Perpangkatan (^) 2. Perkalian (*) atau Pembagian (/) 3. Penjumlahan (+) atau Pengurangan (-)
23
Aturan yang digunakan dalam proses transformasi tersebut adalah : 1. Ekspresi aritmatik yang diberikan di- "Scan" dari kiri ke kanan. 2. Bila simbol yang di-scan adalah "(", maka simbol tersebut di push ke dalam stack. 3. Bila simbol yang di-scan adalah ")", maka seluruh isi stack di pop keluar mulai dari simbol "(" yang pertama ditemukan dalam stack. 4. Bila simbol adalah operator, maka dilakukan perbandingan dulu dengan simbol (operator) yang berada pada posisi top dalam stack. a. Jika derajatnya setara atau lebih rendah dari simbol yang berada pada posisi top, maka top stack di-pop keluar sebagai output dan simbol yang baru dipush ke dalam stack. b. Jika derajatnya lebih tinggi dari simbol yang berada pada posisi top, maka simbol (operator) yang di-scan tersebut di-push ke dalam stack. 5. Bila simbol yang di-scan adalah operand, maka simbol tersebut langsung sebagai output. 6. Bila simbol adalah ";" maka seluruh isi stack di-pop sebagai output.
Contoh : Misal diberikan sebuah ekspresi aritmatik dengan bentuk sbb: ( (A + B) * C / D + E ^ F ) / G ; Selanjutnya akan dicari bentuk ekspresi diatas dalam notasi postfix. Proses yang dilakukan dapat digambarkan dalam tabel berikut : Urutan
1 2
3 4 5
6
7
8
9 10
11
12
13
14
15
16
17
18
Scan
(
(
A + B )
*
C /
D
+
E
^
F
)
/
G
;
Top
(
(
(
+ + (
*
*
/
/
+
+
^
^
/
/
(
(
(
(
(
(
(
(
(
(
+
+
(
(
(
(
Proses Simbol Yang di
Output
A
B +
C * D
24
/
E
F
^+
G
/
Jadi ekspresi aritmatik : ( ( A + B ) * C / D + E^F ) / G ; dalam notasi postfix menjadi : AB+D*C/EF^+G/
3.5.3
PROSES REKURSIF
Stack juga dapat digunakan untuk menelurusuri suatu program atau procedure yang rekursif. Berikut ini sebuh contoh yang menyelesaikannya menggunakan proses rekursif. Persoalan : Agar diperoleh uang sebanyak 1.000.000 rupiah pada 25 tahun yang akan datang, berapakah banyak uang yang harus didepositokan saat ini? dianggap bahwa tingkat bunga tidak berubah selama 25 tahun yaitu sebesar 8% per/tahun.
Penyelesaian : Untuk menyelesaikan masalah ini akan digunakan logika stack yaitu : - pada tahun ke-25 jumlah uang = Rp. 1.000.000,- pada tahun ke-24 jumlah uang = Rp. 1.000.000 / (1 + 0.8) - pada tahun ke-23 jumlah uang = . dst Berikut ini sebuah program PASCAL yang mengandung suatu procedure rekursif untuk menghitung jumlah uang diinginkan.
PROGRAM DEPOSITO ; CONST
Goal = 1000000; Rate = 0.08;
VAR
Ju : Real; Thn: Integer;
PROCEDURE Hitung (VAR Thn : Integer); BEGIN IF (Thn > 0) THEN
25
BEGIN Ju := Ju/(1.0 + Rate); Thn := Thn - 1; Hitung(Thn); END; END; BEGIN Thn := 25; Ju := Goal; HITUNG(Thn); WRITE(Ju); END. Pemanggilan pertama procedure HITUNG dimana nilai Thn =25
Top
9
Pemanggilan kedua procedure HITUNG dimana nilai Thn = 24
Top
5 9
Pemanggilan ketiga procedure HITUNG, dimana nilai Thn = 23
Top
5 5 9
26
Setelah 25 kali pemanggilan procedure HITUNG keadaan stack adalah : Top
5 5 24 kali pemanggilan statement langkah ke 5
5 5 9
3.6 MAPPING KE STORAGE DARI STACK Bentuk mapping ke storage dari stack yang paling sederhana adalah dengan menggunakan pendekatan array satu dimensi. Hal ini karena sarana yang digunakan untuk menyatakan suatu stack adalah array. Jika diberikan stack S dengan m elemen maka bentuk mappingnya seperti mapping array satu dimensi dengan m elemen.
start stack S
batas/start struktur data lain
TOP elemen
Selanjutnya jika terdapat dua stack S1 dan S2 masing-masing dengan jumlah maksimum elemennya adalah M dan N, maka kedua stack ini dialokasikan dalam dengan bentuk sbb:
start S1
TOP S1 (sementara)
start S2
TOP S2 (sementara)
27
start struktur data lain
Konsep mapping seperti diatas dianggap tidak efisien, terutama jika S1 dan S2 tidak penuh pada saat yang bersamaan.
Cara yang dianggap lebih baik adalah : Jika diketahui bahwa jumlah elemen S1 dan S2 tidak melebihi jumlah tertentu, misal N. NOEL(S1) + NOEL(S2) <= N Maka bentuk mapping yang digunakan adalah :
start s1
TOP s1 (sementara)
TOP s2 (sementara)
28
start s2
BAB IV QUEUE
4.1 DEFINISI Queue adalah suatu linear list di mana operasi DELETE terjadi pada sisi depan (FRONT) dan operasi INSERT terjadi pada sisi belakang (REAR). Jika diberikan suatu Queue Q dengan elemen-elemennya yang terdiri atas Q1, Q2, ....., QT maka queue Q dituliskan Q = [ Q1, Q2, .........., QT ] FRONT(Q) = Q1
REAR(Q) = QT
Selanjutnya untuk menyatakan jumlah elemen dalam suatu queue Q digunakan notasi NOEL(Q).
Catatan : Satu pengoperasian berlaku hanya untuk satu elemen.
4.2 GAMBAR QUEUE Untuk menggambarkan suatu queue dapat dilakukan beberapa cara , yaitu : Misal : diberikan Queue Q = [A, B, C, D, E, F], maka Queue Q dapat digambarkan sebagai berikut : A
B
C
D
E
FRONT
F
F REAR
E
D
C
REAR
B
A FRONT
atau dapat pula digambarkan dengan posisi tegak.
29
4.3 PRINSIP KERJA QUEUE Prinsip kerja Queue adalah FIFO (First In First Out), di mana data yang masuk terlebih dahulu akan keluar pertama.
4.4 OPERASI-OPERASI PADA QUEUE (Q) Terdapat empat operasi dasar yang didefinisikan pada queue, yaitu : 1. CREATE Bentuk Umum : CREATE(Queue) Suatu operasi CREATE(Q) akan menghasilkan suatu queue kosong dengan nama Q, dan didefinisikan bahwa : NOEL(CREATE(Q)) = 0 FRONT(CREATE(Q)) = tidak terdefinisi REAR(CREATE(Q)) = tidak terdefinisi
2. ISEMPTY Bentuk Umumnya adalah : ISEMPTY(queue) Jika Q adalah Queue, maka ISEMPTY(Q) adalah suatu operasi yang digunakan untuk memeriksa apakah Queue Q adalah queue kosong. Jika hasil dari operasi ini akan berjenis data boolean (true/false), dengan bentuk sebagai berikut : ISEMPTY(Q) = True, jika Q adalah queue kosong. = False, jika Q bukan queue kosong.
3. INSERT Bentuk Umumnya : INSERT(elemen, Queue) INSERT(E,Q), di mana E = elemen dan Q = queue, adalah suatu operasi yang digunakan untuk memasukkan elemen E ke dalam queue Q. Didefinisikan, bahwa elemen E akan menjadi elemen yang berada pada posisi REAR dari queue Q. Akibat dari operasi ini adalah : - REAR(INSERT(E,Q)) = E - NOEL(Q) bertambah satu dan QNOEL adalah E
30
Jika Q adalah queue kosong, maka : ISEMPTY(INSERT(E,Q)) = False Dalam bentuk statement Pascal, biasanya dituliskan : IF ISEMPTY(Q) Then front(insert(E,Q)) = E Else front(insert(E,Q)) = front(Q) ;
4. REMOVE Bentuk Umum : REMOVE(elemen, queue) REMOVE(Q) berarti mengeluarkan elemen Q yang berada pada posisi FRONT. Akibat dari operasi ini, elemen Q akan berkurang satu dan elemen kedua (elemen yang berada disebelahnya) akan menjadi elemen yang berada pada posisi FRONT dari queue Q ini. Selanjutnya, jika Q adalah queue kosong, maka REMOVE(Q) akan menghasilkan suatu Error. IF NOEL(Q) = 0 Then Remove(Q) = erroe_condition Remove(create(Q)) = error_condition
4.5 DEKLARASI QUEUE DALAM PASCAL Dalam bahasa pemrograman biasanya tidak ada fasilitas queue (built in queue). Untuk itu setiap programmer harus mendefinisikan sendiri dengan bantuan fasilitas yang ada. Pada umumnya fasilitas yang digunakan untuk mendeklarasikan queue adalah Array. Bentuk deklarasinya dalam bahasa Pascal adalah sebagai berikut : TYPE StrukQueue = Record Q : Array[1..100] of integer; Front, Rear : integer; End; VAR Q : StrukQueue;
Selanjutnya untuk keperluan operasinya (bentuk proses atau logikanya), harus dibuat suatu procedure tersendiri dan disesuaikan dengan aturan-aturan yang berlaku (yang telah didefinisikan). Berikut ini contoh sebuah procedure yang digunakan untuk
31
menggantikan operator insert. Pada procedure berikut ini dimisalkan eon adalah elemen yang akan dimasukkan ke dalam queue dan noelmax adalah kapasitas maximum elemenelemen yang dapat ditampung dalam queue. Procedure INSERT (eon : integer); Begin If (q.rear < noelmax) Then Begin q.rear := q.rear + 1; q.queue[q.rear] := eon; If (q.front = 0) Then q.front := 1 End Else overflow_condition End;
Procedure REMOVE(var eoff : integer); Begin If (q.front > 0) Then Begin eoff := q.queue[q.front]; If (q.front = q.rear) Then Begin q.front := 0; q.rear := 0; End Else
q.front := q.front + 1
End Else
underflow-condition
End;
32
4.6 CIRCULAR QUEUE Misal diberikan queue Q dengan jumlah maksimum elemen sebanyak 100, yang digambarkan sebagai berikut :
1
2
3
4
5
.................................
99
100
Queue di atas diisi secara berurutan empat elemen A, B, C dan D, sehingga bentuknya menjadi:
A
B
C
D
1
2
3
4
5
6
FRONT = 1
7 ;
8
......................
99
100
REAR = 4
Kemudian dilakukan operasi REMOVE dua kali berurutan, sehingga bentuknya menjadi :
1
2
C
D
3
4
5
FRONT = 3
6 ;
7
8
......................
99
100
REAR = 4
Selanjutnya dilakukan operasi INSERT untuk 3 elemen secara berurutan, yaitu E, F dan G, maka bentuknya menjadi :
1
2
C
D
E
F
G
3
4
5
6
7
FRONT = 3
;
8
......................
99
100
REAR = 7
Kemudian dilakukan operasi REMOVE lagi berurutan terhadap dua elemen, sehingga bentuknya menjadi :
33
1
2
3
4
FRONT = 5
E
F
G
5
6
7
;
8
......................
99
100
REAR = 7
Terlihat bahwa elemen-elemen queue bergerak terus dari kiri ke kanan sepanjang arraynya. Apa yang terjadi bila suatu saat REAR = 100 dan kita masih akan memasukkan suatu elemen ke dalam queue ? Dalam keadaan ini, batas maksimum telah dicapai, padahal kita masih ingin menambah/memasukkan beberapa elemen lagi. Salah satu cara/pendekatan untuk menyelesaikan masalah seperti ini adalah dengan menambah ukuran array yang digunakan. Artinya kita harus mendeklarasikan array dengan ukuran yang besar untuk menempatkan queue tersebut. Tetapi cara ini dianggap tidak efektif, karena keadaan serupa masih dapat muncul kembali. Cara lain yang dianggap lebih baik adalah dengan mengubah queue tersebut ke dalam bentuk yang disebut CIRCULAR. Berikut ini contoh bentuk circular tersebut : ... Q(5)
Q(N-3)
Q(4) Q(N-2) Q(3) Q(N-1)
Q(2) Q(N) Q(1)
Dalam hal ini kondisi dari suatu queue kosong adalah :FRONT = REAR = 0 Jika queue hanya berisi dua elemen, maka bentuknya adalah :
F
R
34
Selanjutnya jika elemen queue melampaui batas yang ada sedangkan kita masih memiliki ruang yang kosong, maka posisi FRONT dan REAR harus di-'reset' dulu agar kita bisa memasukkan elemen ke dalam queue tersebut.
Berikut ini sebuah algoritma yang digunakan untuk operasi INSERT start
REAR pd akhir array?
ya Move REAR ke posisi yg pertama dr array
tdk Move REAR satu posisi dalam array
FRONT & REAR pd posisi yg sama ?
ya
overflow
tdk
Insert elemen pd posisi REAR dlm array
ya satu-satunya elemen pd queue
Move FRONT pd posisi tsb dlm array
tdk
selesai
35
Algoritma yang digunakan untuk operator REMOVE pada circular queue : start
queue kosong ?
ya underflow
tdk REMOVE elemen pada posisi FRONT
satusatunya elemen pd queue ?
ya
reset FRONT dan REAR = 0
tdk
FRONT pd akhir array ?
ya
tdk move FRONT pd posisi yang baru dalam array
selesai
36
move FRONT ke posisi awal dari array
selesai
Sedangkan bentuk procedure-nya dalam bahasa Pascal adalah sebagai berikut PROCEDURE insert (eon : integer); BEGIN IF (q.rear = n)
THEN q.rear := 1 ELSE q.rear := q.rear + 1; IF (q.rear = q.front) THEN overflow_condition
ELSE BEGIN q.queue[q.rear] := eon; IF (q.front = 0) THEN q.front := 1 end; end;
PROCEDURE remove (eoff : integer); BEGIN IF (q.front = 0)
THEN underflow_condition
ELSE BEGIN eoff := q.queue[q.front] ; IF (q.front = q.rear) THEN BEGIN q.front := 0; q.rear := 0 END
ELSE IF (q.front = n) THEN q.front := 1 ELSE q.front:=q.front + 1 END; END;
37
BAB V LINKED LIST
5.1 PENDAHULUAN. Dalam suatu linear list kita dapat melakukan operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang posisi. Misalkan ada 1500 item yang merupakan elemen dari suatu linear list. Jika elemen ke-56 akan kita keluarkan, maka elemen ke-1 s/d elemen ke-55 tidak akan berubah posisinya pada linear list tersebut. Tetapi elemen ke57 akan menjadi elemen ke-56, elemen ke-58
akan menjadi elemen ke-57 dst.
Selanjutnya, jika kita sisipkan satu elemen pada posisi setelah elemen ke-41, maka elemen ke-42 s/d elemen ke-1500 akan berubah posisinya. Untuk menyatakan keadaan diatas diperlukan suatu konsep yang berbeda dengan konsep sekuensial sebelumnya. Linked list merupakan suatu cara non-sekuensial yang digunakan untuk merepresentasikan suatu data.
5.2 DEFINISI Linked list (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node) dimana urutannya ditentukan oleh suatu pointer. Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu :
INFO, berisi informasi tentang elemen data yang bersangkutan.
NEXT
(link field/ next pointer field), berisi alamat dari elemen (node)
selanjutnya yang dituju.
Berikut ini sebuah contoh linked list yang terdiri atas 4 node : start
info
next
info
next
info
next
info
next null
node ke-1
node ke-2
node ke-3
node ke-4
Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tsb. adalah node terakhir.
38
Node-node dalam linked list tidak harus selalu digambarkan paralel seperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan seperti berikut : info
info
next
next null info
next info
next
CATATAN : -
Ada dua hal yang menjadi kerugian dengan representasi suatu data dengan linked list ini, yaitu : 1. Diperlukan ruang tambahan untuk menyatakan/tempat field pointer. 2. Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam linked list.
-
Sedangkan keuntungannya adalah : 1. Jenis data yang berbeda dapat di-link. 2. Operasi REMOVE atau INSERT hanya dilakukan dengan mengubah pointernya saja.
5.3 OPERASI DASAR PADA LINKED LIST Ada beberapa aturan yang didefinisikan pada operasi didalam linked list, yaitu :
Jika P adalah suatu variabel pointer, maka nilainya adalah alamat atau lokasi dari variabel
lain yang dituju.
Operasi yang didefinisikan pada suatu variabel pointer adalah : 1. Test apakah sama dengan NULL. 2. Test untuk kesamaan dengan variabel pointer lain. 3. Menetapkan sama dengan NULL. 4. Menetapkan menuju ke node lain.
39
Notasi yang didefinisikan sehubungan dengan operasi diatas adalah : 1. NODE(P), artinya node yang ditunjuk oleh pointer P. 2. INFO(P), artinya nilai INFO dari node yang ditunjuk pointer P. 3. NEXT(P), artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer P.
Sebagai contoh, perhatikan linked list dibawah ini : info start
info
next
next info
B
A
next
C
node ke-2 node ke-1
node ke-3
P
info
next
D
null
node ke-4
NODE(P) = node yang ditunjuk oleh P yaitu node pertama. INFO(P) = A NEXT(P) = node ke-dua INFO(NEXT(NEXT(P))) = C
5.4 MENGHAPUS SUATU NODE DARI LINKED LIST (REMOVE) Untuk menghapus node dalam linked list digunakan procedure FREENODE. Jika Q adalah suatu variabel pointer, maka FREENODE(Q) akan menyebabkan node yang ditunjuk oleh variabel pointer Q dihapus dari linked list. Perhatikan linked list berikut :
langkah ke-1 : Q := Next(P) info
next
info
P
next
info
Q
next
info
next ...
40
langkah ke-2 : Next(P) := Next(Q) info
next
info
next
info
P
next
info
next
Q
langkah ke-3 : Freenode(Q)
procedure Freenode(Q) (a)
Next(Q) := Avail Q
info
next
Avail
info
next
next
info ...
null
P
(b)
Info(Q) := Null
(c)
Avail := Q Q
next
Avail
next
info
next
info ...
next null
41
next
5.5 MENYISIPKAN SUATU NODE KE DALAM LINKED LIST Untuk menyisipkan node dalam linked list digunakan procedure GETNODE. Jika NEW adalah suatu variabel pointer, maka GETNODE(NEW) akan menyebabkan node yang ditunjuk oleh variabel pointer NEW disisipkan ke dalam linked list.
5.5.1 Procedure Getnode(NEW) if
Avail = Null
then out-of-free-space
(a)
else
begin Getnode := Avail;
Avail
(b)
info
next
info
next
info
next
info
next
...
null
Avail := Next(Avail); Getnode
info
next
info
next
info
next
info ...
next null
Avail
(c)
Next(Getnode) : = Null; end; Getnode
info
next
Avail
info
next
5.5.2 Algoritma menyisipkan sebuah Node Getnode(NEW);
(b)
Info(NEW) := Name;
next
info ...
null
(a)
info
42
next null
NEW
info
next
Name null
next
info
next
info
next
...
P
(c)
Q := Next(P)
(d)
Next(P) := NEW
NEW
info
Q
next
Name null
next
info
next
info
next
...
P
(e)
Q
Next(NEW) := Q
NEW
info
next
Name
next
info
next
info
P
Q
43
next
5.6 LOGIKA LINKED LIST PADA ARRAY (a)
Jika tidak menggunakan logika linked list (pada umumnya dalam meng-input data digunakan cara sequential) Awal
Insert E
Delete
Insert F
C 1
A
1
A
1
2
C
2
C
2
3
3
E
3
4
4
A
1
A
2 E
4
3
E
4
F
Insert G
1
(overflo
E
w) A
1
2
2
3
3
4
(b)
Delete
F
A
4
F
Jika menggunakan logika Linked List Keadaan awal Info
Insert E Nex
Info
t
Delete C Nex
Info
t
t
1
A
2
1
A
2
1
2
C
0
2
C
3
2
3
4
3
E
0
3
4
0
4
0
4
44
Nex
A
3 4
E
0 0
Insert F Info
Delete E Nex
Info
Insert G Nex
t
Info
t
Nex t
1
A
3
1
A
2
1
A
2
2
F
0
2
F
0
2
F
3
3
E
2
3
4
3
G
0
0
4
0
4
4
5.7 MENDEFINISIKAN LINKED LIST DALAM PASCAL Type nodeptr = ^ nodetype; nametype = packed array [1..10] of char; nodetype = record info : nametype; next : nodeptr; end; Var
p : nodeptr; node : nodetype;
* Catatan : P ^. Info
: Info dari node yang ditunjuk oleh pointer P
P^. Next
: Next dari node yang ditunjuk oleh pointer P
P := nil
: pointer P berisi nilai Null
New(P)
: fungsi Getnode dalam Pascal
dispose(P)
: procedure Freenode dalam Pascal
5.8 MENGHAPUS SEBUAH NODE DALAM PASCAL procedure removaf(p:nodeptr, var out:nametype); var
q : nodeptr;
begin if (p^.Next = nil) then
UNDERFLOW-CONDITION
else
begin
45
q := p^.Next; p^.Next := q^.Next; out := q^.Info; dispose(q); end; end;
5.9 MENYISIPKAN SEBUAH NODE DALAM PASCAL procedure inseraf(p:nodeptr, in:nametype); var
q : nodeptr;
begin New(q); q^.Info := in; q^.Next := p^.Next; p^.Next := q; end;
5.10 PENYISIPAN PADA AKHIR DARI SUATU LINKED LIST (LINKED LIST ANTREAN) DALAM PASCAL Procedure Inserend(first : nodeptr, in :nametype); Var
newnode, q : nodeptr;
Begin New(newnode); newnode^.Info := in; newnode^.Next := nil; q := first; do while (q^.next <> nil) q := q^.Next; q^.Next := newnode; End;
46
Jika sebuah Linked List digunakan untuk menggambarkan suatu antrean, dalam hal ini pointer dapat langsung menunjuk ke rear/akhir dari antrean untuk menghindari pengulangan melalui semua node untuk menemukan node terakhir.
procedure inserend(in : nametype, var rear : nodeptr); var
newnode : nodeptr;
begin New(newnode); newnode^.Info := in; newnode^.Next := nil; rear^.Next := newnode; rear := newnode; end;
5.11 CIRCULAR LINKED LIST first
info
next
info
next
info
next
info
next
info
next
...
Head Nodes
Head
info
next
info
next
info
next ...
Circular Linked List dengan Head Node
Head
info
next
Circular Linked List dengan Head Node kosong
47
5.12 ALGORITMA PENYISIPAN NODE YANG BERISI VARIABEL NAME PADA HEAD DALAM LINKED LIST (a) Ambil node baru pada free storage kemudian node tersebut ditunjuk oleh pointer NEW (b) Isikan Info dengan Name pada node baru tsb. (c) Next dari node baru tsb. menunjuk ke node yang ditunjuk oleh pointer Head (d) Pindahkan pointer Head menunjuk ke node yang baru.
5.13 MENGHAPUS NODE KHUSUS Procedure removp(head : nodeptr, var p:nodeptr, out : nametype); Var
prior, this : nodeptr; flag : 0..2;
Begin prior := head; this := head^.next; flag := 1; While flag = 1 do begin if (this = head) then flag := 2; if (this = p) then flag := 0 else begin prior := this; this := this^.next; end; end; if (flag > 0) then Node yang ditunjuk oleh pointer p tidak ada dalam List else begin prior^.next := p^.next;
48
out := p^.info; dispose(p) end; End;
5.14 DOUBLY LINKED LIST Head
prior info next ...
Tiap node memiliki pointer yang menunjuk ke node sesudahnya dan pointer yang menunjuk ke node sebelumnya. Node Sesudahnya : Next(Node) Node sebelumnya : Prior(Node) Next(Prior(P)) = P dan P = Prior(next(P))
5.14.1 Double Linked List Kosong
prior
head next
prior head next
Prior(Head) = Head Next(Head) = Head
Dalam Pascal : Type nodeptr = ^ nodetype nodetype = record prior : nodeptr; info : nametype; next : nodeptr end;
49
5.14.2 Procedure menghapus sebuah node pada Double Linked List
(a)
Set pointer P prior info next
P
(b)
Ubah pointer pada node Next predecessor P ke node Successor P prior info next
P
(c)
Ubah pointer pada node dari prior Successor P ke node Predeccssor P prior info next
P
(d)
bebaskan node yang ditunjuk pointer P
Dalam Pascal : Procedure Removp(var p:nodeptr, out : nametype); Var
pred, succ : nodeptr;
Begin pred := p^.prior; succ := p^.next; pred^.next := succ; succ^.prior := pred; out := p^.info; dispose(p) End;
50
5.14.3 Penyisipan sebuah Node pada Doubly Linked List
(a)
Ambil sebuah node baru dan isikan datanya
(b)
Set pointer dari Next node baru menunjuk ke Successor P dan pointer Proirnya ke P P
NEW
IN AVAIL
(c)
Ubah pointer Next P menunjuk ke node baru
(d)
Ubah pointer Prior dari Successor P menunjuk ke node baru P
NEW
IN AVAIL
5.15
Contoh Aplikasi Linked List
5.15.1 Polynomial n n-1 2 anx + an-1 x + ... + a2 x + a1 x + a0
Type nodeptr = ^nodetype; nodetype = record exp : integer; coef : integer; next : nodeptr; end;
51
143 x4 + 201 x2 + 14 x + 2
a4 = 143 POLY 1
a3 = 0
a2 = 201
a1 = 14
a0 = 2
EXP COEF 4 143
2
52
20
1
14
0
2
BAB VI GRAPH
6.1 DEFINISI GRAPH merupakan suatu koleksi dari himpunan VG dan EG. Notasi : G = { VG, EG } G = Graph VG = Himpunan titik EG = HImpunan garis Titik : Node / Vertex Garis : Arc / Edge Contoh : Graph G terdiri dari : G = { VG, EG } VG = { a,b,c,d } EG = { 1,2,3,4,5,6,7,8 }
b 1
8
2 3 7
a
c
5
6
d
4
-
edge 1 menghubungkan vertex a & b Edge 1 = (a,b)
-
edge 2 menghubungkan vertex b & c Edge 2 = (b,c)
-
edge 3 menghubungkan vertex b & c Edge 3 = (b,c), dst ...
Jumlah vertex dalam suatu graph disebut ORDER dari graph tersebut. Contoh : Graph G dengan order = 4
(jumlah vertex = 4 ; a,b,c,d)
Suatu graph hanya ditentukan oleh vertex-vertex dan edge-edgenya. Posisi dari vertex-vertex dan edge-edge dalam penggambaran tidaklah penting.
53
GRAPH EQUIVALEN : penggambaran graph yang sama. 8 1
a
2
c
b
3
5
6 7
4
d
GRAPH EQUIVALEN
Suatu graph G disebut SIMPLE GRAPH, jika : 1. tidak mempunyai edge yang SELF LOOP (tidak ada (V,V) dalam G) 2. tidak mempunyai MULTIPLE EDGE (hanya ada (Vi, Vj) dalam G) (V1, V2, V3, ...... VG)
b 1
2
c
5
a d
4
SIMPLE GRAPH
MULTIPLE EDGE adalah 1 vertex dihubungkan oleh beberapa edge. Contoh :
Pada gambar graph equivalen diatas, vertex b dihubungkan oleh edge-
edge 1,2,3,5,6,7. Sedangkan vertex c dihubungkan oleh edge-edge 2,3,4
SELF LOOP adalah vertex yang dihubungkan oleh edge-edge menuju edge itu sendiri. Contoh :
Pada gambar graph equivalen diatas, Vertex a dihubungkan oleh edge 8
menuju a kembali.
Suatu Graph G disebut CONNECTED (terhubung) jika Graph G dapat dipartisi (dibagi) menjadi 2 graph dengan menghapus paling sedikit 1 edge.
54
Contoh yang tidak connected : Suatu graph G terdiri dari :
G = { VG, EG } VG = { e,f,g,h } EG = { 1,2,3 } f
e
2 1
h 3
g
UNCONNECTED GRAPH
PATH dalam Graph adalah barisan dari 1 buah edge-edge yang menghubungkan 2 vertex. Notasi :
P(Vi, Vj) = (Vi, X1) (X1, X2) (X2, Xn-1) (Xn-1, Xn) (Xn, Vj)
Dari gambar simple graph :
P(b,d) =
(b,c) (c,d)
P(b,d) =
(b,c) (c,b) (b,c) (c,d)
P(b,d) =
(b,d)
P(b,d) =
(b,c) (c,b) (b,d)
LENGTH dari suatu path adalah jumlah edge-edge pada path tersebut. Contoh :
Perhatikan gambar simple graph :
P(b,d) = (b,d)
length = 1
= (b,c) (c,d)
length = 2
= (b,c) (c,b) (b,d)
length = 3
CYCLE adalah path yang memenuhi syarat sebagai berikut : 1. tidak ada edge yang tampil lebih dari satu kali dalam barisan edge dari path tersebut contoh : Gambar simple graph ;
P(b,d) = (b,c) (c,b) (b,d) tidak boleh
2. path harus berbentuk P(V,V) 3. tidak ada vertex yang dikunjungi lebih dari satu kali
55
contoh : P(a,a) = (a,b) (b,c) (c,d) (d,b) (b,a) b dikunjungi lebih dari 1x P(b,b) = (b,c) (c,b) (b,a) (a,c) (c,b) c & b dikunjungi 3x Contoh CYCLE :
P(b,b) = (b,d) (d,c) (c,b)
ACYCLIC adalah graph yang tidak mempunyai cycle. Contoh :
Graph G terdiri dari : G = { VG, EG } VG = { e,f,g,h } EG = { 1,2,3 } b
b
a
c
c
a
d
d
(a)
(b)
ACYCLIC GRAPH
Catatan: Graph yang Simple belum tentu graph yang Acyclic. Graph yang Acyclic adalah graph yang Simple.
Graph yang berarah disebut DI-GRAPH / DIRECTED GRAPH, adalah merupakan graph dimana edge-edgenya mempunyai suatu arah. b c
a
Pada Gambar ;
(a,b)
1 arah
(b,a)
0 arah
d
56
Graph yang tidak mempunyai arah boleh bolak-balik.
Pada Gambar ;
a
b
d
c
(a,b)
1 arah
(b,a)
1 arah
6.2 OUT DEGREE, IN DEGREE, DEGREE dari suatu vertex a Vertex a mempunyai : 1. OUT DEGREE (derajat luar) = N Jika vertex a mempunyai N edge mengarah keluar. Misal : Vertex a mempunyai 2 edge mengarah ke luar (Gambar Digraph diatas) 2. IN DEGREE (derajat masuk) = N Jika vertex a mempunyai N edge mengarah masuk (Gambar Digraph diatas) 3. DEGREE (derajat) = N Jika Out Degree a ditambah In Degree a = N misal : vertex b : In Degree
=2
Out Degree = 3 ----------------------Degree = 5
Contoh : Pada Gambar Digraph diatas; degree(a) = 3 degree(b) = 5 degree(c) = 3 degree(d) = 5 -----------------------16
57
Graph G dengan himpunan vertex Vo dan edge Eo diasumsikan graph berorder N untuk N 1.
Salah satu pendekatan untuk graph ini menggunakan matriks ADJACENCY dengan suatu array A ukuran N x N. A(i, j) 1 jika edge (Vi, Vj) Eij 0 jika edge (Vi, Vj) Eij Contoh :
Graph UNDIRECT / Matriks Simetris
5 2 3 1 6
4 i
1
2
3
4
5
6
1
0
1
0
0
0
0
2
1
1
1
0
0
0
3
0
1
0
1
1
1
4
0
0
1
0
0
0
5
0
0
1
0
0
0
6
0
0
1
0
0
0
j
Contoh :
Graph DIRECT
6 2 3 1 4
58
5
i
1
2
3
4
5
6
1
0
1
0
0
0
0
2
0
1
1
0
0
0
3
0
0
0
0
1
1
4
0
0
1
0
0
0
5
0
0
0
0
0
0
6
0
0
0
0
0
0
j
6.3 Penggambaran NODE DIRECTORY Penggambaran node dalam directory dibagi dalam 2 bagian : 1. Directory 2. Himpunan Link List (LL)
Setiap record dari Link List mempunyai 2 field ; 1. Node Identifier 2. Suatu link yang menghubungkan elemen lain dari list (next)
NODE
NEXT
Directory menggambarkan banyak node. Link list menunjukkan edge-edgenya.
4 1
2
3
5 6
59
Directory
Link List
1.
2
2.
1
null
2
3
nul l
3.
2
4
4.
3
null
5.
3
null
6.
3
null
5
6
4 1
2
3
5 6
Directory
Link List
1.
2
null
2.
2
3
null
3.
4
5
null
60
null
4.
null
5.
null
6.
3
null
Kalau punya harga (untuk manajemen proyek) penggambaran node-nya di bagi 3 ; NODE WEIGH
NEX
T
T
2
5 20
10
30
1
3 15
4 25
61
BAB VII TREE
7.1 GENERAL TREE TREE adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.
ROOT Tree A ; suatu vertex dengan derajat masuk = 0. LEAF Tree A ; suatu vertex dengan derajat keluar = 0.
Tree A atas vertex-vertex : V1, V2, V3, ....... , Vn harus mempunyai : 1. Satu root A
Root (A) = V1
2. Sisanya (V2 , V3, ........,Vn) dipartisi menjadi Tm subtree ; di mana : 0 m n-1
Contoh :
TREE A B
A
C
level 0
I
D
level 1
E
F
level 2
G
H
level 3
Keterangan : Root (A) = B Leaf (A) = A,C,D,G,H B mempunyai 4 subtree : A,C,I,D I mempunyai 2 subtree : E,F E mempunyai 1 subtree : G F mempunyai 1 subtree : H 62
LEVEL dari suatu vertex A dalam Tree A adalah LENGTH Path(P) (Root(A),A) Dari gambar Tree A ; Tentukan level A : Length P(Root(A),A) Length P(B,A) = (B,A) = 1 Tentukan level G : Length P(Root(A),G) Length P(B,G) = (B,I) (I,E) (E,G) = 3
HIGH dari suatu tree A adalah level tertinggi ditambah 1. WEIGHT dari suatu tree A adalah jumlah leaf dalam tree A. Contoh :
Dari Tree A ; High Tree A = 3 + 1 = 4 Weight Tree A = 5 (A,C,D,G,H)
7.2 FOREST Forest merupakan koleksi dari tree-tree. Contoh :
7.3 BINARY TREE Binary Tree merupakan himpunan vertex-vertex yang terdiri dari 2 subtree (dengan disjoint) yaitu subtree kiri dan subtree kanan. Setiap vertex dalam binary tree mempunyai derajat keluar max = 2.
63
Contoh :
(1)
(2) A
B
(3) A
A
C
B
B
D
Derajat keluar = 2
A adalah subtree kanan
(4)
A adalah subtree kiri
(5) A
B
A
B
C
E
D
F
Bukan Binary Tree tapi
Bukan Binary Tree tapi General Tree
General Tree karena bukan
karena mempunyai derajat keluar > 2.
merupakan Subtree Kiri/Kanan
7.4 SIMILAR & EKIVALEN dalam 2 BINARY TREE Dua Binary Tree dikatakan Similar, jika struktur dari kedua Binary Tree sama.
64
Contoh :
T1
T2 A
X
B
C
Y
D
Z
K
E
L
Dua Binary Tree dikatakan Ekivalen, jika : - Similar - Informasi setiap vertex sama. Contoh :
T3
T1 A
A
B
C
D
B
E
C
D
E
7.5 COMPLETE Misalnya height dari binary tree T adalah k. Binary Tree T disebut COMPLETE jika jumlah verteks dari binary tree T adalah: k-1
2i
(mencapai maximum)
i=0 Contoh height dari binary tree T = 4. Gambar binary tree-nya :
65
4-1
2 i = (20 + 21 + 22 + 23) = 15 vertex
i=0
7.6 ALMOST COMPLETE Misalnya height dari binary tree T adalah k. Binary Tree T disebut ALMOST COMPLETE jika : -
pada level 0 hingga level k - 2, jumlah verteksnya adalah: k-1
2i
i=0 -
pada level k - 1 verteks-verteksnya terisi dari kiri ke kanan sebagai u, dimana 1 <= u <= 2 k-1
Contoh height dari binary tree T = 4. dan mis u = 5. Gambar binary tree-nya : 4-2
2 i = (20 + 21 + 22 ) = 7
i=0
66
7.7 HEIGHT MIN dan HEIGHT MAX Diperoleh dengan rumus sbb: H min = log 2 (N+1)
H max = N
Keterangan :
= Fungsi celling dengan pembulatan ke atas
N
= jumlah vertex
Contoh : Diberi 7 buah vertex untuk membentuk suatu binary tree. Hitung H min dan H max dari kemungkinan binary tree yang terbentuk. Gambar binary treenya. Jawab : H min = log 2 (7+1)
H max = N = 7
7.8 REPRESENTASI BINARY TREE Contoh :
A
A
B
B
C
C
D D
E
E
Algoritma untuk merubah General Tree menjadi Binary tree: 1. Insert edge-edge yang menghubungkan sibling (saudara) kemudian delete semua edge yang menghubungkan parent dengan child-nya kecuali edge yang paling kiri. 67
2. Rotasi 45o sedemikian sehingga dibedakan subtree kiri dan kanan. Contoh :
(1)
(2) A
B
A
C
D
F
E
G
J
H
B
I
K
E
G
J
A
B C D
E
G
D
F
(3)
F
C
I
H
J K
68
H
I
K
Algoritma untuk merubah Forest menjadi Binary tree: 1. Insert edge-edge yang menghubungkan sibling (saudara) kemudian delete semua edge yang menghubungkan parent dengan child-nya kecuali edge yang paling kiri. 2. Tree-tree yang lain dihitung sebagai satu level Contoh : (1)
(2)
A
B
(3)
G
C
(4)
H
J
(5)
K
I
D
E
F
A
B
G C
H D
I
J
E
K
F
7.9 BINARY TREE TRANSVERSAL Adalah proses menelusuri suatu Binary Tree sehingga sedemikian rupa setiap vertex dikunjungi hanya 1 kali. 3 aktivitas dalam Binary tree Transversal : (1)
Visit the Root
(2)
Transverse the left subtree
(3)
Transverse the right subtree
69
Algoritma dalam Binary Tree Transversal : 1. PRE-ORDER TRANSVERSAL a. visit the root b. tranverse the left subtree c. tranverse the right subtree 2. IN-ORDER TRANSVERSAL a. tranverse the left subtree b. visit the root c. tranverse the right subtree 3. POST-ORDER TRANSVERSAL a. tranverse the left subtree b. tranverse the right subtree c. visit the root
Contoh : (1) +
+
*
A
PRE-ORDER : V L R D
++*ABCD
C
B
70
(2) +
+
D
*
C
A
B
+
IN-ORDER : L V R +
D
A*B+C+D *
A
C
B
(3) +
POST-ORDER : L R V +
D
AB*C+D+ *
A
C
B
71
7.10 BINARY SEARCH TREE Suatu Binary Search Tree adalah suatu
dari himpunan
Binary Tree yang
N record (N1, N2, N3 . . . Nn)
setiap vertex-nya (sebut Ri) ditempati oleh Ni untuk
i = 1,2,3 ... N. Vertex-vertex dari Binary Tree tsb. diatur sedemikian rupa sehingga untuk setiap Ri harus memenuhi syarat sbb : 1. Jika Rj = left (Ri) maka Nj < Ni 2. Jika Rj = right (Ri) maka Nj > Ni Contoh : Diketahui key dari 7 record (K, M, L, N, P, O, Q) Binary Search Tree dari 7 key diatas dapat dibentuk :
K
N
M
K
L
M
Operasi-operasi pada Binary Search Tree : 1.
Direct Search
2.
Sequential Search
3.
Insert Search
4.
Delete Search
7.10.1 DIRECT SEARCH Untuk mencari vertex k dalam binary search tree dengan root=Ri , algoritmanya adalah sbb : 1. Jika tree kosong maka search tidak sukses (k tidak ada dalam binary search tree) 2.
Jika k = Ni maka search sukses (k ada dalam binary search tree)
3. Jika k < Ni maka subtree kiri dari Ri ditelusuri dan Ri = left (Ri) kemudian kembali ke langkah 1.
72
4. jika k > Ni maka subtree kanan dari Ri ditelusuri dan Ri=right (Ri) kembali ke langkah 1. Contoh : Carilah Key M dalam Binary Tree berikut secara Direct Search. Berapa langkah/perbandingan yang dibutuhkan untuk mencari Key M. Bandingkan dengan rootnya, jika : - lebih besar maka cari ke kanan - lebih kecil maka cari ke kiri.
N
K
O
N, K, M
-- 3 kali perbandingan
M:N
-- M < N
M:K
-- M > K
M:M L
Q
M
P
R
7.10.2 SEQUENTIAL SEARCH Untuk mencari vertex K dalam binary search tree dengan Root=Ri. Algoritmanya menggunakan langkah-langkah : IN-ORDER Transversal (Left Visit Right) Contoh : Cari key M dalam Binary Tree berikut secara sequential.
N
K
O
L
M
Q
P
R
73
7.10.3 INSERT SEARCH Prinsipnya sama dengan DIRECT.
4 langkah :
K
K>A F>A
F
M
D>A A=A
D
H
L
A
7.10.4 DELETE SEARCH dilihat dari Link -list-nya.
7.11
BALANCED TREE Suatu Binary Tree dimana untuk setiap Root Ri berlaku struktur subtree kiri =
struktur subtree kanan. Contoh :
7.12
HEIGHT BALANCED TREE Suatu Tree dimana untuk setiap Root Ri berlaku height dari subtree kanan dan
height dari subtree kiri beda paling banyak satu. Contoh : Height balanced Tree
sama
1
Bukan
sama
2
74
Height Balanced tree belum tentu Balance Tree tapi Balance Tree sudah pasti height balance tree. Binary tree yang Complete = Balance Tree
Balance Tree belum tentu Binary Tree Complete :
Height Balance Tree belum tentu Binary Tree Complete :
Height Balance Tree belum tentu Almost Complete :
Balance + Almost
Balance Tree = Almost Complete :
almost + balance
almost + balance
75
BAB VIII SEARCHING & SORTING
8.1 PENDAHULUAN Sorting dan searching merupakan salah satu operasi dasar dalam ilmu komputer. Sorting merupakan suatu proses (operasi) yang mengurutkan data dalam suatu urutan yang diberikan (increasing atau decreasing). Searching merupakan suatu proses (operasi) untuk mencari lokasi dari data yang diberikan dalam suatu urutan data. Secara tidak langsung sorting dan searching menunjuk pada operasi file yang merupakan kumpulan suatu dari record. Masing-masing record dalam file F dapat berisi banyak field, tetapi terdapat 1 buah field yang memiliki nilai unique atau merupakan key yang unique dalam record tersebut. Misal field K merupakan key unique yang disebut primary key, maka proses sorting file F akan berdasarkan key unique tersebut dan proses searching untuk mencari record tertentu berdasarkan nilai key unique yang diberikan.
8.2 SORTING Terdapat 2 katagori dasar dalam tehnik sorting : internal sort dan external sort. Metoda Internal sort digunakan apabila koleksi data yang akan diurutkan tidak dalam jumlah besar sehingga proses dapat dilakukan dalam main memory. Metoda External sort digunakan apabila koleksi data yang akan diurutkan dalam jumlah besar dimana koleksi data tersebut ada dalam auxiliary memory device seperti magnetic tape atau disk. (Yang akan di bahas adalah Internal Sort). Misal A merupakan suatu daftar dari n elemen A1, A2, ..., An dalam memori. Sorting A merupakan operasi yang mengatur elemen dalam A sehingga ada dalam urutan yang terurut, misal dalam increasing order sehingga : A1 A2 A3 ..... An
Contoh : Misal suatu array DATA berisi 8 elemen sebagai berikut : DATA : 77, 33, 44, 11, 88, 22, 66, 55
76
Setelah diurutkan : DATA : 11, 22, 33, 44, 55, 66, 77, 88
8.3 INSERTION SORT Misal array A dengan n elemen A[1], A[2], ..... , A[N] dalam memori. Algoritma Insertion Sort memeriksa A dari A[1] sampai dengan A[N], menyisipkan setiap elemen A[K] ke dalam posisi yang seharusnya dalam subarray terurut A[1], A[2], ..... , A[K-1]. Algoritma sorting ini umumnya digunakan apabila jumlah elemennya sedikit (n kecil). Masalah yang akan muncul dengan metoda ini adalah bagaimana cara menyisipkan A[K] ke dalam letak yang seharusnya pada subarray terurut A[1], A[2], ....., A[K-1]. Hal ini dapat dilakukan dengan membandingkan A[K] dengan A[K-1], kemudian A[K] dengan A[K-2], A[K] dengan A[K-3] dan seterusnya, sampai menemukan elemen A[J] dimana A[J] A[K]. Algoritma ini menggunakan sentinel elemen (A[0]) yang digunakan sebagai perbandingan. Yang dimaksud dengan sentinel elemen adalah elemen yang memiliki nilai yang sangat kecil.
Penggambaran proses Insertion Sort : Proses
A[0]
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[7]
A[8]
K = 1:
-
77
33
44
11
88
22
66
55
K = 2:
-
77
33
44
11
88
22
66
55
K = 3:
-
33
77
44
11
88
22
66
55
K = 4:
-
33
44
77
11
88
22
66
55
K = 5:
-
11
33
44
77
88
22
66
55
77
K = 6:
-
11
33
44
77
88
22
66
55
K = 7:
-
11
22
33
44
77
88
66
55
K = 8:
-
11
22
33
44
66
77
88
55
Urutan :
-
11
22
33
44
55
66
77
88
Contoh : Array A dengan 8 elemen sebagai berikut : 77, 33, 44, 11, 88, 22, 66, 55 Tabel diatas menggambarkan algoritma insertion sort. Elemen yang dilingkari menandakan A[K] dalam masing-masing proses dari algoritma, dan tanda panah menandakan letak yang seharusnya untuk menyisipkan A[K].
Algoritma Insertion Sort : 1. A[0] = 0
{sentinel elemen}
2. Repeat langkah 3 sampai 5 untuk K = 2,3,.....,N 3.
Temp := A[K] ; PTR = K - 1
4.
Repeat While Temp < A[PTR] a. A[PTR+1] = A[PTR] b. PTR = PTR - 1 [End Of Loop]
5.
A[PTR+1] = Temp [End Loop Langkah 2]
6. Return
Complexity Insertion Sort = O(n2)
78
8.4 SELECTION SORT Array A dengan n elemen A[1], A[2], ....., A[N] dalam memori. Algoritma untuk mengurutkan A sebagai berikut : Pertama, cari elemen terkecil dalam array A dan letakkan pada posisi pertama dalam array tersebut. Kemudian cari elemen kedua terkecil dalam array A dan letakkan dalam posisi kedua dari array tersebut, dan begitu seterusnya.
Proses 1 : Cari lokasi LOC yang merupakan elemen terkecil dalam array yang terdiri dari N elemen , A[1], A[2], ...., A[N] dan kemudian tukar posisi A[LOC] dengan A[1].
Proses 2 : Cari lokasi LOC yang merupakan elemen terkecil dalam array yang terdiri dari N-1 elemen , A[2], A[3], ...., A[N] dan tukar posisi A[LOC] dengan A[2]. A[1] , A[2] terurut, jika dan hanya jika A[1] A[2].
Proses 3 : Cari lokasi LOC yang merupakan elemen terkecil dalam array yang terdiri dari N-2 elemen, A[3], A[4],......, A[N] dan tukar posisi A[LOC] dengan A[3]. A[1], A[2], A[3] terurut, jika dan hanya jika A[2] A[3]. Dst................. Sehingga A akan terurut setelah N-1 proses.
Contoh ; Array A dengan 8 elemen sbb : 77, 33, 44, 11, 88, 22, 66, 55 Proses algoritma digambarkan dalam Tabel 1.2. Misalkan LOC berisi nilai lokasi elemen terkecil A[K], A[K+1],...,A[N] selama proses K. Elemen yang dilingkari merupakan elemen yang akan ditukar posisinya.
Proses
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[7]
A[8]
K = 1 ; LOC = 4
77
33
44
11
88
22
66
55
79
K = 2 ; LOC = 6
11
33
44
11
88
22
66
55
K = 3 ; LOC = 6
11
22
44
77
88
33
66
55
K = 4 ; LOC = 6
11
22
33
77
88
44
66
55
K = 5 ; LOC = 8
11
22
33
44
88
77
66
55
K = 6 ; LOC = 7
11
22
33
44
55
77
66
88
K = 7 ; LOC = 7
11
22
33
44
55
66
77
88
Urutan :
11
22
33
44
55
66
77
88
Algoritma : Procedure SELECTION (A, N) 1. Repeat langkah 2 dan 3 untuk K = 1,2,.....,N-1 2.
Call MIN(A, K, N, LOC)
3.
Temp = A[K] ;
A[K] = A[LOC] ; A[LOC] = Temp
[End Loop langkah 1] 4. Exit
Procedure MIN (A,K,N,LOC) 1. Min = A[K] ; LOC = K 2. Repeat For J = K+1, K+2, ......, N If Min > A[J] Then Min = A[J] ; LOC = A[J] ; LOC = J [End Loop] 3. Return
Complexity (kompleksitas) algoritma Selection Sort : O(n2)
80
8.5 MERGING Misal A merupakan himpunan data terurut dengan r buah elemen dan B himpunan data terurut dengan s buah elemen. Proses yang menggabungkan elemen-elemen dalam A dan B menjadi himpunan elemen data terurut tunggal, misal C dengan n = r + s buah elemen disebut dengan proses Merging. Secara singkat, proses Merging dapat dijelaskan sebagai berikut ; ambil elemen pertama dari A, A[1] dan B, B[1]. Bandingkan kedua elemen tersebut. Jika A[1] > B[1], B[1] dimasukkan dalam C, jika tidak A[1] dimasukkan dalam C. Untuk himpunan data yang elemennya dimasukkan dalam C, elemen yang akan dibandingkan adalah elemen berikutnya. Dan seterusnya. Contoh : A = 11 12 23 33 45 B=9
67
12 21 42
Disini A[1] = 11 dan B[1] = 9 dibandingkan dan A[1] > B[1], B[1] dimasukkan dalam C. Pembandingan berikutnya A[1] = 11 dibandingkan dengan B[2] = 12, A[1] dimasukkan dalam C, dan begitu seterusnya.
Algoritma MERGING : 1. NA = 1 ; NB = 1 dan PTR = 1 2. Repeat While NA R and NB S If A[NA] < B[NB] then a. C[PTR] = A[NA] b. PTR = PTR + 1 ; NA = NA + 1 Else a. C[PTR] = B[NB] b. PTR = PTR + 1 ; NB = NB + 1 [End If Structure] [End Loop] 3. If NA > R then Repeat For k = 0,1,2,3,.....,S-NB C[PTR+K] = B[NB+K]
81
[End loop] Else Repeat for K = 0,1,2,3,.....,R-NA C[PTR+K] = A[NA+K] [End loop] [End If Structure] 4. Exit
Kompleksitas algoritma Merging = O(n). Dengan kata lain algoritma Merging dapat dijalankan dalam waktu yang linear.
8.6 MERGE SORT Misal : Array A dangan n elemen A[1], A[2], ....., A[N] dalam memori. Algoritma Merge Sort yang akan mengurutkan A akan digambarkan sebagai berikut : Contoh : Array A berisi 6 elemen sbb : 15
12
45
56
13
10
Masing-masing proses dalam algoritma merge sort akan dimulai dari elemen awal dalam A dan menggabungkan (merge) pasangan subarray yang terurut sbb : 15
12
45
56
12 15
45
56
12 15 45 56
13
10
1013 10 13
10 12 13 15 45
56
Kompleksitas dari proses merge-sort = O(n).
8.7 TOURNAMENT SORT Tournament Sort disebut juga dengan Tree Selection Sort. Misal terdapat elemen data sebagai berikut : 6, 25, 7, 2, 14, 10, 9, 22, 3, 14, 8, 12, 1, 30, 13. Asumsikan bahwa
82
batasan proses dalam memori hanya 4 buah elemen setiap saatnya. Algoritma Tournament Sort membagi 4 elemen tersebut menjadi 2 pasangan elemen sbb : 6 25
7 2 Asumsikan bahwa data tersebut akan diurutkan secara ascending, sehingga elemen terkecil pada masing-masing pasangan di atas adalah 2 dan 6. 6
6
25
7
2
2 2 adalah elemen terkecil dan merupakan elemen pertama pada output dari urutan yang diurutkan. 6
6
25 2 7
2
2
2 Proses yang berikutnya akan ditentukan elemen kedua dalam list terurut. 2 tidak diikutsertakan kembali. 6
6
25 6 7
7
* Proses selanjutnya : 6
6
25
83
2, 6
7
6
2, 6
7
2, 6, 7
9
2, 6, 7, 9
7
14 Proses ketiga : 10
10
25
7
7
14 Proses keempat : 10
10
25
9
9
14 Proses kelima : 10
10
25 10 22
2, 6, 7, 9, 10
14
14 Pada proses keenam elemen 3 dimasukkan dalam tree : 3 25
22
14
14
Apabila 3 diikutkan dalam proses, maka urutan list terurut pada output akan berantakan. Untuk mengatasinya, terdapat aturan sbb : If Keynew < Keylastout
84
then keynew diletakkan dalam tree tetapi untuk sementara waktu didiskualifikasikan.
Catatan : Keylastout adalah key terakhir yang ada dalam list terurut.
Elemen yang didiskualifikasikan akan ditandai dengan asterisk (*). Sehingga hasil dari proses enam adalah : *3
25
25 14 22
2, 6, 7, 9, 10, 14
14
14 Pada proses ketujuh, elemen berikutnya adalah 14. Karena elemen terakhir dalam list terurut tidak lebih kecil dari elemen yang akan dimasukkan, yakni 14, maka elemen 14 masuk dalam list terurut. *3
25
25 14 22
2, 6, 7, 9, 10, 14, 14
14
14 Proses kedelapan, elemen berikutnya 8 dan elemen ini untuk sementara akan didiskualifikasi karena 8 < dari elemen terakhir dalam list terurut yakni 14. *3
25
25
22
22
2, 6, 7, 9, 10, 14, 14, 22
25
2, 6, 7, 9, 10, 14, 14, 22, 25
22
*8 Proses kesembilan : *3
25
25
85
*12
*
*8 Proses kesepuluh, elemen berikutnya 1 : *3 *1
*12 *8 Sekarang semua elemen yang ada adalah elemen yang didiskualifikasikan. Dan saat ini baru 9 elemen yang diurutkan. Sekarang elemen yang untuk sementara didiskualifikasikan, dilepaskan dari diskualifikasi dan proses dimulai kembali. Kali ini akan terbentuk list terurut kedua dari elemen-elemen yang didiskualifikasi sebelumnya. Sehingga proses 10 : 3
1
1 1 12
8
2, 6, 7, 9, 10, 14, 14, 22, 25 1
8 Proses 11, elemen 30 : 3
3
30 3 12
8
2, 6, 7, 9, 10, 14, 14, 22, 25 1, 3
8 Proses 12 : 13
13
30 8 12
8
2, 6, 7, 9, 10, 14, 14, 22, 25 1, 3, 8
8
86
Sekarang input list kosong. Sehingga proses 13 : 13
13
30 12 12
2, 6, 7, 9, 10, 14, 14, 22, 25
12
1, 3, 8, 12
* Proses 14 dan 15 tidak terdapat elemen yang dimasukkan dalam tree. Hasil akhir dari proses tournament sort ini menghasilkan 2 himpunan elemen data yang terurut : 2, 6, 7, 9, 10, 14, 14, 22, 25 1, 3, 8, 12, 13, 30
Kedua himpunan data yang terurut tersebut dapat digabungkan menjadi satu list data terurut dengan menggunakan algoritma Merging.
8.8 SHELL SORT Disebut juga dengan metoda pertambahan menurun (diminishing increment). Metoda ini dikembangkan oleh Donald L. Shell tahun 1959. Metoda ini memanfaatkan penukaran sepasang elemen untuk mencapai keadaan urut. Dalam hal ini jarak dua elemen yang dibandingkan dan ditukarkan tertentu. Pada langkah pertama, ambil elemen pertama dan kita bandingkan dengan elemen pada jarak tertentu dari elemen pertama tersebut. Kemudian elemen kedua dibandingkan dengan elemen lain dengan jarak yang sama. Demikian seterusnya sampai seluruh elemen dibandingkan. Pada contoh berikut, proses pertama kali jarak diambil separoh banyaknya elemen yang akan diurutkan. Proses kedua jaraknya diambil separuh jarak yang pertama, dst....
Misal terdapat elemen sebagai berikut : 23
45
12
24
56
87
34
27
23
16
Proses pengurutan menggunakan metoda Shell ada pada tabel dibawah ini. Dalam hal ini elemen yang ditulis miring adalah elemen yang dibandingkan dan kemudian ditukar, jika perlu.
Jarak
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[7]
A[8]
A[9]
Awal
23
45
12
24
56
34
27
23
16
Jarak = 4
23
45
12
24
56
34
27
23
16
23
45
12
24
56
34
27
23
16
23
34
12
24
56
45
27
23
16
23
34
12
24
56
45
27
23
16
23
34
12
23
56
45
27
24
16
23
34
12
23
16
45
27
24
56
23
34
12
23
16
45
27
24
56
12
34
23
23
16
45
27
24
56
12
23
23
34
16
45
27
24
56
12
23
16
34
23
45
27
24
56
12
23
16
34
23
45
27
24
56
12
23
16
34
23
45
27
24
56
12
23
16
34
23
24
27
45
56
12
23
16
34
23
24
27
45
56
12
23
16
34
23
24
27
45
56
12
23
16
34
23
24
27
45
56
12
16
23
34
23
24
27
45
56
12
16
23
34
23
24
27
45
56
12
16
23
23
34
24
27
45
56
12
16
23
23
24
34
27
45
56
12
16
23
23
24
27
34
45
56
Jarak = 2
Jarak = 1
88
Akhir
12
16
23
23
24
27
34
45
56
12
16
23
23
24
27
34
45
56
12
16
23
23
24
27
34
45
56
8.9 SEARCHING Pencarian data sering disebut juga dengan istilah table look-up atau storage and retrieval information, adalah suatu proses untuk mengumpulkan sejumlah informasi di dalam pengingat komputer dan kemudian mencari kembali informasi yang diperlukan.
8.10 SEQUENTIAL SEARCHING Metoda yang paling sederhana dari sejumlah metoda pencarian adalah metoda pencarian berurutan (sequential searching). Secara singkat metoda ini dapat dijelaskan sebagai berikut : Dari elemen-elemen yang diketahui, data yang dicari dibandingkan satu persatu sampai data tersebut ditemukan atau tidak ditemukan.
Algoritma Sequential Searching : 1. Baca himpunan data yang diketahui, misalnya sebagai himpunan A dengan N elemen. 2. Baca data yang dicari, misal Data 3. Ada = False 4. For I = 1 to N proses langkah 5
5.
If Data = A[I] then Ada = True ; Posisi = I ; I = N
6. If Ada = False Then N = N+1 ; A[I] = Data 7. Selesai
89
8.11 Skema Move To The Front Pada skema pencarian sekuensial move to the front, apabila proses pencarian berhasil, maka record tersebut dipindahkan pada posisi pertama dari daftar tersebut. Record pertama menjadi record kedua dan seterusnya. Metoda move to the front ini, prosesnya lebih baik apabila menggunakan linked list dibandingkan dengan array. (cari alasannya, mengapa !)
8.12 Skema Transposition Pada skema pencarian sekuensial transposition, apabila prose pencarian berhasil, maka record tersebut dipindahkan pada posisi berikutnya. Kedua skema di atas (move to the front dan transposition) didasarkan pada kemungkinan proses pencarian apabila elemen data yang di cari akan digunakan dan dicari kembali.
(Cari kelebihan dan kekurangan kedua skema di atas dengan penggambaran secara linked list dan array !)
90
DAFTAR PUSTAKA
1. D. Suryadi H. S., Pengantar Struktur Data, Penerbit Gunadarma 2. Loomis, Mary E. S., Data Management and File Structures, Prentice Hall International Inc., 1989. 3. Reynolds, W. Charles, Program Design and Data Structures in Pascal, Wadsworth Pub. Co., 1986. 4. Wirth, Niklaus, Algorithms and data Structures, Prentice Hall, 1986. 5. Lipschutz, Seymour, Schaum’s Outline Series, Data Structures, Mc Graw-Hill, 1986. 6. Stubbs, T. Daniel, & Neil W. Webre, Data Structures with Abstracts Data Types and Pascal, Brook/Cole Publishing Company, 1984.
91
