Advertisement
loading...

 

 

MATERI PELATIHAN BERBASIS KOMPETENSI

SEKTOR TELEMATIKA

SUB SEKTOR PROGRAMMER KOMPUTER

 

 

MEMBUAT STRUKTUR DATA

TIK.PR02.003.01

 

 

 

 

BUKU INFORMASI

 

 

 

 

 

DEPARTEMEN TENAGA KERJA DAN TRANSMIGRASI R.I.

DIREKTORAT JENDERAL PEMBINAAN PELATIHAN DAN PRODUKTIVITAS

Jl. Jend. Gatot Subroto Kav.51 Lt.7.B Jakarta Selatan

 

 

DAFTAR ISI

 

Daftar Isi Hal…………………………………………………………………………………………..1

BAB I    PENGANTAR ……………………………………………………………………………. 4

1.1.           Konsep Dasar Pelatihan Berbasis Kompetensi …………………………. 4

1.2.           Penjelasan Modul…………………………………………………………….. 4

1.2.1     Isi Modul……………………………………………………………. 4

1.2.2     Pelaksanaan Modul……………………………………………….. 5

1.3.           Pengakuan Kompetensi Terkini (RCC)…………………………………… 6

1.4.           Pengertian-pengertian Istilah……………………………………………… 7

 

BAB II   STANDAR KOMPETENSI………………………………………………………………. 9

2.1.           Peta Paket Pelatihan ……………………………………………………….. 9

2.2.           Pengertian Unit Standar Kompetensi……………………………………. 9

2.3.           Unit Kompetensi yang Dipelajari ………………………………………… 10

2.3.1.      Judul Unit ………………………………………………………….. 10

2.3.2.      Kode Unit ………………………………………………………….. 10

2.3.3.      Deskripsi Unit …………………………………………………….. 10

2.3.4.      Elemen Kompetensi ……………………………………………… 11

2.3.5.      Batasan Variabel ………………………………………………….. 13

2.3.6.      Panduan Penilaian ……………………………………………….. 13

2.3.7.      Kompetensi Kunci ………………………………………………… 14

 

BAB III  STRATEGI DAN METODE PELATIHAN …………………………………………….. 15

3.1.           Strategi Pelatihan …………………………………………………………… 15

3.2.           Metode Pelatihan ……………………………………………………………. 16

 

BAB IV  MATERI UNIT KOMPETENSI …………………………………………………………. 17

4.1             Pengertian Algoritma ………………………………………………………. 18

4.2             Perbedaan antara Tipe Data, Obyek Data dan Struktur Data  ……… 18

4.2.1     ADT (Abstract Data Type) atau tipe data bentukan ……….. 20

4.3             Array ………………………………………………………………………….. 22

4.3.1     Apakah itu Array ? ……………………………………………….. 22

4.3.2     Pengaksesan Elemen Array …………………………………….. 22

4.3.3     Deklarasi Array 1 Dimensi ………………………………………. 23

4.3.4     Penjelasan Array 1 Dimensi ……………………………………. 24

4.3.5     Deklarasi Array 2 Dimensi ………………………………………. 24

4.4             Searching …………………………………………………………………….. 29

4.4.1…. Pengertian Searching ……………………………………………. 29

4.4.2 … Teknik-teknik Searching ………………………………………… 29

4.5             Sorting ………………………………………………………………………… 32

4.5.1…. Bubble Sort ………………………………………………………… 33

4.5.2…. Selection Sort …………………………………………………….. 34

4.5.3…. Insertion Sort …………………………………………………….. 35

4.5.4…. Tabel Perbandingan Kecepatan Metode Pengurutan

……….. Data…………………………………………………………………. 35

4.6       Pointer ………………………………………………………………………… 36

4.6.1     Apa itu Pointer ? …………………………………………………. 36

4.6.2     Deklarasi Pointer …………………………………………………. 38

4.6.3     Operasi pada Pointer ……………………………………………. 38

4.6.4     Pointer pada Array 1 dan 2 Dimensi …………………………. 42

4.7       Linked List ……………………………………………………………………. 44

4.7.1     Apa itu Linked List ? …………………………………………….. 44

4.7.2     Single Linked List Non Circular ………………………………… 45

4.7.3     Single Linked List Circular ………………………………………. 54

4.7.4     Double Linked List Non Circular ……………………………….. 71

4.7.5     Double Linked List Circular …………………………………….. 84

4.8       List dalam Stack dan Queue ………………………………………………. 98

4.8.1     Pengertian Stack …………………………………………………. 98

4.8.2     Operasi Fungsi Stack …………………………………………….. 99

4.8.3     Queue dengan Menggunakan Array …………………………… 101

4.9       List dalam Tree ……………………………………………………………… 105

4.9.1     Pengertian Tree …………………………………………………… 105

4.9.2     Implementasi Program Tree ……………………………………. 106

4.10      Hash Table …………………………………………………………………… 108

4.11      Mengoperasikan File ……………………………………………………….. 109

4.11.1   Membuka File ……………………………………………………… 110

4.11.2   Menulis ke File …………………………………………………….. 111

4.11.3   Penambahan Data pada File ……………………………………. 111

4.11.4   Menutup File ………………………………………………………. 112

 

BAB V   SUMBER-SUMBER YANG DIPERLUKAN UNTUK PENCAPAIAN KOMPETENSI………………            114

5.1.           Sumber Daya Manusia ……………………………………………………… 114

5.2.           Sumber-sumber Perpustakaan ……………………………………………. 115

5.3.           Daftar Peralatan dan Bahan yang digunakan ………………………….. 116

 

DAFTAR PUSTAKA ……………………………………………………………………………….. 118

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

BAB I

PENGANTAR

 

1.1.      Konsep Dasar Pelatihan Berbasis Kompetensi

 

  • Apakah pelatihan berdasarkan kompetensi?

Pelatihan berdasarkan kompetensi adalah pelatihan yang memperhatikan pengetahuan, keterampilan dan sikap yang diperlukan di tempat kerja agar dapat melakukan pekerjaan dengan kompeten. Standar Kompetensi dijelaskan oleh Kriteria Unjuk Kerja.

 

  • Apakah artinya menjadi kompeten ditempat kerja?

Jika Anda kompeten dalam pekerjaan tertentu, Anda memiliki seluruh keterampilan, pengetahuan dan sikap yang perlu untuk ditampilkan secara efektif ditempat kerja, sesuai dengan standar yang telah disetujui.

 

1.2      Penjelasan Modul

 

Modul ini didisain untuk dapat digunakan pada Pelatihan Klasikal dan Pelatihan Individual/mandiri :

  • Pelatihan klasikal adalah pelatihan yang disampaiakan oleh seorang pelatih.
  • Pelatihan individual/mandiri adalah pelatihan yang dilaksanakan oleh peserta dengan menambahkan unsur-unsur/sumber-sumber yang diperlukan dengan bantuan dari pelatih.

 

1.2.1    Isi Modul

a.    Buku Informasi

Buku informasi ini adalah sumber pelatihan untuk pelatih maupun peserta pelatihan.

 

 

b.    Buku Kerja

Buku kerja ini harus digunakan oleh peserta pelatihan untuk mencatat setiap pertanyaan dan kegiatan praktik baik dalam Pelatihan Klasikal maupun Pelatihan Individual / mandiri.

 

Buku ini diberikan kepada peserta pelatihan dan berisi :

  • Kegiatan-kegiatan yang akan membantu peserta pelatihan untuk mempelajari dan memahami informasi.
  • Kegiatan pemeriksaan yang digunakan untuk memonitor pencapaian keterampilan peserta pelatihan.
  • Kegiatan penilaian untuk menilai kemampuan peserta pelatihan dalam melaksanakan praktik kerja.

 

c.     Buku Penilaian

Buku penilaian ini digunakan oleh pelatih untuk menilai jawaban dan tanggapan peserta pelatihan pada Buku Kerja dan berisi :

  • Kegiatan-kegiatan yang dilakukan oleh peserta pelatihan sebagai pernyataan keterampilan.
  • Metode-metode yang disarankan dalam proses penilaian keterampilan peserta pelatihan.
  • Sumber-sumber yang digunakan oleh peserta pelatihan untuk mencapai keterampilan.
  • Semua jawaban pada setiap pertanyaan yang diisikan pada Buku Kerja.
  • Petunjuk bagi pelatih untuk menilai setiap kegiatan praktik.
  • Catatan pencapaian keterampilan peserta pelatihan.

 

1.2.2    Pelaksanaan Modul

Pada pelatihan klasikal, pelatih akan :

  • Menyediakan Buku Informasi yang dapat digunakan peserta pelatihan sebagai sumber pelatihan.
  • Menyediakan salinan Buku Kerja kepada setiap peserta pelatihan.
  • Menggunakan Buku Informasi sebagai sumber utama dalam penyelenggaraan pelatihan.
  • Memastikan setiap peserta pelatihan memberikan jawaban / tanggapan dan menuliskan hasil tugas praktiknya pada Buku Kerja.

 

Pada Pelatihan individual / mandiri, peserta pelatihan akan :

  • Menggunakan Buku Informasi sebagai sumber utama pelatihan.
  • Menyelesaikan setiap kegiatan yang terdapat pada buku Kerja.
  • Memberikan jawaban pada Buku Kerja.
  • Mengisikan hasil tugas praktik pada Buku Kerja.
  • Memiliki tanggapan-tanggapan dan hasil penilaian oleh pelatih.

 

1.3        Pengakuan Kompetensi Terkini (RCC)

  • Apakah Pengakuan Kompetensi Terkini (Recognition of Current Competency).

Jika Anda telah memiliki pengetahuan dan keterampilan yang diperlukan untuk elemen unit kompetensi tertentu, Anda dapat mengajukan pengakuan kompetensi terkini (RCC). Berarti Anda tidak akan dipersyaratkan untuk belajar kembali.

  • Anda mungkin sudah memiliki pengetahuan dan keterampilan, karena Anda telah :
  1. Bekerja dalam suatu pekerjaan yang memerlukan suatu pengetahuan dan keterampilan yang sama atau
  2. Berpartisipasi dalam pelatihan yang mempelajari kompetensi yang sama atau
  3. Mempunyai pengalaman lainnya yang mengajarkan pengetahuan dan keterampilan yang sama.

 

 

1.4        Pengertian-pengertian Istilah

 

Profesi

Profesi adalah suatu bidang pekerjaan yang menuntut sikap, pengetahuan serta keterampilan/keahlian kerja tertentu yang diperoleh dari proses pendidikan, pelatihan serta pengalaman kerja atau penguasaan sekumpulan kompetensi tertentu yang dituntut oleh suatu pekerjaan/jabatan.

 

Standardisasi

Standardisasi adalah proses merumuskan, menetapkan serta menerapkan suatu standar tertentu.

 

Penilaian / Uji Kompetensi

Penilaian atau Uji Kompetensi adalah proses pengumpulan bukti melalui perencanaan, pelaksanaan dan peninjauan ulang (review) penilaian serta keputusan mengenai apakah kompetensi sudah tercapai dengan membandingkan bukti-bukti yang dikumpulkan terhadap standar yang dipersyaratkan.

 

Pelatihan

Pelatihan adalah proses pembelajaran yang dilaksanakan untuk mencapai suatu kompetensi tertentu dimana materi, metode dan fasilitas pelatihan serta lingkungan belajar yang ada terfokus kepada pencapaian unjuk kerja pada kompetensi yang dipelajari.

 

Kompetensi

Kompetensi adalah kemampuan seseorang untuk menunjukkan aspek sikap, pengetahuan dan keterampilan serta penerapan dari ketiga aspek tersebut ditempat kerja untuk mencapai unjuk kerja yang ditetapkan.

 

 

 

 

Standar Kompetensi

Standar kompetensi adalah standar yang ditampilkan dalam istilah-istilah hasil serta memiliki format standar yang terdiri dari judul unit, deskripsi unit, elemen kompetensi, kriteria unjuk kerja, ruang lingkup serta pedoman bukti.

 

Sertifikat Kompetensi

Adalah pengakuan tertulis atas penguasaan suatu kompetensi tertentu kepada seseorang yang dinyatakan kompeten yang diberikan oleh Lembaga Sertifikasi Profesi.

 

Sertifikasi Kompetensi

Adalah proses penerbitan sertifikat kompetensi melalui proses penilaian / uji kompetensi.

 

BAB II

STANDAR KOMPETENSI

 

2.1.      Peta Paket Pelatihan

Modul yang sedang Anda pelajari ini adalah untuk mencapai satu unit kompetensi, yang termasuk dalam satu paket pelatihan, yang terdiri atas unit-unit kompetensi berikut:

2.1.1.      TIK.PR02.003.01 Membuat Struktur Data

2.1.2.      TIK.OP02.003.01 Mengoperasikan Sistem Operasi

2.1.3.      TIK.OP02.001.01 Mengoperasikan komputer personal yang berdiri

sendiri (PC stand alone)

2.1.4.      TIK.PR02.001.01 Membuat Algoritma Pemrograman Dasar

2.1.5.      TIK.PR02.002.01 Membuat Algoritma Pemrograman Lanjut

2.1.6.      TIK.PR02.008.01 Mengoperasikan Pemrograman Terstruktur

 

2.2.      Pengertian Unit Standar Kompetensi

Apakah Standar Kompetensi?

Setiap Standar Kompetensi menentukan :

  1. Pengetahuan dan keterampilan yang diperlukan untuk mencapai kompetensi.
  2. Standar yang diperlukan untuk mendemonstrasikan kompetensi.
  3. Kondisi dimana kompetensi dicapai.

 

Apa yang akan Anda pelajari dari Unit Kompetensi ini?

Anda akan diajarkan untuk mempelajari struktur data yang akan diterapkan pada setiap pemrograman yang akan dipakai.

 

Berapa lama Unit Kompetensi ini dapat diselesaikan?

Pada sistem pelatihan berdasarkan kompetensi, fokusnya ada pada pencapaian kompetensi, bukan pada lamanya waktu. Namun diharapkan pelatihan ini dapat dilaksanakan dalam jangka waktu satu sampai dua hari. Pelatihan ini ditujukan bagi semua pengguna terutama yang tugasnya berkaitan dengan pemrograman seperti programmer C atau C++.

Berapa banyak/kesempatan yang Anda miliki untuk mencapai kompetensi?

Jika Anda belum mencapai kompetensi pada usaha/kesempatan pertama, Pelatih Anda akan mengatur rencana pelatihan dengan Anda. Rencana ini akan memberikan Anda kesempatan kembali untuk meningkatkan level kompetensi Anda sesuai dengan level yang diperlukan.

Jumlah maksimum usaha/kesempatan yang disarankan adalah 3 (tiga) kali.

 

2.3.      Unit Kompetensi yang Dipelajari

Dalam sistem pelatihan, Standar Kompetensi diharapkan menjadi panduan bagi peserta pelatihan  untuk dapat :

  • mengidentifikasikan apa yang harus dikerjakan peserta pelatihan.
  • memeriksa kemajuan peserta pelatihan.
    • menyakinkan bahwa semua elemen (sub-kompetensi) dan kriteria unjuk   kerja telah dimasukkan dalam pelatihan dan penilaian.

 

2.3.1 JUDUL UNIT          :    Membuat Struktur Data

 

2.3.2 KODE UNIT           :    TIK.PR02.003.01

 

          2.3.3 DESKRIPSI UNIT   :  Unit ini menentukan kompetensi yang diperlukan untuk mempelajari struktur data yang akan diterapkan pada setiap pemrograman yang akan dipakai. Struktur data merupakan materi dasar kelanjutan dari mengidentifikasi algoritma pemrograman dengan lingkup pembahasan pada pemanfaatan array dan pointer untuk kasus-kasus yang mendekati kehidupan sehari-hari.

         

2.3.4 ELEMEN KOMPETENSI

 

 

ELEMEN KOMPETENSI

 

KRITERIA UNJUK KERJA

01     Menerapkan konsep data

dan struktur data

1.1      Program dengan berbagai tipe data dibuat.

1.2     Program dengan tipe data array dan pointer dibuat.

02     Menerapkan array dan record 2.1     Algoritma program dengan array dan pengoperasiannya berupa pencarian dan pengurutan dibuat.

2.2     Algoritma program dengan record seperti pembuatan / penambahan, pengisian, pengubahan dan penghapusan record dibuat.

2.3     Algoritma program dengan array dan record dibuat.

03     Menerapkan pointer 3.1      Algoritma program dengan tipe data pointer dibuat.

3.2      Algoritma program manipulasi data (penambahan, pengurangan, pengisian data, dsb) tipe pointer dibuat.

04     Menerapkan list berkait 4.1     Macam-macam list berkait dijelaskan. List berkait dapat berupa list tunggal, list yang tercatat alamat awal dan akhir, list ganda dsb.

4.2     Algoritma program dengan operasi list berkait dibuat. Operasi list berkait yang diterapkan berupa pembuatan elemen list, penambahan data ke dalam elemen, penyambungan elemen ke dalam list, pemutusan elemen dari list.

4.3     List berkait dengan tipe array dibuat. Dengan penggunaan array sebagai list, maka komponen list harus tetap direalisasikan.

4.4     List berkait dengan tipe pointer dibuat. Dengan penggunaan pointer sebagai list maka komponen list harus tetap direalisasikan.

05     Menerapkan list berkait 5.1     List berkait dalam model antrian (queue) dalam array dan pointer dibuat. Model antrian direalisasikan.

5.2     List berkait untuk model tumpukan (stack) dibuat. Model tumpukan direalisasikan dalam bentuk array dan pointer.

5.3     List berkait untuk model graph dibuat. Model graph direalisasikan dalam bentuk array pointer.

5.4     List berkait untuk model pohon dibuat. Model pohon direalisasikan dalam bentuk array dan pointer.

5.5     List berkait untuk model Hash table dibuat. Model hash table direalisasikan dalam bentuk array dan pointer.

06     Mengoperasikan file secara list berkait 6.1 List berkait untuk pencarian file indeks dioperasikan. Penulisan file berbasis indeks banyak digunakan terutama untuk menyimpan data yang terorganisasi guna percepatan dalam proses pencarian dilakukan berdasarkan indeks yang telah disimpan pada list.

 

 

 

 

2.3.5 BATASAN VARIABEL

 

1.       Unit ini berlaku untuk seluruh sektor teknologi informasi dan komunikasi.

2.       Membuat struktur data bersifat internal pada bidang teknologi informasi dan komunikasi.

 

2.3.6 PANDUAN PENILAIAN

 

1.       Pengetahuan dan keterampilan penunjang untuk mendemontrasikan kompetensi, diperlukan bukti keterampilan dan pengetahuan di bidang berikut ini :

1.1         Pengetahuan dasar :

1.1.1  Mengidentifikasi algoritma pemrograman.

1.1.2    Menguasai bahasa pemrograman.

1.2     Keterampilan Dasar.

1.2.1  Mengoperasikan sistem komputer.

1.2.2  Mengoperasikan bahasa pemrograman.

2.       Konteks penilaian

Kompetensi harus diujikan di tempat kerja atau di tempat lain secara praktek dengan kondisi kerja sesuai dengan keadaan normal.

 

3.       Aspek penting penilaian

Aspek yang harus diperhatikan

3.1     Kemampuan membuat algoritma program menggunakan array dan pointer.

3.2         Kemampuan mengidentifikasi penerapan list berkait sesuai dengan model yang           akan direalisasikan (queue, stack, graph, tree atau hash table).

3.3         Kemampuan mengidentifikasi pengoperasian file dengan menerapkan model list berkait.

4.       Kaitan dengan unit-unit lainnya

4.1         Unit ini didukung oleh pengetahuan dan keterampilan dalam unit-unit kompetensi yang berkaitan dengan dasar-dasar teknologi informasi:

4.1.1             TIK.OP02.003.01 Mengoperasikan Sistem Operasi

4.1.2             TIK.OP02.001.01 Mengoperasikan komputer personal yang

berdiri sendiri (PC stand alone)

4.1.3     TIK.PR02.001.01 Membuat algoritma pemrograman Dasar.

4.1.4     TIK.PR02.002.01 Membuat algoritma pemrograman lanjut

4.1.5  TIK.PR02.008.01 Mengoperasikan pemrograman

terstruktur.

 

4.2         Pengembangan pelatihan untuk memenuhi persyaratan dalam unit ini perlu dilakukan dengan hati-hati. Untuk pelatihan pra kejuruan umum, institusi harus menyediakan pelatihan yang mempertimbangkan serangkaian konteks industri seutuhnya tanpa bias terhadap sektor tertentu. Batasan variabel akan membantu dalam hal ini. Untuk sektor tertentu/khusus, pelatihan harus disesuaikan untuk memenuhi kebutuhan sektor tersebut.

 

2.3.7 KOMPETENSI KUNCI

 

NO

KOMPETENSI KUNCI DALAM UNIT INI

TINGKAT

1

Mengumpulkan, mengorganisir dan menganalisa informasi

2

2

Mengkomunikasikan ide-ide dan informasi

2

3

Merencanakan dan mengorganisir aktifitas-aktifitas

2

4

Bekerja dengan orang lain dan kelompok

1

5

Menggunakan ide-ide dan teknik matematika

2

6

Memecahkan masalah

3

7

Menggunakan teknologi

2

 

BAB III

STRATEGI DAN METODE PELATIHAN

 

3.1.      Strategi Pelatihan        

Belajar dalam suatu sistem Berdasarkan Kompetensi berbeda dengan yang sedang “diajarkan” di kelas oleh Pelatih. Pada sistem ini Anda akan bertanggung jawab terhadap belajar Anda sendiri, artinya bahwa Anda perlu merencanakan belajar Anda dengan Pelatih dan kemudian melaksanakannya dengan tekun sesuai dengan rencana yang telah dibuat.

 

Persiapan/perencanaan

  1. Membaca bahan/materi yang telah diidentifikasi dalam setiap tahap belajar dengan tujuan mendapatkan tinjauan umum mengenai isi proses belajar Anda.
  2. Membuat catatan terhadap apa yang telah dibaca.
  3. Memikirkan bagaimana pengetahuan baru yang diperoleh berhubungan dengan pengetahuan dan pengalaman yang telah Anda miliki.
  4. Merencanakan aplikasi praktik pengetahuan dan keterampilan Anda.

 

Permulaan dari proses pembelajaran

  1. Mencoba mengerjakan seluruh pertanyaan dan tugas praktik yang terdapat pada tahap belajar.
  2. Merevisi dan meninjau materi belajar agar dapat menggabungkan pengetahuan Anda.

 

Pengamatan terhadap tugas praktik

  1. Mengamati keterampilan praktik yang didemonstrasikan oleh Pelatih atau orang yang telah berpengalaman lainnya.
  2. Mengajukan pertanyaan kepada Pelatih tentang konsep sulit yang Anda temukan.

 

 

 

 

Implementasi

  1. Menerapkan pelatihan kerja yang aman.
  2. Mengamati indikator kemajuan personal melalui kegiatan praktik.
  3. Mempraktikkan keterampilan baru yang telah Anda peroleh.

 

Penilaian

Melaksanakan tugas penilaian untuk penyelesaian belajar Anda.

 

3.2.          Metode Pelatihan      

Terdapat tiga prinsip metode belajar yang dapat digunakan. Dalam beberapa kasus, kombinasi metode belajar mungkin dapat digunakan.

 

Belajar secara mandiri

Belajar secara mandiri membolehkan Anda untuk belajar secara individual, sesuai dengan kecepatan belajarnya masing-masing. Meskipun proses belajar dilaksanakan secara bebas, Anda disarankan untuk menemui Pelatih setiap saat untuk mengkonfirmasikan kemajuan dan mengatasi kesulitan belajar.

 

Belajar Berkelompok

Belajar berkelompok memungkinkan peserta untuk dating bersama secara teratur dan berpartisipasi dalam sesi belajar berkelompok. Walaupun proses belajar memiliki prinsip sesuai dengan kecepatan belajar masing-masing, sesi kelompok memberikan interaksi antar peserta, Pelatih dan pakar/ahli dari tempat kerja.

 

Belajar terstruktur

Belajar terstruktur meliputi sesi pertemuan kelas secara formal yang dilaksanakan oleh Pelatih atau ahli lainnya. Sesi belajar ini umumnya mencakup topik tertentu.

 

 

 

 

 

BAB IV

MATERI UNIT KOMPETENSI

MEMBUAT STRUKTUR DATA

 

 

Tujuan Instruksional Umum

  • Siswa mampu membuat struktur data pada setiap pemrograman yang diperlukan.
  • Siswa mampu membuat algoritma pemrograman sesuai kebutuhan.

 

Tujuan Instruksional Khusus

  • Siswa mampu mengenal berbagai tipe data yang ada.
  • Siswa mampu membuat algoritma program dengan tipe data array dan pointer.
  • Siswa mampu mengetahui pemakaian array dan pointer.
  • Siswa mampu membuat algoritma berupa searching dan sorting.
  • Siswa mampu membuat record dengan benar.
  • Siswa mampu membuat algoritma dengan manipulasi data.
  • Siswa dapat mengetahui berbagai macam Linked-List.
  • Siswa mampu membuat algoritma dengan bermacam-macam Linked-List.
  • Siswa mampu membuat algoritma pencarian file atau database.


4.1 Pengertian Algoritma

 

Asal usul kata algoritma ?

 

Kata algoritma berasal dari kata-kata dibawah ini:

Al Khuwarizmi -> algorism -> algorithm (diserap dalam bahasa Indonesia menjadi algoritma).

Abu Ja’far Muhammad Ibnu Musa Al Khuwarizmi adalah seorang penulis buku Arab dari Persia yang berjudul Kitab Al Jabar Wal Muqabala (Buku Pemugaran dan Pengurangan) sekitar tahun 825 M. Kata Al Khuwarizmi dibaca orang Barat menjadi algorism.

Kata algorism berarti proses menghitung dengan angka Arab [1]. Seseorang dikatakan algorist jika orang tersebut menggunakan angka Arab. Kata algorism lambat laun menjadi algorithm disebabkan kata algorism sering dikelirukan dengan kata arithmetic sehingga akhiran –sm berubah menjadi   –thm. Kata algorithm diserap ke dalam bahasa Indonesia menjadi algoritma.

 

Apa yang dimaksud dengan Algoritma ?

 

Algoritma merupakan pola pikir yang terstruktur yang berisi tahap-tahap penyelesaian suatu masalah secara logis, yang nantinya akan diimplementasikan ke dalam suatu bahasa pemrograman.

Kata logis disini benar sesuai dengan logika manusia. Untuk menjadi sebuah algoritma, urutan langkah yang ditempuh untuk menyelesaikan masalah harus memberikan hasil yang benar.

 

4.2 Perbedaan antara Tipe Data, Obyek Data dan Struktur Data

 

Tipe data adalah jenis data yang ditangani oleh suatu bahasa pemrograman pada komputer.

Tiap-tiap bahasa pemrograman memiliki tipe data yang memungkinkan:

  • Deklarasi terhadap variabel tipe data tersebut.
  • Menyediakan kumpulan operasi yang mungkin terhadap variabel bertipe data tersebut.
  • Contoh: tipe data di C? Java? Pascal? .NET?

 

Obyek Data adalah kumpulan elemen yang mungkin untuk suatu tipe data tertentu.

  • Mis: Integer mengacu pada obyek data -32768 s/d 32767, byte 0 s/d 255, string adalah kumpulan karakter maks 225 huruf.

 

Struktur Data adalah cara penyimpanan dan pengorganisasian data-data pada memori komputer maupun file pada media penyimpanan secara efektif sehingga dapat digunakan secara efisien, termasuk operasi-operasi didalamnya.

Di dalam struktur data kita berhubungan dengan 2 aktivitas:

-      Mendeskripsikan kumpulan obyek data yang sah sesuai dengan tipe data yang ada.

-      Menunjukkan mekanisme kerja operasi-operasinya.

Contoh: integer (-32768 s/d 32767) dan jenis operasi yang diperbolehkan adalah +, -, *, /, mod, ceil, floor, <, >, !=, dsb.

Struktur data = obyek data + [operasi manipulasi]

 

Dengan pemilihan struktur data yang baik, maka problem yang kompleks dapat diselesaikan dengan algoritma yang dapat digunakan secara efisien, operasi-operasi penting dapat dieksekusi dengan sumber daya yang lebih kecil, memori lebih kecil, dan waktu eksekusi yang lebih cepat.

Ciri algoritma yang baik menurut Donald E. Knuth:

  • Input: ada minimal 0 input atau lebih.
  • Output: ada minimal 1 output atau lebih.
  • Definite: ada kejelasan apa yang dilakukan.
  • Efective: langkah yang dikerjakan harus efektif.
  • Terminate: langkah harus dapat berhenti (stop) secara jelas.

      

 

4.2.1 ADT (Abstract Data Type) atau Tipe Data Bentukan

 

Bahasa Pemrograman bisa memiliki tipe data:

  • Built-in : Sudah tersedia oleh bahasa pemrograman tersebut. Tidak berorientasi pada persoalan yang dihadapi.
  • UDT : User Defined Type, dibuat oleh pemrogram. UDT mendekati penyelesaian persoalan yang dihadapi. Contoh: record pada Pascal, struct pada C, class pada Java.
  • ADT : Abstract Data Type, memperluas konsep UDT dengan menambahkan pengkapsulan atau enkapsulasi, berisi sifat-sifat dan operasi-operasi yang bisa dilakukan terhadap kelas tersebut. Contoh: class pada Java. ADT adalah kumpulan dari elemen-elemen data yang disajikan dengan satu set operasi yang digambarkan pada elemen-elemen data tersebut. Stacks, queues, pohon biner adalah tiga contoh dari ADT.

Bahasa C memiliki tipe data numerik dan karakter (seperti int, float, char, dan lain-lain). Disamping itu juga memiliki tipe data enumerasi dan structure. Bagaimana jika kita ingin membuat tipe data baru? Untuk pembuatan tipe data baru digunakan keyword typedef.

Bentuk umum:

            typedef <tipe_data_lama> <ama_tipe_data_baru>

 

Contoh:

 

#include <stdio.h>

#include <conio.h>

 

typedef int angka;

typedef float pecahan;

typedef char huruf;

void main() {

 

    clrscr();

angka umur;

pecahan pecah;

huruf h;

 

huruf nama[10];

 

printf(“masukkan umur anda : ”);scanf(“%d”,&umur);

printf(“Umur anda adalah %d”,umur);

 

printf(“\nmasukkan bilangan pecahan : ”);

scanf(“%f”,&pecah);

printf(“Bilangan pecahan %f”,pecah);

 

printf(“\nmasukkan huruf : ”);h = getche();

printf(“\nHuruf anda %c”,h);

 

printf(“\nmasukkan nama : ”);scanf(“%s”,nama);

printf(“Nama anda %s”,nama);

 

getch();

}

 

 

 

 

4.3 Array

 

4.3.1 Apakah itu Array ?

 

Array adalah suatu tipe data terstruktur yang berupa sejumlah data sejenis (bertipe data sama) yang jumlahnya bisa statis ataupun dinamis dan diberi suatu nama tertentu. Antara satu variabel dengan variabel lain di dalam array dibedakan berdasarkan subscript. Sebuah subscript berupa bilangan di dalam kurung siku. Melalui subscript  inilah masing-masing elemen array dapat diakses. Subscript dari array selalu dimulai dari nol. Subscript terkadang disebut sebagai indeks array.

Elemen-elemen array tersusun secara berderet dan sekuensial didalam memori sehingga memiliki alamat yang bersebelahan/berdampingan.

Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-dimensi. Elemen-elemen array bertipe data sama tapi bisa bernilai sama atau berbeda-beda.

 

 

 

 

 

4.3.2 Pengaksesan Elemen Array

 

Setelah suatu array didefinisikan, elemen array dapat diakses dengan bentuk:

nama_array[subscript]

 

  • Elemen-elemen array dapat diakses oleh program menggunakan suatu indeks tertentu
  • Pengaksesan elemen array dapat dilakukan berurutan atau random berdasarkan indeks tertentu secara langsung.
  • Pengisian dan pengambilan nilai pada indeks tertentu dapat dilakukan dengan mengeset nilai atau menampilkan nilai pada indeks yang dimaksud.
  • Dalam C, tidak terdapat error handling terhadap batasan nilai indeks, apakah indeks tersebut berada di dalam indeks array yang sudah didefinisikan atau belum. Hal ini merupakan tanggung jawab programmer. Sehingga jika programmer mengakses indeks yang salah, maka nilai yang dihasilkan akan berbeda atau rusak karena mengakses alamat memori yang tidak sesuai.

 

4.3.3 Deklarasi Array 1 Dimensi

 

tipe_data nama_var_array[ukuran];

 

tipe_data : menyatakan jenis tipe data elemen larik (int, char, float, dll)

nama_var_array : menyatakan nama variabel yang dipakai.

ukuran : menunjukkan jumlah maksimal elemen larik.

 

Contoh:

char huruf[9];

int umur[10];

int kondisi[2] = {0,1}

int arr_dinamis[] = {1,2,3}

 

char huruf[9]:      berarti akan memesan tempat di memori komputer sebanyak 9 tempat dengan indeks dari 0-8, dimana semua elemennya bertipe data karakter semuanya. Kalau satu karakter berukuran 1 byte, berarti membutuhkan memori sebesar 9 byte.

int umur[10]:       berarti akan memesan tempat di memori komputer sebanyak 10 tempat dengan indeks dari 0-9, dimana semua elemennya bertipe data integer semuanya. Kalau satu integer berukuran 4 bytes, berarti membutuhkan memori sebesar 4 x 10 = 20 bytes.

int kondisi[2]:      berarti akan memesan tempat di memori komputer sebanyak 2 tempat dengan indeks 0-1, dimana semua elemennya bertipe data integer semuanya. Dan pada contoh di atas isi elemen-elemennya yang sebanyak 2 buah diisi sekaligus (diinisialisasi) yaitu pada elemen kondisi[0] bernilai 0, dan elemen kondisi[1] bernilai 1.

int arr_dinamis[]:berarti mendeklarasikan array dengan ukuran maksimum array tidak diketahui, namun ukuran tersebut diketahui berdasarkan inisialisasi yaitu sebanyak 3 elemen, yang isinya 1,2, dan 3.

 

4.3.4 Penjelasan Array 1 Dimensi

 

  • Tanda [] disebut juga “elemen yang ke- … Misalnya kondisi[0] berarti elemen yang ke nol.
  • Array yang sudah dipesan, misalnya 10 tempat tidak harus diisi semuanya, bisa saja hanya diisi 5 elemen saja, baik secara berurutan maupun tidak. Namun pada kondisi yang tidak sepenuhnya terisi tersebut, tempat pemesanan di memori tetap sebanyak 10 tempat, jadi tempat yang tidak terisi tetap akan terpesan dan dibiarkan kosong.

 

4.3.5 Deklarasi Array 2 Dimensi

 

C++ menyediakan array berdimensi dua. Array ini dapat digunakan untuk berbagai keperluan.

Sebagai gambaran, data kelulusan dari jurusan Teknik Informatika, Manajemen Informatika dan Teknik Komputer pada suatu Sekolah Tinggi Komputer dari tahun 2002 hingga 2005 dapat dinyatakan dengan array berdimensi dua.

 

Jurusan

2002

2003

2004

2005

Teknik Informatika 35 45 80 120
Manajemen Informatika 100 110 70 101
Teknik Komputer 10 15 20 17

 

 

Tabel diatas dapat didefinisikan ke dalam array berdimensi dua. Pendefinisiannya:

int data_lulus[3][4];

 

Penjelasan:

-      3 menyatakan jumlah baris (mewakili jurusan).

-      4 menyatakan jumlah kolom (mewakili tahun kelulusan).

 

Contoh 1 (variabel array dan variabel biasa)

//Dengan variabel biasa:

int x1=3,x2=5,x3=2,x4=7,x5=9;

//Dengan larik:

int x[5]={3,5,2,7,9};

Bagaimana jika kita ingin menghitung total dari variabel biasa?

total = x1 + x2 + x3 + x4 + x5;

 

Contoh 2 (menginputkan dan menampilkan array)

 

#include <stdio.h>

#include <conio.h>

 

void main()

{ int nilai[5], x;

clrscr();

 

printf(“Memasukkan nilai :\n”);

for(x=0;x<5;x++)

{

printf(“Nilai Angka : “); scanf(“%d”,&nilai[x]);

}

printf(“\n”);

 

  printf(“Membaca nilai :\n”);

for(x=0;x<5;x++)

{

printf(“Nilai Angka : %d“,nilai[x]);

}

getch();

}

 

Hasilnya:

 

 

Contoh 3 (manipulasi array 1 dimensi)

 

#include <stdio.h>

#include <conio.h>

 

int main(){

 

int bil[7],i;

printf(“elemen 1 ? “);scanf(“%d”,&bil[0]);

bil[1] = 5;

bil[2] = bil[1] + 20;

for(i=4;i<7;i++) bil[i] = i*10;

bil[3] = bil[bil[1]];

for(i=0;i<7;i++) printf(“bil[%d] = %d dan alamatnya:

%X\n”,i,bil[i],&bil[i]);

getch();

return 0;

}

 

Hasilnya:

 

 

Terlihat bahwa alamat array berurutan dengan jarak antar alamat adalah 4 bytes (integer berukuran 4 bytes).

 

Contoh 4 (tanpa inisialisasi langsung ditampilkan)

 

#include <stdio.h>

#include <conio.h>

 

int main(){

int bil[7]; //tanpa inisialisasi

for(int i=0;i<7;i++){

printf(“Elemen ke-%i = %d\n”,i,bil[i]);

}

getch();

return 0;

}

 

Hasilnya:

 

 

Contoh 5 (karakter yang tidak diinisialisasi)

 

#include <stdio.h>

#include <conio.h>

 

int main(){

char h[5];

for(int i=0;i<5;i++){

printf(“Elemen ke-%i = %c\n”,i,h[i]);

}

getch();

return 0;

}

 

 

 

 

 

 

 

 

Hasilnya:

 

4.4 Searching

 

4.4.1 Pengertian Searching

 

Searching adalah pencarian data dengan menelusuri tempat pencarian data tersebut. Tempat pencarian data tersebut dapat berupa array dalam memori, bias juga pada file pada external storage. Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching.

 

4.4.2 Teknik-teknik Searching

 

  • Sequential Search adalah suatu teknik pencarian data dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal).

Kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).

 

Misalnya terdapat array satu dimensi sebagai berikut:

 

 

 

Kemudian program akan meminta data yang akan dicari, misalnya 6. Jika ada maka akan ditampilkan tulisan “ADA”, sedangkan jika tidak ada

maka akan ditampilkan tulisan “TIDAK ADA”.

 

#include <stdio.h>

#include <conio.h>

 

void main(){

clrscr();

int data[8] = {8,10,6,-2,11,7,1,100};

int cari;

int flag=0;

printf(“masukkan data yang ingin dicari = “);scanf(“%d”,&cari);

for(int i=0;i<8;i++){

if(data[i] == cari) flag=1;

}

if(flag==1) printf(“Data ada!\n”);

else printf(“Data tidak ada!\n”);

 

 

 

 

- Dari program diatas, terlihat bahwa dilakukan perulangan untuk mengakses semua elemen array data satu persatu berdasarkan indeksnya.

- Program menggunakan sebuah variabel flag berguna untuk menandai ada atau tidaknya data yang dicari dalam array data. Hanya bernilai 0 atau 1.

- Flag pertama kali diinisialiasasi dengan nilai 0.

- Jika ditemukan, maka flag akan diset menjadi 1, jika tidak ada maka flag akan tetap bernilai 0.

- Semua elemen array data akan dibandingkan satu persatu dengan data yang dicari dan diinputkan oleh user.

 

  • Binary Search adalah teknik pencarian data dalam dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pengurutan. Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian.

 

Prinsip pencarian biner adalah:

- Data diambil dari posisi 1 sampai posisi akhir N

- Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2

- Kemudian data yang dicari dibandingkan dengan data yang ditengah, apakah sama atau lebih kecil, atau lebih besar?

- Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1

- Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1

- Jika data sama, berarti ketemu.

 

  • Interpolation Search, teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu. Teknik searching ini dilakukan dengan perkiraan letak data.

Contoh ilustrasi: jika kita hendak mencari suatu nama di dalam buku telepon, misal yang berawalan dengan huruf T, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada 2/3 atau ¾ dari tebal buku. Jadi kita mencari data secara relatif terhadap jumlah data.

Rumus posisi relatif kunci pencarian dihitung dengan rumus:

 

 

4.5 Sorting

 

Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.Pengurutan data dalam struktur data sangat penting untuk data yang bertipe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending dan descending.

 

METODE PENGURUTAN DATA:

• Pengurutan berdasarkan perbandingan (comparison-based sorting)

Bubble sort, exchange sort

• Pengurutan berdasarkan prioritas (priority queue sorting method)

Selection sort, heap sort

• Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)

Insertion sort, tree sort

• Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)

Quick sort, merge sort

• Pengurutan berkurang menurun (diminishing increment sort method)

Shell sort

 

4.5.1 Bubble Sort

 

Buble Sort merupakan metode sorting termudah. Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak / berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya.

 

Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya. Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

 

Contoh prosedur:

Versi 1

void bubble_sort(){

for(int i=1;i<n;i++){

for(int j=n-1;j>=i;j–){

if(data[j]<data[j-1])

tukar(&data[j],&data[j-1]); //ascending

}

}

}

 

Versi 2

void bubblesort2(){

for(i=1;i<6;i++){

for(int j=0;j<6-i;j++){

if(data[j]>data[j+1])

tukar(&data[j],&data[j+1]); //descending

}

}

}

 

“The bubble sort is an easy algorithm to program, but it is slower than many other sorts”

 

4.5.2 Selection Sort

 

Merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).

Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

 

Contoh prosedur:

void selection_sort(){

for(int i=0;i<n-1;i++){

pos = i;

for(int j=i+1;j<n;j++){

if(data[j] < data[pos]) pos = j; //ascending

}

if(pos != i) tukar(pos,i);

}

}

 

4.5.3 Insertion Sort

 

Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.

 

Contoh prosedur:

void insertion_sort(){

int temp;

for(int i=1;i<n;i++){

temp = data[i];

j = i -1;

while(data[j]>temp && j>=0){

data[j+1] = data[j];

j–;

}

data[j+1] = temp;

}

}

 

4.5.4 Tabel Perbandingan Kecepatan Metode Pengurutan Data

 

Untuk data sejumlah 10.000 data pada komputer Pentium II 450 MHz

 

Metode

Waktu (detik)

Data Acak Data Ascending Data Descending
Bubble Sort 11,2 1,32 19,77
Insertion Sort 11,09 0,00 2,25
Selection Sort 1,32 1,32 19,77

4.6 Pointer

 

4.6.1 Apa itu 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. Lokasi memori tersebut bisa diwakili sebuah variabel atau juga berupa alamat memori secara langsung.

 

Ilustrasi:

-    Kita memiliki variabel X yang berisi nilai karakter ‘a’

-    Oleh kompiler C, nilai ‘a’ ini akan disimpan di suatu alamat tertentu di memori.

-    Nilai alamat variabel X dapat diakses dengan menggunakan statement  &X.

-    Jika kita ingin menyimpan alamat dari variabel X ini, kita dapat menggunakan suatu variabel, misalnya alamat_x = &X;

-    alamat_x adalah suatu variabel yang berisi alamat dimana nilai X, yaitu ‘a’ disimpan. alamat_x disebut variabel pointer atau sering disebut pointer saja.

 

Contoh:

 

#include <stdio.h>

 

void main(){

char *alamat_x; //menyiapkan variabel alamat_x bertipe

//pointer to char

char X; //menyiapkan variabel X bertipe karakter

X = ‘a’; //mengisi variabel X dengan nilai ‘a’

alamat_x = &X; //mengisi variabel alamat_x dengan alamat X

printf(“Nilai variabel X, yaitu %c, disimpan pada alamat

%p”,X,alamat_x);

}

Hasilnya:

 

 

Pointer VS Variabel Biasa

 

Variabel Biasa

Pointer

Berisi data/nilai Berisi alamat memori dari suatu variable tertentu
Operasi yang bisa dilakukan seperti

layaknya operasi biasa: +, -, *, /

Membutuhkan operator khusus: “&” yang

menunjuk alamat dari suatu variable tertentu. Operator “&” hanya dapat dilakukan kepada variabel dan akan mengahasilkan 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;

 

Terdapat 2 buah operator pointer, yaitu:

 

Operator *

 

Mendapatkan

nilai data dari

variabel pointer

 

Contoh:

int *alamat;

int nilai = 10;

alamat = &nilai;

printf(“%d”,*alamat);

Hasil:

10

 

Operator &

 

Mendapatkan

alamat memori

dari variabel

pointer

Contoh:

int *alamat;

int nilai = 10;

alamat = &nilai;

printf(“%p”,alamat);

Hasil:

FFCCDD

 

 

4.6.2 Deklarasi Pointer

 

Pointer dideklarasikan dengan cara:

Tipe_data *nama_variabel_pointer;

 

Variabel pointer dapat dideklarasikan dengan tipe data apapun. Pendeklarasian variabel pointer dengan tipe data tertentu digunakan untuk menyimpan alamat memori tertentu, bukan untuk berisi nilai tertentu. Misalnya jika suatu variabel pointer dideklarasikan dengan tipe float, berarti variabel pointer tersebut hanya bisa digunakan untuk menunjuk alamat memori yang berisi nilai bertipe float.

 

4.6.3 Operasi Pada Pointer

 

Operasi yang bisa dilakukan oleh variabel pointer adalah:

  • Operasi pemberian nilai.

Antar variabel pointer dapat dilakukan operasi pemberian nilai.

 

Contoh 1:

Pemberian nilai, sebuah alamat dapat ditunjuk oleh lebih dari satu pointer.

 

#include <stdio.h>

void main(){

float y,*x1,*x2;

y = 12.34;

x1 = &y;

x2 = x1; //operasi pemberian nilai

printf(“nilai y pada x1 adalah %2.2f di alamat

%p\n”,y,x1);

printf(“nilai y pada x2 adalah %2.2f di alamat

%p\n”,*x2,x2);

}

Hasil:

 

 

Contoh 2:

Mengisi variabel dengan nilai yang ditunjuk oleh sebuah variabel pointer.

 

#include <stdio.h>

 

void main(){

int *p,a=25,b;

p = &a;

b = *p;

printf(“nilai a = %d di alamat %p\n”,a,p);

printf(“nilai b = %d di alamat %p\n”,b,p);

}

 

Hasil:

 

Contoh 3:

Mengoperasikan isi variabel dengan menyebut alamatnya dengan pointer.

 

#include <stdio.h>

 

void main(){

int a=25,b=12;

int *p,*q;

p = &a;

q = &b;

printf(“nilai yang ditunjuk p = %d di alamat

%p\n”,*p,p);

printf(“nilai yang ditunjuk q = %d di alamat

%p\n”,*q,q);

*q = *p;

printf(“nilai yang ditunjuk p = %d di alamat

%p\n”,*p,p);

printf(“nilai yang ditunjuk q = %d di alamat

%p\n”,*q,q);

}

 

Hasil:

 

 

Contoh 4:

Mengisi dan mengganti variabel yang ditunjuk oleh pointer.

 

 

#include <stdio.h>

 

void main(){

int a,*p;

p=&a;

*p=25;

printf(“nilai a = %d”,a);

}

 

Hasil:

 

 

  • Operasi aritmatika

Variabel pointer dapat dilakukan operasi aritmatika yang akan menunjuk suatu alamat memori baru.

 

Contoh1:

 

#include <stdio.h>

 

void main(){

char S[] = “anton”;

char *p;

//cara 1

p=S; //menunjuk alamat dari karakter pertama.

//cara 2

//p=&S[0]; //sama, menunjuk alamat dari karakter

pertama

for(int i=0;i<5;i++){

printf(“%c”,*p);

p++;

}

}

 

Hasil:

 

 

4.6.4 Pointer pada Array 1 dan 2 dimensi

 

Pada array, pointer hanya perlu menunjuk pada alamat elemen pertama saja karena letak alamat array sudah berurutan pada memori.

 

Contoh:

#include <stdio.h>

void main(){

int a[5] = {1,2,3,4,5};

int *p;

p=a;

printf(“%d”,*p);

}

Hasil : 1

 

Penjelasan:

- Pernyataan p=a artinya pointer p menyimpan alamat array a, yang alamatnya diwakili alamat elemen pertama, yaitu a[0]

- Kita juga dapat menuliskan baris p=a diganti dengan p=&a[0]

Contoh pembacaan semua elemen array 1 dimensi dengan pointer:

#include <stdio.h>

 

void main(){

int a[5] = {1,2,3,4,5};

int *p;

p=a;

for(int i=0;i<5;i++){

printf(“%d “,*p);

p++;

}

}

Hasil: 1 2 3 4 5

 

Pengisian array 1 dimensi:

#include <stdio.h>

 

void main(){

int a[5];

int *p;

int i;

p=a;

for(i=1;i<=5;i++){

*p=i;

p++;

}

for(i=0;i<5;i++) printf(“%d “,a[i]);

}

Hasil: 1 2 3 4 5

 

 

Pengaksesan array 2 dimensi:

#include <stdio.h>

 

void main(){

char a[3][5] = { “ABCDE”,”FGHIJ”,”KLMNO” };

char *p;

p=&a[0][0];

for(int i=1;i<=3;i++){

for(int j=1;j<=5;j++){

printf(“%c”,*p);

p++;

}

printf(“\n”);

}

}

Hasil:

A B C D E

F G H I J

K L M N O

 

4.7 Linked List

 

4.7.1 Apa itu Linked List ?

 

Dikembangkan tahun 1955-1956 oleh Allen Newell, Cliff Shaw dan Herbert Simon di RAND Corporation sebagai struktur data utama untuk bahasa Information Processing Language (IPL). IPL dibuat untuk mengembangkan program artificial intelligence, seperti pembuatan Chess Solver. Victor Yngve di Massachusetts Institute of Technology (MIT) juga menggunakan linked-List pada natural language processing dan machine transitions pada bahasa pemrograman COMMIT.

 

Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung menyambung, dinamis dan terbatas. Linked List sering disebut juga Senarai Berantai. Linked List saling terhubung dengan bantuan variabel pointer. Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.

 

Linked list merupakan struktur dinamis yang berlawanan dengan array, dimana merupakan struktur statis. Hal ini berarti linked list dapat tumbuh dan berkurang dalam ukuran yang bergantung pada kebutuhan user. Linked list digambarkan sebagai kumpulan dari nodes, Yang masing-masing berisi data dan link atau pointer ke node berikutnya di dalam list.

 

Karakteristik Array VS Linked List

ARRAY

LINKED LIST

Statis Dinamis
Penambahan / penghapusan data

Terbatas

Penambahan / penghapusan data

tidak terbatas

Random access Sequential access
Penghapusan array tidak mungkin Penghapusan linked list mudah

 

4.7.2 Single Linked List Non Circular

 

Pengertian:

Single : artinya field pointer-nya hanya satu buah saja dan satu arah.

Linked List : artinya node-node tersebut saling terhubung satu sama lain.

 

 

Ilustrasi Linked List

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Pada akhir linked list, node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.

 

PEMBUATAN SINGLE LINKED LIST

 

typedef struct TNode{

int data;

TNode *next;

};

 

Penjelasan:

- Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode

- Setelah pembuatan struct, buat variabel head yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.

 

SINGLE LINKED LIST MENGGUNAKAN HEAD

 

Dibutuhkan satu buah variabel pointer: head. Head akan selalu menunjuk pada node pertama

 

 

 

 

 

 

Deklarasi Pointer Penunjuk Kepala Single Linked List

Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer penunjuk ke node pertama dalam linked list (dalam hal ini adalah head). Deklarasinya sebagai berikut:

TNode *head;

 

PENAMBAHAN DATA

 

Penambahan node baru akan dikaitkan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan dengan cara head ditunjukkan ke node baru tersebut.

Pada prinsipnya adalah mengkaitkan node baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.

 

void insertDepan(int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = NULL;

 

if(isEmpty()==1){

head=baru;

head->next = NULL;

}

else {

baru->next = head;

head = baru;

}

cout<<”Data masuk\n”;

}

Ilustrasi:

  1. List masih kosong (head=NULL)

 

 

  1. Masuk data baru, misalnya 5

 

 

  1. Kemudian masuk lagi data baru, misalnya 20 (penambahan di depan)

 

 

Penambahan data dilakukan di belakang, namun pada saat pertama kali, node langsung ditunjuk oleh head. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui node terbelakang, kemudian setelah itu, dikaitkan dengan node baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.

 

void insertBelakang (int databaru){

TNode *baru,*bantu;

baru = new TNode;

baru->data = databaru;

baru->next = NULL;

 

if(isEmpty()==1){

head=baru;

head->next = NULL;

}

else {

bantu=head;

while(bantu->next!=NULL){

bantu=bantu->next;

}

bantu->next = baru;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=NULL)

 

 

  1. Masuk data baru, misalnya 5

 

 

  1. Kemudian masuk lagi data baru, misalnya 20 (penambahan di belakang)

 

 

  1. Datang data baru, misalnya 25 (penambahan di belakang)

 

 

 

 

 

 

 

MENAMPILKAN DATA

 

Function untuk menampilkan isi single linked list non circular

 

void tampil(){

TNode *bantu;

bantu = head;

 

if(isEmpty()==0){

while(bantu!=NULL){

cout<<bantu->data<<” “;

bantu=bantu->next;

}

cout<<endl;

} else cout<<”Masih kosong\n”;

}

 

 

Function di atas digunakan untuk menampilkan semua isi list, di mana linked list ditelusuri satu-persatu dari awal node sampai akhir node. Penelusuran ini dilakukan dengan menggunakan suatu pointer bantu, karena pada prinsipnya pointer head yang menjadi tanda awal list tidak boleh berubah/berganti posisi. Penelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke nilai NULL. Jika tidak NULL, maka node bantu akan berpindah ke node selanjutnya dan membaca isi datanya dengan menggunakan field next sehingga dapat saling berkait. Jika head masih NULL berarti data masih kosong!

 

 

 

MENGHAPUS DATA

 

Function untuk menghapus data terdepan

 

void hapusDepan (){

TNode *hapus;

int d;

 

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

d = hapus->data;

head = head->next;

delete hapus;

} else {

d = head->data;

head = NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

 

 

Function di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunakan suatu pointer lain yang digunakan untuk menunjuk node yang akan dihapus, misalnya pointer hapus dan barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete. Sebelum data terdepan dihapus, head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan menjadi head baru (data terdepan yang baru). Jika head masih NULL maka berarti data masih kosong!

 

Penghapusan data di belakang:

Membutuhkan pointer bantu dan hapus. Pointer hapus digunakan untuk menunjuk node yang akan dihapus, dan pointer bantu digunakan untuk menunjuk node sebelum node yang dihapus yang kemudian selanjutnya akan menjadi node terakhir. Pointer bantu akan digunakan untuk menunjuk ke nilai NULL. Pointer bantu akan selalu bergerak sampai sebelum node yang akan dihapus, baru kemudian pointer hapus diletakkan setelah pointer bantu. Setelah itu pointer hapus akan dihapus, pointer bantu akan menunjuk ke NULL.

 

void hapusBelakang(){

TNode *hapus,*bantu;

int d;

 

if (isEmpty()==0){

if(head->next != NULL){

bantu = head;

while(bantu->next->next!=NULL){

bantu = bantu->next;

}

hapus = bantu->next;

d = hapus->data;

bantu->next = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

 

4.7.3 Single Linked List Circular (SLLC)

 

SLLC adalah Single Linked List yang pointer next-nya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

 

Ilustrasi SLLC

 

 

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head.

 

PEMBUATAN SINGLE LINKED LIST CIRCULAR

 

typedef struct TNode{

int data;

TNode *next;

};

Penjelasan:

- Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode

- Setelah pembuatan struct, buat variabel haed yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.

 

SINGLE LINKED LIST CIRCULAR MENGGUNAKAN HEAD

 

- Dibutuhkan satu buah variabel pointer: head

- Head akan selalu menunjuk pada node pertama

 

Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus melalui node pertama dalam linked list. Deklarasinya sebagai berikut:

TNode *head;

 

Penambahan data di depan

Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya. Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu.

 

void insertDepan(int databaru){

TNode *baru,*bantu;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

if(isEmpty()==1){

head=baru;

head->next=head;

}

else {

bantu = head;

while(bantu->next!=head){

bantu=bantu->next;

}

baru->next = head;

head = baru;

bantu->next = head;

}

cout<<”Data masuk\n”;

}

Ilustrasi:

  1. List masih kosong (head=NULL)

 

 

  1. Masuk data baru, misalnya 5

 

 

  1. Datang data baru, misalnya 20 (penambahan di depan)

 

 

Penambahan data di belakang

Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.

 

void insertBelakang (int databaru){

TNode *baru,*bantu;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

if(isEmpty()==1){

head=baru;

head->next=head;

}

else {

bantu = head;

while(bantu->next != head){

bantu=bantu->next;

}

bantu->next = baru;

baru->next = head;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=NULL)

 

 

  1. Masuk data baru, misalnya 5

 

 

  1. Datang data baru, misalnya 20 (penambahan di belakang)

 

 

  1. Datang data baru, misal 25 (penambahan di belakang)

 

 

Function untuk menampilkan isi single linked list

 

void tampil(){

TNode *b;

b = head;

if(isEmpty()==0){

do{

cout<<b->data<<” “;

b=b->next;

}while(b!=head);

cout<<endl;

} else cout<<”Masih kosong\n”;

}

 

Function di atas digunakan untuk menampilkan semua isi list, di mana linked list ditelusuri satu-persatu dari awal node sampai akhir node. Penelusuran ini dilakukan dengan menggunakan suatu variabel node bantu, karena pada prinsipnya variabel node head yang menjadi tanda awal list tidak boleh berubah/berganti posisi. Penelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke head lagi. Jika belum sama dengan head, maka node bantu akan berpindah ke node selanjutnya dan membaca isi datanya dengan menggunakan field next sehingga dapat saling berkait. Jika head masih NULL berarti data masih kosong!

 

Function untuk menghapus data terdepan

 

void hapusDepan (){

TNode *hapus,*bantu;

if (isEmpty()==0){

int d;

hapus = head;

d = head->data;

if(head->next != head){

bantu = head;

while(bantu->next!=head){

bantu=bantu->next;

}

head = head->next;

delete hapus;

bantu->next = head;

}else{

head=NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

 

Function di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus ditampung dahulu pada variabel hapus dan barulah kemudian menghapus variabel hapus dengan menggunakan perintah delete. Sebelum data terdepan dihapus, head harus ditunjukkan ke data sesudahnya terlebih dahulu sehingga data setelah head lama akan menjadi head baru (data terdepan yang baru). Jika head masih NULL maka berarti data masih kosong!

 

Penghapusan data di belakang:

void hapusBelakang(){

TNode *hapus,*bantu;

if (isEmpty()==0){

int d;

hapus = head;

if(head->next == head){

head = NULL;

}else{

bantu = head;

while(bantu->next->next != head){

bantu = bantu->next;

}

hapus = bantu->next;

d = bantu->data;

bantu->next = head;

delete hapus;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

 

 

 

 

 

 

 

 

 

 

Ilustrasi:

 

 

SINGLE LINKED LIST MENGGUNAKAN HEAD DAN TAIL

 

- Dibutuhkan dua buah variabel pointer: head dan tail

- Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu

menunjuk pada node terakhir.

 

 

 

 

 

PENAMBAHAN DATA

 

Penambahan data baru di depan akan selalu menjadi head.

 

void insertDepan(int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

if(isEmpty()==1){

head=baru;

tail=baru;

head->next=head;

tail->next=tail;

}

else {

baru->next = head;

head = baru;

tail->next = head;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=tail=NULL).

 

 

 

 

  1. Masuk data baru, missal 5

 

 

  1. Datang data baru, missal 20

 

 

Penambahan Data di belakang

Pada penambahan data di belakang, data akan selalu dikaitkan dengan tail, karena tail terletak di node paling belakang. Setelah dikaitkan dengan node baru, maka node baru tersebut akan menjadi tail.

Kelebihan dari Single Linked List dengan Head & Tail adalah pada penambahan data di belakang, hanya dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu.

 

void tambahBelakang(int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

if(isEmpty()==1){

head=baru;

tail=baru;

head->next=head;

tail->next=tail;

}

else {

tail->next = baru;

tail = baru;

tail->next = head;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=tail=NULL).

 

 

  1. Masuk data baru, missal 5

 

 

 

 

 

 

 

 

 

 

  1. Datang data baru, missal 20

 

 

Function untuk menampilkan isi linked list:

 

void tampil(){

TNode *b;

b = head;

if(isEmpty()==0){

do{

cout<<b->data<<” “;

b=b->next;

}while(b!=tail->next);

cout<<endl;

} else cout<<”Masih kosong\n”;

}

 

Function untuk menghapus data di depan

void hapusDepan(){

TNode *hapus;

if (isEmpty()==0){

int d;

hapus = head;

d = head->data;

if(head != tail){

hapus = head;

head = head->next;

tail->next = head;

delete hapus;

} else{

head=NULL;

tail=NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

Function di atas akan menghapus data terdepan (pertama) yang ditunjuk oleh head pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variabel hapus pada head, kemudian dilakukan pergeseran head ke node berikutnya sehingga data setelah head menjadi head baru, kemudian menghapus variabel hapus dengan menggunakan perintah delete. Jika tail masih NULL maka berarti data masih kosong!

 

Function untuk menghapus data di belakang:

 

void hapusBelakang(){

TNode *hapus,*bantu;

if (isEmpty()==0){

int d;

if(head == tail){

d = tail->data;

head = NULL;

tail = NULL;

} else{

bantu = head;

while(bantu->next != tail){

bantu = bantu->next;

}

hapus = tail;

tail = bantu;

d = hapus->data;

tail->next = head;

delete hapus;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

Ilustrasi:

 

Function di atas akan menghapus data terbelakang (terakhir) yang ditunjuk oleh tail pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variabel hapus pada tail, kemudian dibutuhkan pointer bantu untuk membantu pergeseran dari head ke node berikutnya sampai sebelum tail, sehingga tail dapat ditunjukkan ke bantu tersebut, dan bantu tersebut akan menjadi tail yang baru. Setelah itu hapus variabel hapus dengan menggunakan perintah delete. Jika tail masih NULL maka berarti data masih kosong!

 

Function untuk menghapus semua elemen LinkedList:

 

void clear(){

TNode *bantu,*hapus;

if(isEmpty() == 0){

bantu = head;

while(bantu->next!=head){

hapus = bantu;

bantu = bantu->next;

delete hapus;

}

head = NULL;

tail = NULL;

}

}

 

Menggunakan pointer bantu yang digunakan untuk bergerak sepanjang list, dan menggunakan pointer hapus yang digunakan untuk menunjuk node-node yang akan dihapus. Pada saat pointer hapus menunjuk pada node yang akan dihapus, pointer bantu akan bergerak ke node selanjutnya, dan kemudian pointer hapus akan di delete.

 

 

4.7.4 Double Linked List Non Circular (DLLNC)

 

Double Linked List Non Circular adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut.

Double Linked List Non Circular pointer next dan prev nya menunjuk ke NULL.

Dengan adanya 2 pointer penunjuk, next dan prev, DLLNC sangat flexible dibandingkan dengan SLLNC.

 

Bentuk Node DLLNC

 

 

 

Ilustrasi Double Linked List Non Circular

 

 

 

PEMBUATAN DOUBLE LINKED LIST NON CIRCULAR

 

typedef struct TNode{

int data;

TNode *next;

Tnode *prev;

};

 

Penjelasan:

Pembuatan struct bernama TNode yang berisi 3 field, yaitu field data bertipe integer dan field next & prev yang bertipe pointer dari TNode. Setelah pembuatan struct, buat variabel head yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.

 

DOUBLE LINKED LIST NON CIRCULAR MENGGUNAKAN HEAD

 

Function untuk mengetahui kosong tidaknya LinkedList

 

int isEmpty(){

if(head == NULL) return 1;

else return 0;

}

 

 

 

Penambahan data di depan

 

Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya. Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.

 

void insertDepan(int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = NULL;

baru->prev = NULL;

if(isEmpty()==1){

head=baru;

head->next = NULL;

head->prev = NULL;

}

else {

baru->next = head;

head->prev = baru;

head = baru;

}

cout<<”Data masuk\n”;

}

Ilustrasi:

  1. List masih kosong (head=NULL).

 

 

  1. Masuk data baru, missal 5

 

 

  1. Datang data baru, missal 20

 

Penambahan data di belakang

 

Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.

 

void insertBelakang (int databaru){

TNode *baru,*bantu;

baru = new TNode;

baru->data = databaru;

baru->next = NULL;

baru->prev = NULL;

if(isEmpty()==1){

head=baru;

head->next = NULL;

head->

}

else {

bantu=head;

while(bantu->next!=NULL){

bantu=bantu->next;

}

bantu->next = baru;

baru->prev = bantu;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=NULL)

 

 

  1. Masuk data baru, misal 5

 

 

  1. Datang data baru, misal 20 (penambahan di belakang)

 

 

 

 

  1. Datang data baru, misal 25 (penambahan di belakang)

 

 

Function untuk menghapus data di depan:

 

void hapusDepan (){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

d = hapus->data;

head = head->next;

head->prev = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

Function di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus ditampung dahulu pada pointer hapus dan barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete. Namun sebelumnya pointer head harus menunjuk terlebih dahulu ke node selanjutnya. Jika head masih NULL maka berarti data masih kosong!

 

Function untuk menghapus node terbelakang

 

void hapusBelakang(){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

while(hapus->next!=NULL){

hapus = hapus->next;

}

d = hapus->data;

hapus->prev->next = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

Tidak diperlukan pointer bantu yang mengikuti pointer hapus yang berguna untuk menunjuk ke NULL. Karena pointer hapus sudah bisa menunjuk ke pointer sebelumnya dengan menggunakan elemen prev ke node sebelumnya, yang akan diset agar menunjuk ke NULL setelah penghapusan dilakukan.

Function untuk menghapus semua elemen

void clear(){

TNode *bantu,*hapus;

bantu = head;

while(bantu!=NULL){

hapus = bantu;

bantu = bantu->next;

delete hapus;

}

head = NULL;

}

 

DOUBLE LINKED LIST NON CIRCULAR MENGGUNAKAN HEAD dan TAIL

 

Dibutuhkan dua buah variabel pointer: head dan tail. Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.

 

 

 

Pengkaitan node baru ke linked list di depan

 

Penambahan node baru akan selalu dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada tail/head nya. Sedangkan jika tidak kosong, data akan ditambahkan didepan head, kemudian node baru akan berubah menjadi head.

 

 

 

void insertDepan (int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = NULL;

baru->prev = NULL;

if(isEmpty()==1){

head=baru;

tail=head;

head->next = NULL;

head->prev = NULL;

tail->prev = NULL;

tail->next = NULL;

}

else {

baru->next = head;

head->prev = baru;

head = baru;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=tail=NULL)

 

 

  1. Datang data baru, missal 5

 

  1. Datang data baru, missal 20 (di depan)

 

 

Penambahan node di belakang

Penambahan node di belakang akan selalu dikaitkan dengan tail dan kemudian

node baru tersebut akan menjadi tail

 

void insertBelakang(int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = NULL;

baru->prev = NULL;

if(isEmpty()==1){

head=baru;

tail=head;

head->next = NULL;

head->prev = NULL;

tail->prev = NULL;

tail->next = NULL;

}

else {

tail->next = baru;

baru->prev = tail;

tail = baru;

tail->next = NULL;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=NULL)

 

 

  1. Masuk data baru, misal 5

 

 

  1. Datang data baru, misal 20 (penambahan di belakang)

 

 

 

 

  1. Datang data baru, misal 25 (penambahan di belakang)

 

 

Function untuk menampilkan isi linked list

void tampil(){

TNode *bantu;

bantu = head;

if(isEmpty()==0){

while(bantu!=tail->next){

cout<<bantu->data<<” “;

bantu=bantu->next;

}

cout<<endl;

} else cout<<”Masih kosong\n”;

}

 

Function untuk menghapus data di data terdepan

 

void hapusDepan(){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

d = hapus->data;

head = head->next;

head->prev = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

tail = NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

Function di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus ditampung dahulu pada pointer hapus dan barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete. Namun sebelumnya pointer head harus ditunjuk lebih dahulu ke node sesudahnya agar tetap menunjuk ke node terdepan. Jika tail masih NULL maka berarti data masih kosong!

 

Function untuk menghapus node terbelakang

 

void hapusBelakang(){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = tail;

d = tail->data;

tail = tail->prev;

tail->next = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

tail = NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

Pointer hapus tidak perlu di loop untuk mencari node terakhir. Pointer hapus hanya perlu menunjuk pada pointer tail saja. Karena pointer hapus sudah bisa menunjuk ke pointer sebelumnya dengan menggunakan elemen prev, maka pointer prev hanya perlu diset agar menunjuk ke NULL. Lalu pointer hapus di delete.

 

4.7.5 Double Linked List Circular (DLLC)

 

Double Linked List Circular adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut.

Double Linked List Circular pointer next dan prev nya menunjuk ke dirinya sendiri secara circular.

 

Bentuk Node DLLC

 

Ilustrasi Double Linked List Circular

 

 

 

Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya. Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk ke dirinya sendiri. Jika sudah lebih dari satu node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node sesudahnya.

 

DOUBLE LINKED LIST CIRCULAR MENGGUNAKAN HEAD

 

Penambahan data di depan

 

Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya. Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Dibutuhkan pointer bantu yang digunakan untuk menunjuk node terakhir (head->prev) yang akan digunakan untuk mengikat list dengan node terdepan.

 

void insertDepan(int databaru){

TNode *baru, *bantu;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

baru->prev = baru;

if(isEmpty()==1){

head=baru;

head->next = head;

head->prev = head;

}

else {

bantu = head->prev;

baru->next = head;

head->prev = baru;

head = baru;

head->prev = bantu;

bantu->next = head;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=NULL)

 

 

  1. Masuk data baru, misal 5

 

 

 

 

 

 

  1. Datang data baru, misal 20

 

 

  1. Datang data baru, misal 30

 

 

Penambahan data di belakang

 

Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, namun tidak diperlukan loop karena untuk mengetahui node terbelakang hanya perlu menunjuk pada head->prev saja. Kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.

 

void insertBelakang (int databaru){

TNode *baru,*bantu;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

baru->prev = baru;

if(isEmpty()==1){

head=baru;

head->next = head;

head->prev = head;

}

else {

bantu=head->prev;

bantu->next = baru;

baru->prev = bantu;

baru->next = head;

head->prev = baru;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=NULL)

 

 

 

  1. Masuk data baru, missal 5

 

 

  1. Datang data baru, missal 20 (penambahan di belakang)

 

 

  1. Datang data baru, missal 25 (penambahan di belakang)

 

 

 

Function untuk menampilkan isi linked list

 

void tampil(){

TNode *bantu;

bantu = head;

if(isEmpty()==0){

do{

cout<<bantu->data<<” “;

bantu=bantu->next;

}while(bantu!=head);

cout<<endl;

} else cout<<”Masih kosong\n”;

}

 

Function di atas digunakan untuk menampilkan semua isi list, di mana linked list ditelusuri satu-persatu dari awal node sampai akhir node. Penelusuran ini dilakukan dengan menggunakan suatu variabel node bantu, karena pada prinsipnya variabel node head yang menjadi tanda awal list tidak boleh berubah/berganti posisi. Penelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke head lagi. Jika belum sama dengan head, maka node bantu akan berpindah ke node selanjutnya dan membaca isi datanya dengan menggunakan field next sehingga dapat saling berkait. Jika head masih NULL berarti data masih kosong!

 

Function untuk menghapus data di depan:

 

void hapusDepan (){

TNode *hapus,*bantu;

int d;

if (isEmpty()==0){

if(head->next != head){

hapus = head;

d = hapus->data;

bantu = head->prev;

head = head->next;

bantu->next = head;

head->prev = bantu;

delete hapus;

} else {

d = head->data;

head = NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

Function di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus ditampung dahulu pada pointer hapus dan barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete. Jika head masih NULL maka berarti data masih kosong!

 

Function untuk menghapus node terbelakang

 

void hapusBelakang(){

TNode *hapus,*bantu;

int d;

if (isEmpty()==0){

if(head->next != head){

bantu = head;

while(bantu->next->next != head){

bantu = bantu->next;

}

hapus = bantu->next;

d = hapus->data;

bantu->next = head;

delete hapus;

} else {

d = head->data;

head = NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

DOUBLE LINKED LIST MENGGUNAKAN HEAD dan TAIL

 

Pengkaitan node baru ke linked list di depan

 

Penambahan node baru akan selalu dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada tail/head nya. Sedangkan jika tidak kosong, data akan ditambahkan didepan head, kemudian node baru akan berubah menjadi head.

 

void insertDepan (int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

baru->prev = baru;

if(isEmpty()==1){

head=baru;

tail=baru;

head->next = head;

head->prev = head;

tail->next = tail;

tail->prev = tail;

}

else {

baru->next = head;

head->prev = baru;

head = baru;

head->prev = tail;

tail->next = head;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=tail=NULL)

 

 

  1. Masuk data baru, missal 5

 

 

 

 

 

 

 

 

  1. Datang data baru, missal 20 (di depan)

 

 

Penambahan node di belakang

 

void insertBelakang(int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

baru->prev = baru;

if(isEmpty()==1){

head=baru;

tail=baru;

head->next = head;

head->prev = head;

tail->next = tail;

tail->prev = tail;

}

else {

tail->next = baru;

baru->prev = tail;

tail = baru;

tail->next = head;

head->prev = tail;

}

cout<<”Data masuk\n”;

}

 

Ilustrasi:

  1. List masih kosong (head=NULL)

 

  1. Masuk data baru, missal 5

 

  1. Datang data baru, misal 20 (penambahan di belakang)

 

  1. Datang data baru, misal 25 (penambahan di belakang)

 

 

Function untuk menghapus data di data terdepan

 

void hapusDepan(){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head != tail){

hapus = head;

d = hapus->data;

head = head->next;

tail->next = head;

head->prev = tail;

delete hapus;

} else {

d = head->data;

head = NULL;

tail = NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

 

Function di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus ditampung dahulu pada variabel hapus dan barulah kemudian menghapus variabel hapus dengan menggunakan perintah delete. Jika tail masih NULL maka berarti data masih kosong!

 

Function untuk menghapus node terbelakang

 

void hapusBelakang(){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head != tail){

hapus = tail;

d = hapus->data;

tail = tail->prev;

tail->next = head;

head->prev = tail;

delete hapus;

} else {

d = head->data;

head = NULL;

tail = NULL;

}

cout<<d<<” terhapus\n”;

} else cout<<”Masih kosong\n”;

}

Pointer hapus tidak perlu di loop untuk mencari node terakhir. Pointer hapus hanya perlu menunjuk pada pointer tail saja. Karena pointer hapus sudah bisa menunjuk ke pointer sebelumnya dengan menggunakan elemen prev ke node sebelumnya. Kemudian pointer tail akan berpindah ke node sebelumnya.

 

Function untuk menghapus semua elemen LinkedList

 

void clear(){

TNode *bantu,*hapus;

if (isEmpty()==0){

bantu = head;

while(bantu->next!=head){

hapus = bantu;

bantu = bantu->next;

delete hapus;

}

head = NULL;

}

}

 

4.8 List dalam Stack dan Queue

 

4.8.1 Pengertian Stack

 

Stack atau tumpukan adalah suatu stuktur data yang penting dalam pemrograman. Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack. Contohnya, karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo juga. Bersifat LIFO (Last In First Out)

4.8.2 Operasi fungsi Stack

 

Operasi-operasi/fungsi Stack:

- Push : digunakan untuk menambah item pada stack pada tumpukan paling atas

- Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas

- Clear : digunakan untuk mengosongkan stack

- IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong

- IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

 

Fungsi IsFull

- Untuk memeriksa apakah stack sudah penuh?

- Dengan cara memeriksa top of stack, jika sudah sama dengan MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full

int IsFull(){

if(tumpuk.top == MAX_STACK-1)

return 1;

else

return 0;

}

 

Fungsi IsEmpty

-  Untuk memeriksa apakah stack masih kosong?

- Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong!

int IsEmpty(){

if(tumpuk.top == -1)

return 1;

else

return 0;

}

 

Fungsi Push

-    Untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack

-    Tambah satu (increment) nilai top of stack terlebih dahulu setiap kali ada penambahan elemen stack, asalkan stack masih belum penuh, kemudian isikan nilai baru ke stack berdasarkan indeks top of stack setelah ditambah satu (di increment)

 

void Push(char d[10]){

tumpuk.top++;

strcpy(tumpuk.data[tumpuk.top],d);

}

 

Fungsi Pop

-    Untuk mengambil elemen teratas dari stack.

-    Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan diambil terlebih dahulu, baru di decrement nilai top of stack sehingga jumlah elemen stack berkurang

 

void Pop(){

printf(“Data yang terambil =

%s\n”,tumpuk.data[tumpuk.top]);

tumpuk.top–;

}

 

Fungsi Print

-    Untuk menampilkan semua elemen-elemen stack

-    Dengan cara looping semua nilai array secara terbalik, karena kita harus mengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil!

 

void TampilStack(){

for(int i=tumpuk.top;i>=0;i–){

printf(“Data : %s\n”,tumpuk.data[i]);

}

}

 

4.8.3 Queue dengan Menggunakan Array

 

Queue sama dengan antrian. Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya.

 

Dequeue adalah mengeluarkan satu elemen dari suatu Antrian. Antrian dapat dibuat dengan menggunakan: Liniear Array dan Circular Array

 

QUEUE DENGAN LINIEAR ARRAY

 

-    Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya

-    Sehingga membutuhkan variabel Head dan Tail

 

Deklarasi Queue

 

#define MAX 8

typedef struct{

int data[MAX];

int head;

int tail;

} Queue;

Queue antrian;

 

OPERASI-OPERASI PADA QUEUE

 

- Create()

o Untuk menciptakan dan menginisialisasi Queue

o Dengan cara membuat Head dan Tail = -1

void Create(){

antrian.head=antrian.tail=-1;

}

 

- IsEmpty()

o Untuk memeriksa apakah Antrian sudah penuh atau belum

o Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty

o Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubahubah

o Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail.

int IsEmpty(){

if(antrian.tail==-1)

return 1;

else

return 0;

}

 

- IsFull()

o Untuk mengecek apakah Antrian sudah penuh atau belum

o Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh

int IsFull(){

if(antrian.tail==MAX-1) return 1;

else return 0;

}

 

- Enqueue(data)

o Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang

o Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail

void Enqueue(int data){

if(IsEmpty()==1){

antrian.head=antrian.tail=0;

antrian.data[antrian.tail]=data;

printf(“%d masuk!”,antrian.data[antrian.tail]);

} else

if(IsFull()==0){

antrian.tail++;

antrian.data[antrian.tail]=data;

printf(“%d masuk!”,antrian.data[antrian.tail]);

}

}

 

- Dequeue()

o Digunakan untuk menghapus elemen terdepan/pertama dari Antrian

o Dengan cara mengurangi counter Tail dan menggeser semua elemen antrian kedepan.

o Penggeseran dilakukan dengan menggunakan looping

int Dequeue(){

int i;

int e = antrian.data[antrian.head];

for(i=antrian.head;i<=antrian.tail-1;i++){

antrian.data[i] = antrian.data[i+1];

}

antrian.tail–;

return e;

}

- Clear()

o Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1

o Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus   arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca

void Clear(){

antrian.head=antrian.tail=-1;

printf(“data clear”);

}

 

- Tampil()

o Untuk menampilkan nilai-nilai elemen Antrian

o Menggunakan looping dari head s/d tail

void Tampil(){

if(IsEmpty()==0){

for(int i=antrian.head;i<=antrian.tail;i++){

printf(“%d “,antrian.data[i]);

}

}else printf(“data kosong!\n”);

}

4.9 List dalam Tree

 

4.9.1 Pengertian Tree

 

  • Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon.
  • Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah.
  • Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.

 

Gambar Tree

 

Ancestor (F) = C,A

Descendant (C) = F,G

Parent (D) = B

Child (A) = B,C

Sibling (F) = G

Size = 7

Height = 3

Root = A

Leaf = D,E,F,G

Degree (C) = 2

 

 

 

 

4.9.2 Implementasi Program Tree

 

  • Tree dapat dibuat dengan menggunakan linked list secara rekursif.
  • Linked list yang digunakan adalah double linked list.
  • Data yang pertama kali masuk akan menjadi node root.
  • Data yang lebih kecil dari data node root akan masuk dan menempati node kiri dari node root, sedangkan jika lebih besar dari data node root, akan masuk dan menempati node di sebelah kanan node root.

 

Misal terdapat Tree sebagai berikut:

 

Ilustrasi Kunjungan

  1. Kunjungan PreOrder (notasi prefiks)

Hasil kunjungan: “ABDGCEHIF”

void preOrder(Tree *root){

if(root != NULL){

printf(“%d “,root->data);

preOrder(root->left);

preOrder(root->right);

}

}

  1. Kunjungan InOrder (notasi infiks)

Hasil kunjungan: “DGBAHEICF”

void inOrder(Tree *root){

if(root != NULL){

inOrder(root->left);

printf(“%d “,root->data);

inOrder(root->right);

}

}

  1. Kunjungan PostOrder (notasi postfiks)

Hasil kunjungan: “GDBAHIEFCA”

void postOrder(Tree *root){

if(root != NULL){

postOrder(root->left);

postOrder(root->right);

printf(“%d “,root->data);

}

}

  1. Kunjungan LevelOrder

Hasil kunjungan: “ABCDEFGHI”

Algoritma:

o Inisialisasi: masukkan root ke dalam Antrian

o Iterasi: selama Antrian tidak kosong, lakukan:

_ Keluarkan antrian node terdepan, dan kunjungi node tersebut

_ Masukkan node->right dan node->left ke dalam antrian asal

node tersebut tidak NULL.

 

Pencarian Data di Tree

 

Tree *cari(Tree *root,int data){

if(root==NULL) return NULL;

else if(data<root->data)return(cari(root->left,data));

else if(data>root->data)return(cari(root->right,data));

else if(data == root->data) return root;

}

Pencarian dilakukan secara rekursif, dimulai dari node root, jika data yang dicari lebih kecil daripada data node root, maka pencarian dilakukan di sub node sebelah kiri, sedangkan jika data yang dicari lebih besar daripada data node root, maka pencarian dilakukan di sub node sebelah kanan, jika data yang dicari sama dengan data suatu node berarti kembalikan node tersebut dan berarti data ditemukan.

 

Ilustrasi:

Misal dicari data 8

 

1. Root = 6 dan 8 > 6, maka akan dicari di sub node bagian kanan root.

2. Root = 10 dan 8 < 10, maka akan dicari di sub node bagian kiri root.

3. Root = 7 dan 8 > 7, maka akan dicari di sub node bagian kanan root.

4. Root = 8, berarti 8 = 8, maka akan dikembalikan node tersebut dan

dianggap ketemu!

 

4.10 Hash Table

 

  • Suatu struktur data yang efektif untuk mengimplementasikan dictionary.
  • Dibanding linier search: secara teori worst case tetap O(n) secara praktis biasanya dapat dicapai O(1).
  • Seperti array, indeksnya diganti dengan key (jika key=indeks maka itu adalah direct access table).
  • Nilai indeks didapat dengan menggunakan fungsi hash terhadap key.
  • Key diubah menjasi index dengan suatu fungsi hash.
  • Dua key yang berbeda dapat memiliki nilai hash yang sama (terjasi collision).
  • Fungsi hash yang baik akan meminimalkan terjadinya kolisi.
  • Resolusi kolisi dapat dilakukan dengan chaining.
  • Fungsi hash yang baik: setiap key memiliki kemungkinan yang sama untuk di hash ke salah satu dari slot m tanpa tergantung pada key lain.
  • Metode pembagian: h(k) = k mod m
  • Metode perkalian: h(k) = floor(m*(frac(kA)))
  • Universal hashing

- memilih fungsi hash yang random

- untuk security

 

PERFECT HASHING

  • Digunakan jika semua himpunan key diketahui
  • Worst casenya O(1)
  • Menggunakan gabungan antara chaining dengan universal hashing

- Hash pertama memetakan ke fungsi Hj

- Dengan memilih fungsi yang tepat untuk setiap Hj maka tidak akan terjadi kolisi

 

4.11 Mengoperasikan File

 

-      File digunakan sebagai penyimpanan data eksternal selain memori komputer.

-      Tempat penyimpanan eksternal ini bersifat permanen (non-volatile) dan biasanya berukuran besar dengan tujuan untuk dibaca kembali datadatanya.

-      Operasi-operasi terhadap file pasti berkaitan dengan Input (menulis) dan Output (menampilkan) serta berbagai hal lain seperti mengecek keberadaan file, ukuran file, dan lain-lain.

-      Operasi untuk mengolah file membutuhkan buffer untuk menampung informasi yang berkenaan dengan file tersebut.

 

4.11.1 Membuka File

 

Suatu file dalam disk harus dalam keadaan terbuka terlebih dahulu baru dapat diakses.

 

FILE *fopen(const char *filename, const char *mode)

 

Kembalian dari fungsi fopen adalah nilai pointer file atau NULL jika pembukaan file gagal.

filename adalah nama file.

 

Dengan parameter mode adalah:

r – open for reading

w – open for writing (file need not exist)

a – open for appending (file need not exist)

r+ – open for reading and writing, start at beginning

w+ – open for reading and writing (overwrite file)

a+ – open for reading and writing (append if file exists)

 

- File dapat dibuka sebagai file teks (t) atau file biner (b)

- File teks menggunakan parameter tambahan menjadi rt, wt, at,

r+t, w+t, dan a+t

- File biner menggunakan parameter tambahan menjadi rb, wb, ab,

r+b, w+b, dan a+b

- Defaultnya adalah mode teks (t)

 

Contoh penggunaan:

FILE *fp;

fp=fopen(“c:\\test.txt”, “r”);

if (fp==NULL) printf(“Error, file tidak dapat dibuka!”);

 

Sebelum file digunakan/diproses harus dibuka terlebih dahulu. Kita perlu mendefinisikan obyek file. Salah satu bentuk pernyataannya adalah sebagai berikut:

ofstream nama_variabel_file;

nama_variabel_file_output.open(“nama_file.txt”);

 

4.11.2 Menulis ke File

 

Untuk menulis ke file kita perlu menggunakan nama_variabel file dan tanda “<<” seperti berikut ini:

nama_variabel_file_output << “Hallo “<<endl;

nama_variabel_file_output <<”Baris kedua “<<endl;

 

4.11.3 Penambahan Data pada File

 

Gunakan fungsi :

ofstream nama_variabel_file_output(“nama_file.txt”,ios::app);

Sehingga data dapat ditambahkan pada baris bawah dari akhir file.

 

Perhatikan contoh berikut ini:

#include <iostream.h>

#include <fstream.h>

 

void main(){

ofstream f;

f.open(“c:\\coba.txt”,ios::app);

cout<<”Penulisan dimulai…”<<endl;

f<<”hallo2″<<endl;

f<<”anton2″<<endl;

cout<<”Penulisan selesai.”<<endl;

f.close();

}

Akan menghasilkan file coba.txt dengan isi sebagai berikut:

hallo

anton

hallo2

anton2

 

4.11.4 Menutup File

 

int fclose(FILE *a_file);

int fcloseall(void);

 

Nilai kembalian int akan berisi 0 jika berhasil atau -1 (EOF) jika gagal! fcloseall akan menutup seluruh stream yang aktif kecuali stdin, stdout, stdprn dan stdaux. Pada Windows, kembalian dari nilai ini tidak terlalu diperlukan karena di Windows tidak diperlukan untuk mengetahui status suatu program.

 

Contoh penggunaan:

FILE *fp;

fp=fopen(“c:\\test.txt”, “r”);

if (fp==NULL) printf(“Error, file tidak dapat dibuka!”);

fclose(fp);

Contoh program lengkap:

#include <iostream.h>

#include <fstream.h>

 

void main(){

ofstream f;

f.open(“c:\\coba.txt”);

cout<<”Penulisan dimulai…”<<endl;

f<<”hallo”<<endl;

f<<”anton”<<endl;

cout<<”Penulisan selesai.”<<endl;

f.close();

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

BAB V

SUMBER-SUMBER YANG DIPERLUKAN

UNTUK PENCAPAIAN KOMPETENSI

 

5.1.      Sumber Daya Manusia

 

Pelatih

Pelatih Anda dipilih karena dia telah berpengalaman. Peran Pelatih adalah untuk :

  1. Membantu Anda untuk merencanakan proses belajar.
    1. Membimbing Anda melalui tugas-tugas pelatihan yang dijelaskan dalam tahap belajar.
    2. Membantu Anda untuk memahami konsep dan praktik baru dan untuk menjawab pertanyaan Anda mengenai proses belajar Anda.
    3. Membantu Anda untuk menentukan dan mengakses sumber tambahan lain yang Anda perlukan untuk belajar Anda.
    4. Mengorganisir kegiatan belajar kelompok jika diperlukan.
      1. Merencanakan seorang ahli dari tempat kerja untuk membantu jika diperlukan.

 

Penilai

Penilai Anda melaksanakan program pelatihan terstruktur untuk penilaian di tempat kerja. Penilai akan :

  1. Melaksanakan penilaian apabila Anda telah siap dan merencanakan proses belajar dan penilaian selanjutnya dengan Anda.
  2. Menjelaskan kepada Anda mengenai bagian yang perlu untuk diperbaiki dan merundingkan rencana pelatihan selanjutnya dengan Anda.
  3. Mencatat pencapaian / perolehan Anda.

 

Teman kerja/sesama peserta pelatihan

Teman kerja Anda/sesama peserta pelatihan juga merupakan sumber dukungan dan bantuan. Anda juga dapat mendiskusikan proses belajar dengan mereka. Pendekatan ini akan menjadi suatu yang berharga dalam membangun semangat tim dalam lingkungan belajar/kerja Anda dan dapat meningkatkan pengalaman belajar Anda.

 

5.2.          Sumber-sumber Perpustakaan

           

Pengertian sumber-sumber adalah material yang menjadi pendukung proses pembelajaran ketika peserta pelatihan sedang menggunakan Pedoman Belajar ini.

 

Sumber-sumber tersebut dapat meliputi :

  1. Buku referensi dari perusahan
  2. Lembar kerja
  3. Gambar
  4. Contoh tugas kerja
  5. Rekaman dalam bentuk kaset, video, film dan lain-lain.

 

Ada beberapa sumber yang disebutkan dalam pedoman belajar ini untuk membantu peserta pelatihan mencapai unjuk kerja yang tercakup pada suatu unit kompetensi.

 

Prinsip-prinsip dalam CBT mendorong kefleksibilitasan dari penggunaan sumber-sumber yang terbaik dalam suatu unit kompetensi tertentu, dengan mengijinkan peserta untuk menggunakan sumber-sumber alternative lain yang lebih baik atau jika ternyata sumber-sumber yang direkomendasikan dalam pedoman belajar ini tidak tersedia/tidak ada.

 

 

 

 

 

 

 

 

5.3.          Daftar Peralatan dan Bahan yang digunakan

 

  1. Judul/Nama Pelatihan             :        Membuat Struktur Data
  2. Kode Program Pelatihan         :        TIK.PR02.003.01

NO

UNIT KOMPETENSI

KODE UNIT

DAFTAR PERALATAN

DAFTAR BAHAN

KETERANGAN

1 Menerapkan konsep data dan struktur data TIK.PR02.003.01
  • Seperangkat Komputer untuk latihan

 

  • Software aplikasi untuk menginstal bahasa pemrograman C atau C++
  • Manual Pemrograman Borland C
 

  • Internet

 

 

-

2 Menerapkan array dan record TIK.PR02.003.01
  • Seperangkat Komputer untuk latihan

 

  • Software aplikasi untuk menginstal bahasa pemrograman C atau C++
  • Manual Pemrograman Borland C
 

  • Internet

 

 

-

3 Menerapkan pointer TIK.PR02.003.01
  • Seperangkat Komputer untuk latihan

 

  • Software aplikasi untuk menginstal bahasa pemrograman C atau C++
  • Manual Pemrograman Borland C
 

  • Internet

 

 

-

4 Menerapkan list berkait TIK.PR02.003.01
  • Seperangkat Komputer untuk latihan

 

  • Software aplikasi untuk menginstal bahasa pemrograman C atau C++
  • Manual Pemrograman Borland C
 

  • Internet

 

 

-

5 Menerapkan list berkait TIK.PR02.003.01
  • Seperangkat Komputer untuk latihan

 

  • Software aplikasi untuk menginstal bahasa pemrograman C atau C++
  • Manual Pemrograman Borland C
 

  • Internet

 

 

-

6 Mengoperasikan file secara list berkait TIK.PR02.003.01
  • Seperangkat Komputer untuk latihan

 

  • Software aplikasi untuk menginstal bahasa pemrograman C atau C++
  • Manual Pemrograman Borland C
 

  • Internet

 

 

-

 

DAFTAR PUSTAKA

 

 

Testimoni

Filed under : blog, tags: