第五章数组和广义表 数组和广义表的定义 数组和广义表的基本运算 数组的存储结构 广义表的存储结构 5.1数组的概念 数 >数组:是一种线性数据结构,它是有 构限个相同类型数据元素的有序集合。 数组的数据元素是值和下标的偶对 对每个有定义的下标,都有一个相关 数连的值 a11812 ain n a21822…a2n 表 am1am2…amn
1 第五章 数组和广义表 数组和广义表的定义 数组和广义表的基本运算 数组的存储结构 广义表的存储结构 数 据 结 构 之 数 组 和 广 义 表 2 5. 1 数组的概念 ¾ 数组：是一种线性数据结构，它是有 限个相同类型数据元素的有序集合。 ¾ 数组的数据元素是值和下标的偶对， 对每个有定义的下标，都有一个相关 连的值。 a11 a12 … a1n Amxn＝ a21 a22 … a2n · · · · am1 am2 … amn
据>基本操作:两种主要的运算 (1)给定一组下标,读取相应的数据 元素; Getvalue(a, &e,i,j) (2)修改元素值。 Change value(A,e,i,j) >数组一般不作插入和删除操作。 5.2数组的顺序表示和实现 /撂逻辑多维到存储一维的映射,即寻找多维下标和 一维下标的关系 构>存储方式 >行序为主序的存储方式 之数组和广义表 以列序为主序的存储方式 Alll 以行为主 以列为主
2 数 据 结 构 之 数 组 和 广 义 表 3 ¾ 基本操作：两种主要的运算： （1）给定一组下标，读取相应的数据 元素； GetValue( A, &e, i, j ) （2）修改元素值。 ChangeValue(A, e , i , j ) ¾ 数组一般不作插入和删除操作。 数 据 结 构 之 数 组 和 广 义 表 4 5. 2 数组的顺序表示和实现 ¾ 逻辑多维到存储一维的映射，即寻找多维下标和 一维下标的关系。 ¾ 存储方式 ¾ 行序为主序的存储方式 ¾ 以列序为主序的存储方式 a11 : a1n a21 : a2n : amn A1[1] a11 : am1 a12 : am2 : amn A1[1] 以行为主 以列为主
数组元素的存储位置是其下标的线 据结构之数组和广义表 性函数,存取数组中任一元素的时 间相等,所以,数组是随机的存储 结构。 计算一维下标 >以二维数组Am为例,计算数组元素 数据结构之数组和广义 A[ij的存储空间下标w 以行序为主序的存储方式 以列序为主序的存储方式 w=jn十i >有三维数组A|345计算数组元素 A[2l33的存储空间下标:以行序为主 N=2*(45)+3*5+3=58
3 数 据 结 构 之 数 组 和 广 义 表 5 ¾ 数组元素的存储位置是其下标的线 性函数，存取数组中任一元素的时 间相等，所以，数组是随机的存储 结构。 数 据 结 构 之 数 组 和 广 义 表 6 ¾ 计算一维下标 ¾ 以二维数组A[n][m]为例，计算数组元素 A[i][j] 的存储空间下标 w: ¾ 以行序为主序的存储方式 w=i*m+j ¾ 以列序为主序的存储方式 w= j*n+i ¾ 有三维数组A[3][4][5],计算数组元素 A[2][3][3]的存储空间下标：以行序为主 w=2*(4*5)+3*5+3=58
数组的顺序存储表示和实现 数 typedef struct{ 据结构 Elem Type*base int dim nt* bounds;/数组维界基址 int* constants;/数组映象函数(Page93的式(5-2) 数Aray 常量C基址,Ca=L=1,C1=bi*C; 组 第一维界第二维界第三维界第四维界 bounds2(块)5(页)3(行)4(列) constants5*12=603*4=124*1=4 cl=b2*c2c2=b3*c3c3=b4*c4c4=1 数组的算法实现 数# include /* ypedef void *va list; #define va start(ap, parmN 2 #define va_arg(ap, type)(*(type "(ap)++) #define va end(ap) 数 fe va_list ap 和 va start(ap,dim:使ap指向dim后面的实参表; 又 va arg( (ap, int):取出ap所指向的int型数据后, 表 ap++。 va end(ap:空语句
4 数 据 结 构 之 数 组 和 广 义 表 7 ¾ 数组的顺序存储表示和实现 typedef struct{ ElemType *base; int dim ; int *bounds ; //数组维界基址 int *constants ;//数组映象函数(Page93的式(5-2)) }Array; 常量Ci基址，Cn=L=1,Ci -1 =bi*Ci; 第一维界 第二维界 第三维界 第四维界 bounds 2 (块) 5 (页) 3 (行) 4 (列) constants 5*12=60 3*4=12 4*1=4 1 c1=b2*c2 c2=b3*c3 c3=b4*c4 c4=1 数 据 结 构 之 数 组 和 广 义 表 8 ¾ 数组的算法实现 #include typedef void *va_list; #define va_start(ap, parmN) (ap = ...) #define va_arg(ap, type) (*((type *)(ap))++) #define va_end(ap) va_list ap; va_start(ap,dim):使ap 指向dim后面的实参表； va_arg(ap,int):取出ap所指向的int型数据后， ap++。 va_end(ap):空语句
数main( f Array A; int dim 据结构之数组和广义表 InitArray(A, dim, 2, 5, 3,4); Status InitArray(Array &A, int dim, .i 数if(dim8) return ERROR 据A.dim=dim; A bounds=(int *)malloc( dim*sizeof(int) if(!A bounds)exit(OVERFLOW); elemtotall 数 a start(ap,dim); tr for(i=0; i<dim i++) A bounds]va arg(ap, int ) x if(A bounds<l)return UNDERFLOW; A elemtotal*=A bounds il:) va end(ap)
5 数 据 结 构 之 数 组 和 广 义 表 9 main( ) { Array A ; int dim=4; InitArray( A , dim , 2 , 5 , 3 , 4 ); …… } 数 据 结 构 之 数 组 和 广 义 表 10 Status InitArray(Array &A , int dim , ...){ if (dim8 ) return ERROR ; A.dim=dim; A.bounds=(int*)malloc(dim*sizeof(int)); if( !A.bounds) exit(OVERFLOW); elemtotal=1; va_start(ap,dim); for(i=0 ; i<dim ; i++){ A.bounds[i]=va_arg(ap , int ); if(A.bounds[i]<1) return UNDERFLOW; elemtotal*=A.bounds[i]; } va_end(ap) ;
s A base=(Elem Type*)malloc(elemtotal *sizeof(ET); 结if(!A.base)exit(Oⅴ ERFLOW); A constants=(int )malloc(dim*sizeof(int)); x if(!A constants)exit(OVERFLOW); A constants]dim-1=l; or(i=dim-2; i>=0; i--) 组和广义表 A constants i=A constants i+1]A bounds i+1; 义 return OK 5.3特殊矩阵的压缩存储 据 >特殊矩阵:数值相同的元素或零元素 在矩阵中的分布有一定规律。 之例:对称矩阵的压缩存储:以行序为主 数 序存储下三角中的元素,包括对角线 组上的元素。 表
6 数 据 结 构 之 数 组 和 广 义 表 11 A.base=(ElemType*)malloc(elemtotal*sizeof(ET)); if( ! A.base) exit(OVERFLOW); A.constants=(int *)malloc(dim *sizeof(int)); if( !A.constants) exit(OVERFLOW); A.constants[dim-1]=1; for(i=dim-2 ; i >=0 ; i--) A.constants[i]=A.constants[i+1]*A.bounds[i+1]; return OK; } 数 据 结 构 之 数 组 和 广 义 表 12 5. 3 特殊矩阵的压缩存储 ¾ 特殊矩阵：数值相同的元素或零元素 在矩阵中的分布有一定规律。 例：对称矩阵的压缩存储：以行序为主 序存储下三角中的元素，包括对角线 上的元素。 aij = aji 1<= i, j <= n
(1)二维下标为(i,j),存储空间的一维下标 为k,给出k与i,j的关系 (1=j)(,j)在下三角区 k=-1)j2+1(i=j return((i-1)*1/2+j-1) return((-1)*j/2+i-1);} 13 (2)输入并存储对称矩阵的算法(以行序为主序) void Input(ET All, int n)t 数据结构之 for(k=0;k=0)t e=alk; return O; else return error
7 数 据 结 构 之 数 组 和 广 义 表 13 (1) 二维下标为( i , j ),存储空间的一维下标 为k，给出k与 i , j 的关系（1=j) (i, j)在下三角区 k=(j-1)*j/2+i-1 (i=j) return((i-1)*i/2+j-1); return ((j-1)*j/2+i-1); } 数 据 结 构 之 数 组 和 广 义 表 14 (2)输入并存储对称矩阵的算法(以行序为主序) void Input(ET A[ ], int n){ for(k=0;k=0){ e=A[k];return OK; } else return ERROR; }
(4修改对称矩阵中某元素的算法 Status Change(ET Al I, int i, int j, ET e)f 结构之数组和广义表 f(k= k(i,j)>=0)i Ak=e; return OK; else return error: 15 要(5输出打印对称矩阵的算法 据 void PrintPro(eTAl, int n) 构 for(i=1;i<=n;i++){ printf("in”); forgj=l; j<=n;j++)t 数 GetElem(A, i,j,e) printf(%3d”,e);}
8 数 据 结 构 之 数 组 和 广 义 表 15 (4)修改对称矩阵中某元素的算法: Status Change(ET A[ ] ,int i, int j, ET e){ if(k=ij_TO_k(i , j)>=0) { A[k]=e; return OK; } else return ERROR; } 数 据 结 构 之 数 组 和 广 义 表 16 (5)输出打印对称矩阵的算法: void PrintPro( ET A[ ], int n){ for(i=1;i<=n;i++){ printf(“\n”); for(j=1;j<=n;j++) { GetElem(A, i, j, e); printf(“%3d ”,e) ; } } }
思考题 结 上三角矩阵、下三角矩 阵、对角矩阵、等特殊矩 虚阵的压缩存储和相关的算 法描述。 稀疏矩阵及其存储结构 >定义:如果一个m*n矩阵的非零元素 个数r比零元个数少,且非零元的分布 数据结构之数组和广义 没有一定规律。 000000064 260000000 0 0002700 008200000 表 820000000 13>压缩存储:只存储稀疏矩阵的非零元素
9 数 据 结 构 之 数 组 和 广 义 表 17 思考题 上三角矩阵、下三角矩 阵、对角矩阵、等特殊矩 阵的压缩存储和相关的算 法描述。 数 据 结 构 之 数 组 和 广 义 表 18 ¾ 稀疏矩阵及其存储结构 ¾ 定义：如果一个 m*n 矩阵的非零元素 个数 r比零元个数少，且非零元的分布 没有一定规律。 ¾ 压缩存储：只存储稀疏矩阵的非零元素
稀疏矩阵的三元组表存储方式 typedef struct( int i,j; El STriple 结 Triple *data 疏矩阵A的二元A A 0000000645|8|5 260000000 8641 组 000002700 2|1262 008200000 3627 382 820000000 182F data[0的三元分别用于存放矩阵总的行数、列 19数和非零元个数;用三元组表示的非零元以行序 为主序依次存放在data中 转置算法一 据 构 1334566 2316321 112 7 数 和由a求其转置矩阵b,需做以下事情: 义(1)矩阵的行列值互换,即若a为m×n,则b为n×m (2)每个三元组的行列号互换,即a1对应于b1 (3)a中三元组以原矩阵的行号为序,而b中三元组是 以原矩阵的列号为序
10 数 据 结 构 之 数 组 和 广 义 表 19 ¾ 稀疏矩阵的三元组表存储方式 typedef struct { int i , j ; ElemType e ; }Triple ; Triple *data; data[0]的三元分别用于存放矩阵总的行数、列 数和非零元个数；用三元组表示的非零元以行序 为主序依次存放在data中。 数 据 结 构 之 数 组 和 广 义 表 20 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 ¾ 转置算法一 a i j v b i j v 由a求其转置矩阵b，需做以下事情： ⑴ 矩阵的行列值互换，即若a为 m×n,则 b为 n×m； ⑵ 每个三元组的行列号互换，即aij对应于 bji； ⑶ a中三元组以原矩阵的行号为序，而b中三元组是 以原矩阵的列号为序