字符串数组.ppt

《字符串数组.ppt》由会员分享，可在线阅读，更多相关《字符串数组.ppt（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、李云清李云清 杨庆红杨庆红 揭安全揭安全高等学校精品课程高等学校精品课程人民邮电出版社人民邮电出版社（第（第2版）版）揭安全揭安全江西省高等学校精品课程江西省高等学校精品课程E_mailE_mail:江西师范大学计算机信息工程学院江西师范大学计算机信息工程学院江西师范大学计算机信息工程学院江西师范大学计算机信息工程学院退出第第4章字符串、数组章字符串、数组和特殊矩阵和特殊矩阵字符串字符串 字符串的模式匹配字符串的模式匹配稀疏矩阵稀疏矩阵 数组数组 特殊矩阵特殊矩阵退出4.1字符串字符串4.1.1字符串的基本概念字符串的基本概念 字符串是由零个或多个字符构成的有限序列，一字符串是由零个或多个字符

2、构成的有限序列，一般可表示成如下形式：般可表示成如下形式：“c1 c2 ”(n0)串中所含字符的个数串中所含字符的个数n称为字符串的长度；当称为字符串的长度；当n=0时，时，称字符串为称字符串为空串空串。退出串中任意个连续的字符构成的子序列称为该串的串中任意个连续的字符构成的子序列称为该串的子串子串，包含子串的串称包含子串的串称为主串为主串。通常称字符在字符串通常称字符在字符串序列中的序号为该字符在串中的位置。子串在主串中序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。的位置以子串的第一个字符在主串中的位置来表示。例如：例如：T=“STUDENT”，

3、S=“UDEN”,则则S是是T的子的子串，串，S在在T中出现的位置为中出现的位置为3。退出两个字符串相等，当且仅当两个串的长度相等，两个字符串相等，当且仅当两个串的长度相等，并且各个对应位置的字符都相等。并且各个对应位置的字符都相等。例如：例如：T1=“REDROSE”T2=“RED ROSE”由于由于T1和和T2的长度不相等，因此的长度不相等，因此T1T2。若若:T3=“STUDENT”T4=“STUDENS”虽然虽然T3和和T4的长度相等，但两者有些对应的字符不的长度相等，但两者有些对应的字符不同，因而同，因而T3T4。值得一提的是，若值得一提的是，若S=“”，此时此时S由一个空格字由一个

4、空格字符组成，其长度为符组成，其长度为1，它不等价于空串，因为空串的，它不等价于空串，因为空串的长度为长度为0。退出4.1.2字符串类的定义字符串类的定义字符串类的描述如下：字符串类的描述如下：ADT string 数据对象数据对象D:由零个或多个字符型的数据元素构成的有限集由零个或多个字符型的数据元素构成的有限集合合;数据关系数据关系R:|其中其中ai,ai+1 D,i=1,2,n1。字符串的基本操作如下字符串的基本操作如下:（1）strcreate(S):初始化字符串操作初始化字符串操作,该操作产生一个该操作产生一个新的字符串放入字符串变量新的字符串放入字符串变量S中中;（2）strass

5、ign(S,T):字符串赋值操作字符串赋值操作,其中其中S和和T均为字均为字符串变量符串变量,该函数的功能是将字符串变量该函数的功能是将字符串变量T中存放的值赋给中存放的值赋给S;（3）strlength(S):求变量求变量S中存放的字符串的长度中存放的字符串的长度;（4）strempty(S):判断变量判断变量S中存放的字符串是否为空中存放的字符串是否为空串串,若是返回若是返回1,否则返回否则返回0;退出4.1.2字符串类的定义字符串类的定义 （5）strclear(S):若字符串若字符串S已存在已存在,则该操作将它清空则该操作将它清空;（6）strcompare(S1,S2):比较两个字符

6、串比较两个字符串S1和和S2的大的大小。若小。若S1S2,则返回则返回1;若若S1=S2,则返回则返回0;否则返回否则返回1;（7）strconcat(S1,S2):字符串的连接操作字符串的连接操作,它将它将S2中存中存放的字符串连接到放的字符串连接到S1中存放的字符串的后面构成一个新串返中存放的字符串的后面构成一个新串返回回;（8）substring(S,i,len):该操作的功能为求该操作的功能为求S的子串的子串,它它表示在字符串表示在字符串S中中,从第从第i个字符开始取个字符开始取len个连续字符构成一个个连续字符构成一个子串返回子串返回;（9）index(P,T):寻找字符串寻找字符串

7、P在字符串在字符串T中首次出现的中首次出现的起始位置起始位置;（10）strinsert(S,i,T):字符串的插入运算字符串的插入运算,表示将字符表示将字符串串T插入到字符串插入到字符串S的第的第i个字符之前个字符之前;退出4.1.2字符串类的定义字符串类的定义 （11）strdelete(S,i,len):字符串的删除运算字符串的删除运算,表示将字表示将字符串符串S中第中第i个字符开始长度为个字符开始长度为len的子串删除的子串删除;（12）replace(S,T1,T2):表示在字符串表示在字符串S中用中用T2替换替换T1的所有出现的所有出现;（13）strdestroy(S):字符串销

8、毁运算。若字符串字符串销毁运算。若字符串S存在存在,执行执行strdestroy运算后运算后,S被销毁。被销毁。ADT string退出4.1.3字符串的存储及其实现字符串的存储及其实现1、串的顺序存储及其部分运算的实现、串的顺序存储及其部分运算的实现串的顺序存储使用数组存放，具体类型定义如下：串的顺序存储使用数组存放，具体类型定义如下：#define MAXSIZE 100 typedef struct char strMAXSIZE;int length;seqstring;退出（1）插入运算）插入运算strinsert(S,i,T)void strinsert(seqstring S,i

9、nt i,seqstring T)int k;if(iS-length+1|S-length+T.lengthMAXSIZE-1)/非法情况的处理非法情况的处理/printf(cannot insertn);else for(k=S-length-1;k=i1;k-)/S中从第中从第i个元素开始后移个元素开始后移/S-strT.length+k=S-strk;for(k=0;kstri+k-1=T.strk;S-length=S-length+T.length;S-strS-length=0;退出（2）删除运算）删除运算strdelete(S,i,len)void strdelete(seqs

10、tring S,int i,int len)int k;if(iS-length|i+len-1S-length)/非法情况非法情况的处理的处理/printf(cannot deleten);else for(k=i+len-1;klength;k+)/S中从下标中从下标为为i+len1开始的元素前移开始的元素前移/S-strk-len=S-strk;S-length=S-length-len;S-strS-length=0;/置字符串置字符串S新的结束符新的结束符/退出（3）连接运算）连接运算strconcat(S1,S2)seqstring*strconcat(seqstring S1,s

11、eqstring S2)int i;seqstring*r;if (S1.length+S2.lengthMAXSIZE)printf(cannot concate);return(NULL);else r=(seqstring*)malloc(sizeof(seqstring);for(i=0;istri=S1.stri;for(i=0;istr S1.length+i=S2.stri;r-length=S1.length+S2.length;r-strr-length=0;return(r);退出（4）求子串运算）求子串运算substring(S,i,len)seqstring*subst

12、ring(seqstring S,int i,int len)int k;seqstring*r;if(iS.length|i+len-1S.length)printf(“errorn”);return(NULL);else r=(seqstring*)malloc(sizeof(seqstring);for(k=0;kstrk=S.stri+k-1;r-length=len;r-strr-length=0;return(r);退出2串的链接存储及其部分运算的实现串的链接存储及其部分运算的实现abcde S S 串的链接存储采用单链表的形式实现，其中每串的链接存储采用单链表的形式实现，其中每个

13、结点的定义如下：个结点的定义如下：typedef struct node char data;struct node*next;linkstrnode;typedef linkstrnode*linkstring;例如，串例如，串S=“abcde”，其链接存储结构如下图所示：其链接存储结构如下图所示：退出（1）创建字符串运算）创建字符串运算strcreate(S)void strcreate(linkstring*S)char ch;linkstrnode*p,*r;*S=NULL;r=NULL;while(ch=getchar()!=n)p=(linkstrnode*)malloc(size

14、of(linkstrnode);p-data=ch;if(*S=NULL)*S=p;else r-next=p;r=p;/*r移向当前链接串的最后一个字符的位置移向当前链接串的最后一个字符的位置*/if(r!=NULL)r-next=NULL;/*处理表尾结点指针域处理表尾结点指针域*/退出（2）插入运算）插入运算strinsert(S,i,T)void strinsert(linkstring*S,int i,linkstring T)int k;linkstring p,q;p=*S,k=1;while(p&knext;k+;if(!p)printf(errorn);else q=T;wh

15、ile(q-next)q=q-next;q-next=p-next;p-next=T;退出（3）删除运算）删除运算strdelete(S,i,len)void strdelete(linkstring*S,int i,int len)int k;linkstring p,q,r;p=*S,q=null;k=1;/*用用p查找查找S的第的第i个元素，个元素，q始终跟踪始终跟踪p的前驱的前驱*/while(p&knext;k+;if(!p)printf(error1n);else k=1;/*p从第从第i个元素开始查找长度为个元素开始查找长度为len子串的最后元素子串的最后元素*/while(kn

16、ext;k+;if(!p)printf(error2n);退出else if(!q)r=*S;*S=p-next;/*被删除的子串位于被删除的子串位于S的最前面的最前面*/else /*被删除的子串位于的中间或最后被删除的子串位于的中间或最后*/r=q-next;q-next=p-next;p-next=null;while(r!=null)p=r;r=r-next;free(p);退出（4）连接运算）连接运算strconcat(S1,S2)void strconcat(linkstring*S1,linkstring S2)linkstring p;if(!(*S1)*S1=S2;retur

17、n;else if(S2)/*S1和和S2均不为空串的情形均不为空串的情形*/p=*S1;/*用用p查找查找S1的最后一个字符的位置的最后一个字符的位置*/while(p-next)p=p-next;p-next=S2;/*将串将串S2连接到连接到S1之后之后*/退出（5）求子串运算）求子串运算substring(S,i,len)linkstring substring(linkstring S,int i,int len)int k;linkstring p,q,r,t;p=S,k=1;/*用用p查找查找S中的第中的第i个字符个字符*/while(p&knext;k+;if(!p)print

18、f(error1n);return(null);else r=(linkstring)malloc(sizeof(linkstrnode);r-data=p-data;r-next=null;退出k=1;q=r;/*用用q始终指向子串的最后一个字符的位置始终指向子串的最后一个字符的位置*/while(p-next&knext;k+;t=(linkstring)malloc(sizeof(linkstrnode);t-data=p-data;q-next=t;q=t;if(knext=null;return(r);/*处理子串的尾部处理子串的尾部*/退出 寻找字符串寻找字符串p在字符串在字符串t

19、中首次出现的起始位置称中首次出现的起始位置称为字符串的模式匹配，其中为字符串的模式匹配，其中称称p为为模式模式(pattern），），t为正文为正文(text)，t的长度远远大于的长度远远大于p的长度。的长度。4.2字符串的模式匹配字符串的模式匹配退出4.2.1朴素的模式匹配算法朴素的模式匹配算法朴素模式匹配算法的基本思想是：用朴素模式匹配算法的基本思想是：用p中的每个中的每个字符去与字符去与t中的字符一一比较：中的字符一一比较：正文正文t：t1 t2 tmtn模式模式p：p1 p2 pm如果如果t1=p1,t2=p2,.tm=pm，则模式匹配成功；否则模式匹配成功；否则则退出将将p向右移动一

20、个字符的位置，重新用向右移动一个字符的位置，重新用p中的字符从中的字符从头开始与头开始与t中相对应的字符依次比较，即：中相对应的字符依次比较，即：t t1 1 t t2 2 t t3 3 t tm m t tm+1m+1t tn n p p1 1 p p2 2 p pm-1 m-1 p pmm 如此反复，直到匹配成功或者如此反复，直到匹配成功或者p已经移到使已经移到使t中剩中剩下的字符个数小于下的字符个数小于p的长度的位置，此时意味着模式的长度的位置，此时意味着模式匹配失败，表示匹配失败，表示t中没有子串与模式中没有子串与模式p相等，我们约相等，我们约定返回定返回-1代表匹配失败。代表匹配失败

21、。退出int index(seqstring p,seqstring t)int i,j,succ;i=0;succ=0;/*succ为匹配成功的标志为匹配成功的标志*/while(it.length-p.length+1)&(!succ)j=0;succ=1;/*用用j扫描模式扫描模式p*/while(j=p.length-1)&succ)if(p.strj=t.stri+j)j+;else succ=0;+i;if(succ)return(i-1);else return(-1);退出4.2.2快速模式匹配算法（快速模式匹配算法（KMP算法）算法）快速模式匹配算法（快速模式匹配算法（Kmp

22、算法）是由算法）是由D.E.knuth与与V.R.Pratt和和J.H.Morris同时发现的，此算法可以同时发现的，此算法可以在在O（n+m)的时间数量级上完成串的模式匹配算法。的时间数量级上完成串的模式匹配算法。退出现讨论一般情况：现讨论一般情况：假设主串为假设主串为s0s1sn-1,模式串为模式串为t0t1tm-1从上例的分析可知，为了实现改进算法，需要解决下从上例的分析可知，为了实现改进算法，需要解决下述问题：述问题：当匹配过程中产生当匹配过程中产生“失配失配”（即（即si!=tj）时，模式时，模式串串“向右滑动向右滑动”可行的距离多远，换句话说，当主串可行的距离多远，换句话说，当主串

23、中第中第i个字符与模式串中第个字符与模式串中第j个字符个字符“失配失配”时，主串的时，主串的第第i个字符（个字符（i 指针不回溯）应与模式串中哪个字符再指针不回溯）应与模式串中哪个字符再比较。比较。假设此时应与模式串中的第假设此时应与模式串中的第k个（个（kj）字符再比较，字符再比较，则模式串中的前则模式串中的前k个字符的子串必须满足下列关系：个字符的子串必须满足下列关系：退出jikt0tk-1si-ksi-1tj-ktj-1t0t1tk-1=si-k si-k+1si-11-1式ij由模式匹配的已知结果由模式匹配的已知结果si-ksi-1=tj-ktj-1(1-2式）式）可得可得 t0tk-

24、1=tj-ktj-1 1-3式式退出 反之，若模式串中存在满足（反之，若模式串中存在满足（1-3）的两个子）的两个子串，则当匹配过程中，主串中第串，则当匹配过程中，主串中第i个字符与模式串第个字符与模式串第j个字符比较不相等时，仅需将模式串向右滑至模式个字符比较不相等时，仅需将模式串向右滑至模式串第串第k个字符和主串中第个字符和主串中第i个字符对齐，此时，模式个字符对齐，此时，模式串中头串中头k个字符个字符“t0t1tk-1”必定与主串中第必定与主串中第i个个字符之前的长度为字符之前的长度为k的子串的子串“si-k si-k+1si-1”相相等等。由此，匹配仅需从模式串中第由此，匹配仅需从模式

25、串中第k个字符与主串个字符与主串中第中第i个字符继续进行。个字符继续进行。令令nextj=k,nextj=k,则则则则nextjnextj表明当模式串中第表明当模式串中第j个字符与主串中相应字符个字符与主串中相应字符“失配失配”时，在模式串中时，在模式串中需重新和主串中该字符进行比较的字符的位置。需重新和主串中该字符进行比较的字符的位置。退出Nextj=Nextj=-1 -1 当当当当j=0j=0时时时时Maxk|0kj Maxk|0kj 且且且且“t t0 0ttk-1”k-1”=“=“t tj-kj-kttj-j-1 1”0 0 其它情况其它情况其它情况其它情况j 0 1 2 3 4 5

26、6 7j 0 1 2 3 4 5 6 7模式串模式串模式串模式串 a b a a b c a ca b a a b c a cNextjNextj-1-1 0 00 01 11 12 20 01 1注意：注意：注意：注意：nextjnextj的含义是理解的含义是理解的含义是理解的含义是理解KMPKMP算法的关键。算法的关键。算法的关键。算法的关键。退出在求得模式串的在求得模式串的next函数之后，匹配可如下进行：假函数之后，匹配可如下进行：假设以指针设以指针i和和j分别指示主串和模式串中正待比较的字符，分别指示主串和模式串中正待比较的字符，令令i、j的初值为的初值为0，若在匹配过程中，若在匹配

27、过程中si=tj，则，则i与与j分分别加别加1，否则，否则i不变，而不变，而j退到退到nextj的位置再比较，若的位置再比较，若相等，则指针各自增加相等，则指针各自增加1，否则，否则j再退到下一个再退到下一个nextj值的位置，依此类推，直至下列两种可能：值的位置，依此类推，直至下列两种可能：一种是退到某个一种是退到某个next值（值（next.nextj.）时字符比时字符比较相等，则指针各自增加较相等，则指针各自增加1继续进行匹配；继续进行匹配；另一种是另一种是j退到退到-1（即模式的第一个字符（即模式的第一个字符“失配失配”），），则此时，需将主串继续向右滑动一个位置，即从主串则此时，需将

28、主串继续向右滑动一个位置，即从主串的下一个字符的下一个字符S Si+1i+1起和模式串重新开始匹配。起和模式串重新开始匹配。退出以下给出顺序存储结构下的以下给出顺序存储结构下的KMP算法。算法。#define maxsize 100typedef struct char strmaxsize;int length;seqstring;顺序串存储结构顺序串存储结构顺序串存储结构顺序串存储结构退出int kmp(seqstring t,seqstring p,int next)int i=0,j=0;while(it.length&jp.length)if(j=-1|t.stri=p.strj)i

29、+;j+;else j=nextj;if(j=p.length)return(i-p.length);else return(-1);退出以下说明如何求以下说明如何求next函数：函数：由定义：由定义：next0=-1;设设nextj=k,这表明在模式串中存在下列关系：这表明在模式串中存在下列关系：“t0tk-1”=“tj-ktj-1”其中其中k为满足为满足1=kk满足上式，此时满足上式，此时nextj+1的取值可能有两种情况：的取值可能有两种情况：（1）若）若tk=tj 则表明在模式中则表明在模式中 “t0tk-1tk”=“tj-ktj-1tj”此时此时nextj+1=nextj+1退出（2

30、）若）若tk tj 则表明在模式串中则表明在模式串中“t0tk-1tk”“tj-ktj-1tj”此时可把求此时可把求next函数值的问题看成是一个模式匹配函数值的问题看成是一个模式匹配的问题，整个模式串既是主串又是模式串，而当前在的问题，整个模式串既是主串又是模式串，而当前在匹配的过程中，已有匹配的过程中，已有t0=tj-k，t1=tj-k+1，tk-1=tj-1，则当则当tk tj 时应将模式向右滑动至以模式中时应将模式向右滑动至以模式中的第的第nextk个字符和主串中的第个字符和主串中的第j个字符相比较。若个字符相比较。若nextk=k，且且tk=tj ，则说明在主串中第则说明在主串中第j

31、+1个字个字符之前存在一个长度为符之前存在一个长度为k（即（即nextk）的最长子串，的最长子串，和模式串中的首字符起长度为和模式串中的首字符起长度为k的子串相等，即的子串相等，即 “t0tk-1tk”=“tj-ktj-1tj”退出这就是说：这就是说：nextj+1=k+1 即即 nextj+1=nextk+1同理，若同理，若 tk tj ,则将模式继续向右滑动直至将模则将模式继续向右滑动直至将模式中第式中第nextk个字符和个字符和tj对齐，对齐，依次类推，依次类推，直至直至tj和模式中某个字符匹配成功或者不存在任何和模式中某个字符匹配成功或者不存在任何k（1Kj）满足等式（满足等式（4-1

32、0），则），则nextj+1=0；退出void getnext(seqstring p,int next)int i,j;next0=-1;i=0;j=-1;while(ip.length)if(j=-1|p.stri=p.strj)+i;+j;nexti=j;else j=nextj;for(i=0;i2）维数组，可以依据上述规律类推。维数组，可以依据上述规律类推。退出4.3.2数组类的定义数组类的定义ADT array 数据对象数据对象D：具有相同类型的数据元素构成的有序集具有相同类型的数据元素构成的有序集合；合；数据关系数据关系R：对于对于n维数组，其每一个元素均位于维数组，其每一个元素

33、均位于n个个向量中，每个元素最多具有向量中，每个元素最多具有n个前驱结点和个前驱结点和n个后继结个后继结点；点；退出4.3.3数组的顺序存储及实现数组的顺序存储及实现由于数组是由有限的元素构成的有序集合，数由于数组是由有限的元素构成的有序集合，数组的大小和元素之间的关系一经确定，就不再发生组的大小和元素之间的关系一经确定，就不再发生变化，因此数组均采用顺序存储结构实现，它要求变化，因此数组均采用顺序存储结构实现，它要求一片连续的存储空间存储。一片连续的存储空间存储。多维数组数据元素的顺序存储有两种方式：多维数组数据元素的顺序存储有两种方式：按行优先存储按行优先存储 按列优先存储按列优先存储退出

34、例如：对于二维数组例如：对于二维数组Amn：a00a01a0(n-1)a10a11a1(n-1)A=a(m-1)0a(m-1)1a(m-1)(n-1)若将若将A按行优先存储，其存储顺序为：按行优先存储，其存储顺序为：a00，a01，a0(n-1),a10,a11，.a1(n-1)，a(m-1)0，a(m-1)1，a(m-1)(n-1)；而按列优先存储，其顺序为：而按列优先存储，其顺序为：a00，a10，a(m-1)0,a01,a11,.a(m-1)1，a0(n-1),.a1(n-1)，a(m-1)(n-1)。退出对于数组，一旦确定了它的维数和各维的长度，对于数组，一旦确定了它的维数和各维的长度

35、，便可以为它分配存储空间；当规定了数组元素的存储便可以为它分配存储空间；当规定了数组元素的存储次序后，便可根据给定的一组下标值求得相应数组元次序后，便可根据给定的一组下标值求得相应数组元素的存储位置。素的存储位置。现假设数组中每个元素占用现假设数组中每个元素占用L个存储单元，若考个存储单元，若考虑按行优先存储方式，则上述虑按行优先存储方式，则上述A数组中任何一个元素数组中任何一个元素aij的存储位置可以按以下公式确定的存储位置可以按以下公式确定：address（aij）=address(a00)+(in+j)L若考虑按列优先的存储方式，数组中任何一个元若考虑按列优先的存储方式，数组中任何一个元

36、素素aij存储位置的地址计算公式为：存储位置的地址计算公式为：address(aij)=address(a00)+(jm+i)L退出多维数组的存储也和二维数组一样，存在两种多维数组的存储也和二维数组一样，存在两种存储方式：按行优先和按列优先。但由于多维数组中存储方式：按行优先和按列优先。但由于多维数组中数据元素间的关系较二维数组复杂，因此数据元素的数据元素间的关系较二维数组复杂，因此数据元素的地址计算公式也相对复杂些，但两者所采用的原理是地址计算公式也相对复杂些，但两者所采用的原理是相同的。相同的。退出以下以三维数组为例，给出三维数组的顺序存储以下以三维数组为例，给出三维数组的顺序存储表示及其

37、部分运算的实现。表示及其部分运算的实现。typedef int datatype;/*假设数组元素的值为整型假设数组元素的值为整型*/typedef struct datatype*base;/*数组存储区的首地址指针数组存储区的首地址指针*/int index3;/*存放三维数组各维的长度存放三维数组各维的长度*/int c3 /*存放三维数组各维的存放三维数组各维的ci值值*/array；退出1、数组初始化运算数组初始化运算initarray(A,b1,b2,b3)int initarray(array*A,int b1,int b2,int b3)int elements;if(b1=0

38、|b2=0|b3index0=b1;A-index1=b2;A-index2=b3;elements=b1 b2 b3;A-base=(datatype*)malloc(elementssizeof(datatype);if (!(A-base)return(0);A-c0=b2 b3;A-c1=b3;A-c2=1;return(1);退出2、访问数组元素值的运算访问数组元素值的运算value(A,i1,i2,i3,x)int value(array A,int i1,int i2,int i3;datatype*x)int off;if(i1=A.index0|i2=A.index1|i3=

39、A.index2)return(0);/*处理下标非法的情况处理下标非法的情况*/off=i1A.c0+i2A.c1+i3A.c2;*x=*(A.base+off);/*赋值赋值*/return(1);退出3、数组元素的赋值运算、数组元素的赋值运算assign(A,e,i1,i2,i3)int assign(array*A,datatype e,int i1,int i2,int i3)int off;if(i1=A-index0|i2=A-index1|i3=A-index2)return(0);/*处理下标非法的情况处理下标非法的情况*/off=i1A-c0+i2A-c1+i3A-c2;*

40、(A-base+off)=e;/*赋值赋值*/return(1);退出本节主要研究对称矩阵、三角矩阵和带状矩阵本节主要研究对称矩阵、三角矩阵和带状矩阵的压缩存储。所谓压缩存储即为：多个相同值的结的压缩存储。所谓压缩存储即为：多个相同值的结点只分配一个存储空间，值为零的结点不分配空间。点只分配一个存储空间，值为零的结点不分配空间。4.4特殊矩阵特殊矩阵退出4.4.1对称矩阵的压缩存储对称矩阵的压缩存储如果矩阵的行数和列数相等，则称该矩阵为方如果矩阵的行数和列数相等，则称该矩阵为方阵。若阵。若nn阶的方阵阶的方阵A满足：满足：aij=aji(0in-1,0jn-1)则称矩阵则称矩阵A为为对称矩阵对

41、称矩阵。在对称矩阵中，几乎有一在对称矩阵中，几乎有一半元素的值是对应相等的。如果将半元素的值是对应相等的。如果将A中所有元素进中所有元素进行存储，那将会造成空间的浪费，且行存储，那将会造成空间的浪费，且n值越大，浪费值越大，浪费将越严重。将越严重。4.4特殊矩阵特殊矩阵退出对于对称矩阵压缩存储时只需存储对角线以上对于对称矩阵压缩存储时只需存储对角线以上或对角线以下的部分，未存储的部分可以利用元素或对角线以下的部分，未存储的部分可以利用元素之间的对称性来访问。之间的对称性来访问。现考虑只存储对称矩阵现考虑只存储对称矩阵A对角线以下的部分对角线以下的部分（即下标满足（即下标满足ij的数组元素的数组

42、元素aij）：）：a00a10a11A=a20a21a22 a(n-1)0.a(n-1)(n-1)退出若采用按行优先的存储方式，若采用按行优先的存储方式，A进行压缩存储后任进行压缩存储后任何一个元素何一个元素aij的地址计算公式为：的地址计算公式为：address(a00)+(i*(i+1)/2+j)L当当ijaddress(aij)=address(a00)+(j*(j+1)/2+i)L当当ij退出4.4.2三角矩阵的压缩存储三角矩阵的压缩存储1、下三角矩阵、下三角矩阵a00000a10a110.0A=a20a21a22.0 a(n-1)0a(n-1)(n-1)仍考虑采用按行优先方式，仍考虑

43、采用按行优先方式，A中下三角部分的任何一个中下三角部分的任何一个元素元素aij(ij)压缩存储后的地址计算公式为：压缩存储后的地址计算公式为：address(aij)=address(a00)+(i*(i+1)/2+j)L当当ij与对称矩阵不同的是，当与对称矩阵不同的是，当ij时，时，aij的值为的值为0，其没有对应的存储空间，其没有对应的存储空间。退出2、上三角矩阵上三角矩阵a00a01a02a0(n-1)0a11a12.a1(n-1)A=00a22.a2(n-1)000a(n-1)(n-1)对于上三角矩阵，只需考虑存储对角线以上的部分，对对于上三角矩阵，只需考虑存储对角线以上的部分，对角线

44、以下为角线以下为0的部分无需存储。仍采用按行优先存储方式，的部分无需存储。仍采用按行优先存储方式，矩阵矩阵A中被存储元素中被存储元素aij(ij)在在压缩存储方式下的地址计算公压缩存储方式下的地址计算公式为：式为：address(aij)=address(a00)+(n+(n-1)+(n-2)+.+(n-(i-1)+j-iL=address(a00)+(i*n-(i-1)*i/2+j-i)*L而当而当ij时，时，aij的值为的值为0，其没有对应的存储空间，其没有对应的存储空间。退出4.4.3带状矩阵的压缩存储带状矩阵的压缩存储对于对于nn阶方阵，若它的全部非零元素落在一个以主对阶方阵，若它的全

45、部非零元素落在一个以主对角线为中心的带状区域中，这个带状区域包含主对角线下面角线为中心的带状区域中，这个带状区域包含主对角线下面及上面各及上面各b条对角线上的元素以及主对角线上的元素，那么条对角线上的元素以及主对角线上的元素，那么称该方阵为半带宽为称该方阵为半带宽为b的带状矩阵。带状矩阵的特点是：对的带状矩阵。带状矩阵的特点是：对于矩阵元素于矩阵元素aij，若，若i-jb或或j-ib，即即|i-j|b，则，则aij=0。b条对角线条对角线b条对角线条对角线主对角线主对角线退出带状矩阵进行压缩存储时，只存储带状部分内部带状矩阵进行压缩存储时，只存储带状部分内部的元素，对于带状区域以外的元素，即的

46、元素，对于带状区域以外的元素，即|i-j|b的的aij，均不分配存储空间。为了方便起见，我们规定按如均不分配存储空间。为了方便起见，我们规定按如下方法进行存储：除第一行和最后一行外，每行都分下方法进行存储：除第一行和最后一行外，每行都分配配2b+1个元素的空间，将带状区域中的元素存储于个元素的空间，将带状区域中的元素存储于（(2b+1)n-2b）L个存储单元之中，其中个存储单元之中，其中L为每个为每个元素占用空间的大小。仍考虑采用按行优先的存储方元素占用空间的大小。仍考虑采用按行优先的存储方式，于是可以得到带状区域中任何一个元素式，于是可以得到带状区域中任何一个元素aij的地址的地址计算公式为

47、：计算公式为：address(aij)=address(a00)+(i(2b+1)-b)+(j-i+b)L=address(a00)+(i(2b+1)+j-i)L(当当|i-j|b时时)退出如果一个矩阵中很多元素的值为零，即零元素的如果一个矩阵中很多元素的值为零，即零元素的个数远远大于非零元素的个数时，称该矩阵为稀疏矩个数远远大于非零元素的个数时，称该矩阵为稀疏矩阵。阵。4.5.1稀疏矩阵类的定义稀疏矩阵类的定义ADT spmatrix 数据对象数据对象D:具有相同类型的数据元素构成的有限集合具有相同类型的数据元素构成的有限集合;数据关系数据关系R:D中的每个元素均位于中的每个元素均位于2个向

48、量中个向量中,每个元素最每个元素最多具有多具有2个前驱结点和个前驱结点和2个后继结点个后继结点,且且D中零元素的个数远远中零元素的个数远远大于非零元素的个数。大于非零元素的个数。稀疏矩阵的基本运算如下稀疏矩阵的基本运算如下:（1）createspmatrix(A)创建一个稀疏矩阵创建一个稀疏矩阵A;4.5稀疏矩阵稀疏矩阵退出（2）compressmatrix(A,B)创建稀疏矩阵创建稀疏矩阵A的压缩的压缩存储表示存储表示B;（3）destroyspmatrix(A)销毁稀疏矩阵销毁稀疏矩阵A;（4）printspmatrix(A)将已知稀疏矩阵将已知稀疏矩阵A,将将A复制到复制到B中中;（5）

49、copyspmatrix(A,B)将将A复制到复制到B （6）addspmatrix(A,B,C)已知稀疏矩阵已知稀疏矩阵A和和B,且且两者的行数和列数对应相等两者的行数和列数对应相等,求求A和和B相加的结果放入相加的结果放入C中中;（7）subspmatrix(A,B,C)已知稀疏矩阵已知稀疏矩阵A和和B,且且两者的行数和列数对应相等两者的行数和列数对应相等,求求A和和B相减的结果放入相减的结果放入C中中;（8）multspmatrix(A,B,C)已知稀疏矩阵已知稀疏矩阵A和和B,且且A的列数等于的列数等于B的行数的行数,求求A和和B相乘的结果放入相乘的结果放入C中中;退出 （9）transpmatrix(B,C)已知稀疏矩阵已知稀疏矩阵B,求求B的转的转置矩阵放入置矩阵放入C中中;（10）locatespmatrix(A,x,rowx,colx)在稀疏矩阵在稀疏矩阵A中中查找值为查找值为x的结点位置。的结点位置。ADT spmatrix退出4.5.2稀疏矩阵的顺序存储及其实现稀疏矩阵的顺序存储及其实现稀疏矩阵的顺序存储方法包括：三元组表示法、带辅稀疏矩阵的顺序存储方法包括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示法，其中以三元组表助行向量的二元组表示法和伪地址表示法，其中以三元组表示法最常用，故在此主要介绍稀疏矩阵的三元组表示。示法最常用，故在此主要介绍稀疏矩阵