数组和广义表线性表扩展表中数据元素本身

数组和广义表线性表扩展表中数据元素本身一、教学目的与要求理解数组的定义、顺序表示和实现；矩阵的压缩存储；广义表的定义和存储结构二、主要教学内容数组的定义；数组的顺序表示和实现；矩阵的压缩存储、特殊矩阵、稀疏矩阵；广义表的定义、广义表的存储结构三、教学重点、难点多维数组、特殊矩阵、稀疏矩阵、广义表的存储结构四、授课方法及手段采用多媒体大屏幕投影授课五、讲课具体内容（讲稿）ADTArray{数据对象：ji=0,…,bi-1,I=1,2,…,n; D={aj1j2...jn|n(>0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2...jn∈Elemset}数据关系：R={R1,R2...Rn}Ri={＜aj1...ji...jn,aj1...ji+1...jn

＞|对每一维是线性的

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,bound2,...,boundn);……}ADTArray5.1数组的定义二维数组的类型定义: typedefElemTypeArray2[m][n]; Array2A;等价于：

typedefElemTypeArray1[n];typedefArray1Array2[m];Array2A;维数和维界a00a01a02...A0,n-1a10a11a12...A1,n-1Amxn=......am-1,0am-1,1am-1,2...Am-1,n-1

Am×n=((a00,a01,...a0,n-1),(a10,a11,...a1,n-1),...,(am-1,0,am-1,1,...am-1,n-1))二维的数组=定长的线性表5.2数组的顺序表示和实现除了初始化和销毁之外,

数组一般只有存取操作和修改元素值的操作，也没有插入和删除操作。存储时一般以行序为主序:(如C语言,PASCAL,BASIC等)Amxn=(a00,a01,...a0,n-1,a10,a11,...a1,n-1,...,am-1,0,am-1,1,...am-1,n-1)二维数组的存储LOC[0,0]为基地址,二维数组A[b1][b2]中元素aij的存储位置为:LOC[i,j]=LOC[0,0]+(b2×i+j)×L0<=i<=b1-10<=j<=b2-1L——每个数据元素所占的存储空间大小例5.1:若L=2,LOC[0,0]=1000，求LOC[2,3]LOC[2,3]=LOC[0,0]+(5*2+3)*L=1000+13*2=1026a00a01a02a03a04A4x5=a10a11a12a13a14a20a21a22a23a24a30a31a32a33a34三维数组的存储若LOC[0,0,0]为基地址:

LOC[i,j,k]=LOC[0,0,0]+

(n*h*i+h*j+k)*L0<=i<m0<=j<n0<=k<h每个数据元素占L个存储单元N维数组存储b1,b2,...,bn是n维数组A每一维的维界,数组元素A(j1,j2,...,jn)的存储位置为：

LOC[j1,j2,...jn]=LOC[0,0,...,0]+(b2×b3×…×bn×j1+b3×…×bn×j2+...+bn×jn-1+jn)×LSizeof(ElemType)倒推公式例:在C语言中,设数组A[5][6][7][8]的首地址为2000,每个元素占2个字节；求元素A[3][4][5][4]的地址。

LOC[3,4,5,4]=2000+(6*7*8*3+7*8*4+8*5+4)*2=2000+(1008+224+40+4)*2=4552数组顺序存储的表示和实现#incluse<stdarg.h>#defineMAX_ARRAY_DIM8typedefstruct{ElemType*base;intdim;int*bounds;int*constants;}Array;相当于Loc(0,…,0)BiCibasedimboundsconstantsa0a1aiat......01...dim-1101112132021222330313233A=3...basedimboundsconstants01...dim-14821011313233=25.3矩阵的压缩存储矩阵:二维数组特殊矩阵:大量重复元素或大量0元素稀疏矩阵:大量0元素压缩存储:重复元素只分配一个存储空间,0元素不分配存储空间5.3.1特殊矩阵对称矩阵:aij=aji(1<=i,j<=n)下三角矩阵:当i<j时,aij=0,(1<=i,j<=n)三对角矩阵:当|i-j|>1时,aij=0,(1<=i,j<=n)a11a12a13...a1na21a22a23...a2na31a32a33...a3n......an1an2an3...annAn×n=对称矩阵:aij=aji(1<=i,j<=n)4532152156313272528916795A=存储元素数:1+2+...+n=n(n+1)/2用一维数组SA[0…n(n+1)/2-1]存储矩阵A下三角元素:SA[k]=[a11,a21,a22,a31,…,a33,…an1,…,ann]

（k=1,2,…,n(n+1)/2）SA[k]和A[i,j]的一一对应关系:i(i-1)/2+j-1当i>=j（下三角含对角线）

k=j(j-1)/2+i-1当i<j（上三角）例5.3对称矩阵n=5,1+2+3+4+5=5*(5+1)/2=15一维数组SA[0..14]作为数组A的存储结构:SA=(452313252816795)

如:a[5,3]=a[3,5]=7k=5(5-1)/2+3-1=12

故:sa[12]=74532152156313272528916795A=4520313252816795A=下三角矩阵:当i<j时,aij=0,(1<=i,j<=n)同样用一维数组SA[0..n(n+1)/2-1]作为数组A非零元素的存储结构:sa[k]和a[i,j]的一一对应关系:sa[k],k=i(i-1)/2+j-1(当i>=j)a[i,j]=0(当i<j)例5.4下三角矩阵4000052000

A=313002528016795如:a[5,3]=7k=5(5-1)/2+3-1=12故:sa[12]=7（但：a[3,5]=0）三对角矩阵:

当|i-j|>1时,aij=0,(1<=i,j<=n)a11a1200... 0a21a22a230... 0An×n=0a32a33a34... 0...... an-1n

000...ann-1 ann一维数组SA[0..3*n-3]作为数组A三角元素的存储结构:SA[k]=[a11,a12,a21,a22,a23,a32,...,ann-1,ann]（k=0,2,3,4,5,6,…,3n-3,…,3n-3）sa[k]和a[i,j]的一一对应关系:sa[k],k=3*(i-1)+j-i，当|i-j|<=1a[i,j]=0当|i-j|>1例5.5三对角矩阵4300052200A=010400028700095一维数组SA[0..3*5-3]作为数组A的存储结构:SA=(4352210428795)如:a[5,4]=9k=3*(5-1)+4-5=11

故:sa[11]=95.3.2稀疏矩阵稀疏因子：假设在m×n的矩阵中，有t个元素不为零。令δ=t/(m×n)，称δ为矩阵的稀疏因子，通常稀疏因子<0.05时称为稀疏矩阵。

01290000 0000000 M(6×7)=-30000140 00240000 01800000 1500-7000转置矩阵 00-30015 12000180 9002400T(7×6)= 00000-7 000000 0014000 000000稀疏矩阵的存储结构

一.三元组顺序表M:ijeT:ije121213-3139161531-3211236142518432431952183424611546-764-76314三元组顺序表结构定义#defineMAXSIZE12500typedefstruct{inti,j;Elemtypee;}Triple;typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;TSMatrixM,T;M.data[p].i.j.e012..tumunutu1212......64-7求稀疏矩阵M的转置矩阵T012345678M.data[p].i.j.e012345678T.data[q].i.j.e方法：1.将矩阵的行列值相互交换；

2.将每个三元组中的i、j相互调换；

3.重排三元组之间的次序。

算法5.1：求稀疏矩阵M的转置矩阵TStatusTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}}retrunOK;}//TransposeSMatrix算法复杂度：

O(nu*tu)算法5.2：求转置矩阵的快速方法为了减少算法复杂度,增加两个向量num和cpot:num[col]:M中第col列中非零元素的个数;cpot[col]:M中第col列中的第一个非零元素在T.data中的位置;有:cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];

（2<=col<=m.nu）例5.6

01290000 0000000 M=-30000140 00240000 01800000 1500-7000

上例中的向量num和cpot:col1234567num2221010cpot1357889ijvijv0123456787683424161531963142518T[]13-301234567831-361156785218139432464-736141212211246-7col1234567cpot135788946297538M[]StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}}retrunOK;}//FastTransposeSMatrix算法复杂度：

O(nu+tu)三元组顺序表（有序的双下标法）小结特点/优点：

非零元在表中按行序有序存储，便于进行依行序顺序处理的矩阵运算。缺点：

若需按行号存取某一行的非零元，则需从头开始进行查找。#defineMAXRC100typedefstruct{inti,j;Elemtypee;}Triple;二、行逻辑链接的顺序表

（指出每一行的第一个非零元素在三元组中的位置）typedefstruct{Tripledata[MAXSIZE+1];intrpos[MAXRC+1];intmu,nu,tu;}RLSMatrix;M.data[p].i.j.e012........maxsizeM.rpos[row]三、十字链表

（行和列都是线性链表——非线性结构）

当矩阵的非零元个数和位置在操作过程中变化较大时，不宜采用顺序存储结构，采用链式存储结构表示更恰当。十字链表的表示法是稀疏矩阵的链式存储方法之一，其基本思想为：将稀疏矩阵同一行的所有非零元素串成一个带表头的环形链表，同一列的所有非零元素也串成一个带表头的环形链表。因此，在十字链表的表示中有两类结点，非零元素结点和表头结点。rowcolval*right*down非零元素结点：munutu*rhead*chead表头结点：十字链表：1什么是广义表广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。记作：LS=(d1,d2,......dn)。其中di既可以是单个元素，也可以是广义表。说明

1）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；

2）在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素,