Rangkuman
1. Linked List
Linked List ada 4 jenis :1. Single Linked List
2. Double Linked List
3. Circular Single Linked List
4. Circular Double Linked List
1. Single Linked List
adalah sekumpulan node yang terhubung melalui pointer. Single linked list hanya memiliki pointer yang menunjuk ke node selanjutnya tapi tidak ad pointer yang menunjuk ke node sebelumnya
2. Double Linked List
adalah sekumpulan node yang terhubung melalui pointer tetapi terdapat 2 arah yaitu 1 pointer menunjuk ke node selanjutnya dan satu lagi menunjuk ke node sebelumnya. Jadi kita bisa mengakses kembali node yang sebelum node sekarang.
3. Circular Single Linked List
adalah sekumpulan node yang terhubung melalui pointer tetapi pointer node terakhir menunjuk ke node pertama.
4. Circular Double Linked List
adalah sekumpulan node yang terhubung melalui pointer tetapi pointer node terakhir menunjuk ke node pertama dan node pertama juga bisa ke node terakhir.
Beda Linked List dan Array adalah:
- alamat memori Array berurutan, sedangkan Linked List tidak
- Linked List dinamis, bisa berapapun datanya, sedangkan Array statis , hanya bisa diisi data sesuai dengan ukuran array yang sudah diinisialisasi sebelumnya
Insert dalam Linked list ada 3 macam :
1. Push Head ( memasukkan data di depan / head ) FILO
2. Push Tail ( memasukkan data di belakang / tail ) FIFO
3. Push Mid ( memasukkan data di tengah-tengah dengan kondisi tertentu )
Stack & Queue
Dalam memasukkan data baru pada linked list terdapat 2 cara :
1. Stack
yaitu data yang terakhir kita masukkin, itu yang bakal jadi yang pertama(LIFO Last In First Out)
atau biasa di linked list di sebut PushHead
2.Queue
yaitu data yang terakhir kita masukkin, itu yang bakal jadi yang terakhir juga (FIFO First In First Out) atau biasa di linked list di sebut PushTail
Untuk detail yang lebih jelas bisa diklik aja link berikut :
https://www.geeksforgeeks.org/data-structures/linked-list/singly-linked-list/
1. Stack
yaitu data yang terakhir kita masukkin, itu yang bakal jadi yang pertama(LIFO Last In First Out)
atau biasa di linked list di sebut PushHead
2.Queue
yaitu data yang terakhir kita masukkin, itu yang bakal jadi yang terakhir juga (FIFO First In First Out) atau biasa di linked list di sebut PushTail
Untuk detail yang lebih jelas bisa diklik aja link berikut :
https://www.geeksforgeeks.org/data-structures/linked-list/singly-linked-list/
Hash table
Hash table adalah cara dalam memproses data biasanya dilakukan dengan mengenerate key terlebih dahulu lalu key tersebut dijadikan sebagai index yang nanti data tersebut akan dimasukkan ke array dengan index sesuai yang kia dapat tadi.Tapi karena ada kemungkinan kalo misalnya setelah kita generate index, kita mendapat kan index yang sudah pernah kita pakai sebelumnya, maka akan terjadi tubrukan data, sehingga jika kita tetap masukkan data baru ke index tersebut, data sebelumnya yang ada pada index yang sama akan teroverwrite, sehingga akan hilang.
Jadi untuk mengatasi hal tersebut terjadi, ada namanya linear probing dan chaining :
1. Linear probing
Cara ini dilakukan pada saat menemukan index yang sama, kita mencari index setelahnya yang masih belum terpakai(kosong), dengan looping, kita tambah-tambah index nya dengan 1 sambil mengecek apakah isi dari array pada index tersebut sudah terisi apa kosong, jika kosong maka masukkan data ke index tersebut, kalao udah terisi maka lanjut looping dan tambah-tambah 1 lagi hingga menemukan yang kosong.
2.Chaining
Cara ini dilakukan pada saat menemukan index yang sama setelah itu menjadikan setiap array dalam hash table menjadi dynamic array, sehingga data yang pertama masuk menjadi headnya setelah itu jika ada data yang masuk lagi akan menjadi nextnya, dan seterusnya tanpa ada batas
Binary Tree
Binary Tree adalah sebuah tipe struktur data yang bentuknya mrip pohon, berbeda dengan linked list mnggunakan head sebagai acuan, binary tree ini menggunakan root sebagai acuannya, dan ada left dan right, biasa nya left adalah data dengan value yang lebih kecil dari rootnya, sedangkan yang right memiliki value yang lebih besar dari rootnya, sehingga nanti ini akan sangat membantu dalam pencarian data, dan sorting data.
Binary Search Tree
Binary Search Tree atau biasa disingkat BST adalah sebuah data struktur yang berbentuk atau diilustrasikan merupai sebuah pohon,sesuai namanya Binary Search Tree. Prinsip dari Binary Search Tree ini, adalah ketika data baru yang masuk , dicek dlu apakah dia lebih kecil atau lebih besar dari root nya atau akarnya(sebagai acuan) jikalau lebih kecil akan di masukkanke bagian kiri rootnya , jika lebih besar akan dimasukkan sebelah kanan rootnya, dan seterusnya tanpa batas. Jadi kita bisa menambahkan data sebanyak apa pun tanpa batas, karena setiap data itu dihubungkan dengan pointer sama seperti Array dinamis. Dan juga setiap cabang hanya boleh memiliki 2 anak , 1 dikiri yang lebih kecil dari root atau bapaknya, 1 lagi yang dikanan lebih besar dari root atau bapaknya.
contoh binary search tree :
contoh binary search tree :
Keuntungan kita memakai binary search tree untuk menyusun data kita adalah, ketika kita mau mencari data , algoritmanya yaitu jika kita mau mencari sebuah angka x, kita cek dulu si x ini apakah lebih besar dari root atau tidak, jika lebih besar maka dia cek lg kekanan , jika lebih kecil maka cek ke kiri lagi , jika uda sama dengan brarti uda dapat xnya , dan seterusnya dicari sampai datanya habis atau data nya ditemukan.
Jadi dengan binary search tree kita bisa mempercepat pencarian karena kita tidak cek 1 1 lagi melainkan mengeliminasi bebrapa proses yang menyebabkan pencarian jadi lama.
selain untuk mencari data, secara tidak langsung jika kita memakai binary search tree, kita sudah mensort data2 kita.
sekian,terima kasih.
berikut saya sertakan codingan bst saya :
#include <stdio.h>
#include <stdlib.h>
struct node{
int umur;
struct node *left;
struct node *right;
};
struct node* createNode(int umur){
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->umur = umur;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct node* insertion(struct node* root,int umur){
struct node* temp = createNode(umur);
if(root == NULL) root = temp;
else if(umur > root->umur) root->right = insertion(root->right, umur);
else if(umur < root->umur) root->left = insertion(root->left, umur);
return root;
}
struct node* cariMin(struct node* root){
while(root->left != NULL){
root = root->left;
}
return root;
}
struct node* Deletion(struct node* root,int umur){
if(root == NULL){
printf("G ada data jadi g bs hapus\n");
return NULL;
}
else if(umur > root->umur) root->right = Deletion(root->right, umur);
else if(umur < root->umur) root->left = Deletion(root->left, umur);
else{
//ketemu sama apa yang mau didelete
//case 1 : G pnya anak
if(root->left == NULL && root->right == NULL){
free(root);
root = NULL;
}
//Case 2 : 1 anak
else if(root->left == NULL){
struct node* temp = root;
root = root->right;
free(temp);
}
else if(root->right == NULL){
struct node* temp = root;
root = root->left;
free(temp);
}
//case 3 : 2 anak
else{
struct node* temp = cariMin(root->right);
root->umur = temp->umur;
root->right = Deletion(root->right, temp->umur);
}
}
return root;
}
void printAll(struct node* root){
if(root == NULL) return;
// //preorder
// printf("%d\n",root->umur);
printAll(root->left);
//in order
printf("%d\n",root->umur);
printAll(root->right);
// //postorder
// printf("%d\n",root->umur);
}
int main(int argc, const char * argv[]) {
struct node* root = NULL;
root = insertion(root, 15);
root = insertion(root, 13);
root = insertion(root, 20);
root = insertion(root, 12);
root = insertion(root, 14);
root = insertion(root, 18);
root = insertion(root, 22);
printAll(root);
puts("");
root = Deletion(root, 15);
printAll(root);
return 0;
}
Berikut adalah codingan dreammers market untuk tugas forum :
//
// main.cpp
// GSLC
//
// Created by Andrew Tanjaya on 06/04/20.
// Copyright © 2020 Andrew Tanjaya. All rights reserved.
//
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
struct barang{
char nama[100];
int qty;
struct barang* next;
struct barang* prev;
}*head = NULL,*tail = NULL;
struct barang* newBarang(char nama[],int qty){
struct barang* newData = (struct barang*)malloc(sizeof(struct barang));
strcpy(newData->nama,nama);
newData->qty = qty;
newData->next = NULL;
newData->prev = NULL;
return newData;
}
void popHead(){
if(head == NULL) ;
else if(head == tail) head = tail = NULL;
else {
struct barang *temp = head;
head = head->next;
head->prev->next = NULL;
head->prev = NULL;
free(temp);
temp = NULL;
}
}
void popMid(char nama[]){
if(head == NULL) printf("nothing to delete\n");
else if(strcmp(head->nama, nama) == 0 && head == tail) head = tail = NULL;
else if(strcmp(head->nama, nama) == 0){
struct barang *temp = head;
head = head->next;
head->prev->next = NULL;
head->prev = NULL;
free(temp);
temp = NULL;
}
else if(strcmp(tail->nama, nama) == 0) {
struct barang *temp = tail;
tail = tail->prev;
tail->next->prev = NULL;
tail->next = NULL;
free(temp);
temp = NULL;
}
else{
struct barang* curr = head;
while(curr != NULL && strcmp(curr->nama, nama) != 0){
curr = curr->next;
}
//data habis dan g ada yang bisa dihapus
if(curr == NULL){
printf("%s tidak ada dalam data\n",nama);
}
else if(strcmp(curr->nama, nama) == 0){
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
curr->prev = NULL;
curr->next = NULL;
free(curr);
curr = NULL;
printf("Successfully deleted\n");
}
}
}
void pushMid(char nama[],int qty){
struct barang *temp = newBarang(nama,qty);
if(head == NULL) head = tail = temp;
else if(strcmp(head->nama,nama) > 0){
head->prev = temp;
temp->next = head;
head = temp;
}
else if(strcmp(tail->nama,nama) < 0){
tail->next = temp;
temp->prev = tail;
tail = temp;
}
else{
struct barang *curr = head;
while(curr && strcmp(curr->nama,nama) < 0){
curr = curr->next;
}
curr->prev->next = temp;
temp->prev = curr->prev;
temp->next = curr;
curr->prev = temp;
}
}
void changeQty(char nama[],int qty){
struct barang *curr = head;
int i=1;
while(curr){
if(strcmp(curr->nama, nama) == 0) {
curr->qty = qty;
}
curr = curr->next;
i++;
}
}
int cekAll(char nama[]){
struct barang *curr = head;
int i=1;
while(curr){
if(strcmp(curr->nama, nama) == 0) return 1;
curr = curr->next;
i++;
}
return 0;
}
int getPrice(){
srand(time(NULL));
int price = rand()%100000+1;
return price;
}
void printAll(){
struct barang *curr = head;
int i=1;
if(head == NULL) {
printf("No data\n");
return;
}
while(curr){
printf("%d %s %d\n",i,curr->nama,curr->qty);
curr = curr->next;
i++;
}
}
void printAllStruk(){
struct barang *curr = head;
int i=1;
char choice[100];
if(head == NULL) {
printf("No items to buy...\n");
return;
}
int total =0;
printf("NO NamaBarang Quantity @ Price\n");
while(curr){
int price = getPrice();
printf("%2d %10s %10d Rp.%10d Rp.%10d\n",i,curr->nama,curr->qty,price,price*curr->qty);
total += (price*curr->qty);
curr = curr->next;
i++;
}
printf("total = Rp.%d\n",total);
do{
printf("Do you still want to pay ? [Y/N]");
scanf("%[^\n]",choice);
getchar();
}while(strcmp(choice,"Y")!=0 && strcmp(choice,"N")!=0);
if(strcmp(choice, "Y") == 0){
printf("Kindness is free\n");
printf("You have your full carts for free\n");
while(head){
popHead();
}
}
}
int main(int argc, const char * argv[]) {
int choice;
char nama[1000];
int qty;
do{
printf("Dreamers Market\n");
printf("1. Buy Items\n");
printf("2. Edit Items Qty\n");
printf("3. Delete Items\n");
printf("4. View Items\n");
printf("5. Pay\n");
printf("6. Exit\n");
scanf("%d",&choice);
getchar();
switch (choice) {
case 1:
do{
printf("Input nama produk :");
scanf("%[^\n]",nama);
getchar();
}while(cekAll(nama) == 1);
printf("Input product quantity :");
scanf("%d",&qty);
getchar();
pushMid(nama, qty);
break;
case 2:
do{
printf("Input nama produk yang mau di edit qty nya :");
scanf("%[^\n]",nama);
getchar();
}while(cekAll(nama) == 0);
printf("Input qty : ");
scanf("%d",&qty);
getchar();
changeQty(nama, qty);
break;
case 3:
printf("Input nama produk yang mau di hapus :");
scanf("%[^\n]",nama);
getchar();
popMid(nama);
break;
case 4:
printAll();
break;
case 5:
printAllStruk();
break;
case 6:
break;
}
}while(choice >= 1 && choice < 6);
return 0;
}
No comments:
Post a Comment