DI SUSUN OLEH

NOVAL C. KESUMA (10512454)

BENNY ABDULLAH (10512457)

MUAZ MANOPPO (10512483)

TAUFIK SULAEMAN (10512477)

RADEN BAYU SUKARNA (105124

Stack

Pengertian Stack atau Tumpukan adalah suatu stuktur data yang penting dalam

pemrograman yang mempunyai sifat LIFO (Last In First Out), Benda yang terakhir

masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari

stack. Stack (Tumpukan) adalah list linier yang dikenali elemen puncaknya (TOP)

dan Aturan penyisipan dan penghapusan elemennya tertentu. Penyisipan selalu

dilakukan “di atas“ TOP dan Penghapusan selalu dilakukan pada TOP.

STACK ATAU TUMPUKAN PADA MATAKULIAH STRUKTUR DATA

Stack karena aturan penyisipan dan penghapusan semacam itu, TOP adalah satu-

satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir

akan menjadi elemen yang akan dihapus.Dikatakan bahwa elemen Stack akan

tersusun secara LIFO (Last In First Out).

karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi

elemen teratas dalam tumpukan.

Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen

Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil

elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu

Compo juga.

OPERASI-OPERASI/FUNGSI STACK

1. Push : digunakan untuk menambah item pada stack pada tumpukan paling

atas

2. Pop : digunakan untuk mengambil item pada stack pada tumpukan paling

atas

3. Clear : digunakan untuk mengosongkan stack

4. IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong

5. IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

INISIALISASI STACK

Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti

stack adalah KOSONG.!

Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen

teratas Stack sekarang. Top Of Stack akan selalu bergerak hingga mencapai MAX

of STACK sehingga menyebabkan stack PENUH!

Ilustrasi stack pada saat inisialisasi

Fungsi IsFull

Untuk memeriksa apakah stack sudah penuh?

Dengan cara memeriksa top of stack, jika sudah sama dengan MAX_STACK-1

maka full, jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full

Ilustrasi

Contoh program Stack

//program STACK

#include <iostream.h>

#include <conio.h>

#include <string.h>

struct

{

char data [15][100], max [15];

int i,j;

} stack;

void isi () // push untuk memasukan data

{

stack.i++;

cout<<"masukan data: ";

cin>>stack.max;

strcpy (stack.data[stack.i],stack.max);

}

void buang () // pop untuk mengambil data

{

if (stack.i>0)

{

cout<<"data yang terambil: "<<stack.data[stack.i]<<endl;

stack.i--; stack.j--;

}

else

cout<<"tak ada data yang terambil"<<endl;

}

void muncul (int n)//print untuk menampilkan data

{

if (stack.j>0)

{

for (int e=n; e>=1; e--)

{

cout<<stack.data[e]<<endl;

}

}

else

cout<<"tak ada data tersimpan"<<endl;

}

void hapus () // clear untuk menghapus data

{

stack.j=0; stack.i=0;

}

void main ()

{

int n,plh;

ayo:

clrscr();

cout<<"contoh program stack (tumpukan)\n\n";

cout<<"maksimal tumpukan data: "; cin>>n;

stack.data[n];

stack.i=0;

stack.j=0;

pusing:

clrscr();

cout<<"\n1. push \n2. pop \n3. print \n4. clear \n5. quit \n";

cout<<"\npilih :"; cin>>plh;

cout<<"\n";

if (plh==1)

{

if (stack.j<n)

{

stack.j++; isi();

}

else

{

cout<<"tumpukan penuh"<<endl; getch();

}

goto pusing;

}

else if (plh==2)

{

buang(); getch(); goto pusing;

}

else if (plh==3)

{

muncul (stack.i); getch(); goto pusing;

}

else if (plh==4)

{

hapus(); getch(); goto pusing;

}

else if (plh==5)

{

getch(); goto ayo;

}

else

{

cout<<"input yang anda masukan salah !!!";

getch(); goto ayo;

}

}

Tree

Treemerupakan salah satu bentuk struktur data tidak linear yang

menggambarkan hubungan yang bersifat hierarkis (hubungan one to many)

antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node

dengan elemen khusus yang disebut root atau akar.Cara penggunaan Tree :

1. notasi kurung

2. diagram venn

3. notasi tingkat

4. notasi garis

Jenis-jenis Tree :

1. Binnary 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.

Jenis jenis Binnary Tree

1. Full binnary tree

binnary tree ini tiap nodenya (kecuali leaf) memiliki 2 child dan tiap subtree harus

mempunyai panjang path yang sama.

1. complete binnary tree

mirip dengan full binnary tree, tetapi tiap subtree boleh memiliki panjang path

yang berbeda.

1. skewed binnary tree

binnary tree yang semua nodenya (kecuali leaf) hanya memiliki 1 child.

1. Implementasi Binary Tree

Binary Tree dapat diimplemntasikan dalam Pascal dengan menggunakan double

Linked List. Untuk nodenya, bisa dideklarasikan sbb :

Type Tree = ̂ node;

Node = record

Isi : TipeData;

Left,Right : Tree;

end;

Contoh ilustrasi Tree yang disusun dengan double linked list :

(Ket: LC=Left Child; RC=Right Child)

Operasi-operasi pada Binary Tree :

1. Create : Membentuk binary tree baru yang masih kosong.

2. Clear : Mengosongkan binary tree yang sudah ada.

3. Empty : Function untuk memeriksa apakah binary tree masih kosong.

4. Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert:

sebagai root, left child, atau right child. Khusus insert sebagai root,

tree harus dalam keadaan kosong.

5. Find : Mencari root, parent, left child, atau right child dari suatu node.

(Tree tak boleh kosong)

6. Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree

tidak boleh kosong)

7. Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree

tidak boleh kosong)

8. DeleteSub : Menghapus sebuah subtree (node beserta seluruh

descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah

itu pointer current akan berpindah ke parent dari node yang dihapus.

9. Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size,

height, serta average lengthnya. Tree tidak boleh kosong. (Average

Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

10. Traverse : Mengunjungi seluruh node-node pada tree, masing-masing

sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan

dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.

Langkah-Langkahnya Traverse :

1. PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi

Right Child.

2. InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right

Child.

3. PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang

dikunjungi.

2. Binary search Tree

Adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada

right child dan parentnya. Juga semua right child harus lebih besar dari left child

serta parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada

binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu

dalam binary tree. Contoh binary search tree umum :

Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa,

kecuali pada operasi insert, update, dan delete.

1. Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang

tepat. (Lokasi tidak ditentukan oleh user sendiri).

2. Update : Seperti pada Binary Tree biasa, namun disini uapte akan berpengaruh

pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree

tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada

tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya

tetap menjadi Binary Search Tree.

3. Delete : Seperti halnya update, delete dalam Binary Search Tree juga turut

mempengaruhi struktur dari tree tersebut.

(Keadaan awal merupakan lanjutan gambar sebelumnya)

Contoh program Tree

//Program tree

#include "iostream.h"

#include "string.h"

#include "conio.h"

struct simpulpohon

{

simpulpohon *induk;

simpulpohon *kiri;

simpulpohon *kanan;

char data;

};

class pohonbiner

{

private:

simpulpohon *akar;

int tambah(simpulpohon *orangtua, simpulpohon *baru);

void tampil(simpulpohon *simpul);

public:

pohonbiner();

int tambah(char data);

void tampil();

};

void main()

{

clrscr();

char data[] = "CARKDUPBENXZS";

pohonbiner pohon;

for (int i = 0; i < strlen(data); i++)

pohon.tambah(data[i]);

cout<<"Data ke Pohon Biner : "<<endl;

for (int x = 0; x < strlen(data); x++)

cout<<data[x];

cout<<endl;

cout<<endl;

cout<<"Hasil Pohon Biner :"<<endl;

pohon.tampil();

getch();

}

pohonbiner::pohonbiner()

{

akar = NULL;

}

int pohonbiner::tambah(char data)

{

simpulpohon *simpul;

simpul= new simpulpohon;

simpul->kiri = NULL;

simpul->kanan = NULL;

simpul->induk = NULL;

simpul->data = data;

if (akar == NULL)

{

akar = simpul;

return(1);

}

else

return(tambah(akar,simpul));

}

int pohonbiner::tambah(simpulpohon *orangtua, simpulpohon *baru)

{

if (baru->data ==orangtua->data)

{

delete baru;

return(0);

}

else if (baru->data < orangtua->data)

{

if (!orangtua->kiri)

{

orangtua->kiri = baru;

baru->induk = orangtua;

}

else

return(tambah(orangtua->kiri,baru));

}

else

{

if (!orangtua->kanan)

{

orangtua->kanan = baru;

baru->induk = orangtua;

}

else

return(tambah(orangtua->kanan,baru));

}

return(1);

}

void pohonbiner::tampil()

{

tampil(akar);

cout<<endl;

}

void pohonbiner::tampil(simpulpohon *simpul)

{

if (simpul)

{

if (simpul->kiri) tampil(simpul->kiri);

cout<<simpul->data;

if (simpul->kanan) tampil(simpul->kanan);

}

}

Graph

1. Pengertian Graf dan Tree serta Perbedaannya

Graf adalah kumpulan noktah (simpul) di dalam bidang dua dimensi yang

dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk

merepresentasikan objek-objek diskrit dan hubungan antara objek-objek

tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai

noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan

dengan garis (Edge).

G = (V, E)

Dimana

G = Graph

V = Simpul atau Vertex, atau Node, atau Titik

E = Busur atau Edge, atau arc

Graf merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali

struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa

diselesaikan dengan bantuan graf. Seringkali graf digunakan untuk

merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graf

dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkan setiap

kotanya sebagai sisi (edge) yang bobotnya (weight) adalah panjang dari jalan

tersebut.

Ada beberapa cara untuk menyimpan graph di dalam sitem komputer. Struktur

data bergantung pada struktur graph dan algoritma yang digunakan untuk

memmanipulasi graph. Secara teori salah satu dari keduanya dapat dibedakan

antara struktur list dan matriks, tetapi dalam penggunaannya struktur terbaik

yang sering digunakan adalah kombinasi keduanya.

• Graph tak berarah (undirected graph atau non-directed graph) :

• Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat

disebut busur AB atau BA

• Graph berarah (directed graph) :

• Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA

adalah e8.

• Graph Berbobot (Weighted Graph)

• Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah

simpul, maka busur tersebut dinyatakan memiliki bobot.

• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik,

jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

Tree dalam pemrograman merupakan struktur data yang tidak linear / non linear

yang digunakan terutama untuk merepresentasikan hubungan data yang bersifat

hierarkis antara elemen-elemennya. Kumpulan elemen yang salah satu

elemennya disebut dengan root (akar) dan sisa elemen yang lain disebut sebagai

simpul (node/vertex) yang terpecah menjadi sejumlah himpunan yang tidak saling

berhubungan satu sama lain, yang disebut subtree / cabang.

Adapun Perbedaan Graph dengan Tree sebagai berikut:

a. Pada Tree tidak terdapat Cycle

b. Pada Graph tidak memiliki root

2. Istilah-istilah dalam graf

Kemudian terdapat istilah-istilah yang berkaitan dengan graph yaitu:

a. Vertex

Adalah himpunan node / titik pada sebuah graph.

b. Edge

Adalah himpunan garis yang menghubungkan tiap node / vertex.

c. Adjacent

Adalah dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut

terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident dengan titik v2 dan

titik v3, tetapi sisi e3 = v2v3 tidak insident dengan titik v1 dan titik v4.

Titik v1 adjacent dengan titik v2 dan titik v3, tetapi titik v1 tidak adjacent dengan

titik v4.

d. Weight

Adalah Sebuah graf G = (V, E) disebut sebuah graf berbobot (weight graph),

apabila terdapat sebuah fungsi bobot bernilai real W pada himpunan E,

W : E ® R,

nilai W(e) disebut bobot untuk sisi e, " e Î E. Graf berbobot tersebut dinyatakan

pula sebagai G = (V, E, W).

Graf berbobot G = (V, E, W) dapat menyatakan

* suatu sistem perhubungan udara, di mana

· V = himpunan kota-kota

· E = himpunan penerbangan langsung dari satu kota ke kota lain

· W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu

* suatu sistem jaringan komputer, di mana

· V = himpunan komputer

· E = himpunan jalur komunikasi langsung antar dua komputer

· W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu

e. Path

Adalah Walk dengan setiap vertex berbeda. Contoh, P = D5B4C2A Sebuah walk

(W) didefinisikan sebagai urutan (tdk nol) vertex & edge. Diawali origin vertex dan

diakhiri terminus vertex. Dan setiap 2 edge berurutan adalah series. Contoh, W =

A1B3C4B1A2.

f. Cycle

Adalah Siklus ( Cycle ) atau Sirkuit ( Circuit ) Lintasan yang berawal dan berakhir

pada simpul yang sama

3. Representasi Graf

Dalam pemrograman, agar data yang ada dalam graph dapat diolah, maka graph

harus dinyatakan dalam suatu struktur data yang dapat mewakili graph tersebut.

Dalam hal ini graph perlu direpresentasikan kedalam bentuk array dan dimensi

yang sering disebut matrix atau direpresentasikan dalam bentuk linked list.

Bentuk mana yang dipilih biasanya tergantung kepada efisiensi dan kemudahan

dalam membuat program. Berikut ini beberapa bentuk representasi graph:

1. Representasi Graph dalam bentuk Matrix:

a. Adjacency Matrik Graf Tak Berarah

Matrik yang digambarkan pada gambar 1b merupakan representasi dalam bentuk

Adjacency Matrik dari graf yang digambarkan pada gambar 1a. Beberapa hal yang

dapat dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah

sebagai berikut :

1. Matrik yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah

simpul yang ada dalam graf tersebut. Matrik ini menyatakan hubungan antara

simpul satu dengan simpul lainnya.

2. Matrik yang terbentuk adalah matrik simetris dengan sumbu simetris adalah

diagonal dari titik kiri atas ke titik kanan bawah.

3. Data yang tedapat baik dalam baris maupun kolom, dapat menyatakan degree

sebuah simpul. Contoh : baik pada baris D maupun kolom D jumlah angka 1 nya

adalah 3 buah, dimana jumlah ini menyatakan degree simpul D.

b. Adjacency Matrik Graf Berarah

Matrik yang digambarkan pada gambar 2b merupakan representasi dalam bentuk

Adjacency Matrik dari graf yang digambarkan pada gambar 2a. Beberapa hal yang

dapat dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah

sebagai berikut :

1. Matrik yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah

simpul yang ada dalam graf tersebut. Matrik ini menyatakan hubungan antara

simpul satu dengan simpul lainnya.

2. Matrik yang terbentuk mungkin simetris mungkin juga tidak simetris. Menjadi

Simetris bila hubungan antara dua buah simpul (v1 dan v2) terdapat busur dari

v1 ke v2 dan juga sebaliknya.

3. Hal pokok yang dinyatakan oleh matrik ini adalah : busur yang ’keluar’ dari

suatu simpul. Dengan demikian, data yang terdapat dalam suatu baris, dapat

menyatakan outdegree simpul yang bersangkutan.

Contoh : Jumlah elemen yang nilainya = 1 pada baris B ada 3 elemen,ini

menyatakan jumlah outdegree simpul B adalah 3 buah.

4. Data yang terdapat dalam suatu kolom, dapat menyatakan indegree simpul

bersangkutan.

Contoh : Jumlah elemen yang nilainya 1 pada kolom B ada 2 elemen, ini

menyatakan indegree simpul B adalah 2 buah.

c. Adjacency Matrik Graf Berbobot Tak Berarah

Nilai yang ada dalam tiap elemen matrik, menyatakan bobot busur yang

menghubungkan dua buah simpul yang bersangkutan. Untuk dua buah simpul

yang tidak berhubungan langsung oleh sebuah busur, maka dianggap

dihubungkan oleh sebuah busur yang nilai bobotnya tidak terhingga. Dalam

pemograman, karena keperluan algoritma, maka dari total bobot seluruh busur

yang ada atau yang mungkin ada.

Contoh: pada gambar 3a simpul A dan C tidak berhubungan langsung melalui

sebuah busur, maka untuk elemen matrik yang bersangkutan diisi dengan nilai

999 karena nilai 999 dalam kasus ini cukup mewakili nilai tidak terhingga.

2. Representasi graf dalam bentuk Linked List

4. Adjacency List

Bila ingin direpresentasikan dalambentuk linked list, dapat diilustrasikan secara

sederhana seperti gamabar 4b. Dari ilustrasi sederhana tersebut terlihat ada 5

buah simpul A,B,C,D,dan E yang dibariskan dari atas kebawah seperti pada

gambar 4a. Kemudian dari masing-masing simpul ’keluar’ pointer kearah kanan

yang menunjuk simpul-simpul lain. Salah satu contoh, yang dapat dilihat pada

gambar 4b dimana A menunjuk simpul B dan simpul D.

Dalam Adjacency List, kita perlu membedakan antara simpul-vertex dan simpul-

edge. Simpul-vertex untuk menyatakan simpul atau vertex, dan simpul-edge

untuk menyatakan hubungan antar simpul yang biasa disebut busur. Struktur

keduanya bisa sama, bisa juga tidak sama,tergantung kebutuhan.Untuk

memudahkan pembuatan program, struktur kedua macam simpul dibuat sama

seperti yang digambarkan pada gambar 5c. Yang membedakan antara simpul-

vertex dan simpul-edge, adalah anggapan terhadap simpul tersebut. Dalam

contoh ini, terlihat struktur simpul dibuat terdiri dari 3 elemen. Satu elemen

untuk INFO, dua elemen untuk pointer.pointer kiri (left) dan pointer kanan (right).

Struct tipes{

Struct tipes *Left;

int INFO;

Struct tipes *Right;

};

Struct tipes *First,*Pvertex,*Pedge;

- Bila simpul dianggap sebagai simpul-vertex, maka :

Pointer left digunakan untuk menunjuk simpul berikutnya dalam untaian simpul-

simpul yang ada,atau diisi NULL bila sudah tidak ada simpul yang pelu

ditunjuk.Sedangkan pointer Right digunakan untuk menunjuk simpul edge yang

pertama.

- Bila Simpul dianggap sebagai simpul-edge, maka :

Pointer left digunakan untuk menunjuk simpul-vertex ‘tujuan’ yang berhubungan

dengan simpul-vertex ‘asal’ dan pointer right digunakan untuk menunjuk simpul-

edge berkiutnya bila masih ada, atau diisi NULL bila tak ada lagi simpul-busur yang

ditunjuk.

Contoh program graph

#include "stdio.h"

#include "conio.h"

typedef struct Node

{int data;

Node *kiri;

Node *kanan;

};

void tambah(Node **root,int databaru)

{

if((*root) == NULL)

{

Node *baru;

baru = new Node;

baru->data = databaru;

baru->kiri = NULL;

baru->kanan = NULL;

(*root) = baru;

(*root)->kiri = NULL;

(*root)->kanan = NULL;

printf("Data bertambah!");

}

else if(databaru < (*root)->data)

tambah(&(*root)->kiri,databaru);

else if(databaru > (*root)->data)

tambah(&(*root)->kanan,databaru);

else if(databaru == (*root)->data)

printf("Data sudah ada!");

}

void preOrder(Node *root)

{

if(root != NULL){ printf("%d ",root->data);

preOrder(root->kiri);

preOrder(root->kanan);

}}

void inOrder(Node *root)

{

if(root != NULL){ inOrder(root->kiri);

printf("%d ",root->data);

inOrder(root->kanan);

}}

void postOrder(Node *root)

{

if(root != NULL){ postOrder(root->kiri);

postOrder(root->kanan);

printf("%d ",root->data);

}}

void main()

{

int c, data;

Node *pohon,*t;

pohon = NULL;

char pil;

do {

clrscr();

printf("1. Tambah\n");

printf("2. Lihat Pre-order\n");

printf("3. Lihat In-order\n");

printf("4. Lihat Post-order\n");

printf("5. Keluar\n");

printf("Silahkan masukkan pilihan anda (1-5)... ");

pil=getche();

if(pil!='1' && pil !='2' && pil !='3' && pil!='4' && pil!='5' )

printf("\n\nAnda salah mengetikkan inputan...\n");

else

{

if(pil=='1')

{

printf("\n");

printf("\nData baru : ");scanf("%d", &data);

tambah(&pohon,data);

}

else

{

if(pil=='2')

{

printf("\n");

if(pohon!=NULL) preOrder(pohon);

else printf("Masih kosong!");

getch();

}

else

{

if(pil=='3')

{

printf("\n");

if(pohon!=NULL) inOrder(pohon);

else printf("Masih kosong!");

getch();

}

else

{

if(pil=='4')

{

printf("\n");

if(pohon!=NULL) postOrder(pohon);

else printf("Masih kosong!");

getch();

}}}

}}}

while(pil!='5');

}