Hashing & Binary Tree

Apa sih hashing itu ?
Hashing adalah transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau kunci yang mewakili string asli. penggunaannya seperti memberikan indeks ke dalam database.

Ada beberapa jenis teknik hashing:

- Mid Square

ini adalah teknik pengambilan indeks melalui angka tertentu pada value.
cth:

data 1 - 2132411

maka mid part yang diambil adalah 324

data 2 - 7657876

maka mid part yang diambil adalah 578

- Division

ini adalah teknik pengambilan indeks melalui value yang di modulus dengan angka yg sudah ditentukan.

sebagai contohnya, saya mengambil indeks A-Z yang bertotal ASCII sampai 90.
cth: kata yang saya gunakan "ABE"

kita hitung value menggunakan ASCII :
A = 65
B = 66
E = 69
(65+66+69) % 90 = 20

maka akan disimpan di indeks 20

- Folding

ini adalah teknik yang membagi setiap string menjadi beberapa bagian

cth: angka 3241 dalam hash table yang disediakan sebanyak 100

dibagi menjadi 32 dan 41
kemudian ditambahkan dan hasilnya adalah 73

- Digit Extraction

ini adalah teknik dengan mengambil beberapa bagian dari angkanya

cth: 12345
ambil digit 1, 3, dan 5
sehingga hash code yang didapat adalah 135

- Rotating Hash

ini adalah teknik yang dilakukan setelah memiliki hash code dengan cara-cara diatas kemudian di rotasi

cth: hash code = 12345 
rotated menjadi = 54321

sekarang sudah mengerti kan dengan penjelasan apa itu teknik hashing ?

nah sekarang yuk kita pelajari tentang Binary Tree

Apa sih yang dimaksud dengan Binary Tree ?
Binary Tree adalah Tree yang memiliki node yang bisa memiliki maksimal 2 child (left & right)

 
gambar diatas adalah contohnya...

nah itu dia penjelasan singkat tentang Binary Tree...
Apabila ada yang kurang jelas silahkan comment...

selamat berkoding :)

Stack & Queue

Haloo..
apa kalian pernah mendengar istilah dari stack ataupun queue dalam linked list ?

oke, jadi disini saya akan membahas Stack & Queue.
Stack artinya tumpukan, dan Queue artinya antrian.
dari namanya pun kita sudah mendapat gambaran akan seperti apa bentuk linked list yang akan kita buat...

baiklah mari kita mulai membahas gambaran dari Stack & Queue.

Stack artinya tumpukan, yang berarti data linked list yang dibuat harus sesuai dengan definisi stack, yaitu last in first out, layaknya tumpukan balok, kita menyusun dari bawah ke atas, namun saat menarik balok kita mulai dari bagian atas, ini lah mengapa stack di sebut LIFO (Last In First Out).

Queue artinya antrian, yang berarti data linked list yang dibuat harus sesuai dengan definisi queue, yaitu first in first out, layaknya antrian tiket bioskop, orang yang terdepan dan sudah membayar akan keluar dari antrian, ini lah mengapa queue disebut FIFO (First In First Out).

Apakah kodingan berbeda ?? jelas beda...
untuk stack, yang digunakan adalah function push tail dan pop tail.
untuk queue, yang digunakan adalah function push tail dan pop head.

Notes:
- Push = menambahkan data
- Pop = menghapus data

baiklah sepertinya sudah cukup jelass untuk penjelasan tentang stack dan queue, apabila ada pertanyaan bisa bertanya di kolom komentar...

selamat berkoding :)

Linked List

Linked List biasa kita gunakan untuk mempermudah insertion data pada database..Serta tidak membuang-buang memory, karena menggunakan malloc yang disebut juga memory allocation sesuai dengan memory yang dibutuhkan.

Seperti apa sih penggunaan Linked List itu ?

berikut ini adalah contoh kodingan milik saya :

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

struct node {
      int key;
      node *next;
} *head, *tail, *curr;

struct node *create(int key) {
      struct node *newnode = (struct node*)malloc(sizeof(struct node));
      newnode->key = key;
      newnode->next = NULL;
      return newnode;
};

void pushHead(int key) {
    node *temp = create(key);
    if(!head) {
        head = tail = temp;
    }else {
        temp->next = head;
        head = temp;
    }
}

void pushTail(int key) {
    node *temp = create(key);
    if(!head) {
        head=tail=temp;
    }else{
        tail->next = temp;
        tail = temp;
    }
}

void pushMid(int key) {
    node *temp = create(key);
    if(!head) {
        head = tail = temp;
    } else if (head->key > temp->key){
        pushHead(key);
    } else if (tail->key < temp->key) {
        pushTail(key);
    } else {
        curr = head;
        while(curr) {
            if(curr->key > temp->key) {
                temp->next = curr;
            }
        }
    }
}

void popHead() {
    if(head==tail) {
        free(head);
    } else {
        node *temp = head->next;
        head->next = NULL;
        free(head);
        head = temp;
    }
}

void popTail(){
    if(!head) return;
    if(head==tail){
        free(head);
        head = tail = NULL;
        return;
    }
    curr = head;
    while(curr->next!=tail){
        curr = curr->next;  
    }
    tail = curr;
    free(curr->next);
    tail->next = NULL;
}

void popSearch(int key){
    if(!head) return;
    if(head==tail){
        free(head);
        head = tail = NULL;
        return;
    }
    if(head->key == key) popHead();
    else if(tail->key == key) popTail();
    else{
        curr = head;
        while(curr->next){
            if(curr->next->key == key){
                node *temp = curr->next;
                curr->next = curr->next->next;
                free(temp);
                break;
            }
            curr = curr->next;
        }
    }
}

void popMid(int index){
    if(!head) return;
    if(head==tail){
        free(head);
        head = tail = NULL;
        return;
    }
    if(index==0) popHead();
    else{
        curr = head;
        for(int i=0; i<index-1; i++){
            curr = curr->next;
            if(!curr) break;
        }
        if(!curr || !curr->next) printf("Error! PopMid at index %d failed!\n", index);
        else{
            node *temp = curr->next;
            curr->next = temp->next;
            free(temp);
        }
    }
}

void printall() {
  curr = head;
  while (curr != NULL) {
    printf ("%d ", curr->key);
    curr = curr->next;
  }
  puts("");
}

int main() {
   pushTail (5);
   printall();
   pushTail (10);
   printall();
   pushHead (15);
   printall();

  return 0;
}
Kodingan dasar untuk single linked list akan seperti ini.

Jangan lupa untuk menggunakan library stdlib yaa...
karena ada penggunaan malloc..
selain stdlib bisa juga menggunakan library malloc
yaitu : #include<malloc.h>

Push adalah function untuk insertion data
Pop adalah function untuk deletion data
Printall adalah function untuk view data

dan inilah hasil output yang dikeluarkan dari kodingan diatas...

jika ada pertanyaan silahkan comment...

Selamat berkoding :)