edelossantos
asked on
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,ra nge_error, underflow, overflow,f atal,
not_present,duplicate_erro r,entry_in serted,ent ry_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_pos ition(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(con st List<Entry_type> &origList) {
count = origList.count;
if(origList.head == NULL)
head = NULL;
else {
head = new Node<Entry_type>(origList. head->entr y);
Node<Entry_type> *orig = origList.head->next;
Node<Entry_type> *copy = head;
while(orig != NULL) {
copy->next = new Node<Entry_type>(orig->ent ry);
orig = orig->next;
copy = copy->next;
}
}
}
template<class Entry_type>
void List<Entry_type>::operator =(const List<Entry_type> ©) {}
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(c onst 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(c onst 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(con st 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
# 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,ra
not_present,duplicate_erro
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_pos
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(con
count = origList.count;
if(origList.head == NULL)
head = NULL;
else {
head = new Node<Entry_type>(origList.
Node<Entry_type> *orig = origList.head->next;
Node<Entry_type> *copy = head;
while(orig != NULL) {
copy->next = new Node<Entry_type>(orig->ent
orig = orig->next;
copy = copy->next;
}
}
}
template<class Entry_type>
void List<Entry_type>::operator
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(
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
{
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(
{
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(c
{
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(c
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(con
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
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.