一、需求分?/p>
【问题描述?/p>
设计一个程序实现两个任意长的整数求和运算?/p>
【基本要求?/p>
利用双向循环链表实现长整数的存储,每个结点含一个整型变量?/p>
任何整型变量的范围是?/p>
-
?/p>
215-1
?/p>
~
?/p>
215-1
?/p>
。输入和输出形式?/p>
按中国对?/p>
长整数的表示习惯,每四位一组,组间用逗号隔开?/p>
【测试数据?/p>
?/p>
1
?/p>
0
?/p>
0
;应输出?/p>
0?/p>
?/p>
?/p>
2
?/p>
?/p>
2345
?/p>
6789
?/p>
-7654
?/p>
3211
;应输出?/p>
-1
?/p>
0000
?/p>
0000?/p>
?/p>
?/p>
3
?/p>
?/p>
9999
?/p>
9999
?/p>
1
?/p>
0000
?/p>
0000
?/p>
0000
;应输出
?999
?/p>
0000
?/p>
0001?/p>
?/p>
?/p>
4
?/p>
1
?/p>
0001
?/p>
0001
?/p>
-1
?/p>
0001
?/p>
0001
;应输出?/p>
0?/p>
?/p>
?/p>
5
?/p>
1
?/p>
0001
?/p>
0001
?/p>
-1
?/p>
0001
?/p>
0000
;应输出?/p>
1?/p>
?/p>
二、设?/p>
1.
设计思想
?/p>
1
)存储结构:循环双向链表
?/p>
2
)主要算法基本思想?/p>
1
?/p>
每个结点中可以存放的最大整数为
215-1=32767
?/p>
才能保证两数相加
不会溢出。但若这样存,即相当于按
32768
进制数存,在十进制数?/p>
32768
进制数之间的转换十分不方便。故可以在每个结点中仅存十进
制数
4
位,
即不超过
9999
的非负整数,整个链表视为万进制数?/p>
2
、可以利用头结点数据域的符号代表长整数的符号。用其绝对值表?/p>
元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存
于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限?/p>
2.
设计表示
?/p>
1
)函数调用关系图?/p>
?/p>
2
)函数接口规格说明:
结构体:
struct dl_node
{
int x;
dl_node *pre;
dl_node *next;
};