4.1. Definisi
List linier adalah sekumpulan elemen bertype sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari 2 bagian :
Type Elmtlist = record
< Info : InfoType,
Next : address >
Dengan Info Type adalah sebuah type terdefenisi yang menyimpan informasi sebuah elemen list ; Next adalah address dari elemen berikutnya ( suksesor ).
Dengan demikian, jika didefinisikan First adalah alamt elemen pertama list, maka elemen berikutnya dapat diakses secara suksesif dari elemen pertama tersebut
Jadi, sebuah list linier dikenali :
elemen pertamanya, biasanya melalui alamat elemen pertama yang disebut : First
alamat elemen berikutnya ( suksesor ), jika kita mengetahui alamat sebuah elemen , yang dapat diakses melalui field NEXT
setiap elemen mempunyai alamat, yaitu tempat elemen disimpan dapat diacu.Untuk mengacu sebuah elemen , alamat harus terdefenisi . Dengan alamat tersebut Informasi yang tersimpan pada elemen list dapat diakses .
elemen terakhirnya. Ada berbagai cara untuk mengenali elemen akhir
Jika L adalah list , dan P adalah address :
Alamat elemen pertama list L dapat diacu
dengan notasi :
First (L)
Elemen yang diacu oleh P dapat dikonsultasi
informasinya dengan notasi :
Info(P)
Next(P)
Beberapa definisi :
1. List L adalah List kosong , jika First (L) = Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena Next(Last) =Nil
Nil adalah pengganti Null, dalam bahasa C perubahan ini dituliskan dengan
#define Nil Null
Bagian Deklarasi dari algoritma pada List Linier :
{Deklarasi}
type InfoType = … {Sebuah type terdefinisi}
type Address pointer to ElmtL
type ElmtL = record
type List = record
atau dapat juga
type List = Address
{Deklarasi Nama Peubah}
L : List
P : Address
{Deklarasi Nama Peubah}
L : List
P : Address
{Maka penulisan
First (L) menjadi (L)
Next (P) menjadi (P)->info
Info (P) menjadi (P)->next
Null menjadi Nil }
II. Skema traversal untuk list linier
List terdiri dari sekumpulan elemen. Seringkali diperlukan untuk memproses setiap elemen list dengan cara yang sama. Karena itu salah primitif operasi konsultasi dasar pada struktur list adalah traversal, yaitu “mengunjungi” setiap elemen list untuk diproses.
Karena Urutan akses adalah dari elemen pertama sampai dengan elemen terakhir, maka traversal list secara natural dilakukan dari elemen pertama, suksesornya, dan seterusnya sampai dengan elemen terakhir.
Skema traversal yang dipakai adalah Sbb :
Procedure SKEMAListTransversal1( Input L : List )
{K. Awal : List L terdefinisi , mungkin kosong }
{K. Akhir : semua elemen list L dikunjungi dan telah diproses }
{Proses : Traversal sebuah list linier. Dengan MARK, tanpa pemrosesan khusus pada list kosong}
{Deklarasi}
{Deklarasi}
P : address { address untuk traversal , type terdefenisi }
{Deskripsi}
Inisialisasi
P ← First ( L ) { First Element }
While ( P ≠Nil ) do
Proses ( P )
P ← Next ( P ) { Next element }
endwhile
Terminasi
Procedure SKEMAListTransversal 2( Input L : List )
{ K. Awal : List L terdefenisi , mungkin kosong }
{ K. Akhir : semua elemen list L “dikunjungan “ dan telah diproses }
{ Proses : Transversal sebuah list linier yang diidentifikasi oleh elemen pertama L , Dengan MARK dan pemrosesan khusus pada list kosong }
{Deklarasi}
{Deklarasi}
P : address {address untuk traversal , type terdefenisi }
{Deskripsi}
If (First ( L ) = Nil) then
Write ( ‘List kosong ‘ )
else
Insialisasi
P ← First ( L ) { First Element }
Repeat
Proses ( P )
P ← Next ( P ) { Next element }
until P=Nil
Terminasi
III. Skema Sequential Search untuk list linier
Selain traversal, proses pencarian suatu elemen list adalah primitif yang sering kali didefinisikan pada struktur list. Pencarian dapat berdasarkan nilai, atau berdasarkan alamat.
III.1. Search suatu Nilai, output adalah address
Search ini sering dipakai untuk mengenali suatu elemen list berdasarkan nilai informasi yang disimpan pada elemen yang dicari. Biasanya dengan alamat yang ditemukan, akan dilakukan suatu proses terhadap elemen list tersebut.
Procedure SKEMAListSearch1 ( Input L : List, X : InfoType, Output P : address, Found: Boolean )
{ K. Awal : List linier L sudah terdefinisi dan siap dikonsultasi, X terdefenisi }
{ K.Akhir : P : address pada pencarian beurutan, dimana X diketemukan, P = Nil jika tidak ketemu, Found berharga true jika harga X yang dicari ketemu, false jika tidak }
{Proses : Sequential Search harga X pada sebuah list linier L, Semua elemen diperiksa dengan intruksi yang sama, versi dengan Boolean}
{Deklarasi}
{Deskripsi}
P ← First ( L )
Found ← false
While ( P ≠ Nil ) and ( not found ) do
if X = Info (P) then
Found ←True
else
P ← Next (P)
endif
endwhile { P = Nil or Found}
{Jika Found maka P adalah address dimana harga yang dicari diketemukan}
III. 2. Search suatu Elemen yang beralamat tertentu
Procedure SKEMAList Search@( Input L : List, P : address, Found: Boolean )
{K. Awal : List linier L sudah terdefinisi dan siap dikonsultasi, X terdefenisi }
{K.Akhir : Jika ada elemen list beralamat P, Found berharga true, Jika tidak ada elemen list beralamat P, Found berharga false }
{Proses : Sequential Search @ P pada sebuah list linier L, Semua elemen diperiksa dengan intruksi yang sama }
{Deklarasi}
Pt : address
{Deskripsi}
Pt ← First ( L )
Found ← false
While ( Pt ≠ Nil ) and ( not found ) do
if Pt = P then
Found ← true
else
Pt ← Next (Pt)
endif
endwhile { Pt = Nil or Found}
{ Jika Found maka P adalah elemen list}
IV. Definisi fungsional list linier dan algoritmanya
Secara fungsional, pada sebuah list linier biasanya dilakukan pembuatan, penambahan atau penghapusan elemen yang dapat ditulis sebagai berkut :
Jika diberikan L, L1 dan L2 adalah list linier dengan elemen ElmtList, maka operasi yang dapat dilakukan :
ListEmpty, CreateList, Insert, Delete, Concat dan UpdateList
IV. 1. Pengetesan List Kosong
Pemeriksaan apakah sebuah list kosong sangat penting, karena Keadaan Awal dan Keadaan Akhir beberapa prosedur harus didefinisikan berdasarkan keadaan list. Operasi pada list kosong sering kali membutuhkan penanganan khusus Realisasi algoritmik dari definisi fungsional ini adalah sebuah fungsi sebagai berikut.
Function IsEmptyList (L : List ) → boolean
{ Test apakah sebuah list L kosong, Mengirimkan true jika list kosong, false jika tidak kosong}
{Deklarasi}
{Deskripsi}
return(First (L) = Nil)
IV.2 Pembuatan sebuah elemen pada list linier
Pembuatan sebuah list berarti membuat sebuat list KOSONG, yang selanjutnya siap diproses (ditambah elemennya, dsb). Realisasi algoritmik dari defenisi funfsional ini adalah sebuah prosedur sebagai berikut.
Procedure CreateList( Output L : List )
{K. Awal : Sembarang }
K. Akhir : terbentuk list L yang kosong : First (L) diinisialisasi dengan NIL )
Proses : Membuat list kosong}
{Deklarasi}
{Deskripsi}
First (L) ← Nil
IV. 3 Penyisipan sebuah elemen pada list linier
Fungsi insert (penyisipan) harus dijabarkan lebih rinci, karena dapat menjadi penyisipan sebagai elemen pertama, setelah sebuah address P atau penyisipan menjadi elemen terakhir atau bahkan menjadi elemen ditengah
Penyisipan sebuah elemen dapat dilakukan terhadap sebuah elemen yang sudah dialokasi (diketahui address-nya ), atau sebuah elemen yang hanya diketahui nilai Info-nya (berarti belum dialokasi).
IV. 2.1. INSERT-First (Address)
Menambahkan sebuah elemen yang diketahui alamatnya sebagai elemen pertama list.
Procedure InsertFirst (Input/Output L:List, Input P: address)
{K. Awal : List L mungkin kosong
{K. Akhir : P adalah elemen pertama list L}
{Proses : Insert sebuah elemen beralamat P sebagai elemen pertama list linier L yang mungkin kosong}
{Deklarasi}
{Deskripsi}
Next (P) ← First (L)
First (L) ← P
IV.2.2 INSERT-First (Nilai)
Menambahkan sebuah elemen yang diketahui nilainya sebagai elemen pertama list.
Procedure InsFirst (Input/output L :List, Input E : infotype )
{ K. Awal : List L mungkin kosong }
{ K. Akhir : Sebuah elemen dialokasikan dan menjadi elemen pertama list L, jika alokasi berhasil. Jika alokasi gagal list tetap seperti semula }
{ Proses : Insert sebuah elemen sebagai elemen pertama list}
{Deklarasi}
P : address
{Deskripsi}
Alokasi (P)
If P ≠ Nil then
Info (P) ← E
Next (P) ← First (L)
First (L) ← P
endif
IV.2.2. INSERT-AFTER
Menyisihkan sebuah elemen beralamat P sebagai suksesor dari sebuah elemen list linier yang beralamat Prec
Procedure InsertAfter ( Input P, Prec: address )
{K. Awal : Prec adalah elemen list, prec ≠ Nil, P sudah dialokasikan, P ≠ Nil, Next (P) = Nil
K. Akhir : P menjadi suksesor Prec
Proses : Insert sebuah elemen beralamat P pada List linier L}
{Deklarasi}
{Deskripsi}
Next (P) ← Next (Prec)
Next (Prec) ← P
IV. 2.3. INSERT – Last
Menyisipkan sebuah elemen beralamat P sebagai elemen terakhir sebuah list linier. Ada dua kemungkinan list kosong atau tidak kosong
Procedur InsertLast@(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 }
{Deklarasi}
Last : address { address untuk traversal}
{Deskripsi}
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 )
endwhile {Next ( Last) = Nil, Last adalah elemen terakhir; insert P after last }
InsertAfter (P, Last)
endif
Procedure InsertLast(Input/output L :List, Input E : Infotype)
{ 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 sebagai elemen terakhir dari list linier L yang mungkin kosong }
{Deklarasi}
Last : address { address untuk traversal }
{Deskripsi}
Alokasi (P)
If (P ≠ Nil) then
Info(P) ←E
InsertLast@(L,P)
endif
IV.3. Penghapusan sebuah elemen pada list linier
Penghapusan harus dijabarkan lebih rinci, Karena penghapusan elemen dapat merupakan pertama, setelah sebuah address P atau penghapusan elemen terakhir. Perbedaan ini melehirkan 3 operasi dasar penghapusan elemen list yang diturunkan dari definisi fungsional inimenjadi realisasi algoritma.
Operasi penghapusan dapat mengakibatkan list kosong, jika list semula hanya terdiri dari satu elemen.
IV.3.1. DELETFirst : menghapus elemen pertama list linier
a. Elemen yang dihapus dicatat alamatnya
Procedure DeleteFirst@ (Input/Output L : List, Output P : address)
{K. Awal : List L tidak kosong, minimal 1 elemen pertama pasti ada }
{K. Akhir : menghapus elemen pertama L
P adalah @ elemen pertama L sebelum penghapusan, L yang baru adalah Next (L)
{Deklarasi}
{Deskripsi}
P ← First (L)
First (L) ← Next( First (L))
Next(P) ← Nil
Procedure DeleteFirst (Input/Output L : List, Output E : InfoType)
{K. Awal : List L tidak kosong, minimal 1 elemen pertama pasti ada }
{K. Akhir : menghapus elemen pertama L
E adalah Nilai elemen pertama L sebelum penghapusan, L yang baru adalah Next (L)
{Deklarasi}
{Deskripsi}
P ← First (L)
E ← Info (P)
First (L) ← Next ( First (L) )
Next(P) ← Nil
Dealokasi (P)
IV. 3.2. Delete After :
Penghapusan suksesor sebuah elemen :
Procedure DeleteAfter ( Input Prec : adrress, Output P : address )
{ K. Awal : List tidak kosong, Prec adalah elemen list , Next (Prec) ≠ Nil } Prec ≠elemen terakhir
K. Akhir : Menghapus suksesor Prec, P adalah @ suksesor Prec sebelum penghapusan, Next (Prec) yang baru adalah suksesor dari suksesor Prec sebelum penghapusan }
{Deklarasi}
{Deskripsi}
P ← Next (Prec)
Next (Prec) ← Next (Next (Prec))
Dengan primitip ini, maka penghapusan sebuah beralamat P dapat dilakukan dengan : mencari predesesor dari P, yaitu alamat Prec memakai DeleteAfter (Prec)
Procedure DeleteP ( Input/Output L ; List, Output P : address )
{ K. Awal : List L tidak kosong , P adalah elemen list L K. Akhir : Menghapus P dari list, P mungkin elemen pertama, “tengah” atau terakhir }
{Deklarasi}
Prec : address { alamat predesesor }
{Deskripsi}
{ Cari predesesor P }
if (P = First (L) then {Delete list dengan satu elemen }
DeleteFirst (L,P)
else
Prec ← First (L)
While (Next(Prec) ≠ P ) do
Prec ← Next (Prec)
endwhile { Next (Prec) = P , hapus P }
DeleteAfter (Prec , P)
endif
IV. 3.3. DELETELast :
Menghapus elemen terakhir list dapat dilakukan jika alamat dari elemen sebelum elemen terakhir diketahui. Persoalan selanjutnya menjadi persoalan DeleteAfter, kalau last bukan satu- satunya elemen list linier. Ada dua kasus, yaitu list menjadi kosong atau tidak.
Procedure DeleteLast (Input L : List, Output P : address)
{K. Awal : List L tidak kosong, minimal mengandung 1 elemen
K. Akhir : menghapus elemen terakhir dari list, list mungkin menjadi kosong
Proses : P adalah alamat elemen terakhir list sebelum penghapusan }
{Deklarasi}
Last , preclast :address { address untuk traversal }
{Deskripsi}
{Find last dan address sebelum last }
Last ← First (L)
Preclast ← Nil { predesesor dari L tak terdefenisi }
While ( Next( Last ) ≠ Nil) do { Traversal list sampai @ terakhir }
Preclast ← Last
Last ← Next(last)
endwhile {Next( Last )=Nil, Last adalah elemen terakhir; preclast =
sebelum last }
P ← Last
If (Preclast = Nil) then { list dg 1 elemen, jadi kosong }
First(L) ← Nil
Else
Next ( Preclast )← Nil
endif
IV. 5. Konkatenasi dua buah list linier
Concat adalah menggabungkan dua list. Dalam contoh berikut list kedua disambungkan ke list pertama. Jadi Last (L1) menjadi predesesor First (L2). Realisasi algoritma adalah sebuah prosedur sebagai berikut :
Procedure CONCAT (Input L1, L2 : List, Output : L3 : List )
{K. awal : L1 ≠ L2, L1 ≠ L3,dan L3 ≠ L2; L1, L2 mungkin kosong
K. Akhir : L3 adalah hasil konkatenasi (menyambung) dua buah list linier, L2 ditaruh dibelakang L1 }
{Deklarasi}
Last1 : address { alamat elemen terakhir list pertama }
{Deskripsi}
Cratelist (L3) {inisialisasi list hasil }
If Fist (L1) = Nil then
First (L3) ← First (L2)
Else { Traversal list 1 sampai address terakhir,
Hubungkan last dengan Fisrt 2}
First (L3) ← First (L1)
Last1 ← First (L1)
While ( Next (Last 1 ) ≠ Nil ) do
Last1 ← Next (Last 1)
endwhile
Next(Last1) ← First (L2)}
endif
Soal-Soal Latihan
I. Apakah perbedaan struktur data list linier ditinjau dari sudut pandang operasinya, jika dibandingkan dengan struktur data record dan array?
II. Diketahui sebuah list linier dengan elemen bertipe integer, buatlah :
1. Sebuah prosedur untuk menghitung jumlah
elemen list yang genap
2. Prosedur untuk menghitung rata-rata elemen list yang ganjil
3. Prosedur untuk menghitung banyaknya
elemen list yang positif (lebih besar dari
nol)
4. Prosedur untuk mencetak elemen list yang
genap
5. Prosedur untuk mengubah dari satu list
menjadi 2 buah list yang terdiri dari list
dengan elemen genap dan list dengan elemen
ganjil
III. Diketahui sebuah list dengan elemen bertype
integer terurut membesar, buatlah :
1. Fungsi untuk mengirimkan elemen pertama list
2. Fungsi untuk mencari elemen list yang minimum
3. Fungsi untuk menghitung banyaknya elemen yang
lebih besar dari 100
untuk lebih lanjut download di atas atau diSini..
0 komentar:
Posting Komentar