Senin, 30 November 2015

Pertemuan Minggu [11] Structur Data [01 Desember 2015]

Pertemuan Kedelapan kali ini membahas tentang Persiapan Tugas Proyek & Presentasi.

Pada perkuliahan kali ini pak wahyu lebih fokus pada tugas proyek yang diberikan ke kami ketentuan yang diberikan sebagai berikut.

[Penilaian tahap 1 : Persiapan Bahan Media Pembelajaran] [Kelas A]
Silahkan berkumpul 3 tim dalam satu grup. Tim yang presentasi akan DINILAI oleh 2 tim yang lain. Untuk minggu ini, penilaian meliputi :
Tugas Proyek Struktur Data 2015
Struktur Media Pembelajaran
A. materi :
1. Pendahuluan : pentingnya dan motivasi (animasi atau video) - maksimal 15
2. Teori - maksimal 25
a. Definisi, teori penunjang
b. Tipe Data Abstrak (bila ada)
c. Kontruksi class
d. Code (dala C++)
3. Contoh-contoh - maksimal 15
B. Latihan - maksimal 25
C. Evaluasi - maksimal 20

dan kami disuruh presentasi ke 2 kelompok berbeda dan mengupload nilai dengan format seperti diatas...,
Ya.. sekian pembahsan minggu ke sebelas kali ini, Terima Kasih.

Rabu, 25 November 2015

Pertemuan Minggu [10] Structur Data [24 November 2015]

Pertemuan Kesepuluh kali ini membahas tentang Pohon Biner Setimbang.


Pohon Biner
Definisi:
Sebuah pohon biner adalah himpunan terbatas yang:
- mungkin kosong, atau
- terdiri dari sebuah simpul yang disebut akar
dan dua buah himpunan lain yang disjoint yang merupakan pohon biner, yang disebut
sebagai sub pohon kiri dan sub pohon kanan dari pohon biner tersebut
Perhatikanlah perbedaan pohon biner dengan pohon biasa : pohon biner mungkin kosong,
sedangkan pohon n-aire tidak mungkin kosong.
Pohon Seimbang (Balanced Tree)
Pohon seimbang:
• Pohon seimbang tingginya: perbedaan tinggi sub pohon kiri dengan sub pohon kanan
maksimum 1.
• Pohon seimbang banyaknya simpul: perbedaan banyaknya simpul sub pohon kiri
dengan sub pohon kanan maksimum 1.
Berikut ini adalah algoritma untuk pohon yang seimbang banyaknya simpulnya.

Contoh Pohon Setimbang :

Image result for pohon biner setimbang

Image result for pohon biner setimbang

Image result for pohon biner setimbang

Ya.. Sekian pembahasan minggu ke sepuluh saya kali ini.. Terima Kasih. :D

Rabu, 18 November 2015

Pertemuan Minggu [09] Structur Data [17 November 2015]

Pertemuan Kesembilan kali ini membahas tentang Pohon Biner.

Pohon Biner (Binary Tree) adalah sebuah pohon struktur data dimana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon Biner Terurut, yang kata lainnnya adalah heap biner.
Pohon (tree) adalah himpunan terbatas, tidak
kosong, dengan elemen dibedakan sebagai
berikut:
– Sebuah elemen yang dibedakan dari yang lain _
AKAR
– Elemen yang lain (jika ada) dibagi-bagi menjadi
beberapa sub himpunan yang disjoin dan masing-
masingmasing
sub himpunan itu adalah pohon _
SUBPOHON
Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut root atau akar
Definisi tree : “Kumpulan elemen yang salah satu elemennya disebut dengan root (akar) dan sisa elemen yang lain disebut sebagai simpul (node/vertex) yang terpecah menjadi sejumlah himpunan yang tidak saling berhubungan satu sama lain, yang disebut subtree/cabang”.
Jenis-jenis Tree :
1.   Binnary 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, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.
Jenis jenis Binnary Tree



  • Full binnary tree

binnary tree ini tiap nodenya (kecuali leaf) memiliki 2 child dan tiap subtree harus mempunyai panjang path yang sama.
  • complete binnary tree

mirip dengan full binnary tree, tetapi tiap subtree boleh memiliki panjang path yang berbeda.
  • skewed binnary tree

binnary tree yang semua nodenya (kecuali leaf) hanya memiliki 1 child.
Implementasi Binary Tree*
Binary Tree dapat diimplemntasikan dalam Pascal dengan menggunakan double Linked List. Untuk nodenya, bisa dideklarasikan sbb :
Type Tree = ^node;
Node = record
Isi : TipeData;
Left,Right : Tree;
end;
Contoh ilustrasi Tree yang disusun dengan double linked list :



(Ket: LC=Left Child; RC=Right Child)
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 tak boleh kosong)
·         Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)
·         Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)
·         DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.
·         Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)
·         Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.
Langkah-Langkahnya Traverse :
·         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.
 2.  Binary search Tree
Adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree. Contoh binary search tree umum :



Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi insert, update, dan delete.
1. Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat. (Lokasi tidak ditentukan oleh user sendiri).



2. Update : Seperti pada Binary Tree biasa, namun disini uapte akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.
3. Delete : Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.

(Keadaan awal merupakan lanjutan gambar sebelumnya)

Ya.. Sekian pembahasan pertemuan ke sembilan saya kali ini... terima kasih :D

Kamis, 12 November 2015

Pertemuan Minggu [08] Structur Data [10 November 2015]

Pertemuan Kedelapan kali ini membahas tentang Array,Queue, Dequeue dan Stack.


QUEUE & DEQUEUE

PENGERTIAN QUEUE (ANTRIAN) 

  1. Enqueue adalah proses untuk memasukkan elemen artinya menambah data baru. Jika elemen data tidak bisa dimasukkan karena melebihi kapasitas queue akan muncul error yang disebut Overflow.
  2. Dequeue adalah proses untuk mengeluarkan elemen artinya menghapus data. Jika tidak bisa mengeluarkan elemen data satupun karena kosong akan terjadi error yang disebut dengan Underflow.
Definisi 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
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.
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.
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).
Berikut adalah contoh syntax program Stack..
#include <iostream>
#include <conio.h>
#define maxstack 5
using namespace std; //untuk melegalkan header iostream

//pendeklarasian struct
struct STACK
{
      int top;
      float data[4];
};
float dta;

/*struct yang telah dibuat (STACK) dijadikan suatu Tipe data, dimana disebut tipe data abstrak*/
struct STACK stackbaru;

//fungsi boolean untuk mengetahui apakah stack penuh
bool isfull()
{
      if(stackbaru.top == maxstack)
            return true;
      else
            return false;
}

//fungsi boolean untuk mengetahui apakah stack kosong
bool isempty()
{
      if(stackbaru.top == -1)
            return true;
      else
            return false;
}

//fungsi untuk menambahkan data pada stack
void push(float dta)
{
     if(isfull() == true) /*panggil fungsi isempty(), jika kondisi benar pernyataan dijalankan*/
      {
            puts("Maaf, stack penuh");
      }
      else{
            stackbaru.top++;
            stackbaru.data[stackbaru.top]=dta;
      }
}

//fungsi untuk mengambil data pada stack
void pop()
{
      if(isempty() == true) //panggil fungsi isempty(), jika kondisi benar pernyataan dijalankan
      {
            cout<<"Data telah kosong!";
      }
      else
      {
            cout<<"Data yang terambil : " <<stackbaru.data[stackbaru.top]<<endl;
            stackbaru.top--;
      }
}

//fungsi untuk mencetak data pada stack
void print()
{
      printf("\nData yang terdapat dalam stack : \n");
      printf("--------------------------------\n");
      for(int i=0; i<=stackbaru.top; i++)
      {
            cout<<stackbaru.data[i]<<"    ";
      }
}

//fungsi untuk membersihkan data dalam stack
void clear()
{
      stackbaru.top = -1;
      printf("\nSekarang stack kosong");
}

//fungsi utama
int main()
{
      //pendeklarasian variabel
      char menu;
      char ulang;
      //perulangan dengan do-while
      do
      {
            system("cls");
            printf("\t PROGRAM STACK\n");
            printf("\t===============\n");
            printf("Menu : ");
            puts("\n1. Pop stack");
            puts("2. Push stack");
            puts("3. Cetak");
            puts("4. Bersihkan stack");
            puts("5. Exit");
           
            cout<<"Menu pilihan Anda : ";
            cin>>menu;
           
            if(menu == '1')
            {
                  pop(); //panggil fungsi pop()
                  ulang = 'y';
                  getch();
            }
            else if(menu == '2')
            {
                  cout<<"\nTambah Data";
                  cout<<"\n-----------";
                  cout<<"\nData yang akan disimpan di stack : ";
                  cin>>dta;
                 push(dta); /*panggil fungsi push(dta)--dta sesuai dengan data ynag diinput*/
                  ulang = 'y';
            }
            else if(menu == '3')
            {
                  print(); /*panggil fungsi untuk mencetak data dalam stack*/
                  cout<<"\n\nUlang ? (y/t)";
                  cin>>ulang;
            }
            else if(menu == '4')
            {
                  clear(); //panggil fungsi untuk membersihkan stack
                  cout<<"\n\nUlang ? (y/t)";
                  cin>>ulang;
            }
            else if(menu == '5')
            {
                  exit(0); //keluar dari program
            }
       }while(ulang == 'Y' || ulang == 'y'); /*akan selalu diulang ketika ulang == 'y' || ulang'Y'*/
} 

Ya.. Sekian pembahasan saya dalam minggu ke delapan ini.., Terima Kasih semoga membantu...