-==ALL ABOUT TEORI STRUKTUR DATA==-

Searching Array

Pada semester yang lalu kita sudah mempelajari array, baik array 1 dimensi maupun array 2 dimensi. Pada bab ini, kita akan mempelajari beberapa cara untuk melakukan pencarian suatu nilai dalam sebuah array 1 dimensi (pada array 2 dimensi sama saja).

Teknik pencarian data dari array yang paling mudah adalah dengan cara sequential search, dimana data dalam array dibaca 1 demi satu, diurutkan dari index terkecil ke index terbesar, maupun sebaliknya.

Contoh :

Array :

int a[5] = {0,3,6,10,1} (index array pada bahasa c dimulai dari index ke 0 !!!)

jika kita ingin mencari bilangan 6 dalam array tersebut, maka proses yang terjadi kita mencari

1. dari array index ke-0, yaitu 0, dicocokan dengan bilangan yang akan dicari, jika tidak sama, maka mencari ke index berikutnya
2. pada array index ke-1, juga bukan bilangan yang dicari, maka kita mencari lagi pada index berikutnya
3. pada array index ke-2, ternyata bilangan yang kita cari ada ditemukan, maka kita keluar dari looping pencarian

contoh source :

output :

Metode pencarian yang kedua adalah binary search, pada metode pencarian ini, data harus diurutkan terlebih dahulu. Pada metode pencarian ini, data dibagi menjadi dua bagian (secara logika), untuk setiap tahap pencarian.

Algoritma binary search :

1. Data diambil dari posisi 1 sampai posisi akhir N

2. Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2

3. Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?

4. Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1

5. Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1

6. Jika data sama, berarti ketemu.

Contoh source binary search :

Output :

Interpolation search merupakan salah satu metode pencarian yang dapat digunakan. Seperti pada binary search, data yang harus diurutkan terlebih dahulu, sebelum dapat dilakukan pencarian dengan metode ini. Pada metode pencarian ini, kita mencoba menebak letak data yang kita cari, dengan perhitungan

• Jika data[posisi] > data yg dicari, high = pos – 1

• Jika data[posisi] < low =" pos">

Contoh source code interpolation search :

Output :

Tambahan materi :

break ;

digunakan untuk keluar dari suatu blok perintah

continue;

digunakan untuk mem by-pass satu iterasi pada perulangan

contoh kode : (dijalankan dan dipelajari cara kerjanya)

#include

void main(){

for(int i=0;i<10;i++){

for(int j=10;j>0;j--){

if(i+j==10) break;

//if(i+j==10) continue; //hilangkan tanda slash didepan if, dan beri slash 2 di depan if yang atas untuk mencoba kode continue

printf("%i ",i+j);

printf("pass");

}

printf("\n");

}

}

Sorting Algorithm

Salah satu bagian penting dari struktur data adalah sorting atau pengurutan data. Ada banyak sekali Algoritma pengurutan data di dunia komputer, yatu : bubble sort, selection sort, insertion sort, exchange sort, quick sort, merge sort, dll.

Setiap algoritma memiliki kelebihan dan kekurangan masing – masing, kita akan mempelajari cukup 4 algoritma saja, yaitu bubble sort, selection sort, insertion sort, dan exchange sort. Bila ingin mempelajari algoritma yang lain silakan berkunjung ke www.wikipedia.org .

Bubble Sort

Perhatikan kode berikut :

Task 1

1. Apa yang dilakukan program diatas ?

2. Lakukan untuk pengurutan sebaliknya!

3. Pengurutan diatas dilakukan dari depan atau belakang? Buat program untuk sebaliknya!

4. Buat program agar user bisa inputkan data secara dinamis, baik untuk ascending, maupun descending!

5. Tambahkan kode agar user dapat melihat proses pengurutan data!

Note : Ascending adalah pengurutan data dari terkecil menuju terbesar, sedangkan descending adalah pengurutan dari data terbesar menuju terkecil.

Exchange Sort

Perhatikan kode berikut :

Task 2

1. Apa yang dilakukan program diatas ?

2. Lakukan untuk pengurutan sebaliknya!

3. Buat program agar user bisa inputkan data secara dinamis, baik untuk ascending, maupun descending!

4. Tambahkan kode agar user dapat melihat proses pengurutan data!

5. Apa perbedaan antara exchange sort dan bubble sort!

Selection Sort

Perhatikan kode berikut :

Task 3

1. Apa yang dilakukan program diatas ?

2. Lakukan untuk pengurutan sebaliknya!

3. Apa fungsi pos?

4. Buat program agar user bisa inputkan data secara dinamis, baik untuk ascending, maupun descending!

5. Tambahkan kode agar user dapat melihat proses pengurutan data!

Insertion Sort

Perhatikan kode berikut :

Task 4

1. Apa yang dilakukan program diatas ?

2. Lakukan untuk pengurutan sebaliknya!

3. Apa fungsi tampung?

4. Buat program agar user bisa inputkan data secara dinamis, baik untuk ascending, maupun descending!

5. Tambahkan kode agar user dapat melihat proses pengurutan data!

Task 5

1. Apa yang menjadi kesalahan pada program diatas?

2. Coba anda perbaiki!

Task 6

1. Gabungkan 4 sorting diatas menjadi 1 program menu pilihan untuk mengurutkan data kode pos.

2. User pertama kali harus memasukkan data terlebih dahulu, apabila tidak ada data, maka pengurutan data tidak bisa berjalan.

3. Data yang masuk hanya bisa berupa angka.

4. Semua metode mengurutkan secara ascending.

5. Pada tiap metode, user dapat melihat proses pengurutan data.

TAMBAHAN

Quick Sort

Quick sort merupakan algoritma kedua tercepat setelah merge sort. Quick sort disebut juga divide and conquer algorithm. Quick sort memiliki average case _nLog_n

Langkah-langkah quick sort :

1. SELECT

Pilih sebuah element , elemen ini kita sebut pivot

2. DIVIDE

Kemudian pisahkan data menjadi 2 bagian, bagian yang lebih kecil dari pivot dan bagian yang lebih besar dari pivot

3. RECUR and CONQUER

Kemudian 2 bagian tersebut diurutkan secara rekursif dengan memanggil fungsi itu sendiri, misal quicksort()

Perhatikan kode dibawah ini dan silakan di coba deprogram anda masing-masing:

Task 7

1. Bagian mana pada program yang menentukan pivot ?

2. Bagian mana pada program yang memisahkan array menjadi 2 bagian ?

3. Bagian mana pada program yang melakukan fungsi rekursif ?

Daftar Pustaka

· http://en.wikipedia.org/wiki/Sorting_algorithm

· lecturer.eepis-its.edu/~entin/Struktur%20Data/Minggu%2011/Minggu%2011%20Quick.pdf

· http://www.informatika.org/~rinaldi/Stmik/2005-2006/Makalah2006/MakalahStmik2006-27.pdf

· http://lecturer.ukdw.ac.id/anton/strukdat.php

POINTER

Introduction

Setiap kali kita mendeklarasikan variabel, C/C++ akan menyediakan alokasi memori untuk masing-masing variabel. Ukuran memori yang dialokasikan berbeda-beda tergantung dari tipe data variabelnya. Misalnya untuk integer 2 bytes, untuk float 4 bytes, dst. Jadi, setiap variabel yang kita deklarasikan mempunyai 2 atribut yaitu address dan value.

Pengertian Pointer

Pada pertemuan kali ini, kita akan membahas powerful feature dari bahasa pemograman C/C++, yaitu pointer. Pointer (variabel penunjuk) adalah suatu variabel yang berisi alamat memori dari suatu variabel lain. Pointer merupakan variabel level rendah yang dapat digunakan untuk menunjuk nilai integer, character, float, double, atau single, dan bahkan tipe-tipe data lain yang didukung oleh bahasa C.

Variabel biasa, sifatnya statis dan sudah pasti, sedangkan pada pointer sifatnya dinamis dan dapat lebih fleksibel. Variabel pointer yang tidak menunjuk pada nilai apapun berarti memiliki nilai NULL, dan disebut sebagai dangling pointer karena nilainya tidak diinisialisasi dan tidak dapat diprediksi.

Deklarasi Pointer

Seperti halnya variabel yang lain, variabel pointer juga harus dideklarasikan terlebih dahulu sebelum digunakan.

Bentuk Umum : tipe_data *nama_pointer;

Contoh : int *nilai;

char *huruf;

Pendeklarasian variabel pointer menggunakan tanda * sebelum nama variabelnya, sedangkan untuk menampilkan nilai yang ditunjuk oleh suatu variabel pointer, juga digunakan operator * (tanda asterisk). Jika diinginkan untuk menampilkan alamat tempat penyimpanan nilai yang ditunjuk oleh suatu variabel pointer, digunakan operator & (tanda ampersand).

Operasi pada Pointer

· Operasi Penugasan

Suatu variable pointer seperti halnya variable yang lain, juga bisa mengalami operasi

penugasan. Nilai dari suatu variable pointer dapat disalin ke variable pointer yang lain

Operator (&) dalam kaitannya dengan pointer adalah operator yang mengembalikan alamat memori dari operandnya. Contohnya :

int y = 5; /*deklarasi variabel y*/

int *yPtr; /*deklarasi variabel pointer yPtr*/

yPtr = &y; /*mengisi variabel pointer yPtr dengan alamat dari variabel y*/

Maka representasi dari operasi penugasan di atas adalah

Representasi yang lain, misalnya asumsikan bahwa variabel y berada pada alokasi memori 600000 dan variabel pointer yPtr berada pada alokasi memori 500000.

Contoh program (untuk dicoba)

Pertanyaan :

1. Perintah apa yang digunakan untuk menampilkan alamat dari variabel i, namun tanpa melalui pengaksesan variabel pointer ia?

Pertanyaan :

2. t = *p;

*p = *q;

*q = t;

Fungsi di atas ini (dengan pointer) untuk apakah itu?

Untuk membantu, coba tambahkan perintah di bawah ini pada program di atas:

printf("nilai yang ditunjuk p sekarang = %d di alamat %p\n",*p,p);

printf("nilai yang ditunjuk q sekarang = %d di alamat %p\n",*q,q);

· Operasi Aritmatika

Suatu variabel pointer hanya dapat dilakukan operasi aritmatika dengan nilai integer

saja. Operasi yang biasa dilakukan adalah operasi penambahan dan pengurangan.

Operasi penambahan dengan suatu nilai menunjukkan lokasi data berikutnya (index

selanjutnya) dalam memori. Begitu juga operasi pengurangan.

Asumsikan kita telah mendeklarasikan sebuah array float v[5], dan anggap elemen pertamanya berada pada lokasi 3000 di memori. Lalu kita deklarasikan sebuah variabel pointer *vPtr, ada dua cara untuk mengisi variabel pointer *vPtr dengan alamat dari elemen pertama array v, yaitu :

float *vPtr = v;

float *vPtr = &v[0];

Jika kita melakukan operasi aritmatika seperti

vPtr += 2;

dalam perhitungan aritmatika biasa, maka vPtr yang semula berisi 3000 menjadi 3000 + 2 = 3002, namun ini tidak berlaku pada pointer. Operasi aritmatika pada pointer di atas artinya adalah vPtr yang semula menunjuk pada v[0] sekarang menunjuk ke v[2].

Karena vPtr menunjuk alamat memori dari variabel v yang bertipe float, maka vPtr sekarang berisi 3008 (3000 + 2 * 4).

Contoh program (untuk dicoba)

Pertanyaan

3. Berapa selisih nilai (menggunakan heksadesimal) antar penunjuk dengan penunjuk+1? Hal apa yangmempengaruhi besarnya selisih nilai tersebut?

Untuk membantu, coba ganti tipe data variabel nilai dari int menjadi float.

Pointer pada Array

Pada array, pointer hanya perlu menunjuk pada alamat elemen pertama saja karena letak alamat array sudah berurutan pada memori.

Contoh program (untuk dicoba)

Pertanyaan

4. Tambahkan potongan kode program pada program di atas untuk membalik suatu kata/kalimat dengan menggunakan pointer!

Pointer pada Struct

Pointer dapat bertipe apa saja, bahkan tipe buatan kita sendiri.

Contoh program (untuk dicoba)

Latihan

Kalian tentu telah mengenal fitur T9 yang ada di handphone. Misalnya saat kita mengaktifkan T9 input yang bahasa inggris, lalu kita ingin mengetik school, maka kita cukup menekan 724665, maka otomatis akan keluar kata “school”.

Nah, sekarang kita coba menerapkan T9 didalam program latihan kita dengan menggunakan struct dan pointer tentunya.

Spesifikasi Input : Program menampilkan tulisan “Masukkan sebuah kalimat : “ kemudian program menunggu user memasukkan sebuah kalimat (tidak lebih dari 100 karakter).

Spesifikasi output : Program akan mengubah kalimat yang dimasukkan user menjadi rangkaian angka dengan menggunakan tabel T9.

T9	0	1	2	3	4	5	6	7	8	9	#
Data	0	Default 1	A B C 2	D E F 3	G H I 4	J K L 5	M N O 6	P Q R S 7	T U V 8	W X Y Z 9	Spasi

Program ini tidak case sensitif, artinya APA dengan apa atau Apa adalah sama.

Contoh:

Latihan 1

Input:

Masukkan sebuah kalimat : Aku ingin pulang

Output:

258#46446#785264

Latihan 2

Input:

Masukkan sebuah kalimat : Struktur Data 85 dapat A

Output:

78785887#3282#85#32728#2

Langkah-langkahnya:

1. Include kan file stdio.h dan ctype.h (ctype nantinya digunakan untuk memanggil fungsi toupper(char c)).

2. Buat struct Kata berisi 2 elemen yaitu elemen bertipe array of character (elemennya 100) dan jml_kata bertipe integer.

3. Buat sebuah variabel kata bertipe Kata dan sebuah variabel pointer p_kata bertipe Kata dan langsung mengacu pada alamat dari variabel kata.

4. Dalam fungsi main() buat variabel kalimat bertipe array of character dengan 100 elemen.

5. Selanjutnya ikuti code di bawah ini.

Lanjutkan program di atas agar sesuai dengan spesifikasi input dan output!

Hint :

Contoh Output Program :

DAFTAR PUSTAKA

Deitel, Harvey M dan Paul J Deitel. 2005. C++ How to Program, Fifth Edition. New Jersey: Prentice Hall.

Deshpande, P. S dan O. G. Kakde. 2003. C & Data Structures. Massachusetts : Dreamtech Press.

Solichin, Achmad. 2003. Pemograman Bahasa C dengan Turbo C. IlmuKomputer.Com.

Materi Struktur Data TI UKDW oleh Antonius Rachmat C. S.Kom, M.Sc.

Materi Praktikum Struktur Data 2007 oleh TIM Asisten Praktikum Struktur Data 2007.

ARRAY

Pertemuan kali ini kita akan kembali membahas materi yang sudah diberikan di algoritma dan pemrograman, yaitu array. Secara singkat, array adalah suatu tipe data terstruktur yang berupa sejumlah data sejenis (bertipe data sama) yang jumlahnya tetap dan diberi suatu nama tertentu.

Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-dimensi.

DEKLARASI

tipe_data nama_var_array [ukuran];

tipe_data : menyatakan jenis tipe data elemen larik (int, char, float, dll)

nama_var_array : menyatakan nama variabel yang dipakai.

ukuran : menunjukkan jumlah maksimal elemen larik.

Contoh :

Int nilai[6];

INISIALISASI

Menginisialisasi array sama dengan memberikan nilai awal array pada saat didefinisikan.

int nilai[6] = {8,7,5,6,4,3};­­­­­

Contoh diatas berarti berarti anda memesan tempat di memori komputer sebanyak 6 tempat

dengan indeks dari 0-5, dimana indeks ke-0 bernilai 8, ke-1 bernilai 7, dst, dan dimana semua elemennya bertipe data integer.

PENGAKSESAN

nama_var_array [indeks];

Pengisian dan pengambilan nilai pada indeks tertentu dapat dilakukan dengan mengeset nilai atau menampilkan nilai pada indeks yang dimaksud. Pengaksesan elemen array dapat dilakukan berurutan atau random berdasarkan indeks tertentu secara langsung.

Contoh pengisian langsung saat deklarasi:

#include

void main ()

{ int billy [] = {16, 2, 77, 40, 12071};

int n, result=0;

for ( n=0 ; n<5>

{

result += billy[n];

}

printf("%d",result);

}

Contoh pengaksesan dan pengisian langsung ke tiap elemen dari array:

#include

#include

void main ()

{

int A [5]={20,9,1986,200,13},n,edit;

clrscr();

printf("Data yang lama\n");

for (n=0;n<5;n++)

{

printf("%i ",A[n]);

}

printf("\nData yang baru : \n");

A[0]=4;

A[1]=2;

A[2]=1;

A[3]=3;

A[4]=5;

for (n=0;n<5;n++)

{

printf("%i ",A[n]);

}

}

Contoh penghapusan data(elemen) pada array:

#include

#include

void main ()

{ int A [5]={20,9,1986,200,13},n,hapus;

clrscr();

printf("Data yang lama\n");

for (n=0;n<5;n++)

{

printf("%i ",A[n]);

}

printf("data yang ingin dihapus : ");

scanf("%i",&hapus);

printf("\nData yang baru : \n");

for (n=hapus-1;n<5-1;n++)

{

A[n]=A[n+1];

}

for (n=0;n<4;n++)

{

printf("%i ",A[n]);

}

}

LATIHAN

1. Buatlah fungsi untuk array 1 dimensi untuk ADD, EDIT, DELETE, dan VIEW.

STRUCT

· Bentuk struktur data yang dapat menyimpan variabel-variabel dalam 1 nama, namun memiliki tipe data yang berbeda ataupun sama. Variable-variabel tersebut memiliki kaitan satu sama yang lain.

Bentuk umum :

typedef struct nama_struct{

tipe_data ;

tipe_data ;

....

};

DEKLARASI

Ada 2 cara pendeklarasian struct, yaitu :

Deklarasi 1:

typedef struct Mahasiswa {

char NIM[8];

char nama[50];

float ipk;

};

Deklarasi 2 :

struct {

char NIM[8];

char nama[50];

float ipk;

} mhs;

Contoh struct:

#include

#include

void main()

{

struct orang

{

char nama[40];

short umur;

}saya;

printf("nama : ");

cin.getline(saya.nama,40);

printf("umur :" );

scanf("%i",&saya.umur);

printf("%s berumur %i",saya.nama,saya.umur);

}

ARRAY OF STRUCT

Apabila hendak menggunakan 1 struct untuk beberapa kali, ada 2 cara :

1. Deklarasi manual

Contoh :

#include

typedef struct Mahasiswa {

char NIM[8];

char nama[50];

float ipk;

};

void main()

{

Mahasiswa a,b,c;

……

……

……

}

artinya struct mahasiswa digunakan untuk 3 variabel, yaitu a,b,c

2. Array of struct

Contoh :

#include

typedef struct Mahasiswa {

char NIM[8];

char nama[50];

float ipk;

};

void main()

{

Mahasiswa mhs[3];

……

……

……

}

artinya struct mahasiswa dapat digunakan untuk tiga variabel mhs, yaitu mhs[0], mhs[1], dan mhs[2].

Contoh lainnya :

#include

#include

#include

typedef struct orang

{

char nama[30];

short umur;

};

void main()

{

orang saya[5];

int i,x;

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

{

printf("nama ke-%i : ",i+1);

cin.getline(saya[i].nama,30);

printf("umur ke-%i : ",i+1);

scanf("%i",saya[i].umur);

printf("%s berumur %i",saya[i].nama,saya[i].umur);

}

for(x=0;x<=4;x++)

{

printf("nama %s berumur %d",saya[x].nama,saya[x].umur);

}

}