chain.h

使用链表实现大数的阶乘运算

// file chain.h


#ifndef Chain_
#define Chain_


#include <iostream>
#include "cnode.h"
//#include "xcept.h"
using namespace std;
static int t=1000;
template<class T>
class Chain {
   public:
      Chain() {first = 0;}
      ~Chain();
      bool IsEmpty() const {return first == 0;}
      int Length() const; 
      bool Find(int k, T& x) const; 
      int Search(const T& x) const; 
      Chain<T>& Delete(int k, T& x); 
      Chain<T>& Insert(int k, const T& x);
      void Output(ostream& out);
	  void Factorial(int& n);
	  ChainNode<T> * reverse(ChainNode<T> * head);
   private:
      ChainNode<T> *first;  // pointer to first node
};

template<class T>
Chain<T>::~Chain()
{// Chain destructor. Delete all nodes in chain.
   ChainNode<T> *next;  // next node
   while (first) {
      next = first->link;
      delete first;
      first = next;
      }
}

template<class T>
int Chain<T>::Length() const
{// Return the number of elements in the chain.
   ChainNode<T> *current = first;
   int len = 0;
   while (current) {
     len++;
     current = current->link;
     }
   return len;
}

template<class T>
bool Chain<T>::Find(int k, T& x) const
{// Set x to the k'th element in the chain.
 // Return false if no k'th; return true otherwise.
   if (k < 1) return false;
   ChainNode<T> *current = first;
   int index = 1;  // index of current
   while (index < k && current) {
      current = current->link;
      index++;
      }
   if (current) {x = current->data;
                 return true;}
   return false; // no k'th element
}

template<class T>
int Chain<T>::Search(const T& x) const
{// Locate x.  Return position of x if found.
 // Return 0 if x not in the chain.
   ChainNode<T> *current = first;
   int index = 1;  // index of current
   while (current && current->data != x) {
      current = current->link;
      index++;
      }
   if (current) return index;
   return 0;
}

template<class T>
Chain<T>& Chain<T>::Delete(int k, T& x)
{// Set x to the k'th element and delete it.
 // Throw OutOfBounds exception if no k'th element.
   if (k < 1 || !first)
      throw OutOfBounds(); // no k'th
   
   // p will eventually point to k'th node
   ChainNode<T> *p = first;

   // move p to k'th & remove from chain
   if (k == 1) // p already at k'th
      first = first->link; // remove
   else { // use q to get to k-1'st
      ChainNode<T> *q = first;
      for (int index = 1; index < k - 1 && q;
                          index++)
         q = q->link;
      if (!q || !q->link)
         throw OutOfBounds(); // no k'th
      p = q->link; // k'th
      q->link = p->link;} // remove from chain

   // save k'th element and free node p
   x = p->data;
   delete p;
   return *this;
}

template<class T>
Chain<T>& Chain<T>::Insert(int k, const T& x)
{// Insert x after the k'th element.
 // Throw OutOfBounds exception if no k'th element.
 // Pass NoMem exception if inadequate space.
//   if (k < 0) throw OutOfBounds();

   // p will eventually point to k'th node
   ChainNode<T> *p = first;
   for (int index = 1; index < k && p;
                       index++)  // move p to k'th
      p = p->link;
//   if (k > 0 && !p) throw OutOfBounds(); // no k'th

   // insert
   ChainNode<T> *y = new ChainNode<T>;
   y->data = x;
   if (k) {// insert after p
           y->link = p->link;
           p->link = y;}
   else {// insert as first element
         y->link = first;
         first = y;}
   return *this;
}
template<class T>
ChainNode<T> *Chain<T>::reverse(ChainNode<T> * head)
{
if(head==NULL)
   return head;
ChainNode<T> * p=head->link;
head->link=NULL;
while(p!=NULL)
{
   ChainNode<T> * temp=p->link;
   p->link=head;
   head=p;
   p=temp;
}
return head;
}
template<class T>
void Chain<T>::Output(ostream& out) 
{// Insert the chain elements into the stream out.
	/*ChainNode<T> *d=first;
	ChainNode<T> *q=d;ChainNode<T> * k;ChainNode<T> *u=first;
	int f=Length();int a=1;int h=f;
	while(a<=a/f)
	{for(int index=a;index<=h&&h>f/2+1;index++)
			q=q->link;
	        if(a==1){
				k=q->link;
	            q->link=first;
			    first=k;
			    d=d->link;}
			else{
	        k=q->link;
	        q->link=u;
			u=k;
			d=d->link;}
		    a++;h--;
	}	    */
	first=reverse(first);
   ChainNode<T> *current;
   for (current = first; current;current = current->link)
   {                  
		if(current->data<10)
        out << "00" << current->data<<",";
        if(current->data<100&&current->data>=10)
        out << "0" << current->data<<",";
		if(current->data<1000&&current->data>=100)
        out << current->data<<",";
   }
}

// overload <<
template <class T>
ostream& operator<<(ostream& out,  Chain<T>& x)
   {   
	   x.Output(out); return out;}

template<class T>
void Chain<T>::Factorial(int& n)
{
	if(n<0)
		cout<<"-1"<<endl;
	if(n==0||n==1)
		cout<<"1"<<endl;
	if(n>1)
	{
		Insert(0,n);
		
		for(int i=n-1;i>0;i--)
		{
			ChainNode<int> *pt1=first;
			ChainNode<int> *pt2=first;
			//ChainNode<int> *pt3=first;
			while(pt1){
				pt1->data=pt1->data*i;
				pt1=pt1->link;}
			//while(pt3){
			while(pt2){  
			   int j=0;
			   j=pt2->data/t;
			   pt2->data=pt2->data%t;
			   if(pt2->link&&j)
			   pt2->link->data=pt2->link->data+j;
			   if(!(pt2->link)&&j){
				   int len=Length();
				   Insert(len,j);}
			   pt2=pt2->link;}//;//pt3=pt3->link;}
		}
		
		cout<<*this<<endl;
	}
}
#endif