- Pointer and Array
Pointer adalah variable yang berisi alamat memory sebagai nilainya dan berbeda dengan variable biasa yang berisi nilai tertentu. Dengan kata lain, pointer berisi alamat dari variable yang mempunyai nilai tertentu.
Setiap variable di bahasa C memiliki nama dan nilai tersendiri serta address / alamat yang menyimpan nilai tersebut. Pointer berperan sebagai variable yang menyimpan alamat memory tersebut.
Deklarasi penggunaan pointer dapat dilakukan dengan meletakkan tanda * sebelum tipe data, seperti berikut :
Array adalah sekumpulan variabel yang memiliki tipe data yang sama dan dinyatakan dengan nama yang sama. Array merupakan konsep yang penting dalam pemrograman, karna array memungkinkan untuk menyimpan data maupun referensi objek dalam jumlah banyak dan terindeks. Setiap jenis data dapat memiliki lebih dari 1 dimensi array. Saat mendeklarasikan char dan tidak menggunakan pointer, harus di tuliskan arraynya.
Deklarasi penggunaan array dapat dilakukan dengan menggunakan tanda [ x ] dengan x sebagai jumlah array yang ingin dibuat, seperti :
- Data Structure
Structure atau struct adalah kumpulan dari beberapa variabel dengan beragam tipe data yang dibungkus dalam satu varabel. Jadi dalam struct, kita dapan mendeklarasikan berbagai tipe data didalamnya. Penggunaannya dapat dilakukan dengan :
Beberapa tipe dari data structures :
A. Array : Sekumpulan variable yang memiliki tipe data sama.
B. Linked List : Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence.
Representasi sebuah linked list dapat digambarkan melalui gambar di bawah ini:
Sebuah linked list yang hanya memiliki 1 penghubung ke node lain disebut sebagai single linked list.
Di dalam sebuah linked list, ada 1 pointer yang menjadi gambaran besar, yakni pointer HEAD yang menunjuk pada node pertama di dalam linked list itu sendiri.
Sebuah linked list dikatakan kosong apabila isi pointer head adalah NULL.
Beberapa operasi yang bisa dilakukan dalam linked list :
- Insert = Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
- Konstruktor = Fungsi ini membuat sebuah linked list yang baru dan masih kosong.
- IsEmpty = Fungsi ini menentukan apakah linked list kosong atau tidak.
- Find First = Fungsi ini mencari elemen pert ama dari linked list
- Find Next = Fungsi ini mencari elemen sesudah elemen yang ditunjuk now.
- Retrieve = Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
- Update = Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.
Ada beberapa jenis linked list :
1. Single Linked List / Singly Linked List : Sebuah linked list yang hanya memiliki 1 penghubung ke node lain disebut sebagai single linked list.
2. Circular Single Linked List adalah suatu linked list yang tidak memiliki nilai nil/NULL untuk medan sambungannya. Penciptaan adalah memberikan nilai nil terhadap variabel pointer awal dan variabel pointer akhir.
3. Double Linked List / Doubly Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list.
C. Stack
Sumber : wikipedia
Stack biasa disebut sebagai LIFO (Last In First Out), jadi data yang terakhir masuk akan di pop/ keluar duluan. Sebagai contoh seperti saat kita mencuci piring dan terdapat tumpukan piring, maka kita akan mengambilnya dari yang paling atas dahulu secara berurutan. Kurang lebih cara kerja stack seperti itu.
Dalam stack umumnya terdapat 3 proses operasi yang dilakukan :
a. push (x) : menumpuk item x diatas stack.
b. pop( ) : menghapus / mengambil data paling atas.
c. top ( ) : melihat item / value data paling atas pada stack.
a. push (x) : menumpuk item x diatas stack.
b. pop( ) : menghapus / mengambil data paling atas.
c. top ( ) : melihat item / value data paling atas pada stack.
Sumber : wikipediaInfix, Prefix, dan Postfix notation.
Operasi Infix : opd opr opd, ct : 4 * 10
Operasi Prefix : opr opd opd, ct : * 4 10
Operasi Postfix : opd opd opr, ct : 4 10 *
Operasi Prefix : opr opd opd, ct : * 4 10
Operasi Postfix : opd opd opr, ct : 4 10 *
Ketiga operasi ini digunakan pada masa lalu karena computer dimasa lalu tidak dapat menghitung / mendeteksi tanda kurung ( ), maka infix harus diubah ke prefix atau postfix lalu dilakukan pengecekan satu persatu. Hal ini dilakukan untuk mempercepat kerja computer dari O^n2 menjadi O^n saja.
Contoh :
Infix = ( 1 + 3 ) / ( 100 * 5) ^ 30
Dalam mengubah infix menjadi prefix ataupun postfix harus dilakukan secara urut menurut tingkatan / hirarki yang paling tinggi.
Prefix :
( 1 + 3 ) / ( 100 * 5) ^ 30
( 1 + 3 ) dan ( 100 * 5 ) memiliki tingkat yang sama maka kerjakan dari yang kiri dahulu :
ó + 1 3 / ( 100 * 5 ) ^ 30
ó + 1 3 / ( * 5 100 ) ^ 30
ó ( + 1 3 ) / ^ * 5 100 30
ó / + 1 3 ^ * 5 100 30
hasil ubah ini akan dijadikan string dan dilakukan pengecekan dari kanan.
( 1 + 3 ) dan ( 100 * 5 ) memiliki tingkat yang sama maka kerjakan dari yang kiri dahulu :
ó + 1 3 / ( 100 * 5 ) ^ 30
ó + 1 3 / ( * 5 100 ) ^ 30
ó ( + 1 3 ) / ^ * 5 100 30
ó / + 1 3 ^ * 5 100 30
hasil ubah ini akan dijadikan string dan dilakukan pengecekan dari kanan.
Postfix :
( 1 + 3 ) / ( 100 * 5) ^ 30
ó 1 3 + / ( 100 5 * ) ^ 30
ó 1 3 + / 100 5 * 30 ^
ó 1 3 + 100 5 * 30 ^ /
hasil ubah ini akan dijadikan string dan dilakukan pengecekan dari kiri.
ó 1 3 + / ( 100 5 * ) ^ 30
ó 1 3 + / 100 5 * 30 ^
ó 1 3 + 100 5 * 30 ^ /
hasil ubah ini akan dijadikan string dan dilakukan pengecekan dari kiri.
D. Queue
Queue biasa disebut sebagai FIFO (First In First Out), jadi data yang masuk pertama akan di pop/ keluarkan dahulu. Sebagai contoh seperti saat kita mengantri, tentu saja orang paling depan akan dilayani / dapat menggunakan fasilitas dahulu. Kurang lebih ara kerja Queue seperti itu.
Dalam queue umumnya terdapat 3 proses operasi yang dilakukan :
a. push(x) : menambah antrian data pada queue.
b. pop( ) : menghapus / mengambil data paling depan.
C. first( ) : melihat data paling depan
a. push(x) : menambah antrian data pada queue.
b. pop( ) : menghapus / mengambil data paling depan.
C. first( ) : melihat data paling depan
Queue memiliki kekurangan, yaitu jika head telah mencapai batas array (head sudah sama dengan tail di array terakhir) karena head akan terus maju mendekati tail saat dilakukan proses pop( ). Maka dari itu, terdapat Circular Queue dimana kita dapat menukar index L dan R dengan men-set R menjadi 0 dan sama juga L.
Terdapat pula jenis queue berupa Deques (Double Ended Queue) dimana data dapat di push ke kanan atau kekiri.
- Input restricted deque : push dibatasi (1 tempat)
- Output restricted deque : pop dibatasi (1 tempat)
- Input restricted deque : push dibatasi (1 tempat)
- Output restricted deque : pop dibatasi (1 tempat)
E. Binary Tree : adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.
Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis. Tree bias didefinisikan sebagai kumpulan simpul node dengan satu elemen khusus yang disebut Root dan dnode lainnya.
Ada beberapa istilah dalam tree, yaitu sbb :
1. Parent : Node yang berada 1 level diatas suatu node
2. Child : Node yang berada 1 level dibawah suatu node
3. Sibling : Node yang memiliki parent sama
4. Root : Node khusus yang tidak memiliki node diatasnya
5. Degree : Banyaknya child yang dimiliki oleh suatu node
DFS dan BFS
DFS (Depth First Search) biasa digunakan dalam stack, dimana search pada struktur graf / pohon yang dilakukan berdasarkan kedalamannya.
node yang dilewati : A -> C -> B -> E -> D
BFS (Breadth First Search) biasa digunakan dalam queue, diamana search pada struktur graf / pohon yang dilakukan secara melebar.
node yang dilewati : A-> B -> C -> D -> E
HASH TABLE
Hashing adalah teknik dalam struktur data, dimana teknik ini digunakan untuk menyimpan dan mengambil / mencari kata kunci dengan cepat dan efisien. Dalam hashing, string akan ditransformasikan menjadi sebuah kunci yang mewakili string aslinya. Hashing digunakan untuk mengindeks dan menemukan suatu value dengan kata kunci yang lebih pendek. Hashing dilakukan untuk menyimpan data, mencari data, menambah data, dan menghapus data dengan lebih efisien.
Hash Table adalah sebuah struktur data yang terdiri atas table dan fungsi yang digunakan untuk menyimpan / menaruh key value yang unik untuk setiap record (baris) menjadi angka (hash).
Contoh simplenya :
arr[ ]
|
value
|
0
|
algo
|
1
|
bahaha
|
2
|
cat
|
3
|
NULL
|
4
|
NULL
|
5
|
fly
|
6
|
go
|
…
| |
25
|
zebra
|
algo terletak pada arr[0] karena dimulai dengan huruf ‘a’, dimana pemetaan array dimulai dari 0 untuk abjad ‘a’, 1 untuk abjad ‘b’, dst hinggal 25 untuk ‘z’
ada beberapa cara untuk melakukan hash pada sebuah sebuah string, yaitu :
1. Mid-square -> teknik hashing dengan mengkuadratkan value dari string, kemudian diambik digit tengahnya dan dijadikan sebagai key value. Namun, dalam teknik ini ada batasannya, yaitu saat value yang dikuadratkan memiliki 6 digit, maka saat dikuadratkan akan mencapai 12 digit. Tentu saja ini akan mengakibatkan overflow pada int. Hal ini harus diurus, seperti dengan mengganti int menjadi long. Cara ini cukup efisien karena kemungkinan key value sama sangatlah rendah.
2. Divison (paling sering digunakan) -> teknik hashing dengan memodulo nilai asli dengan jumlah lokasi memori yang tersedia. Rumusnya secara umum adalah h(k) = k mod m, dimana k merupakan key nya dan m merupakan jumlah lokasi memori yang tersedia pada array. Metode ini sering kali menghasilkan nilai unik yang sama, sehingga diperlukan mekanisme khusus untuk menanganinya.
3. Folding -> teknik hashing dengan memagi nilai kunci menjadi beberapa bagian dimana setiap bagiannya memiliki jumlah digit yang sama dengan alamat relative.
4. Digit Extraction -> teknik hashing dengan menentukan digit dari angka yang diberikan sebagai hash address.
5. Rotating hash
BINARY SEARCH TREE
Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. BST juga dikenal sebagai binary tree dengan versi terurut.
Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.
Aturan dalam BST :
1. Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
2. Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Terdapat 3 oeprasi dasar pada BST:
1. searchNode(x) : untuk mencari key x dalam BST
struct node *searchNode(struct node *node, int key)
{
if(node==NULL || node->key==key)
return node;
else if(key<node->key)
return searchNode(node->left, key);
else
return searchNode(node->right, key);
}
2. insertNode(x) : untuk menambahkan node pada tree
struct node *insertNode(struct node *node, int key)
{
if(node==NULL)
{
node=(struct node*)malloc(sizeof(struct node));
node->key=key;
node->left=NULL;
node->right=NULL;
}
else
{
if(key<node->key)
node->left=insertNode(node->left, key);
else if(key>node->key)
node->right=insertNode(node->right, key);
}
return node;
}
3. deleteNode(x) : untuk menghapus node pada tree
struct node *findLeftMostRight(struct node *node)
{
while(node->right!=NULL)
node=node->right;
return node;
}
struct node *delNode(struct node *node, int key)
{
if(node==NULL)
{
printf("Data is not found\n");
return NULL;
}
else
{
if(key<node->key)
node->left=delNode(node->left, key);
else if(key>node->key)
node->right=delNode(node->right, key);
else
{
if(node->left==NULL && node->right==NULL) // jika node yang dihapus merupakan leaf node
{
free(node);
node=NULL;
}
else if(node->right==NULL) //jika hanya punya anak kiri
{
struct node *temp = node;
node=node->left;
free(temp);
}
else if(node->left==NULL) // jika hanya punya anak kanan
{
struct node *temp=node;
node=node->right;
free(temp);
}
else //jika punya 2 anak kanan dan kiri
{
struct node *temp = findLeftMostRight(node->left);
node->key=temp->key;
node->left=delNode(node->left, temp->key);
}
}
return node;
}
}
CODE ASSIGNMENT KASUS MINIMARKET
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
struct Item{
char name[100];
int qty;
int harga;
};
struct Node{
struct Item *item;
Node *prev;
Node *next;
}*head = NULL, *tail = NULL;
void push(struct Item *tempItem){
Node *temp = (Node*) malloc (sizeof(Node));
temp->item = tempItem;
temp->next = temp->prev = NULL;
Node *curr = head;
if(head == NULL){
head = tail = temp;
}
else if(strcmp(head->item->name, tempItem->name) > 0){
temp->next = head;
head->prev = temp;
head = temp;
}
else if(strcmp(tail->item->name, tempItem->name) < 0){
tail->next = temp;
temp->prev = tail;
tail = temp;
}
else{
while(curr->next != NULL){
if(strcmp(curr->next->item->name, tempItem->name) > 0){
curr->next->prev = temp;
temp->next = curr->next;
curr->next = temp;
temp->prev = curr;
break;
}
curr = curr->next;
}
}
printf("\nBarang berhasil dimasukkan ke keranjang\n");
printf("\nTekan enter untuk kembali ke menu\n");
getchar();
}
void addItem(){
srand(time(NULL));
Item *temp = (Item*) malloc (sizeof(Item));
printf("Masukkan nama barang: ");
gets(temp->name);
printf("Masukkan jumlah barang: ");
scanf("%d", &temp->qty); getchar();
temp->harga = rand()*1000%100000;
if(temp->qty < 1){
printf("\nInput salah, barang tidak akan tersimpan\n");
printf("\nTekan enter untuk kembali ke menu\n");
getchar();
return;
}
else push(temp);
}
void deleteItem(char nama[]){
Node *curr = head;
while(curr != NULL){
if(strcmp(curr->item->name, nama) == 0){
if(curr == head){
if(head == tail){
head = tail = NULL;
}
else{
head->next->prev = NULL;
head = head->next;
free(curr);
}
}
else if(curr == tail){
tail->prev->next = NULL;
tail = tail->prev;
free(curr);
}
else{
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
free(curr);
}
printf("\n\"%s\" berhasil dihapuskan\n", nama);
printf("\nTekan enter untuk kembali ke menu");
getchar();
return;
}
curr = curr->next;
}
printf("\nTidak ada barang bernama \"%s\"\n\n", nama);
printf("Tekan enter untuk kembali ke menu");
getchar();
}
void changeQty(char nama[]){
Node *curr = head;
while(curr != NULL){
if(strcmp(curr->item->name, nama) == 0){
int changeQty;
int temp = curr->item->qty;
printf("Tentukan jumlah yang ingin diganti: ");
scanf("%d", &changeQty); getchar();
curr->item->qty = changeQty;
printf("\nJumlah barang berhasil diubah dar %d menjadi %d\n", temp, curr->item->qty);
printf("\nTekan enter untuk kembali ke menu");
getchar();
return;
}
curr = curr->next;
}
printf("\nTidak ada barang bernama \"%s\"\n\n", nama);
printf("Tekan enter untuk kembali ke menu");
getchar();
}
void printCart(){
if(head == NULL){
printf("Kamu belum menyimpan apa-apa\n");
}
else{
Node *print = head;
int i = 1;
printf("-----------------------------------------------------------------------------------\n");
printf("| No | Nama Barang | Harga | Jumlah | Total Harga |\n");
while(print != NULL){//31 11 12 17
long total = print->item->harga * print->item->qty;
printf("| %02d | %-29s | Rp%-9d | %-10d | Rp%-13ld |\n", i, print->item->name, print->item->harga, print->item->qty,
total);
print = print->next;
i++;
}
printf("-----------------------------------------------------------------------------------\n");
}
}
void printMenu(){
printf("Dreammers Market\n");
printf("========================\n");
printf("Keranjang Belanjaan Anda : \n");
printCart();
printf("Menu :\n");
printf("1. Tambah belanjaan\n");
printf("2. Hapus belanjaan\n");
printf("3. Ubah jumlah barang\n");
printf("4. Checkout\n");
printf("Pilih menu [1..4]: ");
}
void checkout(){
system("cls");
printCart();
printf("\nTotal harga yang harus dibayar : 0\n");
printf("\n======== Kindness is Free =========\n");
}
int main(){
int menu;
char nama[100];
do{
system("cls");
printMenu();
scanf("%d", &menu); getchar();
switch(menu){
case 1 :
addItem();
break;
case 2 :
printf("Masukan nama barang yang ingin dihapuskan: ");
gets(nama);
deleteItem(nama);
break;
case 3 :
printf("Masukan nama barang yang ingin diganti jumlahnya: ");
gets(nama);
changeQty(nama);
break;
case 4 :
checkout();
break;
}
}
while(menu != 4);
return 0;
}
Komentar
Posting Komentar