Modul Struktur Data

Struktur Data (2) Oleh Rini Tisnawati

Objektif •Mengetahui maksud struktur data dan menjelaskan penggunaannya dalam pemrograman •Mengetahui operasi yang terkait dengan struktur data dan metode pemrograman paling umum yang terkait dengan struktur tersebut. •Mengetahui metode dan notasi yang digunakan untuk menspesifikasi apaapa yang perlu dikerjakan oleh program dan bagaimana program ini melakukan

Jenis/Tipe Data (Data Type) Terdiri dari 2. Set nilai data 3. Set operasi yang bisa diterapkan pada nilai tersebut Klasifikasi Jenis Data f) Simple Data Type (Jenis Data Sederhana) a) Item data individual g) Data Structures / data aggregates (struktur data) a) Kombinasi dari item data individual

Jenis Data Sederhana • Numerik, terdiri dari : – Numerik integer (bilangan bulat) – Numerik real (bilangan riil)

• Karakter, terdiri dari : – Alfabet : a .. z, A .. Z – Angka : 0 .. 9 – Simbol khusus : + ? ‘ ! [ ] { } … dll

• Boolean (logika), terdiri dari : – True – False

Identifier • Dalam bahasa pemrograman, item data diidentifikasi menurut namanya, bukan menurut alamat lokasinya dalam memori • Identifier akan merupakan konstanta jika ia selalu dikaitkan dengan nilai data yang sama • Identifier akan merupakan variabel jika nilai datanya yang terkait bisa berubah • Literal, nilai data yang tertera dalam

Deklarasi Data • Jenis data konstanta dan variabel harus didefinisikan dalam program sehingga : – operasi yang tepat dapat dijalankan pada nilai data dan – Jumlah ruang penyimpanan yang tepat bisa ditentukan

• Statement untuk mendefinisikan jenis data disebut declarative statement • Beberapa bahasa pemrograman memiliki sintaks pendeklarasian yang berbeda • Beberapa contoh program (pendeklarasian data) yang akan diberikan ditulis dalam pseudo-code

Contoh: Constants pi = 3.141592654 Variables i, qty : integer harga_satuan, harga_beli : real status : boolean nama : character(25)

Struktur Data • Kelompok item data yang terorganisasi yang dianggap sebagai suatu unit • Disebut juga sebagai jenis data kompleks (complex data type) atau data aggregates • Beberapa struktur data : – – – – –

Array (larik) String Record List (daftar) Tree

Array (Larik) • Set item data yang disusun secara baik menjadi rangkaian dan diacu atau ditunjuk oleh satu identifier Contoh : Nilai = (56 42 89 65 48) • Item data individual dalam array bisa ditunjuk secara terpisah dengan menyatakan posisinya dalam array itu – Nilai(1) menunjuk 56 – Nilai(2) menunjuk 42

• Bilangan yang ditulis dalam tanda kurung menandakan posisi item individual dalam array (disebut juga subscript / indeks)

Array (Larik) lanjut • Variabel bisa digunakan sebagai subscript, misalnya Nilai(i). – Jika i = 2 maka menunjuk ke Nilai(2) yaitu 42 – Jika i = 4 maka menunjuk ke Nilai(4) yaitu 65

• Item data individual dalam suatu array sering disebut elemen • Matriks – Array yang hanya berisi bilangan dan tidak ada data alfabetisnya

• Klasifikasi Array – Array 1 dimensi – Array multi dimensi

Array Multi Dimensi • Mempunyai elemen-elemen yang disusun ke dalam baris dan kolom dan digunakan sebagai tabel data • Contoh : Nilai ujian dari mahasiswa satu kelas untuk beberapa mata kuliah bisa ditempatkan dalam array 2 dimensi

Deklarasi Array • Array 1 dimensi – Variables

Nilai: array [1..5] of integer A : array [1..4] of real • Array 2 dimensi – Variables

A : array [1..5, 1..2] of integer

Penanganan Array • Metode dasar penanganan array : – – – –

Mencari nilai terbesar Mencari nilai terkecil Menghitung nilai rata-rata Menghitung jumlah nilai di bawah rata-rata

• Menyortir Array (Sort) – Buble sort – Straight selection sort

• Mencari/Meneliti Array (Search) – Linear search

Penanganan Array (Lanjut) • Contoh : Nilai ujian mahasiswa akan dibaca dalam array. Kemudian akan ditampilkan nilai terbesar, nilai terkecil, nilai rata-rata, nilai total, dan jumlah nilai di bawah rata-rata. • Tahapan penanganan array – Input nilai data ke dalam array – Mengkalkulasi nilai terbesar, terkecil, total, dan rata-rata – Mengkalkulasi jumlah nilai di bawah ratarata

String • Rangkaian karakter yang ditangani sebagai unit data tunggal Contoh (string literal) : “ABC, 32fl2. 3h” “Kucing dalam karung” Contoh (variabel string) : A = “Universitas” B = “Gunadarma” • Berada dalam bentuk array karakter 1 dimensi

String (lanjut) • Fixed-length string (String yang panjangnya tetap) – Mempunyai jumlah tempat karakter yang tetap yang tersedia (bisa digunakan) untuk penyimpanan data

• Variable-length string (String yang panjangnya berubah-ubah) – Memberi data sejumlah spasi (ruang) sesuai yang ia perlukan

Deklarasi String • Fixed-length string Variables

nama : string[5] • Variable-length string Variables

nama : string

Operasi pada String • Concatenation – Penggabungan dua atau lebih string – Contoh :

A = “Universitas” B = “Gunadarma” C=A+B maka C = “UniversitasGunadarma”

Operasi pada String [2] • Substring – Mengambil bagian dari suatu string

Contoh A = “Universitas” B = “Gunadarma” C = Left(A, 3) D = Right(B, 5) E = Substr(A, 4, 5) maka C = “Uni” D = “darma” E = “versi”

Teknik Pencarian ( Searching) • Teknik Pencarian ( Searching ) pada array adalah mencari suatu nilai yang diinginkan pada tabel array. • Pencarian di tabel array diklasifikasikan menjadi : – Pencarian sekuensial ( sequential search ). – Pencarian biner ( binary search). – Pencarian sekuensial tidak mensyaratkan tabel terurut.

• Pencarian biner mensyaratkan tabel terurut. Saat array tidak terurut, satusatunya pencarian yang mungkin

•

Deskripsi : Pencarian Diketahui TI sekuensial bertipe TabInt, telah diisi. Tulis procedure yang jika diberikan X bernilai

integer akan mencari apakah harga X terdapat di TI. Pencarian dilakukan secara berurutan mulai elemen pertama sampai ketemu atau sampai elemen terakhir. Program menghasilkan indeks IX dimana X diketemukan pertama kali. IX diberi harga 0 jika tidak ketemu. Pencarian segera dihentikan begitu harga pertama diketemukan. • Pendeklarasian array : Const Idxawal = 1; Idxakhir = 100; Type TypeInfo = integer; TabInt = Array [Idxawal..Idxakhir] of TipeInfo;

Aturan pembuatan program : Algoritma Procedure SeqSearch (TI : TabInt; X : Integer; Var IX : Integer); i  Idxawal foundFalse While i <= Idxakhir . and . not found do If TI[i] = X then Found  true Else ii+1 Endif EndWhile If found then IX  i Else IX  0

Pencarian Biner • Deskripsi : Diketahui TI bertipe TabInt, telah diisi dan isinya terurut menaik. Tulis prosedur yang jika diberikan X bernilai integer akan mencari apakah harga X ada di TI. Pemeriksaan dilakukan dengan mereduksi elemen tabel array, menjadi separuh jumlah elemen tabel semula, yaitu : – Bandingkan harga yang dicari dengan harga elemen tengah. – Jika sama, berarti ketemu. – Jika yang dicari lebih kecil, berarti pencarian dengan cara yang sama harus dilakukan terhadap elemenelemen di belahan atas. – Jika harga yang dicari lebih besar, berarti pencarian dengan cara yang sama harus dilakukan terhadap elemen-elemen di belahan bawah.

• Prosedur menghasilkan harga indeks IX dimana X

Algoritma Procedure BinSearch (TI : TabInt; X : Integer ; Var IX : Integer);

Atas  Idxawal Bawah  Idxakhir Tengah  ( Atas + Bawah ) div 2 While Atas < Bawah . and . TI[Tengah] <> X do If TI[Tengah] < X then Atas  Tengah + 1 Else Bawah  Tengah – 1 Endif Tengah  ( Atas + Bawah ) div 2; EndWhile If TI[Tengah] = X then IX  Tengah Else IX  0

•

Teknik Pengurutan Sorting atau ( pengurutan Sorting data ) adalah

proses yang sering dilakukan dalam pengolahan data. • Mesin otomatik yang pertama kali lahir adalah mesin pengurut (masih dipakai sampai saat ini). • Pengurutan dibedakan menjadi dua, yaitu : – Pengurutan internal, yaitu pengurutan terhadap sekumpulan data yang disimpan dalam media internal komputer, dapat diakses elemennya secara langsung. Pengurutan terhadap array (tabel). – Pengurutan eksternal, yaitu pengurutan

Pengurutan Berdasarkan Seleksi • Gagasan • Menghasilkan nilai minimum tabel (untuk efisiensi, hanya indeks dimana harga minimum ditemukan yang dicatat), kemudian menukarnya dengan elemen terujung, “diisolasi” dan tidak diikutsertakan pada proses berikutnya. Proses diulang untuk sisa tabel.

Procedure MaxSort (Var TI : TabInt); Var I : integer;

{indeks untuk traversal array}

Pass : integer;

{tahapan pengurutan}

Temp : integer;

{memorisasi harga untuk penukaran}

IMin : integer;

{indeks, dimana TI[Nmin .. Pass] berharga minimum}

Begin For Pass = NMin to Nmax – 1 do Begin {tentukan minimum diantara [Pass .. NMax]} IMax 

Pass;

For I = Pass+1 to Nmax do Begin If (TI[Max] > TI[I]) then IMax  I; End; {TI[IMax] adalah minimum TI[Pass .. NMax]} {tukar TI[IMax] dengan TI[Pass]} Temp  TI[IMax]; TI[IMax]  TI[Pass]; TI[Pass]  Temp;

Pengurutan Berdasarkan Penyisipan • Gagasan • Mencari tempat yang tepat untuk setiap elemen tabel, dengan secara sequential search, kemudian menyisipkan sebuah elemen tabel yang diproses ke tempat yang seharusnya.

Procedure InsertionSort (Var TI : TabInt); Var I : integer; Pass : integer; Temp : integer;

{indeks untuk traversal array} {tahapan pengurutan} {memorisasi harga untuk penukaran}

Begin {TI[NMin] adalah terurut} For Pass = Nmin+1 to Nmax do Begin Temp TI[Pass]; {simpan harga TI[Pass] supaya tidak tertimpa pergeseran} {sisipkan elemen ke-Pass dalam TI[NMin .. Pass-1] sambil menggeser} I Pass -1; While ( Temp > TI[I] ) And ( I > NMin) do Begin TI[I+1]  TI[I]; {geser} I I-1;

{elemen berikutnya}

End; {(Temp >= TI[I] yaitu tempat yang tepat) atau I=1 harus disisipkan sebagai elemen pertama} If (Temp > TI[I]) then TI[I+1]  Temp; {telah menemukan tempat yang tepat} Else