Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Doubly Linked List -> main() {

Posted on 2004-10-24
23
Medium Priority
?
470 Views
Last Modified: 2013-12-14
// algorithm check

/* Filename: main.cpp
   Project:  HW#5 Testing a dbly linked list */

#include <iostream>
#include "dlist.h"
#include "util.h"

void main()
{
   int data;
   //int i;
   List<int> the_list;
   the_list.insert(0,1);
   the_list.insert(1,2);
   the_list.insert(2,3);
   the_list.insert(3,4);
   the_list.insert(4,5);
   cout << "The List: \n";
   the_list.display();
   the_list.retrieve(data);
   cout << data << " retrieved at position 1" << endl;
   the_list.remove(0);
   the_list.remove(2);
   the_list.remove(4);
   the_list.remove(5);
   the_list.insert(2,2);
   the_list.insert(7,7);
   cout << "The_List after removing positions 0 2 5 and inserting 2,2: \n";
   the_list.display();
   
   List<int> new_list(the_list);
   new_list.insert(2,9);
   cout << "A copy of The_List after inserting 2,9: \n";
   new_list.display();

   cout << "A copy of The_List displayed in reverse:\n ";
   List<int> newer_list = the_list;
   newer_list.display_rear();
   cout << endl;
}

out:

[edeloss2@pegasus part1]$ make veryclean
rm -f *.o
rm -f core
rm -f  main
[edeloss2@pegasus part1]$ make
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g main.cpp
cxx: Warning: main.cpp, line 20: variable "data" is used before its value is set
   the_list.retrieve(data);
---------------------^
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g util.cpp
cxx -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g -lm -ltask main.o util.o -o main
[edeloss2@pegasus part1]$ main
Segmentation fault (core dumped)


0
Comment
Question by:edelossantos
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 10
  • 5
  • 4
  • +2
23 Comments
 

Author Comment

by:edelossantos
ID: 12395891
# Makefile
#        It uses the C++ Compiler with all warnings and
#        full debugging; will create a single executable called 'main'
# ---------------------------------------------------------------
# the compiler
CPP = cxx
# compiler flags
CFLAGS = -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g
# linker flags to link in the libraries libm.a and libtask.a
LFLAGS = -lm -ltask
#
RM = rm -f
# ----------------------------------------------------------------
# Explanation of macros:
#     $< is any dependent file which is out of file1
#     $* is the target's basename (without extension)
#     $@ is the target's fullname
#
# add suffix .cpp since it is not a default with make util
.SUFFIXES:      .cpp .o
#
# implicit rule for compilation only:
.cpp.o:
      ${CPP} -c ${CFLAGS} $<

OFILES=            main.o util.o

HFILES=            dlist.h util.h

# dependencies
#
default:      main      
#
main:           $(OFILES)
            ${CPP} ${CFLAGS} ${LFLAGS} $(OFILES) -o $@

main.o:            main.cpp dlist.h util.h

util.o:            util.cpp util.h

#
clean:
      ${RM} *.o
      ${RM} core
#
veryclean:      clean
      ${RM}  main  

#ifndef UTIL_H  
#define UTIL_H

#define NULL 0L

#define STDSCREEN 80        
#define DOWN 0                        
#define UP   1
#define END   0
#define START 1
#define FAIL    0
#define SUCCESS 1
#define MISS -1
#define HIT   1

enum Error_code {success,fail,range_error,underflow,overflow,fatal,
                not_present,duplicate_error,entry_inserted,entry_found,
                internal_error };

void clearScreen();
void clearTop();                      
void clearBelowTop();                
void goTop();                          
void topLine(const char * text = " "  );  
void bottomLin (char * text = " ");  
void hitAnyKey();                  
void flushInput();                  
void Warning(char *);                  
void Error(char *);                  
bool promptYesNo(char * prompt="");    
void EatWhiteSpace(void);            

#endif

/* filename: util.cpp
   Purpose: I/O and VT100 screen manipulation utility functions */

#include <iostream>
#include <ctype.h>
#include <stdlib.h>
#include "util.h"
 
void clearScreen (void) {

  cout << "\033[2J";          
  cout << "\033[;f";          

}

void clearTop()
 
  {cout << "\033[0;0f" << "\033[0K";}

void clearBelowTop()
 
  {cout << "\033[1;0f" << "\033[1B" << "\033[J";}

void goTop ()
 
  {cout << "\033[0;0f";}

void topLine(const char str[])
 
  {cout << "\033[0;0f" << "\033[0K" << str;}

void bottomLine (char * str)
 
  {cout << "\033[23;0Hf" << "\033[2K" << str;}

void hitAnyKey() {
   
   char ch;
   bottomLine ("Hit Enter to continue...");
   cin.get(ch);
   clearScreen();

}

void flushInput () {
   
   char buff[81];
   if (cin)
      cin.getline(buff,80);    

}

void Warning(char *message) {
 
   cerr << message;

}

void Error(char *message) {
 
   cerr << message;
   exit(1);

}

void EatWhiteSpace() {
 
    char ch;
    do {
      cin.get(ch);
    }
    while(isspace(ch));

    if(ch != EOF)
      cin.putback(ch);

}

bool promptYesNo(char * c) {
 
   char ch;
   cout << c << " [y|n]?";
   do {
      cin.get(ch);  
      tolower(ch);
      } while (ch != 'y' && ch != 'n');
   return (ch == 'y');

}

#ifndef DLIST_H
#define DLIST_H
#include <iostream>
#include <new>

template <class Entry_type>
class Node
{
 public:
    Node();
    Node(const Entry_type &);
    Entry_type entry;
    Node< Entry_type > *next;
    Node< Entry_type > *back;
};

template< class Entry_type >
Node< Entry_type >::Node()
{
  next = NULL;
  back = NULL;
}

template< class Entry_type >
Node< Entry_type >::Node( const Entry_type &usrEntry)
{
  next = NULL;
  back = NULL;
  entry = usrEntry;
}

template <class Entry_type>
class List {

 public:
   List();

/* needed to manage dynamic memory */
   List(const List &);
   ~List();
   void operator = (const List & copy);

/* standard general list operations */
   void clear();
   bool empty() const;
   bool full() const;
   int  size() const;
   void display() const;
   void display_rear() const;
   Entry_type retrieve(const int) const;
   void replace(const int, const Entry_type&);
   void insert(const int, const Entry_type&);
   void remove(const int);

private:
   Node< Entry_type > *head;
   Node< Entry_type > *rear;
   int count;
};

template< class Entry_type >
List< Entry_type >::List()
{
  head = NULL;
  rear = NULL;
  count = 0;
}

template< class Entry_type >
List< Entry_type >::List(const List & copy)
{
  Node< Entry_type > *currentPtr = copy.head;
  while ( (*currentPtr).next != NULL){
   insert(size()+1, (*currentPtr).entry);
   currentPtr = (*currentPtr).next;
  }
  insert(size()+1, (*currentPtr).entry);  
}

template< class Entry_type >
List< Entry_type >::~List()
{
  cout<<"Deleting list\n";
/*  if (!empty()){
    Node< Entry_type > *currentPtr = head;
//    Node< Entry_type > *temp;
    while (head != NULL){
      while ((*currentPtr).next != NULL )
      currentPtr = (*currentPtr).next;
      delete currentPtr;
      currentPtr = head;
    }
  }
*/
}

template< class Entry_type >
void List< Entry_type >::operator = (const List & copy)
{
  Node< Entry_type > *currentPtr = copy.head;
  while ( (*currentPtr).next != NULL){
   insert(size()+1, (*currentPtr).entry);
   currentPtr = (*currentPtr).next;
  }
  insert(size()+1, (*currentPtr).entry);  
}

template< class Entry_type >
void List< Entry_type >::clear()
{
  if (!empty()){
    Node< Entry_type > *currentPtr = head;
    while (head != NULL){
      while ((*currentPtr).next != NULL )
      currentPtr = (*currentPtr).next;
      delete currentPtr;
      currentPtr = head;
      delete head;
      head = NULL;
    }
  }
  count = 0;
}

template< class Entry_type >
bool List< Entry_type >::empty() const
{
  if (count == 0)
    return true;
  return false;
}

template< class Entry_type >
bool List< Entry_type >::full() const
{
  return false;
}

template< class Entry_type >
int List< Entry_type >::size() const
{
  return count;
}

template< class Entry_type >
void List< Entry_type >::display() const
{
  if (head == NULL)
    return;
  Node< Entry_type > *currentPtr = head;
  while ( (*currentPtr).next != NULL){
   cout<<(*currentPtr).entry;
   currentPtr = (*currentPtr).next;
  }
  cout<<(*currentPtr).entry;
  cout<<endl;
}

template< class Entry_type >
void List< Entry_type >::display_rear() const
{
  Node< Entry_type > *currentPtr = rear;
  while ( currentPtr != head){
   cout<<(*currentPtr).entry;
   currentPtr = (*currentPtr).back;
  }
  cout<<(*currentPtr).entry;
  cout<<endl;
}

template< class Entry_type >
Entry_type List< Entry_type >::retrieve(const int pos) const
{
  if (empty())
    throw "Underflow, cannot retrieve";
  if (pos > count)
    throw "Range Error, cannot retrieve";
  Node< Entry_type > *currentPtr = head;
  for (int i = 1; i < pos; i++)
    currentPtr = (*currentPtr).next;
  return (*currentPtr).entry;
}

template< class Entry_type >
void List< Entry_type >::replace(const int pos, const Entry_type &usrEntry)
{
  if (empty())
    throw "Underflow, cannot replace";
  if (pos > count)
    throw "Range Error, cannot replace";
  Node< Entry_type > *currentPtr = head;
  for (int i = 0; i < pos; i++)
    currentPtr = (*currentPtr).next;
  (*currentPtr).entry = usrEntry;
 
}

template< class Entry_type >
void List< Entry_type >::insert(const int pos, const Entry_type &usrEntry)
{
  if (full())
    throw "Overflow, cannot insert";
  if (pos > count+1)
    throw "Range Error, cannot insert";
  if (pos == 1)
    head = new Node< Entry_type>(usrEntry);

  else {
   Node< Entry_type > *currentPtr = head;
   Node< Entry_type > *newPtr = new Node< Entry_type >;
   for (int i = 1; i < pos-1; i++)
     currentPtr = (*currentPtr).next;
   (*newPtr).next = (*currentPtr).next;
   (*newPtr).entry = usrEntry;
   (*currentPtr).next = newPtr;
   (*newPtr).back = currentPtr;
   currentPtr = head;

   if ((*currentPtr).next != NULL){
    while ( (*(*currentPtr).next).next != NULL)
     currentPtr = (*currentPtr).next;
    rear = (*currentPtr).next;
   }
  }

 count++;
}

template< class Entry_type >
void List< Entry_type >::remove( const int pos)
{
  if (empty())
    throw "Underflow, cannot remove";
  if (pos > count)
    throw "Range Error, cannot insert";
  Node< Entry_type > *currentPtr = head;
  for (int i = 1; i < pos; i++)
    currentPtr = (*currentPtr).next;
  Node< Entry_type > *tempPtr = (*(*currentPtr).next).next;
  delete (*currentPtr).next;
  (*currentPtr).next = tempPtr;

  if ((*currentPtr).next != NULL){
   while ( (*(*currentPtr).next).next != NULL)
    currentPtr = (*currentPtr).next;
   rear = (*currentPtr).next;
  }
  count--;
}

#endif

/* Filename: main.cpp
   Project:  HW#5 Testing a dbly linked list */

#include <iostream>
#include "dlist.h"
#include "util.h"

void main()
{
   int data;
   //int i;
   List<int> the_list;
   the_list.insert(0,1);
   the_list.insert(1,2);
   the_list.insert(2,3);
   the_list.insert(3,4);
   the_list.insert(4,5);
   cout << "The List: \n";
   the_list.display();
   the_list.retrieve(data);
   cout << data << " retrieved at position 1" << endl;
   the_list.remove(0);
   the_list.remove(2);
   the_list.remove(4);
   the_list.remove(5);
   the_list.insert(2,2);
   the_list.insert(7,7);
   cout << "The_List after removing positions 0 2 5 and inserting 2,2: \n";
   the_list.display();
   
   List<int> new_list(the_list);
   new_list.insert(2,9);
   cout << "A copy of The_List after inserting 2,9: \n";
   new_list.display();

   cout << "A copy of The_List displayed in reverse:\n ";
   List<int> newer_list = the_list;
   newer_list.display_rear();
   cout << endl;
}



0
 
LVL 4

Assisted Solution

by:pankajtiwary
pankajtiwary earned 160 total points
ID: 12396353
Hi edelossantos,

There are a couple of things I would like to comment on:
1. NEVER WRITE void main(), ALWAYS WRITE int main(). a void main() does not guarantee you to work the way you think, int main() does.
2. A normal practice is to write a using namespace std; after you include iostream library to use (obviously if you want).
3. As it says during compilation, you need to set the data to 1 before calling the_list.retrieve(data).
4. This may not be necessary but the extension of a C++ code is .cxx or .cc but not .cpp

Regarding the core, you are not initializing the list properly. In your constructor you setting head to NULL and then you are trying to dereference that head in your insert function. The solution is to change your constructor of list so that head is allocated to some memory and then you assign values to it. Hope this solves your problem.

Cheers!
0
 
LVL 9

Assisted Solution

by:jhshukla
jhshukla earned 360 total points
ID: 12396704
> 4. This may not be necessary but the extension of a C++ code is .cxx or .cc but not .cpp
.cpp is a valid extension for C++. and it is not that compilers accept this extension, MSVC will create files with .cpp when it is asked to create a C++ source.
C, cc, cxx, cpp, CC are valid c++ extensions
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:edelossantos
ID: 12396772
o.k. I made the changes to main and am still a little confused.

>>Regarding the core, you are not initializing the list properly. In your constructor you setting head to NULL and then you are trying to dereference that head in your insert function. The solution is to change your constructor of list so that head is allocated to some memory and then you assign values to it. Hope this solves your problem.

Here is my main with changes and new errors:

/* Filename: main.cpp
   Project:  HW#5 Testing a dbly linked list */

#include <iostream>
#include "dlist.h"
#include "util.h"

using namespace std;

int main() {
 
   int data;
   //int i;
   List<int> the_list;
   the_list.insert(0,1);
   the_list.insert(1,2);
   the_list.insert(2,3);
   the_list.insert(3,4);
   the_list.insert(4,5);
   cout << "The List: \n";
   the_list.display();
   //int data = 1;
   the_list.retrieve(data,1);
   cout << data << " retrieved at position 1" << endl;
   the_list.remove(0);
   the_list.remove(2);
   the_list.remove(4);
   the_list.remove(5);
   the_list.insert(2,2);
   the_list.insert(7,7);
   cout << "The_List after removing positions 0 2 5 and inserting 2,2: \n";
   the_list.display();
   
   List<int> new_list(the_list);
   new_list.insert(2,9);
   cout << "A copy of The_List after inserting 2,9: \n";
   new_list.display();

   cout << "A copy of The_List displayed in reverse:\n ";
   List<int> newer_list = the_list;
   newer_list.display_rear();
   cout << endl;
}

out:

[edeloss2@pegasus part1]$ make
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g main.cpp
cxx: Error: main.cpp, line 23: too many arguments in function call
   the_list.retrieve(data,1);
--------------------------^
cxx: Warning: main.cpp, line 23: variable "data" is used before its value is set
   the_list.retrieve(data,1);
---------------------^
cxx: Info: 1 error detected in the compilation of "main.cpp".
make: *** [main.o] Error 1

0
 
LVL 11

Assisted Solution

by:avizit
avizit earned 480 total points
ID: 12396848
The error you get is
>> cxx: Error: main.cpp, line 23: too many arguments in function call

so this suggests that you are passing more arguments than that is required for the function .. so

you have the function prototype
Entry_type retrieve(const int) const;  <----------------ONE arg reqd

and in line 23 you have

>>the_list.retrieve(data,1);       <--------------passing TWO    data and 1

so basically you are passing two arguments when 1 is required ..

0
 
LVL 11

Assisted Solution

by:avizit
avizit earned 480 total points
ID: 12396862
the second is a warning  which says

>>>line 23: variable "data" is used before its value is set

so what does this suggest .. it implies that you are using some variable which was not initialised
and it also hints that the variable in question is in line 23 which so that variable is "data" and you have in  main .



int main() {
    int data;
.............................//// many lines but you dont initialize data in those
   the_list.retrieve(data,1);


so you see you are using "data" without putting any value in it

its like saying

int a ;
cout<<a<<endl;

you have no idea what output you will get.


.........

as you can see del , most of the errors you can easily fix your errors by looking at the compiler output and you also get sufficnet hints where your error might be located .. you get the filename and line number

so try to fix yourself these should be quite simple errors for you . youhave been doping c++ for quite a while now
0
 

Author Comment

by:edelossantos
ID: 12397180
I can't figure this one out...I am going to repost referencing this url.
0
 
LVL 11

Assisted Solution

by:avizit
avizit earned 480 total points
ID: 12397211
cxx: Error: main.cpp, line 23: too many arguments in function call
   the_list.retrieve(data,1);
--------------------------^

Too many arguments to a function call  means you have passed more arguments than is required , for example if you call the sqrt() function as

sqrt(1,2,3,4 )  ; then you are passing too many arguments as only one is required and you are passing 4 ..

your function prototype
Entry_type retrieve(const int) const;   <--- says that only one argument is required which should be of type INT but in the line 23

the_list.retrieve(data,1);  <-- here you are passing TWO arguments
#1: data
#2 : 1  

hence you get the warning
-------------------------------------------------------
cxx: Warning: main.cpp, line 23: variable "data" is used before its value is set
   the_list.retrieve(data,1);

This warning  means that you are using one variable which was not initialized  ..

say for example you have code

int a;
cout<<a<<endl;

in the above case you dont know what the cout is going to print cos you dont know the value of a .. i.e a is uninitialized

similarly in your code "data" is uninitialized ..

you dont know what value "data" holds ..

maybe you wanted to set data to 1
which you can do by

int data;
data = 1;

and then youcan call the function as
the_list.retrieve(data) ;
0
 

Author Comment

by:edelossantos
ID: 12397316
o.k.  I am with you so far...I removed the extra const in the dlist.h and I am getting a core dump.

[edeloss2@pegasus part1]$ make veryclean
rm -f *.o
rm -f core
rm -f  main
[edeloss2@pegasus part1]$ make
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g main.cpp
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g util.cpp
cxx -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g -lm -ltask main.o util.o -o main
[edeloss2@pegasus part1]$ main
Segmentation fault (core dumped)
0
 

Author Comment

by:edelossantos
ID: 12397340
what is meant by apprixmate space and time for each of the algorithms...is there a formula?...I am thinking that this is discrete mathematics which I have not taken yet.  How do you calculate????
0
 
LVL 11

Assisted Solution

by:avizit
avizit earned 480 total points
ID: 12397369
yo dont have to remove the extra const  ...

you just have to change

int data ;

to
int data = 1  ;    // as was suggested by pankaj tiwary   but dont do that unless you know what it is for and why you would like to set it to 1 or any other value

and change

the_list.retrieve(data,1)  to

the_list.retrieve(data)


----------------------------
0
 

Author Comment

by:edelossantos
ID: 12397427
o.k.  

but...what is causing the segmentation core dump?
0
 

Author Comment

by:edelossantos
ID: 12397442
>>Regarding the core, you are not initializing the list properly. In your constructor you setting head to NULL and then you are trying to dereference that head in your insert function. The solution is to change your constructor of list so that head is allocated to some memory and then you assign values to it. Hope this solves your problem.  pankaj tiwary  

I do not know how to do the suggested for the core dump...hence...fyi....I will be repeating cs classes.
0
 
LVL 9

Assisted Solution

by:jhshukla
jhshukla earned 360 total points
ID: 12397499
a core dump occur when you reference memory that you are not supposed/allowed to.

template< class Entry_type >
void List< Entry_type >::insert(const int pos, const Entry_type &usrEntry)
{
  if (full())
    throw "Overflow, cannot insert";
  if (pos > count+1)
    throw "Range Error, cannot insert";
  if (pos == 1)
    head = new Node< Entry_type>(usrEntry);   <<<< I believe your problem is here.

if the position is one, you simply make head point to the new element. you lose the rest of the chain. not really, you can traverse back from rear but you are not doing that. i suggest this approach instead:
1. if current size is 0, head = rear = new node; return;
2. create a local pointer to new node, and an iterator pointer starting at head
3. make a counter go from 0..pos-1 and iterate while incrementing.
4. you know how to insert at that position then...
0
 
LVL 9

Assisted Solution

by:jhshukla
jhshukla earned 360 total points
ID: 12397533
head---------v                   rear-----v
NULL<---node1<--->node2<--->node3--->NULL

changes to

head---------v                                                            rear-----v
NULL<---nodeX--->NULL        NULL<---node1<--->node2<--->node3--->NULL

[rear pointer is pointing at node3].

then you increment the count. on your next insert you try to traverse count nodes but your program crashes. one of the things i learned in last 3 years is that programming is not limited to keyboard and screen; it __really__ helps to draw pictures as you step through your code.
0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 1000 total points
ID: 12398616
>>>> Entry_type retrieve(const int) const;
   
Because of this you have to change

     the_list.retrieve(data);

to

    data = the_list.retrieve(0);  // or any other valid pos

Regards, Alex

0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 1000 total points
ID: 12399600
I checked your DList and found a lot of severe errors, most of them caused by not correctly porting a previously 1-based list to 0-based and by not (correctly) initializing pointers or while loops.

Here is a tested version of your prog.

#ifndef DLIST_H
#define DLIST_H
#include <iostream>
#include <new>

template <class Entry_type>
class Node
{
 public:
    Node();
    Node(const Entry_type &);
    Entry_type entry;
    Node< Entry_type > *next;
    Node< Entry_type > *back;
};

template< class Entry_type >
Node< Entry_type >::Node()
{
  next = NULL;
  back = NULL;
}

template< class Entry_type >
Node< Entry_type >::Node( const Entry_type &usrEntry)
{
  next = NULL;
  back = NULL;
  entry = usrEntry;
}

template <class Entry_type>
class List {

 public:
   List();

/* needed to manage dynamic memory */
   List(const List &);
   ~List();
   void operator = (const List & copy);

/* standard general list operations */
   void clear();
   bool empty() const;
   // bool full() const;  makes no sense for linked lists
   int  size() const;
   void display() const;
   void display_rear() const;
   Entry_type retrieve(const int) const;
   void replace(const int, const Entry_type&);
   void insert(const int, const Entry_type&);
   void append(const Entry_type&);   // to insert at end
   void remove(const int);

private:
   Node< Entry_type > *head;
   Node< Entry_type > *rear;
   int count;
};

template< class Entry_type >
List< Entry_type >::List()
{
  head = NULL;
  rear = NULL;
  count = 0;
}

template< class Entry_type >
List< Entry_type >::List(const List & copy)
{
    head = NULL;
    rear = NULL;
    count = 0;
    Node< Entry_type > *currentPtr = copy.head;
    // insert all at end
    while (currentPtr != NULL)
    {
        append(count, currentPtr->entry);
        currentPtr = currentPtr->next;
    }
}

template< class Entry_type >
List< Entry_type >::~List()
{
  cout<<"Deleting list\n";
  clear();
}

template< class Entry_type >
void List< Entry_type >::operator = (const List & copy)
{
    Node< Entry_type > *currentPtr = copy.head;
    // insert all nodes of list 'copy' at end
    while ( currentPtr != NULL)
    {
        append(currentPtr->entry);
        currentPtr = currentPtr->next;
    }
   
}

template< class Entry_type >
void List< Entry_type >::clear()
{
   Node< Entry_type > *currentPtr = head;
   Node< Entry_type > *prevPtr    = head;
   // delete all nodes in a loop and save next pointer before delete
   while (currentPtr != NULL)
   {
       prevPtr    = currentPtr;
       currentPtr = currentPtr->next;
       delete prevPtr;
   }
   head  = rear = NULL;
   count = 0;
}

template< class Entry_type >
bool List< Entry_type >::empty() const
{
    return (count == 0);
}

template< class Entry_type >
int List< Entry_type >::size() const
{
   return count;
}

template< class Entry_type >
void List< Entry_type >::display() const
{
  Node< Entry_type > *currentPtr = head;
  while (currentPtr != NULL){
   cout<<currentPtr->entry << ' '; // add space character
   currentPtr = currentPtr->next;
  }
  cout<<endl;
}

template< class Entry_type >
void List< Entry_type >::display_rear() const
{
  Node< Entry_type > *currentPtr = rear;
  while ( currentPtr != NULL){
    cout<<currentPtr->entry << ' ';  // add space character
    currentPtr = currentPtr->back;  
  }
  cout<<endl;
}

template< class Entry_type >
Entry_type List< Entry_type >::retrieve(const int pos) const
{
    // that covers underflow as well
    if (pos >= count)
        throw "Range Error, cannot retrieve";
    Node< Entry_type > *currentPtr = head;
    for (int i = 0; i < pos; i++)
       currentPtr = currentPtr->next;
    return currentPtr->entry;
}

template< class Entry_type >
void List< Entry_type >::replace(const int pos, const Entry_type &usrEntry)
{
   if (pos > count)
     throw "Range Error, cannot replace";
  Node< Entry_type > *currentPtr = head;
  for (int i = 0; i < pos; i++)
    currentPtr = currentPtr->next;
  currentPtr->entry = usrEntry;
 
}

template< class Entry_type >
void List< Entry_type >::insert(const int pos, const Entry_type &usrEntry)
{
    if (pos > count)
        throw "Range Error, cannot insert";
    if (pos == 0 && count == 0)
    {
        head = new Node< Entry_type>(usrEntry);
        head->next = head->back = NULL;
        rear = head;
    }
    else {
        Node< Entry_type > *currentPtr = head;
        Node< Entry_type > *newPtr = new Node< Entry_type >;
        for (int i = 0; i < pos-1; i++)
            currentPtr = currentPtr->next;
        if (pos == 0)
        {
            head = newPtr;
            head->next = currentPtr;
            head->back = NULL;
            rear = head;
        }
        else
        {
           
            newPtr->next = currentPtr->next;
            newPtr->entry = usrEntry;
            currentPtr->next = newPtr;
            newPtr->back = currentPtr;

            if (pos == count)
                rear = newPtr;

        }
    }
   
    count++;
}

template< class Entry_type >
void List< Entry_type >::append(const Entry_type &usrEntry)
{
    insert(count, usrEntry);
}

template< class Entry_type >
void List< Entry_type >::remove( const int pos)
{
  if (empty())
    throw "Underflow, cannot remove";
  if (pos >= count)
    throw "Range Error, cannot insert";
  Node< Entry_type > *currentPtr = head;
  for (int i = 0; i < pos; i++)
    currentPtr = currentPtr->next;
  Node< Entry_type > *nextPtr = currentPtr->next;
  Node< Entry_type > *backPtr = currentPtr->back;
  delete currentPtr;
  if (pos == 0)
  {
      head = nextPtr;
      head->back = NULL;
  }
  else
  {
      backPtr->next = nextPtr;
      if (nextPtr != NULL)
          nextPtr->back = backPtr;

  }
  if (pos == count - 1)
      rear = backPtr;

  count--;
}

#endif

/* Filename: main.cpp
   Project:  HW#5 Testing a dbly linked list */

void main()
{
   int data;
   //int i;
   List<int> the_list;
   the_list.insert(0,1);
   the_list.insert(1,2);
   the_list.insert(2,3);
   the_list.insert(3,4);
   the_list.insert(4,5);
   cout << "The List: \n";
   the_list.display();
   data = the_list.retrieve(1);
   cout << data << " retrieved at position 1" << endl;
   the_list.remove(0);
   the_list.display();
   the_list.remove(2);
   the_list.display();
   the_list.remove(2);     // Note, after removing two entries size() is 3 and last pos is 2
   the_list.display();
   the_list.remove(1);
   the_list.display();
   the_list.insert(1,2);
   the_list.display();
   the_list.insert(2,3);
   cout << "The_List after removing positions 0 2 2 1 and inserting 1,2 and 2,3: \n";
   the_list.display();
   
   List<int> new_list(the_list);
   new_list.insert(2,9);
   cout << "A copy of The_List after inserting 2,9: \n";
   new_list.display();

   cout << "A copy of The_List displayed in reverse:\n";
   List<int> newer_list = the_list;
   newer_list.display_rear();
   cout << endl;
}

Regards, Alex
0
 

Author Comment

by:edelossantos
ID: 12401029
Alex,

I am getting this error at line 86.

[edeloss2@pegasus part1]$ make
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g main.cpp
cxx: Error: dlist.h, line 86: too many arguments in function call
          detected during instantiation of "List<Entry_type>::List(const
                    List<Entry_type> &) [with Entry_type=int]"
        append(count, currentPtr->entry);
----------------------^
cxx: Info: 1 error detected in the compilation of "main.cpp".
make: *** [main.o] Error 1
0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 1000 total points
ID: 12401305
>>> append(count, currentPtr->entry);

I added that function but forgot to give the implementation:

template <class Entry_type>
class List {

 public:
   List();

/* needed to manage dynamic memory */
   List(const List &);
   ~List();
   void operator = (const List & copy);

/* standard general list operations */
   void clear();
   bool empty() const;
   // bool full() const;  makes no sense for linked lists
   int  size() const;
   void display() const;
   void display_rear() const;
   Entry_type retrieve(const int) const;
   void replace(const int, const Entry_type&);
   void insert(const int, const Entry_type&);
   void append(const Entry_type&);   // to insert at end
   void remove(const int);

private:
   Node< Entry_type > *head;
   Node< Entry_type > *rear;
   int count;
};

...

template< class Entry_type >
void List< Entry_type >::append(const Entry_type &usrEntry)
{
    insert(count, usrEntry);
}

Regards, Alex

0
 

Author Comment

by:edelossantos
ID: 12401787
Alex, please check...there is something that I am still getting incorrect...

#ifndef DLIST_H
#define DLIST_H
#include <iostream>
#include <new>

template <class Entry_type>
class Node
{
 public:
    Node();
    Node(const Entry_type &);
    Entry_type entry;
    Node< Entry_type > *next;
    Node< Entry_type > *back;
};

template< class Entry_type >
Node< Entry_type >::Node()
{
  next = NULL;
  back = NULL;
}

template< class Entry_type >
Node< Entry_type >::Node( const Entry_type &usrEntry)
{
  next = NULL;
  back = NULL;
  entry = usrEntry;
}

template <class Entry_type>
class List {

 public:
   List();

/* needed to manage dynamic memory */
   List(const List &);
   ~List();
   void operator = (const List & copy);

/* standard general list operations */
   void clear();
   bool empty() const;
   // bool full() const;  makes no sense for linked lists
   int  size() const;
   void display() const;
   void display_rear() const;
   Entry_type retrieve(const int) const;
   void replace(const int, const Entry_type&);
   void insert(const int, const Entry_type&);
   void append(const Entry_type&);   // to insert at end
   void remove(const int);

private:
   Node< Entry_type > *head;
   Node< Entry_type > *rear;
   int count;
};

template< class Entry_type >
List< Entry_type >::List()
{
  head = NULL;
  rear = NULL;
  count = 0;
}

template< class Entry_type >
List< Entry_type >::List(const List & copy)
{
    head = NULL;
    rear = NULL;
    count = 0;
    Node< Entry_type > *currentPtr = copy.head;
    // insert all at end
    while (currentPtr != NULL)
    {
        append(count, currentPtr->entry);
        currentPtr = currentPtr->next;
    }
}

template< class Entry_type >
List< Entry_type >::~List()
{
  cout<<"Deleting list\n";
  clear();
}

template< class Entry_type >
void List< Entry_type >::operator = (const List & copy)
{
    Node< Entry_type > *currentPtr = copy.head;
    // insert all nodes of list 'copy' at end
    while ( currentPtr != NULL)
    {
        append(currentPtr->entry);
        currentPtr = currentPtr->next;
    }
   
}

template< class Entry_type >
void List< Entry_type >::clear()
{
   Node< Entry_type > *currentPtr = head;
   Node< Entry_type > *prevPtr    = head;
   // delete all nodes in a loop and save next pointer before delete
   while (currentPtr != NULL)
   {
       prevPtr    = currentPtr;
       currentPtr = currentPtr->next;
       delete prevPtr;
   }
   head  = rear = NULL;
   count = 0;
}

template< class Entry_type >
bool List< Entry_type >::empty() const
{
    return (count == 0);
}

template< class Entry_type >
int List< Entry_type >::size() const
{
   return count;
}

template< class Entry_type >
void List< Entry_type >::display() const
{
  Node< Entry_type > *currentPtr = head;
  while (currentPtr != NULL){
   cout<<currentPtr->entry << ' '; // add space character
   currentPtr = currentPtr->next;
  }
  cout<<endl;
}

template< class Entry_type >
void List< Entry_type >::display_rear() const
{
  Node< Entry_type > *currentPtr = rear;
  while ( currentPtr != NULL){
    cout<<currentPtr->entry << ' ';  // add space character
    currentPtr = currentPtr->back;  
  }
  cout<<endl;
}

template< class Entry_type >
Entry_type List< Entry_type >::retrieve(const int pos) const
{
    // that covers underflow as well
    if (pos >= count)
        throw "Range Error, cannot retrieve";
    Node< Entry_type > *currentPtr = head;
    for (int i = 0; i < pos; i++)
       currentPtr = currentPtr->next;
    return currentPtr->entry;
}

template< class Entry_type >
void List< Entry_type >::replace(const int pos, const Entry_type &usrEntry)
{
   if (pos > count)
     throw "Range Error, cannot replace";
  Node< Entry_type > *currentPtr = head;
  for (int i = 0; i < pos; i++)
    currentPtr = currentPtr->next;
  currentPtr->entry = usrEntry;
 
}

template< class Entry_type >
void List< Entry_type >::insert(const int pos, const Entry_type &usrEntry)
{
    if (pos > count)
        throw "Range Error, cannot insert";
    if (pos == 0 && count == 0)
    {
        head = new Node< Entry_type>(usrEntry);
        head->next = head->back = NULL;
        rear = head;
    }
    else {
        Node< Entry_type > *currentPtr = head;
        Node< Entry_type > *newPtr = new Node< Entry_type >;
        for (int i = 0; i < pos-1; i++)
            currentPtr = currentPtr->next;
        if (pos == 0)
        {
            head = newPtr;
            head->next = currentPtr;
            head->back = NULL;
            rear = head;
        }
        else
        {
           
            newPtr->next = currentPtr->next;
            newPtr->entry = usrEntry;
            currentPtr->next = newPtr;
            newPtr->back = currentPtr;

            if (pos == count)
                rear = newPtr;

        }
    }
   
    count++;
}

template< class Entry_type >
void List< Entry_type >::append(const Entry_type &usrEntry)
{
    insert(count, usrEntry);
}

template< class Entry_type >
void List< Entry_type >::remove( const int pos)
{
  if (empty())
    throw "Underflow, cannot remove";
  if (pos >= count)
    throw "Range Error, cannot insert";
  Node< Entry_type > *currentPtr = head;
  for (int i = 0; i < pos; i++)
    currentPtr = currentPtr->next;
  Node< Entry_type > *nextPtr = currentPtr->next;
  Node< Entry_type > *backPtr = currentPtr->back;
  delete currentPtr;
  if (pos == 0)
  {
      head = nextPtr;
      head->back = NULL;
  }
  else
  {
      backPtr->next = nextPtr;
      if (nextPtr != NULL)
          nextPtr->back = backPtr;

  }
  if (pos == count - 1)
      rear = backPtr;

  count--;
}

#endif

out:

[edeloss2@pegasus part1]$ make
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g main.cpp
cxx: Error: dlist.h, line 86: too many arguments in function call
          detected during instantiation of "List<Entry_type>::List(const
                    List<Entry_type> &) [with Entry_type=int]"
        append(count, currentPtr->entry);
----------------------^
cxx: Info: 1 error detected in the compilation of "main.cpp".
make: *** [main.o] Error 1



0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 1000 total points
ID: 12401910
Sorry, i didn't read the error message exactly...

template< class Entry_type >
List< Entry_type >::List(const List & copy)
{
    head = NULL;
    rear = NULL;
    count = 0;
    Node< Entry_type > *currentPtr = copy.head;
    // insert all at end
    while (currentPtr != NULL)
    {
        // append(count, currentPtr->entry);   // CHANGE THAT TO
        append(currentPtr->entry);                // THAT
        currentPtr = currentPtr->next;
    }
}

Regards, Alex

0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 12402492
Del, i would recommend you to check the differences between the current implementation and the version you posted above.

You'll see that the current version is much simpler, not using constructions like

  (*(*currentPtr).next).next

that requires at least a minimum of 2 nodes (or it crashes). Also, the while loops now check the pointers directly

   not:  while ((*currentPtr).next != NULL) ...  
   but:  while (currentPtr != NULL) ...

You also should try to make the number of cases as small as possible. Then, it's easier to check for remaining cases whether all variables are initialized and correctly set.

Regards, Alex


0
 

Author Comment

by:edelossantos
ID: 12402536
Thank you Alex.  Del
0

Featured Post

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

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

Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
Update (December 2011): Since this article was published, the things have changed for good for Android native developers. The Sequoyah Project (http://www.eclipse.org/sequoyah/) automates most of the tasks discussed in this article. You can even fin…
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 goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
Suggested Courses

636 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