Algoritma dan Struktur Data - list
-
Upload
georgius-rinaldo -
Category
Engineering
-
view
69 -
download
5
Transcript of Algoritma dan Struktur Data - list
SenaraiAlgoritma danStruktur Data
Kuliahkita - Edwin Lunando
Senarai (List) adalah sebuah penyimpanan yang mirip dengan larik dengan ukuran yang dapat berubah-ubah atau fleksibel sesuai dengan jumlah data.
Senarai = larik yang ukurannya dapat berubah (array list)
Definisi
Struktur Senarai
Pada sebuah penampung atau simpul (node) dari sebuah senarai, terdapat informasi:● nilai● informasi simpul berikutnya
next pada gambar merupakan pointer atau penunjuk yang menghubungkan antar simpul. Apabila simpul merupakan elemen terakhir, maka nilai next adalah null
Cara Menambah ke Senarai
Konsep penambahan elemen pada senarai adalah:1. alokasikan tempat untuk simpul baru2. salin item yang akan disimpan3. buat head dari senarai yang menunjuk ke arah simpul
yang baru
Walaupun tak terbatas seperti larik, tetapi item yang ditambahkan terbatas pada memory yang tersedia.
TDA Senarai{InfoType dan address adalah tipe yang telah didefinisikan} type ElmtList : < Info : InfoType, Next : address > type List : <First: address> {First adalah element pertama di list}
{Deklarasi nama untuk variabel kerja} P: address {address untuk traversal}
Penjelasan TDA Senarai
Dapat dilihat bahwa pada TDA senarai merupakan kumpulan dari alamat simpul yang saling berhubungan.
Struktur data senarai dimulai dengan first yang menunjuk ke alamat dari sebuah simpul. Simpul akan menunjuk simpul lainnya yang akhirnya akan membentuk senarai atau list.
Penjelasan TDA Senarai - 2
Simpul sendiri terdiri dari info dan next.
Info adalah nilai yang disimpan pada sebuah simpul. Sedangkan next merupakan tempat menyimpan alamat dari simpul berikutnya. Karena simpul selalu memiliki next, maka simpul akan terus bersambung dan membentuk list.
Jika sebuah simpul merupakan simpul terakhir, maka next akan berisi null.
Contoh Pendefinisian List C++#include <iostream>using namespace std;#define info(P) (P)->info#define next(P) (P)->next#define First(L) ((L).First) typedef int Infotype; // definisikan bahwa Infotype adalah alias dari tipe integertypedef struct tElmtList *address;typedef struct tElmtList { Infotype info; // informasi bertipe infotype yang telah didefinisi address next; // alamat yang menunjuk ke simpul berikutnya} ElmtList; // ini adalah struktur sebuah simpul
typedef struct { address First;} List; // tipe List berisi alamat pada simpul pertama
Contoh Pendefinisian List C++...
/* Pembuatan simpul */ElmtList buatSimpul(Infotype x) { ElmtList elem; // definisikan ElmtList sebagai simpul elem.info = x; // isi informasi pada simpul elem.next = NULL; // alamat next simpul baru adalah NULL return elem;}
...
Contoh Pendefinisian List C++.../* Mengalokasikan sebuah simpul pada senarai */void alokasi(List *L, ElmtList node) { // apabila senarai kosong, maka langsung alokasikan if (L->First == NULL) { L->First = &node; } else { // apabila senarai sudah ada isinya address el = L->First; // cari mana alamat simpul senarai yang kosong untuk dialokasikan
while(el->next != NULL) { el = el->next;}
// isi senarai dengan simpul yang dibuatel->next = &node;
}}...
Contoh Pendefinisian List C++.../* Pencarian pada senarai */bool pencarian (List *L, Infotype x) { // inisialisasi simpul awal address el = L->First; // iterasi pencarian sampai pada simpul yang tidak memiliki informasi while(el->info != NULL) { // apabila cocok, kembalikan true if (el->info == x){ return true; } // jika tidak cocok, ke simpul berikutnya el = el->next; } return false; // kembalkan false ketika semua telah ditelusuri dan tidak ada}...
Contoh Pendefinisian List C++...
int main() { List L; // definisikan senarai ElmtList elem1,elem2,elem3; // definisikan simpul yang akan diisi elem1 = buatSimpul(10); // buat simpul elem2 = buatSimpul(20); elem3 = buatSimpul(30); alokasi(&L, elem1); // alokasikan simpul-simpul alokasi(&L, elem2); alokasi(&L, elem3); cout << L.First->info << endl; // coba cetak elemen pertama cout << L.First->next->info << endl; // coba cetak elemen kedua bool dapatkah = pencarian(&L,30); // cari apakah elemen ada pada senarai? cout << dapatkah; return 0;}
Contoh: Pemakaian List// Contoh List pada library C++
using namespace std;list<int> deretbilangan; // definisi list dari integer