Lapres Struktur Data

BAB I

PENDAHULUAN

1.1  Latar Belakang

Perkembangan teknologi komputer telah membuat ruang batas perangkat lunak dan perangkat keras semakin sempit. Komputer sebagai sistem tidak dapat dipahami tanpa memahami kedua aspek tersebut. Kalau dalam dekade sebelumnya, rangkaian logika digital dianggap perlu dipahami hanya oleh orang-orang yang bekerja dalam bidang perangkat keras komputer, kini disadari bahwa pemahaman rangkaian logika digital juga merupakan keharusan bagi orang-orang yang bekerja dalam bidang perangkat lunak atau program komputer.

1.2     Tujuan

Dengan di buatnya Laporan Resmi Struktur Data, mahasiswa dapat memahami struktur data dan fungsi masing-masing pembentuk struktur serta mengetahui berbagai arsitektur perancangan sistem komputer untuk mencapai kinerja yang tinggi.

BAB II

TINJAUAN PUSTAKA

2.1 Fungsi dan Penggunaan Elmen-Elemen C++

Ø Statement Output

Untuk menampilkan informasi pada standard output (normalnya berupa layar) dapat digabungkan dengan penggunaan Escape Sequence Character beberapa perintah output yang bisa digunakan:

Ø printf

-          fungsi output yang paling umum digunakan.

-          terdapat dalam file header : stdio.h

-          sintaks:

printf(“Format”, arg1, arg2, …);

keterangan:

format berupa keterangan yang akan ditampilkan ke layar beserta penentu formatnya.

penentu format digunakan untuk menentukan jenis data apa yang akan ditampilkan ke layar.

argumen dapat berupa variabel, konstanta, atau ekspresi.

Ø puts

-          Digunakan untuk mencetak string ke layar.

-          pencetakan akan diakhiri dengan karakter newline (ke baris baru).

-          terdapat dalam file header : stdio.h

-          sintaks:

puts(<string yg ditampilkan>);

Ø putchar

-          menampilkan sebuah karakter ke layar.

-          pencetakan karakter tidak diakhiri dengan karakter new line.

-          terdapat dalam file header : stdio.h

-          sintaks:

putchar(<kar>);

Ø cout

-          merupakan suatu object di dalam C++ yang digunakan untuk menampilkan data ke layar.

-          terdapat pada file header : iostream.h

-          dapat digabungkan dengan penggunaan escape sequence character.

-          contoh:

cout << “Hello World” << endl;

cout << “Pilihan Anda Salah\a\n”;

Ø cprintf

-          memiliki fungsi yang mirip dengan printf.

-          dapat menampilkan tulisan dengan warna.

-          terdapat dalam file header : stdio.h

-          sintaks:

cprintf(“<format>”, arg1, arg2, …);

Ø Statement Input

untuk menerima masukan dari user beberapa fungsi input yang dapat digunakan:

·         scanf

o   digunakan untuk memasukkan berbagai jenis data.

o   terdapat dalam file header : stdio.h

o   sintaks:

scanf(“<format>”, &variabel);

keterangan:

simbol & merupakan pointer yang digunakan untuk menunjuk ke alamat variabel memori yang dituju.

·         gets

o   digunakan untuk memasukkan data string.

o   sintaks:

gets(nama-variabel-array);

·         cin

o   merupakan sebuah object di dalam C++ yang digunakan untuk memasukkan data.

o   terdapat dalam header file : iostream.h

o   sintaks:

cin >> <var>;

o   Catatan!

Untuk mendapatkan sebuah inputan data yang mengandung spasi, anda bisa menggunakan cin.getline(<var>, sizeof(<var>))

·         getch

o   digunakan untuk membaca sebuah karakter dengan sifat karakter yang dimasukkan tidak perlu diakhiri dengan menekan tombol Enter, dan karakter yang dimasukkan tidak akan ditampilkan ke layar.

o   terdapat dalam header file : conio.h

·         getche

o   digunakan untuk membaca sebuah karakter dengan sifat karakter yang dimasukkan tidak perlu diakhiri dengan menekan tombol Enter, dan karakter yang dimasukkan akan ditampilkan ke layar.

o   terdapat dalam header file : conio.h

2.2 Stack

Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In FirstOut), benda yang terakhir masuk dalam stack akan menjadi benda pertama yangdikeluarkan dari stack.

2.3 Queue

Jika diartikan secara harafiah, queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat Anda mengantri di loket untuk membeli tiket.

Istilah yang cukup sering dipakai seseorang masuk dalam sebuah antrian adalah enqueue. Dalam suatu antrian, yang dating terlebih dahulu akan dilayani lebih dahulu.Istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.

2.4  Linked List

Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung-menyambung, dinamis dan terbatas.Linked List sering disebut juga Senarai Berantai.Linked List saling terhubung dengan bantuan variabel pointer.

Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.

2.5  Tree

Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon.Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah.Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.

2.6  Search and Sort

Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching.Searching adalah pencarian data dengan cara menelusuri data-data tersebut.Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage.

Sorting merupakan suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.

2.7 Rekursif

Rekursif adalah salah satu metode dalam dunia matematika dimana definisi sebuah fungsi mengandung fungsi itu sendiri. Dalam dunia pemrograman,rekursi diimplementasikan dalam sebuah fungsi yang memanggil dirinya sendiri.

2.8  Hash Table

Struktur data yang mengasosiasikan sebuah kunci (key) dengan sebuah nilai (value).Key biasanya adalah sebuah string,sedangkan nilai bisa apa saja(integer,string,dll) Memunginkan akses rata-rata 0(1) dengan worst case 0(n) Prinsipnya key diubah menjadi nilai integer yang menjadi indeks table.

BAB III

FUNGSI DAN PENGGUNAAN ELEMEN-ELEMEN C++

3.1  Mengenal fungsi dan penggunaan elemen-elemen C++

C++ diciptakan untuk mendukung pemrograman berorientasi pada objek (Object Oriented Pragramming/OOP) yang tidak dimiliki C. sementara C merupakan bahasa pemrograman terbaik dilingkungannya, bahasa ini tidak memiliki kemampuan OOP. Reputasi C tidak diragukan lagi dalam menghasilkan program. EXE berukuran kecil, eksekusi yang cepat, antarmuka (interfacing) yang sederhana dengan bahasa lain dan fleksibilitas pemrograman.

Element dasar C++

1. Komentar

Digunakan untuk memberikan penjelasan mengenai program atau bagian – bagian program.

      Bisa berupa:

-          Tujuan / fungsi program

-          Informasi waktu program dibuat / direvisi

-          Keterangan mengenai kegunaan sejumlah pernyataan /statement dalam program.

Sintaks:

/* komentar

    banyak baris */

// komentar dalam satu baris

2.  Identifier

      Nama pengenal (identifier) adalah nama-nama yang ditentukan sendiri oleh pembuat program (programmer) untuk memberikan nama pada variabel, konstanta,fungsi atau label.

Ketentuan pemberian nama pada identifier sbb:

1. Diawali dengan huruf atau garis bawah

2. Selanjutnya bisa diikuti oleh huruf atau garis bawah atau angka.

3. Panjang maksimum 32 karakter (ANSI)

4. Membedakan HURUF BESAR dengan huruf kecil (Case Sensitive).

5. Tidak boleh sama dengan kata kunci (keyword).

3. Variabel

Identifier yang digunakan untuk menampung data /informasi

Format deklarasi variabel: <tipe> <nama_variabel>;

<tipe> <nama_variabel> = <initial_value>;

Contoh:

int a, b, c;

int _1x = 20;

float Panjang, Lebar;

float FLOAT;

double Luas_Segitiga;

char Nama_Mahasiswa=“Ali Baba”;

4. Tipe Data Dasar

Data merupakan suatu nilai yang bisa dinyatakan dalam bentuk konstanta atau variabel. Konstanta menyatakan nilai yang tetap, sedangkan variabel menyatakan nilai yang dapat diubah-ubah selama eksekusi berlangsung, Data berdasarkan jenisnya dapat dibagi menjadi lima kelompok, yang dinamakan sebagai tipe data dasar. Kelima tipe data dasar adalah :

1.   Bilangan bulat (integer)

2.   Bilangan real presisi-tunggal

3.   Bilangan real presisi-ganda

4.   Karakter

5.   Tak-bertipe (void)

5 . Konstanta

          Konstanta menyatakan nilai yang tetap. Berbeda dengan variabel, suatu konstanta tidak dideklarasikan. Namun seperti halnya variabel, konstanta juga memiliki tipe. Penulisan konstanta mempunyai aturan tersendiri, sesuai dengan tipe masing-masing.

§  Konstanta karakter misalnya ditulis dengan diawali dan diakhiri dengan tanda petik tunggal, contohnya : ‘A’ dan ‘@’.

§  Konstanta integer ditulis dengan tanda mengandung pemisah ribuan dan tak mengandung bagian pecahan, contohnya : –1 dan 32767.

§  Konstanta real (float dan double) bisa mengandung pecahan (dengan tanda berupa titik) dan nilainya bisa ditulis dalam bentuk eksponensial (menggunakan tanda e), contohnya : 27.5f (untuk tipe float) atau 27.5 (untuk tipe double) dan 2.1e+5 (maksudnya 2,1 x 10⁵ ).

§  Konstanta string merupakan deretan karakter yang diawali dan diakhiri dengan tanda petik-ganda (“), contohnya :“Pemrograman Dasar C”.

6. Operator

        Operator merupakan simbol atau karakter yang biasa dilibatkan dalam program untuk melakukan sesuatu operasi atau manipulasi, seperti menjumlahkan dua buah nilai, memberikan nilai ke suatu variabel, membandingkan kesamaan dua buah nilai.  Sebagian operator C tergolong sebagai operator binary, yaitu operator yang dikenakan terhadap dua buah nilai (operand).

a. Operator Aritmatika

§  Operator untuk operasi aritmatika yang tergolong sebagai operator binary

*          perkalian

/           pembagian

%         sisa pembagian

+          penjumlahan

-           pengurangan

§  Adapun operator yang tergolong sebagai operator unary.

      -           tanda minus

      +          tanda plus

b.  Operator Penurunan dan Penaikan

       Masih berkaitan dengan operasi aritmatika, C menyediakan operator yang disebut sebagai operator penaikan dan operator penurunan, yaitu :

++     operator penaikan

--  operator penurunan

c. Operator Penugasan

Operator penugasan (assignment operator) digunakan untuk memindahkan nilai dari suatu ungkapan (expression) ke suatu pengenal. Operator pengerjaan yang umum digunakan dalam bahasa pemrograman, termasuk bahasa C adalah operator sama dengan (=).  Contohnya :

     fahrenheit = celcius * 1.8 + 32;

Maka ‘=’ adalah operator penugasan yang akan memberikan nilai dari ungkapan : celcius * 1.8 + 32 kepada variabel fahrenheit.

d. Operator Kombinasi (Pemendekan)

       C menyediakan operator yang dimaksudkan untuk memendekkan penulisan operasi penugasan semacam

	x +=  2; y *=  4;

 

       x = x + 2;

       y = y * 4;

Statement Output dan Input

a. Statement Output

         Statement output digunakan untuk menampilkan informasi pada standard output (normalnya berupa layar).

1.   printf

fungsi output yang paling umum digunakan. terdapat dalam file header : stdio.h

sintaks:

printf(“Format”, arg1, arg2, …);

keterangan:

format berupa keterangan yang akan ditampilkan ke layar beserta penentu formatnya. penentu format digunakan untuk menentukan jenis data apa yang akan ditampilkan ke layar. argumen dapat berupa variabel, konstanta, atau ekspresi.

2.   puts

digunakan untuk mencetak string ke layar. pencetakan akan diakhiri dengan karakter newline (ke baris baru). terdapat dalam file header : stdio.h

sintaks:

puts(<string yg ditampilkan>);

3.   putchar

menampilkan sebuah karakter ke layar. pencetakan karakter tidak diakhiri dengan karakter new line. terdapat dalam file header : stdio.h

sintaks: putchar(<kar>);

4.   cprintf

memiliki fungsi yang mirip dengan printf. dapat menampilkan tulisan dengan warna. terdapat dalam file header : stdio.h

sintaks:

cprintf(“<format>”, arg1, arg2, …);

5.   cout

merupakan suatu object di dalam C++ yang digunakan untuk menampilkan data ke layar. terdapat pada file header : iostream.h

dapat digabungkan dengan penggunaan escape sequence character.

contoh:

cout << “Hello World” << endl;

cout << “Pilihan Anda Salah\a\n”;

6.   Fungsi Manipulator

digunakan untuk mengatur tampilan data.

terdapat dalam file header : iomanip.h

1. Beberapa istilah dalam penggunaan elemen-elemen C++ dan berikut beserta artinya,

a. Software : suatu system yang menghubungkan suatu computer(Hardware) dengan User(pengguna) agar dapat tercipta suatu system yang dapat berfungsi sesuai kemauan User

b. Algoritma : urutan logis pengambilan putusan untuk pemecahan masalah

c. Program :  kumpulan instruksi atau perintah yang disusun sedemikian rupa         sehingga mempunyai urutan nalar yang tepat untuk menyelesaikan suatu masalah.

d. Bahasa pemrograman : suatu himpunan dari aturan sintaks dan semantik yang dipakai untuk mendefinisikan program komputer

e. Flowchart    : serangkaian bagan-bagan yang menggambarkan alir program.

f. Deklarasi      :menyadiakan suatu tempat yang dapat digunakan untukmenyimpan  angka yang akan digunakan dalam suatu perhitungan

g. Inisialisasi :proses awal yang dilakukan untuk menyimpan indeks penunjuk stack

h. identifier     :nama dalam pemrograman

i.                    Case Sensitive : penulisan menggunakan huruf besar ataupun huruf kecil pada kode program dapat berarti lain

j. Variabel           :suatu tempat untuk menampung data atau konstanta di memori   yang mempunyai nilai atau data yang dapat berubah – ubah selama proses program

k. Dalam pemrograman pascal, semua peubah yang akan dipakai harus ditentukan tipe data yang digunakan karena akan berpengaruh terhadap operasi bilangan yang dapat dilaksanakan serta hasil akhir dari sebuah operasi bilangan

l. File Header   : suatu file dengan akhiran .h

m. Keyword   : kata-kata yang tidak boleh digunakan sebagai nama variabel, fungsi, prosedur, konstan dan lainnya, karena kata tersebut merupakan kata-kata yang telah dipesan oleh bahasa tersebut untuk melakukan perintah-perintah dasar

n. Operator         : suatu tanda atau simbol yang biasa dilibatkan dalam program untuk melakukan suatu operasi atau manipulasi 

o. Operand         : molekul bahasa pemrograman, yang merupakan kesatuan terkecil dan hampir tak dapat dipisahkan

p. Ukuran memori : Jumlah alamat memori yang dapat dialamati oleh mikroprosesor secara langsung

3.2 Kegunaan Cout dan Cin

 Cout adalah sebuah object dari Pustaka perangkat lunak standart C++ yang digunakan untuk mencetak string ke piranti output standart, yang biasanya adalah layer computer.

 Cin adalah untuk penginputan

3.3 Fungsi Main

Program c++ harus menggandung nilai “main ()” karena beberapa hal sebagai   berikut :

            Program c++ merupakan program yang berbentuk fungsi-fungsi.Main() merupakan nama dari suatu fungsi yang harus ada di program c++ dan diletakkan di bagian tertentu yang menunjukkan compiler di mana awal dari suatu program.Selain itu main() ini hanya dapat digunakan sekali saja dalam suatu program.Dapat juga di katakan bahwa setiap program c harus mengandung fungsi main() agar dapat diproses.Tanda brance pembuka "{" yang di letakkan di bawah nama fungsi main () menunjukkan tanda awal dari perintah-perintah yang akan di tulis atau tanda "{" merupakan awal dari function body atau fungsi block.Tanda brance penutup "}" menunjukkan akhir dari suatu fungsi blog.Suatu program C++ dapat terdiri lebih dari satu tubuh fungsi.Pada program sederhana di atas hanya terdiri dari sebuah tubuh fungsi.Suatu tubuh fungsi dapat berisi beberapa fungsi,sedangkan suatu fungsi dapat dibuat dari satu atau lebih statement atau library function(Fungsi pustaka) yang sudah tersedia.Pada contoh program di atas,perintah printf adalah fungsi pustaka yang di pergunakan untuk menampilkan hasil sedangkan /n untuk menampilkan hasil di bawah atau enter.

3.4  Kegunaan Dan Manfaat Dari File Header iostream.h Dan conio.h

   iostream.h (input output stream)

   File header yang digunakan untuk melakukan penginputan dan pencetakan

   Perintah yang digunakan adalah

   a. cin             : untuk peginputan

   b. cout          : untuk pencetakan conio.h (console input output)

    File header yang digunakan untuk melakukan perintah penghapusan layar dan

    tampilan output

    perintah yang digunakan adalah

    a.  clrscr()    : untuk menghapus layar

    b. getch()     : untuk menahan tampilan output

3.5 Definisi Array

            Array adalah suatu tipe data terstruktur yang dapat menyimpan banyak data dengan suatu nama yang sama dan menempati tempat dimemori yang berurutan serta bertipe data sama pula.

Contoh instruksi menyiapkan array numeric dengan nilainya.

Output program :

3 5 12 7 9

Source code :

#include <stdio.h>

void main ()

{

int A[5]= (3, 5, 12, 7, 9)

int i;

for ( i=0; i<=4; i++ )

{

printf ( “%i”, A[i] );

}

}

3.6  Percobaan Praktikum

3.3.1 Array satu dimensi sebanyak 5 elemen tipe :

Output program :

 

Gambar 3.1 Array satu dimensi

Source Code :

#include<stdio.h>

main()

{

long int *a[5];

for(int n=0 ; n<5 ; n++)

     {

           printf("%ld\n", &a[n]);

     }

}

3.2.2 Array dua dimensi

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

      Baris no.0                          Baris no.1                    Baris no.2

1      2       3       4       5   6      7       8        9      10 11    12    13      14     15

            Maka  akan tercetak : 

Output Program :

 

Gambar 3.2 Array dua dimensi

Source Code :

#include<stdio.h>

main()

{

int z[1][15];

int u,m;

for(u=0;u<1;u++)

{

for(m=0;m<15;m++)

{

z[u][m]=m+1;

if (m%5==u)

{

printf("\n\n");

}

printf("%d\t",z[u][m]);

} } }

3.2.3 Buat tampilan output elemen array dua dimensi sebagai berikut :

  A[1, 1]=1

  A[1, 2]=2

  A[2, 1]=3

  A[2, 2]=4

  B[1,1]=5

  B[1,2]=6

  B[2,1]=7

  B[2,2]=8

  C = A + B

  C[1, 1]=6

  C[1, 2]=8

  C[2, 1]=10

  C[2, 2]=12

Output Program :

 

Gambar 3.3 Elemen array dua dimensi

Source Code :

#include<stdio.h>

void main()

{

     int A[2][2], B[2][2], C[2][2];

     int i,j;

     printf("Nilai A\n");

     for(i=0;i<2;i++)

           for(j=0;j<2;j++)

           {

     printf("A[%d][%d]:",i+1,j+1);

scanf("%d",&A[i][j]);

           }

     printf("Nilai B\n");

     for(i=0;i<2;i++)

     for(j=0;j<2;j++)

           {

     printf("B[%d][%d]:",i+1,j+1);

scanf("%d",&B[i][j]);

           }

     printf("\n");

     puts("C = A+B");

     printf("\n");

     for(i=0;i<2;i++)

     for(j=0;j<2;j++)

     printf("C[%d][%d]= %d\n",i+1,j+1,A[i][j]+B[i][j]);

}

Nilai Ujian             rangking 56                                4 78                                7 43                                2 96                                9 67                                5 83                                8 51             3 74             6 32             1

3.2.4 Buatlah tampilan program seperti berikut:

Output Program :

 

Gambar 3.4 Nilai ujian

Source Code :

#include <stdio.h>

#define banyaknya_nilai 9

main()

{

static int nilai[]={56, 78, 43, 96, 67, 83, 51, 74, 32};

int rangking[banyaknya_nilai];

int a,b;

for (a=0;a<banyaknya_nilai;a++){

rangking[a]=1;

for (b=0;b<banyaknya_nilai;b++){

if (nilai[a]>nilai[b])

rangking[a]++;

}

}

printf("Nilai Ujian \t Rangking\n");

for (a=0;a<banyaknya_nilai;a++){

printf("%d \t\t %d\n",nilai[a], rangking[a]);

}

}

BAB IV

STACK ( TUMPUKAN )

4.1 Definisi Stack

Stack merupakan bentuk khusus dari suatu struktur data, dimana node yang ditambahkan ke dalam list dan diambil dari list hanya pada 'kepala'nya, atau dengan kata lain prinsip pengolahannya adalah last-in first-out (LIFO). data yang terakhir kali dimasukkan akan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix).

4.2 Ciri Stack :

·         Elemen TOP (puncak) diketahui

·         penisipan dan penghapusan elemen selalu dilakukan di TOP

·         LIFO (Last In First Out).

Di C++, ada dua cara penerapan prinsip stack, yakni dengan array dan linked list. Setidaknya stack haruslah memiliki operasi-operasi sebagai berikut.

Push       :  Untuk menambahkan item pada tumpukan paling atas

Pop         :  Untuk mengambil item teratas

Clear      :  Untuk mengosongkan stack

IsEmpty :  Untuk memeriksa apakah stack kosong

IsFul l    :  Untuk memeriksa apakah stack sudah penuh

Dalam bab ini penjelasan mengenai stack akan menggunakan kelas stack. Kelima operasi stack diatas akan dideklarasikan secara abstrak dalam kelas ini, sedangkan kelas turunan dari stack akan mengimplementasikan operasi-operasi tersebut.

4.3 Pengertian Operand Dan Operator

Operator atau tanda operasi adalah suatu tanda atau simbol yang biasa dilibatkan dalam program untuk melakukan suatu operasi atau manipulasi

Operand adalah molekul bahasa pemrograman, yang merupakan kesatuan terkecil dan hampir tak dapat dipisahkan

4.4 Pengertian Infix, Postfix Dan Prefix

Infix adalah notasi yang operatornya ditempatkan di antara dua operand. Notasi ini telah dikenal secara umum oleh manusia dan selalu digunakan dalam perhitungan aritmatika.

Postfix adalah notasi yang operatornya ditempatkan setelah dua operand.

Prefix adalah notasi yang operatornya ditempatkan sebelum dua operand

4.4.1 Stack dengan Array

Sesuai dengan sifat stack, pengambilan / penghapusan delemen dalam stack harus dimulai dari elemen teratas.

Operasi-Operasi Pada Stack Dengan Array

a. Konstruktor

Fungsi ini membuat sebuah stack baru yang masih kosong. Konsepnya adalah bahwa Top menunjukkan elemen stack teratas. Jika Top bernilai -1, berarti tumpukan kosong.

b. IsFul

Fungsi ini memeriksa apakah stack yang ada sudah penuh. Stack penuh jika stack penuh jika puncak stack terdapat tepat dibawah jumlah maksimum yang dapat ditampung stack atau dengan kata lain Top = MAX_STACK -1.

c. Push

Fungsi ini menambahkan sebuah elemen ke dalam stack dan tidak bias dilakukan lagi jika stack sudah penuh.

d. IsEmpty

Fungsi menentukan apakah stack kosong atau tidak. Tanda bahwa stack kosong adalah Top bernilai kurang dari nol.

e. Pop

Fungsi ini mengambil elemen teratas dari stack dengan syarat stack tidak boleh kosong.

f. Clear

Fungsi ini mengosongkan stack dengan cara mengeset Top dengan -1. Jika Top bernilai kurang dari nol maka stack dianggap kosong.

4.1.2 Stack dengan Single Linked List

Operasi-operasi untuk Stack dengan Linked List

a. Konstruktor

Fungsi ini membuat stack baru yang kosong. Stack adalah kosong jika Top tidak menunjuk apa pun (bernilai NULL).

b. IsEmpty

Fungsi memeriksa apakah stack yang adamasih kosong.

c. Push

Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalamsingle linked list biasa.

d. Pop

Fungsi ini mengeluarkan elemen teratas dari stack.

e. Clear

Fungsi ini akan menghapus stack yang ada.

4.2 Percobaan Praktikum

4.2.1 Program untuk mengisi (PUSH) stack sampai PENUH, dan mengambil (POP) isi stack sampai KOSONG

Output Program :

 

Gambar 4.1 Mengisi (PUSH) stack sampai PENUH,

Source Code :

#include<stdio.h>

 #include<conio.h>

 void main()

 {

  int SA[20], SB[20], X, Y, I, TopA, TopB;

  clrscr();

  TopA=-1,TopB=1;

  scanf("%i",&X);

  TopA++;

  SA[TopA]=X;

  for(I=1;I<=9;I++);

{scanf("%i",&X);

 while(TopA >-1 && SA[TopA] > X)

  {

  TopB++;

  SB[TopB]=SA[TopA];

  TopA--;

       }

  //mengisi X ke stack SA

  TopA++;

  SA[TopA]=X;

  //menyalin isi stack B kestack A

  while(TopB > -1)

       {

  SA[TopA]=SB[TopB];

  TopB--;

 }

  }

  for(I=0;I<=9;I++);

  {

  printf("&i", SA[I]);

  }

  }

BAB V

QUEUE ( ANTRIAN )

5.1. Definisi Queue

Jika diartikan secara harafiah, queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat Anda mengantri di loket untuk membeli tiket. Istilah yang cukup sering dipakai seseorang masuk dalam sebuah antrian adalah enqueue. Dalam suatu antrian, yang datang terlebih dahulu akan dilayani lebih dahulu. Istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue. Oleh karena itu, queue bersifat FIFO (first in first out).  Walaupun berbeda implementasi, struktur data queue setidaknya harus memiliki operasi-operasi sebagai berikut :

1.      EnQueue : Memasukkan data ke dalam antrian

2.      DeQueue : Mengeluarkan data terdepan dari antrian

3.      Clear : Menghapus seluruh antrian

4.      IsEmpty : Memeriksa apakah antrian kosong

5.      IsFull : Memeriksa apakah antrian penuh

5.1.1 Implementasi Queue dengan Linear Array

Linear array adalah suatu array yang dibuat seakan-akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar. Berikut ini diberikan deklarasi kelas Queue Linear sebagai implementasi dari Queue menggunakan linear array. Dalam prakteknya, anda dapat menggantinya sesuai dengan kebutuhan Anda. Data diakses dengan field data, sedangkan indeks item pertama dan terakhir disimpan dalam field Head dan Tail. Konstruktor akan menginisialisasikan nilai Head dan Tail dengan -1 untuk menunjukkan bahwa antrian masih kosong dan mengalokasikan data sebanyak MAX_QUEUE yang ditunjuk oleh Data. Destruktor akan mengosongkan antrian kembali dan mendealokasikan memori yang digunakan oleh antrian.

5.2 Operasi-Operasi Queue dengan Linear Array

• IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. hal ini dilakukan dengan mengecek apakah tail bernilai -1 atau tidak. Nilai -1 menandakan bahwa queue masih kosong.
• IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bias menampung data dengan cara mengecek apakah nilai tail sudah sama dengan jumlah maksimal queue. Jika nilai keduanya sama, berarti queue sudah penuh.
• EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen dalam queue.
• DeQueue

Fungsi DeQueue berguna untuk mengambil sebuah elemen dari queue. Operasi ini sering disebut juga serve. Hal ini dilakukan dengan cara memindahkan sejauh satu langkah ke posisi di depannya sehingga otomatis elemen yang paling depan akan tertimpa dengan elemen yang terletak di belakangnya.
• Clear

Fungsi Clear berguna untuk menghapus semua lemen dalam queue dengan jalan mengeluarkan semua elemen tersebut satu per satu hingga queue kosong dengan memanfaatkan fungsi DEQueue.

5.3 Ciri – ciri Queue

1. Kosong tak ada isinya.

Counter = 0

2. Penuh, tak bisa diisi

Counter = n

3. Bisa diisi

Counter < n

4. Ada isinya

Counter > 0

5.4 Contoh Algoritma Pada Queue
2 . Algoritma dasar untuk :

a. inisialisasi

 void AWAL(void)

         {

         F  =  0;

         R  =  -1;

        Counter = 0;    

        }

b.  insert sebuah record

void INSERT(void)

     {

     R = (R+1) % n;

     Q[R] = X;

     Counter++;

     }

c.  delete sebuah record

void DELETE(void)

    {

    X = Q[F];

    F =(F+1) % n;

    Counter--;

    }

d. tidak ada reset

3. Algortima lengkap untuk :

a. Insert sebuah record

void INSERT(void)

        {

        if ( Counter < n)

       {  R = (R+1) % n;

       Q[R] = X;

       Counter++;

       }

       else   printf(“Antrian Penuh”);

      }

b.  Delete sebuah record

void DELETE(void)

    {

    if ( Counter > 0)

    {  X = Q[F];

     F = (F+1) % n;

     Counter--;

     }

     else    printf(“Antrian Kosong”);

     }

4. Algoritma yang lengkap untuk mengisi antrian record per record sampai antrian penuh tak bias di isi lagi.

void INSERT(void)

    { if ( Counter == n)

     printf(“Antrian Penuh”)              

     else  { R = (R+1) % n;

          Q[R] = X;

          Counter++;  }

     }

5. Algoritma lengkap untuk mendelete isi antrian record per record sampai antrian kosong

void DELETE(void)

{ if ( Counter == 0)

     printf(“Antrian Kosong”)

  else  {  X = Q[F];

           F = (F+1) % n;

           Counter--;  }

}

5.3 Percobaan praktikum

5.3.1  Membuat program untuk call function insert dan delete

Output :

 

Gambar 3.1 Tampilan menu

 

Gambar 3.2 Tampilan menginputkan / insert data

 

Gambar 3.3 Tampilan display / menampilkan data

 

Gambar 3.4 Tampilan menghapus data

 

Gambar 3.5 Tampilan data setelah dihapus

Source Code :

#include<stdio.h>

#include<iostream.h>

#include<conio.h>

#define QSIZE 5

int front=0,rear=-1,q[QSIZE];

void insert(int x)

{

rear=(rear+1)%QSIZE;

q[rear]=x;

}

int del()

{

int t=0;

if(rear<=-1)

cout<<"\nQueue is empty.\n\n";

else

{

t=q[front];

if(front!=rear)

front=(front+1)%QSIZE;

else

{

front=0;

rear=-1;

}

}

return t;

}

void display()

{

int i;

if(rear<=-1)

cout<<"\nQueue is empty.\n\n";

else

{

cout<<"\nThe queue is\n";

for(i=front;i!=rear;i=(i+1)%QSIZE)

cout<<q[i]<<" \t";

cout<<q[i]<<" \n";

}

}

void main()

{

int ch,in,d;

clrscr();

do

{

cout<<"\nMenu\n\n";

cout<<"1.Insert\n";

cout<<"2.Delete\n";

cout<<"3.Display\n";

cout<<"Enter your choice:";

cin>>ch;

switch(ch)

{

case 1:clrscr();

if(front==(rear+1)%QSIZE && rear>=QSIZE-1)

cout<<"\nQueue is full\n\n";

else

{

cout<<"\nEnter the element to be inserted:";

cin>>in;

insert(in);

clrscr();

}

break;

case 2:clrscr();

d=del();

if(d!=0)

cout<<"\nElement deleted="<<d<<"\n\n";

break;

case 3:clrscr();

display();

break;

cout<<"\nEnter an appropriate choice.\n\n";

}

}

while(ch!=5);

}

BAB VI

LINKED LIST

6.1 Definisi Pointer

Pointer adalah suatu variabel penunjuk, berisi nilai yang menunjuk alamat suatu lokasi memori tertentu.  

1. Sifat dan ciri variable pointer :

•         Jadi pointer tidak berisi nilai data, melainkan berisi suatu alamat memori atau null jika tidak berisi data.

•         Pointer yang tidak diinisialisasi disebut dangling pointer

•         Lokasi memori tersebut bisa diwakili sebuah variabel atau dapat juga berupa nilai alamat memori secara langsung.

•         Berisi alamat memori dari suatu variabel tertentu.

•         Membutuhkan operator khusus

•         Bersifat dinamis

2.      Metode pembuatan single linked list :
· LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
· FIFO (First In First Out), aplikasinya : Queue (Antrean)

LIFO ( Last In First Out)
Lifo adalah suatu metode pembuatan Linked List di mana data yang masuk paling akhir adalah data yang keluar paling awal. Hal ini dapat dianalogikan (dalam kehidupan sehari-hari) dengan saat Anda menumpuk barang seperti digambarkan dibawah ini.
Jika linked list dibuat dengan metode LIFO, terjadi penambahan / Insert simpul di belakang, dikenal dengan istilah INSERT.

FIFO (First In First Out)

Suatu metode pembuatan linked list dimana data yang masuk paling awal adalah data yang keluar paling awal juga. Hal ini dapat dianalogikan (dalam kehidupan sehari - hari), misalnya saat sekelompok orang yang dating (ENQUEUE) mengantri hendak beli tiket di loket.

      6.1.1 Pengenalan Linked List

         Pada bab sebelumnya telah dijelaskan mengenai variabel array yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu, ruang memori yang dipakai olehnya tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada  saat program dijalankan. Untuk memecahkan masalah di atas, kita dapat  menggunakan variabel pointer. Tipe data pointer bersifat dinamis, variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat direlokasikan kembali.

         Setiap ingin menambahkan data, Anda selalu menggunakan variabel pointer yang baru, akibatnya Anda akan membutuhkan banyak sekali pointer. Oleh karena itu, ada baiknya jika Anda hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kita sebut Linked List. Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian. Linked list juga mengandung sebuah variabel penuding list, yang biasanya diberi nama

start, yang berisi alamat dari simpul pertama dalam list. Di sini tergambar panah  dari start mengarah ke simpul pertama tersebut. Hal khusus dapat terjadi, yakni list tidak mengandung sebuah simpulpun. List semacam itu disebut list hampa atau list nol. List ini disajikan dengan menempatkan  penuding  nol  pada  variabel  START.

6.1.2 Single Linked List

         Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node/simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).

Pembuatan Single Linked List dapat menggunakan 2 metode:

1.)    LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)

2.)    FIFO (First In First Out), aplikasinya : Queue (Antrean)

1.)     LIFO ( Last In First Out) Lifo adalah suatu metode pembuatan Linked List di mana data yang masuk paling akhir adalah data yang keluar paling awal. Hal ini dapat dianalogikan (dalam kehidupan sehari-hari) dengan saat Anda menumpuk barang seperti digambarkan dibawah ini. Pembuatan sebuah simpul dalam suatu linked list seperti digambarkan dibawah ini. Jika linked list dibuat dengan metode LIFO, terjadi penambahan / Insert simpul di belakang, dikenal dengan istilah INSERT.

2.)    FIFO (Fisrt In Fisrt Out)  FIFO adalah suatu metode pembuatan Linked List di mana data yang masuk paling awal adalah data yang keluar paling awal juga. Hal ini dapat di analogikan (dalam kehidupan sehari-hari), misalnya saat sekelompok orang yang datang (ENQUEUE) mengantri hendak membeli tiket di loket. Jika linked list dibuat dengan metode FIFO, terjadi penambahan / Insert simpul didepan.

6.1.3 Double Linked List

         Double Linked List adalah suatu linked list yang mempunyai 2 penunjuk yaitu penunjuk ke data sebelumnya dan berikutnya. Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/ mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, anda dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.

         Untuk view data, langkah yang dilakukan adalah dengan menelusuri semua elemen list sampai elemen terakhir. Setelah melakukan penelurusan posisi awal dan akhir elemen tidak boleh berubah sehingga untuk melakukan penelusuran dibutuhkan sebuah variabel bantu. Kelebihan dari view data pada linked list adalah kita dapat menampilkan data dari data terakhir dengan lebih mudah.

6.1.4 Circular Double Linked List

          Ini adalah double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.

Operasi-Operasi yang ada pada Linked List :

1.)    Insert : istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list. 

2.)    IsEmpty : fungsi ini menentukan apakah linked list kosong atau tidak. 

3.)    Find First : fungsi ini mencari elemen pertama dari linked list

4.)    Find Next : fungsi ini mencari elemen sesudah elemen yang ditunjuk now.

5.)    Retrieve : fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi. 

6.)    Update : fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu. 

7.)    Delete Now : fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut. 

8.)    Delete Head : fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya. 

9.)    Clear : fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

6.2 Percobaan Praktikum

6.2.1 M embuat program dari sebuah penggalan linked list

Output program:

 

Gambar 6.1 Tampilan program dari sebuah penggalan linked list

Source Code :

#include<iostream.h>

#include<conio.h>

#include<stdlib.h>

#include<malloc.h>

#define Nil NULL

#define info(P) P->info

#define next(P) P->next

#define First(L) (L)

typedef int InfoType;

typedef struct telmtlist *address;

typedef struct telmtlist

{

InfoType info;

address next;

}elmtlist;

typedef address list;

void CiptaSenarai(list *L)

{

First(*L)=NULL;

}list NodBaru(int m)

{

list n;

n=(list) malloc(sizeof(elmtlist));

if(n!=NULL)

{

n->info=m;

n->next=NULL;

}return n;

}

void SisipSenarai(list *L, list t, list p)

{

if(p==NULL)

{

t->next = *L;

*L = t;

}else

{

t->next = p->next;

p->next = t;

}

}void CetakSenarai(list L)

{

list ps;

for(ps=L; ps!=Nil; ps=ps->next)

{

cout<<" "<<info(ps)<<" -->";

}cout<<" NULL"<<endl;

}

int main()

{

list pel;

list n;

int i,k,nilai;

CiptaSenarai(&pel);

cout<<"Masukkan Banyak Data = ";

cin>>k;

for(i=1; i<=k; i++)

{

cout<<"Masukkan Data Senarai ke-"<<i<<" = ";

cin>>nilai;

n = NodBaru(nilai);

SisipSenarai(&pel, n, NULL);

}CetakSenarai(pel);

getch();

return 0;

BAB VII

TREE ( POHON)

7.1  Dasar Teori

1.      Definisi tree : “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”.

2.      Istilah-istilah umum dalam tree :

a.             Predecessor adalah simpul yang berada di atas simpul yang ditinjau. Contoh : Predecessor D adalah B.

b.            Successor adalah simpul yang berada di bawah simpul yang ditinjau. Contoh : Successor D adalah I.

c.             Ancestor suatu simpul adalah semua simpul yang terletak dalam satu jalur dengan simpul tersebut, dari akar sampai simul yang ditinjaunya. Contoh Ancestor L adalah A,C dan G.

d.            Descendant adalah seluruh simpul yang terletak sesudah simpul tertentu dan terletak pada jalur yang sama. Contoh : Descendant E adalah J dan K.

e.             Parent adalah simpul yang berada satu level di atas simpul yang ditinjau. Contoh : Parent J adalah E

f.             Child,  suatu node adalah semua node yang dapat dicapai oleh node tersebutdengan sebuah path saja. Sebagai contoh, child dari N1 adalah N2, N3, dan N4;

child dari N4 adalah N5 dan N6; dan sebagainya.

g.             Sibling adalah simpul-simpul yang memiliki parent yang sama dengan simpul yang ditinjau. Contoh : Sibling J adalah K

h.            Subtree, sisa elemen yang lain (yang disebut node) terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu sama

lain (disjoint),

i.              Size : banyaknya node dalam suatu tree

j.              Height, Tinggi (height) atau kedalaman (depth) suatu tree adalah tingkat maksimum dari tingkat dalam tree tersebut dikurangi 1. Contoh dalam tree di atas, mempunyai depth 4.

k.            Root : satu-satunya node khusus dalam tree yang tak punya predecssor

l.              Leaf, simpul yang memiliki derajat 0 (nol) atau node-node dalam tree yang tak memiliki seccessor.

m.          Degree, menyatakan banyaknya anak/turunan di simpul tersebut. Contoh : Simpul A memiliki derajat 2 (B dan C), simpul yang memiliki derajat 0 (nol) disebut leaf (daun) seperti : I, J, K, L, N, dan O.

3.        Jenis-jenis tree

a.       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.

b.      Full Binary Tree, Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

c.       Complete Binary Tree, Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

d.      Skewed Binary Tree yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

•         Tree adalah Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layaknya struktur sebuah pohon.

•         Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah.

•         Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.

7.2  Terminologi Tree

 Table 7.1 Terminologi tree

 

7.3  Jenis Tree

7.3.1 Binary Tree

•         Suatu tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah.

•         Tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Gambar 7.1 Binary tree

Macam-macam Binary tree :

1.      Full Binary Tree : semua node ( kecuali leaf) pasti memiliki 2 anak dan tiap subtreememiliki panjang path yang sam

Gambar 7.2 Full binary tree

2.      Complete Binary Tree : mirip dengan full binary tree, tapi tiap subtree boleh memiliki panjang path yang berbeda dan tiap node ( kecuali leaf) mamiliki 2 anak.

Gambar 7.3 Complete binary tree

3.      Skewed Binary Tree : binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak.

Gambar 7.4 Skewed binary tree

7.4 Operasi-operasi pada Tree

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

•  pohon = NULL;

b.   Clear : menghapus semua elemen tree.

•   pohon = NULL;

c.    Empty : mengetahui apakah tree kosong atau tidak

int isEmpty(Tree *pohon){

if(pohon == NULL) return 1;

else return 0;

}

d.      Insert : menambah node ke dalam Tree secara rekursif.  Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri.  Untuk data pertama akan menjadi elemen root.

e.       Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu.  Syaratnya adalah tree tidak boleh kosong.

f.       Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.

g.      Count: menghitung jumlah node dalam Tree

h.      Height : mengetahui kedalaman sebuah Tree

i.        Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree

j.        Child : mengetahui anak dari sebuah node (jika punya).

7.4  Percobaan Praktikum

7.4.1 Program untuk penempatan pointer

Output Program :

 

Gambar 7.5 Tampilan program untuk penempatan pointer

Source Code :

#include <iostream.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;

cout<<"\n Data bertambah \n";

             }

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

             {

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

             }

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

             {

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

             }

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

             {

cout<<"\n\t Data sudah ada";

             }

      }

void preOrder (Node *root)

      {

if (root != NULL)

             {

cout<<" "<<root->data;preOrder (root->kiri);

preOrder (root->kanan);

             }

     }

void inOrder (Node *root)

     {

if (root != NULL)

             {

inOrder (root->kiri);

cout<<" "<< root->data;

inOrder (root->kanan);

             }

     }

void postOrder (Node *root)

     {

if (root != NULL)

             {

postOrder (root->kiri);

postOrder (root->kanan);

cout<<" "<<root->data;

             }

     }

void main ()

     {

int pil, c;

Node *pohon, *t;

pohon = NULL;

do

             {

int data;

cout<<"\n \t\t\t Menu \n\n";

cout<<"\t 1. Tambah \n";

cout<<"\t 2. Lihat pre-order \n";

cout<<"\t 3. Lihat in-order \n";

cout<<"\t 4. Lihat post-order \n";

cout<<"\t 5. Exit \n";

cout<<"\n \t\t pilihan anda : ";

cin>>pil;

switch (pil)

                   {

case 1 : cout<<"\n\n Data baru : ";

cin>>data;

tambah (&pohon,data);break;

case 2 : if (pohon != NULL) preOrder (pohon);

else cout<<"\n Data masih kosong : "<<" ";break;

case 3 : if (pohon != NULL) inOrder (pohon);

else cout<<"data masih kosong : "<<" ";break;

case 4 : if (pohon != NULL) postOrder (pohon);

else cout<<"\n Data masih kosong"<<" ";break;

                   }

        }

while (pil !=5);

     }

BAB VIII

SEACRH AND SORT

8.1 Dasar Teori

         8.1.1 Searching

Searching merupakan suatu proses pendarian data dari sejumlah data yang ada. Pencarian data dapat dilakukan pada sejumlah data yang sudah terurut atau juga pada data yang sama sekali belum terurut. Kita mencoba menggunakan dua metode pencarian yaitu :

·         Pencarian Berurutan (Sequential Searching).

Metode ini merupakan metode paling sederhana, secara garis besar metode ini bisa dijelaskan sebagai berikut. Dari data yang diketahui, data yang dicari dibandingkan satu per satu sampai data tersebut ditemukan atau tidak ditemukan. Pada saat data yang dicari sudah ditemukan, maka proses pencarian langsung dihentikan. Tetapi jika belum ditemukan, maka pencarian diteruskan sampai seluruh data dibandingkan. Dalam kasus paling buruk, untuk data dengan N elemen harus dilakukan pencarian sebanyak N kali pula. Ada baiknya jika data yang dicari tidak ditemukan maka data ditambahkan pada posisi terakhir.

·         Pencarian Biner (Binary Seacrh).

Metode ini digunakan jika sejumlah data telah diurutkan. Jika dibandingkan dengan metode awal tadi metode ini jauh lebih cepat. Secara garis besar metode ini bisa dijelaskan sebagai berikut. Urutkan dahulu sejumlah data. Lalu bagi dua data-data tadi dengan jumlah data yang sama pada masing-masingnya. Kemudian data dibandingkan dengan data terakhir dari subdata yang pertama. Jika data yang dicari lebih keci, pencarian dilanjutkan pada sub data pertama dengan terlebih dahulu membagi dua lagi data-data tersebut dengan jumlah yang sama. Tetapi jika data yang dicari lebih besar dari data terakhir subdata pertama, berarti data yang dicari kemungkinan terletak pada subdata yang kedua. Proses diatas dilakukan berulang sampai data ditemukan atau tidak ditemukan.

          8.1.2  Sort

Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif. Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan secara ascending demi kenyamanan dalam penelusuran data.Beberapa macam algoritma  sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna. Ada berbagai macam-macam sort :

1. Insertion Sort

Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua.Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua).  Elemen  pertama diambil  dari  bagian  array  yang  belum  diurutkan  dan kemudian  diletakkan  sesuai  posisinya  pada  bagian  lain  dari  array  yang  telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

2. Selection Sort

Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot. Proses pengurutan dengan metode seleksi dapat dijelaskan sebagai berikut : 

• langkah pertama dicari data terkecil dari data pertama sampai data terakhir.  Kemudian data terkecil ditukar dengan data pertama.   Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain.
• Langkah kedua, data terkecil kita

cari mulai dari data kedua sampai terakhir.  Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan.

3.   Merge Sort

Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table sehingga dalam keadaan urut.

4.   Quick Sort

Metode Quick sering disebut juga metode partisi (partition exchange sort).  Metode ini diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1962.  Untuk mempertinggi sefektifitas dari metode ini, digunakan teknik menukarkan dua elemen dengan jarak yang cukup besar. Proses penukaran dengan metode quick dapat dijelaskan sebagai berikut.:  mula-mula dipilih data tertentu yang disebut pivot, misalnya x.  Pivot dipili untuk mengatur data di sebelah kiri agar lebih kecil daripada pivot dan data di sebelah kanan agar lebih besar daripada pivot.  Pivot ini diletakkan pada posisi ke j sedemikian sehingga data antara 1 sampai dengan j-1 lebih kecil daripada x.  Sedangkan data pada posisi ke j+1 sampai N lebih besar daripada x.  Caranya dengan menukarkan data diantara posisi 1 sampai dengan j-1 yang lebih besar daripada x dengan data diantara posisi j+1 sampa dengan N yang lebih kecil daripada x.

5.   Bubble Sort

Metode gelembung (bubble sort) sering juga disebut dengan metode penukaran (exchange sort) adalah metode yang mengurutkan data dengan cara membandingkan masing-masing elemen, kemudian melakukan penukaran bila perlu.  Metode ini mudah dipahami dan diprogram, tetapi bila dibandingkan dengan metode lain yang kita pelajari, metode ini merupakan metode yang paling tidak efisien. Proses pengurutan metode gelembung ini menggunakan dua kalang.  Kalang pertama melakukan pengulangan dari elemen ke 2 sampai dengan elemen ke N-1 (misalnya variable i), sedangkan kalang kedua melakukan pengulangan menurun dari elemen ke N sampai elemen ke i (misalnya variable j).  Pada setiap pengulangan, elemen ke j-1 dibandingkan dengan elemen ke j.  Apabila data ke j-1 lebih besar daripada data ke j, dilakukan penukaran.

Syntax :

void BubbleSort()

{ 

int i, j; 

for(i=1; i<Max-1; i++)

for(j=Max-1; j>=i; j--)

if(Data[j-1] > Data[j])

Tukar(&Data[j-1], &Data[j]);

}  

6.   Shell Sort

Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment).  Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort.  Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan Proses pengurutan dengan metode Shell.

Syntax :

void ShellSort(int N)

{

int Jarak, i, j;

bool Sudah;

Jarak = N;

while(Lompat > 1){

Jarak = Jarak / 2;

Sudah = false;

while(!Sudah){

Sudah = true;

for(j=0; j<N-Jarak; j++){

i = j + Jarak;

if(Data[j] > Data[i]){

Tukar(&Data[j], &Data[i]);

Sudah = false;

} } } } }

8.2  Percobaan Praktikum

8.2.1  Program menggunakan metode insertion Sort sehingga akan tercetak

Output Program :

 

Gambar 8.1 Tampilan program menggunakan insertion sort

Source Code :

#include <stdio.h>

#include <conio.h>

#include <string.h>

#define MAX_STACK 10

typedef struct STACK {

int top;

char data[10][10];

};

STACK tumpuk;

void inisialisasi(){

tumpuk.top = -1;

}

int IsFull(){

if(tumpuk.top == MAX_STACK-1) return 1; else return 0;

}

int IsEmpty(){

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

}

void Push(char d[10]){

tumpuk.top++;

strcpy(tumpuk.data[tumpuk.top],d);

}

void Pop(){

printf("Data yang terambil = %s\n",tumpuk.data[tumpuk.top]);

tumpuk.top--;

}

void Clear(){

tumpuk.top=-1;

}

void TampilStack(){

for(int i=tumpuk.top;i>=0;i--){

printf("Data : %s\n",tumpuk.data[i]);

}

}

int main(){

int pil;

inisialisasi();

char dt[10];

do{

printf("1. Input Data\n");

printf("2. Bubble Sort\n");

printf("3. Exchange Sort \n");

printf("4. Selection Sort \n");

printf("5. Tampilan Data\n");

printf("6. Acak\n");

printf("7. Exit\n");

printf("Pilihan : ");scanf("%d",&pil);

switch(pil){

case 1: if(IsFull() != 1){

printf("Masukkan Jumlah Data = ");scanf("%s",dt);

Push(dt);

printf("Masukkan data ke-1 = ");scanf("%s",dt);

Push(dt);

printf("Masukkan data kw-2 = ");scanf("%s",dt);

Push(dt);

printf("Masukkan data ke-3 = ");scanf("%s",dt);

Push(dt);

printf("Masukkan data ke-4 = ");scanf("%s",dt);

Push(dt);

printf("Masukkan data ke-5 = ");scanf("%s",dt);

Push(dt);

printf("Masukkan data ke-6 = ");scanf("%s",dt);

Push(dt);

printf("Masukkan data ke-7 = ");scanf("%s",dt);

Push(dt);

printf("Masukkan data ke-8 = ");scanf("%s",dt);

Push(dt);

printf("Masukkan data ke-9 = ");scanf("%s",dt);

Push(dt);

printf("Masukkan data ke-10 = ");scanf("%s",dt);

Push(dt);

} else printf("\nSudah penuh!\n");

break;

case 2: if(IsEmpty() != 1)

Pop();

else

printf("\nMasih kosong!\n");

break;

case 3: if(IsEmpty() != 1)

TampilStack();

else

printf("\nMasih kosong!\n");

break;

case 4: Clear();

printf("\nSudah kosong!\n");

break;

}

getch();

}while(pil != 5);

getch();

}

8.2.2        Membuat program perhitungan perkalian

Output program :

 

Gambar 8.1 Tampilan program perhitungan perkalian

Source code :

#include<stdio.h>

main()

{

int a,b;

for(a=1;a<=3;a++)

{

for(b=1;b<=10;b++)

{

printf("%dx%d=%d\t",a,b,a*b);

//printf("\n");

}}}

8.2.3        Periksalah kesalahan-kesalahan program dan benarkan sehingga dapat dieksekusi akan tercetak :

Output program

 

Source Code :

#include <stdio.h>

Char StrBilangan[10][10] = {"nol","satu","dua","tiga","empat","lima","enam","tujuh","delapan","sembilan"};

void SaySatuan(char nilai) //0..9

{

printf("%s",&StrBilangan[nilai]);

}

void SayPuluhan(char nilai) // 10..99

{

   if (nilai <10)

   SaySatuan(nilai);

   else

   {

   if (nilai >= 12 && nilai <= 19)

   {

   SaySatuan(nilai % 10);

   printf(" belas ");

}

   if (nilai >= 20 && nilai <= 99)

   {

   SaySatuan(nilai / 10);

   printf(" puluh ");

   SaySatuan(nilai % 10);}}}

void SayRatusan(int nilai) // 100..999

{

   if (nilai <100)

   SayPuluhan(nilai);

   else{

        if(nilai >= 100 && nilai <= 199)

        printf(" seratus ");

        if (nilai >= 200 && nilai <= 999)

        {

        SaySatuan(nilai / 100);

        printf(" ratus ");

        }

        if(nilai % 100 != 0) //untuk menghindari seratus nol

   SayPuluhan(nilai % 100);

   }

}

void SayRibuan(unsigned long nilai) //1000...999999

{

   if (nilai <1000)

   SayRatusan(nilai);

   else

   {

        if (nilai >= 1000 && nilai <= 1999)

        printf(" Seribu ");

        if (nilai >= 2000 && nilai <= 999999)

        {

             SayRatusan(nilai/1000);

             printf(" ribu ");

        }

        if (nilai % 1000 != 0)

        SayRatusan(nilai % 1000);

   }

}

void SayJuta(unsigned long nilai) //1.000.000 -> 999.999.999

{

   if (nilai <1000000)

   SayRibuan(nilai);

   else

   {

        SayRatusan(nilai / 1000000);

        printf(" juta ");

        if(nilai % 1000000 != 0)

        SayRibuan(nilai % 1000000);

   }

}

void SayMilyar(unsigned long nilai) // 1.000.000.000 -> 999.999.999.999

{

   if (nilai <1000000000)

   SayJuta(nilai);

   else

   {

        SayRatusan(nilai / 1000000000);

        printf(" Milyar ");

        if(nilai % 1000000000 != 0)

        SayJuta(nilai % 1000000000);

   }}

void SayBilangan(unsigned long nilai) // Fungsi pengarah

{

   if (nilai <= 9)

   SaySatuan(nilai);

   if (nilai >= 10 && nilai <= 99)

   SayPuluhan(nilai);

   if (nilai >= 100 && nilai <= 999)

   SayRatusan(nilai);

   if(nilai >= 1000 && nilai <= 999999)

   SayRibuan(nilai);

   if(nilai >= 1000000 && nilai <= 999999999)

   SayJuta(nilai);

   if(nilai >= 1000000000)

   SayMilyar(nilai);

}

void main(void){

   SayBilangan(163);

   SayBilangan(25234);

   SayBilangan(-1);}

BAB IX

RECURSIVE ( REKURSI )

9.1 Dasar Teori

Recursive (rekursif) adalah teknik pemecahan masalah yang powerful dan dapat digunakan ketika inti dari masalah terjadi berulang kali. Tentu saja, tipe dari masalah ini dapat dipecahkan mengunakan perkataan berulang-ulang (i.e., menggunakan konstruksi looping seperti for, while dan do-while).Sesungguhnya, iterasi atau perkataan berulang-ulang merupakan peralatan yang lebih efisien jika dibandingkan dengan recursif tetapi recursion menyediakan solusi yang lebih baik untuk suatu masalah. Pada rekursif, method dapat memanggil dirinya sendiri. Data yang berada dalam method tersebut seperti argument disimpan sementara kedalam stack sampai method pemanggilnya diselesaikan.

Algoritma Recursive adalah fungsi yang tepat yang dapat di gunakan untuk memecahkan suatu masalah yang logis.

9.2 Kelemahan dan kelebihan fungsi recursive :

·         Kelemahan

-          Memakan memori yang lebih besar, karena setiap kali bagian dirinya dipanggil, dibutuhkan sejumlah ruang memori tambahan.

-          Mengorbankan efisiensi dan kecepatan

-          Problem: rekursi seringkali tidak bisa “berhenti” sehingga memori akan terpakai habis dan program bisa hang.

-          Program menjadi sulit dibaca.

• Kelebihan

-          Karena program lebih singkat dan ada beberapa kasus yang lebih mudah menggunakan fungsi yang rekursif.

Definisi recursif

         Ada kalanya kita mengalami kesulitan untuk mendefinisikan suatu obyek secara eksplisit. Mungkin lebih mudah untuk mendefinisikan obyek tersebut dengan menggunakan dirinya sendiri. Ini dinamakan sebagai proses rekursif. Kita dapat mendefinikan barisan, fungsi dan himpunan secara rekursif.

Barisan yang didefinisikan secara rekursif

Contoh:

Barisan bilangan pangkat dari 2

an = 2n untuk n = 0, 1, 2, … .

Barisan ini dapat didefinisikan secara rekursif:

a0 = 1

an+1 = 2an     untuk  n = 0, 1, 2, …

Langkah-langkah untuk mendefinisikan barisan secara rekursif:

1. Langkah basis: Spesifikasi anggota awal.
2. Langkah rekursif: Berikan aturan untuk membangun anggota baru dari anggota yang telah ada.

Contoh barisan yang didefinisikan secara rekursif :

Berikan definisi rekursif dari an=rn, dengan rÎN, r≠0 dan n bilangan bulat positif.

Solusi:

Definisikan a0=r0=1

dan an+1=r . an untuk n = 0, 1, 2, …

Fungsi yang didefinisikan secara rekursif :

Langkah-langkah untuk mendefinisikan fungsi dengan domain bilangan cacah:

1. Langkah basis: Definisikan nilai fungsi pada saat nol.
2. Langkah rekursif: Berikan aturan untuk mencari nilai fungsi untuk setiap bilangan bulat berdasarkan nilai fungsi pada bilangan bulat yang lebih kecil.    

Definisi seperti itu disebut rekursif atau definisi induktif.

Contoh fungsi yang didefinisikan secara rekursif

f(0) = 3

f(n + 1) = 2f(n) + 3

Maka

f(0) = 3

f(1) = 2f(0) + 3 = 2×3 + 3 = 9

f(2) = 2f(1) + 3 = 2×9 + 3 = 21

f(3) = 2f(2) + 3 = 2×21 + 3 = 45

f(4) = 2f(3) + 3 = 2×45 + 3 = 93

Himpunan yang didefinisikan secara rekursif

Langkah-langkah dalam mendefinisikan suatu himpunan secara rekursif:

1. Langkah basis:

                  Spesifikasi koleksi awal dari anggota

2. Langkah rekursif:

                  Mendefinisikan aturan konstruksi anggota baru dari anggota yang telah diketahui

Contoh himpunan yang didefinisikan secara rekursif

Misalkan S didefinisikan secara rekursif oleh:

3 Î S

(x+y) Î S jika x Î S dan y Î S

Maka S adalah himpunan bilangan bulat positif yang habis dibagi 3.

Bukti:

Misalkan A himpunan yang beranggotakan semua bilangan bulat positif yang habis dibagi 3.

Untuk membuktikan bahwa A = S, harus ditunjukkan

A Í S and S Í A.

Bagian I: Akan dibuktikan A Í S, yaitu menunjukkan bahwa setiap bilangan bulat positif yang habis dibagi 3 ada di S (dengan menggunakan induksi matematika).

9.3 Percobaan Praktikum

9.3.1 Buat flowchart & program untuk memberikan solusi masalah menara Hanoi menggunakan fungsi recursive (Hanoi.cpp)

Langkah dan Flowchart Menara Hanoi :

Gambar 9.1 Flowchart menara hanoi

Output Program :

Gambar 9.1 Fungsi rekursive

Source Code :

#include "stdio.h"

#include "math.h"

#include "conio.h"

int n;

char awal='A';

char akhir='C';

char mid='B';

void menara(char awal,char akhir,char mid,int n)

{

if (n==1)

printf("pindahkan balok ke-%d dari %c ke %c\n",n,awal,akhir);

else

{

menara(awal,mid,akhir,n-1);

printf("pindahkan balok ke-%d dari %c ke %c\n",n,awal,akhir);

menara(awal,mid,akhir,n-1);

}

}

void main()

{

int jum;

printf ("Masukkan banyak balok n : ");

scanf ("%d",&n);

fflush (stdin);

menara(awal,akhir,mid,n);

jum=pow(2,n)-1;

printf("\n>>jumlah perpindahannya adalah : %d", jum);

printf("\n\n\n");

getchar ();

}

9.2.2 Buat program untuk menampilkan segitiga pascal menggunakan fungsi recursive (pascal.cpp)

Output Program :

Gambar 9.2 Segitiga Pascal

Source Code :

#include"stdio.h"

#include"conio.h"

main(){

int i,j,n;

ok:

printf("=======================SEGITIGA PASCAL VERSI BINTANG=========================");

printf("\t\t\n\nmasukan jumlah angka segitiga pascal : ");

scanf("%d",&n);

for(i=0;i<n;i++){

for(j=0;j<n-i;j++)

printf(" ");

for(j=0;j<2*i+1;j++)

printf("*");

printf("\n"); }

printf("\n");

goto ok;

getch();}

BAB X

HASH TABLE

10.1 Definisi Hash Table dan Struktur Hash table

Hash Table adalah seluruh struktur data yang terdiri dari table dan fungsi yang bertujuan untuk menentukan nilai kunci yang unik untuk setiap record menjadi angka (hash) lokasi record tersebut dalam sebuah table.

Struktur hash table adalah menggunakan struktur data array assosiatif yang mengasosiasikan record dengan sebuah field kunci berupa bilangan (hash yang merupakan representasikan dari record tersebut).

10.2Keunggulan struktur Hash Table dibandingkan dengan struktur table biasa

waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

10.3 Struktur Gambar Hash Table dengan menggunakan link list

 

Gambar 10.1 Struktur hash table

10.4 Metode-metode yang di gunakan Hash Table :

1.      Open Address : Teknik penyimpanan dalam hash tabel yang membutuhkan memory yang sangat besar.

Gambar 10.2 Metode open address

2. Linear Probing : Dengan menambahkan suatu interval pada hasil yang diperoleh dari fungsi hash sampai ditenukan lokasi yang belum terisi.

Gambar 10.3 Metode linear probing

3. Quadrat Probing / Squared probing : Hanpir samadengan linear probing, tetapi haasil yang dieroleh dari fungsi hash di tambahkan dengan kuadrat dari interval yang digunakan.

Gambar 10.4 Metode quadrat probing / squared probing

4.      Double Probing : Teknik penyimpanan  dalam tabel hash diman jika terjadi collisin, lokasi selanjutnya adalah lokasi sekarang + h (k).

Gambar 10.5 Metode double probing

10.5 Program dengan menggunakan Hash Table

Source Code :

#include <iostream.h>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

//using std::cout;

//using std::cin;

int Hash(int,int);

int HashAdd(int [],int,int);

int main()

{

   int size;

   int number;

   int hashNumber;

   int coll,say,toplam;

   say=0;

   toplam=0;

   coll=1;//collision yoksa 1

     cout<<" ===================>>>>>>>Program Fungsi Hash Table==============";

   cout<<" \t\t\nMasukkan ukuran tabel hash=";

   cin>>size;

   cout<<"\nMenghitung nilai acak..\n";

   int table[1000]={0};

   srand(time(NULL));

   while (coll==1)

   {

        number=rand()%size+1;

        cout<<"-"<<number<<"-";

        hashNumber=Hash(number,size);

        coll=HashAdd(table,hashNumber,number);

        toplam=toplam+hashNumber;

        say=say+1;

   }

   cout<<"\nMenghitung Nilai atas = "<<(toplam-hashNumber);

   cout<<"\nMenghitung jumlah= "<< (say-1);

   cout<<"\nrata-rata = ";

   cout<<(float)(toplam-hashNumber)/(say-1)<<"\n";

   return 0;

}

int Hash(int number, int HashTableSize)

{

return (number % HashTableSize);

}

int HashAdd(int Table[],int HashNum, int num)

{

   if (Table[HashNum]==0)

   {

        Table[HashNum]=num;

        return 1;//collison yok

   }

   else

   {

    return 2;//collision var

   }

}

10.6 Percobaan Praktikum

10.6.1 Buat contoh program dengan menggunakan Hash Table

Output Program :

Gambar 10.1 Program menggunakan Hash Table

Source Code :

#include <iostream.h>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

//using std::cout;

//using std::cin;

int Hash(int,int);

int HashAdd(int [],int,int);

int main()

{

   int size;

   int number;

   int hashNumber;

   int coll,say,toplam;

   say=0;

   toplam=0;

   coll=1;//collision yoksa 1

     cout<<" ===================>>>>>>>Program Fungsi Hash Table==============";

   cout<<" \t\t\nMasukkan ukuran tabel hash=";

   cin>>size;

   cout<<"\nMenghitung nilai acak..\n";

   int table[1000]={0};

   srand(time(NULL));

   while (coll==1)

   {

        number=rand()%size+1;

        cout<<"-"<<number<<"-";

        hashNumber=Hash(number,size);

        coll=HashAdd(table,hashNumber,number);

        toplam=toplam+hashNumber;

        say=say+1;

   }

   cout<<"\nMenghitung Nilai atas = "<<(toplam-hashNumber);

   cout<<"\nMenghitung jumlah= "<< (say-1);

   cout<<"\nrata-rata = ";

   cout<<(float)(toplam-hashNumber)/(say-1)<<"\n";

   return 0;

}

int Hash(int number, int HashTableSize)

{

return (number % HashTableSize);

}

int HashAdd(int Table[],int HashNum, int num)

{

   if (Table[HashNum]==0)

   {

        Table[HashNum]=num;

        return 1;//collison yok

   }

   else

   {

    return 2;//collision var

   }

}