Implementing abstract data types

Posted on 1997-09-22
Last Modified: 2012-06-27

I am trying to figure out how to do this problem and I don't have the faintest idea what to do. I need a few hints or advice on how to implement this reservation system. It suppose to use some sort of array system and if there is an easier way to handle this ... that will be great!

Implement the following abstract datatype reservation system (RS) that provides
the following 7 operations.

create: --> RS
Sem.: starts the reservation system

create-new-event: RSxEVNRxNAT -> RS
Sem.: creates a new event with NAT seats with a given event-number

cancel-event: RSxEVNR -> RS
Sem.: cancels the event with the given number

reserve-seat: RSxEVNRxSSN -> RS
Sem.: reserves a seat for a person with a given ssn for a given event

remove-per-res: RSxSSN -> RS
Sem.: removes the all reservation of a given person

get-ev-res: RSxEVNR -> set-of(SSN)
Sem.: gives the set reservations for a given event,

get-pers-res: RSxSSN -> set-of(EVNR)
Sem.: gives the set of events, a person has reservations for.

get-events: RS -> set-of(EVNR)
Sem.: returns the set of the currently defined events

In the above, the following types have the following meaning:

EVNR are numbers between 1 and 999999999 used to identify events; eventnumbers
are not necessarily consecutive.

NAT represents a positive integer between 1 and 1000 that is used to specify
the number of available seats for the event.

SSN represents social security numbers, which are used to identify persons that
made reservations for a particular event; ssn have to be numbers between
100000000 and 999999999.

Question by:blackbeauty
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2

Accepted Solution

yonat earned 200 total points
ID: 1170252
First, the definition of the ADT:

#include <set>
using namespace std;

class ReservationSystem // RS
    typedef unsigned long EVNR;
    typedef unsigned int  NAT;
    typedef unsigned long SSN;

    virtual void create() = 0;
    virtual void create_new_event(EVNR e, NAT n) = 0;
    virtual void reserve_seat(EVNR e, SSN s) = 0;
    virtual void remove_per_res(SSN s) = 0;
    virtual set<SSN> get_ev_res(EVNR e) = 0;
    virtual set<EVNR> get_pers_res(SSN s) = 0;
    virtual set<EVNR> get_events() = 0;

And here is a simple implementation:

#include <map>
using namespace std;

class SimpleReservationSystem : public ReservationSystem
    struct Seats {
        NAT total;
        set<SSN> reserved;

    map<EVNR, Seats> itsEvents;

    typedef map<EVNR, Seats>::iterator Iter;

    virtual void create() {}

    virtual void create_new_event(EVNR e, NAT n)
        itsEvents[e].total = n;

    virtual void reserve_seat(EVNR e, SSN s)
        Seats& seats = itsEvents[e];
        if ( > seats.reserved.size())

    virtual void remove_per_res(SSN s)
        for( Iter i = itsEvents.begin();
             i != itsEvents.end();
             ++i )

    virtual set<SSN> get_ev_res(EVNR e)
        return itsEvents[e].reserved;

    virtual set<EVNR> get_pers_res(SSN s)
        set<EVNR> ret;
        for( Iter i = itsEvents.begin();
             i != itsEvents.end();
             ++i )
            if (itsEvents.end() != (*i).second.reserved.find(s))
        return ret;

    virtual set<EVNR> get_events()
        set<EVNR> ret;
        for( Iter i = itsEvents.begin();
             i != itsEvents.end();
             ++i )
        return ret;


Since it the indentation sometimes gets mixed up in experts-exchange, I've put the source also at

Please tell me if you're having any problems, since the implementation uses STL, which is problematic for some compilers.

Author Comment

ID: 1170253
This is a nice answer to my questions but I am not understanding the 'virutal' and 'set.' I am still a beginner of data structures but I need explanation of 'virtal set.' I don't think I am that far ahead in C++.  And #include<set> and #include<map>...are those in C compiler library? What if I created some datas to go with this program such as:
create-new-event:  10001  200
create-new-event:   9999  10001
create-new-event:     23  100
create-new-event:     22  150
create-new-event:     33  20
cancel-event:         23
cancel-event:         16
create-new-event:     44  10
create-new-event:     55  5
reserve-seat:       8888  555555555
reserve-seat:          1  6666666666
reserve-seat:         55  123400000
reserve-seat:         55  223400000
reserve-seat:         55  323400000
reserve-seat:          1  123456780
reserve-seat:         55  423400000
reserve-seat:         55  223400000
reserve-seat:         11  223400000
reserve-seat:         55  523400000
reserve-seat:         55  100000004
reserve-seat:         55  100000002
reserve-seat:         11  200000001
reserve-seat:         11  200000002
reserve-seat:         11  200000003
reserve-seat:         11  200000004
reserve-seat:          1  123400000
reserve-seat:          1  123456781
reserve-seat:         22  123456789
get-pers-res:             123400000
get-pers-res:             223400000
remove-per-res:           523400000
remove-per-res:           123400000
remove-per-res:           200000005
cancel-event:          1
get-pers-res:             123400000
get-pers-res:             200000001
get-ev-res:           11
get-ev-res:           55
get-pers-res:         11
get-pers-res:         33

Is there a simpler way to this implementing using some sort of linked arrays or the polynomial system?  

Expert Comment

ID: 1170254
<set> and <map> are standard headers. They declare the templates set and map, which are a part of the Standard Template Library (STL). STL is a part of the standard library.
It is easier to use standard ready maid containers, then to write your own, and that is why I used them.

The 'virtual' keyword has to do with inheritance and polymorphism. From your comment I gather that you haven't learned that yet, so we can ignore it: Ignore the class ReservationSystem and just use SimpleReservationSystem. Also, remover the
: public ReservationSystem
from the declaration and remove all the 'virtual's.
This will be just as good for your purposes.  have updated the web page to reflect this.

About the data: Are you sure that this is the way you want the ADT to be used? If so, I suggest you write a small parser the will parse the input file into calls to ReservationSystem.

Since this is getting a little long, I suggest we use e-mail for further discussion. You can mail me at .

Author Comment

ID: 1170255
Good job on explaining my program.

Featured Post

Secure Your Active Directory - April 20, 2017

Active Directory plays a critical role in your company’s IT infrastructure and keeping it secure in today’s hacker-infested world is a must.
Microsoft published 300+ pages of guidance, but who has the time, money, and resources to implement? Register now to find an easier way.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
c++ how to tell if the progra is ctl or mfc atl ect 6 99
computer science syllabus 3 103
Precision Problem in C++ 7 52
Autosar OS Multicore Share Resources confusion ? 2 111
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

730 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question