SUMMARY (MID SEMESTERS)
Linked List
Linked list adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi.• struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori. Ada 3 macam linked list, yaitu: -Single Linked list ,Double Linked list, Circular Linked list
1. Single Linked List Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.
Bila dalam single LL pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.
2. Double Linked List Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.
3. Circular Linked List Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :
- Circular Single Linked List
- Circular Double Linked List
STACK
Stack adalah kumpulan suatu elemen dimana hanya elemen yang baru dimasukkan yang dapat diakses atau dilihat. Stack merupakan perintah pengumpulan data secara linear yang menyusun data seperti tumpukan dan bersifat Last In First Out(LIFO) yang berarti data yang terakhir masuk adalah data yang pertama keluar.
Jadi, Stack yaitu sebuah koleksi objek yang menggunakan prinsip LIFO(Last In First Out) dan Stack dapat diimplementasikan sebagai representasi berkait atau kontinyu. Ciri-Ciri Stack diantaranya :
- Elemen TOP/Puncak diketahui
- Penyisipan dan Penghapusan selalu dilakukan di TOP
- LIFO(Last In First Out)
Pemanfaatan Stack yaitu :
- Perhitungan Ekspresi Aritmatitika (posfix)
- Algoritma Backtracking (runut balik)
- Algoritma Rekursif
Operasi Stack yang biasa digunakan diantaranya yaitu :
- Push untuk memasukkan atau menginputkan data
- Pop untuk mengeluarkan data
- IsFull untuk mengetahui jika tumpikan sudah penuh
- IsEmpety untuk mengetahui tumpukan yang kosong, dan
- Clear untuk menghapus seluruh data atau membersihkan data.
QUEUE
Secara Harfiah, queue artinya adalah antrian. Queue adalah salah satu contoh penerapan aplikasi dari pembuatan double linked list yang sering ditemui dalam kehidupan sehari-hari. Queue ialah Struktur Data yang mempunyai sifat FIFO(First In First Out) yang artinya, data yang pertama kali masuk merupakan data yang akan keluar paing awal. Contohnya saat mengantri dalam loket untuk membeli tiket. Istilah Enqueue cukup sering dipakai seseorang ketika masuk antrian. Yang datang terlebih pertama, maka akan dilayani terlebih dahulu. Dan istilah untuk seseorang keluar dari antrian adalah Dequeue.
Hashing
Hash atau Hashing berarti memenggal dan kemudian menggabungkan. Hash menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Hash merupakan suatu metode yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data dan penghapusan data dapat dilakukan dengan cepat.
Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.
Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.
Fungsi Hash adalah suatu fungsi yang mengubah key menjadi alamat dalam tabel. Fungsi Hash memetakan sebuah key ke suatu alamat dalam tabel. Idealnya, key-key yang berbeda seharusnya dipetakan ke alamat-alamat yang berbeda juga.
Pada kenyataannya, tidak ada fungsi Hash yang sempurna. Kemungkinan besar yang terjadi adalah dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah diperlukan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).
Pada kenyataannya, tidak ada fungsi Hash yang sempurna. Kemungkinan besar yang terjadi adalah dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah diperlukan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).
ada dua tipe Collision:
- Linear Probing: mencari spot/tempat kosong yang masih satu baris, lalu menaruh string di tempat kosong tersebut
- Chaining: menaruh string di slot yang telah disediakan di chained list (linked list)
Binary Tree
Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many).
Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul).
Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap.
Konsep dalam tree:
- Binary tree adalah rooted tree yang yang setiap nodenya hanya memiliki maksimal 2 anak
- 2 anak tersebut disebut anak kiri dan anak kanan
- node yang tidak mempunyai anak disebut daun (leaf)
BST memiliki ciri-ciri sebagai berikut:
- Setiap node mempunyai value dan tidak ada value yang double
- value yang ada di kiri tree lebih kecil dari rootnya
- value yang ada di kanan tree lebih besar dari rootnya
- kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )
BINARY SEARCH TREE OPERATIONS
- Searching: Mencari elemen secara spesifik di binary search tree
- Insert: Menambahkan elemen baru ke binary search tree di lokasi yang tepat sehingga properti binary search tree tidak bisa mengakses.
- Delete: Menghapus beberapa node tertentu dari binary search tree. Namun, pada berbagai kasus dalam operasi delete tergantung pada jumlah anak, serta simpul yang dimilikinya.
--------------------------------------------------------------------------------------------------------------------------
SOURCE CODE
MINIMARKET CASHIER
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
struct data{
char product[100];
int qty;
struct data *next;
struct data *prev;
}*head,*tail,*curr;
void PUSH(char product[100],int qty)
{
curr = (struct data*) malloc (sizeof(struct data));
curr -> qty = qty;
strcpy(curr->product,product);
if (head == NULL){
head = tail = curr;
}
else if (strcmp(curr -> product, head -> product)<0){
curr -> next = head;
head -> prev = curr;
head = curr;;
}
else if (strcmp(curr->product,tail-> product)>0){
tail->next=curr;
curr->prev=tail;
tail=curr;
}
else {
// kondisi angka sudah terurut
data *temp = head;
while(strcmp(temp -> next -> product, curr -> product)<0){
temp = temp -> next;
}
curr -> next = temp -> next;
temp -> next -> prev = curr;
temp -> next = curr;
curr -> prev = temp;
}
}
void input(){
int len =0;
char tempproduct[100];
int tempqty;
do{
printf("Masukkan nama product: ");
gets(tempproduct);
len = strlen(tempproduct);
}while(len < 1 );
do{
printf("Masukkan Quantity : ");
scanf("%d",&tempqty);getchar();
}while(tempqty < 1 );
printf("\n");
PUSH(tempproduct,tempqty);
}
void POP(char del[]){
struct data *curr = head;
while(curr!=NULL){
if(strcmp(del, curr->product) == 0){
if (curr==head){//popdepan
if (head == tail){
head = tail = NULL;
printf ("\nSuccess to delete Product \"%s\" from Market list. \n", curr);
free(curr);
return;
}
else {
head = head -> next;
head->prev = NULL;
printf ("\nSuccess to delete Product \"%s\" from Market list. \n", curr);
free(curr);
return;
}
}
else if (curr==tail){//popbelakang
tail = tail->prev;
tail->next = NULL;
printf ("\nSuccess to delete Product \"%s\" from Market list. \n", curr);
free(curr);
return;
}
else{//ditengah-tengah
// curr->prev->next = curr->next;
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
printf ("\nSuccess to delete Product \"%s\" from Market list. \n", curr);
free(curr);
return;
}
}
curr = curr->next;
}
printf("File not found...\n");
}
void update(char edit []){
if(head == NULL){
printf("\nProduct Is Empty !");
}
else{
POP(edit);
char updateProd[100];
int updateQty;
printf("Input new Product: "); getchar();
gets(updateProd);
printf("Input new Qty: ");
scanf("%d",&updateQty);
PUSH(updateProd,updateQty);
printf("\nUpdate Successfull !\n");
}
}
void cetak(){
curr = head;
int i = 1;
printf("Minimarket List\n");
printf("-------------------------------------------\n");
printf("No| Nama Produk | QTY |\n");
if(curr == NULL){
printf(" Product is Empty !\n");
}else {
while (curr != NULL) {
printf("%d.|%10s | %d |\n", i,curr->product, curr->qty);
curr = curr -> next;
i++;
}
}
}
int main(){
struct data barang[100];
int pilih;
char del [100];
char updated [100];
do{
printf("1. Insert product\n");
printf("2. View product\n");
printf("3. Edit product\n");
printf("4. Delete product\n");
printf("5. Exit\n");
do{
printf("Masukkan Pilihan: ");
scanf("%d", &pilih);getchar();
}while(pilih < 1 || pilih > 5);
if(pilih == 1){
input();
}else
if (pilih ==2){
cetak();
}else
if(pilih == 3){
cetak();
printf("Select product to Edit (name): ");
scanf("%[^\n]", updated);
update(updated); getchar();fflush(stdin);
}else
if(pilih == 4){
cetak();
printf("Select Product to Delete (name): ");
scanf("%[^\n]", del);
POP(del);
}
}while(pilih != 5);
srand(time(NULL));
printf("Total = Rp. %d.000,-", rand() % 1000);
printf("\n~ ~ ~ ~ ~ KINDNESS IS FREE :) ~ ~ ~ ~ ~ \n");
return 0;
}
