struktur data
Struktur data adalah cara menyimpan atau merepresentasikan data didalam komputer agar bisa dipakai secara efesien. Sedangkan data dalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol.
Struktur data yang biasanya digunakan dibidang informatika meliputi :
Struktur data sederhana, misalnya array dan record.
Struktur data majemuk yang terdiri dari :
Linier : Stack, Queue, Linked List ,
Non-Linier : Pohon biner dan Graph
Pemakaian struktur data yang tepat didalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efesien dan sederhana.
Di dalam mata kuliah Struktur Data ini akan dijelaskan struktur data yang sering digunakan dalam pemrograman seperti pointer, linked list, stack dan queue dengan menggunakan bahasa pemrograman C / C++ sebagai pengantarnya.
A. ARRAY
Array adalah kumpulandarinilai-nilai data bertipe sama dalam urutan tertentu yang menggunakan sebuah nama yang sama Nilai-nilai data disuatu array disebut dengan elemen-elemen array Letak urutan dari elemen-elemen array di tunjukkan oleh suatu subscript atau indek.
Aray Berdimensi Satu
bentuk umum : tipe_data nama_var[ukuran]
contoh : float niali_tes[5];
cara akses :
2. bentuk umum : tipe nama_arrat[baris][kolom];
contoh :
Mendeklarasikan Aray
– Suatu aray berdimensi satu dideklarasikan dalam bentuk umum berupa :
Tipe_data nama_var[ukuran];
– Tipe_data : untuk menyatakan tipe dari elemen arrat, misalnya int, char, float.
Nama_var: nama variable array
Ukuran : untuk menyatakan jumlah maksimal elemen array.
– Contoh pendeklarasikan array :
Float nilai [5];
Menyatakan bahwa variable nilai bertipe array of float dan memiliki 5 elemen bertipe float.
Mengakses Elemen Array
– Pada C, data array akan disimpan dalam memori yang berurutan.
– Elemen pertama mempunyai indeks bernilai 0.
– Jika nilai dideklarasikan sebagai array of float dengan 5 elemen, maka elemen pertama memiliki indeks sama dengan 0, dan elemen terakhir memiliki indeks 4.
Inialisasi Array
– Sebuah array dapat diinisialisasi sekaligus pada saat di deklarasikan.
– Untuk mendeklarasikan array, nilai – nilai yang di inisialisasikan dituliskan diantara kurung kurawal ( {} ) yang dipisahkan dengan koma.
Array Berdimensi Dua
Array berdimensi satu dapat disimpan pada sebuah array berdimensi dua. Pendeklarasian array berdimensi dua adalah sebagai berikut :
int data_lulus[4][3];
Nilai 4 untuk menyatakan banyaknya baris dan 3 menyatakan banyaknya kolom. untuk memudahkan pemahaman tentang array berdimensi dua.
80 540 1032
15 83 301
8 12 15
10 129 257
int data_lulus[4][3];
Array berdimensi dua Sama halnya pada array berdimensi satu, data array aka ditempatkan pada
memori yang berurutan.
Mengakses Elemen Array Berdimensi Dua
Array seperti data_lulus dapat diakses dalam bentuk data_lulus[indeks pertama, indeks kedua :
(1) data_lulus[0][1] = 540;
merupakan instruksi untuk memberikan nilai 540 ke array data_lulus untuk
indeks pertama = 0 dan indeks kedua bernilai 1.
(2) printf(“%d”,data_lulus[2][0]);
merupakan perintah untuk menampilkan elemen yang memiliki indeks pertama =
2 dan indeks kedua = 0.
Array Berdimensi Banyak
C memungkinkan untuk membuat array yang dimensinya lebih dari dua. Bentuk umum pendeklarasian array berdimensi banyak :
tipe nama_var[ukuran 1][ukuran2}…[ukuranN];
sebagai contoh :
int data_huruf[2][8][8];
merupakan pendeklarasian array data_huruf sebagai array berdimensi tiga. Sama halnya dengan array berdimensi satu atau dua, array berdimensi banyak juga bisa diinisialisasi.
contoh soal :
1. Mencari sebuah karakter inputan dalam array yang telah di deklarasi .
source code :
#include <stdio.h>
main()
{
int i,x;
char huruf[20]={‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’j’,’k’,’l’,’m’,’n’,’o’,’p’,’q’,’r’,’s’,’t’}, a;
printf(“Masukan Sebuah karakter = \n”);
scanf(“%c”,&a);
for(i=0;i<20;i++)
if(huruf[i]==a)
x=1;
if (x==1)
printf(“karakter tersebut ada dalam aray\n”);
else
printf(“karakter tersebut tidak ada dalam array\n”);
}
2. program untuk mencocokan apakah sebuah karakter yang diinputkan dari keyboard ada dalam array yang telah dideklarasikan.
source code :
#include <stdio.h>
main()
{
int i,x;
char huruf[20]={‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’j’,’k’,’l’,’m’,’n’,’o’,’p’,’q’,’r’,’s’,’t’}, a;
printf(“Masukan Sebuah karakter = \n”);
scanf(“%c”,&a);
for(i=0;i<20;i++)
if(huruf[i]==a)
x=1;
if (x==1)
printf(“karakter tersebut ada dalam aray\n”);
else
printf(“karakter tersebut tidak ada dalam array\n”);
}
B. LINK LIST ( CIRCULAR+NON, SINGLE+DOUBLE )
Linked List saling terhubung dengan bantuan variabel pointer Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.
Single : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL.
Linked List : artinya node-node tersebut saling terhubung satu sama lain. Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.
Jenis Single LinkList
·Single linked list dengan HEAD
·Single linked list dengan HEAD dan TAIL
Deklarasi Single LinkList
Model struktur dari linked list tersebut dalam Java adalah sebagai berikut:
public class Node {
private int data; /* integer data diisikan dalam node */
Node nextNode; /* node selanjutnya dalam list */
Node(){
this.data = 0;
this.nextNode = null;
}
· Pembuatan Single Linked List
Keyword new gunanya untuk mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL.
public void buatNode (int dt) {
Node nodebaru = new Node();
nodebaru.data = dt;
nodebaru.next = pointer;
pointer = nodebaru;
}
· Penambahan data dari depan
Pada prinsipnya adalah mengkaitkan node baru dengan head, kemudian head akan menunju pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.
public boolean sisip (int dt1, int dt2) {
Node n = pointer;
while ((n!=null) && (n.data!= dt2))
n = n.next;
if (n==null) return false;
Node nn = new Node ();
nn.data=dt1;
nn.next=n.next;
n.next=nn;
return true;
}
· Menghapus data dari depan
Function di atas akan menghapus data terdepan (pertama) yang ditunjuk oleh head pada linked list, Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer. Sebelum data terdepan dihapus, head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan menjadi head baru (data terdepan yang baru). Jika head masih NULL maka berarti data masih kosong!
public int hapusDiDepan () {
Node hapus = pointer;
pointer = pointer.next;
return hapus.data;
}
C. STACK
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.
STACK ATAU TUMPUKAN PADA MATAKULIAH STRUKTUR DATA
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).
karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan.
Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo juga.
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
INISIALISASI STACK
Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah KOSONG.!
Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang. Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH!
Ilustrasi stack pada saat inisialisasi
Fungsi IsFull
Untuk memeriksa apakah stack sudah penuh?
Dengan cara memeriksa top of stack, jika sudah sama dengan MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full
Ilustrasi
Contoh Rumus sederhana 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;
}
D. 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).
Pada Stack atau tumpukan menggunakan prinsip“Masuk terakhir keluar pertama”atau LIFO (Last In First Out), Maka pada 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.
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
1. tambah(menambah item pada belakang antrian)
2. hapus (menghapus elemen depan dari antrian)
3. 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
E. SORTING
Sorting (pengurutan) adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu.
Masalah pengurutan dapat ditulis menjadi 2 jenis, yaitu:
1. Ascending (Tersusun / terurut secara menaik)
Diberikan larik L dengan n elemen yang sudah terdefinisi elemen-elemennya.
Urutan larik tersebut sehingga tersusun secara menaik (dari urutan nilai terkecil ke urutan nilai terbesar), yaitu: L[0] ≤ L[1] ≤ L[2] ≤ ... ≤ L[n-1]
2. Descending (Tersusun / terurut secara menurun)
Diberikan larik L dengan n elemen yang sudah terdefinisi elemen-elemennya.
Urutan larik tersebut sehingga tersusun secara menurun (dari urutan nilai terbesar ke urutan nilai terkecil), yaitu: L[0] ≥ L[1] ≥ L[2] ≥ ... ≥ L[n-1]
Contoh data yang belum terurut : 70, 12, 45, 10, 11, 60, 13, 33, 50
Ascending = 10, 11, 12, 13, 33, 45, 50, 60, 70
Descending = 70, 60, 50, 45, 33, 13, 12, 11, 10
*Pengurutan dikatakan STABIL, jika dua atau lebih data yang sama (identik) tetap pada urutan yang sama setelah pengurutan. Misalnya didalam sekelompok data integer berikut terdapat 3 buah nilai 12 (diberi tanda petik ', '', ''' untuk mengidentifikasi urutannya.
Contoh : 70, 12', 45, 10, 12'', 60, 12''', 33, 50
Dikatakan STABIL jika hasil pengurutannya menjadi : 10, 12', 12'', 12''', 33, 45, 50, 60, 70
Dikatakan TIDAK STABIL jika hasil pengurutannya menjadi : 10, 12'', 12', 12''', 33, 45, 50, 60, 70
ALGORITMA SORTING (PENGURUTAN)
-----------------------------------------------------------
Macam-macam algoritma sorting (pengurutan), yaitu:
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Heap Sort
5. Shell Sort
6. Quick Sort
7. Merge Sort
8. Radix Sort
9. Tree Sort
1. BUBBLE SORT
Diberi nama "bubble" karena proses pengurutan secara berangsur-angsur bergerak / berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelar bersoda.
Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.
- Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar (untuk pengurutan ascending).
- Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar (untuk pengurutan descending).
Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau dari kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya.
Bubble Sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapainya perurutan yang telah diinginkan.
Algoritma Bubble Sort beroperasi sebagai berikut :
1. Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritma menghasilkan data dengan urutan ascending (A-Z), kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z), data ke-i < data ke-i+1.
2. Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dengan 2; 2 dengan 3; 3 dengan 4; 4 dengan 5 … ; n-1 dengan n.
3. Selesai satu proses, yang dimana kita sudah selesai membandingkan antara (n-1) dengan n. Setelah selesai satu proses, kita lanjutkan lagi proses berikutnya sesuai dengan aturan ke-1. Mulai dari data ke-1 dengan data ke-2, dan seterusnya.
4. Proses akan berhenti jika tidak ada pertukaran dalam satu proses.
Contoh Program Bubble Sort C++ (Ascending):
#include <iostream>
#include <conio.h>
using namespace std;
int data[10],data2[10];
int n;
void swap(int a,int b)
{
int swap;
swap = data[b];
data[b] = data[a];
data[a] = swap;
}
void Input()
{
cout<<"Masukkan jumlah data yang diinginkan : ";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"Masukkan data ke-"<<(i+1)<<" : ";
cin>>data[i];
data2[i] = data[i];
}
cout<<endl;
}
void Tampil()
{
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
}
void Bubble_Sort()
{
for(int i=1;i<n;i++)
{
cout<<"Proses ke-"<<(i+1)<<" : ";
for(int j=n-1;j>=i;j--)
{
if(data[j]<data[j-1]) swap(j,j-1);
}
Tampil();
}
cout<<endl;
}
int main()
{
cout<<"------------------------------------------"<<endl;
cout<<"BUBBLE SORT C++"<<endl;
cout<<"------------------------------------------"<<endl<<endl;
Input();
cout<<"Bubble Sort : ";
Tampil();
Bubble_Sort();
cout<<"Hasil Pengurutan Bubble Sort : ";
Tampil();
cout<<"------------------------------------------"<<endl;
getch();
}
F. 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).
Berikut adalah metode-metode yang digunakan dalam Searching
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.
Contoh Program :
#include <iostream>
using namespace std;
main() {
int data[8] = {8,10,6,-2,11,7,1,100};
int cari;
int tanda=0;
cout<<"masukkan data yang ingin dicari = "; cin>>cari;
for(int i=0;i<8;i++){
if(data[i] == cari) tanda=1;
}
if(tanda==1) cout<<"Data ada!\n";
else cout<<"Data tidak ada!\n";
}
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.
Contoh Program:
#include <iostream>
using namespace std;
main() {
int data[7] = {10,13,17,34,58,67,99};
int N = 7
int kiri=0,kanan=N-1,tengah,cari;
int tanda=0;
cout<<”Masukan data yang di cari?”;cin>>cari;
while((kiri<=kanan)&&(tanda==0)) {
tengah=(kiri+kanan)/2;
cout<<”data tengah = ”<<tengah<<endl;
if(data[tengah]==cari) tanda=1;
else if(cari < data[tengah]) {
cout<<”cari di kiri\n”;
kanan=tengah-1;
}
else {
kiri=tengah+1;
cout<<”cari di kanan\n”;
}
if(tanda==1) cout<<”Data ada\n”;
else cout<<”Data tidak ada\n”;
}
}
3. Interpolation Search
Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu. Teknik searching ini dilakukan dengan perkiraan letak data. Contoh ilustrasi: jika kita hendak mencari suatu kata di dalam kamus telepon, misal yang berawalan dengan huruf J, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada 1/3 atau 1/4 dari tebal kamus.
Rumus posisi relatif kunci pencarian dihitung dengan rumus:
- Jika data[posisi] > data yg dicari, high = pos – 1
- Jika data[posisi] < data yg dicari, low = pos + 1 Contoh program:
#include <iostream>
#include <math.h>
using namespace std;
main() {
int data[7] = {10,13,17,34,58,67,99};
int low,high,cari,posisi;
float posisi1;
int N = 7,tanda=0;
low=0,high=N-1;
cout<<”Masukan data yang di cari?”;cin>>cari;
do {
posisi1 = (cari-data[low])/(data[high]-data[low])*(high-low)+low;
posisi = floor(posisi1); //pembulatan ke bawah
if(data[posisi]==cari) {
tanda =1;
break;
}
if(data[posisi]>cari) high=posisi-1;
else if (data[posisi]<cari) low=posisi+1
}
while (cari>=data[low]&&cari<=data[high]);
if(tanda==1) cout<<”Data ditemukan\n”;
else cout<<”Data tidak ada\n”;
}
G. TREE
Tree adalah Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon. Struktur pohon adalah suatu cara merpresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah. Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.
Deklarasi Pohon
Jika kita memperhatikan setiap simpul dalam pohon biner, kita bisa menyusun struktur data yang tepat dari simpul-simpul tersebut. Kita dapat melihat bahwa dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk ke cabang kiri dan cabang kanan, dan informasi yang akan disimpan dalamsimpul tersebut. Dengan memperhatikan hal ini, simpul dalam pohon biner disajikan sebagai berikut:
Sesuai dengan gambar 7.1, maka deklarasi list yang sesuai adalah:
typedef char TypeInfo;
typedef struct Simpul *Tree;
struct Simpul {
TypeInfo Info;
tree Kiri, /* cabang kiri */
Kanan; /* cabang kanan */
};
ISTILAH DALAM TREE
JENIS-JENIS TREE
BINARY TREE
Tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua sub pohon dan kedua sub pohon harus terpisah.
Kelebihan struktur Binary Tree :
Mudah dalam penyusunan algoritma sorting
Searching data relatif cepat
Fleksibel dalam penambahan dan penghapusan data
KUNJUNGAN PADA POHON BINER
Sebuah pohon biner memiliki operasi traversal yaitu suatu kunjungan pada suatu simpul tepat satu kali. Dengan melakukan kunjungan lengkap kita akan memperoleh urutan informasi secara linier yang tersinpan di dalam pohon biner.
Terdapat tiga jenis kunjungan pada pohon biner, yaitu :
PREORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
– Cetak isi simpul yang dikunjungi.
– Kunjungi cabang kiri.
– Kunjungi cabang kanan.
Prosedur untuk melakukan traversal secara PREORDER adalah sebagai berikut:
INORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
– Kunjungi cabang kiri.
– Cetak isi simpul yang dikunjungi.
– Kunjungi cabang kanan.
Prosedur untuk melakukan traversal secara INORDER adalah sebagai berikut:
POSTORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
– Kunjungi cabang kiri.
– Kunjungi cabang kanan.
– Cetak isi simpul yang dikunjungi
BERIKUT MERUPAKN CONTOH PROGRAMNYA
#include<stdio.h>//header file
#include<conio.h>
/* Deklarasi struct */
typedef struct Node{
int data; //data pada tree
Node *kiri; //penunjuk node anak kiri
Node *kanan; //penunjuk node anak kanan
};
/* Fungsi untuk memasukkan data ke dalam tree */
void tambah(Node **root, int databaru){
if((*root) == NULL){ //jika pohon/subpohon masih kosong
Node *baru;//node “baru” dibentuk…
baru = new Node;//berdasarkan struct “Node”
baru->data = databaru; //data node baru diisi oleh variabel databaru
baru->kiri = NULL;//penunjuk kiri node baru masih kosong
baru->kanan = NULL;//penunjuk kanan node baru masih kosong
(*root) = baru; //node pohon (root) diletakkan pada node baru
(*root)->kiri = NULL;//penunjuk kiri node root masih kosong
(*root)->kanan = NULL; //penunjuk kanan node root masih kosong
printf(“Data bertambah!”);
}
else if(databaru < (*root)->data)//jika databaru kurang dari data node root…
tambah(&(*root)->kiri, databaru);//tambahkan databaru pada subpohon kiri
else if(databaru > (*root)->data)//jika databaru lebih dari data node root…
tambah(&(*root)->kanan, databaru); //tambahkan databaru pada subpohon kanan
else if(databaru == (*root)->data)//jika databaru sama dengan data node root
printf(“Data sudah ada!”);//databaru tidak dapat ditambahkan pada tree
}
/* Fungsi untuk menampilkan data secara pre-order
(data ditampilkan dari node induk, node anak kiri, lalu node anak kanan)
*/
void preOrder(Node *root){
if(root != NULL){//jika pohon/subpohon tidak kosong
printf(“%d “, root->data);//menampilkan data node yang dikunjungi
preOrder(root->kiri);//mengunjungi node anak kiri
preOrder(root->kanan); //mengunjungi node anak kanan
}
}
/* Fungsi untuk menampilkan data secara in-order
(data ditampilkan dari node anak kiri, node induk, lalu node anak kanan)
*/
void inOrder(Node *root){
if(root != NULL){//jika pohon/subpohon tidak kosong…
inOrder(root->kiri);//mengunjungi node anak kiri
printf(“%d “, root->data);//menampilkan data node yang dikunjungi
inOrder(root->kanan);//mengunjungi node anak kanan
}
}
/* Fungsi untuk menampilkan data secara post-order
(data ditampilkan dari node anak kiri, node anak kanan, lalu node induk)
*/
void postOrder(Node *root){
if(root != NULL){//jika pohon/subpohon tidak kosong
postOrder(root->kiri); //mengunjungi node anak kiri
postOrder(root->kanan);//mengunjungi node anak kanan
printf(“%d “, root->data); //menampilkan data node yang dikunjungi
}
}
main(){
int pil, c;
Node *pohon, *t;
pohon = NULL;
do{
int data;
printf(“MENU\n”);
printf(“1. Tambah\n”);
printf(“2. Lihat Pre-Order\n”);
printf(“3. Lihat In-Order\n”);
printf(“4. Lihat Post-Order\n”);
printf(“5. Exit\n”);
printf(“Pilihan : “); scanf(“%d”, &pil);
switch(pil){
case 1 :
printf(“Data baru : “);
scanf(“%d”, &data);
tambah(&pohon, data);
break;
case 2 :
if(pohon != NULL)
preOrder(pohon);
else
printf(“Masih kosong!”);
break;
case 3 :
if(pohon != NULL)
inOrder(pohon);
else
printf(“Masih kosong!”);
break;
case 4 :
if(pohon != NULL)
postOrder(pohon);
else
printf(“Masih kosong!”);
break;
}
getch();
printf(“\n”);
}
while(pil != 5);
}
Sumber : wikipedia dan lain-lainnya...
