第 4章 串和数组本章主要介绍下列内容：
串的定义、存储结构和基本运算
数组的定义、基本运算和存储结构
特殊矩阵的压缩存储退出
4.1 串
4.2 数组
4.1 串
4.1.1 串的定义和基本运算串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串,串 是一个有穷字符序列。
串一般记作：
s=,a1a2...an” (n?0)
其中,s是串的名称，用双引号（“”）括起来的字符序列是串的值； ai可以是字母、数字或其他字符；
串中字符的数目 n被称作串的 长度 。当 n=0时，串中没有任何字符，其串的长度为 0，通常被称为 空串 。
s1=,”
s2=,,
s1中没有字符，是一个空串；而 s2中有两个空格字符，它的长度等于 2，它是由空格字符组成的串，一般称此为 空格串 。
概念：
子串,主串,串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。
例如，有下列四个串 a,b,c,d：
a=,Welcome to Beijing”
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,s2start,len)
（ 6） 串的定位 Index(s1,s2)
例如 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个字符开始的连续 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 unsigned char String[MAX_STRING];
第二种是在程序执行过程中，利用标准函数
malloc和 free动态地分配或释放存储字符串的存储单元，
并以一个特殊的字符作为字符串的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源的利用率。类型定义如下所示：
typedef struct{
char *str;
int length;
}STRING;
不同的定义形式，算法中的处理也略有不同。下面我们将给出在第二种顺序存储方式下串的几个基本操作的算法。
（ 1） 串的赋值
int StringAssign(STRING*s,char *string_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-
>str[0]=’\0’; s->length=0; } //空串
else {
s->str=(char*)malloc((len+1)*sizeof(char));
//分配空间
if (!s->str) return ERROR;
s->str[0..len]=string_constant[0..len];
//对应的字符赋值
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(&s,s1->str);
//将 s1原来的内容保留在 s中
len=Length(s1)+Length(s2);
//计算 s1和 s2的长度之和
free(s1->str);
//释放 s1原来占据的空间
s1->str=(char*)malloc((len+1)*sizeof(char));
//重新为 s1分配空间
if (!s1) return ERROR;
else { //连接两个串的内容
s1->str[0..Length(s)-1]=s.str[0..Length(s)-1)];
s1->str[Length(s)..len+1]=s2.str[0..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 (start<1||start>len2||len2<=0||len>len2-start+1) {
//判断 start和 len的合理性
s1->str=(char*)malloc(sizoef(char));s1->str[0]=’\0’;s1-
>length=0;return ERROR;}
s1->str=(char*)malloc((len+1)*sizeof(char));
if (!s1.str) return ERROR;
s1->str[0..len-1]=s2.str[start-1..start+len -2];
s1->str[len]=’\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 (i<len1&&j<len2) {
if (s1.str[i]==s2.str[j]) { i++; j++; }
else {i=i-j+1; j=0;} //对应字符不相等时，重新比较
}
if (j==len2) return i-len2+1;
else return 0;
}
2,链式存储结构由于串结构中每个数据元素为一个字符，所以最直接的链式存储结构是每个结点的数据域存放一个字符。举例：
s t r i n g ^S
图 4-1
优点是操作方便；不足之处是存储密度较低。所谓存储密度为：
实际分配的存储密度串值所占的存储单元存储密度?
若要将多个字符存放在一个结点中，就可以缓解这个问题。举例：
S s t r i n g # # # # ^
图 4-2
由于串中的字符个数不一定是每个结点存放字符个数的整倍数，所以，需要在最后一个结点的空缺位置上填充特殊的字符。
这种存储形式优点是存储密度高于结点大小为 1 的存储形式；不足之处是做插入、删除字符的操作时，
可能会引起结点之间字符的移动，算法实现起来比较复杂。
4.2 数组
4.2.1 数组的定义和基本运算数组的特点是每个数据元素可以又是一个线性表结构。因此，数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，
即为 向量 ；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。
结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。举例：
1,11,10,1
1,11110
1,00100
.,,
.,,.,,.,,.,,
.,,
.,,
nmmm
n
n
nm
aaa
aaa
aaa
A
图 4-3
其中,A是数组结构的名称，整个数组元素可以看成是由 m个行向量和 n个列向量组成，其元素总数为
m× n。在 C语言中，二维数组中的数据元素可以表示成 a[表达式 1][表达式 2]，表达式 1和表达式 2被称为下标表达式，比如,a[i][j]。
数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、
删除元素的操作。
二维数组结构的基本操作：
（ 1） 给定一组下标，修改该位置元素的内容
Assign(A,item,index1,index2)
（ 2）给定一组下标，返回该位置的元素内容
Value(A,item,index1,index2)
4.2.2 数组的存储结构从理论上讲，数组结构也可以使用两种存储结构，
即顺序存储结构和链式存储结构。然而，由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。
组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。
举例：
图 4-4
1,11,10,1
1,11110
1,00100
.,,
.,,.,,.,,.,,
.,,
.,,
nmmm
n
n
nm
aaa
aaa
aaa
A
a 00 a 01,.,a 0,n -
1
a 10 a 11,.,a 1,n -
1
...,.,a m-
1,0
a m-
1,1
..,a m - 1,n -
1
第 0行 第 1行 第 m-1行图 4-5
a 00 a 10,.,a m-
1,0
a 01 a 11,.,a m - 1,1,..,.,a 0,n - 1 a 1,n - 1,.,a m-
1,n - 1
第 0列 第 1列 第 m-1列图 4-6
LOC(i,j)=LOC(0,0)+(n*i+j)*L
数组结构的定义：
#define MAX_ROW_INDEX 10
#define MAX_COL_INDEX 10
typedef struct {
EnterType
item[MAX_ROW_INDEX][MAX_COL_INDEX] ;
} ARRAY;
基本操作算法举例：
（ 1）给数组元素赋值
void Assign(ARRAY *A,EnterType item,int index1,int
index2)
{
if (index1<0||index1>=MAX_ROW_INDEX||
index2<0||index2>=MAX_COL_INDEX) exit(ERROR);
else A->item[index1][index2]=item;
}
（ 2）返回给定位置的元素内容
int Value(ARRAY A,EntryType *item,int index1,int
index2)
{
if (index1<0||index1>=MAX_ROW_INDEX||
index2<0||index2>=MAX_COL_INDEX) return
FALSE;
else { *item= A.item[index1][index2];
return OK;
}
}
3．矩阵的压缩存储矩阵是在很多科学与工程计算中遇到的数学模型。
在数学上，矩阵是这样定义的：它是一个由 s× n个元素排成的 s行（横向） n列（纵向）的表。下面就是一个矩阵：
图 4-7 s× n的矩阵它是一个 s× n的矩阵。
mnmm
n
n
aaa
aaa
aaa
.,,
.,,.,,.,,.,,
.,,
.,,
21
22221
11211
1,特殊矩阵所谓 特殊矩 阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。
对称矩阵的特点是 aij=aji，比如，下面就是一个对称矩阵：
图 4-8
1423417
2320123
41275
173510
下（上）三角矩阵的特点是以主对角线为界的上
（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。比如，下面是一个下三角矩阵：
2092613
030108
00126
00029
图 4-9
对角矩阵的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。比如，下面就是一个 3阶对角矩阵：
1134000
692100
0177300
002059
000123
图 4-10
对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。
三种特殊矩阵的压缩方法：。
（ 1）对称矩阵对称矩阵的特点是 aij=aji。一个 n× n的方阵，共有
n2个元素，而实际上在对称矩阵中有 n(n-1)/2个元素可以通过其他元素获得。
压缩的方法是首先将二维关系映射成一维关系，
并只存储其中必要的 n(n+1)/2个（主对角线和下三角）
元素内容，这些元素的存储顺序以行为主序。举例：
假设定义一个数组型变量,int A[10];
0 1 2 3 4 5 6 7 8 910 5 7 3 12 20 17 4 23 14
图 4-11
k是对称矩阵位于（ i,j）位置的元素在一维数组中的存放位置。
ji 1
2
)1(
ji 1
2
)1(
当当
i
jj
j
ii
k
操作算法的实现：
int Value(int A[],EntryType *item,int i,int j)
{
if (i<1||i>MAX_ROW_INDEX||
j<1||j>MAX_COL_INDEX) return FALSE;
else { if (i>=j) k=i*(i-1)/2+j-1;
else k=j*(j-1)/2+i-1;
*item=A[k];
return TRUE;
}
}
（ 2）下（上）三角矩阵下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在 0单元，下三角和主对角上的元素从 1号单元开始存放。
举例：
0 1 2 3 4 5 6 7 8 9 10
0 29 6 12 8 10 30 13 26 9 20
图 4-12
ji 0
ji
2
)1(
当当j
ii
k
对于任意的（ i,j），在一维数组中的存放位置可利用下列公式求得：
操作算法的实现：
int Value(int A[],EntryType *item,int i,int j)
{
if
(i<1||i>MAX_ROW_INDEX||j<1||j>MAX_COL_INDE
X) return FALSE;
else { if (i>=j) k=i*(i-1)/2+j;
else k=0;
*item=A[k];
return TRUE;
}
}
（ 3）对角矩阵我们以三阶对角矩阵为例讨论一下它的压缩存储方法。对于对角矩阵，压缩存储的主要思路是只存储非零元素。这些非零元素按以行为主序的顺序，从下标为 1 的位置开始依次存放在一维数组中，而 0位置存放数值 0。
0 1 2 3 4 5 6 7 8 9 10 11 12 13
0 3 12 9 5 20 30 7 17 21 9 -6 34 11
图 4-13
下面我们讨论一下对于任意给定的（ i,j），求得在一维数组中存储位置 k的方法。
否则当
0
11 1i-j1)-(i3 iji
k
操作算法的实现：
int Value(int A[ ],EntryType *item,int i,int j)
{
if
(i<1||i>MAX_ROW_INDEX||j<1||j>MAX_COL_INDE
X) return FALSE;
else { if (j>=(i-1)&&j<=(i+1)) k=3*(i-1)+j-i+1;
else k=0;
*item=A[k];
return TRUE;
}
}
2,稀疏矩阵的压缩存储若一个 m× n的矩阵含有 t个非零元素，且 t远远小于 m*n，则我们将这个矩阵称为 稀疏矩阵 。举例：
02000
00000
00021
00100
70003
图 4-14
稀疏矩阵的压缩存储方法 ——三元组表示法。
矩阵中的每个元素都是由行序号和列序号唯一确定的。因此，我们需要用三项内容表示稀疏矩阵中的每个非零元素，即形式为：
(i,j,value)
其中,i表示行序号,j表示列序号,value表示非零元素的值，通常将它称为三元。我们将稀疏矩阵中的所有非零元素用这种三元的形式表示，并将它们按以行为主的顺序存放在一个一维数组中，就形成了我们所说的三元组表示法。举例：
图 4-15
i j v a l u e
0 1 1 3
1 1 5 7
2 2 3 -1
3 3 1 -1
4 3 2 -2
5 5 4 2
类型定义：
#define MAX_SIZE 100 最大的非零元素个数
typedef struct{
int i,j; //行序号,列序号
EntryType value; //非零元素值
}Three_Item;
typedef struct {
Three_Item Item[MAXSIZE];
//存储非零元素的一维数组
int rows,cols,tu;
//稀疏矩阵的总行数,列数及非零元素个数
}Matrix;
操作算法的实现：
（ 1）返回元素内容
int Value(Matrix M,EntryType *item,int i,int j)
{
if (i<1||i>rows||j<1||j>cols) exit(ERROR);
else { for (p=0;p<M.tu;p++)
if (M.item[p].i==i&&M.item[p].j==j)
{ *item=M.item[p].value; return OK; }
else if
(M.item[p].i>i||M.item[p].i==i&&M.Item[p].j>j) break;
*item=0;
return OK;
}
}
（ 2）输出三元组表示的稀疏矩阵
void Print(Matrix M)
{
for (p=0,i=1;i<=M.rows;i++) {
for (j=1;j<=M.cols;j++)
if (p<M.tu&&M.item[p].i==i&&M.item[p].j==j)
printf(“%4d”,M.item[p++].value;);
else printf(“%4d”,0);
printf(“\n”);
}
}
串的定义、存储结构和基本运算
数组的定义、基本运算和存储结构
特殊矩阵的压缩存储退出
4.1 串
4.2 数组
4.1 串
4.1.1 串的定义和基本运算串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串,串 是一个有穷字符序列。
串一般记作：
s=,a1a2...an” (n?0)
其中,s是串的名称，用双引号（“”）括起来的字符序列是串的值； ai可以是字母、数字或其他字符；
串中字符的数目 n被称作串的 长度 。当 n=0时，串中没有任何字符，其串的长度为 0，通常被称为 空串 。
s1=,”
s2=,,
s1中没有字符，是一个空串；而 s2中有两个空格字符，它的长度等于 2，它是由空格字符组成的串，一般称此为 空格串 。
概念：
子串,主串,串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。
例如，有下列四个串 a,b,c,d：
a=,Welcome to Beijing”
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,s2start,len)
（ 6） 串的定位 Index(s1,s2)
例如 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个字符开始的连续 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 unsigned char String[MAX_STRING];
第二种是在程序执行过程中，利用标准函数
malloc和 free动态地分配或释放存储字符串的存储单元，
并以一个特殊的字符作为字符串的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源的利用率。类型定义如下所示：
typedef struct{
char *str;
int length;
}STRING;
不同的定义形式，算法中的处理也略有不同。下面我们将给出在第二种顺序存储方式下串的几个基本操作的算法。
（ 1） 串的赋值
int StringAssign(STRING*s,char *string_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-
>str[0]=’\0’; s->length=0; } //空串
else {
s->str=(char*)malloc((len+1)*sizeof(char));
//分配空间
if (!s->str) return ERROR;
s->str[0..len]=string_constant[0..len];
//对应的字符赋值
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(&s,s1->str);
//将 s1原来的内容保留在 s中
len=Length(s1)+Length(s2);
//计算 s1和 s2的长度之和
free(s1->str);
//释放 s1原来占据的空间
s1->str=(char*)malloc((len+1)*sizeof(char));
//重新为 s1分配空间
if (!s1) return ERROR;
else { //连接两个串的内容
s1->str[0..Length(s)-1]=s.str[0..Length(s)-1)];
s1->str[Length(s)..len+1]=s2.str[0..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 (start<1||start>len2||len2<=0||len>len2-start+1) {
//判断 start和 len的合理性
s1->str=(char*)malloc(sizoef(char));s1->str[0]=’\0’;s1-
>length=0;return ERROR;}
s1->str=(char*)malloc((len+1)*sizeof(char));
if (!s1.str) return ERROR;
s1->str[0..len-1]=s2.str[start-1..start+len -2];
s1->str[len]=’\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 (i<len1&&j<len2) {
if (s1.str[i]==s2.str[j]) { i++; j++; }
else {i=i-j+1; j=0;} //对应字符不相等时，重新比较
}
if (j==len2) return i-len2+1;
else return 0;
}
2,链式存储结构由于串结构中每个数据元素为一个字符，所以最直接的链式存储结构是每个结点的数据域存放一个字符。举例：
s t r i n g ^S
图 4-1
优点是操作方便；不足之处是存储密度较低。所谓存储密度为：
实际分配的存储密度串值所占的存储单元存储密度?
若要将多个字符存放在一个结点中，就可以缓解这个问题。举例：
S s t r i n g # # # # ^
图 4-2
由于串中的字符个数不一定是每个结点存放字符个数的整倍数，所以，需要在最后一个结点的空缺位置上填充特殊的字符。
这种存储形式优点是存储密度高于结点大小为 1 的存储形式；不足之处是做插入、删除字符的操作时，
可能会引起结点之间字符的移动，算法实现起来比较复杂。
4.2 数组
4.2.1 数组的定义和基本运算数组的特点是每个数据元素可以又是一个线性表结构。因此，数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，
即为 向量 ；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。
结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。举例：
1,11,10,1
1,11110
1,00100
.,,
.,,.,,.,,.,,
.,,
.,,
nmmm
n
n
nm
aaa
aaa
aaa
A
图 4-3
其中,A是数组结构的名称，整个数组元素可以看成是由 m个行向量和 n个列向量组成，其元素总数为
m× n。在 C语言中，二维数组中的数据元素可以表示成 a[表达式 1][表达式 2]，表达式 1和表达式 2被称为下标表达式，比如,a[i][j]。
数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、
删除元素的操作。
二维数组结构的基本操作：
（ 1） 给定一组下标，修改该位置元素的内容
Assign(A,item,index1,index2)
（ 2）给定一组下标，返回该位置的元素内容
Value(A,item,index1,index2)
4.2.2 数组的存储结构从理论上讲，数组结构也可以使用两种存储结构，
即顺序存储结构和链式存储结构。然而，由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。
组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。
举例：
图 4-4
1,11,10,1
1,11110
1,00100
.,,
.,,.,,.,,.,,
.,,
.,,
nmmm
n
n
nm
aaa
aaa
aaa
A
a 00 a 01,.,a 0,n -
1
a 10 a 11,.,a 1,n -
1
...,.,a m-
1,0
a m-
1,1
..,a m - 1,n -
1
第 0行 第 1行 第 m-1行图 4-5
a 00 a 10,.,a m-
1,0
a 01 a 11,.,a m - 1,1,..,.,a 0,n - 1 a 1,n - 1,.,a m-
1,n - 1
第 0列 第 1列 第 m-1列图 4-6
LOC(i,j)=LOC(0,0)+(n*i+j)*L
数组结构的定义：
#define MAX_ROW_INDEX 10
#define MAX_COL_INDEX 10
typedef struct {
EnterType
item[MAX_ROW_INDEX][MAX_COL_INDEX] ;
} ARRAY;
基本操作算法举例：
（ 1）给数组元素赋值
void Assign(ARRAY *A,EnterType item,int index1,int
index2)
{
if (index1<0||index1>=MAX_ROW_INDEX||
index2<0||index2>=MAX_COL_INDEX) exit(ERROR);
else A->item[index1][index2]=item;
}
（ 2）返回给定位置的元素内容
int Value(ARRAY A,EntryType *item,int index1,int
index2)
{
if (index1<0||index1>=MAX_ROW_INDEX||
index2<0||index2>=MAX_COL_INDEX) return
FALSE;
else { *item= A.item[index1][index2];
return OK;
}
}
3．矩阵的压缩存储矩阵是在很多科学与工程计算中遇到的数学模型。
在数学上，矩阵是这样定义的：它是一个由 s× n个元素排成的 s行（横向） n列（纵向）的表。下面就是一个矩阵：
图 4-7 s× n的矩阵它是一个 s× n的矩阵。
mnmm
n
n
aaa
aaa
aaa
.,,
.,,.,,.,,.,,
.,,
.,,
21
22221
11211
1,特殊矩阵所谓 特殊矩 阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。
对称矩阵的特点是 aij=aji，比如，下面就是一个对称矩阵：
图 4-8
1423417
2320123
41275
173510
下（上）三角矩阵的特点是以主对角线为界的上
（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。比如，下面是一个下三角矩阵：
2092613
030108
00126
00029
图 4-9
对角矩阵的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。比如，下面就是一个 3阶对角矩阵：
1134000
692100
0177300
002059
000123
图 4-10
对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。
三种特殊矩阵的压缩方法：。
（ 1）对称矩阵对称矩阵的特点是 aij=aji。一个 n× n的方阵，共有
n2个元素，而实际上在对称矩阵中有 n(n-1)/2个元素可以通过其他元素获得。
压缩的方法是首先将二维关系映射成一维关系，
并只存储其中必要的 n(n+1)/2个（主对角线和下三角）
元素内容，这些元素的存储顺序以行为主序。举例：
假设定义一个数组型变量,int A[10];
0 1 2 3 4 5 6 7 8 910 5 7 3 12 20 17 4 23 14
图 4-11
k是对称矩阵位于（ i,j）位置的元素在一维数组中的存放位置。
ji 1
2
)1(
ji 1
2
)1(
当当
i
jj
j
ii
k
操作算法的实现：
int Value(int A[],EntryType *item,int i,int j)
{
if (i<1||i>MAX_ROW_INDEX||
j<1||j>MAX_COL_INDEX) return FALSE;
else { if (i>=j) k=i*(i-1)/2+j-1;
else k=j*(j-1)/2+i-1;
*item=A[k];
return TRUE;
}
}
（ 2）下（上）三角矩阵下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在 0单元，下三角和主对角上的元素从 1号单元开始存放。
举例：
0 1 2 3 4 5 6 7 8 9 10
0 29 6 12 8 10 30 13 26 9 20
图 4-12
ji 0
ji
2
)1(
当当j
ii
k
对于任意的（ i,j），在一维数组中的存放位置可利用下列公式求得：
操作算法的实现：
int Value(int A[],EntryType *item,int i,int j)
{
if
(i<1||i>MAX_ROW_INDEX||j<1||j>MAX_COL_INDE
X) return FALSE;
else { if (i>=j) k=i*(i-1)/2+j;
else k=0;
*item=A[k];
return TRUE;
}
}
（ 3）对角矩阵我们以三阶对角矩阵为例讨论一下它的压缩存储方法。对于对角矩阵，压缩存储的主要思路是只存储非零元素。这些非零元素按以行为主序的顺序，从下标为 1 的位置开始依次存放在一维数组中，而 0位置存放数值 0。
0 1 2 3 4 5 6 7 8 9 10 11 12 13
0 3 12 9 5 20 30 7 17 21 9 -6 34 11
图 4-13
下面我们讨论一下对于任意给定的（ i,j），求得在一维数组中存储位置 k的方法。
否则当
0
11 1i-j1)-(i3 iji
k
操作算法的实现：
int Value(int A[ ],EntryType *item,int i,int j)
{
if
(i<1||i>MAX_ROW_INDEX||j<1||j>MAX_COL_INDE
X) return FALSE;
else { if (j>=(i-1)&&j<=(i+1)) k=3*(i-1)+j-i+1;
else k=0;
*item=A[k];
return TRUE;
}
}
2,稀疏矩阵的压缩存储若一个 m× n的矩阵含有 t个非零元素，且 t远远小于 m*n，则我们将这个矩阵称为 稀疏矩阵 。举例：
02000
00000
00021
00100
70003
图 4-14
稀疏矩阵的压缩存储方法 ——三元组表示法。
矩阵中的每个元素都是由行序号和列序号唯一确定的。因此，我们需要用三项内容表示稀疏矩阵中的每个非零元素，即形式为：
(i,j,value)
其中,i表示行序号,j表示列序号,value表示非零元素的值，通常将它称为三元。我们将稀疏矩阵中的所有非零元素用这种三元的形式表示，并将它们按以行为主的顺序存放在一个一维数组中，就形成了我们所说的三元组表示法。举例：
图 4-15
i j v a l u e
0 1 1 3
1 1 5 7
2 2 3 -1
3 3 1 -1
4 3 2 -2
5 5 4 2
类型定义：
#define MAX_SIZE 100 最大的非零元素个数
typedef struct{
int i,j; //行序号,列序号
EntryType value; //非零元素值
}Three_Item;
typedef struct {
Three_Item Item[MAXSIZE];
//存储非零元素的一维数组
int rows,cols,tu;
//稀疏矩阵的总行数,列数及非零元素个数
}Matrix;
操作算法的实现：
（ 1）返回元素内容
int Value(Matrix M,EntryType *item,int i,int j)
{
if (i<1||i>rows||j<1||j>cols) exit(ERROR);
else { for (p=0;p<M.tu;p++)
if (M.item[p].i==i&&M.item[p].j==j)
{ *item=M.item[p].value; return OK; }
else if
(M.item[p].i>i||M.item[p].i==i&&M.Item[p].j>j) break;
*item=0;
return OK;
}
}
（ 2）输出三元组表示的稀疏矩阵
void Print(Matrix M)
{
for (p=0,i=1;i<=M.rows;i++) {
for (j=1;j<=M.cols;j++)
if (p<M.tu&&M.item[p].i==i&&M.item[p].j==j)
printf(“%4d”,M.item[p++].value;);
else printf(“%4d”,0);
printf(“\n”);
}
}
