Rangkuman Sebelum UTS
Linked List
Linked List adalah suatu struktur data yang terdiri dari urutan record data dimana setiap record data terdiri dari field dimana salah satunya menyimpan alamat dari record data selanjutnya.
Single Linked List
didalam single linked list setiap node terdiri dari 2 field. 1 field merupakan value dan satunya lagi adalah link ke node selanjutnya. Di dalam single linked list, satu node hanya memiliki 1 link saja(hanya searah).
Doubly Linked List
Doubly linked list adalah jenis linked list dimana setiap nodenya memiliki 3 field. Dalam doubly linked list terdapat satu tambahan pointer yang dinamakan previous yang bersamaan dengan next dan data yang single linked.
 |
| https://miro.medium.com/max/4000/1*Rkn3q6HJoEkRO4T_SVlyuw.png |
Circular Single Linked List
Circular Single Linked List ini kurang lebih mirip dengan single linked list hanya jika di single linked list node terakhir atau tail memiliki pointer yang NULL dan pada Circular Single Linked List ini node terakir atau tail akan memiliki pointer yang mengarah ke head.
 |
| https://media.geeksforgeeks.org/wp-content/uploads/CircularSinglyLinkedList.png |
Circular Doubly Linked List
Pada prinsipnya cara kerja Circular Doubly Linked list mirip dengan Circular Doubly Linked List namun bedanya Circular Doubly Linked List memiliki 2 buah link yang satu terkoneksi dengan previous dan yang satu terkoneksi dengan next node.
 |
| https://media.geeksforgeeks.org/wp-content/uploads/Circular-doubly-linked-list.png |
Kunjungi: https://datstruct17.blogspot.com/2020/03/linked-list.html
Linked List VS Array
Ketika kita menggunakan array hal yang dilakukan adalah komputer akan memblok memori ketika compile sementara linked list dialokasikan selama runtime. Operasi seperti insertion dan deletion dalam array jauh lebih sulit dibandingkan di dalam linked list. Perbedaan selanjutnya yang membedakan linked list dengan array adalah dengan array ketika kita memesan sebanyak 10 blok memori maka memori yang diblok sejumlah 10 dengan saling bersebelahan. Sedangkan tidak dengan linked list yang penempatannya random tidak harus bersebelahan.
Stack
Dalam Linked stack, setiap node punya 2 field yang satu untuk menyimpan data dan yang lainnya berfungsi untuk menyimpan alamat dari node selanjutnya. TOP(peek) dari linked list stack adalah pointer headnya. Semua operasi yang dilakukan seperti deletion dan insertions dilakukan dari TOP. jika TOP bernilai NULL maka bisa disimpulkan bahwa stack kosong.
 |
| https://i1.faceprep.in/Companies-1/stack%20data%20structure%20in%20c.png |
Operasi Stack
push(x) adalah operasi untuk menambahkan data ke TOP(peek) stack. pop adalah operasi stack untuk menghilangkan data atau mendelete data dari TOP(peek) stack. Dan top untuk memunculkan data teratas dari stack.
Infix, Postfix, dan Prefix Notation
Infix: Operator berada di antara operand. *operator: +-*/^
Postfix: Operator berada setelah operand.
Prefix: Operator berada di sebelum operand.
contoh:
infix: ((1+3)/(100*5)^30)
Postfix: 13+1005*30^/
Prefix: /+13^*100530
Depth First Search (DFS)
DFS adalah suatu algoritma dimana berguna untuk mencari jalan di dalam tree atau graph. Jika merupakan pohon dimulai dari rootnya.
Queue
Dalam Linked queue, setiap node punya 2 field yang satu untuk menyimpan data dan yang lainnya berfungsi untuk menyimpan alamat dari node selanjutnya. Insertion selalu dilakukan di rear dan deletion dilakukan di front. jika front dan rear bernilai NULL maka queue tersebut kosong.
 |
| https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjS3p6uTo4pES1laqMQ6w4bwEEwbM1S7HV2BGIhetyci7jgKiMVYlNdwp7KjiBICqN413dNjQS9qOKa0dFKFOIaE7zEoYiY-uuptEZNPjXoNovIpJ5KLlIdISGCBW1rQ-NbhMLRhSgkFZpe/h90/linked-list-implementation-of-queue.png |
Operasi queue
push(x) untuk menambahkan elemen x ke-rear. pop() adalah operasi untuk menghilankan elemen dari front. front untuk memunculkan item paling depan dari queue.
Kunjungi: https://datstruct17.blogspot.com/2020/03/stack-queue.html
Kunjungi: https://datstruct17.blogspot.com/2020/03/stack-queue.html
Circular queue
ketika queue sudah penuh dan mencegah data baru berada di luar range maka bisa diatasi dengan circular queue. Ketika index kiri sudah mencapai maksimal index di set kembali ke 0. Demikian juga dengan index kanan.
 |
| https://www.tutorialride.com/images/data-structures/circular-queue2.jpeg |
Priority queue
Jika terdapat dua elemen yang memiliki tingkat priority yang sama makan akan diberlakukan prinsip First In First Served (FIFS). Deletion dengan menghapus node pertama dan data dari node tersebut diproses terlebih dahulu.
Kunjungi: https://datstruct17.blogspot.com/2020/03/stack-queue.html
Kunjungi: https://datstruct17.blogspot.com/2020/03/stack-queue.html
Hash
Hash dengan fungsi yang berbeda akan menghasilkan output dengan ukuran yang berbeda dari input. Tetapi setiap algoritma hashing kemungkinan akan memiliki output dengan ukuran yang konstan. Nilai yang di return oleh fungsi hash disebut nilai hash, kode hash, jumlah hash, atau hanya hash.
Fungsi kriptografi HASH
Agar fungsi kriptografi berjalan denga baik terdapat 3 syarat yang harus dipenuhi:
• Collision resistance
• Fast Computing
• Preimage resistance
Trees
Trees mengambarkan hubungan one to many antar elemen. Tiap-tiap node yang terdapat pada tree tidak perlu disimpan secara bersebelahan atau berdekatan melainkan bisa disimpan dimana saja dan dihubungkan menggunakan pointer seperti linked list.
 |
| https://miro.medium.com/max/677/1*Z89j_NoDx9HkFcPHy3rPZg.png |
Binary Tree
merupakan sebua tree dengan setiap node hanya boleh memiliki masksimal 2 anak yang bisa dibedakan dengan left child dan right child. Berikut merupakan beberapa tipe dalam binary tree:
- Pohon biner penuh: Semua simpul selain daunmemiliki 2 anak dan tiap cabang memiliki panjang ruas yang sama.
- Pohon biner lengkap: semua simpul selain daun memiliki 2 anak tetapi tiap cabang memiliki panjang ruas berbeda.
- Pohon biner miring: Dua pohon yang semua simpulnya mempunyai satu anak / turunan kecuali daun.
- Pohon biner seimbang: Pohon biner di mana tidak ada daun yang lebih jauh dari akar daripada daun lainnya.
BST (Binary Search Tree)
 |
sumber: https://blogger.googleusercontent.com/img/proxy/AVvXsEg5m0k8s6IcTrBVZKFjARzWJRsZOs_1_LtT2hxDtION01HCeUqER6i7Ly27ebjKrYYkQ0JORXzenaUQ5IANUF9loQ8tAXpfuqEX6aUE_tjA_KYVA4H_CtpzB8T4_AeWMMQPBJ7ahrruimVeKqMluUBYrDQa5BbLl8iGESY47192E_lz=
|
Keunggulan Binary search adalah dapat men searching file dengan cepat, mensort dengan
cepat dan dapat dengan mudah menginsert atau mendelete.
Binary search tree bisa dibilang merupakan versi sorted dari binary tree. Namun di dalam BST ada beberapa aturan yaitu:
- Subtree sebelah kiri selalu lebih kecil nilainya dari pada root node.
- Subtree sebelah kanan selalu lebih besar nilainya daripada root node.
- Subtree kiri dan kanan masing-masing juga harus berupa Binary Search Three.
Terdapat 3 buah operasi yang dapat dilakukan di Binary Search Tree
- find(x): Mencari node x di dalam sebuah BST.
- insert(x): memasukan node x baru kedalam BST.
- remove(x): Mendelete node x dari dalam sebuah BST.
kunjungi: https://datstruct17.blogspot.com/2020/03/binary-search-tree.html
kunjungi: https://datstruct17.blogspot.com/2020/03/binary-search-tree.html
Code minimarket scenario
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void menu(){
printf("========================");
printf("\nDreammers Market");
printf("\n========================");
printf("\n1. Input");
printf("\n2. Edit");
printf("\n3. Delete");
printf("\n4. Checkout");
printf("\nChoose>> \n");
}
struct data {
int qty;
char produk[100];
int harga;
struct data* next;
struct data* prev;
}*head = NULL, *tail = NULL;
void insert() {
int qty;
int harga;
char produk[100];
printf("Type product name: ");
scanf(" %[^\n]", &produk); getchar();
printf("Type qty: ");
scanf("%d", &qty);getchar();
harga = produk[0] * 100;
struct data* node = (struct data*) malloc(sizeof(struct data));
node->qty = qty;
strcpy(node->produk, produk);
node->harga = harga;
node->next = NULL;
node->prev = NULL;
if(head == NULL) {
head = tail = node;
}
else {
tail->next = node;
node->prev = tail;
tail = node;
}
}
void editNode(){
int flag = -1;
char produk[100];
int qty;
printData();
printf("Produk yang ingin di edit: ");
scanf(" %[^\n]", &produk);
struct data *temp = head;
while(temp != NULL) {
if(strcmp(temp->produk, produk)==0) {
flag = 1;
break;
}
temp = temp->next;
}
if(flag == 1){
// printf("Input Produk Baru: ");
// scanf("%[^\n]", &produk);
printf("Input Qty Baru: ");
scanf("%d", &qty);
temp->qty = qty;
// strcpy(temp->produk, produk);
printf("Produk Berhasil di Edit!!\n");
}
else{
printf("Produk Tidak Ada Di List!!\n");
editNode();
}
}
void deleteNode() {
//search node
char produk[100];
int flag = -1;
printData();
printf("Produk yang ingin di delete: ");
scanf(" %[^\n]", &produk);
struct data *temp = head;
while(temp != NULL) {
if((strcmp(temp->produk, produk)==0)){
flag = 1;
break;
}
temp = temp->next;
}
if(flag == 1){
//kondisi dihapus adalah data satu-satunya di list
if(temp == head && head == tail) {
head = tail = NULL;
free(temp);
}
//kondisi dihapus adalah head
else if(temp == head) {
head = head->next;
head->prev = NULL;
free(temp);
}//kondisi dihapus adalah tail
else if(temp == tail) {
tail = tail->prev;
tail->next = NULL;
free(temp);
}
//kondisi dihapus ditengah
else {
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
}
printf("Produk Berhasil di Delete!!\n");
}
else{
printf("Produk Tidak ada di list!!\n");
deleteNode();
}
}
void checkOut(){
int total = 0;
struct data* temp = head;
if(temp == NULL){
printf("List Kosong!\n");
}
else{
printf("%10s%10s%15s\n", "Popduk", "Qty", "Harga");
while(temp != NULL) {
printf("%10s%10d%10d%10d\n", temp->produk, temp->qty, temp->harga, temp->harga*temp->qty);
total += temp->harga * temp->qty;
temp = temp->next;
}
printf("%15s RP.%3.d\n\n", "TOTAL ",total);
printf(" \"Kindness is free\"");
}
}
void freeAll() {
struct data* temp;
while(head != NULL) {
temp = head;
head = head->next;
free(temp);
}
head = tail = NULL;
}
void printData() {
struct data* temp = head;
if(temp == NULL){
printf("List Kosong!\n");
}
else{
while(temp != NULL) {
printf("Produk: %s\n", temp->produk);
printf("Qty: %d\n", temp->qty);
temp = temp->next;
}
}
}
int main() {
int choose;
do{
menu();
scanf("%d", &choose);
switch(choose){
case 1: insert();
break;
case 2: editNode();
break;
case 3: deleteNode();
break;
case 4: checkOut();
choose = 5;
}
}while(choose!=5);
return 0;
}
Komentar
Posting Komentar