#include #include #include

using namespace std;

class node { public: typedef int data_t;

node *next; data_t data;

node(data_t d) { next = NULL; data = d; } };

class linked_list { private: node *head;

public:

linked_list() { head = NULL; } int size() { node *tptr = head; int c = 0;

while (tptr) { c++; tptr = tptr->next; }

return c; }

void add(int n, node::data_t d) { node *tptr = head, *prev = head, *curr; int c = 1; if (n < 1) return; if (n == 1) { add_first(d); return; } if (size() == n - 1) { add_last(d); return; } while (tptr) { if (c == n) { curr = new node(d); prev->next = curr; curr->next = tptr; break; } c++; prev = tptr; tptr = tptr->next; } }

void add_last(node::data_t d) { node *tptr = head;

if (!head) { head = new node(d); return; } while (tptr->next) { tptr = tptr->next; }

tptr->next = new node(d); }

void add_first(node::data_t d) { node *newptr = new node(d); newptr->next = head; head = newptr; }

node::data_t get(int n) { node *tptr = head; int c = 1; if (n == 1) return get_first(); if (n == size()) return get_last(); while (tptr) { if (n == c) return tptr->data;

tptr = tptr->next; c++; } return -1; }

node::data_t get_first() { if (!head) return -1; return head->data; }

node::data_t get_last() { node *tptr = head; if (!head) return -1; while (tptr) { if (tptr->next == NULL) return tptr->data;

tptr = tptr->next; } }

void remove(int n) { node *tptr = head, *prev = head; int c = 1; if (n == 1) { remove_first(); return; } if (n == size()) { remove_last(); return; } while (tptr) { if (c == n) { prev->next = tptr->next; return; } c++; prev = tptr; tptr = tptr->next; } }

void remove_first() { if (!head) return; head = head->next; }

void remove_last() { node *tptr = head, *prev = head; if (!head) return; while (tptr->next != NULL) { prev = tptr; tptr = tptr->next; } prev->next = NULL; }

void dump() { node *tptr;

cout << " DUMP: (size = " << size() << ", first = " << get_first() << ", last = " << get_last() << ") ";

if (head == NULL) { cout << " DUMP: head = NULL "; return; }

tptr = head;

while (tptr) { cout << " DUMP: data = : " << tptr->data << endl; tptr = tptr->next; } cout << endl; }

};

int main(void) { linked_list ll; string cmd; int i, d;

while (cin >> cmd >> i >> d) { cout << "MAIN: cmd = " << cmd << ", i = " << i << ", d = " << d << endl;

if (cmd == "add") ll.add(i, d); else if (cmd == "addf") ll.add_first(d); else if (cmd == "addl") ll.add_last(d); else if (cmd == "rem") ll.remove(i); else if (cmd == "remf") ll.remove_first(); else if (cmd == "reml") ll.remove_last(); else if (cmd == "get") { d = ll.get(i); cout << "get returns: " << d << endl; } else if (cmd == "getf") { d = ll.get_first(); cout << "getf returns: " << d << endl;

} else if (cmd == "getl") { d = ll.get_last(); cout << "getl returns: " << d << endl; } else if (cmd == "dump") ll.dump(); else if (cmd == "quit") exit(0); }

Modify the program to allow it to use a C++ template to support a linked list, where the data can be any data type. To make this work, the "main" test driver program will need to be modified. Let's just say that we're going to make a linked list of "double"s. To do this, the test program will need to be tweaked as follows: Note that the first step is to remove the typedef from the node class!

============================================================

int main(void) { linked_list ll; string cmd; double d; int i;

while (cin >> cmd >> i >> d) {

cout << "MAIN: cmd = " << cmd << ", i = " << i << ", d = " << d << endl;

if (cmd == "add") ll.add(i, d); else if (cmd == "addf") ll.add_first(d); else if (cmd == "addl") ll.add_last(d); else if (cmd == "rem") ll.remove(i); else if (cmd == "remf") ll.remove_first(); else if (cmd == "reml")

ll.remove_last(); else if (cmd == "get") { d = ll.get(i); cout << "get returns: " << d << endl; } else if (cmd == "getf") { d = ll.get_first(); cout << "getf returns: " << d << endl; } else if (cmd == "getl") { d = ll.get_last(); cout << "getl returns: " << d << endl; } else if (cmd == "dump") ll.dump(); else if (cmd == "quit") exit(0); } }

============================================================

##############################################################

Part II Implement a stack class that sits on top of your singly linked list class (the new, template version). Use the driver program provided below to test your code. NOTE: Just start with your latest/greatest linked_list class, (with templates) add this main to it, and then add a new "stack" class to the one file. Note that the main program doesn't delcare a linked_list object - instead, it declares an object of type "stack"! Put your program in ~/PF3/lab3/lab3.cpp

==============================================================

int main(void) { stack s; int n; string cmd; double d;

while (cin >> cmd >> d) {

cout << "MAIN: cmd = " << cmd << ", d = " << d << endl;

if (cmd == "push") s.push(d); else if (cmd == "pop") { d = s.pop(); cout << "MAIN: pop = " << d << endl; } else if (cmd == "quit") exit(0); } }