• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 357
  • Last Modified:

Singly-Linked List

# 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  -gall
# 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=            list.h node.h  util.h

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

main.o:            main.cpp list.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 bottomLine (char * text = " ");  
void hitAnyKey ();                  
void flushInput ();                  
void Warning(char *);                  
void Error(char *);                  
bool promptYesNo(char * prompt="");    
void EatWhiteSpace(void);              

#endif

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


#include "util.h"

#include <iostream>
#include <ctype.h>
#include <cstdlib>

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 any key 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');

}

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


#include "util.h"

#ifndef LIST_H
#define LIST_H

#include <iostream>

typedef int Position;

template <class Entry_type>

class List {
public:
   
   List();
   List(const List<Entry_type> & copy);
   ~List();
   void operator = (const List<Entry_type> & copy);
   void clear();
   bool empty() const;
   bool full() const;
   int  size() const;
   void display() const;

   Error_code retrieve(const Position, Entry_type&) const;
   Error_code replace(const Position, const Entry_type&);
   Error_code insert(const Position, const Entry_type&);
   Error_code remove(const Position);

protected:

   int count;
   Node<Entry_type> *head;
   Node<Entry_type> *set_position(int position) const;

};

template<class Entry_type>
Node<Entry_type> *List<Entry_type>::set_position(int position) const {
 
  if(position < 1 || position > count)
    return NULL;

   Node<Entry_type> *marker = head;
   for(int i = 1; i < position; i ++ )
     marker = marker->next;
     return marker;

}

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

}

template<class Entry_type>
List<Entry_type>::~List() {clear();}

template<class Entry_type>
List<Entry_type>::List(const List<Entry_type> &origList) {
   
      count = origList.count;

      if(origList.head == NULL)
        head = NULL;

      else {
        head = new Node<Entry_type>(origList.head->entry);

        Node<Entry_type> *orig = origList.head->next;
        Node<Entry_type> *copy = head;

         while(orig != NULL) {
           copy->next = new Node<Entry_type>(orig->entry);
           orig = orig->next;
           copy = copy->next;
         }
      }
     
}

template<class Entry_type>
void List<Entry_type>::operator=(const List<Entry_type> &copy) {}

template <class Entry_type>
void List<Entry_type>::clear() {
 
   Node<Entry_type> *marker = head;
   Node<Entry_type> *lag_ptr;
   marker = head;

   while(marker != NULL) {
      lag_ptr = marker;
      marker = marker->next;
      delete lag_ptr;
   
    }
    head = NULL;
    count = 0;
}

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

template<class Entry_type>
bool List<Entry_type>::full() const {
 
   Node<Entry_type> *test = new Node<Entry_type>();
   return(test == NULL);

}

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> *marker = head;

   while(marker != NULL) {
      cout << marker->entry << " ";
      marker = marker->next;
   }
   cout << endl;
}

template<class Entry_type>
Error_code List<Entry_type>::retrieve(const Position p,Entry_type &item) const
{
  Node<Entry_type> *marker = set_position(p);
  if (marker == NULL)
      return range_error;
  item = marker->entry;
  return success;

}

template<class Entry_type>
Error_code List<Entry_type>::replace(const Position p, const Entry_type & item)
{
  Node<Entry_type> *marker = set_position(p);
  if (marker == NULL)
      return range_error;
  marker->entry = item;
  return success;

}


template<class Entry_type>
Error_code List<Entry_type>::insert(const Position p, const Entry_type & item)
{
 
  if(full())
    return overflow;

  if(p < 1 || p > count + 1)
    return range_error;

  Node<Entry_type> *marker = head;
  Node<Entry_type> *new_node = new Node<Entry_type>(item);

  if (p == 1)  {
      new_node->next = head;
      head = new_node;
 
  }
  else {
     for(int i = 1; i < p - 1; i++)
        marker = marker->next;

     new_node->next = marker->next;
     marker->next = new_node;
   
   }
   count++;
   return success;

}

template<class Entry_type>
Error_code List<Entry_type>::remove(const Position p) {
 
  if(empty())
    return underflow;

  if(p < 1 || p > count)
    return range_error;

  Node<Entry_type> *lag_ptr;
  Node<Entry_type> *marker;

  if(p == 1) {
      marker = head;
      head = head->next;
      delete marker;
 
  }
  else {
     lag_ptr = set_position(p-1);
     marker = lag_ptr->next;
     lag_ptr->next = marker->next;
     delete marker;
   
  }
  count--;
  return success;

}      
 
#endif

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


#include "list.h"

#ifndef NODE_H
#define NODE_H

#include<iostream>

template<class Entry_type>
class Node {

public:

  Node();
  Node(const Entry_type &);
  Entry_type entry;
  Node<Entry_type> *next;

};

template<class Entry_type>
Node<Entry_type>::Node() {

  entry = 0;
  next = NULL; // 0x0

}

template<class Entry_type>
Node<Entry_type>::Node(const Entry_type &item) {

  entry = item;
  next = NULL;

}

#endif

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

#include "node.h"
#include <ansiut.h>

void main()
{
   int data;
   int i;
   List<int> the_list;
   the_list.insert(1,1);
   the_list.insert(2,2);
   the_list.insert(3,3);
   the_list.insert(4,4);
   the_list.retrieve(1, data);
   cout << data << endl;
   the_list.remove(1);
   the_list.remove(2);
   the_list.remove(5);
   the_list.insert(2,2);
   the_list.insert(7,7);
   the_list.display();
   
   List<int> new_list(the_list);
   new_list.insert(2,2);
   cout << "New List: ";
   new_list.display();

   cout << "Old List: ";
   the_list.display();
   cout << endl;
   the_list.clear();
   the_list.display();
}

output: ?????????????????

 make
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -gall main.cpp
make: cxx: Command not found
make: *** [main.o] Error 127

0
edelossantos
Asked:
edelossantos
  • 3
3 Solutions
 
jkrCommented:
Instead of

CPP = cxx

in your Makefile, you need to use

CPP = g++
0
 
jkrCommented:
BTW, apart from that, your 'util.h' is missing

using namespace std;

and 'list.h' needs to

#include "node.h"

and not the other way round.
0
 
jkrCommented:
Oh, and 'range_error' is ambiguous, since there's already a class with that name.

Try

#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,invalid_range,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 bottomLine (char * text = " ");  
void hitAnyKey ();                  
void flushInput ();                  
void Warning(char *);                  
void Error(char *);                  
bool promptYesNo(char * prompt="");    
void EatWhiteSpace(void);              

#endif

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


#include "util.h"

#include <iostream>
#include <ctype.h>
#include <cstdlib>
using namespace std;

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 any key 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 NODE_H
#define NODE_H

#include<iostream>

template<class Entry_type>
class Node {

public:

 Node();
 Node(const Entry_type &);
 Entry_type entry;
 Node<Entry_type> *next;

};

template<class Entry_type>
Node<Entry_type>::Node() {

 entry = 0;
 next = NULL; // 0x0

}

template<class Entry_type>
Node<Entry_type>::Node(const Entry_type &item) {

 entry = item;
 next = NULL;

}

#endif

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


#include "util.h"

#ifndef LIST_H
#define LIST_H

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

typedef int Position;

template <class Entry_type>

class List {
public:
 
   List();
  List(const List<Entry_type> & copy);
  ~List();
   void operator = (const List<Entry_type> & copy);
  void clear();
  bool empty() const;
  bool full() const;
  int  size() const;
  void display() const;

  Error_code retrieve(const Position, Entry_type&) const;
  Error_code replace(const Position, const Entry_type&);
   Error_code insert(const Position, const Entry_type&);
   Error_code remove(const Position);

protected:

  int count;
   Node<Entry_type> *head;
  Node<Entry_type> *set_position(int position) const;

};

template<class Entry_type>
Node<Entry_type> *List<Entry_type>::set_position(int position) const {
 
 if(position < 1 || position > count)
   return NULL;

  Node<Entry_type> *marker = head;
  for(int i = 1; i < position; i ++ )
    marker = marker->next;
    return marker;

}

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

}

template<class Entry_type>
List<Entry_type>::~List() {clear();}

template<class Entry_type>
List<Entry_type>::List(const List<Entry_type> &origList) {
 
      count = origList.count;

     if(origList.head == NULL)
       head = NULL;

     else {
       head = new Node<Entry_type>(origList.head->entry);

        Node<Entry_type> *orig = origList.head->next;
       Node<Entry_type> *copy = head;

        while(orig != NULL) {
          copy->next = new Node<Entry_type>(orig->entry);
           orig = orig->next;
          copy = copy->next;
        }
     }
     
}

template<class Entry_type>
void List<Entry_type>::operator=(const List<Entry_type> &copy) {}

template <class Entry_type>
void List<Entry_type>::clear() {
 
  Node<Entry_type> *marker = head;
  Node<Entry_type> *lag_ptr;
   marker = head;

  while(marker != NULL) {
     lag_ptr = marker;
     marker = marker->next;
     delete lag_ptr;
   
   }
   head = NULL;
   count = 0;
}

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

template<class Entry_type>
bool List<Entry_type>::full() const {
 
  Node<Entry_type> *test = new Node<Entry_type>();
   return(test == NULL);

}

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> *marker = head;

  while(marker != NULL) {
     cout << marker->entry << " ";
     marker = marker->next;
  }
  cout << endl;
}

template<class Entry_type>
Error_code List<Entry_type>::retrieve(const Position p,Entry_type &item) const
{
 Node<Entry_type> *marker = set_position(p);
 if (marker == NULL)
     return invalid_range;
 item = marker->entry;
 return success;

}

template<class Entry_type>
Error_code List<Entry_type>::replace(const Position p, const Entry_type & item)
{
 Node<Entry_type> *marker = set_position(p);
 if (marker == NULL)
     return invalid_range;
 marker->entry = item;
 return success;

}


template<class Entry_type>
Error_code List<Entry_type>::insert(const Position p, const Entry_type & item)
{
 
 if(full())
   return overflow;

 if(p < 1 || p > count + 1)
   return invalid_range;

 Node<Entry_type> *marker = head;
 Node<Entry_type> *new_node = new Node<Entry_type>(item);

 if (p == 1)  {
     new_node->next = head;
     head = new_node;
 
 }
 else {
    for(int i = 1; i < p - 1; i++)
       marker = marker->next;

    new_node->next = marker->next;
    marker->next = new_node;
 
   }
  count++;
  return success;

}

template<class Entry_type>
Error_code List<Entry_type>::remove(const Position p) {
 
 if(empty())
   return underflow;

 if(p < 1 || p > count)
   return invalid_range;

 Node<Entry_type> *lag_ptr;
 Node<Entry_type> *marker;

 if(p == 1) {
     marker = head;
     head = head->next;
     delete marker;
 
 }
 else {
    lag_ptr = set_position(p-1);
    marker = lag_ptr->next;
    lag_ptr->next = marker->next;
    delete marker;
 
  }
 count--;
 return success;

}      
 
#endif



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

#include "node.h"
#include <ansiut.h>

void main()
{
  int data;
  int i;
  List<int> the_list;
  the_list.insert(1,1);
  the_list.insert(2,2);
  the_list.insert(3,3);
  the_list.insert(4,4);
  the_list.retrieve(1, data);
  cout << data << endl;
  the_list.remove(1);
  the_list.remove(2);
  the_list.remove(5);
  the_list.insert(2,2);
  the_list.insert(7,7);
  the_list.display();
 
   List<int> new_list(the_list);
  new_list.insert(2,2);
  cout << "New List: ";
   new_list.display();

  cout << "Old List: ";
   the_list.display();
  cout << endl;
  the_list.clear();
  the_list.display();
}

The above compiles.
0

Featured Post

Vote for the Most Valuable Expert

It’s time to recognize experts that go above and beyond with helpful solutions and engagement on site. Choose from the top experts in the Hall of Fame or on the right rail of your favorite topic page. Look for the blue “Nominate” button on their profile to vote.

  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now