473,405 Members | 2,160 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,405 software developers and data experts.

do-it-yourself linked list

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.
Jul 22 '05 #1
5 2291

"Darryl B" <db****@aol.com> wrote in message
news:d2**************************@posting.google.c om...
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!


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
Jul 22 '05 #2
In article <d2**************************@posting.google.com >,
db****@aol.com (Darryl B) wrote:
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.
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.
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.


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::ostringstream oss;
oss << "expected: '" << expected << "' got: '" << got << "'";
throw std::logic_error( 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::iterator it( my_list.get_first_by_name() );
check( string("Ferguson"), it.name() );
check( string("Orono"), it.city() );
check( string("581-3930"), it.phone() );
tel_list::iterator it2( my_list.get_first_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?)
Jul 22 '05 #3

"Darryl B" <db****@aol.com> wrote in message
news:d2**************************@posting.google.c om...
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.


'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
Jul 22 '05 #4
db****@aol.com (Darryl B) wrote:
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!


I'll just give you the assignment op:

tel_list& tel_list::operator=( 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 :-)
Jul 22 '05 #5
Darryl B writes:
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!


<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.

Jul 22 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Marco | last post by:
We can read this comment at php.net >jon >05-Nov-2003 10:06 >According to my tests, the "do...while" control structure actually seems to be ~40% faster than the "for" control structure. At...
11
by: Colin Steadman | last post by:
Hope this makes sense! I'm building an ASP page which allows uses to add items to an invoice via a form, ie: Item No Part No Order No Quanity Units Price VAT ------- ...
1
by: Google Mike | last post by:
I have one table of new records (tableA) that may already exist in tableB. I want to insert these records into tableB with insert if they don't already exist, or update any existing ones with new...
5
by: Blatwurst | last post by:
I'm trying to implement a simple server in C#. I want to do the classic thing of spinning off a thread that just blocks in a Socket.Accept() call until a request comes in. At that point, the...
11
by: Angus Graham | last post by:
Hi: I've recently come across a number of programmers who use the following type of do/while(false) structure quite often: do { if (! CatchFish(pFish)) { break; } if (! CleanFish(pFish)) {
1
by: Do Park via SQLMonster.com | last post by:
Hello all, I don?t often export data from a table. I am wondering how you export data from a table. I?d like to know how you export in real world. Do you export data from a table to a flat...
2
by: floyds | last post by:
do child tables inherit the indexes declared for a parent table? or do i need to redeclare the index on each child table? for example: create table fee ( fie text ); create index fee_index on...
1
by: jeffb | last post by:
I am interested in finding out how DB2 DBAs automate tasks/jobs in their environments. What platform do you run DB2 on (Unix, Linux, Mainframe, Windows)? If you currently have a solution, what...
2
by: Loribeth | last post by:
Hi All, I am working on a sub that will loop through a recordset and validate that the ranges are valid, ie no overlapping values - no gaps in the ranges. I am pretty sure I have the validation...
6
by: John Pass | last post by:
What is the difference between a While and Do While/Loop repetition structure. If they is no difference (as it seems) why do both exist?
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
0
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
0
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.