Review Materi Data Structure

Struktur Data  


Struktur data atau biasa  di sebut Data Structure 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.




Struktur data sederhana  

Contohnya : array dan record.


Struktur data majemuk

Pada Struktur majemuk pun di bagi menjadi 2, yaitu:

➤Linier : Stack, Queue, sertaList dan Multilist

➤Non Linier : Pohon Biner dan Graph



Berikut merupakan tipe tipe Struktur data sederhana yang sering di gunakan dalam pemakaian sehari hari :

➤Multilist
➤Stack
➤Queue
➤Tree
➤Graph

MultiList

MultiList adalah suatu struktur yang terdiri dari beberapa buah list berkaitan yang saling berkaitan 

Setiap Struktur list berkait berbeda karakteristiknya dengan list berkait yang lain.

STACK

Stack adalah sebagai tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain, koleksi dari objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja


Stack pada Struktur Data dapat diilustrasikan dengan dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N kotak.

QUQUE

Quque 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, contohnya : 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 serempa

TREE


tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.


GRAPH

Graph adalah salah satu jenis struktur data yang terdiri dari titik(vertex) dan garis(edge), dimana dalam graf tersebut, vertex vertex yang ada dihubungkan oleh edge, hingga menjadi suatu kesatuan yang disebut graf. Sebagai contoh dari pemodelan graf adalah peta kota kota, dimana kota disini sebagai vertex dan jalur yang menghubungkannya berlaku sebagai edge



 Linked List

Linked list atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memliki field yang menyimoan alamat/ referensi dari record selanjutnya (dalam urutan) elemen data yang dihubungkan dengan link pada linked list disebut Node. Biasanya didalam suatu lnked list, terdapat istilah head and tail.

       
Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

             
Tail adalah element yang berada pada posisis terakhir dalam suatu linked list



Single Linked List


Single Linked List merupakan suatu linked list yang hanya memiliki satu varuabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya.Biasanya field pada tail menunjuk ke NULL







 Double Linked List


Double Linked List Merupakan suatau linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke  NULL :







Circular Linked List


Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head(node pertama).Jadi tidak ada pointer yang menunjuk NULL ada 2 jenis Circular Linked List Yaitu:

  
Circular Single Linked List
 Circular Double Linked List



Multiple Linked List

Multi Linked List Merupakan Suatu Linked List yang Memiliki Lebih dari 2 buat variabel pointer








Hashing Table

adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.




Contoh perintah pada Hashing Table


➤ insert:             diberikan sebuah key dan nilai, insert nilai dalam tabel
➤ find:                diberikan sebuah key, temukan nilai yang berhubungan dengan key
➤ remove:          diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
➤ getIterator:     mengambalikan iterator,yang memeriksa nilai satu demi satu



Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

Cara untuk mendapatkan field kunci ini sangatlah beragam, namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function dan menghasilkan indeks lokasi record dalam tabel.
            

k(x) = fungsi pembangkit field kunci (1)

h(x) = hash function (2)


Fakta hashing table!:


➤Hashing digunakan untuk menyimpan data yang cukup besar pada ADT yang disebut hash table.

➤Ukuran Hash table (H-size), biasanya lebih besar dari jumlah data yang hendak disimpan.

➤load factor() adalah perbandingan antara data yang disimpan dengan ukuran hash table.

➤Fungsi Hash memetakan elemen pada indeks dari hash table.




Contoh Kodingan Hash Table:


int hash(String key, int tableSize) {

int hashVal = 0;

for (int i=0; i < key.length(); i++) {

hashVal = (hashVal * 37

+ key.charAt(i));

}
hashVal %= tableSize;
if (hashVal < 0) {
hashVal += tableSize;
}
return hashVal;
}



Binary Tree

Tree
adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya.

Sedangkan Binary Tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja.





Sedangkan Binary Tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja.



Aturan yang ada di binary tree :


  • Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
  • Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.



Lalu, ada 3 jenis cara untuk melakukan penelusuran data(traversal) pada BST:


  • PreOrder : Print data, telusur ke kiri, telusur ke kanan
  • InOrder : Telusur ke kiri, print data, telusur ke kanan
  • Post Order : Telusur ke kiri, telusur ke kanan, print data
Contoh koding:

#include <stdio.h>
#include <stdlib.h>

//inisialisasi struct
struct data{
 int number;
 //pointer untuk menampung percabangan kiri dan kanan
 data *left, *right;
}*root;

//fungsi push untuk menambah data
void push(data **current, int number){
 //jika pointer current kosong maka akan membuat blok data baru
 if((*current)==NULL){
  (*current) = (struct data *)malloc(sizeof data);
  //mengisi data
  (*current)->number=number;
  (*current)->left = (*current)->right = NULL;
 //jika tidak kosong, maka akan dibandingkan apakah angka yang 
 //ingin dimasukkan lebih kecil dari pada root
 //kalau iya, maka belok ke kiri dan lakukan rekursif 
 //terus menerus hingga kosong
 }else if(number < (*current)->number){
  push(&(*current)->left, number);
 //jika lebih besar, belok ke kanan
 }else if(number >= (*current)->number){
  push(&(*current)->right, number);
 }
}

//preOrder : cetak, kiri, kanan
void preOrder(data **current){
 if((*current)!=NULL){
  printf("%d -> ", (*current)->number);
  preOrder(&(*current)->left);
  preOrder(&(*current)->right);
 }
}

//inOrder : kiri, cetak, kanan
void inOrder(data **current){
 if((*current)!=NULL){
  inOrder(&(*current)->left);
  printf("%d -> ", (*current)->number);
  inOrder(&(*current)->right);
 }
}

//postOrder : kiri, kanan, cetak
void postOrder(data **current){
 if((*current)!=NULL){
  postOrder(&(*current)->left);
  postOrder(&(*current)->right);
  printf("%d -> ", (*current)->number);
 }
}

//searching data
void search(data **current, int number){
 //jika pointer current memiliki data
 if((*current)!=NULL){
  //cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
  if(number<(*current)->number){
   search(&(*current)->left,number);
  //jika lebih besar, maka belok ke kanan
  }else if(number>(*current)->number){
   search(&(*current)->right,number);
  //jika sama dengan, maka angka ketemu
  }else{
   printf("Found : %d", (*current)->number);
  }
 //jika tidak ada data lagi (not found)
 }else{
  printf("Not Found.");
 }
}

void main(){
 push(&root, 11);
 push(&root, 22);
 push(&root, 13);
 push(&root, 15);
 push(&root, 9);
 inOrder(&root);
 printf("\n");
 preOrder(&root);
 printf("\n");
 postOrder(&root);
 printf("\n");
 search(&root,91);
 getchar();
}



Binary Search Tree 






Binary Search Tree

Binary Search Tree atau yang sering di singkat menjadi BST adalah  tree yang hanya dapat mempunyai maksimal 2 percabangan saja tapi  setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node.








Aturan yang ada pada Binary Search Tree :

  • Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
  • Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

Ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :

  • PreOrder : Print data, telusur ke kiri, telusur ke kanan
  • InOrder : Telusur ke kiri, print data, telusur ke kanan
  • Post Order : Telusur ke kiri, telusur ke kanan, print data
Pre-order
a. Cetak data pada root
b. Secara rekursif mencetak seluruh data pada subpohon kiri
c. Secara rekursif mencetak seluruh data pada subpohon kanan


In-order

a. Secara rekursif mencetak seluruh data pada subpohon kiri
b. Cetak data pada root
c. Secara rekursif mencetak seluruh data pada subpohon kanan

Post-order

a. Secara rekursif mencetak seluruh data pada subpohon kiri
b. Secara rekursif mencetak seluruh data pada subpohon kanan
c. Cetak data pada root


BERIKUT MERUPAKAN TUGAS DATA STRUCTURE BINUS UNTUK SKYSUBMIT 006:





Sekian Dari Review Saya, Terima Kasih













Komentar

Posting Komentar

Postingan populer dari blog ini

Gambar
HEAP Apa itu heap? adalah struktur data berbasis pohon khusus di mana pohon tersebut adalah pohon biner lengkap. Secara umum, tumpukan dapat terdiri dari dua jenis: Max-Heap : Di Max-Heap kunci di simpul root harus menjadi yang terbesar dari semua kunci di semua anak. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner. Min-Heap : Di Min-Heap kunci di simpul root harus minimum kunci di semua anak. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner. Fungsi Heap adalah  untuk menemukan nilai max untuk max heap, dan min untuk min heap. contoh soal Input:  35 33 42 10 14 19 27 44 26 31 Max - heap Di mana root node lebih besar atau sama dengan salah satu dari anak-anaknya. Min - heap Di mana root node kurang dari atau sama dengan salah satu dari anak-anaknya. Insertion Saat sebuah data dimasukkan kedalam heap, maka data langsung ditempatkan di index terakh...
Baca selengkapnya
Gambar
Struktur Data     Struktur data atau biasa  di sebut Data Structure  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. Struktur data yang biasanya di pelajari di bagi bagi menjadi beberapa bagian, yaitu: 🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻 Struktur data sederhana    Co ntoh nya : array dan record. Struktur data majemuk Pada Struktur majemuk pun di bagi menjadi 2, yaitu: ➤Linier : Stack, Queue, sertaList dan Multilist ➤Non Linier : Pohon Biner dan Graph Berikut merupakan tipe tipe Struktur data sederhana yang sering di gunakan dalam pemakaian sehari hari : ➤Multilist ➤Stack ➤Queue ➤Tree ➤Graph Penasaran dengan pengertian list yang saya tulis di atas? TENANG  Saya su...
Baca selengkapnya
Gambar
Hashing Table dan Binary Tree H ashing Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Contoh perintah pada Hashing Table ➤  insert:             diberikan sebuah key dan nilai, insert nilai dalam tabel ➤  find:                diberikan sebuah key, temukan nilai yang berhubungan dengan key ➤  remove:          diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut ➤  getIterator:     mengambalikan iterator,yang memeriksa nilai satu demi satu Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari r...
Baca selengkapnya