STRUKTUR DATA PERTEMUAN 2

BAB 2

ARRAY DAN RECORD

1.          ARRAY

           

            Salah satu struktur data yang teramat penting adalah array atau larik. Array merupakan bagian dasar, yang disebut blok, guna keperluan pembentukan suatu struktur data lain yang lebih kompleks. Hampir setiap jenis struktur data kompleks dapat di sajikan secara logic oleh array.

            Kita dapat mendefinisikan array sebagai sautau himpunan hingga elemen, terurut dan homogeny. Terurut, kita artikan bahwa elemen tersebut dapat di identifikasi sebagai elemen pertama, elemen kedua, dan seterusnya sampai elemen ke-n. Sedangkan pengertian elemen yang homogeny adalah bahwa setiap elemen dari sebuah array tertentu haruslah mempunyai tipe data yang sama.

            Jadi suatu array dapat mempunyai elemen semuanya berupa integer atau dapat pula seluruhnya berupa untai aksara atau string. Bahkan dapat pula terjadi bahwa suatu array mempunyai elemen berupa array pula.

            Sebenarnya, pengertian array telah banyak kita kenal dan kita pelajari dalam matematika. Di sana, array lebih terkenal sebagai matriks. Kadang-kadang ia disebut juga sebagai table. Juga pernah kita dengar tentang vector. Vektor adalah bentuk yang paling sederhana dari array. Vektor merupakan array dimensi satu atau one dimensional array.

A.     ARRAY SATU DIMENSI

            Sebuah array dimensi satu, yang misalnya kita beri nama NILAI, dapat kita bayangkan berbentuk seperti ini :

 

            Subscript atau indeks dari elemen array menyatakan posisi, elemen pada urutan dalam array tersebut. Notasi yang di gunakan bagi elemen array, biasanya adalah nama array dilengkapi dengan subscript.

            Secara umum, suatu array dimensi satu A dengan tipe data T dan subscript bergerak dari L sampai dengan U, di tulis sebagai A (L:U) = (A(1)), I = L, L+1, L+2,…, U, dan setiap elemen A(1) bertipe data T.

            Sebagai contoh, kita dapat menuliskan data hasil pencatatan suhu ruangan setiap satu jam selama periode 24 jam, dalam sebuah array dimensi satu.

            Harga minimum dari subscript dari array disebut batas bawah atau lower bound, sedangkan harga maksimumnya di sebut batas atas atau upper bound. Jadi pada array di atas, L merupakan batas bawah, dan U batas atas . Sedangkan untuk array “suhu” yang elemennya dapat kita tulis sebagai SUHU (I), batas bawahnya adalah 1 dan batas atasnya 24. SUHU(I) menyatakan suhu pada jam ke-1, dan I memenuhi 1<=I <=24, I merupakan integer.

            Batas bawah dari array, pada beberapa aplikasi, tidak selalu diambil 1. Kadang-kadang di ambil batas bawah nol, bahkan juga negative. Banyaknya elemen sebuah array disebut rentang atau range. Jadi array A(L:U) mempunyai range sebesar U-L+1. Secara khusus bila L=1 dan U=N, maka range dari array A(1:N) adalah N-I+1=N.

B.     ARRAY DUA DIMENSI

            Sebuah array dimensi banyak atau multi-dimensional array didefinisikan sebagai sebuah array yang elemennya berupa array pula. Misal array B mempunyai M lemen berupa array pula, yang terdiri dari N elemen. Kalau hal tersebut kita gambarkan, akan terbentuk baris dan kolom seperti :

                                    Untuk itu di perlukan dua buah subscript. Yang pertama di gunakan untuk menyatakan posisi baris, sedangkan yang kedua untuk posisi kolom. Secara umum array dimensi dua B, dengan elemen bertipe data T, subscript baris dari 1 sampai M, subscript kolom dari 1 samapi N, di tulis sebagai B(1:M, 1:N) = (B(I,J)), I = 1, 2, ...,M dan J = 1, 2,...,N dengan setiap elemen B(I,J) bertipe data T. Array B tersebut dikatakan berukuran atau berorder M x N. Di sini banyak elemen array adalah M*N.

                                    Contoh dari array dimensi dua sangat banyak kita jumpai. Misal nilai ujian 500 mahasiswa ASIA tingkat 3, untuk 8 mata kuliah dapat kita sajikan sebagai array dimensi dua yang berorder 500 x 8. Elemen B(I,J) menyatakan nilai mahasiswa ke-I untuk mata kuliah ke-J.

                                    Seperti halnya pada array dimensi satu, pada array dimensi dua batas bawah untuk subscript I maupun J dapat di ambil secara umum. Misalnya, batas bawah subscript baris adalah L1 subscript kolom adalah L2 sedangkan batas atas subscript baris adalah U1 dan untuk kolom adalah U2, maka array dimensi dua tersebut dapat dinotasikan sebagai :

            B(L1:U1, L2:U2) = (B(I,J)), L1 <= 1 <= U1, L2 <=J <= U2

                        Dengan setiap elemen B(I,J) bertipe data T. Banyak nya elemen pada setiap baris adalah U2-L2+1 dan pada setiap kolom adalah U1-L1+1, sehingga banyaknya elemenpada array B semua ada =(U2-L2 +1) * (U1-L1 +1).

CROSS SECTION

            Yang dimaksud dengan cross-section suatu array berdimensi dua adalah pengambilan salah satu subscript, missal subscript baris untuk tetap atau konstan, sementara subscript yang satunya lagi kita ubah-ubah sepanjang rangenya. Notasi yang umum di gunakan adalah notasi* (asterisk) bagi subscript yang berubah-ubah nilainya tersebut.

            Contohnya, penulisan B(*,4) menyatakan semua elemen pada kolom ke-4, yakni (B(1,4),B(2,4), B(3,4) ...., B(M,4)), seperti terlihat pada gambar : 

TRANSPOSE

            Transpose dari suatu array dimensi dua adalah penulisan baris menjadi kolom (kolom menjadi baris) dari suatu array. Jadi transpose dari array berorder M x N adalah array berorder N x M. Transpose dari array B dinotasikan sebagai BT. Berdasarkan definisi, makan jelas B(I,J) = BT (J,I). Contohnya B(3,5) = BT (5,3).

            Pengertian di atas dapat kita perluas untuk array dimensi tiga, dimensi 4, sampai dimensi N. Array dimensi N kita tulis sebagai :

            A(L1:U1, L2:U2, …, LN: UN) = (A(I1, I2, …, IN))

Dengan  Lk <= Ik <= Uk, untuk setiap k = 1, 2, …, N.

Banyaknya elemen dari array A tersebut adalah :

            PI(Uk - Lk + 1) = (U1-L1+1) * (U2 – L2+1) … * (UN -LN + 1)

            Contoh array dimensi tiga adalah penyajian data mengenai banyaknya mahasiswa dari-20 perguruan tinggi di Malang, berdasarkan tingkat (tingkat 1, 2 sampai dengan 5), dan jenis kelamin (pria atau wanita). Misalnya array tersebut dinamakan MHS. Ambil sebagai subscript pertama, tingkta : I = 1, 2….,5; subscript kedua, jenis kelamin (pria = 1, wanita = 2): J=1,2, dan subscript ke-3, perguruan tinggi adalah K =1,2,…,20. Jadi MHS (4,2,17) menyatakan jumlah mahasiswa tingkat 4, wanita, dari perguruan tinggi ke 17.

Array dimensi tiga dapat kita bayangkan seperti ini :

            Pengertian cross-section pada array dimensi banyak, adalah sama seperti pada array dimensi dua.

Misalnya MHS (4,*,17) menunjukan jumlah mahasiswa tingkat 4 dari perguruan tinggi 17 (masing-masing untuk pria serta wanita). MHS (*,*,3) menunjukan jumlah mahasiswa untuk masing-masing tingkat, pria serta wanita, dari perguruan tinggi 3.

C.     MENDEKLARASIKAN ARRAY DALAM BAHASA PEMROGRAMAN

            Misalkan kita hendak mendeklarasikan array TEMP yang merupakan array dimensi satu dengan nilai subscript 1 sampai 24, dan masing-masing elemen bertipe data integer (nilainya santara 0 sampai 99 derajat).

Dalam bahasa COBOL dapat di tulis :

            01 TABEL-TEMP

                        02 TEMP OCCURS 24 TIMES PIC 99.

Dalam bahasa Pascal :

                        Var temp: array 1 . . 24)of integer

            Dalam bahasa BASIC, kita dapat mendefinisikan array TEMP tersebut dengan statement:

                        DIM     TEMP (24)

Tiga hal harus di kemukakan dalam mendeklarasikan suatu array, yakni :

a)      Nama array

b)      Range dari subscript

c)      Tipe data dari elemen array

            Bahasa Pascal memperkenankan batas bawah subscript yang bukan =1, contohnya adalah :

            var grafik : array [-100 ..100] of integer 

            Dalam COBOL subscript harus dimulai dari 1.

            Untuk menyatakan elemen ke-I dari array, COBOL dan BASIC menggunakan kurung biasa, yakni TEMP(I), sedangkan Pascal menggunakan kurung siku, yakni temp[i].

            Untuk mendeklarasikan sebuah array nilai dari 500 mahasiswa untuk 8 mata kuliah, dalam COBOL di tulis :

                        O1 TABEL-NILAI

                                    02 MHS OCCURS 500 TIMES

                                                03 NILAI OCCURS 8 TIMES

                                                PIC 99V9.

Dalam Pascal di tulis :

            var nilai : Array[1..500,1..8] of real

dan dalam BASIC dapat di tulis :

                        DIM     NILAI (500, 8)

Dalam COBOL maksimum dimensi yang dapat di terima adalah 3 (three dimensional). Contohnya :

            01 MHS-TABEL

                        02 TINGKAT OCCURS 5 TIMES

            03 SEX OCCURS 2 TIMES

                                    04 MHS OCCURS 20 TIMES PIC 9(5).

Dan dalam Pascal :

            var mhs : Array[1..5, 1..2, 1..20] of integer

            Dalam bahasa pemrograman seperti FORTRAN dan COBOL, alokasi untuk array dalam storage memerlukan waktu dalam proses kompilasi, karenanya batas bawah dan batas atas harus dikemukakan ketika mendefinisikan array.

            COBOL dan pascal (juga bahasa lain yang memungkinkan pendeklarasian array) mempunyai fasilitas untuk melakukan manipulasi antarelemen array. Operasi yang sesuai dengan tipe data array tersebut dapat dikerjakan dengan mudah, contohnya dalam COBOL

            COMPUTE TOTAL_UPAH(I) = UPAH_PER_JAM(I) * JUMLAH-JAM(l)

Terlihat bahwa ketiga variable di atas adalah array.

            Beberapa bahasa pemrograman memperkenankan operasi array. Sebagai contoh, A adalah array (bertipe real) yang di deklarasikan dalam PL/1, maka A=A+2 adalah operasi untuk menambah setiap elemen dari A dengan bilangan 2.

            Juga dikenal operasi A = A * B. Operasi ini menghasilkan array A baru yang elemennya merupakan hasil kali elemen A (lama) dengan elemen array B yang posisinya bersesuaian. Order array A dan B harus sama.

            Perhatikan bahwa perkalian array ini bukan perkalian matriks yang telah kita kenal. Dalam PL/1, operasi dapat pula dilakukan terhadap cross-section. Sebagai contoh adalah operasi yang menyebabkan NILAI seluruh baris 20 menjadi nol, berikut ini : 

            NILAI (20, * ) = 0

            Operasi VEKTOR(*)= ARRAY1(I,*) *ARRAY(*,J) akan memperkalikan elemen baris ke-I dari ARRAY1 dengan elemen kolom ke-j dari ARRAY2 . Operasi di atas mempunyai efek yang sama seperti loop dalam Bahasa BASIC. :

                        FOR K = 1 TO N

                        VEKTOR(J) = ARRAY1(I,K)* ARRAY2(K,J)

                        NEXT K

D.     PEMETAAN ARRAY KE STORAGE

            Seperti halnya struktur data yang lain, ada beberapa cara untuk menyajikan array di dalam memori. Skema pennyajian dapat dievaluasi berdasarkan 4 karakteristik, yakni :

a)      Kesederhanaan dari akses elemen

b)      Mudah untuk di telusuri

c)      Efisiensi dari utilitasi storage

d)      Mudah dikembangkan

                        Umumnya tidaklah mungkin untuk mengoptimalkan keempat factor tersebut sekaligus. Pandang array satu dimensi NOPEG dengan batas bawah subscript 1, dan batas atas subscript = N. Salah satu cara untuk menyimpan array ini adalah sedemikian sehingga urutan fisik dari elemen sama dengan urutan logic dari elemen. Storage untuk elemen NOPEG(I+1) adalah berdampingan dengan storage untuk elemen NOPEG (I), untuk setiap I = 1, 2, 3,…, N-1. Untuk menghitung alamat (address) awal dari elemen NOPEG (I), diperlukan untuk mengetahui 2 hal yakni :

a)      Address awal dari ruang storage yang di alokasikan bagi array tersebut.

b)      Ukuran dari masing-masing

           

                        Address awal dari array, kita nyatakan dengan B, disebut juga base-location. Misalkan bahwa masing-masing elemen dari array menduduki S byte. Maka, address awal dari elemen ke-I adalah :

                        B + (I-1) * S

                        Sekarang kita perluas persamaan di atas untuk mendapat address dari elemen ke-I dari array yang mempunyai batas bawah subscript tidaksama dengan 1. Perhatikan array Z(4:10), maka address awal dari Z(6) adalah :

                                    B + (64) * S

Untuk array Z2 (-2:2) misalnya, address awal dari Z2(I) adalah :

                                    B + (I -(-2)) * S

Maka secara umum, untuk array :

                                    ARRAY(L:U),

Elemen ARRAY (I) mempunyai address awal

                                    B + (U-L) * S

2.            RECORD

     

      Sebuah record merupakan koleksi satuan data yang heterogen, yakni terdiri dari berbagai type. Satuan data tersebut sering disebut sebagai field dari record. Field di panggil dengan menggunakan namanya masing-masing.Suatu field dapat terdiri atas beberapa subfield.

      Sebagai contoh, data personalia dari seorang pegawai suatu perusahaan di Amerika Serikat, merupakan sebuah record yang dapat terdiri dari berbagai field, dan subfield seperti berikut ini :

1    NOMOR-JAMINAN-SOSIAL

2                NAMA, yang terdiri atas :

                  NAMA-BELAKANG

                  NAMA-DEPAN

                  NAMA-TENGAH

3    ALAMAT, terdiri atas :

                  JALAN

                  NOMOR RUMAH

                  NAMA-JALAN

                  KOTA

                  NEGARA-BAGIAN

                  KODE-POS

            4    MENIKAH

Dan sebagainya lagi.

            Pada record tersebut di atas, satuan data seperti NAMA BELAKANGAN ataupun KOTA merupakan tipe data string, sedangkan data lain seperti GAJI POKOK, TUNJANGAN JABATAN dan berbagai data yang akan diolah secara matematis akan disimpan dengan tipe data numeric, bisa integer maupun real. Data MENIKAH bisa digunakan tipe data Boolean atau logical.

            Seperti telah kita paparkan terdahulu, array berbeda dengan record, yakni array bersifat homogeny (terdiri dari tipe data yang sama), dan komponen array tidak memiliki nama sendiri, dan hanya diberi identifikasi oleh posisi mereka di dalam array. Penggunaan keduanya di dalam program juga berbeda, jika penggunaan array pada umumnya akan di simpan di memori utama computer (bersifat sementara), sedangkan record biasanya digunakan dalam filling yang akan disimpan di memori sekunder computer, seperti hard disk, disket, dan lainnya.

            Sebuah record memberi informasi tentang berbagai kondisi dari obyek pada permasalahan yang nyata sehari hari. Setiap field memberi uraian tentang satu atribut dari obyeknya. Sebuah record biasanya diberi identifikasi oleh key-nya. Key atau kunci adalah salah satu atau lebih field yang di pilih untuk tujuan penyampaian informasi yang terjadi di dalam record yang bersangkutan.

            Koleksi dari record yang sama struktur fieldnya disebut suatu file atau berj=kas. Jadi, koleksi dari record semua pegawai perusahaan membentuk sebuah file personalia. Pada umunya record disimpan membentuk file, dalam urutan sesuai dengan nilai dari key masing-masing. Di dalam sautu file PERSONALIA, field NOMOR JAMINAN SOSIAL dari seorang pegawai dapat digunakan sebagai key. Di dalam bahasa pemrograman tingkat tinggi, record dapat dinyatakan sebagai struktur data (COBOL dan PL/1) dapat diadakan spesifikasi tentang nama record, field dan subfield yang bersangkutan.

            Record tersebut juga di beri nomor seperti diperlihatkan di dalam contoh di bawah ini. Deklarasi berikut ini dapat digunakan untuk menuliskan record dari file PERSONALIA di atas.

                        01 PEGAWAI

                                    02 NOMOR-JAMINAN-SOSIAL

                                    02 NAMA

                                                03 NAMA-BELAKANG

                                                03 NAMA-DEPAN

                                                03 NAMA-TENGAH

                                    02 ALAMAT

                                                03 JALAN

                                                            04 NOMOR RUMAH

                                                            04 NAMA-JALAN

                                                03 KOTA

                                                03 NEGARA-BAGIAN

                                                03 KODE-POS

                                                02 MENIKAH

(yang harus dilengkapi dengan Picture masing-masing field dan subfield)

            Record tersebut dinyatakan di dalam memori sebagai berikut :

            Secara fisik, field record tersebut biasanya disimpan berurutan di dalam lokasi storage, bahkan sering di satukan. Record biasanya di simpan sebgai file di dalam storage pembantu, dan jika perlu, sebagian di simpan di dalam memori utama. File merupakan organisasi data utama di dalam proses pengolahan informasi.

            Sebagai gambaran sederhana, panda sebuah table dengan sejumlah baris dan kolom. Table tersebut dapat disebut sebagai sebuah file, sedangkan setiap baris table tersebut disebut dengan record, dan setiap kolom dari table disebut dengan field.

STRUKTUR DATA PERTEMUAN 1

PENDAHULUAN

STRUKTUR DATA

           Struktur data adalah suatu koleksi atau kelompok data yang dapat dikarakterisasikan oleh organisasi serta operasi yang di definisikan terhadapnya. Algoritma : barisan langkah - langkah untuk menyelesaikan sebuah program. Inputnya harus data. Sebuah program belum tentu Algoritma. Sebuah Algoritma harus bisa di implementasikan sebuah program.

Jadi Struktur data dan Algoritma adalah sebuah program.

BAB 1

JENIS JENIS DATA

            Data secara umum dapat di bagi menjadi dua yaitu :

• ü        Tipe data sederhana  

1.       Tunggal ( data primitive)  : Integer, Real, Boolean, Karaker.

2.       Majemuk ( data campuran) : String

• ü         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

 INTEGER

            Suatu integer adalah suatu anggota dari himpunan bilangan :

{..., -(n+1), -n, ..., -2, -1, 0, 1, 2, ..., n, n+1, ...}

Operasi dasar yang ada dalam integer yaitu :

• ·         Penjumlahan
• ·         Pengurangan
• ·         Perkalian
• ·         Pembagian
• ·         Perpangkatan

Pembagian Integer (DIV)

Hasil dari pembagian integer DIV adalah integer (menghilangkan bagian pecahan dari hasil pembagian)

Contoh : 17 DIV 3 = 5

Selain itu terdapat operasi MOD (Modulo) : sisa dari pembagian.

Contoh : 17 MOD 3 = 2

Masing - masing operator pada operasi di atas, yang bekerja terhadap sepasang integer (operand) disebut sebagai Binary Operator. Sedangkan operator yang hanya bekerja terhadap satu operand saja disebut sebagai Unary Operator. 

 REAL

            Data numeric yang bukan termasuk integer, di golongkan dalam jenis data real. Jenis data ini di tulis menggunakan titik decimal (atau koma decimal). Bilangan real dimasukan ke dalam memori computer memakai system floating point, merupakan versi yang di sebut Scientific Motation. Di sini penyajiannya terdiri atas dua bagian, yaitu : mantissa (pecahan) dan eksponen.

BOOLEAN

            Jenis data ini di sebut juga jenis data logical. Elemen dari jenis data ini mempunyai nilai salah satu dari true atau false.

Operator yang di kenal pada Boolean, yaitu :

• Operator Logika, yaitu : AND, OR, NOT.

·         Operator AND akan menghasilkan nilai true, jika kedua operand bernilai true.

·         Operator OR akan menghasilkan nilai true, jika salah satu operand bernilai true.

·         Operator NOT merupakan “precedence” dari operator AND dan OR.

• Dalam suatu ekspresi yang tidak menggunakan tanda kurung, operator NOT harus di evaluasi sebelum operator AND dan OR.

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

Contoh : 6 < 8 = True

             9 > 8 = False

KARAKTER

Jenis data karakter merupakan elemen dari suatu himpunan yang terdiri atas bilangan,

abjad dan simbol khusus.

(0,1,...,8,9, A, B, ..., Y,Z, +, -,*,ã, ...}

STRING

            Barisan hingga karakter yang di bentuk oleh suatu kumpulan dari karakter. Karakter yang di gunakan untuk membentuk suatu string di sebut alphabet. Dalam penulisannya, suatu string berada dalam tanda “aphosthrope”.

Contoh :

Misal diberikan himpunan alfabet A = {C,D,1}.

String yang dapat dibentuk dari alfabet di atas antara lain :

‘CD1’,’CDD’,’DDC’,’CDC1’,... dan sebagainya, termasuk “null string” atau “empty

string”

Himpunan tak hingga dari string yang dibentuk oleh alfabet A disebut VOCABULARY,

Notasi : VA atau A*

Jika suatu string dibentuk dari alfabet {0,1}, maka string yang terbentuk disebut dengan “Bit String”.