C++

Forum

 
Node and List

rmartin20 (21)
I converted this StrNode class to a template class, and now I am trying to convert the List portion but cannot get it to match up. Any one have some ideas?

StrNode.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#ifndef STRNODE_H
#define	STRNODE_H

#include <string>
using namespace std;

template<typename C>
class StrNode {
private:
  C data;
  StrNode<C>* next;
public:
  StrNode(C);
  virtual ~StrNode(); // base class destructor must be virtual
  C getData();
  StrNode<C>* getNext();
  void setNext(StrNode<C>*);
  void setData(C d);
};
template<typename C>
StrNode<C>::StrNode(C d) {
  data = d;
  next = NULL;
}
template<typename C>
StrNode<C>::~StrNode() {
}
template<typename C>
void StrNode<C>::setData(C data) {
  data = d;
}
template<typename C>
void StrNode<C>::setNext(StrNode<C>* next) {
  next = n;
}
template<typename C>
StrNode<C>* StrNode<C>::getNext() {
  return next;
}
template<typename C>
C StrNode<C>::getData() {
  return data;
}
#endif	/* STRNODE_H */


StrList.h 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
 
#ifndef STRLIST_H
#define STRLIST_H

#include "StrNode.h"

// Singly linked list
template<typename C>
class StrList {
  private:
    StrNode<C>* head; // pointer to the first node
    StrNode<C>* tail; // pointer to the last node
    int count;  // number of nodes in the list
  public:
    class OutOfRangeException{ }; // empty inner class for exception handling
    StrList();
    virtual ~StrList();
    void add(string item);
    void add(int index, C);
    void remove(int index);
    int indexOf(string item);
    string get(int position); // OutOfRangeException is generated
    bool isEmpty();
    int size();
    void print();
};
template<typename C>
StrList<C>::StrList() {
  head = tail = NULL;
  count = 0;
}
template<typename C>
StrList<C>::~StrList() {
  StrNode<C>* discard;
  while (head != 0) {
    discard = head;
    head = head->getNext();
    delete discard;
  }
}
// add an item at the end of the StrList
template<typename C> 
void StrList<C>::add(string item) {
  try {
    StrNode<C>* newNode = new StrNode(C);
    if (head == 0) {
      head = tail = newNode;
    } else {
      tail->setNext(newNode);
      tail = newNode;
    }
    ++count;
  } catch (bad_alloc &e) {
    cout << "memory allocation exception: " << e.what() << endl;
    exit(1);
  }
}
// add (insert) an item at the specified index
template<typename C>
void StrList<C>::add(int index, C) {
  try {
    if (index < 0 || index > count) // append if index == count
      throw OutOfRangeException();

    StrNode<C>* newNode = new StrNode(C);
    if (head == 0) { // empty
      head = tail = newNode;
    } else if (index == 0) { // at the start
      newNode->setNext(head);
      head = newNode;
    } else if (index == count) { // at the end
      tail->setNext(newNode);
      tail = newNode;
    } else { // insert in the middle
      StrNode<C>* prevNode;
      StrNode<C>* currNode = head;
      for (int i = 0; i < index; i++) {
        prevNode = currNode;
        currNode = currNode->getNext();
      }
      // insert between 'prevNode' and 'currNode'
      prevNode->setNext(newNode);
      newNode->setNext(currNode);
    }
    ++count;

  } catch (bad_alloc &e) {
    cout << "memory allocation exception: " << e.what() << endl;
    exit(1);
  }
}
// is the StrList empty?
template<typename C>
bool StrList<C>::isEmpty() {
  return count == 0;
}
// remove the item at specified index
template<typename C>
void StrList<C>::remove(int index) {
  if (index < 0 || index >= count)
    throw OutOfRangeException();

  if (index == 0) { // at the start
    StrNode* discard = head;
    head = head->getNext();
    delete discard;
  } else {
    StrNode<C>* prevNode;
    StrNode<C>* currNode = head;
    for (int i = 0; i < index; i++) {
      prevNode = currNode;
      currNode = currNode->getNext();
    }
    // remove 'currNode'
    prevNode->setNext(currNode->getNext()); // bypass
    delete currNode;

    if (index == count-1) // last node was removed. Update 'tail'
      tail = prevNode;
  }
  --count;
  if (count == 0)
    tail = NULL;
}
// retrieve the item at the given position of the StrList. position starts from 0.
// throws OutOfRangeException if invalid position value is given.
template<typename C>
string StrList<C>::get(int position) {
  if (position < 0 || position >= count)
    throw OutOfRangeException();

  int loc = 0;
  StrNode<C>* curr = head;
  while (loc < position) {
    ++loc;
    curr = curr->getNext();
  }
  return curr->getData();
}
// Requirement:
//   != operator of <string> class is used
template<typename C>
int StrList<C>::indexOf(string item) {
  if (head == 0) {
    return -1; // not found
  } else {
    int index = 0;
    StrNode<C>* currNode = head;
    while (currNode->getData() != item && currNode != NULL) {
      currNode = currNode->getNext();
      ++index;
    }
    if (currNode == NULL) // not found thru the end
      return -1;
    else
      return index;
  }
}
// number of nodes in the StrList
template<typename C>
int StrList<C>::size() {
  return count;
}

// Requirement:
//   << operator for T class must be overloaded
template<typename C>
void StrList<C>::print() {
  cout << "*** StrList contents ***" << endl;
  for (int i = 0; i < count; i++) {
    cout << i << ": " << get(i) << endl;
  }
}

#endif


main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include <iostream>
using namespace std;

#include "StrList.h"

int main() {

  cout << "\n*** StrList Test ***" << endl;

  StrList<string> list;
  list.add("zero");
  list.add("one");
  list.add("two");
  list.add("three");
  list.add("four");
  list.add("five");
  list.print();
  
  list.add(1, "added at position 1");
  list.add(0, "added at position 0");
  list.add(4, "added at position 4");
  list.print();

  cout << "removing at indexes 3, 0" << endl;
  list.remove(3);
  list.remove(0);
  list.print();

  list.add(2, "added at position 2");
  list.print();

  cout << "five is at index " << list.indexOf("five") << endl;
  cout << "two is at index " << list.indexOf("two") << endl;
  
  return 0;

}
closed account (o1vk4iN6)
You are only specifying a type for the function parameter, so you are not using data sent:

1
2
3
4
5
6
 

template<typename C>
void StrList<C>::add(int index, C /*data*/) { // should make data a const & instead
    StrNode<C>* newNode = new StrNode/*<C>*/(C); // should be creating a copy of "data" instead here
}


Could also consider moving StrNode into StrList, as both require the same template parameter:

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

template< class T >
class List
{
     struct Node
     {
          Node* next;
          T data;

          Node( T const & _data, Node* _next = NULL ) : data(_data), next(_next)
          {
          }

          T& getData(); // your accesor returns a COPY, when it should return a reference, can just keep this class encapsulated than there is no need for an accessor  
     };

};
Last edited on
Peter87 (11175)
Look at the parameter names in setData and setNext and see that you are using a different name when you are trying to use them in the function body.

In StrList<C>::add you are trying to pass a type to the StrNode constructor.

On line 103 in StrList.h you forgot to specify the template argument of StrNode.
rmartin20 (21)
template<typename C>
void StrList<C>::add(int index, C /*data*/) { // should make data a const & instead
StrNode<C>* newNode = new StrNode/*<C>*/(C); // should be creating a copy of "data" instead here
}


When you say i should make data a const&, do you mean that i should change it to (int index, const& data)? Either way, when I try and use a double for a second list declaration in Main i get an error saying that you cannot convert const char[20] to double??

Compiler...
1
2
3
4
5
6
7
 
main.cpp(20): error C2664: 'void List<C>::add(int,C)' : cannot convert parameter 2 from 'const char [20]' to 'double'
1>          with
1>          [
1>              C=double
1>          ]
1>          There is no context in which this conversion is possible
closed account (o1vk4iN6)
There is no implicit conversion from a c-string to a double.

1
2
3
4
5
6
7
8
 

List<double> a;

a.add(0, "five thousand"); //error
a.add(0, "5000."); // error
a.add(0, "5000"); // error
a.add(0, 5000.); // good


When you say i should make data a const&, do you mean that i should change it to (int index, const& data)?


Where's the type declaration in const & ? Does it make any sense ? I even used it in an example if you even glanced over it.

Last edited on
rmartin20 (21)
right i was trying to use const& as a template, either way completely wrong. After reviewing it I was able to use your help to compile and run, now I just have to test some other types. Also the struct Node idea was helpful too so thanks for that.
Topic archived. No new replies allowed.