Minggu, 17 Oktober 2010

Double Circular Link List

DOUBLE CIRCULAR LINK LIST

Deklarasi Type

Type Infotype : < terdefinisi >
Type ElmtListDC :
Type addressDC: pointer to ElmtListDC
Type ListDC :
DCL : ListDC

procedure InsertFirst (Input /Output DCL:ListDC, Input P:addressDC )
{I.S. List DCL sembarang dan sirkuler, P sudah dialokasi, P<>Nil, Next(P)=Nil, Prev(P)=Nil)
F.S. P adalah element pertama list DCL}
Kamus
Algoritma :
If First (DCL) = Nil then
First (DCL) <— P
Last (DCL) <— P
Next(P) <— P
Else
Next (P) <— First (DCL)
Next(Last(DCL)) <— P
First (DCL) <— P





procedure InsertAfter (Input P, Prec : addressDC )
{I.S. Prec adalah elemen List DCL, Prec<>Nil, P sudah dialokasi, P<>Nil, Next(P)=Nil, Prev(P)=Nil)
F.S. P menjadi suksesor Prec}
Kamus
Algoritma :
Next (P) <— Next (Prec)
Prev (Next(Prec) <— P
Next (Prec) <— P
Prev (P) <— Prec

procedure InsertLast (Input /Output DCL:ListDC, Input P:addressDC )
{I.S. List DCL mungkin kosong dan sirkuler, P sudah dialokasi, P<>Nil, Next(P)=Nil, Prev(P)=Nil)
F.S. P adalah element terakhir list DCL}
Kamus
Algoritma :
If First (DCL) = Nil then
InsertFirst(DCL,P)
Else
Prev (P) <— Last (DCL)
Next (Prev (P)) <— P
Last (DCL) <— P
Next (P) <— First (DCL)



procedure DeleteFirst (Input /Output DCL:ListDC, Output P:addressDC )
{I.S. List DCL tidak kosong dan sirkuler, minimal 1 elemen, elemen pertama pasti ada
F.S. menghapus elemen pertama DCL, P adalah elemen pertama DCL sebelum penghapusan, DCL yang baru adalah Next (DCL), Next (P)=Nil, Prev (P)=Nil }
Kamus
Algoritma :
P <— First (DCL)
First (DCL) <— Next (First(DCL))
Next(Last (DCL)) <— Next (First(DCL))
Next (P) <— Nil
Prev (First(DCL)) <— Nil

procedure DeleteAfter (Input Prec:address, Output P:addressDC )
{I.S. List DCL tidak kosong dan sirkuler, Prec adalah elemen list, Next (Prec) <>Nil
F.S. Next (Prec), yaitu elemen beralamat P dihapus dari List, Next (P)=Nil, Prev (P)=Nil }
Kamus
Algoritma :
P <— Next (Prec)
If Next (P) = Nil then
Next (Prec) <— Nil
Last (DCL) <— Prec
Next(Last(DCL)) <— First(DCL)
Else
Next (Prec) <— Next (P)
Prev (Next (Prec)) <— Prec
Next (P) <— Nil


procedure DeleteLast (Input /Output DCL:ListDC, Output P:addressDC )
{I.S. List L tidak kosong dan sirkuler, minimal mengandung 1 elemen
F.S. menghapus elemen terakhir dari List, List mungkin menjadi kosong, P adalah alamat elemen terakhir List sebelum penghapusan }
Kamus
Algoritma :
If Next (First (DCL)) = Nil then
DeleteFirst(DCL,P)
Else
P <— Last (DCL)
Last (DCL) <— Prev (Last (DCL))
Next (Last (DCL)) <— First(DCL)
Prev (P) <— Nil
Next(P) <— Nil

Minggu, 03 Oktober 2010

ADT Garis

BOOLEAN.H

#ifndef __boolean__
#define __boolean__
#define true 1
#define false 0
#define boolean unsigned char

#endif


GARIS.H

/* file : garis.h */
/* ADT point */

#ifndef garis_h
#define garis_h
#include "POINT.h"

/* contoh ADT yg memanfaatkan ADT lain */
/* garis dibentuk oleh duah buah point */

typedef struct
{
point paw; /* titik awal */
point pakh; /* titik akhir */
} garis;


/* definisi prototipe primitif */
/*** konstruktor membentuk garis ***/

void makegaris(point p1,point p2,garis *l);
/* I.S : p1 & p2 terdefinisi */
/* F.S : l terdefinisi dg l.paw=p1 & l.pakh=p2 */
/* membentuk sebuah garis l dari komponen-komponennya */

/*** selektor garis ***/
point getpaw (garis l);
/* mengirimkan komponen titik pertama dari l garis */

point getpakh(garis l);
/* mengirimkan komponen titik kedua dari l garis*/


/* kelompok interaksi dengan I/O device, baca/tulis */
void bacagaris(point p1,point p2,garis *l);
/* makegaris(p1,p2) dari p1 dan p2 yang dibaca */

void tulisgaris(garis l);
/* nilai p ditulis ke layar dg format ((x,y),(x,y)) */

/* kelompok operasi relasional terhadap garis */
boolean garisEQ(garis l1,garis l2);
/* mengirimkan true jika l1=l2 */
/* l1 dikatakan = l2 jika titik awal l1 = titik awal l2*/
/* dan titik akhir l1=titik akhir l2 */

boolean garisNEQ(garis l1,garis l2);
/* mengirimkan true jika l1 tidak sama dengan l2 */
/* negasi dari fungsi EQ */

/* kelompok menentukan dimana l berada */

boolean isgarisonsbx(garis l);
/* menghasilkan true jika l terletak pada sumbu x */

boolean isgarisonsby(garis l);
/* menghasilkan true jika l terletak pada sumbu y */

int kuadrangaris(garis l);
/* menghasilkan kuadran dari l (dimana paw dan pakh berada) */
/* precondition: l tdk terletak pd slh satu sumbu */

/* kelompok predikat lain */
boolean isgaristegaklurus(garis l,garis l1);
/* menghasilkan true jika l tegak lurus l1 */

boolean isgarissejajar(garis l,garis l1);
/* menghasilkan true jika l sejajar terhadap l1 */

/* kelompok operasi lain */

garis g_mirrorof(garis l,boolean sbx,boolean sby);
/* menghasilkan salinan l yang dicerminkan */
/* tergantung nilai sbx dan sby */
/* jika sbx bernilai true, maka dicerminkan terhadap sb x */
/* jika sby bernilai true, maka dicerminkan terhadap sb y */

float panjanggaris(garis l);
/* menghitung panjang garis l */

float arahgaris(garis l);
/* menghitung arah dari garis l*/
/* yaitu sudut yang dibentuk dengan sumbu x */

float sudutgaris(garis l);
/* menghasilkan sudut perpotongan antara l dengan l */
/* precondition : l tidak sejajar dg l dan tidak berimpit dg l */

void gesergaris(garis *l,int deltax,int deltay);
/*I.S : l terdefinisi */
/*F.S : l digeser sebesar deltax dan ordinatnya sebesar delta y*/
/*paw dan pakh digeser*/

void mirrorgaris(garis *l,boolean sbx,boolean sby);
/* I.S : l terdefinisi */
/* F.S : l dicerminkan tergantung nilai sbx atau sby */
/* jika sbx true maka dicerminkan thd sumbu x */
/* jika sby true maka dicerminkan thd sumbu y */

void g_putar(garis *l,float sudut);
/* I.S : l terdefinisi */
/* F.S : l diputar sebesar sudut derajat : paw dan pakh diputar */

#endif


GARIS.C


#ifndef GARIS_c
#define GARIS_c
#include .h>
#include
#include "BOOLEAN.h"
#include "GARIS.h"


void makegaris(point p1,point p2,garis &l){
l.paw=p1;
l.pakh=p2;
};

point getpaw(garis l){
return l.paw;
};

point getpakh(garis l){
return l.pakh;
};


void bacagaris(garis &l){
printf("point awal(x) : ");scanf("%d",&l.paw.x);
printf("point awal(y) : ");scanf("%d",&l.paw.y);
printf("point akhir(x) : ");scanf("%d",&l.pakh.x);
printf("point akhir(y) : ");scanf("%d",&l.pakh.y);
};

void tulisgaris(garis l){
printf("((%d,%d)",l.paw.x,l.paw.y);
printf(",(%d,%d))",l.pakh.x,l.pakh.y);
};

boolean garisEQ(garis l1,garis l2){
if(l1.paw.x==l2.paw.x&&
l1.paw.y==l2.paw.y&&
l1.pakh.x==l2.pakh.x&&
l1.pakh.y==l2.pakh.y)
return true;
else
return false;
};

boolean garisNEQ(garis l1,garis l2){
if (!garisEQ(l1,l2))
return true;
else
return false;
};

boolean isgarisonsbx(garis l){
if(l.paw.y==l.pakh.y==0)
return true;
else
return false;
};

boolean isgarisonsby(garis l){
if(l.paw.x==l.pakh.x==0)
return true;
else
return false;
};

int kuadrangaris(garis l){
if(l.paw.x>0 && l.pakh.x>0 && l.paw.y>0 && l.pakh.y>0)
return 1;
else
if(l.paw.x<0>0 && l.pakh.y>0)
return 2;
else
if(l.paw.x<0 && l.pakh.x<0 && l.paw.y<0 && l.pakh.y<0)
return 3;
else
if(l.paw.x>0 && l.pakh.x>0 && l.paw.y<0 && l.pakh.y<0)
return 4;
else
return 0;
};

boolean isgaristegaklurus(garis l1,garis l2){
float m1=(l1.paw.y-l1.pakh.y)/(l1.paw.x-l1.pakh.x);
float m2=(l2.paw.y-l2.pakh.y)/(l2.paw.x-l2.pakh.x);
if (-m1==1/m2)
return true;
else
return false;
};

boolean isgarissejajar(garis l1,garis l2){
float m1=(l1.paw.y-l1.pakh.y)/(l1.paw.x-l1.pakh.x);
float m2=(l2.paw.y-l2.pakh.y)/(l2.paw.x-l2.pakh.x);
if (m1==m2)
return true;
else
return false;
};


garis g_mirrorof(garis l,bool sbx,bool sby){
if(sbx){
l.paw.y=-l.paw.y;
l.pakh.y=-l.pakh.y;
}
if(sby){
l.paw.x=-l.paw.x;
l.pakh.x=-l.pakh.x;
}
return l;
};

float panjanggaris(garis l){
float a=l.paw.x-l.pakh.x;
float b=l.paw.y-l.pakh.y;
return sqrt(a*a+b*b);
};

float arahgaris(garis l){
float a=l.paw.x-l.pakh.x;
float b=l.paw.y-l.pakh.y;
return atan(b/a);
};

float sudutgaris(garis l1,garis l2){
float sudut;
if(!isgarissejajar(l1,l2) || garisNEQ(l1,l2))
sudut=(arahgaris(l1)-arahgaris(l2));
return sudut;
};

void gesergaris(garis &l,int deltax,int deltay){
l.paw.x+=deltax;
l.paw.y+=deltay;
l.pakh.x+=deltax;
l.pakh.y+=deltay;
};

void mirrorgaris(garis &l,bool sbx,bool sby){
if(sbx){
l.paw.y=-l.paw.y;
l.pakh.y=-l.pakh.y;
}
if(sby){
l.paw.x=-l.paw.x;
l.pakh.x=-l.pakh.x;
}
};

void g_putar(garis &l,float sudut){
float sdt=atan(l.paw.y/l.paw.x);
float pjg=l.paw.y/sin(sdt);
l.paw.y=pjg*sin(sdt+sudut);
l.paw.x=pjg*cos(sdt+sudut);

sdt=atan(l.pakh.y/l.pakh.x);
pjg=l.pakh.y/sin(sdt);
l.pakh.y=pjg*sin(sdt+sudut);
l.pakh.x=pjg*cos(sdt+sudut);
};

#endif




ADT Point (revisi)

BOOLEAN.H

#ifndef __boolean__
#define __boolean__
#define true 1
#define false 0
#define boolean unsigned char
#endif


POINT.H


/* file : point.h */
/* ADT point */

#ifndef point_h
#define point_h
#include "boolean.h"
#include "POINT.c"


/* definisi prototipe primitif */
/*** konstruktor membentuk point ***/
point makepoint(int x,int y);
/* membentuk sebuah point dari komponen-komponennya */

/*** selektor point ***/
int getabsis (point p);
/* mengirimkan komponen absis dari p */

int getordinat(point p);
/* mengirimkan komponen ordinat dari p */

/*** destruktor/dealokator:tidak perlu ***/
/*** set nilai komponen point ***/
void setabsis(point *p,int newx);
/* men-set komponen absis dari p */

void setordinat(point *p,int newy);
/* men-set komponen ordinat dari p */

/* kelompok interaksi dengan I/O device, baca/tulis */
void bacapoint(point *p);
/* bacapoint(x,y,p) membentuk p dari x dan y yang dibaca */

void tulispoint(point p);
/* nilai p ditulis ke layar dg format (X,Y) */

/* kelompok operasi aritmatika terhadap byte */
point pluspoint(point p1,point p2);
/* menghasilkan salinan p yang berisi p1+p2 */
/* melakukan operasi penjumlahan vektor */

point minuspoint(point p1,point p2);
/* menghasilkan p1-p2 */

/*** kelompok operasi relasional terhadap point ***/
boolean EQ(point p1,point p2);
/* mengirimkan true jika p1=p2 */

boolean NEQ(point p1,point p2);
/* mengirimkan true jika p1 tidak sama dengan p2 */

boolean LT(point p1,point p2);
/* mengirimkan true jika p1/* definisi lebih kecil:lebih "kiri-bawah" dalam bidang kartesian */

boolean GT(point p1,point p2);
/* mengirimkan true jika p1>p2 */
/* definisi lebih besar:lebih "kanan-atas" dalam bidang kartesian */

/* kelompok menentukan dimana p berada */
boolean isorigin(point p);
/* menghasilkan true jika p adalah titik origin */

boolean isonsbx(point p);
/* menghasilkan true jika p terletak pada sumbu x */

boolean isonsby(point p);
/* menghasilkan true jika p terletak pada sumbu y */

int kuadran(point p);
/* menghasilkan kuadran dari p: 1,2,3,atau 4 */
/* precondition: p bukan titik origin dan p tdk terletak pd slh satu sumbu */

/* kelompok operasi lain terhadap type */
point nextx(point p);
/* mengirim salinan p dengan absis ditambah satu */

point nexty(point p);
/* mengirim salinan p dengan ordinat ditambah satu */

point plusdelta(point p,int deltax,int deltay);
/* mengirim salinan p yang absisnya = absis(p)+deltax dan */
/* ordinatnya = ordinat(p)+deltay */

point mirrorofpoint(point p,boolean sbx,boolean sby);
/* menghasilkan salinan p yang dicerminkan */
/* tergantung nilai sbx dan sby */
/* jika sbx bernilai true, maka dicerminkan terhadap sb x */
/* jika sby bernilai true, maka dicerminkan terhadap sb y */

float jarak0(point p);
/* menghitung jarak p ke (0,0) */

void geserpoint(point *p,int deltax,int deltay);
/*I.S : p terdefinisi */
/*F.S : p digeser sebesar deltax dan ordinatnya sebesar delta y*/

void geserpointkesbx(point *p);
/* I.S : p terdefinisi */
/* F.S : p di sumbu x dg absis = absis semula */
/* proses : tergeser ke sumbu x */
/* contoh : jika koordinat semula(9,9) menjadi (9,0)*/

void geserpointkesby(point *p);
/* I.S : p terdefinisi */
/* F.S : p di sumbu y dg absis = absis semula */
/* proses : tergeser ke sumbu y */
/* contoh : jika koordinat semula(9,9) menjadi (0,9)*/


void mirrorpoint(point *p,boolean sbx,boolean sby);
/* I.S : p terdefinisi */
/* F.S : p dicerminkan tergantung nilai sbx atau sby */
/* jika sbx true maka dicerminkan thd sumbu x */
/* jika sby true maka dicerminkan thd sumbu y */


void putarpoint(point *p,float sudut);
/* I.S : p terdefinisi */
/* F.S : p diputar sebesar sudut derajat */

#endif



POINT.C


#include
#include
#include "BOOLEAN.h"

/* definisi ADT point */
typedef struct
{

int x; /* absis */
int y; /* ordinat */
} point;


point makePoint(int x,int y)
{
point p;
p.x=x;

p.y=y;
return p;
}

int getabsis(point p)
{
return(p.x);
}

int getordinat(point p)
{
return(p.y);
}

void setabsis(point *p,int newx)

{
scanf("%d",&newx);
(*p).x=newx;
}

void setordinat(point *p,int newy)
{
scanf("%d",&newy);
(*p).y=newy;
}

void bacapoint(point *p)
{


int x,y;
printf("Nilai x: ");
scanf("%d",&x);
printf("Nilai y: ");
scanf("%d",&y);
*p=makePoint(x,y);
}

void tulispoint(point p)
{
printf("(%d,%d)",p.x,p.y);
}

point pluspoint(point p1, point p2)
{
point p;
p.x=p1.x+p2.x;
p.y=p1.y+p2.y;
return p;
}

point minuspoint(point p1, point p2)
{
point p;
p.x=p1.x-p2.x;
p.y=p1.y-p2.y;
return p;
}



/*perkalian skalar----*/

boolean EQ(point p1, point p2)
{
if((p1.x==p2.x)&&(p1.y==p2.y))
return true;
else
return false;
}

boolean NEQ(point p1, point p2)
{
if((p1.x!=p1.y)&&(p2.x!=p2.y))
return true;
else
return false;
}

boolean LT(point p1, point p2)
{
if((p1.x return true;
else
return false;
}

boolean GT(point p1, point p2)
{
if((p1.x>p1.y)&&(p1.y>p2.y))
return true;
else
return false;
}

boolean isorigin(point p)
{
if((p.x==0)&&(p.y==0))
return true;
else
return false;
}

boolean isonsbx(point p)
{
if(p.x==0)
return true;
else
return false;
}

boolean isonsby(point p)
{
if(p.y==0)
return true;
else
return false;
}

int kuadran(point p)
{
if((p.x>0)&&(p.y>0))
return 1;
else
{
if((p.x>0)&&(p.y<0))
return 4;
else
{
if((p.x<0)&&(p.y>0))
return 2;
else
return 3;
}
}
}


point nextx(point p)
{
p.x=p.x+1;
return p;
}
point nexty(point p)
{
p.y=p.y+1;
return p;
}

point plusdelta(point *p,int deltax, int deltay)
{
(*p).x=(*p).x+deltax;
(*p).y=(*p).y+deltay;
return *p;
}

point mirrorofpoint(point p,boolean sbx,boolean sby)
{
if (sbx)
p.y=-1*p.y;
if (sby)
p.x=-1*p.x;
return p;
}

float jarak0(point p)
{
float hasil;

hasil=sqrt((p.x*p.x)+(p.y*p.y));
return hasil;
}




void geserpoint(point *p,int deltax,int deltay)
{
(*p).x=(*p).x+deltax;
(*p).y=(*p).y+deltay;

}

void geserpointkesbx(point *p)
{
(*p).y=0;
(*p).x=(*p).x;
}

void geserpointkesby(point *p)
{
(*p).x=0;
(*p).y=(*p).y;
}

void mirrorpoint(point *p,boolean SbX, boolean SbY)
{
if (SbX)
(*p).y=-1*(*p).y;
if (SbY)
(*p).x=-1*(*p).x;
}

void putarpoint(point *p,float sudut)
{
float phit;
phit=sqrt(((*p).x*(*p).x)+((*p).y*(*p).y));
(*p).x=phit*cos(sudut+90);
(*p).y=phit*sin(sudut);
}


MAINPOINT.CPP

#include
#include
#include "BOOLEAN.h"
#include "POINT.h"

main()
{
int x,y,delx,dely,pilih;
float sudut;
char pil;
point p,p1,p2,ptemp;
boolean sbx,sby;

do{

printf("1.Masukkan nilai suatu Point");
printf("\n2.Ubah nilai absis");
printf("\n3.Ubah nilai ordinat");
printf("\n4.Operasi penambahan");
printf("\n5.Operasi pengurangan");
printf("\n6.Membandingkan nilai Point");
printf("\n7.Menentukan letak titik");
printf("\n8.Tambah nilai absis sebesar 1");
printf("\n9.Tambah nilai ordinat sebesar 1");
printf("\n10.Tambah nilai absis dan ordinat (nilai sembarang)");
printf("\n11.Menentukan jarak point dari sumbu pusat");
printf("\n12.Pencerminan");
printf("\n13.Rotasi");
printf("\n14.Geser point");
printf("\n15.Geser point ke sumbu x");
printf("\n16.Geser point ke sumbu y");
printf("\n17.Keluar");
printf("\nPiih menu: ");
scanf("%d",&pilih);


switch (pilih)
{

case 1: bacapoint(&p);
tulispoint(p);
getch();
break;

case 2:
bacapoint(&p);
printf("Masukan nilai absis baru: ");
setabsis(&p,x);
tulispoint(p);
getch();
break;
case 3: bacapoint(&p);
printf("Masukan nilai ordinat baru: ");
setordinat(&p,y);
tulispoint(p);
getch();
break;

case 4: bacapoint(&p1);
bacapoint(&p2);
ptemp=pluspoint(p1,p2);
printf("Jumlah pertambahan: ");
tulispoint(ptemp);
getch();
break;

case 5: bacapoint(&p1);
bacapoint(&p2);
ptemp=minuspoint(p1,p2);
printf("Jumlah pengurangan: ");
tulispoint(p);
getch();
break;



case 6: bacapoint(&p1);
bacapoint(&p2);
if (EQ(p1,p2))
printf("\nNilai kedua point sama");
if (NEQ)
printf("\nNilai kedua point tidak sama");
if (LT(p1,p2))
printf("\nP1 kurang dari p2");
if (GT(p1,p2))
printf("\nP1 lebih dari p2");
getch();
break;

case 7: bacapoint(&p);
if (isorigin(p))
printf("Point ada pada sumbu pusat");
if (isonsbx(p))
printf("\nPoint ada pada sumbu x)");
if (isonsby(p))
printf("\nPoint ada pada sumbu y");
printf("\nPoint ada di kuadran: %d",kuadran(p));
getch();
break;

case 8: bacapoint(&p);
nextx(p);
tulispoint(p);
getch();
break;


case 9: bacapoint(&p);
nexty(p);
tulispoint(p);
getch();
break;

case 10: bacapoint(&p);
printf("Geser x: ");
scanf("%d",&delx);
printf("Geser y: ");
scanf("%d",&dely);
plusdelta(&p,delx,dely);
tulispoint(p);
getch();
break;

case 11: bacapoint(&p);
printf("Jarak point ke sumbu pusat: %.3f",jarak0(p));
getch();
break;



/*case 12: bacapoint(&p);
printf("Cerminkan ke sumbu x atau y: |x/y| ");
scanf("%s",&pil);
if (pil=='y')
{sby=true;
sbx=false;}
else
{sbx=true;
sby=false;}
mirrorofpoint(&p,sbx,sby);
tulispoint(p);
break;*/ /*<-(yang pencerminan error,saya ga ngerti dimana erronya)*/

case 13: bacapoint(&p);
printf("Masukan besar sudut perputaran: ");
scanf("%f",&sudut);
putarpoint(&p,sudut);
tulispoint(p);
getch();
break;

case 14: bacapoint(&p);
printf("Geser point x: ");
scanf("%d",&delx);
printf("Geser point y: ");
scanf("%d",&dely);
geserpoint(&p,delx,dely);
tulispoint(p);
getch();
break;

case 15: bacapoint(&p);
geserpointkesbx(&p);
tulispoint(p);
getch();
break;

case 16: bacapoint(&p);
geserpointkesby(&p);
tulispoint(p);
getch();
break;

case 17: break;
default : printf("salah input"); break;}
}while ((pilih>0)&&(pilih<18 ));

return 0;
}