TUGAS UAS STRUKTUR DATA

►STRUKTUR DATA

Struktur data adalah cara menyimpan atau merepresentasikan data didalam komputer agar bisa dipakai secara efisien. Sedangkan data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol.

Secara garis besar type data dapat dikategorikan menjadi:
Type data sederhana.

Type data sederhana tunggal, misalnya Integer, real, boolean dan karakter.

Type data sederhana majemuk, misalnyaString

Struktur Data, meliputi:

Struktur data sederhana, misalnya array dan record.

Struktur data majemuk, yang terdiri dari:

Linier : Stack, Queue, sertaList dan Multilist
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 efisien dan sederhana.
Struktur data yang standar yang biasanya digunakan dibidang informatika adalah:
* List linier (Linked List) dan variasinya
* Multilist
* Stack (Tumpukan)
* Queue (Antrian)
* Tree ( Pohon)
* Graph ( Graf )

►ARRAY

Array (larik) merupakan tipe data tersetruktur dimana didalamnya terdiri dari komponen – komponen yang mempunyai tipe data yang sama. Didalam suatu array jumlah komponen banyaknya adalah tetap. Didalam suatu larik atau array setiap kompoenen ditunjukan oleh suatu index yang unik. Index dari setiap komponen array menunjukan urutan data atau identitas yang mewakili data yang ada didalamnya.
Logika sederhananya array itu bisa disamakan dengan dua orang dengan nama yang sama didalam suatu komunitas, untuk membedakan antara nama yang satu atau dengan nama yang lain maka diberikan initial tambahan untuk setiap nama.  Secara singkat, array adalah suatu tipe data terstruktur yang berupa sejumlah data sejenis (bertipe data sama) yang jumlahnya tetap dan diberi suatu nama tertentu.

Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-dimensi.

DEKLARASI

tipe_data nama_var_array [ukuran];

tipe_data                : menyatakan jenis tipe data elemen larik (int, char, float, dll)nama_var_array       : menyatakan nama variabel yang dipakai.

ukuran                    : menunjukkan jumlah maksimal elemen larik.

 Contoh :

Int nilai[6];

Didalam penulisan bahasa pemograman setiap penggunaan array harus dideklarsikan terlebih dahulu. Pendeklarasian array diawali dengan nama variabel array diikuti dengan indeks array yang dituliskan didalam tanda “[]” , diikuti dengan kata cadangan of dan tipe data yang dibutuhkan.

Bentuk Umum Penulisan

Tanda_pengenal : array [..tipe index ..] of tipe data;

Contoh :Var
A : array[1..4] of integer;
B : array[1..5] of string;
C: array[1..10] of real;

Keterangnan :
A,B,C merupakan tanda pengenal/ nama variabel dari array;
1..4 : merupakan tipe indek dari array, yang menunjukan banyaknya data yang mampu disimpan.
Integer : menunjukan bahwa data yang diinput berupa bilangan bulat.

Alokasi Penggunaan Array

Array Static (Static Array)

array static adalah model pendeklarasian array dimana tipe data yang digunakan mempunyai nilai yang tetap. Nilai yang digunakan untuk menentukan jangkauan pada umumnya bernilai integer. Array Static juga bisa disebut Array dengan deklarasi tipe indeks subrange integer.

Bentuk Umum

array[indexType1, …, indexTypen] of baseType

Keterangan = index type menunjukan tipe data ordinal yang menunjukan batasan atau elemen maksimul terhadap seberapa besar variabel tersebut menyimpan komponen.

Contoh

Var arrayku : array[1..5] of char

Atau juga

type
jangkauan=1..5;
var
nilai : array[jangkauan] of integer;

Array Dinamis (Dynamic arrays)

Larik atau array dinamis merupakan array yang tidak mempunyai suatu jangkauan atau ukuran yang tetap. Tetapi ketika program dijalankan maka memori untuk suatu array dinamis direalokasikan ketika kita menugaskan suatu nilai kepada array. Dynamic-Array jenis ditandai oleh konstruksi (menyangkut) format

Bentuk Umum

array of baseType

Contoh

var nilai: array of Real;

Dari deklarasi tersebut nilai yang merupakan deklarasi array belum memperoleh nilai yang tetap, tetapi hanya diberikan batasan sebagai tipe data real. Untuk mendeklarasikan array tersebut kita harus menempatkan array didalam suatu memori, caranya adalah dengan memanfaatkan fungsi dari perintah sellength.

Selllength(nilai,20)

Dari penggalan program tersebut nilai untuk array nilai tersebut mempunyai range sebanyak atau cakupan 20 untuk tipe data real, dengan indeex dimulai dari 0 sampai dengan 20.

INISIALISASI

 Menginisialisasi array sama dengan memberikan nilai awal array pada saat didefinisikan.

int nilai[6] = {8,7,5,6,4,3};­­­­­

 Contoh diatas berarti berarti anda memesan tempat di memori komputer sebanyak 6 tempat dengan indeks dari 0-5, dimana indeks ke-0 bernilai 8, ke-1 bernilai 7, dst, dan dimana semua elemennya bertipe data integer.

 PENGAKSESAN

 nama_var_array [indeks];

 Pengisian dan pengambilan nilai pada indeks tertentu dapat dilakukan dengan mengeset nilai atau menampilkan nilai pada indeks yang dimaksud. Pengaksesan elemen array dapat dilakukan berurutan atau random berdasarkan indeks tertentu secara langsung. 

►Contoh pengisian langsung saat deklarasi:

#include <stdio.h>

void main ()

{ int billy [] = {16, 2, 77, 40, 12071};

  int n, result=0;

  for ( n=0 ; n<5 ; n++ )

  {

    result += billy[n];

  }

  printf(“%d”,result);

} 

►Contoh pengaksesan dan pengisian langsung ke tiap elemen dari array:

#include <stdio.h>

#include <conio.h>

 void main ()

{

  int A [5]={20,9,1986,200,13},n,edit;

  clrscr();

  printf(“Data yang lama\n”);

  for (n=0;n<5;n++)

  {

    printf(“%i “,A[n]);

  }

  printf(“\nData yang baru : \n”);

  A[0]=4;

  A[1]=2;

  A[2]=1;

  A[3]=3;

  A[4]=5;

  for (n=0;n<5;n++)

  {

    printf(“%i “,A[n]);

  }

}

 ►Contoh penghapusan data(elemen) pada array:

#include <stdio.h>

#include <conio.h>

 void main ()

{ int A [5]={20,9,1986,200,13},n,hapus;

  clrscr();

  printf(“Data yang lama\n”);

  for (n=0;n<5;n++)

  {

    printf(“%i “,A[n]);

  }

  printf(“data yang ingin dihapus : “);

  scanf(“%i”,&hapus);

  printf(“\nData yang baru : \n”);

  for (n=hapus-1;n<5-1;n++)

  {

    A[n]=A[n+1];

  }

  for (n=0;n<4;n++)

  {

    printf(“%i “,A[n]);

  }

► LINK LIST

Linked list tidak lain adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi. Untuk memahami

linked list, terlebih dahulu anda harus tahu konsep pointer dan pengalokasian memori

Coba anda bayangkan apabila anda mendeklarasikan array dari record(array of record) sebanyak 10 elemen. Setiap kali program dijalankan, maka akan memesan memory sebesar 10x ukuran record. Itu merupakan suatu pemborosan walaupun kita hanya menggunakan 5 elemen record.

Maka dari itu, biasanya para programer lebih memilih menggunakan linked list dalam pemrograman. Linked list dibedakan atas 2 jenis yaitu singly linked list dan doubly linked list.

►Linked List : Definisi Node, Linked List, Single Linked List, Double Linked List, & Circular Linked List

a. Nodes

Self-referential objects (object yang mereferensikan dirinya sendiri) yang disebutnodes, yang dihubungkan dengan links, membentuk kata “linked” list.

b. Linked List ( LL )

Adalah koleksi data item yang tersusun dalam sebuah barisan  secara linear, dengan penyisipan dan pemindahan dapat dilakukan dalam semua tempat di LL tersebut.

c. Single Linked List

Adalah sebuah LL yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode LL, suatu daftar isi yang saling berhubungan.

Ilustrasi single LL:

Pada gambar di atas, data terletak pada sebuah lokasi dalam sebuah memory, tempat yang disediakan memory untuk menyimpan data disebut node ? simpul, setiap node memiliki pointer ( penunjuk ) yang menunjuk ke node berikutnya sehingga terbentuk suatu untaian yang disebut single LL.

Bila dalam single LL pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.

d. Double Linked List

Dalam double LL ( Linked List berpointer ganda ) dapat mengatasi kelemahan-kelemahan single LL tersebut.

Ilustrasi double LL:

e. Circular Linked List

Adalah double / single LL yang simpul terakhirnya menunjuk ke simpul awal, dan simpul awalnya menunjuk ke simpul akhir, atau dapat disebut LL yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal dan titik akhir saling bersebelahan jika LL tersebut masih kosong, ilustrasi Circular LL :

Dalam ilmu komputer , daftar link (atau lebih jelas, "-linked list tunggal") adalah sebuah struktur data yang terdiri dari urutan node yang masing-masing berisi referensi (yaitu, link) ke node berikutnya dalam urutan tersebut.

Sebuah node linked list yang berisi dua bidang: nilai integer dan link ke node berikutnya

Linked list adalah salah satu struktur data sederhana dan paling umum. Mereka dapat digunakan untuk melaksanakan beberapa umum lainnya struktur data abstrak , termasuk tumpukan , antrian , array asosiatif , dan ekspresi simbolik , meskipun tidak jarang untuk menerapkan struktur data lainnya secara langsung tanpa menggunakan daftar sebagai dasar pelaksanaan.

Manfaat utama dari sebuah linked list melalui konvensional array adalah bahwa daftar elemen dengan mudah dapat ditambahkan atau dihapus tanpa realokasi atau reorganisasi dari struktur keseluruhan karena item data tidak perlu disimpan contiguously dalam memori atau pada disk. daftar Linked memungkinkan penyisipan dan penghapusan node pada setiap titik dalam daftar, dan dapat melakukannya dengan sejumlah konstan operasi jika link sebelumnya untuk link yang ditambahkan atau dihapus dipertahankan selama pencarian daftar.

Di sisi lain, linked list sederhana dengan sendirinya tidak memungkinkan akses acak ke data lain dari node pertama data, atau segala bentuk pengindeksan yang efisien. Dengan demikian, banyak dasar operasi - seperti mendapatkan node terakhir dari daftar (dengan asumsi bahwa node terakhir tidak dipertahankan sebagai referensi node terpisah dalam struktur daftar), atau menemukan sebuah node yang berisi acuan tertentu, atau menemukan tempat dimana node baru harus dimasukkan - mungkin memerlukan pemindaian sebagian besar atau semua elemen daftar.

►STACK

STACK adalah salah satu list linear dalam struktur data yang digunakan untuk menyimpan dan mengambil data dengan konsep LIFO (Last In First Out). Dimana dalam stack ini kumpulan data yang masuk diletakkan di atas data yang lain. Dan berdasar konsep LIFO maka data yang terakhir kali disimpan dalam stack akan menjadi data yang pertama kali diambil. Dalam prosesnya, untuk memasukkan sebuah data ke dalam stack atau dengan kata lain ke bagian atas dari sebuah tumpukan digunakan perintah push. Dan untuk memindahkan data dari tempat tersebut digunakan perintah pop. Sedangkan dalam penyajiannya, stack bisa memakai array atau linked list.

Dari gambar di atas bisa dilihat bahwa data di dalam stack hanya bisa dimasukkan atau diambil melalui bagian ujung saja/top.

Operasi-operasi dasar pada stack :

a. Cek Stack kosong (Isempty)

Fungsi yang melakukan pengecekan apakah stack dalam kondisi kosong.
public int isempty()

if(posisi==0)

System.out.println(“Data Kosong”);

return 1;

else

System.out.println(“Data ada”);

return 0;

b. Cek Stack penuh (full)

Fungsi yang melakukan pengecekan apakah stack dalam kondisi penuh atau tidak.

public int full()

if(posisi==MAX)

System.out.println(”Stack Penuh”);

return 0;

else

return 1;

c. Operasi Push

Operasi push dalam stack adalah operasi yang memasukkan elemen yang akan diletakkan pada posisi teratas dari tumpukan.

public void push (int data)

if(posisi<MAX_STACK)

isistack[++posisi] = data;

d. Operasi Pop

Operasi pop dalam stack adalah operasi untuk mengambil/menghapus elemen yang terletak pada posisi paling atas dari sebuah tumpukan.

public void pop()

int y=0;

if(posisi != 0)

isistack[posisi–]=y;

e. Cek posisi Teratas (Peek)
Operasi peek digunakan untuk mengecek posisi teratas dalam stack.

public void peek()

System.out.print(“Posisi Atas= “);

if(posisi != 0)

System.out.print(isistack[posisi]);

System.out.println();

Penerapan stack :

Stack digunakan untuk menuliskan ungkapan menggunakan notasi tertentu (Notasi Polish). Biasanya ungkapan yang digunakan adalah ungkapan numeris. Sebagai contoh ungkapan (A + B)*(C – D) apabila ditulis dengan menggunakan notasi Polish menjadi * + A B – C D.

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

}