rangkuman materi praktikum algoritma dan struktur data
Modul 1 (struktur data, array, pointer dan struktur)
Konsep dasar struktur data
Struktur data adalah sebuah bagian dari ilmu pemrograman dasar yang mempuyai karakteristik yang terkait dengan sifat dan cara penyimpanan sekaligus pengguna atau pengakses data. Struktur data bertujuan agar cara merepresentasikan data dalam membuat program dapat dilakukan secara efesien dalam pengolahan di memori dan pengolahan penyimpanan dari program ke storage juga lebih mudah dilakukan.
Konsep dasar array
Array adalah kumpulan elemen-elemen data. Kumpulan elemen tersebut mempunyai susunan yang teratur. Jmlah elemen terbatas, dan semua elemen mempunyai tipe data yang sama. Jenis-jenis array :
Array satu dimensi, contoh : int nilai[5];
Array dua dimensi, contoh : int nilai[2][4]; // [2] menyatakan baris, [4] menyatakan kolom
Array multidimensi, contoh : int nilai[3][4][5];
Contoh membuat program pangkat array dimensi satu
Program code:
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
void main(){
int square[100]; //--> Array 1 dimensi dengan tempat yang dipesan sebanyak 100
int i;
int k;
//perhitungan
for(i = 0; i < 10; i++){
k = i+1;
square[i] = k * k;
printf("n Pangkat dari %d adalah %d", k, square[i]);
}
getch();
}
OUTPUT:
Konsep dasar pointer
Pointer adalah sebuah variable yang berisi alamat variable yang lain. Satu pointer dimksudkan untuk menunjuk kesuatu alamat memori sehingga alamat dari suatu variable dapat diketahui dengan mudah.
Contoh program menggunakan POINTER untuk merubah karakter yang dimasukkan dari huruf kecil menjadi besar
Program Code:
#include <iostream>
#include <conio.h>
#include <ctype.h>
using namespace std;
void main()
{
char str[100];
char *p;
int i;
cout<<"tuliskan kata yang ingin dirubah : ";
cin>>str;
p= str;
for(i=0;p[i];i++)
p[i]=toupper(p[i]);
cout<<"Perubahan setelah proses adalah "<<p<<endl;
getch();
}
OUTPUT:
Konsep dasar struktur
Struktur adalah koleksi dari variable yang dinyatakan sebuah nama, dengan sifat setiap variable dapat memiliki tipe yang berlainan. Struktur bisa dipakai untuk mengelompokkan beberapa informasi yang berkaitan menjadi sebuah satu kesatuan. Contoh sebuah struktur adalah informasi data tanggal, yang berisi tanggal, bulan, dan tahun. Bentuk umum dalam mendefenisikan struktur adalah :
Struct nama_tipe_struktur
{
Tipefiled1; tipefiled2; tipefiled3;
}variable_struktur
Modul 2 linked list
Untuk menggabungkan objek satu dengan lainya, diperlukan paling tidak sebuah variable yang bertipe pointer. Syarat linked list adalah harus dapat diketahui alamat simpul pertama atau biasa dipakai variable First/Start/Header.
Istilah-istilah dalam linked list :
A. Simpul, Simpul terdiri dari dua bagian yaitu Bagian data, dan Bagian pointer yang menunjuk ke simpul berikutnya
B. First/Header, Variabel First/Header berisi alamat (pointer)/acuan (refrence) yang menunjuk lokasi simpul pertama linked list, digunakan sebagai awal penelusuran linked list.
C. Nill/Null, Tidak bernilai, digunakan untuk menyatakan tidak mengacu ke manapun.
D. Simpul Terakhir(Last), Simpul terakhir linked list berarti tidak menunjuk simpul berikutnya. Tidak terdapat alamat disimpan di field pointer di simpul terakhir.
1. List kosong, hanya terdiri dari sebuah penunjuk elemen yang berisi NULL(kosong), tidak memiliki satu buah elemen pun sehingga hanya berupa penunjuk awal elemen berisi NULL.
2. List tunggal, adalah list yang elemenya hanya menyimpan informasi elemen setelahnya (next), sehingga jalanya pengaksesan list hanya dapat dilakukan secara maju. List tunggal terbagi menjadi tiga jenis yaitu list tunggal dengan kepala (first), list tunggal dengan kepala (first) dan ekor (tail), serta list tunggal yang berputar.
3. List ganda
Operasi Dasar pada Lingked List :
a. IsEmpty : Fungsi ini menentukan apakah linked list kosong atau tidak.
b. Size : operasi untuk mengirim jumlah elemen di linked list.
c. Create : operasi untuk penciptaan list baru yang kosong.
d. Insertfirst : operasi untuk penyisipan simpul sebagai simpul pertama.
e. Insertafter : operasi untuk penyisipan simpul setelah simpul tertentu.
f. Installaast : operasi untuk penyisipan simpul setelah simpul terakhir.
g. Insertbefore : operasi untuk penyisipan simpul sebelum simpul tertentu.
h. Deletefirst : operasi penghapusan simpul pertama.
i. Deleteafter : operasi untuk penghapusan setelah simpul tertentu.
j. Deletelast : operasi penghapusan simpul terakhir.
Mendeklarasikan, memasukkan data, dan menampilkan data pada Single Linked List
Program Code:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<conio.h>
#include<malloc.h>
using namespace std;
struct dtnilai *tampung;
struct dtnilai *ujung;
struct dtnilai *awal;
int j;
char strnilai[5], jawab[6];
struct dtnilai{
char nim[10];
char nama[20];
double nilai;
struct dtnilai *next;
};
int main(){
printf("DATA MAHASISWA : n");
printf("==================================n");
printf("n");
while(1){
if(j==0){
awal = (struct dtnilai*) malloc(sizeof(struct dtnilai));
printf("NIM : ");
gets(awal->nim);
printf("n");
printf("Nama : ");
gets(awal->nama);
printf("n");
printf("Nilai Test : ");
gets(strnilai);
printf("n");
awal->nilai = atof(strnilai);
tampung=awal;
tampung->next = NULL;
}
else{
ujung = (struct dtnilai*) malloc(sizeof(struct dtnilai));
tampung->next=ujung;
printf("NIM : ");
gets(ujung->nim);
printf("n");
printf("Nama : ");
gets(ujung->nama);
printf("n");
printf("Nilai Test : ");
gets(strnilai);
printf("n");
ujung->nilai=atof(strnilai);
ujung->next=NULL;
tampung=ujung;
}
printf("Masukkan data lagi? (y/t) : ");
gets(jawab);
printf("n");
if((strcmp(jawab, "Y")==0||strcmp(jawab, "y")==0)){
j++;
continue;
}
else if((strcmp(jawab, "Y")==0||strcmp(jawab, "t")==0))
break;
}
printf("Data mahasiswa yang telah diinputkan : n");
printf("=========================================n");
printf("NIMtNamatNilain");
printf("n");
ujung=awal;
while(ujung!=NULL){
printf("%st%st%6.21fn", ujung->nim, ujung->nama, ujung->nilai);
ujung=ujung->next;
}
getch();
}
OUTPUT:
Modul 3 stack
Seperti halnya jika kita mempunyai sebuah tumpukan buku, agar tumpukan buku itu tidak ambruk ketika kita mengambil sebuah buku di dalam tumpukan itu maka harus diambil satu per satu dari tumpukan yang paling atas dari tumpukan.
Perhatikan bahwa dengan definisi semacam ini, representasi tabel sangat tepat untuk mewakili stack, karena operasi penambahan dan pengurangan hanya dilakukan disalah satu ujung tabel.
Stack memiliki operasi-operasi pokok sebagai berikut :
Push : Untuk menambahkan item pada tumpukan paling atas.
void Push (ItemType x, Stack *S)
{
If(Full (S))
Printf(“Stack FULL”);
Else
{
--(S->Count);
x=s->Item(s->Count);
}
}
Clear :Untuk mengosongkan stack
Void intializeStack (Stack S)
{
S->Count=0;
}
IsEmpty : Untuk memeriksa apakah stack kosong
Int Empty (Stack *S)
{
Return(S->Count==0);
}
IsFull : Untuk memeriksa apakah stack sudah penuh
Int Full (Stack S)
{
return (S->Count==MAXSTACK);
}
Contoh Program Stack
Program Code:
#include<stdio.h>
#include<conio.h>
#include<iostream>
#define MAXSTACK 3
typedef int itemType;
typedef struct{
int item[MAXSTACK];
int jml;
} Stack;
void init(Stack *s){
s->jml=0;
}
int kosong(Stack *s){
return (s->jml==0);
}
int penuh(Stack *s){
return (s->jml==MAXSTACK);
}
void isi(itemType x, Stack *s){
if(penuh(s))
printf("MAAF!!! data penuhn");
else{
s->item[s->jml]=x;
++(s->jml);
}
}
void ambil(Stack *s, itemType *x){
if(kosong(s))
printf("nMaaf Data Kosongn");
else
{
--(s->jml);
*x=s->item[s->jml];
s->item[s->jml]=0;
printf("nData %i Berhasil Diambiln", *x);
}
}
void tampil(Stack *s){
if(kosong(s))
printf("nMaaf data masih kosongn");
else
printf("n");
for(int i=s->jml-1;i>=0;i--){
printf("Data: %dn",s->item[i]);
}
}
void hapus(Stack *s){
s->jml=0;
printf("nSemua Data Berhasil Dihapusn");
}
void main(){
int pil;
Stack tumpukan;
itemType data;
init(&tumpukan);
do{
printf("nMENU: n 1. Isi (Data angka)n 2. Ambiln 3. Lihatn 4. Hapus (Hapus semua data)n 5. Keluarn");
printf("n");
printf("Masukkan Pilihan : "); scanf("%i", &pil);
switch(pil){
case 1:
printf("nMasukkan Data Angka : ");
scanf("%i", &data);
isi(data, &tumpukan);
break;
case 2:
ambil(&tumpukan, &data);
break;
case 3:
tampil(&tumpukan);
break;
case 4:
hapus(&tumpukan);
break;
}
}
while(pil!=5);
getch();
}
OUTPUT:
Contoh program mempresentasikan Stack menggunakan Linked List
Program Code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<conio.h>
using namespace std;
struct sStack
{
int isi;
struct sStack*next;
};
int x, i=1, j=1;
struct sStack*atas, *bantu, *baru;
void push(int nilai){
if(j==1){
atas=(struct sStack*)malloc(sizeof(struct sStack));
atas->isi=nilai;
atas->next=NULL;
}
else{
baru=(struct sStack*)malloc(sizeof(struct sStack));
baru->isi=nilai;
baru->next=atas;
atas=baru;
}
j++;
}
void pop(){
bantu=atas;
printf("Data yang di POP %d : %dn", i, bantu->isi);
atas=atas->next;
i++;
free(bantu);
}
void main(){
char jawab[2], strNilai[5];
while(1){
printf("Data yang di PUSH ke %d : ", j);
gets(strNilai);
x=atoi(strNilai);
push(x);
printf("Data lagi? <y/t> : ");
gets(jawab);
if((strcmp(jawab, "Y")==0||(strcmp(jawab, "y")==0)))
continue;
else
break;
}
j--;
printf("Data nilai yang telah diinputkan : n");
while(atas!=NULL)
pop();
getch();
}
OUTPUT:
Modul 4 queue
Antrian adalah suatu kumpulan data yang penambahan elemennya hanya bisa dilakukan pada suatu ujung (disebut sisi belakang atau REAR), dan penghapusan atau pengambilan elemen dilakukan lewat ujung yang lain (disebut sisi depan atau FRONT). Prinsip yang digunakan dalam antrian ini adalah FIFO (First In First Out) yaitu elemen yang pertama kali masuk akan keluar pertama kalinya.
Contoh program queue statis
Program code:
#include<queue>
#include<iostream>
#include<conio.h>
using namespace std;
int main(){
queue <int> que;
que.push(10);
que.push(2);
que.push(3);
cout<<"Paling depan : "<<que.front()<<endl;
cout<<"Paling belakang : "<<que.back()<<endl;
que.pop();
cout<<"10 sudah dikeluarkan"<<endl;
cout<<"Paling depan : "<<que.front()<<endl;
cout<<"Paling belakang : "<<que.back()<<endl;
que.push(6);
cout<<"Angka 6 dimasukkan"<<endl;
cout<<"Paling depan : "<<que.front()<<endl;
cout<<"Paling belakang : "<<que.back()<<endl;
_getch();
}
OUTPUT:
Modul 5 rekursif
Fungsi rekursif adalah suatu fungsi yang memanggil dirinya sendiri，artinya fungsi tersebut dipanggil di dalam tubuh fungsi itu sendiri. Contoh menghitung nilai factorial. Rekursif sangat memudahkan untuk memecahkan permasalahan yang kompleks. Sifat-sifat rekursif:
a) Dapat digunakan ketika inti dari masalah terjadi berulang kali.
b) Sedikit lebih efisien dari iterasi tapi lebih elegan.
c) Method-methodnya dimungkinkan untuk memanggil dirinya sendiri.
Data yang berada dalam method tersebut seperti argument disimpan sementara ke dalam stack sampai method pemanggilnya diselesaikan.
Contoh Program faktorial
Program code:
#include <stdio.h>
#include <iostream>
#include <conio.h>
using namespace std;
int faktorial (int n)
{
if(n==1)
return(1);
else
return (n*faktorial(n-1));
}
void main()
{
int x;
printf("Mencari Nilai Faktorial n");
printf("Masukkan Nilai X : ");
scanf("%d", &x);
printf("Nilai Faktorial dari %d= %d n", x, faktorial(x));
system("pause");
getch();
}
OUTPUT:
Contoh program untuk menentukan bilangan yang terbesar dan terkecil dari dua buah bilangan yang diinputkan
Program code:
# include <iostream>
# include <conio.h>
using namespace std;
int main()
{
int a,b,bsr,kcl;
cout<<"Masukkan Bilangan Pertama : ";
cin>>a;
cout<<"Masukkan Bilangan Kedua : ";
cin>>b;
if (a>b)
{
bsr=a;
kcl=b;
}
else if (a<b)
{
bsr=b;
kcl=a;
}
cout<<" Bilangan yang lebih besar "<<bsr<<endl;
cout<<" Bilangan yang lebih kecil "<<kcl<<endl;
getch();
}
OUTPUT:
modul 6 sorting
Pengurutan data (sorting) didefinisikan sebagai suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Ada dua macam urutan yang biasa digunakan dalam proses pengurutan yaitu : Urutan naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar, dan urutan turun (descending) yaitu dari data yang mempunyai nilai paling besar sampai paling kecil.
Contoh : data bilangan 5, 2, 6, dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6 atau diurutkan turun menjadi 6, 5, 4, 2.
Beberapa algoritma metode pengurutan dan prosedurnya sebagai berikut:
Bubble Sort
Bubble Sort adalah suatu metode pengurutan yang membandingkan elemen yang sekarang dengan elemen berikutnya. Apabila elemen sekarang > elemen berikutnya, maka posisinya ditukar. Kalau tidak, tidak perlu ditukar. Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda.
Contoh program untuk mengurutkan data-data berikut ini secara descending dengan metode bubble sort
4, 8, 5, 6, 2, 7, 5, 9, 5, 23, 30.
Program code:
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;
int main()
{
int dataku[]={4,8,5,9,6,2,7,5,9,5,23,30};
int adaPertukaran;
int n;
cout<<"Data BELUM diurutkan : n";
for(int ctr=0;ctr<12;ctr++)
{
cout<<" "<<dataku[ctr];
}
cout<<endl<<endl;
do{
adaPertukaran=0;
for(int i=0;i<13;i++)
{
for(int j=13;j>i;j--)
{
if(dataku[j-1]<dataku[j])
{
n=dataku[j];
dataku[j]=dataku[j-1];
dataku[j-1]=n;
adaPertukaran=1;
}
}
}
}while(adaPertukaran==1);
cout<<"Data SETELAH diurutkan : n";
for(int i=1;i<=12;i++)
{
cout<<dataku[i];
cout<<" ";
}
getch();
}
OUTPUT:
Selection Sort
Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot. Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
program untuk mengurutkan data-data berikut ini secara descending dengan metode selection sort
Program code:
#include <iostream>
#include <conio.h>
using namespace std;
int num[10],num2[10];
int n;
void select(int a, int b)
{
int t;
t=num[b];
num[b]=num[a];
num[a]=t;
}
void selection_sort()
{
int temp,i,j;
for(i=n;i>0;i--)
{
temp=i;
for(j=1;j<=i;j++)
{
if(num[j]<num[temp])
temp=j;
}
if(temp!=i)
select(temp,i);
}
}
int main()
{
int i;
cout<<"===PROGRAM SELECTION SORT==="<<endl;
cout<<endl;
cout<<"Masukkan Jumlah Data : ";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<"Masukkan Data ke - "<<i<<" : ";
cin>>num[i];
num2[i]=num[i];
}
selection_sort();
cout<<"nn";
cout<<"num Setelah di Sort (Descending): ";
for(i=1;i<=n;i++)
{
cout<<" "<<num[i];
}
cout<<"nn Proses Selesai n";
getch();
}
OUTPUT:
Merge Sort
Algoritma Merge Sort ialah algoritma pengurutan yang berdasarkan pada strategi divide and conquer. Algoritma ini terdiri dari dua bagian utama, pembagian list yang diberikan untuk di-sort ke dalam beberapa sublist yang lebih kecil, dan sort (mengurutkan) dan merge (menggabungkan) sublist-sublist yang lebih kecil ke dalam list hasil yang sudah diurutkan. Pembagian bisa dikatakan cukup mudah karena sublist-sublist tersebut dibagi ke dalam dua sublist yang ukurannya adalah setengah dari ukuran semula. Hal ini terus diulang sampai sublist itu cukup kecil untuk di-sort secara eflsien (umumnya telah terdiri dari satu atau dua elemen). Dalam langkah merge dua sublist disatukan kembali dan diurutkan pada saat yang sama.
Contoh program untuk mengurutkan data-data berikut ini secara descending dengan metode merge sort
Program code:
#include <iostream>
#include<stdio.h>
using namespace std;
#define MAX 5
int Data[MAX];
int temp[MAX];
void merge(int Data[],int temp[],int kiri,int tengah,int kanan)
{
int i, left_end,num_elements,tmp_pos;
left_end = tengah-1;
tmp_pos = kiri;
num_elements = kanan-kiri + 1;
while((kiri<=left_end)&&(tengah<=kanan))
{
if(Data[kiri]<=Data[tengah])
{
temp[tmp_pos] = Data[kiri];
tmp_pos = tmp_pos+1;
kiri = kiri + 1 ;
}
else
{
temp[tmp_pos] = Data[tengah];
tmp_pos = tmp_pos + 1;
tengah = tengah + 1 ;
}
}
while(kiri <= left_end)
{
temp[tmp_pos] = Data[kiri];
kiri = kiri + 1;
tmp_pos = tmp_pos+1;
}
while(tengah <= kanan)
{
temp[tmp_pos] = Data[tengah];
tengah = tengah + 1;
tmp_pos = tmp_pos + 1;
}
for(i=0;i <= num_elements;i++)
{
Data[kanan]=temp[kanan];
kanan = kanan -1 ;
}
}
void m_sort(int Data[],int temp[],int kiri , int kanan)
{
int tengah;
if(kanan > kiri)
{
tengah=(kanan + kiri)/2;
m_sort(Data, temp, kiri, tengah);
m_sort(Data ,temp , tengah+1, kanan);
merge(Data,temp,kiri,tengah+1,kanan);
}
}
void mergeSort(int Data[],int temp[],int array_size)
{
m_sort(Data ,temp, 0, array_size - 1);
}
int main()
{
int i;
printf("Masukkan DATA SEBELUM TERURUT : n");
for(i=0;i<MAX;i++)
{
printf("Data ke %i : ",i+1);
scanf("%d",&Data[i]);
}
mergeSort(Data, temp, MAX);
printf("n DATA SETELAH TERURUT (Descending) : ");
for(i=MAX-1;i >= 0;i--)
printf("%d ",Data[i]);
printf("n");
scanf("%d");
return 0;
}
OUTPUT:
Komentar
Posting Komentar