NIM : 2301870653
Dosen Kelas Besar (CB-01):
- Ferdinand Ariandy Luwinda
- Henry Chong
Dosen Kelas Kecil (LP-01) :
- Wawan Cenggoro
-----------------------------------------------------------------------------------------------------------------------
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...
STACK AND QUEUE
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
HASHING AND BINARY TREE
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...
BINARY SEARCH TREE
BST (Binary Search Tree) adalah Tree yang bisa mempercepat pencarian, sorting data dengan tepat, memiliki kemudahan entri data dana penghapusan data. BST adalah binary tree namun memiliki kemampuan auto sorting.
BST pada anak kiri memiliki nilai yang lebih kecil daripada parentnya dan pada anak kanan memiliki nilai yang lebih besar dari parentnya.
1. Searching
Pencarian data mudah karena hanya perlu membandingkan data dengan root terlebih dahulu, jika lebih kecil maka akan lanjut pencarian ke kiri, dan apabila lebih besar dari root, maka melakukan pencarian ke kanan.
2. Insertion
Memulai memasukkan data dari root terlebih dahulu, apabila kosong maka data pertama akan menjadi root. dan sama halnya apabila data selanjutnya lebih kecil dari root maka data baru akan dibuat di sebelah kiri root, dan apabila data selanjutnya lebih besar dari root maka data baru akan dibuat di sebelah kanan root. Lakukan terus sampai menemukan node kosong yang bisa ditimpa dengan data baru.
3. Deletion
Jika data terdapat pada ujung tree (leaf), maka langsung hapus saja. Apabila memiliki 1 anak, tinggal sambungkan ke parent si data yang akan dihapus. Jika memiliki 2 anak, carilah data yang tepat untuk menggantikan data yang akan di delete, bagaiman mendapatkannya ? yaitu dengan melakukan pencarian data dari bagian kiri root lalu ke kanan sampai ditemukan data paling ujung (predecessor) atau bisa juga dengan melakukan pencarian data dari bagian kanan root lalu ke kiri sampai ditemukan data yang paling ujung (successor) kemudian replace data yang akan dihapus dengan data tersebut.
Namun dari semua advantage yang dimiliki BST, ada bagian dimana BST bisa menjadi tree yang sama saja seperti linkedlist biasa, misalkan akan mengisi data 1,2,3,4,5. apabila data pertama yang masuk 1 maka root = 1, dan 2,3,4,5 akan berada di bagian kanan dari root. Tidak ada bedanya dengan LinkedList, padahal tujuan dari BST sendiri agar mempermudah pencarian data. Nah hal ini disebut dengan Skewed Tree (kekanan terus / kekiri terus).
REVIEW
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.
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
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
Hashing & Binary Tree
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
Binary Tree, berarti sebuah tree yang memiliki 2 anak yaitu anak kiri dan anak kanan, berbeda dengan single linked list karena menunjukkan ke 1 data berikutnya, klo binary tree menunjuk ke 2 data selanjutnya.
Binary Searh Tree
BST (Binary Search Tree) adalah Tree yang bisa mempercepat pencarian, sorting data dengan tepat, memiliki kemudahan entri data dana penghapusan data. BST adalah binary tree namun memiliki kemampuan auto sorting.
BST pada anak kiri memiliki nilai yang lebih kecil daripada parentnya dan pada anak kanan memiliki nilai yang lebih besar dari parentnya.
1. Searching
Pencarian data mudah karena hanya perlu membandingkan data dengan root terlebih dahulu, jika lebih kecil maka akan lanjut pencarian ke kiri, dan apabila lebih besar dari root, maka melakukan pencarian ke kanan.
2. Insertion
Memulai memasukkan data dari root terlebih dahulu, apabila kosong maka data pertama akan menjadi root. dan sama halnya apabila data selanjutnya lebih kecil dari root maka data baru akan dibuat di sebelah kiri root, dan apabila data selanjutnya lebih besar dari root maka data baru akan dibuat di sebelah kanan root. Lakukan terus sampai menemukan node kosong yang bisa ditimpa dengan data baru.
3. Deletion
Jika data terdapat pada ujung tree (leaf), maka langsung hapus saja. Apabila memiliki 1 anak, tinggal sambungkan ke parent si data yang akan dihapus. Jika memiliki 2 anak, carilah data yang tepat untuk menggantikan data yang akan di delete, bagaiman mendapatkannya ? yaitu dengan melakukan pencarian data dari bagian kiri root lalu ke kanan sampai ditemukan data paling ujung (predecessor) atau bisa juga dengan melakukan pencarian data dari bagian kanan root lalu ke kiri sampai ditemukan data yang paling ujung (successor) kemudian replace data yang akan dihapus dengan data tersebut.
Namun dari semua advantage yang dimiliki BST, ada bagian dimana BST bisa menjadi tree yang sama saja seperti linkedlist biasa, misalkan akan mengisi data 1,2,3,4,5. apabila data pertama yang masuk 1 maka root = 1, dan 2,3,4,5 akan berada di bagian kanan dari root. Tidak ada bedanya dengan LinkedList, padahal tujuan dari BST sendiri agar mempermudah pencarian data. Nah hal ini disebut dengan Skewed Tree (kekanan terus / kekiri terus).
Sekian review materi dari
- Linked List
- Stack & Queue
- Hashing & Binary Tree
- Binary Search Tree
APRIL MARKET
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node{
char productName[1000];
int qty;
node *next;
}*head,*curr;
node *create(char productName[], int qty){
node *newnode = (node*) malloc (sizeof(node));
strcpy(newnode->productName,productName);
newnode->qty = qty;
newnode->next = NULL;
return newnode;
}
void insert(char productName[], int qty){
node *temp = create(productName, qty);
if(!head) head = temp;
else{
curr = head;
while(curr->next)curr = curr->next;
curr->next = temp;
}
}
void printAll(){
if(!head){
printf("Daftar belanja masih kosong\n");
return;
}
curr = head;
int i = 1;
while(curr){
printf("%-3d. %-10s %3d\n", i, curr->productName, curr->qty);
curr = curr->next;
i++;
}
}
void addItem(char productName[], int qty){
printf("Input item name: ");
scanf("%s", productName);
getchar();
printf("Input quantity: ");
getchar();
scanf("%d", &qty);
getchar();
getchar();
insert(productName,qty);
}
void editItem(char productName[]){
char userInput[100];
int newQuantity;
if(!head){
printf("Daftar belanja masih kosong\n");
getchar();
getchar();
return;
}
printf("Silahkan masukkan nama item yang mau dirubah: ");
scanf("%s", userInput);
curr = head;
while(curr){
if(strcmp(curr->productName,userInput) == 0){
printf("Silahkan masukkan jumlah barang yang baru: ");
scanf("%d", &newQuantity);
curr->qty = newQuantity;
getchar();
getchar();
return;
}
curr = curr->next;
}
}
void removeItem(){
if(!head){
printf("Daftar belanja masih kosong\n");
getchar();
getchar();
return;
}
printAll();
int counter = 1;
int userInput;
printf("Masukkan angka: ");
scanf("%d", &userInput);
curr = head;
if(counter == userInput){
head = curr->next;
curr->next = NULL;
free(curr);
getchar();
getchar();
return;
}
while(curr->next){
counter++;
if(counter == userInput){
node *temp = curr->next;
curr->next = curr->next->next;
temp->next = NULL;
free(temp);
getchar();
getchar();
return;
}
curr = curr->next;
}
printf("Angka yang anda masukkan salah\n");
getchar();
getchar();
}
void checkout(){
if(!head){
printf("Daftar belanja masih kosong\n");
getchar();
getchar();
return;
}
printAll();
int x = rand() % 1000000 + 10000;
printf("Total harga yang harus dibayarkan: %d\n", x);
getchar();
getchar();
}
int main(){
char productName[100];
int qty;
int choose;
do{
system("cls");
printf("AprilMarket\n");
printf("-----------------\n");
printf("[1]. Add Item\n");
printf("[2]. Edit Item\n");
printf("[3]. Remove Item\n");
printf("[4]. Checkout\n");
printf("[5]. Exit\n");
printf(">> ");
scanf("%d", &choose);
if(choose == 1){
system("cls");
addItem(productName, qty);
}
else if(choose == 2){
system("cls");
editItem(productName);
}
else if(choose == 3){
system("cls");
removeItem();
}
else if(choose == 4){
system("cls");
checkout();
}
}while(choose != 5);
printf(". . .Thank you. . .");
return 0;
}
AVL TREE
Balanced Binary Tree
Balanced Binary Tree adalah Tree yang memiliki minimal ketinggian root ke leaf-nya pada BST agar mencegah terjadinya kegagalan tree yaitu, skewed BST (yang datanya kekanan semua atau kekiri semua)AVL Tree
Dinamakan berdasarkan 2 penemunya yaitu Adelson-Veleskii dan E.M. Landis1. Menentukan Height:
- Height dari tree yang kosong adalah 0.
- Height dari sebuah node tanpa anak adalah 1.
- Height ditentukan dari height anaknya tertinggi (antara anak kiri dan anak kanan) lalu +1.
2. Menentukan Balanced factor:
- Dengan mencari perbandingan height anak kiri dan kanan (height anak kiri - height anak kanan atau sebaliknya).
- Dan disebut balance apabila nilainya tidak lebih dari 1 dan tidak kurang dari -1.
3. Insertion
- Insertnya seperti BST pada umumnya yaitu insert jika ada head dia akan mengecek apakah lebih kecil atau lebih besar dari head ? bila lebih kecil ke kiri dan apa bila lebih besar ke kanan.
- Namun ada yang membedakan yaitu harus disertakan rebalance
berikut beberapa case rebalance :
Misal A adalah node yang harus di rebalance.
Case 1 : node yang akan dimasukkan terletak di subtree kiri dari anak kiri si A.
Case 2 : node yang akan dimasukkan terletak di subtree kanan dari anak kanan si A.
Case 3 : node yang akan dimasukkan terletak di subtree kanan dari anak kiri si A.
Case 4 : node yang akan dimasukkan terletak di subtree kiri dari anak kanan si A.
Rotasi yang dilakukan saat rebalance :
- Single Rotation:
LL rotation: bentuk ke kiri dari root dan salahnya pada anak kirinya.
RR rotation: bentuk ke kanan dari root dan salahnya pada anak kanannya.
-Double Rotation:
LR rotation: bentuk ke kanan dari root dan salahnya pada anak kirinya.
RL rotation: bentuk ke kiri dari root dan salahnya pada anak kanannya.
4. Deletion
- Deletion di AVL tree seperti deletion BST yang mengambil antara successornya atau predecessornya
- Namun ada tambahan lagi bagi AVL karena setelah melakukan deletion ada kemungkinan bahwa treenya menjadi tidak balance lagi, maka dari itu kita haru melakukan rebalance kembali setelah melakukan deletion.
HEAPS AND TRIES
Heaps adalah Binary Tree yang terdiri dari 2 anak seperti layaknya BST namun memiliki 2 konsep yaitu :
- Max Heap
- Min Heap
Max Heap artinya nilai parent lebih besar dibandingkan dengan anaknya
Min Heap artinya nilai parent lebih kecil dibandingkan dengan anaknya
Heaps biasanya diimplementasikan di Array
seperti pada gambar dibawah ini:
Seperti pada gambar, heaps index dimulai dari 1 karena untuk mempermudah melakukan perhitungan sebuah lokasi nodenya
ini adalah rumus indexnya
Parent = x/2
L-Child = 2*x
R-Child = 2*x+1
untuk pencarian data terkecil di Min Heap sudah pasti terletak pada root
untuk pencarian data terbesar di Max Heap sudah pasti terletak pada root
Insertion
Min Heap : apabila pada tree di insert nilai yang kecil dibandingkan dengan parentnya, otomatis akan melakukan penukaran nilai child dengan parentnya, hal ini dilakukan secara terus menerus sampai bertemu parent yang nilainya lebih kecil dibandingkan yang di insert.
Max Heap : apabila pada tree di insert nilai yang besar dibandingkan dengan parentnya, otomatis akan melakukan penukaran nilai child dengan parentnya, hal ini dilakukan secara terus menerus sampai bertemu parent yang nilainya lebih besar dibandingkan yang di insert.
Mix Max Heap : Karena setiap level berbeda beda jenis heap, misalkan pada level 0 itu Min Heap, maka level 1 itu Max Heap, selanjutnya akan ditentukan dengan ganjil genap levelnya. bagaimana insertionnya ? sama seperti Min Heap dan Max Heap hanya saja terdapat perbedaan saat melakukan proses koding atau algorithmnya yaitu setiap mau mengecek antara nilai child dan parentnya, harus memperhatikan levelnya setiap bertemu level genap maka akan melakukan pengecekan insert Min Heap, dan jika bertemu level ganjil akan melakukan pengecekan insert Max Heap.
Deletion
Min Heap : saat mendelete akan mengambil element terakhir pada tree untuk menggantikan posisinya, lalu melakukan downheapmin yang berarti melakukan pengecekan ke anaknya apakah ada nilai yang lebih kecil dari nilai anaknya.
Max Heap : saat mendelete akan mengambil element terakhir pada tree untuk menggantikan posisinya, lalu melakukan downheapmax yang berarti melakukan pengecekan ke anaknya apakah ada nilai yang lebih besar dari nilai anaknya.
Min Max Heap : saat mendelete akan mengambil element terakhir pada tree untuk menggantikan posisinya, lalu melakukan downheapmax/downheap min tergantung pada level berapa yang di delete.
Heap Complexity :
- Searching : O(1)
- Insert : O(log(n))
- Delete : O(log(n))
Applications of Heaps :
- Heap Sort
- Selection Algorithms
- Graph Algoriths
Tries, adalah tree yang setiap nodenya terdapat sebuah huruf, rootnya berisikan empty character
Gambar diatas adalah contoh dari Tries
Sekian penjelasan singkat tentang Heaps dan Tries.
