数据结构-04串和数组

数据结构第四章串和数组第四章串和数组主要内容串的相关知识1数组的定义2特殊矩阵的数组存储3数组和串的应用4教学要求教学重点教学难点目标要求1．理解串的基本操作的定义；2.熟练掌握在串的顺序存储结构上实现串的各种操作的方法3.掌握朴素的模式匹配算法。4.了解数组的两种存储表示方法，并掌握数组的地址计算方法；5.了解稀疏矩阵的特点和压缩存储方法1.朴素的模式匹配运算2.掌握数组的存储方式，顺序存储的地址计算公式1.串的匹配运算算法2.稀疏矩阵压缩存储表示下实现的算法4.1串4.1.1串的定义串的值串的长度串的名串：是由计算机字符组成的有限序列。通常记为：s=‘c1c2c3…ci…cn’(n≥0)。字母、数字或其他字符必须有！但不属于串！作用：避免字符串与变量名或数的常量混淆。例：x=‘123’x=123test=‘test’空串：不含任何字符的串，长度n=0，用表示为表示为S=‘’。空格串：仅由一个或多个空格组成的串。4.1.2串间关系子串：S串中任意m（m≤n）个连续字符构成的串称为S的子串。主串：相对地，S称为主串。2.子串关系1.相等关系精确相等关系左对齐相等关系两串有相同的长度，且自左至右逐对对应字符相等时两串才为相等不要求两串有相同的长度自最左的第1个字符开始逐个对应字符比较当不等时，如何判断大小关系包含关系例：S=‘NanJing’S1=‘NanJing’S3=“NanJing”SS1SS2=例：S7=“Iamastudentnow.”，S8=“student”，S9=“student.”S7——主串S8——S7子串S9——非S7子串空串是任意串的子串，任意串是其自身的子串位置：字符在序列中的序号。子串在主串中的位置：子串的首字符在主串中的位置。在S中的位置：8非串S中的连续字符所组成4.1.3串的基本操作•1串赋值•2串精确相等•3串左对齐相等•4求串长度•5取子串•6串匹配•7并串•8串置换•9串插入•10串删除4.1.4串的存储结构串的存储结构与线性表的存储结构十分相似。区别是：串的数据元素在任何情况下仅是一个单个字符顺序存储结构静态顺序存储结构（顺序串）动态顺序存储结构一次性为串分配好足够的存储单元块链式存储结构堆存储结构（堆串）随时扩充和释放空间顺序串#defineM100typedefstruct{charch[M]；intn；}SSTR；堆串typedefstruct{char*ch；intlen；}HSTR；串的实际长度可在这个预定义长度范围内随意设定，超出则被截断以一个特殊的字符作为字符串的结束标志，串长是一个隐含值3.1.5关于串的几个算法串的基本操作和线性表有很大差别线性表：大多以“单个元素”作为操作对象串：通常以“串的整体”作为操作对象如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。3.1.5关于串的几个算法1.判串精确相等EQUAL（S，Q）串S：串Q：student.studunt,S.nQ.nintEQUAL(SSTRS,SSTRQ){inti;if(S.n!=Q.n)return0;else{for(i=0;S.ch[i]==Q.ch[i];i++);if(i=S.n-1)return(1);elsereturn(0);}}i=0i=0i=1i=1i=2i=2i=3i=3i=4i=4字符不等返回i与S.n比较3.1.5关于串的几个算法2.取子串SUBSTR（S,pos,len）求子串的过程：为复制字符序列的过程将串S中的第pos个字符开始的长度为len的字符串复制到串Sub中。datastructure主串S：子串Q：posalenkkksktkrkukci=0i=7\0可能出现“参数非法”的情况，应返回ERROR3.1.5关于串的几个算法3.串匹配MATCH(S,T)就是在主串中找出子串出现的位置如果在主串S中能够找到子串T，则称匹配成功，返回第一个和子串T中第一个字符相等的字符在主串S中的序号；否则，称匹配失败，返回0。简单匹配算法或朴素匹配算法匹配过程是一个字符比较的过程cdcbabbaacdbai匹配j不匹配jcdbai匹配j不匹配jicdba不匹配jicdba不匹配jicdba匹配j匹配j匹配j匹配jcdbai=i-j+2返回此元素序号3.1.5关于串的几个算法4.并串串S值Q.len+T.lenMAXSTRLENQ.lenMAXSTRLENQ.len+T.lenMAXSTRLENQ.len=MAXSTRLEN结果正确：Q和T全部字符结果T被“截断”结果S=Q或者S=Q的前半部分在串的静态顺序存储结构上实现CONCAT(S,Q,T)，需考虑可能出现的三种情况：采用串的堆存储结构上实现CONCAT(S,Q,T)，不存在串连接时被截断的问题4.2数组数组是同类数据元素的有序排列。4.2.1数组的定义相同数据类型、相同的存储空间大小数组元素：组成数组的数据元素指数据元素的存储和排列有固定的规则一维数组二维数组三维数组...多维数组intsz[M]={0，1，2，3，4};M为最多数组元素个数sz为数组名数组类型为整数注意：C语言规定数组元素号从0起始，到M-1为止(一般从1数数到M)数组元素4.2.2一维数组又称向量，是一个顺序表结构数组元素即是顺序表的数据元素或结点声明格式：数据类型变量名称[长度]；例如：intsz[M]={0，1，2，3，4};存储位置地址(表示为sz[i]的形式)计算公式为sz[i]=A+i×b数组存储空间起始地址第i号数组元素元素存储为b个字节若一维数组中的数据元素又是一维数组结构二维数组三要素便可随时求出任一元素的地址：①开始结点的存放地址（即基地址）②维数和每维的上、下界；③每个数组元素所占用的单元数4.2.3二维数组又称矩阵，是在横竖两个方向上排列数组元素构成的数组声明格式：数据类型变量名称[长度][长度]；例如：intewsz[N][M]（N为行数，M为列数）行列二维数组看成一个一维数组例如：sz[4]={sz[0]，sz[1]，sz[2]，sz[3]};wsz[4][5]e191817161514131211109876543210sz[0]sz[1]sz[2]sz[3]szi=(a0j,a1j,…,am-1,j)0≤j≤N-1二维数组顺序存储位置地址(表示为ewsz[i]的形式)计算公式为数组存储空间起始地址第i号数组元素每行M个元素元素存储为b个字节根据一维数组地址公式ewsz(i)=A+i×（M×b）ewsz[i][j]=(A+i×（M×b）)+j×b=A+i×M×b+j×b=A+（i×M+j）×b某个元素的地址就是它前面所有行所占的单元加上它所在行前面所有列元素所占的单元数之和am-1,n-1……..am-1,1am-1,0……….a1,n-1……..a11a10a0,n-1…….a01a0001n-1m*n-1na00a01……..a0,n-1a10a11……..a1,n-1am-1,0am-1,1……..am-1,n-1………………….例如：设数组A[0…59,0…69]的基地址为2048，每个元素占2个存储单元，顺序存储，则元素A[31,57]的存储地址为。解：ewsz[i][j]=ewsz[31][57]=A（i×M+j）×b=2048+(31×70＋57)×2=6502a00a01…a0,69a10a11…a1,69a59,0a59,1…a59,69………a31,57………………………………4.3特殊矩阵的数组存储矩阵的常规存储的特点：可以对其元素进行随机存取；矩阵运算非常简单；存储的密度为1。不适宜常规存储的矩阵：值相同的元素很多且呈某种规律分布；零元素多。矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。特殊矩阵稀疏矩阵三角形矩阵对角线矩阵对称矩阵4.3.1对角线矩阵的数组表示对角线矩阵是除矩阵主对角线上的元素外，其余所有元素的值都是0的矩阵。nn2211a0a0a将其压缩存储到一维数组中，且能找到每个非零元素和向量下标的对应关系定义为intdjxsz[n]当i=j时，djx(i,j)=djxsz[i]当i≠j时，djx(i,j)=0。第i个元素的存储地址的计算公式是：djx（i，i）=djxsz[i]=A+i×b各参数含义同前面4.3.2三角形矩阵的数组表示以主对角线划分，三角矩阵有上（下）三角两种。上（下）三角矩阵的下（上）三角（不含主对角线）中的元素均为常数(通常为0)。nnn222n11211a00aa0aaann2n1n222111aaa0aa00a上三角矩阵下三角矩阵三角矩阵的存储：存储主对角线和上（下）三角中的元素。用一维数组sjxsz[M]存储，其中M=n(1+n)/2对称矩阵上下三角中的元素数均为：1+2+…+n=n(1+n)/2=n(n+1)/2k=0123n(n-1)/2n(n+1)/2－1a11a21a22a31a32…an1…ann如：一维数组sjxsz[M]存储下三角矩阵存储地址计算公式sjx(i,j)=sjx(i,j)=sjxsz[k+j]=A+(i(i-1)/2+j-1)b各参数含义同前面k=1+2+…+(i-1)=(1+(i-1))(i-1)/2=i(i-1)/24.3.3对称矩阵的数组表示数据元素值以主对角线为对称轴对应相等nnnnnnaaaaaaaaa212222111211存储对称矩阵忽略主对角线上方的所有数据元素或忽略主对角线下方的所有数据元素下三角形矩阵上三角形矩阵满足aij=aji对称矩阵上下三角中的元素数均为：n(n+1)/24.3.4稀疏矩阵的数组表示稀疏矩阵是0元素较多，且出现位置无固定规律的矩阵060000900000004007200010003005M压缩存储原则：存各非零元的值、行列位置和矩阵的行列数例如：5×6的稀疏矩阵，只有8个非0元素用形如（行号,列号,元素值）的三元组表示之,一般表示为（i,j,v）ijv该非零元素的值该非零元素的列号该非零元素的行号三元组表结点：用三元组线性表表示：{{1,1,5},{1,4,3},{2,2,1},{3,1,7},{2,6,2}{3,4,4},{4,6,9},{5,5,6}}三元组线性表结构示意图C语言描述：typedefstruct{inti，j；intv；}JZNODE；typedefstruct{intn，m，k；JZNODEnode[10]；}SPMTX；4.3.5稀疏矩阵的转置算法对一个n×m的矩阵M，执行转置运算后的结果MT是一个m×n矩阵元素关系是MT（i,j）=M（j,i）060000900000004007200010003005M090206000000403000000001000705MT转置后转置后060000900000004007200010003005Mijv012345678568115143221262317344469556M.data090206000000403000000001000705MTijv012345678658115137221413434556622649MT.data解决思路：将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使T.data中元素以T的行(M的列)为主序。MT.dataijv01234567811541322162213743464955