Cari Ilmu

Rabu, 30 Mei 2018

Contoh Program C++ BINARY TREE

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. Ini adalah contoh implementadi pohon biner pada bahasa C++

#define WINDOWS

//#define LINUX

/** FAMILY TREE */

#include<iostream>

#include<string.h>

#include<stdlib.h>

using namespace std;

struct node

{

char name[50];

short int age,x; // x - height of node

bool g; // g- gender

node* fc; // Pointer to first child

node* ns; // Pointer to next sibiling

node();

void getData();

};

node::node()

{

fc=ns=NULL;

g=0;

strcpy(name,"");

age=x=0;

}

void node::getData()

{

char ch;

cout<<"\nNama orang: ";

cin>>name;

cout<<"Umur "<<name<<": ";

cin>>age;

cout<<name<<" Adalah (P/L): ";

cin>>ch;

if(ch=='m')

g=1;

}

class familyTree

{

public:

node* start;

familyTree();

node* traverseDown(node*,char[]); // Search functions

node* traverseRight(node*,char[]);

node* search(char[]);

void addSib(node*,node*); // Functions for adding new members

void addChild(node*,node*);

void addNew();

void find(); // Function to find relations

void show(node*); // Function to show details of particular person

void display(node*); // Function to display full tree

void destroy(node*); // Function to destroy full tree

void updateX(node*,int);

};

familyTree::familyTree()

{

start = NULL;

}

void familyTree::destroy(node* ptr)

{

node* temp = ptr;

if(ptr==NULL)

return;

while(ptr!=NULL)

{

destroy(ptr->fc);

temp = ptr;

ptr = ptr->ns;

delete temp;

}

start = NULL;

}

void familyTree::show(node* ptr)

{

char g[10];

strcpy(g,"Perempuan");

if(ptr->g)

strcpy(g,"Laki laki");

cout<<"\n\nNama: "<< ptr->name <<endl;

cout<<"Umur: "<< ptr->age <<endl;

cout<<"Jenis Kelamin: "<<g<<endl;

}

void familyTree::display(node* ptr)

{

if(ptr==NULL)

return;

while(ptr!=NULL)

{

cout<< ptr->name <<endl;

display(ptr->fc);

ptr = ptr->ns;

}

void familyTree::updateX(node* ptr,int x)

{

if(ptr==NULL)

return;

while(ptr!=NULL)

{

updateX(ptr->fc,x++);

if(ptr->ns!=NULL)

ptr->ns->x = x;

ptr = ptr->ns;

}

void familyTree::find()

{

char name1[50],name2[50];

cout<<"Masukkan nama dua orang: \n";

cin>>name1>>name2;

node* ptr1 = search(name1);

node* ptr2 = search(name2);

node* ptr;

node* ptrk=ptr1;

node* ptrk1=ptr2;

switch(ptr1->x - ptr2->x)

{

case 0:

char s[50];

strcpy(s,"sister");

if(ptr1->g)

strcpy(s,"brother");

ptr = ptr1;

while(ptr!=NULL)

{

if(ptr==ptr2)

{

cout<<endl<<name1<<" is "<<name2<<"'s "<<s<<endl;

return;

}

ptr = ptr->ns;

}

ptr = ptr2;

while(ptr!=NULL)

{

if(ptr==ptr1)

{

cout<<endl<<name1<<" is "<<name2<<"'s "<<s<<endl;

return;

}

ptr = ptr->ns;

}

cout<<endl<<name1<<" and "<<name2<<" are Cousins";

break;

case 1:

char str3[50];

strcpy(str3,"daughter");

if(ptr1->g)

strcpy(str3,"son");

ptr2 = ptr2->fc;

while(ptr2!=NULL)

{

if(ptr2==ptr1)

{

cout<<endl<<name1<<" is "<<name2<<"'s "<<str3;

return;

}

ptr2=ptr2->ns;

}

strcpy(str3,"niece");

if(ptr1->g)

strcpy(str3,"nephew");

cout<<endl<<name1<<" is "<<name2<<"'s "<<str3;

break;

case -1:

char str[10];

strcpy(str,"Ibu");

if(ptrk->g)

strcpy(str,"Ayah");

ptr = ptrk->fc;

while(ptr!=NULL)

{

if(ptr==ptrk1)

{

cout<<endl<<name1<<" is "<<name2<<"'s "<<str;

return;

}

ptr=ptr->ns;

}

strcpy(str,"Paman");

if(ptrk->g)

strcpy(str,"Cucu");

cout<<endl<<name1<<" is "<<name2<<"'s "<<str;

break;

case 2:

char str1[50];

strcpy(str1,"daughter");

if(ptr2->g)

strcpy(str1,"son");

ptr2 = ptr2->fc->fc;

while(ptr2!=NULL)

{

if(ptr2==ptr1)

{

cout<<endl<<name1<<" is grand "<<str1<<" of "<<name2;

return;

}

ptr2 = ptr2->ns;

}

break;

case -2:

char str2[50];

strcpy(str2,"mother");

if(ptr1->g)

strcpy(str2,"father");

ptr1 = ptr1->fc->fc;

while(ptr1!=NULL)

{

if(ptr1==ptr2)

{

cout<<endl<<name1<<" is grand "<<str2<<" of "<<name2;

return;

}

ptr1 = ptr1->ns;

}

break;

default:

cout<<"Hubungan terlalu jauh";

break;

}

node* familyTree::search(char s[50])

{

node *ptr = start;

if(strcmp(ptr->name,s)==0)

return ptr;

else if(traverseRight(start,s)!=NULL)

return traverseRight(start,s);

else if(traverseDown(start,s)!=NULL)

return traverseDown(start,s);

else

{

return NULL;

cout<<"***Tidak ditemukan***";

}

node* familyTree::traverseDown(node* ptr, char s[50])

{

ptr = ptr->fc;

while(ptr!=NULL)

{

if( strcmp(ptr->name,s)==0 )

return ptr;

else if(traverseRight(ptr,s)!=NULL)

return traverseRight(ptr,s);

else

ptr = ptr->fc;

}

return NULL;

}

node* familyTree::traverseRight(node* ptr, char s[50])

{

ptr = ptr->ns;

while(ptr!=NULL)

{

if(strcmp(ptr->name,s)==0)

return ptr;

else if (traverseDown(ptr,s)!=NULL)

return traverseDown(ptr,s);

else

ptr = ptr->ns;

}

return NULL;

}

void familyTree::addNew()

{

node* temp = new node;

temp->getData();

if(start == NULL)

{

start = temp;

temp->x=0;

}

else

{

cout<<"\nMasukkan nama relasi apa pun: ";

char name[50];

cin>>name;

cout<<"\n1. Anak\n2. Saudara kandung\n\n"<< temp->name <<" is ____ to "<<name<<" : ";

int opt;

cin>>opt;

switch(opt)

{

case 1:

addChild(search(name),temp);

break;

case 2:

addSib(search(name),temp);

break;

}

cout<<"\nOrang berhasil ditambahkan.\n";

}

void familyTree::addSib(node* a,node* b)

{

while(a->ns!=NULL)

a=a->ns;

a->ns = b;

b->x = a->x;

}

void familyTree::addChild(node* a,node* b)

{

if(a->fc==NULL)

a->fc = b;

else

addSib(a->fc,b);

b->x = a->x+1;

}

void connect(familyTree *T1, familyTree *T2)

{

char name[50];

int opt;

int x;

cout<<"Nama orang di pohon ke-1 untuk bergabung: ";

cin>>name;

cout<<T2->start->name<<" is __ to "<<name<<"\n1. Anak 2. Saudara Kandung - ";;

cin>>opt;

node *ptr = T1->search(name);

switch(opt)

{

case 1:

T1->addChild(ptr,T2->start);

x = ptr->x + 1;

break;

case 2:

T1->addSib(ptr,T2->start);

x = ptr->x;

break;

}

T2->updateX(T2->start,x);

T2->destroy(T2->start);

cout<<"\nMerged\n";

}

int main()

{

familyTree T[100];

int opt,n,n1,n2;

char c,name[50];

cout<<"\nMasukkan nomor pohon keluarga = ";

cin>>n;

while(1)

{

#ifdef WINDOWS

system("cls");

#endif

#ifdef LINUX

system("clear");

#endif

cout<<"\n\n\n\tPohon keluarga nomer = "<<n<<"\n\n\t1. Tambahkan orang baru\n\t2. Temukan hubungan antara dua orang\n\t3. Pencarian\n\t4. Hapus\n\t5. Tampilkan\n\t6. Ubah silsilah keluarga\n\t7. Hubungkan dua pohon keluarga\n\t8. Exit\n\n\tMasukkan pilihan Anda = ";

cin>>opt;

cout<<endl;

switch(opt)

{

default:

cout<<"Masukan tidak valid";

break;

case 1:

T[n].addNew();

break;

case 2:

T[n].find();

break;

case 3:

cout<<"Masukkan nama orang untuk dicari: ";

cin>>name;

T[n].show(T[n].search(name));

break;

case 4:

T[n].destroy(T[n].start);

cout<<"Tree "<<n<<" telah berhasil dihapus";

break;

case 5:

T[n].display(T[n].start);

break;

case 6:

cout<<"Masukkan nomor pohon keluarga: ";

cin>>n;

break;

case 7:

cout<<"Gabung __ ke __ \n";

cin>>n2>>n1;

connect(&T[n1],&T[n2]);

break;

case 8:

return 0;

}

cout<<"\n\ntekan tombol apa saja untuk melanjutkan.....";

cin>>c;

}

Untuk outputnya dapat dilihat pada gambar dibawah ini ............

TERIMAKASIH................

Sumber Referensi

Modul Praktikum Struktur Data. Sukirman dan Irma Yuliana, Surakarta Februari 2017

Contoh Program C++ ANTRIAN (QUEUE)

Contoh Program C++ ANTRIAN (QUEUE)

Queue atau antrian mempunyai prinsip yang berbeda dengan stack(tumpukan). Stack menggunakan prinsip last In First Out (LIFO) artinya yang terakhir masuk maka pertama keluar, sedangkan Queue menggunakan prinsip First In First Out (FIFO) artinya yang Pertama Masuk Pertama Keluar. Contoh antrian banyak kita jumpai dalam kehidupa sehari-hari misalnya antrian dalam membeli tiket bioskop atau kereta, yang datang terlebih dahulu maka akan mendapatkan pelayanan terlebih dahulu. Untuk contoh implementasinya dapat dilihat pada kode program dibawah :

#include <iostream>

#include<conio.h>

#include<stdlib.h>

#define MAX_SIZE 100

using namespace std;

int main() {

int item, choice, i;

int arr_queue[MAX_SIZE];

int rear = 0;

int front = 0;

int exit = 1;

cout << "\nContoh Antrian Sederhana - Array";

do {

cout << "\n\n Menu Utama Antrian";

cout << "\n1.Memasukkan \n2.Menghapus \n3.Menampilkan \nLainnya untuk keluar";

cout << "\nMasukkan Pilihan Anda : ";

cin>>choice;

switch (choice) {

case 1:

if (rear == MAX_SIZE)

cout << "\n## Antrian Tercapai Maks!!";

else {

cout << "\nMasukkan Nilai yang akan Dimasukkan : ";

cin>>item;

cout << "\n## Posisi : " << rear + 1 << " , Masukkan Nilai : " << item;

arr_queue[rear++] = item;

}

break;

case 2:

if (front == rear)

cout << "\n## Antrian Kosong!";

else {

cout << "\n## Posisi : " << front << " , Hapus Nilai :" << arr_queue[front];

front++;

}

break;

case 3:

cout << "\n## Banyak Antrian : " << (rear - front);

for (i = front; i < rear; i++)

cout << "\n## Posisi : " << i << " , Nilai : " << arr_queue[i];

break;

default:

exit = 0;

break;

}

while (exit);

return 0;

}

Untuk Output Programnya kurang lebih dapat dilihat pada gambar dibawah ini.....

TERIMAKASIH...............

Sumber Referensi
Modul Praktikum Struktur Data. Sukirman dan Irma Yuliana, Surakarta Februari 2017

Rabu, 25 April 2018

LINKED LIST

LINKED LIST

Oleh : Mochkammad Tabah Syafi’uddin

1. PENGERTIAN

Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.

· Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

· Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

2. JENIS - JENIS LINKED LIST

Ada beberapa jenis linked list, yaitu :

i. Single Linked List

ii. Double Linked List

iii. Circular Linked List

iv. Multiple Linked List

· Single Linked List

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.

Contoh :

Contoh codingannya :

struct Mahasiswa

{

char nama [25];

int usia;

struct mahasiswa *next;

}

*head, *tail;

· Double Linked List

Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

Contoh :

Contoh codingannya :

struct Mahasiswa

{

char nama [25];

int usia;

struct mahasiswa *next, *prev;

}

*head, *tail;

· 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:

o Circular Single Linked List

o Circular Double Linked List

· Multiple Linked List

Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer.

Contoh :

3. Operasi - Operasi yang ada pada Linked List

· Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalamsuatu linked list.

· IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.

· Find First

Fungsi ini mencari elemen pertama dari linked list.

· Find Next

Fungsi ini mencari elemen sesudah elemen yang ditunjuk now.

· Retrieve

Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

· Update

Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.

· Delete Now

Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.

· Delete Head

Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.

· Clear

Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

4. Algoritma dan contoh program LINKED LIST

a. Single Linked List

#include <stdio.h>
#include <iostream.h>
#include <conio.h>
struct TNode{
    int data;
    TNode *next;
};
TNode *head, *tail;

void init(){
    head = NULL;
    tail = NULL;
}
int isEmpty(){
if(tail == NULL) return 1;
else return 0;
}
void insertDepan(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
        head=tail=baru;
        tail->next=NULL;
     }
else {
         baru->next = head;
         head = baru;
}
cout<<"Data masuk\n";
}

void insertBelakang(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
tail=baru;
tail->next = NULL;
}
else {
tail->next = baru;
tail=baru;
}
cout<<"Data masuk\n";
}

void tampil(){
TNode *bantu;
bantu = head;
    if(isEmpty()==0){
        while(bantu!=NULL){
           cout<<bantu->data<<" ";
           bantu=bantu->next;
        }
     } else cout<<"Masih kosong\n";
}

void hapusDepan(){
    TNode *hapus;
    int d;
    if (isEmpty()==0){
        if(head!=tail){
           hapus = head;
           d = hapus->data;
           head = head->next;
           delete hapus;
        } else {
           d = tail->data;
           head=tail=NULL;
        }
    cout<<d<<"terhapus";
    } else cout<<"Masih kosong\n";
}
void hapusBelakang(){
    TNode *bantu,*hapus;
    int d;
    if (isEmpty()==0){
    bantu = head;
        if(head!=tail){
               while(bantu->next!=tail){
                bantu = bantu->next;
               }
               hapus = tail;
               tail=bantu;
               d = hapus->data;
               delete hapus;
               tail->next = NULL;
            }else {
            d = tail->data;
            head=tail=NULL;
            }
    cout<<d<<" terhapus\n";
    } else cout<<"Masih kosong\n";
}
void clear()
{
        TNode *bantu,*hapus;
        bantu = head;
        while(bantu!=NULL)
        {
            hapus = bantu;
            bantu = bantu->next;
            delete hapus;
        }
        head = NULL;
      printf("CLEAR");
}

main()
{
    int pil,databaru;

    do
    {
        clrscr();
        cout<<endl<<endl;
        cout<<"   ==========================="<<endl;
        cout<<"   = PROGRAM LINKED LIST    ="<<endl;
        cout<<"   ==========================="<<endl;
        cout<<"   = 1. Insert Depan         ="<<endl;
        cout<<"   = 2. Insert Belakang      ="<<endl;
        cout<<"   = 3. Delete Depan         ="<<endl;
        cout<<"   = 4. Delete Belakang      ="<<endl;
        cout<<"   = 5. Tampil Data          ="<<endl;
        cout<<"   = 6. Clear                ="<<endl;
        cout<<"   = 7. Exit                 ="<<endl;
        cout<<"   ==========================="<<endl;
        cout<<"   Masukan Pilihan : ";cin>>pil;
        switch (pil)
        {
            case 1: clrscr();{
                cout<<"Masukkan Data = ";
                cin>>databaru;
                insertDepan(databaru);
                break;
            }
            case 2: clrscr();{
                cout<<"Masukkan Data = ";
                cin>>databaru;
                insertBelakang(databaru);
                break;
            }
            case 3: clrscr();{
                hapusDepan();
                break;
            }
            case 4: clrscr();{
                hapusBelakang();
                break;
            }
            case 5: clrscr();{
                tampil();
                break;
            }
            case 6: clrscr();{
                clear();
                break;
            }
            case 7: {
            return 0;
             break;
            }
            default : clrscr();{
            cout<<"\n Maaf, Pilihan yang anda pilih tidak tersedia!";
            }

        }
        getch();
    }
    while(pil!=7);
}

b.Double Linked List

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

int pil;

void pilih();

void buat_baru();

void tambah_belakang();

void tambah_depan();

void hapus_belakang();

void hapus_depan();

void tampil();

void tambah_tengah();

void hapus_tengah();

struct node

{

char nama [20];

int umur;

float tinggi;

node *prev, *next;

};

node *baru, *head=NULL, *tail=NULL,*hapus,*bantu,*bantu2;

void main()

{

clrscr();

cout<<"MENU DOUBLE LINKEDLIST"<<endl;

cout<<"1. Tambah Depan"<<endl;

cout<<"2. Tambah Belakang"<<endl;

cout<<"3. Hapus Depan"<<endl;

cout<<"4. Hapus Belakang"<<endl;

cout<<"5. Tampilkan"<<endl;

cout<<"6. Tambah Tengah"<<endl;

cout<<"7. Hapus Tengah"<<endl;

cout<<"8. Selesai"<<endl;

cout<<"Pilihan Anda : ";

cin>>pil;

pilih();

} while(pil!=8);

}

void pilih()

{

if(pil==1)

tambah_depan();

else if(pil==2)

tambah_belakang();

else if(pil==3)

hapus_depan();

else if(pil==4)

hapus_belakang();

else if(pil==5)

tampil();

else if(pil==6)

tambah_tengah();

else if(pil==7)

hapus_tengah();

else

cout<<"selesai";

}

void buat_baru()

{

baru = new(node);

cout<<"input nama : ";cin>>baru->nama;

cout<<"input umur : ";cin>>baru->umur;

cout<<"input tinggi : ";cin>>baru->tinggi;

baru->prev=NULL;

baru->next=NULL;

}

void tambah_belakang()

{

buat_baru();

if(head==NULL)

{

head=baru;

tail=baru;

}

else

{

tail->next=baru;

baru->prev=tail;

tail=baru;

}

cout<<endl<<endl;

tampil();

}

void tambah_depan()

{

buat_baru();

if(head==NULL)

{

head=baru;

tail=baru;

}

else

{

baru->next=head;

head->prev=baru;

head=baru;

}

cout<<endl<<endl;

tampil();

}

void hapus_depan()

{

if (head==NULL)

cout<<"Kosong";

else if (head->next==NULL)

{

hapus=head;

head=NULL;

tail=NULL;

delete hapus;

}

else

{

hapus=head;

head=hapus->next;

head->prev=NULL;

delete hapus;

}

cout<<endl<<endl;

tampil();

}

void hapus_belakang()

{

if (head==NULL)

cout<<"Kosong";

else if (head->next==NULL)

{

hapus=head;

head=NULL;

tail=NULL;

delete hapus;

}

else

{

hapus=tail;

tail=hapus->prev;

tail->next=NULL;

delete hapus;

}

cout<<endl<<endl;

tampil();

}

void tampil()

{

if (head==NULL)

cout<<"Kosong";

else

{

bantu=head;

while(bantu!=NULL)

{

cout<<" nama : "<<bantu->nama;

cout<<" umur : "<<bantu->umur;

cout<<" tinggi : "<<bantu->tinggi<<endl;

bantu=bantu->next;

}

getch();

}

void tambah_tengah()

{

int sisip;

cout<<"Masukan Posisi Sisip Anda : ";cin>>sisip;

bantu=head;

for(int i=1;i<sisip-1;i++)

{

bantu=bantu->next;

}

buat_baru();

bantu2=bantu->next;

bantu->next=baru;

baru->prev=bantu;

baru->next=bantu2;

bantu2->prev=baru;

}

void hapus_tengah()

{

int sisip;

cout<<"Masukan Posisi Sisip Anda : ";cin>>sisip;

bantu=head;

for(int i=1;i<sisip-1;i++)

{

bantu=bantu->next;

}

hapus=bantu->next;

bantu2=hapus->next;

bantu->next=hapus->next;

bantu2->prev=bantu;

delete hapus;

}