长整数四则运算加减法

1、青岛理工大学数据结构课程设计报告题目：长整数四则运算 院（系）：计算机工程学院 学生姓名: 班级： 学号:起迄日期: 指导教师: 房斐斐 20122013年度 第 2 学期 一、需求分析 1.问题描述： 设计一个实现任意长的整数进行加、减法运算的演示程序。2.基本功能1、本程序实现计算任意长的整数的加、减法运算. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。 2、本演示程序中，集合的元素限定为数字字符09和字符，与；，输入字符可以任意长，输入形式以“回车符”为结束标志，串中字符顺序不限，且允许

2、出现重复字符。3、利用双向循环链表现实长整数的存储，每个结点含一个整形变量。输入的形式以回车结束，可以直接输入正数或负数。按中国对于长整数的表示习惯，每四位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，连续多个分隔符当一个处理。但不使用分隔符也不影响结果。3.输入输出（1）0；0；加法应输出“0”，减法应输出”0”。（2）-2345,6789；-7654,3211；加法应输出“-1,0000,0000”，减法应输出”5408,6422”。（3）-9999,9999；1,0000,0000,0000；加法应输出“9999,0000,0001”，减法应输出1,0000,9999,9

3、999。（4）1,0001,0001；-1,0001,0001；加法应输出“0”，减法应输出”2,0002,0002”。（5）1,0001,0001；-1,0001,0000；加法应输出“1”，减法应输出”2,0002,0001”。（6）-9999,9999,9999；-9999,9999,9999；加法应输出“1,9999,9999,9998”，减法应输出”0”。（7）1,0000,9999,9999；1；加法应输出“1,0001,0000,0000”，减法应输出”1,0000,9999,9998”。二、 概要设计1. 设计思路：（1） 利用双向循环链表现实长整数的存储，每个结点中可以存放的

4、最大整数为32767，才能保证两数相加不会溢出，但若这样存放，即相当于按32768进制存放，在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。（2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。2. 数据结构设计：1) 数据类型：typedef int datatype; /定义数据类型 typedef struct doublenode /定义链表元素 datatype

5、 data; struct doublenode *prior; struct doublenode *next; dlnode; 2) 存储结构：顺序结构，链式存储。采用链式存储的方式会方便字符的读入和操作，且算法简单易懂。3. 软件结构设计： 1)初始化链表void initnode(dlnode *head) 2) 向链表第n个位置插入元素x int insertnode(dlnode *head,int n,datatype x)3) 判断整数n有几位int digit(int n)4) 两数相加void add(dlnode *h1,dlnode *h2) 5) 两数相减void j

6、ian(dlnode *h1,dlnode *h2)6）打印链表 void printnode(dlnode *head)7）删除链表void destroynode(dlnode *head)8）主函数int main()三、 详细设计 1. 数据类型。 typedef int datatype; /定义数据类型 typedef struct doublenode /定义链表元素 datatype data; struct doublenode *prior; struct doublenode *next; dlnode; 2.存储结构类型：void initnode(dlnode *he

7、ad) /初始化链表 if(*head=(dlnode*)malloc(sizeof(dlnode)=null) exit(1); (*head)->prior=*head; (*head)->next=*head; 3.主函数和其他函数的伪码算法；1.主函数：int main() /主函数 dlnode *head1,*head2; char data1n,data2n; char d110,d210; int i,j,k; int xun;printf("提示：较长的字符串数作为被加数，如果等长，则第一个数加第二个数nn"); while(1) printf

8、("输入数据：n"); scanf("%s %s",data1,data2); initnode(&head1); initnode(&head2); i=0;k=0; while(data1i!='') /将数1用链表储存 for(j=0;j<10;j+) d1j=0; j=0; while(data1i!=''&&data1i!=',') d1j+=data1i+; if(data1i=',') i+; if(data10='-')

9、/处理正负数 j=-(int)fabs(atoi(d1); /atoi()把字符串转换成整型数,头文件: #include <stdlib.h> elsej=atoi(d1); insertnode(head1,k+,j); i=0; k=0; while(data2i!='') /将数2用链表储存 for(j=0;j<10;j+) d2j=0; j=0; while(data2i!=''&&data2i!=',') d2j+=data2i+; if(data2i=',')i+; if(data2

10、0='-') /处理正负数 j=-(int)fabs(atoi(d2); elsej=atoi(d2); insertnode(head2,k+,j); printf("选择加减法：1加法，0退出n"); scanf("%d",&xun);if(xun=0)break; switch(xun) case 1:if(strlen(data1)>=strlen(data2) /较长的数作为被加数 add(head1,head2); else add(head2,head1); break; default:break; dest

11、roynode(&head1); destroynode(&head2);printf("nn"); return 0; 2.初始化链表：void initnode(dlnode *head) /初始化链表 if(*head=(dlnode*)malloc(sizeof(dlnode)=null) exit(1); (*head)->prior=*head; (*head)->next=*head; 3.向链表第n个位置插入元素x int insertnode(dlnode *head,int n,datatype x) /向链表第n个位置插入元

12、素x dlnode *p,*nt; int i=0; p=head->next; while(p!=head&&i<n) /寻找插入位置 p=p->next; i+; if(i!=n) printf("插入位置错误n"); return 0; if(nt=(dlnode *)malloc(sizeof(dlnode)=null) exit(1); nt->data=x; nt->prior=p->prior; nt->prior->next=nt; nt->next=p; p->prior=nt;

13、return 1; 4. 判断整数n有几位 int digit(int n) /判断整数n有几位 int i; for(i=1;n/=10,i+) if(n/10=0) return i; 5.打印链表 void printnode(dlnode *head) /打印链表 printf("结果是："); dlnode *p=head->prior; int i; while(p->data=0) /去掉前面的一串0 p=p->prior; if(p=head) printf("0n"); return; printf("%d&

14、quot;,p->data); /最前面的一个数进行特殊处理,不用补零 p=p->prior; while(p!=head) /打印后面的数字 printf(","); if(p->data=0) printf("0000"); p=p->prior; continue; for(i=0;i<4-digit(p->data);i+) /补零 printf("0"); printf("%d",p->data); p=p->prior; printf("n&qu

15、ot;); 6.删除链表 void destroynode(dlnode *head) dlnode *p,*p1; p=(*head)->next; while(p!=*head) p1=p; p=p->next; free(p1); free(p); head=null; 7. 两数相加 void add(dlnode *h1,dlnode *h2) int i=0,j=0;dlnode *head3; initnode(&head3); dlnode *p1=h1->prior,*p2=h2->prior,*p3; while(p1!=h1&&am

16、p;p2!=h2) /每个链表元素相加 i=p1->data+p2->data ; p1=p1->prior;p2=p2->prior; insertnode(head3,j+,i);while(p1!=h1)insertnode(head3,j+,p1->data);p1=p1->prior; p3=head3->next; while(p3!=head3->prior) /处理链表元素 if(p3->data>=10000) p3->next->data+=p3->data/10000; p3->data%

17、=10000; if(p3->data<0) /处理负数 if(head3->prior!=0) p3->next->data-=1; p3->data+=10000; p3->data=(int)fabs(p3->data); p3=p3->next; if(head3->prior->data>=10000) /处理最前面的数 insertnode(head3,j,head3->prior->data/10000); head3->prior->prior->data%=10000; if

18、(head3->prior->data<=-10000) insertnode(head3,j,head3->prior->data/10000); head3->prior->prior->data%=10000; head3->prior->prior->data=(int)fabs(head3->prior->prior->data); printnode(head3); 8. 两数相减void jian(dlnode *h1,dlnode *h2) int i=0,j=0;dlnode *head4;

19、initnode(&head4); dlnode *p1=h1->prior,*p2=h2->prior,*p4; while(p1!=h1&&p2!=h2) /每个链表元素相减i=p1->data-p2->data ; p1=p1->prior; p2=p2->prior; insertnode(head4,j+,i);while(p1!=h1)insertnode(head4,j+,p1->data);p1=p1->prior; p4=head4->next; while(p4!=head4->prior)

20、 /处理链表元素 if(p4->data>=10000) p4->next->data+=p4->data/10000; p4->data%=10000; if(p4->data<0) /处理负数 if(head4->prior!=0&&p4->data<=-10000) p4->next->data-=1; p4->data+=10000; p4->data=(int)fabs(p4->data); p4=p4->next; if(head4->prior->da

21、ta>=10000) /处理最前面的数 insertnode(head4,j,head4->prior->data/10000); head4->prior->prior->data%=10000; if(head4->prior->data<=-10000) insertnode(head4,j,head4->prior->data/10000); head4->prior->prior->data%=10000; head4->prior->prior->data=(int)fabs(he

22、ad4->prior->prior->data); printnode(head4);4. 主函数的程序流程图 开始initnode(&head1)initnode(&head2)insertnode(head1,k+,j) switch(sun)insertnode(head2,k+,j)case 2jian(head2,head1)case 1add(head1,head2)defaultbreakinitnode(&head4)initnode(&head3)insertnode(head3,j+,i)insertnode(head4,j

23、+,i)printnode(head4)printnode(head3)destroynode(&head1)destroynode(&head1)四、调试分析 1. 实际完成的情况说明程序基本功已完成，包括：输入长整型数字字符，用双向循环链表储存，计算两数之和、之差，输出值，删除链表，基本符合题目要求。2. 程序的性能分析时间复杂度：o(strlen(data1)+strlen(data2)3. 上机过程中出现的问题及其解决方案 1）双向循环链表指针指向错误 双向循环链表使用错误，指针顺序不对，参考教课书改正。 2)打印顺序错误由于计算值储存顺序是从尾到头，开始误认为是从头到

24、尾，修改指针指向改正。3) 中间计算值错误 中间计算值不足四位的应用0补足。 4）中间值小于0处理错误 中间值小于0但大于-100000的数应取绝对值，小于-10000的数应先借位，这个数加上10000后，再取绝对值4. 程序中可以改进的地方说明 两操作数的头指针存于指针数组中是简化程序结构的一种方法，但由于广泛使用指针 易造成混乱，所以就放弃了，以后可以改进。5. 程序中可以扩充的功能及设计实现假想。本程序可拓展到乘除运算，还有乘方和阶乘运算。五、测试结果l 测试方法：输入数据l 测试数据：（1）0；0；加法应输出“0”，减法应输出”0”。（2）-2345,6789；-7654,3211；加

25、法应输出“-1,0000,0000”，减法应输出”5408,6422”。（3）-9999,9999；1,0000,0000,0000；加法应输出“9999,0000,0001”，减法应输出1,0000,9999,9999。（4）1,0001,0001；-1,0001,0001；加法应输出“0”，减法应输出”2,0002,0002”。（5）1,0001,0001；-1,0001,0000；加法应输出“1”，减法应输出”2,0002,0001”。（6）-9999,9999,9999；-9999,9999,9999；加法应输出“1,9999,9999,9998”，减法应输出”0”。（7）1,0000,9999,9999；1；加法应输出“1,0001,0000,0000”，减法应输出”1,0000,9999,9998”。六、用户手册本程序使用起来简单方便，只要按照菜单提示进行即可。1.加法1. 输入0；0；2. 输入-2345,6789；-7654,3211；3. 输入-9999,9999；1,0000,0000,0000；4. 输入1,0001,0001；-1,0001,0001；5. 输入1,0001,0001；-1,0001,0000；6. 输