数据结构第九讲

数据结构第九讲第一页，共四十四页，2022年，8月28日数组1数组的定义和基本运算数组的特点是每个数据元素可以又是一个线性表结构。因此，数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。举例：第二页，共四十四页，2022年，8月28日第三页，共四十四页，2022年，8月28日其中，A是数组结构的名称，整个数组元素可以看成是由m个行向量和n个列向量组成，其元素总数为m×n。在C语言中，二维数组中的数据元素可以表示成a[表达式1][表达式2]，表达式1和表达式2被称为下标表达式，比如，a[i][j]。数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。二维数组结构的基本操作：（1）给定一组下标，修改该位置元素的内容Assign(A,item,index1,index2)（2）给定一组下标，返回该位置的元素内容Value(A,item,index1,index2)第四页，共四十四页，2022年，8月28日2数组的存储结构从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。然而，由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。举例：第五页，共四十四页，2022年，8月28日假设每个元素占L个存储单元，下面求地址公式第六页，共四十四页，2022年，8月28日第0行第1行第m-1行第0列第1列第m-1列LOC(i,j)=LOC(0,0)+(n*i+j)*LLOC(i,j)=LOC(0,0)+(m*j+i)*L第七页，共四十四页，2022年，8月28日3．矩阵的压缩存储矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由m×n个元素排成的m行（横向）n列（纵向）的表。下面就是一个矩阵：第八页，共四十四页，2022年，8月28日m×n的矩阵第九页，共四十四页，2022年，8月28日4特殊矩阵所谓特殊矩阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。对称矩阵的特点是aij=aji，比如，下面就是一个对称矩阵：第十页，共四十四页，2022年，8月28日第十一页，共四十四页，2022年，8月28日下（上）三角矩阵的特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。比如，下面是一个下三角矩阵：第十二页，共四十四页，2022年，8月28日对角矩阵的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。比如，下面就是一个3阶对角矩阵：第十三页，共四十四页，2022年，8月28日压缩：为多个值相同的元只分配一个存储空间，对零元不分配空间.对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。三种特殊矩阵的压缩方法：（1）对称矩阵对称矩阵的特点是aij=aji。一个n×n的方阵，共有n2个元素，而实际上在对称矩阵中有n(n-1)/2个元素可以通过其他元素获得。第十四页，共四十四页，2022年，8月28日压缩的方法是首先将二维关系映射成一维关系，并只存储其中必要的n(n+1)/2个（主对角线和下三角）元素内容，这些元素的存储顺序以行为主序。举例：假设定义一个数组型变量：intA[10];第十五页，共四十四页，2022年，8月28日设k是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置。注意第一元素放在a[0]。A[i,j],前i-1行元素的个数为i(i-1)/2,在第i行为第j个的次序为j，而A[1,1]放在a[0],所以k=i(i-1)/2+j-1,(i>=j),A[i,j],当i<j时，由于对称性，A[i,j]=A[j,i],即看A[j,i]放在什么位置，所以有上面的知识得到：k=j(j-1)/2+i-1,(i<j),第十六页，共四十四页，2022年，8月28日(2)下（上）三角矩阵下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在0单元，下三角和主对角上的元素从1号单元开始存放。举例：第十七页，共四十四页，2022年，8月28日设k是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置。对于任意的（i，j），在一维数组中的存放位置可利用下列公式求得：第十八页，共四十四页，2022年，8月28日（3）对角矩阵我们以三阶对角矩阵为例讨论一下它的压缩存储方法。对于对角矩阵，压缩存储的主要思路是只存储非零元素。这些非零元素按以行为主序的顺序，从下标为1的位置开始依次存放在一维数组中，而0位置存放数值0。第十九页，共四十四页，2022年，8月28日

下面我们讨论一下对于任意给定的（i，j），求得在一维数组中存储位置k的方法。注：该矩阵除第一行和最后一行外，每行有3个元素。前i-1行元素的个数：3*(i-1)-1;第i行，第j个位置在第i行的次序为：j-i+2故：k=3*(i-1)-1+j-i+2=3*(i-1)+j-i+1,当i-1<=j<=i+1第二十页，共四十四页，2022年，8月28日2.稀疏矩阵的压缩存储若一个m×n的矩阵含有t个非零元素，且t远远小于m*n，则我们将这个矩阵称为稀疏矩阵。举例：注：通常：t/(m*n)<=0.05时称为稀疏矩阵第二十一页，共四十四页，2022年，8月28日稀疏矩阵的压缩存储方法——三元组表示法。矩阵中的每个元素都是由行序号和列序号唯一确定的。因此，我们需要用三项内容表示稀疏矩阵中的每个非零元素，即形式为：(i,j,value)其中，i表示行序号，j表示列序号，value表示非零元素的值，通常将它称为三元。我们将稀疏矩阵中的所有非零元素用这种三元的形式表示，并将它们按以行为主的顺序存放在一个一维数组中，就形成了我们所说的三元组表示法。第二十二页，共四十四页，2022年，8月28日注：稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。例如（（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）这一对行，列值便可作为矩阵M的另一种描述第二十三页，共四十四页，2022年，8月28日//---------稀疏矩阵的三元组顺序表存储表示#defineMAXSIZE125000//最大的非零元素个数typedefstruct{inti,j;//行序号、列序号

ElemTypee;//非零元素值}Triple;typedefstruct{

Tripledata[MAXSIZE+1];//非零元素的三元组表，data[0]未用

intmu,nu,tu;//稀疏矩阵的行数、列数及非零元素个数}TSMatrix;第二十四页，共四十四页，2022年，8月28日那么求矩阵的转置？假设a和b是TSMatrix型的变量，分别表示矩阵M和T,如何a得到b?前两步很容易实现，关键是第三步，我们需要做如下三步：（1）矩阵的行列值互换；（2）将每个三元组中的i和j相互调换；（3）重排三元组之间的次序实现矩阵的转置；有两种处理办法：（1）按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置，即，按照矩阵M的列序来进行转置。其算法如下：第二十五页，共四十四页，2022年，8月28日StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//算法5.1//采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵Tintp,q,col;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;//第1，2步if(T.tu){q=1;for(col=1;col<=M.nu;++col)//第3步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;}第二十六页，共四十四页，2022年，8月28日}returnOK;}//TransposeSMatrix注：该算法仅适用于tu<<mu*nu的情况（2）按照a.data中的三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。提示：如果能预先确定矩阵M的每一列（T的每一行）的第一个非零元在b.data中的应有位置，则在对a.data中的三元组依次作转置时，便可直接放到b.data中的恰当位置，因此在转置前，映先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data中的应有位置。第二十七页，共四十四页，2022年，8月28日设num和cpot两个向量，num[col]表示矩阵M中第col列的非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置，显然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];2<=col<=a.nu;第二十八页，共四十四页，2022年，8月28日前面矩阵M，num和cpot的值如下所示：第二十九页，共四十四页，2022年，8月28日StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵Tintcol,t,p,q;intnum[20],cpot[20];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)//求M中每一列所含非零元的个数++num[M.data[t].j];cpot[1]=1;//求M中每一列的第一个非零元在b.data中的序号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];}//for}//ifreturnOK;}//FastTransposeSMatrix该转置方法称为快速转置，详细算法见课本P100第三十页，共四十四页，2022年，8月28日注：三元顺序表又称为有序的双下表法，其特点是：非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。对于稀疏矩阵的表示还有：行逻辑链接的顺序表和十字链表第三十一页，共四十四页，2022年，8月28日一、选择题1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。13B.33C.18D.403.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。A.BA+141B.BA+180C.BA+222D.BA+2254.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。A.808B.818C.1010D.1020答案：1B,3B,4B第三十二页，共四十四页，2022年，8月28日2.有一个二维数组A[1:6，0:7]每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：①-④：A．12B.66C.72D.96E.114F.120G.156H.234I.276J.282K.283L.288⑤：A．行与列的上界相同B.行与列的下界相同C.行与列的上、下界都相同D.行的元素个数与列的元素个数相同答案：2.1L，2.2J，2.3C，2.4I，2.5C第三十三页，共四十四页，2022年，8月28日5.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()。A.1175B.1180C.1205D.12106.有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（①）。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址是（②）和（③）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（④）和（⑤）。①-⑤:A.28B.44C.76D.92E.108F.116G.132H.176I.184J.188答案：5.A，6.1H，6.2C，6.3E，6.4A，6.5F第三十四页，共四十四页，2022年，8月28日7.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案：198B.195C.1979.二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]10.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i<j）的位置k的关系为()。A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i答案：7.B，9.B，10.B第三十五页，共四十四页，2022年，8月28日8.二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节；（2）A的第8列和第5行共占（）个字节；（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地址一致。供选择的答案：（1）A.90B.180C.240D.270E.540（2）A.108B.114C.54D.60E.150（3）A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]答案：8.1E，8.2A，8.3B第三十六页，共四十四页，2022年，8月28日11.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为()。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-112.A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。A.i（i-1）/2+jB.j（j-1）/2+iC.i（j-i）/2+1D.j（i-1）/2+113.设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为()。A.（i-1）*n+jB.（i-1）*n+j-1C.i*（j-1）D.j*m+i-1答案：11.B，12.B，13.A第三十七页，共四十四页，2022年，8月28日14.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。A.60B.66C.18000D.3315.数组A[0..4,-1..-3,5..7]中含有元素的个数（）。A.55B.45C.36D.1616.用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为()。A.j=r[j].nextB.j=j+1C.j=j->nextD.j=r[j]->next17.对稀疏矩阵进行压缩存储目的是（）。A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度答案：14.B，15.B，16.A，17.C第三十八页，共四十四页，2022年，8月28日二、填空题1.数组的存储结构采用_______存储方式。2.设二维数组A[-20..30,-30..20],每个元素占有4个存储单元,存储起始地址为200.如按行优先顺序存储,则元素A[25,18]的存储地址为_______；如按列优先顺序存储,则元素A[-18,-25]的存储地址为_______。3.设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_______;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_______。4.将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：_______。5.二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储)第三十九页，共四十四页，2022年，8月28日6.设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为_______。7.已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为_______。8.已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是：_______。9.用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j](1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A中的第_（1）_行，第_（2）_列的元素。11．设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为_______。第四十页，共四十四页，2022年，8月28日10.设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（l）存放该数组至少需要的单元数是_______;（2）存放数组的第8列的所有元素至少需要的单元数是_______;（3）数组按列存储时，元素A[5,8]的起始地址是_______。12.n阶对称矩阵a满足a[i][j]=a[j