Modul Praktikum Struktur Data DNBS 2009

Modul Praktikum Struktur Data

Menggunakan Bahasa Pemrograman Turbo C 2.0

Lab Komputer UIN SUNAN GUNUNG DJATI Bandung

2008

Modul Praktikum Struktur Data UIN SGD

2

Daftar Isi

Pengantar ..........................................................................................................................................................3Pendahuluan .....................................................................................................................................................4

Struktur umum Bahasa C ...............................................................................................................................4I. Array (larik) satu dimensi............................................................................................................................6Materi ke-1........................................................................................................................................................6

Pengertian.......................................................................................................................................................6Contoh program: ............................................................................................................................................6

II. Array (larik) dua dimensi...........................................................................................................................8Materi ke-2........................................................................................................................................................8

Pengertian.......................................................................................................................................................8Contoh:...........................................................................................................................................................8

III. Record.......................................................................................................................................................11Materi ke-3......................................................................................................................................................11

Pengertian.....................................................................................................................................................11Contoh program. ..........................................................................................................................................11

IV. Buble Sort .................................................................................................................................................14Materi ke-4......................................................................................................................................................14

Pengertian.....................................................................................................................................................14Contoh..........................................................................................................................................................14

V. Insertion Sort .............................................................................................................................................18Materi ke-5......................................................................................................................................................18


VI. Searching ..................................................................................................................................................22Materi ke-6......................................................................................................................................................22


VII. Stack ........................................................................................................................................................27Materi ke-7......................................................................................................................................................27


VIII. Pointer dan Singly-Linked List ...........................................................................................................31Materi ke-8......................................................................................................................................................31


IX. Doubly-Linked List..................................................................................................................................36Materi ke-9......................................................................................................................................................36

Pengertian.....................................................................................................................................................36Studi Kasus ..................................................................................................................................................37

X. Antrian .......................................................................................................................................................38Materi ke-10....................................................................................................................................................38


XI. Binary-Tree ..............................................................................................................................................41Materi ke-11....................................................................................................................................................41


Referensi .........................................................................................................................................................44

Modul Praktikum Struktur Data STMIK DHARMA NEGARA

3

PengantarMata Kuliah Struktur data adalah kelanjutan dari mata kuliah Algoritma Pemrograman. Bila pada

perkuliahan sebelumnya mahasiswa diajari teknik-teknik dasar pemrograman prosedural, pada mata kuliah ini diajarkan lebih lanjut tentang tipe-tipe dan struktur-struktur data yang belum dikenal pada perkuliahan sebelumnya.

Tipe data yang akan diajarkan pada perkuliahan ini adalah:1. Array, satu dimensi dan dua dimensi. (dikenal juga dg nama larik)2. Record3. PointerStruktur data yang akan diajarkan adalah:1. Stack (tumpukan)2. Linked list [single dan double] (sering disebut sebagai senarai)3. Queue (antrean)4. Tree (pohon)Bahasa pemrograman yang diberikan adalah Turbo C 2.0, dengan alasan bahasa C adalah bahasa

standar dunia informatika/IT. Misalnya, pemrograman pada Linux/Unix, menggunakan bahasa C dan C++. Bahasa Java dikembangkan dari bahasa C++. Pemrograman Java Script mengadopsi sintaks-sintaks bahasa C dan C++ juga.

Pada sejumlah pertemuan awal di laboratorium, praktikan dipandu menggunakan bahasa C, dengan penjelasan seperlunya yang akan diberikan di tempat praktuk. Pada tahap selanjutnya, praktikan akan diberi tugas untuk mengkonversi algoritma menjadi sintaks-sintaks bahasa C.

Pemrograman terstruktur, yaitu penggunaan function dan prosedur tidak akan banyak dijelaskan dalam modul ini. Diasumsikan mahasiswa sudah menguasainya pada perkuliahan sebelumnya. Penjelasan hanya akan diberikan dalam hal penggunaan sintaks-sintaks bahasa C-nya saja.

Semoga modul ini dapat bermanfaat bagi pengembangan wawasan para praktikan. Amin.

Bandung, 17 Februari 2009


4

Pendahuluan

Bahasa C dikembangkan sejak akhir tahun 1950-an, pada komputer generasi kedua, oleh Dennis Richie. Pada perkembangannya, bahasa C menjadi bahasa standar dalam pemrograman/dunia IT, sebagaimana telah disebutkan pada bagian Pengantar.

Bahasa C, tergolong bahasa pemrograman tingkat menengah. Pada awalnya bahasa C hanya merupakan bahasa pemrograman prosedural, namun pada perkembangannya, di awal tahun 80-an mulai dikembangkan C++. yang lebih merupakan bahasa pemrograman berbasis objek, meskipun dapat diperlakukan juga sebagai bahasa pemrograman prosedural.

Sebagai bahasa prosedural, C memiliki kesamaan dengan bahasa Pascal, yaitu dapat melakukan pemrograman terstruktur (penggunaan function dan procedure), dan penggunaan include atau unit. Bedanya, function dan procedure dalam bahasa C tidak perlu diberi kata-kata kunci function dan proceduresebagaimana dalam Pascal.

Penulisan procedure dalam bahasa C:void <nama_procedure> ([<tipe data parameter, ...>])

misalnyavoid clrscr();

mendeklarasikan sebuah procedure bernama clrscr, tanpa parameter masukan apa pun.Penulisan function dalam bahasa C:<tipe_data_kembalian> <nama_function> ([tipe data parameter, ...>])

misalnya:float sinus(float x);

mendeklarasikan sebuah fungsi dengan nama sinur, return value-nya bertipe floating point, dan parameter x bertipe floating point juga.

Harus diperhatikan, bahwa penulisan sintaks dalam bahasa C bersifat case sensitive, artinya, bahasa C membedakan hurud besar dan huruf kecil. Semua perintah (command) dan keyword dalam bahasa C berupa huruf kecil, tidak ada huruf kapitalnya, kecuali beberapa konstanta, misalnya NULL.

Jadi, kalau kita memiliki variabel Abjad, akan berbeda dengan variabel abjad. A berbeda dengan a, dan sebagainya. Juga, kita tidak dibenarkan menuliskan char dengan Char, CHAR, dsb. Fungsi sin(x)berbeda dengan fungsi Sin(x), prosedur clrscr() berbeda dengan ClrScr().

Struktur umum Bahasa CStruktur umum bahasa C

/* deklarasi header file (semacam unit di pascal) */#include <stdio.h>#...

/* deklarasi tipe baru */typedef char kata[80];

/* deklarasi prosedur dan fungsi */void tampilkan(kata k); /* perhatikan, di akhir deklarasi */int factorial(int n); /* diakhiri dengan ‘;’ */

/* deklarasi variabel global */char nama[20]; /* perhatikan, di akhir sintaks*/int NMaks; /* selalu diakhiri dengan ‘;’ */

/* program utama */main(){ /* deklarasi variabel lokal */ int pilih; ...;

/* blok utama program */


5

perintah...; perintah...;}

/* deskripsi fungsi dan prosedur */void tampilkan(kata k) /* pada deskripsi tidak ada ‘;’ */ { /* yg ada: kurung kurawal buka ‘{’ */ /* deklarasi variabel lokal */ int i; perintah ...; perintah ...;} /* dan: kurung kurawal tutup ‘}’ */int factorial(int n){ /* deklarasi variabel lokal */ int i; perintah ...; perintah ...; return(...) /* function selalu diakhiri keyword return */}


6

I. Array (larik) satu dimensi

Materi ke-1

PengertianArray adalah sekumpulan data yang bertipe sama, yang anggota-anggotanya dapat diakses

berdasarkan nomor indeks.Misalnya, ada 26 huruf. Kita sebut saja, array Abjad, adalah kumpulan 26 buah karakter yang berisi

nama-nama abjad latin. Anggota pertama, “A”. Anggota kedua, “B”. Dan seterusnya, hingga anggota ke-26 adalah string “Z”.

Dalam notasi algoritma kita tuliskan:Abjad : array [1..26] of character;

dan pemberian nilainya bisa melalui dua cara:1. satu per satuAbjad[1] “A”Abjad[2] “B”... dst ... Abjad[26] “Z”

2. langsung:Abjad {‘A’,’B’,’C’, ... dst sampai ... ‘Y’,’Z’}

dalam notasi Algoritma, indeks array dimulai dari 1. Artinya kalau kita punya array dengan 26 anggota, indeksnya mulai 1, 2, 3, ... sampai 26.

Penulisasan Array dalam bahasa C sedikit berbeda.Untuk array Abjad di atas, dituliskan sebagai berikut:char Abjad[26];

Dalam bahasa C, indeks array dimulai dari 0. Jadi kalau kita punya array dengan jumlah anggota 26, maka indeksnya adalah dari 0 sampai 25.

Pemberian nilai untuk array Abjad di atas:1. satu per satuAbjad[1] = ‘A’;Abjad[2] = ‘B’;... dst ... Abjad[26] ‘Z’;

2. langsungAbjad = {‘A’,’B’,’C’, ... dst sampai ... ‘Y’,’Z’};

Contoh program:

1. Array 1 dimensi untuk character

/* 01aryc1.c: memperkenalkan struktur data array. *//* dengan elemen data charakter *//* array satu dimensi */

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

char n[100];int nmaks;

main(){ int i;

clrscr(); printf(" penggunaan array untuk karakter\n"); printf("-----------------------------------\n"); printf("jumlah huruf yang akan diinput: ");


7

scanf("%d",&nmaks);

for (i=0;i<nmaks;i++) { printf("huruf ke-%d:",i+1);

scanf("%s",&n[i]); }

printf("data yang anda masukkan: \n"); for (i=0;i<nmaks;i++) printf("huruf ke-%d: %c\n",i,n[i]); getch();}

2. Array 1 dimensi untuk tipe numerik (integer/real)

/* 01aryi1.c: memperkenalkan struktur data array. *//* dengan elemen data integer *//* array satu dimensi */


int n[100];int nmaks;

main(){ int i;

clrscr(); printf(" penggunaan array untuk integer\n"); printf("----------------------------------\n"); printf("jumlah data yang akan diinput: "); scanf("%d",&nmaks);

for (i=0;i<nmaks;i++) { printf("data ke-%d:",i+1);

scanf("%d",&n[i]); }

printf("data yang anda masukkan: \n"); for (i=0;i<nmaks;i++)

printf("data ke-%d: %d\n",i,n[i]); getch();}


8

II. Array (larik) dua dimensi

Materi ke-2

PengertianLarik/array dua dimensi adalah sekumpulan array satu dimensi.Dalam bahasa C, tidak ada tipe data string. Karena string adalah suatu array dari character, maka

array string adalah array character 2 dimensi. Misalnya, nama-nama hari dalam satu minggu, adalah sekumpulan string. Anggaplah sebuah array Hari, yang berisi 7 buah string yang masing-masing stringnya adalah array dari 6 buah character.

Matriks adalah array dua dimensi dari bilangan real/integer. Baris adalah array 1 dimensi dari bilangan. Matriks adalah array dari baris.

Dalam notasi algoritma, dituliskan deklarasi string dan matriks.tipe string = array[1..6] of character;tipe baris = array[1..N] of float;Hari = array[1..7] of string;Matriks = array[1..N] of baris;

dalam sintaks bahasa C:typedef char string[6];typedef float baris[N];

string Hari[7];baris Matriks[N];

Contoh:

1. Array string

/* 02aryc2s.c: memperkenalkan struktur data array. *//* dengan elemen data array character/string *//* array dua dimensi */


typedef char kata[80];kata n[100];int nmaks;

main(){ int i; clrscr(); puts("penggunaan array string/array karakter 2 dimensi"); puts("================================================"); printf("jumlah kata yang akan diinput:"); scanf("%d",&nmaks);

for (i=0;i<nmaks;i++) { printf("kata ke-%d:",i+1);

scanf("%s",n[i]); } puts(""); printf("string yang anda masukkan: \n"); for (i=0;i<nmaks;i++)

printf("kata ke-%d: %s\n",i+1,n[i]); getch();


9

}

2. Matriks

/* 02aryi2.c: memperkenalkan struktur data array. *//* dengan elemen data integer *//* array dua dimensi/matriks */


typedef int matriks[5][5];

void inputbarkol();void inputdata();void tambahmat();void kurangmat();void lihatmat();

matriks A,B,C;int baris,kolom;

void main(){ int pilih='0';

while(pilih!='6') { clrscr();

puts("penggunaan array integer dua dimensi/matriks"); puts("============================================"); puts("1. memasukkan jumlah baris dan kolom"); puts("2. memasukkan data "); puts("3. menjumlahkan matriks "); puts("4. mengurangkan matriks "); puts("5. melihat data "); puts("6. keluar"); printf("pilihan: "); pilih = getche();

puts(""); switch (pilih) { case '1': inputbarkol(); break;

case '2': inputdata(); break;case '3': tambahmat(); break;case '4': kurangmat(); break;case '5': lihatmat(); break;default : break;

} }}

void inputbarkol(){ printf("jumlah baris (2-80): "); scanf("%d",&baris); printf("jumlah kolom (2-80): "); scanf("%d",&kolom);}

void inputdata()


10

{ int b,k; puts("Matriks A"); for (b=1;b<=baris;b++)

for (k=1;k<=kolom;k++) { printf("baris-%d,kolom-%d: ",b,k);

scanf("%d",&A[b][k]); }

puts("Matriks B"); for (b=1;b<=baris;b++)

for (k=1;k<=kolom;k++) { printf("baris-%d,kolom-%d: ",b,k);

scanf("%d",&B[b][k]); }

}void tambahmat(){ int b,k; for (b=1;b<=baris;b++)

for (k=1;k<=kolom;k++) C[b][k]=A[b][k]+B[b][k];

}

void kurangmat(){ int b,k; for (b=1;b<=baris;b++)

for (k=1;k<=kolom;k++) C[b][k]=A[b][k]-B[b][k];

}void lihatmat(){ int b,k; puts("Matriks A"); for (b=1;b<=baris;b++) { for (k=1;k<=kolom;k++)

printf("%6d",A[b][k]); puts("");

} puts("Matriks B"); for (b=1;b<=baris;b++) { for (k=1;k<=kolom;k++)

printf("%6d",B[b][k]); puts("");

} puts("Matriks C"); for (b=1;b<=baris;b++) { for (k=1;k<=kolom;k++)

printf("%6d",C[b][k]); puts("");

} getch();}


11

III. Record

Materi ke-3

PengertianRecord adalah sekumpulan data yang disebut atribut (kadang disebut juga dengan property), kadang-

kadang dari tipe yang sama, kadang dari tipe yang berbeda. Isi record disebutkan dengan memanggil atribut-atributnya.

Record ini sangat bagus untuk menggambarkan sebuah data yang dapat kita temui dalam kehidupan sehari-hari. Misalnya seorang mahasiswa. Data diri seorang mahasiswa, berupa atribut-atribut, misalnya: NIM, bertipe string. Nama, juga string. Nilai, misalnya bertipe real.

Secara algoritma, data mahasiswa di atas dapat kita deklarasikan sebagai berikut:Type DataMahasiswa = Record { NIM : string, Nama : string, Nilai : real }

Tipe data mahasiswa tersebut dapat dipakai untuk merepresentasikan daftar nilai dari suatu mata kuliah. Misalnya, ada seorang mahasiswa bernama Anto, atau kuliah StrukturData, diikuti oleh 100 orang mahasiswa. Maka StrukturData kita deklarasikan sebagai berikut:

Anto : DataMahasiswaStrukturData = Array [1..100] of DataMahasisiswa

Bagaimana sintaksnya dalam bahasa C?typedef struct DataMahasiswa { char NIM[7]; char Nama[20] float Nilai; };struct DataMahasiswa Anto;struct DataMahasiswa StrukturData[100];

Cara mengambil/mengisi datanya:Anto.NIM = “4198200”;Anto.Nama = “Anto Sumanto”;Anto.Nilai = 100;

Cara lain untuk mengisinya:Anto = {“4198200”,“AntoSumanto”,100};

Untuk array StrukturData:temp = StrukturData[100].Nilai; dsb.

Contoh lain penggunaan record adalah untuk menggambarkan koordinat. Koordinat terdiri atas dua variabel, yaitu x dan y. Secara algoritma, bentuknya sebagai berikut:

Type Koordinat = Record { X: real, Y: real)Misalnya kita punya dua titik di bidang koordinat: A dan B,A,B : Koordinat

Dalam bahasa C:typedef struct Koordinat { float x; float y;};struct Koordinat A,B.

Contoh program.

1. Record untuk menggambarkan Data Mahasiswa

/* 03rec1.c: memperkenalkan struktur data record */#include <stdio.h>#include <conio.h>

typedef struct data {char nama[21];char alamat[30];};

struct data mahasiswa[100];int nmaks;


12

void inputnmaks();void inputdata();void lihatdata();

main(){ int pilih=’0’;

while(pilih!=’4’) { clrscr();

puts("penggunaan struktur data record "); puts("================================="); puts("1. memasukkan jumlah data"); puts("2. memasukkan data "); puts("3. melihat data "); puts("4. keluar"); printf("pilihan: "); pilih = getche();

puts(""); switch (pilih) { case '1': inputnmaks(); break;

case '2': inputdata(); break;case '3': lihatdata(); break;default : break;

} }}

void inputnmaks(){ printf("jumlah data yang akan diinput:"); scanf("%d",&nmaks);}

void inputdata(){ int i; for (i=0;i<nmaks;i++) { printf("data ke-%d:\n",i+1);

printf("Nama : ");scanf("%s",&mahasiswa[i].nama); printf("Alamat : ");scanf("%s",&mahasiswa[i].alamat);

}}

void lihatdata(){ int i; printf("data yang anda masukkan: \n"); for (i=0;i<nmaks;i++) { printf("data ke-%d: \n",i+1);

printf("Nama : %s\n",mahasiswa[i].nama); printf("Alamat : %s\n",mahasiswa[i].alamat);

} getch();}

2. Record untuk menggambarkan koordinat.

/* 03rec2.c: memperkenalkan struktur data record */#include <stdio.h>#include <conio.h>


13

typedef struct koordinat { float X;float Y;};

struct koordinat A,B;

main(){ float m,c;

int pilih; while(1) { clrscr();

puts("penggunaan struktur data record "); puts("untuk membuat persamaan matematik"); puts("================================="); printf("Koordinat A: x= ");scanf("%f",&A.X); printf(" y= ");scanf("%f",&A.Y); printf("Koordinat B: x= ");scanf("%f",&B.X); printf(" y= ");scanf("%f",&B.Y); printf("---------------------------------\n");

m = (B.Y - A.Y)/(B.X-A.X); c = A.Y - m*A.X; printf("persamaan garis yang menghubungkan A dan B: \n"); printf("y = %4.2fx + %4.2f\n",m,c);

printf("mau hitung lagi? <Y/N>"); pilih=getche(); if (pilih=='N'||pilih=='n')

break; }}


14

IV. Buble Sort

Materi ke-4

PengertianSorting, atau pengurutan biasa diterapkan pada isi tipe data array. Misalnya kita punya 100 orang

mahasiswa (dengan tipe data DataMahasiswa di atas), lalu ingin kita urutkan data tersebut sesuai tingginya nilai masing-masing mahasiswa.

Buble Sort adalah salah satu metoda pengurutan yang sederhana. Prinsip kerjanya seperti namanya, (buble berarti gelembung). Misalnya kita punya setumpuk data, mau kita urutkan dari yang paling kecil. Ambil data dari paling bawah, bandingkan dengan atasnya. Kalau data atasnya lebih besar, tukar posisi. Yang kecil naik ke atas. Lihatlah tabel berikut:

Data asli Langkah 1 Langkah 2 Langkah 3 Langkah 4 Langkah 5 Data Urutd d a a a a ac a d d b b b

a c c b d c cb b b c c d d

Contoh

1. Buble Sort untuk tipe array Character/string

/* program 04bubles.c, pengurutan data dengan metode buble sort *//* program akan meminta input data berupa string, *//* dan kemudian mengurutkannya, sesuai dengan urutan abjad. */


void buble(char *item,int count);

main(){ char s[80];

int count;

clrscr();printf("ketikkan sesuatu:\n");gets(s);count = strlen(s);buble(s,count);

printf("string yang telah diurutkan:\n");printf("%s",s);getche();

}

void buble(char *item, int count){ register int a,b,i;

register int t;

for (a=1;a<count;a++)for (b=count-1;b>=a;b--){ if (item[b-1] > item[b]) { t = item[b-1];

item[b-1] = item[b];


15

item[b] = t;for (i=0;i<count;i++)

printf("%5.2f ",item[i]);printf("\n");

}}

2. Buble Sort untuk tipe array Numerik

/* program 04bublen.c, pengurutan data dengan metode buble sort *//* program akan meminta input data berupa bilangan bulat/real *//* dan kemudian mengurutkannya, sesuai dengan urutan menaik */


void buble(float *item,int count);

main(){ float n[80];

int max,i;

clrscr();printf("berapa bilangan akan diurutkan? ");scanf("%d",&max);

for (i=0;i<max;i++){ printf("bilangan ke-%d: ",i);

scanf("%f",&n[i]);}

buble(n,max);

printf("bilangan yang telah diurutkan:\n");for (i=0;i<max;i++)

printf("%5.2f; ",n[i]);

getche();}

void buble(float *item, int count){ register int a,b,i;

register int t;

for (a=1;a<count;a++)for (b=count-1;b>=a;b--){ if (item[b-1] > item[b])

{ t = item[b-1]; item[b-1] = item[b]; item[b] = t; for (i=0;i<count;i++)

printf("%5.2f ",item[i]); printf("\n");}

}}

3. Buble Sort untuk tipe array Record

/* program 04bubler.c, pengurutan data dengan metode buble sort *//* program akan meminta input data berupa string, */


16

/* dan kemudian mengurutkannya, sesuai dengan urutan abjad. */


typedef struct data {char nim[8];nama[21];};

struct data mhsiswa[100];struct data mhsurut[100];

int nmaks;void inputnmaks();void inputdata();void urutdata(int count);void lihatdata(struct data *item);

main(){ int pilih; while(1) { clrscr();

puts("penggunaan struktur data record "); puts("================================="); puts("1. memasukkan jumlah data"); puts("2. memasukkan data "); puts("3. mengurutkan data "); puts("4. melihat data asli "); puts("5. melihat data urut "); puts("6. keluar"); printf("pilihan: "); pilih = getche();


case '2': inputdata(); break;case '3': urutdata(nmaks);break;case '4': lihatdata(mhsiswa); break;case '5': lihatdata(mhsurut); break;default : break;

} if (pilih=='6')

break; }

}



printf("NIM : ");scanf("%s",&mhsiswa[i].nim); printf("Nama : ");scanf("%s",&mhsiswa[i].nama); mhsurut[i] = mhsiswa[i];


17

}}

void urutdata(){ int a,b,i;

struct data t;

for (a=1;a<nmaks;a++){ for(b=nmaks-1;b>=a;b--)

{ if (strcmp(mhsurut[b-1].nim,mhsurut[b].nim)>0){ t = mhsurut[b-1]; mhsurut[b-1] = mhsurut[b]; mhsurut[b] = t; for (i=0;i<nmaks;i++)

printf("%s ",mhsurut[i].nim); printf("\n");

};}

}getch();

}

void lihatdata(struct data *item){ int i; printf("data yang anda masukkan: \n"); for (i=0;i<nmaks;i++) { printf("data ke-%d: \n",i+1);

printf("NIM : %s\n",item[i].nim); printf("Nama : %s\n",item[i].nama);

} getch();}


18

V. Insertion Sort

Materi ke-5

PengertianInsertion Sort adalah contoh lain dari metoda pengurutan yang sederhana. Sebaliknya dari Buble Sort

yang mengurutkan data dari belakang, Insertion Sort mengurutkan data dari depan. Ambil dua data pertama, urutkan sesuai yang diinginkan. Lalu sisipkan data ketiga di tempat semestinya. Lalu sisipkan data keempat di tempat seharusnya di antara 3 data sebelumnya. Demikian terus sampai semua data selesai diurutkan.

Data asli Langkah 1 Langkah 2 Langkah 3 Langkah 4 Langkah 5 Data Urutd c c a a a a

c d a c c b ba a d d b c cb b b b d d d

Contoh

1. Insertion Sort untuk tipe array Character/string

/* program 05insrts.c, pengurutan data dengan metode buble sort *//* program akan meminta input data berupa string, *//* dan kemudian mengurutkannya, sesuai dengan urutan abjad. */


void insertion(char *item,int count);

main(){ char s[80];

int count;

clrscr();printf("ketikkan sesuatu:\n");gets(s);count = strlen(s);

insertion(s,count);

printf("string yang telah diurutkan:\n");printf("%s",s);getche();

}

void insertion(char *item, int count){ register int a,b,i;

register char t;

for (a=1;a<count;a++){ t = item[a];

b = a-1;while (b>=0 && t<item[b]){ item[b+1]=item[b];

b--;}


19

item[b+1]=t;for (i=0;i<count;i++)

printf("%c",item[i]);printf("\n");

}}

2. Insertion Sort untuk tipe array Numerik

/* program 05instrn.c, pengurutan data dg metode insertion sort *//* program akan meminta input data berupa bil bulat/real *//* dan kemudian mengurutkannya, sesuai dg urutan menaik */#include <stdio.h>#include <conio.h>

void insertion(float *item,int count);

main(){ float n[80];

int max,i;

clrscr();printf("berapa bilangan akan diurutkan? ");scanf("%d",&max);

for (i=0;i<max;i++){ printf("bilangan ke-%d: ",i);

scanf("%f",&n[i]);}

insertion(n,max);

printf("bilangan yang telah diurutkan:\n");for (i=0;i<max;i++)

printf("%5.2f; ",n[i]);

getche();}

void insertion(float *item, int count){ register int a,b,i;

register int t;

for (a=1;a<count;a++){ t = item[a];

b = a-1;while (b>=0 && t<item[b]){ item[b+1]=item[b];

b--;}item[b+1]=t;for (i=0;i<count;i++)

printf("%5.2f ",item[i]);printf("\n");

}}

3. Insertion Sort untuk tipe array Record

/* program 05insrtr.c, pengurutan data dg metode insertion sort *//* program akan meminta input data berupa record, */


20

/* dan kemudian mengurutkannya, sesuai dg urutan abjad. */



struct data mhsiswa[100];struct data mhsurut[100];

int nmaks;void inputnmaks();void inputdata();void urutdata(int count);void lihatdata(struct data *item);

main(){ int pilih; while(1) { clrscr();

puts("penggunaan struktur data record "); puts("================================="); puts("1. memasukkan jumlah data"); puts("2. memasukkan data "); puts("3. mengurutkan data "); puts("4. melihat data asli "); puts("5. melihat data urut "); puts("6. keluar"); printf("pilihan: "); pilih = getche();


case '2': inputdata(); break;case '3': urutdata(nmaks);break;case '4': lihatdata(mhsiswa); break;case '5': lihatdata(mhsurut); break;default : break;

} if (pilih=='6')

break; }}

void inputnmaks(){ printf("jumlah data yang akan diinput:");

scanf("%d",&nmaks);}


printf("NIM : ");scanf("%s",&mhsiswa[i].nim); printf("Nama : ");scanf("%s",&mhsiswa[i].nama); mhsurut[i] = mhsiswa[i];

}


21

}

void urutdata(){ int a,b,i;

struct data t;

for (a=1;a<nmaks;a++){ t = mhsurut[a];

b = a-1;while (b>=0 && strcmp(t.nim,mhsurut[b].nim)<0){ mhsurut[b+1]=mhsurut[b];

b--;}mhsurut[b+1]=t;for (i=0;i<nmaks;i++)

printf("%s ",mhsurut[i].nim);printf("\n");

}getch();

}

void lihatdata(struct data *item){ int i; printf("data yang anda masukkan: \n"); for (i=0;i<nmaks;i++) { printf("data ke-%d: \n",i+1);


} getch();}


22

VI. Searching

Materi ke-6

PengertianAlgoritma searcing atau pencarian data dalam array setidaknya dapat dikelompokkan dalam dua

kategori, yaitu pencarian pada data yang belum terurut, dan pencarian pada data yang sudah terurut. Pencarian pada data yang belum terurut, menggunakan Sequential Search. Pada data yang sudah terurut, dapat dilakukan Sequential Search, dan juga Binary Search.

1. Sequential Search

Sequential Search adalah pencarian data dengan cara menelusuri isi array satu per satu, dan membandingkan isinya dengan data yang dicari. Metode ini adalah satu-satunya metode searching yang dapat diterapkan pada data yang belum terurut.

2. Binary Search

Bila data sudah terurut, Binary Search adalah cara yang paling baik untuk melakukan pencarian. Bandingkan data yang dicari dengan data paling tengah dari array. Bila sama, data langsung ketemu. Bila lebih kecil, cari data di antara tengahan data yang bawah, dan bila lebih besar, cari data di antara tengahan data sebelah atas. Demikian terus, sampai data ketemu.

Perhatikan tabel berikut:Kita punya data dari 1 sampai 9. Kita akan mencari angka 4.

1 2 3 4 5 6 7 8 9data paling tengah = 5; 4 lebih kecil dari lima. Kita akan mencari di tengahan data yang bawah

1 2 3 4 5data paling tengah = 3; 4 lebih besar dari 3. Kita akan mencari di tengahan data sebelah atas.

3 4 5data paling tengah = 4; data ketemu.

Contoh

1. Sequential Search

/* program 06seqs.c, pencarian data secara sequensial *//* program akan meminta input data berupa string, *//* dan kemudian mengurutkannya, sesuai dengan urutan abjad. */



struct data mhsiswa[100];

int nmaks;void inputnmaks();void inputdata();int caridata(char *key);void lihatdata(struct data *item);

main(){ int pilih; char key[8]; while(1) { clrscr();


23

puts("penggunaan struktur data record "); puts("================================="); puts("1. memasukkan jumlah data"); puts("2. memasukkan data "); puts("3. mencari data "); puts("4. melihat semua data "); puts("5. keluar"); printf("pilihan: "); pilih = getche();


case '2': inputdata(); break;case '3': printf("NIM yang dicari: ");

scanf("%s",key); caridata(key);break;

case '4': lihatdata(mhsiswa); break;default : break;

} if (pilih=='5')

break; }}


void inputdata(){ int i; for (i=0;i<nmaks;i++) { printf("indeks ke-%d:\n",i);

printf("NIM : ");scanf("%s",&mhsiswa[i].nim); printf("Nama : ");scanf("%s",&mhsiswa[i].nama);

}}

int caridata(char *key){ int a,b,i;

int t=-1;

for (a=0;a<nmaks;a++){ if (strcmp(key,mhsiswa[a].nim)==0)

{ t = a; printf("data ditemukan di indeks ke-%d\n",a); break;}

}if (t==-1) printf("data tidak ditemukan!");getch();return(t);

}

void lihatdata(struct data *item)


24

{ int i; printf("data yang anda masukkan: \n"); for (i=0;i<nmaks;i++) { printf("indeks ke-%d: \n",i);


} getch();}

2. Binary Search

/* program 06bins.c, pencarian data secara Binary Search *//* program akan meminta input data berupa string, *//* dan kemudian mengurutkannya, sesuai dengan urutan abjad. */



struct data mhsiswa[100];

int nmaks;void inputnmaks();void inputdata();void urutdata();int caridata(char *key);void lihatdata(struct data *item);

main(){ int pilih; char key[8]; while(1) { clrscr();

puts("penggunaan struktur data record "); puts("================================="); puts("1. memasukkan jumlah data"); puts("2. memasukkan data "); puts("3. mencari data "); puts("4. melihat semua data "); puts("5. keluar"); printf("pilihan: "); pilih = getche();


case '2': inputdata(); break;case '3': printf("NIM yang dicari: ");

scanf("%s",key); caridata(key);break;

case '4': lihatdata(mhsiswa); break;default : break;

} if (pilih=='5')

break; }}

void inputnmaks()


25

{ printf("jumlah data yang akan diinput:"); scanf("%d",&nmaks);}

void inputdata(){ int i;

for (i=0;i<nmaks;i++) { printf("indeks ke-%d:\n",i);

printf("NIM : ");scanf("%s",mhsiswa[i].nim); printf("Nama : ");scanf("%s",mhsiswa[i].nama);

} urutdata();}void urutdata(){ int a,b,i;

struct data t;

for (a=1;a<nmaks;a++){ t = mhsiswa[a];

b = a-1;while (b>=0 && strcmp(t.nim,mhsiswa[b].nim)<0){ mhsiswa[b+1]=mhsiswa[b];

b--;}mhsiswa[b+1]=t;

}}

int caridata(char *key){ int atas,bawah,tengah;

int t=-1;

bawah = 0; atas = nmaks-1;

while (bawah<=atas){ tengah = (atas+bawah)/2;

if (strcmp(key,mhsiswa[tengah].nim)<0) atas = tengah-1;else if (strcmp(key,mhsiswa[tengah].nim)>0) bawah = tengah+1;else /* (strcmp(key,mhsiswa[tengah].nim)==0) */{ t = tengah; printf("data ditemukan di indeks ke-%d\n",tengah); break;}

}if (t==-1) printf("data tidak ditemukan!");getch();return(t);

}

void lihatdata(struct data *item){ int i; printf("data yang anda masukkan: \n"); for (i=0;i<nmaks;i++) { printf("indeks ke-%d: \n",i);

printf("NIM : %s\n",item[i].nim);


26

printf("Nama : %s\n",item[i].nama); } getch();}


27

VII. Stack

Materi ke-7

PengertianStack (tumpukan) adalah struktur data yang memiliki sifat LIFO (last in first out). Seperti halnya bila

kita menumpukkan sejumlah koin ke dalam wadah, koin yang terakhir kali masuk akan menjadi koin yang pertama keluar, karena letaknya paling atas. Sebaliknya, koin yang masuk pertama kali, akan terletak di tempat paling bawah, sehingga keluar paling akhir.

Perhatikan ilustrasi di bawah ini:indeks Stack

kosongindeks data

masukindeks data

masukindeks data

keluarindeks data

keluarnMax NULL NULL nMax NULL nMax NULL nMax NULL

NULL NULL tos NULL NULL NULLNULL tos NULL 2 tos NULL NULL

tos = bos =

0

NULL bos(0) 1 bos(0) 1 bos(0) 1 tos = bos =

0

NULL

keterangan: nMax: isi stack maksimumbos = bottom of stack (dasar tumpukan)tos = top of stack (puncak tumpukan)NULL = data kosong.

Stack disebut penuh, bila tos > nMax, dan disebut kosong bila tos = bos = 0.Ada dua primitif utama dalam stack, yaitu:1. PUSHPush artinya memasukkan data ke dalam stack. Biasanya PUSH dideklarasikan sebagai berikut:int push(int x); /* tipe parameter tergantung tipe data */

dan algoritma dasar dari push() adalah:if (tos>nMax) then output(“Stack Penuh!”) return (0)else stack(tos) i tos tos + 1; return tosend if

2. POPPop artinya mengeluarkan data dari stack. Deklarasi POP biasanya:int pop(int *x); /*tipe parameter bergantung tipe data */

dan algoritma dasar dari pop() adalah:if (tos=bos) output(“Stack kosong!”) return (0)else tos tos - 1; x = stack(tos) return tosend if

Pada kedua algoritma tersebut, push() dan pop() memberikan nilai kembalian (return value) harga index dari TOS.


28

Contoh

1. Demonstrasi Cara Kerja Stack

/* penggunaan stack untuk menampung integer/real *//* pengenalan function push() dan pop(); *//* stack menggunakan array bilangan real */#include <stdio.h>#include <conio.h>#define MAX 100

typedef float tstack[MAX];

tstack stack;int tos=0;int bos=0;

int push(float i);int pop(float *i);

main(){ int pilih='0'; int i; float n;


puts(" penggunaan stack");puts("-----------------------------------");puts("1. memasukkan bilangan ke stack");puts("2. mengeluarkan bilangan dari stack");puts("3. melihat seluruh isi stack");puts("4. keluar");

pilih = getche();

puts("");

switch(pilih){ case '1':

printf("masukkan satu bilangan: ");scanf("%f",&n); i = push(n); if (i!=-1) { printf("bilangan %5.2f masuk di stack ke-%d\n",n,i-1);

if (tos!=MAX) printf("Top of Stack = %d",i); else

printf("STACK sekarang penuh!\n"); }

getche(); break;

case '2': i = pop(&n);

if (i!=-1) { printf("bilangan yang keluar: %f\n",n); printf("Top of Stack = %d",i); } getche(); break;

case '3': printf("seluruh isi stack: \n");


29

printf("Top of Stack = %d\n",tos); printf("tumpukan"); for(i=tos-1;i>=bos;i--) printf(" ke-%d:%5.2f;",i,stack[i]); puts(""); getche(); break;

default : break;}

}}

int push(float i){ if (tos==MAX) { printf("STACK sudah penuh!\n");

return (-1); } else { stack[tos]= i;

tos++; return(tos);

}}

int pop(float *i){ if (tos==bos) { printf("STACK anda kosong!\n");

return (-1); } else { tos--;

*i = stack[tos]; return(tos);

}

2. Stack untuk Kalkulator PostFix.

/* penggunaan stack untuk meniru kalkulator post-fix *//* stack menggunakan pointer */#include <stdio.h>#include <conio.h>#include <math.h>

float *p;float *tos;float *bos;

int push(float i);float pop();

main(){ float a,b; char s[80];

p = (float *)malloc(sizeof(float)); tos = p; bos = p+(100/sizeof(float)) - sizeof(float);

clrscr(); printf("Kalkulator postfix 4 fungsi.\n");


30

do { printf(": ");

gets(s);

switch(*s) { case '+': a = pop();

b = pop();printf("%f\n",a+b);push(a+b);break;

case '-': a = pop();b = pop();printf("%f\n",b-a);push(b-a);break;

case '*': a = pop();b = pop();printf("%f\n",b*a);push(b*a);break;

case '/': a = pop();b = pop();if(fabs(a)<1E-99){ printf("devided by zero"); break;}printf("%f\n",b/a);push(b/a);break;

default : push(atof(s));break;

} } while (*s!='q');}

int push(float i){ if (p>bos) { printf("STACK full!\n");

return (-1); } *p = i; p++; return(1);}

float pop(){ p--; if (p<tos) { printf("STACK anda kosong!\n");

return (0); } return(*p);}


31

VIII. Pointer dan Singly-Linked List

Materi ke-8.

PengertianAlokasi memori untuk menyimpan data dalam komputer terbagi dua, yaitu alokasi statis, dan alokasi

dinamis. Contoh alokasi statis adalah array, dan alokasi dinamis adalah pointer.Maksud dari alokasi statis adalah: program memesan sejumlah memori tertentu yang akan diisi data

pada saat running time. Memori yang sudah dipesan itu tidak dapat ditempati oleh data dari program lain, bahkan data lain dari program yang sama. Kalau kita memesan array integer sejumlah 10000, maka komputer akan mengalokasikan memori sebanyak 10000 * 2 byte = 20000 byte. (+ 20 KB. 2 byte (=16 bit) adalah ukuran satu bilangan integer dalam memori). Memori sebanyak itu akan terpasang, dan tidak akan dapat dipakai data lain, meskipun array yang kita gunakan hanya berisi 10 buah integer, bahkan jika array tersebut kosong (tidak ada datanya).

Jika kita memiliki sebuah struktur data record sebagai berikut:typedef struct mhs1 { char nim[7]; char nama[20]; float nilai;};struct mhs1 SD[1000];

maka untuk tiap data mhs1 komputer akan mengalokasikan 31 byte memori, dan dan untuk seluruh isi array SD, akan membutuhkan 3100 byte, entah arraynya kosong, berisi sedikit, atau penuh. Bayangkan jika datanya ada puluhan ribu, dan array yang diproses ada puluhan buah (misalnya seperti tabel spreadsheet pada MS Excel). Akan sangat banyak memori yang terboroskan, meskipun belum digunakan.

Untuk mengatasi hal itu, maka dikenalkan tipe data pointer.

1. Pointer

Pointer adalah tipe data dengan alokasi dinamis. Maksudnya, jumlah memori yang dipakai oleh struktur data yang menggunakan pointer akan berbanding lurus dengan jumlah data yang diproses. Misalnya pada singly-linked list (senarai berantai tunggal) yang akan kita bahas nanti, jumlah memori yang dipakai bila list kosong hanya sebesar satu atau dua kali ukuran data ybs, tergantung jumlah penanda list yang dipakai.

Misalnya kita mempunya struktur data sbb:typedef struct mhs2 { char nim[7]; char nama[20]; float nilai; struct mhs2 *next;}¦struct mhs2 *first;struct mhs2 *last;

maka untuk setiap mhs2 komputer akan mengalokasikan 33 byte. Jika list kosong, komputer hanya akan memberikan alokasi 2 bit untuk *first dan 2 bit untuk last. Jika hanya ada satu anggota list, maka memori yang dipakai adalah 2+33+2 = 34 byte. Jika list berisi N buah anggota, maka yang diperlukan adalah 2 + 33*N + 2 = 33N+4.

Dapat disimpulkan, penggunaan list jauh lebih efektif daripada penggunaan array, terutama untuk data-data yang jumlahnya belum tentu banyak, tapi mungkin sekali menjadi amat banyak.

2. Singly-Linked List

Bagaimana cara kerja pointer dan list?Perhatikan ilustrasi berikut:

info info info info info info info infonext next next next next next next NULL

link *first *last

alamat di memori

DS:2000

DS:2F00

DS:2030

DS:2E00

DS:2E30

DS:2F30

DS:2D00

DS:1FE0


32

Singly-Linked List ditandai dengan adanya pointer FIRST yang menunjukkan lokasi memori dari elemen pertama list. Di setiap anggota list, ada pointer NEXT yang menunjukkan lokasi elemen berikutnya di memori. Pada elemen terakhir, pointer NEXT ini bernilai NULL, artinya, dia tidak menunjuk lokasi lain lagi, sebab dia adalah elemen terakhir. Biasanya elemen terakhir ditandani dengan pointer LAST. Beberapa programer tidak meggunakan pointer LAST, karena elemen terakhir dapat ditemukan apabila kita menelusuri list dari elemen pertamanya (FIRST). Namun cara ini kurang efektif, sebab jika data yang dimiliki amat banyak, maka terlalu repot apabila harus menelusuri seluruh elemen list satu per satu sampai akhir.

Di praktikum ini, diajarkan singly linked list dengan menggunakan pointer FIRST dan LAST.Notasi algoritmik dari pointer adalah tanda panah ke atas (). Sedangkan dalam bahasa C, pointer

dinotasikan dengan tanda bintang (*) dibelakang nama variabel.Ada beberapa primitif dari struktur data list.1. NewNode(p)mengalokasikan memori untuk ditempati data.NewNode(input/output p: mhs2): fuction->mhs2 allocate(size of p) if p = NULL then return(NULL) p->next NULL; return p

2. deallocate(p)membebaskan/mengembalikan memori kepada sistemdeallocate(p);

3. insertfirst(i)algoritma dasar dari insert (i) if (first=NULL) then /* jika list kosong, dimasukkan sbg */ first i /* pertama dan juga terakhir */ last i else i->next first

first i end if

4. insertlast(i) if (first=NULL) then /* jika list kosong, dimasukkan sbg */ first i /* pertama dan juga terakhir */

last i else last->next i

i->next NULLlast i

end ifPada contoh program dibawah ini, insert yang dipakai selalu insert last.5. delete(i)deklarasi p : data prev: dataalgoritma p first; prev first while(1) if i=first then /* menghapus elemen pertama */ first i->next free(p)

exit while else prev p

p p->next if p=i then prev->next p->next

if p=last then lastprev /* menghapus elemen terakhir */


33

free(p)exit while

end if end if

end while

Contoh

1. Pointer untuk menerapkan Singly-Linked List.

/* 08list1.c: memperkenalkan pointer *//* untuk singly linked list */


typedef struct data { char NIM[8];char nama[21];struct data *next;

} mhsiswa;

struct data *first=0; /* untuk mencatat address pertama list */struct data *last=0; /* untuk mencatat address terakhir list */

int nmaks;void inputdata();void hapusdata();void lihatdata();void caridata();void tampil(struct data *top);void simpan(struct data *i);void hapus(struct data *i);struct data *cari(char *name);

main(){ int pilih='0';


puts("penggunaan pointer pada singly-linked list "); puts("============================================"); puts("1. memasukkan data"); puts("2. mencari data"); puts("3. menghapus data"); puts("4. melihat data"); puts("5. keluar"); printf("pilihan: "); pilih = getche();

puts(""); switch (pilih) { case '1': inputdata(); break;

case '2': caridata(); break;case '3': hapusdata(); break;case '4': lihatdata(); break;default : break;

} }}


34

void inputdata(){ struct data *t;

printf("Memasukkan Data\n"); while(1) { t = (struct data*)malloc(sizeof(struct data));

if (t==0) printf("out of memori!"); else { printf("NIM : ");gets(t->NIM);

if (!t->NIM[0]) break;printf("Nama : ");gets(t->nama);simpan(t);

} }}

void simpan(struct data *i){ if (first==NULL) { first = i;

last = i; } else { last->next = i;

i->next = 0; last = i;

}}

void lihatdata(){ printf("Menampilkan Data\n"); tampil(first); getch();}

void caridata(){ char n[8]; struct data *t;

printf("Mencari Data\n"); printf("NIM : ");gets(n); if (!n[0])

return; t = cari(n); if (t) { printf("NIM : %s\n",t->NIM);

printf("Nama : %s\n",t->nama); } getch();}

void tampil(){ struct data *top = first;

while (top) { printf("NIM : %s\n",top->NIM);

printf("Nama : %s\n",top->nama); top = top->next;

}}


35

void hapusdata(){ char n[8]; struct data *t;

printf("Menghapus Data\n"); printf("NIM : ");gets(n); if (!n[0])

return; t = cari(n);

if (t) { hapus(t);

printf("Data %s telah dihapus!\n",n); }

getch();}

struct data *cari(char *n){ struct data *top=first; while (top) { if (strcmp(n,top->NIM)==0) return(top);

top = top->next; } printf("Data tidak ditemukan"); return(0);}

void hapus(struct data *i){ struct data *p=first; struct data *prev=first;

while(1) { if (i==first)

{ first = i->next;break;

} else { prev = p;

p = p->next;if (p==i){ prev->next = p->next;

if (p==last) last = prev;free(p);break;

} }

}}


36

IX. Doubly-Linked List

Materi ke-9

PengertianDoubly-Linked List pada dasarnya sama dengan singly-linked list. Bedanya, pada setiap data singly-

linked list hanya terdapat satu pounter NEXT, sedangkan pada doubly-linked list terdapat satu lagi pointer PREV. Pointer NEXT untuk menunjukkan lokasi memory elemen berikutnya, dan pointer PREV untuk menunjukkan lokasi memori dari elemen sebelumnya.

Perhatikan ilustrasi berikut:

infoinfo

infoinfo

infoinfo

infoinfo

NULL next prev next prev next prev NULLlink

*first *lastalamat di memori

DS: 2000 DS: 2030 DS: 2E30 DS: 2D00

Penggunaan memori pada doubly-linked list sama saja dengan penggunaan memori pada single-linked list. Dan pada double linked list ini, pointer FIRST dan pointer LAST selalu digunakan bersama sama.

Misalnya, pada struktur data record mhs2 diatas:typedef struct mhs2 { char nim[7]; char nama[20]; float nilai; struct mhs2 *prev; struct mhs2 *next;}¦struct mhs2 *first;struct mhs2 *last;

Primitif dari struktur doubly linked list mirip dengan singly linked list..1. NewNode(p)mengalokasikan memori untuk ditempati data.NewNode(input p: mhs2): function -> mhs2algoritma allocate(size of p) if p=NULL then return 0 p->prev NULL p->prev NULL return (p)

2. deallocate(p)membebaskan/mengembalikan memori kepada sistemdeallocate(p);

3. insertfirst(i)memasukkan data di urutan terdepan dari listInsertFirst(input/output i: mhs2): function -> mhs2algoritma if (first=NULL) then /* jika list kosong, dimasukkan sbg */ first i /* pertama dan juga terakhir */ last i else i->next first i->prev NULL

first->prev i first i


37

end if4 insertlast(i)Memasukkan data di posisi paling belakangInsertLast(input/output i: mhs2): function -> mhs2algoritma if (first=NULL) then /* jika list kosong, dimasukkan sbg */ first i /* pertama dan juga terakhir */

last i else last->next i i->prev last

i->next NULLlast i

end if5. delete(i)Menghapus data dari listDeleteList(input/output i: mhs2): function -> mhs2deklarasi p : dataalgoritma p first while(1) if i=first then /* menghapus elemen pertama */ i->next->prev = NULL first = i->next free(p)

exit while else p p->next if p=i p->prev->next p->next

p->next->prev p->previf p=last then

last p->prev /* menghapus elemen terakhir */ last->next NULL end if free(p)

exit while end if end if

end while

Studi Kasus

1. Pointer untuk menerapkan Doubly-Linked List

Gunakan algoritma-algoritma primitif pada doubly-linked list, untuk diterapkan pada program singly-linked list yang lalu.


38

X. Antrian

Materi ke-10

PengertianAntrian, disebut juga sebagai queu. Sebagaimana stack, antrian terdiri dari elemen-elemen yang

menempati suatu array atau list, dan dapat dimasukkan atau dikeluarkan dengan cara tertentu. Bila pada stackelemen yang pertama keluar adalah elemen yang terakhir masuk, maka pada queu elemen yang pertama keluar adalah elemen yang pertama kali masuk. Maka dikatakan queu bersifat FIFO (first in first out).

Banyak sekali contoh antrian yang dapat kita temukan di dunia nyata. Antrian orang yang akan mengambil uang di bank, antrian pendaftaran mahasiswa, antrian di lampu lalu lintas, antrian pesawat yang akan landing atau take off, dsb.

Struktur data antrian dapat menggunakan array, dan dapat juga menggunakan doubly-link list. Misalnya pada antrian pengambilan uang di bank. Maka struktur data antrian dengan array adalah:

type dtNasabah = record { NomorRekening : string[14], Nama : string[20], JumlahUang : real }

Antrian = array [1..nMax] of dtNasabahawal : integer;akhir : integer;

Dengan struktur data list, misalnya:type dtNasabah = record { NomorRekening : string[14],

Nama : string[20], JumlahUang : real, prev : dtNasabah, next : dtNasabah}

type Antrian = record{ awal : dtNasabah, akhir : dtNasabah}

BankNiaga : Antrian

Pada prinsipnya ada beberapa primitif dalam antrian. Di sini diberikan antrian dalam struktur list.1. BuildQueu(input/output Q: Antrian)algoritma

Q.awal NULLQ.akhir NULL

2. InsertItem(input/output i: dtNasabah, input/output Q: Antrian)algoritma

Q.akhir->next ii->prev Q.akhirQ.akhir i

3. AmbilItem(input/output i: dtNasabah, input/output Q: Antrian)deklarasi p,t : dtNasabahalgoritma if (Q.awal=NULL) and (Q.akhir=NULL) then output(“Tidak ada nasabah yang perlu dilayani”)

i NULL else

t Q.awal; p Q.awal->next p->prev NULL ; Q.awal p

i pdeallocate(t)


39

end if

Studi Kasus

1. Mensimulasikan Antrean Pengambilan Uang.

Buatlah program dengan bahasa C untuk mensimulasikan antrian pengambilan uang, dengan struktur data pointer seperti di atas, dari algoritma berikut:

Program AntrianPengambilanUangdesklarasi { lihat di atas} pilihan : integer; TampilkanMenu(): procedure; TambahkanNasabah(input/output Q:Antrian): procedure; LayaniNasabah(input/output Q:Antrian): procedure; HitungNasabah(input/output Q:Antrian): procedure;

algoritma while(1) BuildQueu(BankNiaga) TampilkanMenu() input(pilihan) case pilihan of:

1: TambahkanNasabah(BankNiaga)2: LayaniNasabah(BankNiaga)3: HitungNasabahYangTersisa(BankNiaga)4: exit while

end case end while

TambahkanNasabah(input/output Q:Antrian): procedure;deklarasi t: dtNasabahalgoritma t allocate(size of t) if t = 0 then output(“Memori tidak mencukupi”) else

input(t) InsertItem(t,Q) end if

LayaniNasabah(input/output Q:Antrian): procedure;deklarasi t: dtNasabahalgoritma AmbilItem(t,Q); if t<>NULL then output(“Telah melayani Nasabah”,t) end if

HitungNasabah(input Q:Antrian): function integer;deklarasi i: integer t: dtNasabahalgoritma if (Q.awal=NULL) and (Q.akhir=NULL) then output(“Tidak ada nasabah yang perlu dilayani”) return (0)


40

elsei 0

t Q.awalwhile (t->next)

i i + 1t t->next

end while return(i) end if


41

XI. Binary-Tree

Materi ke-11

PengertianStruktur TREE atau pohon adalah salah satu bentuk Multiply-Linked List (Linked List dengan pointer

lebih dari satu). Elemen pada tree disebut dengan nama simpul (node). Simpul utama disebut root (akar). Setiap node dapat memiliki anak satu atau lebih. Node yang tidak mempunyai anak disebut leaf (daun).

Struktur pohon yang amat kita kenal misalnya: bagan organisasi, skema garis keluarga dari kakek buyut sampai cicit, struktur direktori di hardisk, dsb.

Pada umumnya TREE dapat digambarkan sebagai berikut:root

A

B C

D E F G H

I J K L M N O P

Yang dimaksud dengan Binary-Tree adalah suatu pohon yang simpul-simpulnya memiliki anak maksimum 2 buah.

root

A

B C

D E G H

I J K N O P

Pada praktikum ini hanya akan dibahas Binary-Tree. Struktur data dasar dari Binary Tree adalah:type tree = record { info : integer; kiri : tree; kanan: tree; }t : tree;root : tree;

Studi KasusKonversikan algoritma-algoritma primitif berikut ini menjadi sintaks bahasa C, dan kembangkan

menjadi sebuah program yang meliputi seluruh fungsi-fungsi primitif tersebut. (Lihatlah contoh program pada materi Record, yaitu record untuk merepresentasikan Data Mahasiswa.


42

1. Binary-Tree Generating

Pembentukan Binary TreeBuildTree(input/output r: tree): procedure;algoritma r NULL

2. Inserting Binary-Tree

Memasukkan data ke dalam binary treeInsertTree(input/output root: tree, input/output r: tree, input info : integer): function treealgoritma if r=NULL then

r allocate(size of t)if r=0 then output(“memory tidak mencukupi”)

return(0)end ifr->kiri 0r->kanan 0r->info infoif (root<>0) then

if (info<root->info) then root->kiri r else root->kanan r

end if else

r->kanan NULL r->kiri NULLend ifreturn(r)

end if if (info<=r->info) InsertTree(r,r->kiri,info) if (info>r->info) InsertTree(r,r->kanan,info)

3. Binary-Tree Traversal

Penelusudan pohon biner dapat dilakukan dengan 3 cara sebagai berikut:

a. In-Order

InOrder(input root: tree): procedurealgoritma if (root=NULL) then return InOrder(root->kiri) output(root->info) InOrder(root->kanan)

b. Pre-Order

PreOrder(input root: tree): procedurealgoritma if (root=NULL) then return output(root->info) PreOrder(root->kiri) PreOrder(root->kanan)

c. Post-Order

InOrder(input root: tree): procedurealgoritma if (root=NULL) then return


43

PostOrder(root->kiri) PostOrder(root->kanan) output(root->info)

4. Searching Tree

Mencari data dalam binary treeSearchTree(input root: tree, input key: integer): function->treealgoritma if (root=NULL) then return(root) while (root->info <> key)

if (key < root->info) rootroot->kiri else rootroot->kanan

if root=NULL then exit while end while return(root)

5. Deleting Node

Menghapus simpul dari suatu pohonDeleteTree(input/output root: tree, key: integer): function-> treedeklarasi p1, p2 : treealgoritma if (root->info = key) then

if (root->kiri=root->kanan) free(root)

return(0)end if

else if root->left=0 p1 root->kanan

free(root) return(p1)

else if root->right=0 p1 root->kiri

free(root) return(p1) else

p2 root->kananp1 root->kananwhile (p1->kiri<>0)

p1-kiri root->kiriend whilep1->kiri = root->kirifree(root)return(p2)

end ifif (root->info<key) then root->kanan = DeleteTree(root->kanan,key)else root->kiri = DeleteTree(root->kiri,key)return (root)


44

Referensi1. Advanced C, Herbert Schild2. Data Structures and Logic Design, ...3. Modul Praktikum Struktur Data Teknik Infomatika STMIK PMBI 20014. Diktat Kuliah Algoritma dan Pemrograman Teknik Informatika ITB (th. ..., Inggriani Liem)5. Materi Perkuliahan Struktur Data tahun 2000 (Suryanudin)6. Materi Perkuliahan Algoritma 2 tahun 2001 (Suryanudin)6. Materi Struktur Data 2003 (Ali Ahmadi)

Documents

Modul Praktikum Struktur Data DNBS 2009