Untuk post kali ini, saya akan menulis ulasan materi mata kuliah Struktur Organisasi Data 2 yang kami pelajari di semester 8 ini. Semoga bermanfaat!


1. Tipe Data

Struktur data adalah koleksi atau kumpulan data yang dapat dikarakterisasikan oleh organisasi serta operasi yang didefinisikan terhadapnya.
Algorithma: urutan langkah-langkah/perintah untuk menyelesaikan sebuah program. Langkah-langkah/perintah tersebut harus bisa dijalankan secara bertahap dari awal hingga akhir.


Data secara umum dapat dikategorikan atas :

-  Tipe data sederhana

1.  Tunggal :

    Integer: Digunakan untuk merujuk kepada tipe data apapun yang merepresentasikan bilangan bulat, atau beberapa bagian dari bilangan bulat. Disebut juga sebagai Integral Data Type.

Operasi dasar yang ada dalam integer yaitu : +, -, *, /, ^

Terdapat dua jenis operator, binary operator adalah operator yang bekerja pada dua (integer) operand dan unary operator adalah operator yang bekerja pada satu operand saja.

    Real: Digunakan untuk tipe data untuk merepresentasikan pendekatan terhadap bilangan real.

    Boolean: Jenis data ini disebut juga jenis data logical. Elemen dari jenis data ini mempunyai nilai salah satu dari true atau false.

    Operator yang sering digunakan pada boolean ada dua, yaitu.

    A. Operator Logika

    AND : bernilai true apabila kedua operand bernilai true.

    OR : bernilai ture apabila salah satu dari operand bernilai true.

NOT : memiliki hak yang lebih tinggi dari AND dan OR, sehingga harus didahulukan, kecuali terdapat tanda kurung.

    B. Operator Relasional

    Operator relasional, yaitu : >, <, >=, <=, <> dan =

    Contoh: 5 > 4 = True, 1 > 2 = False

    Karakter: Jenis data karakter merupakan elemen dari suatu himpunan yang terdiri atas bilangan, abjad dan simbol khusus. Contoh: (0,1,...,8,9, A, B, ..., Y,Z, +, -,*,√, ...}

2.  Majemuk :

String: Barisan hingga karakter yang dibentuk oleh suatu kumpulan dari karakter.
Operasi pada string:

LENGTH : Nilai dari operasi ini adalah suatu integer yang menunjukkan panjang dari suatu string . Notasi : LENGTH(S) = N (integer), di sini S = String, N = integer

CONCAT : Operasi ini bekerja terhadap dua string dan hasilnya merupakan resultan dari kedua string tersebut. Notasi  : CONCAT(S1, S2).

SUBSTR : Operasi ini adalah operasi membentuk string baru, yang merupakan bagian dari string yang diketahui. Notasi : SUBSTR(S, i, j)

INSERT : Operasi ini adalah untuk menyisipkan suatu string ke dalam string lain. Notasi : INSERT(S1,S2,i).

DELETE : Operasi ini digunakan untuk menghapus sebagian karakter dalam suatu string. Notasi : DELETE(S,i,j)


-Struktur data

1.  Sederhana :
    Array
    Record

2. Majemuk :
- Linier : Linier Linked List, Stack, Queue
- Non Linier : Binary Tree, Binary Search Tree, General Tree, Tree, Graf


MAPPING KE STORAGE


* INTEGER

Bentuk mapping ke storage dari integer dapat dilakukan dengan beberapa cara, yaitu :

Skema Sign and Magnitude : Cara ini merupakan bentuk konvensional yang digunakan manusia untuk menyatakan suatu bilangan dalam bentuk biner. Di sini representasi bilangan positif dan negatif hanya dibedakan dengan tanda saja.

Skema Two’s Complement : Jika x bilangan bulat non negatif maka x’ bilangan binary negatif dari x sedemikian sehingga x + x’ = R.

R = 2N
N = jumlah digit maksimum
x’ = R - x

Contoh :

Bila N = 4, maka R = 2^4 = 16
x = 5 ⎢0101
x’ = R - x
    = 16 - 5 = 11 ⎢1011 (-5)

Skema One’s Complement : Jika x bilangan bulat non negatif maka x’ bilangan binary negatif dari x sedemikian sehingga x + x’ = R.
R = 2N - 1
N = jumlah digit maksimum
x’ = R - x

Contoh :

Bila N = 4, maka R = 2^4 - 1= 15
x = 5 ⎢0101
x’ = R - x
    = 15 - 5 = 10 ⎢1010 (-5)





2. Array


Array : Kumpulan data homogen yang berurutan. Terurut berarti, elemen tersebut teridentifikasikan sebagai data pertama, sampan dengan elemen ke-n. Homogen berarti mempunyai tipe data yang sama.


ARRAY DIMENSI SATU : Vektor adalah bentuk yang sederhana dari array, yang merupakan array dimensi satu.


BENTUK UMUM

Misal : Array A dengan tipe data B dan subskrip bergerak dari L sampai U, maka array B dapat ditulis :  N(L:U)
L : Lower Bound (Batas Bawah) | U : Upper Bound (Batas Atas).
Banyaknya elemen adalah : U - L + 1


ARRAY DIMENSI DUA : Suatu array yang setiap elemennya merupakan tipe data array pula.


BENTUK UMUM

Misal : Array B dengan tipe data T, subskrip baris dari L1 sampai U1, subskrip kolom dari L2 sampai U2, ditulis sebagai berikut : B(L1:U1,L2:U2)
Banyaknya elemen adalah : (U1 - L1 +1) * (U2 - L2 +1)


PEMETAAN KE STORAGE : ARRAY

DIMENSI SATU

Alamat awal dari memori yang dialokasikan bagi array. Alamat awal dari array dinyatakan dengan B (Base Location), dan setiap elemen dari array menduduki S byte. Alamat awal dari array dengan elemen ke-I adalah : B + (I -L) * S

DIMENSI DUA

Terdapat dua cara:

1. ROW-MAJOR ORDER
B + (I - L1) * (U2 - L2 + 1) * S + (J - L2) * S

2. COLUMN-MAJOR ORDER
B + (J - L2) * (U1 - L1 + 1) * S + (I - L1) * S


ARRAY DIMENSI TIGA : Adalah suatu array yang setiap elemennya merupakan tipe data array  juga yang merupakan array dimensi dua.

CROSS SECTION (Penampang Array Berdimensi-2) : Adalah pengambilan salah satu subskrip.

Misal : Baris = tetap konstan
Kolom = berubah-ubah (*)


TRANSPOSE dari array dimensi-2 : Adalah penulisan baris menjadi kolom atau kolom menjadi baris. Notasi : Array B (I,J), transpose dari array B adalah BT = (J,I).


TRIANGULAR ARRAY (ARRAY SEGITIGA)

Triangular array dapat berupa :

1. Upper Triangular: Semua elemen di bawah diagonal utama = 0
2. Lower Triangular: Semua elemen di atas diagonal utama = 0

SPARSE ARRAY : Suatu array yang sangat banyak elemen nol-nya dikenal sebagai sparse array.



3. Stack

LINIER LIST : Suatu struktur data umum yang berisi suatu kumpulan terurut dari elemen; jumlah elemen di dalam list dapat berubah-ubah.
Suatu elemen dapat dihilangkan/dihapus dari sembarang posisi dalam linier list, dan dapat pula dimasukkan elemen baru sebagai anggota list.

Contoh :

1. File, dengan elemennya berupa record
2. Buku telepon
3. Stack
4. Queue
5. Linear link list

STACK : suatu bentuk khusus dari linier list, dengan operasi penyisipan dan penghapusan dibatasi hanya pada satu sisinya, yaitu puncak stack (TOP). Elemen teratas dari stack dinotasikan sebagai TOP(S). Jumlah elemen di dalam stack kita notasikan dengan NOEL(S). NOEL(S) menghasilkan nilai integer.

Operator penyisipan (insertion) : PUSH
Operator penghapusan (deletion) : POP
Operasi stack : LIFO(Last In First  Out), yaitu : yang terakhir masuk yang pertama keluar.

Contoh stack : Tumpukan baki dalam cafetaria


Empat operasi dasar yang berlaku pada stack :


1. CREATE(stack) : adalah operator yang menunjukkan suatu stack kosong dengan nama S.

2. ISEMPTY(stack) : adalah operator yang menentukan apakah stack S kosong. Operandnya terdiri dari type data stack. Hasilnya merupakan type data Boolean

3. PUSH(elemen, stack) : operator yang menambahkan elemen E pada puncak stack S. Hasilnya merupakan stack yang lebih besar.

4. POP(stack) : adalah operator yang menghapus sebuah elemen dari puncak stack S. Hasilnya merupakan stack yang lebih kecil.


APLIKASI STACK
1.  Penjodohan Tanda Kurung/Matching Parantheses

ALGORITMA

a. Amati barisan elemen dari kiri ke kanan
b. • bila bertemu ‘(‘, maka ‘(‘ di pushke dalam stack.
   • bila bertemu ‘)’, maka periksa stack hampa atau tidak.
     bila hampa →ada ‘)’ dan tidak ada ‘(‘ (error)
     bila tidak hampa →ada sepasang ‘(‘ & ‘)’ & POP elemen keluar


2.  NOTASI POSTFIX

ALGORITMA
Amati barisan dari kiri ke kanan

1.  Jika ‘(‘, maka PUSH ke dalam stack.
2.  Jika ‘)’, POP elemen dalam stack sampai simbol ‘(‘. Semua di POP merupakan output kecuali ‘(‘ tadi.
3.  Jika simbol operand, langsung merupakan output.
4.  Jika simbol operator, maka : Jika elemen TOP stack dengan level >= maka POP sebagai output teruskan sampai ‘(‘. elemen TOP <, operator yang diamati di PUSH ke dalam stack.
5.  Bila ‘;’ kita POP semua elemen dalam stack hingga hampa.


APLIKASI STACK

Notasi Postfix

Contoh :
Notasi Infix : ((A+B) * C/D+E^F)/G;





4. QUEUE (ANTRIAN)
Suatu bentuk khusus dari linear list, dengan operasi penyisipan (insertion) hanya diperbolehkan pada salah satu sisi, yang disebut REAR, dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi yang lainnya, yang disebut FRONT dari list.

Operasi Antrean : FIFO (First In First Out), elemen yang pertama masuk merupakan elemen yang pertama keluar.
Operator : Penyisipan : Insert | Penghapusan : Remove

Empat operasi dasar antrean, yaitu :

1. CREATE (Q) : Operator yang menunjukkan suatu antrean hampa Q.
Berarti : Noel (Q) = 0 Front (Q) & Rear (Q) = tidak terdefinisi

 2. ISEMPTY (Q) : Operator yang menunjukkan apakah antrean Q hampa.
Operand : tipe data antrean
Hasil : tipe data boolean ISEMPTY (CREATE (Q)) = True

 3. INSERT (E, Q) : Operator yang menginsert elemen E ke dalam antrean Q.
E ditempatkan di bagian belakang antrean. Hasil : antrean yang lebih besar.
REAR (INSERT (E, Q)) = E ISEMPTY (INSERT (E, Q)) = False

4. REMOVE (Q) : Operator yang menghapus elemen bagian depan dari antrean Q.
Hasil : antrean yang lebih pendek.
Pada setiap operasi, Noel (Q) berkurang 1 dan elemen ke-2 menjadi elemen terdepan.
Jika Noel (Q) = 0 maka Q = hampa Remove (Q) = kondisi error (underflow condition) Remove (Create (Q)) = kondisi error (underflow condition)


 5. GRAPH - ALGORITMA DJIKSTRA DAN FLOYD WARSHALL

 tutorial untuk membuat graph serta penjelasan algoritma djikstra :

2KA20_ASSYIFA F_11111265.pdf


penjelasan tentang ALGORITHMA FLOYD-WARSHALL berserta simulasinya ada di video ini :

 

sekian ulasan materi SOD 2 yang bisa saya berikan. kurang lebih nya mohon maaf.

sumber:

 Official Site of DETTY PURNAMASARI - Gunadarma University
 Algoritma - Wikipedia bahasa Indonesia, ensiklopedia bebas
 Struktur data - Wikipedia bahasa Indonesia, ensiklopedia bebas
 Tipe Data ~ Fikri Mujahid
 Integer (ilmu komputer) - Wikipedia bahasa Indonesia, ensiklopedia bebas

Labels: best memories, makul: SOD 2, post: tugas, post: tugas vclass, post: ulasan materi