Review 1: Materi UTS

Angelia

2301854492

COMP6048 - CB01

SINGLE LINKED LIST

1. Pengertian Single Linked List
Single Linked List merupakan kumpulan data yang terhubung dengan 1 pointer, yaitu pointer yang merujuk ke data setelahnya. (Penjelasan lebih lengkap ada pada Double Linked List, karena materi DLL lebih dulu dibuat).

2. Implementasi Single Linked List
Dokumentasi hasil code di lab:
#include<stdio.h>
#include<stdlib.h>

struct Data{
int value;
Data *next;
}*head = NULL, *tail = NULL, *current;

int value;
void inputNilai(){
printf("Masukkan Nilai \t: ");
scanf("%d", &value);
getchar();
}

void pushDepan(int value){
current = (struct Data*) malloc(sizeof(Data));
current->value = value;
current->next = NULL;
if(head == NULL){
head = tail = current;
}
else{
current->next = head;
head = current;
}
}

void pushBelakang(int value){
current = (struct Data*) malloc(sizeof(Data));
current->value = value;
current->next = NULL;
if(head == NULL){
head = tail = current;
}
else{
tail->next = current;
tail = current;
}
}

void pushMid(int value){
//No Data
if(head == NULL) pushDepan(value);
else if(value < head->value) pushDepan(value);
else if(value > tail->value) pushBelakang(value);
else{
current = (struct Data*) malloc(sizeof(Data));
current->value = value;
current->next = NULL;
Data *temp = head;
while(temp->next->value < value){
temp = temp->next;
}
current->next = temp->next;
temp->next = current;
}
}

void popDepan(){
//No Data
if(head == NULL) printf("Pop Failed!\nNo Data!\n");
else{
current = head;
if(head == tail){
//Data = 1
free(current);
head = tail = NULL;
}
else{
//Data > 1
head = head->next;
free(current);
}
}
}

void popBelakang(){
//No Data
if(head == NULL) printf("Pop Failed!\nNo Data!\n");
else{
current = head;
if(head == tail){
//Data = 1
free(current);
head = tail = NULL;
}
else{
//Data > 1
while(current->next != tail){
current = current->next;
}
free(tail);
tail = current;
tail->next = NULL;
}
}
}

void popMid(int value){
if(head == NULL) printf("Pop Failed!\nNo Data!\n");
else if(value == head->value) popDepan();
else if(value == tail->value) popBelakang();
else{
current = head;
Data *temp = head;
while(current != NULL && current->value != value){
temp = current;
current = current->next;
}
if(current == NULL) printf("Pop(%d) Failed!\n%d is not found!\n", value, value);
else{
temp->next = current->next;
free(current);
printf("Data %d Deleted!\n", value);
}
}
}

void cetak(){
current = head;
while(current != NULL){
printf("%d\n", current->value);
current = current->next;
}
}

int main(){
int choose = -1;
do{
printf("===== SINGLE LINKED LIST MENU =====\n");
printf("1. Add Data (Front)\n");
printf("2. Add Data (End)\n");
printf("3. Add Data Mid [Sorted Data]\n");
printf("4. Delete First Data\n");
printf("5. Delete Last Data\n");
printf("6. Delete Targeted Data [Sorted Data]\n");
printf("7. View Data\n");
printf("8. Exit\n");
printf("Choose >> ");
scanf("%d", &choose);
getchar();

switch(choose){
case 1:
inputNilai();
pushDepan(value);
printf("Insert Front Data Success!\n");
break;
case 2:
inputNilai();
pushBelakang(value);
printf("Insert Back Data Success!\n");
break;
case 3:
inputNilai();
pushMid(value);
printf("Insert Mid Data Success!\n");
break;
case 4:
popDepan();
printf("First Data Deleted!\n");
break;
case 5:
popBelakang();
printf("Last Data Deleted!\n");
break;
case 6:
inputNilai();
popMid(value);
break;
case 7:
cetak();
break;
case 8:
printf("Anda keluar aplikasi");
break;
}

printf("\nPress ENTER to continue...");
getchar();
}
while(choose != 8);

}

DOUBLE LINKED LIST

1. Pengertian Double Linked List
Double Linked List merupakan kumpulan data yang terhubung dengan 2 pointer, satu pointer merujuk pada data setelahnya dan satu pointer merujuk pada data sebelumnya.

2. Perbedaan 'Double Linked List' dengan 'Single Linked List'
Tak jauh berbeda dengan materi single linked list, double linked list memiliki konsep yang sama. Sebagai ilustrasi, single linked list hanya dapat berpegangan menggunakan tangan kanan saja (arah akses pointer hanya ke kanan saja, 1 pointer penunjuk), sedangkan double linked list dapat berpegangan menggunakan tangan kiri dan kanan (arah akses pointer dapat ke kiri dan ke kanan, 2 pointer penunjuk).

3. Model Double Linked List
* Default Linked List
Model Linked List ini (Double Linked List) dapat mengakses data sebelum dan sesudahnya, namun jika node berada di bagian akhir/awal data, salah satu pointernya tidak dapat mengakses data selanjutnya atau sebelumnya.

Penjelasan:

Sumber: Geeksforgeeks.org

Berdasarkan contoh gambar di atas, jika node berada di value data 'A' maka pointer ke kiri (kembali ke data paling akhir) untuk mengakses value data 'D' tidak ada/tidak bisa. Begitu pula dengan kondisi jika node berada di value data 'D' maka pointer ke kanan (kembali ke data paling awal) untuk mengakses value data 'A' tidak ada/tidak bisa.

* Circular Linked List
Model Linked List ini dapat mengakses data sebelum dan sesudahnya, serta model Circular ini dapat mengakses data paling awal saat node berada pada data paling akhir dan dapat mengakses data paling akhir saat node berada pada data paling awal.

Penjelasan:

Sumber: Geeksforgeeks.org

Berdasarkan contoh gambar di atas, ketika node berada pada data paling awal (katakanlah Data 'A') maka model ini memiliki fitur untuk mengakses data paling akhir (katakanlah Data 'C'). Begitu pula sebaliknya, ketika posisi node berada di Data 'C', maka dapat mengakses data yang posisinya berada paling awal (Data 'A').

Perbedaan model ini dengan model yang biasanya adalah pada fitur yaitu jika posisi node berada di bagian paling awal/akhir data, maka node tersebut dapat pula mengakses posisi data yang berada di bagian paling akhir/awal data tersebut (lawan ujung dari posisi node).

Tambahan:
Model ini juga diterapkan untuk 'Circular Single Linked List'.

Sumber: javatpoint.com

Perbedaan 'Circular Double Linked List' dengan 'Circular Single Linked List' hanya terletak pada pengizinan akses pointernya saja, dimana untuk Circular Double Linked List memiliki 2 pointer penunjuk (bisa mengakses data sebelum dan sesudahnya) sedangkan untuk Circular Single Linked List hanya memiliki 1 pointer penunjuk (hanya bisa mengakses data selanjutnya saja). Untuk fitur model 'Circular'nya sendiri memiliki fungsionalitas yang sama, yaitu agar dapat mengakses data yang posisinya berada di bagian paling awal/akhir ketika node berada di posisi paling akhir/awal (ujung yang berlawanan).

4. Implementasi Penggunaan Double Linked List
Dokumentasi hasil code di lab
#include<stdio.h>
#include<stdlib.h>

struct Data{
int value;
Data *next, *prev;
}*head = NULL, *tail = NULL, *current;

int value;
void inputNilai(){
printf("Masukkan Nilai \t: ");
scanf("%d", &value);
getchar();
}

void pushDepan(int value){
current = (struct Data*) malloc(sizeof(Data));
current->value = value;
current->next = NULL;
current->prev = NULL;
if(head == NULL){
head = tail = current;
}
else{
current->next = head;
head->prev = current;
head = current;
}
}

void pushBelakang(int value){
current = (struct Data*) malloc(sizeof(Data));
current->value = value;
current->next = NULL;
current->prev = NULL;
if(head == NULL){
head = tail = current;
}
else{
tail->next = current;
current->prev = tail;
tail = current;
}
}

void pushMid(int value){
//No Data
if(head == NULL) pushDepan(value);
else if(value < head->value) pushDepan(value);
else if(value > tail->value) pushBelakang(value);
else{
current = (struct Data*) malloc(sizeof(Data));
current->value = value;
current->next = NULL;
current->prev = NULL;

Data *temp = head;
while(temp->next->value < value){
temp = temp->next;
}
current->next = temp->next;
current->prev = temp;
temp->next->prev = current;
temp->next = current;
}
}

void popDepan(){
//No Data
if(head == NULL) printf("Pop Failed!\nNo Data!\n");
else{
current = head;
if(head == tail){
//Data = 1
free(current);
head = tail = NULL;
}
else{
//Data > 1
head = head->next;
free(current);
head->prev = NULL;
}
}
}

void popBelakang(){
//No Data
if(head == NULL) printf("Pop Failed!\nNo Data!\n");
else{
current = tail;
if(head == tail){
//Data = 1
free(current);
head = tail = NULL;
}
else{
//Data > 1
tail = current->prev;
free(current);
tail->next = NULL;
}
}
}

void popMid(int value){
if(head == NULL) printf("Pop Failed!\nNo Data!\n");
else if(value == head->value) popDepan();
else if(value == tail->value) popBelakang();
else{
current = head;
while(current != NULL && current->value != value){
current = current->next;
}
if(current == NULL) printf("Pop(%d) Failed!\n%d is not found!\n", value, value);
else{
current->prev->next = current->next;
current->next->prev = current->prev;
free(current);
printf("Data %d Deleted!\n", value);
}
}
}

void cetak(){
current = head;
while(current != NULL){
printf("%d\n", current->value);
current = current->next;
}
}

int main(){
int choose = -1;
do{
printf("===== DOUBLE LINKED LIST MENU =====\n");
printf("1. Add Data Mid [Sorted Data]\n");
printf("2. Delete Targeted Data [Sorted Data]\n");
printf("3. View Data\n");
printf("4. Exit\n");
printf("Choose >> ");
scanf("%d", &choose);
getchar();

switch(choose){
case 1:
inputNilai();
pushMid(value);
printf("Insert Mid Data Success!\n");
break;
case 2:
inputNilai();
popMid(value);
break;
case 3:
cetak();
break;
case 4:
printf("Anda keluar aplikasi");
break;
}

printf("\nPress ENTER to continue...");
getchar();
}
while(choose != 4);

}

PUSH AND POP MID (DIRECT SORTED DLL) CODE IMPLEMENTATION

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

struct node{
int value;
struct node *next, *prev;
} *head = NULL, *tail = NULL, *curr;

void push_mid(int x){
curr = (struct node*)malloc(sizeof(struct node));
curr->value = x;
curr->next = curr->prev = NULL;

if(head == NULL){
head = tail = curr;
}
else if (x < head->value){
//push head
curr->next = head;
head->prev = curr;
head = curr;
}
else if (x > tail->value){
//push tail
tail->next = curr;
curr->prev = tail;
tail = curr;
}
else{
node* temp = head;
while(temp->next->value < x){
temp = temp->next;
}
curr->next = temp->next;
temp->next->prev = curr;
temp->next = curr;
curr->prev = temp;
}
}

void pop(int x){
if (head == NULL){
puts("Pop(x) failed! No Data in LL");
}
else if(head == tail){
//only 1 data
free(head);
head = tail = NULL;
}
else if(x == head->value){
//data located at head
curr = head;
head = head->next;
free(curr);
head->prev = NULL;
}
else if(x == tail->value){
//data located at tail
curr = tail;
tail = tail->prev;
free(curr);
tail->next = NULL;
}
else{
curr = head;
while(curr != NULL && curr->value != x){
curr = curr->next;
}
if(curr == NULL){
puts("Pop(x) failed. x is not found!");
}
else{
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
free(curr);
}
}
}


void print_all(){
curr = head; //point to first data
while( curr != NULL )
{
printf("%d ",curr->value);
curr = curr->next;
}
}

int main()
{
push_mid(15);
push_mid(50);
push_mid(99);
push_mid(20);
push_mid(30);
push_mid(25);
push_mid(100);
pop(200);
pop(50);
pop(15);
pop(100);
pop(30);
push_mid(200);
print_all();
return 0;
}

STACK AND QUEUE

Stack and queue merupakan konsep keluar masuk data.
1. Stack
Konsep stack mirip seperti LIFO (Last In First Out). Jadi, data paling akhir yang masuk, data itu yang akan dikeluarkan terlebih dahulu. Pemisalan konsep seperti penumpukkan buku, dimana buku paling atas yaitu buku yang paling terakhir dimasukkan yang akan dikeluarkan terlebih dahulu.

Jenis Linked List yang digunakan: pushDepan dan popDepan, pushBelakang dan popBelakang.
Implementasi Stack: Konversi Infix ke Prefix atau Postfix.

2. Queue
Konsep queue mirip seperti FIFO (First In First Out). Jadi, data yang paling awal masuk, data itulah yang akan dikeluarkan terlebih dahulu. Pemahaman konsep termudah adalah seperti kegiatan mengantri, dimana orang paling depan akan keluar terlebih dahulu.

Jenis Linked List yang digunakan: pushDepan dan popBelakang, pushBelakang dan popDepan.

HASHING DAN HASH TABLES

Pengertian Hashing
Jadi, hashing merupakan teknik yang digunakan untuk mengubah string dengan panjang yang asli menjadi lebih pendek.
Teknik hashing ini biasa digunakan untuk mengambil suatu item dari database. Teknik ini dipilih karena item bisa ditemukan lebih cepat dengan menggunakan kunci hash daripada menggunakan nilai asli.
Hashing juga merupakan konsep mendistribusikan kunci dalam array (table hash) menggunakan fungsi hash.

Fungsi Hash

Sumber: https://en.wikipedia.org/wiki/Hash_function

Pengertian Hash Table
Hash table menjadi tempat penyimpanan string sementara.
Index tabel adalah kunci hashnya, kemudian value tabel adalah string aslinya.
Ukuran hash table bisa lebih sedikit dibandingkan jumlah string asli yang ada, karena beberapa string dapat memiliki kunci hash yang sama.

Contoh Konsep Hash
Soal:
Menyimpan 5 string: define, atan, char, float, exp dengan fungsi hash "ubah karakter dari tiap string menjadi angka mulai dari 0...25"

Dari soal tersebut, maka dapat diklasifikasikan:
a) Index tabel adalah angka 0...25
b) Fungsi hash adalah "ubah karakter dari tiap string menjadi angka mulai dari 0...25"
c) Value tabel adalah define, atan, char, float, exp

Maka, dari penjabaran di atas, dapat disesuaikan bahwa
indeks 0 diisi dengan string atan karena awal karakternya 'a'.
indeks 1 kosong karena tidak ada string yang awal karakternya 'b'.
indeks 2 diisi dengan string char karena awal karakternya 'c'.
indeks 3 diisi dengan string define karena awal karakternya 'd'.
indeks 4 diisi dengan string exp karena awal karakternya 'e'.
indeks 5 diisi dengan string float karena awal karakternya 'f'.
dst

Dari, pengelompokkan di atas, maka didapat hash table sebagai berikut:

Hash Table

Sumber: PPT Binus Maya

Metode-Metode Fungsi Hash

Ada beberapa metode yang digunakan sebagai fungsi hash, diantaranya:

• Mid-square

Metode ini dilakukan dengan:

1) Memangkatkan value (jika value string, convert jadi angka) dengan pangkat dua

2) Mengambil angka di tengah dari hasil pangkat dua tersebut yang kemudian dikonversi menjadi nilai bit

Contoh:

Valuenya adalah 3121. Maka 3121 akan dipangkatkan dengan dua menjadi 9740641. Dari hasil pangkat dua, diambil angka di tengahnya yaitu 406. 

Hasil pangkat dua dari 3121 dalam bentuk bit adalah 1001010-0101000010-1100001. Nilai 0101000010 (angka tengah dari hasil pangkat dua 3121) akan diambil menjadi key hashnya.

• Division

Metode ini menggunakan modulus.

Rumusnya bisa dengan menggunakan angka 64 ditambah nilai urutan huruf (1...26)

Jumlah angka yang didapat akan dimodulus dengan 97.

Contohnya:

"COBB" akan disimpan di index = ((64+3) + (64+15) + (64+2) + (64+2)) % 97 = 88

Maka value "COBB" akan disimpan di index h[88].

• Folding

Metode ini menggunakan konsep 'melipat' yaitu dengan memecah value menjadi beberapa bagian yang masing-masing memiliki 2 digit yang kemudian akan dijumlahkan kemudian 2 angka terakhir dari hasil penjumlahan digunakan sebagai indeks hash.

Contoh:

a) 34567

dipecah per 2 digit menjadi: 34, 56, dan 7

kemudian dijumlahkan: 34 + 56 + 7 = 97

maka indeks hash untuk menyimpan value 34567 adalah h[97].

b) 5678

dipecah per 2 digit: 56 dan 78

dijumlahkan: 56 + 78 = 134

diambil 2 angka terakhir: 34

maka indeks hash untuk menyimpan value 5678 adalah h[34].

• Digit Extraction

Metode ini mengambil value dari digit angka tertentu untuk dijadikan kunci hash.

Contoh:

Nilai 14568

akan diambil value dari digit yang ganjil: digit ke-1,3,5 -> 158

maka indeks hash untuk menyimpan value 14568 adalah h[138].

• Rotating Hash

Metode ini merupakan metode tambahan setelah melakukan metode yang lain (folding, mid-square, division, dsb).

Setelah mendapatkan kunci hash dari fungsi hash sebelumnya, maka akan dilakukan rotasi.

Contoh:

Alamat hash sebelumnya -> Alamat hash setelah dirotasi

600101 -> 160010

600102 -> 260010

600103 -> 360010

(Note: value digit paling terakhir, pindah posisi ke paling depan)

Collision

Collision adalah kondisi dimana ada 2 value yang memiliki kunci hash/indeks hash yang sama.

Contoh lanjutan dari 5 string sebelumnya (ada tambahan):

define, atan, char, float, exp, ceil, acos, floor

Pembahasan:

Jika menggunakan fungsi hash "ubah karakter dari tiap string menjadi angka mulai dari 0...25", maka ada beberapa value yang memiliki kunci hash yang sama.

(atan dan acos berada di h[0], char dan ceil berada di h[2], float dan floor berada di h[5]).

Peristiwa ini disebut Collision.

Ada beberapa cara mengatasi Collision:

• Linear Probing

Metode ini akan mencari slot kosong selanjutnya kemudian meletakkan string tersebut di situ.

Contoh soal sebelumnya:

#Jika disesuaikan dengan soal sekarang (sebelum dilakukan Linear Probing) maka:

h[0] = atan, acos

h[1] = null

h[2] = char, ceil

h[3] = define

h[4] = exp

h[5] = float, floor

Setelah ditambahkan beberapa value string di soal baru (acos, ceil, dan floor) maka ada beberapa value yang berada di indeks yang sama.

Dengan menggunakan 'Linear Probing', maka value selanjutnya yang berada di indeks yang sama akan diletakkan pada slot selanjutnya yang kosong, sehingga menjadi:

Kelemahan: Sulit dilakukan pencarian bila terdapat banyak Collision, karena jika ingin mencari ceil mulai dari indeks ke-2 akan lanjut iterasi hingga menemukan value ceil (2->3->4->5->6) sebanyak 5 step.

Implementasi Code:

char data[TABLE_SIZE][100];

void linearProbing(int key, char name[]){
if(strcmp(data[key],"") == 0 ){
strcpy(data[key],name);
}else{
for(i=key+1; i<TABLE_SIZE ; i++ ){
if(i == key){
printf("Failed to insert %s because TABLE is FULL\n",name);
break;
}

if(strcmp(data[i],"") == 0 ){
strcpy(data[i],name);
break;
}

if (i == TABLE_SIZE -1) i = -1;
}
}
}

void print(){
for(i = 0;i<TABLE_SIZE;i++){
printf("%d. %s\n",i,data[i]);
}
}

• Chaining

Meletakkan string di slot sebagai sebuah chained list (linked list).

Dalam metode chaining ini, value tetap akan diletakkan pada indeks yang sama, hanya saja dijadikan dalam bentuk linked list. Maka, jika terdapat Collision, kita hanya perlu melakukan iterasi di indeks tersebut saja.

Implementasi Code:

struct list{

char name[100];

struct list* next;

}*head[TABLE_SIZE],*tail[TABLE_SIZE], *curr;

int i;

void chaining(int key, char name[]){

curr = (struct data*) malloc (sizeof(struct list));

strcpy(curr->name,name);

curr->next = 0;

if (head[key] == NULL){

head[key] = tail[key] = curr;

}

else{

tail[key]->next = curr;

tail[key] = curr;

}

}

void view(){

for(i=0 ; i< TABLE_SIZE; i++){

if(head[i] == NULL){

printf("%d. \n");

}

else{

printf("%d. ",i);

curr = head[i];

while (curr != NULL){

printf("%s->", curr->name);

curr = curr->next;

}

puts("");

}

}

}

TREE DAN BINARY TREE

Pengertian Tree

Tree merupakan struktur data yang tidak linear, sifatnya hierarki (bertingkat), dan mewakili hubungan hierarkis di antara objek data. 

Tree adalah kumpulan dari satu atau lebih nodes.

Node di pohon dapat disimpan di mana saja dan dihubungkan oleh pointer.

Konsep Binary Tree

Binary Tree merupakan tree yang memiliki anak cabang maksimal 2 pada tiap nodenya.

Tipe Binary Tree:

• Perfect Binary Tree

Binary Tree yang tiap nodenya ( kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

• 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.

• Skewed Binary Tree

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

• Balanced Binary Tree

Merupakan pohon biner di mana tidak ada daun yang lebih jauh dari akar daripada daun lainnya (skema penyeimbangan yang berbeda memungkinkan definisi yang berbeda dari "jauh lebih jauh").

Sumber: https://www.growingwiththeweb.com/2015/11/check-if-a-binary-tree-is-balanced.html

Property Binary Tree

Formula untuk menghitung jumlah node per level: 2^n

Level dimulai dari n = 0.

Maka, jumlah maksimum nodes dari tree dengan height 3 adalah 1+2+4+8 = 15.

Minimum tinggi binary tree dari n nodes adalah 2log(n).

Maksimum tinggi binary tree dari n nodes adalah n - 1. => (skewed binary tree memiliki height tree maksimum).

Implementasi Binary Tree

• Menggunakan Array

Indeks di array mewakili nomor node

Indeks untuk node root adalah 0.

Indeks Anak Kiri adalah 2p + 1 (p adalah indeks parent)

Indeks Anak Kanan adalah 2p+2 

Indeks parent adalah (p-1)/2

• Menggunakan Linked List

struct node {

int data;

struct node *left;

struct node *right;

struct node *parent;

};

struct node *root = NULL;

IMPLEMENTASI HASHING DALAM BLOCKCHAIN

Berdasarkan pembahasan di atas, maka hashing ini kerap kali digunakan dalam konsep blockchain. Dikenal dengan metode 'Kriptografi' yaitu ilmu yang mempelajari teknik-teknik matematika yang berhubungan dengan aspek keamanan informasi, seperti kerahasiaan data, keabsahan data, integritas data, serta autentikasi data.

Pada prinsipnya, Kriptografi memiliki 4 komponen utama yaitu :
1.            Plaintext, yaitu pesan yang dapat dibaca
2.            Ciphertext, yaitu pesan acak yang tidak dapat dibaca
3.            Key, yaitu kunci untuk melakukan teknik kriptografi
4.            Algorithm, yaitu metode untuk melakukan enkrispi dan dekripsi

Kemudian, proses dasar yang umumnya ada pada Kriptografi yaitu:
1.            Enkripsi (Encryption), proses menjadikan pesan yang dapat dibaca (plaintext) menjadi pesan acak yang tidak dapat dibaca (ciphertext).
2.            Dekripsi (Decryption), proses kebalikan dari enkripsi dimana proses ini akan mengubah ciphertext menjadi plaintext dengan menggunakan algoritma "pembalik" dan key yang sama.

Kode-kode asing yang sering kita lihat dalam proses encryption dan decryption merupakan salah satu contoh hash. Hash mampu mengubah setiap data yang mengalami perubahan dengan nilai unik sendiri.

Nilai berharga sebuah data saat ini berpotensi dibobol atau diketahui oleh orang lain. Salah satu teknik mengakalinya ialah dengan pemberian kode unik. 

Ada sejumlah hash yang digunakan saat ini seperti:

• SHA256

Hash ini digunakan pada Bitcoin khusus proses transaksi dan perhitungan nilai Hash.

• RIPEMD160

Hash RIPEMD160 merupakan singkat dari Race Integrity Primitive Evaluation Message Digest. Konsep dari algoritma dari hash ini dikembangkan oleh MD4. Jumlah data transaksi yang dihasilkan lebih kecil dibandingkan SHA256 yaitu hanya 160 bit.

• Monero

Pada Monero, penerapan pada keamanan data menggunakan sejumlah Hash, mulai dari Keccak, Blake, Grostl, JH, dan Skein pada CryptoNote. Konsep dari Monero yang sangat kompleks seakan membuatnya dijuluki sebagai fully anonymous.

Jadi, konsep Hash ini sangat penting dan sering digunakan dalam konsep Blockchain. Teknik Hash ini digunakan untuk melakukan enkripsi terhadap data dengan mengubah value asli dari data menjadi sebuah kode yang unik yang bertujuan untuk menjaga privasi data user dan terhindar dari pencurian data. Konsep ini sering kita dengar seperti dalam penggunaannya di Bitcoin.

INFIX TO PREFIX OR POSTFIX USING STACK AND EXPRESSION TREE

CONVERSION USING STACK

Syaratnya semua operator masuk stack dan semua operand masuk ke string.

Conversion Infix to Postfix:

• dibaca dari kiri ke kanan
• Bisa cek manual dengan menghitung 2 operand dan 1 operator dari kiri hingga selesai
• Syarat: Jika operator lama tingkatnya lebih tinggi atau setara dari operator yang baru masuk, maka masukkan operand sebelumnya ke string. Lalu, jika ada tanda '(' maka masukkan semua operator yang ada dan dikeluarkan secara stack ketika ketemu tanda ')'.

String	Stack	Postfix String	Operation
(A-B/C)*(D/E+F)
(A-B/C)*(D/E+F)	(		push(()
(A-B/C)*(D/E+F)	(	A	add(A)
(A-B/C)*(D/E+F)	( -	A	push(-)
(A-B/C)*(D/E+F)	( -	AB	add(B)
(A-B/C)*(D/E+F)	( - /	AB	push(/)
(A-B/C)*(D/E+F)	( - /	ABC	add(C)
(A-B/C)*(D/E+F)		ABC/-	pop(/), pop(-), pop(()
(A-B/C)*(D/E+F)	*	ABC/-	push(*)
(A-B/C)*(D/E+F)	* (	ABC/-	push(()
(A-B/C)*(D/E+F)	* (	ABC/-D	add(D)
(A-B/C)*(D/E+F)	* ( /	ABC/-D	push(/)
(A-B/C)*(D/E+F)	* ( /	ABC/-DE	add(E)
(A-B/C)*(D/E+F)	* ( +	ABC/-DE/	pop(/), push(+)
(A-B/C)*(D/E+F)	* ( +	ABC/-DE/F	add(F)
(A-B/C)*(D/E+F)		ABC/-DE/F+*	pop(+), pop((), pop(*)

Conversion Infix to Prefix:

• dibaca dari kanan ke kiri
• Bisa cek manual dengan menghitung 2 operand dan 1 operator dari kanan hingga selesai
• Syarat: Jika operator lama tingkatnya lebih tinggi dari operator yang baru masuk, maka masukkan operand sebelumnya ke string. Lalu, jika ada tanda ')' maka masukkan semua operator yang ada dan dikeluarkan secara stack ketika ketemu tanda '('.

String	Stack	Prefix String	Operation
(A-B/C)*(D/E+F)
(A-B/C)*(D/E+F)	)		push())
(A-B/C)*(D/E+F)	)	F	add(F)
(A-B/C)*(D/E+F)	) +	F	push(+)
(A-B/C)*(D/E+F)	) +	EF	add(E)
(A-B/C)*(D/E+F)	) + /	EF	push(/)
(A-B/C)*(D/E+F)	) + /	DEF	add(D)
(A-B/C)*(D/E+F)		+/DEF	pop(/), pop(+), pop())
(A-B/C)*(D/E+F)	*	+/DEF	push(*)
(A-B/C)*(D/E+F)	) *	+/DEF	push())
(A-B/C)*(D/E+F)	) *	C+/DEF	add(C)
(A-B/C)*(D/E+F)	) * /	C+/DEF	push(/)
(A-B/C)*(D/E+F)	) * /	BC+/DEF	add(B)
(A-B/C)*(D/E+F)	) * -	/BC+/DEF	pop(/), push(-)
(A-B/C)*(D/E+F)	) * -	A/BC+/DEF	add(A)
(A-B/C)*(D/E+F)		*-A/BC+/DEF	pop(-), pop(*), pop())

CONVERSION USING EXPRESSION TREE

Alur baca konsep prefix  : Parent - Left - Right

Alur baca konsep postfix: Left - Right - Parent 

Alur baca konsep infix    : Left - Parent - Right

INFIX

POSTFIX

PREFIX

BINARY SEARCH TREE

A. Pengertian Binary Search Tree
Binary Search Tree atau biasa disingkat BST merupakan salah satu struktur data yang mempercepat pencarian dan pengurutan (sorting), dengan metode insertion dan deletion yang mudah. BST dikenal juga sebagai binary tree yang diurutkan (sorted version of Binary Tree).


B. Properti Binary Tree
Berikut ini penjelasan properti di Binary Search Tree:

Sumber: Geeksforgeeks.org

Menggunakan contoh dari gambar di atas, maka akan dijelaskan macam-macam istilah dalam BST:
- Root    : Berperan sebagai akar paling atas/pusatnya tree, yaitu angka 8.
- Parent  : Node yang berada satu level di atas suatu node tertentu, contohnya angka 3 adalah parent node dari angka 1 dan angka 6.
- Child   : Node yang berada satu level di bawah suatu node tertentu, contohnya angka 14 adalah child node dari angka 10.
- Leaf     : Node yang tidak memiliki child, contohnya angka 1, 4, 7, dan 13.
- Sibling : Node yang memiliki parent yang sama, contohnya angka 1 dan angka 6.


C. Konsep Binary Search Tree
Binary Tree memiliki akar atau yang disebut root node dan memiliki 2 sisi cabang tree yaitu tree cabang kiri dan tree cabang kanan.

Tree cabang kiri akan selalu menampung value yang lebih kecil dari value parentnya, sedangkan
tree cabang kanan akan selalu menampung value yang lebih besar dari value parentnya.

Binary Tree memiliki syarat yaitu batas maksimum anak dari node parent adalah 2 child nodes.

Simulasi alur penempatan value di BST (dengan root angka '8' dan inputan angka '4':

1. Cek apakah nilai 4 lebih kecil/besar dari root 8, ternyata lebih kecil maka masuk ke cabang tree kiri.
2. Cek apakah cabang di root 8 sudah ada 2 child nodes? Ya, maka perlu turun cabang.
3. Cek apakah 4 lebih kecil/besar dari 3, ternyata lebih besar maka masuk ke cabang tree kanan.
4. Cek apakah cabang di node 3 sudah ada 2 child nodes? Ya, maka perlu turun cabang.
5. Cek apakah 4 lebih kecil/besar dari 6, ternyata lebih kecil maka masuk ke cabang tree kiri.
6. Cek apakah cabang di node 6 sudah ada 2 child nodes? Tidak/belum, maka value 4 diletakkan di cabang sebelah kiri dari parent node 6.

D. Operasi Binary Search Tree
//Buat struct untuk node
struct node{
int key;
struct node *left;
struct node *right;
};

//Pembuatan node baru
struct node *newNode(int x){
//Pesan space memory ke komputer
struct node *currNewNode = (struct node*) malloc(sizeof(struct node));
//Masukkan value
currNewNode->key = x;
//Set child kiri NULL
currNewNode->left = NULL;
//Set child kanan NULL
currNewNode->right = NULL;

//Return alamat dari currNewNode;
return currNewNode;
}

//Insert new node
struct node *add(struct node *root, int x){
//Saat ketemu root yang kosong, new node diletakkan di sini
if(root == NULL) return newNode(x);
//Jika value lebih kecil dari root, rekursif ke child kiri
else if(x < root->key) root->left = add(root->left, x);
//Jika value lebih besar dari root, rekursif ke child kanan
else if(x > root->key) root->right = add(root->right, x);

//Return alamat root
return root;
}

//Print BST secara Infix
void printAllInfix(struct node *root){
//Kalau ketemu rootnya NULL, maka balik
if(root == NULL) return;
//Rekursif ke child kiri
printAllInfix(root->left);
//Print value
printf(" %d ", root->key);
//Rekursif ke child kanan
printAllInfix(root->right);
}

//Print BST secara Prefix
void printAllPrefix(struct node *root){
//Kalau ketemu rootnya NULL, maka balik
if(root == NULL) return;
//Print value
printf(" %d ", root->key);
//Rekursif ke child kiri
printAllPrefix(root->left);
//Rekursif ke child kanan
printAllPrefix(root->right);
}

//Print BST secara Postfix
void printAllPostfix(struct node *root){
//Kalau ketemu rootnya NULL, maka balik
if(root == NULL) return;
//Rekursif ke child kiri
printAllPostfix(root->left);
//Rekursif ke child kanan
printAllPostfix(root->right);
//Print value
printf(" %d ", root->key);
}

//Hapus tree
struct node *freeAll(struct node *root){
if(root == NULL) return NULL;
root->left = freeAll(root->left);
root->right = freeAll(root->right);
free(root);
return NULL;
}

//Metode deletion dena=gan menggunakan value terbesar di subtree kiri
struct node *predecessor(struct node *root){
//Turun ke cabang kiri
struct node *curr = root->left;
//Selama belum turunannya belum paling kanan (paling besar di cabang kirinya root), turun lagi
while(curr->right != NULL){
curr = curr->right;
}
//Jika sudah paling kanan di cabang kirinya root, maka return nilainya
return curr;
}

struct node *deleteValue(struct node *root, int x){
//Jika data tidak ada di dalam tree
if(root == NULL) return NULL;
else if(x < root->key) root->left = deleteValue(root->left, x);
else if(x > root->key) root->right = deleteValue(root->right, x);
//Jika data ditemukan
else{
//Jika node tidak memiliki child, atau memiliki 1 child
if(root->left == NULL || root->right == NULL){
struct node *temp = NULL;

if(root->left != NULL) temp = root->left;
else temp = root->right;

//Jika tidak memiliki child
if(temp == NULL){
temp = root;
root = NULL;
}
//Jika memiliki 1 child
else{
*root = *temp;
}

free(temp);
}
//Node punya 2 child
else{
//Menggunakan predecessor: Menggunakan value node paling besar di
//cabang tree kiri untuk dijadikan parent
struct node *temp = predecessor(root);
root->key = temp->key;

//Delete
root->left = deleteValue(root->left, temp->key);
}
}

return root;

}

TUGAS CODE REVIEW UTS

Pada tugas ini, saya menambahkan validasi nama dan qty, lalu nama yang baru di-add tidak boleh sama dengan data yang sudah ada. Jika sudah ada maka langsung ke function edit. Lalu ada fitu viewProductList() untuk melihat daftar belanjaan sementara di keranjang. Lalu, ada fitur checkout dimana akan diprint bill hasil pembelian dan program akan exit.

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

char name[51];

int qty;

long long int price;

struct product{

char name[51];

int qty;

long long int price;

struct product *prev;

struct product *next;

} *head = NULL, *tail = NULL, *current;

void printMenu(){

printf("===== WELCOME TO ANGELIA'S DREAMMERS MARKET =====\n");

printf("1. Add New Product\n");

printf("2. Edit Product's Quantity\n");

printf("3. Delete Product\n");

printf("4. View Product List\n");

printf("5. Checkout\n");

printf(">> Choose: ");

}

void inputName(){

do{

printf("Insert Product's Name [1-50]\t: ");

scanf("%[^\n]", name);

getchar();

}

while(strlen(name) < 1 || strlen(name) > 50);

}

void inputQty(){

do{

printf("Insert Product's Qty [1..100]\t: ");

scanf("%d", &qty);

getchar();

}

while(qty < 1 || qty>100);

}

long long int randomPrice(){

long lower  = 100;

long upper = 999000;

return (rand() % (upper-lower+1) + lower);

}

//Sorted push secara ascending bdk nama produk

void push(char name[51], int qty, double price){

//Pesan memori dan Set data

current = (struct product*) malloc(sizeof(struct product));

strcpy(current->name, name);

current->qty = qty;

current->price = price;

current->prev = NULL;

current->next = NULL;

//Kalau data pertama

if(head == NULL){

head = tail = current;

}

//Kalau data abjad paling depan, push depan

else if(strcmp(current->name, head->name) < 0){

head->prev = current;

current->next = head;

head = current;

}

//Kalau data abjad paling belakang, push belakang

else if(strcmp(current->name, tail->name) > 0){

tail->next = current;

current->prev = tail;

tail = current;

}

//Jika posisi di antara, push mid

else{

struct product *temp = head;

while(strcmp(current->name, temp->next->name) > 0){

temp = temp->next;

}

current->next = temp->next;

temp->next = current;

current->prev = temp;

temp->next->prev = current;

}

}

void pop(char name[51]){

//Jika hanya 1 data

if(strcmp(name, head->name) == 0 && head == tail){

printf("\nProduct %s deleted successfully!\n", current->name);

free(head);

head = tail = NULL;

}

//Data ditemukan di awal

else if(strcmp(name, head->name) == 0){

current = head;

head = head->next;

printf("\nProduct %s deleted successfully!\n", current->name);

free(current);

head->prev = NULL;

}

//Data ditemukan di akhir

else if(strcmp(name, tail->name) == 0){

current = tail;

tail = tail->prev;

printf("\nProduct %s deleted successfully!\n", current->name);

free(current);

tail->next = NULL;

}

//Data ditemukan di tengah

else{

current = head;

while(current != NULL){

if(strcmp(name, current->name) == 0) break;

current = current->next;

}

//Data tidak ada

if(current == NULL) printf("Product name is not found!\n");

//Data ada

else{

current->next->prev = current->prev;

current->prev->next = current->next;

printf("\nProduct %s deleted successfully!\n", current->name);

free(current);

}

}

}

void editProduct(char name[51]){

//Cek ada nama produk yang sama, jika ada maka pindah ke bagian edit qty langsung

current = head;

while(current != NULL){

if(strcmp(name, current->name) == 0) break;

current = current->next;

}

//Jika nama product belum ada

if (current == NULL) printf("Product name is not found!\n");

else{

printf("===== EDIT QTY PRODUCT =====\n");

inputQty();

current->qty = qty;

printf("\nPRODUCT %s QTY HAS BEEN CHANGED SUCCESSFULLY!\n", current->name);

}

}

void addProduct(){

printf("===== ADD NEW PRODUCT =====\n");

inputName();

//Cek ada nama produk yang sama, jika ada maka pindah ke bagian edit qty langsung

current = head;

while(current != NULL){

if(strcmp(name, current->name) == 0) break;

current = current->next;

}

//Jika nama product belum ada

if(current == NULL){

inputQty();

//Set random price (per item), untuk total price akan dihitung saat checkout

price = randomPrice();

push(name, qty, price);

printf("\nINSERT NEW PRODUCT SUCCESS!\n");

}

//Jika nama product sudah ada, langsung edit

else{

printf("\nProduct's name is already exist!\n");

editProduct(name);

}

}

void deleteProduct(){

printf("===== DELETE PRODUCT =====\n");

inputName();

pop(name);

}

void viewProductList(int choose){

long long int total = 0;

int index = 0;

if(choose == 4) printf("============================== CURRENT TROLLEY LIST ==============================\n");

else if(choose == 5) printf("============================ DREAMMERS MARKET RECEIPT ============================\n");

printf("|| %3s. || %-20s || %3s || %18s || %15s ||\n", "No", "Product Name", "Qty", "Price (per item)", "Total Price");

current = head;

while(current != NULL){

printf("|| %3d. || %-20s || %3d || %-8s %9ld || %-5s %9ld ||\n", index+1, current->name, current->qty, "Rp.", current->price, "Rp.", current->qty * current->price);

total += current->qty * current->price;

current = current->next;

index++;

}

if(choose == 4){

printf("==================================================================================\n");

puts("");

printf("GRAND TOTAL\t: Rp. %ld\n", total);

}

else if(choose == 5){

printf("==================================================================================\n");

puts("");

printf("TOTAL PAYMENT : Rp. %ld\n", total);

printf("Kindness is free\n\n");

}

}

void byeGreeting(){

printf("Thank you for coming to Angelia's Dreammers Market\n");

printf("Created By: Angelia \(2301854492\)");

}

int main(){

int choose = -1;

do{

system("cls");

printMenu();

scanf("%d", &choose);

getchar();

switch(choose){

case 1:

addProduct();

break;

case 2:

if(head == NULL) printf("No Data!\n");

else{

inputName();

editProduct(name);

}

break;

case 3:

if(head == NULL) printf("No Data!\n");

else deleteProduct();

break;

case 4:

//View Temporary Trolley List

if(head == NULL) printf("No Data!\n");

else viewProductList(choose);

break;

case 5:

//Checkout

if(head == NULL) printf("You have bought nothing!\n");

else viewProductList(choose);

byeGreeting();

break;

}

if(choose<5 && choose>0){

printf("\nPress any key to continue...");

getchar();

}

}

while(choose != 5);

return 0;

}

Berikut ini link google drive untuk file .cpp dan .exe dan summary dari tugas ini:

https://drive.google.com/open?id=1SmpA-EPVZPtcDEpRfKZ8wyWlqMWBRe4H

Demikian review materi pembelajaran Data Structures hingga UTS. Mohon maaf jika ada kekurangan maupun kesalahan. Terima kasih.

Angelia

2301854492

COMP6048 - CB01