自己开始算法与数据结构前需要了解的一些小知识（数组篇）（C Primer Plus 6th总结）

且不谈数据结构的逻辑问题，对于一些数据结构的简单代码的基本问题有时候是由于对C语言基础知识的拓展部分理解和掌握不够牢固，本人总结了一些小知识，觉得在以后的数据结构学习中可能会用的到，这次单拿数组来讲的，其他部分以后陆续补充，全篇是基于自己对《C Primer Plus 6th》英文版的理解，我个人觉得很难记住的要点进行的一些摘要和总结，后期如果还有的话我会继续补充。如果觉得不够全面，还请谅解。

一，变长数组(VLA)

比较简单的定义一个数组的时候总是要指明数组的大小，还需要赋初值，就好比这样：

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

后来比较高端一些的写法是这样的：

#define N 5
int array[N]={1,2,3,4,5}

这类定义或许还可以解决一些简单的程序问题，但是当我们开始尝试解决一些比较难得题目的时候，这种定义似乎对于解决比较难得题目就显得力不从心，根据数组的定义来说，数组的长度在定义之后就不会改变，但是可变长数组又是怎么回事呢，《C Primer Plus》给出的说明是这样的：
当然，这本书是根据二维数组的例子来进行可变长数组讲解得

 int quarters = 4;
int regions = 5;
double sales[regions][quarters]; // a VLA 

可变长数组的一些限制条件：

1.可变长数组属于自动储存类别（不加static声明的局部变量）
也就是说，可变长数组要么是在函数内部声明的并且没有static或者extern之类的储存类型修饰符，要么是声明作为函数参数的

2.不能在函数声明中初始化可变长数组

3.可以用但有时候没必要（原话是： Finally, under C11, VLAs are an optional feature rather than a mandatory feature,
as they were under C99. ）

NOTE，书中原话是这样的：
Note VLAs Do Not Change Size
The term variable in variable-length array does not mean that you can modify the length of thearray after you create it. Once created, a VLA keeps the same size. What the term variabledoes mean is that you can use a variable when specifying the array dimensions when first creating the array.

本人的理解是这样的：这里得可变长数组并不意味着你在声明它之后可以改变这个数组的大小，一旦它被定义了，这个数组的长度是不能变得，可变长数组的“变”在于你第一次定义这个数组的时候你可以用变量来用在代替数组的维度上

在声明具有二维可变长数组作为参数得函数时的固定格式：

 int sum2d(int rows, int cols, int ar[rows][cols]); // ar a VLA 

由于row 和 cols是作为数组 ar 的参数来被定义的，所以他们应该被定义在数组 ar 之前，而不能这么定义：

 int sum2d(int ar[rows][cols], int rows, int cols); // invalid order 

接着作者对可变长数组的用法通过一个例子做了详细的介绍：

 //vararr2d.c -- functions using VLAs
#include <stdio.h>
#define ROWS 3
#define COLS 4
int sum2d(int rows, int cols, int ar[rows][cols]);
int main(void)
{
int i, j;
int rs = 3;
int cs = 10;
int junk[ROWS][COLS] = {
{2,4,6,8},
{3,5,7,9},
{12,10,8,6}
};
int morejunk[ROWS-1][COLS+2] = {
{20,30,40,50,60,70},
{5,6,7,8,9,10}
};
int varr[rs][cs]; // VLA
for (i = 0; i < rs; i++)
for (j = 0; j < cs; j++)
varr[i][j] = i * j + j;
printf("3x5 arrayn");
printf("Sum of all elements = %dn",
sum2d(ROWS, COLS, junk));
printf("2x6 arrayn");
printf("Sum of all elements = %dn",
sum2d(ROWS-1, COLS+2, morejunk));
printf("3x10 VLAn");
printf("Sum of all elements = %dn",
sum2d(rs, cs, varr));
return 0;
}
// function with a VLA parameter
int sum2d(int rows, int cols, int ar[rows][cols])
{
int r;
int c;
int tot = 0;
for (r = 0; r < rows; r++)
for (c = 0; c < cols; c++)
tot += ar[r][c];
return tot;
}

输出结果是这样的：

3x5 array
Sum of all elements = 80
2x6 array
Sum of all elements = 315
3x10 VLA
Sum of all elements = 270

这里需要注意的是：int sum2d(int rows, int cols, int ar[rows][cols])这一句中的可变长数组并没有实际定义数组，这里的可变长数组名仅仅只是指向可变长数组的指针，也就是说函数实现的功能是作用在原始数组上的，因此得以能够修正（改变）作为参数传递过来的数组,接着作者用一下例子来说明：

int thing[10][6];
twoset(10,6,thing);
...
}
void twoset (int n, int m, int ar[n][m]) // ar a pointer to
// an array of m ints
{
int temp[n][m]; // temp an n x m array of int
temp[0][0] = 2; // set an element of temp to 2
ar[0][0] = 2; // set thing[0][0] to 2
}

正如上述代码所表达的，twoset()函数里的参数ar实际在被调用的时候是指向数组thing[10][6]的指针，指向该数组元素的首地址，同时thing也是指向thing[][]数组的首地址，也就是说ar[0][0]实际上是和thing[0][0]访问的数据位置是相同的（也就是ar 和thing指向同样的内容thing[0][0]）
可变长数组和普通数组的区别
可变长数组是动态内存分配的，也就是说可变长数组在运行的时候是可以改变数组大小的；而普通数组是在编译时就要说明大小的。

二，malloc函数

所有程序都要预留足够的内存用于数据的处理，内存的分配有时是自动分配的：

float x;
char place[] = "Dancing Oxen Creek";

也可以指定分配一定数量的内存：

int plates[100];

除此之外，C语言还能实现在程序运行时分配内存，比如使用malloc()函数进行内存分配，这里需要了解的是：
1.malloc()函数接收的参数是指定分配的内存字节数

2.malloc()函数指定分配的内存是匿名的

3.malloc()函数返回的是动态分配内存的首地址，因此就可以把malloc()函数返回的地址赋给一个指针变量，让指针指向该内存块的首地址

4.malloc()函数的返回值通常被指向时默认为指针是指向char类型数据

5.malloc()函数的返回值可以被“泛指针”所指向，这就意味着，malloc()函数的返回指针可以被用来指向数组，指向结构体等等，函数的返回值需要被强制转换成所匹配的类型，学会强制类型转换，提高代码可读性

6.malloc()函数分配内存失败，需要返回空指针NULL（重要）

使用malloc()函数为一个数组分配内存空间的例子：

 double * ptd;
ptd = (double *) malloc(30 * sizeof(double));

当程序运行时可以使用malloc()函数来分配内存空间，同时也可以定义指针变量来指向所分配的内存空间，这个例子需要关注的几点是：
1.我们分配的内存空间是30个字节的，我们定义的指针变量是double型的，我们可以用double类型的指针指向我们所分配的内存空间（前提是你需要将你动态分配的内存空间强制类型转换成double型，比如例子中的(double )malloc())

2.该指针声明时并不是声明的指向存有30个double类型的内存块，声明时只是指向一个double型

3.数组名是该数组首元素的地址（重要）

4.当你用prd指针指向你所分配的动态内存块时，实际上相当于指针指向的是内存块的首元素地址，也就是说，你可以用prd[0]访问内存块数组的第一个元素，prd[1]访问第二个元素

于是我们就有了三种方法来创建数组：

1.用常量表达式来定义数组的维度，用数组名来进行元素的访问，这样的数组既可以用静态的内存也可以用动态的内存存放

2.使用可变长数组来进行定义数组，可变长表达式用于定义数组的维度，数组名访问数组元素，这样的数组只能用动态内存来进行分配

3.使用malloc()函数来进行动态内存分配，返回值赋给指针变量，指向这块内存，通过指针来调用数组元素，指针可以是静态的也可以是动态的

2.和3.两种方式可以创建动态内存数组（ dynamic array），这种数组和普通数组的区别就在于：你可以在程序运行时决定数组的大小并为他分配内存。或许在你没有为变量 n 赋初值的时候，你并不能这样做：

 double item[n];

但是你却可以这么做：

 ptd = (double *) malloc(n * sizeof(double));

这比变长数组更加灵活

三，free()函数

malloc()和free()是成对出现，配套使用的。free()函数的参数是之前maollc()分配动态内存后返回的地址，free()用于释放malloc()所分配的内存。free()释放且仅仅释放他的参数所指定的内存。需要记住的是malloc()和free()是在stdlib.h文件里的。
给出malloc()和free()函数使用的例子：

/* dyn_arr.c -- dynamically allocated array */
#include <stdio.h>
#include <stdlib.h> /* for malloc(), free() */
int main(void)
{
double * ptd;
int max = 0;
int number;
int i = 0;
puts("What is the maximum number of type double entries?");
if (scanf("%d", &max) != 1)
{
puts("Number not correctly entered -- bye.");
exit(EXIT_FAILURE);
}
ptd = (double *) malloc(max * sizeof (double));
if (ptd == NULL)
{
puts("Memory allocation failed. Goodbye.");
exit(EXIT_FAILURE);
}
/* ptd now points to an array of max elements */
puts("Enter the values (q to quit):");
while (i < max && scanf("%lf", &ptd[i]) == 1)
++i;
printf("Here are your %d entries:n", number = i);
for (i = 0; i < number; i++)
{
printf("%7.2f ", ptd[i]);
if (i % 7 == 6)
putchar('n');
}
if (i % 7 != 0)
putchar('n');
puts("Done.");
free(ptd);
return 0;
}

这段代码看起来很冗长，但实现的功能很简单。这里我们关注几个要点就好：
1.

if (scanf("%d", &max) != 1)
{
puts("Number not correctly entered -- bye.");
exit(EXIT_FAILURE);
}

这一段代码需要我们关注的是 if 语句判断的是scanf()函数的返回值，scanf()函数的返回值有两种情况：输入成功返回1，输入失败返回0.如果是输入两个数，全部输入成功返回2，一个输入成功返回1，全部输入失败返回0.
然后就是exit(EXIT_FAILURE),表示程序的异常终止，程序的正常终止用EXIT_SUCCESS

 if (ptd == NULL)
{
puts("Memory allocation failed. Goodbye.");
exit(EXIT_FAILURE);
}

这一段代码是跟在ptd = (double *) malloc(max * sizeof (double));这句话后面的，用于判断malloc函数是否成功分配内存，如果分配失败，返回空指针，程序异常终止。
3.

free(ptd);

程序结束记得使用free()函数释放malloc函数分配的内存!!

四，静态存储和动态存储

静态存储，在编译时就确定需要分配的内存数量，在运行时直接进行数据的存取调用。内存块在程序开始时被创建，程序结束时被释放
动态存储所分配的内存在作用域程序块中开始存在，退出这部分程序块时释放。需要注意的是，这部分内存块通常是在内存的栈区所分配，所以数据是顺序存取，相反的顺序释放。内存的四区相关知识链接：

C/C++内存四区

五，围绕数组的函数和指针

flizny == &flizny[0]; // 数组名是该数组首元素的地址

指向数组的指针+1意味着指向下一个数组元素。

下面的等式体现了C语言的灵活性：
dates + 2 == &date[2] // 相同的地址
*(dates + 2) == dates[2] // 相同的值

不要混淆*(date + 2)和*date + 2

*(dates + 2) // dates第3个元素的值
*dates + 2 // dates第1个元素的值加2

现在假如我们想要能够处理数组的函数，求数组各项元素之和：
1.可能的函数调用：

total = sum(marbles);

这里需要注意的是：
1.数组名代表了数组元素的首地址
2.实参marbles实际代表着存储int类型值的地址
所以在函数声明的时候形参需要指向int类型的指针：

int sum(int * ar);

更通用的方法是函数的第二个参数加上一个指明数组大小的变量n:

int sum(int * ar, int n)

六，写在最后

用一个例子说明：

// sum_arr1.c -- 数组元素之和
// 如果编译器不支持 %zd，用 %u 或 %lu 替换它
#include <stdio.h>
#define SIZE 10
int sum(int ar[], int n);
int main(void)
{
int marbles[SIZE] = { 20, 10, 5, 39, 4, 16, 19, 26,
31, 20 };
long answer;
answer = sum(marbles, SIZE);
printf("The total number of marbles is %ld.n", answer);
printf("The size of marbles is %zd bytes.n",
sizeof marbles);
return 0;
}
int sum(int ar[], int n) // 这个数组的大小是？
{
int i;
int total = 0;
for (i = 0; i < n; i++)
total += ar[i];
printf("The size of ar is %zd bytes.n", sizeof ar);
return total;
}

通过输出我们能看到，marbles有40个字节，每个int类型占据4个字节，一共是10个，所以是40个字节，但是函数定义里的ar却只有8个字节.这是因为ar是一个指向数组首元素的地址的指针，我们的系统用8个字节存放地址，所以指针变量的大小是8个字节。

（参考文献：Stephen Prata《C Primer Plus 6th》）

最后

以上就是欢呼墨镜为你收集整理的自己开始算法与数据结构前需要了解的一些小知识（数组篇）（C Primer Plus 6th总结）的全部内容，希望文章能够帮你解决自己开始算法与数据结构前需要了解的一些小知识（数组篇）（C Primer Plus 6th总结）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。