清华大学：《数据结构》课程电子教案（PPT课件讲稿）第五章 数组和广义表

第五章数组和广义表

第五章 数组和广义表

0一维数组具有线性表的结构,但操作简单,一般不 进行插入和删除操作,只定义给定下标读取元素和 修改元素的操作 0二维数组中,每个数据元素对应一对数组下标,在 行方向上和列方向上都存在一个线性关系,即存在 两个前驱(前件)和两个后继(后件)。也可看作 是以线性表为数据元素的线性表 n维数组中,每个数据元素对应n个下标,受n个关 系的制约,其中任一个关系都是线性关系。可看作 是数据元素为n-1维数组的一维数组。 0因此,多维数组和广义表是对线性表的扩展:线性 表中的数据元素本身又是一个多层次的线性表

一维数组具有线性表的结构，但操作简单，一般不 进行插入和删除操作，只定义给定下标读取元素和 修改元素的操作 二维数组中，每个数据元素对应一对数组下标，在 行方向上和列方向上都存在一个线性关系，即存在 两个前驱（前件）和两个后继（后件）。也可看作 是以线性表为数据元素的线性表。 n维数组中，每个数据元素对应n个下标，受n个关 系的制约，其中任一个关系都是线性关系。可看作 是数据元素为n-1维数组的一维数组。 因此，多维数组和广义表是对线性表的扩展：线性 表中的数据元素本身又是一个多层次的线性表

5.1数组的定义 52数组的顺序表示和实现 53矩阵的压缩存储

5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储

51数组的定义 ADT Array 数据对象:j=0, 2 5=5.:)11 D={a12.nln(>0)称为数组的维数,b是数组第维的 长度,j是数组元素的第维下标 12.n∈ ElemNet 数据关系:R={R31,R2,…,Rn Ri=(<an…1m1-1110≤jk≤bk-1,1≤k≤n 且k≠i,0≤j≤b ai1…ji…jn,aj1…ji+1…j ∈D,i=2,…n

5.1 数组的定义 ADT Array{ 数据对象：j i=0,…,bi-1 ,i=1,2,…,n, D={aj1j2…jn| n(>0)称为数组的维数，bi是数组第i维的 长度，j i是数组元素的第i维下标，aj1j2…jn∈ElemSet} 数据关系：R={R1,R2,…,Rn} Ri={| 0≤jk≤bk-1, 1≤k≤n 且k≠i,0≤ji≤bi-2, aj1…ji…jn,aj1…ji+1…jn∈D,i=2,…n}

基本操作 InitArray(&A, n, bound1, .. bound) DestroyArray (&A) Value(A, &e,index1, .. index) Assign(&A, e, index1,., index) JADT Array

基本操作： InitArray(&A,n,bound1,…,boundn) DestroyArray(&A) Value(A,&e,index1,…,indexn) Assign(&A,e,index1,…,indexn) }ADT Array

52数组的顺序表示 0多维数组用一维的存储单元存放需约定次序。 PASCALI和c语言是以行序为主序, FORTRAN以 列序为主序。 0给定维数和各维长度,数组的存储空间确定。 0二维数组中任一元素a的存储地址 aLoc()=Loc(0,0)+(b2+1+j)L n维数组:教材p93 Loc(j1j2,…jn)=Loc(0,0,…,0)+∑cj 口其中cnL,c1=bc1n

5.2 数组的顺序表示 多维数组用一维的存储单元存放需约定次序。 PASCAL和C语言是以行序为主序，FORTRAN以 列序为主序。 给定维数和各维长度，数组的存储空间确定。 二维数组中任一元素aij的存储地址: Loc(i,j)=Loc(0,0)+(b2*i+j)*L n维数组：教材p93 Loc（j1,j2,…,jn)=Loc(0,0,…,0)+ ∑ci j i 其中 cn=L, ci-1=bi *ci , 1<i≤n

类型定义 Include define MAX ARRAY Dim 8 typedef structi ElemType"base, int dim: int *bounds. int *constants, aRray

类型定义 #include #define MAX_ARRAY_DIM 8 typedef struct{ ElemType *base; int dim; int *bounds; int *constants; }Array;

53矩阵的压缩存储 0矩阵一般可用二维数组实现,特殊矩阵采用压缩存储。 0压缩存储:为多个值相同的元只分配一个存储空间, 对零元不分配空间。 0特殊矩阵:值相同的元素或者零元素在矩阵中的分布 有一定规律 0稀疏矩阵:非零元较零元少,且分布没有一定规律的 矩阵

5.3 矩阵的压缩存储 矩阵一般可用二维数组实现，特殊矩阵采用压缩存储。 压缩存储：为多个值相同的元只分配一个存储空间， 对零元不分配空间。 特殊矩阵：值相同的元素或者零元素在矩阵中的分布 有一定规律 稀疏矩阵：非零元较零元少，且分布没有一定规律的 矩阵

5.3.1.特殊矩阵 0对称矩阵:aj=可1 <i,jsn 口压缩存储方法:为每一对对称元分配一个存储空间 g将下三角的元素,按行存储到一维数组sa中 0共有n(m+1)2个存储单元, 0=副在一维数组中的位置k为:W12+-1当否则J-1)2+-1 角矩阵:上(下)三角中的元均为常数c或0 压缩存储方法:同上,只存储上(下)三角元素。 下三角:k=(-1)2+j-1 口上三角:ke=(2n-)(1-1)2÷1(按行) k=jU-1)2+-1(按列) 0注意:k从零开始,L从1开始 °殲矩阵:所有非零元都集中在以主对角线为中心的带状区 压缩方法:压缩存储到一维数组sa[]中,三对角矩阵有3n2个 元素。 口k=2H3

5.3.1. 特殊矩阵 对称矩阵： aij=aji 1≤i,j≤n 压缩存储方法：为每一对对称元分配一个存储空间 将下三角的元素，按行存储到一维数组sa中 共有n(n+1)/2个存储单元， aij在一维数组中的位置k为：i(i-1)/2+j-1 当i>=j 否则 j(j-1)/2+i-1 三角矩阵： 上（下）三角中的元均为常数c或0 压缩存储方法：同上，只存储上（下）三角元素。 下三角：k=i*(i-1)/2+j-1 上三角：k=(2n-i)(i-1)/2+j-1 (按行) k=j(j-1)/2+i-1 （按列） 注意：k从零开始，i,j从1开始 对角矩阵：所有非零元都集中在以主对角线为中心的带状区 域中。 压缩方法：压缩存储到一维数组sa[ ]中，三对角矩阵有3n-2个 元素。 k=2*i+j-3

532稀疏矩阵 1.三元组的表示 口稀疏矩阵可由表示非零元的三元组及其行列数 唯一确定。 口t个非零元,t(m°n)称为稀疏因子<0.05 0用三元组(J,a)存储行和列的位置,及非零元数值

5.3.2. 稀疏矩阵 1. 三元组的表示 稀疏矩阵可由表示非零元的三元组及其行列数 唯一确定。 t个非零元，t/(m*n)称为稀疏因子 <0.05 用三元组(i,j,aij)存储行和列的位置，及非零元数值