Sabtu, 21 Juli 2012
Double Linked List
Elemen-elemen dihubungkan dengan dua pointer dalam satu elemen. Struktur ini menyebabkan list melintas baik ke depan maupun ke belakang.Masing-masing elemen pada double linked list terdiri dari tiga bagian, disamping
data dan pointer next, masing-masing elemen dilengkapi dengan pointer prev
yang menunjuk ke elemen sebelumnya. Double
linked list dibentuk
dengan menyusun sejumlah elemen sehingga pointer next
menunjuk ke elemen
yang mengikutinya dan pointer prev menunjuk ke elemen yang mendahuluinya. Untuk menunjukkan head dari double linked
list, maka pointer prev
dari elemen pertama menunjuk NULL. Untuk menunjukkan tail
dari double
linked list tersebut,
maka pointer next dari elemen terakhir menunjuk NULL. Susunan elemen yang
dihubungkan dalam bentuk double linked list dapat dilihat pada Gambar
di bawah ini
Untuk melintas kembali melalui double
linked list, kita gunakan
pointer prev dari elemen yang berurutan pada arah tail
ke head. Double linked
list mempunyai
fleksibilitas
yang lebih tinggi daripada single
linked list dalam
perpindahan pada list. Bentuk ini sangat berguna ketika akan meletakkan suatu elemen pada
list dan dapat memilih
dengan lebih bijaksana bagaimana memindahkannya. Sebagai
contoh, salah satu fleksibilitas dari double linked
list adalah dalam hal
memindahkan elemen daripada
menggunakan single linked list.
Contoh Program Double Linked List :
#include <conio.h>
#include <stdio.h>
#include <alloc.h>
typedef struct node t_node;
struct node{
int data;
t_node * next;
t_node * prev;
};
t_node * create(int data);
void forwardprint(t_node * kepala);
void backwardprint(t_node * kepala);
t_node * tambahdepan(t_node * kepala,int data);
t_node * tambahbelakang(t_node * ekor,int data);
t_node * hapusdepan(t_node * kepala);
t_node * hapusbelakang(t_node * ekor);
void main(){
t_node * kepala = NULL;
kepala = create(5);
t_node * ekor = create(6);
kepala->next = ekor;
ekor->prev = kepala;
kepala = tambahdepan(kepala, 4);
ekor = tambahbelakang(ekor,7);
forwardprint(kepala);
kepala = hapusdepan(kepala);
ekor = hapusbelakang(ekor);
forwardprint(kepala);
getch();
}
t_node * create(int data){
t_node * temp = (t_node*) malloc(sizeof(t_node*));
temp->next = NULL;
temp->prev = NULL;
temp->data = data;
}
void forwardprint(t_node * kepala){
while(kepala != NULL){
printf("%d ",kepala->data);
kepala = kepala->next;
}
printf("\n");
}
void backwardprint(t_node * ekor){
while(ekor != NULL){
printf("%d ",ekor->data);
ekor = ekor->prev;
}
printf("\n");
}
t_node * tambahdepan(t_node * kepala,int data){
t_node * baru = create(data);
baru->next = kepala;
kepala->prev = baru;
return baru;
}
t_node * tambahbelakang(t_node * ekor,int data){
t_node * baru = create(data);
ekor->next = baru;
baru->prev = ekor;
return baru;
}
t_node * hapusdepan(t_node * kepala){
t_node * temp = NULL;
if( kepala != NULL){
temp = kepala->next;
free(kepala);
}
if( temp !=NULL){
temp->prev = NULL;
}
return temp;
}
t_node * hapusbelakang(t_node * ekor){
t_node * temp = NULL;
if( ekor != NULL){
temp = ekor->prev;
free(ekor);
}
if( temp !=NULL){
temp->next = NULL;
}
return temp;
}
Contoh Program Double Linked List :
#include <conio.h>
#include <stdio.h>
#include <alloc.h>
typedef struct node t_node;
struct node{
int data;
t_node * next;
t_node * prev;
};
t_node * create(int data);
void forwardprint(t_node * kepala);
void backwardprint(t_node * kepala);
t_node * tambahdepan(t_node * kepala,int data);
t_node * tambahbelakang(t_node * ekor,int data);
t_node * hapusdepan(t_node * kepala);
t_node * hapusbelakang(t_node * ekor);
void main(){
t_node * kepala = NULL;
kepala = create(5);
t_node * ekor = create(6);
kepala->next = ekor;
ekor->prev = kepala;
kepala = tambahdepan(kepala, 4);
ekor = tambahbelakang(ekor,7);
forwardprint(kepala);
kepala = hapusdepan(kepala);
ekor = hapusbelakang(ekor);
forwardprint(kepala);
getch();
}
t_node * create(int data){
t_node * temp = (t_node*) malloc(sizeof(t_node*));
temp->next = NULL;
temp->prev = NULL;
temp->data = data;
}
void forwardprint(t_node * kepala){
while(kepala != NULL){
printf("%d ",kepala->data);
kepala = kepala->next;
}
printf("\n");
}
void backwardprint(t_node * ekor){
while(ekor != NULL){
printf("%d ",ekor->data);
ekor = ekor->prev;
}
printf("\n");
}
t_node * tambahdepan(t_node * kepala,int data){
t_node * baru = create(data);
baru->next = kepala;
kepala->prev = baru;
return baru;
}
t_node * tambahbelakang(t_node * ekor,int data){
t_node * baru = create(data);
ekor->next = baru;
baru->prev = ekor;
return baru;
}
t_node * hapusdepan(t_node * kepala){
t_node * temp = NULL;
if( kepala != NULL){
temp = kepala->next;
free(kepala);
}
if( temp !=NULL){
temp->prev = NULL;
}
return temp;
}
t_node * hapusbelakang(t_node * ekor){
t_node * temp = NULL;
if( ekor != NULL){
temp = ekor->prev;
free(ekor);
}
if( temp !=NULL){
temp->next = NULL;
}
return temp;
}
Single Linked List
Single Linked List adalah terdiri dari elemen-elemen
individu, dimana masing-masing dihubungkan dengan pointer tunggal.
Masing-masing elemen terdiri dari
dua bagian, yaitu sebuah data dan sebuah pointer yang disebut dengan pointer
next. Dengan menggunakan struktur two-member seperti ini, linked list dibentuk
dengan cara menunjuk pointer next suatu elemen ke elemen yang mengikutinya.
Pointer next
pada elemen terakhir merupakan NULL, yang menunjukkan akhir dari suatu
list. Elemen pada awal suatu list
disebut head, dan elemen terakhir dari suatu list disebut tail. untuk mengakses
elemen dalam linked list, dimulai dari head dan menggunakan pointer next dari
elemen selanjutnya untuk berpindah dari elemen ke elemen berikutnya sampai
elemen yang diminta dicapai.Dengan single linke list, list dapat dilintasi
hanya satu arah dari
head ke tail
karena masing-masing elemen
tidak terdapat link
dengan elemen sebelumnya. Sehingga, apabila kita mulai dari head dan
berpindah ke beberapa elemen dan berharap dapat mengakses element sebelumnya,
kita harus mulai dari head. Secara
konseptual, linked list
merupakan deretan elemen
yang berdampingan. Akan tetapi,
karena elemen-elemen tersebut dialokasikan secara dinamis bahwa tapi kenyataannya, linked
list akan terpencar- pencar di
memory, pointer next menjamin bahwa element selanjutnya dapat diakses.
Contoh Program Single Linked List :
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
typedef struct TNode{
int data;
TNode *next;
};
TNode *head;
TNode *bantu;
TNode *baru;
int isEmpty(){
if(head == NULL)
{return 1;}
else return 0;
}
void insertDepan(int databaru){
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
head->next = NULL;
}else {
baru->next = head;
head = baru;
}
cout << "\ndatabaru masuk :::"<<head->data;
}
void insertBelakang (int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
head->next = NULL;
}else {
bantu=head;
while(bantu->next!=NULL){
bantu=bantu->next;
}
bantu->next = baru;
}
cout<<"Data masuk\n";
}
void hapusDepan (){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head->next != NULL){
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
}else{
d = head->data;
head = NULL;
}
cout<<d<<" terhapus\n";
} else cout<<"Masih kosong\n";
}
void hapusBelakang(){
TNode *hapus,*bantu;
int d;
if (isEmpty()==0){
if(head->next != NULL){
bantu = head;
while(bantu->next->next!=NULL){
bantu = bantu->next;
}
hapus = bantu->next;
d = hapus->data;
bantu->next = NULL;
delete hapus;
}else{
d = head->data;
head = NULL;
}
cout<<d<<" terhapus\n";
} else cout<<"Masih kosong\n";
}
void tampil(){
bantu = head;
if(isEmpty()==0){
cout<< "\ndata yang ada dalam list\n";
while(bantu!=NULL){
cout<<bantu->data<<"\n";
bantu=bantu->next;
}
cout<<endl;
} else cout<<"Masih kosong\n";
}
Graph
Graph adalah kumpulan dari titik ( node ) dan garis dimana pasangan-pasangan titik ( node ) tersebut dihubungkan oleh segmen garis. Node ini biasa disebut simpul (verteks) dan segmen garis disebut ruas (edge).
Graph dipakai untuk membantu pemecahan masalah. Dari model
graph yang dibuat, suatu masalah dapat dipahami menjadi lebih mudah. Untuk
kemudian diturunkan metode pemecahannya.
- · Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis:
1. Graph berhingga (limited graph)
Graph berhingga adalah graph yang jumlah simpulnya, n,
berhingga.
2. Graph tak-berhingga (unlimited graph)
- Graph yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graph tak-berhingga.
·
Berdasarkan orientasi arah pada sisi, maka
secara umum graph dibedakan atas 2 jenis:
1. Graph tak-berarah (undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah disebut
graph tak-berarah.
2. Graph berarah (directed graph atau digraph)
Contoh Program Graph :
#include
#include
void main(){
bool ketemu,nolsemua;
int matrix[10] [10];
int i,j,jumlah_simpul,jumlah_sisi,asal,tujuan;
//isnisialisasi matrix
cout<<"jumlah simpul:";
cin>>jumlah_simpul;
cout<<"jumlah_sisi:";
cin>>jumlah_sisi;
for (i=1;i<=jumlah_simpul;i++)
for (j=1;j<=jumlah_simpul;j++)
matrix[i][j]=0;
//isi matrix sesuai input graf
for (i=1;i<=jumlah_sisi;i++){
cout<<"simpul asal:";
cin>>asal;
cout<<"simpul tujuan:";
cin>>tujuan;
matrix[asal][tujuan]=1;
matrix[tujuan][asal]=1;
}
//telusuri graf
i=1;nolsemua=false;
while (i<=jumlah_simpul && !nolsemua){
j=1;ketemu=false;
while (j<=jumlah_simpul && !ketemu){
if (matrix[i][j]==1)
ketemu=true;
else
j++;
}
if (!ketemu)
nolsemua=true;
else
i++;
}
if(nolsemua)
cout<<"graf tidak terhubung";
else
cout<<"graf terhubung";
getch();
}
bool ketemu,nolsemua;
int matrix[10] [10];
int i,j,jumlah_simpul,jumlah_sisi,asal,tujuan;
//isnisialisasi matrix
cout<<"jumlah simpul:";
cin>>jumlah_simpul;
cout<<"jumlah_sisi:";
cin>>jumlah_sisi;
for (i=1;i<=jumlah_simpul;i++)
for (j=1;j<=jumlah_simpul;j++)
matrix[i][j]=0;
//isi matrix sesuai input graf
for (i=1;i<=jumlah_sisi;i++){
cout<<"simpul asal:";
cin>>asal;
cout<<"simpul tujuan:";
cin>>tujuan;
matrix[asal][tujuan]=1;
matrix[tujuan][asal]=1;
}
//telusuri graf
i=1;nolsemua=false;
while (i<=jumlah_simpul && !nolsemua){
j=1;ketemu=false;
while (j<=jumlah_simpul && !ketemu){
if (matrix[i][j]==1)
ketemu=true;
else
j++;
}
if (!ketemu)
nolsemua=true;
else
i++;
}
if(nolsemua)
cout<<"graf tidak terhubung";
else
cout<<"graf terhubung";
getch();
}
Stack
Stack sendiri merupakan sebuah konsep untuk menyimpan dan mengambil dengan algoritma LIFO (“Last In First Out”) dimana data yang masuk duluan yang akan dikeluarkan terlebih dahulu, contoh realnya ketika kita memasukkan bola ke dalam suatu tabung, maka bola yang dimasukkan pertama kali akan diambil terakhir kali,, nah seperti itulah kira2 konsep stack.
- Operasi-operasi yang ada di stack yaitu antara lain:
- IsFull : mengecek apakah STACK sudah penuh
- IsEmpty : mengecek apakah STACK sudah kosong
- Push :menambah data pada STACK pada tumpukan paling atas
- Pop :mengambil data pada STACK pada tumpukan paling atas
- Print :mencetak semua data dalam tumpukan
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
//deklarasi 'STACK' dengan struct dan array
struct STACK
{
int data[5];
int atas;
};
//deklarasi variabel 'tumpuk' dari struct
STACK tumpuk;
void main()
{
clrscr();
int pilihan,baru,i;
//inisialisasi awal
tumpuk.atas=-1;
do
{
clrscr();
cout<<"1.Push Data"<<endl;
22
cout<<"2.Pop Data"<<endl;
cout<<"3.Print Data"<<endl;
cout<<endl;
cout<<"Pilihan = ";
cin>>pilihan;
switch(pilihan)
{
case 1:
{
if(tumpuk.atas==5-1)
{
cout<<"Tumpukan penuh";
getch();
}
else
{
cout<<"Data yang akan di-push = ";
cin>>baru;
tumpuk.atas++;
tumpuk.data[tumpuk.atas]=baru;
}
break;
}
case 2:
{
if(tumpuk.atas==-1)
{
cout<<"Tumpukan kosong";
getch();
}
else
{
cout<<"Data yang akan di-pop =
"<<tumpuk.data[tumpuk.atas]<<endl;
tumpuk.atas--;
getch();
}
break;
}
case 3:
{
if(tumpuk.atas==-1)
{
cout<<"Tumpukan kosong"<<endl;
getch();
}
else
{
cout<<"Data = "<<endl;
for(i=0; i<=tumpuk.atas; i++)
{
cout<<tumpuk.data[i]<<" ";
23
}
getch();
}
break;
}
default:
{
cout<<" Tidak ada dalam pilihan "<<endl;
}
}
}
while( pilihan >=1 && pilihan <= 3 );
getch();}
#include <conio.h>
#include <iostream.h>
//deklarasi 'STACK' dengan struct dan array
struct STACK
{
int data[5];
int atas;
};
//deklarasi variabel 'tumpuk' dari struct
STACK tumpuk;
void main()
{
clrscr();
int pilihan,baru,i;
//inisialisasi awal
tumpuk.atas=-1;
do
{
clrscr();
cout<<"1.Push Data"<<endl;
22
cout<<"2.Pop Data"<<endl;
cout<<"3.Print Data"<<endl;
cout<<endl;
cout<<"Pilihan = ";
cin>>pilihan;
switch(pilihan)
{
case 1:
{
if(tumpuk.atas==5-1)
{
cout<<"Tumpukan penuh";
getch();
}
else
{
cout<<"Data yang akan di-push = ";
cin>>baru;
tumpuk.atas++;
tumpuk.data[tumpuk.atas]=baru;
}
break;
}
case 2:
{
if(tumpuk.atas==-1)
{
cout<<"Tumpukan kosong";
getch();
}
else
{
cout<<"Data yang akan di-pop =
"<<tumpuk.data[tumpuk.atas]<<endl;
tumpuk.atas--;
getch();
}
break;
}
case 3:
{
if(tumpuk.atas==-1)
{
cout<<"Tumpukan kosong"<<endl;
getch();
}
else
{
cout<<"Data = "<<endl;
for(i=0; i<=tumpuk.atas; i++)
{
cout<<tumpuk.data[i]<<" ";
23
}
getch();
}
break;
}
default:
{
cout<<" Tidak ada dalam pilihan "<<endl;
}
}
}
while( pilihan >=1 && pilihan <= 3 );
getch();}
Tree
Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh
memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai
dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki
paling
banyak dua child
Merupakan
salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang
bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa
didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang
disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak
berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan
diuraikan istilah-istilah umum dalam tree :
a) Prodecessor : node
yang berada diatas node tertentu.
b) Successor : node yang berada di bawah node tertentu.
c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
e) Parent : predecssor satu level di atas suatu node.
f) Child : successor satu level di bawah suatu node.
g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.
h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
i) Size : banyaknya node dalam suatu tree.
j) Height : banyaknya tingkatan/level dalam suatu tree.
k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
l) Leaf : node-node dalam tree yang tak memiliki seccessor.
m) Degree : banyaknya child yang dimiliki suatu node.
Contoh Program Tree :
b) Successor : node yang berada di bawah node tertentu.
c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
e) Parent : predecssor satu level di atas suatu node.
f) Child : successor satu level di bawah suatu node.
g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.
h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
i) Size : banyaknya node dalam suatu tree.
j) Height : banyaknya tingkatan/level dalam suatu tree.
k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
l) Leaf : node-node dalam tree yang tak memiliki seccessor.
m) Degree : banyaknya child yang dimiliki suatu node.
Contoh Program Tree :
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>
//Defination of nodes of the tree
class node
{
public:
char value [11];
node *lchild;
node *rchild;
};
node *root = NULL; //root note is set to empty
//INSERT A NEW NODE IN THE TREE
void insert (node *z)
{
node
*x;
node
*y;
y =
NULL;
x =
root;
while ( x!=NULL)
{
y = x;
//compare value of new node with value of x
if(strcmp(z->value,x->value) < 0)
{
x= x-> lchild; //if new value less seek left child
}
else
{
x= x-> rchild; //if new value greater seek right child
}
}
//if
value of y is null write new node at root
if(
y==NULL )
{
root=z;
}
else if(strcmp(
z->value,y->value) < 0)
{
y -> lchild = z;
}
else
{
y-> rchild = z;
}
}
//PREORDER TRAVERSAL OF TREE BY RECURSION
void preorder( node *r )
{
cout<< r -> value << " ";
if
(r->lchild != NULL)
preorder (r->lchild);
if
(r->rchild != NULL)
preorder (r->rchild);
}
//INORDER TRAVERSAL OF TREE BY RECURSION
void inorder( node *r )
{
if
(r->lchild != NULL)
inorder (r->lchild);
cout<< r -> value << " ";
if
(r->rchild != NULL)
inorder (r->rchild);
}
//POSTORDER TRAVERSAL OF TREE BY RECURSION
void postorder( node *r )
{
if
(r->lchild != NULL)
postorder (r->lchild);
if
(r->rchild != NULL)
postorder (r->rchild);
cout<< r -> value << " ";
}
void main()
{
int
choice;
while (choice!=3)
{
clrscr();
cout<<"\n\n\t 1. Insert a element
to the tree.";
cout<<"\n\n\t 2. Traverse the tree.";
cout<<"\n\n\t 3. Exit.";
cout<<"\n\n\t Enter your choice : ";
cin>>choice;
switch (choice)
{
case 1: clrscr();
node *z=new node; //create a new node
cout<<"\n\n\tEnter a text string: ";
cin >> z->value;
z->rchild=NULL; //set left child as NULL
z->lchild=NULL; //set right child as NULL
insert (z); //insert node in tree
break;
case 2: clrscr();
cout << "\n\n\t Preorder Traversal : ";
preorder(root);
cout << "\n\n\t Inorder Traversal : ";
inorder(root);
cout << "\n\n\t Postorder Traversal : ";
postorder(root);
getch();
break;
case 3: break;
}
}
}
// end of program
Rabu, 18 Juli 2012
Linked List
linked list
merupakan sebuah struktur data yang digunakan untuk
menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan
penambahan, pengurangan, dan pencarian atas elemen data yang tersimpan
dalam daftar dilakukan secara lebih efektif. Pada praktiknya sebuah struktur
data memiliki elemen yang digunakan untuk saling menyimpan rujukan antara satu
dengan lainnya sehingga membentuk sebuah daftar abstrak, tiap-tiap elemen yang
terdapat pada daftar abstrak ini seringkali disebut sebagai node. karena mekanisme
rujukan yang saling terkait inilah disebut sebagai daftar berantai.
Sebuah daftar berantai dengan tiap-tiap node yang terdiri atas dua elemen, data integer, dan elemen rujukan ke node berikutnya
Daftar berantai merupakan bentuk struktur data paling
umum dan sederhana yang banyak digunakan untuk mengimplementasikan model
struktur data lainnya, termasuk antrian, stack, ataupun larik assosiatif.
- Keuntungan
Keuntungan utama pemanfaatan daftar
berantai dibandingkan larik, ataupun daftar biasa adalah kemudahan dan efektifitas kerja yang lebih baik dalam hal menambah,
mengurangi, serta mencari suatu elemen/node yang terdapat dalam daftar. Hal
tersebut dimungkinkan karena elemen-elemen yang terdapat pada sebuah daftar
berantai tidak ditempatkan pada sebuah blok memori komputer seperti halnya
larik ataupun daftar biasa, melainkan tiap-tiap elemen/node tersebut tersimpan
dalam blok memori terpisah, penambahan, pengurangan, ataupun penggantian node
dapat dilakukan dengan mengubah elemen rujukan atas tiap-tiap node yang
terkait. Kerugiannya, sebuah daftar berantai tidak memungkinkan pengaksesan
elemen secara acak, dalam artian untuk dapat mengakses node ke tiga pada contoh
di atas harus dilakukan dengan cara mengunjungi elemen-elemen sebelumnya, dimulai
dari elemen pertama, ke dua, seterusnya hingga pada lokasi elemen yang
dimaksudkan.
- Jenis-jenis Daftar Berantai
- Single Linked List
2. Double Linked List
3. Circular Linked List
Pada dua jenis daftar sebelumnya,
node terakhir dalam daftar tersebut merujuk pada null yang artinya akhir dari sebuah daftar,
begitu pula null sebagai rujukan node sebelumnya pada
node pertama bila daftar yang dimaksudkan adalah daftar bertaut ganda. Pada
daftar bertaut sirkular, informasi rujukan pada node terakhir akan merujuk pada
node pertama, dan rujukan pada node pertama akan merujuk pada node terakhir
bila yang digunakan sebagai dasar implementasi adalah daftar bertaut ganda.
Langganan:
Postingan (Atom)