11.用链表模拟大整数加法运算

ゞ浴缸里的玫瑰 2022-05-26 10:26 215阅读 0赞

例如：9->9->9->NULL

\+                      1->NULL

1->0->0->0->NULL

思路：

使用递归，能够实现从前往后计算。

// LinkTable.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include <string>
    using namespace std;
    
    //链表的结构体
    struct node
    {
    	char val;
    	node * next;
    };
    
    //建立链表
    struct node * create( string & str_link )
    {
    	int len = str_link.length();
    
    	struct node * phead = new node();     //带有表头的链表，表头中不存储任何元素
    	struct node * preNode = phead;
    	for( int i=0; i<len; i++ )
    	{
    		struct node * pNode = new node();
    		pNode->val = str_link[i];
    		pNode->next = NULL;
    		preNode->next = pNode;
    		preNode = pNode;
    	}
    	return phead;
    }
    
    //输出链表
    void out_link( struct node * phead )
    {
    	if( phead == NULL )
    		return;
    	struct node * pNode = phead->next;
    	while( pNode )
    	{
    		cout <<pNode->val;
    		pNode = pNode->next;
    	}
    	cout << endl;
    }
    
    //求无表头链表的长度
    //返回-1为链表不存在
    int link_length( struct node* pNode )
    {
    	if(!pNode) return -1;
    
    	int len=0;
    	while( pNode )
    	{
    		pNode = pNode->next;
    		len++;
    	}
    	return len;
    }
    
    
    //大数相加递归算法
    //pNode1, pNode2为两个中间运算结点，但不是头结点
    struct node * add( struct node * pNode1, struct node * pNode2, int & carry )
    {
    	if( !pNode1  ) return pNode2;
    	if( !pNode2  ) return pNode1;

//为了参数简洁，这里增大了计算量，可以将链表长度作为参数传进来
    	int len1 = link_length( pNode1 );
    	int len2 = link_length( pNode2 );
    
    
    	if( len1 == len2 )
    	{
    		if( len1==1 )             //递归终止条件
    		{
    			struct node * pNode = new node();
    			int sum = (pNode1->val - '0' ) + ( pNode2->val -'0');
    			carry = sum/10;
    			pNode->val = sum%10 + '0';
    			pNode->next = NULL;
    			return pNode;
    		}
    		else
    		{
    			int carry_cur=0;
    			struct node * pNode = new node();
    			struct node * pNext = add( pNode1->next, pNode2->next, carry_cur );
    			int sum = (pNode1->val - '0' ) + ( pNode2->val -'0') + carry_cur;
    			carry = sum/10;
    			pNode->val = sum%10 + '0';
    			pNode->next = pNext;
    			return pNode;
    		}
    	}
    
    	if( len1>len2 )
    	{
    		int carry_cur=0;
    			struct node * pNode = new node();
    			struct node * pNext = add( pNode1->next, pNode2, carry_cur );
    			int sum = (pNode1->val - '0' ) + carry_cur;
    			carry = sum/10;
    			pNode->val = sum%10 + '0';
    			pNode->next = pNext;
    			return pNode;
    	}
    
    	if( len1<len2 )
    	{
    		int carry_cur=0;
    			struct node * pNode = new node();
    			struct node * pNext = add( pNode1, pNode2->next, carry_cur );
    			int sum = (pNode2->val - '0' ) + carry_cur;
    			carry = sum/10;
    			pNode->val = sum%10 + '0';
    			pNode->next = pNext;
    			return pNode;
    	}
    
    	return NULL;
    }
    
    struct node * add( struct node * phead1, struct node * phead2 )
    {
    	if( !phead1 || !phead1->next ) return phead2;
    	if( !phead2 || !phead2->next ) return phead1;
    
    	int carry = 0;
    	struct node * pNode = add( phead1->next, phead2->next, carry );
    
    	if( carry > 0 )                     //有进位，则需要多一个结点
    	{
    		struct node * pCarry = new node();
    		pCarry->val = '0' + carry;
    		pCarry->next = pNode;
    		pNode = pCarry;
    	}
    
    	struct node * phead = new node();
    	phead->next = pNode;
    	return phead;
    }
    
    void test()
    {
    	string str;
    	cout << "Input the first link:"<<endl;
    	cin >> str;
    	struct node *phead1 = create( str );
    	
    	cout << "Input the second link:"<<endl;
    	cin >> str;
    	struct node *phead2 = create( str );
    
    	struct node * phead = add( phead1, phead2);
    	
    	cout<< "The result is:" <<endl;
    	out_link( phead );
    
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	test();
    	return 0;
    }