Data Structure Summary
Linked List
Adalah bentuk
implementasi dari struktur data yang paling sederhana. Seperti yang dijelaskan
sebelumnya dalam konsep struktur data. Terdapat beberapa jenis Linked List
·
Single Linked List
Salah satu keuntungan
dari Linked List dibandingkan dengan Array adalah size dari Linked List akan
bertambah hanya ketika kita membutuhkan slot tersebut, berbeda dengan array
yang mereserve tempat, kemudian tempat tersebut akan menjadi terhambur jika
tidak terpakai.
Dalam pembelajaran
struktur data, kita akan lebih sering mengenal dengan istilah :
o Push untuk menambah data.
Single Linked List dan
Circular Single Linked List
Tahapan awal dalam
pembuatan Single Linked List dan Circular Single Linked List :
 |
| Pembuatan Node dan PushHead |
Fungsi *next adalah sebagai penghubung antara satu
data dengan data yang lain.
*head dan *tail sebagai penanda awal dan akhir sebuah
data struktur.
IF pertama pada pushHead adalah kondisi ketika belum
ada data dalam data struktur, maka diinisialisasikan pembuatan Node dengan head
sama dengan tail.
ELSE menandakan adanya penempatan data baru disebelah
head(data lama) kemudian data yang baru menjadi head baru.
PopHead dan Penggunaan fungsi push dan pop pada main
Untuk Pop sendiri, (dalam kasus ini Pop Head), data
temp diset pada head, jika tidak ada data, maka tidak ada yang perlu dihapus,
jika data hanya satu (pada kondisi 2) head sama tail bisa di NULL kan, kemudian
free(fungsi untuk melepaskan memory yang tidak terpakai lagi) data temp.
Untuk kondisi terakhir, head harus dipindahkan ke data
selanjutnya (diamankan), kemudian baru free data temp.
Untuk Circular, tambahkan satu fungsi yang menghubungkan data awal dan terakhir, kemudian dipanggil terakhir dalam main.
Double Linked List dan Circular Double Linked List
Single Linked List dan
Double Linked List mempunyai struktur yang hampir sama, perbedaannya hanyalah
dalam penambahan pointer prev, yang bertujuan untuk menghubungkan satu data
dengan data sebelumnya.
Pointer yang dibutuhkan pada Linked List
1. Pointer Awal (*head)
Pointer Awal ini berfungsi untuk menunjuk kepada data
yang terakhir kali dimasukkan dalam suatu Linked List, untuk penamaan secara
umum menggunakan nama head (untuk memudahkan).
Pointer Awal ini dapat digunakan untuk mengecek
kondisi apakah suatu Linked List sudah terisi atau belum, sebagai pacuan dalam
PushHead, PopHead.
2. Pointer Akhir (*tail)
Pointer Akhir ini berfungsi untuk menunjuk kepada data
yang pertama kali dimasukkan dalam suatu Linked List, untuk penamaan secara
umum menggunakan nama tail.
Pointer Akhir ini dapat digunakan untuk mengecek
apakah suatu Linked List sudah terisi atau belum, dapat juga digunakan sebagai
pacuan dalam PushTail, PopHead, juga dapat menandakan bahwa data yang ditunjuk
merupakan data yang terakhir.
3. Pointer untuk Menunjuk Data Lainnya (*next,
*prev(optional))
Pointer ini memiliki fungsi yang sangat krusial, yaitu untuk menunjuk data selajutnya, bila tidak ada pointer ini, data dalam Linked List tidak dapat saling terhubung
Hash table
Tapi karena ada kemungkinan kalo misalnya setelah kita generate index, kita mendapat kan index yang sudah pernah kita pakai sebelumnya, maka akan terjadi tubrukan data, sehingga jika kita tetap masukkan data baru ke index tersebut, data sebelumnya yang ada pada index yang sama akan teroverwrite, sehingga akan hilang.
Jadi untuk mengatasi hal
tersebut terjadi, ada namanya linear probing dan chaining :
1.
Linear Probing
Cara ini dilakukan pada saat menemukan index yang sama, kita mencari index setelahnya yang masih belum terpakai(kosong), dengan looping, kita tambah-tambah index nya dengan 1 sambil mengecek apakah isi dari array pada index tersebut sudah terisi apa kosong, jika kosong maka masukkan data ke index tersebut, jika sudah terisi maka lanjut looping dan tambah-tambah 1 lagi hingga menemukan yang kosong.
2.
Chaining
Cara ini dilakukan pada saat menemukan index yang sama setelah itu menjadikan setiap array dalam hash table menjadi dynamic array, sehingga data yang pertama masuk menjadi headnya setelah itu jika ada data yang masuk lagi akan menjadi nextnya, dan seterusnya tanpa ada batas
Binary Tree
Binary Tree adalah tipe data struktur yang bentuknya
seperti pohon, dimana ada satu data yang menjadi Root. Berbeda dengan data
structure biasa yang menggunakan Head sebagai data pacuan. Binary Tree
menggunakan data root sebagai data pacuannya.
Disebut sebagai Binary Tree karena data structure ini
memiliki dua cabang, yaitu left dan right. Dalam memasukkan data dalam binary
tree, biasanya, data yang memiliki value lebih kecil dari root, akan diletakkan
di cabang kiri, sedangkan data yang memiliki value lebih besar dari root akan
diletakkan di cabang kanan.
Contoh Binary Tree
Binary Search Tree
Binary Search Tree atau BST adalah
salah satu Data Structure yang memiliki atribut yang sama dengan Binary Tree,
namun memiliki susunan data yang lebih terstruktur, data yang masuk otomatis
telah dimasukkan secara teratur, sebagai contoh:
Ciri ciri Binary Search Tree:
- Cabang bagian kiri memiliki nilai lebih kecil daripada root
- Cabang bagian kanan memiliki nilai lebih besar daripada root
- Setiap cabang hanya dapat memiliki 2 anak
Search
Insert
Deletion
Berikut adalah hasil kodingan untuk program Dreamers
Market :
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node{
char name[105];
int qty;
int price;
node *next, *prev;
} *head, *tail;
node* createNode (char *name, int qty, int price){
node *temp = (node*)malloc(sizeof(node));
strcpy(temp->name, name);
temp->qty = qty;
temp->price = price;
temp->prev = temp->next = NULL;
return temp;
}
void pushHead (char *name, int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else {
node *temp = createNode(name, qty, price);
temp->next = head;
head->prev = temp;
head = temp;
}
}
void pushTail (char *name, int qty, int price){
if (!head) pushHead(name, qty,price);
else {
node *temp = createNode(name, qty, price);
temp->prev = tail;
tail->next = temp;
tail = temp;
}
}
void pushMid (char *name, int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else if(strcmp(name, head->name) <= 0) pushHead(name, qty, price);
else if(strcmp(name, tail->name) >= 0) pushTail(name, qty, price);
else {
node *temp = createNode(name, qty, price);
node *curr = head;
while (curr && strcmp(name, curr->name) > 0){
curr = curr->next;
}
temp->prev = curr;
temp->next = curr->next;
curr->next->prev = temp;
curr->next = temp;
}
}
void popHead(){
if (!head){
printf ("There is no list. . .\n");
return;
} if (head == tail){
node *temp = head;
head = tail = NULL;
free (temp);
} else {
node *temp = head;
head = head->next;
head->prev = NULL;
free(temp);
}
}
void popTail(){
if (!head || head == tail){
popHead();
} else {
node *temp = tail;
tail = tail->prev;
tail->next = NULL;
free(temp);
}
}
void popSearch(char *name){
if (!head){
printf ("There is no list. . .\n");
return;
}
if (strcmp(head->name, name) == 0){
printf ("Successfully delete %s from list. . .\n", head->name);
popHead();
}
else if (strcmp(tail->name, name) == 0){
printf ("Successfully delete %s from list. . .\n", tail->name);
popTail();
}
else {
node *temp = head;
node *curr = temp;
while (temp && strcmp(name, temp->name) != 0){
curr = temp;
temp = temp->next;
}
if (!temp){
printf ("Can't find %s on the list. . .\nPlease check if you type the right product.\n", temp->name);
return;
}
printf ("Successfully delete %s from list. . .\n", temp->name);
curr->next = temp->next;
temp->next->prev = curr;
free(temp);
}
}
void view(){
if (!head){
printf ("You haven't input anything.");
} else {
node *temp = head;
int i = 1;
long long int total = 0;
char space[10];
strcpy(space, " ");
printf ("No Name Qty Price Total\n");
while (temp){
long long int tempTotal = temp->price * temp->qty;
printf ("%2d %-30s%3d @Rp. %5d Rp. %7lld\n", i, temp->name, temp->qty, temp->price, tempTotal);
total += tempTotal;
temp = temp->next;
i++;
}
printf (" Total : %-40s Rp. %7lld\n\n\n", space, total);
}
}
void del(){
char name[100];
int len;
view();
if(!head){
return;
}
do {
printf("Input item's name [3..30]: ");
scanf("%[^\n]", name);
getchar();
len = strlen(name);
} while(len < 3 || len > 30);
printf("Deleting item. . .\n");
popSearch(name);
}
void update(){
if (!head){
printf ("You haven't input anything.\n");
return;
}
else {
printf ("Change Quantity\n");
view();
char name[100];
int len;
do {
printf ("Input item's name [3..100]: ");
scanf ("%[^\n]", name);
getchar();
len = strlen(name);
} while (len < 3 || len > 100);
node *temp = head;
while (temp && strcmp(name, temp->name) != 0){
temp = temp->next;
}
if (!temp){
printf ("Can't find %s on the list. . .\nPlease check if you type the right product.\n", temp->name);
return;
}
int qty;
do {
printf ("Item's quantity : ");
scanf ("%d", &qty);
getchar();
if (temp->qty == qty){
printf ("Type another value, this value is same is before. . .\n");
}
} while (temp->qty == qty);
printf ("Successfully change quantity from %d to %d. . .\n", temp->qty, qty);
temp->qty = qty;
}
}
void add(){
char name[105];
int qty;
printf ("Add item\n");
node *temp;
int len;
do {
do {
printf ("Input item's name [3..30]: ");
scanf ("%[^\n]", name);
getchar();
len = strlen(name);
} while (len < 3 || len > 30);
temp = head;
while (temp && strcmp(temp->name, name) != 0){
temp = temp->next;
}
if (temp){
printf ("Name already been included\n");
getchar();
continue;
}
do {
printf ("Input item's quantity [1..100]: ");
scanf ("%d", &qty);
getchar();
} while (qty < 1 || qty > 100);
} while (temp);
int price;
price = rand() % 50 + 1;
price *= 100;
pushMid(name, qty, price);
}
void checkOut(){
if (!head){
printf ("You haven't buy any item, please buy at least one item");
return;
}
else {
printf ("Checkout\n");
view();
printf (" Kindness is Free\n");
puts("");
puts("");
char confirm[100];
do {
printf ("Do you want to checkout all of your items?[Yes | No] : ");
scanf ("%[^\n]", confirm);
getchar();
} while (strcmp(confirm, "Yes") != 0 && strcmp(confirm, "No") != 0);
if (strcmp(confirm, "Yes") == 0){
while (head){
popHead();
}
printf ("All items has been checkout\n");
}
}
}
int main(){
int menu;
do {
system("cls");
printf ("Dreammers Market\n");
printf ("================================\n");
printf (" 1. Input item\n");
printf (" 2. Update Quantity\n");
printf (" 3. Delete item\n");
printf (" 4. Check Out\n");
printf (" 5. Exit\n");
printf ("Choose >> ");
scanf ("%d", &menu);
getchar();
system("cls");
switch(menu){
case 1:
add();
printf ("Successfully add item");
getchar();
break;
case 2:
update();
getchar();
break;
case 3:
del();
getchar();
break;
case 4:
if (!head) menu = 0;
checkOut();
getchar();
break;
case 5:
printf ("Thank you for using this Application");
break;
default:
break;
}
} while (menu!=5);
return 0;
}
