Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

New Functions Added Linked List

Posted on 2006-04-11
8
Medium Priority
?
543 Views
Last Modified: 2013-12-14
I added additional functions to this code, I have been debugging for 45 minutes and can not seem to figure out these errors.

Please advise.  Del

***************************code********************

#ifndef LIST_H
#define LIST_H

#include <iostream>
#include <fstream>

using namespace std;

//const int CAPACITY = 1024;
typedef int ElementType;

class Node; // fwd. decl. needed here

class List {

     // prototype for ouput operator
       friend ostream &operator << (ostream &out, const List &alist);  // needs to be a friend

public:

     List(int maxSize = 1024);
     ~List();
     // copy constuctor
     List(const List &origList); // no ',' here!
     // assignment operator
     const List &operator = (const List &rightHandSide);
     // list traversal
     void listTraversalNode();
     void printInReverse(Node *Head);   // call function to print list in reverse
     bool sort(); // boolean function ascending
       // perform linear search
       int List::linearSearch();
     // empty operation
     bool empty() const;
     // insert and erase
     void insert(ElementType item, int pos);
     void erase(int pos);
     // output
     void display(ostream &out) const;

private:

     int mySize; // current size of list store in myArray
     //ElementType myArray[CAPACITY]; // array to store list of elements
     int myCapacity; // capacity of array
     Node *myArray; // pointer to dynamic array
       Node *date;
     
};

class Node {

public:

     ElementType data;
     Node *next;

     Node* get_first() const { return first;} // private!
private:

     Node* first;
     int mySize;

};

typedef Node *NodePointer;

#endif

*************

#include <cassert>
#include <iostream>
#include <fstream>
#include <list>
#include <new>
#include <string>
#include "list.h"

using namespace std;

// prototype for ouput operator
ostream &operator << (ostream &out, const List &alist);

// definition of class constructor
List::List(int maxSize) : mySize(0), myCapacity(maxSize) {

     myArray = new Node;
     assert(myArray != 0);

}

// definition of class destructor
List::~List() {

     delete [] myArray;

}

// definition of copy constructor
List::List(const List &origList) : mySize(origList.mySize), myCapacity(origList.myCapacity) {

         myArray = new Node;

}

// definition of assignment operator
const List &List::operator = (const List &rightHandSide) {

     // check that not self-assignment
     if(this != &rightHandSide) {
          // allocate new array if necessary
          if(myCapacity != rightHandSide.myCapacity) {
               delete [] myArray;
               myCapacity = rightHandSide.myCapacity;
               myArray = new Node;
               // check if memory available
               if(myArray == 0) {
                    cerr << " Inadequate memory to allocate stack. \n";
                    exit(1);

               }

          }
          // copy rightHandSide's list elements into this new array
          mySize = rightHandSide.mySize;

     }
     return *this;

}
               
// definition of empty
bool List::empty() const {

     return mySize == 0;

}

// definition of display
void List::display(ostream &out) const {

      out << "\n\n The elements in the list are: ";

      NodePointer ptr = first;
      while(ptr != 0) {
            out << ptr->date << " ";
            ptr = ptr->next;

      }
      out << " ";

}

// definition of output operator
ostream &operator << (ostream &out, const List &aList) {

     aList.display(out);
     return out;

}

// definition of insert
void List::insert(ElementType item, int pos) {

     if(mySize == myCapacity) {
          cerr << " No space for linked list element, terminating execution. \n";
          exit(1);

     }
     if(pos < 0 || pos > mySize) {
          cerr << " Illegal location to insert -- " << pos << ". Linked list unchanged. \n";
          return;

     }

     // first shift array elements right to make room for item
     for(int i = mySize; i > pos; i--)
          myArray[i] = myArray[i - 1];
              mySize++;

}
// perform linear search
int List::linearSearch() { // added function

      ElementType dataVal;
      cout << " Type in value to search-> ";
      cin >> dataVal;

      int loc;
      NodePointer temp = first;
      for(loc = 0; loc < mySize; loc++) {
            if(temp->data == dataVal)
                  cout << " Element located at location. ";
      return loc;
        }
            else {
                  temp = temp -> next;
                  cout << "\n The element is not in the list. ";
                  return -1;

      }

}
// traverse the list
void List::listTraversalNode() {

     NodePointer ptr = myArray->get_first(); // need to declare it with a type!
     NodePointer first = ptr;

     while(ptr != 0) {
          ptr = ptr -> next; // appropriate statements to process ptr -> data

     }

     NodePointer newptr = new Node; // newptr of type NodePointer

     NodePointer predptr = NULL;
     if(predptr != 0) { // not inserting at front
          newptr -> next = predptr -> next;
          predptr -> next = newptr;

     }
     else { // inserting at front
          newptr -> next = first;
          first = newptr; // reset first

     }

     if(predptr != 0) { // not deleting first node
          ptr = predptr -> next;
          predptr -> next = ptr -> next; // bypass

     }
     else { // deleting first node
          ptr = first;
          first = ptr -> next; // reset first

     }
     delete ptr; // return node to heap

}

// reverse print of list
void List::printInReverse(Node *Head) {

     if (Head == 0){
     cout << "List is empty." << endl;
     }
     //int count = 0;
     Node *printPtr = new Node;
     printPtr = Head;

     while(printPtr != 0) {
     printPtr = printPtr->next; //advance pointer to next location in list...
       
      }
 
}

// boolean value function ascending for node element
// the purpose of this function is to generate a boolean-valued
// function that determines whether the data items in the linked
// list are arranged in ascending order.
//sorts list in ascending order
bool List::sort() // new added function to perform above specs
{
     for(NodePointer *temp = first; temp != NULL; temp = temp -> next)
     {
          NodePointer *min = temp;

          for(NodePointer *current = min; curr != NULL; current = current -> next)
          {
               if(current->info < min->data)min=current;
          }

          ElementType temp_var = temp -> data;
          temp -> data = min -> data;
          min -> data = temp_var;
     }
       return true;
       else
             return false; // ???????????
}
// definition of erase
void List::erase(int pos) {

     if(mySize == 0) {
          cerr << " List is empty \n";
          return;

     }
     if(pos < 0 || pos >= mySize) {
          cerr << " Illegal location to delete -- " << pos << ". List unchanged. \n";
          return;

     }

       // decrease list size
     mySize--;

}

int main() {

     int myCapacity = 42; // It is always a good idea to *declare* the variables you are using

     // test the class constructor
     List intList;
     cout << " Constructing intList\n";

     // test empty and output of empty list
     if(intList.empty())
          cout << " Empty: \n" << intList << endl; // test output of empty list

     // test insert
     for(int i = 0; i < 9; i++) {
          cout << " Inserting " << i << " at position " << i/2 << endl;
          intList.insert(i, i/2); // insert i at position i/2

          // test output
          cout << intList << endl;

     }

     cout << " List empty? " << (intList.empty() ? "Yes" : "No") << endl;

     cout << "\nTry to insert at position -1" << endl;
     intList.insert(0, -1);

     cout << "\nTry to insert at position 10" << endl;
     intList.insert(0, 10);

     // test erase
     int index;
     cout << endl;

     while(!intList.empty()) {

          cout << " Give an index of a list element to remove: ";
          cin >> index;
          intList.erase(index);
          cout << intList << endl;

     }
     cout << " List is empty. " << endl;

     cout << "\nInserting " << myCapacity << " integers\n";

     for(int j = 0; j < myCapacity; j++)
          intList.insert(j, j);

     cout << " Attempting to insert one more integer: \n";
     intList.insert(-1, 0);

}

**********

Output:

list.cpp: In member function `void List::display(std::ostream&) const': // this one is new
list.cpp:83: error: `first' undeclared (first use this function)
list.cpp:83: error: (Each undeclared identifier is reported only once for each
   function it appears in.)
list.cpp:85: error: 'class Node' has no member named 'date'
list.cpp: In member function `int List::linearSearch()':
list.cpp:134: error: parse error before `else'
list.cpp: In member function `bool List::sort()':
list.cpp:205: error: request for member `next' in `*temp', which is of
   non-class type `Node*'
list.cpp:209: error: `curr' undeclared (first use this function)
list.cpp:209: error: request for member `next' in `*current', which is of
   non-class type `Node*'
list.cpp:211: error: request for member `info' in `*current', which is of
   non-class type `Node*'
list.cpp:211: error: request for member `data' in `*min', which is of non-class
   type `Node*'
list.cpp:214: error: request for member `data' in `*temp', which is of
   non-class type `Node*'
list.cpp:215: error: request for member `data' in `*temp', which is of
   non-class type `Node*'
list.cpp:215: error: request for member `data' in `*min', which is of non-class
   type `Node*'
list.cpp:216: error: request for member `data' in `*min', which is of non-class
   type `Node*'
list.cpp:219: error: parse error before `else'
0
Comment
Question by:edelossantos
  • 3
  • 2
  • 2
  • +1
8 Comments
 
LVL 4

Assisted Solution

by:uniques
uniques earned 200 total points
ID: 16433457
Can you post your list.h also? It will give more clarity on the errors. From the code it seems

1. first is not a member of the List class. I believe you want it to store the address of first node.
2. You will hve to declare a 'date' member in class Node
0
 

Author Comment

by:edelossantos
ID: 16433462
#ifndef LIST_H
#define LIST_H

#include <iostream>
#include <fstream>

using namespace std;

//const int CAPACITY = 1024;
typedef int ElementType;

class Node; // fwd. decl. needed here

class List {

     // prototype for ouput operator
      friend ostream &operator << (ostream &out, const List &alist);  // needs to be a friend

public:

     List(int maxSize = 1024);
     ~List();
     // copy constuctor
     List(const List &origList); // no ',' here!
     // assignment operator
     const List &operator = (const List &rightHandSide);
     // list traversal
     void listTraversalNode();
     void printInReverse(Node *Head);   // call function to print list in reverse
     bool sort(); // boolean function ascending
      // perform linear search
      int List::linearSearch();
     // empty operation
     bool empty() const;
     // insert and erase
     void insert(ElementType item, int pos);
     void erase(int pos);
     // output
     void display(ostream &out) const;

private:

     int mySize; // current size of list store in myArray
     //ElementType myArray[CAPACITY]; // array to store list of elements
     int myCapacity; // capacity of array
     Node *myArray; // pointer to dynamic array
      Node *date;
     
};

class Node {

public:

     ElementType data;
     Node *next;

     Node* get_first() const { return first;} // private!
private:

     Node* first;
     int mySize;

};

typedef Node *NodePointer;

#endif
0
 
LVL 3

Assisted Solution

by:NeoEGM
NeoEGM earned 200 total points
ID: 16433490
Taking into account that it is your homework (http://www.experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_21807126.html => Last comment), I can't help you with real code...

It's against EE's rules... (Look at the Administrative Comment here: http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_21796266.html)

Anyway, I can tell you that you should double check where you declared the member variables (what you declare in a class is not visible in the other unless you derive it from the first or access it through an instance of that class), and the way you use types... If I were you, I'd delete the declaration:

>>typedef Node* NodePointer;

and use "Node*" where needed at least until you get used to them... it will help you find problems in your code...

Hope it helps.
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 4

Assisted Solution

by:uniques
uniques earned 200 total points
ID: 16433518
edelossantos,

There are some discrepancies between the declarations and usage.

1. You are using 'first' to locate the first node in the list. 'first' node is an attrbute of the list and should be ia member of class List. In all your List member functions, you are accessing 'first' as a member variable.

2. out << ptr->date << " ";
ptr is pointing to Node. Node structure does not have 'date' member. 'date' is a member of List. Anyways, you are using 'data' to store the data value in the node, so do you ned the 'date' member at all?

3. In List::sort()
for(NodePointer *temp = first; ...
temp should be declared as NodePointer (or 'Node *', 'not NodePointer *')

4. bool List::sort()
curr is undefined
0
 
LVL 9

Accepted Solution

by:
DrAske earned 1600 total points
ID: 16436514
**************************************************************************************
#ifndef LIST_H
#define LIST_H

#include <iostream>
#include <fstream>

using namespace std;

//const int CAPACITY = 1024;
typedef int ElementType;

class Node {

public:

     ElementType data;
     Node *next;

     Node* get_first() const { return first;} // private!
private:

     Node* first;
     int mySize;

};

typedef Node *NodePointer;


class List:public Node{

     // prototype for ouput operator
      friend ostream &operator << (ostream &out, const List &aList)  // needs to be a friend
        {

     aList.display(out);
     return out;

        }
public:

     List(int maxSize = 1024);
     ~List();
     // copy constuctor
     List(const List &origList); // no ',' here!
     // assignment operator
     const List &operator = (const List &rightHandSide);
     // list traversal
     void listTraversalNode();
     void printInReverse(Node *Head);   // call function to print list in reverse
     bool sort(); // boolean function ascending
      // perform linear search
      int List::linearSearch();
     // empty operation
     bool empty() const;
     // insert and erase
     void insert(ElementType item, int pos);
     void erase(int pos);
     // output
     void display(ostream &out) const;

private:

     int mySize; // current size of list store in myArray
     //ElementType myArray[CAPACITY]; // array to store list of elements
     int myCapacity; // capacity of array
     Node *myArray; // pointer to dynamic array
    //  Node *date; <----------------- what is this
     
};

#endif
**************************************************************************************

#include <cassert>
#include <iostream>
#include <fstream>
#include <list>
#include <new>
#include <string>
#include "list.h"

using namespace std;

// prototype for ouput operator
//ostream &operator << (ostream &out, const List &alist);<-- you don't need this one

// definition of class constructor
List::List(int maxSize) : mySize(0), myCapacity(maxSize) {

     myArray = new Node;
     assert(myArray != 0);

}

// definition of class destructor
List::~List() {

     delete [] myArray;

}

// definition of copy constructor
List::List(const List &origList) : mySize(origList.mySize), myCapacity(origList.myCapacity) {

         myArray = new Node;

}

// definition of assignment operator
const List &List::operator = (const List &rightHandSide) {

     // check that not self-assignment
     if(this != &rightHandSide) {
          // allocate new array if necessary
          if(myCapacity != rightHandSide.myCapacity) {
               delete [] myArray;
               myCapacity = rightHandSide.myCapacity;
               myArray = new Node;
               // check if memory available
               if(myArray == 0) {
                    cerr << " Inadequate memory to allocate stack. \n";
                    exit(1);

               }

          }
          // copy rightHandSide's list elements into this new array
          mySize = rightHandSide.mySize;

     }
     return *this;

}
               
// definition of empty
bool List::empty() const {

     return mySize == 0;

}

// definition of display
void List::display(ostream &out) const {

     out << "\n\n The elements in the list are: ";

     NodePointer ptr = get_first(); // MODIFIED
     while(ptr != 0) {
          //out << ptr->date << " "; <----- do you mean *date* or *data* ??
            out<<ptr->data<<" "; // MODIFIED
                    ptr = ptr->next;

     }
     out << " ";

}



// definition of insert
void List::insert(ElementType item, int pos) {

     if(mySize == myCapacity) {
          cerr << " No space for linked list element, terminating execution. \n";
          exit(1);

     }
     if(pos < 0 || pos > mySize) {
          cerr << " Illegal location to insert -- " << pos << ". Linked list unchanged. \n";
          return;

     }

     // first shift array elements right to make room for item
     for(int i = mySize; i > pos; i--)
          myArray[i] = myArray[i - 1];
            mySize++;

}
// perform linear search
int List::linearSearch() { // added function

     ElementType dataVal;
     cout << " Type in value to search-> ";
     cin >> dataVal;

     int loc;
     NodePointer temp = get_first(); // MODIFED <-- instead of *first* cauze it returns first pointer :)
     for(loc = 0; loc < mySize; loc++) {
          if(temp->data == dataVal)
              {       cout << " Element located at location. ";
     return loc;
        }
          else {
               temp = temp -> next;
               cout << "\n The element is not in the list. ";
               return -1;
              }
     }

}
// traverse the list
void List::listTraversalNode() {

     NodePointer ptr = myArray->get_first(); // need to declare it with a type!
     NodePointer first = ptr;

     while(ptr != 0) {
          ptr = ptr -> next; // appropriate statements to process ptr -> data

     }

     NodePointer newptr = new Node; // newptr of type NodePointer

     NodePointer predptr = NULL;
     if(predptr != 0) { // not inserting at front
          newptr -> next = predptr -> next;
          predptr -> next = newptr;

     }
     else { // inserting at front
          newptr -> next = first;
          first = newptr; // reset first

     }

     if(predptr != 0) { // not deleting first node
          ptr = predptr -> next;
          predptr -> next = ptr -> next; // bypass

     }
     else { // deleting first node
          ptr = first;
          first = ptr -> next; // reset first

     }
     delete ptr; // return node to heap

}

// reverse print of list
void List::printInReverse(Node *Head) {

     if (Head == 0){
     cout << "List is empty." << endl;
     }
     //int count = 0;
     Node *printPtr = new Node;
     printPtr = Head;

     while(printPtr != 0) {
     printPtr = printPtr->next; //advance pointer to next location in list...
       
      }
 
}

// boolean value function ascending for node element
// the purpose of this function is to generate a boolean-valued
// function that determines whether the data items in the linked
// list are arranged in ascending order.
//sorts list in ascending order
bool List::sort() // new added function to perform above specs
{
     for(NodePointer temp = get_first(); temp != NULL; temp = temp->next)
     {
          NodePointer min = temp;

          for(NodePointer current = min; current != NULL; current = current -> next)
          {
               if(current->info < min->data)min=current; //<-------- from where did you get *info* variable?
          }

          ElementType temp_var = temp -> data;
          temp -> data = min -> data;
          min -> data = temp_var;
     }
      return true;
      else //<-------------------- what is this???????
           return false; // ???????????

}
// definition of erase
void List::erase(int pos) {

     if(mySize == 0) {
          cerr << " List is empty \n";
          return;

     }
     if(pos < 0 || pos >= mySize) {
          cerr << " Illegal location to delete -- " << pos << ". List unchanged. \n";
          return;

     }

      // decrease list size
     mySize--;

}

int main() {

     int myCapacity = 42; // It is always a good idea to *declare* the variables you are using

     // test the class constructor
     List intList;
     cout << " Constructing intList\n";

     // test empty and output of empty list
     if(intList.empty())
          cout << " Empty: \n" << intList << endl; // test output of empty list

     // test insert
     for(int i = 0; i < 9; i++) {
          cout << " Inserting " << i << " at position " << i/2 << endl;
          intList.insert(i, i/2); // insert i at position i/2

          // test output
          cout << intList << endl;

     }

     cout << " List empty? " << (intList.empty() ? "Yes" : "No") << endl;

     cout << "\nTry to insert at position -1" << endl;
     intList.insert(0, -1);

     cout << "\nTry to insert at position 10" << endl;
     intList.insert(0, 10);

     // test erase
     int index;
     cout << endl;

     while(!intList.empty()) {

          cout << " Give an index of a list element to remove: ";
          cin >> index;
          intList.erase(index);
          cout << intList << endl;

     }
     cout << " List is empty. " << endl;

     cout << "\nInserting " << myCapacity << " integers\n";

     for(int j = 0; j < myCapacity; j++)
          intList.insert(j, j);

     cout << " Attempting to insert one more integer: \n";
     intList.insert(-1, 0);
      return 0; //<-------- add this
}

***********************************************************************

regards, DrAske;
0
 
LVL 9

Expert Comment

by:DrAske
ID: 16436528
I didn't fix the code .. I add a few comment and a few modification  :o)

bye
0
 
LVL 9

Expert Comment

by:DrAske
ID: 16436556
ah !! I forgot to tell you .. that I use inheretence to let the member function in List class to be allowed to invoke
get_first() function from Node class ...

0
 

Author Comment

by:edelossantos
ID: 16438297
Perfect!
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

571 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question