1. Inggriani Liem Catatan Kuliah Algoritma & Pemrograman, Jurusan Teknik Informatika ITB

MODUL PERKULIAHAN PROGRAM STUDI – S1 TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER Mata Kuliah : Algoritma & Struktur Data Dosen Pengampu : Mujiono Sadikin ST., MT., CISA

Q

Pertemuan Ke 3 Referensi: 1. Inggriani Liem. 2003. Catatan Kuliah Algoritma & Pemrograman, Jurusan Teknik Informatika ITB 2. Rinaldi Munir. 2003. Algoritma dan Pemrograman II. Bandung : Penerbit Informatika I.

Tabel/Larik/Array Tabel/larik/array adalah struktur data yang menyimpan sekumpulan elemen yang bertipe sama. Setiap elemen dalam tabel diakses langsung melalui indeksnya. Dengan demikian indeks larik harus tipe data yang mempunyai keterurutuan misalnya integer atau character.

Cara mengakses elemen larik dalam notasi algoritma ditulis sbegai

berikut : T[index] adalah elemen ke index dari larik T T[1] adalah elemen ke 1 dari larik T T[100] adalah elemen ke 100 dari larik T T[index].x adalah elemen ke index komponen x dari larik T T[1] .x adalah elemen ke 1 komponen x dari larik T T[100] .x adalah elemen ke 100 komponen x dari larik T Berikut adalah gambaran tabel 1

120

a

<8.6,7.8>

2

90

b

<10.0,2.8>

3

34

c

<4.5,6,8>

4

56

d

<23.45,4.67>

5

78

e

6

1

f

7

2

g

8

3

h

...

5

...

100

6

z

(a) Larik berisi tipe integer

(b) larik berisi tipe Point.

Q


Jika nama larik pertama (a) adalah A maka A[1] = 120, A[100] = 6. Jika nama larik kedua (b) adalah TPoint maka TP[a] = <8.6,7.8>, TP[a].X = 8.6, TP[b].Y = <2.8> 1. Deklarasi Tabel Deklarasi tabel dituliskan sebagai berikut : : array [Nmin....Nmax] of TipeElemen Dengan Nmin adadah index minimum, Nmax index maksiumum, TipeElemen adalah tipe elemen isi tabel. Contoh “ T : array [1....100] of Integer {T adalah tabel dengan index 1 .s.d. 100 yang isinya bertipe inteher} TPoint : array [1....100] of Point {T adalah tabel dengan index 1 .s.d. 100 yang isinya bertipe Point} 2. Pemrosesan terhadap Tabel Pemrosesan dasar terhadap tabel antara lain : Pengisian, Pencarian, Pengurutan. Berikut beberapa contoh primitif pemrosesan terhadap tabel. 2.1. Pengisan Tabel 2.1.1. Pengisian

tabel

dengan

skema traversal.

Traversal

adalah

skema

“menjalani” semua isi dalam tabel tanpa kecuali, dari index terkecil (pertama) sampai dengan index terbesar (terakhir). Algoritma di bawah digunakan untuk melakukan pengisian tabel dengan langkah – langkah : 1. Menerima masukan jumlah elemen N tabel yang akan di isi dengan 1 <= N <= Nmax. Nmax adalah index maksimum tabel Kamus/Deklarasi variable Constant Nmin : integer = 1; Constant Nmax : integer = 100; T : array [Nmin....Nmax] of Integer; {temperatur air} N : integer {jumlah maksimum } I : integer {pencacah}


Q

Algoritma Repeat Input (N) Until (N > 0) {tidak akan selesai melakukan input N selama N <= 0} I traversal [1...N] input(T[I]) 2.1.2. Pengisian tabel dengan menerima masukan dari alat masukan (keyboard). Jika maukan bernilai -99 maka proses pengisian tabel dianggap selesai. Proses isi tabel juga dihentikan jika semua index sudah terisi, sebanyak Nmax. Nmax adalah index maksimum tabel Kamus/Deklarasi variable Constant Nmin : integer = 1; Constant Nmax : integer = 100; T : array [Nmin....Nmax] of Integer; {temperatur air} N : integer {jumlah maksimum } I : integer {pencacah} X : integer { adalah elemen yang dimasukkan} Algoritma I Nmin; Input (X) While (i <= Nmax) and (X <> -99) do T[I] <= X I I +1 Input(X)


Q

{(i > Nmax) or (X == -99)} If (I > Nmax) then Output (“Tabel penuh”) 2.2. Pencarian Isi Tabel secara terurut Misalnya diketahui suatu tabel T [1....Nmax] yang elemennya merupakan bilangan integer. Persoalan yang diberikan adalah mencari apakah integer X ada di dalam tabel. Proses pencarian dilakukan secara berurutan mulai dari T[Nmin] s.d T[IX] di mana IX adalah index di mana X berada atau sampai dengan T[Nmax], yaitu pencarian dilakukan sampai dengan elemen terakhir pada tabel. Pada pencarian ini digunakan deklarasi global sebagai berikut Constant Nmin : integer = 1; Constant Nmax : integer = 100; Type TabInt : array [Nmin....Nmax] of Integer; { definisi tipe tabel integer } T : TabInt

2.2.1. Prsedur Pencarian versi 1, tanp boolean Procedure SeqSearch1(Input T: TabInt; N:Integer; X: Integer; Output : IX :integer) {Memeriksa apakah X ada didalam tabel T yang berindex dari 1 s.d N. Jika X ada di dalam tabel maka IX akan berisi index terkecil tempat X berada. Jika X tidak ada didalam tabel, IX berisi 0} Kamus/Deklarasi I : integer {pencacah}


Q

Algoritma I <= 1 While (i < N) and (T[i] <> X) do I <= I+1 {i = N or T[i] = X} Depend on T, i, X T[i] = X : IX I TI <> X : IX 0 2.2.2. Prsedur Pencarian versi 2, dengan menggunakan boolean Procedure SeqSearch2(Input T: TabInt; N:Integer; X: Integer; Output : IX :integer; Found : Boolean) {Memeriksa apakah X ada didalam tabel T yang berindex dari 1 s.d N. Jika X ada di dalam tabel maka IX akan berisi index terkecil tempat X berada, Found berisi true. Jika X tidak ada didalam tabel, IX berisi 0 found berisi false} Kamus/Deklarasi I : integer {pencacah} Algoritma I1 Found false While (i <= N) and (not Found) do If T[I] == X then Found True Else I <= I+1 {i > N or found }


Q

Depend on Found Found : IX I Not Found : IX 0 2.3. Pencarian pada Tabel yang isinya terurut menaik Misalnya diketahui suatu tabel T [1....Nmax] yang telah terisi dan elemennya merupakan bilangan integer yang terurut menaik. Persoalan yang diberikan adalah mencari apakah integer X ada di dalam tabel. Proses pencarian dilakukan secara berurutan mulai dari T[Nmin] s.d T[IX] di mana IX adalah index di mana X berada atau sampai dengan T[Nmax], yaitu pencarian dilakukan tidak harus dilakukan sampai dengan elemen terakhir pada tabel. Misalnya N = 6, T {2,4,5,7,8,9}, X= 5 maka pencarian dilakukan terhadap {2,4,5}, IX= 3; Misalnya N = 10, T {2,4,5,7,8,9,20,22,45,60}, X= 35 maka pencarian dilakukan terhadap {2,4,5, 7,8,9,20,22,45}, IX= 0; Pada pencarian ini digunakan deklarasi global sebagai berikut Constant Nmin : integer = 1; Constant Nmax : integer = 100; Type TabInt : array [Nmin....Nmax] of Integer; { definisi tipe tabel integer } T : TabInt

2.3.1. Prsedur Pencarian Tabel terurut Procedure SeqSearchSorted(Input T: TabInt; N:Integer; X: Integer; Output : IX :integer) {Memeriksa apakah X ada didalam tabel T yang berindex dari 1 s.d N dengan isi elemen adalah integer terurut menaik. Jika X ada di dalam tabel maka IX akan berisi index terkecil tempat X berada. Jika X tidak ada didalam tabel, IX berisi 0}


Q

Kamus/Deklarasi I : integer {pencacah} Algoritma I <= 1 While (i < N) and (T[i] < X) do I <= I+1 {i = N or T[i] = X} Depend on T, i, X T[i] == X : IX I TI <> X : IX 0 {TI > X} 2.4. Pencarian pada Tabel yang isinya terurut menaik dengan metode Binary Search Dichotomic Misalnya diketahui suatu tabel T [1....Nmax] yang telah terisi dan elemennya merupakan bilangan integer yang terurut menaik. Persoalan yang diberikan adalah mencari apakah integer X ada di dalam tabel. Bayangkan index tabel disusun dari atas kebawah artinya index terkecil di atas, dan index terbesar di bawah. Proses pencarian dilakukan dengan membandingkan X dengan elemen yang di tengah. Jika X lebih kecil dari yang di tengah, maka pencarian di fokuskan di belahan setengah atas, sebaliknya jika X lebih besar dari tengah maka pencarian difokuskan di belahan setengah bawah. Proses ini diluang sampai ditemukan atau tabel tidak dapat dibagi setengah – setengah lagi. Proses pencarian ini hanya bisa digunakan untuk tabel dengan elemen terurut menaik. Perhatikan ilustrasi berikut, memeriksa apakah 12 ada di dalam tabel : X=

10

Index ==> Atas

1

Index 1

1

Index 1

1

1

Q


==> Tengah

==> Bawah

2

4

2

4

2

4

3

6

3

6

3

6

4

7

4

7

4

7

5

9

5

9

5

9

6

10

6

10

6

10

7

12

7

12

7

12

8

14

8

14

8

14

9

15

9

15

9

15

10

18

10

18

10

18

==> Atas

==> Tengah

==> Bawah

==> Atas ==> Bawah,Tengah

2.4.1. Prsedur Pencarian Tabel terurut dengan Binary Search Procedure BinarySearch(Input T: TabInt; N:Integer; X: Integer; Output : IX :integer; Found : Boolean) {Memeriksa apakah X ada didalam tabel T yang berindex dari 1 s.d N. Elemen Tabel terurut menaik T[1]<= T[2] <= T[3]...., pencarian dilakuan dengan model Binary Search dichotomic.} Kamus/Deklarasi Atas, Bawah, Tengah : integer {pencacah yang digunakan sebagai batas pemeriksaan} Algoritma Atas 1; Bawah N Found false ; IX 0; While ( Atas <= Bawah ) and (not Found) do Tengah <= (Atas + Bawah ) div 2


Q

Depend on T, Tengah, X X = T[Tengah] Found True; IX Tengah X > T[Tengah] : Atas Tengah + 1 X < T[Tengah] : Bawah Tengah - 1 {Atas > Bawah or Found}

3. Latihan 3.1. Mencari nilai minimal Ujian Permasalahan : Nilai ujian mahasiswa Kelas Algoritma dimasukkan ke dalam tabel yang tiap elemennya merupakan komponen NIM dan Nilai. Nim bertipe Integer dan Nilai bertipe riil. Diasumsikan tabel Nilai sudah berisi. Tugas yang harus anda lakukan adalah mengeluarkan NIM dan Nilai mahasiswa dengan nilai tertinggi dan nilai terendah. Contoh : Jika tabel berisi {(41501,80.5), (41502,90.5), (41503,60)}, maka outputnya adalah “Nilai minimum NIM 41503, nilai – 60”, “Nilai maksimum NIM 41502, nilai 90.5” 3.2. Menghitung nilai rata – rata Permasalahan : Diterima masukan berupa bilangan riiel lebih besar atau sama dengan nol sebanyak N kali. Setiap menerima masukan bilangan riil tersebut dimasukkan ke dalam tabel yang index maksimumnya N. Hitunglha nilai rata – ratanya. Contoh : jika berturut turut dimasukkan nilai riil tiga kali yatu 3.0, 1.0, 7.0, 5.0, maka outputnya adalah 5.0 ==== End of Document ===

1. Inggriani Liem Catatan Kuliah Algoritma & Pemrograman, Jurusan Teknik Informatika ITB

Recommend Documents