长整数的四则运算
你是最爱-护士执业资格考试试题
课程名称: 《数据结构》课程设计
课程设计题目: 长整数的四则运算
姓 名:
院系: 计算机学院
专 业:计算机科学与技术
年 级:
学 号:
指导教师:
2014 年月 日
目 录
1
课程设计的目的………………………………………………………………3
2
需求分析………………………………………………………………………3
3
课程设计报告内容……………………………………………………………3
3.1概要设计……………………………………………………………………3
3.2详细设计……………………………………………………………………3
3.3调试分析……………………………………………………………………3
3.4用户手册……………………………………………………………………4
3.5测试结果……………………………………………………………………4
3.6程序清单……………………………………………………………………5
4 小结
…………………………………………………………………………x
5 参考文献
………………………………………………………………8
1.课程设计的目的
(1) 熟练使用 C 语言编写程序，解决实际问题;
(2)
了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能
力;
(3)
初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本
方法和技能;
(4)
提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
2.需求分析
问题描述:
设计一个实现任意长的整数进行加法运算的演示程序。基本要求:
利用双向循环链表实现长整数的存储，
每个结点含一个整形变量。任何整形变量
的范围是 -215 - 1 215 - 1。输入和输出形
式:按中国对于长整数的表示习惯，
每四位一组，组间用逗号隔开。测试数据:(1)0;0;应输出‚
0‛ 。
(2)-23456789;-76543211;应输出‚-100000000‛ 。(3
)-99999999;1;
应输出‚999(4)100010001;-100010001;应输
出‚0‛。(5)100010001;-100010000;
应输出‚1‛
。(6)-999999999999;-999999999999;应输出‚98‛
。
(7)1;1;应输出‚1‛。
实现提示:(1)每个结点中可以存放的最大整数为
32767，才能保证两数相加
不会溢出，但若这样存放，即相当于按 32768
进制存放，在十进制与 32768 进
制数之间的转换十分不方便，故可以在每个结点中仅存十进制的
4 位，即不超
过 9999 的非负整数，整个链表表示为万进制。(2)可以利用头结点数据域的符
号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个
操作数链表。不
能给长整数位数规定上限。
3.1概要设计
利用双向循环链表现实长整数的存储，每个结点
含一个整形变量。输入的形
式以回车结束，可以直接输入正数或负数。按中国对于长整数的表示习惯，每
四
位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，连续多
个分隔符当一
个处理,但不使用分隔符也不影响结果。
3.3调试分析
测试数据，测试输出的结果，时间
复杂度分析，和每个模块设计和调试时存
在问题的思考（问题是哪些？问题如何解决？），算法的改进设
想。
3.4用户手册(略)
3.5测试结果(略)
4总结
长整数用双向循环队列的数据结构，用的比较少，查阅不少资料
5、程序清单:(见附录)
#include
#include
#include
#include
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();
节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的
};
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;
}
}
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)
{
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;
如果节点数相同，则判断节点中数值大小
whil
e(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->dataabs(head0->pre->data));
head0的符
号
m2=(head1->pre->dataabs(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->data10000;
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->data10000;
if((m1*m2)>0)
{
if(abs(currptr->data)-10000>=0)
{
s=currptr->data10000;
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=r
esult->pre->dataabs(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<
if(abs(result->pre->data)!=1) p=p->next;
判断非0节点数是否为1
while(p!=result->pre->pre)
继续输出
{
cout<<每4位一组，并用‘，’隔开
(4);
('0');
cout<
p=p->next;
}
if(p==result->pre->pre&&abs(result->pre->data)!=1)
显示最后一个节点数据
{
cout<<
(4);
('0');
cout<
}
cout<
int
sum(int n) 计算10的乘方
{
int i,s=1;
for(i=1;i<=n;i++)
{
s=s*10;
}
return s;
}
int
main() 主函数
{
cout<<长整
数的加法运算-------------
cout<<输入形式为：(-)**,****,****
;(-)*,****,****,****|n
string ch;
char
Yes_No;
do{
cout<<请输入你要计算的两个数:
|n
cin>>ch;
输入任意长字符
串
LinkList List;
定义链表对象
(ch);
把字符串转化为整数，并存到
链表中
();
实现两个整数相加
y();
输出结果
cout<<是否继续计算(YN):询问是否继续
计算
cin>>Yes_No;
}while(Yes_No=='y'||Yes_No=='Y');
Yes_No不等于'Y'或'y'时，
程序退出
}
6、参考文献1
严蔚敏，吴伟民 编著. 数据结构(C 语言版)--北京: 清华
大学出版社，2007.2
严蔚敏，吴伟民 米 宁 编著. 数据结构题集(C 语言版)--
北京: 清华大学出版社，
2007.3网上搜索相关程序作为参考