Hi, I have some problem to implement the constructors from set.h. There was no problem to implement the empty constructor. But as for:

Set(int a[], int n);
I have some problem. It is supposed to use insert() function from node.cpp. And since the class Set is friend a friend to class Node it should have access to the private members in class Node right?

Well, anyway I tried to implement Set(int a[], int n);
with following code

Set::Set(int a[], int n) {
    Set p;
    p.insert(a[0]); 
}

and I get compile error saying "undefined reference to Set::insert(int);

Below is the code I have in use.
set.h

#include "node.h"
#include <iostream>

class Set {
public:
   Set ();
   Set (int a[], int n);
   Set (const Set& b);
   ~Set ();
private:

   Node *header;
   friend std::ostream& operator << (std::ostream& os, const Set& b);
   void insert (int value);
   void del (int value);
};

node.h

#include <iostream>

class Node {
public:
   Node(int, Node*); //constructor
   Node *insert(int value); //function
private:
   int value;
   Node *next;

   friend class Set;
   friend std::ostream& operator << (std::ostream &os, const Set &theSet);
};

node.cpp

#include "node.h"
#include <cassert>    //assert

Node::Node (int nodeVal, Node *nextPtr) : value (nodeVal), next (nextPtr)
{
//   std::cout << "Constructor Node" << std::endl;
}

Node *Node::insert (int newValue) {
    next = new Node (newValue, next);
    assert (next != 0);
    return next;
}

In the constructor you are calling p.insert() where p is an object of class Set. Presumably you want p to be an object of class Node?

What is the error you get?

A common problem with linked lists is not setting the next node to the desired value, such as 0 in your example.

Hmm.. I think i'm heading on the wrong direction. I'll be back when I've evaluated the question and tried a few thing.

Why would Node have an insert method?

The insert method declared doesn't insert anything anywhere. It just declares a new Node, which seems dubious.

Move the insert function to Set itself. Basically you can make the Set class a modified List class (or a wrapper around a List class), but it has the added restriction of requiring that there be no duplicate data values within a given Set (at least in implementations I've seen uinque variable values are a requirment. MultiSets can have duplicates). If you set the Set up this way, you may want an ordered list (a tree may be another base data structure you could use, but trees are generally a bit more confuscating than lists for beginners, so I'd suggest a list) to make searching for duplicates easier. It would help in ordering the list if the data variables within the Node have to have a less than operator overloaded (ints and other native math types have that operator available already).

Set
   Node * header;  //the start of a list
   insert(value)
      Node * newNode = new Node;
      newNode-> data = value;
      newNode->next = NULL;
      //insertion code here

Lerner:

Yep, i'm going to write a class that implement a sorted Set with unique values. You seems to know what I'm going to code. Btw, is that code example you shown a way to make constructor? Anyway here's the whole header file for Set that i'm supposed to implement.

#ifndef SET_H
#define SET_H

#include "node.h"
#include <iostream>

class Set {
public:
   Set ();
   Set (int a[], int n);
   Set (const Set& b);
   ~Set ();

//   bool empty () const;
//   int cardinality() const;
//   bool member (int x) const;
//
//   Set operator+ (const Set& b);
//   Set operator* (const Set& b);
//   Set operator- (const Set& b);
//   Set operator+(int x) const;
//   Set operator-(int x) const;
//   bool operator<=(const Set& b) const;
//   bool operator==(const Set& b) const;
//   bool operator<(const Set& b) const;
//   Set& operator=(const Set& b);
//
private:

   Node *header;
   friend std::ostream& operator << (std::ostream& os, const Set& b);
   void insert (int value);
   void del (int value);
};
#endif

I guess I did the constructor implementation in a wrong way. Since I don't you use the void insert(int value) nor have I implemented it yet :/

and here's the Set.cpp file of what I've implemented so far. It does what I want. It adds to a values to a Node object. But I'm uncertain if I have done it correct. Because the question says that I'm supposed to call function with say and object R of the class Set. E.g. R.insert(value), R.del(value) etc...

#include "set.h"
#include <istream>

using namespace std;

Set::Set() {
    header = new Node(0,0);
    cout << "Empty constructor " << endl;
}

Set::Set(int a[], int n) {

    header = new Node(0,header); //skapar ny lista
    Node *temp = header; //temp tilldelas start värdet för listan

    int i = 0;
    while(i < n+1) {
        temp->next = new Node(a[i],0); //nästa uttrymme på listan tilldelas värde från a[i]
        temp = temp->next; //
        i++;
    }
    cout << "Created constructor" << endl;

}

Set::Set(const Set& b) {
    header = new Node(0,header);
    Node *temp = header;

    Node *templist = b.header -> next;

    while (templist != 0)
    {
        temp -> next = new Node (templist->value, 0);
        temp = temp -> next;
        templist = templist -> next;
    }
}


Set::~Set() {
    delete header;
}

void insert (int value) {

}

std::ostream& operator << (std::ostream& out, const Set& b) {

    Node* temp = b.header;
    temp = temp -> next;
    if (temp == 0) {
        out << "Empty";
    } else {
        while(temp->next != 0) {
            out << temp->value << ", ";
            temp = temp->next;
        }
    }

    return out;
}

My pseudocode was intended to indicate that implementing a Set class based on a list you will need a variable to maintain the first node of the list. The remainder of the pseudocode was intended to show that the insert function properly belongs to the Set and that to insert something into the list you need the value to insert, then you need to embed that value in a new Node, and then you need to insert that new Node in the "appropriate" spot in the list. Basically it would be pseudocode for starting to define the insert function dedlared on line 32 of the .h file you posted.

The two parameter Node constructor you are using to declare new Nodes looks a little suspect. In particular I see no reason why you would want to pass a Node pointer, which is presumably what header is, to a new Node. Passing NULL, or 0, to assign to the next pointer of the new Node is reasonable, if that's what you are trying to do, but passing header doesn't sit well up front. I usually see the default constructor for the class would used to declare memory for a new Node, and the values of the Node data members would be assinged after declaration, but I can't be sure what you are trying to do. Post how you declared the Node class.

If there are n elements of the array you want to change into a set, then you want to let i range from zero to less than n. n itself and n + 1 are invalid element indexes of the array.

Is the array passed in tothe nondefault constructor sorted, or not? If it is, then it would be reasonably convenient to declare a new Node, fill it with the first element of the array, and assign the new Node to header. Then assign header to temp and increment i from zero to one. Then, while i less than n, declare a new node, fill it with the information at a and add it to the end of the list, as you do in your code.

You may need to change header to have public access as opposed to private access if you don't have an accessor function to be able to access b.header in the copy constructor. If it works as is, so be it.

The destructor should delete any and all memory declared with new that hasn't already been deleted. Deleting just header leads to memory leak.

In << it looks like you never will be able to output any data in header. Some lists have header as a dummy Node----no data in it, it's just a place holder. If header has data, you want to be sure to access it. I can't tell if header is to be a dummy node or not though.


The two parameter Node constructor you are using to declare new Nodes looks a little suspect. In particular I see no reason why you would want to pass a Node pointer, which is presumably what header is, to a new Node. Passing NULL, or 0, to assign to the next pointer of the new Node is reasonable, if that's what you are trying to do, but passing header doesn't sit well up front. I usually see the default constructor for the class would used to declare memory for a new Node, and the values of the Node data members would be assinged after declaration, but I can't be sure what you are trying to do. Post how you declared the Node class.

I'm not quite sure myself, since the Node class was already made. The assignment it self is to implement the functions defined in the header file for Set. I have attached the files relevant for my question.

If there are n elements of the array you want to change into a set, then you want to let i range from zero to less than n. n itself and n + 1 are invalid element indexes of the array.

Yes, that's but for some reason it will only add the two first values in the array if I skip the n+1. I'm guessing it is the Node starting values is zero.

New problems I've encountered is my overload for the + function for Sets. As of now I can add
S3 = S1+S2 but when I try something like S3 = S1 + 4 I get compile error with is reasonable since my overload for + doesn't take integers. So my question is can i rewrite my current overload of + to take integers as well? or would I need to write a seperate overload of + to add integers to my Set?

Another question I have is can I use normal sort algorithm like quicksort to sort a linked list?

Attachments
#include "node.h"
#include <cassert>    //assert

Node::Node (int nodeVal, Node *nextPtr) : value (nodeVal), next (nextPtr)
{
//   std::cout << "Konstruktor Node" << std::endl;
}

Node *Node::insert (int newValue) {
    next = new Node (newValue, next);
    assert (next != 0);     //koll fr att next != 0
    return next;
}
#ifndef NODE_H
#define NODE_H

#include <iostream>

class Node
{
public:
   Node(int, Node*); //constructor
   Node *insert(int value); //member function

private:
   int value;
   Node *next;

   friend class Set;
   friend std::ostream& operator << (std::ostream &os, const Set &theSet);
};

#endif
#include "set.h"
#include <istream>

using namespace std;

Set::Set() {
    header = new Node(0,0);
//    cout << "Empty constructor " << endl;
}

Set::Set(int a[], int n) {

    header = new Node(0,0); //skapar ny lista
    Node *temp = header; //temp tilldelas start vrdet fr listan

    int i = 0;
    while(i < n+1) {
        temp->next = new Node(a[i],0); //nsta uttrymme p listan tilldelas vrde frn a[i]
        temp = temp->next; //
        i++;
    }
//    cout << "Created constructor" << endl;

}

Set::Set(const Set& b) {
    header = new Node(0,header);
    Node *temp = header;

    Node *templist = b.header -> next;

    while (templist != 0)
    {
        temp -> next = new Node (templist->value, 0);
        temp = temp -> next;
        templist = templist -> next;
    }
}


Set::~Set() {
    delete header;
}

bool Set::empty () const {
    Node *temp = header;
    temp = temp->next;
    if(temp == 0) {
        return true;
    }
    return false;
}

int Set::cardinality() const {
    Node *temp = header;
    temp = temp->next;
    int count = 0;
    while(temp->next != 0) {
        temp = temp->next;
        count++;
    }
    return count;
}
bool Set::member (int x) const {
    Node *temp = header;
    temp = temp->next;

    while(temp->next != 0) {
        if(temp->value == x) {
            return true;
        }
        temp = temp->next;
    }
    return false;
}

Set Set::operator+ (const Set& b) {

    Node *tmp = header;
    Set out = b;
    tmp = tmp->next;
    int i = 0;
    while (tmp->next != 0 && i != 9) {
        out.insert(tmp->value);
        tmp = tmp->next;
        i++;
    }

    return out;
}
void Set::insert (int value) {

//    Node *temp = header;
//    while(temp->next != 0) {
//        cout << "Occupied by: "<< temp->value << endl;
//        temp = temp->next;
//
//    }
//    temp->next = new Node(value,temp->next);
     Node *temp = header;
     bool exist = false;
     while (temp->next != 0) {
         if(temp->value == value && !exist) {
            cout << "Exist " << endl;
            exist = true;
            break;
         }
         temp = temp->next;
     }
      if(!exist)
        header->next = new Node(value, header->next);

}

std::ostream& operator << (std::ostream& out, const Set& b) {

    Node *temp = b.header;
    temp = temp -> next;
    if (temp == 0) {
        out << "Empty";
    } else {
        while(temp->next != 0) {
            out << temp->value << " ";
            temp = temp->next;
        }
    }

    return out;
}
/*
  Name: set.h
  Author: Kenneth Bjerner
  Date: 04-02-04 11:31
  Description: Definitionsfil fr klassen Set
*/

#ifndef SET_H
#define SET_H

#include "node.h"
#include <iostream>

class Set {
public:
   Set ();
   Set (int a[], int n);
   Set (const Set& b);
   ~Set ();

   bool empty () const;
   int cardinality() const;
   bool member (int x) const;

   Set operator+ (const Set& b);
//   Set operator* (const Set& b);
//   Set operator- (const Set& b);
//   Set operator+(int x) const;
//   Set operator-(int x) const;
//   bool operator<=(const Set& b) const;
//   bool operator==(const Set& b) const;
//   bool operator<(const Set& b) const;
//   Set& operator=(const Set& b);
//
private:

   Node *header;
   friend std::ostream& operator << (std::ostream& os, const Set& b);
   void insert (int value);
   void del (int value);
};
#endif

OK, so the non-default Node constructor with two parameters uses the first parameter to set the value of the data member of the new Node and the second parameter to set the value of the next pointer of new Node. Fair enough.

Do you want header to be a dummy Node or not? I suspect you want the value member to have some value. That is, if you want to add 3 elements to the list then you want 3 Nodes in the listt as opposed to if the header Node is a dummy Node then the list needs to be 4 Nodes long to have 3 Nodes with a value in them.

Assuming header isn't a dummy Node, then in the non-default Set constructor you are passed an array of data (that doesn't need to be sorted according to the examples provided in main()) and the number of values in the array. Since you want to hold onto header I would agree that it should be assigned values before the loop and, if it is to hold a value, then it should contain a[0] as the data value and NULL, or 0, as the value of next:

header = new Node(a[0], 0);

then temp should be assigned the value of header before the loop:
Node *temp = header;

then i shoud range from 1 to less than n to enter the remaining elements of the array into the Set:

int i = 1;    
while(i < n) 
{        
    temp->next = new Node(a[i], 0); 
    temp = temp->next;        
    i++;    
}

That will keep NULL as the value of next for the last Node in the list/Set, and it will always add the values in the array into the listSet in the same order as they were in in the array. That may, or may not be acceptable. For example, if a Set is truly going to be a group of unique values, then you will have to search through the list to see if there are any duplicates before adding the current value in the array (unless you are guaranteed that the arrays passed in have no duplicates). That means searching the list to see if the value to be added is already present or not. If it isn't then it can be added. If the list isn't sorted, then you would loop through the entire list until you either find the value to be added or you have searched the entire list. If it isn't found, then you add the current value to end of the list. Alternatively, if the list is sorted, then you could search the list until the value in the current node is larger than the value to be added and add the current value to the left of that node. This would create a list sorted in ascending order based on the value of value. It takes up a little extra time to do the sorting on insertion, but it can save you time later when trying to do a union of two Sets, and may be helpful if you want to define an == operator or a < operator for the Set class. (See the discussiion below).

Indeed, in the Set.h file there are two methods that need to be implemented for the + operator. The one passed another Set could either concatenate one Set on to the other, irrespective of any duplicate values, or it could create a new Set consisting of all unique values present in both sets, that is (1, 2, 3) + (4, 3, 2) becomes 1, 2, 3, 4 instead of (1, 2, 3, 4, 3, 2) (using simple concatenation) or (1, 2, 2, 3, 3, 4) (if sorted and duplicates allowed). The version that adds a single int could simply call the insert() function passing it the on the right hand side of the + sign.

What does it mean for 2 Sets to be equal? Do they have to have the same number of elements or in addition to having the same number of elements does each Set have to have the same values. That is if S1 is (1, 2, 3), S2 is (2, 3, 4) and S3 is (1, 3, 2) is S1 == S2 == S3 or is S1 == S3 but S2 isn't equal to either S1 or S3?

Likewise, what implications does the < operator have for a Set? Is it simply a matter of size, or if 2 Sets are the same size do the values of the elements of the set matter, and if they do, then is it the Set with the lowest unique value that is smaller or is it the Set with the lowest sum of the elements in the set that is the smallest, etc?

This article has been dead for over six months. Start a new discussion instead.