== Programming Assignment == For this assignment you will write a program that r

Question

== Programming Assignment ==

For this assignment you will write a program that reads in the family data for
the Martian colonies and stores that data in an accessible database. This
database allows for a user to look up a family and its immediate friends. The
program should store the data in a hashtable to ensure quick access time.

The objective of this assignment is to learn how to implement and use a
hashtable. Since this is the objective, you cannot use a premade hashtable
(e.g. the STL map class).

Note: there is an advanced version of this program (for no additional
credit) that also adds the feature of finding ALL friends, friends of friends,
etc. until a certain group size it met.

== Program Design ==

Your program should use good design methodologies so you should have separate
classes for each of the following:

- family -- This class represents a family. Each family has a family ID
(guaranteed to be unique), a family name (not unique), a number of family
members, and a list of 0-3 friends. The friends are identified by their
associated family ID.

- hashtable -- This is the data storage for family data. It is a hash table
that contains families. It supports the ability to lookup a family and an
ability to insert a family. (Remove is not needed for this assignment). For
debugging purposes, this class also needs to have a "dumpTable()" method
that will print out the contents of the hashtable.

- familymgr -- This class is the interface to the main program for handing
family data. The family manager has a method to add families to the
database. It can also print a list of all known families. The primary
value of the family manager is that, given a family id, it can look up that
family and all of the friends of that family. This functionality is meant to
be used by the HR group to make housing assignments. The simple
functionality for this assignment takes a family and prints out only the
immediate friends. The advanced version will print the full transitive
closure of all friends from a given family up to a given group size limit.

== Other Files ==

I have provided two test programs: testfamily.cpp and testhashtable.cpp. These
are for your use. You are not required to use them but they will be helpful
for developing and debugging your classes.

Finally, for your convenience I have provided a "makefile". If you name all of
your files the same as I have then you can use the following makefile to
simplify your building and testing.

Using the makefile is optional. You are welcome to modify it anyway you
want. You do not need to turn in the makefile.

== External Requirements ==

- The main driver (housinghelper.cpp) will add families to your family
manager. When all of the families have been added the driver program will
ask the family manager class to print out a list of all of the
families. After that, it calls the method to print out the family and
immediate friends for a few families.
- The output from your program must match expected.txt exactly.

== Internal Requirements ==

- The program must use the supplied housinghelper.cpp file, unmodified, as the
main driver.
- The program must store all families in a hashtable.
- The hashtable must use linked list chaining to deal with hash
collisions. New items should be added to the front of the linked list.
- The hashtable hashing function should use the method discussed in the book
and in class. That is:
  
s[0] + s[1]*32 + s[2]*32^2 + s[3]*32^3 + ... s[n-1]*32^n-1

Hint: when calculating the hash value keep in mind each of these things:
1) Use the ASCII values of the letters (e.g. "A" = 65).
2) The hash index needs to be an unsigned integer (e.g. size_t).
3) Apply the modulus operator AFTER summing and multiplying all of the numbers.
- The hashtable hash function must use Horner's rule to refactor the
calculation to make it more efficient (you cannot use the pow() function or
anything else like it).
- The hashtable array size should be 7877 elements (that is a prime number).
- You do not need to resize the table.
- The should be no memory leaks.
- All "string" data should be stored as char* variables. DO NOT USE
std::string.

some examples of family.txt (not the entire file)

Family ID: Smith001
Name: Smith
Members: 2
Friends: Ayala002 Goode001
---
Family ID: Smith002
Name: Smith
Members: 4
Friends: Roderick003
---
Family ID: Johnson001
Name: Johnson
Members: 4
Friends: Springer002
---
Family ID: Johnson002
Name: Johnson
Members: 4
Friends: Harman001 Millard002 Hornsby001
---
Family ID: Johnson003
Name: Johnson
Members: 2
Friends: Custer001 Aviles001 Haney001
---
Family ID: Williams001
Name: Williams
Members: 2
Friends: Baylor002 Cleveland001 Kelley001
---
Family ID: Jones001
Name: Jones
Members: 2
Friends: Quinonez001 Groce001
---
Family ID: Jones002
Name: Jones
Members: 2
Friends: Cavazos001
---
Family ID: Jones003
Name: Jones
Members: 4
Friends: Himes002 Guyton002 Macon001
---
Family ID: Brown001
Name: Brown
Members: 3
Friends: Holland002
---

testfamily.cpp

#include <iostream>

#include "family.h"

using namespace std;

void addFriendHelper(family& fam,const char* myfriend)

{

if (!fam.addFriend(myfriend))

{

cout << "Too many friends for " << fam.getId() << endl;

}

}

int main()

{

// Test some of the basic family functionality. Normally a test like this

// should be self-checking but for this class I am just having it print to

// screen since I think that will be more helpful for you (the students)

family fam("Test001","Test",3);

cout << fam;

addFriendHelper(fam,"Friend001");

cout << fam;

addFriendHelper(fam,"Friend002");

cout << fam;

addFriendHelper(fam,"Friend003");

cout << fam;

addFriendHelper(fam,"Friend004");

cout << fam;

return(0);

}

testhashtable.cpp

#include <iostream>

#include "hashtable.h"

using namespace std;

int main()

{

const int HASHTABLESIZE = 13;

const int NUMFAMILIES = 50;

hashtable ht(HASHTABLESIZE);

cout << "======================================================================" << endl;

cout << "Testing inserts (should show full table)" << endl;

for (int i=0;i<NUMFAMILIES;i++)

{

char id[8];

char name[8];

char friendName[10];

family* familyPtr;

sprintf(id,"Test%d",i);

sprintf(name,"Name%d",i);

sprintf(friendName,"Friend%d",i);

familyPtr = new family(id,name,1);

familyPtr->addFriend(friendName);

ht.insert(id,*familyPtr);

delete familyPtr;

}

ht.dumpTable();

cout << "======================================================================" << endl;

cout << "Testing searches (should show no errors)" << endl;

const family* foundFam;

foundFam = ht.lookup("Test44");

if (foundFam == nullptr)

cout << "ERROR searching for Test44" << endl;

foundFam = ht.lookup("Test39");

if (foundFam == nullptr)

cout << "ERROR searching for Test39" << endl;

foundFam = ht.lookup("Test999");

if (foundFam != nullptr)

cout << "ERROR searching for Test999" << endl;

cout << "======================================================================" << endl;

cout << "Testing removes (should show empty table)" << endl;

for (int i=0;i<NUMFAMILIES;i++)

{

char id[8];

sprintf(id,"Test%d",i);

ht.remove(id);

}

ht.dumpTable();

return(0);

}

some examples of expected.txt (not entire file)

table[0]:
List:
Family ID: Thornburg001
Name: Thornburg
Members: 1
Friends: Salmon003 Whyte001
--------------------
table[1]:
List:
--------------------
table[2]:
List:
Family ID: Montes001
Name: Montes
Members: 1
Friends: Coley001   
--------------------
table[3]:
List:
--------------------
table[4]:
List:
--------------------
table[5]:
List:
--------------------
table[6]:
List:
--------------------
table[7]:
List:
--------------------
table[8]:
List:
--------------------
table[9]:
List:
--------------------
table[10]:
List:
--------------------
table[11]:
List:
Family ID: Hoff001
Name: Hoff
Members: 1
Friends: Applegate002 Hanes002 Rosenthal001
--------------------
table[12]:
List:
Family ID: Hoff002
Name: Hoff
Members: 2
Friends: Marlowe003   
--------------------
table[13]:
List:
Family ID: Hoff003
Name: Hoff
Members: 1
Friends: Beltran001 Barfield001 Hardin001
--------------------
table[14]:
List:
Family ID: Fair001
Name: Fair
Members: 2
Friends: Wick002   
Family ID: Mccullough001
Name: Mccullough
Members: 3
Friends: Tatum003 Lovejoy001
--------------------
table[15]:
List:
Family ID: Fair002
Name: Fair
Members: 4
Friends: Mckeon003   
Family ID: Mccullough002
Name: Mccullough
Members: 1
Friends: Pepper002 Larose002
--------------------
table[16]:
List:
Family ID: Mccullough003
Name: Mccullough
Members: 2
Friends: Thao002 Holloman001
--------------------
table[17]:
List:
--------------------
table[18]:
List:
Family ID: Martin001
Name: Martin
Members: 1
Friends: Turner001 Stephenson002

Explanation / Answer

housinghelper.cpp

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.