吉林大学数据结构课件 第三章 数组、字符串

第三章数组、字符串3.1数组3.1.1数组的存储和寻址一维数组是若干个元素的一个有限序列。一维数组的元素都必须具有相同的类型，即每个数组元素都占据相同大小的存储空间。顺序方式存储每个元素都通过一个下标来指定，故一个一维数组对应一个下标函数.一维数组A[n]，每个数组元素占一个存储单元（不妨设为l个连续字节）.数组元素A[0]的首地址Loc(A[0])，则对于0≤i≤n-1一维数组对于一维数组而言，各元素按下标次序依次存放，如a[0]，a[1]，a[2]，…等等。数组中任一元素A[i]的地址可表示为：Loc(a[i])=Loc(a[0])+i*ll为每个元素占用存储空间的字节数。高维数组可以将其转化为一维数组，其存在两种存储方式：按行优先顺序和按列优先顺序。所谓按行优先顺序，就是将数组元素按行向量的顺序存储，第i+1个行向量存储在第i个行向量之后。换句话说，就是将数组转化为一维数组来考虑。2、二维数组[例]intx[2][3]/*它有2×3个数组元素*/x[0][0]x[0][1]x[0][2]x[1][0]x[1][1]x[1][2]按行优先顺序存放其存储分配顺序为：x[0][0]-x[0][1]-x[0][2]-x[1][0]-x[1][1]-x[1][2]x[0][0]x[0][1]x[0][2]x[1][0]x[1][1]x[1][2]二维数组可以看作是一种特殊的一维数组。[例]floata[3][4]（行优先）;b[0]a[0][0]a[0][1]a[0][2]a[0][3]b-b[1]a[1][0]a[1][1]a[1][2]a[1][3]b[2]a[2][0]a[2][1]a[2][2]a[2][3]二维数组元素a[i][j]的地址：Loc(a[i][j])=Loc(b[i])+j*CLoc(b[i])=Loc(b[0])+i*C’//C’=n*CLoc(a[i][j])=Loc(a[0][0])+i*n*C+j*C=Loc(a[0][0])+(i*n+j)*C[例]floata[3][4]C=4a[0][0]=0Loc(a[1][2])=a+(i*n+j)*C=a+(1*4+2)*4=a+243、三维数组多维数组元素在内存中的排序顺序为：第一维的下标变化最慢，最右边的下标变化最快。[例]floata[2][3][4];a[0][0][0]→a[0][0][1]→a[0][0][2]→a[0][0][3]→a[0][1][0]→a[0][1][1]→a[0][1][2]→a[0][1][3]→a[0][2][0]→a[0][2][1]→a[0][2][2]→a[0][2][3]→a[1][0][0]→a[1][0][1]→a[1][0][2]→a[1][0][3]a[1][1][0]→a[1][1][1]→a[1][1][2]→a[1][1][3]a[1][2][0]→a[1][2][1]→a[1][2][2]→a[1][2][3]三维数组A[m][n][p]中数组元素a[i][j][k]地址计算公式为：Loc(a[i][j][k])=Loc(a[0][0][0])+i*n*p*C+j*p*C+k*C[例]D[3][3][4]Loc(a[1][2][2])=a+i*n*p*C+j*p*C+k*C=a+(1*3*4+2*4+2)*4=a+88n维数组a[m1][m2]…[mn]求该数组的任一个元素a[i1][i2]…[in]的地址a[0][0][0]→a[0][0][1]→a[0][0][2]→a[0][0][3]→a[0][1][0]→a[0][1][1]→a[0][1][2]→a[0][1][3]→a[0][2][0]→a[0][2][1]→a[0][2][2]→a[0][2][3]→a[1][0][0]→a[1][0][1]→a[1][0][2]→a[1][0][3]a[1][1][0]→a[1][1][1]→a[1][1][2]→a[1][1][3]a[1][2][0]→a[1][2][1]→a[1][2][2]→a[1][2][3]n维数组可考虑为如下一维数组b1[m1]={a[0][m2]…[mn],…,a[m1-1][m2]…[mn]}b1[m1]看做一维数组，数组每个元素是一个n-1维数组（每个n-1维数组，包含m2*m3*…*mn个的数据元素,设C1=m2*m3*…*mn*C）b1[i1]=Loc(a)+i1*C1b1[1]a[0][0][0]→a[0][0][1]→a[0][0][2]→a[0][0][3]→a[0][1][0]→a[0][1][1]→a[0][1][2]→a[0][1][3]→a[0][2][0]→a[0][2][1]→a[0][2][2]→a[0][2][3]→a[1][0][0]→a[1][0][1]→a[1][0][2]→a[1][0][3]a[1][1][0]→a[1][1][1]→a[1][1][2]→a[1][1][3]a[1][2][0]→a[1][2][1]→a[1][2][2]→a[1][2][3]Loc(a[i1][i2]…[in])=b1[i1]+偏移//a[i1][i2]…[in])在n-1维数组中的偏移=loc(a)+i1*C1+偏移loc(a)+偏移=??=i1*C1+Loc(a[0][i2]…[in])b1[1]多维数组][]][[21nmmma中任一元素][]][[21niiia的存储地址为：11221*),,,0(),,,(CiiiLociiiLocnn11223**),,,0,0(CiCiiiLocn...1111***)0,,0(CiCiCiLocnnn211*******)0,,0(mmCimCiCiLocnnnn111(0,,0){(*)}*nnkpnkpkLocimiC所谓按列优先顺序，就是将数组元素按列向量的顺序存储，第i+1个列向量存储在第i个列向量之后。在FORTRAN语言程序设计中，数组是按列优先顺序存放的。二维数组A[m][n]LOC(A[i][j])=LOC(A[0][0])+j*m*c+i*c3.2矩阵矩阵是许多物理问题中出现的数学对象，是常用的数据组织方式。用二维数组来存放矩阵特殊矩阵：三角矩阵、对角矩阵、对称矩阵和稀疏矩阵等三角矩阵的压缩存储:考虑一个nn维下三角矩阵其第一行有1个非零元素第二行有2个非零元素…第n行有n个非零元素非零元素共有(1+2+…+n)=n(n+1)/2个。用大小为n(n+1)/2的一维数组来存储下三角矩阵假设映射采取按行优先，非零元素M(i,j)会映射到一维数组中的哪个元素？设元素M(i,j)前面有k个元素k=1+2+…+(i1)+(j1)=i(i1)/2+(j1)对角矩阵:采用一维数组d[n]来压缩存储对角矩阵，其中d[i]存储M[i,i]的值对称矩阵：M(i,j)与M(j,i)的信息相同，所以只需存储其上三角矩阵或下三角矩阵的元素信息。参照下三角矩阵的压缩存储方法稀疏矩阵◆定义：设矩阵Amn中非零元素的个数远远小于零元素的个数，则称A为稀疏矩阵。◆特点：零元素的分布一般没有规律。◆作用：解决空间浪费的问题。1三元组表将表示稀疏矩阵的非零元素的三元组结点按行优先的顺序排列，得到一个线性表，将此线性表用顺序存储结构存储起来，称之为三元组表。三元组结点ijaij500001002000000－300－605A＝[例]稀疏矩阵B[0]B[1]B[2]B[3]B[4]B[5]0021501333-6020-301035020三元组表50100-3000000200-600005A`＝[例]稀疏矩阵500001002000000－300－605A＝转置矩阵50100-3000000200-600005A`＝[例]稀疏矩阵500001002000000－300－605A＝b[0]b[1]b[2]b[3]b[4]b[5]005030-30101033532-601220a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30{SparseMatrixTb;//声明一个稀疏矩阵bb.Rows=Cols;//b的行数等于原矩阵的列数b.Cols=Rows;//b的列数等于原矩阵的行数b.Count=Count;//b与原矩阵的非零元素个数相同if（Count0）{//若有非零元素intBnumber=0;for（k=0;kCols;k++）//对b按行优先确认非零元素for（i=0;iCount;i++）//扫描原矩阵的三元组表if（smArray[i].col==k）{//是否有列为k的非零元素b.smArray[Bnumber].row=k;b.smArray[Bnumber].col=smArray[i].row;b.smArray[Bnumber].value=smArray[i].value;Bnumber++;}}returnb;//返回转置矩阵b}FORk=0TOn-1DOFORi=0TOcount-1DOIFcol(a[i])=kTHEN(row(b[j])←k.col(b[j])←row(a[i]).value(b[j])←value(a[i]).j←j+1.)005030-30101033532-601220a[0]00502120011033523-6003-30a[1]a[2]a[3]a[4]a[5]b[0]b[1]b[2]b[3]b[4]b[5]LEFTUPROWCOLVAL2十字链表矩阵的元素结构如下：分别表示该元素的左邻非零元素、上邻非零元素、所在的行、所在的列和它的值。[例]稀疏矩阵800070900004060032103210800070900004060032103210-1-1-1-1-1-1-1-1136214329347448字符串串的定义和操作●串的定义：串是零个或多个字符组成的有限序列。记为S＝“a0a1…an-1”串名串值串的长度●空串：长度为零的串称为空串。●空白串：由一个或多个空格组成的串称为空白串。子串：串中任意个连续字符组成的子序列称为该串的子串。主串：包含子串的串相应地称为主串。子串在主串中的位置：子串在主串中第一次出现时，子串第一个字符在主串中的序号。[例]A=“Thisisastring”B=“is”串的存储方式1串的顺序存储：把一个串所包含的字符序列相继存入连续的字节中●非紧缩格式//一个存储单元存放一个字符[例]S＝“a0a1…an-1”a0a1an-1Word0Word1Wordn-1…………a●紧缩格式//一个存储单元存放多个字符[例]S=“a0a1…an-1”//一个存储单元存放4个字符a1a4an-1Word0Word1……a0a2a3a5a6a7an-2Wordn/4-1……a2串的链式存储串的链接存储是把可用的存储空间分成一系列大小相同的结点，其中每个结点的结构为：（str,link）5china∧p●结点大小为4的链串Sc5hian∧●结点大小为1的链串•关系运算符，=，，=，==，!=的重载.•串拼接运算符的重载.•从start位置确定字符c的位置，函数intFind（charc，intstart）const•确定字符c最后一次出现的位置，函数intFindLast（charc）const•取子串，函数StringSubstr（intindex，intcount）const•在index处插入字符串s，函数voidInsert（constString&s，intindex）……模式匹配算法模式匹配的过程可简单描述如下：给定两个字符串S和P，其中目标S有n个字符，模式P有m个字符，mn。从S的给定位置（通常为S的第一个字符）开始，搜索模式P，如果找到，返回模式P的第一个字符在S中的位置；如果没找到（即S中没有