RESUME

ALGORITMA STRUKTUR DATA

(STRUCT, STACK, DAN QUEUE)

OLEH:

NI KADEK DWI ASRI

(1108605048)

JURUSAN ILMU KOMPUTER

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS UDAYANA

2012

BAB I

STRUCT

1.1. Pengertian Struct

Struct yang merupakan kependekan dari structure (struktur) yaitu tipe data yang

dapat melakukan penyimpanan beberapa data yang saling terkait, berbeda halnya dengan

suatu array yang berisi dengan kumpulan elemen-elemen array yang bertipe sama, suatu

struct merupakan kumpulan dari satu atau beberapa variabel yang mempunyai tipe sama

atau berbeda.

Variabel-variabel yang membentuk suatu struktur ini selanjutnya disebut dengan

elemen-elemen atau angota struktur. Dengan demikian suatu struktur dimungkinkan

dapat diisi dengan elemen-elemen data bertipe int,float,char dan lainnya.

1.2. Bentuk Umum Struct

Bentuk umum dari struct adalah :

struct <struct_name>{

<type> <elemen_name1>;

<type> <elemen_name2>;

} <structure_variable>;

Contoh:

struct Buku{

char namabuku[20];

chat author[15];

int kodebuku;

};

1.3. Contoh Program Struct

#include<stdio.h>#include<conio.h>

struct buku{ char judulbuku[20]; char author[15]; char kodebuku[5]; int banyak;};void main (){ int jml,i; printf("Program input buku perpustakaan\n\n"); printf("Masukkan banyak buku : "); scanf("%d",&jml); struct buku perpus[jml]; for (i=0; i<jml; i++) { printf("\nInput data buku ke - %d \n",i+1); printf("Masukkan Kode Buku: "); fflush(stdin); gets(perpus[i].kodebuku); printf("Masukkan Judul Buku: "); fflush(stdin); gets(perpus[i].judulbuku); printf("Masukkan Nama Pengarang: "); fflush(stdin); gets(perpus[i].author); printf("Masukkan Jumlah Buku yang tersedia: "); scanf("%d",&perpus[i].banyak); }

printf("\n\n====================================\n\n\n"); printf("\nHasil Inputan Buku Perpustakaan: \n"); for (i=0; i<jml; i++) { printf("Data Buku ke-%d\n",i+1); printf("Kode buku: %s \n",perpus[i].kodebuku); printf("Judul buku : %s \n",perpus[i].judulbuku); printf("Nama Pengarang : %s \n", perpus[i].author); printf("Jumlah Buku yang tersedia: %d", perpus[i].banyak); printf("\n\n"); }};

Contoh Eksekusi Program:

Program input perpustakaanMasukkan banyak buku: 2

Input data buku ke – 1Masukkan Kode Buku: 001DCMasukkan Judul Buku: Detective Conan Vol.21Masukkan Nama Pengarang: Aoyama GoshoMasukkan Jumlah buku yang tersedia: 3

Input data buku ke – 2Masukkan Kode Buku: 023DEMasukkan Judul Buku: DoraemonMasukkan Nama Pengarang: Fujiko F. FujioMasukkan Jumlah buku yang tersedia: 1

================================Data buku ke-1Kode Buku : 001DCJudul Buku: Detective Conan Vol.21Nama Pengarang: Aoyama GoshoJumlah buku yang tersedia: 3

Kode Buku: 023DEJudul Buku: DoraemonNama Pengarang: Fujiko F. FujioJumlah buku yang tersedia: 1

Penjelasan Program:

Saat user memasukkan nilai dari “banyak buku” maka nilai tersebut akan disimpan di dalam

variabel “jml”.

struct buku perpus[jml];

merupakan perintah untuk memanggil kumpulan struct yang kita beri nama “perpus” dengan

banyak sesuai dengan jumlah inputan yang diinginkan user.

BAB II

STACK

2.1. Pengertian Stack

Stack disebut juga tumpukan dimana data hanya dapat dimasukkan dan diambil dari satu

sisi. Stack seperti tumpukan buku. Data dapat ditambahkan, tetapi tidak dapat disisipkan. Data dapat diambil, tetapi hanya tumpukan teratas. Karena itu, stack bersifat LIFO (Last In First Out).

Operasi yang dapat dilakukan stack adalah:1. Menambah (push)2. Mengambil (pop)3. megecek apakah stack penuh (isFull)4. mengecek apakah stack kosong (isEmpty)5. membersihkan stack (clear).6. Mencetak isi stack (print)

2.2. Operasi Umum Stack

Saat ini, kita akan mencoba membuat stack dan operasi-operasi yang dapat dilakukannya.

1. Mendefinisikan stack dengan menggunakan struct

typedef struct stack // Mendefinisikan stack dengan menggunakan struct{int top;char data [15][20]; // menampung 15 data dengan jumlah string max 20 huruf};

2. Mendefinisikan max_stack untuk maksimum isi stack#define max_stack 15

3. Membuat variable array sebagai implementasi stackstack tumpuk;

4. Mendeklarasikan operasi-operasi/fungsi yang dapat dilakukan stack.

a. Push (menginputkan data pada stack)

b. Pop (mengambil data pada stack)

c. IsFull (megecek apakah stack penuh)

d. isEmpty (mengecek apakah stack kosong)

int isEmpty(){

if (tumpuk.top==-1)return 1;

elsereturn 0;

}

int isFull(){

if (tumpuk.top==max_stack-1)return 1;

elsereturn 0;

}

void pop(){

printf ("data %s terambil",tumpuk.data[tumpuk.top]);tumpuk.top--;

}

void push(char d[20]){

tumpuk.top++;strcpy(tumpuk.data[tumpuk.top],d);printf("data berhasil dimasukkan");

}

e. clear (membersihkan seluruh isi stack)

f. print (mencetak seluruh isi stack)

2.3. Pemanfaatan Stack

Notasi Infix Postfix

Cara penulisan dengan notasi infix artinya operator ditulis diantara 2 operand . Cara

penulisan dengan notasi postfix artinya operator ditulis sesudah operand.

Konversi infix ke postfix :

= ( 6 - 2 ) * ( 5 + 4 )

= [ 6 2 - ] * [ 5 4 + ]

= [ 6 2 - ] [ 5 4 + ] *

= 6 2 - 5 4 + *

Pembuatan kalkulator SCIENTIFIC

Baca soal dari depan ke belakang

Jika operand à masukkan ke posftix

Jika operator

◦ Jika stack masih kosong à push ke stack

◦ Jika derajat operator soal > derajat operator top of stack

Push operator soal ke stack

◦ Selama derajat operator soal <= derajat operator top of stack

Pop top of stack dan masukkan ke posfix

Setelah semua dilakukan, push operator soal ke stack

void print(){

for (int i=tumpuk.top;i>=0;i--)printf ("%s\n",tumpuk.data[i]);

}

void clear(){

tumpuk.top=-1;printf("semua data terhapus.");

}

Jika sudah semua soal dibaca

◦ pop semua isi stack dan push ke postfix sesuai urutan

Gambar 2.1 Kalkulator SCIENTIFIC Sederhana Menggunakan Notasi Postfix

Pada gambar 2.1 kotak stack akan diisi oleh operator, sedangkan kotak postfix akan

diisi oleh angka/huruf. Untuk lebih mudah dipahami, perhatikanlah contoh soal

berikut: Misalkan kita ingin mencari hasil dari 4 * 5 – 6 / 3 + 3 – 1 dengan notasi

Postfix. Caranya adalah sebagai berikut:

Gambar 2.2 Mencari Hasil Dari 4 * 5 – 6 / 3 + 3 – 1 Menggunakan Notasi Postfix

Dari perhitungan notasi diatas, kita mendapatkan hasil : 4 5 * 6 3 / 3 + – 1 – . Sama

halnya dengan program, tentu saja notasi ini perlu diuji kebenarannya, jika 4 * 5 – 6 /

3 + 3 – 1 = 14. Apakah hasil yang menggunakan notasi prefix sama dengan hasil

perhitungan biasa? Mari kita selesaikan bersama-sama. Caranya adalah sbb:

Gambar 2.3 Menguji Kebenaran Notasi Postfix

Jadi dapat disimpulkan bahwa hasil menggunakan notasi postfix sama dengan

menghitung biasa.

Notasi Infix Prefix

Cara penulisan dengan notasi infix artinya operator ditulis diantara 2 operand. Cara

penulisan dengan notasi prefix artinya operator ditulis sebelum kedua operand yang

akan disajikan.

Proses konversi dari infix ke prefix :

= ( A + B ) * ( C – D )

= [ + A B ] * [ - C D ]

= * [ + A B ] [ - C D ]

= * + A B - C D

Sama halnya denga notasi postfix, notasi prefix ini juga dapat digunakan untuk

menghitung (SCIENTIFIC calculator) namun terdapat beberapa perbedaan pada

postfix dan prefix saat operand masuk ke stack, yaitu:

Gambar 2.4

Perbedaan dan Persamaan Antara Postfox dengan Prefix Saat Operator di Push Ke

Stack

2.4. Contoh Program Stack

int main(){

int stack[MAX]; int atas = -1; int n,nilai;do{

do{printf("Ketik bilangan yang akan di-pushed : "); scanf("%d",&nilai);push(stack, &atas, nilai);printf("Tekan 1 untuk melanjutkan : "); scanf("%d",&n);} while(n == 1);printf("Ketik 1 untuk mem-pop : "); scanf("%d",&n);printf("\n");while( n == 1){pop(stack, &atas, &nilai);printf("Bilangan yang di-pop : %d\n",nilai); printf("Ketik 1 untuk mem-pop : "); scanf("%d",&n);}printf("Ketik 1 untuk melanjutkan\n"); scanf("%d",&n);

} while(n == 1);return 0;

}

#include "stdio.h"#include "stdlib.h"#define MAX 5 /* The maximum size of the stack */void push(int stack[], int *top, int *nilai){

if(*top < MAX ){*top = *top + 1;stack[*top] = *nilai;

} else{printf(“Stack telah penuh…\n");exit(0);

}}void pop(int stack[], int *top, int *value){

if(*top >= 0){*value = stack[*top];

int main()*top = *top - 1;

} else{printf("Stack telah kosong shg tidak dpt mempop

lagi\n");exit(0);

}}

BAB III

QUEUE

3.1. Pengertian Queue

Queue disebut juga antrian dimana data masuk di satu sisi dan keluar di sisi yang lain. Karena itu, queue bersifat FIFO(First In First Out).

3.2. Operasi Umum QueueSaat ini, kita akan mencoba membuat queue dan operasi-operasi yang dapat dilakukannya. Hal-hal yang perlu dilakukan untuk membuat queue yaitu1. Mendefinisikan queue dengan menggunakan struct dimana kita perlu menggunakan

variable head dan tail sebagai penanda pada stack.

2. Mendefinisikan max untuk maksimum isi queue#define max 15

3. Membuat variable array sebagai implementasi queuequeue antri;

4. Mendeklarasikan operasi-operasi/fungsi yang dapat dilakukan queue.a. Enqueue (menginputkan data pada queue)

typedef struct queue // Mendefinisikan queue dengan menggunakan struct{int head;int tail;char data [15][20]; // menampung 15 data dengan jumlah string max 20 huruf};

b. Dequeue (mengambil data dari queue)

c. isEmpty (mengecek apakah antrian kosong)

d. isFull (mengecek apakah antrian penuh)

void enqueue(char d[20]){

antri.head=0;antri.tail++;strcpy(antri.data[antri.tail],d);printf("data berhasil dimasukkan");

}

void dequeue(){

printf ("data %s terambil",antri.data[antri.head]);for (int i=antri.head;i<=antri.tail;i++)

strcpy (antri.data[i],antri.data[i+1]);antri.tail--;

}

int isEmpty(){

if (antri.tail==-1){

antri.head=-1;return 1;

}else

return 0;}

e. clear (membersihkan seluruh isi antrian)

f. Print (mencetak seluruh isi antrian)

3.3. Contoh Program

Queue

Contoh program antrian sederhana:

int isFull(){

if (antri.tail==max-1)return 1;

elsereturn 0;

}

void clear(){

antri.head=antri.tail=-1;printf("semua data terhapus.");

}

void print(){

for (int i=0;i<=antri.tail;i++)printf ("%s\n",antri.data[i]);

}

#include<stdio.h>#include<conio.h>

void main (){ printf("\t\t\t=========================\n"); printf("\t\t\tProgram Antrian Sederhana\n"); printf("\t\t\t=========================\n\n"); int cek=0, data[5],pil,x,v,hapus; menu: printf("\n1. Tambah antrian\n2. Hapus antrian\n3. Lihat antrian\n4. Keluar\nSilahkan masukkan pilihan: "); scanf("%d",&pil); printf("\n"); switch(pil) { case 1: { if(cek== 5) printf("\n Antrian Penuh\n"); else { printf("\nMasukkan nilai: "); scanf("%d",&x); data[cek]=x; cek++;

} break; }

case 2: { if(cek==0) printf("\nAntrian Kosong\n"); else { hapus=data[0]; for(v=0;v<cek;v++) data[v]=data[v+1]; data[cek-1]=NULL; cek--; printf("\n Data dengan nilai %d terhapus\n",hapus); } break; } case 3: { if(cek==0) printf("\nAntrian Kosong\n"); else { printf("\n"); for( v=0;v<cek;v++) { printf("| %d |", data[v]);

} printf("\n"); } break; } case 4: { exit(0); break; } } if(pil<4) goto menu;}

Contoh eksekusi program: