第6讲+字符串、数组和特殊矩阵

第6讲

字符串、数组和特殊矩阵第6讲

字符串、数组和特殊矩阵6.1字符串6.2字符串的模式匹配6.3

数组

6.4特殊矩阵

6.5

稀疏矩阵

6.1字符串串（或字符串）也是一个线性表，是由零个或多个字符组成的有限序列，一般记为：s=“a0a1…an-1”（n≥0）其中，s称为串名；用双引号括起来的字符序列称为串值；每个ai都是字符。串的长度：n(≥0)为串的长度，表示串中字符的个数，其中表示方式中的""不是成员，是定界符。1、概念空串：当n=0时，该串称为空串，表示为""。空格串：一个串中有一个或多个空格组成，如："□

"、"□

□"子串：一个串中任何连续的字符序列都称为该串的子串。如：s="abcdef"则："abc"、"cd"、"def"、"f"

都是s的子串。当然，"abcdef"也是s的子串，""空串也是s的子串。主串：s相对于子串而言称为主串。串相等：两个串的长度相等且对应位置上的子符都相同。子串在主串中的位置：子串的第一个字符在主串中首次出现的位置来表示。求串长复制串联合两个串比较两个串的大小插入一个子串删除一个子串模式匹配（检查一个串是否是另一个串的子串）2、基本运算3、串的顺序存储结构及运算实现

串的顺序存储——顺序串(1)采用数组方式存储

str数组：(2)数据类型定义0'a''b''c''d''e''f'…12345…MAX-1用顺序表的形式表示：#defineMAX100typedefstruct{charstr[MAX];intlength;/*串长*/}seqstring;采用C语言的表示形式：#defineMAX100charstr[MAX];用

'\0'

作为串的结束标记，则串的长度最大为MAX-1。串的基本运算(1)求串的长度intstrlen(chars[]){inti;for(i=0;s[i]!='\0';i++);returni;}0'a''b''c''d''e''\0'…12345…MAX-1intstrlen(chars[]){char*p=s;while(*p!='\0')p++;returnp-s;}(2)复制一个串voidstrcpy(chart[],chars[])/*s串到t串*/{inti;for(i=0;s[i];i++)t[i]=s[i];t[i]='\0';}(3)联结两个串在某个串的基础上作联结设联结后的串长不超过MAX-1，则在s中形成联结串；如超过MAX-1，则在t中适当位置截断。0'a''b''c''\0'…123…MAX-1s0'x''y''\0'…12…MAX-1tvoidstrcat(chars[],chart[]){inti,j;for(i=0;s[i];i++);/*s串扫描到空字符*/for(j=0;t[j]&&i<MAX-1;j++,i++)s[i]=t[j];s[i]='\0';}(3)联结两个串重新申请空间，存放联结之后的串新申请的空间：0'a''b''c''\0'…123…MAX-1s0'x''y''\0'…12…MAX-1tchar*strcat(chars[],chart[]){intns,nt;char*p;ns=strlen(s);nt=strlen(t);p=(char*)malloc(ns+nt+1);strcpy(p,s);strcpy(p+ns,t);returnp;}0…123…strlen(s)+strlen(t)p4(4)串的比较两个串相等：长度相等对应位置上的字符都相等比较算法(s与t串比较)：依次比较对应位置上的字符，两者都未结束，找到第一个不相等的字符(s[i]≠t[i])若s[i]>t[i],返回s[i]-t[i](正数),则称s>t若s[i]<t[i],返回s[i]-t[i](负数),则称s<t其中一个字符串比较结束(s[i]≠t[i])若s[i]=='\0',有s[i]<t[i],返回s[i]-t[i](负数),则称s<t若t[i]=='\0',有t[i]<s[i],返回s[i]-t[i](正数),则称s>t两串字符都比较结束(s[i]=‘\0’且t[i]='\0')有s[i]=='\0',t[i]=='\0',返回s[i]-t[i]

(0),则称s==t算法实现intstrcmp(chars[],chart[]){inti;i=0;while(s[i]&&t[i]&&s[i]==t[i])i++;returns[i]-t[i];}s[i]&&s[i]==t[i]6.2字符串的模式匹配模式匹配：即子串在主串中定位运算概念设有两个串s和t，检查串t是否是s的子串，这种运算称为模式匹配。其中：s串称为正文(目标串)，t串称为模式串。匹配结果(顺序串)匹配成功：返回t子串在s中第一次出现的起始位置(下标)匹配失败：返回-1BF算法(Brute-Froce)

即朴素的模式匹配算法(1)BF算法的基本思想如：目标串

s=“abbaba”，模式串t=“aba”。匹配结果：3设：i指示目标串s当前待比较的字符位置；j指示模式串t当前待比较的字符位置。BF算法的模式匹配过程示意图i=0开始i=1开始i=2开始i=3开始结果为3形参：两个顺序串返回：如出现送出起始位置下标如不出现送出-1(2)顺序串的BF模式匹配算法实现intBFindex(chars[],chart[]){inti,j,k;/*i为s串下标，j为t串下标，k为s串中比较时用的下标*/for(i=0;s[i];i++)/*扫面s串*/{/*从s串下标为i的字符开始与t串字符依次比较*/for(j=0,k=i;t[j]&&s[k]==t[j];k++,j++);if(t[j]=='\0')/*若t串被比较到空字符，则匹配成功*/returni;}return-1;}6.3数组1、概念一维数组由n(n≥1)个元素构成的有限序列也是一个线性表，但该线性表不是空表，通常称为向量。如：(a0,a1,

a2,…an-1)n≥16.3数组二维数组也是线性结构，是一种线性表的线性表该线性表是由m(m≥1)个元素构成而每个元素又是有n(n≥1)个元素构成的线性表如：A(a0,a1,a2,…am-1)

其中：ai=(ai0,ai1,ai2,…ain-1)

通常A表示成：A=(aij)m×n()()()()()()()()()其中：数据元素类型相同三维数组

A=(aijk)m×n×p行列2、运算对于二维数组来说，只有对数组元素的访问和修改，没有删除与插入运算。如：A=(aij)m×nB=(bij)m×nC=A+Bcij=aij+

bij3、数组的存储结构——采用顺序存储实现(1)一维数组

A=(a0,a1,

a2,…an-1)设ai为int型地址：1000a0a1a2…a1的地址=1004=a0的地址+(1-0)×4a2的地址=1008=a0的地址+(2-0)×4…………ai的地址=1000+4i=a0的地址+(i-0)×4若：a0的地址=LOC(a0)ai的地址=LOC(ai)元素所占字节:l则：LOC(ai)=LOC(a0)+(i-0)*l3、数组的存储结构——采用顺序存储实现(2)二维数组

两种存储方式：()()()()()()()()()以行为主序(行优先)——C采用以列为主序(列优先)——FORTRAN采用a00a01…a02a10a11…a12a20a21…a220行1行2行a00a10…a20a01a11…a21a02a12…a220列1列2列问题：已知二维数组datatypea[m][n];若a00

的地址为：LOC(a00)=LOC(a[0][0])每个元素所占字节：l=sizeof(datatype)如何确定

LOC(aij)=LOC(a[i][j])的值？分析：二维数组以行为主序存放方法：假设a00

是第1个元素，求aij前有k各元素？(1)前面0行~i-1行所有元素的个数：k1=i*n(2)i行上aij前面有元素数：k2=j(3)aij之前共有元素数：k=k1+k2=i*n+j(4)则：LOC(aij)=LOC(a00)+(i*n+j)*lj列i行思考：若从a11开始存放，已知LOC(a11),求LOC(aij)？二维数组以列为主序存放方法：假设a00

是第1个元素，求aij前有k各元素？(1)前面0列~i-1列所有元素的个数：k1=j*m(2)第j列上aij前面有元素数：k2=i(3)aij之前共有元素数：k=k1+k2=j*m+i(4)则：LOC(aij)=LOC(a00)+(j*m+i)*lj列j行思考：若从a11开始存放，已知LOC(a11),求LOC(aij)？例：有一5×4的矩阵A,按行优先存储(1)已知：LOC(a00)=1000,l=sizeof(a00)=3

求：LOC(a42)=?

答：

LOC(a42)=1000+(4*4+2)*3=1054(2)已知：LOC(a00)=1000,LOC(a42)=1054

求：LOC(a33)=?

答：

1054=1000+(4*4+2)*l

∴l=sizeof(a00)=3∴LOC(a33)=1000+(3*4+3)*3=10456.4特殊矩阵的压缩存储

矩阵是n×n的方阵，包括：对称矩阵、三角矩阵、对角矩阵等。以主对角线对称1、对称矩阵的压缩存储

即：

aij=aji采用一维数组以行为主序存储下三角部分a00a10a20a11a21a22…0行1行2行1、对称矩阵的压缩存储如下对称矩阵压缩存储一维数组最大元素个数至少是多少？下三角元素个数：1+2+3+…+n=问题：

对于二维数组A来讲，都是以行号i(0≤i＜n-1)，列号j(0≤j＜n-1)来访问aij的，则：当用一维数组B压缩存储A时,如何根据(i,j)去找aij对应的元素B[k]呢？如何根据(i,j)判断元素在二维数组中的位置？

i＝j对角线处i＜j上三角阵处i＞j下三角阵处必须给出：

k=f(i,j)(1)先计算(i,j)位置上放的是下三角阵中的第几个元素？

0行~i-1行共存在B中的元素有：

m1=1+2+3+…i=i(i+1)/2

i行存到B中的元素有：

m2=j+1

由此：aij是存到

B中的第m个元素：

m=m1+m2=

i(i+1)/2+(j+1)

则：矩阵A中aij在数组B中的下标：

k=m-1=

i(i+1)/2+j

推导：k=f(i,j)(2)而对上三角阵中的元素aij

只需存取下三角阵中aji

对应的B[k]

故：对称矩阵的压缩存储有

k=i(i+1)/2+ji≥jk=j(j+1)/2+ii＜j推导：k=f(i,j)2、三角矩阵的压缩存储三角矩阵：上三角矩阵、下三角矩阵一般情况下，常数C为0(1)下三角矩阵aij=0i<j时可能不为0i≥j时下三角部分以行优先压缩存储到一维数组B中，B的最大元素个数至少为：n(n+1)/2若aij对应B[k],则：

k=i(i+1)/2+ji≥j若

i<j时，aij=0(2)上三角矩阵aij=0i>j时可能不为0i≤j时上三角部分以行优先压缩存储到一维数组B中，B的最大元素个数至少为：n(n+1)/2若aij对应B[k],则：

k=i.n-i(i-1)/2+j-ii≤j若

i>j时，aij=0推导k=f(i,j)计算(i,j)位置上放的是上三角阵中的第几个元素？

0行~i-1行共存在B中的元素有：

m1=i.n-(1+2+3+…(i-1))=i.n-i(i-1)/2

i行存到B中的元素有：

m2=(j+1)-i=j-i+1由此：aij是存到

B中的第m个元素：

m=m1+m2=

i.n-i(i-1)/2+j-i+1则：矩阵A中aij在数组B中的下标：

k=m-1=

i.n-i(i-1)/2+j-i推导：k=f(i,j)6.5稀疏矩阵矩阵Am×n非0元素很少，分布无规律，称为稀疏矩阵。若非0元素的个数为t，总元素个数为m*n

则当

f=t/(m*n)≤5%时1、三元组顺序存储(1)存储思想只存非零元素的行号、列号和对应元素值，按行优先存储到数组中去。021

042

105

158

313

351

ijv012345

三元组存储结构：(2)数据类型定义假设：矩阵元素类型int

三元组最大元素数定义

#defineMAX100三元组一个结点类型typedefstruct{inti,j;intv;}TripletNode;

其中：i—行号

j—列号

v—矩阵元素值三元组顺序存储类型typedefstruct{intmu,nu,tu;TripletNodedata[MAX];}TripletList;

其中：mu—矩阵行数

nu—矩阵列数

tu—非0元素的个数约定：三元组元素按行优先存储(3)运算实现把一个稀疏矩阵转化为三元组存储voidMatoTri(inta[][MAX],intm,intn,TripletList*b){inti,j,k=0;/*k为三元组下标*/for(i=0;i