Code :
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
unsigned char c;
struct Node *next;
}Node;
typedef Node *slist;
slist reverse(slist);
Node *makeNode(unsigned char);
/*
*/
slist Sum(slist left, slist right) {
if(!left || !right) {
return left ? left : right;
}
left = reverse(left);
right = reverse(right);
unsigned char carry = left->c + right->c;
slist ret = makeNode(carry % 10);
carry /= 10;
Node *p = left->next;
Node *q = right->next;
Node *r = ret;
while(p || q) {
carry += (p? p->c : 0) + (q ? q->c : 0);
r->next = makeNode(carry % 10);
carry /= 10;
r = r->next;
p = p ? p->next : NULL;
q = q ? q->next : NULL;
}
if(carry)
r->next = makeNode(1);
reverse(left);
reverse(right);
return reverse(ret);
}
/*
utilities
*/
slist reverse(slist s) {
if(s->next == NULL)
return s;
Node *ret = reverse(s->next);
s->next->next = s;
s->next = NULL;
return ret;
}
Node *makeNode(unsigned char c) {
Node * tmp = calloc(sizeof(Node), 1);
tmp->c = c;
return tmp;
}
void print(slist s) {
if(s == NULL) {
printf("\n");
return;
}
printf("%c", s->c + '0');
print(s->next);
}
slist listFromString(const unsigned char *s) {
if(!s || !*s) return NULL;
slist ret = makeNode(*s++ - '0');
Node *tmp = ret;
unsigned char c;
while((c = *s++)) {
tmp->next = makeNode(c - '0');
tmp = tmp->next;
}
return ret;
}
int main()
{
slist left = listFromString("99");
slist right = listFromString("233823");
slist sum = Sum(left, right);
print(sum);
return 0;
}
0 comments:
Post a Comment