algoritma dan struktur data
DESCRIPTION
Materi Algoritma dan Struktur Data mengenai Bahasa C/C++TRANSCRIPT
MODUL PANDUAN PRAKTIKUM
ALGORITMA DAN STRUKTUR DATA
Disusun oleh
Tim Asisten Praktikum
Algoritma dan Struktur Data
Program Studi Teknik Informatika
Fakultas Sains dan Teknologi
Universitas Islam Negeri Sunan Kalijaga
Yogyakarta 2012
KATA PENGANTAR
Assalamu’alaikum wr wb
Kami panjatkan rasa syukur kepada Allah Subhanahuwata’ala yang telah
melimpahkan rahmatNya, sehingga kami mampu menyelesaikan penyusunan buku panduan
praktikum Algoritma dan Struktur Data.
Buku ini ini terdiri dari 14 modul dengan asumsi setiap modul diselesaikan dalam 1
kali praktikum. Setiap modul berisi pengantar materi yang akan dibahas, kemudian
dilanjutkan dengan latihan soal dikerjakan di kelas serta latihan soal dikerjakan di rumah
dengan rincian materi yang tersebar dalam beberapa modul adalah implementasi slass dan
objectnya, rekursif, pointer, link list, queue, stack, sorting dan searching.
Diharapkan setelah mahasiswa mempelajari secara tekun dan rajin dengan melakukan
praktek berulang-ulang baik di kelas maupun di rumah, mahasiswa akan mampu dan trampil
dalam menyusun suatu konsep algoritma khususnya yang terkait dengan manajemen struktur
data dengan baik dan benar kemudian mampu memngimplementasikan dalam pemrograman
menggunakan bahasa C.
Selanjutnya, kami ucapkan banyak terima kasih kepada seluruh asisten Algoritma dan
Struktur Data yang telah banyak membantu sehingga modul panduan praktikum Algoritma
dan Struktur Data ini dapat diselesaikan.
Wassalamu’alaikum wr wb
Yogyakarta, Juni 2012
Dosen Pengampu
Sumarsono
DAFTAR ISI
Halaman Judul……………………………………………………………………………. i
Kata pengantar……………………………………………………………………………. ii
Daftar isi………………………………………………………………………………….. iii
Modul 1 : Class .................................................................................................................. 1
Modul 2 : Fungsi ................................................................................................................. 9
Modul 3 : Rekursif .............................................................................................................. 19
Modul 4 : Pointer ................................................................................................................ 23
Modul 5 : Pointer Lanjutan ................................................................................................. 26
Modul 6 : Link List ............................................................................................................. 28
Modul 7 : Link List lanjutan .............................................................................................. 32
Modul 8: Queue .................................................................................................................. 36
Modul 9 : Stack .................................................................................................................. 40
Modul 10 : Sorting .............................................................................................................. 44
Modul 11 : Sorting Lanjutan ............................................................................................... 50
Modul 12 : Searching ......................................................................................................... 54
Modul 13 : Review Materi Bagian 2 .................................................................................. 55
Modul 14 : Review Materi Bagian 2 .................................................................................. 55
MODUL PRAKTIKUM 1
CLASS
Class adalah objek perluasan dari struktur data. Kelas dapat memegang data dan fungsi.
Object adalah instan dari kelas. Di sini kelas akan menjadi JENIS dan objek akan menjadi
VARIABEL.
Formatnya….
class nama_class {
access_specifier_1:
member1;
access_specifier_2:
member2;
...
} nama_object;
Di sini isi deklarasi member dapat berupa data atau deklarasi fungsi, dan optional specifier.
Contoh:
Classnya bernama CRectangle dan objectnya bernama rect.
2 data member bertipe int (x dan y) dengan akses private(private adalah akses dafault) dan 2
member fungsi yakni set_values dan area dengan akses public
Contoh Class beserta variable public
Di fungsi utama setelah deklarasi CRectangle dan rect, untuk memanggilnya menggunakan tanda
(.) diikuti nama member.
Operator of scope ditandai dengan tanda :: (dobel titikdua). digunakan untuk mendefinisikan
member dari class di luar definisi class itu tadi.
Constructors dan Destructors 1. Constructor
Jika melihat contoh source code di atas, apa yang terjadi jika fungsi area() dipanggil sebelum
memanggil fungsi set_values?? Hasilnya pasti bakal aneh karena x dan y tidak pernah terdefinisi.
Untuk menghindarinya kita menggunakan Constructor.
Constructor harus memiliki nama yang sama dengan nama class dan tidak dapat memiliki
return dan void.
Contoh dengan Constructor:
2. Destructor Kebalikannya Constructor. Akan terpanggil kalo scope-nya uda terpenuhi.
Destructor harus memiliki nama yg sama dengan Class tapi diikuti tanda tilde(~).
Digunakan untuk membebaskan memori.
Contoh Program Destructor
Pointers to Classes
Kita dapat menggunakan nama kelas sebagai tipe pointer. Contoh…
CRectangle * prect;
Artinya adalah pointer untuk objek di kelas CRectangle.
Contoh Program Pointer to Classes
Overloading operators
Bentuknya itu adalah fungsi reguler diikuti 'operator' diikuri tanda operator yang mau
kita overload.
Sintak Overloding operator :
type operator sign (parameters) { /*...*/ }
Contoh Program Overloding operator
Kata Kunci “This”
Kata kunci this dipakai untuk mewakili object yang dipunyai oleh member yang mengeksekusi kata kunci this ini.
Gambaran singkat
Gambar diatas menunjukkan bagaimana kata kunci this bekerja menunjukkan kepada diri sendiri atau object yang menaunginya.
Contoh Program this
Static Member
Class dapat berupa static member selain terdapat banyak data dan fungsi didalamnya. Static variable merupakan variable statis dan tidak berubah sejak pertamakali dideklarasikan. Variable ini sering disebut dengan variable class karena nilainya adalah unique dan satu-satunya dalam class tersebut.
Contoh Program Static Member
Tugas di Rumah
Silahkan Lengkapi Kode dibawah ini untuk menghasilkan program seperti di gambar…
MODUL PRAKTIKUM 2
Fungsi
Fungsi adalah sekumpulan perintah operasi program yang dapat menerima argumen
input dan dapat memberikan hasil output yang dapat berupa nilai ataupun sebuah hasil
operasi. Hasil akhir fungsi akan berupa sebuah nilai balik (return)
Nama fungsi yang didefinisikan sendiri oleh pemrogram tidak boleh sama dengan
nama build-in function pada compiler C++.
Fungsi digunakan agar pemrogram dapat menghindari penulisan bagian program
(kode) berulang-ulang, dapat menyusun kode program agar terlihat lebih rapi dan kemudahan
dalam debugging program. Parameter adalah nama-nama peubah yang dideklarsikan pada
bagian header fungsi. Pemrogram dapat membuat fungsi yang didefinisikan sendiri olehnya.
PROTIPE FUNGSI
Sebuah fungsi tidak dapat dipanggil kecuali sudah dideklarasikan, deklarasi fungsi dikenal
dengan sebutan prototipe fungsi. Prototipe fungsi berupa :
1. Nama Fungsi
2. Tipe nilai fungsi
3. Jumlah dan tipe argumen
Dan diakhiri dengan titik koma, sebagaimana pada pendeklarasian variabel. Sebagai
contoh:
1. long kuadrat ( long l) ;
Pada contoh pertama, fungsi kuadrat ( ) mempunyai argumen bertipe long dan nilai balik
bertipe long .
2. void garis ( );
Pada contoh kedua, fungsi garis ( ) tidakmemiliki argumen dan nilai baliknya tidak ada (
void ).
3. double maks ( double x, double y)
Pada contoh ketiga, fungsi maks( ) mempunyai dua buah argumen, dengan masing-
masing argumen bertipe double.
1. Contoh Progam fungsi 1
2. Contoh Progam fungsi 2
KOLABORASI FUNGSI DALAM CLASS
Contoh pembuatan objek segitiga bernama x:
Tugas di Rumah
1. Buat class kubus dengan property
- Sisi
- Metode Memasukkan data (Public)
- Metode mencari Luas Permukaan dan Volume (Public)
2. Buat class balok dengan property
- Panjang
- Lebar
- Tinggi
- Metode Memasukkan data (Public)
- Metode Mencari Luas Permukaan dan Volume (Public)
3. Gabungkan class kubus dan balok sehingga penggunaannya dapat dipilih oleh user,
seperti contoh dibawah ini :
- Jika Memilih Kubus
- Jika Memilih Balok
Modul Praktikum 3
Rekursif
Perbedaan dan Persamaan Rekursif dan Iteratif :
Persamaan
- Sama-sama merupakan bentuk perulangan.
- Dilakukan pengecekan kondisi terlebih dahulu sebelum mengulang.
Perbedaan
- Iteratif menggunakan FOR, WHILE, DO-WHILE sedangkan rekursif hanya
menggunakan IF.
- Iteratif dapat berjalan pada program yang terdiri dari prosedur (Tidak terdapat fungsi)
sedangkan rekursif merupakan fungsi.
Percobaan Rekursif 1
Percobaan Rekursif 2
Tugas di Rumah
1. Buatlah Program Utuh dari fungsi faktorial dibawah ini
2. Buatlah Program Permutasi dan Kombinasi dari fungsi factorial di atas dengan aturan
a) Kombinasi N dari R= N! / ((N-R)! * R!)
Jika N<R Maka data tidak valid
b) Permutasi N dari R= N! / (N-R)!
Jika N<R maka data tidak valid
Output Program yang diharapkan :
Jika memilih kombinasi, outputnya adalah :
Jika memilih Permutasi, ,outputnya adalah :
3. Buatlah Program deret Fibbonaci dengan fungsi rekursif
1 1 2 3 5 8 13 21 34 55 dst
Dimana bilangan selanjutnya adalah perjumlahan 2 bilangan sebelum
Output yang diharapkan adalah
MODUL PRAKTIKUM 4
POINTER
• Pointer adalah suatu variabel penunjuk, berisi nilai yang menunjuk alamat suatu lokasi
memori tertentu.
• Jadi pointer tidak berisi nilai data, melainkan berisi suatu alamat memori atau null jika
tidak berisi data.
• Lokasi memori tersebut bisa diwakili sebuah variabel atau dapat juga berupa nilai alamat
memori secara langsung.
Perbedaan Pointer dengan Variabel biasa
Operator Pointer
Deklarai Pointer
tipe_data *nama_variabel_pointer;
Contoh inisialisasi pointer
Contoh inisialisasi pointer
Operasi Assignment
Antar variabel pointer dapat dilakukan operasi assignment.
Contoh Assigment dan sebuah alamat dapat ditunjuk oleh lebih dari
satu pointer
Contoh Mengisi variabel dengan nilai yang ditunjuk oleh sebuah variabel
pointer
Contoh Mengoperasikan isi variabel dengan menyebut alamatnya dengan
pointer
Lengkapi program di bawah ini supaya isi dari q diganti dengan p namun alamat yang dituju
tetap berbeda dan dengan hasil running seperti dibawah ini !!!
Contoh Mengisi dan mengganti variabel yang ditunjuk oleh pointer
Lengkapi program di bawah ini supaya variabel a dapat terisi nilai 25 dengan merubah isi
dari variabel pointer p dan dengan hasil running seperti dibawah ini !!!
Operasi aritmatika
• Pada pointer dapat dilakukan operasi aritmatika yang akan menunjuk suatu alamat
memori baru.
• Hanya nilai integer saja yang bisa dioperasikan pada variabel pointer.
• Biasanya hanya operasi penambahan/pengurangan saja.
• Misal pointer X bertipe int (2 bytes), maka X+1 akan menunjuk pada alamat memori
sekarang (mis. 1000) ditambah sizeof(X), yaitu 2, jadi 1002.
Permintaan : perhatikan program diatas, Coba ganti line 14 dengan p--, amati hasilnya !
Contoh pointer pada array 1D
Pernyataan p=numbers artinya p menyimpan alamat array numbers, yang alamatnya
diwakili alamat elemen pertama, yaitu numbers[0].
Kita juga dapat menuliskan baris p=numbers diganti dengan p=&a[0]
Tugas di Rumah
1. Buatlah pengembangan dari latihan terakhir (array 1D) untuk merubah isi array numbers
menjadi kelipatan 10 seperti gambar hasil running dibawah ini :
2. Sempurnakan program di bawah ini dengan mengacu contoh hasil running dibawah ini :
Hasil running :
MODUL PRAKTIKUM 5
POINTER LANJUTAN
Pemahaman Letak Deklarasi
• Global
Diletakkan diatas program utama dan diluar Function.
Lokal
Diletakkan didalam program utama atau didalamFunction.
• Parameter
Diletakkan didalam nama function
Pointer dan Array
Contoh Program 1
#include <iostream.h> int my_array[] = {12,23,17,43,-5,10}; //Deklarasi Array int *ptr; //Deklarasi pointer int main(void) { int i; ptr = &my_array[0]; // mengarahkan pointer ke array ke 0 for (i = 0; i < 6; i++) { cout<<" ptr + "<< i<<" = "<< *(ptr+i)<<"\n"; } }
Pointer dan Function
1. Variable pointer dapat didefinisikan (deklarasikan) sebagai lokal maupun global
2. Juga variable pointer dapat didefinisikan (deklarasikan) sebagai parameter didalam sebuah
function
Contoh Implementasi variabl global :
Contoh Implementasi Variable lokal
Contoh Implementasi Parameter
Latihan Program Pointer Struktur
#include <string.h> #include <stdio.h> #include <iostream.h> //Definisi Struktur struct pegawai{ char nip[20]; char nama[20]; int gp; int tunj; int pot; }; struct pegawai my_struct[10]; //Deklarasi struktur struct pegawai *st_ptr[10]; //Deklarasi pointer ke Struktur void show_name(struct tag *p); //Prototype fungsi int main(void) { int i = 1; int jum; st_ptr[0] = &my_struct[0]; //mengarahkan pointer ke my_struct cout<<"Masukkan jumlah pegawai "; cin>>jum; for (i=1; i<=jum; i++) {
cout<<"NIP pegawai "; cin>>(*st_ptr)[i].nip;
cout<< (*st_ptr)[i].nip <<"\n"; } }
Latihan Program Pointer Function #include <stdio.h> void my_int_func(int x) { printf( "%d\n", x ); } int main() { void (*foo)(int); foo = &my_int_func; /* call my_int_func (note that you do not need to write (*foo)(2) ) */ foo( 2 ); /* but if you want to, you may */ (*foo)( 2 ); return 0; }
Latihan Program Pointer dan Array #include <iostream.h> int my_array[] = {12,23,17,43,-5,10}; //Deklarasi Array int *ptr; //Deklarasi pointer int main(void) { int i; ptr = &my_array[0]; // mengarahkan pointer ke array ke 0 for (i = 0; i < 6; i++) { cout<<"my_array [ "<< i<<" ] = "<< my_array[i]; cout<<" ptr + "<< i<<" = "<< *(ptr+i)<<"\n"; } return 0; }
Latihan Program Pointer, Function dan Struktur #include <string.h> #include <iostream.h> //Definisi Struktur struct tag{ char lname[20]; char fname[20]; int age; }; struct tag my_struct; //Deklarasi struktur void show_name(struct tag *p); //Prototype fungsi int main(void) { struct tag *st_ptr; //Deklarasi pointer ke Struktur st_ptr = &my_struct; //mengarahkan pointer ke my_struct strcpy(my_struct.fname,"Agus"); strcpy(my_struct.lname,"Mulyanto"); cout << my_struct.fname<<" "; cout << my_struct.lname; my_struct.age = 63; show_name(st_ptr); //mengirim pointer ke fungsi return 0; } void show_name(struct tag *p) { cout<< p->fname <<" "<< p->lname << " " << p->age <<"\n"; }
Tugas di Rumah
MODUL PRAKTIKUM 6
LINKED LIST
A. Pengantar
Pada bab sebelumnya telah dijelaskan mengenai variabel array yang bersifat statis(ukuran
danurutannya sudah pasti). Selain itu, ruang memori yang dipakai olehnyatidak dapat
dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Untuk
memecahkan masalah di atas, kita dapat menggunakan variable pointer. Tipe data pointer
bersifat dinamis, variabel akan dialokasikan hanya pada Saat dibutuhkan dan sesudah tidak
dibutuhkan dapat direlokasikan kembali.
B. Pengertian
Linkedlist adalah sekumpulan elemen/nilai bertipesama yang mempunyai keterurutan
keanggotaan. Berdasarkan keterurutan keanggotaan tersebut, jika diketahui Sebuah
anggota/elemen list maka dapat diketahui elemen berikutnya.
Deklarasi node dengan struct
struct tnode
{
int data;
struct tnode *next;
}
C. Jenis Linked List
a. Single Linked List
Pembuatan Single Linked List dapat menggunakan 2 metode:
LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
Suatu metode pembuatan Linked List di mana data yang masuk paling akhir adalah
data yang keluar paling awal.
FIFO (First In First Out), aplikasinya : Queue (Antrean)
FIFO adalah suatu metode pembuatan Linked List di mana data yang masuk paling
awal adalah data yang keluar paling awal juga.
Operasi Pada Single Linked List
- Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
. Konstruktor
Fungsi ini membuat sebuah linked list yang baru dan masih kosong.
. IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
. Find First
Fungsi ini mencari elemen pertama dari linked list
. Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now.
. Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu
dikembalikan oleh fungsi.
. Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.
. Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah
elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
. Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen
sesudahnya.
. Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila
Anda ingin mengakhiri program yang menggunakan linked list. Jika anda
melakukannya,data-data uang dialokasikan ke memori pada program sebelumnya
akan tetaptertinggal di dalam memori.
b. Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergeraksatu
arah saja, maju/ mundur, atau kanan/kiri sehingga pencarian data pada singlelinked list hanya
dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahantersebut, anda dapat
menggunakan metode double linked list. Linked list ini dikenaldengan nama Linked list
berpointer Ganda atau Double Linked List.
Langkah-langkah :
Pembuatan simpul baru
Contoh algoritmanya :
struct TNode
{
int data;
TNode *next;
};
Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan
field next yang bertipe pointer dari Tnode. Setelah pembuatan struct, buat variabel head yang
bertipe pointer dari TNode yang berguna sebagai kepala linked list.
TNode *head;
Selanjutnya digunakan keyword new yang berart mempersiapkan sebuah node baru
beserta alokasi memorinya kemuadian node tersebut di isi data dan pointer nextnya
ditunjuk ken NULL.
Contohnya :
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
Dalam pembuatan simpul baru jangan lupa untuk menggunakan fungsi malloc () sebagai
pointer. Fungsi ini dideklarasikan ke dalam header stdlib.h. Dengan demikian, jangan lupa
untuk meng-include header tersebut.
Contoh instruksinya :
P = (simpul*) malloc(sizeof(simpul));
Algoritmanya :
Void Buat_Simpul(int x) {
P = (simpul*) malloc(sizeof(simpul));
If (P != NULL)
{ P - > Info = x; }
Else
Cout<<”Simpul gagal dibuat”;
}
Bila setiap penambahan simpul pada linked list dilakukan pada bagian depan (paling dekat
dengan head) makakompleksitas yang diperlukan untuk menambah node baru dalam linked
list konstan atau O(1).
Untuk menu memasukkan data baru , digunakan bentuk algoritma seperti ini :
void insertDepan(int databaru) {
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1)
{
head=baru;
head->next = NULL;
}
else
{
baru->next = head;
head = baru;
}
cout<<endl;
cout<<” Data masuk…\n”;
getch();
}
Penghapusan Node Linked List
Sebelum proses penghapusan dilakukan, pencarian node yang ingin dihapus harus terlebih
dahulu dilakukan. Bila nodeyang ingin dihapus ditemukan, suatu hal yang selalu harus
diperhatikan adalah bagaimana mengeluarkan node tersebutdari linked list dan kemudian
menyambung kembali linked list kembali. Kompleksitas menghapus sebuah node dalam
linked list adalah O(n). Contoh programnya :
void hapusDepan() {
TNode *hapus;
int d;
if (isEmpty()==0)
{
if(head->next != NULL)
{
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
}
else
{
d = head->data;
head = NULL;
}
cout<<endl;
cout<<” Data ”<<d<<” terhapus…\n”;
}
else
{
cout<<endl;
cout<<endl;
cout<<” Linked List Masih kosong…\n”;
}
getch();
}
Gambar linklist dengan 6 simpul (nodes)
Tugas di Rumah
Contoh program single linklist yang tambah depan dan belakang menggunakan class (tanpa
fungsi malloc):
Buatlah program untuk menyisipkan atau memasukkan nilai di tengah.
MODUL PRAKTIKUM 7
LINKED LIST Lanjutan
Latihan Program 1 #include<stdio.h> #include<stdlib.h> #include<malloc.h> typedef struct simpul { int data; struct simpul *lanjut; }SIMPUL, *SIMPULPTR; void buatsenerai(SIMPULPTR *s) { *s=NULL; } SIMPULPTR simpulbaru(int m) { SIMPULPTR n; n = (SIMPULPTR)malloc(sizeof(SIMPUL)); if(n!=NULL) { n-> data = m; n-> lanjut =NULL; } return n; } void sisipsenerai(SIMPULPTR *s, SIMPULPTR t, SIMPULPTR p) { if (p==NULL) { t->lanjut=*s; *s=t; } else { t->lanjut=p->lanjut; p->lanjut=t; } } void cetaksenerai(SIMPULPTR s) { SIMPULPTR ps; for (ps=s;ps!=NULL;ps=ps->lanjut) printf(" %d --> ",ps->data); printf("KOSONG\n");
} int main() { SIMPULPTR pel; SIMPULPTR n; buatsenerai(&pel); n=simpulbaru(55); sisipsenerai(&pel,n,NULL); n=simpulbaru(75); sisipsenerai(&pel,n,NULL); cetaksenerai(pel); return 0; }
Latihan Program 2 #include <iostream.h> #include <stdio.h> #include <malloc.h> void main() { struct nodeku { int x; struct nodeku *next; }; struct nodeku *head=NULL,*current=NULL,*tmp=NULL; //perulangan membuat node-node int i; for (i=0; i<=3; i++) { tmp= (struct nodeku *) malloc (sizeof(struct nodeku)); tmp -> x = i; if (head == NULL) { head = tmp; current= tmp; } else { current -> next = tmp; current = tmp; } } current-> next = NULL; //perulangan menampilkan node-node current = head; while (current!= NULL)
{ cout<<current -> x<<" -> "; current = current -> next; } cout<<"Null\n"; //perulangan menghapus node-node current = head->next; head->next = NULL; while (current != NULL) { tmp = current->next; free(current); current = tmp; } cout<<"List telah dihapus\n\n"; }
Tugas dirumah : Lakukan analisa terhadap 2 program diatas, kemudian berikan kesimpulan apa saja yang membedakan dari kedua program diatas.
MODUL PRAKTIKUM 8
QUEUE (Antrian) FIFO (First in Frist Out)
1. Definisi Queue
Queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double
linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat Anda
mengantri di loket untuk membeli tiket.Istilah yang cukup sering dipakai seseorang masuk dalam
sebuah antrian adalah enqueue. Dalam suatu antrian, yang datang terlebih dahulu akan dilayani
lebih dahulu.Istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.
Walaupun berbeda implementasi, struktur data queue setidaknya harus memilikioperasi-
operasi sebagai berikut :
EnQueue : Memasukkan data ke dalam antrian
DeQueue : Mengeluarkan data terdepan dari antrian
Clear : Menghapus seluruh antrian
IsEmptY : Memeriksa apakah antrian kosong
IsFull : Memeriksa apakah antrian penuh
2. Implementasi Queue
Implementasi Queue dengan Double Linked List
Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode
linkedlist yang digunakan adalah double linked list, operasi-operasinya:
Konstruktor
Konstruktor berguna untuk menciptakan queue yang baru dan kosong, yaitu
denganmengarahkan pointer head dan tail kepada NULL.
IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah
berisidata. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada
Nullatau tidak. Jika benar berarti queue masih kosong.
IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih
biasmenampung data dengan cara mengecek apakah Jumlah Queue sudah sama
denganMAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (headdan
tail mula-mula meunjukkan ke NULL).
DeQueue
Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal
inidilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).
Contoh Program:
Output :
Contoh program 2
Tugas di rumah Buatlah contoh program Queue yang memiliki fungsi operasi (dibuat fungsi diluar main): 1. Inisialisasi 2. Enqueue 3. Dequeue 4. Tampil
MODUL PRAKTIKUM 9
STACK (Tumpukan)
A. Definisi Stack
Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In
FirstOut), benda yang terakhir masuk dalam stack akan menjadi benda pertama
yangdikeluarkan dari stack.
DiC++, ada dua cara penerapan prinsip stack, yakni dengan array dan linked list.
Setidaknya stack haruslah memiliki operasi-operasi sebagai berikut:
Push : Untuk menambahkan item pada tumpukan paling atas
Pop : Untuk mengambil item teratas
Clear : Untuk mengosongkan stack
IsEmpty : Untuk memeriksa apakah stack kosong
IsFull : Untuk memeriksa apakah stack sudah penuh
Dalam bab ini penjelasan mengenai stack akan menggunakan kelas stack.
Kelimaoperasi stack diatas akan dideklarasikan secara abstrak dalam kelas ini,
sedangkan kelasturunan dari stack akan mengimplementasikan operasi-operasi tersebut.
B. Implementasi Stack
1. Stack dengan Array
Sesuai dengan sifat stack, pengambilan / penghapusan delemen dalam stack
harusdimulai dari elemen teratas.
Operasi-operasi pada Stcak dengan Array
a. Konstruktor
Fungsi ini membuat sebuah stack baru yang masih kosong. Konsepnya adalah
bahwaTop menunjukkan elemen stack teratas. Jika Top bernilai -1, berarti
tumpukan kosong.
b. IsFull
Fungsi ini memeriksa apakah stack yang ada sudah penuh. Stack penuh jika
stackpenuh jika puncak stack terdapat tepat dibawah jumlah maksimum yang
dapatditampung stack atau dengan kata lain Top = MAX_STACK -1.
c. Push
Fungsi ini menambahkan sebuah elemen ke dalam stack dan tidak bias dilakukan
lagijika stack sudah penuh.
d. IsEmpty
Fungsi menentukan apakah stack kosong atau tidak. Tanda bahwa stack kosong
adalahTop bernilai kurang dari nol.
e. Pop
Fungsi ini mengambil elemen teratas dari stack dengan syarat stack tidak boleh
kosong.
f. Clear
Fungsi ini mengosongkan stack dengan cara mengeset Top dengan -1. Jika Top
bernilaikurang dari nol maka stack dianggap kosong.
2. Double Stack dengan Array
Metode ini adalah teknik khusus yang dikembangkan untuk menghemat
pemakaianmemori dalam pembuatan dua stack dengan array. Intinya adalah
penggunaan hanyasebuah array untuk menampung dua stack.Tampak jelas bahwa
sebuah array dapat dibagi untuk dua stack, stack 1 bergerak ke atasdan stack 2
bergerak ke bawah. Jika Top1 (elemen teratas dari Stack 1) bertemu denganTop 2
(elemen teratas dari Stack 2) maka double stack telah penuh.Implementasi double
stack dengan array adalah dengan memanfaatkan operasi-operasiyang tidak berbeda
jauh dengan operasi single stack dengan array.
Operasi-operasi Double Stack Array
Konstruktor
Fungsi ini membuat stack baru yang masih kosong. Top[0] diset dengan -1 dan
Top[1]diset dengan MAX_STACK.
IsFull
Fungsi ini memeriksa apakah double stack sudah penuh. Stack dianggap penuh
jikaTop[0] dan Top[1] bersentuhan sehingga stack tida memiliki ruang kosong.
Dengan katalain,(Top[0] + 1) > Top[1].
Push
Fungsi ini memasukkan sebuah elemen ke salah satu stack.
IsEmpty
Fungsi memeriksa apakah stack pertama atau stack kedua kosong. Stack
pertamadianggap kosong jika puncak stack bernilai kurang dari nol, sedangkan
stack keduadianggap kosongjika puncak stack sama atau melebihiMAX_STACK.
Pop
Fungsi ini mengeluarkan elemen teratas dari salah satu stack
Clear
Fungsi ini mengosongkan salah satu stack.
3. Stack dengan Single Linked List
Selain implementasi stack dengan array seperti telah dijelasnkan sebelumnya,
ada caralain untuk mengimplementasi stack dalam C++, yakni dengan single linked
list.Keunggulannya dibandingkan array tebtu saja adalah penggunaan alokasi memori
yangdinamis sehingga menghindari pemborosan memori. Misalnya saja pada stack
denganarray disediakan tempat untuk stack berisi 150 elemen, sementara ketika
dipakai olehuser stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori
untuk sisa 100elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat
yangdisediakan akan sesuai dengan banyaknya elemen yang mengisi stack. Oleh
karena itupula dalam stack dengan linked list tidak ada istilah full, sebab biasanya
program tidakmenentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah
dibatasi olehpembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas
kapasitas,yakni dibatasi oleh jumlah memori yang tersedia.
Operasi-operasi untuk Stack dengan Linked List
Konstruktor
Fungsi ini membuat stack baru yang kosong. Stack adalah kosong jika Top
tidakmenunjuk apa pun (bernilai NULL).
IsEmpty
Fungsi memeriksa apakah stack yang adamasih kosong.
Push
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan
insertdalamsingle linked list biasa.
Pop
Fungsi ini mengeluarkan elemen teratas dari stack.
Clear
Fungsi ini akan menghapus stack yang ada.
Contoh Program:
Output :
contoh program 2
Tugas!!
Buatlah contoh program stack di atas dalam bentuk fungsi-fungsi pada setiap
operasi stack
MODUL PRAKTIKUM 10
SORTING
3. Definisi Sorting
Pengurutan (Sorting) adalah suatu proses pengurutan data yang sebelumnya disusun secara
acak atau tidak teratur menjadi urut dan teratur menurut suatu aturan tertentu. Sorting dapat
dibedakan menjadi dua jenis yaitu ascending dan descending. Ascending adalah pengurutan
data dari kecil ke besar, sedangkan descending adalah pengurutan data dari besar ke kecil.
4. Metode Pengurutan
Dalam pertemuan praktikum ini akan dibahas tentang 2 metode, yaitu :
1) Bubble Sort
2) Selection Sort
Bubble Sort
Metode buble sort merupakan metode sederhana untuk melakukan pengurutan data. Metode
buble sort bagus gunakan dalam mengurutkan data dengan jumlah yg sedikit.
Cara kerja Pengurutan Buble short:
Pengurutan dengan mnggunakan buble short dilakukan dengan membandingkan elemen pertama
dengan elemen di sampingnya, jika elemen pertama lebih besar daripada elemen ke dua, maka
posisinya di tukar lakukan hal tersebut berulang-ulang sampai di temukan urutan yang tepat.
Misalkan ada data sebagai berikut:
20 12 35 11 17 9 58 23
1 2 3 4 5 6 7 8 <----- indek yg menunjukan posisi elemen
Dimetode bubble sort, proses pengurutan dimulai dengan membandingkan elemen pertama untuk
mendapatkan angka terbesar. Lalu angka tersebut ditempatkan pada elemen terakhir.
Sebagai langkah awal, isi elemen pertama dibandingkan dengan elemen ke-2. Jika isi elemen ke-2
lebih kecil dari elemen pertama, maka isi kedua elemen tersebut ditukar. Sehingga isi
array berubah menjadi :
12 20 35 11 17 9 58 23
1 2 3 4 5 6 7 8 <----- indek yg menunjukan posisi elemen data
elemen 1 dan 2 setelah di tukar
Lalu elemen ke-2 dibandingkan dengan elemen ke-3. jika isi elemen ke-3 lebih besar, maka isi
kedua elemen tersebut tidak ditukar.
12 20 35 11 17 9 58 23
1 2 3 4 5 6 7 8 <----- indek yg menunjukan posisi elemen data elemen 2
dan 3 tidak ditukar
Perbandingan selanjutnya dilakukan terhadap elemen ke-3 dengan ke-4. Karena elemen ke-4
lebih kecil, maka isi kedua elemen tersebut ditukar. Sehingga isi array sebelumnya berubah
menjadi :
12 20 11 35 17 9 58 23
1 2 3 4 5 6 7 8 <----- indek yg menunjukan posisi elemen
data elemen 3 dan 4 setelah ditukar
Proses perbandingan seperti diatas dilakukan secara berulang sampai pada elemen terakhir.
Sehingga pada akhirnya akan dihasilkan bilangan terbesar yang ditempatkan pada posisi elemen
terakhir. Dibawah ini kondisi array setelah perbandingan elemen terakhir
12 20 11 17 9 35 23 58
1 2 3 4 5 6 7 8 <----- indek yg menunjukan posisi elemen
data setelah ditukar
Proses diatas hanya mencari bilangan terbesar pertama. Ulangi proses tersebut untuk mencari
bilangan terbesar lainnya setelah bilangan terbesar pertama tadi. Namun proses perbandingan
hanya dilakukan mulai dari elemen pertama sampai elemen ke-7. Isi elemen pertama
dibandingkan dengan elemen ke-2. Karena isi elemen ke-2 lebih besar, maka isi kedua elemen
tersebut tidak ditukar.
Kemudian elemen ke-2, dibandingkan dengan elemen ke-3. Karena elemen ke-3 lebih kecil, maka
isi kedua elemen tersebut ditukar sehingga isi array menjadi :
12 11 20 17 9 35 23 58
1 2 3 4 5 6 7 8 <----- indek yg menunjukan posisi
elemen Elemen data 2 dan 3 setelah
ditukar
Lanjutkan proses diatas sampai pada elemen ke-7. Hasilnya isi array menjadi
12 11 17 9 20 23 35 58
1 2 3 4 5 6 7 8 <----- indek yg menunjukan posisi
elemen data setelah ditukar
Kini isi elemen ke-7 dan ke-8 sudah urut berdasarkan bilangan kecil ke besar. Namun elemen
lainnya belum terurut. Untuk itu ulangi proses diatas, namun elemen yang dibandingkan hanya
sampai pada elemen ke-6 saja. Setelah itu, proses perbadingan diulangi lagi sampai elemen
terakhir yang dibandingkan yaitu elemen ke-2. Hasil akhirnya menjadi :
9 11 12 17 20 23 35 58
1 2 3 4 5 6 7 8 <----- indek yg menunjukan posisi
elemen data sudah terurut
Adapun Implementasi Flowchart Sebagai berikut :
Contoh Program Bubble Sort:
Selection Sort
metode ini dikatakan kebalikan dari metode Bubble sort. Pencarian dimulai dengan bilangan
terkecil. Bilangan terkecil ini lalu diletakan di elemen atau urutan pertama, demikian
seterusnya sampai dihasilkan urutan bilangan dari kecil ke besar.
Contoh Program Selection Sort
#include <iostream.h> int arrbil[] = {43,23,17,12,5,10}; int main() { int j;int i=0; int n=6; int temp; while ( i <(n-1)) { j= i+1; while(j <n) { if ( arrbil[i] > arrbil[j]) { temp = arrbil[i]; arrbil[i] = arrbil[j]; arrbil[j] = temp; } j= j+1; } i=i+1; } i = 0; while (i<n) { cout<<arrbil[i]<<endl; i= i+1; } }
Tugas di Rumah
Buat program pengurutan data menggunakan metode bubble sort yang nantinya
hanya mengurutkan data bilangan prima saja. Contoh output program sebagai
berikut :
MODUL PRAKTIKUM 11
SORTING Lanjutan
1. Definisi Sorting
Pengurutan (Sorting) adalah suatu proses pengurutan data yang sebelumnya disusun secara
acak atau tidak teratur menjadi urut dan teratur menurut suatu aturan tertentu. Sorting dapat
dibedakan menjadi dua jenis yaitu ascending dan descending. Ascending adalah pengurutan
data dari kecil ke besar, sedangkan descending adalah pengurutan data dari besar ke kecil.
2. Metode Pengurutan
Dalam pertemuan praktikum ini akan dibahas tentang 2 metode, yaitu :
3) Exchange Sort
4) Insertion Sort
Exchange Sort
Metode pengurutan excahange sort mirip dengan metode pengurutan Buble Sort . Tapi dalam
cara membandingan antar elemennya memiliki tentu memiliki perbedaan.
Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array
tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi
elemen pusat (pivot). Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir
dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot)
untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya
Contoh Program Exchange Sort:
Insertion Sort
Pengurutan dengan penyisipan (insertion sort) adalah suatu metode yang melakukan pengurutan
dengan cara menyisipkan data yang belum urut ke dalam bagian data yang telah diurutkan.
Konsep ini biasa dilakukan pada permainan kartu. Mirip dengan cara orang mengurutkan kartu,
selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.
Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih
kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyisipan elemen, maka
elemen-elemen lain akan bergeser ke belakang
Contoh Program Insertion Sort
Tugas di Rumah
Buat program pengurutan data menggunakan metode Exchange sort yang
nantinya hanya mengurutkan data bilangan prima saja. Contoh output program
sebagai berikut :
MODUL PRAKTIKUM 12
SEARCHING
Searching Data
Didalam modul ini kita akan membahas proses pencarian / searching data pada suatu array /
barisan data. Sebagai contoh sederhana :
Apabila diketahui ada sebuah array / barisan data bernama A yang menampung 10 data yang
bertipe integer sbb A={1,2,3,4,8,5,7,9,6,0} dan kita diberi tugas untuk mencari beberapa data
misal:
Jika data yang akan dicari dalam array A adalah 6, maka dengan cepat dapat kita
ketahui bahwa data 6 ada dalam array A pada index ke-9 (index pada array dimulai
dari 0).
Sedangkan jika data yang akan dicari dalam array A adalah 12, maka dapat
disimpulkan bahwa array A tidak memiliki data 12 tersebut.
Bisa diambil kesimpulan, kita sudah memahami proses pencarian data yang sederhana
tersebut dalam pikiran kita, sekarang permasalahannya adalah bagaimana
mengimplementasikannya kedalam program
Pada umumnya dikenal dua metode searching antara lain : Sequensial search dan binary
search, Untuk lebih memahami kedua metode ini lebih baik kita mulai dari metode yang
paling sederhana terlebih dahulu yaitu sequensial search.
Sequensial search
Metodenya seperti ini..
1. User diminta menentukan banyaknya data yang akan diinputkan
2. User menginputkan data sebanyak yang telah ditentukan pada langkah pertama
3. User diminta memasukkan data yang dicari
4. Program melakukan perulangan, mencari data yang dicari
5. Pada akhir perulangan ada 2 kondisi
5.1 Data yang tidak dicari tidak ditemukan
5.2 Data yang dicari ditemukan, kemudian tampilkan posisinya
Secara garis besarnya seperti itulah Algortima yang digunakan pada metode Sequential
Search. Dapat disimpulkan bahwa sequential search, akan mencari data dengan cara
membandingkannya satu-persatu dengan data yang ada. Prosesnya tentu saja akan
singkat jika data yang diolah sedikit, dan akan lama jika data yang diolah banyak.
Disarankan proses ini digunakan pada jumlah data yang sedikit saja.
Contoh Program Sequensial search
Binary search
Algoritma yang digunakan pada metode Binary seperti dibawah ini :
1. User diminta menentukan banyaknya data yang akan diinputkan
2. User menginputkan data sebanyak yang telah ditentukan pada langkah pertama
3. User diminta memasukkan data yang dicari
4. Mengurutkan data jika data belum terurut
5. User diminta memasukkan data yang dicari
6. Menentukan nilai tengah array
7. Pengecekan apakah nilai array pada index tengah sama dengan data yang dicari
8. Jika “sama”, data yang dicari ditemukan
8.1 jika “tidak”, periksa apakah data yang dicari lebih kecil dari nilai tengah
8.1.1 jika “true” lakukan pencarian dari i=0 sampai i=nilai tengah
8.2 jika 8.1 bernilai “false” berarti data yang dicari lebih besar dari nilai tengah
8.2.1 lakukan pencarian mulai dari i=nilaitengah+1 sampai data terakhir
9. Tampilkan hasil pencarian
Secara garis besarnya seperti itulah Algortima yang digunakan pada metode Binary Search.
Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah
diurutkan terlebih dahulu. Jika terdapat N buah data yang akan dolah, data yang dicari akan
dibandingkan dengan data ke-N jika data ke-N lebih besar dari data yang dicari maka akan
dilakukan pembagian data menjadi dua bagian. Kemudian ujung data pada setiap bagian
dibandingkan lagi dengan nilai yang akan dicari.
Bedanya metode Sequential dan Binary adalah keadaan datanya. Jika Sequential data tidak
terurut pun bisa, namun jika menggunakan Binary data harus dalam keadaan urut.
Contoh Program Binary search
Tugas di Rumah
Rancanglah program menggunakan metode sequensial untuk mencari huruf x dari sederatan
array berikut “B C x E X A a H X x B”
Berikan ulasan anda atas hasil program tersebut.
MODUL PRAKTIKUM 13
Review Materi 1
Dalam pertemuan ini, setiap mahasiswa mampu menyelesaikan masalah dengan memadukan
beberapa materi secara komprehensif, yaitu :
1. Pendefinisian tipe data
2. Penggunaan operator
3. Perulangan data dengan array
4. Penggunaan fungsi logika dan perulangan
5. Penyimpanan data kedalam suatu file
Catatan :
Rancanglah suatu program dengan studi kasus yang anda tentukan sendiri. Materi atau studi kasus
boleh anda unduh dari internet tetapi dengan catatan anda tetap harus mampu
mempertanggjawabkan bahwa anda sangat memahami alur pikiran atau logika dari masalah yang
anda unduh tersebut.
Studi kasus yang anda selesaikan harus memiliki kandungan materi diatas ( 5 materi)
Baris program yang anda susun minimal sebanyak 2 halaman folio spasi 1 font size 12.
MODUL PRAKTIKUM 14
Review Materi 2
Dalam pertemuan ini, setiap mahasiswa mampu menyelesaikan masalah dengan memadukan
beberapa materi secara komprehensif, yaitu :
1. Penyusunan baris program dalam suatu function
2. Paket function dalam suatu file header
3. Penyimpanan data kedalam suatu file
Catatan :
Rancanglah suatu program dengan studi kasus yang anda tentukan sendiri. Materi atau studi kasus
boleh anda unduh dari internet tetapi dengan catatan anda tetap harus mampu
mempertanggjawabkan bahwa anda sangat memahami alur pikiran atau logika dari masalah yang
anda unduh tersebut.
Seluruh function yang anda definisikan, harus dikemas kedalam beberapa file header.
Studi kasus yang anda selesaikan harus memiliki kandungan materi diatas ( 3 materi)
Baris program yang anda susun minimal sebanyak 2 halaman folio spasi 1 font size 12.