链表表示数的运算

算法

题目
分析
实现

题目

用单向链表表示十进制整数，求两个正整数的和。如下，1234+77=1311,注意单向链表的方向。

1->2->3->4
+     7->7
-----------
1->3->1->1

输入:

1234 77

分析

由于是单向链表，其操作顺序为从前往后，但由于十进制加法的特性要求我们从后往前计算，因此可以考虑先将链表反转，然后进行加法计算，得到结果后再次反转链表。

实现

typedef struct list {
    struct list *next;
    int data;
} list;

list *reverse(list *l)
{
        list *prev = NULL;

        while (l != NULL) {
                list *next = l->next;
                l->next = prev;
                prev = l;
                l = next;
        }

        return prev;
}

void release(list *l)
{
    while (l != NULL) {
        list *tmp = l->next;
        free(l);
        l = tmp;
    }
}

list *list_add(list *l, int n)
{
    list *tmp = l;
    list *new;
 
 
    new = malloc(sizeof(list));
    if (new == NULL)
        return NULL;
     
    new->data = n;
    new->next = NULL;
 
    if (tmp == NULL)
        return new;

    while (tmp->next != NULL) {
        tmp = tmp->next;
    }
    tmp->next = new;
    return l;
 
}

void show(list *l)
{
    list *tmp = l;
    while(tmp != NULL) {
        printf("%d", tmp->data);
        tmp = tmp->next;
        if (tmp == NULL) {
            printf("\n");
        } else {
            printf("->");
        }
    }
}

list *add(list *a, list *b)
{
    list *itera = a;
    list *iterb = b;
    int c = 0;
 
    if (a == NULL || b == NULL)
        return NULL;
 
    while(1) {
        itera->data += (iterb->data + c);
        if (itera->data > 9) {
            itera->data -= 10;
            c = 1;
        } else {
            c = 0;
        }
     
        if(itera->next == NULL || iterb->next == NULL) {
            break;
        }
     
        itera = itera->next;
        iterb = iterb->next;
    }
 
    if (iterb->next != NULL) {
        itera->next = iterb->next;
        iterb->next = NULL;
    }
    if (c) {
        itera->next->data++;
    }

    return a;
}

int main()
{
    int num1[] = {1,2,3,4};
    int num2[] = {7,7};
    list *a,*b;
    int i;
    for (i = 0; i < sizeof(num1)/sizeof(int); i++) {
        if ((a = list_add(a, num1[i])) == NULL) {
            printf("list allocat error!\n");
            return -1;
        }
    }
 
    for (i = 0; i < sizeof(num2)/sizeof(int); i++) {
        if ((b = list_add(b, num2[i])) == NULL) {
            printf("list allocat error!\n");
            return -1;
        }
    }
 
    a = reverse(a);
    b = reverse(b);
 
    a = add(a, b);
    a = reverse(a);
    release(a);
    release(b);
    return 0;
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 yxhlfx@163.com