Archive for Maret 2020
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node{
char productName[100];
int qty;
int price;
struct node *prev, *next;
}*head = NULL, *tail = NULL;
void pushData(char productName[], int qty, int price){
struct node *newNode = (struct node*)malloc(sizeof(struct node));
//prepare newNode
strcpy(newNode->productName, productName);
newNode->qty = qty;
newNode->price = price;
newNode->next=NULL;
newNode->prev=NULL;
if(head==NULL){
head=tail=newNode;
}
else if(strcmp(productName, head->productName)<0){
newNode->next=head;
head->prev=newNode;
head=newNode;
}
else if(strcmp(productName, tail->productName)>0){
newNode->prev=tail;
tail->next=newNode;
tail=newNode;
}
else
{
struct node *ptr = head;
while(ptr!=NULL){
if(strcmp(productName,ptr->productName)<0){
newNode->next=ptr;
newNode->prev=ptr->prev;
ptr->prev->next=newNode;
ptr->prev=newNode;
break;
}
ptr = ptr->next;
}
}
}
void editData(char productName[], int qty, int price){
struct node *find = head->next;
if(strcmp(productName,head->productName)==0){
head->qty=qty;
head->price=price;
}
else
{
while(find!=NULL){
if(strcmp(productName,find->productName)==0){
find->qty=qty;
find->price=price;
break;
}
find=find->next;
}
}
}
void deleteData(char productName[]){
struct node *del = head->next;
if(head==tail)
{
if(strcmp(productName,head->productName)==0){
head=tail=NULL;
}
}
else if(strcmp(productName,head->productName)==0){
struct node *ptr = head;
head=head->next;
head->prev=NULL;
free(ptr);
}
else if(strcmp(productName,tail->productName)==0){
struct node *ptr2 = tail;
tail=tail->prev;
tail->next=NULL;
free(ptr2);
}
else{
while(del!=NULL){
if(strcmp(productName,del->productName)==0){
del->prev->next=del->next;
del->next->prev=del->prev;
del->next=NULL;
del->prev=NULL;
free(del);
break;
}
del=del->next;
}
}
}
void printData(){
struct node *ptr = head;
if(ptr==NULL){
printf("No product...\n");
}
else{
printf("| Product | QTY | Price |\n");
printf("=========================\n");
while(ptr!=NULL){
printf("| %s | %d | %d |\n", ptr->productName, ptr->qty, ptr->price);
ptr = ptr->next;
}
}
}
int main(){
int menu, qty, price, newQty, newPrice;
int up = 100000;
int low = 10000;
char productName[100], productFind[100], productDel[100];
do{
system("cls");
printf("=====================\n");
printf("TOKO KOH MORENO JAYA\n");
printf("=====================\n\n");
printData();
printf("\n\n=================");
printf("\n------MENU------\n");
printf("=================\n");
printf("1. Add product\n");
printf("2. Edit product quantity\n");
printf("3. Delete product\n");
printf("4. Checkout\n");
printf("Choose >> ");
scanf("%d", &menu); getchar();
switch(menu)
{
case 1:
printf("Input product name: ");
scanf("%[^\n]", &productName); getchar();
printf("Input product quantity: ");
scanf("%d", &qty); getchar();
price = (rand()%(up-low+1))+low;
pushData(productName, qty, price);
printf("Data Succesfully Added!");
break;
case 2:
printf("Select a product to change: ");
scanf("%[^\n]", &productFind); getchar();
printf("Input new quantity: ");
scanf("%d", &newQty); getchar();
newPrice = (rand()%(up-low+1))+low;
editData(productFind, newQty, newPrice);
printf("Data has been updated!");
break;
case 3:
printf("Select a product to remove: ");
scanf("%[^\n]", &productDel);
deleteData(productDel);
printf("Data has been removed");
break;
}
}while(menu!=4);
printf("Kindness is free ;)\n");
return 0;
}
#include <string.h>
#include <stdlib.h>
struct node{
char productName[100];
int qty;
int price;
struct node *prev, *next;
}*head = NULL, *tail = NULL;
void pushData(char productName[], int qty, int price){
struct node *newNode = (struct node*)malloc(sizeof(struct node));
//prepare newNode
strcpy(newNode->productName, productName);
newNode->qty = qty;
newNode->price = price;
newNode->next=NULL;
newNode->prev=NULL;
if(head==NULL){
head=tail=newNode;
}
else if(strcmp(productName, head->productName)<0){
newNode->next=head;
head->prev=newNode;
head=newNode;
}
else if(strcmp(productName, tail->productName)>0){
newNode->prev=tail;
tail->next=newNode;
tail=newNode;
}
else
{
struct node *ptr = head;
while(ptr!=NULL){
if(strcmp(productName,ptr->productName)<0){
newNode->next=ptr;
newNode->prev=ptr->prev;
ptr->prev->next=newNode;
ptr->prev=newNode;
break;
}
ptr = ptr->next;
}
}
}
void editData(char productName[], int qty, int price){
struct node *find = head->next;
if(strcmp(productName,head->productName)==0){
head->qty=qty;
head->price=price;
}
else
{
while(find!=NULL){
if(strcmp(productName,find->productName)==0){
find->qty=qty;
find->price=price;
break;
}
find=find->next;
}
}
}
void deleteData(char productName[]){
struct node *del = head->next;
if(head==tail)
{
if(strcmp(productName,head->productName)==0){
head=tail=NULL;
}
}
else if(strcmp(productName,head->productName)==0){
struct node *ptr = head;
head=head->next;
head->prev=NULL;
free(ptr);
}
else if(strcmp(productName,tail->productName)==0){
struct node *ptr2 = tail;
tail=tail->prev;
tail->next=NULL;
free(ptr2);
}
else{
while(del!=NULL){
if(strcmp(productName,del->productName)==0){
del->prev->next=del->next;
del->next->prev=del->prev;
del->next=NULL;
del->prev=NULL;
free(del);
break;
}
del=del->next;
}
}
}
void printData(){
struct node *ptr = head;
if(ptr==NULL){
printf("No product...\n");
}
else{
printf("| Product | QTY | Price |\n");
printf("=========================\n");
while(ptr!=NULL){
printf("| %s | %d | %d |\n", ptr->productName, ptr->qty, ptr->price);
ptr = ptr->next;
}
}
}
int main(){
int menu, qty, price, newQty, newPrice;
int up = 100000;
int low = 10000;
char productName[100], productFind[100], productDel[100];
do{
system("cls");
printf("=====================\n");
printf("TOKO KOH MORENO JAYA\n");
printf("=====================\n\n");
printData();
printf("\n\n=================");
printf("\n------MENU------\n");
printf("=================\n");
printf("1. Add product\n");
printf("2. Edit product quantity\n");
printf("3. Delete product\n");
printf("4. Checkout\n");
printf("Choose >> ");
scanf("%d", &menu); getchar();
switch(menu)
{
case 1:
printf("Input product name: ");
scanf("%[^\n]", &productName); getchar();
printf("Input product quantity: ");
scanf("%d", &qty); getchar();
price = (rand()%(up-low+1))+low;
pushData(productName, qty, price);
printf("Data Succesfully Added!");
break;
case 2:
printf("Select a product to change: ");
scanf("%[^\n]", &productFind); getchar();
printf("Input new quantity: ");
scanf("%d", &newQty); getchar();
newPrice = (rand()%(up-low+1))+low;
editData(productFind, newQty, newPrice);
printf("Data has been updated!");
break;
case 3:
printf("Select a product to remove: ");
scanf("%[^\n]", &productDel);
deleteData(productDel);
printf("Data has been removed");
break;
}
}while(menu!=4);
printf("Kindness is free ;)\n");
return 0;
}
Program Toko Koh Moreno Jaya
Linked List I
- Linked List : sebuah struktur data linear yang terdiri dari data berurut sehingga tiap data berisi referensi ke data berikutnya dalam urutan.
- Elemen dalam Linked List disebut Node
- Linked List memungkinkan Insertion dan Deletion pada node di lokasi manapun dalam list
- Linked List dibagi kedalam dua bentuk : Single Linked List & Double Linked List
- Linked List hanya bisa diakses secara sekuensial (berurutan) sesuai jejak penyimpanan data
- Single linked list : setiap node hanya memiliki 1 pointer mengarah ke node lain
Linked List (ii)
Circular
Linked List : Circular Linked List adalah varian dari Linked List dimana node
pertama (head) menunjuk ke node terakhir (tail) dan kebalikannya. Circular
dapat dibentuk dengan single maupun double linked list
Circular
Doubly Linked List : Sama dengan yang single, hanya saja total pointer ada dua.
Double
linked list : Linked list dimana setiap node memiliki 1 pointer keareah node berikutnya
dan 1 pointer kearah node sebelumnya. Seperti halnya single linked list, double
linked list juga dapat melakukan insert dan delete.
Insert :
seperti single linked list, pertama kita harus mengalokasikan node baru
kedalam list, menetapkan value pada node tersebut, dan barulah kita sambungkan
ke list.
Contoh :
1. Jika kita ingin menaruh node baru tersebut dibelakang tail
struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode));
struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode));
node->value
= x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail =
node;
struct tnode *a = ??;
struct tnode *b = ??;
struct tnode *node = (struct
tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next =
b;
node->prev =
a;
a->next =
node;
b->prev =
node
Delete :
4 kondisi yang harus diperhatikan saat melakukan delete:
- Node yang akan dihapus adalah satu-satunya node di linked list
- Node berada di Head
- Node berada di Tail
- Node berada diantara Head dan Tail
- Jika sesuai kondisi (1)
free(head);
head = NULL;
tail = NULL;
head = NULL;
tail = NULL;
- Jika sesuai kondisi (2)
head = head->next;
free(head->prev);
head->prev = NULL
free(head->prev);
head->prev = NULL
- Jika sesuai kondisi (3)
tail =
tail->prev;
free(tail->next);
tail->next = NULL;
free(tail->next);
tail->next = NULL;
- Jika sesuai kondisi (4)
struct tnode *curr = head;
while ( curr->next->value != x ) curr = curr->next;
struct tnode *a = curr;
struct tnode *del = curr->next;
struct tnode *b = curr->next->next;
a->next = b;
b->prev = a;
free(del);
while ( curr->next->value != x ) curr = curr->next;
struct tnode *a = curr;
struct tnode *del = curr->next;
struct tnode *b = curr->next->next;
a->next = b;
b->prev = a;
free(del);
Stack
Stack merupakan struktur data yang menyimpan elemen-elemennya secara teratur menggunakan prinsip LIFO (Last in First out). Sesuai dengan artinya secara langsung, dalam prinsip LIFO data yang terakhir kali dimasukkan akan menjadi yang pertama saat dikeluarkan.Stack adalah struktur data linear yang dapat diimplementasikan dengan menggunakan Array atau Linked List.
Stack dengan array
Stack memiliki 2 variable :- TOP : menyimpan alamat elemen paling atas dari stack
Catatan :- Jika TOP = NULL, maka stack kosong
- Jika TOP = MAX - 1, maka stack full
- Jika TOP = integer tertentu, maka insertion dan deletion akan berakhir pada posisi tersebut
- MAX : menyimpan jumlah maksimum elemen yang dapat ditumpuk oleh stack
Stack dengan linked
Pada Linked Stack, setiap node mempunyai 2 bagian:- satu menyimpan data
- satu menyimpan alamat node berikutnya
Operasi pada Stack
push() : menambah objek kedalam stackpop() : menghilangkan sebuah objek dalam stack
top() : mengembalikan TOP objek dari stack
Infix, Prefix, dan Postfix
Prefix : operator ditaruh sebelum operand- contoh : + 5 * 3 4 = 17
- contoh : 5 + 3 * 4 = 17
- contoh : 5 3 4 * + = 17
Evaluasi untuk postfix (secara manual)
Scan dari kiri ke kanan
7 6
5 x 3
2 ^ – + , scan sampai menemukan operator pertama
7 6
5 x
3 2 ^
– + , hitunglah 6 * 5
7 30
3 2 ^
– + , scan lagi hingga menemukan operator berikutnya
7 30
3 2 ^ – + , hitung 32
7 30
9 – + , scan lagi hingga menemukan operator berikutnya
7 30 9 –
+ , hitung 30 - 9
7 21 + , scan lagi
7
21
+ ,
hitung 7 + 21
28 , Jawaban akhir
Evaluasi untuk prefix (secara manual)
Scan dari kanan ke kiri
+ 7
– x 6
5 ^ 3 2 , Scan hingga menemukan operator pertama
+ 7
– x 6
5 ^
3 2 , hitung 32
+ 7
– x 6
5 9 , Scan lagi hingga menemukan operator berikutnya
+ 7
– x
6 5
9 , hitunglah 6 * 5
+ 7
– 30 9 , Scan hingga menemukan operator berikutnya
+ 7 – 30
9 , hitung 30 - 9
+ 7 21 , Scan hingga menemukan operator berikutnya
+
7 21 , hitung 7 + 21
28 , Jawaban akhirCara konversi infix ke postfix
- Cari operator dengan precedence (prioritas) tertinggi
- Taruh operator tersebut dibelakang operand
- Ulangi hingga selesai
Cara konversi infix ke prefix
- Cari operator dengan precedence (prioritas) tertinggi
- Taruh operator tersebut setelah operand
- Ulangi hingga selesai
Depth First Search
Depth First Search adalah algoritma yang dipakai untuk pencarian jalur pada tree atau graph. Pencarian mulai dari akar kemudian merambat sejauh mungkin sepanjang masing-masing cabang dari tree lalu barulah melakukan backtracking.Penggunaan DFS:
- menemukan titik artikulasi dan menjembatani pada grafik
- menemukan komponen yang terhubung
- Topological sorting
- dan lain-lain
Queue
Queue dapat diimplementasikan dengan array atau Linked List.Elemen-elemen pada queue disimpan dengan metode First in First out (FIFO), sehingga data yang pertama kali masuk akan dikeluarkan pertama kali juga. Data dimasukkan melalui salah satu ujung (rear) dan keluar pada ujung lainnya (front).
Queue memiliki 2 variabel yaitu front dan rear yang menunjuk posisi dimana deletion dan insertion dilakukan.
Queue dengan Linked
Dalam linked queue setiap elemen memiliki 2 bagian:- satu menyimpan data
- satu menyimpan alamat untuk elemen berikutnya
Operasi dalam queue
- push() : menambah data pada rear
- pop() : menghilangkan data pada front
- front() / peek : mengembalikan value data paling depan dari queue
Circular Queue
Definisi dari circular queue sama saja dengan queue hanya saja posisi terakhir dihubungkan kembali dengan posisi awal.Pengaplikasian Queue
- Deques
- Priority Queue
- Breadth First Search
Deques
Deques (double-ended queue) adalah list dimana elemen dapat ditambahkan atau dihapus melalui ujung manapun.Dikenal juga dengan nama head-tail Linked List karena elemen dapat ditambahkan atau dihapus dari front (head) atau back / rear (tail).
Dua macam Deques:
- Input Restricted Deque : dalam deque ini hanya deletion yang dapat dilakukan dari kedua ujung
- Output Restricted Deque : dalam deque ini hanya insertion yang dapat dilakukan dari kedua ujung
Priority Queue
Priority queue adalah tipe data abstrak yang mirip dengan queue biasa. Namun, tiap elemen memiliki prioritas sendiri.Elemen dengan prioritas lebih tinggi akan diproses terlebih dahulu sebelum elemen dengan prioritas lebih rendah.
Elemen dengan tingkat prioritas yang sama akan diproses sesuai dengan urutan data yang pertama kali muncul / first come first serve (FCFS).
Breadth First Search
BFS sama saja dengan DFS, bedanya data structure yang digunakan adalah queue bukan stack.Hash
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil keys dengan cepat.Dalam hashing string akan diubah menjadi string yang lebih pendek sebagai keys (kunci kata) dari string originalnya.
Hashing digunakan untuk mengindeks dan mengambil data dalam database karena teknik mencari kata kunci ini lebih cepat daripada harus mencari langsung data originalnya.
Hashing juga dapat disebut sebagai konsep mendistribusikan keys dalam array yang disebut hash table menggunakan fungsi yang telah ditentukan yang disebut hash function.
Hash Table
Hash Table adalah tabel (array) tempat menyimpan string original.Index untuk array pada hash table disebut hashed key, sementara value adalah string original dari key tersebut.
Beberapa string bisa saja memiliki keys yang sama.
Hash Function
berikut beberapa method untuk meng-hash keys dari string:- Mid-square
- Division
- Folding
- Digit Extraction
- Rotating Hash
Value dari string dipangkatkan, kemudian sebagian angka dari hasil pangkat tersebut dipakai sebagai key.
Contoh:
value = 1254; hasil pangkat = 1572516; hash = 725
Division:
String/identifier dimodulo dengan suatu integer (biasanya memakai bil. prima, size dari tabel, atau size memori yang digunakan).
Contoh:
Misal kita punya string berupa "ABCD". Jumlahkan ASCII dari string tersebut dan bagi dengan salah satu angka prima misalnya 2.
(65 + 66 + 67 + 68) / 2 = 266 / 2 = 133
Folding:
Pisahkan string/identifier ke beberapa bagian, kemudian jumlahkan bagian-bagian tersebut.
Contoh:
Misal kita memiliki integer 6721, pisahkan menjadi 2 bagian yaitu 67 dan 21, kemudian jumlahkan menjadi 83.
Digit Extraction:
Mengambil beberapa digit dari angka yang diberikan dan digabungkan menjadi key.
Contoh:
Misal kita memiliki integer 1435462. Ambil digit ke-1, ke-3, dan ke-5 maka kita mendapat 134
Rotating Hash:
Gunakan method manapun untuk mendapat hash code/address kemudian putar balik angka yang telah didapat untuk mendapat hash code/address yang baru.
Contoh:
Misal kita menggunakan method division, putar balik hash yang didapat dari 133 menjadi 331
Collision
Collision terjadi saat beberapa string menggunakan hash key yang sama.Cara yang biasa digunakan untuk mengatasinya adalah:
- Linear Probing : Cari slot kosong berikutnya dan masukkan kesana
- Chaining : Memasukkan string sebagai list berantai (linked list)
Untuk chaining, kita hanya perlu melakukan iterate untuk mencari string yang diinginkan.
Tree
Tree adalah struktur data non-linear yang menggambarkan hubungan hierarki antara objek data.Untuk penggambaran, node pada tree tidak perlu digambarkan berdekatan dan boleh ditaruh dimana saja. Node pada tree dihubungkan dengan pointer.
Konsep Tree
- Node teratas disebut root
- Garis yang menyambungkan parent dengan child disebut edge
- Nodes yang tidak memiliki child disebut leaf
- Nodes dengan parent yang sama disebut sibling
- Total sub-tree suatu node disebut degree
- Maximum degree suatu node pada tree disebut height / depth
- Node yang berada diatas node lain dan saling terhubung disebut ancestor
- Node yang berada dibawah node lain dan saling terhubung disebut descendant
Binary Tree
Binary tree adalah struktur data rooted tree dimana masing-masing node paling banyak memiliki dua anak. (left child dan right child)Tiper-tipe binary tree:
- Perfect Binary Tree
- Complete Binary Tree
- Skewed Binary Tree
- Balanced Binary Tree
Complete binary tree : binary tree dimana setiap level kecuali yang terakhir, terisi penuh, dan semua anak node pada level terakhir harus menempati titik kiri.
Skewed binary tree : binary tree dimana setiap node setidaknya memiliki satu anak.
Balanced binary tree : jarak setiap leaf dengan root adalah sama.
Implementrasi binary tree pada array :
- Index untuk node root = 0
- Index left child = 2p + 1 (p = index parent)
- Index right child = 2p + 2 (p = index parent)
- Index parent = (p - 1) / 2
Threaded Binary Tree
Threaded Binary Tree sama saja dengan binary tree hanya saja berbeda dalam cara penyimpanan pointer NULL.Ruang node yang terbuang karena menyimpan NULL dapat dipakai secara lebih efisien.
Ruang tersebut dapat dipakai untuk menyimpan pointer ke in-order predecessor dan in-order successor (pointer-pointer ini disebut thread).
Binary Search Tree
Definition
Binary search tree adalah sebuah struktur data yang memungkinkan pencarian cepat, penyortiran cepat, serta penyisipan dan penghapusan data yang mudah.Binary serach tree (BST) juga dikenal sebagai sorted version of binary tree atau versi binary tree yang terurut.
Aturan node pada BST :
- Tangan kanan pada node akan menunjuk ke anak node dengan key lebih besar dari dia
- Tangan kiri pada node akan menunjuk ke anak node dengan key lebih kecil dari dia
BST Operations
BST memiliki 3 operasi dasar:- search( ) : untuk mencari key tertentu dalam BST
- insert( ) : untuk memasukkan key baru ke dalam BST
- remove( ) : untuk menghilangkan key tertentu dalam BST
Seacrh Operation
Operasi search dilakukan mulai dari root (node pertama). Jika root adalah node yang dicari maka operasi search selesai. Jika tidak, maka cek key dari node yang dicari apakah lebih besar atau lebih kecil dari root. Bila key yang dicari lebih kecil, maka search dilakukan secara rekursif pada sub-tree sebelah kiri dan kebalikannya jika key lebih besar.Insert Operation
Operasi insert dilakukan mulai dari root (node pertama). Node baru akan dimasukkan pada leaf (bagian dari tree yang belum memiliki child node sama sekali) dan menjadi leaf baru. Jika key dari node baru tersebut lebih kecil dari root maka dia akan melakukan rekursif hingga menemukan leaf pada sub-tree sebelah kiri. Berlaku kebalikan jika key dari node baru lebih besar dari root.Delete Operation
Operasi delete sedikit lebih rumit daripada operasi search dan insert. Dalam operasi delete kita harus memperhatikan 3 kondisi:- Jika key yang ingin dihapus ada pada leaf, langsung hapus node tersebut
- Jika key yang indin dihapus memiliki 1 child node, maka child node tersebut harus menggantikan posisi parent node yang akan dihapus.
- Jika key yang ingin dihapus memiliki 2 child node, maka pilih salah satu cara untuk menggantikan node tersebut. Cara pertama adalah dengan memilih node paling kanan dari sub-tree sebelah kiri, cara kedua adalah dengan memilih node paling kiri dari sub-tree sebelah kanan.
Tugas Kelas Besar
Berikut saya sertakan link untuk code tugas kelas besar: