teori struktur data full

BAHAN AJAR

Program studi : Teknik Informatika Kode Mata Kuliah : IKK112111 Mata kuliah : Struktur Data SKS : 3 SKS Semester : 3 Jenis Mata Kuliah : Wajib Kelompok MK : MKK

STMIK EL RAHMA YOGYAKARTA

Dibuat Oleh Revisi ke Tanggal dibuat Diperiksa oleh

Kaprodi TI

ii

KATA PENGANTAR

Puji syukut saya penjatkan kehadirat Alloh SWT, atas limpahan rahmad dan hidayahya saya

dapat menyelesaikan bahan ajar untuk mata kuliah Struktur Data Program Studi Teknik

Informatika.

Bahan ajar ini berisikan materi-matari tentang konsep struktur data yang meliputi konsep

linkedlist, double linkedlist, stack, queue, sorting dan seaching, tree. Besar harapan saya bahan

ajar ini akan mempermudah mahasiswa untuk mempelajari Struktur Data.

Tidak lupa saya mengucapkan terima kasih yang sebesar-besarnya kepada semua pihak yang

telah berkontribusi sampai selesainya bahan ajar ini. Untuk menyempurnakan bahan ajar ini,

segala masukan dan saran sangat saya harapkan.

Penyusun

Eko Riswanto

iii

DAFTAR ISI

Halaman Depan ........................................................................................................................ i

Kata Pengantar ......................................................................................................................... ii

Daftar Isi .................................................................................................................................. iii

Bab 1 Linked List (Senara Berkait) ........................................................................................ 1

Bab 2 Linked List (Lanjutan) .................................................................................................. 6

Bab 3 Double Linked List ........................................................................................................ 8

Bab 4 Stack (Tumpukan) ........................................................................................................ 14

Bab 5 Stack Dengan Pointer ................................................................................................... 25

Bab 6 Pengurutan (Sorting) .................................................................................................... 30

Bab 7 Pencarian (Searching) .................................................................................................. 33

Bab 8. Pohon (Tree) ................................................................................................................ 35

1

BAB 1. LINKED LIST (SENARAI BERKAIT)

Pengertian Linked List

Salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara sekuensial, saling

bersambungan, dinamis adalah senarai berkait (linked list).Suatu senarai berkait (linked list) adalah

suatu simpul (node) yang dikaitkan dengan simpul yang lain dalam suatu urutan tertentu. Suatu

simpul dapat berbentuk suatu struktur atau class. Simpul harus mempunyai satu atau lebih elemen

struktur atau classyang berisi data.

Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan

bantuanpointer. Dikatakansingle linked apabila hanya ada satu pointer yangmenghubungkan setiap

node.singleartinya field pointernya hanya satu buah saja dan satu arah.

Senarai berkait adalah struktur data yang paling dasar. Senarai berkait terdiri atas

sejumlah unsur-unsur dikelompokkan, atau terhubung, bersama-sama di suatu deret yang

spesifik. Senarai berkait bermanfaat di dalam memelihara koleksi-koleksi data, yang serupa

dengan array/larik yang sering digunakan. Bagaimanapun juga, senarai berkait memberikan

keuntungan-keuntungan penting yang melebihi array/larik dalam banyak hal. Secara rinci, senarai

berkait lebih efisien di dalam melaksanakan penyisipan-penyisipan dan penghapusan-penghapusan. Senarai

berkait juga menggunakan alokasi penyimpanan secara dinamis, yang merupakan penyimpanan yang

dialokasikan pada runtime . Karena di dalam banyak aplikasi, ukuran dari data itu tidak diketahui pada

saat kompile, hal ini bisa merupakan suatu atributyang baik juga. Setiapnodeakan berbentuk struct dan

memiliki satu buahfield bertipe structyang sama, yang berfungsi sebagai pointer. Dalam

menghubungkan setiap node, kita dapat menggunakan cara first-create-first-access ataupun first-create-

last-access. Yang berbeda dengan deklarasi struct sebelumnya adalah satu field bernama next, yang

bertipe struct node. Hal ini sekilas dapat membingungkan. Namun, satu hal yang jelas, variabel next ini akan

menghubungkan kita dengan node di sebelah kita, yang juga bertipe struct node.Hal inilah yang

menyebabkan next harus bertipe struct node

Deklarasi node:

struct node

{

char nama[20];

int umur;

float tinggi;

node *next; // Pointer menyambung ke node selanjutnya

};

Gambar sebuah node:

data point datadata point

1. Bagian pertama, disebut medan informasi, berisi informasi yang akan disimpan dan diolah.

2. Bagian kedua, disebut medan penyambung (link field), berisi alamat simpul berikutnya

Pada gambar di atas, pointer awal menunjuk ke simpul pertama dari senerai tersebut.

Medan penyambung (pointer) dari suatu simpul yang tidak menunjuk simpul lain disebut pointer

kosong, yang nilainya dinyatakan sebagai null (null adalah kata baku yang berarti bahwa pointer

2

0 atau bilangan negatif). Jadi kita bisa melihat bahwa dengan hanya sebuah pointer Awal saja

maka kita bisa membaca semua informasi yang tersimpan dalam senerai

MENAMBAH SIMPUL DI BELAKANG

Sekarang kita akan mempelajari bagaimana menambah simpul baru ke dalam senerai berantai.

Kita anggap bahwa simpul baru yang akan ditambah selalu menempati posisi setelah posisi yang

terakhir dari senerai berantai yang diketahui. Untuk menjelaskan operasi ini baiklah kita gunakan

deklarasi pointer dan simpul seperti di bawah ini:

struct node

{

char nama[20];

int umur;

float tinggi;

node *next;

};

Menambahkan simpul diakhir list

Misalkan simpul baru yang dibentuk diberi nama temp. Untuk menambahkan simpul baru

perlu kita uji apakah Linked list masih kosong atau tidak. Linked list yang kosong ditandai

dengan awal_ptr bernilai NULL. Jika tidak kosong maka dibaca senarai yang ada mulai dari

posisi awal sampai terakhir misalkan dengan menggunakan pointer temp2. Simpul terakhir

ditandai dengan medan penyambung dari temp2 bernilai NULL.Jika sudah berada pada simpul

terakhir kita tunjukkan medan penyambung temp2 dengan temp.

Program lengkap menambahkan simpul diakhit senarai sebagai berikut:

node *temp, *temp2; // pointer sementara

// Isi data

temp = new node; //menciptakan node baru

cout << "Nama : ";cin >> temp->nama;

cout << "Umur : ";cin >> temp->umur;

cout << "Tinggi : ";cin >> temp->tinggi;

temp->next = NULL;

// Inisialisasi pointer ketika masih kosong

if (awal_ptr == NULL)

{

awal_ptr = temp;

posisi = awal_ptr;

}

else

{

temp2 = awal_ptr;

// list tidak kosong

while (temp2->next != NULL)

{

temp2 = temp2->next;

// pindah ke link berikutnya

}

temp2->next = temp;

}

3

Menghapus simpul diakhir list kita gunakan cara sebagai berikut :

Untuk menghapus simpul diakhir perlu kita uji apakah senarai masih kosong atau tidak, jika

kosong tampilkan pesan bahwa list masih kosong. Jika tidak kosong perlu diuji apakah jumlah

simpul dalam senarai hanya satu yang ditandai dengan medan penyambung yang bernilai null.

Jika simpul lebih dari satu maka dibaca semua simpul sampai simpul terakhir yaitu medan

penyambung bernilai null.

node *temp1, *temp2;


cout << "List kosong!" << endl;

else

{

temp1 = awal_ptr;

if (temp1->next == NULL)

{

delete temp1;

awal_ptr = NULL;

}

else

{


{

temp2 = temp1;


}

delete temp1;

temp2->next = NULL;

}

}

Menghapus simpul diawallist

Menghapus simpul diawal dilakukan dengan cara menampung simpul awal pada pointer temp,

kemudian mengarahkan awal_ptr ke simpul selanjutnya. Kemudian simpul yang ditampung

dalam pointer temp dihapus.

node *temp;

temp = awal_ptr;

awal_ptr = awal_ptr->next;

delete temp;

Menampilkan list

Sebelum menampilkan linked list perlu kita uji apakah senarai kosong atau tidak. Jika senarai

kosong kita tampilkan pesan bahwa List kosong. Jika senarai tidak kosong maka kita baca

senarai mulai posisi awal sampai simpul terakhir.

node *temp;

temp = awal_ptr;

cout << endl;

if (temp == NULL)


else

{

while (temp != NULL)

{

// Menampilkan isi

cout << "Nama : " << temp->nama << " ";

4

cout << "Umur : " << temp->umur << " ";

cout << "Tinggi : " << temp->tinggi;

if (temp == posisi)

cout << " <– Posisi node";

cout << endl;

temp = temp->next;

}

cout << "Akhir list!" << endl;

}

Program Lengkap:

#include <iostream.h>

struct node

{

char nama[20];

int umur;

float tinggi;

node *next;

};

node *awal_ptr=NULL;

node *posisi;

int pilih;

void tambah_simpul_akhir()

{

node *temp, *temp2; //simpul sementara

//isi data

temp=new node;

cout<<"Nama : ";cin>>temp->nama;

cout<<"Umur : ";cin>>temp->umur;

cout<<"Tinggi : ";cin>>temp->tinggi;

temp->next=NULL;

//inisialisasi pointer ketika kosong

if(awal_ptr==NULL)

{

awal_ptr=temp;

posisi=awal_ptr;

}

else

{

temp2=awal_ptr;

while(temp2->next != NULL)

{


}

temp2->next=temp;

}

}

void tampil_senarai()

{

node *temp;

temp = awal_ptr;

if(temp == NULL)

cout<<"List kosong"<<endl;

else

{

cout<<endl<<endl;

while(temp != NULL)

{

cout<<"Nama : "<<temp->nama<<" ";

cout<<"Umur : "<<temp->umur<<" ";

cout<<"Tinggi : "<<temp->tinggi;

if (temp == posisi)

cout<<" << posisi simpul";

cout<<endl;

temp=temp->next;

5

}

cout<<"Akhir list"<<endl;

}

}

void hapus_simpul_akhir()

{

node *temp1, *temp2;



else

{

temp1 = awal_ptr;


{

delete temp1;

awal_ptr = NULL;

}

else

{


{

temp2 = temp1;


}

delete temp1;

temp2->next = NULL;

}

}

}

void hapus_simpul_awal()

{

node *temp;

temp = awal_ptr;


delete temp;

}

void main()

{

awal_ptr=NULL;

do

{

tampil_senarai();

cout<<"Menu Pilihan"<<endl;

cout<<"0. Keluar program"<<endl;

cout<<"1. Tambah simpul akhir"<<endl;

cout<<"2. Hapus simpul akhir"<<endl;

cout<<"3. Hapus simpul awal"<<endl;

cout<<"Pilihan >> ";cin>>pilih;

switch(pilih)

{

case 1: tambah_simpul_akhir();break;

case 2: hapus_simpul_akhir();break;

case 3: hapus_simpul_awal();break;

}

}while(pilih !=0);

}

6

BAB 2. LINKED LIST (LANJUTAN)

Menambah Simpul di Depan

Adalah menambahkan simpul baru yang dimasukkan diawal list. Proses penambahan

simpul diawal list diilustrasikan sebagai berikut:

1. List masih kosong maka awal_ptr bernilai NULL (awal_ptr=NULL)

awal_ptr

NULL

2. Masuk simpul baru, misalkan data A

A

awal_ptrbaru

3. Menambakan simpul diawal simpul A, misalkan simpul B

A

awal_ptr

B

baru

Barunext diisi dengan alamat dimana simpul data A berada, kemudian awal_ptr

ditunjukkan ke simpul baru yang diciptakan.

AB

awal_ptrbaru

Program :

if(awal_ptr == NULL)

{

awal_ptr=baru;

awal_ptr->next = NULL;

}

else

{

baru->next = awal_ptr;

awal_ptr = baru;

}

Menambah Simpul di Tengah

Proses penambahan di tengah berarti proses penyisipan data pada posisi tertentu. Oleh

karena itu, posisi penyisipan sangat diperlukan. Ada beberapa kondisi yang harus diperhatikan

ketika ingin melakukan penyisipandata, yaitu kondisi ketika linked list masih kosong, dan ketika

linked list sudah mempunyai data.

Proses penambahan data ketika linked list sudah mempunyai data. Ada 3 kondisi yang

terjadi ketika akan melakukan proses penyisipan pada linked list yang sudah mempunyai data

adalah :

1. Posisi penyisipan di luar dari jangkauan linked list (posisi kurang dari 1 atau melebihi banyak

data yang ada di linked list). Pada proses ini, jika terjadi posisi penyisipan kurang dari 1

maka proses yang dilakukan adalah proses penambahan data di awal, dan jika posisi diluar

(>) dari banyak data maka proses yang dilakukan adalah proses penambahan data di akhir.

2. Posisi penyisipan di dalam jangkauan linked list. Contoh kalau ingin menyisipkan data pada

posisi ke-3 (posisi_sisip=3).

7

A B C D

awal_ptr

E

baru

Posisi_sisi = 3

Langkah selanjutnya cari posisi elemen sebelum posisi sisip kemudian simpan dalam

suatu variabel dengan nama bantu.

A B C D

awal_ptr

E

baru

Posisi_sisi = 3bantu

Kemudian sambungkan field next dari Baru ke posisi next dari bantu

A B C D

awal_ptr

E

baru


Kemudian pindahkan field next dari bantu ke posisi data baru.

A B C D

awal_ptr

E

baru


Program: if(awal_ptr != NULL)

{

cout<<"Akan disisip setelah Data Ke ? : "; cin>>posisi_sisip;

bantu=awal_ptr;

baru =new node;

for(int i=1;i<posisi_sisip-1;i++)

{

if(bantu->next != NULL)

bantu=bantu->next;

else

break;

}

cout << "Masukkan Nama : "; cin >> baru->nama;

cout << "Masukkan Umur : "; cin >> baru->umur;

cout << "Masukkan tingggi : "; cin >> baru->tinggi;

baru->next=bantu->next;

bantu->next=baru;

}

8

else

{ cout<<"Belum ada data !! silahkan isi data dulu....";

getch();}

}

Menghapus Simpul di Tengah

Menghapus tengah sebuah simpul adalah menghilangkan simpul dari deret linked list.

Misalkan kita akan menghapus simpul pada posisi 3

A B C D

awal_ptr Posisi_sisi = 3

Tempatkan pointer bantu pada posisi sebelum simpul yang akan dihapus

A B C D

awal_ptr Posisi_sisi = 3bantu

Tempatkan pointer hapus sesuai dengan field next pada bantu

A B C D

awal_ptr Posisi_sisi = 3bantu hapus

Sambungkan field next pada bantu dengan field next pada hapus

A B C D

awal_ptr Posisi_sisi = 3bantu hapus

Langkah terakhir delete simpul hapus.

A B D

awal_ptr

Program: if(awal_ptr != NULL)

{

cout<<" Akan dihapus pada data ke : "; cin>>posisi_hapus;

banyakdata=1;

bantu=awal_ptr;

while(bantu->next != NULL)

{

bantu=bantu->next;

banyakdata++;

}

if((posisi_hapus<1)||(posisi_hapus>banyakdata))

{

cout<<"Belum ada data !! masukkan Data dula aja...\n";

}

else

{

bantu=awal_ptr;

poshapus=1;

while(poshapus<(posisi_hapus-1))

{

bantu=bantu->next;

poshapus++;

}

hapus=bantu->next;

bantu->next=hapus->next;

9

delete hapus;

}

}

else cout<<"Data Masih kosong, tidak bisa hapus data dari tengah! ";

getch();

}

Program lengkap:


#include <conio.h>

struct node

{ char nama[20];

int umur;

float tinggi;

node *next;

};

node *awal_ptr = NULL;

node *posisi; //digunakan untuk membaca sepanjang list

int option = 0;

void tambah_awal_list()

{

node *baru;

baru = new node;

cout << "Masukkan Nama : ";

cin >> baru->nama;

cout << "Masukkan Umur : ";

cin >> baru->umur;

cout << "Masukkan tingggi : ";

cin >> baru->tinggi;

baru->next = NULL;

if(awal_ptr == NULL)

{

awal_ptr=baru;

awal_ptr->next = NULL;

}

else

{

baru->next = awal_ptr;

awal_ptr = baru;

}

}

void menambah_node_di_akhir()

{ node *temp, *temp2; // Temporary pointers

// menciptakan node baru

temp = new node;


cin >> temp->nama;


cin >> temp->umur;


cin >> temp->tinggi;

temp->next = NULL;

// Set up link pada node


{ awal_ptr = temp;

posisi = awal_ptr;

}

else

{ temp2 = awal_ptr;

// node tidak NULL – list tidak kosong


{ temp2 = temp2->next;

10

// Memindahkan pada next link dalam rantai

}

temp2->next = temp;

}

}

void display_list()

{ node *temp;

temp = awal_ptr;

cout << endl;

if (temp == NULL)


else

{ while (temp != NULL)

{ // Menampilkan detail data

cout << "nama : " << temp->nama << " ";

cout << "umur : " << temp->umur << " ";

cout << "tinggi : " << temp->tinggi;

if (temp == posisi)

cout << " <<<< posisi node";

cout << endl;

temp = temp->next;

}

cout << "Akhir list!" << endl;

}

}

void hapus_awal_node()

{ node *temp;

temp = awal_ptr;


delete temp;

}

void hapus_akhir_node()

{ node *temp1, *temp2;



else

{ temp1 = awal_ptr;


{ delete temp1;

awal_ptr = NULL;

}

else

{ while (temp1->next != NULL)

{ temp2 = temp1;


}

delete temp1;

temp2->next = NULL;

}

}

}

void pindah_posisi_sebelumnya()

{ if (posisi->next == NULL)

cout << "Kamu berada pada akhir list." << endl;

else

posisi = posisi->next;

}

void pindah_posisi_berikutnya()

{ if (posisi == awal_ptr)

cout << "Kamu berada pada awal list" << endl;

else

{ node *previous; // deklarasi pointer

previous = awal_ptr;

while (previous->next != posisi)

11

{ previous = previous->next;

}

posisi = previous;

}

}

void tambah_tengah_list()

{

node *baru, *bantu;

int posisi_sisip;

if(awal_ptr != NULL)

{

cout<<"Akan disisip setelah Data Ke ? : "; cin>>posisi_sisip;

bantu=awal_ptr;

baru =new node;

for(int i=1;i<posisi_sisip-1;i++)

{

if(bantu->next != NULL)

bantu=bantu->next;

else

break;

}


cin >> baru->nama;


cin >> baru->umur;


cin >> baru->tinggi;

baru->next=bantu->next;

bantu->next=baru;

}

else

{ cout<<"Belum ada data !! silahkan isi data dulu....";

getch();}

}

void Hapus_tengah_list()

{

int banyakdata,posisi_hapus,poshapus;

node *hapus, *bantu;

if(awal_ptr != NULL)

{

cout<<" Akan dihapus pada data ke : "; cin>>posisi_hapus;

banyakdata=1;

bantu=awal_ptr;

while(bantu->next != NULL)

{

bantu=bantu->next;

banyakdata++;

}

if((posisi_hapus<1)||(posisi_hapus>banyakdata))

{

cout<<"Belum ada data !! masukkan Data dula aja...\n";

}

else

{

bantu=awal_ptr;

poshapus=1;

while(poshapus<(posisi_hapus-1))

{

bantu=bantu->next;

poshapus++;

}

hapus=bantu->next;

bantu->next=hapus->next;

delete hapus;

}

}

else cout<<"Data Masih kosong, tidak bisa hapus data dari tengah! ";

getch();

}

12

int main()

{ awal_ptr = NULL;

do

{

clrscr();

display_list();

cout << endl;

cout << "MENU PILIHAN : " << endl;

cout << "0. Keluar program." << endl;

cout << "1. Tambah awal list." << endl;

cout << "2. Tambah akhir list." << endl;

cout << "3. Tambah tengah list."<< endl;

cout << "4. Hapus awal list." << endl;

cout << "5. Hapus akhir list." << endl;

cout << "6. Hapus tengah list." << endl;

cout << "7. Pindah posisi pointer ke berikutnya." << endl;

cout << "8. Pindah posisi pointer ke sebelumnya." << endl;

cout << endl << " Pilihan >> ";

cin >> option;

switch (option)

{

case 1 : tambah_awal_list();break;

case 2 : menambah_node_di_akhir(); break;

case 3 : tambah_tengah_list();break;

case 4 : hapus_awal_node(); break;

case 5 : hapus_akhir_node(); break;

case 6 : Hapus_tengah_list();break;

case 7 : pindah_posisi_sebelumnya(); break;

case 8 : pindah_posisi_berikutnya();

}

}

while (option != 0);

}

13

BAB 3. DOUBLE LINKED LIST

Elemen-elemen dihubungkan dengan dua pointer dalam satu elemen. Struktur ini menyebabkan

list melintas baik ke depan maupun ke belakang. Masing-masing elemen pada double linked list

terdiri dari tiga bagian, disamping data dan pointer next, masing-masing elemen dilengkapi

dengan pointer prev yang menunjuk ke elemen sebelumnya. Double linked list dibentuk dengan

menyusun sejumlah elemen sehingga pointer next menunjuk ke elemen yang mengikutinya dan

pointer prev menunjuk ke elemen yang mendahuluinya. Untuk menunjukkan head dari double

linked list, maka pointer prev dari elemen pertama menunjuk NULL. Untuk menunjukkan tail

dari double linked list tersebut, maka pointer next dari elemen terakhir menunjuk NULL.

Susunan elemen yang dihubungkan dalam bentuk double linked list dapat dilihat pada Gambar di

bawah ini

data nextprev

Gambar 1. Sebuah simpul dengan menggunakan double linked list

Untuk melintas kembali melalui double linked list, kita gunakan pointer prev dari elemen yang

berurutan pada arah tail ke head. Double linked list mempunyai fleksibilitas yang lebih tinggi

daripada single linked list dalam perpindahan pada list. Bentuk ini sangat berguna ketika akan

meletakkan suatu elemen pada list dan dapat memilih dengan lebih bijaksana bagaimana

memindahkannya. Sebagai contoh, salah satu fleksibilitas dari double linked list adalah dalam

hal memindahkan elemen dari pada menggunakan single linked list.

ANULL B C D NULL

Definisi simpul

struct node

{ char nama[20];

int umur;

float tinggi;

node *prev;

node *next;

};

Setelah node dibuat, buat variabel baru yang bertipe pointer dari node yang berguna sebagai

kepala (head) dan ekor (tail) linked list. Head selalu menunjuk pada simpul pertama, sedangkan tail

selalu menunjuk pada simpul terakhir. node *head=NULL, *tail=NULL;

Operasi pada Double Linked List

1. Membuat Simpul Baru

Untuk membuat node baru digunakan keyword new. Perintah ini digunakan untuk

mempersiapkan sebuah node dengan alokasi memorinya. Selanjutnya medan informasi pada node

tersebut diisi dengan data tertentu. Terakhir pointer prev dan next diisi dengan NULL.

Fungsi membuat simpul baru

14

void buat_baru()

{

baru = new(node);

cout<<"input nama : ";cin>>baru->nama;

cout<<"input umur : ";cin>>baru->umur;

cout<<"input tinggi : ";cin>>baru->tinggi;

baru->prev=NULL;

baru->next=NULL;

}

2. Menambah Simpul di Awal

Penambahan node baru yang akan diletakkan di node paling depan, perlu diperhatikan saat

pertama kali (data masih kosong), maka saat penambahan data dilakukan head/tail ditunjukkan

ke node baru tersebut. Sedangkan jika tidak kosong, data akan ditambahkan didepan head,

kemudian node baru akan berubah menjadi head.

B nextprev

head

NULL

tail

NULL NULL

head tailbaru

B nextprevNULL NULL

head tail

A nextprevNULL NULL

baru

B nextprev NULL

head tail

A nextprevNULL

baru

B nextprev NULL

head tail

A nextprevNULL

baru

Fungsi menambah simpul di awal void tambah_depan()

{

buat_baru();

if(head==NULL)

{

head=baru;

tail=baru;

}

else

{

baru->next=head;

head->prev=baru;

head=baru;

}

cout<<endl<<endl;

tampil();

}

3. Menambah Simpul di Belakang

Penambahan node di belakang akan selalu dikaitkan dengan tail dan kemudian node baru tersebut

akan menjadi tail.

15

B nextprev

head

NULL

tail

NULL NULL

head tailbaru

B nextprevNULL NULL

head tail

A nextprevNULL NULL

baru

B nextprevNULL

head tail

A nextprev NULL

baru

B nextprevNULL

head tail

A nextprev NULL

baru

Fungsi menambah simpul di belakang void tambah_belakang()

{

buat_baru();

if(head==NULL)

{

head=baru;

tail=baru;

}

else

{

tail->next=baru;

baru->prev=tail;

tail=baru;

}

cout<<endl<<endl;

tampil();

}

4. Menghapus Simpul di Awal

Menghapus 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. Kemudian head harus ditunjukkan ke node sesudahnya

terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan menjadi head baru.

Setelah itu barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete.

Jika head masih NULL maka berarti data masih kosong!

ANULL B C D NULL

head tailhapus

BNULL C D NULL

tailhead

Fungsi menghapus simpul didepan void hapus_depan()

{

if (head==NULL)

cout<<"Kosong";

16

else if (head->next==NULL)

{

hapus=head;

head=NULL;

tail=NULL;

delete hapus;

}

else

{

hapus=head;

head=hapus->next;

head->prev=NULL;

delete hapus;

}

cout<<endl<<endl;

tampil();

}

Menghapus Simpul di Belakang

Menghapus simpul di belakang dibutuhkan satu buah pointer bantuan, misal pointer hapus, tidak

perlu melakukan perulangan untuk mencari node terakhir seperti pada single linked list. Pointer

hapus hanya perlu menunjuk pada pointer tail saja. Sebelum penghapusan node, tail harus

dipindahkan pada node sebelumnya. Selanjutnya pointer next dari tail diberi nilai NULL.

Kemudian langkah terakhir simpul hapus di-delete

ANULL B C D NULL

head tail hapus

ANULL B C

head tail

Fungsi menghapus simpul dibelakang

void hapus_belakang()

{

if (head==NULL)

cout<<"Kosong";


{

hapus=head;

head=NULL;

tail=NULL;

delete hapus;

}

else

{

hapus=tail;

tail=hapus->prev;

tail->next=NULL;

delete hapus;

}

cout<<endl<<endl;

tampil();

}

17


#include <conio.h>

#include <stdio.h>

int pil;

void pilih();

void buat_baru();

void tambah_belakang();

void tambah_depan();

void hapus_belakang();

void hapus_depan();

void tampil();

struct node

{

char nama [20];

int umur;

float tinggi;

node *prev, *next;

};

node *baru, *head=NULL, *tail=NULL,*hapus,*bantu;

void main()

{

do

{

clrscr();

cout<<"MENU DOUBLE LINKEDLIST"<<endl;

cout<<"1. Tambah Depan"<<endl;

cout<<"2. Tambah Belakang"<<endl;

cout<<"3. Hapus Depan"<<endl;

cout<<"4. Hapus Belakang"<<endl;

cout<<"5. Tampilkan"<<endl;

cout<<"6. Selesai"<<endl;

cout<<"Pilihan Anda : ";

cin>>pil;

pilih();

} while(pil!=6);

}

void pilih()

{

if(pil==1)

tambah_depan();

else if(pil==2)

tambah_belakang();

else if(pil==3)

hapus_depan();

else if(pil==4)

hapus_belakang();

else if(pil==5)

tampil();

else

cout<<"selesai";

}

void buat_baru()

{

baru = new(node);

cout<<"input nama : ";cin>>baru->nama;

cout<<"input umur : ";cin>>baru->umur;

cout<<"input tinggi : ";cin>>baru->tinggi;

baru->prev=NULL;

baru->next=NULL;

}

void tambah_belakang()

{

buat_baru();

if(head==NULL)

18

{

head=baru;

tail=baru;

}

else

{

tail->next=baru;

baru->prev=tail;

tail=baru;

}

cout<<endl<<endl;

tampil();

}

void tambah_depan()

{

buat_baru();

if(head==NULL)

{

head=baru;

tail=baru;

}

else

{

baru->next=head;

head->prev=baru;

head=baru;

}

cout<<endl<<endl;

tampil();

}

void hapus_depan()

{

if (head==NULL)

cout<<"Kosong";


{

hapus=head;

head=NULL;

tail=NULL;

delete hapus;

}

else

{

hapus=head;

head=hapus->next;

head->prev=NULL;

delete hapus;

}

cout<<endl<<endl;

tampil();

}

void hapus_belakang()

{

if (head==NULL)

cout<<"Kosong";


{

hapus=head;

head=NULL;

tail=NULL;

delete hapus;

}

else

{

hapus=tail;

tail=hapus->prev;

tail->next=NULL;

delete hapus;

19

}

cout<<endl<<endl;

tampil();

}

void tampil()

{

if (head==NULL)

cout<<"Kosong";

else

{

bantu=head;

while(bantu!=NULL)

{

cout<<" nama : "<<bantu->nama;

cout<<" umur : "<<bantu->umur;

cout<<" tinggi : "<<bantu->tinggi<<endl;

bantu=bantu->next;

}

}

getch();

}

20

BAB 4. STACK (TUMPUKAN)

Stack dapat diartikan sebagai tumpukan dari benda atau data yang seolah-olah diletakkan di atas

data yang lain dimana data yang pertama kali masuk akan terakhir. Secara sederhana sebuah

stack bisa digambarkan sebagai tumpukan buku yang disimpan dengan cara ditumpuk keatas.

Dimana buku yang pertama kali disimpan atau ditumpuk ada di paling bawah dan yang

selanjutnya ditumpuk diatasnya. Dan ketika kita melakukan pengambilan buku ototmatis buku

yang terkahir ditumpuk atau disimpan terakhir akan mejadi yang pertama diambil, istilah ini

kemudian disebut FILO (First In Last Out) dan bertambah atau berkurangnya data melalui satu

ujung yang sama yaitu ujung atas tumpukan (Top of Stack).

Ada 2 operasi dasar dari stack yang dapat dilakukan, yaitu :

1. Operasi push yaitu operasi menambahkan elemen pada urutan terakhir (paling atas).

2. Operasi pop yaitu operasi mengambil sebuah elemen data pada urutan terakhir dan

menghapus elemen tersebut dari stack.

Top 20

Top 15

15 Top 15

Top 10

10

10

10

Top = 0 push(10) push(15) push(20) pop(20)

kosong

Selain operasi dasar stack (push dan pop), ada lagi operasi lain yang dapat terjadi dalam

stack yaitu :

1. Proses deklarasi yaitu proses pendeklarasian stack.

2. Proses inisialisasi yaitu proses pembuatan stack kosong, biasanya dengan pemberian nilai

untuk top.

3. Proses cek kosong yaitu proses pemeriksaan apakah stack dalam keadaan kosong.

4. Proses cek penuh yaitu proses pemeriksaan apakah stack telah penuh.

Operasi-operasi stack secara lengkap adalah sebagai berikut :

1. Pendeklarasian stack dengan array Proses pendeklarasian stack adalah proses pembuatan struktur stack dalam memori.

Karena stack dapat direpresentasikan dalam 2 cara, maka pendeklarasian stack pun ada 2

yaitu:

Suatu stack memiliki beberapa bagian yaitu

a. top yang menunjuk posisi data terakhir (top)

b. elemen yang berisi data yang ada dalam stack. Bagian ini lah yang berbentuk array.

Deklarasi stack dengan array: struct stack

{

int elemen[10]; //elemen

int top;

};

2. Inisialisasi

Inisialisasi stack adalah proses pembuatan suatu stack kosong. Proses inisialisasi

untuk stack yang menggunakan array adalah dengan mengisi nilai field top dengan 0 (nol)

jika elemen pertama diawali dengan nomor 1. Kalau elemen pertama array dimulai dengan 0

maka top diisi dengan nilai -1.

p->top=-1

3. Operasi Cek Kosong Stack

Operasi ini digunakan untuk memeriksa apakah stack dalam keadaan kosong. Operasi ini

penting dilakukan dalam proses pop. Ketika suatu stack dalam keadaan kosong, maka proses

21

pop tidak bisa dilakukan. Operasi ini dilakukan hanya dengan memeriksa field top. Jika top

top bernilai -1, maka berarti stack dalam keadaan empty (kosong). if (p->top==-1)

{

cout<<"STACK kosong";

return -1;

}

4. Operasi Cek Penuh

Operasi ini berguna untuk memeriksa keadaan stack apakah sudah penuh atau belum.

Operasi ini akan memberikan nilai true (1) jika field top sama dengan size-1.

if(p->top==size-1)

cout<<"STACK penuh ";

5. Operasi Push

Operasi ini berguna untuk menambah suatu elemen data baru pada stack dan disimpan pada

posisi top yang akan mengakibatkan posisi top akan berubah. Langkah operasi ini adalah :

a. Periksa apakah stack penuh. Jika tidak penuh maka proses push dilaksanakan dan

jika stack penuh, maka proses push digagalkan.

b. Proses push-nya sendiri adalah dengan menambah field top dengan 1, kemudian

elemen pada posisi top diisi dengan elemen data baru. if(p->top==size-1)


else

p->elemen[++p->top]=value;

6. Operasi Pop

Operasi ini berguna untuk mengambil elemen terakhir (top) dan kemudian menghapus

elemen tersebut sehingga posisi top akan berpindah. Langkah operasi pop pada stack yang

menggunakan array adalah terlebih dahulu memeriksa apakah stack sedang keadaan kosong,

jika tidak kosong maka data diambil pada posisi yang ditunjuk oleh posisi top, kemudian

posisi top – 1.

if (p->top==-1)

{


return -1;

}

else

return p->elemen[p->top--];

Program Lengkap:

#include<iostream.h>

#include<stdio.h>

#include<conio.h>

#define size 50

struct stack

{

int elemen[size];

int top;

};

typedef struct stack STACK;

void push(STACK *p,int value) // operasi push

{

if(p->top==size-1)


else

p->elemen[++p->top]=value;

}

int pop(STACK *p) //operasi pop

{

22

if (p->top==-1)

{


return -1;

}

else

return p->elemen[p->top--];

}

void display (STACK *p) //menampilkan stack

{

int i;

if(p->top==-1)

cout<<"\n STACK kosong\n";

else

cout<<"\nIsi STACK adalah : \n";

for (i=p->top;i>=0; --i)

cout<<p->elemen[i]<<"\n";

}

void main()

{

STACK s ;

int x,c,i;

s.top=-1;

do

{

cout<<"MENU PILIHAN";

cout<<"\n1: Operasi PUSH\n";

cout<<"2: Operasi POP\n";

cout<<"3: Tampilkan Stack\n";

cout<<"4: Hapus Stasck\n";

cout<<"5: Keluar\n";

cout<<"\n\n Pilihan anda : ";cin>>c;

switch(c)

{

case 1:

cout<<"\nMasukkan Elemen Stack: ";cin>>x;

push (&s,x);

display(&s);

break;

case 2:

x=pop(&s);

if(x!=-1)

cout<<"\nMenghapus Element = "<<x;

break;

case 3:

display(&s);

break;

case 4:

if(s.top==-1)

cout<<endl<<"STACK kosong";

else

cout<<endl<<"STACK dihapus"<<endl;

//Menghapus STACK

for (i=s.top;i>=0; --i)

cout<<"Elemen yang dihapus adalah :

"<<pop(&s)<<endl;

s.top=-1;

}

getch();clrscr();

}while(c!=5);

}

23

Stack dengan animasi


#include <conio.h>

#include <stdlib.h>

int top,i;

char key,temp,e;

char stack[10];

void delay();

void pushanim()

{

for(i=0;i<=17; i++)

{

gotoxy(22+i,7);cout<<" ";

gotoxy(23+i,7);cout<<temp; delay();

}

for(i=1;i<=(14-top);i++)

{

delay();

gotoxy(40,6+i); cout<<" ";

gotoxy(40,7+i); cout<<temp;

}

}

void popanim(char temp)

{

for(i=1;i<=(14-top);i++)

{

delay();

gotoxy(40,22-i-top); cout<<" ";

gotoxy(40,21-i-top); cout<<temp;

}

for(i=1;i<=19;i++)

{

delay();

gotoxy(38+i,7); cout<<" ";

gotoxy(39+i,7); cout<<temp; delay();

}

gotoxy(58,7);cout<<" ";

}

void push(char e)

{

top=top+1;

stack[top]=e;

pushanim();

}

void pop(char e)

{

if(top !=0)

{

e=stack[top];

popanim(e);

top=top-1;

}

else

{

gotoxy(1,7); cout<<"stack telah kosong"<<endl;

gotoxy(1,7);

}

}

void main()

{

clrscr();

cout<<"Animasi Stack"<<endl;

cout<<"1.Push"<<endl;

cout<<"2.Pop"<<endl;

cout<<"3.Keluar"<<endl;

24

gotoxy(59,6); cout<<"=";

gotoxy(59,8); cout<<"=";

gotoxy(37,9); cout<<"|| ||";

for(i=1;i<=11;i++)

{

gotoxy(38,10+i);

if(i==11)

cout<<"|___|";

else

cout<<"| |";

}

top=0;

do

{

gotoxy(1,5);

cout<<"masukkan pilihan anda[1/2/3] : ";

key=getche();

if(int(key)==27 || key=='3')

break;

else if(key=='1')

{

if(top != 10)

{

gotoxy(1,7); cout<<"masukkan suatu huruf : ";

cin>>temp;

push(temp);

gotoxy(1,7); cout<<" ";

}

else

{

gotoxy(1,7); cout<<"stack penuh";

getch();

gotoxy(1,7); cout<<" ";

}

}

else if(key=='2')

pop(temp);

}while(1);

getch();

}

void delay()

{

for(int y=1;y<10000;y++)

for(int x=1;x<10000;x++)

for(int p=1;p<10000;p++)

cout<<"";

}

25

BAB 5. STACK DENGAN POINTER

Top

Top = NULL

23Top 25Top

23

22Top

25

23

25Top

23

Posis Awal Push(23) Push(25) Push(22) Pop(22)

Operasi-operasi stack secara lengkap adalah sebagai berikut :

7. Pendeklarasian stack dengan pointer Proses pendeklarasian stack adalah proses pembuatan struktur stack dalam memori.

Pendeklrasian dengan menggunakan pointer dibuat dua buah struktur yaitu data simpul yang

berupa data dan pointer yang menunjuk ke simpul selanjutnya dan yang kedua struktur stack

yang digunakan untuk menyimpan jumlah stack dan penunjuk posisi top dari stack:

Deklarasi Simpul/node : struct node

{

int bil;

struct node *next;

};

Deklarasi stack dengan array: struct stack

{

int jumlah;

struct node *top;

};

8. Inisialisasi

Inisialisasi stack adalah proses pembuatan suatu stack kosong. Proses inisialisasi

untuk stack yang menggunakan pointer adalah dengan mengisi nilai field top dengan NULL.

stack.top=NULL;

9. Operasi Cek Kosong Stack

Operasi ini digunakan untuk memeriksa apakah stack dalam keadaan kosong. Operasi ini

penting dilakukan dalam proses pop. Ketika suatu stack dalam keadaan kosong, maka proses

pop tidak bisa dilakukan. Operasi ini dilakukan hanya dengan memeriksa jumlah elemen

stack yang terbentuk. Jika jumlah bernilai 0, maka berarti stack dalam keadaan empty

(kosong). int cekKosong(stack *stack)

{

if(stack->jumlah==0)

return 1;

else

return 0;

}

26

10. Operasi Cek Penuh

Operasi ini berguna untuk memeriksa keadaan stack apakah sudah penuh atau belum.

Operasi ini akan memberikan nilai true (1) jika field top sama dengan size. int cekPenuh(stack *stack)

{

if(stack->jumlah==size)

return 1;

else

return 0;

}

11. Operasi Push

Operasi ini berguna untuk menambah suatu elemen data baru pada stack dan disimpan pada

posisi top yang akan mengakibatkan posisi top akan berubah. Langkah operasi ini adalah :

c. Periksa apakah stack penuh. Jika tidak penuh maka proses push dilaksanakan dan jika

stack penuh, maka proses push digagalkan.

d. Proses push-nya sendiri dilakukan dengan menyambungkan simpul baru->next sama

dengan stack->top, kemudian mengubah posisi top stack pada simpul baru dengan

stack->top sama dengan baru, kemudian menambah jumlah simpul sebesar 1 dengan

perintah stack->jumlah++. void Push(stack *stack)

{

node *baru;

if (cekPenuh(stack))

{

cout<<"stack full";

getch();

}

else

{

baru=new(node);

cout<<"\nmasukkan nilai yang ingin dipush ke stack: ";

cin>>baru->bil;

baru->next=stack->top;

stack->top=baru;

stack->jumlah++;

cout<<"\nproses push sukses";

getch();

}

}

12. Operasi Pop

Operasi ini berguna untuk mengambil elemen terakhir (top) dan kemudian menghapus

elemen tersebut sehingga posisi top akan berpindah. Langkah operasi pop pada stack yang

menggunakan pointer adalah terlebih dahulu memeriksa apakah stack sedang keadaan

kosong, jika tidak kosong maka:

a. Gunakan variabel bantu hapusPtr untuk membaca simpul top stack

b. Pindahkan posisi top stack pada posisi sebelumnya

c. Kurangi jumlah simpul pada stack sebasar 1

d. Hapus simpul hapusPrt

void Pop(stack *stack)

{

node *hapusPtr;

hapusPtr=stack->top;

if (cekKosong(stack))

{

cout<<"Stack Kosong";getch();

}

else

{

stack->top=stack->top->next;

stack->jumlah--;

delete hapusPtr;

cout<<"\nproses pop berhasil\n";

getch();

27

}

}

Program Lengkap:

#include<iostream.h>

#include<conio.h>

#define size 5

struct node

{

int bil;

struct node *next;

};

struct stack

{

int jumlah;

struct node *top;

};

int cekPenuh(stack *stack)

{

if(stack->jumlah==size)

return 1;

else

return 0;

}

int cekKosong(stack *stack)

{

if(stack->jumlah==0)

return 1;

else

return 0;

}

void Push(stack *stack)

{

node *baru;

if (cekPenuh(stack))

{

cout<<"stack full";

getch();

}

else

{

baru=new(node);

cout<<"\nmasukkan nilai yang ingin dipush ke stack: ";

cin>>baru->bil;

baru->next=stack->top;

stack->top=baru;

stack->jumlah++;

//cout<<"\nproses push sukses";

//getch();

}

}

void cetak(stack *stack)

{

node *bacaPtr;

bacaPtr=stack->top;

if(cekKosong(stack))

{

cout<<"\nstack kosong";

getch();

}

else

{

clrscr();

28

cout<<"\nTOP\n";

cout<<"---------\n";

while(bacaPtr!=NULL)

{

cout<<bacaPtr->bil<<endl;

cout<<"---------"<<endl;

bacaPtr=bacaPtr->next;

}

getch();

}

}

void Pop(stack *stack)

{

// int dataTop;

node *hapusPtr;

hapusPtr=stack->top;

if (cekKosong(stack))

{

cout<<"Stack Kosong";getch();

}

else

{

// dataTop=stack->top->bil;


stack->jumlah--;

delete hapusPtr;

cout<<"\nproses pop berhasil\n";

getch();

}

}

void Top(stack *stack)

{

int dataTop;

if(cekKosong(stack))

{

cout<<"\ntop = NULL\n";

getch();

}

else

{

dataTop=stack->top->bil;

cout<<"\ntop = "<<dataTop<<endl;

getch();

}

}

void hapus(stack *stack)

{

node *bantuHapus;

while(stack->top!=NULL)

{

bantuHapus=stack->top;


delete bantuHapus;

}

stack->jumlah=0;

}

void main()

{

stack stack;

stack.jumlah=0;

stack.top=NULL;

char pilih;

do

{

clrscr();

cout<<"MENU STACK"<<endl;

cout<<"[1]. Kosongkan Stack"<<endl;

29

cout<<"[2]. Push"<<endl;

cout<<"[3]. Pop"<<endl;

cout<<"[4]. Lihat Top Stack"<<endl;

cout<<"[5]. Tampilkan stack"<<endl;

cout<<"[6]. Keluar\n"<<endl;

cout<<"\npilihan: ";

cin>>pilih;

if(pilih=='1')

hapus(&stack);

if(pilih=='2')

{ Push(&stack);

cetak(&stack);}

if(pilih=='3')

{ Pop(&stack);

cetak(&stack);}

if(pilih=='4')

Top(&stack);

if(pilih=='5')

cetak(&stack);

}while(pilih!='6');

}

30

BAB 6. PENGURUTAN (SORTING)

Pengurutan didefinisikan sebagai suatu penyusunan ulang (pengorganisasian) himpunan obyek

dengan aturan tertentu. Jenis pengurutan:

1. Urut naik (ascending) yaitu jika data disusun mulai dari yang paling kecil hingga yang paling

besar.

2. Urut turun (descending) yaitu jika data disusun mulai dari yang paling besar hingga yang paling

kecil.

Keuntungan dari data yang sudah terurut adalah kemudahan dalam mencari data tertentu dan

kemudahan dalam melakukan perbaikan, disisipi data baru, dihapus serta digabungkan.

PENGURUTAN DENGAN PENYISIPAN LANGSUNG

Algoritma pengurutan langsung (ascending):

1. Mulai dari n=1

2. Bilangan ke-n diambil, cari posisi penyisipan yang sesuai dengan kriteria

3. Geser bilangan-bilangan mulai posisi penyisipan hingga bilangan ke-n

4. Sisipkan bilangan di posisi yang sesuai

5. Tambahkan n dengan 1

6. Ulangi langkah ke-2 sampai 5 hingga bernilai cacah bilangan

Algoritma:

For I 1 to n

X larik[i]

J i-1

While (x < larik[j])

Larik[j+1] larik[j]

J j-1

Endwhile

Larik[j+1] x

Endfor

Angka awal 10 5 12 0 32 56 34 6 11 99

proses 1 5 10 12 0 32 56 34 6 11 99

proses 2 5 10 12 0 32 56 34 6 11 99

proses 3 0 5 12 10 32 56 34 6 11 99

proses 4 0 5 10 12 32 56 34 6 11 99

proses 5 0 5 10 12 32 34 56 6 11 99

proses 6 0 5 6 10 12 32 34 56 11 99

proses 7 0 5 6 10 12 32 34 56 11 99

proses 8 0 5 6 10 11 12 32 34 56 99

terurut 0 5 6 10 11 12 32 34 56 99

Program

int j,x;

for (int i=1;i<10;i++)

{

x=larik[i];

j=i-1;

while (x<larik[j])

{

31

larik[j+1]=larik[j];

j--;

}

larik[j+1]=x;

}

PENGURUTAN DENGAN PEMILIHAN LANGSUNG

Cara kerja metode ini adalah dengan memilih data yang paling kecil (ascending) atau paling besar

(descending) kemudian meletakkannya pada posisi paling kiri dengan langkah-langkah penukaran.

Misalkan kita akan melakukan pengurutan ascending, maka pertama kali kita tunjuk data yang pertama.

Kemudian kita akan mencari data terkecil disebelah kanan data yang pertama tadi. Jika ada, maka data

yang terkecil kita tukar dengan data yang pertama, sehingga data pertama pasti memuat data yang

paling kecil. Selanjutnya kita lakukan hal yang sama untuk data ke-2 dan seterusnya.

Langkah-langkah :

1. Kerjakan langkah 2-4 untuk i=1 hinggai i=n-1

2. Tentukan lokasi = i

3. Kerjakan langkah4-5 untuk j=i+1 hingga j=n

4. Jika larik[lokasi] > larik[j], maka lokasi = j

5. Tukarkan larik[lokasi] dengan larik[i]

Algoritma:

For i 0 to n

Lokasi = i

For j=i+1 to n

If larik[lokasi] > larik[j]

Lokasi j

Endif

Endfor

//penukaran

Tampung larik[lokasi]

Larik[lokasi] = larik[i]

Larik[i] = tampung

Endfor

Angka awal

10 5 12 0 32 56 34 6 11 99

proses 1 0 10 12 5 32 56 34 6 11 99

proses 2 0 5 12 10 32 56 34 6 11 99

proses 3 0 5 6 10 32 56 34 12 11 99

proses 4 0 5 6 10 32 56 34 12 11 99

proses 5 0 5 6 10 11 56 34 12 32 99

proses 6 0 5 6 10 11 12 34 56 32 99

proses 7 0 5 6 10 11 12 32 56 34 99

proses 8 0 5 6 10 11 12 32 34 56 99

terurut 0 5 6 10 11 12 33 34 56 99

Program

int lokasi,temp;

for (int i=0;i<10;i++)

{

lokasi = i;

for(int j=i+1;j<10;j++)

{

if (larik[lokasi] > larik[j])

32

lokasi=j;

}

temp=larik[lokasi];

larik[lokasi]=larik[i];

larik[i]=temp;

}

PENGURUTAN DENGAN METODE GELEMBUNG (BUBLE SORT)

Metode ini cukup mudah dipelajari, tetapi metode ini sangat tidak efisien karena melibatkan langkah-

langkah perbandingan dan penukaran yang berjumlah sangat banyak. Ada dua cara yang dapat

dilakukan untuk mengimplementasikan metode gelembung. Pertama kita letakkan data terbesar

disebalah kanan, kemudian berturut-turut data tersebesar selanjutnya disebelah kirinya. Kedua, kita

letakkan data paling kecil disebelah kiri, kemudian kita letakkan data terkecil selanjutnya disebelah

kanannya. Kita akan membahas cara yang kedua :

Algoritma:

1. Kerjakan langkah untuk i=1 hingga n

2. Kerjakan langkah untuk j=n hingga j=1

3. Jika larik[j-1] > larik[j] maka tukarkan larik[j-1] dan larik[j]

For i=1 to n

For j= n to 0 step -1

If larik[j-1] > larik[j]

Temp larik[j]

Larik[j] larik[j-1]

Larik[j-1] temp

PROGRAM int temp;

for(int i=1;i<10;i++)

{

for(int j=9;j>=0;j--)

{

if(larik[j-1]>larik[j])

{

temp=larik[j];

larik[j]=larik[j-1];

larik[j-1]=temp;

}

}

}

Latihan :

Buat program lengkap

Program dalam fungsi

33

PENCARIAN (SEARCHING) 1. Pencarian Berurutan (Sequential Searching)

Pencarian Berurutan (Sequential Searching) merupakan metode yang paling mudah, tetapi juga paling tidak efisien. Metode ini berjalan lebih lambat dibandingkan metode-metode lainnya, tetapi metode ini merupakan metode yang paling mungkin diterapkan pada larik yang belum terurutkan. ALGORITMA

Ketemu false

I 0

While ((i<n) OR (Not Ketemu))

If data = larik[i]

Ketemu true

Posisi i

Endif

I=i+1

Endwhile

PROGRAM bool ketemu;

i=0;

ketemu=0;

while(i<10 || !ketemu)

{

if (cari==larik[i])

{

ketemu=1;

posisi=i;

}

i++;

}

2. Pencarian pada Larik Terurut Proses pencarian dilakukan dengan membandingkan elemen pertama, jika larik terurut naik (ascending), maka pencarian akan diterukan sepanjang data yang dicari masih lebih kecil dari elemen yang ada pada larik. Jika elemen larik sudah lebih besar maka pencarian bisa dihentikan, karena pasti data yang dicari tidak ada. ALGORITMA

Ketemu false

I 0

Do

If data = larik[i]

Ketemu true

Posisi i

Endif

I=i+1

While ((i<n) OR (Not Ketemu) OR (data < Larik[i])

PROGRAM

bool ketemu;

i=0;

ketemu=0;

do

{

if (cari==larik[i])

{

ketemu=1;

posisi=i;

}

i++;

}while((i<10) || (!ketemu) || (cari<larik[i]));

34

3. Pencarian Biner Metode pencarian biner hanya dapat digunakan pada larik yang sudah terurut. Cara kerja metode pencarian binner sebagai berikut:

1 5 6 10 11 12 32 34 56 99

Misalkan kita akan mencari posisi dari 56. Pertama larik diatas kita bagi menjadi 2 sub larik yaitu :

1 5 6 10 11

12 32 34 56 99

Sub larik 1 Sub larik 2 Kemudian jika data 56 dibandingkan dengan elemen terakhir pada sub larik 1 (yang bernilai 11). Jika data tersebut (56) lebih kecil dari elemen terakhir pada sub larik 1 (11), maka data akan dicari di sublarik 1. Ternyata tidak, maka data akan dicari di sub larik 2 dan sub larik 1 tidak perlu dihiraukan lagi. Proses diatas diulang lagi yaitu sub larik 2 dibagi dua lagi, sehingga menghasilkan sub larik sbb:

12 32 34

56 99

Sub larik 2.1 sub larik 2.2 Kita bandingkan data (56) dengan elemen terakhir sub larik 2.1 (yaitu 34). Ternyata data 56 Lebih besar dari elemen terakhir sub larik 2.1 (34), maka data yang akan dicari ada disub larik 2.2. Terakhir sub larik 2.2 perlu dipecah lagi hasilnya sbb:

56

99

Sub larik 2.2.1 Sub larik 2.2.2 Demikian dengan 4 interasi kita sudah dapat menemukan data yang kita cari. ALGORITMA

Ketemu false

Bawah 0

Atas n

While ((Bawah<=Atas) OR (Not Ketemu))

Tengah (Atas + Bawah) div 2

If (data < larik[tengah]

Atas = tengah -1

Else if (data > larik[tengah]

Bawah = tengah + 1

Else if (data = larik[tengah])

Ketemu = true

Posisi = tengah

Bawah = Atas +1

Endif

endwhile

PROGRAM

bool ketemu;

int atas, tengah, bawah;

ketemu=0; bawah=0; atas=10;

while((bawah<atas) || !ketemu)

{

tengah=(atas+bawah)/2;

if(cari < larik[tengah])

atas=tengah-1;

else if (cari > larik[tengah])

bawah=tengah+1;

else if (cari == larik[tengah])

{

ketemu=1;

posisi=tengah;

bawah=atas+1;

}

}

35

BAB 8. TREE (POHON) Struktur pada tree (pohon) tidak linear seperti pada struktur linked list, stack, dan queue. Setiap node pada tree mempunyai tingkatan, yaitu orang tua (parent) dan anak (child). Struktur ini sebenarnya merupakan bentuk khusus dari struktur tree yang lebih umum, setiap orang tua hanya memiliki dua anak sehingga disebut pohon biner (binary tree), yaitu anak kiri dan anak kanan. ISTILAH DASAR Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree dapat didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut root dan node, disebut sub tree/sub pohon atau cabang. Sehingga secara sederhana pohon bisa didefinisikan sebagai kumpulan elemen yang salah satu elemennya disebut dengan akar (root) dan elemen yang lainnya (simpul), terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu dengan yang lainnya. Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

A

C

D H

B

G J

Keterangan : ·Left Child : B, D, H, ... ·Right Child : C, G, J, … Jenis Binary Tree Full Binary Tree Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap sub tree harus mempunyai panjang path yang sama.

A

C

D E

B

F G

Complete Binary Tree Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

A

C

D E

B

Skewed Binary Tree Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

36

A

D

B

Operasi Binary Tree 1. Deklarasi Tree

Tree tersusun oleh node-node, maka yang perlu kita deklarasikan adalah komponen node itu sendiri. Dalam contoh dibawah, akan kita namai Node. Sebelumnya perlu kita lihat bahwa untuk mewujudkan implementasi node ke dalam bahasa pemrograman, diperlukan sebuah struktur yang memiliki susunan berikut ini:

struct Node

{

int data;

Node *kiri;

Node *kanan;

};

2. Inisialisasi Tree

Saat pertama membuat sebuah pohon biner, asumsi awal adalah pohon itu belum bertumbuh, belum

memiliki node sama sekali, sehingga masih kosong. Oleh karena itu perlu kita tambahkan kode berikut

pada baris awal fungsi Main:

Node *pohon;

pohon = NULL;

3. Menambah Node pada Tree

Karena pohon yang kita buat merupakan sebuah pohon biner, maka untuk menambahkan sebuah node, secara otomatis penambahan tersebut mengikuti aturan penambahan node pada pohon biner: 1. Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon. 2. Jika pohon tidak kosong, maka dimulai dari node akar, dilakukan proses pengecekan berikut:

a. Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

b. Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan node yang sedang dicek. Seandainya kanan node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

Proses penambahan ini diimplementasikan secara rekursif pada fungsi berikut: 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;

cout<<"Data bertambah!";

getch();

}

else

if(databaru < (*root)->data)

tambah(&(*root)->kiri,databaru);

else

if(databaru > (*root)->data)

tambah(&(*root)->kanan,databaru);

else

if(databaru == (*root)->data)

37

{ cout<<"Data sudah ada!";

getch();

}

}

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

4. Membaca dan Menampilkan data pada Tree/Traverse PreOrder : cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child. Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan: 1. Cetak isi (data) node yang sedang dikunjungi 2. Kunjungi kiri node tersebut,

a. Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut. b. Jika kiri kosong (NULL), lanjut ke langkah ketiga.

3. Kunjungi kanan node tersebut, a. Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan

tersebut. b. Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node

yang dikunjungi sebelumnya. void preOrder(Node *root)

{

if(root != NULL)

{

cout<<root->data<<" ";

preOrder(root->kiri);

preOrder(root->kanan);

}

}

InOrder : kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right Child. 1. Kunjungi kiri node tersebut,

a. Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut. b. Jika kiri kosong (NULL), lanjut ke langkah kedua.

2. Cetak isi (data) node yang sedang dikunjungi 3. Kunjungi kanan node tersebut,

a. Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

b. 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);


inOrder(root->kanan);

}

}

PostOrder : kunjungi Left Child, kunjungi Right Child, cetak isi node yang dikunjungi. 1. Kunjungi kiri node tersebut,

a. Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut. b. Jika kiri kosong (NULL), lanjut ke langkah kedua.

2. Kunjungi kanan node tersebut, a. Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan

tersebut. b. 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);

38


}

}

Program Lengkap #include <stdio.h>

#include <conio.h>


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;

cout<<"Data bertambah!";

getch();

}

else

if(databaru < (*root)->data)

tambah(&(*root)->kiri,databaru);

else

if(databaru > (*root)->data)

tambah(&(*root)->kanan,databaru);

else

if(databaru == (*root)->data)

{ cout<<"Data sudah ada!";

getch();

}

}

void preOrder(Node *root)

{

if(root != NULL)

{


preOrder(root->kiri);

preOrder(root->kanan);

}

}

void inOrder(Node *root)

{

if(root != NULL)

{

inOrder(root->kiri);


inOrder(root->kanan);

}

}

void postOrder(Node *root)

{

if(root != NULL)

{

postOrder(root->kiri);

postOrder(root->kanan);

39


}

}

void main()

{

int data;

Node *pohon;

pohon = NULL;

char pil;

do

{

clrscr();

cout<<"1. Tambah\n";

cout<<"2. Lihat Pre-order\n";

cout<<"3. Lihat In-order\n";

cout<<"4. Lihat Post-order\n";

cout<<"5. Keluar\n";

cout<<"Masukkan pilihan anda (1-5) : ";

cin>>pil;

if(pil!='1' && pil !='2' && pil !='3' && pil!='4' && pil!='5' )

cout<<"\n\nAnda salah pilih...\n";

else

{

if(pil=='1')

{

cout<<"\n";

cout<<"\nData baru : ";

cin>>data;

tambah(&pohon,data);

}

else

{

if(pil=='2')

{

cout<<"\n";

if(pohon!=NULL)

preOrder(pohon);

else

cout<<"Masih kosong!";

getch();

}

else

{

if(pil=='3')

{

cout<<"\n";

if(pohon!=NULL)

inOrder(pohon);

else


getch();

}

else

{

if(pil=='4')

{

cout<<"\n";

if(pohon!=NULL)

postOrder(pohon);

else


getch();

}

}

}

}

}

}

while(pil!='5');

40

}

void BinaryTree::remove(int d) { //Tempat element bool found = false; if(isEmpty()) { cout<<" This Tree is empty! "<<endl; return; } tree_node* curr; tree_node* parent; curr = root; while(curr != NULL) { if(curr->data == d) { found = true; break; } else { parent = curr; if(d>curr->data) curr = curr->right; else curr = curr->left; } } if(!found) { cout<<" Data not found! "<<endl; return; } // 3 pilihan : // 1. Kita bisa menghapus cabang node (leaf node) // 2. Kita bisa menghapus sebuah node dengan satu anaknya // 3. Kita bisa menghilangkan sebuah node dengan dua anaknya // Node dengan satu anaknya (cabang dari induknya) if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL && curr->right == NULL)) { if(curr->left == NULL && curr->right != NULL) { if(parent->left == curr) { parent->left = curr->right; delete curr; } else { parent->right = curr->right; delete curr; } } else // untuk cabang bagian kiri, bukan untuk cabang bagian kanan { if(parent->left == curr) { parent->left = curr->left; delete curr;

41

} else { parent->right = curr->left; delete curr; } } return; } //Kita bisa melihat pada pohon node (leaf node) if( curr->left == NULL && curr->right == NULL) { if(parent->left == curr) parent->left = NULL; else parent->right = NULL; delete curr; return; } //Node dengan dua anaknya (cabang dari induknya) // mengganti atau menempatkan lagi dengan nilai terkecil pada anak pohon bagian kanan if (curr->left != NULL && curr->right != NULL) { tree_node* chkr; chkr = curr->right; if((chkr->left == NULL) && (chkr->right == NULL)) { curr = chkr; delete chkr; curr->right = NULL; } else // anak bagian kanan merupakan anak-anak dari induknnya (children) { //jika anak kanan node merupakan anak bagian kiri //memindahkan semua bagian bawah cabang ke tempat element terkecil if((curr->right)->left != NULL) { tree_node* lcurr; tree_node* lcurrp; lcurrp = curr->right; lcurr = (curr->right)->left; while(lcurr->left != NULL) { lcurrp = lcurr; lcurr = lcurr->left; } curr->data = lcurr->data; delete lcurr; lcurrp->left = NULL; } else { tree_node* tmp; tmp = curr->right; curr->data = tmp->data; curr->right = tmp->right; delete tmp; } } return; } }

teori struktur data full

Documents