C/C++实现的数据结构与算法标准代码库

3星 · 超过75%的资源需积分: 9 182 浏览量更新于2024-08-02 1 收藏 389KB PDF 举报

"该资源是一个综合性的C/C++代码库，包含了各种数据结构和算法的实现，涵盖了高精度计算、堆、树结构、排序算法、图理论与网络算法等多个领域，旨在提供一个标准的参考代码集。" 在数据结构和算法的实现中，这个标程库提供了多种重要的数据结构和算法的C/C++代码示例： 1. **高精度计算**：包括C语言和C++语言实现的高精度运算，支持大整数的加减乘除，这对于处理超出普通整型范围的计算是必要的。 2. **分数类(FractionClass)**：实现了分数的表示和操作，如加、减、乘、除以及比较，对于处理有理数计算非常有用。 3. **二叉堆(BinaryHeap)**：二叉堆是一种重要的优先队列实现，可以用于实现堆排序或作为Dijkstra算法中的最小优先队列。 4. **胜者树(WinnerTree)**和**数字树(DigitalTree)**：这两种数据结构常用于动态维护区间最值问题，例如在动态规划和在线算法中。 5. **线段树(SegmentTree)**：线段树能高效地处理区间查询和修改操作，对于解决区间加减、求和等问题非常有效。 6. **并查集(Union-Find Set)**：并查集是一种用于处理集合合并与查询的高效数据结构，常用于处理连通性问题。 7. **快速排序(QuickSort)**和**归并排序(MergeSort)**：快速排序是平均时间复杂度为O(n log n)的原地排序算法，归并排序则是一种稳定的排序算法，适用于大数据量排序。 8. **基数排序(RadixSort)**：基数排序是一种非比较型整数排序算法，适用于大量整数的排序。 9. **选择第k小元素(SelectKthSmallestElement)**：这种算法能够在未排序的数组中找到第k小的元素，通常用在中位数计算等问题中。 10. **KMP算法**：KMP是一种高效的字符串匹配算法，避免了不必要的回溯，提高了搜索效率。 11. **后缀排序(SuffixSort)**：后缀排序用于对字符串的后缀进行排序，是构建后缀数组的基础，广泛应用于文本处理和模式匹配。在图理论和网络算法方面，库还涵盖了以下内容： 1. **单源最短路径(SSSP)**：包括Dijkstra算法和Bellman-Ford算法，用于找出图中从特定顶点到其他所有顶点的最短路径。 2. **最小生成树(MST)**：Kruskal算法用于构建最小生成树，连接图中的所有顶点且边权重之和最小。 3. **最大匹配**：包括在二分图上的最大匹配算法，以及带有成本的最大完美匹配算法。 4. **最大流(MaximumFlow)**：Ford-Fulkson算法用于寻找图中的最大流，同时给出了矩阵形式和链式前向星两种实现。 5. **最小费用最大流(MinimumCostMaximumFlow)**：同样提供了矩阵和链式前向星两种方法来求解带有费用的网络流问题。 6. **识别圈图(ChordalGraph)**：这部分涉及到图的结构分析，帮助识别特定类型的图。这个标程库不仅提供了具体的代码实现，还可能包含每个算法的详细解释和应用示例，对于学习和理解数据结构和算法是极有价值的资源。

Chapter 2

Graph Theory and Network Algorithms

2.1 SSSP — Dijkstra + Binary Heap

const i nt i n f = 1000 0 000 0 0;

in t n ,m, num, len , next [maxm ] , ev [maxm] , ew [maxm ] ;

in t val ue [ maxn ] ,mk[ maxn ] , nbs [ maxn ] , ps [ maxn ] , heap [ maxn ] ;

void update ( i nt r )

{

in t q=ps [ r ] , p=q>>1;

while ( p && val u e [ heap [ p]] > v al ue [ r ] ) {

ps [ heap [ p ]] = q ; heap [ q]=heap [ p ] ;

q=p ; p=q>>1;

}

heap [ q]= r ; ps [ r ]=q ;

}

in t getmin ( )

{

in t r e t=heap [ 1 ] , p=1,q=2, r=heap [ len −−];

while ( q<=le n ) {

i f ( q<l e n && val u e [ heap [ q+1]]< val ue [ heap [ q ] ] ) q++;

i f ( va lue [ heap [ q ]] < va lue [ r ] ) {

ps [ heap [ q ]]= p ; heap [ p]=heap [ q ] ;

p=q ; q=p<<1;

} e l s e break ;

}

heap [ p]= r ; ps [ r ]=p ;

return r e t ;

}

void d i j k s t r a ( i nt s r c , int ds t )

{

in t i , j , u , v ;

fo r ( i =1; i<=n ; i ++) {va l ue [ i ]= i n f ; mk[ i ]= ps [ i ] = 0 ; };

va l ue [ s r c ] = 0 ; heap [ l e n =1]= s r c ; ps [ s r c ]= 1;

while ( ! mk [ ds t ] ) {

i f ( l e n ==0) return ;

u=getmin ( ) ; mk [ u ]= 1 ;

fo r ( j=nbs [ u ] ; j ; j=next [ j ] ) {

v=ev [ j ] ; i f ( ! mk[ v ] && va lu e [ u]+ew [ j ]< val ue [ v ] ) {

i f ( ps [ v ]==0){ heap[++l e n ]=v ; ps [ v]= l e n ; }

va l ue [ v]= va lue [ u]+ew [ j ] ; update ( v ) ;

}

2.4 Minimum Directed Spanning Tree

in t n , g [ maxn ] [ maxn ] , used [ maxn ] , pa s s [ maxn ] , eg [ maxn ] , more , queue [ maxn ] ;

void combine ( i n t id , i n t & sum ) {

in t t o t = 0 , from , i , j , k ;

fo r ( ; i d !=0&&! pass [ id ] ; i d=eg [ i d ] ) { queue [ t o t++]=i d ; pass [ id ]= 1 ;}

fo r ( from =0; from<t o t&&queue [ from ] != id ; from ++);

i f ( from==to t ) return ; more = 1 ;

fo r ( i=from ; i<t o t ; i ++) {

sum+=g [ eg [ queue [ i ] ] ] [ queue [ i ] ] ;

i f ( i !=from ) { used [ queue [ i ] ] = 1 ;

fo r ( j = 1 ; j <= n ; j ++) i f ( ! used [ j ] )

i f ( g [ queue [ i ] ] [ j ]<g [ id ] [ j ] ) g [ i d ] [ j ]=g [ queue [ i ] ] [ j ] ;

}

fo r ( i =1; i<=n ; i ++ ) i f ( ! used [ i ]&& i != id ) {

fo r ( j=from ; j<t o t ; j ++){ k=queue [ j ] ;

i f ( g [ i ] [ id ]>g [ i ] [ k]−g [ eg [ k ] ] [ k ] ) g [ i ] [ i d ]=g [ i ] [ k]−g [ eg [ k ] ] [ k ] ;

}

in t msdt ( in t r oo t ) { // r e t u r n th e t o t a l l e n g t h o f MDST

in t i , j , k , sum = 0 ;

memset ( used , 0 , s i z e o f ( used ) ) ;

fo r ( more =1; more ; ) { more = 0 ;

memset ( eg , 0 , s i z e o f ( eg ) ) ;

fo r ( i = 1 ; i <= n ; i ++) i f ( ! used [ i ] && i ! = r o o t ) {

fo r ( j = 1 , k = 0 ; j <= n ; j ++) i f ( ! used [ j ] && i ! = j )

i f ( k = = 0 || g [ j ] [ i ] < g [ k ] [ i ] ) k = j ;

eg [ i ] = k ;

} memset ( pass , 0 , s i z e o f ( pa s s ) ) ;

fo r ( i =1; i<=n ; i ++) i f ( ! used [ i ]&&! p ass [ i ]&& i != ro o t ) combine ( i , sum ) ;

}

fo r ( i =1; i<=n ; i ++) i f ( ! used [ i ] && i != r oo t ) sum+=g [ eg [ i ] ] [ i ] ;

return sum ;

}

2.5 Maximum Matching on Bipartite Gr aph

in t nx , ny ,m, g [MAXN] [MAXN] , sy [ MAXN] , cx [MAXN] , cy [MAXN] ;

in t path ( i n t u )

{

fo r ( in t v=1;v<=ny ; v++) i f ( g [ u ] [ v ] & & ! sy [ v ] ) { sy [ v ] =1;

i f ( ! cy [ v ] | | path ( cy [ v ] ) ) { cx [ u]=v ; cy [ v]=u ; return 1 ; }

} return 0 ;

}

in t MaximumMatch( )

{

in t i , r e t =0;

memset ( cx , 0 , s i z e o f ( cx ) ) ; memset ( cy , 0 , s i z e o f ( cy ) ) ;

fo r ( i =1; i<=nx ; i ++) i f ( ! cx [ i ] ) {memset ( sy , 0 , si z e o f ( sy ) ) ; r e t+=path ( i ) ; }

return r e t ;

}

2.6 Maximum Cost Perfect Matching on Bipartite Graph

in t cx [ maxn ] , cy [ maxn ] , sx [ maxn ] , sy [ maxn ] , lx [ maxn ] , l y [ maxn ] ;

in t nx , ny , match , g [ maxn ] [ maxn ] ;

in t path ( i n t u )

{

sx [ u ] = 1 ; fo r ( in t v=1;v<=ny ; v++) i f ( g [ u ] [ v]== l x [ u]+ l y [ v ] && ! sy [ v ] ) {

sy [ v ] = 1 ; i f ( ! cy [ v ] | | path ( cy [ v ] ) ) { cx [ u]=v ; cy [ v]=u ; return 1 ; }

} return 0 ;

}

void K uhnMunkres ( )

{

in t i , j , u , min ;

memset ( lx , 0 , s i z e o f ( l x ) ) ; me mset ( ly , 0 , s i z e o f ( l y ) ) ;

memset ( cx , 0 , s i z e o f ( cx ) ) ; memse t ( cy , 0 , s i z e o f ( cy ) ) ;

fo r ( i =1; i<=nx ; i ++) for ( j =1; j<=ny ; j ++) i f ( l x [ i ]<g [ i ] [ j ] ) l x [ i ]=g [ i ] [ j ] ;

fo r ( match =0 , u =1 ; u<=nx ; u++) i f ( ! cx [ u ] ) {

memset ( sx , 0 , si z e o f ( sx ) ) ; memset ( sy , 0 , s i z e o f ( sy ) ) ;

while ( ! path ( u )) {

min=0 x 3 f f f f f f f ;

fo r ( i =1; i<=nx ; i ++) i f ( sx [ i ] ) for ( j =1; j<=ny ; j ++) i f ( ! sy [ j ] )

i f ( lx [ i ]+ l y [ j ]−g [ i ] [ j ]<min ) min=l x [ i ]+ l y [ j ]−g [ i ] [ j ] ;

fo r ( i =1; i<=nx ; i ++) i f ( sx [ i ] ) { l x [ i ]−=min ; sx [ i ] = 0 ; }

fo r ( j =1; j<=ny ; j ++) i f ( sy [ j ] ) { l y [ j ]+=min ; sy [ j ] = 0 ; }

};

}

2.7 Maximum Matching on General Graph

// t o t a l i s t h e maximum c a r d i n a l i t y , p [ 1 . . n ] means a match : i <−> p [ i ]

in t g [ maxn ] [ maxn ] , p [ maxn ] , l [ maxn ] [ 3 ] , n , t o t a l , s t a t u s [ maxn ] , v i s i t e d [ maxn ] ;

void s o l v e ( )

{

in t i , j , k , p a ss ;

memset ( p , 0 , s i z e o f ( p ) ) ;

do { i =0;

do { i f ( p[++ i ] ) pass =0; e ls e {

memset ( l , 0 , s i z e o f ( l ) ) ;

l [ i ] [ 2 ] = 0 x f f ; p ass=path ( i ) ;

fo r ( j =1; j<=n ; j ++) for ( k=1;k<=n ; k++)

i f ( g [ j ] [ k ] < 0) g [ j ] [ k ]=−g [ j ] [ k ] ;

};

}while ( i !=n && ! p a ss ) ;

i f ( p a ss ) t o t a l +=2;

}while ( i !=n && t o t a l !=n ) ;

}

void upgrade ( int r )

{

in t j=r , i=l [ r ] [ 1 ] ;

fo r ( p [ i ]= j ; l [ i ] [ 2 ] < 0 x f f ; ) {

p [ j ]= i ; j=l [ i ] [ 2 ] ; i=l [ j ] [ 1 ] ; p [ i ]= j ;

} p [ j ]= i ;

}

剩余86页未读，继续阅读

meko耗子

粉丝: 0
资源: 2

C/C++实现的数据结构与算法标准代码库

C/C++实现数据结构与算法详解

C/C++实现常用数据结构与算法教程

C/C++实现学生姓名排序的数据结构程序

数据结构与算法 c++实现 //删除顺序递增表中的重复元素 //对单链表实现就地逆置 //删除递增单链表中的重复元素

图解算法数据结构配套代码：C/C++/JAVA/Python实现

数据结构及离散数学的huffman算法c/c++实现

一些经典算法的c/c++实现

AES算法实现（C/C++语言）

算法导论第三版各种排序算法的c/c++实现

几种常用的排序算法的C/C++实现

最新资源