Summary

Linked List


Linked List merupakan data struktur linear, di mana memeory penyimpanan untuk tiap data tidak berdekatan posisinya.Linked List terdiri dari node - node yang berisi data - data. Di dalam Linked List dapat dilakukan insertion dan deletion di posisi manapun.

Linked List sudah sangat membantu menyelesaikan masalah yang pernah terjadi, yaitu kebutuhan penyimpanan data yang tidak dapat diprediksi.

Linked List terdapat 2 tipe, yaitu

1. Single Linked List

Di dalam Single Linked List hanya dapat satu arah, yaitu dari kiri ke kanan, dengan menggunakan pointer yang umunya diberi nama "next", dan terdapat pointer "head" sebagai penunjuk data pada bagian depan.

Di dalam Double Linked List terdapat dua arah, yaitu dari kiri ke kanan dan arah sebaliknya, dengan menggunakan dua pointer yang umumnya diberi nama "next" untuk arah ke kanan dan "prev" untuk arah yang ke kiri, dan pula terdapat dua pointer lagi sebagai penunjuk bagian depan dan belakang, yaitu "head" dan "tail".

https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2014/03/DLL1.png

Stack & Queue

Stack

Stack merupakan struktur data linear yang mengikuti prinsip LIFO (Last In First Out), yaitu datang terakhir, keluar pertama.  

https://media.geeksforgeeks.org/
wp-content/uploads/
geek-stack-1.png

Dalam stack, elemen teratas / terkahir, selalu ditunjuk dengan pointer, yang biasanya dinamakan "top".
Di dalam stack juga, terdapat beberapa operasi yang digunakan:
1. push(), untuk menambah elemen data.
2. pop(), untuk menghapus elemen data.
3. top(), untuk mengambil data teratas.






Prefix, Infix, Postfix Notation

Prefix merupakan di mana sebuah operator berada di depan operand (operator operand1 operand2).
Contoh:
+ 2 3
* 10 + 5 7

Infix merupakan di mana sebuah operator berada di tengah operand (operand1 operator operand2).
Contoh:
5 - 3
10 * 7 - 3

Postfix merupakan di mana sebuah operator berada di belakang operand (operand1 operand2 operator).
Contoh:
8 2 /
10 5 - 5 /


Queue

Queue merupakan struktur data linear yang mengkuti prinsip FIFO (First In First Out), yaitu datang pertama, keluar pertama.

https://media.geeksforgeeks.org/
wp-content/uploads/
geek-queue-1.png

Dalam Queue, elemen pertama selalu ditunjuk dengan pointer "front" dan elemen terkahir dengan pointer "rear".
Di dalam queue juga, terdapat beberapa operasi, yaitu:
1. enqueue(), dapat disebut push(), untuk menambah elemen data.
2. dequeue(), dapat disebut pop(), untuk menghapus elemen data.
3. front() untuk mengambil data.





Hashing dan Hash Table

Hashing

Hashing merupakan suatu teknik untuk menyimpan dan mengambil kunci dengan cepat. Dengan Hashing, string diubah menjadi suatu value yang lebih pendek atau kunci untuk menggantikan stirng. Hashing juga dikenal sebagai distributor kunci array Hash Table yang menggunakan function Hash Function.
https://www.tutorialspoint.com/data_structures_
algorithms/images/hash_function.jpg


Hash Table

Hash Table merupakan table / array tempat menyimpan string. Index dari Hash Table merupakan kunci dari Hashing yang sudah mengandung string.

Hash Function

Terdapat banyak cara untuk mengubah string ke kunci. Berikut meupakan cara penting untuk membuat Hash Function.
- Mid - square
- Division
- Folding
- Digit Extraction
- Rotating hash

Collision

Collision merupakan suatu peristiwa di mana kunci baru, menempati tempat yang sudah terisi dengan kunci sebelumnya. Terdapat cara untuk mengatasi Collision, yaitu:
-  Linear probing
- Chaining


Trees dan Binary Tree

Konsep Tree

Di dalam Tree, node teratas diberi nama root, garis yang menghubungkan praent dan child disebut edge, node yang tidak memiliki anak disebut leaf, node - node yang memiliki parent yang sama disebut sibling.

Konsep Binary Tree

Di dalam Binary Tree, setiap node hanya memiliki maksimal 2 anak, di mana anak - anak tersebut disebut left child dan right child. Node yang tidak memiliki anak disebut leaf.
https://www.geeksforgeeks.org/wp-content/
uploads/binary-tree-to-DLL.png

Jenis - Jenis Binary Tree

- Perfect Binary Tree


- Complete Binary Tree

- Skewed Binary Tree

- Balanced Binary Tree

Threaded Binary Tree

Threaded Binary Tree mirip dengan Binary Tree hanya perbedaan nya Threaded Binary Tree mentimpan pointer NULL.




References :
https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/


Source Code

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

int many=0;

struct tnode{
char name[21];
int qty;
long int price;
struct tnode *next;
struct tnode *prev;
}*head, *tail, *curr;

void push_front(){
curr->next=head;
head->prev=curr;
head=curr;

head->prev = tail->next = NULL;
}

void push_back(){
curr->prev=tail;
tail->next=curr;
tail=curr;

tail->next = head->prev = NULL;
}

void push(char *name, int qty, long int price){
curr = (struct tnode*) malloc(sizeof(struct tnode));
strcpy(curr->name,name);
curr->qty=qty;
curr->price=price;

if(head==NULL){
head = tail = curr;
}
else{
if(strcmp(curr->name,head->name)<0){
push_front();
}
else if(strcmp(curr->name,tail->name)>0){
push_back();
}
else{
tnode *temp = head;
while(strcmp(curr->name,temp->next->name)>0){
temp = temp->next;
}
curr->next=temp->next;
temp->next->prev=curr;
temp->next=curr;
curr->prev=temp;
}
}
head->prev = tail->next = NULL;
}

int random(){
long int price;
int n1,n2,n3,n4,n5;
srand(time(0));
n1 = ((rand() % (9 - 0 + 1)) + 0)*10000;
n2 = ((rand() % (9 - 0 + 1)) + 0)*1000;
n3 = ((rand() % (9 - 0 + 1)) + 0)*100;
n4 = ((rand() % (9 - 0 + 1)) + 0)*10;
n5 = (rand() % (9 - 0 + 1)) + 0;
return price = n1+n2+n3+n4+n5;
}

void menu();

void print(){
printf("===============================================\n");
printf("| No | Name            | Price     | Quantity |\n");
printf("===============================================\n");
if(head==NULL){
printf("|             There is no item                |\n");
printf("===============================================\n");
}
else{
curr=head;
int a=1;
while(curr!=NULL){
printf("| %-2d.| %-16s| Rp%-8ld| %-9d|\n",a,curr->name,curr->price,curr->qty);
a++;
curr = curr->next;
}
printf("===============================================\n");
}
}

void view_item(){
print();
menu();
}

void checkout(){
if(head==NULL){
printf("\nThere is no item yet !\n");
menu();
}
print();
printf("\n");
curr = head;
long long int total=0;
while(curr!=NULL){
printf("%-16s x%-3d = Rp%ld\n",curr->name,curr->qty,curr->qty*curr->price);
total+=(curr->qty*curr->price);
curr = curr->next;
}
printf("--------------------------------------------------------------\n");
printf("Total checkout : Rp%lld\n\n",total);
int choose;
do{
printf("1. Checkout\n");
printf("1. Cancel\n\n");
printf("Choose >> ");
scanf("%d",&choose);
}while(choose<1 || choose>2);
switch(choose){
case 1:
printf("\nTHANK YOU FOR SHOPPING IN APRIL'S MARKET !\n");
break;
case 2:
menu();
break;
}
}

void pop_back(){
if(tail!=NULL){
curr = tail;
tail= tail->prev;
free(curr);
tail->next=NULL;
}
}

void pop_front(){
if(head!=NULL){
curr = head;
head = head->next;
free(curr);
head->prev=NULL;
}
}
void delete_item(){
if(head==NULL){
printf("\nThere is no item !\n");
menu();
}
print();
int no;
printf("Input item number: ");
scanf("%d",&no);
if(no<1 || no>many){
printf("\nItem number %d doesn't exist\n",no);
delete_item();
}
if(head->next==NULL){ //untuk pop data tinggal 1
curr = head;
head = NULL;
tail = NULL;
free(curr);
}
else if(no==1) pop_front();
else if(no==many) pop_back();
else{
tnode *temp = head;
for(int a=1;a<no-1;a++){
temp = temp->next;
}
curr = temp->next;
temp->next=curr->next;
curr->next->prev=temp;
free(curr);
many--;
}
printf("\nItem has been deleted !\n");
menu();
}

void change_qty(){
print();
int no;
printf("Input item number: ");
scanf("%d",&no);
if(no<1 || no>many){
printf("\nItem number %d doesn't exist\n",no);
change_qty();
}
else{
curr = head;
for(int a=1;a<no;a++){
curr = curr->next;
}
int qty;
do{
printf("Input quantity [ min. 1 ]: ");
scanf("%d",&qty);
}while(qty<1);
curr->qty = qty;
printf("\nQuantity has been changed !\n");
menu();
}
}

void add_item(){
char name[21];
int qty;
long int price;
gets(name);
do{
printf("Input item name [ 1..20 characters ]: ");
gets(name);
}while(strlen(name)<1 || strlen(name)>20);
do{
printf("Input quantity [ min. 1 ]: ");
scanf("%d",&qty);
}while(qty<1);
price = random();
push(name,qty,price);
many++;
printf("\nItem Successfully Add !\n");
menu();
}

void pop_all(){
if(head==NULL){
printf("\nThere is no item !\n");
menu();
}
curr = head;
while(curr!=NULL){
head = head->next;
free(curr);
curr = head;
}
head = tail = NULL;
printf("\n Item has been reset !\n");
menu();
}

void menu(){
printf("1. Add Item\n");
printf("2. View Item List\n");
printf("3. Change Quantity\n");
printf("4. Delete Item\n");
printf("5. Reset\n");
printf("6. Checkout\n");
printf("7. Exit\n\n");
printf("Choose >> ");
int choose;
scanf("%d",&choose);
if(choose<1 || choose>7){
printf("Please input between 1...7\n");
menu();
}
switch(choose){
case 1:
add_item();
break;
case 2:
view_item();
break;
case 3:
change_qty();
break;
case 4:
delete_item();
break;
case 5:
pop_all();
break;
case 6:
checkout();
break;
case 7:
break;
}
}

int main(){
printf("April's Market\n\n");
menu();
}

Komentar

Posting Komentar

Postingan populer dari blog ini

AVL-BTREE

Gambar
AVL Tree and B-Tree AVL Tree AVL Tree  merupakan bagian dari Binary Tree Search  ( BST ), di mana AVL Tree memiliki depth untuk subtree sebelah kiri dan kanan memiliki perbedaan depth yaitu lebih kurang sama dengan satu.  Sehingga  AVL Tree  memiliki depth yang lebih stabil dibandingkan  Binary Search Tree. https://media.geeksforgeeks.org/wp-content/cdn-uploads/AVL-Tree1.jpg Untuk mempertahankan keseimbangannya AVL Tree memiliki method untuk menyeimbangkan tree, method ini disebut rotation . Method rotation ini memiliki 4 macam, yaitu 1. Right Rotation                    5                                                          2                   /                                                         /     \                 2                ------------------>              1        5                /                     Right Rotate              1 2. Left Rotation                     5                                             
Baca selengkapnya