Month: March 2016

Tree concepts

tree is a collection of one or more nodes

node at top – root

lines is edge, node with no edge down is leaves

same parent node = sibling, level of depth = degree,

maximum degree = height/depth

binary has at max 2 nodes, left and right child.

How to count depth = 2^k

How to find height = 2^(h+1) – 1

if nodes are known, minimum height = 2log(n), maximum height = n-1 where n is number of nodes.

 

Stack has two variables.

• Top -> Used to store address of the top element of a stack.
• Max -> Used to store the maximum number that can be stacked.

If TOP = Null, stack is empty, if TOP = max -1 , then stack is full.

Insertion & Deletion will be done at TOP.

Stack Operations.

• Push(x) = add an item x to the top of stack
• Pop( ) = remove item from top of stack
• Top( ) = reveal the top item from stack (Top = Peek)

Queue

Front = Rear = -1

Ketika ada yang masuk, misal push (5,3,7,12), rear ditambah 1, jadi rear = 0. cek rear + 1 apakah >= max, jika tidak, lanjutkan terus

pop( ) front + 1 >= rear. jika tidak, lanjutkan terus

Prefix, Postfix

4+6*(5-2)/3 = +4/*6-523

Caranya: Prefix, liat paling duluan.

1. Kurang dulu, prefix operator kiri. Terus operand kiri kanan tentukan.

– 5 2

2.  Next yang tanda * dulu, di kiri. Angka 6 di kirinya (5-3)

*6-52

Seterusnya sampai selesai.

DFS ( Depth First Search), turun dulu ke paling dalam.

BFS (Breath First Search), mencarinya secara menyisir dari kiri- kanan ataupun kanan – kiri.

 

Definisi Data: Suatu data atau informasi.

Macam –  Macam data struct:

• Array: Homogen, Static
• Linklist: Heterogen, Dynamic

Cara storing Array:

Initialization (Dari awal)

Inputting (Scanf dari user)

Assigning (Menggunakan = dari program)

Apa saja yang bisa dilakukan ke array?

Traversal (Assign Nilai)

Insert (Masukkin Nilai)

Searching (Mencari Nilai)

Deletion (Hapus Nilai)

Merging (Gabungin nilai, dari array A gabung ke B)

Sorting (Sort Nilai)

Definisi Pointer

100 = A (Variable)

= B (Variable)

Jika ingin Var B berisi nilai dari Var A

Int A, int *B; B = &A (Sehingga jika value dalam Variable A berubah, value dalam B juga berubah.

Queue

Element that was inserted first is the first one to be taken out.

Dalam Queue terdapat Front dan Rear, front berada di array paling awal, rear berada di paling belakang. Jika [0] selesai, front maju ke [1], seterusnya hingga front bertemu dengan rear. Jika ada data baru, maka rear mundur 1 kali.

Queue ada banyak macam, salah satunya adalah Circular Queue dan Priority Queue.

Stacks

Menggunakan konsep LIFO (Last in, First out)

Contohnya buku yang disusun.

Buku yang diletakkan paling akhir pasti akan keluar pertama, Buku yang diletakkan paling awal pasti akan dikeluarkan paling akhir.

Binary Tree

Bentuknya seperti akar pohon yang selalu kebawah. Jika Binary berarti memmiliki maksimal dua cabang.

Binary Spanning Tree

Sama seperti Binary Tree namun memiliki beberapa aturan. Angka akar utama menjadi referensi untuk akar dibawahnya. Akar sebelah kiri harus lebih kecil dari akar utama dan akar sebelah kanan harus lebih besar.