Linked list dalam bahasa baku Indonesia diartikan sebagai "Seranai berantai".
kelebihan dan kekurangan dalam linked list
Kekurangan
- Diperlukan ruang lebih untuk menempatkan pointer next
- Pencarian dalam linked list relatif lebih lama
Kelebihan
+ Data yang berbeda tipe nya dapat disimpan secara berhubungan
+ Memori dinamis
+ Penambahan dan penghapusan data dilakukan dengan efisien
Komponen linked list
$ Pointer = penunjuk
$ Head = elemen pertama dari linked list
$ Tail = elemen terakhir dari linked list
$ Data = isi dari node (isi dari struct)
$ Node = elemen dalam linked list (struct)
linked list memiliki 3 jenis
1. Single linked list
ciri:
* Hanya memiliki 1 arah ( tidak berbalas ) ke penghubung ke node lain
* Tail akan selalu menunjuk NULL
gambaran:
2. Doubly linked list / double linked list
ciri:
* Setiap node memiliki 2 arah yang menunjuk node sebelum nya dan node selanjut nya.
* Head dan tail akan selalu menunjuk NULL
gambaran :
3. Circular linked list
ciri:
* Tidak memiliki pointer yang menunjuk NULL
juga bersifat double linked list
! note :
*Circular linked list adalah bagian dari single dan double linked list
gambaran:
Single-circular linked list
Double-circular linked list
Operasi:
*Push
Push adalah sebutan untuk operasi insert dalam linked list, push ini
memilikin 3 cara :
@ Push depan = Memasukkan data dari depan
@ Push tengah = Memasukkan data dari tengah
@ Push belakang = Memasukkan data dari belakang
Wajib diperhatikan dalam Push
! Head harus selalu berada paling depan
! Tail harus selalu berada paling belakang
! Bila memasukkan data dari tengah, jangan lupa menggeser belakang nya juga pointer
antara 2 node yang akan di sisipkan node baru.
*Pop
Pop adalah sebutan untuk operasi delete dalam linked list, sama seperti push memiliki cara dari
depan, tengah, dan belakang
Wajib diperhatikan dalam pop
! Head harus ada
! Tail juga harus ada
! Hubungan antara node tidak boleh ada yang terputus
()sytax untuk melepas memory yang terpakai saat linked list()
While(Head){
Head = Head.next;
free(Head.prev);
}
Data Structure session 4
Stack = Tumpukkan
* Konsep
Last In First Out (LIFO), terakhir masuk pertama keluar
* Implementasi
- Perhitungan aritmatika postfix
- Back tracking (Depth First Search / DFS)
- Recursive
- Mengubah decimal menjadi biner
* Operasi
- Push (x) = Memasukkan data / push ke index x
- Pop() = Delete data dari paling atas
- Top() / Peek() = Mengambil (mereturn) nilai paling atas (tail)
Queue = Antrian
* Konsep
First In First Out (FIFO), pertama masuk pertama keluar
* Implementasi
- Sistem antrian
* Queue yang diterapkan dengan array akan memungkinkan bermasalah pada kapasitas. Bila data yang masuk melebihi kapasitas, maka data tidak dapat memasuki queue.
* Circular Queue adalah solusi untuk masalah di atas. Konsep ini mengulang pemasukkan data dari awal sehingga data pertama(Head) akan di timpa dengan data baru
BFS & DFS
* Breadth First Search
Algoritma pencarian data secara melebar dengan mengunjungi semua node yang bertetangga dan dilanjutkan dengan node level selanjut nya, begitu seterus nya hingga habis
* Depth First Search
Berbeda dengan BFS, DFS akan memasuki setiap akar(root) dari tiap node sampai ketemu dengan data yang dicari. Bila tidak bertemu ia akan lanjut ke tetangga nya.
Prefix, Postfix, Infix
* Prefix = Penulisan operasi aritmatika dengan meletakkan semua operator di depan dan operand di belakang nya
contoh = +ab, dibaca a+b
* Postfix = Penulisan operasi aritmatika dengan meletakkan semua operator di belakang dan operand di depan nya
contoh = ab+, dibaca a+b
*Infix = Penulisan operasi aritmatika biasa dan untuk precedence menggunakan kurung buka-tutup
contoh = penulisan notasi matematika biasa
*3 jenis penulisan ini bertujuan untuk mengatur precedence dalam operasi aritmatika pada bahasa pemrograman
*Postfix dan Prefix tidak menggunakan operator kurung buka-tutup sehingga dapat mempercepat komputasi, karena infix yang menggunakan kurung buka-tutup akan menyebabkan komputer mencari kurung buka-tutup terlebih dahulu sebelum memulai perhitungan
*rumus
Pre = opr opd opd
Post = opd opd opr
In = opd opr opd
Contoh soal prefix, postfix, infix
Infix = ((1+3) / (100*5) ^ 30)
Prefix? Postfix?
jawab
Prefix =
+ 1 3
+ 1 3 * 100 5
+ 1 3 ^ * 100 5 30
/ + 1 3 ^ * 100 5 30
Postfix =
1 3 +
1 3 + 100 5 *
1 3 + 100 5 * 30 ^
1 3 + 100 5 * 30 ^ /
Hash Table
* Pengertian
Salah satu struktur data untuk menyimpan data sementara yang terdiri dari sebuah tabel dan fungsi untuk memetakan unique keyword untuk setiap baris (record) menjadi angka (hash) lokasi record tsb. dalam sebuah tabel.
* Keuntungan
- Waktu akses cepat
- Kecepatan pengoperasian insertions, deletions, searching relatif sama
* Kerugian
- Mudah mengalami tabrakan data (Collision)
- Sulit untuk mencetak seluruh data
* Beberapa hal yang perlu diperhatikan untuk membuat hash function
- Table size / ukuran tabel (m)
- Key value / nilai dari data (k)
- Hash index / indeks yang dituju (h)
Contoh
* Fungsi sederhana modulus key value dengan table size:
h = k % m
Tabel size = 13
maka, dengan tabel size dan fungsi tsb. akan didapat
* Operasi
- insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
- find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
- remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
- getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu
Binary Tree
* Pengertian
Sebuah struktur data non-linear yang menggambarkan hubungan bersifat hirarkis antar elemen dan setiap node / simpul memiliki paling banyak 2 anak
* Istilah umum dalam binary tree
- Predecessor : node yang berada diatas node tertentu.
- Successor : node yang berada di bawah node tertentu.
- Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama (Leluhur).
- Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama (Keturunan).
- Parent : predecessor satu level di atas suatu node.
- Child : successor satu level di bawah suatu node.
- Sibling : node-node yang memiliki parent yang sama dengan suatu node.
- Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
- Size : banyaknya node dalam suatu tree.
- Height : banyaknya tingkatan/level dalam suatu tree.
- Root : satu-satunya node khusus dalam tree yang tak punya predecessor.
- Leaf : node-node dalam tree yang tak memiliki turunan.
- Degree : banyaknya child pada suatu node.
* Jenis binary tree
- Perfect binary tree
- Complete binary tree
- Skewed binary tree
Assigment
Buatlah aplikasi dengan syarat:
a. aplikasi dibuat menggunakan linked list.
b. aplikasi dibuat menggunakan double linked list.
c. aplikasi dibuat bisa input barang (nama dan qty), bs edit qty dan bisa menghapus item yang salah.
d. ketika checkout anda akan ditampilkan hasil total dari perhitungan qty (seperti struk minimarket)
e. harga yang tertera random, namun hasil penjumlahan benar (totalnya benar)
f. setelah tahap mau bayar, di bawah tulisan total, tuliskan gratis, “kindness is free”
source: * Pengertian
Salah satu struktur data untuk menyimpan data sementara yang terdiri dari sebuah tabel dan fungsi untuk memetakan unique keyword untuk setiap baris (record) menjadi angka (hash) lokasi record tsb. dalam sebuah tabel.
* Keuntungan
- Waktu akses cepat
- Kecepatan pengoperasian insertions, deletions, searching relatif sama
* Kerugian
- Mudah mengalami tabrakan data (Collision)
- Sulit untuk mencetak seluruh data
* Beberapa hal yang perlu diperhatikan untuk membuat hash function
- Table size / ukuran tabel (m)
- Key value / nilai dari data (k)
- Hash index / indeks yang dituju (h)
Contoh
* Fungsi sederhana modulus key value dengan table size:
h = k % m
Tabel size = 13
maka, dengan tabel size dan fungsi tsb. akan didapat
- insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
- find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
- remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
- getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu
Binary Tree
* Pengertian
Sebuah struktur data non-linear yang menggambarkan hubungan bersifat hirarkis antar elemen dan setiap node / simpul memiliki paling banyak 2 anak
* Istilah umum dalam binary tree
- Predecessor : node yang berada diatas node tertentu.
- Successor : node yang berada di bawah node tertentu.
- Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama (Leluhur).
- Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama (Keturunan).
- Parent : predecessor satu level di atas suatu node.
- Child : successor satu level di bawah suatu node.
- Sibling : node-node yang memiliki parent yang sama dengan suatu node.
- Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
- Size : banyaknya node dalam suatu tree.
- Height : banyaknya tingkatan/level dalam suatu tree.
- Root : satu-satunya node khusus dalam tree yang tak punya predecessor.
- Leaf : node-node dalam tree yang tak memiliki turunan.
- Degree : banyaknya child pada suatu node.
* Jenis binary tree
- Perfect binary tree
- Complete binary tree
- Skewed binary tree
Assigment
Buatlah aplikasi dengan syarat:
a. aplikasi dibuat menggunakan linked list.
b. aplikasi dibuat menggunakan double linked list.
c. aplikasi dibuat bisa input barang (nama dan qty), bs edit qty dan bisa menghapus item yang salah.
d. ketika checkout anda akan ditampilkan hasil total dari perhitungan qty (seperti struk minimarket)
e. harga yang tertera random, namun hasil penjumlahan benar (totalnya benar)
f. setelah tahap mau bayar, di bawah tulisan total, tuliskan gratis, “kindness is free”
Source code in C language
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct data{
char name[101];
int qty;
int price;
struct data *next,*prev;
}*head, *tail, *curr;
void enter(){
puts("\n\nPress enter to continue...");getchar();
}
void add(char name[], int qty, int price){
curr = (struct data*) malloc(sizeof(struct data));
strcpy(curr->name,name);
curr->qty = qty;
curr->price = price;
if(head==NULL)
{
head=tail=curr;
head->prev=tail->next=NULL;
}
else if(strcmp(curr->name,head->name) < 0)
{
curr->next=head;
head->prev=curr;
head=curr;
head->prev=tail->next=NULL;
}
else if(strcmp(curr->name,head->name) > 0)
{
tail->next=curr;
curr->prev=tail;
tail=curr;
head->prev=tail->next=NULL;
}
else
{
struct data *temp=head;
while (strcmp(temp->name,curr->name) <= 0)
{
if(strcmp(temp->name,name) == 0)
{
puts("Can't input the same name");
enter();
return ;
}
temp=temp->next;
}
curr->next=temp->next;
temp->next->prev= curr;
temp->next=curr;
curr->prev=temp;
}
puts("Success !!");
enter();
return;
}
void edit(char name[], int qty){
if(head == NULL){
puts("Emty~~");
enter();
return ;
}
else {
struct data *temp = head;
while(strcmp(temp->name,name) != 0)
{
temp = temp->next;
}
temp->qty=qty;
puts("Success!!");
enter();
return;
}
}
void remove(char name[]){
if(head == NULL){
puts("Emty~~");
enter();
return ;
}
else if(strcmp(head->name,name) == 0 && strcmp(tail->name,name) == 0){
curr=head=tail;
head=tail=head->next;
free(curr);
head->prev=tail->next=NULL;
}
else if(strcmp(head->name,name) == 0)
{
curr=head;
head=head->next;
free(curr);
head->prev=NULL;
}
else if(strcmp(tail->name,name) == 0)
{
curr=tail;
tail=tail->prev;
free(curr);
tail->next=NULL;
}
else
{
struct data *temp=head;
while(strcmp(temp->name,name)!=0)
{
temp=temp->next;
}
puts("belom");
curr=temp->next;
temp->next=curr->next;
curr->next->prev = temp;
head->prev = tail->next = NULL;
free(curr);
puts("free");
}
puts("Success removing");enter();
return;
}
void removeAll()
{
curr=head;
while(curr!=NULL)
{
head=head->next;
free(curr);
curr=head;
}
int i = 1;
while(curr != NULL)
{
printf("|%-4d%-25s%-5d%-10ld%-15ld|\n",i,curr->name,curr->qty,curr->price,curr->price * curr->qty);
curr=curr->next;
i++;
}
}
void Print(){
if(head == NULL){
puts("Emty~~");
enter();
return ;
}
else
{
int i=1;
long total = 0;
curr=head;
puts("=============================================================");
puts("|No. Name Qty Price Total |");
puts("=============================================================");
while(curr != NULL)
{
printf("|%-4d%-25s%-5d%-10ld%-15ld|\n",i,curr->name,curr->qty,curr->price,curr->price * curr->qty);
total+=curr->qty*curr->price;
curr=curr->next;
i++;
}
puts("=============================================================");
printf("|Grand Total %-15d|\n",total);
puts("=============================================================");
return;
}
}
void clss()
{
system("cls");
}
int main()
{
int menu = 0;
do{
clss();
puts("ver 1.5");
puts("Payment cart");
puts("=============");
puts("1. Add item to shopping cart");
puts("2. Edit item in shopping cart");
puts("3. Delete item in shopping cart");
puts("4. Cek out");
printf("Choose >> ");scanf("%d",&menu);getchar();
if(menu == 1)
{
clss();
puts("..Add Cart..");
char name[101];
int qty = 0;
printf("Input item's name : ");scanf("%[^\n]",name);getchar();
do{
printf("Input item's qty : ");scanf("%d",&qty);getchar();
}while(qty < 1);
int price = (rand()%1000000)+1000;
add(name,qty,price);
}
else if(menu == 2)
{
clss();
char name[101];
int qty = 0;
puts("..Edit Cart..");
printf("Input item's name to : ");scanf("%[^\n]",name);getchar();
do{
printf("Input item's qty : ");scanf("%d",&qty);getchar();
}while(qty < 1);
edit(name,qty);
}
else if (menu == 3){
clss();
puts("..Remove cart");
char name[101];
printf("Input item's name : ");scanf("%[^\n]",name);getchar();
remove(name);
}
else if (menu == 4)
{
clss();
puts("..Bill..");
Print();
if(head==NULL)menu=0;
}
}while(menu != 4);
puts("..Kindness is Free..");
removeAll();
}
https://socs.binus.ac.id/2017/03/15/single-linked-list/
https://socs.binus.ac.id/2017/03/15/doubly-linked-list/
https://id.wikipedia.org/wiki/Senarai_berantai
https://docplayer.info/32080128-Kerugian-dan-keuntungan-linked-list.html
https://repository.unikom.ac.id/35731/1/Bab%20VII%20-%20Circular%20Linked%20List.pdf
https://www.geeksforgeeks.org/data-structures/linked-list/
https://www.w3schools.in/wp-content/uploads/2016/09/Data-Structures-Algorithms-Stack.png
https://id.wikipedia.org/wiki/Stack_(struktur_data)
https://socs.binus.ac.id/2018/12/21/stack/
https://www.w3schools.in/data-structures-tutorial/queue/
https://socs.binus.ac.id/2018/12/21/queue/
https://www.mahirkoding.com/struktur-data-queue-dan-implementasinya/
https://piptools.net/algoritma-bfs-breadth-first-search/
http://chandra-mahardika.blogspot.com/2015/10/materi-prefix-infix-dan-postfix.html
https://www.academia.edu/25537608/TABEL_HASH_HASH_TABLE
http://muqoddasrengmadureh.blogspot.com/2013/01/algoritma-dan-struktur-data-hashing.html
http://syazdiayhodian.blogspot.com/2011/06/hashing.html
https://www.slideshare.net/GRADhita/modul-praktikum-11-hashing-table
https://id.wikipedia.org/wiki/Pohon_biner
http://dinda-dinho.blogspot.com/2013/07/pengertian-dan-konsep-binary-tree.html
http://new-funday.blogspot.com/2012/12/struktur-data-tree-dan-penjelasaanya.html
https://saragusti22.wordpress.com/2015/05/04/pengantar-struktur-data-tree-dan-binary-tree/
https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html
Tidak ada komentar:
Posting Komentar