1、ACM程序設計常用算法與 數據結構參考 Tomsdinary目錄前言6排序算法7插入排序7選擇排序9冒泡排序10希爾排序11隨機化快速排序13歸并排序16堆排序18大整數處理21包含頭文件21定義21實現23流輸出23流輸入23賦值23轉換函數24規(guī)范化符號化25帶符號乘法26無符號取模26整數乘法27整數加法29帶符號加法31浮點乘法32浮點加法33帶符號減法35整數減法36浮點減法38帶符號比較40無符號比較40無符號乘方42帶符號乘方42使用方法42高級數據結構43普通二叉搜素樹43包含頭文件43定義43實現46刪樹49插入元素到樹49復制樹52求樹的高度55求葉子的個數56刪除元素56

2、使用方法58基本線段樹模式59基本并查集模式61散列實現的一種方式參考62定義與實現62使用方法71堆71包含頭文件71定義與實現71使用方法74圖相關算法74圖的深度優(yōu)先和廣度優(yōu)先算法舉例74無向圖最小生成樹的Kruskal算法舉例77無向圖最小生成樹的Prim算法舉例79有向圖的單源最短路徑Dijkstra算法舉例81有向圖的多源最短路徑Floyd算法舉例82拓撲排序舉例84AOE網的算法舉例86求圖的一個中心算法舉例91求圖的P個中心算法舉例93SPFA算法舉例98割頂和塊的算法舉例100計算幾何算法103向量模103向量點積104向量叉積104左右判斷104相交判斷104正規(guī)相交交點1

3、05判斷多邊形凸105任意多變形面積106凸包問題的快包實現舉例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()117genera

4、te_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()12

5、5random_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_uni

6、on()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+語言可用頭文件138138138138138138139139139139139139139139140140140140140140140141141141141141141141

7、141142142142142142142142142143143143143143143143143143144144144144144144前言 如今的程序設計已不再是個人英雄時代了，程序的設計和開發(fā)實施需要靠團隊成員的積極配合和合作。軟件技術在當今時代已不是信息技術競爭核心，對于技術知識的獲取變得不再重要。當今IT競爭，靠的是先進的觀念，有效的溝通和合作，靠的是高瞻遠矚的預見能力，靠的是個人的想法而絕不是技能。當然掌握好眾多技術是實現我們獨特創(chuàng)意的途徑，但絕不是我們可以屹立IT界的根本法寶。 隨著互聯網發(fā)展的不斷深入，技術知識的獲取不再成為問題。程序員不能單靠通曉某一核心技術而獲得核心競

8、爭力。當今的IT界知識分享，知識交流，知識開放是主旋律，凡是開放的平臺，開放的個人，開放的公司才是真正擁有競爭力的，凡是那些封閉的平臺，封閉的個人，封閉的公司其發(fā)展的道路終會是艱難的。而這種開放的態(tài)度在中國程序員中更應該得到普及與遵守。其根本在于中國程序員中的高手充其量也只是一個高級用戶，真正的技術掌握在技術公司那里。所以為什么還有保留一些使用技巧呢。不開放不分享不合作，優(yōu)秀的程序員中會淪為平庸的人。 基于以上思考和論斷，我將自己三年在算法設計和數據結構學習過程中可供借鑒和參考使用的代碼總結如下。一方面作為我們隊參加ACM的內部參考資料，另一方面分享出來供后來者學習參考?；蛟S對諸位會有點幫助。

9、同時也請您記住和接受以上觀點，在一個分享交流的環(huán)境你，你的技術進步會更加迅速。也希望那些有好代碼，好思想的高手將自己的智慧分享出來。整理出來。這不僅有利于個人學習總結，更有利于我們懷化學院ACM隊伍健康發(fā)展。排序算法插入排序/*函數名： InsertionSort功能： 插入排序模板參數說明：T必須支持小于操作參數說明： data待排序數組, size待排序數組大小前置條件： data!=NULL, size0后置條件： data按非降序排列用法： int arr=10,9,8,4,5,7,6,3,1,4; InsertionSort(arr, 10);*/template void Inse

10、rtionSort (T data, int size)int i,j; T temp;for (i=1; i0 & temp0后置條件： data按f排列用法： bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;InsertionSort(arr, 10, cmp);*/template void InsertionSort (T data, int size, Func f)int i,j; T temp;for (i=1; i0 & f(temp,dataj-1); -j)dataj=dataj-1;dataj=

11、temp;選擇排序/*函數名： SelectionSort功能： 選擇排序模板參數說明：T必須支持小于操作參數說明： data待排序數組, size待排序數組大小前置條件： data!=NULL, size0后置條件： data按非降序排列用法： #include int arr=10,9,8,4,5,7,6,3,1,4;SelectionSort(arr, 10);*/template void SelectionSort (T data, int size)int i,j,k; for (i=0; isize-1; +i)k=i;for (j=i+1; jsize; +j)if (data

12、j0后置條件： data按f排列用法： #include int arr=10,9,8,4,5,7,6,3,1,4;bool cmp(int a, int b) return ab; SelectionSort(arr, 10, cmp);*/template void SelectionSort (T data, int size, Func f)int i,j,k; for (i=0; isize-1; +i)k=i;for (j=i+1; j0后置條件： data按非降序排列用法： #include int arr=10,9,8,4,5,7,6,3,1,4;BubbleSort(arr,

13、 10);*/template void BubbleSort (T data, int size)int i,j;for (i=0; ii; -j)if (dataj0后置條件： data按f序排列用法： #include bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;BubbleSort(arr, 10, cmp);*/template void BubbleSort (T data, int size, Func f)int i,j;for (i=0; ii; -j)if (f(dataj,dataj-1)s

14、td:swap(dataj, dataj-1);希爾排序/*函數名： ShellSort功能： 希爾排序模板參數說明：T必須支持小于操作參數說明： data待排序數組, size待排序數組大小前置條件： data!=NULL, size0后置條件： data按非降序序排列用法： int arr=10,9,8,4,5,7,6,3,1,4;ShellSort(arr, 10);*/template void ShellSort (T data, int size)int i, j, hCnt, h;int array20, k;T temp;for (h=1, i=0; h=0; -i)h=arr

15、ayi;for (hCnt=h; hCnt2*h; +hCnt) for (j=hCnt; j=0 & temp0后置條件： data按f排列用法： bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;ShellSort(arr, 10, cmp);*/template void ShellSort (T data, int size, Func f)int i, j, hCnt, h;int array20, k;T temp;for (h=1, i=0; h=0; -i)h=arrayi;for (hCnt=h; h

16、Cnt2*h; +hCnt) for (j=hCnt; j=0 & f(temp,datak-h)datak=datak-h;k-=h;datak=temp;j+=h;隨機化快速排序/*函數名： quick_sort功能： 快速排序輔助過程*/template void quick_sort (T data, int frist, int last)int lower=frist+1;int upper=last;int t=rand()%(last-frist)+frist;std:swap(datafrist, datat);T& bound=datafrist;while (lower=

17、upper)while (datalowerbound)+lower;while (bounddataupper)-upper;if (lowerupper)std:swap(datalower, dataupper);+lower;-upper;else+lower;std:swap(dataupper, datafrist);if (fristupper-1)quick_sort(data, frist, upper-1);if (upper+10后置條件： data按f排列用法： #include #include #include int arr=10,9,8,4,5,7,6,3,1,

18、4;QuickSort(arr, 10);*/template void QuickSort (T data, int size)int i, max;if (size2)return;for (i=1, max=0; isize; +i) if (datamaxdatai)max=i;std:swap(datasize-1, datamax);srand(time(0);quick_sort(data, 0, size-2);/*函數名： quick_sort功能： 快速排序輔助過程*/template void quick_sort (T data, int frist, int last

19、, Func& f)int lower=frist+1;int upper=last;int t=rand()%(last-frist)+frist;std:swap(datafrist, datat);T& bound=datafrist;while (lower=upper)while (f(datalower,bound)+lower;while (f(bound,dataupper)-upper;if (lowerupper)std:swap(datalower, dataupper);+lower;-upper;else+lower;std:swap(dataupper, dataf

20、rist);if (fristupper-1)quick_sort(data, frist, upper-1, f);if (upper+10后置條件： data按f排列用法： #include #include #include bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;QuickSort(arr, 10, cmp);*/template void QuickSort (T data, int size, Func f)int i, max;if (size2)return;for (i=1, max=0;

21、i0后置條件： data按非降序排列用法： #include int arr=10,9,8,4,5,7,6,3,1,4;MergeSort(arr, 10);*/template void MergeSort (T data, int size)if ( size1 )/預處理int mid=size/2;int numOfleft=mid;int numOfright=size-mid;T* left=new TnumOfleft;T* right=new TnumOfright;/分std:copy(data, data+numOfleft, left);std:copy(data+num

22、Ofleft, data+size, right);MergeSort(left, numOfleft);MergeSort(right, numOfright);/合std:merge(left, left+numOfleft, right, right+numOfright, data);/清理delete left;delete right;/*函數名： MergeSort功能： 歸并排序模板參數說明：T元素類型, Func函數對象或指針參數說明： data待排序數組, size待排序數組大小,f函數對象或指針前置條件： data!=NULL, size0后置條件： data按f排列用法

23、： #include bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;MergeSort(arr, 10，cmp);*/template void MergeSort (T data, int size, Func f)if ( size1 )int mid=size/2;int numOfleft=mid;int numOfright=size-mid;T* left=new TnumOfleft;T* right=new TnumOfright;std:copy(data, data+numOfleft, lef

24、t);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;堆排序/*函數名： heap_down功能： 堆排序輔助過程*/template void heap_down (T data, int i, const int& size)int p=i*2+1;w

25、hile ( psize )if ( p+1size )if ( datapdatap+1 )+p;if ( datai0后置條件： data按非降序排列用法： #include int arr=10,9,8,4,5,7,6,3,1,4;MergeSort(arr, 10);*/template void HeapSort (T data, int size)int i;for (i=(size-1)/2; i=0; -i)heap_down(data, i, size);for (i=size-1; i0; -i)std:swap(data0, datai);heap_down(data,

26、0, i);/*函數名： heap_down功能： 堆排序輔助過程*/template void heap_down (T data, int i, const int& size, Func& f)int p=i*2+1;while ( psize )if ( p+10后置條件： data按f排列用法： #include bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;HeapSort(arr, 10，cmp);*/template void HeapSort (T data, int size, Func f)i

27、nt i;for (i=(size-1)/2; i=0; -i)heap_down(data, i, size, f);for (i=size-1; i0; -i)std:swap(data0, datai);heap_down(data, 0, i, f);大整數處理包含頭文件#include #include #include #include 定義/大整數類class BigIntegerpublic:/默認構造explicit BigInteger(const std:string& str=0) : m_str(str) Normal();/接受雙精度浮點構造explicit Big

28、Integer(double d)m_str=ToString(d);Normal();/接受單精度浮點構造explicit BigInteger(float f)m_str=ToString(f);Normal();/接受整數構造explicit BigInteger(int i)m_str=ToString(i);Normal();/輸入流運算friend std:ostream& operator (std:istream& in, BigInteger& big);/賦值BigInteger& operator= (const BigInteger& rbs);BigInteger&

29、operator= (double d);BigInteger& operator= (float f);BigInteger& operator= (int i);/高精度乘法BigInteger operator* (const BigInteger& other) return signMultiply(*this, other);/高精度加法BigInteger operator +(const BigInteger& other) return signAdd(*this, other);/高精度減法BigInteger operator- (const BigInteger& ot

30、her) return signMinuse(*this, other);/高精度乘方BigInteger operator (int n) return BigInteger(pow(m_str, n);/高精度正數取模BigInteger operator% (const BigInteger& other);/比較bool operator (const BigInteger& rbs) return signCompare(*this, rbs)=-1; bool operator= (const BigInteger& rbs) return signCompare(*this, r

31、bs)=0; /轉換成字符串std:string ToString();private:/規(guī)范化void Normal();void Unnormal();/轉換std:string ToString(int n);std:string ToString(double n);std:string ToString(float n);/有符號高精度運算及其比較BigInteger signMultiply(const BigInteger& l, const BigInteger& r);BigInteger signAdd(const BigInteger& l, const BigInteg

32、er& r);BigInteger signMinuse(const BigInteger& l, const BigInteger& r);BigInteger signPow(const BigInteger& x, int n);int signCompare(const BigInteger& a, const BigInteger& b);/無符號比較int Compare(const std:string& a, const std:string& b);/無符號高精度運算std:string MultiplyEx (std:string s, std:string t);std:

33、string Multiply (std:string lbs, std:string rbs);std:string AddEx(std:string a, std:string b);std:string Add(std:string lbs, std:string rbs);std:string MinusEx(std:string a, std:string b, bool& sign);std:string Minuss (std:string lbs, std:string rbs, bool& sign);std:string pow(const std:string& b, i

34、nt n);std:string mod(std:string s, const std:string& t);/判斷s是否全為零bool isZero(const std:string& s);private:bool m_sign; /符號std:string m_str; /內部字符串;實現流輸出std:ostream& operator (std:ostream& out, const BigInteger& big)if (!big.m_sign)out.put(-);out (std:istream& in, BigInteger& big)inbig.m_str;big.Normal();return in;賦值BigInteger& BigInteger:operator= (const BigInteger& rbs)if ( this!=&rbs )m_str=rbs.m_str;m_sign=rbs.m_sign;return *this;BigInteger& BigInteger:operator= (double d)m_str=ToString(d);Normal();return *this;BigInteger& BigInteger:operator= (float f)m_str=ToStrin