PERATURAN DAN TATA TERTIB PRAKTIKUM 1. Praktikum dilaksanakan di Laboratorium Kamus UPI Cibiru sesuai jadwal yang ditentukan. 2. Mahasiswa wajib membawa modul praktikum dan alat tulis. 3. Mahasiswa wajib mengisi daftar hadir praktikum dengan pulpen berwarna hitam. 4. Kegiatan praktikum terdiri atas penyampaian materi dan pengerjaan latihan. 5. Saat praktikum berlangsung, mahasiswa: a. Wajib menon-aktifkan/mematikan nada dering alat komunikasi. b. Dilarang membuka aplikasi yang tidak berhubungan dengan praktikum yang sedang berlangsung c. Dilarang mengubah setting software ataupun hardware di ruang praktikum. d. Dilarang membawa makanan dan minuman kedalam ruang praktikum e. Dilarang menyebarkan soal selama praktikum. f. Dilarang membuang sampah apapun di ruang praktikum. 6. Tidak ada jadwal praktikum susulan bagi mahasiswa yang tidak hadir praktikum. 7. Pelanggaran terhadap peraturan praktikum ini akan ditindak secara tegas di lingkup kelas, laboratorium, program studi, hingga universitas. i
DAFTAR ISI Peraturan dan Tata Tertib Praktikum.......................................................... i Daftar Isi...................................................................................................... ii Modul 1 Pendahuluan .................................................................................. 1 1.1 Struktur Data ..............................................................................................1 1.2 Tipe Data ...................................................................................................1 1.3 Variabel .....................................................................................................3 1.4 Jenis Struktur Data .....................................................................................3 Modul 2 Array .............................................................................................. 4 2.1 Array..........................................................................................................4 2.2 Array 2 Dimensi ..........................................................................................6 2.3 Latihan .......................................................................................................9 Modul 3 Struct ............................................................................................ 10 3.1 Struct ........................................................................................................10 3.2 Deklarasi Struct .........................................................................................10 3.3 Akses Struct ..............................................................................................12 3.4 Operator Aggregate Pada Struct...................................................................13 3.4.1 Operator Input / Output Struct .................................................................13 3.4.2 Operator Aritmatika ..................................................................................15 3.4.3 Operator Comparison ...............................................................................17 3.5 Hirarki Struct .............................................................................................20 3.6 Struct of Array ...........................................................................................21 3.7 Latihan ......................................................................................................23 Modul 4 Pointer ........................................................................................... 24 4.1 Pointer ......................................................................................................24 4.2 Pointer dan Fungsi SWAP ...........................................................................26 ii
4.3 Pointer dan Operasi Array ...........................................................................28 4.4 Pointer dan Operasi Aritmatika ....................................................................28 Modul 5 List ................................................................................................. 30 5.1 Linked List .................................................................................................30 5.2 Single Lingked List .....................................................................................31 5.3.1 Operasi Dasar Single List .........................................................................32 5.3.2 Traversal List ..........................................................................................32 5.3.3 Insert List ...............................................................................................33 5.3.4 Delete List ..............................................................................................37 5.3 Double Linked List.......................................................................................39 5.3.1 Insert List ...............................................................................................40 5.3.2 Delete List ..............................................................................................43 5.4 Latihan .......................................................................................................46 Modul 6 Stack .............................................................................................. 47 6.1 Stack..........................................................................................................47 6.2 Latihan .......................................................................................................52 Modul 7 Queue ............................................................................................. 53 7.1 Queue ........................................................................................................53 7.2 Operasi Queue/Antrean ...............................................................................54 7.3 Latihan .......................................................................................................59 Modul 8 Tree ................................................................................................ 60 8.1 Tree ...........................................................................................................60 8.2 Binary Tree (Pohon Biner) ...........................................................................61 8.3 Implementasi .............................................................................................62 8.4 Latihan ......................................................................................................72 Modul 9 Graph ............................................................................................. 73 iii
9.1 Graph ........................................................................................................73 9.2 Graph Tidak Berarah dan Tidak Berbobot .....................................................73 9.2.1 Implementasi............................................................................................76 9.3 Graph Tidak Berarah dan Berbobot ..............................................................81 9.3.1 Implementasi............................................................................................82 9.4 Graph Berarah dan Berbobot .......................................................................83 9.1 Latihan .......................................................................................................84 Daftar Pustaka ............................................................................................. 85 iv
Modul 1 PENDAHULUAN 1.1 Struktur Data Data merupakan fakta atau sesuatu yang sudah tidak perlu dibuktikan akan kebenarannya [Bo Pang and Lillian Lee]. Contoh yang merupakan data ialah Matahari terbit di bagian timur dan Terbenam di bagian barat. Struktur ialah organisasi atau hubungan. Jadi Strukutur Data merupakan Penyimpanan dan pengorganiasasian data- data pada memori komputer ataupun file secara efektif sehingga dapat digunakan secara efisien, termasuk operasi-operasi didalamnya. Definisi Algoritma menurut [Algoritma dan Pemrograman, Rinaldi Munir] menyebutkan bahwa urutan atau langkah-langkah untuk memecahkan suatu permasalahan. Sehingga penggabungan struktur data dan algoritma menghasilkan program sebagai suatu solusi atau memecahkan suatu permasalahan dengan menerapkan organisasi data secara tepat. 1.2 Tipe Data Tipe data ialah jenis data yang mampu ditangani oleh suatu bahasa pemrograman pada komputer. Setiap bahasa pemrograman memiiliki tipe data. TIPE DATA TIPE DATA TIPE DATA SEDERHANA TERSTRUKTUR Tipe Data terdiri dari dua jenis, Tipe data sederhana (tipe data atomik) dan Tipe Data Terstruktur. Contoh tipe sederhana ialah tipe data Float, tipe data Integer, tipe data Struktur Data dan Algoritma 1
Char, dan lain-lain sedangkan tipe data struktur contohnya tipe data array, record, dan lain-lain. 1. Tipe Data Sederhana Tipe data sederhana atau disebut juga tipe data atomik. Pada bahasa pemrograman C++. Penulisan tipe dasar sederhana dapat ditulis sebagai berikut: 1. using namespace std; 2. char nama, kelas; 3. int nilai; Penulisan syntax pada bahasa pemrograman diatas terdapat variabel nama dan kelas termasuk dalam tipe data sederhana char karena nilai yang dimiliki variabel tersebut berjenis string, Sedangkan variabel nilai merupakan tipe data integer karena nilai yang dimiliki variabel memiliki tipe operasi artimatika. 2. Tipe Data Terstuktur Tipe data terstruktur ialah tipe data yang dapat diuraikan dalam bentuk yang lebih sederhana. Contoh pada penulisan tipe data terstruktur pada pemrograman C++ ialah sebagai berikut: 1. using namespace std; 2. char nama[100], kelas[2]; 3. int total[10]; Pada syntax bahasa pemrograman diatas terdapat variabel nama dan kelas, namun pada variabel tersebut dapat menampung himpunan data sebanyak 100 data untuk nama dan 2 data untuk variabel kelas. Sedangkan variabel total dapat menampung himpunan total sebanyak 10 data. Karena tipe data terstruktur dapat disederhanakan kedalam bentuk lain, untuk mengakses bagian tipe data yang lebih sederhana lagi digunakan nomor index, contohnya nama[1] untuk mengakses variabel nama pada index ke-1. Penjelasan detail mengenai tipe data terstruktur array akan dibahas pada bab selanjutnya. Struktur Data dan Algoritma 2
1.3 Variabel Variabel adalah nama yang mewakili suatu elemen data. Aturan penulisan variabel: 1. Harus dimulai dengan abjad, tidak boleh dengan angka atau simbol. 2. Tidak boleh ada spasi diantaranya. 3. Jangan menggunakan simbol-simbol yang bisa membingungkan seperti titik dua, titik koma, koma, dan sebagainya. 4. Sebaiknya memiliki arti yang sesuai dengan elemen data. 5. Sebaiknya tidak terlalu panjang. 1.4 Jenis Struktur Data Pada modul struktur data dan algoritma ini tersususun materi pembelajaran pada gambar 1 jenis struktur data sebagai berikut: Array SEDERHANA Record List LINEAR Stack STRUKTUR DATA Queue MAJEMUK HIERARKI Tree Gambar 1. Jenis Struktur Data Graph Struktur Data dan Algoritma 3
Modul 2 ARRAY 2.1 Array Larik atau array merupakan data yang disimpan dalam suatu tipe data yang sama dan tiap-tiap data atau elemen tersebut dapat diolah secara kelompok ataupun secara individu. Array memiliki sifat homogen yaitu seluruh elemen di dalam struktur array memiliki tipe da yang sama dan random access merupakan setiap elemen dalam struktur array dapat diambil ke lokasi yang diinginkan tanpa harus melalui elemen pertama. Deklarasi Array Array dalam suatu program dideklarasikan terlebih dahulu dengan memiliki 4 (empat) komponen yaitu tipe data array, nama variabel, operator index([ ]), dan nilai dimensi dalam operator[ ] dengan format penulisan sebagai berikut: type_data variabel_array[nilai dimensi] = {nilai dimensi array} Penerapan penulisan format array dengan tipe data integer, nama variabel num, ukuran array 6 yang memiliki 6 buah data. int num[6] = {10, 20, 30, 40, 50, 60}; tipe data array nama variabel array ukuran array nilai dimensi Visualisasi array digambarkan dengan bentuk tabel dengan memiliki baris dengan nilai index awal bernilai 0. nilai 10 20 30 40 50 60 Index num[0] num[1] num[2] num[3] num[4] num[5] tabel 2.1 visualisasi tabel array Struktur Data dan Algoritma 4
Algoritma untuk menampilkan data array pada variabel num dapat ditulis sebagai berikut: Define variabel_array Begin counter = 0; Loop Start counter = 0 → n data Print index, value End Loop End Penulisan bahasa pemrograman pada algortima menampilkan data array ialah sebagai berikut: 1. #include <iostream> 2. 3. using namespace std; 4. 5. int main() 6. { 7. int cb[6] = {10,20,30,40,50,60}; 8. int i = 0; 9. 10. for(i = 0;i<6;i++) 11. { 12. cout<<\"Index ke - \" <<i<< \" : \" <<cb[i]<<endl; 13. } 14. } Struktur Data dan Algoritma 5
Maka, output yang dihasilkan akan menampilkan index beserta nilainya. index value 0 10 1 20 2 30 3 40 4 50 5 60 tabel 2.2 Output index berserta nilai Algoritma untuk mengganti nilai data array pada indek ke-i pada variabel num dapat ditulis sebagai berikut. Define variabel_array // 6 data Begin counter = 0; Varibel[index yang diganti] = X Loop Start counter = 0 → n data Print index, counter End Loop End 2.2 Array 2 Dimensi Array dua dimensi sama halnya dimensi satu yang dapat menyimpan data dalam bentuk tabel. Terbagai menjadi dua bagian, dimensi satu yang merupakan baris (index pertama) dan dimensi dua merupakan representasi dari kolom (index kedua). Pada tabel 2.1 merupakan tabel array 2 dimensi dengan tabel 2x4. Struktur Data dan Algoritma 6
KOLOM BARIS [0,0] [0,1] [0,2] [0,3] [1,0] [1,3] [1,1] [1,2] tabel 2.3 tabel array 2 dimensi Tabel 2.4 merupakan contoh latihan array 2 dimensi dengan ukuran 4 baris dan 5 kolom atau dapat ditulisa dengan variabel array dataArray[4][5]. ABCDE FGH I J 12345 6 7 8 9 10 Tabel 2.4 contoh array 2 dimensi Baik pada baris ataupun kolom, index selalu dimulai pada nilai 0. Sama halnya pada array berdimensi satu, untuk mengakses nilai baris dan kolom dimulai dari 0 sesuai pada tabel 2.3. Berdasarkan tabel 2.3, maka algoritma untuk menampilkan data array dimensi 2 dapat menggunakan fungsi looping atau perulangan. Algoritma dibawah ini digunakan untuk menampilkan data yang ada pada tabel 2.4. Define Variabel_array // given value Begin counter_1,counter_2 = 0; Loop 1 Start counter_1 = 0 → n baris data Loop 2 Start counter_2 = 0 → n kolom data Print index, variabel_array[baris-n][kolom-n] End Loop 2 End Loop 1 End Struktur Data dan Algoritma 7
Implementasi bahasa pemrograman C++ pada algoritma untuk menampilkan data array dua dimensi ialah sebagai berikut: 1. //Nama File : array2dimensi.cpp 2. //Menampilkan data array 2 dimensi 3. 4. #include <iostream> 5. using namespace std; 6. 7. int main() 8. { 9. string data[4][5] = {{\"A\",\"B\",\"C\",\"D\",\"E\"},{\"F\",\"G\",\"H\", \"I\",\"J\"},{\"1\",\"2\",\"3\",\"4\",\"5\"},{\"6\",\"7\",\"8\",\"9\",\"10\"}}; 10. 11. for(int row=0;row<4;row++) 12. { 13. for(int col=0;col<5;col++) 14. { 15. //cout<<row<<col<<endl;//Mencetak Index ROW,COL 16. cout<<\"Data Index ke [\"<<row <<\",\"<<col<<\"] : \"< < data[row][col] <<endl; 17. } 18. //cout<<row<<endl;//Mencetak BARIS 19. } 20. } Output yang dihasilkan ialah sebagai berikut: Data Index ke [0,0] : A Data Index ke [0,1] : B Data Index ke [0,2] : C Data Index ke [0,3] : D Data Index ke [0,4] : E Data Index ke [1,0] : F Data Index ke [1,1] : G Data Index ke [1,2] : H Data Index ke [1,3] : I Data Index ke [1,4] : J Data Index ke [2,0] : 1 Data Index ke [2,1] : 2 Data Index ke [2,2] : 3 Data Index ke [2,3] : 4 Data Index ke [2,4] : 5 Struktur Data dan Algoritma 8
Data Index ke [3,0] : 6 Data Index ke [3,1] : 7 Data Index ke [3,2] : 8 Data Index ke [3,3] : 9 Data Index ke [3,4] : 10 2.3 Latihan 1. Buatlah program untuk menghitung perkaliaan dua buah matrix 2 x 2 yang dapat disesuaikan dengan inputan. 2. Buatlah program untuk mencari nilai terbesar dari n buah data dari nilai yang input. 3. Buatlah program untuk mencari suatu nilai pada elemen data pada n buah data yang telah diinputkan. Struktur Data dan Algoritma 9
Modul 3 STRUCTURE 3.1 Structure Data pada sebuah penyimpanan atau storage ataupun database tersimpan dalam sebuah record. Setiap record memiliki satu atau lebih elemen field yang menunjukan informasi dari record. Contohnya record mahasiswa memiliki field nama, nim, nilai dan lain-lain. Dalam bahasa pemrograman C++, record dikenal dengan nama struct. Pembahasan sebelumnya data yang memilki elemen tipe data sama (homogen) dinamakan array, sedangkan data yang disimpan memiliki variasi tipe data berbeda (heterogen) dinamakan struct. Variabel struct yang dapat mengakses struct dinamakan member. 3.2 Deklarasi Struct Deklarasi tipe record diawali dengan kata struct yang diapit oleh { (kurung buka kurawal) dikikuti oleh suatu daftar elemen dan terakhir di tutup dengan } (kuruang kurawal tutup). Deklarasi struct ditulis dengan format sebagai berikut: struct nama_struct { tipe data nama_variabel 1; tipe data nama_variabel 2; … tipe data nama_variabel n; } #ListMember variabel struct nama_struct variabelStruct; nama_struct variabelStruct; Pada bagian header diawali nama struct berserta nama struct yang digunakan, setelah dibuka dengan { di isi dengan tipe data diikuti dengan nama variabel yang digunakan Struktur Data dan Algoritma 10
sebanyak 1 sampai dengan n field lalu di tutup dengan }. Bagian list member variabel struct merupakan inisialisasi variabel struct yang dapat mengakses struct berserta field yang dimilikinya. Variabel yang dapat mengakses field suatu struct dapat melebihi dari satu variabel. Penggunaan struct berdasarkan format deklarasi struct dapat ditulis pada contoh berikut: 1. struct type1{ 2. int a; 3. int b; 4. }; 5. 6. type1 x,y; Contoh diatas pada baris ke-6, type1 merupakan nama struct dan variabel x dan y merupakan variabel struct yang dapat menggunakan struct berserta field yang dimiliki struct type1. Struct memiliki ketentuan field sebagai berikut: 1. Fieldname merupakan variabel lokal struct. 2. Fieldname yang sama dapat digunakan pada variabel struct. 3. Setiap field variabel struct merupakan assosiasi dari nama field. Penggunaan struct pada contoh kasus berikut, Sebuah perusahaan rintisan teknologi CV. Cibiru Maju memiliki karyawan yang memiliki identitas nama, usia, dan penghasilan yang berbeda dengan karyawan lainnya. Serta memiliki jenis karyawan yang memiliki kategori karyawan tetap (permanent) dan karyawan kontrak (temporary). Untuk membuat mengubah permasalahan tersebut kedalam bentuk structure dapat ditulis sebagai berikut. struct karyawan { string nama; int usia; Struktur Data dan Algoritma 11
float penghasilan; }; karyawan permanent; karyawan temporary; Penulisan dalam bahasa C++ diatas karyawan merupakan nama struct yang memiliki field nama dengan tipe data string, usia tipe data integer dan penghasilan bertipe float. Variabel struct yang dapat mengakses struct karyawan ialah karyawan permanent dan karyawan temporary. Variabel permanent dan temporary dapat mengakses field yang ada pada struct karyawan. 3.3 Akses Struct Untuk mengakses field pada struct oleh variabel struct menggunakan operator (.) diantara nama variabel struct dan field. Penulisan pengaksesan struct ialah sebagai berikut: variabel_struct.field_struct; Sedangkan untuk memberikan value atau nilai pada field pada struct dapat ditulis dalam format berikut: variabel_struct.field_struct = nilai; Penggunaan variabel struct pada contoh kasus karyawan ditulis dalam bahasa pemorgraman C++. 1. //untuk mengakses karyawan pada variabel struct permananet 2. permanent.nama; 3. permanent.usia; 4. permanent.penghasilan; 5. 6. //untuk mengakses karyawan pada variabel struct temporary 7. temporary.nama; 8. temporary.usia; 9. temporary.penghasilan; Struktur Data dan Algoritma 12
Untuk pemberian value atau nilai pada field nama, usia, dan jenis penghasilan pada variabel struct permanent dan temporary ditulis dalam bahasa pemrograman C++. 1. //Passing variabel struct permanent 2. permanent.nama = “Devi”; 3. permanent.usia = 27; 4. permanent.penghasilan = 3000; 5. 6. //Passing variabel struct temporary 7. temporary.nama = “Anwar”; 8. temporary.usia = 23; 9. temporary.penghasilan = 1000; 3.4 Operator Aggregate pada Struct Operator aggregate ialah operatos yang digunakan untuk memanipulasi suatu nilai atau mengubah nilai dalam bentuk lainnya, contohnya operator logic, oprtator comparison, dan operator aritmatika. Pada struct ada beberapa ketentuan yang perlu diperhatikan, antara lain: 1. Tidak dapat melakukan I/O (input/output) pada field struct secara langsung. 2. Tidak dapat menggunakan operator logic, arithmetic dan comparison secara langsung pada field struct. 3. Penggunaan I/O, operator artimatika dan comparison hanya dapat dilakaukan melalui variabel struct atau by variabel reference. 4. Dapat melakukan passing nilai pada variabel struct pada variabel lain yang memiliki type data sama. 5. Dapat memberikan passing variabel struct pada sebuah fungsi serta mengembalikan nilai terhadap sebuah fungsi (return). 3.4.1 Operator Input/Outpur Struct Penggunaan input dan output struct dapat ditulis pada algorima berikut: define Struct() { Struktur Data dan Algoritma 13
field 1 - n; } main() { inisialisasi struct → variabel struct input struc 1 → variabel_struct.field input struc n → variabel_struct.field output 1 → variabel_struct.field output n → variabel_struct.field } Implementasi C++ untuk algoritma diatas, dapat ditulis sebagai berikut: 1. //Nama File : struct_io.cpp 2. //Penggunaan Struct untuk memanipulasi data menggunakan I/O 3. 4. #include <iostream> 5. #include <stdlib.h> 6. 7. using namespace std; 8. 9. struct karyawan 10. { 11. string nama; 12. int usia; 13. float penghasilan; 14. }; 15. 16. int main() 17. { 18. karyawan permanent, temporary; 19. 20. cout<<\"Karyawan Permanent\\n\"; 21. cout<<\"Nama Karyawan Permanent : \";cin>>permanent.nama; 22. cout<<\"Usia Karyawan Permanent : \";cin>>permanent.usia; 23. cout<<\"Panghasilan Karyawan Permanent : \";cin>>permanent .penghasilan; 24. 25. cout<<\"Karyawan Temporary\\n\"; Struktur Data dan Algoritma 14
26. cout<<\"Nama Karyawan Temporary : \";cin>>temporary.nama; 27. cout<<\"Usia Karyawan Temporary: \";cin>>temporary.usia; 28. cout<<\"Panghasilan Karyawan Temporary : \";cin>>temporary .penghasilan; 29. 30. system(\"CLS\"); 31. cout<<\"Display Karyawan Permanent\\n\"; 32. cout<<\"Nama Karyawan : \"<<permanent.nama<<endl; 33. cout<<\"Usia Karyawan : \"<<permanent.usia<<endl; 34. cout<<\"Penghasilan Karyawan : \"<<permanent.penghasilan<< endl; 35. cout<<\"\\n\\n\"; 36. cout<<\"Display Karyawan Temporary\\n\"; 37. cout<<\"Nama Karyawan : \"<<temporary.nama<<endl; 38. cout<<\"Usia Karyawan : \"<<temporary.usia<<endl; 39. cout<<\"Penghasilan Karyawan : \"<<temporary.penghasilan<< endl; 40. } Output dari algortima penggunaan input dan output. Display Karyawan Permanent Nama Karyawan : Devi Usia Karyawan : 27 Penghasilan Karyawan : 3000 Display Karyawan Temporary Nama Karyawan : Anwar Usia Karyawan : 23 Penghasilan Karyawan : 1000 3.4.2 Operator Aritmatika Aritmatika sering digunakan dalam pemrograman dengan fungsi matematik yang terdiri dari penambahan, perkalian, pembagian, pengurangan, modulus, dan lain sebagainya. Pada struct operator artimatika tidak dapat dilakukan secara langsung, namun harus melalui nilai konstan atau by reference (nama struct diikuti dengan field). Perhatikan algoritma berikut: Struktur Data dan Algoritma 15
define struct() { field 1 - n; } main() { inisialisasi struct → VariabelStruct input struct 1 → variabel_struct.field input struct n → variabel_struct.field //operator aritmatika VariabelStruct.field = VariabelStruct.struct_n output 1 → variabel_struct.field output n → variabel_struct.field } Implementasi C++ untuk algoritma diatas, dapat ditulis sebagai berikut: 1. //Nama File : struct_aritmatika.cpp 2. //Penggunaan struct pada operasi artimatika 3. 4. #include <iostream> 5. #include <stdlib.h> 6. 7. using namespace std; 8. 9. struct karyawan 10. { 11. string nama; 12. int usia; 13. float penghasilan; 14. float total; 15. }; 16. 17. int main() 18. { 19. karyawan permanent, temporary; 20. float tunjangan; 21. 22. cout<<\"Karyawan Permanent\\n\"; 23. cout<<\"Nama Karyawan Permanent : \";cin>>permanent.nama; Struktur Data dan Algoritma 16
24. cout<<\"Usia Karyawan Permanent : \";cin>>permanent.usia; 25. cout<<\"Panghasilan Karyawan Permanent : \";cin>>permanent .penghasilan; 26. cout<<\"Tunjangan Kesehatan Karyawan Permanent : \";cin>>t unjangan; 27. 28. permanent.total = permanent.penghasilan + tunjangan; 29. 30. system(\"CLS\"); 31. cout<<\"Display Karyawan Permanent\\n\"; 32. cout<<\"Nama Karyawan : \"<<permanent.nama< <endl; 33. cout<<\"Usia Karyawan : \"<<permanent.usia< <endl; 34. cout<<\"Penghasilan Karyawan : \"<<permanent.pengh asilan<<endl; 35. cout<<\"Tunjangan Karyawan : \"<<tunjangan<<endl ; 36. cout<<\"Total Penghasilan Karyawan : \"<<permanent.total <<endl; 37. } Output yang dihasilkan: Display Karyawan Permanent Nama Karyawan : Anwar Usia Karyawan : 23 Penghasilan Karyawan : 3000 Tunjangan Karyawan : 1500 Total Penghasilan Karyawan : 4500 3.4.3 Operator Comparison Operator comparison digunakan untuk membandingakan dua atau lebih kondisi. Penggunaan struct pada operator comparison tidak dapat dilakukan secara langsung tanpa melalui variabel struct. Pada contoh alogiritma dibawah berikut penggunaan struk pada operator comparison. Struktur Data dan Algoritma 17
define struct() { field 1 - n; } main() { inisialisasi struct → VariabelStruct input struct 1 → variabel_struct.field input struct n → variabel_struct.field //operator aritmatika total penghasilan = penghasilan + tunjangan lain-lain //operator comparison if total penghasilan > 1000 keterangan = “Wajib Pajak” else keterangan = “Tidak Wajib Pajak” output 1 → variabel_struct.field output n → variabel_struct.field } Implementasi C++ untuk algoritma diatas, dapat ditulis sebagai berikut: 1. //Nama File : struct_comparison.cpp 2. //Penggunaan Struct pada Operasi Comparison 3. 4. #include <iostream> 5. #include <stdlib.h> 6. 7. using namespace std; 8. 9. struct karyawan 10. { 11. string nama; 12. int usia; 13. float penghasilan; 14. float total; 15. }; 16. Struktur Data dan Algoritma 18
17. int main() 18. { 19. karyawan permanent, temporary; 20. float tunjangan; 21. string ket_pajak; 22. 23. cout<<\"Karyawan Permanent\\n\"; 24. cout<<\"Nama Karyawan Permanent : \";cin>>permanent.nama; 25. cout<<\"Usia Karyawan Permanent : \";cin>>permanent.usia; 26. cout<<\"Panghasilan Karyawan Permanent : \";cin>>permanent .penghasilan; 27. cout<<\"Tunjangan Kesehatan Karyawan Permanent : \";cin>>t unjangan; 28. 29. permanent.total = permanent.penghasilan + tunjangan; 30. if (permanent.total > 1000) 31. ket_pajak = \"Wajib Pajak\"; 32. else 33. ket_pajak = \"Tidak Wajib Pajak\"; 34. 35. system(\"CLS\"); 36. cout<<\"Display Karyawan Permanent\\n\"; 37. cout<<\"Nama Karyawan : \"<<permanent.nama< <endl; 38. cout<<\"Usia Karyawan : \"<<permanent.usia< <endl; 39. cout<<\"Penghasilan Karyawan : \"<<permanent.pengh asilan<<endl; 40. cout<<\"Tunjangan Karyawan : \"<<tunjangan<<endl ; 41. cout<<\"Total Penghasilan Karyawan : \"<<permanent.total <<endl; 42. cout<<\"Pajak : \"<<ket_pajak<<endl ; 43. } Output yang dihasilkan: Display Karyawan Permanent Nama Karyawan : Anwar Usia Karyawan : 28 Penghasilan Karyawan : 3000 Struktur Data dan Algoritma 19
Tunjangan Karyawan : 1500 Total Penghasilan Karyawan : 4500 Pajak : Wajib Pajak 3.5 Hirarki Struct Struct yang memiliki field struct dengan type data variabel struct pada struct lainnnya dinamakan hirarki struct. Terdapat 2 jenis struct pada contoh dibawah ini: 1. struct type1 2. { 3. char a; 4. char b; 5. }; 6. 7. struct type2 8. { 9. type1 c; 10. int d; 11. }; Pada contoh diatas terdapat 2 struct, yaitu type1 dan type2 yang masing-masing memiliki 2 buah field. Type1 memiliki field tipe data char a dan b sedangkan type2 memiliki field tipe data struct dan integer d. Untuk mengakses field bertipe struct perlu mengakses field terluar hingga yang paling dalam, seperti berikut: 1. main() 2. { 3. type2 hierarch; 4. hierarch.c.a; 5. } Pada baris ke 4, variabel struct hierarch untuk mengakses field a pada struct type1. Struktur Data dan Algoritma 20
3.6 Struct of Array Pada dasarnya struct dapat mengelompokan variabel yang memiliki tipe data namun tidak dapat menampung data sebanyak n data atau hanya single storage untuk single variabel struct. Untuk mengatasi hal tersebut perlu menggunakan variabel struct yang bertipe data array. Perhatikan algoritma penggabungan array terhadap struct. struct nama_struct { field 1..n; } main{ nama_struct variabel_struct_array[index]; call fungsi input_array(); tampilkan hasil array; } fungsi input_array { input->variabel_struct_array; } Implementasi pada bahasa pemrograman C++ dengan pembatasan banyak data, n = 2 buah data. 1. //Nama File : struct_array.cpp 2. //Penggunaan Struct dengan array 3. 4. #include <iostream> 5. using namespace std; 6. 7. struct karyawan 8. { 9. string firstName; 10. string lastName; 11. int usia; 12. }; 13. 14. typedef karyawan karyawan_tipe_array[2]; Struktur Data dan Algoritma 21
15. void LoadArray(karyawan_tipe_array peop); 16. 17. int main(void) 18. { 19. karyawan_tipe_array people; 20. LoadArray(people); 21. 22. cout <<\"\\n\"; 23. cout <<\"No\\t Nama Depan\\t Nama Belakang\\t Usia\\n\"; 24. for (int i = 0; i < 2; i++) 25. { 26. cout << i+1<<\"\\t \"<< people[i].firstName << \"\\t\\t \" << people[i].lastName << \"\\t \"<< people[i].usia<<\"\\n\"; 27. } 28. } 29. 30. void LoadArray(karyawan_tipe_array peop) 31. { 32. for (int i = 0; i < 2; i++) 33. { 34. cout << \"Nama Depan : \";cin >> peop[i].firstName; 35. cout << \"Nama Akhir : \";cin >> peop[i].lastName; 36. cout << \"Usia : \";cin >> peop[i].usia; 37. } 38. } Output yang dihasilkan ialah sebagai berikut: Nama Depan : Devi Nama Akhir : Anissa Usia : 28 Nama Depan : Anwar Nama Akhir : Sarifudin Usia : 30 No Nama Depan Nama Belakang Usia 1 Devi Anissa 28 2 Anwar Sarifudin 30 Struktur Data dan Algoritma 22
3.7 Latihan Seseorang akan menonton film dengan berjudul “Milea: Suara dari Dilan”. Jika 1 orang dapat memesean tiket lebih dari 1. Ketentuan pembelian tiket ialah sebagai berikut: o Jika 1 orang membeli lebih dari 1 tiket, maka total pembayaran ialah 1 * jumlah banyak tiket. o Jika pembeli membeli 10 tiket, maka mendapatkan bonus 1 tiket. o Jika pembeli membeli 5 tiket, maka diskon diberikan 10% dari total pembayaran. o Dengan asumsi 1 tiket merupakan 1 seat, maka tentukan output untuk menghasilkan informasi tiket tersebut. Gunakan field dengan asumsi-asumsi anda! Struktur Data dan Algoritma 23
Modul 4 POINTER 4.1 Pointer Pointer ialah variabel yang nilainya merupakan alamat dari variabel lain. Umumnya program akan menjadi lebih efisien dengan menggunakan pointer, maka variabel tersebut mengandung alamat memori tempat variabel tersebut dialokasikan, namun bukan alamat variabel itu sendiri karena pointer mengandung suatu objek dan dapat diakases melalui sebuah pointer. Sebagai contoh, px adalah variabel pointer dan x adalah variabel yang ditunjuk oleh px. Jika x berada pada alamat memori awal 1000, maka nilai px ialah 1000. Berikut ilustrasi pointer pada gambar 4.1 ilustrasi pointer. xxx alamat 1000 Px xxx ? x Gambar 4.1 Ilustrasi Pointer Untuk mendapatkan alamat dari variebel dengan tipe data tertentu didapatkan dengan menggunakan operator & (dereference operator). Alamat ini yang akan disimpan ke dalam variabel bertipe pointer, sedangkan untuk mendeklarasikan variabel pointer dengan menambahkan operator * (reference operator) didepan nama variabel. Bentuk umum deklarasi variabel pointer ialah pada format berikut: tipe_data *variabel_pointer; Jika X merupakan variabel bertipe integer dan Px merupakan variabel pointer yang berisi menunjuk alamat dari data bertipe integer X, maka penulisan dalam bahasa pemrograman C++ dapat ditulis sebagai berikut: Struktur Data dan Algoritma 24
1. main(){ 2. int X; 3. int *Px; 4. 5. Px = &X; 6. } Berdasarkan syntax program diatas, variabel pointer P hanya berisi alamat dan &X nilai alamat variabel X maka P hanya dapat diisi dengan variabel alamat bukan nilai. Namun jika akan memberikan nilai kedalam variabel pointer P maka dengan menambahkan operator * setelah variabel pointer yang dapat ditulis *p = x. Implementasi penggunaan pointer pada bahasa pemrogramn C++ ditulis sebagai berikut: 1. //Nama File : pointer_first.cpp 2. //Pengenalan pointer 3. 4. #include <iostream> 5. #include <stdio.h> 6. 7. using namespace std; 8. 9. main(){ 10. int x; 11. int *p; 12. 13. cout<<\"Nilai X : \";cin>>x; 14. p =&x; 15. 16. cout<<\"Output 1\"<<endl; 17. cout<<\"Nilai X : \"<<x<<endl; 18. cout<<\"Alamat X : \"<<p<<endl; 19. 20. cout<<\"\\n\"<<endl; 21. cout<<\"Nilai X : \";cin>>x; 22. *p = x; 23. cout<<\"Output 2\"<<endl; 24. cout<<\"Nilai X : \"<<*p<<endl; 25. cout<<\"Alamat X : \"<<p<<endl; 26. } Struktur Data dan Algoritma 25
Output yang akan dihasilkan. Nilai X : 100 Output 1 Nilai X : 100 Alamat X : 0x6dfee8 Nilai X : 200 Output 2 Nilai X : 200 Alamat X : 0x6dfee8 Pengamatan output diatas, variabel X diisi dengan nilai awal 100, maka alamat alamat akan berisi 0x6dfee8. Sedangkan saat mengisi nilai variabel pada pointer yang tunjukan pada baris ke-22, variabel X akan berubah sesuai dengan inputan yang ke dua (dalam hal ini inputan 200) maka alamat akan berisi 0x6dfee8. Hal ini menunjukan bahwa *P akan selalu sama dengan variabel X, karena kedua variabel tersebut menempati alamat yang sama. Variabel Pointer akan menyimpan alamat dari nilai variabel dengan catatan tipe yang dimiliki sama. 4.2 Pointer dan Fungsi SWAP Fungsi swap digunakan untuk menukar dua nilai, misalnya nilai a = 5 dan b = 7 dengan menggunakan fungsi swap maka nilai akan berubah menjadi a = 7 dan b = 5. Namun alamat memori tidak berubah selama alamat variabel tidak serta merta ditukar. Berikut contoh penukaran yang pertama. 1. //Nama File : pointer_swap.cpp 2. //Penggunaan pointer pada swap 3. 4. #include <iostream> 5. 6. using namespace std; 7. 8. main() Struktur Data dan Algoritma 26
9. { int *p,*q; 10. int x = 5, y = 7; 11. 12. cout<<\"Nilai X : \"<<x<<endl; 13. cout<<\"Nilai Y : \"<<y<<endl; 14. cout<<\"Alamat X : \"<<&x<<endl; 15. cout<<\"Alamat Y : \"<<&y<<endl; 16. 17. cout<<\"\\n\"; 18. cout<<\"Penggunaan SWAP (Penukaran Nilai)\\n\"; 19. swap(x,y); 20. cout<<\"Nilai X : \"<<x<<endl; 21. cout<<\"Nilai Y : \"<<y<<endl; 22. cout<<\"Alamat X : \"<<&x<<endl; 23. cout<<\"Alamat Y : \"<<&y<<endl; 24. 25. } Output yang dihasilkan ialah sebagai berikut. Nilai X : 5 Nilai Y : 7 Alamat X : 0x6dfeec Alamat Y : 0x6dfee8 Penggunaan SWAP (Penukaran Nilai) Nilai X : 7 Nilai Y : 5 Alamat X : 0x6dfeec Alamat Y : 0x6dfee8 Hasil yang ditampilkan menunjukan bahwa hanya nilai saja yang berubah namun alamat variabel tidak ikut berubah, hal ini dikarenakan alamat variabel tidak turut dilibatkan. Dengan menyisipkan kode p = &x;q = &y; pada baris ke-23 maka output yang dihasilkan ialah: Struktur Data dan Algoritma 27
Nilai X : 5 Nilai Y : 7 Alamat X : 0x6dfee4 Alamat Y : 0x6dfee0 Penggunaan SWAP (Penukaran Nilai) Nilai X : 7 Nilai Y : 5 Alamat X : 0x6dfee0 Alamat Y : 0x6dfee4 Untuk melakukan inisialisasi terhadap pointer, dilakukan insisalisasi NULL. 4.3 Pointer dan Operasi Array Array pada pointer digunakan untuk menyusun alamat memori secara terurut. Variabel array tanpa definisi index merupakan representasi alamat memori yang paling awal, contohnya char a[], maka alamat memori yang paling awal ialah 0. Variabel array yang memiliki index terdefinisi memiliki jumlah alamat memori sebanyak index tersebut, contohnya variabel array char a[5] menunjukan pada compiler bahwa elemen memeberikan 5 blok dimulai dari alamat paling awal dari variabel a. Hal ini salah satu alasan bahwa penjelasan bahwa array selalu dimulai dari 0. 4.4 Pointer dan Operasi Aritmatika Pointer memungkinkan melakukan operasi aritmatika, namun operator yang dimungkinkan hanyalah pengurangan dan penambahan alamat memori untuk bergeser pada lokasi lain pada memori khusunya pada kasus elemen array. Contohnya variabel Pc merupakan elemen pertama pada suatu array, setelah melakukan operasi arimatika Pc += 3, maka elemen berpindah sebanyak empat elemen. Pada contoh berikut merupakan penggunaan pointer dengan menggunakan operasi aritmatika: Struktur Data dan Algoritma 28
1. //Nama File : pointer_aritmatika.cpp 2. //Penggunaan pointer dengan operasi aritmatika 3. 4. #include <iostream> 5. using namespace std; 6. 7. main() 8. { 9. char lokasi[] = \"Cibiru\"; 10. char *Plokasi = lokasi; 11. 12. cout<<\"Value : \"<<lokasi<<endl; 13. cout<<\"Array[0] : \"<<lokasi[0]<<endl; 14. cout<<\"Nilai Plokasi : \"<<*Plokasi<<endl; 15. cout<<\"Pointer[2] : \"<<Plokasi[2]<<endl; 16. Plokasi += 3; 17. cout<<\"Pointer[2+3] : \"<<Plokasi[2]<<endl; //Bergese r sejauh 2 + 3 18. cout<<\"Pointer[2+3] : \"<<Plokasi<<endl; //Bergeser s ejauh + 3 19. } Output yang dihasilkan dari syntak diatas ialah. Value : Cibiru Array[0] :C Nilai Plokasi :C Pointer[2] :b Pointer[2+3] :u Pointer[2+3] : iru 4.5 Latihan Reverse word ialah membalikan satu kata dari kata aslinya. Array termasuk strukutur data sederhana yang dapat menyimpan data yang bertipe homogen. Dan Pointer merupakan variabel yang menunjuk alokasi memori suatu data. Dengan menggunakan algoritma, buat algortima beserta pemrograman membuat reserved word dari sebuah inputan <kata> dan output berupa jumlah kata dan kata yang sudah terbalik. Struktur Data dan Algoritma 29
Modul 5 LIST 5.1 Linked List Linked list merupakan deretan elemen atau node yang bedampingan yang dialokasikan secara dinamis (menggunakan malloc) dan memungkinkan likned list akan terpencar-pencar pada memori. Ilustrasi list terdapat pada gambar 5.1 liked list. * * * * NULL Gambar 5.1 Likend list Pada gambar 5.1 Linked list terdiri dari node-node yang dihubungkan dengan pointer dan setiap elemen terdiri dari sebuah data dan pointer (pointer next). Linked list dibentuk dengan cara menunjuk pointer next suatu node ke node yang mengikutinya. Pointer next pada node terakhir yang menunjukan akhir suatu list dinamakan NULL, sedangkan awal suatu list disebut head dan node terakhir dari suatu list disebut tail. data pointer * * * * NULL head tail Gambar 5.2 Struktur linked list Pada umumnya linked list terbagi menjadi dua bagian, yaitu single linked list double linked list. Struktur Data dan Algoritma 30
5.2 Single Linked List Single list memiliki satu pointer untuk setiap node yang menunjuk ke node berikutnya. Single linked list hanya memiliki satu pointer untuk setiap node yang akan ditujunya. Node untuk single linked list dapat digambarkan pada gambar 5.3 node single linked list. data *next Gambar 5.3 Node single linked list Penulisan dalam struktur struct yang rekursif untuk mendefinisikan single linked list pada bahasa C++ ialah sebagai berikut: 1. //Nama File : single_linkedlist.cpp 2. //Deklarasi Single Linked List 3. 4. #include <iostream> 5. 6. using namespace std; 7. 8. struct node{ 9. int bilangan; 10. node *next; 11. }; Rekursif ialah variabel yang digunakan ialah variabel dirinya sendiri. Int bilangan ialah deklarasi variabel yang menentukan bahwa datang diolah bertipe integer. Pada baris ke-10 menentukan struct list dengan mendeklarasikan sebuah variabel *next yang menunjuk struct itu sendiri dengan tujuan untuk menunjuk ke node berikutnya. Struktur Data dan Algoritma 31
5.2.1 Operasi Dasar Single List Operasi pada linked list diawali dengan pendefinisian struktur list yang yang kosong dengan menggunakan meng-assigndengan nilai NULL. Dapat ditunjukan pada syntax sebagai berikut: 1. //Nama File : create_list.cpp 2. //Pemuatan list 3. 4. #include <iostream> 5. #include <malloc.h> 6. 7. using namespace std; 8. 9. struct node{ 10. int bilangan; 11. node *next; 12. }; 13. 14. main() 15. { 16. struct node* head = NULL; //deklarasi head 17. head = (struct node*)malloc(sizeof(struct node)); 18. } Struct node berfungsi sebagai prosedur awal yang digunakan untuk rekursi dan pointer next yang bertujuan untuk menunjuk node selanjutnya. Baris ke-16 menunjukan deklarasi variabel head yang menunjukan bahwa setiap awal node selalu diawali head. Baris ke-17 merupakan alokasi memori menggunakan malloc untuk variabel head. 5.2.2 Traversal List Traversal atau penelurusan list digunakan untuk melakukan penelusuran terhadap list yang ada, dimulai dari headi sampai menemukan nilai pointer *next = null. Traversal dapat diimplementasikan sebagai berikut: 1. //Nama File : traversal_list.cpp 32 2. //Penelurusan list 3. Struktur Data dan Algoritma
4. #include <iostream> 5. #include <malloc.h> 6. 7. using namespace std; 8. 9. struct node{ 10. int bilangan; 11. node *next; 12. }; 13. 14. main() 15. { 16. struct node* head = NULL; //deklarasi head 17. struct node* current = NULL; 18. 19. head = (struct node*)malloc(sizeof(struct node)); 20. current = (struct node*)malloc(sizeof(struct node)); 21. 22. current = head; 23. while(current->next != NULL) 24. { 25. current = current->next; 26. } 27. } 5.2.3 Insert List Metode insert atau penyisipan nilai pada node baru terdapat 3 (tiga) pilihan, antara lain: 1. Penyisipan sebelum head Node baru ditambahkan sebelum head. Sebuah node nilai 3, 5, 7, dan 9 akan disisipkan node bernilai 1 yang akan ditempatkan sebelum head node maka, susunan node akan menjadi 1, 3, 5, 7, dan 9. Fungsi untuk menambahkan node pada awal list dinamakan push(). Fungsi push() berfungsi sebagai head pointer karena menggeser head node menjadi node yang baru, pada gambar 5.4 sebagai berikut: Struktur Data dan Algoritma 33
head 3 * 5 * 7 * 9 * NULL 1* Gambar 5.4 Insert pada node awal Implementasi pada pemograman menggunakan prosedur InsertFirst. 1. void insertfirst(int nilai) 2. { 3. node *new_node; 4. new_node = new node; 5. new_node -> data = nilai; 6. if (isEmpty()) 7. { 8. head = new_node; 9. head ->next = NULL; 10. } 11. else 12. { 13. new_node->next = head; 14. head = new_node; 15. } 16. } 2. Penyisipan setelah node tertentu Alur data yang dilakukan untuk penyisipan data pada node tertentu, pastikan head sudah memiliki nilai/data, jika belum memiliki data maka inisiasi maka data baru merupakan head pada link list. Kondisi teleh memiliki data yang dapat ditunjukan pada gambar 5.5 Insert node ke-2, node head menunjuk node pertama dan pointer pertama menunjuk pada node yang akan disisipkan. Maka pointer node baru yang telah disisipakan menunjuk pada pointer node selanjutnya. Struktur Data dan Algoritma 34
head 1 * 5 * 7 * 9 * NULL 3* Gambar 5.5 Insert pada node ke-2 Implementasi pada pemograman menggunakan prosedur InsertAfter. 1. void Insertafter(struct node *prev_node, int nilai) 2. { 3. if(prev_node = NULL) 4. { 5. cout<<\"Nilai sebelumnya tidak boleh NULL\"; 6. return; 7. } 8. 9. node *new_node = new node; 10. new_node->data = nilai; 11. new_node->next = prev_node->next; 12. prev_node->next = new_node; 13. } 3. Penyisipan pada akhir linked list Penyisipan node baru pada akhir link list selalu diawali pengecekan keberadaan link list. Kondisi list masih kosong yang ditandai dengan NULL, maka head menunjuk pada node baru dan pointer pada node baru menunjuk pada NULL. Sedangkan kondisi list sudah memiliki data, maka dilakukan pencarian menggunakan loop sampai data tidak sampai dengan NULL. Node terakhir sudah ditemukan menggunakan loop, maka pointer pada node tersebut menunjuk pada node baru dan pointer pada node baru menunjuk pada NULL. Penyisipan pada akhir linked list dapat ditunjukan pada gambar 5.6 insert atau penyisipan pada node terakhir. Struktur Data dan Algoritma 35
head 1 * 3 * 5 * 7 * NULL 9* Gambar 5.6 Insert pada node terakhir Implementasi pada pemograman menggunakan prosedur insertlast. 1. void insertlast(int nilai) 2. { 3. node *new_node, *current; 4. new_node = new node; 5. new_node->data = nilai; 6. new_node->next = NULL; 7. 8. if(isEmpty()) 9. { 10. head = new_node; 11. head ->next = NULL; 12. } 13. else 14. { 15. current=head; 16. while(current->next!=NULL) 17. { 18. current = current->next; 19. } 20. current->next = new_node; 21. } 22. } Struktur Data dan Algoritma 36
5.2.4 Delete List Metode delete atau menghapus nilai pada node terdapat 2 (tiga) pilihan, antara lain: 1. Remove First Remove first ialah prosedur untuk menghapus pada node yang pertama yang ditandai dengan pointer pada head menghapus pada head->next dan mengganti dengan node yang berikutnya. Remove first dapat ditunjukan pada gambar 5.7 hapus node di awal. head 1 * 3 * 5 * 7 * NULL Gambar 5.7 Menghapus node di awal Implementasi penggunaan procedure removefirst ialah sebagai berikut: 1. void removefirst() 2. { 3. node *hapus; 4. int current; 5. 6. if(isEmpty()) 7. { 8. current = head->data; 9. head = NULL; 10. } 11. else 12. { 13. if(head->next!= NULL) 14. { 15. hapus = head; 16. current = hapus->data; 17. head = hapus->next; 18. delete hapus; Struktur Data dan Algoritma 37
19. } 20. } 21. } 2. Remove Last Remove last ialah prosedur untuk menghapus pada node terakhir. Kondisi jika memiliki 1 node maka head menjadi NULL. Kondisi memiliki linkedlist pada gambar 5.8 menghapus node di akhir, maka dilakukan pengecekan pointer node next sebanyak 2x yang berinal NULL, posisi pada node tersbut merupakan list terakhir dan pointer yang menunjuk pada node terakhir menunjuk pada NULL. head 1 * 3 * 5 * 7 * NULL Gambar 5.8 Menghapus node di akhir Implementasi penggunaan procedure removelast ialah sebagai berikut: 1. void removelast() 2. { 3. node *hapus, *current; 4. if(isEmpty()) 5. { 6. head = NULL; 7. } 8. else 9. { 10. current = head; 11. while(current->next->next!=NULL) 12. { 13. current = current->next; 14. } 15. delete current->next; 16. current->next = NULL; 17. } 18. } Struktur Data dan Algoritma 38
5.3 Double Linked List Double linked list mempunyai dua pointer yang menunjuk ke node berikutnya dan sebelumnya, disebut juga dengan istilah next pointer dan previous pointer. Node untuk double linked list dapat digambarkan pada gambar 5.9 node double linked list. *prev data *next Gambar 5.9 Node double linked list Penulisan dalam struktur struct yang rekursif untuk mendefinisikan double linked list pada bahasa C++ ialah sebagai berikut: 1. #include<iostream> 2. using namespace std; 3. 4. struct node 5. { 6. int data; 7. node *next; 8. node *prev; 9. }; Double link list yang telah memilki data dapat digambarkan pada gambar 5.10 Double link list dibawah ini: head tail * 1 * * 2 * * 3 * NULL Gambar 5.10 Double linked list Struktur Data dan Algoritma 39
5.3.1 Insert List Metode insert atau penyisipan nilai pada node baru terdapat 3 (tiga) pilihan, antara lain: 1. Penyisipan sebelum head Kelebihan yang didapatkan dengan menggunakan double link list ialah dapat menginput dan menghapus data lebih dinamis. Pada gambar 5.11 Insert pada depan list, node yang baru memiliki nilai 1 memeiliki pointer prev menunjuk NULL dan pointer node baru menunjuk pada node→next serta node→prev menunjuk node baru. head tail *3 * *5* *7 * NULL NULL *1* Gambar 5.11 Insert depan DLL 40 Implementasi prosedur insertdepan. 1. void insertdepan(int nilai) 2. { 3. node *new_node; 4. new_node = new node; 5. new_node->data = nilai; 6. 7. if (isEmpty()) 8. { 9. head = new_node; 10. head ->next = NULL; 11. } 12. else Struktur Data dan Algoritma
13. { 14. new_node->next = head; 15. new_node->prev = NULL; 16. head = new_node; 17. } 18. } 2. Penyisipan diakhir list Node baru biasanya ditambahkan setelah node terakhir dari sebuah list. Gambar 5.11 Insert akhir node double link list menunjukan terdapat data dengan nilai 1, 3, dan 5 untuk menambahkan data dengan nilai 7 terletak pada posisi di akhir list. Sebuah linked list yang di representasikan oleh head pada awal suatu list, maka untuk menambahkan node terakhir pada list perlu mekakulan traversal list atau penelurusan list hingga node terakhir. Setelah node terakhir ditemukan, pointer pada node terakhir menunjuk pada node baru (7). head tail * *NULL1 *3* *5 * NULL * *7 NULL Gambar 5.11 Insert akhir node DLL 41 Implementasi prosedur insertlast. 1. void insertlast(int nilai) 2. { 3. node *new_node, *current; 4. new_node = new node; 5. new_node->data = nilai; Struktur Data dan Algoritma
6. new_node->next = NULL; 7. 8. if (isEmpty()) 9. { 10. 11. new_node->prev = NULL; 12. head = new_node; 13. 14. } 15. else 16. { 17. 18. current = head; 19. while(current->next != NULL) 20. { 21. 22. current = current->next; 23. } 24. } current->next= new_node; new_node->prev = current; } 3. Penyisipan sebelum atau setelah posisi node tertentu Prosedur ini bertugas untuk penyisipan sebuah node pada posisi tertentu berdasarkan nilai dari variabel. Gambar 5.12 insert pada posisi node tertentu pada double link list menunjukan sebuah list yang memiliki data awal 1, 5, dan 7. Pada posisi setelah node pertama atau sebelum node ke tiga, akan disispkan node baru dengan nilai 3. Maka akan merubah pointer next dan prev pada node sebelum dan sesudah node baru dan begitu juga pointer next dan prev pada node baru. head tail * *NULL1 *5* *7 * NULL *3* Gambar 5.12 Insert pada posisi node tertentu DLL 42 Struktur Data dan Algoritma
Implementasi prosedur insertAfter. 1. void insertAfter(struct node *next_node, int nilai) 2. { 3. if(next_node == NULL) 4. { 5. cout<<\"Nilai sebelumnya tidak boleh NULL\"; 6. return; 7. } 8. node *new_node = new node; 9. new_node->data = nilai; 10. 11. if (isEmpty()) 12. { 13. new_node->prev->next=new_node; 14. 15. } 16. else 17. { 18. new_node->prev = next_node->prev; 19. next_node->prev = new_node; 20. new_node->next = next_node; 21. head->next = new_node; 22. } 23. } 5.3.2 Delete List Suatu node dapat dihapus dari sebuah double list nilai pada node tertentu antara lain: 1. Delete First Pengahapusan node pada awal melakukan pengecekan prosedur isEmpty, jika pada suatu list belum terdapat linked list maka head berniali NULL. Sedangkan jika sudah memiliki data, maka head menunju pada posisi pointer next node yang dihapus dan nilai prev pada node tersebut menunjuk pada head ditunujukan pada gambar 5.13 hapus node awal pada double linked list. Struktur Data dan Algoritma 43
head tail * 1 * * 3 * * 5 * * 7 * NULL Gambar 5.13 Hapus node awal DLL Implementasi prosedur removefirst. 1. void removefirst(struct node *hapus) 2. { 3. int current; 4. 5. if(isEmpty()) 6. { 7. current = head->data; 8. head = NULL; 9. } 10. else 11. { 12. if (head = hapus) 13. head = hapus->next; 14. if (hapus->next != NULL) 15. hapus->next->prev = hapus->prev; 16. if (hapus->prev != NULL) 17. hapus->prev->next = hapus->next; 18. 19. delete hapus; 20. } 21. } 2. Delete Last Fungsi ini bertugas untuk menghapus node yang berada pada node paling belakang pada double linked list. Pada delete list terdapat tiga kondisi antara lain jika data kosong pada linkedlist maka nilai head ialah NULL. Kondisi kedua jika memilki sebuah node, maka yang akan dihapus ialah node tersebut sehingga nilai head dan tail Struktur Data dan Algoritma 44
menjadi NULL. Kondisi ketiga ialah sebuah linked list yang memilki nilai ditunjukan pada gambar 5.14 hapus node akhir double linked list, untuk mengecek node terakhir dibutuhkan traversal atau penelusuran tiap node. Setalah didapatkan nilai akhir pada sebuah double linked list, maka prev pada node tersebut ialah node terakhir yang memilki pointer next pada tail dan pointer prev tail menunjuk pada node tersebut. head tail * 1 * * 3 * * 5 * * 7 * NULL Gambar 5.14 Hapus node akhir DLL 45 1. void removelast() 2. { 3. node *hapus, *current; 4. 5. if(isEmpty()) 6. { 7. head = NULL; 8. } 9. else if (head->next == NULL) 10. { 11. hapus = head; 12. head = NULL; 13. tail = NULL; 14. delete hapus; 15. } 16. else 17. { 18. current = head; 19. while(current->next->next!=NULL) 20. { 21. current = current->next; 22. } 23. delete current->next; Struktur Data dan Algoritma
Search
