书中例子代码是直接用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
添加回答
举报
0/150
提交
取消