16 | 数据结构（上）：突破基本类型的限制，存储更大的整数

茶艺师学编程 利用老师留下的模块，我多跨了几步 1、课文2的1000次方程序的完全体，计算任何正整数的正整数幂。代码如下： /*大数幂*/ #include <stdio.h> #include <string.h> void print_Big(int x, int n){ int a[100000] = {1,1}; for(int i = 1; i <= n; i++){ for(int j = 1; j <= a[0]; j++)a[j] *= x; for(int j = 1; j <= a[0]; j++){ if(a[j] < 10)continue; if(j == a[0])a[++a[0]] = 0; a[j + 1] += a[j] / 10; a[j] %= 10; } } for(int i = a[0]; i >= 1; --i)printf("%d", a[i]); printf("\n"); } int main(){ int x, n; scanf("%d %d", &x, &n); print_Big(x, n); return 0; } 其中数组a的位数不能再大了，不然就是内存溢出······ 2、大数阶乘，就是计算输入的任意正整数的阶乘。代码如下： /*大数阶乘*/ #include <stdio.h> #include <string.h> void print_factorial(int n){//阶乘的函数 if(n < 0){ printf("error\n");//检查机制 return; } else if(n == 0){ printf("1" ); return; } int a[100000] = {1,1}; for(int i = 2; i <= n; i++){ for(int j = 1; j <= a[0]; j++)a[j] *= i;//乘积的值 for(int j = 1; j <= a[0]; j++){ if(a[j] < 10)continue; if( j == a[0])a[++a[0]] = 0; a[j + 1] += a[j] /10; a[j] %= 10; } } for(int i = a[0]; i >= 1; --i)printf("%d", a[i]);//输出结果 } int main(){ int n; scanf("%d", &n);//输入几的阶乘 print_factorial(n); return 0; }

茶艺师学编程 1、课文的例子代码是在的太漂亮了 2、课文的“搞事情”，看似很简单，老师也十分亲切地给出了思路，其中的关键就是读入字符串数字，然后处理成整数数组······我找到的方法就是利用字符ACSII码性质来实现，说起来没什么，但就是整整耗了两个星期······· 3、无心插柳，我居然把老师的大数数组加法给模块化了。明明在第一次尝试改造时各种出错······ /*交作业：*/ #include <stdio.h> #include <string.h> void printBIG(char a[], char b[]){//定义函数printBIG，实现输入两个“字符串”大数，相加，输出“数字”大数 int c[1000] = {1,1}; int len_a, len_b; len_a = strlen(a) ; len_b = strlen(b) ; c[0] = ((len_a > len_b) ? len_a : len_b); for(int i = 1; i <= c[0]; i++){//从最小位开始相加，从左往右地放在数组C里 c[i] = (a[len_a - i] - '0') + (b[len_b - i] - '0') ;//这里字符数字换成数字数字的窍门是，字符0-9的ACSII码-48（字符0的ACSII码）=数字0-9 } for(int i = 1; i <= c[0]; i++){//进位处理 if(c[i] < 10)continue;// 每一位是否满10？ if(i == c[0])c[++c[0]] = 0;//是否要进位 c[i + 1] += c[i] / 10;//满10进1 c[i] %= 10;//原位除10求余 } for(int i = c[0]; i >= 1; --i)printf("%d", c[i]);//胡老师给的倒序输出语句太漂亮了，我直接拿来用了 printf("\n"); } int main(){ char a[1000], b[1000]; scanf("%s %s", a, b); printBIG(a, b); return 0; }

茶艺师学编程 之前发的代码后来发现有BUG，只要两个数的位数不一致的时候就不能正常运算。 现在修整了该BUG。 其中思路是把两个数的位数情况都遍历：相同、第一个数比第二个数多、第一个数比第二个数少。 以下是修整后的代码： #include <stdio.h> #include <string.h> void printBIG(char a[], char b[]){//定义函数printBIG，实现输入两个“字符串”大数，相加，输出“数字”大数 int c[1000] = {1,1}; int len_a, len_b; len_a = strlen(a) ; len_b = strlen(b) ; c[0] = ((len_a > len_b) ? len_a : len_b); for(int i = 1; i <= c[0]; i++){//从最小位开始相加，从左往右地放在数组C里 if((len_a - i) >= 0 && (len_b - i) >= 0)//位数相同的情况 c[i] = (a[len_a - i] - '0') + (b[len_b - i] - '0') ;//这里字符数字换成数字数字的窍门是，字符0-9的ACSII码-48（字符0的ACSII码）=数字0-9 else if((len_a - i) >= 0 && (len_b - i) < 0)//数1的位数比数2大的情况 c[i] = (a[len_a - i] - '0'); else if((len_a - i) < 0 && (len_b - i) >= 0)//数1的位数比数2小的情况 c[i] = (b[len_b - i] - '0'); } for(int i = 1; i <= c[0]; i++){//进位处理 if(c[i] < 10)continue;// 每一位是否满10？ if(i == c[0])c[++c[0]] = 0;//是否要进位 c[i + 1] += c[i] / 10;//满10进1 c[i] %= 10;//原位除10求余 } for(int i = c[0]; i >= 1; --i)printf("%d", c[i]);//胡老师给的倒序输出语句太漂亮了，我直接拿来用了 printf("\n"); } int main(){ char a[1000], b[1000]; scanf("%s %s", a, b); printBIG(a, b); return 0; }

老师您好，计算2的10次方并输出的示例代码中，我始终没明白为什么 num[0] 会变呢？不是一直都是初始化的值 1 吗？还有， num[j + 1] += num[i] / 10 这一行代码中的 I 是否应该为 j 呢？

对于原来的数据类型而言，我们的数组12345，底层使用64位存储的。而为了突破数据类型本身的限制，存放更大的数字，我们新建了一个数组，数组每个元素大小也是64位的话， 也就是说为了表示12345，实际上使用了更多的内存空间。 那么，有没有通过二进制本身，比如说在底层搞一个新的类型，比如说super long, 用128位或者更多位来表示这个大数据类型的方式呢？

老师您好，可以麻烦您有空的话帮我解决几个问题吗？谢谢！： 1，在标准C中是 以“__”开头,所以在标准C中要写成“__typeof()”或“__typeof__()”，在GNU C 中还支持直接写“typeof()”，我看您写的都是”__typeof()"，其实三个都是一样的，但是否为了不造成不必要的麻烦，才用了标准C的第一个呢？ 2，“一起动手搞事情”前面的代码，第23行，“c[i + 1] += c[i] / 10;”，请问这里直接用“+= 1”不行吗？我在这里看了好久才看明白就是一个“进一”的意思（笑哭）。 3，第22行，"c[++c[0]]"，这里是不是让“c[0]“先加一再拿来用？用"c[0]++"就会先用原来未加一的数值，然后才加一？我理解的对吗？ 谢谢老师，欧拉筛法我看了一些blog，看的头晕，不知道他们的一些变量的作用是什么？例如（https://blog.csdn.net/tianwei0822/article/details/78309453），cnt 是用来干什么的？里面的for循环看不太懂哈哈哈~

在计算机中虽然不用自己去计算，但是得理解计算机是怎么计算和存储与表达出来给人类能看懂的逻辑运算。越是高效的算法越简洁，计算机执行效率越高，但是越高效的算法需要数学能力和数学思维的水平也要越高才能做到。在数学思维上和数学在程序语言的表达逻辑上好像总有些差别。

有个疑问：并列的两个for循环：for (int j = 1; j <= num[0]; j++); 虽然在时空复杂度，两个并列的时间复杂度取最高，那这两个循环合并为一个是不是效率也会提高一些，虽然现在计算机执行速度很快了。

作业： #include <stdio.h> #include <string.h> // 定义交换两个变量值的宏 #define swap(a, b) \ { \ __typeof(a) _t = a; \ a = b; \ b = _t; \ } // 实现大整数加法，a + b的结果，存放在c中 void plus_big_integer(int *a, int *b, int *c) { // 让a指向位数较长的那个数 if (a[0] < b[0]) { swap(a, b); } // 大整数c的位数以a的位数为基准 c[0] = a[0]; // 循环模拟按位加法 for (int i = 1; i <= a[0]; i++) { if (i <= b[0]) { c[i] = a[i] + b[i]; } else { c[i] = a[i]; } } // 处理每一位的进位过程 for (int i = 1; i <= c[0]; i++) { if (c[i] < 10) { continue; } // 判断是不是最高位产生了进位，如果是则进行初始化 if (i == c[0]) { c[++c[0]] = 0; } c[i + 1] += c[i] / 10; c[i] %= 10; } } // 将一个数字字符串转换位大整数表示法 void trans_big_int_expression(char *str, int *arr) { int slen = strlen(str); arr[0] = slen; for (int i = 0; i < slen; i++) { arr[slen - i] = str[i] - 48; } } void main() { int a[20], b[20], c[20] = {0}; char stra[20], strb[20]; scanf("%s%s", stra, strb); // 转换为大整数表示法 trans_big_int_expression(stra, a); trans_big_int_expression(strb, b); // 进行大整数相加，并存入c中 plus_big_integer(a, b, c); for (int i = 0; i < 20; i++) { printf("%d", c[i]); } }

胡船长好，这行代码中 if (j == num[0]) num[++num[0]] = 0; 赋值为0的操作是不是可以省略，num数组在声明的时候已经初始元素全为0，还是说在有的情况下不是0，为了安全起见这样做的。