c++实现任意长整数的四则运算.doc

实验题目：设计一数据结构可处理任意长度的整数

概要设计
1.数据结构的定义
采用双向链表存储任意长整数。双向链表的定义如下：
class DblList {
private:
DblNode *head, *tail;
DblNode *current;
int sign;
public:
DblList(); //构造函数
~DblList(); //析构函数
bool CreatList(string); //生成一个双向链表，存储整数
int GetCount(); //获取整数的长度
void Insert(DblNode *); //从表尾插入一个结点
void InsertFront(DblNode *); //从表头插入
void Clear(); //去除该链表
void operator+(DblList &); //实现两个任意整数的加法
void operator*(DblList &); //实现两个任意整数的乘法
DblList & operator=(DblList &); //重载赋值运算符
int Compare(DblList &); //两个整数的绝对值比拟
void Display(); //任意长度整数的标准化输出
};
说明:数据的存储，无外乎顺序或者链表。顺序存储时，定义数组无法实现任意长度，而且需要预设一个maxsize，不是特别的方便。所以采用链式存储方式。而且任意长数据通过字符串输入。在链表的每一个结点中，数据域是在该数位上的数字大小。

2． 主要功能模块的功能
u 任意长整数的输入
u 任意长整数的标准化输出
u 两个整数的加法
u 两个整数的乘法

三．详细设计〔主模块流程图〕

五、 使用说明与测试结果
1.使用说明：
点击打开应用程序pro1.exe。依次输入任意两个整数〔例如123456，+1234567〕，按回车，会出现菜单，如下列图：

按‘1’那么实现两整数的加法
按‘2’那么实现两整数的乘法
按‘#’完毕
注：菜单可重复出现直至‘#’退出。
实现加法，乘法如下列图：

2.测试结果：
(1) 123456
(2) +1234567
(3) -987654321
(4) 12a3
(5) +
注：当输入错误时，允许重新输入。

六、 源程序
/* 主函数 */
/***************************************************/
#include "cal.h"

void main(){
string s;
string p;
DblList list1;
while(1){ //输入错误时，允许重新输入
cout<<"Input num1"<<endl;
cin>>s;
bool ok1=list1.CreatList(s);
if (!ok1)
{
cout<<"error!"<<endl;
}
else{
cout<<"num1:";
list1.Display();
break;
}
}
DblList list2;
while(1){
cout<<"Input num2:"<<endl;
cin>>p;
bool ok2=list2.CreatList(p);
if (!ok2)
{
cout<<"error!"<<endl;
}
else{
cout<<"num2:";
list2.Display();
break;
}
}
string choose;
while (1)
{
cout<<"请选择运算法："<<endl;
cout<<"--------------------------"<<endl; /*菜单*/
cout<<"|1.num1+num2 |"<<endl; /*可以重复输入运算符，按'#'退出*/
cout<<"|2.num1*num2 |"<<endl;
cout<<"|#.exit |"<<endl;
cout<<"--------------------------"<<endl;
while (1)
{
cin>>choose;
if (choose=="1")
{
list1+list2;
break;
}
else if (choose=="2")
{
list1*list2;
break;
}
else if (choose=="#")
{
return;
}
else
{
cout<<"输入有误，请重新输入！！"<<endl;
continue;
}
}
}
}

/*头文件，包括长整数数据结构的定义，成员函数的定义*/
/***********************************************************/

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
struct DblNode{
int data;
DblNode * prior;
DblNode * next;
};

bool IsNum(char a){ //判断字符a是否是便是数字
int s=a-'0';
if(s>=0&&s<10) return true;
else return false;
}

bool IsInt(string a){ //判断字符串a是否表达一串数字
bool Jud=1;
int i=1;
char s=a[0];
if (a=="+"||a=="-") return false;
if (s=='+'||s=='-') {}
else if (s>='1'&&s<='9'){}
else if (a[0]=='0'&&a[1]=='\0') return true;
else return false;
while (a[i]!='\0')
{
Jud=IsNum(a[i]);
if (Jud==0) return false;
i++;
}
return true;
}

int JudSign(string s){ //返回数字的符号
if (s[0]=='-') return -1;
else if(s[0]=='0'&&s[1]=='\0') return 0;
else return 1;
}

int CtoI(char a){
int i=a-'0';
return i;
}

class DblList { //定义一个双向链表类，存储任意长度的数字
private: //并可以进展标准化输出和加法，乘法。
DblNode *head, *tail;
DblNode *current;
int sign;
public:
DblList(); //构造函数
~DblList(); //析构函数
bool CreatList(string); //生成一个双向链表
int GetCount(); //获取整数的长度
void Insert(DblNode *); //从表尾插入一个结点
void InsertFront(DblNode *); //从表头插入一个结点
void Clear(); //去除该链表
void operator+(DblList &); //实现两个任意整数的加法
void operator*(DblList &); //实现两个任意整数的乘法
DblList & operator=(DblList &); //重载赋值运算符
int Compare(DblList &); //两个整数的绝对值比拟
void Display(); //任意长度整数的标准化输出
};

DblList::DblList(){
head=new DblNode(); //构造函数
head->next=NULL;
head->prior=NULL;
tail=head;
current=NULL;
sign=0;
}

DblList::~DblList(){ //析构函数
while (head->next!=NULL)
{
current=head->next;
head->next=current->next;
delete current;
}
current=NULL;
sign=0;
delete head;
head=NULL;
tail=NULL;
}

int DblList::GetCount(){ //返回该数字的长度〔不包括符号位〕
current=head->next;
int count=0;
while (current)
{
count++;
current=current->next;
}
current=NULL;
return count;
}

void DblList::Insert(DblNode *p){ //从链表尾部插入一个结点
tail->next=p;
p->prior=tail;
tail=p;
}

void DblList::InsertFront(DblNode *q){ //从链表头部插入一个结点
if (head->next==NULL)
{
head->next=q;
q->prior=head;
tail=q;
}
else{
q->next=head->next;
head->next->prior=q;
head->next=q;
q->prior=head;
}
}

bool DblList::CreatList(string s){ //输入的任意长度的表示数字的字符串
bool j=IsInt(s); //以此生成双向链表
if (!j) return j;
else{
int i=0;
sign=JudSign(s);
if (s[0]=='+'||s[0]=='-') i++;
while (s[i]!='\0')
{
int ia=CtoI(s[i]);
current=new DblNode();
current->data=ia;
current->next=NULL;
current->prior=NULL;
Insert(current);
i++;
current=NULL;
}
return true;
}
}

void DblList::Clear(){
while (head->next)
{
current=head->next;
head->next=current->next;
delete current;
}
tail=head;
sign=0;
current=NULL;
}

int DblList::Compare(DblList & s){ //任意两个长度数字绝对值比拟
int a=GetCount();
int b=s.GetCount();
if (a>b) return 1;
else if (a<b) return -1;
else
{
current=head->next;
s.current=s.head->next;
while (current!=NULL)
{
int re=current->data-s.current->data;
if (re>0) return 1;
else if (re<0) return -1;
else
{
current=current->next;
s.current=s.current->next;
}
}
current=NULL;
s.current=NULL;
return 0;
}
}

DblList & DblList::operator =(DblList &s){
Clear();
sign=s.sign;
s.current=s.head->next;
while (s.current!=NULL)
{
current=new DblNode();
current->data=s.current->data;
Insert(current);
s.current=s.current->next;
}
s.current=NULL;
current=NULL;
return *this;
}

void DblList::operator +(DblList & s){ //实现加法〔包括减法〕
DblList temp;
int da;
int f=0;
int si=Compare(s);
if (si==0&&(sign+s.sign==0)) temp.sign=0;
else
{
if (si==0) temp.sign=sign;
else if(si>0) temp.sign=sign;
else temp.sign=s.sign;
current=tail;
s.current=s.tail;
while (1)
{
if (current==head&&s.current==s.head)
{
if (f)
{
da=f;
temp.current=new DblNode();
temp.current->data=f;
temp.InsertFront(temp.current);
}
if (!f) break;
f=0;
}
else if (current!=head&&s.current==s.head)
{
temp.current=new DblNode();
temp.current->data=current->data+f;
temp.InsertFront(temp.current);
current=current->prior;
f=0;
}
else if (current==head&&s.current!=s.head)
{
temp.current=new DblNode();
temp.current->data=s.current->data+f;
temp.InsertFront(temp.current);
s.current=s.current->prior;
f=0;
}
else{
da=current->data*sign+s.current->data*s.sign+f;
if (da*temp.sign>=10)
{
da=da-10*temp.sign;
f=temp.sign;
}
else if (da*temp.sign<0)
{
da=da+10*temp.sign;
f=-temp.sign;
}
else f=0;
temp.current=new DblNode();
temp.current->next=NULL;
temp.current->data=abs(da);
temp.InsertFront(temp.current);
current=current->prior;
s.current=s.current->prior;
}
}
current=NULL;
s.current=NULL;
}
temp.current=temp.head->next;
if (temp.current!=NULL)
while (temp.current->data==0)
{
temp.head->next=temp.current->next;
delete temp.current;
temp.current=temp.head->next;
}
temp.current=NULL;
cout<<"num1+num2=";
temp.Display();
}

void DblList::operator*(DblList & s){ //实现乘法
int cf=0;
int ans;
int i,j;
int count=0;
DblList temp;
temp.sign=sign*s.sign;
int a1=GetCount();
int a2=s.GetCount();
int a=a1+a2;
for (i=0;i<a;i++)
{
temp.current=new DblNode();
temp.current->data=0;
temp.current->next=NULL;
temp.current->prior=NULL;
temp.InsertFront(temp.current);
}
s.current=s.tail;
while (s.current!=s.head){
current=tail;
temp.current=temp.tail;
for (i=0;i<count;i++) temp.current=temp.current->prior;
for(j=0;j<a1;j++){
ans=s.current->data*current->data+temp.current->data+cf;
temp.current->data=ans%10;
cf=ans/10;
current=current->prior;
temp.current=temp.current->prior;
}
if (cf!=0)
{
temp.current->data=temp.current->data+cf;
cf=0;
}
s.current=s.current->prior;
temp.current=temp.tail;
count++;
}
if(temp.head->next->data==0)
{
temp.current=temp.head->next;
temp.head->next=temp.current->next;
delete temp.current;
temp.current=NULL;
}
cout<<"num1*num2=";
temp.Display();
}

void DblList::Display(){ //任意长数字的标准化输出
int count=GetCount();
if (sign==0)
{
cout<<"0"<<endl;
return ;
}
else if (sign==-1) cout<<"-";
current=head->next;
while (current!=NULL)
{
if(count>0){
cout<<current->data;
count--;
if (count%3==0&&count!=0) cout<<",";
current=current->next;
}
}
current=NULL;
cout<<endl;
cout<<"--------------------------------------------------------------"<<endl;
}
14 / 14