Rabu, 30 Mei 2018

Contoh Program C++ BINARY TREE


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
Diposting oleh di Tidak ada komentar:

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
Diposting oleh di 1 komentar:
Langganan: Postingan (Atom)