Skip to content

Materi – materi yang di berikan pada perkuliahan struktur data

January 16, 2011

1.POINTER

Pointer merupakan tipe data berukuran 32 bit yang berisi satu nilai yang berpadanan

dengan alamat memori tertentu. Sebagai contoh, sebuah variabel P bertipe pointer

bernilai 0x0041FF2A, berarti P menunjuk pada alamat memori 0041FF2A. Pointer

dideklarasikan seperti variabel biasa dengan menambahkan tanda * (asterik) yang

mengawali nama variabel.

2. ARRAY

Array adalah suatu struktur yang terdiri dari sejumlah elemen yang memiliki tipe data

yang sama. Elemen-elemen array tersusun secara sekuensial dalam memori komputer.

Array dapat berupa satu dimensi, dua dimensi, tiga dimensi ataupun banyak dimensi

(multi dimensi).

2.1. Array Satu Dimensi

Array Satu dimensi tidak lain adalah kumpulan elemen-elemen identik yang tersusun

dalam satu baris. Elemen-elemen tersebut memiliki tipe data yang sama, tetapi isi dari elemen tersebut boleh berbeda.

2.2. Array Dua Dimensi

Array dua dimensi sering digambarkan sebagai sebuah matriks, merupakan perluasan

dari array satu dimensi. Jika array satu dimensi hanya terdiri dari sebuah baris dan

beberapa kolom elemen, maka array dua dimensi terdiri dari beberapa baris dan

beberapa kolom elemen yang bertipe sama

3. STRUCTURE

Structure (struktur) adalah kumpulan elemen-elemen data yang digabungkan menjadi satu kesatuan. Masing-masing elemen data tersebut dikenal dengan sebutan field. Field data tersebut dapat memiliki tipe data yang sama ataupun berbeda. Walaupun fieldfield tersebut berada dalam satu kesatuan, masing-masing field tersebut tetap dapat diakses secara individual.

Field-field tersebut digabungkan menjadi satu dengan tujuan untuk kemudahan dalam operasinya. Misalnya Anda ingin mencatat data-data mahasiswa dan pelajar dalam sebuah program, Untuk membedakannya Anda dapat membuat sebuah record

mahasiswa yang terdiri dari field nim, nama, alamat dan ipk serta sebuah record pelajar yang terdiri dari field-field nama, nonurut, alamat dan jumnilai. Dengan demikian akan lebih mudah untuk membedakan keduanya.

4. LINKED LIST

Pada bab sebelumnya telah dijelaskan mengenai variabel array yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu, ruang memori yang dipakai olehnya tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Untuk memecahkan masalah di atas, kita dapat menggunakan variable pointer. Tipe data pointer bersifat dinamis, variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat direlokasikan kembali.

Setiap ingin menambahkan data, Anda selalu menggunakan variabel pointer yang baru, akibatnya Anda akan membutuhkan banyak sekali pointer. Oleh karena itu, ada

baiknya jika Anda hanya menggunakan satu variabel pointer saja untuk menyimpan

banyak data dengan metode yang kita sebut Linked List. Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian.

4.1. Single Linked List

Pembuatan Single Linked List dapat menggunakan 2 metode:

LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)

FIFO (First In First Out), aplikasinya : Queue (Antrean)

LIFO ( Last In First Out)

Lifo adalah suatu metode pembuatan Linked List di mana data yang masuk paling akhir adalah data yang keluar paling awal. Hal ini dapat dianalogikan (dalam kehidupan sehari-hari) dengan saat Anda menumpuk barang seperti digambarkan dibawah ini. Pembuatan sebuah simpul dalam suatu linked list seperti digambarkan dibawah ini. Jika linked list dibuat dengan metode LIFO, terjadi penambahan / Insert simpul di belakang, dikenal dengan istilah INSERT.

FIFO (Fisrt In Fisrt Out)

FIFO adalah suatu metode pembuatan Linked List di mana data yang masuk paling awal adalah data yang keluar paling awal juga. Hal ini dapat di analogikan (dalam kehidupan sehari-hari), misalnya saat sekelompok orang yang datang (ENQUEUE) mengantri hendak membeli tiket di loket. Jika linked list dibuat dengan metode FIFO, terjadi penambahan / Insert simpul didepan.

4.2. Double Linked List

Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/ mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, anda dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.

4.3. Circular Double Linked List

Ini adalah double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu ingkaran.

Operasi-Operasi yang ada pada Linked List

Insert

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

IsEmpty

Fungsi ini menentukan apakah linked list kosong atau tidak.

Find First

Fungsi ini mencari elemen pertama dari linked list

Find Next

Fungsi ini mencari elemen sesudah elemen yang ditunjuk now.

Retrieve

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

Update

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

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.

Delete Head

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

sesudahnya.

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.

5. STACK

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.

Di C++, ada dua cara penerapan prinsip stack, yakni dengan array dan linked list. Setidaknya stack haruslah memiliki operasi-operasi sebagai berikut :

1. Push : Untuk menambahkan item pada tumpukan paling atas

2. Pop : Untuk mengambil item teratas

3. Clear : Untuk mengosongkan stack

4. IsEmpty : Untuk memeriksa apakah stack kosong

5. IsFull : Untuk memeriksa apakah stack sudah penuh

6. Retreive : Untuk mendapatkan nilai dari item teratas

5.1. Stack dengan Array

Sesuai dengan sifat stack, pengambilan / penghapusan di elemen dalam stack harus

dimulai dari elemen teratas.

Operasi-operasi pada Stack dengan Array

IsFull

Fungsi ini memeriksa apakah stack yang ada sudah penuh. Stack penuh jika puncak stack terdapat tepat di bawah jumlah maksimum yang dapat ditampung stack atau dengan kata lain Top = MAX_STACK -1.

Push

Fungsi ini menambahkan sebuah elemen ke dalam stack dan tidak bisa dilakukan lagi jika stack sudah penuh.

IsEmpty

Fungsi menentukan apakah stack kosong atau tidak. Tanda bahwa stack kosong adalah Top bernilai kurang dari nol.

Pop

Fungsi ini mengambil elemen teratas dari stack dengan syarat stack tidak boleh kosong.

Clear

Fungsi ini mengosongkan stack dengan cara mengeset Top dengan -1. Jika Top bernilai kurang dari nol maka stack dianggap kosong.

Retreive

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

5.2. 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. Tampak jelas bahwa sebuah array dapat dibagi untuk dua stack, stack 1 bergerak ke atas dan stack 2 bergerak ke bawah. Jika Top1 (elemen teratas dari Stack 1) bertemu dengan Top 2 (elemen teratas dari Stack 2) maka double stack telah penuh. Implementasi double stack dengan array adalah dengan memanfaatkan operasi-operasi yang tidak berbeda jauh dengan operasi single stack dengan array.

Operasi-operasi Double Stack Array

IsFull

Fungsi ini memeriksa apakah double stack sudah penuh. Stack dianggap penuh jika Top[0] dan Top[1] bersentuhan sehingga stack tida memiliki ruang kosong. Dengan kata lain, (Top[0] + 1) > Top[1].

Push

Fungsi ini memasukkan sebuah elemen ke salah satu stack.

IsEmpty

Fungsi memeriksa apakah stack pertama atau stack kedua kosong. Stack pertama dianggap kosong jika puncak stack bernilai kurang dari nol, sedangkan stack kedua dianggap kosong jika puncak stack sama atau melebihi MAX_STACK.

Pop

Fungsi ini mengeluarkan elemen teratas dari salah satu stack

Clear

Fungsi ini mengosongkan salah satu stack.

5.3. Stack dengan Single Linked List

Selain implementasi stack dengan array seperti telah dijelasnkan sebelumnya, ada cara lain untuk mengimplementasi stack dalam C++, yakni dengan single linked list.

Keunggulannya dibandingkan array tebtu saja adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori. Misalnya saja pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack. Oleh karena itu pula dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.

Operasi-operasi untuk Stack dengan Linked List

IsEmpty

Fungsi memeriksa apakah stack yang adamasih kosong.

Push

Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.

Pop

Fungsi ini mengeluarkan elemen teratas dari stack.

Clear

Fungsi ini akan menghapus stack yang ada.

6. QUEUE

Jika diartikan secara harafiah, queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehiduypan sehari-hari, misalnya saat Anda mengantri di loket untuk membeli tiket. Istilah yang cukup sering dipakai seseorang masuk dalam sebuah antrian adalah enqueue. Dalam suatu antrian, yang dating terlebih dahulu akan dilayani lebih dahulu. Istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.

Walaupun berbeda implementasi, struktur data queue setidaknya harus memiliki operasi-operasi sebagai berikut :

EnQueue : Memasukkan data ke dalam antrian

DeQueue : Mengeluarkan data terdepan dari antrian

Clear : Menghapus seluruh antrian

IsEmpty : Memeriksa apakah antrian kosong

IsFull : Memeriksa apakah antrian penuh

6.1. Implementasi Queue dengan Linear Array

Linear Array

Linear array adalah suatu array yang dibuat seakan-akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar. Berikut ini diberikan deklarasi kelas Queue Linear sebagai implementasi dari Queue menggunakan linear array. Dalam prakteknya, anda dapat menggantinya sesuai dengan kebutuhan Anda. Data diakses dengan field data, sedangkan indeks item pertama dan terakhir disimpan dalam field Head dan Tail. Konstruktor akan menginisialisasikan nilai Head dan Tail dengan -1 untuk menunjukkan bahwa antrian masih kosong dan mengalokasikan data sebanyak MAX_QUEUE yang ditunjuk oleh Data. Destruktor akan mengosongkan antrian kembali dan mendealokasikan memori yang digunakan oleh antrian.

Operasi-Operasi Queue dengan Linear Array

IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. hal ini dilakukan dengan mengecek apakah tail bernilai -1 atau tidak. Nilai -1 menandakan bahwa queue masih kosong.

IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bias menampung data dengan cara mengecek apakah nilai tail sudah sama dengan jumlah maksimal queue. Jika nilai keduanya sama, berarti queue sudah penuh.

EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen dalam queue.

DeQueue

Fungsi DeQueue berguna untuk mengambil sebuah elemen dari queue. Operasi ini sering disebut juga serve. Hal ini dilakukan dengan cara memindahkan sejauh satu langkah ke posisi di depannya sehingga otomatis elemen yang paling depan akan tertimpa dengan elemen yang terletak di belakangnya.

Clear

Fungsi Clear berguna untuk menghapus semua lemen dalam queue dengan jalan mengeluarkan semua elemen tersebut satu per satu hingga queue kosong dengan memanfaatkan fungsi DEQueue.

6.2. Implementasi Queue dengan Circular Array

Circular Array

Circular array adalah suatu array yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal (head) dan titik akhir (tail) saling bersebelahan jika array tersebut masih kosong. Posisi head dan tail pada gambar diatas adalah bebas asalkan saling bersebelahan. Berikut ini diberikan deklarasi kelas Queue Circular sebagai implementasi circular array. Dalam prakteknya, Anda dapat menggantikanny sesuai dengan kebutuhan Anda. Data diakses dengan field data, sedangkan indeks itemn pertama dan terakhir disimpan dalam field Head dan Tail. Konstruktor akan menginisialisasi nilai Head dan Tail dengan 0 dan MAX-QUEUE-1 untuk menunjukkan bahwa antrian masih kosong dan mengalokasikan data sebanyak MAX-QUEUE yang ditunjuk oleh Data. destruktor akan mengosongkan antrian kembali dan mendealokasikan memori yang digunakan oleh antrian.

Operasi-Operasi Queue dengan Circular Array

IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah Queue masih kosong atau sudah berisi. Hal ini dilakukan dengan mengecek apakah tail masih terletak bersebelahan dengan head dan tail lebih besar dari head atau tidak. Jika benar, maka queue masih

kosong.

IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bias menampung data dengan cara mengecek apakah tempat yang masih kosong tinggal satu atau tidak (untuk membedakan dengan empty dimana semua tempat kosong). Jika benar berarti queue penuh.

EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue tail dan head mula-mula bernilai nol (0).

DeQueue

DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara memindahkan posisi head satu langkah ke belakang.

6.3. Implementasi Queue dengan Double Linked List

Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list.

Operasi-operasi Queue dengan Double Linked List

IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.

IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bias

menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan

MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.

EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head

dan tail mula-mula meunjukkan ke NULL).

DeQueue

Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini

dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).

7. TREE

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan

hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Treebias didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebutRoot. Notde lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungansatu sama lain (disebut Subtree). Untuk lebih jelasnya, di bawah akan diuraikan istilahistilahumum dalam tree.

Predecessor Node yang berada di atas node tertentu

Successor Node yang berada dibawah node tertentu

Ancestor Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama

Descendant Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama

Parent Predecessor satu level di atas suatu node

Child Successor satu level di bawah suatu node

Sibling Node-node yang memiliki parent yang sama dengan suatunode

Subtree Bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

Size Banyaknya node dalam suatu tree

Height Banyaknya tingkatan / level dalam suatu tree

Root Satu-satunya node khusus dalam tree yang tak punyakpredecessor

Leaf Node-node dalam tree yang tak memiliki successor

Degree Banyaknya child yang dimiliki suatu node

7.1. Jenis-Jenis Tree

Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Jenis- Jenis Binary Tree :

Full Binary Tree

Jenis binary tree ini tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

Complete Binary Tree

Jenis ini mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki 2 child.

Skewed Binary Tree

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

Implementasi Binary Tree

Binary tree dapat diimplementasikan dalam C++ dengan menggunakan double linkedlist.

7.2. Operasi-Operasi pada Binary Tree

Create : Membentuk binary tree baru yang masih kosong

Clear : Mengosongkan binary tree yang sudah ada

Empty : Function untuk memeriksa apakah binary tree masih kosong

Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert : sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong

Find : Mencari root, parent, left child, atau right child dari suatu node. (tree tidak boleh kosong).

Update : Mengubah isi dari node yang ditunjuk oleh pointer curret (Tree tidak boleh kosong)

Retrieve : Mengetahui isi dari node yang ditunjuk oleh pointer current (Tree tidak boleh kosong)

DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tidak boleh kosong. Setelah itu, pointer current dakan berpindah ke parent dari node yang dihapus.

Characteristic : Mengetahui karakteristik dari suatu tree, yakni: size, height, serta average length. Tree tidak boleh kosong.

Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linear yang tersimpan dalam tree. Ada tiga cara traverse,yaitu PreOrder, InOrder, dan PostOrder.

Langkah-langkah Tranverse :

· PreOrder : cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child

· InOrder : kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right Child

· PostOrder : kunjungi Left Child, kunjungi Right Child cetak isi node yang dikunjungi.

7.3. Binary Search Tree

Binary Tree ini memiliki sifat dimana semua left child harus lebih kecil dari pada right child dan parentnya. Semua right child juga harus lebih besar dari left child serta parentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pendarian node tertentu dalam binary tree. Pada dasarnya operasi dalam Binary Search Tree sama dengan Binary Tree biasa, kecuali pada operasi insert, update, dan delete.

Insert

Pada Binary Search Tree insert dilakukan setelah lokasi yang tepat ditemukan (lokasi tidak ditentukan oleh user sendiri ).

Update

Update ini seperti yang ada pada Binary Tree biasa, namun di sini update akan berpengaruh pada posisi node tersebut selanjutnya. Bila update mengakibatkan tree tersebut bukan Binary Search Tree lagi, harus dilakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.

Delete

Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.

AVL Tree

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. Selain AVL Tree, terdapat pula Height Balanced n Tree, yakni Binary Search Tree yang memiliki perbedaan level antara subtree kiri dan subtree kanan maksimal adalah n sehingga dengan kata lain AVL Tree adalah Height Balanced 1 Tree. Untuk memudahkan dalam menyeimbangkan tree, digunakan simbol-simbol Bantu :

- (tanda minus) : digunakan apabila Subtree kiri lebih panjang dari Subtree kanan.

+ (tanda plus) : digunakan apabila Subtree kanan lebih panjang dari Subtree kiri.

0 (nol) : digunakan apabila Subtree kiri dan Subtree kanan mempunyai height yang sama.

About these ads

From → MATERI, Struktur Data

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: