Rangkuman Data Structure selama 1 semester
Nama : Clarik Linadi
NIM :2301883901
Kelas : CB01
Lecturer : Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460)
Linked List
Linked List adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.
- Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
- Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list
Ada beberapa macam Linked List, yaitu :
- Single Linked List
- Double Linked List
- Circular Linked List
- Multiple Linked List
- Doubly Linked List
- Circular Doubly Linked List
Tetapi untuk sekarang saya akan menjelaskan tentang Circular Single Linked List, Doubly Linked List dan Circular Doubly Linked List.
Double Linked List
Double Linked List adalah salah satu contoh lain implementasi linked list selain single linked list. Sesuai namanya, Double artinya blok data yang kita miliki akan memiliki 2 penunjuk kiri dan kanan untuk menentukan data sebelum/sesudahnya. Berbeda dengan single linked list yang hanya mempunyai satu penunjuk, double linked list mempunyai 2 penunjuk kiri dan kanan untuk menentukan urutan datanya.
Circular Linked List
Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL.
Ada 2 jenis Circular Linked List, yaitu :
- Circular Single Linked List
- Circular Double Linked List
Circular Single Linked List
Circular Double Linked List
Linked List
Single Linked List
Linked List merupakan kumpulan dari banyak data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui pointer. Linked List bisa juga disebut kumpulan data linear.
Linked List yang memiliki satu penghubung dengan node lain, disebut single linked list.
Dalam Linked List pasti terdapat node yang bernama head dan tail. Head yang dimaksud disini adalah penunjuk untuk menunjukkan dimana letak data pertama dan tail menunjukkan dimana letak data terakhir.
Sebuah linked list, dikatakan kosong jika tidak memiliki head yang menandakan bahwa node tersebut kosong.
Operasi pada single linked list:
1. Push (Memasukkan data)
2. Pop (Menghapus data dari Node)
1. Push
Push merupakan operasi pada linked list untuk menginsert suatu data pada node, push bisa saja dilakukan pada head, tail, ataupun index.
Contoh push adalah sebagai berikut:
Jika terdapat node yang berisi angka 7, 6, 9, 3, 5 , NULL
Kemudian pushHead(4) maka hasilnya akan menjadi 4, 7, 6, 9, 3, 5, NULL
Sama halnya jika melakukan pushTail(10) hasilnya akan menjadi 4, 7, 6, 9, 3, 5, 10, NULL
Untuk contoh kode pushHead bisa dilihat dibawah ini
public void pushHead(int n){ // int n ini merupakan data yang akan dimasukkan pada linked list
struct Data* curr = (struct Data*)malloc(sizeof(Data));
curr->isi = n;
if(head==NULL) head = tail = curr; // Jika belum terdapat head
else{
curr->next = head;
head = curr;
}
}
2. Pop
Pop merupakan kebalikan dari push, dimana fungsi pop adalah mendelete suatu data dalam linked list dan melepaskanny agar memory dapat dipakai kembali. Pop biasa digunakan untuk mendelete head, tail ataupun suatu index.
Contoh pop:
terdapat suatu data 1, 5, 6, 7, 8, 9, NULL
Kemudian popHead() maka hasilnya akan menjadi 5, 6, 7, 8, 9, NULL
Jika popTail() maka hasilnya akan menjadi 5, 6, 7, 8, NULL
Untuk contoh kode dari popHead bisa dilihat dibawah ini
void popHead(){
struct Data* curr = head;
head = head->next; // merubah head ke angka selanjutnya dikarenakan angka pada head akan dilepas
free(curr);
}
Kesimpulannya, jika ingin memproses suatu data sangat disarankan menggunakan konsep array dinamis untuk memakai Single Linked List ataupun Double Linked List di karenakan jika memakai array yang statis, penggunaan ruang memori yang sudah digunakan tidak dapat dihapus apabila nama variable array tersebut sudah tidak digunakan kembali dalam suatu program.
Hash Table and Binary Tree
Ketika kita diberikan data yang sangat banyak, kita harus membutuhkan suatu data structure yang cepat untuk melakukan banyak hal (insert, delete,dan search). Seharusnya kita mempunyai kunci(key) untuk dapat mengakses data tersebut, agar ketika kita mencari, kita hanya tinggal memakai key tersebut, sehingga waktu yang diperlukan untuk mencari data lebih efisien, karena sudah mendekati dimana lokasi data tersebut dibanginkan jika kita mencari data secara linear(satu per satu). Ada beberapa cara untuk mengimplementasi cara penggunaan key ini, contoh nya seperti, hash table, balanced binary search tree(bst) dan doubly linked list.
Hash Table
Untuk sekarang, saya akan menjelaskan tentang hash table. Hash table merupakan method tercepat yang dapat digunakan insert,delete dan search dibandingkan bst dan double linked list.
Di dalam hash table terdapat suatu function bernama hash function, hash function adalah function untuk menempatkan index dari suatu key dalam suatu array.
Ada banyak cara hash function seperti, salah satu contohnya division method, division method adalah salah satucara pada hash function dimana kita akan menaruh suatu index pada array h dimana
h(k) = k%m , k disini merupakan key dan m merupakan panjang arraynya.
dibawah ini merupakan contoh dari division method:
untuk contoh disamping, terdapat key 1276, maka index dari key tersebut akan disimpan dalam array ke - [6]
Namun, apa yang terjadi jika dalam array tersebut telah terdapat data yang telah disimpan? ini disebut hash collision. Ada banyak cara untuk mengatasi hash collisin ini, contohnya seperti open addressing dan closed addressing.
Open Addressing
suatu cara yang digunakan untuk mencari tempat kosong setelah tempat key tersebut terisi.
Contoh penggunaan open addressing pada bahasa C
Closed Addressing
cara yang digunakan untuk menempatkan suat data secara linked list.
Contoh penggunaan closed addressing
Binary Tree
Tree Concept
Tree adalah sebuah struktur data yang memiliki bentuk sebuah pohon, yang terdiri dari serangkaian node (simpul) berisi data yang saling berhubungan.
Binary tree
Binary Tree adalah sebuah pohon yang menyimpan data, keunikan binary tree adalah mensortir semua data yang dimasukkan. Sebuah binary search tree memiliki root dan cabang left serta right pada setiap nodenya.
dalam binary tree, kita dapat melakukan insert.
Contoh dari insert dalam binary tree: mencari dari parent dimana lokasi yang tepat untuk memasukkan nilai, dan jika ditemukan bahwa parentnya tersebut NULL, masukkan ke dalam parent
Berikut adalah contoh code di C jika kita ingin memasukkan data sesuai gambar diatas
Demikian penjelasan saya mengenai Hash Table dan Binary Tree, terima kasi telah membaca
^ ^
Binary Tree
Binary tree adalah pohon dalam suatu struktur data yang berbentuk seperti pohon. Binary tree biasanya terdiri dari 2 anak dan binary tree tidak memiliki anak lebih dari 3 level dari root.
Jika dilihat contoh diatas, angka 7 dan 5 berada pada level 1, angka 2,6, dan 9 berada pada level 2 dst.
Binary Search Tree
Binary Search Tree adalah tree yang terurut. Binary Search Tree sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Implemetasi binary search tree ini biasanya data akan dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari anak satu pertama yang disebut dengan istilah root. Root tersebut memiliki anak(rootbaru) kiri dan anak kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dengan metode in-order. Data yang telah tersusun dalam struktur data BST dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada worstcase dimana BST berbentuk seperti linked list.
Contoh implementasi code C insert,delete dalam bst.
/*
#include <stdio.h>
#include <stdlib.h>
struct Node{
int value;
Node *left,*right;
}*root,*curr;
Node *createNode(int val){
curr = (Node*) malloc(sizeof(Node));
curr->value = val;
curr->left = curr->right = NULL;
return curr;
}
Node *insertNode(Node *parent,int value){
if(!parent)
return createNode(value);
else if(parent->value == value)
return parent;
else if(parent->value > value)
parent->left = insertNode(parent->left,value);
else
parent->right = insertNode(parent->right,value);
}
Node *removeNode(Node *parent,int value){
if(!parent)
return parent;
else if(parent->value > value)
parent->left = removeNode(parent->left,value);
else if(root->value < value)
parent->left = removeNode(parent->left,value);
else if(parent->value == value){
if(parent->left == NULL || parent->right == NULL){
Node *temp = parent->left != NULL ? parent->left : parent->right;
if(temp)
*parent = *temp;
else{
temp = parent;
parent = NULL;
}
free(temp);
}
else{
Node *temp = parent->left;
while(temp->right)
temp = temp->right;
parent->left=removeNode(parent->left,temp->value);
}
return parent;
}
}
void print(Node *parent){
if(parent){
print(parent->left);
printf("%d ",parent->value);
print(parent->right);
}
}
int main(){
root = insertNode(root,20);
root = insertNode(root,5);
root = insertNode(root,14);
root = insertNode(root,3);
root = insertNode(root,16);
root = insertNode(root,22);
root = insertNode(root,19);
root = removeNode(root,3);
//print in order
print(root);
}
*/
Terima Kasih ^ ^
Summary
Linked List
Linked List adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.
- Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
- Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list
Ada beberapa macam Linked List, yaitu :
- Single Linked List
- Double Linked List
- Circular Linked List
- Multiple Linked List
- Doubly Linked List
- Circular Doubly Linked List
Single Linked List
Linked List merupakan kumpulan dari banyak data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui pointer. Linked List bisa juga disebut kumpulan data linear.
Linked List yang memiliki satu penghubung dengan node lain, disebut single linked list.
Dalam Linked List pasti terdapat node yang bernama head dan tail. Head yang dimaksud disini adalah penunjuk untuk menunjukkan dimana letak data pertama dan tail menunjukkan dimana letak data terakhir.
Sebuah linked list, dikatakan kosong jika tidak memiliki head yang menandakan bahwa node tersebut kosong.
Operasi pada single linked list:
1. Push (Memasukkan data)
2. Pop (Menghapus data dari Node)
1. Push
Push merupakan operasi pada linked list untuk menginsert suatu data pada node, push bisa saja dilakukan pada head, tail, ataupun index.
Contoh push adalah sebagai berikut:
Jika terdapat node yang berisi angka 7, 6, 9, 3, 5 , NULL
Kemudian pushHead(4) maka hasilnya akan menjadi 4, 7, 6, 9, 3, 5, NULL
Sama halnya jika melakukan pushTail(10) hasilnya akan menjadi 4, 7, 6, 9, 3, 5, 10, NULL
Untuk contoh kode pushHead bisa dilihat dibawah ini
public void pushHead(int n){ // int n ini merupakan data yang akan dimasukkan pada linked list
struct Data* curr = (struct Data*)malloc(sizeof(Data));
curr->isi = n;
if(head==NULL) head = tail = curr; // Jika belum terdapat head
else{
curr->next = head;
head = curr;
}
}
2. Pop
Pop merupakan kebalikan dari push, dimana fungsi pop adalah mendelete suatu data dalam linked list dan melepaskanny agar memory dapat dipakai kembali. Pop biasa digunakan untuk mendelete head, tail ataupun suatu index.
Contoh pop:
terdapat suatu data 1, 5, 6, 7, 8, 9, NULL
Kemudian popHead() maka hasilnya akan menjadi 5, 6, 7, 8, 9, NULL
Jika popTail() maka hasilnya akan menjadi 5, 6, 7, 8, NULL
Untuk contoh kode dari popHead bisa dilihat dibawah ini
void popHead(){
struct Data* curr = head;
head = head->next; // merubah head ke angka selanjutnya dikarenakan angka pada head akan dilepas
free(curr);
}
Double Linked List
Double Linked List adalah salah satu contoh lain implementasi linked list selain single linked list. Sesuai namanya, Double artinya blok data yang kita miliki akan memiliki 2 penunjuk kiri dan kanan untuk menentukan data sebelum/sesudahnya. Berbeda dengan single linked list yang hanya mempunyai satu penunjuk, double linked list mempunyai 2 penunjuk kiri dan kanan untuk menentukan urutan datanya.
Circular Linked List
Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL.
Ada 2 jenis Circular Linked List, yaitu :
- Circular Single Linked List
- Circular Double Linked List
Circular Single Linked List
Circular Double Linked List
Hash Table and Binary Tree
Ketika kita diberikan data yang sangat banyak, kita harus membutuhkan suatu data structure yang cepat untuk melakukan banyak hal (insert, delete,dan search). Seharusnya kita mempunyai kunci(key) untuk dapat mengakses data tersebut, agar ketika kita mencari, kita hanya tinggal memakai key tersebut, sehingga waktu yang diperlukan untuk mencari data lebih efisien, karena sudah mendekati dimana lokasi data tersebut dibanginkan jika kita mencari data secara linear(satu per satu). Ada beberapa cara untuk mengimplementasi cara penggunaan key ini, contoh nya seperti, hash table, balanced binary search tree(bst) dan doubly linked list.
Hash Table
Untuk sekarang, saya akan menjelaskan tentang hash table. Hash table merupakan method tercepat yang dapat digunakan insert,delete dan search dibandingkan bst dan double linked list.
Di dalam hash table terdapat suatu function bernama hash function, hash function adalah function untuk menempatkan index dari suatu key dalam suatu array.
Ada banyak cara hash function seperti, salah satu contohnya division method, division method adalah salah satucara pada hash function dimana kita akan menaruh suatu index pada array h dimana
h(k) = k%m , k disini merupakan key dan m merupakan panjang arraynya.
dibawah ini merupakan contoh dari division method:
untuk contoh disamping, terdapat key 1276, maka index dari key tersebut akan disimpan dalam array ke - [6]
Namun, apa yang terjadi jika dalam array tersebut telah terdapat data yang telah disimpan? ini disebut hash collision. Ada banyak cara untuk mengatasi hash collisin ini, contohnya seperti open addressing dan closed addressing.
Open Addressing
suatu cara yang digunakan untuk mencari tempat kosong setelah tempat key tersebut terisi.
Contoh penggunaan open addressing pada bahasa C
Closed Addressing
cara yang digunakan untuk menempatkan suat data secara linked list.
Contoh penggunaan closed addressing
Binary Tree
Tree Concept
Tree adalah sebuah struktur data yang memiliki bentuk sebuah pohon, yang terdiri dari serangkaian node (simpul) berisi data yang saling berhubungan.
Binary tree
Binary Tree adalah sebuah pohon yang menyimpan data, keunikan binary tree adalah mensortir semua data yang dimasukkan. Sebuah binary search tree memiliki root dan cabang left serta right pada setiap nodenya.
dalam binary tree, kita dapat melakukan insert.
Contoh dari insert dalam binary tree: mencari dari parent dimana lokasi yang tepat untuk memasukkan nilai, dan jika ditemukan bahwa parentnya tersebut NULL, masukkan ke dalam parent
Berikut adalah contoh code di C jika kita ingin memasukkan data sesuai gambar diatas
Binary Search Tree
Binary Search Tree adalah tree yang terurut. Binary Search Tree sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Implemetasi binary search tree ini biasanya data akan dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari anak satu pertama yang disebut dengan istilah root. Root tersebut memiliki anak(rootbaru) kiri dan anak kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dengan metode in-order. Data yang telah tersusun dalam struktur data BST dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada worstcase dimana BST berbentuk seperti linked list.
Contoh implementasi code C insert,delete dalam bst.
/*
#include <stdio.h>
#include <stdlib.h>
struct Node{
int value;
Node *left,*right;
}*root,*curr;
Node *createNode(int val){
curr = (Node*) malloc(sizeof(Node));
curr->value = val;
curr->left = curr->right = NULL;
return curr;
}
Node *insertNode(Node *parent,int value){
if(!parent)
return createNode(value);
else if(parent->value == value)
return parent;
else if(parent->value > value)
parent->left = insertNode(parent->left,value);
else
parent->right = insertNode(parent->right,value);
}
Node *removeNode(Node *parent,int value){
if(!parent)
return parent;
else if(parent->value > value)
parent->left = removeNode(parent->left,value);
else if(root->value < value)
parent->left = removeNode(parent->left,value);
else if(parent->value == value){
if(parent->left == NULL || parent->right == NULL){
Node *temp = parent->left != NULL ? parent->left : parent->right;
if(temp)
*parent = *temp;
else{
temp = parent;
parent = NULL;
}
free(temp);
}
else{
Node *temp = parent->left;
while(temp->right)
temp = temp->right;
parent->left=removeNode(parent->left,temp->value);
}
return parent;
}
}
void print(Node *parent){
if(parent){
print(parent->left);
printf("%d ",parent->value);
print(parent->right);
}
}
int main(){
root = insertNode(root,20);
root = insertNode(root,5);
root = insertNode(root,14);
root = insertNode(root,3);
root = insertNode(root,16);
root = insertNode(root,22);
root = insertNode(root,19);
root = removeNode(root,3);
//print in order
print(root);
}
*/
Dan untuk tugas membuat aplikasi dengan konsep double linked list terdapat dalam web :
https://linkedlisttugasmingguan.blogspot.com/2020/04/code-example-for-double-linked-list.html
Demikian rangkuman mengenai hal hal apa saja yang saya pelajari sampai saat ini, Terima Kasih.
Code example for Double Linked List
Dreammer's Market
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct List{
char name[50];
int qty;
int price;
List *next,*prev;
}*head,*tail,*curr,*temp;
List *createNode(const char name[], int qty){
List *temp = (List*)malloc(sizeof(List));
strcpy(temp->name,name);
temp->qty = qty;
temp->next = temp->prev = NULL;
return temp;
}
void enter(){
puts("\nPress any key to continue...");
getchar();
}
void cls(){
for(int i=0;i<30;i++)
puts("");
}
void deleteList(char name[]){
if(!head){
puts("Your cart is empty");
return;
}
curr = head;
while(curr){
if(strcmp(curr->name,name)==0)
break;
if(strcmp(curr->name,name)>0){
puts("Not Found");
return;
}
curr = curr->next;
}
if(!curr)
printf("Not Found");
else if(curr == head && !curr->next)
head = NULL;
else if(curr == head){
head->next->prev = NULL;
head = curr->next;
}
else if(curr == tail){
curr->prev->next = NULL;
tail = curr->prev;
}
else{
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
}
free(curr);
}
void edit(char name[], int change){
if(!head){
puts("Your cart is empty");
return;
}
curr = head;
while(curr){
if(strcmp(curr->name,name)==0)
break;
if(strcmp(curr->name,name)>0){
puts("Not Found");
return;
}
curr = curr->next;
}
if(!curr)
printf("Not found");
else
curr->qty = change;
}
bool search(char name[]){
if(!head)
return false;
curr = head;
while(curr){
if(strcmp(curr->name,name)==0)
return true;
if(strcmp(curr->name,name)>0)
return false;
curr = curr->next;
}
return false;
}
void pushPriority(char name[], int qty){
curr = createNode(name,qty);
curr->price = rand() % 89999 + 10000;
if(!head)
head = tail = curr;
else{
temp = head;
while(temp->next){
if(strcmp(temp->next->name,curr->name)>0)
break;
temp = temp->next;
}
if(temp==tail){
temp->next = curr;
curr->prev = temp;
tail = curr;
}
else{
curr->prev = temp;
curr->next = temp->next;
temp->next->prev = curr;
temp->next = curr;
}
}
head->prev = NULL;
tail->next = NULL;
}
void checkOut(){
if(!head){
puts("Your cart is empty");
enter();
return;
}
curr = head;
int count = 0;
int total = 0;
puts("=====================================================================================");
puts("= Dreammers Market Bill's =");
puts("=====================================================================================");
puts("= No = Item Name = Qty = Price = Total =");
puts("=====================================================================================");
while(curr){
printf("= %3d = %-35s = %6d = Rp.%7d = Rp. %11d
=\n",++count,curr->name,curr->qty,curr->price,
curr->qty*curr->price);
total += curr->qty*curr->price;
curr = curr->next;
}
puts("=====================================================================================");
printf("=-----------------------------Discount----------------------------= Rp. %11d =\n", -total);
puts("=====================================================================================");
printf("=------------------------------Total------------------------------= Free =\n");
puts("= ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~Kindness is Free ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ = ^^ =");
puts("=====================================================================================");
enter();
}
void deleteCart(){
char name[50];
int quantity;
char strquantity[50];
do{
printf("Input item name you want to delete>> ");
scanf("%[^\n]", name);getchar();
}while(strlen(name)<1);
curr = head;
while(curr){
if(strcmp(curr->name,name)==0)
break;
curr = curr->next;
}
if(!curr){
puts("Not Found");
enter();
return;
}
char confirm[10];
printf("%-15s: %s\n", "Item Name",curr->name);
printf("%-15s: %d\n", "Quantity",curr->qty);
printf("%-15s: %d\n\n", "Price", curr->price);
puts("Do you still want to delete this item from cart? [Yes|No] case sensitive");
do{
printf(">> ");
scanf("%[^\n]", confirm);getchar();
}while(!(strcmp(confirm,"Yes")==0 || strcmp(confirm,"No")==0));
if(strcmp(confirm,"No")==0)
return;
deleteList(name);
puts("Succesfully deleted");
enter();
}
void editCart(){
char name[50];
int quantity;
char strquantity[50];
do{
printf("Input item name you want to edit>> ");
scanf("%[^\n]", name);getchar();
}while(strlen(name)<1);
curr = head;
while(curr){
if(strcmp(curr->name,name)==0)
break;
curr = curr->next;
}
if(!curr){
puts("Not Found");
enter();
return;
}
bool error;
printf("%-15s: %s\n", "Item Name",curr->name);
printf("%-15s: %d\n", "Quantity",curr->qty);
printf("%-15s: %d\n\n", "Price", curr->price);
do{
error = false;
printf("Edit Quantity [0 to cancel] >> ");
scanf("%[^\n]", strquantity);getchar();
for(int i=0;strquantity[i]!='\0';i++){
if(strquantity[i]>=48 && strquantity[i]<=57)
continue;
else{
error = true;
break;
}
}
}while(error);
if(quantity)
return;
quantity = atoi(strquantity);
edit(curr->name, quantity);
puts("Succesfully Update Your Cart");
enter();
}
void addCart(){
char name[50];
int quantity;
char strquantity[50];
do{
printf("Input item name >> ");
scanf("%[^\n]", name);getchar();
}while(strlen(name)<1);
if(search(name)){
puts("\n\nYour item already exist!");
enter();
return;
}
bool error;
do{
error = false;
printf("Input %s quantity >> ", name);
scanf("%[^\n]", strquantity);getchar();
for(int i=0;strquantity[i]!='\0';i++){
if(strquantity[i]>=48 && strquantity[i]<=57)
continue;
else{
error = true;
break;
}
}
}while(error);
quantity = atoi(strquantity);
// printf("%d", quantity);
pushPriority(name,quantity);
}
void viewCart(){
if(!head){
puts("Your cart is empty");
enter();
return;
}
curr = head;
int count = 0;
puts("===================================================================");
puts("= Cart =");
puts("===================================================================");
puts("= No = Item Name = Qty = Price =");
puts("===================================================================");
while(curr){
printf("= %3d = %-35s = %6d = Rp.%7d =\n",++count,curr->name,curr->qty,curr->price);
curr = curr->next;
}
puts("===================================================================");
enter();
}
void mainMenu(){
int input=0;
do{
cls();
puts("Welcome to Dreammers Market!!");
puts("");
puts("Choose what to do:");
puts("1. View Cart");
puts("2. Add New Item to Cart");
puts("3. Edit Quantity Item on Cart");
puts("4. Delete Item on Cart");
puts("5. CheckOut");
puts("6. Exit");
scanf("%d", &input);getchar();
switch(input){
case 1:
viewCart();
break;
case 2:
addCart();
break;
case 3:
editCart();
break;
case 4:
deleteCart();
break;
case 5:
checkOut();
break;
}
}while(input!=6);
puts("\n\nThank you for coming!!");
}
int main(){
mainMenu();
return 0;
}
AVL TREE
AVL Tree adalah Binary Search Tree yang memiliki perbedaan level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree digunakan untuk menyeimbangkan BST, dengan AVL Tree waktu pencarian dan bentuk tree dipersingkat dan disederhanakan.
Berikut merupakan contoh dari AVL Tree
Angka 0 menandakan tidak memiliki perbedaan level antara subtree kiri dan subtree kanan
Angka 1 menandakan memiliki perbedaan 1 level yaitu berada pada subtree kanan (subtree kiri < subtree kanan)
Angka -1 menandakan memiliki perbedaan 1 level yaitu berada pada subtree kiri(subtree kanan < subtree kiri)
Penambahan node pada AVL tree (Insert)
Untuk
menjaga BST tetap seimbang, setiap dilakukan penyisipan node, dilakukan
pemeriksaan node baru. Jika tidak seimbang, maka akan dilakukan proses
penyeimbangan yaitu Single Rotation dan Double Rotation.
Single Rotation
Single Rotation dilakukan bila kondisi AVL Tree waktu akan ditambahkan, searah left-left / right-right
Double Rotation
Double Rotation dilakukan bila kondisi AVL Tree berlawan arah, left-right atau right-left.
Rotasi pertama
Rotasi kedua
Penambahan node pada AVL tree (Delete)
Tidak
hanya dapat melakukan insert, tetapi ada operasi lainnya bernama
delete, proses delete ini dilakukan sama seperti BST yaitu node yang
dihapus digantikan oleh node terbesar pada subtree kiri atau yang
terkecil pada subtree kanan. Setelah dilakukan penghapusan, dicek
kembali apakah tree sudah seimbang atau belum, jika tidak seimbang, maka
akan dilakukan proses penyeimbangan dengan menggunakan single rotation
atau double rotation.
Delete node 60
Pada node 55 tidak seimbang maka akan dilakukan single rotation
Pada node 50, tree menjadi tidak seimbang, maka dilakukan double rotation
Hasil akhir setelah dilakukan double rotation
Demikian penjelasan saya mengenai AVL Tree.
Heap
Heap adalah sebuah objek array yang divisualisasikan sebagai complete binary tree. Bentuk Heap adalah complete Binary Tree yang mengartikan bahwa semua level diisi kecuali level terakhir.
Jenis Heap :
1. Min Heap
Setiap elemen memiliki nilai yang lebih kecil daripada node childnya. Angka terbesar dalam min heap terdapat pada salah satu node leaf (Node di level terakhir).
2. Max Heap
Kebalikan dari min Heap, setiap elemen memiliki nilai yang lebih besar daripada node childnya. Angka terkecil dalam min heap terdapat pada salah satu node leaf (Node di level terakhir).
3. Min Max Heap
Gabungan dari min dan max heap dimana masing" level akan berganti ganti antara min heap dan maxheap.
Operasi dalam heap (Min dan Max Heap)
INSERT
untuk menambahkan suatu elemen, kita dapat melakukan operasi up-heap(heapify-up) untuk mengembalikan sifat heap dengan syarat:
-
Tambahkan elemen pada level bawah heap.
-
Bandingkan elemen yg baru ditambahkan dengan parentnya, jika mereka berada di urutan yang benar, berhenti.
-
Jika tidak, swap elemen dengan parent dan kembali ke langkah sebelumnya.
Contoh insert pada maxheap :
Menambahkan angka 15 pada (X).
Dikarenakan angka 15 lebih besar dibandingkan parentnya (8) maka tuker angka 15 dengan 8
Menukar 15 dan 8
Disini angka 15 masi melanggar syarat karena lebih besar daripada parentnya maka, tukar angka 15 dengan 11
Menukar angka 15 dengan 11
Jadilah max-heap yang benar.
REMOVE
untuk operasi remove dapat digunakan cara down-heap (heapify-down).
dengan cara mengganti root heap dengan elemen terakhir pada level terakhir. Kemudian cek apakah heapnya sesuai dengan tidak dengan syarat min atau max heap. Jika tidak sesuai, swap dengan salah satu childerennya. (Jika dalam min heap, swap dengann children yg lebih kecil, dan pada maxheap, sebaliknya swap dengan children yg lebih besar). Terus lakukan sampai sesuai dengan syarat
Contoh Remove 4 pada max heap
Valid Tree
Kemudian tree di remove sehingga angka 11 dikeluarkan
Menghapus root kemudian menukar dengan node paling akhir yaitu 4
Angka 4 sudah melanggar syarat dikarenakan lebih kecil dari child, sehingga tukar dengan child yang lebih besar (angka 8)
Jadilah Heap yang sudah lengkap dan sesuai dengan syarat.
Insert (Min-Max Heap)
Jika suatu terjadi penambahan data (insert) maka proses yang dilakukan akan dipengaruhi oleh level data tersebut.
Ketika data baru berada di level min, maka bandingkan dengan parentnya. Jika parent memiliki nilai yang lebih kecil, dan upheapmax dari parentnya. Jika tidak, upheapmin dari posisi new node. Uphead pada minmax heap tidak membandingkan dengan parent, tetapi grandparent (parent dari parent)
Contoh penerapan jika insert pada level max
Angka 1 dimasukan, sehingga 1 merupakan new Node. Angka 1 berada pada level max, maka jika 1<10 swap.
Angka 1 dan 10 di swap.
Kemudian dari posisi 1 di upheapmin, karena 1<2 maka 1 dan 2 di swap.
Min max heap telah terpenuhi
Contoh penerapan pada level min
Angka
85 baru dimasukkan, dan angka 85 berada level min, sehingga bandingkan
dengan parentnya (80). dan 85 > 80 mala swap. Kemudian 85 di
upheapmax, tetapi karena 85<90, maka 85 tetap diposisinya.
Jadilah Min-max heap yang sesuai dengan syarat.
Remove(Min-maxHeap)
Remove pada min max heap ada 2 jenis yaitu remove min dan remove max. Jika min, maka root langsung dihapus, jika delete max, maka angka max dari children root akan dihapus. Jika pada delete min dimulai dari level 1, delete max dimulai dari level 2 dan dicari nilai yang paling besar untuk di remove.
Contoh dari remove min-maxheap, delete min
Angka 1 di remove, tukar dengan 80.
Angka 80 dibandingkan dengan grand childnya, yaitu 4,8,3,2. Dikarenakan angka 2 merupakan angka paling kecil. maka swap.
Kemudian cek angka 80 dengan childnya. karena 10 merupakan yang terkecil, maka swap.
Jadilah minmax heap yang sesuai dengan syarat.
Tries
Tries adalah struktur data yang meiliki bentuk seperti pohon, biasanya menyimpan data berupa string. Tries diambil dari Retrieval, karena Tries dapat menemukan sebuah kata tunggal dengan menggunakan huruf awal.
Demikian penjelasan mengenai Heap dan Tries . Terima kasi ^ ^
Demikian mengenai rangkuman yang saya buat selama 1 semester. Terima Kasih
Tidak ada komentar:
Posting Komentar