Struct

Sekilas Tentang Struct

* Struct adalah tipe data bentukan yang berisi kumpulan variabel-variabel
yang bernaung dalam satu nama yang sama dan memiliki kaitan satu
sama lain.
* Berbeda dengan array hanya berupa kumpulan variabel yang bertipe data
sama, struct bisa memiliki variabel-variabel yang bertipe data sama atau
berbeda, bahkan bisa menyimpan variabel yang bertipe data array atau
struct itu sendiri.
* Variabel-variabel yang menjadi anggota struct disebut dengan elemen
struct.

Bentuk umum dari struct:

typedef struct{
tipe_data ;
tipe_data ;
.... }

Struct bisa diumpamakan sebagai sebuah obyek, misalnya: obyek Mahasiswa. Struct Mahasiswa memiliki property atau atribut atau variabel yang melekat padanya:

* NIM misal karakter sejumlah 8
* Nama yaitu karakter
* IPK yaitu bilangan pecahan

Struct tidak memiliki operasi (method) atau function. Struct dapat digunakan dengan cara membuat variabel yang bertipe struct tersebut.
Misalnya :

* variabel anton bertipe struct Mahasiswa
* variabel erick bertipe struct Mahasiswa

Dengan demikian variabel anton dan erick memiliki NIM, Nama, dan IPK masing-masing.

Ada dua cara untuk mendeklarasikan struct pada C yaitu:

Menggunakan keyword typedef:

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

//untuk menggunakan struct Mahasiswa dengan membuat variabel mhs dan mhs2
Mahasiswa mhs,mhs2;
//untuk menggunakan struct Mahasiswa dengan membuat variabel array m;
Mahasiswa m[100];

Menggunakan keyword struct:

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

Berarti kita sudah mempunyai variabel mhs yang bertipe data struct seperti diatas

Cara penggunaan struct dan pengaksesan elemen-elemennya:

* Penggunaan/pemakaian tipe data struct dilakukan dengan membuat suatu variabel yang bertipe data struct tersebut
* Pengaksesan elemen struct dilakukan secara individual dengan menyebutkan nama variabel struct diikuti dengan operator titik (.)
* Misalnya dengan struct mahasiswa seperti contoh di atas, kita akan akses elemen-elemennya seperti contoh berikut:

Contoh Program 1 (Penggunaan Struct Sederhana) :

#include
#include

//Pendeklarasian tipe data baru struct Mahasiswa
typedef struct Mahasiswa{
char NIM[9];
char nama[30];
float ipk;
};

void main(){
//Buat variabel mhs bertipe data Mahasiswa
Mahasiswa mhs;
clrscr();

printf("NIM = ");scanf("%s",mhs.NIM);
printf("Nama = ");scanf("%s",mhs.nama);
printf("IPK = ");scanf("%f",&mhs.ipk);

printf("Data Anda : \n");
printf("NIM : %s\n",mhs.NIM);
printf("Nama : %s\n",mhs.nama);
printf("IPK : %f\n",mhs.ipk);
getch();
}

Class

Dalam C++ Struct dan class mempunyai penulisan yang sama. Deklarasi class daan
struct memiliki anggota dengan akses public kecuali jika dinyatakan lain.
C ++ tidak membedakan nama class dan nama tag, paling tidak dari sudut pandang
pemprogram dan tetap menerima deklarasi structure. Kompatibilitas C ++ tidak sebatas
pada perbedaan nama class daan nama type karena C++ masih memerlukan definisi type
POD (Plain Old Data). C++ mendefinisikan POD Type sebagai objek suatu class yang
tidak mempunyai userdefined constructor, anggota protected maupun private, tidak
memiliki base class dan tidak memiliki fungsi virtual.
Compiller C++ dapat menambahkan default constructor apabila diperlukan, jika dalam
definisi class:
· Tidak tertulis secara eksplisit default constructor dan tidak ada dejlarasi
constructor lain.
· Tidak ada anggota class berupa data const maupun referens.
Cara kerja C++ ada 2 tahap :
· Pertama, inisialisasi data
· Kedua, ekesekusi constructor
Jika menggunakan langkah kedua , eksekusi program dilakukan 2 kali: pertama
inisialisasi data lalu assignment. Sedangkan menggunakan member initialization hanya
memanggil sekali memanggil constructor calss string. Sonstructor dengan satu argument
berfungsi sebagai implicit conversion operator .
Sebagai contoh deklarasi class A dan B berikut :
Class A
{
Public :
A () ;
} ;
Class B
{
Public :
B (const A&) ;
} ;
Lalu terjadi konversi type obyek A ke B secara implicit melalui Copy constructor B
A a
B b=a ; //implicit conversion

Buble Sort

Pengertian/Konsep Buble Sort

Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada

dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air,

maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada

pengurutan gelembung.

Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara

melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa

dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan

berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan

dengan lambat menggelembung ke posisinya yang tepat.
Kelebihan Bubble Sort

* Metode Buble Sort merupakan metode yang paling simpel
* Metode Buble Sort mudah dipahami algoritmanya

Kelemahan Bubble Sort

Meskipun simpel metode Bubble sort merupakan metode pengurutanyang paling tidak efisien.

Kelemahan buble sort adalah pada saat mengurutkan data yang sangat besar akan mengalami

kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data

yang diolah jika data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap

sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap

data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.
Algoritma Bubble Sort

1. Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai

maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak

sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z)

kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending

(A-Z).
2. Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini

sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
3. Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n.

Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan

ke-1. mulai dari data ke-1 dgn data ke-2, dst.
4. Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.

Contoh Kasus Bubble Sort

Misalkan kita punya data seperti ini: 6, 4, 3, 2 dan kita ingin mengurutkan data ini

(ascending) dengan menggunakan bubble sort. Berikut ini adalah proses yang terjadi:

Iterasi ke-1: 4, 6, 3, 2 :: 4, 3, 6, 2 :: 4, 3, 2, 6 (ada 3 pertukaran)

Iterasi ke-2: 3, 4, 2, 6 :: 3, 2, 4, 6 :: 3, 2, 4, 6 (ada 2 pertukaran)

Iterasi ke-3: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 1 pertukaran)

Iterasi ke-4: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 0 pertukaran) -> proses selesai
Analisis Algoritma Bubble Sort

Tujuan dari analisis algoritma adalah untuk mengetahui efisiensi dari algoritma. Dalam hal

ini dilakukan pembandingan antara dua atau lebih algoritma pengurutan.Tahap analisis adalah

melakukan pengecekan program untuk memastikan bahwa program telah benar secara logika maupun

sintak (tahap tracing atau debugging). Tahap selanjutnya yaitu menjalankan program untuk

mengetahui running time atau waktu komputasi dalam hal ini
termasuk jumlah langkah. Data uji yang digunakan adalah data yang tidak terurut atau data

random, terurut membesar/, dan terurut mengecil.

Salah satu cara untuk menganalisa kecepatan algoritma sorting saat running time adalah

dengan menggunakan notasi Big O. Algoritma sorting mempunyai kompleksitas waktu terbaik,

terburuk, dan rata-rata. Dengan notasi Big O, kita dapat mengoptimalkan penggunaan

algoritma sorting. Sebagai contoh, untuk kasus dimana jumlah masukan untuk suatu pengurutan

banyak, lebih baik digunakan algoritma sorting seperti quick sort, merge sort, atau heap

sortkarena kompleksitas waktu untuk kasuk terburuk adalah O(n log n). Hal ini tentu akan

sangatberbeda jika kita menggunakan algoritma sorting insertion sort atau bubble sort dimana

waktu yang dibutuhkan untuk melakukan pencarian akan sangat lama. Hal ini disebabkan

kompleksitas waktu terburuk untuk algoritma sorting tersebut dengan jumlah masukan yang

banyak adalah O(n2).

Dari grafik dibawah dapat diketahui buble sort adalah metode yang paling lambat dari yang

lambat-lambat..heheheh..
Implementasi Bubble Sort dalam Bahasa C/C++

Berikut ini listing program atau kode program metode bubble sort
dalam bahasa C/C++

#include
void bubbleSort(int data[], int n){
int i, j=0, temp, flag = 1;
while(flag){
flag = 0;
for(i=0; idata[i+1]){
temp = data[i];
data[i] = data[i+1];
data[i+1] = temp;
flag++;
}
}
}
}
main(){
int data[1000];
int n, i;
printf("________.:: BUBBLE SORT :.________\n");
printf("Enter numbers of data(maks 1000): ");
scanf("%d", &n);
printf("Data (separate by space): ");
for(i=0; i scanf("%d", &data[i]);
bubbleSort(data, n);
printf("\nOutput after sort:\n");
for(i=0; i printf("%d ", data[i]);
getch();
return 0;}

Pointer

Pointer Pada C++



Pointer adalah built-in type di C dan C++, dimana C++ mengambil konsep pointer dari C. Pointer sebenarnya sangat terkait dengan “Abstract C Machine”, yaitu model mesin abstrak dimana program C bekerja. Abstract C Machine adalah mesin abstrak dimana mesin tersebut memiliki prosesor untuk menginterpretasikan stream of instruction, dan addressable memory yang terbagi kedalam 3 bagian : automatic memory, static memory dan free memory. Addressable memory adalah memory yang konten-nya dapat diambil jika diketahui alamatnya. Lebih jauh lagi, terdapat asumsi bahwa konten memori dapat di ambil dengan waktu konstan, tidak peduli berapa nilai alamat.Hal ini disebut dengan Random Access Memory.



Penggunaan Awal Pointer

Jika variabel merupakan isi memori, dan untuk mengakses isi memori tersebut diperlukan address, lalu bagaimana cara kita mengetahui alamat dari suatu variabel ? Jawabannya adalah : untuk kebanyakan kasus kita sama sekali tidak perlu tahu alamat dari sebuah variabel. Untuk mengakses sebuah variabel kita hanya perlu nama dari variabel tersebut. Tugas kompiler lah yang mentranslasikan nama ke alamat mesin yang diperlukan oleh komputer.

Akan tetapi terdapat beberapa kasus dimana kita tidak mungkin memberi nama pada sebuah entitas di program kita. Hal ini terjadi terutama saat kita menggunakan data struktur dinamis seperti linked list, resizeable array, tree dan lain sebagainya. Hal ini karena kita tidak mungkin memberi nama terhadap entitas yang mungkin ada atau tidak ada. Struktur seperti linked list hampir mustahil dibuat tanpa pointer tanpa harus mendefinisikan LISP-like list.

Inilah awal mula penggunaan pointer sebagai moniker. Istilah moniker di sini berarti sesuatu yang menunjuk atau mengacu kepada entitas lain. Istilah moniker ini bukanlah istilah standard dan lazim , tetapi sesuatu yang saya pilih impromptu untuk membedakan dengan pointer atau reference yang sudah memiliki arti tersendiri.

Penggunaan lain pointer sebagai moniker adalah untuk mengatasi kelemahan bahasa C awal : Dahulu fungsi – fungsi di C hanya mengerti pass by value. Pointer digunakan untuk mengemulasi pass by reference karena pointer berisi alamat ke objek lain, sehingga fungsi tersebut dapat mengubah objek tersebut dengan memanipulasi pointer.

Pertanyaanya : siapa yang bertugas menentukan alamat objek yang di tunjuk oleh pointer dalam kasus ini ? jelas bukan kompiler karena objek tersebut tidak bernama. Apakah kita sebagai programmer menentukannya sendiri ? ternyata tidak. Hal tersebut ditentukan oleh fungsi malloc dan sejenisnya (dan juga new di C++), atau untuk kasus passing pointer ke dalam fungsi, operator &. Jadi dalam hal ini kita tidak juga menentukan alamat sebuah objek.







Builtin Array di C dan C++

Sebelum membahas array di C dan di C++, ada baiknya kita membahas tentang array. Array adalah asosiasi antara sebuah index dengan nilai. Jika diketahui sebuah index, kita akan mengetahui nilainya. Dari definisi ini :



1. Tidak disebutkan bahwa index harus integer, atau tipe tertentu.

2. Tidak disebutkan range dari indexnya dimulai dari nilai tertentu, Bahkan tidak disebutkan bahwa indeks nya memiliki batas bawah maupun batas atas.

3. Tidak disebutkan bahwa nilai harus disimpan secara contigous, bahkan tidak disebutkan bahwa nilainya harus di simpan sama sekali.



Akan Tetapi :

1. Banyak bahasa pemrograman yang di desain tahun 60-an hingga tahun 70-an menentukan bahwa index array adalah integer atau sesuatu yang bisa dikonversi menjadi integer atau sesuatu yang memiliki nilai berurutan seperti integer.

2. Beberapa bahasa menentukan bahwa array dimulai dengan nilai tertentu. contohnya di C, array dimulai dari 0 sementara di Pascal Array dimulai dari 1. Dalam Algo-68 programmer dapat menentukan sendiri batas- batas array. Akan tetapi dalam semua bahasa pemrograman mengakses nilai dengan indeks yang di luar batas dianggap sebagai programming error.

3. Semua bahasa pemrogramman yang saya tahu menyimpan elemen – elemen array di memory. beberapa bahasa, misalnya C, menjamin bahwa elemen – elemen tersebut disimpan dalam memory yang contigous.



Sekarang tipe yang lebih mendekati definisi awal array tersedia dengan nama associative array. Tipe ini didukung oleh beberapa bahasa seperti PHP dan JavaScript, dan juga tersedia dalam beberapa bahasa lain sebagai library ( seperti std::map di C++).

Kembali ke C dan C++ array, kita dapat tentukan beberapa property array : zero based, contigous dan convertible to pointer. Banyak alasan dengan dipilihnya property seperti ini, tapi yang paling penting adalah efisiensi, yang akan kita bicarakan sebentar lagi. setiap array dapat dikonversi menjadi pointer yang menunjuk ke elemen pertama. Hal ini sangat konvenien mengingat dynamic array diciptakan dengan alokasi memori dari free memory (dengan fungsi calloc, yang berarti contigous alloc. yang aneh adalah fungsi ini berperilaku mirip dengan malloc kecuali dia menginisialisasi memori dengan nol. ). Kemudian kita tahu bahwa elemen dalam array di simpan secara berurutan, dengan demikian alamat semua elemen array adalah ptr + n * sizeof(elemen). Dengan mendefinisikan pointer arithmatic, didapat kesamaan ar[idx] == *(ar + idx). hal ini menimbulkan sesuatu yang menarik , ar[idx] == *(ar + idx) == *(idx + ar) == idx[ar] (yes, it is valid C !!).

Operasi pointer arithmatic lain juga didefinisikan untuk pointer. yang menarik adalah increment dan decrement. programmer dapat memeriksa semua elemen dalam array dengan cara menginkremen pointer dari pointer penunjuk elemen pertama. Tentu saja hal yang sama dapat dilakukan dengan indexing biasa, ar[idx], akan tetapi dengan operasi pointer bisa lebih efisien. Alasannya terletak pada bagaimana cara komputer membaca data di ar[idx]. Untuk mesin yang memiliki indexed addressing hal ini cukup sederhana dan efisien (ar jadi base, idx jadi index, fetching cukup 1 instruksi mov). Tetapi untuk mesin yang tidak memiliki indexed addressing, akan ada operasi ADD antara ar dan idx, lalu simpan hasilnya ke suatu tempat (register), lalu baru mov. Kadang – kadang register tersebut digunakan untuk operasi ADD sehingga terdapat beberapa mov untuk menyimpan state. Akan tetapi jika menggunakan pointer arithmatic, cukup meng-increase nilai yang sudah ada di register, lalu mov. Tentu saja instruksi di dalam loop juga mempengaruhi efisiensi ini, tetapi untuk mesin yang mendukung operasi increment langsung, iterasi lewat pointer biasanya lebih efisien.Ini adalah penggunaan pointer sebagai iterator. Nama iterator diambil dari STL, dan iterator di STL adalah abstraksi dari pointer. Yang menakjubkan adalah konsep iterator, yang digeneralisasi dari pointer, adalah konsep yang cukup powerful untuk merepresentasikan semua algoritma yang bekerja untuk linear container ( linear container adalah semua container yang memiliki iterator yang menunjuk pada elemen pertama, memiliki iterator yang menunjuk pada elemen one-past-end, dan semua elemen dapat dicapai dengan melakukan operasi incremen dari iterator penunjuk elemen pertama sebanyak yang diperlukan. Contoh linear container adalah array, vector, linked – list, dan deque. contoh yang bukan linear container adalah graph dan forest.).