STRUKTUR DATA PDF

Preview

Summary

LAPORAN PRAKTIKUM STRUKTUR DATA SEMESTER GENAP TAHUN AKADEMIK 2018/2019 Disusun oleh : Nama : Febryan Alfaridzi NIM : 1818057 Prodi : TEKNIK INFORMATIKA S1 Kelompok : 25 PROGRAM STUDI TEKNIK INFORMATIKA S-1 FAKULTAS TEKNOLOGI INDUSTRI INSTITUT TEKNOLOGI NASIONAL MALANG 2019 LEMBAR PERSETUJUAN PRAKTI...

Description

LAPORAN PRAKTIKUM

STRUKTUR DATA SEMESTER GENAP TAHUN AKADEMIK 2018/2019

Disusun oleh : Nama NIM Prodi Kelompok

: Febryan Alfaridzi : 1818057 : TEKNIK INFORMATIKA S1 : 25

PROGRAM STUDI TEKNIK INFORMATIKA S-1 FAKULTAS TEKNOLOGI INDUSTRI INSTITUT TEKNOLOGI NASIONAL MALANG 2019

LEMBAR PERSETUJUAN PRAKTIKUM STRUKTUR DATA SEMESTER GENAP TAHUN AKADEMIK 2018/2019

NAMA NIM PRODI

Disusun Oleh : Febryan Alfaridzi : 1818057 : TEKNIK INFORMATIKA S-1

Mengetahui, Kepala Laboratorium Rekayasa Perangkat Lunak

Menyetujui, Dosen Pembimbing

(Ali Mahmudi,B.Eng,.PhD) NIP.P.1031000429

(Hani Zulfia Zahro’, S.kom,M.kom) NIP.P/Y.1031500480

PROGRAM STUDI TEKNIK INFORMATIKA S-1 FAKULTAS TEKNOLOGI INDUSTRI INSTITUT TEKNOLOGI NASIONAL MALANG 2019

ii

KATA PENGANTAR Dengan memanjatkan puji syukur kehadirat Tuhan Yang Maha Esa, karena atas berkah rahmat dan karunia-Nya sehingga kami dapat menyelesaikan Laporan Praktikum Mata Kuliah, guna persyaratan dalam menempuh mata kuliah. Laporan ini disusun berdasarkan percobaan dan teori dasar yang ada dalam buku panduan praktikum ,teori yang diperoleh praktikan dari perkuliahan, dan tidak lupa yaitu Internet sehingga praktikan dapat menambah tidak hanya menguasai teori saja namun juga memahami serta mengaplikasikannya. Terwujudnya laporan ini, tentunya tidak lepas dari bantuan-bantuan yang telah kami terima. Pada kesempatan ini, kami menyampaikan terima kasih yang sebesar-besarnya kepada yang terhormat: 1. Ibu Hani Zulfia Zahro’, S.kom,M.kom selaku dosen pembimbing Praktikum Struktur Data. 2. Bapak Joseph Agus Pranoto,ST. selaku dosen mata kuliah Struktur Data. 3. Bapak Ali Mahmudi, B.Eng.,PhD. selaku Ketua Pelaksana Praktikum Mata Kuliah Jurusan Teknik Informatika ITN Malang. 4. Instruktur Lab. Rekayasa Perangkat Lunak Teknik Informatika yang telah memberi petunjuk kepada kami selama pelaksanaan praktikum. 5. Rekan-rekan yang telah membantu dalam pelaksanaan dan penyelesaian laporan ini. Dalam menyusun laporan ini kami menyadari bahwa laporan ini masih memiliki kekurangan, karena itu segala kritik dan saran yang membangun akan kami nanti demi perbaikan penyusunan laporan selanjutnya. Harapan kami laporan praktikum ini bermanfaat bagi penulis sendiri maupun pembaca sekalian. Malang,

Mei 2019

Penulis

iii

DAFTAR ISI KATA PENGANTAR ........................................................................................ ii DAFTAR ISI ..................................................................................................... iii DAFTAR GAMBAR .......................................................................................... v DAFTAR TABEL ............................................................................................. vi BAB I POINTER, STRUCTURE, REKURSIF ................................................ 1 I.1 Landasan Teori ........................................................................................... 1 I.2 Langkah-langkah Praktikum ....................................................................... 6 I.3 Tugas Praktikum ke-1 : Program Implementasi Pointer ............................... 6 I.4 Tugas Praktikum ke-2 : Program implementasi Struct ................................. 7 I.5 Tugas Praktikum ke-3 : Program Menghitung Nilai Faktorial...................... 8 I.6 Tugas Rumah ke-1 : Program Implementasi Pointer .................................... 9 I.7 Tugas Rumah ke-2 : Program Implementasi Struct .................................... 10 I.8 Tugas Rumah ke-3 : Program Menara Hanoi............................................. 12 I.9 Kesimpulan ............................................................................................... 13 BAB II Stack dan Queue ................................................................................... 1 II.1 Landasan Teori .......................................................................................... 1 II.2 Langkah-langkah Praktikum ...................................................................... 8 II.3 Tugas Praktikum ke-1 : Program Implementasi Stack ................................ 8 II.4 Tugas praktikum ke-2: Program Implementasi Queue .............................. 11 II.5 Tugas Rumah ke-1 : Program Membalikkan Nama mengguakan Stack .... 14 II.6 Tugas Rumah ke-2 : Program Antrian Bank ............................................. 15 II.7 Kesimpulan ............................................................................................. 17 BAB III SORTING ............................................................................................ 1 III.1 Landasan Teori......................................................................................... 1 III.2 Langkah-langkah Praktikum ..................................................................... 4 III.3 Tugas Praktikum ke-1 : Sorting menggunakan Bubble Sort ...................... 5 III.4 Tugas Praktikum ke-2 : Sorting menggunakan Exchange Sort .................. 6 III.5 Tugas Praktikum ke-3 : Sorting menggunakan Insertion Sort .................... 7 III.6 Tugas Praktikum ke-4 : Sorting menggunakan Selection Sort ................... 8 III.7 Tugas Praktikum ke-5 : Sorting menggunakan Quick Sort ........................ 9

iv

III.8 Tugas Rumah ke-1 : Program mengurutkan Data Aslab .......................... 11 III.9 Tugas Rumah ke-2 : Program Sorting menggunakan Quick Sort............. 13 III.10 Kesimpulan .......................................................................................... 14 BAB IV SEARCHING ....................................................................................... 1 IV.1 Landasan Teori ........................................................................................ 1 IV.2 Langkah-langkah Praktikum..................................................................... 4 IV.3 Tugas Praktikum ke-1 : Program Implementasi Sequential Search............ 5 IV.4 Tugas Praktikum ke-2 : Program Implementasi Binary Search ................. 6 IV.5 Tugas Praktikum ke-3 : Program Implementasi Interpolation Search ........ 7 IV.6 Tugas Rumah ke-1 : Program Mencari Data Aslab ................................... 9 IV.7 Kesimpulan ............................................................................................ 11 BAB V LINKED LIST ....................................................................................... 1 V.1 Landasan Teori.......................................................................................... 1 V.2 Langkah-langkah Praktikum ...................................................................... 3 V.3 Tugas Praktikum ke-1 : Single Linked List ................................................ 4 V.4 Tugas Praktikum ke-2 : Double Linked List Input Data ............................. 7 V.5 Tugas Rumah ke-1 : Menampilkan Hubungan Orang tua Anak .................. 9 V.6 Tugas Rumah ke-2 : Implementasi Double Linked List .......................... 13 V.6 Kesimpulan ............................................................................................. 17 BAB VI TREE .................................................................................................... 1 VI.1 Landasan Teori (Tree) ............................................................................. 1 VI.2 Langkah-Langkah Praktikum .................................................................. 4 VI.3 Tugas Praktikum ke-1 : Tree .................................................................... 4 VI.4 Tugas Rumah ke-1 : Program Implementasi Tree .................................... 8 VI.5 Kesimpulan ........................................................................................... 12 BAB VII KESIMPULAN................................................................................... 1 DAFTAR PUSTAKA ......................................................................................... 2

v

DAFTAR GAMBAR Gambar 1.1 Program Implementasi Pointer ...................................................... 6 Gambar 1.2 Program Implementasi Struct ........................................................ 7 Gambar 1.3 Program Menghitung Nilai Faktorial ............................................. 8 Gambar 1.4 Program Implementasi Pointer ...................................................... 9 Gambar 1.5 Program Implementasi Struct ...................................................... 11 Gambar 1.6 Program Menara Hanoi ............................................................... 12 Gambar 2.1 Program Implementasi Stack....................................................... 10 Gambar 2.2 Program Implementasi Queue ..................................................... 13 Gambar 2.3 Program Membalikkan Nama Menggunakan Stack ..................... 14 Gambar 2.4 Program Antrian Bank ................................................................ 16 Gambar 3.1 Program Sorting menggunakan Bubble Sort .................................. 5 Gambar 3.2 Program Sorting menggunakan Exchange Sort .............................. 6 Gambar 3.3 Program Sorting menggunakan Insertion Sort ............................... 7 Gambar 3.4 Program Sorting menggunakan Selection Sort .............................. 9 Gambar 3.5 Program Sorting menggunakan Quick Sort ................................. 10 Gambar 3.6 Program mengurutkan Data Aslab............................................... 12 Gambar 3.7 Program Sorting menggunakan Quick Sort ................................. 14 Gambar 4.1 Program Implementasi Sequeantial Search .................................... 5 Gambar 4.2 Program Implementasi Binary Search ........................................... 7 Gambar 4.3 Program Implementasi Interpolation Search .................................. 8 Gambar 4.4 Program Mencari Data Aslab ...................................................... 10 Gambar 5.1 Program Single Linked List .......................................................... 7 Gambar 5.2 Program Double Linked List Input Data........................................ 9 Gambar 5.3 Program Menampilkan Hubungan Orang tua Anak ..................... 12 Gambar 5.4 Program Implementasi Double Linked List ................................. 16 Gambar 6.1 Program Tree ................................................................................ 7 Gambar 6.2 Program Implementasi Tree ........................................................ 10 Gambar 6.3 Notasi Tingkat Program Implementasi Tree ................................ 11 Gambar 6.4 Diagram Venn Program Implementasi Tree ................................. 11

vi

DAFTAR TABEL Perbedaan pointer dengan variabel biasa .......................................................... 2 Perbandingan Array dengan Linked List ........................................................... 1 Istilah – istilah dalam Tree ............................................................................... 2

I-1

BAB I POINTER, STRUCTURE, REKURSIF Jumlah Pertemuan

: 2 x 50 menit

Tujuan Praktikum : 1. Praktikan mampu memahami pengertian pointer, structure, rekursif dengan menggunakan C++. 2. Praktikan mengetahui Aturan main dari pointer,structure,rekursif. 3. Praktikan dapat mengoperasikan sebuah program menggunakan metode pointer, structure, dan rekursif. Alat dan bahan : 1. Perangkat komputer 2. Perangkat lunak: Dev C++ 3. Modul Struktur Data 2019 I.1 Landasan Teori 1.1 Pengertian Pointer Pointer adalah suatu variabel penunjuk, berisi nilai yang menunjuk alamat suatu lokasi memori tertentu. Jadi pointer tidak berisi nilai data, melainkan berisi suatu alamat memori atau null, jika pointer tidak berisi data maka disebut null pointer. Untuk mendeklarasikan variabel sebagai pointer, maka hanya menambahkan tanda asterik (*) di depan nama variabel. Dan untuk mendapatkan alamat dari variabel adalah dengan menggunakan operator &. Berikut ini bentuk umum dari pendeklarasian variabel yang bertipe pointer. Tipe_data *nama_pointer;

Jika ingin menyimpan alamat dari variabel x, kita dapat menggunakan suatu variabel misalnya Int alamat_x = &x;

Maka alamat_x adalah suatu variabel yang berisi alamat dimana nilai x disimpan. Variabel alamat_x disebut variabel pointer atau sering disebut dengan pointer saja. Disetujui Aslab Muh. Fitra Rizki Tgl:

Ttd / Paraf

II-2

1.2 Pointer tanpa tipe data Ada cara khusus untuk membuat pointer yang dideklarasikan tersebut tanpa merujuk ke semua tipe data, yaitu dengan mendeklarasikan pointer tersebut sebagai pointer tanpa tipe data atau disebut “void pointer”. Bentuk umumnya adalah : Void *nama_pointer;

Perbedaan pointer dengan variabel biasa Variabel Biasa Berisi data/nilai

Pointer Berisi alamat memori dari suatu variabel tertentu

Operasi yang bisa dilakukan seperti Membutuhkan operator khusus:”&” layaknya operasi biasa +,-,*,/

yang menunjuk alamat dari suatu variabel tertentu. Operator “&” hanya dapat dilakukan kepada variabel dan akan

menghasilkan

alamat

dari

variabel itu. Contoh : p = &n Yang kedua : Operator “*”. Operator ini bersifat menggunakan nilai dari alamat variabel yang ditunjuk oleh pointer tersebut. Contoh : int *p; Bersifat statis

Bersifat dinamis

Deklarasi : int a;

Deklarasi : int *a;

II-3

1.3 Aturan Pointer Variabel pointer dapat dideklarasikan dengan tipe data apapun. Pendeklarasian variabel pointer dengan tipe data tertentu digunakan untuk menyimpan alamat memori yang berisi data sesuai dengan tipe data yang dideklarasikan, bukan untuk berisi nilai bertipe data tertentu. Tipe data digunakan sebagai lebar data untuk alokasi memori (misalnya char berarti lebar datanya 1 byte, dst). Jika suatu variabel pointer dideklarasikan bertipe float, berarti variabel pointer tersebut hanya bisa digunakan untuk menunjuk alamat memori yang berisi nilai bertipe float juga. 1.4 Pointer Pada Array Array adalah suatu variabel yang menyimpan sekumpulan data yang memiliki tipe sama. Setiap data tersebut menempati lokasi atau alamat memory yang berbeda – beda dan selanjutnya di sebut dengan elemen array. Elemen array tersebut kemudian dapat kita akses melalui indeks yang terdapat di dalamnya namun penting sekali untuk diperhatikan bahwa dalam C++, indeks array selalu di mulai dari 0, bukan 1. 1.5 Pengertian Struct Struct (struktur) adalah kumpulan elemen – elemen data yang digabungkan menjadi satu kesatuan. Masing – masing elemen data tersebut dikenal dengan sebutan field. Field data tersebut dapat memiliki tipe data yang sama ataupun berbeda. Walaupun field – field tersebut berada dalam satu kesatuan, masing – masing field tersebut tetap dapat diakses secara individual. Field – field tersebut digabungkan menjadi satu dengan tujuan untuk kemudahan dalam operasinya. Misalnya ingin mencatat data – data mahasiswa dan pelajar dalam sebuah program. Untuk membedakannya kita dapat membuat sebuah struct mahasiswa yang terdiri dari field nama, nim, program studi dan ipk. Serta sebuah record pelajar yang terdiri dari field –

II-4

field nama, nim, alamat dan nilai. Dengan demikian akan lebih mudah untuk membedakan keduanya. Bentuk umum : Struct nama_struct{ Tipe_data1 field1; Tipe_data2 field2; Tipe_dataN fieldN; };

1.6 Penggunaan dan Pengaksesan Elemen Terstruktur Untuk menggunakan struct, tulis nama struct beserta dengan fieldnya yang dipisahkan dengan tanda titik (“.”). Misalnya anda ingin menulis nim seorang mahasiswa ke layar maka penulisan yang benar adalah sebagai berikut: - Mahasiswa.nim = “1818057”; - Cout ”). - Cout nim; 1.7 Pengertian Rekursif Rekursif adalah salah satu metode dalam dunia matematika, rekursif didefinisikan sebagai sebuah fungsi yang mengandung fungsi itu sendiri. Dalam dunia pemrograman, rekursif diimplementasikan dalam sebuah fungsi yang memanggil dirinya sendiri dan prosesnya terjadi secara berulang – ulang. 1.8 Fase dalam Rekursif 1.8.1 Fase Awal Fase awal merupakan fase dimana fungsi tersebut memanggil dirinya sendiri.

II-5

1.8.2 Terminate Terminate merupakan fase dimana fungsi tersebut berhenti memanggil dirinya sendiri. 1.8.3 Fase Balik Fase balik merupakan fase mengunjungi kembali kondisi – kondisi dari fase awal yang telah terbentuk dan mengembalikan nilai yang telah didapat dan fase terminal. 1.9 Implementasi Rekursif 1.9.1 Faktorial Dalam matematika, factorial dari bilangan asli n adalah hasil perkalian antara bilangan bulat positif yang kurang dari atau sama dengan n. Faktorial ditulis sebagai n! dan disebut n factorial. Secara umum dapat dituliskan sebagai : n! = n * (n – 1) * (n – 2) . (n – 3) * … * 3 * 2 * 1 1.9.2 Fibonacci Fibonacci adalah kumpulan deret angka seperti berikut ini “1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …”. Setiap bilangan setelah bilangan kedua merupakan jumlah dari dua bilangan sebelumnya. Dengan demikian 2 dari 1+1, 3 dari 2+1, 5 dari 3+2 dan demikian dijabarkan sebagai berikut : Jika n = 0, maka FN = 0, jika n = 1, maka Fn = 1 Jika n > 1, maka Fn = F(n-1)+F(n-2)

Implementasi dari fungsi Fibonacci dari definisi diatas dapat dinyatakan sebagai berikut : Karena Fn = n untuk n < 2, kita dapat menyederhanakan dengan pernyataan If.

II-6

I.2 Langkah-langkah Praktikum 1. Script ditulis dengan menggunakan Dev C++ 2. Script dicompile dengan menggunakan Dev C++ 3. Aplikasi dijalankan dengan menggunakan Dev C++ I.3 Tugas Praktikum ke-1 : Program Implementasi Pointer 1. Listing Program : #include using namespace std; int main(){ int *a,*b,*c=NULL; int d = 10; a = &d; cout...