4.cpp

《数据结构与程序设计》书本所有源代码！！！！

/* Program extracts from Chapter 4 of
   "Data Structures and Program Design in C++"
   by Robert L. Kruse and Alexander J. Ryba
   Copyright (C) 1999 by Prentice-Hall, Inc.  All rights reserved.
   Extracts from this file may be used in the construction of other programs,
   but this code will not compile or execute as given here. */


// Section 4.1:

int size, *dynamic_array, i;
cout << "Enter an array size: " << flush;
cin >> size;
dynamic_array = new int[size];
for (i = 0; i < size; i++) dynamic_array[i] = i;


class Fraction{
public:
   int numerator;
   int denominator;
};
Fraction *p;


struct Node {
//  data members
   Node_entry entry;
   Node *next;
//  constructors
   Node();
   Node(Node_entry item, Node *add_on = NULL);
};


Node::Node()
{
   next = NULL;
}


Node::Node(Node_entry item, Node *add_on)
{
   entry = item;
   next = add_on;
}


Node first_node('a'); //  Node first_node stores data 'a'.
Node *p0 = &first_node;  //  p0 points to first_Node.
Node *p1 = new Node('b'); //  A second node storing 'b' is created.
p0->next = p1;  //  The second Node is linked after first_node.
Node *p2 = new Node('c', p0);  //  A third Node storing 'c' is created.
    //  The third Node links back to the first node, *p0.
p1->next = p2;  //  The third Node is linked after the second Node.


Node *p0 = new Node('0');
Node *p1 = p0->next = new Node('1');
Node *p2 = p1->next = new Node('2', p1);



// Section 4.2:

class Stack {
public:
   Stack();
   bool empty() const;
   Error_code push(const Stack_entry &item);
   Error_code pop();
   Error_code top(Stack_entry &item) const;
protected:
   Node *top_node;
};


Error_code Stack::push(const Stack_entry &item)
/*
Post: Stack_entry item is added to the top of
      the Stack; returns success or returns a code
      of overflow if dynamic memory is exhausted.
*/
{
   Node *new_top = new Node(item, top_node);
   if (new_top == NULL) return overflow;
   top_node = new_top;
   return success;
}


Error_code Stack::pop()
/*
Post: The top of the Stack is removed.  If the Stack
      is empty the method returns underflow; otherwise it returns success.
*/
{
   Node *old_top = top_node;
   if (top_node == NULL) return underflow;
   top_node = old_top->next;
   delete old_top;
   return success;
}


Error_code Stack::push(Stack_entry item)
{
   Node new_top(item, top_node);
   top_node = new_top;
   return success;
}



// Section 4.3:

for (int i=0; i < 1000000; i++) {
   Stack small;
   small.push(some_data);
}


Stack::~Stack() //  Destructor
/*
Post: The Stack is cleared.
*/
{
   while (!empty())
      pop();
}


Stack outer_stack;
for (int i=0; i < 1000000; i++) {
   Stack inner_stack;
   inner_stack.push(some_data);
   inner_stack = outer_stack;
}


void Stack::operator = (const Stack &original) //  Overload assignment
/*
Post: The Stack is reset as a copy of Stack original.
*/
{
   Node *new_top, *new_copy, *original_node = original.top_node;
   if (original_node == NULL) new_top = NULL;
   else {                         //  Duplicate the linked nodes
      new_copy = new_top = new Node(original_node->entry);
      while (original_node->next != NULL) {
         original_node = original_node->next;
         new_copy->next = new Node(original_node->entry);
         new_copy = new_copy->next;
      }
   }
   while (!empty())               //  Clean out old Stack entries
      pop();
   top_node = new_top;            //  and replace them with new entries.
}


void destroy_the_stack (Stack copy)
{
}

int main()
{
   Stack vital_data;
   destroy_the_stack(vital_data);
}


Stack::Stack(const Stack &original) //  copy constructor
/*
Post: The Stack is initialized as a copy of Stack original.
*/
{
   Node *new_copy, *original_node = original.top_node;
   if (original_node == NULL) top_node = NULL;
   else {                         //  Duplicate the linked nodes.
      top_node = new_copy = new Node(original_node->entry);
      while (original_node->next != NULL) {
         original_node = original_node->next;
         new_copy->next = new Node(original_node->entry);
         new_copy = new_copy->next;
      }
   }
}


class Stack {
public:
//  Standard Stack methods
   Stack();
   bool empty() const;
   Error_code push(const Stack_entry &item);
   Error_code pop();
   Error_code top(Stack_entry &item) const;
//  Safety features for linked structures
   ~Stack();
   Stack(const Stack &original);
   void operator =(const Stack &original);
protected:
   Node *top_node;
};


void Stack::operator = (const Stack &original)
{
   Stack new_copy(original);
   top_node = new_copy.top_node;
}



// Section 4.4:

class Queue {
public:
//  standard Queue methods
   Queue();
   bool empty() const;
   Error_code append(const Queue_entry &item);
   Error_code serve();
   Error_code retrieve(Queue_entry &item) const;
//  safety features for linked structures
   ~Queue();
   Queue(const Queue &original);
   void operator =(const Queue &original);
protected:
   Node *front, *rear;
};


Queue::Queue()
/*
Post: The Queue is initialized to be empty.
*/
{
   front = rear = NULL;
}


Error_code Queue::append(const Queue_entry &item)
/*
Post: Add item to the rear of the Queue and return a code of success
      or return a code of overflow if dynamic memory is exhausted.
*/
{
   Node *new_rear = new Node(item);
   if (new_rear == NULL) return overflow;
   if (rear == NULL) front = rear = new_rear;
   else {
      rear->next = new_rear;
      rear = new_rear;
   }
   return success;
}


Error_code Queue::serve()
/*
Post: The front of the Queue is removed.  If the Queue
      is empty, return an Error_code of underflow.
*/
{
   if (front == NULL) return underflow;
   Node *old_front = front;
   front = old_front->next;
   if (front == NULL) rear = NULL;
   delete old_front;
   return success;
}


class Extended_queue: public Queue {
public:
   bool full() const;
   int size() const;
   void clear();
   Error_code serve_and_retrieve(Queue_entry &item);
};


int Extended_queue::size() const
/*
Post: Return the number of entries in the Extended_queue.
*/
{
   Node *window = front;
   int count = 0;
   while (window != NULL) {
      window = window->next;
      count++;
   }
   return count;
}



// Section 4.5:

int main()
/*
Post: The program has executed simple polynomial arithmetic
      commands entered by the user.
Uses: The classes Stack and Polynomial and the functions
      introduction, instructions, do_command, and get_command.
*/
{
   Stack stored_polynomials;
   introduction();
   instructions();
   while (do_command(get_command(), stored_polynomials));
}


bool do_command(char command, Stack &stored_polynomials)
/*
Pre:  The first parameter specifies a valid calculator command.
Post: The command specified by the first parameter
      has been applied to the Stack of Polynomial
      objects given by the second parameter.
      A result of true is returned unless command == 'q'.
Uses: The classes Stack and Polynomial.
*/
{
   Polynomial p, q, r;
   switch (command) {
   case '?':
      p.read();
      if (stored_polynomials.push(p) == overflow)
         cout << "Warning: Stack full, lost polynomial" << endl;
      break;

   case '=':
      if (stored_polynomials.empty())
         cout << "Stack empty" << endl;
      else {
         stored_polynomials.top(p);
         p.print();
      }
      break;

   case '+':
      if (stored_polynomials.empty())
         cout << "Stack empty" << endl;
      else {
         stored_polynomials.top(p);
         stored_polynomials.pop();
         if (stored_polynomials.empty()) {
            cout << "Stack has just one polynomial" << endl;
            stored_polynomials.push(p);
         }

         else {
            stored_polynomials.top(q);
            stored_polynomials.pop();
            r.equals_sum(q, p);
            if (stored_polynomials.push(r) == overflow)
               cout << "Warning: Stack full, lost polynomial" << endl;
         }
      }
      break;

   //   Add options for further user commands.
    case 'q':
      cout << "Calculation finished." << endl;
      return false;
   }
   return true;
}


class Polynomial {
public:
   void read();
   void print();
   void equals_sum(Polynomial p, Polynomial q);
   void equals_difference(Polynomial p, Polynomial q);
   void equals_product(Polynomial p, Polynomial q);
   Error_code equals_quotient(Polynomial p, Polynomial q);
private:
   double value;
};


void Polynomial::equals_sum(Polynomial p, Polynomial q)
{
   value = p.value + q.value;
}


struct Term {
   int degree;
   double coefficient;
   Term (int exponent = 0, double scalar = 0);
};


Term::Term(int exponent, double scalar)
/*
Post: The Term is initialized with the given coefficient and exponent,
      or with default parameter values of 0.
*/
{
   degree = exponent;
   coefficient = scalar;
}


class Polynomial: private Extended_queue {  //  Use private inheritance.
public:
   void read();
   void print() const;
   void equals_sum(Polynomial p, Polynomial q);
   void equals_difference(Polynomial p, Polynomial q);
   void equals_product(Polynomial p, Polynomial q);
   Error_code equals_quotient(Polynomial p, Polynomial q);
   int degree() const;
private:
   void mult_term(Polynomial p, Term t);
};


void Polynomial::print() const
/*
Post: The Polynomial is printed to cout.
*/
{
   Node *print_node = front;
   bool first_term = true;

   while (print_node != NULL) {
      Term &print_term = print_node->entry;
      if (first_term) {  //  In this case, suppress printing an initial '+'.
         first_term = false;
         if (print_term.coefficient < 0) cout << "- ";
      }
      else if (print_term.coefficient < 0) cout << " - ";
      else cout << " + ";
      double r = (print_term.coefficient >= 0)
                 ? print_term.coefficient : -(print_term.coefficient);
      if (r != 1) cout << r;
      if (print_term.degree > 1) cout << " X^" << print_term.degree;
      if (print_term.degree == 1) cout << " X";
      if (r == 1 && print_term.degree == 0) cout << " 1";
      print_node = print_node->next;
   }
   if (first_term)
      cout << "0";  //  Print 0 for an empty Polynomial.
   cout << endl;
}


void Polynomial::read()
/*
Post: The Polynomial is read from cin.
*/
{
   clear();
   double coefficient;
   int last_exponent, exponent;
   bool first_term = true;

   cout << "Enter the coefficients and exponents for the polynomial, "
        << "one pair per line.  Exponents must be in descending order." << endl
        << "Enter a coefficient of 0 or an exponent of 0 to terminate." << endl;

   do {
      cout << "coefficient? " << flush;
      cin  >> coefficient;
      if (coefficient != 0.0) {
         cout << "exponent? " << flush;
         cin  >> exponent;
         if ((!first_term && exponent >= last_exponent) || exponent < 0) {
            exponent = 0;

            cout << "Bad exponent: Polynomial terminates without its last term."
                 << endl;
         }
         else {
            Term new_term(exponent, coefficient);
            append(new_term);
            first_term = false;
         }
         last_exponent = exponent;
      }
   } while (coefficient != 0.0 && exponent != 0);
}


void Polynomial::equals_sum(Polynomial p, Polynomial q)
/*
Post: The Polynomial object is reset as the sum of the two parameters.
*/
{
   clear();
   while (!p.empty() || !q.empty()) {
      Term p_term, q_term;
      if (p.degree() > q.degree()) {
         p.serve_and_retrieve(p_term);
         append(p_term);
      }
      else if (q.degree() > p.degree()) {
         q.serve_and_retrieve(q_term);
         append(q_term);
      }
      else {
         p.serve_and_retrieve(p_term);
         q.serve_and_retrieve(q_term);
         if (p_term.coefficient + q_term.coefficient != 0) {
            Term answer_term(p_term.degree,
                             p_term.coefficient + q_term.coefficient);
            append(answer_term);
         }
      }
   }
}


int Polynomial::degree() const
/*
Post: If the Polynomial is identically 0, a result of -1 is returned.
      Otherwise the degree of the Polynomial is returned.
*/
{
   if (empty()) return -1;
   Term lead;
   retrieve(lead);
   return lead.degree;
}

/*************************************************************************/