Materi Praktikum Struktur Data (UAS)

Salam Mahasiswa,
Perkenalkan
Nama      :  Dwi Prastio
Sekolah   : STMIK STIKOM BALI
Kelas      : CA141
Nim        : 140010137

Kali ini saya akan memberikan beberapa ilmu mengenai materi untuk matakuliah Praktikum Struktur Data. Beberapa materi yang akan di bahas diantaranya :
- Variable
- Array 1 dimensi dan 2 dimensi
- Stack
- Queue
- Sorting (Selection Sort dan Insertion Sort)
- Searching (Sequential Sort dan Binary Search)

1. VARIABLE

Variabel adalah sebuah identifier yang nilainya dapat diubah sesuai dengan kebutuhan program. Jika dibutuhkan sebuah variabel yang dapat dikenali oleh semua lingkungan dalam program, maka harus digunakan variabel Global.

Pada C++ selalu terdapat fungsi utama, variabel global biasanya dideklarasikan di luar fungsi utama tersebut. Juga terdapat variabel Lokal. Variabel lokal hanya dikenali oleh suatu fungsi saja, artinya variabel lokal tidak dikenal oleh lingkungan luar di dalam program yang dibuat.Variabel lokal harus berada dalam lingkup fungsi tertentu

Pada saat mendeklarasikan sebuah variabel, secara otomatis harus mendeklarasikan tipe data yang dapat ditampung oleh varibel tersebut.

Di dalam bahasa pemrograman terdapat beberapa tipe data dasar yang telah didefenisikan dan digolongkan :

• tipe bilangan bulat (integer)
• bilangan real(floating point),
•   tipe logika(boolean) dan
•  tipe karakter/teks(character/string)

      2. ARRAY 

Array merupakan kumpulan elemen yang bertipe sama dalam urutan tertentu yang menggunakan nama yang sama. Letak atau posisi dari elemen array ditunjukan oleh index atau posisi.

       Array dapat berupa 1 dimensi, 2 dimensi, dan bahkan n-dimensi. Suatu array dikatakan sebagai 1 dimensi, 2 dimensi, atau n-dimensi berdasarkan banyaknya penunjuk indeks/posisi.

       Deklarasi Array dapat dilihat pada gambar berikut :

      

       Inisialisasi Array

       Nilai suatu variabel array dapat juga diinisialisasikan secara langsung pada saat deklarasi   

       Misalnya:

                int nil [5] = {1, 3, 6, 12, 24};

       Maka di penyimpanan ke dalam array dapat digambarkan sebagai berikut :

       

      Untuk mengakses nilai array, dapat menggunakan sintak seperti berikut :

nama_array [index];

      Pada contoh diatas, variabel nil memiliki 5 buah elemen yang masing -  masing berisi data.

      Misal untuk memberi nilai 75 pada elemen ke 3 maka pernyataannya adalah :

      Nil [2] = 75;

      Contoh  penggunaan array 1 dimensi :

   #include<iostream.h>

   #include<conio.h>

   void main()

      int ujian [5]={90, 95,78, 80, 85};

   for(int i=0;i<5;i++)

   {

     cout<<"Nilai dari ujian index ke "<<i <<" = "<<ujian [i]<<endl;

   }

   getch();

   Hasil dari script tersebut seperti gambar berikut :

         

s   Array 2 dimensi 

     Array dua dimensi sering sekali digambarkan/dianalogikan sebagai sebuah matriks. Dimana

      indeks pertama menunjukkan baris dan indeks kedua menunjukan kolom.

      Array dua dimensi terdiri dari beberapa baris dan beberapa kolom elemen yang bertipe sama.

      Array dua dimensi terdapat dua jumlah elemen yang terdapat didalam kurung siku dan 

      keduanya boleh tidak sama. 

      Contoh array 2 dimensi

  #include<iostream.h>

  #include<conio.h>

  void main()

{

  int matrix[3][4]={{5,10,1,11},{4,7,67,-9},{9,0,45,3}};

   for(int i=0;i<3;i++)

   {

     for(int j=0;j<4;j++)

      {

           cout<<matrix[i][j]<<"  ";

      }

      cout<<endl;

   }

   getch();

       hasil dari script tersebut dapat dilihat pada gambar di bawah 

     

      

     3. STACK

     

Stack berarti tumpukan. Jika dikaitkan dengan struktur data, Stack berarti sekumpulan data yang organisasi atau terstruktur dengan sifat operasi penambahan ( Push ) dan pengambilan ( Pop) elemen melalui satu tempat ( Top Of Stack) .

Pengertian Stack atau Tumpukan adalah suatu struktur data yang penting dalam pemrograman yang mempunyai sifat LIFO (Last In First Out), Benda yang terakhir masuk ke dalam stack akan menjadi pertama yang di keluarkan dari stack. Stack (Tumpukan) adalah list linier yang dikenali elemen puncaknya (TOP) dan aturan penyisipan dan penghapusan elemennya tertentu. Penyisipan selalu dilakukan paling atas (TOP) dan penghapusan juga selalu dilakukan pada TOP

“Top “ merupakan pintu untuk keluar masuknya elemen – elemen stack. A, B, dan C merupakan suatu koleksi. Dari ilustrasi dapat digambarkan bahwa C merupakan elemen yang terakhir memasuki stack namun pertama keluar dari stack. Begitu sebaliknya dengan A. A merupakan elemen pertama yang memasuki tumpukan namun terakhir saat keluar dari tumpukan.

Di dalam pengembangannya, stack dapat dikelompokkan menjadi dua bagian. Dua bagian tersebut yaitu Single Stack dan Double Stack.

Stack karena aturan penyisipan dan penghapusan semacam itu, TOP adalah satu-satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus. Dikatakan bahwa elemen stack akan tersusun secara LIFO (Last In First Out). 

OPERASI-OPERASI/FUNGSI STACK

Push : digunakan untuk menambah item pada stack pada tumpukan paling atas

Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas

Clear : digunakan untuk mengosongkan stack

IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong

IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

ilustrasi stack

a.      Single Stack

Single Stack atau Stack Tunggal adalah stack yang hanya terdiri dari satu koleksi. Bila stack ini direpresentasikan dengan array, maka pengisian dan penghapusan harus dilakukan bertahap dari indeks TOP-nya.

Di dalam proses single stack terdapat tiga macam proses utama, yaitu :

- Inisialisasi

- PUSH (Insert, Masuk, Simpan, Tulis)

- POP (Delete, Keluar, Ambil, Baca, Hapus)

Contoh programnya ada di bawah.

#include <iostream.h>

#include <conio.h>

#define max 10

struct Tumpukan{

 int atas;

   int data[max];

   }T;

void awal(){

 T.atas=-1;

   }

int kosong(){

 if(T.atas==-1)

    return 1;

   else

    return 0;

      }

int penuh(){

 if(T.atas==max-1)

    return 1;

   else

    return 0;

      }

void input(int data){

 if(kosong()==1)

    {T.atas++;

       T.data[T.atas]=data;

       cout<<"Data "<<T.data[T.atas]<<" masuk ke stack";}

   else if(penuh()==0)

    {T.atas++;

       T.data[T.atas]=data;

       cout<<"Data "<<T.data[T.atas]<<" masuk ke stack";}

   else

       cout<<"Tumpukan penuh";

   }

void hapus(){

   if(kosong()==0){

      cout<<"Data teratas sudah terambil";

   T.atas--;

   }

   else

   cout<<"Data kosong";

   }

void tampil(){

 if(kosong()==0)

   {for(int i=T.atas;i>=0;i--)

    {cout<<"\nTumpukan ke "<<i<<"="<<T.data[i];}

      }

   else

   cout<<"Tumpukan kosong";

   }

void bersih(){

 T.atas=-1;

cout<<"Tumpukan kosong!";

}

void main(){

int pil,data;

awal();

do

{

clrscr();

cout<<"1. Input\n2. Hapus\n3. Tampil\n4. Bersihkan\n5. Keluar\nMasukkan pilihan :";

cin>>pil;

switch(pil)

 {case 1:cout<<"Masukkan data = ";cin>>data;

       input(data);

           break;

    case 2:hapus();

        break;

    case 3:tampil();

        break;

    case 4:bersih();

        break;

    case 5: cout<<"Terimakasih, tekan enter untuk keluar";

    }

getch();     }

while(pil!=5);}

screenshoot program sebagai berikut :

4. QUEUE / ANTRIAN

Antrian dapat diartikan sebagai suatu kumpulan data yang seolah - olah terlihat seperti ada data yang diletakkan di sebelah data yang lain

Bersifat FIFO (First In First Out)

Elemen yang pertama masuk ke antrian akan keluar pertama kalinya 

Contoh :

1. Penjualan karcis kereta, bioskop

2. Penjadualan Pencetakan

3. Penjadualan pemakaian CPU

4. Penyimpanan barang di Apotek

Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya. Sehingga membutuhkan 2 variabel : Head dan Tail

Operasi - operasi queue :

Create ()

Untuk menciptakan dan menginisialisasi Queue

Dengan cara membuat Head dan Tail = -1 

IsEmpty()

Untuk memeriksa apakah antrian kosong atau tidak dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty

Kita tidak memeriksa Head, karena 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

 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 antrian tidak lagi terbaca

Tampil ()

Untuk menampilkan nilai-nilai elemen antrian 

Menggunakan looping dari head s/d tail

5. SORTING

Pengurutan data (sorting) didefinisikan sebagai suatu proses untuk menyusun
kembali humpunan obyek menggunakan aturan tertentu. Menurut Microsoft Book-shelf,definisi Algoritma Pengurutan adalah algoritma untuk meletakkan kumpulan elemen data ke dalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.

 Ada dua macam urutan yang biasa digunakan dalam proses pengurutan yaitu :

• urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar
• urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil.

      Algoritma untuk melakukan Sorting

1.    Selection Sort

2.    Insertion Sort

3.    BubbleSort

4.    Quick Sort

1.     Metode Seleksi (Selection Sort)

Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil
kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering
dinamakan pivot.

Proses pengurutan dengan metode seleksi dapat dijelaskan sebagai berikut :

Ø  Langkah pertama : dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. 

Ø  Langkah kedua : data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan.

Algoritma seleksi dapat dituliskan sebagai berikut :
1 i ← 0
2 selama (i < N-1) kerjakan baris 3 sampai dengan 9
3 k ← i
4 j ← i + 1
5 Selama (j < N) kerjakan baris 6 dan 7
6 Jika (Data[k] > Data[j]) maka k ← j
7 j ← j + 1
8 Tukar Data[i] dengan Data[k]
9 i ← i + 1

Untuk lebih memperjelas langkah-langkah algoritma seleksi dapat dilihat pada

tabel di bawah. Proses pengurutan pada tabel 6.2 dapat dijelaskan sebagai berikut:

·         Pada saat i=0, data terkecil antara data ke-1 s/d ke-9 adalah data ke-4, yaitu 3, maka data ke-0 yaitu 12 ditukar dengan data ke-4 yaitu 3.

·         Pada saat i=1, data terkecil antara data ke-2 s/d ke-9 adalah data ke-2, yaitu 9, maka data ke-1 yaitu 35 ditukar dengan data ke-2 yaitu 9.

·         Pada saat i=2, data terkecil antara data ke-3 s/d ke-9 adalah data ke-3, yaitu 11, maka data ke-2 yaitu 35 ditukar dengan data ke-3 yaitu 11.

·         Pada saat i=3, data terkecil antara data ke-4 s/d ke-9 adalah data ke-4, yaitu 12, maka data ke-3 yaitu 35 ditukar dengan data ke-4 yaitu 12.

Dan seterusnya

2.   Insertion Sort

Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan ke tempat yang seharusnya

Pengurutan dimulai dari data ke 2 sampai dengan data terakhir , jika ditemukan data yang lebih kecil, maka akan di tempatkan (diinsert) di posisiyang seharusnya.

Pada penyisipan elemen maka elemen – elemen lain akan bergeser ke belakang

Algoritma sorting ini umumnya digunakan apabila jumlah elemennya sedikit (n kecil). Masalah yang akan muncul dengan metoda ini adalah bagaimana cara menyisipkan A[K] ke dalam letak yang seharusnya pada subarray terurut A[1], A[2], ....., A[K-1]. Hal ini dapat dilakukan dengan membandingkan A[K] dengan A[K-1], kemudian A[K] dengan A[K-2], A[K] dengan A[K-3] dan seterusnya, sampai menemukan elemen A[J] dimana A[J] A[K].

Algoritma ini menggunakan sentinel elemen (A[0]) yang digunakan sebagai perbandingan. Yang dimaksud dengan sentinel elemen adalah elemen yang memiliki nilai yang sangat kecil.

Penggambaran proses Insertion Sort :

Proses	A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]
K = 1:	-	77	33	44	11	88	22	66	55
K = 2:	-	77	33	44	11	88	22	66	55
K = 3:	-	33	77	44	11	88	22	66	55
K = 4:	-	33	44	77	11	88	22	66	55
K = 5:	-	11	33	44	77	88	22	66	55
K = 6:	-	11	33	44	77	88	22	66	55
K = 7:	-	11	22	33	44	77	88	66	55
K = 8:	-	11	22	33	44	66	77	88	55
Urutan :	-	11	22	33	44	55	66	77	88

6. SEARCHING 

Searching adalah metode pencarian informasi dalam suatu aplikasi, dengan suatu kunci (key). Pencarian diperlukan untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui. Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut table. Pada metode searching (pencarian) ada 2 teknik yang digunakan yaitu : Pencarian sekuensial (sequential search) dan Pencarian biner (Binary search).

1.    Pencarian Sekuensial (sequential search)

Pencarian sekuensial (sequential search) atau sering disebut pencarian linier menggunakan prinsip sebagai berikut : data yang ada di bandingkan satu persatu secara berurutan dengan yang dicari.

Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap perulangan, di bandingkan data ke-i dengan yang dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan, tidak ada yang sama berarti data tidak ada.

Kelebihan serta Kekurangan Pencarian Sekuensial yaitu :

a.    Kelebihannya :

Ø  Relatif lebih cepat dan efisien untuk data yang terbatas

Ø  Algoritma sederhana.

b.    Kekuranganya :

Ø  Kurang cepat untuk data dalam jumlah besar

Ø  Beban komputasi cenderung lebih besar 

2.    Pencarian Biner (Binary Search)

Salah satu syarat pencarian biner (binary search) dapat dilakukan adalah data sudah dalam keadaan terurut. Dengan kata lain, apabila data belum dalam keadaan terurut , pencarian biner tidak dapat dilakukan . Dalam kehidupan sehari-hari, sebenarnya kita juga serig menggunakan pencarian biner. Misalnya saat kita ingin mencari suatu kata dalam kamus.

Langkah dalam pencarian biner adalah :

1.    Mula-mula diambil dari posisi awal=1 dan posisi akhir = n

2.    Kemudian kita cari posisi data tengah dengan rumus posisi tengah = (posisi awal + posisi akhir ) dibagi 2

3.    Kemudian data yang di cari dibandingkan dengan data tengah

a.    Jika sama, data ditemukan, Proses selesai

b.    Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1,

c.    Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.

4.    Ulangi langkah kedua hingga data ditemukan, atau tidak ditemukan.

5.    Pencarian biner ini akan berakhir jika data ditemukan posisi awal lebih besar dari pada posisi akhir. Jika posisi awal sudah lebih besar dari posisi akhir berarti data tidak diketemukan.

DAFTAR PUSTAKA :

http://elearning.stikom-bali.ac.id/mahasiswa/kelas-detail.aspx?mk=SK0207&kls=CA141

Catatan harian matakuliah Struktur Data

http://www.slideshare.net/wawanext01/materi-tipe-data-dan-variabel

http://www.academia.edu/7491124/Pengertian_Array_dan_Contoh_Program_Array_1_dan_2_Dimensi

Read More