BINARY TREE

"PROGRAM SILSILAH KELUARGA MENGGUNAKAN BINARY TREE"

#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<<"\nName of the Person: ";
    cin>>name;
    cout<<"Age of "<<name<<": ";
    cin>>age;
    cout<<name<<" is (m/f): ";
    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,"Female");
    if(ptr->g)
        strcpy(g,"Male");
    cout<<"\n\nName: "<< ptr->name <<endl;
    cout<<"Age: "<< ptr->age <<endl;
    cout<<"Gender: "<<g<<endl;
}

void familyTree::display(node* ptr)
{
    // Traverses the full n-array tree by recursion to display names of all people

    if(ptr==NULL)
        return;

    while(ptr!=NULL)
    {
        cout<< ptr->name <<endl;
        display(ptr->fc);
        ptr = ptr->ns;
    }
}

void familyTree::updateX(node* ptr,int x)
{
    // Traverses the full n-array tree by recursion and updates x value of all people

    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()
{

    /*
        Same hight: Sibiling if same parent, else cousin
        Difference of height = 1 - Parent if immediate, else uncule/aunt
        Difference oh height = 2 - Grand parents if same link, elss idk
    */

    char name1[50],name2[50];
    cout<<"Enter names of two persons:\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,"mother");
            if(ptrk->g)
                strcpy(str,"father");

            ptr = ptrk->fc;
            while(ptr!=NULL)
            {
                if(ptr==ptrk1)
                {
                    cout<<endl<<name1<<" is "<<name2<<"'s "<<str;
                    return;
                }
                ptr=ptr->ns;
            }
            strcpy(str,"aunt");
            if(ptrk->g)
                strcpy(str,"uncule");
            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<<"Too far relationship";
            break;
    }
}



node* familyTree::search(char s[50])
{
    /*
        Searches for the given name from start to it's sibilings and their children
        Returns the pointer of node where the name is present
    */

    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<<"***Not found***8";
    }
}

node* familyTree::traverseDown(node* ptr, char s[50])
{
    // Searches all the children

    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])
{

    //  Searches all the sibilings

    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<<"\nEnter any relation's name: ";
        char name[50];
        cin>>name;
        cout<<"\n1. Child\n2. Sibiling\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<<"\nPerson sucessfully added.\n";
}

void familyTree::addSib(node* a,node* b)
{
    // b is added as sibling of a

    while(a->ns!=NULL)
        a=a->ns;
    a->ns = b;

    b->x = a->x;
}

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

    // b is added as child as a (or) b is added as sibiling to last child of a

    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<<"Name of person in 1st tree to merge: ";
    cin>>name;
    cout<<T2->start->name<<" is __ to "<<name<<"\n1. Child 2. Sibling - ";;
    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<<"\nEnter the family tree number = ";
    cin>>n;
    while(1)
    {
#ifdef WINDOWS
        system("cls");
#endif // WINDOWS
#ifdef LINUX
        system("clear");
#endif // LINUX
        cout<<"\n\n\n\tFamily tree no = "<<n<<"\n\n\t1. Add new person\n\t2. Find relationship b/w two persons\n\t3. Search\n\t4. Destroy\n\t5. Display\n\t6. Change family tree\n\t7. Connect two family trees\n\t8. Exit\n\n\tEnter your choice = ";
        cin>>opt;
        cout<<endl;

        switch(opt)
        {

        default:
                cout<<"Invalid input";
                break;

        case 1:
                T[n].addNew();
                break;

        case 2:
                T[n].find();
                break;

        case 3:
                cout<<"Enter name of person to search: ";
                cin>>name;
                T[n].show(T[n].search(name));
                break;

        case 4:
                T[n].destroy(T[n].start);
                cout<<"Tree "<<n<<" has been destroyed sucessfully";
                break;

        case 5:
                T[n].display(T[n].start);
                break;

        case 6:
                cout<<"Enter family tree number: ";
                cin>>n;
                break;

        case 7:
               cout<<"Merge __ to __ \n";
               cin>>n2>>n1;
               connect(&T[n1],&T[n2]);
               break;

        case 8:
            return 0;

        }
        cout<<"\n\nPress any key to continue.....";
        cin>>c;
    }
}


jika dijalankan kurang lebih seperti ini outputnya yaa....

referensi saya:

Modul praktikum struktur data Pendidikan teknik informatika Universitas Muhammadiyah Surakarta

antrian "QUEUE"

ANTRIAN "QUEUE"

ANTRIAN (QUEUE)

Program struktur data jenis antrian (queue) yang terdapat operasi didalamnya (enqueue,dequeue,print,clear)


#include <stdio.h>
#include <conio.h>
#include <iostream>
#define MAX 6
using namespace std;
struct Queue
{
  int data[MAX];
  int head;
  int tail;
};

Queue antrian;
void Create()
{
  antrian.head=antrian.tail=-1;
}

int IsEmpty()
{
  if(antrian.tail==-1)
    return 1;
  else
    return 0;
}
int IsFull()
{
  if(antrian.tail==MAX-1)
    return 1;
  else
    return 0;
}

void Enqueue(int data)
{
  if(IsEmpty()==1)
  {
     antrian.head=antrian.tail=0;
     antrian.data[antrian.tail]=data;
     cout<<antrian.data[antrian.tail];
  }
  else
   //kodisi lainnya jika penuh() sama dengan 0 maka antrian.ekor ditambah 1
  {
     antrian.tail++;
     antrian.data[antrian.tail]=data;
     cout<<antrian.data[antrian.tail];
  }
}

int Dequeue()
{
  int i;
  int e=antrian.data[antrian.head];
  for(i=antrian.head;i<=antrian.tail-1;i++)
  {
    antrian.data[i]=antrian.data[i+1];
  }
  antrian.tail--;
  return e;
}

void Clear()
{
  antrian.head=antrian.tail=-1;
  cout<<"Data Clear";
}

void Tampil()
{
  if (IsEmpty()==0)
    for (int i=antrian.head;i<=antrian.tail; i++)
      cout<<antrian.data[i]<<"  ";
  else
    cout<<"Data Kosong\n";
}

int main()
{
  int pil;
  int data;
  Create();
  do
  {
    cout<<endl;
    cout<<"\n============MENU PILIHAN============\n";
    cout<<"1. Enqueue\n";
    cout<<"2. Dequeue\n";
    cout<<"3. Tampil\n";
    cout<<"4. Clear\n";
    cout<<"5. Keluar\n";
    cout<<"************************************\n";
    cout<<"Masukkan Pilihan Anda =  ";
    cin>>pil;
    switch(pil)
    {
    case 1:
      cout<<"Data : ";cin>>data;
      Enqueue(data);
      break;
     case 2:
      if (IsEmpty()==0)
        cout<<"Elemen yang keluar : "<<Dequeue();
      else
      cout<<"Data kosong"<<endl;
      break;
    case 3:
      Tampil();
      break;
    case 4:
      Clear();
      break;
    case 5:
      break;
    }
    getch();
} while(pil!=5);

}


jika dijalankan kurang lebih seperti ini outputnya yaa....

referensi saya:

Modul praktikum struktur data Pendidikan teknik informatika Universitas Muhammadiyah Surakarta

senarai berantai

Struktur Data Jenis Senarai Berantai

(Linked List)

Oleh: Amira Najma

11.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

22.JENIS - JENIS LINKED LIST

Ada beberapa jenis linked list, yaitu :

                                                               1.      Single Linked List

                                                               2.      Double Linked List

                                                               3.      Circular Linked List

                                                               4.      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 :

33. 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.

44. 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()

{

do

{

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;

}