Struktur Data...
•Sistem pengorganisasian data
pada memori komputer (RAM) atau media penyimpanan menggunakan teknik: tumpukan,
antrian, pointer, dan senarai berantai.
•Teknik-teknik manipulasi data:
tambah
(add)
hapus
(delete)
edit
pengurutan
pohon
Sekilas bahasa C / C++
•BahasaC dibuat olehKen Thompson
dan Dennis M. Ritchie, tahun1978,untuk Sistem OperasiUnix oleh Bell Labs. Di dokumentasikan
dalam buku
“The C Programming Language”
•BahasaC (danturunannya: C++,
Visual C, C#) adalah salah satu bahasa pemrograman yang paling sering dipakai oleh
pemrogram
•Memperbolehkan mengakses memori
secara manual, menggunakan pointer
•Sering dipakai untuk membuat bahasa
pemrograman yang lain, bahkan untuk membuat sistem operasi !
•BahasaC yang digunakan sekarang
berdasarkan standarisasi ANSI tahun1989
Identifier & TipeData C
•Identifier adalah nama (ataupengingat)
dari tempat penyimpanan data didalam memori komputer. Secara umum dibedakan,
Variabel:
isi data bisa diubah
Konstanta: isi data bersifat tetap
Beberapa istilah dalam bahasa C
–Source code: kode program
–Compile (build): pengubahan source
code kedalam object code (bisa bahasa mesin / assembly)
–Executable: program dalam bahasa
mesin yang siap dieksekusi.
–Library: fungsi-fungsi yang
digunakan pada program
–Preprocessor Directive
•Dimulai dengan tanda #
•Header file: file yang berekstensi. h yang
disertakan pada program.
Keywords of C
•Flow control (6) –if, else, return, switch,
case, default
•Loops (5) –for, do, while, break,
continue
•Common types (5) –int, float, double, char,
void
•Structures(2) –struct, typedef
•Sizing things (1) –sizeof
•Rare but still useful types (7)
–extern, signed,
unsigned, long, short, static, const
Variabel
•Kita harus mendeklarasikan tipe
data setiapvariabel padaC.
•Setiap varibel punya tipedata
dan namanya.
•Variabel adalah unik, tidak boleh
berupa keyword, dimulai dengan huruf atau underline, maks 32 karakter
Evil keywords which we avoid (1)
–goto
FUNGSI MAIN()
•function main() dibutuhkan
agar program C dapat dieksekusi!
•Tanpa function main, program C
dapat dicompil tetapi tidak dapat dieksekusi (harus dengan flag parameter –c,
jika di UNIX)
•Pada saat program C dijalankan,
maka compiler C pertama kali akan mencari function main() dan melaksanakan instruksi-instruksi
yang ada disana.
intmain()
•Berarti di dalam function main
tersebut harus terdapat keyword return dibagian akhir fungsi dan mengembalikan nilai
bertipe data int,
•Mengapa hasil return harus bertipe
int juga? karena tipe data yang mendahului fungsi main()
diatas dideklarasikan int
diatas dideklarasikan int
•Tujuan nilai kembalian berupa integer
adalah untuk mengetahui status eksekusi program.
–jika “terminated successfully” (EXIT_SUCCESS) maka, akan dikembalikan status
0,
–sedangkan jika“terminated
unsuccessfully” (EXIT_FAILURE) akan dikembalikan
nilai status tidak 0, biasanya
bernilai1
bernilai1
•Biasanya dipakai dilingkungan UNIX
Area pemakaianVariabel
•Area pemakaian variabel(the scopeof
a variable) is where it can be used in a program
•Normally variables are localin
scope -this means they can only be used in the function where they are
declared (main is a function)
•If we declare a variable
outside a function it can be used in any function beneath where it is
declared declare global variables.
variabel
global dapat digunakan oleh baris program yang ada dibawahya.
•Global variables are A BAD
THING
Cara umum(sederhana) untuk melakukan pengecekan kesalahan (debugging)
•Check missing brackets and
commas.
•Check that you have a semicolon
at the end of every line which needs one.
•Put in some printf
–if you know what your program
is DOING you will know what it is Doing wrong or Doing right.
•Try to explain to someone else
what the program is meant to do.
•Take a break, get a cup of
coffee and come back to it fresh.
–Debugging is FRUSTRATING
PENDEKLARASIAN VARIABEL DA KONSTANTA
Antrian (Queue)
•Susunan koleksi data dimana proses penambahan data (add) dilakukan dari
belakang dan penghapusan data (delete) dilakukan dari depan.
•Antrian bersifat FIFO (First In First Out)
FIFO Data yang pertama masuk ke dalam antrian menjadi data yang pertama
keluar dari antrian.
OperasiAntrian
Macam-macam operasi antrian:
OperasiAntrian
Macam-macam operasi antrian:
•EnQue: menambah data pada antrian (dari belakang, posisi tail,atau
ekor)
•DeQue: menghapus
data pada antrian (dari depan, posisi head, atau kepala)
•IsEmpty: menguji
apakah antrian dalam keadaan kosong
•IsFull: menguji
apakah antrian dalam keadaan penuh
•Print: menampilkan
semua elemen (isi) antrian
•Clear: mengosongkan
atau menghapus semua elemen (isi) antrian
Implementasi antrian dengan struct
Langkah-langkah...
•Definisikan
konstanta MAX_QUEUE untuk
menyimpan nilai maksimum isi QUEUE
•Definisikan
queue menggunakan tipe data
struct (struct queue)
•Elemen
struct queue adalah:
int head, int
tail, dan int data [MAX_QUEUE -1]
(head mencatat posisi data
paling depan
tail mencatat posisi data paling belakang
data mencatat isi antrian)
•Definisikan
variabel antrian (yang bertipe
queue)
Deklarasi awal
•Deklarasi MAX_QUEUE
#define MAX_QUEUE 8
•Deklarasi QUEUE dengan tipe data struct
typedef struct QUEUE
{
int head;
int
tail;
int
data[MAX_QUEUE-1];
};
•Deklarasi antrian yang bertipe QUEUE
QUEUE antrian;
Inisialisasi
Inisialisasi Antrian
•Inisialisasi isi head dan tail=
-1 , berarti isi antrian masih kosong atau belum berisi data.
(ingat indeks array dalam bahasa C dimulai dari 0)
•head variabel yang mencatat (menunjukkan) posisi paling
depan antrian.
•tail variabel yang mencatat (menunjukkan) posisi paling
belakang antrian dan sekaligus juga cacah data di dalam antrian.
FungsiIsEmpty
dan IsFull
Fungsi IsEmpty (memeriksa apakah Antrian masih kosong?)
Fungsi IsEmpty (memeriksa apakah Antrian masih kosong?)
•Memeriksa antrian.tail,
jika antrian.tail== -1, berarti antrian masih kosong
Fungsi IsFull (memeriksa apakah Antrian sudah penuh?)
Fungsi IsFull (memeriksa apakah Antrian sudah penuh?)
•Memeriksa antrian.tail,
jika antrian.tail== [MAX_QUEUE-1], berarti antrian sudah penuh
Fungsi EnQueue
•Menambah data pada antrian
(dari belakang, posisi tail,atau ekor)
Algoritma EnQueue
•Apabila antrian belum terisi
penuh, lakukan:
–Jika antrian.tail== -1(berarti
akan menambah data ke dalam antrian dalam kondisi awal antrian tidak ada data)
maka ubah nilai antrian.head=0
–Perbarui nilai antrian.tail,
dengan menambah satu (increment) antrian.tail=
antrian.tail +1atau antrian.tail ++
–Isikan data baru ke antrian
•Apabila antrian telah terisi
penuh, batalkan penambahan data, tampilkan pesan “antrian telah terisi
penuh“
Fungsi DeQueue
•Untuk menghapus data pada
antrian (dari depan, posisi head, atau kepala).
Algoritma DeQueue
•Apabila antrian tidak dalam
keadaan kosong, lakukan:
–Tampilkan data yang akan
dihapus
–Jika cacah data antrian >1,
hapus data tersebut dengan cara melakukan proses “Refresh“. Proses “Refresh“
yaitu pindahkan semua isi antrian.data[ i+1 ] ke dalam antrian.data[ i ]dengan
nilai i=0 sampai dengan antrian.tail-1. Perbarui nilai antrian.tail,
dengan mengurangi satu (decrement) antrian.tail=antrian.tail-1atau antrian.tail--
–Jika cacah data antrian =1,
hapus data tersebut dengan cara mengubah nilai antrian.head = antrian.tail = -1
•Apabila antrian dalam
keadaan kosong, batalkan penghapusan data, tampilkan pesan “antrian dalam
keadaan kosong“
Fungsi Print
•Untuk menampilkan semua elemen
(isi) antrian.
•Menggunakan proses perulangan,
dimulai dari indeks array antrian.head sampai dengan antrian.tail.
•Nilai antrian.head dan
antrian.tail tidak diubah
(karena hanya
menampilkan isi antrian saja)
Fungsi Clear
•Untuk mengosongkan atau
menghapus semua elemen (isi) antrian
•Cara1. Menggunakan proses
DeQueue yang diulang sebanyak:
antrian.tail+1
kali (jika perulangan dimulai dari
indeks 1), atau antrian.tail kali (jika perulangan dimulai dari indeks
0)
Perhatikan,
perulangan bukan sebanyak MAX_QUEUE
•atau Cara2. Mengubah nilai
antrian.head= antrian.tail dengan -1
LATIHAN SOAL
•Buatlah fungsi untuk mencari suatu elemen dalam antrian
•Buatlah fungsi untuk mengedit suatu elemen dalam antrian
•Buatlah fungsi untuk mencari nilai total, nilai rata-rata, nilai terbesar, dan nilai terkecil, dari elemen antrian
•Buatlah fungsi untuk mencari suatu elemen dalam antrian
•Buatlah fungsi untuk mengedit suatu elemen dalam antrian
•Buatlah fungsi untuk mencari nilai total, nilai rata-rata, nilai terbesar, dan nilai terkecil, dari elemen antrian
TUMPUKAN(STACK)
•Susunan koleksi data dimana
proses penambahan data (add) dan penghapusan data (delete) selalu dilakukan
melalui posisi akhir data.
•Posisi akhir data top of stack
•Stack bersifat LIFO (Last In
First Out)
LIFO Data
yang terakhir masuk ke dalam stack menjadi data yang pertama keluar dari stack
Operasi Stack
Macam-macam operasi stack:
•Push: menambah
data pada stack (tumpukan paling atas)
•Pop: menghapus
data pada stack (tumpukan paling atas)
•IsEmpty: menguji apakah stack dalam keadaan kosong
•IsFull: menguji
apakah stack dalam keadaan penuh
•Print: menampilkan
semua elemen (isi) stack
•Clear: mengosongkan
atau menghapus semua elemen (isi) stack
•Peek (‘mengintip’): menampilkanataumelihatisistack padaposisiteratas(top of
stack) saja
Implementasi stack dengan struct
Langkah-langkah...
•Definisikan konstanta MAX_STACK untuk
menyimpan nilai maksimum isi stack
•Definisikan stack menggunakan
tipe data struct (struct stack)
•Elemen struct stack adalah:
int top dan
int data [MAX_STACK -1]
(top mencatat
posisi data teratas
data mencatat
isi stack)
•Definisikan variabel tumpuk (yang
bertipe stack)
Deklarasi awal
•Deklarasi MAX_STACK
#define MAX_STACK 8
•Deklarasi
STACK dengan tipe data struct
typedef struct STACK
{
int top;
int data[MAX_STACK-1];
};
•Deklarasi
tumpuk yang bertipe STACK
STACK tumpuk;
Inisialisasi
Inisialisasi Stack
•Inisialisasi isi top= -1 , berarti isi stack masih
kosong, atau belum berisi data. (ingat indeks array dalam bahasa C dimulai dari
0)
•top variabel penanda yang menunjukkan cacah data di dalam stack.
Fungsi Push
•Untuk
menambah data pada stack (tumpukan paling atas). Data yang diinputkan selalu
menjadi elemen teratas Stack (Top of Stack).
Algoritma Push
•Apabila
stack belum terisi penuh, lakukan:
–Perbarui
nilai top, dengan menambah satu (increment) nilai top (top=top+1atau top++)
–Isikan
data baru ke stack (pada posisi top yang baru)
•Apabila
stack telah terisi penuh, batalkan penambahan data, tampilkan pesan
“stack telah terisi penuh“
Fungsi Pop
•Untuk menghapus data pada stack
(tumpukan paling atas). Data yang dihapus selalu menjadi elemen teratas
Stack (Top of Stack)
Algoritma
Pop
•Apabila stack tidak dalam
keadaan kosong, lakukan:
–Tampilkan data yang akan
dihapus, hapus data tersebut.
–Perbarui nilai top, dengan
mengurangi satu (decrement) nilai top(top=top-1atau top--)
•Apabila stack dalam keadaan
kosong, batalkan penghapusan data, tampilkan pesan “stack dalam keadaan
kosong“
Fungsi Print
•Untuk
menampilkan semua elemen (isi) stack.
•Menggunakan
proses perulangan, dimulai dari indeks array terbesar, diteruskan ke indeks
yang lebih kecil.
•Nilai
top tidak diubah
(karena hanya menampilkan isi stack
saja)
Fungsi Clear
•Untuk mengosongkan atau
menghapus semua elemen (isi) stack
•Cara1. Menggunakan proses
Pop yang diulang sebanyak Top+1 kali
Perhatikan,
perulangan bukan sebanyak MAX_STACK
•Cara2. Mengubah nilai Top
dengan -1 (Top = -1)
FungsiPeek
(‘mengintip’)
•Digunakanuntukmenampilkanataumelihatisistack
padaposisiteratas(top of stack) saja.
Perhatikan,
Bedakandenganmenampilkannilai top.
int peek()
{
return tumpuk.data[tumpuk.top];
}
{
return tumpuk.data[tumpuk.top];
}
Function
•Fungsi/function adalah bagian dari
program yang memilikinama tertentuyang unik, digunakan untuk mengerjakan
suatu pekerjaan tertentu, serta letaknya dipisahkan dari bagian program
yang menggunakan/memanggil fungsi tersebut.
Keuntungan menggunakan Function
•Program besar dapat dipecah menjadi
program-program kecil, yang dapat dikerjakan oleh beberapa orang secara gotong-royong.
•Kemudahan dalam mencari kesalahan
program karena kesalahan dapat dilokalisasi dalam suatu
modul tertentu saja.
modul tertentu saja.
•Modifikasi program dapat dilakukan
pada suatu modul tertentu saja tanpa mengganggu program keseluruhan.
•Reusability: fungsi dapat
digunakan kembali oleh program lain atau
fungsi dapat dipanggil secara berulang-ulang, tanpa harus menulisnya kembali.
KategoriFunction padaC
Standard
Library Function
•Yaitu fungsi-fungsi yang telah
disediakan oleh C dalam file-file header atau librarynya.
•Misalnya: clrscr(), printf(), getch()
•Untuk function ini kita harus
mendeklarasikan terlebih dahulu library yang akan digunakan, yaitu dengan
menggunakan preprosesor direktif: #include <conio.h>
User-Defined
Function
•Adalah function yang dibuat
oleh programmer sendiri. Function ini memiliki nama tertentu yang unik dalam
program, letaknya terpisah dari program utama, dan bisa dijadikan satu ke dalam
suatu library buatan programmer itu sendiri yang kemudian juga di-include-kan
untuk penggunaanya.
Jenis Function
Function Void
•Fungsi yang void sering disebut
juga prosedur.
•Disebut void karena fungsi tersebut
tidak mengembalikan suatu nilai keluaran yang didapat dari hasil proses fungsi
tersebut.
tersebut.
•Ciri: tidak adanya keyword return,
tidak adanya tipe datadidalam deklarasi fungsi, dan menggunakan
keyword void.
keyword void.
•Tidak memiliki nilai kembalian fungsi.
•Contoh: clrscr(), printf()
Function
non-Void
•Fungsinon-void disebut juga function
•Disebut non-void karena mengembalikan
nilai kembalian yang berasal dari keluaran hasil proses function tersebut
•Ciri: ada keyword return, ada
tipe data yang mengawali deklarasi fungsi, dan tidak ada keyword void
•Dapat dianalogikan sebagai suatu variabel yang memiliki tipe
data tertentu sehingga dapat langsung ditampilkan hasilnya.
•Contoh: sin(), getch()
Function main()
•Sebuah program yang paling
sederhanadalamC, agar dapat dieksekusiharus terdiri dari minimal 1 buahfungsi,
yaitu function main()
•Pada saat program C dijalankan,
maka compiler C akan mencari function main() dan melaksanakan instruksi-instruksi
yang ada disana.
•Di dalam function main, sering dideklarasikan
dalam 2 bentuk:
–int main()
–void main()
Function int main() dan void
main()
•int
main()berarti didalam function main
tersebut harus terdapat keyword return dibagian akhir fungsi dan mengembalikan nilai
bertipe data int.
•Mengapa hasil return harus bertipe
int juga ? karena tipe data yang mendahului fungsi main()
diatas dideklarasikan int.
diatas dideklarasikan int.
•Jika sebuah program C
dieksekusi, maka akandikembalikan status eksekusi program, jika “terminated
successfully” maka, akan dikembalikan status 0, sedangkan jika “terminated
unsuccessfully” akan dikembalikan nilai status tidak 0.
•void
main()berarti function yang void dan tidak mengembalikan nilai status
program sehingga nilai status program tidak bisa diketahui.
Argumen pada Function
•Sebuah fungsi bisa memiliki argumen-argumen
yang bersifat opsional.
•Argumenter sebut berfungsi sebagai
parameter inputan yang berupa variabel-variabel bagi fungsi tersebut(bersifat lokal),
dan argumen disini harus bertipe data tertentu.
•Terdapat 2 jenis parameter:
–Parameter formal: parameter yang ditulis pada deklarasi fungsi.
–Parameter aktual: parameter
yang di inputkan dalam program pemanggil fungsi tersebut. Dapat berupa variabel
atau langsung berupa nilai tertentu sesuai dengan tipe data yang dideklarasikan
untuk masing-masing parameter fungsi.
Ruang Lingkup Variabel Pada
Function
•Variabel Global: dikenal disemua
bagian.
•Variabel Lokal: dikenal hanya dibagian
tertentu saja.
•Variabel Static: nilainya tetap
dan nilai terakhir akan tetap disimpan.
Pengiriman by value
•Yang dikirimkan ke fungsi adalah
nilainya, bukan alamat memori letak dari datanya.
•Fungsi yang menerima kiriman nilai
ini akan menyimpan nilainya di alamat terpisah dari nilai asli yang di gunakan
oleh program yang memanggil fungsi tersebut, sehingga pengubahan nilai didalam fungsi
tidak akan berpengaruh pada nilai asli diprogram yang memanggil fungsi (walaupun
menggunakan nama variabel sama).
•Sifat pengiriman Satu arah, dari program pemanggil kefungsi
yang dipanggil saja.
•Parameter bisa berupa ungkapan (statemen).
Pengiriman By Reference
•Yang dikirimkan adalah alamat
memori letak dari nilai datanya, bukan nilai datanya.
•Fungsi yang menerima parameter
ini akan menggunakan data dengan alamat
yang sama dengan alamat nilai datanya, sehingga pengubahan nilai difungsi akan
mengubah juga nilai asli diprogram pemanggil fungsi tersebut.
•Pengiriman parameter by
reference adalah pengiriman dua arah, yaitu dari program pemanggil kefungsi
dan sebaliknya dari fungsi keprogram pemanggilnya.
•Pengiriman parameter by
reference tidak dapat digunakan untuk suatu ungkapan (statemen), hanya bisa
untuk variabel, konstanta atau elemen array saja.
Parameter Berupa Array
•Pengiriman parameter berupa array
sebenarnya adalah pengiriman by reference, yang dikirimkan adalah alamat
elemen pertama dari array, bukan seluruh nilai-nilai arraynya.
•Pada parameter formal, alamat elemen
pertama dari array dapat ditulis berupa nama array saja tanpa ditulis indeksnya
(kosong).
•Pada parameter aktual,
penulisan dilakukan dengan menuliskan nama arraynya saja.
Pointer
atau variabel pointer
•Pointer adalah suatu variabel penunjuk,
berisi nilai yang menunjuk alamat suatu lokasi dimemori tertentu.
•Pointer tidak berisi nilai data,
melainkan berisi suatu alamat memori atau null jika tidak menunjuk suatu alamat
memori.
•Diketahui variabel X yang berisi karakter
‘a’. Karakter ‘a’ ini akan disimpan disuatu alamat tertentu dimemori. Alamat variabel
X dapat diakses menggunakan statemen & X.
•Jika ingin menyimpan alamat dari variabel
X diatas, dapat dilakukan dengan cara:
char alamat_x= &X;
•Variabel alamat_x disebut pointer
atau variabel pointer, suatu variabel yang berisi alamat penyimpan karakter ‘a’.
Aturan
•variabel pointer dapat dideklarasikan
dengan tipe data apapun.
•Pendeklarasian variabel pointer
dengan tipe data tertentu digunakan untuk menyimpan alamat memori yang berisi data
sesuai dengan tipe data yang dideklarasikan.
•Tipe data digunakan sebagai lebar data
untuk alokasi memori (misal char berarti lebar datanya1 byte, dst)
•jika suatu variabel pointer
dideklarasikan bertipe float, berarti variabel pointer tersebut hanya bisa digunakan
untuk menunjuk alamat memori yang berisi nilai bertipe float juga.
Operasi pada Pointer
Operasi
assignment
•Antar variabel pointer dapat dilakukan operasi assignment.
•Contoh1: Assignment dan sebuah alamat dapat ditunjuk oleh lebih dari satu pointer
•Contoh2: Mengisi variabel dengan nilai yang ditunjuk oleh sebuah variabel pointer
•Contoh3: Mengoperasikan isi variabel dengan menyebut alamatnya dengan pointer
•Contoh4: Mengisi dan mengganti variabel yang ditunjuk oleh pointer
•Antar variabel pointer dapat dilakukan operasi assignment.
•Contoh1: Assignment dan sebuah alamat dapat ditunjuk oleh lebih dari satu pointer
•Contoh2: Mengisi variabel dengan nilai yang ditunjuk oleh sebuah variabel pointer
•Contoh3: Mengoperasikan isi variabel dengan menyebut alamatnya dengan pointer
•Contoh4: Mengisi dan mengganti variabel yang ditunjuk oleh pointer
Pointer
padaArray
•Pada array, pointer hanya perlu menunjuk
pada alamat elemen pertama saja karena letak alamat array sudah berurutan
pada memori.
•Variabel pointer hanyaperlu increment
•Lihat contoh-contoh!
SumberReferensi
•James Roberge, Stefan Brandle,
danDavid Whittington, 2003, C++ Data Structures 2nd Edition, Jones and Bartlett
Publishers, Inc., Sudbury, Massachusetts.
•Antonius RachmatChrismanto–UKDW
Yogyakarta.
•P. Insap Santosa, 1992, Struktur Data
Menggunakan Turbo Pascal 6.0, Penerbit Andi, Yogyakarta.
•Berbagai sumber dari Internet.
pakhartono.wordpress.com
Tidak ada komentar:
Posting Komentar