list.txt

Program to implement a list data structure in C++ (partial) With debug output for poor-man s anima

***************************************************************/
/* Program to implement a list data structure in C++ (partial) */
/* With debug output for poor-man's animation                  */
/* and improved print_list method                               */
/* Based on "The practice of programming," pp. 44 ff.          */
/* Author: Jesus A. Izaguirre                                  */
/* Date: Feb. 8, 2005                                          */
/***************************************************************/

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstdlib>
#include "list.h"

using namespace std;

const int DEBUG = 0;
const int MAX_NUM = 5;

Node *add_node(T value) {
  Node *newnode = NULL;
  if (DEBUG) {   
    cout << "Created a blank node and set next to NULL" << endl;
  }
  try {
   newnode = new Node; 
  }
  catch (...) {
    cerr << "memory allocation failed!\n";
  }
  newnode->my_value = value;
  newnode->next = NULL;
  if (DEBUG) {
    cout << "Created node: |" << value << ", NULL|" << endl;
  }
  return newnode;
}

void print(Node* ptr) {
  if (DEBUG) {
    cout << "|" << ptr->my_value;
    if (ptr->next != NULL) cout << ", ->" << ptr->next->my_value << "| ";
    else cout << ", NULL|";
  }
  else {
    cout << left << setw(MAX_NUM) << ptr->my_value << " ";
  }
}


Node *add_front(Node* listhead, Node* newnode) {
  if (DEBUG) {
    cout << "Set ";
    print(newnode);
    cout << " to ";
  }
  newnode->next = listhead;
  if (DEBUG) {
    print(newnode);
    cout << endl;
  }
  return newnode;
}

Node *add_end(Node* listhead, Node* newnode) {
  Node* result = newnode;
  Node * ptr = NULL;
  if (listhead != NULL) {
    if (DEBUG) 
      cout << "ITERATING THROUGH LIST" << endl;
    for (ptr = listhead; ptr->next != NULL; ptr = ptr->next)
      if (DEBUG) {
	cout << "Setting ptr to ";
	print(ptr);
	cout << endl;
      }
    if (DEBUG) {
      cout << "DONE ITERATING." << endl;
      cout << "Setting ";
      print(ptr);
      cout << " to ";
    }
    ptr->next=newnode;
    if (DEBUG) {
      print(ptr);
      cout << endl;
    }
    result = listhead;
  }
  return result;
}

Node *find(Node* listhead, const T value) {
  Node* result = NULL;
  for ( ; listhead != NULL; listhead = listhead-> next)
    if (listhead->my_value == value) {
      result = listhead;
      break;
    }
  return result;
}

void map(Node* listhead, void (*fn)(Node*)) {
  for (; listhead != NULL; listhead = listhead->next) 
    (*fn)(listhead);
}

void print_list(Node* ptr){
  map(ptr, print);
  cout << endl;
  if (DEBUG)
    cout << "H" << endl;
}

/* Implement the following functions to: */ 
/* delete all elements in the list */
void del_all(Node* listhead) {
  assert(listhead != NULL);
  Node* ptr = NULL;
  if (DEBUG) 
    cout << "ITERATING THROUGH LIST" << endl;
  for (; listhead != NULL; listhead = ptr) {
    if (DEBUG) {
      cout << "Setting ptr to ";
      print(listhead);
      cout << endl;
    }
    ptr = listhead-> next;
    delete listhead;
  }
}

/* delete item in the list */
Node* del_item(Node* listhead, const T value) {
  /* Students: add debug/trace information as in the other routines */
  assert(listhead != NULL);
  Node *ptr = NULL;
  Node *prev = NULL;
  for (ptr = listhead; ptr != NULL; ptr = ptr->next) {
    if (value == ptr->my_value) {
      if (DEBUG) 
	cout << "found " << value << endl;
      if (prev==NULL)
	listhead = ptr->next;
      else
	prev->next = ptr->next;
      delete ptr;
      return listhead;
    }
    prev = ptr;
  }
  return NULL;
} 

T find_min(Node* listhead) {
  assert(listhead != NULL);
  T result = listhead->my_value;
  for (listhead=listhead->next; listhead!=NULL; listhead=listhead->next) 
    if (listhead->my_value < result)
      result = listhead->my_value;
  return result;
}

T find_mean(Node* listhead) {
  assert(listhead != NULL);
  T result = listhead->my_value;
  T count = 1;
  for (listhead=listhead->next; listhead!=NULL; listhead=listhead->next) {
    result += listhead->my_value;
    count++;
  }
  if (DEBUG) 
    cout << "count = " << count << ", sum= " << result << endl;
  result /= count;
  return result;
}