Makalah Struktur Data.docx

BAB I PENDAHULUAN A.

LATAR BELAKANG Pemograman dalam struktur data ada beberapa macam. Salah satunya adalah

pemograman C++. Dalam pemograman ini biasanya menggunakan variable Array, Struktur dan Linked List. Makalah ini membahas tentang beberapa variabel tersebut dimana ketiga variable mempunyai ciri dan umum yang berbeda sesuai dengan tipe file yang di gunakan pembaca. Seperti array yang menggunakan satu dimensi dan dua dimensi serta 3 dimensi dimana sangat berbeda dengan struktur yang menggunakan tingkatan prosedur. Pemograman ini merupakan pemograman yang berbeda dari pemograman lainnya misalnya VB, Delphi atau Pascal namun perbedaan juga tidak begitu signifikan pada pemograman pascal. B.

RUMUSAN MASALAH

1.

Penjelasan tentang data dan struktur data.

2.

Penjelasan tentang String.

3.

Penjelasan tentang Array.

4.

Penjelasan tentang Rekursi.

5.

Penjelasan tentang Searching.

6.

Penjelasan tentang Sorting

7.

Penjelasan tentang Linked List.

8.

Penjelasan tentang Stack.

9.

Penjelasan tentang Queue.

10.

Penjelasan tentang Tree.

11.

Penjelasan tentang Graph.

C.

MAKSUD DAN TUJUAN

1.

Untuk memenuhi tugas dari dosen pada pada kuliah Struktur Data.

2.

Untuk menambah wawasan tentang beberapa rumusan masalah diatas.

1

BAB II PEMBAHASAN A.

DATA DAN STRUKTUR DATA

1.

Pengertian Data Data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang

kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol. Pengertian data ini menyiratkan suatu nilai yang bisa dinyatakan dalam bentuk konstanta / variable. Konstanta digunakan untuk menyatakan nilai tetap sedangkan variable digunakan dalam program untuk menyatakan nilai yang dapat berubah-ubah selang eksekusi berlangsung. Ada empat istilah data, yaitu: 1.

Tipe data adalah jenis atau macam data di dalam suatu variable dalam bahasa pemrograman.

2.

Objek data mengacu kumpulan elemen, D (domain).

3.

Representasi data : Suatu mapping dari struktur data ‘d’ ke suatu set ke struktur data ‘e’ (d===e) misal bolean di representasikan dalam 0 dan 1.

4.

Struktur data biasa dipakai untuk mengelompokan beberapa informasi yang terkait menjadi sebuah kesatuan.

Tipe data sederhana terbagi menjadi dua, yaitu: 1.

Data sederhana tunggal.Misalnya : Integer, real / float, Boolean dan character.

2.

Data sederhana majemuk. Misalnya : String.

2.

PENGERTIAN STRUKTUR DATA Struktur data adalah suatu koleksi / kelompok data yang dapat di

karakteristikan oleh organisasi serta operasi yang di definisikan terhadapnya.

2

Dalam teknik pemrograman,struktur data berarti tata letak yang berisi kolom-kolom data,baik itu kolom yang tampak oleh pengguna (user) ataupun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Secara garis besar type data dapat dikategorikan menjadi : 

Struktur data sederhana tunggal, misalnya Integer, real, boolean, dan karakter.



Struktur data sederhana majemuk, misalnya String.

Struktur data meliputi: 

Struktur data sederhana, misalnya array dan record.



Struktur data majemuk, yang terdiri dari : 

Linier : Stack, Queque, serta List dan Multilist



Non Linier : Pohon Biner dan Graph

Pemakaian struktur data yang tepat di dalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana. B.

STRING

1.

Pengertian String dalam Bahasa Pemrograman String pada dasarnya adalah kumpulan dari karakter-karakter (karakter

bertipe data char). Penulisan string harus diawali den diakhiri dengan tanda petik dua (“), sedangkan karakter harus diawali dan diakhiri dengan tanda petik satu (‘). Misalnya : Penulisan string : string A = “gaji”; Penulisan karakter : char A = ‘g’; Dalam pembahasan tentang Character, kita mengetahui bahwa tipe data karakter berhubungan dengan satu karakter dan Anda dapat menetapkan karakter apapun dari keyboard Anda ke variabel tipe karakter. Sekarang, mari kita mempertimbangkan situasi di mana kita perlu menyimpan lebih dari satu karakter 3

dalam variabel. Kita telah melihat bahwa pemrograman C tidak memungkinkan untuk menyimpan lebih dari satu karakter dalam variabel tipe karakter. Jadi pernyataan berikut tidak valid dalam pemrograman C dan menghasilkan kesalahan sintaks. Kita juga telah melihat bagaimana menggunakan konsep array untuk menyimpan lebih dari satu nilai tipe data sejenis dalam sebuah variabel. Berikut adalah sintaks untuk menyimpan dan mencetak lima angka dalam array tipe int. 2.

Konsep Dasar String Berdasarkan pembahasan di atas, kita dapat menyimpulkan hal-hal penting

berikut tentang string dalam bahasa pemrograman C : 1. String dalam C diwakili sebagai array karakter. 2. Kita bisa membentuk sebuah string dalam pemrograman C dengan menugaskan karakter demi karakter ke dalam array karakter. 3. Kita bisa membentuk sebuah string dalam pemrograman C dengan menugaskan sebuah string lengkap yang disertakan dalam double quote 4. Kita bisa mencetak karakter string dengan karakter menggunakan subskrip array atau string lengkap dengan menggunakan nama array tanpa subskrip. 5. Karakter terakhir dari setiap string adalah karakter null, yaitu, '\ 0'. 6. Sebagian besar bahasa pemrograman menyediakan fungsi built-in untuk memanipulasi string, misalnya, Anda dapat menggabungkan string, Anda dapat mencari dari sebuah string, Anda dapat mengekstrak sub-string dari string, dll. Untuk lebih lanjut, Anda dapat memeriksa tutorial terperinci tentang Pemrograman C atau bahasa pemrograman lainnya. 3.

String dalam Bahasa Java Meskipun Anda dapat menggunakan array karakter untuk menyimpan string,

namun Java adalah bahasa pemrograman tingkat lanjut dan para perancangnya berusaha memberikan fungsionalitas tambahan. Java menyediakan string sebagai tipe data built-in seperti tipe data lainnya. Ini berarti Anda dapat menentukan string secara langsung, bukan mendefinisikannya sebagai array karakter.

4

4.

Strings dalam Bahasa Python Python tidak mendukung tipe karakter; Ini diperlakukan sebagai string,

sehingga juga dianggap sebagai substring. Untuk mengakses substring, gunakan tanda kurung siku untuk mengiris beserta indeks C.

ARRAY

1.

Pengertian Array Array atau larik didefinisikan sebagai pemesanan alokasi memory

berurutan.Definisi ini kurang tepat, karena terjadi kerancuan antara struktur data dan representasinya. Memang benar array hampir selalu di implementasikan menggunakan memory berurutan tapi tidak selalu demikian. Semua elemem array bertipe sama. Array cocok untuk organisasi kumpulan data homogen yang ukuran atau jumlah elemen maksimumnya telah diketahui dari awal. Homogen adalah bahwa setiap elemen dari sebuah array tertentu haruslah mempunyai tipe data yang sama. 2.

3.

Karakteristik Array a.

Mepunyai batasan dari pemesanan alokasi memori (bersifat statis)

b.

Mempunyai tipe data sama (bersifat homogen)

c.

Dapat diakses secara acak.

Jenis Array a.

Array Dimensi Satu

Deklarasi : Type_Data Nama_Variabel [index] n (Index Array) i=1 Rumus untuk menentukan jumlah elemen dalam array adalah :  = Perkalian dari index sebelumnya (untuk arraybdimensi dua dan tiga).

5

Pemetaan (Mapping) Array Dimensi Satu Ke Storage Rumus

: @A[i] = B + (i – 1) * L

Dimana : @A[i]

b.

: Posisi array yang dicari

B

: Posisi awal index di memori computer

i

: Subkrip atau index array yang di cari

L

: Ukuran atau besar memori suatu tipe data

Array Dimensi Dua

Deklarasi

: Type_Data Nama_Variabel [index1] [index2]

N (Index Array) i=1 Menentukan jumlah elemen dalam array dimensi dua :  = Perkalian dari statemen sebelumnya Pemetaan (Mapping) Array Dimensi Dua Ke Storage Terbagi dua cara pandang (representasi) yang berbeda :Secara kolom per kolom (coloumn major order / CMO) @M[i][j] = M[0][0] + {(j – 1) * K + (i – 1)} * L

Secara baris per baris (row major order / RMO) @M[i][j] = M[0][0] + {(i – 1) * N + (j – 1)} * L

6

Keterangan : @M[i][j] = Posisi array yang di cari, M[0][0 = Posisi alamat awal index array, i = Baris, j = Kolom, L = Ukuran memory type data, K = Banyaknya elemen per kolom, N = Banyaknya elemen per baris. c.

Array Dimensi Tiga

Deklarasi

: type_Data Nama_Variabel [index1][index2][index3]

n (Index Array) i=1 Menentukan jumlah elemen dalam array dimensi tiga :  = Perkalian dari statemen sebelumnya Pemetaan (Mapping) Array Dimensi Tiga Ke Storage Rumus : @M[n][m][p] = M[0][0][0] + {((n – 1) *(index1)) + ((m – 1) * (index2))+ ((p – 1) * (index3)} * L

4.

Operasi Dasar pada Array Operasi terhadap elemen di array dilakukan dengan pengaksesan langsung.

Nilai di masing-masing posisi elemen dapat diambil dan nilai dapat disimpan tanpa melewati posisi-posisi lain. Terdapat dua tipe operasi, yaitu : 

Operasi terhadap satu elemen / posisi dari array



Operasi terhadap array sebagai keseluruhan

Dua operasi paling dasar terhadap satu elemen / posisi adalah

7



Penyimpanan nilai elemen ke posisi tertentu di array



Pengambilan nilai elemen dari posisi tertentu di array

Operasi-operasi dasar terhadap array secara keseluruhan adalah :

5.



Operasi penciptaan



Operasi penghancuran



Oparasi pemrosesan traversal



Operasi pencarian (table look-up)



Operasi sorting

Keunggulan dan Kelemahan Array a.

Keunggulan array adalah sebagai berikut : 1.

Array sangat cocok untuk pengaksesan acak. Sembarang elemen di array dapat diacu secara langsung tanpa melalui elemenelemen lain.

2.

Jika berada di suatu lokasi elemen, maka sangat mudah menelusuri ke elemen-elemen tetangga, baik elemen pendahulu atau elemen penerus 3.

3.

Jika elemen-elemen array adalah nilai-nilai independen dan seluruhnya harus terjaga,maka penggunaan penyimpanannya sangat efisien.

b.

Kelemahan array adalah sebagai berikut : Array mempunyai fleksibilitas rendah, sehingga tidak cocok untuk

berbagai aplikasi karena array mempunyai batasan sebagai berikut : 1.

Array harus bertipe homogen. Kita tidak dapat mempunyai array dimana satu elemenadalah 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 terjaditerus-menerus, maka representasi statis.

8

D.

REKURSI Rekursi adalah konsep pengulangan yang penting dalam ilmu komputer.

Konsep ini dapat digunakan untuk merumuskan solusi sederhana dalam sebuah permasalahan yang sulit untuk diselesaikan secara iteratif dengan menggunakan loop for, while do. Pada saat tertentu konsep ini dapat digunakan untuk mendefinisikan permasalahan dengan konsisten dan sederhana. Pada saat yang lain, rekursi dapat membantu untuk mengekspresikan algoritma dalam sebuah rumusan yang menjadikan tampilan algoritma tersebut mudah untuk dianalisa. 1.

Rekursi Dasar Rekursi mempunyai arti suatu proses yang bias memanggil dirinya sendiri.

Dalam sebuah rekursi sebenarnya tekandung pengertian sebuah prosedur atau fungsi. Perbedaannya adalah bahwa rekursi bisa memanggil dirinya sendiri, kalau prosedur atau fungsi harus diipanggil melalui pemanggil prosedur atau fungsi. Untuk memulai bahasan rekursi, kita membahas sebuah masalah sederhana yang kemungkinan kita tidak berpikir untuk menyelesaikan dengan cara rekursif. Yaitu permasalahan faktorial, yang mana kita menghitung hasil faktorial dari sebuah bilangan, yaitu n. Faktorial dari n (ditulis n!), adalah hasil kali dari bilangan tersebut dengan bilangan di bawahnya, di bawahnya hingga bilangan 1. Sebagai contoh, 4! = (4)(3)(2)(1). Salah satu cara untuk menghitung adalah dengan menggunakan loop, yang mengalikan masing-masing bilangan dengan hasil sebelumnya. Penyelesaian dengan cara ini dinamakan iteratif, yang mana secara umum dapat didefinisikan sebagai berikut: n! = (n)(n-1)(n-2) … (1) Cara lain untuk menyelesaikan permasalahan di atas adalah dengan cara rekursi, dimana n! adalah hasil kali dari n dengan (n-1)!. Untuk menyelesaikan (n1)! adalah sama dengan n!, sehingga (n-1)! adalah n-1dikalikan dengan (n-2)!, dan (n-2)! adalah n-2 dikalikan dengan (n-3)! dan seterusnya sampai dengan n = 1, kita menghentikan penghitungan n! Cara rekursif untuk permasalahan ini, secara umum dapat kita detailkan sebagai berikut:

9

1 F(n) =

jika n=0, n=1 nF(n-1)

jika n>1

Pada Gambar 5.1 dibawah ini digambarkan penghitungan 4! dengan menerapkan konsep rekursi. Dalam gambar tersebut juga digambarkan dua fase dasar dari sebuah proses rekursi: fase awal dan fase balik. Dalam fase awal, masingmasing proses memanggil dirinya sendiri. Fase awal ini berhenti ketika pemanggilan telah mencapai kondisi terminal. Sebuah kondisi teminate adalah kondisi dimana sebuah fungsi rekursi kembali dari pemanggilan, artinya fungsi tersebut sudah tidak memanggil dirinya sendiri dan kembali pada sebuah nilai. Sebagai contoh, dalam penghitungan faktorial dari n, kondisi terminal adalah n = 1, n = 0. Untuk setiap fungsi rekursi, minimal harus ada satu kondisi terminal. Setelah fase awal selesai, kemudian proses melanjutkan pada fase balik, dimana fungsi sebelumnya akan dikunjungi lagi dalam fase balik ini. Fase ini berlanjut sampai pemanggilan awal, hingga secara lengkap proses telah berjalan.

F(4)=4x F(3)

fase awal

F(3)=3x F(2)

.

F(2)=2x F(1) F(1)=1 F(2)=(2)x(1) F(3)=(3)x(2)

. kondisi terminal fase balik .

F(4)=(4)x (6)

.

24

rekursi lengkap

Gambar 1 Proses Komputasi Secara Rekursif dari 4! 10

Dalam Program 5.1 ditampilkan sebuah fungsi dalam C, fact_rec, dengan parameter sebuah bilangan n dan menghitung faktorial secara rekursi. Fungsi tersebut bekerja sebagai berikut. Jika n kurang dari 0, maka fungsi kembali ke 0, menunjukkan kesalahan. Jika n = 0 atau 1, fungsi kembali ke 1 karena 0! dan 1! hasilnya 1. Dan ini adalah kondisi terminal. Selainnya itu, fungsi kembali dengan hasil n kali factorial dari n-1. Faktorial dari n-1 adalah penghitungan kembali secara rekursif dengan memanggil fact lagi. Perhatikan persamaan dari definisi rekursi dengan implementasi di bawah ini. int fact_rec(int n) { /************************************************************ *

Menghitung sebuah faktorial secara rekursif

*

************************************************************/ if (n < 0) return 0; else if (n == 0) return 1; else if (n == 1) return 1; else return n * fact(n-1); } Program 1 Fungsi Implementasi dari Proses Komputasi Faktorial secara Rekursif

11

Jika kita perhatikan dari fungsi rekursi di atas, maka kita lihat adanya kondisi terminal yang kita cantumkan dalam program tersebut, yaitu jika n = 0 atau n = 1. Hal ini harus kita lakukan dalam setiap fungsi rekursif. Jika tidak, maka eksekusi tidak akan pernah berhenti. Akibatnya memori tumpukan akan habis dan komputer akan hang. Selain itu kita dapat membandingkan proses rekursi di atas dengan proses iteratif, seperti di bawah ini: int fact_it (int n) { int temp; /************************************************************ *

Menghitung sebuah faktorial dengan proses looping *

************************************************************ /

temp = 1; if (n < 0)

return 0; else if (n == 0) return 1; else if (n == 1) return 1; else for (i=2; i<=n; ++i) temp = temp * i; return (temp); }

12

Program 2 Fungsi Implementasi dari Proses Komputasi Faktorial secara Iteratif 2.

Rekursi Tail Sebuah proses rekursi dikatakan rekursi tail jika pernyataan terakhir yang

akan dieksekusi berada dalam tubuh fungsi dan hasil yang kembali pada fungsi tersebut bukanlah bagian dari fungsi tersebut. Ciri fungsi rekursi tail adalah fungsi tersebut tidak memiliki aktivitas selama fase balik. Ciri ini penting, karena sebagian besar kompiler modern secara otomatis membangun kode untuk menuju pada fase tersebut. Ketika kompiler mendeteksi sebuah pemanggilan yang mana adalah rekursi tail, maka kompiler menulis aktivitas yang ada sebagai sebuah record

yang

dimasukkan ke dalam stack. Kompiler dapat melakukan hal tersebut karena pemanggilan rekursi adalah pernyataan terakhir yang dieksekusi dalam aktivitas yang sedang berlangsung, sehingga tidak ada aktivitas yang harus dikerjakan pada saat pemanggilan kembali. Untuk memahami bagaimana sebuah rekursi tail bekerja, kita akan kembali membahas tentang penghitungan komputasi dari faktorial secara rekursi. Sebagai langkah awal, akan sangat membantu jika kita memahami alasan dalam definisi awal yang bukan rekursi tail. Dimana dalam definisi tersebut, penghitungan n! adalah dengan mengalikan n dengan (n-1)! dalam setiap aktivitas, yang mana hal tersebut terus diulang dari n = n –1 sampai n = 1. Definisi ini bukanlah rekursi tail karena nilai yang dikembalikan dalam setiap aktivitas bergantung pada perkalian n dengan nilai yang dikembalikan oleh aktivitas sesudahnya.

Oleh karena itu,

pencatatan aktivitas dari masing-masing pemanggilan harus diingat dalam stack sampai nilai-nilai yang dikembalikan dalam aktivitas-aktivitas sesudahnya telah terdefinisi. Sekarang marilah kita melihat bagaimana rekursi tail didefinisikan untuk menghitung n!, yang secara formal kita definisikan sebagai berikut:

13

a F(n,a) =

jika n=0, n=1 F(n-1,na) jika n>1

Pada definisi ini digunakan parameter kedua, yaitu a, yang mana merupakan nilai utama dari penghitungan faktorial secara rekursif. Hal ini mencegah kita untuk mengalikan nilai yang dikembalikan dalam setiap aktivitas dengan n. Dalam masingmasing pemanggilan rekursi kita mendefinisikan a = na dan n = n – 1. Kita melanjutkan sampai n = 1, sebagai kondisi terminal. Dalam gambar 2 menggambarkan proses komputasi 4! dengan menggunakan rekursi tail. Perhatikan bahwa di sana tidak ada aktivitas selama fase balik. F(4,1)=F(3,4)

fase awal

F(3,4)=F(2,12)

F(2,12)=F(1,24)

.

.

F(1,24)=24 24

kondisi terminal fase balik rekursi lengkap

Gambar 2 Proses Komputasi 4! dengan Rekursi Tail Program 3 mempresentasikan sebuah fungsi dalam bahasa C, yang menerima sebuah bilangan n dan menghitung faktorialnya dengan menggunakan rekursi tail. Fungsi ini juga menerima parameter tambahan, yaitu a, untuk initial pertama diset 1. Fungsi ini hampir sama dengan fact pada Program 1, kecuali dia menggunakan a untuk mengelola lebih jauh nilai dari komputasi faktorial dalam proses rekursi. /************************************************************ *

Fungsi Rekursi Tail

*

****************************************************** *******/ int facttail(int n, int a) {

14

/************************************************************ *

Menghitung sebuah faktorial dengan rekursi tail

*

************************************************************/ if (n < 0) return 0; else if (n == 0) return 1; else if (n == 1) return a; else return facttail(n-1,n*a); } Program 3 Fungsi Implementasi Proses Komputasi Faktorial 4! dengan Rekursi Tail E.

SEARCHING Dalam pencarian data juga terdapat beberapa jenis algoritma, tujuan dari

adanya banyak algoritma yang di temukan adalah karena memiliki keuntungankeuntungan tersendiri, seperti lebih cepatnya bila mengolah data yang jumlahnya lebih dari juta data, ada yang lebih efisien dengan jumlah kurang dari jutaan. serta ada pula yang tidak perlu untuk mengurutkan data terlebih dahulu, tetapi memakan waktu lebih lama.

15

1.

Line Search teknik searching ini dibuat dengan cara melakukan pengecek’an 1 persatu,

yaitu antara data yang di cari dengan kumpulan data yang di miliki, Keuntungan metode ini adalah kita tidak perlu mengurutkan data yang ada, bila mencari data pada kumpulan data yang tidak urut hanya terdapat metode ini yang dapat di lakukan. 2.

Binnary Search teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di

urutkan, karena teknik ini melakukan pencarian dengan mencari data pada index yang tengah, apakah lebih besar/lebih kecil/sama dengan. bila hasil sama dengan maka nilai yang di cari telah di temukan. bila lebih kecil/lebih besar maka akan di buang setengah data dari yang salah, dan mencari dari indeks yang tengah dari sisanya. demikian samapi data ditemukan atau tidak di temukan. 3.

Fibonachi Search Teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di

urutkan, karena teknik ini melakukan pencarian dengan mencari data melalui pola bilangan fibonachi. Bila pada binnary search pembandingnya adalah nilai pada index tengahnya jumlah data, pada fibonachi search berbeda yaitu: bilangan fibonachi, yang bilangan fibonachinya terdekat dengan jumlah data tetapi tidak lebih besar dari jumlah data yang akan di proses. Bilangan fibonachi itu di jumlahkan dengan batas paling awal data dikurangi 1. Contohnya: jumlah data yang akan di cari adalah 15, maka batas paling bawah adalah 1 dan batas paling akhir=15 dan index pembandingnya= 13(nilai awal + dijumlahkan Bilangan fibonachi – 1) karena bilangan fibonachi terdekat dengan 15 (data ke 1- data ke 15) adalah 13 (1,2,3,5,8,13,21,34…..), bila data yang di cari lebih besar dari bilangan indeks ke tengahnya maka. batas paling bawah= tetap, batas akhir nilai tengah-1, bila data yang dicari lebih kecil maka batas bawah = nilai tengah +1 dan batas akhir tetap, sedangkan nilai tengahnya memakai fungsi tadi.

16

F.

SORTING Dalam penyelesaian suatu masalah pasti terdapat banyak cara atau solusi-

solusi yang dapat dilakukan, seperti halnya pembuatan program memiliki banyak tehnik atau algoritma yang dapat di gunakan salah satunya untuk kebutuhan sorting atau pengurutan kumpulan data-data. terdapat 4 algoritma atau tehnik dalam melakukan sorting. 

Straight Selection Sort. teknik sorting ini dibuat dengan cara melakukan pengecek’an 1 persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecek’an nilai tempat yang pertama (index pertama pada array) bila lebih kecil daripada index berikutnya (index 1 dengan index 2, index 1 dengan index 3, ….. index 1 dengan index terakhi) maka kita lakukan pertukaran nilai pada array index tersebut. proses ini dilakukan terus menerus sampai pada pengecekan index terakhir – 1 dengan nidex terakhir.



Selection Sort.Teknik sorting ini dibuat dengan cara melakukan pengecek’an 1 persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecek’an nilai tempat yang pertama (index pertama pada array)kita bandingkan dengan semua nilai yang ada kita cari nilai minimalnya. lalu simpan index/ letak nilai minimum itu di temukan, setelah pengecekan selesai tukar index awal pengecekan dengan nilai minimum yang telah di simpan tadi. Proses ini dilakukan terus menerus sampai pada pengecekan index terakhir min 1 dengan index terakhir. beda dengan streith selection sort adalah dengan teknik ini melakukan pertukaran nilai lebih sedikit, hanya jumlah data – 1 pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.



Bubble Sort. Teknik ini dilakukan degan pola membawa nilai terbesar menjadi nilai index terakhir array. jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data – 1.

17



Modified Bubble Sort. Teknik ini dilakukan degan pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.

G.

LINKED LIST

1.

Pengertian Linked List Link List adalah sekumpulan elemen bertipe sama yang mempunyai

keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian. Struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer (alamat elemen). Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik, walau tidak bersebelahan secara fisik di memori. 2.

Single Linked List

Pada gambar di atas, tampak bahwa sebuah data terletak pada sebuah lokasi memori area. Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variable pointer. Susunan berupa

18

untaian semacam ini disebut Single Linked List (NULL memiliki nilai khusus yang artinya tidak menunjuk ke mana-mana, biasanya Linked List pada titik akhirnya akan menunjuk ke NULL). Pembuatan Single Linked List dapat menggunakan 2 metode:

3.

•

LIFO (Last In First Out), aplikasinya: Stack (tumpukan)

•

FIFO (First In First Out), aplikasinya: Queue (antrean)

Double Linked List Salah satu kelemahan Single Linked List adalah pointer hanya dapat bergerak

satu arah saja, maju/mundur, kanan/kiri, sehingga pencarian data pada Single Linked List hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode Double Linked List. Linked List ini dikenal dengan nama Linked List berpointer ganda atau Double Linked List. 4.

Circular Double Linked List Merupakan Double Linked List yang simpul terakhirnya menunjuk ke simpul

terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir, sehingga membentuk suatu lingkaran. 5.

Operasi-Operasi yang ada pada Linked List a.

Insert: istilah insert berarti menambahkan sebuah simpul baru ke dalam suatu Linked List.

b.

IsEmpty: fungsi ini menentukan apakah Linked List kosong atau tidak.

c.

FindFirst: fungsi ini mencari elemen pertama dari Linked List.

d.

Find Next: fungsi ini mencari elemen sesudah elemen yang ditunjuk now.

e.

Retrieve: fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

f.

Update: fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.

19

g.

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 berikut.

h.

Delete Head: fungsi ini menghapus elemen yang ditunjuk head, head berpindah ke elemen sesudahnya.

i.

Clear: fungsi ini menghapus Linked List yang sudah ada, fungsi ini wajib dilakukan bila anda ingin mengakhiri program

yang

menggunakan Linked List, jika dilakukan, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori. H.

STACK

1.

Pengertian Stack Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan

dalam satu lajur linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi ATAS (TOP) tumpukan. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur. Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack. Tumpukan disebut juga “Push Down Stack” yaitu penambahan elemen baru (PUSH)ndan penghapusan elemen dari tumpukann(POP). Contoh pada PDA (Push Down Automaton). Sistem pada pengaksesan pada tumpukan menggunakn system LIFO (Last In First Out), artinya elemen yang terakhir masuk itu yang akan pertama dikeluarkan dari tumpukan (Stack). Ilustrasi tumpukan (Stack) dapat digambarkan seperti tumpukan CD atau tumpukan sate. Stack merupakan suatu susunan koleksi data dimana dapat ditambahkan dan dihapus selalu dilakukan pada bagian akhir data, yang disebut dengan Top Of Stack.

20

Sebelum struktur data tumpukan ini bisa digunakan, harus dideklarasikan dahulu dalam kamus data. Ada beberapa cara pendeklarasian struktur data ini, salah satunya dengan menggunakan tata susunan linear (larik) dan sebuah variable, yang dikemas dalam tipe data record. Stack (tumpukan) adalah struktur data bertipe record yang terdiri dari field elemen, bertipe larik/array dengan indek dari 1 sampai dengan MaksTum (Maksimum Tumpukan), atas, bertipe interger berkisar dari 0 (saat kosong) sampai dengan MaksTum (Maksimum Tumpukan). 2.

Operasi – operasi pada Stack Operasi yang sering diterapkan pada struktur data Stack (Tumpukan) adalah

Push dan Pop. Operasi – operasi yang dapat diterapkan adalah sebagai berikut : a.

Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.

b.

Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.

c.

Clear : digunakan untuk mengosongkan Stack.

d.

Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.

e.

MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.

f.

IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.

g.

Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

Pada proses Push, Tumpukan (Stack) harus diperiksa apakah jumlah elemen sudah mencapai masimum atau tidak. Jika sudah mencapai maksimum maka OVERFLOW, artinya Tumpukan penuh tidak ada elemen yang dapat dimasukkan ke dalam Tumpukan. Sedangkan pada proses Pop, Tumpukan harus diperiksa apakah ada elemen yang hendak dikeluarkan atau tidak. Jika tidak ada maka UNDERFLOW, artinya tumpukan kosong tidak ada elemen yang dapat diambil.

21

3.

Macam–Macam Stack a.

Stack dengan Array Sesuai dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus dimulai dari elemen teratas.

b.

Double Stack dengan Array Metode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.

I.

QUEUE

1.

Pengertian Queue Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan

Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur. Tumpukan disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue jika diartikan secara harfiah, queue berarti antrian. Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk membeli tiket. Istilah yang cukup sering dipakai apabila seseorang masuk dalam sebuah antrian adalah enqueue. Sedang istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue. 2.

Operasi-Operasi pada Queue a.

Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.

22

b.

Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.

c.

EnQueue : berfungsi memasukkan data kedalam antrian.

d.

DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.

e.

Clear : Menghapus seluruh Antrian

f.

IsEmpty : memeriksa apakah antrian kosong

g.

IsFull : memeriksa apakah antrian penuh.

J.

TREE

1.

Pengertian Tree Tree merupakan salah satu bentuk struktur data tidak linear yang

menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop. Sebuah binary search tree (bst) adalah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. Value pada semua node subpohon sebelah kiiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing-masing subpohon tersebut (kiri dan kanan) itu sendiri adalah juga binary search tree. Struktur data bst sangat penting dalam struktur pencarian, misalkan dalam kasus pencarian dalam sebuah list, jika list sudah dalam keadaan terurut maka proses pencarian akan semakin cepat, jika kita menggunakan list contigue dan melakukan pencarian biner,akan tetapi jika kita ingin melakukan perubahan isi list (insert atau delete), menggunakan list contigue akan sangat lambat, karena prose insert dan delete dalam list contigue butuh memindahkan linked-list, yang untuk operasi insert atau delete tinggal mengatur- atur pointer,akan tetapi pada n-linked list, kita tidak bisa melakukan pointer sembarangan setiap saat, kecuali hanya satu kali dengan kata lain hanya secara squential.

23

2.

Pengertian Binary Tree Binary Tree merupakan salah satu bentuk struktur data tidak linear yang

menggambarkanhubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya ( disebut subtree). Dalam tree terdapat jenis-jenis tree yang memiliki sifat khusus, diantaranya adalah binary tree. Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya dinamakan kiri dan kanan. Binary Tree merupakan himpunan vertex-vertex yang terdiri dari 2 subtree (dengan disjoint) yaitu subtree kiri dan subtree kanan. Setiap vertex dalam binary tree mempunyai derajat keluar max = 2.

Sebuah pohon biner adalah grafik asiklis yang terhubung dimana setiap tingkatan dari susut tidak lebih dari 3. Ini dapat ditunjukkan bahwa dalam pohon biner manapun, terdapat persis dua atau lebih simpul dengan tingkat satu daripada yang terdapat dengan tingkat tiga, tetapi bisa terdapat angka apa saja dari simpul dengan tingkat dua. Sebuah pohon biner berakar merupakan sebuah grafik yang mempunyai satu dari sudutnya dengan tingkat tidak lebih dari dua sebagai akar. Dengan akar yang dipilih, setiap sudut akan memiliki ayah khusus, dan diatas dua anak bagaimanapun juga, sejauh ini terdapat keterbatasan informasi untuk membedakan antara anak kiri atau kanan. Jika kita membuang keperluan yang tak

24

terkoneksi, membolehkan bermacam koneksi dalam komponen di grafik, kita memanggil struktur sebuah hutan. Sebuah jalan lain untuk mendefinisikan pohon biner melalui definisi rekursif pada grafik langsung. Sebuah pohon biner dapat berarti : 

Sebuah sudut tunggal.



Sebuah graf yang dibentuk dengan mengambil dua pohon biner, menambahkan sebuah sudut, dan menambahkan sebuah panah langsung dari sudut yang baru ke akar dai setiap pohon biner. Pohon biner dapat dikontruksi dari bahasa pemrogaraman primitif dalam

berbagai cara. Dalam bahasa yang menggunakan records dan referensi. Pohon biner secara khas dikontruksi dengan mengambil sebuah struktur simpul pohon yang memuat beberapa data dan referensi ke anak kiri dan anak kanan. Kadang-kadang itu juga memuat sebuah referensi ke ayahnya yang khas. Jika sebuah simpul mempunyai kurang dari dua anak, beberapa penunjuk anak diaatur kedalam nilai nol khusus atau kesebuah simpul sentinel. Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong). Metode ini menguntungkan dari banyak penyimpanan yang rapat dan memiliki referensi lokal yang lebih baik, teristimewa selama sebuah preordeer traversal. 3.

Istilah-Istilah dalam Tree a.

Predesesor ,Node yang berada diatas node tertentu. (contoh :

B

predesesor dari E dan F). b.

Succesor, Node yang berada dibawah node tertentu. (contoh : E dan F merupakan succesor dari B).

25

c.

Ancestor, Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama. (contoh : A dan B merupakan ancestor dari F).

d.

Descendant, Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama. (contoh : F dan B merupakan ancestor dari A).

e.

Parent, Predesesor satu level diatas satu node. (contoh : B merupakan parent dari F).

f.

Child, Succesor satu level dibawah satu node .(contoh : F merupakan child dari B).

g.

Sibling, Node yang memiliki parent yang sama dengan satu node. (contoh : E dan F adalah sibling) .

h.

Subtree, Bagian dari tree yang berupa suatu node beserta descendantnya. (contoh : Subtree B, E, F dan Subtree D, G, H).

i.

Size, Banyaknya node dalam suatu tree (contoh : gambar tree diatas memiliki size = 8).

j.

Height, Banyaknya tingkat/level dalam suatu tree (contoh : gambar tree diatas memiliki height = 3).

k.

Root (Akar), Node khusus dalam tree yang tidak memiliki predesesor (Contoh : A)

l.

Leaf (Daun), Node-node dalam tree yang tidak memiliki daun (contoh : Node E,F,C,G,H)

m.

Degree (Derajat), Banyaknya child yang dimiliki oleh suatu node (contoh : Node A memiliki derajat 3, node B memiliki derajat 2)

4.

Istilah pada Binary Tree a.

Pohon Biner Penuh (Full Binary Tree) Semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki panjang ruas yang sama.

26

b.

Pohon Biner Lengkap (Complete Binary Tree) Hampir sama dengan Pohon BinerPenuh, semua simpul (kecualidaun) memiliki 2 anak tetapi tiap cabang memiliki panjang ruas berbeda.

c.

Pohon Biner Similer Dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda.

d.

Pohon Biner Ekivalent Dua pohon yang memiliki struktur dan informasi yangsama.

e.

Pohon Biner Miring (Skewed Tree) Dua pohon yang semua simpulnya mempunyai satu anak / turunan kecuali daun.

27

K.

GRAPH

1.

Pengertian Graph Graph / Graf adalah kumpulan noktah (simpul) di dalam bidang dua dimensi

yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge). Graf merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Seringkali graf digunakan untuk merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkan setiap kotanya sebagai sisi (edge) yang bobotnya (weight) adalah panjang dari jalan tersebut. Ada beberapa cara untuk menyimpan graph di dalam sitem komputer. Struktur data bergantung pada struktur graph dan algoritma yang digunakan untuk memmanipulasi graph. Secara teori salah satu dari keduanya dapat dibedakan antara struktur list dan matriks, tetapi dalam penggunaannya struktur terbaik yang sering digunakan adalah kombinasi keduanya. 

Graph tak berarah (undirected graph atau non-directed graph) : • Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur AB atau BA



Graph berarah (directed graph) :

28

• Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA adalah e8. 

Graph Berbobot (Weighted Graph) : • Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot. • Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

2.

Istilah-istilah dalam Graph a.

Vertex Adalah himpunan node / titik pada sebuah graph.

b.

Edge Adalah himpunan garis yang menghubungkan tiap node / vertex.

c.

Adjacent Adalah dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident dengan titik v2 dan titik v3, tetapi sisi e3 = v2v3 tidak insident dengan titik v1 dan titik v4. Titik v1 adjacent dengan titik v2 dan titik v3, tetapi titik v1 tidak adjacent dengan titik v4.

d.

Weight Adalah Sebuah graf G = (V, E) disebut sebuah graf berbobot (weight

29

graph), apabila terdapat sebuah fungsi bobot bernilai real W pada himpunan

E,

W : E ® R, nilai W(e) disebut bobot untuk sisi e, " e Î E. Graf berbobot tersebut dinyatakan pula sebagai G = (V, E, W). Graf berbobot G = (V, E, W) dapat menyatakan * suatu sistem perhubungan udara, di mana · V = himpunan kota-kota · E = himpunan penerbangan langsung dari satu kota ke kota lain · W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu * suatu sistem jaringan komputer, di mana · V = himpunan komputer · E = himpunan jalur komunikasi langsung antar dua komputer · W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu e.

Path Adalah Walk dengan setiap vertex berbeda. Contoh, P = D5B4C2A Sebuah walk (W) didefinisikan sebagai urutan (tdk nol) vertex & edge. Diawali origin vertex dan diakhiri terminus vertex. Dan setiap 2 edge berurutan adalah series. Contoh, W = A1B3C4B1A2.

f.

Cycle Adalah Siklus ( Cycle ) atau Sirkuit ( Circuit ) Lintasan yang berawal dan berakhir pada simpul yang sama

3.

Representasi Graf Dalam pemrograman, agar data yang ada dalam graph dapat diolah, maka

graph harus dinyatakan dalam suatu struktur data yang dapat mewakili graph

30

tersebut. Dalam hal ini graph perlu direpresentasikan kedalam bentuk array dan dimensi yang sering disebut matrix atau direpresentasikan dalam bentuk linked list. Bentuk mana yang dipilih biasanya tergantung kepada efisiensi dan kemudahan dalam membuat program.

31

BAB III PENUTUP A.

KESIMULAN Struktur data merupakan salah satu bahan dasar pembuatan program.

Pemakaian struktur data yang tepat di dalam proses pemrograman, akan menghasilkan algoritma yang jelas dan tepat sehingga menjadikan program secara keseluruhan lebih sederhana. Bahasan diatas merupakan bagian dari struktur data yaitu termasuk kedalam struktur data sederhana yang dapat di definisikan sebagai pemesanan alokasi memory sementara pada komputer. Apabila kita membuat program dengan data yang sudah kita ketahui batasnya maka kita menggunakan Array (type data statis), namun apabila datanya belum kita ketahui batasnya maka gunakan pointer (type data dinamis), dan juga tipe yang lainnya juga. B.

SARAN Menyadari bahwa makalah ini masih jauh dari kata sempurna, kedepannya

penyusun akan lebih fokus dan detail dalam menjelaskan tentang makalah di atas dengan

sumber-sumber

yang

lebih

banyak

yang

tentunya

dapat

dipertanggungjawabkan. Untuk saran bisa berupa kritik atau saran terhadap penyusun juga bisa untuk menanggapi terhadap kesimpulan dari bahasan makalah yang telah dijelaskan.

32

DAFTAR PUSTAKA http://dyananyun.blogspot.com/2010/02/struktur-data-array.html http://kintung05.wordpress.com/2008/11/23/pengertian-struktur-data/ http://www.nusinau.com/pengertian-struktur-data-2/ http://www.nusinau.com/pengenalan-array-dan-string/ http://strukturdata18.blogspot.com/2013/05/makalah-struktur-dar.html http://www.sistem-informasi.xyz/2017/09/pengertian-string-dalam-bahasa.html https://id.pdfcoke.com/document/370433685/Makalah-Fungsi-Dan-Rekursi https://andikafisma.wordpress.com/teknik-sorting-dan-teknik-searching/ https://www.slideshare.net/Fajar_Sany/linked-list-dalam-strukturdata?from_action=save https://furqonubd.wordpress.com/2013/05/20/stack-and-queue/ http://t4urusboy08.blogspot.com/

33