数据结构经典代码（ACM）高精运算: typedef struct //为方便处理,用结构体 {

文件名称: 数据结构经典代码（ACM）

所属分类: C

开发工具:

文件大小: 85kb

下载次数: 0

上传时间: 2010-05-08

提供者: zhuying*******

下载 (85kb)

不能下载？报告错误

详细说明：高精运算: typedef struct //为方便处理,用结构体 { int len ; long num [1024] ; } HNum ; //万进制高精加法, 注意输出高位补0, printf ("%04d" …) ; void HPlus (HNum &a, HNum &b, HNum &c) { int i, len = a.len > b.len ? a.len : b.len ; memset (&c, 0, sizeof (HNum)) ; for (i = 1 ; i <= len ; i ++) { c.num [i] += a.num [i] + b.num [i] ; if (c.num [i] >= BASE) { c.num [i+1] += c.num [i] / BASE ; c.num [i] %= BASE ; } } c.len = len ; while (c.num [c.len+1] > 0) c.len ++ ; } //万进制高精乘法 void HMul (HNum &a, HNum &b, HNum &c) { int i, j ; memset (&c, 0, sizeof (HNum)) ; for (i = 1 ; i <= a.len ; i ++) for (j = 1 ; j <= b.len ; j ++) { c.num [i+j-1] += a.num [i] * b.num [j] ; //注意+号 if (c.num [i+j-1] >= BASE) { c.num [i+j] += c.num [i+j-1] / BASE ; //注意+号 c.num [i+j-1] %= BASE ; } } c.len = a.len + b.len - 1 ; while (c.num [c.len+1] > 0) // c.len ++ ; } //万进制高精减法 void HSub (HNum &a, HNum &b, HNum &c) { int i, len = a.len ; //保证a >= b memset (&c, 0, sizeof (HNum)) ; for (i = 1 ; i <= len ; i ++) { c.num [i] += a.num [i] - b.num [i] ; //注意+号 if (c.num [i] < 0) { c.num [i+1] -= 1 ; //注意-号 c.num [i] += BASE ; } } c.len = len ; while (c.len > 0 && c.num [c.len] == 0) c.len -- ; } //万进制高精减法, 直接就 long long…. -------------------------------------------------------------------------------- //Fibonacci, Fibo [i] = Fibo [i-1] + Fibo [i-2], Fibo [3] = 3 ; // Catalan数列S[n] = C(2n,n)/(n+1) long Catalan (long n) { long i, x, y ; x = y = 1 ; for (i = 2 ; i <= n ; i ++) x *= i ; for (i = n ; i <= 2*n ; i ++) y *= i ; return y/x/(n + 1) ; } //最小公倍数 long lcm (long a, long b) { return a*b/gdc (a, b) ; } //最大公约数, 辗转相除法 long gdc (long a, long b) { return (a%b == 0)? b : gdc (b, a%b) ; } ------------------------------------------------------------------------------------------------------------ //堆操作 void In (HeapDT dt) //进堆 { int i ; list [++ len] = dt ; i = len ; while (i > 1) //向上调整 { if (list [i].w < list [i/2].w) Swap (i, i/2) ; else break ; i /= 2 ; } } HeapDT Out () //出堆 { HeapDT ret = list [1] ; Swap (1, len) ; //NOTE: 最重要的一步, 最后(最大)一个元素与第一个元素交换 len -- ; //堆长度减1 int i, pa = 1 ; for (i = pa * 2 ; i <= len ; i *= 2) //向下调整 { if (i < len && list [i+1].w < list [i].w) i ++ ; if (list [i].w < list [pa].w) Swap (pa, i) ; else break ; pa = i ; } return ret ; } ------------------------------------------------------------------------------------------------------------ //二分查找, 注意等号 while (low < high) { mid = (low + high) >> 1 ; if (strcmp (spname, name [mid]) <= 0) high = mid ; else low = mid + 1 ; } ------------------------------------------------------------------------------------------------------------ //快排 void QSort (int low, int high) { int l, r ; Milkcow p = cow [low] ; l = low, r = high ; while (l < r) { while (l < r && cow [r].price >= p.price) r -- ; cow [l] = cow [r] ; while (l < r && cow [l].price <= p.price) l ++ ; cow [r] = cow [l] ; } cow [l] = p ; if (l-1 > low) QSort (low, l-1) ; if (l+1 < high) QSort (l+1, high) ; } -------------------------------------------------------------------------------------------- //优化并查集 int FindSet (int i) { if (Parent [i] != i) //状态压缩 Parent [i] = FindSet (Parent [i]) ; return Parent [i] ; } void UnionSet (int a, int b) { int i, j ; i = FindSet (a) ; j = FindSet (b) ; if (i != j) if (Rank [i] > Rank [j]) //启发式合并:让深度较小的树成为深度较大的树的子树 Parent [j] = i ; else { Parent [i] = j ; if (Rank [i] == Rank [j]) Rank [j] ++ ; } } ------------------------------------------------------------------------------------------- 图论: //MST double Kruscal () { int i, k = 0 ; double s = 0 ; for (i = 0 ; i <= n ; i ++) Parent [i] = i ; for (i = 0 ; i < m && k < n-1; i ++) //m为总边数 { if (FindSet (Edge [i].a) != FindSet (Edge [i].b)) { s += Edge [i].v ; if (s > S) //是否超出范围 return 0 ; UnionSet (Edge [i].a, Edge [i].b) ; k ++ ; //记录合并的边数 } } if (k != n-1) return 0 ; ...展开收缩

(系统自动生成,下载前可以参看下载内容)