SUMMARY UTS
Review summary UTS:
- Linked List
- Stack & Queue
- Hash table and binary tree
- Binary tree
Linked List
Linked list sendiri merupakan seperangkat node yang dialokasikan secara dinamis, disusun sedemikian rupa sehingga setiap node berisi satu nilai dan satu pointer. Pointer selalu menunjuk ke anggota berikutnya dari daftar. Jika penunjuknya adalah NULL, maka itu adalah simpul terakhir dalam daftar. Namun, memahami pointer sangat penting untuk memahami cara kerja daftar yang ditautkan. Pada dasarnya, Linked List berfungsi sebagai array yang dapat tumbuh dan menyusut sesuai kebutuhan, dari titik mana pun dalam array.
Linked list diperlukan alokasi dan pointer memori dinamis, yang memperumit kode dan meningkatkan risiko kebocoran memori dan kesalahan segmen. Linked List memiliki overhead yang lebih besar daripada array, karena item linked list dialokasikan secara dinamis (kurang efisien) dan setiap item dalam daftar juga harus menyimpan pointer tambahan.
Stack & Queue
1. Stack
- Stack adalah linear data structure yang elemennya hanya dapat di insert dan di delete dari satu sisi, yang disebut top.
- Stack sendiri memiliki konsep yang mirip dengan tumpukan piring, dimana jika kita ingin meletakkan piring, maka kita akan meletakan piring di paling atas (insert), serta ketika ingin mencuci piring tersebut, maka piring yang kita ambil adalah piring paling atas juga (delete).
- Prinsip yang dipakai dalam stack adalah LIFO (Last In First Out), artinya elemen yang dimasukkan terakhir adalah yang dikeluarkan pertama.
- Fungsi insert dalam stack dinamakan push operation, sedangkan fungsi delete dalam stack dinamakan pop operation.
2. Queue
- Queue adalah linear data structure yang elemennya hanya dapat di-insert dari satu sisi yang disebut rear dan hanya dapat di delete dari satu sisi juga yang disebut front.
sumber : https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/
- Konse queue mirip dengan konsep orang mengantri, dimana orang baru akan mengantri di urutan paling belakang (insert) dan yang akan dilayani dahulu adalah orang yang paling depan (delete).
- Prinsip yang dipakai dalam queue adalah prinsip FIFO (First In First Out), dimana elemen yang dimasukkan pertama akan dikeluarkan pertama juga.
- Fungsi insert dalam queuedinamakan enqueue operation, sedangkan fungsi delete dalam stack dinamakan dequeue operation.
sumber : https://www.hackerearth.com/practice/notes/stacks-and-queues/
- Kelemahan queue adalah ketika pointer left sudah mencapai elemen maximal, maka elemen sebelumnya yang di delete akan kosong (left to right). Sehingga diperlukan Circular Queue, dimana ketika pointer right/rear telah mencapai MAX, maka pointer right akan berlaku sebagai index 0 kembali, Sehingga menghasilkan bentuk siklus/circular.
- Pengaplikasian queue antara lain pada:
- Deques
- Priority Queues
- Breadth-First-Search (BFS)
<<Perbedaan Antara Stack dan Queue>>
sumber : https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/
NOTASI INFIX, POSTFIX, DAN PREFIX
Terdapat dua istilah dalam infix, postfix, prefix, yaitu:
- Operator : tanda operasi (contoh : '+' , '-' , '*' , dll)
- Operand : sebuah objek yang ada pada operasi matematika (contoh : 2 + 5, maka operand nya adalah 2 dan 5)
Infix : operator ditulis di antara operand ( misal : (2 * 5) + 10 ) --> operand, operator, operand
Prefix : operator ditulis sebelum operand ( misal : + * 2 5 10 ) --> operator, operand, operand
Postfix : operator ditulis setelah operand ( misal : 2 5 * 10 + ) --> operand, operand, operator
Kenapa perlu menggunakan notasi prefix/postfix?
- Tidak perlu menggunakan tanda kurung untuk menentukan precedence, sehingga mempermudah komputer dalam mengoperasikan operasi hitung, yang artinya mempercepat dan menghemat alokasi memori komputer.
Catatan :
- Hal penting dalam membuat notasi prefix/postfix adalah memahami urutan prioritas (precedence) dari operasi hitung, dan apabila terdapat precedence yang sama dalam satu operasi hitung, maka menggunakan associative (left to right atau right to left --> tergantung dari operasi yang digunakan).
Contoh :
Infix : ( (1 + 3) / (100 * 5) ^ 30 )
Prefix : / + 1 3 ^ * 100 5 30
Postfix : 1 3 + 100 5 * 30 ^ /
Contoh penerapan stack dalam konversi infix to prefix / infix to postfix :
- Infix to Prefix
- Infix to Postfix
Hash Table
Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan.
Operasi pada Hash Table:
- insert
- find
- remove
- getiterator
Metode untuk membangun Hash function:
- Mid-Square
- Division
- Folding
- Digit Extraction
- Rotating Hash
Binary Tree
Binary Tree is a data structure in a form of a tree with only 2 branches/children. Since there are only 2 of them, they are typically called the left child and the right child depending on where the child is to its parent. The end of a branch in a binary tree is called a leaf A binary tree node only contains 3 parts: Data, a pointer to left child, and a pointer to right child.
1. Full Binary Tree
A binary tree is called full only if all of its nodes have either 0 or 2 children. Binary trees with only 1 node or a node with only 1 child can not be called a full binary tree.
2. Complete Binary Tree
A binary tree is completed only if all levels, with exception to the last possible, has its nodes completely filled. If the last level is not completely filled, the elements should be as left as possible.
3. Perfect Binary Tree
A perfect binary tree is one in which all nodes have 2 children and all leaves are at the same level.
4. Degenerate/Pathological Binary Tree
A tree where each parent node only has 1 child. Identical in behavior to a linked list.
Tugas koding membuat aplikasi
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node{
char barang[51];
int qty;
int value;
struct node *next,*prev;
}*head = NULL , *tail = NULL , *curr;
void push(const char *s , int x)
{
curr = (struct node*)malloc(sizeof(struct node));
strcpy(curr->barang,s);
curr->qty = x;
curr->value = rand()%11;
curr->next = curr->prev = NULL;
if(head == NULL)
{
head = tail = curr;
}
else if(x < head->qty || strcmp(s,head->barang) < 0)
{
curr->next = head;
head->prev = curr;
head = curr;
}
else if(x > tail->qty || strcmp(s,tail->barang) > 0)
{
tail->next = curr;
curr->prev = tail;
tail = curr;
}
else
{
struct node *temp = head;
while(temp->next->qty < x)
{
temp = temp->next;
}
curr->next = temp->next;
temp->next->prev = curr;
temp->next = curr;
curr->prev = temp;
}
}
void pop(const char *s)
{
if(head == NULL)
{
puts("Pop failed! No Data found!");
}
else if(head == tail)
{
free(head);
head = tail = NULL;
}
else if(strcmp(head->barang,s) == 0)
{
curr = head;
head = head->next;
free(curr);
head->prev = NULL;
}
else if(strcmp(tail->barang,s) == 0)
{
curr = tail;
tail = tail->prev;
free(curr);
tail->next =NULL;
}
else
{
curr = head;
while(curr != NULL && strcmp(curr->barang,s) != 0)
{
curr = curr->next;
}
if(curr == NULL)
{
printf("No item found!\n");
}
else
{
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
free(curr);
printf("Remove successful!\n");
getchar();
}
}
}
void Edit(const char *s , int editqty)
{
struct node *temp = head;
while(temp != NULL && strcmp(temp->barang,s)!=0)
{
temp = temp->next;
}
if(temp != NULL)
{
temp->qty = editqty;
}
}
void popall()
{
while(head != NULL)
{
struct node *temp = head;
head = head->next;
free(temp);
}
}
void cetak()
{
int index = 1;
curr = head;
while(curr != NULL)
{
printf("%d. %s %d\n",index,curr->barang,curr->qty);
curr = curr->next;
index = index + 1;
}
printf("\n");
}
void checkout()
{
int i=1;
int x = 0;
cetak();
curr = head;
while(curr != NULL)
{
printf("%d. %s %d x %d = %d\n",i,curr->barang,curr->qty,curr->value,curr->qty*curr->value);
x += curr->qty * curr->value;
curr = curr->next;
i++;
}
printf("Total : %d\n",x);
printf("Kindness is free\n");
popall();
}
int main()
{
char wishlist[51];
int wishprioriry;
char hapus[51];
char ubah[51];
int editqty;
int pilih = 0;
do{
printf("1. Tambahkan barang\n");
printf("2. Ubah barang\n");
printf("3. Hapus barang\n");
printf("4. Periksa\n");
printf("5. Keluar\n");
printf("Silakan pilih : ");
scanf("%d",&pilih);
switch (choose) {
case 1:
printf("Masukkan nama benda [1-100] : ");
getchar();
scanf("%[^\n]",wishlist);
printf("Input qty [1-10] : ");
scanf("%d",&wishprioriry);
printf("\n");
push(wishlist,wishprioriry);
getchar();
break;
case 2:
if(head == NULL)
{
printf("Daftar benda kosong!\n\n");
}
else
{
printf("Masukkan benda yang ingin diubah : ");
getchar();
scanf("%[^\n]",ubah);
printf("masukkan qty yang ingin diubah : ");
scanf("%d",&ubahqty);
printf("\n");
Ubah(ubah,ubahqty);
getchar();
}
break;
case 3:
if(head == NULL)
{
printf("Daftar benda kosong!\n\n");
}
else{
printf("Masukkan nama benda [1-100] : ");
getchar();
scanf("%[^\n]",hapus);
struct node *temp = head;
while(temp!= NULL && strcmp(temp->barang,hapus) != 0)
{
temp = temp->next;
}
if(temp == NULL)
{
printf("Barang tidak ditemukan!\n\n");
}
else
{
pop(hapus);
printf("Berhasil dihapus!\n\n");
}
}
break;
case 4:
checkout();
break;
case 5:
popall();
break;
default:
break;
}
}while(pilih != 5 && pilih != 4);
}
Linked list sendiri merupakan seperangkat node yang dialokasikan secara dinamis, disusun sedemikian rupa sehingga setiap node berisi satu nilai dan satu pointer. Pointer selalu menunjuk ke anggota berikutnya dari daftar. Jika penunjuknya adalah NULL, maka itu adalah simpul terakhir dalam daftar. Namun, memahami pointer sangat penting untuk memahami cara kerja daftar yang ditautkan. Pada dasarnya, Linked List berfungsi sebagai array yang dapat tumbuh dan menyusut sesuai kebutuhan, dari titik mana pun dalam array.
Linked list diperlukan alokasi dan pointer memori dinamis, yang memperumit kode dan meningkatkan risiko kebocoran memori dan kesalahan segmen. Linked List memiliki overhead yang lebih besar daripada array, karena item linked list dialokasikan secara dinamis (kurang efisien) dan setiap item dalam daftar juga harus menyimpan pointer tambahan.
Stack & Queue
1. Stack
- Stack adalah linear data structure yang elemennya hanya dapat di insert dan di delete dari satu sisi, yang disebut top.
- Stack sendiri memiliki konsep yang mirip dengan tumpukan piring, dimana jika kita ingin meletakkan piring, maka kita akan meletakan piring di paling atas (insert), serta ketika ingin mencuci piring tersebut, maka piring yang kita ambil adalah piring paling atas juga (delete).
- Prinsip yang dipakai dalam stack adalah LIFO (Last In First Out), artinya elemen yang dimasukkan terakhir adalah yang dikeluarkan pertama.
- Fungsi insert dalam stack dinamakan push operation, sedangkan fungsi delete dalam stack dinamakan pop operation.
2. Queue
- Queue adalah linear data structure yang elemennya hanya dapat di-insert dari satu sisi yang disebut rear dan hanya dapat di delete dari satu sisi juga yang disebut front.
 |
| sumber : https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/ |
- Konse queue mirip dengan konsep orang mengantri, dimana orang baru akan mengantri di urutan paling belakang (insert) dan yang akan dilayani dahulu adalah orang yang paling depan (delete).
- Prinsip yang dipakai dalam queue adalah prinsip FIFO (First In First Out), dimana elemen yang dimasukkan pertama akan dikeluarkan pertama juga.
- Fungsi insert dalam queuedinamakan enqueue operation, sedangkan fungsi delete dalam stack dinamakan dequeue operation.
 |
| sumber : https://www.hackerearth.com/practice/notes/stacks-and-queues/ |
- Kelemahan queue adalah ketika pointer left sudah mencapai elemen maximal, maka elemen sebelumnya yang di delete akan kosong (left to right). Sehingga diperlukan Circular Queue, dimana ketika pointer right/rear telah mencapai MAX, maka pointer right akan berlaku sebagai index 0 kembali, Sehingga menghasilkan bentuk siklus/circular.
- Pengaplikasian queue antara lain pada:
- Deques
- Priority Queues
- Breadth-First-Search (BFS)
<<Perbedaan Antara Stack dan Queue>>
 |
| sumber : https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/ |
NOTASI INFIX, POSTFIX, DAN PREFIX
Terdapat dua istilah dalam infix, postfix, prefix, yaitu:
- Operator : tanda operasi (contoh : '+' , '-' , '*' , dll)
- Operand : sebuah objek yang ada pada operasi matematika (contoh : 2 + 5, maka operand nya adalah 2 dan 5)
Infix : operator ditulis di antara operand ( misal : (2 * 5) + 10 ) --> operand, operator, operand
Prefix : operator ditulis sebelum operand ( misal : + * 2 5 10 ) --> operator, operand, operand
Postfix : operator ditulis setelah operand ( misal : 2 5 * 10 + ) --> operand, operand, operator
Kenapa perlu menggunakan notasi prefix/postfix?
- Tidak perlu menggunakan tanda kurung untuk menentukan precedence, sehingga mempermudah komputer dalam mengoperasikan operasi hitung, yang artinya mempercepat dan menghemat alokasi memori komputer.
Catatan :
- Hal penting dalam membuat notasi prefix/postfix adalah memahami urutan prioritas (precedence) dari operasi hitung, dan apabila terdapat precedence yang sama dalam satu operasi hitung, maka menggunakan associative (left to right atau right to left --> tergantung dari operasi yang digunakan).
Contoh :
Infix : ( (1 + 3) / (100 * 5) ^ 30 )
Prefix : / + 1 3 ^ * 100 5 30
Postfix : 1 3 + 100 5 * 30 ^ /
Contoh penerapan stack dalam konversi infix to prefix / infix to postfix :
Contoh penerapan stack dalam konversi infix to prefix / infix to postfix :
- Infix to Prefix
- Infix to Postfix
Hash Table
Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan.
Operasi pada Hash Table:
- insert
- find
- remove
- getiterator
Metode untuk membangun Hash function:
- Mid-Square
- Division
- Folding
- Digit Extraction
- Rotating Hash
Binary Tree
Binary Tree is a data structure in a form of a tree with only 2 branches/children. Since there are only 2 of them, they are typically called the left child and the right child depending on where the child is to its parent. The end of a branch in a binary tree is called a leaf A binary tree node only contains 3 parts: Data, a pointer to left child, and a pointer to right child.
Common example of binary trees include:
1. Full Binary Tree
A binary tree is called full only if all of its nodes have either 0 or 2 children. Binary trees with only 1 node or a node with only 1 child can not be called a full binary tree.
2. Complete Binary Tree
A binary tree is completed only if all levels, with exception to the last possible, has its nodes completely filled. If the last level is not completely filled, the elements should be as left as possible.
3. Perfect Binary Tree
A perfect binary tree is one in which all nodes have 2 children and all leaves are at the same level.
4. Degenerate/Pathological Binary Tree
A tree where each parent node only has 1 child. Identical in behavior to a linked list.
Tugas koding membuat aplikasi
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node{
char barang[51];
int qty;
int value;
struct node *next,*prev;
}*head = NULL , *tail = NULL , *curr;
void push(const char *s , int x)
{
curr = (struct node*)malloc(sizeof(struct node));
strcpy(curr->barang,s);
curr->qty = x;
curr->value = rand()%11;
curr->next = curr->prev = NULL;
if(head == NULL)
{
head = tail = curr;
}
else if(x < head->qty || strcmp(s,head->barang) < 0)
{
curr->next = head;
head->prev = curr;
head = curr;
}
else if(x > tail->qty || strcmp(s,tail->barang) > 0)
{
tail->next = curr;
curr->prev = tail;
tail = curr;
}
else
{
struct node *temp = head;
while(temp->next->qty < x)
{
temp = temp->next;
}
curr->next = temp->next;
temp->next->prev = curr;
temp->next = curr;
curr->prev = temp;
}
}
void pop(const char *s)
{
if(head == NULL)
{
puts("Pop failed! No Data found!");
}
else if(head == tail)
{
free(head);
head = tail = NULL;
}
else if(strcmp(head->barang,s) == 0)
{
curr = head;
head = head->next;
free(curr);
head->prev = NULL;
}
else if(strcmp(tail->barang,s) == 0)
{
curr = tail;
tail = tail->prev;
free(curr);
tail->next =NULL;
}
else
{
curr = head;
while(curr != NULL && strcmp(curr->barang,s) != 0)
{
curr = curr->next;
}
if(curr == NULL)
{
printf("No item found!\n");
}
else
{
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
free(curr);
printf("Remove successful!\n");
getchar();
}
}
}
void Edit(const char *s , int editqty)
{
struct node *temp = head;
while(temp != NULL && strcmp(temp->barang,s)!=0)
{
temp = temp->next;
}
if(temp != NULL)
{
temp->qty = editqty;
}
}
void popall()
{
while(head != NULL)
{
struct node *temp = head;
head = head->next;
free(temp);
}
}
void cetak()
{
int index = 1;
curr = head;
while(curr != NULL)
{
printf("%d. %s %d\n",index,curr->barang,curr->qty);
curr = curr->next;
index = index + 1;
}
printf("\n");
}
void checkout()
{
int i=1;
int x = 0;
cetak();
curr = head;
while(curr != NULL)
{
printf("%d. %s %d x %d = %d\n",i,curr->barang,curr->qty,curr->value,curr->qty*curr->value);
x += curr->qty * curr->value;
curr = curr->next;
i++;
}
printf("Total : %d\n",x);
printf("Kindness is free\n");
popall();
}
int main()
{
char wishlist[51];
int wishprioriry;
char hapus[51];
char ubah[51];
int editqty;
int pilih = 0;
do{
printf("1. Tambahkan barang\n");
printf("2. Ubah barang\n");
printf("3. Hapus barang\n");
printf("4. Periksa\n");
printf("5. Keluar\n");
printf("Silakan pilih : ");
scanf("%d",&pilih);
switch (choose) {
case 1:
printf("Masukkan nama benda [1-100] : ");
getchar();
scanf("%[^\n]",wishlist);
printf("Input qty [1-10] : ");
scanf("%d",&wishprioriry);
printf("\n");
push(wishlist,wishprioriry);
getchar();
break;
case 2:
if(head == NULL)
{
printf("Daftar benda kosong!\n\n");
}
else
{
printf("Masukkan benda yang ingin diubah : ");
getchar();
scanf("%[^\n]",ubah);
printf("masukkan qty yang ingin diubah : ");
scanf("%d",&ubahqty);
printf("\n");
Ubah(ubah,ubahqty);
getchar();
}
break;
case 3:
if(head == NULL)
{
printf("Daftar benda kosong!\n\n");
}
else{
printf("Masukkan nama benda [1-100] : ");
getchar();
scanf("%[^\n]",hapus);
struct node *temp = head;
while(temp!= NULL && strcmp(temp->barang,hapus) != 0)
{
temp = temp->next;
}
if(temp == NULL)
{
printf("Barang tidak ditemukan!\n\n");
}
else
{
pop(hapus);
printf("Berhasil dihapus!\n\n");
}
}
break;
case 4:
checkout();
break;
case 5:
popall();
break;
default:
break;
}
}while(pilih != 5 && pilih != 4);
}
Comments
Post a Comment