• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 373
  • 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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

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