Write a program that maintains a list of travelers using a singly linked list. E

Question

Write a program that maintains a list of travelers using a singly linked list. Each node in the list will correspond to one traveler. Each node in the list will have two links: one for linking travelers alphabetically by last name and the other for linking traveler alphabetically by state. Implementation: Implement the above program using only one singly linked list. Each node in the list will have two links. One will be used for linking the nodes sorted alphabetically by last name. The second will be used for linking the nodes sorted alphabetically by state name and then within the state by last name. (Since, a state may have more than one entry associated with it. Multiple entries within a state will be sorted by last name). The list will be kept sorted at all times. The data will be read from an input text file one traveler at a time. After inputting a traveler data, the program will create a node for the traveler and insert it in the linked list such that the list will remain sorted at the end of insertion. At the end of inputting data, the program will output results to an output text file. The output will consists of two listings: one lists travelers alphabetically by last name and the second lists travelers alphabetically by state. Input The program will input data from a text file. Each traveler data will comprise the following:

Explanation / Answer

#include #include using namespace std; //typedef NodeType * NodePtr; struct NodeType; //forward declaration typedef NodeType * NodePtr; //for passing parameters as a bundle struct RecType { string lname; string fname; string state; }; //for linking an node (entry) struct NodeType { string lname; string fname; string state; NodePtr nlink; NodePtr slink; }; class TravelerList { private: NodePtr nameHead; NodePtr stateHead; public: TravelerList ( ); void addEntry (RecType r); void outputByName (ofstream & f ); void outputByState (ofstream & f ); }; TravelerList::TravelerList ( ) { nameHead = NULL; stateHead = NULL; } void TravelerList::addEntry(RecType r) { NodePtr cur,prev; //Create an entry NodePtr newPtr = new NodeType; //fill up the entry newPtr->lname = r.lname; newPtr->fname = r.fname; newPtr->state = r.state; newPtr->slink = NULL; newPtr->nlink = NULL; //Link the entry using nlink at its appropriate place //case: empty list if (nameHead == NULL) { nameHead = newPtr; } //case: head insertion else if (r.lname lname) { newPtr->nlink = nameHead; nameHead = newPtr; } //case: mid and end insertion: else { //use the cur to locate the point of insertion //let prev walk behind it. for (prev=nameHead, cur=nameHead->nlink; cur != NULL; prev=prev->nlink, cur=cur->nlink) { if (newPtr->lname lname) break; } //do the insertion using prev newPtr->nlink = prev->nlink; prev->nlink = newPtr; } //Link the entry using slink at its appropriate place //For linking state entries, the expression in the if statement for the case //of head insertion and mid/end insertion will be different. //The if expression both for head insertion and //mid/end insertion will be something like below: // //if ( (newPtr->state state) || // ( (newPtr->state == cur->state) && (newPtr->lname lname) ) ) //{ // //} } void TravelerList::outputByName (ofstream & f ) { for (NodePtr cur=nameHead; cur != NULL; cur = cur ->nlink) { } } void TravelerList::outputByState (ofstream & f ) { for (NodePtr cur=stateHead; cur != NULL; cur = cur ->slink) { //disply the node } } void main ( ) { ifstream fin("input.txt"); ofstream fout ("output.txt"); RecType rec; //createTravelerList object TravelerList list; string n; //User Input char buf[102]; fin.getline(buf,100); rec.lname = buf; while (!fin.eof()) { fin.getline(buf,100); rec.fname = buf; fin.getline(buf,100); rec.state = buf; //process the person list.addEntry (rec); fin.getline(buf,100); rec.lname = buf; } list.outputByName(fout); list.outputByState(fout); }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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