Summary Data Structure

Untuk post kali saya hanya akan meng-review kembali post saya yang sebelum-sebelumnya. Dan pada akhir review akan ada contoh program yang bekerja pada cashier dengan menggunakan Linked List.

SINGLE LINKED LIST

Single Linked-List merupakan Barisan Data yang disambung hanya dengan 1 arah, yaitu next. Jadi anggap kita dari kota B merupakan next dari kota A, jika kita dari kota A pergi ke kota B maka kita tidak dapat kembali lagi ke kota A. Seperti itulah Single Linked-List. Contoh-contoh code saya berikan dalam bahasa C.

Hari ini saya mempelajari hal-hal dibawah ini :
1. Create Node
    Function ini biasanya kita gunakan untuk mengalokasikan memori baru menampung data yang baru. Berikut contoh codenya. (Create Node hanya penamaan saja, kalian boleh ubah nama function sesuka kalian ya.)

#include<stdio.h>
#include<string.h>
#include<stdlib,h>      //Library ini digunakan untuk malloc, bisa juga dengan malloc.h

struct Mahasiswa {
     char nama[21];
     int ID;

     Mahasiswa *next;
} *head, *tail;

void createNode(char *name, int ID) {
 
     Mahasiswa *temp = (Mahasiswa*) malloc (sizeof(Mahasiswa));

     strcpy(temp -&gt; nama, name);
     temp -&gt; ID = ID;

     temp -&gt; next = NULL;
     return temp;
}

2. Push
    Function ini digunakan untuk mendorong data yang baru ke dalam sebuah barisan data maupun menjadi barisan data baru. Push biasanya ada 3 macam, yaitu Push Head, Push Mid, dan Push Tail.
Biasanya Push Mid sudah memasukkan function dari Push Head dan Push Tail. Sekarang saya akan berikan contoh untuk Push Head.

void pushHead(Mahasiswa *newNode) {
 
     if(head == NULL) {
          head = tail = newNode;
    }
    else {
          newNode -&gt; next = head;
          head = newNode;
    }
}

3. Show All
    Untuk membuktikan bahwa sudah masuk semua datanya menjadi barisan data, maka kita harus membuktikannya, berikut contoh kode nya

void showAll() {
 
     Mahasiswa *curr = head;

     while(curr != NULL) {
          printf("%s dan %d\n", curr -&gt; nama, curr -&gt; ID);
     }
}

4. Penggunaannya
    Dari semua penjelasan function di atas saya sudah paham, lalu bagaimana cara menggunakannya?? Nah, akan saya contohkan melalu kode dibawah ini

int main() {

     pushHead(createNode("Joko", 123123123));
     showAll();

     pushHead(createNode("Budi", 789789789));
     showAll();
}

Sekian pembelajaran hari ini mengenai Single Linked List.

CIRCULAR LINKED LIST (SINGLE & DOUBLE)

Pada Single dan Double Linked List kita mempelajari bagaimana data yang satu saling berhubungan dengan data selanjutnya atau sebelumnya. Pada materi hari ini, saya akan menjelaskan Double Circular Linked List, Single dan Double.

Circular Linked List, mirip seperti Linked List. Perbedaannya yaitu pada Data/Node terakhir tidak menunjuk next adalah NULL, tetapi Data/Node terakhir (Tail) menunjuk nextnya adalah Data/Node pertama (Head). Jadi pada Circular Linked List tidak ada pointer yang menunjuk NULL. Lalu apa perbedaannya antara Single dan Double ??


Circular Single Linked List hanya dapat mengakses Data selanjutnya atau disebut next, namun tidak dapat mengakses data sebelumnya. Pada circular, Tail dapat mengkases Head, tapi Head tidak dapat mengakses Tail. Gambar disamping merupakan penggambarannya.

Sedangkan pada Circular Double Linked List, masing-masing Node/Data dapat mengakses data selanjutnya (Next) dan sebelumnya, biasa kita sebut Prev. Pada contoh gambar disamping menunjukkan penggambarannya disertai Insert pada Linked List.


Pada Linked List, selain Insert, ada juga Delete. Insert akan terjadi saat ingin memasukkan data baru ke Linked List tersebut, sedangkan Delete terjadi saat ingin menghapus data yang dinginkan. Insert dan Delete harus memperhatikan apakah data tersebut Head, Tail, hanya Single Node (1 Data saja), atau bukan Head bukan Tail. Sekian penjelasan saya tentang Circular Linked List, sekian Terima Kasih.

HASHING & HASHTABLE

Hashing merupakan Data Structures yang menggunakan function yang biasa disebut Hash Function, Hashing digunakan karena dapat mengakses alamat lebih cepat dengan di tandai menggunakan key.

Contoh Gambar :

Gambar disamping salah satu contoh hashing dengan function x % 10. Jika salah satu value dari list disamping 19, maka hashing akan menyimpan value tersebut di Hash Table ke 9.

Lalu bagaimana dengan String?? Akan dicontohkan dibawah ini.



Yang pertama kita buat terlebih dahulu struct atau tables yang nanti akan menampung value. Seperti Linked List, disini juga ada Head dan Tail.

struct Node{
char name[100];
char age[100];
char key[205];

Node *next;
} *tableHead, *tableTail;

lalu ada Create Node, seperti Linked List, function ini menambah data baru dengan memesan memori untuk si data baru ini.

Node *createNode(char name[100], char age[100]){
Node *temp = (Node *)malloc(sizeof(Node));
strcpy(temp->name, name);
strcpy(temp->age, age);
strcpy(temp->nim, "1");
sprintf(temp->key, "%s%s", temp->name, temp->age);

temp->next = NULL;
return temp;
}

Apa yang dimaksud bagian sprintf itu?? Itu merupakan bagian kita membuat key untuk string, untuk formatnya yaitu sprintf(tujuan, apa yang ingin dimasukkan). Contoh untuk bagian tersebut yaitu : Misalkan temp -> name = "Alpha" dan temp -> age = 10 maka hasil di temp -> key = Alpha10.

Function utama kita pada pembahasan kali ini yaitu Hash Function, sebagai berikut :

int hashFunction(char key[205]){
int len = strlen(key);
int total = 0;
for(int i=0;i<len;i++){
total += key[i]*i;
total %= 100;
}
return total;
}

Apa maksudnya diatas ini?? Nah, function di atas ini saya contohkan dengan menggunakan ASCI dari String untuk mencari value di Hash Table atau disebut Hash Index nya. Misalkan pada String "Alpha10", jika kita ikuti function di atas, maka total awal = 0, lalu ditambahkan ASCI dari "A" yaitu  65 dikali loopingannya yaitu 0. Maka value "total" di loopingan ke-0 yaitu 0, pada loopingan ke-1, mak value "total" sebelumnya yaitu 0 ditambah dengan ASCI "l" yaitu 108 dikali 1, maka hasilnya yaitu 108, dan dimodulo 100 menjadi 8, dst sampai key habis.

Untuk peletakan nya pada Hash Table, saya contohkan dengan Push Tail

void pushTail(int hashIndex, Node *newNode){
if(tableHead[hashIndex] == NULL){
tableHead[hashIndex] = tableTail[hashIndex] = newNode;
}else{
tableTail[hashIndex]->next = newNode;
tableTail[hashIndex] = newNode;
}
}

void insert(Node *newNode){
int hashIndex = hashFunction(newNode->key);
pushTail(hashIndex, newNode);
}

Berikut merupakan cara memasukkan data tersebut ke Table, dengan mencari Hash Function dengan Hash Index.

BINARY TREE

Dalam Tree normal, setiap node boleh memliki berapapun jumlah anak. Binary Tree merupakan tree spesial dalam data structure dimana setiap node dengan anak maksimum 2, anak kiri dan anak kanan.

Disamping merupakan contoh gambar dari Binary Tree dengan anak 0, 1, dan 2.

Binary Tree memliki beberapa jenis, yaitu Strictly Binary Tree dan Complete Binary Tree.







1. Strictly Binary Tree

Dalam Binary Tree, setiap node boleh memliki maksimum 2 anak, Namun dalam Strictly Binary Tree, setiap node harus memiliki 2 anak atau tidak memliki anak sama sekali, artinya setiap internal node harus memliki tepat 2 anak. Biasanya Strictly Binary Tree bisa juga disebut Full Binary Tree atau Proper Tree atau 2-Tree, dan digunakan untuk mewakili ekspresi matematik.

2. Compete Binary Tree

Dalam Complete Binary Tree, semua nodes harus memiliki 2 anak dan setiap level Complete Binary Tree harus ada nodes dengan jumlah 2 pangkat level. Jadi misalkan pada level 3 harus ada 8 nodes, karena 2 pangkat 3 = 8.

Sekian teori-teori mengenai Binary Tree dari saya, terima kasih.

BINARY SEARCH TREE

Saya akan membagikan tentang Binary Search Tree, apa bedanya dengan Binary Tree biasa?? Nah pada pemrograman Binary Tree biasa, kita hanya perlu menginput value dari node tersebut dimanapun. Pada Binary Search Tree (BST) value yang kita input kan akan dilihat dari lebih kecil atau lebih besar dari node utamanya dan posisinya pun bergantung dari lebih kecil lebih besar tersebut. Nah kita mulai saja contoh code nya ya

Seperti biasa kita membuat struct nya terlebih dahulu,

struct Tree {

char name[21];

int age;

Tree *left, *right;

} *root;

Setelah itu kita membuat fungsi untuk mengalokasikan memori baru,

Tree *createTree(char *name, int age) {

Tree *temp = (Tree*) malloc (sizeof(Tree));

strcpy(temp -> name, name);

temp -> age = age;

temp -> left = temp -> right = NULL;

return temp;

} 

nah setelah kita memiliki objek nya dan fungsi untuk mengalokasikan memorinya, kita harus membuat fungsi dimana dia melihat value dari node baru tersebut lebih kecil atau lebih besar, serta kosong atau tidak node yang akan ditempati,

Tree *insertRoot(Tree *root, Tree *newTree) {

if(!root) return newTree;

else if(newTree -> age < root -> age) root -> left = insertRoot(root -> left, newTree);

else root -> right = insertRoot(root -> right, newTree);

}

lalu kita coba sekarang memasukan nama dan umur pada main kita,

int main() {

root = insertRoot(root, createTree("Budi", 18));

root = insertRoot(root, createTree("Setiawan", 21));

return 0;

}

nah setelah dimasukkan seperti itu kita belum bisa melihat hasil nya betul atau salah, kita harus membuat fungsi untuk mencetak hasilnya tersebut, 

void printInOrder(Tree *root) {

if(root) {

printInOrder(root -> left);

puts("+-------------------+");

printf("| Name : %-10s |\n", root -> name);

printf("| Age  : %-10d |\n", root -> age);

puts("+-------------------+");

printInOrder(root -> right);

}

}

nah kita modif sedikit pada main tadi,

int main() {

root = insertRoot(root, createTree("Budi", 18));

root = insertRoot(root, createTree("Setiawan", 21));

printInOrder(root);

return 0;

}

nah sudah selesai untuk Insert, dan Print kita. Sekarang gimana jika kita ingin delete node tersebut?? Kita harus buat membuat fungsi untuk meng-delete, fungsi dibawah ini saya delete dengan mencari umur yaa,

Tree *removeRoot(Tree *root, int age) {

if(!root) return root;

else if(age < root -> age) root -> left = removeRoot(root -> left, age);

else if(age > root -> age) root -> right = removeRoot(root -> right, age);

else {

//Kalo dia punya 1 anak atau ga punya anak

if(root -> left == NULL || root -> right == NULL) {

Tree *temp = root -> left != NULL ? root -> left : root -> right;

//Kalo punya 1 anak

if(temp) {

*root = *temp;

} 

//Kalo tak punya anak

else {

temp = root;

root = NULL;

}

free(temp);

}

//Kalo dia punya 2 anak

else {

Tree *temp = root -> left;

while(temp -> right)

temp = temp -> right;

root -> age = temp -> age;

strcpy(root -> name, temp -> name);

root -> left = removeRoot(root -> left, temp -> age);

}

return root;

}

}

Nah cukup panjang untuk delete kita yak, sekarang tinggal kita modif lagi main kita,

 int main() {

root = insertRoot(root, createTree("Budi", 18));

root = insertRoot(root, createTree("Setiawan", 21));

printInOrder(root);

root = removeRoot(root, 18);

printInOrder(root);

return 0;

}

nah sudah selesai semua Insert, Delete, dan Print. Sampai sini saja materi yang saya bawakan mengenai Binary Search Tree, selamat mencoba.

TUGAS PROGRAM DENGAN LINKED LIST

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

int customer = 1;

void cls() {

system("cls");
for(int a = 0; a < 30; a++) {
puts("");
}
}

struct Item {
char name[21];
int qty, price;

Item *next, *prev;
} *head, *tail;

Item *createItem(char *name, int qty) {

Item *temp = (Item*) malloc (sizeof(Item));

strcpy(temp -> name, name);
temp -> qty = qty;

srand(time(NULL));
temp -> price = rand() % 9000 + 1000;

temp -> next = temp -> prev = NULL;
return temp;
}

void pushHead(Item *newItem) {

newItem -> next = head;
head -> prev = newItem;
head = newItem;
}

void pushTail(Item *newItem) {

tail -> next = newItem;
newItem -> prev = tail;
tail = newItem;
}

void pushMid(Item *newItem) {

if(!head) {
head = tail = newItem;
}
else if(strcmp(head -> name, newItem -> name) > 0) pushHead(newItem);
else if(strcmp(tail -> name, newItem -> name) < 0) pushTail(newItem);
else {
Item *curr = head;

while(strcmp(curr -> name, newItem -> name) < 0) {
curr = curr -> next;
}

curr -> prev -> next = newItem;
newItem -> prev = curr -> prev;

curr -> prev = newItem;
newItem -> next = curr;
}
}

void popHead() {

if(head == tail) {
head = tail = NULL;
free(head);
}
else {
Item *temp = head;
head = head -> next;
head -> prev = NULL;
free(temp);
}
}

void popTail() {

if(head == tail) {
head = tail = NULL;
free(head);
}
else {
Item *temp = tail;
tail = tail -> prev;
tail -> next = NULL;
free(temp);
}
}

void popSearch(char *name) {

if(strcmp(head -> name, name) == 0) popHead();
else if(strcmp(tail -> name, name) == 0) popTail();
else {
Item *curr = head;

while(strcmp(curr -> name, name) != 0) {
curr = curr -> next;

if(!curr) {
puts("No Item Matched!!\n");
return;
}
}

curr -> prev -> next = curr -> next;
curr -> next -> prev = curr -> prev;
curr -> next = curr -> prev = NULL;
free(curr);
}
puts("Item deleted successfully!!\n");
}

void itemsList() {

Item *curr = head;

puts("======================================");
puts("|              Items List            |");
puts("======================================");
puts("| Name                 | Price | Qty |");
puts("======================================");
if(curr) {
while(curr) {
printf("| %-20s | %-5d | %-3d |\n", curr -> name, curr -> price, curr -> qty);

curr = curr -> next;
}
}
else puts("|            Input items...          |");
puts("======================================\n");
}

void input() {

int qty;
char name[21];

cls();
puts("*[Press 0 to cancel]*");
printf("Item's Name : ");
scanf("%[^\n]", name); getchar();
if(strcmp(name, "0") == 0) return;

do {
printf("Item's Quantity : ");
scanf("%d", &qty); getchar();

if(qty == 0) return;
else if(qty > 0) break;
} while(true);

pushMid(createItem(name, qty));
}

void edit() {

int bener, qty;
char name[21];

if(!head) {
cls();
puts("There's no item yet...\n");
}
else {
Item *curr;
do {
cls();
itemsList();
puts("*[Press 0 to cancel]*");
printf("Input the item's name : ");
scanf("%[^\n]", name); getchar();

if(strcmp(name, "0") == 0) return;

bener = 0;
curr = head;
while(curr) {
if(strcmp(curr -> name, name) == 0) {
bener++;
break;
}
curr = curr -> next;
}

if(bener != 0) break;
else {
puts("No Item Matched!!\n");
system("pause");
}
} while(true);

printf("Input new Quantity : ");
scanf("%d", &qty);

curr -> qty = qty;

puts("Item's quantity changed successfully!!\n");
}
system("pause");
}

void remove() {

char name[21];

cls();
if(!head) {
puts("There's no item yet...\n");
}
else {
itemsList();
puts("*[Press 0 to cancel]*");
printf("Input the item's name : ");
scanf("%[^\n]", name); getchar();
popSearch(name);
}
system("pause");
}

void checkout() {

int total = 0;

cls();
if(!head) {
puts("There's no item to checkout yet...\n");
}
else {
itemsList();

do {
total += (head -> price * head -> qty);
popHead();
} while(head);

printf("TOTAL >> %d\n", total);
puts("Kindness is free ^_^\n");
}
system("pause");
}

int main() {

int choose;

do {
cls();
itemsList();
printf("Customer No. %d\n", customer);
puts("===============");
puts("1. Input");
puts("2. Change Qty");
puts("3. Delete Item");
puts("4. Checkout");
puts("0. Exit");
printf(">> ");
scanf("%d", &choose); getchar();

switch(choose) {
case 1 :
input();
break;
case 2 :
edit();
break;
case 3 :
remove();
break;
case 4 :
checkout();
customer++;
break;
}
} while(choose != 0);

return 0;

}