大学《数据结构》第四章：多维数组和广义表-第一节-多维数组和运算

1、本章概览当前讲授一.知识结构C多维数组的定义多维数组 多维数组的顺序存储对称矩阵矩阵的压缩存储1三角矩阵多维数组J稀疏矩阵和广义表r广义表的定义 主 J 广义表基本运算（X不r工广义表的存储结构I广义表基本运算的实现（略讲）二、本章重难点本要求考生熟悉数组在按行优先顺序的存储结构中元素地址的计算 方法；熟悉特殊矩阵在压缩存储时的下标变换方法；理解稀疏矩阵的 三元组表存储表示方法及有关算法；熟悉广义表的有关概念，理解广 义表的括号表示和图形表示；掌握广义表的求表头和表尾的运算。本章重点是多维数组的存储方式、矩阵的压缩存储、广义表的表头 和表尾的求解；难点是压缩存储特殊矩阵和稀疏矩阵的各种运算及应

2、 用。第一节多维数组和运算当前讲授一、多维数组的定义1、一维数组是一种元素个数固定的线性表。2、多维数组是一种复杂的数据结构，可以看成是线性表的推广，一个n维数组 可视为其数据元素为n-1维数组的线性表。二、数组的顺序存储通常采用顺序存储结构来存放数组。对二维数组可有两种存储方 法：一种是以行序为主序的存储方式，另一种是以列序为主序的存储 方式。在C语言中，采用以行为主序存储。（1）对于C语言的二维数组Amn,下标从0开始，假设一个数组元素占数组元素占d个存储单元，那么二维数组中任数组元素占d个存储单元，数组元素占d个存储单元，那么二维数组中任元素的存储位置loc(Aij) = loc(A00

3、)+(i *n + j) * d【真题选解】（例题单项选择题）二维数组A4 5按行优先顺序存储，假设每个元素 占2个存储单元，且第一个元素A的存储地址为1000 ,那么数组 元素A32的存储地址为（）A . 1012B . 1017C . 1034D . 1036隐藏答案【答案】C【解析】loc(A32) = loc(A00) + (3 *5 + 2) * 2=1000+34=1034(2 )对于C语言的三维数组Amnp,下标从0开始，假设一 个数组元素占d个存储单元，那么三维数组中任一元素的存储loc(Aijk) = loc(A000 + (i *n *p+j*p+k) * d(例题单项选择

4、题)三维数组A4 5按行优先存储方法存储在内存 中，假设每个元素占2个存储单元，且数组中第一个元素的存储地址为 120 ,那么元素A345的存储地址为()。A . 356B . 358C . 360D . 362隐藏答案【答案】B【解析】A45表示它共有4片，每片有5行，每行有6个元 素。元素A345处在3片4行5列上,是三维数组的最后一个元 素。按行优先存储方法存储时，它前面有3个完整的片，每片有5*6 个元素，3片有3*5*6个元素；在它所在片的4行之前，有4个完整 的行，每行有6个元素，因此它所在片所在行之前有4*6个元素；在 它所在行所在列之前还有5个元素。因此，在它之前总共有3*5*

5、6+4*6+5个元素，每个元素占2个存储单元。所以，元素A34的存储地址为:loc(A345) = loc(A000 + (3*5 *6+ 4*6+5) *2=120+238=358三、数组运算举例【例】设计一个算法，实现矩阵Amn的转置矩阵Bnm0【分析】对于一个mxn的矩阵A,其转置矩阵是一个nxm的矩阵B ,而且, 0in-l , 0jm-lo 假设 m=5 , , n=8e【算法描述】void trsmat(int a8 , int b5 , int m , int n) int i J;for(j=O;jm;j + +)for(i=0;in;i+)bij=aji;【例】如果矩阵A中存

6、在这样的一个元素,满足：是 第i行元素中最小值，且又是第j列元素中最大值，那么称此元素为该矩 阵的一个马鞍点。假设以二维数组存储矩阵Am x n ,试编写求出矩阵 中所有马鞍点的算法。【分析】算法思想：先求出每行中的最小值元素，存入数组Minm之中，再求出每列的最大值元素，存入数组Maxn之中。假设某 元素既在Mini中又在Max。中，那么该元素就是马鞍点，找出 所有这样元素。【算法描述】void MaxMin(int A45 , int m , int n) int i , j ;int Max5 , Min4;for(i=O ; im ; i+)计算每行的最小值元素，存入Min数组中 Mi

7、ni=AiO;先假设第i行第一个元素最小，然后再与后面的元素比拟for(j = l; jn ; j + +) if(AijMini) Mini=Aig;)for(j=0 ; jn ; j + +)计算每列的最大值元素，存入Max数组中 Maxj=AOj;假设第j列第一个元素最大，然后再与后面的元素比拟for(i=l; iMaxj)Maxg=Aij;)for(i=0;im; i + +)for(j=0;jn;j + +)if(Mini = = Maxj)判断是否为马鞍点pnntf(%dz%d, ij);显示马鞍点【真题选解】(例题算法阅读题)阅读以下程序。void f3O(int A , int n) intfor(i = l ; in ; i + +)for(j=0 ; ji ; j + +) m=Ai*n+j ; Ai*n+j与 An + i值交换Ai*n+j=Aj*n + i;Aj*n + i = m ;)回答以下问题：T23、B= 456(1)矩阵1789),将其按行优先存于一维数组A中，给出执行函数调用f30(A , 3)后矩阵B的值；(2)简述函数f30的功能。隐藏答案【解析】矩阵B存储在一维数组A中的初始状态如下图数组AA0 Al A2A3A4A5A6A7A81456789循环过程函数执行完后，数组A的状态如以下图外层循环内层