STRUKTUR DAN ORGANISASI DATA
Struktur
data menjadi dasar perancangan program
Algoritma
+ Struktur Data = Program
Struktur
data adalah cara menyimpan atau merepresentasikan data di dalam komputer agar
bisa dipakai secara efisien (Efisiensi waktu,Resources RAM storage,kemudahan
programming)
·
Data Dan Tipe Data
Data: representasi dari fakta dunia nyata
Tipe Data
Secara umum dikelompokkan:
Tipe data Sederhana
tunggal
1. Integer : nilai bilangan
bulat( operator logika +,-,*,/)
2. Real : ditulis menggunakan
titik desimal
3. Boolean : true & False
(And,Or,Not)
4. Karakter : terdiri atas
bilangan,abjad dan special symbol (Length,concat,substr)
Tipe data Sederhana majemuk
1. String : barisan hingga
simbol yg diambil dari himpunan karakter (“STMIK”,”Facebook”)
Tipe data berstruktur
1. Struktur sederhana :
o
Array à [“Z”,”F”,”R”], ([1,3,12],
o
Record à Mhs : {Nama=”Rudi”,
Usia=23}
2. Struktur majemuk :
o
Linier(stack,queue,Linear Linked list)
o
Non Linier (Tree,Graph)
·
Deklarasi Dan Mapping Ke
Storage
- Struktur data
secara logik dapat mempunyai beberapa storage mapping atau
representasi fisik.
- Salah
satu storage mapping yang dapat dilakukan adalah apa yang disebut
bentuk sign-and-magnitude.
- Sehari-hari
bilangan dinyatakan dalam basis 10 (sistem desimal), dalam memori komputer
dinyatakan dalam basis 2 (sistem binary).
- Ada aturan yang dapat kita gunakan untuk menyatakan
data dalam storage, yakni
- Extended Binary Coded Decimal Interchange Code
(EBCDIC)
- American Standard Code for Information Interchange(ASCII)
·
Struktur Data Array
Array
adalah sekumpulan variabel yang memiliki tipe data yang sama dan dinyatakan
dengan nama yang sama. Penomoran yang diberikan pada array dimulai dari angka
nol sampai angka maksimal. Contoh ada 10 nomor maka nomor pertama adalah nol
sampai 9.
·
Triangular Array
Triangular array dapat berupa :
1. Upper Triangular : Semua elemen di
bawah diagonal utama = 0
2. Lower Triangular : Semua elemen di atas
diagonal utama = 0
Jumlah baris (N) besar, elemen 0 tidak perlu disimpan
dalam memori.
Pendekatan :
1. Pelinieran array
2. Menyimpan bagian/elemen ≠ 0.
·
Sparse Array
Suatu array yang sangat banyak elemen nol-nya dikenal
sebagai sparse array.
Contoh :
Menyimpan elemen ≠ 0 saja, disimpan sebagai TRIPEL,
dengan bentuk :
(sub baris, sub kolom, nilai elemen)
TRIPEL tersebut
disimpan sebagai vektor.
·
Record
Suatu
kumpulan elemen hingga, terurut dan heterogen sebagai suatu unit. Elemen-elemen
dari suatu record disebut field.( Kumpulan dari field)
Field
adalah suatu area dari record yang menggunakan suatu informasi tertentu.
·
Mapping Ke Storage Dari Record
type S = record
v : integer;
n : array [1..10] of char;
end;
·
Stack
Stack adalah suatu
bentuk khusus dari linier list, dengan operasi penyisipan dan penghapusan
dibatasi hanya pada satu sisinya, yaitu puncak stack (TOP).
Operasi
stack : (LIFO)
last in first out
Ada
empat operasi dasar yang didefinisikan pada stack, yaitu :
1. CREATE(stack) : untuk membuat sebuah stack
kosong
NOEL(CREATE(S)) = 0 dan TOP(CREATE(S)) = null
2. ISEMPTY(stack) : utk menentukan apakah suatu stack adalah
stack kosong
ISEMPTY(S) = true, jika NOEL(S) = 0
= false, jika NOEL(S) 0
3. PUSH(elemen,stack) : utk menambahkan satu elemen ke dalam
stack
PUSH(E,S)
4. POP(stack) : untuk mengeluarkan satu elemen dari dalam stack
POP(S)
·
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 :
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.
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 :
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
Notasi postfix
Misal diberikan ekspresi aritmatik : A + B ;
Maka bentuknya dalam notasi postfix menjadi
: AB+
Jadi ekspresi aritmatik
: ( ( A + B ) * C / D + E^F ) / G ;
dalam notasi postfix menjadi : AB+D*C/EF^+G/
·
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.
·
Queue
Suatu bentuk khusus
dari linear list, dengan operasi penyisipan (insertion) hanya diperbolehkan
pada salah satu sisi, yang disebut REAR, dan operasi penghapusan (deletion)
hanya diperbolehkan pada sisi yang lainnya, yang disebut FRONT dari list.
Antrean Q = [Q1,
Q2, ... , QN]
Front(Q) = Q1
bagian depan antrean
Rear(Q) = QN bagian
belakang antrean
Noel(Q) = N jumlah
elemen dalam antrean
Elemen yang pertama
masuk merupakan elemen yang pertama
keluar.
Operator :
Penyisipan : Insert
Penghapusan :
Remove
Empat operasi dasar antrean, yaitu :
1.
CREATE
2.
ISEMPTY
3.
INSERT
4.
REMOVE
·
Cara Peletakan Elemen Pada Queue
Karakteristik yang membedakan queue (antrian) dari
stack adalah cara menyimpan dan mengambil data dengan struktur first in first out (FIFO). Hal ini berarti elemen pertama yang ditempatkan pada queue
adalah yang pertama dipindahkan. Contoh yang paling populer untuk
membayangkan sebuah queue adalah antrian pada kasir sebuah bank. Ketika seorang
pelanggan datang, akan menuju ke belakang dari antrian. Setelah pelanggan
dilayani, antrian yang berada di depan akan maju. Pada saat menempatkan elemen
pada ujung (tail) dari queue disebut dengan enqueue, pada saat memindahkan
elemen dari kepala (head) sebuah queue disebut dengan dequeue.
Pada Gambar 5.1 diperlihatkan sebuah queue serta
proses enqueue dan dequeue.
·
Dequeue (Queue Ganda atau Double Queue)
Suatu linear list, yang penambahan dan
penghapusan elemen dapat
dilakukan pada kedua sisi ujung list, tetapi
tidak dapat dilakukan
ditengah-tengah list.
Deque (menggunakan array sirkular)
Menggunakan 2 pointer/penunjuk :
1. LEFT : sisi kiri dari deque
2. RIGHT : sisi kanan dari deque
2 variasi deque, yaitu :
1. Deque Input Terbatas : Pemasukan elemen pada satu ujung list, penghapusan elemen pada kedua
ujung list.
2. Deque Output Terbatas : Pemasukan elemen pada kedua ujung list, penghapusan elemen pada salah
satu ujung list.
·
Priority Queue
Himpunan elemen, yang setiap elemennya telah
diberikan sebuah prioritas, dan urutan proses penghapusan elemen adalah berdasarkan
aturan berikut :
1. Elemen yang prioritasnya
lebih tinggi, diproses lebih dahulu dibandingkan dengan elemen yang
prioritasnya lebih rendah.
2. Dua elemen dengan prioritas
yang sama, diproses sesuai dengan
urutannya sewaktu dimasukkan ke dalam antrean berprioritas.
·
Linked List
Adalah koleksi
linier dari elemen data yang disebut Simpul atau Node.
Cara melinierkan
urutan adalah dengan menggunakan Penuding atau Pointer.
Setiap simpul
terdiri atas dua bagian yaitu :
1. Berisi informasi
data
2. Merupakan field
link atau nextpointer.
Link menghubungkan
satu elemen data ke elemen data lainnya, sehingga urutan
elemen data
tersebut membentuk suatu linier list.
Link akan bernilai
= 0 bila tidak menuding ke data (simpul) lainnya. Penuding ini
disebut Penuding
Nol.
Gambar list dengan
6 simpul
·
Linked List Dalam Memory
1. Array INFO(K) :
menyajikan bagian informasi
2. Array LINK(K) :
field nextpointer
3. Variabel START :
untuk menyimpan alamat dari elemen LIST
Pada bagian akhir
dari LIST, nextpointer bernilai NULL.
Menggambarkan suatu
linked list dalam memori.
Data dalam Array
INFO(K) adalah sebuah karakter tunggal.
·
Deklarasi Dalam Linked List
·
Manipulasi Linked List
Tidak bias dilakukan
langsung ke node yang dituju, harus menggunakan suatu pointer penunjuk ke node
pertama dalam linked list (disini adalah head). Deklarasinya adalah:
TNode*head;
·
Struktur Data Graf
Graf adalah kumpulan simpul (vertices atau nodes)
yang dihubungkan satu sama lain melalui sisi / busur (edges)
Perbedaan graf dengan pohon :
-
graf mungkin terjadi siklus
(cycle)
-
graf dapat terdiri lebih dari
satu sambungan
Graf G terdiri dua himpunan :
Verteks(simpul)
: V = himpunan simpul yang terbatas dan tidak kosong
Edge(sisi/busur)
: E = himpunan busur yang menghubungkan sepasang simpul
Jenis
Graf
·
Pohon Umum Dan Pohon Binar
Pohon
Biner
Kalau kita mempunyai sebuah struktur pohon yang umum
(general tree), maka ada sebuah
algoritma yang dapat menyajikannya secara pohon binar. Kita ingat
kembali bahwa pohon binar selalu terdiri
atas paling banyak dua subpohon, yakni subpohon kiri dan subpohon kanan. Pendefinisian ini berlaku secara
rekursif. Gambar 7.17 merupakan contoh dari pohon binar.
·
Sortir Dan Cariews
