Tugas Praktek Algo

I Made Wira Dharma
080010243
P081


POINTER

Dikutip dari :mas-devid.blogspot.com

Pengertian Pointer

Pointer (variabel penunjuk) adalah suatu variabel yang berisi alamat memori dari suatu variabel lain. Alamat ini merupakan lokasi dari obyek lain (biasanya variabel lain) di dalam memori. Contoh, jika sebuah variabel berisi alamat dari variabel lain, variabel pertama dikatakan menunjuk ke variabel kedua.



Operator Pointer

Ada 2 operator pointer yang dikenal secara luas, yaitu operator & dan operator *.
Operator &


Operator & merupakan operator alamat. Pada saat pendeklarasian variable, user tidak diharuskan menentukan lokasi sesungguhnya pada memory, hal ini akan dilakukan secara otomatis oleh kompiler dan operating sysem pada saat run-time. Jika ingin mengetahui dimana suatu variable akan disimpan, dapat dilakukan dengan memberikan tanda ampersand (&) didepan variable , yang berarti "address of". Contoh :

ted = &andy;

Penulisan tersebut berarti akan memberikan variable ted alamat dari variable andy. Karena variabel andy diberi awalan karakter ampersand (&), maka yang menjadi pokok disini adalah alamat dalam memory, bukan isi variable. Misalkan andy diletakkan pada alamat 1776 kemudian dituliskan instruksi sbb :

andy = 25;

fred = andy;

ted = &andy;


Operator *

Operator * merupakan operator reference. Dengan menggunakan pointer, kita dapat mengakses nilai yang tersimpan secara langsung dengan memberikan awalan operator asterisk (*) pada identifier pointer, yang berarti "value pointed by". Contoh :

beth = *ted;

(dapat dikatakan:"beth sama dengan nilai yang ditunjuk oleh ted") beth = 25, karena ted dialamat 1776, dan nilai yang berada pada alamat 1776 adalah 25.


Ekspresi dibawah ini semuanya benar, perhatikan :

andy = 25;

&andy = 1776;

ted = 1776;

*ted = 25;




Ekspresi pertama merupakan assignation bahwa andy = 25;. Kedua, menggunakan operator alamat (address/derefence operator (&)), sehingga akan mengembalikan alamat dari variabel andy. Ketiga bernilai benar karena assignation untuk ted adalah ted = &andy;. Keempat menggunakan reference operator (*) yang berarti nilai yang ada pada alamat yang ditunjuk oleh ted, yaitu 25. Maka ekspresi dibawah ini pun akan bernilai benar :

*ted = andy;



Deklarasi Pointer

Seperti halnya variabel lain, variabel pointer juga harus dideklarasikan terlebih dahulu sebelum digunakan. Bentuk umum deklarasi pointer adalah :

\



Dimana Tipe_data
merupakan tipe dari data yang ditunjuk, bukan tipe dari pointer-nya. Contoh :

1. Mensubstitusikan address sebuah variabel ke pointer dengan memakai address operator &

int x;
int *ptr;
ptr = &x;

2. Mensubstitusikan address awal sebuah array ke pointer

char t[5];
char *ptr;
ptr = t;

3. Mensubstitusikan address salah satu elemen array dengan address operator

char t[5] ;
char *ptr;
ptr = &t[3];

4. Mensubstitusikan address awal character string ke pointer char

char *ptr;
ptr = "jakarta"

5. Mensubstitusikan NULL pada pointer. NULL ada pointer kosong, menunjukkan suatu status dimana pointer itu belum diinisialisasikan dengan sebuah address tertentu.

6. Memakai fungsi MALLOC.




LINKED LIST


Dikutip dari : http://hatma.info/download/struktur_data/
linked%20list%20VS%20array.doc.


Pengertian Linked list :
• sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian
• struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori.

X
Y
Null

Bentuk Umum :
Infotype sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list
Next address dari elemen berikutnya (suksesor)
Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu dengan notasi :
Sebelum digunakan harus dideklarasikan terlebih dahulu :
Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :
Beberapa Definisi :
1. List l adalah list kosong, jika First(L) = Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena
Next(Last) = Nil
Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null
Single Linked List

Pada gambar di atas tampak bahwa sebuah data terletak pada sebuah lokasi memori area. Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).
Pembuatan Single Linked List dapat menggunakan 2 metode:
• LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
• FIFO (First In First Out), aplikasinya : Queue (Antrean)
Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.
Circular Double Linked List
Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.
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.
A. STACK DENGAN SINGLE LINKED LIST
Selain implementasi stack dengan array seperti telah dijelaskan sebelumnya, stack daat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori.
Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack.
Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.
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.

B. QUEUE DENGAN DOUBLE LINKED LIST
Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list.
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).

Stack Dengan Linked List Stack Dengan Array operasi : create() procedure create;
begin
top := nil ;
end;
procedure create;
begin
top := 0;
end;
operasi : empty() function empty : boolean;
begin
empty := false ;
if top = nil then empty := true ;
end;
function empty : boolean;
begin
empty := false ;
if top = 0 then empty := true ;
end;
operasi : full() tidak ada istilah full pada stack.
program tidak menentukan jumlah elemen stack yang mungkin ada. kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. tempat akan sesuai dengan banyaknya elemen yang mengisi stack.
function full : boolean;
begin
full := false ;
if top = max then full := true ;
end;
operasi : push() procedure push (elemen : typedata) ;
var now:point ;
begin
now(now) ;
now^.isi := elemen ;
if empty then
now^.next := nil ;
else
now^.next := top ;
top := now ;
end;
procedure push (elemen : typedata) ;
begin
if not full then
begin
top := top + 1 ;
stack [top] := elemen ;
end;
end;
operasi : pop() procedure pop (var elemen : typedata) ;
var now:point ;
begin
if not empty then
begin
elemen := now^.isi ;
now := top ;
top := top^.next ;
dispose(now) ;
end;
end;
procedure pop (elemen : typedata) ;
begin
if not empty then
begin
elemen := stack [top] ;
top := top – 1 ;
end;
end;
operasi : clear procedure clear ;
var trash : typedata ;
begin
while not empty do pop(trash) ;
end;
procedure clear ;
begin
top := 0 ;
end;



__Sorting Source Code__

#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);
}



source code program Sequential
Yang datanya telah diinputkan di source code.

#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();
}

source code program Sequential
Yang datanya telah diinputkan dari user.

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

void main()
{
clrscr();
int data[100],n;
int cari,index;
int ketemu=0;

cout<<"Masukkan jumlah data : "; cin>>n;
for(int i=0;i<n;i++)
{
cout<<"Masukkan data ke-"<<(i+1)<<" = "; cin>>data[i];

}
cout<<"Masukkan data yang ingin di cari = ";
cin>>cari;

for(int i=1;i<=100;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();
}

source code program Binary Searching

#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();
}

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.