华师本科生数据结构课件 第5章 串和数组.PPT

《华师本科生数据结构课件 第5章 串和数组.PPT》由会员分享，可在线阅读，更多相关《华师本科生数据结构课件 第5章 串和数组.PPT（102页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、【课前思考】,为什么顺序表以及其它线性结构的顺序存储结构都可以用一维数组来描述？,因为在高级编程语言中实现的一维数组正是用的这种顺序存储的映象方式。,从数据结构的观点来说，串是一种特殊的线性表;但就数据类型而言，串不是线性表。,串就是线性表的结论是否正确？,第4章 串和数组,5.1 串类型的定义 5.2 串的表示和实现 5.3 串的模式匹配算法 5.4 串操作应用举例 5.5 数组的定义 5.6 数组顺序存储的表示和实现 5.7 矩阵的压缩存储,【学习目标】,理解串类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。理解串类型的各种存储表示方法。理解串匹配的各种算法。 理解数组类型的

2、特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在以行为主的存储表示中的地址计算方法； 掌握特殊矩阵的存储压缩表示方法； 理解稀疏矩阵的两类存储压缩方法的特点及其适用范围,掌握以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法；,【重点和难点】,重点 了解串类型定义以及串的实现方法串的匹配， 学会利用这些基本操作来实现串的其它操作； 掌握随机稀疏矩阵的压缩存储表示方法和运算实现,串、串的匹配、数组、特殊矩阵、稀疏矩阵、三元组、十字链表。,【知识点】,课后练习题：5.1，5.2，5.3，5.4，5.6，5.11，5.12,记为： s = “a0 a1 . an-1” (n0 ),串中字符

3、个数(n0),n=0时称为空串 。 由一个或多个空格符组成的串。 串s中任意个连续的字符序列叫s的子串; S叫主串。 子串的第一个字符的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。,串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,若干术语： 串长： 空白串： 子串： 子串位置： 字符位置： 串相等：,隐含结束符/0 ，即ASCII码NUL,5.1 串的定义和操作,串（string）：由0个或多个字符组成的有限序列，也称字符串。记为：s=“a0a1a2an-1” (n0), 其中s是串的名，a0a1a2an-1是串的值，ai(0in-1)可以是

4、字母、数字或其它字符。 串长度：串中字符的数目n。 空串：不含任何字符的串，串长度=0 空格串：仅由一个或多个空格组成的串 子串：由串中任意个连续的字符组成的子序列 主串：包含子串的串。,串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。 注意：(1) 串值必须用一对单引号括起来 (2) 串值大小是按词典次序进行比较的 StrCompare(data,Stru)0显然，只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等。,练1：串是由 字符组成的序列，一般记为 。,练2：现有以下4个字符串： a =BEI b =JING c = BEIJING d = BEI JI

5、NG,问： 他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？,a =3，b =4，c = 7，d=8,a是c和d的子串，在c和d中的位置都是1,练3：空串和空白串有无区别？ 答：有区别。空串(Null String)是指长度为零的串；而空 白串(Blank String),是指包含一个或多个空白字符 (空格键)的字符串。,0个或多个,S=a1a2an,串的数据对象约束为字符集。 线性表的基本操作大多以“单个元素”为操作对象，而串的基本操作通常以“串的整体”作为操作对象。,串的逻辑结构和线性表的区别:,补充：C语言中常用的串运算,串比较， int strcmp(chars1,char

6、s2); /StrCompare(S,T) 求串长， int strlen(char s); /StrLength(S) 串连接， char strcat(char *to,char *from) /Concat( /Index(S,T,pos) ,注：用C处理字符串时，要调用标准库函数 #include,gets( char *s ) 输入一个串； puts( char *s ) 输出一个串； strcat(char *s1, char *s2 ) 串联接函数； strcpy( char *s1, char *s2 ) 串复制函数； strcmp( char *s1, char *s2 )

7、串比较函数； strlen( char *s ) 求串长函数；, 表示空串，空串的长度为零。,StrAssign ( 若S T，则返回值 0; 若S T，则返回值 0.,StrLength (S) 初始条件：串S存在。 操作结果：返回S的元素个数,称为串的长度.,Concat (,SubString( sub, commander , 1, 9 ),SubString( sub, commander , 9, 1 ),求得 sub = r ,求得 sub = commander ,SubString( sub, commander, 4, 7 ) sub = ?,SubString( sub,

8、 beijing, 7, 2 ) = ? sub = ?,SubString( student, 5, 0 ) = ,起始位置和子串长度之间存在约束关系,长度为 0 的子串为“合法”串,Index( S, T, pos )初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置; 否则函数值为0。,假设 S = abcaabcaaabc , T = bca ,Index(S, T, 1) = 2;,Index(S, T, 3) = 6;,Index(S, T, 8) =

9、0;,“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。,Replace ( /S中不存在与T相等的子串 ,n = StrLength(S); m = StrLength(T); i = pos;,while ( i = n-m+1) / while,SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ;,串的置换函数：,S串,T串,V串,V串,pos,pos,sub,i,news 串,sub,= i+m,pos,n-pos+1,void replace(String / 剩余串 Conca

10、t( S, news, sub );,n=StrLength(S); m=StrLength(T); pos = 1; StrAssign(news, NullStr); i=1;,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以单个元素作为操作对象； 在串的基本操作中，通常以串的整体作为操作对象。,串的整体操作 赋值 StrAssign(S, “Data Structure”) 复制 StrCopy(T, S) / T=S, T为“Data Structure” 比较 StrCompare(S, T) 连接 C

11、oncat(T, “Data”, “Structure”) /T为“DataStructure” 取子串 SubString(sub, S, 2, 5) / sub为“ata S” 子串在主串中的定位 Index(S, “a”, 3) / 4 子串置换 Replace(S, “a”, “b”) / S为“Dbtb Structure” 子串插入 StrInsert(S, 3, “aha”) / “Daahata Structure” 子串删除 StrDelete(S, 3, 5) / “Daructure”,设 s =I AM A STUDENT, t =GOOD, q=WORKER。求：,练

12、习：,StrLength(s) StrLength(t) SubString(s, 8, 7)= SubString(t, 2, 1)= Index(s, A)= Index(s, t)= Replace(s, STUDENT,q)=,14 4 STUDENT O 3 0 （ s中没有t！） I AM A WORKER,再问：Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ？,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,5.2 串的表示和实现,5.2串的表示和实现,定长顺序存储表示用一组地址连续的存储单元存储串值

13、的字符序列 堆分配存储表示用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。 串的块链存储表示链式方式存储,首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。,串有三种机内表示方法：,顺序存储,链式存储,定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。,例如：#define Maxstrlen 255 /用户可用的最大串长 typedef unsigned char SStringMaxstrlen+1; SString s;

14、/s是一个可容纳255个字符的顺序串。,注： 一般用SString0来存放串长信息； C语言约定在串尾加结束符 0，以利操作加速，但不计入串长； 若字符串超过Maxstrlen 则自动截断（因为静态数组存不 进去）。,讨论：想存放超长字符串怎么办？静态数组有缺陷！,实现方式：两串连接和求子串,改用动态分配的一维数组,“堆”！,5.2.1 串的定长顺序存储表示,void Concat_Sq( char S1 , char S2 , char T ) j=0; k=0; while ( S1j != 0 ) Tk+ = S1j+; /复制串S1 j = 0; while ( S2j != 0 )

15、Tk+ = S2j+; /接着复制串S2 Tk = 0; / Concat,#define MAXSTRLEN 255 /串长度最大为255 char SStringMAXSTRLEN;,void SubString_Sq( char Sub , char S, int pos, int len) / 用Sub返回串S的第pos个字符起长度为len的子串。 / 其中，0posslen-1|lenslen-pos ) ERROR( 参数不合法); for ( j = 0; j len; j+ ) Sub j = S pos + j ; Sublen = 0; / SubString,将串S中从第

16、pos个字符开始长度为len的字符序列复制到串Sub中（注：串Sub的预留长度与S一样）,typedef struct char *ch; / 若是非空串,则按串实用长度分配存储区,否则 ch 为NULL int length; / 串长度 HString;,5.2.2 串的堆分配存储表示,通常，C/C+语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( ) /new和 free( )/delete 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为堆。 C语言中的串以一个空字符为结束符，串长是一个隐含值。,这类串操作实现的算法为: 先为新生成

17、的串分配一个存储空间，然后进行串值的复制。,void StrInsert_ HSq (char *S, int pos, char *T) /1posStrLength(S)+1。在串S的第pos个字符之前插入串T slen=StrLength_HSq (S); tlen=StrLength_HSq (T); char S1slen +1 ; / S1作为辅助串空间用于暂存S if ( posslen+1 ) ERROR( 插入位置不合法); if ( tlen0 ) i=0; while ( (S1i=Si)!=0 ) i+; / 暂存串S S = new charslen+tlen+1;

18、/ 为S重新分配空间 for ( i=0, k=0; ipos-1; i+ ) Sk+ = S1i; j = 0; while ( Tj!= 0 ) Sk+ = Tj+; / 插入T while ( S1i!= 0 ) Sk+ = S1i+; 串 Sk = 0; / 置串S的结束标志 ,void StrInsert ( char *S, int pos, char *T ) char *S1, *Sub; slen = strlen(S); tlen = strlen(T); if ( posslen+1 ) ERROR( “ 插入位置不合法” ); if ( tlen0 ) S1 = str

19、dup(S); S = new charslen+tlen+1; Sub = s1+pos-1; strncpy( S, S1, pos-1 ); spos-1 = 0; strcat( S, T ); strcat( S, Sub ); ,例：用堆实现串插入操作,5.2.3 串的块链存储表示,也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。,存储密度 =,数据元素所占存储位,实际分配的存储位,#define CHUNKSIZE 80 / 可由用户定义的块大小 typedef struct Chunk

20、/ 结点结构 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString;,例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构(80个字符),行和行之间用指针相联接。,实际应用时，可以根据问题所需来设置结点的大小。,讨论：法1存储密度为 ；法2存储密度为 ；,显然，若数据元素很多，用法2存储更优称为块链结构,链式存储特点 ：用链表存储串值，易

21、插入和删除。,法1：链表结点（数据域）大小取1,法2：链表结点（数据域）大小取n(例如n=4),1/2,9/15=3/5,模式匹配(Pattern Matching) 即子串定位运算(Index函数).,初始条件：串S和T存在，T是非空串，1posStrLength(s) 操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。,注：S称为被匹配的串，T称为模式串。若S包含串T，则称匹配成功。否则称匹配不成功。,算法目的：确定主串中所含子串第一次出现的位置（定位） 即如何实现Index(S,T,pos)函数,5.3 串的模式匹配算法,B

22、F算法 (又称古典的、经典的、朴素的、穷举的) KMP算法 (特点：速度快),Index(S,T,pos)函数,S串,T串,T串,i,pos,n-m+1,S串,T 串,T串,i,j,jm,T串,BF算法设计思想： 将主串的第pos个字符和模式的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。,直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0 .,S=a b a b c a b c a c b a b,T=a b c a c,pos=5,int In

23、dex( char char S, char T, int pos ) I = pos; j = 1; Slen = strlen(S); Tlen = strlen(T); while ( iTlen ) return i-j+1; /子串结束，说明匹配成功 else return 0; /Index,BF算法的实现即Index()操作的实现,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,S,a,b,b,b,a,a,T,朴素的模式匹配过程,a b a,a b a,a b a,a b a,模式匹配的最简单的做法是：用T中的字符依次与S中的字符比较

24、：如果S0 = T0，S1 = T1，Sm-1 = Tm-1，则匹配成功,调用求子串的操作subString(S,1,m)即是找到的子串。否则必有某个i（0im-1），使得Si Ti，这时可将T右移一个字符,用T中字符从头开始与S中字符依次比较；如此反复执行，直到下面两种情况之一：或者到达某步时，Si = T0，Si+1 = T1，Si+m-1 = Tm-1，匹配成功，subString(S,i+1,m)即是找到的（第一个）与模式T相同的子串；或者一直将T移到无法与S继续比较为止,则匹配失败。,a,第一趟匹配 a b a b c a b c a c b a b,i=3,a b c,j=3,第二

25、趟匹配 a b a b c a b c a c b a b,i=2,a,j=1,第三趟匹配 a b a b c a b c a c b a b,a b c a c,S2!=t2,该趟匹配失败 i=i- j+1,j=0 进入下趟,匹配算法,i=0,i=1,S1!=t0,该趟匹配失败 i=i- j+1,j=0 进入下趟,i=2,S6!=t4,该趟匹配失败 i=i- j+1,j=0 进入下趟,串的模式匹配算法,第四趟匹配 a b a b c a b c a c b a b,a,第五趟匹配 a b a b c a b c a c b a b,a,第六趟匹配 a b a b c a b c a c b

26、a b,i=11,a b c a c,匹配成功,匹配算法2,S3!=t0,该趟匹配失败 i=i- j+1,j=0 进入下趟,S4!=t0,该趟匹配失败 i=i- j+1,j=0 进入下趟,j 等于t 的串长,该趟匹配成功,返回i=i-n,i=4,i=3,i=5,串的模式匹配算法,int Index_BF ( char S , char T , int pos ) i = pos; j = 0; while ( Si+j != 0 ,BF算法的时间复杂度,讨论：若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为：,(n-m+1)*mO(n*m),最恶劣情况是：主串

27、前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次，再加上最后m位也各比较了1次，所以总次数为：(n-m)*m+m(n-m+1)*m,一般的情况是：O(n+m) 要从最好到最坏情况统计总的比较次数,然后取平均。,最好的情况是：一配就中！,5.4 正文编辑串操作应用举例,文本编辑：实质是修改字符数据的形式或格式，包括串的查找、插入、删除等基本操作。 思路：可以利用换行符和换页符将文本划分成若干页，每页包含若干行。页是文本串的子串，行是页的子串。在编辑程序中，先为文本串建立相应的页表和行表，即建立各子串的存储映象，在程序中设立页指针、行指针和字符指针，分别指向当前操作的页、行和字

28、符。进行文本编辑的过程，就是一个对行表、页表进行查找、插入或删除的过程。,假设有下列一段C的源程序main() float a,b,max; scanf(“%f,%f”,将此源程序看成是一个正文串,输入 内存后如图所示,图中“”为换行符。,如果在某行内插入或删除若干字符,则要修改行表中该行的长度,若该行长度因插入而超出了原分配给它的存储空间,则要为该行重新分配存储空间,并修改该行的起始位置。 例如,对上述源程序进行编辑后,其中的105行修改成： If (ab) max=a;108行修改成： 修改后的行表如图所示。,5.5 数组,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性

29、表,数组特点 数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值,5.5.1 数组的定义和特点,一、定义,5.5.1 数组的定义和操作,定义 特殊的线性表：一个数组中，数据元素的类型是一样的；数据元素的类型可能是非结构的原子类型，也可能是定长线性表。数组一旦被定义，它的维数和维界就不再改变。 数组(数据结构) vs 数组类型(程序设计语言中) 数组(数据结构)反映数据元素之间的特殊逻辑关系 可以用数组类型表示，也可以用链表示 数组类型体现物理表示，如C中规定按行优先存储 ADT Array 初始化、注销、存取元素值-无插入、删除操作,二维数组

30、 a00 a01 a0,n-1 a10 a11 a1,n-1 am-1, 0 am-1, 1 am-1, n-1 将二维数组看成是一个定长线性表，即 A = ( a0, a1, . . . , ap )p=m-1或n -1 其中每个数据元素也是一个定长线性表，即 aj = ( a0j, a1j, . . . , am-1, j )0j n -1 aj是列向量形式的线性表 ai = ( ai0, ai1, . . . , ai, n-1 )0i m -1 ai是行向量形式的线性表,Amn =,5.5.1 数组的定义和操作,数组： 由一组名字相同、下标不同的变量构成,注意： 本章所讨论的数组与高级

31、语言中的数组有所区别： 高级语言中的数组是顺序结构； 本章的数组既可以是顺序的，也可以是链式结构。,答：对的。因为： 数组中各元素具有统一的类型； 数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。 数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。,讨论：“数组的处理比其它复杂的结构要简单”，对吗？,5.5.1 数组的定义和操作,二维数组的特点：,一维数组的特点：,1个下标，ai 是ai+1的直接前驱,2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维

32、数组。,N维数组的特点：,n个下标，每个元素受到n个关系约束,一个n维数组可以看成是由若干个n1维数组组成的线性表。,5.5.1 数组的定义和操作,5.5.2 数组的顺序存储表示和实现,问题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？ 解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。 例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。,注意： 若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式； 约定的次序不同，则计算元素地址的公式也有所不同； C和PASCAL中一般采用行优先顺序；FORTRAN采用列

33、优先。,通常有两种顺序存储方式： 以行序为主序 以列序为主序,补充：计算二维数组元素地址的通式设一般的二维数组是Ac1.d1, c2.d2，这里c1,c2不一定是0。,无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）：,二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L,单个元素长度,aij之前的行数,数组基址,总列数，即第2维长度,aij本行前面的元素个数,开始结点的存放地址（即基地址） 维数和每维的上、下界； 每个数组元素所占用的单元数,则行优先存储时的地址公式

34、为：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L,Loc(j1,j2,jn)=LOC(0,0,0),若是N维数组，其中任一元素的地址该如何计算？,其中Cn=L, Ci-1=biCi， 1in,一个元素长度,数组基址,前面若干元素占用的地址字节总数,第i维长度,与所存元素个数有关的系数，可用递推法求出,例如：,称为基地址或基址。,以“行序为主序”的存储映象,二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij),a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2,a1,

35、0,a1,1,a1,2,L,L,在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2mn; 等价于： typedef elemtype array1n; typedef array1 array2m; 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。,5.5.2 数组的顺序表示和实现,例：已知二维数组Am,m按行存储的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 按列存储的公式是？,Loc(aij)=L

36、oc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同）,例：一个二维数组A，行下标的范围是1到6，列下标的范围是0 到7，每个数组元素用相邻的6个字节存储，存储器按字节编 址。那么，这个数组的体积是 个字节。,288,例：设数组a160, 170的基地址为2048，每个元素占2个存储 单元，若以列序为主序顺序存储，则元素a32,58的存储地 址为 。,8950,LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L 得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950,答：请注意审题！,利用列优先

37、通式：,答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288,5.5.3 数组的应用,利用数组降低算法的复杂度。 例：寻求两个字符串中的最大公共子串。 设string1 = “sgabacbadfgbacst”, string2 =“gabadfgab” 最长公共子串为badfg。,算法的复杂度： 时间复杂度：O(m*n) 空间复杂度：O(m*n),子串集：,Gab, 3,a, 1,b, 1,a, 1,最大长度：3，位置序号：1,最大长度：0， 位置序号：-1,a, 1,gaba, 4,a/b, 1,最大长度：4， 位置序号：1,badfg, 5,a, 1,

38、最大长度：5， 位置序号：6,a, 1,ba, 2,g, 1,a, 1,位置数：6号， 长度：5 子串：badfg,程序,void diagmaxl( int mat , int ,void diagscan( int I, int j ) eg = 0; len = 0; while ( imaxlen ) maxlen = len; jpos = sj; eg = 0; len = 0; i+; j+; ,int maxsamesubstring ( char *string1, char *string2, char * ,void SubString( char * ,在科学与工程计算

39、问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。,5.6 矩阵的压缩存储,以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:,1) 零值元素占了很大空间

40、;,计算中进行了很多和零值的运算，遇除法，还需判别 除数是否为零;,1) 尽可能少存或不存零值元素;,解决问题的原则:,2) 尽可能减少没有实际意义的运算;,3) 操作方便; 即: 能尽可能快地找到与下标值 (i, j) 对应 的元素; 能尽可能快地找到同一行或同一列的非零值元;,5.6 矩阵的压缩存储,讨论： 1. 什么是压缩存储？ 若多个数据元素的值都相同，则只分配一个元素值的存储空 间，且零元素不占存储空间。 2. 所有二维数组（矩阵）都能压缩吗？ 未必，要看矩阵是否具备以上压缩条件。 3. 什么样的矩阵具备以上压缩条件？ 一些特殊矩阵， 如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。

41、4. 什么叫稀疏矩阵？ 矩阵中非零元素的个数较少（一般小于5%）,重点介绍稀疏矩阵的压缩和相应的操作。,在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1 则称A为对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。,5.6.1 特殊形状矩阵的存储表示,所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。,1、对称矩阵,5.3 矩阵的压缩存储,对称矩阵 为每一对对称元分配一个存储空间：n2n(n+1)/2 以行序为主序存储下三角中的元

42、下三角矩阵 a11 a21 a22 an1 an2 an n,k =0 1 2 3 n(n-1)/2 n(n+1)/2-1,对称矩阵 定义：n阶矩阵A中的元满足 aij= aji ( 1 i,jn),a00 a01 a0 n-1 a00 0 0 0 a11 a1 n-1 a10 a11 0 . . 0 0 an-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵,2、三角矩阵,以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵：它的下三角(除主对角线)中的元素均为常数。 下三角矩阵：它的主对角线上方均为常数。 三角矩阵常数为零,2、三角矩阵,按

43、行序为主序：,1、若ij，则ai j在下三角形中。 ai j之前的i行(从第0 行到第i-1行)一共有: 1+2+i=i(i+1)/2个元素， 在第i行上, ai j之前恰有j个元素 （即ai0,ai1,ai2,aij-1）， 因此有： k=i*(i+1)/2+j 0kn(n+1)/2 2、若ij，则aij是在上三角矩阵中。 因为aij=aji， 所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2,3、对角矩阵,Loc(aij)=Loc(a11)+2(i-1)+(j-1) |i-j|=1,按行序为主序：,k =1 2 3 4 3n-2,假设 m

44、行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子 通常认为 0.05 的矩阵为稀疏矩阵,5.6.2 稀疏矩阵的压缩存储,何谓稀疏矩阵？,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)唯一确定,稀疏矩阵 定义：非零元较零元少，且分布没有一定规律的矩阵 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,一、稀疏矩阵的压缩存储,问题： 如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？ 解决思路： 对每个非零元素增开若干存储单元，例如存

45、放其所在的行号和列号，便可准确反映该元素所在位置。 实现方法： 将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组表来表示。,二、稀疏矩阵的操作,1、三元组顺序表,随机稀疏矩阵的压缩存储方法,稀疏矩阵的三元组顺序表表示 存储非零元：记录值、位置(行下标和列下标)三元组 三元组的排列次序：这里以行序为主序，也可选择以列序为主序有序表 稀疏矩阵的规模：行数、列数以及非零元的个数,0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0,1、三元组

46、顺序表,#define MAXSIZE 125000 /设非零元素最大个数125000 typedef struct int i; /元素行号 int j; /元素列号 ElemType e; /元素值 Triple; typedef struct Triple dataMAXSIZE+1; /三元组表，以行为主序存入一维向量 data 中 int mu; /矩阵总行数 int nu; /矩阵总列数 int tu; /矩阵中非零元素总个数 TsMatrix;,三元组表的顺序存储表示,稀疏矩阵的压缩存储方法 顺序存储结构 三元组表,6 7 8,1 2 12,1 3 9,3 1 -3,3 6 14

47、,4 3 24,5 2 18,6 1 15,6 4 -7,ma,i j v,#define M 20 typedef struct node int i, j; int v; Node; Node maM;,三元组表所需存储单元个数为3(t+1) 其中t为非零元个数,ma0.i,ma0.j,ma0.v分别存放 矩阵行列维数和非零元个数,链式存储结构 - 带行指针向量的单链表表示 每行的非零元用一个单链表存放 设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空 表头结点与单链表结点类型定义0,需存储单元个数为3t+m,例：三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，

48、它包含有三个数据项，分别表示该元素的 、 和 。,行下标,列下标,元素值,例：写出右图所示稀疏矩阵的压缩存储形式。,( 1,2,12) ,(1,3,9), (3,1,-3), (3,5,14), (4,3,24), (5,2,18) ,(6,1,15), (6,4,-7),法1：用线性表表示,法2：用三元组矩阵表示：,注意：为更可靠描述， 通常再加一行总体信息：总行数、总列数、非零元素总个数,稀疏矩阵压缩存储的缺点：将失去随机存取功能,法3：用带辅助向量的三元组表示。,方法： 增加2个辅助向量： 记录每行非0元素个数,用NUM(i)表示; 记录稀疏矩阵中每行第一个非0元素在三元组中的行号，用POS(i)表示。,7,6,5,3,1,3,用途：通过三元组高效访问稀疏矩阵中任一