数据结构讲义四：数组

1、第四章 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表4.1 数组的定义和特点定义mnmmnnnmaaaaaaaaaA.212222111211数组特点v数组结构固定v数据元素同构数组运算v给定一组下标，存取相应的数据元素v给定一组下标，修改数据元素的值( )( )( )( )( )( )( )( )( )维数和维界二维数组的类型定义:等价于 typedef ElemType Array1n; typedef Array1 Array2m; typedef ElemType Array2mn; Array2 A;二维的数组 = 定长的线性表 a11 a12 a13 .

2、 a1n a21 a22 a23 . a2n Amxn= . am1 am2 am3 . amnAmxn=(a11,a12,a13,.a1n),(a21,a22,a23,.a2n),., (am1,am2,am3,.amn)数组的顺序表示和实现数组的顺序表示和实现除了初始化和销毁之外, 数组一般只有存取操作和修改元素值的操作. 通常不作删除和插入.行序为主序:(C语言,PASCAL, BASIC等)Amxn=(a11,a12,a13,.a1n,a21,a22,a23,.a2n,.am1,am2,am3,.amn)LOC1,1 为基地址: LOCi,j = LOC1,1 + (n*(i-1)+j

3、-1)*L (1=i=m, 1=j=n, 每个数据元素占L个存储单元)LOC3,4 = LOC1,1 + (5*(3-1)+4-1)*L = 1000 + 13 * 2 = 1026LOC0,0 为基地址: LOCi,j = LOC0,0 + (n*i+j)*L (0=im, 0=jn, 每个数据元素占L个存储单元)LOCi,j,k = LOC0,0,0 + (n*h*i+ h*j + k)*L(0=im, 0=jn, 0=kh, 每个数据元素占L个存储单元) a11 a12 a13 a14 a15A4x5 = a21 a22 a23 a24 a25 a31 a32 a33 a34 a35 a

4、41 a42 a43 a44 a45例：若 L=2, LOC1,1 = 1000一般n维数组的行主元存储地址计算公式b1,b2,.,bn是n维的维界,数组元素A(j1,j2,.,jn)的存储位置为LOCj1,j2,.jn= LOC0,0,.,0 + (b2 b3 . bn j1 + b3 . bn j2 + . + bn jn-1 + jn ) L n-1 n = LOC0,0,.,0 + ( ji bk + jn) L i=1 k=i+1 例例: : 在在C C语言中语言中, ,设设 数组数组A5678A5678的首地址为的首地址为 2000, 2000, 每个元素占每个元素占2 2个字节个

5、字节; ; 求元素求元素A3454A3454的地址的地址. . LOC3,4,5,4 = 2000 + (6 LOC3,4,5,4 = 2000 + (6* *7 7* *8 8* *3 + 73 + 7* *8 8* *4 + 84 + 8* *5 + 4)5 + 4)* *2 2 = 2000 + ( 336 = 2000 + ( 336* *3 + 563 + 56* *4 + 84 + 8* *5 + 15 + 1* *4)4)* *2 2 = 2000 + (1008 + 224 + 40 + 4) = 2000 + (1008 + 224 + 40 + 4)* *2 = 45522

6、 = 4552数组顺序存储的表示和实现数组顺序存储的表示和实现#include #include #define MAX_ARRAY_DIM 8typedef struct ElemType *base; int dim; int *bounds; int *constants;Array;basedimboundsconstantsa0a1aiat.0 1 . dim-1. Status InitArray(Array &A, int dim, .) va_list ap; ifif(dim MAX_ARRAY_DIM) returnreturn ERROR; A.dim = dim; A.

7、bounds = (intint * ) mallomalloc(dim*sizeofsizeof(int); ifif(!A.bounds) exitexit(OVERFLOW); elemtotal = 1; va_start(ap, dim); forfor(i =0 ; idim; +i) A.boundsi = va_arg(ap,int); ifif(A.boundsi =0; -i) A.constantsi = A.boundsi+1 * A.constantsi+1; returnreturn OK; VA_LIST VA_LIST 是在C语言中解决变参问题的一组宏VA_LI

8、ST的用法：的用法： （1）首先在函数里定义一具VA_LIST型的变量，这个变量是指向参数的指针 （2）然后用VA_START宏初始化变量刚定义的VA_LIST变量，这个宏的第二个参数是一个固定的参数。 （3）然后用VA_ARG返回可变的参数，VA_ARG的第二个参数是你要返回的参数的类型。 （4）最后用VA_END宏结束可变参数的获取。然后你就可以在函数里使用第二个参数了。如果函数有多个可变参数的，依次调用VA_ARG获取各个参数。 VA_LIST在编译器中的处理 (1)在运行VA_START(ap,v)以后，ap指向第一个可变参数在堆栈的地址。(2）VA_ARG()取得类型t的可变参数值，

9、在这步操作中首先ap = sizeof(t类型)，让ap指向下一个参数的地址。即第一个可变参数在堆栈里的地址。(3）VA_END(),X86平台定义为ap = (char*)0)，使ap不再指向堆栈，而是跟NULL一样，有些直接定义为(void*)0)，这样编译器不会为VA_END产生代码，例如gcc在Linux的X86平台就是这样定义的。要注意的是：由于参数的地址用于VA_START宏，所以参数不能声明为寄存器变量，或作为函数或数组类型。InitArray(A,4,5,6,7,8);basedim (4)boundsconstantselemtotal-17 0 1 2 38653361Ar

10、ray A5678;Array A5678;85605x6x7x84.2 数组的顺序存储结构次序约定v以行序为主序v以列序为主序 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序为主序存放按行序为主序存放 amn . am2 am1 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1n 按列序为主序存放按列序为主序存放01m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n

11、a21 a22 . a2n am1 am2 . amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 4.3 矩阵的压缩存储对称矩阵jiijjjijiik, 12/ ) 1(12/ ) 1(， a11 a12 . . a1n a21 a22 . . a2n an1 an2 . ann . a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：三角矩阵 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0Loc(aij)=Loc(a11)+( +(j-1

12、)*l i(i-1)2a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：对角矩阵 a11 a12 0 . 0 a21 a22 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann. 0 a32 a33 a34 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1) a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：7600070015000001800000

13、240001400003000000000009120MM由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维数（6,7）唯一确定稀疏矩阵v定义：非零元较零元少，且分布没有一定规律的矩阵v压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值v稀疏矩阵的压缩存储方法l顺序存储结构u三元组表#define M 20typedef struct node int i,j; int v;JD;JD maM;三元组表所需存储单元个数为3(t+1)其中t为非零元个数6 7 8 1 2

14、12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 mai j v0 1 2 3 4 5 6 7 8ma0.i,ma0.j,ma0.v分别存放矩阵行列维数和非零元个数行列下标非零元值7600070015000001800000240001400003000000000009120Mu带辅助行向量的二元组表增加一个辅助数组NRAm+1,其物理意义是第i行第一个非零元在二元组表中的起始地址（m为行数）显然有：NRA1=1NRAi=NRAi-1+第i-1行非零元个数(i2)0 1 2 3 4 5 6 NRA1335676 7 8 2 12 3 9 1

15、 -3 6 14 3 24 2 18 1 15 4 -7 maj v0 1 2 3 4 5 6 7 8矩阵列数和非零元个数列下标和非零元值NRA0不用或存矩阵行数二元组表需存储单元个数为2(t+1)+m+17600070015000001800000240001400003000000000009120Mu伪地址表示法伪地址：本元素在矩阵中（包括零元素再内） 按行优先顺序的相对位置 6 7 2 12 3 9 15 -3 20 14 24 24 30 18 36 15 39 -7 maaddr v伪地址非零元值矩阵行列维数0 1 2 3 4 5 6 7 8伪地址表示法需存储单元个数为2(t+1)7600070015000001800000240001400003000000000009120Mu求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表Y问题分析一般矩阵转置算法：for(col=0;coln;col+) for(row=0;rowp-col时，p和q右移（2）插入：