1、第四章第四章 串串4.1 4.1 串类型的定义串类型的定义4.2 4.2 串的表示和实现串的表示和实现4.3 4.3 串的模式匹配串的模式匹配x 的值为整数的值为整数 123。x 的值为字符串的值为字符串 123。串的串的 串的串的 串的串的 4.1 串类型的定义 是由是由 0 个或多个字符组成的有限序列。个或多个字符组成的有限序列。通常记为：通常记为：s=“a1 a2 a3 ai an”(n0)。字母、数字或其他字符字母、数字或其他字符 必须有！必须有！不属于串！不属于串！作用：避免与作用：避免与变量名变量名或或数的常量数的常量混淆。混淆。例：例：x=“123”x=123 test=“tes
2、t”基本概念基本概念 不含任何字符的串，串长度不含任何字符的串，串长度=0，用符号，用符号 表示表示。仅由一个或多个空格组成的串。仅由一个或多个空格组成的串。由串中由串中任意任意个个连续连续的字符组成的子序列。的字符组成的子序列。例：例：S=“JINAN”S1=“”、S2=“NA”、S=“JINAN”包含子串的串。包含子串的串。字符在序列中的序号。字符在序列中的序号。子串在主串中的位置是子串的子串在主串中的位置是子串的在主串中的位置。在主串中的位置。子串。子串。S4=“JAN”非子串（非子串（非非串串 S 中的中的连续连续字符所组成）。字符所组成）。在在 S 中的位置：中的位置：3 在在 S
3、中的位置：中的位置：1 当两个串的长度相等且各个对应位置的字符都当两个串的长度相等且各个对应位置的字符都 相等时才相等。相等时才相等。例：例：S=“JINAN”S1=“JI NAN”S S1 空串是任意串的子串，任意串是其自身的子串。空串是任意串的子串，任意串是其自身的子串。和线性表极为相似。和线性表极为相似。和线性表有很大差别。和线性表有很大差别。区别：区别：串的数据对象约定是串的数据对象约定是字符集字符集。在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单个元素单个元素”作为操作对象；作为操作对象；在串的基本操作中，通常以在串的基本操作中，通常以“串的整体串的整体”作为作为 操作
4、对象。操作对象。例如：在串中查找某个子串、求例如：在串中查找某个子串、求 取一个子串、在串的某个位置上插入一个子取一个子串、在串的某个位置上插入一个子 串以及删除一个子串等。串以及删除一个子串等。串的抽象数据类型的定义串的抽象数据类型的定义 ADT String 数据对象：数据对象：D ai|ai,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,ai D,i=2,.,n 基本操作：基本操作：初始条件：初始条件：chars 是字符串常量。是字符串常量。操作结果：操作结果：把把 chars 赋为赋为 T 的值。的值。初始条件：初始条件：串串 S 存在。存在。操作结果：操作结果：由串由
5、串 S 复制得串复制得串 T。初始条件：初始条件：串串 S 存在。存在。操作结果：操作结果：串串 S 被销毁。被销毁。初始条件：初始条件：串串 S 存在。存在。操作结果：操作结果：若若 S 为空串，则返回为空串，则返回 TRUE，否则返回，否则返回 FALSE。初始条件：初始条件：串串 S 和和 T 存在。存在。操作结果：操作结果：若若 S T，则返回值，则返回值 0；若若 S=T，则返回值，则返回值=0；若若 S T，则返回值，则返回值 0。“串值大小串值大小”是按是按“词典次序词典次序”进行比较的，如：进行比较的，如：StrCompare(“data”,“stru”)0 初始条件：初始条件
6、：串串 S 存在。存在。操作结果：操作结果：返回返回 S 的元素个数，称为串的长度。的元素个数，称为串的长度。初始条件：初始条件：串串 S1 和和 S2 存在。存在。操作结果：操作结果：用用 T 返回由返回由 S1 和和 S2 联接而成的新串。联接而成的新串。初始条件：初始条件：串串 S 存在，存在，1posStrLength(S)且且 0lenStrLength(S)pos+1。操作结果：操作结果：用用 Sub 返回串返回串 S 的第的第 pos 个字符起长度个字符起长度 为为 len 的子串。的子串。子串为子串为“串串”中的一个字符子序列中的一个字符子序列例如：例如：SubString(s
7、ub,commander,4,3)求得求得 sub=man ；SubString(sub,commander,1,9)求得求得 sub=commander；SubString(sub,commander,9,1)求得求得 sub=r；初始条件：初始条件：串串 S 和和 T 存在，存在，T 是非空串，是非空串，1posStrLength(S)。操作结果：操作结果：若主串若主串 S 中存在和串中存在和串 T 值相同的子串，则返回值相同的子串，则返回 它在主串它在主串 S 中第中第 pos 个字符之后第一次出现的个字符之后第一次出现的 位置；否则函数值为位置；否则函数值为 0。（。（见例子见例子）初
8、始条件：初始条件：串串 S、T 和和 V 存在，存在，T 是非空串。是非空串。操作结果：操作结果：用用 V 替换主串替换主串 S 中出现的所有与中出现的所有与 T 相等的相等的 的子串。的子串。假设假设 S=“abcacabcaca”，T=“abca”V=“ab”，则置换之后的则置换之后的 S=“abcabca”，而不是而不是“abbca”。假设 S=abcaabcaaabc,T=bcaIndex(S,T,1)=2；Index(S,T,3)=6；Index(S,T,8)=0；“子串在主串中的位置子串在主串中的位置”意指子串中的第一个字符在主串中的位序位序。Index(S,T,pos)返回子串子
9、串T在主串 S 中第pos个字符之后第一次出现的位置 初始条件：初始条件：串串 S 和和 T 存在，存在，1posStrLength(S)1。操作结果：操作结果：在串在串 S 的第的第 pos 个字符之前插入串个字符之前插入串 T。初始条件：初始条件：串串 S 存在，存在，1posStrLength(S)-len+1。操作结果：操作结果：从串从串 S 中删除第中删除第 pos 个字符起长度为个字符起长度为 len 的子串。的子串。初始条件：初始条件：串串 S 存在。存在。操作结果：操作结果：将将 S 清为空串。清为空串。ADT String 在以上操作中，串赋值在以上操作中，串赋值 StrAs
10、sign、串比较、串比较 StrCompare、求、求 串长串长 StrLength、串联接、串联接 Concat 以及求子串以及求子串 SubString 等五种操等五种操 作构成串类型的最小操作子集，即作构成串类型的最小操作子集，即。除串清除除串清除 ClearString 和串销毁和串销毁 DestroyString 以外的其他串以外的其他串 操作均可在最小操作子集上实现。操作均可在最小操作子集上实现。例如，例如，可利用判等、求串长和求子串等操作实现定位函数可利用判等、求串长和求子串等操作实现定位函数 Index(S,T,pos)：在主串：在主串 S 中取从第中取从第 i（i 的初值为的
11、初值为pos）个字符）个字符 起、长度和串起、长度和串 T 相等的子串同串相等的子串同串 T 比较，若相等，则求得函数比较，若相等，则求得函数 值为值为 i，否则，否则 i 值增值增 1，直至串，直至串 S 中从第中从第 i 个字符起直到串尾的个字符起直到串尾的 子串长度小于串子串长度小于串 T 的长度为止。的长度为止。int Index(String S,String T,int pos)/T 为非空串。若为非空串。若 S 中第中第 pos 个字符之后存在与个字符之后存在与 T 相等的子相等的子 /串，则返回第一个这样的子串在串，则返回第一个这样的子串在 S 中的位置，否则返回中的位置，否则
12、返回 0。if(pos 0)n=StrLength(S);m=StrLength(T);/求串长求串长 i=pos;while(i=n-m+1)SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)+i;else return i;/找到和找到和 T 相等的子串相等的子串 /while /if return 0;/S 中不存在满足条件的子串中不存在满足条件的子串 /Index 4.2 串的表示和实现 因为串是特殊的线性表，故其存储结构与线性表的存储结构因为串是特殊的线性表，故其存储结构与线性表的存储结构 类似，只不过类似，只不过。4.2.1 定长顺序存储表示
13、 定长顺序存储表示定长顺序存储表示，也称为，也称为静态存储分配的顺序串静态存储分配的顺序串。它是。它是 用一组用一组的存储单元来的存储单元来串中的字符序列。串中的字符序列。“定长定长”、“静态静态”的意思可简单地理解为一个确定的存储空的意思可简单地理解为一个确定的存储空 间，它的长度是不变的。间，它的长度是不变的。可直接使用定长的字符数组来定义一个串，可直接使用定长的字符数组来定义一个串，数组的上界数组的上界 预先给出：预先给出：#define maxstrlen 255 /可在可在 255 以内定义最大串长。以内定义最大串长。typedef unsignde char sstringmaxs
14、trlen+1;/0 号单元存放串的长度。号单元存放串的长度。串的实际长度可在这个预定义长度的范围内随意设定，串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为超过预定义长度的串值则被舍去，称之为“截断截断”。例：对于串例：对于串 ch=“This is a dog.”用上述一方法表示为：用上述一方法表示为：T h i s i s a d o g .0 14 T h i s i s a d o g .的两种表示方法：的两种表示方法：一：是在串的存贮区首地址一：是在串的存贮区首地址记录串的长度。记录串的长度。二：是二：是，在串之后加入一个串的结束标志。，在串之后
15、加入一个串的结束标志。PASCAL 语言中的串类型就采用这种方法。语言中的串类型就采用这种方法。如如 C 中使用中使用“0”，“0”不计入串长。不计入串长。同样对于串同样对于串 ch=“This is a dog.”用上述二方法表示为：用上述二方法表示为：定长顺序存储表示时串的操作的实现定长顺序存储表示时串的操作的实现 1、串联接、串联接 Concat(&T,S1,S2)假设串假设串 T 是由串是由串 S1 联结串联结串 S2 得到的，则只要进行相应的得到的，则只要进行相应的“串值复制串值复制”操作即可，需要时进行操作即可，需要时进行“截断截断”。串串 T 值值 S10+S20 MAXSTRL
16、EN S10 MAXSTRLEN S10=MAXSTRLEN Status Concat(SString&T,SString S1,SString S2)/未截断未截断 T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;/截断截断 T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;/截断截断(仅取仅取S1)T0.MAXSTRLEN=S10.MAXSTRLEN;uncut=FALSE;return uncut;/Concat 串联
17、接串联接 Concat 算法描述算法描述 2、求子串、求子串 SubString(&Sub,S,pos,len)求子串的过程即为复制字符序列的过程，将串求子串的过程即为复制字符序列的过程，将串 S 中的第中的第 pos 个字符开始的长度为个字符开始的长度为 len 的字符串复制到的字符串复制到 串串 Sub 中。中。1)、不会出现、不会出现“截断截断”的情况。的情况。2)、可能出现、可能出现“参数非法参数非法”的情况，应返回的情况，应返回 ERROR。Status SubString(SString&Sub,SString S,int pos,int len)if(pos S0|len S0-
18、pos+1)return ERROR;Sub1len=Spospos+len-1;Sub0=len;return OK;/SubString 求子串求子串 SubString 算法描述算法描述 仍以一组地址连续的存储单元存放串值字符序列，但存储空间是在程序执行过程中动态分配而得4.2.2 堆分配存储表示mallocmalloc()()合理预设串长空间；若串长改变，合理预设串长空间；若串长改变，使用使用reallocrealloc()()按新串长度增加空间按新串长度增加空间Typedef struct char*ch;int length;HString;/若非空串，按串长分配空间；否则若非空串
19、，按串长分配空间；否则chch=NULL=NULL/串长度串长度4.2 串的表示和实现例：用堆分配存储方式实现串插入操作(参见教材参见教材P75)P75)Status StrInsert(HString&S,int pos,HString T)/在串在串S S的第的第pospos个字符之前（包括尾部）插入串个字符之前（包括尾部）插入串T T/StrInsert if(posS.length+1)Return ERROR;/pos/pos不合法则警告不合法则警告if(T.length)/只要串只要串T T不空，就需要重新分配不空，就需要重新分配S S空间，以便插入空间，以便插入T T retur
20、n OK;if(!(S.ch=(char)*realloc(S.ch,(S.length+T.length)*sizeof(char)exit(OVERFLOW);/若开不了新空间，则退出若开不了新空间，则退出for(i=S.length-1;i=pos-1;-i)/为插入为插入T T而腾出而腾出pospos之后的位置，即从之后的位置，即从S S的的pospos位置起全部字符均后移位置起全部字符均后移 S.chi+T.length=S.chi;S.chpos-1.pos+T.length-2=T.ch0.T.length-1;/插入插入T TS.length+=T.length;/刷新刷新S
21、S串长度串长度4.2 串的表示和实现4.2.3 串的块链存储表示headABIC例：例：S=ABCDEFGHI 链表结点大小为1 链表结点大小为4headABCDE F G HI#法法1 1存储密度为存储密度为1/21/2；法；法2 2存储密度为存储密度为9/15=3/59/15=3/5存储密度存储密度=串值所占的存储位串值所占的存储位实际分配的存储位实际分配的存储位4.2 串的表示和实现4.3 串的模式匹配算法 模式匹配模式匹配：子串定位运算。子串定位运算。(串匹配串匹配)用函数用函数 Index(S,T,pos)实现。实现。在在串匹配串匹配中中，将将主串主串 S 称为称为目标目标(串串)，
22、子串子串 T 称为称为模式模式(串串)。如果在如果在主串主串 S 中能够找到中能够找到子串子串 T，则则称称，第一第一 个和个和子串子串 T 中第一个字符相等的字符在中第一个字符相等的字符在主串主串 S 中的中的；否则否则，称称，。当用当用模式模式依次从依次从目标目标的头部往后移，移到的位置就的头部往后移，移到的位置就 叫叫，每次移动后要看，每次移动后要看模式模式里的字符和里的字符和目标目标中相应的中相应的 字符是否相等，若都相等，这次位移就叫字符是否相等，若都相等，这次位移就叫（其（其 实就是从这个位置开始的实就是从这个位置开始的匹配成功匹配成功），否则叫），否则叫。模式匹配模式匹配是各种处
23、理系统中最重要的操作之一，也是各种处理系统中最重要的操作之一，也 是一个比较复杂的串操作。模式匹配的算法不同，效率是一个比较复杂的串操作。模式匹配的算法不同，效率 将有很大差别。同一算法应用不同，效率亦有很大差别。将有很大差别。同一算法应用不同，效率亦有很大差别。朴素的模式匹配算法朴素的模式匹配算法 算法思想：算法思想：从从主串主串 S 的第的第 pos 个字符起和个字符起和模式模式 T 的第一个字符比较之，的第一个字符比较之，若相同，则继续比较后续字符；否则从若相同，则继续比较后续字符；否则从主串主串 S 的下一个字符起再的下一个字符起再 重新和重新和模式模式 T 的字符比较之。的字符比较之
24、。例：例：S=JINANSHI，T=NAN。J INAN SH INAN不匹配不匹配 N A N不匹配不匹配 N A N匹配匹配 N A N匹配匹配 匹配匹配 3 第一趟匹配第二趟匹配第三趟匹配第四趟匹配第五趟匹配第六趟匹配a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca b c a ca b c a ca
25、b c a ca b c a c4.3.1（BF）匹配算法算法思想：算法思想：用子串T中的字符依次与主串S中的字符比较：若不匹配，将T右移一个字符，从头开始与S中字符依次比较；如此反复执行，直到匹配成功或者一直将T移到无法与S继续比较为止，则匹配失败。子串T主串S当采用定长顺序存储结构时，实现此操作的算法如下：当采用定长顺序存储结构时，实现此操作的算法如下：int Index(SString S,SString T,int pos)/返回子串返回子串 T 在主串在主串 S 中第中第 pos 个字符之后的位置。个字符之后的位置。/若不存在，则函数值为若不存在，则函数值为 0。/其中，其中，T 非
26、空，非空，1posStrLength(S)。i=pos;j=1;while(i=S0&j T0)return i-T0;else return 0;/IndexKMP算法的时间复杂度可以达到O(m+n)二、KMP 算法模式匹配：子串T(模式p）在主串S中的定位操作(mn)。S=s1 s2 sn 主串 P=p1 p2 pm 模式 (同子串T)从主串S中查找与模式P完全相同子串的过程。第一趟匹配第二趟匹配第三趟匹配a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a c
27、(a)b c a cKMP算法匹配情况：算法匹配情况：pj si 下一步下一步p中哪个字符和中哪个字符和si比较？比较？(i不回溯）不回溯）Pk 1 kj设主串S=“ababcabcacbab”,模式串P=“abcac”。k值仅依赖于P本身的前个j-1字符，于目标S无关；当 si pj 时，已经得到的结果：si-j+1.si-1=p1.pj-1 若已知 p1.pk-1=pj-k+1.pj-1 则有 si-k+1.si-1=p1.pk-1定义：定义：模式串的next函数其它情况且时当 1 pp ppp jk1|Maxk1j 0j1-j1k-j1-k21next int Index_KMP(SSt
28、ring S,SString T,int pos)/1posStrLength(S)i=pos;j=1;while(i=S0&j T0)return i-T0;/匹配成功 else return 0;/Index_KMP这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串求next函数值的过程是一个递推过程，分析如下:已知：next1=0；假设：nextj=k；又 Tj=Tk则：nextj+1=k+1若：Tj Tk则需往前回朔，检查 Tj=T？void get_next(SString T,int next)/求模式串T的next函数值并存入数组next。算法4.7 int i=1,j
29、=0;next1=0;/T的第1个字符与主串“失配”时，主串的下一字符与T的第1个字符比较 while(i1时，next2=1 if(j=0|Ti=Tj)/初态或两字符相等 +i;/各+1继续向后比较 +j;nexti=j;/主串和T在第i个字符不匹配时，前j-1个字符是匹配的，只须与第j个字符比较 else/两字符不等 j=nextj;/j减小到前面字符相等之处 还有一种特殊情况需要考虑：例如：S=aaabaaabaaabaaabaaab T=aaaabnextvalj=00004nextj=01234 void get_nextval(SString&T,int&nextval)i=1;n
30、extval1=0;j=0;while(i T0)if(j=0|Ti=Tj)+i;+j;if(Ti!=Tj)nextval i=j;else nextvali=nextvalj;else j=nextvalj;/get_nextval 1.熟悉串的七种基本操作的定义，并能利用这些基本操作熟悉串的七种基本操作的定义，并能利用这些基本操作 来实现串的其它各种操作的方法。来实现串的其它各种操作的方法。2.熟练掌握串的定长顺序存储结构及其实现串的各种操作熟练掌握串的定长顺序存储结构及其实现串的各种操作 的基本方法。的基本方法。3.了解串的堆存储结构及其实现串的各种操作的基本方法。了解串的堆存储结构及其
31、实现串的各种操作的基本方法。教学要求教学要求 4.掌握朴素的模式匹配算法。掌握朴素的模式匹配算法。1、试问执行以下函数会产生怎样的输出结果？void demonstrate()StrAssign(s,THIS IS A BOOK);Replace(s,SubString(s,3,7),ESE ARE);StrAssign(t,Concat(s,S);StrAssign(u,XYXYXYXYXYXY);StrAssign(v,SubString(u,6,3);StrAssign(w,W);Printf(“t=%s,v=%s,u=%s”,t,v,Replace(u,v,w);练习 5.1 数组的定
32、义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 元素的值并非原子类型，可以再分解，表中元素也是元素的值并非原子类型，可以再分解，表中元素也是 一个线性表一个线性表 所有数据元素仍属于所有数据元素仍属于同一数据类型同一数据类型。数组和广义表是线性表的扩充：第5章 数组和广义表注：注：数组中的元素都具有统一的类型数组中的元素都具有统一的类型;数组元素的下标一般都具有固定的上界和下界，即数组一旦数组元素的下标一般都具有固定的上界和下界，即数组一旦 被定义，它的维数和维界就不再发生改变；被定义，它的维数和维界就不再发生改变；数组的基本操作简单：
33、初始化、销毁、存取元素和修改元素值数组的基本操作简单：初始化、销毁、存取元素和修改元素值 一维数组的特点：一维数组的特点：1 1个下标，个下标，aiai 是是ai+1ai+1的直接前驱的直接前驱 二维数组的特点：二维数组的特点：2 2个下标，每个元素个下标，每个元素aijaij 受两个关系受两个关系 （行关系和列关系）（行关系和列关系）的约束；的约束；数组：数组：由一组名字相同、下标不同的变量构成由一组名字相同、下标不同的变量构成一个一个mn的二维数组可以的二维数组可以看成是看成是m行的一维数组，或行的一维数组，或者者n列的一维数组。列的一维数组。()()()()a00 a01 a1,n-1
34、a10 a11 a1,n-1 am-1,0 am-1,2 am-1,n-1 Amn=()()()()5.1 数组的定义 a11 a12 a1n a21 a22 a2n am1 am2 amnA=A=a11 a12 a1na21 a22 a2nam1 am2 amna11 a21 am1a12 a22 am2a1n a2n amnA=图图5-1 二维数组图二维数组图例形式例形式(a)矩阵矩阵表示形式表示形式(b)列向量的一维数组形式列向量的一维数组形式(c)行向量的一维数组形式行向量的一维数组形式存储单元是存储单元是一维一维结构，而数组是个结构，而数组是个多维多维结构结构,则用一组连续存储单元存
35、放数组的数据元素就有则用一组连续存储单元存放数组的数据元素就有个个次序约定次序约定问题。问题。二维数组可有两种存储方式：1）以行序为主序；2）以列序为主序。a00 a01 a0,n-1 a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1 a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1a00a10am-1,0a01a11am-1,1a0,n-1a1,n-1am-1,n-15.2 数组的顺序表示和实现 （以行序为主序为例（以行序为主序为例）假设每个数据元素占L个存储单元，则二维数组Ab1b2中任一元素aij的存储位置可由下式确定：L
36、OC（i，j）=LOC（0，0）+（b2*i+j）*L对于数组，一旦规定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置。数组基址数组基址总列数，即总列数，即第第2 2维长度维长度aij本行前面本行前面的元素个数的元素个数每个元素每个元素所占的存所占的存储单元储单元若是若是N N维数组维数组Ab1b2bn，其中任一元素的地址，其中任一元素的地址:LOC(j1,j2,jn)=LOC(0,0,0)+(j1b2bn+j2b3bn+jn-1bn+jn)L5.2 数组的顺序表示和实现注意：注意：2.2.以以“列优先顺序列优先顺序”存储存储 二维数组中二维
37、数组中任一元素任一元素aij的的(首首)地址地址是：是：LOCaij=LOCa11+(i-1)m+(j-1)l (5-1)i=1,2,n j=1,2,m 1.以以“行优先顺序行优先顺序”存储：存储：由此可知，二维数组中由此可知，二维数组中任一元素任一元素aij的的(首首)地址地址是：是：LOCaij=LOCa11+(i-1)n+(j-1)l (5-1)i=1,2,m j=1,2,n例例1：一个二维数组一个二维数组A，行下标的范围是，行下标的范围是1到到6，列下标的范围，列下标的范围 是是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存储，存储器个字节存储，存储器 按字节编址。那么
38、，这个数组的体积是按字节编址。那么，这个数组的体积是 个字节。个字节。例例2：设数组设数组a160,170的基地址为的基地址为2048，每个元素，每个元素2个存个存 储单元，若以列序为主序顺序存储，则元素储单元，若以列序为主序顺序存储，则元素a32,58 的的 存储地址为存储地址为 。288例例3：已知二维数组已知二维数组M的每个元素占的每个元素占4个存储单元，数组行下标个存储单元，数组行下标 i的范围从的范围从0到到4，列下标，列下标j的范围从的范围从0到到5，数组，数组M按行存按行存 储时，元素储时，元素M35的地址和的地址和M按列存储时，元素按列存储时，元素_ 的地址相同。的地址相同。A
39、.M24 B.M34 C.M35 D.M445.2 数组的顺序表示和实现压缩存储：为多个值相同的元素分配一个存储空间；对零元素不为多个值相同的元素分配一个存储空间；对零元素不分配空间。分配空间。具备压缩条件的矩阵包括：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵。对称矩阵、三角矩阵、对角矩阵、稀疏矩阵。稀疏矩阵：矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%5%）。）。5.3 矩阵的压缩存储矩阵下三角部分元素是随机的，而上三角部分元素全部相同矩阵下三角部分元素是随机的，而上三角部分元素全部相同（为某常数（为某常数C C）或全为）或全为0 0。一、三角矩阵（1 1）上三角矩阵
40、）上三角矩阵矩阵上三角部分元素是随机的，而下三角部分元素全部相同矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数（为某常数C C）或全为）或全为0 0。（2 2）下三角矩阵）下三角矩阵（b）下三角矩阵）下三角矩阵111110111000.-nnnnaaa0aa00a（a）上三角矩阵）上三角矩阵 111111100100.-nnnna000aa0aaa5.3.1 特殊矩阵（3）下三角矩阵的压缩存储矩阵中共有矩阵中共有n(n+1)/2个非零元素，共需要个非零元素，共需要n(n+1)/2+1个存储空间。若将个存储空间。若将其存放到一维向量空间其存放到一维向量空间S0.Sn(n+1)/2
41、中，则中，则SK与与aij的对应关系的对应关系为：为：当当ij时，时，aij是非零元素，是非零元素，aij前面有前面有i行，共有行，共有1+2+3+i=i(i+1)/2个非零元素，个非零元素，aij前面有前面有j列，共列，共j个非零元素，即个非零元素，即k=i(i+1)/2+j；当；当ij时，时，aij是零元素，存放在最后一个存储单元是零元素，存放在最后一个存储单元Sn(n+1)/2中。中。i*n-i(i-1)/2+j-i 当当 ijn(n+1)/2 当当ijK=111111100100.-nnnna000aa0aaa5.3.1 特殊矩阵二、对称矩阵在一个在一个n n阶方阵阶方阵A A中，若元
42、素满足下述性质：中，若元素满足下述性质：aij=aji （0i0i，jn-1jn-1）则称则称A A为对称矩阵。为对称矩阵。a11 a12 a13.a1n a21 a22 a23.a2n a31 a32 a33.a3n .an1 an2 an3.ann1、对称矩阵的定义5.3.1 特殊矩阵2、对称矩阵的压缩存储对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。在下三角矩阵中，元素
43、的总个数为的存储空间。在下三角矩阵中，元素的总个数为1+2+n=n(n+1)/2。按按行优先顺序行优先顺序存储主对角线存储主对角线(包括对角线包括对角线)以下的元素以下的元素 0123n(n-1)/2n(n+1)/2-1a11a21a22a31an1ann a11 a12 a13.a1n a21 a22 a23.a2n a31 a32 a33.a3n .an1 an2 an3.ann5.3.1 特殊矩阵2、对称矩阵的压缩存储 a11 a12 a13.a1n a21 a22 a23.a2n a31 a32 a33.a3n .an1 an2 an3.ann元素元素aij的存放位置的存放位置 aij
44、元素前有元素前有i-1行行(从第从第1行到第行到第i-1行行)，一共有：，一共有：1+2+(i-1)=(i-1)(1+(i-1)2=i(i-1)/2个元素个元素;在第在第i行上，行上，aij之前恰有之前恰有j-1个元素个元素(即即ai1，ai2，ai,j-1)，因此有：，因此有：aij之前共有之前共有i(i-1)2+(j-1)个元素个元素aij和和sk之间的对应关系：之间的对应关系：i(i-1)/2+j-1 当当 ijj(j-1)/2+i-1 当当ijK=5.3.1 特殊矩阵三、对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中心的带状若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中
45、，区域外的值全为区域中，区域外的值全为0，则称为对角矩阵。常见的有，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。三对角矩阵、五对角矩阵、七对角矩阵等。66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa一个一个77的三对角矩阵的三对角矩阵5.3.1 特殊矩阵对角矩阵的压缩存储我们仅讨论三对角矩阵的压缩存储。我们仅讨论三对角矩阵的压缩存储。在一个在一个n n的三对角矩阵中，只有的三对角矩阵中，只有n+n-1+n-1个非零元素，故个非零元素，故只需只需3n-2
46、个存储单元即可，零元已不占用存储单元。个存储单元即可，零元已不占用存储单元。故可将故可将n n三对角矩阵三对角矩阵A压缩存放到只有压缩存放到只有3n-2个存储单元的个存储单元的s向向量中，假设仍按行优先顺序存放，量中，假设仍按行优先顺序存放，sk与与aij的对应关系为：的对应关系为：3i或或 3j 当当i=j3i+1或或3j-2 当当i=j-13i-1 或或3j+2 当当i=j+1K=66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa5.3.1 特殊矩阵 以常规方法，即以
47、二维数组表示高阶的稀疏矩阵时产生的问题问题:1)零值元素占了很大空间零值元素占了很大空间;2)计算中进行了很多和零值的运算，计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。遇除法，还需判别除数是否为零。解决的办法：解决的办法：只存储非零元素。在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。M由(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩阵维数（6,7）唯一确定7600070015000001800000240
48、001400003000000000009120-M稀疏矩阵的存储：如何表示非零元素的位置信息如何表示非零元素的位置信息每个元素用一个三元组（每个元素用一个三元组（i，j，v）来表示。）来表示。1.三元组表：0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 7 0 0i j v12345678 1 2 12 1 3 9 3 1 -3 3 5 14 4 3 24 5 2 18 6 1 15 6 4 -7注意：注意：为更可靠描述，通常再加一个为更可靠描述，通常再加一个“总体总体”信息：即信息：即总行数、总列数、非总
49、行数、总列数、非零元素总个数零元素总个数。06 6 8 5.3.2 稀疏矩阵例：试还原出下列三元组所表示的稀疏矩阵。试还原出下列三元组所表示的稀疏矩阵。64612221123134445366116ijvalue646640 2 0 012 0 0 03 0 0 00 0 0 40 0 6 016 0 0 05.3.2 稀疏矩阵1、顺序存储结构、顺序存储结构（1）三元组表）三元组表对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。素值。#define MAXSIZE 12500 typedef struct int i
50、,j;/该非零元的行下标和列下标该非零元的行下标和列下标 ElemType e;/非零元素的值非零元素的值 Triple;/三元组类型三元组类型typedef struct Triple dataMAXSIZE+1;/非零元三元组表，非零元三元组表，data0未未用用 int mu,nu,tu;/矩阵的行数、列数和非零元个数矩阵的行数、列数和非零元个数 TSMatrix;/稀疏矩阵类型稀疏矩阵类型稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法2.十字链表：i j v down right指向同一列中下一非零元素指向同一行中下一非零元素3 0 0 50 1 0 02 0 0 01 1 31 4 5
