Tree Atau Pohon Pada Struktur Data

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.

Deklarasi Pohon

Jika kita memperhatikan setiap simpul dalam pohon biner, kita bisa menyusun  struktur data yang tepat dari simpul-simpul tersebut. Kita dapat melihat bahwa dalam  setiap simpul selalu berisi dua buah pointer untuk menunjuk ke cabang kiri dan cabang  kanan, dan informasi yang akan disimpan dalamsimpul tersebut.

Berdasarkan gambar, maka deklarasi list yang sesuai adalah:

typedef char TypeInfo;

typedef struct Simpul *Tree;

struct Simpul {

TypeInfo Info;

tree Kiri, /* cabang kiri */

Kanan; /* cabang kanan */

};

Istilah Dalam Pohon

JENIS-JENIS POHON

1. Pohon Biner

Pohon dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua sub pohon dan kedua subpohon harus terpisah.

Kelebihan struktur pohon biner :

1. Mudah dalam penyusunan algoritma sorting

2. Searching data relatif cepat

3..  Fleksibel dalam penambahan dan penghapusan data.

KUNJUNGAN PADA POHON BINER

Sebuah pohon biner memiliki operasi  traversal  yaitu suatu kunjungan pada suatu simpul tepat satu kali. Dengan melakukan kunjungan lengkap kita akan memperoleh urutan informasi secara linier yang tersinpan di dalam pohon biner.

Terdapat tiga jenis kunjungan pada pohon biner, yaitu :

PREORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

-  Cetak isi simpul yang dikunjungi.

-  Kunjungi cabang kiri.

-  Kunjungi cabang kanan.

INORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

-  Kunjungi cabang kiri.

-  Cetak isi simpul yang dikunjungi.

-  Kunjungi cabang kanan.

POSTORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

-  Kunjungi cabang kiri.

-  Kunjungi cabang kanan.

-  Cetak isi simpul yang dikunjungi

Struct Dan Pointer

Struct

Definisi Struct

Definisi Struktur (struct) sendiri adalah kumpulan dari variabel yang dinyatakan dengan sebuah nama , dengan sifat setiap variabel dapat memiliki tipe yang berlainan. Struct digunakan untuk mengelompokkan sejumlah data yang mempunyai tipe dan ukuran yang berbeda.

Dalam pemrograman C++, jika kita membuat suatu program yang memerlukan berbagai tipe data yang akan digunakan. Tentunya dengan nama variable yang banyak pula. Dalam program yang sederhana, jika kita manggunakan sedikit variable tentu tidak jadi masalah. Akan tetapi jika kita akan membuat sebuah program yang lebih kompleks, dengan berbagai macam nama dan tipe variable dalam pendeklarasianya. Dengan struct, kita bisa mengelompokkan berbagai nama dan tipe variable tersebut sesuai dengan kelompoknya. Hal ini tentunya bisa berguna untuk memudahkan dalam mengelompokkan sebuah variable. Sebagai contoh umum, ada terdapat berbagai nama variable : nama, npm, alamat, dll. Variabel – variable tersebut dapat kita kelompokkan menjadi satu dengan nama data_mahasiswa. Kemudian jika terdapat variable mata_kuliah, nilai, sks, kelas, dll dapat kita kelompokkan menjadi satu dengan nama krs. Itulah sebagian gambaran umum tentang struct.

Dalam mendeklarasikan struct, ada beberapa cara penulisan yang biasa digunakan.

Pertama :

struct nama_struct {

tipe_data_1 nama_var_1;

tipe_data_2 nama_var_2;

tipe_data_3 nama_var_3;

……

};

Yang kedua adalah dengan deklarasi menggunakan typedef.

typedef struct {

tipe_data_1 nama_var_1;

..

.

tipe_data_n nama_var_n;

} nama_struct;

Kemudian untuk mendeklarasikan sebuah variable dengan tipe data struct yang telah dibuat sebelumnya adalah :

struct tipe_struct nama_variabel;

Jika pendeklarasian struct sebelumnya menggunakan typedef, maka untuk mendeklarasikan sebuah variable dengan tipe data struct adalah :

tipe_struct nama_variabel;

Dan untuk mengakses sebuah struct adalah dengan menggunakan operator titik (.) nama_var_struct . nama_var_elemen;

Nested Struct

Di dalam sebuah struct dapat dimungkinkan terdapat sebuah struct lagi. Jadi hal ini dapat diartikan struct di dalam struct. Hampir mirip nested loop, yaitu for di dalam for.

POINTER

Pengertian Pointer

Pointer (variabel penunjuk) adalah suatu variabel yang berisi alamat memori dari suatu variabel lain. Alamat ini merupakan lokasi dari obyek lain (biasanya variabel lain) di dalam memori. Contoh, jika sebuah variabel berisi alamat dari variabel lain, variabel pertama dikatakan menunjuk ke variabel kedua.

Operator Pointer :

Ada 2 operator pointer yang dikenal secara luas, yaitu “operator &” dan “operator *”.

1. Operator &

Operator & merupakan operator alamat. Pada saat pendeklarasian variable, user tidak diharuskan menentukan lokasi sesungguhnya pada memory, hal ini akan dilakukan secara otomatis oleh kompiler dan operating sysem pada saat run-time. Jika ingin mengetahui dimana suatu variable akan disimpan, dapat dilakukan dengan memberikan tanda ampersand (&) didepan variable , yang berarti "address of".

Contoh :

ted = &andy;

Penulisan tersebut berarti akan memberikan variable ted alamat dari variable andy. Karena variabel andy diberi awalan karakter ampersand (&), maka yang menjadi pokok disini adalah alamat dalam memory, bukan isi variable. Misalkan andy diletakkan pada alamat 1776 kemudian dituliskan instruksi sbb :

andy = 25;

fred = andy;

ted = &andy;

2. Operator *

Operator * merupakan operator reference. Dengan menggunakan pointer, kita dapat mengakses nilai yang tersimpan secara langsung dengan memberikan awalan operator asterisk (*) pada identifier pointer, yang berarti "value pointed by".

Contoh :

beth = *ted;

(dapat dikatakan:"beth sama dengan nilai yang ditunjuk oleh ted") beth = 25, karena ted dialamat 1776, dan nilai yang berada pada alamat 1776 adalah 25.

Ekspresi dibawah ini semuanya benar, perhatikan :

andy = 25;

&andy = 1776;

ted = 1776;

*ted = 25;

Ekspresi pertama merupakan assignation bahwa andy = 25;. Kedua, menggunakan operator alamat (address/derefence operator (&)), sehingga akan mengembalikan alamat dari variabel andy. Ketiga bernilai benar karena assignation untuk ted adalah ted = &andy;. Keempat menggunakan reference operator (*) yang berarti nilai yang ada pada alamat yang ditunjuk oleh ted, yaitu 25. Maka ekspresi dibawah ini pun akan bernilai benar :

*ted = andy;

Deklarasi Pointer

Seperti halnya variabel lain, variabel pointer juga harus dideklarasikan terlebih dahulu sebelum digunakan. Bentuk umum deklarasi pointer adalah : Dimana Tipe_data merupakan tipe dari data yang ditunjuk, bukan tipe dari pointer-nya

Linked List

Konsep dasar struktur data dinamis adalah alokasi memori yang dilakukan secara dinamis. Pada konsep ini, terdapat suatu struktur yang disebut dengan struktur referensi diri (self-referential structure), mempunyai anggota pointer yang menunjuk ke struktur yang sama dengan dirinya sendiri.

Struktur data dinamis sederhana dapat dibagi menjadi empat jenis, yaitu :

1. Linked list

2. Stack

3. Queue

4. Binary tree

Definisi ini dapat dituliskan secara sederhana dengan struktur :

struct node {

int info;

struct node *nextPtr;

}

Struktur ini mempunyai dua anggota, yaitu bilangan bulat info dan pointer nextPtr. Variabel pointer nextPtr ini menunjuk ke struktur bertipe struct node, yang sama dengan deklarasi induknya. Untuk membuat dan menangani struktur data dinamis dibutuhkan alokasi memori dinamis agar tersedia ruang bagi node-node yang ada. Fungsi malloc, free, dan operator sizeof banyak digunakan dalam alokasi memori dinamis ini.

Contoh :

typedef struct node NODE;

typedef NODE *NODEPTR;

NODEPTR newPtr = malloc (sizeof (NODE));

newPtr -> info = 15;

newPtr -> nextPtr = NULL;

Fungsi free digunakan untuk menghapus memori yang telah digunakan untuk node yang ditunjuk oleh pointer tertentu. Jadi free (newPtr); akan menghapus memori tempat node yang ditunjuk oleh newPtr.

DEFINISI LINKED LIST

Linked list adalah suatu cara untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data yang diperlukan. Program akan berisi suatu struct atau definisi kelas yang berisi variabel yang memegang informasi yang ada didalamnya, dan mempunyai suatu pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya. Struktur dinamis ini mempunyai beberapa keuntungan dibanding struktur array yang bersifat statis. Struktur ini lebih dinamis, karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya

bersifat tetap. Manipulasi setiap elemen seperti menyisipkan, menghapus, maupun menambah dapat dilakukan dengan lebih mudah.

Contoh :

//Program:link1.cpp

#include 

#include 

#include 

typedef struct nod {

int data;

struct nod *next;

} NOD, *NODPTR;

void CiptaSenarai(NODPTR *s)

{

*s = NULL;

}

NODPTR NodBaru(int m)

{

NODPTR n;

n = (NODPTR) malloc(sizeof(NOD));

if(n != NULL) {

n -> data = m;

n -> next = NULL;

}

return n;

}

void SisipSenarai (NODPTR *s, NODPTR t, NODPTR p)

{

if (p==NULL) {

t -> next = *s;

*s = t;

}

else {

t -> next = p -> next;

p ->next = t;

}

}

void CetakSenarai (NODPTR s)

{

NODPTR ps;

for (ps = s; ps != NULL; ps = ps -> next)

printf("%d -->", ps -> data);

printf("NULL\n");

}

int main ()

{

NODPTR pel;

NODPTR n;

CiptaSenarai(&pel);

n = NodBaru(55);

SisipSenarai(&pel, n, NULL);

Modul 6 Struktur Data (Arie) - 3

n= NodBaru(75);

SisipSenarai(&pel, n, NULL);

CetakSenarai(pel);

return 0;

}

Bila program dijalankan maka :

75->55->NULL

TEKNIK DALAM LINKED LIST

Pengulangan Linked List

Secara umum pengulangan ini dikenal sebagai while loop. Kepala pointer (head pointer) dikopikan dalam variabel lokal current yang kemudian dilakukan perulangan dalam linked list. Hasil akhir dalam linked list dengan current!=NULL. Pointer lanjut dengan current=current->next.

Contoh :

// Return the number of nodes in a list (while-loop version)

int Length(struct node * head) {

int count = 0;

struct node* current = head;

while (current != NULL) {

count++;

current=current->next;

}

return (count);

}

Mengubah Pointer Dengan Referensi Pointer

Banyak fungsi pada linked list perlu untuk merubah pointer kepala. Pointer ke pointer disebut dengan “reference pointer”.

Langkah utamanya dalam teknik ini adalah :

• Merancang fungsi untuk mengambil pointer ke pointer kepala. Untuk melewati pointer ke “value of interest” yang dibutuhkan untuk diubah. Untuk mengubah struct node*, lewati struct node**.

• Gunakan ‘&’ dalam panggilan untuk menghitung dan melewati pointer ke value of interest.

• Gunakan ‘*’ pada parameter dalam fungsi pemanggil untuk mengakses dan mengubah value of interest.

Contoh :

void ChangeToNull (struct node** headRef)

*headRef=NULL;

void ChangeCaller() {

struct node* head1;

struct node* head2;

ChangeToNull (&head1);

ChangeToNull (&head2);

}

Fungsi sederhana tersebut akan membuat pointer kepala ke NULL dengan menggunakan parameter reference.

Stack Atau Tumpukan

Pengertian Stack atau Tumpukan

 Adalah suatu stuktur data yang penting dalam pemrograman yang mempunyai sifat LIFO (Last In First Out), Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.  Stack (Tumpukan) adalah list linier yang dikenali elemen puncaknya (TOP) dan Aturan penyisipan dan penghapusan elemennya tertentu. Penyisipan selalu dilakukan “di atas“  TOP dan Penghapusan selalu dilakukan pada TOP.

 STACK ATAU TUMPUKAN PADA MATAKULIAH STRUKTUR DATA

Stack karena aturan penyisipan dan penghapusan semacam itu, TOP adalah satu-satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus.Dikatakan bahwa elemen Stack akan tersusun secara LIFO (Last In First Out). Karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo juga.

OPERASI-OPERASI/FUNGSI STACK

Push : digunakan untuk menambah item pada stack pada tumpukan paling atas

Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas

Clear : digunakan untuk mengosongkan stack

IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong

IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

Cara mendefenisikan Stack dengan Array of Struct yaitu:

1. Definisikan Stack dengan menggunakan struct

2. Definisikan konstanta MAX_STACK untuk menyimpan maksimum isi stack

3. Buatlah variabel array data sebagai implementasi stack

4. Deklarasikan operasi-operasi/function di atas dan buat implemetasinya.

contoh :

//Deklarasi MAX_STACK

                #define MAX_STACK 10   

            

//Deklarasi STACK dengan struct dan array data

                typedef struct STACK{

                                int top;

                                char data[10][10];                                                           

                }; 

//Deklarasi/buat variabel dari struct

                STACK tumpuk;

Inisialisasi Stack

Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah kosong. Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang.  Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack penuh.