Summary

Linked List

Pada pertemuan kedua kelas besar kemarin saya belajar mengenai cara membuat linked list di C. Setelah saya mempelajarinya kemarin, saya juga mencoba membuat linked list buatan saya sendiri. Berikut codingan linked list saya :

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

struct Node{
int test;
char nama[1000];
struct Node *next;
}*head,*curr,*tail,*temp1,*temp2;

void pushhead(int a,char nama[]){
curr = (struct Node*)malloc(sizeof(struct Node));
curr -> test = a;
strcpy(curr->nama,nama);
if(head==NULL){
head=curr;
tail=curr;
tail->next=NULL;
}
else{
curr->next = head;
head = curr;
}
}

void pushtail(int a,char nama[]){
curr = (struct Node*)malloc(sizeof(struct Node));
curr -> test = a;
strcpy(curr->nama,nama);
if(head==NULL){
head=curr;
tail=curr;
tail->next=NULL;
}
else{
tail->next = curr;
curr->next=NULL;
tail = curr;
}
}

void poptail(){
curr=head;
while(curr->next->next!=NULL){
curr=curr->next;
}
free(tail);
tail=curr;
tail->next=NULL;
}

void pophead(){
curr=head;
curr=curr->next;
free(head);
head=curr;
}

void print(){
curr=head;
while(curr!=NULL){
printf("%d %s\n",curr->test,curr->nama);
curr=curr->next;
  }
}

void pushmiddle(int a,char nama[],int urutan1,int urutan2){
curr = (struct Node*)malloc(sizeof(struct Node));
curr -> test = a;
strcpy(curr->nama,nama);
temp1=temp2=head;
for(int i=1;i<urutan1;i++){
temp1=temp1->next;
}
temp2=temp1->next;
temp1->next=curr;
curr->next=temp2;
}

void popmiddle(int urutan){
curr=head;
for(int i=1;i<urutan-1;i++){
curr=curr->next;
}
temp1=curr->next;
curr->next=temp1->next;
free(temp1);
}

int main(){
pushtail(1,"a");
pushtail(2,"b");
pushtail(3,"c");
pushtail(4,"d");
pushtail(5,"e");
pushtail(6,"f");
pushtail(7,"g");
pushtail(8,"h");
pushhead(0,"bukan huruf");
pophead();
poptail();
popmiddle(4);
pushmiddle(100,"ivano",3,4);
print();
}

Ada juga double linked list yang memiliki node next dan previous yang berarti satu node itu memiliki 2 tangan yang memegang node sebelumnya dan setelahnya.

Stack & Queue

Queue adalah sebuah konsep yang dapat diimplementasikan menggunakan linked list atau array. Queue menggunakan prinsip First In First Out(FIFO) yang berarti data yang pertama masuk akan menjadi yang pertama keluar. Berikut contoh gambaran mengenai Queue.
Amalkan Ilmu Berbagi Untuk Semua: Pemodelan Dalam Sistem Antrian
Pada gambar tersebut merupakan sebuah antrian, bagi siapa yang masuk pertama maka akan dilayani pertama kali dan keluar lebih cepat. Jika kita mengimplementasikan Queue pada C maka operator yang digunakan adalah pushtail dan pophead yang dapat dilihat pada kodingan diatas bab ini.
Stack adalah sebuah konsep yang dapat diimplementasikan menggunakan array atau linked list juga. Stack menggunakan prinsip Last In First Out(LIFO) yang berarti data yang terakhir kali masuk akan menjadi yang pertama keluar. Berukut contoh gambaran mengenai Stack.
Stacks and Queues
Pada gambar tersebut bisa dicontohkan seperti tumpukan sebuah buku yang dimana jika ingin mengambil buku yang bawah maka harus mengambil buku yang atas terlebih dahulu. Stack pada C maka operator yang digunakan adalah pushead dan pophead yang dapat dilihat pada kodingan diatas bab ini.

Hashing & Binary Tree

Hashing and Hash Table

Hashing adalah transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau menjadi sebuah kunci yang mewakili string aslinya. Hashing digunakakn untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hahs yang lebih pendek daripada menemunkannya mengginakan nilai asli. Hashing juga bisa didefinisikan sebagai konsep yang mendistribusikan kunci ke dalam array yang biasa disebut "Hash Table" yang menggunakan sebuah fungsi yang biasa disebut "Hash Function". Hash Table ada table yang berupa array yang merupakan tempat dimana kita menyimpan string yang asli. Index yang terdapat pada tabel adalah hashed key atau key yang telah didapat melalui suatu proses sementara isi dari array tersebut adalah original stringnya. Biasanya ukuran dari Hash Table ini cukup kecil sehingga memungkinkan untuk menghasilkan hashed key atau kunci yang sama.

Hash Function

Ada berbagai macam cara untuk transformasi string untuk menjadi sebuah key. Berikut adalah beberapa method yang penting untuk membentuk Hash Function :
  1. Mid-square
  2. Division
  3. Folding
  4. Digit Extraction
  5. Rotating Hash

Collision

Pada sebelumnya sudah saya katakan bahwa akan ada kemungkinan untuk suatu string menghasilkan key yang sama. Hal ini biasa disebut Collision. Untuk mengatasi hal tersebut maka 2 cara untuk mengatasi kejadian ini :
  • Linear Probing
          Mencari slot kosong disebelahnya dan memasukkannya pada slot kosong tersebut.
  • Chaining
          Meletakkan string pada slot tersebut dengan cara chained list (linked list).

Trees & Binary Tree

Untuk memahami Trees & Binary Tree, lebih baik kita memahami terlebih dahuli bagaimana konsep dari Tree dan Binary Tree. Berikut gambar dari konsep Trees dan Binary Tree.
Berikut sebuah codingan simple tree di C
struct node  
{ 
    int data; 
    struct node *left; 
    struct node *right; 
}; 
  
struct node* newNode(int data) 
{  
  struct node* node = (struct node*)malloc(sizeof(struct node)); 
  
  node->data = data; 
  
  node->left = NULL; 
  node->right = NULL; 
  return(node); 
} 
  
  
int main() 
{ 

  struct node *root = newNode(1);   
  root->left        = newNode(2); 
  root->right       = newNode(3); 
  root->left->left  = newNode(4); 

  getchar(); 
  return 0; 
}

Binary Search Tree

Berikut kodingan saya sendiri mengenai Binary Search Tree.

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

int flag = 0;

struct node{
int angka;
struct node *left;
struct node *right;
};

struct node *NodeBaru(int InputanAngka){
//bkin structnya buat ditempatin di akar paling bawah
struct node *temp = (struct node*) malloc (sizeof(struct node));
temp->angka = InputanAngka;
temp->left=temp->right=NULL;
}

struct node *MasukkanAngka(struct node *ROOT,int InputanAngka){
//klo misal akar yang ditempatinya NULL yauda tinggal dimasukkin datanya
if(ROOT==NULL){
return NodeBaru(InputanAngka);
}
//bakal pindah akar ke kiri teros klo lebih kecil smpe nemu NULL^
if(InputanAngka < ROOT->angka){
ROOT->left = MasukkanAngka(ROOT->left, InputanAngka);
}
//bakal pindah akar ke kanan teros klo lebih besar dr smua angka smpe nemu NULL^
else if(InputanAngka > ROOT->angka){
ROOT->right = MasukkanAngka(ROOT->right, InputanAngka);
}
}

struct node *CariNode(struct node *root){
struct node *curr = root->left;
while(curr->right!=NULL){
curr = curr->right;
}
return curr;
}

struct node *HapusAngka (struct node *root, int AngkaYangDicari){
//klo data ga ditemukan
if(root==NULL){
flag = 2;
return NULL;
}
//cari angka di root kiri
else if(AngkaYangDicari < root->angka){
root->left = HapusAngka(root->left,AngkaYangDicari);
}
//cari angka di root kanan
else if(AngkaYangDicari > root->angka){
root->right = HapusAngka(root->right,AngkaYangDicari);
}
//angkanya udah ketemu
else{
//ini untuk case klo rootnya punya 1 cabang atau tidak punya sama sekali
if(root->left==NULL||root->right==NULL){
struct node *temp = NULL;
if(root->right!=NULL){
temp=root->right;
}
else{
temp=root->left;
}
//jika tidak mempunyai cabang samsek
if(temp==NULL){
root=NULL;
}
//jika terdapat salah satu cabang
else{
*root = *temp;
}
free(temp);
}
//ini untuk case yang terdapat 2 cabang
else{
//cari node paling kanan di root->left
struct node *temp = CariNode(root);
root->angka=temp->angka;

//deletenya
root->left=HapusAngka(root->left,temp->angka);
}
}
return root;
}

void PrintAll(struct node *root){
//klo misal akar yg diliatnya skrg udah NULL printnya berhenti
if(root!=NULL){
//nge print smua yg dikiri
PrintAll(root->left);
printf("%d\n",root->angka);
//ini biar printnya bisa liat angka yang dikanan
PrintAll(root->right);
}
}

int main(){
int Menu,AngkaInput,AngkaDelete;
//ini biar jadi pusat akarnya
struct node *root = NULL;
do{
if(flag==0){
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
}
else if (flag==1){
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
PrintAll(root);
flag=0;
}
else if(flag==2){
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
printf("Data Tidak Ditemukan!\n");
}
printf("BINARY SEARCH TREE\n");
printf("Menu :\n");
printf("1. Masukkan Angka\n");
printf("2. Hapus Angka\n");
printf("3. Print Angka\n");
printf("4. Exit\n");
printf(">> ");
scanf("%d",&Menu);
if(Menu==1){
printf("Input Angka : ");
scanf("%d",&AngkaInput);
root=MasukkanAngka(root,AngkaInput);
}else if(Menu==2){
printf("Tulis Angka Yang Mau Dihapus : ");
scanf("%d",&AngkaDelete);
root=HapusAngka(root,AngkaDelete);
}else if(Menu==3){
flag=1;
}
}while(Menu!=4);
}


TUGAS KELAS BESAR(dreammers market)

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

int valid;

struct node{
int Quantity;
int Price;
char NameProduct[1000];
int SubTotal;
struct node* next;
struct node* prev;
}*head,*temp,*curr;

void insert(char Item[],int Quantity,int Price){
//BKIN NODE SAMA ISI VARIABEL
struct node* NodeBaru = (struct node*) malloc (sizeof(struct node));
strcpy(NodeBaru->NameProduct, Item);
NodeBaru->Price=Price;
NodeBaru->Quantity=Quantity;
NodeBaru->SubTotal=Price*Quantity;
NodeBaru->prev=NULL;
NodeBaru->next=NULL;
//MULAI INPUT
temp=head;
if(head==NULL){
head=NodeBaru;
}
else{
while(temp->next!=NULL){
temp=temp->next;
}
NodeBaru->prev=temp;
temp->next=NodeBaru;
}
}

void Sort(){
int nilai,penggantinilai;
char pengganti[1000];
temp=head;
if(head!=NULL){
while(temp->next!=NULL){
nilai=strcmp(temp->NameProduct,temp->next->NameProduct);
if(nilai==1){
//TUKAR NAMA
strcpy(pengganti,temp->NameProduct);
strcpy(temp->NameProduct,temp->next->NameProduct);
strcpy(temp->next->NameProduct,pengganti);
//TUKAR PRICE
penggantinilai=temp->Price;
temp->Price=temp->next->Price;
temp->next->Price=penggantinilai;
//TUKAR QUANTITY
penggantinilai=temp->Quantity;
temp->Quantity=temp->next->Quantity;
temp->next->Quantity=penggantinilai;
}
temp= temp->next;
}
}
}

void ShowTable1(){
int total=0;
curr=head;
if(head!=NULL){
while(curr->next!=NULL){
printf("%s - %d - Rp%d - Subtotal : Rp%d\n",curr->NameProduct,curr->Quantity,curr->Price,curr->SubTotal);
total += curr->SubTotal;
curr=curr->next;
}
printf("%s - %d - Rp%d - Subtotal : Rp%d\n",curr->NameProduct,curr->Quantity,curr->Price,curr->SubTotal);
total += curr->SubTotal;
printf("\nTOTAL HARGA : Rp%d\n",total);
printf("~Kindess is Free~\n");
}
else{
printf("DATA NOT FOUND!\n");
printf("~Kindess is Free~\n");
}
}

void ShowTable(){
curr=head;
if(head!=NULL){
while(curr->next!=NULL){
printf("%s - %d - Rp%d\n",curr->NameProduct,curr->Quantity,curr->Price);
curr=curr->next;
}
printf("%s - %d - Rp%d\n",curr->NameProduct,curr->Quantity,curr->Price);
}
else{
printf("DATA NOT FOUND!\n");
}
}

void CariNama(char namacari[]){
int nilai;
curr=head;
while(curr->next!=NULL){
nilai=strcmp(namacari,curr->NameProduct);
if(nilai==0){
valid=1;
break;
}
curr=curr->next;
}
nilai=strcmp(namacari,curr->NameProduct);
if(nilai==0){
valid=1;
}
}

void Edit(int newquantity){
curr->Quantity=newquantity;
}

void Delete(){
if(curr->next==NULL&&curr->prev==NULL){
free(curr);
head=NULL;
}
else if(curr->next!=NULL&&curr->prev==NULL){
head=curr->next;
free(curr);
head->prev=NULL;
}
else if(curr->next==NULL){
temp=curr->prev;
temp->next=NULL;
free(curr);
}
else{
temp=curr->prev;
temp->next=curr->next;
temp=curr->next;
temp->prev=curr->prev;
free(curr);
}
}

void clear(){
for(int i=0;i<40;i++){
printf("\n");
}
}

int main(){
int pilihan;
srand(time(0));
clear();
do{
ShowTable();
printf("\n====Welcome to BetaMarket====\n");
printf("1. Input Item Baru\n");
printf("2. Edit Item\n");
printf("3. Delete Item\n");
printf("4. Checkout\n");
printf("Choose>> ");
scanf("%d", &pilihan);
//INPUT ITEM
if(pilihan==1){
clear();
char Item[1000];
int Quantity, RandomPrice;
printf("Input item name: ");
scanf(" %[^\n]",&Item);
printf("Input the quantity of %s: ",Item);
scanf("%d",&Quantity);
//SET RANDOM FROM 1K to 10K
RandomPrice = rand()%9000;
RandomPrice += 1000;
//INSERT AND SORT
insert(Item,Quantity,RandomPrice);
clear();
printf("Add item success...\n");
}
//EDIT ITEM
else if(pilihan==2){
char namaedit[1000];
int newquantity;
clear();
if(head==NULL){
}
else{
valid=0;
ShowTable();
do{
printf("\nInput item name that you want to edit: ");
scanf(" %[^\n]",&namaedit);
CariNama(namaedit);
if(valid==1){
printf("Input the new quantity : ");
scanf("%d",&newquantity);
Edit(newquantity);
clear();
}
else{
printf("Name not found!\n");
}
}while(valid==0);
}
}
//DELETE ITEM
else if(pilihan==3){
char namadelete[1000];
clear();
if(head==NULL){
}
else{
ShowTable();
valid=0;
do{
printf("\nInput item name that you want to delete: ");
scanf(" %[^\n]",&namadelete);
CariNama(namadelete);
if(valid==1){
Delete();
clear();
}
else{
printf("Name not found!\n");
}
}while(valid==0);
}
}
//CHECKOUT
else if(pilihan==4){
clear();
Sort();
printf("Your Bill\n");
ShowTable1();
}
}while(pilihan!=4);
}

Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree

Gambar
Pada dasarnya AVL Tree ini adalah Binary Search Tree namun yang lebih seimbang atau balance karena pasti total node kiri dan kanan selisih tingginya tidak akan lebih dari 1. Sedangkan di BST bisa saja tinggi node kiri dan kanan tidak seimbang sehingga bisa menyebabkan proses pencarian, insert, maupun delete lebih lama yaitu n sedangkan dengan AVL Tree proses pencarian,insert, atau delete menjadi log n. Contoh hasil BST jika dengan insert 2, 5, 7, 8, 13: Contoh hasil AVL Tree jika dengan insert yang sama: Untuk menyeimbangkan node tersebut, AVL Tree menggunakan rotasi atau rotation. Rotation ini dibagi menjadi 2 yaitu single rotation dan double rotation. rotation ini terjadi akibat perbedaan selisih tinggi node kiri dan kanan yang lebih dari 1. Contoh single rotation Contoh double rotation
Baca selengkapnya

HEAP and TRIES

Gambar
HEAP Heaps adalah binary tree yang nodenya dapat direpresentasikan dalam sebuah array. Type of Heap A. Max Heap Max yang berarti parentnya lebih besar daripada childnya. Elemen terbesar pada Max Heap terdapat di root tree dan semakin kebawah artinya semakin kecil. B. Min Heap Min yang berarti parentnya lebih kecil daripada childnya. Elemen terbesar pada Min Heap terdapat di root tree dan semakin kebawah artinya semakin besar. Heap dapat diimplementasikan menggunakan linked list tapi lebih mudah menggunakan array. C. Min Max Heap Ini adalah case unik atau spesial dari heap. Max dan min bergantian pada setiap level. Urutan level dari heap berupa min(dimulai dari root) lalu max lalu min lagi dan seterusnya. Pada bagian min akan selalu ganjil dan max akan selalu genap. Di dalam heap terdapat 2 metode yaitu insertion dan deletion. Max Heap Insertion step 1 : membuat node baru di akhir dari heap step 2 : memasukkan nilai baru ke node tersebut ste...
Baca selengkapnya