Huffmen tree menggunakan link-list

PRAKTIKUM MANDIRI

HUFFMAN TREE

NAMA            : ISNI FACHRI RIZAL

NIM                : F1D013049

A.    Tujuan

a.       Memahami tentang tree

b.      Mengimplementasikan tree dalam pembutan program

B.     Permasalan

Membuat program yang menggunakan Huffmen tree

C.    Gambar Design Program

 

D.    Penjelasan Design

OPERASI	DESKRIPSI	C/C++
Bangun()	Membangun suatu link-list dan tree	void bangun(){head=NULL;tail=NULL; root=NULL; size=0;};
Masukan()	Memasukan data ke dalam link-list	void LL::masukkandata(char huruf){ buat node baru; if(size==0){        head=tmp;        tail=tmp; }else{        tail->next=tmp;        tmp->back=tail;        tail=tmp; } size++; }
Mengurut()	Mengurutkan data dari yang  terkecil hingga terbesar	void LL::urut(){ node*tmp=tail; node*tmp1,*tmp2; while(tmp->back!=NULL){ tmp1=head; tmp2=tmp1->next; while(tmp2!=NULL){ if(tmp1->jumlah>tmp2->jumlah){ if(tmp1==head&&tmp2!=tail){ tukar; }else if(tmp1!=head&&tmp2==tail) { tukar; }else if(tmp1==head&&tmp2==tail) { tukar; }else{ Tukar; }} tmp1=tmp1->next; tmp2=tmp2->next; } tmp=tmp->back; }}
Buat_tree()	Membuat binary tree	void LL::buattree(node*tmp1,node*tmp2){ node*tmp=new node; tmp->isi=NULL; tmp->back=NULL; tmp->kiri=tmp1; tmp->kanan=tmp2; tmp->jumlah=tmp1->jumlah+tmp2->jumlah; tmp->next=head; head->back=tmp; head=tmp;}
Tampil_binary	Menampilkan lokasi data dalam pohon binary	void LL::inorder(node*tmp, int x, int y) { int z,b=0,c=1; a[x]=y; z=x+1; if(tmp->kiri!=NULL&&tmp->kanan!=NULL){ inorder(tmp->kiri, z, b); inorder(tmp->kanan, z, c); }else if(tmp->kiri!=NULL){ inorder(tmp->kiri, z, b); }else if(tmp->kanan!=NULL){ inorder(tmp->kanan, z, c); }else{ cout<<tmp->isi<<" "; for(int i=1;i<z;i++){        cout<<a[i];} cout<<endl;}}

E.     Kode Program

#include <iostream> using namespace std; class LL{ private: struct node{        char isi;        int jumlah;        node*next;        node*back;        node*kiri;        node*kanan; }; node*root; node*head; node*tail; int size; int a[20]; public: void bangun(){head=NULL;tail=NULL;root=NULL;size=0;}; void masukkandata(char huruf); void menentukanjunmalahhuruf(); void hapus(node*tmp); void urut(); void ngambil(); void buattree(node*tmp1,node*tmp2); void tampil(); void inorder(node*tmp, int x, int y); }; void LL::masukkandata(char huruf){ node*tmp=new node; tmp->isi=huruf; tmp->jumlah=1; tmp->next=NULL; tmp->back=NULL; tmp->kiri=NULL; tmp->kanan=NULL; if(size==0){        head=tmp;        tail=tmp; }else{        tail->next=tmp;        tmp->back=tail;        tail=tmp; } size++; } void LL::menentukanjunmalahhuruf(){ node*tmp=head; node*tmp1=tmp->next; node*tmp2; while(tmp!=NULL){        tmp1=tmp->next;        while(tmp1!=NULL){              if(tmp->isi==tmp1->isi){                    tmp2=tmp1;                    tmp->jumlah++;                    tmp1=tmp1->next;                    hapus(tmp2);              }else{                    tmp1=tmp1->next;              }        }        tmp=tmp->next; } } void LL::hapus(node*tmp){ if(tmp==tail){        tail=tail->back;        tail->next=NULL;        tmp->back=NULL;        delete tmp; }else{        tmp->back->next=tmp->next;        tmp->next->back=tmp->back;        tmp->next=NULL;        tmp->back=NULL;        delete tmp; } } void LL::tampil(){ node*tmp=head; while(tmp!=NULL){        cout<<tmp->isi<<" "<<tmp->jumlah<<endl;        tmp=tmp->next; } cout<<endl; } void LL::urut(){ node*tmp=tail; node*tmp1,*tmp2; while(tmp->back!=NULL){        tmp1=head;        tmp2=tmp1->next;        while(tmp2!=NULL){              if(tmp1->jumlah>tmp2->jumlah){                    if(tmp1==head&&tmp2!=tail){                          tmp1->next=tmp2->next;                          tmp2->next->back=tmp2->back;                          tmp1->back=tmp2;                          tmp2->next=tmp1;                          tmp2->back=NULL;                          tmp1=tmp1->back;                          tmp2=tmp2->next;                          head=tmp1;                    }else if(tmp1!=head&&tmp2==tail){                          tmp1->back->next=tmp2;                          tmp2->back=tmp1->back;                          tmp1->next=NULL;                          tmp1->back=tmp2;                          tmp2->next=tmp1;                          tmp1=tmp1->back;                          tmp2=tmp2->next;                          tail=tail->next;                    }else if(tmp1==head&&tmp2==tail){                          tmp1->back=tmp2;                          tmp1->next=NULL;                          tmp2->back=NULL;                          tmp2->next=tmp1;                          tmp1=tmp1->back;                          tmp2=tmp2->next;                          head=head->back;                          tail=tail->next;                          tmp=tmp->next;                    }else{                          tmp1->back->next=tmp2;                          tmp2->next->back=tmp1;                          tmp1->next=tmp2->next;                          tmp2->back=tmp1->back;                          tmp1->back=tmp2;                          tmp2->next=tmp1;                          tmp1=tmp1->back;                          tmp2=tmp2->next;                          }              }              tmp1=tmp1->next;              tmp2=tmp2->next;        }        tmp=tmp->back; } } void LL::buattree(node*tmp1,node*tmp2){ node*tmp=new node; tmp->isi=NULL; tmp->back=NULL; tmp->kiri=tmp1; tmp->kanan=tmp2; tmp->jumlah=tmp1->jumlah+tmp2->jumlah; tmp->next=head; head->back=tmp; head=tmp; } void LL::ngambil(){ while(head!=tail){        if(head->next!=tail){              node*tmp1=head;              head=head->next;              tmp1->next=NULL;              head->back=NULL;              node*tmp2=head;              head=head->next;              tmp2->next=NULL;              head->back=NULL;              buattree(tmp1,tmp2);              urut();              size--;        }else{              head->next=NULL;              tail->back=NULL;              node*tmp=new node;              tmp->kiri=head;              tmp->kanan=tail;              tmp->jumlah=head->jumlah+tail->jumlah;              tmp->isi=NULL;              head=tail=tmp;              size--;        } } root=head; head=NULL; tail=NULL; inorder(root, 0, 0); } void LL::inorder(node*tmp, int x, int y) { int z,b=0,c=1; a[x]=y; z=x+1; if(tmp->kiri!=NULL&&tmp->kanan!=NULL){        inorder(tmp->kiri, z, b);        inorder(tmp->kanan, z, c); }else if(tmp->kiri!=NULL){        inorder(tmp->kiri, z, b); }else if(tmp->kanan!=NULL){        inorder(tmp->kanan, z, c); }else{        cout<<tmp->isi<<" ";        for(int i=1;i<z;i++){              cout<<a[i];        }        cout<<endl; } } void main(){ int a; char b; LL c; c.bangun(); cout<<"masukan jumlah huruf :";cin>>a; cout<<"masukan kata :"; for(int i=0;i<a;i++){        cin>>b;        c.masukkandata(b); } c.menentukanjunmalahhuruf(); c.tampil(); cout<<"Data setelah di Urut\n"; c.urut(); c.tampil(); cout<<"Data dalam tree\n"; c.ngambil(); system ("pause"); }

F.     Tampilan Ketika Dijalankan

G.    Cara Kerja Program

Pertama program akan meminta pengguna untuk memasukan jumlah huruf, kemudian meminta untuk memasukan kata/kalimat. Kata/kalimat yang dimasukan oleh pengguna akan dimasukan kedalam link-list dengan menggunakan fungsi masukan.

Setelah data dimasukan, program akan menentukan frekuensi masing-masing data dengan menghapus kembaran dari data yang sama.

Kemudian program akan mengurut data sesuai dengan jumlah frekuensinya (dari yang terkecil ke terbesar)

Dalam pembuatan binary tree, program akan mengambil dua frekuensi terkecil dari data yang kemudian akan diproses untuk membuat tree. Proses tersebut akan terus diulang sampai head==tail.

Setelah binary tree jadi maka program akan menampilkan data yang tersimpan pada tree beserta alurnya dari root sampai lokasi tempat data tersimpan.