Review Topic Session 1-5
Pointer
Pada materi single linked list dan double linked list hal yang sangat penting adalah pointer. Definsi pointer adalah suatu variabel yang berisi suatu alamat lokasi tertentu.Fungsi pointer adalah sebagai penunjuk alamat lokasi variabel lain. Berikut adalah potongan source code untuk penggunaan pointer sederhana.
1.Single Linked List
Linked list adalah suatu koneksi linear dari data, atau yang lebih umum dikenal sebagai nodes. Dimana setiap node menunjuk node yang lainnya melalui sebuah pointer. Pada umumnya sebuah rangkaian single linked list maupun double linked list diawali dengan head dan diakhiri dengan node yang mengarah ke pointer NULL.
Representasi single linked list dapat dilihat pada gambar di bawah ini :
Pada gambar diatas angka 10 adalah sebagai Head, sesusai dengan definisi head yaitu elemen yang berada pada posisi pertama dalam linked list. Sedangkan 30 adalah sebagai Tail yaitu elemen yang berada pada posisi terakhir.
Operasi-Operasi di Single Linked List
1.Insert
Fungsi ini adalah menambahkan sebuah simpul yang baru ke dalam sebuah linked list
2.Konstrukor
Fungsi ini membuat linked list yang baru dan tidak berisi apapun(kosong)
3.isEmpty
Fungsi ini adalah untuk mengecek isi dari linked list, apakah kosong atau tidak.
4.FindFirst
Fungsi ini digunakan untuk mencari elemen pertama dalam sebuah linked list
5.FindNext
Fungsi ini digunakan untuk mencari elemen yang ditunjuk oleh pointer
6.Retrive
Fungsinya digunakan untuk mengamnil elemen yang ditunjuk, dan dikembalikan ke dalam function
Fungsinya digunakan untuk mengamnil elemen yang ditunjuk, dan dikembalikan ke dalam function
7.Update
Fungsinya mengubah elemen yang ada di dalam linked list atau bisa saja kita sebut mereplace
8.Delete Now
Fungsinya adalah untuk menghapus elemen yang terdapat dalam linked list.
Fungsinya adalah untuk menghapus elemen yang terdapat dalam linked list.
Circular Single Linked List
Circular single linked list adalah single linked list yang pointer nextnya menunjuk pada dirinya sendiri, jikalau di single linked list di elemen terakhir(tail) akan ada pointer next yang menunjuk NULL, tapi jika circular single linked list jikalau sudah di elemen terakhir, dia akan kembali ke dirinya sendiri sehingga berputar,oleh sebab itu disebut circular
Representasi circular single linked list dapat dilihat pada gambar di bawah ini :
2.Double Linked List
Berbeda dengan single linked list dan circular single linked list yang hanya memiliki 1 pointer saja sedangkan double linked list adalah salah satu contoh implementasi linked list dan single linked list, berdasarkan namanya yaitu double, artinya di linked list ini mempunyai 2 penunjuk yaitu kiri dan kanan. Pada umumnya kanan adalah sebagai next dan penunjuk kiri sebagai prev.
Representasi sebuah double linked list dapat dilihat pada gambar di bawah ini :
Operasi-Operasi di Double Linked List
1.Insert Tail
Fungsinya adalah menambahkan sebuah simpul baru di belakang(bagian kanan) dalam sebuah linked list
2.Insert Head
Fungsinya adalah menambahkan sebuah simpul baru di depan(bagian kiri) dalam sebuah linked list
3.Delete Tail
Fungsinya adalah menghapus simpul dari yang paling belakang(kanan), berkebalikan dengan fungsi Insert tail
4.Delete Head
Fungsinya adalah menghapus simpul dari yang paling depan(kiri), yang berkebalikan dengan fungsi insert head
Circular Double Linked List
Circular double linked list memiliki 3 field yaitu :
1.Pointer berikutnya(next)
2.Pointer sebelumnya(prev)
3.Berisi data untuk node
Double Linked List Circular pointer next dan prev nya menunjuk ke dirinya sendiri secara circular.
Representasi sebuah circular double linked list dapat dilihat pada gambar di bawah ini :
Implementasi single linked list dalam bahasa c :
#include <stdio.h>
#include <stdlib.h>
struct data{
int angka;
struct data *next;
}*head=NULL, *tail=NULL;
struct data *createNewNode(int num){
struct data *newNode = (struct data *)malloc(sizeof(struct data));
newNode->angka = num;
newNode->next = NULL;
return newNode;
}
void pushHead(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
}
else {
newNode->next = head;
head = newNode;
}
}
void pushTail(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
head->next = NULL;
}
else {
tail->next = newNode;
tail = newNode;
}
}
void pushMid(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
head->next = NULL;
}
else {
if (head->angka > newNode->angka) pushHead(angka);
else if (tail->angka <= newNode->angka) pushTail(angka);
else {
struct data *temp = head;
while (temp->next->angka < newNode->angka){
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
}
}
void popHead(){
if (head){
struct data *temp = head;
if (head == tail){ // Kalau data tinggal 1
head = tail = NULL;
free(temp);
}
else {
head = head->next;
temp->next = NULL;
}
free(temp);
}
}
void popTail(){
if (head){
struct data *temp = head;
if (head == tail){ // Kalau data tinggal 1
head = tail = NULL;
free(temp);
}
else {
while (temp->next != tail){
temp = temp->next;
}
temp->next = NULL;
free(tail);
tail = temp;
}
}
}
void popMid(int angka){
if (head){
if (angka == head->angka){ // Angka ada di Head
popHead();
}
else if (angka == tail->angka){ // Angka ada di Tail
popTail();
}
else { // Angka bukan di tail atau head
struct data *temp = head;
while (temp->next != NULL && temp->next->angka != angka){
temp = temp->next;
}
if (temp->next == NULL || temp->next->angka != angka ) {
printf("Angka %d tidak ditemukan\n", angka);
return;
}
struct data *temp2 = temp->next;
temp->next = temp2->next;
temp2->next = NULL;
free(temp2);
}
}
}
void cetak(){
if (head){
struct data *temp = head;
while (temp != NULL){
printf("%d", temp->angka);
if (temp != tail) printf("->");
temp = temp->next;
}
}
}
int main(){
pushMid(5);
pushMid(10);
pushMid(7);
pushMid(3);
pushMid(9);
pushMid(22);
cetak();
printf("\n");
popMid(3);
popMid(22);
popMid(9);
popMid(11);
popMid(1);
cetak();
}
Implementasi double Linked list dalam bahasa c :
#include <stdio.h>
#include <stdlib.h>
struct data{
int angka;
struct data *next, *prev;
}*head=NULL, *tail=NULL;
struct data *createNewNode(int num){
struct data *newNode = (struct data *)malloc(sizeof(struct data));
newNode->angka = num;
newNode->next = NULL;
newNode->prev = NULL; // Double Linked List
return newNode;
}
void pushHead(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
}
else {
newNode->next = head;
head->prev = newNode; // Double Linked List
head = newNode;
}
}
void pushTail(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
head->next = NULL;
}
else {
tail->next = newNode;
newNode->prev = tail; // Double Linked List
tail = newNode;
}
}
void pushMid(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
head->next = NULL;
}
else {
if (head->angka > newNode->angka) pushHead(angka);
else if (tail->angka <= newNode->angka) pushTail(angka);
else {
struct data *temp = head;
while (temp->next != NULL && temp->next->angka < newNode->angka){ // Double Linked List
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
newNode->next->prev = newNode; // Double Linked List
newNode->prev = temp; // Double Linked List
}
}
}
void popHead(){
if (head){
struct data *temp = head;
if (head == tail){ // Kalau data tinggal 1
head = tail = NULL;
free(temp);
}
else {
head = head->next;
head->prev = NULL; // Double Linked List
temp->next = NULL;
}
free(temp);
}
}
void popTail(){
if (head){
struct data *temp = tail->prev; // Double Linked List
if (head == tail){ // Kalau data tinggal 1
head = tail = NULL;
free(tail);
}
else {
temp->next = NULL; // Double Linked List
tail->prev = NULL; // Double Linked List
free(tail);
tail = temp;
}
}
}
void popMid(int angka){
if (head){
if (angka == head->angka){ // Angka ada di Head
popHead();
}
else if (angka == tail->angka){ // Angka ada di Tail
popTail();
}
else { // Angka bukan di tail atau head
struct data *temp = head;
while (temp->next != NULL && temp->next->angka != angka){
temp = temp->next;
}
if (temp->next == NULL || temp->next->angka != angka ) {
printf("Angka %d tidak ditemukan\n", angka);
return;
}
struct data *temp2 = temp->next;
temp->next = temp2->next;
temp2->next = NULL;
temp2->prev = NULL;
temp2->next->prev = temp;
free(temp2);
// 4<->5<->8
}
}
}
void cetak(){
if (head){
struct data *temp = head;
while (temp != NULL){
printf("%d", temp->angka);
if (temp != tail) printf("->");
temp = temp->next;
}
}
}
int main(){
pushMid(5);
pushMid(10);
pushMid(7);
pushMid(3);
pushMid(9);
pushMid(22);
cetak();
printf("\n");
popMid(3);
popMid(22);
popMid(9);
}
Session 2
1. Stack
Stack atau tumpukan adalah suatu kumpulan elemen dimana elemen yang baru dimasukkan yang dapat diakses. Sebuah stack biasa di implementasikan menggunakan array atau bisa juga dengan linked list. Sebuah stack biasa menggunakan prinsip Last In First Out (LIFO), yang artinya masuk terakhir pertama. Contoh penerapan prinsip LIFO adalah sebuah kumpulan tumpukan buku yang baru saja dimasukkan ke dalam toko dengan jenis buku yang sama, pasti buku yang paling atas yang terjual terlebih dahulu.
Adapun pemanfaatan stack adalah untuk perhitungan ekspresi aritmetika(postfix),algoritma Backtracking(runut balik) dan algoritma rekursif.
Operasi-Operasi dalam Stack
1.Push : Menambahkan sebuah data baru
2.Pop : Menghapus sebuah data
3.Top : Mengambil data yang paling atas
2.value yang ada di kiri tree lebih kecil dari rootnya
3.value yang ada di kanan tree lebih besar dari rootnya
4.kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )
Aturan main Binary Search Tree :
Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya
Operasi-operasi yang dilakukan pada binary search tree meliputi :
1. Operasi: Insertion BST
Memasukan value (data) baru kedalam BST dengan rekrusif
Bayangkan kita menginsert value x :
Dimulai dari root
jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )
2. Operasi: Delete ( Remove )
akan ada 3 case yang ditemukan ketika ingin menghapus yang perlu diperhatikan :
Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan) atau dengan cari dari right sub-tree anak kiri paling terakhir(leaf) (kanan,kiri)
3. Operasi: Search BST
dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.
Bayangkan kita akan mencari value X.
Memulai Pencarian Dari Root
Jika Root adalah value yang kita cari , maka berhenti
Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan
ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :
PreOrder : Print data, telusur ke kiri, telusur ke kanan
InOrder : Telusur ke kiri, print data, telusur ke kanan
Post Order : Telusur ke kiri, telusur ke kanan, print data
sumber :
https://abdilahrf.github.io/2015/06/pengenalan-binary-search-tree/
http://www.nblognlife.com/2014/12/binary-search-tree-bst-tree-lanjutan.html
http://lang8088.blogspot.com/2015/06/memahami-pengertian-binary-search-tree.html
contoh implementasi binary search tree dalam bahasa c :
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int x;
struct node *left, *right;
}node;
node *createNewNode(int x) {
node *temp = (node *)malloc(sizeof(node));
temp->x = x;
temp->left = temp->right = NULL;
return temp;
}
node *insertNode(node *root, int x) {
if(root == NULL)
{
return createNewNode(x);
}
else
{
if(x < root->x)
{
root->left = insertNode(root->left,x);
}
else if( x > root->x) {
root->right = insertNode(root->right,x);
}
else {
printf("Same data !!!\n");
}
}
return root;
}
node *findminimum(node *temp) {
// root kiri paling kanan || ambil root kanan paling kiri
if(temp->right == NULL)
return temp;
return findminimum(temp->right);
}
int search(node *root, int x) { // x yang dicari
if(root == NULL)
return -1;
if(root->x == x) // target kita
return 1;
else {
if(x < root->x)
{
return search(root->left,x);
}
else if( x > root->x) {
return search(root->right,x);
}
}
return -1;// gak dapaet
}
node *deleteNode(node *root,int x)
{
if(root == NULL) // gadapet.
{
printf("Gaada\n");
return root;
}
else if(x < root->x)
root->left = deleteNode(root->left,x);
else if(x > root->x)
root->right = deleteNode(root->right,x);
else
{
//3 case
//1.leaf
if(root->right == NULL && root->left == NULL)
{
free(root);
root = NULL;
}
else if(root->left == NULL)
{
node *temp = root;
root = root->right;
free(temp);
}
else if(root->right == NULL)
{
node *temp = root;
root = root->left;
free(temp);
}
else //case 3.
{
node *temp = findminimum(root->left);
root->x = temp->x;
root->left = deleteNode(root->left,temp->x);
}
}
return root;
}
void printInorder(node *root) {
if(root == NULL) {
return;
}
printf("%d ",root->x);
printInorder(root->left);
printInorder(root->right);
}
int main() {
node *root = NULL;
root = insertNode(root,16);
root = insertNode(root,25);
root = insertNode(root,14);
root = insertNode(root,17);
root = insertNode(root,18);
printInorder(root);
printf("\n");
root = deleteNode(root,17);
printInorder(root);
}
#include <stdio.h>
#include <stdlib.h>
struct data{
int angka;
struct data *next;
}*head=NULL, *tail=NULL;
struct data *createNewNode(int num){
struct data *newNode = (struct data *)malloc(sizeof(struct data));
newNode->angka = num;
newNode->next = NULL;
return newNode;
}
void pushHead(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
}
else {
newNode->next = head;
head = newNode;
}
}
void pushTail(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
head->next = NULL;
}
else {
tail->next = newNode;
tail = newNode;
}
}
void pushMid(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
head->next = NULL;
}
else {
if (head->angka > newNode->angka) pushHead(angka);
else if (tail->angka <= newNode->angka) pushTail(angka);
else {
struct data *temp = head;
while (temp->next->angka < newNode->angka){
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
}
}
void popHead(){
if (head){
struct data *temp = head;
if (head == tail){ // Kalau data tinggal 1
head = tail = NULL;
free(temp);
}
else {
head = head->next;
temp->next = NULL;
}
free(temp);
}
}
void popTail(){
if (head){
struct data *temp = head;
if (head == tail){ // Kalau data tinggal 1
head = tail = NULL;
free(temp);
}
else {
while (temp->next != tail){
temp = temp->next;
}
temp->next = NULL;
free(tail);
tail = temp;
}
}
}
void popMid(int angka){
if (head){
if (angka == head->angka){ // Angka ada di Head
popHead();
}
else if (angka == tail->angka){ // Angka ada di Tail
popTail();
}
else { // Angka bukan di tail atau head
struct data *temp = head;
while (temp->next != NULL && temp->next->angka != angka){
temp = temp->next;
}
if (temp->next == NULL || temp->next->angka != angka ) {
printf("Angka %d tidak ditemukan\n", angka);
return;
}
struct data *temp2 = temp->next;
temp->next = temp2->next;
temp2->next = NULL;
free(temp2);
}
}
}
void cetak(){
if (head){
struct data *temp = head;
while (temp != NULL){
printf("%d", temp->angka);
if (temp != tail) printf("->");
temp = temp->next;
}
}
}
int main(){
pushMid(5);
pushMid(10);
pushMid(7);
pushMid(3);
pushMid(9);
pushMid(22);
cetak();
printf("\n");
popMid(3);
popMid(22);
popMid(9);
popMid(11);
popMid(1);
cetak();
}
Implementasi double Linked list dalam bahasa c :
#include <stdio.h>
#include <stdlib.h>
struct data{
int angka;
struct data *next, *prev;
}*head=NULL, *tail=NULL;
struct data *createNewNode(int num){
struct data *newNode = (struct data *)malloc(sizeof(struct data));
newNode->angka = num;
newNode->next = NULL;
newNode->prev = NULL; // Double Linked List
return newNode;
}
void pushHead(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
}
else {
newNode->next = head;
head->prev = newNode; // Double Linked List
head = newNode;
}
}
void pushTail(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
head->next = NULL;
}
else {
tail->next = newNode;
newNode->prev = tail; // Double Linked List
tail = newNode;
}
}
void pushMid(int angka){
struct data *newNode = createNewNode(angka);
if (!head){
head = tail = newNode;
head->next = NULL;
}
else {
if (head->angka > newNode->angka) pushHead(angka);
else if (tail->angka <= newNode->angka) pushTail(angka);
else {
struct data *temp = head;
while (temp->next != NULL && temp->next->angka < newNode->angka){ // Double Linked List
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
newNode->next->prev = newNode; // Double Linked List
newNode->prev = temp; // Double Linked List
}
}
}
void popHead(){
if (head){
struct data *temp = head;
if (head == tail){ // Kalau data tinggal 1
head = tail = NULL;
free(temp);
}
else {
head = head->next;
head->prev = NULL; // Double Linked List
temp->next = NULL;
}
free(temp);
}
}
void popTail(){
if (head){
struct data *temp = tail->prev; // Double Linked List
if (head == tail){ // Kalau data tinggal 1
head = tail = NULL;
free(tail);
}
else {
temp->next = NULL; // Double Linked List
tail->prev = NULL; // Double Linked List
free(tail);
tail = temp;
}
}
}
void popMid(int angka){
if (head){
if (angka == head->angka){ // Angka ada di Head
popHead();
}
else if (angka == tail->angka){ // Angka ada di Tail
popTail();
}
else { // Angka bukan di tail atau head
struct data *temp = head;
while (temp->next != NULL && temp->next->angka != angka){
temp = temp->next;
}
if (temp->next == NULL || temp->next->angka != angka ) {
printf("Angka %d tidak ditemukan\n", angka);
return;
}
struct data *temp2 = temp->next;
temp->next = temp2->next;
temp2->next = NULL;
temp2->prev = NULL;
temp2->next->prev = temp;
free(temp2);
// 4<->5<->8
}
}
}
void cetak(){
if (head){
struct data *temp = head;
while (temp != NULL){
printf("%d", temp->angka);
if (temp != tail) printf("->");
temp = temp->next;
}
}
}
int main(){
pushMid(5);
pushMid(10);
pushMid(7);
pushMid(3);
pushMid(9);
pushMid(22);
cetak();
printf("\n");
popMid(3);
popMid(22);
popMid(9);
}
Session 2
Stack & Queue
1. Stack
Stack atau tumpukan adalah suatu kumpulan elemen dimana elemen yang baru dimasukkan yang dapat diakses. Sebuah stack biasa di implementasikan menggunakan array atau bisa juga dengan linked list. Sebuah stack biasa menggunakan prinsip Last In First Out (LIFO), yang artinya masuk terakhir pertama. Contoh penerapan prinsip LIFO adalah sebuah kumpulan tumpukan buku yang baru saja dimasukkan ke dalam toko dengan jenis buku yang sama, pasti buku yang paling atas yang terjual terlebih dahulu.
Adapun pemanfaatan stack adalah untuk perhitungan ekspresi aritmetika(postfix),algoritma Backtracking(runut balik) dan algoritma rekursif.
Operasi-Operasi dalam Stack
1.Push : Menambahkan sebuah data baru
2.Pop : Menghapus sebuah data
3.Top : Mengambil data yang paling atas
2.Queue
Queue atau antrian merupakan struktur data linear dimana penambahan komponen dilakukan disatu ujung, sementara pengurangan dilakukan diujung lain. Queue sendiri menggunakan prinsip First In First Out (FIFO), yang artinya masuk pertama keluar pertama. Contoh penerapan FIFO di dalam kehidupan sehari-hari adalah antrian di dalam sebuah bank, yang setiap datang nasabah diwajibkan mengambil nomor antrian, dan yang datang lebih dahulu pastilah akan di panggil duluan oleh teller bank
Operasi-Operasi dalam Queue
1.Fungsi insert atau Enqueue digunakan untuk memasukkan sebuah data atau sebuah nilai ke dalam queue
2.Fungsi delete atau Dequeue digunakan untuk mengapus sebuah data di dalam queue.
Circular Queue
Jika kita menggunakan array untuk queue seperti di atas, maka ketika ada proses pengambilan (dequeue) ada proses pergeseran data. Proses pergeseran data ini pasti memerlukan waktu apalagi jika elemen queue-nya banyak. Oleh karena itu solusi agar proses pergeseran dihilangkan adalah dengan metode circular array
Perbedaan antara Stack dan Queue
Infix, Postfix, and Prefix Notation
Terdapat 2 istilah dalam notasi Infix, Postfix, Prefix
1.Operator : Tanda operasi ('+', '-', '/', '*', '%')
2.Operand : Nilai asal yang digunakan dalam operasi contohnya angka 1-10 dst.
Hal yang penting saat menggunakan notasi ini adalah komputer akan lebih cepat mengeksekusi program, dan lebih mengehemat penggunaan memori komputer.
Infix, Postfix, Prefix
Keterangan : Opd --> Operand
Opr --> Operator
1.Infiix : operator ditulis diantara operand --> (opd opr opd)
Contoh : 10 + 3 * 4
2.Postfix : operator ditulis setelah operand --> (opr opr opd)
Contoh : 10 3 4 * +
3.Prefix : operand ditulis sebelum operator-->(opd opr opr)
Contoh : + 10 * 3 4
Contoh lain
Infix : ((1 + 3) / (100 * 5) ^ 30)
Prefix : / + 1 3 ^ * 100 5 30
Postfix : 1 3 + 100 5 * 30 ^ /
Breadth First Search and Depth First Search
1. Breadth First Search
Metode pencari BFS adalah salah satu metode pencarian yang sederhana, dimana pencarian dimulai dari titik awal, kemudian dilanjutkan ke semua cabang titik tersebut secara berurutan. Jika titik yang dituju belum ditemukan, maka akan ada perulangan ke masing-masing titik cabang dari masing-masing titik, sampai titik tujuan ditemukan.
Source : binusmaya.binus.ac.id
Visit order : A, B, C, D, E
Untuk kelanjutannya, ada di link dibawah ini :
2.Depth First Search
Algoritma ini mirip dengan Algoritma BFS (Breadth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.
visit order : A, C, B, E, D.
contoh implementasi stack dalam bahasa c :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <Windows.h>
struct book{
char name[30];
struct book *next, *prev;
}*head, *tail, *curr;
void print(){
if(head!=NULL){
curr = head;
while(curr !=NULL){
printf("%s -> ", curr->name);
curr=curr->next;
}
}else{
printf("No Data");
}
printf("\n\n");
};
void pushHead(char name[]){
curr = (struct book *)malloc(sizeof (book));
strcpy(curr->name, name);
curr->next = curr->prev = NULL;
if(head==NULL){
head=tail=curr;
}else{
head->prev=curr;
curr->next=head;
head=curr;
}
}
void popHead(){
if(head==NULL){
printf("No Data");
}else if(head==tail){
curr=head;
head=tail=NULL;
free(curr);
}else{
curr=head;
head=head->next;
head->prev=NULL;
free(curr);
}
}
int main(){
int menu;
char name[30];
print();
do{
do{
system("cls");
print();
printf("1. Stack\n");
printf("2. UnStack\n");
printf("3. Exit\n");
printf("Choose : "); scanf("%d", &menu); fflush(stdin);
}while(menu<1 || menu>3);
switch(menu){
case 1 :
printf("Input Student Name : "); scanf("%s", name); fflush(stdin);
pushHead(name);
break;
case 2 :
popHead();
break;
}
}while(menu!=3);
}
contoh implementasi queue dalam bahasa c :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <Windows.h>
struct antrian{
int value;
struct antrian *next, *prev;
}*head, *tail, *curr;
void print(){
if(head!=NULL){
curr=head;
while(curr!=NULL){
printf("%d -> ", curr->value);
curr=curr->next;
}
}else{
printf("No Data");
}
printf("\n\n");
};
void pushHead(int value){
curr = (struct antrian *)malloc(sizeof (antrian));
curr->value=value;
curr->next = curr->prev = NULL;
if(head==NULL){
head=tail=curr;
}else{
head->prev=curr;
curr->next=head;
head=curr;
}
}
void popTail(){
if(tail==NULL){
printf("No Data");
}else if(tail==head){
curr=tail;
head=tail=NULL;
free(curr);
}else{
curr=tail;
tail=tail->prev;
tail->next=NULL;
free(curr);
}
}
int main(){
int menu;
int antrianke=1;
print();
do{
do{
system("cls");
print();
printf("1. Queue\n");
printf("2. DeQueue\n");
printf("3. Exit\n");
printf("Choose : "); scanf("%d", &menu); fflush(stdin);
}while(menu<1 || menu>3);
switch(menu){
case 1 :
pushHead(antrianke);
antrianke++;
break;
case 2 :
popTail();
break;
}
}while(menu!=3);
}
Session 3
Hasing
Hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya
Hash Table
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. Kelebihan menggunakan hash table adalah hash table relatif lebih cepat, kecepatan dalam insertsion,deletions relatif sama.
Pada saat kita ingin membuat hash table function ada beberapa hal yang perlu kita perhatikan yaitu ukuran array / table size, key value/nilai yang di dapat dari data(k) , hash value/hash index/indeks yang dituju(h).
Contoh - contoh hash function :
1.Mid-square
2.Division (most common)
3.Folding
4.Digit Extraction
5.Hashing Rotation
1.Mid square
mencari sebuah value dengan cara mengkuadratkan dan kemudian menggunakan jumlah bit yang sesuai dari kotak tengah untuk mendapatkan kunci hash
step :
1.Kuadratkan nilai dari kuncinya (k^2)
2.Meng-extract r bit yang berada di tengah dari hasil yang diperoleh pada langkah pertama
function : h(k) = s
k = key
s = hash key yang diperoleh dengan memilih r bit dari k^2
Contoh mid square
2.Division
Mencari sebuah value menggunakan operator modulus(%). Cara ini adalah cara tersimple untuk menemukan sebuah value dalam hash table.
function : h(z) = z mod M
z = key
m = nilai yang digunakan untuk membagi kunci, biasanya menggunakan bilangan prime, besar dari tabel / besar dari memori yang digunakan.
Contoh division
3.Folding
Metode ini membagi nilai asli ke dalam beberapa bagian, kemudian menambahkan nilai-nilai tersebut, dan mengambil beberapa angka terakhir sebagai nilai hashnya.
step :
1.membagi nilai kunci menjadi beberapa bagian
2.tambahkan bagian-bagiannya
4.Digit Extraction
Metode ini menggunakan cara digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.
contoh : Misal x = 15,980
jika kita mengekstrak digit 1,2,5 maka kita dapat mendapatkan hash code : 150.
5.Rotation hash
Metode ini menggunakan cara merotasi digit
contoh : alamat hash = 25291
hasil rotasi = 19252
Collision
Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.
Collision(tabrakan pada hash function) bisa saja terjadi, ada dua cara untuk permasalah tersebut yaitu, Linear Probing dan Chaining
1. Linear Probing
Dengan menambahkan suatu interval pada hasil yang diperoleh dari fungsi hash sampai ditemukan lokasi yang belum terisi. Interval yang biasa digunakan adalah
2.Chaining
Metode rantai bisa juga digunakan untuk menyelesaikan tabrakan pada hash function, setiap data yang di dalam array sebenarnya terhubung secara single linked list yang berpasangan.
Tree
Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lain
Konsep tree
DEGREE of TREE = 3
DEGREE of C = 2
HEIGHT = 3
PARENT of C = A
CHILDREN of A = B, C, D
SIBILING of F = G
ANCESTOR of F = A, C
DESCENDANT of C = F, G
istilah-istilah dalam tree :
a.)Root = node yang berada paling atas
b.)Edge = garis yang menghubungkan node
c.)Leaf = node-node yang tidak memilik daun
d.)Degree of node = degree suatu node adalah total subtree
e.)Sibling = node yang mempunyai parent sama
f.)Ancestor = Seluruh node yang terletak sebelum node tertentu dan
terletak pada jalur yang sama.
g.)Descendant = Seluruh node yang terletak sesudah node tertentu
dan terletak pada jalur yang sama.
Binary Tree
Binary tree adalah suatu tree yang selalu mempunyai 2 anak, biasanya ada di kiri dan kanan.Binary tree mempunyai beberapa tipe yaitu, perfect binary tree, balance binary tree, skewed binary tree, dan balance binary tree.
A. Perfect binary tree
Binary tree yang mempunyai kedalaman sama di bagian kiri dan kanan
B.Complete binary tree
Complete binary tree adalah suatu pohon biner yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.
C.Skewed binary tree
Skewed binary tree adalah binary tree yang mempunyai node paling banyak satu, sehingga membuatnya tidak seimbang
D.Balanced Binary Tree
Balanced binary tree adalah suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu
Implementasi hash table dalam bahasa c :
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define size 97
struct data {
int value;
char name[100];
struct data *next;
}*table[97] = {NULL}, *curr, *ptr;
void cls() {
for(int i = 0; i< 50; i++) {
printf("\n");
}
}
void push(int value, char name[]) {
curr = (struct data*)malloc(sizeof(struct data));
curr->value = value;
strcpy(curr->name,name);
int key = value % size;
curr->next = NULL;
if(table[key]==NULL) {
table[key]=curr;
}
else {
ptr = table[key];
while(ptr->next != NULL){
ptr = ptr->next;
}ptr->next = curr;
}
}
void cari() {
int search = 0;
int i = 0;
printf("Input Your KEYDATA : ");
scanf("%d",&search);
getchar();
search = search % 97;
ptr = table[search];
if(ptr != NULL) {
while(ptr !=NULL) {
if(ptr->value == search) {
printf("THE STRING DATA STORED IS %s\n",ptr->name);
break;
}
ptr = ptr->next;
}
}
else {
printf("THERE IS NO DATA REFERENCE TO NUMBER %d\n",search);
system("pause");
}
}
void tampil(){
int i = 0;
do{
ptr = table[i];
if(ptr !=NULL) {
printf("DATA AT INDEX %d:\n",i);
while(ptr != NULL){
printf("(%d \t %s)\n",ptr->value,ptr->name);
ptr = ptr->next;
}
printf("\n");
}
i++;
}while(i < 97);
}
void menu_awal() {
int data;
char string[100];
printf("Input your KEY DATA : ");
scanf("%d",&data);
getchar();
printf("Input your STRING DATA : ");
scanf("%[^\n]",string);
push(data,string);
}
void init() {
for(int i = 0; i< size; i++) {
table[i] = NULL;
}
}
int main() {
int choice;
init();
while(true) {
do{
tampil();
printf("--[PROGRAM MENU]--\n");
printf("1. Input Data\n");
printf("2. Search Data\n");
printf("3. Exit\n");
printf("Input your choice: ");
scanf("%d",&choice);
}while(choice < 1 || choice > 3);
switch(choice) {
case 1 :
menu_awal();
break;
case 2 :
cari();
break;
case 3 :
return 0;
}
}
}
Session 4
Binary Search Tree
Binary Search Tree
Binary search tree mempunyai ciri-ciri :
1.Setiap node mempunyai value dan tidak ada value yang double2.value yang ada di kiri tree lebih kecil dari rootnya
3.value yang ada di kanan tree lebih besar dari rootnya
4.kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )
Aturan main Binary Search Tree :
Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya
Operasi-operasi yang dilakukan pada binary search tree meliputi :
1. Operasi: Insertion BST
Memasukan value (data) baru kedalam BST dengan rekrusif
Bayangkan kita menginsert value x :
Dimulai dari root
jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )
2. Operasi: Delete ( Remove )
akan ada 3 case yang ditemukan ketika ingin menghapus yang perlu diperhatikan :
Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan) atau dengan cari dari right sub-tree anak kiri paling terakhir(leaf) (kanan,kiri)
3. Operasi: Search BST
dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.
Bayangkan kita akan mencari value X.
Memulai Pencarian Dari Root
Jika Root adalah value yang kita cari , maka berhenti
Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan
ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :
PreOrder : Print data, telusur ke kiri, telusur ke kanan
InOrder : Telusur ke kiri, print data, telusur ke kanan
Post Order : Telusur ke kiri, telusur ke kanan, print data
sumber :
https://abdilahrf.github.io/2015/06/pengenalan-binary-search-tree/
http://www.nblognlife.com/2014/12/binary-search-tree-bst-tree-lanjutan.html
http://lang8088.blogspot.com/2015/06/memahami-pengertian-binary-search-tree.html
contoh implementasi binary search tree dalam bahasa c :
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int x;
struct node *left, *right;
}node;
node *createNewNode(int x) {
node *temp = (node *)malloc(sizeof(node));
temp->x = x;
temp->left = temp->right = NULL;
return temp;
}
node *insertNode(node *root, int x) {
if(root == NULL)
{
return createNewNode(x);
}
else
{
if(x < root->x)
{
root->left = insertNode(root->left,x);
}
else if( x > root->x) {
root->right = insertNode(root->right,x);
}
else {
printf("Same data !!!\n");
}
}
return root;
}
node *findminimum(node *temp) {
// root kiri paling kanan || ambil root kanan paling kiri
if(temp->right == NULL)
return temp;
return findminimum(temp->right);
}
int search(node *root, int x) { // x yang dicari
if(root == NULL)
return -1;
if(root->x == x) // target kita
return 1;
else {
if(x < root->x)
{
return search(root->left,x);
}
else if( x > root->x) {
return search(root->right,x);
}
}
return -1;// gak dapaet
}
node *deleteNode(node *root,int x)
{
if(root == NULL) // gadapet.
{
printf("Gaada\n");
return root;
}
else if(x < root->x)
root->left = deleteNode(root->left,x);
else if(x > root->x)
root->right = deleteNode(root->right,x);
else
{
//3 case
//1.leaf
if(root->right == NULL && root->left == NULL)
{
free(root);
root = NULL;
}
else if(root->left == NULL)
{
node *temp = root;
root = root->right;
free(temp);
}
else if(root->right == NULL)
{
node *temp = root;
root = root->left;
free(temp);
}
else //case 3.
{
node *temp = findminimum(root->left);
root->x = temp->x;
root->left = deleteNode(root->left,temp->x);
}
}
return root;
}
void printInorder(node *root) {
if(root == NULL) {
return;
}
printf("%d ",root->x);
printInorder(root->left);
printInorder(root->right);
}
int main() {
node *root = NULL;
root = insertNode(root,16);
root = insertNode(root,25);
root = insertNode(root,14);
root = insertNode(root,17);
root = insertNode(root,18);
printInorder(root);
printf("\n");
root = deleteNode(root,17);
printInorder(root);
}
Tidak ada komentar:
Posting Komentar