Selasa, 01 November 2016

ADT Queue with Dynamic Allocation

Written by   on   in , , , ,   with Tidak ada komentar
Artikel ini berisi tentang :
  • Penjelasan definisi ADT
  • Komponen dan fungsi apa saja yang terdapat pada ADT
  • Contoh kodingnya dalam bahasa C
  • Penjelasan dari kodingnya
  • Contoh bagaimana penggunaannya untuk menyelesaikan suatu permasalah tertentu
Definisi ADT
Tipe data abstrak (Abstract Data Type - ADT) adalah tipe data yang diatur menggunakan struktur data tertentu sehingga "spesifikasi data" dan "spesifikasi operasi" terpisah dari “representasi” dan “implementasinya” (Horowitz, Sahni dan Freed, 1993,pp1-100). Pengguna ADT (user), hanya perlu memperhatikan spesifikasi data dan operasi, tidak perlu memperhatikan representasi dan implementasinya. Namun seorang perancang program (program designer) perlu mengetahui implementasinya. Antara user dan pro

ADT (Abstract Data Type) atau Tipe Data Bentukan :
- Bahasa C memiliki tipe data numerik dan karakter (seperti integer, float, char dan lainlain).
Bagaimana jika kita ingin membuat tipe data baru?
- ADT adalah tipe data yang dibuat oleh programmer sendiri yang memiliki suatu nama
tertentu.
- ADT dapat berupa tipe data dasar namun diberi nama baru atau berupa kumpulan tipe
data berbeda yang diberi nama baru.
- Untuk pembuatan ADT digunakan keyword typedef

Komponen dan Fungsi ADT Queue

Tipe Data Abstrak ‘antrian’ (Queue FIFO (First In First Out) system) berisi data nilai dalam antrian ( ex. (2, 5, 4, 1) ).

File terdiri dari :
  1. main.c
  2. driver.c
  3. header.h
Header yang tersedia :

typedef int infotype; //Tipe data bentukan bernama infotype bertipe int
typedef int address; //Tipe data bentukan bernama address bertipe int
typedef struct
{
    infotype *T; //Berfungsi sebagai wadah penyimpan nilai di posisi tertentu
    address HEAD; //Berfungsi sebagai posisi nilai awal
    address TAIL; //Berfungsi sebagai posisi nilai terakhir yang termasukkan
    int MaxEl; //Berfungsi sebagai total posisi (elemen) yang bisa dimasukkan
}Queue; //Tipe data bentukan bernama Queue bertipe struct

Fungsi yang tersedia :

  • void CreateEmpty(Queue *Q, int Max);
  • boolean IsEmpty(Queue Q);
  • boolean IsFull(Queue Q);
  • int NBElmt(Queue Q);
  • void DeAlokasi(Queue *Q);
  • void Add(Queue *Q, infotype X);
  • void Del(Queue *Q, infotype *X);
  • void PrintfQueue(Queue Q);
  • void AddPriority(Queue *Q);


Contoh source code bahasa c

/*file : main.c*/
#include <stdio.h>
#include <stdlib.h>
#include "header.h"

int main()
{
    Queue Saya;
    int Callista;
    int batas;
    int input;
    int angka;
    printf("Masukkan Batas Maksimal Queue : "); scanf("%d", &batas);
    CreateEmpty(&Saya, batas);
    input = 0;
    while(input != 9)
    {
        system("pause");
        system("cls");
        printf("1. Masukkan Angka Untuk dimasukkan");
        printf("\n2. Mengecek keadaan apakah Queue masih kosong (Nil)");
        printf("\n3. Mengecek keadaan apakah Queue sudah penuh (Full)");
        printf("\n4. Menghapus angka pada posisi pertama (HEAD)");
        printf("\n5. Mengirimkan banyaknya elemen yang telah dimasukkan");
        printf("\n6. Print Queue");
        printf("\n7. De-alokasi Memori Queue  //Posisi HEAD = TAIL = MAX = 0");
        printf("\n8. Menampilkan Posisi HEAD, TAIL, MAX");
        printf("\n9. Keluar Program");
        printf("\n100. Add Priority (LIFO) ");
        printf("\n\nMasukkan Pilihan : "); scanf("%d", &input);
        switch(input)
        {
            case 1:
                if(IsFull(Saya) == false)
                {
                    printf("Masukkan Angka Untuk diAdd : ");scanf("%d", &angka);
                    Add(&Saya, angka);
                }
                else
                    printf("Queue sudah Full\n\n");
                break;
            case 2:
                printf("IsEmpty : %s\n\n", IsEmpty(Saya)?"True (Queue masih Nil)":"False (Queue tidak Nil)");
                break;
            case 3:
                printf("IsFull : %s\n\n", IsFull(Saya)?"True (Queue sudah Full)":"False (Queue tidak Full)");
                break;
            case 4:
                Del(&Saya, &Callista);
                break;
            case 5:
                printf("NBElmt : %d\n\n", NBElmt(Saya));
                break;
            case 6:
                PrintfQueue(Saya);
                break;
            case 7:
                DeAlokasi(&Saya);
                break;
            case 8:
                printf("Pos HEAD : %d, Pos TAIL : %d, Pos MAX : %d\n", Saya.HEAD, Saya.TAIL, Saya.MaxEl);
                break;
            case 9:
                break;
            case 100:
                AddPriority(&Saya);
                break;
            default:
                printf("Pilihan Tidak Tersedia\n\n");
                break;
        }
    }
    return 0;
}

/*file : driver.c*/
#include "header.h"
void CreateEmpty(Queue *Q, int Max)
{
    Q->T = (int*)malloc((Max + 1) * sizeof(int));
    Q->HEAD = Nil;
    Q->TAIL = Nil;
    Q->MaxEl = Max;
}
boolean IsEmpty(Queue Q)
{
    return (Q.HEAD == Nil && Q.TAIL == Nil);
}
boolean IsFull(Queue Q)
{
    return (Q.TAIL == Q.MaxEl);
}
int NBElmt(Queue Q)
{
    return Q.TAIL;
}
void DeAlokasi(Queue *Q)
{
    free(&(*Q).T);
    Q->HEAD = Nil;
    Q->TAIL = Nil;
    Q->T=Nil;
    Q->MaxEl = Nil;
}
void Add(Queue *Q, infotype X)
{
    Q->HEAD = 1;
    Q->TAIL++;
    Q->T[Q->TAIL] = X;
}
void AddPriority(Queue *Q)
{
    int X;
    if(IsEmpty(*Q))
    {
        printf("Masukkan Angka Untuk diAdd : ");scanf("%d", &X);
        Add(&(*Q), X);
    }
    else if(IsFull(*Q))
        printf("Angka tidak bisa diAdd karena Queue penuh\n");
    else
    {
        printf("Masukkan Angka Untuk diAdd : ");scanf("%d", &X);
        int loop;
        loop = Q->TAIL;
        Q->TAIL++;
        while(loop >= Q->HEAD)
        {
            Q->T[loop + 1] = Q->T[loop];
            loop--;
        }
        Q->T[Q->HEAD] = X;
    }
}
void Del(Queue *Q, infotype *X)
{
    int loop;
    if(IsEmpty(*Q) == false)
    {
        *X = Q->T[Q->HEAD];
        Q->TAIL--;
        if(Q->TAIL == Nil)
            Q->HEAD = Nil;
        loop = 1;
        while(loop <= Q->TAIL)
        {
            Q->T[loop] = Q->T[loop + 1];
            loop++;
        }
        printf("Angka pada posisi Head sudah diDel\n\n");
    }
    else
        printf("Head tidak bisa dihapus, karena tidak ada Angka yang dimasukkan\n\n");
}
void PrintfQueue(Queue Q)
{
    if(IsEmpty(Q) == false)
    {
        printf("Queue : ");
        while (Q.HEAD != Q.TAIL)
        {
            printf("%d\t", Q.T[Q.HEAD]);
            Q.HEAD++;
        }
        printf("%d\n", Q.T[Q.TAIL]);
    }
    else
    {
        printf("Data masih Nil\n\n");
    }
}

/*file : header.h*/
//Kas Raygaputra Ilaga
//A11.2015.08977
//STRUKTUR DATA A11.4308
#ifndef HEADER_H_INCLUDED
#define HEADER_H_INCLUDED
#define boolean unsigned char
#define true 1
#define false 0
#define Nil 0
typedef int infotype;
typedef int address;
typedef struct
{
    infotype *T;
    address HEAD;
    address TAIL;
    int MaxEl;
}Queue;

//Prototypes
void CreateEmpty(Queue *Q, int Max);
boolean IsEmpty(Queue Q);
boolean IsFull(Queue Q);
int NBElmt(Queue Q);
void DeAlokasi(Queue *Q);
void Add(Queue *Q, infotype X);
void Del(Queue *Q, infotype *X);
void PrintfQueue(Queue Q);
void AddPriority(Queue *Q);
#endif // HEADER_H_INCLUDED


Penjelasan dari source code "driver.c"

FIFO SYSTEM


Contoh Kasus

Kemarin saat saya ada menghadiri kelas mata kuliah Sistem Operasi kelas unggulan. Pak Adhitya Nughraha menjelaskan tentang beberapa penjadwalan proses pada sistem. Disitu ada tentang Round Priority Scheduling. Dari sistem tersebut saya mendapatkan ide tentang nasabah bank prioritas yang memiliki tabungan milyaran, pasti akan dilayani langsung. jadi saya menambahkan sebuah fungsi untuk menambahkan data di depan (posisi awal) (LIFO Priority System).



DOWNLOAD PROGRAM DAN GAMBARAN DI EXCEL -> DOWNLOAD
Share:

0 komentar:

Posting Komentar