《数据结构与算法分析》课件第4章-串和多维数组

第四章串和数组串及存储结构串运算矩阵的压缩存储应用实例串在文字编辑、词法扫描、符号处理、自然语言翻译系统及事务处理程序中有着广泛的应用。几乎所有的程序设计语言都允许用数组来描述数据。数组可以看成是线性表的扩展。串概念

串：由零个或多个字符组成的有限序列，记为S="a1a2a3…an"

子串：串中任意个连续的字符组成的子序列。【例1】

A=“Thisisastring.”长度17

主串

B=“string”长度6子串运算①strcopy(S,T)赋值②strcat(S,T)连接③strlen(S)求串长④substr(S,i,j)求子串⑤strcmp(S,T)比较串大小⑥insert(S,i,T)插入⑦delete(S,i,j)删除⑧index(S,T)子串定位⑨replace(S,i,j,T)置换串的存储结构顺序串用一组地址连续的存储单元依次存储串中的字符。顺序串类型描述Thisisastring\0#defineMAXSIZE100 //串可能的最大长度

typedefstruct{charch[MAXSIZE];//串值

intlen;//串长度}SeqString;

链串类型描述typedefstructlinknode{chardata;structlinknode*next;}LinkString;LinkString

*S;abcds∧结点大小为1sabcdef∧结点大小为3串的存储结构串的索引存储建立串名和串值之间对应关系，为存取串值提供足够信息。

带长度索引表namelengthstadrs1s243…

workday…typedefstruct{charname[M];//串名intlength;//串长

char*stadr;//串值存入的起始地址}LenNode;串的存储结构串的存储结构

带末指针的索引表typedefstruct{

charname[M];char*stadr,*enadr;}EndNode;namestadrenadrs1s2…workday…串的存储结构

带特征位的索引表typedefstruct{

charname[maxsize];inttag;//特征位

union{char*stadr;charvalue[4];

}uval;}TagNode;nametagstadr/values1s2…work…01day\0串的存储结构说明

顺序串空间是预先定义的，需避免溢出。若使用多个串，可共享空间、按需分配。解决问题：

删除串所占空间的回收；插入操作时，如何扩充串值空间等。freenamelengthstadrs1s281380………main()↙inta[10],i;↙maxsize-1串运算的实现——串连接SeqString*StrCat(SeqString*s,SeqString*t){inti;SeqString*r=(SeqString*)malloc(sizeof(SeqString));

if(s->len+t->len>MAXSIZE)printf("上溢\n");

else{

for(i=0;i<s->len;i++)//将s串传给r

r->ch[i]=s->ch[i];

for(i=0;i<t->len;i++)//将t串传给r

r->ch[s->len+i]=t->ch[i];

r->ch[s->len+i]='\0';//最后一个位置赋'\0'

r->len=s->len+t->len;//串长度等于两串之和

}

returnr;//返回新串}

//StrCatatSeqString*SubStr(SeqString*s,inti,intj){intk;SeqString*t;t=(SeqString*)malloc(sizeof(SeqString));

if(i+j-1>s->len){//i,j值超出允许范围printf("超界\n");returnNULL;

}

else{

for(k=0;k<j;k++)t->ch[k]=s->ch[i+k-1];//将s中指定的子串传给t

t->len=j;//将子串长度赋给t的长度域

t->ch[t->len]='\0';

returnt;

}}

//SubStr串运算的实现——求子串模式匹配模式匹配从目标S中查找模式T的过程。目标S：s1s2s3…sm…sn

模式T：t1t2t3…tm

朴素的模式匹配（布鲁特—福斯算法）

从目标S的第一个字符开始和模式T中第一个字符比较，相等则继续比较后续字符，否则从S的第二个字符开始重新比较。直至T中的每个字符依次和S中的某个子序列相等（匹配成功），否则匹配失败。模式匹配第一趟：

abbabaabai=3j=3失败第二趟：abbabaai=2j=1失败第三趟：abbabaai=3j=1失败第四趟：abbabaaba

成功【例2】

S=“abbaba”，T=“aba”为例的模式匹配模式匹配分析

如何从上一趟失败的匹配中得到新一趟匹配S的比较位置i?在失败的匹配中若si≠tj（1≤j≤m），则tj-1=si-1，tj-2=si-2，…，t1=si-j+1，即t1和si-j+1对应新的一趟匹配开始时，i应回溯到i-j+2。

第三趟：abbabaai=3j=1失败第四趟：abbabaaba

成功模式匹配算法intIndex(SeqString*s,SeqString*t){inti=0,j=0;

while(i<s->len&&j<t->len){if(s->ch[i]==t->ch[j]){i++;j++;}else{i=i-j+1;j=0;}

}if(j==t->len)

returni-t->len;elsereturn-1;}

//Index模式匹配特点

算法过程简单，易于理解，但由于i的回溯，效率不高。改进

某趟匹配失败，i值回溯后，可加入判断：若S串剩余长度＜T串长度(S→len-i+1＜T→len)

即：i>S→len-T→len+1匹配失败ababaaab

bb

i=5j=3失败【例3】

因回溯后i=4，则i>6-4+1，故匹配不可能成功模式匹配时间性能最好的情况：O(m＋n)设从S的第i个位置与T匹配成功的概率为pi，第i趟成功匹配中字符比较的次数为m，则匹配成功时的平均比较次数：模式匹配设第i趟匹配成功，其概率为pi，每趟比较m次，则匹配成功时的平均比较次数：O(m×n)时间性能最坏的情况：模式匹配快速模式匹配（Knuth-Morris-Pratt,KMP匹配）基本思想

当匹配过程中字符比较不等时，不需回溯i值，而利用已经得到的"部分匹配"结果，将模式向右"滑动"尽可能远的距离后继续比较。【例4】S=“ababcabcacbab”，T=“abcac”为例的模式匹配。模式匹配【例4】

S="ababcabcacbab"，T="abcac"为例的模式匹配。第一趟：ababcabcacbabab

ci=3j=3第二趟：ababcabcacbababcaci=7j=5ij=1第三趟：ababcabcacbab(a)bcacij=2模式匹配

分析S=“abbaba”，T=“aba”的匹配过程第一趟：abbabaabai=3j=3失败即：s1＝t1s2＝t2s3≠t3

因：t1≠t2

则s2≠t1T右移一位比较一定不等

t1＝t3

则s3≠t1T再右移一位比较一定不等故可从s4开始与t1比较第二趟：abbabaaba前面部分匹配结果为后续匹配提供了信息模式匹配模式串的预处理

设置数组next[]保存匹配失败后，从模式串t重新开始比较的位置1≤next[j]<j(1≤j≤m)若上趟模式串匹配失败的位置是j，则下趟匹配应将si与tnext[j]开始next[j]值仅依赖于模式串本身的前j个字符的组成模式匹配s1s2…si-j+1…si-2si-1sisi+1…t1…tk…tj-2tj-1tj…tj-k+1tj-k+2…tj-1＝si-k+1si-k+2…si-1设下一趟si可与tk(k<j)比较，则t中前k-1个字符的子串须满足：t1t2…tk-1＝si-k+1si-k+2…si-1由部分匹配结果：t1t2…tk-1＝tj-k+1tj-k+2…tj-1故：计算next[j](=k)关键：是否存在从模式串第一个位置出发右移得到的子串和从模式串的第j-1个字符位置出发左移得到的子串匹配。模式匹配结论令next[j]=k，则失配时，用t中以k为下标的字符与si进行下一趟比较以加速匹配过程。k值仅依赖于t本身的前j个字符的组成。

0

j=1next[j]=

max{k|0＜k＜j，且使t1t2…tk-1=tj-k+1…tj-1成立}

1

其它情况若上趟匹配si与tj不等，模式匹配

【例5】S=“aaaabbb”，T=“aaab”

当s4≠t4时，k可取2和3S：aaaa

bbbT：aaab

(a)aabk=2S：aaaa

bbbT：aaab(aa)a

b

k=3注意：为使t的右移不丢失任何匹配成功的可能，若同时存在多个满足条件的k值，应取其中的最大的，这样移位j-k最小。成功失败模式匹配【例6】计算T=“abaabcac”的next值。

解：j=1j=2j=3j=4j=5j=6j=7j=8next[1]=0next[2]=1同j=2next[3]=1有首尾相等的子串“a”，则next[4]=2next[5]=2next[6]=3next[7]=1next[8]=2模式匹配时间复杂度：T(n)=O(m)voidGetNext(SeqString*t,intnext){inti=0;//next数组下标,next[]值范围0~m-1intj=-1;

next[0]=-1;//-1表示下一趟t0与si+1比较while(i<t->len){if(j==-1||t->ch[i]==t->ch[j]){++i;++j;next[i]=j;}

else

j=next[j];

}}//GetNext模式匹配intIndex(SeqString*s,SeqString*t){inti=0,j=0;while(i<s->len&&j<t->len){ if((j==-1)||(s->ch[i]==t->ch[j])){ i++;j++; }

else

j=next[j];//模式串T向右移

}

if(j==t->len)

returni-t->len; //匹配成功

else

return-1; //匹配失败}

//Index模式匹配说明：（1）尽管朴素模式匹配算法时间复杂度是O(n×m)，但很多情况下其实际执行时间近似于O(n+m)。（2）KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才显得比朴素匹配算法快得多。（3）KMP算法的最大特点是不需回溯，对目标串仅需从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效。多维数组的存储实现当数组维数为1时，数组是一种元素数目固定的线性表；当维数大于1时，数组可以看做是线性表的推广。数组结构的性质数据元素数目固定。一旦说明了一个数组结构，其中的元素数目就不再有增减变化。数据元素具有相同的类型。数据元素的下标关系具有上下界的约束，并且下标有序。多维数组的存储实现Loc(aij)=Loc(a11)+[(i-1)*n+(j-1)]*d

按行序为主序存放a11a12……..a1na21a22……..a2n

am1am2……..amn

……

amn

…

am2

am1…a2n

…

a22

a21a1n

…a12

a1101n-1m*n-1nLoc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*d

按列序为主序存放a11a12……..a1na21a22……..a2n

am1am2……..amn

……

amn

…

a2n

a1n…am2

…

a22

a12am1

…a21

a1101n-1m*n-1n多维数组的存储实现数组的顺序存储地址公式一般地，若A[c1…d1,c2…d2]，则Loc(aij)=Loc(ac1c2)+[(i－c1)×(d2－c2＋1)＋(j－c2)]×d以列为主序：Loc(aij)=Loc(a11)+[(j－1)×m＋(i－1)]×d二维数组Am×n

，每个元素占d个单元，则以行为主序：Loc(aij)=Loc(a11)+[(i－1)×n＋(j－1)]×d

数组的顺序存储三维数组Am×n×p

顺下标存储，则Loc(aijk)=Loc(a111)+[(i－1)×n×p＋(j－1)×p＋k－1]×d如：A3×2×2

元素在内存中的排列为：a000a001a010a011a100a101a110a111a200a201a210a211Loc(a210)=Loc(a000)+[i×n×p＋j×p＋k]×d=Loc(a000)+(8+2+0)×d矩阵的压缩存储压缩存储——零元素不分配存储空间，多个值相同的元素分配一个空间。需压缩存储的矩阵：特殊矩阵、稀疏矩阵特殊矩阵的压缩存储对角阵a00

0

0

…………….0

0

a11

0

0

……………0

0

0

…0

an-2,n-2

0

0

0

……0

an-1n-10

0

a22

0

0

………0…存放在一维数组A[n]（以行为主序）A的下标k与矩阵下标i的对应关系:k=i矩阵的压缩存储三角阵（以下三角阵为例）下三角矩阵上三角矩阵存放在一维数组A[n]（以行为主序）A的下标k与矩阵下标i的对应关系:i*(i+1)/2+j

i≥jn*(n+1)/2i＜jk=k:0123……n(n+1)/2-1a00a10a11a20an-1,n-1……a00

00

……..0

a10a11

0

……..0an-1,0an-1,1

……..an-1,n-1

an-2,0…………….0……………0a11…

a1,n-2a1,n-1

a00

a01……..an-1,00

0

……..an-1,n-1

00

…an-2,n-2an-2,n-1

……………矩阵的压缩存储对称阵a00a01

….

……..a0.n-1a10

a11

……..…….a1n-1an-1,0

an-1,1

……..an-1,n-1….存放在一维数组A[n]（以行为主序）A的下标k与矩阵下标i的对应关系:K=I×(I+1)/2+J其中I=max(i,j)，J=min(i,j)i(i+1)/2+ji≥jj(j+1)/2+ii＜jk=k:0123……n(n+1)/2-1a00a10a11a20an-1,n-1……矩阵的压缩存储稀疏矩阵

定义非零元素较少，且分布没有一定规律的矩阵。

压缩存储原则需存矩阵的行、列维数和每个非零元素的行、列下标及其值。

压缩存储方式三元组表、十字链表矩阵的压缩存储

三元组表将表示非零元素的三元组（行号、列号、值）按行优先（或列优先）的顺序排列，得到一个其结点是三元组的线性表。类型描述：typedefstruct{

inti,j;//行号，列号

Datatypev;//元素值}Node;typedefstruct{

intm,n,t;//行数，列数，非零元素个数

Nodedata[SMAX];//三元组表}Spmatrix;//稀疏矩阵类型矩阵的压缩存储【例7】三元组表示例011202920-3251432244118501553-7ijvnmt矩阵的压缩存储01-3051510121418209232435-75214i

j

vNM011202920-3251432244118501553-7i

j

v【例8】稀疏矩阵转置。矩阵的压缩存储算法思路：将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使M中元素以N的行(M的列)为主序

按A的列序转置。按N中三元组次序依次在M中找到相应的三元组进行转置，即从M的第一行扫描，依此将M中的j由小→大选择，将选中的三元组i和j交换后顺序放入N，直到M中的三元组全部放入N中。矩阵的压缩存储spmatrix*TRANSMAT(spmatrix*a){//求a矩阵的转置矩阵bintmno,nno,col;spmatrix*b;//存放转置后的矩阵

b=(spmatrix*)malloc(sizeof(spmatrix));b→m=a→n;b→n=a→m;//行列数交换

b→t=a→t;if(a→t>0){//有非零元素，则转置

bno=0;for(col=0;col<a→n;col++)//按*a的列序转置

for(ano=0;ano<a→t;ano++)//扫描整个三元组表

if(a→data[ano].j==col){//列号为col则进行置换

b→data[bno].i=a→data[mno].j;b→data[bno].j=a→data[mno].i;b→data[bno].v=a→data[mno].v;bno++;//b→data结点序号加1}}returnb;//返回转置结果指针

}

时间复杂度：T(n)=O(nt)问题要求实现稀疏矩阵的加法和转置运算。数据结构typedefstruct{//三元组结点

introw;//行

intcol;//列

intval;//值

}Node;typedefstruct{

intm,n,t;//矩阵行数,列数,非零元素个数

Node

data[SMAX];//三元组表}Spmatrix;//稀疏矩阵类型应用实例——稀疏矩阵的运算应用实例——稀疏矩