PENYAJIAN
(TUTORIAL)
A. Konsep Dasar Struktur Data
Struktur
data adalah sebuah bagian dari ilmu pemrograman dasar yang mempunyai
karakteristik yang terkait dengan sifat dan cara penyimpanan sekaligus
penggunaan atau pengaksesan data.
Struktur
data bertujuan agar cara merepresentasikan data dalam membuat program dapat
dilakukan secara efisien dalam pengolahan di memori dan pengolahan penyimpanan
dari program ke strorage juga lebih mudah dilakukan.
B. Konsep Dasar Array
Array
adalah kumpulan elemen – elemen data. Kumpulan elemen tersebut
mempunyai susunan tertentu yang teratur. Jumlah elemen terbatas, dan semua
elemen mempunyai tipe data yang sama. Jenis-jenis array:
1. Array satu dimensi
Struktur
array satu dimensi dapat dideklarasikan dengan bentuk umum berupa: tipe_var
nama_var [ukuran];
Dengan:
- Tipe_var :
untuk menyatakan jenis elemen array (misalnya int, char, unsigned)
- Nama_var : untuk
menyatakan nama variable yang dipakai.
- Ukuran : untuk
menyatakan jumlah maksimal elemen array.
Contoh
: float nilai_ujian [5];
2. Array Dua Dimensi
Tipe
data array dua dimensi biasa digunakan untuk menyimpan, mengolah maupun
menampilkan suatu data dalam bentuk tabel atau matriks. Untuk mendeklarasikan
array agar dapat meyimpan data adalah :
tipe_var nama_var
[ukuran1][ukuran2];
Dimana
- Ukuran1
menunjukkan jumlah/nomer baris.
- Ukuran2
menunjukkan jumlah/nomor kolom.
Jumlah
elemen yang dimiliki array dua dimensi dapat ditentukan dari hasil perkalian :
ukuran1
x ukuran2
Seperti
halnya pada array satu dimensi, data array dua dimensi akan ditempatkan pada
memori secara berurutan.
Array
Multidimensi/Dimensi Banyak.
Array
berdimensi banyak atau multidimensi terdiri dari array yang tidak terbatas
hanya dua dimensi saja. Bentuk umum pendeklarasian array multidimensi adalah :
tipe_var nama_var[ukuran1][ukuran2]…[ukurann];
Contoh
: int data_angka [3][6][6];
Yang
merupakan array tiga dimensi.
Mengakses Elemen Array :
Dalam Bahasa C++, data array akan disimpan dalam memory pada
alokasi yang berurutan.
Elemen pertama biasanya mempunyai indeks bernilai 0. Contoh
:
Float nilai_tes[5];
Jika pada contoh di atas, variable nilai_tes mempunyai 5
elemen, maka elemen pertama mempunyai indeks sama dengan 0, elemen kedua
mempunyaiindeks 1, dan seterusnya. Bentuk umum pengaksesan suatu elemen
variable array adalah :
Nama_var[indeks];
Gambar berikut memperlihatkan urutan komponen array memori.
Untuk
variable array nilai_tes :
Gambar
1.1 Struktur Array Satu Dimensi
Inisialisasi Array :
Array dapat diinisialisasikan secara langsung saat pertama
kali dideklarasikan (efisien
untuk array berdimensi sedikit).
Contoh : int x[2]={1,2};
Array dapat dideklarasikan terlebih dahulu, baru kemudian
diisi elemennya.
Contoh :
Int x[2];
X[0]=1;
X[1]=2;
A. Konsep
Dasar Pointer
Pointer
adalah sebuah variable yang berisi lamat variable yang lain. Suatu pointer
dimaksudkan untuk menunjuk ke suatu alamat memori sehingga alamat dari suatu
variable dapat diketahui dengan mudah. Deklarasi pointer :
Operator pointer :
Operator
‘&’ : untuk mendapatkan alamat memori operand / variabel pointer ‘*’ :
untuk mengakses nilai data operand / variable pointer.
B. Konsep
Dasasr Struktur
Struktur
adalah koleksi dari variabel yang dinyatakan dengan sebuah nama, dengan sifat
setiap variabel dapat memiliki tipe yang berlainan. Struktur biasa dipakai
untuk mengelompokkan beberapa informasi yang berkaitan menjadi sabuah satu
kesatuan. Contoh sebuah struktur adalah informasi data tanggal, yang berisi
tanggal, bulan, dan tahun.
Mendeklarasikan Struktur :
Contoh pendefinisian tipe data
Struktur adalah : struct
Data_tanggal
{int tanggal;
Masing-masing
tipe dari elemen struktur dapat berlainan. Adapun variable_struktur1 sampai
dengan variabel_struktur M menyatakan bahwa variablel struktur yang
dideklarasikan bisa lebih dari satu.jika ada lebih dari satu variable, antara
variabel struktur dipisahkan dengan tanda koma.
Mengakses Elemen Struktur :
Elemen dari struktur dapat diakses dengan menggunakan bentuk
:
Variable_struktur.nama_field
Antara variabel_struktur dan nama_field dipisahkan dengan
operator titik (disebut operator anggota struktur). Contoh berikut merupakan
instruksi
Tgl_lahir.tang
Gal=30 int
Bulan;
Int
tahun;
}
Yang mendefinisikan tipe struktur Bernama data_tanggal, yang
terdiri dari tiga buah elemen berupa tanggal, bulan, dan tahun. Bentuk umum
dalam mendefinisikan dan mendeklarasikan struktur adalah :
Struct
nama_tipe_struktur
{
Tipe
Field1
; Tipe
Field2
; Tipe
Field3
;
}variabel_struktur1....
variabel_strukturM;
LEMBAR KERJA DAN TUGAS
1. Program pangkat dengan array dimensi satu.
#include <stdio.h>
#include <iostream>
#include <conio.h>
using namespace std ;
int main()
{
int
square[100]; // --> Array 1 dimensi dengan tempat yang dipesan sebanyak 100
int
i;
int
k;
//perhitungan
for
(i = 0; i < 10; i++) // angka yang ditampilkan 1-10
{
k
= i + 1;
square[i]
= k * k;
printf("\n
Pangkat dari %d adalah %d", k, square[i]);
}
_getch();
}
2. Array
dimensi dua
#include <stdio.h>
#include <iostream>
#include <conio.h>
using namespace std ;
void printArray(int [][3]);//-->penulisan array 2
dimensi
int main()
{
//pengisian
elemen array
int
matrik1[2][3]={{1,2,3},{4,5,6}},matrik2[2][3]={1,2,3,4,5},matrik3[2][3]={{1,2},{4}};
printArray(matrik1);
printArray(matrik2);
printArray(matrik3);
_getch();
}
//prosedur tampilan array
void printArray(int a[][3])
{
int
i, j;
for
(i = 0; i<=1; i++)
{
for
(j = 0; j<=2; j++)
printf("%d
", a[i][j]);;
printf("\n");
}
}
3. Program
pointer
#include <stdio.h>
#include <iostream>
#include <conio.h>
using namespace std ;
//cetak p dan *p
int main(void)
{
int
v
= 7, *p; //untuk mengakses nilai data
p
= &v; //untuk mendapatkan alamat memori
cout<<"Nilai
v = " <<v;
cout<<endl;
cout<<endl;
cout<<"Nilai
*p = " <<*p;
cout<<endl;
cout<<endl;
cout<<"Alammatnya
= "<<p;
_getch()
;
}
4. Mendaklarasikan
struktur, memasukkan struktur, dan menampilkan data struktur.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
using namespace std ;
#define MAX 10 //--> max untuk nilai
struct dtnilai //--> prosedur sstructur
{
char
nim[12];
char
name[20];
double
nilai[MAX];
};
int main()
{
struct
dtnilai data;
int
i, jml;
char
strnilai[5], strjum[5];
printf("NIM
: ");
gets(data.nim);
cout<<endl;
printf("Nama
: ");
gets(data.name);
cout<<endl;
printf("Jumlah
Test : ");
gets(strjum);
jml
= atoi(strjum);
cout<<endl;
for(i
= 0; i<jml; i++)
{
printf("Nilai
Test %d : ", i+1);
gets(strnilai);
data.nilai[i]
= atof(strnilai);
}
cout<<endl;
printf("DATA MAHASISWA YANG TELAH
DIINPUTKAN : \n");
cout<<endl;
printf("NIM
: %t\n", data.nim);
cout<<endl;
printf("Nama
: %s\n", data.nama);
cout<<endl;
for(i
= 0; i<jml; i++)
{
printf("Nilai
Test %d : %lf\n", i+1, data.nilai[i]);
}
_getch();
}
5. Memesan
tempat memory, mendeklarasikan member nilai, mengcopy alamat pointer.
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
using namespace std ;
void p(void) ;
int *a, *b;
int main()
{
p();
}
void p(void)
{
a
= (int *)malloc(sizeof(int));
b
= (int *)malloc(sizeof(int));
*a
= 19;
*b
= 5;
a
= b;
*b
= 8;
printf("Alamat
a = %x\t Isi a = %d\n", a, *a);
printf("Alamat
b = %x\t Isi b = %d\n", b, *b);
_getch;
}
TUGAS
1. Buatlah program menggunakan
POINTER untuk merubah karakter yang dimasukkan dari huruf kecil menjadi huruf
besar.
2. Buatlah program untuk
perhitungan karakter dengan ARRAY.
3. Buatlah program array dalam
struktur, yang menampilkan judul film dan tahun terbit dari data yang telah
diinputkan. Data yang dimasukkan sebanyak.
Jawab
:
1. Program
#include
<stdio.h>
#include
<ctype.h>
#include
<iostream>
#include
<conio.h>
#include
<stdio.h>
#include
<cstdlib>
#include
<string.h>
using
namespace std;
int
main ()
{
int
a=0;
char
nama[100];
char
b;
cout<<"MASUKKAN
HURUF BESAR YANG AKAN DIRUBAH MENJADI HURUF KECIL\n"<<endl;
gets(nama);
system("CLS");
cout<<"HURUF
VERSI lowercase (HURUF KECIL) dari
"<<nama<<"\n"<<endl;
while
(nama[a])
{
b=nama[a];
if
(isupper(b)) b=tolower(b);
putchar
(b);
a++;
}
}
2. Perhitungan karakter dengan
ARRAY.
#include
<stdio.h>
#include
<string.h>
int
main()
{
char
kalimat[100];
int
jumlah;
printf("Masukkan
sebuah string: " );
fgets(kalimat,
sizeof(kalimat), stdin);
jumlah
= strlen(kalimat)-1;
printf("Jumlah
karakter adalah %d\n", jumlah);
return
0;
}
3. Program array dalam
struktur.
#include
<stdio.h>
#include
<string.h>
#include
<stdlib.h>
#include
<iostream>
#include
<conio.h>
using
namespace std;
#define
MAX 10 //-->mx untuk nilai
struct
dtnilai//-->prosedur structur
{
char
film[20];
char
tahun[5];
char
film1[20];
char
tahun1[5];
char
film2[20];
char
tahun2[5];
double
nilai[MAX];
};
int
main()
{
struct
dtnilai data;
int
i, jml;
char
strnilai[5], strjum[5];
printf("Masukkan
Judul Film : ");
gets(data.film);
cout<<endl;
printf("Masukkan
Tahun Terbit : ");
gets(data.tahun);
cout<<endl;
printf("Masukkan
Judul Film : ");
gets(data.film1);
cout<<endl;
printf("Masukkan
Tahun Terbit : ");
gets(data.tahun1);
cout<<endl;
printf("Masukkan
Judul Film : ");
gets(data.film2);
cout<<endl;
printf("Masukkan
Tahun Terbit : ");
gets(data.tahun2);
cout<<endl;
cout<<endl;
printf("Film
yang menjadi favorit kamu : \n");
cout<<endl;
printf(data.film);
cout<<"
(";
printf(data.tahun);
cout<<")";
cout<<endl;
printf(data.film1);
cout<<"
(";
printf(data.tahun1);
cout<<")";
cout<<endl;
printf(data.film2);
cout<<"
(";
printf(data.tahun2);
cout<<")";
cout<<endl;
cout<<
cout<<endl;
_getch();
}
POKOK
BAHASAN 2
Linked List
(Senarai)
PENDAHULUAN
Pada pokok
bahasan ini akan dibahas mengenai sruktur data senarai (list) yang
pembahasannya meliputi definisi dan representasi list, jenis-jenis list serta
oerasi- operasi dasar pada list. Sehingga setelah mempelajari bab ini
diharapkan maahasiswa mampu :
a. Menjelaskan definisi dan
representasi list.
b. Mengetahui jenis-jenis list.
c. Memahami operasi-operasi
pada list.
PENYAJIAN
(TUTORIAL)
Linked
list adalah sejumlah objek atau
elemen yang dihubungkan satu dengan lainnya sehingga membentuk suatu list.
Sdangkan objek atau elemen itu sendiri adalah merupakan gabungan beberapa data
(variabel) yang dijadikan satu kelompok atau structure atau record yang
dibentuk dengan perintah struct. Untuk menggabungkan objek satu
dengan lainnya, diperlukan paling tidak sebuah variabel yang bertipe pointer.
Syarat linked list adalah harus adapat diketahui alamat simpul
pertama atau biasa dipakai variabel First/Start/Header. Struktur
dasar sebuah list seperti gambar berikut :
Gambar 2.1
List Tunggal
Istilah
- istilah dalam linked list :
- Simpul
Simpul
terdiri dari dua bagian yaitu :
a. Bagian data
b. Bagian pointer yang menunjuk
ke simpul berikutnya
- First/Header
Variabel
First/Header berisis alamat (pointer)/acuan (reference) yag
menunjuk lokasi simpul pertama linked list, digunakan sebagai
awal penelusuran linked list.
- Nil/Null
Tidak
bernilai, digunakan untuk menyatakan tidak mengacu ke manapun.
- Simpul Terakhr
(Last)
Simpul
terakhir linked list berari tidak menunjuk simpul berikutnya. Tidak terdapat
alamat disimpan di field pointer (bagian kedua dari simpul).
Nilai null atau nil disimpan di field pointer di simpul
terakhir.
Jenis - jenis linked list:
List
kosong
List
kosong hanya terdiri dari sebuah petujuk elemen yang berisi NULL (kosong),
tidak memiliki satu buah elemen pun sehigga hanya berupa penunjuk awal elemn
berisi NULL.
List
Tunggal
List
tuggal adalah list yang elemenya hanya menyimpan informasi elemen
setelahnya (next), sehingga jalanya pengaksessan list hanya
dapat dilakukan secara maju. List tuggal terbagi menjadi tiga jenis yaitu list
tunggal dengan kepala first), list tunggal kepala first) dan
ekor (tail), serta list tunggal yang berputar.
Gambar
2.2 List Tunggal dengan Kepala dan Ekor, List Tunggal Berputar
List
Ganda
List ganda adalah sebuah list yang elemenya menyimpan
informasi elemen sebelumnya dan informasi elemen setelahnya, sehingga proses
penelusuan list dapat dilakukan secara maju dan mundur. List ganda terbagi
menjadi tiga jenis yaitu list ganda engan kepala (first), list
ganda dengan kepala (first) dan ekor (tail), serta
list ganda yag berputar.
Gambar 2.3
List ganda dengan Kepala, List ganda dengan Kepala dan
Ekor
Operasi Dasar pada Linked List :
IsEmpty :
Fungsi ini menentukan apakan linked list kosong atau tidak.
Size :
operasi untuk mengirim jumlah elemen di linked list.
Create :
operasi untuk penciptaan list baru yang kosong.
Insertfirst:
operasi penyisipan simpul sebagai simpul pertama.
Insertafter :
operasi untu penyisispan simpul setelah simpul tertentu.
Insertlast:
operasi untuk penyisipan simpul sebagai simpul terakhir.
Insertbefore :
operasi untuk penyisipan simpul sebelum simpul tertentu.
Deletefirst:
operasi penghapusan simpul pertama.
Deleteafter :
operasi penghapusan setelah simpul tertentu.
Deletelast:
operasi penghapusan simpul terakhir.
LEMBAR KERJA DAN TUGAS
1. Contoh
program sisip senarai.
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
using namespace std;
typedef struct nod
{
int
data;
struct
nod *next;
}NOD, *NODPTR;
void CiptaSenarai(NODPTR *s)
{
*s
= NULL;
}
NODPTR NodBaru(int m)
{
NODPTR
n;
n
= (NODPTR) malloc (sizeof(NOD));
if
(n != NULL)
{
n->data=m;
n->next
= NULL;
}
return
n;
}
void SisipSenarai(NODPTR *s, NODPTR t, NODPTR p)
{
if(p==NULL)
{
t->next=*s;
*s=t;
}
else
{
t->next=p->next;
p->next=t;
}
}
void CetakSenarai(NODPTR s)
{
NODPTR
ps;
for
(ps=s; ps!=NULL; ps=ps->next)
printf("%d
--> ", ps->data);
printf("NULL\n");
}
int main()
{
NODPTR
pel;
NODPTR
n;
CiptaSenarai(&pel);
n=NodBaru(55);
SisipSenarai(&pel,
n, NULL);
n=NodBaru(75);
SisipSenarai(&pel,
n, NULL);
CetakSenarai(pel);
_getch();
}
HASIL :
2. Single
linked list.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
using namespace std ;
struct dtnilai *tampung;
struct dtnilai *ujung;
struct dtnilai *awal;
int j;
char strnilai[5], jawab[6];
struct dtnilai
{
char
nim[10];
char
nama[20];
double
nilai;
struct
dtnilai *next;
};
int main()
{
printf("DATA
MAHASISWA : \n");
printf("==================================\n");
printf("\n");
while(1)
{
if(j==0)
{
awal=(struct
dtnilai*)malloc(sizeof(struct dtnilai));
printf("NIM
: ");
gets(awal->nim);
printf("\n");
printf("Nama
: ");
gets(awal->nama);
printf("\n");
printf("Nilai
Test : ");
gets(strnilai);
printf("\n");
awal->nilai
= atof(strnilai);
tampung=awal;
tampung->next=NULL;
}
else
{
ujung=(struct
dtnilai*)malloc(sizeof(struct dtnilai));
tampung->next=ujung;
printf("NIM
: ");
gets(ujung->nim);
printf("\n");
printf("Nama
: ");
gets(ujung->nama);
printf("\n");
printf("Nilai
Test : ");
gets(strnilai);
printf("\n");
ujung->nilai
= atof(strnilai);
tampung=ujung;
tampung->next=NULL;
}
printf("Masukkan
Data Lagi ? (IYA/TIDAK) : ");
gets(jawab);
printf("\n");
if(strcmp(jawab,
"iya")==0 || strcmp(jawab, "IYA")==0)
{
j++;
continue;
}
else
if(strcmp(jawab, "tidak")==0 || strcmp(jawab, "TIDAK")==0)
break;
}
}
HASIL:
3. Menghapus
data pada simpul tertentu.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
using namespace std ;
struct dtnilai
{
char
nim[15];
char
nama[20];
double
nilai ;
struct
dtnilai *next;
};
int main ()
{
printf("DATA
MAHASISWA : \n");
printf("=======================\n");
struct
dtnilai *tampung;
struct
dtnilai *ujung;
struct
dtnilai *awal;
struct
dtnilai *tanda;
struct
dtnilai *tanda2;
char
strnilai[10];
char
jawab[5];
char
hapus[5];
int
j=0;
while
(1)
{
if(j==0)
{
awal=(struct
dtnilai*)malloc(sizeof(struct dtnilai));
printf("NIM
: ");
gets(awal->nim);
printf("\n");
printf("Nama
: ");
gets(awal->nama);
printf("\n");
printf("Nilai
Test : ");
gets(strnilai);
printf("\n");
awal->nilai
= atof(strnilai);
tampung=awal;
tampung->next=NULL;
}
else
{
ujung=(struct
dtnilai*)malloc(sizeof(struct dtnilai));
tampung->next=ujung;
printf("NIM
: ");
gets(ujung->nim);
printf("\n");
printf("Nama
: ");
gets(ujung->nama);
printf("\n");
printf("Nilai
Test : ");
gets(strnilai);
printf("\n");
ujung->nilai=atof(strnilai);
ujung->next=NULL;
tampung=ujung;
}
printf("Masukkan
Data Lagi? (y/t) : ");
gets
(jawab);
printf("\n");
if(strcmp(jawab,"Y")==0||strcmp(jawab,"y")==0)
{
j++;
continue;
}
else
if((strcmp(jawab,"T")==0||strcmp(jawab,"t")==0))
break;
}
printf("\nData
Mahasiswa yang Diinputkan : \n");
printf("=========================================\n");
printf("NIM
\tNama \tNilai\n");
ujung=awal;
while
(ujung!=NULL)
{
printf("%s\t%s\t%6.2f\n",ujung->nim,ujung->nama,ujung->nilai);
ujung=ujung->next;
}
while(1)
{
printf("\n");
printf
("NIM yang akan dihapus (NIM/(t/T)) : \n");
gets
(hapus) ;
if
((strcmp (hapus, "t")==0 ||strcmp(hapus,"T")==0))
{
printf
("Masukkan NIM\n");
continue;
}
else
break;
}
if
(strcmp(awal -> nim,hapus)==0)
{
tanda=awal->next;
free
(awal);
awal=tanda;
}
else
{
tanda2=awal;
tanda=tanda2->next;
while
(tanda!=NULL)
{
if
(strcmp(tanda->nim,hapus)==0)
{
if(tanda->next!=NULL)
tanda2->next=tanda->next;
else
tanda2->next=NULL;
free
(tanda);
break;
}
tanda2=tanda;
tanda=tanda->next;
}
}
printf("\n");
printf ("Data Mahasiswa yang telah Dihapus (FIFO):\n");
printf("===============================================\n");
printf ("NIM \tNama \tNilai\n");
ujung=awal;
while (ujung!=NULL)
{
printf
("%s\t%s\t%6.2f\n", ujung ->nim, ujung -> nama,ujung
->nilai);
ujung=ujung
-> next;
}
_getch();
}
Hasil :
TUGAS
1. Buatlah
progam untuk menampilkan 10 bilangan secara menurun yaitu 10,9,8 sampai 1
dengan menggunakan LINKED LIST.
2. Buatlah
sebuah progam yang mengimplementasikan Linked List,dimana data yang di pakai
adalah data bukuyang ada dalam sebuah perpustakan (ID Buku,Judul, dan jumlah
buku).progam juga mengiplementasikan penambahan dan pengurangan simpul pada
Linked List berdasarkan ID buku.
HASIL
:
1. Program
#include
<iostream>
using
namespace std;
int
main()
{
int
i=10;
while(i>=1)
{
cout<<"
"<< i ;
i--;
}
cout<<endl;
system("pause");
}
Hasil
:
2. Program
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<conio.h>
using
namespace std;
struct
dtjumlah
{
char
ID[15];
char
judul[20];
double
jumlah;
struct
dtjumlah *next;
};
int
main()
{
printf("DATA
BUKU : \n");
printf("=====================================\n");
struct
dtjumlah *tampung;
struct
dtjumlah *ujung;
struct
dtjumlah *awal;
struct
dtjumlah *tanda;
struct
dtjumlah *tanda2;
char
strjumlah[10];
char
jawab[5];
char
hapus[5];
int
j=0;
while
(1)
{
if(j==0)
{
awal=(struct
dtjumlah*)malloc(sizeof(struct dtjumlah));
printf("ID :
");
gets(awal->ID);
printf("\n");
printf("judul :
");
gets(awal->judul);
printf("\n");
printf("Jumlah :
");
gets(strjumlah);
printf("\n");
awal->jumlah
= atof(strjumlah);
tampung=awal;
tampung->next=NULL;
}
else
{
ujung=(struct
dtjumlah*)malloc(sizeof(struct dtjumlah));
tampung->next=ujung;
printf("ID :
");
gets(ujung->ID);
printf("\n");
printf("Judul :
");
gets(ujung->judul);
printf("jumlah :
");
gets(strjumlah);
printf("\n");
ujung->jumlah=atof(strjumlah);
ujung->next=NULL;
tampung=ujung;
}
printf("Masukkan
Data lagi? (y/t) : ");
gets(jawab);
printf("\n");
if(strcmp(jawab,
"y")==0||strcmp(jawab,"Y")==0)
{
j++;
continue;
}
else
if((strcmp(jawab,"T")==0||strcmp(jawab,"t")==0))
break;
}
printf("\nData
buku yang Diinputkan : \n");
printf("===========================================\n");
printf("ID\tjudul\t\tjumlah\n");
ujung=awal;
while
(ujung!=NULL)
{
printf("%s\t%s\t%6.2f\n",ujung->ID,ujung->judul,ujung->jumlah);
ujung=ujung->next;
}
while(1)
{
printf("\n");
printf("ID
yang akan dihapus
(ID/(t/T)) : \n");
gets
(hapus);
if
((strcmp (hapus, "t")==0 ||strcmp(hapus,"T")==0))
{
printf
("Masukkan ID\n");
continue;
}
else
break;
}
if(strcmp(awal
-> ID,hapus)==0)
{
tanda=awal->next;
free
(awal);
awal=tanda;
}
else
{
tanda2=awal;
tanda=tanda2->next;
while
(tanda!=NULL)
{
if
(strcmp(tanda->ID,hapus)==0)
{
if(tanda->next!=NULL)
tanda2->next=tanda->next;
else
tanda2->next=NULL;
free
(tanda);
break;
}
tanda2=tanda;
tanda=tanda->next;
}
}
printf("\n");
printf("Data
Buku yang telah Dihapus (FIFO) : \n");
printf("============================================\n");
printf("ID\tjudul\t\tjumlah\n");
ujung=awal;
while
(ujung!=NULL)
{
printf
("%s\t%s\t%6.2fn",ujung ->ID, ujung ->judul,ujung ->jumlah);
ujung=ujung
-> next;
}
getch();
cout<<endl;
}
POKOK
BAHASAN 3
Struktur
Pemrograman: Berkondisi
PENDAHULUAN
Pada pokok
bahasan ini akan dibahs mengenai struktur datatumpukan atau stack, dimana stack
merupakan suatu kumpulan data yang seolah-olah ada data yang diletakkan di ats
data yang lain. Setelah mempelajari materi ini diharapkan mahasiswa mampu untuk
:
a. Mengetahui dan memahami
definisi stack.
b. Memahami operasi-operasi
dasar stack.
c. Memahami representasi statis
dan dinamis stack.
PENYAJIAN
(TUTORIAL)
Stack
adalah kumpula elemen-elemen yang tersimpan dalam suatu tumpukan. Aturan
penyisispan dan penghapusan elemennya tertentu :
- Penyisispan
selalu dilakukan “di atas “ TOP
- Penghapusan
selalu dilakukan pada TOP
Karena
aturan penyisipan dan penghapusan semacam itu, TOP adalah satu- satunya alamat
tempat terjadi operasi, elemen yang ditambahkan paling akhir akan menjadi
elemen yang akan dihapus. Dikatakan bahwa elemen Stack tersususn secara
LIFO (Last In First Out).
Seperti
halnya jika kita mempunyai sebuah tumpukan buku, agar tumpukan buku itu tidak
ambruk ketika kita mengambil sebuah buku di dalam tumpukan itu amaka harus
diambil satu per satu dari tumpukan yang paling atas dari tumpukan.
Gambar 3.1
Ilustrasi Stack
Perhatikan
bahwa dengan definsi semacam ini, representasi tabel sangat tepat untuk
mewakili stack, karena operasi penambahan dan pengurangan hanya dilakukan
disalah satu ujung tabel.
Beberapa
contoh penggunaan stack adalah pemanggilan prosedur, perhitugan ekspresi
aritmatika, rekursifitas, backtracking, peaganan interupsi, dan lain-lain.
Karakteristik penting stack sebagai berikut :
1. Elemen stack yaitu item-item data
di elemen stack
2. TOP (elemen puncak
dari stack)
3. Jumlah elemen pada stack
4. Status/kondisi stack, yaitu
:
- Penuh
Bila
elemen di tumpukan mencapai kapasitas maksimum tumpukan. Pada kondisi ini,
tidak mungkin dilakukan penambahan ke tumpukan.Penambahan di elemen
menyebabakan kondisi kesalahan Overflow.
- Bila
tidak ada elemen tumpukan. Pada kondisi ini, tidak mungkin dilakukan
pengambilan elemen tumpukan. Pengambilan elemen menyebabkan kondisi
kesalahan Underflow.
Stack
memiliki operasi-operasi pokok sebagai berikut :
Push : Untuk
menambahkan item pada tumpukan paling atas.
void
Push (itemType x, Stack*S)
{
Printf(“Stack FULL”);
else
{
S->item[S->Count]=x;
++(S->count);
}
}
Pop
: Untuk mengambil item teratas
int
Pop (Stack S, itemType x)
{
if
(Empty (S))
Printf(“Stack Kosong”);
else
{
-(S->Count);
x=s->item(s->Count);
}
}
Clear :
Untuk mengosongkan stack
void
InitializeStack (Stack S)
{
S->Count=0;
}
IsEmpty :
Untuk memerikasa apakah stack kosong
int Empty
(Stack *S)
{
return (S->Count==0);
}
IsFull :
Untuk memeriksa apakah stack sudah penuh
int Full
(Stack S)
{
return(S->Count==MAX S TACK);
}
Representasi
stack :
-
Representasi statis
Stack
dengan representasi statis biasanya diinplementasikan dengan menggunakan array.
Sebuah array memiliki tempat yang dialokasikan diawal sehingga sebuah elemen
yang dimasukan dalam sebuah array terbatas pada tempat yang ada pada array.
Karena menggunakan array maka stack dengan representasi statis dalam mengalami
kondisi elemen penuh. Ilustrasi stack dengan representasi statis dapat dilihat
pada gambar 3.2 :
Gambar 3.2 Representasi Stack Statis
-
Representasi dinamis
Stack
dengan representasi dinamis biasanya diimplementasikan dengan menggunakan
pointer yang mnunjuk pada elemen-elemen yang dialokasikan pada memori.
Illustrasi stack dengan representasi dinamis dapat dilihat pada gambae 3.3 :
Gambar
3.3 Representasi Stack Dinamis
Karena
semua operasi pada sebuah stack diawali dengan elemen yang paling atas maka
jika menggunakan representasi dinamis saat elemen ditambahkan akan mengguakan
penambahan elemenpada awal stack (addfirst) dan saat
pengambilan atau penghapusan elemen menggunakan penghapusan di awal stack (delfrst).
LEMBAR KERJA DAN TUGAS
1. Program
stack
#include <stdio.h>
#include <iostream>
#include <conio.h>
#define MAXSTACK 3
typedef int itemType;
typedef struct
{
int item[MAXSTACK];
int jml;
}Stack;
void init(Stack *s)
{
s->jml=0;
}
int kosong(Stack *s)
{
return (s->jml==0);
}
int penuh(Stack *s)
{
return (s->jml==MAXSTACK);
}
int isi(itemType x, Stack *s)
{
if (penuh(s))
printf("\nMAAF!!! Data PENUH\n");
else{
s->item[s->jml]=x;
++(s->jml);
}
}
int ambil(Stack *s, itemType *x){
if (kosong(s))
printf("\nMaaf Data Kosong\n");
else
{
--(s->jml);
*x=s->item[s->jml];
s->item[s->jml]=0;
printf("\nData %i Berhasil Diambil\n",*x);
}
}
int tampil(Stack *s){
if (kosong(s))
printf("\nMaaf Data Masih Kosong\n");
else
printf("\n");
for(int i=s->jml-1; i>=0; i--){
printf("Data : %d\n", s->item[i]);
}
}
int hapus(Stack *s){
s->jml=0;
printf("\nSemua Data Berhasil Dihapus\n");
}
int main(){
int pil;
Stack tumpukan;
itemType data;
init(&tumpukan);
do{
printf("\nMENU: \n 1. Isi (Data Angka)\n 2. Ambil\n 3. Lihat\n 4. Hapus
(Hapus Semua Data)\n 5. Keluar\n");
printf("\n");
printf("Masukkan Pilihan : ");
scanf("%i",&pil);
switch(pil){
case 1 :
printf("\nMasukkan Data Angka : ");
scanf("%i",&data);;isi(data, &tumpukan);
break;
case 2 :
ambil(&tumpukan,&data);
break;
case 3 :
tampil(&tumpukan);
break;
case 4 :
hapus(&tumpukan);
break;
}
}while(pil!=5);
_getch;
}
Hasil :
2. Mendeklarasikan,
memasukan, dan menampilkan elemen data pada sebuah stack dengan menggunakan
array :
#include<stdio.h>
#include<iostream>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define MAX 10
struct ttumpukan
{
int elm[MAX];
int puncak ;
};
struct ttumpukan t;
int top;
void inisialisasi()
{
t.puncak=0;
top=0;
}
void push(int x)
{
if(t.puncak==MAX)
printf("Stack Sudah Penuh");
else
{
t.puncak=top+1;
t.elm[t.puncak]=x;
top=t.puncak;
printf("PUSH %d : %d\n", t.puncak,t.elm[t.puncak]);
}
}
void pop()
{
if(top==0)
printf("Stack Kosong\n");
else
{
printf("\nPOP %d = %d\n", top,t.elm[top]);
t.puncak=top-1;
top=t.puncak;
}
}
int main()
{
int i, jum;char strnilai[5], strjum[5];
inisialisasi();
printf("Masukkan Jumlah Data : "); gets(strjum);
printf("\n");
jum=atoi(strjum);
for(i=0;i<jum;i++)
{
printf("Nilai Interger %d : ",1+1);
gets(strnilai); push(atoi(strnilai));
printf("\n");
}
for(i=jum;i>0;i--)
printf("Elemen Data : %d\n,", t.elm[i]);for(i=0;i<jum;i++)
pop();
_getch();
}
Hasil :
3. Merepresentasikan
stack menggunakan Linked List :
#include<stdio.h>
#include<iostream>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
struct stack
{
int isi;
struct stack*next;
};
int x,i=1,j=1;
struct stack*atas,*bantu,*baru;
void push (int nilai)
{
if(j==1)
{
atas=(struct stack*)malloc(sizeof(struct stack));
atas->isi=nilai;
atas->next=NULL;
}
else
{
baru=(struct stack*)malloc(sizeof(struct stack));
baru->isi=nilai;
baru->next=atas;
atas=baru;
}
j++;
}
void pop()
{
bantu=atas;
printf("Data yang di POP %d : %d\n" ,i,bantu->isi);
atas=atas->next;
i++;
free(bantu);
}
int main()
{
char jawab[2],strNilai[5];
while(1)
{
printf("data yang di PUSH ke %d : ",j);
gets(strNilai);
x=atoi(strNilai);
push(x);
printf("Data lagi? <y/t> : ");
gets(jawab);
if((strcmp(jawab,"Y")==0)||(strcmp(jawab,"y")==0))
continue;
else
break;
}
j--;
printf("Data nilai yang telah diinputkan:\n");
while(atas!=NULL)
pop();
_getch();
}
TUGAS
1. Buatlah
progam stack statis yang menampilkan data yang di push dan di-pop
2. Diketahui
data-data berikut:T,I,D,dan E. Buatlah progam
untuk memesukkan data-data di atas sehingga aka muncul tampilan
berikut:T,E,D,I.Manfaatkan operasi PUSH dan POP.
Hasil
:
1. Program
#include
<iostream>
#include
<conio.h>
#define
maxstack 5
using
namespace std;
struct
STACK
{
int top;
float data[4];
};
float
dta;
struct
STACK stackbaru;
bool
isfull()
{
if(stackbaru.top == maxstack)
return true;
else
return false;
}
bool
isempty()
{
if(stackbaru.top == -1)
return true;
else
return false;
}
void
push(float dta)
{
if(isfull() == true)
puts("Maaf, stack penuh");
else
{
stackbaru.top++;
stackbaru.data[stackbaru.top]=dta;
}
}
void
pop()
{
if(isempty() == true)
{
cout<<"Data telah kosong!";
}
else
{
cout<<"Data yang terambil : "
<<stackbaru.data[stackbaru.top]<<endl;
stackbaru.top--;
}
}
void
print()
{
printf("\nData yang terdapat dalam stack : \n");
printf("--------------------------------\n");
for(int i=0; i<=stackbaru.top; i++)
{
cout<<stackbaru.data[i]<<"
";
}
}
void
clear()
{
stackbaru.top = -1;
printf("\nSekarang stack kosong");
}
int
main()
{
stackbaru.top = -1;
char menu;
char ulang;
do
{
system("cls");
printf("\t PROGRAM STACK\n");
printf("\t===============\n");
printf("Menu : ");
puts("\n1. Pop stack");
puts("2. Push stack");
puts("3. Cetak");
puts("4. Bersihkan stack");
puts("5. Exit");
cout<<"Menu pilihan Anda : ";
cin>>menu;
if(menu == '1')
{
pop();
ulang = 'y';
getch();
}
else if(menu == '2')
{
cout<<"\nTambah Data";
cout<<"\n-----------";
cout<<"\nData yang akan disimpan di stack : ";
cin>>dta;
push(dta);
ulang = 'y';
}
else if(menu == '3')
{
print();
cout<<"\n\nUlang ? (y/t)";
cin>>ulang;
}
else if(menu == '4')
{
clear();
cout<<"\n\nUlang ? (y/t)";
cin>>ulang;
}
else if(menu == '5')
{
exit(0);
}
}while(ulang == 'Y' || ulang == 'y');
}
Hasil
:
2. Program
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include
<iostream>
#include
<conio.h>
using
namespace std;
struct
sStack
{
char isi;
struct sStack*next;
};
int
x,i=1,j=1;
struct
sStack*atas, *bantu, *baru;
void
push(char nilai)
{
if(j==1)
{
atas=(struct sStack*)malloc(sizeof(struct sStack));
atas->isi=nilai;
atas->next=NULL;
}
else
{
baru=(struct sStack*)malloc(sizeof(struct sStack));
baru->isi=nilai;
baru->next=atas;
atas=baru;
}
j++;
}
void
pop()
{
bantu=atas;
printf("[%c] --> ",*bantu);
atas=atas->next;
i++;
free(bantu);
}
int
main()
{
push('I');
push('D');
push('E');
push('T');
j--;
while(atas!=NULL)
pop();
printf("NULL");
_getch();
}
POKOK
BAHASAN 4
Queue
(Antrian)
PENDAHULUAN
Pada pokok
bahasan ini akan dibahas mengenal antrian atau queue, dimana struktur data ini
hamper sama dengan tumpukan atau stack yang merupakan struktur data yang
linier. Perbedaannya adalah pada operasi penambahan dan pengurangan pada ujung
yang berbeda. Setelah mempelajari materi ini diharapkan mahasiswa mampu:
a. Mengetahui dan memahami
definisi antrian.
b. Memahami operasi-operasi
dasar pada antrian.
c. Memahami representasi statis
dan dinamis pada antrian.
PENYAJIAN
(TUTORIAL)
Antrian
adalah suatu kumpulan data yang penambahan elemennya hanya bisa dilakukan pada
suatu ujung (disebut sisi belakang atau REAR), dan penghapusan atau pengambilan
elemen dilakukan lewat ujung yang lain (disebut sisi depan atau FRONT). Prinsip
yang digunakan dalam antrian ini adalah FIFO (First In First Out) yaitu elemen
yang pertama kali masuk akan keluar pertama kalinya. Penggunaan antrian antara
lain simulasi antrian di dunia nyata (antrian pembelian tiket), sistem Jaringan
komputer (pemrosesan banyak paket yang datang dari banyak koneksi pada suatu
host, bridge, gateway), dan lain-lain.
Gambar 4.1
ilustrasi antrian dengan 8
Elemen
Karakteristik penting antrian sebagai berikut:
a. Elemen
antrian yaitu item-item data yang terdapat dalam antrian.
b.
Head/front (elemen terdepan antrian).
c.
Tail/rear (elemen terakhir antrian).
d. Jumlah
antrian pada antrian (count).
e.
Status/kondisi antrian, ada dua yaitu:
- Penuh
Bila
elemen di antrian mencapai kapasitas maksimum antrian. Pada kondisi ini, tidak
mungkin dilakukan penambahan ke antrian. Penambahan di elemen menyebabkan
kondisi kesalahan Overflow.
- Kosong
Bila tidak
ada elemen antrian. Pada kondisi ini, tidak mungkin dilakukan pengambilan
elemen antrian. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.
Operasi-operasi
pokok pada antrian diantaranya adalah :
1. Create Membuat antrian baru.
NOEL(CREATE(Q))
= 0
FRONT(CREATE(Q)) = tidak terdefinisi
REAR(CREATE(Q)) = tidak terdefinisi
2. IsEmpty Untuk
memeriksa apakah Antrian sudah penuh atau belum.
ISEMPTY(Q) = True, jika Q adalah queue kosong.
3. IsFull mengecek apakah
Antrian sudah penuh atau belum.
ISFULL(Q)=True,
jika Q adalah queue penuh.
4. Enqueue/Insert menambahkan
elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling
belakang.
REAR
(INSERT(A,Q)) = A
ISEMPTY
(INSERT(A,Q)) = FALSE
Algoritma
QINSERT:
a. IF FRONT = 1 AND REAR=N, OR
IF FRONT = REAR + 1,
THEN
OVERFLOW, RETURN
b. IF FRONT := NULL, THEN
SET FRONT
:= 1 AND REAR:=1
ELSE IF REAR=N,
THEN SET REAR
:=1
ELSE
SET
REAR :=REAR+1
c. SET QUEUE[REAR] := ITEM
d. RETURN
5. Dequeue/Remove untuk
menghapus elemen terdepan/pertama dari Antrian.
Algoritma
QDELETE:
a. IF FRONT:= NULL, THEN
UNDERFLOW, RETURN
b. SET ITEM := QUEUE[FRONT]
c. [FIND NEW VALUE OF FRONT] IF
FRONT= REAR, THEN
SET
FRONT:= NULL AND REAR;= NULL ELSE IF FRONT = N, THEN
SET
FRONT:=1
ELSE
SET
FRONT: FRONT+1
d. RETURN
Representasi
queue:
Representasi
statis
Queue
dengan representasi statis biasanya diimplementasikan dengan menggunakan array.
Sebuah array memiliki tempat yang dialokasikan diawal sehingga sebuah elemen
yang dimasukkan dalam sebuah array terbatas pada tempat yang ada pada array.
Karena menggunakan array maka queue dengan representasi statis dalam mengalami
kondisi elemen penuh. Ilustrasi queue dengan representasi statis dapat dilihat
pada gambar :
Gambar 4.2
Representasi Queue Statis
Representasi
dinamis
Queue
dengan representasi dinamis biasanya diimplementasikan dengan menggunakan
pointer yang menunjuk pada elemen-elemen yang dialokasikan pada memori.
Ilustrasi queue dengan representasi dinamis dapat dilihat pada gambar :
Gambar 4.3
Representasi Queue Dinamis
LEMBAR
KERJA DAN TUGAS
1. Program
queue statis
#include<queue>
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
queue<int>que;
que.push(10);
que.push(2);
que.push(3);
cout<<"Paling Depan : "<<que.front()<<endl;
cout<<"Paling Belakang : "<<que.back()<<endl;
que.pop();
cout<<"10 Sudah dikeluarkan"<<endl;
cout<<"Paling Depan : "<<que.front()<<endl;
cout<<"Paling Belakang : "<<que.back()<<endl;
que.push(6);
cout<<"6 Sudah dikeluarkan"<<endl;
cout<<"Paling Depan : "<<que.front()<<endl;
cout<<"Paling Belakang : "<<que.back()<<endl;
_getch();
}
Hasil:
2. Program
Queue
#include <iostream>
using namespace std;
#define MAX 5
class queue{
private:
int t[MAX];
int al;
int dl;
public:
queue(){
dl=-1;
al=-1;
}
void del(){
int tmp;
if(dl==-1)
{
cout<<"Queue kosong";
}
else
{
for(int j=0; j<=al; j++)
{
if((j+1)<=al)
{
tmp=t[j+1];
t[j]=tmp;
}
else{
al--;
if(al==-1)
dl=-1;
else
dl=0;
}
}
}
}
void add(int item){
if(dl==-1&&al==-1){
dl++;
al++;
}
else{
al++;
if(al==MAX){
cout<<"Queue penuh\n";
al--;
return;
}
}
t[al]=item;
}
void display(){
if(dl!=-1){
for(int iter=0; iter<=al; iter++)
cout<<t[iter]<<" ";
}
else
cout<<"Kosong";
}
};
int main(){
queue a;
int data[5]={32, 23, 45, 99, 24};
cout<<"Queue sebelum penambahan elemen : ";
a.display();
cout<<endl<<endl;
for(int iter=0; iter<5; iter++){
a.add(data[iter]);
cout<<"Penambahan Angka : "<<(iter+1)<<" :
";
a.display();
cout<<endl;
}
cout<<endl;
cout<<"Queue setelah penambahan elemen : ";
a.display();
cout<<endl<<endl;
for(int iter=0; iter<5; iter++){
a.del();
cout<<"Penghapusan Angka : "<<(iter+1)<<" :
";
a.display();
cout<<endl;
}
system("pause");
return 0;
}
Hasil:
3. Buatlah
program queue untuk memasukkan dan mengeluarkan data berupa huruf dalam
antrian.
#include <stdio.h>
#include <iostream>
#include <conio.h>
using namespace std;
typedef char Titem;
#define MAXN 3
typedef enum {NOT_OK, OK} Tboolean;
typedef struct
{
Titem array[MAXN];
int first;
int last;
int number_of_items;
}Tqueue;
void initialize_queue(Tqueue *Pqueue);
Tboolean enqueue(Tqueue *p, Titem item);
Tboolean dequeue(Tqueue *p, Titem *Pitem);
void print_queue(const Tqueue *Pqueue);
#include <ctype.h>
int main()
{
Tqueue queue;
Tboolean succeed;
char chr;
initialize_queue(&queue);
printf("\n# Masukkan Sebuah Huruf Untuk Masuk Dalam Antrian \n");
printf("\n# Atau Tekan Angka 1 Untuk Mengeluarkan Sebuah Huruf Dalam
Antrian \n");
printf("\n# Atau Tekan x Untuk Keluar : \n");
printf("\n");
chr = getche();;
while(chr !=10 && chr != 13)
{
if (isalpha(chr))
{
succeed=enqueue(&queue, chr);
print_queue(&queue);
if (!succeed)
printf("\n Operasi Pemasukan Data Gagal \n");
}
if(chr == '1')
{
succeed = dequeue(&queue, &chr);
if (succeed)
{
printf("\n");
printf("\n Huruf Yang Keluar Dari Antrian adalah : %c ",chr);
print_queue(&queue);
}
else printf("\nOperasi Pengambilan Data Gagal\n");
}
chr = getche();
}
_getch();
}
void initialize_queue(Tqueue *Pqueue)
{
Pqueue->first=0;
Pqueue->last=-1;
Pqueue->number_of_items=0;
}
Tboolean enqueue(Tqueue *Pqueue, Titem item)
{
if (Pqueue->number_of_items >= MAXN)
return(NOT_OK);
else
{
Pqueue->last++;
if (Pqueue->last > MAXN -1)
Pqueue->last = 0;
Pqueue->array[Pqueue->last] = item;
Pqueue->number_of_items++;
return(OK);
}
}
Tboolean dequeue(Tqueue *Pqueue, Titem *Pitem)
{
if(Pqueue->number_of_items == 0)
return(NOT_OK);
else
{
*Pitem = Pqueue->array[Pqueue->first++];
if (Pqueue->first > MAXN - 1)
Pqueue->first = 0;
Pqueue->number_of_items--;
return(OK);
}
}
void print_queue(const Tqueue *Pqueue)
{
int i, n;
printf("\n");
printf("\n Data Antrian Sekarang : \n\n");
for (n = 1, i = Pqueue->first; n <= Pqueue->number_of_items; n++)
{
printf("%c", Pqueue->array[i]);
i++;
if(i > MAXN - 1)
i = 0;
}
printf("\n\n");
}
Hasil:
4. Program
untuk pengurutan data secara ascending menggunakan QUEUE.
#include<stdio.h>
#include<iostream>
#include<conio.h>
#include<queue>
using namespace std;
int main()
{
queue<int>q;
for(int i=0 ; i<10 ; i++)
q.push(i);
cout<<"isi : ";
do
{
cout<<" "<<q.front();
q.pop();
}while(!q.empty());
cout<<"\n";
_getch;
}
Hasil:
Tugas!
|
1. Buatlah program
queue untuk memasukkan dan mengeluarkan data berupa angka dalam antrian
(Modifikasi program latihan 3).
2. Buatlah
program untuk pengurutan data secara Descending menggunakan QUEUE (Modifikasi
program latihan 4)
|
1. Queue
#include
<iostream>
#include
<conio.h>
#include
<stdlib.h>
#define
MAX 3
using
namespace std;
int
nomer[MAX];
int
head=-1, tail=-1;
bool
IsEmpty(){
if(tail == -1){
return true;
}else{
return false;
}
}
bool
IsFull(){
if(tail == MAX-1){
return true;
}else{
return false;
}
}
void
AntrianMasuk(int no){
if (IsEmpty()){
head=tail=0;
}else {
tail++;
}
nomer[tail]=no;
}
void
AntrianKeluar(){
if(IsEmpty()){
cout<<"Antrian sudah kosong ! ";
getch();
} else {
for(int a=head;a<tail;a++){
nomer[a]=nomer[a+1];
}
tail--;
if(tail == -1){
head = -1;
}
}
}
void
Clear(){
head=tail=-1;
}
void
View(){
if(IsEmpty()){
cout<<"Antrian kosong ! ";
}else {
system("cls");
for(int a=head;a<=tail;a++){
cout << "==============================="
<< "\n >> No. Antri : [" << nomer[a] <<
"]"
<< "\n==============================="<< endl;
}
}
}
int
main(){
int choose, p=1, urut;
do{
system("cls");
cout << "\n\n===== PROGRAM ANTRIAN C++ ====="
<< "\n==============================="
<< "\n|1. Tambah
Antrian
|"
<< "\n|2. Panggil
Antrian |"
<< "\n|3. Lihat daftar antrian |"
<< "\n|4.
Format
|"
<< "\n|5.
Exit
|"
<< "\n===============================";
cout << "\nChoose ! "; cin >> choose;
cout << "\n\n";
if(choose == 1){
if(IsFull()) {
cout<<"Antrian sudah penuh, mohon tunggu beberapa saat lagi ";
}
else{
urut=p;
AntrianMasuk(urut);
cout << "---------------------------------" << endl;
cout << "| NO.
ANTRIAN |" <<
endl;
cout <<
"|
" << p << "
||" << endl;
cout << "---------------------------------" << endl;
cout << "| Silahkan
Mengantri |" << endl;
cout << "| Menunggu " <<
tail << " Antrian ||" <<
endl;
cout << "---------------------------------" << endl;
p++;
}
}
else if(choose == 2){
cout << "=================================" << endl;
cout << "No. Antri : [" << nomer[head] <<
"]";
cout << "\n=================================" << endl;
AntrianKeluar();
cout << "Silahkan Dipanggil !" << endl;
}
else if(choose == 3){
View();
}
else if(choose == 4){
Clear();
cout<<"Antrian dikosongkan ! ";
}
else if(choose == 5){
}
else{
cout << "Masukan anda salah ! \n"<< endl;
}
getch();
}while(choose!=5);
}
Hasil:
2. Queue
Descending.
#include
<stdio.h>
#include
<iostream>
#include
<conio.h>
#include
<queue>
using
namespace std;
int
main()
{
queue <int> q;
for(int i=9;i>=0;i--)
q.push(i);
cout<<"Isi : ";
do
{
cout<<' '<<q.front();
q.pop();
}
while(!q.empty());
cout<<'\n';
_getch();
}
POKOK BAHASAN
5
Rekursif
PENDAHULUAN
Pada pokok
bahasan ini akan dibahas mengenai rekursif. Setelah mempelajari bab ini
diharapkan mahasiswa mampu :
a. Mengetahui dan memahami
definisi rekursif.
b. Memahami sifat-sifat
rekursif.
c. Mengaplikasikan rekursif.
PENYAJIAN
(TUTORIAL)
Fungsi
rekursif adalah suatu fungsi yang memanggil dirinya sendiri, artinya fungsi
tersebut dipanggil di dalam tubuh fungsi itu sendiri. Contoh menghitung nilai
factorial. Rekursif sangat memudahkan untuk memecahkan permasalahan yang
kompleks. Sifat-sifat rekursif:
Dapat
digunakan ketika inti dari masalah terjadi berulang kali.
Sedikit
lebih efisien dari iterasi tapi lebih elegan.
Method-methodnya
dimungkinkan untuk memanggil dirinya sendiri.
Data yang
berada dalam method tersebut seperti argument disimpan sementara ke
dalam stack sampai method pemanggilnya diselesaikan.
LEMBAR KERJA DAN TUGAS
1. Program
bilangan genap dan bilangan ganjil
#include<iostream>
#include<conio.h>
using namespace std;
void odd(int a);
void even(int a);
int main(void)
{
int i;
do
{
cout<<"Masukkan Bilangan 1-9 (0 untuk keluar) : \n";
cin>>i;
odd(i);
cout<<endl;
}while
(i=!0);
_getch();
}
void odd(int a)
{
if((a%2)==!0)
cout<<"Bilangan GANJIL \n";
else
even(a);
}
void even(int a)
{
if((a%2)==0)
cout<<"Bilangan GENAP \n";
else
odd(a);
}
Hasil:
2. Program
Fibonacci.
#include<stdio.h>
#include<iostream>
#include<conio.h>
using namespace std;
long fibonacci (long n)
{
if(n==1 || n== 2)
return(1);
else
return fibonacci(n-1)+fibonacci(n-2);
}
int main()
{
int x;
printf("mencari Nilai fibonacci \n");
printf("Masukkan nilai X : ");
scanf("%d", &x);
printf("Nilai Fibonacci dari %d = %d \n", x, fibonacci(x));
system("pause");
_getch();
}
Hasil:
3. Program
factorial.
#include<stdio.h>
#include<iostream>
#include<conio.h>
using namespace std;
int faktorial (int n)
{
if(n==1)
return(1);
else
return(n*faktorial(n-1));
}
int main()
{
int x;
printf("mencari Nilai Faktorial \n");
printf("Masukkan nilai X : ");
scanf("%d", &x);
printf("Nilai Faktorial dari %d = %d \n", x, faktorial(x));
system("pause");
_getch();
}
Hasil:
4. Program
penjumlahan kuadrat sejumlah bilangan menggunakan iterasi.
JumKuadrat (m,n) = m2 + (m+1)2 +
……+n2 dengan m<=n.
JumKuadrat (5,9) = 52 + 62 +
72 + 82 + 92 = 225
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<conio.h>
using namespace std;
int jumkuadrat(int m, int n)
{
int i, jum=0;
for(i=m ; i<=n ; i++)
{
jum+=i*i;
printf("\n %d Kuadrat = %d dan jumlah Kuadrat : %d \n");
}
return jum;
}
int main(void)
{
char cNilaim[3],cNilain[3],cJawab[2];
int iNilaim,iNilain,iNilaijumkuadrat;
while(1)
{
printf("Masukkan nilai m dan n. NILAI HARUS M < N. \n");
cout<<endl;
printf("Nilai m : ");
gets(cNilaim);
printf("Nilai n : ");
gets(cNilain);
cout<<endl;
iNilaim=atoi(cNilaim);
iNilain=atoi(cNilain);
iNilaijumkuadrat=jumkuadrat(iNilaim,iNilain);
cout<<"============================================";
printf("\nJumlah Kuadrat (dari %d dan %d) =
%d,",iNilaim,iNilain,iNilaijumkuadrat);
cout<<endl;
printf("\nCoba Lagi? [Y/T] : ");
gets(cJawab);
if(strcmp(cJawab,"t")==0||strcmp(cJawab,"T")==0)
break;
}
}
Hasil:
Tugas
|
1. Buatlah program untuk
menentukan bilangan yang terbesar dan terkecil dari dua buah bilangan yang
diinputkan.
2. Buatlah program dengan
cara rekursi untuk menampilkan perkalian 3 buah bilangan, dimana ketiga
bilangan tersebut nilainya diinputkan.
3. Buatlah program untuk
mengurutkan bilangan secara Descending dengan menggunakan Rekursif.
4. Buatlah program
perhitungan gaji karyawan. Dengan ketentuan :
a. Jika
gaji kotor 1.500.000 maka mendapat potongan 10%.
b. Jika
gaji kotor >1.500.000 maka mendapat potongan 15%.
|
1. Program menentukan bilangan.
#
include<stdio.h>
#
include<conio.h>
int
main ()
{
int data [50];
int a,b;
int max,min;
printf("Banyak Bilangan: ");scanf ("%d",&a);
for (b=1;b<=a;b++)
{
printf("\nbilangan ke-%d:
",b);scanf("%d",&data [b]);
}
max=data[1];
min=data[1];
for (b=1;b<=a;b++)
{
if (data[b]>=max)
{
max=data[b];
}
else if (data[b]<=min)
{
min=data[b];
}
}
printf("\n\nBilangan yang lebih besar adalah\t:%d", max);
printf("\n\nBilangan yang lebih kecil adalah\t:%d", min);
getch();
}
Hasil:
2. Perkalian 3 bilangan.
#include<iostream>
#include<conio.h>
using
namespace std;
int
tambah(int e, int o, int f)
{
if( f == 0 )
{
return 0;
}
if( f == 1 )
{
return (e*o);
}
else
return ( (e*o) + tambah( e, o, (f-1)));
}
int
main()
{
int x, y, z;
ulang:
cout<<"Masukkan bilangan pertama : ";
cin>>x;
cout<<"Masukkan bilangan kedua : ";
cin>>y;
cout<<"Masukkan bilangan ketiga : ";
cin>>z;
cout<<"\nHasil Perkalian 3 angka tersebut: ";
cout<<tambah(x,y,z);
cout<<endl;
getch();
}
Hasil:
3. Descending rekursif.
#include<iostream>
#include<conio.h>
#define
max 20
using
namespace std ;
void
quick_sort(int darr[max], int zero, int ten)
{
int a;
int up,down;
int temp;
if (zero>=ten)
return;
a=darr[zero];
up=ten;
down=zero;
while (down < up)
{
while (darr[down] <= a)
down++;
while (darr[up]>a)
up--;
if(down<up)
{
temp=darr[down];
darr[down]=darr[up];
darr[up]=temp;
}
}
darr[zero]=darr[up];
darr[up]=a;
quick_sort(darr,zero,up-1);
quick_sort(darr,up+1,ten);
}
int
main()
{
int i,n = 10 ,zero,ten;
int arr []= {1,3,2,6,5,4,8,9,10,7};
zero=0;
ten=n;
quick_sort(arr,zero,ten);
for(i=n-1; i>=0;i--)
cout<<"Proses Rekursif dengan Nilai Counter :
"<<arr[i]<<endl;
getch();
}
Hasil:
4. Perhitungan Gaji Karyawan.
#include<iostream>
#include<conio.h>
using
namespace std;
int
main()
{
int gaji1,pot,gaji2;
cout<<"Program Menghitung Gaji"<<endl;
cout<<"\n";
cout<<"Masukkan Gaji Kotor = ";
cin>>gaji1;
if(gaji1<=1500000)
{
pot=(gaji1*10)/100;
gaji2=gaji1-pot;
}
else if(gaji1>1500000)
{
pot=(gaji1*15)/100;
gaji2=gaji1-pot;
}
cout<<"Total Gaji Sebelum Potongan =
"<<gaji1<<endl;
cout<<"Total
Potongan
= "<<pot<<endl;
cout<<"Gaji
Bersih
= "<<gaji2<<endl;
system("PAUSE");
}
POKOK
BAHASAN 6
Sorting
(Pengurutan)
PENDAHULUAN
Setelah mempelajari bab ini diharapkan mahasiswa mampu :
a. Menunjukkan
beberapa algoritma dalam pengurutan.
b. Menunjukkan
bahwa pengurutan merupakan suatu persoalan yang bisa diselesaikan dengan
sejumlah algoritma yang berbeda satu sama lain.
c. Dapat
memilih algoritma yang paling sesuai untuk menyelesaikan suatu permasalahan
pemograman.
PENYAJIAN
(TUTORIAL)
Pengurutan data (sorting) didefinisikan sebagai
suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu.
Ada dua macam urutan yang biasa digunakan dalam proses pengurutan yaitu :
· Urutan
naik (ascending) yaitu dari data yang mempunyai nilai paling kecil
sampai paling besar.
· Urutan
turun (descending) yaitu dari kata yang mempunyai nilai paling besar
sampai paling kecil.
Contoh : data bilangan 5, 2, 6, dan 4 dapat diurutkan
naik menjadi 2, 4, 5, 6 atau diurutkan turun menjadi 6, 5, 4, 2. Pada data yang
bertipe char, nilai data dikatakan lebih besar dari yang lain didasarkan pada
urutan relatif (collating sequence) seperti dinyatakan dalam tabel
ASCII. Keuntungan dari data yang sudah dalam keadaan terurut yaitu :
Data mudah dicari, mudah untuk
dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadaan terurutkan, kita
mudah melakukan pengecekan apakah ada data yang hilBang. Misalnya kamus bahasa,
buku telepon. Mempercepat proses pencarian data yang harus dilakukan berulang
kali.
Beberapa faktor yang berpengaruh pada efektifitas suatu
algoritma pengurutan antara lain :
Banyak data yang diurutkan. Kapasitas
peningkat apakah mampu menyimpan semua data yang kita miliki. Dan tempat
penyimpanan data, misalnya piringan, pita atau kartu, dll.
Beberapa algoritma metode pengurutan dan prosedurnya
sebagai berikut :
1. Bubble
Sort
Bubble Sort adalah suatu metode pengurutan yang
membandingkan elemen yang sekarang dengan elemen berikutnya. Apabila elemen
sekarang > elemen berikutnya, maka posisinya ditukar. Kalau tidak, tidak
perlu ditukar. Diberi nama “Bubble” karena proses pengurutan secara
berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung
yang keluar dari sebuah gelas bersoda.
Proses Bubble Sort :
Data paling akhir dibandingkan dengan data di depannya,
jika ternyata lebih kecil atau besar maka tukar sesuai dengan ketentuan
(descending atau ascending). Dan pengecekan yang sama dilakukan terhadap data
yang selanjutnya sampai dengan data yang paling awal
Gambar 6.1 Langkah 1 Bubble Sort
Gambar 6.2 Langkah 2 Bubble sort
Gambar 6.3 Langkah 3 Bubble Sort
Algoritma Bubble Sort :
I = 0
Selama (i < N – 1) Kerjakan baris 3
sampai 7
J = N – 1
Selama (j >= i) Kerjakan baris 5
sampai 7
Jika (Data[j-i] > Data[j]) maka
tukar Data [j-1] dengan Data [j]
J = j – 1
I = i + 1
Prosedur yang menggunakan metode gelembung :
Void BubbleSort()
{
Int i, j;
For(i=1:i<Max-1;i++)
For(j=Max-1; j>=i;j--)
If(Data[j-1] > Data[j])
}
2. Selection
Sort
Metode seleksi melakukan pengurutan dengan cara mencari
data yang terkecil kemudain menukarkannya dengan data yang digunakan sebagai
acuan atau sering dinamakan pivot. Selama proses, pembandingan dan pengubahan
hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik
terjadi pada akhir proses. Proses pengurutan dengan metode seleksi dapat
dijelaskan sebagai berikut :
Langkah pertama dicari data terkecil dari data pertama sampai data terakhir.
Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data
pertama sekarang mempunyai nilai paling kecil dibanding data yang lain.
Langkah kedua dicari data terkecil dari data kedua sampai terakhir. Data
terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya
sampai semua elemen dalam keadaan terurutkan.
Gambar 6.4 Langkah Selection Sort
Algoritma seleksi dapat dituliskan sebagai berikut :
I = 0
Selama (i < N – 1) Kerjakan baris 3
sampai dengan 9
K = i
J = i + 1
Selama (j < N) Kerjakan baris 6 dan
7
Jika (Data[k] > Data[j]) maka k = j
J = j + 1
Tukar Data[i] dengan Data [k]
I = i + 1
Di bawah ini merupakan prosedur yang
menggunakan metode seleksi :
Void
SelectionSort()
{
Int i, j, k;
For(i=0; i<Max-1++)
{
K = i;
For (j=i+1; j<Max; j++)
If(Data[K] > Data [j]);
}
}
3. Merger
Sort
Algoritma Merge Sort ialah algoritma pengurutan yang
berdasarkan pada strategi divide and conquer. Algoritma
ini terdiri dari dua bagian utama, pembagian list yang diberikan untuk di-sort ke
dalam beberapa sublist yang lebih kecil, dan sort(mengurutkan)
dan merge (menggabungkan) sublist-sublist yange
lebih kecil ke dalam list hasil yang diurutkan. Pembagian bisa dikatakan cukup
mudah karena sublist-sublist tersebut dibagi kedalam dua sublist yang ukurannya
adalah setengah dari ukuran semula. Hal ini terus diulang sampai sublist itu
cukup kecil untuk di-sort secara efisien (umumnya telah terdiri
dari satu atau dua elemen). Dalam langkah merge dua sublist disatukan
kembali dan diurutkan pada saat yang sama. Algoritma untuk merge sort ialah
sebagai berikut :
A. Untuk
kasus n=1, maka table a sudah terurut sendirinya (langkah solve)
B. Untuk
kasus n>1, maka :
a. DIVIDE
: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-masing
bagian berukuran n/2 elemen.
b. CONCUER
: secara rekursif, terapkan algoritma D-and-C pada masing-masing bagian.
c. MERGE
: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.
LEMBAR KERJA DAN TUGAS
1. Program
ascending menggunakan bubble sort.
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std ;
int main ()
{
int dataku[] = {5, 34, 32, 25, 75, 42, 2};
int adaPertukaran;
int n;
cout << "Data BELUM diurutkan : \n";
for (int ctr = 0; ctr<7; ctr++)
{
cout << setw( 3 ) << dataku[ctr];
}
cout << endl << endl;
//PENGURUTAN
do
{
adaPertukaran = 0;
for (int i = 0; i < 7-1; i++)
{
if (dataku[i+1] < dataku[i])
{
n = dataku[i];
dataku[i] = dataku[i+1];
dataku[i+1] = n;
adaPertukaran = 1;
}
}
} while (adaPertukaran == 1);
//MENAMPILKAN HASIL PENGURUTAN
cout << "Data SETELAH diurutkan : \n";
for (int i = 0; i < 7; i++){
cout << dataku[i];
cout << " ";
}
_getch();
}
Hasil:
2. Program
aplikasi array untuk mengurutkan bilangan dengan metode bubble sort.
#include <stdio.h>
#include <iostream>
#include <conio.h>
#define MAX 20
void input(int jum);
void buble(int jum);
void output(int jum);
int n, A[MAX];
using namespace std ;
int main()
{
printf("Masukkan Jumlah Bilangan : ");
scanf("%d" ,&n);
cout<<endl;
input(n);
buble(n);
output(n);
_getch();
}
void input (int jum)
{
int i;
for(i=0;i<jum;i++)
{
printf("Bilangan ke %d : ",i+1);
scanf("%d", &A[i]);
cout<<endl;
}
cout<<endl;
cout<<"Hasil Pengurutan Secara Ascending : \n";
cout<<endl;
}
void buble(int jum)
{
int i,j,temp;
for(i=1;i<=jum-1;i++)
{
for (j=i;j<n;j++)
{
if (A[i-1]>A[j])
{
temp=A[i-1];
A[i-1]=A[j];
A[j]=temp;
}
}
}
}
void output (int jum)
{
int i;
for(i=0;i<jum;i++)
{
printf("Bilangan ke %d = %d\n",i+1,A[i]);
cout<<endl;
}
}
Hasil:
3. Program
ascending dengan menggunakan selection sort.
#include <iostream>
#include <conio.h>
using namespace std ;
int data[10],data2[10];
int n;
void Select(int a, int b)
{
int t;
t = data[b];
data[b] = data[a];
data[a] = t;
}
void selection_sort()
{
int pos,i,j;
for(i=1;i<=n-1;i++)
{
pos = i;
for(j = i+1;j<=n;j++)
{
if(data[j] < data[pos]) pos = j;
}
if(pos != i) Select(pos,i);
}
}
int main()
{
cout<<"===PROGRAM SELECTION SORT==="<<endl;
cout<<endl;
//Input Data
cout<<"Masukkan Jumlah Data : ";
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<"Masukkan Data Ke - "<<i<<" : ";
cin>>data[i];
data2[i]=data[i];
}
selection_sort();
cout<<"\n\n";
//Menampilkan Data
cout<<"Data Setelah di Sort : ";
for( int i=1; i<=n; i++)
{
cout<<" "<<data[i];
}
cout<<"\n\n Proses Selesai \n";
_getch();
}
Hasil:
4. Program
ascending menggunakan merger sort.
#include <stdio.h>
#define MAX 5
int Data[MAX];
int temp[MAX];
// Procedure Merger Sort
void merge(int Data[], int temp[], int kiri, int tengah,
int kanan)
{
int i, left_end, num_elements, tmp_pos;
left_end = tengah - 1;
tmp_pos = kiri;
num_elements = kanan - kiri + 1;
while ((kiri <= left_end) && (tengah <= kanan))
{
if (Data[kiri] <= Data[tengah])
{
temp[tmp_pos] = Data[kiri];
tmp_pos = tmp_pos + 1;
kiri = kiri +1;
}
else
{
temp[tmp_pos] = Data[tengah];
tmp_pos = tmp_pos + 1;
tengah = tengah + 1;
}
}
while (kiri <= left_end)
{
temp[tmp_pos] = Data[kiri];
kiri = kiri + 1;
tmp_pos = tmp_pos + 1;
}
while (tengah <= kanan)
{
temp[tmp_pos] = Data[tengah];
tengah = tengah + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
Data[kanan] = temp[kanan];
kanan = kanan - 1;
}
}
// Prosedur Kumpulan Data
void m_sort(int Data[], int temp[], int kiri, int kanan)
{
int tengah;
if (kanan > kiri)
{
tengah = (kanan + kiri) / 2;
m_sort(Data, temp, kiri, tengah);
m_sort(Data, temp, tengah+1, kanan);
merge(Data, temp, kiri, tengah+1, kanan);
}
}
void mergeSort(int Data[], int temp[], int array_size)
{
m_sort(Data, temp, 0, array_size - 1);
}
int main()
{
int i;
printf("Masukkan DATA SEBELUM TERURUT : \n");
for (i = 0; i < MAX; i++)
{
printf ("Data ke %i : ", i+1);
scanf ("%d", &Data[i]);
}
mergeSort(Data, temp, MAX);
printf("\n DATA SETELAH TERURUT : ");
for (i = 0; i < MAX; i++)
printf("%d ", Data[i]);
printf("\n");
scanf("%d");
return(0);
}
umsida.ac.id
fst.umsida.ac.id
