Pengertian dan Penjelasan Struktur Data, Stack, Queue, Sorting (Bubble Sort & Selection Sort), Searching, dan Tree
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 )
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
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
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.
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
SORTING
Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif. Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan secara ascending demi kenyamanan dalam penelusuran data. Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna.
1.Selection Sort (Ascending): Pengurutan dilakukan dengan memilih elemen terbesar dan menempatkan pada posisinya, kemudian mencari element terbesar berikutnya dan menempatkan pada tempatnya, dan seterusnya.
Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah :
1. Mencari data terkecil dari data pertama sampai data terakhir, kemunian di tukar posisinya dengan data pertama.
2. mencari data terkecil dari data kedua sampai data terakhir, kemudian di tukar dengan posisinya dengan data kedua.
3. mencari data terkecil dari data ketiga sampai data terakhir, kemudian di tukar posisinya dengan data ketiga
4. dan seterusnya sampai semua data turut naik. apabila terdapat n buah data yang akan di urutkan, maka membutukan (n - 1) langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu di urutkan karena hanya tinggal satu satunya.
2. Bubble Sort Konsep Buble Sort Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung. Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.
Searching
Pencarian (Searching) merupakan proses yang fundamental dalam pemrograman, guna menemukan data (nilai) tertentu di dalam sekumpulan data yang bertipe sama. Fungsi pencarian itu sendiri adalah untuk memvalidasi (mencocokkan) data.
2. 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 (Binary Search)
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.
Contoh implementasi searching
#include
void main()
{
clrscr();
int bil[5];
int jml_bil,nilai_max;
int i;
/* input data */
cout<<"masukkan jumlah bilangan kurang dari 5 : ";cin>>jml_bil;
for(i=0;i {
cout<<"bilangan ke"<>bil[i];
}
/* menentukan nilai max */
nilai_max=bil[0];
for(i=0;i {
if (bil[i]>nilai_max)
{
nilai_max=bil[i];
}
}
/* mencetak nilai max */
cout<<"nilai maksimum : "< cout<
getch();
}
Algoritma dari
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 :
1. Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
2. Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.
Pencarian (Searching) merupakan proses yang fundamental dalam pemrograman, guna menemukan data (nilai) tertentu di dalam sekumpulan data yang bertipe sama. Fungsi pencarian itu sendiri adalah untuk memvalidasi (mencocokkan) data.
2. 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 (Binary Search)
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.
Contoh implementasi searching
#include
void main()
{
clrscr();
int bil[5];
int jml_bil,nilai_max;
int i;
/* input data */
cout<<"masukkan jumlah bilangan kurang dari 5 : ";cin>>jml_bil;
for(i=0;i
cout<<"bilangan ke"<>bil[i];
}
/* menentukan nilai max */
nilai_max=bil[0];
for(i=0;i
if (bil[i]>nilai_max)
{
nilai_max=bil[i];
}
}
/* mencetak nilai max */
cout<<"nilai maksimum : "<
getch();
}
Algoritma dari
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 :
1. Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
2. Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.
TREE (struktur data)
Dalam ilmu komputer, sebuah Pohon adalah suatu struktur data yang digunakan secara luas yang menyerupai struktur pohon dengan sejumlah simpul yang terhubung.
Simpul (node)
Sebuah Simpul dapat mengandung sebuah nilai atau suatu kondisi atau menggambarkan sebuah struktur data terpisah atau sebuah bagian pohon itu sendiri. Setiap simpul dalam sebuah pohon memiliki nol atau lebih simpul anak (child nodes), yang berada dibawahnya dalam pohon (menurut perjanjian, pohon berkembang ke bawah, tidak seperti yang dilakukannya di alam). Sebuah simpul yang memiliki anak dinamakan simpul ayah (parent node) atau simpul leluhur(ancestor node) atau superior. Sebuah simpul paling banyak memiliki satu ayah. Tinggi dari pohon adalah panjang maksimal jalan ke sebuah daun dari simpul tersebut. Tinggi dari akar adalah tinggi dari pohon. Kedalaman dari sebuah simpul adalah panjang jalan ke akarnya dari simpul tersebut.
Daun (Leaf nodes)
Semua simpul yang berada pada tingkat terendah dari pohon dinamakan daun (leaf node). Sejak mereka terletak pada tingkat paling bawah, mereka tidak memiliki anak satupun. Seringkali, daun merupakan simpul terjauh dari akar. Dalam teori grafik, sebuah daun adalah sebuah sudut dengan tingkat 1 selain akar (kecuali jika pohonnya hanya memiliki satu sudut; maka akarnya adalah daunnya juga). Setiap pohon memiliki setidaknya satu daun.
Dalam pohon berdasarkan genetic programing sebuah daun (juga dibilang terminal) adalah bagian terluar dari sebuah program pohon. Jika dibandingkan dengan fungsinya atau simpul dalam, daun tidak memiliki argumen. Di banyak kasus dalam daun-GP input ke programnya.
Simpul dalam (Internal nodes)
Sebuah simpul dalam adalah semua simpul dari pohon yang memiliki anak dan bukan merupakan daun. Beberapa pohon hanya menyimpan data di dalam simpul dalam, meskipun ini memengaruhi dinamika penyimpanan data dalam pohon. Sebegai contoh, dengan daun yang kosong, seseorang dapat menyimpan sebuah pohon kosong dengan satu daun. Bagaimanapun juga dengan daun yang dapat menyimpan data, tidak dimungkinkan untuk menyimpan pohon kosong kecuali jika seseorang memberikan beberapa jenis penanda data di daun yang menandakan bahwa daun tersebut seharusnya kosong (dengan demikian pohon itu seharusnya kosong juga).
Sebaliknya, beberapa pohon hanya menyimpan data dalam daun, dan menggunakan simpul dalam untuk menampung metadata yang lain, seperti jarak nilai dalam sub pohon yang berakar pada simpul tersebut. Jenis pohon ini berguna untuk jarak yang meragukan.
Sub pohon (Subtrees)
Sebuah sub pohon adalah suatu bagian dari pohon struktur data yang dapat dilihat sebagai sebuah pohon lain yang berdiri sendiri. Simpul apapun dalam pohonP, bersama dengan seluruh simpul dibawahnya, membentuk sebuah sub pohon dari P. Sub pohon yang terhubung dengan akar merupakan keseluruhan pohon tersebut. Sub pohon yang terhubung dengan simpul lain manapun dinamakan sub pohon asli (proper subtree)
Penyusunan pohon
Terdapat dua jenis pohon. Sebuah pohon tidak terurut (unordered tree) adalah sebuah pohon dalam arti struktural semata-mata, yang dapat dikatakan memberikan sebuah simpul yang tidak memiliki susunan untuk anak dari simpul tersebut. Sebuah pohon dengan suatu susunan ditentukan, sebagai contoh dengan mengisi bilangan asli berbeda ke setiap anak dari simpul tersebut, dinamakan sebuah pohon terurut (ordered tree), dan struktur data yang dibangun di dalamnya dinamakan pohon terurut struktur data (ordered tree data structures). Sejauh ini pohon terurut merupakan bentuk umum dari pohon struktur data. Pohon biner terurut merupakan suatu jenis dari pohon terurut.
Hutan
Sebuah hutan adalah sebuah himpunan yang terdiri dari pohon terurut. Lintasan inorder, preorder, dan postorder didefinisikan secara rekursif untuk hutan.
- inorder
- lewati inorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
- kunjungi akar dari pohon pertama.
- lewati inorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
- preorder
- kunjungi akar dari pohon pertama.
- lewati preorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
- lewati preorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
- postorder
- lewati postorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
- lewati postorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
- kunjungi akar dari pohon pertama.
Penggambaran pohon
Ada banyak cara untuk menggambarkan pohon; pada umumnya penggambaran mewakili simpul sebagai rekor yang dialokasikan pada heap (bedakan dengan heap struktur data) yang mengacu pada anaknya, ayahnya, atau keduanya, atau seperti data materi dalam array, dengan hubungan diantaranya ditentukan oleh posisi mereka dalam array (contoh binary heap)
Pohon sebagai grafik
Dalam teori grafik, sebuah pohon adalah sebuah grafik asiklis yang terhubung. Pohon yang berakar merupakan sebuah grafik dengan sudut tunggal di luar sebagai akar. Dalam kasus ini, dua sudut apapun yang terhubung dengan sebuah sisi mewarisi hubungan orang tua dan anak. Sebuah grafik asiklis dengan bermacam-macam komponen yang terhubung atau himpunan dari pohon-pohon yang berakar kadang-kadang dipanggil hutan
Metode traversal
Melangkah melalui materi dari pohon, dengan arti dari hubungan antara orang tua dan anak, dinamakan menelusuri pohon, dan tindakannya adalah sebuahjalan dari pohon. Seringkali, sebuah operasi mungkin dapat dilakukan sebagai penunjuk ysng mengacu pada simpul khusus. Sebuah penelusuran dimana setiap simpul ayah dikunjungi sebelum anaknya dinamakan pre-order walk; sebuah penelusuran dimana anaknya dikunjungi sebelum ayahnya masing-masing dinamakanpost-order walk.