fathoni m bahan ajar_if2018_prak.struktur data

Disusun oleh: Fathoni Mahardika

BAHAN AJAR

PENGAJAR : FATHONI MAHARDIKA

SEMESTER : II (Genap)

TEKNIK INFORMATIKA SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER

STMIK SUMEDANG 2011

Praktek Struktur Data


LEMBAR PENGESAHAN

JUDUL : BAHAN AJAR

TOPIK BAHAN AJAR : Praktikum Struktur Data

NAMA : FATHONI MAHARDIKA, S.Kom

NIP/NIK : 0416068401

SUMEDANG, 27 JANUARI 2012

Mengetahui :

KETUA STMIK SUMEDANG,

Dady Mulyadi, Drs., M.M.

NIK. 00010001

Pembimbing,

PEMBANTU KETUA I,

Dwi Yuniarto, Sos., M.Kom.

NIK. 05010020


BAHAN AJAR

SESSI/PERKULIAHAN KE 1

I. Buku / bacaan wajib (bw) 1. Algoritma dan Pemrograman EDISI 3 (Rinaldi Munir;2004)

2. Algoritma dan Struktur Data dengan C# (Adi Nugroho;2009)

3. Anonim, Algoritma dan Pemrograman II, Penerbit Gunadarma, Jakarta, 1990

4. Moh. Sjukani, Algoritma dan Struktur Data dengan C, C++, dan Java, Mitra

Wacana Media, 2005

5. Dwi Sanjaya, Asyiknya Belajar Struktur Data di Planet C++, PT. Elex Media

Komputindo, Jakarta, 2005

6. Abdul Kadir, Pemrograman Turbo PASCAL untuk IBM PC Versi 5.0 dan 5.5, Penerbit PT. Elex Media Komputindo, Jakarta

Tujuan Instruksional Khusus :

Pada akhir pertemuan ini anda diharapkan mampu : 1. Memahami silabus, sap mata kuliah praktikum struktur data

2. Memahami dasar hubungan algoritma dengan struktur data

3. Mengenal dan memahami dasar struktur data

Pokok Bahasan :

Pengenalan Praktikum Struktur Data

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari ruang lingkup, memahami dasar

hubungan algoritma dengan struktur data, serta kategori materi struktur data secara garis besar

yang merupakan pembelajaran lanjutan dari praktikum algoritma dan pemrograman pada

semester sebelumnya.

TujuanInstruksionalUmum

Pada akhir pertemuan ini mahasiswa diharapkan mampu :

Memahami sistem pengorganisasian data pada memori komputer dan file (berkas) pada

media penyimpanan.

Mengimplementasikannya dalam program dengan menggunakan salah satu bahasa

(Bahasa C/Pascal) untuk membuat berbagai macam struktur data (array, tree, struct)

dengan teknik-teknik tertentu (linked list, stack, dan queue) serta manipulasinya (sorting

dan searching) secara baik, efisien, dan cepat.


Pengantar Struktur Data Bagaimana cara mengatasi masalah implementasi program dengan komputer?

1. Pemahaman masalah secara menyeluruh dan persiapan data

2. Keputusan operasi-operasi yang dilakukan terhadap data

3. Penyimpanan data-data pada memori sehingga tersimpan dan terstruktur

secara logis, operasinya efisien

4. Pengambilan keputusan terhadap bahasa pemrograman mana yang

paling cocok untuk jenis data yang ada

Perbedaan Tipe data, Objek data, dan Struktur Data

1. Tipe data adalah jenis data yang mampu ditangani oleh suatu bahasa

pemrograman pada komputer.

2. Tiap-tiap bahasa pemrograman memiliki tipe data yang memungkinkan:

3. Deklarasi terhadap variabel tipe data tersebut

4. Menyediakan kumpulan operasi yang mungkin terhadap variabel bertipe

data tersebut

5. Jenis obyek data yang mungkin

6. Contoh tipe data di C? Java? Pascal? .NET?


BAHAN AJAR






Wacana Media, 2005





Pada akhir pertemuan ini anda diharapkan mampu : 1. Memahami konsep fungsi, dan kegunaan array dalam bahasa C++/Pascal

2. Memahami konsep fungsi, dan kegunaan struct dalam bahasa C++/Pascal

3. Membuat program sederhana sebagai solusi atas suatu masalah tertentu yang di dalamnya

menggunakan array dan struct

4.

Pokok Bahasan :

Pengenalan Struktur Data

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan array

dalam bahasa C/Pascal, mempelajari fungsi dan kegunaan struct, membuat program sederhana

yang di dalamnya terdapat array dan struct yang merupakan pembelajaran lanjutan dari

praktikum algoritma dan pemrograman pada semester sebelumnya.




media penyimpanan.

Mengimplementasikannya dalam program dengan menggunakan salah satu bahasa





ARRAY

Array adalah suatu tipe data terstruktur yang berupa sejumlah data sejenis (bertipe

data sama) yang jumlahnya tetap dan diberi suatu nama tertentu.

Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-dimensi.

DEKLARASI

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.

Contoh :

Int nilai[6];

INISIALISASI

Menginisialisasi array sama dengan memberikan nilai awal array pada saat

didefinisikan. int nilai[6] = {8,7,5,6,4,3};

Contoh diatas berarti berarti anda memesan tempat di memori komputer sebanyak

6 tempat

dengan indeks dari 0-5, dimana indeks ke-0 bernilai 8, ke-1 bernilai 7, dst, dan

dimana semua elemennya bertipe data integer.

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 :

#include <stdio.h>

void main ()

{ int billy [] = {16, 2, 77, 40, 12071};

int n, result=0;

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

{

result += billy[n];

}

printf("%d",result);

}


Contoh : #include <stdio.h>

#include <conio.h>

void main ()

{ int A [5]={20,9,1986,200,13},n,edit;

clrscr();

printf("Data yang lama\n");

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

{

printf("%i ",A[n]);

}

printf("\nData yang baru : \n");

A[0]=4;

A[1]=2;

A[2]=1;

A[3]=3;

A[4]=5;

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

{

printf("%i ",A[n]);

}

}

Contoh :

#include <stdio.h>

#include <conio.h>

void main ()

{ int A [5]={20,9,1986,200,13},n;

clrscr();


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

{

printf("%i ",A[n]);

}


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

{

printf("%i ",A[n]);

}

}

Contoh :

#include <stdio.h>

#include <conio.h>

void main ()

{ int A [5]={20,9,1986,200,13},n,hapus;

clrscr();


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


{

printf("%i ",A[n]);

}

printf("data yang ingin dihapus : ");

scanf("%i",&hapus);


for (n=hapus-1;n<5-1;n++)

{

A[n]=A[n+1];

}

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

{

printf("%i ",A[n]);

}

}

LATIHAN

1. Buatlah fungsi untuk array 1 dimensi untuk ADD, EDIT, DELETE, dan

VIEW.

STRUCT

Bentuk struktur data yang dapat menyimpan variabel-variabel dalam 1

nama, namun memiliki tipe data yang berbeda ataupun sama. Variable-

variabel tersebut memiliki kaitan satu sama yang lain.

Bentuk umum :

typedef struct nama_struct{

tipe_data <nama_var>;

tipe_data <nama_var>;

....

};

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;


contoh #include <stdio.h>

#include <iostream.h>

void main()

{

struct orang

{

char nama[40];

short umur;

}saya;

printf("nama : ");

cin.getline(saya.nama,40);

printf("umur :" );

scanf("%i",&saya.umur);

printf("%s berumur %i",saya.nama,saya.umur);

}

ARRAY OF STRUCT

Apabila hendak menggunakan 1 struct untuk beberapa kali, ada 2 cara :

1. Deklarasi manual


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


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]


#include <iostream.h>

#include <conio.h>

typedef struct orang

{

char nama[30];

short umur;

};

void main()

{

orang saya[5];

int i,x;

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

{

printf("nama ke-%i : ",i+1);

cin.getline(saya[i].nama,30);

printf("umur ke-%i : ",i+1);

scanf("%i",saya[i].umur);

printf("%s berumur %i",saya[i].nama,saya[i].umur);

}

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

{

printf("nama %s berumur %d",saya[x].nama,saya[x].umur);

}

}

LATIHAN

1. Buat struct untuk data buku yang berisi tentang : kode buku, nama buku,

tahun terbit, pengarang, dan harga. Gunakan array of struct.

2. Buatlah fungsi untuk soal no 1, agar dapat dimanipulasi untuk ADD,

EDIT, HAPUS, dan TAMPIL

3. Cari 2 contoh kasus lain disekitar anda yang dapat menggunakan struct,

selain KTP, KTM, SIM, buku.


BAHAN AJAR






Wacana Media, 2005





Pada akhir pertemuan ini anda diharapkan mampu : 1. Memahami konsep fungsi, dan kegunaan Searching array dalam bahasa C++/Pascal

2. Memahami konsep fungsi, dan kegunaan Sequential Search, Binary Search, Interpolation Search,

Array Eclipse/Explode dalam bahasa C++/Pascal

3. Membuat program sederhana sebagai solusi atas suatu masalah tertentu yang di dalamnya

menggunakan array dan struct

4.

Pokok Bahasan :

Searching Array

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan Searching

array dalam bahasa C/Pascal, mempelajari fungsi dan kegunaan Sequential Search, Binary

Search, Interpolation Search, Array Eclipse/Explode membuat program sederhana yang di

dalamnya terdapat Searching Array yang merupakan pembelajaran lanjutan dari praktikum

algoritma dan pemrograman pada semester sebelumnya.




media penyimpanan.

Mengimplementasikannya dalam program dengan menggunakan bahasa pemrograman





SEARCHING ARRAY

Sesuai dengan judulnya, dalam modul ini kita akan membahas proses pencarian /

searching data pada suatu array / barisan data. Jika diketahui ada sebuah array /

barisan data bernama A yang menampung 10 data yang bertipe integer sbb

A={1,2,3,4,8,5,7,9,6,0} dan kita diberi tugas untuk mencari beberapa data misal:

Jika data yang akan dicari dalam array A adalah 6, maka dengan cepat dapat

kita ketahui bahwa data 6 ada dalam array A pada index ke-9 (index pada

array dimulai dari 0)

Sedangkan jika data yang akan dicari dalam array A adalah 12, maka dapat

disimpulkan bahwa array A tidak memiliki data 12 tersebut.

Nah, kita sudah memahami proses pencarian data yang sederhana tersebut dalam

pikiran kita, sekarang permasalahannya adalah bagaimana

mengimplementasikannya kedalam program ?

Pada umumnya dikenal dua metode searching antara lain : Sequensial search dan

binary search, Untuk lebih memahami kedua metode ini lebih baik kita mulai dari

metode yang paling sederhana terlebih dahulu yaitu sequensial search.

Sequensial search

Disebut juga sebagai metode pencarian urut adalah metode pencarian yang paling

mudah. Bayangkan saja jika anda dihadapkan pada sebuah rak buku, dan anda

diberi tugas untuk mencari sebuah buku dari rak tersebut. Sudah tentu anda akan

mulai mencarinya satu – persatu entah itu dari atas atau dari bawah sampai buku

yang dimaksud ketemu.

Singkatnya sequential search memiliki proses sebagai berikut:

Tentukan banyaknya data yang akan di olah, missal banyak data adalah N.

Tentukan data apa yang akan dicari, missal data yang akan dicari adalah C.

Deklarasikan sebuah counter untuk menghitung banyak data yang ditemukan,

missal counternya adalah K.

Inisialisasikan K =0

Lakukanlah perulangan sebanyak N kali


Dalam tiap proses perulangan tersebut periksalah apakah data yang sedang

diolah sama dengan data yang dicari.

Jika ternyata sama K=K+1

Jika tidak, lanjutkan proses perulangan .

Setelah proses perulangan berhenti, periksalah nilai K.

Jika nilai K lebih dari 0, artinya data yang dicari ada dalam data /array dan

tampilkan nilai K ke layer sebagai jumlah data yang ditemukan.

Jika nilai K=0, artinya data yang dicari tidak ditemukan dalam data / array dan

tampilkan ke layar bahwa data tidak ditemukan

Proses selesai.

Dapat disimpulkan bahwa sequential search, akan mencari data dengan cara

membandingkannya satu-persatu dengan data yang ada. Prosesnya tentu saja

akan singkat jika data yang diolah sedikit, dan akan lama jika data yang diolah

banyak. Disarankan proses ini digunakan pada jumlah data yang sedikit saja.


Coding Program Sequential Search untuk dicoba

GAMBARAN KERJA

Pada program diatas jumlah data yang akan diolah berjumlah 10 data dan

disimpan kedalam array A[10] yang bejenis integer, array index[10] digunakan

untuk mencatat index pada array A dimana data ditemukan daya tampung array

sama dengan array A karena ada kemungkinan data yang akan dicari adalah

#include<stdio.h>

void main()

{

//deklarasi variabel

int A[10],index[10], i,j,k;

//proses penginputan data

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

{

printf("Data ke-%d:",i+1);

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

}

//memasukkan data yang akan dicari ke dalam K

printf("Masukkan data yang akan anda cari:");

scanf("%d",&k);

//proses pencarian data

j=0;

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

{

if(A[i]==k)

{

index[j]=i;

j++;

}

}

//jika data ditemukan dalam array

if (j>0)

{

printf("Data %d yang dicari ada %d buah\n",k,j);

printf("Data tersebut terdapat dalam index ke :");

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

{

printf(" %d ",index[i]);

}

printf("\n");

}

//jika tidak ditemukan

else

{

printf("Data tidak ditemukan dalam array\n");

}

}


semua data yang ada dalam array A. sedangkan variable I digunakan sebagai

counter dalam proses perulangan, variable j digunakan sebagai counter untuk

menghitung jumlah data yang ditemukan dan variable k digunakan untuk

menyimpan data yang akan dicari.

Proses pertama adalah memasukkan data-data yang akan diolah ke dalam array A

dan data yang akan dicari ke dalam variable K. setelah itu akan dilakukan

perulangan sebanyak data yang ada dalam array A untuk mencari apakah ada data

dalam variable K didalam array A, jika ada maka counter j akan mencatat

jumlahnya dan array index akan mencatat pada index ke berapa data tersebut

ditemukan. Setelah proses perulangan selesai, tampilkanlah hasil yang terdapat

pada variable j dan array index ke layer.

Gambaran kerja program (Perhatikan koding diatas agar lebih jelas)

Misalkan pada perulangan yang pertama kita masukkan data sebagai berikut:

Array A (berisi data yang akan diolah)

ISI 1 3 5 8 6 5 7 11 9 0

INDEX 0 1 2 3 4 5 6 7 8 9

Data yang akan dicari K=5

Proses pencarian / proses perulangan yang kedua

Array A (berisi data yang akan diolah)

ISI 1 3 5 8 6 5 7 11 9 0

INDEX 0 1 2 3 4 5 6 7 8 9

Data ditemukan ketika i = 2

Maka K++ menjadi 1, artinya ada 1 data dalam array A

Array index akan menyimpan index tempat data tersebut ditemukan pada array A

Array index (berisi index data yang ditemukan pada array A)


ISI 2

INDEX 0 1 2 3 4 5 6 7 8 9

Data ditemukan ketika i = 5

Maka K++ menjadi 2, artinya ada 2 data dalam array A

Array index akan menyimpan index tempat data tersebut ditemukan pada array A

Array index (berisi index data yang ditemukan pada array A)

ISI 2 5

INDEX 0 1 2 3 4 5 6 7 8 9

Proses pencarian data selesai dan tampilkan hasil output

Data 5 yang dicari ada 2 buah ambil dari variable K

Data tersebut terdapat dalam index ke: 2 5 ambil dari array index.

Binary search

Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang

sudah diurutkan terlebih dahulu. Jika terdapat N buah data yang akan dolah, data

yang dicari akan dibandingkan dengan data ke-N jika data ke-N lebih besar dari

data yang dicari maka akan dilakukan pembagian data menjadi dua bagian.

Kemudian ujung data pada setiap bagian dibandingkan lagi dengan nilai yang

akan dicari.


Coding Program Binary Search untuk dicoba

#include<stdio.h>

void main()

{

//deklarasi variabel

int A[10], i,j,k,tkr,top,bottom,middle,tm;


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

{

printf("Data ke-%d:",i+1);

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

}


scanf("%d",&k);

//proses pengurutan data

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

{

for(j=i+1;j<10;j++)

{

if (A[i]>A[j])

{

tkr=A[i];

A[i]=A[j];

A[j]=tkr;

}

}

}


tm=0;

top=9;

bottom=0;

while(top>=bottom)

{

middle=(top+bottom)/2;

if(A[middle]==k)

{

tm++;

}

if(A[middle]<k)

{

bottom=middle+1;

}

else

{

top=middle-1;

}

}

if (tm>0)

{

printf("Data %d yang dicari ada dalam array\n",k);

}


else

{

printf("Data tidak ditemukan dalam array\n");

}

}


Contoh kasus:

Ada 12 data 11 13 15 18 23 27 29 31 54 58 59 61

Data yang akan dicari : 13

Proses 1

11 13 15 18 23 27 29 31 54 58 59 61 lebih besar dengan data yg akan

dicari , lakukan pembagian data

Proses 2

11 13 15 18 23 27 lebih besar dari data yang dicari, bagi 2 29 31 54 58

59 61

Proses 3

11 13 15 lebih besar dari data yang dicari, bagi 2 18 23 27 29 31 54 58

59 61

Proses 4

11 lebih kecil dari data yang dicari, abaikan saja 13 15 lebih besar

dari data yang dicari, bagi 2 18 23 27 29 31 54 58 59 61

Proses 5

11 13 sesuai data yang dicari 15 lebih besar dari data yang

dicari 18 23 27 29 31 54 58 59 61

Dari proses diatas dapat disimpulkan bahwa binary search akan membagi-

bagi sekumpulan data menjadi 2 bagian sampai data yang dicari ditemukan.

Kesimpulan

Sequential search lebih efektif jika digunakan pada sekumpulan data yang sedikit,

sedangkan binary search efektif jika digunakan pada sekumpulan data yang

berjumlah banyak.

Sequential search dapat digunakan pada sekumpulan data yang urut ataupun tidak

urut, sedangkan binary search harus pada data yang sudah urut.


Interpolation search

Proses pencarian data ini hampir sama dengan proses pencarian binary search,

pencarian ini juga dilakukan pada kumpulan data yang sudah urut. Akan tetapi

jika pada binary search kita membagi data menjadi 2 bagian tiap prosesnya, pada

interpolation search kita akan membagi data menurut rumus sebagai berikut:

Posisi = ( kunci – data[low] / data[high] – data[low] ) * ( high – low ) + low

Singkatnya proses pencarian interpolation search hampir mirip dengan proses

pencarian kata dikamus, yaitu kita mencari data yang dimaksud dengan cara

memperkirakan letak data.

Misal terdapat data sebagai berikut:

Kode Judul Buku Pengarang

025 The C++ Programming James Wood

034 Mastering Delphi 6 Marcopolo

041 Professional C# Simon Webe

056 Pure JavaScript v2 Michael Bolton

063 Advanced JSP & Servlet David Dunn

072 Calculus Make it Easy Gunner Christian

088 Visual Basic 2005 Express Antonie

096 Artificial Life : Volume 1 Gloria Virginia

Kunci Pencarian ? 088

Low ? 0

High ? 7

Posisi = (088 - 025) / (096 - 025) * (7 - 0) + 0 = [6]

Kunci[6] = kunci pencarian, data ditemukan : Visual Basic 2005

Kunci Pencarian ? 060

Low ? 0

High ? 7

Posisi = (060 – 025) / (096 – 025) * (7 – 0) + 0 = [3]

Kunci[3] < kunci pencarian, maka teruskan


Low = 3 + 1 = 4

High = 7

Ternyata Kunci[4] adalah 063 yang lebih besar daripada 060.

Berarti tidak ada kunci 060.

Coding Program Interpolation Search untuk dicoba

#include<stdio.h>

void main()

{

//deklarasi variable

int A[10], i,j,k,tkr,low,high,pos,tm;


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

{

printf("data ke-%d:",i+1);

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

}

//Input data yang akan dicari


scanf("%d",&k);

//proses pengurutan data

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

{

for(j=i+1;j<10;j++)

{

if (A[i]>A[j])

{

tkr=A[i];

A[i]=A[j];

A[j]=tkr;

}

}

}


tm=0;

high=9;

low=0;

do

{

pos = ((k - A[low]) / (A[high] - A[low]))*(high-low) + low;

if (A[pos] == k)

{

tm++;

break;

}

if (A[pos] > k)

high = pos-1;

else

if (A[pos] < k)

low = pos + 1;

}

while(k >= A[low] && k <= A[high]);

if (tm>0)

{

printf("data %d yang dicari ada dalam array\n",k);

}


else

{

printf("data tidak ditemukan dalam array\n");

}

}


Array Splice/Explode

Secara harafiah, dapat diartikan sebagai metode untuk memecah-mecah array.

Pemecahan array itu sendiri, tergantung berdasarkan apa array akan dipecah. Agar

lebih jelas, lihat ilustrasi array splice pada gambar berikut :

Char P A K A N T O N

Indeks 0 1 2 3 4 5 6 7 8

Char P A K A N T O N

Indeks1 0 0 0 1 1 1 1 1

Indeks2 0 1 2 0 1 2 3 4

Ada pemecahan dari array of character 1 dimensi menjadi array of character 2

dimensi berdasarkan spasi pada inputan stringnya.

Coba coding array explode dan searchingnya berikut ini :


#include <stdio.h>

#include <string.h>

void main()

{

char str[100],cari[100];

char hasil[100][100];

int n,i,j,t,a,b,c,d,e;

printf("Masukkan string: ");

gets(str);

n=strlen(str);

j=0;

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

{

if (i!=(n-1))

{

if(str[i]==32)

j++;

}

else if(i==(n-1))

j++;

}

t=0;

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

{

e=0;

for(a=t;a<n;a++)

{

if(str[a]!=32)

{

hasil[i][e]=str[a];

printf("Indeks [%d][%d] =

%c\n",i,e,hasil[i][e]); //untuk melihat hasil splice

e++;

}

else

{

t=a+1;

break;

}

}

printf("\n");

}

printf("Kata yang ingin dicari : ");

gets(cari);

b=strlen(cari);

printf("Panjang kata cari %i\n",b);

c=-1;

d=0;

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

{

t=e=0;

for(a=0;a<n;a++)

{

if(hasil[i][a]<=0 && cari[e]<=0)

break;

else

{

if(cari[e]==hasil[i][a])

t++;

}

e++;

}

if(t==b)

{

c=i;

break;

}

}

if(c!=-1)

{

printf("Kata %s yang dicari ada di indeks [%d][%d] sampai

[%d][%d]\n",cari,c,0,c,a-1);

}

else

printf("Kata tidak ada dalam string!\n");

}


Pengembangan:

Soal:

Buat array rekening bank dengan ketentuan :

- Gunakan Struct (int no_rek, char nama[100], long saldo)

Buatlah fungsi-fungsi sebagai berikut :

- Add

- Edit

- Cari (Sequential)

- Setor

- Ambil

- Transfer

- Tutup Rekening (Delete)

Ganti coding program diatas agar array yang ada bisa ditentukan ukurannya oleh

user (array dinamis) [gunakan template program yang telah ada]

Buat menu searching untuk menggabungkan ketiga metode searching tersebut.

Dibuat dalam bentuk fungsi!

Buat array explode untuk memecah input NIM menjadi seperti berikut:

Input = 22053752

Output = 22 05 3752 (dipisah berdasarkan kode jurusan, angkatan dan nomor

mahasiswa)


BAHAN AJAR

SESSI/PERKULIAHAN KE 4 - 5





Wacana Media, 2005




Pada akhir pertemuan ini anda diharapkan mampu : 1. Memahami konsep penggunaan Sorting Array dalam bahasa C++/Pascal

2. Memahami konsep fungsi dan kegunaan Bubble sort, Exchange sort, Selection sort,

Insertion sort, Quick Sort

3. Membuat program sederhana sebagai solusi atas suatu masalah tertentu yang di

dalamnya menggunakan Sorting Array

4.

Pokok Bahasan :

Sorting Array

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan Sorting

array dalam bahasa C/Pascal, mempelajari Memahami konsep fungsi dan kegunaan Bubble sort,

Exchange sort, Selection sort, Insertion sort, Quick Sort.. membuat program sederhana yang di

dalamnya terdapat Sorting Array yang merupakan pembelajaran lanjutan dari praktikum

algoritma dan pemrograman pada semester sebelumnya.




media penyimpanan.






SORTING ARRAY Sorting

Salah satu bagian penting dari struktur data adalah proses pengurutan data-

data itu sendiri. Data akan terkadang akan berada dalam bentuk yang tidak

berpola ataupun dengan pola tertentu yang tidak kita inginkan, namun dalam

penggunaanya, kita akan selalu ingin menggunakan data-data tersebut dalam

bentuk yang rapi atau berpola sesuai dengan yang kita inginkan. Maka dari itu

proses sorting adalah proses yang sangat penting dalam struktur data, terlebih

untuk pengurutan data yang bertipe numerik ataupun karakter.

Sorting adalah proses menyusun kembali data yang sebelumnya telah

disusun dengan suatu pola tertentu ataupun secara acak, sehingga menjadi

tersusun secara teratur menurut aturan tertentu.

Pada umumnya ada 2 macam pengurutan, yaitu:

o Pengurutan secara ascending (urut naik).

o Pengurutan secara descending (urut turun).

Algoritma untuk melakukan sorting juga ada berbagai macam, antara lain:

o Teoretis : Computational complexity theory, Big O notation,

Total order, Stability, Comparison sort.

o Exchange sorts : Exchange sort, Bubble sort, Cocktail sort, Comb

sort, Gnome sort, Quick sort.

o Selection sorts : Selection sort, Heap sort, Smooth sort.

o Insertion sorts : Insertion sort, Shell sort, Tree sort, Library sort,

Patience sorting.

o Merge sorts : Merge sort.

o Non-comparison : Radix sort, Bucket sort, Counting sort, Pigeonhole

sort.

o Others : Topological sorting, Sorting network.

Algoritma-algoritma ini tentu saja akan mempunyai efek yang berbeda

dalam setiap prosesnya, ada yang mudah digunakan, ada yang mempunyai proses

yang sangat cepat, dan sebagainya.

Pemilihan algoritma untuk sorting ini tidak hanya asal saja dipilih.

Pemilihian ini semestinya berdasarkan kebutuhan yang diperlukan. Tidak semua

algortima yang pendek itu buruk dan tidak semua algoritma yang super cepat juga

akan baik dalam semua kondisi. Misal: algoritma Quick Sort adalah algoritma

sorting yang tercepat dalam proses pencariannya, namun jika data yang akan

diurutkan ternyata sudah hampir terurut atau tidak terlalu banyak, maka algoritma

ini malah akan memperlama proses pengurutan itu sendiri, karena akan banyak

perulangan tidak perlu yang dilakukan dalam proses sorting ini.

Hal yang umum dilakukan dalam proses sorting adalah proses pertukaran

antara 2 elemen atau lebih (analogi memindah air dalam gelas). Untuk melakukan

proses pertukaran akan diperlukan adanya variable baru yang digunakan sebagai

variable penampung.


//fungsi penukar data

void tukar (int a[], int I, int j) {

int tampung = a[i];

a[i] = a[j];

a[j] = tampung;

}

Sorting Algorithm

o Bubble Sort

Metode sorting paling mudah, namun paling lambat

dibandingkan dengan yang lain.

Bubble sort mengurutkan data dengan cara membandingkan

elemen sekarang dengan elemen berikutnya.

Bisa dilakukan baik dari kepala array maupun ekor array.

Proses yang berlangsung, jika:

Ascending: jika elemen sekarang lebih besar daripada

elemen berikutnya, maka kedua elemen tersebut

ditukar.

Descending: jika elemen sekarang lebih kecil daripada

elemen berikutnya, maka kedua elemen tersebut

ditukar.

Hal ini akan terlihat seperti penggeseran angka, perbandingan,

kemudian jika memenuhi syarat kemudian tukar.

Proses penukaran ini akan terus dilakukan hingga seluruh array

telah diperiksa.

Contoh fungsi bubble sort:

//Bubble Sort

void bubble (int a[], int n) {

int i,j;

for (i=n;i>=1;i--) {

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

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

tukar (a,j-1,j);

}

}

o Exchange Sort

Mirip dengan bubble sort.


Perbedaannya: dalam exchange sort ada elemen yang berfungsi

sebagai pusat (pivot), pertukaran hanya akan dilakukan jika

diperlukan saja dari pivot tersebut.

Sedangkan bubble sort akan membandingkan elemen

pertama/terakhir dengan elemen sebelumnya/sesudahnya,

kemudian elemen sebelum/sesudahnya itu akan menjadi pusat

(pivot) untuk dibandingkan dengan elemen

sebelumnya/sesudahnya lagi, begitu seterusnya.

Contoh fungsi exchange sort:

//Exchange Sort

void exchange (int a[], int n) {

int i,j;

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

for (j=(i+1);j<n;j++)

if(a[i]>a[j])

tukar (a,i,j);

}

}

o Selection Sort

Kombinasi sorting dan searching.

Untuk setiap proses, akan dilakukan dengan mencari elemen

dari posisi yang belum diurutkan dan kemudian memilih

elemen yang memiliki nilai terkecil atau terbesar yang akan

ditukarkan ke posisi yang tepat di dalam array.

Misalnya untuk putaran pertama, akan dicari data dengan nilai

terkecil dan data ini akan ditempatkan pada indeks terkecil,

pada putaran kedua akan dicari data kedua terkecil, dan akan

ditempatkan di indeks kedua, negitu seterusnya hingga tidak

ada data yang dicari lagi.

Selama proses, pembandingan dan pengubahan hanya

dilakukan pada indeks pembanding saja, pertukaran data secara

fisik terjadi pada akhir proses.

Contoh fungsi selection sort:

//Selection Sort

void selection (int a[],int n) {

int i,j,pos;

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

pos=i;

for (j=i+1;j<=n;j++)

if(a[j]<a[pos])

pos=j;

tukar(a,pos,i);

}

}


o Insertion Sort

Analogi pengurutan kartu.

Proses dilakukan dengan membandingkan data ke-I dengan

data yang sebelum-sebelumnya.

Misal ascending: pengurutan dimulai dari data ke-2 sampai

dengan data terakhir, jika ditemukan data yang lebih kecil,

maka akan dimasukkan di posisi yang seharusnya.

Pada penyisipan elemen, maka elemen-elemen lain akan

bergeser ke belakang.

Contoh fungsi insertion sort:

//Insertion Sort

void insertion (int a[],int n) {

int i,j,v;

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

v=a[i];

j=1;

while (a[j-1]>v) {

a[j]=a[j-1]

j--;

a[j=v];

}

}

o Quick Sort

Bersifat divide&conquer.

Merupakan metode pencarian yang sangat cepat (saat ini

tercepat).

Pertama-tama deret dibagi menjadi dua bagian, misal, semua

elemen pada bagian b (bagian pertama) mempunyai kurang dari

atau sama dengan semua elemen pada bagaian c (bagian kedua

-- membagi). Kemudian kedua bagian tersebut dilakukan

proses sorting dengan rekursif secara terpisah dengan prosedur

yang sama(coquer). Kemudian gabungkan lagi kedua bagian

terpisah tersebut.


Langkah:

Memilih sebuah elemen pembanding (pivot), misal x.

Semua elemen dari deret tersebut yang kurang dari x

diletakkan pada bagian pertama.

Kemudian semua elemen dari yang lebih besar dari x

diletakkan pada bagian kedua.

Untuk elemen yang sama dengan x bias diletakkan di

mana saja bahkan bisa juga di antara kedua bagian

tersebut.

Algoritma partisi:

Input : sequence a0, ..., an-1 with n elements

Output : permutation of the sequence such that all elements

a0, ..., aj are less than or equal to all elements ai, ..., an-1 (i > j)

Method : choose the element in the middle of the sequence as

comparison element x

let i = 0 and j = n-1

while i j

search the first element ai which is greater than or

equal to x

search the last element aj which is less than or equal to

x

if i j

exchange ai and aj

let i = i+1 and j = j-1


setelah mempartisi, prosedur sorting akan dilakukan secara

rekursif. Hingga proses rekursif tersebut akan berhenti saat

sebuah bagian hanya tinggal terdapat satu elemen saja.

Tidak baik digunakan jika elemen-elemen yang akan diurutkan

hanya ada sedikit atau sudah hamper terurut, karena jika

menggunakan metode ini justru akan melakukan perulangan

yang tidak berguna dan lama.

Mempunyai algoritma dan program yang cukup kompleks.

Contoh fungsi quick sort:

//Quick Sort

void quicksort (int a[],int l,int r) {

int i,j,v;

if(r>1) {

v=a[r];i=l-1;j=r;

for(;;) {

while(a[++i]<v);

while(a[--j]>v);

if(i>=j)

break;

tukar(a,i,j)

}

tukar(a,i,r);

quicksort(a,l,i-1);

quicksort(a,i+1,r);

}

}

Pengembangan:

o Dari potongan-potongan fungsi sorting di atas, buatlah sebuah program

yang dapat menampilkan semua hasil sorting dalam berbagai versi!

o Dari program tersebut tambahkanlah bagian program yang dapat

menampilkan proses sorting yang sebenarnya terjadi (tidak hanya hasil

akhirnya saja)! Sehingga Anda pun akan lebih mudah memahami

proses yang terjadi dalam suatu sorting…

o Buat program yang dapat mengurutkan sebuah urutan alphabet!

Soal:

o Buat program dengan inputan NIM (empat digit terakhir), nama, dan

fakultas untuk beberapa mahasiswa, kemudian lakukan sorting

terhadap inputan berdasarkan NIMnya!

o Buat sebuah program database pabrik, merk, CC dan harga sepeda

motor kemudian hasil tersebut bisa diurutkan berdasarkan harga dan

CCnya (secara ascending dan descending)!

Misal:

Yamaha >> Mio >> 135CC >> 12.000.000

Honda >> Revo >> 100CC >> 13.000.000

Viar >> ViarX >> 125CC >> 7.000.000


BAHAN AJAR






Wacana Media, 2005





Pada akhir pertemuan ini anda diharapkan mampu : 1. Memahami konsep penggunaan stack dalam bahasa C++/Pascal


dalamnya menggunakan stack

Pokok Bahasan :

Array Stack

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan Stack

dalam bahasa C/Pascal. membuat program sederhana yang di dalamnya terdapat Stack yang

merupakan pembelajaran lanjutan dari praktikum algoritma dan pemrograman pada semester

sebelumnya.




media penyimpanan.






ARRAY STACK

STACK

STACK atau TUMPUKAN adalah suatu struktur data yang seolah-olah terlihat

seperti data yang tersusun secara „menumpuk‟, dimana ada data yang terletak

diatas data yang lainnya.

Bersifat LIFO (Last In First Out), berarti data yang masuk terakhir akan keluar

pertama.

Operasi pada Stack :

IsFull mengecek apakah STACK sudah penuh

IsEmpty mengecek apakah STACK sudah kosong

Push menambah data pada STACK pada tumpukan paling atas

Pop mengambil data pada STACK pada tumpukan paling atas

Tampil mencetak semua data dalam tumpukan

Contoh program untuk dicoba:

#include <stdio.h>

#include <conio.h>

//deklarasi 'STACK' dengan struct dan array

typedef struct STACK

{

int data[5];

int atas;

};

//deklarasi variabel 'tumpuk' dari struct

STACK tumpuk;

void main()

{

clrscr();

int pilihan,baru,i;

//inisialisasi awal

tumpuk.atas=-1;

do

{

clrscr();

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

printf("2.Pop Data\n");

printf("3.Print Data\n");

printf("\nPilihan = ");

scanf("%i",&pilihan);

switch(pilihan)

{

case 1:

{

if(tumpuk.atas==5-1)

{

printf("Tumpukan penuh");


getch();

}

else

{

printf("Data yang akan di-push

= ");

scanf("%d",&baru);

tumpuk.atas++;

tumpuk.data[tumpuk.atas]=baru;

}

break;

}

case 2:

{

if(tumpuk.atas==-1)

{

printf("Tumpukan kosong");

getch();

}

else

{

printf("Data yang akan di-pop =

%d", tumpuk.data[tumpuk.atas]);

tumpuk.atas--;

getch();

}

break;

}

case 3:

{

if(tumpuk.atas==-1)

{

printf("Tumpukan kosong");

getch();

}

else

{

printf("Data = ");

for(i=0; i<=tumpuk.atas; i++)

{

printf("%d

",tumpuk.data[i]);

}

getch();

}

break;

}

default:

{

printf("\nTidak ada dalam pilihan");

}

}

}while(pilihan>=1 && pilihan<=3);

getch();

}


JAWABLAH!

- Kapan tumpukan dinyatakan kosong?

- Kapan tumpukan dinyatakan penuh?

- Bagaimana cara untuk mengosongkan semua data dalam tumpukan (CLEAR)?

SOAL LATIHAN

1. Ubahlah contoh program stack diatas dalam bentuk fungsi-fungsi yang terpisah

dari program utama (fungsi IsFull, IsEmpty, Push, Pop, Tampil)!

2. Buatlah program kalkulator sederhana (pengoperasian 2 bilangan aritmatika

sederhana)!

Operasi aritmatika tersebut (dalam notasi infiks), harus diubah kedalam bentuk

notasi postfiks.

Contoh:

INFIKS POSTFIKS

3 + 7 3 7 +

2 – 9 2 9 -

8 * 7 8 7 *

9 / 3 9 3 /

Misal algoritma: 3 7 +

indeks stack Process

2 + Add

1 7 push operand

0 3 push operand

1

BAHAN AJAR





4. Moh. Sjukani, Algoritma dan Struktur Data dengan C, C++, dan Java, Mitra Wacana

Media, 2005





Pada akhir pertemuan ini anda diharapkan mampu : 1. Memahami konsep penggunaan antrian array (Queue) dalam bahasa C++/Pascal


dalamnya menggunakan antrian (Queue)

Pokok Bahasan :

Penggunaan Antrian Array

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan Antrian

Array dalam bahasa C/Pascal. membuat program sederhana yang di dalamnya terdapat Antrian

Array yang merupakan pembelajaran lanjutan dari praktikum algoritma dan pemrograman pada





media penyimpanan.





2

ANTRIAN DENGAN ARRAY

Pengertian

Antrian (Queue) dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat

seperti ada data yang diletakkan di sebelah data yang lain seperti pada gambar 01.

Pada gambar, data masuk melalui lorong di sebelah kanan dan masuk dari terowongan

sebelah kiri. Hal ini membuat antrian bersifat FIFO (First In First Out), beda dengan

stack yang berciri LIFO.

Gambar 01

Antrian dapat dibuat baik dengan array maupun dengan struct. Pada pembuatan

antrian dengan array, antrian yang disajikan bersifat statis. Ini disebabkan oleh jumlah

maksimal array sudah ditentukan sejak deklarasi awal.

Algoritma PUSH

Salah satu algoritma untuk proses memasukkan data (PUSH) adalah sebagai berikut:

0. Masukkan inputan (x)

1. Jika variabel cek = max (Nilai maksimal array), kerjakan langkah 2. Jika tidak,

kerjakan langkah 3.

2. Cetak “ANTRIAN PENUH” lalu selesai.

3. Selama cek kurang dari max, maka c c +1 dan data [c] x.

Algoritma POP

Salah satu algoritma untuk proses mengeluarkan data (POP) adalah sebagai berikut:

0. Jika cek = 0, cetak “ANTRIAN KOSONG” kemudian selesai. Jika tidak,

lakukan langkah 2.

1. mulai x=0, selama x kurang dari cek, lakukan langkah 2 dan 3.

2. data[x] data [x+1].

3. data[cek-1] NULL.

4. cek cek – 1

Contoh program yang mengimplementasikan algoritma di atas :

#include<stdio.h>

#include<conio.h>

void main()

{

int cek=0, data[20], x, hapus;

char pil;

do {

A B

C

D

E

F

F

3

clrscr();

printf("1. Tambah Antrian\n");

printf("2. Hapus Antrian\n");

printf("3. Lihat Antrian\n");

printf("4. Keluar\n");

printf("Silahkan masukkan pilihan anda... ");

pil=getche();

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

printf("\n\nAnda salah mengetikkan

inputan...\n");

else

{

if(pil=='1') //PUSH

{

if(cek==20)

printf("\nAntrian Penuh\n\n");

else

{

printf("\nMasukkan nilai-->

");scanf("%i",&x);

data[cek]=x;

cek++;

}

}

else

{

if(pil=='2') //POP

{

if(cek==0)

printf("\nAntrian

kosong\n\n");

else

{

hapus=data[0];

for(int v=0;v<cek;v++)

data[v]=data[v+1];

data[cek-1]=NULL;

cek--;

printf("\nData dgn nilai=%i

terhapus.",hapus);

}

getch();

}

else

{

if(pil=='3') //CEK DATA

{

if(cek==0)

printf("\nAntrian

Kosong.\n\n");

else

{

printf("\n");

4

for(int

z=0;z<cek;z++)

{

printf(" | ");

printf("%i",data[z]);

printf(" | ");

}

}

getch();

}

}

}

}

}while(pil!='4');

}

Pengembangan :

1. Buatlah program untuk simulasi antrian registrasi UKDW. Yang tercatat

adalah nim mahasiswa.

2. Kembangkan program tersebut sehingga bisa menyimpan keterangan nim,

nama, dan prodi mahasiswa tersebut.

3. Tambahkan fitur untuk mengetahui urutan antrian dari nim tertentu.

Soal :

Buat pengembangan program dari latihan di atas dengan beberapa fitur :

1. Bisa melihat urutan untuk prodi tertentu ataupun secara keseluruhan.

2. Bisa POP melompati urutan. Jadi misalkan urutan nomor 2 keluar (POP) lebih

dulu daripada urutan pertama.

5

BAHAN AJAR






Media, 2005





Pada akhir pertemuan ini anda diharapkan mampu :

1. Memahami konsep fungsi dan penggunaan pointer dalam bahasa

C++/Pascal

2. Membuat program sederhana sebagai solusi atas suatu masalah tertentu yang

di dalamnya menggunakan pointer

Pokok Bahasan :

Penggunaan Pointer

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan Pointer

dalam bahasa C/Pascal. membuat program sederhana yang di dalamnya terdapat Pointer yang


sebelumnya.




media penyimpanan.





6

POINTER

Pointer adalah suatu variabel penunjuk yang menunjuk pada suatu alamat memori

komputer tertentu. Pointer merupakan variabel level rendah yang dapat digunakan

untuk menunjuk nilai integer, character, float, double, atau single, dan bahkan tipe-tipe

data lain yang didukung oleh bahasa C. Variabel biasa, sifatnya statis dan sudah pasti,

sedangkan pada pointer sifatnya dinamis dan dapat lebih fleksibel. Variabel pointer

yang tidak menunjuk pada nilai apapun berarti memiliki nilai NULL, dan disebut

sebagai dangling pointer karena nilainya tidak diinisialisasi dan tidak dapat diprediksi.

Pendeklarasian variabel pointer menggunakan tanda * sebelum nama variabelnya,

sedangkan untuk menampilkan nilai yang ditunjuk oleh suatu variabel pointer, juga

digunakan operator * (tanda asterisk). Jika diinginkan untuk menampilkan alamat

tempat penyimpanan nilai yang ditunjuk oleh suatu variabel pointer, digunakan

operator & (tanda ampersand).

Pada suatu tipe data array, variabel pointer hanya perlu menunjuk pada nama variabel

arraynya saja tanpa perlu menggunakan tanda ampersand, atau menunjuk pada nama

variabel array pada indeks yang ke nol nya. Untuk lebih jelasnya, silahkan lihat

contoh berikut:

Pendeklarasian variabel biasa dan pointer: //variabel biasa

int nilai1 = 4;

float nilai2 = 3.5;

char nama[10] = “anton”; //array of char (string)

//variabel pointer

int *nilai_p1; //dangling pointer

int *nilai_p2 = &nilai1; //menunjuk ke tipe data int

char *nilai_p3 = nama; //menunjuk ke tipe data array of char

char *nilai_p4 = &nama[0];

Ilustrasi Pointer:

7

Contoh program untuk dicoba: #include <stdio.h>

#include <conio.h>

int main(){

int nilai1 = 4;

int nilai2 = 5;

float nilai3 = 3.5;

char nama[11] = "abcdefghij";

int *nilai_p1 = &nilai1;

int *nilai_p2 = &nilai2;

char *nilai_p4 = nama;

float *nilai_p3= &nilai3;

printf("nilai 1 = %d, alamat1 = %p, ukuran

%d\n",*nilai_p1,&nilai_p1,sizeof(nilai1));

printf("nilai 2 = %d, alamat2 = %p, ukuran


printf("nilai 3 = %f, alamat3 = %p, ukuran


printf("nilai 4 = %s, alamat4 = %p, ukuran

%d\n",nama,&nilai_p4,sizeof(nama));

getch();

return 0;

}

Operasi pointer:

1. Operasi Pemberian nilai

Contoh 1: #include <stdio.h>

#include <conio.h>

4 nilai1

int

3.5 nilai2

float

“anton” nama

char

nilai_p1

nilai_p2

nilai_p3

ff4c

ff4a

ff47

4

3.5

anton

8

int main(){

float nilai,*p1,*p2;

nilai = 14.54;

printf("nilai = %2.2f, alamatnya %p\n",nilai,&nilai);

p1 = &nilai;

printf("nilai p1 = %2.2f, p1 menunjuk alamat

%p\n",*p1,p1);

//pada awalnya p2 masih dangling pointer

printf("mula-mula nilai p2 = %2.2f, p2 menunjuk alamat

%p\n",*p2,p2);

p2 = p1; //operasi pemberian nilai, berarti alamat x2

sama dengan x1

printf("sekarang nilai p2 = %2.2f, p2 menunjuk alamat

%p\n",*p2,p2);

getch();

}


#include <conio.h>

int main(){

int *p,a=25,b;

//p masih dangling

printf("nilai a = %d di alamat a = %p,\n",a,&a);

printf("nilai p di alamat = %p\n",p);

p = &a;

printf("nilai p = %d di alamat %p\n",*p,p);

//b diisi dengan nilai yang berasal dari nilai

//variabel a yang ditunjuk oleh pointer p

b = *p;

printf("nilai b = %d di alamat %p\n",b,&b);

getch();

}

Contoh 3: #include <conio.h>

#include <stdio.h>

int main(){

int a=25,b=12,t;

int *p,*q;

p = &a;

q = &b;

printf("nilai yang ditunjuk p = %d di alamat %p\n",*p,p);

printf("nilai yang ditunjuk q = %d di alamat %p\n",*q,q);

//Contoh kasus, penukaran nilai 2 variabel dengan pointer

9

t = *p;

*p = *q;

*q = t;

printf("nilai yang ditunjuk p sekarang = %d di alamat

%p\n",*p,p);

printf("nilai yang ditunjuk q sekarang = %d di alamat

%p\n",*q,q);

getch();

}


#include <conio.h>

int main(){

int a,*p;

p=&a;

*p=25;

printf("nilai a = %d",a);

}

2. Operasi Aritmatika #include <stdio.h>

#include <conio.h>

int main(){

int a,b=10,*p,*q;

p=&a;

*p=25;

printf("nilai a = %d\n",a);

printf("alamat p = %p\n",p);

q=&b;

printf("alamat q = %p\n",q);

printf("nilai a + b = %d\n",(*p+*q));

//posisi alamat p menjadi bergeser, nilai berubah

p=p+1;

printf("nilai p = %d, alamat = %p\n",*p,&p);

q=q-1;

printf("nilai q = %d, alamat = %p\n",*q,&q);

getch();

}

Pointer pada array 1 dimensi: #include <stdio.h>

#include <conio.h>

int main(){

char S[] = "anton";

char *p;

//cara 1

//langsung menunjuk nama array.

p=S;

for(int i=0;i<5;i++){

printf("%c",*p);

p++;

}

printf("\n");

10

//cara 2

p=&S[0];


printf("%c",*p);

p++;

}

printf("\n");

//Membalik kalimat

p--;


printf("%c",*p);

p--;

}

printf("\n");

getch();

}

Pointer pada Struct: #include <stdio.h>

#include <conio.h>

typedef struct{

int nim;

int umur;

float ipk;

} Mahasiswa;

Mahasiswa m;

Mahasiswa *p = &m;

int main(){

//struct biasa

m.nim=123;

m.ipk=3.2;

m.umur=23;

printf("nim = %d\n",m.nim);

printf("ipk = %f\n",m.ipk);

printf("umur = %d\n",m.umur);

//struct pointer

p->ipk = 3.5;

p->nim = 321;

p->umur = 32;

printf("nim = %d\n",p->nim);

printf("ipk = %f\n",p->ipk);

printf("umur = %d\n",p->umur);

//mengacu pada variabel aslinya

printf("nim = %d\n",m.nim);

printf("ipk = %f\n",m.ipk);

printf("umur = %d\n",m.umur);

getch();

11

}

Pengembangan:

Buatlah sebuah program untuk mengecek apakah suatu kata palindrom atau bukan,

tanpa memperhatikan spasi dan huruf besar/kecilnya. Program dibuat dengan

menggunakan template struct sebagai berikut: typedef struct{

char elemen[30];

int jml_kata;

} Kata;

Kata kata;

Kata *p_kata=&kata;

Lanjutkanlah program berikut agar hasilnya sesuai dengan soal di atas: #include <stdio.h>

#include <conio.h>

typedef struct{

char elemen[30];

int jml_kata;

} Kata;

Kata kata;

Kata *p_kata=&kata;

int main(){

char kalimat[30];

p_kata->jml_kata=0;

char *p = p_kata->elemen;

printf("Masukkan kata : ");gets(kalimat);

fflush(stdin);

printf("Kalimat : %s\n",kalimat);

for(int i=0;i<kalimat[i];i++){

*p=kalimat[i];

p_kata->jml_kata++;

p++;

}

p=p_kata->elemen;

//tampilkan kembali kalimat tersebut

for(int i=0;i<=p_kata->jml_kata;i++){

printf("%c ",*p);

p++;

}

//kembangkan….

getch();

}

Soal:

Buatlah program data KTP, dengan menggunakan pointer pada struct KTP sebagai

berikut:

12

typedef struct

{

int tgl;

int bln;

int th;

}Tanggal;

typedef struct

{

char noID[5];

char nama[30];

char jenis_kelamin; //‟L‟ atau „P‟

Tanggal t;

}KTP;

typedef struct

{

KTP ktp;

int jml;

}Data_KTP;

Data_KTP data_ktp;

Data_KTP *p;

Buatlah fungsi untuk:

1. Menambah data

2. Mencari data berdasarkan tahun kelahiran tertentu

3. Menampilkan data berdasarkan L dan P

4. Mengedit data

Semua pengaksesan dilakukan dengann menggunakan pointer.

13

BAHAN AJAR






Media, 2005





Pada akhir pertemuan ini anda diharapkan mampu : 1. Memahami konsep fungsi dan penggunaan senarai tunggal (Linked List)


dalamnya menggunakan Linked List

Pokok Bahasan :

Kegunaan Linked List

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan Linked List

dalam bahasa C/Pascal. membuat program sederhana yang di dalamnya terdapat Linked List

yang merupakan pembelajaran lanjutan dari praktikum algoritma dan pemrograman pada





media penyimpanan.





14

SENARAI BERANTAI TUNGGAL TIDAK BERPUTAR

(SINGLE LINKED LIST NON CIRCULAR)

DEKLARASI LINKED LIST

Sebelum membuat sebuah senarai (Link List) kita harus mendeklarasikan tipe

data dan pointer yang akan kita gunakan. Selain itu kita juga harus

mendeklarasikan list -list yang nantinya akan kita gunakan. Sebagai contoh:

#include “stdio.h”

typedef struct Gerbong //membuat sebuah tipe data baru yang

terdiri dari 2 field

{

int data; //field data bertipe integer

Gerbong *next; //field next merupakan pointer dari list

};

Gerbong *baru; //variable baru bertipe pointer dari

list

Gerbong *kepala; //variable kepala bertipe pointer dari list

Gerbong *ekor; //variable ekor bertipe pointer dari

list

Gerbong *bantu; //variable bantu bertipe pointer dari list

Gerbong *hapus; //variable hapus bertipe pointer dari list

catatan:

'Gerbong' diatas merupakan nama dari tipe data bentukan.

kepala, ekor, baru, bantu,hapus merupakan variable pointer yang berisi alamat

memori.

kepala merupakan node paling awal dan selalu tetap(tidak boleh berpindah).

ekor merupakan node paling akhir jadi ketika terjadi penambahan sebuah node

yang diletakan di belakang maka pointer dari ekor akan ikut berpindah.

baru merupakan nama untuk node yang diciptakan atau ditambahkan.

bantu, hapus digunakan untuk memudahkan operasi edit dan delete sebuah node.

ILUSTRASI

Senarai berantai dapat diilustrasikan seperti satu kesatuan rangkaian kereta api.

Kereta api terdiri dari beberapa gerbong, masing-masing dari gerbong itulah yang

disebut struct / tipe data bentukan. Agar gerbong-gerbong tersebut dapat saling

bertaut dibutuhkan minimal sebuah kait yang dinamakan sebagai pointer.

Setelah mendeklarasikan tipe data dan pointer pada list, selanjutnya kita akan

mencoba membuat senarai / linked list tunggal tidak berputar atau sebuah gerbong. Ada

beberapa operasi yang dapat kita buat pada senarai tersebut, diantaranya: tambah, hapus

dan edit dari gerbong tersebut.

Inti dari linked list adalah proses (tambah, edit, hapus) dari gerbong / node dan

bagaimana rnenyambungkan antar gerbong / node tersebut.

15

Gambar diatas dilustrasikan sebuah rangkaian kereta api dengan 4 buah

gerbong. Gerbong A akan disebut sebagai kepala / head (walaupun penamaan ini bebas)

dan gerbong D adalah ekor / tail. Tanda panah merupakan kait atau pointer yang

menghubungkan satu gerbong dengan yang lainnya.

Pointer yang dimiliki D menuju ke NULL,inilah yang membedakan antara

senarai berputar dengan yang tidak berputar. Kalau senarai berputar maka pointer dari

D akan menuju ke A lagi.

PEMBENTUKAN NODE (GERBONG)

Digunakan keyword new yang berarti mempersiapkan sebuah node baru

berserta alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya

ditunjuk ke NULL. Pembentukan node tidak dapat dilakukan sekaligus namun harus

satu persatu, hal ini berkaitan dengan bagaimana cara menyambungkan antar node

tersebut.

kepala= new Gerbong; //membuat sebuah node dengan nama kepala

kepala->next==NULL; //pointer milik kepala diarahkan ke NULL

kepala->data=101; //isi field data dengan 101

Kode diatas apabila dicompile maka akan membentuk sebuah node bertipe

Gerbong dengan nama kepala. Karena bertipe list maka kepala juga memiliki 2 field

seperti list yaitu field data dan field next. Bila diasumsikan dengan gerbong maka pada

proses ini dibentuk gerbong A.

Setelah membentuk sebuah node dengan nama kepala, maka langkah

selanjutnya adalah membentuk gerbong yang lain (gerbong B dan selanjutnya). baru=new Gerbong; //membuat sebuah node dengan nama baru

baru->data=5;

//Tambah Depan if (kepala->next==NULL)

{

baru-->next=kepala; //rnenyambung node bare dengan

node kepala

kepala=baru; //memindahkan kepala ke node baru

}

//Tambah Belakang ekor->next=baru; //menyambung node paling akhir/ekor ke

node baru

ekor=baru; //meniindahkan ekor ke node terakhir yaitu

node baru .

ekor->next=NULL;

16

Tambah belakang berarti node baru yang terbentuk akan diletakan di posisi paling

belakang.

PENGHAPUSAN NODE

Pada senarai berkepala, penghapusan sebuah list dilakukan jika ada list lain yang

bukan list "kepala" dalam barisan senarai tersebut. Dengan kata lain, list yang digunakan

sebagai "kepala" tidak boleh dihapus, "kepala harus dipindahkan terlebih dahulu.

Keyword yang digunakan adalah delete. Contoh:

//Hapus Depan

if(kepala->next!=NULL)

{ if(kepala->next==ekor)

{ hapus=kepala;

kepala=kepala->next;

delete hapus;

}

}

else

{

kepala=NULL;

}

//Hapus Belakang

if(head->next!=NULL)

{

bantu=kepala;

while(bantu->next->next!=NULL)

{ bantu=bantu->next;

}

hapus=bantu->next;

bantu->next = NULL;

delete hapus;

}

else

{

head =NULL;

}

17

MENAMPILKAN ISI NODE

Untuk menampilkan isi suatu node dengan cara mengakses field yang ada di dalam node

tersebut. Yaitu dengan Contoh : bantu =head;

while(bantu!=NULL)

{

printf(“%i ”,bantu->data);

bantu=bantu->next;

}

LATIHAN

1. Buatlah sebuah linked list non circular yang berisi nim anda dan nama lengkap

anda.

2. Buat fungsi untuk menambahkan node single linked list non circular dimana tiap

node mengandung informasi nim dan nama. Peletakan posisi node urut

berdasar nim secara ascending, jadi bisa tambah depan, belakang maupun

tambah di tengah.

Isikan data nim dan nama lengkap teman sebelah kiri dan kanan anda!!!

3. Buatlah fungsi untuk menampilkan data 3 buah node yang telah anda bentuk

sebelumnya. Contoh tampilan

NIM Nama Lengkap

22053766 Hernawan

22053768 Andrew S

22053791 Anthony S

4. Buatlah fungsi untuk mencari nama yang telah diinputkan dengan

menggunakan NIM.

Contoh tampilan:

Inputkan nim yang dicari = 22053768

Nama yang tercantum Andrew S

5. Buatlah sebuah fungsi untuk menghapus nim yang diinputkan oleh user.

Contoh tampilan:

NIM yang mau dihapus = 2205376

NIM dengan nama Andrew S ditemukan dan telah dihapus

6. Buatlah sebuah program dengan menggunakan single linked list non circular

dengan fungsi-fungsi:

menambah data(dari depan dan dari belakang)

search data yang telah diinputkan

menghapus data( dari depan dan dari belakang)

mencetak data

Buat dengan menggunakan menu ya…..

7. (soal extended) Dengan menggunakan soal no 6 tambahkan 4 fungsi tambahan:

18

menambah data(di tengah)

menghapus data tertentu(berada di tengah)

mengurutkan data acak secara acending

mengurutkan data acak secara decending

SELAMAT MENGERJAKAN

SENARAI BERANTAI TUNGGAL BERPUTAR

(SINGLE LINKED LIST CIRCULAR)

Perbedaan Single Linked list Circular dengan Non Circular

Pada saat kita membahas Single Linked List non Circular telah dijelaskan

bahwa kita membutuhkan sebuah kait untuk menghubungkan node-node /

gerbong-gerbong data yang ada. Perbedaan dengan Single Linked List Circular

adalah pada node terakhir/ ekor yang semula menunjuk ke NULL diganti

menunjuk kembali ke kepala atau head.

Contoh Struct Single Link List Circular

Dengan melihat gambar kita dapat membayangkan bahwa setiap node akan

membentuk lingkaran, dan semakin banyak node lingkaran akan semakin besar.

Pada intinya tail akan selalu terhubung dengan head. Membuat Single Linked List Circular berkepala berputar

Untuk menginisialisasikan Single Linked List Circular berkepala berputar

cukup mudah karena kita hanya seperti memberikan label pada suatu list. Cara

mendeklarasikanna seperti contoh dibawah ini: #include “stdio.h”

typedef struct Tnode

{ int data;

Tnode *next;

};

Tnode *bantu; //mendeklarasikan pointer bantu

Tnode *baru; //mendeklarasikan pointer baru

Tnode *head; //mendeklarasikan pointer head

Tnode *tail; //mendeklarasikan pointer tail

void main()

{

head=new Tnode;

head ->next=head;

}

//memasukkan data Single Linked list Circular berkepala berputar head -> data = 50;

//menambah simpul baru dan menghubungkannya dengan simpul kepala baru = new Tnode;

baru -> data = 20; apakah perintah ini masih dapat

digunakan untuk penambahan

baru -> next = head; simpul berikutnya???

19

head ->next = head;

//menambah simpul baru dan membuat ekor pada akhir senarai tail = baru;

baru = new Tnode;

baru -> data = 30; apakah perintah ini masih dapat

digunakan untuk penambahan

baru ->next=head; simpul berikutnya???

tail -> next=baru;

tail = baru;

Pada senarai berantai seperti gambar di bawah:

Bagaimana cara meletakkan data baru 40 diantara simpul dengan data 50 dan 20??

Tambahkan pada program diatas: baru=new Tnode;

baru->data=40;

baru->next=head->next;

head->next=baru;

Mengedit / update data

Misalnya kita ingin mengganti data pada ekor menjadi 25, caranya adalah sebagai

berikut: tail->data=25;

Membaca senarai

Tambahkan pada program diatas bantu=head;

printf(“%d”, bantu);

bantu=bantu->next;

while(bantu!=head)

{

printf(“%d”, bantu);

bantu=bantu->next;

}

Menghapus Simpul ekor

Tambahkan pada program diatas: bantu=head;

while(bantu->next!=tail)

{

bantu=bantu->next;

}

bantu->next=head;

delete tail;

tail=bantu;

20

Menghapus Simpul kepala/head

Tambahkan pada program diatas: bantu=head->next;

delete head;

head = bantu;

Latihan

1. Buatlah sebuah Single Linked List Circular yang mcmpunyai 5 buah simpul

seperti pada contoh dibawah ini

a. Tuliskan listing program untuk membaca data dari seluruh simpul dengan

menggunakan perulangan (for/while)

b. TuIiskan listing program untuk menambah sebuah simpul baru dengan data

5 yang diletakan diantara data 30 dan data 20.

c. Tuliskan listing program untuk menghapus simpul dengan data 20 tanpa

merusak senarai.

d. Tuliskan listing program untuk menghapus semua simpul dengan

menggunakan variabel bantu dengan menggunakan perulangan

(while/for).

2. Buatlah program Single Linked List Circular yang fleksibel dan

dinamis. Dimana user dapat menambah simpul baru beserta datanya,

membaca semua data pada senarai, menghapus simpul dengan data yang

ditentukan oleh user, dan dapat menghapus semua simpul yang ada. Jangan

Iupa membuat trapping errornya.

3. (soal extended) Buatlah sebuah link list berisi data-data identitas ktp(nama,

alamat, no KTP) buatlah menu sebagai berikut:

a. Input entry ktp ( input akan langsung terurutkan berdasarkan no ktp

asending )

b. Delete file yang diinginkan user.

c. Searching entry ktp

d. Cetak semua entry ktp

e. Cetak entry ktp tertentu

4. (soal extended) Buatlah 3 link list yang merepresentasikan jam(1-12), menit(1-

60) dan detik(1-60). Mintalah inputan dari user berupa jumlah detik.

21

Konversikan jumlah detik tersebut dan masukkan ke dalam link list (gunakan

pointer jam,menit,detik) kemudian cetak jam yang tertera di link list tersebut.

22

BAHAN AJAR






Media, 2005





Pada akhir pertemuan ini anda diharapkan mampu : 1. Memahami konsep fungsi dan penggunaan senarai ganda (Double Linked List)


dalamnya menggunakan Double Linked List

Pokok Bahasan :

Double Linked List

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan Double

Linked List dalam bahasa C/Pascal. membuat program sederhana yang di dalamnya terdapat

Double Linked List yang merupakan pembelajaran lanjutan dari praktikum algoritma dan

pemrograman pada semester sebelumnya.




media penyimpanan.





23

Double Linked List

Tidak jauh berbeda dengan materi sebelumnya yakni Single Linked List.

Materi ini hanya menambahkan satu pointer (yang nantinya dapat dikembangkan

dengan banyak pointer). Bila kita lihat lagi penggambaran dari Single Linked List :

typedef struct TNode { data int data;

TNode *next; pointer next };

Sedangkan pada materi yang ada sekarang, kita akan menambahkan satu lagi

pointernya. Sehingga bila kita lihat ilustrasinya :

typedef struct TNode{ data int nim;

TNode *next;

TNode *prev; pointer prev pointer next };

Untuk setiap pembuatan node yang baru kita mempergunakan keyword new.

TNode *baru;

baru = new TNode;

baru ->data = databaru;

baru ->next = NULL;

baru-> prev = NULL;

Sama seperti Single Linked List, kita juga membagi materi ini dalam dua jenis,

yakni :

a. Non Circular

b. Circular

Dimana tiap-tiap juga akan terdiri dari linked list yang terdiri dari Head saja

dan Head dengan Tail.

A. Non Circular

1. Dengan Head

- Menggunakan 1 pointer head

- Head selalu menunjuk node pertama

Sebelumnya kita harus mendeklarasikan dulu pointer head :

TNode *head;

Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung

mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai

null terlebih dahulu :

24

head = NULL;

untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat

mengetahuinya dengan mengecek nilai dari pointer Head-nya.

int isEmpty() {

if(head==NULL) return 1;

else return 0;

}

Contoh program :

Penambahan didepan

void tambahdata (int databaru){

TNode *baru;

baru = new TNode;

baru -> data = databaru;

baru -> next = NULL;

baru -> prev = NULL;

if (isEmpty()==1) {

head=baru;

head->next=NULL;

head->prev=NULL;

}

else {

baru->next=head;

head->prev=baru;

head=baru;

}

printf(”data masuk”);

}

Penggambaran :

head

NULL

Setelah dibuat node baru dan jika diketahui head==NULL :

head baru

Bila kita membuat node baru lagi maka

25

baru head

head

baru head

head

Penambahan di belakang

void insertBelakang (int databaru){

TNode *baru,*bantu;

//digunakan untuk mengetahui data terbelakang

baru = new TNode;

baru->data = databaru;

baru->next = NULL;

baru->prev = NULL;

if(isEmpty()==1){

head=baru;

head->next = NULL;

head->prev = NULL;

}

else {

bantu=head;

while(bantu->next!=NULL){

bantu=bantu->next;

}

bantu->next = baru;

baru->prev = bantu;

}


}

26

Tampil

void tampil(){

TNode *bantu;

bantu = head;

if(isEmpty()==0){

while(bantu!=NULL){

printf(“%i “,bantu->data);

bantu=bantu->next;

}

printf(“\n”);

}

else printf(“Masih Kosong”);

}

Hapus di depan

void hapusDepan (){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

d = hapus->data;

head = head->next;

head->prev = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

}

prinf(“%i terhapus”,d);

} else printf(“Masih Kosong”);

}

Hapus di belakang

void hapusBelakang(){

TNode *hapus;

int d;

if (isEmpty()==0){


hapus = head;

while(hapus->next!=NULL){

hapus = hapus->next;

}

d = hapus->data;

hapus->prev->next = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

}

27

printf(“%i terhapus”,d);


}

latihan :

Buatlah ilustrasi dari masing-masing potongan program.

Buat program lengkap dari potongan-potongan program yang ada

diatas! Buat agar menjadi seperti menu.

Buat program untuk memasukkan node baru tetapi diantara node yang

sudah ada. Tentukan node yang baru akan berada pada antrian

keberapa.

2. Dengan Head dan tail

- Menggunakan 2 pointer, head dan tail.

- Head selalu menunjuk node pertama dan tail selalu menunjuk node

terakhir


TNode *head, *tail;




head = NULL;

tail = NULL;


mengetahuinya dengan mengecek nilai dari pointer Tail-nya.

int isEmpty() {

if(tail==NULL) return 1;

else return 0;

}

28

Contoh program :

Penambahan di depan


TNode *baru;

baru = new TNode;




if (isEmpty()==1) {

head=baru;

tail=head;

head->next=NULL;

head->prev=NULL;

tail->next=NULL;

tail->prev=NULL;

}

else {

baru->next=head;

head->prev=baru;

head=baru;

}


}

Penggambaran :

head tail

NULL

Setelah dibuat node baru dan jika diketahui tail==NULL :

head tail baru

Bila kita membuat node baru lagi maka :

baru head tail

29

head tail

baru head tail

head tail


void insertBelakang(int databaru){

TNode *baru;

baru = new TNode;


baru->next = NULL;

baru->prev = NULL;

if(isEmpty()==1){

head=baru;

tail=head;

head->next = NULL;

head->prev = NULL;

tail->prev = NULL;

tail->next = NULL;

}

else {

tail->next = baru;

baru->prev = tail;

tail = baru;

tail->next = NULL;

}

printf(“Data sudah masuk\n”);

}

Tampil void tampil(){

TNode *bantu;

bantu = head;

if(isEmpty()==0){

while(bantu!=tail->next){

prinrf(“%i ”,bantu->data);

bantu=bantu->next;

}

cout<<endl;

} else printf(“masih kosong\n”); }

30

Hapus di depan

void hapusDepan(){

TNode *hapus;

if (isEmpty()==0){


hapus = head;

d = hapus->data;

head = head->next;

head->prev = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

tail = NULL;

}

printf(“%i terhapus\n”,d);

} else printf(“masih kosong\n”);

}

Hapus di belakang


TNode *hapus;

int d;

if (isEmpty()==0){


hapus = tail;

d = tail->data;

tail = tail->prev;

tail->next = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

tail = NULL;

}



}

latihan :






keberapa.

B. Non Circular dengan Head, head & tail

1. Dengan Head

31

- Menggunakan 1 pointer head

- Head selalu menunjuk node pertama

Sebelumnya kita harus mendeklarasikan dulu pointer head : TNode *head;



null terlebih dahulu : head = NULL;


mengetahuinya dengan mengecek nilai dari pointer Head-nya.

int isEmpty() {

if(head==NULL) return 1;

else return 0;

}

Contoh program :

Penambahan di depan


TNode *baru,*bantu;

//pointer bantu digunakan untuk menunjuk node terakhir

(head->prev)

baru = new TNode;


baru -> next = baru;

baru -> prev = baru;

if (isEmpty()==1) {

head=baru;

head->next=head;

head->prev=head;

}

else {

bantu=head->prev;

baru->next=head;

head->prev=baru;

head=baru;

head->prev=bantu;

bantu->next=head;

}


}

Penggambaran :

head

NULL

32

Setelah dibuat node baru dan jika diketahui head==NULL :

head baru


baru head bantu

baru head bantu

baru head bantu

head bantu

head bantu

33


void insertBelakang (int databaru){

TNode *baru,*bantu;

baru = new TNode;


baru->next = baru;

baru->prev = baru;

if(isEmpty()==1){

head=baru;

head->next = head;

head->prev = head;

}

else {

bantu=head->prev;

bantu->next = baru;

baru->prev = bantu;

baru->next = head;

head->prev = baru;

}


}

Tampil

void tampil(){

TNode *bantu;

bantu = head;

if(isEmpty()==0){

do{

printf(“%i ”,Bantu->data);

bantu=bantu->next;

}while(bantu!=head);

printf(“\n”);

} else printf(“masih Kosong”);cout<<"Masih kosong\n";

}

34

Hapus di depan

void hapusDepan (){

TNode *hapus,*bantu;

int d;

if (isEmpty()==0){

if(head->next != head){

hapus = head;

d = hapus->data;

bantu = head->prev;

head = head->next;

bantu->next = head;

head->prev = bantu;

delete hapus;

} else {

d = head->data;

head = NULL;

}


} else printf(“Masih kosong\n”);

}

Hapus di belakang


TNode *hapus,*bantu;

int d;

if (isEmpty()==0){

if(head->next != head){

bantu = head;

while(bantu->next->next != head){

bantu = bantu->next;

}

hapus = bantu->next;

d = hapus->data;

bantu->next = head;

delete hapus;

} else {

d = head->data;

head = NULL;

}



}

35

latihan :






keberapa.

2. Dengan Head dan tail

- Menggunakan 2 pointer, head dan tail.

- Head selalu menunjuk node pertama dan tail selalu menunjuk node

terakhir


TNode *head, *tail;




head = NULL;

tail = NULL;


mengetahuinya dengan mengecek nilai dari pointer Tail-nya.

int isEmpty() {

if(tail==NULL) return 1;

else return 0;

}

Contoh program :

Penambahan di depan


TNode *baru;

baru = new TNode;




36

if (isEmpty()==1) {

head=baru;

tail=head;

head->next=head;

head->prev=head;

tail->next=tail;

tail->prev=tail;

}

else {

baru->next=head;

head->prev=baru;

head=baru;

head->prev=tail;

tail->next=head;

}


}

Penggambaran :

head tail

NULL

Setelah dibuat node baru dan jika diketahui tail==NULL :

head baru tail


baru head bantu

baru head tail

37

baru head tail

head bantu

head bantu


void insertBelakang(int databaru){

TNode *baru;

baru = new TNode;


baru->next = baru;

baru->prev = baru;

if(isEmpty()==1){

head=baru;

tail=baru;

head->next = head;

head->prev = head;

tail->next = tail;

tail->prev = tail;

}

else {

tail->next = baru;

baru->prev = tail;

tail = baru;

tail->next = head;

head->prev = tail;

}

printf(“Data masuk\n”);

}

38

Tampil

void tampil(){

TNode *bantu;

bantu = head;

if(isEmpty()==0){

do{

cout<<bantu->data<<" ";

bantu=bantu->next;

}while(bantu!=tail->next);

printf(“\n”);

} else printf(“masih kosong\n”);

}

Hapus di depan

void hapusDepan(){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head != tail){

hapus = head;

d = hapus->data;

head = head->next;

tail->next = head;

head->prev = tail;

delete hapus;

} else {

d = head->data;

head = NULL;

tail = NULL;

}



}

39

Hapus di belakang


TNode *hapus;

int d;

if (isEmpty()==0){

if(head != tail){

hapus = tail;

d = hapus->data;

tail = tail->prev;

tail->next = head;

head->prev = tail;

delete hapus;

} else {

d = head->data;

head = NULL;

tail = NULL;

}

cout<<d<<" terhapus\n";

} else cout<<"Masih kosong\n";

}

latihan :




40

BAHAN AJAR






Media, 2005






1. Memahami konsep fungsi dan penggunaan rekursif


di dalamnya menggunakan rekursif

Pokok Bahasan :

Fungsi Rekursif

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan rekursif

dalam bahasa C/Pascal. membuat program sederhana yang di dalamnya terdapat rekursif yang


sebelumnya.




media penyimpanan.





41

faktorial(4)

4 * faktorial(3)

Fungsi Rekursif

Fungsi rekursif adalah suatu fungsi yang memanggil dirinya sendiri. Pada beberapa

persoalan, fungsi rekursif sangat berguna karena mempermudah solusi. Namun

demikian, fungsi rekursif juga memiliki kelemahan, yakni memungkinkan terjadinya

overflow pada stack, yang berarti stack tidak lagi mampu menangani permintaan

pemanggilan fungsi karena kehabisan memori( stack adalah area memori yang dipakai

untuk variable lokal untuk mengalokasikan memori ketika suatu fungsi dipanggil.

Oleh karena itu, jika bisa diselesaikan dengan metode iteratif, gunakanlah metode

iteratif.

Bentuk umum fungsi rekursif.

return_data_type function_name(parameter_list)

{

...

function_name(...);

...

}

Contoh program

Contoh #1: Faktorial

Fungsi rekursif dapat digunakan untuk menghitung faktorial. Berikut penjelasan

beserta dengan contoh listing programnya.

Fungsi faktorial dapat dinyatakan dalam bentuk rekursif seperti berikut:

fak(n) = 1, untuk n = 0 atau n = 1

fak(n) = n x (n-1)!, untuk n > 0

Berikut contoh proses untuk perolehan hasil 4!.

Hasil akhir: 24

faktorial(1)

3 * faktorial(2)

2 * faktorial(1)

42

Berikut implementasi program dengan metode iteratif.

#include <stdio.h>

int fak(int n)

{

int i,fak;

if(n == 0 || n == 1)

return 1;

else

{

temp = 1;

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

fak = fak * i;

return (fak);

}

void main()

{

int fakt;

printf("Masukkan berapa faktorial : ");

scanf("%d",&fakt);

printf("Hasil faktorial dari adalah : %d\n", fak(fakt));

}

Berikut implementasi program untuk proses faktorial dengan metode rekursif:

#include <stdio.h>

int fak( int n )

{

if (n == 0 || n == 1)

return 1;

else

return n * fak(n-1);

}

void main()

{

int n, hasil;

printf(“Masukkan suatu bilangan bulat : “);

scanf(”%d”, &n);

hasil = fak(n);

printf(“%d! = %d”, n, hasil);

}

Sekarang cobalah ketikan program di atas dan masukkan beberapa bilangan untuk

mengujinya!Manakah yang memiliki kecepatan yang lebih baik: pendekatan rekursif

atau pendekatan iteratif?

43

Contoh #2: Fibonacci

Fungsi rekursif juga dapat digunakan untuk menyelesaikan bilangan Fibonacci. Fungsi

Fibonacci dapat dinyatakan dalam bentuk rekursif seperti berikut:

fib(n) = 0, untuk n = 0

fib(n) = 1, untuk n = 1

fib(n) = fib(n-1) + fib(n-2), untuk n > 1

Berikut contoh hubungan antara n dan hasil fungsi:

n fib(n)

0 0

1 1

2 1

3 2

4 3

5 5

6 8

… …

Berikut contoh proses pemanggilan fib(4)

fib(4) = fib(3) + fib(2)

fib(2) + fib(1) fib(1) + fib(0)

fib(1) + fib(0)

44

Implementasi program dengan metode iteratif

#include <stdio.h>

int fib(int n)

{

int f1 = 0, f2 = 1, fibo;

if(n == 0)

return 0;

else if(n == 1)

return 1;

else

{

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

{

fibo = f1 + f2;

f2 = f1;

f1 = fibo;

}

return fibo;

}

}

void main()

{

int n, hasil;

printf(“Bilangan Fibonacci ke-“);

scanf(“%d”, &n);

hasil = fib(n);

printf(“fib(%d) = %d”, n, hasil);

}

Implementasi program dengan metode rekursif.

#include <stdio.h>

int fib(int n)

{

if(n == 0)

return 0;

else if(n == 1)

return 1;

else

return fib(n-1) + fib(n-2);

}

void main()

{

int n, hasil;

printf(“Bilangan Fibonacci ke-“);

scanf(“%d”, &n);

hasil = fib(n);

printf(“fib(%d) = %d”, n, hasil);

}

45

Cobalah ketikkan implementasi program dari metode rekursif di atas dan jalankan

program tersebut!Uji dengan memasukkan beberapa bilangan!Selanjutnya,

kembangkan program tersebut sehingga dapat untuk menampilkan n buah bilangan

fibonacci!

Contoh #3: Menara Hanoi

Menara Hanoi adalah persoalan untuk memindahkan tumpukan piring dari suatu

tonggak ke tonggak lain dengan bantuan sebuah tonggak perantara. Penyelesaian

secara rekursif untuk persoalan ini untuk n buah piring:

1. Pindahkan n-1 piring teratas pada tonggak A ke tonggak B, dengan

menggunakan tonggak C sebagai perantara.

2. Pindahkan 1 piring tersisa pada tonggak A ke tonggak C.

3. Pindahkan n-1 piring teratas pada tonggak B ke tongak C, dengan

menggunakan tonggak A sebagai perantara.

Berikut implementasi program dengan metode rekursif.

#include <stdio.h>

void tonggak(int n, char a, char b, char c)

{

if(n == 1)

printf(“Pindahkan piring dari %c ke %c\n”, a, c);

else

{

tonggak(n-1, a, c, b);

tonggak(1, a, b, c);

tonggak(n-1, b, a, c);

}

}

void main()

{

int jml_piring;

printf(“Jumlah piringan: ”);

scanf(“%d”, &jml_piring);

tonggak(jml_piring, „A‟, „B‟, „C‟);

}

46

Latihan

Berikut ini diberikan contoh program untuk menghitung pangkat sebuah bilangan

dengan menggunakan metode iteratif.

#include <stdio.h>

int pangkat (int a,int b)

{

int i, bil = a;

if(b==1)

return a;

else

{ for (i=2;i<=b;i++)

a = a * bil;

return a;

}

}

void main()

{ int x,y,hasil;

printf("masukan bilangan:");

scanf("%i",&x);

printf("masukan pangkat:");

scanf("%i",&y);

hasil = pangkat (x,y);

printf("%i",hasil);

}

Ketikkan program di atas dan jalankan!Ujilah dengan memasukkan beberapa bilangan.

Kemudian ubahlah program tersebut sehingga program tersebut menggunakan metode

rekursif!

Soal

1. Buatlah program untuk menghitung FPB(faktor persekutuan terbesar) dari 2

bilangan dengan menggunakan metode rekursif! Untuk membantu, berikut

diberikan penyelesaian secara rekursif dari FPB :

fpb(x,y) = y jika y <= x dan sisa_pembagian(x,y) = 0

fpb(x,y) = fpb(y,x) jika x < y

fpb(x,y) = fpb(y, sisa_pembagian(x,y)) untuk keadaan yang lain

2. Buatlah suatu fungsi untuk membalik suatu bilangan dengan cara rekursif. Sebagai

contoh, bilangan 1238 ditampilkan menjadi 8321!

47

BAHAN AJAR






Media, 2005






1. Memahami konsep fungsi dan penggunaan Tree


di dalamnya menggunakan Tree

Pokok Bahasan :

Penggunaan Tree

Deskripsi Singkat : Dalam pertemuan ini anda akan mempelajari fungsi dan kegunaan tree dalam

bahasa C/Pascal. membuat program sederhana yang di dalamnya terdapat tree yang merupakan

pembelajaran lanjutan dari praktikum algoritma dan pemrograman pada semester sebelumnya.




media penyimpanan.





48

TREE

Dalam ilmu komputer, tree adalah sebuah struktur data yang secara bentuk

menyerupai sebuah pohon, yang terdiri dari serangkaian node (simpul) yang saling

berhubungan. Node-node tersebut dihubungkan oleh sebuah vektor. Setiap node dapat

memiliki 0 atau lebih node anak (child). Sebuah node yang memiliki node anak

disebut node induk (parent). Sebuah node anak hanya memiliki satu node induk.

Sesuai konvensi ilmu komputer, tree bertumbuh ke bawah, tidak seperti pohon di

dunia nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan

berada di bawah node induknya.

Node yang berada di pangkal tree disebut node root (akar), sedangkan node yang

berada paling ujung pada piramida tree disebut node leaf (daun).

Ilustrasi Tree:

Binary Tree (Pohon Biner)

Dalam mata kuliah struktur data, secara khusus akan dipelajari mengenai pohon biner.

Pohon biner adalah sebuah tree yang pada masing-masing simpulnya hanya dapat

memiliki maksimum 2 (dua) simpul anak. Tidak boleh lebih. Pada pohon biner,

umumnya kedua node anak disebut dengan posisinya, yaitu kiri dan kanan.

Beberapa istilah pada pohon biner:

- Size (ukuran): jumlah total node yang terdapat pada pohon biner tersebut.

- Depth (kedalaman): panjang jalur yang menghubungkan sebuah node sampai

ke node anaknya yang paling ujung (leaf). Depth biasa juga disebut height.

Full Binary Tree (Pohon Biner Penuh) adalah pohon biner yang setiap nodenya pasti

memiliki 0 atau 2 node anak.

Perfect Binary Tree (Pohon Biner Sempurna) adalah pohon biner yang semua node

leafnya berada pada kedalaman yang sama dari node root. Juga disebut sebagai

Complete Binary Tree (Pohon Biner Lengkap)

Almost Complete Binary Tree (Pohon Biner Hampir Lengkap) adalah pohon biner

yang setiap nodenya dapat memiliki 0 node anak, atau memiliki kiri, atau jika

memiliki kanan harus memiliki kiri. Tidak boleh memiliki kanan saja.

49

Ilustrasi Binary Tree:

Implementasi

Implementasi dalam pemrograman, dalam pokok bahasan ini akan dibicarakan untuk

pohon biner saja. Asumsi awal adalah data yang hendak dimasukkan ke dalam node,

bertipe data integer.

1. Deklarasi Tree

Karena tree tersusun oleh node-node, maka yang perlu kita deklarasikan adalah

komponen node itu sendiri. Dalam contoh dibawah, akan kita namai Node.

Sebelumnya perlu kita lihat bahwa untuk mewujudkan implementasi node ke

dalam bahasa pemrograman, diperlukan sebuah struktur yang memiliki susunan

berikut ini:

Variabel data digunakan untuk menyimpan nilai angka node tersebut, sedangkan

kiri dan kanan, bertipe pointer, masing-masing mewakili vektor yang akan

menunjuk ke node anak kiri dan kanan.

2. Inisialisasi Tree

typedef struct Node{

int data;

Node *kiri;

Node *kanan;

};

50

Untuk pertama kali, saat kita akan membuat sebuah pohon biner, asumsi awal

adalah pohon itu belum bertumbuh, belum memiliki node sama sekali, sehingga

masih kosong. Oleh karena itu perlu kita tambahkan kode berikut pada baris awal

fungsi Main:

Kita mendeklarasikan sebuah pointer yang akan menunjuk ke akar pohon yang kita

buat, dengan nama *pohon. Pointer ini ditujukan untuk menunjuk struktur bertipe

Node, yang telah dibuat pada bagian 1. Karena pohon tersebut sama sekali belum

memiliki node, maka pointer *pohon ditunjukkan ke NULL.

3. Menambahkan Node Pada Tree

Karena pohon yang kita buat merupakan sebuah pohon biner, maka untuk

menambahkan sebuah node, secara otomatis penambahan tersebut mengikuti

aturan penambahan node pada pohon biner:

1. Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon.

2. Jika pohon tidak kosong, maka dimulai dari node akar, dilakukan proses

pengecekan berikut:

a. Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka

lihat ke kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki

kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri

node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri

tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat

ditempatkan.

b. Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka

lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum

memiliki kanan), maka node baru menjadi kanan node yang sedang dicek.

Seandainya kanan node sudah terisi, lakukan kembali pengecekan a dan b

terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga

node baru dapat ditempatkan.

Proses penambahan ini diimplementasikan secara rekursif pada fungsi berikut:

Node *pohon;

pohon = NULL;

51

Variabel **root menunjukkan node mana yang sedang dicek saat ini, untuk itu

saat pemanggilan fungsi ini, variabel **root kita beri nilai pointer yang menunjuk

ke node akar, yaitu pohon.

Untuk selengkapnya dapat dilihat pada bagian 5, kode program lengkap.

4. Membaca dan Menampilkan Node Pada Tree

Untuk membaca dan menampilkan seluruh node yang terdapat pada pohon biner,

terdapat 3 macam cara, atau yang biasa disebut kunjungan (visit). Semua

kunjungan diawali dengan mengunjungi akar pohon. Karena proses kunjungan ini

memerlukan perulangan proses yang sama namun untuk depth (kedalaman) yang

berbeda, maka ketiganya diimplementasikan dengan fungsi rekursif.

a. Kunjungan Pre-Order.

Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan:

1. Cetak isi (data) node yang sedang dikunjungi

2. Kunjungi kiri node tersebut,

- Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama,

terapkan untuk kiri tersebut.

- Jika kiri kosong (NULL), lanjut ke langkah ketiga.

3. Kunjungi kanan node tersebut,

- Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama,

terapkan untuk kanan tersebut.

- Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses

yang sama untuk node yang dikunjungi sebelumnya.

tambah(&pohon,data);

void tambah(Node **root,int databaru){

if((*root) == NULL){

Node *baru;

baru = new Node;


baru->kiri = NULL;

baru->kanan = NULL;

(*root) = baru;

(*root)->kiri = NULL;

(*root)->kanan = NULL;

}

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

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

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

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

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

printf("Data sudah ada!");

}

52

b. Kunjungan In-Order.




- Jika kiri kosong (NULL), lanjut ke langkah kedua.

2. Cetak isi (data) node yang sedang dikunjungi




- Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses

yang sama untuk node yang dikunjungi sebelumnya.

c. Kunjungan Post-Order.




- Jika kiri kosong (NULL), lanjut ke langkah kedua.




- Jika kanan kosong (NULL), lanjut ke langkah ketiga.

3. Cetak isi (data) node yang sedang dikunjungi. Proses untuk node ini selesai,

tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

void postOrder(Node *root){

if(root != NULL){

postOrder(root->kiri);

postOrder(root->kanan);

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

}

}

void inOrder(Node *root){

if(root != NULL){

inOrder(root->kiri);


inOrder(root->kanan);

}

}

void preOrder(Node *root){

if(root != NULL){


preOrder(root->kiri);

preOrder(root->kanan);

}

}

53

Variabel **root pada setiap fungsi diatas menunjukkan node mana yang sedang

dikunjungi saat ini, untuk itu saat pemanggilan, variabel **root kita beri nilai

pointer yang menunjuk ke node akar, yaitu pohon.

Untuk selengkapnya dapat dilihat pada bagian 5, kode program lengkap.

5. Kode Program Lengkap

Berikut ini kode program keseluruhan, termasuk menu tampilan, di mana di

dalamnya terdapat Deklarasi Tree, Inisialisasi Tree, Penambahan Node, dan

Pembacaaan serta Menampilkan Node dengan 3 macam kunjungan. Kode ditulis

dengan C++ 3.00.

#include <stdio.h>

#include <conio.h>

typedef struct Node{

int data;

Node *kiri;

Node *kanan;

};

void tambah(Node **root,int databaru){

if((*root) == NULL){

Node *baru;

baru = new Node;


baru->kiri = NULL;

baru->kanan = NULL;

(*root) = baru;

(*root)->kiri = NULL;

(*root)->kanan = NULL;

printf("Data bertambah!");

}

preOrder(pohon);

inOrder(pohon);

postOrder(pohon);

54

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

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

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

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

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

printf("Data sudah ada!");

}

void preOrder(Node *root){

if(root != NULL){


preOrder(root->kiri);

preOrder(root->kanan);

}

}

void inOrder(Node *root){

if(root != NULL){

inOrder(root->kiri);


inOrder(root->kanan);

}

}

void postOrder(Node *root){

if(root != NULL){

postOrder(root->kiri);

postOrder(root->kanan);


}

}

void main(){

int pil,c;

Node *pohon,*t;

pohon = NULL;

do{

clrscr();

int data;

printf("MENU\n");

printf("1. Tambah\n");

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

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

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

printf("5. Exit\n");

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

switch(pil){

case 1: printf("Data baru : ");scanf("%d",

&data);

tambah(&pohon,data);

break;

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

else printf("Masih kosong!");

break;

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


break;

55

Soal

Berikut ini beberapa latihan yang dapat dicoba, setelah selesai cek hasil kerja anda

bersama asisten praktikum.

1. Buatlah fungsi untuk menghitung jumlah node keseluruhan pada pohon biner.

Penghitungan dilakukan dengan menjelajahi isi pohon, bukan dengan

menambahkan counter saat setiap data baru dimasukkan!.

2. Buatlah fungsi untuk mencetak semua leaf (daun) yang ada pada pohon biner.

3. Buatlah fungsi untuk mencetak nilai node minimum (terkecil) pada pohon biner.

4. Tanpa mencobanya pada kompiler C++, analisislah untuk apa fungsi F di bawah

ini:

5. Tanpa mencobanya pada kompiler C++, analisislah untuk apa fungsi G di bawah

ini, dan nilai yang dikembalikan berupa apa?

Node *G(Node *root)

{

if(root == NULL)

return NULL;

else

if(root->kanan == NULL)

return root;

else

return G(root->kanan);

}

int F(Node *root)

{

if (root == NULL) return -1;

int u = F(root->kiri), v = F(root->kanan);

if (u > v) return u+1;

else return v+1;

}

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


break;

}

getch();

}while(pil!=5);

}

fathoni m bahan ajar_if2018_prak.struktur data

Education