Rangkuman Data Structure Tengah Semester

Rangkuman Data Structure, Tengah Semester

Nama : Julian Andhika Diputra

NIM : 2301858023

Data Structure adalah salah satu cara untuk mengorganisir data di sebuah computer sehingga bisa digunakan secara efektif. Salah satu yang contoh Data Structure yang kita dapatkan adalah, Linked List. 

Linked List

Linked List adalah data structure linear (Array) yang berisi data – data record yang berkoneksi dengan record di sequence selanjutnya. Linked list sendiri memiliki beberapa keuntungan dan kekurangan. 

Keuntungan linked list adalah data struktur yang dinamik, pemasukan dan penghapusan node yang lebih mudah, dan juga data struktur lebih mudah diemplementasi menggunakan linked list. Kekurangannya adalah pengunaan memori lebih banyak, transferal antara node lebih susah, dan juga pengaksesan node harus dimulai dari node pertama, tidak boleh random.

Linked list dibagi menjadi 3, yaitu Circular single linked list, Doubly Linked List, dan Circular Doubly Linked List.

1. Circular Single Linked List, adalah linked list yang paling umum, dimana node terakhir linked list ini memiliki pointer yang mempoint ke node pertama.
   
2. Doubly Linked List, disebut juga sebagai two-way linked list adalah linked list dimana data structurenya memiliki dua link, satu yang memiliki referensi ke data selanjutnya dan satu lagi yang memiliki referensi ke data sebelumnya.
   
3. Circular Doubly Linked List, mirip dengan Circular single linked list tetapi pointernya ada dua.

Dalam pembuatan Linked List sendiri, dapat digunakan beberapa contoh fungsi - fungsi yang dapat membantu dalam pembuatan Linked List, contohnya adalah Push and Pop. Sebelum membuat coding Linked List, jangan lupa untuk membuat struct.

Push 

Push adalah  aksi/fungsi menambahkan sebuah node baru. Bisa dilakukan push kedepan node ataupun kebelakang node. Dalam Double Linked List, Push dapat dilakukan ketengah node.

Pop

Pop yaitu aksi/fungsi menghilangkan sebuah node. Bisa dilakukan pop node didepan dan juga dalam Double Linked List dapat dilakukan pop node kebelakang ataupun node manapun yang diinginkan. Ada juga fungsi pop all yaitu, adalah fungsi dimana kita menghapus semua node yang ada. 

Selain Linked List, juga ada Hashing dan Binary Tree 

Hashing

Hashing adalah sebuah fungsi yang bisa digunakan dalam Data 

Structure, yang dapat digunakan untuk menggunakan sebuah fungsi khusus yaitu Hash Function. Hash function sendiri digunakan untuk memetakan sebuah nilai dengan key tertentu agar lebih mudah untuk diakses.

Ada beberapa cara untuk meng-hash sebuah string menjadi key;

1. Mid-Square
2. Division
3. Folding
4. Digit Extraction
5. Rotating Hash 

Mid-Square

Mid-Square adalah Teknik hashing dimana key hashing di-generate secara unik. Dalam Teknik ini, sebuah string diambil dan dikuadratkan. Lalu beberapa digit dari tengah diambil, yang nanti akan menjadi sebuah key baru. Teknik ini dapat membuat key dengan keacakan yang tinggi, jika digitnya besar. Jika key itu adalah sebuah string, akan diubah menjadi sebuah nomor.

Division

Division adalah Teknik hashing dimana sebuah string/identifier dibagi menggunakan operator modulus. Teknik ini merupakan Teknik hashing yang paling mudah. 

Folding

Folding adalah Teknik hashing dimana sebuah string/identifier dipartisikan menjadi berbagai bagian, lalu kita menambahkan semua part tersebut untuk mendapatkan sebuah hash key. 

Digit Extraction

Digit Extraction adalah Teknik hashing dimana sebuah digit yang ditentukan dari nomor yang diberikan akan dijadikan sebagai alamat hash 

Rotating Hash

Rotating Hash adalah salah satu Teknik hashing. Sebelum menggunakan Rotating Hash, kita harus menggunakan hash method yang lain. Setelah mendapatkan Hash code dari hash method yang lain, lakukanlah rotation. Rotation dilakukan dengan mengubah posisi digit untuk mendapatkan hash code/address baru.

Collision

Apakah yang terjadi jika terjadi tabrakan antara hash-key yang satu dengan hash-key yang lain. Hal ini disebut sebagai Collision. Ada dua cara untuk menangani Collision.

1. Linear Probing :Mencari slot kosong selanjutnya dan menaruh string disana. Linear probing akan mengalami beberapa masalah jika terjadi banyak Collision.    
2. Chaining: Masukkan string di slot sebagai chained list (linked list). Dalam chaining ini, kita menyimpan setiap string dalam sebuah chain. Jika terjadi Collision, kita tingal mengubah chain/linked list tersebut.

Binary Tree 

Binary tree adalah sebuah data structure yang non linear yang merepresentasikan hubungan hirearki antara objek.

• Node dipaling atas disebut root 
• Garis yang menghubungkan sebuah parent dengan child disebut edge
• Node yang tidak memiliki children disebut leaf 
• Node yang memiliki parent yang sama disebut sibling 
• Degree dari sebuah node adalah total sub tree dari node tersebut 
• Height/Depth adalah maximum degree dari sebuah node dalam tree 
• Jika ada sebuah garis yang menghubungi p ke q, maka p disebut sebagai ancestor dari q, dan q adalah descendant dari p.

Konsep Binary Tree ada beberapa yaitu; Perfect Binary Tree, Complete Binary Tree, Skewed Binary Tree, dan Balanced Binary Tree.  Salah satu contoh Binary Tree adalah Binary Search Tree.

Binary Search Tree

Binary Search Tree adalah salah satu data structure yang mensupport searching lebih cepat, sorting yang lebih baik, dan insertion dan deletion yang mudah. Dalam Binary Search Tree, setiap node disorting. Untuk Node X, elemen yang dikiri tree, adalah element yang lebih kecil dari yang Node X. Sedangkan elemen yang diakanan tree, adalah element yang lebih besar dari Node X.

Dalam Binary Search Tree ada beberapa operasi basic;

1. Find adalah operasi untuk mencari sebuah element dalam tree. Untuk mencari element, dimulai dari root sebuah tree. Jika yang dicari lebih kecil daripada root, maka dia mencari di bagian kiri. Sedangkan, jika yang dicari lebih besar daripada root, maka dia mencari di bagian kanan. 
2. Insert adalah operasi untuk menambah sebuah element dalam tree. Untuk menambah element, dimulai dari root sebuah tree. Jika yang ingin ditambah lebih kecil dari key, maka akan ditambah di bagian kiri. Selain itu, akan ditambah di bagian kanan. Teruskan ini sampai kita mendapatkan node kosong untuk ditaruh.
3. Delete adalah operasi untuk mendelete sebuah element dalam tree. Untuk mendelete sebuah tree ada beberapa cara:

• Jika key itu leaf, bisa langsung di delete. 
• Jika key itu itu memiliki satu child, delete node tersebut, lalu connect parent node tersebut dengan child tersebut. 
• Jika key itu dalam sebuah node yang memiliki dua child, cari node terkanan dari bagian kiri, lalu ganti node tersebut dengan node yang didapatkan.

 

Berikut saya lampirkan coding Dreamers Market saya:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

struct dmarket{
    char name[1000];
    int quantity;
    long long int price;
    struct dmarket *next, *prev;
}*head,*tail,*current;


void pdepan(char productName[],int pquantity, long long int pprice){
    current=(struct dmarket*) malloc(sizeof(struct dmarket));
    strcpy(current->name,productName);
    current->quantity = pquantity;
    current->price = pprice;
   
    if(head==NULL){
        head=tail=current;
    }
    else{
        current->next=head;
        head->prev=current;
        head=current;
    }
    tail->next = head->prev = NULL;
}

void pbelakang(char productName[],int pquantity, long long int pprice){
    current=(struct dmarket*) malloc(sizeof(struct dmarket));
    strcpy(current->name,productName);
    current->quantity = pquantity;
    current->price = pprice;
   
    if(head==NULL){
        head=tail=current;
    }
    else{
        tail->next=current;
        current->prev=tail;
        tail=current;
    }
    tail->next = head->prev = NULL;
}

void push(char productName[], int pquantity, long long int pprice){
    current=(struct dmarket*) malloc(sizeof(struct dmarket));
    strcpy(current->name,productName);
    current->quantity = pquantity;
    current->price = pprice;
   
    if(head==NULL){
        head=tail=current;
    }
    else if(strcmp(current->name,head->name)<0){
        pdepan(productName,pquantity,pprice);
    }
    else if(strcmp(current->name,head->name)>0){
        pbelakang(productName,pquantity,pprice);
    }
    else{
        struct dmarket* temp;
        temp=head;
        while(strcmp(temp->next->name,current->name)<0){
            temp=temp->next;
        }
        current->next=temp->next;
        temp->next->prev=current;
        temp->next=current;
        current->prev=temp;
    }
}

void popdepan(){
    current=head;
    head=head->next;
    free(current);
    head->prev=NULL;
}

void popbelakang(){
    current=tail;
    tail=tail->prev;
    free(current);
    tail->next=NULL;
}

void pop(char productName[], int pquantity, long long int pprice){
    if(strcmp(head->name,productName)==0){
        popdepan();
    }
    else if(strcmp(tail->name,productName)==0){
        popbelakang();
    }
    else{
        struct dmarket* temp=head;
        while(strcmp(temp->next->name,productName)!=0){
            temp=temp->next;
        }
        current=temp->next;
        temp->next=current->next;
        current->next->prev=temp;
        free(current);
    }
}

void addProduct(){
    int flag=0;
    char productName[1000];
    int quantity;
    long long int price;
   
    flag=0;
    printf("Enter Product Name: ");
    scanf("%[^\n]",productName);
   
    current=head;
   
    while (current!=NULL){
        if(strcmp(current->name,productName)==0){
            flag=1;
            break;
        }
        current=current->next;
    }

    if(flag==0){
        printf("Enter Product Quantity: ");
        scanf("%d",&quantity);   
       
        price=(rand()%100)*1000;
        push(productName,quantity,price);
        printf("\n");
        printf("Item Added Successfully!\n");
        printf("Press Enter To Continue....\n");
        getchar();
        getchar();
        system("cls");
    }
    else if(flag==1){
        printf("This Product Already Existed!\n");
        printf("Press Enter To Continue....");
        getchar();
        getchar();
        system("cls");
    }
}

void editProduct(){
    int count=0;
    int amount=0;
    char productName[1000];
    int quantity;
   
    if(head==NULL){
        printf("No Item Has Been Added!\n");
        printf("Press Enter To Continue...\n");
        getchar();
        system("cls");
    }
    else{
        current=head;
        printf("==========================================\n");
        printf("| %28s         |\n","Dreamers Market List");
        printf("==========================================\n");
        printf("|%-3s|%-15s|%-8s|%-10s|\n","No","Product Name","Quantity","Price");
        printf("==========================================\n");
        while(current!=NULL){
            printf("|%-3d|%-15s|%-8d|%-7d RP|\n",amount+1,current->name,current->quantity,current->price);
            current=current->next;
            amount++;
        }
        printf("==========================================\n");
        printf("\n");
       
        count=0;
        printf("Enter Product Name To Edit: ");
        scanf("%[^\n]",productName); getchar();
           
        current=head;
        while(current!=NULL){
            if(strcmp(current->name,productName)==0){
                count=1;
                break;
            }   
            current=current->next;
        }
       
        if(count==0){
            printf("The Product Does Not Exist!\n");   
            printf("Press Enter To Continue....");
            getchar();
            system("cls");
        }
        else if(count==1){
            printf("Input Quantity: ");
            scanf("%d",&quantity);
            current->quantity = quantity;
           
            printf("Edit Successful!\n");
            printf("Press Enter To Continue....");
            getchar();
            getchar();
            system("cls");
        }
    }
}

void deleteProduct(){
    int count=0;
    int amount=0;
    char productName[1000];
    char name[1000];
    int quantity;
    long long int price;
   
    if(head==NULL){
        printf("No Item Has Been Added!\n");
        printf("Press Enter To Continue...\n");
        getchar();
        system("cls");
    }
    else{
        current=head;
        printf("==========================================\n");
        printf("| %28s         |\n","Dreamers Market List");
        printf("==========================================\n");
        printf("|%-3s|%-15s|%-8s|%-10s|\n","No","Product Name","Quantity","Price");
        printf("==========================================\n");
        while(current!=NULL){
            printf("|%-3d|%-15s|%-8d|%-7d RP|\n",amount+1,current->name,current->quantity,current->price);
            current=current->next;
            amount++;
        }
        printf("==========================================\n");
        printf("\n");
       
        count=0;
        printf("Enter Product Name To Delete: ");
        scanf("%[^\n]",productName); getchar();
           
        current=head;
        while(current!=NULL){
            if(strcmp(current->name,productName)==0){
                count=1;
                break;
            }   
            current=current->next;
        }
       
        if(count==0){
            printf("The Product Does Not Exist!\n");   
            printf("Press Enter To Continue....");
            getchar();
            system("cls");
        }
        else if(count==1){
            quantity=current->quantity;
            price=current->price;
            pop(productName,quantity,price);
            printf("Delete Succesful!\n");
            printf("Press Enter To Continue....");
            getchar();
            system("cls");
        }
    }
}

void checkout(){
    int amount=0;
    long long int price;
    long long int totalprice=0;
   
    if(head==NULL){
        printf("No Item Has Been Added!\n");
        printf("Press Enter To Continue...\n");
        getchar();
        system("cls");
    }
    else{
        current=head;
        printf("=========================================================\n");
        printf("| %38s         |\n","Dreamers Market Receipt");
        printf("=========================================================\n");
        printf("|%-3s|%-15s|%-8s|%-10s|%-15s|\n","No","Product Name","Quantity","Price","Total Price");
        printf("=========================================================\n");
        while(current!=NULL){
             price= current->quantity * current->price;
            printf("|%-3d|%-15s|%-8d|%-7d RP|%-12d RP|\n",amount+1,current->name,current->quantity,current->price,price);
            current=current->next;
            amount++;
            totalprice+=price;
        }
        printf("=========================================================\n");
        printf("Total Amount = Free\n");
        printf("Kindness Is Free!");
        printf("\n");
        printf("Press Enter To Continue...");
        getchar();
        system("cls");
    }
}


int main(){
    int input;
   
    do{
        printf("Julian Dreamers Market\n");
        printf("======================\n");
        printf("1. Add Product\n");
        printf("2. Edit Quantity\n");
        printf("3. Delete Product\n");
        printf("4. Checkout\n");
        printf("5. Exit\n");
        printf("Choose: ");
       
        scanf("%d",&input);
        getchar();
       
        system("cls");
       
            switch(input){
                case 1:{
                    addProduct();
                    break;
                }
                case 2:{
                    editProduct();
                    break;
                }
                case 3:{
                    deleteProduct();
                    break;
                }
                case 4:{
                    checkout();
                    break;
                }
            }
    }while(input!=5);
   
    if(input==5){
        printf("Thank You For Using Dreamers Market!\n");
        printf("Press Enter To Exit....");
    }
   
    return 0;
}