Struktur Data Pertemuan 17 CIRCULAR DOUBLY LINKED LIST

 Circular Doubly Linked List

Circular Doubly Linked List adalah sederetan elemen yang saling berhubungan satu dengan yang lain, dimana pointer kiri simpul pertama menunjuk simpul terakhir dan pointer kanan simpul terakhi menunjuk simpul pertama. Semua simpul berhak menjadi simpul pertama. Jika suatu simpul dibuat menjadi simpul depan maka simpul yang ada di sebelah kiri merupakan simpul belakang.

Pendeklarasian simpul untuk Circular Doubly Linked List sama dengan pendeklarasian pada Doubly Linked List. Operasi yang ada pada Doubly Linked List juga berlaku pada Circular Doubly Linked List, hanya saja pada Circular tidak mengandung NULL,

Circular Doubly Linked List adalah Linked List dimana link simpul terakhir bukan diisi dengan null, tetapi diisi dengan alamat simpul pertama yaitu simpul yang ditunjuk oleh pointer FIRST, sehingga menciptakan efek melingkar’ sesuai arah jarum jam’. 

_ Pointer RIGHT simpul paling kanan berisi alamat simpul paling kiri

_ Pointer LEFT simpul paling kiri berisis alamat simpul paling kanan

Program :

Buat program animasi Circular Doubly Linked List untuk mengelola data mahasiswa dengan struktur mahasiswa sbb : NAMA, NIM, GENDER, NILAI . Data terurut naik berdasarkan NIM. Program dibuat dalam bentuk menu dengan pilihan : INSERT DATA, HAPUS DATA, CETAK DATA, EXIT.

Ket :

INSER DATA : menambah data

HAPUS DATA : menghapus satu data berdasarkan kriteria NIM

CETAK DATA : mencetak seluruh isi linked list

EXIT : Keluar/selesai

Tampilan menu :

CIRCULAR DOUBLY LINKED LIST

==========================

1. INSERT DATA

2. HAPUS DATA

3. CETAK DATA

4. EXIT

Pilihan (1 – 4) :

Source Code :

#include <iostream>

#include <conio.h>

#include <stdio.h>

#include <windows.h>//mendukung format system("CLS") sebagai peganti clrscr()

using namespace std;

int pilih; void pilihan();

void insert_data();

void hapus_data();

void cetak_data();

struct node

{

 int nomorinduk;

 char nama [40];

 char gender [20];

 float nilai;

 node *prev, *next;

};

node *baru, *head=NULL, *tail=NULL,*help,*del;

main()//interface monitor

{

 do

 {

  system("cls");

  cout<<"\tLIN. DOUBLY LINKED LIST"<<endl;

  cout<<"\t=========================="<<endl;

  cout<<"\t1. INSERT DATA"<<endl;

  cout<<"\t2. HAPUS DATA"<<endl;

  cout<<"\t3. CETAK DATA"<<endl;

  cout<<"\t4. EXIT"<<endl;

  cout<<"\tPilihan (1 - 4) : ";

  cin>>pilih;

  cout<<endl<<endl;

  pilihan();

  cout<<"==============================="<<endl;

 }

 while(pilih!=4);

}

void pilihan()//fungsi "pilihan" untuk pemrosesan

{

 if(pilih==1)

 insert_data();

 else if(pilih==2)

 hapus_data();

 else if(pilih==3)

 cetak_data();

 else

 {

  cout<<"EXIT";

  cout<<"\nSampai Jumpa lagi"<<endl;

 }

}

void buat_baru()//fungsi membuat data baru

{

 baru = new(node);

 cout<<"Masukkan Nomor Induk : ";cin>>baru->nomorinduk;

 cout<<"Masukkan Nama : ";cin>>baru->nama;

 cout<<"Masukkan Gender : ";cin>>baru->gender;

 cout<<"Masukkan Nilai : ";cin>>baru->nilai;

 cout<<"\n\t---Data telah dimasukkan---";

 cout<<"\n\nPRESS ENTER TO CONTINUE...";

 getch();

 baru->prev=NULL;

 baru->next=NULL;

}

void insert_data()

{

 buat_baru();

 if(head==NULL)

 {

  head=baru;

  tail=baru;

 }

 else

 {

  baru->next=head;

  head->prev=baru;

  head=baru;

 }

 cout<<endl<<endl;

}

void hapus_data()//fungsi penghapusan data

{

 int hapus,nomorinduk;

 if(head==NULL)

 {

  cout<<"\nLinked List kosong, \nPenghapusan tidak dapat dilakukan"<<endl;//data yang habis maka tampilannya

 }

 else

 {

  hapus=head->nomorinduk;

  cout<<"\nData yang dihapus adalah ";//pemilihan data yang akan dihapus

  cin>>nomorinduk;

  del = head;

  head = head->next;

  delete del;

 }

}

void cetak_data()

{

 if (head==NULL)

 cout<<"\nData tidak dapat ditemukan!"<<endl;//data yang kosong

 else

 {

  help=head;

  while(help!=NULL)

  {

   cout<<" Nomor Induk : "<<help->nomorinduk;//data akan muncul dengan tampilan

   cout<<" Nama : "<<help->nama;

   cout<<" Gender : "<<help->gender;

   cout<<" Nilai : "<<help->nilai<<endl;

   help=help->next;

  }

 }

getch();

}

Readmore → Struktur Data Pertemuan 17 CIRCULAR DOUBLY LINKED LIST

Struktur Data Pertemuan 16 CIRCULAR LINKED LIST

 CIRCULAR LINKED LIST 

Circular Linked List pada C++. Semua Linked List baik Singly maupun Doubly selalu berisi pointer NULL yaitu pointer Next simpul terakhir dari Singly Linked List dan pointer kiri simpul pertama dan pointer kanan simpul terakhir Doubly Linked List. Dengan demikian untuk membaca isi Linked List selalu dilakukan dari simpul pertama ke kanan. Ada kalanya kita membaca isi Linked List mulai dari posisi tertentu tanpa harus mundur dan kembali ke posisi semula. Maka untuk itu kita buat dengan Linked List Melingkar (Circular Linked List).

Circular Linked List dapat dilakukan terhadap Singly Linked List maupun Doubly Linked List. Dalam Circular Linked List tidak terdapat suatu simpul yang bernilai NULL. Hal ini terjadi karena simpul terakhir dihubungkan terhadap simpul pertama untuk Singly Linked List dan simpul pertama dengan simpul terakhir saling terhubung untuk Doubly Linked List. Semua simpul berhak diperlakukan sebagai simpul depan.

Circular Single Linked List adalah singly Linked List dimana link simpul terakhir bukan diisi dengan null, tetapi diisi dengan alamat simpul pertama yaitu simpul yang ditunjuk oleh pointer FIRST, sehingga menciptakan efek melingkar’ sesuai arah jarum jam’. 

 

 

Perbedaan antara Linearly Singly Link List dengan Circular Singly Link List terletak pada simpul terakhir. Dengan demikian proses pada Linearly dengan Circular sama kecuali penanganan simpul terakhir. 

Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :

• Circular Single Linked List

• Circular Double Linked List

TUGAS

Buat program animasi Circular Linked List untuk mengelola data mahasiswa dengan struktur mahasiswa sbb : NAMA, NIM, GENDER, NILAI . Data terurut naik berdasarkan NIM. Program dibuat dalam bentuk menu dengan pilihan : INSERT DATA, HAPUS DATA, CETAK DATA, EXIT.

Ket :

INSER DATA : menambah data

HAPUS DATA : menghapus satu data berdasarkan kriteria NIM

CETAK DATA : mencetak seluruh isi linked list

 EXIT : Keluar/selesai

Tampilan menu :

                  CIRCULAR LINKED LIST

                  ==========================

1. INSERT DATA

2. HAPUS DATA

3. CETAK DATA

4. EXIT

Pilihan (1 – 4) :

Readmore → Struktur Data Pertemuan 16 CIRCULAR LINKED LIST

Struktur Data Pertemuan 15 POHON BINER LANJUTAN

 Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.

Dalam ilmu komputer, sebuah pohon biner adalah struktur data pohon di mana setiap node memiliki paling banyak dua anak, yang disebut sebagai anak kiri dan anak kanan. Definisi rekursif hanya menggunakan teori himpunan gagasan adalah bahwa (non-kosong) pohon biner adalah tiga (L, S, R), di mana L dan R adalah pohon biner atau himpunan kosong dan S adalah satu set tunggal. Beberapa penulis memungkinkan pohon biner menjadi himpunan kosong juga.

Dari perspektif teori grafik, biner (dan K-ary) pohon seperti yang didefinisikan di sini sebenarnya arborescences. Sebuah pohon biner sehingga dapat juga disebut bifurcating arborescence-istilah yang benar-benar muncul di beberapa buku-buku pemrograman yang sangat tua, sebelum terminologi ilmu komputer modern menang. Hal ini juga memungkinkan untuk menafsirkan sebuah pohon biner sebagai diarahkan, bukan grafik diarahkan, dalam hal pohon biner adalah memerintahkan, berakar pohon. Beberapa penulis menggunakan berakar pohon biner bukan pohon biner untuk menekankan fakta bahwa pohon berakar, tetapi seperti yang didefinisikan di atas, pohon biner selalu berakar. Sebuah pohon biner adalah kasus khusus dari pohon K-ary memerintahkan, di mana k adalah 2.

Dalam komputasi, pohon biner jarang digunakan semata-mata untuk struktur mereka. Jauh lebih khas adalah untuk mendefinisikan fungsi pelabelan pada node, yang menghubungkan beberapa nilai untuk setiap node. Pohon biner berlabel cara ini digunakan untuk mengimplementasikan pohon pencarian biner dan tumpukan biner, dan digunakan untuk pencarian yang efisien dan penyortiran. Penunjukan node non-root sebagai kiri atau kanan anak bahkan ketika hanya ada satu anak hal hadir dalam beberapa aplikasi, khususnya adalah penting dalam pohon pencarian biner. Dalam matematika, apa yang disebut pohon biner dapat bervariasi secara signifikan dari penulis ke penulis. Beberapa menggunakan definisi yang biasa digunakan dalam ilmu komputer, tetapi yang lain mendefinisikannya sebagai setiap non-daun memiliki tepat dua anak dan tidak selalu order (sebagai kiri / kanan) anak-anak baik.

Istilah

a. Pohon :susunan dari satu atau lebih simpul (node) yang terdiri dari satu simpul khusus yang disebut akat (root) sedang sisanya membentuk subtree dari akar.

b.  Simpul/Vertex/Node : A, B,…, N

c. Busur/Edge/Arc : garis yang menghubungkan antar simpul

d. Superordinat/Father/Parent dan Subordinat/Son/Children.

i. Simpul A merupakan superordinat bagi simpul B, C, D

ii. Simpul B, C,D merupakan subordinat bagi simpul A

e. Root/Akar : simpul yang tidak mempunyai superordinat. Pada gambar diatas : A.

f. Leaf/Daun : simpul yang tidak mempunyai subordinat. Pada gambar diatas : C, E, G, I, J, K, L, M, N.  

g. Level/Tingkat : Simpul A berada pada level 0, simpul B, C, D berada pada level 1, dst.

h. Depth/kedalaman : Level tertinggi dari suatu pohon. Pada gambar 1, depth = 3.

i. Derajat/Degree sebuah simpul jumlah simpul subordinat dari simpul tersebut.

j. Derajat/degree sebuah pohon adalah derajat tertinggi dari derajat simpul yang ada pada pohon tersebut.

Aturan Penyajian Binary Tree

• Tree dapat dibuat dengan menggunakan linked list secara rekursif.
• Linked list yang digunakan adalah double linked list non circular
• Data yang pertama kali masuk akan menjadi node root.
• Data yang lebih kecil dari data node root akan masuk dan menempati node kiri dari node root, sedangkan jika lebih besar dari data node root, akan masuk dan menempati node di sebelah kanan node root.

Karakteristik Binary Tree

• Setiap Simpul paling banyak hanya memiliki dua buah anak
• Derajat Tertinggi dari setiap Simpul adalah dua.
• Dibedakan antara Cabang Kiri dan Cabang Kanan.
• Dimungkinkan tidak mempunyai Simpul

Istilah Pada Binary Tree

1. Pohon Biner Penuh (Full Binary Tree)
   
   Semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki panjang ruas yang sama
2. Pohon Biner Lengkap (Complete Binary Tree)
   
   Hampir sama dengan Pohon Biner Penuh, semua simpul (kecuali daun) memiliki 2 anak tetapi tiap cabang memiliki panjang ruas berbeda
3. Pohon Biner Similer
   
   Dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda
4. Pohon Biner Ekivalent
   
   Dua pohon yang memiliki struktur dan informasi yang sama
5. Pohon Biner Miring (Skewed Tree)
   
   Dua pohon yang semua simpulnya mempunyai satu anak / turunan kecuali daun

Contoh program

Program tersebut untuk menambahkan data, kunjungan in order, 

lalu menghitung jumlah node

menghitung tinggi pohon

mencari data terbesar

Readmore → Struktur Data Pertemuan 15 POHON BINER LANJUTAN

UTS Struktur Data _ M Yahya Fauzi

Nama : M Yahya Fauzi

Nim : 191011401394

Kelas : 03TPLE020

Mata Pelajaran: Struktur Data

Soal 1

Saya pilih yg bagian nomor 2 Selection Sort Descending

Readmore → UTS Struktur Data _ M Yahya Fauzi