Pertemuan 1
Data & Struktur Data
STRUKTUR DATA
Struktur Data adalah : suatu koleksi atau kelompok datayang dapat dikarakteristikan oleh organisasi serta operasi
yang didefinisikan terhadapnya.
Pemakaian Struktur Data yang tepat didalam proses
pemrograman, akan menghasilkan Algoritma yang lebih
jelas dan tepat sehingga menjadikan program secara
keseluruhan lebih sederhana.
STRUKTUR DATA
Pada garis besarnya, Data dapat dikategorikan menjadi :
A. Type Data Sederhana / Data Sederhana
Terdiri dari :
1. Data Sederhana Tunggal
Misalnya : Integer, Real/Float, Boolean dan
Character
2. Data Sederhana Majemuk
Misalnya : String
B. Struktur Data
Terdiri dari :
1. Struktur Data Sederhana
Misalnya Array dan Record
Konsep Dasar Tipe Data
2. Struktur Data Majemuk
Terdiri dari :
a. Linier
Misalnya : Stack, Queue dan Linear Linked List.
b. Non Linier
Misalnya : Pohon (Tree), Pohon Biner (Binary
Tree), Pohon Cari Biner (Binary Search Tree),
General Tree serta Graph.
TYPE DATA SEDERHANA (Dalam Program C++)
1. INTEGER
Merupakan Bilangan Bulat dan tidak mengandung
pecahan. seperti : ...-3,-2,-1,0,1,2,3,....
Integer | - 32768..32767 (2 byte)
Long | - 2147483648..2147483647 (4 byte)
Type Data Sederhana
2. FLOAT
Type data yang merupakan bilangan pecahan.
Jenis Data float ditulis dgn menggunakan
titik(koma) desimal.
Misalnya : 0.32 4,35 -131.128
Type Real dapat juga ditulis dengan Rumus :
M * R e = X
M = Pecahan, R = Radix,
e = Exponen, X = Hasil Bilangan,
Misalnya : 3.2 * 10 -1 = 0.32
4.35 * 10 2 = 435
TYPE DATA SEDERHANA
(Dalam Program C++)
3. BOOL ATAU LOGICAL
Type data yang hanya mempunyai dua bentuk keluaran
yaitu nilai True dan False (Benar dan Salah) yang
dinyatakan dengan 1 dan 0, Sehingga satuan data yang
terpakai cukup satu bit saja. Operator yang digunakan
adalah : And, Or dan Not.
4. CHARACTER
Type data yang terdiri dari aksara (simbol) yang
meliputi digit numerik, character alfabetik dan spesial
character. Untuk menuliskan tipe char, karakter perlu
ditulis di dalam tanda petik tunggal ( ‘ )
Contoh :
‘A’ = karakter berupa huruf A
‘1’ = karakter berupa angka 1
‘*’ = karakter simbol *
5. STRING
Merupakan type data majemuk yang terbentuk dari
kumpulan character sebanyak 256 (default) dengan
jangkauan niai 0 - 255. Kumpulan character yang
digunakan untuk membentuk String dinamakan
alfabet. Pemberian nilai String diapit dengan tanda
petik ganda (“)
Bentuk umum penulisan tipe data ini adalah :
tipe_data pengenal [panjang] ;
pengenal = nama variabel
panjang = bilangan bulat yg menunjukan jumlah
karakter
Contoh : char nama[15] ;
Fungsi pada Operasi STRING
1. Strcpy()
untuk menyalin nilai string.
2. Strcat()
untuk menggabungkan nilai string.
3. Strcmp()
untuk membandingkan 2 nilai string.
4. Strlen()
untuk mengetahui panjang nilai string.
5. Strchr ()
untuk mencari nilai karakter dalam string.
Pertemuan 2
ARRAY DIMENSI 1 & 2
Definisi Array? Array / Larik : Struktur Data Sederhana yang dapat
didefinisikan sebagai pemesanan alokasi memory
sementara pada komputer.
? Array dapat didefinisikan sebagai suatu himpunan hingga
elemen yang terurut dan homogen.
? Terurut : Dapat diartikan bahwa elemen tersebut dapat
diidentifikasi sebagai elemen pertama, elemen kedua dan
seterusnya sampai elemen ke-n.
? Homogen : Adalah bahwa setiap elemen dari sebuah
Array tertentu haruslah mempunyai type data yang sama.
Definisi Array
? Sebuah Array dapat mempunyai elemen yang seluruhnya
berupa integer atau character atau String bahkan dapat
pula terjadi suatu Array mempunyai elemen berupa Array.
? Karakteristik Array :
1. Mempunyai batasan dari pemesanan alokasi memory
(Bersifat Statis)
2. Mempunyai Type Data Sama (Bersifat Homogen)
3. Dapat Diakses Secara Acak
Definisi Array
?3 Hal yang harus diketahui dalam mendeklarasikan
array :
a. Type data array
b. Nama variabel array
c. Subskrip / index array
?Jenis Array (yang akan dipelajari) adalah :
a. Array Dimensi Satu (One Dimensional Array)
b. Array Dimensi Dua (Two Dimensional Array)
c. Array Dimensi Tiga (Thee Dimensional Array)
Array Dimensi Satu
1.ARRAY DIMENSI SATU (One Dimensional Array)
Dapat disebut juga dengan istilah vektor yang
menggambarkan data dalam suatu urutan
Deklarasi : Type_Data Nama_Variabel [index]
PEMETAAN (MAPPING)
ARRAY DIMENSI SATU KE STORAGE
Rumus : @A[i] = B + (i – 1) * L
Dimana : @A[i] : Posisi Array yg dicari
B : Posisi awal index di memory komputer
i : Subkrip atau indeks array yg dicari
L : Ukuran / Besar memory suatu type data
KONVERSI BILANGAN
1. Decimal adalah bilangan berbasis sepuluh yang
terdiridari 0, 1, 2, 3, 4, 5, 6, 7, 8, dan 9
2. Hexadecimal adalah bilangan berbasis enam belas yang
terdiri dari 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, dan F
Pertemuan 3
ARRAY DIMENSI BANYAK
3. ARRAY DIMENSI TIGA (Three Dimensional Array)Digunakan untuk mengelola data dalam bentuk 3
dimensi atau tiga sisi.
Deklarasi :
Type_Data Nama_Variabel [index1] [ndex2] [index3];
Misal : int A [3][4][2];
TRINGULAR ARRAY
(ARRAY SEGITIGA)
Tringular Array dapat merupakan Upper Tringular
(seluruh elemen di bawah diagonal utama = 0),
ataupun Lower Tringular (seluruh elemen di atas
diagonal utama = 0).
Dalam Array Lower Tringular dengan N baris, jumlah
maksimum elemen <> 0 pada baris ke-I adalah = I,
karenanya total elemen <> 0, tidak lebih dari
SPARSE ARRAY (ARRAY JARANG)
Suatu Array yang sangat banyak elemen nol-nya,
Pertemuan 4
Single Linked List (Non Circular)
KONSEP POINTER DAN LINKED LISTUntuk mengolah data yang banyaknya tidak bisa
ditentukan sebelumnya, maka disediakan satu fasilitas
yang memungkinan untuk menggunakan suatu perubah
yang disebut dengan perubah dinamis (Dinamic variable)
Perubah Dinamis (Dinamic variable)
Suatu perubah yang akan dialokasikan hanya pada saat
diperlukan, yaitu setelah program dieksekusi.
Perbedaan Perubah Statis & Dinamis
Pada perubah statis, isi Memory pada lokasi tertentu
(nilai perubah) adalah data sesungguhnya yang akan
diolah. Pada perubah dinamis, nilai perubah adalah
alamat lokasi lain yang menyimpan data sesungguhnya.
Dengan demikian data yang sesungguhnya dapat
dimasukkan secara langsung.
DEKLARASI POINTER
Pointer digunakan sebagai penunjuk ke suatu alamat
memori
Dalam pemrograman C++, Type Data Pointer
dideklarasikan dengan bentuk umum :
Type Data * Nama Variabel;
Type Data dapat berupa sembarang type data, misalnya
char, int atau float. Sedangkan Nama veriabel merupakan
nama variabel pointer
LINKED LIST (LINKED LIST)
Salah satu Struktur Data Dinamis yang paling
sederhana adalah Linked List atau Struktur Berkait
atau Senarai Berantai, yaitu suatu kumpulan komponen
yang disusun secara berurutan dengan bantuan
Pointer.
Linked List (Senarai Berantai) disebut juga dengan
Senarai Satu Arah (One-Way List). Masing-masing
komponen dinamakan dengan Simpul (Node).
Setiap simpul dalam suatu Linked List terbagi menjadi dua
bagian,yaitu :
1. Medan Informasi
Berisi informasi yang akan disimpan dan diolah.
2. Medan Penyambung (Link Field)
Berisi alamat berikutnya. Bernilai 0, Jika Link tersebut
tidak menunjuk ke Data (Simpul) lainnya. Penunjuk ini
disebut Penunjuk Nol.
Bentuk Node
Single Linked List non Circular
• Single : field pointer-nya hanya satu dan satu arah,pada
akhir node pointernya menunjuk NULL
• Linked List : node-node tersebut saling terhubung satu
sama lain.
Menempati alamat memori tertentu
• Setiap node pada linked list mempunyai field yang berisi
pointer ke node berikutnya, dan juga memiliki field yang
berisi data.
• Node terakhir akan menunjuk ke NULL yang akan
digunakan sebagai kondisi berhenti pada saat
pembacaan isi linked list.
Single Linked List non Circular
Menggunakan Head
• Dibutuhkan satu buah variabel pointer : head yang akan
selalu menunjuk pada node pertama
Deklarasi Pointer Penunjuk Head Single Linked List
• Manipulasi linked list tidak dapat dilakukan langsung ke
node yang dituju, melainkan harus menggunakan suatu
pointer penunjuk ke node pertama (Head) dalam linked
list
Function untuk mengetahui kondisi Single Linked List
• Jika pointer head tidak menunjuk pada suatu node
maka kosong
Menambah Node di Depan
• Penambahan node baru akan dikaitan di node paling
depan, namun pada saat pertama kali (data masih
kosong), maka penambahan data dilakukan dengan
cara: node head ditunjukkan ke node baru tersebut.
• Prinsipnya adalah mengkaitkan node baru dengan head,
kemudian head akan menunjuk pada data baru tersebut
sehingga head akan tetap selalu menjadi data terdepan.
Menambah Node di Belakang
• Penambahan data dilakukan di belakang, namun
pada saat pertama kali, node langsung ditunjuk oleh
head.
• Penambahan di belakang membutuhkan pointer bantu
untuk mengetahui node terbelakang. Kemudian,
dikaitkan dengan node baru.
• Untuk mengetahui data terbelakang perlu digunakan
perulangan.
Menghapus Node di Depan
• Penghapusan node tidak boleh dilakukan jika keadaan
node sedang ditunjuk oleh pointer, maka harus
dilakukan penggunakan suatu pointer lain (hapus) yang
digunakan untuk menunjuk node yang akan dihapus,
barulah kemudian menghapus pointer hapus dengan
menggunakan perintah delete.
• Sebelum data terdepan dihapus, terlebih dahulu head
harus menunjuk ke node berikutnya agar list tidak putus,
sehingga node setelah head lama akan menjadi head
baru
• Jika head masih NULL maka berarti data masih kosong!
Menghapus Node di Belakang
• Membutuhkan pointer bantu dan hapus. Pointer hapus
digunakan untuk menunjuk node yang akan dihapus,
pointer bantu untuk menunjuk node sebelum node yang
dihapus yang akan menjadi node terakhir.
• Pointer bantu digunakan untuk menunjuk ke nilai NULL.
Pointer bantu selalu bergerak sampai sebelum node
yang akan dihapus, kemudian pointer hapus diletakkan
setelah pointer bantu. Selanjutnya pointer hapus akan
dihapus, pointer bantu akan menunjuk ke NULL.
Menampilkan / Membaca
Isi Linked List
• Linked list ditelusuri satu-persatu dari awal sampai akhir
node. Penelusuran dilakukan dengan menggunakan
pointer bantu, karena pointer head yang menjadi tanda
awal list tidak boleh berubah/berganti posisi.
• Penelusuran dilakukan terus sampai ditemukan node
terakhir yang menunjuk ke nilai NULL.
Jika tidak NULL, maka node bantu akan berpindah ke
node selanjutnya dan membaca isi datanya dengan
menggunakan field next sehingga dapat saling berkait.
• Jika head masih NULL berarti data masih kosong!
Single Linked List non Circular
Menggunakan Head dan Tail
• Dibutuhkan dua variabel pointer : head dan tail
• Head selalu menunjuk pada node pertama, sedangkan
tail selalu menunjuk pada node terakhir.
• Kelebihan dari Single Linked List dengan Head & Tail
adalah pada penambahan data di belakang, hanya
dibutuhkan tail yang mengikat node baru saja tanpa
harus menggunakan perulangan pointer bantu.
Menghapus Node di Depan
(Dengan Head dan Tail)
• Penghapusan node tidak boleh dilakukan jika keadaan
node sedang ditunjuk oleh pointer, maka harus
dilakukan penunjukkan terlebih dahulu dengan pointer
hapus pada head, kemudian dilakukan pergeseran head
ke node berikutnya sehingga data setelah head menjadi
head baru, kemudian menghapus pointer hapus dengan
menggunakan perintah delete.
• Jika tail masih NULL maka berarti list masih kosong!
Menghapus Node di Belakang
(Dengan Head dan Tail)
• Penghapusan node tidak boleh dilakukan jika keadaan
node sedang ditunjuk oleh pointer, maka harus
dilakukan penunjukkan terlebih dahulu dengan variabel
hapus pada tail. Jika tail masih NULL maka berarti list
masih kosong!
• Dibutuhkan pointer bantu untuk membantu pergeseran
dari head ke node berikutnya sampai sebelum tail,
sehingga tail dapat ditunjukkan ke bantu, dan bantu
tersebut akan menjadi tail yang baru.
• Setelah itu hapus pointer hapus dengan menggunakan
perintah delete.
Pertemuan 5
STACK atau TUMPUKAN
STACK (TUMPUKAN)
Merupakan bentuk khusus dari Linier List yang pemasukandan penghapusan elemennya hanya dapat dilakukan pada
satu posisi, yaitu posisi akhir dari List (Top)
Prinsip Stack adalah LAST-IN-FIRST-OUT (LIFO).
OPERASI STACK
• ISEMPTY
Untuk memeriksa apakah stack kosong
• ISFULL
Untuk memeriksa apakah stack sudah penuh
• PUSH
Untuk menambahkan item pada posisi paling atas
(TOP)
• POP
Untuk menghapus item paling atas (TOP)
• CLEAR
Untuk mengosongkan stack
Inisialisasi
• Pada mulanya isi top dengan
-1, karena array dalam
C/C++ dimulai dari 0, berarti
stack adalah KOSONG
• TOP adalah variabel
penanda dalam STACK yang
menunjukkan elemen teratas
Stack.
• TOP of STACK akan selalu
bergerak hingga mencapai
MAX of STACK sehingga
menyebabkan stack PENUH
Fungsi IsEmpty
• Digunakan untuk
memeriksa apakah
stack masih dalam
kondisi kosong
• Dengan cara memeriksa
TOP of STACK.
Jika TOP masih = -1
maka berarti stack
masih kosong
Fungsi IsFull
• Digunakan untuk memeriksa apakah kondisi stack
sudah penuh
• Dengan cara memeriksa TOP of Stack.
Jika TOP of STACK = MAX_STACK-1 maka FULL
(Penuh).
Jika TOP of STACK < MAX_STACK-1 maka belum penuh
Fungsi PUSH
• Digunakan untuk memasukkan elemen ke dalam stack
dan selalu menjadi elemen teratas stack
• Dengan cara :
1. Menambah satu (increment) nilai TOP of
STACK setiap ada penambahan elemen
stack selama stack masih belum penuh
2. Isikan nilai baru ke stack berdasarkan indeks TOP
of STACK setelah ditambah satu (diincrement)
Fungsi POP
• Digunakan untuk menghapus elemen yang berada pada
posisi paling atas dari stack.
• Dengan cara :
1. Ambil dahulu nilai elemen teratas stack dengan
mengakses TOP of STACK.
2. Tampilkan nilai yang akan diambil.
3. Lakukan decrement nilai TOP of STACK
sehingga jumlah elemen stack berkurang 1
Fungsi CLEAR
• Digunakan untuk mengosongkan stack / membuat stack
hampa sehingga Top pada Stack berada kembali di
posisi Top = -1
Pertemuan 6
QUEUE (ANTREAN)
PENGERTIAN QUEUE (ANTREAN)Struktur Data Antrean (Queue) adalah suatu bentuk
khusus dari List Linier dengan operasi pemasukan data
hanya diperbolehkan pada salah satu sisi, yang disebut
sisi Belakang / ekor (Tail) dan operasi penghapusan
hanya diperbolehkan pada sisi lainnya yang disebut sisi
Depan / kepala (Head) dari LinkedList.
Prinsip Antrean : FIFO (First In First Out)
FCFS (First Come First Serve)
“Yang Tiba lebih awal Maka akan dilayani Terlebih
Dahulu”
OPERASI QUEUE
• CREATE
Untuk menciptakan dan menginisialisasi Queue
Dengan cara membuat Head dan Tail = -1
• ISEMPTY
Untuk memeriksa apakah queue kosong
• ISFULL
Untuk memeriksa apakah queue sudah penuh
• ENQUEUE
Untuk menambahkan item pada posisi paling belakang
• DEQUEUE
Untuk menghapus item dari posisi paling depan
• CLEAR
Untuk mengosongkan queue
Fungsi Create
• Digunakan untuk membentuk dan menunjukan awal
terbentuknya suatu Antrean / Queue
Fungsi IsEmpty
• Untuk memeriksa apakah Antrian penuh atau kosong
• Dengan cara memeriksa nilai Tail, jika Tail = -1 maka
antrian kosong (empty)
• Head adalah tanda untuk kepala antrian (elemen
pertama dalam antrian) yang tidak akan berubah-ubah
• Pergerakan pada Antrian terjadi dengan penambahan
elemen Antrian kebelakang, yaitu menggunakan nilai
Tail
Fungsi IsFull
• Untuk mengecek apakah Antrian sudah penuh
atau belum
• Dengan cara :
- Mengecek nilai Tail
- Jika tail = MAX-1 berarti antrian sudah penuh
(MAX-1 adalah batas elemen array dalam
program C++)
Fungsi Enqueue
• Untuk menambahkan elemen ke dalam Antrian,
penambahan elemen selalu dilakukan pada
elemen paling belakang
• Penambahan elemen selalu menggerakan variabel
Tail dengan cara menambahkan Tail terlebih dahulu
Fungsi Dequeue
• Digunakan untuk menghapus elemen terdepan (head)
dari Antrian
• Dengan cara : menggeser semua elemen antrian
kedepan dan mengurangi Tail dgn 1. Penggeseran
dilakukan dengan menggunakan looping
Fungsi Clear
• Untuk menghapus elemen-elemen Antrian dengan
cara membuat Tail dan Head = -1
• Penghapusan elemen-elemen Antrian sebenarnya
tidak menghapus arraynya, namun hanya mengeset
indeks pengaksesan-nya ke nilai -1 sehingga
elemen-elemen Antrian tidak lagi terbaca sehingga
mengembalikan antrian seperti keadaan semula
