FINAL REVIEW

POINTER

---

Pointer sebenarnya sudah dipelajari pada saat semester 1 yaitu pada matakuliah algorithm. Pointer sendiri adalah penunjuk suatu variabel. Pointer wajib memiliki alamat dari variabel yang ditunjuknya.

cara deklarasi pointer seperti ini

tipe_data *nama_pointer;

jika ingin membuat 2 pointer yang berbeda bisa menambahkan 1 bintang lagi atau membuat dengan nama pointer yang berbeda

tipe_data **nama_pointer;

ARRAY

---

Array merupakan kumpulan variabel yang bertipe data sama. array biasa digunakan untuk menyimpan sebuah nilai.

cara deklarasi array seperti ini

misalnya kita ingin membuat data angka yang dapat menyimpan angka 1-3

maka

int angka[4];

perlu diketahui bahwa setiap kali membuat array banyaknya data harus +1 karena array selalu mulai dari angka 0.

LINKED LIST

---

Linked list adalah salah satu data structure yang terdiri dari urutan record data dimana setiap record punya field yang berisikan alamat/referensi ke record data berikutnya dalam sebuah urutan.

SINGLE LINKED LIST

---

Sebuah Single Linked List hanya memiliki 1 penghubung ke node lain.

Sebuah Linked List dikatakan kosong apabila isi pointer head adalah NULL.

Single Linked List hanya memiliki beberapa operasi yaitu PUSH dan POP.

Contoh

PUSH DEPAN 2,4,6,8 maka hasilnya angka paling depan akan ada dipaling belakang maka urutannya 8-6-4-2-NULL.

PUSH BELAKANG 2,4,6,8 maka hasilnya akan sama 2-4-6-8-NULL.

cara coding single linked list

pertama buat dulu struct data misal untuk nama dan score.

struct data{ char name[51]; int score; struct data *next; }*head=NULL, *tail=NULL;

kedua buat nodenya

struct data* newNode(char name[], int score){ //1. reserve memory struct data *node = (struct data*)malloc(sizeof(struct data)); //2. assign value strcpy(node->name, name); (*node).score = score; node->next = NULL; return node; }

setelah itu bisa buat program pushnya. seperti push depan, belakang atau tengah

Push Depan

void pushHead(struct data **head, struct data **tail, char name[], int score){ //1. reserve memory & 2. assign value struct data *node = newNode(name, score); //3. connect if(*head == NULL) //list masih kosong *head = *tail = node; else{ node->next = *head; *head = node; } }

Push Belakang

void pushTail(struct data **head, struct data **tail, char name[], int score) { //1. reserve memory & 2. assign value struct data *node = newNode(name, score); //3. connect if(*head == NULL) //list masih kosong *head = *tail = node; else { (*tail)->next = node; *tail = node; } }

Push Tengah

void pushMiddle(struct data **head, struct data **tail, char name[], int score){ //1. reserve memory & 2. assign value struct data *node = newNode(name, score); //3. connect if(*head == NULL) //list masih kosong *head = *tail = node; else if(score < (*head)->score){ //pushHead node->next = *head; *head = node; } else if(score >= (*tail)->score){ //pushTail (*tail)->next = node; *tail = node; } else{ struct data *curr = *head; while(score >= curr->next->score) { curr = curr->next; } node->next = curr->next; curr->next = node; } }

setelah membuat program maka kita akan membuat program pop yaitu delete.

Pop Depan

void popHead(struct data **head, struct data **tail){ if(*head == NULL) printf("No Data to Delete\n"); else if(*head == *tail){ free(*head); *head = *tail = NULL; } else{ struct data *curr = *head; *head = (*head)->next; free(curr); } }

Pop Belakang

void popTail(struct data **head, struct data **tail){ if(*head == NULL) printf("No Data to Delete\n"); else if(*head == *tail){ free(*head); *head = *tail = NULL; } else{ struct data *curr = *head; while(curr->next!= *tail){ curr= curr->next; } free(*tail); *tail = curr; (*tail)->next= NULL; } }

Pop Tengah

void popMiddle(struct data **head, struct data **tail){ int count=2; struct data *curr = *head; if(*head == NULL){ printf("No Data to Delete\n"); } else if(*head == *tail){ free(*head); *head = *tail = NULL; } else{ while(curr->next!=NULL){ curr=curr->next; count++; } curr=*head; if(count%2==0){ count=count/2; } else{ count=(count/2)+1; } int dex=1; while(dex!=count-1){ curr=curr->next; dex++; } struct data *depan = *head; struct data *belakang = *head; struct data *prev; while(depan!=NULL && depan->next!=NULL){ depan=depan->next->next; prev=belakang; belakang=belakang->next; } prev->next=belakang->next; free(belakang); } }

Pop All

void popAll(struct data **head, struct data **tail){ struct data *curr = *head; if(*head == NULL) printf("No Data to Delete\n"); else{ while(curr!=NULL){ *head = (*head)->next; free(curr); curr = *head; } *head = *tail = NULL; } }

cara deklarasinya

int main(){ struct data *head=NULL; struct data *tail=NULL;

//lalu masukkan function push yang diinginkan misal push middle atau pop

pushMiddle(&head, &tail, "michael", 19);

//perlu diingat function pop tidak akan berjalan jika data yang tersisa tinggal 1

}

LINKED LIST II

---

CIRCULAR SINGLE LINKED LIST

Circular Single Linked List adalah sebuah Linked List dimana semua node terhubung untuk membentuk sebuah loop.

Pada Circular Single Linked List tidak memiliki NULL pada bagian akhirnya.

Cara Deklarasi Node Circular Single Linked List

typedef struct TNode{

int data;

TNode *next;

};

DOUBLY LINKED LIST

Doubly Linked List adalah Linked List dua arah dimana yang satu berisi refrensi kedata berikutnya dan yang satunya lagi berisi data refrensi berikutnya.

deklarasi Doubly Linked List

struct tnode {

int value;

struct tnode *next;

struct tnode *prev;

};

struct tnode *head = 0;

struct tnode *tail = 0;

HASHING TABLE & BINARY TREE

---

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil key dengan cepat.

Dalam Hashing character string dapat ditransform menjadi sebuah nilai yang datanya pendek atau sebuah key yang mewakili string asli.

Hash Table adalah tabel (array) tempat dimana menyimpan string asli. Indeks tabel adalah Hashed Key sementara nilainya adalah string asli.

Ukuran table hash berbeda-beda biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin ada, sehingga beberapa string mungkin memiliki hash key yang sama.

HASH FUNCTION

---

MID-Square

Mid-Square merupakan fungsi hashing dengan cara mengkuadratkan nilai string/indentifier yang kemudian digunakan dalam jumlah bit sesuai dengan tengah kotak untuk mendapatkan hash key.

Sebagai contoh

Nilai = 1003

Nilai 1003 dipangkatkan menjadi 1.006.009‬ nilai tersebut merupakan square value

Setelah itu ambil nilai tengah dari squre value yaitu 606 ini merupakan hasil dari Mid-Square Hashing.

Division

Division merupakan fungsi hashing dengan cara membagi nilai string/indentifier menggunakan operator modulus.

Sebagai contoh

Misalnya table menyimpan string. Fungsi hash yang sangat sederhana adalah menambahkan nilai ASCII dari semua karakter dalam string dan mengambil modulo ukuran tabel, misalnya 97.

Misalnya data "ABCD" maka ( 64+1 + 64+2 + 64+3 + 64+4) % 97 = 76 oleh karena itu data "ABCD" akan disimpan di 76.

Folding

Folding merupakan fungsi hashing dengan cara mempartisi string/indentifier menjadi beberapa bagian lalu ditambahkan bersama-sama untuk mendapatkan hash key

Sebagai contoh

Nilai = 1234

maka akan dipecah menjadi 2 part yaitu 12 dan 34

setelah itu ditambahkan 12+34 maka menjadi 46

maka hash keynya 46

Digit Extraction

Digit Extraction merupakan fungsi hashing dengan cara digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

Sebagai contoh

Nilai = 123456

jika kita hanya mengambil digit ke 1, 3 dan 5 maka kita akan mendapatkan

hash code = 135

Rotating Hash

Rotating Hash merupakan fungsi hashing dengan cara metode hash (seperti metode pembagian atau mid-square)

Setelah mendapatkan kode / alamat hash dari metode hash, lakukan rotasi.

Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Sebagai contoh

diberikan hash address 12345

maka hasil dari rotating hashnya 54321

COLLISION

---

Collision terjadi jika kita ingin menyimpan string ini menggunakan fungsi hash sebelumnya (gunakan karakter pertama dari setiap string).

Cara untuk menyelesaikan collision ada 2 yaitu

1. Linear Probing

Cari slot kosong berikutnya dan letakkan string tersebut di sana.

2. Chaining

Masukkan string ke dalam slot sebagai chained list(linked list).

TREE & BINARY TREE

---

Tree adalah struktur data non-linear yang mewakili hubungan hierarkis di antara objek data.

Beberapa hubungan tree dapat diamati dalam struktur direktori atau hierarki organisasi.

Node di tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.

BINARY TREE CONCEPT

---

Binary tree adalah struktur data rooted tree di mana setiap node memiliki paling banyak dua anak.

Kedua anak itu biasanya dibedakan sebagai anak kiri dan anak kanan.

Node yang tidak memiliki anak disebut leaf.

TIPE-TIPE BINARY TREE

---

Perfect Binary Tree

PERFECT binary tree adalah binary tree di mana setiap level berada pada kedalaman yang sama.

Complete Binary Tree

Complete Binary Tree adalah binary tree di mana setiap level, kecuali mungkin yang terakhir, terisi penuh, dan semua node sejauh mungkin dibiarkan. Perfect Binary Tree adalah Complete Binary Tree.

Skewed Binary Tree

Skewed Binary Tree adalah binary tree di mana setiap node memiliki paling banyak satu anak.

Balanced Binary Tree

Balanced Binary Tree adalah binary tree di mana tidak ada daun yang jauh lebih jauh dari root daripada leaf lainnya (skema penyeimbangan yang berbeda memungkinkan definisi yang berbeda dari "jauh lebih jauh").

TRANSVERSAL

---

misal ekspresi pada tree concept

struct tnode {

char chr;

struct tnode *left;

struct tnode *right;

};

lalu buat ekspresi pada tree dari prefix

Bisa dideklarasikan dengan cara rekursif

char s[MAXN];

int p = 0;

void f(struct tnode *curr) {

if(is_operator(s[p])) {

p++; curr->left = newnode(s[p]);

f(curr->left);

p++; curr->right = newnode(s[p]);

f(curr->right);

} }

Prefix transversal

void prefix(struct tnode *curr){

printf( “%c “, curr->chr );

if ( curr->left != 0 ) prefix(curr->left);

if ( curr->right != 0 ) prefix(curr->right);

}

Postfix transversal

void postfix(struct tnode *curr) {

if ( curr->left != 0 ) postfix(curr->left);

if ( curr->right != 0 ) postfix(curr->right); printf( “%c“, curr->chr );

}

Infix transversal

void infix(struct tnode *curr) {

if ( curr->left != 0 ) infix(curr->left);

printf( “%c“, curr->chr );

if ( curr->right != 0 ) infix(curr->right);

}

Binary Search Tree

---

Binary search tree adalah salah satu struktur data yang faster searching, rapid sorting, and easy insertion and deletion. Binary search tree juga dikenal sebagai versi binary tree yang disort.

INSERTION OPERATION

Dimulai dari root. jika x kurang dari node maka insert x ke sub tree, atau masukkan x ke sub tree kanan ulang terus sampai menemukan empty node untuk meletakkan X (X akan selalu menjadi leaf baru)

DELETION

jika key hanya leaf tinggal delete saja nodenya

jika key memiliki 1 child delete node dan connect child ke parentnya

Jika key ada dinode yang memiliki dua child, temukan child paling kanan dari sub tree kirinya (simpul P), ganti kuncinya dengan kunci P dan hapus P secara rekursif. (atau secara bergantian Anda dapat memilih anak paling kiri dari sub tree kanannya)

CIRCULAR LINKED LIST Circular Single Linked List adalah sebuah Linked List dimana semua node terhubung untuk membentuk sebuah loop. Pada Circular Single Linked List tidak memiliki NULL pada bagian akhirnya. Cara deklarasi Circular Linked List typedef struct TNode{

int data;

TNode *next;

}; DOUBLY LINKED LIST Doubly Linked List adalah Linked List dua arah dimana yang satu berisi refrensi kedata berikutnya dan yang satunya lagi berisi data refrensi berikutnya. Cara deklarasi Doubly Linked List struct tnode { int value; struct tnode *next; struct tnode *prev; }; struct tnode *head = 0; struct tnode *tail = 0; BINARY SEARCH TREE Binary search tree adalah salah satu struktur data yang faster searching, rapid sorting, and easy insertion and deletion. Binary search tree juga dikenal sebagai versi binary tree yang disort. binary search tree memiliki 2 operation yaitu insert dan delete Program Toko CPP bisa didownload pada link google drive disini Max-Min heap

dalam max-min heap, max dan min bergantian pada setiap level

level ganjil memakai max heap

level genap memakai min heap

FFind-Min in Min-Heappertama kita harus tahu dulu apa itu heap

Heap sendiri merupakan complete binary tree berdasarkan struktur data yang memenuhi properti heap.

nah properti apa yang dimiliki heap

- Min Heap

setiap element node lebih kecil dari childrennya.

- Max Heap

setiap element node lebih besar dari childrennya.

pertama kita bahas dulu min heap

seperti yang dijelaskan tadi Min heap setiap element nodenya lebih kecil dari childrennya artinya elemen terbesar terletak di suatu tempat di salah satu leaf node. Heap dapat diimplementasikan menggunakan linked-list, tetapi jauh lebih mudah untuk mengimplementasikan heap dengan array.

berikut contoh dari Min Heap

lalu heap memiliki beberapa aplikasi

1. Priority Queue

- Algoritma Pilihan (menemukan elemen min / maks, median, elemen kth- terbesar, dll).

- Algoritma Dijkstra (menemukan jalur terpendek dalam grafik).

- Algoritma Prim (menemukan pohon rentang minimum).

2. Heap Sort

- An O(n.lg(n)) algorithm.

MIN HEAP

---

PRIORITY QUEUE

Heap adalah implementasi efisien dari priority queue data structure.

- find-min: cari elemen terkecil di heap.

- insert: memasukkan elemen baru ke heap.

- delete-min: hapus elemen terkecil dari heap.

untuk delete-min dan insert sama halnya namanya seperti pop dan push.

ARRAY IMPLEMENTATION

heap biasanya mengimplementasikan dalam bentuk array.

Elemen-elemen disimpan secara berurutan dari indeks 1 ke N dari atas ke bawah dan dari node kiri ke kanan tree.

Root disimpan dalam indeks 1

(kami membiarkan indeks 0 kosong / tidak digunakan, untuk tujuan kenyamanan).

Cara menghitung index bisa seperti ini

anggap current node adalah sebuah index x maka

parent(x) = x/2

left-child(x) = 2*x

right-child(x) = 2*x+1

Inilah mengapa kita menggunakan indeks 1 sebagai root, jika tidak

hubungan tidak akan muncul.

Find-Min in Min-Heap

untuk mencari nilai minimum dalam min heap bisa dilakukan dengan

int findmin() {return data[1];}

INSERTION IN MIN-HEAP

insert untuk min-heap ada 2 cara yaitu

1. Upheap

Masukkan node seperti biasa, lalu bandingkan dengan node di atasnya (parent) bila parent nilai nya lebih besar, tukar. Setelah ditukar lakukan hal yang sama dengan node diatasnya. Berhenti ketika node yang diatas nya sudah lebih kecil.

2. Downheap

Masukkan node seperti biasa, mulai dari node root, bandingkan dengan left dan right child, bila lebih kecil, tukar node nya dengan node yang lebih kecil. lanjutkan terus dan berhenti bila node dibawahnya.

Heap Complexity

find-min: O (1)

insert: O (log (n))

delete-min: O (log (n))

insert dan delete-min tergantung pada ketinggian tree, yang

adalah log (n), ketinggian binary tree lengkap.

MAX HEAP

---

Setiap elemen node lebih besar dari elemen childnya.

Ini menyiratkan bahwa elemen terbesar terletak di root pohon.

Max-heap memiliki prinsip yang sama dengan min-heap dan dapat digunakan untuk membuat queue priority yang perlu menemukan elemen terbesar alih-alih yang terkecil.

MIN-MAX HEAP

dalam max-min heap, max dan min bergantian pada setiap level

Setiap elemen pada level genap / ganjil lebih kecil dari semua childnya (level min).

Setiap elemen pada level ganjil / genap lebih besar dari semua childnya (level maksimal).

INSERTION PADA MIN-MAX HEAP

masukkan node seperti biasa,

bila node ada di min heap:

- jika node parent lebih kecil, tukar node sekarang dengan node parent, lalu cek grand parent dari nodenya, bila lebih kecil, tukar.

bila node ada di max heap:

- jika node parent lebih besar, tukar node sekarang dengan node parent, lalu cek grand parent dari nodenya, bila lebih besar, tukar.

DELETION PADA MIN-MAX HEAP

Penghapusan elemen terkecil

- Ganti root dengan elemen terakhir di heap.

- Kurangi jumlah elemen dalam tumpukan.

- Downheapmin dari root.

Penghapusan elemen terbesar

- Ganti child kiri atau child kanan root (tergantung mana yang lebih besar) dengan elemen terakhir di heap.

- Kurangi jumlah elemen dalam tumpukan.

- Downheapmax dari node.

TRIES

---

Tries (prefix tree) adalah struktur data tree terurut yang digunakan untuk menyimpan array asosiatif (biasanya string)

Istilah TRIE berasal dari kata RETRIEVAL, karena mencoba dapat menemukan satu kata dalam kamus dengan hanya awalan kata.

Nama : Antonio Michael Kurniawan

NIM : 2301924063