长整数的四则运算.docx
- 文档编号:2502647
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:12
- 大小:184.16KB
长整数的四则运算.docx
《长整数的四则运算.docx》由会员分享,可在线阅读,更多相关《长整数的四则运算.docx(12页珍藏版)》请在冰点文库上搜索。
课程名称:
《数据结构》课程设计
课程设计题目:
长整数的四则运算
姓名:
院系:
计算机学院
专业:
计算机科学与技术
年级:
学号:
指导教师:
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-1215-1。
输入和输出形式:
按中国对于长整数的表示习惯,每四位一组,组间用逗号隔开。
测试数据:
(1)0;0;应输出“0”。
(2)-23456789;-76543211;应输出“-100000000”。
(3)-99999999;1000000000000;应输出“999(4)100010001;-100010001;应输出“0”。
(5)100010001;-100010000;应输出“1”。
(6)-999999999999;-999999999999;应输出“1999999999998”。
(7)1000099999999;1;应输出“1000100000000”。
实现提示:
(1)每个结点中可以存放的最大整数为32767,才能保证两数相加不会溢出,但若这样存放,即相当于按32768进制存放,在十进制与32768进制数之间的转换十分不方便,故可以在每个结点中仅存十进制的4位,即不超过9999的非负整数,整个链表表示为万进制。
(2)可以利用头结点数据域的符号代表长整数的符号。
用其绝对值表示元素结点数目。
相加过程中不要破坏两个操作数链表。
不能给长整数位数规定上限。
3.1概要设计
利用双向循环链表现实长整数的存储,每个结点含一个整形变量。
输入的形式以回车结束,可以直接输入正数或负数。
按中国对于长整数的表示习惯,每四位一组,除数字和位于首位置的负号外,其它一切字符都将作为分隔符,连续多个分隔符当一个处理,但不使用分隔符也不影响结果。
3.3调试分析
测试数据,测试输出的结果,时间复杂度分析,和每个模块设计和调试时存在问题的思考(问题是哪些?
问题如何解决?
),算法的改进设想。
3.4用户手册(略)
3.5测试结果(略)
4总结
长整数用双向循环队列的数据结构,用的比较少,查阅不少资料
5、程序清单:
(见附录)
#include
#include
#include
#include
usingnamespacestd;
structLinkNode
{
intdata;//记录每个节点的整数(小于10000)
LinkNode*next;//记录下一个节点的地址
LinkNode*pre;//记录前一个节点的地址
};
classLinkList
{
private:
LinkNode*head0,*head1;//head0,head1分别记录两个整数链表的头指针
LinkNode*currptr;
LinkNode*result;//result记录结果链表的头指针
public:
LinkList();//构造函数,初始化链表
~LinkList();//析构函数,释放空间
voidCreat(stringa);//引入字符串,创立两个链表,分别表示两个整数
voidAdd();//实现两个整数相加
voidDisplay();//显示结果
voidaddtwo();
//节点多的作为被加数,少的作为加数,实现整数绝对值大的加小的
};
intsum(intn);
LinkList:
:
LinkList()//构造函数,初始化链表
{
head0=newLinkNode;
//申请一个空间记录整数的符号和节点数
head1=newLinkNode;
head0->next=head0;
head0->pre=head0;//初始化链表,建立双向循环链表
head1->next=head1;
head1->pre=head1;
result=newLinkNode;
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;
deletecurrptr;
}
while(p2!
=p2->pre)//逐个删除节点,释放空间
{
p2->pre->next=p2->next;
p2->next->pre=p2->pre;
currptr=p2;
p2=p2->next;
deletecurrptr;
}
while(p3!
=p3->pre)
{
p3->pre->next=p3->next;
p3->next->pre=p3->pre;
currptr=p3;
p3=p3->next;
deletecurrptr;
}
}
voidLinkList:
:
Creat(stringa)//引入字符串,创立两个链表,分别表示两个整数
{
inti=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=newLinkNode;//把整数存到双向循环链表中
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=newLinkNode;
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;
}
voidLinkList:
:
Add()//实现两个整数相加
{
LinkNode*temp;
if(abs(head0->pre->data)>abs(head1->pre->data))
//两个整数中,绝对值大的为被加数
addtwo();
elseif(abs(head0->pre->data)
{
temp=head0;
head0=head1;
head1=temp;
addtwo();
}
elseif(abs(head0->pre->data)==abs(head1->pre->data))
{
intk1,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();
}
}
}
voidLinkList:
:
addtwo()
//节点多的作为被加数,少的作为加数,实现整数绝对值大的加小的
//默认head0存的整数绝对值比head1大
{
ints=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=newLinkNode;
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);
}
}
elseif(m1>0&&m2<0)
//符号不同,在此相当于实现两个正整数相减
{
s=0;
if(currptr->data<0)//小于0,向前一位借1
{
currptr->data+=10000;
s=-1;
}
}
elseif(m1<0&&m2>0)
//符号不同,在此相当于实现负整数加上正整数
{
s=0;
if(currptr->data>0)//大于0,
{
currptr->data=10000-currptr->data;
s=1;
}
elsecurrptr->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=newLinkNode;
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);}
}
elseif(m1>0&&m2<0)
{
s=0;
if(currptr->data<0)
{
currptr->data+=10000;
s=-1;
}
}
elseif(m1<0&&m2>0)
{
s=0;
if(currptr->data>0)
{
currptr->data=10000-currptr->data;
s=1;
}
elsecurrptr->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=newLinkNode;
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);
}
}
voidLinkList:
:
Display()//显示结果
{
LinkNode*p=result;
intFuHao=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<
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=p->next;
}
if(p==result->pre->pre&&abs(result->pre->data)!
=1)
//显示最后一个节点数据
{
cout<<",";
cout.width(4);
cout.fill('0');
cout<
}
cout< } intsum(intn)//计算10的乘方 { inti,s=1; for(i=1;i<=n;i++) { s=s*10; } returns; } intmain()//主函数 { cout<<"------------长整数的加法运算-------------"< cout<<"|输入形式为: (-)**,****,****;(-)*,****,****,****|\n"; stringch; charYes_No; do{ cout<<"|请输入你要计算的两个数: |\n"; cin>>ch;//输入任意长字符串 LinkListList;//定义链表对象 List.Creat(ch);//把字符串转化为整数,并存到链表中 List.Add();//实现两个整数相加 List.Display();//输出结果 cout<<"是否继续计算(Y/N): ";//询问是否继续计算 cin>>Yes_No; }while(Yes_No=='y'||Yes_No=='Y');//Yes_No不等于'Y'或'y'时,程序退出 } 6、参考文献1严蔚敏,吴伟民编著.数据结构(C语言版)--北京: 清华大学出版社,2007.2严蔚敏,吴伟民米宁编著.数据结构题集(C语言版)--北京: 清华大学出版社,2007.3网上搜索相关程序作为参考
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 整数 四则运算