猿问

数据结构的一个问题：用链表实现大整数的加减乘除运算

书中例子代码是直接用STL的list的，我自己写了一个带头结点的双向循环链表DouList,已经能实现大整数的加法了。现在就是搞不清乘法和除法的算法怎么写。

大家麻烦看一下我写的这几个类，然后帮忙写一下大整数乘法，除法的代码。或者可以提供点思路，3Q啊

//DouListNode.h 结点类

template<class T>
class DouListNode
{
  T data;
  DouListNode<T>* link, * prior;
  public: 
	DouListNode():link(NULL),prior(NULL){};
	DouListNode(T value):link(NULL),prior(NULL),data(value){}

	~DouListNode(){};
	void SetLink(DouListNode<T>* next);
	void SetPrior(DouListNode<T>* pre);
	DouListNode<T>* GetLink();
	DouListNode<T>* GetPrior();
	T & GetData();



};
template<class T>
void DouListNode<T>::SetLink(DouListNode<T>* next)
{
  link=next;
}

template<class T>
void DouListNode<T>::SetPrior(DouListNode<T>* pre)
{
  prior=pre;
}

template<class T>
DouListNode<T>* DouListNode<T>::GetLink()
{
  return link;//unhandled exception in XXXXX.exe  Access violation
}

template<class T>
DouListNode<T>* DouListNode<T>::GetPrior()
{
  return prior;
}

template<class T>
T& DouListNode<T>::GetData()
{
  return data;
}


///////////////////////////////////////
//DouList.h 双向循环链表类

#include "DouListNode.h"

template<class T>
class DouList
{
  DouListNode<T>* head,*tail,*cur;
  public:
  
	DouList();
	~DouList(){};
	bool AddTail(T value);
	bool AddHead(T value);
	void RemoveThis(bool direction);
	void RemoveAll();
	void SetBegin();
	int GetCount();
	void TowardCur();
	void BackCur();
	DouListNode<T>* GetCur();
	DouListNode<T>* GetHead();
	DouListNode<T>* GetTail();
	
	void InsertAfter(T value);
	bool IsEmpty();
	T GetNext();
	T GetPrior();

};
template<class T>
DouList<T>::DouList()
{
  head=tail=new DouListNode<T>;
  cur=NULL;
  head->SetLink(head);
  head->SetPrior(tail);
}

template<class T>
bool DouList<T>::AddTail(T value)
{
  DouListNode<T>* add=new DouListNode<T>(value);
  tail->SetLink(add);
  add->SetPrior(tail);
  tail=tail->GetLink();
  tail->SetLink(head);
  head->SetPrior(add);
  if (tail != NULL)
  {
	return true;
  }
  else
  {
	return false;
  }
}



template<class T>
bool DouList<T>::AddHead(T value)
{
  DouListNode<T>* add=new DouListNode<T>(value);
  add->SetPrior(head);
  add->SetLink(head->GetLink());
  (head->GetLink())->SetPrior(add);
  head->SetLink(add);
  if (tail == head)
  {
	tail=head->GetLink();
  }
  if (add != NULL)
  {
	return true;
  }
  else
  {
	return false;
  }
}

template<class T>
void DouList<T>::RemoveThis(bool direction)
{
  if (cur == head)
  {
	if (direction ==0 )
	{
	  cur =cur->GetLink();
	}
	if (direction ==1 )
	{
	  cur=cur->GetPrior();
	}
  }

  DouListNode<T>* preCur=NULL;
  DouListNode<T>* nextCur=NULL;
  preCur=cur->GetPrior();
  nextCur=cur->GetLink();
  preCur->SetLink(nextCur);
  nextCur->SetPrior(preCur);

  if (direction==0)
  {
	cur=nextCur;
  }

  if (direction == 1)
  {
	cur =preCur;
  }
}

template<class T>
void DouList<T>::RemoveAll()
{
  SetBegin();
  int length=GetCount();
  for(int i=0;i<length;i++)
  {
	RemoveThis(0);
  }
  cur=head;
}


template<class T>
void DouList<T>::SetBegin()
{
  cur=head;
}

template<class T>
int DouList<T>::GetCount()
{
  int num=0;
  cur=head;//增加这个初始化

  DouListNode<T>* here=cur;
  while (cur->GetLink() != here )
  {
	cur=cur->GetLink();
	num++;
  }

  cur=cur->GetLink();
  return num;
}

template<class T>
void DouList<T>::TowardCur()
{
  cur=cur->GetLink();
}

template<class T>
void DouList<T>::BackCur()
{
  cur=cur->GetPrior();
}

template<class T>
DouListNode<T>* DouList<T>::GetCur()
{
  return cur;
}

template<class T>
DouListNode<T>* DouList<T>::GetHead()
{
  return head;
}

template<class T>
DouListNode<T>* DouList<T>::GetTail()
{
  return tail;
}

template<class T>
bool DouList<T>::IsEmpty()
{
  return head->GetLink()== head;
}

template<class T>
void DouList<T>::InsertAfter(T value)
{
  DouListNode<T>* add=new DouListNode<T>(value);
  DouListNode<T>* nextCur=cur->GetLink();

  cur->SetLink(add);
  add->SetLink(nextCur);
  nextCur->SetPrior(add);
  add->SetPrior(cur);
  if (cur == tail)
  {
	tail=cur->GetLink();
  }
}


template<class T>
T DouList<T>::GetNext()
{
  if (cur==head)
  {
	cur=cur->GetLink();
  }
  T num=cur->GetData();
  cur=cur->GetLink();
  
  return num;
}

template<class T>
T DouList<T>::GetPrior()
{
  if (cur==head)
  {
	cur=cur->GetPrior();
  }
  T num=cur->GetData();
  cur=cur->GetPrior();
  
  return num;
}

//////////////////////////////
//BigInt.h 大整数类


#include <iostream>
#include <iomanip>       // setfill(), setw()
#include <list>
#include "DouList.h"

#ifndef BIGINT
#define BIGINT

const int DIGITS_PER_BLOCK = 3;
class BigInt
{
 public:
 
  void read(istream & in);
  

 
  void display(ostream & out) ;
  

  
  BigInt operator+(BigInt addend2);

  BigInt operator-(BigInt addend2);

  BigInt operator*(BigInt addend2);

  BigInt operator/(BigInt addend2);

  BigInt operator^(BigInt addend2);

 private:
  
   DouList<short int> myList;

}; 

inline istream & operator>>(istream & in, BigInt & number)
{
  number.read(in);
  return in;
}

inline ostream & operator<<(ostream & out,  BigInt & number)
{
  number.display(out);
  return out;
}

#endif


////////////////////////////////////////
//BigInt.cpp 

#include <iostream>
#include <CMATH>
using namespace std;

#include "BigInt.h"

//--- Definition of read()
void BigInt::read(istream & in)
{
  static bool instruct = true;
  if (instruct)
  {
     cout << "Enter " << DIGITS_PER_BLOCK << "-digit blocks, separated by "
            "spaces.\nEnter a negative integer in last block to signal "
            "the end of input.\n\n";
    instruct = false;
  }
  short int block;
  const short int MAX_BLOCK = (short) pow(10.0, DIGITS_PER_BLOCK) - 1;
  for (;;)
  {
    in >> block;
    if (block < 0) return;

    if (block > MAX_BLOCK)
      cerr << "Illegal block -- " << block << " -- ignoring\n";
    else
     
	 myList.AddTail(block);
  }
}


//--- Definition of display()
void BigInt::display(ostream & out) 
{ 
   int blockCount = 0;
   const int BLOCKS_PER_LINE = 20;   // number of blocks to display per line
  

   //myList.SetBegin();
   DouListNode<short int>* pt=myList.GetHead();
	pt=pt->GetLink();

   for (int i=0;i<myList.GetCount() -1 ;i++)
   {
	 out << setfill('0'); 
	 if (blockCount == 0)
	   out << setfill(' '); 
	 
	 //if (myList.GetCur() != myList.GetTail() )
	   
	 out << setw(3) << pt->GetData();
	 blockCount++ ;


	 pt=pt->GetLink();

	 out << ',';
	 if (blockCount > 0 && blockCount % BLOCKS_PER_LINE == 0)
            out << endl;
   }
	out << setfill('0');
	out << setw(3) << pt->GetData();//最后一个数字块后不输出逗号,
	
   
}


//--- Definition of operator+()
BigInt BigInt::operator+(BigInt addend2)
{
   BigInt sum;
   short int first,                  // a block of 1st addend (this object)
             second,                 // a block of 2nd addend (addend2)
             result,                 // a block in their sum
             carry = 0;              // 两个数字块相加后的进位

   DouListNode<short int>* pt1=myList.GetTail(),  //pt1指向当前myList的链尾结点
	 *pt2=addend2.myList.GetTail(); //pt2指向addend2的myList的链尾结点

   while ( pt1 != myList.GetHead() || pt2 != addend2.myList.GetHead())
   {
	 if (pt1 != myList.GetHead())
	 {
	   first=pt1->GetData();
	   pt1=pt1->GetPrior();  //pt1从链尾向链首移动
	 }
	 else
	  first=0;


	 if (pt2 != addend2.myList.GetHead())
	 {
	   second=pt2->GetData();
	   pt2=pt2->GetPrior();
	 }
	 else
	   second=0;

	 short int temp = first + second + carry;
	 result = temp % 1000;
	 carry = temp / 1000;
      sum.myList.AddHead(result);
   }

   if (carry > 0)
      sum.myList.AddHead(carry);



   return sum;
}

大家帮忙写一下减法，乘法，除法等的算法吧，3Q3Q


仰望星空683
浏览 5131回答 1
1回答

write

表示代码太长，，，不过用c语言的数组。。很好实现
0
随时随地看视频慕课网APP

相关问题

centos7里没有locate命令，请问在哪里有centos6.5的镜像文件？ 2 回答

相关分类

iOS
Linux
linux 2 回答
centos7里没有locate命令，请问在哪里有centos6.5的镜像文件？ 2 回答
Java
我要回答