ajo loepus

Rabu, 02 September 2009

makalah struktur data dan algoritma

1. LATAR BELAKANG

Pada bahasa pemrograman tingkat tinggi, seperti Pascal dan C, telah tersedia jenis data standar integer, yang merupakan jenis data untuk menyimpan bilangan bulat. Secara algoritmik, jenis data integer tidak mempunyai batas nilai maksimum maupun batas nilai minimum, namun tidak demikian halnya dalam implementasi pada bahasa pemrograman. Sebagai contoh pada bahasa Turbo Pascal dan Turbo C, jenis data integer terbesar diimplementasikan dalam 4 byte data, yang berarti membatasi nilainya dari 2147483648 sampai dengan 2147483647. Pembatasan nilai ini akan meningkatkan efisiensi kompilator, tetapi di sisi yang lain akan membatasi perhitungan yang bisa dilakukan. Secara praktis hal ini diatasi dengan menggunakan jenis data real (atau float pada bahasa C) untuk melakukan perhitungan dengan bilangan bulat yang cukup besar, akan tetapi solusinya tidak selalu memuaskan. Jenis data real seringkali tidak bisa dipergunakan pada perhitungan yang menuntut kecermatan tinggi.

Suatu cara untuk mengatasi masalah ini adalah dengan mendefinisikan suatu struktur data baru menggunakan array. Tujuan penulisan makalah ini adalah mendefinisikan struktur data untuk mendukung operasi aritmetika pada bilangan bulat besar, dan MengimplemenTasi

kannya dalam bahasa C dan Java.

2. PENDAHULUAN

Secara tradisional, matakuliah Struktur Data difokuskan pada detail implementasi dari sejumlah struktur data sederhana; mahasiswa membuat dan mempelajari kode untuk linked list dan struktur data lain dari nol atau berdasarkan kode buatan dosen atau pengarang buku teks. Sebagai alternatif, diusulkan penggunaan Standard Template Library C++ (STL) yang telah teruji dan tersedia luas. STL yang termasuk dalam pustaka baku C++ ini telah menyediakan sejumlah besar struktur data dan algoritma untuk mengolah struktur data tersebut, sehingga pemrogram tidak lagi terbebani oleh detail implementasi. Dengan penggunaan STL, fokus matakuliah dapat digeser ke jenjang yang lebih tinggi, yaitu kepada pemilihan dan penggunaan struktur data secara tepat. Hal ini tepat dalam kurikulum yang memberi penekanan ke software engineering. Walaupun STL hingga saat ini belum mencakup semua struktur data yang mungkin ada, namun dengan penggunaan STL, perluasan juga dapat lebih mudah dilakukan ke struktur data yang lebih kompleks dan lebih dekat ke masalah nyata. Misalnya implementasi general tree, yang biasanya dihindari dalam zpengajaran Struktur Data tradisional karena tingkat kesulitannya yang tinggi, dapat dengan mudah dibuat dengan bantuan STL.

STL juga dapat digunakan oleh mahasiswa dalam matakuliahmatakuliah selanjutnya, dan, lebih penting lagi, dalam industri setelah nantinya mereka lulus. Dikembangkan oleh Alexander Stepanov dan Meng Lee dari Hewlett-Packard, STL telah dimasukkan sebagai bagian dari pustaka baku C++ oleh ANSI/ISO pada tahun 1994. Stepanov (1995) menyatakan bahwa STL telah dikembangkan dengan sangat memperhatikan sifat umum dan efisiensi.

Dua aspek ini memiliki arti penting dalam industri. Dengan perhatian pada aspek pertama, yaitu sifat umum, STL memiliki reusability yang tinggi sehingga penggunaannya dapat menghemat waktu dan sumber daya dalam pengembangan sistem. Semua struktur data dalam STL memiliki sifat umum, yaitu dapat menampung elemen bertipe data apa saja sesuai dengan yang ditentukan oleh pemrogram. Hal ini dimungkinkan oleh penggunaan fasilitas template (class dan function yang memiliki parameter berupa tipe data) yang tersedia pada C++.

Ini berbeda misalnya dengan pustaka baku Java untuk struktur data, yaitu Java Collections Framework (JCF), yang struktur datanya dapat memiliki sifat umum berkat penggunaan inheritance.

Namun atas desakan para pemrogram Java, fasilitas yang serupa dengan template juga telah ditambahkan pada versi Java yang terbaru, Java 2 Platform Standard Edition 5.0. Ini berarti bahwa pengalaman dalam menggunakan STL akan dapat bermanfaat juga saat bekerja dengan bahasa pemrograman lain seperti Java.

STL lebih jauh lagi memisahkan struktur data dengan algoritma, sehingga algoritma STL memiliki sifat umum, yaitu dapat diterapkan pada berbagai macam struktur data. Hal ini dimungkinkan oleh penggunaan fasilitas template dan karena algoritma STL tidak mengakses elemen secara langsung namun melalui sejenis pointer. Ada pandangan bahwa pemisahan ini merupakan kelemahan STL karena membuatnya tidak murni berorientasi objek dan karenanya memperbesar peluang terjadinya kesalahan pemrograman (Keffer 1995). Namun keuntungan dari pemisahan ini adalah bahwa pemrogram dapat menerapkan algoritma baru buatannya sendiri pada struktur data STL, dan dapat menerapkan algoritma STL pada struktur data baru buatannya sendiri.Fleksibilitas ini tentunya meningkatkan reusability STL. Dengan perhatian pada aspek kedua, yaitu efisiensi, STL dapat digunakan tanpa perlu mengorbankan efisiensi yang selama ini telah menjadi ciri khas dari C and C++. Walaupun memiliki sifat

umum, tiap komponen dalam STL memiliki implementasi yang efisiensinya tidak jauh berbeda dengan kode ekuivalennya yang dibuat secara manual. Bahkan ada argumentasi bahwa pemanggilan algoritma STL lebih baik daripada pembuatan algoritma secara manual (yang biasanya dilakukan pemrogram dengan menggunakan loop) karena algoritma STL seringkali lebih efisien. Selain alasan efisensi ini ada alasan-alasan lain, yaitu pembuatan loop lebih rentan terhadap kesalahan, dan pemanggilan algoritma STL seringkali menghasilkan kode yang lebih ringkas dan jelas sehingga lebih mudah dipelihara (Meyers 2001).

Berikutnya akan diberikan suatu pengantar singkat mengenai STL, dan kemudian akan dibicarakan hal-hal yang perlu diperhatikan dalam penggunaan STL untuk mengajarkan Struktur Data.

1 STL

Penjelasan dasar mengenai STL dapat diperoleh antara lain dari buku teks karya Hubbard (2000), Savitch (2002), dan Deitel dan Deitel (2003), sedangkan penjelasan lebih lanjut dapat diperoleh antara lain dari artikel karya Stepanov dan Lee (1995) dan buku teks karya Austern (1999). Berikut hanya akandiberikan pengantar singkat mengenai STL. STL terdiri atas tiga komponen, yaitu container, iterator, dan algorithm. Pada prinsipnya dapat dikatakan bahwa algorithm melakukan manipulasi terhadap container dengan bantuan iterator.

1.1 Container

Container adalah struktur data yang dapat menampung elemen bertipe data apa saja. Container diimplementasikan sebagai container class yang merupakan suatu template class, yaitu class yang memiliki parameter berupa tipe data. Beberapa di antaranya, yaitu vector, list, deque, stack, queue, priority_queue, set, dan map akan dibicarakan di sini. Tiap class tersebut didefinisikan pada header dengan nama yang sama dengan nama class yang dimilikinya, kecuali priority_queue didefinisikan pada header .

1.1.1 vector

Container vector diimplementasikan sebagai array dengan realokasi memori otomatis saat kapasitasnya dalam menampung elemen perlu ditambah. Iterator-nya berjenis random-access. Member function yang dimiliki antara lain:

• vector() merupakan default constructor yang membentuk vector kosong.

• vector(n) merupakan constructor yang membentuk vector berisi n buah elemen.

• empty() memberikan true jika dan hanya jika vector kosong.

• size() memberikan jumlah elemen.

• capacity() memberikan jumlah maksimum elemen yang dapat ditampung tanpa realokasi memori.

• reserve(n) melakukan alokasi atau realokasi memori sebesar n.

• operator [i] memberikan elemen kei.

• front() memberikan elemen paling awal.

• back() memberikan elemen terakhir.

• begin() memberikan iterator yang menunjuk ke elemen paling awal.

• end() memberikan iterator yang menunjuk ke posisi setelah elemen terakhir.

• push_back(x) menyisipkan elemen x pada bagian akhir.

• pop_back() menghapus elemen terakhir.

• insert(p, x) menyisipkan elemen x pada lokasi sebelum yang ditunjuk oleh p.

• erase(p) menghapus elemen pada lokasi yang ditunjuk oleh p.

• clear() menghapus semua elemen.

1.1.2 list

Container list diimplementasikan sebagai doubly-linked list. Iterator-nya berjenis bidirectional. Member function yang dimiliki oleh vector juga dimiliki oleh list, kecuali capacity(), reserve(), dan operator []. Class list memiliki member function yang tidak dimiliki oleh vector, antara lain:

• push_front(x) menyisipkan elemen x pada bagian awal.

• pop_front() menghapus elemen paling awal.

• splice(p, l, p1, p2) memindahkan elemen pada posisi p1 hingga p2-1 dari list l ke posisi p pada list ini.

• remove(x) menghapus semua elemen x.

• unique() menghapus semua elemen yang memiliki duplikat.

• merge(l) menggabungkan semua elemen pada list l ke list ini. Kedua list harus sudah terurut.

• reverse() memutarbalikkan susunan elemen.

• sort() mengurutkan elemen.

Dalam Java ada dua cara untuk menyatakan list, yaitu menggunakan array dinamis atau linked list. Kedua cara ini tercakup dalam kumpulan class java.util.ArrayList and java.util.LinkedList. ArrayList menyimpan obyek dalam array sedangkan LinkedList menyimpan obyek dalam node-node yang saling terkait oleh pointer.

Contoh operasi-operasi atau metode dalam list:

1. list.get(index): digunakan untuk mengambil obyek dalam posisi index.

2. list.set(index,obj): digunakan untuk menyimpan obyek di posisi index, jika posisi tersebut sebelumnya sudah terisi maka akan ditimpa.

3. list.add(index,obj): digunakan untuk menyisipkan obyek di posisi index.

4. list.remove(index): digunakan untuk menghapus obyek pada posisi index.

5. list.indexOf(obj): digunakan untuk mengetahui di mana posisi sebuah obyek dalam list.

Metode-metode di atas berlaku baik untuk ArrayList maupun LinkedList. Contoh operasi

berikut ini hanya berlaku khusus untuk LinkedList:

1. linkedlist.getFirst(): digunakan untuk mengambil obyek pertama dalam list.

2. linkedlist.getLast(): digunakan untuk mengambil obyek terakhir dalam list.

3. linkedlist.removeFirst(): digunakan untuk menghapus obyek pertama dalam list.

4. linkedlist.removeLast(): digunakan untuk menghapus obyek terakhir dalam list.

5. linkedlist.addFirst(obj): digunakan untuk menambah obyek di awal list.

6. linkedlist.addLast(obj): digunakan untuk menambah obyek di akhir list.

Berikut ini adalah contoh implementasi list untuk menambahkan data pada list,

tetapi diinginkan supaya list yang sudah ada tetap dalam kondisi terurut naik.

static void orderedInsert(List list, Comparable newItem)

{

// Precondition: The items in list are sorted into ascending

// order, according to the compareTo method.

// newitem.compareTo(item) must be defined for

// each item in the list.

// Postcondition: newItem has been added to the list in its

// correct position, so that the list is still

// sorted into ascending order.

ListIterator iter = list.listIterator();

// Move the iterator so that it points to the position where

// newItem should be inserted into the list. If newItem is

// bigger than all the items in the list, then the while loop

// will end when iter.hasNext() becomes false, that is, when

// the iterator has reached the end of the list.

while (iter.hasNext()) {

Object item = iter.next();

if (newItem.compareTo(item) <= 0) {

// newItem should come BEFORE item in the list.

// Move the iterator back one space so that

// it points to the correct insertion point,

// and end the loop.

iter.previous();

break;

}

iter.add(newItem);

}

1.1.3 deque

Diimplementasikan sebagai sederetan pointer yang menunjuk ke sejumlah array, elemen dapat secara efisien disisipkan ke dan dihapus dari bagian awal dan bagian akhir container deque.

Iterator-nya berjenis random-access. Member function yang dimiliki oleh vector juga dimiliki oleh deque, kecuali capacity() dan reserve(). Class deque memiliki dua buah member function yang tidak dimiliki oleh vector, yaitu push_front(x) dan pop_front().

1.1.4 stack

Container stack dibuat berdasarkan deque dan tidak memiliki iterator. Container ini hanya mengijinkan penyisipan dan penghapusan elemen pada bagian atas. Member function yang

dimiliki antara lain:

• empty() memberikan true jika dan hanya jika stack kosong.

• size() memberikan jumlah elemen.

• top() memberikan elemen palingatas.

• push(x) menyisipkan elemen x.

• pop() menghapus elemen.

1.1.5 queue

Container queue dibuat berdasarkan deque dan tidak memiliki iterator. Container ini hanya mengijinkan penyisipan elemen pada bagian belakang dan penghapusan elemen pada bagian depan. Selain empty(), size(), push(x), dan pop(), member function yang dimiliki antara lain:

• front() memberikan elemen paling depan.

• back() memberikan elemen paling belakang.

1.1.6 priority_queue

Container priority_queue dibuat berdasarkan vector dan tidak memiliki iterator. Container ini hanya mengijinkan penghapusan elemen berprioritas paling tinggi. Harus sudah didefinisikan operator < untuk tipe data elemen. Jika xmemberikan true, ini berarti bahwa prioritas elemen y lebih tinggi daripada elemen x. Member function yang dimiliki serupa dengan yang dimiliki oleh stack.

1.1.7 set

Diimplementasikan sebagai red-black tree, container ini menampung elemen secara terurut dan tanpa duplikat. Harus sudah didefinisikan operator < untuk tipe data elemen. Iterator-nya berjenis bidirectional. Selain empty(), size(), begin(), end(), erase(p), dan clear(), yang serupa dengan yang dimiliki oleh vector, member function yang dimiliki

antara lain:

• insert(x) menyisipkan elemen x

• erase(x) menghapus elemen x

• find(x) memberikan iterator yang menunjuk ke elemen x, atau memberikan end() jika elemen x tidak ada.

Seperti sudah diungkapkan di muka, bahwa set adalah sekumpulan obyek yang setiap obyek hanya pernah muncul sekali. Set menerapkan semua metode yang ada dalam collection, dengan satu tambahan ada langkah untuk memastikan bahwa tidak ada obyek yang kembar dalam set. Java mempunyai dua class yang menerapkan antarmuka set, yaitu java.util.TreeSet dan java.util.HashSet. TreeSet mempunyai sifat bahwa setiap elemen dalam set selalu diurutkan dalam urut naik. Contoh penerapan TreeSet dalam kasus pembacaan daftar kata dalam sebuah file, kemudian daftar kata tersebut diurutkan dan hanya dimunculkan sekali jika ada yang kembar. Algoritma untuk memecahkan masalah tersebut menggunakan TreeSet adalah:

TreeSet words = new TreeSet();

while there is more data in the input file:

Let word = the next word from the file.

words.add(word);

Iterator iter = words.iterator();

while (iter.hasNext()):

Write iter.next() to the output file.

Sedangkan kode program yang lebih lengkap adalah sebagai berikut:

import java.io.*;

import java.util.TreeSet;

import java.util.Iterator;

public class WordListWithTreeSet {

public static void main(String[] args) {

TreeSet words;

TextReader in;

PrintWriter out;

String inputFileName;

String outputFileName;

words = new TreeSet();

TextIO.put("Input file name? ");

inputFileName = TextIO.getln().trim();

try {

in = new TextReader(new FileReader(inputFileName));

}

catch (FileNotFoundException e) {

TextIO.putln("Can't find file \"" + inputFileName + "\".");

return;

}

TextIO.put("Output file name? ");

outputFileName = TextIO.getln().trim();

try {

out = new PrintWriter(new FileWriter(outputFileName));

}

catch (IOException e) {

TextIO.putln("Can't open file \"" + outputFileName + "\" for output.");

TextIO.putln(e.toString());

return;

}

try {

while (true) {

while ( ! in.eof() && ! Character.isLetter(in.peek()) )

in.getAnyChar();

if (in.eof())

break;

words.add(in.getAlpha()); // Add the word to the TreeSet.

// Has no effect if the word is

// already there!

}

catch (TextReader.Error e) {

TextIO.putln("An error occured while reading from the input file.");

TextIO.putln(e.toString());

return;

}

Iterator iter = words.iterator();

while (iter.hasNext())

out.println(iter.next());

if (out.checkError() == true) {

TextIO.putln("Some error occured while writing output.");

TextIO.putln("Output might be incomplete or invalid.");

}

else {

TextIO.putln( words.size() + " words from \"" + inputFileName +

"\" output to \"" + outputFileName + "\".");

}

1.1.8 map

Container map serupa dengan set, namun elemennya tidak tunggal melainkan pasangan indeks-nilai. Member function yang dimiliki serupa dengan yang dimiliki oleh set, dengan tambahan operator [key] yang memberikan nilai dengan indeks key, jika ada, dan menyisipkan elemen dengan indeks tersebut, jika belum ada.

Map merupakan sejenis array yang disamaratakan. Dikatakan sejenis atau mirip dengan array karena map juga didefinisikan menggunakan operasi get dan put. Bedanya, array menggunakan integer sebagai indeks untuk mengakses elemen array, sedangkan map bisa menggunakan sembarang obyek. Bahasa pemrograman lain ada yang menggunakan istilah associative array untuk menyebut map. Dalam Java, map didefinisikan dalam antarmuka java.util.Map. Berikut ini adalah metode-metode yang dalam map:

1. map.get(key): mengambil obyek yang dipetakan dengan obyek key.

2. map.put(key,value): memetakan obyek value dengan obyek key.

3. map.putAll(map2): menyalin semua pemetaan di map2 ke map.

4. map.remove(key): menghapus pemetaan obyek dengan key.

5. map.containsKey(key): mengetahui apakah ada obyek-obyek yang dipetakan ke key.

6. map.containsValue(value): mengetahui apakah ada value/obyek yang dipetakan ke beberapa key.

7. map.size(): mengetahui berapa jumlah pemetaan yang ada.

8. map.isEmpty(): mengetahui apakah tidak ada pemetaan dalam map.

9. map.clear(): menghapus semua pemetaan yang ada.

Berikut ini adalah contoh implementasi map dalam program buku telepon:

import java.util.HashMap;

public class PhoneDirectory

{

private HashMap info = new HashMap();

public void addEntry(String name, String number) {

info.put(name,number);

}

public String getNumber(String name)

{

return (String)info.get(name);

}

1.2 Iterator

Berperilaku seperti pointer, iterator digunakan untuk menelusuri dan memanipulasi elemen-elemen yang tersimpan dalam suatu container. Iterator diimplementasikan sebagai embedded class dalam container class yang bersangkutan. Operator yang dapat diterapkan ke semua jenis iterator antara lain:

• ++ membuat iterator menunjuk ke elemen selanjutnya.

• -– membuat iterator menunjuk ke elemen sebelumnya.

• == dan != untuk mengetahui apakah dua iterator menunjuk ke elemen yang sama.

• * memberikan akses ke elemen yang ditunjuk oleh iterator.

Sedangkan operator yang hanya dapat diterapkan ke iterator random-access antara lain [i] yang memberikan akses ke elemen berjarak i dari elemen yang ditunjuk oleh iterator.

1.3 Algorithm

Diimplementasikan sebagai template function, yaitu function yang memiliki parameter berupa tipe data, algorithm adalah algoritma yang dapat diterapkan ke rentang elemen tertentu dalam container yang ditunjukkan oleh pasangan iterator. Template function yang didefinisikan pada header antara lain:

• binary_search(p1, p2, x) memberikan true jika elemen x terdapat pada rentang p1 hingga p2-1. Rentang harus sudah terurut secara ascending.

• copy(p1, p2, p) menduplikasi elemen pada rentang p1 hingga p2-1 ke rentang berukuran sama yang dimulai dari p.

• count(p1, p2, x) memberikan cacah kemunculan elemen x pada rentang p1 hingga p2-1.

• equal(p1, p2, p) memberikan true jika rentang p1 hingga p2-1 serta rentang berukuran sama yang dimulai dari p memiliki elemen dengan nilai dan urutan yang sama.

• find(p1, p2, x) memberikan posisi kemunculan pertama elemen x pada rentang p1 hingga p2-1.

• merge(p1, p2, q1, q2, r) menggabungkan elemen pada rentang p1 hingga p2-1 dan rentang q1 hingga q2-1 ke rentang yang dimulai dari r.

• random_shuffle(p1, p2) mengacak susunan elemen pada rentang p1 hingga p2-1 (hanya untuk iterator random-access).

• remove(p1, p2, x) menggeser ke belakang semua elemen x pada rentang p1 hingga p2-1, lalu memberikan p di mana p1 hingga p-1 adalah rentang tanpa elemen x.

• reverse(p1, p2) memutar balik susunan elemen pada rentang p1 hingga p2-1.

• search(p1, p2, q1, q2) memberi posisi kemunculan pertama isi rentang q1 hingga q2-1 pada rentang p1 hingga p2-1.

• sort(p1, p2) mengurutkan elemen pada rentang p1 hingga p2-1 (hanya untuk iterator random-access).

2 STL UNTUK MENGAJARKAN

STRUKTUR DATA

Dalam penggunaan STL untuk mengajarkan Struktur Data, dianggap mahasiswa telah memiliki pengetahuan dasar mengenai C atau C++ dari matakuliah sebelumnya. Akan sangat membantu jika mahasiswa telah atau sedang menempuh matakuliah Pemrograman Berorientasi Objek atau ekuivalennya dalam C++. Namun jika tidak demikian, dalam beberapa kali pertemuan awal mahasiswa dapatdiperkenalkan kepada class, operator overloading, dan template; sedangkan konsep-konsep C++ lain seperti inheritance dan polymorphism maupun detaildetail seperti destructor, copy constructor, dan initialization section untuk sementara dapat dengan aman

diabaikan.

Mahasiswa dapat diperkenalkan kepada STL antara lain melalui kode. Sebagai contoh, kode-kode berikut menyisipkan sejumlah elemen ke dalam container, menggunakan iterator untuk melakukan penelusuran sambil mencetak nilai tiap elemen, dan kemudian menggunakan algorithm find untuk mencari suatu elemen dengan nilai tertentu. Kode berikut menggunakan vector:

#include

using namespace std;

void main() {

vector c;

vector::iterator i;

c.push_back(1);

c.push_back(3);

c.push_back(2);

for(i=c.begin(); i!=c.end();

i++)

cout << *i;

i = find(c.begin(), c.end(), 2);

if(i != c.end()) cout << "found";

else cout << "not found";

}

Sedangkan kode berikut menggunakanlist:

#include

using namespace std;

void main() {

list c;

list::iterator i;

c.push_front('C');

c.push_front('A');

c.push_front('B');

for(i=c.begin(); i!=c.end();

i++)

cout << *i;

i = find(c.begin(), c.end(),'B');

if(i != c.end()) cout <<"found";

else cout << "not found";

}

Dalam kode-kode di atas, vector dibuat menampung elemen bertipe int dan list dibuat menampung elemen bertipe char. Ini menunjukkan sifat umum container. Kode lain untuk kasus lain perlu juga diadakan, misalnya kasus container menampung pointer ke object merupakan kasus penggunaan STL yang sering terjadi (Eckel 1996).

Kode-kode di atas juga menggambarkan bahwa cara penggunaan iterator adalah seragam untuk container yang berbedabeda, dan bahwa algorithm dapat diterapkan pada berbagai macam container.

Dengan penggunaan STL, tidak berarti semua pendekatan dalam pengajaran tradisional dapat ditinggalkan. Yang perlu dipertahankan adalah antara lain pengantar ke analisis kompleksitas

(notasi big-O).

Pemilihan struktur data secara tepat kini mendapat perhatian khusus. STL menyediakan berbagai macam container dan mahasiswa perlu dianjurkan untuk memilih container yang paling efisien sesuai permasalahan. Sebagai contoh, biasanya vector merupakan container pilihan, namun jika akan sering dilakukan operasi penyisipan atau penghapusan pada posisi sembarang dalam struktur data, maka list lebih tepat dipilih karena operasi tersebut kompleksitasnya linear untuk vector namun konstan untuk list. Pemilihan struktur data ini dapat diperjelas dengan menunjukkan contoh-contoh permasalahan nyata.

Penggunaan struktur data secara tepat juga kini mendapat perhatian khusus. Meskipun algorithm memiliki sifat umum, yaitu dapat diterapkan pada berbagai macam container, namun mahasiswa perlu dianjurkan untuk memilih kombinasi yang efisien dan menghindari kombinasi yang tidak efisien. Sebagai contoh, dalam memilih algorithm pencarian, perlu dilihat apakah iterator menunjuk ke rentang terurut. Jika ya, sebaiknya dipilih algorithm yang kompleksitasnya logaritmik seperti binary_search. Jika tidak, terpaksa dipilih algorithm yang kompleksitasnya linear seperti find.

Sebelum menerapkan suatu algorithm pada suatu container, perlu dipastikan bahwa tidak ada member function dalam container yang dapat mengerjakan tugas tersebut secara lebih efisien. Sebagai contoh, set dan map selalu terurut dan memiliki member function find yang kompleksitasnya logaritmik, sehingga tentunya algorithm find sama sekali tidak tepat diterapkan pada mereka. Dengan penggunaan STL, perluasan juga dapat lebih mudah dilakukan ke struktur data yang lebih kompleks, seperti misalnya general tree. General tree, bentuk umum dari tree, merupakan struktur data yang sering digunakan, misalnya dalam aplikasi-aplikasi kecerdasan buatan. Gambar 1 memberikan suatu contoh general tree. Setiap node di dalam general tree dapat memiliki child dalam jumlah tak terbatas, berbeda dengan node di dalam binary tree yang hanya dapat memiliki paling banyak dua child; akibatnya implementasi untuk general tree lebih kompleks daripada untuk binary tree.

Gambar 1. Contoh general tree

Salah satu cara untuk membuat implementasi general tree adalah dengan menempatkan suatu linked list di setiap node untuk menampung sejumlah pointer yang masing-masing menunjuk ke tiap child dari node tersebut. Ini dapat dengan mudah dilakukan dengan menggunakan list seperti ditunjukkan oleh kode pada Gambar 2. Dalam program tersebut, nilai dari nodenode dimasukkan secara level order dan setelah itu dilakukan penelusuran secara inorder dan postorder sambil mencetak nilai dari setiap node. Demi kesederhanaan, implementasi ini memang terbatas fasilitasnya. Namun tidak sulit untuk melengkapinya dan menjadikannya sebagai komponen buatan sendiri yang kompatibel dengan komponen STL lain.

Berikut contoh dialog program yang berkaitan dengan general tree pada Gambar 1:

Enter root: A

Enter children of A: BC

Enter children of B: DEF

Enter children of C: G

Enter children of D:

Enter children of E:

Enter children of F:

Enter children of G:

Preorder: ABDEFCG

Postorder: DEFBGCA

3 KESIMPULAN

#include

using namespace std;

class N { // node

public:

char data;

list *link;

N(char d, list *l) { data = d; link = l; }};

void createSubs(list *l) {

for(list::iterator i = l->begin(); i != l->end(); i++) {

cout << "Enter children of " <<>data << ": ";

char c;

cin.get(c);

while(c != '\n') {

if(!i->link) i->link = new list;

i->link->push_back(N(c, 0));

cin.get(c);

}

for(i = l->begin(); i != l->end(); i++)

if(i->link) createSubs(i->link);

}

void traverse(list *l, int order) {

for(list::iterator i = l->begin(); i != l->end(); i++) {

if(order == 0) cout <<>data; // preorder

if(i->link) traverse(i->link, order);

if(order == 1) cout <<>data; // postorder

}

void main() {

cout << "Enter root: ";

char c;

cin.get(c); cin.ignore();

list *root = new list;

root->push_back(N(c, 0));

createSubs(root);

cout << "Preorder: "; traverse(root, 0); cout <<>

cout << "Postorder: "; traverse(root, 1); cout <<>

}

Gambar 2. Kode untuk general tree

Diusulkan penggunaan STL oleh staf pengajar yang selama ini masih mengajarkan matakuliah Struktur Data dengan fokus tradisional, yaitu pada detail implementasi struktur data sederhana. Dengan penggunaan STL, fokus matakuliah dapat digeser ke jenjang yang lebih tinggi, yaitu kepada pemilihan dan penggunaan struktur data sederhana tersebut secara tepat. Dengan penggunaan STL, perluasan juga dapat dilakukan ke struktur data yang lebih kompleks dan lebih dekat ke masalah nyata. Sebagai ilustrasi, ditunjukkan bahwa implementasi general tree, yang tingkat kesulitannya membuatnya kerap dihindari dalam pengajaran Struktur Data tradisional, dapat dengan mudah dilakukan dengan bantuan STL.

3. Struktur Data

Pada pemrograman prosedural, setiap data mempunyai jenis. Jenis data menentukan bagaimana mengartikan nilai dari suatu data serta operasi apa yang dapat dilakukan terhadap data tersebut. Secara umum jenis data dapat digolongkan menjadi 4 golongan, yaitu :

1. jenis dasar, adalah jenis data yang dianggap sudah terdefinisi misalnya integer, real, boolean, character; suatu data yang memiliki jenis ini setiap saat hanya dapat memiliki satu nilai

2. jenis bentukan, adalah jenis data yang merupakan komposisi dari jenis dasar; suatu data yang memiliki jenis ini setiap saat hanya dapat memiliki satu nilai yang sesuai dengan susunan dari jenis dasar yang didefinisikannya

3. tabel, adalah jenis data yang terdiri atas sekumpulan unsure berjenis sama yang tersusun secara kontinu dan setiap unsure dapat diperoleh melalui indeks tabel; suatu data yang memiliki jenis ini setiap saat dapatmemiliki banyak nilai sesuai dengan ukuran tabel

4. pointer, adalah jenis data yang menyimpan alamat komputer dari suatu data

Data yang ada di dunia nyata seringkali amat kompleks, sehingga membutuhkan suatu abstraksi dari representasi data tersebut, agar memudahkan dalam merancang struktur datanya. Dikenal 3 tingkatan abstraksi yaitu:

1. definisi fungsional,

2. representasi lojik,

3. representasi fisik

Pada definisi fungsional, dilakukan pendefinisian suatu struktur data dan operator-operator yang berlaku pada struktur tersebut.

Untuk melakukannya tidak digunakan notasi khusus melainkan mendefinisikan dengan kata-kata. Representasi lojik adalah rincian jenis dari struktur data, menyangkut nama jenis dan jenis-jenis operator. Untuk membuat representasi lojik digunakan notasi algoritmik. Representasi ini tak bergantung pada memory komputer. Pada representasi lojik belum digunakan jenis data yang sudah dikenal di atas. Relasi antara definisi fungsional dan representasi lojik adalah satu-ke-satu, artinya setiap definisi fungsional hanya mempunyai satu representasi lojik. Representasi fisik adalah spesifikasi dari struktur data sesuai dengan implementasinya pada memory komputer. Digunakan notasi algoritmik dan type-type dasar yang sudah dikenal. Pada dasarnya hanya ada dua macam representasi fisik yaitu: kontigu dan berkait. Untuk satu representasi lojik bisa dikembangkan menjadi banyak kemungkinan representasi fisik.

4. PENGERTIAN STRUKTUR DATA

Suatu bilangan bulat terdiri dari dua bagian yaitu tanda (-/+) untuk menyatakan apakah bilangan

tersebut negatif/positif yang diikuti dengan deretan angka (0,1,2,…,9). Representasi bilangan bulat secara lengkap dapat dituliskan sebagai berikut :

s an-1an-2…a1a0, di mana s ∈{-,+}, ai ∈{0,1,…,9}

Panjang maksimum dari bilangan bulat yang dapat diproses adalah 100 (antara – 10100 dan 10100).

Namun jika diperlukan, maka panjang maksimum dapat diubah sesuai dengan kebutuhan. Untuk kemudahan bilangan bulat disimpan sebagai sebuah string, sedangkan tanda dari bilangan tersebut disimpan terpisah. Di bawah ini disajikan implemen - tasi struktur data tersebut dalam bahasa C.

#define NMAX 100typedef struct

{char sign,isi[NMAX];} bulat;

5. Definisi Algoritma

Ditinjau dari asal usul katanya kata Algoritma sendiri mempunyai sejarah yang aneh. Orang hanya menemukan kata Algorism yang berarti proses menghitung dengan angka arab. Anda

dikatakan Algorist jika anda menghitung menggunakan Angka Arab. Para ahli bahasa berusaha menemukan asal kata ini namun hasilnya kurang memuaskan. Akhirnya para ahli sejarah matematika menemukan asal kata tersebut yang berasal dari nama seorang ahli matematika dari Uzbekistan Abu Abdullah Muhammad Ibnu Musa Al-Khuwarizmi (770-840). Al-Khuwarizmi dibaca orang barat menjadi Algorism. Al-Khuwarizmi menulis buku yang berjudul Kitab Al Jabar Wal- Muqabala yang artinya “Buku pemugaran dan pengurangan” (The book of restoration and reduction). Dari judul buku itu kita juga memperoleh akar kata “Aljabar” (Algebra). Perubahan kata dari Algorism menjadi Algorithm muncul karena kata Algorism sering dikelirukan dengan Arithmetic, sehingga akhiran –sm berubah menjadi –thm. Karena perhitungan dengan angka Arab sudah menjadi hal yang biasa. Maka lambat laun kata Algorithm berangsur-angsur dipakai sebagai metode perhitungan (komputasi) secara umum, sehingga kehilangan makna kata aslinya. Dalam Bahasa Indonesia, kata Algorithm diserap menjadi Algoritma. Kita bisa mendefinisikan algoritma sebagai berikut:

Algoritma adalah logika, metode dan tahapan (urutan) sistematis yang digunakan untuk memecahkan suatu permasalahan. Kamus besar bahasa Indonesia (Balai Pustaka 1988) secara formal mendefinisikanalgoritma sebagai: Algoritma adalah urutan logis pengambilan putusan untuk pemecahan masalah.

6. Hubungan Algoritma dan Struktur Data

Program adalah kumpulan instruksi komputer, sedangkan metode dan tahapan sistematis dalam program adalah algoritma. Program ini ditulis dengan menggunakan bahasa pemrograman. Jadi bisa kita sebut bahwa program adalah suatu implementasi bahasa pemrograman. Beberapa pakar memberi formula bahwa:

program = struktur data + algoritma

Bagaimanapun juga struktur data dan algoritma berhubungan sangat erat pada sebuah

program. Algoritma yang baik tanpa pemilihan struktur data yang tepat akan membuat

program menjadi kurang baik, demikian juga sebaliknya.

Menilai Sebuah Algoritma

Ketika manusia berusaha memecahkan masalah, metode atau teknik yang digunakan untuk memecahkan masalah kemungkinan bisa lebih dari satu. Dan kita memilih mana yang terbaik diantara teknik-teknik itu. Hal ini sama juga dengan algoritma, yang memungkinkan suatu permasalahan dipecahkan dengan metode dan logika yang berlainan. Lalu bagaimana mengukur mana algoritma yang terbaik ?

Beberapa persyaratan untuk menjadi algoritma yang baik adalah:

• Tingkat kepercayaannya tinggi (realibility). Hasil yang diperoleh dari proses harus berakurasi tinggi dan benar.

• Pemrosesan yang efisien (low cost). Proses harus diselesaikan secepat mungkin dan jumlah kalkulasi yang sependek mungkin.

• Bersifat general. Bukan sesuatu yang hanya untuk menyelesaikan satu kasus saja, tapi juga untuk kasus lain yang lebih general.

• Bisa dikembangkan (expandable). Haruslah sesuatu yang dapat kita kembangkan lebih jauh berdasarkan perubahan requirement yang ada.

• Mudah dimengerti. Siapapun yang melihat, dia akan bisa memahami algoritma anda. Sulit dimengertinya suatu program akan membuat sulit pengelolaan.

• Portabilitas yang tinggi (portability). Bisa dengan mudah diimplementasikan di berbagai platform komputer.

Contoh Algoritma dan Implementasinya

Sebagai contoh sederhana, mari kita berlatih melihat permasalahan, mencoba menyusun

algoritma, dan menerapkan dalam bahasa C.

Permasalahan

Ada seorang guru SD yang ingin membuat rangking nilai ujian 9 orang murid. Nilai ujian

murid adalah sebagai berikut:

56 78 43 96 67 83 51 74 32

Bagaimana algoritma dalam pembuatan rangking nilai tersebut?

Untuk memecahkan masalah di atas, kita bisa menyusun algoritma sebagai berikut:

1. Buat satu variable (misalnya rangking)

2. Set variable rangking = 1

3. Ambil satu nilai sebagai data yang ke a, misalnya 56

4. Cek nilai dari paling depan (56) sampai paling belakang (32) (b=0-8). Apabila

nilai tersebut lebih tinggi daripada nilai ke a (56), maka set variable rangking = ranking + 1.

5. Ulangi proses nomor 2 dengan mengambil data ke (a) berikutnya. Kemudian mari kita implementasikan algoritma di atas dalam program bahasa C.

Program: Rangking Nilai Ujian

#include

#define banyaknya_nilai 9

main(){

static int nilai[]={56, 78, 43, 96, 67, 83, 51, 74, 32};

int rangking[banyaknya_nilai];

int a,b;

for (a=0;a

rangking[a]=1;

for (b=0;b

if (nilai[a]>nilai[b])

rangking[a]++;

}

printf("Nilai Ujian \t Rangking\n");

for (a=0;a

printf("%d \t\t %d\n",nilai[a], rangking[a]);

}

Hasil

Nilai Ujian Rangking

56 4

78 7

43 2

96 9

67 5

83 8

51 3

74 6

32 1

Algoritma Tidak Tergantung Bahasa Pemrograman Dan Mesin Komputer

Notasi Algoritma dapat diterjemahkan ke dalam berbagai bahasa pemrograman. Analoginya sama dengan resep membuat kue. Sebuah resep dapat ditulis dalam bahasa apapun. Bahasa Jepang, Inggris, Perancis, Indonesia, dan lain sebagainya. Apapun bahasanya, kue yang dihasilkan tetap sama asalkan semua aturan pada resep diikuti. Mengapa demikian? Karena setiap juru masak (sebagai pemroses) dapat melakukan operasi dasar yang sama, seperti mengocok telur, menimbang berat gula, dan lain sebagainya. Demikian juga halnya dengan komputer. Meskipun setiap komputer berbeda teknologinya, tetapi secara umum semua komputer dapat melakukan operasi-operasi dasar dalam pemrograman seperti operasi pembacaan data, operasi perbandingan, operasi aritmatika, dan sebagainya. Perkembangan teknologi komputer tidak mengubah operasi-operasi dasar itu, yang berubah hanyalah kecepatan, biaya, atau tingkat ketelitian. Pada sisi lain setiap program dalam bahasa tingkat tinggi selalu diterjemahkan kedalam bahasa mesin sebelum akhirnya dikerjakan oleh CPU. Setiap instruksi dalam bahasa mesin menyajikan operasi dasar yang sesuai, dan menghasilkan efek yang sama pada setiap komputer.

IV. Algoritma

7. ALGORITMA

Suatu operasi aritmetika terdiri atas dua operand dan satu operator. Hasil operasi ini sangat dipengaruhi oleh tanda dari masing-masing operand. Pada dasarnya hanya ada dua operasi dasar yaitu penjumlahan dan pengurangan, dengan asumsi kedua operand memiliki tanda yang sama.

Berikut ini akan disajikan modulmodul dalam bahasa C untuk kedua operasi yang sudah disebutkan diatas.

void sub(bulat a, bulat b, bulat *c) /*a.sign==b.sign*/

{ char i,j,k=0,x,*p;

i = strlen(a.isi)-1; /*mencari posisi digit terakhir*/

j = strlen(b.isi)-1; /*di a dan b*/

c->isi[0] = 0; /*inisialisasi c*/

if ((x=lessthan(a,b))==1) /* |a| < |b| */

{ sub(b,a,c); minus(*c,c);}

else

{ do /* kurangkan digit demi digit */

{ c->isi[k] += (a.isi[i]-b.isi[j]+'0');

if (c->isi[k] < '0')

{ c->isi[k] += 10;

c->isi[++k] = -1;}

else c->isi[++k] = 0;

i--; j--;

}while (i>-1 && j>-1);

if (i>-1) /* a lebih panjang dari b */

{ do

{ c->isi[k] += (a.isi[i--]);

if (c->isi[k] < '0')

{ c->isi[k] += 10;

c->isi[++k] = -1;}

else c->isi[++k] = 0;

}while (i>-1);

c->sign = a.sign;

strrev(c->isi);

while (c->isi[0]=='0')

{ strcpy(c->isi,c->isi+1);}

}else /* a sama panjang dengan b */

{ strrev(c->isi);

while (c->isi[0] == '0')

{ strcpy(c->isi,c->isi+1);}

if (!c->isi[0]) strcpy(c->isi,"0");

}

c->sign = a.sign;

}

Yang dilakukan pada kedua operasi dasar tersebut adalah menjumlahkan/ mengurang-kan satu demi satu setiap digit yang bersesuaian pada kedua operand. Jika hasil penjumlahan dua digit lebih dari 9 (overflow), maka digit berikutnya akan ditambah 1. Sebaliknya jika hasil pengurangan dua digit kurang dari 0 (underflow), maka digit berikutnya akan dikurangi 1. Pada modul pengurangan terdapat dua modul tambahan yaitu void minus(bulat a, bulat *b) yang berfungsi untuk mengubah a menjadi –a dan char lessthan(bulat a, bulat b) yang berfungsi untuk memeriksa apakah a <>

void minus(bulat a, bulat *b)

{ strcpy(b->isi,a.isi);

b->sign = (a.sign == '-')?'+':'-';

}

char lessthan(bulat a, bulat b)

{ char i;

if (strlen(a.isi) <>

return(1); /* |a| < |b| */

else if (strlen(a.isi) > strlen(b.isi))

return(-1); /* |a| > |b| */

else /* a dan b sama panjangnya */

{ for (i=0; i <>

i++);

if (a.isi[i] <>

return(1);

else if (a.isi[i] > b.isi[i])

return(-1);

else return(0);

}

Pada operasi penjumlahan dua bilangan, sebut saja a dan b, akan diperiksa tanda kedua operand. Jika tidak sama maka yang dilakukan adalah pengurangan a dan –b. Demikian juga pada operasi pengurangan

a dan b. Jika tidak sama tandanya, maka yang dilakukan adalah penjumlahan a dan –b. Berikut ini adalah implementasi operasi penjumlahan dan pengurangan.:

void addprocess(bulat a, bulat b)

{ bulat c, temp;

printf("Hasil Penjumlahan : %c%s + %c%s

=",a.sign,a.isi,b.sign,b.isi);

if (a.sign == b.sign)

{ add(a,b,&c);

printf("%c%s\n",c.sign,c.isi);}

else if (a.sign == '-')

{ minus(a,&temp);

sub(b,temp,&c);

printf("%c%s\n",c.sign,c.isi);}

else

{ minus(b,&temp);

sub(a,temp,&c);

printf("%c%s\n",c.sign,c.isi);}

}

void subprocess(bulat a, bulat b)

{ bulat c, temp;

printf("Hasil Pengurangan : %c%s - %c%s

=",a.sign,a.isi,b.sign,b.isi);

if (a.sign != b.sign)

{ minus(b,&temp);

add(a,temp,&c);

printf("%c%s\n",c.sign,c.isi);}

else

{ sub(a,b,&c);

printf("%c%s\n",c.sign,c.isi);}

}

void addprocess(bulat a, bulat b)

{ bulat c, temp;

printf("Hasil Penjumlahan : %c%s + %c%s

=",a.sign,a.isi,b.sign,b.isi);

if (a.sign == b.sign)

{ add(a,b,&c);

printf("%c%s\n",c.sign,c.isi);}

else if (a.sign == '-')

{ minus(a,&temp);

sub(b,temp,&c);

printf("%c%s\n",c.sign,c.isi);}

else

{ minus(b,&temp);

sub(a,temp,&c);

printf("%c%s\n",c.sign,c.isi);}

}

void subprocess(bulat a, bulat b)

{ bulat c, temp;

printf("Hasil Pengurangan : %c%s - %c%s

=",a.sign,a.isi,b.sign,b.isi);

if (a.sign != b.sign)

{ minus(b,&temp);

add(a,temp,&c);

printf("%c%s\n",c.sign,c.isi);}

else

{ sub(a,b,&c);

printf("%c%s\n",c.sign,c.isi);}

}

Operasi perkalian a dan b sebenarnya adalah operasi penjumlahan bilangan b sebanyak a kali. Untuk mempercepat, terlebih dulu harus diperiksa apakah a < b. Jika tidak, maka operasinya harus diubah menjadi menjumlahkan a sebanyak b kali. Operasi pembagian a dan b sebenarnya adalah operasi pengurangan a dengan b sampai a < b. Berapa kali kita melakukan pengurangan menjadi hasil pembagian tersebut. Operasi modulo a dan b bias diimplementasikan menjadi a – tb, di mana t adalah hasil pembagian a dan b.

void mul(bulat a, bulat b, bulat *c)

{ bulat temp;

if (zero(a) || zero(b))

{ c->sign = '+'; strcpy(c->isi,"0");}

else if (lessthan(b,a)==1)

mul(b,a,c);

else

{ c->sign = '+'; strcpy(c->isi,"0");

temp.sign = a.sign; strcpy(temp.isi,a.isi);

{ dec(&temp); add(b,*c,c);

}while (!zero(temp));

}

c->sign = (a.sign==b.sign)?'+':'-';

}

void div(bulat a, bulat b, bulat *c)

{ bulat ta;

ta.sign = a.sign; strcpy(ta.isi,a.isi);

c->sign = '+'; strcpy(c->isi,"0");

while (lessthan(ta,b)!=1)

{ sub(ta,b,&ta); inc(c);

}

c->sign = (a.sign == b.sign)?'+':'-';

}

void mod(bulat a, bulat b, bulat *c)

{ bulat t1,t2;

div(a,b,&t1);

mul(b,t1,&t2);

sub(a,t2,c);

}

Selain modul-modul di atas, ada tiga modul tambahan yaitu int zero(bulat a) untuk memeriksa apakah a = 0, void dec(bulat *a) untuk mengurangi a dengan 1, dan void inc(bulat *a) untuk menambah a dengan 1.

int zero(bulat a)

{ return(!strcmp(a.isi,"0"));

}

void dec(bulat *a) /* !zero(a) */

{ char i = strlen(a->isi)-1;

if (a->isi[i] > '0')

a->isi[i]--;

else

{ do

{ a->isi[i--] = '9';

}while (a->isi[i] == '0');

a->isi[i]--;

}

8. POINTER

8.1 Konsep Dasar Pointer

Pointer (variabel penunjuk) adalah suatu variabel yang berisi alamat lokasi suatu memori tertentu. Jadi isi dari variabel pointer merupakan alamat dari lokasi memori yang digunakan untuk menyimpan data dan bukan nilai data itu sendiri. Misalnya X adalah suatu variabel biasa yang berisi nilai karakter ‘J’. X bukan variabel pointer. Nilai dari X ini oleh kompiler C++ akan diletakkan di suatu lokasi memori tertentu. Nilai ini dapat diakses jika diketahui alamat memorinya. Untuk mengetahui alamat memori yang digunakan oleh variabel X dalam menyimpan nilai datanya dapat diketahui dengan ungkapan &X. Alamat tersebut dapat ditulis dengan mengambil sebuah variabel lagi yang disebut dengan variabel pointer, misalnya: Alamat_X = &X. Alamat_X adalah variabel pointer karena variabel ini menunjuk ke lokasi memori di mana nilai data dari variabel X disimpan.

Contoh pada sebuah baris program berikut:

char *Alamat_X, X;

X = ‘J’;

Alamat_X = &X;

Dari baris program di atas, dapat ditemukan bahwa:

Nilai X = ‘J’

Nilai Alamat_X = 2527:24C7

Dengan ilustrasi sebagai berikut:

Ini berarti variabel X menyimpan nilai datanya yaitu ‘J’ pada alamat lokasi memori 2527:24C7. Alamat_X adalah variabel pointer yang menunjuk pada alamat lokasi memori yang digunakan oleh variabel X. Sebelum digunakan, variabel pointer harus dideklarasikan terlebih dahulu dengan diawali suatu asterisk (“*”).

Bahasa C/C++ menyediakan dua buah operator pointer, yaitu operator ‘&’ dan operator ‘*’. Operator ‘&’ digunakan untuk mendapatkan alamat lokasi memori yang digunakan oleh sebuah variabel biasa (dalam contoh di atas, &X digunakan untuk mendapatkan alamat memori yang digunakan oleh variabel X). Sedangkan operator ‘*’ digunakan untuk mendapatkan nilai data yang ditunjuk oleh variabel pointer pada alamat memori tersebut.

Contoh 1:

#include

void main()

{

char *Alamat_X, X, Y, Z;

X = 'J';

Alamat_X = &X;

Y = X;

Z = *Alamat_X;

cout<<"Nilai variabel X adalah "<

cout<<"Nilai variabel Y adalah "<

cout<<"Nilai variabel Z adalah "<

cout<<"Nilai variabel X berada di alamat memori ";printf("%p",Alamat_X);

}

Jika program ini dijalankan, akan didapatkan hasil:

Pada contoh-contoh di atas, kita mengalokasikan alamat lokasi memori yang digunakan oleh sebuah variabel pointer dengan menggunakan variabel bantu (dalam hal ini adalah variabel X). Jika kita ingin menciptakan sebuah variabel pointer tanpa menggunakan bantuan variabel biasa, kita harus terlebih dahulu mengalokasikan alamat lokasi memori variabel pointer yang akan digunakan. Kompiler C++ tidak dapat mengalokasikan secara otomatis alamat lokasi memori sebuah variabel pointer pada saat pertama kali variabel tersebut dideklarasikan. Untuk mengatasi hal ini, kita dapat menggunakan alokasi dinamis yang dapat dilakukan dengan pemanggilan fungsi standar malloc() dengan prototipenya berada pada file malloc.h. Cara alokasi dinamis ini akan menggunakan memori yang masih kosong. Fungsi malloc() akan mengalokasikan secara dinamis blok memori yang masih kosong untuk digunakan oleh variabel pointer.

Format pemanggilan fungsi malloc() adalah:

tipe_data *[var_pointer];

var_pointer = ([tipe_data *]) malloc(sizeof([tipe_data]));

Kemudian untuk menghapus nilai alamat lokasi memori yang disimpan oleh variabel pointer digunakanlah fungsi free().

Format pemanggilan fungsi malloc() adalah:

free([variabel_pointer]);

Contoh 2:

#include

void main()

{

char *X;

X = (char *) malloc(sizeof(char));

if (X == NULL)

{

cout<<"Memori Tidak Cukup!!!";

}

else

{

*X = 'J';

cout<<"Nilai variabel X = "<<*X<

cout<<"Nilai variabel X berada pada alamat = "; printf("%p",X);

}

Jika program ini dijalankan, akan didapatkan hasil:

Seperti pada contoh di atas, kita telah menciptakan sebuah variabel pointer dengan alokasi memori secara dinamis tanpa variabel bantu dengan menggunakan fungsi malloc(). Fungsi ini akan mengalokasikan alamat memori yang digunakan oleh variabel pointer X secara dinamis pada alamat 2D37:00FA.

8.2 Operasi Aritmatika Pada Pointer

Operasi aritmatika yang umum dilakukan pada suatu variabel pointer hanya berupa operasi pertambahan dan pengurangan. Suatu variabel pointer hanya dapat ditambah atau dikurangi dengan suatu nilai integer.

Operasi pertambahan pointer dengan suatu nilai integer merupakan suatu peningkatan nilai pointer yang menunjukkan alamat lokasi memori yang menyimpan nilai data berikutnya. Alamat lokasi memori dinyatakan dalam bilangan heksadesimal.

Misalnya sebuah variabel pointer X menunjuk pada alamat memori 182F:00FA, maka operasi pertambahan X+1 menunjuk pada alamat:

182F:00FA + sizeof(tipe_data_x)

Fungsi sizeof() berfungsi untuk mengembalikan nilai ukuran (dalam byte) terhadap tipe data yang digunakan oleh variabel pointer tersebut.

Jika X merupakan variabel pointer bertipe integer (dimana sizeof(int) = 2 byte), maka operasi X+1 akan menunjukkan alamat:

182F:00FA

----------------- +

182F:00FC

Jika X merupakan variabel pointer bertipe float (dimana sizeof(float) = 4 byte), maka operasi X+1 akan menunjukkan alamat:

182F:00FA

----------------- +

182F:00FE

Misalnya, X dideklarasikan sebagai variabel pointer bertipe int, maka hubungan operasi X+1, X+2, X+3 dan seterusnya dengan alamat lokasi memori dapat dilihat pada ilustrasi berikut ini:

Contoh 3:

#include

void main()

{

int *X;

X = (int *) malloc(sizeof(int));

if (X == NULL)

{

cout<<"Memori Tidak Cukup!!!";

}

else

{

cout<<"Variabel X+0 menunjuk pada alamat = ";

printf("%p",X);cout<

cout<<"Variabel X+1 menunjuk pada alamat = ";

printf("%p",X+1);cout<

cout<<"Variabel X+2 menunjuk pada alamat = ";

printf("%p",X+2);cout<

cout<<"Variabel X+3 menunjuk pada alamat = ";

printf("%p",X+3);cout<

cout<<"Variabel X+4 menunjuk pada alamat = ";

printf("%p",X+4);cout<

}

Jika program di atas dijalankan, didapatkan hasil:

8.3 Pointer Sebagai Suatu Larik

Pointer dan larik (array) mempunyai hubungan yang erat. Suatu nama larik yang ditulis tanpa indeks menunjukkan alamat elemen pertama dari larik. Hubungan lain antara larik dengan pointer adalah dalam hal pengaksesan nilai-nilai elemen lariknya. Pada contoh 4 di bawah ini juga dapat dilihat bahwa nilai elemen-elemen larik dapat diakses dengan menggunakan pointer, demikian sebaliknya.

Misalnya suatu larik berdimensi satu dengan nama X dan variabel pointer dengan nama P. Alamat elemen-elemen larik dimensi satu ini mulai elemen pertama sampai ke-n dapat ditunjukkan sebagai berikut:

Elemen ke-1 : &X[0] atau X atau (X+0) atau P atau (P+0)

Elemen ke-2 : &X[1] atau (X+1) atau (P+1)

Elemen ke-3 : &X[2] atau (X+2) atau (P+2)

Elemen ke-n : &X[n-1] atau (X+n-1) atau (P+n-1)

Sedangkan nilai-nilai dari elemen larik dimensi satu ini dapat diakses sebagai berikut:

Elemen ke-1 : X[0] atau *X atau *(X+0) atau *P atau *(P+0)

Elemen ke-2 : X[1] atau *(X+1) atau *(P+1)

Elemen ke-3 : X[2] atau *(X+2) atau *(P+2)

Elemen ke-n : X[n-1] atau *(X+n-1) atau *(P+n-1)

Contoh 4:

#include

void main()

{

char *P, X[7]={'A','B','C','D'};

int i;

P = X;

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

{

cout<<"Nilai variabel (P+"<

"' berada pada alamat = ";printf("%p",(P+i));

cout<

}

cout<

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

{

cout<<"Nilai variabel X["<

"' berada pada alamat = ";printf("%p",&X[i]);

cout<

}

Jika program diatas dijalankan maka didapatkan hasil:

8.4 Pointer dan Tipe Data String

String adalah sekumpulan karakter-karakter yang membentuk suatu larik atau array. Suatu string dapat diakses elemen-elemen karakternya baik sebagai pointer ataupun sebagai larik.

Berikut ini adalah contoh ilustrasi string sebagai pointer dan larik:

char *P;

P = “FASILKOM”;

Dari gambar di atas dapat dilihat bahwa tiap-tiap karakter padastringmenempati satu lokasi alamat memori. Oleh karena itu, tiap-tiap elemen karakter di dalam string dapat diakses dengan menggunakan pointer atau larik:

Pointer:

*P ‘F'

*(P+1) ‘A’

*(P+2) ‘S’

*(P+3) ‘I’

*(P+4) ‘L’

*(P+5) ‘K’

*(P+6) ‘O’

*(P+7) ‘M’

Larik:

P[0] ‘F'

P[1] ‘A’

P[2] ‘S’

P[3] ‘I’

P[4] ‘L’

P[5] ‘K’

P[6] ‘O’

P[7] ‘M’

Satu karakter menempati 1 byte (1 lokasi alamat) pada memori. Oleh karena itu string “FASILKOM” yang terdiri dari 8 karakter akan menempati 8 lokasi alamat pada memori dan membutuhkan memori sebesar 8 byte.

Contoh 5:

#include

void main()

{

char *P;

int i;

P = "FASILKOM";

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

{

cout<<"Nilai variabel (P+"<

"' berada pada alamat = ";printf("%p",(P+i));

cout<

}

cout<

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

{

cout<<"Nilai variabel P["<

"' berada pada alamat = ";printf("%p", &P[i]);

cout<

}

Jika program di atas dijalankan, maka didapatkan hasil:

Nilai variabel (P+0) = 'F' berada pada alamat = 232F:0076

Nilai variabel (P+1) = 'F' berada pada alamat = 232F:0077

Nilai variabel (P+2) = 'F' berada pada alamat = 232F:0078

Nilai variabel (P+3) = 'F' berada pada alamat = 232F:0079

Nilai variabel (P+4) = 'F' berada pada alamat = 232F:007A

Nilai variabel (P+5) = 'F' berada pada alamat = 232F:007B

Nilai variabel (P+6) = 'F' berada pada alamat = 232F:007C

Nilai variabel (P+7) = 'F' berada pada alamat = 232F:007D