Problem with template linked list

This is a discussion on Problem with template linked list within the C++ Programming forums, part of the General Programming Boards category; the goal of my program is to take in two sets of any regular data type (int, double, char, etc) ...

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    46

    Problem with template linked list

    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

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    46
    problem solved. now I'm having another problem.....sigh

  3. #3
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    Quote 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.

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    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.
    Last edited by 7stud; 03-12-2005 at 12:00 AM.

  5. #5
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    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.
    Last edited by 7stud; 03-12-2005 at 12:51 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  3. I need help on this particular Linked List problem
    By sangken in forum C Programming
    Replies: 11
    Last Post: 08-06-2006, 12:26 AM
  4. error: template with C linkage
    By michaels-r in forum C++ Programming
    Replies: 3
    Last Post: 05-17-2006, 08:11 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21