//进制转换函数，实现任意进制互转，将data转为N进制 num *BaseConversion(num *data, int N) { // temp存储转化结果 num *temp = InitNum(); int base = data->base; temp->base = N; temp->neg = data->neg; //符号位不变
//高精度加法器，严格规定x，y均为正数且x>y num *adding_box(num *x, num *y) { //存储结果 num *ans = InitNum(); int base = x->base; //进制不变 ans->base = base; //符号为+ ans->neg = 0;
//小数部分
//确定最后一位小数 int low = (x->deci[0] >= y->deci[0] ? x->deci[0] : y->deci[0]); int pos = low; //指向当前操作位的指针 int temp = 0; //暂存当前进位和运算结果 for (int i = low; i >= 1; i--) { //逐位相加，考虑进位 temp += (x->deci[i] + y->deci[i]); ans->deci[pos--] = temp % base; //当前位保留的数 temp /= base; //进位值 } ans->deci[0] = low; //和的小数部分长度
//整数部分
//计算整数部分长度之差，小数点对齐，逐位相加，和小数部分类似 int dis = x->inte[0] - y->inte[0]; pos = x->inte[0]; for (int i = x->inte[0]; i - dis >= 1; i--) { temp += (x->inte[i] + y->inte[i - dis]); ans->inte[pos--] = temp % base; temp /= base; } for (int i = dis; i >= 1; i--) { temp += x->inte[i]; ans->inte[pos--] = temp % base; temp /= base; } ans->inte[0] = x->inte[0]; //如果最后一位有进位，需要整数部分整体右移 if (temp > 0) { for (int i = ans->inte[0]; i >= 1; i--) ans->inte[i + 1] = ans->inte[i]; ans->inte[1] = temp; //加上最后的进位 ans->inte[0] = x->inte[0] + 1; //更新长度 } else ans->inte[0] = x->inte[0]; return ans; }
//高精度乘法函数，调用大整数乘法器，在合适位置点上小数点即可 num *Mul(num *x, num *y) { //将x转为大整数a int xlen = x->inte[0] + x->deci[0]; int a[xlen + 1]; a[0] = xlen; int pos = 0; for (int i = 1; i <= x->inte[0]; i++) a[++pos] = x->inte[i]; for (int i = 1; i <= x->deci[0]; i++) a[++pos] = x->deci[i]; //将y转为大整数b int ylen = y->inte[0] + y->deci[0]; int b[ylen + 1]; b[0] = ylen; pos = 0; for (int i = 1; i <= y->inte[0]; i++) b[++pos] = y->inte[i]; for (int i = 1; i <= y->deci[0]; i++) b[++pos] = y->deci[i]; //存储结果的z int z[xlen + ylen + 1]; memset(z, 0, sizeof(z)); //进入大整数乘法器，获取z的有效区间 int start = multy_box(x->base, a, b, z); int end = z[start] + start; //小数点位置 int dot = x->deci[0] + y->deci[0]; //把大整数z转为需要的结果ans num *ans = InitNum(ans); ans->base = x->base; ans->neg = (x->neg + y->neg) % 2; //判断符号 pos = 0; // printf("%d\n", z[start]); int temp = start + 1; while (z[temp] == 0) //去除高位0 temp++; for (int i = temp; i <= end - dot; i++) { // printf("%d %d\n", i, z[i]); ans->inte[++pos] = z[i]; } ans->inte[0] = pos; //指针归零，读入小数部分 pos = 0; //有效位数较少，需要补0 if (end - start < dot) { //z中有效位数和补的0加一起足够小数位数为止 while (pos + end - start < dot) { if (pos >= n) break; ans->deci[++pos] = 0; } //再读入z中的全部数据 for (int i = start + 1; i <= end; i++) { ans->deci[++pos] = z[i]; if (pos >= n) break; } } //否则直接读入 else { for (int i = end - dot + 1; i <= end; i++) { ans->deci[++pos] = z[i]; // printf("%d ", z[i]); //因为大整数乘法器得到的结果精度是两个乘数精度之和 //为了防止把ans撑死，达到目标精度就可以退出了 if (pos >= n) break; } } ans->deci[0] = pos; return ans; }
多项式求值
解析表达式
表达式标准化
对于输入的一个多项式字符串，例如：3/7x^3-1/3x^2+6x-4，要提取出各项的系数与指数非常麻烦，所以我们需要将它格式化，转化为容易识别和处理的形式，比如转换为：+3/7x^3-1/3x^2+6x^1-4x^0，这样就可以通过 x 和 +- 号的位置快速定位到系数和指数的位置。所以我们需要一个转换函数。
//多项式的结构体 typedefstruct { num *a[MX]; //系数，按位存储 int power[MX]; //指数 int sum; //项数 } var;
//初始化 var *InitVar() { var *tmp = (var *)malloc(sizeof(var)); for (int i = 0; i < MX; i++) { tmp->a[i] = NULL; tmp->power[i] = 0; } return tmp; }
//销毁 var *DestroyVar(var *tmp) { for (int i = 0; i < MX; i++) { if (tmp->a[i] != NULL) free(tmp->a[i]); } free(tmp); }
注意：结构体中有 malloc 的时候不要忘记 free，比如这里的 num *a[]，里面有可能有指向堆内存的指针，需要在销毁函数里 free 掉。
当然，为了方便调试，输出函数必不可少。
代码
1 2 3 4 5 6 7 8
voidPrintVar(var *cal) { for (int i = 0; i < cal->sum; i++) { PrintNum(cal->a[i]); printf("%d\n", cal->power[i]); } }
最最困难的一个问题来了，对于这样的形式：+3/7x^3-1/3x^2+6x^1-4x^0，系数里有分数，不但要识别出来，还要进行计算后才能作为系数！这里我们先写一个除法函数，低精除以低精，结果返回 num 类型高精度数。大体思路就是先用整型的除法把结果的整数部分搞出来，然后剩下的被除数不断乘 10 再除以除数，保留每次的商拼接起来就是结果的小数部分，实际也是模拟手算的方法。
//除法函数，低精除以低精，返回高精 num *divide(int x, int y) { num *ans = InitNum(); ans->base = 10; //确定符号 ans->neg = (x * y > 0 ? 0 : 1); //负数转为正数，方便运算 if (x < 0) x = -x; if (y < 0) y = -y; // printf("x=%d y=%d\n", x, y); //先得到整数部分 int z = x / y; //存储z的每一位数，放在整数部分里 int temp[10]; memset(temp, 0, sizeof(temp)); int i = 0; while (z) { temp[++i] = z % 10; z /= 10; } temp[0] = i; ans->inte[0] = i; for (int j = 1; j <= i; j++) ans->inte[j] = temp[temp[0]--]; //如果除尽了，没有小数部分 if (x % y == 0) { ans->deci[0] = 0; return ans; } //否则余数*10继续除，直到除尽或者达到精度 else { int pos = 0; int res = x % y; for (int i = 0; i < n; i++) { res *= 10; ans->deci[++pos] = res / y; res %= y; if (res == 0) break; } ans->deci[0] = pos; return ans; } }
//计算多项式的值，调用上面的函数即可 num *Calcu(char expr[], num *x, int type) { //先解析表达式 var *cal = trans(expr, type); //调用加法和乘法运算 // PrintVar(cal); num *ans = InitNum(); num *used; num temp[cal->sum]; for (int i = 0; i < cal->sum; i++) { num *tmp = Pow(x, cal->power[i]); used = Mul(cal->a[i], tmp); free(tmp); temp[i] = *used; free(used); } num temp2; temp2 = temp[0]; for (int i = 1; i < cal->sum; i++) { used = Add(&temp2, &temp[i]); temp2 = *used; free(used); } *ans = temp2; DestroyVar(cal); return ans; }
