Data StructureData Structure第五章第五章 数组和广义表数组和广义表q学习目标学习目标v理解理解多维数组类型多维数组类型的特点及其在高级编程语言中的的特点及其在高级编程语言中的存储表示和实现存储表示和实现方法方法，并掌握数组在，并掌握数组在“以行为主以行为主”的存储表示中的地址计算方法。的存储表示中的地址计算方法。v掌握掌握特殊矩阵的存储压缩特殊矩阵的存储压缩表示方法。表示方法。v理解理解稀疏矩阵稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。q重点和难点重点和难点v重点是学习重点是学习数组类型数组类型的定义及其的定义及其存储表示存储表示。q知识点知识点v数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法随机稀疏矩阵的压缩存储表示方法。9/18/20241Data StructureData Structure5.1 5.1 数组的定义数组的定义q数组是线性表的推广数组是线性表的推广v数组可以看成是一种数组可以看成是一种特殊的线性表特殊的线性表，即线性表中，即线性表中数据元素本身也数据元素本身也是一个线性表是一个线性表。列向量列向量行向量行向量9/18/20242Data StructureData Structure数组的抽象数据类型定义数组的抽象数据类型定义ADTADT Array Array 数据对象数据对象：j ji i=0,., b=0,., bi i-1, i=1,2,.,n-1, i=1,2,.,n D Daaj1,j2,.j1,j2,.jnjn|n|n(0)(0)为数组的维数，为数组的维数，b bi i为数组第为数组第i i维的长度，维的长度， j ji i为为数组元素的第数组元素的第i i维下标，维下标， a aj1,j2,.j1,j2,.jnjn ElemSetElemSet 数据关系数据关系：R RR1, R2, ., R1, R2, ., RnRn RiRi a | |0j0jk kbbk k-1, 1kn -1, 1kn 且且k k i,i,0j0ji ibbi i-2,-2,a aj1,j1,，jiji, , ,jnjn, a, aj1,j1,，ji+1, ,ji+1, ,jnjn D, i=2,.,n D, i=2,.,n 9/18/20243Data StructureData Structure基本操作基本操作基本操作基本操作InitArray(&AInitArray(&A, n, bound1, ., , n, bound1, ., boundnboundn) )操作结果：若维数操作结果：若维数 n n 和各维长度合法，则构造相应的数组和各维长度合法，则构造相应的数组A A。DestroyArray(&ADestroyArray(&A) )初始条件：数组初始条件：数组 A A 已经存在。已经存在。操作结果：销毁数组操作结果：销毁数组 A A。Value(A, &e, index1, ., Value(A, &e, index1, ., indexnindexn) )初始条件：初始条件：A A 是是 n n 维数组，维数组，e e 为元素变量，随后是为元素变量，随后是 n n 个下标值。个下标值。操作结果：若各下标不超界，则操作结果：若各下标不超界，则e e赋值为所指定的赋值为所指定的A A的元素值，并返回的元素值，并返回OKOK。Assign(&A, e, index1, ., Assign(&A, e, index1, ., indexnindexn) )初始条件：初始条件：A A 是是 n n 维数组，维数组，e e 为元素变量，随后是为元素变量，随后是 n n 个下标值。个下标值。操作结果：若下标不超界，则将操作结果：若下标不超界，则将 e e 的值赋给的值赋给A A中指定下标的元素。中指定下标的元素。 ADT Array ADT Array9/18/20244Data StructureData Structure5.2 5.2 5.2 5.2 数组的顺序表示和实现数组的顺序表示和实现数组的顺序表示和实现数组的顺序表示和实现q用用一组连续的存储单元一组连续的存储单元来表示数组。来表示数组。q有两种映象方法：有两种映象方法：v“以行以行( (序序) )为主为主( (序序) )” ” ：对二维数组进行：对二维数组进行 按行切分按行切分 ，即将数组，即将数组中的数据元素中的数据元素 按行依次排放按行依次排放 在存储器中；在存储器中；v“以列以列( (序序) )为主为主( (序序) )”对二维数组进行对二维数组进行 按列切分按列切分 ，即将数组中，即将数组中的数据元素的数据元素 按列依次排放按列依次排放 在存储器中。在存储器中。9/18/20245Data StructureData Structure按行序为主序存放按行序为主序存放 am-1,n-1 . am-1,1 am-1,0 a1,n-1 . a11 a10 a0,n-1 . a01 a0001n-1m*n-1n9/18/20246Data StructureData Structure 按列序为主序存放按列序为主序存放按列序为主序存放按列序为主序存放am-1 ,n-1 . a1,n-1 a0,n-1 .am-1,1 . a11a01 am-1,1 .a10a0001m-1m*n-1m9/18/20247Data StructureData Structure按行序为主序存放按行序为主序存放 am-1,n-1 . am-1,1 am-1,0 a1,n-1 . a11 a10 a0,n-1 . a01 a0001n-1m*n-1nv 每个数据元素占每个数据元素占L L个存储单元个存储单元; ;v LOC(0,0) LOC(0,0)表示数据元素表示数据元素a a0000的存储地址，的存储地址， 是数组的起始地址（基地址）是数组的起始地址（基地址）; ;v LOC(i,j) LOC(i,j)表示下标为表示下标为(i,j)(i,j)的数据元素的数据元素 a aijij的存储地址的存储地址 LOC(i,j)=LOC(0,0)+(i*n+j)*LLOC(i,j)=LOC(0,0)+(i*n+j)*L9/18/20248Data StructureData Structure 按列序为主序存放按列序为主序存放按列序为主序存放按列序为主序存放am-1 ,n-1 . a1,n-1 a0,n-1 .am-1,1 . a11a01 am-1,1 .a10a0001m-1m*n-1mv 每个数据元素占每个数据元素占L L个存储单元个存储单元; ;v LOC(0,0) LOC(0,0)表示数据元素表示数据元素a a0000的存储地址，的存储地址， 是数组的起始地址（基地址）是数组的起始地址（基地址）; ;v LOC(i,j) LOC(i,j)表示下标为表示下标为(i,j)(i,j)的数据元素的数据元素 a aijij的存储地址的存储地址 LOC(i,j)=LOC(0,0)+(j*m+i)*LLOC(i,j)=LOC(0,0)+(j*m+i)*L9/18/20249Data StructureData Structure5.3 5.3 矩阵的压缩存储矩阵的压缩存储q压缩存储压缩存储v为多个为多个值相同的矩阵元只分配一个存储空间值相同的矩阵元只分配一个存储空间；对；对零元不分配空间零元不分配空间。9/18/202410Data StructureData Structure5.3.1 5.3.1 5.3.1 5.3.1 特殊矩阵特殊矩阵特殊矩阵特殊矩阵q特殊矩阵特殊矩阵v值相同的元素或者零元素在矩阵中的值相同的元素或者零元素在矩阵中的分布有一定规律分布有一定规律。对称矩阵对称矩阵 n n阶矩阵；阶矩阵； a aijij= =a ajiji1 1 i,j i,j n n9/18/202411Data StructureData Structureq特殊矩阵特殊矩阵v值相同的元素或者零元素在矩阵中的值相同的元素或者零元素在矩阵中的分布有一定规律分布有一定规律。三角矩阵三角矩阵 n n阶矩阵；阶矩阵； 下下（上上）三角矩阵：矩阵的）三角矩阵：矩阵的上上（下下）三角（不）三角（不 包括对角线）中的元均为包括对角线）中的元均为常数常数c c或零。或零。9/18/202412Data StructureData Structureq特殊矩阵特殊矩阵v值相同的元素或者零元素在矩阵中的值相同的元素或者零元素在矩阵中的分布有一定规律分布有一定规律。对角矩阵对角矩阵 n n阶矩阵；阶矩阵； 所有的所有的非零元都非零元都集中集中在以主对角线为中心的带状区域中在以主对角线为中心的带状区域中。9/18/202413Data StructureData Structure压缩存储压缩存储对称矩阵对称矩阵按行序为主序：按行序为主序：仅存储下仅存储下三角三角a11a12.a1na21a22.a2nan1an2.ann.annan1a32a31a22a21a114321k=09/18/202414Data StructureData Structure压缩存储压缩存储下三角矩阵下三角矩阵a1111.1a21a221.1an1an2an3.ann.1按行序为主序：按行序为主序：annan1a32a31a22a21a11仅存储下仅存储下三角三角14321k=09/18/202415Data StructureData Structure压缩存储压缩存储对角矩阵对角矩阵a11a120.0a21a22a230000an-1,n-2an-1,n-1an-1,n00an,n-1an,n0a32a33a3400仅存储主对仅存储主对角线非角线非0元元素素按行序为主序：按行序为主序：an,nan,n-1a23a22a21a12a114321k=09/18/202416Data StructureData Structure5.3.2 5.3.2 稀疏矩阵稀疏矩阵q稀疏矩阵稀疏矩阵v非零元较零元少非零元较零元少，且，且分布没有一定规律分布没有一定规律的矩阵。的矩阵。v压缩存储原则：只存矩阵的压缩存储原则：只存矩阵的行列维数行列维数和每个和每个非零元的行列下标及其值非零元的行列下标及其值。v 矩阵维数矩阵维数（6,76,7）v 非零元非零元(1,2,12)(1,2,12)(1,3,9)(1,3,9)(3,1,-3)(3,1,-3)(3,6,14)(3,6,14)(4,3,24)(4,3,24)(5,2,18)(5,2,18)(6,1,15)(6,1,15)(6,4,-7) (6,4,-7) 9/18/202417Data StructureData Structure压缩存储压缩存储稀疏矩阵稀疏矩阵( (三元组顺序表三元组顺序表) )q以以顺序存储结构顺序存储结构来表示三元组。来表示三元组。q稀疏矩阵的三元组顺序表存储表示稀疏矩阵的三元组顺序表存储表示#define MAXSIZE 12500 /假设非零元个数的最大值为假设非零元个数的最大值为12500typedef structint i,j; /该非零元的行下标和列下标该非零元的行下标和列下标ElemType e;Triple;typedef structTriple dataMAXSIZE+1; /非零元三元组表，非零元三元组表，data0未用未用int mu,nu,tu; /矩阵的行数、列数和非零元个数矩阵的行数、列数和非零元个数TSMatrix ; 行序行序9/18/202418Data StructureData Structure678121213931-3361443245218611564-7dataije01234567行列下标行列下标非零元值非零元值data0.i,data0.j,datadata0.i,data0.j,data0.e0.e分别存放矩阵行列维分别存放矩阵行列维数和非零元个数数和非零元个数9/18/202419Data StructureData Structure求转置矩阵求转置矩阵q问题描述问题描述v已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。q解决思路解决思路v将矩阵行、列维数互换；将矩阵行、列维数互换；v将每个三元组中的将每个三元组中的i i和和j j相互调换相互调换；v重排三元组次序。重排三元组次序。9/18/202420Data StructureData Structure678121213931-3361443245218611564-7ije01234567M.dataije76813-3161521122518319342446-7631401234567T.data?9/18/202421Data StructureData Structureq方法一：按矩阵方法一：按矩阵的列序转置的列序转置v按按T.dataT.data中三元组次序中三元组次序依次在依次在M.dataM.data中找到相应的三元组进行中找到相应的三元组进行转置转置。678121213931-3361443245218611564-7ije012345678M.data76813-3161521122518319342446-76314ije012345678T.dataqppppppppqqqqppppppppcol=1col=29/18/202422Data StructureData Structure算法算法算法算法5.15.15.15.1Status Status TransposeSMatrix(TSMatrixTransposeSMatrix(TSMatrix M, M, TSMatrixTSMatrix &T) &T)/采用三元组表存储表示，求稀疏矩阵采用三元组表存储表示，求稀疏矩阵M M的的转置矩阵转置矩阵T T。T.muT.mu= =M.nuM.nu; ; T.nuT.nu= =M.muM.mu; ; T.tuT.tu= =M.tuM.tu; ; /T/T的维数和非零元个数的维数和非零元个数if(T.tuif(T.tu)/M/M存在非零元存在非零元q=1; q=1; /T/T的序号的序号for(colfor(col=1;col=1;col=M.nu;+colM.nu;+col) ) /扫描所有列扫描所有列 for(p=1;p=for(p=1;p=M.tu;+pM.tu;+p) ) /扫描每个三元组扫描每个三元组if(M.datap.j = if(M.datap.j = colcol)/交换交换 T.dataq.i=M.datap.j;T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; T.dataq.e=M.datap.e; +q; +q; return OK;return OK;/TransposeMatrixTransposeMatrix 时间复杂度为时间复杂度为O(nuO(nu tutu) )适用于适用于tutumumu* *tutu9/18/202423Data StructureData Structureq方法二：按矩阵方法二：按矩阵的的行行序转置序转置v按按M.dataM.data中三元组次序转置中三元组次序转置，转置结果放入，转置结果放入T.dataT.data中恰当位置中恰当位置。v此法此法关键关键是要预先确定是要预先确定M.dataM.data中每一列第一个非零元在中每一列第一个非零元在T.dataT.data中位中位置置。v为确定这些位置，转置前应先求得为确定这些位置，转置前应先求得M.dataM.data的每一列中非零元个数的每一列中非零元个数。9/18/202424Data StructureData Structure678121213931-3361443245218611564-7ije012345678M.dataije012345678T.datacolnumcolcpotcol11223235247158068179076813-3161521122518319342446-76314pppppppp462975389/18/202425Data StructureData Structure算法算法算法算法5.25.25.25.2Status Status FastTransposeSMatrix(TSMatrixFastTransposeSMatrix(TSMatrix M, M, TSMatrixTSMatrix &T) &T)/采用三元组表存储表示，求稀疏矩阵采用三元组表存储表示，求稀疏矩阵M M的转置矩阵的转置矩阵T T。T.muT.mu= =M.nuM.nu; ; T.nuT.nu= =M.muM.mu; ; T.tuT.tu= =M.tuM.tu; ; /T/T的维数和非零元个数的维数和非零元个数if(T.tuif(T.tu)/M/M存在非零元存在非零元for(colfor(col=1;col=1;col=M.nu;+colM.nu;+col) ) numcolnumcol=0;=0;for(t=1;t=for(t=1;t=M.tu;+tM.tu;+t) +numM.datat.j; ) +numM.datat.j; /M/M每一列非零元个数每一列非零元个数cpot1=1;cpot1=1;/求第求第colcol列中第一个非零元在列中第一个非零元在b.datab.data中的序号中的序号for(colfor(col=2;col=2;col=M.nu;+colM.nu;+col) ) cpotcolcpotcol=cpotcol-1+numcol-1;=cpotcol-1+numcol-1;for(p=1;p=for(p=1;p=M.tu;+pM.tu;+p) colcol=M.datap.j; q=M.datap.j; q=cpotcolcpotcol; T.dataq.i= M.datap.j; T.dataq.j= M.datap.i; T.dataq.i= M.datap.j; T.dataq.j= M.datap.i; T.dataq.e= M.datap.e; T.dataq.e= M.datap.e; +cpotcolcpotcol; /for/for /if/ifreturn OK;return OK;/FastTransposeMatrixFastTransposeMatrix时间复杂度为时间复杂度为O(nuO(nu+tu+tu) )用空间换取用空间换取时间时间9/18/202426Data StructureData Structure三元组顺序表的特点三元组顺序表的特点q优点优点v非零元在表中按行序有序存储，便于进行依行序处理的矩阵运算。非零元在表中按行序有序存储，便于进行依行序处理的矩阵运算。q缺点缺点v若需按行号存取某一行的非零元，则需从头开始进行查找。若需按行号存取某一行的非零元，则需从头开始进行查找。9/18/202427Data StructureData Structure压缩存储压缩存储稀疏矩阵稀疏矩阵( (行逻辑链接的顺序表行逻辑链接的顺序表) )q为了便于随机存储任意一行的非零元，需要知道每一行的为了便于随机存储任意一行的非零元，需要知道每一行的第一个非零元在三元组表中的位置。第一个非零元在三元组表中的位置。v解决方法：将解决方法：将cpot固定在稀疏矩阵的存储结构中。固定在稀疏矩阵的存储结构中。#define MAXSIZE 12500 /假设非零元个数的最大值为假设非零元个数的最大值为12500typedef structint i,j; /该非零元的行下标和列下标该非零元的行下标和列下标ElemType e;Triple;typedef structTriple dataMAXSIZE+1; /非零元三元组表，非零元三元组表，data0未用未用 int rposMAXRC+1; /各行第一个非零元的位置表各行第一个非零元的位置表int mu,nu,tu; /矩阵的行数、列数和非零元个数矩阵的行数、列数和非零元个数RLSMatrix ; 9/18/202428Data StructureData Structure34411314522-1312ije01234M.data42412221131-2324ije01234N.data32312621-1324ije0123Q.data矩阵乘法运算矩阵乘法运算如何如何求？求？9/18/202429Data StructureData Structure0 00 00 00 00 00 0ctempctemp累加器累加器矩阵Q的rposrow123rposrow1p pp pp2pp312621-1324ije0123Q.data431rposrow321row矩阵M的rpos54321rposrow321row矩阵N的rpos11314522-1312ije01234M.data34412221131-2324ije01234N.data424320arow=1arow=2arow=36-149/18/202430Data StructureData StructureStatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q)/求矩阵乘积Q=M*N，采用行逻辑链接存储表示if(M.nu!=N.mu)returnERROR;/两个矩阵无法进行相乘Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;/Q初始化if(M.tu*N.tu!=0)/Q是非零矩阵for(arow=1;arow=M.mu;+arow)/处理M的每一行ctemp=0;/当前行各元素累加器清零Q.rposarow=Q.tu+1;if(arowM.mu)tp=M.rposarow+1;/M下一行第一个元素地址elsetp=M.tu+1;for(p=M.rposarow;ptp;+p)/当前行中每个非零元素找到brow=M.datap.j;/对应元在N中的行号if(browN.mu)t=N.rposbrow+1;/N下一行第一个元素地址elset=N.tu+1;for(q=N.rposbrow;qt;+q)ccol=N.dataq.j;/乘积元素在Q中的列号ctempccol+=M.datap.e*N.dataq.e;/for/求得Q中第crow(=arow)行的非零元for(ccol=1;ccolMAXSIZE)returnERROR;Q.dataQ.tu=(arow,ccol,ctempccol);/if/forarow/ifreturnOK;/MultSMatrix时间复杂度为时间复杂度为O(O(M.mu*N.nu+M.tu*N.tu/N.mu) )9/18/202431Data StructureData Structure压缩存储压缩存储稀疏矩阵稀疏矩阵( (十字链表十字链表) )q引入原因引入原因v当矩阵的非零元的个数发生变化时，当矩阵的非零元的个数发生变化时，不宜采用三元组表。如不宜采用三元组表。如A=A+BA=A+B，非零元的插入或删除将会引起非零元的插入或删除将会引起A.dataA.data中的数据移动，这是顺序中的数据移动，这是顺序结构三元组的弱势。结构三元组的弱势。q十字链表结点形式十字链表结点形式ijedownright非零元的非零元的行、列、行、列、值值同一列下同一列下一个非零一个非零元元同一行下同一行下一个非零一个非零元元typedefstructOLNodeinti,j;ElemTypee;structOLNode*right,*down;OLNod,*OLink;typedefstructOlink*rhead,*chead;intmu,nu,tu;CrossList;9/18/202432Data StructureData Structure113418225234M.cheadM.rhead列链表头列链表头指针指针行链表头行链表头指针指针9/18/202433Data StructureData Structure建立十字链表的算法建立十字链表的算法5.45.4418234m=4,n=3,t=51132172251,1,32,2,52,3,44,1,82,1,7M.rheadM.cread9/18/202434Data StructureData StructureStatusCreateSMatrix_OL(CrossList&M)/创建稀疏矩阵M，采用十字链表存储表示if(M)free(M);scanf(&m,&n,&t);/输入M的行数、列数和非零元个数M.mu:=m;M.nu:=n;M.tu:=t;if(!(M.rhead=(OLink*)malloc(m+1)*sizeof(OLink)exit(OVERFLOW);if(!(M.chead=(OLink*)malloc(n+1)*sizeof(OLink)exit(OVERFLOW);M.rhead=M.chead=NULL;/初始化行、列头指针向量；各行列链表为空链表for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)/按任意次序输入非零元if(!(p=(OLNode*)malloc(sizeof(OLNode)exit(OVERFLOW);p-i=i;p-j=j;p-e=e;/生成结点if(M.rheadi=NULL|M.rheadi-jj)p-right=M.rheadi;M.rheadi=p;else/寻查在行表中的插入位置for(q=M.rheadi;(q-right)&q-right.jright);p-right=q-right;q-right=p;/完成行插入if(M.cheadj=NULL|M.rheadj-ii)p-down=M.cheadj;M.rheadj=p;else/寻查在列表中的插入位置for(q=M.cheadj;(q-down)&q-down.idown);p-down=q-down;q-down=p;/完成列插入returnOK;/CreateSMatrix_OL时间复杂度为时间复杂度为O(O( t*s) ) ，s=max(m.n)9/18/202435Data StructureData StructurevoidOLMatrix_Add(CrossList&A,CrossListB)/把十字链表表示的矩阵B加到A上for(j=1;j=A.nu;j+)cpj=A.cheadj;/向量cp存储每一列当前最后一个元素的指针for(i=1;ijpb-j)/新插入一个结点p=(OLNode*)malloc(sizeof(OLNode);if(!pre)A.rheadi=p;elsepre-right=p;p-right=pa;pre=p;p-i=i;p-j=pb-j;p-e=pb-e;/插入行链表中if(!A.cheadp-j)A.cheadp-j=p;p-down=NULL;elsewhile(cpp-j-down)cpp-j=cpp-j-down;p-down=cpp-j-down;cpp-j-down=p;cpp-j=p;/插入列链表中/if9/18/202436Data StructureData Structureelseif(pa-jj)pre=pa;pa=pa-right;/pa右移一步elseif(pa-e+pb-e)pa-e+=pb-e;pre=pa;pa=pa-right;pb=pb-right;/直接相加elseif(!pre)A.rheadi=pa-right;elsepre-right=pa-right;p=pa;pa=pa-right;/从行链表中删除if(A.cheadp-j=p)A.cheadp-j=cpp-j=p-down;elsecpp-j-down=p-down;/从列链表中删除free(p);/else/while/for/OLMatrix_Add时间复杂度为时间复杂度为O(O( ta+tb) )9/18/202437Data StructureData Structure5.45.4广义表的定义广义表的定义q广义表广义表( (列表列表) )v是线性表的推广是线性表的推广，广泛地应用于人工智能等领域的表处理语言，广泛地应用于人工智能等领域的表处理语言LISPLISP语言。语言。v一般记作一般记作LS=(a1,a2,an)(n0)名称：名称：LS；长度：长度：n；原子：原子：ai是单个元素，一般用小写字母表示；是单个元素，一般用小写字母表示；子表：子表：ai是广义表，一般用大写字母表示。是广义表，一般用大写字母表示。表头表头(Head)：非空广义表非空广义表 LS的第一个数据元素的第一个数据元素a1；表尾表尾(Tail)：非空广义表非空广义表 LS除第一个数据元素除第一个数据元素外的外的其余数据其余数据元元 素构成的广义表素构成的广义表 (a2,an)。9/18/202438Data StructureData Structure特性特性A=()F=(b,(c,d,e)E=(b,(c),(d,e)D=(E,A,F)C=(A,D,F)B=(a,B)=(a,(a,(a,v.) 广义表中的数据元素有固定的相对次序；广义表中的数据元素有固定的相对次序； 广义表的元素可以是子表，而子表的元素还可以是子表。广义表的元素可以是子表，而子表的元素还可以是子表。 广义表可以为其它列表共享。广义表可以为其它列表共享。 广义表可以是一个递归的表。广义表可以是一个递归的表。广义表与数广义表与数组的区别组的区别9/18/202439Data StructureData Structure操作操作长度长度A=()F=(b,(c,d,e)E=(b,(c),(d,e)D=(E,A,F)C=(A,D,F)B=(a,B)=(a,(a,(a,v.)广义表中元素的广义表中元素的“长度长度 应由最外层括弧中的应由最外层括弧中的 逗号逗号 来定。来定。 A的长度为0F的长度为2E的长度为3D的长度为3C的长度为3B的长度为29/18/202440Data StructureData Structure操作操作取表头、取表尾取表头、取表尾 F=(b,(c,d,e)F=(b,(c,d,e)GetHead(F)=bGetTail(F)=(c,d,e)=F1GetHead(F1)=(c,d,e)=F2，GetTail(F1)=()GetHead(F2)=c，GetTail(F2)=(d,e)=F3GetHead(F3)=d，GetTail(F3)=(e)=F4GetHead(F4)=e，GetTail(F4)=()q 两个操作只对非空表有意义；两个操作只对非空表有意义；q 取表头的结果可能是原子，也可能是个广义表；取表头的结果可能是原子，也可能是个广义表；q 取表尾取表尾 必定必定 是个广义表，但可能是个空的广义表。是个广义表，但可能是个空的广义表。9/18/202441Data StructureData Structure5.5 5.5 广义表的存储结构广义表的存储结构q采用链式存储结构。采用链式存储结构。q广义表的结点广义表的结点v表结点表结点v原子结点原子结点表结点tag=1hptp原子结点tag=0atom标志标志域域标志标志域域表头指针表头指针表尾指针表尾指针值域值域9/18/202442Data StructureData StructureA=()B=(e)C=(a,(b,c,d)D=(A,B,C)E=(a,E)1 1 11111 1 1 11 0a0a0e0d0b0cABCDE1 9/18/202443Data StructureData Structure另一种结点结构另一种结点结构表结点tag=1hptp原子结点tag=0atomtp标志标志域域标志标志域域表头指针表头指针值域值域同层下一个元同层下一个元素指针素指针同层下一个元同层下一个元素指针素指针9/18/202444Data StructureData StructureA=()B=(e)C=(a,(b,c,d)D=(A,B,C)E=(a,E)1 1 1 1 1 11 0a0a0e 0d 0b0cBCDEA1 1 1 9/18/202445Data StructureData Structure本章小结本章小结q了解了解数组的类型定义数组的类型定义及其在高级语言中实现的方法。及其在高级语言中实现的方法。q数组的特点是一种多维的线性结构，并只进行存取或修改数组的特点是一种多维的线性结构，并只进行存取或修改某个元素的值，因此它只需要某个元素的值，因此它只需要采用顺序存储结构采用顺序存储结构。q介绍了介绍了稀疏矩阵的三种表示方法稀疏矩阵的三种表示方法。至于在具体应用问题中。至于在具体应用问题中采用哪一种表示法这取决于该矩阵主要进行什么样的运算。采用哪一种表示法这取决于该矩阵主要进行什么样的运算。q广义表是一种广义表是一种递归定义的线性结构递归定义的线性结构，因此它兼有线性结构，因此它兼有线性结构和层次结构的特点。和层次结构的特点。9/18/202446Data StructureData Structure基础知识题基础知识题(数组部分数组部分)q假设有二维数组假设有二维数组 A A6868，每个元素用相邻的每个元素用相邻的6 6个字节存储，个字节存储，存储器按字节编址。已知存储器按字节编址。已知A A的起始存储位置的起始存储位置( (基地址基地址) )为为 10001000，计算：，计算：v数组数组 A A 的存储）的存储）; ;v数组数组 A A 的最后一个元素的最后一个元素 a a5,75,7 的第一个字节的地址的第一个字节的地址; ;v按行存储时，元素按行存储时，元素 a a1,41,4 的第一个字节的地址的第一个字节的地址; ;v按列存储时，元素按列存储时，元素 a a4,74,7 的第一个字节的地址。的第一个字节的地址。9/18/202447Data StructureData Structureq假设按低下标优先存储整数数组假设按低下标优先存储整数数组A A93589358时，第一个元素时，第一个元素的字节地址是的字节地址是 100100，每个整数占四个字节。问下列元素的，每个整数占四个字节。问下列元素的存储地址是什么？存储地址是什么？(1) a(1) a00000000 (2) a(2) a11111111 (3) a(3) a31253125 (4) a(4) a82478247 q按高下标优先存储方式按高下标优先存储方式( (以最右的下标为主序以最右的下标为主序) )，顺序列出，顺序列出数组数组 A A22332233 中所有元素中所有元素 a ai,j,k,li,j,k,l，为了简化表达，可以为了简化表达，可以只列出只列出 (i,j,k,l) (i,j,k,l) 的序列。的序列。q设有上三角矩阵设有上三角矩阵( (a aijij) )nnnn，将其上三角元素逐行存于数组将其上三角元素逐行存于数组 Bm Bm 中中( m ( m 充分大充分大) ) ，使得，使得 Bk=Bk=a aijij 且且 k=fk=f1 1(i)+f(i)+f2 2(j)+c(j)+c。试推导出函数试推导出函数 f f1 1，f f2 2 和常数和常数 c (c (要求要求 f f1 1 和和 f f2 2 中不含常数项中不含常数项) )。9/18/202448Data StructureData Structureq设有三对角矩阵设有三对角矩阵( (a aijij) )nnnn，将其三条对角线上的元素存于将其三条对角线上的元素存于数组数组 B3n B3n 中，使得元素中，使得元素 Buv=Buv=a aijij，试推导出从试推导出从(i,j) (i,j) 到到(u(u，v) v) 的下标变换公式。的下标变换公式。q设有三对角矩阵设有三对角矩阵( (a aijij) )nnnn，将其三条对角线上的元素逐行将其三条对角线上的元素逐行地存于数组地存于数组 B3n-2 B3n-2 中，使得中，使得 Bk=Bk=a aijij，求：求：(1) (1) 用用 i,j i,j 表示表示 k k 的下标变换公式；的下标变换公式；(2) (2) 用用 k k 表示表示 i i，j j 的下标变换公式。的下标变换公式。9/18/202449Data StructureData Structure基础知识题基础知识题(广义表部分广义表部分)q求下列广义表操作的结果：求下列广义表操作的结果：vGetHead(p,h,wGetHead(p,h,w););vGetTail(b,k,p,hGetTail(b,k,p,h););vGetHead(a,b),(c,dGetHead(a,b),(c,d); ); vGetTail(a,b),(c,dGetTail(a,b),(c,d););vGetHead(GetTail(a,b),(c,dGetHead(GetTail(a,b),(c,d););vGetTail(GetHead(a,b),(c,dGetTail(GetHead(a,b),(c,d););vGetHead(GetTail(GetHead(a,b),(c,dGetHead(GetTail(GetHead(a,b),(c,d););vGetTail(GetHead(GetTail(a,b),(c,dGetTail(GetHead(GetTail(a,b),(c,d)。9/18/202450Data StructureData Structureq利用广义表的利用广义表的 GetHeadGetHead 和和 GetTailGetTail 操作写出函数表达式，操作写出函数表达式，把原子把原子 banana banana 分别从下列广义表中分离出来。分别从下列广义表中分离出来。vL1 = (apple,pear,banana,orange);L1 = (apple,pear,banana,orange);vL2 = (apple,pear),(banana,orange);L2 = (apple,pear),(banana,orange);vL3 = (apple),(pear),(banana),(orange);L3 = (apple),(pear),(banana),(orange);vL4 = (apple,(pear),(banana),(orange);L4 = (apple,(pear),(banana),(orange);vL5 = (apple),(pear),(banana),orange);L5 = (apple),(pear),(banana),orange);vL6 = (apple),pear),banana),orange);L6 = (apple),pear),banana),orange);vL7 = (apple,(pear,(banana),orange);L7 = (apple,(pear,(banana),orange);9/18/202451Data StructureData Structureq画出下列广义表的存储结构图。画出下列广义表的存储结构图。 v( ), a, (b, c), ( ), d), (e)( ), a, (b, c), ( ), d), (e)v(a), b), ( ), (d), (e, f) (a), b), ( ), (d), (e, f) q已知右侧各图为广义表的存储结构图，写出各图表示的广已知右侧各图为广义表的存储结构图，写出各图表示的广义表。义表。9/18/202452