RANGKUMAN PRAKTIKUM ALGORITMA DAN STRUKTUR DATA

RANGKUMAN PRAKTIKUM ALGORITMA DAN STRUKTUR DATA

MODUL 1-6

    Disusun Oleh:

Nama : Loranti Valentina

NIM :231080200049

Kelompok : 4

Assalamu’alaikum Wr.Wb.

Materi yang saya lampirkan ini merupakan hasil rangkuman dari materi praktikum Algoritma dan Struktur Data yang dilaksanakan selama satu semester ini untuk memenuhi tugas Praktikum Algoritma dan Struktur Data. Saya merupakan Mahasiswi Universitas Muhammadiyah Sidoarjo Program Studi Informatika Fakultas Sains dan Teknologi. Jika ingin mengetahui lebih detail tentang Universitas Muhammadiyah Sidoarjo bisa langsung mengakses link 

umsida.ac.id atau fst.umsida.ac.id

POKOK BAHASAN 1

STRUKTUR DATA, ARRAY, POINTER, DAN STRUKTUR

PENDAHULUAN

Pada pokok bahasan ini berisi penjelasan disertai contoh mengenai konsep struktur data, array, pointer, dan struktur yang menjadi pemahaman dasar bagi mahasiswa sebelum mempelajari struktur data, dimana konsep array, pointer, dan struktur digunakan untuk mempresentasikan sebuah struktur data.

PENYAJIAN (TUTORIAL)

    A.    Konsep Dasar Struktur Data

Struktur data adalah sebuah bagian dari ilmu pemrograman dasar yang mempunyai karakteristik yang terkait dengan sifat dan cara penyimpanan sekaligus penggunaan atau pengaksesan data.

    B.    Konsep Dasar Array

Array adalah kumpulan elemen-elemen data. Kumpulan elemen tersebut mempunyai susunan tertentu yang teratur. Jumlah elemen terbatas, dan semua elemen mempunyai tipe data yang sama. Jenis-jenis array :

      a. Array Satu Dimensi

 Struktur array satu dimensi dapat dideklarasikan dengan bentuk umum berupa : tipe_var nama_nama [ukuran];

  Dengan :

-       Tipe_var : unutk menyatakan jenis elemen array (misalnya int, char, unsigned).

-       Nama_var : untuk menyatakan nama variab  yang dipakao.

-       Ukuran : untuk menyatakan jumlah maksimal elemen array.

Contoh : fload nilai_ujian [5];

b. Array Dua Dimensi

Tipe data array dua dimensi bisa digunakan untuk menyimpan, mengolah maupun menampilkan suatu data dalam bentuk tabel atau matriks. Untuk mendeklarasikan array agar dapat menyimpan data adalah :

Tipe_var nama_var [ukuran1][ukuran2];

Dimana :

-       Ukuran1 menunjukkan jumlah/nomor baris.

-       Ukuran2 menunjukkan jumlah/nomor kolom.

Jumlah elemen yang dimiliki array dua dimensi dapat ditentukan dari hasil perkalian :

ukuran1 x ukuran2.

Seperti halnya pada array satu dimensi, data array dua dimensi akan ditempatkan pada memori secara berurutan.

c. Array Multidimensi / Dimensi Banyak

Array berdimensi banyak atau multidimensi terdiri dari array yang tidak terbatas hanya dua dimensi saja. Bentuk umum pendeklarasian array multidimensi adalah : tipe_var nama_var [ukuran1][ukuran2]…[ukurann];

Contoh : int data_angka [3][6][6];

Yang merupakan array tiga dimensi

       Mengakses Elemen Array :

        Dalam Bahasa C++, data array akan disimpan memori pada alokasi yang berurutan.

        Elemen pertama biasanya mempunyai indeks bernilai 0.

        Contoh : Float nilai_tes[5];

  Jika pada contoh di atas, variable nilai_tes mempuyai 5 elemen, maka elemen pertama                mempunyai indeks sama dengan 0, elemen kedua mempunyai indeks 1, dan seterusnya. 

  Bentuk umum pengaksesan suatu elemen variabel array adalah:

  Nama_var[indeks];

  Gambar berikut memperlihatkan urutan komponen array dalam memori,

  Untuk variabel array nilai_tes :

Inisialisasi Array :

Array dapat diinisialisasaikan secara langsung saat pertama kali dideklarasikan (efisien

untuk array berdimensi sedikit).

Contoh : int x[2]={1,2};

Array dapat dideklarasikan terlebihan dahulu, baru kemudian diisi elemennya.

Contoh :

Int x[2];

x[0]=1;

x[1]=2;

C.   Konsep Dasar Pointer

Pointer adalah sebuah variabel yang berisi Alamat variabel yang lain. Suatu pointer dimaksudkan untuk menunjuk ke suatu alamat memori sehingga alamat dari suatu variabel dapat diketahui dengan mudah. Deklarasi pointer :

Operator pointer :

       Operator ‘&’ : untuk mendapatkan alamat memori operand / varibel     pointer.

       Operator ‘*’ : untuk mengakses nilai data operand / variabel pointer.

D.    Konsep Dasar Struktur :

Struktur adalah koleksi dari variabel yang dinyatakan dengan sebuah nama, dengan sifat setiap variabel dapat memiliki tipe berlainan. Contoh sebuah struktur  adalah informasi data tanggal, yang berisi tanggal, bulan, dan tahun.

Mendeklarasikan Struktur :

Contoh pendefinisian tipe data

       struktur adalah : struct

       data_tanggal

       {int tanggal;

Masing-masing tipe dari elemen struktur dapat berlainan. Jika ada lebih dari satu variabel,antara variabel struktur dipisahkan dengan tanda koma.

Mengakses Elemen Struktur :

Elemen dari struktur dapat diakses dengan menggunakan bentuk :

variabel_struktur.nama_field

Antara variabel_struktur dan nama_field dipisahkan dengan operator titik (disebut operator anggota struktur). Contoh berikut merupakan intruksi untuk mengisikan data pada field tanggal :

        tgl_lahir.tanggal=30 int

        bulan;

        int tahun;

        };

Yang mendefinisikan tipe struktur bernama data_tanggal, yang terdiri dari tiga buah elemen berupa tanggal, bulan, tahun. Bentuk umum dalam mendefinisikan dan mendeklarasikan struktur adalah :

Struct nama_tipe_struktur

{

Tipe

field1

; Tipe

field2

; Tipe

field3

;

}variabel_struktur1….variabel_strukturM;

POKOK BAHASAN 2

LINKED LIST (SENARAI)

PENDAHULUAN

Pada pokok bahasan ini akan dibahas mengenai struktur data senarai (list) yang pembahasannya meliputi definisi dan representasi list, jenis-jenis list serta operasi-operasi dasar pada list.

PENYAJIAN (TUTORIAL)

Linked List adalah sejumlah objek atau elemen yang dihubungkan satu dengan lainnya sehingga membentuk suatu list. Sedangkan objek atau elemen itu sendiri adalah merupakan gabungan beberapa data (variabel) yang dijadikan satu kelompok atau structure atau record yang dibentuk dengan perintah struct. Untuk menggabungkan objek satu dengan lainnya, diperlukan paling tidak sebuah variabel yang bertipe pointer. Syarat linked list adalah harus dapat diketahui alamat simpul pertama atau biasa dipakai variabel First/Start/Header. Struktur dasar sebuah list seperti gambar berikut : 

Gambar 2.1 List Tunggal

Istilah-istilah dalam linked list :

-       Simpul

Simpul terdiri dari dua bagian yaitu :

            a.     Bagian data
      b.     Bagian pointer yang menunjuk ke simpul berikutnya

-       First/Header

Variabel First/header berisi alamat (pointer)/acuan (reference) yang menunjuk lokasi simpul pertama linked list, digunakan sebagai awal penelusuran linked list.

-       Nil/Null

Tidak bernilai, digunakan untuk menyatakan tidak mengacu ke manapun.

-       Simpul Terakhir

Simpul Terakhir linked list berarti tidak menunjuk simpul berikutnya. Tidak terdapat alamat disimpan di field pointer (bagian kedua dari simpul). Nilai null atau nil disimpan di field pointer di simpul terakhir.

Jenis-jenis linked list :

a. List Kosong

List Kosong hanya terdiri dari sebuah penunjuk elemen yang berisi NULL (kosong), tidak memiliki satu buah elemen pun sehingga hanya berupa penunjuk awal elemen berisi NULL.

b. List Tunggal

List tunggal adalah list yang elemennya hanya menyimpan informasi elemen setelahnya (next),  List tunggal terbagi menjadi tiga jenis yaitu list tunggal dengan kepala (first). List Tunggal dengan kepala (first) dan ekor (tail), serta list tunggal yang berputar.

c. List Ganda

List ganda adalah sebuah list yang elemennya menyimpan informasi elemen sebelumnya dan informasi elemen setelahnya. List ganda terbagi menjadi tiga jenis yaitu list ganda dengan kepala (first), list ganda dengan kepala (first) dan ekor (tail), serta list ganda yang berputar.

Operasi Dasar pada Linked List :

IsEmpty : Fungsi ini menentukan apakah linked list kosong atau tidak .
Size : operasi untuk mengirim jumlah elemen di liked list.
Create : operasi untuk penciptaan list baru yang kosong.
Insertfirst : operasi unruk penyisipan simpul sebagai simpul pertama.
Insertafter : operasi untuk penyisipan simpul setelah simengpul tertentu.
Insertlast : operasi untuk penyisipan simpul sebagai simpul terakhir.
Insertbefore : operasi untuk penyisipan simpul sebelum simpul terakhir.
Deletefirt : operasi penghapusan simpul pertama.
Deleteafter : operasi untuk penghapusan setelah simpul tertentu.
Deletelast : operasi penghapusan simpul terakhir.

POKOK BAHASAN 3

STACK (TUMPUKAN)

PENDAHULUAN

Pada pokok bahasan ini akan dibahas mengenai data tumpukan atau stack, dimana stack merupakan suatu kumpulan data yang seolah-olah data yang diletakkan di atas data yang lain. 

PENYAJIAN (TUTORIAL)

Stack adalah kumpulan elemen-elemen yang tersimpan dalam suatu tumpukan. Aturan

penyisipan dan penghapusan elemennya tertentu:

-   Penyisipan selalu dilakukan “di atas” TOP

-   Penghapusan selalu dilakukan pada TOP

Karena aturan penyisipan dan penghapusan semacam itu, TOP adalah satu-satunya alamat terjadi operasi, elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus. Dikatakan bahwa elemen Stack secara LIFO (Last In First Out).

Beberapa contoh penggunaan stack adalah pemanggilan prosedur, perhitungan ekspresi aritmatika, rekursifitas, backtracking, penanganan interupsi, dan lain-lain. 

Karakteristik penting stack sebagai berikut :

            1.     Elemen stack yaitu item-item data di elemen stack
      2.     TOP (elemen puncak dari stack)
      3.     Jumlah elemen pada stack
       4.     Status/kondisi stack, yaitu :

 - Penuh, Bila elemen di tumpukan mencapai kapasitas maksimum tumpukan. Pada kondisi

    ini, tidak mungkin dilakukan penambahan ke tumpukan. Penambahan di elemen

    menyebabkan kondisi kesalahan Overflow.

- Kosong, Bila tidak ada elemen tumpukan. Pada kondisi ini, tidak mungkin dilakukan

   pengambilan elemen tumpukan. Pengambilan elemen menyebabkan kondisi kesalahan

   Underflow.

Stack memiliki operasi-operasi pokok sebagai berikut :

Push          : Untuk menambahkan item pada tumpukan paling atas.

void Push (ItemType x, Stack *S)

{

          if (Full(S))

                         Printf("Stack FULL");

          else

          {

                         S->Item[S->Count]=x;

                         ++(S->count);

        }

}

Pop            : Untuk mengambil item teratas

int Pop (Stack S, ItemType x)

{

if (Empty (S))

Printf(“Stack Kosong”);

else

{

--(S->Count);

x=s->Item(s->Count);

}

}

Clear         : Untuk mengosongkan stack

void Initialize Stack (Stack *S)

{

S->Count=0;

}

IsEmpty    : Untuk memeriksa apakah stack kosong

int Empty (Stack *S)

{

return (S->Count==0);

}

IsFull        : Untuk memeriksa apakah stack sudah penuh

int Full (Stack S)

{

return (S-.>Count==MAXSTACK);

}

Representasi stack :

-       Representasi statis

     Stack dengan representasi statis biasanya diimplementasikan dengan menggunakan array. Sebuah array memiliki tempat yang dialokasikan diawal sehingga sebuah elemen yang dimasukkan dalam sebuah array terbatas pada tempat yang ada pada array.

      Ilustrasi stack dengan representasi statis dapat dilihat pada gambar  :

-       Representasi dinamis

        Stack dengan representasi dinamis biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen-elemen yang dialokasikan pada memori. 

      Ilustrasi stack dengan represntasi dinamis dapat dilihat pada gambar :

POKOK BAHASAN 4

QUEUE (ANTRIAN)

PENDAHULUAN

Pada pokok bahasan ini akan dibahas mengenai antrian atau queue, dimana struktur data ini hampir

sama dengan tumpukan atau stack yang merupakan struktur data yang linier. Perbedaannya adalah pada

operasi penambahan dan pengurangan pada ujung yang berbeda.

PENYAJIAN (TUTORIAL)

Antrian adalah suatu kumpulan data yang penambahan elemennya hanya bisa dilakukan pada suatu

ujung (disebut sisi belakang atau REAR). dan penghapusan atau pengambilan elemen dilakukan lewat

ujung yang lain (disebut sisi depan atau FRONT). Prinsip yang digunakan dalam antrian ini adalah

FIFO (First In First Out) yaitu elemen yang pertama kali masuk akan keluar pertama kalinya.

Ilustrasi Antrian dengan 

8 Elemen Karakteristik penting-penting antrian sebagai berikut :

a. Elemen antrian yaitu item-item data yang terdapat dalam antrian.

b. Head/front (elemen terdepan antrian).

c. Tail/rear (elemen terakhir antrian).

d. Jumlah antrian pada antrian (cout).

e. Status/kondisi antrian, ada dua yaitu :

   - Penuh, Bila elemen di antrian mencapai kapasitas maksimum antrian. Pada kondisi ini, tidak        mungkin dilakukan penambahan ke antrian. Penambahan di elemen menyebabkan kondisi                 kesalahan Overflow.

     - Kosong, Bila tidak ada elemen antrian. Pada kondisi ini, tidak mungkin dilakukan pengambilan       elemen antrian. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.

Operasi-operasi pokok pada antrian diantaranya adalah :

1. Create    Membuat antrian baru.

NOEL(CREATE(Q)) = 0

FRONT(CREATE(Q)) = tidak terdefinisi

REAR(CREATE(Q)) = tidak terdefinisi

2. IsEmpty  Untuk memeriksa apakah Antrian sudah penuh atau belum.

   ISEMPTY(Q) = True,jika Q adalah queue kosong.

3. IsFull       mengecek apakah Antrian sudah penuh atau belum.

   ISFULL(Q) = True,jika Q adalah queue penuh.

4. Enqueue/Insert      menambahkan elemen ke dalam Antrian, penambahan elemen

    selalu ditambahkan di elemen paling belakang.     

     REAR (INSERT(A,Q)) = A

     ISEMPETY (INSERT(A,Q)) = FALSE

     Algoritma QINSERT :

a. IF FRONT = 1 AND REAR = N, OR IF FRONT = REAR +

    1, THEN OVERFLOW, RETURN

b. IF FRONT := NULL,THEN

    SET FRONT := 1 AND REAR := 1

    ELSE IF REAR = N,

       THEN SET REAR

        := 1

    ELSE

       SEF REAR := REAR+1

c. SET QUEUE[REAR] := ITEM

d. RETURN

5. Dequeue/Remove      untuk menghapus elemen terdepan/petama dari Antrian.

 Algoritma QDELETE :

a. IF FRONT := NULL, THEN UNDERFLOW, RETURN

b. SET ITEM := QUEUE[FRONT]

c. [FIND NEW VALUE OF

    FRONT] IF FRONT =

      REAR, THEN

         SET FRONT := NULL AND REAR

    ;= NULL ELSE IF FRONT = N, THEN

SET FRONT := 1

ELSE

SET FRONT := FRONT+1

d. RETURN

Representasi queue :

Representasi statis

    Queue dengan representasi statis biasanya diimplementasikan dengan menggunakan array. Sebuah array memiliki tempat yang dialokasikan diawal sehingga sebuah elemen yang dimasukkan dalam sebuah array terbatas pada tempat yang ada pada array. Karena menggunakan array maka queue dengan representasi statis dalam mengalami kondisi elemen penuh. Ilustrasi queue dengan representasi statis dapat dilihat pada gambar :

Representasi dinamis

      Queue dengan representasi dinamis biasanya diimplementasikan dengan menggunakan pointer yang merujuk pada elemen-elemen yang dialokasikan pada memori. Ilustrasi queue dengan represntasi dinamis dapat dilihat pada gambar :

POKOK BAHASAN 5

REKURSIF

PENDAHULUAN

Pada pokok bahasan ini akan dibahas mengenai rekursif. Setelah mempelajari bab ini diharapkan

mahasiswa mampu :
a. Mengetahui dan memahami definisi rekursif.
b. Memahami sifat-sifat rekursif.
c. Mengaplikasikan rekursif.

PENYAJIAN (TUTORIAL)

Fungsi rekursif adalah suatu fungsi yang memanggil dirinya sendiri, artinya fungsi tersebut dipanggil di

dalam tubuh itu sendiri. Contoh menghitung nilai factorial.

Rekursif sangat memudahkan untuk memecahkan permasalahan yang kompleks.

Sifat-sifat rekursif :
·  Dapat digunakan ketika inti dari masalah terjadi berulang kali.
·  Sedikit lebih efisien dari iterasi tapi lebih elegan.
·  Method-methodnya dimungkinkan untuk memanggil dirinya sendiri.

POKOK BAHASAN 6

SORTING (PENGURUTAN)

PENDAHULUAN

Setelah mempelajari bab ini diharapkan mahasiswa mampu :

a.   Menunjukkan beberapa algoritma dalam pengurutan.

b. Menunjukkan bahwa pengurutan merupakan suatu persoalan yang bisa diselesaikan dengan sejumlah algoritma yang berbeda satu sama lain.

c. Dapat memilih algoritma yang paling sesuai untuk menyelesaikan suatu permasalahan pemrograman.

PENYAJIAN (TUTORIAL)

Pengurutan data (sorting) didefinisikan sebagai suatu proses untuk menyusun kembali himpunan obyek

menggunakan aturan tertentu. Ada dua macam urutan yang biasa digunakan dalam proses pengurutan

yaitu :

·    Urutan naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar.

·    Urutan turun (descending) yaitu dari data yang mempunyai nilai paling besar sampai paling kecil.

Contoh : data bilangan 5, 2, 6, dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6, atau diurutkan turun

menjadi 6, 5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil atau lebih besar dari

yang lain didasarkan pada urutan relatif (collating sequence) seperti dinyatakan dalam table ASCII.

Keuntungan dari data yang sudah dalam keadaan terurut yaitu :

Data mudah dicari, mudah untuk dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadan

terurutkan, kita mudah melakukan pengecekan apakah ada yang hilang. Misalnya kamus

Bahasa, buku telepon.

Mempercepat proses pencarian data yang harus dilakukan berulang kali.

Beberapa factor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain : 

Banyak data yang diurutkan.

Kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki.

Tempat penyimpanan data, misalnya piringan, pita atau kartu, dll.

Beberapa algoritma metode pengurutan dan prosedurnya sebagai berikut:

1.     Bubble Sort

    Bubble Sort adalah suatu metode pengurutan yang membandingkan elemen yang sekarang dengan elemen berikutnya. Apabila elemen sekarang > elemen berikutnya, maka posisinya ditukar. Kalau tidak, tidak perlu ditukar. 

Proses Bubble Sort :

    Data paling akhir dibandingkan dengan data di depannya, jika ternyata lebih kecil atau besar maka tukar sesuai dengan ketentuan(descending atau ascending). Dan pengecekan yang sama dilakukan terhadap data yang selanjutnya sampai dengan data paling awal.

2.     Selection Sort

   Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot. Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. Proses pengurutan dengan metode seleksi dapat dijelaskan sebagai berikut :

    -  Langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain.

     - Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai elemen dalam keadaan terurutkan.

 

3.     Merger Sort

    Algoritma Merge Sort ialah algoritma pengurutan yang berdasarkan pada strategi divide and conquer. Algoritma ini terdiri dari dua bagian utama, pembagian list yang diberikan untuk di-sort ke dalam beberapa sublist yang lebih kecil, dan sort (mengurutkan) dan merge (menggabungkan) sublist-sublist yang lebih kecil ke dalam list hasil yang sudah diurutkan. Pembagian bisa dikatakan cukup mudah karena sublist-sublist tersebut dibagi ke dalam dua sublist yang ukurannya adalah setengah dari ukuran semula. Hal ini terus diulang sampai sublist itu cukup kecil untuk di-sort secara efisien (umumnya telah terdiri dari satu atau dua elemen). Dalam Langkah merge dua sublist disatukan kembali dan diurutkan pada saat yang sama. Algoritma untuk merge sort ialah sebagai berikut :

A. Untuk kasus n=1, maka table a sudah terurut sendirinya (langkah solver)

B. Untuk kasus n>1, maka :

      a. DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-masing                             bagian berukuran n/2 elemen.

            b. CONQUER: secara rekursif, terapkan algoritma D-and-C pada masing-masing bagian.

            c. MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.

 

 Semoga rangkuman ini bermanfaat bagi penulis dan pembaca.

Terima kasih.

Wassalamu'alaikum Wr. Wb.