STRUKTUR DATA SMTR 2

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

pencarian

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

•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

•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:

•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?)

•Memeriksa antrian.tail, jika antrian.tail== -1, berarti antrian masih kosong
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

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];
         }

 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.

•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.

•Ciri: tidak adanya keyword return, tidak adanya tipe datadidalam deklarasi fungsi, dan menggunakan         
  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.

•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

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