生活随笔
收集整理的這篇文章主要介紹了
链表系列之单链表——使用单链表实现大整数相加
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
原文：http://blog.csdn.net/iloveyoujelly/article/details/38321735
大數(shù)相加在我之前的一篇博客里有一個使用數(shù)組實現(xiàn)的方案，使用單鏈表實現(xiàn)更靈活。
有兩個由單鏈表表示的數(shù)。每個結(jié)點(diǎn)代表其中的一位數(shù)字。
數(shù)字的存儲是逆序的， 也就是說個位位于鏈表的表頭。
寫一函數(shù)使這兩個數(shù)相加并返回結(jié)果，結(jié)果也由鏈表表示。
eg.
?Input:(3->9->6), (4->7->8->3)
Output:(7->6->5->4)
?
[html]?view plaincopy
#include?<iostream>??#include?<stack>??using?namespace?std;????typedef?struct?node??{??????int?data;??????node?*next;??}Node,?*LinkList;??//建立鏈表??Node*?createList(const?int?a[],?int?n)??{??????Node?*head,?*endPtr;??????head?=?endPtr?=?NULL;????????????for(int?i=0;i<n;i++)??????{??????????Node?*temp?=?new?Node; / /node = (struct Node *)malloc(sizeof(struct Node));????????temp->data?=?a[i];??????????temp->next?=?NULL;????????????if(i==0)??????????{??????????????head?=?endPtr?=?temp;??????????}??????????else??????????{??????????????endPtr->next?=?temp;??????????????endPtr?=?temp;??????????}??????}????????return?head;??}??/*從尾到頭打印鏈表，要求不修改鏈表結(jié)構(gòu)*/??//使用棧適配器??void?PrintListReversing(LinkList?pHead)??{??????stack<Node*>?nodes;??????Node*?pNode?=?pHead;????????????if(pNode==NULL)??????????return;????????while(pNode!=NULL)???//將節(jié)點(diǎn)依次入棧??????{??????????nodes.push(pNode);??????????pNode?=?pNode->next;??????}????????while(!nodes.empty())???//出棧??????{??????????pNode?=?nodes.top();???//讀取棧頂元素??????????cout<<pNode->data;??????????nodes.pop();???//刪除棧頂元素??????}??}??//大數(shù)相加??Node?*ListAdd(Node*?L1,?Node*?L2)??{??????if(L1==NULL)??????????return?L2;??????if(L2==NULL)??????????return?L1;????????Node?*ptr1?=?L1,?*ptr2?=?L2,?*ResultPtr=NULL,?*TmpPtr=NULL;??????int?carry?=?0;????????Node?*p_node?=?new?Node();??????p_node->data?=?(L1->data+L2->data)%10;??????p_node->next?=?NULL;??????carry?=?(L1->data+L2->data)/10;??????ResultPtr?=?TmpPtr?=?p_node;??????TmpPtr->next?=?NULL;??????L1?=?L1->next;??????L2?=?L2->next;????????while(L1?&&?L2)??????{??????????Node?*pNode?=?new?Node();??????????TmpPtr->next?=?pNode;????????????int?tmp?=?L1->data+L2->data+carry;??????????carry?=?tmp/10;??????????pNode->data?=?tmp%10;??????????pNode->next?=?NULL;????????????TmpPtr?=?TmpPtr->next;??????????L1?=?L1->next;??????????L2?=?L2->next;??????}????????while(L1)??????{??????????Node?*pNode?=?new?Node();??????????TmpPtr->next?=?pNode;????????????int?tmp?=?L1->data+carry;??????????carry?=?tmp/10;??????????pNode->data?=?tmp%10;??????????pNode->next?=?NULL;????????????TmpPtr?=?TmpPtr->next;??????????L1?=?L1->next;??????}??????while(L2)??????{??????????Node?*pNode?=?new?Node();??????????TmpPtr->next?=?pNode;????????????int?tmp?=?L2->data+carry;??????????carry?=?tmp/10;??????????pNode->data?=?tmp%10;??????????pNode->next?=?NULL;????????????TmpPtr?=?TmpPtr->next;??????????L2?=?L2->next;??????}????????if(carry)??????{??????????Node?*pNode?=?new?Node();??????????TmpPtr->next?=?pNode;????????????pNode->data?=?carry;??????????pNode->next?=?NULL;??????}????????return?ResultPtr;??}????int?main()??{??????int?a[]?=?{1,9,9};??//991??????int?b[]?=?{9,8,5,6,6,2,8};???//8266589??????Node?*L1?=?createList(a,3),?*L2?=?createList(b,7),?*L3?=?NULL;????????L3?=?ListAdd(L1,L2);????????PrintListReversing(L1);??????cout<<"+";??????PrintListReversing(L2);??????cout<<"=";??????PrintListReversing(L3);??????cout<<endl;????????return?1;??} ?
總結(jié)
以上是生活随笔為你收集整理的链表系列之单链表——使用单链表实现大整数相加的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
