Data Structure Summary

Data Structure Summary

Muhammad Raul Taqi Athallah

2301893013

CD-01

POINTER

Pointer adalah sebuah variable untuk menunjuk variable lainnya
Contoh:
A = 5, *ptr = &A berarti pointer menunjuk variable A (jika di output akan menujukan nilai dari A)

Operator:
- & = Address, agar compiler tau letak variable dimana
- *  = untuk nentuin isinya (untuk pointer)

Mempelajari data structure bertujuan untuk mengatur data secara structural dan efisien. Contoh : antrian ke ATM

LINKED LIST:
Linked list ditaruh secara acak di RAM dan cara data a dan b saling berhubungan maka ditunjuk oleh pointer
- Single linked list = 1 pointer
- Double linked list = 2 pointer
- Multiple linked list  >2 pointer

Single linked list = contohnya seperti  Array1 menunjuk Array2, Array2 menunjuk Array3, kelemahan Single linked list adalah posisi nya tidak bisa terbalik.

Double linked list = contohnya seperti Array1 menunjuk Array2, Array2 menunjuk ke Array3 tetapi Array2 juga menunjuk ke Array1

HEAD selalu menunjuk ke Node paling awal/paling kiri (note: tidak ada HEAD akan menjadikan program itu error)
TAIL selalu menunjuk ke Node paling akhir/paling kanan

MALLOC itu mengembalikan void bintang
Kita dapat menambahkan maupun mengdelete data.
Jika codingan error, biasanya kesalahannya ada di HEAD / TAIL / Head dan Tail belum sampai NULL

Jika ingin Delete, pastikan HEAD dipindahkan terlebih dahulu

Circular single list tidak ada NULL di akhir, tapi menunjuk kembali ke HEAD

STACK & QUEUE

STACK

Data struktur penting yang menyimpan elemen-elemennya dengan kaidahnya tersendiri. Dapat dibilang Last In First Out. Stack dapat menggunakan array atau linked list. Elemen di stack paling atas dapat ditambah/dihilangkan. Elemen yang berada di stack paling atas dapat disebut sebagai TOP.

1.      Operator Stack

·        Push(x) : add item x ke paling atas dari stack

·        Pop()    : remove item paling atas dari stack

·        Top()    : reveal/return item paling atas dari stack

2.      Notasi  Infix, Postfix, dan prefix =

·        Prefix   : menuliskan operator sebelum operand. (operator operand operand)

                (* 4 10)

·        Infix     : menuliskan operator diantara operand. (operand operator operand)

                (4 * 10)

·        Postfix  : menuliskan operator setelah operand. (operand operand operator)

                (4 10 *)

Kenapa kita belajar prefix/postfix notaion? Prefix/postfix notation berfungsi untuk menghilangkan brackets/kurung agar bisa diproses lebih cepat.

3.      Depth First Search (DFS)

Algoritma untuk melintasi atau mencari didalam grafik atau pohon. Kita mulai dari akar sebuat pohon (atau sebuah simpul dalam grafik) dan mengexplore sebisa mungkin pada setiap cabang sebelum backtracking.

DFS memiliki banyak pengaplikasian seperti topological sorting, menemukan artikulasi point dan bridge di grafik, menemukan connected component, DLL. DFS dapat di implementasikan dengan fungsi rekursif atau prosedur interatif menggunakan stack.

4.      Pengaplikasian dari Stack

·        Reverse the order of data

·        Convert infix expression into postfix

·        Convert postfix expression into infix

·        Backtracking problem

·        System stack is used in every recursive function

·        Converting a decimal number into its binary equivalent

QUEUE 

Data struktur penting yang menyimpan elemen-elemennya dengan kaidahnya tersendiri. Dapat di implementasikan dengan menggunakan array atau linked list. Elemen-elemen di queue di tambahkan pada bagian akhirnya, dan penghilangan pada bagian depannya saja. Atau dapat disebut First In First Out.

1.      Operator Queue

·        Push (x)            :  add item x pada queue paling belakang.

·        Pop()    : remove item pada bagian depan queue.

·        Front() : reveal/return item paling deoan dari queue .(peek)

2.      Circular Queue

kita dapat wrap-around index L dan R. jika R mencapai MAXN lalu set R sebagai 0, lakukan hal yang sama pada L.

3.      Pengaplikasian queue =

·        Deques

·        Priority Queues

·        Breadth First Search

4.      Deques

Deques adalah  list di dalam setiap elemen yang dapat dimasukan/dihilangkan pada setiap bagian akhir. Deques juga dikenal sebagai head-tail linked list karena elemen-elemen dapat dimasukan/dihilangkan dari head/tail.

5.      Dua variasi pada double-ended queue =

·        Input restricted deque

In this dequeue insertions can be done only at one of the dequeue while deletions can be done from both the ends.

·        Output restricted deque

In this dequeue deletions can be done only at one of the dequeue while insertions can be done on both the ends.

6.      Priority Queue

Tipe data yang abstrak di setiap elemen memiliki prioritas sendiri.

Aturan umum dari processing elements priority queue yaitu:

·        Elemen dengan prioritas tertinggi di proses sebelum elemen dengan prioritas yang rendah

·        Dua elemen yang memiliki prioritas yang sama akan diproses sesuai dengan urutan kedatangan

7.      Breadth First Search (BFS)

BFS seperti DFS dimana algoritma untuk melintas/mencari dalam diagram/pohon

8.      Pengaplikasian dari BFS :

·        Menemukan connected component pada grafik

·        Menemukan jalan terpendek dalam grafik tanpa bobot

·        Metode Ford-Fulkerson untuk computing maximum flow.

·        Etc.

9.      Perbedaan BFS dan DFS = perbedaan dalam implementasi iterasi hanya pada data structure yang dipakai. DFS menggunakan stack, BFS menggunakan queue.

Nama   : Muhammad Raul Taqi Athallah

NIM     : 2301893013

Hashing, Hash Tables, and Binary Tree

1.     Hashing

Hashing adalah Teknik untuk menyimpan dan mengambil keys dengan cepat. Dalam hashing, string dari karakter di ubah menjadi value pendek atau key yang mewakili string aslinya.

Hasing juga bisa dikenal sebagai konsep pendistribusian kunci/key di dalam array yang disebut hash table menggunakan fungsi hash fuction.

2.     Hash Table

Hash Table adalah sebuah struktur data yang terdiri atas sebuah table dan fungsi bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah table.

·       Operasi pada Hash Table

a.      insert         : menginput nilai dalam table

b.     find           : temukan nilai yang berhubungan dengan key

c.      remove      : temukan nilai yang berhubungan dengan key, kemudian     hapus nilai tersebut

d.     getIterator : mengembalikan iterator, yang memeriksa nilai satu demi satu

·       Struktur dan Fungsi pada Hast Tabel

Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

Cara untuk mendapatkan field kunci ini sangatlah beragam, namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function dan menghasilkan indeks lokasi record dalam tabel.

a.      k(x) = fungsi pembangkit field kunci (1)

b.     h(x) = hash function (2)

3.     Tree

Tree adalah data struktur non-linear yang mewakili relasi hirarki dari setiap objek data. Sebagian dari relasi tree bisa dilihat di directory structures atau hirarki organisasi.

Tree adalah kumpulan dari satu node atau lebih

 

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

• Node paling atas adalah root.
• Garis yang menyambungkan node parent ke node child disebut edge.
• Node yang tidak mempunyai child disebut leaf.
•  Node yang mempunyai parent yang sama disebut sibling.
•  Degree adalah total sub tree dari node tersebut
•  Height/Depth adalah maksimum degree dari node dalam tree.
• Jika ada garis yang menyambungkan P ke Q, maka P itu disebut ancestor dari Q, dan Q adalah descendant dari P

4.     Binary Tree

Binary tree adalah rooted tree data structure dimana setiap node memiliki maksimal 2 children.

2 children itu biasanya disebut left child dan right child. Node yang tidak mempunyai child disebut leaf.

Ini adalah contoh dari Binary Tree 9 nodes. Rootnya adalah node yang berisi 18. Leaves adalah node yang berisi 9, 12, 10, dan 23

Ada beberapa tipe dari Binary Tree, yaitu :

• PERFECT Binary Tree, memiliki depth yang sama.

• COMPLETE Binary Tree 

• SKEWED Binary Tree, setiap node hanya bisa memiliki 1 anak.

• BALANCED Binary Tree is a binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther