第46题  N×N矩阵转置并求右上三角元素之和

试编写函数fun,通过指针形参a接收一个N×N矩阵即二维数组,实现矩阵转置,即行列互换,将右上三角元素(不含对角线)之和作为函数值返回。

例如:若接收3×3矩阵的二维数组为:

­         1   1   1
­ ­        2   2   2
­ ­        3   3   3

则转置结果为:

­         1   2   3
­ ­        1   2   3
­ ­        1   2   3

函数fun应当返回4(1+1+2=4)。

注意:部分源程序在PROG1.C中,请勿改动已给定的任何内容,只在函数fun的指定位置填入你编写的若干语句。

PROG1.C:

PROG46-01

参考答案:

PROG46-02

运行结果:

PROG46-03

程序解析:

编译预处理指令#include <stdio.h>让预处理器用头文件stdio.h的内容替换#include <stdio.h>这一行,这叫做文件包含,用来包含标准库的相关信息,支持在程序下文中调用printf、scanf、gets、puts等标准输入输出函数。换言之,如果程序要调用printf、scanf、gets、puts等库函数,就必须前置#include <stdio.h>,而且要单独占一行、结尾无标点,通常写在程序开头处。

编译预处理指令#define N 3定义符号常量N为3,这叫做宏定义或宏替换,凡在程序下文中N的出现均等同于3。倘若常量3在程序中多个地方多次出现,而且将来还可能需要改变,比方说要改为10,那么只要改变这个宏定义,就能保证多个地方的同步改变,这种修改程序的方式叫系统化修改。此外,由于宏名命名通常体现常量的意义,有助于提高程序易读性。宏名通常大写,而变量名通常小写,便于区分。为了养成习惯,即使宏名只用一次,也要这样定义。在本题中,N表示方阵的行、列数。

在main函数中,声明

int a[N][N] = {
­        {1, 1, 1},
­        {2, 2, 2},
­        {3, 3, 3}
­ };

定义a为N×N即3×3的二维int数组,其行下标从0到2、列下标从0到2,可容纳3行3列共9个整数,并做初始化。声明int i, j, s;定义3个int变量i、j和s,用作循环控制变量,s用来接收函数fun的返回值,上述定义的效果如下图所示。C语言把数组名定义为指向首元素的常量指针,只供引用但不能被改变,该指针的存储空间是(在含有数组名的表达式求值过程中)临时自动分配的,并不是数组存储块的组成部分,因此,二维数组名a是指向其第0元素(长度为3的一维整型数组)的常量指针,必须通过指针式∗(a+i)才能访问二维数组a的第i元素(长度为3的一维整型数组),但也可采用下标式a[i]访问a的第i元素,a[i]会自动转换为∗(a+i)。因为∗(a+i)或a[i]仅代表a的第i元素(长度为3的一维整型数组),是一维数组名,可继续套用数组名定义,因此∗(a+i)或a[i]是指向其第0元素(整型值)的常量指针,必须通过指针式∗(∗(a+i)+j)才能访问一维整型数组∗(a+i)或a[i]的第j元素,但也可采用下标式(∗(a+i))[j]或a[i][j]访问一维整型数组∗(a+i)或a[i]的第j元素,(∗(a+i))[j]或a[i][j]会自动转换为∗(∗(a+i)+j)。上面推理是比较费解的,对考生而言,记住用下标式a[i][j]访问二维数组的第i行第j列元素就行了!机器内存是一维连续字节阵列,数组元素连续占据一段内存,数组下标从0开始。二维数组a由3个长度为3的一维整型数组组成,其存储结构如下图,这3个一维整型数组连续占据一段内存,数组名a这个指针指向首元素即第0个长度为3的一维整型数组{1, 1, 1},以红色矩形框表示。

PROG46-04

在main函数中,函数调用语句s = fun(a);在执行之初完成参数传递,即把main的指针a传值(拷贝)于fun的指针形参a,其效果是让fun的形参指针a指向main中的数组对象a的首元素,如下图所示。还要注意:两个a同名同型,但不会冲突,因为它们分属不同的函数fun和main、分别存在于不同的存储空间、各有自己的作用域。函数fun的形参声明int a[ ][N]等价于int a[N][N]或int (∗a)[N],均声明a是指向长度为N的一维int数组的指针,故第1个N是冗余可省的。

PROG46-05

在函数fun中,通过形参指针a就能访问main中的数组a。既然a是指针且已实际指向二维数组首元素,那么a的下标式a[0]、a[1]、a[2]就分别是数组a的3个成员数组的标识或名字,由于a[0]、a[1]、a[2]都是一维数组名,即分别指向各自的首元素1、2、3,如上图所示,而且各有其下标式,分别是各自3个int元素的名字,例如:a[0][0]、a[0][1]、a[0][2]的值分别是1、1、1,如上图所示。上述概念比较繁琐,考生只要记住下面这张示意图,关于二维数组的问题均可迎刃而解。

PROG46-06

在函数fun中,声明int i, j, t, s;定义int变量i、j、t和s,i和j用作循环控制变量,同时充当访问数组a的下标。变量t用作数组元素交换位置的辅助变量。s用作累加器、累加矩阵右上三角元素之和。凡是二维数组问题,首先要根据题目具体要求,考虑扫描哪些元素。要实现矩阵转置,通行算法是行列互换,但对于N×N方阵,存在更简单的″就地″实现算法,那就是将右上三角元素与其关于对角线对称元素互换位置,这就要求逐个扫描右上三角的元素(不含对角线),每扫到一个元素就与其对称元素互换位置。下面的二重嵌套for循环语句就可实现这种扫描与互换:

for (i = 0; i < N−1; ++i)
­      for (j = i+1; j < N; ++j) {
­            t = a[i][j];
­            a[i][j] = a[j][i];
­            a[j][i] = t;
­            s += t;
­      }

外层以循控变量i从第0到N−2行扫描右上三角所在的各行,内层以循控变量j从第i+1到N−1列扫描当前第i行内的右上三角元素,因为在当前第i行内,位于对角线上的元素a[i][i]的列下标为i,而a[i][i]右边直到行尾均处于右上三角区域内,这些元素的列下标从第i+1、每次加1递增到N−1列,由变量j控制。在二重for语句控制下,每扫到右上三角的一个元素a[i][j]即借助变量t与其对称元素a[j][i]互换位置,由语句t = a[i][j]; a[i][j] = a[j][i]; a[j][i] = t;完成互换,由语句s += t;把当前元素t累加于变量s中。当二重for循环终止后,方阵转置完毕,转置效果如下图所示,s的当前值就是上三角元素之和4。

PROG46-07

接着,语句return s;将上三角元素之和返回main,被main的变量s接收,如下图:

PROG46-08

知识点:

① 函数通过指针形参可以访问调用者的数组,这是本题的考查要点,如通过形参a访问main的二维数组a。

②  函数通过指针形参,如指针a,访问调用者的二维数组时,通常采用下标式a[i][j]访问第i行、第j列的元素,直观又自然。注意:行、列下标均从0开始。

③ 通常采用二重嵌套for循环实现对二维数组元素的逐一扫描或符合某条件的局部区域扫描。程序经常基于这种扫描、在其中嵌入适当语句来解决问题,如函数main中二维数组元素的输出,就是逐一扫描;而函数fun对右上三角元素的扫描则是局部扫描。如果外层for语句的循控变量指定行下标、内层for语句的循控变量指定列下标,称为按行扫描;反过来,则称为按列扫描。本题中的扫描均属按行扫描。

④ 用于接收二维数组的函数形参声明的语法规则。例如:函数fun的形参声明int a[ ][N]等价于int a[N][N]或int (∗a)[N],均声明a是指向长度为N的一维int数组的指针。

⑤ 二维数组的定义及初始化的语法规则。初始化规则有两种形式。

⑥ 二维数组是一维数组的一维数组,也就是说,如果一维数组的元素是一维数组,那么就构成了二维数组。照此推广,还可以有多维数组。

⑦ 无论一维数组,还是多维数组,数组名均是指向其首元素的常量指针,均可通过下标式指定其各个元素。对于一维数组,其下标式就代表各个元素的值;而对于多维数组,其下标式只代表各个成员数组的名字,即维数减1的多维数组的名字,这些名字并不是元素的值,而是指向各自首元素的常量指针,这个过程可能反复进行,直到降维变成一维数组的名字,这时候再取一次下标式,才得到基本元素的值。

⑧ 利用辅助变量的二变量值互换定式。例如本题a[i][j]与其对称元素a[j][i]的互换,由3条语句t = a[i][j]; a[i][j] = a[j][i]; a[j][i] = t;共同完成,t是辅助变量,就像两杯水的互换,必须借助第3只空杯子一样。

练习题:

试改变程序中的适当内容,为自己命新题,举一反三。

返回