lzyq88客服
  咨询电话:15382901348

lzyq88游戏

以杨辉三角为例,从内存角度简单分析C语言中的动态二维数组

学C语言,一定绕不过指针这一大难关,而指针最让人头疼的就是各种指向关系,一阶的指针还比较容易掌握,但一旦阶数一高,就很容易理不清楚其中的指向关系,现在我将通过杨辉三角为例,我会用四种方法从内存的角度简单分析动态二维数组,若有不足或错误之处,还请指出!

在讲这之前,以一维数组为例,先重新认识一下数组:

int array[5] = {1, 2, 3, 4, 5};

首先数组名称是该数组的首地址常量,即数组名称就是指针,就有&array[0] == array!

那么我们可以推出*array == array[0] == 1;

这里引入一个概念“指类”(这个概念没有在正规场合出现过,只是我为了方便分析而引入的),其表示指针所指向的空间的类型!array是一个int*类型的指针,那么它的指类就是int类型(比较容易的记忆,就是指针的类型去掉一个*就是其指类!);

其实array[0]是一个表象,其本质应该是*array ;

我们的array是局部变量,在系统堆栈中申请了sizeof(int)*5,即20字节大小的空间,用于存放5个整型数!

因为array的值是该数组首元素的地址(即首地址),那么array+1的意思就是给该数组的首地址这个值增加了一个int类型空间字节数,也就是4字节,从而array+1的值就应该是该数组的下一个int类型元素的地址,即&a[1],所以就有array+1 == &a[1];

那么array加几加几,加的实际就是多少个指类空间大小!

那么*array就可以理解成*(array + 0),同理,array[1] ==*(array + 1),array[2] == *(array + 2)......

上式还可以由加法交换律变形得到array[1] == *(1 + array),那么array[1]透过这一本质来看,其也可以变形成1[array];

*这样写编译器不但不会报错,而且连警告都不会有,但不建议这样书写!

*如果对我上文提到的系统堆栈不了解的话,强烈建议看一看下面的这个博客,后文全部涉及到内存!

*后文我不会用array[index]这种方式,而是用*(array + index)这种最本质的方式

C语言中关于形参与实参关系

 

这里我们先讲一讲系统堆栈和系统堆:

        操作系统将内存分成:系统数据,系统功能调用(核心代码)区域;用户代码和数据区域;系统堆栈区;系统堆区;

        系统堆栈是由编译器自动分配,用于存放函数的参数值,局部变量的值等;

        而系统堆区是由程序员通过malloc/calloc函数自主申请的空间,系统堆的空间要远远大于系统堆栈的空间,但切记,一定要在使用完毕后,通过free函数释放掉所申请的空间。

*C语言(包括C++)不像Java那样有gc(垃圾回收)机制,gc机制大大减少了程序员的工作量,程序员在Java中通过new申请空间时,只需负责申请,gc会帮助善后(实则是Java的JVM),而C/C++需要程序员自主释放,所以java相比C++要容易掌握!

----------------------------------------------------------------------------------------------------------------------------------

 

杨辉三角:

                                                 

关于杨辉三角如何计算得到的问题,我就不累赘了(*^_^*)

方法一:

如图,我们给出了一个六层的杨辉三角,通常的话,我们会给一个静态的二维数组用来存放这个杨辉三角:

int yangHui[row][row];

但是这会生成一个row行×row列的空间,而我们实际用到的的空间要比这小,除了最后一层,其他每一层都会有浪费的空间,为了避免这样的情况,我们就应该想到动态的数组,根据当前行数,通过malloc/calloc动态申请每一层的空间。所以,我们可以用如下的方式表示这个二维数组:

int *yangHui[row];

这种定义看起来很奇怪,其实它完全就是一个一维数组,这个一维数组的大小是row,只不过这个一维数组的每一个元素是由int *类型所组成,其本质就是一个一维的指针数组!我们可以把它定义成以下这种形式:

typedef int* type;type yangHui[row];

这样看的话就比较好理解了,他就是一个类型为type类型的一维数组!而type就是int*,那么,这个一维数组存放的每一个元素就应该是一个int*类型的的值,那么这个值完全就可以是一个int类型的一维数组的首地址!即yangHui数组里面存放的是row个一维数组的首地址!

铺垫工作完成,下来我们就来生成杨辉三角:

*由于杨辉三角往后的数字越来越大,故以下代码都用long类型!先假定要生成的杨辉三角的层数num = 5;

void creatYangHuiOne(int num);void creatYangHuiOne(int num) {long *yangHui[num];int row;int col;for (row = 0; row < num; row++) {*(yangHui + row) = (long *) calloc(sizeof(long), row + 1);for (col = 0; col <= row; col++) {*(*(yangHui + row) + col) = (row == col || col == 0) ? 1 : *(*(yangHui + row - 1) + col - 1) + *(*(yangHui + row - 1) + col);}} // 关于showYangHuiTriangle函数我会在最后给出,只是为了打印好看,不做重点! showYangHuiTriangle(yangHui, num);for (row = 0; row < num; row++) {free(*(yangHui + row));}}

多次循环得到下列关系

方法二:

void creatYangHuiTwo(int num);void destoryYangHui(long **yangHui, int num);void creatYangHuiTwo(int num) {long **yangHui = NULL;int row;int col;yangHui = (long **) calloc(sizeof(long *), num);for (row = 0; row < num; row++) {*(yangHui + row) = (long *) calloc(sizeof(long), row + 1);for (col = 0; col <= row; col++) {*(*(yangHui + row) + col) = (row == col || col == 0) ? 1 : *(*(yangHui + row - 1) + col - 1) + *(*(yangHui + row - 1) + col);}}showYangHuiTriangle(yangHui, num);destoryYangHui(yangHui, num);}void destoryYangHui(long **yangHui, int num) {int row; for (row = 0; row < num; row++) {free(*(yangHui + row));}free(yangHui);}

方法三:

long **creatYangHuiThree(int num);long **creatYangHuiThree(int num) {long **yangHui = NULL;int row;int col;yangHui = (long **) calloc(sizeof(long *), num);for (row = 0; row < num; row++) {*(yangHui + row) = (long *) calloc(sizeof(long), row + 1);for (col = 0; col <= row; col++) {*(*(yangHui + row) + col) = (row == col || col == 0) ? 1 : *(*(yangHui + row - 1) + col - 1) + *(*(yangHui + row - 1) + col);}}return yangHui;}

与方法二基本一样,只不过返回值是long **类型,将creatYnaghHuiThree函数中yangHui的值即在系统堆中申请的空间的首地址addressRow作为返回值返回!该空间不会随着子函数的调用结束而消失,需要在主函数中释放!

 

方法四:

void creatYangHuiFour(long ***yangHui, int num);void creatYangHuiFour(long ***yangHui, int num) {int row;int col;*yangHui = (long **) calloc(sizeof(long *), num);for (row = 0; row < num; row++) {*((*yangHui) + row) = (long *) calloc(sizeof(long), row + 1);for (col = 0; col <= row; col++) {*(*((*yangHui) + row) + col) = (row == col || col == 0) ? 1 : *(*((*yangHui) + row - 1) + col - 1) + *(*((*yangHui) + row -1 ) + col);}}}

当creatYangHuiFour函数调用结束,栈底栈顶指针回落,系统堆栈申请的子函数的局部变量都奔释放,但是主函数的yangHui空间的值通过指针运算已经由NULL变为ddressRow,而这个空间是在系统堆中申请的,不会随着子函数的调用结束而消失,即该空间还未被释放,故需要在主函数中释放!

打印函数及主函数:

void showYangHuiTriangle(long **yangHui, int num);int getMaxNumberLength(long num);int getMaxNumberLength(long num) {int count = 1;while (num/=10) {++count;}return count;}void showYangHuiTriangle(long **yangHui, int num) {int len = getMaxNumberLength(*(*(yangHui + num -1) + num/2));int i;int j;int row;int col;for (row = 0; row < num; row++) {for (i = 0; i < num - row - 1; i++) {for (j = 0; j < len; j++) {printf(" ");}}for (col = 0; col < row + 1; col++) {printf("%ld", *(*(yangHui + row) + col));if (getMaxNumberLength(*(*(yangHui + row) + col)) < len) {for (j = 0; j < len - getMaxNumberLength(*(*(yangHui + row) + col)); j++) {printf(" ");}}for (j = 0; j < len; j++) {printf(" ");}}printf("");}}int main() {long **yangHui = NULL;int num;printf("请输入行数:");scanf("%d", &num);creatYangHuiOne(num);creatYangHuiTwo(num);//yangHui = creatYangHuiThree(num);creatYangHuiFour(&yangHui, num);showYangHuiTriangle(yangHui, num);destoryYangHui(yangHui, num);return 0;}

输出如图:

感谢您的阅读(*^_^*)