Help with hash table please :) .... I\'m partly here looking for a cleaner syste
ID: 3920890 • Letter: H
Question
Help with hash table please :) .... I'm partly here looking for a cleaner system than my hack-job. Must use char* and can NOT use std::string. ... Thanking you all in advance... You guys have helped me learn so much. You're all pretty amazing.
Question: Write a program that reads in "family" data 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.
You canNOT use a pre-built hashtable (e.g. the STL map class).
-----Design-----
Have at least the following classes:
- 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. The functionality for this assignment takes a family and prints out only the immediate friends.
----Externals----
- 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 - Only partly given in this question.
----Internals-----
- The program must use the supplied housinghelper.cpp file, unmodified, as the main driver.
- Must store families in a hashtable
- Hashtable must use linked list chaining for collisions. New items should be added to the front of the linked list.
- The hashtable hashing function should use the following: s[0] + s[1]*32 + s[2]*32^2 + s[3]*32^3 + ... s[n-1]*32^n-1
Hint: 1. Use the ASCII values for letters (e.g. "A" = 65). 2. Hash index must be unsigned integer (e.g. size_t). 3. Apply modules AFTER summing and multiplying all 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.
---------------------housinghelper.cpp (main driver)---------------------------
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include "familymgr.h"
using namespace std;
int main(int argc,char** argv)
{
if (argc != 2)
{
cout << "Usage: " << argv[0] << " <datafile>" << endl;
exit(0);
}
// family manager object;
familymgr familyMgr;
// Read the data
const int MAX_LINE = 64;
char* datafile = argv[1];
ifstream infile(datafile);
char line[MAX_LINE];
char id[MAX_LINE];
char name[MAX_LINE];
int members;
char friend1[MAX_LINE];
char friend2[MAX_LINE];
char friend3[MAX_LINE];
if (infile.is_open())
{
while (infile.getline(line,MAX_LINE) )
{
char* s;
// ID -- Family ID: <id>
s = strchr(line,':') + 2; // Skip the space
strncpy(id,s,MAX_LINE);
// Name
infile.getline(line,MAX_LINE);
s = strchr(line,':') + 2; // Skip the space
strncpy(name,s,MAX_LINE);
// members
infile.getline(line,MAX_LINE);
s = strchr(line,':') + 2; // Skip the space
members = atoi(s);
// friends
infile.getline(line,MAX_LINE);
s = strchr(line,':') + 2; // Skip the space
char* friendPtr;
friendPtr = strtok(s," ");
if (friendPtr != nullptr)
strncpy(friend1,friendPtr,MAX_LINE);
else
friend1[0] = '';
friendPtr = strtok(nullptr," ");
if (friendPtr != nullptr)
strncpy(friend2,friendPtr,MAX_LINE);
else
friend2[0] = '';
friendPtr = strtok(nullptr," ");
if (friendPtr != nullptr)
strncpy(friend3,friendPtr,MAX_LINE);
else
friend3[0] = '';
infile.getline(line,MAX_LINE);
if (strcmp(line,"---")!=0) {
cout << "Error parsing the file" << endl;
}
// Add the family to the family manager
family* famPtr = new family(id,name,members);
famPtr->addFriend(friend1);
famPtr->addFriend(friend2);
famPtr->addFriend(friend3);
familyMgr.addFamily(*famPtr);
delete famPtr;
}
infile.close();
familyMgr.printAllFamilies();
// familyMgr.printGroup("Smith001");
familyMgr.printSmallCircle("Smith001");
familyMgr.printSmallCircle("Hall001");
familyMgr.printSmallCircle("Noel003");
}
return(0);
}
-------------------------familydata.txt (input stream - NOT the entire file... only ~5%)-----------------------
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
---
Family ID: Davis001
Name: Davis
Members: 1
Friends: Sargent002
---
Family ID: Davis002
Name: Davis
Members: 2
Friends: Crowe001
---
Family ID: Davis003
Name: Davis
Members: 3
Friends: Troutman002 Hill002 Layton001
---
Family ID: Miller001
Name: Miller
Members: 3
Friends: German001
---
Family ID: Wilson001
Name: Wilson
Members: 2
Friends: Stanton001
---
Family ID: Wilson002
Name: Wilson
Members: 1
Friends: Mcgill003 Mcdonnell001
---
Family ID: Wilson003
Name: Wilson
Members: 4
Friends: Nagel001 Romero001 Donato001
---
Family ID: Moore001
Name: Moore
Members: 1
Friends: Warner003 Allred002 Allan001
---
Family ID: Moore002
Name: Moore
Members: 3
Friends: Woo002 Oreilly002
---
Family ID: Moore003
Name: Moore
Members: 4
Friends: Dionne003
---
Family ID: Taylor001
Name: Taylor
Members: 1
Friends: Lively003
---
Family ID: Taylor002
Name: Taylor
Members: 2
Friends: Couch002
---
Family ID: Taylor003
Name: Taylor
Members: 1
Friends: Myles002 Tharp002
---
Family ID: Anderson001
Name: Anderson
Members: 1
Friends: Satterfield002
---
Family ID: Thomas001
Name: Thomas
Members: 4
Friends: Scott001
---
Family ID: Jackson001
Name: Jackson
Members: 3
Friends: Dyson003 Dowdell001
---
Family ID: Jackson002
Name: Jackson
Members: 2
Friends: Chavis002 Redmon001
---
Family ID: Jackson003
Name: Jackson
Members: 2
Friends: Wang002 Steele001
---
Family ID: White001
Name: White
Members: 3
Friends: Sparrow003 Burroughs002
---
Family ID: White002
Name: White
Members: 1
Friends: Shepherd001 Sherman002 Rivas002
---
Family ID: White003
Name: White
Members: 4
Friends: Stillwell003 Montgomery003
---
Family ID: Harris001
Name: Harris
Members: 3
Friends: Harter001
---
Family ID: Harris002
Name: Harris
Members: 4
Friends: Cobbs002 Harry001 Wofford001
---
Family ID: Martin001
Name: Martin
Members: 1
Friends: Turner001 Stephenson002
---
Family ID: Martin002
Name: Martin
Members: 3
Friends: Barber001 Shannon002 Ramsay001
---
Family ID: Thompson001
Name: Thompson
Members: 2
Friends: Findley001
---
Family ID: Thompson002
Name: Thompson
Members: 4
Friends: Swain001
---
Family ID: Garcia001
Name: Garcia
Members: 1
Friends: Kilgore001 Gonzalez003 Mojica002
---
Family ID: Garcia002
Name: Garcia
Members: 2
Friends: Staggs001 Kenyon001
---
Family ID: Martinez001
Name: Martinez
Members: 3
Friends: Baum001
---
Family ID: Robinson001
Name: Robinson
Members: 3
Friends: Bonilla003 Eskridge001
---
Family ID: Clark001
Name: Clark
Members: 2
Friends: Whyte003 Gardner001
---
Family ID: Clark002
Name: Clark
Members: 3
Friends: Badger003 Gee001 Jeter001
---
Family ID: Rodriguez001
Name: Rodriguez
Members: 2
Friends: Purvis002
---
Family ID: Rodriguez002
Name: Rodriguez
Members: 2
Friends: Penrod003
---
Family ID: Lewis001
Name: Lewis
Members: 4
Friends: Gamble002 Prichard001
---
Family ID: Lewis002
Name: Lewis
Members: 4
Friends: Speight001 Brooks002 Irons003
---
Family ID: Lee001
Name: Lee
Members: 1
Friends: Noland002 Berlin001 Cohn001
---
Family ID: Lee002
Name: Lee
Members: 3
Friends: Cheng001
---
Family ID: Walker001
Name: Walker
Members: 1
Friends: Inman001
---
Family ID: Walker002
Name: Walker
Members: 3
Friends: Irons003 Anders001
---
Family ID: Walker003
Name: Walker
Members: 3
Friends: Brinkley003
---
Family ID: Hall001
Name: Hall
Members: 2
Friends: Kraft003 Hutchinson002 Bryant002
---
Family ID: Hall002
Name: Hall
Members: 4
Friends: Redd003 Coy001 Moffett003
---
Family ID: Allen001
Name: Allen
Members: 1
Friends: Harlow003 Shelton001
---
Family ID: Allen002
Name: Allen
Members: 4
Friends: Crain003
---
Family ID: Young001
Name: Young
Members: 4
Friends: Mullis002 Criswell002 Denny002
---
Family ID: Young002
Name: Young
Members: 4
Friends: Dunning002 Lance001 Mccall001
---
Family ID: Young003
Name: Young
Members: 2
Friends: Singh002 Bandy002 Rowell001
---
Family ID: Hernandez001
Name: Hernandez
Members: 4
Friends: Simms002 Lowman002 Mora001
---
Family ID: Hernandez002
Name: Hernandez
Members: 1
Friends: Rudd002 Mcdade001 Clancy003
---
Family ID: Hernandez003
Name: Hernandez
Members: 2
Friends: Everson003
---
Family ID: King001
Name: King
Members: 4
Friends: Blackwell001 Sullivan002 Atkinson002
---
Family ID: King002
Name: King
Members: 3
Friends: Lugo001 Leighton001 Gomes001
---
Family ID: Wright001
Name: Wright
Members: 3
Friends: Deluca001 Dancy002 Payne001
---
Family ID: Wright002
Name: Wright
Members: 1
Friends: Riley002
---
Family ID: Wright003
Name: Wright
Members: 2
Friends: Fox003
---
Family ID: Lopez001
Name: Lopez
Members: 4
Friends: Gamez002
---
Family ID: Hill001
Name: Hill
Members: 1
Friends: Treat002
---
Family ID: Hill002
Name: Hill
Members: 4
Friends: Harrison001 Wentz003 Martz002
---
Family ID: Hill003
Name: Hill
Members: 4
Friends: Adamson001
---
Family ID: Scott001
Name: Scott
Members: 4
Friends: Roth002 Gibbs002 Pinkston001
---
Family ID: Scott002
Name: Scott
Members: 2
Friends: Michaud001
---
Family ID: Scott003
Name: Scott
Members: 4
Friends: Albright002 Day002 Gregory001
---
Family ID: Green001
Name: Green
Members: 4
Friends: Catron002 Keister001
---
Family ID: Green002
Name: Green
Members: 4
Friends: Rincon001
---
Family ID: Adams001
Name: Adams
Members: 4
Friends: Mcvey001
---
Family ID: Adams002
Name: Adams
Members: 3
Friends: Thayer001
---
Family ID: Baker001
Name: Baker
Members: 3
Friends: Shelby002
---
Family ID: Baker002
Name: Baker
Members: 2
Friends: Hoff001 Mott002 Morehead001
---
Family ID: Gonzalez001
Name: Gonzalez
Members: 4
Friends: Jameson001 Skidmore003
---
Family ID: Gonzalez002
Name: Gonzalez
Members: 1
Friends: Abrams003
---
Family ID: Gonzalez003
Name: Gonzalez
Members: 1
Friends: Renfro002 Williams001 Staten001
---
Family ID: Nelson001
Name: Nelson
Members: 2
Friends: Vaught001
---
Family ID: Nelson002
Name: Nelson
Members: 4
Friends: Stamps001
---
Family ID: Nelson003
Name: Nelson
Members: 3
Friends: Reece002 Goad002
---
Family ID: Carter001
Name: Carter
Members: 2
Friends: Gibbs001
---
Family ID: Mitchell001
Name: Mitchell
Members: 4
Friends: Picard001
---
Family ID: Mitchell002
Name: Mitchell
Members: 3
Friends: Moore003 Olive002
---
Family ID: Perez001
Name: Perez
Members: 1
Friends: Dionne002 Catalano001
---
Family ID: Perez002
Name: Perez
Members: 3
Friends: Laney002 Lerner002 Denham003
---
Family ID: Perez003
Name: Perez
Members: 1
Friends: Yu001 Heredia001 Cheatham001
---
Family ID: Roberts001
Name: Roberts
Members: 4
Friends: Christ001 Booker003
---
Family ID: Roberts002
Name: Roberts
Members: 1
Friends: Wilbur002 Carrasco001 Cooksey001
---
Family ID: Roberts003
Name: Roberts
Members: 2
Friends: Leclair003 Havens001
---
Family ID: Turner001
Name: Turner
Members: 3
Friends: Criswell003
---
Family ID: Turner002
Name: Turner
Members: 1
Friends: Kearney001 Chitwood002 Glenn003
---
Family ID: Turner003
Name: Turner
Members: 3
Friends: Mcmahon001 Montero002
---
Family ID: Phillips001
Name: Phillips
Members: 4
Friends: Sheets003 Bock002
---
Family ID: Campbell001
Name: Campbell
Members: 4
Friends: Kuykendall003 Soule001
---
Family ID: Campbell002
Name: Campbell
Members: 2
Friends: Runyan001 Beamon001
---
Family ID: Campbell003
Name: Campbell
Members: 2
Friends: Upchurch002 Becker002
---
Family ID: Parker001
Name: Parker
Members: 1
Friends: Byers001
---
Family ID: Parker002
Name: Parker
Members: 2
Friends: Brittain002 Rosser003 Rangel002
---
Family ID: Evans001
Name: Evans
Members: 1
Friends: Masterson001 Lundberg001
---
Family ID: Edwards001
Name: Edwards
Members: 1
Friends: Ceja003 Staten001 Blackmon003
---
----------------------------expected.txt (what the output should look like - NOT entire file. Won't match above copied dataset)-------------------------
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
--------------------
table[19]:
List:
Family ID: Martin002
Name: Martin
Members: 3
Friends: Barber001 Shannon002 Ramsay001
--------------------
table[20]:
List:
--------------------
table[21]:
List:
Family ID: Gutierrez001
Name: Gutierrez
Members: 4
Friends: Beaudoin001
--------------------
table[22]:
List:
Family ID: Gutierrez002
Name: Gutierrez
Members: 1
Friends: Ball001
--------------------
table[23]:
List:
--------------------
table[24]:
List:
--------------------
table[25]:
List:
--------------------
table[26]:
List:
--------------------
table[27]:
List:
Family ID: Schaefer001
Name: Schaefer
Members: 2
Friends: Atwell003 Broadnax003 Laney001
--------------------
table[28]:
List:
Family ID: Mosher001
Name: Mosher
Members: 1
Friends: Staten003 Mcdowell002 Worsham001
Family ID: Schaefer002
Name: Schaefer
Members: 1
Friends: Barringer001 Peltier002
--------------------
table[29]:
List:
Family ID: Arevalo001
Name: Arevalo
Members: 3
Friends: Towns001
Family ID: Mosher002
Name: Mosher
Members: 1
Friends: Stuart001 Giles001 Lusk002
--------------------
table[30]:
List:
Family ID: Arevalo002
Name: Arevalo
Members: 3
Friends: Behrens001
Family ID: Mosher003
Name: Mosher
Members: 3
Friends: Kirchner001 Hatfield001 Rico002
Family ID: Sadler001
Name: Sadler
Members: 2
Friends: Renfro003
--------------------
table[31]:
List:
Family ID: Soria001
Name: Soria
Members: 3
Friends: Burney001
Family ID: Arevalo003
Name: Arevalo
Members: 4
Friends: Melton002
Family ID: Sadler002
Name: Sadler
Members: 2
Friends: Weaver001
--------------------
table[32]:
List:
Family ID: Sadler003
Name: Sadler
Members: 4
Friends: Cato003
--------------------
table[33]:
List:
Family ID: Bostick001
Name: Bostick
Members: 2
Friends: Matney002 Knapp002 Bogan001
--------------------
table[34]:
List:
Family ID: Osorio001
Name: Osorio
Members: 4
Friends: Yocum003
--------------------
table[35]:
List:
Family ID: Catalano001
Name: Catalano
Members: 2
Friends: Ainsworth002 Talbott002 Blue003
--------------------
table[36]:
List:
Family ID: Catalano002
Name: Catalano
Members: 4
Friends: Laporte001 Osteen001
Family ID: Tipton001
Name: Tipton
Members: 4
Friends: Mcdaniels002
--------------------
table[37]:
List:
Family ID: Catalano003
Name: Catalano
Members: 3
Friends: Reichert003 Holloman001
--------------------
table[38]:
List:
Family ID: Battaglia001
Name: Battaglia
Members: 1
Friends: Dorsey001
--------------------
table[39]:
List:
Family ID: Battaglia002
Name: Battaglia
Members: 1
Friends: Clough003
--------------------
table[40]:
List:
Family ID: Battaglia003
Name: Battaglia
Members: 4
Friends: Maher001 Adam001 Jaramillo001
--------------------
table[41]:
List:
--------------------
table[42]:
List:
Family ID: Casanova001
Name: Casanova
Members: 2
Friends: Ewing002 Willson001
--------------------
table[43]:
List:
Family ID: Barrows001
Name: Barrows
Members: 3
Friends: Escobar001
--------------------
table[44]:
List:
Family ID: Barrows002
Name: Barrows
Members: 2
Friends: Moody002
--------------------
table[45]:
List:
Family ID: Barrows003
Name: Barrows
Members: 3
Friends: Furman003 Runyon001
--------------------
table[46]:
List:
--------------------
table[47]:
List:
--------------------
table[48]:
List:
Family ID: Spalding001
Name: Spalding
Members: 1
Friends: Whitworth001 Brookins002 Hummel001
--------------------
table[49]:
List:
Family ID: Spalding002
Name: Spalding
Members: 3
Friends: Mcgill003
--------------------
table[50]:
List:
Family ID: Spalding003
Name: Spalding
Members: 2
Friends: Laplante003
--------------------
table[51]:
List:
--------------------
table[52]:
List:
Family ID: Hardaway001
Name: Hardaway
Members: 2
Friends: Worrell002
--------------------
table[53]:
List:
Family ID: Hardaway002
Name: Hardaway
Members: 3
Friends: Grover002 Treadwell001
--------------------
table[54]:
List:
Family ID: Amundson001
Name: Amundson
Members: 4
Friends: Bravo003 Hutton001
--------------------
table[55]:
List:
Family ID: Beavers001
Name: Beavers
Members: 1
Friends: Massie001
--------------------
table[56]:
List:
Family ID: Beavers002
Name: Beavers
Members: 4
Friends: Dover002
--------------------
table[57]:
List:
Family ID: Beavers003
Name: Beavers
Members: 4
Friends: Kinney001 Harp001
--------------------
table[58]:
List:
Family ID: Maier001
Name: Maier
Members: 4
Friends: Bridges001
--------------------
table[59]:
List:
Family ID: Maier002
Name: Maier
Members: 1
Friends: Root002 Qualls002 Ivory001
--------------------
table[60]:
List:
Family ID: Maier003
Name: Maier
Members: 3
Friends: Mcvay001 Hays002
Family ID: Stephenson001
Name: Stephenson
Members: 4
Friends: Nunn001 Whitten002
--------------------
table[61]:
List:
Family ID: Tomlinson001
Name: Tomlinson
Members: 4
Friends: Santoro001
Family ID: Kerr001
Name: Kerr
Members: 4
Friends: Worthy001
Family ID: Stephenson002
Name: Stephenson
Members: 4
Friends: Skelton001
--------------------
table[62]:
List:
Family ID: Kerr002
Name: Kerr
Members: 4
Friends: Reddick001
--------------------
table[63]:
List:
--------------------
table[64]:
List:
Family ID: Nolen001
Name: Nolen
Members: 1
Friends: Beaty002 Bittner002
Family ID: Fontaine001
Name: Fontaine
Members: 2
Friends: Almeida001 Crist001
Family ID: Ogle001
Name: Ogle
Members: 1
Friends: Mullins001 Chandler001
--------------------
table[65]:
List:
Family ID: Bittner001
Name: Bittner
Members: 2
Friends: Pettis002 Shearer003 Ziegler003
Family ID: Nolen002
Name: Nolen
Members: 4
Friends: Mcarthur001 Fox001
Family ID: Fontaine002
Name: Fontaine
Members: 3
Friends: Stevens002 Jordan001
Family ID: Ogle002
Name: Ogle
Members: 2
Friends: Charles001 Haywood001
Family ID: Farley001
Name: Farley
Members: 2
Friends: Lauer002 Wentworth001
Family ID: Ford001
Name: Ford
Members: 4
Friends: Hutchison002 Drayton002
--------------------
table[66]:
List:
Family ID: Bittner002
Name: Bittner
Members: 2
Friends: Beaudoin002
Family ID: Nolen003
Name: Nolen
Members: 3
Friends: Gagne003 Tackett002
Family ID: Fontaine003
Name: Fontaine
Members: 1
Friends: Devries001 Mcdonough001
Family ID: Ogle003
Name: Ogle
Members: 1
Friends: Ogden001
Family ID: Farley002
Name: Farley
Members: 2
Friends: Streeter002 Mauro002
Family ID: Ford002
Name: Ford
Members: 1
Friends: Hitt001 Plante002
--------------------
table[67]:
List:
Family ID: Bittner003
Name: Bittner
Members: 2
Friends: Troutman002 Mcelroy001
Family ID: Riggs001
Name: Riggs
Members: 3
Friends: Snodgrass002 Boisvert002 Longoria001
Family ID: Farley003
Name: Farley
Members: 2
Friends: Storey001 Nettles002 German002
Family ID: Ford003
Name: Ford
Members: 2
Friends: Howell002
--------------------
table[68]:
List:
Family ID: Riggs002
Name: Riggs
Members: 1
Friends: Mcnamara001
--------------------
table[69]:
List:
Family ID: Sepulveda001
Name: Sepulveda
Members: 1
Friends: Branham002 Parrott002 Peel001
--------------------
table[70]:
List:
Family ID: Sepulveda002
Name: Sepulveda
Members: 2
Friends: Roark001
--------------------
table[71]:
List:
Family ID: Sepulveda003
Name: Sepulveda
Members: 1
Friends: Canada003
--------------------
table[72]:
List:
--------------------
table[73]:
List:
--------------------
table[74]:
List:
--------------------
table[75]:
List:
--------------------
table[76]:
List:
--------------------
table[77]:
List:
--------------------
table[78]:
List:
Family ID: Hammond001
Name: Hammond
Members: 2
Friends: Lusk001 Wickham003 Mcintosh003
--------------------
table[79]:
List:
Family ID: Hammond002
Name: Hammond
Members: 1
Friends: Cote001 Freeland002 Finch002
--------------------
table[80]:
List:
Family ID: Artis001
Name: Artis
Members: 3
Friends: Ezell002
--------------------
table[81]:
List:
Family ID: Artis002
Name: Artis
Members: 4
Friends: Soper002
--------------------
table[82]:
List:
--------------------
table[83]:
List:
Family ID: Fugate001
Name: Fugate
Members: 3
Friends: Callender001 Hite001 Mcconnell001
--------------------
table[84]:
List:
Family ID: Sebastian001
Name: Sebastian
Members: 1
Friends: Duncan001
Family ID: Libby001
Name: Libby
Members: 3
Friends: Roddy002
Family ID: Lindsey001
Name: Lindsey
Members: 1
Friends: Hatch001 Smothers003 Hagan002
--------------------
table[85]:
List:
Family ID: Durbin001
Name: Durbin
Members: 3
Friends: Frey002 Vaughn002
Family ID: Libby002
Name: Libby
Members: 2
Friends: Shapiro001
Family ID: Villalobos001
Name: Villalobos
Members: 1
Friends: Ellis003 Finch002
Family ID: Lindsey002
Name: Lindsey
Members: 4
Friends: Peters001
--------------------
table[86]:
List:
Family ID: Durbin002
Name: Durbin
Members: 2
Friends: Parra002
Family ID: Villalobos002
Name: Villalobos
Members: 2
Friends: Walsh003 Binder001
Family ID: Lindsey003
Name: Lindsey
Members: 2
Friends: Bolen002
--------------------
table[87]:
List:
Family ID: Mcnabb001
Name: Mcnabb
Members: 4
Friends: Flora001 Canty001 Schaefer002
Family ID: Durbin003
Name: Durbin
Members: 4
Friends: Marquez001 Falk002 Marquardt003
--------------------
table[88]:
List:
Family ID: Pitman001
Name: Pitman
Members: 1
Friends: Norfleet002 Schell001
Family ID: Dent001
Name: Dent
Members: 2
Friends: Trejo001 Crow002
--------------------
table[89]:
List:
Family ID: Pitman002
Name: Pitman
Members: 4
Friends: Foy001
Family ID: Dent002
Name: Dent
Members: 4
Friends: Stonge002 Denman002 Creighton001
--------------------
table[90]:
List:
Family ID: Vaughn001
Name: Vaughn
Members: 4
Friends: Loomis003
--------------------
table[91]:
List:
Family ID: Mack001
Name: Mack
Members: 4
Friends: Angel001
Family ID: Vaughn002
Name: Vaughn
Members: 4
Friends: Gallagher001 Pitre001
--------------------
table[92]:
List:
Family ID: Mack002
Name: Mack
Members: 1
Friends: Jude001
Family ID: Vaughn003
Name: Vaughn
Members: 2
Friends: Chin002
--------------------
table[93]:
List:
Family ID: Dover001
Name: Dover
Members: 1
Friends: Vu002
Family ID: Nobles001
Name: Nobles
Members: 2
Friends: Dees002 Stoner001
--------------------
table[94]:
List:
Family ID: Dover002
Name: Dover
Members: 1
Friends: Driver002
--------------------
table[95]:
List:
--------------------
table[96]:
List:
Family ID: Manzo001
Name: Manzo
Members: 4
Friends: Chinn002 Burley001
--------------------
table[97]:
List:
Family ID: Manzo002
Name: Manzo
Members: 3
Friends: Folsom002 Mcdougal003 Hamby001
Family ID: Runyan001
Name: Runyan
Members: 2
Friends: Phan003 Vang001 Worrell003
Family ID: Sylvester001
Name: Sylvester
Members: 4
Friends: Pike003
--------------------
table[98]:
List:
Family ID: Runyan002
Name: Runyan
Members: 2
Friends: Glenn002 Dupont001 Boynton002
Family ID: Lofton001
Name: Lofton
Members: 3
Friends: Cervantes001
--------------------
table[99]:
List:
Family ID: Runyan003
Name: Runyan
Members: 2
Friends: Begay001 Reese001
Family ID: Escobar001
Name: Escobar
Members: 4
Friends: Gipson001 Bryson001 Foster001
--------------------
table[100]:
List:
--------------------
table[101]:
List:
Family ID: Nagel001
Name: Nagel
Members: 2
Friends: Oleary002 Mcgovern001 Busch001
--------------------
table[102]:
List:
Family ID: Fenwick001
Name: Fenwick
Members: 3
Friends: Cochrane003 Riddell001
Family ID: Guido001
Name: Guido
Members: 1
Friends: Mcnair001 Mott001 Mcginnis002
Family ID: Nagel002
Name: Nagel
Members: 4
Friends: Kern001 Bottoms001 Sena002
Family ID: Keyes001
Name: Keyes
Members: 2
Friends: Farias001
Family ID: Colon001
Name: Colon
Members: 2
Friends: Maxey001 Fife001
--------------------
table[103]:
List:
Family ID: Fenwick002
Name: Fenwick
Members: 2
Friends: Lilley001
Family ID: Guido002
Name: Guido
Members: 4
Friends: Atwell001 Roy002
Family ID: Keyes002
Name: Keyes
Members: 3
Friends: Akers001 Swafford001
--------------------
table[104]:
List:
Family ID: Fenwick003
Name: Fenwick
Members: 2
Friends: Fitts001 Wickham003 Benge001
Family ID: Paredes001
Name: Paredes
Members: 1
Friends: Mosher003 Forrest001
Family ID: Keyes003
Name: Keyes
Members: 3
Friends: Mccullough002 Trowbridge001 Loper002
--------------------
table[105]:
List:
Family ID: Paredes002
Name: Paredes
Members: 3
Friends: Olsen002
Family ID: Fong001
Name: Fong
Members: 4
Friends: Edgar001
--------------------
table[106]:
List:
--------------------
table[107]:
List:
Family ID: Escobedo001
Name: Escobedo
Members: 3
Friends: Barksdale001
Family ID: Walls001
Name: Walls
Members: 3
Friends: Goodman001 Gilson001 Nickel002
--------------------
table[108]:
List:
Family ID: Matson001
Name: Matson
Members: 4
Friends: Romeo002
Family ID: Schumacher001
Name: Schumacher
Members: 3
Friends: Brim001
Family ID: Escobedo002
Name: Escobedo
Members: 4
Friends: Marquardt002
Family ID: Walls002
Name: Walls
Members: 3
Friends: Potts003
--------------------
table[109]:
List:
Family ID: Dugas001
Name: Dugas
Members: 3
Friends: Herring001 Durand003 Lance002
Family ID: Brackett001
Name: Brackett
Members: 4
Friends: Burt002
Family ID: Schumacher002
Name: Schumacher
Members: 2
Friends: Fishman001 Mulligan002
Family ID: Escobedo003
Name: Escobedo
Members: 3
Friends: Shumaker001 Weis001
--------------------
table[110]:
List:
Family ID: Dugas002
Name: Dugas
Members: 1
Friends: Guido001
Family ID: Brackett002
Name: Brackett
Members: 2
Friends: Fish001 Arthur001 Braden001
Family ID: Schumacher003
Name: Schumacher
Members: 4
Friends: Mcfall002
--------------------
table[111]:
List:
Family ID: Dugas003
Name: Dugas
Members: 2
Friends: Davis003 Moulton002
--------------------
table[112]:
List:
Family ID: Nation001
Name: Nation
Members: 3
Friends: Littlejohn001 Crandall001
--------------------
table[113]:
List:
Family ID: Nation002
Name: Nation
Members: 2
Friends: Buford003 Bruce001
--------------------
table[114]:
List:
Family ID: Flanigan001
Name: Flanigan
Members: 2
Friends: Barkley002
Family ID: Nation003
Name: Nation
Members: 1
Friends: Scribner001 Lipscomb002 Odell002
Family ID: Pollard001
Name: Pollard
Members: 4
Friends: Hillman002 Nagy002
--------------------
table[115]:
List:
Family ID: Flanigan002
Name: Flanigan
Members: 4
Friends: Finley001
Family ID: Pollard002
Name: Pollard
Members: 1
Friends: Keefe001
--------------------
table[116]:
List:
Family ID: Swank001
Name: Swank
Members: 1
Friends: Earl001
Family ID: Pollard003
Name: Pollard
Members: 3
Friends: Sonnier001 Hodgson002
--------------------
table[117]:
List:
Family ID: Swank002
Name: Swank
Members: 4
Friends: Morrow001 Keefer002 Gilley002
Family ID: Sorenson001
Name: Sorenson
Members: 2
Friends: Veal001
--------------------
table[118]:
List:
--------------------
table[119]:
List:
--------------------
table[120]:
List:
--------------------
table[121]:
List:
Family ID: Jenson001
Name: Jenson
Members: 4
Friends: Hamer001 Redd003 Whitcomb001
Family ID: Minton001
Name: Minton
Members: 3
Friends: Lombardi001
--------------------
table[122]:
List:
--------------------
table[123]:
List:
--------------------
table[124]:
List:
--------------------
table[125]:
List:
--------------------
table[126]:
List:
Family ID: Wendt001
Name: Wendt
Members: 2
Friends: Reis002 Samuels003 Golding001
--------------------
table[127]:
List:
Family ID: Wendt002
Name: Wendt
Members: 4
Friends: Grey001 Gibbons001 Moffett002
--------------------?
Explanation / Answer
family.cpp
#include "family.h"
// -------------------------------------------------------------
// Constructors/Destructors
// -------------------------------------------------------------
family::family()
{
ID = new char [4];
strcpy(ID,"N/A");
name = new char[4];
strcpy(name,"N/A");
members = 0;
nFriends = 0;
}
family::family(char * tID, char * tName, int tMemebers)
{
ID = new char [strlen(tID) + 1];
strcpy(ID,tID);
name = new char[strlen(tName) + 1];
strcpy(name,tName);
members = tMemebers;
nFriends = 0;
for (int i = 0; i < MAX_FRIENDS; i++)
friends[i] = NULL;
}
family::~family()
{
if(ID)
delete[] ID;
if(name)
delete[] name;
for(int i = 0; i < MAX_FRIENDS ; i++)
{
if(friends[i])
delete friends[i];
}
}
// -------------------------------------------------------------
// Accessors
// -------------------------------------------------------------
char * family::getId()
{
return ID;
}
char * family::getName()
{
return name;
}
int family::getMembers()
{
return members;
}
int family::getFriendCount()
{
return nFriends;
}
char * family::getFriend(int index) const
{
return friends[index];
}
void family::getFriends(ostream & buffer)
{
for(int i = 0; i < 3; i++)
{
if(friends[i])
buffer << friends[i] << " ";
}
}
// -------------------------------------------------------------
// Mutators
// -------------------------------------------------------------
bool family::addFriend(const char * tFriend)
{
if (nFriends == MAX_FRIENDS)
{
return false;
}
else
{
friends[nFriends] = new char[strlen(tFriend) + 1];
strcpy(friends[nFriends],tFriend);
nFriends++;
return true;
}
}
// -------------------------------------------------------------
// Operators
// -------------------------------------------------------------
const family & family::operator = (const family & tempFam)
{
if(this == & tempFam)
{
return *this;
}
else
{
if(ID)
delete [] ID;
ID = new char[strlen(tempFam.ID)];
strcpy(this->ID,tempFam.ID);
if(name)
delete [] name;
name = new char[strlen(tempFam.name)];
strcpy(this->name,tempFam.name);
this->members = tempFam.members;
for(int i = 0; i < MAX_FRIENDS; i++)
{
if(friends[i])
{
delete friends[i];
}
if(tempFam.friends[i])
{
friends[i] = new char[strlen(tempFam.friends[i]) + 1];
strcpy(this->friends[i],tempFam.friends[i]);
}
}
return * this;
}
}
ostream & operator << (ostream & buffer, family & fam)
{
buffer << "Family ID: " << fam.getId() << endl;
buffer << " Name: " << fam.getName() << endl;
buffer << " Members: " << fam.getMembers() << endl;
buffer << " Friends: ";
fam.getFriends(buffer);
buffer << endl;
return buffer;
}
family.h
#ifndef FAMILY_H
#define FAMILY_H
#include <iostream>
#include <string.h>
using namespace std;
class family
{
private:
const int MAX_FRIENDS = 3;
char * ID;
char * name;
int members;
int nFriends;
char * friends[3];
public:
// Constructors/Destructors
family();
family(char*, char*, int);
~family();
// Accessors
char * getId();
char * getName();
int getMembers();
int getFriendCount();
char * getFriend(int) const;
void getFriends(ostream & buffer);
// Mutators
bool addFriend(const char *);
// Operators
const family & operator = (const family &);
friend ostream & operator << (ostream &, family &);
};
#endif
familymgr.cpp
#include "familymgr.h"
// -------------------------------------------------------------
// Constructors/Destructors
// -------------------------------------------------------------
familymgr::familymgr()
{
families = new hashtable();
outFile.open("assigned.txt");
}
familymgr::~familymgr()
{
if(families)
delete families;
outFile.close();
}
// -------------------------------------------------------------
// Accessors
// -------------------------------------------------------------
void familymgr::printAllFamilies()
{
outFile << * families;
}
void familymgr::printGroup(family *)
{
}
void familymgr::printSmallCircle(char * thing)
{
family * fam = families->lookup(thing);
outFile << "Printing family and immediate friends " << thing << endl;
outFile << "== Family ==" << endl;
outFile << * fam << endl;
outFile << "== Friends (1 level) ==" << endl;
cout << endl<< endl<< endl<< endl<< endl<< fam->getFriendCount() << endl;
for(int i = 0; i < 3; i++)
{
if(families->lookup(fam->getFriend(i)))
outFile << * families->lookup(fam->getFriend(i));
}
}
// -------------------------------------------------------------
// Mutators
// -------------------------------------------------------------
void familymgr::addFamily(family & fam)
{
families->insert(fam.getId(),fam);
}
familymgr.h
#ifndef FAMILYMGR_H
#define FAMILYMGR_H
#include <iostream>
#include <fstream>
#include "hashtable.h"
using namespace std;
class familymgr
{
private:
hashtable * families;
ofstream outFile;
public:
// Constructors/Destructors
familymgr();
~familymgr();
// Accessors
void printAllFamilies();
void printGroup(family *);
void printSmallCircle(char *);
// Mutators
void addFamily(family &);
};
#endif
hashtable.cpp
#include "hashtable.h"
// -------------------------------------------------------------
// Constructors/Destructors
// -------------------------------------------------------------
hashtable::hashtable()
{
tableCount = 0;
tableSize = MAX_CAP;
famTable = new hashEntry * [tableSize];
for (int i = 0; i < tableSize; i++)
{
famTable[i] = NULL;
}
}
hashtable::hashtable(int x)
{
tableCount = 0;
tableSize = x;
famTable = new hashEntry * [tableSize];
for (int i = 0; i < tableSize; i++)
{
famTable[i] = NULL;
}
}
hashtable::~hashtable()
{
destroyTable();
}
// -------------------------------------------------------------
// Accessors
// -------------------------------------------------------------
family * hashtable::lookup(char * id) const
{
size_t i = hash(id);
hashEntry * curr = famTable[i];
while(curr)
{
if(curr->data.getId())
{
char * tID = new char[strlen(curr->data.getId())];
strcpy(tID,curr->data.getId());
if(strcmp(id, tID) == 0)
{
delete tID;
return & curr->data;
}
else
{
delete tID;
curr = curr->next;
}
}
}
curr = NULL;
return NULL;
}
int hashtable::getSize() const
{
return tableSize;
}
void hashtable::dumpTable()
{
for(int i = 0; i < tableSize; i++)
{
for(hashEntry * curr = famTable[i]; curr; curr = curr->next)
{
cout << curr->data << endl;
}
}
}
// -------------------------------------------------------------
// Mutators
// -------------------------------------------------------------
void hashtable::insert(char * id, const family & fam)
{
size_t i = hash(id);
hashEntry * temp = new hashEntry(fam);
temp->next = famTable[i];
famTable[i] = temp;
tableCount++;
}
size_t hashtable::hash(char * id) const
{
size_t index = id[0];
size_t length = strlen(id);
for(int i = 1; i < length; i++)
{
index = (int) id[i] + (index * 32);
}
return index % tableSize;
}
void hashtable::destroyTable()
{
for(int i = 0; i < tableSize; i++)
{
hashEntry * head = famTable[i];
hashEntry * curr;
while(head)
{
curr = head->next;
head->next = NULL;
delete head;
head = curr;
}
}
delete [] famTable;
}
// -------------------------------------------------------------
// Operators
// -------------------------------------------------------------
ostream & operator << (ostream & buffer, hashtable & entry)
{
hashtable::hashEntry * curr;
for(int i = 0; i < entry.tableSize; i++)
{
buffer << "table[" << i << "]:" << endl << "List:" << endl;
for(curr = entry.famTable[i]; curr; curr = curr->next)
{
buffer << curr->data;
}
buffer << setw(20) << right << setfill('-') << "" << endl;
}
return buffer;
}
const hashtable & hashtable::operator = (const hashtable & temp)
{
if(this == & temp)
{
return *this;
}
else
{
destroyTable();
famTable = new hashEntry * [MAX_CAP];
tableCount = temp.tableCount;
tableSize = temp.tableSize;
for(int i = 0; i < tableSize; i++)
{
if(temp.famTable[i] == NULL)
{
famTable[i] = NULL;
}
else
{
famTable[i] = new hashEntry(temp.famTable[i]->data);
hashEntry * curr = temp.famTable[i]->next;
hashEntry * tNext = famTable[i];
while(curr)
{
tNext->next = new hashEntry(tNext->data);
curr = curr->next;
tNext = curr->next;
}
tNext->next = NULL;
}
}
return * this;
}
}
hashtable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <iostream>
#include <iomanip>
#include "family.h"
using namespace std;
class hashtable
{
private:
// Hash Entry Node
struct hashEntry
{
// Constructors/Destructors
hashEntry(const family & fam)
{
data = fam;
next = NULL;
}
family data;
hashEntry * next;
};
const size_t MAX_CAP = 7877;
int tableCount;
int tableSize;
hashEntry ** famTable;
public:
// Constructors/Destructors
hashtable();
hashtable(int);
~hashtable();
// Accessors
family * lookup(char *) const;
int getSize() const;
void dumpTable();
// Mutators
void insert(char *, const family &);
size_t hash(char *) const;
void destroyTable();
// Operators
friend ostream & operator << (ostream &, hashtable &);
const hashtable & operator = (const hashtable &);
};
#endif
housinghelper.cpp
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include "familymgr.h"
using namespace std;
int main(int argc,char** argv)
{
if (argc != 2)
{
cout << "Usage: " << argv[0] << " <datafile>" << endl;
exit(0);
}
// family manager object;
familymgr familyMgr;
// Read the data
const int MAX_LINE = 64;
char* datafile = argv[1];
ifstream infile(datafile);
char line[MAX_LINE];
char id[MAX_LINE];
char name[MAX_LINE];
int members;
char friend1[MAX_LINE];
char friend2[MAX_LINE];
char friend3[MAX_LINE];
if (infile.is_open())
{
while (infile.getline(line,MAX_LINE) )
{
char* s;
// ID -- Family ID: <id>
s = strchr(line,':') + 2; // Skip the space
strncpy(id,s,MAX_LINE);
// Name
infile.getline(line,MAX_LINE);
s = strchr(line,':') + 2; // Skip the space
strncpy(name,s,MAX_LINE);
// members
infile.getline(line,MAX_LINE);
s = strchr(line,':') + 2; // Skip the space
members = atoi(s);
// friends
infile.getline(line,MAX_LINE);
s = strchr(line,':') + 2; // Skip the space
char* friendPtr;
friendPtr = strtok(s," ");
if (friendPtr != nullptr)
strncpy(friend1,friendPtr,MAX_LINE);
else
friend1[0] = '';
friendPtr = strtok(nullptr," ");
if (friendPtr != nullptr)
strncpy(friend2,friendPtr,MAX_LINE);
else
friend2[0] = '';
friendPtr = strtok(nullptr," ");
if (friendPtr != nullptr)
strncpy(friend3,friendPtr,MAX_LINE);
else
friend3[0] = '';
infile.getline(line,MAX_LINE);
if (strcmp(line,"---")!=0) {
cout << "Error parsing the file" << endl;
}
// Add the family to the family manager
family* famPtr = new family(id,name,members);
famPtr->addFriend(friend1);
famPtr->addFriend(friend2);
famPtr->addFriend(friend3);
familyMgr.addFamily(*famPtr);
delete famPtr;
}
infile.close();
familyMgr.printAllFamilies();
// familyMgr.printGroup("Smith001");
familyMgr.printSmallCircle("Smith001");
familyMgr.printSmallCircle("Hall001");
familyMgr.printSmallCircle("Noel003");
}
return(0);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.