Sabtu, 04 April 2020

2nd Semester: Summary 1

Pada kesempatan kali ini saya merangkum topik-topik semester 2 yang telah dibahas sebelumnya dengan menggunakan bahasa Inggris dan Indonesia. Topik-topik tersebut diantaranya:

  1. Circular Single Linked List, Doubly Linked List, & Circular Doubly Linked List
  2. Stack & Queue
  3. Hashing Table & Binary Tree
  4. Binary Search Tree

Circular Single Linked List
• In circular, last node contains a pointer to the first node
• We can have a circular singly linked list as well as a circular doubly linked list.
• There is no storing of NULL values in the list



Advantages of Circular Linked Lists:
1) Any node can be a starting point.
2) Useful for implementation of queue.
3) Circular lists are useful in applications to repeatedly go around the list.
4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.


Doubly Linked List
Double/Doubly linked list (DLL) or two-way linked list is a linked list data structure with
two link, one that contain reference to the next data and one that contain reference to the
previous data.
dll
Following is representation of a DLL node in C language.

/* Node of a doubly linked list */
struct Node {
    int data;
    struct Node* next; // Pointer to next node in DLL
    struct Node* prev; // Pointer to previous node in DLL
};

Advantages over singly linked list:
1) A DLL can be traversed in both forward and backward direction.
2) The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
3) We can quickly insert a new node before a given node.


Disadvantages over singly linked list:
1) Every node of DLL Require extra space for an previous pointer.
2) All operations require an extra pointer previous to be maintained.


Doubly Linked List: Insertion 
A node can be added in four ways:
1) At the front of the DLL.
2) After a given node.
3) At the end of the DLL.
4) Before a given node.


Doubly Linked List: Deletion
There are 4 conditions we should pay attention when deleting:
1) The node to be deleted is the only node in linked list.
2) The node to be deleted is head.
3) The node to be deleted is tail.
4) The node to be deleted is not head or tail.


Circular Doubly Linked List
Circular Doubly Linked List has properties of both doubly linked list and circular linked list in
which two consecutive elements are linked or connected by previous and next pointer and
the last node points to first node by next pointer and also the first node points to last node
by previous pointer.



Stacks Concept

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.A stack is a recursive data structure. Here is a structural definition of a Stack:

a stack is either empty or it consistes of a top and the rest which is a stack;

 


Prefix, Infix, & Postfix
1. Prefix adalah notasi yang terbentuk atas
operator dengan operand, dimana oprator
didepan operand.

Contoh: A + B * C (infix).
maka notasi prefixnya adalah: +A*BC.


Pemecahannya:

Diketahui ada 3 operand yaitu: A, B, C dan 2


operand yaitu: +, *.proses dimulai dengan
melihat dari hirarkhi oprator.Contoh diatas operator yang tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand yaitu B*C, prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari operand,sehingga fungsi B*C, notasi prefixnya menjadi *BC, sehingga hasil sementara dari notasi prefix adalah A+*BC.


Selanjutnya mencari prefix untuk operator yang berikutnya yaitu +, cara yang dilakukan sama seperti diatas, operator + diapit oleh operand, yaitu A dan *BC, gabungkan operand,sehingga menjadi A*BC,lalu pindahkan operator kedepan operand,sehingga hasil akhir menjadi +A*BC.





2.Infix adalah notasi yang membentuk atas operator dengan operand,dimana operator berada diantara operand.

Contoh :  - A + B * C
                 - (A + B) * C
                 - A - (B + C) * D ^ E




3.Postfix adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.

Contoh : A + B * C (infix).
maka notasi postfix adalah ABC*+.


Pemecahannya:
Diketahui ada 3 operand yaitu : A,B,C dan 2 operator yaitu : +, *. proses dimulai dengan melihat dari hirarkhi operator.Contoh diatas operator yang tertinggi adalah * kemudian +.


Tanda * diapit oleh kedua operand yaitu B dan C yaitu B*C, postfix dengan menggabungkan operand B dan C menjadi BC,lalu memindahkan operator ke belakang operand C, sehingga fungsi B*C, notasi postfixnya menjadi BC*.Sehingga hasil sementara dari notasi postfix adalah A + BC*.


Selanjutnya mencari postfix untuk operator yang berikutnya, yaitu +, dengan cara yang dilakukan sama seperti di atas, operator + diapit oleh 2 operand, yaitu A dan BC*. Gabungkan operand tersebut, sehingga menjadi ABC*, lalu pindahkan operator + kebelakang operand ABC*.

Sehingga hasil akhir  menjadi ABC*+.




Stack Applications
Stacks are widely used to:
• Reverse the order of data
• Convert infix expression into postfix
• Convert postfix expression into infix
• Backtracking problem
• System stack is used in every recursive function
• Converting a decimal number into its binary equivalent




Queue Concept
A Queue is a linear structure which follows
particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.



Circular Queue
Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.

circularqueues
In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we can not insert the next element even if there is a space in front of queue.



Priority Queue
Priority Queue is an extension of queue with following properties.
  1. Every item has a priority associated with it.
  2. An element with high priority is dequeued before an element with low priority.
  3. If two elements have the same priority, they are served according to their order in the queue.

Hashing
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Dalam hashing, string karakter ditransformasikan menjadi nilai panjang yang biasanya lebih pendek atau kunci yang mewakili string asli. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut tabel hash menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.



Hash Table

Hash table adalah struktur data yang mengimplementasikan tipe data abstrak array asosiatif, struktur yang dapat memetakan kunci ke nilai. Tabel hash menggunakan fungsi hash untuk menghitung indeks, juga disebut kode hash, ke dalam array dari ember atau slot, dari mana nilai yang diinginkan dapat ditemukan.

Implementasi Hash Table pada Blockchain
Peran penting kriptografi dalam jaringan blockchain terus berkembang tiada hentinya. Salah satunya adalah proses perhitungan sebuah data secara konkret dan unik. Metode ini dikenal dengan Hash, mungkin anda tak asing dengan kode unik yang banyak ditemukan di Blockchain dan itulah salah satu contoh Hash.
Nilai berharga sebuah data saat ini berpotensi dibobol atau diketahui oleh orang lain. Salah satu teknik mengakalinya ialah dengan pemberian kode unik. Ibarat peran dari sidik jari elektronik (digital fingerprint) pada data digital punya Anda.
Data tersebut akan aman dan pastinya menjadi orisinalitas data dari orang lain. Hanya orang yang terkait berhak dan bisa masuk ke akses data tersebut. Saat ini beragam proses pengamanan data, mulai dari sidik jari, sidik mata, dan di sistem Blockchain menggunakan kode unik (Hash).
Password atau kode unik di blockchain punya nilai karakter yang lebih panjang dan menggunakan kode unik. Pastinya proses peretesan dengan aplikasi tebak saat ini jelas sangat lama dan bahkan mustahil. Itulah yang menjadi alasan bahwa Hash sangat penting dan dinilai sangat aman.
Tak hanya itu saja, Hash mampu mengubah setiap data yang mengalami perubahan dengan nilai unik sendiri. Ini yang tidak didapatkan pada jaringan biasa. Selain itu, setiap data dokumen dengan panjang berapa pun akan menghasilkan nilai hash yang punya nilai panjang berbeda tergantung spesifikasi Hash yang digunakan.
Monero menilai bahwa perlu adanya keamanan khusus dan beragam pada Hash. Inilah yang menjadi dasar lahirnya konsep CryptoNote. Pengguna yang mengirimkan transaksi atau data tidak dapat diidentifikasi oleh publik karena ada beberapa kunci tersebut. Ia kata sebagai pengalih dan membuat Anda sulit diintai dan data serta privasi tetap aman di jaringan Blockchain.

Implementasi Hash Table di C menggunakan array

Example
#include<stdio.h>

#define size 7

int arr[size];

void init()
{   
    int i;
    for(i = 0; i < size; i++)
        arr[i] = -1;
}

void insert(int value)
{   
    int key = value % size;
    
    if(arr[key] == -1)
    {   
        arr[key] = value;
        printf("%d inserted at arr[%d]\n", value,key);
    }
    else
    {   
        printf("Collision : arr[%d] has element %d already!\n",key,arr[key]);
        printf("Unable to insert %d\n",value);
    }
}

void del(int value)
{
    int key = value % size;
    if(arr[key] == value)
        arr[key] = -1;
    else
        printf("%d not present in the hash table\n",value);
}

void search(int value)
{
    int key = value % size;
    if(arr[key] == value)
        printf("Search Found\n");
    else
        printf("Search Not Found\n");
}

void print()
{
    int i;
    for(i = 0; i < size; i++)
        printf("arr[%d] = %d\n",i,arr[i]);
}

int main()
{
    init();
    insert(10); //key = 10 % 7 ==> 3
    insert(4);  //key = 4 % 7  ==> 4
    insert(2);  //key = 2 % 7  ==> 2
    insert(3);  //key = 3 % 7  ==> 3 (collision)

    printf("Hash table\n");
    print();
    printf("\n");

    printf("Deleting value 10..\n");
    del(10);
    printf("After the deletion hash table\n");
    print();
    printf("\n");

    printf("Deleting value 5..\n");
    del(5);
    printf("After the deletion hash table\n");
    print();
    printf("\n");

    printf("Searching value 4..\n");
    search(4);
    printf("Searching value 10..\n");
    search(10);

    return 0;
}
Hash Function
Ada banyak cara untuk mengaitkan string menjadi kunci. Berikut ini adalah beberapa metode penting untuk membangun hash function.
1. Mid-square
Mid-Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan. Saat bijinya dikuadratkan, jika angka 6-digit diambil, maka persegi akan memiliki 12-digit. Ini melebihi kisaran tipe data int. Jadi, overflow harus diurus. Jika terjadi overflow, gunakan tipe data int panjang atau gunakan string sebagai perkalian jika luapan masih terjadi. Kemungkinan tabrakan di tengah-tengah hashing rendah, tidak usang. Jadi, dalam peluang, jika tabrakan terjadi, itu ditangani menggunakan beberapa peta hash.
2. Division (paling umum)
Jumlah lokasi memori yang tersedi dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya. Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hash tersebut menempatkan record dengan kunci K pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.
3. Folding
Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).
4. Digit Extraction 
Menggunakan ekstraksi digit digit yang dipilih diekstraksi dari kunci dan digunakan sebagai alamat.
5. Hash Rotation
Metode rotasi umumnya tidak digunakan dengan sendirinya melainkan digabungkan dalam kombinasi dengan metode hashing lainnya. Ini sangat berguna ketika kunci ditugaskan secara serial
Tree
tree adalah abstract data type (ADT) yang banyak digunakan untuk mensimulasikan struktur hierarki pohon, dengan nilai root dan subtrees of children dengan node parent, direpresentasikan sebagai satu set node yang terhubung.

Struktur data pohon dapat didefinisikan secara rekursif sebagai kumpulan node (dimulai dari simpul akar), di mana setiap simpul adalah struktur data yang terdiri dari suatu nilai, bersama dengan daftar referensi ke node ("children"), dengan kendala yang tidak ada referensi digandakan, dan tidak ada yang menunjuk ke root


Binary Tree
Pohon yang unsurnya paling banyak memiliki 2 children disebut pohon biner (Binery Tree). Karena setiap elemen dalam pohon biner hanya dapat memiliki 2 children, biasanya disebut left children dan right children.

Node Pohon Biner berisi bagian-bagian berikut.
1. Data.
2. Pointer ke left children.
3. Pointer ke right children.


Jenis-jenis Binary Tree :
a) Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.


b) Complete Binary Tree
Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

c) Skewed Binary Tree
akni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.



       expression tree concept:

Prefix  : *+ab/-cde
Postfix : ab+cd-e/*
Infix  : (a+b)*((c-d)/e)


Binary Search Tree
Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap child node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.

Binary Search Tree membedakan kiri dan kanan sesuai besaran nilainya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan binary search tree, proses search akan lebih cepat.
Aturan 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.
Kemudian, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada binary search tree, yaitu:
  • Pre Order : Print data, telusur ke kiri, telusur ke kanan.
  • In Order : Telusur ke kiri, print data, telusur ke kanan.
  • Post Order : Telusur ke kiri, telusur ke kanan, print data.
Binary Search Tree memiliki operasi dasar berikut:
- find (X): cari kunci X di Binary Search Tree.
a. Karena properti Binary Search Tree, finding/searching di Binary Search Tree mudah.
b. Biarkan kunci yang ingin kita cari adalah X.
1. Kita mulai dari root.
2. Jika root berisi X maka pencarian berhasil dihentikan.
3. Jika X kurang dari kunci root, maka cari secara rekursif pada sub tree kiri, jika tidak cari
  secara rekursif pada sub tree kanan.

- insert (X): masukkan kunci baru X ke dalam Binary Search Tree.
a. Memasukkan ke dalam Binary Search Tree dilakukan secara rekursif.
b. Biarkan kunci node baru menjadi X,
1. Mulailah dari root.
2. Jika X kurang dari kunci simpul maka masukkan X ke sub tree kiri, jika tidak masukkan X
ke sub tree kanan.
3. Ulangi sampai menemukan simpul kosong untuk meletakkan X (X akan selalu menjadi
leaf baru).
- remove (X): hapus kunci X dari Binary Search Tree.
Ada 3 kasus yang harus dipertimbangkan: 1. Jika kunci ada di leaf, hapus saja node itu. 2. Jika kunci ada di node yang memiliki satu children, hapus node itu dan sambungkan
children-nya ke parent-nya.
3. Jika kunci ada di node yang memiliki dua children, temukan children paling kanan dari sub
tree kirinya (node P), ganti kuncinya dengan kunci P dan hapus P secara rekursif. (atau
secara alternatif dapat memilih anak paling kiri dari sub tree kanannya).

Contoh Aplikasi Binary Search Tree:
1. Membangun daftar vocabulary yang merupakan bagian dari inverted index (sebuah struktur
    data yang digunakan oleh banyak mesin pencari seperti Google.com, Yahoo.com dan
    Ask.com).
2. Banyak digunakan dalam bahasa pemrograman untuk mengelola dan membangun dynamic
    sets.

Pembentukan Binary Search Tree
Bila diketahui sederetan data 5, 3, 7, 1, 4, 6, 8, 9 maka pemasukan data tersebut dalam struktur data BST, langkah per langkah, adalah sebagai berikut:

Langkah 1:
Pemasukan data 5 sebagai root.

Langkah 2:
Pemasukan data 3 disebelah kiri simpul 5 karena 3 < 5. 5 3 5 Struktur Data dan Algoritma 4 Taufik Fuadi Abidin, Irvanizam Zamanhuri, Muhammad Subianto.


Langkah 3:
Pemasukan data 7 disebelah kanan simpul 5 karena 7 > 5.


Langkah 4:
Pemasukan data 1. Karena data 1 lebih kecil dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kiri root. Kemudian karena disebelah kiri sudah ada daun dengan nilai 3 dan data 1 lebih kecil dari data 3 maka data 1 disisipkan disebelah kiri simpul 3.



Langkah 5:
Pemasukan data 4. 3 5 7 3 5 7 1 3 5 7 1 4 Struktur Data dan Algoritma 5 Taufik Fuadi Abidin, Irvanizam Zamanhuri, Muhammad Subianto.



Langkah 6:
Pemasukan data 6. Karena data 6 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 7 dan data 6 lebih kecil dari data 7 maka data 6 disisipkan disebelah kiri simpul 7.



Langkah 7:
Pemasukan data 8. Karena data 8 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 7 dan karena data 8 lebih besar dari data 7 maka data 8 disisipkan disebelah kanan simpul 7. 5 7 6 3 1 4 5 7 6 3 1 4 8 Struktur Data dan Algoritma 6 Taufik Fuadi Abidin, Irvanizam Zamanhuri, Muhammad Subianto.



Langkah 8:
Pemasukan data 9. Karena data 9 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan bukan merupakan daun yaitu simpul dengan nilai 7 dan karena data 9 lebih besar dari data 7 penelusuran terus dilanjutkan kesebelah kanan. Selanjutnya ditemukan daun dengan nilai 8, karena data 9 lebih besar dari 8 maka data 9 disisipkan disebelah kanan simpul 8. 5 7 6 3 1 4 8 9.

Berikut adalah contoh implementasi Binary Search Tree pada C beserta searching datanya:


#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.");
 }
}

int 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();
}
Berikut adalah link tugas koding untuk market berbasis c yang telah saya buat:
https://drive.google.com/open?id=18SQo5RFyK-2cFsNQ42RiRp_zF5hqmhGT

Sekian Summary 1 saya untuk semester 2, mohon maaf bila ada kekurangan, terima kasih.

Tidak ada komentar:

Posting Komentar