struktur data

1

Struktur Data Universitas Pamulang Teknik Informatika

Disusun Oleh

Kussigit Santosa

2


Jl. Surya Kencana No. 1 Pamulang Telp (021)7412566, Fax. (021)7412566 Tangerang Selatan – Banten

PERTEMUAN I

STRUKTUR DATA Bobot : 4 SKS Prasyarat :

Sistim Digital PTI Algoritma dan Pemrograman

Perkuliahan:

24 kali pertemuan di kelas 2 kali Ujian (UTS dan UAS)

Penilaian :

Kehadiran : 10% Tugas : 20% UTS : 30% UAS : 40%

3


Apa itu Struktur Data ?

ALGORITMA Deskripsi langkah‐langkah penyelesaian masalah yang tersusun secara logis

1. Ditulis dengan notasi khusus 2. Notasi mudah dimengerti 3. Notasi dapat diterjemahkan menjadi sintaks suatu bahasa pemrograman

CONTOH

ALGORITMA

1. Mencari nilai maksimum 2. Mengurutkan data 3. Mencetak bilangan ganjil dari 1 – 19 4. Menyimpan data mahasiswa baru 5. Mencetak data absensi 6. Mengirim email berdasarkan jadual…. 7. DLL

PROGRAM

STRUKTUR DATA

4


Contoh Algoritma Mencetak Absensi 1. Buka Data Absensi 2. Tentukan Mata Kuliah 3. Tentukan Kelas 4. Tentukan Format Absensi (4 / 14 kolom) 5. Tentukan banyak pencetakan 6. Ambil data mhs ke‐1, lalu cetak 7. Ulangi langkah ke‐6 sampai data habis

STRUKTUR DATA Model logika/matematik yang secara khusus mengorganisasi data

• Struktur Data Statis – array/larik , rekord, himpunan. • Struktur Data Dinamis ‐ list/senarai, queue /antrian /giliran, tumpukan /stack

/timbunan, pohon, graf. DEFINISI DATA Data : Fakta atau kenyataan yang tercatat mengenai suatu obyek

Pengertian data ini menyiratkan suatu nilai yang bisa dinyatakan dalam bentuk konstanta atau variabel

Konstanta menyatakan nilai yang tetap Variabel digunakan dalam program untuk menyatakan nilai yang dapat diubah‐ubah selama eksekusi berlangsung

EMPAT ISTILAH TENTANG DATA

TIPE DATA : macam/isi data didalam suatu variabel

OBYEK DATA : Himpunan dari elemen,

misal : x himpunan bilangan integer REPRESENTASI DATA :

Suatu mapping dari struktur data d kesuatu himpunan struktur data e, misal : boolean direpresentasikan dalam 0 dan 1

STRUKTUR DATA : koleksi dari variabel yang dinyatakan dengan sebuah nama, dengan sifat setiap variabel dapat memiliki tipe yang berlainan. Struktur data biasa dipakai untuk mengelompokkan beberapa informasi yang berkaitan menjadi sebuah kesatuan

5


HIRARKI TIPE DATA

REVIEW C/C++ PERINTAH OUTPUT Bentuk Umum : cout<<“Keterangan”<<variabel<<endl;

Out put ( Tampilan pada monitor )

#include<iostream> using namespace std; void main( ) { int BIL; BIL = 100; cout <<”Nilai Bilangan BIL adalah ………………. : “<< BIL<< endl; }

Nilai Bilangan BIL adalah ………………. : 100

6


PERINTAH INPUT Bentuk Umum : cin>>variabel; Hasilnya :

#include<iostream> using namespace std; void main( ) { int BIL; cout <<”Masukkan Nilai Bilangan BIL ………………. : “<< endl; cin>>BIL; }

#include<iostream> using namespace std; void main( ) { Char nama[20]; cout <<”Masukkan nama anda : “;cin>>nama ; cout<<”Nama saya adalah ……………: “<< nama<< endl; }

Masukkana nama anda : Gustav Stevani Nama saya adalah …………… : Gustav Stevani

7


PERTEMUAN 2 ( DATA TERSTRUKTUR) TIPE DATA TERSTRUKTUR 1. String

Data yang berisi sederetan karakter dimana banyaknya karakter bisa berubah‐ubah sesuai dengan kebutuhan

// contoh program #include<iostream> using namespace std; void main( ) { int I ; char N[8] = “JAKARTA” ; for(i=0;i<=7 ; i ++) cout<<”N[ “<< i<<”]“<< “= “ << N[i]<< endl; }

8


2. Larik(Array)

Array adalah variabel yang mampu menyimpan sejumlah nilai yang bertipe sama.

9


3. Record/Struktur

Terdiri dari beberapa variabel yang terstruktur dan masing‐masing variabel bisa mempunyai tipe yang berbeda.

struct mahasiswa {

char *nama; char *nim; int uts,uas; float akhir; char grade;

} 4. Set ‐> Union

Berbeda dengan struktur, anggota dari union menggunakan secara bersama‐sama ruang penyimpanan memori yang sama.

// contoh program #include<iostream> using namespace std; union BilBulat { unsigned int bInt; unsigned char cKar[4];

}; void main(void) {

BilBulat Bilangan; Bilangan.bInt=0x56782233; cout<<"bInt : "<<hex<<Bilangan.bInt<<endl; cout<<"cKar[0] : "<<hex<<int(Bilangan.cKar[0])<<endl; cout<<"cKar[1] : "<<hex<<int(Bilangan.cKar[1])<<endl; cout<<"cKar[2] : "<<hex<<int(Bilangan.cKar[2])<<endl; cout<<"cKar[3] : "<<hex<<int(Bilangan.cKar[3])<<endl;

} Hasilnya : bInt : 56782233 cKar[0] : 33 cKar[1] : 22 cKar[2] : 78 cKar[3] : 56

10


5. Set ‐> Enumerasi

Merupakan himpunan dari konstanta integer yang diberi nama. #include<iostream> using namespace std;

6. File

Merupakan organisasi dari sejumlah record sejenis. Masing‐masing record dapat terdiri dari satu atau beberapa field dan setiap field terdiri dari satu atau beberapa karakter

7. PROGRAM

Kumpulan instruksi‐instruksi yang ditulis dengan aturan tertentu yang dimengerti oleh komputer untuk melaksanakan suatu tugas.

11


PERTEMUAN III ( Statemen elementer dan kendali) PROGRAM

STATEMEN ELEMENTER 1. Assignment(penugasan)

Untuk memberikan nilai ke variabel yang telah dideklarasikan Bil = 3;

2. Compariason Untuk keperluan pengambilan keputusan. Diperlukan operator relasi sebagai berikut : >, <, >=, <=, ==, !=

Contoh : A = 5 dan B = 2

C=(A < B); cout<< C; Hasilnya = 1 Sehingga :

Kumpulan instruksi-instruksi yang ditulis dengan aturan tertentu yang dimengerti oleh komputer untuk melaksanakan suatu tugas.

12


3. Arithmetic Statement

4. Operasi Boolean/logika : menghubungkan ungkapan relasi yang hasilnya true atau false.

Operator : && (dan), || (atau), ! (not)

#include<iostream> using namespace std;

5.Operasi Input/Output

Operator cin, cout Standard Input : Keyboard Standard Output : Screen

13


A. OPERASI KONTROL

1. Alternatif : if, if – else, switch

2. Pengulangan : do – while, while, for

14


3. Percabangan

LATIHAN



15


KOREKSILAH KESALAHAN PROGRAM DIATAS

16


PERTEMUAN IV

ARRAY (LARIK) Array adalah suatu struktur yang terdiri dari sejumlah elemen yang memiliki tipe data yang sama. Elemen‐elemen array tersusun secara sekuensial/ urut dalam memori komputer. Array dapat berupa satu dimensi, dua dimensi, tiga dimensi ataupun banyak dimensi (multi dimensi). Array Satu Dimensi Array Satu dimensi tidak lain adalah kumpulan elemen‐elemen identik yang tersusun dalam satu baris. Elemen‐elemen tersebut memiliki tipe data yang sama, tetapi isi dari elemen tersebut boleh berbeda. Bentuk umum:

tipe_data nama_var_array [ukuran]; tipe_data : menyatakan jenis tipe data elemen larik (int, char, float, dll) nama_var_array : menyatakan nama variabel yang dipakai. ukuran : menunjukkan jumlah maksimal elemen larik.

INISIALISASI Menginisialisasi array sama dengan memberikan nilai awal array pada saat didefinisikan. int nilai[10] = {23,34,32,12,25,14,23,12,11,10};

PENGAKSESAN nama_var_array [indeks]; Pengisian dan pengambilan nilai pada indeks tertentu dapat dilakukan dengan mengeset nilai atau menampilkan nilai pada indeks yang dimaksud. Pengaksesan elemen array dapat dilakukan berurutan atau random berdasarkan indeks tertentu secara langsung. Contoh : Sebuah array A[4] menyimpan data tipe int

17


Jum elemen array = 4 elemen Panjang array = 4 elemen * 4 byte/elemen = 16 byte Contoh Soal : 1.Suatu array dideklarasikan dengan A[9], setiap elemen terdiri dari 8 byte. Jika alamat elemen pertama sama dg 16FFH, ditanyakan : a.Jumlah elemen array b.Panjang array dalam byte c.Alamat A[5]

Jawab : 1. &A[0] = 16FFH Lebar elemen = 8 byte/elemen a. Jumlah elemen array = 9 elemen b. Panjang array = 9 elemen x 8 byte/elemen = 72 byte c. &A[5] = ?

Perpindahan = (5 – 0) elemen x 8 byte/elemen = 40 byte = 28H byte &A[5] = 16FFH + 28H = 1727H

Soal : 1.Suatu array dideklarasikan dengan int Angka[12]. Jika alamat elemen pertama 2C3EH, ditanyakan : a.Jumlah elemen array b.Jumlah byte seluruhnya (panjang array) c.Alamat Angka[6]

2. Array 2D

Deklarasi A[I]{J] I : Jumlah baris J : Jumlah kolom Urutan elemen dalam memori :

18


Urutan baris per baris ( Row Major Order/RMO) A[3][4]

0 1 2 3 0 1 2 3 4 1 5 6 7 8 2 9 10 11 12

Urutan kolom per kolom (Column Major Order/CMO) A[3][4] 0 1 2 3 0 1 4 7 10 1 2 5 8 11 2 3 6 9 12

Contoh : int A[3][4]

A. Jika matrik diatas disimpan dengan urutan RMO, maka :

17 14 75 10 20 50 80 11 35 60 90 12Baris 0 Baris 1 Baris 2

Tipe data int memerlukan 4 byte/elemen. &A[0][1]=1004H, &A[0][2]=1008H, &A[0][3]=100CH &A[1][0]=1010H, &A[1][1]=1014H, &A[1][2]=1018 &A[1][3]=101B, &A[2][0]=1020, &A[2][1]=1024 B. Jika matrik disimpan dengan urutan CMO, maka: 17 20 35 14 50 60 75 80 90 10 11 12Kolom 0 Kolom 1 Kolom 2 Kolom 3

&A[1][0]=1004H, &A[2][0]=1008H, &A[0][1]=100BH &A[1][1]=1010H, &A[2][1]=1014H

19


Penyelesaian tanpa melihat gambar : a. Jika matrik diatas disimpan dengan urutan RMO, maka : Jumlah elemen/baris = 4 elemen/baris Ditanya : &A[2][1] Diketahui : &A[0][0] _ 2 1 Pindah baris = 2 baris x 4 elemen/baris = 8 elemen Pindah kolom = 1 kolom = 1 elemen Total perpindahan = 8 + 1 = 9 elemen = 9 elemen x 4 byte/elemen = 36 byte = 24H byte Jadi &A[2][1] = 1000H + 24H = 1024H b. Jika matrik diatas disimpan dengan urutan CMO, maka : Jumlah elemen/kolom = 3 elemen/kolom Ditanya : &A[2][1] Diketahui : &A[0][0] _ 2 1 Pindah kolom = 1 kolom x 3 elemen/kolom = 3 elemen Pindah baris = 2 baris = 2 elemen Total perpindahan = 3 + 2 = 5 elemen = 5 elemen x 4 byte/elemen = 20 byte = 14H byte Jadi &A[2][1] = 1000H + 14H = 1014H Soal : Diketahui suatu array 2D yang dideklarasikan dengan int A[6][7]. Alamat elemen pertama 10CCH. Ditanyakan : a.Jumlah elemen b.Jumlah byte seluruhnya c.Alamat A[2,5] (Penempatan dlm memori secara RMO dan CMO) 3. Array 3D Diketahui array A[2][3][3] dengan lebar elemen 2 byte. Alamat elemen pertama 1000H. Ditanya &A[1][2][1]? Jawab : 0 1 2 0 1 2 0 10 30 50 0 50 12 171 25 15 17 1 24 22 372 32 35 36 2 46 11 18 Blok 0 Blok 1 a.RMO Jumlah elemen tiap baris = 3 elemen/baris Jumlah elemen tiap bolk = 9 elemen/blok

20


Ditanya : &A[1][2][1] Diketahui : &A[0][0][0] _ 1 2 1 Pindah kolom = 1 kolom = 1 elemen Pindah baris = 2 baris x 3 elemen/baris = 6 elemen Pindah blok = 1 blok x 9 elemen/blok = 9 elemen Total perpindahan = 1 + 6 + 9 = 16 elemen x 2 byte/elemen = 32 byte = 20H byte Jadi &A[1][2][1] = 1000H + 20H = 1020H b. CMO Jumlah elemen tiap kolom = 3 elemen/kolom Jumlah elemen tiap bolk = 9 elemen/blok Ditanya : &A[1][2][1] Diketahui : &A[0][0][0] _ 1 2 1 Pindah kolom = 1 kolom x 3 elemen/kolom = 3 elemen Pindah baris = 2 baris = 2 elemen Pindah blok = 1 blok x 9 elemen/blok = 9 elemen Total perpindahan = 3 + 2 + 9 = 14 elemen x 2 byte/elemen = 28 byte = 1CH byte Jadi &A[1][2][1] = 1000H + 1CH = 101CH Soal : Diketahui suatu array 3D yang dideklarasikan dengan int A[4][3][6]. Alamat elemen pertama adalah CBBDH. Ditanyakan :

a. Jumlah elemen b. Jumlah byte seluruhnya c. &A[2][2][4]

Contoh 1. #include <iostream> using namespacestd; void main ( ) { int billy [ ] = {16, 2, 77, 40, 12071}; int n, result=0; for ( n=0 ; n<5 ; n++ ) { result += billy[n]; } cout<<result); }

21


Contoh 2. #include <iostream> using namespacestd; void main ( ) { int A [5]={20,9,1986,200,13},n; cout<<"Data yang lama”<<endl; for (n=0;n<5;n++) { cout<<A[n]; } cout<<endl; cout<<"Data yang baru :"<<endl; A[0]=4; A[1]=2; A[2]=1; A[3]=3; A[4]=5; for (n=0;n<5;n++) { cout<< A[n]; } } TUGAS

1. Buatlah kesimpulan dari masing‐masing program diatas. 2. Buatlah program untuk menentukan nilai terkeci dan terbesar

22


PERTEMUAN V LANJUTAN ARRAY dimensi 1 Array adalah suatu struktur yang terdiri dari sejumlah elemen yang memiliki tipe data yang sama. Elemen‐elemen array tersusun secara sekuensial/ urut dalam memori komputer. Array dapat berupa satu dimensi, dua dimensi, tiga dimensi ataupun banyak dimensi (multi dimensi). Array Satu Dimensi Array Satu dimensi tidak lain adalah kumpulan elemen‐elemen identik yang tersusun dalam satu baris. Elemen‐elemen tersebut memiliki tipe data yang sama, tetapi isi dari elemen tersebut boleh berbeda. /*Program Mencari bilangan Terkecil dan terbesar di dalam array */ #include<iostream> Using namespace std;

Output : Nilai maksimum : 76 Nilai minimum : 12 TUGAS :

1. Jelaskan konsep program tersebut diatas 2. Buatlah kesimpulan dari program diatas.

23


PERTEMUAN VI (Array Dimensi Dua ) TUJUAN : Agar mahasiswa memahami cara penjumlahan, pengurangan dan perkalian matriks menggunakan Array dimensi 2 TEORI : Array dua dimensi sering digambarkan sebagai sebuah matriks, tabel yang merupakan perluasan dari array satu dimensi. Jika array satu dimensi hanya terdiri dari sebuah baris dan beberapa kolom elemen, maka array dua dimensi terdiri dari beberapa baris dan beberapa kolom elemen yang bertipe sama sehingga dapat digambarkan sebagai berikut: Tabel Data penjualan per tahun

Bentuk umum: <tipe data> NamaArray [indeks_1][indeks_2]; Indeks_1 : menyatakan jumlah baris Indeks_2 : menyatakan jumlah kolom

Contoh: Tabel diatas dapat dituliskan kedalam array dimensi 2 sebagai berikut : Int data_jual [3][7]; bool papan[2][2] = { {true,false},{true,false} }; Elemen array dua dimensi diakses dengan menuliskan kedua indeks elemennya dalam kurung siku seperti pada contoh berikut: //papan nama memiliki 2 baris dan 5 kolom

bool papan[2][5]; papan[0][0] = true; papan[0][4] = false; papan[1][2] = true; papan[1][4] = false;

no Tahun penjualan

2001 2002 2003 2004 2005 2006 2007 1 45 43 65 12 21 12 21 2 32 34 23 56 54 34 45 3 11 12 32 23 56 76 45

24


CONTOH : // array dimensi dua #include<iostream> #include<iomanip.h> Using namespace std; Void main() {

Int i,j; Int data_jual[4][4]; for(i=1;i<=3; i++) {

for(j=1;j<=3; j++) { cout<<”Data ke ‐ “ << i<< “, “<<j<<endl; cout<<”Jumlah Penjualan : “; cin>>data_jual[i][j]; }

} cout << “ NO 2001 2002 2003”<<endl; cout<<”‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐“<<endl; for(i=1;i<=3; i++) {

cout<<setiosflags(ios::left)<<setw(5)<<i; for(j=1;j<=3; j++) {

cout<<setiosflags(ios::right)<<setw(4)<<i; cout<<data_jual[i][j]; cout<<” “ ;

} cout<<endl;

} cout<<”‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐“<<endl; getchar();

} Output ? TUGAS :

1. ketik dan jalankan 2. Jelaskan dan berikan kesimpulan

25


PERTEMUAN VII POINTER Pointer merupakan tipe data berukuran 32 bit yang berisi satu nilai yang berpadanan dengan alamat memori tertentu. Sebagai contoh, sebuah variabel P bertipe pointer bernilai 0x0041FF2A, berarti P menunjuk pada alamat memori 0041FF2A. Pointer dideklarasikan seperti variabel biasa dengan menambahkan tanda * (asterik) yang mengawali nama variabel.

Bentuk Umum: <tipe data> namaVariabel;

Contoh: float * px; Statement di atas mendeklarasikan variabel px yang merupakan pointer. Penyebutan tipe data float berarti bahwa alamat memori yang ditunjuk oleh px dimaksudkan untuk berisi data bertipe float.

Contoh Program 1

#include<iostream> using namespace std; void main( ) { Int x; Int *px; X=2; px = &x // membaca alamat dari x cout <<”Nilai x ……………………. : “<< x<< endl; cout <<”Nilai *px……………….… : “<<x << endl; cout <<”Nilai px ( alamat x ) ..: “<<px<<endl;

}

26


KELUARANNYA : Program 2. #include<iostream> using namespace std; void main( ) {

Int x[10]={0,1,2,3,4,5,6,7,8,9} Int *px; Int i; for(i=0;i<10;i++) {

px = &x[i] ; // membaca alamat dari x

cout <<x[i] << “ “ <<*px<< “ “<< px<< endl;

}

}

Output nya :

Program 3. #include<iostream> using namespace std;

Output nya

Selamat datang Muhammad Fachrurrozi

27


TUGAS :

1. Tentukan ukuran masing –masing tipe data dasar ( int, unsigned int, float, double, long, char, bool) dan berikan contoh programnya.

2. Tulis alamat masing‐masing variabel yang anda gunakan dalam praktikum

28


PERTEMUAN VIII Struktur TEORI

Structure (struktur) adalah kumpulan elemen‐elemen data yang digabungkan menjadi satu kesatuan. Masing‐masing elemen data tersebut dikenal dengan sebutan field. Field data tersebut dapat memiliki tipe data yang sama ataupun berbeda. Walaupun fieldfield tersebut berada dalam satu kesatuan, masing‐masing field tersebut tetap dapat diakses secara individual. Field‐field tersebut digabungkan menjadi satu dengan tujuan untuk kemudahan dalam operasinya. Misalnya Anda ingin mencatat data‐data mahasiswa dan pelajar dalam sebuah program, Untuk membedakannya Anda dapat membuat sebuah record mahasiswa yang terdiri dari field nim, nama, alamat dan ipk serta sebuah record pelajar yang terdiri dari field‐field nama, nonurut, alamat dan jumnilai. Dengan demikian akan lebih mudah untuk membedakan keduanya. Bentuk umum :

typedef struct nama_struct { tipe_data <nama_var>; tipe_data <nama_var>; .... };

DEKLARASI Ada 2 cara pendeklarasian struct, yaitu : Deklarasi 1:

typedef struct Mahasiswa { char NIM[8]; char nama[50]; float ipk; };

Deklarasi 2 :

struct { char NIM[8]; char nama[50]; float ipk; } mhs;

29


ARRAY OF STRUCT Apabila hendak menggunakan satu struct untuk beberapa kali, ada 2 cara :

1. Deklarasi manual #include <stdio.h>

typedef struct Mahasiswa {

char NIM[8]; char nama[50];

float ipk; };

void main( ) { Mahasiswa a,b,c; …… …… …… }

artinya struct mahasiswa digunakan untuk 3 variabel, yaitu a,b,c

2. Array of struct #include <stdio.h>

typedef struct Mahasiswa {

char NIM[8]; char nama[50];

float ipk; };

void main() { Mahasiswa mhs[3]; …… …… …… } artinya struct mahasiswa digunakan untuk mhs[0], mhs[1], dan mhs[2] Akses data. Untuk menggunakan struktur, tulis nama struktur beserta dengan fieldnya yang dipisahkan dengan tanda titik (“ . “). Misalnya Anda ingin menulis nim seorang mahasiswa ke layar maka penulisan yang benar adalah sebagai berikut:

30


Jika Pmhs adalah pointer bertipe mahasiswa* maka field dari Pmhs dapat diakses dengan mengganti tanda titik dengan tanda panah (“ à “)

Contoh /* Mengisi Biodata dan Nilai IPK mahasiswa */ #include<iostream> Using namespace std ;

Keluarannya

TUGAS

1. Buat struct untuk data buku yang berisi tentang : kode buku, nama buku, tahun terbit, pengarang, dan harga. Gunakan array of struct

2. Buat program menghitung durasi rental warnet, dengan ketentuan perhitungannya: 30 detik = Rp. 130,‐ Satuan waktu : jam : menit : detik

31


PERTEMUAN IX ( STACK ) TUJUAN

‐ Agar mahasiswa memahami metode pengolahan data menggunakan metode stack ‐ Mahasiswa mampu mengurutkan data menggunakan metode pengolahan stack

TEORI: Stack adalah suatu tumpukan DATA . Konsep utamanya adalah LIFO (Last In First Out), DATA yang terakhir masuk dalam stack akan menjadi DATA pertama yang dikeluarkan dari stack Ada dua jenis stack yaitu single stack dan double stack .

I. Single Stack/Stack Tunggal : satu stack dalam satu array. KONDISI STACK

Kosong : Top = ‐1 Bisa Diisi : Top < n‐1

Gambar 1

Ada Isinya: Top > ‐1 Masih Bisa Diisi : Top < n‐1

Gambar 2

Penuh : Top = n ‐ 1 Ada Isinya : Top > n‐1

Gambar 3

32


Ada 4 macam kondisi stack Kondisi Stack Ciri Ilustrasi a b c d

Kosong Penuh Bisa diisi (kebalikan penuh) Ada Isinya (kebalikan kosong)

Top = ‐1 Top = n – 1 Top < n ‐ 1 Top > ‐1

Ganbar 1. Gambar 3 Gambar 1. & 2 Gambar 2 & 3

Proses :

a. AWAL (inisialisasi) b. PUSH (Insert, Masuk, Simpan, Tulis) c. POP (Delete, Keluar, Ambil, Baca/Hapus)

a. Algoritma PUSH

Periksa apakan Top < n – 1

Jika ya, o Naikan Top dengan 1 o Isikan data kedalam elemen yang ditunjuk Top

Jika tidak, o Cetak komentar “Stack Penuh”

if(Top < n – 1) {

S[++Top] = x; } else

Cout<< ”Stack Penuh”; b. Algoritma POP

Periksa apakah Top > ‐1

Jika ya, o Copy data dari elemen yg ditunjuk Top ke suatu variabel

Jika tidak,

o Cetak komentar “Stack kosong”

if(Top > –1) {

x = S[Top‐‐]; } else

33


Cout<< ”Stack Kosong”; Contoh 1. //Program mengurutkan data menggunakan metode stack. #include<iostream> #include<conio.h> using namespace std ; void main ( ) { int SA[20], SB[20],X,I, TOPA,TOPB; TOPA= ‐1; TOPB = ‐1; cin>> X; TOPA++ ; SA[TOPA]=X; for ( I=1 ; I<=9 ; I++)

{ cin>> X; while(TOPA > ‐1 && SA[TOPA] > X)

{ TOPB++; SB[TOPB] = SA[TOPA]; TOPA‐‐;

} TOPA++ SA[TOPA]= X;

While(TOPB> ‐1) {

TOPA++; SA[TOPA] = SB[TOPB]; TOPB‐‐;

}

}

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

Cout<<SA[I]; }

} }

TUGAS :

1. Jelaskan dan buat kesimpulan tentang pengolahan data menggunakan metode stack tersebut diatas

2. Buatlah program yang akan mengisi dan menjumlahkan seluruh isi stack.

34


PERTEMUAN X ( DOUBLE STACK ). 2. Double Stack

Dua stack dalam satu array Dasar stack1 berada pada index terkecil Dasar stack2 berada pada index terbesar

Ilustrasi :

Proses :

a) AWAL(Inisialisasi) b) PUSH1, Push untuk stack1 c) POP1, Pop untuk stack1 d) PUSH2, Push untuk stack2 e) POP2, Pop untuk stack2

a. Fungsi dasar proses AWAL :

void AWAL(void) {

Top1 = ‐1;Top2 = n;

}

b. Fungsi dasar proses PUSH1 : void PUSH1(void) {

S[++Top1] = x;}

c. Fungsi dasar proses POP1 :

void POP1(void) {

x = S[Top1‐‐];}

35


d. Fungsi dasar proses PUSH2 : void PUSH2(void) {

S[‐‐Top2] = x;}

e. Fungsi dasar proses POP2 :

void POP2(void) {

x = S[Top2++];}

Kondisi Stack

Kondisi Stack Ciri1 Stack1 kosong Top1 = ‐1 2 Stack2 kosong Top2 = n 3 Stack Penuh Top2 – Top1 = 1 4 Stack bisa diisi Top2 – Top1 > 1 5 Stack1 ada isinya Top1 > ‐1 6 Stack2 ada isinya Top2 < n

a) Algoritma lengkap proses PUSH1 :

Periksa apakah Top2 – Top1 > 1, a. jika ya :

o Naikan Top1 dengan 1 o Isikan data kedalam elemen yang ditunjuk oleh Top1

b. Jika tidak o Cetak komentar “Stack Penuh”

void PUSH1(void) {

if(Top2 – Top1 > 1) S[++Top1] = x;

else cout<< “Stack Penuh”;

} b) Algoritma lengkap proses POP1 :

Periksa apakah Top1 > ‐1, Jika ya,

o Copy data dari elemen yang ditunjuk Top1 o Turunkan Top1

Jika tidak, o Cetak komentar “Stack Kosong”

36


void POP1(void){

if(Top1 > ‐1) x = S[Top1‐‐] ;

else cout<< “Stack Kosong”;

} c) Algoritma lengkap proses PUSH2 :

Periksa apakah Top2 – Top1 > 1, c. jika ya :

i. Turunkan Top2 dengan 1 ii. Isikan data kedalam elemen yang ditunjuk oleh Top2

d. Jika tidak i. Cetak komentar “Stack Penuh”

void PUSH2(void) {

if(Top2 – Top1 > 1) S[‐‐Top2] = x;

else cout<< “Stack Penuh”;

} d) Algoritma lengkap proses POP2 :

Periksa apakah Top2 < n, Jika ya,

o Copy data dari elemen yang ditunjuk Top2 o Naikan Top2

Jika tidak, o Cetak komentar “Stack Kosong”

void POP2(void) {

if(Top2 < n) x = S[Top2++] ;

else cout<< “Stack Kosong”;

} Soal :

1. Susunlah program untuk menginput data dari keyboard terus menerus hingga stack1 penuh

2. Susunlah program untuk menginput data dari keyboard terus menerus hingga stack2 penuh

3. Susunlah program untuk menghapus stack1 hingga kosong 4. Susunlah program untuk menghapus stack2 hingga kosong

37


PERTEMUAN XI

Queue ( Antrian ) TUJUAN :

‐ Agar mahasiswa mampu memahami konsep pengolahan data dengan menggunakan metode antrian linear

TEORI : Jika diartikan secara harfiah, queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehiduypan 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. Walaupun berbeda implementasi, struktur data queue setidaknya harus memiliki operasi‐operasi sebagai berikut : Queue menggunakan array 1D:

1. Linear Queue (Antrian Lurus) 2. Circular Queue (Antrian Melingkar) 3. Double Ended Queue/Deque (Antrian dengan ujung ganda)

A. ANTRIEN LINEAR. I. Ilustrasi

Misal n= 10

F (Front) : menunjuk pengantri paling depan/siap untuk keluar/ siap untuk dilayani R (Rear) : menunjuk pengantri paling belakang/paling akhir masuk R = 6, artinya :

Pernah masuk 7 pengantri dengan urutan masuk Q[0], Q[1], Q[2], Q[3], Q[4], Q[5], Q[6]

F = 3, artinya : Sudah keluar sebanyak 3 pengantri dengan urutan keluar Q[0], Q[1], Q[2]

II. Prinsip : FIFO(First In First Out) atau

III. Proses :

AWAL (Inisialisasi) INSERT (Sisip, Masuk, Simpan, Tulis) DELETE (Hapus, Keluar, Ambil, Dilayani) RESET (Kembali ke keadaan awal)

38


a) Fungsi dasar untuk proses AWAL :

void AWAL(void) {

F = 0; R = ‐1;

} b) Fungsi dasar proses INSERT :

void INSERT(void) {

if(R < n – 1) Q[++R] = x;

else cout<<”Antrian penuh”;

}

c) Fungsi dasar proses DELETE void DELETE(void) {

if(F < R + 1) {

x = Q[F++]; if(F == n) {

F = 0; R = ‐1;

} } else

cout<<”Antrian kosong”; }

d) Fungsi dasar proses RESET :

void RESET(void) {

F = 0; R = ‐1;

}

39


IV. Kondisi antrian (n : jml elemen array) 1. Kondisi awal

a. F = 0, R = ‐1 kondisi awal b. F = R + 1 antrian kosong c. R < n ‐ 1 antrian bisa diisi

2. Misal masuk 1 pengantri, belum ada yang keluar a. F = 0 belum ada yang keluar b. F < R + 1 antrian ada isinya c. R < n – 1 antrian bisa diisi

3. Misal masuk lagi 5 pengantri, belum ada yang keluar a. R = 5 sudah pernah masuk 6 b. F = 0 belum ada yang keluar c. F < R + 1 antrian ada isinya d. R < n – 1 antrian bisa diisi

4. Misal keluar 5 pengantri

a. F = 5 sudah keluar 5 pengantri b. F = R tinggal 1 pengantri c. F < R + 1 antrian ada isinya d. R < n – 1 antrian bisa diisi

5. Misal keluar lagi satu pengantri a. F = 6 sudah keluar 6 pengantri b. R = 5 c. F = R + 1 antrian kosong d. R < n + 1 antrian bisa diisi

6. Misal masuk lagi 3 pengantri a. F < R + 1 antrian ada isinya b. R < n – 1 antrian masih bisa diisi

40


7. Misal masuk lagi 1 pengantria. F < R + 1 antrian ada isinya b. R = n – 1 antrian penuh

8. Misal keluar 3 pengantri a. F < R + 1 antrian ada isinya b. F = R antrian sisa 1 pengantri c. R = n – 1 antrian penuh

9. Misalkan keluar 1 pengantri

a. F = n semua antrian sudah keluar b. F = R + 1 antrian kosong c. R = n – 1 antrian penuh (disebut penuh) d. F = R + 1 dan R = n – 1 kondisi khusus :

Kosong karena tidak ada isinya Penuh karena tidak bisa diisi Perlu direset(kembali ke posisi awal)

10. Kondisi khusus lainnya :a. Antrian penuh tapi belum ada yang keluar

i. F = 0 belum ada yang keluar ii. R = n – 1 antrian penuh

Kondisi antrian: Kondisi Ciri a Kosong F = R + 1 dimana saja b Penuh R = n – 1 c Bisa diisi R < n – 1 d Ada isinya F < R + 1 e Perlu direset F = R + 1 dan R = n ‐ 1

41


Soal 1. Buatlah suatu program Animasi Antrian dengan 4 buah pilihan : INSERT, DELETE, CETAK

ANTRIAN, QUIT. Jika dipilih INSERT : program akan meminta user untuk menginput sebuah karakter yang

akan dimasukan kedalam antrian Jika dipilih DELETE : maka karakter pertama masuk akan dikeluarkan dari antrian Jika dipilih CETAK ANTRIAN : komputer menampilkan karakter yang ada pada antrian Jika dipilih QUIT : program keluar

42


PERTEMUAN X B. Cicular Queue ( Antrian Melingkar ) TUJUAN :

‐ Agar mahasiswa mampu memahami konsep pengolahan data dengan menggunakan metode antrian melingkar.

‐ Mahasiswa mampu membedakan konsep pengolahan data menggunakan metode antrian linear dan metode antrian melingkar.

TEORI :

I. Representasi

Misal n= 10

atau

Counter : Jumlah pengantri yang ada dalam antrian

F tidak selalu <= R Setelah R dan F sampai ke n‐1, maka tidak direset tetapi melingkar ke 0. II. Prinsip : FIFO(First In First Out) III. Proses :

AWAL (Inisialisasi) INSERT (Sisip, Masuk, Simpan, Tulis) DELETE (Hapus, Keluar, Ambil, Dilayani)

a) Fungsi dasar untuk proses AWAL :

void AWAL(void) {

F = 0; R = ‐1; COUNTER = 0

} b) Fungsi dasar proses INSERT :

void INSERT(void) {

R = (R + 1) % n; Q[R] = x; COUNTER++;

}

void INSERT(void) {

if(COUNTER < n) {

R = (R + 1) % n; Q[R] = x;

43


COUNTER++;} else

cout<<”Antrian penuh”;}

c) Fungsi dasar proses DELETE :

void DELETE(void) {

x = Q[F]; F =(F + 1) % n; COUNTER‐‐;

}

void DELETE(void) {

if(COUNTER > 0) {

x = Q[F]; F = (F + 1) %n; COUNTER‐‐;

} else

cout<<”Antrian kosong”;}

IV. Kondisi antrian (n : jml elemen array). Beberapa kondisi antrian al :

1. Kondisi awal d. F = 0, R = ‐1, COUNTER = 0 kondisi awal e. COUNTER = 0 Antrian kosong

2. Misal masuk 1 pengantri, belum ada yang keluar a. COUNTER > 0 ada isinya b. F = R isinya hanya 1 c. Counter < n masih bisa diisi

3. Misal masuk lagi 3 pengantri, belum ada yang keluara. COUNTER > 0 ada isinya b. F <> R + 1 ada isinya c. COUNTER < n masih bisa diisi

44


4. Misal keluar 1 pengantri

a. COUNTER > 0 ada isinya b. F <> R + 1 ada isinya c. COUNTER < n bisa diisi

5. Misal masuk lagi 3 pengantri a. COUNTER > 0 ada isinya b. F <> R + 1 ada isinya c. COUNTER < n bisa diisi

6. Misal keluar 2 pengantri a. COUNTER > 0 ada isinya b. R <> R + 1 ada isinya c. COUNTER < n bisa diisi

7. Misal keluar lagi 3 pengantri

a. COUNTER > 0 ada isinya b. F = R hanya 1 pengantri c. COUNTER < n bisa diisi

8. Misal keluar lagi 1 pengantri

45


a. COUNTER = 0 antrian kosong b. COUNTER < n bisa diisi

9. Misalkan masuk lagi 3 pengantri a. COUNTER > 0 ada isinya b. COUNTER < n bisa diisi

10. Misal masuk lagi 4 pengantri a. COUNTER > 0 ada isinya b. COUNTER < n bisa diisi

11. Misal masuk lagi 2 pengantri a) COUNTER >0 ada isinya b) F <> R + 1 ada isinya c) COUNTER < n bisa diisi

12. Misal masuk lagi 1 pengantri a) COUNTER > 0 ada isinya b) COUNTER = n antrian penuh

Kondisi antrian: Kondisi Ciri a Kosong COUNTER = 0 b Penuh COUNTER = n c Bisa diisi COUNTER < n

46


d Ada isinya COUNTER > 0 TUGAS : Buatlah suatu program Animasi Antrian Melingkar dengan 4 buah pilihan : INSERT, DELETE, CETAK ANTRIAN, QUIT. Jika dipilih INSERT : program akan meminta user untuk menginput sebuah karakter yang akan dimasukan kedalam antrian Jika dipilih DELETE : maka karakter pertama masuk akan dikeluarkan dari antrian Jika dipilih CETAK ANTRIAN : komputer menampilkan karakter yang ada pada antrian Jika dipilih QUIT : program keluar

47


PERTEMUAN 11. C. Double Ended Queue

I. Representasi

Misal n= 10

Insert Kiri : masuk dari pintu kiri Insert Kanan : masuk dari pintu kanan Delete Kiri : keluar dari pintu kiri Delete Kanan : keluar dari pintu kanan

II. Prinsip : Keluar masuk dari kedua ujung III. Proses :

AWAL (Inisialisasi) INSERT (Sisip, Masuk, Simpan, Tulis) DELETE (Hapus, Keluar, Ambil, Dilayani)

e) Fungsi dasar untuk proses AWAL : void AWAL(void){

L = 0; R = ‐1;

} f) Fungsi dasar proses INSERT KIRI:

void INSERT_KIRI(void){

Q[‐‐L] = x; }

g) Fungsi dasar proses INSERT KANAN:

void INSERT_KANAN(void) {

Q[++R] = x; }

h) Fungsi dasar proses DELETE KIRI:

void DELETE_KIRI(void){

x = Q[L++]; }

48


i) Fungsi dasar proses DELETE KANAN : void DELETE_KANAN(void){

x = Q[R‐‐]; }

IV. Kondisi antrian (n : jml elemen array).

1. Kondisi awal • L = 0, R = ‐1 kondisi awal • L = R ‐ 1 Antrian kosong • L = 0 Penuh kiri • R < n – 1 Bisa insert kanan

2. Misal masuk 1 pengantri dari kanan • L < R + 1 ada isinya • L = 0 penuh kiri • R < n ‐ 1 bisa insert kanan

3. Misal masuk lagi 3 pengantri dari kanan • L < R + 1 ada isinya • L = 0 penuh kiri • R < n ‐ 1 bisa insert kanan

4. Misal keluar 1 pengantri dari kiri • L < R + 1 ada isinya • L > 0 bisa insert kiri • R < n ‐ 1 bisa insert kanan

49


5. Misal masuk lagi 3 pengantri dari kanan • L < R + 1 ada isinya • L > 0 bisa insert kiri • R < n – 1 bisa insert kanan

6. Misal keluar 5 pengantri melalui kiri• L < R + 1 ada isinya • L > 0 bisa insert kiri • R < n – 1 bisa insert kanan • L = R hanya 1 pengantri

7. Misal keluar 1 pengantri melalui kiri • L = R + 1 ada isinya • L > 0 bisa insert kiri • R < n ‐ 1 bisa insert kanan

8. Misal masuk 4 pengantri dari kiri • L < R + 1 ada isinya • L > 0 bisa insert kiri • R < n – 1 bisa insert kanan

9. Misalkan masuk lagi 2 pengantri dari kanan • L < R + 1 ada isinya • L > 0 bisa insert kanan • R < n – 1 bisa insert kanan

10. Misal masuk lagi 1 pengantri dari kanan• L < R + 1 ada isinya • L > 0 bisa insert kiri • R = n – 1 penuh kanan

50


11. Misal masuk lagi 3 pengantri dari kiri • L < R + 1 ada isinya • L = 0 penuh kiri • R = n ‐ 1 penuh kanan

12. Misal seluruh pengantri keluar dari kiri• L = R + 1 antrian kosong • L > 0 bisa insert kiri • R = n – 1 penuh kanan

Kondisi antrian: Kondisi Ciri a Kosong L = R + 1b Penuh kiri L = 0c Penuh kanan R = n ‐1d Bisa diisi dari kiri L > 0e Bisi diisi dari kanan R < n – 1f Ada isinya L < R + 1 V. Fungsi lengkap

a) INSERT KIRI lengkap void INSERT_KIRI(void) {

if(L > 0) {

Q[‐‐L] = x; } else

cout<<”Antrian penuh kiri”;}

51


b) INSERT KANAN lengkap

void INSERT_KANAN(void){

if(R < n ‐ 1) {

Q[++R] = x; } else

cout<<”Antrian penuh kanan”;}

c) DELETE KIRI lengkap

void DELETE_KIRI(void) {

if(L < R + 1) {

x = Q[L++]; } else


d) DELETE KANAN lengkap

void DELETE_KANAN(void){

if(L < R + 1) {

x = Q[R‐‐]; } else


Soal 1. Buatlah suatu program Animasi Double Ended Queue dengan 6 buah pilihan : INSERT KIRI,

INSERT KANAN, DELETE KIRI, DELETE KANAN, CETAK ANTRIAN, QUIT.

52


PERTEMUAN XII. ( Lingked List)

TUJUAN : - Agar mahasiswa memahami konsep penambahan data pada pengolahan data

menggunakan Lingked List TEORI Link List: sejumlah obyek yang dilink/dihubungkan satu dengan lainnya. Obyek : gabungan bebErapa elemen data yg dijadikan satu kelompok/struktur/record Untuk menghubungkan antar obyek perlu variabel tipe pointer yg merupakan salah satu variabel dalam struktur obyek. Ada 4 macam struktur linked list : 1. Linear Singly Linked List 2. Linear Double – Linked List 3. Circular Single – Linked list 4. Circular Double linked List 1. Linear Singly Linked List : Link list lurus dengan pointer tunggal I. Ilustrasi

Ada 4 simpul : 1, 2, 3, 4 Setiap simpul terdiri dari 2 elemen/field, yaitu :

o INFO : bertipe integer o LINK : bertipe pointer

Simpul no.1 : o Field INFO berisi 10 o Field LINK berisi alamat simpul no. 2

Simpul no.1 ditunjuk oleh pointer FIRST Simpul no.4 ditunjuk oleh pointer LAST

Ilustrasi sebuah simpul :

53


Untuk mempersiapkan sebuah linked list maka harus dideklarasikan sebagai berikut : struct SIMPUL {

int INFO; struct SIMPUL *LINK;

}; SIMPUL *P,*Q,*FIRST,*LAST; II. Proses

a. Inisialisasi : persiapan pembuatan linked list b. Membuat simpul awal c. Insert simpul kedalam linked list d. Delete simpul dari linked list

II.1. Inisialisasi FIRST = NULL; LAST = NULL; II.2. Pembuatan simpul Instruksi untuk membuat sebuah simpul : P=(SIMPUL*) malloc(sizeof(SIMPUL));

Fungsi untuk membuat simpul : void BUAT_SIMPUL(int X) {

P=(SIMPUL*) malloc(sizeof(SIMPUL)); if(P!=NULL) {

P‐>INFO=X; } else

cout<<”Pembuatan simpul gagal”;}

Contoh : #include<iostream> #include<stdlib.h> struct SIMPUL{ int INFO; struct SIMPUL *LINK; }; SIMPUL *P,*FIRST,*LAST; void BUAT_SIMPUL(int); using namespace std; void main(void) {

void BUAT_SIMPUL(int x) { P=(SIMPUL *)malloc(sizeof(SIMPUL)); if(P!=NULL) P‐>INFO=x; else cout<<"Pembuatan Simpul Gagal"<<endl; }

54


int x; cout<<"Masukan Data : ";cin>>x; BUAT_SIMPUL(x); cout<<"Data : "<<P‐>INFO<<endl; } II. 3. Pembuatan simpul awal Menjadikan sebuah simpul menjadi simpul awal dari sebuah linked list. Simpul awal ditunjuk oleh pointer FIRST. Fungsi : Void AWAL(void) {

if(FIRST==NULL) {

FIRST=P; LAST=P; P‐>LINK=NULL;

} else

cout<<”Linked List sudah ada””<<endl;} Ilustrasi : Sudah dibuat simpul sbb:

FIRST=P

LAST=P atau LAST=FIRST

P‐>LINK=NULL atau FIRST‐>LINK=NULL atau LAST‐>LINK=NULL

II.4. Insert Kanan Menyisipkan sebuah simpul baru pada ujung kanan linked list. Proses :

- sudah ada linked list - buat simpul baru - sisipkan simpul baru tsb diujung kanan linked list

55


Fungsi : void INSERT_KANAN(void) {

if(LAST!=NULL) {

LAST‐>LINK=P; LAST=P; P‐>LINK=NULL;

} else

cout<<”Linked List belum ada”;} Ilustrasi :

Sudah ada linked list

Buat simpul baru P=(SIMPUL *)malloc(sizeof(SIMPUL));

LAST‐>LINK=P atau FIRST‐>LINK=P

LAST=P atau LAST=FIRST‐>LINK

P‐>LINK=NULL atau LAST‐>LINK=NULL atau FIRST‐>LINK‐>LINK=NULL

II.5. Insert Kiri Menyisipkan sebuah simpul baru pada ujung kiri linked list. Proses :

- sudah ada linked list - buat simpul baru - sisipkan simpul baru tsb diujung kiri linked list

Fungsi : void INSERT_KIRI(void) {

if(FIRST!=NULL) {

P‐>LINK=FIRST; FIRST=P;

}

56


else cout<<”Linked List belum ada”;

} Ilustrasi:


Buat simpul baru P=(SIMPUL *)malloc(sizeof(SIMPUL));

P‐>LINK=FIRST atau P‐>LINK=LAST

FIRST=P

II.6. Insert Tengah Menyisipkan sebuah simpul antara dua buah simpul pada linked list.

setelah diinsert menjadi :

Syarat : simpul no.7 harus sudah ditunjuk oleh pointer Q, caranya : Q=FIRST; For(i=1;i<=6;i++)

Q=Q‐>LINK; Fungsi : Void INSERT_TENGAH(void) {

P‐>LINK=Q‐>LINK; Q‐>LINK=P;

}

57


TUGAS Buat program animasi Linear Singly Linked List untuk mengelola data mahasiswa dengan struktur mahasiswa sbb : NAMA, NIM, GENDER, NILAI STRUKTUR DATA. Program dibuat dalam bentuk menu dengan pilihan : INSERT DATA, , CETAK DATA, EXIT. Ket : INSER DATA : menyisipkan satu simpul pada akhir linked list CETAK DATA : mencetak seluruh isi linked list EXIT : Keluar/selesai Tampilan menu : LIN. SINGLY LINKED LIST ==========================

1. INSERT DATA 2. CETAK DATA 3. EXIT Pilihan (1 – 3) :

58


PERTEMUAN XIII Lanjutan Lingked List

(DELETE) TUJUAN :

- Agar mahasiswa memahami konsep delete pada pengolahan data menggunakan Lingked List

TEORI Link List: sejumlah obyek yang dilink/dihubungkan satu dengan lainnya. Obyek : gabungan bebrapaelemen data yg dijadikan satu kelompok/struktur/record Untuk menghubungkan antar obyek perlu variabel tipe pointer yg merupakan salah satu variabel dalam struktur obyek. II.7. Delete Kanan/Akhir Menghapus simpul yang ada pada linked list paling akhir/kanan. Ilustrasi : sudah ada sebuah linked list

akan dihapus simpul terakhir menjadi :

Syarat agar simpul no.8 dapat dihapus adalah simpul no.7 sudah ditunjuk oleh pointer Q. Caranya : Q = FIRST; while(Q ‐>LINK != LAST)

Q = Q ‐> LINK; Fungsi : void DELETE_KANAN(void) {

free(LAST); LAST = Q; LAST ‐> LINK = NULL;

} Ilustrasi :


59


free(LAST)

LAST = Q

LAST ‐> LINK = NULL

II.8. Delete Kiri/Awal Menghapus simpul yang ada pada linked list paling awal/kiri. Ilustrasi : sudah ada sebuah linked list

akan dihapus simpul awal menjadi :

Fungsi : void DELETE_KIRI(void) {

Q = FIRST; FIRST = Q ‐> LINK; free(Q);

} Ilustrasi :


Q = FIRST

FIRST = Q ‐> LINK

60


free(Q)

Tuliskan cara lain! Tip : Tempatkan Q pada simpulkedua, hapus simpul pertama, pindahkan FIRST ke simpul kedua. II.9. Delete Tengah Menghapus simpul yang ada diantara dua simpul lain. Ilustrasi : sudah ada linked list

simpul no.7 akan dihapus sehingga menjadi :

Syarat agar simpul no.7 bisa dihapus maka simpul no.6 harus sudah ditunjukoleh Q. Caranya : Q = FIRST; For(I = 1; I <= 5; I++)

Q = Q ‐> LINK; Fungsi : void DELETE_TENGAH(void) {

R = Q ‐> LINK; Q ‐> LINK = R ‐> LINK; free(R);

} Ilustrasi :


R = Q ‐> LINK

Q ‐> LINK = R ‐> LINK

free(R)

61


TUGAS : Buat program animasi Linear Singly Linked List untuk mengelola data mahasiswa dengan struktur mahasiswa sbb : NAMA, NIM, GENDER, NILAI STRUKTUR DATA. Program dibuat dalam bentuk menu dengan pilihan : INSERT DATA, HAPUS DATA, CETAK DATA, EXIT. Ket : INSER DATA : menyisipkan satu simpul pada akhir linked list HAPUS DATA :menghapus satu simpul pada akhir linked list CETAK DATA : mencetak seluruh isi linked list EXIT : Keluar/selesai Tampilan menu : LIN. SINGLY LINKED LIST ==========================

1. INSERT DATA 2. HAPUS DATA 3. CETAK DATA 4. EXIT Pilihan (1 – 4) :

62


PERTEMUAN XIV Aplikasi Antrian pada single lingked list TUJUAN ;

- Agar mahasiswa mampu mengaplikasikan dan memahami pengolahan data lingked list yang diperlakukan sebagai antrian.

TEORI :

Proses : FIFO INSERT : selalu Insert Kanan DELETE : selalu Delete Kiri Bila FRONT = REAR artinya antrian tinggal 1 (simpul awal) Bila FRONT = NULL artinya antrian kosong Fungsi‐fungsi yang diperlukan :

1) Deklarasi struktur simpul dan pointer yg diperlukan

struck SIMPUL{ int INFO; struck SIMPUL *LINK;

}; SIMPUL *P,*Q,*FRONT,*REAR;

2) Inisialisasi

FRONT = NULL; REAR = NULL;

3) Fungsi pembuatan Simpul Baru

void BUAT_SIMPUL(int X) {

P=(SIMPUL *)malloc(sizeof(SIMPUL));if(P!=NULL)

P‐>INFO=X; else

63


{ cout<<”Membuat simpul gagal”; exit(1);

} }

4) Fungsi INSERT (Insert Kanan atau BuatAwal)

void INSERT(void) {

if(FRONT==NULL) {

FRONT=P; REAR=P; REAR‐>LINK=NULL;

} else {

REAR‐>LINK=P; REAR=P; REAR‐>LINK=NULL;

} }

5) Fungsi DELETE (Delete Kiri)

Int DELETE(void) {

int X; if(FRONT!=NULL) {

X=FRONT‐>INFO; Q=FRONT‐>LINK; free(FRONT); FRONT=Q; return(X);

} else

cout<<”Queue Kosong”; } TUGAS : Buat program animasi Queue menggunakan Linked List tanpa Head untuk mengelola data mahasiswa dengan struktur mahasiswa sbb : NAMA, NIM, GENDER, NILAI STRUKTUR DATA. Program dibuat dalam bentuk menu dengan pilihan : INSERT DATA, HAPUS DATA, CETAK DATA, EXIT.

64


PERTEMUAN XV Aplikasi Stack pada lingked list TUJUAN :

- Mahasiswa mampu mengaplikasikan teori stack untuk menangani data yang berbentuk lingked list.

TEORI : Ilustrasi untuk STACK tanpa menggunakan simpul Head

PUSH : selalu insert kiri POP : selalu delete kiri Jika TOP‐>LINK=NULL berarti isi stack tinggal satu simpul (simpul pertama) dan bila simpul ini dihapus (POP) maka TOP dibuat sama dengan NULL. Fungsi‐fungsi yang diperlukan :

1) Deklarasi struktur simpul dan pointer yang diperlukan

struck SIMPUL{ int INFO; struck SIMPUL *LINK;

}; SIMPUL *P,*Q,*TOP;

2) Inisialisasi stack

TOP=NULL 3) Fungsi pembuat simpul baru


P=(SIMPUL *)malloc(sizeof(SIMPUL)); if(P!=NULL)

P‐>INFO=X; else

65


{ cout<<”Membuat simpul gagal”; exit(1);

} } 4). Fungsi PUSH (Insert Kiri atau Buat Awal)

void PUSh(void) {

if(TOP==NULL) {

TOP=P; TOP‐>LINK=NULL;

} else {

P‐>LINK=TOP; TOP=P;

} }

1) Inisialisasi stack TOP=NULL

2) Fungsi pembuat simpul baru


P=(SIMPUL *)malloc(sizeof(SIMPUL)); if(P!=NULL)

P‐>INFO=X; else {

cout<<”Membuat simpul gagal”; exit(1);

} }

3) Fungsi PUSH (Insert Kiri atau Buat Awal)

void PUSh(void) {

if(TOP==NULL) {

TOP=P; TOP‐>LINK=NULL;

} else {

66


P‐>LINK=TOP; TOP=P;

} }

1) Fungsi POP (Delete Kiri) int POP(void) {

int X; if(TOP!=NULL) {

X=TOP‐>INFO; Q=TOP‐>LINK; free(TOP); TOP=Q; return(X);

} else

cout<<”Stack kosong”; } TUGAS Buat program animasi Stack menggunakan Linked List tanpa Head untuk mengelola data mahasiswa dengan struktur mahasiswa sbb : NAMA, NIM, GENDER, NILAI STRUKTUR DATA. Program dibuat dalam bentuk menu dengan pilihan : INSERT DATA, HAPUS DATA, CETAK DATA, EXIT.

67


PERTEMUAN XVI ( Linear Double Linked List ) Adalah Linked lurus dengan pointer ganda, yaitu ada dua buah pointer . Jadi dalam struktur simpul ada dua elemen atau field yang bertipe pointer. Yang pertama menunjuk alamat simpul sebelumnya dan yang kedua menunjuk simpul berikutnya.

68


PROSES

69


70


71


INSERT KIRI

72


INSERT TENGAH

73


DELETE KANAN

74


DELETE KIRI

75


DELETE TENGAH Diasumsikan pointer Q sudah menunjuk ke simpul no 7

Buatlah fungsi delete tengah

a. Jika pointer Q menunjuk simpul nomer 8 b. Jika pointer Q menunjuk simpul nomer 9

76


PERTEMUAN XVII A. Circular Single Linked List

Circular Single Linked List adalah singly Linked List dimana link simpul terakhir bukan diisi dengan null, tetapi diisi dengan alamat simpul pertama yaitu simpul yang ditunjuk oleh pointer FIRST, sehingga menciptakan efek melingkar’ sesuai arah jarum jam’. Ilustrasi

PROSES

77


B. CIRCULAR DOUBLY LINKED LIST .

78


ILUSTRASI

PROSES

79


80


PERTEMUAN XVIII TREE ( POHON)

81


82


83


84


85


PERTEMUAN XIX POHON BINER

Pohon biner dengan kedalaman (depth) d =3

86


87


88


Pohon Biner Seimbang ( Balanced Binary Tree)

89


PERTEMUAN XX Penomoran Simpul Pohon Biner

90


Contoh Soal

91


92


93


PERTEMUAN XXI OPERASI PADA POHON BINER

PROSES INISIALISASI

94


PEMBUATAN SEBUAH SIMPUL

Menjadikan sebuah simpul menjadi sebagai simpul akar

Insert sebuah simpul

- Insert urut nomor simpul, atau insert t level per level - Insert pada nomor simpul tertentu

95


Insert urut nomor simpul, atau insert t level per level

96


97


98


99


PERTEMUAN XXII

100


101


102


103


104


105


106


PERTEMUAN XXIV Searching (sequencial dan binary.)

TUUAN - Agar mahasiswa memahami beberapa metode pencarian menggunakan metode

sequencial dan binary. TEORI Teknik pencarian data dari array yang paling mudah adalah dengan cara sequential search, dimana data dalam array dibaca 1 demi satu, diurutkan dari index terkecil ke index terbesar, maupun sebaliknya. Contoh :

int a[5] = {0,3,6,10,1} jika kita ingin mencari bilangan 6 dalam array tersebut, maka proses yang terjadi kita mencari

1. dari array index ke‐0, yaitu 0, dicocokan dengan bilangan yang akan dicari, jika tidak sama, maka mencari ke index berikutnya

2. pada array index ke‐1, juga bukan bilangan yang dicari, maka kita mencari lagi pada index berikutnya

3. pada array index ke‐2, ternyata bilangan yang kita cari ada ditemukan, maka kita keluar dari looping pencarian

contoh :


output :

Metode pencarian yang kedua adalah binary search, pada metode pencarian ini, data harus diurutkan terlebih dahulu. Pada metode pencarian ini, data dibagi menjadi dua bagian (secara logika), untuk setiap tahap pencarian. Algoritma binary search :

107


1. Data diambil dari posisi 1 sampai posisi akhir N 2. Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2 3. Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau

lebih kecil, atau lebih besar? 4. Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah +

1 5. Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1 6. Jika data sama, berarti ketemu.

Contoh source binary search : #include<iostream> using namespace std;

Output :

TUGAS :

1. Buatlah sebuah program yang dapat menerima inputan data kedalam sebuah array. 2. Lanjutan dari nomor 1, gunakan sequensial search untuk mencari sebuah nilai dari

array tersebut, dan gantilah nilainya. 3. Coba gunakan metode pencarian lainnya 4. Buatlah menu untuk program tersebut (1. Sequential search, 2. Binary Search, 3. exit)

108


CONTOH PROGRAM :

#include<iostream> typedef enum (false=0, true=1) bool ; using namespace std ;

109


Output :

Atau ;

struktur data

Documents