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 6 : Representasi Fisik List Linier 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.

Lanjutan Operasi Primitif List 1.1. Menyisipkan elemen di akhir List Menyisipkan sebuah elemen beralamat P sebagai elemen terakhir sebuah list linier. List yang akan disisipkan elemen padanya, bisa kosong atau tidak. Contoh kasus insert after dengan List tidak kosong seperti gambar di bawah. K-Awal

K-Akhir

1

Q


Procedure InsertLast1(Input/Output L: List, Input P : address) {K. Awal : List L mungkin kosong, P sudah dialokasi, P ≠ Nil, Next (P) = Nil K. Akhir : P adalah elemen terakhir list L Proses

: Insert sebuah elemen

beralamat P sbg elemen terakhir dari list linier L yg mungkin kosong } Kamus/Deklarasi Nama Last : address { address untuk traversal} Algoritma If

(First (L) = Nil) then { insert sebagai elemen pertama} InsertFirst(L, P)

Else { Traversal list sampai address terakhir} Last ← First (L) While (Next (Last ) ≠ Nil ) do Last ←

Next (Last )

{Next ( Last) = Nil, Last adalah elemen terakhir insert P after last } InsertAfter (P, Last) II. List Berkait Representai lojik list linier L dengan P Adalah Address telah didefinisikan yaitu dengan cara: First (L), Next (P) dan info P. Modul ini akan membahas representasi list secara fisik, yaitu implementasi struktur data list yang dapat ditangani oleh pemroses bahasa pemrogaman. Tidak semua bahasa pemrograman mungkin dapat merepresentasikan representasi list yang dibahas dalam modul ini.

Penulisan algoritma representasi fisik list linier pada dasarnya adalah

menterjemahkan struktur lojik yang sudah dibahas sebelumnya.

2

Q


Representasi fisik list linier dapat berupa BERKAIT maupun KONTIGU. Representasi BERKAIT dapat diimplementasikan dalam dua struktur yaitu pointer dan tebel. Sedangkan kontigu hanya dapat diimplementasikan dengan tabel. 2. Representasi Fisik List Liner dengan BERKAIT 2.1. Representasi Fisiki List linier BERKAIT dengan “pointer”. Contoh representasi list liner berkait dengan pointer : Kamus/Deklarasi Nama Type InfoType = .........................{tipe terdefinisi} Type ElmtList : Address : Pointer to ElmtList Type List : L : List {Elemen list pertama} {Penggunaan dalam algoritma} P : Address {Address

yang

digunakan

untuk

traversal,

maka

penulisan

untuk

mengaksesnya adalah Next(P) menjadi P^. Next Info(P) menjadi P^.Info } 2.2. Representasi Fisiki List linier BERKAIT dengan tabel. Jika Bahasa Pemrograman tidak menyediakan struktur data pointer (dengan primitif Allocate, Freee, Saturate), maka kita bisa melakukan implementasi fisik alamat dengan index tabel. Dengan demikian sebenarnya yang disebut pengelolaan “memori” dalam hal ini adalah dengan alamat memori yang sebenarnya diacu melalui tabel. Dengan demikian kita harus mendefinisikan tabel Global yang setiap elemennya adalah emelen list yang diacu sebagai alamat.

3

Q


Kamus/Deklarasi Nama Type InfoType = .........................{tipe terdefinisi} Type ElmtList : Address : integer [IndexMin....IndexMax] {Tabel ini mengacu pada memori global} Constant IndexMing : Integer = 1 Constant Index Max : Integer = 100 Constant Nil : Integher = 0 {Nil address tak terdefinisi di luar Index Min dan IndexMax} TabElmt: array[IndexMin....IndexMax] of ElmtList FirstAvail: Address {alamat pertama list siap digunakan } {Maka

penulisan

First(L)

menjadi

First,

Next(P)

menjadi

TabElemList[P].Next, dan Info(P) menjadi TabElmList[P].Info} Function MemFull {mengirimkan true, jika memori sudah habis, FirstAvail == Nil} Procedure InitTab {Inisiasi tabel yang akan digunakan sebagi memori list linier} {IS sembarang, FS TabElmList[IndexMin..IndexMax] siap digunakan sebagai elemen list berkait. Elemen pertama yang abailabel adalah FirstAvail=1, Next(i) = i+1 untuk i di dalam [IndexMin...IndexMax], Next(IndexMax) ==Nil} Procedure AllocTab (Output: P : Address) {Mengambil sebuah elemen P Siap pakai pada awal list FirstAvail} {IS FirstAvail mungkin kosong, FS jika FirstAvail tidak Nil, P adalah FirstAvail, dan FirstAvail yang baru adalah Next(FirstAvail)} {Jika FirstAvail == Nil, P == Nil, tulis pesan “Tidak tersedia lagi elemen siap pakai} Procedure DeAllocTab (Input: P : Address)

4


Q

{Mengembalikan sebuah elemen P pada awal list FirstAvail} {IS FirstAvail mungkin kosong, P tidak kosong. FS FirstAvail =P adalah FirstAvail, dan FirstAvail yang baru adalah Next(FirstAvail)} 2.3. Menguji ketersediaan memori Function MemFull {Mengirimkan true jika memori habis, FirstAvail == Nil} Kamus/Deklarasi Algoritma (FirstAvail == NIL){ambil elemen pertama} 2.4. Procedure InitTab Procedure InitTab {Inisiasi tabel yang akan digunakan sebagi memori list linier} {IS sembarang, FS TabElmList[IndexMin..IndexMax] siap digunakan sebagai elemen list berkait. Elemen pertama yang abailabel adalah FirstAvail=1, Next(i) = i+1 untuk i di dalam [IndexMin...IndexMax], Next(IndexMax) ==Nil} Kamus/Deklarasi P : address { address untuk traversal , type terdefenisi } Algoritma U traversal [IndexMin...IndexMax-1] TabElmList[P].Next P+ 1 TabElmList[IndexMax].Next Nil FirstAcail IndexMin 2.5. Procedure AllocTab Procedure AllocTab (Output: P : Address) {Mengambil sebuah elemen P Siap pakai pada awal list FirstAvail}

5


Q

{IS FirstAvail mungkin kosong, FS jika FirstAvail tidak Nil, P adalah FirstAvail, dan FirstAvail yang baru adalah Next(FirstAvail)} {Jika FirstAvail == Nil, P == Nil, tulis pesan “Tidak tersedia lagi elemen siap pakai} Kamus/Deklarasi Algoritma If (not MemFull) then P TabElmList[FirstAvail] Else Output(“Tidak Tersedia lagi elemen memori siap pakai”) P Nil 2.6. Procedure DeAllocTab Procedure DeAllocTab (Input: P : Address) {Mengembalikan sebuah elemen P pada awal list FirstAvail} {IS FirstAvail mungkin kosong, P tidak kosong. FS FirstAvail =P adalah FirstAvail, dan FirstAvail yang baru adalah Next(FirstAvail)} Kamus/Deklarasi Algoritma TabElmList[P].Next FirstAvail FirstAvail P Ilustrasi berikut menggambarkan beberapa keadan List berkait dengan tabel

6


Q

3. Representasi Fisik List Liner secara kontigu Representasi

list

secara

kontigu

hanya

dapat

diimplementasikan

dengan

menggunakan tabel, karena hanya tabel yang dapat merepresentasikan struktur dat asecara kontigu. Setiap elemen tabel mengandung informasi info, sedangkan informasi mengenai Next tidak perlu disimpan secara eksplisit kerena secara implisit sudah ada dalam struktur data. Elemen terakhir tidak dapat dikenali dengan NEXT, karena Next tidak disimpan secara eksplisit. Elemen terakhir dikenai dari alamatnya P = N, N adalah lokasi pada tabel tempat peyimpanan elemen terakhir. Representasi list linier secara kontigu dengan tabel adalah :

7


Q

Kamus/Deklarasi Nama Constant IndexMin : Integer = 1 Constant Index Max : Integer = 100 Constant Nil : Integer = 0 {Nil address tak terdefinisi di luar Index Min dan IndexMax} Type InfoType = .........................{tipe terdefinisi} Info : Infotype {tidak perlu mengandung Next} TabElmtList: array[IndexMin....IndexMax] of Info Type Address : integer [IndexMin....IndexMax] {Deklarasi nama untuk variabel kerja} N : address {alamat elemen terakhir. Karena field NEXT tidak ada secaa eksplisit, maka satu = satunya jalan untuk mengenali elemen terekahir adalah dengan addressnya} Type List : Address First : Address {alamat pertama list siap digunakan } P : Address {Maka First(L) ...Last (L) adaah index efektif elemen tabel anggota list. Next(P) menjadi P P + 1; dan Info(P) menjadi TabElmList[P].Info}

8

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

Recommend Documents