SATU UNTUK SEMUA

Just another WordPress.com weblog

Linked List,,Pointer dan Contoh Program C++

LINKED LIST

Linked list (list bertaut) adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu komputer. Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibutuhkan. Linked list mirip dangan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).

Linked List sering disebut juga Senarai Berantai
Linked List saling terhubung dengan bantuan variabel pointer

Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.

linked-list

Gambar tersebut menunjukkan Linked List tunggal atau ’singly-linked list’ dimana tiap simpul hanya memiliki satu taut (link) yang merujuk ke simpul berikutnya atau nilai null pada akhir simpul. Seranai berantai ini hanya bisa diakses maju dari awal simpul ke akhir simpul.

Operasi-Operasi yang ada pada Linked List
Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
Find First
Fungsi ini mencari elemen pertama dari linked list
Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

Operasi-operasi untuk Stack dengan Linked List
IsEmpty
Fungsi memeriksa apakah stack yang adamasih kosong.
Push
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.
Pop
Fungsi ini mengeluarkan elemen teratas dari stack.
Clear
Fungsi ini akan menghapus stack yang ada.

Operasi-operasi Queue dengan Double Linked List
IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.
IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
DeQueue
Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).

Single Linked List Circular

Single Linked List Circular (SLLC) adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

Pengertian:
Node : rangkaian beberapa simpul
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar
picture1

Ilustrasi SLLC
Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar.

picture2

Deklarasi:
Deklarasi node dibuat dari struct berikut ini:
typedef struct TNode{
int data;
TNode *next;
};

Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru
berserta alokasi memorinya.

TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;

Dibutuhkan satu buah variabel pointer: head
Head akan selalu menunjuk pada node pertama
picture3

Penambahan data di depan
Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya.
Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu.

HEAD Single Linked List Circular

Penambahan data di depan
picture4

Penambahan data di depan

void insertDepan(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
baru->next = head;
head = baru;
bantu->next = head;
}
printf(”Data masuk\n“);
}
Penambahan data di belakang
Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya.
Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.

picture5 picture6

Penambahan data di belakang

void insertBelakang (int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next != head){
bantu=bantu->next;
}
bantu->next = baru;
baru->next = head;
}
printf(”Data masuk\n“);
}

Operasi Penghapusan

Penghapusan node dilakukan dengan memutus rantai node kemudian menghapus node. Jika node berada di tengah rangkaian, rangkaian yang terputus perlu disambung kembali. Untuk memudahkan penghapusan simpul dibutuhkan dua cursor sebagai simpul bantu. Selain cursor juga dibutuhkan simpul head sebagai acuan awal simpul dalam rangkaian.

Berikut langkah langkah untuk menghapus simpul dalam rangkaian:

  • Buat cursor bantu yang menunjuk ke awal node(simpul).
  • Pindahkan cursor ke node berikutnya
  • Putus sambungan awal node dengan node berikutnya.
  • Hapus rangkaian
  • Jika berada di akhir rangkaian, putuskan dari rangkaian sebelumnya
  • Jika di tengah rangkaian, pindahkan penunjukan node berikutnya, atau di akhir, atau setelah node yang akan dihapus

Ilustrasi Hapus Depan

picture7

Ilustrasi Hapus Depan

void hapusDepan (){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
hapus = head;
d = head->data;
if(head->next != head){
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
head = head->next;
delete hapus;
bantu->next = head;
}else{
head=NULL;
}
printf(“%d terhapus\n“,d);
} else printf(”Masih kosong\n“);
}

Ilustrasi Hapus Belakang
picture8

Ilustrasi Hapus Belakang

void hapusBelakang(){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
hapus = head;
if(head->next == head){
head = NULL;
}else{
bantu = head;
while(bantu->next->next != head){
bantu = bantu->next;
}
hapus = bantu->next;
d = bantu->data;
bantu->next = head;
delete hapus;
}
printf(“%d terhapus\n“,d);
} else printf(”Masih kosong\n“);
}

Contoh Coding Stack Dengan Linked List

#include
#include

/* membuat linked list */
typedef struct myLinkedList {
char nim[10];
char nama[35];
int nilai;

myLinkedList *next;
};

myLinkedList *head;

/* keadaan awal */
void init() {
head = NULL;
}

/* fungsi untuk mengecek linked list
* apakah kosong atau tidak
* jika kosong maka bernilai 1
* jika tidak kosong maka bernilai 0
*/
int paKosong() {
if (head == NULL) return 1;
else return 0;
}

/**
* fungsi untuk menambahkan data dari depan node
*/
void tambahDepan() {

myLinkedList *baru;
baru = new myLinkedList;

cout << “Masukkan Data lengkap di bawah ini : ” <<>> baru->nim;
cout << “Nama : “; cin >> baru->nama;
cout << “Nilai : “; cin >> baru->nilai;

baru->next = NULL;

if (paKosong() == 1) {
head = baru;
head->next = NULL;
} else {
baru->next = head;
head = baru;
}
}
/**
* fungsu untuk menambahkan data dari depan node
*/

void tambahBelakang() {

myLinkedList *baru, *bantu;
baru = new myLinkedList;

cout << “Masukkan Data lengkap di bawah ini : ” <<>> baru->nim;
cout << “Nama : “; cin >> baru->nama;
cout << “Nilai : “; cin >> baru->nilai;

baru->next = NULL;

if (paKosong() == 1) {
head = baru;
head->next = NULL;
} else {
bantu = head;
while (bantu->next != NULL) {
bantu = bantu->next;

}
bantu->next = baru;
}
}

/**
* fungsi untuk menghapus dari depan node
*/
void hapusDepan() {
myLinkedList *hapus;
char *data;
if (paKosong() == 0) {
if (head->next != NULL) {
hapus = head;
data = hapus->nim;
head = head->next;
delete hapus;
} else {
data = head->nim;
head = NULL;
}

cout <<>

/**
* fungsi untuk menghapus dari belakang node
*/
void hapusBelakang() {
myLinkedList *hapus, *bantu;
char *data;
if (paKosong() == 0) {
if (head->next != NULL) {
bantu = head;
while(bantu->next->next != NULL) {
bantu = bantu->next;
}

hapus = bantu->next;
data = hapus->nim;
bantu->next = NULL;
delete hapus;
} else {
data = head->nim;
head = NULL;
}
cout <<>

cout << “Tekan Enter untuk kembali ke Menu!”; getch(); }

/**
* fungsi untuk menampilkan data linked list
*/

void tampilData() {
int no = 1;

myLinkedList *bantu;
bantu = head;
if (paKosong() == 0) {
while (bantu != NULL) {
cout << “No. : ” <<>nim <<>nama <<>nilai <<>

no++;
bantu = bantu->next;
}
cout <<>

} else {
cout << “Data masih kosong ” <<>

/**
* fungsi Menu, Untuk menentukan linked list mana
* yang dipilih
*/
int menu() {
int pilihan;

cout << “+———————-+\n”; cout << “| MENU PILIHAN |\n”; cout << “+———————-+\n”; cout << “| 1. Tambah Depan |\n”; cout << “| 2. Tambah Belakang |\n”; cout << “| 3. Hapus Depan |\n”; cout << “| 4. Hapus Belakang |\n”; cout << “| 5. Tambah Tengah |\n”; cout << “| 6. Hapus Tengah |\n”; cout << “| 7. TampilData |\n”; cout << “| 8. Keluar |\n”; cout << “+———————-+\n”; cout << “| PILIHAN ANDA ? [ ] |\n”; cout << “+———————-+\n”;

cin >> pilihan;
return pilihan;
}

/**
* fungsi operasi data
*/
void operasiData() {
int pilih;

do {
pilih = menu();

switch (pilih) {
case 1 :
tambahDepan();
break;
case 2 :
tambahBelakang();
break;
case 3 :
hapusDepan();
break;

case 4 :
hapusBelakang();
break;
case 5 :
tampilData();
break;
case 6:

cout << “Terima kasih coy!!!”; break; } } while (pilih != 6); }

/**
* PROGRAM UTAMA
*/
void main() {
init();
operasiData();
}

Setelah diCompile, maka akan menghasilkan tampilan:

stack-linked-list

_____________________________________________________________________________________________

POINTER

Penjelasan tentang pointer
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.).

—Fixed memory Location
Dalam pemrograman, kita dihadapkan pada beberapa situasi seperti :
– setelah startup, prosesor 80386 akan memulai eksekusi pada alamat ( … lupa).
– Interrupt vector beberapa prosesor ditaruh pada alamat yang ditentukan oleh pembuat prosesor tersebut.
– Video Memory di DOS dimulai pada alamat (… lupa).

Situasi – situasi tersebut hanya mungkin terjadi jika kita memrogram “close to metal” e.g membuat operating system, atau kita memrogram dalam OS yang super primitif seperti DOS. Dalam kasus – kasus ini kita memerlukan pointer dengan alamat di set ke nilai tertentu. Ini adalah penggunaan pointer sebagai abstraksi alamat di hardware. Penggunaan ini adalah penggunaan pointer paling jarang.

— So, What’s a big deal about it ?
Ketiga fungsi pointer di atas memerlukan operasi yang berbeda- beda. Contohnya jika pointer berfungsi sebagai moniker, operasi yang sangat diperlukan adalah fungsi malloc, calloc, free, new, delete, operator ->, operator * dan operator &. sebagai moniker pointer tidak memerlukan konvertability ke integer dan operasi pointer arihmatic (walaupun ada trik mengakses field struct dari pointer dengan meng-cast pointer to struct menjadi char*, tambahkan offsetnya, lalu baca dengan operator * dan di cast ke tipe field tersebut. trik ini sangat berbahaya dan sebaiknya tidak dipakai ).
Jika pointer berfungsi sebagai iterator, operasi pointer arithmatic adalah esensial. Tetapi operasi new dan delete sama sekali tidak di perlukan (kecuali untuk array of pointer). bottom line is: you do not do memory management via iterator.
Sifat konvertibilitas antara integer dan pointer hanya diperlukan jika pointer tersebut dipakai sebagai abstraksi fixed address. Dua fungsi lain tidak memerlukan sifat ini.

— Pointer in OOP
C++ mendukung OOP, akan tetapi pada saat yang sama juga kompatibel dengan C. Hal ini menimbulkan masalah. Akan tetapi sebelum melihat apa masalahnya, ada baiknya kita bahas sedikit tentang Polymorphism.

Polymorphism adalah jawaban untuk pertanyaan: bagaimana cara menulis fungsi atau prosedur yang tidak dibatasi oleh tipe. contohnya adalah fungsi average, fungsi ini menjumlahkan sejumlah elemen dan membaginya dengan banyaknya elemen. hal ini benar untuk banyak tipe termasuk integer, koordinat kartesian, bilangan kompleks, kuartenion, matrix ,dsb walau aturan penjumlahan tipe – tipe tersebut berbeda. Untuk bahasa yang tidak mendukung polymorphism, anda harus menulis fungsi seperti averageInt, averageMatrix, averageComplex, etc.

Dari sifatnya, polymorphism terbagi dua: ad-hoc polymorphism dimana polymorphism hanya bekerja pada tipe yang sudah ada. contoh mekanisme ad-hoc polymorphism adalah function dan operator overloading. Sedangkan true polymorphism atau parametric polymorphism dapat digunakan bahkan untuk tipe yang belum dispesifikasi. Perbedaan lainnya adalah untuk ad-hoc polymorphism biasanya anda harus menulis fungsi untuk semua tipe yang berpartisipasi dalam mekanisme polymorphism, sperti menulis average untuk integer, lalu untuk quartenion, lalu satu lagi untuk complex, dll. Sedangkan untuk parametric polymorphism anda hanya perlu menulis satu fungsi.

Dari binding-time nya, polymorphism dapat dibagi 2: static dan dynamic polymorphism. Static polymorphism menentukan fungsi mana yang akan di panggil (atau mungkin di generate ) pada saat kompilasi. Sedangkan dynamic polymorphism menentukan fungsi yang di panggil pada saat run-time. contoh static polymorphism adalah template, sedangkan contoh dynamic polymorphism adalah virtual function.

static polymorphism dapat dibagi menjadi predicative atau impredicative, tetapi hal ini tidak ada hubungannya dengan diskusi kita.

Untuk dynamic polymorphism, dapat dibagi lagi berdasarkan berapa banyak parameter yang berpengaruh dari penentuan fungsi. Jika hanya parameter pertama yang berpengaruh, hal ini disebut dengan single dispatch. Jika lebih dari satu, hal ini disebut dengan multimethod. multimethod yang dipengaruhi oleh dua parameter mempunyai nama khusus yaitu double dispatch. Harap perhatikan bahwa p->somefunc(a,b) itu secara prinsip sama dengan somefunc(p,a,b) dimana p adalah this parameter (walaupun semua kompiler akan mereject kalau anda mengganti fungsi seperti itu).

Dynamic Polymorphism juga dapat dibagi berdasarkan constraint nya menjadi dua: Subtyping Polymorphism dimana polymorphic type harus merupakan turunan dari satu base class yang merupakan sebuah interface yang menentukan sifat mana yang polymorphic. Yang lainnya adalah DuckTyping yang tidak memerlukan base class yang berfungsi sebagai interface. Dalam DuckTyping sebuah object dapat menerima message apa saja, walau jika object tersebut tak dapat merespond message tersebut objeck yang bersangkutan akan mengeluarkan error seperti DoesNotUnderstand message di SmallTalk. Untuk subtype polymorphism, hal ini tidak mungkin karena sebuah object hanya akan menghandle message yang didefinisikan di base class, dan kompiler akan mereject message lain.

Kembali ke bahasan kita, C++ mendukung Subtyping single dispatch dynamic Polymorphism. Jadi untuk dynamic polymorphism, semua tipe yang ingin digunakan secara polymorphic harus diturunkan dari satu base class. C++ juga mengharuskan semua fungsi yang bisa dipanggil secara polymorphic harus dideklarasikan virtual. Dan pemilihan fungsi yang diperlukan hanya ditentukan oleh satu parameter (this parameter) melalui mekanisme vtable.

So, what’s the big deal ?
Masalahnya adalah untuk semua bahasa yang menggunakan subtype polymorphism, semua object harus bisa di akses melalui base class nya. Jadi kode berikut harus valid:

Parent p = create_child(); // asumsi nya create child menghasilkan
// object child;

Hal ini menimbulkan pertanyaan : Bagaimana caranya membuat kode di atas valid ?
Dalam bahasa pemrograman tradisional, ketika anda mendeklarasikan sebuah variabel, anda menciptakan instance dari sebuah tipe, kecuali jika dideklarasikan khusus. Di C

Sometype somevar;

artinya anda menciptakan sebuah objek somevar bertipe Sometype.

Sometype somevar2 = somevar;

artinya anda mengkopi nilai somevar ke somevar2

somevar2 == somevar; // OK, ini tidak didefinisikan di C untuk User Defined Type,
// but you got the idea

artinya anda membandingkan nilai somevar dengan nilai somevar2. Mari kita sebut ini value semantic, dimana sebuah variabel mengandung isi instance dari tipe tertentu.
Lalu perhatikan kode berikut :

Child child;
Parent parent = child;

See the problem ? Masalahnya adalah anda mencoba mengkopi nilai child ke variabel parent, tapi apa artinya operasi kopi tersebut ? jika berarti mengopi nilai byte by byte, implikasinya adalah ukuran parent dan child harus sama. Akan tetapi hal ini sulit atau tidak mungkin dipenuhi. Bila parent adalah pure interface, parent hampir tidak memiliki data member, tapi child akan memiliki data member untuk mendukung operasi – operasi method-nya.

Bagaimana cara mengatasinya ? salah satu cara yang populer adalah dengan tidak menggunakan value semantic. Di bahasa seperti Java, setiap variable adalah reference ke sebuah instance. Artinya:
1. Ketika anda mendeklarasikan sebuah variabel, anda tidak menginstansiasi sebuah object. object harus di instansiasi secara terpisah, biasanya lewat operator new.
2. Ketika anda mengkopi dua buah variabel, anda tidak mengkopi instance byte by byte, tapi hanya membuat dua reference mengacu pada object yang sama. Jika ingin menghasilkan kopi dari instance, biasanya anda menggunakan method seperti clone.
3. Ketika anda membandingkan dua buah variabel, anda hanya mengetahui apakah dua variabel tersebut merujuk pada objek yang sama atau tidak. jika anda ingin membandingkan nilainya, anda harus menggunakan method seperti equal.
let’s call this reference semantic.

Masalahnya C++ karena berbagai alasan (salah satunya kompatibilitas dengan C) tidak mungkin mengadopsi reference semantic dan harus tetap menggunakan value semantic. Akan tetapi reference semantic sepertinya diperlukan untuk subtype polymorphism. so, what to do ? Ternyata Pointer adalah object yang dapat dipakai untuk mengemulasi reference semantic tanpa harus mengubah bahasa menggunakan reference semantic.
Dengan demikian dynamic polymorphism di C++ harus menggunakan pointer (atau reference, yang sebenarnya adalah pointer dengan sedikit perubahan sifat).

— Bahaya Pointer
1. Bahaya yang mungkin ada dengan pointer sebagai moniker: memory leak, double delete, invalid memory access. Semuanya dapat dihindari dengan ownership analysis yang bagus (pada setiap saat, harus diketahui pihak mana yang bertanggung jawab mendelete sebuah object). Jika hal ini sulit dilakukan, misalnya karena shared ownership, anda dapat menggunakan smart pointer atau garbage collector.
2. Bahaya yang mungkin ada dengan pointer sebagai iterator: array out of bound. Salah satu cara yang efektif menghindari hal ini adalah dengan menggunakan standard algorithm.
3. Bahaya yang mungkin ada dengan pointer sebagai abstraksi fixed memory : Tidak tahu, tetapi ini bukan mainan sembarang programmer.

— Bahasa Pemrograman tanpa pointer ?
1. Semua Bahasa pemrograman Fungsional, terutama yang murni , tidak mengenal pointer atau memerlukan pointer. Akan tetapi bahasa ini menggunakan model komputasi yang jauh berbeda, bukan abstract C machine.

2. Beberapa bahasa pemrograman dengan reference semantik dapat mengklaim mereka tidak memiliki pointer, akan tetapi setiap variabel sebenarnya adalah pointer. Secara fisik mungkin reference tidak memiliki struktur seperti pointer (biasanya merupakan data struktur yang lebih kompleks sehingga lebih friendly terhadap garbage collector) tapi reference tersebut memiliki fungsi yang mirip dengan pointer di C atau C++. Ada yang bilang bahwa reference dalam bahasa – bahasa ini menyebabkan optimasi lebih mudah karena tidak menyebabkan aliasing, tetapi optimasi tersebut juga mungkin dilakukan di C dan C++ ( dengan restrict pointer, sayangnya belum merupakan bagian dari standard C++).

_____________________________________________________________________________________________

Algoritma Sorting
ada beberapa Algoritma Sorting, yaitu :
1.Insertion Sort
Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu.
Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling
kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja,sebutlah meja
ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian
kita mempunyai meja yang lain,meja kedua, dimana kartu yang diurutkan akan diletakkan.Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama
dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan
dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang
sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu
pada meja pertama telah diletakkan berurutan pada meja kedua.
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi
dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja
kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan
kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah
diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang
tersisa pada bagian array yang belum diurutkan.

2.Selection Sort
Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan
menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion
sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan. Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah–langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan dapat digeser dengan kartu yang bernilai lebih rendah.Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi

3.Merge Sort
Sebelum mendalami algoritma merge sort, mari kita mengetahui garis besar dari
konsep divide and conquer karena merge sort mengadaptasi pola tersebut.
Pola Divide and Conquer
Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan
permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah,
kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan
utama.
Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.
– Divide
Memilah masalah menjadi sub masalah
– Conquer
Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut
cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan
lebih efektif
– Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju
penyelesaian atas permasalahan utama

4.Quicksort
Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga
berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini
hanya mengikuti langkah – langkah sebagai berikut :
1. Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r]
dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q]
dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan
elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada
elemen q merupakan salah satu bagian dari prosedur pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif
Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi
pengurutan elemen – elemen pada sub-array

Algoritma Binary Search

Binary Search adalah algoritma pencarian yang lebih efisien daripada algorima Sequential Search. Hal ini dikarenakan algoritma ini tidak perlu menjelajahi setiap elemen dari tabel. Kerugiannya adalah algoritma ini hanya bisa digunakan pada tabel
yang elemennya sudah terurut baik menaik maupun menurun.Pada intinya, algoritma ini menggunakan prinsip divide and conquer, dimana sebuah masalah atau tujuan diselesaikan dengan cara mempartisi masalah menjadi bagian yang lebih kecil. Algoritma ini membagi sebuah tabel menjadi dua dan memproses satu bagian dari tabel itu saja.
Algoritma ini bekerja dengan cara memilih record dengan indeks tengah dari tabel
dan membandingkannya dengan record yang hendak dicari. Jika record tersebut lebih rendah atau lebih tinggi, maka tabel tersebut dibagi dua dan bagian tabel yang bersesuaian akan diproses kembali secara
rekursif.

_____________________________________________________________________________________________

Contoh Program sort, binary, sequential  pada C++

Ini adalah program sorting paling lengkap.

contoh program sort c++ :

#include <iostream.h>
#include <conio.h>

int data[100],data2[100];
int n;

void tukar(int a,int b)
{
int t;
t = data[b];
data[b] = data[a];
data[a] = t;
}

void bubble_sort()
{
for(int i=1;i<n;i++)
{
for(int j=n-1;j>=i;j–)
{
if(data[j]<data[j-1]) tukar(j,j-1);
}
}
cout<<”bubble sort selesai!”<<endl;
}

void exchange_sort()
{
for (int i=0; i<n-1; i++)
{
for(int j = (i+1); j<n; j++)
{
if (data [i] > data[j]) tukar(i,j);
}
}
cout<<”exchange sort selesai!”<<endl;
}

void selection_sort()
{
int pos,i,j;
for(i=0;i<n-1;i++)
{
pos = i;
for(j = i+1;j<n;j++)
{
if(data[j] < data[pos]) pos = j;
}
if(pos != i) tukar(pos,i);
}
cout<<”selection sort selesai!”<<endl;
}

void insertion_sort()
{
int temp,i,j;
for(i=1;i<n;i++)
{
temp = data[i];
j = i -1;
while(data[j]>temp && j>=0)
{
data[j+1] = data[j];
j–;
}
data[j+1] = temp;
}
cout<<”insertion sort selesai!”<<endl;
}

void QuickSort(int L, int R) //the best sort i’ve ever had
{
int i, j;
int mid;

i = L;
j = R;
mid = data[(L+R) / 2];

do
{
while (data[i] < mid) i++;
while (data[j] > mid) j–;

if (i <= j)
{
tukar(i,j);
i++;
j–;
};
} while (i < j);

if (L < j) QuickSort(L, j);
if (i < R) QuickSort(i, R);
}

void Input()
{
cout<<”Masukkan jumlah data = “; cin>>n;
for(int i=0;i<n;i++)
{
cout<<”Masukkan data ke-”<<(i+1)<<” = “; cin>>data[i];
data2[i] = data[i];
}
}

void Tampil()
{
cout<<”Data : “<<endl;
for(int i=0;i<n;i++)
{
cout<<data[i]<<” “;
}
cout<<endl;
}

void AcakLagi()
{
for(int i=0;i<n;i++)
{
data[i] = data2[i];
}
cout<<”Data sudah teracak!”<<endl;
}

void main()
{
int pil;
clrscr();
do
{
clrscr();
cout<<”Program Sorting Komplit!!!”<<endl;
cout<<”*********************************************”<<endl;
cout<<” 1. Input Data”<<endl;
cout<<” 2. Bubble Sort”<<endl;
cout<<” 3. Exchange Sort”<<endl;
cout<<” 4. Selection Sort”<<endl;
cout<<” 5. Insertion Sort”<<endl;
cout<<” 6. Quick Sort”<<endl;
cout<<” 7. Tampilkan Data”<<endl;
cout<<” 8. Acak Data”<<endl;
cout<<” 9. Exit”<<endl;
cout<<”    Pilihan Anda = “;  cin>>pil;
switch(pil)
{
case 1:Input(); break;
case 2:bubble_sort(); break;
case 3:exchange_sort(); break;
case 4:selection_sort(); break;
case 5:insertion_sort(); break;
case 6:QuickSort(0,n-1);
cout<<”quick sort selesai!”<<endl;
break;
case 7:Tampil(); break;
case 8:AcakLagi(); break;
}
getch();
}while(pil!=9);
}

contoh program searching (binary) pada c++ :

#include<iostream.h>
#include<conio.h>

int data[10] = {1,3,4,7,12,25,40,65,78,90};  //variabel global

int binary_search(int cari)
{
int l,r,m;
int n = 10;
l = 0;
r = n-1;
int ketemu = 0;
while(l<=r && ketemu==0)
{
m = (l+r)/2;
if( data[m] == cari )
ketemu = 1;
else
if (cari < data[m])
r = m-1;
else l = m+1;
}
if(ketemu == 1) return 1; else return 0;
}

void main()
{
clrscr();
int cari,hasil;
cout<<“masukkan data yang ingin dicari = “;
cin>>cari;
hasil = binary_search(cari);
if(hasil == 1)
{
cout<<“Data ada!”<<endl;
}
else
if(hasil == 0)
cout<<“Data Tidak ada!”<<endl;
getch();
}

contoh program searching (sequential) pada c++ :

#include <iostream.h>
#include <conio.h>
void main()
{
clrscr();
int data[8] = {8,10,6,-2,10,7,1,100};
int cari,index;
int ketemu=0;
cout<<“masukkan data yang ingin dicari = “;
cin>>cari;
for(int i=0;i<8;i++)
{
if(data[i] == cari)
{
ketemu=1;
index = i;
break;
}
}
if(ketemu == 1)
{
cout<<“Data ada!”<<endl;
cout<<“Data terletak di index ke – “<<index;
}
else cout<<“Data Tidak ada!”<<endl;
getch();
}

About these ads

Juni 15, 2009 - Posted by | Uncategorized

8 Komentar »

  1. lumayan…

    Komentar oleh singamasae | Juni 29, 2009 | Balas

  2. mAu taNya,,,gmn cRanYa masuKin bLo9eR k dLm wEb….??????

    Komentar oleh dWiE aFRiYanTi | Juli 14, 2009 | Balas

  3. mAu TaNya 9mN cRanya maSukin bLo9 ke wEb????

    Komentar oleh dWiE aFRiYanTi | Juli 14, 2009 | Balas

  4. terima kasih atas keterangannya..
    hanya saja belum ada contoh penggunaan c++..
    good luck..

    Komentar oleh agustriyan | Juli 24, 2009 | Balas

  5. Artikel yang sangat bagus…
    thanks yah…

    Komentar oleh Amaliah | November 28, 2009 | Balas

  6. algoritma mpusing bgt ya,,,
    tolong kasih tau cara penghapusan secara bubble sort donk????

    Komentar oleh wina | Januari 29, 2010 | Balas

  7. program yang link list itu pake turbo C++ atw dev C++ supaya bisa d rnn?

    Komentar oleh andry | Maret 20, 2010 | Balas

  8. krennnnnnnnnnnnnnnnnnnn
    makasi ya

    Komentar oleh tia | April 17, 2010 | Balas


Berikan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

Ikuti

Get every new post delivered to your Inbox.

%d blogger menyukai ini: