Materi

1. Variabel

2. Larik(Array)

3. Stack

4. Queue

5. Sorting (Selection Sort danInsertion Sort )

6. Searching (Sequential Search danBinarry Search)

Queue (Antrean)

Pengertian Queue (Antrean)

Secara harfiah Queue dapat diartikan sebagi antrean. Queue sering kita temui dalam kehidupan sehari hari sebagai sebuah antrian di loket. Dalam sebuah antrean yang datang lebih dahulu maka dia akan dilayani terlebih dahulu.

Queue merupakan kumpulan data dengan penambahan data hanya melalui satu sisi, yaitu belakang (tail) dan penghapusan data hanya melalui sisi depan (head). Berbeda dengan stack yang bersifat LIFO maka queue bersifat FIFO(First In First Out), yaitu data yang pertama masuk akan keluar terlebih dahulu dan data yang terakhir masuk akan keluar terakhir.

Struktur data queue memiliki operasi-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

Operasi-Operasi Queue dengan Linear Array

 

EnQueue

 

Fungsi EnQueue berfungsi untuk memasukkan elemen  ke dalam queue.

 

DeQueue

 

Berfungsi untuk mengambil sebuah elemen dari queue.

 

Clear

 

Berfungsi untuk menghapus semua lemen dalam queue dengan jalan mengeluarkan semua elemen tersebut satu per satu hingga queue kosong dengan menggunakan fungsi DEQueue.

 

IsEmpty

 

Berfungsi untuk mengecek apakah queue sudah kosong atau masih berisi data.

 

IsFull

 

Berfungsi untuk mengecek apakah queue sudah penuh atau masih bias menampung data.

Contoh Program Queue:

 

#include <iostream.h>
#include <conio.h>

main()
{
    int cek=0, data[20], x, hapus;
    char pil;
    do
    {
      clrscr();
      cout<<"1. Tambah Antrian"<<endl;
      cout<<"2. Hapus Antrian"<<endl;
      cout<<"3. Lihat Antrian"<<endl;
      cout<<"4. Keluar"<<endl;
      cout<<endl;
      cout<<"masukkan pilihan anda = ";
      pil=getche();
      cout<<endl;

        if(pil!='1' && pil !='2' && pil !='3' && pil!='4' )
          cout<<"salah mengetikkan inputan";
        else
        {
           if(pil=='1')   //PUSH
           {
               if(cek==20)
                  cout<<"Antrian Penuh";
              else
              {
                  cout<<"Masukkan nilai = ";
                  cin>>x;
                  data[cek]=x;
                  cek++;
              }
           }
           else
           {
               if(pil=='2')     //POP
               {
                  if(cek==0)
                     cout<<"Antrian kosong";

                  else
                  {
                     hapus=data[0];
                     for(int v=0;v<cek;v++)
                        data[v]=data[v+1];
                        data[cek-1]=NULL;
                        cek--;
                        cout<<"Data dengan nilai "<<hapus<<" terhapus";
                   }
                   getch();
                }
                else
                {
                    if(pil=='3')   //CEK DATA
                    {
                        if(cek==0)
                            cout<<"Antrian Kosong";

                     else
                     {
                         cout<<endl;
                         for(int z=0;z<cek;z++)
                             cout<<" "<<data[z];
                      }

                   }
                   getch();
                }
            }
        }
    }

while(pil!='4');
}

 

Hasil eksekusi program:

 

 

 

Stack (Tumpukan)

Pengantar Stack (Tumpukan)
 

Contoh nyata dari penggunaan stack bisa kita lihat di kehidupan sehari-hari misalnya di parkiran mobil di gang sempit.Seseorang yang datang duluan ke parkiran akan parkir paling pojok, jika ada lima mobil di parkiran maka mobil yang terakhir parkir akan keluar duluan dan mobil yang datang pertama kali akan keluar terakhir.

Sama halnya dengan data pada konsep stack di algoritma dan pemrograman. Stack (tumpukan) inilah yang menerapkan konsep yang kita kenal dengan LIFO (Last-In-First-Out) atau FCLS (First-Come-Last-Serve), artinya elemen struktur yang dimasukkan ke dalam rangkaian terakhir kali maka akan muncul pertama kali apabila ditampilkan/dikeluarkan.

Pada konsep Last-In-First-Out, yang terakhir masuk yang pertama kali keluar. Jika ada sebanyak NOEL elemen pada sebuah stack, maka elemen ke-NOEL merupakan elemen TOP.

Berikut ini adalah operator-operator atau nama method yang biasa digunakan dalam pemrograman algoritma stack.

- PUSH: penyisipan (Memasukkan elemen).

- POP: penghapusan (Mengeluarkan elemen puncak).

- IsEmpty: operator yang memeriksa apakah stack kosong.

- IsFull: operator yang memeriksa apakah stack penuh.

- Clear: operator untuk menghapus stack.

 

Agar lebih jelas mari kita lihat gambar:

 

Berikut merupakan program stack:

#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);
}

Hasil eksekusi program:

Searching (Sequential Search dan Binarry Search)

Pengantar Pencarian Data

Pencarian (searching) merupakan tindakan untuk mendapatkan suatu data dalam kumpulan data. Dalam kehidupan sehari hari, seringkali kita berurusan dengan pencarian; misalnya untuk menemukan nomor telepon seseorang pada buku telepon atau mencari suatu istilah dalam kamus. Pada aplikasi komputer, pencarian kerap dilakukan; misalnya untuk mendapatkan data dari seorang mahasiswa, mendapatkan nomor telepon berdasarkan suatu alamat atau nama perusahaan.

Untuk keperluan mencari data, terdapat beberapa algoritma pencarian. Yang dimadsud dengan algoritma pencarian adalah "algoritma yang menerima sebuah argumen a dan mencoba untuk menemukan sebuah rekaman yang memiliki kunci a". Sebagai contoh, dikehendaki untuk mendapatkan mahasiswa dengan nomor 140010289. Hasilnya adalah rekaman yang berisi data mahasiswa tersebut; yang barang kali berisi nama, alamat, tanggal lahir, dan nama program studi. Dalam implementasi, algoritma bisa jadi memberikan nilai balik berupa sebuah rekaman yang diperoleh, tetapi bisa hanya memberikan pointer yang menunuk ke sebuah rekaman.

Pencarian dapat dilakukan terhadap data yang secara keselurahan berada dalam memori komputer ataupun terhadap data yang berada dalam penyimpanan eksternal (harddisk). Pencarian yang dilakukan terhadap data yang berada dalam memori komputer dikenal dengan sebutan pencarian internal, sedangkan pencarian yang dilakukan pada media penyimpanan eksternal disebut pencarian eksternal. Pencarian internalah yang akan kita bahas.

Sequential Search (Pencarian Sekuensial)

Pencarian sekuensial (atau disebut juga pencarian linear) merupakan model pencarian yang paling sederhana yang dilakukan terhadap suatu kumpulan data.

Secara konsep, penjelasannya adalah seperti berikut: terdapat L yang merupakan larik yang berisi n buah data (L[0],L[1],...,L[n-1]) dan k adalah data yang hendak dicari. Pencarian dilakukan untuk menemukan

L[i] = k

dengan i adalah bilangan indeks terkecil  yang memenuhi kondisi 0<=k<=n-1. Tentu saja ada kemungkinan bahwa data yang dicari tidak ditentukan. Contoh:

L <- [10,9,4,6,4,3,2,5]

Dimanakah posisi 4 yang pertama? Dalam hal ini k adalah 4 dan k ditemukan pada posisi dengan indeks berupa 2.

Contoh :

1.Implementasi pencarian sekuensial yang digambarkan di atas dalam bentuk algoritma dan program

Algoritma:

Subrutin berikut merupakan implementasi algoritma pencarian secara sekuensial. Dalam hal ini subrutin menghasilkan nilai balik berupa:

• -1 jika data yang dicari tidak ditemukan, dan
• bilangan antara 0 sampai dengan n-1 (dengan n adalah jumlah elemen larik) jika data yang dicari ditemukan.

SUBRUTIN cari(L,n,k)

       JIKA n<= 0 MAKA

              posisi <- -1

       SEBALIKNYA

              ketemu <- SALAH

              i <- 0

              ULANG SELAMA (i<n-1) DAN (TIDAK ketemu)

                   JIKA k = L[i] MAKA

                         posisi <- i

                         ketemu <- BENAR

                   SEBALIKNYA

                         i <- i+1

                   AKHIR-JIKA

             AKHIR-ULANG

             JIKA TIDAK ketemu  MAKA

                   posisi <- -1

             AKHIR-JIKA

      AKHIR-JIKA

    

      NILAI-BALIK posisi

AKHIR-SUBRUTIN

Program:

#include <iostream.h>

#include <conio.h>

int cari(int data[], int n, int k)

{

   int posisi, i, ketemu;

   if (n <= 0)

      posisi = -1;

   else

   {

      ketemu = 0;

      i = 1;

      while ((i < n-1) && ! ketemu)

         if (data[i] == k)

         {

            posisi = i;

            ketemu = 1;

         }

         else

            i++;

      if (!ketemu)

         posisi = -1;

   }

   return posisi;

}

int main()

{

   int data[8] = { 6, 7, 8, 5, 7, 8, 1, 9};

   int dicari = 5;

   cout << "Posisi " << dicari << " dalam larik data: "

        << cari(data, 8, dicari) << "\n";

   getch ();

   return 0;

}

Hasil eksekusi program:

2. Tulislah algoritma untuk menghitung jumlah suatu bilangan dalam larik L yang berisi n buah elemen.

Algoritma:

SUBRUTIN hitung(L,n,k)

       jumlah <- 0

       UNTUK i <- 0 S/D n-1

           JIKA k = L[i] MAKA

                 jumlah <- jumlah+1

           AKHIR-JIKA

      AKHIR-UNTUK

   NILAI-BALIK jumlah

AKHIR-SUBRUTIN

Program:

#include <iostream.h>

#include <conio.h>

int hitung(int data[], int n, int k)

{

   int jumlah, i, ketemu;

   jumlah = 0;

   for (i = 1; i < n; i++)

      if (data[i] == k)

         jumlah++;

   return jumlah;

}

int main()

{

   int data[8] = { 6, 7, 8, 5, 7, 8, 1, 9};

   int dicari = 8;

   cout << "Banyak bilangan " << dicari

        << " dalam larik data: "

        << hitung(data, 8, dicari) << "\n";

   getch ();

   return 0;

}

Hasil eksekusi program:

Binary Search (Pencarian Terhadap Data Urut)

Apabila kumpulan data sudah terurut , pencarian data dengan menggunakan pencarian sekuensial akan memakan waktu yang lama jika jumlah data dalam kumpulan data tersebut sangat banyak. Untuk mengatasi hal itu terdapat algoritma yang dirancang agar pencarian data dapat dilakukan secara efisien. Metode yang digunakan dikenal dengan nama pencarian biner (binary search). Pencarian biner hanya bisa dilakukan jika data sudah terurut.

Pencarian biner dilakukan dengan membagi larik menjadi dua bagian dengan jumlah yang sama atau berbeda 1 jika jumlah data semula ganjil. Data yang dicari kemudian dibandingkan dengan data terakhir pada bagian pertama. Dalam hal ini ada tiga kemungkinan yang terjadi:

• data yang dicari sama dengan elemen terakhir pada bagian petama dalam larik. Jika kondisi ini terpenuhi , data yang dicari berarti ditemukan.
• data yang dicari bernilai kurang dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian pertama.
• data yang dicari bernilai lebih dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian kedua.

Contoh program:

#include <iostream.h>

#include <conio.h>

int caribin(int data[], int n, int k)

{

   int ada, atas, bawah, tengah, posisi;

   ada = 0;

   bawah = 0;

   atas = n-1;

   while (atas >= bawah)

   {

      tengah = (atas + bawah) / 2;

      if (k > data[tengah])

         bawah = tengah + 1;

      else

         if (k < data[tengah])

            atas = tengah - 1;

         else

         {

            ada = 1;           /* Ketemu   */

            posisi = tengah;

            bawah = atas + 1;  /* Mengakhiri pengulangan */

         }

   }

   if (!ada)

      posisi = -1;

   return posisi;

}

int main()

{

   int data[] = { 1, 2, 4, 4, 5, 7, 8, 10, 13, 14, 15};

   int dicari = 13;

   cout << "Posisi " << dicari << " dalam larik data: "

        << caribin(data, 11, dicari) << "\n";

   getch ();

   return 0;

}

Hasil eksekusi program:

Data yang belum terurut harus diurutkan terlebih dahulu dengan menggunakan tehnik sorting.