do-it-yourself linked list

[Darryl B]

I can not get anywhere on this project I'm tryin to do. I'm not
expecting any major help with this but any would be appreciated. The
assignment is attached. The problem I'm having is trying to set up the
class link and tel_list. I set up a class person with strings for
name, town, and number. I just don't know how to set up the classes w/
their methods (constructors and operations). I'm stuck on the
assignment operator and the add and delete operations. A little help
to get me going on this would be appreciated. Thanks!

Assignment:
This is a do-it-yourself linked list exercise. Create a class tel_list
which is a list of telephone subscribers. The data in each list entry
consists of a person's name, city (or town), and telephone number.
The data is to be maintained in order by the name of the person. It
is also to be kept in order by telephone number. The subscribers will
be linked in two different ways: in name order and in number order.
Set up a class link to store this data and some pointers to link (one
set of pointers joins people in alphabetical order, one set joins them
in numerical order) for each subscriber. Your class link should have
constructors (including a copy constructor), an assignment operator
(member), and accessors and mutators as you find them useful.

The data of class tel_list will consist of pointers to the first link
in each of the two orderings: one to the first link in alphabetical
order, one to the first link in numerical order. For methods it will
require a constructor (to make an initially empty list), add (which is
given a link to insert in the list), delete (which is given a person's
name and city and must remove their link from the list), and two
versions of print. One version prints the list in alphabetical order;
one prints it in numerical order.

You will also need two methods to find a link since you must be able
to search either list. It is possible to name them both find and
distinguish them by the nature of their arguments (the name in one
case, the telephone number in the other). To either delete a current
link or add a new link you need to search for the proper location in
both orderings.

You may set your list up with either forward links only for both
alphabetical and numerical ordering or you may set up forward and
backward links for both. Your choice clearly affects the way your
methods are implemented.

In the text class link is entirely private and declares list (and
listIterator) as friends. This doesn't seem to work with your
compiler (!) and the easiest solution is to make your class link
entirely public. Do not access links directly in your main program.
The only mention of links, their functions, and their data should be
in the class list and its members.


The program using these classes will consist of a loop reading
commands and data to manipulate the list. Some sample data (with
explanations) might be

A A - add to the list
Ferguson Orono 581-3930
A
Baron Orono 866-2103
..
..
..
P P – print the list (names, cities, and numbers) twice: once in

order by name, once in order by number
A
Mittkind Bangor 947-4397
D D – delete the node whose person and city follow
Pritchard Veazie
A
Xenophon Stillwater 827-9000


Remember, errors are possible. You might be told, for example, to
remove a node with a given name and city, but the person cannot be
found. Your program should take some reasonable action in these cases
and continue to the next piece of data.

Create any additional methods you find useful for these classes. The
data is in the data folder under the name tel_list.dat

Keep your list and link classes simple – you do not need anything near
the complexity of the library link and list classes. Links with only
forward pointers are sufficient, for example. You do not need a
separate iterator class. Any function that needs to move through the
list can have its own loop within itself.

[Jonathan Turkanis]

Re: do-it-yourself linked list


"Darryl B" <dbrag1@aol.com > wrote in message
news:d22e4ee8.0 403311914.3a4c1 40f@posting.goo gle.com...[color=blue]
> I can not get anywhere on this project I'm tryin to do. I'm not
> expecting any major help with this but any would be appreciated. The
> assignment is attached. The problem I'm having is trying to set up[/color]
the[color=blue]
> class link and tel_list. I set up a class person with strings for
> name, town, and number. I just don't know how to set up the classes[/color]
w/[color=blue]
> their methods (constructors and operations). I'm stuck on the
> assignment operator and the add and delete operations. A little help
> to get me going on this would be appreciated. Thanks!
>[/color]

For the person class, I'd start by writing getter and setter functions
for each of the data members, plus a copy constructor and assignment
operator. Start by mimicking a simple example class from your
textbook, then see if you can get it to compile. Post your code if you
have questions.

You should be able to get linked list code from an introductory
algorithms text, like Sedgewick's. Start by copying from the book,
then modify the code to suit your requirements. If you get stuck, post
your code here.

Jonathan

[Daniel T.]

Re: do-it-yourself linked list

In article <d22e4ee8.04033 11914.3a4c140f@ posting.google. com>,
dbrag1@aol.com (Darryl B) wrote:
[color=blue]
> I can not get anywhere on this project I'm tryin to do. I'm not
> expecting any major help with this but any would be appreciated. The
> assignment is attached. The problem I'm having is trying to set up the
> class link and tel_list. I set up a class person with strings for
> name, town, and number. I just don't know how to set up the classes w/
> their methods (constructors and operations). I'm stuck on the
> assignment operator and the add and delete operations. A little help
> to get me going on this would be appreciated. Thanks!
>
> Assignment:
> This is a do-it-yourself linked list exercise. Create a class tel_list
> which is a list of telephone subscribers. The data in each list entry
> consists of a person's name, city (or town), and telephone number.
> The data is to be maintained in order by the name of the person. It
> is also to be kept in order by telephone number. The subscribers will
> be linked in two different ways: in name order and in number order.
> Set up a class link to store this data and some pointers to link (one
> set of pointers joins people in alphabetical order, one set joins them
> in numerical order) for each subscriber. Your class link should have
> constructors (including a copy constructor), an assignment operator
> (member), and accessors and mutators as you find them useful.
>
> The data of class tel_list will consist of pointers to the first link
> in each of the two orderings: one to the first link in alphabetical
> order, one to the first link in numerical order. For methods it will
> require a constructor (to make an initially empty list), add (which is
> given a link to insert in the list), delete (which is given a person's
> name and city and must remove their link from the list), and two
> versions of print. One version prints the list in alphabetical order;
> one prints it in numerical order.[/color]

This is a very interesting assignment! With just a little bit of effort,
one could end up with a generally useful set type class that is able to
present its data in any of several different ways.
[color=blue]
> You will also need two methods to find a link since you must be able
> to search either list. It is possible to name them both find and
> distinguish them by the nature of their arguments (the name in one
> case, the telephone number in the other). To either delete a current
> link or add a new link you need to search for the proper location in
> both orderings.
>
> You may set your list up with either forward links only for both
> alphabetical and numerical ordering or you may set up forward and
> backward links for both. Your choice clearly affects the way your
> methods are implemented.
>
> In the text class link is entirely private and declares list (and
> listIterator) as friends. This doesn't seem to work with your
> compiler (!) and the easiest solution is to make your class link
> entirely public. Do not access links directly in your main program.
> The only mention of links, their functions, and their data should be
> in the class list and its members.
>
>
> The program using these classes will consist of a loop reading
> commands and data to manipulate the list. Some sample data (with
> explanations) might be
>
> A A - add to the list
> Ferguson Orono 581-3930
> A
> Baron Orono 866-2103
> .
> .
> .
> P P – print the list (names, cities, and numbers) twice: once in
>
> order by name, once in order by number
> A
> Mittkind Bangor 947-4397
> D D – delete the node whose person and city follow
> Pritchard Veazie
> A
> Xenophon Stillwater 827-9000
>
>
> Remember, errors are possible. You might be told, for example, to
> remove a node with a given name and city, but the person cannot be
> found. Your program should take some reasonable action in these cases
> and continue to the next piece of data.
>
> Create any additional methods you find useful for these classes. The
> data is in the data folder under the name tel_list.dat
>
> Keep your list and link classes simple – you do not need anything near
> the complexity of the library link and list classes. Links with only
> forward pointers are sufficient, for example. You do not need a
> separate iterator class. Any function that needs to move through the
> list can have its own loop within itself.[/color]

OK, it looks like there are three commands: A, D and P. Let's start with
a simple test:



#include <sstream>
#include <string>
#include <stdexcept>
#include <iostream>

// insert your code here

template < typename T >
void check( T expected, T got )
{
if ( !(expected == got) ) {
std::ostringstr eam oss;
oss << "expected: '" << expected << "' got: '" << got << "'";
throw std::logic_erro r( oss.str() );
}
}

int main() {
using namespace std;
try {
tel_list my_list;
my_list.add( "Ferguson", "Orono", "581-3930" );
my_list.add( "Gunter", "Atlanta", "438-2543" );
tel_list::itera tor it( my_list.get_fir st_by_name() );
check( string("Ferguso n"), it.name() );
check( string("Orono") , it.city() );
check( string("581-3930"), it.phone() );
tel_list::itera tor it2( my_list.get_fir st_by_phone() );
check( string("Gunter" ), it2.name() );
check( string("Atlanta "), it2.city() );
check( string("438-2543"), it2.phone() );
}
catch ( exception& err ) {
cerr << err.what() << endl;
}
}

Plug the code above into your compiler and then fix each error that pops
up one at a time. When you get it working, post what you got and I'll
(or someone else) will suggest another test. (Or maybe you will be able
to come up with some of your own tests?)

[John Harrison]

Re: do-it-yourself linked list


"Darryl B" <dbrag1@aol.com > wrote in message
news:d22e4ee8.0 403311914.3a4c1 40f@posting.goo gle.com...[color=blue]
> I can not get anywhere on this project I'm tryin to do. I'm not
> expecting any major help with this but any would be appreciated. The
> assignment is attached. The problem I'm having is trying to set up the
> class link and tel_list. I set up a class person with strings for
> name, town, and number. I just don't know how to set up the classes w/
> their methods (constructors and operations). I'm stuck on the
> assignment operator and the add and delete operations. A little help
> to get me going on this would be appreciated. Thanks!
>
> Assignment:
> This is a do-it-yourself linked list exercise. Create a class tel_list
> which is a list of telephone subscribers. The data in each list entry
> consists of a person's name, city (or town), and telephone number.
> The data is to be maintained in order by the name of the person. It
> is also to be kept in order by telephone number. The subscribers will
> be linked in two different ways: in name order and in number order.
> Set up a class link to store this data and some pointers to link (one
> set of pointers joins people in alphabetical order, one set joins them
> in numerical order) for each subscriber. Your class link should have
> constructors (including a copy constructor), an assignment operator
> (member), and accessors and mutators as you find them useful.
>[/color]

'as you find them useful'

Isn't this the key phrase? Personally I would not have any of those things
on the link class. The link class is an implementation detail, it is used to
implement the tel_list class, which is the main class. I would have a scheme
like this

struct link
{
link* next_name;
link* next_number;
string name;
string city;
string number;
};

class tel_list
{
public:
// constructors, copy constructors, assignment, destructor
// add and delete operations etc.
private:
link* first_name;
link* first_number;
};

The important thing about this scheme is that all the operations are defined
on tel_list, link is never seen or used by person using the tel_list class.
It is purely an implementation detail. That is why you don't need to worry
about or define an interface for link, you just use it as you think best
within tel_list.

You could even put link inside tel_list to emphasise this relationship.

class tel_list
{
private:
struct link
{
link* next_name;
link* next_number;
string name;
string city;
string number;
};
public:
// constructors, copy constructors, assignment, destructor
// add and delete operations
private:
link* first_name;
link* first_number;
};

By putting link inside tel_list (and in the private part) you are
emphasising that link in not part of the interface you are designing, it is
only there as part of the implementation of tel_list.

Seperation of interface from implementation is the key to OO design. You are
designing a system that maintains a list of telephone subscribers. Do you
think the user of that system is interested in links? Do you think they
would even care or know that they exist? All they are interested in is
adding and removing subscribers from the list, they don't care about links
at all. In fact it would be wrong for the user to have to know about links,
if you design your tel_list class in such a way that the user has to know
about links in order to use it then you have made a bad design decision. So
just write the link class in the way that makes things easy for you, and
keep it simple (like I did above) is the best advice.

john

[Daniel T.]

Re: do-it-yourself linked list

dbrag1@aol.com (Darryl B) wrote:
[color=blue]
> I can not get anywhere on this project I'm tryin to do. I'm not
> expecting any major help with this but any would be appreciated. The
> assignment is attached. The problem I'm having is trying to set up the
> class link and tel_list. I set up a class person with strings for
> name, town, and number. I just don't know how to set up the classes w/
> their methods (constructors and operations). I'm stuck on the
> assignment operator and the add and delete operations. A little help
> to get me going on this would be appreciated. Thanks![/color]

I'll just give you the assignment op:

tel_list& tel_list::opera tor=( const tel_list& o )
{
tel_list temp( o );
std::swap( var1, temp.var1 );
std::swap( var2, temp.var2 );
// &c. for each variable in your class
return *this;
}

There are sometimes cheaper (better performing) op= but the above is a
standard idiom that works in every case. (assuming the copy c_tor and
d_tor work properly :-)

[osmium]

Re: do-it-yourself linked list

Darryl B writes:
[color=blue]
> I can not get anywhere on this project I'm tryin to do. I'm not
> expecting any major help with this but any would be appreciated. The
> assignment is attached. The problem I'm having is trying to set up the
> class link and tel_list. I set up a class person with strings for
> name, town, and number. I just don't know how to set up the classes w/
> their methods (constructors and operations). I'm stuck on the
> assignment operator and the add and delete operations. A little help
> to get me going on this would be appreciated. Thanks![/color]

<snip assignment>

Considering an add operation. You will have to maintain two pointers. In
the general case you will not know where to insert the new datum until you
have gone past it. To insert orange between apple and pear you need a
pointer to both apple *and* pear. Searching the Web for "walking the list"
or some such may be helpful.

I have read the assignment several times and I don't know where the
assignment operator (or the copy constructor for that matter) are needed.
They just seem to be tacked on with no real obvious functional necessity.
Maybe if I really got into it I would see the need ..... In any event the
assignment operator checks to see if it is self assignment, if not do what
needs to be done. Certainly, if any assignment or copy is invoked, there
must be code provided by you for them, the defaults give unusable results.
It is a good practice to declare both of these two as private while
debugging, that makes any unforeseen calls produce an *obvious* error.

My reading of the assignment leads to this basic datum:

class Link
{
string name;
string address;
string phone;
Link* next_name;
Link* next_phone;
};

My understanding is that is what the instructor wants but I don't think that
is the starting point you have. But I could well mis-undrstand something in
the assignment or what you said.

Compile often. Just because you compile doesn't mean you have to run. C++
is laden with gotchas laying in wait for you.