刘冉.cpp

问题描述：设计一个程序实现两个任意长的整数的求和运算。 基本要求：利用双向循环链表

// 刘冉.cpp : Defines the entry point for the console application.
//

// k.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//ZhengshuAdd.h文件，链表的定义部分
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
struct LinkNode
{
int data;                  //记录每个节点的整数（小于10000）
LinkNode *next;            //记录下一个节点的地址
LinkNode *pre;             //记录前一个节点的地址
};
class LinkList
{
private:
LinkNode *head0,*head1;      //head0，head1分别记录两个整数链表的头指针
LinkNode *currptr;
LinkNode *result;            //result记录结果链表的头指针
public:
LinkList();                   //构造函数，初始化链表
~LinkList();                 //析构函数，释放空间
void Creat(string a);        //引入字符串，创立两个链表，分别表示两个整数
void Add();                  //实现两个整数相加
void Display();              //显示结果
void addtwo(); 
void      Scrpee();      
//节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的
};
//ZhengshuAdd.cpp文件，链表的实现部分
//#include "ZhengshuAdd.h"
int sum(int n);
LinkList::LinkList()                //构造函数，初始化链表
{
head0=new LinkNode;           
//申请一个空间记录整数的符号和节点数
head1=new LinkNode;
head0->next=head0;
head0->pre=head0;               //初始化链表，建立双向循环链表
head1->next=head1;
head1->pre=head1;
      result=new LinkNode;
result->next=result;
result->pre=result;
currptr=NULL;
}

LinkList::~LinkList()                        //析构函数，释放空间
{
LinkNode *p1=head0,*p2=head1,*p3=result;  
//三个指针分别指向三条链表的头指针
while(p1!=p1->pre)                        
{
    p1->pre->next=p1->next;
    p1->next->pre=p1->pre;
    currptr=p1;
    p1=p1->next;
    delete currptr;
}
while(p2!=p2->pre)                        //逐个删除节点，释放空间
{ 
    p2->pre->next=p2->next;
    p2->next->pre=p2->pre;
    currptr=p2;
    p2=p2->next;
    delete currptr;
}
while(p3!=p3->pre)
{
    p3->pre->next=p3->next;
    p3->next->pre=p3->pre;
    currptr=p3;
    p3=p3->next;
    delete currptr;
}
// delete p1;
// delete p2;
// delete p3;
}

void LinkList::Creat(string a)                   //引入字符串，创立两个链表，分别表示两个整数
{
int i=0,j=0,m=0,n=0,k=0,l=0,s=0,w=0;      
//i记录字符串，j记录加数节点数；s记录被加数节点数
                //w标记字符串中的‘-’号
             //k记录字符串中的字符转化为整数的值，l使每个节点记录4位
while(a[m]!=';') m++;            //m记录字符串中被加数的字符数
    n=m;                                
while(a[n]!='\0') n++;           //n记录字符串的总字符数
if(a[0]=='-')
{
    head0->data=(-1);              //记录整数符号
    w=1;
}
else {head0->data=1;}
for(i=m-1;i>=w;i--)             
{
    if(a[i]!=',')                   //把字符转化为整数
    {
     k+=(a[i]-'0')*sum(l);
     l++;
    }
    if(a[i]==','||i==w)
    {
     currptr=new LinkNode;             //把整数存到双向循环链表中
     currptr->data=k;
     currptr->next=head0;
     currptr->pre=head0->pre;
     head0->pre->next=currptr;
     head0->pre=currptr;
     head0=currptr; 
     s++;                               //节点数加1
     k=0;                               //重新初始化k和l
     l=0;                             
    }
}
      head0->pre->data*=s;                     //存储整数符号和节点数


//与建第一个整数链表一样，建立第二个整数链表head1
k=0;l=0;

if(a[m+1]=='-')
{
    head1->data=(-1);
    m++;
}
else 
    head1->data=1;
for(i=n-1;i>m;i--)
{
    if(a[i]!=',')
    {
     k+=(a[i]-'0')*sum(l);
     l++;
    }
    if(a[i]==','||i==m+1)
    {
     currptr=new LinkNode;
     currptr->data=k;
     currptr->next=head1;
     currptr->pre=head1->pre;
     head1->pre->next=currptr;
     head1->pre=currptr;
     head1=currptr;
     j++;
     k=0;
     l=0;
    }
}
head1->pre->data*=j;
}

void LinkList::Add()                               //实现两个整数相加
{
LinkNode *temp;
if(abs(head0->pre->data)>abs(head1->pre->data))        
    //两个整数中，绝对值大的为被加数
    addtwo();
else if(abs(head0->pre->data)<abs(head1->pre->data))
{
    temp=head0;
    head0=head1;
    head1=temp;
    addtwo();
}
else if(abs(head0->pre->data)==abs(head1->pre->data))
{
    int k1,k2;
    LinkNode *p=head0,*q=head1;                
//如果节点数相同，则判断节点中数值大小 

while(p->data==q->data&&p!=head0->pre->pre&&q!=head1->pre->pre)
    {
     p=p->next;
     q=q->next;
    }
    k1=p->data;
    k2=q->data;
    if(k1>k2)
     addtwo();
    else 
    { 
    temp=head0;
    head0=head1;
    head1=temp;
    addtwo();
    }
}
}
void LinkList::addtwo()        
//节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的
             //默认head0存的整数绝对值比head1大
{
int s=0,m1=head0->data,m2=head1->data;
m1=(head0->pre->data/abs(head0->pre->data));         //head0的符号
m2=(head1->pre->data/abs(head1->pre->data));         //head1的符号
LinkNode *p=head0->pre->pre,*q=head1->pre->pre;
result->data=head0->pre->data;            //存结果的节点数和符号  
while(q!=head1->pre)        
//head0存的整数绝对值比head1大，即head0的节点数大于或等于head1
{
    currptr=new LinkNode;
    currptr->data=(p->data)*m1+(q->data)*m2+s;     //两整数相加
    if((m1*m2)>0)                             //如果符号相同
    {
     if(abs(currptr->data)-10000>=0)       //相加后超过10000，则进位
     {
      s=currptr->data/10000;
      currptr->data=abs(currptr->data)%10000;
     } 
     else                 //abs(currptr->data)-10000<0，不进位
     {
      s=0;
      currptr->data=abs(currptr->data);
     }
    }
    else if(m1>0&&m2<0)              
//符号不同，在此相当于实现两个正整数相减
    {
     s=0;
     if(currptr->data<0)               //小于0，向前一位借1
     {
      currptr->data+=10000;
      s=-1;
     }
    }
    else if(m1<0&&m2>0)           
//符号不同，在此相当于实现负整数加上正整数
    { 
     s=0;
     if(currptr->data>0)           //大于0，
     {
      currptr->data=10000-currptr->data;
      s=1;
     }
     else currptr->data=abs(currptr->data);
    }
    currptr->next=result;              //存入链表
    currptr->pre=result->pre;
    result->pre->next=currptr;
    result->pre=currptr;
    result=currptr;
    p=p->pre;
    q=q->pre;
}              
       //当head0节点数比head1长时，继续建链
while(p!=head0->pre)  
{
    currptr=new LinkNode;
    currptr->data=p->data*m1+s;
    s=currptr->data/10000;
    if((m1*m2)>0)
    {
     if(abs(currptr->data)-10000>=0)
     {
      s=currptr->data/10000;
      currptr->data=abs(currptr->data)%10000;
     }
     else {s=0;currptr->data=abs(currptr->data);}
    }
    else if(m1>0&&m2<0)
    {
     s=0;
     if(currptr->data<0)
     {
      currptr->data+=10000;
      s=-1;
     }
    }
    else if(m1<0&&m2>0)
    {
     s=0;
     if(currptr->data>0)
     {
      currptr->data=10000-currptr->data;
      s=1;
     }
     else currptr->data=abs(currptr->data);
    }
    currptr->data=abs(currptr->data)%10000;
    currptr->next=result;
    currptr->pre=result->pre;
    result->pre->next=currptr;
    result->pre=currptr;
    result=currptr;
    p=p->pre;
}
if(s!=0)                     //处理相加后，进位问题
{
    currptr=new LinkNode;
    currptr->data=abs(s);
    currptr->next=result;
    currptr->pre=result->pre;
    result->pre->next=currptr;
    result->pre=currptr;
    result=currptr;
    result->pre->data=m1*(abs(result->pre->data)+1);
}
}
void LinkList::Display()                     //显示结果
{
LinkNode *p=result;
int FuHao=result->pre->data/abs(result->pre->data);//结果的符号
while(p->data==0&&p!=result->pre->pre)              
//当运算后前几个节点的数据为0时，不输出
{
    p=p->next;
    result->pre->data=(abs(result->pre->data)-1)*FuHao; 
//结果记录非0节点数
}
cout<<FuHao*p->data;           //首先显示符号和第一个节点中的数
if(abs(result->pre->data)!=1) p=p->next; //判断非0节点数是否为1
while(p!=result->pre->pre)      //继续输出
{
    cout<<",";                 //每4位一组，并用‘，’隔开
    cout.width(4);
       cout.fill('0');
          cout<<p->data;
          p=p->next;
}
if(p==result->pre->pre&&abs(result->pre->data)!=1)   
//显示最后一个节点数据
{
    cout<<",";
    cout.width(4);
       cout.fill('0');
          cout<<p->data;
}
cout<<endl;
}
int sum(int n)                    //计算10的乘方
{
int i,s=1;
for(i=1;i<=n;i++)
{
    s=s*10;
}
return s;
}

//main.cpp文件，主函数和其他函数的实现
//#include"ZhengshuAdd.h"                     //访问文件ZhengshuAdd.h
void main()                      //主函数
{LinkList List; int i=0; 
    for(i=0;i<100000000;i++);
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";

cout<<"               |===============================================|\n";
cout<<"               |***********************************************|\n";
cout<<"               |**********欢迎使用任意长整数加法系统***********|\n";
cout<<"               |***********************************************|\n";
cout<<"               |===============================================|\n";
for(i=0;i<1000000000;i++);
system("cls"); 
List.Scrpee();
}

void LinkList::Scrpee()
{
	cout<<"\n";
	cout<<"\n";
	cout<<"\n";
	cout<<"                        |在此系统中，可以输入任意长的整数|\n";
string ch;
char Yes_No;
do{
    cout<<"\n";
	cout<<"\n";
    cout<<"\n";
	cout<<"\n";
	cout<<"\n";
	cout<<"                  |输入形式为：(-)**,****,****;(-)*,****,****,****|\n";
    cout<<"\n";
	cout<<"                  |即符号+数，每4位加一个','，两个数之间用';'隔开 |\n";
    cout<<"\n";
	cout<<"                  |请输入你要计算的两个数:                        |\n";
    cout<<"\n";
	cin>>ch;                                    //输入任意长字符串
    LinkList List;                             //定义链表对象
    List.Creat(ch);                            //把字符串转化为整数，并存到链表中
    List.Add();                                //实现两个整数相加
    List.Display();                              //输出结果
    cout<<"是否继续计算(Y/N):";                    //询问是否继续计算
    cin>>Yes_No;
}while(Yes_No=='y'||Yes_No=='Y');     //Yes_No不等于'Y'或'y'时，程序退出
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"                    |===============================================|\n";
cout<<"                    |***********************************************|\n";
cout<<"                    |*****************感谢使用本系统!***************|\n";
cout<<"                    |***********************************************|\n";
}