C趣味编程百例(33)超长正整数的加法

99.超长正整数的加法
请设计一个算法，完成两个超长正整数的加法。
*问题分析与算法设计
首先要设计一个数据结构来表示一个超长正整数，然后才能设计算法。
首先，我们用一个带头节点的环形链来表示一个非负的超大整数。如果每个数字都是从低位开始编号的，则由第一个数字到第四个数字，第五个数字到第八个数字等组成。，被放置在第一、第二，...节点，不足四位数存储在链表的最后一个节点。指定了头节点的值。例如:
大整数“587890987654321”可以用下面的链表来表示，头节点head:

根据这个数据结构，可以从两个头节点开始，依次相加，找出需要的进位，在后面的运算中会用到。具体实现算法见程序中的注释。
*程序和程序注释
# include
# include
# define hun Hou 10000
typedef结构节点{ intdata
struct node * next；
}节点；/*定义链表结构*/

NODE *insert_after(NODE *u，int num)；/*在U节点后插入一个新节点，值为num */
NODE * additive(NODE * p，NODE * q)；/*完成加法运算，将指针*/
void printint(NODE *s)返回到*p+*q的结果；
NODE * input int(void)；

void main()
{
NODE *s1、*s2、* s；
NODE *inputint()，*addint()，* insert _ after()；
printf(" Enter S1 = ")；
S1 = input int()；/*输入被加数*/
printf(" Enter S2 = ")；
S2 = input int()；/*输入加数*/
printf(" S1 = ")；print int(S1)；putchar(' \ n ')；/*显示被加数*/
printf(" S2 = ")；print int(S2)；putchar(' \ n ')；/* display加数*/
s =加法(S1、S2)；/* sum */
printf(" S1+S2 = ")；printint(s)；putchar(' \ n ')；/* output result */
}
node * insert _ after(node * u，int num)
{
node * v；
v =(NODE *)malloc(sizeof(NODE))；/*申请一个节点*/
v-> data = num；/*赋值*/
u-> next = v；/*插入一个节点*/
在U节点后返回v；
}
node * additive(node * p，node * q)/*完成加法运算并返回一个指向*p+*q */
{
node * pp，* QQ，* r，* s，* t.
int total，number，carry
PP = p-> next；qq=q->下一个；
s =(NODE *)malloc(sizeof(NODE))；/*建立存储sum */
s->data=-1的链表头；
t = s；进位= 0；/*进位:进位*/
while(pp->数据！=-1&&qq->数据！=-1) /*不是header */
{
total = PP-> data+QQ-> data+carry；/*将相应的位与前一进位相加*/
number = total % hundhou；/*求链中存储的部分的值*/
carry = total/hundou；/*计算进位*/
t = insert _ after (t，number)；/*将部分和存储在S方向的链中*/
PP = PP-> next；/*分别取以下加数*/
QQ = QQ-> next；
}
r=(pp->data！=-1)?PP:QQ；/*取未完成自理的链指针*/
while(r->data！=-1) /*处理加数中较大的数字*/
{
total = r-> data+carry；/*加到进位*/
number = total % huntou；/*求链中存储的部分的值*/
carry = total/hundou；/*计算进位*/
t = insert _ after (t，number)；/*将部分和存储在S */
r=r->next所指向的链中；/*取以下值*/
}
if(carry)t = insert _ after(t，1)；/*处理最后一个进位*/
t-> next = s；/*完成的链表并*/
返回s；/*返回结构指针，指向and */
}
NODE * input int(void)/*输入一个超长正整数*/
{
NODE *s，*ps，* qs
结构号{ int num
结构号* np
}*p，* q；
int i，j，k；
long sum；
char c；
p = NULL；/*指向输入的整数，链路径是整数的最低位，链尾是整数的位*/
while((c=getchar()))！='\n') /*输入一个整数以接收数字*/
if(c > = ' 0 ' & & c {
q =(struct number *)malloc(sizeof(struct number))；/*在应用程序之间空*/
q-> num = c-' 0 '；/*存一个整数*/
q-> NP = p；/*建立指针*/
p = q；
}
s =(NODE *)malloc(sizeof(NODE))；
s-> data =-1；/*建表求一个超长正整数的链头*/
PS = s；
while(p！=NULL) /*将接收到的临时数据链接中的数据转换成要求的标准格式*/
{
sum = 0；I = 0；k = 1；
while(I {
sum = sum+k *(p-> num)；
i++；p = p-> NP；k = k * 10
}
QS =(NODE *)malloc(sizeof(NODE))；/*应用程序之间空*/
QS-> data = sum；/*赋值并建立链表*/
PS-> next = QS；
PS = QS；
}
PS-> next = s；
return s；
}
void print int(NODE * s)
{
if(s-> next-> data！=-1) /*如果不是头，输出*/
{
print int(s-> next)；/*递归输出*/
if(s-> next-> data = =-1)
printf(" % d "，s-> next-> data)；
else{
int i，k = HUNTHOU
for(I = 1；我put char(' 0 '+s-> next-> data %(k)/(k/10))；
}
}
}