Problem with template linked list

**Strait** · 03-11-2005

the goal of my program is to take in two sets of any regular data type (int, double, char, etc) then be able to manipulate them. so far I'm working on input and output, but it's not working. here's my code so far:

Code:

//NODE.H    header for class node. all the functions are inline
---------------------------------------------------------------------------
#ifndef NODE_H
#define NODE_H
#include <cstdlib>

template <class Item>
class node
{
  public:
    node(Item the_data = Item(), node* link_field = NULL)
    {data = the_data; link = link_field;}
    //default constructor. sets data = whatever the default   
    //constructor of the data type is and sets the link = NULL
    void set_link(node* link_field) {link = link_field;}
    void set_data(Item value) {data = value;}
    Item get_data() {return data;}
    node* get_link() {return link;}
  private:
    Item data;
    node* link;
};

#endif

//BAG.H   header for class bag which is a set of any data type
----------------------------------------------
#ifndef BAG_H
#define BAG_H
#include <cstdlib>

template <class Item>
class bag
{
  public:
    bag() {head = NULL;}
    //default constructor
    void print();
    //prints with cout
    void input();
    //inputs with cin and head_insert
    void set_head(node<Item>* n1) {head = n1;}
    node<Item>* get_head() {return head;}
    bool is_element(const Item& value);
    //finds if any of the nodes in the set have data = value
    //there will be more here later, but right now I just wanna have
    //I/O
  private:
    node<Item>* head;
};

template <class Item>
void head_insert(node<Item>* head, Item value);
//creates a new node at the head of the list

#include bag.template
#endif

BAG.TEMPLATE  implementation for class bag
----------------------------------------------------------
#include "node.h"
#include <iostream>
#include <cstdlib>

using namespace std;

template <class Item>
void bag<Item>::input()
{
  Item value;

  cout << "Please enter a set: \n";  //set will have no spaces
  cin >> value;
  head_insert(head, value);
  while (cin.peek() != '\n')
  {
    cin >> value;
    head_insert(head, value);
  }
}

template <class Item>
void bag<Item>::print()
{
  node<Item>* temp = head;
  cout << "{";      //output is like this {a,b,c,d}
  if (head != NULL)
  {
    cout << temp->get_data();
    temp = temp->get_link();
    while (temp)
    {
      cout << "," << temp->get_data();
      temp = temp->get_link();
    }
    cout << "}";
  }
}

template <class Item>
void head_insert(node<Item>* head, Item value)
{
  node<Item>* temp;
  temp = new node<Item>;
  temp->set_data(value);
  temp->set_link(head);
  head = temp;
}

//MAIN.CC  application file
-----------------------------------

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

using namespace std;

int main()
{
  bag<char> b1, b2;

  b1.input();
  cout << endl;
  b1.print();
  cout << endl;
  b2.input();
  cout << endl;
  b2.print();
  cout << endl;

  return 0;
}
//that should be all you need

I keep getting a segmentation fault when I get to my print function. I'm thinking that either my input function doesn't work right or I'm not setting the end of the list = NULL

please help ASAP

**Strait** · 03-11-2005

problem solved. now I'm having another problem.....sigh

**grib** · 03-11-2005

Originally Posted by Strait

the goal of my program is to take in two sets of any regular data type (int, double, char, etc) then be able to manipulate them. so far I'm working on input and output, but it's not working. here's my code so far:

Code:

template <class Item>
void head_insert(node<Item>* head, Item value)
{
  node<Item>* temp;
  temp = new node<Item>;
  temp->set_data(value);
  temp->set_link(head);
  head = temp;
}

I keep getting a segmentation fault when I get to my print function. I'm thinking that either my input function doesn't work right or I'm not setting the end of the list = NULL

please help ASAP

This is confusing, but is your problem. This should be a member function, but is in fact an ordinary free function. More confusingly head is the name of a paramiter. This blisfully set's head, the local paramiter to the new node, then head leaves scope never to be heard from again. This changes nothing in bag.

Code:

template <class Item>
class node
{
  public:
    node(node* link_field = NULL) : link(link_field) {}
    //default constructor. implicitly calls default constructor for data, sets link
    //to the given address or NULL, if no address given.
    node(const Item &the_data, node* link_field = NULL) : data(the_data), link(link_field) {}
    //explcitly calls copy constrctor for data
    void set_link(node* link_field) {link = link_field;}
    void set_data(Item value) {data = value;}
    Item get_data() {return data;}
    node* get_link() {return link;}
  private:
    Item data;
    node* link;
};
...
bag<Item>::push_front(const Item &value) {head = new node<Item>(value,head);}

This uses copy constructors, rather than assignment in the constructor body, and has a re-written head_insert. Other changes that may make life easyer are to make node a nested friend of bag, or a private nested struct. Then you will simply use link (you may want to rename this next) directly. If anyone can get or set a value, there usually is little need to make that value private.

**7stud** · 03-12-2005

It's probably a good idea to get your program to work with non-templated classes first, and then convert it to a template.

Let's examine your program in the context of type int. This line in main():

Code:

bag b1, b2;

calls the default constructor in the bag class:

Code:

class bag
{
  public:
    bag() {head = NULL;}
    //default constructor

so b1.head = NULL. The next line in main() is:

Code:

b1.input();

which calls:

Code:

void bag::input() 
{
  int value;

  cout << "Please enter a set: \n";  //set will have no spaces
  cin >> value;
  head_insert(head, value);
  while (cin.peek() != '\n')
  {
    cin >> value;
    head_insert(head, value);
  }
}

So, lets say the user enters: 12345, and therefore value=12345. Then, head_insert() is called:

Code:

void head_insert(node* head, int value)
{
  node* temp;
  temp = new node();  //No parentheses
  temp->set_data(value);
  temp->set_link(head);
  head = temp;
}

The function call looks like this: head_insert(NULL, 12345), and inside the function, you create a node; make a call to set_data() to set the node's data member equal to value, and then you call set_link() and send it b1.head, which is NULL. set_link() looks like this:

Code:

void set_link(node* link_field) {link = link_field;}

and it just sets the node pointer to NULL. The result is that any input from the user is put in a node
that points to nothing, and so you end up with a collection of nodes that all point to nothing. Then, you call print():

Code:

void bag::print()
{
  node* temp = head;  
  cout << "{";      //output is like this {a,b,c,d}
  if (head != NULL)
  {
    cout << temp->get_data();
    temp = temp->get_link();
    while (temp)
    {
      cout << "," << temp->get_data();
      temp = temp->get_link();
    }
    cout << "}";
  }
}

which outputs "{", and since b1.head equals NULL, the if statement is skipped and nothing is output after that. Note that even if you have only 1 node, the print() function won't display that node's data.

**7stud** · 03-12-2005

More confusingly head is the name of a paramiter. This blisfully set's head, the local paramiter to the new node, then head leaves scope never to be heard from again. This changes nothing in bag.

Good catch. That's a good argument for never naming your function parameters the same name as the variable you are sending to the function, and never naming a function parameter the same name as a member variable!

Strait,

In case you weren't aware, a function 'parameter', e.g.:

void somefunc(int name1, double name2)

creates a variable local to the function, which stores the 'arguments' you send to the function, e.g.:

somefunc(10, 2.50);

A local variable is destroyed once the function finishes executing. You named your local variable 'head', which is not the same variable as the head member of a bag object. So, when you assigned temp to head as the last line of your function, you assigned temp to the local 'head', and then head was subsequently destroyed. Local variable names are said to 'hide' variables with the same name in a calling function.

Thread: Problem with template linked list

Thread Tools

Search Thread

Display

Problem with template linked list

Similar Threads

Sorting linked list please help with CODE

Reverse function for linked list

I need help on this particular Linked List problem

error: template with C linkage

singly linked list