wex9_22.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#include <stdlib.h>
#pragma hdrstop

#include "node.h"

template <class T>
class Stack
{
	private:
		// pointer to top of the stack
		Node<T> *top;
		// used by assginment operator and copy constructor
		void CopyStack(const Stack<T>& s);
	public:
		// constructor and copy constructor
		Stack(void);
		Stack(const Stack<T>& s);
		
		// destructor
		~Stack(void);
		
		// assignment operator
		Stack<T>& operator= (const Stack<T>& s);
		
		// stack operations
		void Push(const T& elt);
		T Pop(void);
		T Peek(void) const;
		int StackEmpty(void) const;
		void ClearStack(void);
};

// copy Stack object s to the current object
template <class T>
void Stack<T>::CopyStack(const Stack<T>& s)
{
	// p points to first node in s, q traverses current
	// object's linked list
	Node<T> *p = s.top, *q , *newnode;

	// set top to NULL, since we are constructing a
	// new stack
	top = NULL;
	// if stack s is not empty, create first node on stack
	// and assign top. move p to the second node of stack s
	if (p != NULL)
	{
		top = new Node<T> (p->data);
		p = p->NextNode();
	}
	// insert the remaining elements of s at the end of
	// the linked list
	q = top;
	while (p != NULL)
	{
		newnode = new Node<T> (p->data,NULL);
		q->InsertAfter(newnode);
		q = newnode;
		p = p->NextNode();
	}
}

// constructor. initialize top to NULL
template <class T>
Stack<T>::Stack(void): top(NULL)
{}

// copy constructor. use CopyStack to copy stack
// s to the current object
template <class T>
Stack<T>::Stack(const Stack<T>& s)
{
	CopyStack(s);
}

// destructor. use ClearStack to delete the linked list
template <class T>
Stack<T>::~Stack(void)
{
	ClearStack();
}

// assignment operator. clear the current stack and
// copy stack s into the object
template <class T>
Stack<T>& Stack<T>::operator= (const Stack<T>& s)
{
	if (this == &s)		// Can't assign list onto itself
		return *this;

	ClearStack();
	CopyStack(s);
	return *this;
}

// push the stack by inserting a node at the front of the
// linked list
template <class T>
void Stack<T>::Push(const T& elt)
{
	Node<T> *newnode;
	
	newnode = new Node<T> (elt,top);
	top = newnode;
}

// pop the stack by deleting the node at the front of the list
template <class T>
T Stack<T>::Pop(void)
{
	Node<T> *p;
	T datavalue;
	
	if (top == NULL)
	{
		cerr << "Attempting to Pop an empty stack!" << endl;
		exit(1);
	}
	
	// record p and its data value
	p = top;
	datavalue = p->data;

	// move top to the next node
	top = top->NextNode();
	
	// delete former top of stack and return its value
	delete p;
	return datavalue;
}

// return the data value in node at the front of the list
template <class T>
T Stack<T>::Peek(void) const
{
	if (top == NULL)
	{
		cerr << "Peek with an empty stack!" << endl;
		exit(1);
	}
	return top->data;
}

// the stack is empty of top is NULL
template <class T>
int Stack<T>::StackEmpty(void) const
{
	return top == NULL;
}

// delete all the node in the linked list
template <class T>
void Stack<T>::ClearStack(void)
{
	Node<T> *p, *q;

	// cycle through the list
	p = top;
	while(p != NULL)
	{
		q = p;				// q tags node to be deleted
		p = p->NextNode();	// move p forward to the next node
		delete q;			// delete the node
	}
	top = NULL;
}

// ***** use Program 5.2 to test the Stack class *****

// print integer num in base B
void MultibaseOutput(long num, int B)
{
    // stack holds base B digits left to right
    Stack<int> S;
    
    // extract base B digits right to left and push on stack S
    do
    {
        S.Push(int(num % B));	// convert to int and push on stack
        num /= B;				// remove right most digit
    } while (num != 0);			// continue until all digits computed
    
    while (!S.StackEmpty())		// flush the stack
        cout << S.Pop();
}

void main(void)
{
    long num;					// decimal number
    int  B;						// base
    
    // read 3 positive numbers and the desired base 2 <= B <= 9
    for(int i=0;i < 3;i++)
    {
        cout << "Enter non-negative decimal number and base "
             << "(2<=B<=9): ";
        cin >> num >> B;
        cout << num << " base " << B << " is ";
        MultibaseOutput(num, B);
        cout << endl;
    }
}

/*

<Run>

Enter non-negative decimal number and base (2<=B<=9): 72 4
72 base 4 is 1020
Enter non-negative decimal number and base (2<=B<=9): 53 2
53 base 2 is 110101
Enter non-negative decimal number and base (2<=B<=9): 3553 8 
3553 base 8 is 6741
*/