《数据结构（C#）》-第5章 数组和广义表

第5章数组和广义表5.1数组

5.2多维数组及其存储结构

5.3特殊矩阵及其压缩存储

5.4稀疏矩阵

5.5广义表5.1数组

数组可以看作是线性表的推广，特点是结构中的数据元素可以是具有某种结构的数据，甚至可以是数组，但属于同一数据类型。数组在许多高级语言里面都被作为固定类型来使用。数组的逻辑结构数组是n(n≥1)个相同数据类型的数据元素的有限序列。一维数组可以看作是一个线性表，二维数组可以看作是“数据元素是一维数组”的一维数组，三维数组可以看作是“数据元素是二维数组”的一维数组，依次类推。

数组是一个具有固定格式和数量的数据有序集，每一个数据元素通过下标来标识和访问。一个数组一经定义，每一维的大小及上下界都不能改变。所以，在数组上不能进行插入、删除数据元素等操作。数组上的操作一般有：取值操作：给定一组下标，读其对应的数据元素。赋值操作：给定一组下标，存储或修改与其对应的数据元素。清空操作：将数组中的所有数据元素清除。复制操作：将一个数组的数据元素赋给另外一个数组。排序操作：对数组中的数据元素进行排序。反转操作：反转数组中数据元素的顺序。5.2多维数组及其存储结构二维数组二维数组可以看成是向量的推广。例如，设A是一个有m行n列的二维数组，则A可以表示为：数组的内存映象采用顺序存储结构来存储数组中的数据元素。计算机的内存是一个一维数组，内存地址就是数组的下标。所以，可根据一维数组元素的下标得到它的存储地址及访问一维数组中的元素。对于多维数组，需要把多维的下标表达式转换成一维的下标表达式。两种存储方式：一种是以行序为主序（先行后列）的顺序存放，另一种是以列序为主序（先列后行）的顺序存放。

a11a12…a1na21a22…a2n…am1am2…amn(a)以行为主序a11a21…Am1a12a22…am2…a1na2n…amn(b)以列为主序按元素的下标求地址当以行序为主序进行存储：

Loc(aij)=Loc(a11)+((i-1)*n+j-1)*w

数组元素aij的前面有i-1行，每一行有n个数据元素，在第i行中aij的前面还有j-1个元素。当以列序为主序进行存储：Loc(aij)=Loc(a11)+((j-1)*m+i-1)*w

数组元素aij的前面有j-1列，每一列有m个数据元素，在第j列中aij的前面还有i-1个元素。数组是一种随机存储结构。

5.3特殊矩阵及其压缩存储特殊矩阵(RegularMatrix)的存储稀疏矩阵(SparseMatrix)的存储具有一定规律的矩阵，如对称矩阵，三角矩阵等很多元素是0（或者同一个值）,只有少量元素具有特定值压缩存储(compressedstorage)：使用少于二维数组的空间存储矩阵对称矩阵的存储n阶对称矩阵：aij=aji0i,jn-1不需存储所有n2个元素，只需存储n(n+1)/2个元素方法是将下三角元素线性化后用一维数组存储a00a01….a0n-1a10a11….a1n-1an-1,0an-1,1….an-1,n-1…aij….….….….aij(i<j)(=aji)的存储单元j(j+1)/2+iaij(ij)的位序1+2+…+i+j+1=i(i+1)/2+j+1aij(ij)的存储单元i(i+1)/2+j(丛0单元算起)三角矩阵的存储

（下)三角矩阵：所有的上三角元素aij(i<j)均等于一个常数,如0.上述方法同样适用于三角矩阵的存储:用一维数组存储下三角元素aij(ij),其中一个单元存储上三角元素，如0单元存放上三角元素，i(i+1)/2+j+1存放aij(ij)5.4稀疏矩阵6行,7列,非零元素8个稀疏因子

=稀疏因子

0.2稀疏矩阵:

非零元素数<<m*n应用:数值计算,图算法等稀疏矩阵ADT稀疏矩阵作为一类重要的数据结构可以定义为一个ADTADTSparseMatrix{

数据对象：D={aij|aijElemTypei=1,2,…,m;j=1,2,…,n}

数据关系：R={Row,Col}Row={(ai,j,ai,j+1)1im,1jn-1}Col={(ai,j,ai+1,j)1im-1,1jn}

基本操作：

…}ADTSparseMatrix基本操作包括：创建、输出、转置和加、减、乘等运算。稀疏矩阵的存储稀疏矩阵可以用所有的非零元素和它们的下标来唯一表示；每个非零元素可用一个三元组

（行下标，列下标，值）表示；

任务：如何存储这些三元组，并实现稀疏矩阵上的运算；顺序结构—三元组顺序表：按照行优先或者列优先的方法把非零元素视为一个线性表；链式存储—十字链：给每个非零元素附上它所在行和列的下一个非零元素的地址；稀疏矩阵的顺序存储使用顺序结构存储行优先的三元组表称为三元组顺序表其结构定义如下：

structtupletype<T>{publicintr;//行号

publicintc;//列号

publicTv;//矩阵中元素值

publictupletype(inti,intj,Tv){this.r=r;this.c=c;this.v=v;}}classspmatrix<T>{intMAX_Num;//非零元素的最大个数

introws;//行数值

intcols;//列数值

inttd;//非零元素的实际个数

tupletype<T>[]data;//存储非零元素的值及一个表示矩阵行数、列数和总的非零元素数目的特殊三元组矩阵的转置A67的转置矩阵的转置A67的存储结构(行优先序列)B76的存储结构(A67的列优先序列)转置的实现：扫描数组M，顺序找出列号为0的元素，转置，将其存放到数组T中；对下一列号重复进行，…直至最大列号MT转置的实现

StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元组顺序表表示稀疏矩阵，求稀疏矩阵M的转置TT.rows=M.cols;T.cols=M.rows;T.vals=M.vals;if(T.vals){q=0;//T.data的当前位置

for(j=0;j<M.cols;++j)for(k=0;k<M.vals;++k)if(M.data[k].col==j){//转置，拷贝到TT.data[q].col=M.data[k].row;T.data[q].row=M.data[k].col;T.data[q].val=M.data[k].val;++q;}}returnOK;}//TranspsoeSMatrix时间复杂度上述算法的时间复杂度为O(colsvals)通常的转置算法时间复杂度为O(colsrows)for(j=0;j<cols;++j)for(k=0;k<=rows;++k)T[i][k]=M[k][j];如果vals

colsrows,则时间复杂度为O(cols2

rows).可见，只有非零元素个数vals<<cols

rows时，上述算法才是有效的。快速转置扫描一次，转置每个三元组，直接定位快速转置顺序转置三元组表中的每个元素，将其存储到转置矩阵的三元组表中的最终位置；用rowSize[j]表示矩阵M中第j列非零元素个数，则第j列的第一个非零元素存放位置为

rowStart[j]=rowSize[0]+…+rowSize[j-1]用rowStart[j]表示M的当前读到的第j列元素在转置三元表中的位置rowSize[j]可以通过扫描M一次求得算法的时间复杂度为O(vals+cols)，代价是空间算法实现见课本三元组表示的特点节省了空间；当非零元素个数远远小于矩阵规模时，操作效率较高；当非零元素个数与矩阵规模为同一数量阶时，操作效率大大降低；稀疏矩阵的其他运算会使得结果的非零元素增加或者减少，相应的三元组表需要增加或者删除元素，在线性结构中需要移动元素，增加了时间的支出。稀疏矩阵的十字链表030056200每个结点存储非零元的行列号，值，以及指向下一行和下一列非零元结点的指针C#中的数组C#支持一维数组、多维数组及交错数组（数组的数组）。数组类型都隐含继承自System.Array。Array是一个抽象类，本身又继承自System.Object。数组总是在托管堆上分配空间，是引用类型。任何数组变量包含的是一个指向数组的引用，而非数组本身。当数组中的元素的值类型时，该类型所需的内存空间也作为数组的一部分而分配；当数组的元素是引用类型时，数组包含是只是引用。Array还继承了ICloneable、IList、ICollection、IEnumerable等接口。

C#中的数组一般是0基数组（最小索引为0）。支持非0基数组。可以创建动态数组，使用Array的静态方法CreateInstance方法来实现。publicabstractclassArray:ICloneable,IList,ICollection,IEnumerable{//判断Array是否具有固定大小。publicboolIsFixedSize{get;}//获取Array元素的个数。

publicintLength{get;}//获取Array的秩（维数）。

publicintRank{get;}//实现的IComparable接口，在.Array中搜索特定元素。

publicstaticintBinarySearch(Arrayarray,objectvalue);//实现的IComparable<T>泛型接口，在Array中搜索特定元素。publicstaticintBinarySearch<T>(T[]array,Tvalue);//实现IComparable接口，在Array的某个范围中搜索值。

publicstaticintBinarySearch(Arrayarray,intindex,intlength,objectvalue);//实现的IComparable<T>泛型接口，在Array中搜索值。

publicstaticintBinarySearch<T>(T[]array,intindex,intlength,Tvalue);//Array设置为零、false或null，具体取决于元素类型。

publicstaticvoidClear(Arrayarray,intindex,intlength);//System.Array的浅表副本。

publicobjectClone();//从第一个元素开始复制Array中的一系列元素到另一Array中。

publicstaticvoidCopy(ArraysourceArray,ArraydestinationArray,intlength);//将一维Array的所有元素复制到指定的一维Array中。

publicvoidCopyTo(Arrayarray,intindex);//创建使用从零开始的索引、具有指定Type和维长的多维Array。

publicstaticArrayCreateInstance(TypeelementType,paramsint[]lengths);

//返回ArrayIEnumerator。

publicIEnumeratorGetEnumerator();//获取Array指定维中的元素数。

publicintGetLength(intdimension);//获取一维Array中指定位置的值。

publicobjectGetValue(intindex);//返回整个一维Array中第一个匹配项的索引。

publicstaticintIndexOf(Arrayarray,objectvalue);

//返回整个.Array中第一个匹配项的索引。

publicstaticintIndexOf<T>(T[]array,Tvalue);//返回整个一维Array中最后一个匹配项的索引。publicstaticintLastIndexOf(Arrayarray,objectvalue)；//反转整个一维Array中元素的顺序。publicstaticvoidReverse(Arrayarray);//设置给一维Array中指定位置的元素。publicvoidSetValue(objectvalue,intindex);//对整个一维Array中的元素进行排序。publicstaticvoidSort(Arrayarray);}5.5广义表一个广义表是零个或者多个原子或者子表构成的有限序列。一个不空的广义表记作L=(d1,d2,…,dn)，其中di可以是单元素（原子），也可以是广义表，称为广义表的子表。n称为广义表的长度。d1称为表头，(d2,…,dn)成为表尾。广义表简称表或者列表。在线性表中，所有元素具有相同的类型。而在广义表中，每个元素可以是单个元素，也可以是一个广义表。广义表的例子A=()是一个空表；

B=(6,2)是长度为2的广义表。

C=(‘a’,(5,3,‘x’))是长度为2的表。

D=(B,C,A)是长度为3的表。

E=（B,D)是长度为2的表。

F=(4,F)是一个递归表。一个广义表的元素间不仅有次序关系，而且存在层次关系，即表的钳套深度。如B的深度为1，D的深度为3.F的深度为无穷大。（广义）表的图示表结点用圈表示，原子结点用方框表示构成一棵树广义表的运算创建空的广义表:initGList(&L);销毁广义表:destroyGList(&L);复制广义表:copyGList(&T,L);求广义表的长度:length(L);求广义表的深度:depth(L);求广义表的表头:getHead(L);求广义表的表尾:getTail(L);插入一个元素使其成为新的表头:insertFirst(&L,e);删除表头元素:deleteFirst(&L,&e);判断表是否空:isEmpty(L);广义表作为ADT

ADTGlist{

数据对象:D={ei|i=1,2,…,n;n0,eiAtomSet或eiGlist}

数据关系:R={(ei-1,ei)|eiD}

基本操作:initGList(&L);

操作结果:创建空表;destroyGList(&L);

初始条件:广义表L已存在操作结果:销毁广义表….}//Glist;广义表的存储顺序结构不适用,因为表中元素类型不同;采用类似于线性表的链式结构：L1=(5,12,’s’,47,’a’)L2=(5,(3,2,(14,9,3),(),4),2,(6,3,10))广义表的存储结构tagatom/hptptag=0:原子结点tag=1:表结点

结点格式：原子结点：原子信息表结点：指向表头结点的指针指向同层下一个结点的指针

0‘a’

1/\

05

03

0‘x’/\head广义表的链表表示typedefenum{ATOM,LIST}ElemTag;typedef

structGLNode{ElemTagtag;//标志原子或表结点

union{AtomTypeatom;//原子结点的值

structGLNode*hp;//表结点的表头指针

}；

structGLNode*tp;//指向下一个元素结点}*GList;//广义表类型是扩展的线性表求广义表的深度例如，对于广义表

E(B(a,b),D(B(a,b),C(u,(x,y,z)),A()))按递归算法分析：

Depth(E)=1+Max{Depth(B),Depth(D)}Depth(B)=1+Max{Depth(a),Depth(b)}=1Depth(D)=1+Max{Depth(B),Depth(C),Depth(A)}LS=(a1,a2,…,an)

Depth(C)=1+Max{Depth(u),Depth((x,y,z))}Depth(A)=1Depth(u)=0

Depth((x,y,z))=1+Max{Depth(x),

Depth(y),Depth(z)}=1Depth(C)=1+Max{Depth(u),Depth((x,y,z))}=1+Max{0,1}=2Depth(D)=1+Max{Depth(B),Depth(C),

Depth(A)}