POKOK BAHASAN 1
STRUKTUR DATA, ARRAY, POINTER, DAN STRUKTUR
A. Konsep Dasar Struktur Data
Struktuk data adalah sebuah bagian dari ilmu pemrograman dasar yang mempuyai karakteristik yang terkait dengan sifat dan cara penyimpanan sekaligus pengguna atau pengakses data. Struktuk data bertujuan agar cara mereprentsikan data dalam membuat program dapat dilakuian secara efesien dalam pengolahan di memori dan pengolahan penyimpanan dari program ke storage juga lebih mudah dilakukan.
B. Konsep Dasar Array
Array adalah kumpulan elemen-elemen data. Kumpulan elemen tersebut mempunyai susunan yang teratur. Jmlah elemen terbatas, dan semua elemen mempunyai tipe data yang sama. Jenis-jenis array :
1. Array Satu Dimensi
2. Array Dua Dimensi
3. Array multidimensi/Dimensi Banyak
C. Konsep Dasar Pointer
Pointer adalah sebuah variable yang berisi alamat variable yang lain. Satu pointer dimksudkan untuk menunjuk kesuatu alamat memori sehingga alamat dari suatu variable dapat diketahui dengan mudah. Deklarasi ponter :
Oprator pointer :
- Oprator ‘&’ ; untuk mendapatkan alamat memori operand/variable ponter.
- Oprator ‘*’ : untuk mengakses nilai data operand/variable pointer.
D. Konsep Dasar Struktur
Struktur adalah koleksi dari variable yang dinyatakan sebuah nama, dengan sifat setiap variable dapat memiliki tipe yang berlainan. Struktur bisa dipakai untuk mengelompokkan beberapa informasi yang berkaitan menjadi sebuah 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 variable_struktur M menyatakan bahwa variable struktur yang dideklarasikan bisa lebih dari satu. Jika ada lebih dari satu variable, antara variable struktur dipisahkan dengan tanda koma.
Mengakses Elemen Struktur:
Elemen dalam struktur dapat diakses dengan mengguanakan bentuk:
Variable_struktur.nama_field
Antara variable_struktur dab nama_field dipisahkan dengan oprator titik (disebut oprator anggota struktur). Contoh berikut merupakan intruksi untuk mengisikan data pada file tanggal:
Tgl_lahir.tanggal=30 int bulan;
Int tahun;
};
Yang mendefinisikan tipe bernama data_tanggal, yang terdiri dari tiga buah elemen berupa tanggal, bulan, dan tahun. Bentuk umum dalam mendefenisikan struktur adalah :
Struct nama_tipe_struktur
{
Tipefiled1; tipefiled2; tipefiled3;
}variable_struktur….variabel_struktur;
#include <stdio.h>
#include <iostream>
#include <conio.h>
using namespace std;
int main(){
int square[100];
int i;
int k;
for (i=0; i<10; i++){
k = i+1;
square[i] = k*k;
printf("\n pangkat dari %d adalah %d ", k, square[i]);
}
getch();
}
Hasil Output:
POKOK BAHASAN 2
LINKED LIST (SENARAI)
PENYAJIAN (TUTORIAL)
Linked List adalah sejumlah objek atau elemen yang dihubungkan satu dengan lainya sehingga membentuk suatu list. Sedangkan objek atau elemen itu sendiri adalah merupakan gabungan beberapa data(variable) yang dijadikan satu kelompok atau structure atau record yang dibentuk dengan perintah struct. Untuk menggabungkan objek satu dengan lainya, diperlukan paling tidak sebuah variable yang bertipe pointer. Syarat linked list adalah harus dapat diketahui alamat simpul pertama atau biasa dipakai variable First/Start/Header.
Istilah-istilah dalam linked list :
A. Simpul
B. First/Header
C. Nill/Null
D. Simpul Terakhir(Last)
Jenis-jenis linked list :
1. List kosong
2. List tunggal
3. List ganda
Operasi Dasar pada Lingked List :
IsEmpty : Fungsi ini menentukan apakah linked list kosong atau tidak.
Size : operasi untuk mengirim jumlah elemen di linked list.
Create : operasi untuk penciptaan list baru yang kosong.
Insertfirst : operasi untuk penyisipan simpul sebagai simpul pertama.
Insertafter : operasi untuk penyisipan simpul setelah simpul tertentu.
Installaast : operasi untuk penyisipan simpul setelah simpul terakhir.
Insertbefore : operasi untuk penyisipan simpul sebelum simpul tertentu.
Deletefirst : operasi penghapusan simpul pertama.
Deleteafter : operasi untuk penghapusan setelah simpul tertentu.
Deletelast : operasi penghapusan simpul terakhir.
Contoh program sisip senarai (Linked List)
#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 SisiSeranai(NODPTR *s, NODPTR t, NODPTR p)
{
if(p==NULL)
{
t->next=*s;
*s=t;
}
else
{
t->next=p->next;
p->next=t;
}
}
void CetakSeranai(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);
SisiSeranai(&pel, n, NULL);
n=NodBaru(75);
SisiSeranai(&pel, n, NULL);
CetakSeranai(pel);
getch();
}
Hasil Output :
POKOK BAHASAN 3
STACK (TUMPUKAN)
PENYAJIAN (TUTORIAL)
Stack adalah kumpulan elemen-elemen yang tersimpan dalam suatu tumpukan. Aturan penyisipan dan penghapusan elemennya tertentu:
- Penyisipan 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 tersusun secara LIFO (Last In First Out). Beberapa contoh penggunaan stack adalah pemanggilan prosedur, perhitungan ekspresi aritmatika, rekursifitas, backtracking, penanganan 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 menyebabkan kondisi kesalahan Overflow.
- Kosong
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 menambahka item pada tumpukan paling atas.
void Push (ItemType x, Stack *S)
{
If(Full (S))
Printf(“Stack FULL”);
Else
{
--(S->Count);
x=s->Item(s->Count);
}
}
Clear :Untuk mengosongkan stack
Void intializeStack (Stack S)
{
S->Count=0;
}
IsEmpty : Untuk memeriksa 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==MAXSTACK);
}
Representasi stack:
- Representasi statis
Stack 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 stack dengan representasi statis dalam mengalami kondisi elemen penuh .
- Representasi dinamis
Stack dengan representasi dinamis biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen-elemen yang dialokasikan pada memori.
Karena semua operasi pada sebuah stack diawali dengan elemen yang paling atas maka jika menggunakan representasi dinamis saat elemen ditambahkan akan menggunakan penambahan elemen pada awal stack (addfirst) dan saat pengambilan atau penghapusan elemen menggunakan penghapusan di awal stack (deffirst).
Program Stack
#include <stdio.h>
#include <conio.h>
#include <iostream>
#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);
}
void isi(itemType x, Stack *s)
{
if(penuh(s))
printf("\nMAAF!!! Data PENUH\n");
else{
s->item[s->jml]=x;
++(s->jml);
}
}
void 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("\Data %i Berhasil Diambil\n",*x);
}
}
void tampil(Stack *s)
{
if(kosong(s))
printf("\Maaf Data Masih Kosong\n");
else
printf("\n");
for(int i=s->jml-1;i>=0;i--)
{
printf("Data: %d\n",s->item[i]);
}
}
void 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 Output:
POKOK BAHASAN 4
QUEUE (ANTRIAN)
PENYAJIAN (TUTORIAL)
Antrian adalah salah satu 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.
Karakteristik penting antrian sebagai berikut:
Elemen antrian yaitu item-item data terdapat dalam antrian.
A. Heat/font (elemen terdepan dalam antrian).
B. Tail/rear (elemen terakhir antrian).
C. Jumlah antrian pada antrian (count).
D. Status/kondisi antrian, ada dua yaitu:
- Penuh
Bila elemen pada antrian mencapai kapasitas maksimum antrian. Pada kondisi ini, tidak mungkin dilakuakan penambahan ke antrian. Penambahan di elemen menyebabkan kondisi kesalahan overflow.
- Kosong
Bila tidak ada elemen antrian. Pada kondisi ini, tidak mungkin dilakuakan 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. IsEmpety → Untuk memeriksa apakah Antrian sudah penuh atau belum.
ISEMPETY(Q) = True, jika Q adalah queue kosong.
3. IsFull→mengecek apakah Antrian sudah penuh atau belum.
ISFULL(Q) = True, jika Qadalah queue penuh.
4. Enqueue/Insert → menambahkan elemen ke dalam Antrian, penambahan elemen selaluditambahkan di elemen paling belakang.
REAR(INSERT(A,Q)) =A
ISEMPETY (INSERT(A,Q)) FALSE
Algoritma QINSERT :
A. IF FRONT = 1 AND REAR = N, OR IF FRONT = REAR + 1, THEN OVERFLOW, RETUN
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 = 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 biasasnya diimplementasikan dengan menngunakan array. Sebuah array memiliki tempat yang di alokasikan diawal sehingga sebuah elemen yang dimasukkan dalam sebuah array terbatas pada tempat yang ada pada array. Karena menggunakan array maka queue representasi statis dalam mengalami kondisi elemen penuh. Ilustrasi queue dengan representasi statis dapat dilihat pada gambar:
- Representasi dinamis
Queue dengan representasi dinamis biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen –elemen yang dialokasikan pada memori. Ilustrasi queue representasi dinamis dapat dilihat pada gambar :
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<<"\n10 sudah dikeluarkan"<<endl;
cout<<"Paling depan : "<<que.front()<<endl;
cout<<"Paling belakang : "<<que.back()<<endl;
que.push(6);
cout<<"\nAngka 6 dimasukkan"<<endl;
cout<<"Paling depan : "<<que.front()<<endl;
cout<<"Paling belakang : "<<que.back()<<endl;
getch();
}
Hasil Output :
POKOK BAHASAN 5
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 faktorial. 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.
Program bilangan genap dan bilangan ganjil.
#include <iostream>
#include <conio.h>
using namespace std;
void odd (int a);
void even(int a);
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 Output :
POKOK BAHASAN 6
SORTING (PENGURUTAN)
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 data yang mempunyai nilai paling besar sampai paling kecil.
Keuntungan dari data yang sudah dalam keadaan terurut yaitu :
A. Data mudah dicari, mudah untuk dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadaan terurutkan, kita mudah melakukan pengecekan apakah ada data yang hilang.
B. Misalnya kamus bahasa, buku telepon.
C. Mempercepat proses pencarian data yang harus dilakukan berulang kali.
Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain :
A. Banyak data yang diurutkan.
B. Kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki.
C. 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.
Algoritma bubble sort:
1. i=0
2. selama (i<N-1)kerjakan baris 3 sampai 7
3. j=N-1
4. selama (j>=i)kerjakan baris 5 sampai 7
5. jika (data [j-1]>data[j]maka tukar data[j-1]dengan data[j]
6. j=j-1
7. 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])
Tukar(&data[j-1],&data[j]);
}
2. Selection Sort
Metode seleksi melakukan pengurutan dengan cara mencari dta yang terkecil kemudian menukarnya 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:
A. 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.
B. Langkah kedua,data terkecil kita cari mulai data kedua sampai terakhir.data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan.
Algoritma seleksi dapat dituliskan sebagai berikut:
1. i=0
2. selama(i<N-1)kerjakan baris 3 sampai dengan 9
3. k=i
4. j=i+1
5. selama (j<N)kerjakan baris 6 dan 7
6. jika (data[k]>data[j]maka k=j
7. j=j+1
8. tukar data [i] dengan data[k]
9. i=i+1
Dibawah ini merupakan prosedur yang menggunakan metode seleksi:
Void selectionsort()
{
Int i,j,k;
For(i=0; i<Max-1;i++)
{
K=i;
For(j=i+1;j<max;j++)
If(data[k]>data[j])
K=j;
Tukar(&data[i],&data[k]);
} }
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 yang lebih kecil ke dalam list hasil yang sudah diurutkan. Pembagian bisa dikatakan cukup mudah karena sublist-sublist tersebut dibagi ke dalam 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 sendiirinya (langkah solve)
B. untuk kasus n>1,maka:
- DEVIDE: bagi table a menjadi dua bagian,bagian kiri dan bagian kanan, masing-masing bagian berukuran n/2 elemen.
- CONQUER:secara rekursif,terapkan algoritma D-dan-C pada masing-masing bagian.
- MERGE:gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.
Program ascending dengan menggunakan bubble sort
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;
void main(void)
{
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 Output :
