fathonim bahan ajar if2018 prak.struktur data

BAHAN AJAR

Praktek Struktur Data

PENGAJAR SEMESTER

: FATHONI MAHARDIKA : II (Genap)

TEKNIK INFORMATIKASEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER

STMIK SUMEDANG2011

Disusun oleh: Fathoni Mahardika

LEMBAR PENGESAHAN JUDUL : BAHAN AJAR TOPIK BAHAN AJAR : Praktikum Struktur Data

NAMA NIP/NIK

: FATHONI MAHARDIKA, S.Kom : 0416068401

SUMEDANG, 27 JANUARI 2012 Mengetahui : KETUA STMIK SUMEDANG, Pembimbing, PEMBANTU KETUA I,

Dady Mulyadi, Drs., M.M. NIK. 00010001

Dwi Yuniarto, Sos., M.Kom. NIK. 05010020


BAHAN AJAR SESSI/PERKULIAHAN KE 1 TujuanInstruksionalUmum Pada akhir pertemuan ini mahasiswa diharapkan mampu : Memahami sistem pengorganisasian data pada memori komputer dan file (berkas) pada media penyimpanan. Mengimplementasikannya dalam program dengan menggunakan salah satu bahasa (Bahasa C/Pascal) untuk membuat berbagai macam struktur data (array, tree, struct) dengan teknik-teknik tertentu (linked list, stack, dan queue) serta manipulasinya (sorting dan searching) secara baik, efisien, dan cepat.

Tujuan Instruksional Khusus : Pada akhir pertemuan ini anda diharapkan mampu :1. Memahami silabus, sap mata kuliah praktikum struktur data 2. Memahami dasar hubungan algoritma dengan struktur data 3. Mengenal dan memahami dasar struktur data

Pokok Bahasan : Pengenalan Praktikum Struktur Data Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari ruang lingkup, memahami dasar hubungan algoritma dengan struktur data, serta kategori materi struktur data secara garis besar yang merupakan pembelajaran lanjutan dari praktikum algoritma dan pemrograman pada semester sebelumnya. I. Buku / bacaan wajib (bw)1. 2. 3. 4. Algoritma dan Pemrograman EDISI 3 (Rinaldi Munir;2004) Algoritma dan Struktur Data dengan C# (Adi Nugroho;2009) Anonim, Algoritma dan Pemrograman II, Penerbit Gunadarma, Jakarta, 1990 Moh. Sjukani, Algoritma dan Struktur Data dengan C, C++, dan Java, Mitra Wacana Media, 2005 5. Dwi Sanjaya, Asyiknya Belajar Struktur Data di Planet C++, PT. Elex Media Komputindo, Jakarta, 2005

6. Abdul Kadir, Pemrograman Turbo PASCAL untuk IBM PC Versi 5.0 dan 5.5, Penerbit PT. Elex Media Komputindo, Jakarta


Pengantar Struktur Data Bagaimana cara mengatasi masalah implementasi program dengan komputer? 1. Pemahaman masalah secara menyeluruh dan persiapan data 2. Keputusan operasi-operasi yang dilakukan terhadap data 3. Penyimpanan data-data pada memori sehingga tersimpan dan terstruktur secara logis, operasinya efisien 4. Pengambilan keputusan terhadap bahasa pemrograman mana yang paling cocok untuk jenis data yang ada Perbedaan Tipe data, Objek data, dan Struktur Data 1. Tipe data adalah jenis data yang mampu ditangani oleh suatu bahasa pemrograman pada komputer. 2. Tiap-tiap bahasa pemrograman memiliki tipe data yang memungkinkan: 3. Deklarasi terhadap variabel tipe data tersebut 4. Menyediakan kumpulan operasi yang mungkin terhadap variabel bertipe data tersebut 5. Jenis obyek data yang mungkin 6. Contoh tipe data di C? Java? Pascal? .NET?


BAHAN AJAR SESSI/PERKULIAHAN KE 2 TujuanInstruksionalUmum Pada akhir pertemuan ini mahasiswa diharapkan mampu : Memahami sistem pengorganisasian data pada memori komputer dan file (berkas) pada media penyimpanan. Mengimplementasikannya dalam program dengan menggunakan salah satu bahasa (Bahasa C/Pascal) untuk membuat berbagai macam struktur data (array, tree, struct) dengan teknik-teknik tertentu (linked list, stack, dan queue) serta manipulasinya (sorting dan searching) secara baik, efisien, dan cepat. Tujuan Instruksional Khusus : Pada akhir pertemuan ini anda diharapkan mampu :1. 2. 3. Memahami konsep fungsi, dan kegunaan array dalam bahasa C++/Pascal Memahami konsep fungsi, dan kegunaan struct dalam bahasa C++/Pascal Membuat program sederhana sebagai solusi atas suatu masalah tertentu yang di dalamnya menggunakan array dan struct

4.

Pokok Bahasan : Pengenalan Struktur Data Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan array dalam bahasa C/Pascal, mempelajari fungsi dan kegunaan struct, membuat program sederhana yang di dalamnya terdapat array dan struct yang merupakan pembelajaran lanjutan dari praktikum algoritma dan pemrograman pada semester sebelumnya. I. Buku / bacaan wajib (bw)1. 2. 3. 4. Algoritma dan Pemrograman EDISI 3 (Rinaldi Munir;2004) Algoritma dan Struktur Data dengan C# (Adi Nugroho;2009) Anonim, Algoritma dan Pemrograman II, Penerbit Gunadarma, Jakarta, 1990 Moh. Sjukani, Algoritma dan Struktur Data dengan C, C++, dan Java, Mitra Wacana Media, 2005 5. Dwi Sanjaya, Asyiknya Belajar Struktur Data di Planet C++, PT. Elex Media Komputindo, Jakarta, 2005



ARRAY Array adalah suatu tipe data terstruktur yang berupa sejumlah data sejenis (bertipe data sama) yang jumlahnya tetap dan diberi suatu nama tertentu. Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-dimensi. DEKLARASItipe_data nama_var_array [ukuran];

tipe_data dll) nama_var_array ukuranContoh : Int nilai[6];

: menyatakan jenis tipe data elemen larik (int, char, float, : menyatakan nama variabel yang dipakai. : menunjukkan jumlah maksimal elemen larik.

INISIALISASI Menginisialisasi array sama dengan memberikan nilai awal array pada saat didefinisikan.int nilai[6] = {8,7,5,6,4,3};

Contoh diatas berarti berarti anda memesan tempat di memori komputer sebanyak 6 tempat dengan indeks dari 0-5, dimana indeks ke-0 bernilai 8, ke-1 bernilai 7, dst, dan dimana semua elemennya bertipe data integer. PENGAKSESANnama_var_array [indeks];

Pengisian dan pengambilan nilai pada indeks tertentu dapat dilakukan dengan mengeset nilai atau menampilkan nilai pada indeks yang dimaksud. Pengaksesan elemen array dapat dilakukan berurutan atau random berdasarkan indeks tertentu secara langsung. Contoh :#include void main () { int billy [] = {16, 2, 77, 40, 12071}; int n, result=0; for ( n=0 ; njml_kata=0; char *p = p_kata->elemen; printf("Masukkan kata : ");gets(kalimat); fflush(stdin); printf("Kalimat : %s\n",kalimat); for(int i=0;ijml_kata++; p++; } p=p_kata->elemen; //tampilkan kembali kalimat tersebut for(int i=0;ijml_kata;i++){ printf("%c ",*p); p++; } //kembangkan. getch(); }

Soal: Buatlah program data KTP, dengan menggunakan pointer pada struct KTP sebagai berikut:

11

typedef struct { int tgl; int bln; int th; }Tanggal; typedef struct { char noID[5]; char nama[30]; char jenis_kelamin; //L atau P Tanggal t; }KTP; typedef struct { KTP ktp; int jml; }Data_KTP; Data_KTP data_ktp; Data_KTP *p;

Buatlah fungsi untuk: 1. Menambah data 2. Mencari data berdasarkan tahun kelahiran tertentu 3. Menampilkan data berdasarkan L dan P 4. Mengedit data Semua pengaksesan dilakukan dengann menggunakan pointer.

12

BAHAN AJAR SESSI/PERKULIAHAN KE 10 TujuanInstruksionalUmum Pada akhir pertemuan ini mahasiswa diharapkan mampu : Memahami sistem pengorganisasian data pada memori komputer dan file (berkas) pada media penyimpanan. Mengimplementasikannya dalam program dengan menggunakan bahasa pemrograman (Bahasa C/Pascal) untuk membuat berbagai macam struktur data (array, tree, struct) dengan teknik-teknik tertentu (linked list, stack, dan queue) serta manipulasinya (sorting dan searching) secara baik, efisien, dan cepat. Tujuan Instruksional Khusus : Pada akhir pertemuan ini anda diharapkan mampu :1. Memahami konsep fungsi dan penggunaan senarai tunggal (Linked List) 2. Membuat program sederhana sebagai solusi atas suatu masalah tertentu yang di dalamnya menggunakan Linked List

Pokok Bahasan : Kegunaan Linked List Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan Linked List dalam bahasa C/Pascal. membuat program sederhana yang di dalamnya terdapat Linked List yang merupakan pembelajaran lanjutan dari praktikum algoritma dan pemrograman pada semester sebelumnya.

I. Buku / bacaan wajib (bw)1. 2. 3. 4. Algoritma dan Pemrograman EDISI 3 (Rinaldi Munir;2004) Algoritma dan Struktur Data dengan C# (Adi Nugroho;2009) Anonim, Algoritma dan Pemrograman II, Penerbit Gunadarma, Jakarta, 1990 Moh. Sjukani, Algoritma dan Struktur Data dengan C, C++, dan Java, Mitra Wacana Media, 2005 5. Dwi Sanjaya, Asyiknya Belajar Struktur Data di Planet C++, PT. Elex Media Komputindo, Jakarta, 2005


13

SENARAI BERANTAI TUNGGAL TIDAK BERPUTAR (SINGLE LINKED LIST NON CIRCULAR) DEKLARASI LINKED LIST Sebelum membuat sebuah senarai (Link List) kita harus mendeklarasikan tipe data dan pointer yang akan kita gunakan. Selain itu kita juga harus mendeklarasikan list -list yang nantinya akan kita gunakan. Sebagai contoh:#include stdio.h typedef struct Gerbong terdiri dari 2 field { int data; Gerbong *next; }; Gerbong *baru; list Gerbong *kepala; Gerbong *ekor; list Gerbong *bantu; Gerbong *hapus; //membuat sebuah tipe data baru yang //field data bertipe integer //field next merupakan pointer dari list //variable baru bertipe pointer dari //variable kepala bertipe pointer dari list //variable ekor bertipe pointer dari //variable bantu bertipe pointer dari list //variable hapus bertipe pointer dari list

catatan: 'Gerbong' diatas merupakan nama dari tipe data bentukan. kepala, ekor, baru, bantu,hapus merupakan variable pointer yang berisi alamat memori. kepala merupakan node paling awal dan selalu tetap(tidak boleh berpindah). ekor merupakan node paling akhir jadi ketika terjadi penambahan sebuah node yang diletakan di belakang maka pointer dari ekor akan ikut berpindah. baru merupakan nama untuk node yang diciptakan atau ditambahkan. bantu, hapus digunakan untuk memudahkan operasi edit dan delete sebuah node.

ILUSTRASI Senarai berantai dapat diilustrasikan seperti satu kesatuan rangkaian kereta api. Kereta api terdiri dari beberapa gerbong, masing-masing dari gerbong itulah yang disebut struct / tipe data bentukan. Agar gerbong-gerbong tersebut dapat saling bertaut dibutuhkan minimal sebuah kait yang dinamakan sebagai pointer. Setelah mendeklarasikan tipe data dan pointer pada list, selanjutnya kita akan mencoba membuat senarai / linked list tunggal tidak berputar atau sebuah gerbong. Ada beberapa operasi yang dapat kita buat pada senarai tersebut, diantaranya: tambah, hapus dan edit dari gerbong tersebut. Inti dari linked list adalah proses (tambah, edit, hapus) dari gerbong / node dan bagaimana rnenyambungkan antar gerbong / node tersebut.

14

Gambar diatas dilustrasikan sebuah rangkaian kereta api dengan 4 buah gerbong. Gerbong A akan disebut sebagai kepala / head (walaupun penamaan ini bebas) dan gerbong D adalah ekor / tail. Tanda panah merupakan kait atau pointer yang menghubungkan satu gerbong dengan yang lainnya. Pointer yang dimiliki D menuju ke NULL,inilah yang membedakan antara senarai berputar dengan yang tidak berputar. Kalau senarai berputar maka pointer dari D akan menuju ke A lagi. PEMBENTUKAN NODE (GERBONG) Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL. Pembentukan node tidak dapat dilakukan sekaligus namun harus satu persatu, hal ini berkaitan dengan bagaimana cara menyambungkan antar node tersebut.kepala= new Gerbong; kepala->next==NULL; kepala->data=101; //membuat sebuah node dengan nama kepala //pointer milik kepala diarahkan ke NULL //isi field data dengan 101

Kode diatas apabila dicompile maka akan membentuk sebuah node bertipe Gerbong dengan nama kepala. Karena bertipe list maka kepala juga memiliki 2 field seperti list yaitu field data dan field next. Bila diasumsikan dengan gerbong maka pada proses ini dibentuk gerbong A. Setelah membentuk sebuah node dengan nama kepala, maka langkah selanjutnya adalah membentuk gerbong yang lain (gerbong B dan selanjutnya).baru=new Gerbong; baru->data=5; //membuat sebuah node dengan nama baru

//Tambah Depanif (kepala->next==NULL) { baru-->next=kepala; node kepala kepala=baru; } //rnenyambung node bare dengan //memindahkan kepala ke node baru

//Tambah Belakange k or -> n ex t= b ar u; node baru ekor=baru; node baru . ekor->next=NULL; //menyambung node paling akhir/ekor ke //meniindahkan ekor ke node terakhir yaitu

15

Tambah belakang berarti node baru yang terbentuk akan diletakan di posisi paling belakang. PENGHAPUSAN NODE Pada senarai berkepala, penghapusan sebuah list dilakukan jika ada list lain yang bukan list "kepala" dalam barisan senarai tersebut. Dengan kata lain, list yang digunakan sebagai "kepala" tidak boleh dihapus, "kepala harus dipindahkan terlebih dahulu. Keyword yang digunakan adalah delete. Contoh: //Hapus Depan

if(kepala->next!=NULL) { if(kepala->next==ekor) { hapus=kepala; kepala=kepala->next; delete hapus; } } else { kepala=NULL; }

//Hapus Belakang

if(head->next!=NULL) { bantu=kepala; while(bantu->next->next!=NULL) { bantu=bantu->next; } hapus=bantu->next; bantu->next = NULL; delete hapus; } else { head =NULL; }

16

MENAMPILKAN ISI NODE Untuk menampilkan isi suatu node dengan cara mengakses field yang ada di dalam node tersebut. Yaitu dengan Contoh :bantu =head; while(bantu!=NULL) { printf(%i ,bantu->data); bantu=bantu->next; }

LATIHAN 1. Buatlah sebuah linked list non circular yang berisi nim anda dan nama lengkap anda. 2. Buat fungsi untuk menambahkan node single linked list non circular dimana tiap node mengandung informasi nim dan nama. Peletakan posisi node urut berdasar nim secara ascending, jadi bisa tambah depan, belakang maupun tambah di tengah. Isikan data nim dan nama lengkap teman sebelah kiri dan kanan anda!!! 3. Buatlah fungsi untuk menampilkan data 3 buah node yang telah anda bentuk sebelumnya. Contoh tampilan NIM Nama Lengkap 22053766 Hernawan 22053768 Andrew S 22053791 Anthony S 4. Buatlah fungsi untuk mencari nama yang telah diinputkan dengan menggunakan NIM. Contoh tampilan: Inputkan nim yang dicari = 22053768 Nama yang tercantum Andrew S 5. Buatlah sebuah fungsi untuk menghapus nim yang diinputkan oleh user. Contoh tampilan: NIM yang mau dihapus = 2205376 NIM dengan nama Andrew S ditemukan dan telah dihapus 6. Buatlah sebuah program dengan menggunakan single linked list non circular dengan fungsi-fungsi: menambah data(dari depan dan dari belakang) search data yang telah diinputkan menghapus data( dari depan dan dari belakang) mencetak data Buat dengan menggunakan menu ya.. 7. (soal extended) Dengan menggunakan soal no 6 tambahkan 4 fungsi tambahan:

17

menambah data(di tengah) menghapus data tertentu(berada di tengah) mengurutkan data acak secara acending mengurutkan data acak secara decending SELAMAT MENGERJAKAN

SENARAI BERANTAI TUNGGAL BERPUTAR (SINGLE LINKED LIST CIRCULAR) Perbedaan Single Linked list Circular dengan Non Circular Pada saat kita membahas Single Linked List non Circular telah dijelaskan bahwa kita membutuhkan sebuah kait untuk menghubungkan node-node / gerbong-gerbong data yang ada. Perbedaan dengan Single Linked List Circular adalah pada node terakhir/ ekor yang semula menunjuk ke NULL diganti menunjuk kembali ke kepala atau head. Contoh Struct Single Link List Circular

Dengan melihat gambar kita dapat membayangkan bahwa setiap node akan membentuk lingkaran, dan semakin banyak node lingkaran akan semakin besar. Pada intinya tail akan selalu terhubung dengan head. Membuat Single Linked List Circular berkepala berputar Untuk menginisialisasikan Single Linked List Circular berkepala berputar cukup mudah karena kita hanya seperti memberikan label pada suatu list. Cara mendeklarasikanna seperti contoh dibawah ini:#include stdio.h typedef struct Tnode { int data; Tnode *next; }; Tnode *bantu; Tnode *baru; Tnode *head; Tnode *tail; void main() { head=new Tnode; head ->next=head; } head -> data = 50;

//mendeklarasikan //mendeklarasikan //mendeklarasikan //mendeklarasikan

pointer pointer pointer pointer

bantu baru head tail

//memasukkan data Single Linked list Circular berkepala berputar //menambah simpul baru dan menghubungkannya dengan simpul kepalabaru = new Tnode; baru -> data = 20; digunakan untuk penambahan baru -> next = head; apakah perintah ini masih dapat simpul berikutnya???

18

head ->next = head;

//menambah simpul baru dan membuat ekor pada akhir senaraitail = baru; baru = new Tnode; baru -> data = 30; digunakan untuk penambahan baru ->next=head; tail -> next=baru; tail = baru; apakah perintah ini masih dapat simpul berikutnya???

Pada senarai berantai seperti gambar di bawah:

Bagaimana cara meletakkan data baru 40 diantara simpul dengan data 50 dan 20?? Tambahkan pada program diatas:baru=new Tnode; baru->data=40; baru->next=head->next; head->next=baru;

Mengedit / update data Misalnya kita ingin mengganti data pada ekor menjadi 25, caranya adalah sebagai berikut:tail->data=25;

Membaca senarai Tambahkan pada program diatasbantu=head; printf(%d, bantu); bantu=bantu->next; while(bantu!=head) { printf(%d, bantu); bantu=bantu->next; }

Menghapus Simpul ekor Tambahkan pada program diatas:bantu=head; while(bantu->next!=tail) { bantu=bantu->next; } bantu->next=head; delete tail; tail=bantu;

19

Menghapus Simpul kepala/head Tambahkan pada program diatas:bantu=head->next; delete head; head = bantu;

Latihan 1. Buatlah sebuah Single Linked List Circular yang mcmpunyai 5 buah simpul seperti pada contoh dibawah ini

a. Tuliskan listing program untuk membaca data dari seluruh simpul dengan menggunakan perulangan (for/while) b. TuIiskan listing program untuk menambah sebuah simpul baru dengan data 5 yang diletakan diantara data 30 dan data 20. c. Tuliskan listing program untuk menghapus simpul dengan data 20 tanpa merusak senarai. d. Tuliskan listing program untuk menghapus semua simpul dengan menggunakan variabel bantu dengan menggunakan perulangan (while/for). 2. Buat lah program Single Linked List Circular yang fleksibel dan dinamis. Dimana user dapat menambah simpul baru beserta datanya, membaca semua data pada senarai, menghapus simpul dengan data yang ditentukan oleh user, dan dapat menghapus semua simpul yang ada. Jangan Iupa membuat trapping errornya. 3. (soal extended) Buatlah sebuah link list berisi data-data identitas ktp(nama, alamat, no KTP) buatlah menu sebagai berikut: a. Input entry ktp ( input akan langsung terurutkan berdasarkan no ktp asending ) b. Delete file yang diinginkan user. c. Searching entry ktp d. Cetak semua entry ktp e. Cetak entry ktp tertentu 4. (soal extended) Buatlah 3 link list yang merepresentasikan jam(1-12), menit(160) dan detik(1-60). Mintalah inputan dari user berupa jumlah detik.

20

Konversikan jumlah detik tersebut dan masukkan ke dalam link list (gunakan pointer jam,menit,detik) kemudian cetak jam yang tertera di link list tersebut.

21

BAHAN AJAR SESSI/PERKULIAHAN KE 11 TujuanInstruksionalUmum Pada akhir pertemuan ini mahasiswa diharapkan mampu : Memahami sistem pengorganisasian data pada memori komputer dan file (berkas) pada media penyimpanan. Mengimplementasikannya dalam program dengan menggunakan bahasa pemrograman (Bahasa C/Pascal) untuk membuat berbagai macam struktur data (array, tree, struct) dengan teknik-teknik tertentu (linked list, stack, dan queue) serta manipulasinya (sorting dan searching) secara baik, efisien, dan cepat. Tujuan Instruksional Khusus : Pada akhir pertemuan ini anda diharapkan mampu :1. Memahami konsep fungsi dan penggunaan senarai ganda (Double Linked List) 2. Membuat program sederhana sebagai solusi atas suatu masalah tertentu yang di dalamnya menggunakan Double Linked List

Pokok Bahasan : Double Linked List Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan Double Linked List dalam bahasa C/Pascal. membuat program sederhana yang di dalamnya terdapat Double Linked List yang merupakan pembelajaran lanjutan dari praktikum algoritma dan pemrograman pada semester sebelumnya.

I. Buku / bacaan wajib (bw)1. 2. 3. 4. Algoritma dan Pemrograman EDISI 3 (Rinaldi Munir;2004) Algoritma dan Struktur Data dengan C# (Adi Nugroho;2009) Anonim, Algoritma dan Pemrograman II, Penerbit Gunadarma, Jakarta, 1990 Moh. Sjukani, Algoritma dan Struktur Data dengan C, C++, dan Java, Mitra Wacana Media, 2005 5. Dwi Sanjaya, Asyiknya Belajar Struktur Data di Planet C++, PT. Elex Media Komputindo, Jakarta, 2005


22

Double Linked ListTidak jauh berbeda dengan materi sebelumnya yakni Single Linked List. Materi ini hanya menambahkan satu pointer (yang nantinya dapat dikembangkan dengan banyak pointer). Bila kita lihat lagi penggambaran dari Single Linked List :typedef struct TNode { int data; TNode *next; };

data pointer next

Sedangkan pada materi yang ada sekarang, kita akan menambahkan satu lagi pointernya. Sehingga bila kita lihat ilustrasinya :typedef struct TNode{ int nim; TNode *next; TNode *prev; };

data pointer prev pointer next

Untuk setiap pembuatan node yang baru kita mempergunakan keyword new.TNode *baru; baru = new TNode; baru ->data = databaru; baru ->next = NULL; baru-> prev = NULL;

Sama seperti Single Linked List, kita juga membagi materi ini dalam dua jenis, yakni : a. Non Circular b. Circular Dimana tiap-tiap juga akan terdiri dari linked list yang terdiri dari Head saja dan Head dengan Tail. A. Non Circular 1. Dengan Head - Menggunakan 1 pointer head - Head selalu menunjuk node pertama Sebelumnya kita harus mendeklarasikan dulu pointer head :TNode *head;

Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai null terlebih dahulu :

23

head = NULL;

untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Head-nya.int isEmpty() { if(head==NULL) return 1; else return 0; }

Contoh program : Penambahan didepanvoid tambahdata (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; } printf(data masuk); }

Penggambaran : head

NULL

Setelah dibuat node baru dan jika diketahui head==NULL : head baru

Bila kita membuat node baru lagi maka

24

baru

head

head

baru

head

head

Penambahan di belakang

void insertBelakang (int databaru){ TNode *baru,*bantu; //digunakan untuk mengetahui data terbelakang baru = new TNode; baru->data = databaru; baru->next = NULL; baru->prev = NULL; if(isEmpty()==1){ head=baru; head->next = NULL; head->prev = NULL; } else { bantu=head; while(bantu->next!=NULL){ bantu=bantu->next; } bantu->next = baru; baru->prev = bantu; } printf(data masuk); }

25

Tampil

void tampil(){ TNode *bantu; bantu = head; if(isEmpty()==0){ while(bantu!=NULL){ printf(%i ,bantu->data); bantu=bantu->next; } printf(\n); } else printf(Masih Kosong); }

Hapus 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; } prinf(%i terhapus,d); } else printf(Masih Kosong); }

Hapus di belakang

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; }

26

printf(%i terhapus,d); } else printf(Masih Kosong); }

latihan : Buatlah ilustrasi dari masing-masing potongan program. Buat program lengkap dari potongan-potongan program yang ada diatas! Buat agar menjadi seperti menu. Buat program untuk memasukkan node baru tetapi diantara node yang sudah ada. Tentukan node yang baru akan berada pada antrian keberapa. 2. Dengan Head dan tail - Menggunakan 2 pointer, head dan tail. - Head selalu menunjuk node pertama dan tail selalu menunjuk node terakhir Sebelumnya kita harus mendeklarasikan dulu pointer head :TNode *head, *tail;

Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai null terlebih dahulu :head = NULL; tail = NULL;

untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Tail-nya.int isEmpty() { if(tail==NULL) return 1; else return 0; }

27

Contoh program : Penambahan di depanvoid tambahdata (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->next=NULL; tail->prev=NULL; } else { baru->next=head; head->prev=baru; head=baru; } printf(data masuk); }

Penggambaran : head tail

NULL

Setelah dibuat node baru dan jika diketahui tail==NULL : head tail baru

Bila kita membuat node baru lagi maka : baru head tail

28

head

tail

baru

head

tail

head

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 = head->prev = tail->prev = tail->next = } else { tail->next = baru->prev = tail = baru; tail->next = } printf(Data sudah }

NULL; NULL; NULL; NULL; baru; tail; NULL; masuk\n);

Tampil

void tampil(){ TNode *bantu; bantu = head; if(isEmpty()==0){ while(bantu!=tail->next){ prinrf(%i ,bantu->data); bantu=bantu->next; } coutdata; head = head->next; head->prev = NULL; delete hapus; } else { d = head->data; head = NULL; tail = NULL; } printf(%i terhapus\n,d); } else printf(masih kosong\n); }

Hapus di belakang

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; } printf(%i terhapus,d); } else printf(Masih Kosong); }

latihan : Buatlah ilustrasi dari masing-masing potongan program. Buat program lengkap dari potongan-potongan program yang ada diatas! Buat agar menjadi seperti menu. Buat program untuk memasukkan node baru tetapi diantara node yang sudah ada. Tentukan node yang baru akan berada pada antrian keberapa.

B. Non Circular dengan Head, head & tail 1. Dengan Head

30

- Menggunakan 1 pointer head - Head selalu menunjuk node pertama Sebelumnya kita harus mendeklarasikan dulu pointer head :TNode *head;

Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai null terlebih dahulu :head = NULL;

untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Head-nya.int isEmpty() { if(head==NULL) return 1; else return 0; }

Contoh program : Penambahan di depanvoid tambahdata (int databaru){ TNode *baru,*bantu; //pointer bantu digunakan untuk menunjuk node terakhir (head->prev) 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; } printf(data masuk); }

Penggambaran : head

NULL

31

Setelah dibuat node baru dan jika diketahui head==NULL : head baru

Bila kita membuat node baru lagi maka : baru head bantu

baru

head

bantu

baru

head

bantu

head

bantu

head

bantu

32


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; } printf(data masuk); }

Tampil

void tampil(){ TNode *bantu; bantu = head; if(isEmpty()==0){ do{ printf(%i ,Bantu->data); bantu=bantu->next; }while(bantu!=head); printf(\n); } else printf(masih Kosong);coutdata; bantu = head->prev; head = head->next; bantu->next = head; head->prev = bantu; delete hapus; } else { d = head->data; head = NULL; } printf(%i terhapus,d); } else printf(Masih kosong\n); }

Hapus di belakang

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; } printf(%i terhapus\n,d); } else printf(Masih Kosong); }

34

latihan : Buatlah ilustrasi dari masing-masing potongan program. Buat program lengkap dari potongan-potongan program yang ada diatas! Buat agar menjadi seperti menu. Buat program untuk memasukkan node baru tetapi diantara node yang sudah ada. Tentukan node yang baru akan berada pada antrian keberapa.

2. Dengan Head dan tail - Menggunakan 2 pointer, head dan tail. - Head selalu menunjuk node pertama dan tail selalu menunjuk node terakhir Sebelumnya kita harus mendeklarasikan dulu pointer head :TNode *head, *tail;

Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai null terlebih dahulu :head = NULL; tail = NULL;

untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Tail-nya.int isEmpty() { if(tail==NULL) return 1; else return 0; }

Contoh program : Penambahan di depan

void tambahdata (int databaru){ TNode *baru; baru = new TNode; baru -> data = databaru; baru -> next = NULL; baru -> prev = NULL;

35

if (isEmpty()==1) { head=baru; tail=head; 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; } printf(data masuk); }

Penggambaran : head tail

NULL

Setelah dibuat node baru dan jika diketahui tail==NULL : head baru tail

Bila kita membuat node baru lagi maka : baru head bantu

baru

head

tail

36

baru

head

tail

head

bantu

head

bantu


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; } printf(Data masuk\n); }

37

Tampil

void tampil(){ TNode *bantu; bantu = head; if(isEmpty()==0){ do{ coutdata; head = head->next; tail->next = head; head->prev = tail; delete hapus; } else { d = head->data; head = NULL; tail = NULL; } printf(%i terhapus\n,d); } else printf(Masih Kosong); }

38

Hapus di belakang

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; } coutkiri,databaru); else if(databaru > (*root)->data) tambah(&(*root)->kanan,databaru); else if(databaru == (*root)->data) printf("Data sudah ada!"); }

Variabel **root menunjukkan node mana yang sedang dicek saat ini, untuk itu saat pemanggilan fungsi ini, variabel **root kita beri nilai pointer yang menunjuk ke node akar, yaitu pohon.tambah(&pohon,data);

Untuk selengkapnya dapat dilihat pada bagian 5, kode program lengkap. 4. Membaca dan Menampilkan Node Pada Tree Untuk membaca dan menampilkan seluruh node yang terdapat pada pohon biner, terdapat 3 macam cara, atau yang biasa disebut kunjungan (visit). Semua kunjungan diawali dengan mengunjungi akar pohon. Karena proses kunjungan ini memerlukan perulangan proses yang sama namun untuk depth (kedalaman) yang berbeda, maka ketiganya diimplementasikan dengan fungsi rekursif. a. Kunjungan Pre-Order. Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan: 1. Cetak isi (data) node yang sedang dikunjungi 2. Kunjungi kiri node tersebut, - Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut. - Jika kiri kosong (NULL), lanjut ke langkah ketiga. 3. Kunjungi kanan node tersebut, - Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut. - Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

51

void preOrder(Node *root){ if(root != NULL){ printf("%d ",root->data); preOrder(root->kiri); preOrder(root->kanan); } }

b. Kunjungan In-Order. 1. Kunjungi kiri node tersebut, - Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut. - Jika kiri kosong (NULL), lanjut ke langkah kedua. 2. Cetak isi (data) node yang sedang dikunjungi 3. Kunjungi kanan node tersebut, - Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut. - Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.void inOrder(Node *root){ if(root != NULL){ inOrder(root->kiri); printf("%d ",root->data); inOrder(root->kanan); } }

c. Kunjungan Post-Order. 1. Kunjungi kiri node tersebut, - Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut. - Jika kiri kosong (NULL), lanjut ke langkah kedua. 2. Kunjungi kanan node tersebut, - Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut. - Jika kanan kosong (NULL), lanjut ke langkah ketiga. 3. Cetak isi (data) node yang sedang dikunjungi. Proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.void postOrder(Node *root){ if(root != NULL){ postOrder(root->kiri); postOrder(root->kanan); printf("%d ",root->data); } }

52

Variabel **root pada setiap fungsi diatas menunjukkan node mana yang sedang dikunjungi saat ini, untuk itu saat pemanggilan, variabel **root kita beri nilai pointer yang menunjuk ke node akar, yaitu pohon.preOrder(pohon); inOrder(pohon); postOrder(pohon);

Untuk selengkapnya dapat dilihat pada bagian 5, kode program lengkap. 5. Kode Program Lengkap Berikut ini kode program keseluruhan, termasuk menu tampilan, di mana di dalamnya terdapat Deklarasi Tree, Inisialisasi Tree, Penambahan Node, dan Pembacaaan serta Menampilkan Node dengan 3 macam kunjungan. Kode ditulis dengan C++ 3.00.#include #include typedef struct Node{ int data; Node *kiri; Node *kanan; }; void tambah(Node **root,int databaru){ if((*root) == NULL){ Node *baru; baru = new Node; baru->data = databaru; baru->kiri = NULL; baru->kanan = NULL; (*root) = baru; (*root)->kiri = NULL; (*root)->kanan = NULL; printf("Data bertambah!"); }

53

else if(databaru < (*root)->data) tambah(&(*root)->kiri,databaru); else if(databaru > (*root)->data) tambah(&(*root)->kanan,databaru); else if(databaru == (*root)->data) printf("Data sudah ada!"); } void preOrder(Node *root){ if(root != NULL){ printf("%d ",root->data); preOrder(root->kiri); preOrder(root->kanan); } } void inOrder(Node *root){ if(root != NULL){ inOrder(root->kiri); printf("%d ",root->data); inOrder(root->kanan); } } void postOrder(Node *root){ if(root != NULL){ postOrder(root->kiri); postOrder(root->kanan); printf("%d ",root->data); } } void main(){ int pil,c; Node *pohon,*t; pohon = NULL; do{ clrscr(); int data; printf("MENU\n"); printf("1. Tambah\n"); printf("2. Lihat pre-order\n"); printf("3. Lihat in-order\n"); printf("4. Lihat post-order\n"); printf("5. Exit\n"); printf("Pilihan : "); scanf("%d",&pil); switch(pil){ case 1: printf("Data baru : ");scanf("%d", &data); tambah(&pohon,data); break; case 2: if(pohon!=NULL) preOrder(pohon); else printf("Masih kosong!"); break; case 3: if(pohon!=NULL) inOrder(pohon); else printf("Masih kosong!"); break;

54

case 4: } getch(); }while(pil!=5); }

if(pohon!=NULL) postOrder(pohon); else printf("Masih kosong!"); break;

Soal Berikut ini beberapa latihan yang dapat dicoba, setelah selesai cek hasil kerja anda bersama asisten praktikum. 1. Buatlah fungsi untuk menghitung jumlah node keseluruhan pada pohon biner. Penghitungan dilakukan dengan menjelajahi isi pohon, bukan dengan menambahkan counter saat setiap data baru dimasukkan!. 2. Buatlah fungsi untuk mencetak semua leaf (daun) yang ada pada pohon biner. 3. Buatlah fungsi untuk mencetak nilai node minimum (terkecil) pada pohon biner. 4. Tanpa mencobanya pada kompiler C++, analisislah untuk apa fungsi F di bawah ini:int F(Node *root) { if (root == NULL) return -1; int u = F(root->kiri), v = F(root->kanan); if (u > v) return u+1; else return v+1; }

5. Tanpa mencobanya pada kompiler C++, analisislah untuk apa fungsi G di bawah ini, dan nilai yang dikembalikan berupa apa?Node *G(Node *root) { if(root == NULL) return NULL; else if(root->kanan == NULL) return root; else return G(root->kanan); }

55

fathonim bahan ajar if2018 prak.struktur data

Documents