Solved

Link List and Insertion Sort

Posted on 2003-12-06
9
1,421 Views
Last Modified: 2013-12-14
Hi all,

Here's another assignment I am working on. I've already designed the main classes and the required code, but am hitting blocks on executing the main(). I've used "Insertion sort" to sort by alphabetical order by LASTNAME (as required by the question). The assignment asks me to use the string class for the individual piece of information (like lastname, firstname, occup, address, phone number etc).

EXPERTS PLEASE LOOK INTO MY CODE AND give me some advice on how I could pass the info in the main program (I've listed error that I am getting too)

******************************************************************
The problem is to produce an information manager similiar to a rolodex. A physical rolodex is made up of cards arranged in alphabetical order. Each of the cards contains some information, usually names, addresses, phone numbers and type of business (why the person is in the rolodex). The physical mechanism of using a rolodex is turning the group of cards and flipping through them. When the last card is read, the rolodex is then at the start of the list since a rolodex is built on a circular track.
These are the fields in the Rolodex:

 First:  Last:  Occupation:  Address:  Phone:
 
The rolodex should be stored in alphabetic sorted order by last name.
Entries can be added, deleted, and changed. Also one should be able to search the rolodex for specific information. The list should also be able to be printed/displayed.

A string class should be used for the individual pieces of information. The cards should also be represented by a user defined class. This means that idea of a container class should be used.


**************************************************

Here's my code

#include <iostream>
#include <string>

using namespace std;

class RolodexCard {
 private:
   string firstname;
   string lastname;
   string occupation;
   string address;
   string phone_number;
   RolodexCard * next;
   int rolodex_record_number;
   static int rolodex_counter;  

public:      
   RolodexCard(string,string,string,string,string);
   void set_next(RolodexCard *);
   RolodexCard * get_next();
   bool operator > (RolodexCard& op1);
   void print_output();
};


RolodexCard::RolodexCard(string fname, string lname, string occup, string addr,
string phone_num)
{
      firstname = fname;
      lastname = lname;
      occupation = occup;
      address = addr;
      phone_number = phone_num;
      next = 0;
}

void RolodexCard::set_next(RolodexCard* next_info)
{
    next = next_info;  
}

RolodexCard * RolodexCard::get_next()
{
      return next;
}

bool RolodexCard::operator > (RolodexCard & op1)
{
      bool isGreat = false;

      if( lastname > op1.lastname )
            
            isGreat = true;

      return isGreat;
}

void RolodexCard::print_output()
{
    cout <<" ******************************** " << endl;
    cout << "FIRSTNAME " << "     " << firstname << endl;
    cout << "LASTNAME " << "     " << lastname << endl;
    cout << "OCCUPATION" << "      " << occupation << endl;
    cout << "ADDRESS " << " " << address << endl;
    cout << "PHONE NUMBER " << " " << phone_number << endl;
}


class RolodexFile
{
private:
   RolodexCard * head;
   RolodexCard * tail;
public:
   void AddInOrder(RolodexCard *newCard);
   void AddAtHead(RolodexCard *newCard);
   void AddAtTail(RolodexCard *newCard);
   void DisplayRolodex();
   void Erase();
   RolodexFile(); // default CTOR
   ~RolodexFile();  // default DTOR
};



RolodexFile::RolodexFile()
{
      head = 0;
      tail = 0;
}

RolodexFile::~RolodexFile()
{
      Erase();
}

void RolodexFile::AddInOrder(RolodexCard *newCard)  // This is Insertion Sort(by lastname )
{

      RolodexCard * nextptr = head;
      RolodexCard * lastptr = 0;

      while(nextptr!=0 && (*newCard) > (*nextptr))
      {
            lastptr = nextptr;
            nextptr = nextptr->get_next();
      }

      if (nextptr == 0)   // hit end of list, AddAtTail,
               {
            AddAtTail(newCard);
      }
      else
      {
            if (lastptr == 0)   // this means to add at the beginning
            {
                  AddAtHead(newCard);
            }

            else              // this means tp add at the middle
            {
                  newCard->set_next(nextptr);
                    lastptr->set_next(newCard);
            }
      }
      
}



void RolodexFile::AddAtTail(RolodexCard *newCard)
{
    if (tail == 0)
            head = newCard;
      else
            tail->set_next(newCard);

      tail=newCard;
}


void RolodexFile::AddAtHead(RolodexCard *newCard)
{
      if (head==0)
            tail = newCard;

      newCard->set_next(head);
      head = newCard;
}


void RolodexFile::Erase()
{
      RolodexCard * temp;

      while(head)
      {
            temp = head;
            head = head->get_next();

            delete temp;
      }

      tail = 0;
}


void RolodexFile::DisplayRolodex()
{
    RolodexCard * temp = head;
    if(temp != 0)
    {
       while (temp->get_next() != 0)
       {
          temp = temp->get_next();
          temp->print_output();
       }
    }
    else
    cout << "EVERYTHING Erased NO LIST to PRINT ******* " << endl;

}

int RolodexCard::rolodex_counter =  0;


void main()
{
  RolodexFile r_file;
  r_file.AddInOrder("Tony","Hansen","Writer","12E.St. NY 33333","555-9999");
  r_file.AddInOrder("John","Smyth","Computer Hardware","CMU Pittsburg","555-1234");
  r_file.DisplayRolodex();
}


***************************************

ERROR that I get :

proj2.cpp: In function `int main(...)':
proj2.cpp:189: no matching function for call to `RolodexFile::AddInOrder (char[5], char[7], char[7], char[17], char[9])'
proj2.cpp:98: candidates are: RolodexFile::AddInOrder(RolodexCard *)
proj2.cpp:190: no matching function for call to `RolodexFile::AddInOrder (char[5], char[6], char[18], char[14], char[9])'
proj2.cpp:98: candidates are: RolodexFile::AddInOrder(RolodexCard *)

0
Comment
Question by:anushan
  • 4
  • 3
  • 2
9 Comments
 
LVL 1

Expert Comment

by:meow00
Comment Utility
Hi,

   I would try to pass a "pointer to a RolodexCard" rather than 5 strings in the AddInOrder function. Since the AddInOrder function is declared to take a "pointer to RolodexCard".
The following main() program seems to work .....

meow.

----------------------------------------------------------------------------
void main()
{
  RolodexFile r_file;
  RolodexCard *TempCard = new RolodexCard("Tony","Hansen","Writer","12E.St. NY 33333","555-9999");
  r_file.AddInOrder(TempCard);

  TempCard = new RolodexCard("John","Smyth","Computer Hardware","CMU Pittsburg",
"555-1234");
  r_file.AddInOrder(TempCard) ;

  r_file.DisplayRolodex();
}
0
 

Author Comment

by:anushan
Comment Utility
Thanks...I feel stupid..darn why didn't I think of that :)...I still have a few questions as my program evolves..please bear with me ....once am done..I will close this session.

thanks
0
 

Author Comment

by:anushan
Comment Utility
Hi again,

As I develop my program....I have one more problem...I am trying to get the info for the fields from the user instead of hard coding it in the main() program. So here is where my problem lies, when the User inputs the Address field (which has space between words), only the first word is taken by the string ?? I put a cin.ignore(80,'\n') between the cin statements so that it removes the first 80 characters of what is left in the buffer
UNLESS there is a newline (\n).  This still doesn't solve my problem. I want to absorb the FULL Address

 e.g:  "CMU Computer Services Pittsburg, PA"

When I input this for address: , it only takes "CMU" and omits the rest...how do I solve this problem???

Here is my code for the AddInOrder() function ( which is the only function modifed from the previous code that I posted )  
******************************************************************

void RolodexFile::AddInOrder()  // This is Insertion Sort
{
        string _fname;string _lname;string _occup; string _addr; string _phone;
        cout << "\nADDING A NEW CARD\n";
        cout << "Firstname: ";
        cin >> _fname;
        cin.ignore(80,'\n');
        cout << "Lastname: ";
        cin >> _lname;
        cin.ignore(80,'\n');
        cout << "Occupation: ";
        cin >> _occup;
        cin.ignore(80,'\n');
        cout << "Address: ";
        cin >> _addr;
        cin.ignore(80,'\n');
        cout << "Phone number: ";
        cin >> _phone;
        cin.ignore(80,'\n');
        RolodexCard * newCard = new RolodexCard(_fname,_lname,_occup,_addr,_phone);
        RolodexCard * nextptr = head;
        RolodexCard * lastptr = 0;

        while(nextptr!=0 && (*newCard) > (*nextptr))
        {
                lastptr = nextptr;
                nextptr = nextptr->get_next();
        }

        if (nextptr == 0)   // hit end of list, AddAtTail, so even if it didn't enter the loop, it should atleast add at the Tail
        {
                AddAtTail(newCard);
        }
        else
        {
                if (lastptr == 0)   // this means to add at the beginning
          {
               AddAtHead(newCard);
          }

          else              // this means tp add at the middle
          {
               newCard->set_next(nextptr);
                 lastptr->set_next(newCard);
          }
     }
     
}



0
 

Author Comment

by:anushan
Comment Utility
PS:  I would like to only use the string datatype for each of the fields, as it a requirement for the assignment
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 1

Expert Comment

by:meow00
Comment Utility
Hello,

  What I would do is :
--------------------------------
  //     cin >> _addr;
  //     cin.ignore(80,'\n');
  getline(cin,_addr) ;
---------------------------
  in the void RolodexFile::AddInOrder().

  and of course, add  " void AddInOrder() ;" in the RolodexFile class, and call
  "r_file.AddInOrder() ;" in main().

  This seems to work for me ......

meow.
 
0
 

Author Comment

by:anushan
Comment Utility
Hi,

I have developed my code further....and am having trouble debugging it in the "Delete_node" function....PLEASE HELP !!...I am getting a non-lvalue in assignment  ERROR

I don't even know what that means...and am running out of time in the assignment..Please help!!

******************************************************************
Here's the code:

#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

class RolodexCard {
 private:
   string firstname;
   string lastname;
   string occupation;
   string address;
   string phone_number;
   RolodexCard * next;
   int rolodex_record_number;
   static int rolodex_counter;

public:
   RolodexCard(string,string,string,string,string);
   void set_next(RolodexCard *);
   RolodexCard * get_next();
   string get_lname();
   bool operator > (RolodexCard& op1);
   void print_output();
};


RolodexCard::RolodexCard(string fname, string lname, string occup, string addr,
string phone_num)
{
        firstname = fname;
        lastname = lname;
        occupation = occup;
        address = addr;
        phone_number = phone_num;
        rolodex_record_number = ++ rolodex_counter;
        next = 0;
}

void RolodexCard::set_next(RolodexCard* next_info)
{
    next = next_info;
}

RolodexCard * RolodexCard::get_next()
{
        return next;
}

string RolodexCard::get_lname()
{
        return lastname;
}

bool RolodexCard::operator > (RolodexCard & op1)
{
        bool isGreat = false;

        if( lastname > op1.lastname )

                isGreat = true;

        return isGreat;
}

void RolodexCard::print_output()
{
    cout << "***********************************"<<endl;
    cout << "Firstname :" << " "  <<  firstname << endl;
    cout << "Lastname  :" << " "  << lastname << endl;
    cout << "Occupation:" << " "  << occupation << endl;
    cout << "Address   :" << " "  << address << endl;
    cout << "Phone     :" << " "  << phone_number << endl;
 }
}

void RolodexCard::set_next(RolodexCard* next_info)
{
    next = next_info;
}

RolodexCard * RolodexCard::get_next()
{
        return next;
}

string RolodexCard::get_lname()
{
        return lastname;
}

bool RolodexCard::operator > (RolodexCard & op1)
{
        bool isGreat = false;

        if( lastname > op1.lastname )

                isGreat = true;

        return isGreat;
}

void RolodexCard::print_output()
{
    cout << "***********************************"<<endl;
    cout << "Firstname :" << " "  <<  firstname << endl;
    cout << "Lastname  :" << " "  << lastname << endl;
    cout << "Occupation:" << " "  << occupation << endl;
    cout << "Address   :" << " "  << address << endl;
    cout << "Phone     :" << " "  << phone_number << endl;
 }
class RolodexFile
{
private:
   RolodexCard * head;
   RolodexCard * tail;
   RolodexCard * currptr;
public:
   void AddInOrder();
   void AddAtHead(RolodexCard *newCard);
   void AddAtTail(RolodexCard *newCard);
   void DeleteCard();
   int verify_delete();
   void DeleteNode(RolodexCard *prevptr);
   RolodexCard * Previous(RolodexCard * index);
   void DisplayRolodex();
   void Erase();
   RolodexFile(); // default CTOR
   ~RolodexFile();  // default DTOR
};



RolodexFile::RolodexFile()
{
        head = 0;
        tail = 0;
        currptr = head;
}

RolodexFile::~RolodexFile()
{
        Erase();
}

void RolodexFile::AddInOrder()  // This is Insertion Sort
{
        string _fname;string _lname;string _occup; string _addr; string _phone;
        cout << "\nADDING A NEW CARD\n";
        cout << "Firstname: ";
        getline(cin,_fname);
        cout << "Lastname: ";
        getline(cin,_lname);
        cout << "Occupation: ";
        getline(cin,_occup);
        cout << "Address: ";
        getline(cin,_addr);
        cout << "Phone number: ";
        getline(cin,_phone);
        RolodexCard * newCard = new RolodexCard(_fname,_lname,_occup,_addr,_phone);
        RolodexCard * nextptr = head;
        RolodexCard * lastptr = 0;

        while(nextptr!=0 && (*newCard) > (*nextptr))
        {
                lastptr = nextptr;
                nextptr = nextptr->get_next();
        }

        if (nextptr == 0)   // hit end of list, AddAtTail, so even if it didn't enter the loop, it should atleast add at the Tail
        {
                AddAtTail(newCard);
        }
        else
        {
                if (lastptr == 0)   // this means to add at the beginning
                {
                        AddAtHead(newCard);
                }

                else              // this means tp add at the middle
                {
                        newCard->set_next(nextptr);
                        lastptr->set_next(newCard);
                }

        }

}



void RolodexFile::AddAtTail(RolodexCard *newCard)
{
    if (tail == 0)
        head = newCard;
    else
        tail->set_next(newCard);

    tail=newCard;
}


void RolodexFile::AddAtHead(RolodexCard *newCard)
{
        if (head==0)
        tail = newCard;

        newCard->set_next(head);
        head = newCard;
}


void RolodexFile::DeleteCard()
{
 string _lname;
 currptr = head; // move currptr to head of list
 RolodexCard * prevptr = 0; // initialize previous ptr to NULL
 cout << "\nEnter the Lastname of the card that you want to delete: ";
 getline(cin,_lname);
 while((currptr != 0) && (currptr->get_lname() != _lname))
 {
   prevptr = currptr;

        }

}



void RolodexFile::AddAtTail(RolodexCard *newCard)
{
    if (tail == 0)
        head = newCard;
    else
        tail->set_next(newCard);

    tail=newCard;
}


void RolodexFile::AddAtHead(RolodexCard *newCard)
{
        if (head==0)
        tail = newCard;

        newCard->set_next(head);
        head = newCard;
}


void RolodexFile::DeleteCard()
{
 string _lname;
 currptr = head; // move currptr to head of list
 RolodexCard * prevptr = 0; // initialize previous ptr to NULL
 cout << "\nEnter the Lastname of the card that you want to delete: ";
 getline(cin,_lname);
 while((currptr != 0) && (currptr->get_lname() != _lname))
 {
   prevptr = currptr;

   currptr = currptr->get_next();
 }

 if (currptr != 0)  // if currptr is not 0, then match was found
 {
   cout<<"\nCARD FOUND\n";
   tail->print_output;
   if (verify_delete())
   {
     DeleteNode(prevptr);
     cout << "\nCARD DELETED\n";
   }
   else
   {
     cout << "\nCARD NOT DELETED\n";
   }
 }
 else
 {
   cout << "\nNO MATCH FOUND. NO CARD DELETED.\n";
 }
}


int RolodexFile::verify_delete()
{
 char YesNo;
 cout << "\nDo you wish to delete this card??(Y/N)";
 cin >>YesNo;
 if((YesNo=='Y') || (YesNo =='y'))
 {
   return(1);
 }
 else
 {
  return(0);
 }

}


void RolodexFile::DeleteNode(RolodexCard *prevptr)
{
 RolodexCard * temp;
 if (prevptr == head) // case 1 delete head of list
 {
    temp = head;
    head = head->get_next();
    delete temp;
 }
 else if( prevptr->get_next() == 0) // case 2 delete end of list
 {
    temp = prevptr;
    prevptr = Previous(prevptr);
    prevptr->get_next() = 0;
   delete temp;
   tail = prevptr;
 }
 else       // case 3 delete from middle of list
 {
   temp = Previous(prevptr);
   temp->get_next() = prevptr->get_next();
   delete prevptr;
 }

 currptr = head;
}

RolodexCard* RolodexFile::Previous(RolodexCard * index)
{
 RolodexCard * temp = head;
 if(index == head) // special case if index is the head
 {
   return head;
 }
 while(temp->get_next() != index)
 {
   temp = temp->get_next();
 }
 return temp;
}


void RolodexFile::Erase()
{
        RolodexCard * temp = head;
        currptr = head;

        while(currptr)
        {
          currptr = currptr->get_next();
          delete temp;
          temp = currptr;
        }
}


void RolodexFile::DisplayRolodex()
{
    currptr = head;
    if(currptr != 0)
    {
       cout << "*************************************\n";
       cout << "** Displaying the Rolodex Cards ***\n";
       while (currptr)
       {
          currptr->print_output();
          currptr = currptr->get_next();
       }
    }
    else
    cout << "EVERYTHING Erased NO LIST to PRINT ******* " << endl;
    currptr = head;
}


int RolodexCard::rolodex_counter =  0;

void main()
{
  RolodexFile r_file;
  r_file.AddInOrder();
  r_file.AddInOrder();
  r_file.DisplayRolodex();
}


********************************************

The error I am getting is as follows:

proj2.cpp: In method `void RolodexFile::DeleteNode(class RolodexCard *)':
proj2.cpp:241: non-lvalue in assignment
proj2.cpp:248: non-lvalue in assignment


I am running out of time on this...and the experts help would be appreciated tremendously!!

thanks
0
 
LVL 49

Expert Comment

by:DanRollins
Comment Utility
Are you sure you posted the correct code?  The only compile error that I get is in main():

      error C2660: 'AddInOrder' : function does not take 5 parameters

-- Dan
0
 
LVL 49

Expert Comment

by:DanRollins
Comment Utility
and after fixing those errors like so..

    RolodexCard* prRC= new RolodexCard("Tony","Hansen","Writer","12E.St. NY 33333","555-9999");
    r_file.AddInOrder( prRC );

Another remaining problem I see is in your DisplayRolodex function which needs work.  I think it is not displaying the first card.

-- Dan
0
 
LVL 1

Accepted Solution

by:
meow00 earned 250 total points
Comment Utility
Hi,

   There are several things :
1. in the DeleteCard:
-----------------------------
 if (currptr != 0)  // if currptr is not 0, then match was found
 {
   cout<<"\nCARD FOUND\n";
   tail->print_output;
----------------------------
   "print_output" should be "print_output()"

2.  In the DeleteNode, I would do :
-----------------------------------------
 else if( prevptr->get_next() == 0) // case 2 delete end of list
 {
    temp = prevptr;
    prevptr = Previous(prevptr);
//    prevptr->get_next() = 0;
     prevptr->get_next() ;
   delete temp;
   tail = prevptr;
 }
 else       // case 3 delete from middle of list
 {
   temp = Previous(prevptr);
//   temp->get_next() = prevptr->get_next();
   delete prevptr;
 }
-----------------------------------------------------
  I am not quite sure what you want to do here,  but you can NOT assign a function a value because a function is l-value. "temp->get_next()" and "prevptr -> get_next()" are member functions, we are not supposed to assign values to them.

 It seems to work for me now after the above changes.......

meow......

 
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
How to install Selenium IDE and loops for quick automated testing. Get Selenium IDE from http://seleniumhq.org (http://seleniumhq.org) Go to that link and select download selenium in the right hand columnThat will then direct you to their downlo…
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now