第四章串和数组2011.ppt

1、第4章 串和数组,本章主要介绍下列内容： 串的定义、存储结构和基本运算 数组的定义、基本运算和存储结构 特殊矩阵的压缩存储,退出,4.1 串 4.2 数组,4.1 串,4.1.1 串的定义和基本运算 串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。,串一般记作： s= “a1a2.an” (n0) 其中，s是串的名称，用双引号（“”）括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n被称作串的长度。当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串。

2、 s1= “” s2= “ ” s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。 概念： 子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。,串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为 A=“This is a string” B=“is” 则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序

3、号（或位置）为3 特别地，空串是任意串的子串，任意串是其自身的子串。 通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C+中，可定义 const char path=“dir/bin/appl”; 这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。,例如，有下列四个串a，b，c，d： a= “Welcome to Bei

4、jing” b= “Welcome” c= “Bei” d= “welcometo” 子串的位置：子串在主串中第一次出现的第一个字符的位置。 两个串相等：两个串的长度相等，并且各个对应的字符也都相同。 例如，有下列四个串a，b，c，d： a= “program” b= “Program” c= “pro” d= “program ”,串的基本操作： （1） 创建串 StringAssign (s,string_constant) （2）判断串是否为空 StringEmpty(s) （3）计算串长度 Length(s) （4）串连接 Concat(s1,s2) （5）求子串 SubStr(s1,

5、s2start,len) （6）串的定位 Index(s1,s2),例1、求子串 求子串的过程即为复制字符序列的过程，将串S中的第pos个字符开始长度为len的字符复制到串T中。 void substr(string sub,string s,int pos,int len) if(posstrlen(s)-1 | len0) error(“parameter error”) strncpy(sub, ,例2、串的定位index(s,t,pos) 在主串中取从第i个字符起、长度和串T相等的子串和T比较，若相等，则求得函数值为i，否则值增1直至S中不存在和串T相等的子串为止。 int index

6、(string s,string t,int pos) if(pos0) n=strlen(s); m=strlen(t); i=pos; while(in-m+1) substr(sub,s,i,m); if(strcmp(sub,t)!=0) +i; else return(i); return(0); ,例如1：将s2串插入到串s1的第i个字符后面。 SubStr(s3,s1,1,i); SubStr(s4,s1,i+1,Length(s1)-i); Concat(s3,s2); Concat(s3,s4); StringAssign (s1,s3); 例如2：删除串s中第i个字符开始的

7、连续j个字符。 SubStr(s1,s,1,i-1); SubStr(s2,s,i+j,Length(s)-i-j+1); Concat(s1,s2); StringAssign(s,s1);,4.1.2 串的存储结构 1. 顺序存储结构 串的顺序存储结构与线性表的顺序存储类似，用一组连续的存储单元依次存储串中的字符序列。在C语言中，有两种实现方式： 第一种是定长顺序存储表示,也称为静态存储分配的顺序表。事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下所示： #define MAX_STRING 255 /0号单元存放串的长度，字符从1号单元开始存放 type unsig

8、ned char StringMAX_STRING;,第二种是堆分配存储表示在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的存储单元，并以一个特殊的字符作为字符串的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源的利用率。类型定义如下所示： typedef struct char *str; int length; STRING; 不同的定义形式，算法中的处理也略有不同。下面我们将给出在第二种顺序存储方式下串的几个基本操作的算法。,（1） 串的赋值 int StringAssign(STRING*s,char *strin

9、g_constant) if (s-str) free(s-str); /若s已经存在，将它占据的空间释放掉 for (len=0,ch=string_constant;ch;len+,ch+); /求string_constant串的长度 if (!len) s-str=(char*)malloc(sizeof(char);s-str0=0; s-length=0; /空串,else s-str=(char*)malloc(len+1)*sizeof(char); /分配空间 if (!s-str) return ERROR; s-str0.len=string_constant0.len;

10、 /对应的字符赋值 s-length=len; /赋予字符串长度 return OK; ,（2）判断串是否为空 int StringEmpty(STRING s) if (!s.length) return TRUE; else return FALSE; （3）求串的长度 int Length(STRING s) return s.length; ,（4）串连接 int Concat(STRING *s1,STRING s2) STRING s; StringAssign( /重新为s1分配空间,if (!s1) return ERROR; else /连接两个串的内容 s1-str0.Le

11、ngth(s)-1=s.str0.Length(s)-1); s1-strLength(s).len+1=s2.str0.Length(s2); s1-length=len; free(s-str); /释放为临时串s分配的空间 return OK; ,（5）求子串 int SubStr(STRING *s1,STRING s2,int start,int len) len2=Length(s2); /计算s2的长度 if (startlen2|len2len2-start+1) /判断start和len的合理性 s1-str=(char*)malloc(sizoef(char);s1-str

12、0=0;s1-length=0;return ERROR; s1-str=(char*)malloc(len+1)*sizeof(char); if (!s1.str) return ERROR; s1-str0.len-1=s2.strstart-1.start+len -2; s1-strlen=0; s1-length=len; return OK; ,（6）串的定位 int Index(STRING s1,STRING s2) len1=Length(s1); len2=Length(s2); /计算s1和s2的长度 i=0; j=0; /设置两个扫描指针 while (ilen1 ,

13、2. 链式存储结构 顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。由于串结构中每个数据元素为一个字符，所以最直接的链式存储结构是每个结点的数据域存放一个字符。举例：,图 4-1,优点是操作方便；不足之处是存储密度较低。所谓存储密度为：,若要将多个字符存放在一个结点中，就可以缓解这个问题。举例：,S s t r i n g # # # # ,图 4-2,由于串中的字符个数不一定是每个结点存放字符个数的整倍数，所以，需要在最后一个结点的空缺位置上填充特殊的字符。 这种存储形式优点是存储密度高于结点大小为1 的存储形式；不足之

14、处是做插入、删除字符的操作时，可能会引起结点之间字符的移动，算法实现起来比较复杂。,4.1.3 串的模式匹配算法 4.1.3.1 求子串位置的定位函数 又称模式匹配或串匹配，应用非常广泛。 在串匹配中，假设S为目标串，P为模式串： S=s1s2.sn P=p1p2pm 串的匹配实际上是根据 1in-m+1 依次将 S 的子串 Si.i+m-1 和 P1.m 进行比较，若 Si.i+m-1 = P1.m，则称从位置i开始的匹配成功；反之，匹配失败。,上述的位置i又称为位移， 当Si.i+m-1 = P1.m时，i称有效位移； 当Si.i+m-1 P1.m时，i称无效位移。 这样，串匹配问题可简化

15、为是找出某给定模式串 P 在给定目标串 S 中首次出现的有效位移。,串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。 基本思想：用一个循环来依次检查 n-m+1个合法的位移i(1in-m+1)是否为有效位移。,算法段： for(i=1;i=n-m+1;i+) if(Si.i+m-1=P1.m) return i;,例： 设pos=1； 模式串T=abcac,例：模式匹配的算法 int Index(SString s,SString p,int pos) j=1; i=pos; while (i p0) return i-p0; /匹配成功 else return 0; / I

16、ndex,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,算法简单并易于实现，但在某些情况下时间效率不高，主要的原因是主串下标i在若干个字符序列比较相等后只要有一个字符比较不相等时便需要把下标i的值回退。 算法的最坏情况是：当模式串p的前m-1个字符序列与主串s的相应字符序列比较总是相等，但模式串p的第m个字符与主串的相应字符比较总是不等。 每次比较m个字符，比较n-m+1次，共比较m*(n-m+1)次，时间复杂度为O(n*m)。,4.1.3.2 模式匹配算法的改进算法(KMP算法) 1.匹配分析 KMP算法的特点主要是消除了上述算法的主串下标i在

17、若干次字符序列比较相等后只要有一个字符比较不相等便把下标i的值回退的缺点。 分析上述算法可以发现，算法中的主串下标i值的回退并非一定必要。我们从2种情况来分析：,对于p中已与s前若干字符相匹配的部分p1pj-1 第一种情况是： 模式串中不存在相等真子串的情况，即p1pj-1中不存在前k（1kj-1）个字符等于后k个字符的情况。 例：主串s=cddcde，模式串p=cde的模式匹配过程。 当s1=p1，s2=p2，s3p3时，由于p1pj-1=cd，k=2,情况成立,即 p2p1，所以定有s2p1，接下来可直接比较 s3 和 p1。,第二种情况是： 模式串中存在相等真子串的情况，即p1pj-1存

18、在前k（1kj-1）个字符等于后k个字符的情况。 例：主串s=aaabaaad，模式串p=aaad的模式匹配过程。 当 s1=p1，s2=p2，s3=p3，s4p4 时，有 p1=p3，还有 p1p2=p2p3，取最大的相等子串 p1p2=p2p3，有k=3，由于s2s3=p2p3,此时必然有 s2s3=p1p2,显然，接下来可直接比较 s4 和 p3。,总结以上2种情况可以发现： 一旦有比较不相等时，主串 s 的下标不必回退，主串的 si 可直接和模式串的 pk(1 kj-1）比较，k 的确定与主串 s 并无关系，k 的确定只与模式串 p 本身的构成有关，即从模式串本身就可求出 k 的值。,

19、利用已经部分匹配的结果而加快模式串的滑动速度，而且主串S的指针i不必回溯！可提速到O(n+m)！例：,S=a b a b c a b c a c b a b,P=a b c a c,S=a b a b c a b c a c b a b,P=a b c a c,S=a b a b c a b c a c b a b,P=a b c a c,Index_kmp的返回值应为i=6,需要讨论两个问题： 如何“记忆”部分匹配结果？ 如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点k。,a b a,a b c,KMP算法设计思想,抓住部分匹配结果的两个特征

20、：,两式联立可得：P1Pk-1=Pj-(k-1) Pj-1 注意：j 为当前已知的失配位置，我们的目标是计算新起点 k，仅剩一个未知数k，理论上已可解，且k仅与模式串T有关！,则S前i-1i-(k-1)位P的j-1j-(k-1)位 即(4-3）式含义,则P的k-11位S前i-1i-(k-1)位 即(4-2）式含义,刚才肯定是在S的i处和T的第j字符处失配,设目前应与T的第k字符开始比较,从模式串本身求出k的值 当主串的si和模式串的pj比较不等时，由于满足关系式 p1p2 pk-1 = pj-k+1pj-k+2 pj-1 则要确定与主串si比较的子串pk的k值，只需求出模式串p中的每个字符的n

21、extj函数即可。,2.next函数 令 nextj=k ,则表示主串和子串第 j 个元素失配时，应与第 pk 个字符比较。 0 当j=1时 nextj= Max k|1kj，且p1 pk-1=pj-k+1 pj-1 当此集合不空时 1 其他情况,例：求下列模式串的nextj函数 模 式 串 T： a b a a b c a c 可能失配位 j ： 1 2 3 4 5 6 7 8 新匹配位 nextj :,0,1,1,2,2,3,1,2,讨论：,j=1时, next j = 0；因为属于“j=1”; j=2时, next j = 1；因为属于“其他情况”；,刚才已归纳：,j=3时, 只需查看是

22、否T1=T2；,j=4时, 要查看是否T1=T3 和T1T2=T2T3,j=5时, 要查看是否T1=T4、T1T2=T3T4和T1T2T3=T2T3T4,以此类推，可得后续nextj值。,例：求下列模式串的nextj函数 模式串 c d d c d e c e c d e a 下标j 1 2 3 4 5 6 7 8 9 10 11 12 nextj,0 1 1 1 2 3 1 2 1 2 3 1,例：模式匹配的KMP算法： int index(SString s,SString p,int pos) i=pos; j=1; while (i p0) return i-p0; else retu

23、rn 0; ,j=1时,next(j)=0,int String:Find ( String ,k 的确定方法 当比较到模式第 j 个字符失配时， k 的值与模式的前 j 个字符有关，与目标无关。 利用失效函数 f (j)可描述。 利用失效函数 f (j) 的匹配处理 如果 j = 0，则目标指针加 1，模式指针回到 p0。 如果 j 0，则目标指针不变，模式指针回到 pf(j-1)+1。,若设 模式 P = p0 p1pm-2 pm-1,示例 ：确定失效函数 f (j),运用KMP算法的匹配过程 第1趟 目标 a c a b a a b a a b c a c a a b c 模式 a b

24、a a b c a c j = 1 j = f (j-1)+1 = 0 第2趟 目标 a c a b a a b a a b c a c a a b c 模式 a b a a b c a c j = 5 j = f (j-1)+1= 2 第3趟 目标 a c a b a a b a a b c a c a a b c 模式 (a b) a a b c a c ,int String : fastFind ( String pat ) const /带失效函数的KMP匹配算法 int posP = 0, posT = 0; int lengthP = pat.curLen, lengthT =

25、curLen; while ( posP lengthP ,计算失效函数 f j 的方法 首先确定f 0 = -1，再利用f j求f j+1。 其中, f (1) j = f j , f (m) j = f f (m -1) j ,f 0 = -1; j = 1时, f 0+1 = 0, p0 p1, f 1 = -1; j = 2时, f 1+1 = 0, p0 = p2, f 2 = f 1+1 = 0; j = 3时, f 2+1 = 1, p1 p3, f 1+1= 0, p0 = p3, f 3 = f 1+1 = 0; j = 4时, f 3+1 = 1, p1 = p4, f 4

26、 = f 3+1 = 1;,void String:fail ( ) /计算失效函数 int lengthP = curLen; f 0 = -1; /直接赋值 for ( int j=1; j= 0 ) i = f i; /递推 if ( *(ch+j) = *(ch+i+1) ) f j = i+1; else f j = -1; ,练1：串是由 字符组成的序列，一般记为 。,练2：现有以下4个字符串： a =BEI，b =JING，c = BEIJING ，d = BEI JING，问： 他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？,a = 3，b = 4，c = 7，d

27、= 8,a是a、c和d的子串，在a、c和d中的位置都是1,0个或多个,S=a1a2an,练4：令模式串 s=a a a b t=a b c a b a a u=a b c a a b b a b c a b a a c b a c b a 分别求出他们的next函数值。,练3：空串和空格串有无区别？ 答：有。空串(Null String)是指长度为零的串；而空格串(Blank String)，是指包含一个或多个空白字符 (空格键)的字符串。,练5：从串S中删除所有和串T相同的子串。 此题的操作等同于“以空串置换串S中所有和串T相同的子串。”,显然，算法的目标是构造如上所画的一个新串。,Stri

28、ng Delete (String / Delete,练6：顺序串上的插入insert( ARRAY;,基本操作算法举例： （1）给数组元素赋值 void Assign(ARRAY *A,EnterType item,int index1,int index2) if (index1=MAX_ROW_INDEX| index2=MAX_COL_INDEX) exit(ERROR); else A-itemindex1index2=item; ,（2）返回给定位置的元素内容 int Value(ARRAY A,EntryType *item,int index1,int index2) if (

29、index1=MAX_ROW_INDEX| index2=MAX_COL_INDEX) return FALSE; else *item= A.itemindex1index2; return OK; ,3矩阵的压缩存储 矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由sn个元素排成的s行（横向）n列（纵向）的表。下面就是一个矩阵：,图4-7 sn的矩阵,矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非

30、常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。,特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1 则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。 对称矩阵中的元素关于主对角线对称，故只

31、要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先,顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 . 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 对称矩阵 在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： (i+1)=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa0.n(n+1)/2-1

32、中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak,之间找一个对应关系。 若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 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为： k=I*(I+1

33、)/2+J 0 kn(n+1)/2,因此，aij的地址可用下列式计算： LOC(aij)=LOC(sak) =LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d 有了上述的下标交换关系，对于任意给定一组下标 (i，j)，均可在sak中找到矩阵元素aij，反之，对所有 的k=0,1,2,n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(i,j)。由此，称san(n+1)/2为阶对称矩阵A的压缩存储，见下图： k=0 1 2 3 n(n-1)/2 n(n-1)/2-1 例如a21和a12均存储在 sa4中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4

34、,2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵如图所示，它的下三角（不包括主对角线） 中的元素均为常数。下三角矩阵正好相反，它的主对 角线上方均为常数，如图所示。在大多数情况下， 三角矩阵常数为零。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 三角矩阵,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0.n(n+1)/2中，其中c存放在

35、向量的最后一个分量中， 上三角矩阵中，主对角线之上的第p行(0pj,k=,下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是： i(i+1)/2+j ij n(n+1)/2 ij 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵 a00 a01 a10 a11 a12 a21 a22 a23 . . . an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1,k=,非零元素仅出现在主对角(aii,0in-1上，紧邻主对角线上面

36、的那条对角线上(aii+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0in-2)。显然，当i-j1时，元素aij=0。 由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若i-j(k-1)/2 ，则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。,在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其余元素都是零。 对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是

37、3个，因此，需存储的元素个数为3n-2。,K=0 1 2 3 4 5 3n-2 3n-1 数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：,LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d 上例中，a34对应着sa10。 k=2*i+j=2*3+4=10 a21对应着sa5 k=2*2+1=5 由此，我们称sa0.3*n-2是阶三对角带状矩阵A的压缩存储表示。,上述的各种特殊矩阵，其非零元素的分布都是有规律的

38、，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。 稀疏矩阵 什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。,精确点，设在的矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e0.05时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)唯一

39、确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。,例如，下列三元组表 (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)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7

40、0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 稀疏矩阵M和T,M=,T=,一、三元组顺序表 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元顺序表。 #define maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple;,typedef struct triple datamaxsize; int m,n,t; tripletable; 设A为tripletable型的结构变量，图

41、5.4中所示的稀疏矩阵的三元组的表示如下： i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7,下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。 一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。 将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。

42、 由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。,按这种方法设计的算法，其基本思想是：对A中的每一列 col(0coln-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。 i j v 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14,Void transmatrix(tripletable a,tripletable b) int p q col; b.m

43、=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0n”); q=0;,for(col=1;col=a.n;col+) for(p=0;p=a.t;p+) if(a.datap.j=col) b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; q+; ,分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=0;col=n-1;+col) for(row=0;ro

44、w=m;+row) tcolrow=mrowcol; 其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。,三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于t=m*n的情况。 下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。,为了预先确定矩阵M中的每一列的第一个非零元素在数组

45、B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 为此，需要设置两个一维数组num0.n和cpot0.n num0.n：统计M中每列非零元素的个数，numcol的值可以由A的第二列求得。,cpot0.n：由递推关系得出M中的每列第一个非零元素在B中的位置。 算法通过cpot数组建立位置对应关系： cpot1=1 cpotcol=cpotcol-1+numcol-1 2=cpl=a.n 例如：图中的矩阵M和相应的三元组A可以求得numcol和 cpotcol的值如下： col

46、 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9,A i j v,第一列元素个数 第二列元素个数 第三列元素个数,num,cpot,q=cpotcol,p,p,快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a) int p,q,col,k; int num0.a.n,copt0.a.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”n); for(col=1;col=a.u;+col) numcol=0; for(k=1;k=a.t;+k) +numa.datak.j;,cpot0=1; for(col=2;col=a.t;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;p=a.t;+p) col=a.datap.j; q=cpotcol; b.data