第 4章 字符串、数组和特殊矩阵
字符串
字符串的模式匹配
稀疏矩阵
数组
特殊矩阵
4,1 字符串
4.1.1 字符串的基本概念字符串是由零个或多个字符构成的有限序列，
一般可表示成如下形式：
,c1 c2 c3…,cn” (n≥ 0)
串中所含字符的个数 n称为字符串的长度；当 n=0时，
称字符串为 空串 。
串中任意个连续的字符构成的子序列称为该串的 子串,包含子串的串称 为 主串 。通常称字符在字符串序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。例如,T =“STUDENT”,S=“UDEN”,则 S
是 T的子串,S在 T中出现的位置为 3。
两个 字符串相等,当且仅当两个串的长度相等，
并且各个对应位置的字符都相等。例如：
T1=“REDROSE” T2=“RED ROSE”
由于 T1和 T2的长度不相等，因此 T1≠T2 。
若
T3=“STUDENT” T4=“STUDENS”
虽然 T3和 T4的长度相等，但两者有些对应的字符不同，因而 T3≠T4 。
值得一提的是，若 S=― ‖，此时 S由一个空格字符组成，其长度为 1，它不等价于空串，因为空串的长度为 0。
4.1.2 字符串类的定义
ADT string {
数据对象 D：由零个或多个字符型的数据元素构成的有限集合；
数据关系 R,{<ai,ai+1>|其中 ai,ai+1?D,
i=1,2,…… n-1 }
字符串的基本操作如下：
（ 1） Strcreate (S)
（ 2） Strassign(S,T)
（ 3） Strlength(S)
（ 4） Strempty(S)
（ 5） Strclear(S)
（ 6） Strcompare(S1,S2)
（ 7） Strconcat(S1,S2)
（ 8） Substring(S,i,len)
（ 9） Index(P,T)
（ 10） Strinsert(S,i,T)
（ 11） Strdelete(S,i,len)
（ 12） Replace(S,T1,T2)
（ 13） Strdestroy(S)
} ADT string
4.1.3 字符串的存储及其实现
1、串的顺序存储及其部分运算的实现串的顺序存储使用数组存放，具体类型定义如下：
#define MAXSIZE 100
typedef struct {
char str[MAXSIZE];
int length ;
} seqstring;
（ 1）插入运算 strinsert(S,i,T)
void strinsert(seqstring *S,int i,seqstring T)
{ int k;
if (i<1 || i>S->length+1 || S->length + T.length>MAXSIZE)
printf("connot insert\n“);
else
{
for(k=S->length-1;k>=i-1;k--)
S->str[T.length+k]=S->str[k];
for (k=0;k<T.length;k++)
S->str[i+k-1]=T.str[k];
S->length= S->length + T.length;
S->str[S->length]=?\0?;
}
}
（ 2）删除运算 strdelete(S,i,len)
void strdelete(seqstring *S,int i,int len)
{ int k ;
if (i<1 || i>S->length||i+len-1>S->length)
printf(,cannot delete\n”);
else
{
for(k=i+len-1; k<S->length;k++)
S->str[k-len]= S->str[k];
S->length=S->length-len;
S->str[S->length]=?\0?;
}
}
（ 3）连接运算 strconcat(S1,S2)
seqstring * strconcat(seqstring S1,seqstring S2)
{ int i; seqstring *r;
if (S1.length+S2.length>MAXSIZE)
{ printf("cannot concate"); return(NULL);}
else
{ r=(seqstring*)malloc (sizeof(seqstring));
for (i=0; i<S1.length;i++) r->str[i]= S1.str[i];
for (i=0; i<S2.length;i++)
r->str[ S1.length+i]= S2.str[i];
r->length= S1.length+ S2.length;
r->str[r->length]='\0';
}
return (r);
}
（ 4）求子串运算 substring(S,i,len)
seqstring *substring(seqstring S,int i,int len)
{ int k; seqstring *r;
if (i<1 || i>S.length || i+len-1>S.length)
{ printf(“error\n”); return(NULL);}
else
{ r=(seqstring*) malloc (sizeof(seqstring));
for(k=0;k<len;k++) r->str[k]= S.str[i+k-1];
r->length=len;
r->str[r->length]='\0';
}
return(r);
}
2 串的链接存储及其部分运算的实现串的链接存储采用单链表的形式实现，其中每个结点的定义如下：
typedef struct node
{
char data;
struct node *next;
} linkstrnode;
typedef linkstrnode *linkstring;
例如，串 S=―abcde‖，其链接存储结构如下图所示：
a b c d e ∧
S
（ 1）创建字符串运算 strcreate (S)
void strcreate (linkstring *S)
{ char ch; linkstrnode *p,*r;
*S=NULL; r=NULL;
while ((ch=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;
p=*S,k=1;
while (p && k<i-1)
{ p=p->next ; k++; }
if (!p) printf("error\n");
else
{ q=T;
while(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 && k<i)
{q=p; p=p->next ; k++;}
if (!p) printf("error1\n");
else
{ k=1;
/*p从第 i个元素开始查找长度为 len子串的最后元素 */
while(k<len && p )
{ p=p->next ;k++;}
if(!p) printf("error2\n");
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; return;}
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 && k<i) {p= p->next;k++;}
if (!p) {printf("error1\n"); return(null);}
else
{
r=(linkstring) malloc (sizeof(linkstrnode));
r->data=p->data; r->next=null;
k=1; q=r; /*用 q始终指向子串的最后一个字符的位置 */
while (p->next && k<len) /*取长度为 len的子串 */
{
p=p->next ;k++;
t=(linkstring) malloc (sizeof (linkstrnode));
t->data=p->data;
q->next=t; q=t;
}
if (k<len) {printf("error2\n") ; return(null);}
else
{q->next=null; return(r);} /*处理子串的尾部 */
}
}
4.2 字符串的模式匹配寻找字符串 p在字符串 t中首次出现的起始位置称为字符串的 模式匹配,其中称 p为 模式 (pattern）,t
为 正文 (text),t的长度远远大于 p的长度。
4.2.1 朴素的模式匹配算法朴素模式匹配算法的基本思想是：用 p中的每个字符去与 t中的字符一一比较：
正文 t,t1 t2 …… tm…… tn
模式 p,p1 p2 …… pm
如果 t1=p1,t2=p2,…,.tm=pm，则模式匹配成功；否则将 p向右移动一个字符的位置，重新用 p中的字符从头开始与 t中相对应的字符依次比较，即：
t1 t2 t3 …… tm tm+1…… tn
p1 p2…… pm-1 pm
如此反复，直到匹配成功或者 p已经移到使 t中剩下的字符个数小于 p的长度的位置，此时意味着模式匹配失败，表示 t中没有子串与模式 p相等，我们约定返回 -1代表匹配失败。
朴素模式匹配算法的具体实现如下：
int index(seqstring p,seqstring t)
{ int i,j,succ;
i=0; succ=0; /* succ为匹配成功的标志 */
while((i<=t.length-p.length+1) && (!succ))
{ j=0 ; succ=1; /*用 j扫描模式 p*/
while ((j<=p.length-1) && succ)
if (p.str[j]==t.str[i+j] ) j++;
else succ=0;
++i;
}
if (succ) return (i-1);
else return (-1);
}
4.2.2 快速模式匹配算法（ KMP算法）
首先我们来分析下图所示的情况：
t0 t1 t2 …… tk tk+1 tk+2…… tr-2 tr-1 tr……,
‖ ‖ ‖ ‖ ‖ ╫
p0 p1 p2…… pi-2 pi-1 pi………,
（ 4-1）
t0 t1 t2 …… tk tk+1 tk+2…… tr-2 tr-1 tr……,
‖ ‖ ‖ ‖
p0 p1 …… pi-2 pi-1
pi………
（ 4-2）
t0 t1 t2 …… tk tk+1 tk+2…… tr-2 tr-1 tr……,
‖ ‖ ‖
p0 ……… pi-3 pi-2 pi-1 pi……
（ 4-3）
(4-1)式表明此次匹配从 p0与 tk开始比较，当比较到 pi与 tr时出现不等情况，于是将模式右移一位，变成 (4-2)所示的状态，若此次比较成功，则必有 p0= tk+1,p1= tk+2,…… pi-2=
tr-1，且 pi-1≠p i；而根据 (4-1)的比较结果有,p1= tk+1,p2=
tk+2,…… pi-1= tr-1，因此有,p0= p1,p1= p2,…… pi-2=
pi-1。这个性质说明在模式 p中 pi之前存在一个从 p0开始长度为 i-1的连续序列 p0 p1 …… pi-2 和以 pi-1为结尾，长度同样为 i-1的连续序列 p1 p2…… pi-1其值对应相等，即：
p0 p1 p2…… pi-2 pi-1 pi………,
简记为：
[p0—pi-2]=[p1—pi-1]
称模式 p中 pi之前存在 长度为 i-1的真前缀和真后缀的匹配 。
反之，若在 (4-1)所示的状态下，模式 p中 pi之前存在长度为 i-1的真前缀和真后缀的匹配，即 [p0—pi-
2]=[p1—pi-1] 且 pi-1≠p i；当 pi与 tr出现不等时，根据前面已比较的结果 p1= tk+1,p2= tk+2,…… pi-1= tr-1，
于是可得 p0= tk+1,p1= tk+2,…… pi-2= tr-1，因此接下来只需从 pi-1与 tr开始继续后继对应字符的比较即可。
再假设在 (4-1)所示的状态下，模式右移一位成为状态 (4-2)后，匹配仍然不成功，说明 [p0—pi-2]
[p1—pi-1]或 pi-1=pi，于是模式再右移一位，成为状态 (4-3)，若此次匹配成功，仿照上述分析，必有：
p0 p1 p2…… pi-3 pi-2 pi-1 pi………,
即：
[p0—pi-3]=[p2—pi-1]
说明模式 p中 pi之前存在长度为 i-2的真前缀和真后缀的匹配。由 (4-3)表明，在 (4-1)所示的状态下，
若模式 p中 pi之前最长真前缀和真后缀匹配的长度为
i-2，当 pi与 tr出现不等时，接下来只需从 pi-2与 tr开始继续后继对应字符的比较。
考虑一般情况。在进行模式匹配时，若模式 p中
pi之前最长真前缀和真后缀匹配的长度为 j，当
pi?tr时，则下一步只需从 pj与 tr开始继续后继对应字符的比较,而不应该将模式一位一位地右移，也不应该反复从模式的开头进行比较。这样既不会失去任何匹配成功的机会，又极大地加快了匹配的速度。
根据上述分析，在模式匹配过程中，每当出现 pi?tr时，
下一次与 tr进行比较的 pj和模式 p中 pi之前最长真前缀和真后缀匹配的长度密切相关；而模式 p中 pi之前最长真前缀和真后缀匹配的长度只取决于模式 p的组成，与正文无关。
于是我们可以针对模式 p定义一个数组 next[m]，其中
next[i]表示当 pi?tr时，下一次将从 pnext[i]与 tr开始继续后继对应字符的比较。显然,next[i]的值与模式 p中 pi之前最长真前缀和真后缀匹配的长度密切相关。下面考虑如何根据模式 p的组成求数组 next的值。我们规定：
next[0]=-1
这表明当 p0?tr时，将从 p-1与 tr开始继续后继对应字符的比较；
然而 p-1是不存在的，我们可以将这种情况理解成下一步将从
p0与 tr+1开始继续后继对应字符的比较。
以下假设 next[0],next[1],……,next[i]的值均已求出，现要求 next[i+1]的值。由于在求解 next[i]时已得到
pi之前最长真前缀和真后缀匹配的长度，设其值为 j，即：
p0 p1 p2…… pi-j ……,pj-1 pj…… pi-2 pi-1 pi pi+1……
如果此时进一步有 pj=pi，则 pi+1之前最长真前缀和真后缀匹配的长度就为 j+1，且 next[i+1]=j+1;反之，若 pj?pi，注意到，求 pi+1之前最长真前缀和真后缀匹配问题本质上仍然是一个模式匹配问题，只是在这里模式和正文都是同一个串
p而已。因此当 pj?pi时，应该检查 pnext[j]与 pi是否相等；若相等，则 next[i+1]=next[j]+1；如仍然不相等，则再取
pnext[next[j]]与 pi进行比较,…… 直至要将 p-1与 pi进行比较为止，此时 next[i+1]=0。
以下给出了根据模式 p的组成求数组 next值的算法：
void getnext(seqstring p,int next[])
{ int i,j;
next[0]=-1;
i=0; j=-1;
while (i<p.length)
{
if (j==-1||p.str[i]==p.str[j])
{++i;++j;next[i]=j;}
else
j=next[j];
}
for(i=0;i<p.length;i++)
printf("%d",next[i]);
}
KMP算法基本思想如下：
假设以 i和 j分别指示正文 t和模式 p中正待比较的字符，令 i,j的初值为 0；若在匹配过程中 ti=pj，则 i
与 j分别加 1；否则 i不变，而 j退到 next[j]的位置继续比较（即 j= next[j]）；若相等，则指针各自增加
1；否则 j再退到下一个 next[j]值的位置，依此类推，
直至下列两种可能,
(1)一种是 j退到某个 next（ next[..[next[j]]… ]））
时,ti与 pj字符比较相等，则 i,j指针各自增加 1
后继续进行比较；
(2)一种是 j退到 -1（即模式的第一个字符,失配,），
此时需将正文指针 i向右滑动一个位置，即从正文的下一个字符 ti+1起和模式 p重新从头开始比较。
KMP算法的具体实现如下：
int kmp(seqstring t,seqstring p,int next[])
{ int i,j;
i=0; j=0;
while (i<t.length && j<p.length)
{
if (j==-1||t.str[i]==p.str[j])
{i++; j++;}
else j=next[j];
}
if (j==p.length) return (i-p.length);
else return(-1);
}
4.3 数 组
4.3.1 数组和数组元素数组是线性表的一种存储方式。其实，数组本身也可以看成是线性表的推广，数组的每个元素由一个值和一组下标确定，在数组中，对于每组有定义的下标都存在一个与之相对应的值；而线性表是有限结点的有序集合，若将其每个结点的序号看成下标，线性表就是一维数组（向量）；当数组为多维数组时，其对应线性表中的每个元素又是一个数据结构而已。
例如，对于一个 m?n的二维数组 A[m][n]：
a00 a01 a02……… a0( n-1)
a10 a11 a12……… a1( n-1)
A = ┋ ┋ ┋ ┋
┋ ┋ ┋ ┋
a(m-1)0 a(m-1)1……… a(m-1)(n-1)
当把二维数组看成是线性表时，它的每一个结点又是一个向量（一维数组）。例如，上述二维数组 A可以看成是如下的线性表：
(A0,A1,A2,…… Am-1)
即 A中每一行成为线性表的一个元素，其中每个元素
Ai(0≤i≤m -1)都是一个向量；
（ ai0,ai1,ai2……,ai(n-1) ）
当然，也可以将上述二维数组 A看成如下的线性表：
(A0?,A1?,A2?,…… An-1?)
即 A中每一列成为线性表的一个元素，其中每一个元素 Ai?(0≤i≤n -1)都是一个向量,
（ a0i,a1i,a2i,…… a (m-1) i）
二维数组 A中的每一个元素 aij都同时属于两个向量，即：第 i+1行的行向量和第 j+1列的列向量，
因此每个元素 aij最多有两个前驱结点 a(i-1) j和 ai(j-1)，
也最多有两个后继结点 a(i+1) j和 ai(j+1)（只要这些结点存在）；特别地,a00没有前驱结点,a(m-1) (n-1)没有后继结点，边界上的结点均只有一个后继结点或一个前驱结点。
对于 m（ m>2）维数组，可以依据上述规律类推。
4.3.2 数组类的定义
ADT array {
数据对象 D：具有相同类型的数据元素构成的有序集合；
数据关系 R：对于 n维数组，其每一个元素均位于 n个向量中，
每个元素最多具有 n个前驱结点和 n个后继结点；
数组的基本操作如下：
（ 1） Initarray (A,n,index1,index2,…… index n)
（ 2） Destroyarray(A)
（ 3） Value(A,index1,index2,…… index n,x)
（ 4） Assign (A,e,index1,index2,…… index n)
} ADT array
4.3.3 数组的顺序存储及实现由于数组是由有限的元素构成的有序集合，数组的大小和元素之间的关系一经确定，就不再发生变化，因此数组均采用顺序存储结构实现，它要求一片连续的存储空间存储。
多维数组数据元素的顺序存储有两种方式：
按行优先存储
按列优先存储例如：对于二维数组 A[m][n]：
a00 a01 …………… a0( n-1)
a10 a11 …………… a1( n-1)
A = ┋ ┋ ┋
┋ ┋ ┋
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) 。
对于数组，一旦确定了它的维数和各维的长度，
便可以为它分配存储空间；当规定了数组元素的存储次序后，便可根据给定的一组下标值求得相应数组元素的存储位置。
现假设数组中每个元素占用 L个存储单元，若考虑按行优先存储方式，则上述 A数组中任何一个元素
aij的存储位置可以按以下公式确定：
address（ aij ） = address ( a00 ) + ( i× n+j )× L
若考虑按列优先的存储方式，数组中任何一个元素 aij存储位置的地址计算公式为：
address( aij ) = address ( a00 ) + (j× m +i )× L
多维数组的存储也和二维数组一样，存在两种存储方式：
按行优先和按列优先。但由于多维数组中数据元素间的关系较二维数组复杂，因此数据元素的地址计算公式也相对复杂些，但两者所采用的原理是相同的。
考虑 n维数组的情形：
datatype A[b1][b2]…… [bn]；
其中 b1,b2,…… bn为数组每一维的长度。仍假设每个元素占用 L个单元，则 n维数组 A中任何一个元素 A[j1][j2]…… [jn]在按行优先存储方式下的地址计算公式为：
address(A[j1][j2]…… [jn])=address(A[0][0]… [0])+
(b2× b3× …… bn× j1+ b3× b4× …… bn× j2+ …… bn× jn-1+
jn)× L
上式可以简写为：
address((A[j1][j2]…… [jn])=address(A[0][0]… [0])+
c1*j1+c2*j2+…… cn*jn
其中 cn=L,ci-1=bi× ci,1<i≤n 。
以下以三维数组为例，给出三维数组的顺序存储表示及其部分运算的实现。
typedef int datatype;
/*假设数组元素的值为整型 */
typedef struct {
datatype *base; /* 数组存储区的首地址指针 */
int index[3]; /* 存放三维数组各维的长度 */
int c[3] /* 存放三维数组各维的 ci值 */
} array；
1,数组初始化运算 initarray (A,b1,b2,b3)
int initarray (array *A,int b1,int b2,int b3)
{
int elements;
if (b1<=0||b2<=0||b3<=0) return( 0 );
A->index[0]=b1; A->index[1]=b2; A->index[2]=b3;
elements = b1 × b2 × b3;
A->base=(datatype*)malloc(elements× sizeof(datatype));
if (! (A->base)) return(0);
A->c[0]= b2 × b3; A->c[1]= b3; A->c[2]= 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<0 || i1>=A.index[0] || i2< 0 || i2>=A.index[1] ||
i3<0 || i3>=A.index[2])
return(0); /*处理下标非法的情况 */
off= i1× A.c[0]+ i2× A.c[1]+ i3× A.c[2];
*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<0 || i1>=A->index[0] || i2< 0 || i2>=A->index[1]
|| i3<0 || i3>=A->index[2])
return (0 ); /*处理下标非法的情况 */
off= i1× A->c[0]+ i2× A->c[1]+ i3× A->c[2];
*(A->base + off)=e; /*赋值 */
return(1);
}
4.4 特殊矩阵本节主要研究对称矩阵、三角矩阵和带状矩阵的压缩存储。所谓压缩存储即为：多个相同值的结点只分配一个存储空间，值为零的结点不分配空间。
4.4.1 对称矩阵的压缩存储如果矩阵的行数和列数相等，则称该矩阵为方阵。若 n× n阶的方阵 A满足：
aij=aji (0≤i≤n -1,0≤j≤n -1)
则称矩阵 A为对称矩阵。在对称矩阵中，几乎有一半元素的值是对应相等的。如果将 A中所有元素进行存储，那将会造成空间的浪费，且 n值越大，浪费将越严重。
对于对称矩阵压缩存储时只需存储对角线以上或对角线以下的部分，未存储的部分可以利用元素之间的对称性来访问。
现考虑只存储对称矩阵 A对角线以下的部分（即下标满足
i≥j 的数组元素 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 当 i≥j
address(aij)=
address(a00)+(j*(j+1)/2+i)× L 当 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(i≥j) 压缩存储后的地址计算公式为：
address(aij)= address(a00)+ (i*(i+1)/2+j)× L 当 i≥j
与对称矩阵不同的是，当 i<j时,aij的值为 0，其没有对应的存储单元。
2,上三角矩阵
a00 a01 a02 …… a0(n-1)
0 a11 a12,..…,a1(n-1)
A = 0 0 a22,…… a2(n-1)
┋ ┋ ┋ ┋
0 0 0 …… a(n-1)(n-1)
对于上三角矩阵，只需考虑存储对角线以上的部分，对角线以下为 0的部分无需存储。仍采用按行优先存储方式，矩阵 A
中被存储元素 aij (i≤j) 在压缩存储方式下的地址计算公式为：
address(aij)=address(a00)+[(n+(n-1)+(n-2)+…,.+(n-
(i-1))) +j-i]× L
=address(a00)+(i*n-(i-1)*i/2+j-i)*L
而当 i>j时,aij的值为 0，其没有对应的存储空间。
4.4.3 带状矩阵的压缩存储对于 n× n阶方阵，若它的全部非零元素落在一个以主对角线为中心的带状区域中，这个带状区域包含主对角线下面及上面各 b条对角线上的元素以及主对角线上的元素，那么称该方阵为半带宽为 b的带状矩阵。带状矩阵的特点是：对于矩阵元素 aij，若
i-j>b或 j-i>b，即 |i-j|>b，则 aij=0。
b条对角线
b条对角线 主对角线带状矩阵进行压缩存储时，只存储带状部分内部的元素，对于带状区域以外的元素，即 |i-j|>b的 aij，
均不分配存储空间。为了方便起见，我们规定按如下方法进行存储：除第一行和最后一行外，每行都分配
2b+1个元素的空间，将带状区域中的元素存储于
（ (2b+1)× n-2b） × L个存储单元之中，其中 L为每个元素占用空间的大小。仍考虑采用按行优先的存储方式，于是可以得到带状区域中任何一个元素 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 稀疏矩阵如果一个矩阵中很多元素的值为零，即零元素的个数远远大于非零元素的个数时，称该矩阵为 稀疏矩阵 。
4.5.1 稀疏矩阵类的定义
ADT spmatrix {
数据对象 D：具有相同类型的数据元素构成的有限集合；
数据关系 R,D中的每个元素均位于 2个向量中，每个元素最多具有 2个前驱结点和 2个后继结点，
且 D中零元素的个数远远大于非零元素的个数；
稀疏矩阵的基本运算如下：
（ 1） Createspmatrix (A)
（ 2） compressmatrix(A,B)
（ 3） Destroyspmatrix(A)
（ 4） Printspmatrix(A)
（ 5） Copyspmatrix(A,B)
（ 6） Addspmatrix(A,B,C)
（ 7） Subspmatrix(A,B,C)
（ 8） Multspmatrix(A,B,C)
（ 9） Transpmatrix(B,C)
（ 10） locatespmatrix(A,x,rowx,colx)
} ADT spmatrix
4.5.2 稀疏矩阵的顺序存储及其实现稀疏矩阵的顺序存储方法包括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示法，其中以三元组表示法最常用，故在此主要介绍稀疏矩阵的三元组表示。
在三元组表示法中，稀疏矩阵的每个非零元素可以采用如下形式表示：
( i,j,value )
其中 i表示非零元素所在的行号,j表示非零元素所在的列号，
value表示非零元素的值。采用三元组表示法表示一个稀疏矩阵时，首先将它的每一个非零元素表示成上述的三元组形式，然后按行号递增的次序、同一行的非零元素按列号递增的次序将所有非零元素的三元组表示存放到一片连续的存储单元中即可。
以下是稀疏矩阵 A7× 6及其对应的三元组表示。
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 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的三元组表示稀疏矩阵 A及其对应的三元组表示矩阵 B的数据类型定义如下,
typedef struct {
int data[100][100]; /*存放稀疏矩阵的二维数组 */
int m,n; /*分别存放稀疏矩阵的行数和列数 */
} matrix;
typedef int spmatrix[100][3];
/*稀疏矩阵对应的三元组表示的类型 */
1、产生稀疏矩阵三元组表示的算法
void compressmatrix(matrix A,spmatrix B)
{ int i,j,k=1;
for ( i=0; i<A.m; i++)
for (j=0; j<A.n; j++)
if (A.data[i][j] !=0)
{ B[k][0]=i;
B[k][1]=j;
B[k][2]=A.data[i][j];
k++;
}
B[0][0]=A.m; B[0][1]=A.n;
B[0][2]=k-1;
}
2、求稀疏矩阵的转置算法 transpmatrix(B,C)
按照矩阵转置的定义，要实现矩阵的转置，只要将矩阵中以主对角线为对称轴的元素 aij和 aji的值互换。但三元组的排列要求采用按行优先方式，如果只是简单地将非零元素的行号和列号交换，则新产生的三元组表示将不再满足按行优先的原则。
解决的办法是：首先确定 B中每一列非零元素的个数，也即将来 C中每一行非零元素的个数，从而可计算出 C中每一行非零元素三元组的起始位置，这样便可实现将 B中的非零元素交换行号和列号后逐一放到它们在 C中的最终位置上了。为了求 B中每一列非零元素的个数和 C中每一行非零元素三元组的起始位置，
可以设置两个数组 x和 y来实现相应的功能。
void transpmatrix (spmatrix B,spmatrix C)
{ int i,j,t,m,n;
int x[100]; /*用来存放 B中每一列非零元素的个数 */
int y[100]; /*存放 C中每一行非零元素三元组的起始位置 */
m=B[0][0]; n=B[0][1]; t=B[0][2];
C[0][0]=n; C[0][1]=m; C[0][2]=t;
if (t>0)
{
for (i=0; i<n; i++) x[i]=0;
for (i=1; i<=t; i++) x[B[i][1]]=x[B[i][1]]+1;
/*统计 B中每一列非零元素的个数 */
/*求矩阵 C中每一行非零元素三元组的起始位置 */
y[0]=1;
for (i=1; i<n; i++) y[i]=y[i-1]+x[i-1];
for (i=1; i<=t; i++)
{ /*将 B中非零元素交换行号、列号后写入 C中其最终的位置上 */
j=y[B[i][1]];
C[j][0]= B[i][1];
C[j][1]= B[i][0];
C[j][2]= B[i][2];
y[B[i][1]]=j+1;
}
}
}
4.5.3 稀疏矩阵的链式存储及实现十字链表的表示法是稀疏矩阵的链式存储方法之一，其基本思想为：将稀疏矩阵同一行的所有非零元素串成一个带表头的环形链表，同一列的所有非零元素也串成一个带表头的环形链表，且第 i行非零元素链表的表头和第 i列非零元素链表的表头共用一个表头结点，同时所有表头结点也构成一个带表头的环形链表。因此，在十字链表的表示中有两类结点，非零元素结点和表头结点。非零元素结点的结构：
row col val
right down
为了程序实现方便，我们将表头结点的结构定义成与非零元素结点的结构相同，只是将其行域和列域的值置为 0；另外，由于所有的表头结点也要串成一个带表头的环形链表，且表头结点本身没有数据值，因此可将非零元素结点中的 val域改为指向本表头结点的下一个表头结点的指针域 next，即 val域和 next域共用一片存储空间，于是得到表头结点的结构如下：
row col next
right down
具体实例见书第 99页。
稀疏矩阵十字链表表示中结点的类型定义如下,
typedef struct matrixnode
/*十字链表中结点的结构 */
{
int row,col;
struct matrixnode *right,* down;
union{ int val;
struct matrixnode *next;
} tag;
} matrixnode;
typedef matrixnode *spmatrix;
typedef spmatrix headspmatrix[100];
1、稀疏矩阵十字链表的创建算法
void Createspmatrix (headspmatrix h)
{ int m,n,t,s,i,r,c,v; spmatrix p,q;
printf(“矩阵的行数、列数和非零元素的个数：,);
scanf(“%d%d%d”,&m,&n,&t);
p=(spmatrix) malloc (sizeof(matrixnode));
h[0]=p; /* h[0]为表头环形链表的表头结点 */
p->row=m; p->col=n;
s=m>n?m:n;
for (i=1;i<=s;++i)
{ p=(spmatrix) malloc (sizeof(matrixnode));
h[i]=p; h[i-1]->tag.next=p;
p->row=p->col=0; p->down=p->right=p;
}
h[s]->tag.next=h[0];
for (i=1;i<=t;++i)
{ printf("输入非零元素的行号、列号和值,");
scanf("%d%d%d",&r,&c,&v);
p=(spmatrix) malloc (sizeof(matrixnode));
p->row=r; p->col=c; p->tag.val=v;
q=h[r];
while (q->right!=h[r] && q->right->col<c)
q=q->right;
p->right=q->right;
q->right=p;
q=h[c]; /*将非零元素插入到其所在列的环形链表 */
while (q->down!=h[c] && q->down->row<r)
q=q->down;
p->down=q->down;
q->down=p;
}
}
2、稀疏矩阵十字链表的查找算法
int locatespmatrix(headspmatrix h,int x,int *rowx,
int *colx)
{ spmatrix p,q;
p=h[0]->tag.next;
while (p!=h[0])
{ q=p->right;
while (p!=q)
{if (q->tag.val==x)
{*rowx=q->row; *colx=q->col; return(1);}
q=q->right;
}
p=p->tag.next; /*准备进入下一行查找 */
}
return(0);
}
字符串
字符串的模式匹配
稀疏矩阵
数组
特殊矩阵
4,1 字符串
4.1.1 字符串的基本概念字符串是由零个或多个字符构成的有限序列，
一般可表示成如下形式：
,c1 c2 c3…,cn” (n≥ 0)
串中所含字符的个数 n称为字符串的长度；当 n=0时，
称字符串为 空串 。
串中任意个连续的字符构成的子序列称为该串的 子串,包含子串的串称 为 主串 。通常称字符在字符串序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。例如,T =“STUDENT”,S=“UDEN”,则 S
是 T的子串,S在 T中出现的位置为 3。
两个 字符串相等,当且仅当两个串的长度相等，
并且各个对应位置的字符都相等。例如：
T1=“REDROSE” T2=“RED ROSE”
由于 T1和 T2的长度不相等，因此 T1≠T2 。
若
T3=“STUDENT” T4=“STUDENS”
虽然 T3和 T4的长度相等，但两者有些对应的字符不同，因而 T3≠T4 。
值得一提的是，若 S=― ‖，此时 S由一个空格字符组成，其长度为 1，它不等价于空串，因为空串的长度为 0。
4.1.2 字符串类的定义
ADT string {
数据对象 D：由零个或多个字符型的数据元素构成的有限集合；
数据关系 R,{<ai,ai+1>|其中 ai,ai+1?D,
i=1,2,…… n-1 }
字符串的基本操作如下：
（ 1） Strcreate (S)
（ 2） Strassign(S,T)
（ 3） Strlength(S)
（ 4） Strempty(S)
（ 5） Strclear(S)
（ 6） Strcompare(S1,S2)
（ 7） Strconcat(S1,S2)
（ 8） Substring(S,i,len)
（ 9） Index(P,T)
（ 10） Strinsert(S,i,T)
（ 11） Strdelete(S,i,len)
（ 12） Replace(S,T1,T2)
（ 13） Strdestroy(S)
} ADT string
4.1.3 字符串的存储及其实现
1、串的顺序存储及其部分运算的实现串的顺序存储使用数组存放，具体类型定义如下：
#define MAXSIZE 100
typedef struct {
char str[MAXSIZE];
int length ;
} seqstring;
（ 1）插入运算 strinsert(S,i,T)
void strinsert(seqstring *S,int i,seqstring T)
{ int k;
if (i<1 || i>S->length+1 || S->length + T.length>MAXSIZE)
printf("connot insert\n“);
else
{
for(k=S->length-1;k>=i-1;k--)
S->str[T.length+k]=S->str[k];
for (k=0;k<T.length;k++)
S->str[i+k-1]=T.str[k];
S->length= S->length + T.length;
S->str[S->length]=?\0?;
}
}
（ 2）删除运算 strdelete(S,i,len)
void strdelete(seqstring *S,int i,int len)
{ int k ;
if (i<1 || i>S->length||i+len-1>S->length)
printf(,cannot delete\n”);
else
{
for(k=i+len-1; k<S->length;k++)
S->str[k-len]= S->str[k];
S->length=S->length-len;
S->str[S->length]=?\0?;
}
}
（ 3）连接运算 strconcat(S1,S2)
seqstring * strconcat(seqstring S1,seqstring S2)
{ int i; seqstring *r;
if (S1.length+S2.length>MAXSIZE)
{ printf("cannot concate"); return(NULL);}
else
{ r=(seqstring*)malloc (sizeof(seqstring));
for (i=0; i<S1.length;i++) r->str[i]= S1.str[i];
for (i=0; i<S2.length;i++)
r->str[ S1.length+i]= S2.str[i];
r->length= S1.length+ S2.length;
r->str[r->length]='\0';
}
return (r);
}
（ 4）求子串运算 substring(S,i,len)
seqstring *substring(seqstring S,int i,int len)
{ int k; seqstring *r;
if (i<1 || i>S.length || i+len-1>S.length)
{ printf(“error\n”); return(NULL);}
else
{ r=(seqstring*) malloc (sizeof(seqstring));
for(k=0;k<len;k++) r->str[k]= S.str[i+k-1];
r->length=len;
r->str[r->length]='\0';
}
return(r);
}
2 串的链接存储及其部分运算的实现串的链接存储采用单链表的形式实现，其中每个结点的定义如下：
typedef struct node
{
char data;
struct node *next;
} linkstrnode;
typedef linkstrnode *linkstring;
例如，串 S=―abcde‖，其链接存储结构如下图所示：
a b c d e ∧
S
（ 1）创建字符串运算 strcreate (S)
void strcreate (linkstring *S)
{ char ch; linkstrnode *p,*r;
*S=NULL; r=NULL;
while ((ch=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;
p=*S,k=1;
while (p && k<i-1)
{ p=p->next ; k++; }
if (!p) printf("error\n");
else
{ q=T;
while(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 && k<i)
{q=p; p=p->next ; k++;}
if (!p) printf("error1\n");
else
{ k=1;
/*p从第 i个元素开始查找长度为 len子串的最后元素 */
while(k<len && p )
{ p=p->next ;k++;}
if(!p) printf("error2\n");
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; return;}
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 && k<i) {p= p->next;k++;}
if (!p) {printf("error1\n"); return(null);}
else
{
r=(linkstring) malloc (sizeof(linkstrnode));
r->data=p->data; r->next=null;
k=1; q=r; /*用 q始终指向子串的最后一个字符的位置 */
while (p->next && k<len) /*取长度为 len的子串 */
{
p=p->next ;k++;
t=(linkstring) malloc (sizeof (linkstrnode));
t->data=p->data;
q->next=t; q=t;
}
if (k<len) {printf("error2\n") ; return(null);}
else
{q->next=null; return(r);} /*处理子串的尾部 */
}
}
4.2 字符串的模式匹配寻找字符串 p在字符串 t中首次出现的起始位置称为字符串的 模式匹配,其中称 p为 模式 (pattern）,t
为 正文 (text),t的长度远远大于 p的长度。
4.2.1 朴素的模式匹配算法朴素模式匹配算法的基本思想是：用 p中的每个字符去与 t中的字符一一比较：
正文 t,t1 t2 …… tm…… tn
模式 p,p1 p2 …… pm
如果 t1=p1,t2=p2,…,.tm=pm，则模式匹配成功；否则将 p向右移动一个字符的位置，重新用 p中的字符从头开始与 t中相对应的字符依次比较，即：
t1 t2 t3 …… tm tm+1…… tn
p1 p2…… pm-1 pm
如此反复，直到匹配成功或者 p已经移到使 t中剩下的字符个数小于 p的长度的位置，此时意味着模式匹配失败，表示 t中没有子串与模式 p相等，我们约定返回 -1代表匹配失败。
朴素模式匹配算法的具体实现如下：
int index(seqstring p,seqstring t)
{ int i,j,succ;
i=0; succ=0; /* succ为匹配成功的标志 */
while((i<=t.length-p.length+1) && (!succ))
{ j=0 ; succ=1; /*用 j扫描模式 p*/
while ((j<=p.length-1) && succ)
if (p.str[j]==t.str[i+j] ) j++;
else succ=0;
++i;
}
if (succ) return (i-1);
else return (-1);
}
4.2.2 快速模式匹配算法（ KMP算法）
首先我们来分析下图所示的情况：
t0 t1 t2 …… tk tk+1 tk+2…… tr-2 tr-1 tr……,
‖ ‖ ‖ ‖ ‖ ╫
p0 p1 p2…… pi-2 pi-1 pi………,
（ 4-1）
t0 t1 t2 …… tk tk+1 tk+2…… tr-2 tr-1 tr……,
‖ ‖ ‖ ‖
p0 p1 …… pi-2 pi-1
pi………
（ 4-2）
t0 t1 t2 …… tk tk+1 tk+2…… tr-2 tr-1 tr……,
‖ ‖ ‖
p0 ……… pi-3 pi-2 pi-1 pi……
（ 4-3）
(4-1)式表明此次匹配从 p0与 tk开始比较，当比较到 pi与 tr时出现不等情况，于是将模式右移一位，变成 (4-2)所示的状态，若此次比较成功，则必有 p0= tk+1,p1= tk+2,…… pi-2=
tr-1，且 pi-1≠p i；而根据 (4-1)的比较结果有,p1= tk+1,p2=
tk+2,…… pi-1= tr-1，因此有,p0= p1,p1= p2,…… pi-2=
pi-1。这个性质说明在模式 p中 pi之前存在一个从 p0开始长度为 i-1的连续序列 p0 p1 …… pi-2 和以 pi-1为结尾，长度同样为 i-1的连续序列 p1 p2…… pi-1其值对应相等，即：
p0 p1 p2…… pi-2 pi-1 pi………,
简记为：
[p0—pi-2]=[p1—pi-1]
称模式 p中 pi之前存在 长度为 i-1的真前缀和真后缀的匹配 。
反之，若在 (4-1)所示的状态下，模式 p中 pi之前存在长度为 i-1的真前缀和真后缀的匹配，即 [p0—pi-
2]=[p1—pi-1] 且 pi-1≠p i；当 pi与 tr出现不等时，根据前面已比较的结果 p1= tk+1,p2= tk+2,…… pi-1= tr-1，
于是可得 p0= tk+1,p1= tk+2,…… pi-2= tr-1，因此接下来只需从 pi-1与 tr开始继续后继对应字符的比较即可。
再假设在 (4-1)所示的状态下，模式右移一位成为状态 (4-2)后，匹配仍然不成功，说明 [p0—pi-2]
[p1—pi-1]或 pi-1=pi，于是模式再右移一位，成为状态 (4-3)，若此次匹配成功，仿照上述分析，必有：
p0 p1 p2…… pi-3 pi-2 pi-1 pi………,
即：
[p0—pi-3]=[p2—pi-1]
说明模式 p中 pi之前存在长度为 i-2的真前缀和真后缀的匹配。由 (4-3)表明，在 (4-1)所示的状态下，
若模式 p中 pi之前最长真前缀和真后缀匹配的长度为
i-2，当 pi与 tr出现不等时，接下来只需从 pi-2与 tr开始继续后继对应字符的比较。
考虑一般情况。在进行模式匹配时，若模式 p中
pi之前最长真前缀和真后缀匹配的长度为 j，当
pi?tr时，则下一步只需从 pj与 tr开始继续后继对应字符的比较,而不应该将模式一位一位地右移，也不应该反复从模式的开头进行比较。这样既不会失去任何匹配成功的机会，又极大地加快了匹配的速度。
根据上述分析，在模式匹配过程中，每当出现 pi?tr时，
下一次与 tr进行比较的 pj和模式 p中 pi之前最长真前缀和真后缀匹配的长度密切相关；而模式 p中 pi之前最长真前缀和真后缀匹配的长度只取决于模式 p的组成，与正文无关。
于是我们可以针对模式 p定义一个数组 next[m]，其中
next[i]表示当 pi?tr时，下一次将从 pnext[i]与 tr开始继续后继对应字符的比较。显然,next[i]的值与模式 p中 pi之前最长真前缀和真后缀匹配的长度密切相关。下面考虑如何根据模式 p的组成求数组 next的值。我们规定：
next[0]=-1
这表明当 p0?tr时，将从 p-1与 tr开始继续后继对应字符的比较；
然而 p-1是不存在的，我们可以将这种情况理解成下一步将从
p0与 tr+1开始继续后继对应字符的比较。
以下假设 next[0],next[1],……,next[i]的值均已求出，现要求 next[i+1]的值。由于在求解 next[i]时已得到
pi之前最长真前缀和真后缀匹配的长度，设其值为 j，即：
p0 p1 p2…… pi-j ……,pj-1 pj…… pi-2 pi-1 pi pi+1……
如果此时进一步有 pj=pi，则 pi+1之前最长真前缀和真后缀匹配的长度就为 j+1，且 next[i+1]=j+1;反之，若 pj?pi，注意到，求 pi+1之前最长真前缀和真后缀匹配问题本质上仍然是一个模式匹配问题，只是在这里模式和正文都是同一个串
p而已。因此当 pj?pi时，应该检查 pnext[j]与 pi是否相等；若相等，则 next[i+1]=next[j]+1；如仍然不相等，则再取
pnext[next[j]]与 pi进行比较,…… 直至要将 p-1与 pi进行比较为止，此时 next[i+1]=0。
以下给出了根据模式 p的组成求数组 next值的算法：
void getnext(seqstring p,int next[])
{ int i,j;
next[0]=-1;
i=0; j=-1;
while (i<p.length)
{
if (j==-1||p.str[i]==p.str[j])
{++i;++j;next[i]=j;}
else
j=next[j];
}
for(i=0;i<p.length;i++)
printf("%d",next[i]);
}
KMP算法基本思想如下：
假设以 i和 j分别指示正文 t和模式 p中正待比较的字符，令 i,j的初值为 0；若在匹配过程中 ti=pj，则 i
与 j分别加 1；否则 i不变，而 j退到 next[j]的位置继续比较（即 j= next[j]）；若相等，则指针各自增加
1；否则 j再退到下一个 next[j]值的位置，依此类推，
直至下列两种可能,
(1)一种是 j退到某个 next（ next[..[next[j]]… ]））
时,ti与 pj字符比较相等，则 i,j指针各自增加 1
后继续进行比较；
(2)一种是 j退到 -1（即模式的第一个字符,失配,），
此时需将正文指针 i向右滑动一个位置，即从正文的下一个字符 ti+1起和模式 p重新从头开始比较。
KMP算法的具体实现如下：
int kmp(seqstring t,seqstring p,int next[])
{ int i,j;
i=0; j=0;
while (i<t.length && j<p.length)
{
if (j==-1||t.str[i]==p.str[j])
{i++; j++;}
else j=next[j];
}
if (j==p.length) return (i-p.length);
else return(-1);
}
4.3 数 组
4.3.1 数组和数组元素数组是线性表的一种存储方式。其实，数组本身也可以看成是线性表的推广，数组的每个元素由一个值和一组下标确定，在数组中，对于每组有定义的下标都存在一个与之相对应的值；而线性表是有限结点的有序集合，若将其每个结点的序号看成下标，线性表就是一维数组（向量）；当数组为多维数组时，其对应线性表中的每个元素又是一个数据结构而已。
例如，对于一个 m?n的二维数组 A[m][n]：
a00 a01 a02……… a0( n-1)
a10 a11 a12……… a1( n-1)
A = ┋ ┋ ┋ ┋
┋ ┋ ┋ ┋
a(m-1)0 a(m-1)1……… a(m-1)(n-1)
当把二维数组看成是线性表时，它的每一个结点又是一个向量（一维数组）。例如，上述二维数组 A可以看成是如下的线性表：
(A0,A1,A2,…… Am-1)
即 A中每一行成为线性表的一个元素，其中每个元素
Ai(0≤i≤m -1)都是一个向量；
（ ai0,ai1,ai2……,ai(n-1) ）
当然，也可以将上述二维数组 A看成如下的线性表：
(A0?,A1?,A2?,…… An-1?)
即 A中每一列成为线性表的一个元素，其中每一个元素 Ai?(0≤i≤n -1)都是一个向量,
（ a0i,a1i,a2i,…… a (m-1) i）
二维数组 A中的每一个元素 aij都同时属于两个向量，即：第 i+1行的行向量和第 j+1列的列向量，
因此每个元素 aij最多有两个前驱结点 a(i-1) j和 ai(j-1)，
也最多有两个后继结点 a(i+1) j和 ai(j+1)（只要这些结点存在）；特别地,a00没有前驱结点,a(m-1) (n-1)没有后继结点，边界上的结点均只有一个后继结点或一个前驱结点。
对于 m（ m>2）维数组，可以依据上述规律类推。
4.3.2 数组类的定义
ADT array {
数据对象 D：具有相同类型的数据元素构成的有序集合；
数据关系 R：对于 n维数组，其每一个元素均位于 n个向量中，
每个元素最多具有 n个前驱结点和 n个后继结点；
数组的基本操作如下：
（ 1） Initarray (A,n,index1,index2,…… index n)
（ 2） Destroyarray(A)
（ 3） Value(A,index1,index2,…… index n,x)
（ 4） Assign (A,e,index1,index2,…… index n)
} ADT array
4.3.3 数组的顺序存储及实现由于数组是由有限的元素构成的有序集合，数组的大小和元素之间的关系一经确定，就不再发生变化，因此数组均采用顺序存储结构实现，它要求一片连续的存储空间存储。
多维数组数据元素的顺序存储有两种方式：
按行优先存储
按列优先存储例如：对于二维数组 A[m][n]：
a00 a01 …………… a0( n-1)
a10 a11 …………… a1( n-1)
A = ┋ ┋ ┋
┋ ┋ ┋
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) 。
对于数组，一旦确定了它的维数和各维的长度，
便可以为它分配存储空间；当规定了数组元素的存储次序后，便可根据给定的一组下标值求得相应数组元素的存储位置。
现假设数组中每个元素占用 L个存储单元，若考虑按行优先存储方式，则上述 A数组中任何一个元素
aij的存储位置可以按以下公式确定：
address（ aij ） = address ( a00 ) + ( i× n+j )× L
若考虑按列优先的存储方式，数组中任何一个元素 aij存储位置的地址计算公式为：
address( aij ) = address ( a00 ) + (j× m +i )× L
多维数组的存储也和二维数组一样，存在两种存储方式：
按行优先和按列优先。但由于多维数组中数据元素间的关系较二维数组复杂，因此数据元素的地址计算公式也相对复杂些，但两者所采用的原理是相同的。
考虑 n维数组的情形：
datatype A[b1][b2]…… [bn]；
其中 b1,b2,…… bn为数组每一维的长度。仍假设每个元素占用 L个单元，则 n维数组 A中任何一个元素 A[j1][j2]…… [jn]在按行优先存储方式下的地址计算公式为：
address(A[j1][j2]…… [jn])=address(A[0][0]… [0])+
(b2× b3× …… bn× j1+ b3× b4× …… bn× j2+ …… bn× jn-1+
jn)× L
上式可以简写为：
address((A[j1][j2]…… [jn])=address(A[0][0]… [0])+
c1*j1+c2*j2+…… cn*jn
其中 cn=L,ci-1=bi× ci,1<i≤n 。
以下以三维数组为例，给出三维数组的顺序存储表示及其部分运算的实现。
typedef int datatype;
/*假设数组元素的值为整型 */
typedef struct {
datatype *base; /* 数组存储区的首地址指针 */
int index[3]; /* 存放三维数组各维的长度 */
int c[3] /* 存放三维数组各维的 ci值 */
} array；
1,数组初始化运算 initarray (A,b1,b2,b3)
int initarray (array *A,int b1,int b2,int b3)
{
int elements;
if (b1<=0||b2<=0||b3<=0) return( 0 );
A->index[0]=b1; A->index[1]=b2; A->index[2]=b3;
elements = b1 × b2 × b3;
A->base=(datatype*)malloc(elements× sizeof(datatype));
if (! (A->base)) return(0);
A->c[0]= b2 × b3; A->c[1]= b3; A->c[2]= 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<0 || i1>=A.index[0] || i2< 0 || i2>=A.index[1] ||
i3<0 || i3>=A.index[2])
return(0); /*处理下标非法的情况 */
off= i1× A.c[0]+ i2× A.c[1]+ i3× A.c[2];
*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<0 || i1>=A->index[0] || i2< 0 || i2>=A->index[1]
|| i3<0 || i3>=A->index[2])
return (0 ); /*处理下标非法的情况 */
off= i1× A->c[0]+ i2× A->c[1]+ i3× A->c[2];
*(A->base + off)=e; /*赋值 */
return(1);
}
4.4 特殊矩阵本节主要研究对称矩阵、三角矩阵和带状矩阵的压缩存储。所谓压缩存储即为：多个相同值的结点只分配一个存储空间，值为零的结点不分配空间。
4.4.1 对称矩阵的压缩存储如果矩阵的行数和列数相等，则称该矩阵为方阵。若 n× n阶的方阵 A满足：
aij=aji (0≤i≤n -1,0≤j≤n -1)
则称矩阵 A为对称矩阵。在对称矩阵中，几乎有一半元素的值是对应相等的。如果将 A中所有元素进行存储，那将会造成空间的浪费，且 n值越大，浪费将越严重。
对于对称矩阵压缩存储时只需存储对角线以上或对角线以下的部分，未存储的部分可以利用元素之间的对称性来访问。
现考虑只存储对称矩阵 A对角线以下的部分（即下标满足
i≥j 的数组元素 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 当 i≥j
address(aij)=
address(a00)+(j*(j+1)/2+i)× L 当 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(i≥j) 压缩存储后的地址计算公式为：
address(aij)= address(a00)+ (i*(i+1)/2+j)× L 当 i≥j
与对称矩阵不同的是，当 i<j时,aij的值为 0，其没有对应的存储单元。
2,上三角矩阵
a00 a01 a02 …… a0(n-1)
0 a11 a12,..…,a1(n-1)
A = 0 0 a22,…… a2(n-1)
┋ ┋ ┋ ┋
0 0 0 …… a(n-1)(n-1)
对于上三角矩阵，只需考虑存储对角线以上的部分，对角线以下为 0的部分无需存储。仍采用按行优先存储方式，矩阵 A
中被存储元素 aij (i≤j) 在压缩存储方式下的地址计算公式为：
address(aij)=address(a00)+[(n+(n-1)+(n-2)+…,.+(n-
(i-1))) +j-i]× L
=address(a00)+(i*n-(i-1)*i/2+j-i)*L
而当 i>j时,aij的值为 0，其没有对应的存储空间。
4.4.3 带状矩阵的压缩存储对于 n× n阶方阵，若它的全部非零元素落在一个以主对角线为中心的带状区域中，这个带状区域包含主对角线下面及上面各 b条对角线上的元素以及主对角线上的元素，那么称该方阵为半带宽为 b的带状矩阵。带状矩阵的特点是：对于矩阵元素 aij，若
i-j>b或 j-i>b，即 |i-j|>b，则 aij=0。
b条对角线
b条对角线 主对角线带状矩阵进行压缩存储时，只存储带状部分内部的元素，对于带状区域以外的元素，即 |i-j|>b的 aij，
均不分配存储空间。为了方便起见，我们规定按如下方法进行存储：除第一行和最后一行外，每行都分配
2b+1个元素的空间，将带状区域中的元素存储于
（ (2b+1)× n-2b） × L个存储单元之中，其中 L为每个元素占用空间的大小。仍考虑采用按行优先的存储方式，于是可以得到带状区域中任何一个元素 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 稀疏矩阵如果一个矩阵中很多元素的值为零，即零元素的个数远远大于非零元素的个数时，称该矩阵为 稀疏矩阵 。
4.5.1 稀疏矩阵类的定义
ADT spmatrix {
数据对象 D：具有相同类型的数据元素构成的有限集合；
数据关系 R,D中的每个元素均位于 2个向量中，每个元素最多具有 2个前驱结点和 2个后继结点，
且 D中零元素的个数远远大于非零元素的个数；
稀疏矩阵的基本运算如下：
（ 1） Createspmatrix (A)
（ 2） compressmatrix(A,B)
（ 3） Destroyspmatrix(A)
（ 4） Printspmatrix(A)
（ 5） Copyspmatrix(A,B)
（ 6） Addspmatrix(A,B,C)
（ 7） Subspmatrix(A,B,C)
（ 8） Multspmatrix(A,B,C)
（ 9） Transpmatrix(B,C)
（ 10） locatespmatrix(A,x,rowx,colx)
} ADT spmatrix
4.5.2 稀疏矩阵的顺序存储及其实现稀疏矩阵的顺序存储方法包括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示法，其中以三元组表示法最常用，故在此主要介绍稀疏矩阵的三元组表示。
在三元组表示法中，稀疏矩阵的每个非零元素可以采用如下形式表示：
( i,j,value )
其中 i表示非零元素所在的行号,j表示非零元素所在的列号，
value表示非零元素的值。采用三元组表示法表示一个稀疏矩阵时，首先将它的每一个非零元素表示成上述的三元组形式，然后按行号递增的次序、同一行的非零元素按列号递增的次序将所有非零元素的三元组表示存放到一片连续的存储单元中即可。
以下是稀疏矩阵 A7× 6及其对应的三元组表示。
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 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的三元组表示稀疏矩阵 A及其对应的三元组表示矩阵 B的数据类型定义如下,
typedef struct {
int data[100][100]; /*存放稀疏矩阵的二维数组 */
int m,n; /*分别存放稀疏矩阵的行数和列数 */
} matrix;
typedef int spmatrix[100][3];
/*稀疏矩阵对应的三元组表示的类型 */
1、产生稀疏矩阵三元组表示的算法
void compressmatrix(matrix A,spmatrix B)
{ int i,j,k=1;
for ( i=0; i<A.m; i++)
for (j=0; j<A.n; j++)
if (A.data[i][j] !=0)
{ B[k][0]=i;
B[k][1]=j;
B[k][2]=A.data[i][j];
k++;
}
B[0][0]=A.m; B[0][1]=A.n;
B[0][2]=k-1;
}
2、求稀疏矩阵的转置算法 transpmatrix(B,C)
按照矩阵转置的定义，要实现矩阵的转置，只要将矩阵中以主对角线为对称轴的元素 aij和 aji的值互换。但三元组的排列要求采用按行优先方式，如果只是简单地将非零元素的行号和列号交换，则新产生的三元组表示将不再满足按行优先的原则。
解决的办法是：首先确定 B中每一列非零元素的个数，也即将来 C中每一行非零元素的个数，从而可计算出 C中每一行非零元素三元组的起始位置，这样便可实现将 B中的非零元素交换行号和列号后逐一放到它们在 C中的最终位置上了。为了求 B中每一列非零元素的个数和 C中每一行非零元素三元组的起始位置，
可以设置两个数组 x和 y来实现相应的功能。
void transpmatrix (spmatrix B,spmatrix C)
{ int i,j,t,m,n;
int x[100]; /*用来存放 B中每一列非零元素的个数 */
int y[100]; /*存放 C中每一行非零元素三元组的起始位置 */
m=B[0][0]; n=B[0][1]; t=B[0][2];
C[0][0]=n; C[0][1]=m; C[0][2]=t;
if (t>0)
{
for (i=0; i<n; i++) x[i]=0;
for (i=1; i<=t; i++) x[B[i][1]]=x[B[i][1]]+1;
/*统计 B中每一列非零元素的个数 */
/*求矩阵 C中每一行非零元素三元组的起始位置 */
y[0]=1;
for (i=1; i<n; i++) y[i]=y[i-1]+x[i-1];
for (i=1; i<=t; i++)
{ /*将 B中非零元素交换行号、列号后写入 C中其最终的位置上 */
j=y[B[i][1]];
C[j][0]= B[i][1];
C[j][1]= B[i][0];
C[j][2]= B[i][2];
y[B[i][1]]=j+1;
}
}
}
4.5.3 稀疏矩阵的链式存储及实现十字链表的表示法是稀疏矩阵的链式存储方法之一，其基本思想为：将稀疏矩阵同一行的所有非零元素串成一个带表头的环形链表，同一列的所有非零元素也串成一个带表头的环形链表，且第 i行非零元素链表的表头和第 i列非零元素链表的表头共用一个表头结点，同时所有表头结点也构成一个带表头的环形链表。因此，在十字链表的表示中有两类结点，非零元素结点和表头结点。非零元素结点的结构：
row col val
right down
为了程序实现方便，我们将表头结点的结构定义成与非零元素结点的结构相同，只是将其行域和列域的值置为 0；另外，由于所有的表头结点也要串成一个带表头的环形链表，且表头结点本身没有数据值，因此可将非零元素结点中的 val域改为指向本表头结点的下一个表头结点的指针域 next，即 val域和 next域共用一片存储空间，于是得到表头结点的结构如下：
row col next
right down
具体实例见书第 99页。
稀疏矩阵十字链表表示中结点的类型定义如下,
typedef struct matrixnode
/*十字链表中结点的结构 */
{
int row,col;
struct matrixnode *right,* down;
union{ int val;
struct matrixnode *next;
} tag;
} matrixnode;
typedef matrixnode *spmatrix;
typedef spmatrix headspmatrix[100];
1、稀疏矩阵十字链表的创建算法
void Createspmatrix (headspmatrix h)
{ int m,n,t,s,i,r,c,v; spmatrix p,q;
printf(“矩阵的行数、列数和非零元素的个数：,);
scanf(“%d%d%d”,&m,&n,&t);
p=(spmatrix) malloc (sizeof(matrixnode));
h[0]=p; /* h[0]为表头环形链表的表头结点 */
p->row=m; p->col=n;
s=m>n?m:n;
for (i=1;i<=s;++i)
{ p=(spmatrix) malloc (sizeof(matrixnode));
h[i]=p; h[i-1]->tag.next=p;
p->row=p->col=0; p->down=p->right=p;
}
h[s]->tag.next=h[0];
for (i=1;i<=t;++i)
{ printf("输入非零元素的行号、列号和值,");
scanf("%d%d%d",&r,&c,&v);
p=(spmatrix) malloc (sizeof(matrixnode));
p->row=r; p->col=c; p->tag.val=v;
q=h[r];
while (q->right!=h[r] && q->right->col<c)
q=q->right;
p->right=q->right;
q->right=p;
q=h[c]; /*将非零元素插入到其所在列的环形链表 */
while (q->down!=h[c] && q->down->row<r)
q=q->down;
p->down=q->down;
q->down=p;
}
}
2、稀疏矩阵十字链表的查找算法
int locatespmatrix(headspmatrix h,int x,int *rowx,
int *colx)
{ spmatrix p,q;
p=h[0]->tag.next;
while (p!=h[0])
{ q=p->right;
while (p!=q)
{if (q->tag.val==x)
{*rowx=q->row; *colx=q->col; return(1);}
q=q->right;
}
p=p->tag.next; /*准备进入下一行查找 */
}
return(0);
}
