1 Semester Summary

Di semester ini, saya telah belajar tentang Data Structure dan berikut adalah ringkasannya .

1. Linked List
   Linked List adalah koleksi data item tersusun dalam sebuah barisan  secara linear, di dalam tempat yang disebut dengan node . Sedangkan Array adalah koleksi dari object yang mempunyai tipe identik / sama, array dapat disebut juga koleksi data dengan setiap elemen data menggunakan nama yang sama dan masing-masing elemen mempunyai tipe data sama. Array dapat diloop dengan memberi indeks setiap item di dalamnya, dan setiap komponen / item array dapat diakses dan dibedakan melalui indeks array.
   Perbedaan linked list dan array :
   - Linked List :
      -> Setiap elemen linked list terdiri dari 2 bagian, data dan pointer address.
      ->  Pengalokasian ruang memori dilakukan tanpa pendeklarasisan sebelumnya dan bersifat dinamis.
   - Array :
      -> Setiap elemen array hanya berisi data saja.
      -> Pengalokasian ruang memori terbatas pada jumlah ruang yang dideklarasikan sebelumnya dan bersifat statis.
   
   Di Linked List terdapat beberapa operasi, yaitu :
   - Push 
   Push adalah operasi untuk insert sebuah data ke dalam linked list. Ada terdiri dari 3 macam push. yaitu Push Head, Push Tail , dan Push Mid.
   Push Head adalah cara menginsert ke depan, jadi data yang di Push Head akan selalu berada di paling kiri/ depan sebuah linked list.
   Contohnya :
   4-5-7-1-8 (Push Head 9)
   Menjadi 9-4-5-7-1-8
   Sedangkan Push Tail adalah kebalikan dari Push Head yaitu menginsert sebuah data di belakang linked list. Jadi data yang di Push Tail akan selalu di paling kanan/ belakang linked list tersebut. Contoh :
   4-5-7-1-8 (Push Tail 9)
   Menjadi 4-5-7-1-8-9
   
   Push Mid adalah cara untuk insert data di tengah-tengah linked list atau bisa disebut jg sorting.
   Jadi Push Mid membandingkan data di nodenya dengan data yang terdiri dalam linked list. Contoh :
   4-5-7-1-8 (Push Mid 6)
   Menjadi 4-5-6-7-1-8 
   
   - Pop
   Pop adalah sebuah fungsi untuk mendelete atau menghapus sebuah node di dalam sebuah linked list. Pop juga terbagi menjadi 3 yaitu, Pop Head (untuk menghapus data yang berada di paling depan), Pop Tail (untuk menghapus data yang berada di paling kiri) , dan Pop Mid
    (untuk menghapus sebuah data spesifik). Contoh :
   - 4-5-7-1-8 (Pop Head) = 5-7-1-8
   - 4-5-7-1-8 (Pop Tail) = 4-5-7-1
   - 4-5-7-1-8 (Pop Mid(7)) = 4-5-1-8 
   
   Ada beberapa macam linked list, saya akan membahas yang single dan double linked list :
   
   Single Linked List
   Single linked list adalah sebuah linked list yang menggunakan satu pointer saja untuk menyimpan banyak data di linked list. Di single linked list pointer hanya dapat bergerak ke satu arah saja yaitu maju dengan menggunakan pointer next, sehingga pencarian data dilakukan satu arah juga. Berikut adalah source code untuk beberapa operasi single linked list .
   

   Push Head

   void pushHead(int angka){
    node = (Data*)malloc(sizeof(struct Data));
    node->angka = angka;
           node->next = NULL;
   
    if(head == NULL){    //jika linked list kosong
     head = tail = node;
    }
    
    else{                //jika linked list tidak kosong             
     node->next = head;
     head = node;
    } 
   }

   
   

   Push Tail

   void pushTail(int angka){
    node = (Data*)malloc(sizeof(struct Data));
    node->angka = angka;
           node->next = NULL;
           
    if(head == NULL){            //jika linked list kosong
     head = tail = current;
    }
    
    else{                        //jika linked list tidak kosong
     tail->next = node;
     tail = node;
    }
    tail->next = NULL;
   }

   Push Mid

   void pushMid(int angka){
    node = (Data*)malloc(sizeof(struct Data));
    node->angka = angka;
   
    
    if(head == NULL){                  //jika linked list kosong
     head = tail = node;
    }
    else if(node->angka < head->angka){//jika angka node lebih kecil dari angka di head
     pushHead(angka);
    }
    else if(node->angka > tail->angka){//jika angka node lebih besar dari angka di tail
     pushTail(angka);
    }
    else{
         while(temp->next->angka < node->angka){ //akan looping hingga temp ke next lebih besar dari node
         temp = temp->next;
     }
     node->next = temp->next;   //node ke next akan disambungkan ke temp ke next
     temp->next = node;         //temp ke next akan disambungkan ke node
    }
   }

   Pop Head

   void popHead(){
    Data *curr = head;
    if(head==NULL){          //jika tidak ada data
     return;
    }else if(head==tail){    //jika hanya terdapat 1 data
     head=tail=NULL;
     free(curr);
    }else{                   //jika terdapat banyak data
     head=head->next;
     free(curr);
    }
   }

   Pop Tail

   void popTail(){
    if(head==NULL){                               //jika tidak ada data
                   return;  
    }else if(head==tail){                         //jika hanya ada 1 data
     Data *curr = head;
     head=tail=NULL;
     free(curr);
    }else{
     Data *temp=head;
     while(temp->next!=tail){          //looping mencari posisi 1 data sebelum tail
      temp=temp->next;
     }
     curr=tail;
     tail=temp;
     free(curr);
     tail->next=NULL;
    }
   }

   Pop Mid

   void popMid(int angka){
    if(head==NULL){                       //jika tidak ada data
     return;
    }else if(head->angka==angka){         //jika angka berada di head
     popHead();
    }else if(tail->angka==angka){         //jika angka berada di tail
     popTail();
    }else{                                //jika angka berada di tengah-tengah
     Data *temp=head;
     while(temp->next->angka!=angka && temp!=tail){
      temp=temp->next;
     }
     curr=temp->next;
     temp->next=temp->next->next;
     free(curr);
    }
   }

2. Stack & Queue
          - Konsep Stack
                 Stack menggunakan konsep LIFO(Last In First Out). Analoginya adalah sama seperti kita  menyusun piring setelah dicuci, kita menyusun dari bawah/belakang ke atas/depan sampai penuh, tetapi ketika kita ingin menggunakan piring tersebut, kita mengambil yang paling atas/depan. 
       
          - Konsep Queue
                 Queue menggunakan konsep FIFO(First In First Out) /  sesuai urutan. Contohnya : Antri menggunakan toilet, orang yang duluan antri adalah yang dapat masuk dulu.
3. Hash Table
   ·        Hashing
   Hashing adalah sebuah teknik untuk menyimpan data  dengan menggunakan index (key) dari string tersebut.
   Fungsi hashing adalah untuk mendapat index (key) untuk menentukan lokasi data.
   Contoh Hashing :
   Misalkan kita ingin menyimpan 5 data string : “define”,”float”,”exp”,”char”,”atan” ke dalam hash table dengan size 26. Hash function yang kita gunakan adalah mengubah karakter pertama dalam string tersebut menjadi angka antara 0 sampai 25.
   Hasilnya :
   - define “d” = 3
   - float “f” =  5
   - exp “e” = 4
   - char “c” = 2
   - atan “a” = 0
                 
   ·        Hash Table
   Hash table adalah sebuah tabel / array dimana kita menyimpan string / data kita.
   Index dari tabel adalah hashed key, sedangkan value (isi) di dalamnya adalah value dari data kita.
   Contoh Hash Table :
   5 string yang sudah dihashing akan disimpan sesuai nilai key yang didapatkan. Kita cuma memakai karakter pertama dari string.
   
   
   -        atan disimpan di h[0] karna a = 0  
   -        char disimpan di h[2] karna c = 2  
   -        define disimpan di h[3] karna d = 3  
   -        exp disimpan di h[4] karna e = 4  
   -        float disimpan di h[5] karna f = 5  
   
   
   
   
   ·        Collision
   Apa yang akan terjadi apabila kita ingin menyimpan string kita dengan metode hashing dengan menggunakan karakter pertama dari string :
   “define”,”float”,”exp”,”char”,”atan”,”ceil”,”acos”,”floor”
   Ada 3 pasang string yang mempunyai hash key yang sama, yaitu : “float” dan “floor, “char” dan “ceil”, “atan” dan “acos”.
   Karena ada string yang mempunyai hash key yang sama, maka dapat terjadi collision.
   Ada 2 cara untuk collision :
   -        Linear Probling
   Metode yang akan dilakukan adalah cari tempat yang kosong da nisi string tersebut di tempat kosong tersebut.
   -        Chaining
   Metode chaining adalah dengan menjadikan string tersebut ke dalam linked list.
   
   
   ·        Linear Probling
   Contoh :
   
   String : “define”,”float”,”exp”,”char”,”atan”,”ceil”,”acos”,”floor”
   
   - “acos” berada di h[1]
   - “ceil” berada di h[6]
   - “floor” berada di h[7]
   
   Ketika kita ingin menyimpan “ceil”, di h[2] sudah terpakai, jadi
   kita menempatkannya di tempat kosong selanjutnya yaitu h[6].
   
   Kekurangannya adalah kompleksitas searching jika terjadi banyak collision.
   Ketika kita ingin mencari “ceil”, hash key dari “ceil” menunjukkan 2. Tetapi ceil tidak ada disana, jadi terus dilakukan looping sampai “ceil” ditemukan.
   
   
   ·        Chaining
   
   
   Di dalam chaining, kita menyimpan setiap setiap ke dalam linked list.
   Jadi, ketika terjadi collision, kita cuma perlu melakukan pengulangan di
   linked listnya.  
4. BST
   
   
         -        Pengertian
         Binary search tree (BST) adalah sebuah data struktur yang digunakan untuk mempercepat        searching, sorting, insertion dan deletion.
         BST juga dikenal sebagai binary tree yang sudah disortir
         Untuk sebuah node x dari BST :
   è Value di subtree kiri lebih kecil dari value dalam x
   è Value di subtree kanan lebih besar dari value dalam x
         -        Binary search tree operations
         BST mempunyai beberapa operasi :
   è Search(x) : untuk mencari key x di dalam BST
   Misalnya kita ingin mencari key x :
   o   Pertama kita mulai dari root
   o   Jika root adalah x maka proses selesai
   o   Jika x lebih kecil dari key root maka dilakukan searching secara rekursif di subtree sebelah kiri, begitu pula sebaliknya
   è Insert(x) : untuk memasukkan key baru x ke ke dalam BST
   Operasi di BST dilakukan secara rekursif
   Jika kita ingin memasukkan node baru yang valuenya x :
   o   Pertama mulai dari root
   o   Jika x kurang dari value node maka insert x di sub tree kiri, sebaliknya insert x di sub tree sebelah kanan
   o   Ulangi sampai kita menemukan node yang kosong untuk x ( x selalu menjadi leaf baru).
   
   
   è Remove(x) : untuk menghapus key x dari BST
   Dalam operasi ini ada 3 macam kasus yang kita perlu perhatikan :
   o   Jika key di dalam leaf, maka langsung hapus node tersebut
   o   Jika key di dalam node yang mempunyai sebuah child, maka delete node tersebut dan connect child tersebut dengan parentnya
   o   Jika key di dalam node yang mempunyai 2 children, cari child yang paling kiri, dan bandingkan dengan yang kanan
   
   
   Demikian penulisan saya tentang binary search tree, anda dapat mencoba langsung visualisasi dengan membuka link dibawah ini.
   https://www.cs.usfca.edu/~galles/visualization/BST.html

Berikut saya lampirkan source code tugas kodingan saya :

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

int count=0;
int total=0;

struct Cart{
char name[100];
int qty;
int price;
Cart *next,*prev;
}*head=NULL,*tail=NULL;

Cart *newNode(char name[100],int qty,int price){
Cart *node=(struct Cart*)malloc(sizeof(Cart));
strcpy(node->name,name);
node->price=price;
node->qty=qty;
node->next=node->prev=NULL;

return node;
}

void pushhead(Cart *node){
if(!head){
head=tail=node;
}
else{
head->prev=node;
node->next=head;
head=node;
}
}

void pushtail(Cart *node){
if(!head){
head=tail=node;
}
else{
tail->next=node;
node->prev=tail;
tail=node;
}
}

void pushmid(Cart *node){
if(!head){
head=tail=node;
}
else{
if(node->qty<=head->qty){
pushhead(node);
}
else if(node->qty>=tail->qty){
pushtail(node);
}
else {
Cart *temp=head;
while(temp->next!=NULL&&node->qty>=temp->next->qty){
temp=temp->next;
}
node->next=temp->next;
node->prev=temp;
temp->next->prev=node;
temp->next=node;
}
}
}

void pophead(){
if(!head){
printf("There is no item in your cart\n");
return;
}
else if(head==tail){
free(head);
head=tail=NULL;
}
else{
Cart *curr=head;
head=head->next;
curr->next=NULL;
head->prev=NULL;
free(curr);
}
}

void poptail(){
if(!head){
printf("There is no item in your cart\n");
return ;
}
else if(head==tail){
free(head);
head=tail=NULL;
}
else{
Cart *curr=tail;
tail=tail->prev;
tail->next=NULL;
curr->prev=NULL;
free(curr);
}
}

void popmid(int qty){
if(!head){
return;
}
else if(head->qty==qty){
pophead();
}
else if(tail->qty==qty){
poptail();
}
else{
Cart *curr=head->next;
while(curr!=tail&&curr->qty!=qty){
curr=curr->next;
}
curr->next->prev=curr->prev;
curr->prev->next=curr->next;
curr->next=NULL;
curr->prev=NULL;
}
}

void printall(){
Cart *curr=head;
count=1;
total=0;
while(curr){
if(count>9){
printf("| %d| %-5s              | Rp.%10d   | %d  |\n",count,curr->name,curr->price,curr->qty);
}
else{
printf("| %d | %-5s              | Rp.%10d   | %d  |\n",count,curr->name,curr->price,curr->qty);
}
total+=(curr->price*curr->qty);
curr=curr->next;
count++;
}
count--;
}

void checkout(){
system("cls");
char choice;
if(count!=0){
printf("-----------------------------------------------------\n");
printf("======================RoYi-Mart======================\n");
printf("-----------------------------------------------------\n");
printf("======================Your Cart======================\n");
printf("-----------------------------------------------------\n");
printf("| No| Product Name          |  Price          | Qty |\n");
printall();
printf("------------------------------------------------------\n");
do{
printf("Do you want to checkout? [Y/N](Case Sensitive) : ");
scanf("%c",&choice);getchar();
}while(choice!='Y'&&choice!='N');
if(choice=='Y'){
printf("Total : Rp.%d\n",total);
printf("------------------------------------------------------\n");
printf("Discount 100%% = Rp.%d\n",total);
printf("------------------------------------------------------\n");
printf("Total You Need To Pay : 0\n");
printf("------------------------------------------------------\n");
printf("~Because Kindness is free~\n");
printf("------------------------------------------------------\n");
printf("Thank you for buying our products\n");
printf("------------------------------------------------------\n");
printf("See you next time!");
exit(0);
}
}
else{
printf("There is no item in your cart\n");
}
printf("Press Enter To Continue . . . ");getchar();
}

void deletion(){
system("cls");
int cut,qty;
if(count!=0){
printf("-----------------------------------------------------\n");
printf("======================RoYi-Mart======================\n");
printf("-----------------------------------------------------\n");
printf("======================Your Cart======================\n");
printf("-----------------------------------------------------\n");
printf("| No| Product Name          |  Price          | Qty |\n");
printf("------------------------------------------------------\n");
printall();
printf("------------------------------------------------------\n");
do{
printf("Select item that you want to delete [1-%d] : ",count);
scanf("%d",&cut);getchar();
}while(cut>count||cut<=0);
int counter=1;
Cart *curr=head;
if(counter==cut){
pophead();
}
else{
while(counter!=cut){
counter++;
curr=curr->next;
}
qty=curr->qty;
popmid(qty);
}
printf("Success delete the product.\n");
}
else{
printf("There is no item in your cart\n");
}
printf("Press Enter To Continue . . . ");getchar();
}

void update(){
system("cls");
int update,price,qty;
char name[100];
if(count!=0){
printf("-----------------------------------------------------\n");
printf("======================RoYi-Mart======================\n");
printf("-----------------------------------------------------\n");
printf("======================Your Cart======================\n");
printf("-----------------------------------------------------\n");
printf("| No| Product Name          |  Price          | Qty |\n");
printall();
printf("------------------------------------------------------\n");
do{
printf("Select item that you want to update [1-%d] : ",count);
scanf("%d",&update);getchar();
}while(update>count||update<=0);
do{
printf("Insert product name [5-20] : ");
scanf("%[^\n]",name);getchar();
}while(strlen(name)>20||strlen(name)<5);
do{
printf("Insert product qty [>10] : ");
scanf("%d",&qty);getchar();
}while(qty<=10);
int counter=1;
Cart *curr=head;
while(counter!=update){
counter++;
curr=curr->next;
}
strcpy(curr->name,name);
curr->qty=qty;
printf("Success update the product.\n");
}
else{
printf("There is no item in your cart\n");
}
printf("Press Enter To Continue . . . ");getchar();
}

void view(){
system("cls");
if(count!=0){
printf("-----------------------------------------------------\n");
printf("======================RoYi-Mart======================\n");
printf("-----------------------------------------------------\n");
printf("======================Your Cart======================\n");
printf("-----------------------------------------------------\n");
printf("| No| Product Name          |  Price          | Qty |\n");
printall();
printf("------------------------------------------------------\n");
}
else{
printf("There is no item your cart\n");
}
printf("Press Enter to Continue...");getchar();


}

void add(){
int len,price,qty;
char name[100];
system("cls");
printf("=========================\n");
printf("-------Add Product-------\n");
printf("=========================\n");
do{
printf("Input product name [5-20 characters] : ");
scanf("%[^\n]",name);getchar();
len=strlen(name);
}while(len<5||len>20);
do{
printf("Input product qty [>10] : ");
scanf("%d",&qty);getchar();
}while(qty<=10);
count++;
price=rand()%100000+1001;
pushmid(newNode(name,qty,price));
printf("Success added the product!\n");
printf("==========================\n");getchar();
}

void menu(){
int choose;
system("cls");
printf("====================\n");
printf("      RoYi-Mart     \n");
printf("====================\n");
printf("1. Add Product\n");
printf("2. View Products\n");
printf("3. Update Product\n");
printf("4. Delete Product\n");
printf("5. Checkout\n");
printf("6. Exit\n");
do{
printf(">> ");
scanf("%d",&choose);getchar();
}while(choose>6||choose<=0);
printall();
switch(choose){
case 1:
add();
menu();
break;
case 2:
view();
menu();
break;
case 3:
update();
menu();
break;
case 4:
deletion();
menu();
break;
case 6:
printf("===============\n");
printf("---Thank you---\n");
printf("===============\n");
exit(0);
break;
case 5:
checkout();
menu();
break;


}
}

int main(){
srand(time(0));
menu();

return 0;
}