LAPORAN TUGAS AKHIR SEMESTER

PROGRAM AdSD

Disusun untuk Memenuhi Matakuliah Algoritma dan Struktur Data

Dibimbing oleh Bpk Utomo Pujianto, S.Kom., M.Kom.

Oleh:Eny Winarsih (150533602273)

Faizathi Sunarto (150533604509)

Hilmi Rahardian Zain (150533605479)

Laskar Amaruta Alfajri (150533604345)

Mirza R. Pratama (150533604496)

UNIVERSITAS NEGERI MALANG

FAKULTAS TEKNIK

JURUSAN TEKNIK ELEKTRO

PRODI S1 PENDIDIKAN TEKNIK INFORMATIKA

Mei 2016

A. Tujuan

1. Memenuhi tugas akhir Mata Kuliah Alogaritma dan Struktur Data

2. Memahami konsep Sorting dan mengimplementasikannya.

3. Memahami konsep Stack dan mengimplementasikannya.

4. Memahami konsep Queue dan mengimplementasikannya.

5. Memahami konsep Linked List dan mengimplementasikannya.

6. Memahami konsep Searching dan mengimplementasikannya.

7. Memahami konsep Sorting dan mengimplementasikannya.

8. Memahami konsep Tree dan mengimplementasikannya.

9. Mendemonstrasikan Materi Alogoritma dan Struktur Data dalam sebuah program.

B. Latar Belakang

Struktur Data memberikan penjelasan tentang suatu koleksi atau kelompok data yang

dapat dikarakteristikan oleh organisasi serta operasi yang didefinisikan terhadapnya.

Pemakaian struktur data yang tepat didalam proses pemrograman, akan menghasilkan

algoritma yang lebih jelas dan tepat sehingga menjadikan program secara keseluruhan lebih

sederhana.

Didalam sruktur data ini terdapat struct yang menampung beberapa data yang tipenya

bisa berlainan, menggunakan fungsi pointer yang digunakan untuk menunjuk suatu data

dimana tidak berisis data, melainkan alamat suatu data sehingga ketika kita mengalamatkan

suatu data, pointer akan langsung mengenali data tersebut.

Dalam struktur data ini terdapat juga tree yang menyerupai pohon yang dibalik dimana

sebuah simpul digunakan untuk menyimpan data. Struktur data yang dibuat ini juga

menampilkan isi tree yang berupa PreOrder, InOrder, PostOrder dan lainnya. Dengan

menggunakan program tersebut, struktur data yang akan dibuat akan menghasilkan

algoritma tepat.

Oleh karena alasan diatas, maka dalam membuat struktur data akan lebih baik jika kita

bisa memahami dengan benar karena jika kita paham dan menguasai materi, pembuatan

struktur data akan lebih mudah dan cepat.

C. Dasar Teori

2. Modul (Struct, Array, dan Pointer)

1.1 Pengenalan Struktur Data

Struktur data adalah sebuah skema organisasi, seperti struktur dan array,

yang diterapkan pada data sehingga data dapat diinterprestasikan dan sehingga

operasioperasi spesifik dapat

dilaksanakan pada data tersebut

1.2 Pengenalan Algoritma

Algoritma adalah barisan langkah-langkah perhitungan dasar yang

mengubah masukan

(dari beberapa fungsi matematika) menjadi keluaran. Contoh :

Perkalian

Input : integer positif a , b

Output : a X b

Algoritma perkalian :

Contoh kasus : a = 365, b = 24

Metode 1 : 365 * 24 = 365 + (365 * 23)

= 730 + (365 * 22)

…..

= 8760 + (365 * 0)

= 8760

Metode 2 : 3 6 5

2 4

1 4 6 0

7 3 0

8 7 6 0

Manakah algoritma yang lebih baik ?

1.3 Array

Array adalah organisasi kumpulan data homogen yang ukuran atau jumlah

elemen maksimumnya telah diketahui dari awal. Array umumnya disimpan di memori

komputer secara kontigu (berurutan). Deklarasi dari array adalah sebagai berikut:

int A[5]; artinya variabel A adalah kumpulan data sebanyak 5 bilangan bertipe

integer.

Operasi terhadap elemen di array dilakukan dengan pengaksesan langsung. Nilai

dimasing-masing posisi elemen dapat diambil dan nilai dapat disimpan tanpa melewati

posisi-posisi lain. Terdapat dua tipe operasi, yaitu:

1. Operasi terhadap satu elemen/posisi dari array

2. Operasi terhadap array sebagai keseluruhan

Dua operasi paling dasar terhadap satu elemen/posisi adalah

1. Penyimpanan nilai elemen ke posisi tertentu di array

2. Pengambilan nilai elemen dari posisi tertentu di array

1.3.1 Penyimpanan dan Pengambilan Nilai

Biasanya bahasa pemrograman menyediakan sintaks tertentu untuk penyimpanan

dan pengambilan nilai elemen pada posisi tertentu di array.

Contoh:

A[10] = 78, berarti penyimpanan nilai 78 ke posisi ke-10 dari array A

C = A[10], berarti pengambilan nilai elemen posisi ke-10 dari array A

1.3.2 Keunggulan dan Kelemahan Array

Keunggulan array adalah sebagai berikut:

1. Array sangat cocok untuk pengaksesan acak. Sembarang elemen di array dapat

diacu secara langsung tanpa melalui elemen-elemen lain.

2. Jika berada di suatu lokasi elemen, maka sangat mudah menelusuri ke elemen-

elemen tetangga, baik elemen pendahulu atau elemen penerus

3. Jika elemen-elemen array adalah nilai-nilai independen dan seluruhnya harus

terjaga, maka penggunaan penyimpanannya sangat efisien

Kelemahan array. Array mempunyai fleksibilitas rendah, karena array mempunyai batasan

sebagai berikut:

1. Array harus bertipe homogen. Kita tidak dapat mempunyai array dimana satu elemen

adalah karakter, elemen lain bilangan, dan elemen lain adalah tipe-tipe lain

2. Kebanyakan bahasa pemrograman mengimplementasikan array statik yang sulit diubah

ukurannya di waktu eksekusi. Bila penambahan dan pengurangan terjadi terus-menerus,

maka representasi statis

1) Tidak efisien dalam penggunaan memori

2) Menyiakan banyak waktu komputasi

3) Pada suatu aplikasi, representasi statis tidak dimungkinkan

1.4 Pointer

Misalnya kita ingin membuat beberapa penunjuk ke blok penyimpan yang berisi

integer.

Deklarasi pada C adalah:

int *IntegerPointer;

Tanda asterik (*) yang berada sebelum nama variable IntegerPointer menandakan

‘pointer pada suatu int’. Jadi deklarasi diatas berarti ‘definisikan sebuah tipe yang terdiri

dari

pointer bertipe integer yang bernama IntegerPointer’. Apabila didepannya ditambahkan

typedef

sebagai berikut

Typedef int *IntegerPointer;

Berarti IntegerPointer merupakan suatu tipe pointer berbentuk integer.

Apabila akan mendeklarasikan dua variable A dan B sebagai penunjuk ke bilangan

integer :

IntegerPointer A, B;

Berarti kompiler C akan berisi nilai dari variable A dan B yang ‘menunjuk ke integer’.

Untuk membuat beberapa penunjuk ke beberapa penyimpan integer yang kosong

dan

untuk membuat A dan B menunjuk tempat tersebut, digunakan prosedur dinamis untuk

alokasi

penyimpan yang disebut malloc

A = (IntegerPointer *) malloc (sizeof(int));

B = (int *) malloc (sizeof(int));

Misalnya kita akan menyimpan integer 5 pada blok penyimpan yang ditunjuk

pointer pada variable A. Untuk menuimpan angka 5 pada blok penyimpan integer itu

melalui pointer A,

digunakan pernyataan :

*A = 5;

Linked list adalah salah satu struktur data yang paling fundamental. Linked list

terdiri dari sejumlah kelompok elemen (linked ) dengan urutan tertentu. Linked list sangat

berguna untuk memelihara sekelompok data, semacam array, tetapi linked list lebih

menguntungkan dalam beberapa kasus. Linked list lebih efisien dalam proses penyisipan

(insertion ) dan penghapusan (deletion ). Linked list juga menggunakan pengalokasian

penyimpan secara dinamis, dimana penyimpan dialokasikan pada saat waktu berjalan

(runtime).

1.5 Struktur

Struktur adalah koleksi dari variabel yang dinyatakan dengan sebuah nama,

dengan sifat setiap variabel dapat memiliki tipe yang berlainan. Struktur biasa dipakai

untuk mengelompokkan beberapa informasi yang berkaitan menjadi sebuah satu kesatuan.

Contoh sebuah struktur adalah informasi data tanggal, yang berisi: tanggal, bulan dan

tahun.

1.5.1 Mendeklarasikan Struktur

Contoh pendefinisian tipe struktur adalah sebagai berikut:

struct data_tanggal {

int tanggal;

int bulan;

int tahun;

};

yang mendefinisikan tipe struktur bernama data_tanggal, yang terdiri dari tiga buah elemen

(field)

berupa : tanggal, bulan dan tahun. Pendefnisian dan pendeklarasian struktur dapat juga

ditulis

sebagai berikut:

struct data_tanggal {

int tanggal;

int bulan;

int tahun;

} tgl_lahir;

Bentuk umum dalam mendefinisikan dan mendeklarasikan struktur adalah sebagai berikut

struct nama_tipe_struktur {

tipe field1;

tipe field2;

...

...

tipe fieldn;

}variabel_struktur1, ... , variabel_strukturM;

Masing-masing tipe dari elemen struktur dapat berlainan. Adapun variabel_struktur1

sampai

dengan variabel_strukturM menyatakan bahwa variabel struktur yang dideklarasikan bisa

lebih

dari satu. Jika ada lebih dari satu variabel, antara variabel struktur dipisahkan dengan tanda

koma.

1.5.2 Mengakses Elemen Struktur

Elemen dari struktur dapat diakses dengan menggunakan bentuk

variabel_struktur.nama_field

Antara variabel_struktur dan nama_field dipisahkan dengan operator titik (disebut operator

anggota struktur). Contoh berikut merupakan instruksi untuk mengisikan data pada field

tanggal

tgl_lahir.tanggal = 30;

1.6 Kesimpulan

1. Struktur data adalah sebuah skema organisasi yang diterapkan pada data sehingga data

dapat diinterprestasikan dan sehingga operasi-operasi spesifik dapat dilaksanakan pada data

tersebut

2. Apabila kita membuat program dengan data yang sudah kita ketahui batasnya, maka kita

bias menggunakan array (tipe data statis), namun apabila data kita belum kita ketahui

batasnya,kita bisa menggunakan pointer (tipe data dinamis)

3. Untuk sekumpulan data dengan tipe data yang berlainan, namun merupakan satu-

kesatuan, kita dapat menggunakan struktur untuk merepresentasikannya.

3. Modul 3 (SEARCHING)

1. Linked List

Secara umum search dapat diartikan mencari data dengan cara menelusuri

tempat penyimpanan data tersebut. Tempat penyimpanan data dalam memory

dapat berupa array atau dapat juga dalam bentuk Linked List.

Pencarian dapat dilakukan terhadap data yang secara keseluruhan berada dalam

memory computer ataupun terhadap data yang berada dalam penyimpanan

eksternal (hard disk).

a. Sequential Search

Teknik pencarian data dari array yang paling mudah adalah dengan cara

sequential search, dimana data dalam array dibaca 1 demi satu, diurutkan dari

index terkecil ke index terbesar, maupun sebaliknya.

Array

Int A[5]={12, 13, 19, 27, 28}

Misalkan, dari data diatas angka yang akan dicari adalah angka 19 dalam array A, maka proses yang akan terjadi pada proses pencarian adalah sebagai berikut.

Pencarian dimulai pada index ke-0 yaitu angka 12, kemudian dicocokkan dengan angka yang akan dicari, jika tidak sama maka pencarian akan dilanjutkan ke index selanjutnya.

Pada index ke-1, yaitu angka 13, juga bukan angka yang dicari, maka pencarian juga akan dilanjutkan pada index selanjutnya

Pada index ke-2, yaitu angka 19, ternyata angka 19 merupakan angka yang dicari. Pencarian angka telah ditemukan, maka pencarian akan dihentikan dan keluar dari looping pencarian.

b. Binary SearchMetode pencarian yang kedua adalah binary search, pada metode pencarian ini, data

harus diurutkan terlebih dahulu. Pada metode pencarian ini, data dibagi menjadi dua bagian (secara logika), untuk setiap tahap pencarian.Algoritma binary search :

a) Data diambil dari posisi 1 sampai posisi akhir Nb) Kemudian cari posisi data tengah dengan rumus : (posisi awal + posisi akhir)/2c) Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau

lebih kecil, atau lebih besar ?d) Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah+1e) Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah-1f) Jika data sama, berarti ketemu.

c. Fibonacci SearchFibonacci search adalah pencarian sebuah elemen dalam array satu dimensi dengan

menggunakan angka Fibonacci sebagai titik-titik (indeks) elemen array yang isinya dibandingkan dengan nilai yang dicari. Sama halnya dengan binary search, Fibonacci Search juga mengharuskan data yang sudah terurut baik menaik (ascending) maupun menurun (descending).

d. Interpolation SearchInterpolation Search adalah pencarian sebuah elemen dalam array satu dimensi dengan metode interpolasi atau perkiraan secara interpolasi, dimana data harus diurutkan terlebih dahulu.

a) Jika data[posisi]>data yang dicari, high = pos-1b) Jika data[posisi]<data yang dicari, low = pos+14. MODUL IV (STACK)

1. Pengertian Stack

Stack merupakan sebuah kumpulan data yang diletakkan di atas data lainnya, seperti

sebuah tumpukan. Dengan demikian, stack merupakan salah satu struktur data yang

menerapkan prinsip LIFO (Last In First Out). Dimana elemen yang terakhir disimpan

dalam stack, menjadi elemen yang pertama diambil. Untuk meletakkan sebuah elemen

pada bagian atas dari stack, maka dilakukan operasi push. Sedangkan untuk memindahkan

sebuah elemen dari tempat atas tersebut dalam sebuah stack, maka dilakukan operasi pop.

2. Operasi Dasar Pada Stack

Create

Merupakan operator yang berfungsi untuk membuat sebuah stack kosong.

IsEmpty

Merupakan operator yang berfungsi untuk menentukan apakah suatu stack merupakan

stack kosong. Tanda bahwa sebuah stack kosong adalah Top bernilai kurang dari nol (-1).

IsFull

Merupakan operator yang digunakan untuk memeriksa apakah stack yang ada sudah penuh.

Stack akan penuh jika puncak stack terletak tepat dibawah jumlah maksimum yang dapat

ditampung stack (Top = MAX_STACK-1).

Push

Merupakan operator yang berfungsi untuk menambahkan satu elemen ke dalam stack dan

tidak dapat dilakukan jika stack dalam keadaan penuh.

Pop

Merupakan operator yang berfungsi untuk mengeluarkan satu elemen teratas dari dalam

stack dengan syarat stack tidak dalam kondisi kosong.

Clear

Fungsi yang digunakan untuk mengosongkan stack dengan cara mengeset Top dengan -1.

Jika Top bernilai kurang dari nol maka stack dianggap kosong.

Retrive

Fungsi yang digunakan untuk melihat nilai yang berada pada posisi tumpukan teratas.

3. Pointer Sebagai Penunjuk Stack

Selain menggunakan indeks, untuk menunjuk sebuah Top atau posisi teratas dari stack,

dapat juga digunakan pointer sebagai berikut.

Membuat Stack Dengan Pointer

Proses Push

Proses Pop

4. Representasi Proses Stack

Stack adalah salah satu dari contoh struktur data yang terdiri dari satu collection, yang juga

menerapkan prinsip LIFO. Bila stack tersebut menggunakan array satu dimensi, maka stack

tersebut dapat diilustrasikan sebagai berikut :

Pada gambar 4.2 diatas diilustrasikan ada sebuah indeks array yang masih kosong pada

awal pembuatan stack dimana n[10], variabel Top berada pada -1 yang menunjukkan

indeks masih dalam keadaan kosong.

Pada gambar 4.3 adalah keadaan ketika stack sudah diisi data. Pada kondisi ini data

pertama yang diinputkan adalah S[0]=11, data kedua S[1]=7, data ketiga S[2]=15, data

keempat S[23]=23. Kondisi Top sudah berubah menjadi data yang terakhir diinputkan (data

keempat) sehingga Top[3]X=23.

Variabel Top digunakan sebagai indeks untuk menunjuk nomor elemen array yang

berisi nilai stack yang berada paling kanan atau Top, yang ditunjukkan dengan angka 3.

Variabel X bertipe integer digunakan sebagai perantara, dimana data yang akan disimpan

kedalam stack harus berasal dari X. Demikian juga data yang baru diambil dari dalam stack

harus diterima terlebih dahulu oleh variabel X, kemudian baru diberikan ke variabel lain

untuk diolah.

Oleh karena itu, jika ada instruksi PUSH, maka data baru (yang diambil dari isi variabel

X) akan disimpan dalam elemen S[4] sehingga indeks Top harus diarahkan ke posisi no. 4.

Artinya, Top maju terlebih dahulu satu langkah ke S[4], kemudian baru mengisi nilai pada

S[4]. Sedangkan jika ada instruksi Pop, maka yang akan diambil adalah isi dari S[3] dan

datanya akan disimpan terlebih dahulu dalam variabel X, kemudian indeks Top menjadi

mundur satu langkah sehingga akan menunjuk S[2].

5. Double Stack

Double stack atau Stack Ganda adalah dua stack yang berada dalam satu array. Satu

array digunakan untuk dua stack dimana dasar Stack1 berada pada sisi indeks yang terkecil

dan dasar Stack2 berada pada sisi indeks yang terbesar. Sama halnya dengan Single Stack,

Double Stack juga menerapkan prinsip LIFO (Last In First Out).

Pada gambar 4.4 diatas adalah ilustrasi indeks array pada double stack. Pada stack 1

kondisi data pertama yang diinputkan adalah S[0], data kedua S[1], data ketiga S[2] dan

Top=data input terakhir S[2]. Sedangkan pada stack 2 data pertama adalah S[9], data kedua

S[8], data ketiga S[7], data keempat S[6], dan Top=data input terakhir S[6].

6. Operasi Dasar Pada Double Stack

Inisialisasi

Proses awal adalah proses menyiapkan indeks penunjuk stack untuk pertama kali. Pada

tahap ini ditetapkan Top=-1 (sama seperti single stack) dan Top2=banyak jumlah data.

Is Empty

Sama dengan single stack, yaitu proses pengecekan stack dalam kondisi kosong.

Is Full

Sama dengan single stack, yaitu proses pengecekan stack dalam kondisi penuh.

Push (Stack1 dan Stack2)

Proses mengisi data pada stack1 maupun stack2.

Pop (Stack1 dan Stack2)

Proses mengambil data pada stack1 maupun stack2.

5. MODUL 5 (QUEUE)

QUEUE

Queue atau antrian adalah suatu kumpulan data yang penambahan elemennya hanya

bisa dilakukan pada suatu ujung (disebut dengan sisi belakang atau rear), dan

penghapusan atau pengambilan elemen dilakukan lewat ujung yang lain (disebut

dengan sisi depan atau front). Kalau tumpukan dikenal dengan menggunakan prinsip

LIFO (Last In First Out), maka pada antrian prinsip yang digunakan adalah FIFO (First

In First Out).

Implementasi Antrian dengan Array

Untuk memahami penggunaan antrian dalam array, kita membutuhkan deklarasi antrian, misalnya:

Dengan deklarasi di atas, elemen antrian dinyatakan dalam tipe integer yang semuanya

terdapat dalam struktur. Variabel first menunjukkan posisi elemen pertama dalam array,

dan variable last menunjukkan posisi elemen terakhir dalam array.

Algoritma dari penggalan program di atas adalah:

1. Tentukan elemen yang akan dimasukkan ke dalam antrian (dalam hal ini adalah 6

elemen)

2. Deklarasikan struktur untuk menampung elemen pada antrian

3. Selesai

Untuk menambah elemen baru dan mengambil elemen dari antrian dalam antrian,

diperlukan deklarasi berikut ini

Implementasi Antrian dengan Pointer

Untuk mengimplementasikan antrian dengan menggunakan pointer, perhatikan algoritma berikut ini:

1. Tentukan struktur untuk menampung node yang akan dimasukkan pada antrian. Deklarasi struktur pada penggalan program berikut ini:

2. Deklarasikan penambahan elemen baru pada antrian, di mana letaknya adalah paling belakang. Deklarasi penambahan elemen baru tersebut dapat dilihat pada penggalan program berikut ini:

3. Lakukan pengecekan terhadap antrian, apakah antrian dalam kosong atau tidak. Kalau kondisi antrian kosong, maka elemen bisa dihapus. Penggalan program berikut ini akan menunjukkan kondisi tersebut.

6. MODUL 6 (LINKED LIST)

Salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara

sekuensial, saling bersambungan, dinamis dan terbatas 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 class yang berisi

data.

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

bantuan pointer. 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

compile, hal ini bisa merupakan suatu atribut yang baik juga. Setiap node akan berbentuk

struct dan memiliki satu buah field bertipe struct yang sama, yang berfungsi sebagai

pointer.

Dalam menghubungkan setiap node, kita dapat menggunakan carafirst-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, variable next ini akan menghubungkan kita

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

next harus bertipe struct node.

Bentuk umum :

Infotype sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list

Next address dari elemen berikutnya (suksesor).

Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu

dengan notasi : first (L)

Sebelum digunakan harus dideklarasikan terlebih dahulu :#define first(L) (L)

Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :Info(P)deklarasi #define info(P) P->info

Next(P)deklarasi #define next(P) P->next

Beberapa definisi :

1. List 1 adalah list kosong, jika First(L)=Nil

2. Elemen terakhir dikenali, dengan salah satu cara adalah karena Next(Last)=Nil

Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null

Operasi-operasi Linked List

1) Insert

Istilah insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

2) IsEmpty

Fungsi ini menentukan apakah linked list kosong atau tidak.

3) Find First

Fungsi ini mencari elemen pertama dari linked list

4) Find Next

Fungsi ini mencari elemen sesudah elemen yang ditunjuk now

5) Retrieve

Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu

dikembalikan oleh fungsi

6) Update

Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu

7) Delete Now

Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah

elemen pertama dari linked list (head), head akan berpindah ke elemen berikutnya

8) Delete Head

Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen

sesudahnya

9) Clear

Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila

anda ingin mengakhiri program yang menggunakan linked list. Jika anda

melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya

akan tetap tertinggal di dalam memori.

a. Single linked list (Senarai berkait tunggal)

Single linked list adalah apabila hanya ada satu pointer yang menghubungkan setiap

node (satu arah “next”).

a.1. Single Linked Listnon Circular

Pembuatan struct bernama tnode berisi 2 field, yaitu field data bertipe integer

dan field next yang bertipe pointer dari tnode.

Deklarasi node dengan struct :

Asumsikan kita memiliki sejumlah node yang selali menoleh ke sebelah dalam

arah yang sama. Atau, sebagai alat bantu, kita bias mengasumsikan beberapa orang

yang bermain kereta api. Yang belakang akan memegang bahu pemain adalah node.

Dan tangan pemain yang digunakan untuk memegang bahu pemain depan adalah

variable next. Sampai di sini, kita baru saja mendeklarasikan tipe data dasar sebuah

node. Selanjutnya, kita akan mendeklarasikan beberapa variable pointer bertipe

struct tnode. Beberapa variable tersebut akan kita gunakan sebagai awal dari linked

list, node aktif dalam linked list, dan node sementara yang akan digunakan dalam

pembuatan node di linked list. Berikan nilai awal NULL kepada mereka. Deklarasi

node untuk beberapa keperluan, seperti berikut ini :

Struct tnode *head=NULL, *curr=NULL, *node=NULL;

Dengan demikian, sampai saat ini, telah dimiliki tiga node. Satu sebagai

keepada (head), satu sebagai node aktif dalam linked list (curr) dan satu lagi node

sementara (node). Untuk mempermudah pengingatan, ingatlah gambar anak panah

yang mengarah ke kanan. Head akan berada pada pangkal anak panah, dan node-

node berikutnya akan berbaris kea rah bagian anak panah yang tajam.

Apabila diperhatikan, setiap node memiliki petunjuk untuk node sebelahnya.

Node terakhir akan diberikan nilai NULL. Dengan demikian, setiap node kebagian

jatah.

Berikut adalah penjelasan kode-kode pembuatan singly linked list tersebut,

pertama-tama, akan dibuat perulangan dari 0 sampai 4, yang dimaksudkan untuk

membuat lima buah node yang masing-masing field data nya berisikan nilai dari 0

sampai 4. Pembuatan node dilakukan dengan fungsi malloc().

Setelah itu, perlu dibuat node dan penghubung. Pertama-tama, akan diuji

apakah head bernilai NULL. Kondisi head bernilai NULL hanya terjadi apabila

belum dimiliki satu node pun. Dengan demikian, node tersebut akan dijadikan

sebagai head. Node aktif (curr), juga kita dapat dari node tersebut. Kalau head tidak

bernilai NULL alias telah memiliki satu atau lebih node, yang pertama dilakukan

adalah menghubungkan pointer next dari node aktif (curr) ke node yang baru saja

dibuat. Dengan demikian, baru saja dibuat penghubung antara rantai lama dengan

mata rantai baru. Atau, dalam permainan kereta api, pemain paling depan dalam

barisan lama akan menempelkan tangannya pada bahu pemain yang baru bergabung.

Node aktif (curr) kemudian dipindahkan ke node yang baru dibuat.

a.2. Single Linked List Circular

Hampir sama dengan single linked list non circular, bahwa dibutuhkan sebuah

kait untuk menghubungkan node-node data yang ada, dimana pada node terakhir atau

tail yang semula menunjukkan NULL diganti dengan menunjuk ke kepala atau head.

Dimana inisialisasi senarai berkait tunggal sirkular menggunakan struct adalah

sebagai berikut :

Deklarasi Single Linked List Circular :

Menambah node dan membuat tail dari single linked list circular

Deklarasi penambahan node baru :

Menyisipkan node baru

Deklarasi menyisipkan node baru menggunakan syntax berikut :

Menghapus node dari Single Linked List Circular

Deklarasi menghapus node dari single linked list circular, menggunakan sintaks

berikut :

b. Double Linked List (Senarai berkait ganda)

Double linked list adalah elemen-elemen yang dihubungkan dengan dua pointer dalam

satu elemen dan list dapat melintas baik di depan atau belakang. Elemen double linked

list terdiri dari tiga bagian :

1. Bagian data informasi

2. Pointer next yang menunjuk ke elemen selanjutnya

3. Pointer prev yang menunjuk ke elemen sebelumnya

b.1. Double Linked List non Circular

Deklarasi pointer penunjuk kepala Double Linked List

Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node

berikutnya dan ke node sebelumnya. Untuk pembentukan node baru, mulanya pointer

next dan prev akan menunjuk ke nilai NULL. Selanjutnya, pointer prev akan menunjuk

ke node sebelumnya, dan pointer next akan menunjuk ke node selanjutnya pada list.

Deklarasi node dibuat dari struct berikut ini :typedef struct TNode{

int data;

Tnode *next;

Tnode *prev;

};

Double Linked List Non Circular dengan HEAD membutuhkan satu buah

variabel pointer, yaitu: head. Head akan selalu menunjuk pada node

pertama.

Deklarasi Pointer Penunjuk Kepala Double Linked List

Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, Melainkan

harus melalui node pertama dalam linked list. Deklarasinya sebagai

berikut:

TNode *head;

Fungsi Inisialisasi Single Linked List non Circular

void init(){

– head = NULL;

Function untuk mengetahui kosong tidaknya DLLNC

int isEmpty(){

if(head == NULL) return 1;

else return 0;

}

Penambahan data di depan

Penambahan node baru akan dikaitkan di ode paling depan, namun pada

saat pertama kali (data masih kosong), maka penambahan data dilakukan

pada head-nya. Pada prinsipnya adalah mengkaitkan data baru dengan

head, kemudian head akan menunjuk pada data baru tersebut sehingga

head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node

terakhir dengan node terdepan dibutuhkan pointer bantu.

Fungsi Menambah Di Depan

void insertDepan(int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = NULL;

baru->prev = NULL;

if(isEmpty()==1){

head=baru;

head->next = NULL;

head->prev = NULL;

}

else {

baru->next = head;

head->prev = baru;

head = baru;

}

cout<<”Data masuk\n”;

}

Function untuk menampilkan isi DLLNC

void tampil(){

TNode *bantu;

bantu = head;

if(isEmpty()==0){

while(bantu!=NULL){

cout<<bantu->data<<" ";

bantu=bantu->next;

}

cout<<endl;

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

}

Function untuk menghapus data di depan:

void hapusDepan (){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

d = hapus->data;

head = head->next;

head->prev = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

}

cout<<d<<" terhapus\n";

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

}

Fungsi untuk menghapus node terbelakang

void hapusBelakang(){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

while(hapus->next!=NULL){

hapus = hapus->next;

}

d = hapus->data;

hapus->prev->next = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

}cout<<d<<" terhapus\n";

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

}

Ilustrasi Penghapusan Node

Menghapus Node Double Linked List

Tidak diperlukan pointer bantu yang mengikuti pointer hapus yang

berguna untuk menunjuk ke NULL. Karena pointer hapus sudah bisa

menunjuk ke pointer sebelumnya dengan menggunakan elemen prev ke

node sebelumnya, yang akan diset agar menunjuk ke NULL setelah

penghapusan dilakukan.

Fungsi menghapus semua elemen

void clear(){

TNode *bantu,*hapus;

bantu = head;

while(bantu!=NULL){

hapus = bantu;

bantu = bantu->next;

delete hapus;

}

head = NULL;

}

b.2 Double Linked List Circular

Double Linked List Circular (DLLC) adalah linked list dengan

menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field

pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer

sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut

dengan pointer next dan pre-nya menunjuk ke dirinya sendiri secara

circular.

Setiap node pada linked list mempunyai field yang berisi data dan pointer

ke node berikutnya dan ke node sebelumnya. Untuk pembentukan node

baru, mulanya pointer next dan prev akan menunjuk ke dirinya sendiri. Jika

sudah lebih dari satu node, maka pointer prev akan menunjuk ke node

sebelumnya, dan pointer next akan menunjuk ke node sesudahnya.

Deklarasi dan node baru DLLC

Deklarasi node

Dibuat dari struct berikut ini:

typedef struct TNode{

int data;

TNode *next;

Tnode *prev;

};

Pembentukan node baru

Digunakan keyword new yang berarti mempersiapkan sebuah node baru

berserta alokasi memorinya.

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

baru->prev = baru;

Penambahan data di depan

Penambahan node baru akan dikaitan di node paling depan, namun pada

saat pertama kali (data masih kosong), maka penambahan data dilakukan

pada head nya. Pada prinsipnya adalah mengkaitkan data baru dengan head,

kemudian head akan menunjuk pada data baru tersebut sehingga head akan

tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir

dengan node terdepan dibutuhkan pointer bantu.

void insertDepan(int databaru){

TNode *baru, *bantu;

baru = new TNode;

baru->data = databaru;

baru->next = baru;

baru->prev = baru;

if(isEmpty()==1){

head=baru;

head->next = head;

head->prev = head;

}

else {

bantu = head->prev;

baru->next = head;

head->prev = baru;

head = baru;

head->prev = bantu;

bantu->next = head;

}

cout<<"Data masuk\n";

}

Penambahan data di belakang

Penambahan data dilakukan di belakang, namun pada saat pertama kali

data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit

karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang,

kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang

perlu digunakan perulangan.

void insertBelakang (int databaru){

Tnode *baru, *bantu;

baru = new Tnode;

baru->data = databaru;

baru->next = baru;

baru->prev = baru;

if(isEmpty()==1){

head=baru;

head->next = head;

head->prev = head;

}

else{

bantu=head->prev;

bantu->next = baru;

baru->prev = bantu;

baru->next = head;

head->prev = baru;

}

Cout<<”Data masuk\n”;

}

Function untuk menampilkan isi linked list

void tampil(){

TNode *bantu;

bantu = head;

if(isEmpty()==0){

do{

cout<<bantu->data<<" ";

bantu=bantu->next;

}while(bantu!=head);

cout<<endl;

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

}

Function untuk menghapus node terbelakang

void hapusDepan (){

TNode *hapus,*bantu;

int d;

if (isEmpty()==0){

if(head->next != head){

hapus = head;

d = hapus->data;

bantu = head->prev;

head = head->next;

bantu->next = head;

head->prev = bantu;

delete hapus;

} else {

d = head->data;

head = NULL;

}

cout<<d<<" terhapus\n";

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

}

Function untuk menghapus node terbelakang

void hapusBelakang(){

TNode *hapus,*bantu;

int d;

if (isEmpty()==0){

if(head->next != head){

bantu = head;

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

bantu = bantu->next;

}

hapus = bantu->next;

d = hapus->data;

bantu->next = head;

delete hapus;

} else {

d = head->data;

head = NULL;

}

cout<<d<<" terhapus\n";

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

}

Function untuk menghapus semua elemen

void clear(){

TNode *bantu,*hapus;

if (isEmpty()==0){

bantu = head;

while(bantu->next!=head){

hapus = bantu;

bantu = bantu->next;

delete hapus;

}

head = NULL;

}

}

7. MODUL 7 (TREE)

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

Ilustrasi Algoritma Tree

Ancestor (F) = C,A Sibling(F) = G Leaf = D,E,F,G Descendant (C) = F,G Size = 7 Degree = 2 Parent(D) = B Height = 3 Child(A) = B,C Root = A

3. JENIS - JENIS

BINARY TREE

Tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua sub pohon dan kedua subpohon harus terpisah. Kelebihan struktur Binary Tree : 1. Mudah dalam penyusunan algoritma sorting.2. Searching data relatif cepat.3. Fleksibel dalam penambahan dan penghapusan data

4. IMPLEMENTASI ALGORITMA TREE

Insert : menambahkan node dalam tree Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri. Untuk data pertama akan menjadi elemen root.

PreOrder: cetak node yang dikunjungi, kunjungi left, kunjungi right

InOrder: kunjungi left, cetak node yang dikunjungi, kunjungi right

PostOrder: kunjungi left, kunjungi right, cetak node yang dikunjungi

Searching Data : untuk searching data kita tinggal menjelajahi node yang ada di dalam tree,

algoritmanya adalah jika data yang di cari sama dengan root maka data di temukan, jika tidak

maka akan mengecek kembali apakah data lebih lebih kecil dari root maka secara rekursi akan

mencari kekiri, jika data lebih besar dari root maka secara rekursif akan mencari ke kanan

D. Algoritma ProgramAlgoritma utama program

(1) Definisikan Node [tipe Struct, data dan pointer *kiri dan *kanan](2) Lakukan: Tampilkan menu program(3) Ambil pilihan:

Jika pilihan = 1, panggil fungsi tambah()Jika pilihan = 2, panggil fungsi hapus()Jika pilihan = 3, jika pohon ≠ NULL, panggil fungsi preorder()

Jika tidak keluarkan pesan “Masih kosong!”Jika pilihan = 4, jika pohon ≠ NULL, panggil fungsi inorder()

Jika tidak keluarkan pesan “Masih kosong!”Jika pilihan = 5, jika pohon ≠ NULL, panggil fungsi postorder()

Jika tidak keluarkan pesan “Masih kosong!”Jika pilihan = 6, jika pohon ≠ NULL, panggil fungsi levelorder()

Jika tidak keluarkan pesan “Masih kosong!”

Jika pilihan = 7, panggil fungsi search()(4) Ulangi ke langkah Lakukan selama pilihan ≠ 8(5) Selesai

Algoritma fungsi tambah()

(1) Siapkan parameter ‘**root’ bertipe Node dan ‘databaru’ bertipe Integer(2) Jika pointer root = NULL maka

1) Buat variabel pointer ‘baru’ bertipe Node2) Variabel ‘baru’ bertipe Node3) Isi ‘data’ pada variabel dengan parameter ‘databaru’4) Arahkan isi ‘kiri’ dan ‘kanan’ pada variabel dengan NULL5) Arahkan pointer ‘root’ pada variabel baru6) Arahkan ‘kiri’ dan ‘kanan’ pada pointer root pada NULL7) Cetak pesan dan inkremenkan hitung

Jika tidak, jika ‘databaru’ kurang dari ‘data’ di variabel pointer ‘root’ maka

1) Panggil fungsi tambah dengan parameter ‘kiri’ pada pointer root dan ‘databaru’

Jika tidak, jika ‘databaru’ lebih dari ‘data’ di variabel pointer ‘root’ maka1) Panggil fungsi tambah dengan parameter ‘kanan’ pada pointer root dan

‘databaru’Jika tidak, jika ‘databaru’ sama dengan ‘data’ di variabel pointer ‘root’ maka

1) Cetak pesan “data sudah ada”(3) Selesai

Algoritma fungsi deleteTree() dan hapusPohon()

(1) deleteTree(): Siapkan parameter ‘*node’ bertipe Node(2) jika ‘node’ = NULL maka hentikan eksekusi fungsi dan keluar dari fungsi(3) dengan fungsi yang sama/rekursif, hapus ‘kiri’ dan ‘kanan’ dari node(4) hapus node dengan membebaskan memori melalui fungsi free()(5) hapusPohon(): Siapkan parameter ‘**node_ref’ bertipe Node(6) panggil fungsi deleteTree dengan parameter *nodeRef(7) Atur *node_ref menjadi NULL(8) Selesai

Algoritma fungsi preorder()

(1) Siapkan parameter *root bertipe Node(2) Jika root ≠ NULL maka:

1) Buat stack baru (nodestack) dan push root ke ‘nodestack’2) Ketika nodestack tidak kosong

Pop semua isi satu per satu, lakukan hal berikut:a) Cetak isi di saat inib) Push child kanan dari node yang di-pop ke stackc) Push child kiri dari node yang di-pop ke stack

(3) Jika nodestack sudah kosong, selesai.

Algoritma fungsi inorder()

(1) Siapkan parameter *root bertipe Node(2) Jika root ≠ NULL maka

1) Panggil fungsi inorder, dengan parameter isi dari ‘kiri’ pada root2) Cetak data dari root di posisi saat ini3) Panggil fungsi inorder, dengan parameter isi dari ‘kanan’ pada root

(3) Selesai.

Algoritma fungsi postorder()

(1) Siapkan parameter *root bertipe Node

(2) Jika root ≠ NULL maka1) Panggil fungsi postorder, dengan parameter isi dari ‘kiri’ pada root2) Panggil fungsi postorder, dengan parameter isi dari ‘kanan’ pada root3) Cetak data dari root di posisi saat ini

(3) Selesai.

Algoritma fungsi levelorder()

(3) Siapkan parameter *root bertipe Node(4) Buat variabel untuk antrian/queue (q)(5) Jika root ≠ NULL maka

1) Push root ke queue(6) Ketika queue tidak kosong maka

1) Buat variabel pointer tmpNode (node sementara) berisi data paling depan dari queue

2) Pop/Dequeue antrian/queue3) Cetak data dari tmpNode4) Jika ada data ‘kiri’ dari tmpNode maka enqueue/push bagian tersebut ke

queue5) Jika ada data ‘kanan’ dari tmpNode maka enqueue/push bagian tersebut ke

queue(7) Selesai

Algoritma fungsi search()

(1) Siapkan parameter ‘**root’ bertipe Node dan ‘cari’ bertipe Integer(2) Jika *root = NULL maka cetak peringatan “Data tidak ditemukan!”(3) Jika tidak, jika data pada ‘cari’ kurang dari ‘data’ pada *root maka cari ke

‘kiri’(4) Jika tidak, jika data pada ‘cari’ lebih dari ‘data’ pada *root maka cari ke

‘kanan’(5) Jika tidak, jika data pada ‘cari’ sama dengan ‘data’ pada *root maka cetak

“Data ditemukan!”(6) Selesai

E. Penjelasan Program

Program diatas menggunakan fungsi tree, yang terdapat beberapa proses didalamnya

diantaranya :

1. Menambahkan data dengan menggunakan fungsi tambah().

Jika root=NULL maka data yang dimasukkan akan masuk ke root. Jika root!=NULL,

maka lihat databaru tersebut. Jika databaru lebih kecil daripada root maka databaru

akan ditambah di sebelah kiri root. Sebaliknya jika databaru lebih besar daripada root

maka databaru akan ditambah di sebelah kanan root.

2. Hapus Data dengan menggunakan fungsi deleteTree() dan hapusPohon()

Ketika ada parameter *node bertipe node. Jika nilai node=NULL maka hentikn

eksekusi fungsi dan keluar dari fungsi, dengan fungsi yang sama/rekursif, hapus

‘kiri’ dan ‘kanan’ dari node hapus node dengan membebaskan memori melalui

dungsi tree(). Siapkan parameter **node_ref bertipe Node, panggil fungsi

deleteTRee dengan parameter *nodeRef, kemudian atur *node_ref menjadi NULL.

3. Preorder dengan menggunakan fungsi preorder()

Untuk proses preorder menggunakan stack dalam menjalankannya. Jika root!=NULL maka akan membuat stack baru (nodestack) dan push root ke “nodestack”. Jika nodestack tidak kosong, maka pop semua isi satu per satu, dan selanjutnya cetak isi yang sudah ada, lalu push child kanan dari node lalu push child kiri dari node yang di-pop ke stack. Jika nodestack sudah kosong, proses selesai.

4. Inorder dengan menggunakan fungsi inorder()

Untuk proses inorder jika root!=NULL maka, panggil fungsi inorder dengan

parameter isi dari “kiri” root. Lalu cetak data dari root saat ini, dan selanjutnya

panggil fungsi inorder, dengan parameter isi dari “kanan” root. Proses inorder juga

bisa dibilang proses sorting

5. Postorder dengan menggunakan fungsi postorder()

Untuk proses postorder jika root!=NULL maka, panggil fungsi postorder dengan

parameter isi dari “kiri” root, lalu panggil fungsi postorder lagi dengan panggil

fungsi postorder dengan parameter isi dari “kanan” root. Selanjutnya cetak data dari

root saat ini.

6. Levelorder dengan menggunakan fungsi levelorder()

Untuk proses levelorder kita menggunakan queue. Buat variabel untuk antrian/queue.

Jika root !=NULL maka push root ke queue. Ketika queue sedang tidak kosong maka

buatlah variabel pointer tmpNode (node sementara) yang berisikan data paling depan

dari queue. Selanjutnya pop/dequeue antrian, lalu cetak data dari tmpNode. Jika ada

data “kiri” dari tmpNode maka enqueue/push bagan tersebut ke queue dan jika ada

data “kanan” dari tmpNode maka enqueue/push bagian tersebut ke queue.

7. Search dengan menggunakan fungsi search()

Untuk proses search jika *root=NULL maka cetak “Data Tidak Ditemukan”. Tetapi

jika tidak, data pada “cari” kurang dari “data” pada *root maka cari ke “kiri”. Jika

data pada “cari” lebih dari “data” pada *root maka cari ke “kanan”. Jika data pada

“cari” lebih dari “data” pada *root maka cetak “Data Ditemukan” atau sama dengan

data telah ditemukan.

F. Hasil Program

Memasukkan data sebanyak enam kali

Menghapus Data

Pre-Order

In Order

Post Order

Level Order

Searching

Kesimpulan

Dari progam diatas dapat disimpulkan bahwa :

1. Terdapat beberapa fungsi tambah (void tambah) untuk menambahkan data pada

progam.

2. Menggunakan fungsi deleteTree dan hapus pohon yang akan menghentikan eksekusi

dan mmenghapus data pada program yang telah di inputkan.

3. Menggunakan fungsi Preorder dengan stack dalam menjalankan program degan

ketentuan jika node stack tidak kosong, maka pop semua akan diisi satu persatu.

4. Menggunakan fungsi Inorder untuk memanggil fungsi isi pada root dengan parameter

isi dari kiri root lalu cetak dari kanan root.

5. Menggunakan fungsi postorder

6. Menggunakan fungsi levelorder yang menggunakan fungsi queue dimana

penambahan elemennya hanya bisa dilakukan pada suatu ujung (disebut dengan sisi

belakang atau rear), dan penghapusan atau pengambilan elemen dilakukan lewat ujung

yang lain (disebut dengan sisi depan atau front.

7. Menggunakan fungsi search untuk menemukan data jika *root!=NULL. Jika data yang

dicari lebih besar dari NULL maka data ditemukan.

G. Daftar Rujukan

Tim Asisten Dosen. 2016. Modul 1 – Struck, Array, Pointer. Malang: Unversitas Negeri

Malang.

Tim Asisten Dosen. 2016. Modul 2 – Sorting. Malang: Unversitas Negeri Malang.

Tim Asisten Dosen. 2016. Modul 3 – Serching. Malang: Unversitas Negeri Malang.

Tim Asisten Dosen. 2016. Modul 4 – Stack. Malang: Unversitas Negeri Malang.

Tim Asisten Dosen. 2016. Modul 5 - Queue. Malang: Unversitas Negeri Malang.

Tim Asisten Dosen. 2016. Modul 6 – Linked LIst. Malang: Unversitas Negeri Malang.

H. Lampiran

a. Source Code#include <stdio.h>#include <conio.h>#include <windows.h>#include <iostream>#include <stack>#include <queue>using namespace std;

typedef struct Node{int data;Node *kiri;Node *kanan;

};

int hitung;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("\n\tData Bertambah!");hitung++;

}

else if(databaru < (*root)->data)tambah(&(*root)->kiri,databaru);

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

else if(databaru == (*root)->data)printf("\n\tData Sudah Ada!");

}void hapus(Node **root, int del){

if((*root) == NULL){printf("D\n\tata Tidak Ada");

} else if(del < (*root)->data)

hapus(&(*root)->kiri,del);

else if(del > (*root)->data)hapus(&(*root)->kanan,del);

else if(del == (*root)->data){(*root)=NULL;printf("\n\tData telah dihapus");

}}void preorder(Node *root){//menggunakan stack

if(root != NULL){stack<Node *> nodestack;nodestack.push(root);

while(nodestack.empty() == false){

Node *node = nodestack.top();printf("%d ", node->data);nodestack.pop();

if(node->kanan)nodestack.push(node->kanan);

if(node->kiri)nodestack.push(node->kiri);

}}

}

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 levelorder(Node* root){//menggunakan queue queue<Node*> q;

if(root != NULL) { // root di-PUSH q.push(root);

// lopp s.d. ada node dalam queue while(!q.empty()) { // node awal di-dequeue Node *tmpNode = q.front(); q.pop();

// tidak NULL, maka dicetak cout<< tmpNode->data <<" \n";

// kiri di-enqueue jika ada if(tmpNode->kiri) { q.push(tmpNode->kiri); } // kanan di-enqueue jika ada if(tmpNode->kanan) { q.push(tmpNode->kanan); }

} }

}

void search(Node **root, int cari){if((*root) == NULL){

printf("\n\tData Tidak Ditemukan!");} else if(cari < (*root)->data)

search(&(*root)->kiri,cari);else if(cari > (*root)->data)

search(&(*root)->kanan,cari);else if(cari == (*root)->data)

printf("\n\tData Ditemukan!");

}

int main(){int pil,cari,del;Node *pohon;pohon = NULL;do{

int data;printf("\n ==================================");printf("\n == PROGRAM TREE ==");printf("\n ==================================\n");printf("\nPilihan Menu:");printf("\n=========================\n");printf("1. Menambah Data\n");printf("2. Hapus Data\n");printf("3. Lihat Pre-Order\n");printf("4. Lihat In-Order\n");printf("5. Lihat Post-Order\n");printf("6. Lihat Level-Order\n");printf("7. Searching\n");printf("==========================\n");printf("Masukkan Pilihan Menu: " ); scanf("%d",&pil);system("cls");switch(pil){

case 1: printf("\n\t-Data Baru dalam Angka-\n");printf("\tMasukkan Data Baru : ");scanf("%d", &data);tambah(&pohon,data);

break;case 2:

printf("\n\tMasukkan Data yang ingin dihapus : ");

scanf("%d", &del);hapus(&pohon,del);break;

case 3: if(pohon!=NULL) preorder(pohon);

else printf("\n\tMasih Kosong!!");break;

case 4: if(pohon!=NULL) inorder(pohon);

else printf("\n\tMasih Kosong!!");break;

case 5: if(pohon!=NULL) postorder(pohon);

else printf("\n\tMasih Kosong!!");break;

case 6: if(pohon!=NULL) levelorder(pohon);

else printf("\n\tMasih Kosong!!");break;

case 7: printf("\n\tMasukkan Data yg Dicari: ");scanf("%d", &cari);search(&pohon,cari);break; }

getch();system("cls");

}while(pil!=8);}

b. Gsmbar