Tuesday, May 19, 2020

Heap & Tries

Heap & Tries

Heap

  • Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifatnya, yaitu jika B adalah anak dari A, maka nilai yang tersimpan di node A lebih besar atau sama dengan nilai yang tersimpan di node B.
  • Heap terbagi menjadi 2 yaitu:
    1. Min Heap, setiap elemen node adalah lebih kecil daripada childrennya. Ini menunjukan bahwa elemen terkecil terletak pada root dari tree. Unsur terbesar adalah terletak di suatu tempat di salah satu node leaves.
    2. Max Heap, setiap elemen node adalah lebih besar daripada childrennya. Karena urutan sibling dalam heap tidak ditentukan oleh sifat heap, dua node tunggal anak-anak bisa secara bebas dipertukarkan.
  • Sifat dari Heap: 
    • Setiap node lebih besar dari atau sama dengan masing-masing anak sesuai dengan perbandingan predikat yang ditetapkan untuk struktur data.
Tries
  • Adalah Binary Tree dimana didalamnya terdapat kumpulan dari kata-kata. Tree ini dibuat untuk mempermudah pencarian suatu kata-kata (biasanya digunakan pada saat pembuatan fitur search pada kamus).

Sumber:

Monday, May 4, 2020

AVL Tree

AVL Tree
  • AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian danbentuk tree dapat dipersingkat dan disederhanakan. Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru→root. Node pertama yang memiliki balance factor > 1 diseimbangkan. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. 

  • Proses penyeimbangan dilakukan dengan: 
    1. Single rotation adalah rotasi yang dilakukan apabila data yang diinsert searah, left-left atau right-right.
    2. Double rotation adalah rotasi yang dilakukan apabila data yang diinsert tidak searah, left-right atau right-left.
  • Operasi pada AVL:
    1. Insertion atau insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam.
    2. Deletion yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. 

Sumber: 

Tuesday, April 7, 2020

Drummers Market

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<windows.h>
#include<time.h>


char name[100];
char namee[100];
int quantity=0;
int price=0;
int newStock=0;

void enter();
void menu();
void print();
void space();

struct barang{
char name[100];
int quantity;
int price;
struct barang *next, *prev;
}*head=NULL, *tail=NULL, *curr;

void space(){
printf("\n\n\n\n\n\n\n\n\n\n\n");
}

void pushData(char name[], int quantity, int price){
struct barang *temp = (struct barang*)malloc(sizeof(struct barang));

strcpy(temp->name, name);
temp->quantity = quantity;
temp->price = price;
temp->next = NULL;
temp->prev = NULL;

if(head==NULL){
head=tail=temp;
}
else{
tail->next = temp;
temp->prev = tail;
tail=temp;
}
}

void enter(){
printf("Press Enter to continue...");
getchar();
menu();
}

void checkoutItem(){
struct barang *curr = (struct barang*)malloc(sizeof(struct barang));

if(head==NULL){
printf("There is no data\n");
enter();
}
else{
barang *curr=head;
int count=1;
while(curr!=NULL){
printf("%-2d. %-20s %-6d Rp. %-6d\n", count, curr->name, curr->quantity, curr->price);
price += curr->price*curr->quantity;
curr=curr->next;
count++;
}
printf("\nTotal price: Rp.%d\n", price);
printf("\nKindness is free\n");
space();
}
}

void deleteData(char name[100]){
struct barang *curr = (struct barang*)malloc(sizeof(struct barang));
if(head==tail){
free(head);
head=tail=NULL;
}
else if(strcmp(name, head->name)==0){
curr=head;
head=head->next;
free(curr);
}
else if(strcmp(name,tail->name)==0){
curr=tail;
tail->next;
}
else{
curr=head;
while(curr!=NULL){
if(strcmp(curr->name, name)==0){
break;
}
curr=curr->next;
}
curr->next->prev=curr->prev;
curr->prev->next=curr->next;
curr->next=NULL;
curr->prev=NULL;
free(curr);
}
}

void deleteItem(){
struct barang *curr = (struct barang*)malloc(sizeof(struct barang));
if(head==NULL){
printf("There is no data\n");
enter();
}
else{
print();
do{
printf("Input item name[3-20]");
scanf("%[^\n]", namee);
}
while(strlen(namee)<3 || strlen(namee)>20);
deleteData(namee);
}
enter();
}

void addItem(){
srand(time(NULL));
do{
printf("Input item name[3-20]: ");
scanf("%[^\n]", name);
getchar();
}
while(strlen(name)<3 || strlen(name)>20);
do{
printf("Input item stock: ");
scanf("%d", &quantity);
}
while(quantity<1);
price = (rand() % ((20000+1)-5000)) + 20000;
pushData(name, quantity, price);
enter();
}

void print(){
struct barang *curr = (struct barang*)malloc(sizeof(struct barang));

curr=head;
int count=1;
while(curr!=NULL){
printf("%-2d. %-20s %-6d Rp. %-6d\n", count, curr->name, curr->quantity, curr->price);
curr=curr->next;
count++;
}
space();
}

void editItem(){
char namee[100];
if(head==NULL){
printf("There is no data");
enter();
}
else{
barang *temp = head;
print();
printf("\nInput item name[3-20]: ");
scanf("%[^\n]", namee);
getchar();
while(temp!=NULL){
if(strcmp(namee, temp->name)==0){
printf("\nInput new item quantity: ");
scanf("%d", &newStock);
temp->quantity = newStock;
}
temp = temp->next;
}
}
enter();
}

void menu(){
system("cls");
int choose;
do{
printf("~~~Drummers Market~~~\n");
printf("1. Add Item\n");
printf("2. Edit Item\n");
printf("3. Delete Item\n");
printf("4. Checkout Item\n");
printf(" >> ");
scanf("%d", &choose);
getchar();

if(choose==1){
system("cls");
addItem();
}
else if(choose==2){
system("cls");
editItem();
}
else if(choose==3){
system("cls");
deleteItem();
}
else if(choose==4){
system("cls");
checkoutItem();
}
}
while(choose!=5);

}

int main(){
menu();

return 0;
}

Saturday, April 4, 2020

Summary

Summary

Single Linked List
adalah sebuah Linked List yang menggunakan satu variabel pointer saja untuk menyimpan banyak data.
Dalam single Linked List, pointer hanyak bergerak ke satu arah saya, kedepan/kebelakang.

Single Linked List dibagi menjadi 2 yaitu:
  1. Circular Single Linked List.
  2. Non Circular Single Linked List.

Circular Single Linked List
  • Adalah Single Linked List yang pointernya menunjuk pada dirinya sendiri, kata circular dalam Circular Single Linked List memiliki arti bahwa pointer selanjutnya akan menunjuk pada dirinya sendiri sehingga akan berputar.


Non Circular Single Linked List

  • Perbedaanya dengan Circular adalah Single Linked List ini, pointer selanjutnya tidak akan menunjuk pada dirinya sendiri sehingga tidak akan berputar.


Double Linked List
  • Adalah Linked List yang memiliki 2 variabel pointer yaitu pointer yang menunjuk pada node setelahnya dan satu lagi yang menunjuk pada node sebelumnya. Setiap head and tailnya menunjuk Null
  • Elemennya terdiri dari 3 bagian:
  1. Pointer next yang menunjuk elemen setelahnya
  2. Pointer prev yang menunjuk elemen sebelumnya
  3. Bagian data informasi

Circular Double Linked List
  • Adalah Linked List yang disetiap nodenya memiliki 3 field yaitu:
  1. 1 Field pointer menunjuk next
  2. 1 Field pointer menunjuk prev
  3. 1 Field yang berisi data dari node
  • Pointer next dan prevnya menunjuk kedirinya sendiri secara circular.
  • Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node setelahnya serta ke node sebelumnya
  • Untuk membuat node baru, pada awalnya pointer next dan prev akan menunjuk pada NULL
  • Selanjutnya pointer prev akan menunjuk ke yang sebelumnya dan next menunjuk pada node setelahnya



Stack & Queue

Stack adalah tumpukan data yang diletakkan bertumpukkan. Stack menggunakan konsep yang bernama LIFO yang berarti Last in First Out, data yang terakhir dimasukkan merupakan data yang pertama kali diakses atau dikeluarkan. 

Terdapat 2 operasi di dalam Stack yang sering digunakan yaitu:

  1. Push: digunakan untuk menambahkan data pada Stack 
  2. Pop: digunakan untuk mengambil data pada Stack 


Queue adalah stuktur data linear dimana penambahan data dilakukan disatu sisi, disalah satu ujungnya, untuk penguruangannya dilakukan diujung lain, Queue menggunakan konsep FIFO yang berarti First in First Out, data yang pertama kali dimasukkan merupakan data yang pertama kali diakses.

Terdapat 2 operasi dalam Queue yang sering digunakan yaitu:
  1. Enqueue: digunakan untuk memasukkan sebuah data ke dalam queue. pada proses enqueue, bagian tail yang berjalan sendiri seiring dengan masuknya data baru ke dalam queue.
  2. Dequeue: digunakan untuk menghapuskan sebuah data yang paling pertama masuk ke dalam queue


Perbedaan antara Stack & Queue
  • Prinsip kerjanya, Stack menggunakan prinip kerja tumpukan sementara Queue menggunakan prinsip kerja antrian.
  • Konsep kerjanya, Stack menggunakan LIFO, Last in First Out sementara Queue menggunakan FIFO, First in First Out.
  • Pada proses penambahan dan penghapusan elemen, pada Stack operasi penambahan atau pengurangannya dilakukan pada satu ujungnya. Pada Queue operasi penambahan atau pengurangannya dilakukan di tempat yang berbeda.



Hash Table 




  • Merupakan salah satu stuktur data yang digunakan untuk menyimpan data sementara. Hash Table digunakan untuk mempercepat pencarian kembali dari banyak data yang telah disimpan. Haah table menggunakan teknik penyimpanan sehingga waktu yang dibutuhkan untuk insertions, deletions, dan searching relatif sama dibandingkan dengan struktur data yang lain.
  • Kelebihan Hash table:
  1. Hash table relatif lebih cepat.
  2. Kecepatan dalam insertions, deletions, dan searching relatif sama.
  • Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Intinya hash table merupakan penyimpanan data yang menggunakan key value yang didapat dari nilai data itu sendiri.
  • Beberapa hal yang perlu diperhatikan dalam membuat hash function:
  1. Ukuran array
  2. Key value
  3. Hash value/ Hash index
Tree
  • Merupakan salah satu bentuk struktur data yang tidak linear, menggambarkan hubungan ont to many antara elemen-elemen. Tree terdiri dari kumpulan node di mana ada yang disebut root dan node lainnya disebut subtree. 

  • Bagian-bagian dari tree:

  1. Root, jika tree kosong maka node pertama dan merupakan node unik merupakan root.
  2. Branch, banyaknya cabang sidebut degree dari node tersebut.
  3. Leave, merupakan node yang nilai outdegreenya 0, merupakan node yang tidak memiliki successor.
  4. Parent, disebut parent ketika outdegreenya lebih dari 0.
  5. Child, cabang terakhir dari sebuah tree.



Binary Tree
  • Merupakan tree yang memiliki syarat tiap nodenya hanya memiliki maksimal dua subtree dan kedua subtreenya harus terpisah. Maka tiap node dalam binary tree hanya dapat memiliki 2 child. 
  • Ada dua cara representase binary tree:
  1. Representasi sekuensial
  2. Representasi terkait
  • Jenis-jenis binary tree:
  1. Full Binary Tree
  2. Complete Binary Tree
  3. Skewed Binary Tree


Binary Search Tree
  • Disebut juga pohon biner yang dalam struktur data bersifat hirarkis. Binary Tree merupakan suatu tree dengan dyarah bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binaty tree boleh memiliki paling banyak 2 child, secara khusus anaknya dinamakan kiri dan kanan.
  • Binary Search Tree berfungsi menyimpan informasi nama atau bilangan yang disimpan dalam memory. Dengan membagi data menjadi dua dengan mencari titik tengah sbagai patokannya. Binary tree terdiri dari simpul pertama yang disebut  root.
  • Binary Search memungkinkan pencarian dengan cepat, penambahan, dan penghapusan menggunakan informasi kunci atau key. 
  • Dua aturan yang harus dipenuhi:
    1. Semua data dibagian kiri sub-tree node t selalu lebih kecil dari data dalam node t itu sendiri.
    2. Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.


  • Ada beberapa metode di dalam Binary Search Tree:
    1. Insert, pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat
    2. Update, update akan mempengaruhi posisi node tersebut. Setelah diupdate yang awalnya Binary Search Tree, menjadi bukan Binary Search Tree. Maka perubahan perlu dilakukan dengan melakukan rotasi agar tetap menjadi Binary Search Tree.
    3. Delete, delete dalam Binary Search Tree juga memperngaruhi posisi tree tersebut.


Sumber:
https://kuliahinformatika.wordpress.com/2010/01/21/linked-list-definisi-node-linked-list-single-linked-list-double-linked-list-circular-linked-list/
http://brawlyvonfabre.blogspot.com/p/single-linked-list.html
http://suciantinovi.blogspot.com/2014/03/linked-list-i_14.html
http://brawlyvonfabre.blogspot.com/p/double-linked-list.html
http://bocahngoding.blogspot.com/2018/01/pengertian-stack-dan-queue-dalam.html
https://furqonubd.wordpress.com/2013/05/20/stack-and-queue/
http://17416255201077-azizfirmansaputra.blogspot.com/2018/10/pengertian-dan-contoh-sederhana-tentang.html
https://informatika11d.wordpress.com/2012/11/22/struktur-data-hash-table/
http://kupaskode.blogspot.com/2015/09/tentang-hashing.html
https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html
http://new-funday.blogspot.com/2012/12/struktur-data-tree-dan-penjelasaanya.html
https://saragusti22.wordpress.com/2015/05/04/pengantar-struktur-data-tree-dan-binary-tree/
https://herlinnairine.wordpress.com/2015/05/05/tree-dalam-pengantar-struktur-data/
https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/
https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html
http://new-funday.blogspot.com/2012/12/struktur-data-tree-dan-penjelasaanya.html
https://saragusti22.wordpress.com/2015/05/04/pengantar-struktur-data-tree-dan-binary-tree/



Monday, March 23, 2020

Binary Search Tree

Binary Search Tree
  • Disebut juga pohon biner yang dalam struktur data bersifat hirarkis. Binary Tree merupakan suatu tree dengan dyarah bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binaty tree boleh memiliki paling banyak 2 child, secara khusus anaknya dinamakan kiri dan kanan.
  • Binary Search Tree berfungsi menyimpan informasi nama atau bilangan yang disimpan dalam memory. Dengan membagi data menjadi dua dengan mencari titik tengah sbagai patokannya. Binary tree terdiri dari simpul pertama yang disebut  root.
  • Binary Search memungkinkan pencarian dengan cepat, penambahan, dan penghapusan menggunakan informasi kunci atau key. 
  • Dua aturan yang harus dipenuhi:
    1. Semua data dibagian kiri sub-tree node t selalu lebih kecil dari data dalam node t itu sendiri.
    2. Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.


  • Ada beberapa metode di dalam Binary Search Tree:
    1. Insert, pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat
    2. Update, update akan mempengaruhi posisi node tersebut. Setelah diupdate yang awalnya Binary Search Tree, menjadi bukan Binary Search Tree. Maka perubahan perlu dilakukan dengan melakukan rotasi agar tetap menjadi Binary Search Tree.
    3. Delete, delete dalam Binary Search Tree juga memperngaruhi posisi tree tersebut.



Sumber:







Wednesday, March 11, 2020

Hash Table, Tree, & Binary Tree

Hash Table 




  • Merupakan salah satu stuktur data yang digunakan untuk menyimpan data sementara. Hash Table digunakan untuk mempercepat pencarian kembali dari banyak data yang telah disimpan. Haah table menggunakan teknik penyimpanan sehingga waktu yang dibutuhkan untuk insertions, deletions, dan searching relatif sama dibandingkan dengan struktur data yang lain.
  • Kelebihan Hash table:
    1. Hash table relatif lebih cepat.
    2. Kecepatan dalam insertions, deletions, dan searching relatif sama.
  • Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Intinya hash table merupakan penyimpanan data yang menggunakan key value yang didapat dari nilai data itu sendiri.
  • Beberapa hal yang perlu diperhatikan dalam membuat hash function:
    1. Ukuran array
    2. Key value
    3. Hash value/ Hash index
Tree
  • Merupakan salah satu bentuk struktur data yang tidak linear, menggambarkan hubungan ont to many antara elemen-elemen. Tree terdiri dari kumpulan node di mana ada yang disebut root dan node lainnya disebut subtree. 

  • Bagian-bagian dari tree:

    1. Root, jika tree kosong maka node pertama dan merupakan node unik merupakan root.
    2. Branch, banyaknya cabang sidebut degree dari node tersebut.
    3. Leave, merupakan node yang nilai outdegreenya 0, merupakan node yang tidak memiliki successor.
    4. Parent, disebut parent ketika outdegreenya lebih dari 0.
    5. Child, cabang terakhir dari sebuah tree.

Binary Tree
  • Merupakan tree yang memiliki syarat tiap nodenya hanya memiliki maksimal dua subtree dan kedua subtreenya harus terpisah. Maka tiap node dalam binary tree hanya dapat memiliki 2 child. 
  • Ada dua cara representase binary tree:
    1. Representasi sekuensial
    2. Representasi terkait
  • Jenis-jenis binary tree:
    1. Full Binary Tree
    2. Complete Binary Tree
    3. Skewed Binary Tree


Sumber:

Wednesday, March 4, 2020

Stack & Queue

Stack & Queue

Stack adalah tumpukan data yang diletakkan bertumpukkan. Stack menggunakan konsep yang bernama LIFO yang berarti Last in First Out, data yang terakhir dimasukkan merupakan data yang pertama kali diakses atau dikeluarkan. 

Terdapat 2 operasi di dalam Stack yang sering digunakan yaitu:

  1. Push: digunakan untuk menambahkan data pada Stack 
  2. Pop: digunakan untuk mengambil data pada Stack 


Queue adalah stuktur data linear dimana penambahan data dilakukan disatu sisi, disalah satu ujungnya, untuk penguruangannya dilakukan diujung lain, Queue menggunakan konsep FIFO yang berarti First in First Out, data yang pertama kali dimasukkan merupakan data yang pertama kali diakses.

Terdapat 2 operasi dalam Queue yang sering digunakan yaitu:
  1. Enqueue: digunakan untuk memasukkan sebuah data ke dalam queue. pada proses enqueue, bagian tail yang berjalan sendiri seiring dengan masuknya data baru ke dalam queue.
  2. Dequeue: digunakan untuk menghapuskan sebuah data yang paling pertama masuk ke dalam queue


Perbedaan antara Stack & Queue
  • Prinsip kerjanya, Stack menggunakan prinip kerja tumpukan sementara Queue menggunakan prinsip kerja antrian.
  • Konsep kerjanya, Stack menggunakan LIFO, Last in First Out sementara Queue menggunakan FIFO, First in First Out.
  • Pada proses penambahan dan penghapusan elemen, pada Stack operasi penambahan atau pengurangannya dilakukan pada satu ujungnya. Pada Queue operasi penambahan atau pengurangannya dilakukan di tempat yang berbeda.


Sumber:


Tuesday, February 25, 2020

LINKED LIST II



Single Linked List
adalah sebuah Linked List yang menggunakan satu variabel pointer saja untuk menyimpan banyak data.
Dalam single Linked List, pointer hanyak bergerak ke satu arah saya, kedepan/kebelakang.

Single Linked List dibagi menjadi 2 yaitu:
  1. Circular Single Linked List.
  2. Non Circular Single Linked List.

Circular Single Linked List
  • Adalah Single Linked List yang pointernya menunjuk pada dirinya sendiri, kata circular dalam Circular Single Linked List memiliki arti bahwa pointer selanjutnya akan menunjuk pada dirinya sendiri sehingga akan berputar.


Non Circular Single Linked List

  • Perbedaanya dengan Circular adalah Single Linked List ini, pointer selanjutnya tidak akan menunjuk pada dirinya sendiri sehingga tidak akan berputar.


Double Linked List
  • Adalah Linked List yang memiliki 2 variabel pointer yaitu pointer yang menunjuk pada node setelahnya dan satu lagi yang menunjuk pada node sebelumnya. Setiap head and tailnya menunjuk Null
  • Elemennya terdiri dari 3 bagian:
    1. Pointer next yang menunjuk elemen setelahnya
    2. Pointer prev yang menunjuk elemen sebelumnya
    3. Bagian data informasi

Circular Double Linked List
  • Adalah Linked List yang disetiap nodenya memiliki 3 field yaitu:
    1. 1 Field pointer menunjuk next
    2. 1 Field pointer menunjuk prev
    3. 1 Field yang berisi data dari node
  • Pointer next dan prevnya menunjuk kedirinya sendiri secara circular.
  • Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node setelahnya serta ke node sebelumnya
  • Untuk membuat node baru, pada awalnya pointer next dan prev akan menunjuk pada NULL
  • Selanjutnya pointer prev akan menunjuk ke yang sebelumnya dan next menunjuk pada node setelahnya






Final Summary

Final Summary Name: Ignatius Hansen NIM: 2301853275 Class: CB01-CL, LL01 Lecturer: Henry Chong (D4460), Ferdinand Ariandy Luwinda (D452...