Docs
Powered by

# Array

  1. 数组在计算机内存中采用顺序存储结构进行存储,这是其最基本和最常用的存储方式。不论是一维数组还是多维数组,元素在内存中都是连续存放的。
  2. 稀疏矩阵
  • 稀疏矩阵的三元组表转置操作不仅需要将行和列对换,还需要对所有元素重新排序。
  • 三元组表中每个非零元素由(行号,列号,值)三个分量组成
  • 转置操作需要两个步骤:
    • 将每个元素的行号和列号互换
    • 按照新的行号和列号对所有元素进行重新排序(按行优先)
  • 如果只是简单地将行和列对换,而不进行重新排序:
    • 不能保证转置后的三元组表仍然保持"按行优先"的顺序
    • 违反了三元组表的基本存储规则
    • 会导致后续对矩阵的操作出现错误
  1. 数组常用的两种基本操作 -> 插入与索引
  2. 长度为N的顺序表中删除下标为i的元素(0 ≤ i ≤ N-1)，需要向前移动的元素个数是-> N-i-1
  3. 若有定义:
int c[4][5],( *pc)[5];
pc=c;

那么，下列对数组C的元素引用正确的是: -> * (*pc+2)

  • 这里pc是一个指向包含5个整型元素的数组的指针，通过pc=c使其指向二维数组c的首地址。
  • 二维数组和一维数组的区别在于，二维数组可以理解为一维的一维。在一维中，*表示取数值，在二维中*表示取第几行的地址，**表示取值。
  1. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n（n+1）/2]中，对上述任一元素aij (1≤i，j≤n，且i≤j)在B中的位置为 -> j（j-1）/2+i
  • 对于n*n的对称矩阵，由于对称性质，只需存储对角线及对角线以上的元素。
  • 以列为主序存储意味着按列优先顺序存储元素，即:
    • 第1列存储a11
    • 第2列存储a12,a22
    • 第3列存储a13,a23,a33 以此类推
  • 对于第j列(j≥i)，在该列之前已经存储了: 1+2+...+(j-1) = j(j-1)/2 个元素
  • 在第j列中，位置aij是该列的第i个元素，所以其在B数组中的位置为: j(j-1)/2 + i
  1. 若定义char a[10] = "good"，则数组a在内存中所占的字节数为10
  • char型数组a的长度为10，则其在内存中所占的字节数为就为10，与其赋值的字符串没有关系。
  1. 用数组 M[0..N-1] 用来表示一个循环队列， FRONT 指向队头元素，REAR 指向队尾元素的后一个位置，则当前队列中的元素个数是 -> (rear-front+n)%n（注：队列总的元素数不会超过队列大小）
  2. C中字符串和字符数组初始化是不同的。使用双引号初始化会自动添加字符串结束符,而使用花括号列表初始化则只包含显式指定的字符。这是在C编程中需要特别注意的一个细节。
在C++中，以下定义和初始化的两数组a1和a2
char a1[]= "program";
char a2[]={'p','r','o','g','r','a','m'}
  • a1[] = "program" 会在字符串末尾自动添加''(空字符),因此实际占用8个字节的存储空间。
  • a2[] = {'p','r','o','g','r','a','m'} 只存储了7个字符,没有自动添加'',因此只占用7个字节的存储空间。
char a[2][3];
    strcpy(a[0], "ab");
    strcpy(a[1], "cd");
    printf("%s", a);

输出ab。上述执行后相当于a[2][3] = {{'a', 'b', '\0'}, {'c', 'd', '\0'}};，在输出字符串的时候以'\0'为止结束字符串，所以输出的是字符串"ab"。 10. 在顺序表上进行插入操作时,平均移动结点数为n/2. 11. 在循环队列中,出队操作需要移动队头指示器f。使用(f+1)%m可以实现循环队列的特性. 12. 有一个用数组C[1..m]表示的环形队列，m为数组的长度。假设f为队头元素在数组中的位置，r为队尾元素的后一位置（按顺时针方向）。若队列非空，则计算队列中元素个数的公式应为 -> (m+r-f) mod m 13. C/C++ 中在二维数组的声明中，如果要省略维度，只能省略第一个维度（行数），而第二个维度（列数）必须明确指定。这样编译器才能正确计算数组元素的存储位置。 14. 数组和矩阵在计算机科学中是两个不同的概念,它们不能完全等同。

  • 数组是一种线性的数据结构,用于存储相同类型的元素序列。数组可以是一维的,也可以是多维的。数组主要特点是按照索引访问元素,且元素在内存中连续存储。
  • 矩阵是数学概念,是一个按照行列排列的二维数字或符号集合。矩阵有其特定的运算规则,如矩阵加法、乘法等。虽然在程序实现上通常用二维数组来表示矩阵,但这只是一种实现方式。
  1. 在C语言中，字符数组之间不能直接用赋值运算符进行复制，必须使用字符串处理函数strcpy()来完成字符串的复制。strcpy()函数会将源字符串(包括结束符'')复制到目标数组中。
  2. 在行优先存储的三维数组中,元素A[i][j][k]的地址计算公式为: 基地址 + (i×列数×层数 + j×层数 + k) × 元素大小
  3. 对称矩阵并不是所有特殊矩阵中压缩存储节省空间最多的。以n阶矩阵为例:
  • 对称矩阵需要存储的元素个数为n(n+1)/2个,因为只需要存储上(下)三角和对角线元素。

但其他一些特殊矩阵可以节省更多存储空间:

  • 对角矩阵:只需存储对角线上的n个元素
  • 三对角矩阵:需要存储3n-2个元素
  • 单位矩阵:实际上只需存储1个值即可(对角线上都是1)

所以当n较大时: 单位矩阵(1个) < 对角矩阵(n个) < 三对角矩阵(3n-2个) < 对称矩阵(n(n+1)/2个) 18. 在64位机器上运行以下代码段会输出什么结果。 ()

    char a[2] = {1,2};
    char *b= &a[0];
    printf("%d，%d", sizeof(a), sizeof(b));

sizeof(a)为数组a的长度，a为char类型数组，所以sizeof(a)为2；sizeof(b)为指针b的长度，在64位机上指针占8个字节，所以，sizeof(b)为8。 19. 中缀表达式 a * b + c / d - e 转换为前缀表达式。

  • 乘法 * 和除法 / 优先级高于加法 + 和减法 -。
  • 同一优先级按 从左到右 结合。
  • 所以先算 a * b 和 c / d，再处理 + 和 -。
  • 分步括号化
    • ((a * b) + (c / d)) - e
  • 转换为前缀
    • a * b → * a b
    • c / d → / c d
    • (a * b) + (c / d) → + * a b / c d
    • 整体：((a * b) + (c / d)) - e → - + * a b / c d e
  • 最终前缀表达式：
    • −+∗ab/cde
  1. 已知int a[3][4];则下列能表示a[1][2]元素值的是 （（a+1）+2）,分析过程如下：
  • a+1 得到第2行的首地址
  • *(a+1) 得到第2行首元素地址
  • *(a+1)+2 得到第2行第3个元素的地址
  • （（a+1）+2）最终得到a[1][2]的值
  1. 在C语言中，设有数组定义：char arrays[]="China"；则数组array所占用的空间为6个字节
  • 在C语言中，字符串"China"实际上包含了5个可见字符('C','h','i','n','a')以及一个隐含的字符串结束符''，因此总共需要6个字节的存储空间。
  1. 在循环队列中，指针移动时要考虑取模运算，这样才能保证在数组范围内循环。当队列执行删除操作时，front向后移动；当执行插入操作时，rear向后移动。
  2. 线性表的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。
  3. 在程序设计中，要对两个16K×16K的多精度浮点数二维数组进行矩阵求和时，行优先读取和列优先读取的区别是 -> 行优先快

在计算机体系结构中,数据访问的局部性原理(空间局部性)对程序性能有重要影响。

行优先读取更快的原因是:

  • 计算机内存是按行存储二维数组的,相邻元素在物理内存中连续存储
  • 行优先访问符合CPU缓存的预取机制,可以充分利用空间局部性
  • 每次读取可以最大化利用缓存行(cache line),减少缓存未命中的次数

而列优先读取会导致:

  • 访问内存时跳跃性大,不连续
  • 频繁发生缓存未命中(cache miss)
  • 需要更多的内存访问操作,影响性能
  1. 快速排序的划分过程是通过选择一个基准元素，将数组分为两个部分，小于基准的放在左边，大于基准的放在右边。
  2. 下三角矩阵的压缩存储空间节约量并不是完全的一半，这取决于矩阵的维度。

具体分析如下：

  • 对于n阶方阵，完整存储需要n×n个元素空间
  • 下三角矩阵的非零元素个数为n×(n+1)/2，包括:
  • 主对角线上的n个元素
  • 下三角部分的n×(n-1)/2个元素

实际节省的空间计算:

  • 原始存储空间: n×n
  • 压缩后存储空间: n×(n+1)/2
  • 节省空间比例 = (n×n - n×(n+1)/2) / (n×n) = (2n×n - n×(n+1)) / (2n×n) = (2n×n - n×n - n) / (2n×n) = (n×n - n) / (2n×n) = (n-1) / (2n)

从计算结果可以看出:

  • 当n很大时，节省比例接近1/2
  • 当n较小时，节省比例小于1/2
  1. 在定义 int a[3][4][2]; 后，第 20 个元素是

在C语言中,多维数组的元素按行优先顺序存储。对于int a[3][4][2]这个三维数组,总共有3×4×2=24个元素。

查找第20个元素的位置,我们需要:

  • 先理解数组的存储顺序:从最右维度开始,按[0][0][0],[0][0][1],[0][1][0],[0][1][1]...这样的顺序排列
  • 计算具体位置:
    • 每个a[i]包含8个元素(4×2)
    • 每个a[i][j]包含2个元素
    • 第20个元素的索引应该是19(因为数组索引从0开始)

具体计算:

  • 19 ÷ 8 = 2 (商)...3(余数) → 确定第一维是2
  • 3 ÷ 2 = 1 (商)...1(余数) → 确定第二维是1
  • 余数1就是第三维的索引
char s[5];
    s = "good";
    printf("%s", s);

定义了数组s，s为数组名，代表数组的首地址，不能直接赋值，所以编译出错。 29. 有一个100*90的稀疏矩阵,非0元素有10个,设每个整型数占2字节,则用三元组表示该矩阵时,所需的字节数是 -> 66

三元组表示法需要存储的内容:

  • 矩阵的行数(100)、列数(90)和非零元素个数(10)各占2字节
  • 每个非零元素需要存储:行号(2字节)、列号(2字节)、元素值(2字节)

计算总字节数:

  • 矩阵基本信息: 2 + 2 + 2 = 6字节
  • 非零元素信息: 10 * (2 + 2 + 2) = 60字节
  • 总计: 6 + 60 = 66字节
  1. 线性结构是指数据元素之间存在一对一的线性关系的数据结构,而二维数组和多维数组确实不属于线性结构

线性结构的特点:

  • 数据元素之间是一对一的关系
  • 除第一个和最后一个外,每个数据元素只有一个前驱和一个后继
  • 典型的线性结构包括:顺序表、链表、栈、队列等

二维数组和多维数组的特点:

  • 数据元素之间是一对多的关系
  • 一个元素可能有多个相邻元素
  • 数据在逻辑上呈现出网格状或立体状的组织形式
  • 存在行、列等多个维度的关系
  1. 数组除了可以在静态存储区和栈上创建，还可以在堆上动态创建。例如使用malloc函数分配的数组就是在堆上创建的。

指针虽然可以指向不同类型的内存块，但必须遵循类型安全原则。随意指向任意类型的内存块可能导致类型安全问题，需要进行适当的类型转换。

sizeof作用于指针变量时，只能得到指针本身的大小（通常是4字节或8字节），而不是指针所指向内容的大小。例如，int *p，sizeof(p)只会返回指针的字节数，而不是p所指向的内容大小。

sizeof运算符确实可以计算出数组的总字节数，这是因为数组在定义时就确定了大小，其内存空间是连续且固定的。例如int arr[10]，使用sizeof(arr)会返回40（假设int为4字节）。