ACM程序設(shè)計常用算法和數(shù)據(jù)結(jié)構(gòu)參考

./ACM程序設(shè)計常用算法與數(shù)據(jù)結(jié)構(gòu)參考Tomsdinary目錄前言6排序算法7插入排序7選擇排序9冒泡排序10希爾排序11隨機(jī)化快速排序13歸并排序16堆排序18大整數(shù)處理21包含頭文件21定義21實(shí)現(xiàn)23流輸出23流輸入23賦值23轉(zhuǎn)換函數(shù)24規(guī)范化符號化25帶符號乘法26無符號取模26整數(shù)乘法27整數(shù)加法29帶符號加法31浮點(diǎn)乘法32浮點(diǎn)加法33帶符號減法35整數(shù)減法36浮點(diǎn)減法38帶符號比較40無符號比較40無符號乘方42帶符號乘方42使用方法42高級數(shù)據(jù)結(jié)構(gòu)43普通二叉搜素樹43包含頭文件43定義43實(shí)現(xiàn)46刪樹49插入元素到樹49復(fù)制樹52求樹的高度55求葉子的個數(shù)56刪除元素56使用方法58基本線段樹模式59基本并查集模式61散列實(shí)現(xiàn)的一種方式參考62定義與實(shí)現(xiàn)62使用方法71堆71包含頭文件71定義與實(shí)現(xiàn)71使用方法74圖相關(guān)算法74圖的深度優(yōu)先和廣度優(yōu)先算法舉例74無向圖最小生成樹的Kruskal算法舉例77無向圖最小生成樹的Prim算法舉例79有向圖的單源最短路徑Dijkstra算法舉例81有向圖的多源最短路徑Floyd算法舉例82拓?fù)渑判蚺e例84AOE網(wǎng)的算法舉例86求圖的一個中心算法舉例91求圖的P個中心算法舉例93SPFA算法舉例98割頂和塊的算法舉例100計算幾何算法103向量模103向量點(diǎn)積104向量叉積104左右判斷104相交判斷104正規(guī)相交交點(diǎn)105判斷多邊形凸105任意多變形面積106凸包問題的快包實(shí)現(xiàn)舉例106STL算法參考111accumulate<>111adjacent_difference<>111adjacent_find<>112binary_search<>112copy<>113copy_backward<>113count<>113count_if<>114equal<>114equal_range<>114fill<>115fill_n<>115find<>115find_if<>115find_end<>116find_first_of<>116for_each<>117generate<>117generate_n<>117includes<>117inner_product<>118inplace_merge<>118iter_swap<>119lexicographical_compare<>119lower_bound<>120max<>120max_element<>120min<>121min_element<>121merge<>121mismatch<>122next_permutation<>122nnth_element<>123partial_sort<>123partial_sort_copy<>124partial_sum<>124prev_permutation<>125random_shuffle<>125remove<>125remove_copy<>126remove_if<>126remove_copy_if<>126replace<>126replace_copy<>127replace_if<>127replace_copy_if<>127reverse<>127reverse_copy<>128rotate<>128rotate_copy<>128search<>128search_n<>129set_difference<>129set_intersection<>130set_symmetric_difference<>130set_union<>131sort<>131stable_partition<>132stable_sort<>132swap<>132swap_range<>132transform<>133unique<>133unique_copy<>134upper_bound<>134make_heap<>135pop_heap<>135push_heap<>135sort_heap<>136字符串處理136KMP算法舉例136C++語言可用頭文件138<algorithm>138<bitset>138<complex>138<deque>138<exception>138<fstream>139<functional>139<iomanip>139<ios>139<iosfwd>139<iostream>139<iso646.h>139<istream>139<iterator>140<limits>140<list>140<locale>140<map>140<memory>140<new>140<numeric>141<ostream>141<queue>141<set>141<sstream>141<stack>141<stdexcept>141<streambuf>141<string>142<strstream>142<utility>142<valarray>142<vector>142<cassert>142<cctype>142<cerrno>142<cfloat>143<ciso646>143<climits>143<clocale>143<cmath>143<csetjmp>143<csignal>143<cstdarg>143<cstddef>143<cstdio>144<cstdlib>144<cstring>144<ctime>144<cwchar>144<cwctype>144前言如今的程序設(shè)計已不再是個人英雄時代了,程序的設(shè)計和開發(fā)實(shí)施需要靠團(tuán)隊(duì)成員的積極配合和合作。軟件技術(shù)在當(dāng)今時代已不是信息技術(shù)競爭核心,對于技術(shù)知識的獲取變得不再重要。當(dāng)今IT競爭,靠的是先進(jìn)的觀念,有效的溝通和合作,靠的是高瞻遠(yuǎn)矚的預(yù)見能力,靠的是個人的想法而絕不是技能。當(dāng)然掌握好眾多技術(shù)是實(shí)現(xiàn)我們獨(dú)特創(chuàng)意的途徑,但絕不是我們可以屹立IT界的根本法寶。隨著互聯(lián)網(wǎng)發(fā)展的不斷深入,技術(shù)知識的獲取不再成為問題。程序員不能單靠通曉某一核心技術(shù)而獲得核心競爭力。當(dāng)今的IT界知識分享,知識交流,知識開放是主旋律,凡是開放的平臺,開放的個人,開放的公司才是真正擁有競爭力的,凡是那些封閉的平臺,封閉的個人,封閉的公司其發(fā)展的道路終會是艱難的。而這種開放的態(tài)度在中國程序員中更應(yīng)該得到普及與遵守。其根本在于中國程序員中的高手充其量也只是一個高級用戶,真正的技術(shù)掌握在技術(shù)公司那里。所以為什么還有保留一些使用技巧呢。不開放不分享不合作,優(yōu)秀的程序員中會淪為平庸的人?；谝陨纤伎己驼摂?我將自己三年在算法設(shè)計和數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)過程中可供借鑒和參考使用的代碼總結(jié)如下。一方面作為我們隊(duì)參加ACM的內(nèi)部參考資料,另一方面分享出來供后來者學(xué)習(xí)參考。或許對諸位會有點(diǎn)幫助。同時也請您記住和接受以上觀點(diǎn),在一個分享交流的環(huán)境你,你的技術(shù)進(jìn)步會更加迅速。也希望那些有好代碼,好思想的高手將自己的智慧分享出來。整理出來。這不僅有利于個人學(xué)習(xí)總結(jié),更有利于我們ACM隊(duì)伍健康發(fā)展。排序算法插入排序/*函數(shù)名：InsertionSort功能：插入排序模板參數(shù)說明：T必須支持小于操作參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小前置條件：data!=NULL,size>0后置條件：data按非降序排列用法：intarr[]={10,9,8,4,5,7,6,3,1,4};InsertionSort<arr,10>;*/template<typenameT>voidInsertionSort<Tdata[],intsize>{inti,j;Ttemp;for<i=1;i<size;++i> {temp=data[i];for<j=i;j>0&&temp<data[j-1];--j>data[j]=data[j-1];data[j]=temp; }}/*函數(shù)名：InsertionSort功能：插入排序模板參數(shù)說明：T元素類型,Func函數(shù)對象或函數(shù)指針參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小,f函數(shù)對象或地址前置條件：data!=NULL,size>0后置條件：data按f排列用法：boolcmp<inta,intb>{returna<b;}intarr[]={10,9,8,4,5,7,6,3,1,4};InsertionSort<arr,10,cmp>;*/template<typenameT,typenameFunc>voidInsertionSort<Tdata[],intsize,Funcf>{inti,j;Ttemp;for<i=1;i<size;++i> {temp=data[i];for<j=i;j>0&&f<temp,data[j-1]>;--j>data[j]=data[j-1];data[j]=temp; }}選擇排序/*函數(shù)名：SelectionSort功能：選擇排序模板參數(shù)說明：T必須支持小于操作參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小前置條件：data!=NULL,size>0后置條件：data按非降序排列用法：#include<algorithm>intarr[]={10,9,8,4,5,7,6,3,1,4};SelectionSort<arr,10>;*/template<typenameT>voidSelectionSort<Tdata[],intsize>{inti,j,k;for<i=0;i<size-1;++i> {k=i;for<j=i+1;j<size;++j> {if<data[j]<data[k]>k=j; }std::swap<data[i],data[k]>; }}/*函數(shù)名：SelectionSort功能：選擇排序模板參數(shù)說明：T元素類型,Func函數(shù)對象或函數(shù)地址參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小,f函數(shù)對象或地址前置條件：data!=NULL,size>0后置條件：data按f排列用法：#include<algorithm>intarr[]={10,9,8,4,5,7,6,3,1,4};boolcmp<inta,intb>{returna<b;}SelectionSort<arr,10,cmp>;*/template<typenameT,typenameFunc>voidSelectionSort<Tdata[],intsize,Funcf>{inti,j,k;for<i=0;i<size-1;++i> {k=i;for<j=i+1;j<size;++j> {if<f<data[j],data[k]>>k=j; }std::swap<data[i],data[k]>; }}冒泡排序/*函數(shù)名：BubbleSort功能：冒泡排序模板參數(shù)說明：T必須支持小于操作參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小前置條件：data!=NULL,size>0后置條件：data按非降序排列用法：#include<algorithm>intarr[]={10,9,8,4,5,7,6,3,1,4};BubbleSort<arr,10>;*/template<typenameT>voidBubbleSort<Tdata[],intsize>{inti,j;for<i=0;i<size-1;++i> {for<j=size-1;j>i;--j> {if<data[j]<data[j-1]>std::swap<data[j],data[j-1]>; } }}/*函數(shù)名：BubbleSort功能：冒泡排序模板參數(shù)說明：T元素類型,Func函數(shù)對象或函數(shù)地址參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小,f函數(shù)對象或地址前置條件：data!=NULL,size>0后置條件：data按f序排列用法：#include<algorithm>boolcmp<inta,intb>{returna<b;}intarr[]={10,9,8,4,5,7,6,3,1,4};BubbleSort<arr,10,cmp>;*/template<typenameT,typenameFunc>voidBubbleSort<Tdata[],intsize,Funcf>{inti,j;for<i=0;i<size-1;++i> {for<j=size-1;j>i;--j> {if<f<data[j],data[j-1]>>std::swap<data[j],data[j-1]>; } }}希爾排序/*函數(shù)名：ShellSort功能：希爾排序模板參數(shù)說明：T必須支持小于操作參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小前置條件：data!=NULL,size>0后置條件：data按非降序序排列用法：intarr[]={10,9,8,4,5,7,6,3,1,4};ShellSort<arr,10>;*/template<typenameT>voidShellSort<Tdata[],intsize>{inti,j,hCnt,h;intarray[20],k;Ttemp;for<h=1,i=0;h<size;++i> {array[i]=h;h=3*h+1; }for<i--;i>=0;--i> {h=array[i];for<hCnt=h;hCnt<2*h;++hCnt> {for<j=hCnt;j<size;> {temp=data[j];k=j;while<k-h>=0&&temp<data[k-h]> {data[k]=data[k-h];k-=h; }data[k]=temp;j+=h; } } }}/*函數(shù)名：ShellSort功能：希爾排序模板參數(shù)說明：T元素類型,Func函數(shù)對象或指針參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小,f函數(shù)對象或指針前置條件：data!=NULL,size>0后置條件：data按f排列用法：boolcmp<inta,intb>{returna<b;}intarr[]={10,9,8,4,5,7,6,3,1,4};ShellSort<arr,10,cmp>;*/template<typenameT,typenameFunc>voidShellSort<Tdata[],intsize,Funcf>{inti,j,hCnt,h;intarray[20],k;Ttemp;for<h=1,i=0;h<size;++i> {array[i]=h;h=3*h+1; }for<i--;i>=0;--i> {h=array[i];for<hCnt=h;hCnt<2*h;++hCnt> {for<j=hCnt;j<size;> {temp=data[j];k=j;while<k-h>=0&&f<temp,data[k-h]>> {data[k]=data[k-h];k-=h; }data[k]=temp;j+=h; } } }}隨機(jī)化快速排序/*函數(shù)名：quick_sort功能：快速排序輔助過程*/template<typenameT>voidquick_sort<Tdata[],intfrist,intlast>{intlower=frist+1;intupper=last;intt=rand<>%<last-frist>+frist;std::swap<data[frist],data[t]>;T&bound=data[frist];while<lower<=upper> {while<data[lower]<bound> { ++lower; }while<bound<data[upper]> { --upper; }if<lower<upper> {std::swap<data[lower],data[upper]>; ++lower; --upper; }else ++lower; }std::swap<data[upper],data[frist]>;if<frist<upper-1>quick_sort<data,frist,upper-1>;if<upper+1<last>quick_sort<data,upper+1,last>;}/*函數(shù)名：QuickSort功能：快速排模板參數(shù)說明：T必須支持小于操作參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小前置條件：data!=NULL,size>0后置條件：data按f排列用法：#include<algorithm>#include<stdlib.h>#include<time.h>intarr[]={10,9,8,4,5,7,6,3,1,4};QuickSort<arr,10>;*/template<typenameT>voidQuickSort<Tdata[],intsize>{inti,max;if<size<2>return;for<i=1,max=0;i<size;++i> {if<data[max]<data[i]>max=i; }std::swap<data[size-1],data[max]>;srand<time<0>>;quick_sort<data,0,size-2>;}/*函數(shù)名：quick_sort功能：快速排序輔助過程*/template<typenameT,typenameFunc>voidquick_sort<Tdata[],intfrist,intlast,Func&f>{intlower=frist+1;intupper=last;intt=rand<>%<last-frist>+frist;std::swap<data[frist],data[t]>;T&bound=data[frist];while<lower<=upper> {while<f<data[lower],bound>> ++lower;while<f<bound,data[upper]>> --upper;if<lower<upper> {std::swap<data[lower],data[upper]>; ++lower; --upper; }else ++lower; }std::swap<data[upper],data[frist]>;if<frist<upper-1>quick_sort<data,frist,upper-1,f>;if<upper+1<last>quick_sort<data,upper+1,last,f>;}/*函數(shù)名：QuickSort功能：快速排模板參數(shù)說明：T元素類型,Func函數(shù)對象或指針參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小,f函數(shù)對象或指針前置條件：data!=NULL,size>0后置條件：data按f排列用法：#include<algorithm>#include<stdlib.h>#include<time.h>boolcmp<inta,intb>{returna<b;}intarr[]={10,9,8,4,5,7,6,3,1,4};QuickSort<arr,10,cmp>;*/template<typenameT,typenameFunc>voidQuickSort<Tdata[],intsize,Funcf>{inti,max;if<size<2>return;for<i=1,max=0;i<size;++i> {if<f<data[max],data[i]>>max=i; }std::swap<data[size-1],data[max]>;srand<time<0>>;quick_sort<data,0,size-2,f>;}歸并排序/*函數(shù)名：MergeSort功能：歸并排序模板參數(shù)說明：T必須支持小于操作參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小前置條件：data!=NULL,size>0后置條件：data按非降序排列用法：#include<algorithm>intarr[]={10,9,8,4,5,7,6,3,1,4};MergeSort<arr,10>;*/template<typenameT>voidMergeSort<Tdata[],intsize>{if<size>1> {//預(yù)處理intmid=size/2;intnumOfleft=mid;intnumOfright=size-mid;T*left=newT[numOfleft];T*right=newT[numOfright];//分std::copy<data,data+numOfleft,left>;std::copy<data+numOfleft,data+size,right>;MergeSort<left,numOfleft>;MergeSort<right,numOfright>;//合std::merge<left,left+numOfleft,right,right+numOfright,data>;//清理delete[]left;delete[]right; }}/*函數(shù)名：MergeSort功能：歸并排序模板參數(shù)說明：T元素類型,Func函數(shù)對象或指針參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小,f函數(shù)對象或指針前置條件：data!=NULL,size>0后置條件：data按f排列用法：#include<algorithm>boolcmp<inta,intb>{returna<b;}intarr[]={10,9,8,4,5,7,6,3,1,4};MergeSort<arr,10,cmp>;*/template<typenameT,typenameFunc>voidMergeSort<Tdata[],intsize,Funcf>{if<size>1> {intmid=size/2;intnumOfleft=mid;intnumOfright=size-mid;T*left=newT[numOfleft];T*right=newT[numOfright];std::copy<data,data+numOfleft,left>;std::copy<data+numOfleft,data+size,right>;MergeSort<left,numOfleft,f>;MergeSort<right,numOfright,f>;std::merge<left,left+numOfleft,right,right+numOfright,data,f>;delete[]left;delete[]right; }}堆排序/*函數(shù)名：heap_down功能：堆排序輔助過程*/template<typenameT>voidheap_down<Tdata[],inti,constint&size>{intp=i*2+1;while<p<size> {if<p+1<size> {if<data[p]<data[p+1]> ++p; }if<data[i]<data[p]> {std::swap<data[p],data[i]>;i=p;p=i*2+1; }elsebreak; }}/*函數(shù)名：HeapSort功能：堆排序模板參數(shù)說明：T必須支持小于操作參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小前置條件：data!=NULL,size>0后置條件：data按非降序排列用法：#include<algorithm>intarr[]={10,9,8,4,5,7,6,3,1,4};MergeSort<arr,10>;*/template<typenameT>voidHeapSort<Tdata[],intsize>{inti;for<i=<size-1>/2;i>=0;--i>heap_down<data,i,size>;for<i=size-1;i>0;--i> {std::swap<data[0],data[i]>;heap_down<data,0,i>; }}/*函數(shù)名：heap_down功能：堆排序輔助過程*/template<typenameT,typenameFunc>voidheap_down<Tdata[],inti,constint&size,Func&f>{intp=i*2+1;while<p<size> {if<p+1<size> {if<f<data[p],data[p+1]>> ++p; }if<f<data[i],data[p]>> {std::swap<data[p],data[i]>;i=p;p=i*2+1; }elsebreak; }}/*函數(shù)名：HeapSort功能：堆排序模板參數(shù)說明：T元素類型,Func函數(shù)對象或指針參數(shù)說明：data待排序數(shù)組,size待排序數(shù)組大小,f函數(shù)對象或指針前置條件：data!=NULL,size>0后置條件：data按f排列用法：#include<algorithm>boolcmp<inta,intb>{returna<b;}intarr[]={10,9,8,4,5,7,6,3,1,4};HeapSort<arr,10,cmp>;*/template<typenameT,typenameFunc>voidHeapSort<Tdata[],intsize,Funcf>{inti;for<i=<size-1>/2;i>=0;--i>heap_down<data,i,size,f>;for<i=size-1;i>0;--i> {std::swap<data[0],data[i]>;heap_down<data,0,i,f>; }}大整數(shù)處理包含頭文件#include<iostream>#include<string>#include<stdio.h>#include<algorithm>定義//大整數(shù)類classBigInteger{public://默認(rèn)構(gòu)造explicitBigInteger<conststd::string&str="0">:m_str<str>{Normal<>;}//接受雙精度浮點(diǎn)構(gòu)造explicitBigInteger<doubled> {m_str=ToString<d>;Normal<>; }//接受單精度浮點(diǎn)構(gòu)造explicitBigInteger<floatf> {m_str=ToString<f>;Normal<>; }//接受整數(shù)構(gòu)造explicitBigInteger<inti> {m_str=ToString<i>;Normal<>; }//輸入流運(yùn)算friendstd::ostream&operator<<<std::ostream&out,constBigInteger&big>;//輸出流運(yùn)算friendstd::istream&operator>><std::istream&in,BigInteger&big>;//賦值BigInteger&operator=<constBigInteger&rbs>;BigInteger&operator=<doubled>;BigInteger&operator=<floatf>;BigInteger&operator=<inti>;//高精度乘法BigIntegeroperator*<constBigInteger&other> {returnsignMultiply<*this,other>;}//高精度加法BigIntegeroperator+<constBigInteger&other> {returnsignAdd<*this,other>;}//高精度減法BigIntegeroperator-<constBigInteger&other> {returnsignMinuse<*this,other>;}//高精度乘方BigIntegeroperator^<intn> {returnBigInteger<pow<m_str,n>>;}//高精度正數(shù)取模BigIntegeroperator%<constBigInteger&other>;//比較booloperator<<constBigInteger&rbs> {returnsignCompare<*this,rbs>==-1;}booloperator==<constBigInteger&rbs> {returnsignCompare<*this,rbs>==0;}//轉(zhuǎn)換成字符串std::stringToString<>;private://規(guī)范化voidNormal<>;voidUnnormal<>;//轉(zhuǎn)換std::stringToString<intn>;std::stringToString<doublen>;std::stringToString<floatn>;//有符號高精度運(yùn)算及其比較BigIntegersignMultiply<constBigInteger&l,constBigInteger&r>;BigIntegersignAdd<constBigInteger&l,constBigInteger&r>;BigIntegersignMinuse<constBigInteger&l,constBigInteger&r>;BigIntegersignPow<constBigInteger&x,intn>;intsignCompare<constBigInteger&a,constBigInteger&b>;//無符號比較intCompare<conststd::string&a,conststd::string&b>;//無符號高精度運(yùn)算std::stringMultiplyEx<std::strings,std::stringt>;std::stringMultiply<std::stringlbs,std::stringrbs>;std::stringAddEx<std::stringa,std::stringb>;std::stringAdd<std::stringlbs,std::stringrbs>;std::stringMinusEx<std::stringa,std::stringb,bool&sign>;std::stringMinuss<std::stringlbs,std::stringrbs,bool&sign>;std::stringpow<conststd::string&b,intn>;std::stringmod<std::strings,conststd::string&t>;//判斷s是否全為零boolisZero<conststd::string&s>;private:boolm_sign;//符號std::stringm_str;//內(nèi)部字符串};實(shí)現(xiàn)流輸出std::ostream&operator<<<std::ostream&out,constBigInteger&big>{if<!big.m_sign>out.put<'-'>;out<<big.m_str;returnout;}流輸入std::istream&operator>><std::istream&in,BigInteger&big>{in>>big.m_str;big.Normal<>;returnin;}賦值BigInteger&BigInteger::operator=<constBigInteger&rbs>{if<this!=&rbs> {m_str=rbs.m_str;m_sign=rbs.m_sign; }return*this;}BigInteger&BigInteger::operator=<doubled>{m_str=ToString<d>;Normal<>;return*this;}BigInteger&BigInteger::operator=<floatf>{m_str=ToString<f>;Normal<>;return*this;}BigInteger&BigInteger::operator=<inti>{m_str=ToString<i>;Normal<>;return*this;}BigIntegerBigInteger::operator%<constBigInteger&other>{BigIntegerret;ret.m_str=mod<m_str,other.m_str>;ret.m_sign=true;returnret;}轉(zhuǎn)換函數(shù)boolBigInteger::isZero<conststd::string&s>{for<size_ti=0;i<s.size<>;++i>if<s[i]!='0'>returnfalse;returntrue;}std::stringBigInteger::ToString<>{std::strings;if<!m_sign>s.push_back<'-'>;returns+m_str;}std::stringBigInteger::ToString<intn>{staticcharbuf[100];sprintf<buf,"%d",n>;returnstd::string<buf>;}std::stringBigInteger::ToString<doublen>{staticcharbuf[100];sprintf<buf,"%f",n>;returnstd::string<buf>;}std::stringBigInteger::ToString<floatn>{staticcharbuf[100];sprintf<buf,"%f",n>;returnstd::string<buf>;}規(guī)范化符號化voidBigInteger::Normal<>{if<m_str[0]=='-'> {m_sign=false;m_str.erase<0,1>; }elsem_sign=true;}voidBigInteger::Unnormal<>{if<!m_sign>m_str="0"+m_str;}帶符號乘法BigIntegerBigInteger::signMultiply<constBigInteger&l,constBigInteger&r>{BigIntegerret;ret.m_sign=!<l.m_sign^r.m_sign>;ret.m_str=MultiplyEx<l.m_str,r.m_str>;if<ret.m_str=="0">ret.m_sign=true;returnret;}無符號取模std::stringBigInteger::mod<std::strings,conststd::string&t>{std::stringp;boolf; {intsize=t.size<>;p=s.substr<0,size>;s.erase<0,size>;while<!s.empty<>> {while<Compare<p,t>>=0>p=Minuss<p,t,f>;if<p=="0"> {p=s.substr<0,size>;s.erase<0,size>;if<isZero<p>> {p="0";break; } }else {p+=s.substr<0,1>;s.erase<0,1>; } }if<p=="0">p=s;elsep+=s;if<isZero<p>>p="0";while<Compare<p,t>>=0>p=Minuss<p,t,f>; }returnp;}整數(shù)乘法std::stringBigInteger::Multiply<std::stringlbs,std::stringrbs>{int*g_lbs;int*g_rbs;int*g_result;charbuffer[10];intlenLbs=lbs.length<>;intlenRbs=rbs.length<>;intsizeLbs=lenLbs%4==0?lenLbs/4:lenLbs/4+1;intsizeRbs=lenRbs%4==0?lenRbs/4:lenRbs/4+1;g_lbs=newint[sizeLbs+1];g_rbs=newint[sizeRbs+1];inti,j;memset<g_lbs,0,sizeof<int>*<sizeLbs+1>>;memset<g_rbs,0,sizeof<int>*<sizeRbs+1>>;std::stringstr;intcount=1;while<lbs.length<>>=4> {str=lbs.substr<lbs.length<>-4>;lbs.erase<lbs.length<>-4>;g_lbs[count]=atoi<str.c_str<>>; ++count; }if<!lbs.empty<>> {str=lbs;lbs.clear<>;g_lbs[count]=atoi<str.c_str<>>; }count=1;while<rbs.length<>>=4> {str=rbs.substr<rbs.length<>-4>;rbs.erase<rbs.length<>-4>;g_rbs[count]=atoi<str.c_str<>>; ++count; }if<!rbs.empty<>> {str=rbs;rbs.clear<>;g_rbs[count]=atoi<str.c_str<>>; }g_result=newint[sizeLbs*sizeRbs+2];memset<g_result,0,sizeof<int>*<sizeLbs*sizeRbs+2>>;for<i=1;i<=sizeLbs;++i> {for<j=1;j<=sizeRbs;++j> {g_result[i+j-1]+=g_lbs[i]*g_rbs[j];g_result[i+j]+=g_result[i+j-1]/10000;g_result[i+j-1]=g_result[i+j-1]%10000; } }std::stringret;i=sizeLbs*sizeRbs+1;while<!g_result[i]> { --i;if<i==0> {ret="0";gotoleave; } }sprintf<buffer,"%d",g_result[i--]>;ret.append<buffer>;for<j=i;j>=1;--j> {if<g_result[j]<1000>ret.append<"0">;if<g_result[j]<100>ret.append<"0">;if<g_result[j]<10>ret.append<"0">;sprintf<buffer,"%d",g_result[j]>;ret.append<buffer>; }leave:delete[]g_lbs;delete[]g_rbs;delete[]g_result;returnret;}整數(shù)加法std::stringBigInteger::Add<std::stringlbs,std::stringrbs>{int*g_lbs;int*g_rbs;int*g_result;charbuffer[10];intlenLbs=lbs.length<>;intlenRbs=rbs.length<>;if<lenLbs<lenRbs> {std::swap<lbs,rbs>;std::swap<lenLbs,lenRbs>; }intsizeLbs=lenLbs%4==0?lenLbs/4:lenLbs/4+1;intsizeRbs=lenRbs%4==0?lenRbs/4:lenRbs/4+1;g_lbs=newint[sizeLbs];g_rbs=newint[sizeRbs];inti,j;memset<g_lbs,0,sizeof<int>*sizeLbs>;memset<g_rbs,0,sizeof<int>*sizeRbs>;std::stringstr;intcount=0;while<lbs.length<>>=4> {str=lbs.substr<lbs.length<>-4>;lbs.erase<lbs.length<>-4>;g_lbs[count]=atoi<str.c_str<>>; ++count; }if<!lbs.empty<>> {str=lbs;lbs.clear<>;g_lbs[count]=atoi<str.c_str<>>; }count=0;while<rbs.length<>>=4> {str=rbs.substr<rbs.length<>-4>;rbs.erase<rbs.length<>-4>;g_rbs[count]=atoi<str.c_str<>>; ++count; }if<!rbs.empty<>> {str=rbs;rbs.clear<>;g_rbs[count]=atoi<str.c_str<>>; }g_result=newint[sizeLbs+1];memset<g_result,0,sizeof<int>*<sizeLbs+1>>;for<j=0;j<sizeLbs;++j> {if<j<sizeRbs> {g_result[j]+=g_lbs[j]+g_rbs[j]; }else {g_result[j]+=g_lbs[j]; }g_result[j+1]+=g_result[j]/10000;g_result[j]%=10000; }std::stringret;i=sizeLbs;while<!g_result[i]> { --i;if<i==-1> {ret.append<"0">;gotoleave; } }sprintf<buffer,"%d",g_result[i--]>;ret.append<buffer>;for<j=i;j>=0;--j> {if<g_result[j]<1000>ret.append<"0">;if<g_result[j]<100>ret.append<"0">;if<g_result[j]<10>ret.append<"0">;sprintf<buffer,"%d",g_result[j]>;ret.append<buffer>; }leave:delete[]g_lbs;delete[]g_rbs;delete[]g_result;returnret;}帶符號加法BigIntegerBigInteger::signAdd<constBigInteger&l,constBigInteger&r>{BigIntegerret;if<l.m_sign==r.m_sign> {ret.m_sign=l.m_sign;ret.m_str=AddEx<l.m_str,r.m_str>; }else {boolf;if<Compare<l.m_str,r.m_str><0> {ret.m_str=MinusEx<r.m_str,l.m_str,f>;ret.m_sign=r.m_sign; }else {ret.m_str=MinusEx<l.m_str,r.m_str,f>;ret.m_sign=l.m_sign; } }if<ret.m_str=="0">ret.m_sign=true;returnret;}浮點(diǎn)乘法std::stringBigInteger::MultiplyEx<std::strings,std::stringt>{intdots;intdott;inti;std::stringans; {dots=0;for<i=s.size<>-1;i>=0;--i>if<s[i]=='.'>break;else ++dots;if<dots<s.size<>>s.erase<i,1>;elsedots=0;dott=0;for<i=t.size<>-1;i>=0;--i>if<t[i]=='.'>break;else ++dott;if<dott<t.size<>>t.erase<i,1>;elsedott=0;intdot=dots+dott;std::stringret=Multiply<s,t>;s.clear<>;t.clear<>;s=ret;if<s.size<>!=1> {if<dot!=0> {std::reverse<s.begin<>,s.end<>>;while<s[0]=='0'> {s.erase<0,1>; --dot; }std::reverse<s.begin<>,s.end<>>; } }elseif<s[0]=='0'>dot=0;intidx=s.size<>-dot;if<idx<0> {ans="0.";while<idx<0> {ans.push_back<'0'>; ++idx; }idx=-1; }for<i=0;i<s.size<>;++i> {if<i==idx> {if<i==0>ans.push_back<'0'>;ans.push_back<'.'>; }ans.push_back<s[i]>; } }returnans;}浮點(diǎn)加法std::stringBigInteger::AddEx<std::stringa,std::stringb>{std::stringah,ab;std::stringbh,bb;inti;intsize;std::stringans; {for<i=0;i<a.size<>;++i>if<a[i]=='.'>break;ah=a.substr<0,i>;if<i<a.size<>>ab=a.substr<i+1>;a.clear<>;for<i=0;i<b.size<>;++i>if<b[i]=='.'>break;bh=b.substr<0,i>;if<i<b.size<>>bb=b.substr<i+1>;b.clear<>;a=Add<ah,bh>;ah.clear<>;bh.clear<>;size=<ab.size<><bb.size<>?bb.size<>:ab.size<>>;if<ab.size<><size> {intn=size-ab.size<>;while<n-->ab.push_back<'0'>; }if<bb.size<><size> {intn=size-bb.size<>;while<n-->bb.push_back<'0'>; }b=Add<ab,bb>;ab.clear<>;bb.clear<>;if<b.size<>>size> {std::stringc;c.push_back<b[0]>;b.erase<0,1>;a=Add<a,c>; }elseif<b.size<><size> {intn=size-b.size<>;while<n-->b="0"+b; }std::reverse<b.begin<>,b.end<>>;while<!b.empty<>&&b[0]=='0'>b.erase<0,1>;std::reverse<b.begin<>,b.end<>>;ans=a;if<!b.empty<>>ans.push_back<'.'>;ans.append<b>; }returnans;}帶符號減法BigIntegerBigInteger::signMinuse<constBigInteger&l,constBigInteger&r>{BigIntegerret;if<l.m_sign&&r.m_sign>ret.m_str=MinusEx<l.m_str,r.m_str,ret.m_sign>;elseif<!l.m_sign&&!r.m_sign> {ret.m_str=MinusEx<l.m_str,r.m_str,ret.m_sign>;ret.m_sign=!ret.m_sign; }elseif<l.m_sign&&!r.m_sign> {ret.m_str=AddEx<l.m_str,r.m_str>;ret.m_sign=true; }else {ret.m_str=AddEx<l.m_str,r.m_str>;ret.m_sign=false; }if<ret.m_str=="0">ret.m_sign=true;returnret;}整數(shù)減法std::stringBigInteger::Minuss<std::stringlbs,std::stringrbs,bool&sign>{int*g_lbs;int*g_rbs;int*g_result;charbuffer[10];intlenLbs=lbs.length<>;intlenRbs=rbs.length<>;sign=true;if<lenLbs<lenRbs>sign=false;elseif<lenLbs==lenRbs> {sign=<lbs>=rbs>;if<!sign> {std::swap<lbs,rbs>;std::swap<lenLbs,lenRbs>; } }if<lenLbs<lenRbs> {std::swap<lbs,rbs>;std::swap<lenLbs,lenRbs>; }intsizeLbs=lenLbs%4==0?lenLbs/4:lenLbs/4+1;intsizeRbs=lenRbs%4==0?lenRbs/4:lenRbs/4+1;g_lbs=newint[sizeLbs];g_rbs=newint[sizeRbs];inti,j;memset<g_lbs,0,sizeof<int>*sizeLbs>;memset<g_rbs,0,sizeof<int>*sizeRbs>;std::stringstr;intcount=0;while<lbs.length<>>=4> {str=lbs.substr<lbs.length<>-4>;lbs.erase<lbs.length<>-4>;g_lbs[count]=atoi<str.c_str<>>; ++count; }if<!lbs.empty<>> {str=lbs;lbs.clear<>;g_lbs[count]=atoi<str.c_str<>>; }count=0;while<rbs.length<>>=4> {str=rbs.substr<rbs.length<>-4>;rbs.erase<rbs.length<>-4>;g_rbs[count]=atoi<str.c_str<>>; ++count; }if<!rbs.empty<>> {str=rbs;rbs.clear<>;g_rbs[count]=atoi<str.c_str<>>; }g_result=newint[sizeLbs+1];memset<g_result,0,sizeof<int>*<sizeLbs+1>>;for<j=0;j<sizeLbs;++j> {if<j<sizeRbs> {if<g_lbs[j]-g_rbs[j]<0> { --g_lbs[j+1];g_lbs[j]+=10000; }g_result[j]=g_lbs[j]-g_rbs[j]; }else {if<g_lbs[j]<0> { --g_lbs[j+1];g_lbs[j]+=10000; }g_result[j]=g_lbs[j]; } }std::stringret;i=sizeLbs;while<!g_result[i]> { --i;if<i==-1> {ret.append<"0">;gotoleave; } }sprintf<buffer,"%d",g_result[i--]>;ret.append<buffer>;for<j=i;j>=0;--j> {if<g_result[j]<1000>ret.append<"0">;if<g_result[j]<100>ret.append<"0">;if<g_result[j]<10>ret.append<"0">;sprintf<buffer,"%d",g_result[j]>;ret.append<buffer>; }leave:delete[]g_lbs;delete[]g_rbs;delete[]g_result;returnret;}浮點(diǎn)減法std::stringBigInteger::MinusEx<std::stringa,std::stringb,bool&sign>{std::stringah,ab;std::stringbh,bb;inti;intsize;std::stringans; {sign=true;if<Compare<a,b>==-1> {a.swap<b>;sign=false; }for<i=0;i<a.size<>;++i>if<a[i]=='.'>break;ah=a.substr<0,i>;if<i<a.size<>>ab=a.substr<i+1>;a.clear<>;for<i=0;i<b.size<>;++i>if<b[i]=='.'>break;bh=b.substr<0,i>;if<i<b.size<>>bb=b.substr<i+1>;b.clear<>;boolf;a=Minuss<ah,bh,f>;ah.clear<>;bh.clear<>;size=<ab.size<><bb.size<>?bb.size<>:ab.size<>>;if<ab.size<><size> {intn=size-ab.size<>;while<n-->ab.push_back<'0'>; }if<bb.size<><size> {intn=size-bb.size<>;while<n-->bb.push_back<'0'>; }if<ab<bb> {if<a!="0"> {a=Minuss<a,"1",f>;ab="1"+ab;b=Minuss<ab,bb,f>; }elseb=Minuss<ab,bb,f>; }elseb=Minuss<ab,bb,f>;ab.clear<>;bb.clear<>;if<b.size<><size> {intn=size-b.size<>;while<n-->b="0"+b; }std::reverse<b.begin<>,b.end<>>;while<!b.empty<>&&b[0]=='0'>b.erase<0,1>;std::reverse<b.begin<>,b.end<>>;ans=a;if<!b.empty<>>ans.push_back<'.'>;ans.append<b>; }returnans;}帶符號比較intBigInteger::signCompare<constBigInteger&a,constBigInteger&b>{if<a.m_sign&&b.m_sign>returnCompare<a.m_str,b.m_str>;elseif<!a.m_sign&&!b.m_sign> {intret=Compare<a.m_str,b.m_str>;if<ret!=0>ret=0-ret;returnret; }elsereturna.m_sign?a.m_sign:b.m_sign;}無符號比較intBigInteger::Compare<conststd::string&a,conststd::string&b>{std::stringah,ab;std::stringbh,bb;inti;for<i=0;i<a.size<>;++i>if<a[i]=='.'>break;ah=a.substr<0,i>;ab.clear<>;if<i<a.size<>>ab=a.substr<i+1>;for<i=0;i<b.size<>;++i>if<b[i]=='.'>break;bh=b.substr<0,i>;bb.clear<>;if<i<b.size<>>bb=b.substr<i+1>;if<ah.size<><bh.size<>>return-1;elseif<ah.size<>>bh.size<>>return1;else {if<ah<bh>return-1;elseif<ah>bh>return1;else {if<ab<bb>return-1;elseif<ab>bb>return1;elsereturn0; } }}無符號乘方std::stringBigInteger::pow<conststd::string&b,intn>{if<n==0>returnstd::string<"1">;if<n==1> {returnb; }else {if<n%2==0> {std::stringt=pow<b,n/2>;returnMultiplyEx<t,t>; }else {std::stringt=pow<b,n/2>;returnMultiplyEx<MultiplyEx<t,t>,b>; } }}帶符號乘方BigIntegerBigInteger::signPow<constBigInteger&x,intn>{BigIntegerret;ret.m_sign=true;if<!x.m_sign&&n%2!=0>ret.m_sign=false;ret.m_str=pow<x.m_str,n>;returnret;}使用方法std::cout<<"Inputanynumber:\n";BigIntegera,b;std::cin>>a>>b;std::cout<<"a*b="<<a*b<<std::endl;std::cout<<"a+b="<<a+b<<std::endl;std::cout<<"a-b="<<a-b<<std::endl;std::cout<<"Inputoneofnormalpositiveintegernumber:\n";intn;std::cin>>a>>n;std::cout<<"a^n="<<<a^n><<std::endl;std::cout<<"Allintegernumber:\n";std::cin>>a>>b;std::cout<<"a%b="<<<a%b><<std::endl;if<a<b>std::cout<<"alessb\n";elsestd::cout<<"anotlessb\n";if<a==b>std::cout<<"aequalb\n";elsestd::cout<<"anotequalb\n";高級數(shù)據(jù)結(jié)構(gòu)普通二叉搜素樹包含頭文件#include<stddef.h>定義//beginclassBinarySearchTreedefinition//template<typenameKey,typenameValue>classBinarySearchTree{private://二叉搜索樹節(jié)點(diǎn)類型structBSTnode {constKeym_key;//比較關(guān)鍵字Valuem_value;//映射類型BSTnode*m_left;//左子樹BSTnode*m_right;//右子樹BSTnode*m_parent;//雙親節(jié)點(diǎn)BSTnode<constKey&k,constValue&v>;//撤銷結(jié)構(gòu)voidDestroy<>;private: ~BSTnode<>;//保證只能在堆上創(chuàng)建對象 };//endofstructBSTnodepublic://二叉搜索樹訪問引用類型classNode {public:explicitNode<typenameBinarySearchTree<Key,Value>::BSTnode*target=NULL>;boolIsNull<>const;//判斷節(jié)點(diǎn)是否為空boolIsRoot<>const;//判斷節(jié)點(diǎn)是否為根NodeGetLeft<>const;//返回左子樹NodeGetRight<>const;//返回右子樹NodeGetParent<>const;//返回父節(jié)點(diǎn)voidMoveLeft<>;//移動到左子樹voidMoveRight<>;//移動到右子樹voidMoveParent<>;//移動到雙親constKey&GetKey<>const;//返回當(dāng)前節(jié)點(diǎn)的鍵值voidSetValue<constValue&v>;//設(shè)