[ 问题描述 ]
设计程序实现两个任意长整数的求和运算。
[ 基本要求 ]
《数据结构》题集
利用双向循环链表实现长整数的存储, 每个结点含一个整型变量. 任何整型变量的范围是 -(215-1)~(215-1)。输入和输出形式: 按中国对于长整数的表示习惯, 每四位一组,组间用逗号隔开。
[ 测试数据 ]
(1) 0;0;应输出"0"。
(2) -2345,6789;-7654,3211; 应输出"-1,0000,0000"。
(3) -9999,9999; 1,0000,0000,0000; 应输出"9999,0000,0001"。
(4) 1,0001,0001; -1,0001,0001; 应输出"0"。
(5) 1,0001,0001; -1,0001,0000; 应输出"1"。
[ 实现提示 ]
(1) 每个结点可以存放的最大整数为 215-1 = 32767 才能保证两数相加不会溢出。但若这样存,即相当于按 32768 进制数存,在十进制数与 32768 进制数间的转换十分不方便,故可以在每个结点中仅存十进制数的 4 位,即不超过 9999的非负整数, 整个链表被视为万进制。
(2)可以利用头结点数据域的符号代表长整数的符号。 用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。
[ 选作内容 ]
修改上述程序,使它在整型量范围是-(2n-1)~(2n-1) 的计算机上都能有效地运行。其中 n 是由程序读入的参量。输入数据的分组方法可另行规定。
1