Rangkuman Materi Praktikum Struktur Data

NAMA	: I KOMANG JUNI ARTAWAN
NIM	: 140010307
KELAS	: AB141
MATA KULIAH	: PRAKTIKUM STRUKTUR DATA
DOSEN PENGAMPU	: IB KETUT SURYA ARNAWA, S.Kom
ASISTEN DOSEN	: STEVEN ANTHONY

Posting ini dibuat sebagai syarat mengikuti responsi mata kuliah Praktikum Struktur Data di kampus STMIK STIKOM Bali tahun ajaran 2014/2015.

1. Variabel

2. Array

3. Stack (Tumpukan)

Stack merupakan bentuk khusus dari suatu struktur data, dimana elemen yang ditambahkan ke dalam daftar dan diambil dari daftar hanya pada bagian yang paling atas atau terakhir, atau dengan kata lain prinsip pengolahannya adalah last-in first-out (LIFO). Data yang terakhir kali dimasukkan akan pertama kali keluar dari stack.

Gambar 7 : Ilustrasi tumpukan (stack)

Macam-macam operasi/fungsi yang digunakan pada stack

Push	Digunakan untuk menambah elemen pada tumpukan paling atas;
Pop	Digunakan untuk mengambil elemen pada tumpukan paling atas
Clear	Digunakan untuk mengosongkan tumpukan
IsEmpty	Digunakan untuk mengecek apakah tumpukan sudah kosong
IsFull	Digunakan untuk mengecek apakah tumpukan sudah penuh

Contoh Penerapan Tumpukan (Stack) Dalam Kehidupan Sehari-hari

Contoh penerapan umpukan dalam kehidupan sehari-hari bisa ditemukan saat menumpuk pakaian di lemari, dimana untuk menambahkan pakaian kita harus mengetahui apakah lemari masih mempunyai ruang kosong atau tidak, jika ternyata masih tersedia ruang kosong maka tumpukan masih bisa ditambahkan, sedangkan jika tumpukan sudah penuh maka tumpukan tidak bisa ditambah lagi. Untuk mengambil salah satu pakaian, maka cara yang paling tepat adalah mengambil dari bagian tumpukan yang paling atas, proses ini menyerupai konsep Last In First Out (LIFO) dimana yang terakhir masuk kedalam tumpukan akan pertamakali keluar dari tumpukan.

Contoh kode program stack sederhana dalam bahasa pemrograman C++

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

struct STACK
{
int data [5];
   int atas;
};
STACK tumpuk;

void main()
{
clrscr();
   int pilihan,baru,i;
   tumpuk.atas=-1;
   do
   {
    clrscr();
      cout<<"1. Push Data: "<<endl;
      cout<<"2. Pop Data: "<<endl;
      cout<<"3. Print Data: "<<endl;
      cout<<endl;
      cout<<"Pilihan: ";
      cin>>pilihan;
      switch(pilihan)
      {
       case 1:
         {
         if(tumpuk.atas==5-1)
         {
          cout<<"Tumpukan Penuh";
            getch();
         }
         else
         {
          cout<<"data yang akan di push: ";
            cin>>baru;
            tumpuk.atas++;
            tumpuk.data[tumpuk.atas]=baru;
         }

break;
         }
         case 2 :
         {
          if(tumpuk.atas==-1)
            {
             cout<<"Tumpukan kosong";
               getch();
            }
            else
            {
             cout<<"Data yang akan di pop: "<<tumpuk.data[tumpuk.atas]<<endl;
               tumpuk.atas--;
               getch();
            }
            break;
         }
         case 3 :
         {
          if(tumpuk.atas==-1)
            {
             cout<<"Tumpukan kosong"<<endl;
               getch();
            }
            else
            {
             cout<<"Data: "<<endl;
               for(i=0;i<=tumpuk.atas;i++)
               {
                cout<<tumpuk.data[i]<<" ";
               }
               getch();
            }
            break;
         }
         default:
         {
          cout<<"Tidak ada dalam pilihan"<<endl;
         }
      }
   }
   while(pilihan>=1 && pilihan<=3);
   getch();
}

4. Queue (Antrian)

Struktur Data Antrian (Queue) adalah suatu bentuk khusus dari List Linier dengan operasi penyisipan (Insertion) hanya diperbolehkan pada salah satu sisi, yang disebut sisi belakang (Rear) dan operasi penghapusan (Deletion) hanya diperbolehkan pada sisi lainnya yang disebut sisi depan (Front) dari list.

Gambar 8 : Ilustrasi struktur data antrian

Macam-macam operasi/fungsi yang digunakan pada queue

EnQueue	Digunakan untuk memasukan data ke antrian paling belakang
DeQueue	Digunakan paling depan untuk mengeluarkan data dari antrian
Clear	Digunakan untuk mengosongkan antrian
IsEmpty	Fungsi yang digunakan untuk mengecek apakah antrian sudah kosong
IsFull	Fungsi yang digunakan untuk mengecek apakah antrian sudah penuh

Tabel 2: Daftar operasi pada antrian

Contoh penerapan antrian dalam kehidupan sehari-hari
Contoh penerapan antrian dalam kehidupan sehari-hari sangat mudah kita temukan, misalnya antrian pada antrian gerbang tol, kendaraan yang pertama kali memasuki gerbang tol maka akan menjadi yang pertama pula keluar dari gerbang tol sesuai dengan konsep First In First Out (FIFO).

Contoh kode program antrian sederhana dalam bahasa pemrograman C++

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

#define max 10

typedef struct
{
int data[max];
   int head;
   int tail;
}
queue;

queue antrian;

void create()
{
antrian.head=antrian.tail=-1;
}

int isempty()
{
if(antrian.tail==-1)
   return 1;
   else
   return 0;
}

int isfull()
{
if(antrian.tail>=max-1)
   return 1;
   else
   return 0;
}

void enqueue(int data)
{
if(isempty()==1)
   {
    antrian.head= antrian.tail= 0;
      antrian.data[antrian.tail]=data;
      cout<<"Data "<<antrian.data[antrian.tail]<<"Masuk!!!";
   }
   else if(isfull()==0)
   {
    antrian.tail++;
      antrian.data[antrian.tail]=data;
      cout<<"Data"<<antrian.data[antrian.tail]<<"Masuk!!!";
   }
   else if(isfull()==1)
   {
    cout<<"Ruangan Penuh!!"<<endl;
      cout<<data<<"Ga Bisa Masuk!!!";
   }
}
void dequeue()
{
int i;
   int e= antrian.data[antrian.head];
   if(antrian.tail==-1)
   {
    cout<<"Ga Ada Antrian... Data Kosong"<<endl;
   }
   else
   {
    for(i=antrian.head; i<antrian.tail-1; i++)
      {
       antrian.data[i]= antrian.data[i+1];
      }
      antrian.tail--;
      cout<<"Data yang keluar lebih dulu= "<<e<<endl;
   }
}
void clear()
{
antrian.head=antrian.tail=-1;
   cout<<"Duh Lega, Ruangan jadi ngga sumpek..."<<endl;
   cout<<"Data Clear";
}
void tampil()
{
if(isempty()==0)
   {
    cout<<"Data Dalam Antrian"<<endl;
      cout<<"=====================================";
      cout<<endl;
      for(int i=antrian.head; i<antrian.tail; i++)
      {
       cout<<"| " <<antrian.data[i]<<" |";
      }
   }
   else
   {
    cout<<"Ga ada antrian.... Data kosong";
   }
}
void main()
{
int pil;
   int data;
   create();
   do
   {
    clrscr();
      cout<<"Implementasi Antrian dengan Struct"<<endl;
      cout<<"==========================================";
      cout<<endl;
      cout<<"1. Enqueue (Push)"<<endl;
      cout<<"2. Dqueue (Pop)"<<endl;
      cout<<"3. Print"<<endl;
      cout<<"4. Clear"<<endl;
      cout<<"5. Exit"<<endl;
      cout<<"Masukkan pilihan anda : ";
      cin>>pil;
      switch(pil)
      {
       case 1:
         {
          cout<<endl;
            cout<<"Data = ";
            cin>>data;
            enqueue(data);
            break;
         }
         case 2:
         {
          cout<<endl;
            dequeue();
            break;
         }
         case 3:
         {
          cout<<endl;
            tampil();
            break;
         }
         case 4:
         {
          cout<<endl;
            clear();
            break;
         }
      }
      getch();
   }
   while(pil!=5);
}

5. Sorting (Pengurutan)

Sorting atau disebut juga pengurutan merupakan suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.

Terdapat beberapa algoritma yang umum digunakan dalam proses pengurutan yaitu:

1. Insertion Sort

Insertion sort atau metode pengurutan dengan proses “menyelipkan” dimana algoritma dari metode insertion sort ini dapat dianalogikan seperti halnya mengurutkan kartu. Jika suatu kartu dipindahkan posisinya berdasarkan urutan yang benar, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi untuk pemindahanan kartu tersebut.

2. Selection Sort

Insertion sort ada metode pengurutan berdasarkan 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, temukan 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.

Contoh penerapan sorting dalam kehidupan sehari-hari

Contoh penerapan sorting dalam kehidupan sehari-hari dapat ditemukan pada aktifitas permainan kartu, dimana jika menerapkan metode insertion sort maka suatu kartu akan diselipkan pada posisi yang sesuai dan menggeser posisi kartu lain baik maju ataupun mundur untuk memperoleh urutan yang sesuai. Jika proses pengurutan kartu menggunakan metode selection sort maka secara sementara akan membentuk dua kelompok kartu yaitu kelompok kartu yang telah berurutan dan kelompok kartu yang belum berurutan. Yang pertama dicari adalah kartu dengan nila terkecil kemudian meletakkannya pada suatu sisi (kelompok kartu yang telah terurut), kemudian dilanjutkan dengan mencari kartu urutan berikutnya dengan membandingkan nilai antar kartu pada kelompok kartu yang masih belum terurut hingga menemukan kartu dengan nilai yang sesuai, proses demikian diulang terus hingga seluruh kartu menemukan urutan yag sesuai.

Contoh Kode Program Sorting Menggunakan Metode Insertion Sort dan Selection Sort Dalam Bahasa C++

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
int data[10];
int n;

void tukar(int a, int b)
{
int t;
   t=data[b];
   data[b]=data[a];
   data[a]=t;
}

void insertion_sort()
{
int pos, i, j;
   for(i=1; i<n; i++)
   {
    pos=data[i];
      j=i-1;
      while(data[j]>pos && j>=0)
      {
       data[j+1]=data[j];
         j--;
      }
      data[j+1]=pos;
   }
   cout<<"insertion sort selesai !"<<endl;
   cout<<"Data : "<<endl;
   for(int i=0;i<n;i++)
   {
    cout<<data[i]<<" ";
   }
   cout<<endl;
}

void selection_sort()
{
int pos,i,j;
   for(i=0;i<n-1;i++)
   {
    pos=i;
      for(j=i+1;j<n;j++)
      {
       if(data[j]<data[pos])pos=j;
      }
      if(pos!=i)
      {
       tukar(pos,i);
      }
   }
   cout<<"selection sort selesai !"<<endl;
   cout<<"Data : "<<endl;
   for(int i=0;i<n;i++)
   {
    cout<<data[i]<<" ";
   }
   cout<<endl;
}

void input()
{
cout<<"Masukkan jumlah data = ";
   cin>>n;
   for(int i=0;i<n;i++)
   {
    cout<<"Masukkan data ke - "<<(i+1)<<" = " ;
      cin>>data[i];
   }
}

void main()
{
int pil;
   clrscr();
   do
   {
      clrscr();
    cout<<"1. Input Data"<<endl;
    cout<<"2. Selection Sort"<<endl;
      cout<<"3. Insertion Sort"<<endl;
    cout<<"4. Exit"<<endl;
      cout<<"Masukkan Pilihan anda = ";
      cin>>pil;

    switch(pil)
    {
       case 1: input();break;
       case 2: selection_sort();break;
         case 3: insertion_sort();break;
    }
    getch();
   }
   while(pil!=4);
}

6. Searching (Pencarian)

Searching adalah aktifitas pencarian data dengan cara menelusuri data-data tersebut. Dalam kaitan struktur data, tempat pencarian data berupa array dalam memori. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun).

Terdapat 2 algoritma pencarian yang umum digunakan, yaitu:

1. Sequential Search

Pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana. Prinsik kerja algoritma ini adalah dengan membandingkan data yang ada satu persatu secara berurutan dengan yang data yang dicari hingga data tersebut ditemukan atau tidak ditemukan.

2. Binary Search
Metode binary search hanya dapat digunakan jika sejumlah data telah diurutkan. Jika dibandingkan dengan metode sequential search, metode ini jauh lebih cepat. Secara garis besar cara kerja metode ini bisa adalah sebagai berikut:
Urutkan dahulu sejumlah data. Lalu bagi dua data-data tadi dengan jumlah data yang sama pada masing-masingnya. Kemudian data dibandingkan dengan data terakhir dari subdata yang pertama. Jika data yang dicari lebih keci, pencarian dilanjutkan pada sub data pertama dengan terlebih dahulu membagi dua lagi data-data tersebut dengan jumlah yang sama. Tetapi jika data yang dicari lebih besar dari data terakhir subdata pertama, berarti data yang dicari kemungkinan terletak pada subdata yang kedua. Proses diatas dilakukan berulang sampai data ditemukan atau tidak ditemukan.

Contoh Penerapan Struktur Data Searching Dalam Kehidupan Sehari-hari
Contoh penerapan proses pencarian sangat mudah ditemukan dalam kehidupan sehari-hari, untuk metode sequential search bisa kita temukan saat membeli pakaian, proses pencarian dimulai dengan mencari salah satu pakaian yang menurut kita sesuai kemudian mencari lagi pakaian lain dengan cara membandingkannya satu persatu. Sedangakan contoh penerapan meteode binary search bisa kita temukan saat hendak mencari sebuah buku dengan judul yang diawali oleh huruf A pada rak yang isinya telah terurut berdasarkan judul dari A hingga Z, maka kita akan lebih mudah menemukan buku yang hendak kita cari, yaitu cukup dengan melakukan pencarian pada rak yang berisi buku dengan kode A.

Contoh Kode Program Searching Dengan Dalam Bahasa C++

Sequential Search

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
void main()
{
//deklarasi variabel
int A[10],n, i,j,k,tkr,right,left,middle,tm;

//fungsi untuk input data
   cout<<"Masukkan jumlah data = ";
   cin>>n;
for(i=0;i<n;i++)
{
    cout<<"Masukkkan data ke - "<<(i+1)<<" = ";
      cin>>A[i];
}
   cout<<"Masukkan data yang akan anda cari :";
   cin>>k;

//fungsi untuk pengurutan data
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if (A[i]>A[j])
{
tkr=A[i];
A[i]=A[j];
A[j]=tkr;
         }
      }
   }

//fungsi untuk pencarian data
tm=0;
right=n;
left=0;
while(right>=left)
{
middle=(right+left)/2;
if(A[middle]==k)
{
tm++;
}
if(A[middle]<k)
{
left=middle+1;
}
else
{
right=middle-1;
}
   }
if (tm>0)
   {
    cout<<"Data " << k << " yang dicari ada dalam array"<<endl;
   }
//output jika data tidak ditemukan
else
{
    cout<<"Data tidak ditemukan dalam array"<<endl;
   }
   getch();
}

Binary Search

#include<stdio.h>
#include<iostream.h>
#include<conio.h>
void main()
{
//deklarasi variabel
int A[10],index[10], i,j,k,n;

//bagian penginputan data
   cout<<"Masukkan jumlah data [Max 10] : ";
   cin>>n;

for(i=0;i<n;i++)
{
    cout<<"Masukkan Data ke - "<<(i+1)<<" = ";
      cin>>A[i];
}

//bagian untuk memasukkan data yang akan dicari ke dalam K
   cout<<"Masukkan data yang anda akan cari : ";
   cin>>k;

//bagian pencarian data
j=0;
for (i=0;i<n;i++)
{
if(A[i]==k)
{
index[j]=i;
j++;
}
   }

//jika data ditemukan dalam array
if (j>0)
{
cout<<"Data" <<k<< "yang dicari ada" <<j<< "buah"<<endl;
      cout<<"Data tersebut terdapat dalam index ke : ";
   for(i=0;i<j;i++)
{
         cout<<index[i]<<" ";
}
      cout<<endl;
}

//output data jika tidak ditemukan
else
{
      cout<<"Data tidak ditemukan dalam array"<<endl;;
}
  getch();
}

DAFTAR PUSTAKA