You are here:

C++/Data Structures and Lists

Advertisement


Question
QUESTION: I'm trying to grasp the concept, I have to create a shopping list asking a user to provide items, then sort by price and priority, also ask the user to provide a budge and delete according to the budge. The list should contain price, priority, and category. this is what I have so far:

#include <iostream>
#ifndef DLIST
#define DLIST

typedef int ElementType;

class List
{
 public:
 List(int maxSize = 1024);

Can you  help me, please

ANSWER: Sara, your code did not come through. Please post a follow up with the code you want me to look at.

---------- FOLLOW-UP ----------

QUESTION: #include <iostream>
#ifndef DLIST
#define DLIST

typedef int ElementType;

class List
{
public:
List(int maxSize = 1024);


~List();

List(const List &origList);

const List & operator=(const List & rightHandSide);

bool empty() const;

void insert(ElementType item, int pos);

void erase(int pos);

void display(ostream & out) const;

private:

int mySize;
int myCapacity;
ElementType * myArray

};

ostream & operator<< (ostream & out, const List &aList);

#endif

#include <cassert>
#include <new>
using namespace std;

#include "DList.h"

List::List(int maxSize)
: mySize(0), myCapacity(maxSize)
{
  myArray + new(nothrow) ElementType[maxSize];
  assert(myArray != 0);
}

List::~List()
{
  delete [] myArray;
}

List::List(const List & origList)
: mySize(origList.mySize), myCapacity(origList.myCapacity)
{
  myArray = new(nothrow) ElementType[myCapacity];
  
  if (myArray != 0)
     for(int i = 0; i < mySize; i++)
        myArray[i] = origList.myArray[i];
  else
  {
     cerr << "***Inadequate memory to allocate storage for list ***\n";
     exit(1)
   }
}

cost List & List::operator=(const List & rightHandSide)
{
  if (this != &rightHandSide)
  {
     if (myCapacity != rightHandSide.Capacity)
     {
        delete[] myArray;
        myCapacity = rightHandSide.myCapacity;
        myArray = new(nothrow) ElementType[myCapacity];

        if (myArray ==0)
        {
         cerr << "*Inadequate memory to allocate stack ***\n";
         exit(1)
        }
     }
     mySize = rightHandSide.mySize;
     for(int i = 0; i <mySize; i++)
        myArray[i] = rightHandSide.myArray[i];
   }
   return *this;
}

somehow I don't think I did it right according to what I was suppose to do, can you help me out and explain..

Answer
Hello Sara

You've made a good start on the assignment. I can see that you understand the ideas of memory management, and copy constructors, and operator overloading. Those are elements from a more advanced C++ course. Now you just need to continue on the same path. I've corrected a few compiler errors in your code, and I've explained some things in comments in the code.

Now you need to get on with the rest of the assignment.

You need to complete the insert method, and my advice is to start without the pos parameter unless the assignment requires it. Even then, I would do the assignment without the pos parameter, and once it is working, add the pos feature in. Remember to handle the case for when there is no space for an element. Your options in that case are to report and error, and don't do the insertion, or reallocate the higher capacity for the myArray data store. I would do the reallocation, because without it you really have nothing more than a simple C array wrapped in a class. It is the ability to grow your data storage that gives you a truly useful container class.

Next you will need to add a sort feature to the array. For that you will need to add a comparison operator to your ShoppingItem. I've given you the function declaration for that.

Do you know how to sort? I recommend a simple selection sort.

Once you get the insertion and sorting done, then it is time to add a function to trim the list based on budget. Probably you want to start deleting the lowest priority items until the total of the shopping list is less than or equal to the budget. If you do your sorting so that the lowest priority items are at the end, it should be easy to trim the list. Perhaps sort in descending priority and ascending price. In other words, when comparing Shopping items, compare only on priority, and if the priorities are equal then compare on price.

That's my advice to you. There is still a lot to do on this assignment, but what you have done so far is good, so I know you have the ability to finish it. I'll be around to give you more advice if you want it.

Best regards
Zlatko

#include <iostream>
using namespace std;

#ifndef DLIST
#define DLIST

/* you need to create elements with a price and a priority,
so lets start with that. It will be no harder than using integers
so I removed this: typedef int ElementType;
*/
struct ShoppingItem
{
   ShoppingItem()
   {
       myPrice = 0;
       myPriority = 0;
   }
   ShoppingItem(float price, int priority)
   {
       myPrice = price;
       myPriority = priority;
   }
   float myPrice;
   int myPriority;

   bool operator<(const ShoppingItem& rhs)
   {
       // TODO add in the real comparison logic
       return true;
   }

   void display(ostream & out) const
   {
       // TODO add display logic
   }
};

typedef ShoppingItem ElementType;

/*
A list implies a data structure having data items connected by
links, so the name is misleading. A name like ShoppingList might
be better.

Here you are using an array, and that is a reasonable choice, but
be sure about what your instructor wants. If they will
accept an array, then your work is OK. If they want a linked list,
then you have to start over.
*/
class List
{
public:
   List(int maxSize = 1024);
   ~List();

   List(const List &origList);
   const List & operator=(const List & rightHandSide);

   bool empty() const;

   /*
   For insert:
   You will need to decide what to do if the user of List
   gives a pos is past the end
   of the current array. You have some options:
   1) put the item at the end of the myArray
   2) make dummy elements between the end of the myArray and pos
   3) report an error and don't do the insert
   4) get rid of the pos parameter and just have insert put
   elements to the end of the myArray

   Also, consider passing in
   const ElementType& item
   */
   void insert(ElementType item, int pos);

   void erase(int pos);

   void display(ostream & out) const;

private:

   int mySize;
   int myCapacity;
   ElementType * myArray;

};

// TODO implement this function
ostream & operator<< (ostream & out, const List &aList);

#endif

#include <cassert>
#include <new>
using namespace std;

/*
#include "DList.h"
I've put DList.h into the cpp source file just for convenience. You
can separate them out if you like.
*/

List::List(int maxSize)
: mySize(0), myCapacity(maxSize)
{
   myArray = new(nothrow) ElementType[maxSize];
   assert(myArray != 0);
}

List::~List()
{
   delete [] myArray;
}

List::List(const List & origList)
: mySize(origList.mySize), myCapacity(origList.myCapacity)
{
   myArray = new(nothrow) ElementType[myCapacity];

   if (myArray != 0)
       for(int i = 0; i < mySize; i++)
         myArray[i] = origList.myArray[i];
   else
   {
       cerr << "***Inadequate memory to allocate storage for list ***\n";
       exit(1);
   }
}

const List & List::operator=(const List & rightHandSide)
{
   if (this != &rightHandSide)
   {
       /*
       The check
       if (myCapacity != rightHandSide.myCapacity)
       is OK, but I would do
       if (myCapacity < rightHandSide.mySize)

       In other words, reallocate this object's data storage area
       only if it cannot hold all the data in the rightHandSide.

       To me it would not be important that this object has the same
       capacity as the rightHandSide. It would only matter that this
       gets a copy of the rightHandSide data. That's just my opinion.
       */
       if (myCapacity != rightHandSide.myCapacity)
       {
         delete[] myArray;
         myCapacity = rightHandSide.myCapacity;
         myArray = new(nothrow) ElementType[myCapacity];

         if (myArray ==0)
         {
         cerr << "*Inadequate memory to allocate stack ***\n";
         exit(1);
         }
       }
       mySize = rightHandSide.mySize;
       for(int i = 0; i <mySize; i++)
         myArray[i] = rightHandSide.myArray[i];
   }
   return *this;
}

void List::insert(ElementType item, int pos)
{
   // TODO add insert code here.
}

int main(void)
{
   List list;
   list.insert(ElementType(1.00, 1), 0);
}

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Zlatko

Expertise

No longer taking questions.

Experience

No longer taking questions.

Education/Credentials
No longer taking questions.

©2016 About.com. All rights reserved.