Rangkuman Final Data Structure

Rangkuman

Tipe-tipe Linked list:

1. Circular Linked List
2. Double/doubly Linked List
3. Circular Doubly Linked List

Circular Linked Lists:

Linked List yang node terakhirnya (tail) memiliki pointer ke node pertama (head).

Double/doubly Linked List:

Linked list yang setiap nodenya memiliki referensi/pointer ke node sebelum dan sesudahnya. Node sebelum head dan sesudah tail bersifat null.

Circular Douubly Linked List:

Sama seperti Doubly Linked list tetapi node sebelum head memiliki pointer ke tail dan node setelah tail memiliki pointer ke head sehingga memiliki kedua sifat linked list.
Pointer and Arrays
Pointer adalah data type yang nilainya mereferensi nilai lain melalui adressnya dalam komputer, dideklarasikan dengan:
data_type* variable_name;
untuk membuat pointer menuju pointer gunakan,
data_type** variable_name;

Array adalah kumpulan data yang bertipe sama dan disimpan secara berurutan dalam memory dan di lokasikan mengunakan indeks (indeks dimulai dari 0), dideklarasikan menggunakan:
data_type variable_name[size_of_array];

Data Structures

Structure adalah sebuah data type yang dibuat oleh user, structure dapat menyimpan lebih dari satu data type tidak seperti array, dideklarasikan dengan:
struct structure_name{
     data_type variable_name;
}struct_variable_name;

Data Structures example:
-Arrays: koleksi data dengan data type yang sama.
-Linked Lists: data structure yang elemennya dapat dihapus atau ditambahkan kapanpun.
-Queue: data structure yang data pertama yang dimasukan adalah data pertama yang dikeluarkan.
-Stacks: data structure kebalikan dari queue, data terakhir dimasukan adalah data pertama yg dikeluarkan.
-Binary Trees: Sama seperti linked lists tetapi setiap node memiliki pointer ke kiri dan kanan, dan bersifat non circular.

Stack & Queue

Stack

Stack adalah data structure yang menyimpan data secara terurut, sehingga yang pertama keluar adalah yang terakhir dimasukan ke dalam stack (seperti menaruh piring).
mempunyai 2 variable:
-Top: data yang berada di paling luar
-Max: data maksimal yang dapat ada di stack
operation di stack:
-push: menambah item
-pop: membuang item dari atas stack
-top: menunjukan item apa yang berada di atas stack
Prefix, Infix, Postfix
prefix: operator ditulis sebelum operand
infix: operator ditulis ditengah operand
postfix: operator ditulis setelah operand

mengapa dibutuhkan ?
-untuk mempercepat komputasi karena memberitahu order dari komputasi

Queue

Queue adalah data structure yang menyimpan data secara berurut, sehingga yang pertama masuk adalah yang pertama keluar.
mempunyai 2 variabel:
-front: index pertama
-rear: index terakhir
operation di stack:
-push: menambah item
-pop: membuang item dari depan queue
-top: menunjukan item apa yang berada di front queue

Hashing, Hashing Tables and Binary Trees

Hashing

hashing adalah suatu teknik untuk menyimpan dan menemukan kunci secara cepat dengan cara mengubah string menjadi kunci yang lebih pendek.
Metode:
- MidSquare: hashing dengan cara menkuadratkan nilai dari key dan mengambil nilai tengah dari hasil tersebut.
- Division: Hashing dengan cara menggunakan sisa bagi dari kunci.
- Folding: Hashing dengan cara membelah key lalu menjumlahkan keduanya dan mengambil dua digit terakhir.
- Digit Extraction: Hashing dengan cara mengambil nilai dari beberapa index tertentu dari kunci.
- Rotating Hash: Hashing ini dapat menggunakan metode hashing apapun lalu melakukan pergerakan nilainya agar mendapatkan nilai baru.

Collision

Apabila terjadi string dengan hash key yang sama maka terdapat beberapa cara untuk menanganinya:
- linear Probing: Mencari slot kosong berikutnya
- Chaining: menggunakan linked list untuk mengikatnya.

Tree

Data stucture yang memiliki banyak node dan setiap nod maksimal memiliki 2 node.
Setiap node memiliki link parent, left, dan right.

Expression tree:
Membuat expression tree dari sebuah prefix menggunakan rekurif
void f(struct tnode *curr) {
  if ( is_operator(s[p]) ) {
  p++; curr->left  = newnode(s[p]);
  f(curr->left);
  p++; curr->right = newnode(s[p]);
  f(curr->right);

  }
}
(untuk menjelaskan algoritma diatas menggunakan rekursif agar apabila node adalah sebuah operator aritmatika maka akan memanggil dirinya sendiri hingga operaator terakhir lalu kembali)
Algoritma membuat prefix dari expression tree:
void prefix(struct tnode *curr) {
  printf( “%c “, curr->chr );
  if ( curr->left  != 0 ) prefix(curr->left);

  if ( curr->right != 0 ) prefix(curr->right);
}
Algoritma membuat postfix dari expression tree:
void postfix(struct tnode *curr) {
    if ( curr->left  != 0 ) postfix(curr->left);
    if ( curr->right != 0 ) postfix(curr->right);
    printf( “%c“, curr->chr );
}

Code C Data Structure Tugas MiniMarket:

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

struct tnode {
 char name[20];
 int qty;
 int price;
 struct tnode* next;
 struct tnode* prev;
};

struct tnode* input(struct tnode* head){
 if(head==NULL){
  char name[20];
  printf("Name: ");
  scanf("%s",name);
  int qty;
  printf("Quantity: ");
  scanf("%d",&qty);
  struct tnode* node = (struct tnode*)malloc(sizeof(struct tnode));
  head= node;
  strcpy(node->name,name);
  node->qty = qty;
  node->price=rand();
  node->next = NULL;
  node->prev = NULL;
  printf("Success!\n");
 }else{
  char name[20];
  printf("Name: ");
  scanf("%s",name);
  int qty;
  printf("Quantity: ");
  scanf("%d",&qty);
  struct tnode* node = (struct tnode*)malloc(sizeof(struct tnode));
  struct tnode* temp = head;
  while(temp->next!=NULL){
   temp = temp->next;
  }
  strcpy(node->name,name);
  node->qty = qty;
  node->price=rand();
  node->next = NULL;
  temp->next = node;
  node->prev = temp;
  printf("Success!\n");
 }
 return head;
}

struct tnode* edit(struct tnode* head){
 if(head==NULL){
  printf("Cart is empty\n");
 }else{
  bool check=false;
  char name[20];
  int qty;
  printf("Search Name: ");
  scanf("%s",name);
  struct tnode* temp = head;
  if(strcmp(temp->name,name)==0){
   check=true;
  }else{
   while(strcmp(temp->name,name)!=0&&temp->next!=NULL){
    temp = temp->next;
    if(strcmp(temp->name,name)==0){
     check=true;
    }
   }
  }
  if (check==true){
   printf("Change Name: ");
   scanf("%s",name);
   strcpy(temp->name,name);
   int price;
   printf("Change Quantity: ");
   scanf("%d",&qty);
   temp->qty=qty;
  }else{
   printf("not found\n");
  }
 }
 return head;
}

struct tnode* del(struct tnode* head){
 if(head==NULL){
  printf("not found\n");
 } else {
  bool check=false; 
  bool tail=true;
  char name[20];
  printf("Search Name: ");
  scanf("%s",name);
  struct tnode* temp = head;
  if(strcmp(temp->name,name)==0){
   struct tnode* temp = head;
   head = head->next;
   if(head!=NULL){
    head->prev=NULL;
   }
   free(temp);
  }else{
   while(strcmp(temp->name,name)!=0&&temp->next!=NULL){
    temp = temp->next;
    if(strcmp(temp->name,name)==0){
     check=true;
    }
    if(temp->next==NULL){
     tail=true;
    }
   }
  }
  
  
  if (check==true){
   if(tail==true){
    temp->prev->next=NULL;
   }else{
    printf("Search Name: ");
    if(temp->next!=NULL){
     temp->prev->next=temp->next;
    }else{
     temp->prev->next=NULL;
    }
    if(temp->prev!=NULL){
     temp->next->prev=temp->prev; 
    }
    else{
     temp->next->prev=NULL;
    }
    free(temp);
   }
  }else{
   printf("not found\n");
  }
 }
 return head;
}

void checkOut(struct tnode* head){
 int x=1;
 long int total=0;
 long int totals=0;
 if (head==NULL){
  printf("Cart is empty\n");
 }else{
  printf("Receipt:\n");
  struct tnode* temp = head;
  while(temp->next!=NULL){
   total=temp->price*temp->qty;
   totals+=total;
   printf("%d. %s || %d || %d || total:%d\n",x,temp->name,temp->price,temp->qty,total);
   temp=temp->next;
   x++;
  }
  total=temp->price*temp->qty;
   totals+=total;
   printf("%d. %s || %d || %d || total:%d\n",x,temp->name,temp->price,temp->qty,total);
  printf("Harga total: %d",totals);
 }

}

void menu(struct tnode* head){
 int x=1;
 struct tnode* temp = head;
 printf("========================================\n");
 printf("Cart(no/name/price/quantity):\n");
 if(head!=NULL){
  printf("%d. %s || %d || %d\n",x,temp->name,temp->price,temp->qty);
  while(temp->next!=NULL){
   temp=temp->next;
   x++;
   printf("%d. %s || %d || %d\n",x,temp->name,temp->price,temp->qty);
  }
 }
 printf("========================================\n");
 printf("Choices:\n1. Input\n2. Edit\n3. delete\n4. Checkout\n");
}

int main(){
 int choice;
 struct tnode* head = NULL;
 do{
  menu(head);
  printf("Insert Input: ");
  scanf("%d",&choice);
  switch (choice){
   case 1:{
    head=input(head);
    break;
   }
   case 2:{
    head=edit(head);
    break;
   }
   case 3:{
    head=del(head);
    break;
   }
   case 4:{
    checkOut(head);
    break;
   }
  }
 }while(choice!=4);

AVL TREE

AVL Tree is a self balancing binary tree that changes when a new node is inserted. This makes it faster to search for a specific node.

INSERTION

There are 4 cases for tree balancing if a new node is inserted:
Case 1 : the deepest node is located at the left sub tree of the left child of T.
Case 2 : the deepest node is located at the right sub tree of the right child of T.
Case 3 : the deepest node is located at the right sub tree of the left child of T.
Case 4 : the deepest node is located at the left sub tree of the right child of T.

there are 2 types of rotations in tree balancing, single rotation and double rotation. the following is all the possible rotation variant:
LL rotation: the new node is inserted in the left sub-tree of the left sub-tree of the critical node
RR rotation: the new node is inserted in the right sub-tree of the right sub-tree of the critical node.
LR rotation: the new node is inserted in the right sub-tree of the left sub-tree of the critical node
RL rotation: the new node is inserted in the left sub-tree of the right sub-tree of the critical node

DELETION

the following are all the possible rotation variants of delete operation:
Case 1 : y is left child of z and x is left child of y (Left Left Case)
Case 2 : y is left child of z and x is right child of y (Left Right Case)
Case 3 : y is right child of z and x is right child of y (Right Right Case)
Case 4 : y is right child of z and x is left child of y (Right Left Case)

HEAPS & TRIES

Heaps

Heaps adalah binary tree yang terdiri dari 3 jenis:
- min heap: setiap node lebih kecil daripada childrennya.
- max heap: setiap node lebih besar daripada childrennya.
- min-max heap: node terkecil terdapat pada root dan node terbesar berada pada children root.

operation dalam heap (tergantung jenis heap):

find-min/max  : mencari node terkecil/terbesar.
insert  : memasukan node kedalam heap.
delete-min/max: menghapus elemen terkecil/terbesar.

Representasi heap dalam array:

Rumus lokasi node heap dalam suatu array (sudah pasti):

-Parent(x) = x / 2
-Left-child(x) = 2 * x
-Right-child(x) = 2 * x + 1

Tries

Tries adalah data structure yang efisien dan menggunakan waktu pencarian selama banyaknya character yang dicari. Root node pada suatu tries selalu kosong untuk menggabungkan seluruh children dari root.



Tries digunakan dalam aplikasi search and spell checker.

}