ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > IT综合 > 算法用链表模拟大整数加法运算

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

IT综合 作者：dongyu2013 时间：2014-04-15 16:43:32 0 删除 编辑

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

+                      1->NULL

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


思路：

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


[cpp] view plaincopyprint?
  1. // LinkTable.cpp : 定义控制台应用程序的入口点。  
  2. //  
  3.   
  4. #include "stdafx.h"  
  5. #include   
  6. #include   
  7. using namespace std;  
  8.   
  9. //链表的结构体  
  10. struct node  
  11. {  
  12.     char val;  
  13.     node * next;  
  14. };  
  15.   
  16. //建立链表  
  17. struct node * create( string & str_link )  
  18. {  
  19.     int len = str_link.length();  
  20.   
  21.     struct node * phead = new node();     //带有表头的链表，表头中不存储任何元素  
  22.     struct node * preNode = phead;  
  23.     for( int i=0; i
  24.     {  
  25.         struct node * pNode = new node();  
  26.         pNode->val = str_link[i];  
  27.         pNode->next = NULL;  
  28.         preNode->next = pNode;  
  29.         preNode = pNode;  
  30.     }  
  31.     return phead;  
  32. }  
  33.   
  34. //输出链表  
  35. void out_link( struct node * phead )  
  36. {  
  37.     if( phead == NULL )  
  38.         return;  
  39.     struct node * pNode = phead->next;  
  40.     while( pNode )  
  41.     {  
  42.         cout <val;  
  43.         pNode = pNode->next;  
  44.     }  
  45.     cout << endl;  
  46. }  
  47.   
  48. //求无表头链表的长度  
  49. //返回-1为链表不存在  
  50. int link_length( struct node* pNode )  
  51. {  
  52.     if(!pNode) return -1;  
  53.   
  54.     int len=0;  
  55.     while( pNode )  
  56.     {  
  57.         pNode = pNode->next;  
  58.         len++;  
  59.     }  
  60.     return len;  
  61. }  
  62.   
  63.   
  64. //大数相加递归算法  
  65. //pNode1, pNode2为两个中间运算结点，但不是头结点  
  66. struct node * add( struct node * pNode1, struct node * pNode2, int & carry )  
  67. {  
  68.     if( !pNode1  ) return pNode2;  
  69.     if( !pNode2  ) return pNode1;  

  1. "white-space: pre;">    //为了参数简洁，这里增大了计算量，可以将链表长度作为参数传进来  
  2.     int len1 = link_length( pNode1 );  
  3.     int len2 = link_length( pNode2 );  
  4.   
  5.   
  6.     if( len1 == len2 )  
  7.     {  
  8.         if( len1==1 )             //递归终止条件  
  9.         {  
  10.             struct node * pNode = new node();  
  11.             int sum = (pNode1->val - '0' ) + ( pNode2->val -'0');  
  12.             carry = sum/10;  
  13.             pNode->val = sum%10 + '0';  
  14.             pNode->next = NULL;  
  15.             return pNode;  
  16.         }  
  17.         else  
  18.         {  
  19.             int carry_cur=0;  
  20.             struct node * pNode = new node();  
  21.             struct node * pNext = add( pNode1->next, pNode2->next, carry_cur );  
  22.             int sum = (pNode1->val - '0' ) + ( pNode2->val -'0') + carry_cur;  
  23.             carry = sum/10;  
  24.             pNode->val = sum%10 + '0';  
  25.             pNode->next = pNext;  
  26.             return pNode;  
  27.         }  
  28.     }  
  29.   
  30.     if( len1>len2 )  
  31.     {  
  32.         int carry_cur=0;  
  33.             struct node * pNode = new node();  
  34.             struct node * pNext = add( pNode1->next, pNode2, carry_cur );  
  35.             int sum = (pNode1->val - '0' ) + carry_cur;  
  36.             carry = sum/10;  
  37.             pNode->val = sum%10 + '0';  
  38.             pNode->next = pNext;  
  39.             return pNode;  
  40.     }  
  41.   
  42.     if( len1
  43.     {  
  44.         int carry_cur=0;  
  45.             struct node * pNode = new node();  
  46.             struct node * pNext = add( pNode1, pNode2->next, carry_cur );  
  47.             int sum = (pNode2->val - '0' ) + carry_cur;  
  48.             carry = sum/10;  
  49.             pNode->val = sum%10 + '0';  
  50.             pNode->next = pNext;  
  51.             return pNode;  
  52.     }  
  53.   
  54.     return NULL;  
  55. }  
  56.   
  57. struct node * add( struct node * phead1, struct node * phead2 )  
  58. {  
  59.     if( !phead1 || !phead1->next ) return phead2;  
  60.     if( !phead2 || !phead2->next ) return phead1;  
  61.   
  62.     int carry = 0;  
  63.     struct node * pNode = add( phead1->next, phead2->next, carry );  
  64.   
  65.     if( carry > 0 )                     //有进位，则需要多一个结点  
  66.     {  
  67.         struct node * pCarry = new node();  
  68.         pCarry->val = '0' + carry;  
  69.         pCarry->next = pNode;  
  70.         pNode = pCarry;  
  71.     }  
  72.   
  73.     struct node * phead = new node();  
  74.     phead->next = pNode;  
  75.     return phead;  
  76. }  
  77.   
  78. void test()  
  79. {  
  80.     string str;  
  81.     cout << "Input the first link:"<
  82.     cin >> str;  
  83.     struct node *phead1 = create( str );  
  84.       
  85.     cout << "Input the second link:"<
  86.     cin >> str;  
  87.     struct node *phead2 = create( str );  
  88.   
  89.     struct node * phead = add( phead1, phead2);  
  90.       
  91.     cout<< "The result is:" <
  92.     out_link( phead );  
  93.   
  94. }  
  95.   
  96. int _tmain(int argc, _TCHAR* argv[])  
  97. {  
  98.     test();  
  99.     return 0;  
  100. }  

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29012686/viewspace-1142668/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： 算法单链表交换任意两个元素
下一篇： 算法单链表快速排序算法实现
请登录后发表评论 登录
全部评论
dongyu2013

注册时间：2013-12-25

  • 博文量
    263
  • 访问量
    238078

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593