Contoh program Single Linked List

#include <iostream>

using namespace std;

class LinkList{

private:

struct node{

int data;

node *next;

};

node *head;

public:

LinkList();

void insertData(int num);

void deleteData (int num);

void displayData();

int count();

~LinkList();

};

LinkList::LinkList()

{

head=NULL;

}

void LinkList::insertData(int num)

{

node *temp;

node *t;

if( head == NULL)

{

head = new node;

head->data = num;

head->next = NULL;

}

else

{

temp = head;

while(temp->next != NULL)

{

temp = temp->next;

}

t = new node;

t->data = num;

t->next = NULL;

temp->next = t;

}

}

void LinkList::deleteData(int num)

{

node *q, *r;

q= head;

if(q->data == num)

{

head = q->next;

delete q;

return;

}

r = q;

while(q!= NULL)

{

if(q->data == num )

{

r->next = q->next;

delete q;

return;

}

r = q;

q = q->next;

}

cout << ” Nilai ” << num << “tidak ditemukan”;

}

void LinkList::displayData()

{

node *q;

for(q=head; q != NULL; q=q->next)

{

cout<<q->data<<endl;

}

}

int LinkList::count()

{

node *q;

int c=0;

for( q=head ; q != NULL ; q = q->next )

c++;

return c;

}

LinkList::~LinkList()

{

node *q;

if(head == NULL)

{

return;

}

while(head != NULL)

{

q = head->next;

delete head;

head = q;

}

}

int main()

{ LinkList list;

int temp;

int pilihan;

while(1)

{

cout<<”Link List Single”<<endl;

cout<<”1.Insert / Creation”<<endl;

cout<<”2.Delete Element”<<endl;

cout<<”3.View Element”<<endl;

cout<<”4.Count Element”<<endl;

cout<<”5.Exit”<<endl;

cout<<”Enter your choice:”;

cin>>pilihan;

switch(pilihan)

{  cout<<endl;

case 1:

cout<<”Insert Element Data”;

cin>>temp;

list.insertData(temp);

break;

case 2:

cout<<”Delete Element :”;

cin>>temp;

list.deleteData(temp);

break;

case 3:

list.displayData();

break;

case 4:

cout<<”Number Total Element at List : “<<list.count()<<endl;

break;

case 5:

return 0;

}

}

}

[\code]

POHON (TREE)

Definisi Rekurens Dari Pohon:

Sebuah pohon adalah himpunan terbatas tidak kosong, dengan elemen yang dibedakan sebagai berikut :
1.     Sebuah elemen yang dibedakan dari yang lain yang disebut sebagai AKAR (root) dari pohon
2.     Elemen yang lain (jika masih ada) dibagi-bagi menjadi beberapa sub himpunan yang disjoint dan masing-masing sub himpunan tersebut adalah pohon yang disebut sebagai sub pohon dari pohon tersebut.

Sifat sifat pohon:

1. Jika Pohon mempunyai simpul sebanyak n,maka banyaknya ruas atau edge adalah n-1
2. Mempunyai simpul khusus yang di sebut root,jika simpul tersebut mempunyai derajat keluar >=0,dan derajat masuk = 0
3. Mempunyai simpul yang disebut daun/leaf,jika simpul tersebut berderajat keluar = 0,dan berderajat masuk = 1
4. Setiap simpul mempunyai Tingkatan/level yang dimulai dari root yang levelnya =1,sampai dengan  level ke-n yang berada pada daun yang paling bawah.simpul yang mempunyai level sama di sebut bersaudara
5. Pohon mempunyai ketinggian atau kedalaman atau height ,yang merupakan level tertinggi.
6. Pohon mempunyai berat atau weight,yang banyaknya daun pada pohon.

Beberapa Istilah:

1.      Hutan adalah sequence (list) dari pohon.

2.      Simpul (Node) Simpul adalah elemen dari pohon yang memungkinkan akses pada sub pohon dimana simpul tersebut berfungsi sebagai Akar

3.      Cabang   adalah hubungan antara Akar dengan sub pohon

4.      Ayah, Akar  dari sebuah pohon adalah Ayah dari sub pohon

5.       Anak , dari sebuah pohon adalah Sub pohon.

6.       Saudara  adalah simpul-simpul yang mempunyai Ayah yang sama

7.       Daun adalah simpul terminal dari pohon. Semua simpul  selain Daun adalah simpul bukan terminal

8.      Jalan (Path) adalah suatu urutan tertentu dari Cabang

9.      Derajat
Derajat sebuah pohon adalah banyaknya anak dari  dari pohon tersebut.
Jika sebuah simpul berderajat N disebut     pohon N-aire
1 disebut pohon 1-aire/uner
2 disebut pohon 2-aire/biner

Struktur Pohon Biner

Sebuah pohon biner (Binary Tree) adalah himpunan terbatas yang :
Mungkin kosong atau terdiri dari sebuah simpul yang disebut sebagai Akar dan dua buah himpunan lain yang disjoint yang merupakan pohon biner yang disebut sebagai Sub Pohon Kiri (Left) dan Sub Pohon Kanan (Right) dari pohon biner tersebut. Pohon biner merupakan tipe yang sangat penting  dari struktur data dan banyak dijumpai  dalam berbagai terapan. Karakteristik yang  dimiliki oleh pohon biner adalah bahwa     setiap simpul paling banyak hanya   memiliki  dua buah anak, dan mungkin tidak punya anak.

Karakteristik Pohon binar

1. Setiap simpul paling banyak hanya memiliki dua buah anak.
2. Derajat tertinggi dari setiap simpul adalah dua
3. Dibedakan antara cabang kiri dan cabang kanan
4. Dimmungkinkan tidak memiliki simpul

dibawah ini contoh pohon binar dengan cabang kiri dan kanan

Istilah pada pohon binar(binary tree)

• Pohon binar penuh (full binary tree)

semua simpul (kecuali daun) memiliki dua anak dan tiap cabang memiliki panjang ruas yang sama

• Pohon Binar lengkap(complate binary tree)

hampir sama dengan pohon biner penuh,bedanya tiap cabang memiliki ruas berbeda

• Pohon biner Similer

Dua pohon yang memiliki struktur sama tapi informasinya berbeda

• Pohon biner Ekivalent

Dua pohon yang memiliki struktur sama dan informasi yang sama.

• Pohon biner Miring(skewed Tree)

Dua pohon yang semua simpulnya mempunyai satu anak /turunan kecuali daun.

deklarasi Pohon Biner dengan program C++

Dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk ke arah cabang kiri dan cabang kanan dan informasi yang akan di simpan .

Penyajian Pohon Binar (binary tree)

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

MENGUBAH FUNGSI ITERATIF MENJADI FUNGSI REKURSIF

Pengertian iteratif

Perulangan iteratif merupakan perulangan yang melakukan proses perulangan terhadap sekelompok instruksi di mana perulangan tersebut akan berhenti jika batasan syarat sudah tidak terpenuhi.

Kelebihan perulangan iteratif:

• Mudah dipahami dan mudah melakukan debugging ketika ada perulangan yang salah.

• Dapat melakukan nested loop atau yang disebut dengan looping bersarang.

• Proses lebih singkat karena perulangan terjadi pada kondisi yang telah disesuaikan.

• Jarang terjadi overflow karena batasan dan syarat perulangan yang jelas.

Kelemahan perulangan iteratif:

• Tidak dapat menggunakan batasan berupa fungsi.

• Perulangan dengan batasan yang luas akan menyulitkan dalam pembuatan program perulangan itu sendiri.

program 1

Bentuk fungsi iteratif :

#include <cstdlib>

#include <iostream>

using namespace std;

int jumlah(int n) {

int hasil = 0;

for (int i=0; i<n; i=i+2)

hasil = hasil + i;

return hasil;

}

void cetak(int n) {

for (int i=0; i<n; i=i+2)

cout << i << ” “;

}

int main(int argc, char *argv[])

{

int n = 10;

cout << jumlah(n);

cetak(n);

system(“PAUSE”);

return EXIT_SUCCESS;

}

Pengertian rekursif

Rekursif berarti bahwa suatu proses bisa memanggil dirinya sendiri. Menurut definisi dalam Microsoft Bookshelf, Rekursif adalah kemampuan suatu rutin untuk memanggil dirinya sendiri. Dalam Rekursif sebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil lewat pemanggil prosedur dan fungsi. Rekursif merupakan teknik pemrograman yang penting dan beberapa bahasa pemrograman mendukung keberadaan proses rekursif ini. Dalam prosedur dan fungsi, pemanggilan ke dirinya sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir.

Kelebihan perulangan rekursif:

• Sangat mudah untuk melakukan perulangan dengan batasan yang luas dalam artian melakukan perulangan dalam skala yang besar.

• Dapat melakukan perulangan dengan batasan fungsi.

Kekurangan perulangan rekursif:

• Tidak bisa melakukan nested loop atau looping bersarang.

• Biasanya membuat fungsi sulit untuk dipahami, hanya cocok untuk persoalan tertentu saja.

• Trace error sulit.

• Memerlukan stack yang lebih besar, sebab setiap kali fungsi dipanggil, variabel lokal dan parameter formal akan ditempatkan ke stack dan ada kalanya akan menyebabkan stack tak cukup lagi (Stack Overrun).

• Proses agak berbelit-belit karena terdapat pemangilan fungsi yang berulang-ulang dan pemanggilan data yang ditumpuk.

jika pada program 1, diubah kedalam bentuk rekursif :

Dalam bentuk rekursif :

#include <cstdlib>

#include <iostream>

using namespace std;

int jumlah(int n) {

if(n==0) return (0);

else return (n-2 + jumlah(n-2));

}

void cetak(int n) {

if(n!=0){

cetak(n-2);

cout << n-2 << ” “;

}

}

int main(int argc, char *argv[])

{

int n = 10;

cout << jumlah(n);

cetak(n);

system(“PAUSE”);

return EXIT_SUCCESS;

}

Rekursif  Versus  Iteratif

            Dalam beberapa situasi, pemecahan secara rekursif maupun secara iteratif mempunyai keuntungan dan kekurangan yang bisa saling diperbandingkan. Adalah cukup sulit untuk menentukan mana yang paling sederhana, paling jelas, paling efisien dan paling mudah disbanding yang lain. Boleh dikatakan pemilihan cara iterative maupun rekursif merupakan kesenangan seorang programmer dan tergantung konteks permasalahan yang akan dipecahkan sesuai dengan kesanggupan yang bersangkutan.

Persamaan antara perulangan iteratif dan rekursif:

• Iteratif dan rekursif merupakan metode atau teknik di dalam perulangan (looping).

• Sama-sama mengalami perulangan kondisi

Contoh program menghitung hari

#include<iostream>
#include<conio>

class hitung_hari{
friend istream& operator>>(istream&,hitung_hari&);
friend ostream& operator<<(ostream&,hitung_hari&);

public :
hitung_hari();
void hitung_dibulan();
void hitung_ditahun();

private :
int a,bulan,tahun,jum_hari;
int hari;

};

hitung_hari::hitung_hari(){
cout<<"menghitung jumlah hari dalam 1 bulan atau dalam 1 tahun"<<endl;
cout<<"pilihan : \n 1 menghitung hari dalam satu bulan \n 2 menghitung hari dalam satu tahun"<<endl;
cout<<endl;
}

istream& operator>>(istream& in,hitung_hari& masuk){
cout<<"masukkan pilihan anda : ";
in>>masuk.a;
if (masuk.a==1){
    cout<<"bulan ke- : ";
    in>>masuk.bulan;
    cout<<"tahun : ";
    in>>masuk.tahun;
    cout<<endl;
    void hitung_dibulan();
    }
else if (masuk.a==2){
   cout<<"tahun ke- : ";
   in>>masuk.tahun;
   cout<<endl;
   void hitung_ditahun();
    }
else cout<<"masukan salah!"<<endl;
return in;
}

void hitung_hari::hitung_dibulan(){
if(bulan==1 || bulan==3 || bulan==5 || bulan==7 || bulan==8 || bulan==10||bulan==12)jum_hari=31;
if(bulan==2 && tahun % 4==0)                                                        jum_hari=29;
if(bulan==2)                                                                                         jum_hari=28;
if(bulan==4 || bulan==6 || bulan==9 || bulan==11)                                                jum_hari=30;
}

void hitung_hari::hitung_ditahun(){
if(tahun%4==0) jum_hari=366;
else jum_hari=365;
cout<<endl;
}

ostream& operator<<(ostream& out,hitung_hari& keluar){
out<<"jumlah = "<<keluar.jum_hari<<" hari"<<endl;
return out;
}

void main(){
hitung_hari x;
cin>>x;
x.hitung_dibulan();
x.hitung_ditahun();
cout<<x;
getch();
}

program membalik 4 digit angka

#include <cstdlib>
#include <iostream>

using namespace std;
class balik{
      friend istream& operator>>(istream&, balik&);
      friend ostream& operator<<(ostream&, balik&);
     
      public:
             balik();
             void proses();
            
      private:
              int nilai;
              int a,b,c,d,e,f;
      };
     
balik::balik(){
        cout<<"membalik nilai 4 digit\n\n";
        }
       
istream& operator>>(istream& in, balik& mlebu){
         cout<<"masukkan nilai  : ";
         in>>mlebu.nilai;
         return in;
         }
        
ostream& operator<<(ostream& out, balik& metu){
         if(metu.nilai>9999 || metu.nilai<=999) {
                   out<<"range nilai salah"<<endl;
                   return out;
                   }
         else {
         out<<"setelah dibalik : "<<metu.f<<metu.e<<metu.c<<metu.a<<endl<<endl;
         return out;
         }
         }
        
void balik::proses(){
     a = nilai / 1000;
     b = nilai % 1000;
     c = b / 100;
     d = b % 100;
     e = d / 10;
     f = d % 10;
     
     }
int main(int argc, char *argv[])
{
    balik njo;
    cin>>njo;
    njo.proses();
    cout<<njo;
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

program mencari volume bola

#include <cstdlib>
#include <iostream>


using namespace std;

class livobo {
      friend ostream&operator<<(ostream&, livobo&);
      friend istream&operator>>(istream&, livobo&);
public:
       livobo();
       void li_vobo(){
            pi=3.14;
            volum =(4/3)*pi*r*r*r;
            luas=pi*r*r;}
private:
        int r;
        float luas, volum;
        double pi;
        };
livobo::livobo(){
                 cout<<"Program menghitung luas lingkaran dan volume bola dengan 1 masukkan\n";
                 }
istream& operator>>(istream& in, livobo& masukan){
         cout<<"Masukkan r (jari-jari) = ";
         in>>masukan.r;
         return in;}
ostream& operator<<(ostream& out, livobo& keluaran){
         out<<"luas lingkaran = "<<keluaran.luas<<endl;
         out<<"volume bola = "<<keluaran.volum<<endl;
         return out;}
int main(int argc, char *argv[])
{
    livobo x;
    cin>>x;
    x.li_vobo();
    cout<<x;
    system("PAUSE");
    return EXIT_SUCCESS;
}

program nilai max dan min

#include <iostream.h>
int main(){
  int a,maks,min;
  int c[100];

  maks=-100;
  min=100;
  cout<<"masukkan banyak data yang mau dimasukkan:";
  cin>>a;
  for (int t=0; t<a; t++){
      cout<<"data ke-"<<t+1<<":";
      cin>>c[t];
      }
  cout<<endl;
  cout<<"menampilkan data inputan"<<endl;
        for(int x=0; x<a; x++){
  cout<<"data ke-"<<x+1<<":"<<c[x]<<endl;
       if (c[x]>maks){
            maks=c[x];
            }
       if (c[x]<min){
            min=c[x];
            }
       }
       cout<<"nilai maksimal :"<<maks<<endl;
       cout<<"nilai minimal :"<<min<<endl;

  cin>>a;
        return 0;
}