算法.List链表加法

链表加法
/*************************************************************************
        > File Name: list.h
        > Author: zhoulin
        > Mail: 715169549@qq.com
        > Created Time: Sat 16 Apr 2016 10:58:58 AM CST
 ************************************************************************/

#ifndef _LIST_H
//define a node of list
typedef struct _baseNode
{
    int v;
    struct _baseNode *next;
}baseNode;
baseNode *listAdd(baseNode *p1,baseNode *p2);
baseNode *listInsert(baseNode *b,int v);
void listFree(baseNode *p);
#define _LIST_H
#endif

listc:

/*************************************************************************
        > File Name: list.c
        > Author: zhoulin
        > Mail: 715169549@qq.com
        > Created Time: Sat 16 Apr 2016 11:04:56 AM CST
 ************************************************************************/

#include "list.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define size 64
void listPrt(baseNode *p)
{
    while(p != NULL)
    {
        if(p->next == NULL)
        {
            fprintf(stdout," %d
",p->v);
            break;
        }
        fprintf(stdout,"%d ->",p->v);
        p = p->next;
    }
}
baseNode *listInsert(baseNode *b,int v)
{
    char pbuf[size] = {''};
    sprintf(pbuf,"%d",v);
    int len = strlen(pbuf),i;
    for(i = 0;i < len;i++)
    {
        char tbuf[2] = {''};
        strncpy(tbuf,pbuf+i,1);
        if(b == NULL)
        {
            b = (baseNode *)malloc(sizeof(*b));
            b->next = NULL;
        }
        else{
            baseNode *cur = (baseNode *)malloc(sizeof(*b));
            cur->next = NULL;
            cur->next = b;
            b = cur;
        }
        b->v = atoi(tbuf);
    }
    return b;
}
//分三种情况
//  1.链接平衡，p1.len = p2.len
//  2.链表左倾，p1.len > p2.len
//  3.链表右倾，p1.len < p2.len
// p1 = 1->2->3,代表321;
// p2 = 4->9->0->3,代表3094
// 输出：p3 = 5->1->4->3,3451
baseNode *listAdd(baseNode *p1,baseNode *p2)
{
    baseNode *ph1 = p1;
    baseNode *ph2 = p2;
    baseNode *head = NULL;
    baseNode *tail = NULL;
    baseNode *ph = NULL;
    baseNode *fn = NULL;
    int mode = 0,flag = 0,sum = 0;
    while(ph1 != NULL && ph2 != NULL)
    {
        
        if(ph == NULL)
        {
            ph = (baseNode *)malloc(sizeof(*ph));
            ph->next = NULL;
            tail = head = ph;
        }else{
            baseNode *cur = (baseNode *)malloc(sizeof(*cur));
            cur->next = NULL;
            ph->next = cur;
            ph = cur;
            tail = cur;
        }
        sum = ph1->v + ph2->v+flag;
        if(sum >= 10)
        {
            mode = (sum)%10;
            flag = 1;
        }else{
            mode = sum;
            flag = 0;
        }
        ph->v = mode;
        ph1 = ph1->next;
        ph2 = ph2->next;
    }
    if(ph1 != NULL)
    {
        fn = ph1;
    }
    if(ph2 != NULL)
    {
        fn = ph2;
    }
    while(fn != NULL)
    {
        baseNode *t = (baseNode *)malloc(sizeof(*tail));
        sum = fn->v + flag;
        if(sum >= 10)
        {
            mode = sum%10;
            flag = 1;
        }else
        {
            mode = sum;
            flag = 0;
        }
        t->v = mode;
        tail->next = t;
        tail = t;
        fn = fn->next;
    }
    if(flag == 1)
    {
        baseNode *t = (baseNode *)malloc(sizeof(*tail));
        t->v = flag+mode;
        tail->next = t;
        tail=t;
    }
    return head;
}
//销毁链表
void listFree(baseNode *p)
{
    while(p!= NULL)
    {
        baseNode *n = p->next;
        free(p);
        p = n;
    }
    p = NULL;
}
int main(int argc,char *args[])
{
    if(argc != 3)
    {
        printf("usage:
");
        printf("   %s p1 p2
",args[0]);
        return -1;
    }
    int v1 = atoi(args[1]);
    int v2 = atoi(args[2]);
    fprintf(stdout,"********v1 = %d, v2 =%d********
",v1,v2);
    baseNode *p1 = listInsert(NULL,v1);
    baseNode *p2 = listInsert(NULL,v2);
    baseNode *p3 = listAdd(p1,p2);
    printf("
---------p1--------------
");
    listPrt(p1);
    printf("
---------p2--------------
");
    listPrt(p2);
    printf("
---------add p1 and p2 equals p3--------------
");
    listPrt(p3);
    listFree(p1);
    listFree(p2);
    listFree(p3);
    return 0;
}

运行结果：

　　

zhoulin@:~/code/c_src/algorithm/list_add:./list 22211 99999
********v1 = 22211, v2 =99999********

---------p1--------------
1 ->1 ->2 ->2 -> 2

---------p2--------------
9 ->9 ->9 ->9 -> 9

---------add p1 and p2 equals p3--------------
0 ->1 ->2 ->2 ->2 -> 3