Struktur Data Linier
Tujuan Mahasiswa mampu memilih struktur/type data yang tepat pada setiap variabel yang digunakan dalam program guna meningkatkan efisiensi penggunaan memori (Space) sehingga berdampak pada peningkatan Speed (kecepatan eksekusi) sebuah program. Definisi Struktur dan Data Struktur dapat diartikan sebagai suatu susunan, bentuk, pola atau bangunan. Contoh rangkaian kata yang mengandng kata struktur adalah: struktur organisasi, struktur jaringan, struktur kimia, dsb Data berasal dari bahasa Yunani datum yang berarti fakta. Kata data sudah berarti majemuk/jamak sehingga tidak perlu mengulangnya untuk menyatakan banyak. Ada 2 Model Data a. Model data logika adalah model data yang ditinjau dari sudut pandang pemakai (manusia), yaitu segala sesuatu yang dapat diterima oleh indera manusia yang berasal dari rangsangan-rangsangan di sekitarnya, baik secara tersurat maupun tersirat. b. Model data fisik adalah model data yang ditinjau dari sudut pandang komputer yaitu segala sesuatu yang dapat dikodekan atau disimbolkan dengan kode-kode atau simbol-simbol yang telah disediakan di setiap komputer. (Ingat kembali data di komputer/ sistem bilangan dan konversi bilangan) Definisi Struktur Data Jika kata “struktur” dan “data’ disatukan akan bermakna “suatu susunan simbol-simbol yang diorganisasikan sesuai dengan definisi yang diberikan terhadapnya di komputer”. Jadi mata kuliah ini mempelajari bagaimana data disusun di memori utama komputer agar penggunaan space di memori efisien, cepat dalam pencarian dan pengambilannya kembali (retrieving) dan dapat diolah sesuai tujuan kita. Sehingga mempelajari struktur data erat kaitannya dengan membuat suatu algoritma (rangkaian pemikiran logis untuk menyelesaiakan suatu masalah). Input Algoritma Penyelesaian
Program untuk menyelesaikan masalah
Proses
Masalah Struktur Data
Output Gambar 1 : Peranan algoritma dan struktur data dalam pembuatan program
Halaman 1/8
Struktur Data Linier
Data Majemuk dan Data Elementer Nim
Nama
Alamat
TTL
0431001 0431002
Agus Dessy
Jl. Kartini 25 Malang Jl. Ijen 25 Malang
Malang, 11/11/77 L Surabaya, 12/01/80 P
data elementer
Jkel
data majemuk
Operasi-Operasi Dasar Pada Struktur Data a. Traversing
: proses mengunjungi setiap elemen data pada suatu struktur data, tepat satu kali
b. Searching
: proses pencarian data dengan kriteria tertentu
c. Inserting
: proses menambah elemen data baru ke suatu struktur data
d. Deleting
: proses menghapus elemen data dari struktur
e. Sorting
: proses menyusun elemen-elemen data dalam urutan/aturan tertentu
f. Update
: proses mengganti nilai suatu elemen data dengan nilai baru
g. Mergening
: proses menggabung dua buah struktur data menjadi satu
Klasifikasi Struktur Data Array Linier Link List Struktur data
Sederhan Tree Non linier Graph
Halaman 2/8
Struktur Data Linier
Struktur Data Linier Array (Larik) Array adalah tipe terstruktur yang mempunyai komponen/elemen dalam jumlah yang tetap (statis sesuai deklarasi) dan setiap elemennya mempunyai tipe data yang sama. Posisi setiap elemen dalam array dinyatakan dalam nomor indek atau subscript. Struktur ini banyak digunakan dalam operasi sorting, searching dan traversing data. Ciri-ciri array: a. Banyak elemennya tertentu/terhingga b. Tipe elemennya sama c. Membutuhkan lokasi memori yang Contigueus/menyatu sehingga letak elemen berdekatan satu sama lain (dengan tujuan agar mudah melacak/membaca kembali) • Array Satu Dimensi a. Model Logika Cara penulisan di media kertas/papan sedemikian rupa sehingga dapat dengan mudah untuk menulis atau membaca kembali. Contoh :
daftar belanja 1. 2. 3. 4. 5.
nilai
sawi bawang bayam mie cien kecap
1 2 3 4 5
60 70 100 50 40
b. Model Fisik Menyusun sedemikian rupa elemen-elemen data yang akan diinputkan dan kemudian disimpan dalam memori komputer. Untuk lebih memperjelas pemahaman tentang model fisik ini dapat diambil contoh sebagai berikut: Tipe data sederhana
Tipe data array
int A, JM; char I;
int A[100], JM; char I;
main() { For (I=0; I<100; I++) { cin >> A; JM += A; } ………. }
main() { For (I=0; I<100; I++) { cin >> A[I]; JM += A[I]; } ………… }
Halaman 3/8
Struktur Data Linier
Tipe data sederhana
PEMETAAN DATA DI MEMORI
Tipe data array
A
2 Byte
A[0]
I
1 Byte
A[1]
JM
2 Byte
•
Free
Total : 5 Byte
•
•
2 Byte * 100 = 200 Byte
A[99]
•
1 Byte
I
•
2 Byte
JM
203 Byte
Free
Free Total : Pendeklarasian tipe data array 1 demensi type_elemen namaarray[jumlah_elemen]; contoh: int A[10]; float B[20];
dari deklarasi di atas, dapat dihitung kebutuhan memori suatu array atau yang lebih dikenal dengan istilah Panjang Dimensi (DIM(A)) sebagai berikut: DIM(A) = Banyak Elemen (A) * W (Word Length) dimana W adalah kebutuhan memori masing-masing elemennya. Sedangkan untuk mencari lokasi atau address suatu elemen array dapat digunakan rumus: LOC(A[i]) = Base(A) + i * W Keterangan: i
: Nomor elemen yang dicari
Base(A) : Alamat elemen pertama (biasanya diketahui) Contoh kasus : Diket deklarasi array sebagai berikut: int A[20]; Hitunglah: a. DIM(A) b. Alamat A[3], Jika diketahui Base(A)=2500. Latihan: Diketahui deklarasi array sebagai berikut: int A[20]; float B[100]; Hitunglah: a. DIM(A) dan DIM(B) b. Alamat A[10], Jika diketahui Base(A)=2150. c. Alamat B[55], Jika diketahui Base(B)=5400. Operasi-operasi Pada Array 1 Demensi Halaman 4/8
Struktur Data Linier
• Traversing Proses mengunjungi setiap elemen data tepat satu kali Traversing(A, Jml) I=0 While (I < Jml) /* Proses A[ I ] */ I = I +1 EndOf While EndOfTraversing
Atau
For (I=0; I < Jml; I++) { /* Proses A[ I ] */ }
• Inserting Operasi menambahkan elemen data baru ke struktur. Operasi ini hanya dapat dilakukan jika ada kelebihan alokasi memori/masih ada tempat yang kosong. Untuk melakukan operasi inserting, dimisalkan: • Nama arraynya = A • Kapasitas maximum dari array = Max • Jumlah elemen yang sudah terisi = Jml, • Posisi penyisipan/Index = P, dan • Elemen yang disisipkan = X, maka Algoritma insertingnya adalah: Inserting_array(A, Max, Jml, P, X) If Jml = Max Then write ( over flow ) Else I = Jml While ( I > P ) do A[I] = A[I -1] I = I -1 EndOfWhile A[P] = X /* atau */ A[I] = X Jml = Jml +1 EndIf EndOfInserting_array
Index 0 1 2 3 4 5 6 7 8 9
Data 9 8 7 6 5 . . . . .
Index 0 1 2 3 4 5 6 7 8 9
Data 9 8 4 7 6 5 . . . .
4
Catatan: Dalam algoritma ini diusahakan seluruh elemen data berdekatan satu sama lain agar mudah dalam membaca kembali.
Halaman 5/8
Struktur Data Linier
• Deleting Operasi menghapus elemen data dari struktur Array. Operasi ini hanya dapat dilakukan jika ada data dalam struktur tersebut (tidak kosong). Untuk melakukan operasi inserting, dimisalkan: • Nama arraynya = A • Jumlah elemen yang terisi = Jml, • Posisi penghapusan/Index = P, dan Algoritma Deleting adalah: Deleting_array(A, Jml, P) If Jml = 0 Then write ( under flow ) Else I = P; While ( I < Jml - 1 ) do A[I] = A[I +1] I = I +1 EndOfWhile Jml = Jml -1 EndIf EndOfDeleting_array
Index 0 1 2 3 4 5 6 7 8 9
Data 9 8 7 6 5 2 3 4 0 1
Index 0 1 2 3 4 5 6 7 8 9
Data 9 8 7 6 2 3 4 0 1 1
• Sorting Operasi menyusun elemen-elemen data dalam aturan atau urutan tertentu. Ada dua model sorting yaitu: 1. Data disusun dengan urutan dari kecil ke besar, yang dikenal dengan model ascending, dan 2. Data disusun dengan urutan dari besar ke kecil, yang dikenal dengan model descending. Sedangkan metode/cara yang dapat digunakan untuk mengurutkan data cukup banyak, diantaranya: Buble Sort
Shell Sort
Insertion Sort
Quick Sort
Radix sort
dsb
Metode-metode ini akan kita bahas dalam bab tersendiri.
Halaman 6/8
Struktur Data Linier
•
Searching Operasi mencari elemen data dengan kriteria tertentu. Metode yang dapat digunakan dalam operasi ini ada dua yaitu: Linier/sequential Search Searching Binary Search
A. Metode Sequential Search Metode Sequential Search adalah metode pencarian data dengan cara membandingkan nilai pencarian setiap elemen dalam struktur mulai index pertama hingga index terakhir selama pencarian belum ditemukan. Algoritma Sequential Search Sequential_Search(A, Cari, Max) I = 0; While (A[I] != Cari) && (I <= Max) I = I + 1; If I > Max Write ( data tidak ditemukan) Else Write ( data ketemu di posisi I ) Endif EndOfSequential_Search Dalam pencarian data dengan metode ini dikenal dua kasus sebagai hasil pemcarian 0 1 2 3 4 . . Max
yaitu: Kasus terbaik (best case)
: Data yang dicari ditemukan pada index pertama
Kasus terburuk (worst case) : Data yang dicari ditemukan pada index terakhir atau tidak ditemukan hingga index+1. Sehingga rata-rata jumlah pembandingan data, dapat dihitung sebagai berikut:
∑ Pembandingan =
1 + Max 2
Halaman 7/8
Struktur Data Linier
B. Metode Binary Search Pencarian biner hanya dapat dilakukan pada DATA yang sudah terurut. Pencarian data dengan metode ini dilakukan dengan membandingkan nilai pencarian dengan nilai elemen tengah, pada contoh berikut dimisalkan CARI merupakan nilai pencarian, maka pembandingan selalu dilakukan terhadap nilai CARI dengan nilai elemen tengah, dimana nilai tengah didapat dengan cara sebagai berikut: AWAL := BB; AHIR := BA; TENGAH := (AWAL + AKHIR) DIV 2; BERULANG SELAMA ((Data[Tengah] != CARI) DAN (AWAL <= AKHIR)) JIKA CARI > D[TENGAH] MAKA PENCARIAN KE RUAS/BAGIAN KANAN (AWAL := TENGAH+1) JIKA CARI < D[TENGAH] MAKA PENCARIAN KE RUAS/BAGIAN KIRI (AKHIR := TENGAH-1) TENGAH := (AWAL + AKHIR) DIV 2; AKHIR PERULANGAN AW T AH 0 1 2 3 4 5 6
Dari algoritma diatas jika dibuat programnya sebagai berikut: #include
#include void main() { int data[8] = {1,2,3,4,5,6,7,8}; int aw, tg, ah, cari; clrscr(); cout << "Nilai yang dicari : "; cin >> cari; aw = 0; ah = 7; tg = (aw + ah) / 2; while (cari != data[tg] && aw <= ah) { if (cari > data[tg]) aw = tg + 1; else ah = tg - 1; tg = (aw + ah) / 2; } if (cari == data[tg]) cout << cari << " ditemukan di urutan ke " << tg; else cout << cari << " tidak ditemukan !"; getch(); }
Jumlah proses pembandingan data pada pencarian biner rata-rata adalah 2 log N, itupun jika nilai yang dicari berada di ujung urutan. Sebagai contoh lihat tabel berikut : Jumlah Data (N) 2 Log N
4 2
8 3
16 4
1024 10
Halaman 8/8
