第04章_字符串数组

1、第第4章字符串、数组章字符串、数组和特殊矩阵和特殊矩阵字符串字符串 字符串的模式匹配字符串的模式匹配稀疏矩阵稀疏矩阵 数组数组 特殊矩阵特殊矩阵 4 .1 字符串字符串 4.1.1 字符串的基本概念字符串的基本概念字符串是由零个或多个字符构成的有限序列，一字符串是由零个或多个字符构成的有限序列，一般可表示成如下形式：般可表示成如下形式： “c1 c2 ” (n0)串中所含字符的个数串中所含字符的个数n称为字符串的长度；当称为字符串的长度；当n=0时，时，称字符串为称字符串为空串空串。 串中任意个连续的字符构成的子序列称为该串串中任意个连续的字符构成的子序列称为该串的的子串子串，包含子串的串称包

2、含子串的串称为主串为主串。通常称字符在字通常称字符在字符串序列中的序号为该字符在串中的位置。子串在符串序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置主串中的位置以子串的第一个字符在主串中的位置来表示。例如：来表示。例如：T =“STUDENT”，S=“UDEN”, 则则S是是T的子串，的子串，S在在T中出现的位置为中出现的位置为3。 两个字符串相等，当且仅当两个串的长度相等，两个字符串相等，当且仅当两个串的长度相等，并且各个对应位置的字符都相等。并且各个对应位置的字符都相等。例如：例如： T1=“REDROSE” T2=“RED ROSE”由于由于T1和和

3、T2的长度不相等，因此的长度不相等，因此T1T2。若若: T3=“STUDENT” T4=“STUDENS” 虽然虽然T3和和T4的长度相等，但两者有些对应的字符不的长度相等，但两者有些对应的字符不同，因而同，因而T3T4。 值得一提的是，若值得一提的是，若S=“ ”，此时，此时S由一个空格字由一个空格字符组成，其长度为符组成，其长度为1，它不等价于空串，因为空串的，它不等价于空串，因为空串的长度为长度为0。4.1.2 字符串类的定义字符串类的定义字符串类的描述如下：字符串类的描述如下：ADT string 数据对象数据对象D:由零个或多个字符型的数据元素构成的有限由零个或多个字符型的数据元素

4、构成的有限集合集合; 数据关系数据关系R:|其中其中ai,ai+1 D,i=1,2,n1。 字符串的基本操作如下字符串的基本操作如下: （1）strcreate(S):初始化字符串操作初始化字符串操作,该操作产生一个该操作产生一个新的字符串放入字符串变量新的字符串放入字符串变量S中中; （2）strassign(S,T):字符串赋值操作字符串赋值操作,其中其中S和和T均为字均为字符串变量符串变量,该函数的功能是将字符串变量该函数的功能是将字符串变量T中存放的值赋给中存放的值赋给S; （3）strlength(S):求变量求变量S中存放的字符串的长度中存放的字符串的长度; （4）strempty

5、(S):判断变量判断变量S中存放的字符串是否为空中存放的字符串是否为空串串,若是返回若是返回1,否则返回否则返回0; 4.1.2 字符串类的定义字符串类的定义 （5）strclear(S):若字符串若字符串S已存在已存在,则该操作将它清空则该操作将它清空; （6）strcompare(S1,S2):比较两个字符串比较两个字符串S1和和S2的大的大小。若小。若S1S2,则返回则返回1;若若S1=S2,则返回则返回0;否则返回否则返回1; （7）strconcat(S1,S2):字符串的连接操作字符串的连接操作,它将它将S2中存中存放的字符串连接到放的字符串连接到S1中存放的字符串的后面构成一个新

6、串返中存放的字符串的后面构成一个新串返回回; （8）substring(S,i,len):该操作的功能为求该操作的功能为求S的子串的子串,它它表示在字符串表示在字符串S中中,从第从第i个字符开始取个字符开始取len个连续字符构成一个个连续字符构成一个子串返回子串返回; （9）index(P,T):寻找字符串寻找字符串P在字符串在字符串T中首次出现的中首次出现的起始位置起始位置; （10）strinsert(S,i,T):字符串的插入运算字符串的插入运算,表示将字符表示将字符串串T插入到字符串插入到字符串S的第的第i个字符之前个字符之前;4.1.2 字符串类的定义字符串类的定义 （11）strd

7、elete(S,i,len):字符串的删除运算字符串的删除运算,表示将字表示将字符串符串S中第中第i个字符开始长度为个字符开始长度为len的子串删除的子串删除; （12）replace(S,T1,T2):表示在字符串表示在字符串S中用中用T2替换替换T1的所有出现的所有出现; （13）strdestroy(S):字符串销毁运算。若字符串字符串销毁运算。若字符串S存在存在,执行执行strdestroy运算后运算后,S被销毁。被销毁。 ADT string4.1.3 字符串的存储及其实现字符串的存储及其实现 1、串的顺序存储及其部分运算的实现、串的顺序存储及其部分运算的实现串的顺序存储使用数组存放

8、，具体类型定义如下：串的顺序存储使用数组存放，具体类型定义如下： #define MAXSIZE 100 typedef struct char strMAXSIZE; int length ; seqstring; 若S=“abcdef”, i=4, T=“kk” 执行strinsert(S,i,T)后，S=“abckkdef”初始状态初始状态初始状态初始状态初始状态初始状态void strinsert(seqstring S, int i , seqstring T) int k; if (iS-length+1 | S-length+ T.lengthMAXSIZE-1) printf(

9、cannot insertn); else for(k=S-length-1;k=i1;k-) 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)n若若S=“abcdefg”, i=3, len=3n执行执行strdelete(S,i,len)后，后，S=“abfg”void strdelete(seqstring S,int i,int len) int k; if (iS-length

10、 | i+len-1S-length) printf( cannot deleten); else for(k=i+len-1; klength;k+) S-strk-len= S-strk; S-length=S-length-len; S-strS-length=0; （3）连接运算）连接运算strconcat(S1,S2)n若若S1=“abcdef”, S2=“ab”n执行执行strconcat(S1,S2)后后,S=“abcdefab”seqstring * strconcat(seqstring S1,seqstring S2) int i; seqstring *r; if (S1

11、.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)n若若S=“abcdefg”, i=3, len=2执行执行subst

12、ring(S,i,len) =“cd”n若若S=“abc”, i=3, len=2,出错。出错。seqstring *substring(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

13、 串的链式存储及其部分运算的实现串的链式存储及其部分运算的实现串的链式存储采用单链表的形式实现，结点定义：串的链式存储采用单链表的形式实现，结点定义：typedef struct node char data; struct node *next; linkstrnode;typedef linkstrnode *linkstring; 例如，例如， linkstring S1=“abcde”，其存储结构如下图：，其存储结构如下图： 对于对于linkstring *S; S=&S1; 其存储结构如下图：其存储结构如下图： abcde （1）创建字符串运算）创建字符串运算strcreate (S

14、) void strcreate (linkstring *S)由参数由参数S返回创建的串。返回创建的串。S为指向为指向linkstring类型的指针。不然，类型的指针。不然，有以下示意图。有以下示意图。（1）创建字符串运算）创建字符串运算strcreate (S) 按按void strcreate (linkstring *S)调用调用,有正确结果有正确结果: （1）创建字符串运算）创建字符串运算strcreate (S) void strcreate (linkstring *S) char ch; linkstrnode *p,*r; *S=NULL; r=NULL; while (ch

15、=getchar()!=n) p=(linkstrnode *)malloc(sizeof(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;

16、 p=*S, k=1;/p指向指向S串的头部串的头部 while (p & knext ; k+; if (!p) printf(errorn); else q=T; while(q-next) q=q-next; q-next=p-next; p-next=T; （3）删除运算）删除运算strdelete(S,i,len)（3）删除运算）删除运算strdelete(S,i,len) void strdelete(linkstring*S,int i,int len) int k ; linkstring p,q,r;/q为为p的前驱，的前驱，r指向待回收的结点指向待回收的结点 p=*S, q

17、=null; k=1; while (p & knext ; k+; /p指向第指向第i个结点个结点 if (!p) printf(“error1n”); else k=1; while(knext ;k+; /p指向待删除子串的最后元素指向待删除子串的最后元素 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;

18、r=r-next; free(p); （4）连接运算）连接运算strconcat(S1,S2)void strconcat(linkstring *S1, linkstring S2) linkstring p; if (!(*S1) ) *S1=S2; return; else if (S2) /*S1和和S2均不为空串均不为空串*/ p=*S1; /*用用p查找查找S1的最后一个字符的位置的最后一个字符的位置*/ while(p-next ) p= p-next; p-next=S2; （5）求子串运算）求子串运算substring(S,i,len) linkstring substrin

19、g(linkstring S,int i, int len) int k; linkstring p,q,r,t;/*r返回结果串返回结果串,q指向指向r尾；尾；t指向新生成的结点，链接到指向新生成的结点，链接到q的后面的后面*/ p=S, k=1; while (p & knext;k+; /*p指向第指向第i个个*/ if (!p) printf(error1n); return(null); else r=(linkstring) malloc (sizeof(linkstrnode); r-data=p-data; r-next=null; k=1; q=r; /*用用q始终指向子串的

20、最后一个字符的位置始终指向子串的最后一个字符的位置*/ 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中首次出现的起始位置称中首次出现的起始位置称为字符串的模式匹配，其中称为字符串的模式匹配，其中称p为为模式模式(pattern），），t为正文为正文(text)，t的长度远远大于的长度远远大于p的长度。的长度

21、。 例如例如 t=“abcde”, p=“cd”,index(p,t)=2 p=“bd”,index(p,t)=0 4.2 字符串的模式匹配字符串的模式匹配4.2.1 朴素的模式匹配算法朴素的模式匹配算法 朴素模式匹配算法的基本思想是：用朴素模式匹配算法的基本思想是：用p中的每个中的每个字符去与字符去与t中的字符一一比较：中的字符一一比较： 正文正文t： t1 t2 tmtn模式模式p： p1 p2 pm如果如果t1=p1,t2=p2,.tm=pm，则模式匹配成功；否则，则模式匹配成功；否则将将p向右移动一个字符的位置，重新用向右移动一个字符的位置，重新用p中的字符从中的字符从头开始与头开始与

22、t中相对应的字符依次比较，即：中相对应的字符依次比较，即： 如此反复，直到匹配成功或者如此反复，直到匹配成功或者p已经移到使已经移到使t中剩中剩下的字符个数小于下的字符个数小于p的长度的位置，此时意味着模的长度的位置，此时意味着模式匹配失败，表示式匹配失败，表示t中没有子串与模式中没有子串与模式p相等，我们相等，我们约定返回约定返回-1代表匹配失败。代表匹配失败。例如例如t=“abcde”, p=“cd”,比较：比较：t0=p0? False t1=p0? Falset2=p0? truet3=p1? true 结束：结束：index(p,t)=2例如例如t=“abcde”,p=“cda”,比

23、较：比较：t0=p0? False t1=p0? Falset2=p0? truet3=p1? true t4=p2? False t3=p0?该比较无必要，该比较无必要，此时此时t中剩下的长度中剩下的长度2小于小于p长度长度3.结束：结束：index(p,t)=0算法实现算法实现n涉及到回溯。算法实现时，定义两个下标涉及到回溯。算法实现时，定义两个下标变量变量i和和j，分别指向，分别指向t和和p中当前比较的字符中当前比较的字符当当ti和和pj相等时，保留相等时，保留t当前下标当前下标i不变（便于不变（便于回溯），而只改变回溯），而只改变p当前下标当前下标j+，且由，且由i+j来取来取到到t中

24、的后续字符中的后续字符ti+j继续和继续和pj进行比较。进行比较。 if (p.strj=t.stri+j ) j+;遇到不相等时，遇到不相等时，t下标下标i才增才增1。例如例如t=“abcde”,p=“cda”,比较：比较：t0+0=p0? False t1+0=p0? Falset2+0=p0? truet2+1=p1? true t2+2=p2? False t3=p0?结束：结束：index(p,t)=0int index(seqstring p, seqstring t) /返回下标返回下标 int i,j, succ; i=0; succ=0; /* succ为匹配成功的标志为匹配

25、成功的标志*/ 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算法）是由算法）是由D.E.knuth与与V.R.Pratt和和J.H.Morris同时发现的，此算法可以在同

26、时发现的，此算法可以在O（n+m)的时间数量级上完成串的模式匹配算法。的时间数量级上完成串的模式匹配算法。 例如例如 t=“abcabfabca”, p=“abcabdf”比较：比较： t=“abcabfabca”, p=“abcabdf”, 此时有此时有t5p5按朴素匹配法，接下来按朴素匹配法，接下来p右移一格，从右移一格，从t的的1位置位置,即即“b”开始重新比较开始重新比较,有无必要？可否加快有无必要？可否加快p向右滑动的速度向右滑动的速度?由前一次比较，有由前一次比较，有t04=p04， t5p5 。观察朴素匹配法，接下来观察朴素匹配法，接下来p右移右移1格，从格，从t1位置重新位置重

27、新比较比较: t=“abcabfabca”, “abcabdf”, 要该比较成功，首先需保证要该比较成功，首先需保证t14=p03，由前面，由前面的结果，这就是要的结果，这就是要p14 =p03，由，由p可看出，该可看出，该式不成立。此次比较没有必要进行。式不成立。此次比较没有必要进行。由前一次比较，有由前一次比较，有t04=p04， t5p5 。同理，同理，p右移右移2格，从格，从t2位置重新比较位置重新比较: t=“abcabfabca”, “abcabdf”, 要该比较成功，首先需保证要该比较成功，首先需保证t24=p02，由前面，由前面的结果，这就是要的结果，这就是要p24 =p02，

28、由，由p可看出，该可看出，该式不成立。此次比较也没有必要进行。式不成立。此次比较也没有必要进行。由前一次比较，有由前一次比较，有t04=p04， t5p5 。同理，同理，p右移右移3格，从格，从t3位置重新比较位置重新比较: t=“abcabfabca”, “abcabdf”, 要该比较成功，首先需保证要该比较成功，首先需保证t34=p01，这就是，这就是要要p34 =p01，由，由p可看出，该式成立。可看出，该式成立。实际上，由于可推断出实际上，由于可推断出t3=p0、t4=p1成立，接下来的成立，接下来的比较，只需从比较，只需从t5与与p2开始。开始。即当即当t5p5时，接下来（时，接下来

29、（next）就从）就从t5与与p2开始比较，开始比较，加快了加快了p向右滑动的速度。那么，向右滑动的速度。那么，p中下一次比较的下标（中下一次比较的下标（next值）从何而来？值）从何而来？p=“aacaadf” 对于串对于串p中的中的“d”，即，即p5，之，之前存在的前缀有：前存在的前缀有：aaaaacaacaaacaa除最后一个，其它都是真前缀除最后一个，其它都是真前缀.p5之前存在的后缀有：之前存在的后缀有：aaacaaacaaaacaa除最后一个，其它都是真除最后一个，其它都是真后缀后缀.p5之前的真前缀和真后缀有两组相等，而最之前的真前缀和真后缀有两组相等，而最大长度是大长度是2。记

30、为：。记为：next5=2.next的含义的含义n是模式串是模式串P中每个字符的属性值。中每个字符的属性值。表明当表明当Pi Tr时，下一次将从时，下一次将从Pnexti与与Tr开始后续对应字符的比较。开始后续对应字符的比较。在求得模式串在求得模式串p的的next函数之后，匹配可如下进行：函数之后，匹配可如下进行：假设以假设以i和和j分别指示主串分别指示主串t和模式串和模式串p中正待比较的字中正待比较的字符，令符，令i、j的初值为的初值为0。在匹配过程中：。在匹配过程中：if ti=pj，则，则i+，j+；否则；否则, i不变，而不变，而j退到退到nextj的位置（的位置（j=nextj）再比

31、较）再比较ti=pj 。若相。若相等，则等，则i+，j+；否则否则j再退到下一个再退到下一个nextj值的值的位置，依此类推。位置，依此类推。若若j退到退到-1（即（即p的第一个字符的第一个字符“失配失配”），则），则此时此时i+，j+ ，即将主串继续向右滑动一个位置，即将主串继续向右滑动一个位置(i+)，从，从主串的下一个字符主串的下一个字符起和模式串重新开始匹配。起和模式串重新开始匹配。以下给出顺序存储结构下的以下给出顺序存储结构下的KMP算法。算法。# define maxsize 100typedef struct char strmaxsize; int length ; seqst

32、ring;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+; j+; else j=nextj; if (j=p.length) return (i-p.length); else return(-1); 以下说明如何求以下说明如何求next函数：函数：由定义：由定义：next0=-1;表明当表明当p0 tr时时,将从将从p-1与与tr开始开始比较，由于比较，由于p-1不存在，可理解成从不存在，可理解成从p0与与tr+1开始比较

33、。开始比较。设设nexti=j,这表明在模式串这表明在模式串p中存在下列关系：中存在下列关系：“p0pj-1”=“pi-jpi-1”其中其中j为满足为满足1=ji的某个值，此时的某个值，此时nexti+1的取值可的取值可能有两种情况：能有两种情况：（1）若）若pj=pi则表明在模式中则表明在模式中“p0pj-1pj”=“pi-jpi-1pi” 此时此时nexti+1=nexti+1=j+1（2）若）若pj pi 则表明在模式串中则表明在模式串中“p0pj-1pj” “pi-jpi-1pi”此时可把求此时可把求next函数值的问题看成是一个模式匹配函数值的问题看成是一个模式匹配的问题，整个模式串

34、既是主串又是模式串。的问题，整个模式串既是主串又是模式串。当当pj pi时，根据时，根据next函数的定义，此时应比较函数的定义，此时应比较pnext(j)与与pi是否相等。是否相等。同理，令同理，令next(j)=k，若若 pk pi,则将模式继续向则将模式继续向右滑动，取右滑动，取pnext(k)和和pi比较，比较，依次类推，直至，依次类推，直至pi和模式中某个字符匹配成功，或者要将和模式中某个字符匹配成功，或者要将p-1和和pi比较比较，则，则nexti+1=0；void getnext(seqstring p,int next)int i,j; next0=-1; i=0;j=-1;

35、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维数组，其每一个元素均位于维数组，其每一个元素均位于n个个向量中，每个元素最多具有向量中，每个元素最多具有n个前驱结点和个前驱结点和n个后继结个后继结点；点；ADT array4.3.3

36、 数组的顺序存储及实现数组的顺序存储及实现 由于数组是由有限的元素构成的有序集合，数由于数组是由有限的元素构成的有序集合，数组的大小和元素之间的关系一经确定，就不再发生组的大小和元素之间的关系一经确定，就不再发生变化，因此数组均采用顺序存储结构实现，它要求变化，因此数组均采用顺序存储结构实现，它要求一片连续的存储空间存储。一片连续的存储空间存储。 多维数组数据元素的顺序存储有两种方式：多维数组数据元素的顺序存储有两种方式： 按行优先存储按行优先存储 按列优先存储按列优先存储例如：对于二维数组例如：对于二维数组Amn： a00 a01 a0( n-1) a10 a11 a1( n-1) A =

37、a(m-1)0 a(m-1)1 a(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) 。 对于数组，一旦确定了它的维数和各维的长度，对于数组，一旦确定了它的维数和各维的长度，便可以为它分配存储空间；当规定了数组元素的存储便可以为

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

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

40、表示及其部分运算的实现。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 el

41、ements; if (b1=0|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)

42、 int off; if (i1=A.index0 | i2=A.index1 | i3=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

43、| i3=A-index2) return (0 ); /*处理下标非法的情况处理下标非法的情况*/ off= i1A-c0+ i2A-c1+ i3A-c2; *(A-base + off)=e; /*赋值赋值*/ return(1); 本节主要研究对称矩阵、三角矩阵和带状矩阵本节主要研究对称矩阵、三角矩阵和带状矩阵的压缩存储。所谓压缩存储即为：多个相同值的结的压缩存储。所谓压缩存储即为：多个相同值的结点只分配一个存储空间，值为零的结点不分配空间。点只分配一个存储空间，值为零的结点不分配空间。 4.4 特殊矩阵特殊矩阵4.4.1 对称矩阵的压缩存储对称矩阵的压缩存储 如果矩阵的行数和列数相等，

44、则称该矩阵为方如果矩阵的行数和列数相等，则称该矩阵为方阵。若阵。若nn阶的方阵阶的方阵A满足：满足： aij=aji (0in-1 , 0jn-1)则称矩阵则称矩阵A为为对称矩阵对称矩阵。在对称矩阵中，几乎有一在对称矩阵中，几乎有一半元素的值是对应相等的。如果将半元素的值是对应相等的。如果将A中所有元素进中所有元素进行存储，那将会造成空间的浪费，且行存储，那将会造成空间的浪费，且n值越大，浪值越大，浪费将越严重。费将越严重。 4.4 特殊矩阵特殊矩阵 对于对称矩阵压缩存储时只需存储对角线以上对于对称矩阵压缩存储时只需存储对角线以上或对角线以下的部分，未存储的部分可以利用元素或对角线以下的部分，

45、未存储的部分可以利用元素之间的对称性来访问。之间的对称性来访问。 现考虑只存储对称矩阵现考虑只存储对称矩阵A对角线以下的部分对角线以下的部分（即下标满足（即下标满足ij的数组元素的数组元素aij）：）： a00 a10 a11 A = a20 a21 a22 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

46、 当当i j 4.4.2 三角矩阵的压缩存储三角矩阵的压缩存储 1、下三角矩阵、下三角矩阵 a00 0 0 0 a10 a11 0 . 0 A = a20 a21 a22 . 0 a(n-1)0 a(n-1) (n-1) 仍考虑采用按行优先方式，仍考虑采用按行优先方式， A中下三角部分的任何一个中下三角部分的任何一个元素元素aij(ij)压缩存储后的地址计算公式为：压缩存储后的地址计算公式为： address(aij)= address(a00)+ (i*(i+1)/2+j)L 当当ij与对称矩阵不同的是，当与对称矩阵不同的是，当ij时，时，aij的值为的值为0，其没有对应的存储空间，其没有对

47、应的存储空间。 4.4.3 带状矩阵的压缩存储带状矩阵的压缩存储 对于对于nn阶方阵，若它的全部非零元素落在一个以主阶方阵，若它的全部非零元素落在一个以主对角线为中心的带状区域中，这个带状区域包含主对角线下对角线为中心的带状区域中，这个带状区域包含主对角线下面及上面各面及上面各b条对角线上的元素以及主对角线上的元素，那条对角线上的元素以及主对角线上的元素，那么称该方阵为半带宽为么称该方阵为半带宽为b的带状矩阵。带状矩阵的特点是：的带状矩阵。带状矩阵的特点是：对于矩阵元素对于矩阵元素aij，若，若i-jb或或j-ib，即，即|i-j|b，则，则aij=0。 b条对角线条对角线 b条对角线条对角线

48、 主对角线主对角线 带状矩阵进行压缩存储时，只存储带状部分内带状矩阵进行压缩存储时，只存储带状部分内部的元素，对于带状区域以外的元素，即部的元素，对于带状区域以外的元素，即|i-j|b的的aij，均不分配存储空间。为了方便起见，我们规定，均不分配存储空间。为了方便起见，我们规定按如下方法进行存储：除第一行和最后一行外，每行按如下方法进行存储：除第一行和最后一行外，每行都分配都分配2b+1个元素的空间，将带状区域中的元素存个元素的空间，将带状区域中的元素存储于（储于（(2b+1) n-2b）L个存储单元之中，其中个存储单元之中，其中L为为每个元素占用空间的大小。仍考虑采用按行优先的存每个元素占用

49、空间的大小。仍考虑采用按行优先的存储方式，于是可以得到带状区域中任何一个元素储方式，于是可以得到带状区域中任何一个元素aij的地址计算公式为：的地址计算公式为：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

50、 数据对象数据对象D:具有相同类型的数据元素构成的有限集合具有相同类型的数据元素构成的有限集合; 数据关系数据关系R:D中的每个元素均位于中的每个元素均位于2个向量中个向量中,每个元素最每个元素最多具有多具有2个前驱结点和个前驱结点和2个后继结点个后继结点,且且D中零元素的个数远远中零元素的个数远远大于非零元素的个数。大于非零元素的个数。 稀疏矩阵的基本运算如下稀疏矩阵的基本运算如下: （1）createspmatrix (A) 创建一个稀疏矩阵创建一个稀疏矩阵A; 4.5 稀疏矩阵稀疏矩阵 （2）compressmatrix (A,B) 创建稀疏矩阵创建稀疏矩阵A的压缩的压缩存储表示存储表示

51、B; （3）destroyspmatrix (A) 销毁稀疏矩阵销毁稀疏矩阵A; （4）printspmatrix (A) 将已知稀疏矩阵将已知稀疏矩阵A,将将A复制到复制到B中中; （5）copyspmatrix(A,B) 将将A复制到复制到B （6）addspmatrix (A,B,C) 已知稀疏矩阵已知稀疏矩阵A和和B,且且两者的行数和列数对应相等两者的行数和列数对应相等,求求A和和B相加的结果放入相加的结果放入C中中; （7）subspmatrix (A,B,C) 已知稀疏矩阵已知稀疏矩阵A和和B,且且两者的行数和列数对应相等两者的行数和列数对应相等,求求A和和B相减的结果放入相减的结

52、果放入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 spmatrix4.5.2 稀疏矩阵的顺序存储及其实现稀疏矩阵的顺序存储及其实现 稀疏矩阵的顺序存储方法包括：三元组表示法、带辅助稀疏矩阵的顺序存

53、储方法包括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示法，其中以三元组表示行向量的二元组表示法和伪地址表示法，其中以三元组表示法最常用，故在此主要介绍稀疏矩阵的三元组表示。法最常用，故在此主要介绍稀疏矩阵的三元组表示。 在三元组表示法中，稀疏矩阵的每个非零元素可以采用如在三元组表示法中，稀疏矩阵的每个非零元素可以采用如下形式表示：下形式表示： ( i, j, value )其中其中i表示非零元素所在的行号，表示非零元素所在的行号，j表示非零元素所在的列号，表示非零元素所在的列号，value表示非零元素的值。采用三元组表示法表示一个稀疏矩表示非零元素的值。采用三元组表示法表示一个稀疏矩

54、阵时，首先将它的每一个非零元素表示成上述的三元组形式，阵时，首先将它的每一个非零元素表示成上述的三元组形式，然后按行号递增的次序、同一行的非零元素按列号递增的次然后按行号递增的次序、同一行的非零元素按列号递增的次序将所有非零元素的三元组表示存放到一片连续的存储单元序将所有非零元素的三元组表示存放到一片连续的存储单元中即可。中即可。以下是稀疏矩阵以下是稀疏矩阵A76及其对应的三元组表示。及其对应的三元组表示。 B 0 1 2 0 7 6 7 0 0 5 0 1 0 1 0 2 -5 0 0 0 2 0 0 2 0 4 1 3 0 0 0 0 0 3 1 3 2 0 0 0 0 0 0 4 2 0

55、 3 12 0 0 0 0 0 5 4 0 12 0 0 0 0 0 4 6 5 5 4 0 0 21 0 0 0 7 6 2 21 稀疏矩阵稀疏矩阵A A的三元组表示的三元组表示B B的第一行表示的第一行表示A的行数、列数及非零元素的总个数。的行数、列数及非零元素的总个数。 稀疏矩阵稀疏矩阵A及其对应的三元组表示矩阵及其对应的三元组表示矩阵B的数据的数据类型定义如下类型定义如下: typedef struct int data100100; /*存放稀疏矩阵的二维存放稀疏矩阵的二维 数组数组*/ int m,n; /*分别存放稀疏矩阵分别存放稀疏矩阵 的行数和列数的行数和列数*/ matri

56、x;typedef int spmatrix1003; /*稀疏矩阵对应的三元组表示的类型稀疏矩阵对应的三元组表示的类型 */1、产生稀疏矩阵三元组表示的算法、产生稀疏矩阵三元组表示的算法void compressmatrix(matrix A , spmatrix B) int i, j, k=1; for ( i=0; iA.m; i+) for (j=0; j0) for (i=0; in; i+) xi=0; for (i=1; i=t; i+) xBi1=xBi1+1; /*统计统计B中每一列非零元素的个数中每一列非零元素的个数*/ /*求矩阵求矩阵C中每一行非零元素三元组的起始位置中每一行非零元素三元组的起始位置*/y0=1;for (i=1; in; i+) yi=yi-1+xi-1; for (i=1; i=t; i+) /*将将B中非零元素交换行号、列号后写入中非零元素交换行号、列号后写入C中中 其最终的位置上其最终的位置上*/ j=yBi1; Cj0= Bi1; Cj1= Bi0; Cj2= Bi2; yBi1=j+1; 三元组顺序表虽然节省了存储空间，但时间三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于有可能增