Searching (sequential search dan binarry search)

Searching

                Searching adalah pencarian data dengan cara menelusuri data-data tersebut. Tempat pencarian data dapat berupa array dalam memori(pencarian internal), bisa juga pada file pada external storage(pencarian external).
                Ada dua macam teknik pencarian yaitu pencarian sekuensial dan pencarian biner. Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut (contoh: sequential search). Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut (contoh: Binary serach dan interpolation search). Pada Kesempatan ini kita hanya akan membahas tentang pencarian internal menggunakan Array dinamis (pointer).

Metode pencarian dibagi menjadi 2, yaitu: 

1.       Metode Pencarian Beruntun:
Konsep yang digunakan dalam metode ini adalah membandingkan data-data yang ada dalam kumpulan tersebut, mulai dari elemen pertama sampai elemen ditemukan, atau sampai elemen terakhir. 

2.       Metode Pencarian Bagi Dua:
Metode ini diterapkan pada sekumpulan data yang sudah terurut (menaik atau menurun). Metode ini lebih cepat dibandingkan metode pencarian beruntun. Data yang sudah terurut menjadi syarat mutlak untuk menggunakan metode ini.
Konsep dasar metode ini adalah membagi 2 jumlah elemennya, dan menentukan apakah data yang berada pada elemen paling tengah bernilai sama, lebih dari atau kurang dari nilai data yang akan dicari. Jika bernilai sama, maka langsung data yang dicari ditemukan. Jika data di elemen terurut naik, maka jika data yang berada di tengah kurang dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kanan, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan sebaliknya untuk nilai data yang berada di tengah lebih dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kiri, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan demikian sebaliknya untuk data yang terurut menurun. Dalam hal ini tentukan indeks paling awal dan indeks paling akhir, untuk membagi 2 elemen tersebut.
Indeks awal = i, dimana nilai i, pada awalnya bernilai 0;
Indeks akhir = j, dimana nilai j, pada awalnya bernilai sama dengan jumlah elemen. 

Algoritma

Proses yang terjadi pada pencarian dengan metode ini adalah sebagai berikut :

1. Membaca Array data
2. Apabila Array belum terurut maka array diurutkan terlebih dahulu.
3. Menentukan data yang akan dicari
4. Menentukan elemen tengah dari array
5. Jika nilai elemen tengah sama dengan data yang dicari, maka pencarian berhenti.
6. Jika elemen tengah tidak sama dengan data yang dicari maka :
    a. Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
    b. Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.

1. Sequential Search (Pencarian berurutan)
                Adalah suatu teknik pencarian data dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Pencarian berurutan menggunakan prinsip sebagai berikut : data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan. 

Algoritma pencarian berurutan dapat dituliskan sebagai berikut :

1. i ← 0
2. ditemukan ← false
3. Selama (tidak ditemukan) dan (i <= N) kerjakan baris 4
4. Jika (Data[i] = x) maka ditemukan ← true, jika tidak i ← i + 1
5. Jika (ditemukan) maka i adalah indeks dari data yang dicari, jika tidak data tidak ditemukan

Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian sekuensial.

int SequentialSearch(int x)
{
     int i = 0;
     bool ditemukan = false;
     while ((!ditemukan) && (i < Max))
     {
          if(Data[i] == x)
               ditemukan = true;
          else
               i++;
     }
     if(ditemukan)
          return i;
     else
          return -1;
}

Fungsi diatas akan mengembalikan indeks dari data yang dicari. Apabila data tidak ditemukan maka fungsi diatas akan mengembalikan nilai –1.

Contoh program:

#include <conio.h>
#include <iostream.h>
main(){
int c,i,posisi;
int A[20]={3,2,4,10,20,1,5,8,7,9,6,5,11,12,14,13,16,15,17,19};


cout<<"Data : ";
for(i=0;i<20;i++){
 cout<<A[i]<<" ";
}

cout<<"\nData yang ingin dicari : ";
cin>>c;
i=0;
posisi=0;
while(i<19 && A[i]!=c){
 i++;
}
if (A[i]!=c){
 cout<<"Maaf data yang dicari tidak ada";
}else if(posisi=i+1)
   cout<<"ditemukan pada posisi ke "<<posisi;
getch();
}

2. Binary Search
                Salah satu syarat agar binary search dapat dilakukan adalah data sudah dalam keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, binary search tidak dapat dilakukan.
Prinsip dari binary search dapat dijelaskan sebagai berikut :
a.Mula-mula diambil posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data tengah.
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. Jika data sama, berarti ketemu.

Salah satu syarat agar pencarian biner dapat dilakukan adalah data sudah dalam keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita juga sering menggunakan pencarian biner. Misalnya saat ingin mencari suatu kata dalam kamus Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : mula-mula diambil posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data tengah. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1. Jika lebih besar, porses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah sama dengan yang dicari.Untuk lebih jelasnya perhatikan contoh berikut:

Misalnya ingin mencari data 17 pada sekumpulan data berikut :

Mula-mula dicari data tengah, dengan rumus (0 + 9) / 2 = 4. Berarti data tengah adalah data ke-4, yaitu 15. Data yang dicari, yaitu 17, dibandingkan dengan data tengah ini. Karena 17 > 15, berarti proses dilanjutkan tetapi kali ini posisi awal dianggap sama dengan posisi tengah + 1 atau 5.

Data tengah yang baru didapat dengan rumus (5 + 9) / 2 = 7. Berarti data tengah yang baru adalah data ke-7, yaitu 23. Data yang dicari yaitu 17 dibandingkan dengan data tenah ini. Karena 17 < 23, berarti proses dilanjukkan tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1 atau 6.

Data tengah yang baru didapat dengan rumus (5 + 6) / 2 = 5. Berarti data tengah yang baru adalah data ke-5, yaitu 17. data yang dicari dibandingkan dengan data tengah ini dan ternyata sama. Jadi data ditemukan pada indeks ke-5. Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar daripada posisi akhir. Jika posisi sudah lebih besar daripada posisi akhir berarti data tidak ditemukan.

Untuk lebih jelasnya perhatikan contoh pencarian data 16 pada data diatas. Prosesnya hampir sama dengan pencarian data 17. Tetapi setelah posisi awal 5 dan posisi akhir 6, data tidak ditemukan dan 16 < 17, maka posisi akhir menjadi posisi tengah – 1 atau = 4 sedangkan posisi awal = 5.

Disini dapat dilihat bahwa posisi awal lebih besar daripada posisi akhir, yang artinya data tidak ditemukan. 

Algoritma pencarian biner dapat dituliskan sebagai berikut : 

1 L ← 0
2 R ← N - 1
3 ditemukan ← false
4 Selama (L <= R) dan (tidak ditemukan) kerjakan baris 5 sampai dengan 8
5 m ← (L + R) / 2
6 Jika (Data[m] = x) maka ditemukan ← true
7 Jika (x < Data[m]) maka R ← m – 1
8 Jika (x > Data[m]) maka L ← m + 1
9 Jika (ditemukan) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan. 

Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian biner. 

int BinarySearch(int x)
{
     int L = 0, R = Max-1, m;
     bool ditemukan = false;
     while((L <= R) && (!ditemukan))
     {
          m = (L + R) / 2;
          if(Data[m] == x)
               ditemukan = true;
          else if (x < data[m])
               R = m - 1;
          else
               L = m + 1;
     }
     if(ditemukan)
          return m;
     else
          return -1;
}

Fungsi diatas akan mengembalikan indeks dari data yang dicari. Apabila data tidak ditemukan maka fungsi diatas akan mengembalikan nilai –1.

 Jumlah pembandingan minimum pada pencarian biner adalah 1 kali, yaitu apabila data yang dicari tepat berada di tengah-tengah. Jumlah pembandingan maksimum yang dilakukan dengan pencarian biner dapat dicari menggunakan rumus logaritma, yaitu : C = 2log(N)

Contoh program:

#include <iostream.h>

#include <conio.h>

#include <string.h>

main ()

{

    int jd,no,kiri,kanan,center;

    char data[20][50],cari[20];

   cout<<"\n\t\t *************************************** \n";

   cout<<"\t\t | \t\t\t\t       | \n";

   cout<<"\t\t | \t     Proses Pencarian \t       | \n";

   cout<<"\t\t | Menggunakan Algoritma Binary Search | \n";

   cout<<"\t\t | \t\t\t\t       | \n";

   cout<<"\t\t *************************************** \n\n\n";

    cout<<" Input Jumlah Data  : ";

    cin>>jd;

   cout<<endl;

    for (no=0;no<jd;no++)

    {

        cout<<" Input Data Ke-"<<(no+1)<<"    : ";

       cin>>data[no];

    }

   cout<<endl;

    cout<<" Input Nilai Dicari : ";

    cin>>cari;

    kiri=0;

    kanan=jd-1;

   center=(kanan-kiri)/2;

    while ((strcmp(data[center],cari)!=0) && (kiri>=0)&& (kanan<jd) && (kanan>=kiri))

    {

        if (strcmp (cari,data[center])>0)

       {

           kiri=center+1;

       }

       else if (strcmp (cari,data[center])<0)

       {

           kanan=center-1;

       }

       center=kiri+(kanan-kiri)/2;

    }

   cout<<endl;

    if (strcmp(data[center],cari)==0)

    {

        cout<<" Keterangan         : Data Ditemukan";

    }

    else

    {

        cout<<" Keterangan         : Data Tidak Ditemukan";

   }

    getch();

}

DAFTAR PUSTAKA:

http://hack.spyrozone.net/0202_Struktur_Data_Pencarian_searching_by_y3ppy_WWW.SPYROZONE.TK_06_Juni_2007.html

hendra-ryuka.blogspot.com/2010/05/searching.html

PENJELASAN TENTANG SORTING (SELECTION SORT DAN INSERTION SORT

METODE SORTING

Seringkali perancang program perlu mengurutkan sekumpulan data yang dimiliki untuk memudahkan pemrosesan selanjutnya terhadap data tersebut. Pengurutan adalah sebuah algoritma dasar yang sering diperlukan dalam pembuatan program. Berbagai algoritma pengurutan telah diciptakan dan dapat digunakan. Pemahaman tentang beberapa algoritma pengurutan dasar perlu diketahui, termasuk cara penggunaannya dalam program.

PENGERTIAN SORT

Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan data. Sortdalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urut menaik (ascending) dari nilai terkecil sampai dengan nilai terbesar, atau urut menurun (descending) dari nilai terbesar sampai dengan nilai terkecil. Sorting adalah proses pengurutan.

Terdapat dua macam pengurutan:

• Pengurutan internal (internal sort), yaitu pengurutan terhadap sekumpulan data yang disimpan dalam media   internal komputer yang dapat diakses setiap elemennya secara langsung. Dapat dikatakan sebagai   pengurutan tabel
• Pengurutan eksternal (external sort), yaitu pengurutan data yang disimpan dalam memori sekunder, biasanya data   bervolume besar sehingga tidak mampu untuk dimuat semuanya dalam memori.

SELECTION SORT

                   Algoritma Selection sort memilih elemen maksimum/minimum array, lalu menempatkan elemen maksimum/minimum itu pada awal atau akhir array (tergantung pada urutannya ascending/descending). Selanjutnya elemen tersebut tidak disertakan pada proses selanjutnya. Karena setiap kali selection sort harus membandingkan elemen-elemen data, algoritma ini termasuk dalam comparison-based sorting.

Seperti pada algoritma Bubble Sort, proses memilih nilai maksimum /minimum dilakukan pada setiap pass. Jika array berukuran N, maka jumlah pass adalah N-1.

Selection Sort (Metode Seleksi) 

• One of the simplest sorting algorithms
• Merupakan kombinasi antara sorting dan searching
• Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil (Ascending) atau terbesar (Descending) akan dipertukarkan ke posisi yang tepat di dalam array.
• Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0])/ data pertama, pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1])/ data kedua atau selanjutnya.
• Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. 

Contoh Selection Sort :

Ascending 

• Cek seluruh elemen array, temukan nilai terkecil (1) dan tukarkan posisinya dengan posisi nilai yang tersimpan pada posisi pertama dari array (3)

• Temukan nilai terkecil kedua (2), dan tukarkan posisinya dengan nilai yang berada pada posisi kedua (10).

• Dua elemen biru pertama tidak akan berubah lagi sebab mereka sudah merupakan nilai terkecil pertama dan kedua dalam array tsb.

• Sekarang, ulangi dengan cara/proses “pilih dan tukar” 

• Pengurutan Selesai.

Contoh Program Selection Sort menggunakan bahasa pemrograman C++
berikut kode programnya :

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

int main(void)
{
int array[5]; // An array of integers.
int length = 5; // Lenght of the array.
int i, j;
int firstelement, temp;

//Some input
for (i = 0; i < length; i++)
{
cout << "Enter a number: ";
cin >> array[i];
}

//Algorithm
for (i= length - 1; i > 0; i--)
{
firstelement = 0;
for (j=1; j<=i; j++)
{
if (array[j] < array[firstelement])
firstelement = j;
}
temp = array[firstelement];
array[firstelement] = array[i];
array[i] = temp;
}

//Some output
for (i = 0; i < 5; i++)
{
cout << array[i] << endl;
}
getch();
}

• Program Setelah dieksekusi :

INSERTION SORT

                Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort.

                Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang “tepat” untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya yang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sortingdisebut sebagai “pass“), dengan indeks dimulai dari 0.

                Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.

Berikut adalah simulasi Algoritma Insertion Sort
Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.

Simulasi Insertion Sort

Dari gambaran proses pengurutan/ sorting  data di atas dapat diketahui  bagaimana data-data tersebut berpindah  posisi  dari satu index ke index lain dalam satu array.  Untuk detail proses pengurutan diatas, dapat disimak melalui detail simulasi berikut.

Data awal : 5, 2, 4, 6, 1, 3

Jumlah Index = 6   dimulai dari 0 s/d 5

Anggaplah index adalah ‘I’,

Untuk setiap proses pengurutan data, perbandingan data dimulai dari index kedua (dalam hal ini i=1)

Proses I:

i=1, x=1; j=0

x<j à2<5? — true  =2, 5, 4, 6, 1, 3

Proses II

i=2, j=1, x=2

x<j à  4<5 — true = 2, 4, 5, 6, 1, 3     j=j-1,      Jika benar    x=x-1

x<j à4<2 — false = 2, 4, 5, 6, 1, 3

Proses III

I=3, j=2, x=3

x<j à6<5 — false =  2, 4, 5, 6, 1, 3     j=j-1    jika sebuah proses bernilai false, maka proses tersebut tidak akan dilanjutkan, karena secara otomatis data yang ada disebelah kiri semuanya sudah terurut dengan benar.

Proses IV

i=4, j=3, x=4

x<j à1<6 — true = 2, 4, 5, 1, 6, 3   j=j-1,     jika benar  maka  x=x-1

x<j à 1<5 — true = 2, 4, 1, 5,6, 3  j=j-1 ,   jika benar  maka   x=x-1

x<j  à1<4  — true = 2, 1, 4, 5,6, 3  j=j-1,    jika benar  maka   x=x-1

x<j  à 1<2 — true =   1, 2, 4, 5,6, 3

Proses V

i=5, j=4, x=5

x<j à3<6  — true = 1, 2, 4, 5,3, 6  j=j-1, jika benar maka x=x-1

x<j à3<5 — true = 1, 2, 4, 3, 5, 6   j=j-1, jika benar maka x=x-1

x<j à3<4 — true = 1, 2, 3, 4, 5, 6  j=j-1, jika benar maka x=x-1

x<jà3<2 — false = 1, 2, 3, 4, 5, 6  j=j-1

Berikut adalah contoh program dari insertion sort

#include<iostream>

#include <conio.h>

int main()

{

int data[]={5, 2, 4, 6, 1, 3};

cout<<“sebelum disorting: “;

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

cout<<data[i] <<“,  “;

cout<<endl <<endl;

for(int i=1; i<6; i++)

{

int j=i;

while(data[j]<data[j-1])

{

int tmp=data[j];

data[j]=data[j-1];

data[j-1]=tmp;

j­­--;

}

}

cout<<“Setelah disorting: “;

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

cout<<data[i] <<“,  “;

getch();

}

DAFTAR PUSTAKA:

https://thenurulazizah.wordpress.com/artikel-2/13-metode-sorting/

https://penamisterius.wordpress.com/2011/03/22/insertion-sort

QUEUE

QUEUE

        Queue pada Struktur Data atau antrian adalah sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung disebut dengan sisibelakang(rear), dan penghapusan(pengambilan elemen) dilakukan lewat ujung lain (disebut dengan sisi depan atau front). 

Queue atau antrian prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In First Out). 

Queue atau antrian banyak kita jumpai dalam kehidupan sehari-hari, ex: antrian Mobil diloket Tol, Antrian mahasiswa Mendaftar, dll. Contoh lain dalam bidang komputer adalah pemakaian sistem komputer berbagi waktu(time-sharing computer system) dimana ada sejumlah pemakai yang akan menggunakan sistem tersebut secara serempak.

Contoh yang paling populer untuk membayangkan sebuah queue adalah antrian pada kasir sebuah bank. Ketika seorang pelanggan datang, akan menuju ke belakang dari antrian. Setelah pelanggan dilayani, antrian yang berada di depan akan maju. Pada saat menempatkan elemen pada ujung (tail) dari queue disebut dengan enqueue, pada saat memindahkan elemen dari kepala (head) sebuah queue disebut dengan dequeue.

Pada Queue atau antrian Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya dimana membutuhkan variabel Head dan Tail ( depan/front, belakang/rear). 

Karakteristik Queue atau antrian : 

1. elemen antrian 

2. front (elemen terdepan antrian) 

3. tail (elemen terakhir) 

4. jumlah elemen pada antrian 

5. status antrian Operasi pada Queue atau antrian 

6. tambah(menambah item pada belakang antrian) 

7. hapus (menghapus elemen depan dari antrian) 

8. kosong( mendeteksi apakah pada antrian mengandung elemen atau tidak) 

Operasi-operasi Queue : 

 1. Create() Untuk menciptakan dan menginisialisasi Queue Dengan cara membuat Head dan Tail = -1 

 2. IsEmpty() Untuk memeriksa apakah Antrian sudah penuh atau belum 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. 

3. IsFull Untuk mengecek apakah Antrian sudah penuh atau belum Dengan cara mengecek nilai Tail, jika 

Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh 

4. Enqueue Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu 

5. Dequeue() Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1 Penggeseran dilakukan dengan menggunakan looping.

6. 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-elemen Antrian tidak lagi terbaca 

7. Tampil() Untuk menampilkan nilai-nilai elemen Antrian Menggunakan looping dari head s/d tail 

Queue juga mempunya dua tipe, yaitu:

1.    Queue dalam bentuk Linier

Linear array adalah suatu array yang dibuat seakan-akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar. 

2.    Queue dalam bentuk Circular

Circular array adalah suatu array yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal (head) dan titik akhir (tail) saling bersebelahan jika array tersebut masih kosong. Posisi head dan tail itu bebas asalkan saling bersebelahan.

Implementasi Antrian dengan Array

                Seperti halnya pada tumpukan, maka dalam antrian kita juga mengenal ada dua operasi dasar, yaitu menambah elemen baru yang akan kita tempatkan di bagian belakang antrian dan menghapus elemen yang terletak di bagian depan antrian. Disamping itu seringkali kita juga perlu melihat apakah antrian mempunyai isi atau dalam keadaan kosong.

                Operasi penambahan elemen baru selalu bisa kita lakukan karena tidak ada pembatasan banyaknya elemen dari suatu antrian. Tetapi untuk menghapus elemen, maka kita harus melihat apakah antrian dalam keadaan kosong atau tidak. Tentu saja kita tidak mungkin menghapus elemen dari suatu antrian yang sudah kosong. Untuk menyajikan antrian menggunakan array, maka kita membutuhkan deklarasi antrian, misalnya sebagai berikut:

#define MAXQUEUE 100;

typedef int ItemType;

typedef struct{

                 int Count;

                 int Front;

                int Rear;

                 ItemType Item[MAXQUEUE];

                 }Queue;

Front, menunjukkan item yang paling depan, yaitu elemen yang akan dihapus jika dilakukan operasi penghapusan. Setelah kita melakukan penghapusan, kita melakukan increment pada indeks Front, sehingga indeks menunjuk pada posisi berikutnya. Jika indeks ini jatuh pada angka tertinggi, yaitu angka paling maksimum dari array (N), maka kita melakukan setting ulang ke 0. Array Item[0:N-1] berisi N item yang merupakan isi dari antrian. Berada pada posisi 0:N-1dimana pada posisi ini dapat diindikasikan dua pengenal, yaitu Front dan Rear.

 Count menunjukkan jumlah item dalam antrian. Rear menunjukkan posisi dimana setelahnya dapat dimasukkan item berikutnya. Representasi antrian lengkap dengan operasi-operasi yang merupakankarakteristik antrian adalah sebagai berikut:

Implementasi Antrian dengan Linked list

Antrian yang direpresentasikan dengan linked list mempunyai beberapa variasi. Pada kesempatan kali ini hanya direpresentasikan satu macam saja. Linked list yang digunakan di sini menggunakan struktur yang berisi pointer yang menunjuk pada simpul Front dan Rear dari linked list. Masing-masing simpul berisi data dari antrian dan juga link yang menunjuk pada simpul selanjutnya dari linked list, yang dinamakan Link.

Antrian Berprioritas

                Dalam antrian yang telah dibahas di atas, semua elemen yang masuk dalam antrian dianggap mempunyai prioritas yang sama, sehingga elemen yang masuk lebih dahulu akan diproses lebih dahulu. Dalam praktek, elemen-elemen yang akan masuk dalam suatu antrian ada yang dikatakan mempunyai prioritas yang lebih tinggi disbanding yang lain. Antrian yang demikian ini disebut dengan antrian berprioritas (priority queue).

 Dalam antrian berprioritas, setiap elemenn yang akan msuk dalam antrian sudah ditentukan lebih dahulu prioritasnya. Dalam hal ini berlaku dua ketentuan, yaitu:

1. Elemen-elemen yang mempunyai prioritas lebih tinggi akan diproses lebih dahulu.

2. Dua elemen yang mempunyai prioritas sama akan dikerjakan sesuai dengan urutan

pada saat kedua elemen ini masuk dalam antrian.

                Dengan memperhatikan kedua ketentuan di atas, akan berlaku ketentuan bahwa elemen yang mempunyai prioritas lebih tinggi akan dikerjakan lebih dahulu disbanding elemen yang mempunyai prioritas lebih rendah, meskipun elemen yang berprioritas tinggi masuknya sesudah elemen yang berprioritas rendah. Salah satu contoh antrian berprioritas ini adalah pada sistem berbagi waktu (time-sharing system) dimana program yang mempunyai prioritas tinggi akan dikerjakan lebih dahulu dan program-program yang berprioritas sama akan membentuk antrian biasa.  Ada beberapa cara untuk mengimplementasikan antrian berprioritas. Salah satu caranya adalah dengan menggunakan linked list. Jika kita menggunakan linked list, khususnya single linked list atau double linked list, maka ada ketentuan lain yang perlu diperhatikan, yaitu:

1. Setiap node dari linked list terdiri tiga bagian, yaitu bagian informasi, angka prioritas dan bagian-bagian penyambung ke simpul lain.

2. Simpul X mendahului (terletak di sebelah kiri) simpul Y, jika prioritas X lebih tinggi dibanding prioritas Y atau jika prioritas X dan Y sama, maka simpul X datang lebih dahulu dibanding dengan Y.

Biasanya dibuat suatu perjanjian bahwa angka prioritas yang lebih kecil menunjukkan derajad prioritas yang lebih tinggi. Sebagai contoh, jika angka prioritas pada simpul X adalah 1 dan pada simpul Y adalah 2, maka dikatakan bahwa simpul X berprioritas lebih tinggi dibanding dengan simpul Y.

Contoh program Queue

#include <conio.h>
#include <stdio.h>
#include <iostream.h>
#include <iomanip.h>
#define max 6

typedef struct
{
 int head;
   int tail;
}antrian;

antrian ue;

typedef struct
{
   char *nm[max], *almt[max], *tgl[max];
} variabel;

variabel qu;


void creat()
{
 ue.head=ue.tail=-1;
}

empty()
{
 if(ue.tail==-1)
      return 1;
   else
      return 0;
}

full()
{
 if(ue.tail==max-1)
      return 1;
   else
      return 0;
}

void en(char *a, char *b, char *c)
{
 if(empty()==1)
   {
      ue.head=ue.tail=0;
      qu.nm[ue.tail]=a;
      qu.almt[ue.tail]=b;
      qu.tgl[ue.tail]=c;
   }

   else if(full()==0)
   {
    ue.tail++;
      qu.nm[ue.tail]=a;
      qu.almt[ue.tail]=b;
      qu.tgl[ue.tail]=c;
   }

   else if(full()==1)
   {
    cout<<"QUEUE PENUH";
   }
}

de()
{
 if(empty()==0)
 {
  int i;
      char *aa=qu.nm[ue.tail];
      char *bb=qu.almt[ue.tail];
      char *cc=qu.tgl[ue.tail];

       for(i=ue.head; 1<=ue.tail-1; i++)
    {
       qu.nm[i]=qu.nm[i+1];
         qu.almt[i]=qu.almt[i+1];
     qu.tgl[i]=qu.tgl[i+1];
    }

    ue.tail--;
      cout<<"DATA YANG DIHAPUS ADALAH : \n";

      cout<<"NAMA   : "<<aa<<endl;
      cout<<"ALAMAT : "<<bb<<endl;
      cout<<"TANGGAL: "<<cc<<endl;
   }


   else if(empty()==1)
   { cout<<"DATA EROR......QUEUE KOSONG"; }

   return 1;
}

void clear()
{
   ue.head=ue.tail=-1;
   cout<<"QUEUE CLEAR";
}

void view()
{
 if(empty()==0)
   {
  cout<<"NO NAMA       ALAMAT            TANGGAL\n";

   for(int i=ue.head; i<=ue.tail; i++)
   {
     cout<<setiosflags(ios::left)<<setw(3)<<i;
      cout<<setiosflags(ios::left)<<setw(11)<<qu.nm[i];
      cout<<setiosflags(ios::left)<<setw(18)<<qu.almt[i];
      cout<<setiosflags(ios::left)<<setw(9)<<qu.tgl[i]<<endl;
   }
   }
   else
   { cout<<"NO NAMA       ALAMAT            TANGGAL\n"; }
}

main()
{

 int menu;
   char nm[20], almt[40], tgl[20];

creat();

do{

clrscr();

cout<<"===========================\n";
cout<<"    MENU PROGRAM QUEUE\n";
cout<<"===========================\n";
cout<<"1.ENQUEUE\n";
cout<<"2.DEQUEUE\n";
cout<<"3.CLEAR\n";
cout<<"4.VIEW\n";
cout<<"5.EXIT\n";
cout<<"===========================\n";
cout<<"PILIH MENU : ";       cin>>menu;

if(menu==1)
{     cout<<"MASUKAN NAMA   : ";    gets(nm);
     cout<<"MASUKAN ALAMAT : ";    gets(almt);
         cout<<"MASUKAN TANGGAL: ";      gets(tgl);
     en(nm, almt, tgl);
}

else if(menu==2)
{
   de();
}

else if(menu==3)
{
    clear();
}

else if(menu==4)
{
    view();
}

else if(menu==5)
{
    cout<<"exiiitttt......";
}
getch();

}while(menu!=5);

}

DAFTAR PUSTAKA:

http://entin.lecturer.pens.ac.id/Struktur%20Data%20&%20Algoritma/buku/Data%20Structure%20-%20Bab%204.pdf

http://www.slideshare.net/rhedwiyuni/implementasi-queue

STACK

STACK

                Pengertian Stack atau tumpukan adalah suatu stuktur data yang penting dalam pemrograman yang mempunyai sifat LIFO (Last In First Out), Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.  Stack (Tumpukan) adalah list linier yang dikenali elemen puncaknya (TOP) dan Aturan penyisipan dan penghapusan elemennya tertentu. Penyisipan selalu dilakukan “di atas“  TOP dan Penghapusan selalu dilakukan pada TOP. 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).

OPRASI-OPRSI/ 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

Berikut ini merupakan karakteristik yang dimiliki oleh stack :

- Data hanya dapat di-insert pada posisi top stack

- Data hanya dapat di-delete pada posisi top stack

- Data tidak dapat di-delete dari tengah-tengah stack tanpa memindahkan item yang ada pada atasnya terlebih dahulu

Terdapat 2 operasi basic dalam stack :

- PUSH

- POP

Ketika kita memasukkan data kedalam sebuah stack, kita dapat menyebutnya PUSH. Sebaliknya, jika kita mengeluarkan data dari sebuah stack, kita dapat menyebutnya POP. Untuk lebih memperjelas PUSH dan POP, Simaklah gambar berikut ini.

IMPLEMENTASI STACK MENGGUNAKAN ARRAY

                Sebuah array dapat kita manfaatkan untuk mengimplementasikan stack jika jumlah elemen maksimum diketahui. Ketika kita hendak meng- implementasikan stack menggunakan array, kita harus memastikan bahwa array yang dideklarasikan cukup untuk menyimpan data atau elemen maksimum pada stack.

Untuk menerapkan stack menggunakan array, tentunya kita harus mendeklarasikan array terlebih dahulu. Misalkan :

int stack[10];

Pendeklarasian diatas berarti kita membuat sebuah array dengan ukuran/size sebesar 10, dan hanya dapat menampung maksimal 10 nilai integer.

Setelah mendeklarasikan array, kita perlu mendeklarasikan variabel untuk menyimpan index terakhir (top position), misalnya kita deklarasikan seperti ini :

int top;

Untuk kondisi stack yang masih kosong, mari kita set top = -1

Nah, baru setelah ini kita akan mengimplementasikan operasi PUSH dan POP.

PUSH

Dengan menjalankan operasi PUSH, berarti kita menyimpan data pada posisi top didalam stack. Langkah selanjutnya yang dapat kita tempuh adalah :

1. Melakukan increment terhadap top sebesar 1

2. Menyimpan nilai/value pada index top didalam array

(Sekarang top mengandung index dari elemen yang paling atas)

Perhatikan gambar dibawah ini :

Ketika stack di implementasikan didalam sebuahh array, size/ukuran dari stack adalah fixed. Hal ini berarti terdapat batas atas pada jumlah maksimum elemen yang dapat ditampung dalam stack.

Ketika stack sudah menampung data secara maksimum, maka dapat kita berikan status stack telah penuh/full. Ketika kita mencoba melakukan operasi push pada stack yang sudah penuh, maka akan terjadi overflow. Maka dari itu sebelum  kita melakukan operasi push, kita harus melakukan pengecekan apakah stack sudah full atau belum.

Jika stack sudah penuh, maka kondisi stack tsb adalah :

top = MAX -1

Jika kondisi tersebut true, maka operasi push seharusnya tidak dapat dilaksanakan.

Sehingga kita dapat membuat kondisi seperti berikut :

If top = MAX-1:

a. Display “Stack Full”

b. Exit

POP

Operasi POP berarti memindahkan atau menghapus item pada posisi top didalam stack. Untuk mengimplementasikannya kita dapat menggunakan langkah berikut ini :

1. Memungut kembali nilai dari index top

2. Melakukan decrement terhadap top sebesar 1

Bagaimanapun juga, sebelum melakukan operasi pop, kita harus melakukan pengecekan apakah stack itu kosong atau tidak. Jika kosong, tentu tidak ada elemen yang harus kita pop. Masih ingat dengan pendeklarasian diatas? Ya, sebelumnya kita telah mendeklarasikan bahwa jika kondisi stack kosong, maka top = -1

Sehingga kita dapat menerapkan kondisi berikut ini :

if top = -1

a. Display “Stack empty”

b. Exit

Contoh Program Stack PUSH / POP 

                Mengisi (PUSH) stack sampai PENUH, dan mengambil (POP) isi stack sampai KOSONG. Susun program untuk menyiapkan array satu dimensi yang akan digunakan sebagai stack S sebanyak 10 elemen, bertipe integer. Kemudian inputkan data (nilai numerik) dan simpan (PUSH) ke stack S. Proses input dan PUSH selesai bila data yang diinput bernilai = 999, atau stack S penuh. (nilai 999 dipakai sebagai end of data, tidak ikut dipush ke stack S). setelah itu dikeluarkan (POP) isi stack dan cetak ke layar satu persatu sampai stack menjadi KOSONG.

Contoh program sederhana single stack:

#include <iostream.h>
#include<stdio.h>
#define MAX 5
#define true 1
#define false 0

char stack[MAX];
int top;

void init(void);
int full(void);
int empty(void);
char pop(void);
void clear(void);
void push(char info);
void baca(void);

void main()
{
char pilih,elm;
cout<<"demo operasi single stack"<<endl;
init();
do
{
cout<<"OPERASI SINGLE STACK :"<<endl;
cout<<"[1]PUSH"<<endl;
cout<<"[2]POP"<<endl;
cout<<"[3]clear"<<endl;
cout<<"[4]BACA"<<endl;
cout<<"[5]selesai"<<endl;
cout<<"pilihan:";cin>>pilih;
switch(pilih)
{
case '1':cout<<"PUSH-->";cin>>elm;
push(elm);
break;
case '2':elm=pop();
cout<<"pop"<<elm;
break;
case '3':clear();
break;
case '4':baca();
break;
case '5':break;
default:cout<<"salah pilih..."<<endl;
}
cout<<endl;
}
while(pilih!='5');
}

void init(void)
{
top=0;
}
void push(char info)
{
if(full()!=true)
{
top++;
stack[top]=info;
}
else
cout<<"stack overflow..."<<endl;
}
char pop(void)
{
char info;
if(empty()!=true)
{
info=stack[top];
top--;
return(info);
}
else
cout<<"stack underflow..."<<endl;
}
void clear(void)
{
top=0;
}
int full(void)
{
if(top==MAX)
return(true);
else
return(false);
}
int empty(void)
{
if(top==0)
return(true);
else
return(false);
}
void baca(void)
{ int i;
cout<<"isi stack:"<<endl;

if(top>0)
{
for(i=1;i<=top;i++)
cout<<stack[i];
}
else
cout<<"(kosong)";
cout<<endl;
}

 

DAFTAR PUSTAKA:

http://www.purwadhikapress.com/konsep-stack.html

http://bekokmarley.blogspot.com/2014/01/pengertian-dan-penjelasan-struktur-data.html

pengertian array dan contoh program sederhana

ARRAY

                Array adalah sekelompok data sejenis yang disimpan ke dalam variabel dengan nama yang sama, dengan memberi indeks pada variabel untuk membedakan antara yang satu dengan yang lain.

-          Larik adalah struktur data statik yang menyimpan sekumpulan elemen yang bertipesama.

-          Setiap elemen diakses langsung melalui indeksnya.

-          Indeks larik harus tipe data yang menyatakan keterurutan misalnya integer atau karakter.

1.       Deklarasi Variable Array

BU : tipe nama_variabel[indeks];

Contoh : float bil[10];

                Deklarasi variabel array dengan nama bil yang akan menampung 10 data yang bertipe float. Indeks 10 menunjukkan variabel bil terdiri dari 10 elemen, dimana setiap elemen akan menampung sebuah data. Indeks array dimulai dari nol(0) , sedang nomor elemen biasanya dimulai dari satu(1). Nomor elemen dapat dibuat sama dengan nomor indeks untuk mempermudah pembuatan program yaitu dengan memberi indeks satu lebih banyak dari jumlah data yang dibutuhkan, sehingga menjadi: 

float bil[11]

Cara Pendefinisian Array

a.       Sebagai Peubah

Contoh :

L : array[1..50] of integer

NamaMhs : array[‘a’..’j’] of string

b.      Sebagai tipe baru

Contoh :

type LarikInt : array[1..100] of integer

P : LarikInt

c.       Mendefinisikan ukuran maksimum elemen larik sebagai konstanta

Contoh :

Const Nmaks = 100

type Larikint : array[1..Nmaks] of integer

P : LarikInt

Cara menterjemahkan ke bahasa C++ :

#define Nmaks 100

typedef int Larikint[Nmaks+1];

Larikint P;

2.       Jenis Array

a.       Array Dimensi Satu

Array Satu dimensi tidak lain adalah kumpulan elemen-elemen identik yang tersusun dalam satu baris. Elemen-elemen tersebut memiliki tipe data yang sama, tetapi isi dari elemen tersebut boleh berbeda.

Bentuk umum:

NamaArray[n] = {elemen0, elemen1, elemen2,…..,n};

n = jumlah elemen

b.       Array Dimensi Dua

Array dua dimensi sering digambarkan sebagai sebuah matriks, merupakan perluasan dari array satu dimensi. Jika array satu dimensi hanya terdiri dari sebuah baris dan beberapa kolom elemen, maka array dua dimensi terdiri dari beberapa baris dan beberapa kolom elemen yang bertipe sama sehingga dapat digambarkan sebagai berikut:

Bentuk umum:

NamaArray [m][n];

Atau

NamaArray [m][n] = { {a,b,..z},{1,2,…,n-1} };

Contoh:

double matrix[4][4];

bool papan[2][2] = { {true,false},{true,false} };

Pendeklarasian array dua dimensi hampir sama dengan pendeklarasian array satu dimensi, kecuali bahwa array dua dimensi terdapat dua jumlah elemen yang terdapat di dalam kurung siku dan keduanya boleh tidak sama. Elemen array dua dimensi diakses dengan menuliskan kedua indeks elemennya dalam kurung siku.

c.        Pointer

Pointer merupakan tipe data berukuran 32 bit yang berisi satu nilai yang berpadanan dengan alamat memori tertentu. Sebagai contoh, sebuah variabel P bertipe pointer bernilai 0x0041FF2A, berarti P menunjuk pada alamat memori 0041FF2A. Pointer dideklarasikan seperti variabel biasa dengan menambahkan tanda * (asterik) yang mengawali nama variabel.

Bentuk Umum:

namaVariabel;

Contoh:

float * px;

Statement di atas mendeklarasikan variabel px yang merupakan pointer. Penyebutan tipe data float berarti bahwa alamat memori yang ditunjuk oleh px dimaksudkan untuk berisi data bertipe float.

Contoh program Array sederhana untuk Menghitung Nilai Rata-Rata:

#include<iostream.h>
#include<conio.h>
#define max 7
main()
{
float a[max],jumlah=0,rata_rata;
int j;

//Memasukkan nilai ke dalam elemen array
// \n\n" berfungsi sama seperti endl
cout<<"Masukkan Nilai : \n\n";
for(j=0;j<max;j++)
{
cout<<"A["<<j<<"]= ";
cin>>a[j];
jumlah=jumlah + a[j];
}
//Melakukan Proses perhitungan
rata_rata=jumlah/max;
cout<<endl;

//Menampilkan Hasil Perhitungan
cout<<"Nilai Rata-Rata= "<<rata_rata;
getch();
} 

DAFTAR PUSTAKA:

https://ununisnanto.wordpress.com/struktur-data/

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