Skip to main content

Final-Rangkuman

Nama : Clarissa Chuardi
NIM : 2301941366
Kelas : CB01-CL
Lecturer : Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460)
  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
    3.           - 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;
}

AVL Tree

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree digunakan untuk melakukan searching yang lebih singkat dan sederhana.

Ada 4 case dalam melakukan operasi insert :

  • Single Rotation
    Ada 2 case yang dapat diselesaikan dengan single rotation, yaitu ketika node terdalam terletak pada subtree kiri dan anak kiri T, (left rotation) dan ketika node terdalam terletak pada subtree kanan dan anak kanan T (right rotation).




  • Double RotationDi double rotation juga terdapat 2 case yang dapat terselesaikan dengan double rotation, yaitu jika node terdalam terletak pada subtree kanan dan anak kiri T (right-left), dan node terdalam terletak pada subtree kiri dan anak kanan T (left-right).


Ada 2 case yang terjadi saat operasi delete :

  1. Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
  2. Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.Anggap T adalah node yang harus diseimbangkan kembali
    – Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
    – Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
    – Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
    – Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

              Jika kita ingin menghapus node 60


    Terdapat node yang tidak seimbang yaitu node 55, maka kita dapat seimbangkan dengan single rotation (left rotation), tetapi node 50 menjadi tidak seimbang.
     
    Lalu diseimbangkan dengan double rotation (left-right) karena dari 50 ke 25 kiri dan 25 ke 40 kanan.

     



Heap 
Heap adalah suatu tree yang terdiri dari 3, yaitu Min Heap, Max Heap, dan Min-Max Heap. Heap juga berguna untuk membuat Priority Queue.

Ciri - ciri dari heap adalah :
- Setiap parent mempunyai maksimal 2 child
- Root dari heap berupa angka maksimal / minimal dari tree tersebut
- Berbeda dengan tree lain, heap menyimpan data-datanya di dalam array
- Index array di heap dimulai dari 1 untuk memudahkan ketika mencari parent dari child
- Setiap angka baru yang dimasukkan akan berada pada index terakhir yang akan dibandingkan dengan parentnya

Rumus untuk mencari parent di heap adalah :
Parent_index = index/2
Leftchild_index = index * 2
Rightchild_index = index*2+1

1. Min Heap
Min Heap adalah heap yang dimana rootnya adalah angka minimum dari heap itu sendiri.
Contoh Insertion :

Contoh Deletion :


2. Max Heap
Max Heap adalah kebalikan dari min heap. Max heap adalah sebuah heap yang dimana rootnya adalah angka maksimum dari heap itu sendiri.
Contoh Insertion :
Contoh Deletion :



3. Min-Max Heap
Min-Max Heap adalah sebuah heap yang terdiri dari level-level yang setiap levelnya itu berbeda.
Level genap di heap ini adalah berupa angka min dan level ganjil terdapat angka max.
Angka terkecil dari heap berada di array pertama,
Angka terbesar dari heap berada di array kedua atau ketiga.


Tries
Biasanya di tree pada umumnya, tries menyimpan dalam bentuk karakter. Tries bisa mempunyai anak lebih dari 2. Biasa digunakan untuk auto-complete / searching, bubble words, list/set/collection
misalnya space,spaces,spade,speak,speaker,speakers, dll
Maka kita gak perlu simpan per katanya, melainkan per karakter.








Comments

Post a Comment

Popular posts from this blog

Binary Search Tree

Binary Search Tree        -         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, be...
Post a Comment
Read more

AVL Tree (Insertion and Deletion)

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree digunakan untuk melakukan searching yang lebih singkat dan sederhana. Ada 4 case dalam melakukan operasi insert : Single Rotation Ada 2 case yang dapat diselesaikan dengan single rotation, yaitu ketika node terdalam terletak pada subtree kiri dan anak kiri T, (left rotation) dan ketika node terdalam terletak pada subtree kanan dan anak kanan T (right rotation). Double Rotation Di double rotation juga terdapat 2 case yang dapat terselesaikan dengan double rotation, yaitu jika node terdalam terletak pada subtree kanan dan anak kiri T (right-left), dan node terdalam terletak pada subtree kiri dan anak kanan T (left-right). Ada 2 case yang terjadi saat operasi delete : Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus. Jika node yang akan dihapus memiliki anak, maka pros...
Post a Comment
Read more