Struktur Data Non-Linear (Tree & Graph)

TREE

Tree ialah 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.

 

NODE ROOT

Node root dalam sebuah tree adalah suatu node yang memiliki hiarki tertinggi dan dapat juga memiliki node-node anak. Semua node dapat ditelusuri dari node root tersebut.

Contoh penggunaan struktur pohon :

- Silsilah keluarga

- Hasil pertandingan yang berbentuk turnamen

- Struktur organisasi dari sebuah perusahaan

 

ISTILAH DALAM TREE

 

Contoh Tree

Datanya ialah : MASR

Ancestor (R) = S,M

Descendandt (S) = R

Parent (A) = M

Child (M) = A,S

Sibling (A) = S

Size = 4

Height = 3

Root = M

Deklarasi simpul tree :

Strcut simpulpohon{

   Simpulpohon *induk;

  Simpulpohon *kiri;

  Simpulpohon *kanan;

  Char kata[20];    //Tipe data bisa disesuaikan

};

Kunjungan :

Pre-order, in-order, dan post-order traversal

Pre-order, in-order, dan post-order traversal mengunjungi setiap simpul dalam sebuah pohon dengan pengunjungan secara berulang-ulang pada sub pohon kiri dan kanan dari akarnya. Jika akarnya dikunjungi sebelum sub pohonnya, ini merupakan preoder. Jika akarnya dikunjungi sesudah sub pohonnya, ini dinamakan postorder dan jika akarnya dikunjungi di antara sub pohonnya, dinamakan inorder. In-order traversal sangat berguna dalam pohon biner terurut, dimana traversal ini mengunjungi simpul dalam urutan yang meningkat.

Kita contohkan kembali menggunakan contoh tree yang diatas,

Datanya ialah : MASR

 

 

Jika Pre-order maka data ketika dibaca yaitu : MASR

Jika Post-Order maka data dibaca : ARSM

Jika In-Order maka  data dibaca : AMRS

Download Program C++,Tree ,3 All-In-One Kunjungan . Selamat Mencoba !!!

Untuk Selanjutnya Graph masih belajar :)

Sumber : Antonius Rachmat C, S.Kom,  Ibu Yuli, Wikipedia

[Continue reading...]

Struktur Data Linear (Linked List Linear)

Struktur Data Linear ialah data yang dipresentasikan berhubungan dengan data lainnya dengan teratur (lurus) sehingga membentuk barisan antara data satu dengan data lainnya.

Linked List ialah suatu record data yang dihubungkan satu dengan lainnya menggunakan pointer.

Fungsi-fungsi yang dapat dipakai dalam operasi linked list adalah:

1.      Fungsi menambah simpul di belakang. Langkah-langkahnya:

a.       membuat simpul baru kemudian diisi info baru.

b.      simpul paling akhir dihubungkan ke simpul baru.

c.       penunjuk pointer akhir diarahkan ke simpul simpul baru.

2.      Fungsi menambah simpul di depan. Langkah-langkahnya:

a.       membuat simpul baru, kemudian diisi info baru.

b.      simpul baru dihubungkan ke simpul awal.

c.       penunjuk pointer awal diarahkan ke simpul baru.

3.      Fungsi menyisipkan simpul di tengah. Langkah-langkahnya:

a.       membuat simpul bantu, kemudian diisi info baru.

b.      menentukan di mana simpul baru akan ditambahkan, yaitu dengan menempatkan pointer bantu pada suatu tempat.

c.       pointer baru dihubungkan ke simpul setelah simpul yang ditunjuk oleh pointer bantu, kemudian penunjuk pointer bantu diarahkan ke simpul baru.

4.      Fungsi menghapus simpul di depan. Langkah-langkahnya:

a.       simpul bantu diarahkan pada simpul awal.

b.      simpul awal diarahkan ke simpul berikutnya.

c.       menghapus simpul bantu.

5.      Fungsi menghapus simpul di tengah. Langkah-langkahnya:

a.       meletakkan pointer bantu di sebelah kiri simpul yang akan dihapus.

b.      simpul yang akan dihapus ditunjuk oleh pointer lain, misalnya pointer hapus.

c.       pointer bantu diarahkan ke simpul yang ditunjuk oleh hapus, kemudian simpul hapus dihapus.

6.      Fungsi menghapus simpul di belakang. Langkah-langkahnya:

a.       meletakkan pointer bantu di sebelah kiri simpul yang akan dihapus.

b.      simpul yang akan dihapus ditunjuk oleh pointer lain, misalnya pointer hapus.

c.       pointer bantu, diarahkan ke simpul yang ditunjuk oleh hapus, kemudian simpul hapus dihapus.

7.      Fungsi mencetak list dengan membaca maju. Langkah-langkahnya:

a.       mengatur agar pointer bantu menunjuk simpul yang ditunjuk oleh pointer awal.

b.      setelah isi simpul dibaca dan dicetak, pointer bantu digerakkan ke kanan untuk membaca simpul berikutnya.

c.       proses ini diulang sampai pointer bantu sama dengan pointer akhir.

8.      Fungsi mencetak list dengan membaca mundur. Langkah-langkahnya:

a.       mengatur agar pointer bantu menunjuk simpul yang ditunjuk oleh pointer akhir.

b.      setelah pointer bantu menunjuk simpul akhir, baru dicetak.

c.       proses pencetakan dilanjutkan dengan mencetak isi simpul di sebelah kiri simpul akhir.

d.      proses selesai jika isi simpul paling awal telah selesai dicetak.

9.      Fungsi mencari data pada list. Langkah-langkahnya:

a.       data yang dicari disimpan dalam suatu variabel, misalkan elemen.

b.      membuat pointer bantu sama dengan pointer awal.

c.       isi simpul yang ditunjuk oleh pointer bantu dibandingkan dengan elemen. Jika sama, berarti data yang dicari ditemukan. Jika belum sama, maka pointer bantu dipindahkan ke simpul di sebelah kanannya dan proses perbandingan diulang. Proses ini diulang sampai data yang dicari ditemukan atau sampai pada simpul akhir

1. Single Linked List Non Circular

Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & 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.

Deklasari simpul :

Struct simpul{

    int angka;

    simpul *berikut;

            };

             a.     Tambah Depan

Prinsipnya ketika data baru datang atau akan ditambahkan maka head atau awal akan menunjuk pada data baru tersebut dan data baru tersebut menunjuk pada data yang lama. Sehingga data lama akan menjadi di bawah data baru.

void tambahdepan(int x)

{

 struct titik *baru;

 baru=new titik;

 baru->angka=x;

 baru->berikut=awal;

 awal=baru;

}

     b.   Tambah Belakang

Pada prinsipnya sama dengan antrian, siapa yang masuk dialah yang akan keluar terlebih dulu. Maka data lama akan tetap menjadi awal bagi data baru, sehingga data pertama kali masuk akan terus menjadi awal dan data baru akan terus menjadi setelah data sebelumnya.

void tambahbelakang(int x) {

 struct simpul *baru;

 baru=new simpul;

 baru->angka=x;

 if(awal==NULL){

  awal=baru;}

 else{

 akhir->berikut=baru; }

 akhir=baru;

 akhir->berikut=NULL;

 }

      c.   Tambah List di tengah

Tambah list ditengah ini berguna ketika kita telah menginputkan data ternyata terdapat data yang terlewat untuk diinputkan dan harus berada diantara data yang telah di inputkan. Untuk memudahkan pemahamannya saya akan memberikan langsung dengan pengisian datanya. Yang pertama terdapat fungsi sisip_isi() ini berfungsi untuk menginputkan data dan fungsi sisip_list(simpul *first, int x, int posisi) untuk menentukan data akan disimpan setelah data yang mana sehingga dapat diisi diantara data-data yang lainnya.

void sisip_list(struct simpul *first,int x,int posisi)

{

struct simpul *bantu,*baru;

baru = new simpul;

baru->angka=x;

bantu=first;

do

{

if (posisi!=bantu->angka) {bantu=bantu->berikut;}

}

while (bantu!=NULL && posisi!=bantu->angka);

baru->berikut=bantu->berikut;

bantu->berikut=baru;

}

void sisip_isi_list()

{

int cari;

int ganti;

cout<<"\nBilangan : "; cin>>ganti;

cout<<"\nDisipkan setelah : ";

cin>>cari;

sisip_list(awal,ganti,cari);

}

     d.   Hapus Tengah

Tidak jauh beda dengan isi list di tengah, kita membutuhkan 2 fungsi yang pertama untuk mengiput data yang akan dihapus dan fungsi yang akan menghapus list. Fungsi carihapus() akan menjadi fungsi untuk membawa parameter atau nilai yang akan dihapus sementara fungsi hapustengah(int info) akan menghapus data yang sesuai dengan isi dari info yang dibawa oleh fungsi carihapus().

void hapustengah(int info)

{

titik *bantu,*hapus;

bantu=awal;

while ((info!=bantu->berikut->angka) && (bantu->berikut!=NULL))

 {

  bantu=bantu->berikut;

 }

  hapus=bantu->berikut;

  bantu->berikut=hapus->berikut;

  delete hapus;

}

void carihapus()

{

int cari;

clrscr();

tampillist();

cout<<"\nData yang akan dihapus, Bilangan :";

cin>>cari;

hapustengah(cari);

cout<<"\nData menjadi :";

tampillist();

}

     e.  Hapus Depan

Hapus di depan sebenarnya sangat simple karena kita bisa langsung menghapus *awal, namun disela itu sebelum tugas kita menghapus *awal kita harus mengganti *awal dengan pointer berikutnya sehingga ketika ditampilkan, data masih akan terlihat.

Void hapusdepan()

{

Simpul *hapus;

Hapus=awal;

Awal=hapus->berikut;

Delete hapus;

}

  

     f.   Hapus Belakang

Tidak jauh beda dengan hapus depan, namu hapus belakang membutuhkan looping untuk mengetahui bahwa dia adalah simpul paling terakhir.

Void hapusbelakang()

{

Simpul *hapus, *bantu;

Bantu=awal;

                While(bantu->berikut->berikut!=NULL){

                                bantu=bantu->berikut;

                }

hapus=bantu->berikut;

bantu->berikut=NULL;

delete hapus;

}

    g. Hapus Semua

Hapus semua merupakan cara penghapusan paling sederhana, kita hanya menentukan kapan *hapus berisi null dan disitulah dia berhenti.

void hapus()

{

simpul *hapus;

hapus=awal;

while(hapus!=NULL){

 awal=hapus->berikut;

delete hapus;

hapus=awal;

}

} 

2. Single Linked list Circular 

 Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

Deklarasi simpul :

struct simpul{

     int angka;

     simpul *berikut;

};

       a.       Tambah Depan

 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 tambahdepan(int x)

{

simpul *baru, *bantu;

baru = new simpul;

baru->angka=x;

baru->berikut=baru;

if(awal==NULL){

 awal=baru;

 awal->berikut=awal;

 }

else{

bantu=awal;

while(bantu->berikut!=awal){

  bantu=bantu->berikut;

  }

baru->berikut=awal;

awal=baru;

bantu->berikut=awal;

}

}

      b.      Tambah Belakang

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 tambahbelakang(int x)

{

simpul *baru, *bantu;

baru = new simpul;

baru->angka=x;

baru->berikut=baru;

if(awal==NULL){

 awal=baru;

 awal->berikut=awal;

 }

else{

bantu=awal;

while(bantu->berikut!=awal){

  bantu=bantu->berikut;

  }

bantu->berikut=baru;

awal=baru;

baru->berikut=awal;

}

}

1.       3. Double Linked List Circular

          Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & 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 simpul :

Struct simpul{

      int angka;

      simpul *next;

      simpul *prev;

};

 

a.           a.  Tambahdepan

Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Dibutuhkan pointer bantu yang digunakan untuk menunjuk node terakhir (head->prev) yang akan digunakan untuk mengikat list dengan node terdepan.

void tambahdepan(int x){

simpul *baru, *bantu;

baru = new simpul;

baru->angka = x;

baru->next = baru;

baru->prev = baru;

if(awal==NULL){

awal=baru;

awal->next =awal;

awal->prev = awal;

}

else {

bantu = awal->prev;

baru->next = awal;

awal->prev = baru;

awal = baru;

awal->prev = bantu;

bantu->next = awal;

}

}

b         b. Tambah Belakang

Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, namun tidak diperlukan loop karena untuk mengetahui node terbelakang hanya perlu menunjuk pada head->prev saja. Kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.

void tambahbelakang (int x){

simpul *baru,*bantu;

baru = new simpul;

baru->data = x;

baru->next = baru;

baru->prev = baru;

if(awal==NULL){

awal=baru;

awal->next = awal;

awal->prev = awal;

}

else {

bantu=awal->prev;

bantu->next = baru;

baru->prev = bantu;

baru->next = awal;

awal->prev = baru;

}

}

1.       4. Double Linked List Non-Circular

Double Linked List Non Circular 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.

Deklarasi simpul :

Struct simpul{

     Int angka;

        simpul *next;

               simpul *prev;

};

 

a.       Tambah depan

Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.

void tambahdepan(int x)

{

titik *baru;

baru=new simpul;

baru->nilai=x;

baru->next=NULL;

baru->prev=NULL;

if(awal==NULL){

        awal=baru;

        awal->next=NULL;

        awal->prev=NULL;

        }

        else{

        baru->next=awal;

        awal->prev=baru;

        awal=baru;

        }

}

b.      Tambah belakang

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 tambahbelakang(int x)

{

titik *baru, *bantu;

baru=new simpul;

baru->nilai=x;

baru->next=NULL;

baru->prev=NULL;

if(awal==NULL){

        awal=baru;

        awal->next=NULL;

        awal->prev=NULL;

        }

        else{

        bantu=head;

while(bantu->next!=NULL){

bantu=bantu->next;

}

        bantu->next=baru;

        baru->prev=bantu;

        }

}

Download Contoh Program C++ nya Tambah Depan, Tambah Belakang, Tambah Tengah, dan Hapus All-In-One.

Selanjutnya Mengenai Struktur Data Non-Linear !!!

  


Sumber : Antonius Rachmat C, S.Kom,  Ibu Yuli
 

[Continue reading...]

Array & Pointer

1. Array

 Array adalah suatu tipe data terstuktur yang berupa sejumlah data sejenis (bertipe data sama) dibedakan oleh index yang jumlahnya bisa statis ataupu dinamis dan diberi suatu nama tertentu. Elemen-elemen array tersusun secara berderet dan sekuensial di dalam memori sehingga memiliki alamat yang besebelahan/berdampingan. Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-dimensi. Elemen-elemen array bertipe data sama tapi bisa bernilai sama atau berbeda-beda. Keunggulan Array :

• Array sangat cocok untuk pengaksesan acak. Sembarang elemen di array dapat diacu secara langsung tanpa melalui elemen-elemen lain.
•  Jika berada di suatu lokasi elemen, maka sangat mudah menelusuri ke elemenelemen tetangga, baik elemen pendahulu atau elemen penerus.
•  Jika elemen-elemen array adalah nilai-nilai independen dan seluruhnya harus terjaga, maka penggunaan penyimpanannya sangat efisien.

Kelemahan Array :

• Array harus bertipe homogen. Kita tidak dapat mempunyai array dimana satu elemen adalah karakter, elemen lain bilangan, dan elemen lain adalah tipe-tipe lain.
•  Kebanyakan bahasa pemrograman mengimplementasikan array statik yang sulit diubah ukurannya di waktu eksekusi. Bila penambahan dan pengurangan terjadi terus-menerus, maka  representasi statis.

Deklarasi Variable Array :

tipe_data nama_var[banyak]; 
tipe_data : menyatakan jenis tipe data elemen larik (int, char, float, dll)
nama_var : menyatakan nama variabel yang dipakai.
banyak : menunjukkan jumlah maksimal elemen larik. 
Example :

Char nama[9];

Int nilai[4];

int bilangan[]; 

char nama[9]: berarti akan memesan tempat di memori komputer sebanyak 9 tempat dengan indeks dari 0-8, dimana semua elemennya bertipe data karakter semuanya. Kalau satu karakter berukuran 1 byte, berarti membutuhkan memori sebesar 9 byte.  

int nilai[4]: berarti akan memesan tempat di memori komputer sebanyak 4 tempat dengan indeks dari 0-3, dimana semua elemennya bertipe data integer semuanya. Kalau satu integer berukuran 4 bytes, berarti membutuhkan memori sebesar 4 x 4 = 16 bytes. 

int bilangan[]:berarti mendeklarasikan array dengan ukuran maksimum array tidak diketahui, namun ukuran tersebut diketahui berdasarkan inisialisasi yaitu sebanyak 3 elemen, yang isinya 1,2, dan 3.

Mengakses Elemen Array 

Nama_var[index]; 
Pengisian dan pengambilan nilai pada indeks tertentu dapat dilakukan dengan mengeset nilai atau menampilkan nilai pada indeks yang dimaksud. Pengaksesan elemen array dapat dilakukan berurutan atau random berdasarkan indeks tertentu secara langsung.

Contoh : nilai[2];

 
Contoh syntax : 

#include

#include

void main ()

{ int y [] = {1, 2, 7, 4, 5};

int n, r=0;

for ( n=0 ; n<5 ; n++ )

{

r += y[n];

}c

out<<" "<

getch(); }

Array Multidimensi 

Array multidimensi yaitu array yang terdiri dari beberapa subskrip atau index array. Contoh, array 2 dimensi adalah array yang mempunyai 2 index, array 3 dimensi adalah array yang mempunyai 3 index. Array seperti ini sering digunakan untuk pemrosesan matrik.

DEKLARASI ARRAY MULTIDIMENSI 

tipe_data nama_var[banyak_baris][banyak_kolom];

contoh : int matriks[3][4];                     

array ini bisa di ibaratkan table yang mempunya baris dan kolom. 

Contoh pengaksesan : 

matrix[2][3]; 

Maka nilainya ialah 3.

2. Pointer

Pointer adalah suatu variabel penunjuk yang menunjuk pada suatu alamat memori komputer tertentu. Pointer merupakan variabel level rendah yang dapat digunakan untuk menunjuk nilai integer, character, float, double, atau single, dan bahkan tipe-tipe data lain yang didukung oleh bahasa C. Variabel biasa, sifatnya statis dan sudah pasti, sedangkan pada pointer sifatnya dinamis dan dapat lebih fleksibel. Variabel pointer yang tidak menunjuk pada nilai apapun berarti memiliki nilai NULL, dan disebut sebagai dangling pointer karena nilainya tidak diinisialisasi dan tidak dapat diprediksi.

Deklarasi variabel pointer

tipe _data * nama_pointer;

• Operator Alamat / Dereference Operator(&)

Setiap variabel yang dideklarasikan, disimpan dalam sebuah lokasi memori dan pengguna biasanya tidak mengetahui di alamat mana data tersebut disimpan. Dalam C++, untuk mengetahui alamat tempat penyimpanan data, dapat digunakan tanda ampersand(&) yang dapat diartikan “alamat”.

Contoh :

Bil1 = &Bil2;

dibaca: isi variabel bil1 sama dengan alamat bil2

• Operator Reference (*)

Penggunaan operator ini, berarti mengakses nilai sebuah alamat yang ditunjuk oleh variabel pointer.

Contoh :

Bil1=*Bil2;

dibaca: bil1 sama dengan nilai yang ditunjuk oleh bil2.

OPERASI POINTER

1. Operasi penugasan

Nilai dari suatu variabel pointer dapat disalin ke variabel pointer yang lain.

contoh: y = 35;

x1 = &y;

x2 = x1;

2. Operasi aritmatika

 Suatu variabel pointer hanya dapat dilakukan operasi aritmatika dengan nilai integer saja.

 Operasi yang biasa dilakukan adalah operasi penambahan dan pengurangan.

 Operasi penambahan dengan suatu nilai menunjukkan lokasi data berikutnya (index selanjutnya) dalam memori.

Begitu juga operasi pengurangan.

3. Operasi Logika

Suatu pointer juga dapat dikenai operasi logika.

#include"constream.h"

void main()

{ int a = 100, b = 200, *pa, *pb;

clrscr();

pa = &a;

pb = &b;

cout<<"nilai pa= "<

if(pa < pb)

cout<<"pa menunjuk ke memori lebih rendah dari pb\n";

if(pa == pb)

cout<<"pa menunjuk ke memori yang sama dengan pb\n";

if(pa > pb)

cout<<"pa menunjuk ke memori lebih tinggi dari pb\n";

getch();

}



Download contoh program C++, Array1, Array2, Array 3 Dimensi, Pointer1, 2, & 3
Selanjutnya kita akan membahasa Linked List !!! Klik Disini Linked List 


Sumber : Antonius Rachmat C, S.Kom,  Ibu Yuli

 

[Continue reading...]