Hatrack River Forum: C++ Array Implementation of the Ordered List ADT

This is topic C++ Array Implementation of the Ordered List ADT in forum Books, Films, Food and Culture at Hatrack River Forum.

To visit this topic, use this URL:
http://www.hatrack.com/ubb/main/ultimatebb.php?ubb=get_topic;f=2;t=047466

Posted by Blayne Bradley (Member # 8565) on :

Okay my teacher gave me a main.cpp and a header file orderedlist.h,

I comile the code and run it and my compile errors are unresolved externals, my assignments I believe is essentally fill-in-the-blanks and create the actual functions being called.

here's main;

code:

// Test of an array implementation of the OrderedList class

#include <cassert>
#include <cstring>
#include <iostream>
#include "OrderedList.h"

using namespace std;

void main ()
{
    Info infos[] = 
    {
        { "Jones",    "John", 40000 },
        { "Smith",    "Sam",  45000 },
        { "Tremblay", "Tina", 50000 },
        { "Nguyen",   "Jean", 55000 },
    };

    OrderedList list;
    assert( list.IsEmpty() );
    assert( ! list.IsFull() );
    assert( list.Insert( 13, infos[0] ) );
    assert( ! list.IsEmpty() );
    assert( ! list.Insert( 13, infos[1] ) );
    assert( list.Size() == 1 );
    assert( ! list.Delete( 10 ) );
    assert( list.Delete( 13 ) );
    assert( list.IsEmpty() );
    assert( list.Insert( 13, infos[0] ) );
    assert( list.Insert(  9, infos[1] ) );
    assert( list.Insert( 11, infos[2] ) );
    assert( list.Insert( 15, infos[3] ) );
    
    int  key;
    Info info;

    assert( ! list.Search( 7, info ) );
    assert(   list.Search( 9, info ) );
    assert( strcmp(info.firstname, infos[1].firstname) == 0 );
    assert( ! list.Search( 12, info ) );
    assert(   list.Search( 13, info ) );
    assert( strcmp(info.firstname, infos[0].firstname) == 0 );
    assert(   list.Search( 15, info ) );
    assert( strcmp(info.firstname, infos[3].firstname) == 0 );
    assert( ! list.Search( 17, info ) );

    list.Reset();
    list.Advance( key, info );
    assert( key == 9 );
    assert( strcmp(info.firstname, infos[1].firstname) == 0 );
    list.Advance( key, info );
    assert( key == 11 );
    assert( strcmp(info.firstname, infos[2].firstname) == 0 );
    list.Advance( key, info );
    assert( key == 13 );
    assert( strcmp(info.firstname, infos[0].firstname) == 0 );
    list.Advance( key, info );
    assert( key == 15 );
    assert( strcmp(info.firstname, infos[3].firstname) == 0 );

    assert( ! list.Delete( 7 ) );
    assert(   list.Delete( 9 ) );
    assert( ! list.Delete( 12 ) );
    assert(   list.Delete( 13 ) );
    assert(   list.Delete( 15 ) );
    assert( ! list.Delete( 17 ) );
    assert( list.Size() == 1 );

    list.Reset();
    list.Advance( key, info );
    assert( key == 11 );
    assert( strcmp(info.firstname, infos[2].firstname) == 0 );
 
    assert( list.Delete( 11 ) );
    assert( list.IsEmpty() );

    assert( ! list.Search( 1, info ) );
    assert( list.Insert( 1, info ) );
    assert( ! list.Search( 0, info ) );
    assert(   list.Search( 1, info ) );
    assert( ! list.Search( 2, info ) );
    assert( list.Insert( 3, info ) );
    assert( ! list.Search( 0, info ) );
    assert(   list.Search( 1, info ) );
    assert( ! list.Search( 2, info ) );
    assert(   list.Search( 3, info ) );
    assert( ! list.Search( 4, info ) );
    assert( list.Insert( 5, info ) );
    assert( ! list.Search( 0, info ) );
    assert(   list.Search( 1, info ) );
    assert( ! list.Search( 2, info ) );
    assert(   list.Search( 3, info ) );
    assert( ! list.Search( 4, info ) );
    assert(   list.Search( 5, info ) );
    assert( ! list.Search( 6, info ) );

    {
        OrderedList list;
        Info info = { "", 0, 0 };

        for ( int i = 0; i < MAX_SIZE_ORDERED_LIST - 1; i++ ) {
            assert( list.Insert( i, info ) );
        }
        assert( ! list.IsFull() );
        assert( list.Insert( MAX_SIZE_ORDERED_LIST - 1, info ) );
        assert ( list.IsFull() );
    }  

    {
        OrderedList list;
        Info info = { "", 0, 0 };
        int key ;

        assert( list.Insert( 20, info ) );
        assert( list.Insert( 22, info ) );
        assert( list.Insert( 24, info ) );
        assert( list.Insert( 19, info ) );
        assert( list.Insert( 21, info ) );
        assert( list.Insert( 23, info ) );
        assert( list.Insert( 25, info ) );
        list.Reset();
        for ( int i = 19; i < 26; i++ ) {
            list.Advance( key , info );
            assert( key == i );
        }
    }

    cout << "Completed test Ordered List." << endl;

    char dummy;
    cin >> dummy;
}

and heres the header.

code:

#ifndef ORDERED_LIST_H
#define ORDERED_LIST_H

const int MAX_SIZE_ORDERED_LIST = 20;
const int MAX_LENGTH_NAME       = 20;

struct Info
{
    char   lastname[MAX_LENGTH_NAME+1];
    char   firstname[MAX_LENGTH_NAME+1];
    double salary;
};

class OrderedList
{
public:    
    OrderedList();
    bool Search( /* in */ int key, /* out */ Info& info );
    bool Insert( /* in */ int key, /* in  */ Info  info );
    bool Delete( /* in */ int key );
    int  Size() const;
    void Reset();
    void Advance( /* out */ int& key, /* out */ Info& info );
    bool IsEmpty( void ) const;
    bool IsFull( void ) const;
private:
    struct Item
    {
        int  key;
        Info info;
    };
    Item items[MAX_SIZE_ORDERED_LIST];
    int  size;
    int  current;
};

#endif

Now here's the thing I believe the assignment (which just says Implement the Ordered List ADT using a array implementation) is to make another .cpp file and fill in the functions there.

I'm not entirely sure how functions are called inbetween .cpp files (linking?) like if a function protype is made in the header and called in main.cpp do I simply finish the job and define the function in the separate .cpp file and if so how do I link files?

Posted by Chanie (Member # 9544) on :

Go talk to your TA. She should be able to help you understand how this works.

Posted by Will B (Member # 7931) on :

Write the body of these functions either in orderedlist.cpp; or if it's short enough, make it inline, in orderedlist.h.

Whatever you were already doing to create an executable program, do it in this case as well, and it'll do the linking.

Posted by Nighthawk (Member # 4176) on :

Lord I've never seen so many "assert" calls in my life.

Does the code inside of the "assert" get executed when you compile a RELEASE version? I use to remember that MFC's equivalent (DEBUG) would effectively null out the statement in release, which means that the code never gets compiled or executed.

Really bad practice, if you ask me.

Posted by fugu13 (Member # 2859) on :

Its an assignment. The asserts both indicate desired behavior of the API to the student and check his code's compliance with it.

Posted by Will B (Member # 7931) on :

Yeah, it's a driver -- there shouldn't *be* a release version.